近年来，各类社交网络已经迅速发展成为国内外广大网民分享信息、参与社会热点讨论的重要网上活动场所。以国内主流的社交平台新浪微博为例，据统计(http: //finance.sina.com.cn/stock/t/2017-02-23/doc-ifyavwcv8648272.shtml)，2016年新浪微博月活跃用户全年净增长7 700万，增至3.13亿，每天发布信息1亿多条。微博作为重要的网上舆论场，对其中的话题进行建模^[1]，在商业推广^[2]、传播分析^[3-4]及舆论引导与决策^[5]等方面都有很大应用价值；同时，高质量的话题有助于正确引导网民情感方向、研究舆情扩散传播规律以及促进社会的稳定发展^[6]。然而，微博在语言文字方面的一些特点也给相关的研究带来不少障碍: 1)微博文本的长度比较短，通常不超过140字，并且用语不规范，常常包含大量网络流行语、音译词等；2)垃圾用户(spammer)常常传播营销广告^[7]和不当言论^[8]等，不仅影响用户的使用体验，而且妨碍正常商业活动在平台上的健康发展。如表 1中第一条微博内容所示，垃圾用户利用堆积关键词如“金融理财” “大学生创业”等热搜词增加被检索概率，同时插入了“LR支付，无痛消费”营销广告；3)正常用户发布的微博中也存在不少无实质内容的信息，如抒发感情、调侃恶搞等。

因此，在对微博内容进行话题分析和建模之前，有必要过滤掉与给定话题无关的噪声。通常有2种研究思路，一种是把话题噪声过滤看成分类问题，然而传统的长文本分类方法并不适用于微博^[9-10]；另一种是直接识别过滤垃圾信息，包括识别垃圾用户来检测垃圾信息以及根据内容特征检测垃圾信息。Lee等^[11]提出根据行为识别垃圾用户的方法，并在垃圾用户与正常用户比例分别为1:9和9:1的小规模数据集上取得了较高的准确率。Yang等^[12]通过总结垃圾用户的一些新特征，发现用Bayes分类器效果最好。文[13]利用用户的双向信任传播和邻居节点统计特征识别垃圾用户；文[14]用检测异常的方法，通过聚类多个用户属性把Twitter中表现异常的用户归为垃圾用户。以上方法的重点在于提取垃圾用户特征，能够用于间接发现垃圾信息，但不适用于识别正常用户发布无实质内容的噪声信息。对于垃圾信息内容，Wang等^[15]提出一种基于内容特征的垃圾微博过滤方法，结合用户、内容以及情感等特征，用多种分类方法验证了提取的特征有效性；文[16]将朴素Bayes模型与最大期望方法相结合，解决同一话题下的微博广告识别问题；文[17]提出一种多视角特征融合的方法，从词特征、社交结构和内容3方面建立规则过滤垃圾微博。这些方法基本上采用有监督机器学习的方式，算法复杂度较高且需要人工标注。

1 半监督的微博噪声过滤算法 1.1 特征抽取

考虑到微博内容相对短小，长度通常不超过140个字且内容形式多样，若采用分词方法抽取特征则存在一定局限性。因此，本文采用基于N-gram方法^[18]抽取微博特征。与基于词汇的特征抽取方式相比，基于N-gram方法主要有以下优点:一是无需对处理的微博内容做分词等预处理操作；二是与语种无关，可以同时处理中文、英文、繁体中文等内容；三是能够有效识别信息伪装，如在垃圾微博中一些敏感文字含义相对比较隐晦，使用分词工具则无法有效识别；四是能够有效地降低特征维数稀疏对微博分类造成的负面影响。具体步骤: 1)微博内容按照语段标点进行粗切分，将原文档切分为语段序列，即相对逻辑独立的单句或短语；2)对语段序列进行N-gram切分，产生的gram片断记为C_i，同时统计出现的频度，记为F_i；3)选择出现频度F_i大于设定阈值α的gram片段作为特征向量，删除所有不符合条件阈值的gram片段，形成特征向量表。

1.2 过滤算法思路

支持向量机(support vector machine，SVM)分类算法建立在统计学习理论和结构风险最小化理论基础之上，有严格的理论基础，并且可以较好地解决小样本、高维度以及非线性等问题，更适合二分类问题。与其他分类方法相比，虽然SVM有较高的分类精度，但在实际应用中仍存在一些问题。一方面，SVM对大规模分类问题训练时间长，对复杂的问题分类精度低；另一方面，传统的有监督SVM方法仅依靠训练样本集构建分类模型，而未标记样本所包含的信息却被忽略。在有限的样本集情况下，SVM训练出的模型泛化能力较弱；而如果要增加训练样本集规模，无疑会大大提高人工标注成本。

在实际情况下，未标注样本的数量往往远大于标注样本，如果用半监督SVM的学习方法，不仅要利用少量的标注样本，更要用到大量的未标注样本，因为后者能更好地刻画整个样本空间的分布特性(见图 1和2)。然而，传统半监督SVM算法存在时间复杂度高、效率低等缺陷，因此如何高效准确地利用未标注样本的分布信息成为关键。

k最近邻(k-nearest neighbor，kNN)分类算法是常见的基于距离分类方法之一，较其他方法更适合用于对类域交叉或重叠较多的待分样本集进行分类，最大的优点是算法简单，只需计算极少量的邻近样本来做决策；缺点是算法精度严重依赖k值的选择，若k值的选择较小，将导致训练样本得到的有效信息偏少；若k值的选择较大，会引入较多的噪声导致样本分类精度不准确。

基于以上考虑，同时针对微博数据量大以及微博话题噪声的特点，本文借鉴半监督SVM与kNN相结合的思想，提出了pSVM-kNN算法，仅用少量标注的样本作为训练数据，把大量未标注的数据特征引入到算法中，同时解决分类器的性能和精度问题，获得了更好的分类效果。

算法的基本思路是:先用SVM算法训练标注样本得到分类器，对未标注样本进行分类，再用kNN算法标注超平面附近的样本，然后加入到有标签样本中，开始新一轮训练。通过不断的迭代，最终获得最优的分类超平面。同时，pSVM-kNN算法分别在SVM阶段和kNN阶段引入了惩罚代价，以达到更高的准确率和召回率，进一步提高分类器精度。

不同于常见的半监督SVM算法，本文提出的pSVM-kNN算法并不估计未标注样本的分布情况，而是寻找对后续迭代训练影响力大的未标注样本，同时赋予更有把握的类别标签，再引入到新一轮的训练中。而每一轮新的训练很可能会产生新的分类平面，一些标注过的样本也有可能被赋予不同的标签，这说明前期出现了误标注，这些误标注的样本需要重置并从标注样本集中删除。在整个迭代训练的过程中充分发挥kNN算法基于距离分类的特长，能够更为准确地标注样本，使得分类超平面不断逼近最优解。

1.3 SVM阶段

在SVM阶段，本文采用直推式学习方法，先训练已标注的少量样本，得到一个初始分类器后再训练未标注样本。为进一步提高SVM分类器在实际应用中的效果，本文引入松弛变量和惩罚因子，使找到的超平面对训练样本局部扰动的容忍性达到最佳。对于惩罚因子，需要考虑2方面的因素:一是训练集的数据倾斜问题，即正负样本的分布比例情况；二是样本误分类对微博话题建模有效性的代价。因此，本文的基本算法如下:

设训练样本集合为D_l={(x₁, y₁), (x₂, y₂), …, (x_l, y_l)}，未标记样本集D_u={x_l+1, x_l+2, …, x_l+u}，其中：y_i∈{-1, +1}，l≪u，l+u=n。SVM方法的学习目标为给出未标记样本集D_u中所有样本的类别标记，即ŷ∈{ŷ_l+1, ŷ_l+2, …, ŷ_l+u}，该问题可以转化为如下的凸二次规划问题:

$ \mathop {\min }\limits_{w, b, \mathit{\boldsymbol{\xi }}} \frac{{{{\left\| w \right\|}^2}}}{2} + {C_ + }\sum\limits_{i = 1}^k {{\xi _{{i_1}}}} + {C_ - }\sum\limits_{i = k + 1}^l {{\xi _{{i_2}}}} + {C_u}\sum\limits_{j = l + 1}^n {{\xi _j}} ; $

(1)

$ \begin{array}{*{20}{c}} {{\rm{s}}.\;{\rm{t}}.\;\;\;\;{y_i} \cdot \left( {w \cdot {x_{{i_1}}} + b} \right) \ge 1 - {\xi _{{i_1}}}, {\xi _{{i_1}}} \ge 0, }\\ {i = 1, 2, \cdots , k;} \end{array} $

(2)

$ \begin{array}{*{20}{c}} {{y_i} \cdot \left( {w \cdot {x_{{i_2}}} + b} \right) \ge 1 - {\xi _{{i_2}}}, {\xi _{{i_2}}} \ge 0, }\\ {i = k + 1, k + 2, \cdots , l;} \end{array} $

(3)

$ \begin{array}{*{20}{c}} {{{\hat y}_i} \cdot \left( {w \cdot {x_j} + b} \right) \ge 1 - {\xi _j}, {\xi _j} \ge 0, }\\ {j = l + 1, l + 2, \cdots , l + u.} \end{array} $

(4)

其中: (w, b)确定了一个非噪声话题的分类超平面，ξ为松弛向量，ξ_i1(i₁=1, 2, …, k)对应非噪声话题样本，ξ_i2(i₂=k+1, k+2, …, l)对应噪声话题样本，ξ_j(j=l+1, l+2, …, l+u)对应无标记的话题样本，C为惩罚因子。

$ {C_ + } = n \cdot \frac{{{C_v}}}{{{N_v}}}, \;\;{C_ - } = n \cdot \frac{{{C_s}}}{{{N_s}}}. $

(5)

其中: C_v为非噪声话题误分类的期望代价，N_v为标记样本中的非噪声话题总数，n为配比因子，C_s为噪声话题误分类的期望代价，N_s为标记样本中的噪声话题总数。在实验中，希望尽可能不漏掉噪声样本，因此选取C_s>C_v。

C_u为设定无标记样本重要程度的参数，在初始时刻设置为较大的值，表示新标注的样本对后续训练过程有很大的影响，相比直推式支持向量机(transductive support vector machine，TSVM)算法逐渐增大C_u的方法，这种设置能缩短训练时间，提高训练效率。

根据常规的SVM算法，对于ŷ∈{ŷ_l+1, ŷ_l+2, …, ŷ_l+u}，可以构造判别函数:

$ \begin{array}{*{20}{c}} {f\left( x \right) = {\rm{sign}}\left[ {\sum\limits_{{i_1} = 1}^k {{y_{{i_1}}}{\alpha _{{i_1}}}K\left( {x, {x_{{i_1}}}} \right)} + } \right.}\\ {\sum\limits_{{i_2} = k + 1}^l {{y_{{i_2}}}{\alpha _{{i_2}}}K\left( {x, {x_{{i_2}}}} \right)} + }\\ {\left. {\sum\limits_{j = l + 1}^n {y_j^ * \alpha _j^ * K\left( {x, x_j^ * } \right)} + b} \right], } \end{array} $

(6)

$ {\rm{s}}.\;{\rm{t}}.\;\;\;0 \le {\alpha _{{i_1}}} \le {C_ + }, $

(7)

$ 0 \le {\alpha _{{i_2}}} \le {C_ - }, $

(8)

$ \sum\limits_{{i_1} = 1}^k {{y_{{i_1}}}{\alpha _{{i_1}}}} + \sum\limits_{{i_2} = k + 1}^l {{y_{{i_2}}}{\alpha _{{i_2}}}} + \sum\limits_{j = l + 1}^n {y_j^ * \alpha _j^ * } = 0. $

(9)

1.4 kNN阶段

由于SVM算法的特点，分布在超平面附近的未标注样本容易出现分类错误问题，这将会直接影响到当前分类器的精度；另一方面，超平面附近未标注样本如何分类也会对后面的迭代训练造成较大影响。鉴于上述问题，本文不对未标注样本的分布情况做预估，而是在当前超平面附近利用kNN算法找出有助于寻找最优分类平面的未标注样本，把这些样本加入到标注样本集后再进行新一轮训练，这样也避免了TSVM算法在所有未标注样本空间上进行频繁计算的缺陷。

通过SVM阶段的学习，能够用当前所有已标注的样本得到分类超平面和判别函数，由此可计算出所有未标注样本的判别函数值。在每一次训练过程中，定义当前分类超平面边界内区域，如图 3所示，即样本的判别函数值满足下列条件:

$ \begin{array}{l} {\varepsilon _1} < f\left( {{x^ * }} \right) < 1\;或\; - 1 < f\left( {{x^ * }} \right) < {\varepsilon _2};\\ \;\;\;{\varepsilon _1} = \sum\limits_{{m_ + }} {\frac{{f\left( {{x^ * }} \right)}}{{{m_ + }}}} , 0 < f\left( {{x^ * }} \right) < 1; \end{array} $

(10)

$ {\varepsilon _2} = \sum\limits_{{m_ - }} {\frac{{f\left( {{x^ * }} \right)}}{{{m_ - }}}} , \;\;\;\;\; - 1 < f\left( {{x^ * }} \right) < 0. $

(11)

即ε₁和ε₂是分类超平面两侧未标注样本判别函数的平均值。

对于这个区域的所有样本(除了原始标注样本)，利用kNN算法计算这些样本与已标注样本之间的距离，根据最近的邻居情况进行投票打分类标签。对于新的未标注样本和已标注样本类别标签没有变化的，赋予标签后把它们加入到标注样本集内；对于已标注样本在此次训练过程中标注结果发生变化的，则认为在前面的训练中是错误分类，如果继续保留会导致后面训练得出的分类超平面发生偏离，因此需要直接重置这些样本并从标注样本集中删除，然后开始下一轮的训练学习。当超平面边界区域内不再有新的未标注样本或者已标注样本的类别标签不再变化，认为此时已达到最优超平面，迭代训练即可终止。

在实际应用中，话题的噪声和非噪声数据的比例分布往往非常不均衡。为了避免待标注样本周边局部样本分布不均衡对分类结果造成影响，本文提出距离越近的样本对未标注样本类别判断的贡献越大的假定，在kNN阶段引入距离权重因子作为补偿，将较大的权值赋给较近的近邻，采用加权投票的方式判断该样本的类别。

设待标注样本的k个近邻中非噪声话题和噪声话题样本集合分别为x⁺和x^-，d(x, y)表示待标注样本x与k近邻样本y之间的距离，则k近邻中每个类别的权重因子可分别表示为:

$ {W_ + } = \sum {\frac{1}{{d{{\left( {x, {x_i}} \right)}^2}}}} , \;\;\;\;{x_i} \in {x^ + }; $

(12)

$ {W_ - } = \sum {\frac{1}{{d{{\left( {x, {x_i}} \right)}^2}}}} , \;\;\;\;{x_j} \in {x^ - }. $

(13)

最后根据权重相加的结果判断待标注样本所属类别:

1) W₊>W_-，待标注样本赋予非噪声标签；

2) W₊ < W_-，待标注样本赋予噪声标签；

3) W₊=W_-，由于k一般取值为奇数，出现这种情况说明数量少的一类标注样本距离待标注样本要相对近一些，所以应把x⁺和x^-中数量少的那个类的标签赋给待标注样本。

1.5 算法步骤

综上所述，pSVM-kNN算法步骤如下:

初始条件: 原始标注样本集L，训练标注样本集L′和未标注样本集U。

步骤1  使用SVM算法对有标注样本集L进行初始学习，得到初始分类器。

步骤2  用初始分类器对未标注样本集U进行分类，计算每一个样本的判别函数值，对于分类超平面边界区域的所有未标注样本用kNN算法分类并作为训练标注样本加入到L′。

步骤3  用L∪L′重新训练分类器，对在新的分类超平面区域内所有未标注样本(包括训练标注样本)用kNN算法再分类。

步骤4  分析kNN算法分类结果，把不在L′的新标注样本加入到L′中，对于已在L′的样本且此次训练后类别发生变化的，去除类别标签并从L′中删除。

步骤5  如果训练标注样本集L′发生变化，则返回步骤3；否则就用当前分类平面对剩下所有未标注样本做分类并赋予类别标签，算法结束。

2 实验结果与分析

节1中详细介绍了基于半监督pSVM-kNN模型的话题噪声过滤算法。为了定量地分析微博话题噪声过滤方法的性能，本文爬取新浪微博中2015年的部分数据，其中包括2015年一些热门微博话题，涉及娱乐、社会、军事以及政治等多个领域。从中选取微博话题进行实验，分别使用准确率、召回率和F值3个指标衡量和对比本文提出的pSVM-kNN模型与其他模型的性能表现。

2.1 实验数据

从新浪微博中随机爬取关于10个微博话题的数据共143 751条，其中10个微博话题选取与领域分布如表 2所示。

每个话题分为2部分，一部分为“标注数据集”，即从微博话题中随机选取和标注若干条数据，用于实验中的训练样本集和测试样本集；另一部分为“未标注数据集”，即除了人工标注部分的数据外，剩余的微博话题数据不做标注，如表 3所示。

在不同话题中含噪声话题与无噪声话题的比例不同。例如，“iPhone6”话题中含噪声微博大约占84%，而“9.3大阅兵”话题中含噪声微博仅占17%，如表 4所示。

2.2 实验内容与结果 2.2.1 模型选择

实验比较以下3个算法模型的噪声过滤效果。

1) 朴素Bayes分类算法(Naïve Bayes，NB):话题的特征选取使用节1.1中特征抽取处理后的结果，利用训练样本集中“含噪声话题”与“无噪声话题”数据，实现一个完全有监督的NB分类模型；

2) SVM:由于线性核支持向量机(linear-SVM)在文本分类中效果较好，因此本文采用Linear-SVM进行实验，模型的实现采用LibSVM工具(http://www.csie.ntu.edu.tw/~cjlin/libsvm/)。在实验中支持向量机对训练集非平衡问题非常敏感，因此在实现支持向量机的过滤过程中，根据比例调整训练集数据，调整后训练集数据中两个类别的比例大约为1:1。

3) pSVM-kNN算法:文本特征提取采用N-grams方法，训练集处理同SVM分类器，同时，使用话题下的“未标注集”作为方法中所需的未标注文本集。

2.2.2 试验结果及分析

本文在实验中采用交叉检验的方式(以k=1为基准)，通过计算分类器的误差率选取k值。实验结果表明:当k=5时，分类器有着最小的误差率，因此设定k=5。

为验证在不同标注集下不同模型对话题的过滤效果，从标注训练集中分别随机选取32、64、128、256以及512条标注数据训练分类器，剩余的标注集作为测试集，然后分别对每个话题进行5组训练集的实验，每组实验分别做5次，最后将5次实验平均结果作为该组实验的最终结果。

1) 准确率评估。

首先评估算法准确率，准确率表示正确分类的样本数量占所有分类样本数量的比例，表征了实验中测试数据的整体分类效果。准确率的计算如下:

$ {\rm{Accuracy}} = \frac{{{\rm{TP}} + {\rm{TN}}}}{{{\rm{TP}} + {\rm{FP}} + {\rm{TN}} + {\rm{FN}}}}. $

(14)

其中: TP表示被正确判断为“含噪声话题”的含噪声话题数量；TN表示被正确判断为“无噪声话题”的无噪声话题数量；FN表示被错误判断为“无噪声话题”的含噪声话题数量；FP表示被错误判断为“含噪声话题”的无噪声话题数量。

图 4a与4d分别是算法SVM、NB和pSVM-kNN在“我是歌手”话题、“iPhone6”话题的5组标注训练集下的准确率情况。如图 4所示，随着训练集规模的不断增加，3种算法的准确率都呈现增加的趋势，这也说明训练集规模越大，训练出的模型的准确率越高。相比较而言，算法NB与SVM在不同训练集规模的情况下准确率有着一定的优势，而本文提出的半监督算法比NB算法在准确率上有一定的提高。从实验结果还可以看出，随着训练集规模的不断增加，3种算法的准确率差距呈现缩小的趋势。因此在训练集规模较小的情况下，本文提出的半监督方法在准确率方面优势更加明显。

2) 召回率评估。

召回率表示正确分类的含噪声话题样本数占真实含噪声话题样本数的比例。召回率计算如下:

$ {\rm{Recall}} = \frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{TN}}}}. $

(15)

图 4b与4e分别是算法SVM、NB和pSVM-kNN在“我是歌手”话题、“iPhone6”话题的5组标注训练集下的召回率情况。从召回率指标来看，在不同训练集规模情况下，pSVM-kNN算法的表现最优，其次是算法NB，算法SVM最差。与准确率的变化幅度相比，3种算法的召回率差距呈缩小趋势。

3) F值评估。

最后，评估各算法的F值(F-measure)。F值计算如下:

$ F - {\rm{measure}} = \frac{{{\rm{2TP}}}}{{{\rm{2TP}} + {\rm{FN}} + {\rm{FP}}}}. $

(16)

F值表征了测试数据分类为“含噪声话题”类别的分类效果。由于准确率的高低容易受到“含噪声话题”与“无噪声话题”数量比例的影响，因此需要F值衡量指标。本文对实验结果的评价中，F值侧重于“含噪声话题”的分类效果。在理想情况下，“含噪声话题”的精确度和召回率都应该相对较高，保证噪声过滤之后的话题中，大部分话题都是“无噪声话题”，且尽可能避免将“无噪声话题”划分为“含噪声话题”。

图 4c与4f分别是算法SVM、NB和pSVM-kNN算法在“我是歌手”话题、“iPhone6”话题以及5组标注训练集下的F值情况。相比而言，本文的算法与算法SVM和NB相比，在F值方面有一定的优势，与算法SVM相比优势明显。

3 结论

在算法方面，本文提出的半监督pSVM-kNN算法融合了半监督SVM算法和kNN算法的优点，重点解决在半监督训练过程中如何找到最优分类超平面的问题。在训练混合样本集的过程中，本文对分类超平面边界区域的样本进行标注，应用kNN算法找到最有可能的类别标签，通过迭代训练尽快找到最优解。实验结果表明: pSVM-kNN在准确率、召回率和F值方面均优于其他的对比方法。然而，pSVM-kNN算法在kNN阶段增加了一定的计算开销，这是一个不足之处。一种可能的改进是简化kNN算法，降低算法复杂度和时间开销，提升训练效率。