基于聚類的關聯規則后處理算法研究

艾云昊，楊超宇，李慧宗

(安徽理工大學，安徽 淮南 232001)

關聯規則是數據挖掘的重要技術之一，它的簡明性和集成性使其在數據挖掘領域得到廣泛應用。關聯規則通常用于挖掘大量數據中各個數據項之間有價值的隱藏信息。然而關聯規則挖掘會產生大量的關聯規則，手動對規則進行探索根本不可行，這使得用戶分析和利用這些規則變得十分困難。并且，跟規則總數相比，用戶感興趣的規則數量太小，此時，用戶不得不利用更多的數據處理手段去找到他們感興趣的規則。

很多學者提出了可以使規則數量降低的研究方法，例如李廣原等[1]提出基于約束的關聯規則挖掘算法MACL，陸鑫赟等[2]提出一種基于刪除冗余規則的FUI_DK算法。除了基于約束條件的挖掘和刪除冗余規則這兩種方法，聚類算法也被大量應用在關聯規則的后處理中。阮備軍等[3]提出基于商品分類信息的關聯規則聚類，先根據分類樹定義項與項、項集與項集之間的聚類，然后使用OPTICS聚類算法處理關聯規則，最終產生能夠描述總體情況、便于分析觀察的聚類結構。郭鵬等[4]基于K-Means和關聯算法對學生的成績進行挖掘，通過基于樣本分布密度的初始聚類中心優化改進k-Means算法，然后使用K-Means算法對規則進行聚類，提高挖掘質量。張玲玲等[5]對關聯規則使用DBSCAN算法進行聚類分析，然后將聚類后的規則和領域知識進行分析，達到篩選出較高價值規則的目的。可以看出，基于約束條件的挖掘和刪除冗余規則這兩種方法都是運用在關聯規則算法運行過程中，聚類算法是用在處理關聯規則算法運行結束后得到的關聯規則。

聚類算法作為一種常用的關聯規則后處理算法，在實際應用中被廣泛使用。但是大多數研究者都僅僅使用一種聚類算法來做研究，沒有對比不同聚類算法對規則的聚類效果。目前主流的聚類算法分為三種類型：基于劃分的聚類算法、基于密度的聚類算法、層次聚類算法。本文分別選用三種類型中的K-Medoids、AGNES、OPTICS算法處理同一組關聯規則，并對比分析聚類結果。

1 基于聚類的關聯規則后處理算法

1.1 距離定義

聚類算法在聚類過程中需要通過考慮樣本的特征測量出一個樣本與其他樣本之間的相似程度，最終將相似度較高的對象分進同一個組。一般采用計算樣本間的距離來表示不同樣本之間的相似性度量。樣本之間的距離越小，說明樣本之間的相似度越高。距離的計算方法選取十分重要，會直接影響聚類的結果。歐式距離作為最常用的距離計算方法之一，具有較強的代表性，所以本文以歐式距離為例，使用歐式距離計算規則之間的距離。

歐式距離可以簡單的看成多維空間的點與點之間的幾何距離，設N個樣本組成集合X=(X1,X2,…,XN)，若樣本Xi∈X和Xj∈X，則樣本Xi和Xj樣本之間的距離定義為公式(1)。

(1)

1.2 規則之間的距離

由于規則是由各個事務組成，這些事務并不是數值型，所以不能直接用來計算歐式距離。在計算距離時需要對規則做一些處理，具體步驟如下。

(1)設有規則集合X=(X1,X2,…,XN)，規則Xi、Xj∈X，Xi=(a,b,c,d)，Xj=(c,d,f,g)。

(2) 列出兩條規則內所有的事務項。Xi∪Xj=(a,b,c,d,f,g)。

(3)計算事務項在兩條規則中出現的頻率。Xi:(a1,b1,c1,d1,f0,g0)，Xi:(a0,b0,c1,d1,f1,g1)。

(4)寫出規則頻率向量。Xi:(1,1,1,1,0,0)，Xi:(0,0,1,1,1,1)。

然后將規則頻率向量代入歐式距離的計算公式中即可。

1.3 三種聚類算法

1.3.1 K-Medoids聚類算法

K-Medoids算法由Kaufman于1990年首次提出，是基于劃分的聚類算法的代表之一，可以看作是對K-Means算法的優化和改進，這兩種算法的基本思想是相同的。K-Medoids算法并沒有像K-Means一樣將當前類中的平均值作為下一個參考點，而是選取當前類中存在的一點，計算出當前類中所有其他點到該點的最小距離之和。并且K-Means算法對數據要求較高，要求所有的數據樣本均為數值型，無法處理非數值型的數據，而K-Medoids算法則對數據沒有太多要求，且在一定程度上削弱了異常值的影響，在處理少量數據時表現較好。

具體的算法流程如下。

輸入：簇類的數目K，樣本集X。

輸出：K個簇類。

(1)在樣本集X中隨機選取K個樣本作為質心；

(2)按照與質心最近的原則，將樣本集X中剩余的點分配到當前最佳的質心代表的類中；

(3)對于第個類中除對應質心點外的所有其他點，按順序計算當其為新的質心時，準則函數的值，遍歷所有可能，選取準則函數最小時對應的點作為新的質心；

(4)重復(2)(3)的過程，直到所有的質心點不再發生變化或已達到設定的最大迭代次數；

(5)產出最終確定的K個類。

1.3.2 Agnes算法

AGNES(AGglomerative NESting)算法[6]是凝聚的層次聚類算法，采用“自底向上”的聚合策略。“自底向上”聚合策略就是一開始每個個體都是一個類，然后根據Linkage尋找同類，最后形成一個“類”。本文選用的Linkage方法是平均連接距離法，因為相對最短距離法和最長距離法等其他Linkage方法，平均連接距離法具有更好的單調性且空間擴張/濃縮的程度適中，在實際應用中被使用的也更為廣泛。

平均連接距離法(Average Linkage)：

設有X、Y兩個類，X與Y之間的距離為X中所有點和Y中所有點之間的距離的平均值，點與點之間的距離本文采用歐氏距離計算，可表示為公式(2)。|X|和|Y|分別表示X與Y類中點的個數。

(2)

AGNES聚類的流程。

輸入：簇的數目K，樣本集X，Linkage方法。

輸出：K個簇類。

(1)將每個對象都作為一個初始類，計算兩兩之間的距離；

(2)將距離最小的兩個類合并成一個新類；

(3)重新計算新類與所有類之間的距離；

(4)重復(2)、(3)，直到所有類最后合并成一類。

1.3.3 OPTICS聚類算法

OPTICS(Ordering Points to Identify the Clustering Structure)是對DBSCAN(Density- Based Spatial Clustering of Applications with Noise)算法進行改進后的一種基于密度聚類的聚類算法[7]。該算法對鄰域半徑ε不再敏感，只需確定鄰域最小樣本數MinPts的值，半徑ε的輕微變化，并不會影響聚類結果。

相關定義如下：

ε領域，X為集合，對于xi∈X，其ε領域為X中與xi的距離不大于ε的子樣本集，ε領域本質上是一個集合，可記為Nε(xi)，集合的個數記為|Ng(xi)|；

核心對象，對任一樣本xi∈X，若其ε領域對應的Nε(xi)至少包含了MinPts個樣本，則xi是核心對象；

直接密度可達，樣本x,y∈X，x為核心對象，若y∈Nε(x)，則y從x直接密度可達；

核心距離，樣本x∈X，樣本點的核心距離是使得x其成為核心點的最小半徑，即是樣本點距離其第MinPts個最近的點的距離；

可達距離，對于樣本x點的鄰點x1,x2,…xn而言，如果他們到點x的距離大于核心距離，則其可達距離為該點到點x的實際距離；如果小于核心距離，則其可達距離就是點x的核心距離。

OPTICS算法處理關聯規則步驟。

輸入：樣本集X，鄰域半徑ε與MinPts。

輸出：具有可達距離信息的樣本點輸出排序。

(1)首先構建種子隊列Qseed和結果隊列Qorder，種子隊列用來存儲當前所有沒有被訪問過的樣本點的最小可達距離，結果隊列用來存儲樣本點的輸出次序；

(2)計算每個樣本點的核心距離，并根據核心距離與ε的關系得到核心點的隊列Qcore；

(3)任取一個核心點作為開始節點，將其標為以訪問并加入結果隊列Qorder，并將其可達距離記為其核心距離，可達距離隊列記為Qreachdist；

(4)計算其余各點相對起始節點的可達距離，并將未訪問過點的可達距離放入種子隊列中Qseed；

(5)循環執行下面操作，直到種子隊列Qseed為空，從Qseed中取出一個可達距離最小的樣本點q，將q標記訪問，并加入結果隊列，計算每個沒用訪問過點相對q的可達距離，如果距離變小則更新Qseed和Qreachdist，用小的可達距離代替大的可達距離；

(6)輸出標簽，遍歷樣本集，然后根據樣本的可達距離與ε的關系將樣本集劃分為多個類，然后輸出所有的類。

2 關聯規則評價與關聯規則后處理算法評價

2.1 關聯規則評價

(1)支持度

支持度表示x和y在總事務集合D中同時的出現的概率，如公式(3)所示。

(3)

(2)置信度

置信度表示的是包含x和y所有項的事務個數在包含前件所有項的事務總數x中的占比，也可用x∪y的支持度除以x的支持度，如公式(4)所示。

(4)

(3)確定性因子CF

確定性因子CF(A→B)[9]定義為公式(5)。

(5)

式中A→B為一條關聯規則，A為前件，B為后件，Conf(A→B)為前件為A后件為B的關聯規則的置信度，Supp(B)為關聯規則后件B的支持度。由式(1)可知，確定性因子會產生一個[-1，1]區間的值。當得知A包含在某個事務中，確定性因子可以度量B在那個事務中的可信度是如何變化的。正值表示可信度增加，負值意味著可信度下降，而0意味著可信度沒有變化。

(4)規則質量評價函數φ(r)

規則質量評價函數φ(r)[8]的定義為公式(6)。

(6)

式中r的為關聯規則，minSupp、minConf、minCF分別是最小支持度、最小置信度、最小確定性因子，由公式可以很明顯的看出φ(r)的值越大，表明規則的質量越好。

2.2 關聯規則后處理算法評價

本文將根據兩個指標評價關聯規則后處理算法：探索效率提升度、準確度。探索效率提升度就是用戶在探索規則時可以減少查看的規則的百分比，計算步驟為(1)利用規則質量評價函數φ(r)計算出所有規則的質量，然后根據規則質量對規則排序，選取質量最大的前百分之T個規則作為最佳規則集。T的大小由作者進行選定，本文將T選為1，也就是說最佳規則為質量排名前百分之一的規則；(2)使用聚類算法對關聯規則進行聚類；(3)在聚類過后的規則中找出最佳規則的位置，若最佳規則大部分都集中在m個類中，則探索效率提升度為總規則數減去m個類中的規則數后與總規則數的百分比。表示為(總規則數-m個簇中的規則數)/總規則數。其中m可被稱為最佳類數，大小由作者進行定義，本文定為不大于當前規則聚類得出的類個數的二分之一。準確度的計算方法為找出最佳類中包含的最佳規則的個數，然后將其除以最佳規則數就可得到準確度。

3 實驗

3.1 數據選取

本文隨機選取某電商平臺四天的訂單交易數據，使用Apriori算法對其進行挖掘，將挖掘出的關聯規則作為四個數據庫。Apriori算法在挖掘過程中的最小支持度、最小置信度和最小確定性因子這三個參數均憑經驗進行設置，旨在保證四個數據庫得到的規則數相近，不會因規則數量相差太大造成誤差。如表1所示。

表1 數據庫描述

該表第1列為數據庫序號，第2、3、4列分別為最小支持度、最小置信度和最小確定性因子，第5列為數據庫中的規則數目。

3.2 實驗結果與分析

本文采用探索效率提升度和準確度這兩個指標對三種基于不同聚類算法的關聯規則后處理算法進行評價，最終三種算法的探索效率提升度為表2，準確度為表3。從表2可以看出基于AGNES算法的關聯規則后處理算法在對數據庫2、3、4中表現比其他兩種算法更好，可以探索效率提升度更高，可以減少探索更多的規則。基于OPTICS算法的關聯規則后處理算法在數據庫1中表現最好，不過在其他三個數據庫中的表現相對來說就差一點，尤其是數據庫3，效率提升度只有25.0%。基于k-medoids算法的關聯規則后處理算法在四個數據庫中的表現都相對一般。

根據表3中顯示的準確度可以看出，基于k-medoids算法的關聯規則后處理算法擁有良好的效果，在數據庫1、3、4中的準確度可以達到100%，基于AGNES算法的關聯規則后處理算法表現也較為優秀，在數據庫3、4中的準確度達到了100%，在數據庫1、2中的準確度也超過80%。基于OPTICS算法的關聯規則后處理算法相對表現差一些，不過在數據庫2中的準確度也達到了100%。

根據探索效率提升度和準確度的性質，可知這兩個指標越高，說明聚類算法的聚類效果越好。基于AGNES算法的關聯規則后處理算法在數據庫3、4中的探索效率提升度和準確度都是三種算法中最高的，這說明基于AGNES算法的關聯規則后處理算法對數據庫3、4的聚類效果最好。基于k-medoids算法的關聯規則后處理算法在數據庫1中的準確度為100%，探索效率提升度為21.1%，這說明雖然在最佳個m類中找到了所有的最佳規則，但是最佳個m類包含了總規則的78.9%，相對來說并沒有減少太多不必要的規則，探索效率提升不大。基于OPTICS算法的關聯規則后處理算法在數據庫3中的表現也一樣，雖然準確度達到了88.9%，但是探索效率提升度為25.0%，效率提升不高。根據表2、3可以得出結論，基于AGNES算法的關聯規則后處理算法對關聯規則的處理效果最好。

表2 探索效率提升度

表3 準確度

結語

本文提出對使用關聯規則算法挖掘出的關聯規則結果進行二次挖掘，設計關聯規則后處理算法，探究基于不同聚類算法的關聯規則后處理算法對探索關聯規則結果的效率提升度和準確性。本文首先用關聯規則算法對數據進行挖掘，而后使用規則質量評價函數對規則進行評價并排序，再使用聚類算法對規則進行聚類，最后使用探索效率提升度和準確度兩個指標對關聯規則后處理算法進行評價。根據實驗結果可以看出，基于AGNES算法的關聯規則后處理算法總體表現最好，在擁有較高的探索效率提升度的同時還能具有較高的準確度，而其他兩種關聯規則后處理算法雖然相對來說效果較弱，但是也能較明顯的提高對關聯規則的探索效率。最終，我們可以得出結論，本文提出的關聯規則后處理算法確實可以減少冗余規則，提高探索有價值規則的效率。