关联分类算法的研究与实现

苗世强 郑晓势

摘 要： 关联分类算法是对数据进行分析处理中的一个分支。文中结合了关联分类CBA算法，针对数据集样本进行了详细分析。首先，对关联分类中的CBA算法进行了研究，并同步对其实现的代码进行了编写。随后，结合相关数据，运行相关算法进行实现与分析。最终，对该样本数据进行了有效地分类和预测，也完成了算法的有效实现与分析。

关键词： 关联；关联分类；CBA算法

Abstract：Classification algorithm based on association rules is a branch of data analysis and processing. In this paper the CBA algorithm is used to analyze the detailed sample data. First of all the CBA algorithm is studied and the code of CBA algorithm is realized synchronously. After that combined with the relevant data it is designed to run the CBA algorithm for analysis. Finally the sample data are effectively classified and predicted the algorithm implementation and analysis are also completed.

Key words： association；classification based on association rules；CBA algorithm

1 关联和分类算法简介

关联规则和分类方法作为大数据分析和处理中的2个分支，一直得到了广泛的研究与应用。其中，分类就是通过已有的分类技术，实际地构造出一个分类器模型，在此基础上继续进行分类分析。其中比较典型的算法就是决策树算法和贝叶斯分类算法。而关联规则就是通过对频繁数据的挖掘，进而找到关联性强的规则集合。

决策树是一种代表性的分类算法，也是一种归纳学习算法。具体来说，决策树中的标志性算法主要有ID3[1]、C4.5[2]、CART算法[3]。决策树算法的基本思想是，从最上端到下端开始使用贪心算法，继而递归调用搜索样本集，并在每个测试候选集上展开测试，最终构造出决策树。贝叶斯分类算法是一种基于统计学的分类算法。通过给定的数据，结合贝叶斯分类来预测样本数据属于一个指定类的发生概率。

顾名思义，关联规则就是对数据集合中挖掘出一些关联性强的数据，即频繁项集，整个过程需要挖掘出符合设定的最小支持度的数据。关联分类算法，作为二者的结合，就是通过对关联规则的挖掘，并以此为基础来设计实现分类操作。

2 关联分类CBA算法

研究中，将对关联分类CBA算法[4]展开如下设计论述。过程中，关联分类的第一步就是通过已有的数据结合关联规则算法，产生频繁项集数据，找到类关联规则。在此基础上将转入分类处理中。分类的原理思路就是按照支持度与置信度的不同构造分类器，然后进行分类。挖掘频繁项集的步骤就是通过关联规则Apriori算法[5]挖掘得到了频繁项。假设一项集中含有该已知的属性，同时含有分类的该属性的值，随后在该算法中通过计算此频繁项是否能通过已知的属性值来推导出决策的属性值的关联规则。如果该规则满足设定的最小置信度，那么就把该频繁项集中的决策属性的值作为最终的分类结果。

CBA算法是建立在关联规则上的分类算法，重点分为CBA-RG和CBA-CB两个操作进程。具体内容如下：

（1）CBA-RG主要用于产生类关联规则数据集合。在该阶段利用关联规则算法运行发现类关联规则集合，同时还要设定给出最小支持度和置信度。通过扫描数据库，生成满足最小支持度和置信度的数据集合。

（2）CBA-CB主要就是构建分类器。在该过程对上述产生的规则数据提供了进一步的排序研究，并且选择具有高置信度的规则优先插入到分类器中。最后，根据该分类器，对数据进行分类。

3 关键步骤代码实现

输入：所有的事务集，最小支持度MinSup

输出：关联分类结果

4 实验与结果分析

该算法选用的计算机硬件环境如下：CPU为Core i5-7500，3.4 GHz，内存为2 GB；操作系统为Window7；采用的开发语言为Java。使用的数据测试集合是从UCI上真实下载，该程序测试的样本数据分别为：car、led7、cmc。由于在这些数据中，存在着一些连续、且冗余的数据，在算法尚未开启执行时，需要对此中数据进行预处理。对一些存在连续性的数据转换为离散化，同时对干扰数据实现了部分删除，保证了数据的质量。处理后的数据内容信息可见表1。

随后，将应用本次研究选取的测试样本数据来设计执行算法，并分别从算法执行准确度和运行时间进行了分析。在算法运行过程中，测试了不同最小支持度下对算法精确度和运行时间的作用影响。本文研究算法的综合测试效果对比可详见图1、图2。

由图1、图2可知，在选用数据集car、led7、cmc的情况下，当设定不同的最小支持度时，对算法的准确性和运行时间均会带来一定的调控影响。

5 结束语

着重研究了关联分类中的CBA算法，并编译实现了该算法。结合UCI数据集上下载数据，通过成功设计编写本文算法，輸入部分测试的样本数据项，完成了对数据的关联分类和预测。基于此，还对算法分别从准确度以及性能方面进行了测试与分析，并获得了合理、有效的研究成果。

参考文献

[1] QUINLAN J R. Induction of decision trees[J]. Machine learning 1986 1（1）： 81-106.

[2] QUINLAN J R. C4. 5：Programs for machine learning[J]. Machine Learning，1994，16（3）：235-240.

[3] BREIMAN L REIEDMAN J H OLSHEN R A et al. Classification and regression trees[M]. New York： Chapman & Hall 1984.

[4] LIU Bing HSU W MA Yiming. Integrating classification and association rule mining[C]//Proceedings of the fourth international conference on knowledge discovery and data mining. New York：AAAI 1998：1-7.

[5] AGRAWAL R IMIELINSKI T SWAMI A. Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD Conference. Washington DC USA： ACM 1993：1-10.

[6] 禹蒲阳. CBA分类算法的一种改进[J]. 计算机应用与软件，2010，27（8）：241-243，254.

[7] 张明卫，朱志良，刘莹，等. 一种大数据环境中分布式辅助关联分类算法[J]. 软件学报，2015，26（11）：2795-2810.

[8] 王熙照，赵东垒. 基于规则兴趣度的关联分类[J]. 计算机工程与应用，2007，43（25）：168-171.

[9] 武建华，沈钧毅，方加沛. 提取有效规则的关联分类算法[J]. 西安交通大學学报，2009，43（4）：22-25.