一種以主題詞為特征的排序劃界網(wǎng)站聚類算法*

路文華,羅鈞旻,趙 丹,高武奇

(西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,西安 710021)

clustering

互聯(lián)網(wǎng)的快速發(fā)展使得網(wǎng)絡(luò)信息呈指數(shù)級(jí)增長(zhǎng),雖然信息越來(lái)越豐富,但是人們很難取得真正需要的信息,搜索引擎通過對(duì)網(wǎng)絡(luò)信息的組織與管理為人們有效獲取信息提供了便利,網(wǎng)頁(yè)作為網(wǎng)絡(luò)信息的載體,讓計(jì)算機(jī)理解網(wǎng)絡(luò)信息語(yǔ)義,可以更好的把網(wǎng)頁(yè)按照各類主題進(jìn)行分類,對(duì)其進(jìn)行有效分類可以極大提高人們獲取信息的效率.

為了讓計(jì)算機(jī)理解Web資源的意義,Berners-Lee提出了語(yǔ)義Web[1]的概念；文獻(xiàn)[2]認(rèn)為語(yǔ)義Web的核心——本體沒有考慮到主體agent[3]的能動(dòng)性,將agent的概念引入到本體中得到動(dòng)態(tài)本體的概念,文獻(xiàn)[4]用動(dòng)態(tài)本體描述語(yǔ)言來(lái)描述動(dòng)態(tài)本體,文獻(xiàn)[5]認(rèn)為語(yǔ)義是與agent的自我意識(shí)分不開的,以動(dòng)態(tài)本體描述語(yǔ)言為基礎(chǔ)對(duì)agent的自我意識(shí)進(jìn)行了研究.文獻(xiàn)[6]在文獻(xiàn)[5]的研究基礎(chǔ)上,將整個(gè)互聯(lián)網(wǎng)看成是一個(gè)由具有自我意識(shí)的網(wǎng)站agent、網(wǎng)眼agent以及客戶agent組成的動(dòng)態(tài)本體.網(wǎng)眼agent對(duì)其所認(rèn)知的網(wǎng)站agent、客戶agent、信息資源、及其之間關(guān)系的描述就構(gòu)成了網(wǎng)眼agent的自我意識(shí),也就構(gòu)成了Web的語(yǔ)義結(jié)構(gòu),而網(wǎng)站agent間的分類關(guān)系[7]是其中最重要的一種關(guān)系,文中通過對(duì)網(wǎng)站結(jié)構(gòu)[8]的分析,提出了一種基于主題詞的網(wǎng)站特征值排序劃界聚類算法,并對(duì)網(wǎng)站進(jìn)行聚類,以期更好地設(shè)計(jì)出Web語(yǔ)義結(jié)構(gòu).

1 主題詞與網(wǎng)站結(jié)構(gòu)分析

從用戶角度仔細(xì)觀察每個(gè)網(wǎng)站可知,一個(gè)網(wǎng)站是由一個(gè)主網(wǎng)頁(yè)和多級(jí)子網(wǎng)頁(yè)組成.每一個(gè)網(wǎng)頁(yè)的上方或者側(cè)面都會(huì)顯示與該網(wǎng)頁(yè)要表述內(nèi)容相關(guān)的子網(wǎng)頁(yè)的標(biāo)題,點(diǎn)開這些標(biāo)題就會(huì)連接到相關(guān)的子網(wǎng)頁(yè),這些子網(wǎng)頁(yè)的標(biāo)題稱為該網(wǎng)頁(yè)的主題詞.網(wǎng)頁(yè)的中間部分一般是網(wǎng)站推薦的一些以主題詞為標(biāo)題的子欄目,子欄目是這個(gè)主題詞代表的子網(wǎng)頁(yè)的重要內(nèi)容的目錄.最下方是有關(guān)網(wǎng)站的自我介紹等內(nèi)容.因此,可把網(wǎng)站看成是由主題詞組成的樹型結(jié)構(gòu),一個(gè)主題詞的下層主題詞是對(duì)這個(gè)主題詞的解釋.網(wǎng)站主頁(yè)是一個(gè)網(wǎng)站的總體概括,含有表現(xiàn)這個(gè)網(wǎng)站主要內(nèi)容的主題詞.

2 基于主題詞的網(wǎng)站聚類思想

基于主題詞的網(wǎng)站特征值排序劃界聚類算法可以分為三個(gè)階段:主題詞收集、網(wǎng)站特征值收集和網(wǎng)站聚類.

1) 主題詞收集:收集盡可能多的網(wǎng)頁(yè),抓取其上的主題詞并計(jì)算該詞出現(xiàn)的頻率,按出現(xiàn)頻率從大到小對(duì)主題詞排序,對(duì)同義詞合并、刪除無(wú)意義詞及出現(xiàn)頻率極小的主題詞等精簡(jiǎn)優(yōu)化處理后得到有序的主題詞表,那么這個(gè)主題詞表就是對(duì)整個(gè)Web網(wǎng)站要表述內(nèi)容的抽象；

2) 網(wǎng)站特征值收集:設(shè)計(jì)一個(gè)無(wú)符號(hào)大整數(shù),其位數(shù)與這個(gè)主題詞表中主題詞個(gè)數(shù)相同,位次與這個(gè)主題詞表中主題詞出現(xiàn)頻率對(duì)應(yīng),每個(gè)網(wǎng)站對(duì)應(yīng)這樣一個(gè)無(wú)符號(hào)大整數(shù),若某個(gè)主題詞在這個(gè)網(wǎng)站上出現(xiàn),就把對(duì)應(yīng)位置1,否則置0,我們稱這個(gè)無(wú)符號(hào)大整數(shù)為這個(gè)網(wǎng)站的特征值；

3) 網(wǎng)站聚類:根據(jù)特征值的大小對(duì)網(wǎng)站排序,計(jì)算相鄰網(wǎng)站的距離[9],根據(jù)距離值的大小對(duì)網(wǎng)站分類.

3 主題詞收集

刪除無(wú)意義詞及出現(xiàn)頻率極小的主題詞等精簡(jiǎn)優(yōu)化處理后,得到1536*64條主題詞,根據(jù)主題詞出現(xiàn)頻率從大到小排序,主題詞表navword(ID,Nav,Number,Frequecy),其屬性含義見表1.

表1 主題詞表

4 網(wǎng)站特征值的收集

4.1 相關(guān)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

在網(wǎng)站特征值收集階段,與其相關(guān)的數(shù)據(jù)結(jié)構(gòu)包括三個(gè),分別為:

1) 定義一個(gè)元素類型為URL的數(shù)組WS,用于存放要聚類的m個(gè)網(wǎng)站的URL.

2) 定義一個(gè)二維long型數(shù)組metadata[m][n]:用于存放m個(gè)網(wǎng)站的特征值,每個(gè)網(wǎng)站的特征值由n個(gè)long型數(shù)組成.

3) 定義一特征詞表nav_index(ID,Nav,Number,Frequecy,LL,BB,value),前四項(xiàng)字段含義同主題詞表,后三項(xiàng)的字段含義見表2.

其部分?jǐn)?shù)據(jù)見表3.

表2 特征詞表

表3 特征詞表部分?jǐn)?shù)據(jù)

4.2 獲取網(wǎng)站特征值

依次取WS中網(wǎng)站主頁(yè)的主題詞與特征詞表中的特征詞進(jìn)行匹配,若特征詞表中有該主題詞,則把該網(wǎng)站特征值中代表該特征詞的那一位置1,即把該詞的value值與該詞所對(duì)應(yīng)的網(wǎng)站特征值中的long型變量的值相加,得到該網(wǎng)站的特征值.具體算法如下:

① 定義并初始化二維long型數(shù)組metadata,初值為0；

② 查看網(wǎng)站表中是否有未被抓取過的主頁(yè)地址,如果有,則取出一條未被抓取過的記錄,轉(zhuǎn)③,否則,結(jié)束；

③ 取得該記錄的網(wǎng)站編號(hào)id和網(wǎng)站主頁(yè)URL；

④通過該URL獲取該網(wǎng)站主頁(yè)的內(nèi)容content；

⑤ 使用正則表達(dá)式匹配獲取該網(wǎng)站主頁(yè)的所有主題詞；

⑥ 將得到的主題詞依次與特征詞表nav_index中的主題詞進(jìn)行匹配,如果沒有,則丟棄,如果有,則從特征詞表中找到該主題詞屬于網(wǎng)站特征值的第幾個(gè)long型值l和該詞的value值v；

⑦ 計(jì)算網(wǎng)站特征值,metadata[id][l]=metadata[id][l]+v；

⑧ 查看該主頁(yè)的主題詞是否已匹配完,如果沒有,取下一主題詞,轉(zhuǎn)⑥,否則,轉(zhuǎn)②.網(wǎng)站搜狐的特征值為:

{0:12 890 906 240 245 811,1:213 198 865 169 606 298 6,2:139 418 397 535 119 38,……,153 3:0,153 4:0,153 5:0}

5 Web網(wǎng)站聚類

5.1 Web網(wǎng)站排序

用基數(shù)排序算法根據(jù)網(wǎng)站特征值(1536個(gè)long型值)從大到小對(duì)網(wǎng)站數(shù)組WS排序,得到一個(gè)有序的網(wǎng)站數(shù)組SW.

5.2 計(jì)算網(wǎng)站距離

由于內(nèi)容相似的網(wǎng)站特征值會(huì)比較接近,可以分為一類,因此,用SW中兩個(gè)相鄰網(wǎng)站間特征值的差作為分類的依據(jù),差值越小網(wǎng)站內(nèi)容越相似.用數(shù)組distance[m-1][n]來(lái)記錄數(shù)組SW中相鄰網(wǎng)站間的距離,由相鄰兩個(gè)網(wǎng)站的特征值異或得到.

5.3 網(wǎng)站距離號(hào)

定義一整型數(shù)組DS用來(lái)記錄SW中相鄰網(wǎng)站間的距離從大到小排序的排序號(hào),簡(jiǎn)稱距離號(hào).距離號(hào)越小,說明網(wǎng)站間距離越大,網(wǎng)站內(nèi)容差異越大.

由于相鄰網(wǎng)站之間的距離值由n個(gè)long型數(shù)組成,不方便計(jì)算,因此,以距離號(hào)作為網(wǎng)站類別劃分的參數(shù),計(jì)算方便且不會(huì)對(duì)分類結(jié)果造成影響.

5.4 聚類算法

根據(jù)給定的分類數(shù)Cn,計(jì)算對(duì)應(yīng)的距離號(hào)Δ(Δ=Cn-1),則小于等于Δ的距離號(hào)稱作類分割距離號(hào).類分割距離號(hào)把SW中的網(wǎng)站分割成Cn類,每一類的第一個(gè)網(wǎng)站稱作類分割點(diǎn).因此,對(duì)SW中的網(wǎng)站聚類,就是根據(jù)Δ尋找SW中的類分割點(diǎn),兩個(gè)類分割點(diǎn)之間的網(wǎng)站被劃分成一類.尋找類分割點(diǎn)的算法如下:

① 定義一個(gè)整型數(shù)組CDP[Δ],記錄類分割點(diǎn),初始化為0；定義一個(gè)整型變量j,記錄CDP中元素的下標(biāo),初始化為0；

定義一個(gè)整型變量i作為DS的下標(biāo),初始化為0；

② 判斷DS[i]是否小于等于Δ,如果是,則DS[i]是一個(gè)類分割距離號(hào),轉(zhuǎn)③,否則,轉(zhuǎn)④；

③ CDP[J]=i,j++.判斷i是否等于m-1,如果是,則結(jié)束,否則,轉(zhuǎn)④；

④i++,轉(zhuǎn)②；

5.5 測(cè)試結(jié)果及分析

實(shí)驗(yàn)一:選取20個(gè)網(wǎng)站作為聚類的網(wǎng)站對(duì)象,利用文中算法將其劃分成5類；匹配特征詞表中的主題詞獲取到各個(gè)網(wǎng)站的元數(shù)據(jù),并根據(jù)網(wǎng)站元數(shù)據(jù)的大小對(duì)其進(jìn)行排序,得到的SW如表4中所示的websiteURL列；計(jì)算相鄰網(wǎng)站間的距離并根據(jù)距離大小排序,得到每個(gè)網(wǎng)站的距離排序號(hào),記錄在DS中,見表4中所示的ds列；由于要?jiǎng)澐譃?類,可確定Δ是4,根據(jù)Δ尋找類分割點(diǎn),見表4中所示的websiteID列.

表4 網(wǎng)站聚類數(shù)據(jù)1

從表4中可以看出,該算法將20個(gè)網(wǎng)站劃分成了主題較為鮮明的5個(gè)類別,在網(wǎng)站的分類上是有效的.

實(shí)驗(yàn)二:選取90個(gè)網(wǎng)站作為聚類的網(wǎng)站對(duì)象,文中算法將其分為9類,部分?jǐn)?shù)據(jù)見表5.

表5 網(wǎng)站聚類部分?jǐn)?shù)據(jù)2Fig.5 Data of website clustering 2

表5中為90個(gè)網(wǎng)站的部分?jǐn)?shù)據(jù),只顯示了四個(gè)分割點(diǎn).從分類結(jié)果來(lái)看,得到的網(wǎng)站類別主題較為鮮明,文中算法可以對(duì)網(wǎng)站進(jìn)行有效分類.

在這9個(gè)類別中的某些類別中,存在主題有所偏差的網(wǎng)站,如:在類別1中的第1個(gè)網(wǎng)站是有關(guān)房產(chǎn)的,而其他都是軍事類的.造成偏差的原因?yàn)?用于獲取網(wǎng)站特征值的主題詞的語(yǔ)義沒有進(jìn)行統(tǒng)一定義,同一主題詞可能被網(wǎng)站設(shè)計(jì)者用于不同的場(chǎng)合,賦予不同的語(yǔ)義,從而引起分類混亂.因此,對(duì)Web上主題詞的語(yǔ)義進(jìn)行統(tǒng)一定義,形成標(biāo)準(zhǔn),對(duì)語(yǔ)義Web的設(shè)計(jì)可以減少偏差,這也是課題未來(lái)的研究方向.

6 結(jié) 論

1) 收集并精簡(jiǎn)處理了互聯(lián)網(wǎng)特征詞即主題詞,根據(jù)特征詞的出現(xiàn)頻率對(duì)主題詞進(jìn)行排序,將這個(gè)主題詞序列作為網(wǎng)站特征值的結(jié)構(gòu)；根據(jù)特征詞在某網(wǎng)站是否出現(xiàn)計(jì)算出該網(wǎng)站的特征值,將網(wǎng)站根據(jù)網(wǎng)站特征值的大小進(jìn)行降序排序；計(jì)算相鄰網(wǎng)站之間的距離,并根據(jù)距離大小進(jìn)行排序；根據(jù)要求的分類數(shù)k,取前k個(gè)距離作為類分割點(diǎn)對(duì)網(wǎng)站進(jìn)行聚類.聚類測(cè)試結(jié)果分類準(zhǔn)確,主題鮮明,可以對(duì)網(wǎng)站進(jìn)行有效聚類.

2) 測(cè)試結(jié)果有個(gè)別網(wǎng)站的所屬類別存在偏差,其原因?yàn)?網(wǎng)站主題詞的語(yǔ)義沒有進(jìn)行統(tǒng)一,同一主題詞可能被賦予不同語(yǔ)義,進(jìn)而造成分類混亂.

3) 未來(lái)的研究將從兩個(gè)方面進(jìn)行:① 對(duì)Web上主題詞的語(yǔ)義進(jìn)行統(tǒng)一定義,形成標(biāo)準(zhǔn),設(shè)計(jì)出語(yǔ)義Web的語(yǔ)義結(jié)構(gòu),以減少主題詞歧義；② 將基于主題詞的網(wǎng)站特征值排序劃界聚類算法進(jìn)行抽象,形成基于距離序的劃界聚類算法,使其聚類的數(shù)據(jù)類型更廣泛.

參考文獻(xiàn):

[1] BEMERS-LEE T,HENDLER J,LASSILA O.The Semantic Web[J].Scientific American,2001,23(3):21.

[2] 羅鈞旻,王蕾.基于互表性的動(dòng)態(tài)本體體系結(jié)構(gòu)的研究[J].微電子學(xué)與計(jì)算機(jī),2013(2):124.

LUO Junmin,WANG Lei.Research on Architecture of Dynamic Ontology Based on Mutual-description Principle[J].Microelectronics and Computer,2013(2):124.(in Chinese)

[3] GUERRA-HERNANDEZ A,FALLAH- SEGHROU-CHNI A E I,SOLDANO H.Learning in BDI Multi-agent Systems[J].Lecture Notes in Computer Science,2004,3259:39.

[4] 羅鈞旻,謝磊.動(dòng)態(tài)本體描述語(yǔ)言的研究[J].西安工業(yè)大學(xué)學(xué)報(bào),2014,34(1):44.

LUO Junmin,XIE Lei.Research on Description Language of Dynamic Ontology[J].Journal of Xi’an Technological University,2014,34(1):44.

(in Chinese)

[5] 羅鈞旻,李俊偉.Agent自我意識(shí)的研究[J].微電子學(xué)與計(jì)算機(jī),2015(12):72.

LUO Junmin,LI Junwei.Research on Self-consciousness of Agents[J].Microelectronics and Computer,2015(12):72.(in Chinese)

[6] 羅鈞旻,趙丹,高武奇,等.基于自我意識(shí)的語(yǔ)義Web研究[J].微電子學(xué)與計(jì)算機(jī),2016,30(10):50.

LUO Junmin,ZHAO Dan,GAO Wuqi,et al.Research on Semantic Web Based on Self Consciousness.[J].Microelectronics and Computer ,2016,30(10):50.

(in Chinese)

[7] SRIRAM B,FUHRY D,DEMIR E,et al.Short Text Classification in Twitter to Improve Information Filtering[C]//Proceeding of the International ACM SIGIR Conference on Research and Development in Information Retrieval,2010,Geneva:DBLP,2010:841.

[8] 羅鈞旻,桑蓓蓓.基于動(dòng)態(tài)本體的語(yǔ)義B/S研究[J].微電子學(xué)與計(jì)算機(jī),2014,31(8):136.

LUN Junmin,SANG Beibei.Research on Semantic B/S Based on Dynamic Ontology[J].Microelectronics and Computer ,2014,31(8):136.(in Chinese)

[9] ZHU C H,WEN F,SUN J.A Rank-order Distance Based Clustering Algorithm for Face Tagging[C]//Computer Vision and Pattern Recognition 2011,Springs:IEEE,2011:481.