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

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

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

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