曾姣艷

（福州軟件職業(yè)技術學院計算機系，福建福州350003）

Web挖掘的關聯(lián)規(guī)則優(yōu)化算法

曾姣艷

（福州軟件職業(yè)技術學院計算機系，福建福州350003）

對Apriori算法進行優(yōu)化，提出了一種Z_Apriori算法。該算法在首次產生頻繁項集時，掃描數(shù)據(jù)庫并通過二進制編碼串記錄每個項目在事務里是否出現(xiàn)過，在每次進行計算迭代過程中無需再對數(shù)據(jù)庫進行掃描，避免了對數(shù)據(jù)庫的重復掃描，在系統(tǒng)性能和效率上較經(jīng)典的Apriori算法有一定的改善。

關聯(lián)規(guī)則；個性化推薦服務；頻繁項集

Internet技術近年來正以難以想象的速度爆炸式發(fā)展，面對“信息超載”的問題，如何從海量的信息中分析和研究客戶的喜好和瀏覽習慣，有針對性地為不同客戶群提供他們所需要或感興趣的信息資源，已成為一項迫切而重要的課題。

Web日志挖掘屬于Web挖掘的一個研究方向，它基于站點服務器的日志文件進行數(shù)據(jù)挖掘，找出其中的特點和規(guī)律，分析客戶在對系統(tǒng)進行瀏覽和訪問過程中的行為特性，推測出用戶的興趣偏好，根據(jù)這些特點改進系統(tǒng)的組織和結構，制定商品銷售方案，從而提升公司的服務標準［1］。因此，在電子商務系統(tǒng)中使用日志挖掘和個性化服務等技術是非常迫切需要也是必然趨勢。

1 關聯(lián)規(guī)則經(jīng)典Apriori算法

1.1 算法的設計思想

關聯(lián)規(guī)則挖掘實現(xiàn)從龐大的數(shù)據(jù)集中發(fā)現(xiàn)它們之間的關聯(lián)。Apriori算法作為關聯(lián)規(guī)則的經(jīng)典算法，其主要思想是在大量的數(shù)據(jù)集中發(fā)現(xiàn)頻繁項集，再由頻繁項集產生強關聯(lián)規(guī)則。該算法中涉及到支持度和置信度兩個重要指標［2］。

Aprior算法的實現(xiàn)分成兩步：第一步是進行迭代，發(fā)現(xiàn)數(shù)據(jù)集中所有頻繁項目集，要求計算得到的支持度不小于最小支持度；第二步是根據(jù)頻繁項目集生成強關聯(lián)規(guī)則并計算置信度，要求計算得到的置信度不小于最小置信度［3］。

1.2 算法示例

表1是一個簡單的事務數(shù)據(jù)庫D，該數(shù)據(jù)庫D里共有4個事務，包含項目｛A｝、｛B｝、｛C｝、｛D｝和｛E｝，設定的最小支持度閥值s=40％，用戶設定的最小置信度閥值c=80％。

頻繁項目集挖掘過程：

（1）第一次迭代，產生1-頻繁項目集。分三個階段計算

生成階段：產生1-候選項目集C1。

計算階段：求每個候選集在事務中出現(xiàn)的次數(shù)并計算支持度。

表1 事務數(shù)據(jù)庫D

選擇階段：選擇支持度s≥40％的項目，生成1-頻繁項目集L1。

（2）第二次迭代，2-產生頻繁項目集。

產生階段：利用L1*L1生成候選項目集。“*”運算定義為：Lk*Lk={X∪Y,其中X，Y∈Lk，|X∩Y|=k+1}。設C2為在第二次迭代中產生的2-候選項目集。|C2|=|L1|· （|L1|-1）／2。在此例中為：4·3／2=6。因此，產生6項2-候選項目集C2。

計算階段：求每個候選項目集在事務中出現(xiàn)的次數(shù)并計算支持度。

選擇階段：選擇支持度s≥40％的2-頻繁項目集L2。

（3）第三次次迭代，產生3-頻繁項目集。

產生階段：使用L2*L2生成候選項目集。計算產生1項3-候選項目集C3。

計算階段：求每個候選集在事務中出現(xiàn)的次數(shù)并計算支持度。

選擇階段：選擇支持度s≥40％的3-頻繁項目集L3，并根據(jù)Apriori算法的性質進行剪枝：所有頻繁項目集的子集都是頻繁項目集，項集｛A，B，D｝的所有子集都是L2的元素，故保留。

由于本例的L3不能產生4-候選項目集，因此迭代停止。

由頻繁項目集產生關聯(lián)規(guī)則：

第二階段的工作是根據(jù)第一階段計算的結果，生成關聯(lián)規(guī)則。如果規(guī)則為｛x1，x2，x3｝→x4，那么項集｛x1，x2，x3，x4｝和｛x1，x2，x3｝都必須是頻繁的。然后，規(guī)則置信度c=P（｛x4｝|｛x1，x2，x3｝）=s（x1，x2，x3，x4）／s（x1，x2，x3）。置信度c不小于最小置信度閥值的規(guī)則就是強關聯(lián)規(guī)則［4］。

由上面的例子，得到一個頻繁集｛A，B，D｝，非空真子集有｛A｝，｛B｝，｛D｝，｛A，B｝，｛A，D｝，｛B，D｝。結果關聯(lián)規(guī)則如下。

根據(jù)設定的最小置信度閥值c=80％，只有第三、第三和第六規(guī)則符合可以輸出，因為這些都是強規(guī)則。

1.3 算法的缺點

對Apriori算法進行研究發(fā)現(xiàn)，在計算支持度的過程中，進行每一次迭代發(fā)現(xiàn)頻繁項集都要重新掃描整個事務數(shù)據(jù)庫，因此若要進行n次迭代，則需要重復掃描數(shù)據(jù)庫n次［5］。若碰到事務數(shù)據(jù)庫非常龐大或迭代次數(shù)非常多時，則該算法運行要花費大量的時間，導致可能不能滿足實際要求甚至難以進行。

2 優(yōu)化的Z＿Apriori算法

2.1 算法的基本思想

針對Apriori算法存在的缺陷，提出了一種優(yōu)化算法Z_Apriori算法。對于Apriori算法在每次計算頻繁項目集時都需要對數(shù)據(jù)庫重復進行掃描的問題進行了優(yōu)化，Z_Apriori算法通過二進制編碼統(tǒng)計每個項目在事務中是否出現(xiàn)，因此只需要掃描一次數(shù)據(jù)庫，大大提高了算法的執(zhí)行效率。

2.2 算法示例

表2為一個簡單的事務數(shù)據(jù)庫D，共有8個事務，數(shù)據(jù)庫D中包含的項目｛A｝、｛B｝、｛C｝、｛D｝、｛E｝和｛F｝，設定最小支持度s= 50％。

Z_Apriori算法頻繁集挖掘過程：

（1）第1次迭代，生成1-候選項目集，選擇支持度s≥50％的項目，生成1-頻繁項目集L1。對事務數(shù)據(jù)庫進行掃描，用一串二進制編碼依次記錄每個項目在事務中是否有出現(xiàn)，出現(xiàn)用1表示，沒出現(xiàn)用0表示。

表2 事務數(shù)據(jù)庫D

（2）第2次迭代，產生2－候選項目集，選擇支持度s≥50％的項目集，生成2－頻繁項目集L2。將使用L*L1產生候選項集，根據(jù)第1次迭代計算得到的二進制編碼計算每個新項目在事務中是否出現(xiàn)。

（3）第3次迭代，產生3-候選項目集，選擇支持度s≥50％的項目，生成3-頻繁項目集L3。

由于本例的L3無法生成4－候選項目集，因此算法迭代結束。

3 兩種算法性能比較

使用Microsoft Visual Studio 2005中的C＃分別實現(xiàn)了經(jīng)典Apriori算法和改進的Z＿Apriori算法，利用Microsoft SQL Server 2005中的Transaction數(shù)據(jù)集進行測試，證實了Z＿Apriori算法節(jié)省了系統(tǒng)運行時間［6］。

實驗1：項目數(shù)items＝25，事務數(shù)目TID＝5000，計算在不同支持度情況下Apriori算法和改進的Z＿Apriori算法的運行時間，實驗結果如圖1所示。由圖1可知，在相同的項目數(shù)和事務數(shù)目情況下，隨著最小支持度閥值的增加，兩種算法的運行時間都隨著變少。但在同一最小支持度下，Z＿Apriori算法的運行時間一直小于Apriori算法的運行時間。

實驗2：交易事務表項目數(shù)items＝25，最小支持度s＝40％，考察不同事務數(shù)量下兩種算法的運行時間。實驗結果如圖2所示：由圖2可知，在相同的項目數(shù)和最小支持度情況下，隨著事務數(shù)目的增加，兩種算法的運行時間都隨著增加。但在同一事務數(shù)目下，Z＿Apriori算法的運行時間一直小于Apriori算法的運行時間。

圖1 不同支持度下兩種算法的運行時間比較

圖2 不同事務數(shù)量下兩種算法的運行時間比較

4 結語

分析和研究了關聯(lián)規(guī)則的經(jīng)典算法Apriori算法，并基于該算法提出了一種改進算法Z＿Apriori算法。跟Apriori算法相比較，Z＿Apriori算法中在整個計算求解的過程中只需要對事務數(shù)據(jù)庫掃描一次。只有在第一次迭代生成1－頻繁項集時要對數(shù)據(jù)庫進行掃描，通過一串二進制編碼來統(tǒng)計每個項目是否在事務里出現(xiàn)過。每次迭代產生頻繁項集的過程中，只需根據(jù)二進制編碼計算項目集的支持度，不用像APriori算法要對事務數(shù)據(jù)庫進行重復掃描，因此減少了系統(tǒng)運行花費的時間，很好地對Apriori算法不足的地方進行了優(yōu)化。

［1］李曉艷.Web使用挖掘在電子商務個性化服務中的應用［J］.科技創(chuàng)業(yè)月刊，2008，21（5）：122－124.

［2］楊風召，白慧.電子商務推薦系統(tǒng)的算法與模型分析［J］.情報雜志，2007，26（12）：40－42.

［3］陳美榮，楊莉.基于電子商務網(wǎng)站的WEB內容挖掘［J］.商場現(xiàn)代化，2008（5）：149－150.

［4］曹麗君，劉蹦印.基于電子商務的數(shù)據(jù)挖掘探究［J］.商場現(xiàn)代化，2008（5）：157－157.

［5］許國忠.基于可變階模型的Web訪問模式挖掘算法［J］.三明學院學報，2008，25（2）：204－207.

［6］姜美玉，盧利平，宜建軍.基于WEB日志挖掘的網(wǎng)站個性化服務研究［J］.圖書館學刊，2006，28（5）：137－138.

An Optimization Association Rules Algorithm of Web Mining

ZENG Jiao-yan
(Department of Computer,Fuzhou Software Vocational Technology College,Fuzhou 350003,China)

Z_Apriori algorithm,which based on optimization of Apriori algorithm,is put forward in this paper.When generating frequent item sets for the first time,the algorithm can scan the database and record which project appears in the transaction by the binary code string and it no longer need to scan the database in each calculation and iteration process, which avoids scanning the database repeatedly.Compared with Apriori algorithm,it has a certain improvement about the performance and efficiency of the system.

association rules;personalized recommendation service;frequent item set

TP301.6

A

1673-4343（2013）02-0027-05

2012-11-26

曾姣艷，女，湖南郴州人，助教。研究方向：計算機應用。