【作者】 胡陈勇；

【导师】 刘大有；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2004， 硕士

【摘要】 数据挖掘，又称数据库中的知识发现，作为一门新兴的研究领域，主要目的是从数据集合中发现隐含的、事先未知的、对决策有潜在价值的用户感兴趣的知识，数据挖掘是当前数据库领域中最受瞩目的研究方向之一。在数据挖掘研究中，关联规则挖掘作为数据挖掘研究中的一个重要部分，引起了越来越多的关注。关联规则最初来源于对超市数据的分析，用来发现超级市场中用户购买的商品之间的隐含关系，以便为商场的决策提供依据。关联规则通常具有如下形式：AB，其中A和B都是条件的合取范式。关联规则挖掘就是发现满足用户定义的最小支持度和最小可信度的关联规则。本文从数据挖掘和关联规则的基本概念出发，介绍了各种经典的关联规则算法。比如，关联规则的挖掘工作可以分成两个步骤,第一个步骤是发现所有满足用户给定的最小支持度的频繁项目集（如果某一项目集合X在数据库中出现的次数超过了用户定义的最小值支持度，则X就是频繁项目集）；第二个步骤是从频繁项目集生成所有满足用户给定的最小可信度的关联规则。由于第一个子问题由于产生的数据量巨大，面临更大的计算复杂性问题，具有很大的挑战性，其中算法的关键是效率问题，大多数关联规则算法主要是集中在如何高效的寻找频繁项目集。在文中，我们详细介绍了一个经典的Apriori算法，并对其他算法作了概要性回顾；同时针对第二步骤，我们也介绍了一些常用的算法。然而由于目前大多数关联规则算法只是停留在挖掘布尔类型的关联规则，而在有些情况下，整个决策系统，经典的关联规则并不能达到的用户的要求。因此，我们提出了扩展经典关联规则的算法，在特定的情况下，显得更加有意义。这也是写这篇论文的主要目的之一，在本文的后半部分，我们提出了一些扩展的关联规则算法。如在第三部分提出的加权关联规则算法，主要是基于每一个Transaction对整个系统的贡献大小不一样。这样就克服了传统关联规则在某些特定的领域中的问题。在本文的第四章，也是这篇论文的重点部分，由于传统算法只是针对二元数据矩阵进行操作，抛弃了可能对整个决策系统起着非常作用的数量化信息。而在实际过程中，这些数量化信息往往对整个决策系统起着非常重要的<WP=47>作用，因此如何能够充分利用这些信息成为当前关联规则领域的一个难点。针对这种情况，提出了一种新的扩展的关联规则-比例规则，主要思想是通过PCA，SVD等方法求出主向量，再通过自己定义了比例项目集等挖掘可以度量比例规则。其形式如下： Bread:Milk:Butter=1:2:5 上面这规则说明这样一个意思：如果一个顾客花1块钱买面包，那么他有可能会花2块钱买牛奶和花5块钱买黄油。同时我们又通过实验证明了该算法对于挖掘传统的关联规则同样有效。另外，该算法除了挖掘量化的关联规则以外，在其他方面同样具有重要的意义，比如，由于在实际过程中，经常会遇见一些数据不完整的情况，在这种情况下，传统的关联规则算法显得力不从心。在我们提出的算法却很好地解决了这种普遍的缺失值问题，在尽量减少误差的条件下，该算法巧妙的利用各种已知的信息来获取缺失值，并保证重新构造的值尽量的接近隐含的真实值。与此同时，该算法还具有捕获一些非正常数据：包括误操作，或者影响整个决策系统的其他重要数据，如信用卡欺诈行为。而传统关联规则在这些方面显得束手无策。在文中最后一部分，我们简单介绍了关于数据挖掘知识库求精平台。该平台作为国家863项目“智能化农业信息系统开发平台中”重要的一部分，集成了常用的数据挖掘算法，如粗糙集，决策树，关联规则等。同时用户可以通过良好的界面方式进行简单操作就可以完成这种数据处理。该平台在可移植性，可扩充性方面达到了较好的效果。由于关联规则作为一个崭新的领域，很多方面有待于更进一步去研究，挖掘。比如如何挖掘基于增量式的关联规则，挖掘不确定关联规则，挖掘有序关联规则的问题摆在我们的眼前，这也是本人在今后研究的重点。更多还原

【Abstract】 Data mining has received considerable interest (Fayyad & Uthurusamy, 1996),of which the quintessential problem in database research has been association rule mining(Agrawalet al..,1993). Today the mining of such rules is still one of the most popular pattern discover method in KDD.In brief, an association rule is an expression X=>Y, where X and Y are sets of items. The meaning of such rules is quite intuitive: Given a database D of transactions –where each transaction is a set of items-X=>Y expresses that whenever a transaction T contains X than T probably contains Y also.In this paper we deal with the algorithmic aspects of association rule mining .In fact, a broad variety of efficient algorithms to mine association rules have been developed during the last years. These approaches are more or less described separately in the corresponding literature .To overcome this situation we gibe a general survey of the basic ideas behind association rule mining in chart 1,2.In the following sections, we propose several extended association rules algorithms. In chapter 3, we introduction a weighted association rules which affect the computation of the support. In this extended model, transactions contain information that is of different importance to the user.In chapter 4, we propose another extended association rules—Ration Association Rules, which is the kernel section in this paper. Because the tradition Association Rule algorithms operate on a data matrix to derive association rules. That is ,the vast majority of association rule discovery technique are Boolean ,since they discard the quantities of the items bought and only pay attention to whether something was bought or not. Here, we propose a new paradigm, namely, Ratio Association Rules, which are quantifiable in that we can measure the “goodness” of a set of discovered rules. In fact, we have proved that our algorithm works very well in mining traditional association rules. What’s more, we can illustrate some contributions about such algorithm. For example, using such method, we reconstruct missing data which is very prevail problems, and we can detection some outlier in our original data matrix such as noise, fraud data etc. In the last section, we introduction our data mining platform which is a <WP=49>important part of our National 863 Projection. In the platform, we can select some kinds of data mining algorithms to operate the database. Such as attribute reduction, classify, clustering. And so on.In the field of Data Mining, the research of association rules is carried abroad. Today, mining quantitative association rule is still in open which needs us to spend more time to research更多还原