改進PM-MD的分類器集成①

吳立凡,何振峰

(福州大學 數學與計算機科學學院,福州 350116)

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

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

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

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

(1)兩類降Hubness 策略

1)二次距離策略

① NICDM

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

其中,μx表 示x最近鄰的平均距離,μy同理.NICDM 傾向于通過換算的數據點x和y的局部距離統計數據使得近鄰關系更加對稱[6].

② MP

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

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

2)線性換算策略

① CENT

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

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

② MINMAX

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

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

③ ZSCORE

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

其中,和 σx分別為訓練集中變量值的均值和標準差.在映射之后,平均值將為0,標準差將為1.

(2)集成方法

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

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

1)類支持向量

分類器ψl相當于一個從特征度量空間x?Rdim到一個類標簽集合M={1,2,···,m}的函數.對于每個數據點x,分類器 ψl經過該分類器的數據轉換后通過KNN找到x的K近鄰從而生成相應的類支持向量：

2)根據PM 計算決策表

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

用PM 方法通過K近鄰計算數據點x的決策表的步驟如下：

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

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

其中,NK(x)為驗證集V中的數據點x的K近鄰集合,xk為來自驗證集的數據對象,jk為相應的類標簽.

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

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

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

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

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

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

假設類支持向量為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.所以距離計算如下：

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

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

對于測試數據點x,其最后的分類結果 ψ (x)是由分類器組合中的每個分類器產生的類支持向量(式(6))結合其對應的分類器競爭力(式(11))組合投票得出來的：

其中,T為分類器的個數.

最后的分類精度是對測試集V中的每個測試數據點進行分類,然后計算正確分類的數據點數占總點數的比例：

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

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

(3)改進PM-MD

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

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

將PM 進行改進：

所對應的決策表公式：

(4)實驗結果

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

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

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

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

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

大部分單一分類器分類效果,也明顯優于原始分類結果.

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

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

表1 實驗結果

(5)結論與展望

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

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]