面向Ｗｅｂ日志的語義聚類算法

摘要：由于現(xiàn)有的Web日志缺少明顯語義，提出一種語義Web日志模型——SWLM，并給出基于該模型的網(wǎng)頁和用戶聚類算法。通過日志概念的語義距離定量計算來聚類網(wǎng)頁和用戶，奠定了Web個性化服務(wù)的基礎(chǔ)。性能測試實驗證明，該模型具有較好的整體性能，能有效地進行網(wǎng)頁和用戶聚類。

關(guān)鍵詞：Web日志；挖掘；語義；本體

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2007)07－0267－03

Web日志挖掘?qū)儆赪eb使用挖掘。它通過挖掘相關(guān)的Web日志記錄，來發(fā)現(xiàn)用戶訪問Web頁面的模式，通過分析日志記錄中的規(guī)律，識別用戶的忠實度、喜好、滿意度，發(fā)現(xiàn)潛在用戶，增強站點的服務(wù)競爭力。但是，現(xiàn)有的Web日志挖掘是基于語法的數(shù)據(jù)挖掘，舍棄了數(shù)據(jù)之間豐富的語義關(guān)聯(lián)信息[1，2]。為了使Web上的信息具有計算機可理解的形式語義，滿足智能軟件代理（Agent）對WWW上異構(gòu)和分布信息的有效訪問及檢索[3]，在XML2000的會議上，Berners－Lee提出語義Web及其層次關(guān)系——基于XML和RDF/RDFS，并在此之上構(gòu)建本體（Ontology）和邏輯推理規(guī)則，以完成基于語義的知識表示和推理，從而能夠被計算機所理解和處理。本體提供了語義Web上一切對象和行為描述的詞匯集合，同時又是Web上數(shù)據(jù)的解釋模板。

基于本體的語義Web日志首先定義一個描述概念集，即建立符合學科領(lǐng)域要求、用開放語言描述的概念集體系（Ontology Systems），利用概念集體系對Web日志的內(nèi)容進行語義標注或語義挖掘，形成基于語義的日志元數(shù)據(jù)。在此基礎(chǔ)上，利用概念集中語義定義、語義關(guān)系定義和推理規(guī)則，實現(xiàn)基于語義的Web日志挖掘，如用戶聚類［4］。

1相關(guān)工作

Web日志挖掘是Web挖掘的重要內(nèi)容之一，也是當前數(shù)據(jù)挖掘研究的一個熱點問題。Web日志挖掘通常分為數(shù)據(jù)預(yù)處理、模式發(fā)現(xiàn)和模式分析三個階段[1]。現(xiàn)有的大量研究工作均基于這三個方面。在數(shù)據(jù)預(yù)處理階段，文獻[5]提出了挖掘異常數(shù)據(jù)的方法和途徑。文獻[6]提出了基于最大前向引用的事務(wù)辨識。在模式發(fā)現(xiàn)階段，文獻[7]把服務(wù)器日志載入數(shù)據(jù)立方體結(jié)構(gòu)，執(zhí)行OLAP。文獻[8]使用Markov模型生成序列模式，用于Web預(yù)取和系統(tǒng)優(yōu)化；在模式分析階段，如WebWatcher跟蹤用戶的瀏覽行為，辨識出用戶可能感興趣的鏈接并推薦給用戶。對每個用戶，WebWatcher先對其興趣進行簡單的描述，然后基于該用戶的瀏覽行為和具有相似興趣的其他用戶的瀏覽行為學習該用戶的興趣。但是現(xiàn)階段的研究大多都是基于語法的日志挖掘，隨著語義Web的逐漸升溫[8]，把語義知識和領(lǐng)域本體集成到Web日志挖掘中去已經(jīng)成為可能。

2語義Web日志模型——SWLM

2．1語義日志模型

基于本體的領(lǐng)域建模的中心任務(wù)是建立可共享的領(lǐng)域詞匯集。

定義1領(lǐng)域本體（Domain Ontologies）可以定義為一個四元組：

2．2基于本體的語義相似度計算

在一個相應(yīng)的本體概念層次樹中，計算兩個語義對象相似問題，應(yīng)該主要考慮以下三個問題：

(1)距離。這是主要的衡量標準，通常層次樹中距離越遠的語義對象其差異越大，即相似度就越小；距離越近的語義對象其差異越小，即相似度就越大。這是直觀上容易得到的。

(2)深度。路徑長度相同的兩個節(jié)點，如果位于概念層次的越底層，其語義距離較大。比如動物和植物、哺乳動物和爬行動物，這兩對概念間的路徑長度在一概念層次樹中均是2。但前一對詞處于語義樹的較高層，因此認為其語義距離較大，后一對詞處于語義樹的較低層，其語義距離更小。

(3)區(qū)域密度。路徑長度相同的兩個節(jié)點，如果位于概念層次樹中高密度區(qū)域，其語義距離應(yīng)大于位于低密度區(qū)域。本體中概念描述的粗細程度不均。假設(shè)某些區(qū)域概念的描述極其詳盡，而有些區(qū)域的概念描述又較粗疏，所以加入了概念層次樹區(qū)域密度對語義距離的影響。

3基于SWLM的網(wǎng)頁聚類與用戶聚類算法

對于一個包括一定數(shù)量的靜態(tài)頁面和大量的根據(jù)用戶查詢請求動態(tài)生成頁面的網(wǎng)站來說，它的Log中含有大量的語義信息。針對這些語義信息，用計算事務(wù)語義相似度的方法來對Log記錄進行處理。為此，必須建立一個Web與用戶的交互模型，利用這個交互模型來處理語義。

根據(jù)式（1）可以在概念層次樹結(jié)構(gòu)中判斷兩個語義對象的相似度。對于一個產(chǎn)生動態(tài)網(wǎng)頁的查詢字符串由一個或多個語義對象組成，分別計算對應(yīng)的單個語義對象的相似度；然后利用式（2）加權(quán)求和得到整個查詢字符串的相似度，它也就代表了動態(tài)網(wǎng)頁的語義相似度。利用這個相似度可以對動態(tài)網(wǎng)頁按照一定的算法進行聚類，也可以根據(jù)不同用戶的語義事務(wù)的相似度按照一定算法來對用戶進行聚類。這樣用戶在查詢相關(guān)網(wǎng)頁時可以根據(jù)用戶的查詢信息對用戶進行實時推薦語義相似度相對較高的網(wǎng)頁，也可以對有較高語義相似度的用戶進行類似推薦。

下面給出利用語義相似進行網(wǎng)頁聚類和用戶聚類的兩個算法：

算法1利用語義相似進行網(wǎng)頁聚類的算法

4實驗及分析

使用www.animal.net網(wǎng)站的Web服務(wù)器的日志文件來測試算法和公式。為了加以對比，也使用傳統(tǒng)的基于關(guān)鍵詞匹配的方法來聚類網(wǎng)頁和用戶。選取網(wǎng)站日志文件2005年1月1日00∶00∶00~1月31日23∶59∶59所有的訪問信息。共有12 345個不同的IP對123 456個網(wǎng)頁進行了1 234 567次訪問。以其中的102 354個由查詢字符串生成的動態(tài)網(wǎng)頁為測試源，并從中抽出了123 561次有效的會話過程。首先，用本體來描述整個站點的名詞和動詞，然后再通過把用于產(chǎn)生動態(tài)頁面的查詢詞語集映射到相應(yīng)的概念層次。根據(jù)公式計算對應(yīng)詞語的語義相似度，然后再利用算法對這些動態(tài)網(wǎng)頁聚類，從而為用戶提供推薦。

search.php?key=animal+can+fly

Class1:search.php?key=bird+have+wing

search.php?key=bird

search.php?key=eagle …

search.php?key=wild +animals

Class2:search.php?key=swan

search.php?key=crane…

Class3:search.php?key=animals +salvation

search.php?key= animals + protect…

分別用本文中的算法和基于關(guān)鍵詞匹配的算法進行用戶和網(wǎng)頁聚類測試，并對聚類結(jié)果進行比較。圖1給出了使用本文算法和使用關(guān)鍵詞匹配算法結(jié)果的比較。其中，X軸表示類的數(shù)量，Y軸表示每一類的數(shù)量。從結(jié)果中可以清楚地看出，使用基于關(guān)鍵詞匹配的算法聚類，幾乎大部分的用戶都獨自成為一個類。這樣顯然忽視了用戶之間的相似性和共性。表1給出的是使用本文算法聚類的部分結(jié)果。從表1可以明顯看出，如果使用基于關(guān)鍵詞匹配的方法聚類，那么很多具有相似內(nèi)容的網(wǎng)頁均要被劃分在不同的類中。而使用本文算法把頁面合理地分成相應(yīng)數(shù)目的類，每個類的頁面之間的確存在著相似的內(nèi)容，可以一并推薦給用戶。

5結(jié)束語

對于大部分由用戶的查詢生成動態(tài)網(wǎng)頁的網(wǎng)站來說，采用本文的公式和算法來聚類網(wǎng)頁及用戶，向用戶推薦相關(guān)的感興趣的網(wǎng)頁是合理有效的。該算法和公式克服了傳統(tǒng)的只是關(guān)鍵詞匹配的不足。隨著語義網(wǎng)的興起，語義知識越來越多地受到人們的關(guān)注和利用。該算法只是闡述了一個可利用的方向，算法的效率問題、靜態(tài)網(wǎng)頁的語義表示問題等都是下一步的研究重點。

參考文獻：

［1］HAN J，KAMBER M．數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，盂小峰，等譯．北京：機械工業(yè)出版社，2001:441－443.

[2]王繼成，潘金貴，張福炎．Web文本挖掘技術(shù)研究[J]．計算機研究與發(fā)展，1998，37(5)：513－520.

[3]王實，高文，李錦濤．Web數(shù)據(jù)挖掘[J]．計算機科學，2000，21(4)：28－31.

[4]CHEN Hsinchun，CHUNG Wingyan，JENNIFER J，et al.Crime data mining：a general framework and some examples[J]． IEEE Computer，2004，37(4)：50－56．

[5]HAUCK R V，CHEN H．Coplink：a case of intelligent analysis and knowledge management[C]//Proc of the International Conference on Information Systems.North Carolina，USA：[s.n.]，1999:15－28．

[6]AGRAWAL R，GEHRKE J，GUNOPULOS D．Automatic sub space clustering of high dimensional data for data mining applications[C]//Proc of International Conference on Management of Data．New York：ACM Press，1998:95－105．

[7]CANNATARO M，COMITO C．A data mining ontology for grid programming[C]//The 1st International Workshop on Semantics in Peer－to－Peer and Grid Computing[C]．Budapest，Hungary:[s.n.]，2003:113－134．

[8]MEHTA M，AGAWAL R，RISSANEN J．SLIQ：a fast scalable classi－fier for data mining[C]//Proc of the 5th International Conference on Extending Database Technology (EDBT)． Avignon，F(xiàn)rance:[s.n.]，1996:18－32．

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”