一種新的基于事物聚類Web瀏覽偏愛路徑挖掘算法

李曉靜，王樹森

（濟源職業技術學院，濟源 459000）

0 引言

使用Web用戶瀏覽偏愛路徑挖掘算法分析Web日志記錄，并發現用戶訪問規律，已成功應用于個性化推薦、系統改進以及商業智能等方面。目前在瀏覽模式的獲取上常用的算法主要有最大頻繁序列法、引用長度法和樹型拓撲結構法等[1]，但是這些算法其實都是一種改進的關聯規則算法，存在以下兩方面的問題：一是簡單地認為用戶的瀏覽頻度就代表了用戶的訪問興趣度，這很片面；其次，隨著網絡的發展，Web日志數據逐漸呈現出分布性、異構性、動態性和海量性等特點[2]，傳統的集中式數據挖掘算法就不能滿足對擁有海量數據的Web日志進行挖掘處理的需求。

為了解決上述問題，本文將事物聚類算法和W eb用戶瀏覽模式挖掘算法相結合，并對現有算法進行改進，提出將雅克比系數與最長公共路徑系數相乘綜合考慮的方法，更準確地反應用戶之間的相似度，該方法采用一個三元組表示頁面興趣度，綜合考慮了用戶的訪問時間、所訪問頁面的大小以及訪問次數等因素，從而構造出以引用網頁的URL地址為行、瀏覽網頁的URL地址為列，以訪問興趣度為元素值的數據矩陣，在此基礎上采用改進的挖掘算法對該矩陣進行偏愛度和興趣度的計算[3]。用戶通過選擇進入下一個頁面時，由于綜合考慮了頁面的訪問次數、訪問時間和頁面大小，從而可以得到更為準確地偏愛路徑。

1 改進的事物聚類算法

1.1 事物聚類算法的基本定義

設n個用戶訪問路徑集合U={C1,C2,…,Cn}，其中一條訪問路徑為Ci={V1,V2,…,Vi}，其中Vi表示一個被訪問過的節點。

定義1：用戶訪問路徑中節點的個數等于路徑長度C。

定義2：雅克比系數：

例如有兩條W eb用戶訪問路徑C1={V1，V2，V3}，C2={V2，V1，V3}，采用雅克比系數進行計算的結果均為1，但是這兩條路徑顯然是不相同的，這是因為雅克比系數所描述的事務數據不具有先后次序關系，而用戶訪問Web路徑卻是有先后順序的，因此不能單純用雅克比系數來描述訪問路徑的相似度。

設定 c omm( ci, cj)表示最長公共路徑長度，的最長路徑長度，則用戶訪問路徑的相似度系數為：

如有3條W eb訪問路徑C1={V1，V2，V3}、C2={V2，V3，V4}、C3={V3，V2，V4}，則C1→C2的最長公共路徑為V2、V3，長度為2，相似度系數為0.5，而C1→C3的最長公共路徑為V2或V3，長度為1，相似度系數為0.25，而C2和C3兩條路徑中的節點完全相同，節點順序也大致相同，但是使用該公式計算的相似度僅為0.33，比C1→C2的相似度還低，這顯然是不合理的。為此對路徑相似度作如下改進：

定義4：路徑 Ci→Cj之間的相似度度量記作：

該系數綜合考慮了雅克比系數和相似度系數的優點，其中βα,為調節度量的系數，雅克比系數所起的作用隨著α值的增大而增大，相似度系數的作用隨著β值的增大而增大，順序性也相應增強。采用該系數進行全部路徑之間相似度的計算，得到訪問路徑的相似度數據矩陣S：

1.2 改進的事物聚類算法

在將訪問路徑進行兩兩合并的過程中，最大相似度系數起到了決定性作用，而大部分小于閾值的相似度系數對聚類是不起作用的[5]，因此要解決傳統聚類算法在Web日志高維空間數據聚類時的“維數災難”問題，可以通過過濾較小的相似度系數，從而大大縮小數據規模。

算法1 輸出用戶訪問的相似路徑聚類

輸入：Web 日志文件，并設定一個閾值θ；

輸出：相似路徑聚類 C = { Ci}。

算法描述：

C = {φ}；//初始化

While（沒有到文件尾）

{

從數據表中讀取記錄；

While（沒有到文件尾）

{

從數據表中讀取記錄；

計算訪問路徑的相似度系數 S = ( S')α( S'')β；

If（S>θ）//對S和閾值θ進行大小比較

{保留當前的路徑編號；

}

}

得到臨時聚類 Ci；

If（ Ci不是類集合C中的一個子集）

{

將 Ci增加到類集合C中；

}

}

計算相交項對各自類的隸屬度，并依據隸屬度的大小消除重復項；

輸出得到的聚類C。

2 改進的偏愛路徑挖掘算法

2.1 瀏覽頻度的偏愛度

若用戶有m種途徑離開某Web頁面，則出現次數相對較高的選擇是用戶較為感興趣的、偏愛度較高的選擇[4]。

定義1：設定Si表示用戶通過第i種選擇進入下一個頁面的頻度。根據傳統置信度以及公式1的定義，在不考慮所訪問站點的結構對傳統置信度的限制的情況下，設定用戶的第i種選擇的置信度為：

定義2：對某一網站，設定其中所有URL集為U，所有子路徑集為W，假如Ww?，則wx∈?（x表示由Uu∈?構成的頁面瀏覽序列，其中第i位表示第i個瀏覽頁面），該瀏覽序列的前m位是相同的，但第m+1位存在n個不同的頁面，表示從m位到m+1位有n種不同的瀏覽途徑，因此，設定第j（j=1,2,…,n）種瀏覽途徑的偏愛度為：

由此可見，在n>1時，由于偏愛度系數P在n種選擇中考慮了用戶通過第i種途徑瀏覽網頁的可能性，因此比傳統置信度更能準確地反映出用戶的興趣度。

2.2 瀏覽興趣的偏愛度

公式5的算法僅僅考慮了用戶瀏覽頁面的頻度，這是不全面的[6,7]。因為用戶的興趣度與其訪問頁面的大小、時間、次數均有關系。頁面大則瀏覽時間長；瀏覽時間長，則說明用戶的瀏覽興趣度高；同時，用戶的瀏覽興趣度還取決于訪問次數。

定義3：用戶的瀏覽興趣度記作I(URL.time,URL.size,URL.num)，設定頁面URLi→U RLj的次數為num，在頁面 U RLj的訪問時間為 U RLi→j.time ，頁面URLj的大小為 U RLj.s i ze 。則定義用戶的興趣度為：

2.3 改進的偏愛路徑挖掘算法

設定某一網站有n個URL頁面，在此構造出一個URL-URL矩陣，其中行元素為URL-Reference，列元素為URL，元素值為用戶從一個引用頁鏈接到訪問頁的興趣度值；并在行和列中各自增設一個Null空值，如果用戶是直接輸入網頁地址或者是從其他網站鏈接訪問頁面，則Null空值就出現在行中；如果用戶在所訪問的頁面上退出網站或者從該網站鏈接到外部站點，則Null空值就出現在列向量中[8]。另外，任一網頁的引用頁都不能為自身，因此該矩陣的對角線元素為0。

例1挖掘用戶偏愛路徑的過程

Null A B C D E F G H 總和Null 0 63 15 2 5 0 0 0 5 90 A 6 0 36 35 0 0 0 0 0 77 B 43 0 0 0 6 40 0 0 8 97 C 3 0 0 0 0 10 30 0 0 43 D 16 0 0 0 0 8 0 35 20 79 E 3 0 0 0 0 0 31 0 0 34 F 5 0 0 23 0 0 0 0 0 28 G 4 45 0 0 0 0 0 0 0 49 H 6 0 0 0 0 0 0 0 0 6

算法2 改進的Web瀏覽偏愛路徑挖掘算法

輸入：設定Web瀏覽矩陣M[n+1][n+1]，Sup表示瀏覽支持度閾值，Pre表示瀏覽偏愛度閾值；

輸出：Web瀏覽偏愛路徑集合NPS。

3 實驗結果分析

設定URL表示站點頁面的數目，采用上述算法可以得出挖掘瀏覽偏愛子路徑的時間復雜度是，將相同路徑進行合并的時間是，從而得出總時間是

在實驗過程中，采用包含25930條記錄，35個頁面的Web日志作為實驗對象，分別使用本文提出的改進偏愛路徑挖掘算法與MFP算法在設定的閾值控制下進行路徑挖掘，在這兩種算法挖掘出相同數量的偏愛子路徑和頻繁瀏覽子路徑的情況下，與已知的該網站訪問偏愛路徑進行比較，從而得出各自的準確性。

圖1 算法的準確度比較

由此可見，本文提出的改進算法比MFP算法在挖掘偏愛子路徑方面有更高的準確性。同時，從圖1可以看出隨著挖掘路徑數的增加這兩個算法的準確性都有所降低。這是因為挖掘興趣度量閾值會隨著路徑個數的增加而降低，致使挖掘偏愛路徑的可信度也隨之下降。為了檢測兩種算法的挖掘時間性能，在實驗中，將實驗對象分別劃分為5000條記錄、15000條記錄、20000條記錄、25000條記錄，通過對執行時間進行比較得到圖2。從中可以看出改進的用戶瀏覽模式挖掘算法比傳統的MFP算法的執行時間增加幅度小，擴展性好。

圖2 算法的時間性能比較

4 結束語

本文提出了一種改進的基于事物聚類W eb日志用戶偏愛瀏覽路徑的挖掘方法，首先通過對事物聚類算法的改進，消除重復項及相交項，從而更準確地反應出Web用戶訪問路徑相似度，接著以一個三元組模型為基礎，對多個相似用戶群體相關頁面集的偏愛瀏覽路徑進行了挖掘。最后通過與其他算法相比較，本文算法在準確性和時間性能等方面具有一定優越性，能針對不同用戶群體的Web瀏覽偏愛路徑進行更加全面、精確地挖掘，可擴展性好。

[1] 李健,徐超,譚守標.一種Web數據挖掘系統的設計和研究[J].計算機技術與發展,2009(02):70-73.

[2] Pierrako S D,Paliouras G.Web Usage M ining as a T00l for Personalization:A survey[J].K luw er A cadem ic Publishers,2003：311-372.

[3] Myra S,Lukaa F. A data m iner analyzing the navigational behaviour of web users [EB/OL].http://www.w iw i.hu_berlin.de/～myra/w_acai99.ps.gz,1999-07-16/2001-07-28.

[4] 付玉.基于W eb日志的頻繁瀏覽路徑挖掘技術研究[D].遼寧師范大學,2009,5.

[5] 吳雯雯.基于W eb的用戶訪問模式挖掘算法及其應用研究[D]. 合肥工業大學,2008,5.

[6] 繆勇,宋斌.基于Web日志的典型匿名用戶路徑挖掘研究[J].計算機應用,2009,29(10):2774-2777.

[7] 張海玉,劉曉霞.一種挖掘用戶瀏覽模式的新方法[J],計算機應用與軟件,2007,24(2):143-150.

[8] 朱志國,鄧貴仕.持久偏愛的Web用戶訪問路徑信息挖掘方法[J],情報學報,2010:29(2):208-214.

[9] 富麗娜.關聯規則算法研究及其在汽車銷售網站的應用[D], 大連理工大學,2007.10.