最小組合法挖掘最大頻繁集

摘要：提出了與apriori和FPtree兩類算法完全不同的高效挖掘最大頻繁集的算法，即最小組合算法MCA。該算法不產生候選頻繁集，能大大減少計算量的開銷。在此算法的研究中提出了另一個子課題，即重復數列中最小組合算法研究。

關鍵詞：關聯規則；最大頻繁集；最小組合算法；重復數列中最小組合

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2008)03－0702－03

挖掘所有頻繁集是數據挖掘中關聯規則研究的關鍵問題。近年來，關于頻繁集先后出現了多種挖掘算法，主要有apriori法[1]和FPtree（頻繁樹法）[2]兩大類，其他大多數算法都是這兩種算法的改進或衍生變種。Apriori算法的思想是使用一種稱做逐層搜索的迭代方法，K項集用于探索（K+1）項集；同時對候選頻繁集進行縮水剪枝，其目的是及早盡多地剔除實際不可能產生頻繁集的候選頻繁集，減少運算量。FPtree法是將數據庫投影到一棵頻繁模式樹FPtree上，然后通過尋找FPtree中節點路徑來窮盡挖掘頻繁項目集。

經分析，以上兩類算法均存在一定的缺陷。Apriori算法先要求出全部的候選頻繁集，若數據庫寬度較大則候選頻繁集會很龐大，且每個候選頻繁集要對數據庫深度進行掃描，這樣運算量勢必很大。FPtree算法的優點是掃描數據庫的次數少，但其關鍵缺陷是由節點前綴路徑形成條件模式基來導出頻繁模式時同樣要分析大量的候選頻繁模式；當數據庫很大時，構造的FPtree將很龐大，因而不僅運算時間長，可能還存在內存空間不夠的問題。本文首次提出與以上兩類算法完全不同的高效挖掘最大頻繁集的算法——MCA。

1相關概念和性質

1．1頻繁集和最大頻繁集

事務是指數據庫D的一個記錄；項目（item）是記錄中的屬性。設I={I1，I2，…，Im}是一個全部的項目集，數據庫D就是所有事務的集合，每個事務T對應于一個項目子集，即T∈I。每個事務有一個事務標志TID。對項目集X，當且僅當X∈T，稱事務T包含X。

定義1[3]設數據庫D共有N個事務。設項目集X∈I，D中包含X的事務數為S(S稱為X的支持數，S/N%稱為X的支持度)。若S不小于某個給定的最小支持數閾值S0，稱項目集X為頻繁集；反之，稱X為非頻繁集。

定義2[3]若頻繁集X的所有超集都是非頻繁集，則稱X為最大頻繁集。

性質1[3]如果X是頻繁集，那么X的任何非空子集都是頻繁集。

性質2[3]如果X是非頻繁集，那么X的任何超集都是非頻繁集。

性質3包含項目Ij的頻繁集的產生只可能與包含Ij的事務有關，與不包含Ij的事務無關。

證明設A是不包含Ij的事務，B是某個包含Ij的頻繁集，則A的任何子集都不可能是B，因此A存在與否不影響B的支持數，那么在挖掘頻繁集B時不必考慮事務A。

性質4如果事務T是某最大頻繁集的子集，則該事務存在與否對其他新的最大頻繁集的產生不起作用。

證明設T是最大頻繁集K1的子集，K2是另一個最大頻繁集，K2不可能是K1的子集，則K2中某些項目不會在T中出現。根據性質3可知T對K2的誕生不起作用。因此在求K2時不必考慮T。

1．2事務的最小組合

事務的計數值是指該事務在D中出現的次數。該值包含兩個方面的內容：該事務在D中重復出現的次數；有些不同事務計數值的合并，如事務{I1，I2}的計數值為n1，事務{I1，I2，I3}的計數值為n2，若項目I3在D中的支持數小于S0，根據性質2可將所有事務中的I3剔除，則上面兩事務可合并成一個事務{I1，I2}，其計數值為n1+n2。

定義3若干事務集合的計數值之和不小于S0，且該集合的任何子集的事務計數值之和均小于S0，則稱該事務集合為最小組合MC（minimal combination）。

性質5MC的事務集合中，各事務的公共項目集為頻繁集，且為候選最大頻繁集。

證明MC的公共項目集必定出現在MC的每個事務中，根據定義3其計數值之和不小于S0，根據定義1其為頻繁集。若某個MC的公共項目集不是其他MC的公共項目集的子集，根據定義2則該MC的公共項目集便是最大頻繁集。

性質6數據庫D的所有最大頻繁集包含在所有MC的公共項目子集的集合中。

證明設M是最大頻繁集，則包含M的事務計數值之和必定不小于S0，這些事務（或一部分事務）一定會產生MC，其公共子集就是M。也就是說，每一個最大頻繁集必定有一個對應的MC。一個MC的公共項目子集是頻繁集，但不一定是最大頻繁集。

2MCA介紹

本文采用的研究思想是充分利用最小支持數閾值S0這個惟一已知的參數，采用最小組合法（MCA）挖掘最大頻繁集。首先求MC。其方法是根據定義3對數據庫中事務進行邏輯組合，即找出所有符合MC定義的事務組合。由性質6可知所有MC的公共項目集的集合包含全部的最大頻繁集。以表1的簡單數據庫D為例（設S0=4）說明MCA的思想。

求MC的過程：a）T01、T02組合不是MC，因為它們計數值和為3S0），其公共子集為{I2，I4}。d）T02和T04組合為MC（計數和為5>S0），其公共子集為{I1，I5，I6}。e)T03和T04組合為MC（計數和為6>S0），其公共子集為{I3}。

所有MC的公共子集是：{I2，I3，I7}，{I1，I3，I5}，{I2，I4}，{I1，I5，I6}，{I3}。{I3}是其他集合的子集，它是頻繁集而不是最大頻繁集。由此得出所有最大頻繁集為{I2，I3，I7}，{I1，I3，I5}，{I2，I4}，{I1，I5，I6}。

3重復數列中最小組合算法介紹與分析

3．1問題的提出

求MC是MCA的精髓，也是該算法的難點。為此將問題轉換成另一種形式：每個事務的計數值作為數列中的一個元素，n個事務便對應一個有n個元素的數列。如果某事務計數值不小于S0，則該事務本身為MC，不必再求。由此提出另一個課題，即數列中最小組合算法研究。設A1，A2，A3，…，An是一個有n個數值小于S0的正整數數列，求出所有的最小組合（MC是該組合的所有元素之和不小于S0，且其子集的元素之和小于S0）。這是一個看似簡單實際復雜的問題，該問題的解決能進一步優化MCA的性能。

經分析，在實際數據庫中，有較多的不同事務具有相同的計數值（原因是S0的設置是一個較小的數，一般是整個事務數的百分之幾以下，這是實際應用的要求；若S0設置較大，頻繁集將很稀疏，挖掘的運算量小，這將不是一個課題問題。由于S0/n<10%，且n個事務的計數值是小于S0的正整數（若不小于S0，則該事務本身為MC，不必再求），根據鴿巢原理可得到較多的不同事務必定具有相同的計數值。根據這一特點可對上面課題進一步簡化。設D中有n個不同的事務，則數列中有n個元素，若n的值大則求MC的運算量也大。由于求MC時只考慮元素數據和的值，則相同數據值的元素可以合并處理。

合并處理的方法是設A1，A2，…，Ai，Ai+1，…，Ak，…，An為一個n項元素的數列，A1，A2，…，Ai這i個元素有相同的值。Ai+1…Ak這k-i個元素有另一個相同的值。若{A1，Ai+1}為MC（即A1+Ai+1≥S0），則數列中前i項任取一項與從Ai+1…Ak中任取一項的組合都為MC。因此A1，A2，…，Ai可合并成一個元素B1（B1=A1=…=Ai），重復次數為i，記為B1（i）； Ai+1…Ak可合并為另一個元素B2（B2= Ai+1=…=Ak），重復次數為k-i，記為B2（k-i）;上述n項數列可轉換成B1（S1），B2(S2)，…，Bm(Sm)只有m項的數列。Bi(Si)表示計數值為Bi的事務有Si個，且m≤S0（因為B1，B2，…，Bm的值為小于S0的不同正整數）。也就是說，無論D中事務數n多大，都可以將問題轉換成元素個數小于S0的數列來求MC。將此最小組合稱為重復數列中最小組合MCRA（定義4）。下面提出挖掘MCRA的一種高效算法。

3．2算法思想介紹與分析

按以下步驟求MCRA：a)求重復數列中每個元素自身若干項組合產生的MCRA。輸入：B1（S1），B2(S2)，…，Bi(Si)，…，Bm(Sm)；輸出：每個元素自身若干項組合產生的MCRA，并將輸入數列重新整理成B1（M1），B2(M2)，…，Bi(Mi)，…，Bm(Mm)。此新數列中每個元素自身若干項組合不能產生MCRA，即Bi×MiS0 ，可見Mi≤Si。這樣在第二步中不必考慮每個元素自身組合產生的MCRA，同時將Si減小至Mi，以減小第二步的冗余循環。該步采用簡單循環即可實現，循環的終止條件是Bi×MiS0。b)求重復數列中每個元素若干項與其他元素若干項組合產生的MCRA。該步要考慮若干元素的若干項組合產生的MCRA，計算比較復雜。本文采用遞歸調用循環子程序的方法解決。

1)求重復數列中每個元素自身若干項組合產生MCRA的算法

輸入：B1（S1），B2(S2)，…，Bm(Sm)。

輸出：每個元素自身若干項組合產生的MCRA，并將輸入數列重新整理成B1（M1），B2(M2)，…，Bm(Mm)。此數列每個元素自身若干項組合不能產生MCRA，即Bi×Mi< S0，這樣便于下一步求重復數列中每個元素若干項與其他元素組合產生的MCRA。

3．3算法的性能分析

設數據庫D有n個項目、C個事務，最小支持度為S0/C（一般0.1%

1)求重復數列中每個元素自身若干項組合產生MCRA的運算量分析

B1（S1），B2(S2)，…，Bm(Sm)是由數據庫D事務映射成的數列(是小于S0的不同正整數數列)；計數值為Bk的事務映射成Bk；Sk是計數值為Bk事務的個數，顯然事務總數C=S1+…Sm。

根據定義4，求Bk自身產生的MCRA的循環次數為int(S0/Bk)+1（因為Bk×(int(S0/Bk)+1)≥S0便可得MCRA），總的運算量為mk=1int(S0/Bk)+1。

設C=106（稍大點的數據庫），最小支持度為1%，則S0=104。極端情況是數列包含所有小于S0的數據項（此時有m= S0-1），總的運算量為mk=1int(S0/k)+1≈94 000（經實驗驗證）。可見這步的運算量是很小的。

2)求重復數列中每個元素若干項與其他元素組合產生MCRA的運算量分析

這一步要精確計算其運算量是比較困難的，因為每個元素若干項與其他若干元素的若干項組合皆可能產生MCRA。對于數列B1（M1），B2(M2)，…，Bm(Mm)，由于數據項自身產生的MCRA已分析，只需考慮每個元素若干項與其他元素組合產生的MCRA，則有Bk×Mk< S0。該步運算量是如算法所描述的多層循環的循環次數，即以K1×B1(K1=0～M1)+ K2×B2(K2=0～M2)+…+ Km×Bm(Km=0～Mm)≥S0為循環終止條件的循環次數。由于循環結束條件無規律性，運算量的表達式很復雜。本文仍以上面C=106、最小支持度為1%的數據庫所映射的數列為例，極端情況下數列是1(9999)，2（4999），3（3333），4（2499），…，4999(2)，5000（1），5001（1），…，9999（1），通過MCA運算，其循環次數為1 910 317 662。可見這步的運算量仍然是可接受的。MCA將一個天文級的組合數降低至可接受的運算量，應該說取得了較大的突破，比FPtree和apriori算法大約快2~3個數量級，為大型數據庫挖掘關聯規則從理論走向應用掃除了障礙。

4實驗結果

本文用VC++ 6.0在內存128 MB，CPU為PentiumⅡ 667 MHz，操作系統為Windows 98的PC機上實現了MCA。使用與文獻[4，5]同樣的測試數據庫，該數據庫有8 124條記錄，記錄了蘑菇的23種屬性。同時與apriori類有代表性的DMFI[4]算法和FPtree類有代表性的IDMFIA[5]進行比較分析。圖1顯示了在不同的最小支持度（0.5%、1%、2%、3%、4%、5%）下三種算法的性能變化。實驗結果表明，最小支持度越小，頻繁集就越多，CPU耗時越多。圖2檢驗了三種算法的擴展性，固定最小支持度為1%，從上面的數據庫中隨機抽取不同的記錄數（1 500、3 000、4 500、6 000、7 500）進行測試。實驗也說明了因MCA的邏輯組合針對性非常強，效率是較高的。

5結束語

通過上面的分析可以看出，采用MCA挖掘最大頻繁集，應該是較逼近求取最大頻繁集問題的最優理論算法。

因為在挖掘頻繁集過程中，對給定的最小支持數閾值S0這惟一參數，apriori和FPtree算法都只將其作為挖掘頻繁集的依據；本文不僅將其作為挖掘的依據，而且作為挖掘的手段，利用這一參數第一次提出了最小組合的概念，采用最小組合技術來挖掘最大頻繁集，即用S0作為挖掘中循環運算的控制參數，使循環的次數最小，剔除大量的冗余循環。具體表現在：a）對數據庫D掃描次數很少。剔除出現次數小于S0的項目，相同的事務合并，這樣對D的預處理就完成了。b）將挖掘最大頻繁集轉換成求數列中最小組合的問題。從本文算法可看到，搜索手段針對性很強，不會產生候選頻繁集（但有可能產生的頻繁集不是最大頻繁集）。c)將求MC進一步轉換成求MCRA，這樣無論D中事務數n多大，都可以將問題轉換成一個元素項小于S0的數列來求最小組合。

參考文獻：

［1］AGRAWAL R，IMIELINSKI T，SWAMI A.Minig association rules between sets of items in large databases[C]//Proc of ACM SIGMOD International Conference Management of Data. Washington DC:[s.n.]，1993:207－216.

[2]HAN Jiawei，PEI Jian，YIN Yiwei.Mining frequent patterns without candidate generation[C]//Proc of ACM SIGMOD International Conference Management of Data.Dallas:[s.n.]，2000:1－12.

[3]HAN Jiawei，KAMBER M.Data mining:concepts and techniques[M].Beijing:High Education Press，2001.

[4]路松峰，盧正鼎.快速開采最大頻繁項目集[J].軟件學報，2001，12（2）：293－297.

[5]吉根林，楊明，宋余慶，等.最大頻繁項目集的快速更新[J].計算機學報，2005，28（1）：128－135.

[6]宋余慶，朱玉全，孫志揮，等.基于FPtree的最大頻繁項目集挖掘及更新算法[J].軟件學報，2003，14（9）：1586－1592.

[7]BAYARDO R.Efficiently mining long patterns from databases[C]//Proc of ACM SIGMOD International Conference on Management of Data.New York:ACM Press，1998:85－93.

[8]楊明，孫志揮，吉根林.快速挖掘全局頻繁項目集[J].計算機研究與發展，2003，40（4）：620－626.

[9]朱玉全，孫志揮，趙傳申.快速更換頻繁項集[J].計算機研究與發展，2003，40（1）：94－99.

[10]楊明，孫志揮，宋余慶.快速更新全局頻繁項目集[J].軟件學報，2004，15（8）：1189－1197.

[11]劉君強，孫曉瑩，王勛，等.挖掘最大頻繁模式的新方法[J].計算機學報，2004，27（10）：1327－1334.

[12]陸介平，楊明，孫志揮，等.快速挖掘全局最大頻繁項目集[J].軟件學報，2005，16（4）：553－560.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”