基于類別信息熵加權的MKNN算法

陳雪云*，劉艷芳，柯婷，張劍楠

?

基于類別信息熵加權的MKNN算法

陳雪云*，劉艷芳，柯婷，張劍楠

(龍巖學院信息工程學院，福建省龍巖市 364000)

針對MKNN算法對類屬性數據處理簡單的問題，引入信息熵作為處理類屬性數據的相似性度量，進而引入類別信息熵的概念。對同一類型的類屬性數據根據其類別信息熵權重的大小，把數據集的記錄進行分類進而得到測試結果。實驗結果驗證了該算法的有效性。

數據挖掘；MKNN；類別信息熵；類屬性

引言

數據挖掘算法有分類算法、聚類算法、回歸等這幾類。每一類的分析側重點和其優勢各有差異。分類是通過分析已知數據集數據特征為其標簽，再通過與此標簽和對未知數據集的對比從而進行分類，分類是數據挖掘中的一個必不可少的研究方向。1968年Cover和Hart[1]提出的K近鄰(KNN, k-Nearest Neighbor)算法是最簡單的數據挖掘分類算法之一，同樣也是最好的文本算法之一。由于它的“簡單”，被稱為懶惰算法，因此可以改進的地方很多。比如分類速度慢，屬性相同的權重影響了準確率。直到目前為止，有很多學者對它進行過研究并提出了很多改進方法。例如：張著英等[2]提出將粗糙集理論應用到KNN算法中，實現屬性約簡以解決KNN分類效率低的缺點；周靖[3]等提出一種采用類相關度優化距離的KNN改進算法，提高了KNN的分類性能；戚孝銘[4]通過聚類手段進行去噪處理，并且通過加快K近鄰的搜索速度提高KNN算法的分類效率；肖輝輝[5]等利用屬性值對類別的重要性對KNN進行改進，提高了分類準確性；耿麗娟和李星毅[6]對已知樣本根據類域進行分層，大大降低了無效的計算；郝勝軒[7]等針對KNN算法對缺失數據的填補效果會因為原始數據中存在噪聲而受到嚴重影響的問題，提出了ENN-KNN消除噪聲最近鄰對填補結果的影響；蘇毅娟等[8]創新性地通過線性復雜度聚類方法對大數據樣本進行分塊，然后在測試過程中找出與待測樣本距離最近的塊，并將其作為新的訓練樣本進行K最近鄰分類，大幅度地減少了K最近鄰算法的測試開銷，使其能在大數據集中得以應用；康麗萍[9]等提出基于加權KNN的融合分類方法以解決將語義級融合算法應用于不同分類方法時由于分類決策基準不統一導致分類結果不理想，大幅降低融合分類性能的問題；劉繼宇[10]等針對粗糙集訓練過程中從未遇到過的樣本的分類問題進行了探討,根據條件屬性的重要性確定加權系數，采用加權KNN的方法來解決無法與決策規則精確匹配的樣本分類問題。Liu和Zhang[11]提出的互K近鄰算法(MKNN)很好的解決了K最近鄰(KNN)存在的偽近鄰問題。MKNN可以很好的消除異常數據和提高質量，因為該算法通過更好地丟棄訓練樣本中可能會有的噪聲數據從而實現克服KNN中存在的偽近鄰問題，所以說MKNN是基于在KNN的基礎之上，解決了KNN偽近鄰問題的干擾，而改善了算法的性能。但是兩者的近鄰選擇都取決于相似性度量的選擇，而相似性度量是數據集中分類分析的決定性因素。傳統的相似性度量大多適合數值型屬性，MKNN和傳統的KNN一樣都適合在數值型領域。對于類屬性數據也有學者提出了改進的方法。陳雪云[12]等提出的GwMKNN算法引入了類別基尼系數的概念來處理類屬性數據，用基尼系數統計某一類屬性中不同值分布對這個類的貢獻度作為此類屬性的權重,并以此作為估算不同樣本之間的相似性度量對MKNN進行優化,擴寬了MKNN的使用面。

根據上述研究內容的有關分析，提出的基于類別信息熵加權的MKNN算法（以下簡稱EwMKNN)主要研究的是類屬性數據的分類，是在MKNN算法基礎上衍生過來的，EwMKNN算法中引入信息熵用來作為處理類屬性數據的相似性度量。現在同樣也有很多關于信息熵的研究算法，例如：王磊[13]利用熵來度量新文本對于已分類文本集合的貢獻度大小，并以此熵值來判斷文本歸屬的類；甘蘇婷[14]在信息熵理論的基礎上利用數據挖掘技術構建決策支持系統的信息組織機制，信息熵的利用可以度量決策支持系統中信息組織的規律性程度；陳曦[15]等利用信息熵原理定義了不同類型的謠言信息熵，并通過對謠言傳播計算機仿真結果的熵值分析，驗證了謠言信息度量方法的可行性；Li[16]等將最大信息熵模型應用于各種自然語言的語義分析任務中，進而實現輿情分析；朱佳佳[17]等使用改進的SVM多分類器對熵值量化后的流量進行分類判決,根據分類結果捕獲異常；魏琴芳[18]等將信息熵和遺傳算法應用于檢測過程所用比對庫的訓練，采用異常檢測和特征檢測結合方法進行入侵檢測；潘瑞林[19]等提出基于α信息熵的屬性重要度度量,并以此構建混合屬性約簡算法。

根據這些算法的分析，得知信息熵有著很好避免噪聲數據的干擾的效果，可用來作為處理類屬性數據的相似性度量，以更好地優化MKNN算法,提高其對類屬性數據處理的效率。為研究類屬性型的數據提供了更加準確的分析方法。

1 基本概念和定義

1.1 偽近鄰

K近鄰是根據測量不同特征值之間的距離分類，首先需要在訓練數據集中找到K個最近鄰的樣本，類別由這K個近鄰中占最多的樣本的類別決定，若k值取得較大就會出現很多干擾的樣本，影響了分類準確率。通過引入互近鄰的概念，獲取更加真實的樣本，去除掉干擾的或者“假”的鄰居，即偽近鄰，依據真實鄰居的標簽信息分類，丟棄噪聲數據，從而提高了預測結果的準確性，以及分類模型的預測性能。

1.2 信息熵

熵可以說是個物理單位因為最早是表示熱力學，其值表示的是一個系統的混亂程度，然而在信息理論中的這個熵也可稱信息熵，可用來表示某個隨機變量的不穩定性程度。可以有效避免噪聲數據的干擾。

定義1信息熵

假定X是一個隨機變量，p(x)表示變量X取值為x的概率，那么它的不確定性程度可以表示為信息熵E(X)形式，則：

定義2集合D的信息熵Entropy(D)[13]

公式中Pi表示集合D中屬于Ci的比例。

定義3類別信息熵[12]

在文獻[12]中已經提出過類別信息熵的概念，類別信息熵就是在香農信息熵的概念上對其延伸和擴展，使其適應對多維類屬性數據的處理，設定現有一個多維的類屬性數據集，D表示一個多維的樣本數據集，即，是一個r維的數據集合，其中表示的是的數據集的已定義的標簽類別，，q是指樣本集中的類別數，代表中的樣本數，表示在類中第個屬性上的不同取值的次數，其中。那么類別信息熵的公式可表示為:

其中，（1-4）

將計算得到的信息熵與公式3-5的結果相乘后得到一個規范化的結果。

經過以上的分析，可以了解到，關于樣本中的某一個屬性，通過對其有著一樣的類別標識，再通過類別信息熵的統計和計算：若其中某一個類別在這個屬性的對于一樣的屬性值的越大，那么其通過類別信息熵處理的權重越大，則屬于該類別的機率就越大。如果類別信息熵越小，則其計算所得的權重越小，屬于該類別的機率就會更大。

2 EwMKNN的算法步驟和基本實現

通過在MKNN算法的基礎之上引入類別信息熵的概念，并將類別信息熵作為一種新的權重，進而對樣本進行分類。

EwMKNN的算法實現：

算法1：計算類別信息熵（CaculateCategory’s Entorpy）

輸入：訓練樣本集C

輸出：當j屬性屬于Nominal類型時，其不同類別信息熵E(k,j)；

Begin

Step 1：聲明訓練樣本數據集trainIns,不妨選取數據集C中標號為k的樣本集；

Step 2: 遍歷所有訓練樣本數據集，再對其進行操作；

Step 3: 計算出訓練數據樣本trainIns中Xjl在第k類樣本中出現的次數，即fk(Xjl)的值對樣本集trainIns進行統計，即nk的值；

Step 4：依據公式（4）和fk(Xjl)的值，nk的值，算出Pjl(k)的值，表示trainIns中某個屬性的某個值Pjl(k)出現的概率；

Step 5：依據公式（3）計算出類別信息熵E(i,j),最后通過和相乘得到規范化的結果；

Step 6:返回E(i,j)的值作為權重；

End

算法2：計算樣本和樣本之間在j屬性上的距離（CaculteEntoryDistance）；

輸入：兩個樣本集例如：Dt（Dt為測試樣本）和Di,屬性j,權重E(k,j)；

輸出：兩個樣本在j屬性上的距離EnDis(Djt,Dji)；

Begin

Step 1:初始化EnDis(Djt,Dji)=0；

Step 2:遍歷樣本中的所有屬性，若屬性是Nominal型，則接著判斷樣本Dt和樣本Di是否相等，如果相等則返回EnDis(Djt,Dji)=0；反之則返回Di所在的類別信息熵，且EnDis(Djt,Dji)=EnDis(yi,j)；

Step 3:若數據類型不是類屬性數據則EnDis(Djt,Dji)=（Djt-Dji）2

Step 4:最后返回EnDis(Djt,Dji)

End

算法3:類別信息熵分類算法(EwMKNN)

Begin

輸入：訓練樣本集C,樣本和樣本之間在j屬性上的距離EnDis(Djt,Dji)，待分類樣本Dt,近鄰數K

輸出：預測待分類樣本Dt的類別St

Step 1:聲明訓練樣本Di和測試樣本Dt,并初始化Dt的近鄰集合為空；

Step 2：用CaculteEnDis計算待測試樣本Dt與各訓練樣本Di之間的距離CaluteEnDis(Djt,Dji)，i={1,...,n}；

Step 3:依據上一步驟的計算結果作為判定數據集中樣本是否為Dt的K近鄰的標準，獲得近鄰集Nk(Dt),k即近鄰數；

Step 4: 重復上面兩步操作，然后找出Dt的互k近鄰：先設Dt近鄰集合Nk(Dt)中的一個近鄰為Di，再從數據集C中找出Di的近鄰集合Nk(Di)，接著判斷Dt∈Nk(Di)是否為真，若為真則將Di的類別信息Si添加到Dt的類別信息集合Y(Dt)中；

Step 5：最后對上一步驟的結果進行統計，將最大類別數作為待測樣本Dt的類別標簽；

Step 6:返回最后的結果St，即Dt的類別標。

End

3 實驗的結果與分析

3.1 實驗數據的基本信息

為了驗證算法的性能，選擇在UCI[20]的數據集中選取10個數據集進行檢測，數據集的詳細信息如表1所示。

表1 數據集基本信息表

3.2 實驗結果

為了驗證EwMKNN的可靠性，將它與KNN，MKNN，EwKNN，GwMKNN這幾個算法一同進行對比檢驗，其中EwKNN是只把類別信息熵應用于KNN上的處理方法。主要用了10-折交叉檢驗法，10-折交叉檢驗是通過將數據集分成10個小的子集，然后將這些子集中挑選一個出來做測試樣本集，10個子集輪流做測試樣本集，最終得到的結果取均值做最終測試結果，要保證上述幾個算法檢驗過程中用的是同一數據集和測試樣本集。測試時，k值選擇可以是20以內的質數，這里k取3。檢測分析的結果如表2所示。

表2 分類精度對比

根據表2的數據可以很好的看出，MKNN的準確率是比KNN的要高，在16個數據集中有12個數據集都顯示其優越性，然而在對MKNN算法加以改進的基于類別信息熵加權的MKNN算法EwMKNN在7個數據集的測試中都顯示出在所有算法中最高的準確率，GwMKNN算法的準確率也是比較好的，文獻[9]中非常清楚的提出GwMKNN算法是引入的基尼系數的概念，通過對距離加權來進行對數據集分類的算法，在處理hayes-roth，labor，promoters數據集時，還顯示出更加好的準確率。從數據集的角度來看，在數據集audiology，dermatology，zoo上都可以體現出EwMKNN算法在處理多類別數據時比EwKNN，GwMKNN這兩種算法有更高的準確率。在處理類別較少類屬性較多的數據集時，雖然EwMKNN算法的準確率沒有比MKNN算法高出很多，也證明該算法還需要經過改善，但也在總體方面說明了MKNN改進后的EwMKNN算法是有效的。

4 結束語

提出的基于類別信息熵加權的MKNN算法是首先要在已經解決了KNN算法偽近鄰問題的MKNN算法上，進行對權重的改進，互k近鄰算法（MKNN）準確率在KNN基礎上本來就有提高，但在處理類屬性數據仍表現出有些不足之處。引入類別信息熵后，用信息熵加權的方式提高類屬性數據分類的準確率。在數據集上的檢測結果說明了EwMKNN相比較一同檢測的幾種算法而言有相對較好的對類屬性數據的分類準確率。也就驗證了EwMKNN算法的改進是有效的。EwMKNN算法的優點是：有較好的分類準確性；可以針對類屬性數據的分類；引入了類別信息熵的概念，易于改進和實現；同樣易于結合，可以同許多其他分類算法結合，例如KNN算法等。基于類別信息熵加權的MKNN算法（EwMKNN）仍存在著不足之處，對于有高維數據集時準確率會下降，在多類別的類屬性數據集的處理上可以進一步的開拓，更好增強其使用程度。

[1] Cover, T.M., Hart, P.E.. Nearest Neighbor Pattern Classific. IEEE Trans on Information Theory, 1967, 13( 1) : 21－27.

[2] 張著英, 黃玉龍, 王翰虎. 一個高效的KNN分類算法[J]. 計算機科學, 2008, 03: 170-172.

[3] 周靖, 劉晉勝. 一種采用類相關度優化距離的KNN算法[J]. 微計算機應用,2010, 11: 7-12.

[4] 戚孝銘. 基于蜂群算法和改進KNN的文本分類研究[D]. 上海交通大學, 2013.

[5] 肖輝輝, 段艷明. 基于屬性值相關距離的KNN算法的改進研究[J]. 計算機科學, 2013, S2: 157-159+187.

[6] 耿麗娟, 李星毅. 用于大數據分類的KNN算法研究[J]. 計算機應用研究,2014, 05: 1342-1344+1373.

[7] 郝勝軒, 宋宏, 周曉鋒. 基于近鄰噪聲處理的KNN缺失數據填補算法[J]. 計算機仿真, 2014, 07: 264-268.

[8] 蘇毅娟, 鄧振云, 程德波, 等. 大數據下的快速KNN分類算法[J]. 計算機應用研究, 2016, 33(4): 1003-1006.

[9] 康麗萍, 孫顯, 許光鑾. 加權KNN的圖文數據融合分類[J]. 中國圖象圖形學報, 2016, 21(7): 854-864.

[10] 劉繼宇, 王強, 羅朝暉,等. 基于粗糙集的加權KNN數據分類算法[J]. 計算機科學, 2015, 42(10): 281-286.

[11] Liu, H., Zhang,S.. Noisy data elimination using mutual k-nearest neighbor for classification mining. The Journal of Systems and Software, 2012, 85: 1067–1074.

[12] 陳雪云, 郭躬德, 陳黎飛, 盧偉勝. GwMKNN:針對類屬性數據加權的MKNN算法[J]. 計算機系統應用, 2013, 08:103-108 +158.

[13] 王磊. 基于信息熵的中文文本分類算法研究[D]. 西北師范大學, 2007.

[14] 甘蘇婷. 基于信息熵的數據挖掘算法在決策支持系統中的改進研究[D]. 吉林大學, 2015.

[15] 陳曦, 翔晨, 李煒, 樓宗元. 基于信息熵的謠言信息度量方法[J]. 華中科技大學學報(自然科學版), 2013, S1: 413-417.

[16] Li, R., Tao, X., Tang, L., Hu, Y. Using Maximum Entropy Model for Chinese Text Categorization. Computer Science, 2004, 3007: 578-587.

[17] 朱佳佳, 陳佳. 基于熵和SVM多分類器的異常流量檢測方法[J]. 計算機技術與發展, 2016, 26(3): 31-35.

[18] 魏琴芳, 成勇, 胡向東. 基于信息熵的無線傳感網入侵檢測遺傳算法[J]. 重慶郵電大學學報(自然科學版), 2016(1): 107-112.

[19] 潘瑞林, 李園沁, 張洪亮, 伊長生, 樊楊龍, 楊庭圣. 基于α信息熵的模糊粗糙屬性約簡方法[J]. 控制與決策, 2017(2): 340-348.

[20] UCI Repository of Machine Learning Databases [DB /OL]. [2012-12-12].

[21] ZHANG Zhen Jie, ZUO Ren Guang, XIONG Yi Hui. A comparative study of fuzzy weights of evidence and random forests for mapping mineral prospectivity for skarn-type Fe deposits in the southwestern Fujian metallogenic belt, China [J]. Science China (Earth Sciences), 2016, 03:556-572.

[22] Data Mining: Concepts and Techniques, 2nd ed., Jiawei Han and Micheline Kamber, Morgan Kaufmann, 2006. P P383-464.

MKNN Algorithm Based on the Weight of Category's Entropy

CHEN Xueyun *, LIU Yanfang, KE Ting, ZHANG Jiannan

(Institute of Information Engineering, Longyan University, Longyan Fujian 364000, China)

Since the process of the mutual k-nearest neighbor (MKNN) dealing with nominal data is simple, we introduce the entropy to deal with the similarity measure of the nominal data, and then the concept of Category's entropy is introduced. We can obtain the entropy weight of the same type of nominal data, and then get experimental results through the classification of the data set. The experimental results demonstrate the effectiveness of the proposed algorithm.

data mining; mutual k-nearest neighbor; category's entropy; nominal data

10.19551/j.cnki.issn1672-9129.2017.01.03

TP18

A

1672-9129(2017)01-0010-05

2017-01-23；

2017-02-09。

國家自然科學基金面上項目（61379049和61379089），福建省大學生創新創業訓練計劃項目（S20141004）；龍巖學院協同創新項目（張凌）。

陳雪云(1976-)，女，福建省漳平市，龍巖學院副教授，碩士，主要研究方向：數據挖掘技術及其應用、計算機應用技術；劉艷芳(1987-)，女，河南省濮陽市，龍巖學院教師，研究生，主要研究方向：粗糙集與粒計算、人工智能和機器學習；柯婷(1995-)，女，安徽省安慶市，龍巖學院學生，主要研究方向：軟件工程；張劍楠(1994-)，男，廣東省梅州市，龍巖學院學生，主要研究方向：軟件工程。E-mail：cxy2165254@163.com