張小林

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

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

挖掘關(guān)聯(lián)規(guī)則的一種原始方法：計算每個可能規(guī)則的支持度和置信度。這種方法的過高代價令人望而卻步，因為可以從數(shù)據(jù)集提取的規(guī)則的數(shù)目達(dá)指數(shù)級。具體點說，從包含d個項的數(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ù)分解為如下兩個主要的子任務(wù)：(1)頻繁項集產(chǎn)生。其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項集找出所有的頻繁項集。(2)規(guī)則的產(chǎn)生。其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項集中提取高置信度的規(guī)則。這兩個步驟中，第二步是在第一步的基礎(chǔ)上進(jìn)行的，工作量非常小。挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。

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

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

(2)Apriori算法

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

2 Apriori算法的核心思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 基于矩陣的挖掘算法

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

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

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

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

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

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

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

5 實驗結(jié)果

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

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

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

具體分析時，用A代表主頁index.asp；B代表channel.asp?id=2；C代表/article.asp?class_id=1，后面都是通過class_id來區(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ù)庫中新建一個表，用于記錄事務(wù)和訪問者、IP的對應(yīng)關(guān)系表。

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

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

表3 網(wǎng)站分析

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

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

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

[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ù)倉庫與數(shù)據(jù)挖掘[M].北京:人民郵電出版社,2005.

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