基于K-Means聚類算法的HDMA數(shù)據(jù)挖掘方法

耿德志，徐 乾

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

1 引言

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

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

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

2 高維混合屬性數(shù)據(jù)相似度分析

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

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

(1)

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

所以，下列為數(shù)據(jù)Xi與簇Uj的相似度界定式

(2)

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

(3)

其中，Cj內(nèi)的數(shù)據(jù)數(shù)量是|Cj|。

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

(4)

(5)

若將分類型數(shù)據(jù)Xi與分類型簇A的相似度認(rèn)為是數(shù)據(jù)與其它數(shù)據(jù)的相似度均值，則下列公式為其相似度界定表達(dá)式

(6)

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

(7)

將上述兩類型數(shù)據(jù)相似度度量形式作為高維混合屬性數(shù)據(jù)的度量標(biāo)準(zhǔn)，采用下列等式對(duì)其進(jìn)行描述

d(xi，Uj)=dn+wldc

(8)

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

(9)

(10)

3 K-Means聚類算法下高維混合屬性數(shù)據(jù)挖掘

3.1 K-Means聚類算法下數(shù)據(jù)聚類

3.1.1 K-means算法聚類流程

K-means聚類算法的核心理念是把簇中心點(diǎn)[6]設(shè)定為簇里點(diǎn)的平均數(shù)值或質(zhì)心[7]，采取持續(xù)迭代下降策略，完成數(shù)據(jù)集的聚類，作為一種簡(jiǎn)單的無(wú)監(jiān)督學(xué)習(xí)方法，該算法能夠基于無(wú)任意標(biāo)號(hào)的條件，對(duì)簇與簇中心點(diǎn)進(jìn)行自動(dòng)設(shè)置，所以，該方法被當(dāng)做挖掘工具廣泛應(yīng)用于工業(yè)、商業(yè)等諸多領(lǐng)域。

通過持續(xù)迭代計(jì)算數(shù)據(jù)對(duì)象聚類中心點(diǎn)的過程就是K-means聚類算法，其運(yùn)算流程描述如下：

1)從數(shù)據(jù)集X內(nèi)隨機(jī)選取數(shù)據(jù)對(duì)象，假設(shè)初始聚類中心為所選的k個(gè)數(shù)據(jù)對(duì)象，則初始聚類中心點(diǎn)分別是C1，C2，…，Ck，明確數(shù)據(jù)集所需劃分類別個(gè)數(shù)；

2)通過求取數(shù)據(jù)集的其余數(shù)據(jù)對(duì)象與k個(gè)初始中心點(diǎn)間距，完成各數(shù)據(jù)對(duì)象與最近類別的分類，進(jìn)而產(chǎn)生中心是k個(gè)初始中心點(diǎn)的類。若數(shù)據(jù)Xp與中心點(diǎn)Ci距離最近，則把數(shù)據(jù)Xp分類至Ci類別內(nèi)；

(11)

4)迭代上述兩個(gè)步驟，待計(jì)算后聚類中心點(diǎn)與計(jì)算前一致時(shí)，聚類收斂，迭代結(jié)束；

5)將聚類結(jié)果輸出。

3.1.2 最大距離自動(dòng)生成k值聚類優(yōu)化

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

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

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

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

3)在類別S11數(shù)據(jù)與S1的所有間距中得到最遠(yuǎn)距離d11，同理可得類別S12中數(shù)據(jù)與S2的最大間距d21，將兩個(gè)最大間距中的較大距離設(shè)定成d1，那么，其相應(yīng)數(shù)據(jù)則是S3；

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

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

3.1.3 坐標(biāo)旋轉(zhuǎn)聚類優(yōu)化

為了防止出現(xiàn)局部最優(yōu)解問題，可利用坐標(biāo)旋轉(zhuǎn)方法獲取初始中心點(diǎn)，穩(wěn)定聚類結(jié)果，其計(jì)算流程如下：

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

2)若數(shù)據(jù)A和B是DM對(duì)應(yīng)數(shù)據(jù)，則對(duì)該數(shù)據(jù)間的中心點(diǎn)坐標(biāo)C及其半徑R/2進(jìn)行計(jì)算；

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

4)當(dāng)聚類中心點(diǎn)數(shù)量與k值相等時(shí)，進(jìn)行下一步；當(dāng)不足k值時(shí)，將起始參照點(diǎn)設(shè)定為點(diǎn)D，返回第三步，待滿足k值后結(jié)束；

5)初始中心點(diǎn)為k個(gè)聚類中心點(diǎn)，利用歐幾里得距離公式與K-means算法，聚類劃分?jǐn)?shù)據(jù)集X。

坐標(biāo)轉(zhuǎn)換過程的基點(diǎn)是最大距離，通過旋轉(zhuǎn)坐標(biāo)使初始聚類中心不再進(jìn)行隨機(jī)選擇，從而實(shí)現(xiàn)聚類中心點(diǎn)散布于各類別里，防止發(fā)生類別中沒有中心點(diǎn)或者超出一個(gè)中心點(diǎn)的情況。

3.2 數(shù)據(jù)挖掘?qū)崿F(xiàn)

利用降噪處理所得的聚類結(jié)果進(jìn)行異常標(biāo)記。假設(shè)類別C里的元素?cái)?shù)量比已知的noise count少，則其屬于噪音類別；采用下列公式界定類別集合C={C1，C2，…，Ck}中的各類別類異常因子[8-10]

(12)

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

(13)

根據(jù)得到的b1值，對(duì)異常數(shù)據(jù)E1，E2，…，Eb1進(jìn)行標(biāo)記挖掘，Eb1+1，…，Ek屬于正常類別。

依據(jù)上述非噪音類別中心與數(shù)據(jù)標(biāo)記，評(píng)估數(shù)據(jù)集P，評(píng)估具體流程如下：

1)讀取整個(gè)數(shù)據(jù)集P，當(dāng)至數(shù)據(jù)集末端時(shí)，評(píng)估結(jié)束；相反，則對(duì)新數(shù)據(jù)Pi進(jìn)行讀取，并利用該數(shù)據(jù)的極小值與極大值來(lái)標(biāo)準(zhǔn)化其高維混合屬性，通過歐幾里得距離公式，解得類別Ci(i∈(1，k))與數(shù)據(jù)Pi的間距d(P，Ci)，從而得到最近間距dmin(P，C)與類別Cj；

2)當(dāng)間距最小值大于已知聚類半徑R/2時(shí)，判定數(shù)據(jù)Pi屬于異常數(shù)據(jù)，重新對(duì)新的數(shù)據(jù)進(jìn)行讀?。?/p>

3)若間距最小值不足聚類半徑，則把該數(shù)據(jù)標(biāo)記為Ej，并重新對(duì)其進(jìn)行異常判定。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境

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

表1 仿真數(shù)據(jù)信息統(tǒng)計(jì)表

根據(jù)選取的數(shù)據(jù)集，對(duì)高維混合屬性數(shù)據(jù)進(jìn)行樣本采集，結(jié)果如圖1所示。

圖1 樣本采集

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

F(Cg)=

(14)

4.2 實(shí)驗(yàn)結(jié)果對(duì)比分析

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

根據(jù)圖2的數(shù)據(jù)可以看出，多層次分布式方法與FFD方法在處理屬性數(shù)量較少的數(shù)據(jù)集時(shí)，聚類效果相對(duì)較好，但仍遠(yuǎn)不及本文方法的聚類效果與穩(wěn)定性。

根據(jù)圖3中曲線走勢(shì)可以看出，多層次分布式方法與FFD方法的高維混合屬性數(shù)據(jù)聚類結(jié)果較本文方法的高維混合屬性數(shù)據(jù)聚類結(jié)果差，是因?yàn)楸疚姆椒尤胱畲缶嚯x自動(dòng)生成k值策略與坐標(biāo)旋轉(zhuǎn)策略，在短時(shí)間就發(fā)揮出極佳的性能，獲取最優(yōu)的聚類結(jié)果。

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

圖2 DS1聚類對(duì)比

圖3 DS2聚類結(jié)果對(duì)比

圖4 三種方法的挖掘誤差對(duì)比

根據(jù)圖4可知，本文方法挖掘到的高維混合屬性數(shù)據(jù)量與實(shí)際挖掘到的高維混合屬性數(shù)據(jù)量誤差較小，而多層次分布式方法和FFD方法挖掘到的高維混合屬性數(shù)據(jù)量與實(shí)際挖掘到的高維混合屬性數(shù)據(jù)量誤差較大，說明本文方法的挖掘效果好，是因?yàn)楸疚姆椒ㄍㄟ^降序排列類別異常因子，大幅度降低挖掘誤差，聚類挖掘性能優(yōu)勢(shì)顯著。

5 結(jié)論

隨著信息技術(shù)的自然演化，數(shù)據(jù)挖掘技術(shù)開始出現(xiàn)并飛速發(fā)展。早期的數(shù)據(jù)采集與數(shù)據(jù)庫(kù)架構(gòu)階段，只能夠處理存儲(chǔ)、查詢、檢索等簡(jiǎn)易操作，后期便擴(kuò)展至關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的建立，提升了應(yīng)用靈活性，當(dāng)數(shù)據(jù)庫(kù)內(nèi)出現(xiàn)了知識(shí)發(fā)現(xiàn)時(shí)，數(shù)據(jù)挖掘技術(shù)才引起關(guān)注并日益普及。本文針對(duì)高維混合屬性數(shù)據(jù)，采用K-means聚類算法，研究一種新的數(shù)據(jù)挖掘方法，因?yàn)閿?shù)據(jù)知識(shí)挖掘是一種非單調(diào)的邏輯歸納過程，有可能與初始知識(shí)存在沖突，所以，今后應(yīng)在挖掘方法的遞增性方面展開研究。該方法具有廣闊的應(yīng)用前景與發(fā)展空間，為后續(xù)的相關(guān)研究提出了指導(dǎo)性的建議。