一种应用SAVBP神经网络的僵尸粉判别方法

王越，张剑金

(重庆理工大学计算机科学与工程学院，重庆 400054)

一种应用SAVBP神经网络的僵尸粉判别方法

王越，张剑金

(重庆理工大学计算机科学与工程学院，重庆 400054)

微博僵尸粉干扰了微博的正常社交环境，对微博用户影响巨大。首先，阐述了微博僵尸粉的发展趋势与最新特点，分析了微博僵尸粉与正常用户的不同特征;其次，针对微博数据量大、使用BP神经网络判别僵尸粉易陷入局部极小点、收敛速度慢、无法收敛等缺点，提出基于模拟退火算法的可变速率BP神经网络－SAVBP，并建立僵尸粉判别模型;最后，使用新浪微博数据对系统进行评估。结果显示:该系统对微博僵尸粉有93%的判别准确率与93%的召回率。

僵尸粉;BP神经网络;模拟退火;可变速率

自2009年8月新浪微博正式推出以来，微博在中国迅速发展，成为最流行的社交网络之一。微博用户的粉丝数在一定程度上反映了用户的影响力与受欢迎程度。为了快速提高粉丝数量，市场上出现了大规模的买粉现象。但随着用户粉丝需求量的增加，使用真实用户作为粉丝进行交易已经无法满足需求，一种全新的微博僵尸粉开始出现。目前学术界对僵尸粉并没有统一的定义。百度百科定义为:微博上的虚假粉丝，指花钱可以买到“关注”，有名无实的微博粉丝，通常是由系统自动产生的恶意注册用户;维基百科定义为:一些长期没有动态、同一IP地址申请多个微博账号的用户。随着僵尸粉的不断发展，这些定义已经过时。本文根据僵尸粉的最新发展特点，对僵尸粉进行了重新定义:出现于微博平台上，以提高用户粉丝数为目的，由软件自动产生、维护的一类虚假用户。僵尸粉具有操作简单、维护成本低等特点，在短短几年时间内迅速发展并遍布整个微博网络，给微博造成了诸如诚信危机、用户影响力无法正确计算、用户社交网络关系模糊不清等问题［1－2］。因此，准确判别出微博僵尸粉，剔除僵尸粉对微博的影响具有现实意义。

1 僵尸粉特征分析

僵尸粉由软件自动产生并维护，并没有实际真人使用。故僵尸粉在个人信息、微博内容等方面都有聚团相似性且与普通用户特征差别明显。

1.1 个人信息特征

在微博网络中，用户粉丝与关注代表了用户的社交关系。假设用户A是用户B的粉丝(也可以说用户A关注了用户B)，则认为用户A认同用户B为自己的朋友。僵尸粉通过买卖手段提高其他用户的粉丝数。商家为了节约成本，通常一个僵尸粉充当几百甚至几千用户的粉丝，故僵尸粉的关注数较多。而僵尸粉自身没有社交关系，粉丝数极少。人气指数是用户粉丝数与关注数的比值［3］，可以很好地反映用户社交关系的组成。

普通用户的粉丝数与关注数较为接近，反映了现实生活中“对等”的社交关系，即我认识的和认识我的人的数量相差不大。而僵尸粉的关注数远远大于他的粉丝数，偏离了实际的社交关系网络。个人信息定义的僵尸粉特征如表1所示。

表1 僵尸粉个人信息特征

1.2 微博内容特征

早期的僵尸粉并不会发送微博，但为了逃避新浪微博封杀，僵尸粉开始升级，大量更新微博，其微博数远远超过了普通用户的微博数。僵尸粉能发送大量微博，但并不能发送原创微博，只能大量转发其他用户的微博。本文定义微博转发率计算转发微博数在总微博数中所占的比例:

表2 僵尸粉微博内容特征

2 基于模拟退火算法的可变速率BP神经网络－SAVBP

神经网络拥有较好的非线性能力与泛化能力，只要有足够的训练样本，BP神经网络就能自学习与自适应。本文选取BP神经网络作为基本判别模型。

2.1 BP神经网络及其缺陷

在人工神经网络出现后的很长一段时间里，并没有找到一种能解决连接权值调整问题的有效算法，直到BP算法出现，成功地解决了求解非线性连续函数的神经网络权重调整问题［4］。BP算法实质为最速下降法迭代循环求解权值，网络被分为输入层、隐藏层、输出层3层。文献［5］指出:只要隐藏层中拥有足够多的神经元，BP神经网络就可以以任意精度逼近任何函数。

BP神经网络一般使用均方误差作为性能指标。假设使用的数据集为:

这里pQ是目标的输入，tQ是对应的目标输出。

每输入一个样本，将神经网络的实际输出与目标输出做比较，调整均方误差的权值与偏置以使其最小化［6］。为便于计算，把输入输出矩阵化:这里a为实际输出矩阵，t为目标输出矩阵，n为第n次迭代。

BP算法使用以下式子修改权值与偏置［2］:

其中:Wm为第m层对应权值矩阵;bm为第m层对应偏置矩阵;k为第k次迭代;∂为学习速度;am－1为第m－1层网络输出;Fm(nm)为关联函数。

BP神经网络采用最速下降法(梯度法)计算性能函数的最小值，因而存在着易陷入局部极小点、无法收敛、收敛速度慢等缺点［7］。

1)易陷入局部极小点:BP网络从某一初始点开始寻找使均方误差下降且下降最快的点，但如图1所示误差函数是一个多维空间曲面，可能存在着多个凸点与凹点。在搜寻过程中，算法可能陷入某一小凹面区无法跳出，从而无法找出全局最小点。

图1 误差函数曲面

2)收敛速度慢、无法收敛:由Wm(k+1)= Wm(k)－∂Sm(am－1)T可知:学习速度∂直接影响收敛速度。当∂过小时，收敛速度较慢;当∂变大时，网络又将变得振荡、无法收敛。

2.2 BP神经网络的改进

微博数据量庞大，使用传统的BP神经网络判别僵尸粉计算缓慢，且当计算陷入局部极小点时，判别效果较差。

由式(5)可知:学习速度∂是个定值，直接影响收敛的速度，BP神经网络运行的各时期对学习速度有着不同要求。当距极小点较远时，要求较大的学习速度以提高收敛速度;当越接近极小点时，要求越小的学习速度以提高收敛精度。文献［7－9］引入学习因子与动量项实现可变速率的神经网络，动态改变学习速度。

模拟退火算法是一种优秀的全局寻优算法，其出发点是把现实生活中固体物质的退火过程用于组合优化问题。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在陷入局部最优解时能以一定概率跳出并最终趋于全局最优［10］。其中:k是常数;exp表示自然指数，且dE＜ 0;T为初始温度。

由式(7)可知:温度T越高，dE的降温的概率就越大;温度越低，则出现降温的概率就越小。又由于dE＜0，kT＞0，所以dE/kT＜0，P(dE)的函数取值范围为(0，1)。随着温度T的降低，P(dE)会逐渐降低，并最终趋于稳定。模拟退火算法能很好地解决BP算法易陷入局部最小点的缺点，理论上只要初始温度T足够大，则一定能找出全局最小点。

本文结合模拟退火算法与可变速率的BP神经网络，提出一种基于模拟退火算法的可变速率BP神经网络SAVBP，用以提高计算速度并寻找全局最优解。

具体算法如下:

1)初始化:初始温度T(充分大);

2)BP网络开始训练，每一组数据输入完毕，计算均方误差Fn(X)。如Fn(X)－Fn－1(X)小于ε(ε为以极小值)，则判断网络陷入了局部最小点区间。当温度T小于ρ(ρ为一极小值)时转8)。否则转3)进行模拟退火;

3)在原有权值W上添加一个随机权值，在原有偏置b上添加一个随机偏置，重新计算均方误差F'(X);

4)计算增量Δt=F'(X)－Fn(X);

5)若Δt＜0则接受F'(X)作为新的当前解，否则以概率exp(－Δt/T)接受F'(x)作为新的当前解。T为当前的温度，当T＜T0(T0为临界温度)时算法终止;

6)降温退火T=r*T，0＜r＜1，如第5)步新解接受则转7)，否则转3);

7)以现有权值、偏置作为BP算法的起始点重新训练BP网络，转2);

8)所有局部极小点区间都已找出，判断全局最小区间，使用可变速率BP神经网络继续寻找全局最优点。

3 实验与结果分析

3.1 实验数据获取与标注

本文使用新浪微博提供的API对微博数据进行抓取，新浪微博自身拥有一套简单判别僵尸粉的方法。已被新浪判别出的僵尸粉在抓取数据时会被自动过滤，无法抓取，故只研究未被新浪识别的新型僵尸粉，并最终成功抓取5 000个用户数据、232 357条微博数据。抓取到的微博数据并未标注普通用户与僵尸粉，故本文根据用户信息、微博内容、链接关系等特征对用户类别进行手工标注。此外，为了便于有效分类，需对数据进行预处理。在人气指数、微博转发率的计算中，有可能出现除数为0的情况，无法计算。该类用户大多为新注册用户，无法分辨是普通用户还是僵尸粉，故把该类用户从数据集中排除。最终本文人工分类了4 500个用户，其中普通用户为4 111个，僵尸粉为389个。取其中1/3数据作为训练样本，其余作为测试样本。

3.2 实验结果

经过多次实验表明:针对本文使用的数据集，在模拟退火中选取初始温度T为3 000，降温参数r为0.99，临界温度T0为0.01。在BP神经网络中选取激活函数为S型激活函数，网络层数为3，隐含层神经元数为6，学习速率∂为0.1时具有较好的收敛性与较高的判别准确率。

采用5－6－2的SAVBP网络建立僵尸粉判别模型，如图2所示。

图2 SAVBP网络建立僵尸粉判别模型

其中:ZF表示僵尸粉，NU表示普通用户。

当限定收敛精度为0.03时，不限制迭代次数，比较3类神经网络的收敛性曲线。由结果可知:传统BP网络无法收敛到0. 03;模拟退火改进的BP网络迭代13 360次可达到指定精度，如图3所示;SAVBP网络迭代6 820次可达到指定精度，如图4所示。

图3 模拟退火改进的BP网络迭代曲线

图4 SAVBP网络迭代曲线

由仿真结果可知:传统的BP神经网络陷入了局部极小点，无法跳出，导致无法达到指定精度;模拟退火BP网络与SAVBP网络均能达到指定精度，但SAVBP网络收敛速度明显快于模拟退火改进的BP网络。

本文比较了3类神经网络算法迭代次数在50 000次之内时的最小收敛精度。实验结果如表3所示。

表33 类神经网络最小精度对比

由表3可以看出:BP神经网络易陷入局部最小点，收敛精度最低;SAVBP网络能达到最好的收敛精度。

使用SAVBP网络分类僵尸粉，实验结果如表4所示。

对2 740个普通用户进行分类，分类正确的用户为2 586个，准确率为94.4%，并具有94.4%的召回率，F1－Measure达到了0.931。通过分析分类错误的用户信息，发现把普通用户判别为僵尸粉的主要原因是微博网络中某些用户喜欢大量关注名人，并喜欢转发名人用户微博，导致微博转发率、关注数等属性皆与僵尸粉相似。但从其所发的原创微博与微博评论上可以看出其为普通用户。

对260个僵尸粉进行分类，分类正确的用户为238个，准确率为91.6%，并具有91.6%的召回率，F1－Measure达到了0.929。通过分析分类错误的用户信息，发现把僵尸粉误判为普通用户的主要原因为僵尸粉从开始使用微博到稳定需要一个发展的过程，某些刚开始使用微博的僵尸粉在个人信息方面与稳定时的僵尸粉特征差别较大。但从其所发微博中已经表现出僵尸粉转发多、无原创等特征。

4 结束语

微博在快速发展的同时产生了僵尸粉问题。本文首先对僵尸粉进行了概念上的定义，分析了僵尸粉与普通用户的不同特征，并针对微博网络数据量大，使用普通BP神经网络计算缓慢、容易陷入局部极小等缺点，提出了SAVBP神经网络算法。最后实现了僵尸粉判别模型，使用新浪微博数据进行测试，取得了较为满意的结果。

随着僵尸粉的不断变异升级，本文所选取的特征可能会渐渐失效，同时僵尸粉也会产生更加复杂的特征。跟踪僵尸粉的变异升级过程并使用新的特征判别僵尸粉将是一项长期的工作。此外，由于SAVBP基于模拟退火算法，具有不稳定性，故选取更加优秀的全局寻优算法将是下一步的研究方向。

［1］Shen Yang，Li Shuchen，Ye Xiaoxiao，et al.Content mining and network analysis of microblog spam［J］.JCIT，2010，5(1):135－140.

［2］Ghosh S，Korlam G，Ganguly N.Spammers’Networks within Online Social Networks:A Case－Study on Twitter［J］.ACM WWW 2011，2011.

［3］郭浩，陆余良，王宇，等.多特征微博垃圾互粉检测方法［J］.中国科技论文，2012，7(7):548－551.

［4］Hornik K M，Stinchcombe M，White H.Multilayer feedforward networks are universal approximators［J］.Neural Networks，1989，2(5):359－366.

［5］Vogl T P，Mangis J K，Zigler A K，et al.Accelerating the convergence of the backpropagation method［J］.Biological Cybernetics，1988，59:256－264.

［6］Martin T Hagan，Howard BDemuth.Neural Network Design［Z］.PWS Pub.Co，2002.

［7］唐艳，付存君，魏建新.基于自适应学习速率的改进BP神经网络［J］.计算机光盘软件与应用，2012(4): 48－49.

［8］罗胜琪，付金勇.对BP神经网络算法传递函数的改进［J］.中国科技博览，2011(28):418－418.

［9］马玉梅，武玉厚.动量因子对BP算法的影响［J］.中央民族大学学报，2008，17(4):312－313.

［10］孟力，陈少雄.基于模拟退火神经网络的高科技成果转化评估研究［J］.科技管理研究，2011，31(15):91－93.

(责任编辑 杨黎丽)

Discrimination Method of Zombie Fans Based on SAVBP Neural Network

WANG Yue，ZHANG Jian－jin
(School of Computer Science and Engineering，
Chongqing University of Technology，Chongqing 400054，China)

:Zombie fans of microblogging interfere normal social environment and have enormous impact on microblogging users.First，this paper expounded microblogging zombie fans with the latest trends，analyzed microblogging zombie fans with different characteristics of normal users.Then，by the large amount of data for the microblogging，the use of BP neural network discriminant zombie fans is easy to fall into local minima，convergence slow convergence and other shortcomings.We proposed variable rate BP neural network－SAVBP based on simulated annealing algorithm，and established the zombie fans discriminant model.Sina microblogging data were used to evaluate the system.The results show that the system can identify microblogging zombie fans with 93%accuracy and 93%recall rate.Key words:zombie fans;BP neural network;simulated annealing;variable rate

10.3969/j.issn.1674－8425(z).2014.04.016

2013－12－10

重庆理工大学研究生创新基金资助项目(YCX2012317)

王越(1961—)，男，博士，教授，主要从事数据挖掘、数据库技术、嵌入式系统及应用研究;张剑金(1988—)，男，浙江湖州人，硕士研究生，主要从事社交网络数据挖掘研究。

王越，张剑金.一种应用SAVBP神经网络的僵尸粉判别方法［J］.重庆理工大学学报:自然科学版，2014 (4):72－76.

format:WANG Yue，ZHANG Jian－jin.Discrimination Method of Zombie Fans Based on SAVBP Neural Network［J］.Journal of Chongqing University of Technology:Natural Science，2014(4):72－76.

TP391

A

1674－8425(2014)04－0072－05