基于最大频繁项集挖掘的微博炒作群体发现方法

摘要

本发明涉及基于最大频繁项集挖掘的微博炒作群体发现方法，有效解决微博炒作群体的发现，防止虚假恶意炒作的问题，方法是，以炒作微博的相关性为线索，基于爬虫技术或微博公共开放平台获取参与炒作微博传播的账户集合；以单个微博为事务，参与微博传播的账户为项，构建炒作微博事务数据库；对待检测微博组所对应的事务数据库中的每个事务，找出所有事务中包含的最大频繁项集，计算每个最大频繁项集间的重叠率，将规模小的项集归并到大项集中，减少交集次数，事务间取交集时，用二分查找法判断事务中是否包含某项目，提高挖掘最大频繁项集的效率，发现微博炒作群体，本发明方法简单，能准确发现恶意微博炒作群体，防止给社会造成的不良影响。

说明书

技术领域

本发明涉及微博舆情监控领域，特别是一种基于最大频繁项集挖掘的微博炒作群体发现 方法。

背景技术

微博作为一种新兴的社会媒体形式，兼具博客、媒体、即时通讯功能于一身。微博自身 的即时性、草根性、移动性、互动性等特点使其成为网络舆情传播的天然载体。在网络舆情 中，微博不仅成为舆论传播的中心和渠道，同时也参与舆论的形成、发展与引导过程。

微博传播是一把双刃剑：一方面，微博为一些社会事件中的信息公开提供了一个快速响 应的平台，它在一定程度上弥补了传统媒体和其他网络工具的不足；另一方面，微博不同于 传统新闻媒体，其新闻的发布存在重复性，且真实性无法保证，可能会被利用成为谣言传播 的载体、不满情绪的导火索，甚至给国家安全和社会稳定造成极坏的后果。网络不实信息始 于其制造者，扩散于其传播者。

惠普公司旗下的社交计算研究团队在最新报告中称，新浪微博存在异常严重的话题炒作 问题，围绕热门话题转发的微博中有半数都是由炒作用户发送的。研究发现，热门话题传播 中人为操纵的虚假转发数量极大，1％的垃圾消息发送者创造了49％的转发量。自2013年8月 以来，政府部门加大了对网络舆论引导的力度，根据对“秦火火”、“立二拆四”等所在网 络推手公司的调查结果来看，网络中存在着大量有组织的推手团队，他们伙同少数“意见领 袖”组织网络“水军”，长期在网上炮制虚假新闻、故意歪曲事实，制造事端，混淆是非， 严重扰乱了网络舆论秩序，其行为已经受到国家舆情管控的高度关注，相关人等也因涉嫌犯 罪被依法刑事拘留。

因此，面向新兴媒体，针对各种隐藏的舆论煽动行为，开展对炒作微博的识别，分析其 传播群体特征，收集虚假推送行为的识别证据，甄别人为制造的炒作热点，对于发现、预测、 引导网络舆论，提高政府舆论监管能力，维护社会和谐稳定具有重要的理论价值和现实意义。

随着微博的爆炸式发展，针对微博账户的研究吸引了国内外学者的广泛兴趣，一些研究 成果近年来在WWW、KDD等重要会议上发表。目前对微博账户的研究可以大致分为以下三类： 1)特征分析，包括账户属性特征和行为特征等；2)影响力分析，包括影响力评价体系构建 及度量方法等；3)账户间关系网络分析，包括账户关系网络的基本属性、生成与演进等。

然而，目前国内外对炒作群体研究的文献相对较少，主要相关文献有对垃圾账户 (spammer)、马甲账户(sockpuppet)、僵尸账户的识别。垃圾账户是指经常发布垃圾信息的账 户，Z.Yi等人从多个角度分析了垃圾账户的特征，并采用机器学习的方式自动识别垃圾账 户。Chao Yang等人深入分析了垃圾账户间的社会关系，提出了一种根据账户间亲密度来发 现垃圾账户的方法。马甲账户是指通过注册多个账号进行发帖、转发、评论等行为的虚假账 户，Xueling Zheng等人提出了一种利用文本内容、相似度匹配来识别马甲账户的方法。僵 尸账户是指为了进行粉丝买卖而恶意注册的账户，方明等提出了一种基于微博注册账户名特 征提取的智能分类方法，具有较高的准确率。但这些方法并未解决如何发现微博炒作群体， 防止虚假炒作，炒作账户与以上几类账户之间最大的区别是，炒作账户侧重于其“炒作”行 为，参与炒作的账户较为分散且直接关系不明显，隐蔽性和组织性更强，也更加难以发现。

群体炒作与普通微博类似，传播人群的发帖、转发、评论等行为表面上是孤立的，但是 非常规的恶意传播往往不是单个人的行为，而是有组织的群体行为，但是这种群体行为是隐 蔽的，难以察觉。因此，如何发现微博炒作群体，防止虚假恶意炒作给社会造成的不良影响 和不必要的经济损失，是必需认真解决的技术问题。

发明内容

针对上述情况，为克服现有技术之缺陷，本发明之目的就是提供一种基于最大频繁项集 挖掘的微博炒作群体发现方法，可有效解决微博炒作群体的发现，防止虚假恶意炒作的问题。

本发明解决的技术方案是，基于最大频繁项集挖掘的微博炒作账户发现方法包括如下步 骤：

(1)炒作微博样本搜集：以炒作微博的相关性为线索，基于爬虫技术或微博公共开放平 台获取参与炒作微博传播的账户集合；

(2)事务数据库构建：以单个微博为事务，参与微博传播的账户为项，构建炒作微博事 务数据库；

(3)最大频繁项集挖掘：对待检测微博组所对应的事务数据库中的每个事务，利用迭代 交集法找出所有事务中包含的最大频繁项集，得到若干最大频繁项集集合；

由于炒作微博事务库中每个事务包含的项目大都数以万计，直接在原始事务数据库中挖 掘最大频繁项集将会影响算法执行的效率，利用二分查找法，快速剔除事务中的非频繁项目， 找出最大频繁项集的候选集合，缩减事务数据库规模；

(4)最大频繁项集归并：对每个最大频繁项集，计算项集间的重叠率，对最大频繁项集 进行合并，尽量将规模较小的项集归并到较大项集中，并保证归并后项集中的账户依然具有 一定的关联性；通过缩减事务数据库规模，减少交集次数，事务间取交集时，采用二分查找 法判断事务中是否包含某项目，以提高挖掘最大频繁项集的效率，从而发现微博炒作群体。

本发明方法简单，易操作，能准确发现恶意微博炒作群体，防止给社会造成的不良影响 和不必要的经济损失，具有实际的应用价值。

附图说明

图1为本发明流程框示图。

图2为本发明的炒作微博事务数据库示意图。

图3为本发明炒作微博事务数据库截图。

图4为本发明算法在Mushroom数据集上执行时间对比图。

图5为本发明算法在炒作微博数据集上执行时间对比图。

图6为本发明MFS中项集个数变化图。

图7为本发明MFS中项集的最大长度变化图。

具体实施方式

以下结合附图对本发明的具体实施方式作详细说明。

由图1给出，本发明包括炒作微博事务库、最大频繁项集挖掘以及最大频繁项集归并部 分，炒作微博事务库构建模块主要负责采集数据并进行预处理，构建事务数据库D；最大频 繁项集挖掘模块首先基于二分查找方法筛选候选最大频繁项集，然后基于迭代交集方法从事 务数据库D中挖掘出最大频繁项集MFS；最大频繁项集归并模块主要对MFS进行归并处理， 以尽可能还原真实的炒作群体，具体步骤是：

1)、搜集炒作微博样本

炒作微博样本搜集实现本发明的最初步骤，微博样本的选择应具有相关性，若某个炒作 账户曾经参与的若干微博，或与某个主题相关的若干微博，微博样本的判定应借鉴已有的成 熟判别方法或专家系统，炒作微博样本搜集有两种方法：一种方法是选择爬虫技术，从微博 网页下载网页、解析页面结构并提取微博传播账户的信息；另一种方法是调用微博公共开放 平台，调用微博官方对外提供的API函数获取微博传播账户的信息，为了有利于对炒作群体 的发现，在选取炒作微博样本时还应遵循以下原则：

a、选取转发数相对较高的热门微博；

b、微博发布时间跨度<180天；

按照待挖掘炒作账户的算法分析条件，样本搜集的内容应包括微博标识号、微博账户标 识号、微博账户的基本信息；

2)构建事务数据库

将炒作群体发现问题转化为数据挖掘中的最大频繁项集挖掘，在炒作微博样本搜集的基 础上，将炒作微博对应事务，参与微博转发的账户对应事务中的项，构建事务数据库，如图 2所示；

3)基于二分查找的候选最大频繁项集筛选

由于炒作微博事务库中每个事务包含的项目大都数以万计，直接在原始事务库中挖掘最 大频繁项集将会影响算法执行的效率，基于二分查找的方法，能够快速剔除事务中的非频繁 项目，找出最大频繁项集的候选集合，缩减事务库规模，给定事务数据库D，最小支持数S， 进行候选最大频繁项集筛选，方法是：

(1)将事务库D中的事务按项目个数从大到小排序

(2)记频繁项目集合，非频繁项目集合；从i＝1开始，按顺序遍历D中 的每个事务T_i(1≤i≤|D|)，对事务T_i中的每个项目u：

a)若u∈FI，则保留u；

b)若u∈NFI，则从T_i中剔除u；

c)若，则转到下一步判断u是否是频繁项目；

(3)、从j＝i+1开始遍历剩余的事务，并利用二分查找法判断T_j，i<j≤|D|中是否包含u， 终止条件为：

a)当包含u的事务个数达到S时，说明u是频繁项目，将u加入到FI中；

b)当剩余的事务个数与包含了u的事务个数之和小于S时，说明u是非频繁项目，从T_i中剔除u。若此时包含了u的事务个数大于1，说明u还出现在T_i之外的事务中，则将u加入 到NFI中；

(4)剔除完D中所有事务中的非频繁项目后，即可得到缩减后的事务库D₁；

4)基于迭代交集的最大频繁项集挖掘：

通过对事务迭代取交集的方式挖掘最大频繁项集，给定缩减后的事务库D₁，最小支持数 S，最大频繁项集挖掘的方法如下：

(1)将事务库D₁中的事务按项的个数从大到小排序，以尽早发现最大频繁项集，为缩 减事务库规模，合并事务库中重复的事务，并对事务个数计数；

(2)为减少取交集的次数，对于事务T_i，1≤i≤|D₁|-S+1，从i＝1开始，首先找出包含了T_i中任意项的事务集合，T_j|T_j至少包含了Ti中的一个项目；j>i)，T_i依次与T_j取交集，将两者 的交集移入新的事务库D₂，同时剔除T_j，；

(3)对于新事务库D₂中的事务T，如果T是由不小于S个事务取交集而得，则将T移 入最大频繁候选项集集合MFCS中，同时剔除T在D₂中的子事务；

(4)如果新事务库D₂中的剩余事务个数小于S，则结束对事务库D₂的处理，返回到上 层事务库；否则，对D₂从第1步开始再进行此过程；

(5)当事务库D₁中剩余的事务数小于S时，即i>|D₁|-S+1，结束对当前事务库D₁的处 理；

(6)对MFCS中的项集进行合并同时剔除非最大频繁项集，最后的结果即为所求的最 大频繁项集集合MFS；

5)最大频繁项集归并：

由于最小支持数的限制，使得MFS中最大频繁项集规模较小，而且有些项集之间存在大 量的重叠项，这些项集代表的账户群很可能从属于同一个炒作群体，为解决这一问题，使用 重叠率来反映两个项集之间的相似性，设项集X₁,X₂∈MFS，将X₁和X₂的重叠率记为：

$\mathrm{ORate}(X_1,X_2)=\frac{|X_1\cap X_2|}{\mathrm{Min}\left(\right|X_1|,|X_2\left|\right)}$

上式中，|X₁∩X₂|表示X₁与X₂重叠项目的个数，Min(|X₁|,|X₂|)表示规模较小的项集中 项目的个数，项集归并的方法是：

(1)将MFS中的最大频繁项集按项目的个数从大到小排序；

(2)遍历MFS中的每个最大频繁项集，从i＝1开始，对，若 ORate(X_i,X_j)≥minOR，i<j≤|MFS|，则将X_i和X_j的并集添加到新的集合MMFS中，同时剔 除X_j；

(3)对MMFS中的项集重复执行以上两个步骤；

(4)当MMFS中任意两个项集的重叠率小于minOR时，结束。

本发明方法简单，易操作，并经实际试用，表明方法稳定可靠，具有实际的应用价值， 有关资料如下：

1)数据集

以新浪微博作为研究平台，以81条具有炒作嫌疑的微博为研究对象，实际参与其转发的 账户数量为380,726(不含多次参与转发的账户)，平均每条事务的项目个数为6,286，这些微 博大多属于广告营销类，有可能存在多个炒作群体参与其传播过程。利用爬虫程序爬取参与 这些微博转发的所有账户标识(UID)，并存储到事务数据库中，部分数据的格式如图3所示。

为了验证本发明所述算法(以下简称IIA)应用于最大频繁项集挖掘的效率，对经典的 Mushroom数据集进行性能测试，并与已知方法进行比较。该数据集包含了8,124条记录，每 条记录有23个项，记录了蘑菇的23个属性。

2)性能评估

首先对本发明所述方法的性能进行评估，实验环境为4G内存、2.0GHz双核Duo T5800 CPU、Windows732位操作系统，用Java实现该算法，并分别与经典的MAFIA算法和DFMFI 算法进行比较。

图4为三种算法在Mushroom数据集中不同支持度下的执行情况，可以看出本方法的效 率明显高于其它两种算法，即使在最小支持度很低的情况下执行效率也有优势。图5为三种 算法在炒作微博数据集上执行情况，可以看出本方法的执行效率最高。

3)参数阈值选择

图6、图7为在不同最小支持数下从炒作微博数据集中发现的最大频繁项集结果，图6 和图7分别表示最大频繁项集中项集个数和最大频繁项集中项集的最大长度随最小支持数的 变化。结合本发明研究背景可以发现，minSup(最小支持数)设定的越大，发现的账户群体 炒作嫌疑越大，但群体规模和数量也会随之减小；反之，minSup设定的越小，发现的账户群 体炒作嫌疑越小，但群体规模和数量会增大。为此，需要给minSup设定一个合理的阈值，以 发现具有一定规模且炒作嫌疑较高的群体。

另一方面，在对最大频繁项集中的项集进行归并时，minOR的设定也将直接影响合并后 项集的规模。通过对数据的不断分析，将minOR设定为50％，即当两个项集超过一半的项目 相同时将其合并。

为了进一步确定minSup的取值，表1分别列出了minSup＝3,4,5时对最大频繁项集归并 后的结果，按归并后项集长度排序，这里仅列出了前8个项集(疑似炒作群体)。从表中可以 看出，当minSup＝3和5时，除了第一个项集规模很大外，其它项集规模都很小；而当minSup＝4 时，项集规模并没有急剧变化，且规模适当，说明取值相对合理。。

表1不同支持数下最大频繁项集归并结果

序号 minSup＝3 minSup＝4 minSup＝5 1 14,863 2,623 963 2 311 1,755 65 3 156 688 29 4 77 410 19 5 59 129 9

6 56 98 9 7 55 82 7 8 55 54 5

4)准确率分析

为了验证本发明所述炒作群体发现算法的准确率，即发现的炒作群体中实际炒作账户所 占比例，结合已有基于多特征分析的炒作账户识别方法和人工标注方法综合验证结果的准确 率。假设待验证的炒作群体为H，首先利用已有基于多特征分析的炒作账户识别方法对每个 账户进行判别，得到的炒作账户集合记为H₁；然后，采用人工标注的方法对剩余的账户进行 判别，得到的炒作账户集合记为H₂，炒作群体H的准确率计算公式为：

$\mathrm{Precision}=\frac{\left|H_1\right|+\left|H_2\right|}{\left|H\right|}\times 100\%---\left(1\right)$

上式中，|H|表示H中的账户总数，|H₁|+|H₂|表示H中实际的炒作账户数。对表1中 minSup＝4且群体规模(即项集长度)大于100的部分群体进行验证，具体结果如表2所示。

表2炒作群体发现的准确率(minSup＝4)

序号 |H₁| |H₂| |H| Precision 1 2,016 451 2,623 94.1％ 2 1,465 163 1,755 92.8％ 3 571 78 688 94.3％ 4 354 33 410 94.4％ 5 109 10 129 92.2％

从表2中可以看到，对于本方法发现的每一个炒作群体，实际炒作账户所占的比例都高 于90％，表明本方法能识别出更为隐蔽的炒作账户(即H₂)，而这些账户往往是一些偶尔参 与炒作但影响力巨大的炒作大号。由此可见，本发明具有实际的应用价值，经济和社会效益 巨大。