一种基于分布式框架的舆情并行关联挖掘方法转让专利
申请号 : CN202110813202.8
文献号 : CN113254755B
文献日 : 2021-10-08
发明人 : 刘宇 , 彭艳兵 , 唐帅 , 李雪
申请人 : 南京烽火星空通信发展有限公司
摘要 :
权利要求 :
1.一种基于分布式框架的舆情并行关联挖掘方法,用于实现对各目标网络舆情文本的舆情数据挖掘,其特征在于,包括如下步骤:步骤A.分别针对各目标网络舆情文本执行分词操作,获得各目标网络舆情文本分别所对应的各个分词,然后进入步骤B;
步骤B.根据预设热词库,获得各目标网络舆情文本分别所对应的热度,筛选获得热度大于预设文本热度下限阈值的各个目标网络舆情文本,构成各个待处理目标网络舆情文本,然后进入步骤C;
步骤C.针对各待处理目标网络舆情文本,通过提取待处理目标网络舆情文本所对应频繁出现的分词作为各个频繁项,并结合各频繁项在待处理目标网络舆情文本中的位置进行排序,构成待处理目标网络舆情文本所对应的频繁项集,进而获得各待处理目标网络舆情文本分别所对应的频繁项集,然后进入步骤D;
步骤D.分别针对各待处理目标网络舆情文本所对应的频繁项集,按预设分区数N,基于滑动窗口针对频繁项集逐个频繁项滑动下、所获各位置滑动窗口分别对应一个分区,各分区分别包含对应位置滑动窗口中的各频繁项,获得该频繁项集所对应的N个分区,即获得各待处理目标网络舆情文本分别所对应的N个分区,然后进入步骤E;
步骤E.分别基于参数n=1、…、N,针对各待处理目标网络舆情文本所对应的第n分区,通过有序森林存储模式的构建,作为该各第n分区共同所对应第n汇总分区所对应的有序模式森林,进而获得各汇总分区分别所对应的有序模式森林,然后进入步骤F;
步骤F.基于各汇总分区分别所对应的有序模式森林,根据针对有序模式森林中树节点的深度路径搜索应用,通过后缀树的构建,获得各汇总分区分别所对应的各最大频繁候选项集,然后进入步骤G;
步骤G.针对各汇总分区分别所对应的各最大频繁候选项集,删除最大频繁候选项集中的冗余节点集合、低支持度节点集合,更新各汇总分区分别所对应的各最大频繁候选项集,然后进入步骤H;
步骤H.针对各汇总分区分别所对应的各最大频繁候选项集,执行降维操作,删除其中彼此之间构成子集的最大频繁候选项集,更新各汇总分区分别所对应的各最大频繁候选项集,然后进入步骤I;
步骤I.针对各汇总分区分别所对应的各最大频繁候选项集,通过预设置信度阈值、预设提升度阈值挖掘关键词,实现对各目标网络舆情文本的舆情数据挖掘。
2.根据权利要求1所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤C中,分别针对各个待处理目标网络舆情文本,执行如下步骤C1至步骤C3,获得各待处理目标网络舆情文本分别所对应的频繁项集;
步骤C1.获得待处理目标网络舆情文本所对应各不同分词分别出现的次数,并针对该各不同分词按其出现次数由高到低进行排序,然后进入步骤C2;
步骤C2.按公式 选取该各不同分词排序中的前A个不同分词,作为该待处理目标网络舆情文本所对应的各个频繁项,然后进入步骤C3;其中,a表示比例数,L表示该待处理目标网络舆情文本所对应各不同分词的数量;
步骤C3.获得各频繁项分别在该待处理目标网络舆情文本中最后一次出现的位置,并按此顺序,由各频繁项构成该待处理目标网络舆情文本所对应的频繁项集。
3.根据权利要求1所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤E包括如下步骤E1至步骤E6;
步骤E1.初始化参数n=1,并进入步骤E2;
步骤E2.针对各待处理目标网络舆情文本所对应的第n分区,统计其中各不同频繁项出现次数分别与其中最大频繁项出现次数的比值,作为各不同频繁项分别对应的热度,并进入步骤E3;
步骤E3.针对各待处理目标网络舆情文本所对应的第n分区,统计其中各不同频繁项出现次数分别与其中各不同频繁项出现总次数的比值,作为各不同频繁项分别对应的频率,并进入步骤E4;
步骤E4.选择所包含各频繁项的热度、频率分别均小于预设频繁项热度阈值、预设频繁项频率阈值,且所包含频繁项个数不小于预设分区频繁项数阈值的各第n分区,删除该各第n分区,然后进入步骤E5;
步骤E5.基于剩余各第n分区中的各频繁项,构建有序森林存储模式,作为第n汇总分区所对应的有序模式森林,然后进入步骤E6;
步骤E6.判断n是否等于N,是则即获得各汇总分区分别所对应的有序模式森林,并进入步骤F;否则针对n的值进行加1更新,并返回步骤E2。
4.根据权利要求3所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤E5包括如下步骤E5‑1至步骤E5‑3;
步骤E5‑1.基于剩余各第n分区中的各频繁项,统计其中各不同频繁项出现次数分别与其中各不同频繁项出现总次数的比值,作为各不同频繁项分别对应的二次频率,然后进入步骤E5‑2;
步骤E5‑2.分别针对剩余各第n分区,按二次频率由高至低顺序,针对第n分区中的各频繁项进行排序,进而更新剩余各第n分区中频繁项的排序,然后进入步骤E5‑3;
步骤E5‑3.创建、并基于根节点root,依次选择剩余各第n分区,并按所选分区中频繁项的排序,依次创建各频繁项分别对应的树节点,完成剩余各第n分区中各频繁项的有序森林存储模式,进而作为第n汇总分区所对应的有序模式森林,然后进入步骤E6。
5.根据权利要求1所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤F中,分别针对各汇总分区分别所对应的有序模式森林,执行如下步骤F1至步骤F3,获得各有序模式森林分别所对应的各最大频繁候选项集,即各汇总分区分别所对应的各最大频繁候选项集,然后进入步骤G;
步骤F1.获得有序模式森林中各树节点分别到对应根节点的跳数,并选择其中跳数大于预设跳数阈值的各个树节点,作为各个待处理节点,然后进入步骤F2;
步骤F2.分别针对各个待处理节点,基于该有序模式森林,在待处理节点位置进行深度路径搜索,获得该待处理节点到根节点的所有逆向搜索路径,构成该待处理节点所对应的后缀树,进而获得各待处理节点分别所对应的后缀树,然后进入步骤F3;
步骤F3.分别针对各个待处理节点,由待处理节点所对应后缀树中各路径的节点集合,作为以该待处理节点为结尾节点的各最大频繁候选项集,进而获得各待处理节点分别作为结尾节点的各最大频繁候选项集,即该有序模式森林所对应的各个最大频繁候选项集。
6.根据权利要求1所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤G中,分别针对各汇总分区,执行如下步骤G1至步骤G2,更新各汇总分区分别所对应的各最大频繁候选项集,然后进入步骤H;
步骤G1.提取汇总分区中各最大频繁候选项集所对应的各不同结尾节点,作为各个待处理结尾节点,然后进入步骤G2;
步骤G2.分别针对各个待处理结尾节点,删除待处理结尾节点所对应的冗余最大频繁候选项集、低支持度最大频繁候选项集,更新各待处理结尾节点分别所对应的各最大频繁候选项集,即更新该汇总分区所对应的各最大频繁候选项集。
7.根据权利要求6所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤G2中,分别针对各个待处理结尾节点,执行如下步骤G2‑1至步骤G2‑4,更新各待处理结尾节点分别所对应的各最大频繁候选项集,即更新该汇总分区所对应的各最大频繁候选项集;
步骤G2‑1.针对待处理结尾节点所对应的各最大频繁候选项集,统计其中各不同节点出现次数分别与其中各不同节点出现总次数的比值,作为该各不同节点分别对应的频率,并进入步骤G2‑2;
步骤G2‑2.分别针对该待处理结尾节点所对应的各最大频繁候选项集,按频率由大至小的顺序,针对最大频繁候选项集中的各节点进行排序,更新该最大频繁候选项集中的节点排序,即更新该待处理结尾节点所对应各最大频繁候选项集中的节点排序,然后进入步骤G2‑3;
步骤G2‑3.针对该待处理结尾节点所对应的各最大频繁候选项集进行比较,删除其中彼此间构成子集的各最大频繁候选项集,然后进入步骤G2‑4;
步骤G2‑4.针对该待处理结尾节点所对应剩余各最大频繁候选项集,删除其中出现次数不大于预设出现次数阈值的最大频繁候选项集,更新该待处理结尾节点所对应的各最大频繁候选项集,即更新该待处理结尾节点所对应的最大频繁候选项集。
8.根据权利要求1所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤B中,分别针对各目标网络舆情文本,获得目标网络舆情文本中与预设热词库中词汇相同的分词的数量,并通过与该目标网络舆情文本中分词总数的比值,获得该目标网络舆情文本所对应的热度,进而获得各目标网络舆情文本分别所对应的热度。
9.根据权利要求1所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤A中,还包括分别删除各目标网络舆情文本所对应分词中的各个连词,更新各目标网络舆情文本分别所对应的各个分词,然后进入步骤B。
10.根据权利要求1所述一种基于分布式框架的舆情并行关联挖掘方法,其特征在于:所述步骤I包括如下步骤I1至步骤I2;
步骤I1.分别针对各汇总分区所对应各最大频繁候选项集,作为待处理最大频繁候选项集,执行如下步骤I1‑1至步骤I,获得各待处理最大频繁候选项集分别对应的置信度、提升度,即获得各最大频繁候选项集分别对应的置信度、提升度,然后进入步骤I2;
步骤I1‑1.分别针对各其余最大频繁候选项集,根据待处理最大频繁候选项集所在全部各汇总分区中包含其余最大频繁候选项集的比例,构成待处理最大频繁候选项集到该其余最大频繁候选项集的置信度,进而获得待处理最大频繁候选项集分别到各其余最大频繁候选项集的置信度,并通过平均值法,获得待处理最大频繁候选项集的置信度,然后进入步骤I1‑2;
步骤I1‑2.分别针对各其余最大频繁候选项集,根据待处理最大频繁候选项集所在全部各汇总分区中其余最大频繁候选项集出现概率、与全部最大频繁候选项集中该其余最大频繁候选项集出现概率的比值,构成待处理最大频繁候选项集对应该其余最大频繁候选项集的提升度,并通过平均值法,获得待处理最大频繁候选项集的提升度;
步骤I2.删除置信度、提升度分别均小于预设置信度阈值、预设提升度阈值的最大频繁候选项集,保留剩余各最大频繁候选项集,则剩余各最大频繁候选项集中的各频繁项均为所挖掘的关键词,实现对各目标网络舆情文本的舆情数据挖掘。
说明书 :
一种基于分布式框架的舆情并行关联挖掘方法
技术领域
背景技术
多民众关于社会中各种现象、问题所表达的信念、态度、意见和情绪等等表现的总和。网络
舆情形成迅速,对社会影响巨大。传统的社会舆情存在于民间,存在于大众的思想观念和日
常的街头巷尾的议论之中,前者难以捕捉,后者稍纵即逝,舆情的获取只能通过社会明察暗
访、民意调查等方式进行,获取效率低下,样本少而且容易流于偏颇,耗费巨大。而随着互联
网的发展,大众往往以信息化的方式发表各自看法,网络舆情可以采用 Apriori 数据挖掘
算法技术自动抓取目标数据,效率高而且信息保真,覆盖面全。
算法往往是有效的,然而随着数据集规模的增加,算法的效率也将下降。MapReduce方法使
关联规则的挖掘过程非常快,许多基于MapReduce的关联规则算法陆续被提出,与传统方法
相比,这些算法显示出较好的性能但仍存在一些局限性。由于频繁模式的反单调性,一个频
繁模式包含很多频繁子模式,而一个频繁模式也能到处多个关联规则,因此关联规则数量
巨大、且存在多个规则蕴含同个目标项目的情况广泛存在。
对舆情频繁项进行挖掘时多容易产生巨大的冗余项集,算法效率大大降低。许多基于群集
的并行算法能够处理大型数据集,但也带来诸如复杂性、数据同步、数据复制等许多问题,
且大多数的数据挖掘算法都是基于内存迭代式的,每次迭代后的中间结果需要单独存储作
为下一次迭代的输入,存在算法性能下降、并行化程度和效率低下等一系列问题。
发明内容
提高数据挖掘的工作效率。
下步骤:
文本,然后进入步骤C;
置进行排序,构成待处理目标网络舆情文本所对应的频繁项集,进而获得各待处理目标网
络舆情文本分别所对应的频繁项集,然后进入步骤D;
区,各分区分别包含对应位置滑动窗口中的各频繁项,获得该频繁项集所对应的 个分区,
即获得各待处理目标网络舆情文本分别所对应的 个分区,然后进入步骤E;
获得各汇总分区分别所对应的有序模式森林,然后进入步骤F;
繁候选项集,然后进入步骤G;
选项集,然后进入步骤H;
选项集,然后进入步骤I;
集;
表示该待处理目标网络舆情文本所对应各不同分词的数量, 表示向上取整;
度,并进入步骤E3;
频率,并进入步骤E4;
除该各第 分区,然后进入步骤E5;
后进入步骤E5‑2;
有序森林存储模式,进而作为第 汇总分区所对应的有序模式森林,然后进入步骤E6。
繁候选项集,即各汇总分区分别所对应的各最大频繁候选项集,然后进入步骤G;
对应的后缀树,进而获得各待处理节点分别所对应的后缀树,然后进入步骤F3;
别作为结尾节点的各最大频繁候选项集,即该有序模式森林所对应的各个最大频繁候选项
集。
频繁候选项集,即更新该汇总分区所对应的各最大频繁候选项集。
集,即更新该汇总分区所对应的各最大频繁候选项集;
率,并进入步骤G2‑2;
的节点排序,即更新该待处理结尾节点所对应各最大频繁候选项集中的节点排序,然后进
入步骤G2‑3;
最大频繁候选项集,即更新该待处理结尾节点所对应的最大频繁候选项集。
情文本中分词总数的比值,获得该目标网络舆情文本所对应的热度,进而获得各目标网络
舆情文本分别所对应的热度。
入步骤B。
度、提升度,即获得各最大频繁候选项集分别对应的置信度、提升度,然后进入步骤I2;
该其余最大频繁候选项集的置信度,进而获得待处理最大频繁候选项集分别到各其余最大
频繁候选项集的置信度,并通过平均值法,获得待处理最大频繁候选项集的置信度,然后进
入步骤I1‑2;
最大频繁候选项集出现概率的比值,构成待处理最大频繁候选项集对应该其余最大频繁候
选项集的提升度,并通过平均值法,获得待处理最大频繁候选项集的提升度;
项均为所挖掘的关键词,实现对各目标网络舆情文本的舆情数据挖掘。
架,解决面向大规模高维舆情数据的频繁项挖掘问题,并针对传统算法的并行化策略进行
优化,结合了Spark的分布式框架和DMFIA(最大频繁项集挖掘算法)的优点,首先将各目标
网络舆情文本进行划分投影,对每条目标网络舆情文本生成频繁项集,接着基于分区划分,
设计有序模式森林,用于压缩存储舆情频繁模式;然后基于舆情频繁模式,提出深度路径搜
索和长度优先超集检验,进行深度路径递归搜索生成最大舆情频繁候选项集,对舆情候选
项集进行长度优先排序并检验超集,降低舆情候选项集的规模和挖掘次数,解决传统最大
频繁项集挖掘算法在数据量大、维度高时效率低的问题,且对数据集规模具有良好的扩展
性。
附图说明
具体实施方式
目标网络舆情文本分别所对应的各个分词,并进入步骤B。
文本,然后进入步骤C。
与该目标网络舆情文本中分词总数的比值,获得该目标网络舆情文本所对应的热度,进而
获得各目标网络舆情文本分别所对应的热度。
置进行排序,构成待处理目标网络舆情文本所对应的频繁项集,进而获得各待处理目标网
络舆情文本分别所对应的频繁项集,然后进入步骤D。
表示该待处理目标网络舆情文本所对应各不同分词的数量, 表示向上取整。
区,各分区分别包含对应位置滑动窗口中的各频繁项,获得该频繁项集所对应的 个分区,
即获得各待处理目标网络舆情文本分别所对应的 个分区,然后进入步骤E。
获得各汇总分区分别所对应的有序模式森林,然后进入步骤F。
度,并进入步骤E3。
频率,并进入步骤E4。
除该各第 分区,然后进入步骤E5。
后进入步骤E5‑2。
有序森林存储模式,进而作为第 汇总分区所对应的有序模式森林,然后进入步骤E6。
b,c,d,e,f,m,n,h,k,q分别为频繁项),统计此全部第1分区中各频繁项出现频率,即b:5,a:
3,c:3,d:3,e:1,f:1,m:1,n:1,h:1,l:1,k:1,q:1,然后选择所包含各频繁项的热度、频率分
别均小于20%,且所包含频繁项个数不小于2的各第1分区,删除该各第1分区,执行删除后,
剩余各第1分区如下:[a,b,d], [a,b,c],[c,d,e,l],[b,a,c,d], [b,e,f],下面基于剩余
各第1分区构建森林存储频繁模式,构建过程如下:针对第一条记录[a,b,d],按照频率由大
至小排序后的顺序可调整为[b,a,d],首先创建跟节点root,依次在树中添加节点b,a,d,然
后处理第二条记录[a,b,c],同样按照频率排序后的顺序可调整为[b,a,c],之后对第三条
记录进行添加[c,d,e,l],依次添加,过程如图2所示。
项的频繁模式。同时,FP‑growth自底向上的遍历方式使得挖掘出的每个频繁模式遵循
FList偏序关系。类于FP树可以对每条舆情文本记录进行压缩存储一样,此处提出一种树型
结构压缩存储频繁模式。由于频繁模式分布式存储于不同分区中舆情子集列表中的n个节
点,这种树型结构本质上是一个森林,称为有序模式森林,定义如下:有序模式森林
(Ordered‑Patterns Forest,OPF)。有序模式森林由多棵多叉树组成,每个多叉树的节点包
含四个域:item、child_list、parent和statinfo,分别对应项目名称、孩子节点、父亲节点
与用于推荐计算的统计量。
的统计量,参与推荐分值的计算。如下算法1给出了构建有序模式森林的伪代码,其中虚根
节点 用来保存指向多叉树根节点的指针。
尾项代表一条模式,相比于FIG(频繁项集图)极大地降低了存储空间。
繁候选项集,然后进入步骤G。
汇总分区分别所对应的各最大频繁候选项集,然后进入步骤G。
对应的后缀树,进而获得各待处理节点分别所对应的后缀树,然后进入步骤F3。
别作为结尾节点的各最大频繁候选项集,即该有序模式森林所对应的各个最大频繁候选项
集。
(Item,suffixTree)进行深度路径搜索,基于有序模式森林中各树节点分别到对应根节点
的跳数Item.Count,如果Item.Count大于预设跳数阈值minCount,则递归构建子树搜索,最
终形成每一条路径都是叶子节点到根节点的逆向最长路径,所有的路径均以该树节点为结
尾节点的最大频繁候选项集(prefix‑MFICS)。本发明中采用并行生成舆情文本频繁候选
集,先对生成树递归进行最长路径搜索,诸如针对以第1汇总分区为例,对满足第1汇总分区
的频繁项(步骤二中的每个树节点a,b,c,d等),设置阈值预设跳数阈值mincount,对有序模
式森林中的节点item(a,b,c,d,e等),若item.count>mincount,则在节点item处进行深度
路径搜索,最终形成每一条路径都是叶子节点到根节点的逆向搜索路径,在该分区中形成
多个后缀树,后缀树中的所有路径组成以该item为结尾的最大频繁候选项集。此案例中最
大频繁候选项集有(a,b,c),(b,c),(a,c),诸如图4所示。
作,所以是在多个机器上分布式处理。SMFI算法整体伪代码如下:
选项集,然后进入步骤H。
频繁候选项集,即更新该汇总分区所对应的各最大频繁候选项集。
应的各最大频繁候选项集。
率,并进入步骤G2‑2。
的节点排序,即更新该待处理结尾节点所对应各最大频繁候选项集中的节点排序,然后进
入步骤G2‑3。
最大频繁候选项集,即更新该待处理结尾节点所对应的最大频繁候选项集,此步骤的应用,
诸如该汇总分区中最大频繁候选项集[a,b,c],[c,d,e]都出现了10次,但最大频繁候选项
集[m,n,l]只出现了一次,则可删除[m,n,l]。
为(c,a),(c,b),(c,a,b)。从排序后的结果显而易见(c,a),(c,b)为(c,a,b)的子集,(c,a),
(c,b)为冗余项,可删除,最大频繁项集为(c,a,b),若(c,a,b)大于设定的支持度阈值,则可
保留,此方法提高运行效率。(注:同一分区中有多个符合阈值的节点,故会产生多个后缀
树,则会有多个候选项集合)。
选项集,然后进入步骤I。此步骤的应用,诸如[a,b,c,d,e,f,g,h,l]为最大频繁候选项集,
则对存在能够作为子集的[a,b,c,d,e,f],[b,c,d]等最大频繁候选项集,既可以进行删除
操作。
度、提升度,即获得各最大频繁候选项集分别对应的置信度、提升度,然后进入步骤I2。
该其余最大频繁候选项集的置信度,进而获得待处理最大频繁候选项集分别到各其余最大
频繁候选项集的置信度,并通过平均值法,获得待处理最大频繁候选项集的置信度,然后进
入步骤I1‑2。
最大频繁候选项集出现概率的比值,构成待处理最大频繁候选项集对应该其余最大频繁候
选项集的提升度,并通过平均值法,获得待处理最大频繁候选项集的提升度。
项均为所挖掘的关键词,实现对各目标网络舆情文本的舆情数据挖掘。
题,并针对传统算法的并行化策略进行优化,结合了Spark的分布式框架和DMFIA(最大频繁
项集挖掘算法)的优点,首先将各目标网络舆情文本进行划分投影,对每条目标网络舆情文
本生成频繁项集,接着基于分区划分,设计有序模式森林,用于压缩存储舆情频繁模式;然
后基于舆情频繁模式,提出深度路径搜索和长度优先超集检验,进行深度路径递归搜索生
成最大舆情频繁候选项集,对舆情候选项集进行长度优先排序并检验超集,降低舆情候选
项集的规模和挖掘次数,解决传统最大频繁项集挖掘算法在数据量大、维度高时效率低的
问题,且对数据集规模具有良好的扩展性。
做出各种变化。