一種改進的Web社區(qū)結構挖掘系統

羅彩君

（陜西職業(yè)技術學院 計算機科學系，陜西 西安 710100）

一種改進的Web社區(qū)結構挖掘系統

羅彩君

（陜西職業(yè)技術學院 計算機科學系，陜西 西安 710100）

針對HITS算法、傳統最大流算法在挖掘Web社區(qū)時存在主題漂移、噪音頁面等問題，采用基于傳遞概率的邊容量分配最大流改進算法，開發(fā)了一個改進的Web社區(qū)結構挖掘系統，詳細描述了該系統的設計和實現過程。實驗表明，利用該系統進行Web社區(qū)挖掘能較好的解決傳統算法中存在的問題，進一步提高了Web社區(qū)挖掘的準確性。

結構挖掘；Web社區(qū)；體系結構；種子節(jié)點

Web社區(qū)的結構挖掘是基于兩種模型：一個是Hub和Authority模型，一個是拓撲圖中最大流量/最小割集模型?；贖ub和Authority模型的HITS算法挖掘社區(qū)，存在主題漂移等問題，而用傳統的最大流算法，則可能產生一些噪音頁面，降低社區(qū)質量[1]。為解決上述存在的問題，本文開發(fā)了一個改進的Web社區(qū)結構挖掘系統。

1 系統算法分析

在本系統中，將網絡中任意兩個節(jié)點之間的緊密程度用它們之間產生的傳遞概率來度量，傳遞概率的計算可以綜合考慮節(jié)點屬性之間的連接度、節(jié)點之間的相關度、節(jié)點之間發(fā)生信息傳遞等多種因素，進行綜合度量，為不同的邊分配不同的邊值。因此，本系統采用動態(tài)分配邊容量的算法——基于傳遞概率的邊容量分配最大流改進算法進行設計。其算法步驟如下：

Step1：構建種子節(jié)點集合：S={s1，s2，…，sk}；

Step2：對種子節(jié)點集S中的每個節(jié)點以深度為2進行擴展；

Step3：計算鏈接所對應的兩個端點的相關度；

Step4：計算鏈接所對應的兩個端點的出度和入度值，并計算兩端點的傳遞概率值；

Step5：構造鄰接圖 G（V，E）；

Step6：根據 Puv給邊（u，v）分配邊容量 c（u，v）；

Step7：執(zhí)行最大流算法；

Step8：得到仍然同種子節(jié)點相連的節(jié)點集合C={c1，c2，…，cm}；

Step9：將C中入度最高的兩個非種子節(jié)點添加到S中，重復上述過程直到C中節(jié)點比較穩(wěn)定，形成一個穩(wěn)定的社區(qū)；

Step10：對最終結果進行處理，輸出社區(qū)中的各節(jié)點。

此算法在頁面集合基礎上實現更精確的信息聚類、識別、匹配等操作[2]，從而有助于實現根據用戶的搜索請求，為用戶提供更加精準的搜索結果。

2 系統體系結構

系統體系結構主要包括原始數據收集、數據預處理和在線處理等部分，其體系結構如圖1所示。

由于客觀條件的限制，不可能對所有網站數據甚至是所有特定類型的網絡數據進行研究，因此，為了確保Web數據的獲取不影響研究結果的可靠性，選擇了代表性網站作為樣本數據源，即在研究總體中進行抽樣，利用現有搜索引擎對Web數據資源進行搜索，然后對Web的數據進行采集、組織和存儲，建立Text或知識模型庫，通過對樣本的研究達到了解總體的目的。

圖1 Web社區(qū)結構挖掘系統體系結構Fig.1 The system structure of Web community structure mining system

在經過數據采集階段后將進入數據預處理程序中。在網頁文件中存在亂碼、連接重復等問題，為了滿足實驗的要求，必須對所采集的原始數據進行預處理。數據處理是為了更好地進行數據挖掘以獲得高質量的挖掘結果而做的準備工作。數據處理后就可以得到一個比較合理的鄰接Web圖[3]。在數據處理過程中主要做了以下幾個工作:

1）去除死鏈接和無效鏈接，某些網頁已經不存在，或改成新的地址，如果不存在，就刪除這個網頁的URL，如果地址已更改，則用新的URL代替舊的URL。

2）排除那些入鏈接或者出鏈接數超過了500以上的Web頁面，因為這樣的一些頁面往往是非常出名的一些站點頁面，像Yahoo，Google等，這些站點頁面根本就不需要用戶使用什么挖掘策略去獲得。

3）統一URL的格式，去除那些URL里包含有關鍵詞%，?，bbs，cgi-bin，di-ary，news等的頁面，因為這樣的一些頁面往往和用戶要找的主題無關，還會產生更多的主題漂移問題[4]。

4）去除鏡像頁面，所謂的鏡像頁面是指與主網站的內容相同的其它位置的網站頁面，太多的鏡像頁面只會重復同一個頁面內容，擾亂用戶的視野，所以要盡可能事先去除。

在線處理模塊主要目的是利用之前預處理好的數據與Web信息搜索技術相結合，提高傳統搜索引擎的效率及搜索精度。主要包括頁面處理、文檔索引、鏈接分析及Web社區(qū)發(fā)現等模塊組成，最終將發(fā)現的結果返回給用戶，具體過程如圖2所示。

頁面處理：主要功能是將頁面中的所有鏈接提取出來，并對鏈接進行必要的轉換以獲取真實的URL，因為頁面鏈接中給出的URL格式可能是不一樣的，既可能是完整的絕對路徑，也可能是一個相對路徑，為方便處理，需要先將其規(guī)格化為統一的絕對路徑格式。根據一定計算模型可計算出鏈接的價值，并由此預測鏈接指向的頁面對主題的相關性，將其認為主題相關的URL放入URL隊列中以供選擇出合適的URL提供給Crawler進行采集。

文檔索引：為原始網頁建立索引，實現索引網頁庫。針對索引網頁庫切分，將網頁轉化為詞的集合。將網頁到索引詞的映射轉化為索引詞到網頁的映射，同時將網頁中包含的不重復的索引詞匯聚成索引詞表[5]。

圖2 在線處理模塊體系結構圖Fig.2 The system structure diagram of online processing module

鏈接分析：由一組種子URL開始，DNS解析器獲得該URL對應的主機IP地址，然后通過機器人拒絕協議檢測后由HTTP/HEEPS下載模塊下載該網頁。URL抽取器從下載的網頁中抽取出新的URL。然后由URL過濾器逐個檢測是否符合過濾規(guī)則的限制。最后，用哈希函數計算各個URL的哈希值，將符合下載規(guī)則的URL加入到鏈接數據庫中。

Web社區(qū)發(fā)現：根據鏈接分析和文檔分析的結果，關注那些關系較為緊密的節(jié)點，計算出節(jié)點的連接度和節(jié)點相關度[6]，將節(jié)點的連接度與節(jié)點之間的相關度統一起來計算連邊的傳遞概率，依據傳遞概率動態(tài)分配邊的容量，然后執(zhí)行改進的最大流算法，進行Web社區(qū)劃分，對用戶的請求進行分析并返回結果。

3 系統實現

3.1 開發(fā)環(huán)境

本系統開發(fā)環(huán)境為Windows操作系統，2.4 GHz處理器，1 GB內存，768 MB虛擬內存，開發(fā)工具為Visual Studio 2005。

3.2 用戶界面

本文基于Web搜索引擎技術設計并實現了Web社區(qū)結構挖掘系統，其檢索頁面如圖3，Web用戶通過圖3界面輸入要查詢的內容。

圖3 搜索界面Fig.3 Search interface

當輸入主題 “java“時，得到如圖4所示搜索結果。

在搜索結果中，前10個被搜索出的URL都是與主題“java“相關的。

3.3 實驗及性能評價

圖4 搜索結果Fig.4 Search results

Web挖掘需要的數據集往往非常龐大，Web社區(qū)的挖掘需要更大數據資源才能體現算法的性能和優(yōu)越性，為了測試算法的效果和驗證它的有效性，本系統分別選擇10個互不相同的主題頁面作為種子節(jié)點，前5個選擇了以中文為關鍵字的查詢主題，后5個選擇了英文為關鍵字的查詢主題，每一個主題都具有明確的意義。表1中列出了利用本系統的算法和利用原系統算法發(fā)現社區(qū)的情況比較。

表1 兩種系統發(fā)現社區(qū)情況比較Tab.1 The contrast found in community of the two systems

其中 N、URL、CS、W1、W2 分別表示節(jié)點、種子節(jié)點、社區(qū)主題、本系統算法獲得的社區(qū)成員數及原系統算法獲得社區(qū)成員數。W2豎排的第5主題上面標有一個“*”，表示在這種情況下所獲得的社區(qū)體積都是不合理的失敗情況。

如表1所示，本系統算法所獲得的社區(qū)W1在總體上要明顯好于原來系統算法的結果，原來的系統雖然在某些情況下確實獲得了比較好的結果，但在另外一些情況下卻產生了非常壞的結果，比如在主題5情況下，所獲得的結果就不理想。

4 結束語

Web在發(fā)展過程中存在大量的社區(qū)，社區(qū)可以為用戶提供有價值的、可靠的、及時的信息。本文在深入研究了Web社區(qū)[7]結構挖掘算法的基礎上開發(fā)了一個改進的Web社區(qū)結構挖掘系統。實驗證明，利用該系統進行Web社區(qū)挖掘，能很好的解決主題漂移、噪音頁面等問題，從而發(fā)現更多有價值的社區(qū)。

[1]楊杰，姚莉秀.數據挖掘技術及其應用[M].上海:上海交通大學出版社，2011.

[2]李星，鐘志農，景寧，等.社區(qū)挖掘技術研究[J].計算機工程與科學，2012，34（9）:157-158.

LI Xing，ZHONG Zhi-nong，JING Ning，et al.Research on community detection methon[J].Computer Enginteering and Science， 2012，34（9）:157-158.

[3]陳麗萍.基于Web鏈接結構的挖掘算法研究與應用[J].巢湖學院學，2011，13（6）:39-40.

CHEN Li-ping.Research and application of mining algorithm basedonWebhyperlinkstructure[J].JournalofChaohu College，2011，13（6）:39-40.

[4]劉兵.Web數據挖掘[M].北京:清華大學出版社，2009.

[5]Takaffoli M，Sangi F，Fagnan J，et al.Community evolution mining in dynamic social networks[J].Procedia-Social and Behavioral Sciences，2011，7（55）:49-58.

[6]李瑩，吳曉軍.基于最大流及頁面相似度的Web結構挖掘[J].計算機技術與發(fā)展，2011，21（10）:112-113.

LI Ying，WU Xiao-jun.Web structure mining based on maximum flow and page similar value[J].Computer Technology and Development，2011，21（10）:112-113.

[7]李剛.基于SOA的Web GIS系統框架設計分析[J].陜西電力，2011（2）：38-41.

LI Gang.Web GIS system frame design analysis based on SOA[J].Shaanxi Electric Power，2011（2）：38-41.

An improved Web community structure mining system

LUO Cai-jun
（Department of Computer Science， Shaanxi Vocational and Technical College， Xi’an 710100， China）

For the topic drift，noise pages and other problems of the HITS algorithm and the traditional maximum flow algorithm in mining Web community，maximum flow improvement algorithm based on transmission probability's side capacity assignment is used， an improvement Web community structure mining system is developed，and described this system design and the realization process in detail.It is proved with numbers of experiment that the system of the community structure mining can well solve problems of traditional algorithm，the accuracy of the Web community mining is more improved.

structure mining； Web community； system structure； seed node

TP391

A

1674－6236（2014）12-0034-03

2013-12-26稿件編號201312218

陜西省教育廳科學研究計劃項目（2013JK0433）；陜西職業(yè)技術學院國家骨干高職院校建設項目課題（GJ1314）

羅彩君（1979—），女，湖南桂東人，碩士，副教授。研究方向：計算機應用技術、數據處理。