改進(jìn)PM-MD的分類器集成①

吳立凡,何振峰

(福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,福州 350116)

Hub[1]指一些經(jīng)常出現(xiàn)在其他數(shù)據(jù)點(diǎn)的最相鄰列表中的數(shù)據(jù)點(diǎn),它是隨著維度的增加而出現(xiàn)的,這種現(xiàn)象一般稱為Hubness 現(xiàn)象[2].Hubness 是高維空間數(shù)據(jù)分布的一個固有性質(zhì),對高維數(shù)據(jù)分析產(chǎn)生了顯著的影響[2],受影響的方法和任務(wù)包括貝葉斯建模,近鄰預(yù)測和搜索,神經(jīng)網(wǎng)絡(luò)等等[2].比如,Hubness 的出現(xiàn)會直接影響到KNN 分類的準(zhǔn)確性[3],這是因為：Hub 在相應(yīng)的距離空間中傳播其編碼信息過于廣泛,而非Hub 攜帶的信息基本上丟失,導(dǎo)致這些距離空間不能很好地反映類信息[4].

為了減少Hubness 的負(fù)面影響,有兩類(共五種)降Hubness 的分類器策略應(yīng)用于數(shù)據(jù)轉(zhuǎn)換以提高KNN 分類精度：其中第一類策略(二次距離策略)將距離矩陣換算到二次距離(NICDM[1]、MP[1]),第二類策略(線性換算策略)直接應(yīng)用于數(shù)據(jù)向量(CENT[3]、MINMAX[5]、ZSCORE[5]).第一類策略中：NICDM 是將Hubness 問題與使最近鄰關(guān)系對稱的方法聯(lián)系起來,它需要得到每個數(shù)據(jù)點(diǎn)的局部鄰域,因此并不適用于非常大的數(shù)據(jù)庫；MP 是一種無監(jiān)督的將任意的距離函數(shù)轉(zhuǎn)換成概率相似性(距離)測量的方法,適用于非常大的數(shù)據(jù)庫,并且支持多個距離空間的簡單組合.實驗表明NICDM 和MP 顯著的減少了Hubness,提高了KNN分類精度,還增強(qiáng)了近鄰的穩(wěn)定性[1,6]；但是,NICDM和MP 適用于中心性和內(nèi)在維度較高的數(shù)據(jù)集,否則性能不穩(wěn)定[1].第二類策略中：CENT 是將特征空間的原點(diǎn)移到數(shù)據(jù)中心,可用于內(nèi)積相似空間以減少Hubness(其中每個樣本和中心的相似性在CENT 后等于零),但它并不是適用于所有數(shù)據(jù)集,它成功的必要條件是Hub 與數(shù)據(jù)中心點(diǎn)有著高相似度[1]；而MINMAX和ZSCORE 則是應(yīng)用很廣泛的數(shù)據(jù)標(biāo)準(zhǔn)化方法,MINMAX 是對原始數(shù)據(jù)進(jìn)行線性變換,適用于原始數(shù)據(jù)的取值范圍已經(jīng)確定的情況；ZSCORE 基于原始數(shù)據(jù)的均值和標(biāo)準(zhǔn)差進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化,適用于最大值和最小值未知的情況,或有超出取值范圍的離群數(shù)據(jù)的情況.

在本文中對這兩類策略進(jìn)行多分類器集成,由于不同的分類器提供了關(guān)于被分類的對象的補(bǔ)充信息,因此多分類器系統(tǒng)可以獲得比整體中任何單一的分類器更好的分類精度.本文中的集成采用了一種計算特征空間分類器競爭力的名為PM-MD[7]的方法.在該方法中,首先使用KNN 的驗證對象來確定分類對象x點(diǎn)的決策表,決策表提供了被識別對象屬于指定類的機(jī)會.在概率模型中,決策表的自然概念是基于x點(diǎn)上的類的后驗概率.接下來,將決策表與分類器所產(chǎn)生的響應(yīng)(支持向量或判別函數(shù)的值)進(jìn)行比較,并根據(jù)相似性規(guī)則[8]計算分類器的分類競爭力：對決策表的響應(yīng)越接近,分類器的競爭力就越強(qiáng)[9,10].

本文的第1 部分介紹兩類降Hubness 策略(共五種),第2 部分介紹PM-MD 集成的方法并對第1 部分的策略進(jìn)行集成,第3 部分介紹對PM-MD 集成進(jìn)行改進(jìn)的部分,第4 部分對實驗結(jié)果進(jìn)行分析.

(1)兩類降Hubness 策略

1)二次距離策略

① NICDM

NICDM (Non-Iterative Contextual Dissimilarity Measure)用K近鄰的平均距離來重新?lián)Q算距離,相比于利用K近鄰距離來重新?lián)Q算距離,這將返回更穩(wěn)定的換算數(shù)據(jù).NICDM 通過式(1)得到二次距離：

其中,μx表 示x最近鄰的平均距離,μy同理.NICDM 傾向于通過換算的數(shù)據(jù)點(diǎn)x和y的局部距離統(tǒng)計數(shù)據(jù)使得近鄰關(guān)系更加對稱[6].

② MP

相互接近(Mutual Proximity)通過將兩個對象之間的距離轉(zhuǎn)換為一個相互接近的距離來重新解釋原始的距離空間,使得兩個共享最近鄰的對象之間的距離就更緊密了,而不共享最近鄰的對象則相互排斥.在n個對象集合中,計算一個給定距離dx,y可以歸結(jié)為簡單地計算出j與x和y之間大于dx,y的距離[1]：

式(2)中,MP 是計算點(diǎn)x和y的相似度,通過計算1-MP將相似度變成了二次距離[6].

2)線性換算策略

① CENT

定心(Centering)將特征空間的原點(diǎn)轉(zhuǎn)移到數(shù)據(jù)中心它是一種去除數(shù)據(jù)中觀測偏差的經(jīng)典方法,但直到最近才被確定為減少Hubness 的方法.

式(3)中simCENT(x;q)是計算相似度,需要通過計算1-simCENT(x;q)將相似度變成了距離.

② MINMAX

在MINMAX 算法里,原始數(shù)據(jù)是線性變化的.MINMAX 使用式(4)將v值進(jìn)行映射到v′：

將xmin和xmax定義為樣本中變量的最小值和最大值,MINMAX 將在[xmin,xmax]區(qū)間的訓(xùn)練樣本映射到[0,1].

③ ZSCORE

ZSCORE 通過式(5)將v值進(jìn)行映射到v′：

其中,和 σx分別為訓(xùn)練集中變量值的均值和標(biāo)準(zhǔn)差.在映射之后,平均值將為0,標(biāo)準(zhǔn)差將為1.

(2)集成方法

本文采用的PM-MD 是一種全新的計算特征空間中分類器能力的集成方法,被集成的方法為第一章中提到的5 種策略：NICDM、MP、MINMAX、ZSCORE、CENT.PM-MD 方法是由兩個方法結(jié)合起來：PM 方法(Potential function Method)和MD 方法(Max-max Distance).PM-MD 的特色在于對驗證集的不同使用,在PM-MD 中驗證集是用來評估測試點(diǎn)的類支持向量的,并且在PM 中使用K近鄰來確定測試點(diǎn)的決策表,最后在MD 中由類支持向量與決策表的相似性決定分類器的競爭力[7].

集成流程的圖示如圖1,本文采用的是5 種降Hubness 策略和KNN 分類,也可以采用其他策略和分類方法.

1)類支持向量

分類器ψl相當(dāng)于一個從特征度量空間x?Rdim到一個類標(biāo)簽集合M={1,2,···,m}的函數(shù).對于每個數(shù)據(jù)點(diǎn)x,分類器 ψl經(jīng)過該分類器的數(shù)據(jù)轉(zhuǎn)換后通過KNN找到x的K近鄰從而生成相應(yīng)的類支持向量：

2)根據(jù)PM 計算決策表

決策表 ω (x)=[ω1(x),ω2(x),···,ωM(x)]提供了數(shù)據(jù)點(diǎn)x屬于指定類的機(jī)會,其中

用PM 方法通過K近鄰計算數(shù)據(jù)點(diǎn)x的決策表的步驟如下：

① 計算一個非負(fù)勢函數(shù)H(x,xk)[11],其值隨著x和xk之間距離增大而快速減少(xk為來自驗證集的數(shù)據(jù)對象)：

② 根據(jù)上一步得到的勢函數(shù)計算決策表 ωj(x),它是x屬于第j類的機(jī)會的衡量：

其中,NK(x)為驗證集V中的數(shù)據(jù)點(diǎn)x的K近鄰集合,xk為來自驗證集的數(shù)據(jù)對象,jk為相應(yīng)的類標(biāo)簽.

3)根據(jù)MD 計算分類器競爭力

分類器競爭力c(ψl|x)用來衡量分類器ψl在數(shù)據(jù)點(diǎn)x的分類能力,它隨著支持向量dl(x)和 決策表ω (x)的距離dist[ω(x),dl(x)]的增大而減少.

圖1 結(jié)合降Hubness 過程的分類器集成框架

根據(jù)MD 方法計算分類器競爭力步驟如下：

① 令j為分類器 ψl在數(shù)據(jù)點(diǎn)x產(chǎn)生的類支持向量的最優(yōu)值的類編號,即dl j(x)=maxk∈M(dlk(x))；同理,令i為決策表ω (x)在數(shù)據(jù)點(diǎn)x產(chǎn)生的最優(yōu)值的類編號.

則支持向量dl(x)和 決策表ω (x)的距離定義如下：

假設(shè)類支持向量為dl(x)=[0.1,0.4,0.2,0.3],決策表為ω(x)=[0.2,0.1,0.2,0.5] ,則dl j(x)=0.4,j=2 ,ωi(x)=0.5,i=4.所以距離計算如下：

② 根據(jù)上一步得到的距離計算競爭力c(ψl|x)：

4)組合投票以及最后分類精度的計算

對于測試數(shù)據(jù)點(diǎn)x,其最后的分類結(jié)果 ψ (x)是由分類器組合中的每個分類器產(chǎn)生的類支持向量(式(6))結(jié)合其對應(yīng)的分類器競爭力(式(11))組合投票得出來的：

其中,T為分類器的個數(shù).

最后的分類精度是對測試集V中的每個測試數(shù)據(jù)點(diǎn)進(jìn)行分類,然后計算正確分類的數(shù)據(jù)點(diǎn)數(shù)占總點(diǎn)數(shù)的比例：

其中,m(x)為x的真實類標(biāo)簽,m(x)∈M.

將所有屬于測試集V的數(shù)據(jù)點(diǎn)的result(x)相加后除以測試集V的數(shù)據(jù)點(diǎn)總個數(shù)num便可得到最終的分類精度Result.

(3)改進(jìn)PM-MD

原PM-MD 中式(7)采用高斯勢函數(shù)將歐氏距離||x-xk||映射到(0,1)之間,但當(dāng)數(shù)據(jù)集的內(nèi)在維度較高時不同樣本距離經(jīng)過高斯勢函數(shù)轉(zhuǎn)換后會非常地趨于0,這會弱化距離所帶來的不同類的區(qū)別.如圖2,圖2(d)MINMAX 的距離均值較大,大部分樣本距離采用高斯勢函數(shù)會得到趨于0 的結(jié)果,這樣會使得MINMAX 分類效果變?nèi)?從而影響集成效果；這個情況在文獻(xiàn)[7]的表3所給實驗結(jié)果中也可以體現(xiàn)出來,當(dāng)數(shù)據(jù)集的內(nèi)在維度較高時(如Ionosphere 和Spam等)PM-MD 的分類結(jié)果往往不是很好.

根據(jù)PM-MD 不適用于高維數(shù)據(jù)集的情況下,本文提出將直接采用歐氏距離計算決策表.

將PM 進(jìn)行改進(jìn)：

所對應(yīng)的決策表公式：

(4)實驗結(jié)果

實驗中共選用12 個UCI 數(shù)據(jù)集[12]進(jìn)行測試.經(jīng)過10 輪十折交叉驗證,取100 個結(jié)果的準(zhǔn)確率均值.12 個UCI 數(shù)據(jù)集測試結(jié)果(表1)表明：

1)單一分類器并不適用于所有情況(比如NICDM在數(shù)據(jù)集seeds 效果最優(yōu)但在數(shù)據(jù)集mammographic_masses 效果很差),PM-MD 集成中和分類器的優(yōu)劣,在一定程度上可以獲得比整體中任何單一的分類器更好的分類精度.

圖2 數(shù)據(jù)集Dermatology 在各個分類器中得到的距離箱線圖

2)對于一些存在較大異常值的數(shù)據(jù)集(比如Pima_indians_diabetes),PM-MD 集成之后比起單一分類器有著更優(yōu)的精度,由此可見對于存在大量較大異常值的數(shù)據(jù)集,PM-MD 集成獲得了比任何單一分類器要更高的分類精度.

3)對于一些不僅存在較大異常值還存在較小異常值的數(shù)據(jù)集(比如wine),集成后的分類效果明顯優(yōu)于

大部分單一分類器分類效果,也明顯優(yōu)于原始分類結(jié)果.

4)改進(jìn)后的PM-MD 在一定程度上具有比PMMD 更精確的分類效果(比如數(shù)據(jù)集Liver),由此可見改進(jìn)后的PM-MD 確實提升了PM-MD 的分類效果.

5)NICDM、CNET、MINMAX、ZSCORE 的復(fù)雜度都為O (n2),MP 的復(fù)雜度為O (n3),故PM-MD 的復(fù)雜度為O (n3).

表1 實驗結(jié)果

(5)結(jié)論與展望

Hubness 現(xiàn)象是維度災(zāi)難的一個方面,hub 的出現(xiàn)嚴(yán)重降低了分類器的性能.本文結(jié)合了五種降Hubness 策略以減少Hubness 的影響,由于每種策略所適用范圍的差異,為此采用了PM-MD 方式進(jìn)行集成以擴(kuò)大適用范圍.并針對PM-MD 不適用于高維數(shù)據(jù)集的問題提出改進(jìn),直接將歐氏距離直接用于計算決策表.實驗結(jié)果表明,PM-MD 獲得了比單一分類器要高的分類精度的同時擴(kuò)大了適用范圍,改進(jìn)后的PMMD 獲得了更高的分類精度.目前研究主要關(guān)注于噪聲較小的高維數(shù)據(jù)分類,未來我們將致力于通過有效分類器集成以解決噪聲較大的數(shù)據(jù)集的分類問題.

1 Schnitzer D,Flexer A,Schedl M,et al.Local and global scaling reduce hubs in space.Journal of Machine Learning Research,2012,13(1)：2871-2902.

2 Zhai TT,He ZF.Instance selection for time series classification based on immune binary particle swarm optimization.Knowledge-Based Systems,2013,49：106-115.[doi：10.1016/j.knosys.2013.04.021]