基于Web日志挖掘的個性化服務(wù)技術(shù)的研究

熊熙湖北工業(yè)大學(xué)計算機(jī)學(xué)院 湖北 430068

0 引言

World Wide Web自1989 年首次提出以來，Web網(wǎng)站無論是在訪問量、規(guī)模上還是在網(wǎng)站設(shè)計的復(fù)雜度上都以驚人的速度增長著。這為人們提供豐富信息的同時，也為人們查找自己感興趣的信息帶來了困難。為此，如何針對Web網(wǎng)站內(nèi)容、網(wǎng)站結(jié)構(gòu)、用戶訪問日志信息等數(shù)據(jù)進(jìn)行研究進(jìn)入了一個新的階段。Web日志挖掘技術(shù)便是運用數(shù)據(jù)挖掘的思想來對服務(wù)器日志進(jìn)行分析處理，從而找出用戶訪問規(guī)律和內(nèi)容喜好，為改進(jìn)網(wǎng)站結(jié)構(gòu)和內(nèi)容提供了決策支持。同時，如何應(yīng)用數(shù)據(jù)挖掘技術(shù)挖掘出有用的知識，更好地為用戶服務(wù)，已經(jīng)成為國際上的熱門研究方向。本文主要論述了兩個挖掘聚類算法相結(jié)合在網(wǎng)絡(luò)用戶個性化服務(wù)中的應(yīng)用。

1 Web日志挖掘技術(shù)

什么是Web日志挖掘？Web日志挖掘或叫Web使用記錄挖掘，它通過挖掘 Web日志記錄，來發(fā)現(xiàn)用戶訪問 Web頁面的模式。通過分析和探究Web日志記錄中的規(guī)律，可以對不同背景、不同興趣和目的的用戶行為規(guī)律加以分析，來改進(jìn)網(wǎng)站的組織結(jié)構(gòu)及其性能，增加個性化服務(wù)，實現(xiàn)網(wǎng)站自適應(yīng)，發(fā)現(xiàn)潛在的用戶群體。Web日志挖掘己成為一個新的研究領(lǐng)域，在電子商務(wù)和個性化Web等方面有著廣泛的應(yīng)用。

Web日志挖掘的對象通常是服務(wù)器的日志信息，Web服務(wù)器的日志記載了用戶訪問站點的數(shù)據(jù)，這些數(shù)據(jù)包括：訪問者的IP地址、訪問的頁面，頁面的大小，瀏覽器類型，響應(yīng)狀態(tài)訪問時間、訪問方式、訪問的頁面、協(xié)議、錯誤代碼以及傳輸?shù)淖止?jié)數(shù)等。每當(dāng)網(wǎng)頁被請求一次，Web Log就在日志數(shù)據(jù)庫內(nèi)追加相應(yīng)的記錄。熱點的Web站點每天可以記錄下數(shù)以百計字節(jié)的Web Log記錄。Web Log數(shù)據(jù)庫提供了有關(guān)Web動態(tài)的豐富信息。因此研究復(fù)雜的Web Log挖掘技術(shù)是十分重要的。

Web Log挖掘可以分成三個階段：數(shù)據(jù)預(yù)處理、模式發(fā)現(xiàn)、模式分析，其系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 Web日志挖掘技術(shù)系統(tǒng)結(jié)構(gòu)圖

2 數(shù)據(jù)預(yù)處理

Web Log挖掘首先要對用戶的日志記錄數(shù)據(jù)進(jìn)行預(yù)處理，其任務(wù)是通過對來自不同數(shù)據(jù)源的各類用戶訪問數(shù)據(jù)的分析，組織轉(zhuǎn)化為所必需的數(shù)據(jù)挖掘格式并保存起來，形成用戶會話文件，等待進(jìn)一步的處理。Web數(shù)據(jù)預(yù)處理過程共包括四個步驟：數(shù)據(jù)清洗、用戶識別、會話識別和路徑補充。

2.1 數(shù)據(jù)清洗

數(shù)據(jù)清洗工作與具體站點情況相關(guān)，它包括從多個服務(wù)器中對日志文件進(jìn)行處理，刪除與挖掘算法無關(guān)的數(shù)據(jù)，合并某些記錄，對用戶請求頁面時發(fā)生錯誤的記錄進(jìn)行適當(dāng)?shù)奶幚淼鹊?。具體是從服務(wù)器日志文件中刪除不相關(guān)的項和冗余信息，比如一些廣告信息動畫；輔助文件wav，jpeg，CSS，gif，PEG；腳本程序文件cgi，js；返回碼404等，縮小日志挖掘的范圍。將 URL地址表示規(guī)范化也是這個階段的任務(wù)之一。URL地址規(guī)范化就是將相對的URL地址轉(zhuǎn)換為絕對的URL地址，成為適當(dāng)?shù)臄?shù)據(jù)格式以方便Web數(shù)據(jù)挖掘過程。

2.2 用戶識別

用戶識別的主要任務(wù)是從清洗過的 Web服務(wù)器訪問日志所得到的中間數(shù)據(jù)中，識別出相應(yīng)的用戶。每一個用戶需被準(zhǔn)確地區(qū)分開的難點在于一些本地緩存、代理服務(wù)器、單位和個人防火墻的存在，訪問站點的用戶留下的是同樣的IP地址。故姚洪波、楊炳儒提出了三則啟發(fā)式規(guī)則來識別用戶：不同的IP地址代表著不同的用戶；若IP地址相同，但是操作系統(tǒng)類型或者瀏覽器軟件不同被默認(rèn)為是不同的用戶；若當(dāng)前用戶請求的頁面同用戶已瀏覽的頁面間沒有鏈接關(guān)系，則認(rèn)為存在IP地址相同的不同的用戶。

2.3 會話識別

會話識別就是將用戶的訪問記錄劃分成單個的會話，不同用戶訪問的頁面屬于不同的會話，日志文件中不同的頁面也屬于不同的會話。由于在較長的時間里，用戶可能多次訪問了該站點，也很難知道用戶是否為分開幾次登錄。所以一般利用最大的超時來判斷用戶是否已離開了該網(wǎng)站，若兩次請求時間之間超過了一定的時間界限，就會被認(rèn)為用戶的一個會話已結(jié)束，開始了一個新的會話。

2.4 路徑補充

由于高速緩沖存儲器Cache的存在，一般在會話識別后還要確認(rèn)Web Log中所有的重要訪問記錄都是否完整。若用戶使用了緩存頁面訪問網(wǎng)頁，則當(dāng)前請求頁與用戶上一次請求頁之間沒有超文本鏈接，應(yīng)當(dāng)檢查引用日志確定當(dāng)前請求具體來自哪一頁，通過這種方法將遺漏的頁面補充添加到用戶的會話文件路徑中。總之，可以根據(jù)網(wǎng)站的拓?fù)浣Y(jié)構(gòu)圖和引用日志提供的信息，對用戶訪問路徑進(jìn)行補充。

3 模式發(fā)現(xiàn)

模式發(fā)現(xiàn)是運用各種算法和技術(shù)對電子商務(wù)網(wǎng)站中預(yù)處理后的數(shù)據(jù)進(jìn)行挖掘，生成模式。這些技術(shù)包括人工智能、數(shù)據(jù)挖掘、統(tǒng)計理論、信息論等多領(lǐng)域的成熟技術(shù)?？梢赃\用數(shù)據(jù)挖掘中的常用技術(shù)，如分類聚類、關(guān)聯(lián)規(guī)則、序列模式以及統(tǒng)計分析等等。網(wǎng)站中一旦用戶識別和會話識別完成，就可以采用下面的技術(shù)進(jìn)行模式發(fā)現(xiàn)。

3.1 分類

分類技術(shù)主要是從個人信息或共同的訪問模式中得出訪問某一服務(wù)器文件的用戶特征。分類是將數(shù)據(jù)按照預(yù)先定義的類別進(jìn)行劃分。在Web日志挖掘領(lǐng)域中，分類主要是將用戶配置文件歸屬給定的用戶類別。分類技術(shù)要求抽取關(guān)鍵屬性描述已知的用戶類別。發(fā)現(xiàn)分類規(guī)則可以給出識別一個特殊群體的公共屬性的描述，這種描述可以用于分類客戶。例如：在某網(wǎng)站中訪問瀏覽過的客戶中有30%是女性?？梢酝ㄟ^指導(dǎo)性歸納學(xué)習(xí)算法進(jìn)行分類，主要包括決策樹分類法、貝葉斯分類、最近鄰分類法、k-相似相鄰分類等技術(shù)。

3.2 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則指發(fā)現(xiàn)用戶會話中經(jīng)常被用戶一起訪問的頁面集合，這些頁面之間并沒有順序關(guān)系，就是要找到客戶對網(wǎng)站上各種文件之間訪問的相互聯(lián)系。如果關(guān)聯(lián)規(guī)則中的頁面之間沒有超鏈接，則這是一個我們感興趣的關(guān)聯(lián)規(guī)則。挖掘關(guān)聯(lián)規(guī)則通常使用Apriori算法或其變形算法，從事務(wù)數(shù)據(jù)庫中挖掘出最大的頻繁訪問項集，這個項集就是關(guān)聯(lián)規(guī)則挖掘出來的用戶訪問模式。

利用這些相關(guān)性，可以發(fā)現(xiàn)用戶瀏覽的某些規(guī)律，更好的組織 Web網(wǎng)站的結(jié)構(gòu)。在這里，經(jīng)典的關(guān)聯(lián)挖掘算法有Apriori算法。一般使用的叫做序列模式挖掘。

3.3 序列模式

在平時生活中，很多事情都屬于按時間進(jìn)行排序的序列這一范疇。比如，在現(xiàn)實超市中，某天顧客購買商品的活動序列；在電子商務(wù)網(wǎng)站中，客戶對自己感興趣的物品的點擊序列；在網(wǎng)絡(luò)中，用戶對Web網(wǎng)站的訪問序列等等。故在科學(xué)技術(shù)和商業(yè)的很多領(lǐng)域中，發(fā)現(xiàn)事件之間預(yù)期的序列關(guān)聯(lián)顯得越來越重要。

網(wǎng)絡(luò)中的用戶數(shù)量及其龐大，每人的興趣愛好又不盡相同，其特點較為復(fù)雜。所以網(wǎng)站不僅需要分析用戶在訪問過程中最喜歡看哪些頁面內(nèi)容，還需要分析用戶在瀏覽某些網(wǎng)頁之后，接下來會對哪些其它網(wǎng)頁更感興趣；分析用戶每次訪問的網(wǎng)頁間的聯(lián)系后進(jìn)行各種個性化服務(wù)，這樣才能方便用戶，進(jìn)而吸引更多的用戶。為了解決以上問題，便產(chǎn)生了序列模式挖掘。

序列模式挖掘的方法目前有很多種，比較經(jīng)典的算法有三種：GSP算法、Prefix Span算法和SPADE算法。

3.4 聚類算法

聚類分析是從 Web訪問信息數(shù)據(jù)中聚類出具有相似特性的客戶，然后把具有相似瀏覽行為的用戶或數(shù)據(jù)項歸類，利用這類知識可以在電子商務(wù)中進(jìn)行市場分割或者為用戶提供個性化Web頁面內(nèi)容。在Web日志挖掘技術(shù)中，聚類分析主要集中于用戶群體聚類算法和Web頁面聚類算法。

聚類就是將物理或抽象的集合分組成為由類似的對象組成的多個類或簇，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。通過聚類，我們能夠識別密集的和稀疏的區(qū)域，因而發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的有趣的相互關(guān)系。數(shù)據(jù)對象算法的選擇取決于數(shù)據(jù)的類型、聚類的目的和應(yīng)用。如果聚類分析被用作描述或探查的工具，可以對同樣的數(shù)據(jù)嘗試多種算法，已發(fā)現(xiàn)數(shù)據(jù)可能揭示的結(jié)果。

3.4.1 用戶群體聚類算法

用戶群體聚類，不是指簡單的根據(jù)IP地址得到用戶所在地來給用戶聚類，而是先對每一個用戶訪問過的所有Web頁面進(jìn)行聚類，即Web文檔聚類；然后根據(jù)數(shù)據(jù)預(yù)處理過程中提到的啟發(fā)式規(guī)則，判斷每一個用戶訪問過的頁面屬于哪一網(wǎng)頁類，從而將所有訪問該網(wǎng)頁類的用戶聚成一類。所以，一個用戶可以分別屬于多個類。

首先要分析用戶瀏覽行為和Web站點的表示。以L=＜IP,ID,URL,TIME＞的形式服務(wù)器日志。其中IP為用戶的IP地址，ID為用戶ID,URL為用戶請求的URL,TIME為請求網(wǎng)頁相應(yīng)的瀏覽時間。設(shè)A為用戶的瀏覽行為，LA.URL=URLA，n≥1，hits為目前客戶瀏覽頁面LA.URL的次數(shù)。有如下公式：

設(shè)hi,j是j用戶在一段時間內(nèi)訪問第i個URL的次數(shù)；每一行向量M[x.,j]表示所有用戶對URLx的訪問情況；每一列向量M[i,y]表示用戶y對該站點中所有的 URL的訪問情況。因此,可以這樣認(rèn)為：行向量既代表了站點的結(jié)構(gòu)，又蘊涵有客戶共同的訪問模式；而列向量則既反應(yīng)了客戶類型，也勾勒出了客戶的個性化訪問子圖。那么，分別度量行向量和列向量的相似性，就能直接得到相關(guān)Web頁面和相似客戶群體，進(jìn)一步分析還能獲得客戶訪問模式，即頻繁訪問路徑。據(jù)此就可以建立如下所示的URL-UserID關(guān)聯(lián)矩陣Mm×n：

相似性的度量是根據(jù) Hamming距離來判斷的。對于M[i,j]＞0,令M[i,j]=1。然后，計算向量間的Hamming距離。當(dāng)Hamming距離越小的時候，其相似程度越高。設(shè)X，Y間的Hamming距離Hd(X,Y)，公式為：

根據(jù)公式2，URL-UserID關(guān)聯(lián)矩陣Mm×n的列向量M[i,y]是用戶訪問站點網(wǎng)頁的個性化子圖，具有相似訪問個性化子圖的用戶即為相似用戶群體。在電子商務(wù)網(wǎng)站中，根據(jù)交易數(shù)據(jù)庫，若用戶僅作了瀏覽而并未與商家成交，則關(guān)聯(lián)矩陣列向量中的值是未成交的瀏覽次數(shù)。那么，此類用戶群體為潛在用戶群體；否則，則為在冊用戶群體。這是特殊情況。聚類時，首先對URL-UserID關(guān)聯(lián)矩陣Mm×n進(jìn)行預(yù)處理，然后計算列向量間的 Hamming距離，建立列向量間的距離矩陣。接下來根據(jù)公式4來計算閾值：

如果ijd＜Λ,那么所有的滿足這個條件的第j個用戶和第i個用戶被劃分為一個類。同時，我們還要考慮到用戶對某一網(wǎng)頁的訪問頻率。因此，要對聚類的結(jié)果進(jìn)行確認(rèn)?？梢赃\用下面的公式計算用戶U和類C之間的連接強度來進(jìn)行確認(rèn)。

若使用公式5計算得到的連接強度CU(U,C)小于某個閾值(如2/C)，那么，將這個客戶U從類C中移出，并與其它被排除的U劃為另一個類C2。

3.4.2 Web頁面聚類算法

Web頁面聚類是將內(nèi)容相關(guān)的頁面歸類，它的主要作用是可以利用這些信息為用戶的查詢提供相關(guān)的超鏈接，后文中的個性化系統(tǒng)便是通過這個算法對用戶進(jìn)行推薦服務(wù)。

URL-UserID關(guān)聯(lián)矩陣Mm×n的行向量M[x,j]反映了所有客戶對本站點中不同頁面的訪問情況。如果客戶對某些頁面的訪問情況相同或相似，那么，這些頁面理應(yīng)為相關(guān)頁面，可以聚為一類。聚類時，同樣先對URL-UserID關(guān)聯(lián)矩陣Mm×n進(jìn)行預(yù)處理，去掉所有值為零的行向量，對于可先令M[i,j]=1。再計算行向量間的Hamming距離，建立行向量間的距離矩陣Mm×Hmd。在對稱矩陣M’Hd中，dij∈M’Hd(1≤i≤m，i＜j≤m)表示第i個行m×mm×m向量和第j個行向量間的Hamming距離，對角元素的值為0。接下來根據(jù)公式4計算閾值，也可以按照具體情況自己指定閾值的大小。對于(1≤i≤m，i＜j≤m)，如果dij＜Λ，那么就將第i個URL和所有的滿足這個條件的第j個URL劃分為一個類。

同樣，與用戶群體聚類算法提到的情況：上述聚類過程中沒有考慮客戶對某一 URL的訪問頻率，因此也要對聚類的結(jié)果進(jìn)行確認(rèn)。同理，根據(jù)公式5進(jìn)行確認(rèn)。若計算得到的連接強度CU(U,C)小于某個閾值(如1/C)，那么，將這個客戶U從類C中移出，并與其它被排除的U劃為另一個類C2。

3.5 用戶訪問模式挖掘

經(jīng)過上文所敘述的分類、關(guān)聯(lián)規(guī)則、聚類算法、統(tǒng)計分析后，重點將用戶群體聚類算法與 Web頁面聚類算法相結(jié)合，我們就可以更快捷準(zhǔn)確地得到每一類用戶的訪問模式(如表1所示)。

表1 挖掘出的每類用戶的訪問模式

4 模式分析

模式分析是基于Web的日志挖掘中最后一項重要步驟。我們通過模式發(fā)現(xiàn)、選擇和觀察，把從Web日志挖掘中得到的相關(guān)規(guī)則、模式和統(tǒng)計值轉(zhuǎn)換為知識，再經(jīng)過模式分析這一步驟得到相應(yīng)的模式，即用戶所需要的規(guī)則和模式，采用可視化圖形的方法，以推薦頁面的方式提供給訪問該網(wǎng)站的用戶，即個性化服務(wù)。

5 個性化服務(wù)的應(yīng)用和發(fā)展方向

實現(xiàn)個性化服務(wù)系統(tǒng)較重要的一步便是用戶訪問模式的挖掘。這是一個較新的研究領(lǐng)域，它的應(yīng)用非常廣泛，主要應(yīng)用在電子商務(wù)、站點系統(tǒng)改進(jìn)、站點系統(tǒng)性能的改進(jìn)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改進(jìn)和構(gòu)建自適應(yīng)站點、網(wǎng)絡(luò)安全以及智能化等方面。

[1]Dimitrios Pierrakos，Georgios Paliouras.KOINOTITES:A Web Usage Mining Tool for Personalization.

[2]李文媛,林克正.Web日志挖掘研究[J].金融理論與教學(xué).2008.

[3]Abraham,Ajith.Business Intelligence from Web Usage Mining [J].Journal of Information＆ Knowledge Management.2003．

[4]姚洪波,楊炳儒.Web日志挖掘數(shù)據(jù)預(yù)處理過程技術(shù)研究[J].微計算機(jī)信息.2006．

[5]陳志敏,沈潔.基于 Web日志的混合挖掘模型研究[J].揚州大學(xué)學(xué)報(自然科學(xué)版).2007.

[6]張濤,周愛武,謝榮傳.基于概念格和關(guān)聯(lián)規(guī)則Web個人化系統(tǒng)[J],計算機(jī)技術(shù)與發(fā)展.2008.

[7]Meng X F,Lu H Y,SG-Wrap；A schema-guided wrapper generator demonstration,Proc of ICDE'2002,Los Alamitos,CA：IEEE Computer Society Press.2002.

[8]宋麟,王鎖柱.基于模糊多重集的Web頁面與用戶聚類算法研究[J].計算機(jī)工程與設(shè)計.2008.

[9]趙娜,田保慧,姜建國.基于加權(quán)矩陣聚類的Web日志挖掘算法[J].現(xiàn)代電子技術(shù).2008.