聚類算法在Web日志挖掘中的研究

彭思琪

摘 要：互聯(lián)網(wǎng)上的信息是一個(gè)價(jià)值難以估量的寶庫，如何利用這些豐富的互聯(lián)網(wǎng)資源是我們需要解決的一個(gè)問題。文中通過數(shù)據(jù)挖掘手段，以服務(wù)器日志為例，論述了Web日志挖掘的概念和步驟，重點(diǎn)介紹了Web日志在聚類算法中的處理方法，最后結(jié)合實(shí)際對(duì)K-means算法的初始點(diǎn)的選取做了改進(jìn)，同時(shí)引入權(quán)重降低了噪聲和孤立點(diǎn)對(duì)聚類結(jié)果的影響。

關(guān)鍵詞：Web日志挖掘；聚類；K-means；權(quán)重

中圖分類號(hào)：TP311.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2015）07-00-02

0 引 言

一個(gè)大型網(wǎng)站通常有成千上萬的網(wǎng)頁，而用戶可能只對(duì)其中某些網(wǎng)頁中的內(nèi)容感趣。對(duì)每個(gè)用戶來說，他們需要的信息也各不相同；這就需要網(wǎng)站對(duì)網(wǎng)站的用戶進(jìn)行分類，給他們推送針對(duì)性強(qiáng)的服務(wù)。而通過數(shù)據(jù)挖掘的技術(shù)手段，對(duì)服務(wù)器日志對(duì)用戶和用戶的行為分類，為不同的用戶推送他們關(guān)注的信息是解決這個(gè)問題的方法。

1 Web日志挖掘概述

1.1 Web挖掘的概念

數(shù)據(jù)挖掘是指從海量的數(shù)據(jù)信息中，通過對(duì)數(shù)據(jù)的分析，提取出我們需要的信息[1]；Web數(shù)據(jù)挖掘是一項(xiàng)具有挑戰(zhàn)性的課題，其目標(biāo)是從Web的超鏈接結(jié)構(gòu)、網(wǎng)頁內(nèi)容和使用日志中探尋有用的信息[2]。

1.2 Web日志挖掘步驟

Web日志挖掘是Web挖掘在Web日志中的使用，主要是通過對(duì)Web日志數(shù)據(jù)的預(yù)處理、分析后，從中獲取感興趣的信息的一種分析模式?[3]。服務(wù)器日志記錄中記錄了用戶的各種網(wǎng)站瀏覽信息，通過分析這些數(shù)據(jù)，我們可以知道用戶對(duì)什么感興趣，網(wǎng)站可以有針對(duì)性的為用戶推送相關(guān)的服務(wù)。典型的Web日志挖掘流程如圖1所示。

圖1 Web日志挖掘流程圖

2 Web事務(wù)聚類探究

2.1 Web日志聚類算法特點(diǎn)

隨著聚類算法的研究和應(yīng)用，我們對(duì)一般數(shù)據(jù)挖掘的聚類算法有了一定的了解，一個(gè)聚類算法通常需要考慮算法是否具有可伸縮性，能否處理不同數(shù)據(jù)的能力、對(duì)于多位數(shù)據(jù)的處理能力、抗噪性能是否良好等問題[4]。

但是對(duì)于Web日志挖掘的數(shù)據(jù)來說，聚類算法僅僅具有上述的特點(diǎn)還不能滿足對(duì)日志數(shù)據(jù)處理的要求。首先對(duì)于一個(gè)大型網(wǎng)站的服務(wù)器日志來說，它的日志記錄是龐大的，所以這就要求聚類算法可以高效地處理這些龐大的日志記錄數(shù)據(jù)，但是一般的算法是不能滿足這個(gè)要求的或者處理的效率不高。其次日志記錄數(shù)據(jù)中，每個(gè)用戶對(duì)一個(gè)網(wǎng)站的網(wǎng)頁通常都是只對(duì)其部分頁面感興趣，因此建立的用戶-頁面矩陣是一個(gè)典型的稀疏矩陣，所以聚類算法處理稀疏矩陣的能力也是我們選擇算法和改進(jìn)算法需要考慮的一個(gè)重要因素。

2.2 用戶訪問矩陣的建立

經(jīng)過對(duì)日志數(shù)據(jù)的預(yù)處理，將網(wǎng)站中的每一個(gè)頁面URL進(jìn)行了編碼；通常一個(gè)設(shè)計(jì)合理的網(wǎng)站，頁面URL之間的層次是比較清楚的。在對(duì)用戶編碼中，通常我們可以選取IP地址或者用戶注冊(cè)的登錄名來區(qū)分不同的用戶。

處理好對(duì)URL編碼和用戶編碼后，我們可根據(jù)用戶瀏覽每個(gè)頁面的平均訪問時(shí)間來分析用戶關(guān)注的信息。通常如果用戶對(duì)網(wǎng)頁的內(nèi)容感興趣，那么用戶瀏覽網(wǎng)頁的時(shí)間就越長(zhǎng)。所以，我們可以通過下面的計(jì)算方法來計(jì)算平均訪問時(shí)間：

AT=PTT/PC

其中AT為頁面平均訪問時(shí)間；PTT為頁面的總訪問時(shí)間；PC：頁面的點(diǎn)擊次數(shù)。

經(jīng)過前期的處理，我們可以構(gòu)建一個(gè)矩陣關(guān)聯(lián)矩陣M，其行為Web站點(diǎn)URL、列為USER。矩陣的元素為某用戶對(duì)某URL的平均訪問時(shí)間，為連續(xù)型數(shù)值：

（1）

其中，n為用戶的數(shù)量，m為頁面的數(shù)量，Uij為第i個(gè)用戶對(duì)第j個(gè)頁面的平均訪問時(shí)間。

由于Uij 是不同的平均時(shí)間值，在進(jìn)行比較的過程中，關(guān)注的是其所占的比重。所以需要將M矩陣進(jìn)行歸一化處理。其處理方式如下：

行向量歸一化得到矩陣M1

。 （2）

列向量歸一化得到矩陣M2

。 （3）

2.3 相似度的定義

本文相似度[5]是使用歐式距離[6]來計(jì)算2個(gè)向量間的距離，其計(jì)算公式如式（4）所示：

（4）

通過該公式可以計(jì)算出M1行向量間的距離，表示兩兩用戶間的距離，結(jié)果為N1，M2列向量間的距離，表示兩兩頁面間的距離，結(jié)果為N2。綜合考慮這2個(gè)因素，通過加入權(quán)值做矩陣加法可以得到以下的相似度矩陣N：

（5）

（6）

Pij表示第i個(gè)對(duì)象到第j個(gè)對(duì)象的相似性，值越大，表示2個(gè)對(duì)象越相近。

2.4 k-means聚類算法的改進(jìn)

目前聚類的算法比較多，基于劃分的較經(jīng)典的有K-means算法[7]，其核心思想如下：

（1）從N個(gè)數(shù)據(jù)元素中選出K個(gè)對(duì)象作為K個(gè)初始簇的在中心。

（2）計(jì)算剩下的數(shù)據(jù)元素與K個(gè)初始簇的相似度，并將各個(gè)元素歸并到相似度最高的簇中。

（3）根據(jù)聚類結(jié)果重新計(jì)算K個(gè)簇的質(zhì)心。

（4）再次計(jì)算N個(gè)元素與K個(gè)簇（質(zhì)心）的相似度，將各個(gè)元素歸并到相似度最高的簇中。

（5）重復(fù)（3）、（4）步，直到每個(gè)簇的中心點(diǎn)不在變化。

K-means算法可以很好地得到數(shù)據(jù)對(duì)象的聚類效果，但是它本身依然還有許多不完善的地方，其中最明顯的2個(gè)缺陷為：初始簇的選取好壞極大地影響了聚類結(jié)果的好壞和速度（迭代次數(shù)），在迭代過程中噪聲和孤立點(diǎn)的影響沒有進(jìn)行過濾。特別是在用于日志挖掘的數(shù)據(jù)對(duì)象的處理中，所以我們需要對(duì)其中的缺陷做出調(diào)整。其改進(jìn)和調(diào)整思路如下：

（1）對(duì)于初始簇的選取，可以選取高密度區(qū)域的點(diǎn)作為初始簇的中心。

（2）加入權(quán)值來減少噪聲和孤立點(diǎn)對(duì)聚類結(jié)果的影響。

根據(jù)上述思路，初始簇的選擇策略如下：

（1）將全部數(shù)據(jù)作為一個(gè)整體，計(jì)算其質(zhì)心a和平均距離d，并選出距離質(zhì)心a最遠(yuǎn)的點(diǎn)作為第一個(gè)初始簇的質(zhì)心b，并將距離質(zhì)心b小于d的點(diǎn)歸到第一個(gè)初始簇中。并將這些點(diǎn)從全部數(shù)據(jù)中刪除；

（2）在剩余數(shù)據(jù)中找到距離質(zhì)心a最遠(yuǎn)的點(diǎn)作為質(zhì)心c；將距質(zhì)心c小于d的點(diǎn)歸到第二個(gè)初始簇中，同時(shí)刪除這些點(diǎn)；

（3）重復(fù)第（2）步直到所有點(diǎn)都?xì)w類到K個(gè)初始簇中。

這樣就可以將全部的數(shù)據(jù)元素按照其分布的密度進(jìn)行劃分，保證每個(gè)初始簇的相識(shí)度都比較高，簇外的元素與簇內(nèi)的元素相識(shí)度都小于該簇的平均值。這樣就可以避免由于人工選擇初始點(diǎn)導(dǎo)致初始簇分布的不合理從而影響聚類的準(zhǔn)確性和聚類的速度。

此時(shí)還不能排除噪聲和孤立點(diǎn)的影響，我們通過添加權(quán)重來減小其影響。其調(diào)整的思路如下：相似度高的點(diǎn)所占的權(quán)重較高，而孤立點(diǎn)和噪聲則權(quán)重較小，權(quán)重的計(jì)算方法如式（7）所示：

（7）

其中：，再通過來計(jì)算質(zhì)心，這樣就可以最大限度地減少噪聲和孤立點(diǎn)的影響。

通過上面的調(diào)整，改進(jìn)后的K-means算法有效地降低了人為選擇初始點(diǎn)不當(dāng)造成的影響，同時(shí)在聚類迭代過程中減小了噪聲和孤立點(diǎn)對(duì)結(jié)果的影響。

3 結(jié) 語

本文主要針對(duì)服務(wù)器日志數(shù)據(jù)在聚類過程中的處理以及K-means在處理日志數(shù)據(jù)的調(diào)整。但這些研究還有待我們進(jìn)一步深入，這樣才能將用戶的信息更好地利用起來。

參考文獻(xiàn)

[1]史振華.基于WEB日志挖掘的網(wǎng)站優(yōu)化技術(shù)及應(yīng)用 [D].武漢：武漢理工大學(xué)，2010.

[2] admin.什么是Web挖掘？[EB/OL].http：//server.zzidc.com/fwqcjwt/web/633.html，2014.6.

[3]崔江彥.基于Web日志挖掘的用戶興趣模式研究[D].南京：南京航空航天大學(xué)，2010.

[4]梁志榮.數(shù)據(jù)挖掘中聚類分析的技術(shù)方法[J].電腦開發(fā)與應(yīng)用，2007，20（2）：37-39.

[5]何躍，馬麗霞，騰格爾.基于用戶訪問興趣的日志挖掘[J].系統(tǒng)工程理論與實(shí)踐，2012，32（6）：1353-1361.

[6]肖云.基于Web日志挖掘的聚類算法研究[D].合肥：安徽大學(xué)，2011.

[7]楊小兵.聚類分析中若干關(guān)鍵技術(shù)的研究[D].杭州：浙江大學(xué)，2005.