摘 要：Web服務(wù)器日志中記錄了用戶的瀏覽模式，為了從中提取出具有相似訪問模式的用戶群，對其提供個性化服務(wù)，提出一種針對Web日志的分析方法。通過構(gòu)建UserID-URL關(guān)聯(lián)矩陣，引入加權(quán)關(guān)聯(lián)矩陣，提出一種基于加權(quán)矩陣的聚類算法——多標記傳播算法。實驗表明，該算法在Web日志挖掘中進行用戶聚類和頁面聚類是高效可靠的。

關(guān)鍵詞：數(shù)據(jù)挖掘；Web日志挖掘；加權(quán)矩陣聚類；多標記傳播算法;用戶聚類

Web Log Mining Algorithm Based on Weighted Matrix Cluster

HAO Na1，2 ，TIAN Baohui1，JIANG Jianguo1

(1.Xidian University，Xi′an，710071，China;2.Qinghai Architecture Vocational Techniqual College，Xining，810012，China

Abstract：Web server log files registered browsing patterns of users，in order to extract users with similar accessing patterns and provide personal service for them，a new method of analysis on Web log is proposed.A User-URL matrix is created and weighted matrix is introduced，additionally，a mutlimarker propagation algorithm based on weighted matrix cluster is proposed.The experiments show that this algorithm has high-performance and reliability to cluster users and pages in Web log mining.

eywords：data mining；Web log mining；weighted matrix cluster；mutlimarker propagation algorithm；users clustering

1 引 言

隨著因特網(wǎng)的迅速發(fā)展，Web在人們的日常生活和工作中的地位日益顯著^［1，2］。Web中包含頁面的內(nèi)容信息、超鏈接信息，以及Web頁面的訪問和使用信息，如何針對這些信息，應(yīng)用數(shù)據(jù)挖掘技術(shù)挖掘出有用的信息，更好地為用戶服務(wù)，已經(jīng)成為目前國內(nèi)外的一個新的研究熱點^［3］。在Internet中，對于特定的網(wǎng)站而言，其頁面之間的拓撲結(jié)構(gòu)是已知的。盡管不同的用戶在不同時期可能會有不同的瀏覽模式，但長期趨勢應(yīng)該是穩(wěn)定的。因此，挖掘特定網(wǎng)站一定時期內(nèi)用戶的訪問信息，便可以發(fā)現(xiàn)該網(wǎng)站的相似用戶群體以及相關(guān)頁面信息，從而對相似用戶群提供個性化服務(wù)。本文對Web站點的拓撲結(jié)構(gòu)和用戶瀏覽信息進行分析，以UserID為行、URL為列，構(gòu)建UserID-URL關(guān)聯(lián)矩陣，元素值為用戶訪問頁面的次數(shù)。在此基礎(chǔ)上，通過閾值參數(shù)的引入，將關(guān)聯(lián)矩陣轉(zhuǎn)化為加權(quán)關(guān)聯(lián)矩陣，提出一種基于加權(quán)矩陣的聚類算法——多標記傳播算法(multiMarker propagation algorithm。該算法利用矩陣的稀疏特性，可從1個稀疏矩陣中抽出1個稠密子矩陣，因此，對用戶（頁面）聚類的過程，也轉(zhuǎn)化為從稀疏矩陣中抽取稠密子矩陣的過程。

2 加權(quán)矩陣聚類

矩陣聚類^［4］（Matrix Cluster，MC）最初是為客戶關(guān)系管理（Customer Relationship Management，CRM）提出的。圖1所示的關(guān)聯(lián)矩陣，[WTHX]M[WTBX]m×n中，行代表用戶，列代表頁面。矩陣元素值hi，j表示用戶i訪問頁面j，的次數(shù)。以往文獻常見做法是用0或者1來表示用戶是否訪問某個頁面，直接對關(guān)聯(lián)矩陣進行歸一化處理得到元素值非0即1的矩陣，再運用各種算法進行聚類分析。

為了更好地刻畫用戶的特征向量，反映出用戶的訪問頻度和興趣所在，本文引入加權(quán)關(guān)聯(lián)矩陣的概念。加權(quán)關(guān)聯(lián)矩陣，[WTHX]A[WTBX]m×n由關(guān)聯(lián)矩陣加權(quán)處理轉(zhuǎn)化而來。通常這樣的加權(quán)矩陣是個大而稀疏的矩陣。

由于用戶和頁面的順序不是很重要，所以行和列可以任意交換。圖2顯示了從給定加權(quán)矩陣中抽取出的稠密矩陣。如圖所示，抽取出的稠密矩陣包括用戶B，D，F(xiàn)，G 及頁面1，3，6，這個子矩陣可解釋成如下這樣：用戶B，D，F(xiàn)，G在訪問頁面1，3，6時具有一個共同特征。同時頁面1，3，6被用戶B，D，F(xiàn)，G的訪問也具有一個共同的特征。

下面給出支持度和置信度的概念：

支持度抽取出的子矩陣的面積，此處定義為：子矩陣的行×子矩陣的列；

置信度抽取出的子矩陣的密度，即：子矩陣中非0元素的個數(shù)/子矩陣的面積；

這樣，加權(quán)矩陣聚類的問題就轉(zhuǎn)化為從稀疏矩陣中找出面積大于指定支持度且密度大于指定置信度的所有子矩陣的問題。

3 多標記傳播算法

當(dāng)矩陣很大時，一般算法會反復(fù)交換行或列，進行大量的計算，本文提出的基于加權(quán)矩陣聚類的多標記傳播算法能夠通過應(yīng)用矩陣的稀疏特性來減少執(zhí)行時間。該算法使用標記傳播，標記傳播通常定義為一個計算模型，它描述一個作為結(jié)點的處理單元和一個作為鏈接邊的結(jié)點間的關(guān)系。標記傳播通過從與結(jié)點，N相連的活動結(jié)點傳輸一個標記的方式激活結(jié)點N。在多標記傳播算法中，行(列代表結(jié)點。當(dāng)一個矩陣元素非0時，相應(yīng)的行和列被一個雙向邊連接。當(dāng)一個結(jié)點收到一個標記時，它會把該標記累積起來形成標記總數(shù)，標記總數(shù)通常用于裁剪。，

如果某結(jié)點收到的標記總數(shù)小于指定的閾值，那么，該結(jié)點對應(yīng)的行(列被裁剪，被裁剪掉的行(列不再參與后面的運算；需要說明的是，當(dāng)執(zhí)行行裁剪時，活動列只能激活那些與對應(yīng)活動列標記相同的行。不過，由行發(fā)送標記時，只要對應(yīng)列為非0元素均可被激活。標記會反復(fù)地在行(列之間傳播，直到活動的行(列不再變化為止，即行(列裁剪結(jié)束，此時如果發(fā)現(xiàn)剩余的活動行和列，均大于用戶指定的行和列的最小值(支持度，并且矩陣密度也大于用戶指定的最小密度(置信度，則剩余的活動行(列對應(yīng)的用戶(頁面即為用戶(頁面聚類，否則，說明沒有滿足要求的用戶(頁面聚類存在。

為了算法的需要，這里引入幾個概念：

用戶信度：用戶點擊所有頁面的累計次數(shù)；

頁面信度：頁面被所有用戶點擊的累計次數(shù)；

最小標記數(shù)：剪切矩陣的條件。

多標記傳播算法結(jié)構(gòu)如下：

輸入：加權(quán)關(guān)聯(lián)矩陣，[WTHX]A[WTBX]m×n、，最小支持度、最小置信度、最小用戶信度、最小頁面信度、最小標記數(shù)。

輸出：用戶聚類和頁面聚類。

初始化；

找出所有用戶信度小于指定值的行；

找出所有頁面信度小于指定值的列；

剪切掉所有用戶信度低于給定閾值的行和所有頁面信度低于給定閾值的列；

repeat

{

找出含有非零元素的行開始；

repeat 

{

行標記清零；

[（]行裁剪[CD2]按照初始行所在列的標記激活相應(yīng)的行（激活的條件是兩行對應(yīng)列的權(quán)值相等），剪切行標記總數(shù)小于最小標記數(shù)的行；列標記清零；列裁剪[CD2]剪切列標記總數(shù)小于最小標記數(shù)的列；[）]

} until (沒有裁剪

[（]求出面積大于支持度，并且密度大于置信度的子矩陣；輸出用戶聚類和頁面聚類；清除用戶聚類和頁面聚類的標志； [）]

} until (沒有非0元素的行

由分析得知，多標記傳播算法的時間復(fù)雜度為，O((M + N×M×N。，該算法會反復(fù)在行與列之間傳播標記，直到活動的行與列不再變化為止，處理過程如圖3所示。

這里需要指出，選擇不同的起始行，則會得到不同的聚類結(jié)果。若以A行作為初始行，則得到的聚類結(jié)果為由A，E，G行和1，4，5列組成的子矩陣。

4 應(yīng)用實例及實驗結(jié)果

Web訪問日志是Web服務(wù)器用以記錄用戶訪問網(wǎng)站各頁面情況的文件^［5］。對Web日志進行數(shù)據(jù)采集、預(yù)處理后，得到每個用戶訪問每個URL頁面的信息。用本文提出的多標記傳播算法實現(xiàn)用戶聚類，把用戶劃分成若干個用戶群，具有相似訪問模式的用戶被分在同一個群體中，相同用戶群中所訪問的頁面也具有相同的特征。

為了驗證多標記傳播算法的有效性，實驗提取某高校網(wǎng)站W(wǎng)eb服務(wù)器上1天的日志記錄，共57 138條記錄，數(shù)據(jù)凈化后得到5 126條記錄，經(jīng)過數(shù)據(jù)清洗、用戶識別和格式化操作后提取112個用戶和53個URL頁面數(shù)，使用本文提出的算法最后識別出6類用戶群，圖4以柱形圖的形式直觀地表示最終的用戶聚類情況。

5 結(jié) 語

本文描述加權(quán)矩陣聚類及其在Web日志挖掘中的應(yīng)用，通過構(gòu)建UserID-URL關(guān)聯(lián)矩陣，引入加權(quán)關(guān)聯(lián)矩陣的概念，提出一種基于加權(quán)矩陣的聚類算法——多標記傳播算法，該算法利用矩陣的稀疏特性，從一個稀疏矩陣中抽出一個稠密子矩陣實現(xiàn)用戶（頁面）聚類，實驗表明，該算法用于Web日志挖掘中高效可靠。

參 考 文 獻

［1］Jiawei Han，Micheline amber.數(shù)據(jù)挖掘概念與技術(shù)［M］.2版.北京：機械工業(yè)出版社，2007.

［2］韓家煒，孟小峰，王靜，等.Web挖掘[J].計算機研究與發(fā)展，2001，38(4:405-413.

［3］郭巖，白碩，于滿泉.Web使用信息挖掘綜述[J].計算機科學(xué)，2005，32(1:1-7.

［4］岳訓(xùn)，苗良，鞏君華，等.基于矩陣聚類的電子商務(wù)網(wǎng)站個性化推薦系統(tǒng)[J].小型微型計算機系統(tǒng)，2003，24(11:1 922-1 926.

［5］呂佳.Web日志挖掘技術(shù)應(yīng)用研究[J].重慶師范大學(xué)學(xué)報，2006，23(4:39-44.

［6］趙瑩瑩，韓元杰.Web日志數(shù)據(jù)挖掘中數(shù)據(jù)預(yù)處理模型的研究與建立[J].現(xiàn)代電子技術(shù)，2007，30(4:103-105.