羅彩君

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

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

羅彩君

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

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

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

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

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

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

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

Step2：對(duì)種子節(jié)點(diǎn)集S中的每個(gè)節(jié)點(diǎn)以深度為2進(jìn)行擴(kuò)展；

Step3：計(jì)算鏈接所對(duì)應(yīng)的兩個(gè)端點(diǎn)的相關(guān)度；

Step4：計(jì)算鏈接所對(duì)應(yīng)的兩個(gè)端點(diǎn)的出度和入度值，并計(jì)算兩端點(diǎn)的傳遞概率值；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 用戶界面

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

圖3 搜索界面Fig.3 Search interface

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

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

3.3 實(shí)驗(yàn)及性能評(píng)價(jià)

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

Web挖掘需要的數(shù)據(jù)集往往非常龐大，Web社區(qū)的挖掘需要更大數(shù)據(jù)資源才能體現(xiàn)算法的性能和優(yōu)越性，為了測(cè)試算法的效果和驗(yàn)證它的有效性，本系統(tǒng)分別選擇10個(gè)互不相同的主題頁(yè)面作為種子節(jié)點(diǎn)，前5個(gè)選擇了以中文為關(guān)鍵字的查詢主題，后5個(gè)選擇了英文為關(guān)鍵字的查詢主題，每一個(gè)主題都具有明確的意義。表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é)點(diǎn)、種子節(jié)點(diǎn)、社區(qū)主題、本系統(tǒng)算法獲得的社區(qū)成員數(shù)及原系統(tǒng)算法獲得社區(qū)成員數(shù)。W2豎排的第5主題上面標(biāo)有一個(gè)“*”，表示在這種情況下所獲得的社區(qū)體積都是不合理的失敗情況。

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

4 結(jié)束語(yǔ)

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

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

[2]李星，鐘志農(nóng)，景寧，等.社區(qū)挖掘技術(shù)研究[J].計(jì)算機(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]李瑩，吳曉軍.基于最大流及頁(yè)面相似度的Web結(jié)構(gòu)挖掘[J].計(jì)算機(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ì)分析[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稿件編號(hào)201312218

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

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