基于kmeans-SVM的二叉樹粗分類方法?

（北京細推科技有限公司 北京 100026）

1 引言

隨著信息技術的發展，需要處理的數據量也越來越大，如何能更有效地獲得想要的信息是人們越來越關注的問題，其中常用的辦法就是對數據做粗分類處理，根據數據的某些特征把數據粗分為若干類，再根據想要信息的特征去相應的類別里面去查找，這樣不僅縮小了搜索范圍提高了搜索效率，還明顯節省了時間。

生物識別技術主要是根據人體固有的生理特性和行為特性等生物特征進行身份認證的一種技術，現在生物識別技術已經應用于生活的各個方面，如指紋、人臉、靜脈、虹膜等。

以人臉識別為例，當1：n識別時，即從成千上萬的人臉中找出目標人臉，如果n比較大的情況下算法的時間復雜度比較高，因此需要縮小搜索范圍，提高算法的運行效率，因此有必要對數據做粗分類處理。

常用的分類方法：k-means［1］、支持向量機［2～7］（Support Vector Machine，SVM）、Kdtree［8～9］、集成分類器［10～12］、貝葉斯分類［13～14］等。k-means［1］算法是一種基于樣本間相似性度量的間接聚類方法，屬于非監督學習方法，實現起來比較簡單。此算法以k為參數，把n個對象分為k個簇，以使簇內具有較高的相似度而緊密的聯系在一起，而且使得簇間的相似度較低而距離盡量的大。但是k-means［1］是局部最優的，而且容易受到初始質心的影響。支持向量機［2～7］（Support Vector Machine，SVM）是在特征空間里尋找一個最大間隔超平面，在這個最大間隔超平面的兩邊建立兩個互相平行的超平面，這兩個平行超平面間的距離越大，分類器的總誤差越小。SVM［2～7］在解決非線性以及高維模式識別問題中有許多特有的優勢。但是SVM［2～7］屬于有監督學習，使用SVM［2～7］訓練之前需要先做粗分類好訓練數據。Kdtree［8～9］是k-dimensional tree的縮寫，是一種高維索引樹形數據結構，常用于最近鄰查找（Near?est Neighbor）和近似最近鄰查找（Approximate Near?est Neighbor），因此可以用來做粗分類，縮小目標的搜索范圍，但是Kdtree［8～9］做粗分類的話一般拿各類數據的類中心來訓練樹形結構。集成分類器［10～12］是指把性能較低的多種弱學習器，通過適當組合形成高性能的強學習器的方法，通常采用Bagging和Boosting的方差去訓練單個弱分類器，然后通過投票的方式做最終的決策，集成分類器取得了很好的分類效果。貝葉斯分類［13～14］是一類利用概率統計知識進行分類的一種統計學分類方法。

2 基于kmeans-SVM的樹粗分類

本文提出一種結合k-means［1］和SVM［2～7］的一種樹形粗分類方法，利用k-means［1］提供的無監督分類結果作為訓練SVM［2～7］的訓練數據，然后在根據SVM［2～7］的預測結果不斷調分割超平面，最后形成二叉樹型分類樹。

首先用k-means［1］算法得到用以訓練粗分類分類器的訓練數據。假設樣本數據集D={x1,x2,…,xn}，以及數據集D對應的標簽Y={y1,y2,…,yn}，其中yi∈{-1,1} 。聚類的簇數k，簇劃分C={c1,c2,…,ck}，從數據D中隨機選擇k個樣本作為初始的k個質心，計算數據D中的任意樣本xi(i∈[1,n])距離各個質心cj(j∈[1,k])的距離，把xi劃分到距離最小的質心所在的簇，當D中所有樣本劃分完后各自重新計算k簇的k個質心，然后根據新的k個質心重新劃分數據D，重復更新質心直到質心不在發生變化為止。這樣就得到了訓練SVM［2～7］的k類數據C={c1,c2,…,ck}。

其次用SVM［2～7］在特征空間中找到一個最優分類超平面wT?x+b=0把數據C={c1,c2,…,ck}分開，要找到這個最優平面，需要求解如下二次規劃問題：

滿足：

利用拉格朗日法把上述二次優化問題轉化為其對偶問題：

求解對偶問題得到原二次規劃問題的解，最終得到最優分類超平面。

k-means［1］聚類算法是無監督的分類算法，此算法分類時根據樣本距離簇中心點的距離來劃分類別，當樣本位于兩簇的連接地帶時，同一類別的樣本可能被錯誤地分到了不同的簇里面，我們可以用聚類得到的兩簇有“標簽”的數據去訓練一個SVM［2～7］分類超平面，然后根據超平面去調整兩簇有“標簽”的數據，用新得到的兩簇有“標簽”的數據再訓練一個新的分類超平面，以此迭代不斷更新兩個有“標簽”的簇和分類超平面，直到有“標簽”的簇和分類超平面不在變化則停止迭代。最后根據最終的分類超平面把數據分割成兩部分，這兩部分數據分別作為新節點的訓練數據。

利用k-means［1］無監督學習的特點，根據特征空間中的歐式距離把相近數據聚成若干簇。k-means［1］把特征數據分成兩類，分別標記為0和1，接下來根據這兩簇有標簽的數據訓練一個SVM［2～7］的二分類器，找到一個平面把盡可能多的0和1分別分割在一個平面的兩側，SVM［2～7］訓練完成以后拿訓練好的平面測試k-means［1］聚類得到的兩類數據，把SVM［2～7］預測準確的數據拿來重新訓練SVM［2～7］的分割平面，照此方法迭代更新SVM［2～7］的分割平面直到用SVM［2-7］預測數據的誤差個數不在發生變化為止。根據最后得到的SVM［2～7］分割平面把k-means［1］得到的兩類數據中SVM［2～7］能分類正確的數據分別是左右兩個子節點的訓練數據，把SVM［2～7］分類錯誤的數據同時屬于兩個子節點的訓練數據。并且在每個節點都要保存該節點數據的所有類別數據的中心點（同類數據求和算平均值），每一類中心點數據在做預測knn［15～16］搜索時使用。

預測的時候指定knn［15～16］的范圍，使用knn［15～16］算法根據每個節點數據中每一類的中心點數據返回預測數據距離這些中心點最近的前若干（預測時需要提前指定）結果。

3 算法流程

1）在根節點用k-means［1］聚類算法把數據聚成兩簇，分別標記為0和1。

2）利用步驟1）得到的兩類數據去訓練一個SVM［2～7］的分類器，再用得到的SVM［2～7］分類器去分類訓練數據，根據結果重新劃分0和1數據集里的數據，接下來用得到的新0和1數據集訓練新的SVM［2～7］分類器；重復以上過程直到0和1數據集不在發生變化時則停止訓練。

3）由步驟2）中得到的0和1兩個數據集，在根據樣本的實際標簽，若同一類中的數據被完全劃分到0或者1中，則這類樣本不做處理；若同一類中的數據既有一部分劃分到了0中，又有一部分數據劃分到了1中，則這類數據的全部數據既要放入0中，又要放入1中。

4）以步驟3）中最終劃分得到的0和1數據分別為新的父節點，執行步驟1）、2）、3），直到滿足二叉樹的終止生長條件。

5）預測時指定knn［15～16］的搜索范圍，根據每個候選節點上標簽信息以及中心點完成粗分類預測。

流程圖如圖1。

圖1 算法流程圖

4 實驗及分析

實驗以人臉分類為例，實驗中采樣LFW人臉數據庫，LFW數據集中一共包含5000個人臉數據，數據集中的人臉大多是在非限制環境下拍攝的，數據集包含13000多張人臉圖像。

本實驗每個人臉圖片提取一個1024維度的特征向量。其中訓練數據49686個樣本，測試數據24830個樣本。對比方法是kdtree［8～9］中提到的算法，其中訓練kdtree［8～9］時使用每類特征的中心點作為訓練數據。實驗分別測試了在測試集中搜索范圍前200、300、400和500條件下的準確率。

實驗結果如表1。

表1 實驗對比結果

從表1的實驗結果可以看出本文提出的方法優于kdtree［8～9］方法。

5 結語

針對大數據范圍搜索時可以使用粗分類方法，縮小目標的搜索范圍，本文方法的優點在于將易分錯數據分別加入左右子樹的訓練數據中去訓練新的節點，從而一定程度上避免了誤差累計，增加了識別準確率，在利用樹形結構的優點對數據集進行拆分很好地達到了縮小搜索范圍的目的，提高了搜索效率。