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

王 琢，荀亞玲，張繼福

(太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

?

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

王 琢，荀亞玲，張繼福

(太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 算法描述

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

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

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

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

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

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

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

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

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

2.2 相似性度量的定義

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

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

(1)

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

2.3 聚類結(jié)果的顯示

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

2.4 算法描述

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

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

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

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

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

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

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

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

圖1 支持度閾值變化的實(shí)驗(yàn)結(jié)果(最小置信度=0.2)

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

圖2 置信度閾值變化的實(shí)驗(yàn)結(jié)果(最小支持度=0.5)

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

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

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

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

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

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

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

3.2.1 K值對聚類的影響

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

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

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

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

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

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

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

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

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

表5 不同、β取值的聚類結(jié)果(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的關(guān)聯(lián)規(guī)則算法和基于密度的聚類關(guān)聯(lián)規(guī)則算法DBSCAN對相同蘑菇關(guān)聯(lián)規(guī)則的聚類時(shí)間(ms)進(jìn)行對比，如表6所示。

表6 聚類運(yùn)行時(shí)間(ms)

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

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

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

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

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

[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ù)平臺(tái) hadoop 的聚類算法K值優(yōu)化研究[J].太原科技大學(xué)學(xué)報(bào),2015,36(2):92-96.

[8] HAN J, KAMBER M,數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰,譯.北京：機(jī)械工業(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] 韋素云,吉根林,曲維光.關(guān)聯(lián)規(guī)則的冗余刪除與聚類[J].小型微型計(jì)算機(jī)系統(tǒng), 2006,27(1):110-113.

[14] 張愛芳.基于密度網(wǎng)格的關(guān)聯(lián)規(guī)則開采及聚類算法[D].華中科技大學(xué),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ù)相關(guān)性分析方法[J].模式識(shí)別與人工智能,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-)，女，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘與知識(shí)工程；通信作者：張繼福教授，E-mail:jifuzh@sina.com

TP391

A

10.3969/j.issn.1673-2057.2016.06.003