基于矩陣的Apriori改進(jìn)算法與實(shí)現(xiàn)

張小林

關(guān)聯(lián)規(guī)則[1-4]由Agrawal、Imielinski和Swami于1993年在對(duì)市場(chǎng)購(gòu)物籃問(wèn)題進(jìn)行分析時(shí)首次提出，用以發(fā)現(xiàn)商品銷售中的顧客購(gòu)買(mǎi)模式，是數(shù)據(jù)中一種簡(jiǎn)單但很實(shí)用的規(guī)則。關(guān)聯(lián)規(guī)則的主要思想就是找出頻繁項(xiàng)集，算法的主要工作就是尋找K-項(xiàng)集。根據(jù)相關(guān)性質(zhì)，頻繁項(xiàng)集的子集必是頻繁項(xiàng)集，非頻繁項(xiàng)集的超集一定是非頻繁的。利用上一步產(chǎn)生的頻繁項(xiàng)集來(lái)生成長(zhǎng)度更大的項(xiàng)集，并將其稱之為候選頻繁項(xiàng)集。候選頻繁項(xiàng)集是指那些有可能成為頻繁項(xiàng)集的集合。算法先計(jì)算所有的候選1-項(xiàng)集C1；從C1中找出所有的頻繁1-項(xiàng)集L1；然后，再將L1與自身做連接運(yùn)算，生成候選2-項(xiàng)集的集合C2；從C2中找出所有的頻繁2-項(xiàng)集L2；再將L2與自身做連接運(yùn)算，生成候選3-項(xiàng)集的集合C3；從C3中找出所有的頻繁3-項(xiàng)集L3；如此下去直到不再產(chǎn)生新的候選集。一般地，將候選K-項(xiàng)集的集合記為Ck，將頻繁k-項(xiàng)集記為L(zhǎng)k，顯然Lk哿Ck。

1 關(guān)聯(lián)規(guī)則的算法簡(jiǎn)介

挖掘關(guān)聯(lián)規(guī)則的一種原始方法：計(jì)算每個(gè)可能規(guī)則的支持度和置信度。這種方法的過(guò)高代價(jià)令人望而卻步，因?yàn)榭梢詮臄?shù)據(jù)集提取的規(guī)則的數(shù)目達(dá)指數(shù)級(jí)。具體點(diǎn)說(shuō)，從包含d個(gè)項(xiàng)的數(shù)據(jù)集提取的可能規(guī)則的總數(shù)為：R=3d-2d+1+1。

提高關(guān)聯(lián)規(guī)則挖掘算法性能的第一步是拆分支持度和置信度要求。因此，大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法通常采用的一種策略是，將關(guān)聯(lián)規(guī)則挖掘任務(wù)分解為如下兩個(gè)主要的子任務(wù)：(1)頻繁項(xiàng)集產(chǎn)生。其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集找出所有的頻繁項(xiàng)集。(2)規(guī)則的產(chǎn)生。其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取高置信度的規(guī)則。這兩個(gè)步驟中，第二步是在第一步的基礎(chǔ)上進(jìn)行的，工作量非常小。挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。

關(guān)聯(lián)規(guī)則的挖掘有很多方法，比較典型的算法有兩種：

(1)ARGen算法。ARGen算法由Agrawal和Ramakrishman提出的，過(guò)程如下：

(2)Apriori算法

Apriori算法在關(guān)聯(lián)規(guī)則算法分析中具有相當(dāng)重要的地位，其中含有priori是因?yàn)樗惴ㄊ褂昧祟l繁項(xiàng)集性質(zhì)的先驗(yàn)（priori）知識(shí)。Apriori算法是由Agrawal等在1993年提出的，主要是基于數(shù)據(jù)庫(kù)中數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)規(guī)則。隨著需求的不斷擴(kuò)大，應(yīng)用范圍的拓展，隨后幾年有很多的理論研究人員開(kāi)始對(duì)Apriori算法感興趣。因此，Apriori算法一直被稱為經(jīng)典算法，后來(lái)的一些算法主要是對(duì)經(jīng)典算法進(jìn)行優(yōu)化，被稱之為類Apriori算法。

2 Apriori算法的核心思想

Apriori算法的核心思想主要如下：

(1)通過(guò)單趟掃描事務(wù)數(shù)據(jù)庫(kù)D計(jì)算出所有1-項(xiàng)集的支持度，從而得到滿足最小支持度s%的頻繁1-項(xiàng)集構(gòu)成的集合L1。

(2)為了產(chǎn)生頻繁k-項(xiàng)集構(gòu)成的集合Lk，必須先產(chǎn)生候選頻繁k-項(xiàng)集的集合Ck，產(chǎn)生Ck的方法是連接。過(guò)程如下所述：設(shè)li是Lk-1中的項(xiàng)集，li[j]表示li的第j項(xiàng)。在此假定事務(wù)或項(xiàng)集中的項(xiàng)按一定順序排列。設(shè)l1、l2是Lk-1中的項(xiàng)集，如果它們的前（k-2）個(gè)項(xiàng)相同，則l1、l2是可連接的，即如果（l1[1]=l2[1]）∧（l1[2]=l2[2]）∧…∧（l1[k-2]=l2[k-2]）∧（l1[k-1]≠ l2[k-1]），則連接l1和l2產(chǎn)生的結(jié)果項(xiàng)集是l1[1]l1[2]…l1[k-2]l1[k-1]l2[k-1]。由Lk-1中可連接的項(xiàng)集連接所產(chǎn)生的k-項(xiàng)集的集合便是Ck。

(3)由于Ck是Lk的超集，可能有些元素不是頻繁的。由于任何非頻繁的（k-1）項(xiàng)集必定形不成頻繁k-項(xiàng)集的子集，所以，當(dāng)候選k-項(xiàng)集的某個(gè)（k-1）子集不是Lk-1中的成員時(shí)，則該候選頻繁項(xiàng)集不可能是頻繁的，可以從Ck中移去。通過(guò)單趟掃描事務(wù)數(shù)據(jù)庫(kù)D，計(jì)算Ck中各個(gè)項(xiàng)集的支持度。將Ck中不滿足最小支持度計(jì)數(shù)s的項(xiàng)集刪除，生成頻繁k項(xiàng)集Lk。

通過(guò)迭代循環(huán)，重復(fù)上述步驟，直到不能產(chǎn)生新的頻繁項(xiàng)集的集合為止。在頻繁項(xiàng)集的基礎(chǔ)上篩選出支持度大于最小支持度的頻繁項(xiàng)集，最終找到滿足設(shè)定好的最小支持度和最小置信度的頻繁項(xiàng)集，產(chǎn)生關(guān)聯(lián)規(guī)則。

3 Apriori算法不足與改進(jìn)思路

Apriori算法的思想是查找頻繁項(xiàng)集，盡管它也在產(chǎn)生候選集的時(shí)候也采取了一些措施，但是仍然存在一些致命的缺點(diǎn)。

(1)當(dāng)所挖掘的數(shù)據(jù)量很大，它可能需要產(chǎn)生大量候選項(xiàng)集。例如，如果有104個(gè)頻繁1項(xiàng)集，則Apriori算法需要產(chǎn)生多達(dá)107個(gè)候選2項(xiàng)集，如果還要產(chǎn)生候選3-項(xiàng)集，那所產(chǎn)生的數(shù)據(jù)量無(wú)法估量了，顯然效率極低。此外，為發(fā)現(xiàn)長(zhǎng)度為100的頻繁模式，如{a1,…,a100}，必須產(chǎn)生多達(dá)2100≈1030個(gè)候選。

(2)每當(dāng)產(chǎn)生一個(gè)候選集的時(shí)，它就需要重新掃描數(shù)據(jù)庫(kù)D，通過(guò)模式匹配來(lái)計(jì)算候選集中每個(gè)項(xiàng)集的支持度計(jì)數(shù)，顯然通過(guò)掃描事務(wù)數(shù)據(jù)庫(kù)中每個(gè)事務(wù)來(lái)計(jì)算候選項(xiàng)集的支持度的開(kāi)銷非常大，而且事務(wù)數(shù)據(jù)庫(kù)中的事務(wù)數(shù)越多，效率越低。

根據(jù)以上缺點(diǎn)，很多理論研究者提出了一些改進(jìn)算法和新的技術(shù)[5]，以提高Apriori算法的效率。主要的一些技術(shù)如下所述：

(1)基于散列的技術(shù)（散列項(xiàng)集到對(duì)應(yīng)的桶中）：散列技術(shù)實(shí)際上是通過(guò)減少候選集的方法來(lái)提高算法效率的技術(shù)。改進(jìn)思想是，當(dāng)有候選1-項(xiàng)集產(chǎn)生頻繁1-項(xiàng)集時(shí)，在掃描事務(wù)數(shù)據(jù)庫(kù)的同時(shí)，也對(duì)它們每個(gè)事務(wù)可能產(chǎn)生的候選2-項(xiàng)集散列到所定義的散列表數(shù)據(jù)結(jié)構(gòu)（桶）中，并將對(duì)應(yīng)的桶的計(jì)數(shù)增加。然后在查找散列表中各個(gè)桶的計(jì)數(shù)，如果小于支持度閾值，那么該2-項(xiàng)集是非頻繁的，應(yīng)該從候選集中刪除。該壓縮算法對(duì)2-項(xiàng)集是非常有用的。

(2)事務(wù)壓縮（壓縮未來(lái)迭代掃描的事務(wù)數(shù)）：根據(jù)頻繁項(xiàng)集的性質(zhì)，不包含任何頻繁k項(xiàng)集的事務(wù)，它不可能包含任何頻繁（k+1）項(xiàng)集。算法思想就是利用了上述的性質(zhì)，如果事務(wù)不包含頻繁2-項(xiàng)集，那么它就不可能包含頻繁3-項(xiàng)集，頻繁4-項(xiàng)集。因此在產(chǎn)生頻繁項(xiàng)集的時(shí)候，不斷地發(fā)現(xiàn)這些事務(wù)，并將這些事務(wù)屏蔽，通過(guò)加上特殊的標(biāo)記或者刪除，因?yàn)檫@些事務(wù)不可能再產(chǎn)生更多的頻繁項(xiàng)集，以減少下一步產(chǎn)生頻繁項(xiàng)集掃描數(shù)據(jù)庫(kù)的次數(shù)。

(3)劃分（為尋找候選項(xiàng)集劃分?jǐn)?shù)據(jù)）：使用劃分技術(shù)，實(shí)際上就是將事務(wù)數(shù)據(jù)庫(kù)從邏輯上劃分成n個(gè)不相交的劃分塊，然后再針對(duì)每個(gè)劃分塊查找頻繁項(xiàng)集，最后將所有的劃分塊中的頻繁項(xiàng)集集合起來(lái)，從中找出頻繁項(xiàng)集。因此使用劃分技術(shù)只需要掃描兩趟事務(wù)數(shù)據(jù)庫(kù)，一次是在每個(gè)劃分塊中，另一次是在集成頻繁項(xiàng)集的時(shí)候。盡管劃分技術(shù)從理論上來(lái)說(shuō)，是減少了數(shù)據(jù)庫(kù)的掃描次數(shù)，但是在實(shí)際實(shí)現(xiàn)過(guò)程中，還是存在很多問(wèn)題，將數(shù)據(jù)庫(kù)劃分為多少個(gè)塊，太多太少都不合適，還有就是如果從CPU運(yùn)行的效率上來(lái)說(shuō)，并行處理效率更高，但是它會(huì)受到每個(gè)劃分產(chǎn)生的頻繁項(xiàng)集之間通信的制約。

(4)采樣（對(duì)給定數(shù)據(jù)的子集挖掘）：采樣技術(shù)在很多領(lǐng)域中都在應(yīng)用，在統(tǒng)計(jì)學(xué)中的應(yīng)用更為廣泛?，F(xiàn)在將它引用到數(shù)據(jù)挖掘中，主要來(lái)解決數(shù)據(jù)挖掘中數(shù)據(jù)量大的問(wèn)題。抽樣方法的基本思想和其他應(yīng)用領(lǐng)域中是一樣的，從給定的數(shù)據(jù)中選取樣本，但是所選取的樣本要具有代表性。選定樣本后，在根據(jù)挖掘算法對(duì)樣本進(jìn)行查找頻繁項(xiàng)集，而不是在給定的原始數(shù)據(jù)中查找頻繁項(xiàng)集，這樣大大提高了頻繁項(xiàng)集的查找效率。當(dāng)由樣本生成的頻繁項(xiàng)集，產(chǎn)生一些規(guī)則，然后用非樣本數(shù)據(jù)庫(kù)的事務(wù)去驗(yàn)證哪些規(guī)則是成立的。顯然，這種方法也有它的一些弊端，肯定會(huì)丟失一些頻繁項(xiàng)集，遺漏一些重要的規(guī)則，畢竟樣本不能代表所有的數(shù)據(jù)。采樣技術(shù)，可以減少數(shù)據(jù)庫(kù)的掃描次數(shù)，提高了系統(tǒng)的I/O性能。

4 基于矩陣的挖掘算法

關(guān)聯(lián)規(guī)則挖掘主要分為兩個(gè)步驟，首先是找出所有的頻繁項(xiàng)集，然后是通過(guò)這些頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。根據(jù)開(kāi)始設(shè)置的最小支持度和最小置信度來(lái)提取關(guān)聯(lián)規(guī)則。

在具體實(shí)現(xiàn)的時(shí)候，采取了一種新的改進(jìn)算法。它的主要思想是：(1)減少事務(wù)數(shù)據(jù)庫(kù)記錄數(shù)量；(2)盡量減少讀取數(shù)據(jù)庫(kù)操作。在壓縮事務(wù)數(shù)據(jù)庫(kù)采取的策略是，盡量刪除那些不可能得到頻繁項(xiàng)集的項(xiàng)目。改進(jìn)算法思想是，利用矩陣的的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，直接查找頻繁項(xiàng)集。定義矩陣數(shù)據(jù)結(jié)構(gòu)，行向量表示項(xiàng)目，列向量表示事務(wù)。矩陣X為：

圖中I1…Im表示m個(gè)項(xiàng)目，T1…Tn表示n個(gè)事務(wù)。yji(1≤j≤m,1≤i≤n)只能等于0或者1。行向量可以理解為，項(xiàng)目在哪些事務(wù)中；列向量可以理解為什么，當(dāng)前事務(wù)包含哪些項(xiàng)目。譬如，當(dāng)y11=1時(shí)，表示項(xiàng)目I1在事務(wù)T1中，當(dāng)y21=0時(shí)，表示項(xiàng)目I1不在事務(wù)T2中。當(dāng)yji=1時(shí)，表示項(xiàng)目Ij在事務(wù)Ti中，反之則不在事務(wù)Tj中。此算法只需讀取一次數(shù)據(jù)庫(kù)，在讀取的同時(shí)就開(kāi)始給每個(gè)項(xiàng)目計(jì)數(shù)。

當(dāng)查找頻繁1-項(xiàng)集時(shí)，只需計(jì)算當(dāng)前項(xiàng)目Ii的行向量的和，當(dāng)min_sup時(shí)，則Ij是頻繁1-項(xiàng)集。將當(dāng)前項(xiàng)目Ij寫(xiě)入數(shù)據(jù)庫(kù)中，并將它的支持度計(jì)數(shù)同時(shí)寫(xiě)入數(shù)據(jù)中。反之則不是頻繁項(xiàng)集，則也要將它寫(xiě)入數(shù)據(jù)庫(kù)中，并標(biāo)上標(biāo)記，只要當(dāng)后面出現(xiàn)此項(xiàng)目的時(shí)候，就不需要計(jì)算了，肯定是不頻繁的。

當(dāng)查找頻繁2-項(xiàng)集時(shí)，同樣是求和。具體算法如下：sum（IjIk）=yj1×yk1+yj2×yk2+…+yjn×ykn，當(dāng)sum（IjIk）≥min_sup時(shí)，IjIk是頻繁2-項(xiàng)集，反之就不是頻繁2-項(xiàng)集；同上，要將頻繁的項(xiàng)集和非頻繁的項(xiàng)集寫(xiě)入數(shù)據(jù)庫(kù)，為它們分別標(biāo)上標(biāo)記，對(duì)于非頻繁的項(xiàng)集，在下次出現(xiàn)的時(shí)候，直接跳過(guò)。當(dāng)查找頻繁3-項(xiàng)集時(shí)，算法和2-項(xiàng)集一樣，求每個(gè)項(xiàng)目的列向量的積，然后求和，當(dāng)求的值大于或等于最小支持度，就是頻繁的。

sum（IjIkIp）=yj1×yk1×yp1+yj2×yk2×yp2+…+yjn×ykn×ypm，當(dāng)Sum（IjIkIp）≥min_sup時(shí)，IjIkIp是頻繁3-項(xiàng)集，反之就不是頻繁3-項(xiàng)集；然后將它們寫(xiě)入數(shù)據(jù)庫(kù)，并標(biāo)上標(biāo)記。

在上述運(yùn)算中，由于矩陣具有一些運(yùn)算法則，可以直接將Ij∧Ik進(jìn)行與運(yùn)算，然后統(tǒng)計(jì)當(dāng)前向量的和是否滿足最小支持閾值的計(jì)數(shù)。如此循環(huán)，直到不能發(fā)現(xiàn)新的頻繁項(xiàng)集，算法結(jié)束。在查找頻繁K-項(xiàng)集時(shí)，可以利用到在查找頻繁K-1項(xiàng)集時(shí)的數(shù)據(jù)。因?yàn)榫仃囍械臄?shù)據(jù)yji=0或者yji=1，因此也可以使用與運(yùn)算來(lái)計(jì)算。目前，CPU性能相當(dāng)?shù)母撸瑘?zhí)行加法運(yùn)算速度相當(dāng)快，相對(duì)于在Apriori算法中用到的連接運(yùn)算來(lái)說(shuō)，效率明顯提高了。

5 實(shí)驗(yàn)結(jié)果

將改進(jìn)后的Apriori算法應(yīng)用到Apache+PHP+Mysql平臺(tái)上開(kāi)發(fā)的web日志挖掘系統(tǒng)中。利用改進(jìn)后的算法對(duì)學(xué)校的招生就業(yè)網(wǎng)站進(jìn)行分析。從訪問(wèn)web的IIS日志中提取了相關(guān)信息進(jìn)行數(shù)據(jù)挖掘，主要是希望能挖掘到一些訪問(wèn)信息，對(duì)網(wǎng)站的結(jié)構(gòu)布局進(jìn)行改版，便于不同要求的訪客能快捷地找到有用的信息。

在經(jīng)過(guò)數(shù)據(jù)凈化、會(huì)話識(shí)別等步驟后，得到用戶的事務(wù)集，如表1所示（部分）。

表1 凈化后的數(shù)據(jù)

具體分析時(shí)，用A代表主頁(yè)index.asp；B代表channel.asp?id=2；C代表/article.asp?class_id=1，后面都是通過(guò)class_id來(lái)區(qū)分不同的欄目；D代表class_id=2；E代表class_id=3；F代表class_id=4；G代表class_id=5；H代表class_id=6；I代表class_id=7……。生成的事務(wù)集如表2所示。然后在數(shù)據(jù)庫(kù)中新建一個(gè)表，用于記錄事務(wù)和訪問(wèn)者、IP的對(duì)應(yīng)關(guān)系表。

表2 就業(yè)網(wǎng)站事務(wù)集

在大量的數(shù)據(jù)中，選擇一些典型的頁(yè)面進(jìn)行分析，如表3所示以及挖掘結(jié)果如表4所示。根據(jù)關(guān)聯(lián)規(guī)則求得它們的支持度和置信度。

表3 網(wǎng)站分析

表4 選取的挖掘結(jié)果

其中showdl.asp?id=14這個(gè)網(wǎng)頁(yè)是一個(gè)下載鏈接，它鏈接的內(nèi)容是：安慶師范學(xué)院畢業(yè)生就業(yè)推薦表。A∩X圯Z表示訪問(wèn)同時(shí)訪問(wèn)主頁(yè)和就業(yè)指導(dǎo)服務(wù)網(wǎng)頁(yè)的人群中，有16.2%的人會(huì)去訪問(wèn)資料下載這個(gè)頁(yè)面。6結(jié)語(yǔ)

網(wǎng)絡(luò)時(shí)代的飛速發(fā)展，使網(wǎng)絡(luò)上的數(shù)據(jù)呈幾何數(shù)量級(jí)增長(zhǎng)，數(shù)據(jù)挖掘的應(yīng)用也越來(lái)越廣泛。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中的一個(gè)重要的挖掘方法，雖然它有很多的不足，但還是能夠找到一些方法加以改進(jìn)。本文提出的基于矩陣的改進(jìn)算法主要是基于事務(wù)壓縮的思路來(lái)考慮的，在對(duì)數(shù)據(jù)庫(kù)掃描的同時(shí)就開(kāi)始給每個(gè)項(xiàng)目計(jì)數(shù)，因此對(duì)數(shù)據(jù)庫(kù)只需要掃描一遍，這大大地提高了算法的效率。

[1]Agrawalr,Imielinskit,Swamia.Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACMS IGMOD International Conference on Management of Data.New York:ACMPress,1993:207-216.

[2]Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘:概念與技術(shù)[M].范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2007.

[3]梁循.數(shù)據(jù)挖掘算法與應(yīng)用[M].北京:北京大學(xué)出版社,2006.

[4]陳文偉,黃金才.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘[M].北京:人民郵電出版社,2005.

[5]柴華昕,王勇.Apriori頻繁項(xiàng)目集算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(24):158-161,171.