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

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

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

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