鄭碧如，吳廣潮

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

0 引 言

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

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

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

1 Lin相似性度量

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

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

(1)

(2)

(3)

(4)

2 Lin相似性度量的改進

2.1 MLin相似性度量

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

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

(5)

(6)

(7)

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

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

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

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

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

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

過程：

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目標實例x,y的相似性。

算法2MLin相似性度量算法

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

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

過程：

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 實驗與分析

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

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

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

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

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

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

3.2 實驗結(jié)果與分析

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

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

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

圖2 k-NN(k=3)十折交叉驗證錯誤率折線圖

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

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

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

4 結(jié)束語

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

參考文獻：

[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]. 計算機科學(xué), 2016,43(6):280-282.

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

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