楊曉雷,楊清琳,杜英?。◤V西財經(jīng)學(xué)院現(xiàn)代教育技術(shù)部,南寧 530003）

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

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

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

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

1 引言

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

2 算法的改進

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

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

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

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

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

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

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

假定矩陣

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

最終得到的改進的LSSVM模型表達式為

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

針對自回歸對象模型，改進的LSSVM回歸的一般流程可歸納如下:

（1）由得到的數(shù)據(jù)集{xi,yi}Ni=1進行訓(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進行改進的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ù)點；

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

3 實驗與分析

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

特此說明的是，因為改進的LSSVM采用迭代方式訓(xùn)練得到Lagrange乘子，然后根據(jù)Lagrange乘子的值來確定支持向量度，因此訓(xùn)練時間方面會變長，采用訓(xùn)練時間衡量算法性能是沒有意義的，因此我們只用訓(xùn)練精度做為衡量標(biāo)準(zhǔn)。

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

第一組：

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

第二組：

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

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

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

第一組：

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

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

第二組：

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

表6 改進的LSSVM測試結(jié)果

由表3和4可以看出可以看出，當(dāng)我們采用較小數(shù)據(jù)集做測試時候，比如50，在改進的LSSVM的精度為61.7，而標(biāo)準(zhǔn) LSSVM為60.5，精度只有微量的提升，而我們增大訓(xùn)練數(shù)據(jù)集，,采用數(shù)據(jù)集個數(shù)為100和150的時候，精度開始有明顯的提高，提高了接近10的百分點。當(dāng)我們數(shù)據(jù)量增到到300的時候，提升更是明顯，提升了18個百分點。因此，通過實驗我們可以發(fā)現(xiàn)，采用剪切算法在數(shù)據(jù)集數(shù)量增大的時候，對精度的提高就越明顯。同樣第二組實驗中改進的lssvm算法在低維數(shù)據(jù)集中，通過表5 和6觀察也能得出相同的結(jié)論。因此，通過支持向量度的引入采用剪切數(shù)據(jù)的改進的LSSVM方法，精度要好于LSSVM。因此，通過剪切數(shù)據(jù)的方法來實現(xià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]覃希,夏寧霞,蘇一丹.基于支持向量機的垃圾標(biāo)簽檢測模型.[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.