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

(西安工業(yè)大學 計算機科學與工程學院,西安 710021)

clustering

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

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

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

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

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

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

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

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

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

3 主題詞收集

刪除無意義詞及出現(xià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è)計

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

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

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

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

其部分數(shù)據(jù)見表3.

表2 特征詞表

表3 特征詞表部分數(shù)據(jù)

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

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

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

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

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

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

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

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

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

⑧ 查看該主頁的主題詞是否已匹配完,如果沒有,取下一主題詞,轉(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個long型值)從大到小對網(wǎng)站數(shù)組WS排序,得到一個有序的網(wǎng)站數(shù)組SW.

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

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

5.3 網(wǎng)站距離號

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

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

5.4 聚類算法

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

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

定義一個整型變量i作為DS的下標,初始化為0；

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

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

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

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

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

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

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

實驗二:選取90個網(wǎng)站作為聚類的網(wǎng)站對象,文中算法將其分為9類,部分數(shù)據(jù)見表5.

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

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

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

6 結(jié) 論

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

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

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

參考文獻:

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

[2] 羅鈞旻,王蕾.基于互表性的動態(tài)本體體系結(jié)構(gòu)的研究[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] 羅鈞旻,謝磊.動態(tài)本體描述語言的研究[J].西安工業(yè)大學學報,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自我意識的研究[J].微電子學與計算機,2015(12):72.

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

[6] 羅鈞旻,趙丹,高武奇,等.基于自我意識的語義Web研究[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] 羅鈞旻,桑蓓蓓.基于動態(tài)本體的語義B/S研究[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.