支持度和置信度自適應的關聯規則挖掘

林甲祥，巫建偉，陳崇成，張澤均，舒兆港

(1.福建農林大學 計算機與信息學院，福建 福州 350002；2.國家海洋局第三海洋研究所海洋環境管理與發展戰略研究中心，福建 廈門 361001；3.福州大學 空間數據挖掘與信息共享教育部重點實驗室，福建 福州 350116)

0 引 言

關聯規則是數據挖掘一個重要研究主題，在購物籃分析、醫療診斷、股票存貨分析、Web日志挖掘、客戶市場分析、生物信息資訊等領域有著廣泛的應用[1]。文獻中提出的大多數關聯規則挖掘方法采用兩步驟的策略，首先從數據集中尋找所有頻繁項集，然后由這些頻繁項集生成強關聯規則，算法的原理簡單且易于實現，其中第一步頻繁項集的生成是算法的關鍵，典型算法如Apriori、FP-tree等[2]。

以頻繁項集搜索為核心的關聯規則挖掘算法，在支持度的約束下進行頻繁項集搜索，在置信度的約束下進行強關聯規則確認。目前，許多關聯規則挖掘實踐中，最小支持度(minsup)和最小置信度(minconf)參數的取值方法仍是由用戶根據先驗知識進行人為的指定，一方面，非專業關聯規則算法用戶，對算法參數的取值一般具有較大的主觀隨意性、往往很少考慮參數取值的科學性；另一方面，挖掘模型中支持度和置信度閾值的不同取值，對挖掘過程中頻繁項集的大小、自連接產生候選項集的規模、挖掘結果中關聯規則的數目有著顯著的影響。從算法設計的角度實現關聯規則支持度和置信度參數的科學化和自適應化取值，文獻中還鮮有相關的研究成果報道。因此，擬在分析事務數據集中所有項的支持數和所有規則的置信度的基礎上，使用統計擬合技術，對支持度和置信度閾值的自動化確定技術進行研究，提出基于支持度和置信度自適應技術的無參化關聯規則挖掘解決方案，以期降低關聯規則挖掘行業化應用的門檻。

1 相關研究進展

近年來，研究人員在提高關聯規則計算效率、尋找更緊致數據結構、處理的數據類型擴展等方面做了大量的研究。典型工作如：增量式關聯規則挖掘方面，Nath等[3]對增量式關聯規則挖掘算法進行了綜述。基于特定數據結構的關聯規則挖掘方面，Vo等[4]對基于N-list和包含概念的頻繁項集挖掘PrePost算法進行研究，在N-lists創建和交互中融合了Hash技術，對算法進行了改進。此后，Huong等[5]對基于N-list和考慮權重的頻繁項集挖掘算法進行了研究。Maria Luna等[6]提出了一種稱為倒排索引壓縮(inverted index compression)的數據結構，能夠用于很多現有的關聯規則挖掘算法，用于提高算法的效率。Anand等[7]為提高關聯規則挖掘的效率，提出了基于橫二叉樹(Treap)數據結構的關聯規則挖掘算法。牛新征等[8]提出了一種基于FP-tree的快速關聯規則隱藏算法，避免了遍歷原始數據集產生的大量I/O時間，減少了關聯規則隱藏處理對原始數據集的影響。分布式&并行關聯規則挖掘方面，Wang等[9]使用微處理器技術對關聯規則的并行化和效率提升進行了研究。Vu等[10]針對頻繁模式搜索，開展了多核共享存儲器的并行關聯規則挖掘研究。Liu等[11]面向大數據，提出了一套基于MapReduce和最大頻繁項集的啟發式多流程關聯挖掘解決方案。基于智能技術的關聯規則挖掘方面，Sohrabi等[12]對基于元胞自動機的頻繁模式挖掘進行了研究，并與Apriori、FP-Growth、BitTable等知名算法的效率進行了對比分析。Zou等[13]提出了一種基于模糊概念格的關聯規則挖掘及其動態更新算法。Heraguemi等[14]將使用多重合作策略的蜂窩算法用于關聯規則挖掘。基于關聯規則的應用研究方面，Tseng等[15]對事務數據庫中高效用項集的關聯規則挖掘進行研究，提出了效用模式增長算法UP-Growth及其改進算法UP-Growth(+)。Leu-ng等[16]針對大數據環境下的Web頁面推薦，提出了一套按位(bitwise)并行關聯規則挖掘方法。何明等[17]為了提高個性化推薦效率和推薦質量，平衡冷門與熱門數據推薦權重，提出了優化Apriori算法且適合不同測評標準值的k前項頻繁項集挖掘算法。

在關聯規則算法參數取值研究方面，Sarath等[18]使用二進制粒子群優化策略，對關聯規則挖掘進行研究，無須指定最小支持度和最小置信度參數，只需指定要獲得的規則的數目。雖然，一些基于智能技術的關聯規則挖掘，通過問題解空間的全域搜索，無須設置最小支持度和最小置信度參數的值，即可獲得支持度最高、置信度最高的若干強關聯規則，但需要很大的計算量。對于關聯規則挖掘算法參數的自適應取值研究，文獻中未見相關成果報道。

2 核心概念與挖掘流程

2.1 相關概念

令交易事務數據庫中所有商品種類的集合為I=i1,i2,…,im，其中m為自然數，表示數據集中不同商品的數目。D為規模為N的事務集，即數據庫中交易記錄的集合，N為交易的數量(記錄數)，其中每一個事務t是一個項集，表示為t=t1,t2,…,tn，ti∈I，n為自然數，n≤m，表示事務t中商品的數目(項數)，即t?I。對于項集X，若X中含有的項數為k，則稱X為k-項集；若X?t，則稱事務t包含I的一個子集X。

事務集D中的關聯規則是一種由支持度(support)和置信度(confidence)約束的蘊含式X?Y，其中X?I，Y?I且X∩Y=?，支持度表示規則的頻度，置信度表示規則的強度。

(1)

在事務集D中，項集X的支持數是D中包含X的交易數，記為support_count(X)，如式(2)所示，support_count(X)∈{0,1,…,N}，即X的支持數是不大于交易記錄數N的一個自然數

(2)

在事務集D中，規則X?Y的置信度是D中同時包含X和Y的交易數與包含X的交易數之比，記為confidence(X?Y)，如式(3)所示，confidence(X?Y)∈[0,1]

(3)

2.2 關聯規則挖掘的一般流程

現有大多數關聯規則挖掘算法采用兩階段頻集思想，首先獲得事務集D的所有頻繁項集，然而基于頻繁項集進行關聯規則生成，挖掘的一般流程包括圖1所示的4個核心步驟。

圖1 基于頻繁項集的關聯規則挖掘的一般流程

圖1中，步驟1指定參數minsup和minconf的值是關聯規則挖掘的前提；步驟2在事務集中尋找所有k階頻繁項集是關聯規則挖掘的核心計算花銷所在，往往需要對事務數據集進行多趟掃描；在步驟2得到所有k階頻繁項集后，步驟3和步驟4則較為容易。

3 自適應關聯規則挖掘

3.1 算法思想

支持度和置信度自適應關聯規則挖掘算法AdapARM(adaptive association rule mining)的基本思想是：以事務集D中所有項的支持數和頻繁項集能產生的所有規則的置信度數據為依據，用數據說話、由數據決定支持度和置信度參數的取值，在支持數和置信度數據從大到小有序排列的基礎上，通過遞減序列不低于3次的多項式曲線擬合，尋找擬合曲線切線斜率變化速度(二階導數)首次為0、即擬合曲線凹凸轉換的拐點位置，作為最小支持數mincount和最小置信度minconf的取值。

由于支持數和置信度序列的單調遞減性和多項式擬合曲線的連續性，二階導數為0的地方是曲線變化由緩到急或由急到緩的轉折點，將二階導數首次為0的地方選取為支持數和置信度參數的閾值，具有較為科學的統計和數理分析依據。至于多項式擬合曲線的次數，由于2次多項式無法較好擬合支持數和置信度序列的單調遞減性，而1次多項式退化為直線，也無法用于確定參數的科學取值，因此使用不低于3階的多項式進行曲線擬合，從技術上確保了二階導函數及其支持數和置信度參數取值的存在性。

總之，算法通過數學的方法，使用擬合支持數和置信度序列的曲線及其二階導函數，確定數理意義上最適合的數值作為關聯規則挖掘的mincount和minconf閾值，能夠有效解決關聯規則挖掘算法對先驗知識的依賴問題。

3.2 核心步驟

傳統關聯規則挖掘通常要求算法用戶根據先驗知識事先指定最小支持度和最小置信度參數的值，而提出的算法AdapARM讓數據說話、根據數據集自身的特性，自適應地確定最小支持數和最小置信度的值。AdapARM的核心步驟如圖2所示，其中步驟2和步驟5：最小支持數和最小置信度的自動確定，是核心研究內容。

圖2 支持度和置信度自適應的關聯規則挖掘的核心步驟

3.3 支持度和置信度自適應的實現

首先，將事務集D中各商品(項)的支持數或某個規則的置信度，按從大到小的順序進行排序，建立“序-值”對序列(xp,yp)p=1,2,…,t(如圖3所示),其中序號值xp=p，序列值yp隨著序號值xp的遞增而遞減，即當xp

圖3 面向項支持數和規則置信度的“序-值”對

對于支持度，yx為某個項ix在事務D中支持數(即yx=support_count(ix))，“序-值”對的數目t為事務數據集D中商品(項)的數目，即t=m。

對于置信度，yx為頻繁項集生成的某個規則的置信度(即yx=confidence(X?Y))，“序-值”對的數目t為所有k階頻繁項集能夠產生的關聯規則的數目。

然后，基于“序-值”對數據，以序號值為x、序列值為y，建立有序的平面坐標(xv,yv)點序列(v=1,2,…,t)，并采用多項式進行曲線擬合。擬合的多項式曲線如式(4)所示

(4)

緊接著，求取以獲得擬合曲線的二階導函數f″(x)，如式(5)所示

(5)

從mincount和minconf的取值方法可見，其數值取決于所擬合的曲線f(x)，而f(x)主要由有序支持數或置信度構造而來的平面點序列(xv,yv)所刻畫。因此，可以說按提出方法自動獲得的mincount和minconf的取值，與事務集D中項的支持數與產生的規則的置信度的分布情況密切相關，能夠自適應地貼合數據集自身的特性。

3.4 AdapARM算法實現

支持度和置信度自適應的關聯規則挖掘算法AdapARM的偽代碼如下：

(1)C1= find_candidate_1-itemsets(D); //get all items’s support count

(4)findminix0,wheref″(x0)=0; //compute second derivative and get the minimal resolution

(6){L1,L2, …,Lk}=find_all_frequent_k-itemsets(D,mincount); //accordingmincount

(7){R1,R2, …,Rt}=generateRule_from_frequent_k-itemsets({L1,L2, …,Lk}); //generate rules

(8)R′=sort_InDescOrder({R1,R2, …,Rt}); //sort rules in descending order according the rule confidence

(9)y=h(x)=polynomial_curve_fitting(R′); //(x=order id,y=rule confidence)

(10)findminix0,whereh″(x0)=0; //compute second derivative and get the minimal resolution

(11)minconf=h(x0); //minconfis defined as the valueh(x0)

(12){SR1,SR2, …,SRr}=find_strong_rules({R1,R2, …,Rt},minconf); //find strong rules withminconf

首先，掃描一次數據庫，產生候選1項集C1；

緊接著，根據最小支持數閾值mincount，尋找所有k階頻繁項集。

再接著，通過所有k階頻繁項集，生成關聯規則，并根據規則置信度值從大到小的方式對規則進行降序排列，對序號與規則置信度值進行多項式曲線擬合，尋找二階導數為0的點x0，并將x0對應的擬合曲線函數值h(x0)作為最小置信度閾值minconf。

最后，依據最小置信度閾值minconf，篩選并獲得所有強關聯規則。

4 實驗及分析

本節使用關聯規則挖掘購物車Trolley數據集和開源軟件R GUI里的Groceries數據集，對無須用戶指定支持度和置信度參數的AdapARM算法的挖掘流程進行介紹，并對挖掘結果進行分析與討論，從而驗證提出算法在自動確定參數上的有效性和實用性。

4.1 數據集說明

Trolley數據集是很多數據挖掘教材中用于講解Apriori和FP_Growth算法的某面包店仿真交易記錄，總共有7個不同商品，有9條消費記錄(即9行)，如表1第2列所示。

Groceries數據集記錄了某個雜貨店一個月的真實交易記錄，總共有169個不同商品，有9835條消費記錄(即9835行)，如表1第3列所示(僅列舉前9條事務記錄)。

4.2 挖掘流程

步驟1 計算各數據項的支持數

遍歷數據集，獲得每個事務項的支持數，即獲得候選1項集C1中各項的支持數，并按支持數從大到小對項進行排序，見表2(僅列舉支持數最大的前7個項)。

表1 Trolley數據集和Groceries數據集

表2 數據集Trolley和Groceries中C1各項的支持數和排序號信息

步驟2 根據支持數從大到小排序數據項并進行曲線擬合

將Trolley數據集和Groceries數據集中各數據項的支持數，按從大到小的方式進行排序并使用3次多項式對數據進行曲線擬合，支持數與序值對應關系及其擬合曲線如圖4所示。

Trolley數據項的支持數擬合曲線如式(6)所示

fT(x)=4.2857142857+3.5595238095·x-
1.1428571429·x2+0.0833333333·x3

(6)

Groceries數據項的支持數擬合曲線如式(7)所示

fG(x)=1486.065650975-42.7627470864·x+
0.4135366641·x2-0.001283055089·x3

(7)

步驟3 根據擬合曲線的二階導函數求取最小支持數

(8)

(9)

步驟4 根據最小支持數獲得所有k階頻繁項集

根據獲得的最小支持數(Trolley數據集為4、Groce-ries數據集為107)，按照經典Apriori算法的思想，從一階頻繁項開始逐階向上，獲得數據集對應的所有k階頻繁項集。

Trolley數據集和Groceries數據集的所有k階頻繁項集

如表3所示，其中NULL表示“空”。

步驟5 根據頻繁項集產生關聯規則

根據獲得的所有k階頻繁項集(見表3)，為Trolley數據集和Groceries數據集產生關聯規則，見表4。

步驟6 根據置信度從大到小排序頻繁項集產生的規則

表3 Trolley數據集和Groceries數據集的所有頻繁項集

表4 Trolley數據集和Groceries數據集頻繁項集產生的關聯規則

并進行曲線擬合

根據Trolley數據集和Groceries數據集頻繁項集產生的關聯規則的置信度，按從大到小的方式進行排序并使用3次多項式對數據進行曲線擬合，置信度與序值對應關系及其擬合曲線如圖5所示。

Trolley數據集產生的規則的置信度擬合曲線如式(10)所示

hT(x)=0.9357665007-0.0199431001·x+
4.0050650021E-4·x2-5.6182859607E-6·x3

(10)

圖5 從大到小有序的規則置信度及其擬合曲線

Groceries數據集產生的規則的置信度擬合曲線如式(11)所示

hG(x)=0.5230242099-0.0027245952246·x+
6.7022637026E-6·x2-6.426271112E-9·x3

(11)

步驟7 根據擬合曲線的二階導函數求取最小置信度

(12)

(13)

步驟8 根據置信度閾值判斷并獲得強關聯規則

根據設定的置信度閾值(Trolley數據集為0.6126373314、Groceries數據集為0.1158444298)，獲得Trolley數據集和Groceries數據集對應的強關聯規則，見表5。

表5 Trolley數據集和Groceries數據集中的強關聯規則

4.3 結果分析與討論

從上述數據挖掘流程可見，與傳統算法需要用戶預先指定最小支持度minsup和最小置信度minconf的具體數值不同，譬如最小支持度取值為50%、最小置信度取值為80%，提出的AdapARM算法不需要用戶指定任何算法參數值，算法將根據不同的數據集，自動確定mincount和minconf的值。對Trolley數據集，自動確定的mincount值為4，minconf值為61.26373314%；對Groceries數據集，自動確定的mincount值為107，minconf值為11.58444298%。可見，AdapARM算法能夠在用戶不具備先驗知識的前提下，自動確定參數minsup和minconf的值，且參數值與具體的數據集相適應，而不需要由用戶進行算法參數值的人為指定，從而為關聯規則挖掘任務的無參化運行提供了一種統計學意義上具有較高可信性的解決方案。

盡管如此，提出的方案經過進一步處理，仍能為實際關聯規則挖掘任務的參數確定提供一定的借鑒。有效的閾值二次確定技術如：在最高支持數(或置信度)和自適應支持數(或置信度)之間，采用第一四分位數(Q1)、第二四分位數(Q2)、第三四分位數(Q3)作為最終選定的支持數(或置信度)的值。

總之，算法在確定支持度和置信度閾值時，通過計算所有數據項的支持數和所有規則的置信度，經從大到小排序后進行多項式曲線擬合，用數據說話、憑數據進行算法參數決策，使得算法在實際行業應用中走向科學，對于算法的推廣應用乃至普及具有重要的實踐意義。

5 結束語

本文提出了一個支持度和置信度自適應的關聯規則挖掘算法AdapARM，能夠在用戶不具備先驗知識、不指定支持度和置信度閾值的情況下，通過數據集自身的數據特征自適應地確定關聯規則挖掘的支持數和置信度。支持度和置信度參數的自適應確定策略：是在數據集所有項的支持數、所有規則的置信度的有序序列的多項式曲線擬合的基礎上，通過求取擬合曲線二階導函數為零的點x0及其函數值f(x0)，作為支持數和置信度閾值，進而挖掘統計意義上支持度和置信度較高的強關聯規則。在關聯規則挖掘標準數據集Trolley和標準數據集Groceries上的實驗結果及分析表明，提出的方法對于關聯規則挖掘算法的實施和推廣具有一定的實際應用價值。