基于頻繁閉項集的Web日志挖掘算法

秦東霞,周 航,張棟梁,吳文歡

(周口師范學院計算機科學與技術(shù)學院,河南周口466001)

伴隨著電腦技術(shù)和互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展,人們希望在互聯(lián)網(wǎng)上找到自己需要的各種各樣的信息。用戶在網(wǎng)上的各種行為都保存在服務器中,如何發(fā)現(xiàn)這些行為中隱含的規(guī)則和關(guān)系,對改進網(wǎng)站及吸引更多用戶有著重要的意義。Web日志數(shù)據(jù)挖掘技術(shù)是解決上述問題的一個有效辦法。本文將關(guān)聯(lián)規(guī)則引入到Web日志挖掘過程中,并通過頻繁閉項集來壓縮關(guān)聯(lián)規(guī)則產(chǎn)生的數(shù)量,同時使用最小關(guān)聯(lián)規(guī)則有效地避免了冗余規(guī)則的產(chǎn)生。實驗證明該算法不僅能提高挖掘效率,并且不丟失任何信息。

1 Web日志挖掘

Web日志挖掘是指通過分析用戶訪問服務器時留下的訪問記錄,結(jié)合各種數(shù)據(jù)挖掘技術(shù),得到包括網(wǎng)站運營和用戶訪問規(guī)律等信息,從而改進網(wǎng)站服務,提高用戶滿意度。

1.1 Web日志挖掘模型

提取Web日志中的隱含的信息需要經(jīng)過數(shù)據(jù)預處理、模式發(fā)現(xiàn)和模式分析等階段[1],圖1顯示了Web日志挖掘模型。

數(shù)據(jù)預處理是進行Web日志挖掘的前提步驟,它是針對具體的挖掘目的將Web日志文件轉(zhuǎn)換為適合進行挖掘的數(shù)據(jù)文件的過程。預處理要經(jīng)過數(shù)據(jù)清洗、用戶識別、會話識別和路徑補充等階段,以保證數(shù)據(jù)的準確性和有效性[2]。

圖1 Web日志挖掘模型

模式發(fā)現(xiàn)在Web日志挖掘中具有舉足輕重的作用。該階段通過相應的數(shù)據(jù)挖掘算法對預處理后的數(shù)據(jù)進行挖掘,提取其中有價值的信息。模式發(fā)現(xiàn)包括分類、聚類、關(guān)聯(lián)規(guī)則、序列模式和統(tǒng)計分析等常用的方法和技術(shù)[3]。

模式分析是針對用戶感興趣的規(guī)則和模式進行進一步地分析,從而挖掘得到有價值的信息。

1.2 問題與解決方法

關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘中得到了廣泛的應用,尤其在大量商業(yè)決策中。近年來頁面關(guān)聯(lián)規(guī)則挖掘可以提取用戶訪問頁面間隱含的因果關(guān)系、簡單關(guān)系和前后關(guān)系等,具有較好的商業(yè)前景。然而,現(xiàn)有的基于關(guān)聯(lián)規(guī)則的Web日志挖掘算法往往產(chǎn)生大量的候選規(guī)則,這對規(guī)則的排序、修剪和查找都帶來了許多不便,同時這些候選規(guī)則中存在大量不能為用戶提供有價值信息的冗余規(guī)則。本文通過引入頻繁閉項集和最小關(guān)聯(lián)規(guī)則的相關(guān)概念,解決了如下三個問題:

1 )在一定程度上避免了大量候選規(guī)則的產(chǎn)生,從而降低了算法對內(nèi)存空間的要求;

2 )在分析冗余規(guī)則產(chǎn)生原因的基礎上,提出了使用最小關(guān)聯(lián)規(guī)則減少冗余規(guī)則產(chǎn)生的對策;

3 )將頻繁閉項集的概念應用到了Web日志挖掘中,使得頻繁閉項集的應用得到進一步推廣。

2 基于頻繁閉項集的無冗余關(guān)聯(lián)規(guī)則

2.1 基本概念

假設集合I={i1,i2,…,in}是一項目組,D= {t1,t2,…,tn}是一數(shù)據(jù)集。表1是一個示例數(shù)據(jù)集,一個事務可以用二元組表示,其中事務的標志用tid表示,該事務對應的項集用X表示[4]。如果項集X?Y,那么事務X蘊含在事件中。

圖2a)中給出了事務集和項目集之間的對應關(guān)系。以表1中給出的示例數(shù)據(jù)庫為t(AC)=t(A)∩t(C)=126∩1356=16,i(135)=i(1)∩i(3)∩i(5)=ACDE∩CDE∩CE=CE。

圖2 a)事務集與項目集的對應關(guān)系; b)閉項集的表示

表1 示例數(shù)據(jù)庫

定義1 項目集I中,有項集X?I存在,X是閉項集當且僅當c(X)=i(t(X))=X。如圖2b)所示

定理1[5]對于項集D中的任一項集X,項集X的支持度sup(X)與其閉項集c(X)的支持度sup(c(X))相同,也即σ(X)=σ(cit(X))。

定理2[6]對于任一項集X,有X?i(t(X))。對任意標志集Y,有Y?t(i(Y))。

以示例數(shù)據(jù)庫為例,CD?i(t(CD))= i(2456)=CD,AC?i(t(AC))=i(16)=ACDE。

以上兩個定理表明,由頻繁閉項集可以推導出頻繁項集,同時頻繁閉項集的數(shù)量更少,尤其對密集數(shù)據(jù)集而言。最壞的情況是頻繁閉項集的數(shù)量與頻繁項集的數(shù)量相等[7]。

定義2[6]如果存在項集X滿足以下兩個條件:

1 )sup(X)≥a(a表示用戶規(guī)定的最小支持度閾值),

2 )不存在項集Y?I∧X?Y∧sup(X)= sup(Y),

則稱項集X為頻繁閉項集(Closed Frequent Itemset)。頻繁閉項集也可稱作閉頻繁項集。

定義3[6]D為事務集,從其中挖掘得到的頻繁閉項集的集合記作C,那么頻繁閉項集格L= (C,≤),其中“≤”表示這些頻繁閉項集的偏序關(guān)系。由表1示例數(shù)據(jù)庫產(chǎn)生的頻繁閉項集格結(jié)構(gòu)如圖3所示。

圖3 示例數(shù)據(jù)得到的頻繁閉項集格

在集合C中,如果存在頻繁閉項集X和Y滿足下面兩個條件:

1 )X?Y,

2 )不存在Z使得X?Z?Y,

那么Y是X的直接閉超集。建立頻繁閉項集格結(jié)構(gòu)就是建立節(jié)點X和其直接頻繁閉超集之間的鏈接,因為節(jié)點X的子節(jié)點就是其直接閉超集。通過這種格結(jié)構(gòu)的建立可以快速地產(chǎn)生最小關(guān)聯(lián)規(guī)則,從而得到所有的關(guān)聯(lián)規(guī)則[7]。

2.2 基于閉項集的關(guān)聯(lián)規(guī)則

自1999年P(guān)asquier等提出閉項集的相關(guān)理論以后,閉項集解決了全項集出現(xiàn)的一些問題,不斷得到廣泛的應用。眾所周知,閉項集是全項集的子集,更是全項集的無損表示。在挖掘關(guān)聯(lián)規(guī)則的過程中,用頻繁閉項集代替頻繁項集可以使得挖掘得到的規(guī)則數(shù)量更小,而且不會損失任何信息。通過頻繁閉項集可以誘導推出所有的頻繁項集,同時通過挖掘頻繁閉項集得到的關(guān)聯(lián)規(guī)則可以推導出所有的關(guān)聯(lián)規(guī)則[6]。

挖掘頻繁閉項集的經(jīng)典算法有A-close,Closet和Closet+[7],以及高效快速挖掘頻繁閉項集的CHARM算法[8]等。CHARM-L算法是一個能高效挖掘產(chǎn)生頻繁閉項集并構(gòu)建其格結(jié)構(gòu)的算法,它是CHARM算法的進一步應用。

2.3 無冗余的關(guān)聯(lián)規(guī)則

通過挖掘頻繁閉項集得到的關(guān)聯(lián)規(guī)則中同樣包含支持度和置信度相同的冗余規(guī)則。文獻[6]提出了最小關(guān)聯(lián)規(guī)則的概念,通過此理論的引入,可以得到無冗余的關(guān)聯(lián)規(guī)則。

最小關(guān)聯(lián)規(guī)則是指這些規(guī)則有一些與其支持度和置信度相同的規(guī)則,通過在最小關(guān)聯(lián)規(guī)則的前件或者后件添加相應的項可以推導出這些冗余的規(guī)則。

性質(zhì)1[6,9]關(guān)聯(lián)R:X?Y是置信度為100%的規(guī)則,當且僅當t(X)?t(Y)。

性質(zhì)1說明置信度為100%的規(guī)則是那些從超集推導到子集的規(guī)則,又由項集的支持度sup(X)與其閉項集的支持度sup(c(X))相等,他們能提取出相同的關(guān)聯(lián)規(guī)則。

性質(zhì)2[6,9]假設規(guī)則Ri:X?X是置信度為100%的關(guān)聯(lián)規(guī)則,其中Ri是集合R=(R1,R2,…, Rn)中的一員。若I1=c(X∪X),I2=c(X),則關(guān)聯(lián)規(guī)則I1?I2是該集合中置信度為100%的最小關(guān)聯(lián)規(guī)則,且其他所有的規(guī)則都是冗余的,并且都等價于規(guī)則I1?I2。

性質(zhì)3[6,9]假設規(guī)則Ri:X?X是置信度小于100%的關(guān)聯(lián)規(guī)則,其中Ri是集合R=(R1, R2,…,Rn)中的一員。若I1=c(X),I2=c(X∪X),則關(guān)聯(lián)規(guī)則I1?I2是該集合中置信度小于100%的最小關(guān)聯(lián)規(guī)則,且其他所有的規(guī)則都是冗余的,并且都等價于規(guī)則I1?I2。

2.4 挖掘基于閉項集的無冗余關(guān)聯(lián)規(guī)則

若希望在挖掘得到頻繁閉項集并產(chǎn)生其關(guān)聯(lián)規(guī)則的同時,提取無冗余的關(guān)聯(lián)規(guī)則,可通過建立規(guī)則的前件和后件之間的父子關(guān)系,也就是格結(jié)構(gòu)來完成。Charm-L算法[10]是在Charm算法的基礎上快速建立此格結(jié)構(gòu)。本文將使用Charm-L算法來建立Web日志之間的格結(jié)構(gòu),同時引入最小關(guān)聯(lián)規(guī)則的概念挖掘得到無冗余的關(guān)聯(lián)規(guī)則。

3 算法性能評價及應用

以上通過實例和相關(guān)概念闡述了最小關(guān)聯(lián)規(guī)則在挖掘關(guān)聯(lián)規(guī)則過程中的優(yōu)勢,接下來將使用相關(guān)算法來進行實驗對比。本實驗是在一臺CPU主頻為2.00GHz,內(nèi)存為2GB的Window 7操作系統(tǒng)中進行的,實驗數(shù)據(jù)來自于ftp://ftp.ics.uci。 edu/pub/machineLearning-databases/。本文主要做了兩個對比實驗,一個是在稠密數(shù)據(jù)集和稀疏數(shù)據(jù)集中挖掘所有關(guān)聯(lián)規(guī)則和最小關(guān)聯(lián)規(guī)則所用時間的對比,如圖4。

圖4 生成關(guān)聯(lián)規(guī)則平均時間

另外一個是針對相同的數(shù)據(jù)集,挖掘得到的所有關(guān)聯(lián)規(guī)則和最小關(guān)聯(lián)規(guī)則的數(shù)量對比,如表2。

表2 關(guān)聯(lián)規(guī)則數(shù)量

由圖4和表2可以明顯看出,無論對稀疏數(shù)據(jù)集還是稠密數(shù)據(jù)集,挖掘最小關(guān)聯(lián)規(guī)則的時間總是比較短,而且挖掘得到的規(guī)則數(shù)量要小得多。

下面將其算法應用到具體的Web日志數(shù)據(jù)中。以周口師范學院校園網(wǎng)Web日志數(shù)據(jù)為實驗對象,經(jīng)過預處理后的數(shù)據(jù)對這些數(shù)據(jù)進行轉(zhuǎn)換,具體處理過程參考文獻[7],這里不再贅述。然后使用Charm-L算法進行挖掘,最后得到頻繁閉項集及其格結(jié)構(gòu)。挖掘過程中選取最小支持度為5%,最小置信度為10%,本實驗共得到23條最小關(guān)聯(lián)規(guī)則。接著對這些規(guī)則進行分析,去除用戶點擊產(chǎn)生的無意義的頻繁規(guī)則,挖掘得到的有價值模式4條,如表3所示,其中輸出的結(jié)果按照支持度從小到大排列。

下面,具體分析挖掘出的這幾條關(guān)聯(lián)規(guī)則的使用價值:

1 )規(guī)則1顯示5%的用戶通過校園網(wǎng)來查看校歷,這表明學校校歷放在了不顯眼的位置。因此,網(wǎng)站管理者可以通過此條信息調(diào)整一下校歷的相關(guān)網(wǎng)頁的位置。

2 )規(guī)則2中6%的用戶訪問學校的精品課堂,但我們發(fā)現(xiàn)學校的精品課堂相關(guān)網(wǎng)頁有時候打不開。

表3 挖掘得到的有價值的關(guān)聯(lián)規(guī)則

3 )規(guī)則3表明用戶使用招生網(wǎng)站中的搜索功能比較多,表明該頁面中網(wǎng)站的信息分類功能做的不太完善。

4 )從規(guī)則4可以得知9%的用戶同時訪問了“校園簡介”和“校園風光”,然而我們卻發(fā)現(xiàn)在“校園簡介”這一頁面中并無“校園風光”的相關(guān)鏈接,用戶要返回到學校主頁才能點擊查看校園風光。因此,根據(jù)這條信息的提示,建議網(wǎng)站管理者在“校園簡介”這一頁面中加入“校園風光”的相關(guān)鏈接。

4 結(jié)束語

本文分析了Web日志挖掘模型以及目前Web日志挖掘中出現(xiàn)的規(guī)則數(shù)量多,存在冗余規(guī)則等問題,并提出了運用頻繁閉項集挖掘關(guān)聯(lián)規(guī)則減少規(guī)則數(shù)量的思想。本算法同時引入最小關(guān)聯(lián)規(guī)則的概念挖掘無冗余的關(guān)聯(lián)規(guī)則,最后以周口師范學院校園網(wǎng)Web日志為挖掘?qū)ο?驗證算法的可行性和實用性。實驗證明了算法的有效性,也為日后該算法的推廣提供了有力的依據(jù)。

[1]Cooley R,Mobasher B,Srivastava J.Web mining Information and pattern discovery on the world wide web [C]//In proceedings of the 9th IEEE International Conference on Tools with Arifical Intelligence (ICTAT97),1997:558-567.

[2]周增國,龐有軍.Cookie技術(shù)在Web日志挖掘預處理中的應用[J].大連大學學報,2006,27(2):59-62.

[3]王繼成,潘金貴,張福炎.Web文本挖掘技術(shù)研究[J].計算機研究與發(fā)展,2000,37(5):513-520.

[4]陳安,陳寧,周龍驤.數(shù)據(jù)挖掘技術(shù)及應用[M].北京:科學出版社,2006.

[5]朱玉全,宋余慶.頻繁閉項目集挖掘算法的研究[J].計算機研究與發(fā)展,2007,11(7):1177-1183.

[6]Zaki M J.Generating Non-Redundant Association Rules[C]//Proc.of the 6th ACM SIGKDD Intl'Conf. on Knowledge Discovery and Data Mining,2000:34-43.

[7]Raymond Kosala,Hendrik Blockeel.Web Mining Research:A Survey[J].ACM SIGKDD Explorations, 2000,2:1-15.

[8]秦東霞.基于頻繁閉項集的關(guān)聯(lián)分類算法[D].重慶:重慶大學計算機學院,2009.

[9]閆英春.基于閉頻繁項集的Web日志挖掘[D].成都:電子科技大學,2010.

[10]Zaki MJ,Hsiao C J.Efficient Algorithms for Mining Closed Itemsets and Their Lattice structure[J].IEEE Transactions on Knowledge and Data Engineering, 2005,17(4):462-478.