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

0 引言

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

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

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

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

Web Log挖掘可以分成三個(gè)階段：數(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挖掘首先要對(duì)用戶的日志記錄數(shù)據(jù)進(jìn)行預(yù)處理，其任務(wù)是通過(guò)對(duì)來(lái)自不同數(shù)據(jù)源的各類用戶訪問(wèn)數(shù)據(jù)的分析，組織轉(zhuǎn)化為所必需的數(shù)據(jù)挖掘格式并保存起來(lái)，形成用戶會(huì)話文件，等待進(jìn)一步的處理。Web數(shù)據(jù)預(yù)處理過(guò)程共包括四個(gè)步驟：數(shù)據(jù)清洗、用戶識(shí)別、會(huì)話識(shí)別和路徑補(bǔ)充。

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

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

2.2 用戶識(shí)別

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

2.3 會(huì)話識(shí)別

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

2.4 路徑補(bǔ)充

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

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

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

3.1 分類

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

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

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

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

3.3 序列模式

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

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

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

3.4 聚類算法

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

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

3.4.1 用戶群體聚類算法

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

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

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

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

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

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

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

3.4.2 Web頁(yè)面聚類算法

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

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

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

3.5 用戶訪問(wèn)模式挖掘

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

表1 挖掘出的每類用戶的訪問(wèn)模式

4 模式分析

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

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

實(shí)現(xiàn)個(gè)性化服務(wù)系統(tǒng)較重要的一步便是用戶訪問(wèn)模式的挖掘。這是一個(gè)較新的研究領(lǐng)域，它的應(yīng)用非常廣泛，主要應(yīng)用在電子商務(wù)、站點(diǎn)系統(tǒng)改進(jìn)、站點(diǎn)系統(tǒng)性能的改進(jìn)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改進(jìn)和構(gòu)建自適應(yīng)站點(diǎn)、網(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ù)處理過(guò)程技術(shù)研究[J].微計(jì)算機(jī)信息.2006．

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

[6]張濤,周愛(ài)武,謝榮傳.基于概念格和關(guān)聯(lián)規(guī)則Web個(gè)人化系統(tǒng)[J],計(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頁(yè)面與用戶聚類算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì).2008.

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