摘要：针对垃圾标签检测数据集特征维数高，规模大的问题，提出利用序列最小最优化算法大幅度约减庞大的垃圾标签特征数据集，同时保持原有分类精度，降低训练时间。为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.
