雙層分類策略及其實現(xiàn)算法

摘 要：針對常見分類算法在全局和局部區(qū)域性能不一致的問題，提出了雙層分類策略及其實現(xiàn)算法。雙層分類策略的思想是離線地建立全局分類器，當全局分類器決策信用度低于指定閾值時，在線生成局部分類器進行決策修正。實現(xiàn)算法以支持向量機(support vector machine，SVM)和模糊分類器(fuzzy classifier)作為全局與局部分類器，命名為SFC。為全局分類器定義了SVM決策信用度的評估機制，并以此給出局部分類器的啟動條件。為局部分類器設計了基于新測度的模糊隸屬度函數完成決策修正。實驗結果表明，SFC顯著提高了單一分類器的性能，可達到較好的分類效果。由此說明雙層分類思想是正確且有效的，可作為一種通用思想對應多種具體實現(xiàn)算法。

關鍵詞：雙層分類策略；全局分類器；局部分類器；信用度評估；新測度

中圖分類號：TP139文獻標志碼：A

文章編號：1001-3695(2009)06-2074-05

doi:10.3969/j.issn.1001-3695.2009.06.022

Double-classification strategy and its implementation algorithm

LING Ping1，2，ZHOU Chun-guang2

(1.College of Computer Science Technology， Xuzhou Normal University， Xuzhou Jiangsu 221116， China；2.College of Computer Science Technology， Jilin University， Changchun 130012， China)

Abstract:To address the unsteady performance of common classifier in global environment and local region，this paper proposed a double-classification strategy and its implementation algorithm.The idea of the strategy was to create global classifier offline and local classifier online. When the confidence of global classifier’s decision was below some threshold，constructed local classifier to refine the global decision. The implementation algorithm employed support vector machine (SVM) and fuzzy classifier as global and local classifier respectively， named as SFC.Defined the confidence scoring method of SVM decision.Based on that，gave motivation condition of local classifier.For local classifier，defined a new metric to facilitate the work of fuzzy membership function. Empirical evidence shows SFC improves classification performance of the single classifier， and exhibites fine classification ability in applications. SFC’s good behaviors lead to the conclusion that double-classification idea is correct and valid， and it can be realized into multi implementations.

Key words:double-classification strategy; global classifier; local classifier; confidence scoring method; new metric

0 引言

分類算法是從已知類別的樣本中提取分類模型，并將其應用于測試數據之上的過程。理論上，分類算法的設計基于以下兩個假設^[1，2]：a）空間鄰近一致性假設，空間上鄰近的數據有一致的類別；b)分布方向一致性假設，在同一數據分布方向上的數據有一致的類別。其中，空間鄰近一致性假設在局部有效，而分布方向一致性假設則在全局有效。一般的分類算法往往基于兩個假設中的一個來建立分類器。例如，kNN^[3]是基于空間鄰近一致性假設的分類器，它以局部的鄰域信息作為分類的依據；而SVM^[4]則是基于分布方向一致性假設的分類器，它從數據分布的整體信息出發(fā)建立類別之間的分界面。顯然，若僅依據兩個原則中的一個設計算法，得到的分類器可能有局限性，即分類器不能在局部和全局均取得較好的分類效果。

鑒于此，本文提出雙層分類策略及其實現(xiàn)算法。雙層分類策略的思想是：構建離線的全局分類器及其決策評估機制，當全局決策的信用度低于指定閾值，在線地啟動局部分類器，進行決策修正。本文給出了以SVM和模糊分類器作為全局與局部分類器的實現(xiàn)算法，命名為SFC(SVM fuzzy classi-fier)。文中定義了SVM在二分類和多分類任務下決策信用度的評估機制及相應的局部分類器的啟動條件。局部模糊分類器的隸屬度函數中使用了新的測度，該測度利用局部信息的傳遞來獲知數據分布結構的信息，為決策修正提供幫助。在真實數據集上的實驗表明，相對于單一分類器，SFC有更高的準確率及良好的分類能力，這表明了雙層分類思想的正確性和有效性。

1 雙層分類策略及SFC算法

1.1 雙層分類思想

雙層分類策略對應的分類過程由全局分類器和局部分類器共同完成，以全局分類器的決策信用度作為啟動局部分類器的條件。本文選擇SVM和模糊分類器作為全局與局部分類器，原因如下：首先，SVM是結構風險最小這一優(yōu)化目標下得到的結果，其具有全局最優(yōu)、推廣能力好的特點；其次，SVM中使用了kernel（核）函數，可將數據從原輸入空間映射到一個特征空間，把問題的非線性解轉換為線性解，這樣使得SVM能夠處理較復雜的數據；最后，局部分類器應具有較低的復雜度，以保證雙層分類算法的計算代價相對于單一分類器的增長不至于過大。模糊分類器的主要計算耗費在于模糊隸屬度函數的計算。具體到本文設計的模糊分類器，其耗費在于用新測度計算訓練數據和測試數據之間的距離上。這一過程代價較小，符合此要求。

1.2 SFC算法

SFC算法框架

訓練階段：離線建立全局SVM分類器

測試階段：對被測試數據Q

a)使用全局分類器給出決策；

b)確定全局決策的信用度score(Q)；

c)若滿足局部分類器啟動條件，建立局部隸屬度函數；

d)給出最終決策。

這里，全局分類器以SVM為基礎。其過程簡單介紹如下。對給定數據集{(x1，y1)(x2，y2)…(xN，yN)}∈X×Y，X=Rn，Y是類別標志，Y = {1，-1}，SVM尋求具有最大分類間隔的決策函數f，并以決策函數的符號決定數據的類別：

f(x)=(w×Φ(x))+b(1)

當f(x)>0，x劃分為正類；否則，x被劃分為負類。f通過求解如下的最優(yōu)化目標獲得：

max 1/2wTw+CsvmΣiξi(2)

其中：ξi是松弛變量；Csvm是懲罰系數，表示在準確性和松弛性之間所做的權衡。將上式寫為Lagrange函數，轉換為Wolfe對偶形式，再利用kernel技巧，有

max Σiαi-1/2ΣiΣjαiαjyiyjK(xi，xj)(3)

s.t. 0≤αi≤Csvm ，Σiαiyi=0

其中:α是Lagrange乘子。設上述函數的最優(yōu)解為α=(α1，…，αl)T，則w=Ni=1yiαixi， 選擇滿足0＜αj＜Csvm的點xj，可求出b=yj-Ni=1yiαi(xi×xj)。那些滿足0＜αi＜Csvm的數據點稱為非限定支持向量(non-bounded SV，nbSV)，它們描述了數據簇的輪廓；那些滿足αi=Csvm的點稱為限定支持向量(bounded SV，bSV)，它們位于分界面的間隔內，是發(fā)生分類錯誤的點。K一般取Gaussian核函數：K(x，y)=exp(-q‖x-y‖2)。其中，q為核函數的尺度參數。

上述SVM解決了二分類問題。當處理多分類任務(設有M個類)，有兩種方式：a)建立M個一對余類SVM(SVM1r)^[5]，數據的類別由最大決策函數值決定；b)建立M(M-1)/2個一對一的SVM(SVM11)^[6]，數據的類別由投票機制完成。

2 SVM決策信用度評估機制及局部分類器啟動條件

2.1 SVM決策信用度評估

本節(jié)建立SVM決策的信用度評估機制。因為一個決策函數在數據分布的不同區(qū)域產生的決策的信用度不同，所以本文設定評估機制是一個以數據點為自變量的函數。信用度評估的思想是：分析SVM在被測試數據鄰域中的決策一致性，以一致性的高低決定決策信用度值。具體地，考察Q的鄰域NEI(Q)，統(tǒng)計其中正類和負類的數據量，記為plus和minus，同時記鄰域大小為Nnei。選出其中的主流類別：若plus>minus，則main=plus/Nnei；若plus

score(Q)=exp[main×sign(f(Q))×|f(Q)|](4)

其中:sign(f(Q))×main表示Q的類別與主流類別是否一致以及一致的程度。通過exp機制的調整，當兩者類別一致，score(Q)>1；否則，0

NEI(Q)由距離Q最近的前r個點組成。r根據訓練數據的信息確定，其啟發(fā)式設計步驟為：a)從小到大排列各訓練數據xi到其他點的距離，構成序列{‖xi-xj‖}；b)gap(i)=maxj{(‖xi-xj‖-‖xi-xj-1‖)/‖xi-xj‖}；c)r=ave{gap(i)}。

2.2 二分類任務下局部分類器的啟動條件

對于二分類任務，只需建立一個SVM，Q的類別由此SVM的決策函數符號決定。此時局部分類器的啟動條件為

score(Q)＜ε1(5)

閾值ε1定義為支持向量決策的信用度的平均值：

ε1= ave{score(v)，其中，v∈SVs}(6)

其中：SVs表示nbSV和bSV的集合。因為nbSV表達了正確劃分區(qū)的邊界，bSV代表了發(fā)生分類錯誤的實例，它們的信用度平均值反映了SVM正確分類區(qū)的邊緣，所以用做置信度的下限。當score(Q)低于此下限，說明Q有較大可能發(fā)生分類錯誤，需要重新決策。

2.3 多分類任務下局部分類器的啟動條件

本文選用SVM11來處理多分類任務。設共有M個類，建立于I類和J類上的SVM對應的決策函數為fIJ(x)(I=1，…，M；J=I+1，…，M)，相應的信用度函數為scoreIJ(x)。這里首先提出新的投票方法，然后給出基于新投票方法的局部分類器啟動條件。新投票過程將信用度值作為具體的投票值，步驟如下：

vote[1..M]=0;

for I=1:M

for J = I+1:M

if (fIJ(Q)> 0) vote[I]=vote[I] +scoreIJ(Q);

else vote[J]=vote[J]+scoreIJ(Q);

endif

endfor

endfor

其中：vote[1..M]記錄了M個類上獲得的投票值；Q的類別由最高投票值決定，即label=maxJ{vote[J]}。此時局部分類器啟動的條件為

vote[label]-vote[second_label]<ε2(7)

其中，second_label對應了除label之外最高投票值的類別：second_label=max J≠label{vote[I]}。這一啟動條件說明，此時Q在兩個最有可能的類別上的隸屬度接近，不能有充分把握將其劃分為第一個類。閾值指定為

ε2 = coef ×vote[label](8)

本文設定coef=0.3。

3 局部分類器的在線生成

3.1 模糊分類器設計

局部模糊分類器的啟動過程為：考察NEI(Q)中出現(xiàn)的類別，在所涉及的類別中求出Q的最近鄰，用最近鄰信息參與隸屬度函數定義。設NEI(Q)中出現(xiàn)的類別為C1…CL(L≤M)，求這些類別中Q的最近鄰b1…bL：

bJ=arg minxi∈CJ‖Q-xi‖*(9)

則Q屬于CJ類的隸屬度定義為

ρJ(Q)=1-‖Q-bJ‖*/LI=1‖Q-bI‖*(10)

其中：Q將被標志為隸屬度值最大的類。上述隸屬度函數對測度定義有較大依賴，當所測度提供的距離信息不能正確反映類別劃分狀態(tài)時，局部分類器的性能將受到較大影響。如圖1所示的數據集中，在呈帶狀分布的第一個簇(cluster1)中，歐式測度便無法提供正確分類信息。因為若從類別歸屬的角度分析，數據點與同一類別內點之間的距離應小于它與其他類別內的點的距離，即應有‖x-y‖<‖x-z‖。然而在歐式測度下卻有‖x-y‖=0.535 6，‖x-z‖=0.223 9，相應的路徑如圖2所示。為解決此問題，本文將定義一個新測度，將數據的分布特征納入測度定義之中，以應對多樣的數據分布。

3.2 新測度定義

新測度尋求x、y兩點間的多條可達路徑，從中選擇最短的路徑，以此路徑的長度作為兩者的距離值。所考察的路徑包括x、y之間的直接可達路徑，以及兩者之間通過若干點傳遞構成的間接路徑。相對于歐式測度只考察x、y之間的惟一路徑，即直接相連兩點的邊構成的路徑，并以此邊的長度作為距離的做法，新測度擴展了路徑空間，具有靈活性。這時問題相當于在一個完全無向圖中確定兩點間的最短路徑，圖的頂點表示數據，兩點之間邊表示兩點間的直接可達路徑。首先定義兩點間邊的權值：

W（x，y）=ηxy[exp(‖x-y‖2)-1](11)

上述定義中用exp機制對歐式測度信息作調整，以此強調數據的類別邊界。ηxy是相對密度比率，定義為

ηxy=2-min{AD(x)，AD(y)}/max{AD(x)，AD(y)}(12)

其中:AD(x)=aveu∈NEI(x){‖x-u‖}。

其中：AD(x)是x鄰域中的平均距離，它表示了x所在局部區(qū)域的分布密度；NEI(x)的大小仍由前文啟發(fā)式步驟確定；ηxy的作用是平衡x和y所在局部區(qū)域的密度差異，消除由于這種差異對距離計算帶來的誤差。當x、y的分布密度接近，則W(x，y)趨近于exp(‖x-y‖2)-1；否則，W(x，y)趨近于2×[exp(‖x-y‖2)-1]。新測度的計算可使用Dijstra算法^[7]。

再定義路徑長度，對一條從x出發(fā)，到y(tǒng)終止的路徑p，p={z1，z2，…，zh}。其中：x= z1，zh=y。其長度為

PL(p)=h-1i=1W(zi，zi+1)(13)

則x、y之間的新距離定義為

‖x-y‖*=minp∈path[x，y]{PL(p)}(14)

其中：path[x，y]表示x、y之間所有路徑的集合。依據新測度‖#8226;‖*，圖2中的‖x-z‖*= 0.013 5，‖x-y‖*=0.012 6，相應的最短路徑如圖3所示。這樣的距離信息可正確反映類別劃分狀態(tài)，幫助局部分類器作出正確決策。

4 實驗分析

實驗有三個目的：a)觀察新測度的性能；b)比較SFC與單一分類器的性能；c)比較SFC和常用分類算法的性能。

4.1 新測度性能實驗

該部分實驗將不同的測度應用于K-means方法，用聚類結果來評價測度的優(yōu)劣。參與比較的測度有歐式測度‖#8226;‖、‖#8226;‖*和‖#8226;‖0。其中，‖#8226;‖0中未使用相對密度比率，它對邊的權值定義是

W0（x，y）=exp(‖x-y‖2)-1(15)

數據集2如圖4所示。圖5和6是K-means在三種測度下的結果。可見，‖#8226;‖提供的結果與真實的簇分布差距很大，說明歐式距離信息無法正確反映數據類別。‖#8226;‖*和‖#8226;‖0由于使用了最短路徑方式的距離定義，能夠克服數據分布形狀給距離計算帶來的干擾，產生正確的聚類結果。這說明了新測度定義思想的有效性。數據集3如圖7所示，其特點是數據簇分布密度差異較大，以此觀察ηxy的效果。圖8~10是三種測度下的聚類結果。此時除‖#8226;‖外，‖#8226;‖0也未能給出正確結果，原因可從圖11~13所示的最短路徑看出。當測定同一簇中兩點間的距離時，‖#8226;‖選用了直接的直線路徑，‖#8226;‖0選用的最短路徑穿越了其他的簇，只有‖#8226;‖*選用的路徑穿越的是同一簇的區(qū)域，反映了正確的類別信息。這說明ηxy能夠平衡數據局部密度的差異，在簇的分布密度不均勻情況下也能找到符合數據分布結構的路徑信息。

4.2 SFC與單一分類器比較

此部分實驗對比SFC和單一的全局分類器、局部分類器的性能。具體參與比較的是SVM1r^[5]、SVM11^[6]，以及NN、kNN。kNN中使用的鄰域大小用交叉驗證方法獲得。為觀察文中給出的鄰域設定方法的效果，此處還執(zhí)行了另一版本的SFC過程，即rSFC。該方法用交叉驗證方式確定SFC中的鄰域大小。數據集從UCI選用^[8]，以30%的數據作為訓練數據。實驗將在分類性能和時間耗費上分別進行比較。

4.2.1 分類性能比較

首先觀察分類能力，各方法的分類錯誤率如表1所示。從中可看出，SFC相對于單一分類器在性能上有明顯提高。原因在于：SFC擁有全局和局部分類器的優(yōu)勢，同時克服了它們各自的不足。rSFC由于搜索了參數空間，產生比SFC更好的結果。SFC和rSFC在Iris、Sonar、Vote及Liver四個數據集上的差距不大，但Sonar數據集上的差距稍大。這是因為Sonar是一個高維低密度數據集，有208個60維的數據，其分布相對稀疏。此時的鄰域信息較弱，不能準確表示數據間的關系信息。因此用文中給出啟發(fā)式步驟確定的r欠準確，使得分類錯誤率稍高。SFC的整體表現(xiàn)說明，SFC具有比單一分類器更高的性能，其鄰域尺寸設計方法也具有良好效果。從實驗還可看出，全局分類器SVM的性能優(yōu)于局部分類器NN和kNN，所以數據的分布結構還是決定類別劃分的主要因素。在多分類任務上，SVM1r的性能整體略低于SVM11，因為前者的原子性SVM所針對的分類雙方數據量不平衡，影響了分類結果。

4.2.2 時間耗費對比

SFC相對于單一分類器性能的提高是以生成局部分類器為代價的，為觀察這一代價是否值得，圖14記錄了上述實驗中SVM1r、SVM11及SFC的時間耗費。這里的時間耗費包括分類器訓練時間和測試時間。可見，前兩個數據集含有兩個類，SVM1r、SVM11均只建立一個SVM，它們的訓練時間和測試時間大致相同。在后三個含多個類的數據集上，SVM1r的原子性SVM的數目比SVM11少，但前者的單個SVM1r建立于整個數據集之上，所需的時間較多，而后者的單個SVM11建立于數據集中的兩個類，所需的時間少。所以在整體時間上SVM11并不比SVM1r有明顯的增長。SFC的全局分類器是SVM11，它比SVM11多消耗的時間用在信用度評估和局部分類器的生成上。但是這種額外時間耗費并不特別突出。若記：

add%=(SFC′s time-SVM11′s time)/SFC′s time(16)

則上述五個數據集上，add%<15%。在Vote數據集上，add%=8%。這是因為局部分類器只在全局決策信用度低于閾值時才啟動，當所測試數據可被全局分類器正確決策，這一額外耗費不會產生。



從上述分析可見，SFC相對于單一分類器有性能上的顯著提高。當以分類準確率為更高追求環(huán)境下，其為此多付出的耗費完全可接受。

4.3 SFC與其他分類算法比較

該部分實驗比較SSN與其他常見分類算法的性能。參與比較的方法有C4.5^[9]、Machete^[10]、Scythe^[10]、DANN^[11]、Adamenn^[12]。其中，Machete對應了一個迭代的劃分過程，每次迭代選擇某一維進行數據劃分；Scythe是Machete方法的一個推廣和改進版；DANN是一個有一定自適應能力的、基于最近鄰原則的分類算法；Adamenn方法依據數據維的相關性學習數據分布模型，以此生成有自適應能力的分類器。前五個數據集仍從UCI中選用。最后一個數據集是US Postal Codes^[13]。其中的9 298個數據共分10類，覆蓋了0~9這10個數字。這里從某些類中隨機選取若干數據構成五個實驗數據集：a){‘0’， ‘1’} (300)；b){‘1’， ‘2’} (350)； c){‘2’， ‘3’， ‘5’} (200)；d){‘3’， ‘5’， ‘8’} (220)；e){‘1’， ‘3’， ‘5’， ‘7’， ‘8’} (160)。括號中的數字表示從每一類中隨機取出的樣本數目。實驗以30%的數據作為訓練數據，分類錯誤率列于表2中。

從實驗結果可看出，眾方法中Adamenn和SFC處于領先地位。前者在除e)之外的數據集上均給出了最佳結果。SFC的整體性能次之，它在九個數據集中的Waveform，c)和d)上達到最優(yōu)；在Diabetes，a)b)和e)三個數據集上結果次優(yōu)，在另外兩個數據集上結果尚可。Adamenn優(yōu)異表現(xiàn)的原因在于它是通過尋求數據的分布模型獲知了數據維之間的相關性，求出了數據的新坐標表達，并用新坐標完成數據劃分。這一過程同時掌握了數據分布的全面信息，因而對類別劃分有極大幫助，產生正確的劃分；但是Adamenn的計算耗費較大，有六個參數需要設定。相比之下，SFC的計算成本小得多，其性能也較好。因此就性價比而言，SFC高于Adamenn。DANN的表現(xiàn)與SFC接近，但在個別數據集上遜于SFC。這是因為DANN的性能受到數據分布的影響，當數據分布不適應DANN中使用的測度定義時，會降低分類準確率。Scythe和Machete的性能依次降低，這兩種方法本質相同，但前者改進了后者的貪心策略，所以產生稍好的結果。兩個SVM方法的表現(xiàn)與前文實驗類似，其原因也不再多述。kNN完全基于距離定義，欠缺對數據集的適應能力，性能一般。C4.5利用對各個維的劃分逐漸產生分類規(guī)則，它在離散型和類屬型的數據上具有優(yōu)勢，但在連續(xù)性屬性之上性能較差，所以其整體表現(xiàn)不佳。在與常見分類算法的比較中，SFC顯示出良好分類能力，這說明了雙層分類思想的正確性和有效性。

5 結束語

本文提出了雙層分類策略及其實現(xiàn)算法(SFC)。在真實數據集上的實驗表明，作為一種組合形式的分類算法，SFC有計算耗費上的小幅增加，但這一耗費增加換來的是分類性能的提高。在很多具體應用中，計算機硬件的發(fā)展使得計算耗費已經不是主要關注的方面，所以雙層分類策略及其實現(xiàn)算法會有廣泛的應用。雙層分類策略的一個關鍵是設計局部分類器的啟動條件，這一條件在本文中是通過定義分類器決策的信用度評估函數實現(xiàn)的。未來的工作方向是深入研究更有效的局部分類器啟動條件，并思考更多的實現(xiàn)算法。

參考文獻：

［1］CHAPELLE O， WESTON J， SCHOLKOPF B. Cluster kernels for semi-supervised learning[C]//Advances in Neural Information Processing Systems.Cambridge， MA：MIT Press，2002.

［2］SEEGER M.Learning with labeled and unlabeled data[R].Edinburgh:The University of Edinburgh， 2000.

［3］FUKUNAGE K，NARENDRA P M.A branch and bound algorithm for computing k-nearest neighbors[J].IEEE Trans on Computers，1975，C-24(7):750- 753.

［4］VAPNIK V.Statistical learning theory[M]. New York:Wiley，1998.

［5］MURINO V，BICEGO M，ROSSI I A.Statistical classification of raw textile defects[C]//Proc of the 17th International Conference on Pattern Recognition.2004:311-314.

［6］HASTIE T J， TIBSHIRANI R J. Classification by pairwise coupling[J].Advances in Neural Information Processing Systems，1998，26（2）:507-513.

［7］DIJKSTRA E W. A note on two problems in connexion with graphs[J].Numerische Mathematik，1959，1(1):269-271.

［8］UC irvine machine learning repository[EB/OL].(2008-07-23).http://archive.ics.uci.edu/ml.

［9］QUINLAN J R.C4.5:programs for machine learning[M].San Francisco:Morgan Kaufmann Publishers，1993.

［10］FRIEDMAN J H.Flexible metric nearest neighbor classification[R].[S.l.]:Department of Statistics， Stanford University，1994.

［11］HASTIE T，TIBSHIRANI R.Discriminant adaptive nearest neighbor classification[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1996，18(6):607-615.

［12］DOMENICONI C，PENG J，GUNOPULOS D.An adaptive metric machine for pattern classification[M].Advances in Neural Information Processing Systems.[S.l.]:MIT Press，2000:458-464.

［13］LECUN Y.Comparison of learning algorithms for handwritten digit recognition[C]//Proc of International Conference on Artificial Neural Networks.1995:53-60.