基于復(fù)雜網(wǎng)絡(luò)的混合數(shù)據(jù)聚類分析

王依赟，許 英

(新疆財經(jīng)大學(xué) 統(tǒng)計與數(shù)據(jù)科學(xué)學(xué)院，烏魯木齊 830012)

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

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

本文把復(fù)雜網(wǎng)絡(luò)相關(guān)知識應(yīng)用到混合數(shù)據(jù)中，針對混合數(shù)據(jù)的基于熵的相似矩陣，利用閾值法生成0-1矩陣(即復(fù)雜網(wǎng)絡(luò)的鄰接矩陣)，進而構(gòu)造復(fù)雜網(wǎng)絡(luò)，對生成的復(fù)雜網(wǎng)絡(luò)進行社團結(jié)構(gòu)劃分，復(fù)雜網(wǎng)絡(luò)的一種社團結(jié)構(gòu)劃分就對應(yīng)混合數(shù)據(jù)的一種聚類結(jié)果。

本文用三個數(shù)據(jù)集作為實驗對象，通過和混合數(shù)據(jù)的聚類算法：DP-MD-FN、K-Prototypes、KL-FCM-GM、iEKP、OCIL算法進行比較，實驗結(jié)果表明利用復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)劃分算法得到的混合數(shù)據(jù)的聚類結(jié)果的準(zhǔn)確性更高。

1 混合數(shù)據(jù)相似矩陣

1.1 概念

1.2 數(shù)值型的相似性度量

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

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

(1)

為了計算混合數(shù)據(jù)的相似度，采用一個單調(diào)遞減函數(shù)將距離dist轉(zhuǎn)化為相似度Sr[2-3],它是由一個指數(shù)函數(shù)給出：

(2)

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

1.3 分類型的相似性度量

(3)

(4)

(5)

(6)

(7)

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

(8)

1.4 混合型的相似性度量

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

(9)

2 轉(zhuǎn)換混合數(shù)據(jù)集為復(fù)雜網(wǎng)絡(luò)

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

2.1 相關(guān)網(wǎng)絡(luò)法

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

(10)

可以得到混合數(shù)據(jù)間的相似度的鄰接矩陣A=(Aij)n×n,基于該鄰接矩陣，構(gòu)建相對應(yīng)的復(fù)雜網(wǎng)絡(luò)。

2.2 三種混合數(shù)據(jù)集對應(yīng)的相關(guān)網(wǎng)絡(luò)

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

表1 三個實際混合數(shù)據(jù)集

三組數(shù)據(jù)集在不同閾值下對應(yīng)了不同的復(fù)雜網(wǎng)絡(luò)。Heart Disease混合數(shù)據(jù)集在閾值s為0.1～0.8時，連通分支數(shù)均為1，當(dāng)閾值s為0.9時，連通分支數(shù)為5,不同閾值對應(yīng)的網(wǎng)絡(luò)邊數(shù)和連通分支數(shù)如表2所示。

表2 混合數(shù)據(jù)集Heart在不同閾值下對應(yīng)的復(fù)雜網(wǎng)絡(luò)

Credit Approval混合數(shù)據(jù)集在閾值為0.1～0.3時，連通分支數(shù)為1，當(dāng)閾值為0.35～0.8時，連通分支數(shù)為2，閾值為0.8時，連通分支數(shù)為4，閾值為0.9時，連通分支數(shù)為5，不同閾值對應(yīng)的網(wǎng)絡(luò)邊數(shù)和連通分支數(shù)如表3所示。

表3 混合數(shù)據(jù)集Credit在不同閾值下對應(yīng)的復(fù)雜網(wǎng)絡(luò)

Australian Credit Approval混合數(shù)據(jù)集在閾值為0.1～0.3時，連通分支數(shù)為1，當(dāng)閾值為0.35～0.7時，連通分支數(shù)為2，閾值為0.8～0.9時，連通分支數(shù)為4，不同閾值對應(yīng)的網(wǎng)絡(luò)邊數(shù)和連通分支數(shù)如表4所示。

表4 混合數(shù)據(jù)集Australian在不同閾值下對應(yīng)的復(fù)雜網(wǎng)絡(luò)

3 聚類結(jié)果分析

3.1 復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)劃分結(jié)果

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

混合數(shù)據(jù)集Heart在0.1～0.9閾值下對應(yīng)復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)劃分的NMI值和分類數(shù)k如表5所示，由表5可知，混合數(shù)據(jù)集Heart在閾值為0.1時，LE算法得到的NMI值最大，NMI=0.413，該社團結(jié)構(gòu)劃分算法的結(jié)果即為所對應(yīng)的Heart混合數(shù)據(jù)集的聚類結(jié)果。

表5 混合數(shù)據(jù)集Heart在不同閾值下對應(yīng)復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)劃分NMI值和分類數(shù)k

混合數(shù)據(jù)集Credit在0.1～0.8閾值下對應(yīng)復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)劃分NMI值和分類數(shù)k如表6所示，由表6可知，混合數(shù)據(jù)集Credit在閾值為0.35時，LOU算法得到的NMI值最大，最大值為0.457，該社團結(jié)構(gòu)劃分算法的結(jié)果即為所對應(yīng)的Credit混合數(shù)據(jù)集的聚類結(jié)果。

表6 混合數(shù)據(jù)集Credit在不同閾值下對應(yīng)復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)劃分NMI值和分類數(shù)k

混合數(shù)據(jù)集Australian在0.1～0.8閾值下對應(yīng)復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)劃分NMI值和分類數(shù)k如表7所示，由表7可知，混合數(shù)據(jù)集Australian在閾值為0.35時，F(xiàn)G算法得到的NMI值最大，最大值為0.434，該社團結(jié)構(gòu)劃分算法的結(jié)果即為所對應(yīng)的Australian混合數(shù)據(jù)集的聚類結(jié)果。

表7 混合數(shù)據(jù)集Australian在不同閾值下對應(yīng)復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)劃分NMI值和分類數(shù)k

3.2 混合數(shù)據(jù)集聚類結(jié)果分析

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

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

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

表9 混合數(shù)據(jù)集在多種算法下的ACC值

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

表10 混合數(shù)據(jù)集在多種算法下的ARI值

4 結(jié)論

數(shù)據(jù)挖掘擅長處理各類數(shù)據(jù)并從中發(fā)現(xiàn)隱藏規(guī)律，復(fù)雜網(wǎng)絡(luò)著重于從網(wǎng)絡(luò)角度描述系統(tǒng)結(jié)構(gòu)功能并發(fā)掘其普適規(guī)律，將復(fù)雜網(wǎng)絡(luò)相關(guān)知識應(yīng)用于混合數(shù)據(jù)中，將有效解決混合數(shù)據(jù)在聚類分析與處理方面的瓶頸。

針對混合數(shù)據(jù)集的聚類問題，本文把復(fù)雜網(wǎng)絡(luò)相關(guān)知識應(yīng)用到混合數(shù)據(jù)中，針對混合數(shù)據(jù)的基于熵的相似矩陣，利用閾值法生成復(fù)雜網(wǎng)絡(luò)的鄰接矩陣，對生成的復(fù)雜網(wǎng)絡(luò)進行社團結(jié)構(gòu)劃分，復(fù)雜網(wǎng)絡(luò)的一種社團結(jié)構(gòu)劃分就對應(yīng)混合數(shù)據(jù)的一種聚類結(jié)果。該方法進一步 探索了數(shù)據(jù)挖掘和復(fù)雜網(wǎng)絡(luò)之間的關(guān)系，也為混合數(shù)據(jù)的處理提供了新的方向。

通過與現(xiàn)有的聚類方法進行比較，本文的NMI、ACC和ARI值均有所提高，結(jié)果表明本文提出的方法將有助于提高混合數(shù)據(jù)聚類分析的準(zhǔn)確度，從而為今后復(fù)雜網(wǎng)絡(luò)和數(shù)據(jù)挖掘知識的融合提供強有力的依據(jù)。