一種新的基于事物聚類(lèi)Web瀏覽偏愛(ài)路徑挖掘算法

李曉靜，王樹(shù)森

（濟(jì)源職業(yè)技術(shù)學(xué)院，濟(jì)源 459000）

0 引言

使用Web用戶(hù)瀏覽偏愛(ài)路徑挖掘算法分析Web日志記錄，并發(fā)現(xiàn)用戶(hù)訪(fǎng)問(wèn)規(guī)律，已成功應(yīng)用于個(gè)性化推薦、系統(tǒng)改進(jìn)以及商業(yè)智能等方面。目前在瀏覽模式的獲取上常用的算法主要有最大頻繁序列法、引用長(zhǎng)度法和樹(shù)型拓?fù)浣Y(jié)構(gòu)法等[1]，但是這些算法其實(shí)都是一種改進(jìn)的關(guān)聯(lián)規(guī)則算法，存在以下兩方面的問(wèn)題：一是簡(jiǎn)單地認(rèn)為用戶(hù)的瀏覽頻度就代表了用戶(hù)的訪(fǎng)問(wèn)興趣度，這很片面；其次，隨著網(wǎng)絡(luò)的發(fā)展，Web日志數(shù)據(jù)逐漸呈現(xiàn)出分布性、異構(gòu)性、動(dòng)態(tài)性和海量性等特點(diǎn)[2]，傳統(tǒng)的集中式數(shù)據(jù)挖掘算法就不能滿(mǎn)足對(duì)擁有海量數(shù)據(jù)的Web日志進(jìn)行挖掘處理的需求。

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

1 改進(jìn)的事物聚類(lèi)算法

1.1 事物聚類(lèi)算法的基本定義

設(shè)n個(gè)用戶(hù)訪(fǎng)問(wèn)路徑集合U={C1,C2,…,Cn}，其中一條訪(fǎng)問(wèn)路徑為Ci={V1,V2,…,Vi}，其中Vi表示一個(gè)被訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)。

定義1：用戶(hù)訪(fǎng)問(wèn)路徑中節(jié)點(diǎn)的個(gè)數(shù)等于路徑長(zhǎng)度C。

定義2：雅克比系數(shù)：

例如有兩條W eb用戶(hù)訪(fǎng)問(wèn)路徑C1={V1，V2，V3}，C2={V2，V1，V3}，采用雅克比系數(shù)進(jìn)行計(jì)算的結(jié)果均為1，但是這兩條路徑顯然是不相同的，這是因?yàn)檠趴吮认禂?shù)所描述的事務(wù)數(shù)據(jù)不具有先后次序關(guān)系，而用戶(hù)訪(fǎng)問(wèn)Web路徑卻是有先后順序的，因此不能單純用雅克比系數(shù)來(lái)描述訪(fǎng)問(wèn)路徑的相似度。

設(shè)定 c omm( ci, cj)表示最長(zhǎng)公共路徑長(zhǎng)度，的最長(zhǎng)路徑長(zhǎng)度，則用戶(hù)訪(fǎng)問(wèn)路徑的相似度系數(shù)為：

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

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

該系數(shù)綜合考慮了雅克比系數(shù)和相似度系數(shù)的優(yōu)點(diǎn)，其中βα,為調(diào)節(jié)度量的系數(shù)，雅克比系數(shù)所起的作用隨著α值的增大而增大，相似度系數(shù)的作用隨著β值的增大而增大，順序性也相應(yīng)增強(qiáng)。采用該系數(shù)進(jìn)行全部路徑之間相似度的計(jì)算，得到訪(fǎng)問(wèn)路徑的相似度數(shù)據(jù)矩陣S：

1.2 改進(jìn)的事物聚類(lèi)算法

在將訪(fǎng)問(wèn)路徑進(jìn)行兩兩合并的過(guò)程中，最大相似度系數(shù)起到了決定性作用，而大部分小于閾值的相似度系數(shù)對(duì)聚類(lèi)是不起作用的[5]，因此要解決傳統(tǒng)聚類(lèi)算法在Web日志高維空間數(shù)據(jù)聚類(lèi)時(shí)的“維數(shù)災(zāi)難”問(wèn)題，可以通過(guò)過(guò)濾較小的相似度系數(shù)，從而大大縮小數(shù)據(jù)規(guī)模。

算法1 輸出用戶(hù)訪(fǎng)問(wèn)的相似路徑聚類(lèi)

輸入：Web 日志文件，并設(shè)定一個(gè)閾值θ；

輸出：相似路徑聚類(lèi) C = { Ci}。

算法描述：

C = {φ}；//初始化

While（沒(méi)有到文件尾）

{

從數(shù)據(jù)表中讀取記錄；

While（沒(méi)有到文件尾）

{

從數(shù)據(jù)表中讀取記錄；

計(jì)算訪(fǎng)問(wèn)路徑的相似度系數(shù) S = ( S')α( S'')β；

If（S>θ）//對(duì)S和閾值θ進(jìn)行大小比較

{保留當(dāng)前的路徑編號(hào)；

}

}

得到臨時(shí)聚類(lèi) Ci；

If（ Ci不是類(lèi)集合C中的一個(gè)子集）

{

將 Ci增加到類(lèi)集合C中；

}

}

計(jì)算相交項(xiàng)對(duì)各自類(lèi)的隸屬度，并依據(jù)隸屬度的大小消除重復(fù)項(xiàng)；

輸出得到的聚類(lèi)C。

2 改進(jìn)的偏愛(ài)路徑挖掘算法

2.1 瀏覽頻度的偏愛(ài)度

若用戶(hù)有m種途徑離開(kāi)某Web頁(yè)面，則出現(xiàn)次數(shù)相對(duì)較高的選擇是用戶(hù)較為感興趣的、偏愛(ài)度較高的選擇[4]。

定義1：設(shè)定Si表示用戶(hù)通過(guò)第i種選擇進(jìn)入下一個(gè)頁(yè)面的頻度。根據(jù)傳統(tǒng)置信度以及公式1的定義，在不考慮所訪(fǎng)問(wèn)站點(diǎn)的結(jié)構(gòu)對(duì)傳統(tǒng)置信度的限制的情況下，設(shè)定用戶(hù)的第i種選擇的置信度為：

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

由此可見(jiàn)，在n>1時(shí)，由于偏愛(ài)度系數(shù)P在n種選擇中考慮了用戶(hù)通過(guò)第i種途徑瀏覽網(wǎng)頁(yè)的可能性，因此比傳統(tǒng)置信度更能準(zhǔn)確地反映出用戶(hù)的興趣度。

2.2 瀏覽興趣的偏愛(ài)度

公式5的算法僅僅考慮了用戶(hù)瀏覽頁(yè)面的頻度，這是不全面的[6,7]。因?yàn)橛脩?hù)的興趣度與其訪(fǎng)問(wèn)頁(yè)面的大小、時(shí)間、次數(shù)均有關(guān)系。頁(yè)面大則瀏覽時(shí)間長(zhǎng)；瀏覽時(shí)間長(zhǎng)，則說(shuō)明用戶(hù)的瀏覽興趣度高；同時(shí)，用戶(hù)的瀏覽興趣度還取決于訪(fǎng)問(wèn)次數(shù)。

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

2.3 改進(jìn)的偏愛(ài)路徑挖掘算法

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

例1挖掘用戶(hù)偏愛(ài)路徑的過(guò)程

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 改進(jìn)的Web瀏覽偏愛(ài)路徑挖掘算法

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

輸出：Web瀏覽偏愛(ài)路徑集合NPS。

3 實(shí)驗(yàn)結(jié)果分析

設(shè)定URL表示站點(diǎn)頁(yè)面的數(shù)目，采用上述算法可以得出挖掘?yàn)g覽偏愛(ài)子路徑的時(shí)間復(fù)雜度是，將相同路徑進(jìn)行合并的時(shí)間是，從而得出總時(shí)間是

在實(shí)驗(yàn)過(guò)程中，采用包含25930條記錄，35個(gè)頁(yè)面的Web日志作為實(shí)驗(yàn)對(duì)象，分別使用本文提出的改進(jìn)偏愛(ài)路徑挖掘算法與MFP算法在設(shè)定的閾值控制下進(jìn)行路徑挖掘，在這兩種算法挖掘出相同數(shù)量的偏愛(ài)子路徑和頻繁瀏覽子路徑的情況下，與已知的該網(wǎng)站訪(fǎng)問(wèn)偏愛(ài)路徑進(jìn)行比較，從而得出各自的準(zhǔn)確性。

圖1 算法的準(zhǔn)確度比較

由此可見(jiàn)，本文提出的改進(jìn)算法比MFP算法在挖掘偏愛(ài)子路徑方面有更高的準(zhǔn)確性。同時(shí)，從圖1可以看出隨著挖掘路徑數(shù)的增加這兩個(gè)算法的準(zhǔn)確性都有所降低。這是因?yàn)橥诰蚺d趣度量閾值會(huì)隨著路徑個(gè)數(shù)的增加而降低，致使挖掘偏愛(ài)路徑的可信度也隨之下降。為了檢測(cè)兩種算法的挖掘時(shí)間性能，在實(shí)驗(yàn)中，將實(shí)驗(yàn)對(duì)象分別劃分為5000條記錄、15000條記錄、20000條記錄、25000條記錄，通過(guò)對(duì)執(zhí)行時(shí)間進(jìn)行比較得到圖2。從中可以看出改進(jìn)的用戶(hù)瀏覽模式挖掘算法比傳統(tǒng)的MFP算法的執(zhí)行時(shí)間增加幅度小，擴(kuò)展性好。

圖2 算法的時(shí)間性能比較

4 結(jié)束語(yǔ)

本文提出了一種改進(jìn)的基于事物聚類(lèi)W eb日志用戶(hù)偏愛(ài)瀏覽路徑的挖掘方法，首先通過(guò)對(duì)事物聚類(lèi)算法的改進(jìn)，消除重復(fù)項(xiàng)及相交項(xiàng)，從而更準(zhǔn)確地反應(yīng)出Web用戶(hù)訪(fǎng)問(wèn)路徑相似度，接著以一個(gè)三元組模型為基礎(chǔ)，對(duì)多個(gè)相似用戶(hù)群體相關(guān)頁(yè)面集的偏愛(ài)瀏覽路徑進(jìn)行了挖掘。最后通過(guò)與其他算法相比較，本文算法在準(zhǔn)確性和時(shí)間性能等方面具有一定優(yōu)越性，能針對(duì)不同用戶(hù)群體的Web瀏覽偏愛(ài)路徑進(jìn)行更加全面、精確地挖掘，可擴(kuò)展性好。

[1] 李健,徐超,譚守標(biāo).一種Web數(shù)據(jù)挖掘系統(tǒng)的設(shè)計(jì)和研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,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日志的頻繁瀏覽路徑挖掘技術(shù)研究[D].遼寧師范大學(xué),2009,5.

[5] 吳雯雯.基于W eb的用戶(hù)訪(fǎng)問(wèn)模式挖掘算法及其應(yīng)用研究[D]. 合肥工業(yè)大學(xué),2008,5.

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

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

[8] 朱志國(guó),鄧貴仕.持久偏愛(ài)的Web用戶(hù)訪(fǎng)問(wèn)路徑信息挖掘方法[J],情報(bào)學(xué)報(bào),2010:29(2):208-214.

[9] 富麗娜.關(guān)聯(lián)規(guī)則算法研究及其在汽車(chē)銷(xiāo)售網(wǎng)站的應(yīng)用[D], 大連理工大學(xué),2007.10.