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

（北京細(xì)推科技有限公司 北京 100026）

1 引言

隨著信息技術(shù)的發(fā)展，需要處理的數(shù)據(jù)量也越來(lái)越大，如何能更有效地獲得想要的信息是人們?cè)絹?lái)越關(guān)注的問(wèn)題，其中常用的辦法就是對(duì)數(shù)據(jù)做粗分類處理，根據(jù)數(shù)據(jù)的某些特征把數(shù)據(jù)粗分為若干類，再根據(jù)想要信息的特征去相應(yīng)的類別里面去查找，這樣不僅縮小了搜索范圍提高了搜索效率，還明顯節(jié)省了時(shí)間。

生物識(shí)別技術(shù)主要是根據(jù)人體固有的生理特性和行為特性等生物特征進(jìn)行身份認(rèn)證的一種技術(shù)，現(xiàn)在生物識(shí)別技術(shù)已經(jīng)應(yīng)用于生活的各個(gè)方面，如指紋、人臉、靜脈、虹膜等。

以人臉識(shí)別為例，當(dāng)1：n識(shí)別時(shí)，即從成千上萬(wàn)的人臉中找出目標(biāo)人臉，如果n比較大的情況下算法的時(shí)間復(fù)雜度比較高，因此需要縮小搜索范圍，提高算法的運(yùn)行效率，因此有必要對(duì)數(shù)據(jù)做粗分類處理。

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

2 基于kmeans-SVM的樹粗分類

本文提出一種結(jié)合k-means［1］和SVM［2～7］的一種樹形粗分類方法，利用k-means［1］提供的無(wú)監(jiān)督分類結(jié)果作為訓(xùn)練SVM［2～7］的訓(xùn)練數(shù)據(jù)，然后在根據(jù)SVM［2～7］的預(yù)測(cè)結(jié)果不斷調(diào)分割超平面，最后形成二叉樹型分類樹。

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

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

滿足：

利用拉格朗日法把上述二次優(yōu)化問(wèn)題轉(zhuǎn)化為其對(duì)偶問(wèn)題：

求解對(duì)偶問(wèn)題得到原二次規(guī)劃問(wèn)題的解，最終得到最優(yōu)分類超平面。

k-means［1］聚類算法是無(wú)監(jiān)督的分類算法，此算法分類時(shí)根據(jù)樣本距離簇中心點(diǎn)的距離來(lái)劃分類別，當(dāng)樣本位于兩簇的連接地帶時(shí)，同一類別的樣本可能被錯(cuò)誤地分到了不同的簇里面，我們可以用聚類得到的兩簇有“標(biāo)簽”的數(shù)據(jù)去訓(xùn)練一個(gè)SVM［2～7］分類超平面，然后根據(jù)超平面去調(diào)整兩簇有“標(biāo)簽”的數(shù)據(jù)，用新得到的兩簇有“標(biāo)簽”的數(shù)據(jù)再訓(xùn)練一個(gè)新的分類超平面，以此迭代不斷更新兩個(gè)有“標(biāo)簽”的簇和分類超平面，直到有“標(biāo)簽”的簇和分類超平面不在變化則停止迭代。最后根據(jù)最終的分類超平面把數(shù)據(jù)分割成兩部分，這兩部分?jǐn)?shù)據(jù)分別作為新節(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)。

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

預(yù)測(cè)的時(shí)候指定knn［15～16］的范圍，使用knn［15～16］算法根據(jù)每個(gè)節(jié)點(diǎn)數(shù)據(jù)中每一類的中心點(diǎn)數(shù)據(jù)返回預(yù)測(cè)數(shù)據(jù)距離這些中心點(diǎn)最近的前若干（預(yù)測(cè)時(shí)需要提前指定）結(jié)果。

3 算法流程

1）在根節(jié)點(diǎn)用k-means［1］聚類算法把數(shù)據(jù)聚成兩簇，分別標(biāo)記為0和1。

2）利用步驟1）得到的兩類數(shù)據(jù)去訓(xùn)練一個(gè)SVM［2～7］的分類器，再用得到的SVM［2～7］分類器去分類訓(xùn)練數(shù)據(jù)，根據(jù)結(jié)果重新劃分0和1數(shù)據(jù)集里的數(shù)據(jù)，接下來(lái)用得到的新0和1數(shù)據(jù)集訓(xùn)練新的SVM［2～7］分類器；重復(fù)以上過(guò)程直到0和1數(shù)據(jù)集不在發(fā)生變化時(shí)則停止訓(xùn)練。

3）由步驟2）中得到的0和1兩個(gè)數(shù)據(jù)集，在根據(jù)樣本的實(shí)際標(biāo)簽，若同一類中的數(shù)據(jù)被完全劃分到0或者1中，則這類樣本不做處理；若同一類中的數(shù)據(jù)既有一部分劃分到了0中，又有一部分?jǐn)?shù)據(jù)劃分到了1中，則這類數(shù)據(jù)的全部數(shù)據(jù)既要放入0中，又要放入1中。

4）以步驟3）中最終劃分得到的0和1數(shù)據(jù)分別為新的父節(jié)點(diǎn)，執(zhí)行步驟1）、2）、3），直到滿足二叉樹的終止生長(zhǎng)條件。

5）預(yù)測(cè)時(shí)指定knn［15～16］的搜索范圍，根據(jù)每個(gè)候選節(jié)點(diǎn)上標(biāo)簽信息以及中心點(diǎn)完成粗分類預(yù)測(cè)。

流程圖如圖1。

圖1 算法流程圖

4 實(shí)驗(yàn)及分析

實(shí)驗(yàn)以人臉分類為例，實(shí)驗(yàn)中采樣LFW人臉數(shù)據(jù)庫(kù)，LFW數(shù)據(jù)集中一共包含5000個(gè)人臉數(shù)據(jù)，數(shù)據(jù)集中的人臉大多是在非限制環(huán)境下拍攝的，數(shù)據(jù)集包含13000多張人臉圖像。

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

實(shí)驗(yàn)結(jié)果如表1。

表1 實(shí)驗(yàn)對(duì)比結(jié)果

從表1的實(shí)驗(yàn)結(jié)果可以看出本文提出的方法優(yōu)于kdtree［8～9］方法。

5 結(jié)語(yǔ)

針對(duì)大數(shù)據(jù)范圍搜索時(shí)可以使用粗分類方法，縮小目標(biāo)的搜索范圍，本文方法的優(yōu)點(diǎn)在于將易分錯(cuò)數(shù)據(jù)分別加入左右子樹的訓(xùn)練數(shù)據(jù)中去訓(xùn)練新的節(jié)點(diǎn)，從而一定程度上避免了誤差累計(jì)，增加了識(shí)別準(zhǔn)確率，在利用樹形結(jié)構(gòu)的優(yōu)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行拆分很好地達(dá)到了縮小搜索范圍的目的，提高了搜索效率。