一種改進(jìn)型關(guān)聯(lián)規(guī)則算法設(shè)計(jì)與研究

鄧 毅，鄧曉慧

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

1 Apriori算法概述

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

1.1 Apriori算法過(guò)程

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

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

該算法通過(guò)逐層的迭代來(lái)得到需要的頻繁項(xiàng)集，獲取頻繁項(xiàng)集的算法偽代碼如下所示：

算法：Apriori算法生成頻繁項(xiàng)集

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

輸出：D中的頻繁項(xiàng)集L

方法：

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

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這兩個(gè)值作為函數(shù)apriori_produce的參數(shù)值被代入，獲取了候選n-項(xiàng)集Cn,這個(gè)函數(shù)進(jìn)行了兩個(gè)操作：連接操作、剪枝操作，如下所示的實(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--項(xiàng)集后，使用Apriori的性質(zhì)，需要對(duì)Cn進(jìn)行剪枝的操作，刪除掉擁有非頻繁子集的候選。用于對(duì)非頻繁子集測(cè)試的函數(shù)實(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算法實(shí)例解析

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

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

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

首先，生產(chǎn)頻繁項(xiàng)集。當(dāng)對(duì)交易數(shù)據(jù)庫(kù)Q完成掃描后，會(huì)得到候選1-項(xiàng)集C1：{M1}、{M2}、{M3}、{M4}、{M5}。因?yàn)樯傻拿總€(gè)項(xiàng)集的支持度的值都大于或者等于設(shè)定的2，所以C1中的所有的項(xiàng)集都被包含在1-項(xiàng)集L1中。

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

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

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

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

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

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

按照以上的方法對(duì)其他的頻繁項(xiàng)項(xiàng)進(jìn)行類(lèi)似的操作，就可以得到全部的規(guī)則。

2 Apriori算法的性能分析

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

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

第二可能會(huì)生成較大的候選集；

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

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

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

2.1.1 基于哈希的方法

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

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

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

2.1.3 基于采樣的方法

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

2.1.4 間隔計(jì)算的方法

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

3 Apriori算法改進(jìn)

3.1 Apriori算法改進(jìn)思想

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

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

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

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

3.2 事先剪枝策略

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

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

第二如果K-項(xiàng)集X里面（K-1）項(xiàng)子集不是頻繁項(xiàng)集，那么X就不會(huì)是頻繁項(xiàng)目集；

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

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

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

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

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

4 算法改進(jìn)性能評(píng)價(jià)

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

實(shí)驗(yàn)環(huán)境：

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

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

測(cè)試使用數(shù)據(jù)：選取UCI標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集Mushroom,此種數(shù)據(jù)的特征就是頻繁項(xiàng)目集密集分布。

實(shí)驗(yàn)步驟：

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

圖2 不同支持度下的候選項(xiàng)集

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

圖3 不同支持度下的運(yùn)行時(shí)間

5 基于U檢驗(yàn)思想置信度評(píng)價(jià)

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

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

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

(1)|u|

(2)u0.05≤|u|

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

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

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

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

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

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

6 結(jié)語(yǔ)

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