羅彩君

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

一種改進的Web社區(qū)結(jié)構(gòu)挖掘系統(tǒng)

羅彩君

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

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

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

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

1 系統(tǒng)算法分析

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

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

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

Step3：計算鏈接所對應(yīng)的兩個端點的相關(guān)度；

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

Step5：構(gòu)造鄰接圖 G（V，E）；

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

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

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

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

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

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

2 系統(tǒng)體系結(jié)構(gòu)

系統(tǒng)體系結(jié)構(gòu)主要包括原始數(shù)據(jù)收集、數(shù)據(jù)預(yù)處理和在線處理等部分，其體系結(jié)構(gòu)如圖1所示。

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

圖1 Web社區(qū)結(jié)構(gòu)挖掘系統(tǒng)體系結(jié)構(gòu)Fig.1 The system structure of Web community structure mining system

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

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

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

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

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

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

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

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

圖2 在線處理模塊體系結(jié)構(gòu)圖Fig.2 The system structure diagram of online processing module

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

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

3 系統(tǒng)實現(xiàn)

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

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

3.2 用戶界面

本文基于Web搜索引擎技術(shù)設(shè)計并實現(xiàn)了Web社區(qū)結(jié)構(gòu)挖掘系統(tǒng)，其檢索頁面如圖3，Web用戶通過圖3界面輸入要查詢的內(nèi)容。

圖3 搜索界面Fig.3 Search interface

當(dāng)輸入主題 “java“時，得到如圖4所示搜索結(jié)果。

在搜索結(jié)果中，前10個被搜索出的URL都是與主題“java“相關(guān)的。

3.3 實驗及性能評價

圖4 搜索結(jié)果Fig.4 Search results

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

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

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

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

4 結(jié)束語

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

[1]楊杰，姚莉秀.數(shù)據(jù)挖掘技術(shù)及其應(yīng)用[M].上海:上海交通大學(xué)出版社，2011.

[2]李星，鐘志農(nóng)，景寧，等.社區(qū)挖掘技術(shù)研究[J].計算機工程與科學(xué)，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鏈接結(jié)構(gòu)的挖掘算法研究與應(yīng)用[J].巢湖學(xué)院學(xué)，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數(shù)據(jù)挖掘[M].北京:清華大學(xué)出版社，2009.

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

[6]李瑩，吳曉軍.基于最大流及頁面相似度的Web結(jié)構(gòu)挖掘[J].計算機技術(shù)與發(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系統(tǒng)框架設(shè)計分析[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

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

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