论文部分内容阅读
摘要：为了解决数据挖掘中关联规则算法存在的缺陷，提出了一种全新的基于二叉树逐渐合并堆积原理的BT_CM全新算法。实际应用表明，改进后的算法具有操作简便、测试准确的特点，达到了提高数据挖掘效率和准确性的要求。
关键词：数据挖掘 关联规则 二叉树 BT_CM全新算法
1 数据挖掘简介
数据挖掘（Data Mining）[1]即“从数据中挖掘知识”，是目前数据库和人工智能领域研究的热点问题，所谓数据挖掘就是从大量数据中提取或“挖掘”知识。具体来说，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘是一种决策支持过程，它主要基于人工智能[2]、机器学习、模式识别、统计学、数据库、可视化技术等，高度自动化地分析企业的数据，做出归纳性的推理，从中挖掘出潜在的模式，帮助决策者调整市场策略，减少风险，做出正确的决策。数据挖掘在数据库领域使用最多。典型的数据挖掘系统由以下六部分组成： 数据库、数据仓库或其他信息库、数据库或数据仓库服务器、知识库、数据挖掘引擎、模式评估模块、图形用户界面。
2 BT_CM算法思路
针对原始Apriori算法[3]存在多次扫描数据库以及产生大量候选集的两大缺陷，提出一种基于二叉树逐渐合并堆积原理的BT_CM全新算法。新算法首先利用事务数据库中各单项产生对应的子集集合，并利用子集集合进而形成各单项子二叉树。其次可对产生的子二叉树进行剪树操作，剪树的原理是根据关联规则的目标是找出项集之间关联的缘故，将深度为1的树结点剪掉。紧接着将后产生的子二叉树合并到之前产生的树中，并累加统计得出树中分支的权重值（即分支出现的次数）。最后删掉所有小于事先给定最小支持度值的分支，得到一颗总的频繁二叉树，并总结出关联规则[4]。
3 BT_CM算法改进描述
根据BT_CM算法的思路，该算法可概括为五个步骤：
第一步：利用给定事务数据库中各事务列表产生对应的子集集合，集合中子集个数为2n-1个，不包含空集。
第二步：根据产生的子集集合生成对应的频繁集子二叉树。将产生的频繁集子二树进行进行剪树操作，并合并到上一步产生的频繁集子二叉树中。
第三步：累加统计已形成的二叉树分支的权重值。
第四步：循环以上步骤，得到频繁集二叉总树。根据最小支持度对二叉总树进行修剪。
第五步：得到关联规则频繁集二叉总树，并生成关联规则。
该算法具体的描述如下：
算法目标：根据事务数据库产生关联规则二叉树，得
到关联规则。
输入：事务列表。
输出：关联规则二叉树及其关联规则。
算法描述：①假如事务列表某一项为{I1，I2，I3}，求出该项集的子集为{{I1}，{I2}，{I3}，{I1，I2}，{I1，I3}，{I2，I3}，{I1，I2，I3}}。同时该项集产生频繁集子二叉树的过程为：创建一个根结点，将子集集合中长度length为1的子集项即{I1}，{I2}，{I3}添加到根结点下面。接下来进行长度length为2的子集项{I1，I2}，{I1，I3}，{I2，I3}的添加，以{I1，I2}为例具体进行。首先从根结点开始找到结点I1，将I2顺延添加结点I1后面。重复对{I1，I3}，{I2，I3}子集项进行添加。最后从根结点开始依次找到I1，I2结点，并将I3添加到其后，完成对{I1，I2，I3}子集项的添加，即完成长度length为3的子集添加。
②接着将另一个子集项{{I2}，{I3}，{I2，I3}}形成频繁子二叉树，对其利用关联规则原理进行剪树之后将其加入到第一步生成的频繁子二叉树中。具体为先将该二叉树深度为1的结点进行剪树操作，即剪掉{I3}结点单独的分支。然后将剩下部分添加到已有树中去。方法为从已有树的根结点开始查找I2结点以及{I2→I3}分支是否存在，若存在则将相应分支的权重值加1，若不存在则从根结点开始创建这一新的结点或是分支。
③将事务数据库中其它事务项集对应的子集集合生成的频繁子二叉树按照上述方法添加到已有树中去，形成一颗频繁二叉总树。
④根据最小支持度将频繁二叉总树进行修剪得到最终关联规则二叉树并取得关联规则。
4 BT_CM算法仿真
通过仿真实验比较新提出的BT_CM算法与原始Apriori算法在运行时间上的差异。仿真实验的测试环境为Intel Core i5-3210M2.5GHz，内存为2G，仿真数据选取某数据库中数据表前5条、50条、500条记录进行测试。两者的仿真结果如表1所示：
由上表可以看出新提出的算法随着记录数的增加，算法在时间效率上得到了很大提高。
5 BT_CM算法实例说明
为了更好地介绍BT_CM关联规则新算法，在此选择如表2中所示的事务数据库来说明关联规则形成的过程。设定最小支持度为2，即min_sup=2/9≈22%。整个过程如下表2：
5.1 分别对给出的每一项的列表进行求子集运算。得到的子集个数为2n-1个（n为每一项列表的个数，不包括空集），如表3所示：
5.2 利用得到的各项列表子集集合进行二叉树的建树操作。根结点表示为Ti，其中i={1，2，3，4，5，6，7，8，9}。产生的频繁子集二叉树如下图1所示：
5.3 将修剪之后的各频繁子集二叉树进行合并堆积操作，并在关联规则树逐步形成的过程中不断地改变结点及各分支路径的权重值。得到的二叉树如图2所示。
5.4 对合并之后得到的完整的二叉树进行修剪，原则是根据事先确定好的最小支持度来判断哪一分支会被修剪掉。修剪之后得到的树如图3所示。
5.5 由修剪之后的二叉树得到事务数据库的关联规则。该算法产生关联规则是由生成的二叉树的深度来决定的。具体关联规则如下：
①根据树深为2得到关联规则为：I1→I2，I1→I3， I1→I5，I2→I3，I2→I3，I2→I5。
②根据树深为3得到关联规则为：I1→I2→I3，I1→I2→I5。
6 结论
经过改进之后的数据挖掘关联规则算法比起原算法有了较大的性能提高。其最大的优势体现在：首先改进的算法大大减少了执行时间。新算法首先利用事务数据库中各单项产生对应的子集集合，并利用子集集合进而形成各单项子二叉树。接着可对产生的子二叉树进行剪树操作。其次改进的算法大大减少了计算量。
参考文献：
[1]罗刚.浅谈Apriori算法[J].企业导报，2012，10.
[2]李忠哗.人工智能技术的发展趋势研究[J].信息与电脑（理论版），2012，08.
[3]R.Agrawal，R. Srikant. Fast Algorithirns for Mining Assoeiation Rules[C].Proeeedings of the 20th Intemational Confereneeon Very Large Database （VLDB’94），Santiago，Chile，Morgan Kaufinann Publisher，1994：487-499.
[4]吴斌，肖刚，陆佳炜.基于关联规则挖掘领域的Apriori算法的优化研究.计算机工程与科学，2009，06.
作者简介：
朱金坛（1981-），男，陕西西安人，教研室副主任，高校讲师，研究方向：计算机软件技术、信息系统开发、信息安全与加密。
关键词：数据挖掘 关联规则 二叉树 BT_CM全新算法
1 数据挖掘简介
数据挖掘（Data Mining）[1]即“从数据中挖掘知识”，是目前数据库和人工智能领域研究的热点问题，所谓数据挖掘就是从大量数据中提取或“挖掘”知识。具体来说，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘是一种决策支持过程，它主要基于人工智能[2]、机器学习、模式识别、统计学、数据库、可视化技术等，高度自动化地分析企业的数据，做出归纳性的推理，从中挖掘出潜在的模式，帮助决策者调整市场策略，减少风险，做出正确的决策。数据挖掘在数据库领域使用最多。典型的数据挖掘系统由以下六部分组成： 数据库、数据仓库或其他信息库、数据库或数据仓库服务器、知识库、数据挖掘引擎、模式评估模块、图形用户界面。
2 BT_CM算法思路
针对原始Apriori算法[3]存在多次扫描数据库以及产生大量候选集的两大缺陷，提出一种基于二叉树逐渐合并堆积原理的BT_CM全新算法。新算法首先利用事务数据库中各单项产生对应的子集集合，并利用子集集合进而形成各单项子二叉树。其次可对产生的子二叉树进行剪树操作，剪树的原理是根据关联规则的目标是找出项集之间关联的缘故，将深度为1的树结点剪掉。紧接着将后产生的子二叉树合并到之前产生的树中，并累加统计得出树中分支的权重值（即分支出现的次数）。最后删掉所有小于事先给定最小支持度值的分支，得到一颗总的频繁二叉树，并总结出关联规则[4]。
3 BT_CM算法改进描述
根据BT_CM算法的思路，该算法可概括为五个步骤：
第一步：利用给定事务数据库中各事务列表产生对应的子集集合，集合中子集个数为2n-1个，不包含空集。
第二步：根据产生的子集集合生成对应的频繁集子二叉树。将产生的频繁集子二树进行进行剪树操作，并合并到上一步产生的频繁集子二叉树中。
第三步：累加统计已形成的二叉树分支的权重值。
第四步：循环以上步骤，得到频繁集二叉总树。根据最小支持度对二叉总树进行修剪。
第五步：得到关联规则频繁集二叉总树，并生成关联规则。
该算法具体的描述如下：
算法目标：根据事务数据库产生关联规则二叉树，得
到关联规则。
输入：事务列表。
输出：关联规则二叉树及其关联规则。
算法描述：①假如事务列表某一项为{I1，I2，I3}，求出该项集的子集为{{I1}，{I2}，{I3}，{I1，I2}，{I1，I3}，{I2，I3}，{I1，I2，I3}}。同时该项集产生频繁集子二叉树的过程为：创建一个根结点，将子集集合中长度length为1的子集项即{I1}，{I2}，{I3}添加到根结点下面。接下来进行长度length为2的子集项{I1，I2}，{I1，I3}，{I2，I3}的添加，以{I1，I2}为例具体进行。首先从根结点开始找到结点I1，将I2顺延添加结点I1后面。重复对{I1，I3}，{I2，I3}子集项进行添加。最后从根结点开始依次找到I1，I2结点，并将I3添加到其后，完成对{I1，I2，I3}子集项的添加，即完成长度length为3的子集添加。
②接着将另一个子集项{{I2}，{I3}，{I2，I3}}形成频繁子二叉树，对其利用关联规则原理进行剪树之后将其加入到第一步生成的频繁子二叉树中。具体为先将该二叉树深度为1的结点进行剪树操作，即剪掉{I3}结点单独的分支。然后将剩下部分添加到已有树中去。方法为从已有树的根结点开始查找I2结点以及{I2→I3}分支是否存在，若存在则将相应分支的权重值加1，若不存在则从根结点开始创建这一新的结点或是分支。
③将事务数据库中其它事务项集对应的子集集合生成的频繁子二叉树按照上述方法添加到已有树中去，形成一颗频繁二叉总树。
④根据最小支持度将频繁二叉总树进行修剪得到最终关联规则二叉树并取得关联规则。
4 BT_CM算法仿真
通过仿真实验比较新提出的BT_CM算法与原始Apriori算法在运行时间上的差异。仿真实验的测试环境为Intel Core i5-3210M2.5GHz，内存为2G，仿真数据选取某数据库中数据表前5条、50条、500条记录进行测试。两者的仿真结果如表1所示：
由上表可以看出新提出的算法随着记录数的增加，算法在时间效率上得到了很大提高。
5 BT_CM算法实例说明
为了更好地介绍BT_CM关联规则新算法，在此选择如表2中所示的事务数据库来说明关联规则形成的过程。设定最小支持度为2，即min_sup=2/9≈22%。整个过程如下表2：
5.1 分别对给出的每一项的列表进行求子集运算。得到的子集个数为2n-1个（n为每一项列表的个数，不包括空集），如表3所示：
5.2 利用得到的各项列表子集集合进行二叉树的建树操作。根结点表示为Ti，其中i={1，2，3，4，5，6，7，8，9}。产生的频繁子集二叉树如下图1所示：
5.3 将修剪之后的各频繁子集二叉树进行合并堆积操作，并在关联规则树逐步形成的过程中不断地改变结点及各分支路径的权重值。得到的二叉树如图2所示。
5.4 对合并之后得到的完整的二叉树进行修剪，原则是根据事先确定好的最小支持度来判断哪一分支会被修剪掉。修剪之后得到的树如图3所示。
5.5 由修剪之后的二叉树得到事务数据库的关联规则。该算法产生关联规则是由生成的二叉树的深度来决定的。具体关联规则如下：
①根据树深为2得到关联规则为：I1→I2，I1→I3， I1→I5，I2→I3，I2→I3，I2→I5。
②根据树深为3得到关联规则为：I1→I2→I3，I1→I2→I5。
6 结论
经过改进之后的数据挖掘关联规则算法比起原算法有了较大的性能提高。其最大的优势体现在：首先改进的算法大大减少了执行时间。新算法首先利用事务数据库中各单项产生对应的子集集合，并利用子集集合进而形成各单项子二叉树。接着可对产生的子二叉树进行剪树操作。其次改进的算法大大减少了计算量。
参考文献：
[1]罗刚.浅谈Apriori算法[J].企业导报，2012，10.
[2]李忠哗.人工智能技术的发展趋势研究[J].信息与电脑（理论版），2012，08.
[3]R.Agrawal，R. Srikant. Fast Algorithirns for Mining Assoeiation Rules[C].Proeeedings of the 20th Intemational Confereneeon Very Large Database （VLDB’94），Santiago，Chile，Morgan Kaufinann Publisher，1994：487-499.
[4]吴斌，肖刚，陆佳炜.基于关联规则挖掘领域的Apriori算法的优化研究.计算机工程与科学，2009，06.
作者简介：
朱金坛（1981-），男，陕西西安人，教研室副主任，高校讲师，研究方向：计算机软件技术、信息系统开发、信息安全与加密。