微博垃圾用户检测一直是微博反垃圾研究的工作重点, 从检测方法上可以分为两类：基于监督学习算法的检测方法和基于无监督学习算法的检测方法^[1]。在监督学习检测方面, 文献[2]使用Twitter提供的API(application programming interface)抓取了活跃的Twitter用户, 讨论了一些基于用户和基于内容的垃圾用户和合法用户之间不同的特征, 利用这些特征来帮助检测垃圾用户。文献[3]开发了一个数据采集器, 收集了两万多个微博用户发布的微博, 分析了垃圾用户和正常用户之间不同的行为特征和文本特征, 整合了SVM、RF(random forest)和NB(naive bayes)3种监督学习算法并实现了自动垃圾信息检测框架。文献[4]从爬取的新浪微博数据集中研究一组与消息内容和用户行为相关的最重要的一套特征, 并将其应用于基于SVM的垃圾用户检测模型, 用于检测垃圾信息的发送者。

在无监督学习检测算法方面比较具有代表性的是Tan等^[5]提出一种无监督的社交网络垃圾检测方法, 该方法通过观察垃圾用户行为模式, 发现垃圾用户通过不断改变行为来逃避检测。文献[6]考虑了每个用户在用户关系中的活动序列, 提取社交网络特征, 并使用马尔可夫模型混合标记垃圾用户, 最后利用基于马尔可夫随机场的统计关系模型检测垃圾用户群。文献[7]提出一种在线社交网络垃圾用户检测方案, 该方案从Facebook网页中抓取用户数据, 然后按照用户的兴趣进行分组, 每个组内建立图结构, 根据节点间的相似度区分用户。

综上所述, 现有的微博垃圾用户研究方案中, 基本上都是对全局的垃圾用户特征进行分析, 将问题转化为二分类问题, 即分出垃圾用户和正常用户, 缺乏针对某类垃圾用户的特征分析, 这样会使垃圾用户逃避系统的检测。笔者在模糊多类支持向量机算法^[8]基础上, 设计了一种垃圾用户检测方法。该方法在进行垃圾用户检测时, 利用CDF(cumulative distribution function)曲线寻找每类垃圾用户区分度高的特征, 并利用这些特征构造多类分类器。这种多分类器基于一对多SVM算法, 然后针对一对多SVM产生的混分样本和漏分样本进行模糊处理, 最后得到基于FMSVM(fuzzy multi-class support vector machine)的一种垃圾用户检测方法。

1 相关定义 1.1 多分类思想

定义1  多分类, 给定一组训练实例(X₁, Y₁), (X₂, Y₂), …, (X_n, Y_n), 典型地, 每个实例X_i(i=1, 2, …, n)是一个m维向量, Y_i是一个有K(K≥1)个类别的向量, 分类的任务是从训练实例中学习一个模型f:X→Y, 从而对新的实例给出一个值得信赖的类别预测。

多类分类(multi-class classification)学习的分类器需要对一个样本指定唯一的类别, 常见的多类分类器的构造策略有2种：第1种是基于距离或者后验概率一次性地给出所有类别的度量, 然后判定度量结果, 选择度量值最大的类别作为预测类别; 第2种的思想是将多类分类问题拆解为多个二值分类问题, 然后结合全部二值分类的结果, 得到组合分类器。

第1种的指导思想看起来简单, 但由于该类最优化问题的设计方法和求解过程相对来说过于复杂, 还要同时计算出所有多类分类决策函数, 计算量太大, 实现难度大、可行性比较弱, 未被广泛应用。因此, 笔者选择第2种策略来构造多分类器。

1.2 多分类SVM

SVM是统计机器学习理论(statistical learning theory, SLT)的核心内容, 它基于VC维(vapnik-chervonenkis dimension)理论和结构风险最小化原理^[9]。现如今, SVM作为分类算法已经得到了相当广泛的应用, 常应用在遥感图像识别^[10]、人脸检测^[11]以及入侵检测^[12]等方面, 是目前最常用、效果最好的分类器之一。它能够在有限的样本数据中权衡模型的学习能力与复杂性, 并自主寻找多分类有比较好的区分能力的支持向量, 达到不同样本类之间间隔最大化的目的, 此外, SVM其本身的优化目标是结构化风险最小, 容易抓住数据和特征之间的非线性关系, 在小样本训练集上能够得到比其他算法好很多的结果, 因此, 笔者将运用SVM构造多分类器。

SVM最初的设计目的是将样本分为正类或者负类, 但是本研究的目的是要解决多分类问题, 因此, 选择间接的一对多SVM来构造多类分类器。

定义2  一对多SVM, 该算法是最早出现也是目前应用最为广泛的多类分类方法之一^[13]。与一对一SVM构建分类器的思想不同, 对于K类分类问题, 其步骤是用一类和剩下其他所有类判别分类, 即构造K个二值分类器。对于第i(1≤i≤K)个分类器, 将i类中训练样本作为正类, 然后将其他类的训练样本作为负类, 待分类样本通过K个分类器分类, 找出属于正类的一个, 得到最后的分类结果。

1.3 隶属度函数

SVM算法对数据中存在的孤立点和干扰数据是非常敏感的, 在一对多SVM分类器中会存在决策函数出现混分或者漏分的情况, 如图 1所示, 此时无法判断待测样本类的类别, 因此, 需要对决策函数进行处理, 或者对决策函数的分类结果作进一步判断。

Zadeh^[14]提出“隶属度函数”来反映了隶属度问题。在给出的模糊集中, 要对论域U上面的每个元素给出隶属度, 隶属度表示一个元素属于一个集合的程度, 隶属度越高就表示属于该集合的程度越大, 隶属度越低就表示属于该集合的程度越小。

常用的隶属度函数有4种, 分别是三角形隶属函数、钟型隶属函数、高斯隶属函数和两边型高斯隶属函数。其中, 高斯隶属函数具有良好的抗干扰能力, 性能良好, 计算方便, 模糊化结果更接近于人的认知特点, 因此, 笔者在垃圾用户分类中选择高斯隶属函数。

定义3  高斯隶属函数(gaussian membership function)^[15], 它是典型的模糊控制算法之一, 由2个参数{c, σ}来描述：

$ g\left( {x, c, \sigma } \right) = {e^{ - \frac{{{{\left( {x - c} \right)}^2}}}{{2{\sigma ^2}}}}}。$

(1)

公式(1)中, x为自变量, c为某类聚类中心, σ决定了高斯函数的陡度。通过公式(1)可以得出：0 < g(x, c, σ)≤1, 当x距离聚类中心c越近, 那么其函数值就越大, 也就是隶属于该类的可能性就越高。

在多类垃圾用户分类的过程中, 由于垃圾用户的类别是确定的且其识别范围属于个体的识别, 因此, 笔者在对垃圾用户的归类问题中, 使用模糊识别的直接方法, 而直接方法的判别标准是最大隶属度原则, 就是将样本归入到隶属度最大的类别中^[15], 具体定义如下：

定义4  设A_i∈F(U)(i=1, 2, …, n)对u₀∈U, 若存在i, 使得：

$ {A_i}({u_0}) = \max \{ {A_1}({u_0}), {A_2}({u_0}), \cdots , {A_n}({u_0})\} , $

(2)

式中：F(U)为论域U上的模糊集的全体成员; A_i(u₀)为隶属度函数中的最大值, 那么认为u₀相对地隶属于A_i。

2 基于FMSVM的垃圾用户检测模型框架

FMSVM框架采用的网页爬虫方法是UID(user IDentification)遍历爬取策略。UID就是新浪微博提供给每一个用户的ID号, 唯一对应且不会改变。UID遍历全网爬虫的算法是根据指定的UID段去爬取微博用户数据, 该算法从UID的初始字段X爬取到结束字段Y。该UID爬虫程序包括3个模块：模拟登录、网页爬虫和网页内容解析。首先根据新浪微博的特点, 实现程序对微博网页的模拟登录; 接着通过HTTP协议使用GET方法采集网页数据并对该数据进行解析。这种方法通过模拟正常用户使用浏览器客户端浏览微博的过程, 不依赖于微博平台开放API, 可以根据自己的需求灵活改变爬取数据字段。

针对新浪微博多个用户的特征数据N={X₁, X₂, …, X_n}, 其中X_i(i=1, 2, …, n)为用户i的特征向量, n表示用户数, 这里的特征为微博用户的统计特征。从上述特征数据中选取部分微博用户作为训练样本, 并对其进行标注。假设L={(X₁, Y₁), (X₂, Y₂), …, (X_l, Y_l)}表示有类标签的样本集, 其中, l表示被标记的用户数, Y_i∈{0, 1, 2, 3, 4}表示用户i的类标签, 0表示正常用户类标签, 1表示营销广告型垃圾用户类标签, 2表示重复发送型垃圾用户类标签, 3表示过度关注型垃圾用户类标签, 4表示主动骚扰型垃圾用户类标签。基于FMSVM的垃圾用户检测模型框架如图 2所示。

基于FMSVM的垃圾用户检测模型大体上可以分为两部分：训练模块和测试模块。训练模块利用训练样本构建多分类垃圾用户分类器, 测试模块主要是利用测试样本集对分类器进行测试, 检测分类效果。

第1步, 分析微博现状, 根据用户的行为模式将微博用户分为5类：营销广告型垃圾用户Spammer1、重复发送型垃圾用户Spammer2、过度关注型垃圾用户Spammer3、主动骚扰型垃圾用户Spammer4和正常用户User。利用爬虫程序获取用户原始数据集D={M₁, M₂, …, M_n}, 其中M_i(i=1, 2, …, n)是用户i的原始数据, 包括粉丝数、微博数等直接从网页爬取的基本信息, 然后利用原始数据集D通过预处理得到微博用户的特征值向量N={X₁, X₂, …, X_n}。

第2步, 对5类用户在统计分析的基础上进行人工标记处理, 获得有类标签样本集L={(X₁, Y₁), (X₂, Y₂), …, (X_l, Y_l)}, 其中Spammer1的标签样本集为L₁、Spammer2的标签样本集为L₂、Spammer3的标签样本集为L₃、Spammer4标签样本集为L₄, User的标签样本集为L₀。

第3步, 构造一对多SVM分类器。具体步骤是：针对Spammer1的分类器Classifier1, 将Spammer1标为正类, 其他4类用户标为负类, 得到新的标签样本集LS₁, 利用CDF曲线寻找Spammer1与其他4类用户区分度高的特征值Feature1={V₁, V₂, …, V_k1}, 其中k₁是被选出来的区分度高的特征个数总数, 在LS₁中只保留下Feature1的特征, 利用SVM构建Spammer1的分类器。以此类推, 完成其他4类用户的分类器, 分别为Spammer2的分类器Classifier2、Spammer3的分类器Classifier3、Spammer4的分类器Classifier4、User的分类器Classifier0。

第4步, 利用这五类分类器构造一对多SVM分类器, 先判断多分类有无不可分样本, 针对不可分样本引入高斯隶属度函数gaussian(x, c, σ)进行模糊处理, 最后得到FMSVM分类器。

第5步, 利用待测用户测试FMSVM分类器的各项指标性能。

3 基于FMSVM的垃圾用户检测算法

FMSVM算法是在一对多SVM算法的基础上引入模糊隶属度函数, 并在对不可分样本进行处理的时候, 与原算法进行融合。因此, 可以得出该算法的具体实施步骤, 并对该步骤进行代码实现, 其伪代码如表 1所示。

针对上述伪代码, 构建每一类的SVM分类器, 需要初始化惩罚参数C, 然后根据SMO(Sequential Minimal Optimization)算法计算每个最优解α^(i)*, 最后根据最优解α^(i)*, 计算ω^(i)*和b^(i)*。

表 1中模糊处理过程为：对于不可分样本x, 先计算第i类用户能与其他类区分开的决策函数：D_i(x)=w_i^Tx+b_i, 当D_i(x)=0时, 超平面形成最优分类面, 那么通过超平面的分割, 属于第i类用户的D_i(x)=1, 属于其他四类用户的D_i(x)=-1, 也就是对于不可分样本x, 当：

$ {D_i}\left( x \right) > 0。$

(3)

如果公式(3)只有一个i满足, 那么样本x就属于第i类用户。如果公式(3)中有多个i满足, 那么就存在混分样本, 为了解决这类不可分情况, 对满足公式(3)的样本点引入高斯隶属度函数, 下面具体阐述模糊处理过程。

首先, 对于用户类别i在第j类用户的最优分类面D_j(x)=0的垂直方向上定义一个隶属度函数m_{i, j}(x), 那么当i=j时：

$ {m_{i, j}}\left( x \right) = \left\{ {\begin{array}{*{20}{l}} {1, }&{for\;{D_i}\left( x \right) \ge 1}\\ {{D_i}\left( x \right), }&{otherwise} \end{array}} \right.; $

(4)

当i≠j时：

$ {m_{i, j}}\left( x \right) = \left\{ {\begin{array}{*{20}{l}} {1, }&{for\;{D_j}\left( x \right) \le - 1}\\ { - {D_j}\left( x \right), }&{otherwise} \end{array}} \right.。$

(5)

当i=j时, 如果D_i(x)≥1, 则表示只存在i类的训练样本数据, 那么假设此时m_{i, j}(x)的值是1, 否则m_{i, j}(x)的值就是D_i(x)。当i≠j时, 如果D_j(x)≤-1, 则表示类别i的样本在最优分类面D_j(x)=0的负值区域, 那么假设此时m_{i, j}(x)的值是-1, 否则m_{i, j}(x)的值为-D_j(x)。

接下来, 求m_{i, j}(x)(j=1, …, n)的最小值来定义用户类别i的隶属度函数：

$ {m_i}\left( x \right) = \mathop {\min }\limits_{j = 1, \cdots , n} {m_{i, j}}\left( x \right)。$

(6)

根据公式(6)将样本x归入类别：

$ \arg \mathop {\max }\limits_{i = 1, \cdots , n} {m_i}\left( x \right)。$

(7)

如果从公式(4)和公式(5), x满足：

$ {D_k}\left\{ \begin{array}{l} > 0, k = i;\\ \le 0, k \ne i, k = 1, \cdots , n。\end{array} \right. $

(8)

且有m_i(x)>0和m_j(x)≤0(j≠i, j=1, …, n), 将向量x归入到类别i中。混分情况得到解决, 再看多分类中的漏分样本, 即

$ {D_i}\left( x \right) < 0。$

(9)

对于满足高斯隶属度函数的样本i₁, …, i_l(l>1), 从公式(4)到公式(6), 对m_k(x)定义如公式(10)所示：

$ {m_k}\left( x \right) = \mathop {\min }\limits_{j = {i_1}, \cdots , {i_l}} - {D_j}\left( x \right)k \in {i_1}, \cdots {i_l}。$

(10)

在公式(9)中根据最大隶属度原则, 选择最大的m_k(x)(k∈i₁, …i_l)赋给D_k(x), 即

$ {m_k}\left( x \right) = {D_k}\left( x \right)。$

(11)

至此, 解决了一对多SVM中漏分的问题。

4 实验与结果分析 4.1 实验数据

通过网页爬虫的方式来遍历爬取了新浪微博中20 000多名用户的个人信息及其发表的149 090条微博信息, 其中, 选取4 928名用户作为训练数据集, 这些数据被保存在MySQL数据库中。

4.2 FMSVM分类结果分析

在构造一对多SVM分类器之前, 需要先构造5个分类器的训练集。针对每一类样本的数量, 在完整的负类样本集中再抽取相应的数量, 例如, 针对正常用户, 将正常用户标记为0, 将其余4类垃圾用户标记为-1。5个分类器的训练集样本个数如表 2所示。

对于每一类用户的分类器, 训练集样本的特征选择是十分重要的步骤。为了区分开正类与负类, 特征的选择要尽量选出区分度较高的特征, 实验通过绘制特征的CDF曲线来寻找每一类用户与其余4类用户具有较大区分度的特征, 利用这些特征作为每一类用户分类器的样本特征。

以表 2中的粉丝数特征为例, 绘制出来该特征在5类样本集中的CDF曲线。如图 3所示, 从图 3(a)和图 3(b)可以看出, 正常用户样本和营销广告垃圾用户样本的粉丝数特征与其他用户的区分度较大; 从图 3(c)、(d)、(e)可以看出, 其他3类用户的粉丝数特征区分度较小, 因此, 粉丝数是正常用户和营销广告垃圾用户要选择的特征之一。

最后, 针对每一类样本选择了如表 3所示的各类分类器的训练集特征集。

为了得到一对多SVM分类器, 利用表 2中的训练样本, 使用第2章FMSVM框架中步骤3来训练每一个用户分类器, 得到5类用户的SVM分类器。为了检测一对多SVM分类器的效果, 选择训练集样本作为本次的测试样本, 将这5类测试样本输入到一对多SVM分类器中, 然后查看每类样本的测试情况。以营销广告垃圾用户为例, 将营销广告型垃圾用户测试样本送入到这5个分类器中, 先统计只分类成正常用户、营销广告型垃圾用户、重复发送型垃圾用户、过度关注型垃圾用户和主动骚扰型垃圾用户的数量, 最后统计不可分样本的数量(即混分样本和漏分样本), 最后结果如表 4所示。

从表 4中可以得出, 正常用户的分类器能够较好地将正常用户分类出来, 测试样本中的1 000个正常用户中有938个样本被正确地分出, 比其他4个垃圾用户的正确分类比例都要高。在垃圾用户检测方面, 要在尽量保证正常用户不会误判的前提下, 提高垃圾用户的检测效果, 正常用户分类器的分类结果达到了要求。再看其他4类垃圾用户的分类情况, 从分类结果可以看出, 营销广告型垃圾用户和重复发送型垃圾用户由于多是真人操作的垃圾用户, 其行为会模仿正常用户, 因此, 相较于其他主动策略型垃圾用户会较多地被误判为正常用户。营销广告型垃圾用户和重复发送型垃圾用户之间也存在相似行为, 分类结果也表明这两类垃圾用户之间被误判为对方垃圾用户的概率要比剩下的主动型垃圾用户和过度关注型用户大。过度关注型垃圾用户分类器的不可分样本最少。主动骚扰型垃圾用户分类器的分类效果最差, 105个主动骚扰型垃圾用户只有63个被正确分类, 但是其他用户被误判为主动骚扰型垃圾用户的情况也是最少的。此外, 从结果可以看出每类用户都存在不可分情况, 因此, 引入模糊处理十分有必要。

通过分析一对多SVM多类分类器的结果, 发现一对多SVM存在较多的不可分样本, 针对不可分样本, 利用模糊处理方法继续对不可分样本进行分类。分类结果如表 5所示。

通过模糊处理, 不可分样本得到了新的分类。从分类结果来看, 每类用户的不可分样本中大部分都被正确地分类到相对应的类别中, 少部分被错分为其他类别。以营销广告型垃圾用户的不可分样本为例, 51个不可分样本中, 有31个被正确地分到营销广告型垃圾用户、5个被分到正常用户、10个被分到重发送型垃圾用户、3个被分到过度关注型垃圾用户和2个被分到主动骚扰型垃圾用户, 除了本身31个被正确分类之外, 重复发送型垃圾用户由于与营销广告型垃圾用户的行为较为相似, 不可分样本也较多地被分到重复发送型垃圾用户中。结合上文的一对多SVM分类结果与本节的模糊处理结果, 可以得到FMSVM的最后结果, 分类结果如表 6所示。

从表 6的最后结果来看, 通过模糊处理, 不可分样本得到了较好的处理。单一的评价指标在垃圾识别方面是比较片面的, 因此, 还需要评估每一个分类器的各项指标, 在计算每一类用户分类器指标的时候, 将该类作为正类, 其他4类作为负类, 将问题转化为二值分类, 评价指标分别为：准确率、精确率、召回率和F₁值, 结果如图 4所示。

从图 4可知, 五类用户的分类器中, 正常用户分类器的各项指标都比较优秀, 这说明正常用户能够被很好地分类出来, 并且较少地被误判为其他用户。四类垃圾用户分类器中, 过度关注型垃圾用户和主动骚扰型垃圾用户在准确率方面都比较高, 这是由于样本数量较少而负类样本数量较多, 即提高了公式中TN的值, 因此, 这两类样本的准确率上升, 其他两类垃圾用户分类器的准确率也能保持在90%以上。

营销广告型分类器和主动骚扰型分类器的精确率较高, 说明被检测出的这两类垃圾用户中真实的用户占比较大, 重复发送型分类器的准确率在80%以上, 过度关注型分类器的准确率最低, 但也在70%以上。四类垃圾用户分类器中, 过度关注型垃圾用户和主动骚扰型垃圾用户分类器的召回率较低, 其原因是这两类用户本身的样本数偏少, 而且存在较多样本被错分为其他类别; 营销广告型垃圾用户和主动骚扰型垃圾用户的样本数较多, 正确分类的样本数也较多, 因此, 这两类垃圾用户的召回率较高。最后, 分析综合评价指标F₁值, 四类垃圾用户分类器中, 除了过度关注型分类器的F₁值较低之外, 其余三类垃圾用户分类器的F₁值均在80%以上, 重复转发型分类器和主动骚扰型分类器的F₁值基本相同, 营销广告垃圾用户的F₁值最高。

总体来说, 4类垃圾用户的各项指标令人满意, 尤其是垃圾用户数量最多的广告营销型垃圾用户, 该类垃圾用户分类器的各项指标都比较高, 能够起到检测广告营销型垃圾用户的作用。

4.3 多分类器对比分析

随后, 在多分类器的对比上, 选择MLP(multiLayer perceptron)^[16]、MCC(multi-class classifier)与FMSVM进行对比。实验样本选择表 2中的样本集, 多分类器的评价指标依然选择准确率、精确率、召回率和F₁值, 各项指标的计算方法同FMSVM, 最后得到图 5的各项指标结果。

如图 5所示, 通过柱状图的形式展示各项评价指标实验结果。从图 5可以看出, FMSVM在准确率上高于MLP和MCC, 说明了FMSVM中加入模糊处理能够提高正确分类的样本数。在精确率方面, FMSVM略高于MLP, 明显高于MCC, 精确率得到保证意味着检测出来的垃圾用户中真实的垃圾用户占比高, 也说明正常用户被误判的比例较低, 保证精确率是有效检测垃圾用户的前提条件。在召回率上, MLP要略高于FMSVM; 相比于MCC, FMSVM比MCC低0.6%, 基本持平。最后分析综合评价指标F₁值, 3种多分类器中, FMSVM处在中等水平, 相比MLP低1.1%, 相比MCC高1.1%。总之, FMSVM算法的垃圾用户检测能力还是较好的。

5 结语

设计了一种基于FMSVM的垃圾用户检测方法。该检测方法在一对多SVM分类器的基础上, 首先, 在构造每一类用户分类器的时候, 需要选择不同的训练集, 每一类用户的训练集要将该类用户标记为正类, 其余用户标记为负类; 然后, 通过特征选择选取区分度高的特征组合成训练集; 最后, 通过训练得到5类用户的5个分类器。针对多分类的混分样本和漏分样本, 该检测方法引入模糊处理, 在垂直于SVM的最优分类面上定义一个隶属度函数, 解决多分类的不可分情况。实验对比了多分类算法, 对比结果表明, 设计的基于FMSVM的垃圾用户检测方法在多分类情况下, 能够达到较好的检测效果。