尚靖博, 左萬利

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

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

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稱為匹配項(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é)果即為聚類結(jié)果. 算法過程偽代碼描述如下：

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)的集合, 完成聚類.

A.append( );

else:

B.append( ); }}

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

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

首先產(chǎn)生原始矩陣U, 對(duì)數(shù)據(jù)集中的兩種標(biāo)注情況(“欺詐網(wǎng)頁”、 “非欺詐網(wǎng)頁”)分別使用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)頁； 若E=2, 則標(biāo)記為非欺詐網(wǎng)頁, 其他情況則標(biāo)記為未知.

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

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

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

[1] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究 [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特征與層次聚類的Web查詢接口發(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)化聚類的長周期峰谷時(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)格聚類算法 [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)平, 馮欣. 基于主成分分析及匹配聚類分析的數(shù)據(jù)表語義壓縮方法 [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.