基于加權矩陣聚類的Ｗｅｂ日志挖掘算法
2008-04-12 00:00:00趙娜田保慧姜建國
現代電子技術 2008年12期
摘 要：Web服務器日志中記錄了用戶的瀏覽模式，為了從中提取出具有相似訪問模式的用戶群，對其提供個性化服務，提出一種針對Web日志的分析方法。通過構建UserID-URL關聯矩陣，引入加權關聯矩陣，提出一種基于加權矩陣的聚類算法——多標記傳播算法。實驗表明，該算法在Web日志挖掘中進行用戶聚類和頁面聚類是高效可靠的。
關鍵詞：數據挖掘；Web日志挖掘；加權矩陣聚類；多標記傳播算法;用戶聚類
Web Log Mining Algorithm Based on Weighted Matrix Cluster
HAO Na1，2 ，TIAN Baohui1，JIANG Jianguo1
(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 引 言
隨著因特網的迅速發展，Web在人們的日常生活和工作中的地位日益顯著［1，2］。Web中包含頁面的內容信息、超鏈接信息，以及Web頁面的訪問和使用信息，如何針對這些信息，應用數據挖掘技術挖掘出有用的信息，更好地為用戶服務，已經成為目前國內外的一個新的研究熱點［3］。在Internet中，對于特定的網站而言，其頁面之間的拓撲結構是已知的。盡管不同的用戶在不同時期可能會有不同的瀏覽模式，但長期趨勢應該是穩定的。因此，挖掘特定網站一定時期內用戶的訪問信息，便可以發現該網站的相似用戶群體以及相關頁面信息，從而對相似用戶群提供個性化服務。本文對Web站點的拓撲結構和用戶瀏覽信息進行分析，以UserID為行、URL為列，構建UserID-URL關聯矩陣，元素值為用戶訪問頁面的次數。在此基礎上，通過閾值參數的引入，將關聯矩陣轉化為加權關聯矩陣，提出一種基于加權矩陣的聚類算法——多標記傳播算法(multiMarker propagation algorithm。該算法利用矩陣的稀疏特性，可從1個稀疏矩陣中抽出1個稠密子矩陣，因此，對用戶（頁面）聚類的過程，也轉化為從稀疏矩陣中抽取稠密子矩陣的過程。
2 加權矩陣聚類
矩陣聚類［4］（Matrix Cluster，MC）最初是為客戶關系管理（Customer Relationship Management，CRM）提出的。圖1所示的關聯矩陣，[WTHX]M[WTBX]m×n中，行代表用戶，列代表頁面。矩陣元素值hi，j表示用戶i訪問頁面j，的次數。以往文獻常見做法是用0或者1來表示用戶是否訪問某個頁面，直接對關聯矩陣進行歸一化處理得到元素值非0即1的矩陣，再運用各種算法進行聚類分析。
為了更好地刻畫用戶的特征向量，反映出用戶的訪問頻度和興趣所在，本文引入加權關聯矩陣的概念。加權關聯矩陣，[WTHX]A[WTBX]m×n由關聯矩陣加權處理轉化而來。通常這樣的加權矩陣是個大而稀疏的矩陣。
由于用戶和頁面的順序不是很重要，所以行和列可以任意交換。圖2顯示了從給定加權矩陣中抽取出的稠密矩陣。如圖所示，抽取出的稠密矩陣包括用戶B，D，F，G 及頁面1，3，6，這個子矩陣可解釋成如下這樣：用戶B，D，F，G在訪問頁面1，3，6時具有一個共同特征。同時頁面1，3，6被用戶B，D，F，G的訪問也具有一個共同的特征。
下面給出支持度和置信度的概念：
支持度抽取出的子矩陣的面積，此處定義為：子矩陣的行×子矩陣的列；
置信度抽取出的子矩陣的密度，即：子矩陣中非0元素的個數/子矩陣的面積；
這樣，加權矩陣聚類的問題就轉化為從稀疏矩陣中找出面積大于指定支持度且密度大于指定置信度的所有子矩陣的問題。
3 多標記傳播算法
當矩陣很大時，一般算法會反復交換行或列，進行大量的計算，本文提出的基于加權矩陣聚類的多標記傳播算法能夠通過應用矩陣的稀疏特性來減少執行時間。該算法使用標記傳播，標記傳播通常定義為一個計算模型，它描述一個作為結點的處理單元和一個作為鏈接邊的結點間的關系。標記傳播通過從與結點，N相連的活動結點傳輸一個標記的方式激活結點N。在多標記傳播算法中，行(列代表結點。當一個矩陣元素非0時，相應的行和列被一個雙向邊連接。當一個結點收到一個標記時，它會把該標記累積起來形成標記總數，標記總數通常用于裁剪。，
如果某結點收到的標記總數小于指定的閾值，那么，該結點對應的行(列被裁剪，被裁剪掉的行(列不再參與后面的運算；需要說明的是，當執行行裁剪時，活動列只能激活那些與對應活動列標記相同的行。不過，由行發送標記時，只要對應列為非0元素均可被激活。標記會反復地在行(列之間傳播，直到活動的行(列不再變化為止，即行(列裁剪結束，此時如果發現剩余的活動行和列，均大于用戶指定的行和列的最小值(支持度，并且矩陣密度也大于用戶指定的最小密度(置信度，則剩余的活動行(列對應的用戶(頁面即為用戶(頁面聚類，否則，說明沒有滿足要求的用戶(頁面聚類存在。
為了算法的需要，這里引入幾個概念：
用戶信度：用戶點擊所有頁面的累計次數；
頁面信度：頁面被所有用戶點擊的累計次數；
最小標記數：剪切矩陣的條件。
多標記傳播算法結構如下：
輸入：加權關聯矩陣，[WTHX]A[WTBX]m×n、，最小支持度、最小置信度、最小用戶信度、最小頁面信度、最小標記數。
輸出：用戶聚類和頁面聚類。
初始化；
找出所有用戶信度小于指定值的行；
找出所有頁面信度小于指定值的列；
剪切掉所有用戶信度低于給定閾值的行和所有頁面信度低于給定閾值的列；
repeat
{
找出含有非零元素的行開始；
repeat
{
行標記清零；
[（]行裁剪[CD2]按照初始行所在列的標記激活相應的行（激活的條件是兩行對應列的權值相等），剪切行標記總數小于最小標記數的行；列標記清零；列裁剪[CD2]剪切列標記總數小于最小標記數的列；[）]
} until (沒有裁剪
[（]求出面積大于支持度，并且密度大于置信度的子矩陣；輸出用戶聚類和頁面聚類；清除用戶聚類和頁面聚類的標志； [）]
} until (沒有非0元素的行
由分析得知，多標記傳播算法的時間復雜度為，O((M + N×M×N。，該算法會反復在行與列之間傳播標記，直到活動的行與列不再變化為止，處理過程如圖3所示。
這里需要指出，選擇不同的起始行，則會得到不同的聚類結果。若以A行作為初始行，則得到的聚類結果為由A，E，G行和1，4，5列組成的子矩陣。
4 應用實例及實驗結果
Web訪問日志是Web服務器用以記錄用戶訪問網站各頁面情況的文件［5］。對Web日志進行數據采集、預處理后，得到每個用戶訪問每個URL頁面的信息。用本文提出的多標記傳播算法實現用戶聚類，把用戶劃分成若干個用戶群，具有相似訪問模式的用戶被分在同一個群體中，相同用戶群中所訪問的頁面也具有相同的特征。
為了驗證多標記傳播算法的有效性，實驗提取某高校網站Web服務器上1天的日志記錄，共57 138條記錄，數據凈化后得到5 126條記錄，經過數據清洗、用戶識別和格式化操作后提取112個用戶和53個URL頁面數，使用本文提出的算法最后識別出6類用戶群，圖4以柱形圖的形式直觀地表示最終的用戶聚類情況。
5 結 語
本文描述加權矩陣聚類及其在Web日志挖掘中的應用，通過構建UserID-URL關聯矩陣，引入加權關聯矩陣的概念，提出一種基于加權矩陣的聚類算法——多標記傳播算法，該算法利用矩陣的稀疏特性，從一個稀疏矩陣中抽出一個稠密子矩陣實現用戶（頁面）聚類，實驗表明，該算法用于Web日志挖掘中高效可靠。
參 考 文 獻
［1］Jiawei Han，Micheline amber.數據挖掘概念與技術［M］.2版.北京：機械工業出版社，2007.
［2］韓家煒，孟小峰，王靜，等.Web挖掘[J].計算機研究與發展，2001，38(4:405-413.
［3］郭巖，白碩，于滿泉.Web使用信息挖掘綜述[J].計算機科學，2005，32(1:1-7.
［4］岳訓，苗良，鞏君華，等.基于矩陣聚類的電子商務網站個性化推薦系統[J].小型微型計算機系統，2003，24(11:1 922-1 926.
［5］呂佳.Web日志挖掘技術應用研究[J].重慶師范大學學報，2006，23(4:39-44.
［6］趙瑩瑩，韓元杰.Web日志數據挖掘中數據預處理模型的研究與建立[J].現代電子技術，2007，30(4:103-105.
