基于改進的K-means算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘研究

李 珺，劉 鶴，朱良寬

(東北林業(yè)大學(xué)，哈爾濱 150040)

1 引 言

數(shù)據(jù)挖掘是從隨機的、不完全的大量數(shù)據(jù)中，找出隱藏在其中的有價值信息的過程[1，2].隨著時代的發(fā)展，能獲取到的信息越來越多，如何能利用有限的資源快速在大量的數(shù)據(jù)中找出有價值的信息是數(shù)據(jù)挖掘所面臨的挑戰(zhàn)[3].關(guān)聯(lián)規(guī)則和聚類分析是數(shù)據(jù)挖掘中兩個重要方法.

關(guān)聯(lián)規(guī)則分析尋找給定數(shù)據(jù)集中數(shù)據(jù)項之間隱藏的關(guān)聯(lián)關(guān)系，描述數(shù)據(jù)之間的密切程度，通過關(guān)聯(lián)規(guī)則可以發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)規(guī)則或者相關(guān)關(guān)系[4-6].關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法分為兩個步驟：首先從事物數(shù)據(jù)庫中挖掘出支持度不小于給定最小支持度的所有頻繁項集，即產(chǎn)生頻繁項集，然后從頻繁項集中挖掘出置信度不小于給定最小置信度的強關(guān)聯(lián)規(guī)則，即產(chǎn)生規(guī)則[7].

將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程被稱為聚類[8].由聚類所產(chǎn)生的簇是一組數(shù)據(jù)對象的合集，這些對象與同一個簇中的對象彼此相似，卻與其他簇中的對象相異[9].聚類分析是將對象分成多個子集的過程.聚類分析主要分為4個步驟：數(shù)據(jù)的預(yù)處理，衡量相似度的距離函數(shù)的定義，數(shù)據(jù)的聚類，輸出結(jié)果的評估[10].K-means算法是基于劃分的經(jīng)典聚類算法，其基本思想是在空間設(shè)置K個初始聚類中心，分別計算K個中心點到數(shù)據(jù)集中點的距離，如果滿足定義的距離最小閾值，則劃分新的類別，通過迭代的方法逐次更新聚類的初始中心點，直到初始中心點不再發(fā)生變化或者變化范圍很小，迭代結(jié)束[11，12].K-means算法中K值的選擇和初始聚類中心的選擇對聚類效果會產(chǎn)生很大影響.

為了能更迅速準(zhǔn)確的找出有價值的規(guī)則，提高關(guān)聯(lián)規(guī)則的理解性，本文提出一種方法將關(guān)聯(lián)規(guī)則Apriori算法和聚類分析中K-means算法相結(jié)合使用.1)將數(shù)據(jù)預(yù)處理完成之后，用Apriori算法產(chǎn)生關(guān)聯(lián)規(guī)則，利用本文建立的3個檢驗指標(biāo)的方法對冗余的關(guān)聯(lián)規(guī)則進行刪除;2)聚類之前要先對初始點進行選擇，將產(chǎn)生的關(guān)聯(lián)規(guī)則利用最大三角形法通過迭代確定初始點;3)用K-means算法對產(chǎn)生的規(guī)則進行聚類.此方法能有效的刪除大量的冗余規(guī)則，將相似的關(guān)聯(lián)規(guī)則歸為一簇，提高聚類性能，節(jié)省運行時間.

2 基于改進的K-means算法關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘方法

K-means算法是一種迭代求解的聚類分析算法，是基于劃分式方法的一種聚類方法，它有線性的時間復(fù)雜度和線性的空間復(fù)雜度[13].其步驟是隨機選取K個對象作為初始的聚類中心，然后計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心.在算法中，k是需要用戶提前設(shè)定的，它代表期望的種類數(shù)，但有時會不確定數(shù)據(jù)的種類數(shù)目，這種情況下會多次嘗試用不同的k值進行聚類，選取其中最符合的K值.K-means算法對大數(shù)據(jù)集有比較高的效率，但對于K的定義和初始點的選擇方面存在缺陷.

2.1 數(shù)據(jù)預(yù)處理

本文采用的數(shù)據(jù)是鳶尾花(iris)數(shù)據(jù)集，是一類多重變量分析的數(shù)據(jù)集.完整的鳶尾花(iris)數(shù)據(jù)集是一個150×5的矩陣.每一行代表一株鳶尾花，包含的屬性有萼片長度(Sepal.Length)，萼片寬度(Sepal.Width)，花瓣長度(Petal.Length)，花瓣寬度(Petal.Width)和該鳶尾花的類型(Species)共計5種屬性，其中前4種屬性都是以厘米計數(shù).鳶尾花類型屬性里的數(shù)據(jù)都是文本格式，為了后續(xù)的數(shù)據(jù)分析更加方便，本文選擇把種類中的字符型數(shù)據(jù)轉(zhuǎn)化成數(shù)值型數(shù)據(jù).由于本數(shù)據(jù)集中鳶尾花的種類只包含3種，所以在R軟件中，將setosa類型替換為1，將versicolor類型替換成2，將virginica類型替換成3.替換后的數(shù)據(jù)集由R軟件導(dǎo)出，用Excel顯示部分數(shù)據(jù)如圖1所示.本文所用的R軟件為64位3.5.1版本，鳶尾花數(shù)據(jù)集可以在R軟件自帶的數(shù)據(jù)包中導(dǎo)入.

圖1 數(shù)據(jù)預(yù)處理后的數(shù)據(jù)集部分數(shù)據(jù)Fig.1 Partial data of the data set after data preprocessing

2.2 冗余規(guī)則的刪除

關(guān)聯(lián)規(guī)則的產(chǎn)生是同時滿足最小支持度和最小置信度的形如X→Y的蘊涵式，其中X稱為關(guān)聯(lián)規(guī)則的前項，Y稱為關(guān)聯(lián)規(guī)則的后項.當(dāng)數(shù)據(jù)集較大時，會產(chǎn)生大量的關(guān)聯(lián)規(guī)則，這些規(guī)則中包含的冗余規(guī)則是具有誤導(dǎo)性的，不利于用戶進行后續(xù)的分析和決策.本文將引入3個關(guān)聯(lián)規(guī)則的檢驗指標(biāo)增加刪除冗余規(guī)則的條件，提高關(guān)聯(lián)規(guī)則的實用效率.

2.2.1 相關(guān)性系數(shù)(Lift)

相關(guān)性系數(shù)(Lift)是觀察到的X和Y的聯(lián)合概率與期望聯(lián)合概率的比值，前提是假設(shè)他們在統(tǒng)計上是獨立的.相關(guān)性系數(shù)是用來度量一條規(guī)則出乎意料的程度.相關(guān)性系數(shù)的計算公式如下：

(1)

相關(guān)性系數(shù)接近1表示一條規(guī)則的支持度期望是由其兩個分量的支撐的乘積決定的，即表示項集X和項集Y的出現(xiàn)是相互獨立的，X和Y之間相互不受影響，X和Y同時出現(xiàn)沒有意義；相關(guān)性系數(shù)小于1，則說明項集X和項集Y是互斥的，即X的出現(xiàn)降低了Y出現(xiàn)的概率；相關(guān)性系數(shù)大于1時，項集X的出現(xiàn)會帶動另一個頻繁項集Y的出現(xiàn).

2.2.2 杠桿率(Leverage)

杠桿率(Leverage)是用來衡量XY的聯(lián)合概率和期望聯(lián)合概率之間的差異，杠桿率的計算公式如下：

leverage(X→Y)=P(XY)-P(X)·P(Y)=rsup(XY)-rsup(X)·rsup(Y)

(2)

杠桿率表示了規(guī)則出乎意料程度的“絕對”度量，它和相關(guān)性系數(shù)同時使用.

2.2.3 出錯率(Conviction)

出錯率衡量了規(guī)則的期望錯誤數(shù)，表示X出現(xiàn)的時候Y不在同一事務(wù)中的次數(shù).因此，它是對關(guān)于后項的補集的規(guī)則強度的度量，出錯率的定義如下：

(3)

以上考慮的所有規(guī)則度量都只使用了X和Y的聯(lián)合分布.定義X′為X不出現(xiàn)在事務(wù)中的事，Y′也以此定義.表1中的列聯(lián)表中給出了4種可能的事件，分別對應(yīng)X和Y出現(xiàn)或者不出現(xiàn)的情況.從表1中可以觀察到P(X)=P(XY)+P(XY′)，這表示P(XY′)=P(X)-P(XY)，以及P(Y′)=1-P(Y)也成立.由此可得出錯率的計算公式如下：

(4)

出錯率越大表明規(guī)則預(yù)測錯誤的概率越大，這樣產(chǎn)生的規(guī)則有一定誤導(dǎo)性，即使?jié)M足最小支持度和最小置信度也不能采用.

表1 X和Y的列聯(lián)表Table 1 X and Y contingencyTable

2.2.4 檢驗指標(biāo)的權(quán)重分析

本文利用R軟件隨機產(chǎn)生的數(shù)據(jù)集對以上檢驗指標(biāo)進行權(quán)重分析.表2為樣例數(shù)據(jù)集.

表2 樣例數(shù)據(jù)集Table 2 Sample dataset

表3所示的3條規(guī)則及其支持度、置信度和相關(guān)性系數(shù).比較前兩條規(guī)則可以看出盡管前兩條規(guī)則的相關(guān)性系數(shù)相同并且都大于1，但提供了不同的信息.因其置信度為0.4，所以E→AC是一條弱規(guī)則，而E→AB不僅置信度更高，支持度也更大.比較第2條和第3條規(guī)則，盡管B→E的相關(guān)性系數(shù)為1，但是它的置信度和支持度都較高.說明在分析關(guān)聯(lián)規(guī)則的時候，必須要使用多個衡量指標(biāo)進行評估.

表3 關(guān)聯(lián)規(guī)則的支持度、置信度和相關(guān)性系數(shù)的比較Table 3 Comparison of support，confidence and correlation coefficients of association rules

表4中所示的4條規(guī)則及其支持度、相關(guān)性系數(shù)和杠桿率.從表中可以看出前兩條規(guī)則的相關(guān)性系數(shù)相同，但第1條規(guī)則的杠桿率僅為第2條規(guī)則杠桿率的一半，主要是因為AC→E的支持度更大.因此僅考慮杠桿率很容易被誤導(dǎo)，原因是即使在支持度不同的情況下規(guī)則的相關(guān)性系數(shù)也有可能相同.第2條規(guī)則和第3條規(guī)則雖然相關(guān)性系數(shù)不同，但杠桿率卻相同.最后，通過比較第1、第2和第4條規(guī)則可知：他們的相關(guān)性系數(shù)相同，但杠桿率不同，實際上第4條規(guī)則A→E可能優(yōu)于前兩條規(guī)則，因為它更簡潔，杠桿率也更高.

通過表3和表4可知在分析關(guān)聯(lián)規(guī)則的時候不能只靠單一的支持度和置信度對規(guī)則進行評估，要多個檢驗指標(biāo)對規(guī)則進行綜合衡量，表4說明當(dāng)相關(guān)性系數(shù)相同時，杠桿率更高的規(guī)則要優(yōu)于其他的規(guī)則.因此，定義相關(guān)性系數(shù)、杠桿率和出錯率的綜合權(quán)重分析指標(biāo)計算公式如下：

(5)

式中，conf(X→Y)代表的是當(dāng)事務(wù)X發(fā)生時事務(wù)Y也發(fā)生的置信度，sup(Y)表示事務(wù)Y發(fā)生時的支持度，sup(XY)表示事務(wù)XY同時發(fā)生時的支持度.

2.3 初始點的選擇

2.4 聚類過程及結(jié)果的顯示

聚類的過程分為3個部分.第1部分，利用最大三角形方法選擇初始點；第2部分，計算關(guān)聯(lián)規(guī)則之間的距離并分類；第3部分，判斷聚類是否收斂，重新分配關(guān)聯(lián)規(guī)則.

將關(guān)聯(lián)規(guī)則聚類后，會得到K個聚類簇，其中K為用戶自定義.由海量數(shù)據(jù)產(chǎn)生的關(guān)聯(lián)規(guī)則即使進行聚類后，結(jié)果依舊很龐大，很難從中快速找到符合用戶需求的規(guī)則.為了減少聚類時間，提高聚類效率，在產(chǎn)生關(guān)聯(lián)規(guī)則后按照用戶需求設(shè)置檢驗指標(biāo)，刪除冗余的規(guī)則，并將刪除冗余規(guī)則后的關(guān)聯(lián)規(guī)則進行聚類分析.具體步驟如下：

1)先將得到的關(guān)聯(lián)規(guī)則按照置信度從高到低降序排列，選擇置信度高的前n條規(guī)則進行聚類(n可以根據(jù)產(chǎn)生的規(guī)則數(shù)目進行相應(yīng)的調(diào)整)；

2)對n條規(guī)則進行聚類，在每類簇中各個關(guān)聯(lián)規(guī)則到簇中心的距離分為K個類.那么這個聚類簇中就有n*K條關(guān)聯(lián)規(guī)則被顯示出來，這樣能減少關(guān)聯(lián)規(guī)則的數(shù)量，便于用戶快速對規(guī)則進行分析，得到自己感興趣的結(jié)論.

3 實驗結(jié)果與分析

3.1 冗余關(guān)聯(lián)規(guī)則的刪除

由于引入了檢驗指標(biāo)對關(guān)聯(lián)規(guī)則進行刪除，本文用鳶尾花數(shù)據(jù)集進行驗證.圖2為部分規(guī)則的支持度，置信度，3種檢驗指標(biāo)及其權(quán)重指標(biāo).規(guī)則的出錯率普遍數(shù)值較大，而出錯率越大，表示規(guī)則進行預(yù)測時出錯的機率越大，所以進行權(quán)重分析時，要降低出錯率的影響，將比重放在相關(guān)性系數(shù)和杠桿率上.從圖2中可以看出，rule29的出錯率較大，但是綜合權(quán)重分析沒有受到出錯率的影響而變大反而非常低，這說明rule29是冗余規(guī)則，會被識別出來并進行刪除.rule19的出錯率很低，相關(guān)性系數(shù)達到3，并且綜合權(quán)重非常高，說明這條是一條強規(guī)則.

圖2 部分規(guī)則的支持度，置信度，3種檢驗指標(biāo)及其權(quán)重指標(biāo)Fig.2 Support，confidence，three test indicators and their weight indicators of some rules

本文用鳶尾花數(shù)據(jù)集進行兩組實驗，第1組實驗是保持最小支持度在0.2不變，改變最小置信度，對冗余關(guān)聯(lián)規(guī)則的刪除，結(jié)果如圖3所示；第2組是在最小置信度保持在0.4不變，通過改變最小支持度對比冗余關(guān)聯(lián)規(guī)則的刪除情況，結(jié)果如圖4所示.

從圖3和圖4中可以看出引入檢驗指標(biāo)后能將冗余的關(guān)聯(lián)規(guī)則有效的刪除，并且當(dāng)最小支持度和最小置信度的降低時，關(guān)聯(lián)規(guī)則數(shù)增多的情況下，還能有效刪除冗余的關(guān)聯(lián)規(guī)則.

圖3 最小置信度變化的實驗結(jié)果(最小支持度為0.2)Fig.3 Experimental results of minimum confidence change (Minimum support is 0.2)

圖4 最小支持度變化的實驗結(jié)果(最小置信度為0.4)Fig.4 Experimental results of minimum support change (Minimum confidence is 0.4)

為了能更好的衡量對冗余關(guān)聯(lián)規(guī)則刪除的效果，本文定義了一種衡量指標(biāo)Dr.計算公式如下：

(6)

式中Dr表示衡量指標(biāo)，NumR表示刪除的冗余規(guī)則數(shù)，TR表示總規(guī)則數(shù).如果Dr的數(shù)值越大，表示刪除的冗余規(guī)則數(shù)量越多，說明刪除效果越好，反之，Dr的數(shù)值越小，冗余關(guān)聯(lián)規(guī)則刪除的效果越差.本文對鳶尾花數(shù)據(jù)集分別用兩種方法進行了冗余關(guān)聯(lián)規(guī)則的刪除，本文利用韋素云文中所提的刪除冗余關(guān)聯(lián)規(guī)則的ADRR算法和本文的方法進行冗余關(guān)聯(lián)規(guī)則的刪除，并對兩種方法的效果進行對比，對比結(jié)果如圖5所示.

圖5 兩種方法刪除效果的對比Fig.5 Comparison of the deletion effect of the two methods

由圖5中Dr的數(shù)值比較可知，本文中刪除冗余關(guān)聯(lián)規(guī)則方法效果較好，因此本文的冗余關(guān)聯(lián)規(guī)則刪除方法是有效的.

3.2 關(guān)聯(lián)規(guī)則的聚類

將鳶尾花數(shù)據(jù)集按照最小支持度為0.25，最小置信度為0.8挖掘關(guān)聯(lián)規(guī)則，產(chǎn)生了40條規(guī)則，對冗余規(guī)則進行刪除后剩下11條規(guī)則，如表5所示.利用表5所示的規(guī)則進行聚類分析，K值分別取K=2，K=3和K=4，結(jié)果如表6所示.

表5 關(guān)聯(lián)規(guī)則Table 5 Association rules

聚類是將數(shù)據(jù)分類到不同的類或者簇的過程，所以同一個簇中的對象有很大的相似性而不同簇之間的差異性非常大.通過比較表6(a)，表6(b)和表6(c)，可以看出K值的變化對聚類的影響較小，每個簇內(nèi)的趨勢大致相同.當(dāng)K=3的時候聚類效果最好，每個簇內(nèi)的規(guī)則間前項都具有共同的特征，且后項相同，簇內(nèi)的相似性高，不同簇之間的趨勢不同.

因為聚類效果最好的是K=3，從分類上可以看出，聚類規(guī)則集1的規(guī)則都是通過鳶尾花的萼片或者花瓣的長度和寬度來預(yù)測鳶尾花的種類；聚類規(guī)則集2和3都是鳶尾花萼片和花瓣長寬度之間的關(guān)系，而這些規(guī)則對鳶尾花沒有實際意義，用戶可以直接將聚類規(guī)則集進行刪除.用戶在得到聚類規(guī)則集時，容易通過聚類規(guī)則集內(nèi)的規(guī)則找出規(guī)則之間的共同點，快速得到有價值的結(jié)論，對無意義或者不感興趣的規(guī)則直接進行刪除.

表6(a) K=2時聚類分析結(jié)果Table 6(a) Cluster analysis results at K=2

表6(b) K=3時聚類分析結(jié)果Table 6(b) Cluster analysis results at K=3

表6(c) K=4時聚類分析結(jié)果Table 6(c) Cluster analysis results at K=4

相較于傳統(tǒng)的K-means對比較大的數(shù)據(jù)集采用的隨機選取初始點的方法，本文采用了在K條關(guān)聯(lián)規(guī)則構(gòu)建的三角形中迭代選擇初始點的方法，在很大程度上減少了聚類運行時間.由圖6可以綜合看出本文方法能有效的刪除冗余關(guān)聯(lián)規(guī)則，并且本文方法的運行時間比ADRR算法的運行時間短，因此，本文方法能有效的減少運行時間，提高聚類效率.

3.3 運行效率的比較

在最小支持度不同的情況下，用鳶尾花數(shù)據(jù)集分別用本文方法和ADRR算法對數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則并進行聚類分析，對兩種方法刪除冗余后規(guī)則數(shù)以及運行時間進行比較，比較結(jié)果如圖6所示.

圖6 兩種方法運行效率的比較Fig.6 Comparison of operating efficiency of the two methods

4 結(jié)束語

當(dāng)數(shù)據(jù)集比較龐大的時候，產(chǎn)生的關(guān)聯(lián)規(guī)則數(shù)比較多，用戶很難在短時間內(nèi)在大量的規(guī)則中找出符合條件且感興趣的規(guī)則，本文引入了3個檢驗指標(biāo)，可以精確的將冗余的規(guī)則刪除，并對刪除后的關(guān)聯(lián)規(guī)則進行聚類分析，將相似的規(guī)則歸為同一簇，這樣用戶通過查看每一簇中的規(guī)則就能快速的找到自己感興趣的規(guī)則并且針對簇內(nèi)的規(guī)則得出規(guī)律.本文利用產(chǎn)生的關(guān)聯(lián)規(guī)則構(gòu)建三角形，進行迭代選擇聚類的初始點，極大的減少了聚類的運行時間，提高了聚類的效率.通過對鳶尾花數(shù)據(jù)集進行的關(guān)聯(lián)規(guī)則分析，證明本文對冗余關(guān)聯(lián)規(guī)則的刪除和對相似規(guī)則進行聚類方法的有效性和可行性.