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

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

關鍵詞：Web日志；挖掘；語義；本體

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

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

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

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

1相關工作

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

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

2．1語義日志模型

基于本體的領域建模的中心任務是建立可共享的領域詞匯集。

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

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

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

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

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

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

3基于SWLM的網頁聚類與用戶聚類算法

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

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

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

算法1利用語義相似進行網頁聚類的算法

4實驗及分析

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

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…

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

5結束語

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

參考文獻：

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

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

[3]王實，高文，李錦濤．Web數據挖掘[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，France:[s.n.]，1996:18－32．

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