工业大数据背景下频繁项集挖掘算法对比分析及研究展望

邓靖秋

（四川大学计算机学院，成都610065）

0 引言

数据库中的知识发现（Knowledge Discovery in Databases，KDD）是指利用机器学习、模式识别、统计等领域的方法从大量数据中提取知识[1]，而这些知识并不是数据库结构中明确可用的，需要通过某些特殊处理后再进行提取。现今比较具有代表性的四种现代数据挖掘技术为：粗糙集理论（RST）、关联规则挖掘（ARM）、新兴模式挖掘（EP）以及形式概念分析（FCA）。这些方法的主要优点之一是它们的描述能力，即当用于派生规则时，在结构-活动关系中便具有了明确的物理意义。一般地进行大数据挖掘常用的关联规则挖掘技术，根据文献[2]描述为，假设有一个数据库D，第一步找出支持度大于或等于最小支持度（minsup）阈值的全部项集，从而得到所有的频繁项集；第二步通过从满足最小支持度阈值找出的频繁项集中挖掘大于或等于最小置信度（minconf）阈值的关联规则，从而得到强关联规则。其中满足最小支持度保证了挖掘的规则具有重要性，而满足最小置信度则保证挖掘规则的可靠性。

大数据（Big Data）指的是大容量的、复杂的、不断增长的、具有多个自主来源的数据集。随着网络、数据存储和数据采集能力的快速发展，大数据在物理、生物和生物医学等各科学工程领域迅速扩张，数据量呈指数增长[3-4]。围绕工业大数据研究并发现其内在价值变得尤为重要，现今工业大数据的5V 特性主要体现在：大容量（Volume）、多样性（Variety）、速度（Velocity）、价值（Value）、真实性（Veracity）[5]，尽管数据量极其丰富，但因为缺少有效的挖掘技术和分析工具从中提取有用的东西，工业大数据的内在价值现阶段也还未得到有效的体现。

1 频繁项集挖掘算法

考虑一个项的集合I。每条事务都有它唯一的标记符号，这个标记符记为TID，在给定的一个数据库表中，表中每一行对应交易中的一条事务，对事务T 来说，X 表示一个项集，如果有X⊆T，则表示事务T 中包含一个为X 的项。项集的支持度计数为发生该事件的事务数，即事务A、B 同时出现的频率，用数学公式表示为：Support（A==>B）=P（A n B），支持度（sup）是某事务所占比重重要性的衡量，而频繁项集为支持度至少满足某个阈值的所有项集。假设有如下数据库S 如表1，minsup 值人为设定为4。

表1 事务数据库S

则根据设定的最小支持度阈值4，统计数据库S 中各项支持度，过滤掉不满足sup=4 的事务项并按照支持度大小降序排序，得到如表2 满足的频繁1-项集，更新后的事务数据库S 如表2 所示。

表2 更新后数据库S

对于现今频繁项集挖掘算法来说，其开销主要在于产生所需的所有频繁项集，一般的挖掘频繁项算法包括：Apriori、FP-growth、Eclat、DHP、MBS、HBS、DIC[6]、Clique、dEclat、MaxEclat[7]等算法，其中文献[8]中提到的DHP 算法，利用Hash 修剪技术解决了对于在生成频繁k-项集时遇到的性能不佳问题，通过减少数据库事务的数据量，从而更高效地生成频繁项目集；文献[9]中提出的两种本文提出的两种新的算法MBS 和HBS 采用逆向思维通过有效地发现非频繁项之间的关联规则，同时也可以有效地挖掘有限长度频繁项之间的关联规则，两种算法也只需要遍历数据库两次，并且利用剪枝函数interest（X,Y）来显著减少搜索空间，使用interest度量correlation 相关性（X,Y）和CPIR（X,Y），从中提取感兴趣的规则；文献[10]提出一种最小生成树的聚类算法Partition，相似记录被聚合到包含K 个最小记录的组中，对于具有明显聚类效应的数据可以显著降低数据的信息损失从而加速k-项集的寻找过程；文献[11]提出一种在图形处理单元上并行化求解区间图最大组合的算法Clique；文献[12]提出了一种在对传统Elcat算法基础上，通过优化数据垂直结构，减轻项集迭代归一负担的dEclat 算法。据统计，现今采用的大部分频繁项集的挖掘算法中，Apriori 算法、FP-growth 算法、Eclat 算法仍是在求解关联规则挖掘问题上较为经典的三种算法。

1.1 Apriori算法

Apriori 算法是层次算法的经典算法之一，是Agrawal 和Srikant 于1994 年提出的，其主要是针对布尔关联规则的挖掘算法[13]，它作为层次算法的代表算法，采用一层一层搜索的策略，利用候选项集作为中间工厂，通过频繁k 项集生成频繁k+1 项集。Apriori 针对挖掘布尔型数据挖掘频繁项集，利用自底向上的方法，从挖掘频繁1-项集作为起点，根据上一层产生的序列逐步找出高阶频繁项集的过程。

该算法的基本流程是：第一次扫描给定数据库，记录每条事务中每个项出现的频数，将频数低于最小支持度阈值的单项集进行删除处理后整合剩下所有项集，产生频繁1-项集。在频繁1-项集的基础上进行连接操作生成2-候选项集，再对其修剪操作得到频繁2-项集，迭代上述过程直到不再产生更高阶的频繁项集即可结束，此时结果即挖掘出的所有频繁项集。

1.2 FP-growth算法

FP-growth 算法是Han 等人提出来的一种从事务集中挖掘频繁项集而不产生候选集的算法[14]。算法思路采用一棵FP 树存储数据库中的事务，对数据库扫描两次，在整个挖掘过程中采用递归策略迭代挖掘。算法过程大致分为两步：第一步，构造一颗FP 树；第二步，对第一步中构造出的FP 树进行递归操作，得到所有的频繁项结果集。

1.2.1 构建FP 树

（1）第一次扫描数据库，首先统计数据集中每个元素出现的频数，即计算每个元素支持度，剔除元素支持度小于minsup 值的元素，接着将数据集中的每条记录按照支持度大小进行降序排序，剩下的这些元素即为频繁1-项集列表F-List；

（2）对更新后的数据库第二次扫描，记录数据库中每条事务出现的项的顺序，根据记录结果创建一颗FP树，设树的根结点为null，若待增加的记录与FP 树中的路径相同时，只用更新该元素对应的频数，即将该元素结点频数相应加1，若待增加的记录与FP 树存在不相同时，则将该项添加到FP 树的一个分支当中，即新增一个新的结点。

1.2.2 挖掘FP 树

通过得到的FP 树，采用自底向上递归的思想，对每一个频繁项进行逐个挖掘，首先得到频繁项的前缀路径，将前缀路径看作新的数据集构建前缀路径的条件模式基（cpb），接着对该条件模式基中的某个频繁项又继续获得其前缀路径并构建新的条件模式基，以此不停迭代，直到条件模式基（cpb）中只剩下一个频繁项为止。

1.3 Eclat算法

根据文献[15]可知，Apriori 算法和FP-growth 算法都是以事务-项的格式，定义为：{TID:itemset}，一条事务对应一个或多个项，这种数据格式称为水平格式。而Eclat 算法则采用项-事务数据格式表示，一般定义为：{item:TIDset}，其中item 是项的名称，TIDset 是包含item 的事务标识符的集合，这种数据格式被称作垂直格式的数据集合。同时Eclat 中还加入了倒排的思想，将事务中的项item 作为key，每个项对应的事务TIDset作为value，数据表示清晰，算法执行过程中只需要对数据库扫描一次即可。

Eclat 算法基本流程表示为：通过扫描一次数据库改变数据格式。假设给定水平格式的数据库D，如表3。

表3 数据格式为水平结构的数据库D

转换数据格式为垂直格式，通过转换后的倒排表可加快频繁项集的生成速度，转换后的数据库D 如表4。

表4 数据格式为垂直结构的更改后的数据库D

接着从k=1 开始，可计算得到频繁1-项集如表5所示。

表5 频繁1-项集

通过取得频繁k-项集的TIDset 事务集的交集计算对应频繁（k+1）-项集的TIDset 事务集，每次k 的值增加1，则由频繁1-项集构造生成的频繁2-项集结果如表6 所示：

表6 频繁2-项集

继续由频繁2-项集构造频繁3-项集，频繁3-项集构造频繁4-项集，…，频繁k-项集构造频繁k+1 项集（k为正整数），直到最后结果不再产生频繁k-项集即可。

2 经典挖掘算法对比分析

通过对现今使用频率较高的三种经典频繁项集挖掘算法原理介绍，对于各自优缺点做如下对比分析，如表7。

表7 三类经典挖掘项集算法比较

3 基于工业大数据下挖掘关联信息分析研究

随着人工智能的发展，基于对工业大数据关联信息的挖掘成为广大科研人员研究的热点之一[16]，其主要任务是挖掘大数据集中潜在的有价值的关联关系以及动态数据中规则的变化规律，从而可以利用得到的知识反作用于数据，为事件发生做一些有效的预测和推断，这一举措在很多行业和领域都有着重大的研究意义和应用前景，例如工业大数据背景下，对机械生产质量管理问题的研究，通过挖掘生产中有关质量问题的关联信息，逆向补抓作用生产过程，有效地进行质量监控和管理，生产更多合格产品，从而提高生产效率。但在海量数据产生的今天，对于传统单机的关联规则挖掘算法在频繁项集挖掘步骤上耗时多且挖掘出的项集规模过于庞大，可能导致后期的关联规则挖掘无法进行。为解决这一问题，考虑结合现今通用的大数据框架，将传统的频繁项集挖掘算法移植运用到大数据并行化平台，利用并行的思想进行海量数据挖掘，同时对经典挖掘算法进行相应移植后的优化，提取出定量的有规律有意义的数据信息，有效提高大数据下海量数据挖掘的效率。

4 结语

基于工业大数据背景下的数据之间关联信息的挖掘，经典的三种挖掘算法在各自算法原理上都有一定的局限性，本文对其进行了特点分析，同时也对在工业大数据背景下如何快速、高效挖掘数据之间信息进行研究分析。通过减少候选项集数量，优化均衡分组，结合大数据框架并行挖掘从而得以实现。

本文研究的算法为传统单机频繁项集挖掘算法，但随着现今大数据时代的不断发展，数据量不断地扩展，产生的关联规则也随之增多，因此未来研究工作地重点可能主要包括：

（1）对于算法中生成大量候选项集的问题，采用对原始数据进行压缩的方法，如何对原始数据进行高效的压缩操作是未来研究的难点之一；

（2）设计更加优化的挖掘算法，将其移植到并行的大数据平台上，考虑移植后算法分组策略问题，从而有效解决负载均衡问题；

（3）现今大部分挖掘算法采用以挖掘正的关联规则的思路进行挖掘，这将会产生过多的结果集，从实际工程项目出发，正确衡量正负结果比，当挖掘的正规则结果集过于庞大时，考虑从挖掘负的关联规则入手，将挖掘少量负关联规则反作用于正关联规则得到定量的规则结果集，同时如何对结果集进行划分归类也是一大难关；

（4）最小支持度minsup 阈值的设定存在一定的人为影响性，设计一种能够通过针对不同数据规模自动生成最优最小支持度阈值的算法帮助在规则挖掘中等到更有效的信息；

（5）除了基本数据模式的挖掘算法研究之外，多层次的、多维度的挖掘算法也需要移植到并行化数据平台进行实行，同时现今的挖掘的需求不仅仅局限于对文本数据集的挖掘，视频、图像、音频等数据类型也将会成为今后关联挖掘的研究内容，如何对这种繁琐的数据类型进行关联挖掘也将会成为一项重大的挑战。