一种基于垂直分解的并行频繁闭序列挖掘方法

摘要

本发明提出一种基于垂直分解的并行频繁闭序列挖掘方法，属于数据挖掘领域，该方法采用序列求交的方式，缩短序列的长度，这相当于在竖直方向将原始序列分割成较短的序列；再从求交结果中选出K条差异度最大的序列，这又使得序列之间列数差异较大，两步均可缩短挖掘时间；本发明提出压缩频繁模式的观点，压缩模式的好处在于减小了频繁闭模式枚举范围，缩短挖掘时间，减小算法的时间复杂度；本发明采用现阶段最流行的并行框架Hadoop实现频繁闭序列挖掘算法；充分利用Hadoop的并行特点，将海量数据分散存储到集群中的各个节点上，按照map函数、reduce函数的特点编写算法，因为枚举出的模式独立的分发到不同节点进行检测封闭性，因此本方法获得较高的加速比。

主权项

一种基于垂直分解的并行频繁闭序列挖掘方法，其特征在于，包括以下步骤：步骤1、对原始数据库扫描，将数据按行进行水平分片处理，并分别发送至不同的处理器中；步骤2、对每个处理器中的数据进行垂直分解；具体为：在每个处理器上，并行执行以下操作：执行一条数据与数据集中的所有数据进行两两相交，获得任意两条数据之间的公共子序列，即候选模式集；步骤3、将获得的所有公共子序列进行合并和去重操作，得到挖掘前的候选模式集；步骤4、将挖掘前的候选模式集中的序列转变成图的存储结构，图中每个结点代表一个序列；步骤5、采用基于独立支配集约减算法对图存储结构中的序列进行约减，将所有处理器中保存的集合进行合并；步骤6、采用基于阈值约减算法在合并后的集合进行约减操作，选取最具代表性的K个模式，即TopK，实现频繁模式的压缩；步骤7、挖掘约减后序列中的频繁闭序列，具体步骤如下：步骤7‑1、将步骤6获得的所有序列分配到每台处理器中；步骤7‑2、在每台处理器中，枚举固定长度的前缀序列；具体为：设置序列的前缀固定长度范围，所述的范围为：1～最长序列长度值，且固定长度为整数；在设置的长度范围内依次取前缀固定长度值，由第一条序列至最后一条序列，由左向右依次枚举，获得所有固定长度所对应的前缀序列；步骤7‑3、判断所获得的前缀序列是否包含在处理器的数据集中，若是，则将该前缀序列放入至自身投影数据库中；否则执行下一条前缀序列的判断；步骤7‑4、将所有处理器中相同前缀序列所对应的投影数据库进行合并，存储于同一个处理器中；步骤7‑5、依次判断每个前缀序列是否为频繁序列，若是，则执行步骤7‑6，否则，削减该前缀序列，并执行步骤7‑7；步骤7‑6、通过回插检测和向后扩展测，判断该前缀序列是否为频繁闭序列，若是，则保留此频繁闭序列，否则，削减该前缀序列；步骤7‑7、判断该序列是否能成片削减，若是，则执行成片削减，并返回执行步骤7‑5，否则，执行步骤7‑8；步骤7‑8、获得全部的频繁闭序列。