王依赟，許 英

(新疆財經大學 統計與數據科學學院，烏魯木齊 830012)

隨著社會的高速發(fā)展，人們對數據價值的認識逐漸加深。在這個大數據時代，人們希望從紛繁復雜的數據中提取到有價值的信息。聚類分析是數據挖掘的一個重要算法，是以相似性為基礎，在一個聚類中的對象之間比不在同一聚類中的對象之間具有更多的相似性。

近年來，聚類算法中針對混合數據聚類最著名的方法是Huang提出的K-prototypes算法[1]，該方法結合K-means與K-modes算法對混合屬性數據進行劃分，通過參數μi來控制數值屬性與分類屬性在聚類過程中的權重。

本文把復雜網絡相關知識應用到混合數據中，針對混合數據的基于熵的相似矩陣，利用閾值法生成0-1矩陣(即復雜網絡的鄰接矩陣)，進而構造復雜網絡，對生成的復雜網絡進行社團結構劃分，復雜網絡的一種社團結構劃分就對應混合數據的一種聚類結果。

本文用三個數據集作為實驗對象，通過和混合數據的聚類算法：DP-MD-FN、K-Prototypes、KL-FCM-GM、iEKP、OCIL算法進行比較，實驗結果表明利用復雜網絡社團結構劃分算法得到的混合數據的聚類結果的準確性更高。

1 混合數據相似矩陣

1.1 概念

1.2 數值型的相似性度量

數值型的相似性度量可以采用歐氏距離，兩個數值型數據的歐氏距離定義為：

dist(xi,xj)=‖xi-xj‖2

(1)

為了計算混合數據的相似度，采用一個單調遞減函數將距離dist轉化為相似度Sr[2-3],它是由一個指數函數給出：

(2)

其中Sr的值越接近1，兩個對象越相似。

1.3 分類型的相似性度量

(3)

(4)

(5)

(6)

(7)

將式(7)代入式(4)，可以得到分類屬性的最終相似性測度，如下所示：

(8)

1.4 混合型的相似性度量

數值部分的相似性是作為一個整體來對待的，而分類部分的相似性是作為個體來計算。因此，兩個混合類型對象xi和xj之間的相似性(表示為S(xi,xj))定義為：

(9)

2 轉換混合數據集為復雜網絡

各類數據轉換為復雜網絡數據將會有更多的附加信息，其中最重要的是結構或拓撲信息，網絡拓撲能夠以簡潔的方式對數據交互進行系統化的編碼，從本地結構信息到全局結構信息。構建網絡的方法有很多種，如閾值法、最小生成樹法等等,本文將采用閾值法將混合數據轉換為復雜網絡數據。

2.1 相關網絡法

設定閾值參數s，以每個混合數據對象為節(jié)點，若任意兩個混合數據的相似性大于或者等于所給定的閾值s(s∈[-1,1]),則這兩個混合數據之間有邊相連，小于閾值的不相連。具體定義如下：

(10)

可以得到混合數據間的相似度的鄰接矩陣A=(Aij)n×n,基于該鄰接矩陣，構建相對應的復雜網絡。

2.2 三種混合數據集對應的相關網絡

為了驗證本文方法的有效性，選用UCI Machine Learning Repository里的Credit Approval數據集、Heart Disease數據集以及Australian Credit Approval這三個實際混合數據集，數據集的真實類別屬性剔除，并作為原始數據分類的基準對各類算法的準確性進行評估。數據集的具體信息如表1所示。

表1 三個實際混合數據集

三組數據集在不同閾值下對應了不同的復雜網絡。Heart Disease混合數據集在閾值s為0.1～0.8時，連通分支數均為1，當閾值s為0.9時，連通分支數為5,不同閾值對應的網絡邊數和連通分支數如表2所示。

表2 混合數據集Heart在不同閾值下對應的復雜網絡

Credit Approval混合數據集在閾值為0.1～0.3時，連通分支數為1，當閾值為0.35～0.8時，連通分支數為2，閾值為0.8時，連通分支數為4，閾值為0.9時，連通分支數為5，不同閾值對應的網絡邊數和連通分支數如表3所示。

表3 混合數據集Credit在不同閾值下對應的復雜網絡

Australian Credit Approval混合數據集在閾值為0.1～0.3時，連通分支數為1，當閾值為0.35～0.7時，連通分支數為2，閾值為0.8～0.9時，連通分支數為4，不同閾值對應的網絡邊數和連通分支數如表4所示。

表4 混合數據集Australian在不同閾值下對應的復雜網絡

3 聚類結果分析

3.1 復雜網絡社團結構劃分結果

本節(jié)基于上述三個實際混合數據集所構造的復雜網絡，利用復雜網絡社團結構劃分的四種算法Fast greedy(FG),Leading eigen(LE),Louvalin(LOU),Walktrap(WA)算法對復雜網絡進行社團結構劃分，記錄不同閾值下的復雜網絡社團結構劃分的NMI值和分類數。

混合數據集Heart在0.1～0.9閾值下對應復雜網絡的社團結構劃分的NMI值和分類數k如表5所示，由表5可知，混合數據集Heart在閾值為0.1時，LE算法得到的NMI值最大，NMI=0.413，該社團結構劃分算法的結果即為所對應的Heart混合數據集的聚類結果。

表5 混合數據集Heart在不同閾值下對應復雜網絡的社團結構劃分NMI值和分類數k

混合數據集Credit在0.1～0.8閾值下對應復雜網絡的社團結構劃分NMI值和分類數k如表6所示，由表6可知，混合數據集Credit在閾值為0.35時，LOU算法得到的NMI值最大，最大值為0.457，該社團結構劃分算法的結果即為所對應的Credit混合數據集的聚類結果。

表6 混合數據集Credit在不同閾值下對應復雜網絡的社團結構劃分NMI值和分類數k

混合數據集Australian在0.1～0.8閾值下對應復雜網絡的社團結構劃分NMI值和分類數k如表7所示，由表7可知，混合數據集Australian在閾值為0.35時，FG算法得到的NMI值最大，最大值為0.434，該社團結構劃分算法的結果即為所對應的Australian混合數據集的聚類結果。

表7 混合數據集Australian在不同閾值下對應復雜網絡的社團結構劃分NMI值和分類數k

3.2 混合數據集聚類結果分析

復雜網絡的社團結構劃分結果對應混合數據集的聚類結果，針對上述結果，表8列出了3.1節(jié)的結果和DPC-MD、DP-MD-FN、K-Prototypes、KL-FCM-GM、EKP、OCIL算法在三個混合數據集上NMI值。由表8可以看到，本文所得的三個數據集聚類結果的NMI最大值分別為0.413,0.458,0.434，與其他算法相比效果更好。

表8 三個混合數據集在多種算法下的NMI值比較

表9列出了3.1節(jié)的結果和DPC-MD、DP-MD-FN、K-Prototypes、KL-FCM-GM、EKP、OCIL算法在三個混合數據集上的準確度ACC值。由表9可以看到，本文所得的三個混合數據集的ACC值分別為0.858 1,0.872 9,0.858 0，與其他算法相比效果更好。

表9 混合數據集在多種算法下的ACC值

表10列出了3.1節(jié)的結果和DPC-MD、DP-MD-FN、K-Prototypes、KL-FCM-GM、EKP、OCIL算法在三個混合數據集上的蘭德指數ARI值。由表10可以看到，本文所得的三個混合數據集的ARI值分別為0.512 9,0.558 9,0.512 6，與其他算法相比效果更好。

表10 混合數據集在多種算法下的ARI值

4 結論

數據挖掘擅長處理各類數據并從中發(fā)現隱藏規(guī)律，復雜網絡著重于從網絡角度描述系統結構功能并發(fā)掘其普適規(guī)律，將復雜網絡相關知識應用于混合數據中，將有效解決混合數據在聚類分析與處理方面的瓶頸。

針對混合數據集的聚類問題，本文把復雜網絡相關知識應用到混合數據中，針對混合數據的基于熵的相似矩陣，利用閾值法生成復雜網絡的鄰接矩陣，對生成的復雜網絡進行社團結構劃分，復雜網絡的一種社團結構劃分就對應混合數據的一種聚類結果。該方法進一步 探索了數據挖掘和復雜網絡之間的關系，也為混合數據的處理提供了新的方向。

通過與現有的聚類方法進行比較，本文的NMI、ACC和ARI值均有所提高，結果表明本文提出的方法將有助于提高混合數據聚類分析的準確度，從而為今后復雜網絡和數據挖掘知識的融合提供強有力的依據。