数据挖掘中关联规则挖掘的应用研究 http://www.paper.edu.cn 吴海玲，王志坚，许峰 河海大学计算机及信息工程学院，江苏南京（210098） 摘 要： 本文首先介绍关联规则的基本原理，并简单概括其挖掘任务，然后说明关联规则 的经典挖掘算法 Apriori 算法，通过一个实例分析进一步明确关联规则在 CRM 中的应用， 最后展望了关联规则挖掘的研究方向。 关键词：数据挖掘，关联规则，Apriori 算法，CRM 引言 关联规则是表示数据库中一组对象之间的某种关联关系的规则，关联规则挖掘的主要 对象是交易(Transaction)数据库。这种数据库的一个主要应用是零售业，比如超级市场的销 售管理。条形码技术的发展使得数据的收集变得更容易、更完整，从而可以存储大量的交 易资料。关联规则就是辨别这些交易项目之间是否存在某种关系。例如：关联规则可以表 示“购买了商品A和B的顾客中有 80％的人又购买了商品C和D”。这种关联规则提供的信息 可以用作商品目录设计、商场货架的布置、生产安排、具有针对性的市场营销等。 [1] 1 关联规则的基本原理 设Ｉ＝｛i1，i2，……，im｝是项的集合，设任务相关的数据D是数据库事务的集合， 其中每个事务T是项的集合，使得T I。每一个事务有一个标识符，称作T ID。设X是一个 项集，事务T包含X当且仅当X T。关联规则是形如X Y的蕴涵式，其中X I，Y ⊆ I， 并且X∩Y＝∅ 。规则X Y 在事务集D中成立，具有支持度s，其中s是D中事务包含X∪Y （即X和Y二者）的百分比，它是概率P（X∪Y）。规则X Y在事务集中具有可信度c，如 果D中包含X的事务同时也包含Y的百分比c。这是条件概率P（X Y∣ ）。即是 ⇒ ⇒ ⊆ ⊆ ⊆ ⇒ support(X⇒ Y)= P（X Y∪ ） confidence(X⇒ Y)= P（X Y∣ ） 同时满足最小支持度(minsup)和最小可信度阈值（minconf）的规则称作强规则[1]。 项的集合称为项集（itemset）。包含k个项的项集成为k－项集，例如集合{computer, software }是一个 2—项集。项集的出现频率是包含项集的事务数，简称为项集的频率。项 集满足最小支持度minsup，如果项集的出现频率大于或者等于minsup与D中事务总数的乘 积。如果项集满足最小支持度，则称它为频繁项集(frequent itemset) [2]。 2 关联规则的发现任务 关联规则挖掘的问题就是要找出这样的一些规则，它们的支持度或可信度分别大于指 定的最小支持度minsup和最小可信度minconf。因此，该问题可以分解成如下两个子问题[3]： 1．产生所有支持度大于或等于指定最小支持度的项集，这些项目集称为频繁项目集 （frequent itemsets），而其他的项目集则成为非频繁项目集（non-frequent itemsets） 2．由频繁项集产生强关联规则。根据定义，这些规则必须满足最小支持度和最小可信 度。 关联规则挖掘的问题的主要特征是数据量巨大，因此算法的效率很关键。目前研究的 重点在第一步，即发现频繁项目集，因此第二步相对来说是很容易的。 -1- 

http://www.paper.edu.cn 3 Apriori 挖掘算法 关联规则是反应两项或多项属性之间存在的相关性，其目的是为了从一些项的属性值 来预测其他属性值，同时可以应用推广所反映一个事件和其他事件之间依赖或者关联的知 识。最为著名的关联规则挖掘方法是由美国学者 R.Agrawal 提出的 Apriori 算法，主要是用 于从大规模商业数据中挖掘关联规则。 Apriori算法利用了项目集如下性质对数据库进行多趟扫描：任意频繁项集的子集都是 频繁项集；任意非频繁项集的超集都是非频繁项集。第一趟扫描得到频繁－1 项集的集合 L1，第k趟扫描前先利用上趟扫描的结果项目集Lk-1产生k－项集的集合Ck，然后再通过扫描 数据库确定对Ck中每一候选k－项集的支持数，最后在该趟结束时求出频繁k项集合Lk，算 法在Ck或Lk为空时终止。 下面是 Apriori 算法的伪代码： 算法：Apriori 算法，使用逐步迭代法生成频繁项集 输入：事务数据库 D；最小支持度阈值 minsup 输出：D 中的频繁项集 L L1 = {large 1－itemsets}； for (k = 2； Lk-1 ≠ ；k++ ) { Ck ＝ apriori_gen (Lk-1；minsup)；//产生候选项 forall transactions t { D∈ ∅ Ct = subset (Ck， t);//找出包含Ck的事务子集 forall candidates c ∈Ct { c.count++；} Lk = {c ∈ Ck| c.count/|D|≥ minsup} } } Return Answer k LU k 算法：apriori_gen 函数： 输入：以Lk-1频繁（k-1）－项集，minsup：最小支持度作为输入参数 输出：返回所有k－项集的集合Ck procedure apriori_gen (Lk-1；minsup) forall itemset l1 forall itemset l2 L∈ k-1 L∈ k-1 if (l1[1]= l2[1]) … (l ∧ ∧ 1[k-2]= l2[k-2]) (l∧ 1[k-2]＜ l2[k-2]) then { C = l1[1] l1[2] …l1[k-2] l1[k-1] l2[k-1]}；//连接产生候选项 forall(k-1)-项集 sin c { If s ∉ Lk-1 then delete c； -2- 

http://www.paper.edu.cn else add c to Ck； } } return Ck ； 4 关联规则在 CRM 中的应用 4.1 CRM 简介 Customer Relationship Management (CRM)，客户关系管理，指的是企业与其客户的交 流方式,它实施于企业的市场营销、销售、服务与技术支等与客户有关的领域。它是一种管 理理念，又是一种旨在改善企业与客户之间关系的新型管理机制，也是一种管理软件和技 术，它将最佳的商业实践与数据挖掘、数据仓库、一对一营销、销售自动化以及其它信息 技术紧密结合在一起,为企业的销售、客户服务和决策支持等领域提供了一个业务自动化的 解决方案,使企业有了一个基于电子商务的面对客户的前沿，从而顺利实现由传统企业模式 到以电子商务为基础的现代企业模式的转化。CRM 的特征是:①一对一营销②高度集成的 交流渠道③统一共享的信息资源④商业智能化的数据分析和处理⑤对基于 Web 的功能的 支持。 CRM的目标就在于协助企业不断地获取和积累客户知识，并将这些知识运用在企业的 生产、市场营销和客户服务等各个领域，以提升客户满意度和忠诚度，提高企业的核心竞 争力，从而降低生产、销售和服务成本，增加企业效益。[5] 4.2 基于关联规则的客户获得 以在线商店中的购物系统为例，说明 关联规则在 CRM 客户获得中的应用。某 在线商店货架上有多种货物，例如，帽子、 裙子、鞋子等,我们应用关联规则就是为了 发现当一个人已经购买了帽子时，那他有 多大可能还会买裙子呢？ 首先，设定最小支持度为 40%，假设 该在线商店数据库中共有 5 条记录，如表 1 所示： 表 1 客户购买信息表 记录号 帽子 裙子 鞋子 1 1 1 0 2 0 1 0 3 1 1 0 4 1 0 1 5 0 1 0 根据Apriori算法，首先产生第一频集L1，如表 2 所示。 由于鞋子的支持度小于 40%，最终Ｌ1 频集为表 3 所示。 表 2 第一频集 L1 项目集 X 支持度％ 帽子 60(3/5) 裙子 80(4/5) 鞋子 20(1/5) 表 3 最终Ｌ1 频集 项目集 X 支持度％ 帽子 60(3/5) 裙子 80(4/5) -3- 

http://www.paper.edu.cn 由L1频集，得出C2候选集，如表 4 所示。由C2候选集,得出L2频集，如表 5 所示。 表 4 C2 候选集 表 5 L2 频集 项目集 X 支持度％ 帽子、裙子 ？ 项目集 X 支持度％ 帽子、裙子 40(2/5) L2为得出的最终频集。 由关联规则可得： confidence(帽子⇒ 裙子)= P（帽子∣裙子）= 40%/60%=2/3 confidence(裙子⇒ 帽子)= P（裙子∣帽子）= 40%/80%=1/2 由此可以看到买帽子的人也买裙子的可能性(67%)高于买裙子的人也买帽子的可能性 (50%)。帽子和裙子关联的支持度已足够高了，意味着这是一条有意义的关联规则。 5 结论与展望 关联规则挖掘是数据挖掘的一个重要应用。本文首先介绍关联规则的基本原理，并简 单概括其挖掘任务，然后说明关联规则的经典挖掘算法 Apriori 算法，通过分析进一步明确 关联规则在 CRM 中的应用。 数据库中的关联规则挖掘研究已经取得了令人瞩目的成绩，但以下方面的研究也将是 具有挑战性的工作：在处理极大量的数据时，如何设计更高效的挖掘算法；对各种非结构 化数据的挖掘；制定更为合理的规则衡量标准；与数据仓库（Data Warehouse）和OLAP （Online Analytical Process）的结合；在挖掘的过程中，提供一种与用户进行交互的方法， 与用户的知识领域相结合，生成结果的可视化等等[6]。 -4- 

http://www.paper.edu.cn 参考文献 [1] David Hand，Heiki Mannila，Padhraic Smith．Principles of Data Mining．机械工业出版社，中信出版社， 2003 年 4 月． [2] Jiawei，Micheline Kamber．Data Mining Concepts and Techniques．范明，孟小峰等译．机械工业出版 社，2001 年 8 月． [3] 关联规则算法概述．通信企业管理[J]，2005，9：76～77． [4] 姚俊．浅谈关联规则挖掘．信息技术[J]，2005，6：85～87． [5] 费贤举，王文琴，庄燕滨．基于关联规则的数据挖掘技术在 CRM 中的应用研究．常州工学院学报[J]， 2005，8（4）：1～6． [6] 毕建欣，张岐山．关联规则挖掘算法综述．中国工程科学[J]，2005，4（7）：88～94． The Applied Research of Association Rules Mining in Data Mining Department of Computer Information & Engineering, Hohai University, Nanjing (210098 ) Wu Hailing，Wang Zhijian，Xu Feng Abstract association rule This paper firstly introduces the principles of association rules and also simply summarizes the association rules mining tasks. In the next place, a typical association rules mining algorithm, which is named Apriori algorithm, is explained. Through analyzing an instance, the application of association rules in Customer Relationship Management is further illustrated. At last, this paper prospects the future research directions on association rules mining. Keywords: management customer relationship Apriori algorithm date mining -5-