一種快速的Web用戶和URL聚類算法

張線媚

摘 要：本文提出一個(gè)基于Web日志的用戶和URL聚類的快速算法。利用用戶瀏覽行為建立用戶事務(wù)矩陣，在此基礎(chǔ)上綜合考慮用戶瀏覽時(shí)間以及點(diǎn)擊頻率來獲取用戶權(quán)值和頁面權(quán)值，構(gòu)建帶權(quán)值的模糊聚類。為了縮小運(yùn)算量，構(gòu)造等價(jià)事務(wù)，進(jìn)行事務(wù)約減；并針對(duì)于FCM算法簇?cái)?shù)目初始化敏感的問題，提出了一種全局搜索的方法，搜尋最優(yōu)的類中心數(shù)。實(shí)驗(yàn)證實(shí)，該算法在精度和效率上都獲得了大大提高。

關(guān)鍵字：權(quán)值距離；等價(jià)事務(wù)；事務(wù)約減；全局搜索

中圖分類號(hào)： TP274.2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)1672-3791（2015）06（a）-0000-00

因?yàn)榫W(wǎng)站的內(nèi)容及結(jié)構(gòu)的組織形式是否合理直接決定了網(wǎng)站是否受歡迎，所以需要對(duì)Web訪問信息進(jìn)行有效的聚類，分析挖掘出合理有效的運(yùn)行模式和隱含信息等知識(shí)，而在Web訪問信息的聚類過程中，最常用到的方法是頁面聚類和用戶聚類。頁面聚類方法主要是通過分析頁面之間的關(guān)聯(lián)知識(shí)來改進(jìn)站點(diǎn)的組織結(jié)構(gòu)，而用戶聚類則是以相似訪問喜好的用戶作為集合進(jìn)行聚類，為同一集合的用戶提供針對(duì)性的服務(wù)。因此聚類算法研究在Web訪問信息挖掘中起到?jīng)Q定性的作用。

目前多數(shù)日志聚類以Web站點(diǎn)的URL為行、以User-ID為列，建立關(guān)聯(lián)矩陣，對(duì)用戶的訪問時(shí)間進(jìn)行離散后用作矩陣的元素值，經(jīng)過User-ID的相似性分析，得到相似客戶群體，經(jīng)過對(duì)URL的相似性度量獲得相關(guān)Web頁面。

本文首先清洗日志數(shù)據(jù)，然后根據(jù)用戶的瀏覽行為建立矩陣，通過對(duì)矩陣的列向量和行向量進(jìn)行模糊聚類，從而得到用戶聚類和URL聚類。為了提高聚類算法的精度和整體效率，在確定初始中心時(shí)采用了全局搜索方法。

1.日志的清洗

1.1 用戶事務(wù)集合

WEB服務(wù)器日志包括訪問日志、引用日志和代理日志，數(shù)據(jù)清洗主要完成錯(cuò)誤和冗余數(shù)據(jù)的剔除和重復(fù)數(shù)據(jù)的合并操作，用來表示日志信息，利用最大時(shí)間間隔法來得到用戶事務(wù)集合。結(jié)合用戶在頁面上的停留時(shí)間及其點(diǎn)擊次數(shù)，總結(jié)用表示用戶事務(wù)集合，對(duì)于， 有：。其中： ，m表示站點(diǎn)的URL數(shù)，表示到截止到當(dāng)前時(shí)間用戶在上的瀏覽時(shí)間，表示點(diǎn)擊次數(shù)。

1.2瀏覽時(shí)間的離散化

將用戶事務(wù)在站點(diǎn)URL上的瀏覽時(shí)間屬性用間隔（即離散值）表示，將時(shí)間離散化。離散值和實(shí)際時(shí)間的關(guān)系如表1所示：

表1 離散值與瀏覽時(shí)間對(duì)照表

在進(jìn)行離散化時(shí)，當(dāng)用戶在URL上的停留時(shí)間少于5s時(shí)，則離散值取0，表示URL是導(dǎo)航頁而不是內(nèi)容頁，應(yīng)該刪除。考慮主頁訪問的普遍性，所以對(duì)主頁的研究意義不大，也應(yīng)該刪除，即使用戶對(duì)網(wǎng)頁的瀏覽時(shí)間很長，離散值也只有3。這樣可有效判別區(qū)分在用戶事務(wù)的相似性，當(dāng)用戶瀏覽時(shí)間過長或過短時(shí)，如果采用連續(xù)時(shí)間則會(huì)造成聚類結(jié)果畸變。

1.3用戶瀏覽矩陣和用戶點(diǎn)擊矩陣

（1）用戶瀏覽矩陣：

其中：代表Web站點(diǎn)URL的個(gè)數(shù)，代表用戶事務(wù)數(shù)，代表第個(gè)用戶事務(wù)對(duì)第個(gè)URL 的訪問時(shí)間總和。

（2）用戶點(diǎn)擊矩陣：

其中：為Web站點(diǎn)URL的個(gè)數(shù)，為用戶事務(wù)數(shù)，為第個(gè)用戶事務(wù)對(duì)第個(gè)URL 的點(diǎn)擊次數(shù)總和。

用戶瀏覽矩陣中用戶對(duì)該站點(diǎn)中所有URL的訪問情況可表示為，即列向量；所有用戶對(duì)URL“”的訪問情況表示為，即行向量。分別度量二者的相似性，就能得到用戶聚類和URL聚類。

2.聚類算法

2.1 模糊聚類

在數(shù)學(xué)上模糊聚類可用如下的目標(biāo)函數(shù)求極值來表示：

（1）

（2）

綜合考慮（1）式的優(yōu)化和（2）式的約束條件，用拉格朗日乘數(shù)法可求得到和分別為：

（3） （4）

對(duì)（1）式優(yōu)化采用FCM算法：

a.取常數(shù)，令迭代次數(shù)t=0，任選聚類中心；

b.對(duì)按式（3）求得；

c.由式（4）算出下一次類別中心；

d.如果，退出迭代；否則，令t的值加1，跳至步驟b；

數(shù)據(jù)點(diǎn)的分類在每次迭代中同時(shí)進(jìn)行調(diào)整，而且聚類中心需要更新。當(dāng)先后兩次迭代隸屬度矩陣很接近，則算法處于收斂。在得到用戶瀏覽矩陣以后，分別對(duì)行向量和列向量進(jìn)行聚類，得到相似的用戶簇和URL簇。

2.2 帶屬性權(quán)重的歐氏距離

如果采用傳統(tǒng)的歐氏距離，度量列向量和的距離公式為： （5）

度量行向量和的距離公式為：

（6）

由于傳統(tǒng)的距離公式忽略權(quán)重，故提出帶權(quán)重的歐氏距離公式：

（7）

其中：表示第k維數(shù)據(jù)的重要性。

由此可以求得帶權(quán)重的模糊聚類算法目標(biāo)函數(shù)為：

在URL聚類和用戶聚類中，分別代表第k個(gè)用戶的權(quán)重和第k個(gè)URL的權(quán)重。

2.3頁面權(quán)重

用戶具體的瀏覽行為體現(xiàn)在用戶對(duì)頁面的點(diǎn)擊次數(shù)和停留時(shí)間，采用極值法對(duì)點(diǎn)擊次數(shù)進(jìn)行歸一化處理，則對(duì)應(yīng)的點(diǎn)擊權(quán)重值為：

（8）

其中：為單頁面點(diǎn)擊的最大次數(shù)，為單頁面點(diǎn)擊的最小次數(shù)。

同理可得到對(duì)應(yīng)的瀏覽時(shí)間權(quán)重值：

（9）

其中：為單頁面瀏覽的最長時(shí)間，為單頁面瀏覽的最短時(shí)間。

結(jié)合用戶的瀏覽時(shí)間權(quán)重和點(diǎn)擊權(quán)重，構(gòu)建URL權(quán)重計(jì)算的線形公式：

（10）

其中：

（11）

（12）

2.4用戶權(quán)重

同理對(duì)于用戶訪問頻率和訪問時(shí)間，采用權(quán)重概念可得到用戶權(quán)重的計(jì)算公式：

（13）

其中：

（14）

（15）

為歸一化的點(diǎn)擊次數(shù)權(quán)重，反映了各個(gè)用戶總的點(diǎn)擊次數(shù)情況；為歸一化的瀏覽時(shí)間權(quán)重，反映了各個(gè)用戶總的瀏覽時(shí)間情況。

3.聚類中心的選取

模糊聚類算法中，目標(biāo)聚類數(shù)目K要提前設(shè)定，由于算法的迭代都要求沿著使J減小的方向進(jìn)行，而J可能有多個(gè)極值點(diǎn)。當(dāng)確定的初始聚類中心靠近一個(gè)局部極小點(diǎn)時(shí)，則算法收斂到局部最小。為了解決這個(gè)問題，在聚類中可以使用全局優(yōu)化方法中的模擬退火技術(shù)，但是這樣就增加了計(jì)算量，而且收斂速度也會(huì)相應(yīng)減慢，所以實(shí)際應(yīng)用中不常使用。

本文在確定類別數(shù)目時(shí)采用了全局搜索的方法，即取數(shù)據(jù)空間中的多個(gè)數(shù)值進(jìn)行初始化，則初始中心可分布在較廣的范圍，而且滿足了數(shù)據(jù)的多樣性。在聚類過程中利用有效性度量函數(shù)逐步減少聚類數(shù)目K的值，直到有效性函數(shù)的變化趨向于某個(gè)閾值停止。

3.1取樣

在初始化時(shí)為了減少計(jì)算量，對(duì)原始數(shù)據(jù)集合進(jìn)行取樣。采用隨機(jī)取樣，選取能基本代表原始數(shù)據(jù)特性的數(shù)據(jù)作為訓(xùn)練集，在訓(xùn)練集中求得初始化中心點(diǎn)，從而可以快速地找到最優(yōu)的簇?cái)?shù)目。

3.2等價(jià)事務(wù)和事務(wù)約減

當(dāng)兩個(gè)訪問事務(wù)的瀏覽時(shí)間以和點(diǎn)擊次數(shù)相等或相近時(shí)，則它們對(duì)C個(gè)類中心的隸屬度也是相同或相近的。

（1）等價(jià)事務(wù)：

當(dāng)隨機(jī)的兩個(gè)事務(wù)對(duì)應(yīng)的與，滿足，，其中為事前選定的任意小整數(shù)。而且，它們所對(duì)應(yīng)的和，滿足：，，其中為事先設(shè)定的任意小整數(shù)。則它們?yōu)橐粚?duì)等價(jià)事務(wù)。

（2）事務(wù)約減：

有了等價(jià)事務(wù)的概念，原瀏覽矩陣和點(diǎn)擊矩陣可以看成多個(gè)子集的并集

，其中：

因?yàn)榈葍r(jià)事務(wù)對(duì)各中心的隸屬度相同，即：，所以可以利用子集中任意一個(gè)事務(wù)來代表整個(gè)子集，即對(duì)訪問矩陣和點(diǎn)擊矩陣進(jìn)行約減。

3.3全局搜索

為了避免FCM算法中事先確定聚類數(shù)目帶來的難題，引入Xie-Beni聚類有效性度量： （16）

可以設(shè)定一個(gè)較大，（為約減后的事務(wù)數(shù)目）。確保在最小化Xie-Beni聚類有效性度量的情況下，使得設(shè)定的目標(biāo)函數(shù)最優(yōu)，從而得到的簇?cái)?shù)目為最優(yōu)值。

過程執(zhí)行步驟如下：

（1）對(duì)原始數(shù)據(jù)集進(jìn)行取樣，進(jìn)行數(shù)據(jù)約減，得到

（2）對(duì)簇?cái)?shù)目進(jìn)行初始化

（3）任選k個(gè)對(duì)象為最初的簇中心集合

（4）計(jì)算對(duì)象的隸屬度矩陣

（5）由隸屬度矩陣得到新的簇中心集合

（6）重復(fù)隸屬度和簇中心的計(jì)算過程，當(dāng)目標(biāo)函數(shù)處于收斂時(shí)結(jié)束。

（7）迭代XB函數(shù)，令，閾值為，當(dāng)時(shí)停止迭代，最后得到簇?cái)?shù)目k；否則繼續(xù)，令k=k-1，跳轉(zhuǎn)至（4）

因?yàn)樽顑?yōu)簇?cái)?shù)目是從訓(xùn)練集求得中，故計(jì)算量大為減少。全局的聚類和迭帶是在全局搜索求得最優(yōu)化簇?cái)?shù)目后進(jìn)行的，而且求解的結(jié)果在訓(xùn)練集中，所以聚類的效率大為提高。

4.算法仿真及分析

仿真數(shù)據(jù)來自站點(diǎn)的日志數(shù)據(jù)，下載URL為598的WWW服務(wù)器日志文件，選取40000條記錄，對(duì)日志進(jìn)行清洗，最終得到1034個(gè)用戶事務(wù)。算法的性能分析從算法的有效性和效率兩方面進(jìn)行比較。

（1）算法的有效性：與傳統(tǒng)的FCM算法比較，適當(dāng)?shù)卣{(diào)整聚類閾值，得到圖1。

圖1 算法的有效性比較

Fig1.Comparison of the validity of two algorithms

通過圖1中的對(duì)比，可以看到本文的算法在用戶聚類和URL聚類上，有效性都是高于FCM算法。

（2）算法的效率比較：仿真得到如圖2結(jié)果。

圖2 算法的效率比較

Fig2.Comparison of the performance of two algorithms

算法的效率主要通過CPU運(yùn)行的時(shí)間來衡量，從圖2的顯示結(jié)果我們看到本文的算法在進(jìn)行用戶聚類和URL聚類時(shí)，CPU運(yùn)行時(shí)間比FCM算法要小得多，即本文算法在效率上遠(yuǎn)勝于FCM算法。

5.結(jié)語

本文在對(duì)用戶瀏覽時(shí)間做了離散處理后提出了一個(gè)基于用戶離散化時(shí)間、以用戶瀏覽次數(shù)為度量的新的聚類算法，可以進(jìn)行Web用戶和URL的聚類。新算法在傳統(tǒng)FCM算法基礎(chǔ)上，利用訪問時(shí)間和頻率確定用戶和URL權(quán)值，構(gòu)建了帶權(quán)值的模糊聚類。另外，通過事務(wù)約減和全局搜索的方法來確定最優(yōu)的初始簇中心。與已有的FCM算法對(duì)比，仿真結(jié)果表明，新算法在有效性和效率上都有很大提升。

參考文獻(xiàn)：

[1]宋春江，沈鈞毅.一種新的Web用戶群體和URL聚類算法的研究[J].控制與決策.2007，22（3）.

[2]田生文，黃明明.密集簇中心二次模糊聚類算法[J].計(jì)算機(jī)工程與設(shè)計(jì).2007，28（2）.

[3]Jiawei Han， Micheline Kambr.數(shù)據(jù)挖掘概念與技術(shù)[M].北京機(jī)械工業(yè)出版社，2002.223-224.

[4]Xie X，Beni G.A validity measure for fuzzy clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（8）：841一847.

[5]劉小覽，趙英凱，陸金桂.數(shù)據(jù)挖掘中Fuzzy C-means的自適應(yīng)聚類算法[J].南京化工大學(xué)學(xué)報(bào)（自然科學(xué)版），2001，23 （5）.