吳立凡,何振峰

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(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ù)分布的一個(gè)固有性質(zhì),對(duì)高維數(shù)據(jù)分析產(chǎn)生了顯著的影響[2],受影響的方法和任務(wù)包括貝葉斯建模,近鄰預(yù)測(cè)和搜索,神經(jīng)網(wǎng)絡(luò)等等[2].比如,Hubness 的出現(xiàn)會(huì)直接影響到KNN 分類的準(zhǔn)確性[3],這是因?yàn)椋篐ub 在相應(yīng)的距離空間中傳播其編碼信息過(guò)于廣泛,而非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 問(wèn)題與使最近鄰關(guān)系對(duì)稱的方法聯(lián)系起來(lái),它需要得到每個(gè)數(shù)據(jù)點(diǎn)的局部鄰域,因此并不適用于非常大的數(shù)據(jù)庫(kù)；MP 是一種無(wú)監(jiān)督的將任意的距離函數(shù)轉(zhuǎn)換成概率相似性(距離)測(cè)量的方法,適用于非常大的數(shù)據(jù)庫(kù),并且支持多個(gè)距離空間的簡(jiǎn)單組合.實(shí)驗(yàn)表明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(其中每個(gè)樣本和中心的相似性在CENT 后等于零),但它并不是適用于所有數(shù)據(jù)集,它成功的必要條件是Hub 與數(shù)據(jù)中心點(diǎn)有著高相似度[1]；而MINMAX和ZSCORE 則是應(yīng)用很廣泛的數(shù)據(jù)標(biāo)準(zhǔn)化方法,MINMAX 是對(duì)原始數(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ù)的情況.

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

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

(1)兩類降Hubness 策略

1)二次距離策略

① NICDM

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

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

② MP

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

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

2)線性換算策略

① CENT

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

式(3)中simCENT(x;q)是計(jì)算相似度,需要通過(guò)計(jì)算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 通過(guò)式(5)將v值進(jìn)行映射到v′：

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

(2)集成方法

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

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

1)類支持向量

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

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

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

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

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

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

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

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

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

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

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

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

則支持向量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ì)算如下：

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

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

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

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

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

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

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

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

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

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

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

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

(4)實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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]