改進(jìn)的LSSVM算法在垃圾標(biāo)簽檢測(cè)上的應(yīng)用

楊曉雷,楊清琳,杜英俊（廣西財(cái)經(jīng)學(xué)院現(xiàn)代教育技術(shù)部,南寧 530003）

改進(jìn)的LSSVM算法在垃圾標(biāo)簽檢測(cè)上的應(yīng)用

楊曉雷,楊清琳,杜英俊
（廣西財(cái)經(jīng)學(xué)院現(xiàn)代教育技術(shù)部,南寧 530003）

為了解決 Folksonomy 存在垃圾標(biāo)簽的問(wèn)題，提出垃圾標(biāo)簽檢測(cè)模型。利用向量空間模型表征用戶特征，再用支持向量機(jī)將Folksonomy 用戶二分類。通過(guò)檢測(cè)出隱藏在正常用戶群體中的垃圾投放人，以此減少垃圾標(biāo)簽數(shù)量。垃圾標(biāo)簽數(shù)據(jù)集具有數(shù)量大，緯度高的特點(diǎn)。面對(duì)傳統(tǒng)svm算法處理高維大規(guī)模數(shù)據(jù)集上過(guò)于復(fù)雜，存在速度和精度的瓶頸的問(wèn)題，筆者曾經(jīng)提出用lssvm算法進(jìn)行垃圾標(biāo)簽檢測(cè)處理，取得一定的效果。但是，lssvm算法本身也存在稀疏性以及處理重要數(shù)據(jù)點(diǎn)不敏感的問(wèn)題，所以針對(duì)這點(diǎn)，提出了用剪切法進(jìn)行解決，通過(guò)實(shí)驗(yàn)表明，改進(jìn)的LSSVM提高了建模的精度，而稀疏化的處理雖然對(duì)精度有一定影響，但大大減少了訓(xùn)練數(shù)據(jù)量，從而有效減輕了計(jì)算負(fù)擔(dān)，使快速性得到了保障。

垃圾標(biāo)簽；Folksonomy lssvm；剪切法

1 引言

隨著 Web 2.0 技術(shù)架構(gòu)的推廣，社會(huì)網(wǎng)絡(luò)( SN) 的應(yīng)用逐漸擴(kuò)大。社會(huì)化標(biāo)簽系統(tǒng)廣受大眾的歡迎。國(guó)內(nèi)外知名的社會(huì)化標(biāo)簽系統(tǒng)有Delicious、Flickr、Last． fm、豆瓣網(wǎng)等。由于采用 Folksonomy 的框架，社會(huì)化標(biāo)簽系統(tǒng)特別強(qiáng)調(diào)用戶參與其創(chuàng)建和維護(hù)過(guò)程。在 Folksonomy中，用戶行為十分自由，這為垃圾信息的投放提供了新的途徑。這些投放在社會(huì)化標(biāo)簽系統(tǒng)中的垃圾信息，稱為社會(huì)垃圾( social spam) 或垃圾標(biāo)簽。目前檢測(cè)垃圾標(biāo)簽的主流方法是從用戶中檢測(cè)出垃圾投放人，通過(guò)控制垃圾投放人的行為，達(dá)到減少垃圾標(biāo)簽的效果[1]。筆者曾經(jīng)采用lssvm算法進(jìn)行垃圾標(biāo)簽檢測(cè)的應(yīng)用，雖然比起傳統(tǒng)的svm方法有一定的改進(jìn)，但是lssvm算法本身也存在一定問(wèn)題。

2 算法的改進(jìn)

在LSSVM中，由于Lagrange乘子均不為零，因此所有的數(shù)據(jù)向量都是支持向量。那如何區(qū)分這些支持向量的重要程度呢?本章引入了“支持向量度”的概念，為每個(gè)訓(xùn)練數(shù)據(jù)定義了一個(gè)支持向量度。訓(xùn)練數(shù)據(jù)(xi,yi)對(duì)應(yīng)的支持向量度為0＜si＜1，代表了該數(shù)據(jù)隸屬于支持向量的程度。0＜si＜1值越大，則對(duì)應(yīng)的訓(xùn)練點(diǎn)隸屬于支持向量的程度越高。

給定訓(xùn)練數(shù)據(jù)集{xi,yi,si}Ni=1。在標(biāo)準(zhǔn)LSSVM優(yōu)化問(wèn)題(2.2)的第二項(xiàng)中引入支持向量度構(gòu)成了改進(jìn)的LSSVM的優(yōu)化問(wèn)題

顯然，當(dāng)所有的支持向量度 定義為1時(shí)，改進(jìn)的LSSVM就是標(biāo)準(zhǔn)LSSVM.從這個(gè)意義上說(shuō)，標(biāo)準(zhǔn)LSSVM可以看成是改進(jìn)的LSSVM的一種特殊情況。

構(gòu)建Lagrange函數(shù)

根據(jù)最優(yōu)性條件，得到

整理上面的方程組，消去變量。得到矩陣形式為

其中，向量S=diag{S1,S2…Sn}是一個(gè)由所有支持向量度{Si}Ni=1絲構(gòu)成的N×N對(duì)角陣。其它參數(shù)的意義同前。

假定矩陣

可逆，則參數(shù)。和b的解析解可通過(guò)下式得到

最終得到的改進(jìn)的LSSVM模型表達(dá)式為

改進(jìn)的LSSVM建模算法的實(shí)施。要實(shí)施改進(jìn)的LSSVM，還存在一個(gè)問(wèn)題:既然支持向量度是由Lagrange乘子所決定的，而Lagrange乘子是由LSSVM學(xué)習(xí)后產(chǎn)生的，那么在算法沒(méi)有實(shí)施之前，如何得到Lagrange乘子來(lái)計(jì)算支持向量度呢?我們解決這個(gè)問(wèn)題的辦法是，首先假定所有的支持向量度{s*}均為1，訓(xùn)練得到Lagrange乘子，然后根據(jù)Lagrange乘子的值來(lái)確定支持向量度，然后再進(jìn)行改進(jìn)的LSSVM的訓(xùn)練。

針對(duì)自回歸對(duì)象模型，改進(jìn)的LSSVM回歸的一般流程可歸納如下:

（1）由得到的數(shù)據(jù)集{xi,yi}Ni=1進(jìn)行訓(xùn)練，得到Lagrange乘子{αi}Ni=1；

（2）根據(jù)公式（8），選擇合適的數(shù)0≤δ≤1，利用上次訓(xùn)練得到的Lagrange乘子確定支持向量度；

（3）構(gòu)建新的訓(xùn)練數(shù)據(jù)集{xi,yi,si}Ni=1進(jìn)行改進(jìn)的LSSVM訓(xùn)練，得到模型參數(shù){αi}Ni=11和b；（4）根據(jù)|αi|Ni=1升序排列訓(xùn)練集{xi,yi,si}N

i=1中的數(shù)據(jù)，剪除一小部分（如5%）具有最小αi值的數(shù)據(jù)點(diǎn)；

（5）由剩余的Lagrange乘子重新計(jì)算8、，由剩余的數(shù)據(jù)重新構(gòu)建訓(xùn)練集{xi,yi,si}Ni=1再次進(jìn)行改進(jìn)的LSSVM訓(xùn)練，得到新的Lagrange乘子。如果擬合性能下降，則結(jié)束訓(xùn)練，得到對(duì)象模型;否則，轉(zhuǎn)至（3）。

3 實(shí)驗(yàn)與分析

用改進(jìn)的LSSVM方法辨識(shí)上述模型，采用徑向基函數(shù)作為核函數(shù)。

特此說(shuō)明的是，因?yàn)楦倪M(jìn)的LSSVM采用迭代方式訓(xùn)練得到Lagrange乘子，然后根據(jù)Lagrange乘子的值來(lái)確定支持向量度，因此訓(xùn)練時(shí)間方面會(huì)變長(zhǎng)，采用訓(xùn)練時(shí)間衡量算法性能是沒(méi)有意義的，因此我們只用訓(xùn)練精度做為衡量標(biāo)準(zhǔn)。

實(shí)驗(yàn)的程序使用MATLAB2009a實(shí)現(xiàn)，實(shí)驗(yàn)硬件環(huán)境：CPU為P4，3.0GHz，1GB內(nèi)存。所有實(shí)驗(yàn)運(yùn)行15次取平均值。本文采用的數(shù)據(jù)集來(lái)自二元分類測(cè)試數(shù)據(jù)集synth、bc本文采取的源數(shù)據(jù)包含2個(gè)數(shù)據(jù)文件(tas，bookmark)，其中tas文件包含用戶、tas_id、標(biāo)簽和對(duì)應(yīng)bookmark_id的關(guān)系記錄，bookmark文件包含資源、資源描述、bookmark_id和對(duì)應(yīng)tas_id的關(guān)系記錄。為兩個(gè)數(shù)據(jù)文件接由tas_id和bookmark_id來(lái)接。

第一組：

表1 bc數(shù)據(jù)集樣本及維度

第二組：

表2 bc數(shù)據(jù)集樣本及維度

實(shí)驗(yàn)方案設(shè)計(jì)分為兩組，第一組是訓(xùn)練集樣本維度為10的時(shí)候，分別采用LSSVM和改進(jìn)的LSSVM算法進(jìn)行分類，而第二組是當(dāng)訓(xùn)練集維度為2的時(shí)候分別采用兩種算法進(jìn)行分類。

首先采用標(biāo)準(zhǔn)LSSVM方法分別對(duì)bc數(shù)據(jù)集和synth 數(shù)據(jù)集取300，150，60，30組采樣數(shù)據(jù)進(jìn)行訓(xùn)練，然后用200組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，其中參數(shù)由libSVM工具箱自動(dòng)尋優(yōu)函數(shù)給出，改進(jìn)的LSSVM中，最小的支持向量度使用上一步標(biāo)準(zhǔn)LSSVM所得出的參數(shù)，每迭代一次剪切5%的數(shù)據(jù)，用200組測(cè)試數(shù)據(jù)得到的測(cè)試結(jié)果。測(cè)試得到的結(jié)果如下所示：

第一組：

表3 bc 數(shù)據(jù)集LSSVM測(cè)試結(jié)果

表4 bc 數(shù)據(jù)集 改進(jìn)的LSSVM測(cè)試結(jié)果

第二組：

表5 synth 數(shù)據(jù)集LSSVM測(cè)試結(jié)果

表6 改進(jìn)的LSSVM測(cè)試結(jié)果

由表3和4可以看出可以看出，當(dāng)我們采用較小數(shù)據(jù)集做測(cè)試時(shí)候，比如50，在改進(jìn)的LSSVM的精度為61.7，而標(biāo)準(zhǔn) LSSVM為60.5，精度只有微量的提升，而我們?cè)龃笥?xùn)練數(shù)據(jù)集，,采用數(shù)據(jù)集個(gè)數(shù)為100和150的時(shí)候，精度開(kāi)始有明顯的提高，提高了接近10的百分點(diǎn)。當(dāng)我們數(shù)據(jù)量增到到300的時(shí)候，提升更是明顯，提升了18個(gè)百分點(diǎn)。因此，通過(guò)實(shí)驗(yàn)我們可以發(fā)現(xiàn)，采用剪切算法在數(shù)據(jù)集數(shù)量增大的時(shí)候，對(duì)精度的提高就越明顯。同樣第二組實(shí)驗(yàn)中改進(jìn)的lssvm算法在低維數(shù)據(jù)集中，通過(guò)表5 和6觀察也能得出相同的結(jié)論。因此，通過(guò)支持向量度的引入采用剪切數(shù)據(jù)的改進(jìn)的LSSVM方法，精度要好于LSSVM。因此，通過(guò)剪切數(shù)據(jù)的方法來(lái)實(shí)現(xiàn)改進(jìn)的LSSVM算法是可行的。

[1] KIM C J，HWANG K B．Naive Bayes classier.learning with featureselection for spam detection in social bookmarking[C]//Lecture Notes in Computer Science． Berlin: Springer-Verlag，2008．

[2]覃希,夏寧霞,蘇一丹.基于支持向量機(jī)的垃圾標(biāo)簽檢測(cè)模型.[J].計(jì)算機(jī)應(yīng)用研究,2010,27(10):40-46.

[3]GRAMME P，CHEVALIER J F． Rank for spam dsetection[C]/ /Lecture Notes in Computer Science． Berlin: Springer-Verlag，2008．

[4]Van Gestel, T. Suykens, J.A.K., Baesens, B., Viaene, S., Vanthienen, J., Dedene, G., De Moor, B., Vandewalle, J., Benchmarking least squares support vector machine classifiers", Mach. Learning, vol 54, pp.5-32, 2003.

[5]ADKOUR A，HEFNI T，HEFNY A，et al． Using semantic featuresto detect spamming in social bookmarking systems ［C］// LectureNotes in Computer Science． Berlin: Springer-Verlag，2008．

[6]HOTHO A，JASCHKE R，SCHMITZ C，et al．Emergent semantics in BibSonomy［M］． Liskowsky: GI Jahrestagung,2006:305-312．

[7]SALTON G，McGILL M J． Introduction to modern information retrieval［M］．New York: McGraw-Hill，1983: 1-12．

[8]http://www.csie.ntu.edu.tw/-cjlin/libsvmtools/datasets/.

[9] BROADLY． Social spam definition［EB/OL］．(2008-7-21) ．http://www． bryanchen． com /2008 /07 /21 / social-spam /.

[10]Kuh, A., De Wilde, P. "Comments on pruning error minimization in least squares support vector machines". IEEE Trans. Neural Networks, vol 18 (2). 2007.

[11]Lazar, A. Income prediction via support vector machine[C]. New York:Machine Learning and Applications, IEEE 2004' Proceedings,2004.