基于信息論方法的分類數(shù)據(jù)相似性度量

鄭碧如，吳廣潮

(華南理工大學(xué)數(shù)學(xué)學(xué)院，廣東 廣州 510641)

0 引 言

在機(jī)器學(xué)習(xí)算法中，兩實(shí)例間距離或者相似性度量扮演著重要的角色，廣泛地應(yīng)用于分類、聚類和奇異值檢測(cè)和特征學(xué)習(xí)[1-2]等算法中。常用的距離度量方法，如閔可夫斯基距離、馬氏距離等，通常只適用于數(shù)值型數(shù)據(jù)。而對(duì)于分類數(shù)據(jù)，其屬性為分類屬性(如顏色、形狀等)，其值具有離散、無(wú)序和取值有限的特點(diǎn)，因此，不能直接對(duì)2個(gè)不同屬性值進(jìn)行比較，通常是利用數(shù)據(jù)驅(qū)動(dòng)的方法，通過(guò)數(shù)據(jù)的分布情況等信息來(lái)對(duì)其進(jìn)行度量。

對(duì)已提出的分類數(shù)據(jù)的度量方法，可分為不相似性和相似性這2大類。不相似性的方法包括Xie等人[3]提出的方法將分類數(shù)據(jù)映射到實(shí)數(shù)域，并以此度量不相似性，通過(guò)基于最近鄰分類錯(cuò)誤率最小化來(lái)更新值；Cheng等人[4]使用自適應(yīng)相異矩陣評(píng)估分類屬性值之間的差異，用梯度下降法優(yōu)化誤差；Le等人[5]則考慮給定2個(gè)值與其他屬性的條件概率分布差異的組合進(jìn)行度量，但隨數(shù)據(jù)維度的增大，其復(fù)雜度也大大增加。Alamuri等人在文獻(xiàn)[6]中介紹了對(duì)分類數(shù)據(jù)的距離或相似性度量的方法，而B(niǎo)oriah等人在文獻(xiàn)[2]則側(cè)重介紹了數(shù)據(jù)驅(qū)動(dòng)的分類數(shù)據(jù)相似性度量方法，并根據(jù)方法所基于的理論對(duì)其做如下分類：基于頻數(shù)的方法有OF(Occurrence Frequency)，IOF(Inverse Occurrence Frequency)，其中IOF與信息檢索的逆文檔頻率的概念相關(guān)[7]，Wang等人[8]將其應(yīng)用到中文文本分析?；诟怕实姆椒ㄓ蠫oodall，Smirnov和Anderberg，其中Goodall提出的度量使得不頻繁屬性值對(duì)整體相似性的貢獻(xiàn)大于頻繁屬性值；而Smirnov不僅考慮給定屬性值的概率，還考慮同屬性其他取值的概率分布?；谛畔⒄摰姆椒ㄓ蠦urnaby[9]、Lin[10]、Lin1[2]，其中Burnaby提出的方法使得在值不匹配時(shí)，對(duì)不頻繁的屬性值賦予較低的相似性；Lin定義2條數(shù)據(jù)的相似性是其共同的信息與總信息的比率，對(duì)頻繁值在匹配時(shí)賦予更高的權(quán)重，對(duì)不頻繁的值在不匹配時(shí)賦予更低的權(quán)重；Lin1是Lin相似性的修正方法，其不僅考慮給定屬性值的概率，還考慮同屬性的概率處于兩者間的值的概率。除上面介紹的方法外，還有簡(jiǎn)單易懂的度量方法：Overlap[11]，其定義2屬性值相同時(shí)的相似性為1，否則為0；Eskin等人[12]提出的度量是關(guān)于屬性取值個(gè)數(shù)的遞增函數(shù)，取值越多的屬性，被賦予更高的權(quán)重，但會(huì)出現(xiàn)同屬性不同值具有同樣的相似性。

上述相似性度量方法可應(yīng)用于分類、聚類算法中，但是在有監(jiān)督學(xué)習(xí)任務(wù)中，其未利用到數(shù)據(jù)集的類信息?？紤]到類信息對(duì)分類有至關(guān)重要的作用，本文提出Lin方法改進(jìn)版本MLin(Modified Lin)，該方法把給定屬性值的類概率與信息論方法結(jié)合，構(gòu)造新相似性度量函數(shù)，對(duì)分類數(shù)據(jù)進(jìn)行相似性度量。最后，在UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的多個(gè)有類標(biāo)簽的分類數(shù)據(jù)集上，利用k-NN[13]算法與多個(gè)相似性度量方法結(jié)合進(jìn)行實(shí)驗(yàn)比較，驗(yàn)證MLin的合理性和效用性。

1 Lin相似性度量

Lin[10]提出的分類數(shù)據(jù)度量方法是基于信息論的，包括了對(duì)有序和無(wú)序數(shù)據(jù)進(jìn)行相似性度量。本文主要介紹對(duì)無(wú)序?qū)傩缘亩攘糠椒?，Lin認(rèn)為x和y這2個(gè)實(shí)例的相似性與它們的共同信息和總描述信息有關(guān)。顯然，若2實(shí)例的共同性越大，相似性越大；差異性越大，相似性越小。

對(duì)于2個(gè)實(shí)例x=(X1,X2,…,Xd)和y=(Y1,Y2,…,Yd)，Lin對(duì)其相似性的定義為：

(1)

(2)

(3)

(4)

2 Lin相似性度量的改進(jìn)

2.1 MLin相似性度量

從上一章可知Lin相似性只利用屬性值的概率，結(jié)合信息論方法構(gòu)造相似性度量，且2實(shí)例的相似性范圍為[0,1]。在處理分類問(wèn)題時(shí)，Lin度量沒(méi)有利用到類標(biāo)簽信息，而類信息對(duì)分類起著至關(guān)重要的作用?？紤]到對(duì)帶標(biāo)簽數(shù)據(jù)的相似性度量除利用屬性值出現(xiàn)的概率外，還可以利用屬性值在各個(gè)類上的分布信息，為此，本文將在Lin的理論框架上進(jìn)行延伸——利用屬性值的類條件概率結(jié)合信息論方法構(gòu)造相似性度量，并對(duì)該修正方法命名為MLin。

假設(shè)分類數(shù)據(jù)包含C個(gè)類別，將Lin相似性中的概率改為類條件概率，即對(duì)式(2)～式(4)作如下修正得到式(5)～式(7)：

(5)

(6)

(7)

2.2 MLin相似性算法描述與分析

對(duì)于MLin相似性，最核心的部分是求出各屬性值的類條件概率，再進(jìn)一步求出屬性值間的相似性。在算法1中，先假設(shè)屬性Ak有nk個(gè)取值，再以維度為d，包含C個(gè)類別的數(shù)據(jù)集D作為輸入，求出所有屬性值的類條件概率列表M,相似度列表S。M的第k個(gè)元素Mk是關(guān)于Ak的條件概率矩陣，其規(guī)模為nk×C；S的第k個(gè)元素Sk是關(guān)于屬性Ak的相似性矩陣，其規(guī)模為nk×nk，并且是對(duì)稱矩陣。

為了方便算法描述，先對(duì)數(shù)據(jù)集進(jìn)行數(shù)據(jù)化預(yù)處理，把屬性Ak的nk個(gè)取值按0到nk-1進(jìn)行標(biāo)記。例如對(duì)顏色(紅，黃，藍(lán))進(jìn)行如{紅：0，黃：1，藍(lán)：2}的形式數(shù)字化處理。在此，假設(shè)數(shù)據(jù)集D已經(jīng)過(guò)數(shù)值化預(yù)處理。

算法1預(yù)處理信息提取算法

輸入：數(shù)據(jù)集D={(xi,ci),i=1,2,…,N}，維度d，類別數(shù)C

輸出：所有屬性的類條件概率列表M,屬性相似性列表S

過(guò)程：

1:初始化類條件概率列表M,屬性相似性列表S

2:for k=1,2,…，d do

3:初始化類條件概率矩陣Mk,屬性相似性矩陣Sk

4:for i=0,…,nk-1 do

5:for c=1,…,C do

7:end for

8:for j=i,…,nk-1 do

9:Sk[i,j]=Sk(i,j)

10:Sk[j,i]=Sk[i,j]

11:end for

12:end for

13:將Mk,Sk分別加入M,S

14:end for

將算法1的輸出類條件概率列表M,屬性相似性列表S作為算法2的輸入，即可求出2目標(biāo)實(shí)例x,y的相似性。

算法2MLin相似性度量算法

輸入：x=(X1,X2,…,Xd)和y=(Y1,Y2,…,Yd)，類條件概率列表M,屬性相似性列表S

輸出：x和y的相似性S(x,y)

過(guò)程：

1:初始化相似度S(x,y)=0,總信息Info=0

2:for k=1,2,…，d do

3:S(x,y)=S(x,y)+Sk[Xk,Yk]

4:for c=1,…,C do

5:Info=Info+log (Mk[Xk,c-1]×Mk[Yk,c-1])

6:end for

7:end for

8:S(x,y)=S(x,y)/Info

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)集描述

在UCI數(shù)據(jù)庫(kù)中選取6個(gè)純分類屬性的數(shù)據(jù)集進(jìn)行分類，在表1中，給出了各個(gè)數(shù)據(jù)集的名稱、數(shù)據(jù)集包含的實(shí)例數(shù)N、維度d、類別數(shù)C以及各分類屬性取值的個(gè)數(shù)nk范圍。

在圖1中，圖例對(duì)圖中的折線進(jìn)行了說(shuō)明，例如c=1的折線上的各個(gè)點(diǎn)為其屬性在c=1下的條件概率，各個(gè)點(diǎn)的橫坐標(biāo)是其屬性值，縱坐標(biāo)是其所對(duì)應(yīng)的條件概率值。從圖1可看出各個(gè)數(shù)據(jù)集在各個(gè)類別上屬性值的概率分布情況，在Hayes-roth子圖中出現(xiàn)3條折線多處重合；在Balance-scale中c=2的折線波動(dòng)并不大，即c=2的數(shù)據(jù)對(duì)屬性值并無(wú)明顯的偏好；Tic-Tac-Toe和Mushroom都是二分類數(shù)據(jù)集，其對(duì)應(yīng)子圖的折線波動(dòng)都比較明顯；在Car Evaluation上，其在c=1、2時(shí)這2條折線在前半部分幾乎重合了，c=3、4時(shí)也在前半部分出現(xiàn)重合；在Nursery的c=1、3、4上，3條折線的區(qū)分度都不大，而c=2的折線波動(dòng)大，具有較高的區(qū)分度。由此可見(jiàn)，對(duì)于二分類數(shù)據(jù)，一般不會(huì)出現(xiàn)折線平行或多處點(diǎn)重合的情況。

表1 數(shù)據(jù)集情況

數(shù)據(jù)集NdCnk范圍Hayes-roth132433～4Balance-scale625435Tic-Tac-Toe958923Car Evaluation1728643～4Mushroom81242022～12Nursery12960842～5

圖1 各屬性值的類條件概率分布圖

3.2 實(shí)驗(yàn)結(jié)果與分析

把表1中的數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集，將MLin、Lin、Lin1、Burnaby、IOF、OF、Overlap和Eskin相似性度量方法分別與k-NN[13]結(jié)合，通過(guò)在訓(xùn)練集中尋找k個(gè)與測(cè)試集中的目標(biāo)實(shí)例相似度最大的k個(gè)實(shí)例，并由其類標(biāo)簽進(jìn)行投票，來(lái)預(yù)測(cè)目標(biāo)實(shí)例所屬的類別。由于ID3決策樹(shù)算法[14]是對(duì)離散數(shù)據(jù)進(jìn)行分類的經(jīng)典方法，因此實(shí)驗(yàn)中應(yīng)用ID3對(duì)數(shù)據(jù)集進(jìn)行分類并與相似度結(jié)合k-NN的分類結(jié)果作比較。在表2中，給出了各種方法結(jié)合k-NN(k=3)在各數(shù)據(jù)集上進(jìn)行十折交叉驗(yàn)證的平均錯(cuò)誤率。

表2 十折交叉驗(yàn)證的平均錯(cuò)誤率(k=3) 單位：%

在表2中，加粗的數(shù)值為所在行的最小值，即在某一數(shù)據(jù)集上的最小分類錯(cuò)誤率。從中可看出，ID3在這幾個(gè)數(shù)據(jù)集中的判錯(cuò)率都比較低，分類效率高，尤其在數(shù)據(jù)點(diǎn)較小的Hayes-roth上的平均分類錯(cuò)誤率達(dá)到最低，體現(xiàn)了其對(duì)小數(shù)據(jù)集具有較好的魯棒性，在該數(shù)據(jù)集上，MLin的表現(xiàn)比ID3略差。觀察其余多個(gè)數(shù)據(jù)集的分類情況，除了Tic-Tac-Toe在基于IOF的k-NN上的分類效果最好外，其余的4個(gè)數(shù)據(jù)集均在基于MLin的k-NN上的分類錯(cuò)誤率最低。尤其在Mushroom上，MLin方法的錯(cuò)誤率僅有0.002；并且在Balance-scale上，MLin的準(zhǔn)確率比Lin和Lin1的均高出近20%，比ID3高出了近10%的準(zhǔn)確率。

圖2 k-NN(k=3)十折交叉驗(yàn)證錯(cuò)誤率折線圖

為了對(duì)ID3、MLin、Lin和Lin1的分類結(jié)果進(jìn)行更深入的比較，在k=3時(shí)，對(duì)其十折交叉驗(yàn)證的錯(cuò)誤率畫(huà)折線圖進(jìn)行可視化，見(jiàn)圖2。圖中包含6個(gè)子圖，分別是6個(gè)數(shù)據(jù)集的十折交叉驗(yàn)證錯(cuò)誤率折線圖，其中橫坐標(biāo)為“avg.”的點(diǎn)的縱坐標(biāo)值為十折交叉驗(yàn)證的平均錯(cuò)誤率。顯然可看出Lin1所對(duì)應(yīng)的折線基本處于圖的上方，錯(cuò)誤率居高，而MLin所在折線幾乎都在圖的下方，錯(cuò)誤率較低。在Hayes-roth的子圖中，ID3所在折線明顯地處在MLin的下方，這與表2的結(jié)論相對(duì)應(yīng)。而在Balance-scale、Car Evaluation和Mushroom這3個(gè)子圖中，MLin的表現(xiàn)明顯優(yōu)于其他方法。可見(jiàn)，MLin在各數(shù)據(jù)集的分類具有較高的準(zhǔn)確率，ID3的表現(xiàn)處于MLin和Lin之間。綜合表2和圖2來(lái)看，Lin1的綜合表現(xiàn)比較差，而MLin的表現(xiàn)都優(yōu)于Lin，這也驗(yàn)證了MLin在有監(jiān)督學(xué)習(xí)分類問(wèn)題上的度量具有合理性和效用性。

為了比較在不同k值，k-NN方法在各數(shù)據(jù)集上的分類效果，將數(shù)據(jù)集分割出30%的數(shù)據(jù)作為測(cè)試集進(jìn)行測(cè)試。在圖3中給出了MLin、Lin、Lin1方法在不同k值下k-NN在各數(shù)據(jù)的測(cè)試集上的分類錯(cuò)誤率折線圖?？v觀圖3中的6個(gè)子圖，MLin的錯(cuò)誤率的折線幾乎都處在圖的最下方，而Lin1的分類效果則比較一般。同時(shí)可發(fā)現(xiàn)，在小數(shù)據(jù)集上(Hayes-roth，Balance-scale)，MLin的表現(xiàn)比較一般，隨著數(shù)據(jù)集規(guī)模的增大，MLin方法下的錯(cuò)誤率均較低，如在Nursery數(shù)據(jù)集上，MLin方法的錯(cuò)誤率低于0.05，且明顯低于其他方法的錯(cuò)誤率。

作為數(shù)據(jù)驅(qū)動(dòng)的相似性度量方法，并不適合處理小規(guī)模數(shù)據(jù)，若數(shù)據(jù)集太小，會(huì)導(dǎo)致估計(jì)的條件概率與實(shí)際分布的條件概率有較大的誤差。再?gòu)臅r(shí)間代價(jià)上看，MLin在計(jì)算實(shí)例的相似度的復(fù)雜度比Lin和Lin1相似度方法的復(fù)雜度大，再結(jié)合k-NN進(jìn)行分類驗(yàn)證，自然會(huì)比ID3花費(fèi)更多的時(shí)間。

4 結(jié)束語(yǔ)

本文提出了Lin相似性的改進(jìn)方法MLin，應(yīng)用于分類數(shù)據(jù)的分類問(wèn)題。MLin是基于信息論和屬性值的類條件概率的，將數(shù)據(jù)的類信息、數(shù)據(jù)分布考慮入內(nèi)，屬于數(shù)據(jù)驅(qū)動(dòng)的相似性度量方法。本文中，利用k-NN結(jié)合相似性度量方法，對(duì)UCI的6個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果顯示MLin的分類錯(cuò)誤率均較低，但在小規(guī)模的數(shù)據(jù)集上的效果比較差，并且也證實(shí)了數(shù)據(jù)驅(qū)動(dòng)方法在小數(shù)據(jù)集上的表現(xiàn)都會(huì)比較差，由此可見(jiàn)MLin更適合應(yīng)用于數(shù)據(jù)規(guī)模較大的數(shù)據(jù)中。未來(lái)可對(duì)其做進(jìn)一步的擴(kuò)展和應(yīng)用，對(duì)混合數(shù)據(jù)進(jìn)行相似度的度量[15-16]和對(duì)文本進(jìn)行分析[17-18]。

參考文獻(xiàn)：

[1] Lin Liang, Wang Guangrun, Zuo Wangmeng, et al. Cross-domain visual matching via generalized similarity measure and feature learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017,39(6):1089-1102.

[2] Boriah S, Chandola V, Kumar V. Similarity measures for categorical data: A comparative evaluation[C]// Proceedings of 2008 SIAM International Conference on Data Mining. 2008:243-254.

[3] Xie Jierui, Szymanski B, Zaki M. Learning dissimilarities for categorical symbols[C]// The 4th Workshop on Feature Selection in Data Mining. 2010:97-106.

[4] Cheng Victor, Li Chun-hung, Kwok J T, et al. Dissimilarity learning for nominal data[J]. Pattern Recognition, 2004,37(7):1471-1477.

[5] Le Siquang, Ho Tubao. An association-based dissimilarity measure for categorical data[J]. Pattern Recognition Letters, 2005,26(16):2549-2557.

[6] Alamuri M, Surampudi B R, Negi A. A survey of distance/similarity measures for categorical data[C]// 2014 IEEE International Joint Conference on Neural Networks. 2014:1907-1914.

[7] Sparck J K. A statistical interpretation of term specificity and its application in retrieval[J]. Journal of Document, 1972,28(1):11-21.

[8] Wang Yue, Ge Jidong, Zhou Yemao, et al. Topic model based text similarity measure for Chinese judgement document[C]// International Conference of Pioneering Computer Scientists, Engineers and Educators. 2017:42-54.

[9] Burnaby T P. On a method for character weighting a similarity coefficient, employing the concept of information[J]. Mathematical Geology, 1970,2(1):25-38.

[10] Lin Dekang. An information-theoretic definition of similarity[C]// Proceedings of the 15th International Conference on Machine Learning. 1998:296-304.

[11] Stanfill C, Waltz D. Toward memory-based reasoning[J]. Communications of the ACM, 1986,29(12):1213-1228.

[12] Eskin E, Arnold A, Prerau M, et al. A geometric framework for unsupervised anomaly detection: Detecting intrusions in unlabeled data[M]// Applications of Data Mining in Computer Security. Springer, Boston, MA, 2002:77-102.

[13] Cover T, Hart P. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967,13(1):21-27.

[14] Quinlan J R. Induction of decision trees[J]. Machine Learning, 1986,1(1):81-106.

[15] 鞠可一,周德群,吳君民. 混合概念格在案例相似性度量中的應(yīng)用[J]. 控制與決策, 2010,25(7):987-992.

[16] 趙亮,劉建輝,王星. 基于Hellinger距離的混合數(shù)據(jù)集中分類變量相似度分析[J]. 計(jì)算機(jī)科學(xué), 2016,43(6):280-282.

[17] 孫怡帆,李賽. 基于相似度的微博社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014,51(12):2797-2807.

[18] 陳彥萍,楊威,唐成務(wù),等. 基于語(yǔ)義相似度的數(shù)據(jù)服務(wù)分類方法[J]. 信息技術(shù), 2017(12):93-96.