基于K-Means聚類算法的HDMA數據挖掘方法

耿德志，徐 乾

(1. 晉中學院信息技術與工程學院，山西 晉中 030600；2. 山西大學計算機與信息技術學院(大數據學院)，山西 太原 030006)

1 引言

作為一種決策支持階段，數據挖掘[1]在人工智能、統計學技術以及機器學習等基礎上，對企業原有數據進行高度自動化分析，根據歸納性推理挖掘到內在形式，從而精準預測用戶行為，并做出策略上的適當調整，通過正確決策降低市場風險。數據挖掘技術是大勢所趨的必然產物，隨著企業數據量的爆炸式增長，當前數據庫工具既無法進行高效處理，也無法在海量的數據里選取出有用信息，所以，數據挖掘技術成為了數據庫與決策領域的熱點研究課題。數據挖掘就是在大規模的數據庫內，完成用戶隱含未知有效信息的興趣知識提取，該知識具有概念、模式、規律以及規則等多種形式，也就是說，數據挖掘技術的處理目標除了數據庫，還有可能是文件系統或者其它種類的數據集合。

數據挖掘過程中的關鍵環節之一就是聚類，通過劃分物理或者抽象的數據集為相似對象類別，實現各類別中的數據對象彼此相似，且又不同于其它類別中所含的數據對象。經過數據聚類，可以更好地對數據集中的數據對象進行理解，因此，在文本分析、機器學習、模式識別以及數據挖掘等研究中運用廣泛。文獻[2]提出的多層次分布式網絡數據挖掘改進方法，利用概率歪曲策略解決初始數據集擾亂問題，重構項集支持度，通過概率轉換得到挖掘數據；文獻[3]提出一種基于FFD(Full Functional Device，完整功能設備)的大規模高維數據集中局部異常數據挖掘方法，為了提升異常數據的抑制性能，采用無線傳輸技術，設定方法宗旨是對任務級與作業級的實現，通過FFD強控性能來互通無線傳輸技術數據和挖掘進程數據，最后，依據FIFO(First Input First Output，先進先出隊列)挖掘理念與目標函數，完成數據挖掘與本地化處理。

上述兩種文獻方法的挖掘數據類型相對單一，導致混合屬性數據的挖掘效果較差，故本文對基于K-Means聚類算法的高維混合屬性數據挖掘方法進行研究，依據分類型與數值型數據的度量形式，探索高維混合屬性數據相似度，提升聚類精準度，在K-means聚類算法中引入最大距離自動生成k值與坐標旋轉方法，抑制挖掘階段中的聚類中心點影響，應用類異常因子，增加異常數據判定與挖掘的準確性。

2 高維混合屬性數據相似度分析

分類型數據與數值型[4]數據共同構成的高維混合屬性數據，相似度不同于單一屬性數據度量形式，同時，聚類過程中，相似度主要用于反映數據之間的類別概率。

基于數值型數據的相似度度量，一般情況下，會采用幾何性質[5]度量方式當做標準。假設數據Xi(xi1，xi2，…，xiq)與Xj(xj1，xj2，…，xjq)是數據集X的兩條數據，則兩數據的間距界定式如下所示

(1)

式中，數據集X維數是q，第k維Xi與Xj的取值分別是xik、xjk。

所以，下列為數據Xi與簇Uj的相似度界定式

(2)

式中，第j個簇中心為Uj，其第k維取值為Ujk。數據Xi與其它數據的間距均值表達式如下所示

(3)

其中，Cj內的數據數量是|Cj|。

針對分類型數據相似度的度量形式，如果兩個分類型數據Xi(xi1，xi2，…，xiq)與Xj(xj1，xj2，…，xjq)屬于同一數據集X，則兩數據間相似度定義式如下所示

(4)

(5)

若將分類型數據Xi與分類型簇A的相似度認為是數據與其它數據的相似度均值，則下列公式為其相似度界定表達式

(6)

通過擴展上列定義式，即可獲得兩分類型數據的簇相似度，設定A、B分別是該分類型數據的簇，那么，其相似度界定式如下所示

(7)

將上述兩類型數據相似度度量形式作為高維混合屬性數據的度量標準，采用下列等式對其進行描述

d(xi，Uj)=dn+wldc

(8)

式中，dn為高維混合屬性數據中的數值型數據相似度，dc為分類型數據相似度，Uj為第j個簇特征矢量，wl為第l個簇內的分類型數據維占比權值，dn、dc分別為數值型數據與分類型數據的相似度，則計算式如下

(9)

(10)

3 K-Means聚類算法下高維混合屬性數據挖掘

3.1 K-Means聚類算法下數據聚類

3.1.1 K-means算法聚類流程

K-means聚類算法的核心理念是把簇中心點[6]設定為簇里點的平均數值或質心[7]，采取持續迭代下降策略，完成數據集的聚類，作為一種簡單的無監督學習方法，該算法能夠基于無任意標號的條件，對簇與簇中心點進行自動設置，所以，該方法被當做挖掘工具廣泛應用于工業、商業等諸多領域。

通過持續迭代計算數據對象聚類中心點的過程就是K-means聚類算法，其運算流程描述如下：

1)從數據集X內隨機選取數據對象，假設初始聚類中心為所選的k個數據對象，則初始聚類中心點分別是C1，C2，…，Ck，明確數據集所需劃分類別個數；

2)通過求取數據集的其余數據對象與k個初始中心點間距，完成各數據對象與最近類別的分類，進而產生中心是k個初始中心點的類。若數據Xp與中心點Ci距離最近，則把數據Xp分類至Ci類別內；

(11)

4)迭代上述兩個步驟，待計算后聚類中心點與計算前一致時，聚類收斂，迭代結束；

5)將聚類結果輸出。

3.1.2 最大距離自動生成k值聚類優化

最大距離自動生成k值策略無需提前明確k的大小，進一步提升了K-means算法的可行性，該策略的基本原理為：通過掃描全部數據，設置初始聚類中心為最遠距離的兩個數據，根據歐幾里得距離完成剩余數據與兩類別的劃分，若新增加類別中心點為距離最遠的數據對象，則要重新分類全部數據，待符合終止條件，循環結束。

依據最大距離自動生成k值策略原理，得到如下算法具體流程：

1)假設含有x個數據的數據集為Xx={A1，A2，…，Ax}，初始聚類中心應選取間距最大的兩數據，由于Ai=S1，Aj=S2，且i，j≤x，則dij為最遠間距；

2)根據歐幾里得距離公式，完成剩余數據與初始聚類中心分類，若數據與中心點Ai更近，則歸屬于S1，反之則歸屬至S2，從而產生類別S11與S12；

3)在類別S11數據與S1的所有間距中得到最遠距離d11，同理可得類別S12中數據與S2的最大間距d21，將兩個最大間距中的較大距離設定成d1，那么，其相應數據則是S3；

4)通過參數h比較dij與d1大小，若d1≥hdij，則認為第三個聚類中心是S3，可得類別S31、S32以及S33；

5)從類別S31數據與S1的所有間距中得到最遠距離d12，同理可得類別S32、S33中數據與S2、S3的最大間距d22、d33，將三個最大間距中的較大距離設定成d2，則其相應數據則是S4；

3.1.3 坐標旋轉聚類優化

為了防止出現局部最優解問題，可利用坐標旋轉方法獲取初始中心點，穩定聚類結果，其計算流程如下：

1)已知有n個數據存在于數據集X內，集合P為所有數據的間距，其中，DM為最大間距；

2)若數據A和B是DM對應數據，則對該數據間的中心點坐標C及其半徑R/2進行計算；

3)將其中一個數據設定成首個中心點，圓心是C，半徑是R/2，假設起始參照點是首個中心點，根據圓心角2π/k即可獲得點D，則第二個中心點就是數據集X內與點D間距最小的數據；

4)當聚類中心點數量與k值相等時，進行下一步；當不足k值時，將起始參照點設定為點D，返回第三步，待滿足k值后結束；

5)初始中心點為k個聚類中心點，利用歐幾里得距離公式與K-means算法，聚類劃分數據集X。

坐標轉換過程的基點是最大距離，通過旋轉坐標使初始聚類中心不再進行隨機選擇，從而實現聚類中心點散布于各類別里，防止發生類別中沒有中心點或者超出一個中心點的情況。

3.2 數據挖掘實現

利用降噪處理所得的聚類結果進行異常標記。假設類別C里的元素數量比已知的noise count少，則其屬于噪音類別；采用下列公式界定類別集合C={C1，C2，…，Ck}中的各類別類異常因子[8-10]

(12)

針對全部非噪音類別，求取各類別的異常因子并降序排列，設定數據集的異常數據比例是β，計算能夠滿足下列不等式的b1極大值：

(13)

根據得到的b1值，對異常數據E1，E2，…，Eb1進行標記挖掘，Eb1+1，…，Ek屬于正常類別。

依據上述非噪音類別中心與數據標記，評估數據集P，評估具體流程如下：

1)讀取整個數據集P，當至數據集末端時，評估結束；相反，則對新數據Pi進行讀取，并利用該數據的極小值與極大值來標準化其高維混合屬性，通過歐幾里得距離公式，解得類別Ci(i∈(1，k))與數據Pi的間距d(P，Ci)，從而得到最近間距dmin(P，C)與類別Cj；

2)當間距最小值大于已知聚類半徑R/2時，判定數據Pi屬于異常數據，重新對新的數據進行讀取；

3)若間距最小值不足聚類半徑，則把該數據標記為Ej，并重新對其進行異常判定。

4 實驗分析

4.1 實驗環境

為了驗證基于K-Means聚類算法的高維混合屬性數據挖掘方法在實際應用中的性能，通過my eclipse6.0編程環境與JAVA語言軟件得以實現，實驗采用windows XP操作系統，3.6GHz處理器，內存為24GB，實驗數據對象從UCI Knowledge Discovery Archive database中隨機抽取，所得數據信息如下表所示。

表1 仿真數據信息統計表

根據選取的數據集，對高維混合屬性數據進行樣本采集，結果如圖1所示。

圖1 樣本采集

通過高維混合屬性數據樣本采集，利用評估指標F-measure進行說明，根據多層次分布式方法、FFD方法與本文方法的聚類結果，求解對應的F-measure值，數據相似度與該指標呈正相關。假設各方法的聚類結果分別是Cq與Cp以及Cg，且相應的任意聚簇為Ui、Uj與Ul，nijl=|Ui∩Uj∩Ul|，數據集樣本個數是|T|，則本文方法的F-measure指標計算公式分別為：

F(Cg)=

(14)

4.2 實驗結果對比分析

聚類DS1與DS2數據集，對多層次分布式方法、FFD方法與本文方法的高維混合屬性數據DS1聚類和DS2聚類結果進行對比分析，對比結果如圖2、圖3所示。

根據圖2的數據可以看出，多層次分布式方法與FFD方法在處理屬性數量較少的數據集時，聚類效果相對較好，但仍遠不及本文方法的聚類效果與穩定性。

根據圖3中曲線走勢可以看出，多層次分布式方法與FFD方法的高維混合屬性數據聚類結果較本文方法的高維混合屬性數據聚類結果差，是因為本文方法加入最大距離自動生成k值策略與坐標旋轉策略，在短時間就發揮出極佳的性能，獲取最優的聚類結果。

聚類效果會直接影響數據的挖掘結果，采用多層次分布式方法、FFD方法與本文方法挖掘高維混合屬性數據，將挖掘結果與實際的挖掘結果進行誤差對比，對比結果如圖4所示。

圖2 DS1聚類對比

圖3 DS2聚類結果對比

圖4 三種方法的挖掘誤差對比

根據圖4可知，本文方法挖掘到的高維混合屬性數據量與實際挖掘到的高維混合屬性數據量誤差較小，而多層次分布式方法和FFD方法挖掘到的高維混合屬性數據量與實際挖掘到的高維混合屬性數據量誤差較大，說明本文方法的挖掘效果好，是因為本文方法通過降序排列類別異常因子，大幅度降低挖掘誤差，聚類挖掘性能優勢顯著。

5 結論

隨著信息技術的自然演化，數據挖掘技術開始出現并飛速發展。早期的數據采集與數據庫架構階段，只能夠處理存儲、查詢、檢索等簡易操作，后期便擴展至關系數據庫系統的建立，提升了應用靈活性，當數據庫內出現了知識發現時，數據挖掘技術才引起關注并日益普及。本文針對高維混合屬性數據，采用K-means聚類算法，研究一種新的數據挖掘方法，因為數據知識挖掘是一種非單調的邏輯歸納過程，有可能與初始知識存在沖突，所以，今后應在挖掘方法的遞增性方面展開研究。該方法具有廣闊的應用前景與發展空間，為后續的相關研究提出了指導性的建議。