基于正相关关联规则的分类算法

【作者】 李睿楠；

【导师】 范明；

【作者基本信息】 郑州大学 ， 计算机软件与理论， 2007， 硕士

【摘要】 分类是数据挖掘研究中的一个基本任务，关联规则挖掘是数据挖掘研究中的一个重要领域，把关联规则挖掘用于分类问题开辟了数据分类的一条新路。常见的基于关联规则分类算法通常在训练数据集上生成关联规则的全部集合，然后选择一个高质量的规则子集作为分类规则集去分类和预测测试数据集。研究表明，基于关联规则分类具有高准确率和强适应性的特点。但是，在生成的分类器中，往往会产生大量的分类规则，而其中很大一部分的分类规则可能对分类并没有好处。并且，有时因为选取单一高置信度的规则，使分类结果产生了过分拟合。因此，基于关联规则的分类算法，其关键在于分类器也就是分类规则集的建立。而且对挖掘得到的分类规则集需要有不同的度量去评估其分类性能。如何产生更有意义的关联规则，如何使用有意义的关联规则对测试数据集进行分类，是本文研究的主要内容。本文提出了一种新的关联分类算法CPCAR。该方法对FP-Growth算法进行改进，在频繁项集产生的过程中，引入正相关性的判断，使最后生成的频繁项集是正相关的，并使用正相关的频繁项集得到正相关的初始分类规则集。为了提高分类准确率和效率，再利用置信度对初始分类规则集进行规则选取，生成由正相关关联规则组成的分类器。分类时，本文算法首先在每个分类器中选取分类规则，这些分类规则可以分类测试事务，每条分类规则都有一个x~2权值，然后计算每个分类器中选取出的分类规则的权值和，比较权值和最大的分类器的类标号与测试事务的类标号，两个类标号一致则表示分类正确。最后根据正确分类的测试事务数与总测试事务数得出本文算法在某事务数据集上的分类准确率。实验表明，虽然本文算法在生成分类规则集的时候，删除了大量的关联规则，但是在UCI机器学习的14个数据集中，最终的分类准确率可以与C4.5和CMAR相媲美，且算法运行的时间开销明显降低。更多还原

【Abstract】 Classification is a basic task of data mining research, association rule mining is an important area of data mining research, classification based on association rule mining break a new path in data classification. The normal classification based on association rule algorithms usually mine all association rules set in training database. Then they classify or predict the test database by a high performance classification rule set which is chosen in all association rules set.Previous studies propose that classification based on association rule has high classification accuracy and strong flexibility. However, there are huge classification rules in the classifier, and the most of it are helpless in classification. And classification will be overfitting sometimes since it is based on only single high-confidence rule. So the key of classification based on association rule algorithms is the constructing of classifier i.e. classification rule set. We need different measurements to evaluate the performance of the classification rule set.The main content of this paper are how to get more meaning association rules and how to classify test datasets by the meaning association rules. In this paper, we propose a new associative classification algorithm, CPCAR, i.e. Classification based on Positively Correlated Association Rules. The algorithm improves the FP-Growth algorithm, it estimates positively correlation of frequent item sets when they are gotten. So the final frequent itemsets is positively correlated. The algorithm can get the original classification rules set by positively correlated frequent itemsets. For enhancing the accuracy and efficiency of classification, the algorithm selects the predictive rules in the original classification rule set by confidence to generate classifiers which are composed by positively correlated association rules.. When it classifies, at first, the algorithm selects all rules which can classify test transaction in each classifiers. Then it computes the summary of weight x~2 of multiple selected predictive rules in each classifiers, and compares class label of the classifier which weight summation is maximal with test transaction. If two class label is the same, it means classification is right. The accuracy of CPCAR algorithm in a transaction database can be gotten by the number of accurately classified test transactions and total test transactions. Although the algorithm deletes a great deal of associative rules when generates the predictive rules sets, our experiments on 14 databases from UCI machine learning database repository show that the final accuracy of CPCAR is close to C4.5 and CMAR, but the time of algorithm circulation has been reduced obviously.更多还原