摘要：針對(duì)垃圾標(biāo)簽檢測(cè)數(shù)據(jù)集特征維數(shù)高，規(guī)模大的問(wèn)題，提出利用序列最小最優(yōu)化算法大幅度約減龐大的垃圾標(biāo)簽特征數(shù)據(jù)集，同時(shí)保持原有分類精度，降低訓(xùn)練時(shí)間。為Folksonomy的垃圾標(biāo)簽檢測(cè)研究拓寬道路。
　　關(guān)鍵詞：垃圾標(biāo)簽；序列最小最優(yōu)化算法；約減
　　
　　0． 引言
　　隨著Web2.0技術(shù)架構(gòu)的推廣，社會(huì)化標(biāo)簽系統(tǒng)越來(lái)越受到人們的歡迎，但它容易受到社會(huì)垃圾（SocialSpam）或垃圾標(biāo)簽的干擾。目前檢測(cè)垃圾標(biāo)簽的主流途徑是從用戶中檢測(cè)出垃圾投放人，通過(guò)控制垃圾投放人的行為，達(dá)到減少垃圾標(biāo)簽的效果。現(xiàn)行檢測(cè)方法有樸素貝葉斯法[2]、神經(jīng)網(wǎng)絡(luò)[3]、支持向量機(jī)[3]等。然而，社會(huì)化標(biāo)簽系統(tǒng)的數(shù)據(jù)量極為龐大。現(xiàn)有方法幾乎都是直接采用分類算法進(jìn)行分類檢測(cè)，雖然都有不同程度的效果，但檢測(cè)速度慢。少數(shù)方法通過(guò)采用設(shè)計(jì)統(tǒng)計(jì)量描述特征、隨機(jī)抽取樣本點(diǎn)等方法壓縮數(shù)據(jù)集。這些方法雖然能把數(shù)據(jù)集控制在一定小規(guī)模內(nèi)，但具有一定局限性，容易造成特征丟失，影響檢測(cè)精度。本篇將采用序列最小最優(yōu)化算法約減大規(guī)模的垃圾標(biāo)簽數(shù)據(jù)集，實(shí)現(xiàn)對(duì)檢測(cè)模型的優(yōu)化，在保證檢測(cè)精度的同時(shí)，大幅度提高分類檢測(cè)的速度。
　　
　　1. 垃圾標(biāo)簽檢測(cè)模型
　　1.1 Folksonomy用戶的向量空間模型
　　在Folksonomy中，整個(gè)系統(tǒng)體現(xiàn)了用戶、標(biāo)簽和資源三者的關(guān)系。其用戶的形式化定義為[4]：
　　定義（Folksonomy用戶定義）對(duì)于給定的用戶uU，Pu是F對(duì)u的約束，即Pu:=(Tu，Ru，Iu，﹤u)，其中Iu:={(t，r)T×R|(u，t，r)Y}，Tu:=1(Iu)，Ru:=2(Iu)，﹤u:={(t1，t2)T×T|(u，t1，t2)﹤}(cāng)。這里表示投影，i表示第i元的投影。
　　根據(jù)以上定義可知，用戶可以由其標(biāo)識(shí)過(guò)的標(biāo)簽和對(duì)應(yīng)的資源一起聯(lián)合描述。本篇的垃圾標(biāo)簽檢測(cè)模型將利用這一定義，采用字符串連接的方式將標(biāo)簽、資源結(jié)合，即用戶使用過(guò)的標(biāo)簽詞匯和對(duì)應(yīng)資源連接成字符串文本。經(jīng)此轉(zhuǎn)化可得到新的用戶文本形式。在此基礎(chǔ)上借鑒文本特征的處理方法，對(duì)其進(jìn)行詞條切分，構(gòu)建詞典，然后利用文本的向量空間模型[5]表征，最后得到如下新的用戶特征模型：
　　Uk=(Wk1，Wk2，…，Wkg，Wkg+1，Wkg+2，…，Wkh)，
　　其中，用戶特征向量維數(shù)由構(gòu)建的詞典大小決定。Wki為第k個(gè)用戶文本中使用了詞典第i個(gè)分詞的權(quán)重。利用TF/IDF函數(shù)計(jì)算權(quán)重。函數(shù)中的N表示用戶模型總數(shù)，n(i)表示訓(xùn)練集中使用標(biāo)簽分詞i的用戶數(shù)。
　　1.2 SVM二次規(guī)劃模型
　　支持向量機(jī)(SupportVectorMachines,SVM)理論是Vapnik[6][7]等人提出用來(lái)具體實(shí)現(xiàn)統(tǒng)計(jì)學(xué)習(xí)理論核心思想的一種通用的學(xué)習(xí)方法。支持向量機(jī)的訓(xùn)練算法主要在于求解一個(gè)凸二次規(guī)劃問(wèn)題，考慮其原始問(wèn)題的對(duì)偶問(wèn)題，引入Lagrange乘子，其公式如下：
　　(1)
　　可得該問(wèn)題的最優(yōu)解為其決策函數(shù)為
　　(2)
　　其中。事實(shí)上，最優(yōu)解的每一個(gè)分量都對(duì)應(yīng)一個(gè)訓(xùn)練點(diǎn)。因此，構(gòu)造的分化超平面僅僅依賴于那些對(duì)應(yīng)于不為零的訓(xùn)練點(diǎn)，這些訓(xùn)練點(diǎn)就稱為支持向量，而其他對(duì)應(yīng)于為零的訓(xùn)練點(diǎn)則稱為非支持向量。
　　
　　2. SMO算法優(yōu)化垃圾標(biāo)簽檢測(cè)模型
　　2.1 SMO算法
　　支持向量機(jī)的優(yōu)化算法是將大規(guī)模的原始問(wèn)題分解成一系列小規(guī)模的子問(wèn)題，按照某種迭代策略，不斷求解這些子問(wèn)題，逐漸提高原問(wèn)題的近似解的精確度。序列最小最優(yōu)化算法（SMO）[9]是支持向量機(jī)的一種快速優(yōu)化算法。序列最小最優(yōu)化算法的主要步驟如下：
　　算法一
　　(1) 選取精度要求，選取，令k=0；
　　(2) 根據(jù)當(dāng)前可行的近似解選取集合{1,2,…,l}的一個(gè)由兩個(gè)元素組成的子集{i,j}作為工作集B；
　　(3) 求解與工作集B對(duì)應(yīng)的最優(yōu)化問(wèn)題
　　
　　得解，據(jù)此更新中的第i個(gè)和第j個(gè)分量，得到新的可行的近似解；
　　(4) 若在精度范圍內(nèi)滿足某個(gè)停機(jī)準(zhǔn)則，則得近似解，停止計(jì)算；否則，令k=k+1，轉(zhuǎn)第（2）步。
　　2.2 垃圾標(biāo)簽檢測(cè)模型的優(yōu)化算法
　　使用SMO算法從大規(guī)模垃圾標(biāo)簽訓(xùn)練集中抽取對(duì)分類其決定作用的邊界支持向量，其算法描述如下：
　　算法二
　　設(shè)為訓(xùn)練樣本集，樣本集的問(wèn)題長(zhǎng)度為N。
　　(1) 將帶入算法一（SMO）求出最優(yōu)近似解；
　　(2) 根據(jù)最優(yōu)近似解向量各分量的取值情況，將大于0的分量對(duì)應(yīng)在中的訓(xùn)練點(diǎn)挑出，放入集合中。
　　(3) 選擇核函數(shù)K(ui,uj)和懲罰參數(shù)C，構(gòu)造并求解如下最優(yōu)化問(wèn)題：
　　
　　得到最優(yōu)解
　　(4) 通過(guò)選擇中小于C的正分量，獲得支持向量，并據(jù)此計(jì)算；
　　(5) 求得決策函數(shù)；
　　
　　3. 實(shí)驗(yàn)
　　3.1實(shí)驗(yàn)設(shè)計(jì)
　　本文采用的數(shù)據(jù)集來(lái)自PKDD2008提供的Spam檢測(cè)數(shù)據(jù)集，該數(shù)據(jù)集采集了國(guó)外知名社會(huì)書(shū)簽網(wǎng)站Socialbookmarking和BibSonomy的數(shù)據(jù)。這兩大網(wǎng)站都是基于Folksonomy框架的系統(tǒng)，數(shù)據(jù)集中包含了垃圾投放人和普通用戶的數(shù)據(jù)。數(shù)據(jù)集情況如表1所示，其中普通用戶是指網(wǎng)站中行為正常的用戶，垃圾投放人指網(wǎng)站中行為具有危害性的用戶，用戶分類是由網(wǎng)站專業(yè)人員經(jīng)過(guò)行為跟蹤、專業(yè)分析判斷后確定的。TAS是指用戶、標(biāo)簽和資源的關(guān)系記錄，向量維數(shù)是指原始數(shù)據(jù)經(jīng)文本處理、權(quán)值計(jì)算后得到的用戶特征向量的維數(shù)。
　　表1數(shù)據(jù)集情況
　

　　實(shí)驗(yàn)硬件環(huán)境：CPU為P4，3.00GHz，512M內(nèi)存。算法實(shí)現(xiàn)語(yǔ)言為C++。用戶模型創(chuàng)建算法中的詞條切分環(huán)節(jié)，使用porterstemmer詞干提取器提取文本詞干。SVM算法中涉及的核函數(shù)選用徑向基函數(shù)（RBF）：
　　
　　其主要參數(shù)設(shè)置為C=1000，=0.0001。
　　3.2實(shí)驗(yàn)結(jié)果及分析
　　實(shí)驗(yàn)一設(shè)計(jì)了6組不同規(guī)模的數(shù)據(jù)集，對(duì)比之間的效果。這6組訓(xùn)練集是按原訓(xùn)練集的正、負(fù)類的比例截取而獲得。
　　表2不同規(guī)模的訓(xùn)練數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對(duì)比

　　表2給出了6組數(shù)據(jù)的實(shí)驗(yàn)對(duì)比情況。這6組訓(xùn)練樣本數(shù)據(jù)分別是從500條逐漸擴(kuò)大到原數(shù)據(jù)集規(guī)模。隨著訓(xùn)練集規(guī)模的變化，分類器的檢測(cè)精度一直保持在97%以上，沒(méi)有較大浮動(dòng)。由此說(shuō)明，本文的垃圾標(biāo)簽檢測(cè)模型效果是穩(wěn)定的。另外，當(dāng)訓(xùn)練樣本數(shù)增加到5000條時(shí)，分類器的訓(xùn)練速度出現(xiàn)了明顯下降，而且下降速度非常快。由這一現(xiàn)象證明了，當(dāng)問(wèn)題規(guī)模擴(kuò)大到一定程度時(shí)，若直接利用檢測(cè)模型處理，速度會(huì)出現(xiàn)瓶頸，影響檢測(cè)效果。
　　實(shí)驗(yàn)二是一組對(duì)比實(shí)驗(yàn)，用垃圾標(biāo)簽分類模型分別對(duì)未處理過(guò)的數(shù)據(jù)集與利用SMO算法優(yōu)化后的數(shù)據(jù)集進(jìn)行訓(xùn)練并實(shí)施分類預(yù)測(cè)，結(jié)果如表3所示。優(yōu)化后的壓縮比達(dá)到35.88%，但分類精度沒(méi)有損失，保持原有的97.4518%，訓(xùn)練時(shí)間比原來(lái)提高了38.46%
　　表3數(shù)據(jù)集優(yōu)化前后分類情況對(duì)比

　　
　　從以上實(shí)驗(yàn)可知，本文的垃圾標(biāo)簽檢測(cè)模型雖然分類精度穩(wěn)定，但直接將其作用于大規(guī)模數(shù)據(jù)集存在速度瓶頸。利用本文提出的SMO算法優(yōu)化數(shù)據(jù)集法，能有效的壓縮數(shù)據(jù)集的規(guī)模，同時(shí)不損失分類精度。
　　
　　4. 結(jié)論
　　針對(duì)垃圾標(biāo)簽檢測(cè)數(shù)據(jù)集特征維數(shù)高、規(guī)模大，影響分類檢測(cè)模型效果的問(wèn)題，本文提出利用SMO算法優(yōu)化數(shù)據(jù)集，有效的約減龐大的垃圾標(biāo)簽特征數(shù)據(jù)集，減輕檢測(cè)模型的運(yùn)算負(fù)擔(dān)。本文方法不僅較大幅度的約減了垃圾標(biāo)簽特征數(shù)據(jù)集，還保持了原有數(shù)據(jù)集的分類精度，提升訓(xùn)練時(shí)間。雖然本文方法對(duì)原數(shù)據(jù)集做了優(yōu)化，但數(shù)據(jù)集規(guī)模仍較大，主要原因是原數(shù)據(jù)集維數(shù)甚高，在進(jìn)行核聚類時(shí)代價(jià)較高，效果也受到一定影響。進(jìn)一步工作將對(duì)原數(shù)據(jù)集進(jìn)行降維處理。
　　
　　參考文獻(xiàn)
　　
　　[1] 鄧乃陽(yáng),田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機(jī)[M].第一版.北京:科學(xué)出版社,2004.
　　[2] 鄧乃陽(yáng),田英杰.支持向量機(jī)-理論、算法與拓展[M].第一版.北京:科學(xué)出版社,2009.