鄧 毅，鄧曉慧

（1.重慶科創(chuàng)職業(yè)學(xué)院 人工智能學(xué)院，重慶 永川 402160 2.重慶城市職業(yè)學(xué)院 商學(xué)院，重慶 永川 402160）

1 Apriori算法概述

AIS算法是較早被用來解決關(guān)聯(lián)規(guī)則問題的算法，但此算法在使用的過程中性能較低，于是Agrawal等人在此前的應(yīng)用基礎(chǔ)上，對AIS算法進行了相關(guān)的改造，Apriori算法此時便被提出來了，且成為利用關(guān)聯(lián)規(guī)則進行數(shù)據(jù)挖掘較好算法之一[1]。依據(jù)Apriori算法，延伸出了類似Apriori-Hybrid、DIC、AprioriTid、DHP等算法。

1.1 Apriori算法過程

在Apriori算法運行之前，用戶需要首先設(shè)定好最小支持度，一旦開始掃描事務(wù)數(shù)據(jù)庫時，就僅計算每一個項目的具體值的數(shù)量，來確定大型1--項集，后面的n次遍歷，都將重復(fù)連接與剪枝的操作，直到產(chǎn)生的項為空，停止算法。該算法的流程圖如圖1所示[2]。

圖1 算法執(zhí)行過程

該算法通過逐層的迭代來得到需要的頻繁項集，獲取頻繁項集的算法偽代碼如下所示：

算法：Apriori算法生成頻繁項集

輸入：事務(wù)庫D；最小支持度閥值minSup

輸出：D中的頻繁項集L

方法：

L1={發(fā)現(xiàn)頻繁1-項集}；

For(n=2;Ln-1≠φ;n++)

{

Cn=apriori_produce(Ln-1,minSup);

for each transactionT∈D{

CT=sub set(Cn,T);

for all candidate c∈CT

C.count++;

}

Ln={c∈Cn|c.count≥min Sup}

}

Return L={UnLn}

在該算法的偽代碼方法中，Ln-1和min S up這兩個值作為函數(shù)apriori_produce的參數(shù)值被代入，獲取了候選n-項集Cn,這個函數(shù)進行了兩個操作：連接操作、剪枝操作，如下所示的實現(xiàn)步驟[3]：

Function apriori_gen(Ln-1,minsup)

For each itemset S1∈Ln-1

For each itemset S2∈Ln-1

c=s1?s2;

If exist_infrenquent_subset(c,Ln-1)

{

Delete c;

}

Else fill cnwith c;

}

Return cn

在完成了上述的n--項集后，使用Apriori的性質(zhì)，需要對Cn進行剪枝的操作，刪除掉擁有非頻繁子集的候選。用于對非頻繁子集測試的函數(shù)實現(xiàn)如下：

Function exist_infrenquent_subset(c,Ln-1)

for each(n-1)-subset p of c

If p?Ln-1

Return true;

Return false;

1.2 Apriori算法實例解析

由于偽代碼語言并不能夠清晰的說明Apriori算法的執(zhí)行過程，接下來將通過一個使用該算法產(chǎn)生關(guān)聯(lián)規(guī)則的例子來說明。如表1所示的交易數(shù)據(jù)庫Q。

表1 交易數(shù)據(jù)庫Q

在算法實施的過程中，支持度用項集出現(xiàn)的次數(shù)來表示，設(shè)定挖掘的過程中，最小支持度的閥值為2，該算法的執(zhí)行步驟如下：

首先，生產(chǎn)頻繁項集。當對交易數(shù)據(jù)庫Q完成掃描后，會得到候選1-項集C1：{M1}、{M2}、{M3}、{M4}、{M5}。因為生成的每個項集的支持度的值都大于或者等于設(shè)定的2，所以C1中的所有的項集都被包含在1-項集L1中。

對第一環(huán)節(jié)中的1-項集L1進行自連接，得到候選2-項集C2：{M1,M2}、{M1,M3}、{M1,M4}、{M1,M5}、{M2,M3}、{M2,M4}、{M2,M5}、{M3,M4}、{M3,M5}、{M4,M5}，在L1中包含了他們所有的子集，不需要剪枝操作[4]。接著完成這些候選項集的支持度計算，結(jié)果如下：{M1,M4}、{M3,M4}、{M3,M5}、{M4,M5}支持度的值小于設(shè)定的閥值2。說明這些不是頻繁2-項集的內(nèi)容，其余都是。

2-項集C2進行自連接操作產(chǎn)生3-項集C3：{M1,M2,M3}、{M1,M2,M5}、{M1,M3,M5}、{M1,M3,M4}、{M2,M3,M5}、{M2,M4,M5}。因為{M3,M5}、{M3,M4}、{M4,M5}都不在L2里面，所以可根據(jù)Apriori的性質(zhì)得出后面四個選項是可以被剪枝的。只需要對候選項集{M1,M2,M3}、{M1,M2,M5}進行計數(shù)，就可以獲得3-項集C3。

3-項集L3進行自連接就可以獲取到4-項集C4：{M1,M2,M3,M5}，由于{M1,M3,M5}不在L3里面，所以要進行剪枝，最后得到L4為空集，到此為止，算法計算完成。

最后經(jīng)過Apriori算法得到的頻繁項集為：{M1}、{M2}、{M3}、{M4}、{M5}、{M1,M2}、{M1,M3}、{M1,M5}、{M2,M3}、{M2,M4}、{M2,M5}、{M1,M2,M3}、{M1,M2,M5}。

然后，將以上得到的所有的頻繁項集繼續(xù)處理，得到需要的強關(guān)聯(lián)規(guī)則。拿{M1.M2,M3}為例進行說明，{M1,M2,M3}的全部非空子集為：{M1}、{M2}、{M3}、{M1,M2}、{M1,M3}、{M2,M3}，那么可能的關(guān)聯(lián)規(guī)則計算如下：

如果將最小置信度的閥值設(shè)定為40%，那么就可以將上述計算得到的Confidence的值與設(shè)定的40%進行比較，選取其中大于該值的規(guī)則。從上面的計算結(jié)果來看，第4、5、6條規(guī)則滿足條件，即得到這幾條是強關(guān)聯(lián)規(guī)則。

按照以上的方法對其他的頻繁項項進行類似的操作，就可以得到全部的規(guī)則。

2 Apriori算法的性能分析

Apriori算法的核心思想為：候選產(chǎn)生-檢查。這種方法的優(yōu)點為：對候選K-項集采取了有效的裁剪，可以大大的降低了候選集的大小，從而減少了計算量。缺點為：當設(shè)定的最小支持度的閥值比較小，相反事務(wù)集量較大，就會表現(xiàn)出性能上的不足，主要體現(xiàn)在以下幾個方面[5]。

第一掃描事務(wù)數(shù)據(jù)庫次數(shù)較多；

第二可能會生成較大的候選集；

第三產(chǎn)生過多的無用的規(guī)則。

2.1 Apriori算法的優(yōu)化

通過上文對Apriori算法的介紹和分析，該算法容易被人理解和接受，但是其也存在需要解決的問題，需要對該算法進行部分的優(yōu)化。通過查閱相關(guān)的文獻資料，專家及學(xué)者對該算法的優(yōu)化思想，主要有以下幾個方面。

2.1.1 基于哈希的方法

該方法的主要思想為：將哈希技術(shù)運用到頻繁2-項集的獲取上面。如果最小支持度的閥值大于某一個K-項集在哈希樹路徑上的計數(shù)值，那么該項不會是頻繁的。

2.1.2 降低交易個數(shù)的方法

該方法的原理為：不包括任何K-項集的事務(wù)一定不包括（K+1）項集。通過使用該方法減少未來需要掃描的事務(wù)記錄，從而提高算法的效率[6]。

2.1.3 基于采樣的方法

該方法通過抽取數(shù)據(jù)集中的部分數(shù)據(jù)作為樣本，得到可能在整個數(shù)據(jù)集中成立的規(guī)則，然后利用未作為樣本的數(shù)據(jù)進行規(guī)則的驗證。此種方法減少了I/O的操作，但是降低了數(shù)據(jù)的精度，可能會導(dǎo)致數(shù)據(jù)扭曲，針對此種現(xiàn)象，很多學(xué)者也討論了反扭曲的相關(guān)算法[7]。

2.1.4 間隔計算的方法

該方法的過程為：首先由CK直接生成CK+1，得到CK+1的支持度進而獲取LK+1，從而不需要計算的CK支持度來獲LK，減少了數(shù)據(jù)庫的一次掃描。使用該方法的前提條件是生成的候選項目集CK+1要能夠被放進內(nèi)存。

3 Apriori算法改進

3.1 Apriori算法改進思想

通過對Apriori算法性能及算法思想的分析，該算法還是存在一定的缺陷[8]。盡管很多的專家學(xué)者針對某些缺陷，提出了一些解決方法，但仍然有掃描事務(wù)數(shù)據(jù)庫次數(shù)較多，準確度不精準的問題，主要體現(xiàn)在以下兩個方面：

第一為了獲取候選頻繁集的支持度，需要多次掃描事務(wù)庫，I/O的開銷很大，當數(shù)據(jù)的量較大時，算法的執(zhí)行效率低下，花費的時間較長[9]。

第二在頻繁集連接時，沒有考慮到現(xiàn)實的意義，讓很多無關(guān)項集參與到了連接，導(dǎo)致了大量的候選項集產(chǎn)生，最后也導(dǎo)致了自連接和后剪枝的量的增加。

在本次的研究中，針對第2個問題進行改進，主要在原Apriori算法基礎(chǔ)上引入事先剪枝的方法，來降低候選集的數(shù)目，從而提高數(shù)據(jù)挖掘的效率。

3.2 事先剪枝策略

Apriori原算法是LK-1在進行自連接后，可以得到候選集CK，利用算法的性質(zhì)對CK進行剪枝操作。改進之后的思想為：如果在CK被生成之前就能夠判斷出那些非頻繁，那么就可以提前剪掉這些項集。優(yōu)點為：避免了為產(chǎn)生這些項集的連接操作，同時也省去了在掃描事務(wù)庫時的支持度頻度需要計算的問題，進而減少了算法計算的時間，下面結(jié)合頻繁項集的幾個性質(zhì)來進行算法改進的說明。

第一如果K-項集X是頻繁項集，那么X下的全部（K-1）項子集都是頻繁項集；

第二如果K-項集X里面（K-1）項子集不是頻繁項集，那么X就不會是頻繁項目集；

第三如果K-項集X={i1,i2,...,ik}中，滿足S∈X，且LK-1(S)

對第3條性質(zhì)進行證明：若X是頻繁K-項集，則LK-1包含K個K-1項子集。在這些子集中，單個項目S(S∈X)總計出現(xiàn)了k-1次，因此對?S∈X，都滿足|LK-1(S)|≥K-1，和條件矛盾，所以X不是頻繁項目集。

由第三條性質(zhì)可以得到，如果LK-1里面有元素L包含了s,滿足|LK-1(S)|≥K-1，那么LK-1中除去之外的L全部元素與L連接，得到的K-項集全部不是頻繁項目集。由L進行連接得到的候選K-項集是非頻繁的，就不需要讓L加入連接。

結(jié)合上述的相關(guān)性質(zhì)，具體的事先剪枝實施步 驟 如 下 ：第 一 算 出 |LK-1(S)|，其 中S∈{?A|A∈LK-1}，則算出LK-1中單個項目出現(xiàn)的次數(shù)；第二記錄頻度低于K-1的項目，標記為U={S||LK-1(S)

在完成第4步的L'K-1的自連接之后，使用原Apriori中的后剪枝可以進一步的減少候選集的規(guī)模。使用改進的事先剪枝策略可以實現(xiàn)降低頻繁項集連接操作的時間花銷，也實現(xiàn)了降低后剪枝操作時的工作量。使用該策略減少了候選項集的數(shù)量，同時變相的也減少了掃描數(shù)據(jù)庫的I/O開銷，降低了算法的運行的時間復(fù)雜度[10]。

4 算法改進性能評價

為了能夠獲取改進后算法的性能，本小結(jié)將改進前后的算法進行比較分析。實驗比較的數(shù)據(jù)分為兩個方面：在不同的最小支持度閥值下，產(chǎn)生的候選集數(shù)量和運行的時間。

實驗環(huán)境：

操作系統(tǒng)：windows 7 Professional。

仿真環(huán)境：Matlab R2012a。

測試使用數(shù)據(jù)：選取UCI標準測試數(shù)據(jù)集Mushroom,此種數(shù)據(jù)的特征就是頻繁項目集密集分布。

實驗步驟：

第一使用相同的數(shù)據(jù)集，設(shè)置不同的最小支持度閥值，比較改進前后的不同支持度下的候選集數(shù)量，如圖2所示。隨著最小支持度的閥值的增加，候選集的數(shù)目都在減少，但是在相同的支持度下，改進后的算法生成的候選集數(shù)目要少于改進前。

圖2 不同支持度下的候選項集

第二使用相同的數(shù)據(jù)集，設(shè)置不同的最小支持度閥值，比較改進前后的運行時間，如圖3所示。通過實驗結(jié)果表明：改進過后的算法在不同的支持度下的運行時間都要小于改進之前的運行時間。

圖3 不同支持度下的運行時間

5 基于U檢驗思想置信度評價

在實際的關(guān)聯(lián)規(guī)則挖掘中，基于傳統(tǒng)的支持度-置信度的Apriori算法存在著一些問題。例如：不能夠得到更加有效的關(guān)聯(lián)規(guī)則。針對此問題，本論文在研究時，在Apriori算法基礎(chǔ)上，采用了基于U檢驗思想衡量標準，即：通過限制、約束關(guān)聯(lián)規(guī)則的產(chǎn)生方式，得到需要的強關(guān)聯(lián)規(guī)則。

U檢驗數(shù)學(xué)算法思想：設(shè)一個擁有K屬性的總體樣本為S，對象的總個數(shù)為計為n,擁有K屬性的對象個數(shù)為m,那么具備該條件的對象在S中的比率為：P=m/n。使用U檢驗，可以比較總體百分數(shù)P0與樣本百分數(shù)P之間的差異。該差異值用標準差SP，計算公式如下所示。

利用以上的兩個公式，可以得到如下的差異關(guān)系：

(1)|u|

(2)u0.05≤|u|

(3)|u|≥u0.01，p與p0顯著性差異很大。

在事務(wù)集L中，一個X項對另外一個Y項的影響度的大小，可以利用期望置信度及置信度之間的差異來表現(xiàn)。結(jié)合上述的公式，得到關(guān)聯(lián)規(guī)則的影響度定義公式如下：

若P(Y)=1且P(X)<1,規(guī)則的影響度值為0;

當滿足最小支持度和最小置信度時，依據(jù)影響度，可以將支持度-置信度生成的規(guī)則分為三類，如表2所示。

表2 關(guān)聯(lián)規(guī)則分類a

在T分布下，一個樣本容量為n,ua表示為顯著水平為a下的臨界值u的最小影響度。如果n的值比較的大，可以得到ta(n)≈ua，ua為臨界u值。如果e ffect(x?y)>ua，那么此時得到的關(guān)聯(lián)規(guī)則為正關(guān)聯(lián)規(guī)則，是值得研究的規(guī)則。一般取a=0.05作為顯著性校驗水準，此時得到u0.05=1.96。依據(jù)臨界值的大小和影響度的大小，在本次的研究中，表明可以得到置信度較高的規(guī)則。

6 結(jié)語

本文在針對關(guān)聯(lián)規(guī)則算法Apriori算法掃描次數(shù)過多、產(chǎn)生過多無關(guān)規(guī)則及算法效率不高的問題，采用了事先剪枝的方法進行改進，通過使用Matlab對改進的算法進行了評測，同時使用了U檢驗思想衡量標準的算法對評測的結(jié)果進行信度測算，實驗結(jié)果表明，改進后的算法較好的解決了以上的問題，在后續(xù)的研究中，可以進一步的優(yōu)化算法產(chǎn)生更強的關(guān)聯(lián)性規(guī)則。