一種具有增量挖掘功能的Web點擊流聚類算法

李曉明,夏秀峰,張 斌

(1.沈陽航空工業(yè)學(xué)院 計算機學(xué)院,遼寧 沈陽 110136;2.東北大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽 110004)

一種具有增量挖掘功能的Web點擊流聚類算法

李曉明1,2,夏秀峰1,張 斌2

(1.沈陽航空工業(yè)學(xué)院 計算機學(xué)院,遼寧 沈陽 110136;2.東北大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽 110004)

分析了典型的聚類算法及其適用范圍,針對其處理Web點擊流數(shù)據(jù)的不足,提出了一種用于Web點擊流的增量挖掘的聚類算法WCSCluster,給出了相關(guān)定義及存儲結(jié)構(gòu),并用實例說明了算法的運行過程·最后對比同類算法給出實驗結(jié)果·實驗結(jié)果表明該算法具有良好的性能,能夠發(fā)現(xiàn)更優(yōu)的簇·

Web使用挖掘;點擊流;增量挖掘;聚類

Web使用挖掘就是把數(shù)據(jù)挖掘技術(shù)應(yīng)用到Web點擊流數(shù)據(jù)中,從而發(fā)現(xiàn)使用模式的過程·Web使用挖掘是從數(shù)據(jù)挖掘發(fā)展而來的,在對大量數(shù)據(jù)進行分析的基礎(chǔ)上,作出歸納性的推理,以預(yù)測客戶的行為·Web使用挖掘用于數(shù)據(jù)庫知識發(fā)現(xiàn)的特征化(Characterization)、分類(Classification)、預(yù) 測 (Prediction)、聚 類(Clustering)、關(guān)聯(lián)(Association)和序列模式(Sequential Pattern)分析等技術(shù)·Web服務(wù)器能夠記錄每次Web訪問的詳細點擊信息,例如頁面URL、IP地址、日期、Web站點及配置信息等·其中,通過對Web點擊流數(shù)據(jù)進行聚類技術(shù)研究可以使站點管理者發(fā)現(xiàn)用戶的訪問模式,改進Web服務(wù)器的設(shè)計,提高Web服務(wù)器的性能,以方便用戶使用,增加個性化服務(wù),發(fā)現(xiàn)電子商務(wù)中潛在的客戶·

1 現(xiàn)有算法及存在的不足

傳統(tǒng)的聚類技術(shù)研究最早源于統(tǒng)計學(xué),利用數(shù)據(jù)(點)之間的曼哈頓距離、歐幾里德距離、閔科夫斯基距離[1]來衡量數(shù)據(jù)點之間的相似程度,進而將其劃分到距離最近的簇中·然而,現(xiàn)實世界中的數(shù)據(jù)往往是高維的,并且擁有不同種類的數(shù)據(jù)類型·最常見的數(shù)據(jù)類型分以下6種[2]:區(qū)間標度變量,二元變量,分類變量,序數(shù)變量,比例標度變量,向量對象·

經(jīng)典聚類算法并不適用于直接處理Web點擊流數(shù)據(jù),因此,近年來國內(nèi)外不少學(xué)者在經(jīng)典聚類算法基礎(chǔ)上提出許多改進算法,主要有:FCM dd[3]、時間意識聚類[4]、相似矩陣結(jié)構(gòu)分解[5]、擴展的人工神經(jīng)網(wǎng)絡(luò) k均值[6]等算法·其中一些取得了不錯的效果·但仔細分析上述這些算法,不難發(fā)現(xiàn)它們都存在一個或幾個如下所述的弊端:①不能處理混合屬性的數(shù)據(jù);②需用戶來指定最終簇的數(shù)目;③聚類結(jié)果受離群點數(shù)據(jù)的影響;④大多數(shù)算法不具備增量挖掘功能;⑤數(shù)據(jù)點只屬于一個簇·針對這些弊端,本文提出一個針對Web點擊流數(shù)據(jù)的聚類算法WCSCluster(Web Click Stream Cluster)·

2 相關(guān)概念和定義

設(shè)非空集合I={P1,P2,…,Pn},其中的Pi(1≤i≤n)稱為Web頁面·

定義1 Web點擊流:Web點擊流是用戶訪問Web頁面時的一組連續(xù)訪問序列,記作〈P1,P2,…,Pm〉,其中Pi∈I,1≤i≤m·

定義2 會話(session)序列:會話序列是某個用戶特定時間段的頁面瀏覽序列,記作〈(P1,t1),(P2,t2),…,(Pk,tk)〉,其中ti(1≤i≤k)是用戶在Pi頁面的駐留時間·為方便以下討論我們把會話分成兩個部分,即訪問序列〈P1,P2,…,Pk〉與駐留時間序列〈t1,t2,…,tk〉·

考慮到一個大型的站點可能含有上千個URL,這會造成訪問者之間的公共訪問序列很有可能為空,那么訪問者之間的相似度則為0,即任意兩個用戶都不可能劃分到一個簇中,這顯然不是我們所希望的·這里我們用到了一個層次提升的概念,即將一個站點中的所有URL歸類,如新浪網(wǎng)中可以將所有URL歸類成新聞、軍事、體育、財經(jīng)等,體育類可再分為籃球、足球、排球等,具體劃分程度可視實際應(yīng)用而定·

3 算法描述

文中采用一種類十字鏈表的存儲結(jié)構(gòu)來存儲聚類過程與結(jié)果,具體分為簇頭節(jié)點與會話節(jié)點兩個部分·

為了便于算法描述,對涉及到的相關(guān)概念給出簡要介紹·

定義3 特征訪問序列:特征訪問序列是指一個簇中所有會話節(jié)點訪問序列的交集序列·

定義4 特征訪問時間:特征訪問時間是指特征訪問序列中對應(yīng)的、本簇中所有會話節(jié)點對應(yīng)的訪問時間的平均時間序列·

WCSCluster算法偽代碼如下:

4 實驗分析

與本文最相近的工作是文獻[3]中的FCM dd算法,有別于該文;本文采用了會話節(jié)點與簇頭節(jié)點的相似度計算代替了該文中的相異度矩陣的計算,且本文中的模糊劃分也有別于該文:所以采用FCM dd算法與WCSCluster算法進行比較·實驗采用C#語言,在VS2005下完成,后臺數(shù)據(jù)庫采用SQL Server2005,實驗 PC機配置為2.0 GHz AMD,1 GB RAM,WinXP Professional操作系統(tǒng)·實驗數(shù)據(jù)來自沈陽航空工業(yè)學(xué)院Web服務(wù)器上的日志文件,大小約287 M.約有2 455 600條點擊記錄·

4.1 進行會話重構(gòu)

本文設(shè)定會話的持續(xù)時間上限為30 min,兩個連續(xù)訪問頁面的時間間隔下限為1min,上限為6min,同時剔除那些序列長度小于4的會話(設(shè)定的時間及序列的長度可視具體應(yīng)用調(diào)整)·利用文獻[7]中的方法處理點擊流數(shù)據(jù),從而形成用戶會話·在VS2005下利用C#語言編寫日志抽取程序·進行頁面的層次提升后最終歸為11個大類,對形成的大類進行編碼,即將它們賦值從A到K,清洗掉無用的點擊記錄,最終形成約34 000條會話記錄·將抽取后的結(jié)果存儲到后臺數(shù)據(jù)庫中·

將抽取后的會話記錄分成3個大小不等的數(shù)據(jù)集 DS1、DS2、DS3,DS2與 DS3分別為 DS1的整數(shù)倍,分別約為5 700、11 320、16 980條會話記錄·首先驗證不同閾值下的聚類效果,在3個數(shù)據(jù)集下同時將閾值λ分別取 0.3、0.4、0.5,結(jié)果DS1分別形成9,10,12個簇,DS2分別形成21,24,28個簇,DS3分別形成53,61,72個簇·從聚類結(jié)果上看,隨著閾值的增大簇的數(shù)目會急劇上升,不難看出不同的閾值取值對應(yīng)了不同的劃分結(jié)果,這也驗證了WCSCluster的模糊聚類功能,對比如圖1所示·

圖1 WCSCluster聚類結(jié)果比較

4.2 對比在相同實驗環(huán)境下的WCSCluster算法與FCMdd算法的處理速度與空間消耗

為客觀起見,WCSCluster算法的閾值λ分3次取值,分別為0.3、0.4、0.5,然后兩個算法分別在3個數(shù)據(jù)集上運行·最終兩個算法的時間消耗對比如圖2所示,空間消耗對比如圖3所示·從運行時間比較看來,WCSCluster處理數(shù)據(jù)的時間基本是線性的,時間消耗隨著數(shù)據(jù)集的增大而線性增大·而FCM dd隨著處理數(shù)據(jù)量的增加,處理時間急劇上升·一個好的聚類算法在時間上應(yīng)該近似滿足線性規(guī)律,故從可伸縮性角度上看WCSCluster要比FCM dd更優(yōu)·同時也看到,相同數(shù)據(jù)集下聚類結(jié)果受到閾值大小的影響,但聚類時間主要受數(shù)據(jù)集大小影響,而受閾值影響不大·從空間消耗來看,在相同數(shù)據(jù)集下,WCSCluster的空間消耗比FCM dd要小·仔細分析不難發(fā)現(xiàn),FCM dd建立了相異度矩陣進行數(shù)據(jù)存儲,當會話數(shù)目增多時內(nèi)存消耗會急劇增加·

圖2 WCSCluster與FCMdd運行時間比較

圖3 WCSCluster與FCMdd內(nèi)存消耗比較

5 結(jié) 論

文本全面對比了傳統(tǒng)聚類的各種算法,針對其處理Web點擊流數(shù)據(jù)的不足,提出了一種用于Web點擊流聚類的算法WCSCluster,該算法克服了同類算法中的缺點,具有增量挖掘、模糊聚類、刪除過期會話等功能·分析表明,該算法在處理Web點擊流的聚類問題上優(yōu)于同類其他算法·目前,越來越多的數(shù)據(jù)以流的形式出現(xiàn)·與靜態(tài)Web數(shù)據(jù)相比,動態(tài)Web點擊流具有潛在無窮大、迅速、時變和連續(xù)到達等特點·其中的數(shù)據(jù)按照固定的次序,只能被讀取一次或幾次,不再是永久的關(guān)系形式,數(shù)據(jù)無法全部保存后再進行處理,即無法甚至不可能進行多次 IO操作,對于數(shù)據(jù)的在線處理性、實時性處理提出了更高的要求·如何在動態(tài)環(huán)境下對Web點擊流進行有效聚類是我們下一個研究目標·

[1] Tan Pangning,Steinbach M,Kumar V.Introduction to Data Mining[M].Addison Wesley:Pearson Education,2006:33-35.

[2] Han Jiawei,Kamber M.Data Mining Conceptsand techniques[M].Beijing:Machinery Industry Press,2007:47-48.

[3] Kamdar T,Joshi A.Using incremental Web log mining to create adaptive Web servers[J].Int J Digit Libr,2005(5):133-150.

[4] Petridou S G,Koutsonikola V A,Vabali A I,et al.Time aware Web users clustering[J]. Know ledge and Data Engineering,2008,20(5):653-667.

[5] 周寬久,王艷萍,李瑤.Web用戶聚類算法[J].計算機工程與應(yīng)用,2006,42(16):184-186.

[6] Park S,Suresh N C,Jeong B K.Sequence-based clustering for Web usage mining:a new experimental framework and ANN-enhanced K-means algorithm[J].Data&Know ledge Engineering,2008,65:512-543.

[7] Sadagopan N,Li Jie.Characterizing Typical and Atypical User Sessions in clickstreams[C].Beijing:[s.n.],2008:21-25.

An Incremental M ining Clustering Algorithm for Web Clickstreams

L I Xiaom ing1,2,XIA Xiufeng1,ZHANG Bin2
(1.Computer School,Shenyang Institute of Aeronautical Engineering,Shenyang 110036,China;2.College of Information Science and Engineering,Northeastern University,Shenyang 110004,China)

After analyzing the classic clustering algorithmsand itsconfine,an incrementalmining clustering algorithm w hich is used in Web clickstream s field called WCSCluster is p roposed.Relevant definitions and storage structure are given;running p rocedure is show n by a specific example.Experimental results are given comparing w ith congener algorithms.Experimental results demonstrate that the algorithm has good performance w hich can find superior clusters.

Web usagemining;clickstreams;incrementalmining;clustering

TP 311.131

A

1008-9225(2010)03-0008-03

2010-04-09

李曉明(1980-),男,遼寧丹東人,沈陽航空工業(yè)學(xué)院工程師,東北大學(xué)碩士研究生·

【責任編輯 劉曉鷗】