基于抽樣學習的關聯(lián)挖掘算法設計

謝笑盈， 徐應濤， 張 瑩

(1.浙江師范大學 經濟與管理學院,浙江 金華 321004;2.浙江師范大學 行知學院,浙江 金華 321004;3.浙江師范大學 數理與信息工程學院,浙江 金華 321004)

0 引 言

關聯(lián)規(guī)則[1]是Agarwal于1994年首次提出的、旨在分析購物籃中各商品之間關聯(lián)性的數據分析方法，該方法能從數據集中找到滿足最小支持度(minsup)和最小置信度(minconf)閾值的規(guī)則.按照Agarwal的原始提法，要在數據集中提取出關聯(lián)規(guī)則，需要計算每個可能規(guī)則的支持度和置信度，這種方法的時空代價太高，因為一個包含d個屬性的數據集中能提取的可能規(guī)則的個數為r=3d-2d+1+1，若最小支持度為20%，最小置信度為50%，則80%以上的規(guī)則將被丟棄，使得大部分的計算是無用的.為了提高挖掘效率，避免進行不必要的計算，統(tǒng)計學界及計算機學界的學者紛紛提出了不同的解決方法.

抽樣技術是統(tǒng)計學中常常被用來獲取有效信息的經典方法，近十幾年來，抽樣的方法也開始被許多學者用來提高關聯(lián)挖掘的效率.這些研究主要包含兩大類：一類是靜態(tài)抽樣的方法，即根據數理統(tǒng)計的方法計算出一個能代替總體進行關聯(lián)分析的樣本容量，再用隨機抽樣的方法抽得該樣本；另一類是動態(tài)抽樣(常分為累進抽樣和自適應抽樣)的方法，即容量從小到大不斷地從總體中抽出樣本，同時為抽樣設計一個停止抽取的規(guī)則，當樣本的容量達到抽樣停止閾值時，停止抽樣，獲得的樣本被稱為最優(yōu)樣本，將作為總體的替代數據集進行關聯(lián)分析.這種描述樣本容量與模型準確度之間關系的曲線稱為動態(tài)抽樣的學習曲線[2]，如圖1所示.

圖1 動態(tài)抽樣的學習曲線

學習曲線的橫軸代表一個樣本序列，縱軸代表樣本序列對應的準確度值.典型的學習曲線分為3個演變階段：坡度陡峭階段、坡度相對平緩階段和坡度為零階段.其中，第2和第3階段的連接點nmin代表的樣本容量通常被稱為最優(yōu)樣本容量OSS(optimal sample size)，對應的樣本被稱為最優(yōu)樣本OS(optimal sample).因為所有容量大于nmin的樣本的準確度不再有顯著提升，而所有容量小于nmin的樣本的準確度都比它小，所以繪制學習曲線的目的就是要找到nmin，并用它對應的樣本完成挖掘任務.要找到nmin并不是容易的事情，就關聯(lián)挖掘而言，學者們就如何設置高效簡便的抽樣停止規(guī)則做了很多研究，下面就一些有代表性的抽樣方法進行綜述.

文獻[3]設計了一種基于動態(tài)抽樣的關聯(lián)分析方法，這個方法的新穎之處在于設計了動態(tài)樣本的關聯(lián)規(guī)則相似度Sim(d1,d2),d1,d2是前后抽取的2個樣本.當這2個樣本的相似度值接近1時，2個樣本上產生的關聯(lián)規(guī)則不再有變化，進一步的抽樣也不會再產生新的關聯(lián)規(guī)則，此時就可以認為找到了可以代替總體進行關聯(lián)規(guī)則挖掘的樣本了.

文獻[4]提出了一種針對關聯(lián)分析的兩步抽樣法.第1步，隨機抽取一個容量較大的初始樣本，并計算出該樣本中各個項的支持度；第2步，以前一步計算的支持度作為閾值去刪除“孤立點”，留下具有代表性的項，構成一個能較好反映總體統(tǒng)計性質的容量較小的最終樣本.在這個最終樣本上的關聯(lián)分析結果被證明能較好地反映總體上的關聯(lián)規(guī)則.

文獻[5]設計了一種被稱為抽樣錯誤估計(sampling error estimation(SEE))的動態(tài)抽樣方法,認為:隨著樣本容量的不斷增加，在樣本上進行關聯(lián)分析產生的錯誤將不斷減少，如果將所有頻繁項在樣本上的支持度和它在總體上的支持度之差的均方根定義為錯誤度量值，那么，當這個均方根的值不再有顯著變化時，就可以認為找到了代替總體進行關聯(lián)分析的最優(yōu)樣本.

除上述的方法以外，文獻[6]設計了Epsilon Approximation Sample Enabled(EASE)的抽樣方法；文獻[7]設計了EASIER方法，對EASE進行了改進；文獻[8]利用馬爾科夫鏈建立網絡，并通過隨機游走的方法抽取網絡上的節(jié)點進入樣本，解決了關聯(lián)規(guī)則挖掘中項集提取的問題；文獻[9-10]設計了一種基于序列插值的累進抽樣法來提高關聯(lián)挖掘的效率；文獻[11]設計了一種基于新的累進抽樣的方法，提高了關聯(lián)挖掘的效率；文獻[12]設計了從特征空間抽取隨機樣本序列的方法，以確定關聯(lián)規(guī)則的方向性；文獻[13]設計了micro-randomized方法，獲得隨機的關聯(lián)項集，改進了Apriori方法的執(zhí)行效率；文獻[14]設計了Gibbs-sampling方法，減少了參加關聯(lián)挖掘的項集個數，并在精簡的特征空間中進行隨后的關聯(lián)挖掘.這些方法在尋找最優(yōu)樣本的過程中大多數都需要多次執(zhí)行關聯(lián)挖掘，可能會使抽樣引起的開銷大于其為挖掘帶來的效率.

本文從數據挖掘中分類器性能比較的度量方法上得到啟發(fā)，將這種度量方法引入到累進抽樣的學習曲線構建中，在不執(zhí)行關聯(lián)挖掘的前提下，設計了一種新穎的累進抽樣方法，利用關聯(lián)規(guī)則的支持度找到一個能代替總體進行關聯(lián)分析的最優(yōu)樣本.

1 理論與方法分析

在利用分類模型對不平衡數據進行分類挖掘時，通常需要對挖掘結果進行評價.對于二元分類，稀有類通常記為正類，而多數類記為負類.表1顯示了匯總分類模型正確和不正確預測的實例數目的混淆矩陣.其中：真正數(f+,+(TP))(或簡稱TP)是指被分類模型正確預測的正樣本數；假負數(f+,-(FN))(或簡稱FN)是指被分類模型錯誤預測為負類的正樣本數；假正數(f-,+(FP))(或簡稱FP)是指被分類模型錯誤預測為正類的負樣本數；真負數(f-,-(TN))(或簡稱TN)是指被正確預測的負樣本數.

表1 二元分類問題的混淆矩陣

為了評價分類模型的分類效果，構造了準確率(P)、召回率(R)和F1度量3個指標,即

(1)

(2)

(3)

式(1)～式(3)中:P反映被分類模型預測為正類的樣本中實際為正類的樣本所占的比例；R反映所有的正類中能被分類模型正確預測的樣本所占的比例.要使分類模型的性能良好，通常會平衡準確率和召回率的值，因為前者越大，犯假正類的錯誤就越小;后者越大，犯假負類的錯誤就越小.因此，將P和R合并成另一個度量，稱為F1度量,該度量是準確率與召回率的調和平均數.

從式(1)和式(2)容易看出,P，R其實就是2個條件概率，可表示為

P=p(L=+/Z=+),R=p(Z=+/L=+).

進一步得，TP,FP,TN,FN服從參數為(λTP,λFP,λTN,λFN)的多項分布，即

P(D=(TP,FP,TN,FN))=

λTP+λFP+λTN+λFN=1.

其中：λTP，λFP，λTN，λFN分別表示分類挖掘結果中TP,FP,TN,FN實例數目占所有實例數目的比例.由多項分布的邊緣分布和條件分布的性質，可寫出P的似然函數為

L(p)=P(D|p)∝pTP(1-p)FP.

根據貝葉斯規(guī)則和先驗分布假設可推出

其中，λ是形狀參數.

1.1 基于抽樣學習的關聯(lián)規(guī)則算法設計

為了提高關聯(lián)分析的效率，從總體中抽出一個樣本，理想的，若抽到的樣本中各個n-項集的頻繁性與它們在總體中的頻繁性相同，頻繁度相似，則樣本所產生的關聯(lián)規(guī)則與總體產生的關聯(lián)規(guī)則基本相同.但尋找和比較所有的項集是沒有必要的，因為頻繁項集具有向下覆蓋性(若1-項集是非頻繁的，則包含它的2-，3-,…項集都是非頻繁的)，所以只需要考察所有1-項集的頻繁度即可.在總體D中設置一個最小支持度閾值minsup(D)，同時為最終的樣本設置一個最小支持度閾值minsup(S)，總體D中的1-項集在隨機抽樣后以某個概率P進入樣本S，相應的會產生4種情況：1)在D中頻繁而在S中不頻繁；2)在D中不頻繁而在S中頻繁；3)在D和S中都頻繁；4)在D和S中都不頻繁.根據表1所介紹的分類模型的混淆矩陣評估抽樣的效果，抽樣后對樣本中的1-項集的頻繁性產生了一個“預測”：第1種情況可表述為FN，第2種情況可表述為FP，第3種情況可表述為TP，第4種情況可表述為TN.由此可設計一個讓抽樣學習停止的規(guī)則，并由該規(guī)則計算出停止抽樣的閾值.由此，產生了一個可代替總體進行關聯(lián)挖掘的最優(yōu)樣本OS，該樣本的容量即為最優(yōu)樣本容量OSS.本文設計的抽樣停止規(guī)則表述為

(4)

1.2 基于抽樣學習的關聯(lián)規(guī)則算法實現

本文所設計的基于累進抽樣的關聯(lián)分析算法簡單，只需瀏覽數據總體一次，且不必重復執(zhí)行關聯(lián)規(guī)則挖掘，在動態(tài)的抽樣學習過程中獲得最優(yōu)樣本，且只在最終的樣本上執(zhí)行一次關聯(lián)分析，無論在時間還是空間上都大大提高了挖掘的效率.以下給出該算法的描述：

輸入：進行過簡單預處理的數據總體

輸出：最優(yōu)樣本OS

步驟1：遍歷數據總體D以產生一個容量為ni=n0+200*i的隨機樣本序列{Si}，i=1,2,3,…,同時計算所有1-項集的支持度(包括總體和各個樣本中的1-項集).

步驟2：設置總體的最小支持度minsup(D)，各個樣本的最小支持度minsup(Si)=pi5minsup(D)，其中，pi=ni/N,N表示總體的容量.

步驟3：從S1開始計算F(Si)，當F(Sm)=F(Sm+1)=F(Sm+2)≈1時(為了避免隨機情況的發(fā)生，對相同容量的樣本進行若干次循環(huán)，以求得最大的F(Si)值，同時該等式可適當地延長至Sm+l，m+l

步驟4：用Sm+l代替D進行關聯(lián)分析,得到具有較強概率保證的關聯(lián)規(guī)則挖掘結果.

2 實證分析

本算法在Windows 7系統(tǒng)下、8.00 G內存、i7-5600 U處理器的PC機上進行了效果測試，所用的數據來自2010年第6次全國人口普查浙江省人口普查長表，共有26 823個樣本，17個屬性變量，這些變量都是人口普查表中個人填報的項目，包括年齡、性別、職業(yè)、婚姻狀況和受教育狀況等相關內容.本文為了分析驗證所設計的算法在關聯(lián)挖掘中的優(yōu)越性，以人口流動與就業(yè)分布的關聯(lián)關系為挖掘目的，對該數據集進行了必要的預處理，最終有26 823個樣本參加了關聯(lián)分析.

對比Apriori算法、EASE算法和EASEIER算法，可明顯看出該算法的優(yōu)越性.圖2是樣本容量以200為步長，從200到12 600時各個樣本與其對應的F(Si)值形成的學習曲線，其中，橫坐標表示樣本容量，縱坐標表示F(Si)值.與圖1所顯示的學習曲線的特性完全相同：當樣本容量在[0,2 600]時，坡度陡峭，F(Si)值從0急速過度到0.902 1，這說明總體中接近90%的1-項集的頻繁性被容量為2 600的這個樣本準確地“預測”了，那么總體中與這些1-項集相關的關聯(lián)規(guī)則都可以由這個樣本來產生，換句話說，由這個樣本產生的關聯(lián)規(guī)則與總體產生的關聯(lián)規(guī)則的一致率約為90%；當樣本容量在[2 600，11 200]時，坡度相對平緩，F(Si)值從0.902 1緩慢地過度到0.973 1，說明當樣本容量到達11 200時，總體中約97.31%的1-項集的頻繁性被這個樣本準確地“預測”了，若用這個樣本代替總體進行關聯(lián)挖掘，則準確率能達到97%左右；當樣本容量在[11 200,12 600]時，學習曲線的坡度幾乎為零，F(Si)值從0.973 1緩慢地趨于1，理論上說，總體的F(Si)值就等于1.如果以損失一部分的準確性為代價來提高挖掘效率，就可以選擇OSS=12 600，或者選擇更小的容量值.

樣本容量圖2 用F(Si)值刻畫的樣本學習曲線

3 效果評估

本節(jié)將對抽樣結果的有效性和可靠性進行評估：通過對抽樣序列的F1度量值對比來完成有效性的評估；通過對總體、最優(yōu)樣本和拐點樣本的關聯(lián)挖掘結果對比來完成可靠性評估.

從表2可以看出：隨著樣本容量的增加，樣本的F1度量值在逐漸增大，說明在此變化過程中，樣本容量越大，樣本對總體的頻繁度信息保留就越多，特別是當樣本容量達到由F(Si)值計算的最優(yōu)樣本容量時，F1度量值達到最大，此時的準確率P或者召回率R也將最大.因此，用樣本的F(Si)值作為抽樣停止的閾值這一抽樣策略是有效的.

從表3可以看出：對學習曲線上的幾個特殊點處的樣本進行關聯(lián)挖掘時，在相同的支持度和置信度評價前提下，隨著樣本容量的增加，樣本產生的1-項集，2-項集，…，6-項集的個數越來越接近于對總體進行挖掘時產生的項集個數，特別是當樣本的F(Si)值接近于1時，挖掘結果與總體幾乎完全一致，說明在該樣本容量下，抽樣引起的頻繁項集丟失問題可以被忽略，用該樣本進行關聯(lián)分析是可靠的.

表2 不同樣本容量下樣本的F1度量值對比

表3 學習曲線上特殊容量樣本產生的頻繁項集數對比

在相同的支持度閾值和置信度閾值下比較了學習曲線上各個特殊點樣本產生的規(guī)則個數，結果如表4所示.從表4可以看出，容量為11 200和12 600的樣本產生的規(guī)則個數與總體產生的規(guī)則個數非常接近.這一結果表明:根據F(Si)值產生的最優(yōu)樣本可以代替總體進行關聯(lián)分析，它們之間因為抽樣引起的關聯(lián)分析的誤差很小，用最優(yōu)樣本進行關聯(lián)挖掘是可靠的.

表4 學習曲線上各樣本在相同支持度與置信度下產生的規(guī)則數對比

4 結論與展望

根據關聯(lián)挖掘的特點設計了一種新穎的累進抽樣的方法，該方法將二元分類評估的混淆矩陣引入到因隨機抽樣引起的樣本1-項集頻繁性變動的問題中.因為頻繁1-項集的個數是關聯(lián)規(guī)則產生的基礎，是所有后續(xù)關聯(lián)挖掘的前提，所以本文設計的方法以此為切入點，針對抽樣后1-項集頻繁性變動的4種可能結果，以保證最終樣本中的頻繁1-項集個數與總體中的頻繁1-項集的個數相同為抽樣學習的目標，設計了累進抽樣的停止公式.

本文設計的抽樣停止公式以抽樣的真正數、假正數、真負數、假負數為基礎，以真正數和真負數最大化為獲取閾值的臨界點.根據抽樣過程中F(Si)值相對于樣本容量的變化關系來刻畫累進抽樣的學習曲線，然后根據學習曲線找到抽樣停止的樣本容量，并以該樣本作為代替總體進行關聯(lián)挖掘的最優(yōu)樣本.

為了驗證本文設計的抽樣學習公式是有效的、可靠的，用二元混淆矩陣的F1度量值進行評估.F1度量是抽樣的準確率(P)與召回率(R)的調和平均值，當F1度量值接近于穩(wěn)定值時，準確率或者召回率將達到最優(yōu)，穩(wěn)定值的選擇取決于召回率或準確率.實踐表明該抽樣方法是有效的、可靠的.

在未來的研究中，還有以下幾個方面的挑戰(zhàn)：一是在刻畫累進抽樣的學習曲線時如何產生抽樣序列,使得學習曲線的行為更良好；二是如何處理低支持度且高置信度規(guī)則的未入樣問題.

[1]Agarwal R,Srikant R.Fast algorithms for mining association rules[J].Journal of Computer Science and Technology,1994,15(6):619-624.

[2]Provost F,Jensen D，Oates T.Efficient progressive sampling[C]//Proc of the 5th Conf on Knowledge Discovery and Data Mining.New York:ACM Press,1999:23-32.

[3]Parthasarathy S，Zaki M J，Ogihara M，et al.Parallel data mining for association rules on shared memory system knowledge and information system[J].Knowl Inf Syst,2001,3(1):1-29.

[4]Chen B，Haas P，Scheuermann P.A new two phase sampling based algorithm for discovering association rules[C]//The 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Edmonton:ACM Press,2002:462-468.

[5]Chuang K T，Chen M S，Yang W C.Progressive sampling for association rules based on sampling error estimation[J].Lecture Notes in Computer Science,2005,3518(1):505-515.

[6]Dash M，Haas P,Haas P,et al.Efficient data reduction with EASE[C]//Proc of the 9th International Conference on KDD.Washington:ACM,2003:59-68.

[7]Wang S，Dash M，Chia L T.Efficient sampling:Application to image data[C]//Advances in Knowledge Discovery and Data Mining of the 9th Pacific-Asia Conference.Hanoi:ACM,2005.

[8]Fang M，Yin J，Zhu X.Supervised sampling for networked data[J].Signal Processing,2015,124(1):93-102.

[9]Umarani V，Punithavalli M.Developing novel and effective approach for association rule mining using progressive sampling[C]//The 2nd International Conference on Computer and Electrical Engineering.Dubai:UAE,2009.

[10]Umarani V,Punithavalli M.On developing an effectual progressive sampling based approach for association rule discovery[C]//International Conference on Information Management & Engineering.Chengdu:IEEE,2010.

[11]Chakaravarthy V T，Pandit V，Sabharwal Y.Analysis of sampling techniques for association rule mining[C]//Database Theory:The 12th International Conference.Petersberg:ICDT,2009.

[12]Lopez-Paz D，Muandet K，Sch?lkopf B,et al.Towards a learning theory of cause-effect inference[C]//The 32th International Conference on Machine Learning.Lille:JMLR,2015.

[13]Rutterford C，Copas A，Eldridge S.Methods for sample size determination in cluster randomized trials[J].International Journal of Epidemiology,2015,44(3):1051-1067.

[14]Qian G，Rao C R,Sun X,et al.Boosting association rule mining in large datasets via Gibbs sampling[J].Proceedings of the National Academy of Sciences,2016,13(18):4958-4963.

[15]Goutte C，Gaussier E.A probabilistic interpretation of precision recall andF-score,with implication for evaluation[J].Chapman and Hall,1979,3408(2):345-359.