李 珺，劉 鶴，朱良寬

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

1 引 言

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

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

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

為了能更迅速準(zhǔn)確的找出有價(jià)值的規(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個(gè)檢驗(yàn)指標(biāo)的方法對冗余的關(guān)聯(lián)規(guī)則進(jìn)行刪除;2)聚類之前要先對初始點(diǎn)進(jìn)行選擇，將產(chǎn)生的關(guān)聯(lián)規(guī)則利用最大三角形法通過迭代確定初始點(diǎn);3)用K-means算法對產(chǎn)生的規(guī)則進(jìn)行聚類.此方法能有效的刪除大量的冗余規(guī)則，將相似的關(guān)聯(lián)規(guī)則歸為一簇，提高聚類性能，節(jié)省運(yùn)行時(shí)間.

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

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

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

本文采用的數(shù)據(jù)是鳶尾花(iris)數(shù)據(jù)集，是一類多重變量分析的數(shù)據(jù)集.完整的鳶尾花(iris)數(shù)據(jù)集是一個(gè)150×5的矩陣.每一行代表一株鳶尾花，包含的屬性有萼片長度(Sepal.Length)，萼片寬度(Sepal.Width)，花瓣長度(Petal.Length)，花瓣寬度(Petal.Width)和該鳶尾花的類型(Species)共計(jì)5種屬性，其中前4種屬性都是以厘米計(jì)數(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顯示部分?jǐn)?shù)據(jù)如圖1所示.本文所用的R軟件為64位3.5.1版本，鳶尾花數(shù)據(jù)集可以在R軟件自帶的數(shù)據(jù)包中導(dǎo)入.

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

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

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

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

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

(1)

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

2.2.2 杠桿率(Leverage)

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

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

(2)

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

2.2.3 出錯(cuò)率(Conviction)

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

(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)也成立.由此可得出錯(cuò)率的計(jì)算公式如下：

(4)

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

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

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

本文利用R軟件隨機(jī)產(chǎn)生的數(shù)據(jù)集對以上檢驗(yàn)指標(biāo)進(jìn)行權(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ī)則的時(shí)候，必須要使用多個(gè)衡量指標(biāo)進(jìn)行評估.

表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ī)則杠桿率的一半，主要是因?yàn)锳C→E的支持度更大.因此僅考慮杠桿率很容易被誤導(dǎo)，原因是即使在支持度不同的情況下規(guī)則的相關(guān)性系數(shù)也有可能相同.第2條規(guī)則和第3條規(guī)則雖然相關(guān)性系數(shù)不同，但杠桿率卻相同.最后，通過比較第1、第2和第4條規(guī)則可知：他們的相關(guān)性系數(shù)相同，但杠桿率不同，實(shí)際上第4條規(guī)則A→E可能優(yōu)于前兩條規(guī)則，因?yàn)樗啙?，杠桿率也更高.

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

(5)

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

2.3 初始點(diǎn)的選擇

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

(6)

式中Dr表示衡量指標(biāo)，NumR表示刪除的冗余規(guī)則數(shù)，TR表示總規(guī)則數(shù).如果Dr的數(shù)值越大，表示刪除的冗余規(guī)則數(shù)量越多，說明刪除效果越好，反之，Dr的數(shù)值越小，冗余關(guān)聯(lián)規(guī)則刪除的效果越差.本文對鳶尾花數(shù)據(jù)集分別用兩種方法進(jìn)行了冗余關(guān)聯(lián)規(guī)則的刪除，本文利用韋素云文中所提的刪除冗余關(guān)聯(lián)規(guī)則的ADRR算法和本文的方法進(jìn)行冗余關(guān)聯(lián)規(guī)則的刪除，并對兩種方法的效果進(jìn)行對比，對比結(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ī)則進(jìn)行刪除后剩下11條規(guī)則，如表5所示.利用表5所示的規(guī)則進(jìn)行聚類分析，K值分別取K=2，K=3和K=4，結(jié)果如表6所示.

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

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

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

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

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

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

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

3.3 運(yùn)行效率的比較

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

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

4 結(jié)束語

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