一種新的關聯規則挖掘算法研究

收稿日期：2007-11-27；修回日期：2008-03-20

基金項目：國家自然科學基金資助項目(30472122)

作者簡介：韋玉科（1965-），女，副教授，碩導，博士研究生，主要研究方向為智能信息處理、智能控制與檢測（weiyuke@gdut.edu.cn）；汪仁煌（1945-），男，教授，博導，主要研究方向為計算機測控技術、信息處理與智能儀器；李江平（1964-），男，副教授，碩導，博士研究生，主要研究方向為模式識別與圖像處理技術；陳群(1954-)，女，教授，博導，主要研究方向為中醫診斷學.*

（1. 廣東工業大學 a.自動化學院；b.計算機學院，廣州 510640；2.廣州中醫藥大學 基礎醫學院，廣州510405）

摘 要：通過分析數據關聯的特點和已有的關聯規則挖掘算法，在定量描述的準確性和算法高效性方面作了進一步研究，提出了更準確的支持度和置信度定量描述方法和關聯關系強弱的定量描述方法。同時，改進了FP-growth挖掘算法，并應用于中醫舌診臨床病例數據庫挖掘實驗中，可成功準確地提取中醫舌診診斷規則。測試結果表明該算法速度快、準確度高。

關鍵詞：數據挖掘；關聯規則；頻繁模式增長算法；頻繁模式樹；中醫診斷

中圖分類號：TP301

文獻標志碼：A

文章編號：1001-3695(2008)10-2962-03

New mining algorithm study on association rules

WEI Yu-ke¹a，1b， WANG Ren-huang¹a， LI Jiang-ping¹a， CHEN Qun²

（1. a. School of Automation，b.School of Computer，Guangdong University of Technology， Guangzhou 510640， China；2. School of Basic Medical Science， Guangzhou University of TraditionalChineseMedicine， Guangzhou 510405， China）

Abstract:By analyzed the characteristics of data association and the mining algorithm of association rules that have been put forward， advanced research have been made in every field of accuracy of quantitative description and high efficiency of algorithm. The article put forward a more efficiency method of quantitative description about support degree and confidence degree， and a method of quantitative description about strength of association relationship. Meanwhile the article improved FP-growth mining algorithm and applied it to mining experiment on clinical diseases database in the traditional Chinese medicine (TCM) tongue diagnosis. The algorithm could accurately draw diagnosis rule from (TCM) tongue diagnosis successfully. The application result in make clear that， the algorithm can be faster and accurate more.

Key words：data mining；association rules；FP-growth algorithm；FP-tree ；TCM diagnosis

關聯規則是數據庫中一種重要的知識模式。其概念最早于1993年由Agrawal等人提出，研究對象是交易數據庫。其主要目的是發現交易數據庫中交易項目之間是否存在某種關系，后來又推廣到關系型數據庫。Agrawal等人[1，2]提出的經典Apriori算法和Han等人[3，4]提出的FP-growth(frequent-pattern growth)算法最為著名。Apriori算法主要是基于Apriori性質，即如果某k項目集Ik不是頻繁k-項目集，則包含Ik的(K+1)項目集也不是頻繁(K+1)-項目集，亦即一個項目集是頻繁項目集當且僅當它的所有子集都是頻繁項目集。Apriori算法的基本思想是：掃描一次事務集合，找出頻繁1-項目集集合L1；基于集合L1，產生所有可能的頻繁2-項目集，即候選2-項目集集合C2，再掃描一次事務集合，基于L1和C2，找出頻繁2-項目集集合L2；依此類推，直至不能找到頻繁項目集為止。最后在所有頻繁項目集中產生強關聯規則。FP-growth算法是一種不產生候選項目集而采用模式增長的方式挖掘頻繁模式的算法。將數據庫壓縮到一顆頻繁模式樹，但仍保留項目集關聯信息，然后將這種壓縮后的數據庫分成一組條件數據庫，每個關聯一個頻繁項，并分別挖掘每個數據庫。基于這兩種算法，已經出現了很多的改進算法，這些算法[5]大多集中在如何提高挖掘的效率上。

近年來，針對傳統的支持度—置信度模型所存在的問題提出了很多改進的方法。這方面的研究大體可以分為：a)設法尋找置信度度量的替代物[6] (如興趣度、有效度、匹配度等)；b)擴展原有的固定支持度閾值限制的客觀評價方法的改進，如Wang等人[7]提出的面向盒子的非統一支持度設置模型，Liu等人[8]提出的多支持度閾值的關聯規則挖掘算法，Seno等人[9]使用了可變的支持度閾值，使它隨著項目集的長度增加而減少，有助于發現長項目集而不會產生大量的短項目集；c)設法增加主觀度量方法[10] 。總之，如何從挖掘出來的關聯規則中選擇出用戶最希望得到的知識是關聯規則挖掘需要解決的重要問題。

通過分析數據關聯的特點及Agrawal等人的關聯規則的基本概念，筆者認為其關聯規則的基本概念存在些許偏差。在修正基本概念偏差的基礎上，本文提出了一種更合適的關聯概念。

1 關聯規則理論

11 支持度

在Agrawal等人的關聯規則理論中，把相關聯的項目集X和Y分別看做前件和后件，在文獻[11]中將支持度定義為support(X)= P(X)

支持度是定義在項目集上的，它給出交易中項目集X出現的頻度，只有項目集頻繁出現，才能比較準確地找出其中的規律，因此支持度可以用來衡量一個項目集的重要性，通常稱為概率約束。如果一個項目集X的支持度大于或等于用戶指定的最小支持度，即稱項目集X滿足為頻繁項目集。

支持度具有向下閉合特征，即具有半單調性。這意味著頻繁項目集的所有非空子集都是頻繁的。支持度的取值為[0，1]。如果關聯規則的前件和后件在交易數據庫中都沒有出現，則它的支持度等于0；如果關聯規則的前件和后件在交易數據庫中的所有交易事務中都出現，則它的支持度等于1。支持度可以描述一個被挖掘出的關聯規則的有用性。

文獻[11]中定義的支持度作為度量有一個偏差，只考慮了交易中項目集X出現的頻度，而忽略了項目集Y出現的頻度。作為相關聯的兩個對象之一的項目集Y被忽略，顯然是不合適的。

分析其原因，Agrawal等人的關聯概念中把關聯關系似乎人為地限定為弱因果關系：項目集X的產生是項目集Y產生的原因，認為抓住了原因就可以了，故可以忽略項目集Y。但實際上，關聯關系可能是弱因果關系，也可能不是這種關系，關聯關系只能確定為是一種可共存或非互斥關系基礎上的某種聯系。究竟是一種什么關系其實不是關注的焦點，關鍵是把存在這種關聯的雙方找到，因此應把關聯的雙方對等看待。對支持度定義作如下修正：

定義1 設I ={I1，I2，…，Im }是由m個不同項目組成的集合，給定一個事務數據庫D。其中：每個事務T是一組項目的集合；X和Y為部分項目的集合，即TI，XI，YI，X≠，Y≠，X ∩Y＝; TX表示包含項目集X的事務集;TY表示包含項目集Y的事務集；TX∪TY表示TX和TY的并集；XY表示項目集X和Y的對等關聯關系。其支持度為support (XY)= P(TX∪TY) 

因為P(TX)= P(X)；P(Ty) = P(Y)，P(TX∩TY) = P(XY)，所以P(TX∪TY) = P(X)+ P(Y)- P(XY)，得support (XY)= P(X)+ P(Y)- P(XY)。

12 置信度

在Agrawal等人的關聯規則理論中，把相關聯項目集X和Y看做前件導致后件的出現。在文獻[12]中將置信度定義為

confidence(XY) = P(Y︱X )= P(XY)/P（X）。

置信度可以看成是在交易數據庫中前件發生的條件下后件概率P(Y︱X )的估計，它表示某些項目集的出現會導致其他項目集出現的可能性大小。置信度的取值為[0，1]。如果關聯規則的前件和后件無關，則它的置信度等于0；如果關聯規則的前件出現后件必然出現，則它的置信度等于1。置信度可以描述一個被挖掘出的關聯規則的確定性。

置信度作為度量有一個缺點，就是只考慮了X與XY的關系，而忽略了P(Y)。置信度對于關聯規則XY和YX具有不同的值，這是不太恰當的。關聯規則置信度的計算可能出現較大誤差，這就有可能提取一些不符合實際的信息。

為了更準確地度量關聯關系，置信度作如下定義：

定義2 設I={I1，I2，…，Im }是由m個不同的項目組成的集合，給定一個事務數據庫D。其中：每個事務T是一組項目的集合；X和Y為部分項目的集合，即TI，XI，YI，X≠，Y≠，X ∩Y＝; TX表示包含項目集X的事務集;TY表示包含項目集Y的事務集; TX∪TY表示TX和TY的并集;TX∩TY表示TX和TY的交集;XY表示項目集X和Y的對等關聯關系，則其置信度為confidence(XY) = P(TX∩TY)/ P(TX∪TY) 得confidence(XY) = P(XY) /( P(X)+ P(Y)- P(XY))。

關聯關系有強弱之分。為了定量描述關聯關系的強弱，提出關聯強度的概念，定義如下：

定義3 項目集X和Y相關聯的概率與項目集X和Y非關聯的概率的比值稱為關聯強度。當P(TX∪TY)≠ P(TX∩TY)時，Con-strength(XY) = P(TX∩TY)/（P(TX∪TY)- P(TX∩TY)）得 Con-strength(XY)=P(XY) /( P(X)+ P(Y)-2×P(XY))。當P(TX∪TY)＝ P(TX∩TY)時，Con-strength(XY) = +∞。

關聯強度的值域為[0，+∞）。

Con-strength(XY)=0 稱為無關聯；0＜Con-strength(XY)≤1稱為弱關聯; Con-strength(XY)＞1稱為強關聯。

2 算法分析與實現

本文采用改進的FP-growth算法。在算法的實現步驟中，關鍵是建立FP-tree的過程。對于一個事務數據集，按照FP-growth算法建立的FP-tree完全反映了該數據集的頻繁項的信息，對數據集挖掘轉變為對FP-tree的挖掘，從而實現了對數據集頻繁項的挖掘過程。對事務數據集的每個事務逐個調用插入節點函數insert_tree(p|P]，T)的過程就是生成FP-tree的過程，而在每個事務中insert_tree(p|P]，T)的遞歸調用即是實現搜索P與T的共享前綴的過程。如果它們有相同的前綴，則把這個共享前綴的計數加1后繼續搜索下一個相同前綴；若沒有相同前綴則建立新節點并鏈接到T。對于有大量數據集的事務數據庫而言，事務集的數目越多，樹的規模也越龐大，為搜索一個相同的前綴可能需要遍歷一個節點的所有子女節點，從而搜索共享前綴的時間復雜度也隨之增加。下面按照共享前綴的程度分為以下三種情況對搜索前綴的時間復雜度進行討論。

1)完全共享前綴 在理想條件下，遍歷第一個子女節點就發現共享前綴，其時間復雜度為O(n)，n為該事務的長度。在最壞條件下，遍歷到最后一個子女節點才發現共享前綴，其時間復雜度為O(∑n-1i=1Li)。其中：n為根節點到最后一個節點的長度;Li為根節點到最后一個節點的所有節點的子女數。

2)部分共享前綴 在最壞條件下，遍歷到節點的最后一個子女才發現共享前綴，其時間復雜度為O( ∑n-1i=1Li)。其中：n為根節點到最后一個共享前綴節點的長度；Li為根節點到最后一個共享節點的這部分節點的子女數。

3)無共享前綴 在這種情況下復雜度為O(m)，m為根節點的子女數。

在生成FP-tree的過程中，事務集的數目越多，需要遍歷的節點數目也就越多，就一般事務集而言，遍歷節點的第一個子女節點就發現相同前綴的理想條件出現的可能性也越低，這必然使得搜索共享前綴變得非常耗時。對于建立節點并鏈接和節點計數加1而言，搜索共享前綴的時間復雜度決定了生成FP-tree的時間復雜度，即如果能夠減少搜索共享前綴的時間也就減少了生成FP-tree的時間，進而提高挖掘效率。

為確保在理想條件下搜索共享前綴，也就是在存在共享前綴的條件下，遍歷節點的第一個子女節點就發現相同前綴。對數據庫的第一次掃描導出頻繁1-項集，并得到它們出現的頻度，然后按頻繁1-項集出現的頻度建立降序表L。把事務集的每個事務項目按照表L的次序排列得到數據庫D′，針對數據庫D′建立FP-tree。為便于樹的遍歷，創建一個項頭表，使得每個項通過一個節點鏈指向它在樹中的出現位置（圖1）。

3 實驗及結果分析

本例的頻繁模式挖掘是在相同病癥的病例內進行的。關聯規則的挖掘主要由三個模塊組成：數據預處理，尋找頻繁項目集，計算關聯的頻繁項目集的支持度、置信度和關聯強度，提取強關聯關系（即獲取知識）。其中尋找頻繁項目集是運算量最大的模塊。由于算法都是基于事務數據庫挖掘單維布爾關聯規則的，首先要將數據庫記錄中的項目值轉換成布爾型值，這就是數據預處理。

表1 某病例數據庫的部分記錄TID癥狀代號TID癥狀代號T100I1，I2，I5T600I2，I3T200I2，I4T700I1，I3T300I2，I3T800I1，I2，I3，I5T400I1，I2，I4T900I1，I2，I3

數據庫的第一次掃描導出頻繁1-項集，并得到它們的出現頻度計數。項目按1-項集的頻度遞減順序排序，建立降序表，記做L，有L={I2∶7， I1∶6， I3∶6， I4∶2， I5∶2}。

為方便樹的遍歷，創建一個項頭表，使得每個項通過一個節點鏈指向它在樹中的出現位置。掃描所有事務之后得到的FP-tree如圖1所示，圖中給出了相關的節點鏈。這樣，數據庫頻繁模式的挖掘問題就轉換成挖掘FP-tree的問題。

FP-tree的挖掘總結在表2中。筆者首先考慮I5，它是L中的最后一項，而不是第一項。I5出現在圖1的FP-tree的兩個分支。這些路徑由分支（I2 I1 I5∶1）和（I2 I1 I3 I5∶1）形成。這樣，考慮I5后綴，它的兩個對應前綴路徑是（I2 I1∶1）和（I2 I1 I3：1），它們形成I5的條件模式基。它的條件FP-tree只包含單個路徑（I2∶2I1∶2），不包含I3，因為它的支持度計數為1，小于最小支持度計數。該單個路徑產生頻繁模式的所有組合：I2 I5∶2，I1 I5∶2，I2 I1 I5∶2。對于I4，它的兩個前綴形成條件模式基{(I2 I1∶1)，(I2∶1)}，產生一個單節點的條件FP-tree〈I2∶2〉，并導出一個頻繁模式 (I2 I4∶2)。注意，盡管I5跟在第一個分支中的I4之后，也沒有必要在此分析中包含I5，因為涉及I5的頻繁模式在對I5的考察時已經分析過。這就是為什么在L的后端，而不是在前段開始處理的原因。算法偽代碼描述如下：

算法：改進的FP-growth。使用FP-tree，通過模式段增長挖掘頻繁模式。

輸入：事務數據庫D；最小支持度閾值min_sup。

輸出：頻繁模式的完全集。

方法：

a）按以下步驟構造FP-tree：

(a)掃描事務數據庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結果為頻繁項表L。

(b)創建FP-tree的根節點，以1標記。對于D中每個事務trans執行：

選擇trans中的頻繁項，并按L中的次序排序。設排序后的頻繁項表為[p|P]。其中：p是第一個元素；P是剩余元素的表。調用insert_tree([p|P]， T)，T是FP-tree的一個節點。該過程執行情況如下：如果T有兒子N使得N.item-name=p.item-name，則N的計數增加1；否則創建一個新節點N，將其計數設置為1，連接到它的父節點T，并且通過節點鏈節構將其連接到具有相同item-name的節點。如果P非空，遞歸地調用insert_tree(P，N)。

b）FP-tree的挖掘通過調用FP_growth(FPTree， 1)實現。該過程如下：

ProcedureFP_growth(tree， α)

if tree 含有單個路徑 P then

for 路徑P中所有節點的每個組合(記做β)

生成模式β∪α with support = minimum support of nodes in β;

else for each ai 在tree的頭部{

生成模式β=ai ∪α with support=ai.support;

構造β的條件模式基（conditional pattern base），然后構造β的條件FP-tree(conditional FP-tree);

if treeβ ≠then

調用FP_growth(treeβ， β);

表2 通過條件模式基挖掘FP-treeItem條件模式基條件FP-tree 產生的頻繁模式I5

I4

I3

I1{(I2 I1∶1)，(I2 I1 I3∶1)}

{(I2 I1∶1)，(I2∶1)}

{(I2 I1∶2)，(I2，2)，(I1∶2)}

{(I2∶4)}〈I2∶2， I1∶2〉

〈I2∶2〉

〈I2∶4， I1∶2〉，〈I1∶2〉

〈I2∶4〉I2 I5 ∶2， I1 I5∶2，I2 I1 I5∶2

I2 I4∶2

I2 I3∶4， I1 I3∶4，I2 I1 I3∶2

I2 I1∶44 結束語

關聯規則的準確定量描述，直接影響獲取知識的真實性和有用性。本文提出的度量方法雖然計算復雜，但較全面地考慮了所有必要因素，故準確性高。由于對具體實現算法也作了改進，計算速度較快。中醫診斷不僅要全面考慮病人的臨床表現，一般還要考慮病人的年齡、職業、生活地區以及季節等與病癥的關系。由于其復雜性，中醫診斷規則往往隱藏在大量的病例數據中，很難明確地敘述。本文方法應用于提取中醫診斷規則，實驗證明是有效和可靠的。

參考文獻：

[1]SRIKANT R， AGRAWAL R.Mining generalized association rules[C]// Proc of the 21st Int Conf on Very Large Database.1995: 407-419.

[2]AGRAWAL R， SRIKANT R. Fastalgorithms for mining association rules in large database， FJ 9839[R]. San Jose， CA: IBM Almaden Research Center， 1994.

[3]HAN J， PEI J， YINY. Mining frequent patterns without candidate generation[C]// Proc of 2000 ACM-SIGMOD Int Conf on Management of Data (SIGMOD’00). 2000:1-12.

[4]KAMBER M， HAN J， CHANG J. Metarule-guided mining of multi-dimensional association rules using data cubes[C]//Proc of 1997 Int Conf on Knowledge Discovery and Data Mining(KDD’97). 1997:207-210.

[5]廖仁全，王利華，邱江濤．一種基于FP-tree的頻繁項目集增量更新算法[J]．計算機工程與應用，2007，43（4）：176-178.

[6]馬建慶，鐘亦平，張世永.基于興趣度的關聯規則挖掘算法[J]．計算機工程，2006，32(17)：121-122.

[7]WANG K， HE Y， HAN J. Mining frequent itemsets using support constraints[C]// Proc of the 26th Int Conf on Very Large Databases. Cario:[s.n.]: 2000:43-52.

[8]LIU B， HSU W， MA Y. Mining association rules with multiple minimum supports[C]//Proc of ACM-SIGKDD Int Conf on Knowledge Discovery and Data Mining. San Deigo， CA:[s.n.]， 1999:337-341.

[9]SENO M， KARYPIS G. LPMiner: an algorithm for finding frequent itemsets using length-decreasing support constrain[C]//Proc of ICDM’01. California: IEEE Computer Society，2001:505-512.

[10]蘇占東，游福成，楊炳儒．關聯規則的綜合評價方法研究與實驗驗證[J]．計算機應用，2004，24（10）：17-20.

[11]BRIN S， MOTWANI R， SILVERSTEIN C. Beyond market baskets: generalizing association rules to correlations[C]//Proc of ACM SIGMOD Conf on Management of Data. Tucson:[s.n.]， 1997:265-276.