王 琢，荀亞玲，張繼福

(太原科技大學計算機科學與技術學院，太原 030024)

?

一種基于K-means的關聯(lián)規(guī)則聚類算法

王 琢，荀亞玲，張繼福

(太原科技大學計算機科學與技術學院，太原 030024)

關聯(lián)規(guī)則是數(shù)據(jù)挖掘領域中的主要研究內(nèi)容之一。針對高維海量數(shù)據(jù)集，尤其當支持度和置信度閾值太低時，將生成大量冗余和相似的關聯(lián)規(guī)則，從而對關聯(lián)規(guī)則的理解和使用造成了困難。本文采用改進的K-means思想，給出了一種關聯(lián)規(guī)則聚類算法：首先重新定義了冗余關聯(lián)規(guī)則，并給出了刪除的方法；然后定義了一種新的規(guī)則間相似性度量；最后利用K-means思想，采用最大三角形方法選取聚類的初始點，將相似的關聯(lián)規(guī)則歸為一類。實驗驗證該算法能夠幫助用戶快速有效地找到有用的關聯(lián)規(guī)則，提高了關聯(lián)規(guī)則的可理解性。

關聯(lián)規(guī)則聚類算法；冗余關聯(lián)規(guī)則；相似性度量；恒星光譜數(shù)據(jù)

關聯(lián)規(guī)則挖掘[1]是尋找一個事物與其他事物之間的依賴性和關聯(lián)性，使其中一個事物通過其他事物得到預測的過程，并已廣泛應用在股票市場[2]、金融市場[3]、教學管理[4]、職業(yè)選擇[5]、臨床醫(yī)學[6]等方面。聚類分析師數(shù)據(jù)挖掘領域的一個熱門的研究分支[7]。聚類分析[8]，就是將物理或抽象對象的集合分成由類似的對象組成的多個類的過程。

對于海量高維數(shù)據(jù)集，傳統(tǒng)的關聯(lián)規(guī)則挖掘方法，往往會生成包括冗余和相似規(guī)則在內(nèi)的大量關聯(lián)規(guī)則，造成了關聯(lián)規(guī)則難以被理解的困境。刪除冗余規(guī)則和將相似規(guī)則聚類于一簇是有利于用戶分析和理解關聯(lián)規(guī)則的有效手段之一。

目前，刪除冗余關聯(lián)規(guī)則的方法主要有：在文獻[9]中，利用Galois連接提出了一種快速消除冗余的方法，并采用文獻[10]中meta-rule減少冗余的方法作為基準來判斷刪除效果。但需多次訪問閉規(guī)則集中出現(xiàn)的規(guī)則。在文獻[11]中，通過屬性前綴樹來挖掘無冗余的順序規(guī)則，但只適用于序列數(shù)據(jù)集。在文獻[12]中對冗余關聯(lián)規(guī)則進行定義：若一條規(guī)則包含其他規(guī)則，且置信度為100% ，那么這條規(guī)則就是冗余的。但是，置信度高的關聯(lián)規(guī)則往往是用戶所關心的，因此該定義存在問題。在文獻[13]中，定義冗余規(guī)則為一條規(guī)則能夠推出另一條規(guī)則，那么另一條規(guī)則是冗余的。并在此基礎上提出了冗余關聯(lián)規(guī)則刪除算法ADRR.

現(xiàn)有關聯(lián)規(guī)則的聚類方法主要采用的是：1)基于密度和網(wǎng)格的聚類方法：在文獻[13]中，提出了關聯(lián)規(guī)則聚類算法ACAR，同時結合基于密度的聚類算法DBSCAN的思想對關聯(lián)規(guī)則進行聚類，但對于規(guī)則間的距離定義過于粗糙。在文獻[14]中，通過將基于密度和基于網(wǎng)格的聚類方法結合，改善了基于密度聚類方法效率低的不足，但存在網(wǎng)格數(shù)量與內(nèi)存不匹配的情況。2)K-means聚類方法：在文獻[15]中提出了一種適用于關聯(lián)規(guī)則聚類的K-means改進算法，但該方法沒有考慮到關聯(lián)規(guī)則之間的關系。在文獻[16]中提出了基于最大三角形規(guī)則的K-means聚類算法，改善了K-means隨機選擇初始點的缺點。

綜上所述，現(xiàn)有關聯(lián)規(guī)則冗余刪除和聚類方法難以有效地提高關聯(lián)規(guī)則的可理解性。本文根據(jù)關聯(lián)規(guī)則中重復、多余的關聯(lián)規(guī)則特性(能被其他關聯(lián)規(guī)則完全包含)，對冗余關聯(lián)規(guī)則定義并刪除，有效地減少了冗余規(guī)則；對前件與后件的關系重新定義關聯(lián)規(guī)則間的相似性度量，結合K-means聚類的思想，對關聯(lián)規(guī)則進行聚類，將聚類簇中的相似規(guī)則選擇輸出，大量地減少了呈現(xiàn)給用戶的規(guī)則數(shù)目。兩個方法的結合有效地減少了無用信息對用戶的干擾，利于用戶快速發(fā)現(xiàn)關聯(lián)規(guī)則間的規(guī)律。

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

1.1 冗余關聯(lián)規(guī)則的定義

關聯(lián)規(guī)則是滿足最小支持度與最小置信度的形如X→Y的蘊含式。其中，X和Y分別稱為關聯(lián)規(guī)則的先導和后繼。由于適用于海量關聯(lián)規(guī)則集，且需在保留用戶所關心的規(guī)則上對重復、多余的規(guī)則進行刪除的情況下，本文重新對冗余規(guī)則進行定義并進行刪除處理。定義如下：

定義1：設有兩條關聯(lián)規(guī)則R1：X1→Y1(sup1，conf1)，R2：X2→Y2(sup2，conf2)，若X2?X1，且Y2?Y1，即R2R1或R2=R1，則R1能夠推出R2，那么R2是冗余的。

因為X2?X1，且Y2?Y1，則有sup1≤sup2、conf1≤conf2，那么R1必然能夠推出R2，R2是冗余的規(guī)則。比如，最小支持度0.5，最小置信度0.3，有兩條關聯(lián)規(guī)則R1：A，C→B，D(0.6，0.3)，R2：A→B(0.7，0.4)，可知R2R1，R1能夠推出R2，則R2是冗余的關聯(lián)規(guī)則。

由定義1可知，冗余關聯(lián)規(guī)則沒有固定某種數(shù)據(jù)集的限制，同時也避免了將用戶所需要的信息刪除的可能，從而能夠更有效地刪除真正重復、多余的關聯(lián)規(guī)則。

1.2 算法描述

在一個關聯(lián)規(guī)則R1中截取部分前件與部分后件重新構成一個關聯(lián)規(guī)則R2，如果R2存在，那么R2所表現(xiàn)的關聯(lián)模式完全可以用R1表現(xiàn)出來，則R2是冗余的。依據(jù)定義1，刪除冗余關聯(lián)規(guī)則見算法1.

算法1：刪除冗余的關聯(lián)規(guī)則

Input:File(全部的關聯(lián)規(guī)則)Output:File(無冗余的關聯(lián)規(guī)則)ForeveryLine in File FortempLine in otherLines IfeveryLine?tempLine (一條規(guī)則若被其他規(guī)則包含) ThenDelete everyLine(刪除這條規(guī)則) ElseiftempLine?everyLine Then Delete tempLine EndIf EndForEndFor

對關聯(lián)規(guī)則間的前件與后件進行相等判斷，若某條關聯(lián)規(guī)則被其他關聯(lián)規(guī)則完全包含，那么刪除該條關聯(lián)規(guī)則。該算法主要耗費時間部分為訪問文件中的n條關聯(lián)規(guī)則的兩個for循環(huán)，因此時間復雜度是T(n)=O(n2).

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

K-means方法是基于劃分式方法的一種聚類方法。它有線性的時間復雜度和線性的空間復雜度[17]。對大數(shù)據(jù)集有較高的效率，適合挖掘大規(guī)模數(shù)據(jù)集。但存在用戶定義K和隨機選擇初始點以及對于噪聲和離群點敏感的歐式距離定義[17]的缺陷。

本文針對K-means存在的缺陷，主要從兩個方面進行改進：初始點的選擇、相似性度量的定義。

2.1 初始點的選擇

傳統(tǒng)的K-means方法第一步是隨機選取任意的k個對象作為初始聚類的中心，對聚類結果具有較大的影響。在文獻[16]中，利用最大三角形方法來選取初始聚類中心，改善了K-means隨機選擇初始點的缺點，提高了聚類性能。參照文獻[16]，在關聯(lián)規(guī)則聚類中，其初始聚類中心選擇過程如下：從生成的一組關聯(lián)規(guī)則中，均勻隨機選擇k條關聯(lián)規(guī)則，選擇其中三個構造一個三角形，那么總共有C3k個三角形；計算一個區(qū)域內(nèi)的所有三角形的個數(shù)之和記作S，它們的周長之和記作L，最小邊記作Lens；如果θ*L/C3k≤ Lens(θ作為判斷因素，θ=0.133)，那么保留這組k條關聯(lián)規(guī)則集，同時保留S。若不滿足，則丟棄這組關聯(lián)規(guī)則集，并拋棄S.第四步，重復上面的過程Ts次，最大的S對應的k條關聯(lián)規(guī)則當作K-means的初始聚類中心。

2.2 相似性度量的定義

K-means算法是基于距離的聚類算法，根據(jù)距離大小衡量兩個對象之間的相似性，即距離越近，其相似度就越大。因此，距離的定義是影響聚類結果的主要因素。為了表示具有關聯(lián)規(guī)則性質(zhì)的聚類距離，可根據(jù)關聯(lián)規(guī)則中前件與后件之間的關系，來定義關聯(lián)規(guī)則的相似性度量。首先，采用Jaccard相似性系數(shù)形式來比較規(guī)則之間的相似度。其次，考慮規(guī)則前件與后件的重要性因素，引進兩個參數(shù)α和β來限定它們的重要程度。

定義2：設有兩條關聯(lián)規(guī)則R1：X1→Y1(sup1，conf1)，R2：X2→Y2(sup2，conf2)，設X1有m項，Y1有o項，X2有n項，Y2有p項，m，o，n，p≥0.R1和R2之間的相似性度量表示為：

(1)

在此定義中，規(guī)則間的距離由加權后的規(guī)則前件交集數(shù)與后件交集數(shù)的和與兩個規(guī)則總共項目數(shù)的比來度量。一般情況下，限定兩者權重之間的關系為α+β=1，考慮到規(guī)則前件對于規(guī)則間相似性度量影響更大，因此令α取值偏大，如=0.6，β=0.4或=0.7，β=0.3.

2.3 聚類結果的顯示

聚類后，會得到k(k為用戶自定義)個聚類簇。由海量數(shù)據(jù)生成的關聯(lián)規(guī)則，聚類后的結果依然很大，對于用戶仍舊很難去尋找有用信息?？紤]到置信度高的關聯(lián)規(guī)則往往是用戶所關心的，本文選擇對置信度高的規(guī)則部分輸出，以便于用戶分析規(guī)律。具體操作如下：第一步，在每個聚類簇中，按照該聚類簇中各關聯(lián)規(guī)則到簇中心的距離分為k個小類，其中，每個小類里的關聯(lián)規(guī)則條數(shù)不定。第二步，假設一個小類中有p條關聯(lián)規(guī)則。將這些關聯(lián)規(guī)則按照置信度從高到低排序，選擇置信度高的關聯(lián)規(guī)則q%條(q=[1，100]，q可以根據(jù)規(guī)則數(shù)目做相應的調(diào)整)進行顯示，那么這個聚類簇將會有p*q%*k條關聯(lián)規(guī)則顯示，很大程度上減少了關聯(lián)規(guī)則數(shù)量，同時將較重要的規(guī)則突出呈現(xiàn)給用戶，利于用戶快速地發(fā)現(xiàn)規(guī)律。

2.4 算法描述

本節(jié)對算法進行了詳細描述。聚類過程大致分為三個子過程：1)利用最大三角形方法選擇初始點：構造三角形，所構造的三角形個數(shù)和最大值對應的k條關聯(lián)規(guī)則作為初始聚類中心；2)計算關聯(lián)規(guī)則之間的距離并分類：定義關聯(lián)規(guī)則之間的相似性度量，并計算關聯(lián)規(guī)則與聚類中心的距離，再根據(jù)距離對關聯(lián)規(guī)則進行分配；3)判斷聚類是否收斂，重新分配關聯(lián)規(guī)則。

算法2：關聯(lián)規(guī)則的聚類

3 實驗結果及分析

實驗環(huán)境：Intel Core i5-4570，2GB內(nèi)存，Windows 7 64位操作系統(tǒng)，Microsoft Visual Studio 2010.實驗數(shù)據(jù)：(1)采用關聯(lián)規(guī)則挖掘數(shù)據(jù)集——蘑菇數(shù)據(jù)集，該數(shù)據(jù)集有8124個記錄，由蘑菇的顏色、氣味、形狀、生長環(huán)境、… 、類別等23個屬性組成，包含了蘑菇的127種不同屬性；(2)國家天文臺提供的SDSS恒星光譜數(shù)據(jù)，包含206維的8315條數(shù)據(jù)，前件是200個波長，后件包括6個物理化學性質(zhì)，參照文獻[18]對其離散化處理。

3.1 冗余關聯(lián)規(guī)則

為了檢驗冗余關聯(lián)規(guī)則的刪除效果，本文用蘑菇數(shù)據(jù)集做了兩組實驗。第一組實驗：分別對不同支持度、置信度時生成的關聯(lián)規(guī)則進行冗余刪除，結果如圖1、圖2所示。第二組實驗：設置最小支持度=0.5，最小置信度=0.7對蘑菇數(shù)據(jù)集生成的18條關聯(lián)規(guī)則進行冗余刪除，剩余12條關聯(lián)規(guī)則。如表1所示。

從圖1和圖2可以看出，該方法在不同最小支持度和不同最小置信度時都能夠?qū)﹃P聯(lián)規(guī)則集中的冗余有效地刪除，且隨著支持度和置信度的降低，關聯(lián)規(guī)則數(shù)增多的情況下，該方法依舊能夠達到很好的冗余刪除效果。

從表1中可以看出，按照定義1，冗余的關聯(lián)規(guī)則(10)～(13)、(16)、(17)相對于包含它的關聯(lián)規(guī)則(14)、(18)置信度更高，即這些規(guī)則可以被其他規(guī)則推出，那么將其刪除。從表1右側刪除后的關聯(lián)規(guī)則集中可以看出，該方法能夠有效的將原關聯(lián)規(guī)則中冗余的關聯(lián)規(guī)則刪除，減少無關信息對用戶的干擾。

圖1 支持度閾值變化的實驗結果(最小置信度=0.2)

Fig.1 Experimental results of the support threshold change (minimum confidence = 0.2)

圖2 置信度閾值變化的實驗結果(最小支持度=0.5)

Fig.2 Experimental results of the confidence threshold change (minimum support = 0.2)

采用文獻[11]中ratio，結合本文重新定義ratio=non-redundancy rules/rules(刪除冗余后的最終關聯(lián)規(guī)則數(shù)與總關聯(lián)規(guī)則數(shù)的比值)來衡量冗余關聯(lián)規(guī)則的刪除效果。若ratio越大，說明最終的無冗余關聯(lián)規(guī)則數(shù)越多，即刪除的冗余規(guī)則數(shù)量少，那么刪除效果差，反之，ratio越小，冗余規(guī)則的刪除效果越理想。將文獻[10]中的Meta-rule方法和文獻[11]中的Prefix-tree方法與本文方法進行冗余關聯(lián)規(guī)則的刪除效果對比，如表2所示。

表1 冗余關聯(lián)規(guī)則的刪除結果(最小支持度=0.5，最小置信度=0.7)

Tab.1 The results of deleting redundant association rules minimum support = 0.5, minimum confidence = 0.7)

表2 刪除冗余關聯(lián)規(guī)則

Meta-rule方法在定義冗余關聯(lián)規(guī)則中，假定后件一樣，當前件出現(xiàn)包含情況，定義被包含的規(guī)則為冗余規(guī)則，缺少了后件不同時候的情況。Prefix-tree中只考慮有相同的支持度與置信度時出現(xiàn)包含現(xiàn)象，被包含的關聯(lián)規(guī)則是冗余規(guī)則，卻忽略支持度與置信度不同時存在的冗余規(guī)則。從表2 ratio數(shù)值對比中可知，本文的方法每組ratio數(shù)值低，即刪除冗余規(guī)則的效果最理想，因此本文的刪除冗余關聯(lián)規(guī)則方法是有效的。

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

3.2.1 K值對聚類的影響

對蘑菇數(shù)據(jù)集采用最小支持度0.8、最小置信度0.2，生成76條關聯(lián)規(guī)則，刪除冗余規(guī)則后剩下14條關聯(lián)規(guī)則，用這14條關聯(lián)規(guī)則進行實驗，如表3所示。分別選取K=3，K=4，K=5時進行聚類(=0.6，β=0.4)，結果如表4所示。

聚類的目標是使每個聚類內(nèi)盡可能相似，聚類間盡可能區(qū)分。比較表4(a)、4(b)、4(c)，可以看出K值的變化對聚類的影響較小，每個聚類內(nèi)的趨勢大致相同。當K=4時的聚類結果最理想：每個聚類內(nèi)的規(guī)則間的前件具有共同的特征，且后件都一樣，聚類內(nèi)相似度高。對于不同聚類間的趨勢最大程度上不同。因此，K=4作為后續(xù)實驗的前提假設。

表3 關聯(lián)規(guī)則

表4(a) K=5的聚類結果

表4(b) K=4的聚類結果

表4(c)K=3的聚類結果

選取聚類個數(shù)K=4，針對、β不同情況：當=0.4，β=0.6；=0.5，β=0.5；=0.6，β=0.4；=0.7，β=0.3時，分別對刪除冗余后的蘑菇數(shù)據(jù)集進行聚類，如表5所示。

表5 不同、β取值的聚類結果(K=4)

Tab.5 The clustering result on different and β(K=4)

表5 不同、β取值的聚類結果(K=4)

a、β聚類規(guī)則集1聚類規(guī)則集2聚類規(guī)則集3聚類規(guī)則集4a=0.4,β=0.6(2)(6)(13)(8)(14)(7)(10)(12)(9)(11)(1)(3)(4)(5)a=0.5,β=0.5(2)(6)(7)(8)(10)(12)(9)(11)(13)(14)(1)(3)(4)(5)a=0.6,β=0.4(2)(6)(13)(7)(8)(10)(12)(14)(9)(11)(1)(3)(4)(5)a=0.7,β=0.3(13)(14)(7)(3)(10)(12)(9)(11)(1)(4)(5)(8)(2)(6)

3.2.3 聚類效率

通過與基于K-means的關聯(lián)規(guī)則算法和基于密度的聚類關聯(lián)規(guī)則算法DBSCAN對相同蘑菇關聯(lián)規(guī)則的聚類時間(ms)進行對比，如表6所示。

表6 聚類運行時間(ms)

對于傳統(tǒng)K-means對于龐大關聯(lián)規(guī)則集中隨機選取初始點的方法，本文采用在K條關聯(lián)規(guī)則構建的三角形中迭代選擇初始點，大量減少計算時間。DBSCAN算法主要處理低維數(shù)據(jù)，且復雜性高，面對高維數(shù)據(jù)時往往回導致維度災難，達到最差時間復雜度T(n)=O(n2)。從表6中可知在對相同數(shù)量的關聯(lián)規(guī)則進行聚類時，本文的聚類方法運行時間最短，因此，本文方法能夠有效地減少了聚類時間，提高了聚類效率。

3.3 恒星光譜數(shù)據(jù)

參照文獻[18]，由8315條恒星光譜數(shù)據(jù)，生成關聯(lián)規(guī)則74056條(最小支持度=1%，最小置信度=50%)，采用本文算法，刪除冗余關聯(lián)規(guī)則后，還剩有34774條；對其34774條關聯(lián)規(guī)則進行聚類，得到4個聚類簇。其聚類結果由表7(a)-(d)所示。

根據(jù)文獻[18]可知，恒星光譜數(shù)據(jù)前200個屬性為關聯(lián)規(guī)則前件，后6個屬性為關聯(lián)規(guī)則后件。從表7(a)可知：聚類1中當波4570、4970、5730、6290處窄、很強的時候往往伴隨著化學豐度4、5、微湍流2；從表7(b)可知：當波4930、5410處窄、弱；波5910、7170處特寬、一般、波6610處窄、一般的時候往往能夠得到溫度1屬性；從表7(c)得出：當波4390、4750、5110、7550處窄；波5910、7170特寬一般的時候推出溫度1或mh值1；從表7(d)得出：當波4010、4330、4890、5830處寬、較強時可獲得溫度6屬性。此聚類方法將海量關聯(lián)規(guī)則以聚類簇的方式清晰地將部分相似的關聯(lián)規(guī)則集顯示出來，能夠讓用戶快捷得獲取龐大數(shù)據(jù)內(nèi)所需的關聯(lián)信息，利于用戶理解并發(fā)現(xiàn)規(guī)律。

表7 (a) 恒星光譜數(shù)據(jù)聚類規(guī)則集1

表7 (b) 恒星光譜數(shù)據(jù)聚類規(guī)則集2

表7 (c) 恒星光譜數(shù)據(jù)聚類規(guī)則集3

表7 (d) 恒星光譜數(shù)據(jù)聚類規(guī)則集4

4 結束語

用戶面對大量的關聯(lián)規(guī)則，難以選擇有用信息。本文，采用改進的K-means聚類思想，給出了一種關聯(lián)規(guī)則聚類算法，有效地約簡了大量冗余關聯(lián)規(guī)則，并將相似的關聯(lián)規(guī)則歸為一簇。最后，采用SDSS恒星光譜數(shù)據(jù)以及人工數(shù)據(jù)集，實驗驗證了該算法的可行性和有效性。

[1] LIN J L, DUNHAM M H. Mining association rules: Anti-skew algorithms[C]//Data Engineering, 1998. Proceedings.14th International Conference on. IEEE, 1998: 486-493.

[2] KUO R J, CHAO C M, ChiuY T. Application of particle swarm optimization to association rule mining[J]. Applied Soft Computing, 2011, 11(1): 326-336.

[3] HO G T S, IP W H, WU C H, et al. Using a fuzzy association rule mining approach to identify the financial data association[J]. Expert Systems with Applications, 2012, 39(10): 9054-9063.

[4] WANG H, LIU P, LI H. Application of improved association rule algorithm in the courses management[C]//Software Engineering and Service Science (ICSESS), 2014 5th IEEE International Conference on. IEEE, 2014: 804-807.

[5] PERI H, KUMAR P. Application of association rule mining to help determine the process of career selection[J]. International Journal of Computer Application, 2014, 94(16): 15-19.

[6] SIMON G J, SCHROM J, CASTRO M R, et al. Survival association rule mining towards type 2 diabetes risk assessment[C]//AMIA Annual Symposium Proceedings. American Medical Informatics Association, 2013: 1293.

[7] 武霞,董增壽,孟曉燕. 基于大數(shù)據(jù)平臺 hadoop 的聚類算法K值優(yōu)化研究[J].太原科技大學學報,2015,36(2):92-96.

[8] HAN J, KAMBER M,數(shù)據(jù)挖掘概念與技術[M].范明,孟小峰,譯.北京：機械工業(yè)出版社2004.

[9] LIU H, LIU L, ZHANG H. A fast pruning redundant rule method using Galois connection[J]. Applied Soft Computing, 2011, 11(1): 130-137.

[10] BERRADO A, RUNGER G C. Using metarules to organize and group discovered association rules[J]. Data Mining and Knowledge Discovery, 2007, 14(3): 409-431.

[11] PHAM T T, LUO J, HONG T P, et al. An efficient method for mining non-redundant sequential rules using attributed prefix-trees[J]. Engineering Applications of Artificial Intelligence, 2014，32: 88-99.

[12] NGUYEN L T T, VO B, HONG T P, et al. Classification based on association rules: A lattice-based approach[J]. Expert Systems with Applications, 2012, 39(13): 11357-11366.

[13] 韋素云,吉根林,曲維光.關聯(lián)規(guī)則的冗余刪除與聚類[J].小型微型計算機系統(tǒng), 2006,27(1):110-113.

[14] 張愛芳.基于密度網(wǎng)格的關聯(lián)規(guī)則開采及聚類算法[D].華中科技大學,2004.

[15] LIU G, HUANG S, LU C, et al. An improved K-means Algorithm Based on Association Rules[J]. International Journal of Computer Theory and Engineering, 2014, 6(2): 146-150.

[16] FENG J, LU Z, YANG P, et al. A K-means clustering algorithm based on the maximum triangle rule[C]// Mechatronics and Automation (ICMA),2012 International Conference on. IEEE, 2012: 1456-1461.

[17] CELEBI M E, KINGRAVI H A, Vela P A. A comparative study of efficient initialization methods for the K-means clustering algorithm[J]. Expert Systems with Applications, 2013, 40(1): 200-210.

[18] 張繼福,趙旭俊.一種基于約束 FP樹的天體光譜數(shù)據(jù)相關性分析方法[J].模式識別與人工智能,2009(4): 639-646.

An Association Rule Clustering Algorithm Based on K-means

WANG Zhuo, XUN Ya-ling, ZHANG Ji-fu

(School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China)

Association rule is one of the main research contents in the filed of data mining. For mining the association rule on massive and high-dimensional data set, a large number of redundant and similar association rules will be generated if the support or confidence threshold is low, so that it will cause difficulties to understand and use the rules. In this paper，an association rule clustering algorithm is presented by using improved K-means idea, which improves the understandability of association rules. First, the redundant association rules is redefined, and a method of deleting the rules is presented. Second，a new similarity measure of the rules is defined according to the structure characteristics between antecedent and consequent of association rules. Third，by using largest triangle method to select the initial cluster points and the idea of K-means, a clustering algorithm of association rules is presented to analyze association rules after deleting redundant rules, and put them into one cluster, and let users find useful association rules quickly and efficiently. In the end, the experiments on celestial spectra data and simulated datasets verified the feasibility and effectiveness of the algorithm.

an association rule clustering algorithm, redundant association rules, similarity measurement, celestial spectra data

1673-2057(2016)06-0429-09

2015-11-09

王琢(1990-)，女，碩士研究生，研究方向為數(shù)據(jù)挖掘與知識工程；通信作者：張繼福教授，E-mail:jifuzh@sina.com

TP391

A

10.3969/j.issn.1673-2057.2016.06.003