尚靖博, 左萬利

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

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

1 算法描述

本文對清晰有理數(shù)均值方法進(jìn)行如下改進(jìn)： 對于論域U=(x1,x2,…,xn)(n∈), 其中x1,x2,…,xn是一組有若干重復(fù)項的自然數(shù), 將其刪除重復(fù)項后, 論域U變?yōu)檎撚騐=(x1,x2,…,xm}(m≤n,m∈), 其中x1,x2,…,xm稱為匹配項. 計算x1,x2,…,xm分別在論域U中的個數(shù), 記作c1,c2,…,cm, 則x1,x2,…,xm在論域U中的概率記作p1,p2,…,pm. 計算有理數(shù)的均值計算結(jié)果僅取其整數(shù)位, 與匹配項匹配后, 標(biāo)記與匹配項相關(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ù)項得到匹配項；

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

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

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

forbin range (m) {p(b)=c[b]/sumc;} //計算每個匹配項的概率；

fortin range (m) {

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

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

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

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

A.append( );

else:

B.append( ); }}

2 實驗結(jié)果與分析

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

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

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

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

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

[1] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究 [J]. 軟件學(xué)報, 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ī)工程, 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)化聚類的長周期峰谷時段劃分模型研究 [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ī)與應(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é)報(自然科學(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.