基于Apriori数据挖掘算法的网络舆情信息索引研究
高 宾 王兰成
（国防大学政治学院军事信息与网络舆论系 上海 200433）
摘 要 Apriori算法是一种极有影响力的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段频集思想的递推算法，该算法是挖掘产生布尔关联规则频繁项目集的经典算法，从其产生到现在对关联规则挖掘方面的研究有着很大的影响。当前，随着网络信息技术的快速发展，将Apriori数据挖掘算法与网络舆情信息索引结合，对于网络舆情信息的精准检索、准确定位、实时修正、准确引导等环节，都将产生极为广泛而深刻的影响。
关键词 数据挖掘 网络舆情 信息索引
一、Apriori数据挖掘算法的关联规则
Apriori算法是一种极有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段频集思想的递推算法，该关联规则在分类上属于单维、单层、布尔关联规则。
由国际权威学术组织International Conference on Data Mining①（简称ICDM）评选出的十大数据挖掘领域经典算法中，就有 Apriori 数据挖掘算法的身影。Apriori算法是由Agrawal等人提出的经典的关联规则和频繁项集挖掘算法，围绕着它的改进和实现有大量的文献。该算法是挖掘产生布尔关联规则频繁项目集的经典算法，从其产生到现在对关联规则挖掘方面的研究有着很大的影响。当前，随着网络信息技术的快速发展，Apriori数据挖掘算法在网络舆情领域同样产生了极为广泛而深刻的影响。
如果用一个简单的例子来说明Apriori数据挖掘算法的关联规则和基本原理，那么在市场营销中的“尿布与啤酒”现象，①就是一个再恰当不过的案例了。在美国中西部的一家连锁店中，市场营销人员发现，尿布经常会和啤酒一同被购买，然后就对这一奇怪的现象做了一番调查，发现原来男人们在购买尿布的同时会顺便购买啤酒，或者说男人们在定期购买啤酒的同时会顺便购买婴儿经常用的尿布。因此，市场营销人员脑洞大开，及时调整货架和物品的摆放顺序，将尿布与啤酒放在一起，最终获得了更大的收益，这就是发生在现实生活中的一个典型的关联分析的例子。其中，关联分析是指从大规模数据集中寻找物品间的隐含关系的一种方法。② 寻找物品间的隐含关系，或寻找物品的不同组合，是一项很耗时的任务，所需的计算代价很大，通过普通的人工搜索方法并不能解决这个问题，所以需要用更高效的方法在合理的时间内找到频繁项集，即经常出现在一起的物品组成的集合。而Apriori算法恰好是解决上述类似问题的一种智能高效的算法。
Apriori算法适用于关联分析——发现大数据集中元素间的有趣关系。这种关系分为两种形式：频繁项集和关联规则。频繁项集是指经常出现在一起的事物组合的集合；关联规则是指两种或多种事物之间可能存在很强的关系，即某些事物的出现很大可能会导致其他事物的高频发生。例如在上述案例中，人们日常购物的集合{洗衣液，啤酒，尿布}就是一个频繁项集，尿布→啤酒就是一个关联规则，这意味着如果有人买了尿布，那么他很有可能还会买啤酒。使用频繁项集和关联规则，商家可以更好地理解顾客的行为并获得更大的利益。在利用Apriori数据挖掘算法开展研究中，还牵涉到了两个重要的概念：支持度和可信度。
支持度是针对频繁项集定义的，一个项集的支持度是指数据集中包含该项集的记录所占的比例。假设{啤酒}的支持度为4/5, {啤酒，尿布}的支持度为3/5，因此，可以定义一个最小支持度，只要满足最小支持度的项集就被称为频繁项集。可信度是针对关联规则定义的，“尿布→啤酒”这一关联规则的可信度被定义为“支持度（{尿布，啤酒}）/支持度（{尿布}）”。已知{尿布}的支持度为4/5, {尿布，啤酒}的支持度为3/5，所以“尿布→啤酒”的可信度为3/4=75%。这就意味着对于包含“尿布”的所有记录，我们的规则对其中的75%的记录都适用。以此类推，我们就可以定义一个最小可信度，那么只有满足最小可信度被称为关联规则。
我们知道对于包含N种物品的数据集共有2^N-1种项集组合。① 随着物品数目的增加，项集组合的数目会急剧增长。如果计算每种项集的支持度和可信度，那将会十分耗时。为了降低计算时间，人们利用到了Apriori索引，如果某个项集是频繁的，那么它的所有子集也是频繁的，这个原理直观上并没有什么帮助，但是如果反过来看就会变得很有用，即如果一个项集是非频繁的，那么它的所有超集也是非频繁的，Aprior数据挖掘算法正是基于Apriori原理得到的。
二、基于Apriori算法的网络舆情信息索引
网络舆情②是指在一定的时间空间内，通过网络围绕中介性社会事件的发生、发展和变化，民众对公共问题和社会管理者产生和持有的社会政治态度、信念和价值观。它是较多民众关于社会中各种现象、问题所表达的信念、态度、意见和情绪等等表现的总和。网络舆情形成迅速，对社会影响巨大。随着因特网在全球范围内的飞速发展，网络媒体已被公认为是继报纸、广播、电视之后的“第四媒体”，网络成为反映社会舆情的主要载体之一，网络舆情是社会舆情在互联网空间的映射，是社会舆情的直接反映。传统的社会舆情存在于民间，存在于大众的思想观念和日常的街头巷尾的议论之中，前者难以捕捉，后者稍纵即逝，舆情的获取只能通过社会明察暗访、民意调查等方式进行，获取效率低下，样本少而且容易流于偏颇，耗费巨大。而随着互联网的发展，大众往往以信息化的方式发表各自看法，网络舆情可以采用Apriori数据挖掘算法技术自动抓取目标数据，效率高而且信息保真，覆盖面全。
网络舆情信息的一大特点是信息量大、更新迅速、实时变化，那么要在海量的网络信息中检索出目标信息，其难度可想而知。当前已有的网络舆情信息索引技术主要包括单体化技术与系统化技术两类，③但基本都存在检索效率低、准确度不高等问题。因此为了提高频繁项目的挖掘效率，基于Apriori数据挖掘算法技术有其独特的优势，其快速高效的检索方式、精准方便的指向性、压缩搜索的空间、先验频繁项等特点都为网络舆情信息的索引提供极大的便利性。Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索（k+1）项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，利用L2找L3，以此类推，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。
Apriori算法的具体处理流程为：
宽度优先搜索整个项集空间，从k=0开始，迭代产生长度为k+1的候选项集的集合Ck+1。候选项集是其所有子集都是频繁项集的项集。C1由I0中所有的项构成，在第k层产生所有长度为k+1的项集。这由两步完成：第一步，Fk自连接。将Fk中具有相同（k-1）-前缀的项集连接成长度为k的候选项集。第二步是剪枝，如果项集的所有长度为k的子集都在Fk中，该项集才能作为候选项集被加入Ck+1中。为了计算所有长度为k的候选项集的支持度，在数据库水平表示方式下，需要扫描数据库一遍。在每次扫描中，对数据库中的每条交易记录，为其中所包含的所有候选k-项集的支持度计数加1。所有频繁的k-项集被加入Fk中。此过程直至Ck+1等于空集时结束。
Apriori算法①：
Input: Transaction DataBase D, Minimum support threshold minsup
Output: Frequent pattern L
L1=search frequent 1-itemsets（D）；
for（k=2; Lk-1≠φ; k++）do
begin
Ck=apriori-gen（Lk-1）；
for all transactions t D do
begin
Ct=subset（Ck, t）；
for all candidates c Ct do
c.count++；
end
Lk ={c Ck|c.count≥minsup}
end
Answer L=∪kLk；
其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P（I）＜最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I出现次数更多。因此A∩I也不是频繁的。若有两个k-1项集，每个项集按照“属性-值”（一般按值）的字母顺序进行排序。如果两个k-1项集的前k-2个项相同，而最后一个项不同，则证明它们是可连接的，即这个k-1项集可以联姻，即可连接生成k项集。假如有两个3项集：{a, b, c}, {a, b, d}，这两个3项集就是可连接的，它们可以连接生成4项集{a, b, c, d}。又如两个3项集{a, b, c}, {a, d, e}，这两个3项集显示是不能连接生成3项集的。若一个项集的子集不是频繁项集，则该项集肯定也不是频繁项集。这个很好理解，举一个例子，若存在3项集{a, b, c}，如果它的2项子集{a, b}的支持度即同时出现的次数达不到阈值，则{a, b, c}同时出现的次数显然也是达不到阈值的。因此，若存在一个项集的子集不是频繁项集，那么该项集就应该被无情地舍弃，这种特性对于网络舆情索引来说无疑会提供较大的帮助。
三、基于Apriori数据挖掘算法的网络舆情信息索引实证
在网络舆情领域，所有的舆情事件都是由现实生活中的社会热点所引起。例如2012年8月的陕西延安特大交通事故，事件本事起因于一起死亡36人的特大交通事故，而这起事故引发广泛关注，却是由于陕西安监局长杨达才在事故现场的微笑门所致。也就在网友强烈谴责的同时，有网友“人肉”出杨达才佩戴的手表基本都是奢侈品，且价值不菲。至此，原本是一起交通事故的原始舆情，经过网友的“挖掘”、“爆料”，迅速从“微笑门”又衍化成“名表门”事件。随后有网友申请公开杨达才年度工资被拒，将网络舆情再一次推向了又一个高潮，然而这次的舆情已然衍生为官员的“贪腐门”。
图1 “8·26”延安特大交通事故示意图
“8·26”延安特大交通事故原本是单纯的交通事故，由于原始舆情不断被升级转变，衍变异化为政府官员的贪污受贿事件，最终以杨达才被撤职查办，受贿赃款上缴国库才得以收场。由特大交通事故引发事故舆情，受到广泛关注后，依次衍生出了“微笑门”、“名表门”和“贪腐门”。从网络舆情事件的传播过程也可以清晰地看出，由原始事件（特大交通事故）引发原始舆情之后，网络舆情的传播相对独立，互不干扰。
我们为了研究的方便，将网络舆情事件简化为：陕西延安特大交通事故→事件A1，同时将网络舆情根据类别简化为：交通事故→E0，政府作风→E1，贪污腐败→E2，司法公正→E5。依次类推一个时间段内的社会热点事件A1, A2, A3, A4, A5, A6, A7, A8, A9，可以依次用{E0, E1, E2, E5}, {E2, E4}, {E2, E3}, {E1, E2, E4}, {E1, E3}, {E2, E3}, {E1, E3}, {E1, E2, E3, E5}, {E1, E2, E3}来替代。① 如表1所示：
表1 网络舆情事件对应表
这种合并项集的方法有两大优势。第一，避免合并得到的项集重复并且减少计算量。假设需要把{E0, E1}, {0, E2}, {E1, E2}合并为三元素项集，如果将每两个集合合并，就会得到{E0, E1, E2}, {0, E1, E2}, {0, E1, E2}，即得到3个重复的结果。但是利用上述的合并规则只有{E0, E1}和{0,2}需要合并，只会得到一个{E0, E1, E2}。而且该合并规则只操作了1次合并，而普通的合并方法操作了3次。第二，从另一个方面减少计算量。在把k元素的项集合并为k+1元素的项集的过程，我们也可以比较两个项集中是否有k-1个元素相同，而不是前k-1个元素相同，如果相同，合并后的项集也是k个元素。但是这样会增加某些不频繁的项集。假设需要把{E0, E1}, {E1, E2}合并为三元素项集，如果按照这里的方法就会得到{E0, E1, E2}，按照上述的合并规则就会得到一个空集。其实{E0, E1, E2}一定是不频繁项集，是不需要进行支持度计算的，那么按照Apriori原理，{E0, E1, E2}一定不是频繁项集，从而大幅减少了计算量。
图2 “杨达才事件”网络舆情传播示意图
在Apriori数据挖掘过程中，每次合并项集之后，算法都会重新扫描整个数据集来找出合并后的项集中的频繁项集，当数据集很大时，都会大大提高频繁项集的发现速度，这是Apriori算法的一个优势所在。通过上述算法就可以找到所有的频繁项集，即网络舆情的下一步发展方向，然后利用这些频繁项集以及它们的支持度，就能挖掘出所有的关联规则。我们可以为每个频繁项集产生许多关联规则，同样，如果能够通过某种原理或方法减少关联规则的数目，那么就能够在合理的时间内找到所有的满足最小可信度的关联规则，这在网络舆情领域可以得到较好的应用。具体说来，就是通过Apriori算法逐一对每一种可能的舆情发展趋势进行计算排查，同时有效输入近期发生、发展的与此次舆情相关的数据，最终计算得出舆情发展的主要趋势和可能的结果；同时，在此过程中通过Apriori算法，可以较为容易地得到舆情事件的关联规则和每一趋向的支持度，这是Apriori算法在网络舆情领域的一大贡献，为网络信息的索引提供了较大的便利。
高 宾 国防大学政治学院图书情报与档案管理专业博士，研究方向：网络信息管理。
王兰成 国防大学政治学院军事信息与网络舆论系教授、博导，中国索引学会常务理事，研究方向：索引技术、数据库管理。
Research on the Index of Internet Public Opinion Information Based on Apriori Data Mining Algorithm
Gao Bin Wang Lancheng
Absrtact: The Apriori algorithm is very influential for mining frequent itemsets of boolean association rules.Its core is a recursive algorithm based on the idea of two-stage frequent itemsets.It has exerted great influence on the research of association rule mining.At present, with the rapid development of network information technology, the combination of Apriori data mining algorithm and network public opinion information index will widely and profoundly impact on the accurate retrieval, accurate positioning, real-time correction and so on.
Keywords: Data Mining; Internet Public Opinion; Information Index