基于清晰有理數(shù)均值的新匹配聚類(lèi)算法

尚靖博, 左萬(wàn)利

(1. 吉林大學(xué) 軟件學(xué)院, 長(zhǎng)春 130012； 2. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130012)

聚類(lèi)的本質(zhì)是將本屬于同類(lèi)而因某種原因分離的事物, 按照某種邏輯和方法重新聚合的過(guò)程. 聚類(lèi)主要分為層次聚類(lèi)、 劃分式聚類(lèi)、 網(wǎng)格聚類(lèi)和密度聚類(lèi). 層次聚類(lèi)以倒樹(shù)形結(jié)構(gòu)排列, 通過(guò)從根節(jié)點(diǎn)層層向下不斷聚合和分裂, 最終完成聚類(lèi). 由于倒樹(shù)形結(jié)構(gòu)的特性, 所以更適用于小型數(shù)據(jù)集[1]. 文獻(xiàn)[2]的方法為典型層次聚類(lèi)方法, 它先基于HTML特征和層次聚類(lèi)實(shí)現(xiàn)Web接口查詢(xún), 再利用Web中的各種關(guān)系和相關(guān)特性建立倒樹(shù)形結(jié)構(gòu), 最后通過(guò)層次聚類(lèi)的方式完成聚類(lèi), 該方法在實(shí)驗(yàn)室的準(zhǔn)確率可達(dá)90%以上. 劃分式聚類(lèi)通過(guò)預(yù)先設(shè)置好聚類(lèi)的中心或數(shù)目, 經(jīng)過(guò)一系列的計(jì)算最終收斂完成聚類(lèi)過(guò)程. 劃分式聚類(lèi)在使用頻率上有K均值聚類(lèi)和模糊聚類(lèi)等類(lèi)型[1]. 文獻(xiàn)[3]的方法為典型的劃分式聚類(lèi), 它將樣本數(shù)據(jù)集高維化處理, 并結(jié)合K均值聚類(lèi)的方法劃分出各時(shí)段的負(fù)荷差異, 實(shí)驗(yàn)結(jié)果表明, 該方法可以在一個(gè)長(zhǎng)周期內(nèi)穩(wěn)定運(yùn)行. 網(wǎng)格聚類(lèi)和密度聚類(lèi)都是基于觀察樣本空間中各組成部分的疏密程度完成聚類(lèi)[1], 因此更適用于圖像與視頻的聚類(lèi). 該聚類(lèi)方法最典型的是文獻(xiàn)[4]中方法, 它利用圖像由像素點(diǎn)組成, 且不同圖像各部分的疏密程度必不同的原理聚類(lèi), 實(shí)驗(yàn)結(jié)果表明, 該方法對(duì)噪聲數(shù)據(jù)過(guò)濾效果較好, 執(zhí)行效率較高, 能更好地識(shí)別出不同類(lèi)別的簇. 此外, 文獻(xiàn)[5]利用匹配程度的量度決定隸屬, 利用主成分分析決定縱向壓縮, 該方法壓縮率也較高. 本文通過(guò)改進(jìn)文獻(xiàn)[6]的清晰有理數(shù)均值方法, 提出一種針對(duì)人工標(biāo)注型數(shù)據(jù)的聚類(lèi)算法, 稱(chēng)為新匹配聚類(lèi)算法.

1 算法描述

本文對(duì)清晰有理數(shù)均值方法進(jìn)行如下改進(jìn)： 對(duì)于論域U=(x1,x2,…,xn)(n∈), 其中x1,x2,…,xn是一組有若干重復(fù)項(xiàng)的自然數(shù), 將其刪除重復(fù)項(xiàng)后, 論域U變?yōu)檎撚騐=(x1,x2,…,xm}(m≤n,m∈), 其中x1,x2,…,xm稱(chēng)為匹配項(xiàng). 計(jì)算x1,x2,…,xm分別在論域U中的個(gè)數(shù), 記作c1,c2,…,cm, 則x1,x2,…,xm在論域U中的概率記作p1,p2,…,pm. 計(jì)算有理數(shù)的均值計(jì)算結(jié)果僅取其整數(shù)位, 與匹配項(xiàng)匹配后, 標(biāo)記與匹配項(xiàng)相關(guān)的信息, 標(biāo)記結(jié)果即為聚類(lèi)結(jié)果. 算法過(guò)程偽代碼描述如下：

U={以矩陣形式表示的數(shù)據(jù)集}, //導(dǎo)入數(shù)據(jù)集, 其行數(shù)為i, 列數(shù)為j；

forkin range (i) { //遍歷矩陣的每一行；

V=U[k].drop_duplicates( ); //刪除重復(fù)項(xiàng)得到匹配項(xiàng)；

m=V.count( ); //計(jì)算匹配值的總數(shù)目；

forsin range(m) {c[s]=U[k].count(′V[s]′)}; //計(jì)算每個(gè)匹配項(xiàng)的數(shù)目；

forqin range (m) {sumc=sumc([q]);} //計(jì)算所有匹配項(xiàng)數(shù)目總和；

forbin range (m) {p(b)=c[b]/sumc;} //計(jì)算每個(gè)匹配項(xiàng)的概率；

fortin range (m) {

E1+=V[t]*p[t]; //計(jì)算清晰有理數(shù)的均值分子；

E2+=p[t]; //計(jì)算清晰有理數(shù)的均值分母；

E=E1/E2; } //計(jì)算清晰有理數(shù)的均值；

if (E==V[ ]) { //計(jì)算結(jié)果依次與匹配項(xiàng)比較, 匹配到哪項(xiàng)就將目標(biāo)數(shù)據(jù)名加入對(duì)應(yīng)的集合, 完成聚類(lèi).

A.append( );

else:

B.append( ); }}

2 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文新匹配聚類(lèi)算法的效果, 將其應(yīng)用于非欺詐網(wǎng)頁(yè)檢測(cè)實(shí)驗(yàn). 互聯(lián)網(wǎng)的飛速發(fā)展推動(dòng)了搜索引擎的提升, 但由于利益的驅(qū)使, 大批量的欺詐網(wǎng)頁(yè)混雜于互聯(lián)網(wǎng)中. 欺詐者采取非正常方法, 人工干預(yù)搜索引擎的排序策略, 以獲取與其地位不相符的高排名, 擾亂用戶(hù)對(duì)信息的獲取, 甚至侵害用戶(hù)利益. 所以要將非欺詐網(wǎng)頁(yè)通過(guò)聚類(lèi)的方式提取出來(lái). 本文采用Webspam-uk2007數(shù)據(jù)集(http://chato.cl/webspam/datasets/), 其為一組由人工合作完成, 對(duì)UK域上的114 529個(gè)主機(jī)的105 896 555個(gè)頁(yè)面人工標(biāo)記(包括S： 欺詐網(wǎng)頁(yè);N： 非欺詐網(wǎng)頁(yè);B： 無(wú)法確定;U： 未知)所形成的數(shù)據(jù)集, 在實(shí)驗(yàn)中選取其中最終可確定是欺詐網(wǎng)頁(yè)或非欺詐網(wǎng)頁(yè)的6 053個(gè)頁(yè)面作為數(shù)據(jù)集.

首先產(chǎn)生原始矩陣U, 對(duì)數(shù)據(jù)集中的兩種標(biāo)注情況(“欺詐網(wǎng)頁(yè)”、 “非欺詐網(wǎng)頁(yè)”)分別使用1和2替換, 缺位的用0補(bǔ)全, 保證數(shù)據(jù)的每一行列數(shù)相同. 然后取每一行, 刪除重復(fù)元素后確定最終的匹配項(xiàng)x1,x2,…,xm, 計(jì)算每個(gè)匹配項(xiàng)的數(shù)目, 記作c1,c2,…,cm, 計(jì)算每個(gè)匹配項(xiàng)的概率, 記作p1,p2,…,pm, 利用匹配項(xiàng)和概率計(jì)算清晰有理數(shù)均值, 記作E. 若E=1, 則標(biāo)記為欺詐網(wǎng)頁(yè)； 若E=2, 則標(biāo)記為非欺詐網(wǎng)頁(yè), 其他情況則標(biāo)記為未知.

為評(píng)估其性能, 本文采用準(zhǔn)確率、 召回率和F值作為評(píng)價(jià)標(biāo)準(zhǔn), 公式如下：

其中：TP表示非欺詐網(wǎng)頁(yè)樣本集中被標(biāo)記正確的數(shù)量；TN表示非欺詐網(wǎng)頁(yè)樣本集中被標(biāo)記錯(cuò)誤的數(shù)量；FP表示欺詐網(wǎng)頁(yè)樣本集中被標(biāo)記錯(cuò)誤的數(shù)量；FN表示欺詐網(wǎng)頁(yè)樣本集中被標(biāo)記正確的數(shù)量.

新匹配聚類(lèi)算法在非欺詐網(wǎng)頁(yè)檢測(cè)問(wèn)題的實(shí)驗(yàn)結(jié)果： 非欺詐網(wǎng)頁(yè)樣本集中被標(biāo)記正確的數(shù)量為5 596, 非欺詐網(wǎng)頁(yè)樣本集中被標(biāo)記錯(cuò)誤的數(shù)量為113, 欺詐網(wǎng)頁(yè)樣本集中被標(biāo)記錯(cuò)誤的數(shù)量為0, 欺詐網(wǎng)頁(yè)樣本集中被標(biāo)記正確的數(shù)量為334, 準(zhǔn)確率為100%, 召回率為98.02%. 由準(zhǔn)確率為100%和召回率為98.02%, 可計(jì)算出F值為0.99, 實(shí)驗(yàn)結(jié)果較好, 因此驗(yàn)證了本文提出的新匹配聚類(lèi)算法在反欺詐網(wǎng)頁(yè)領(lǐng)域的有效性及在人工標(biāo)注型數(shù)據(jù)聚類(lèi)的合理性. 使用傳統(tǒng)的K最近鄰算法[7]與本文算法在同一名稱(chēng)但不同類(lèi)型的數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn), 實(shí)驗(yàn)結(jié)果如圖1所示. 由圖1可見(jiàn), 本文算法在反欺詐網(wǎng)頁(yè)檢測(cè)問(wèn)題上具有更好的效果.

[1] 孫吉貴, 劉杰, 趙連宇. 聚類(lèi)算法研究 [J]. 軟件學(xué)報(bào), 2008, 19(1): 48-61. (SUN Jigui, LIU Jie, ZHAO Lianyu. Clustering Algorithms Research [J]. Journal of Software, 2008, 19(1): 48-61.)

[2] 魏佳欣, 葉飛躍. 基于HTML特征與層次聚類(lèi)的Web查詢(xún)接口發(fā)現(xiàn) [J]. 計(jì)算機(jī)工程, 2016, 42(2): 56-61. (WEI Jiaxin, YE Feiyue. Discovery of Web Query Interface Based on HTML Features and Hierarchical Clustering [J]. Computer Engineering, 2016, 42(2): 56-61.)

[3] 李娜, 王磊, 張文月, 等. 基于高維數(shù)據(jù)優(yōu)化聚類(lèi)的長(zhǎng)周期峰谷時(shí)段劃分模型研究 [J]. 現(xiàn)代電力, 2016, 33(4): 67-71. (LI Na, WANG Lei, ZHANG Wenyue, et al. Reasearch on the Partition Model of Long Period Peak and Valley Time Based on High Dimensional Data Clustering [J]. Modern Electric Power, 2016, 33(4): 67-71.)

[4] 田宇, 羅辛. 一種基于圖像去噪的多密度網(wǎng)格聚類(lèi)算法 [J]. 智能計(jì)算機(jī)與應(yīng)用, 2016, 6(1): 44-47. (TIAN Yu, LUO Xin. A Multi Mesh Density Clustering Algorithm Based on Image Denoising [J]. Intelligent Computer and Applications, 2016, 6(1): 44-47.)

[5] 馮靜, 金遠(yuǎn)平, 馮欣. 基于主成分分析及匹配聚類(lèi)分析的數(shù)據(jù)表語(yǔ)義壓縮方法 [J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2006, 36(6): 927-930. (FENG Jing, JIN Yuanping, FENG Xin. Semantic Compression for Data Tables Based on Principal Component and Matching Clustering Analysis [J]. Journal of Southeast University (Natural Science Edition), 2006, 36(6): 927-930.)

[6] 蘇發(fā)慧. 清晰理論基礎(chǔ) [M]. 合肥: 合肥工業(yè)大學(xué)出版社, 2012: 123-126. (SU Fahui. Clear Theoretical Basis [M]. Hefei: Hefei University of Technology Press, 2012: 123-126.)

[7] Ali H, Behrouz M B. Multi-view Learning for Web Spam Detection [J]. Journal of Emerging Technologies in Web Intelligence, 2013, 5(4): 395-400.