謝笑盈， 徐應(yīng)濤， 張 瑩

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

0 引 言

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

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

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

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

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

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

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

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

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

1 理論與方法分析

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

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

為了評價分類模型的分類效果，構(gòu)造了準(zhǔn)確率(P)、召回率(R)和F1度量3個指標(biāo),即

(1)

(2)

(3)

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

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

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

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

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

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

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

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

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

其中，λ是形狀參數(shù).

1.1 基于抽樣學(xué)習(xí)的關(guān)聯(lián)規(guī)則算法設(shè)計

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

(4)

1.2 基于抽樣學(xué)習(xí)的關(guān)聯(lián)規(guī)則算法實現(xiàn)

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

輸入：進行過簡單預(yù)處理的數(shù)據(jù)總體

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

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

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

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

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

2 實證分析

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

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

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

3 效果評估

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

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

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

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

表3 學(xué)習(xí)曲線上特殊容量樣本產(chǎn)生的頻繁項集數(shù)對比

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

表4 學(xué)習(xí)曲線上各樣本在相同支持度與置信度下產(chǎn)生的規(guī)則數(shù)對比

4 結(jié)論與展望

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

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

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

在未來的研究中，還有以下幾個方面的挑戰(zhàn)：一是在刻畫累進抽樣的學(xué)習(xí)曲線時如何產(chǎn)生抽樣序列,使得學(xué)習(xí)曲線的行為更良好；二是如何處理低支持度且高置信度規(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.