Web日志頻繁序列模式挖掘算法研究.pdf

1、Web日志頻繁序列模式的挖掘是Web日志挖掘的重要組成部分，主要用來(lái)發(fā)掘站點(diǎn)和用戶交互的頻繁路徑。利用這些頻繁序列模式,可以簡(jiǎn)單的分析出用戶的訪問(wèn)序列模式規(guī)律、進(jìn)行建模以及對(duì)Web站點(diǎn)進(jìn)行優(yōu)化調(diào)整，以更好地滿足用戶訪問(wèn)需求來(lái)提升用戶體驗(yàn)，進(jìn)而增加訪問(wèn)用戶數(shù)量，因而對(duì)形成智能化Web站點(diǎn)和個(gè)性化推薦有其特殊的意義。
　　針對(duì)Web日志頻繁序列模式挖掘這一研究領(lǐng)域，目前已經(jīng)提出一系列算法，比如GSP、Apriori、PSP、G序列、圖

2、形遍歷、FreeSpan、PrefixSpan、Disc-all、MEMISP、MFS、LAPIN-SPAM、WAP-tree、PLWAP-tree和最近的NGCWAP-tree等。本文針對(duì)PLWAP-tree算法存在：1）當(dāng)樹(shù)的深度或者寬度超過(guò)計(jì)算機(jī)字長(zhǎng)時(shí)，判斷節(jié)點(diǎn)間的位置關(guān)系時(shí)需要多次移動(dòng)指針，導(dǎo)致搜索空間挖掘過(guò)慢；2）重復(fù)遍歷頭表節(jié)點(diǎn)，因此消耗了更多的時(shí)間；3）需要更多內(nèi)存空間來(lái)存儲(chǔ)PLWAP-tree等缺陷，探索新的改進(jìn)算法，主

3、要研究?jī)?nèi)容及取得成果如下：
　　首先，在現(xiàn)有PLWAP-tree算法基礎(chǔ)上，提出了一種存儲(chǔ)空間更節(jié)省、時(shí)間效率也略有提升的改進(jìn)算法PREWAP-tree。PREWAP-tree算法使用樹(shù)狀結(jié)構(gòu)來(lái)存儲(chǔ)Web訪問(wèn)序列，通過(guò)具有相同前子序列的序列共用路徑節(jié)點(diǎn)來(lái)構(gòu)建PREWAP樹(shù)，基于前綴序列進(jìn)行逐步挖掘，得到所有的頻繁項(xiàng)集。在先序遍歷PREWAP樹(shù)構(gòu)建頭表的同時(shí)，記錄當(dāng)前節(jié)點(diǎn)的先序遍歷序號(hào)和指向其最大先序遍歷序號(hào)的后代節(jié)點(diǎn)的指針，結(jié)合節(jié)

4、點(diǎn)的先序遍歷次序和指向最大先序遍歷次序的后代節(jié)點(diǎn)指針，來(lái)判斷節(jié)點(diǎn)間的位置關(guān)系，遍歷頭表隊(duì)列挖掘PREWAP-tree。
　　進(jìn)而，在上述改進(jìn)算法 PREWAP-tree基礎(chǔ)上，提出了另一種改進(jìn)算法BFWAP-tree。BFWAP-tree算法首先構(gòu)建BFWAP樹(shù)，使相同前綴子序列每重復(fù)出現(xiàn)一次時(shí)路徑上的所有節(jié)點(diǎn)權(quán)值依次遞加一。之后，在先序遍歷BFWAP-tree建立頭表的同時(shí)，記錄每個(gè)節(jié)點(diǎn)所在的子分支序號(hào)，在挖掘過(guò)程中借助于節(jié)點(diǎn)所

5、在分支序號(hào)判斷其是否為首節(jié)點(diǎn)。該算法避免了使用位置碼標(biāo)識(shí)節(jié)點(diǎn)位置關(guān)系，在數(shù)據(jù)量規(guī)模較大的情況下，時(shí)間效率和空間節(jié)省方面都有更好改進(jìn)。
　　最后，將本文提出的兩種改進(jìn)算法PREWAP-tree和BFWAP-tree與現(xiàn)有PLWAP-tree、WAP-tree和 NGCWAP-tree算法進(jìn)行了對(duì)比實(shí)驗(yàn)和結(jié)果分析。分別在一定支持度和不同數(shù)據(jù)量下以及一定數(shù)據(jù)量和不同支持度下，對(duì)各個(gè)算法的時(shí)間消耗和內(nèi)存消耗進(jìn)行對(duì)比和分析，驗(yàn)證了本文提出算