基于改進的K-means算法的關聯規則數據挖掘研究

李 珺，劉 鶴，朱良寬

(東北林業大學，哈爾濱 150040)

1 引 言

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

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

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

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

2 基于改進的K-means算法關聯規則數據挖掘方法

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

2.1 數據預處理

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

圖1 數據預處理后的數據集部分數據Fig.1 Partial data of the data set after data preprocessing

2.2 冗余規則的刪除

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

2.2.1 相關性系數(Lift)

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

(1)

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

2.2.2 杠桿率(Leverage)

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

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

(2)

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

2.2.3 出錯率(Conviction)

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

(3)

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

(4)

出錯率越大表明規則預測錯誤的概率越大，這樣產生的規則有一定誤導性，即使滿足最小支持度和最小置信度也不能采用.

表1 X和Y的列聯表Table 1 X and Y contingencyTable

2.2.4 檢驗指標的權重分析

本文利用R軟件隨機產生的數據集對以上檢驗指標進行權重分析.表2為樣例數據集.

表2 樣例數據集Table 2 Sample dataset

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

表3 關聯規則的支持度、置信度和相關性系數的比較Table 3 Comparison of support，confidence and correlation coefficients of association rules

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

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

(5)

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

2.3 初始點的選擇

2.4 聚類過程及結果的顯示

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

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

1)先將得到的關聯規則按照置信度從高到低降序排列，選擇置信度高的前n條規則進行聚類(n可以根據產生的規則數目進行相應的調整)；

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

3 實驗結果與分析

3.1 冗余關聯規則的刪除

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

圖2 部分規則的支持度，置信度，3種檢驗指標及其權重指標Fig.2 Support，confidence，three test indicators and their weight indicators of some rules

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

從圖3和圖4中可以看出引入檢驗指標后能將冗余的關聯規則有效的刪除，并且當最小支持度和最小置信度的降低時，關聯規則數增多的情況下，還能有效刪除冗余的關聯規則.

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

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

為了能更好的衡量對冗余關聯規則刪除的效果，本文定義了一種衡量指標Dr.計算公式如下：

(6)

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

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

由圖5中Dr的數值比較可知，本文中刪除冗余關聯規則方法效果較好，因此本文的冗余關聯規則刪除方法是有效的.

3.2 關聯規則的聚類

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

表5 關聯規則Table 5 Association rules

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

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

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

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

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

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

3.3 運行效率的比較

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

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

4 結束語

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