数据挖掘中关联规则算法及应用的研究

数据挖掘中关联规则算法及应用的研究

姓名：刘芳申请学位级别：硕士专业：计算机应用技术指导教师：陆奎20100601

摘要摘要如今，人们把握数据的能力在不断提升。面对海量数据，人们更加关注的是隐藏在数据背后的重要信息，而非数据本身。数据挖掘满足了我们的需求，它是帮助我们发现数据中重要知识的有利工具。关联规则是数据挖掘的一个重要分支，挖掘出大型事务数据库中的关联规则对不同领域实际问题的解决起着非常重要的作用。本论文主要研究关联规则算法及其应用。首先，论文系统地阐述了数据挖掘和关联规则中的相关理论知识，为研究内容的全面展开打下坚实的理论基础。其次，论文通过指出经典的挖掘频繁项目集算法Ａｐｒｉｏｒｉ算法的性能瓶颈问题，即多次扫描数据库以及可能会产生庞大的候选集，为新算法的研究找到入口。因此，本论文对Ａｐｒｉｏｒｉ算法做了如下改进：首先从数据库布尔矩阵的角度来生成厶和厶，打破了Ａｐｒｉｏｒｉ算法生成厶的固有模式；然后在证明结论“厶一，生成Ｇ的连接步可用厶一，∞厶来代替厶一。ｏｏＬ，．．＂成立的基础上，再来改进ｋ－候选集的集合Ｃｒ（ｋ≥３）的生成算法。所以，综合上述工作本论文提出了Ａｐｒｉｏｒｉ算法的改进算法ＢＭＳＬ算法（ＢｏｏｌｅａｎＭａｔｒｉｘＳｉｍｐｌｉｆｉｅｄＬｉｎｋｅｄＡｐｒｉｏｒｉＢＭＳＬＡｐｒｉｏｒｉ算法的理论性分析，我们可以得知该算法不仅能够减少数据库的扫描次数以及一定程度上避免庞大候选集的产生，而且还能够降低算法的时间与空间开销。然后，我们又通过具体的实验进一步证明了ＢＭＳＬＡｐｒｉｏｒｉ算法的效率确实优于Ａｐｒｉｏｒｉ算法和其他算法。最后，在较好的软硬件环境下并借助真实超市交易数据库中的部分数据，论文采用ＭｉｃｒｏｓｏｆｔＳＱＬＳｅｒｖｅｒ２００５和ＶＢ．ＮＥＴ作为开发平台来构建一个简单的关联规则挖掘系统，将ＢＭＳＬ通过挖掘结果再次证明了该算法较Ａｐｒｉｏｒｉ算法和其他算法确实取得了不错的挖掘效果。图［２４】表［４】参【６０】关键词：数据挖掘；关联规则；Ａｐｒｉｏｒｉ；ＦＰ—ｇｒｏｗｔｈ；ＢＭＳＬ＿Ａｐｒｉｏｒｉ分类号：５２０．６０；摘要Ａｂｓ仃ａｃｔＮｏｗａｄａｙｓ，ｔｈｅｃａｐａｃｉｔｙｏｆｐｅｏｐｌｅｔｏｇｒａｓｐｔｈｅｄａｔａｉｓｒｉｓｉｎｇ．ＦａｃｉｎｇＳＯｍａｓｓｄａｔａ，ｐｅｏｐｌｅｄａｔａｍｏｒｅｃｏｎｃｅｒｎｔｈｅｖｅｒｙｉｍｐｏｒｔａｎｔｉｎｆｏｒｍａｔｉｏｎｈｉｄｄｅｎｉｎｔｈｅｄａｔａｔｈａｎｔｈｅｏｕｒｉｔｓｅｌｆ．ＤａｔａＭｉｎｉｎｇｍｅｅｔｓｒｅｑｕｉｒｍｅｎｔ，ａｎｄｉｔｉｓａｕｓｅｆｕｌｔｏｏｌｔｏｈｅｌｐａｒｅｕｓｆｍｄｔｈｅｉｍｐｏｒｔａｎｔｋｎｏｗｌｅｄｇｅｆｒｏｍｔｈｅｄａｔａ．ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓｉｍｐｏｒｔａｎｔｂｒａｎｃｈｏｆＤａｔａａｌｌＭｉｍｎｇ，ａｎｄｅｘｃａｖａｔｉｎｇＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓｏｆｔｈｅｌａｒｇｅｓｅｒｖｉｃｅｓＤａｔａｂａｓｅｐｌａｙｓｉｍｐｏｒｔａｎｔｐａｒｔＴｈｅｉｎｔｈｅｓｏｌｖｉｎｇｏｆａｃｔｕａｌｐｒｏｂｌｅｍｓｏｆｄｉｆｆｅｒｅｎｔｄｏｍａｉｎ．ｍａｉｎｌｙｄｉｓｃｕｓｓｅｓＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓｐａｐｅｒａｌｇｏｒｉｔｈｍａｎｄｉｔｓａｐｐｌｉｃａｔｉｏｎ．Ｆｉｒｓｔ，ｔｈｅｐａｐｅｒｓｙｓｍａｔｉｃａｌｌｙｄｅｓｃｒｉｂｅｓｔｈｅｒｅｌａｔｅｄｔｈｅｏｒｙｋｎｏｗｌｅｄｇｅｏｆＤａｔａＭｉｎｉｎｇａｎｄＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓｉｎｏｒｄｅｒｔｏｌａｙｔｈｅｆｏｕｎｄａｔｉｏｎｆｏｒｒｅｓｅａｒｃｈｃｏｎｔｅｎｔ．Ｓｅｃｏｎｄ，ｉｔｉｎｄｉｃａｔｅｓｔｈｅｄｅｆｉｃｉｅｎｃｙｏｆＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍ，ｔｈａｔｒｅｐｅａｔｅｄｌｙＳＣａｎＳＤａｔａｂａｓｅａｎｄｍａｙｎｅｗｇｅｎｅｒａｔｅｈｕｇｅｃａｎｄｉｄａｔｅｓｅｔｓ，ａｎｄｍａｋｅｓｔｈｅｎｗｅｃａｎｆｍｄｔｈｅｅｎｔｒａｎｃｅｔｏａｌｇｏｒｉｔｈｍ．Ｓｏ，ｔｈｅｐａｐｅｒｔｈｅｔｈｅｆｏｌｌｏｗｉｎｇｉｍｐｒｏｖｅｍｅｎｔｏｆｔｏａｐｒｉｏｒｉａｌｇｏｒｉｔｈｍ：ｆｉｒｓｔ，ｉｔｇｅｔｓ厶ａｎｄ厶ｆｒｏｍｐｅｒｓｐｅｃｔｉｖｅＤａｔａｂａｓｅＢｏｏｌｅａｎＭａｔｒｉｘ，ｂｒｅａｋｉｎｇｔｈｅｎａｔｕｒａｌｍｏｄｅｏｆ厶ｇｅｎｅｒａｔｉｏｎｉｎａｐｒｉｏｒｉ；ａｎｄｔｈｅｎｉｔｉｍｐｒｏｖｅｓｔｈｅｇｅｎｅｒａｔｉｏｎａｌｇｏｒｉｔｈｍｏｆＧ（ｋ≥３）ｂｙＧ．ｐｒｏｖｉｎｇｃｏｎｃｌｕｓｉｏｎ，ｔｈａｔ厶一ｌ吗ｃａｎｔａｋｅｔｈｅｐｌａｃｅｏｆ厶一ｌ鸣一１ｔｏｐｒｏｐｏｓｅｇｅｔＳｏ，ｗｅｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍ，ＢＭＳＬ＿Ａｐｒｉｏｒｉａｌｇｏｒｉｔｈｍ（Ｂｏｏｌｅａｎａｌｇｏｒｉｔｈｍ），ｂｙｃａｎｄｉｄａｔｅｉｎｔｅｇｒａｔｉｎｇａｂｏｖｅ－ｍｅｎｔｉｏｎｅｄＭａｔｒｉｘＳｉｍｐｌｉｆｉｅｄｃａｎＬｉｎｋｅｄ＿Ａｐｒｉｏｒｉｗｏｒｋ．Ｆｉｒｓｔ，ｗｅｋｎｏｗＢＭＳＬ＿ＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｎｏｔｏｎｌｙｒｅｄｕｃｅｓｔｈｅｎｕｍｂｅｒｏｆｈｕｇｅｓｅｔｓＤａｔａｂａｓｅｓｃａｎｎｉｎｇａｎｄａｖｏｉｄｓｐｅｎｄｉｎｇｏｆｇｅｎｅｒａｔｉｏｎ，ｂｕｔａｌｓｏｉｔｄｒｏｐｓｔｈｅｔｉｍｅａｎｄｓｐａｃｅ，ｂｙａｎａｌｙｓｉｓｏｆｉｔｓｔｈｅｏｒｙ．Ｓｅｃｏｎｄ，ｗｅｐｒｏｖｅｓｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｉｓｓｕｐｅｒｉｏｒｔｏａｐｒｉｏｒｉａｎｄｏｔｈｅｒａｌｇｏｒｉｔｈｍｂｙｓｐｅｃｉｆｉｃｅｘｐｅｒｉｍｅｎｔ．、斩ｍＳＱＬｓｏｍｅｄａｔａａｎｄｏｆｔｒｕｅｔｒａｎｓａｃｔｉｏｎＤａｔａｂａｓｅ，ｗｅｔａｋｅＶＢ．ＮＥＴｔｏｃｏｎｓｔｒｕｃｔａａｄｖａｎｔａｇｅｏｆＭｉｃｒｏｓｏｆｔＳｅｒｖｅｒ２００５ｓｉｍｐｌｅＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓＭｉｎｉｎｇｓｙｓｔｅｍｗｅｉｎｇｏｏｄｓｏｆｔｗａｒｅａｎｄｈａｒｄｗａｒｅｅｎｖｉｒｏｎｍｅｎｔ，ａｎｄｕｓｅＢＭＳＬ＿＿ＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｉｎｔｈｅｐｒｏｃｅｄｕｒｅｏｆＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓＭｉｎｉｎｇ．Ｆｉｎａｌｌｙ，ｉｔｉｓｖｅｒｉｆｉｅｄｔｈａｔｔｈｅｉｔｏｂｔａｉｎｓｔｈｅｂｅｔｔｅｒｅｆｆｅｃｔｔｈａｎａｐｒｉｏｒｉａｎｄｏｔｈｅｒａｌｇｏｒｉｔｈｍｂｙＭｉｎｉｎｇｒｅｓｕｌｔ．Ｆｉｇｕｒｅ【２４】ｔａｂｌｅ【４】４ｒｅｆｅｒｅｎｃｅ［６０】Ｋｅｙｗｏｒｄｓ：ＤａｔａＭｉＩｌｉｎｇ；ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ；Ａｐｒｉｏｒｉ；ＦＰ—ｇｒｏｗｔｈ；ＢＭＳＬ＿ＡｐｒｉｏｒｉＣｈｉｎｅｓｅｂｏｏｋｓｃａｔａｌｏｇ：５２０．６０；ＩＩ１绪论１绪论１．１研究背景在计算机和网络技术快速发展的今天，我们逐步实现了信息数据的数字化管理。首先，数据库尤其是数据仓库的出现和应用，以及人类采集数据工具的进步，使得数据呈爆炸般增长，再加上有限的数据库技术，最终导致“数据爆炸、知识贫乏＂的现象产生。其次，集网络技术于一体的并行计算机处理系统的发展，使人们不仅能够更快、更好地把握住数据，而且也使他们的注意力发生了转变，不再追求数据本身，而是希望从数据中发现对组织、单位或企业具有特殊作用的有价值的信息。最后，经济的全球化发展使得企业在残酷的竞争中面临了前所未有的压力，企业管理者迫切地希望能够从企业的历史数据中发现有助于企业自我完善、不断发展的信息数据。等等这些现象都迫使人们能够尽快找到一种新的工具，这种工具不仅能快速、方便地把数据转变为有用的知识，而且人们也可以利用这种工具对海量数据进行更高层次的分析，以便挖掘出隐藏在这些数据里的重要信息。因此集统计学、人工智能、模式识别及最优化等技术于一身的数据挖掘技术应运而生。由于数据挖掘既能够展现过去数据的一般状态，又能对未来趋势做进一步预测，因此近年来数据挖掘在电信业、金融业、零售业、生物医学等各个领域越来越显示出其强大的生命力。关联规则挖掘是数据挖掘的一个重要组成部分，是实现数据挖掘的主要分析方法之一，１９９３年由Ａｇｒａｗａｌ等人提出。挖掘出海量数据背后的关联规则形成对管理和决策有用的价值规律体系是非常有必要的。关联规则挖掘的一个典型案例是购物篮分析，通过发现顾客购买商品之间的联系来分析顾客的购物模式，以便帮助零售商制定相应的营销策略。发生在美国沃尔玛连锁超市的“尿布与啤酒”的故事就是关联规则的一个经典实例，它激起了众商家探索数据背后奥秘的兴趣。关联规则挖掘的核心是关联规则挖掘算法，其中最具影响力的算法有经典的挖掘频繁项目集的算法—＿Ａｐｒｉｏｒｉ算法，以及频繁模式增长算法——－ＦＰ—ｇｒｏ讹算法。深入研究关联规则挖掘算法不断地提高其效率并且使其更好地应用在各个领域中是目前研究的热点，也是势在必行的。１．２国内外的研究现状有关数据挖掘的研究，国内比国外起步稍微晚些，且没有形成大的研究规模，基本上以学术研究为主，在实际应用方面尚且处于初始阶段；而国外早已经是热门研究课题，并且达到了相当高的水平，大部分研究成果都比较成熟，有的都已ｌ绪论经投入到实际的应用领域当中。关联规则挖掘是发现数据库中数据间的关联关系，最早由Ａｇｒａｗａｌ等人于１９９３年提出。在关联规则挖掘的过程中，最为核心是关联规则挖掘算法，它是决定挖掘出的关联规则是否具有实际意义和价值的一个重要因素。关联规则算法就是如何从大量数据中挖掘出关联规则的方法与步骤，最著名的算法是Ａｇｒａｗａｌ等人于１９９４年提出的挖掘频繁项目集的算法Ａｐｒｉｏｆｉ算法。Ａｐｒｉｏｄ算法在关联规则挖掘研究中具有里程碑作用，它采用逐层搜索的迭代方法来对数据库进行多次扫描直到找出数据库中的所有频繁项目集为止。但是随着研究与应用地不断深入，Ａｐｒｉｏｆｉ算法也逐渐暴露出它的弊端。因此，后来的诸多研究人员在结合实际问题的基础上又对关联规则挖掘做了大量的研究。他们所做的工作主要有Ａｐｒｉｏｒｉ算法及其衍生算法、量化关联规则挖掘算法、增量挖掘算法以及并行挖掘算法等；采用的挖掘方式主要有自底向上型和自顶向下型ＩｌＪ。就大型事务数据库而言，可能蕴藏着大量的关联知识，我们不能盲目地进行挖掘，而是要附加一定的条件来指导挖掘，使得挖掘工作变得有目的和有意义；如果我们分析出数据的某一个或多个特定属性进而来对其特定属性值下的数据而非全体数据进行挖掘，那么数据间又有可能产生特定的关联规则，这些规则可能对实际问题的解决起到意想不到的作用。因此，将约束引入到关联规则的挖掘中成为近年来关联规则挖掘研究的一个重要方向。此外，我们还可以将数据的每个属性在概念上分为多个层次，数据中每个属性间的关联规则是否具有实际意义和价值与该属性所在概念层次的高低有一定的联系。因此，多层关联规则挖掘也成为目前关联规则挖掘研究的热点方向之一。再者，关联规则挖掘算法中各种度量参数的使用，以及将不断走向成熟的ＯＬＡＰ技术与关联规则挖掘结合起来成为近年来人们研究关联规则的主要方向之一【２Ｊ。国内对于关联规则挖掘的研究主要集中在算法、理论和实际应用上。虽然在政府出资的情况下也研制开发了若干关联规则挖掘系统，且这些系统也取得了一定的成功，但是在如何提高算法效率，如何提供与用户交互的方法等方面还存在一些问题。１．３当前存在的问题最经典、最具影响力的挖掘频繁项目集的算法是Ａｐｒｉｏｒｉ算法，由ＲａｋｅｓｈＡｇｒａｗａｌ等人于１９９４年提出，该算法在关联规则挖掘研究中具有里程碑作用。但是随着研究地不断深入，它的缺点也逐步暴露出来。Ａｐｒｉｏｆｉ算法有两个致命的性能瓶颈：其一是多次扫描事务数据库，需要很大的Ｉ／Ｏ负载；其二是可能产生庞大的候选集【３Ｊ。为了减少数据库的扫描次数以及避免庞大候选集的产生，许多专家学者提出了一些基于Ａ研ｏｒｉ算法的改进算法以提高Ａｐｒｉｏｒｉ算法的效率，如散列（Ｈａｓｈ）技术、划分（Ｐａｒｔｉｔｉｏｎ）技术、采样（Ｓａｍｐｌｉｎｇ）方法等。但是这些改２ｌ绪论进的算法又或多或少的存在一些问题，如采样方法，它的最大问题就是如何选取样本数据，即便选取了样本数据且提高了算法的效率但却降低了算法的精度。２０００年，ＪｉａｗｅｉＨａｒｔ等人提出了一个称为频繁模式增长的算法，简称为ＦＰ—ｇｒｏｗｔｈ算法。该算法采用压缩的频繁模式树结构，只需要扫描数据库两次，而且不产生候选集，打破了Ａｐｆｉｏｆｉ算法生成频繁项目集的固有模式，有效地提高了频繁项目集的挖掘效率，但不足的是该算法不太适合于大型数据库中关联规则的挖掘。等等这些问题都要求我们更深入地去研究关联规则挖掘算法，尽可能地消除瓶颈等问题，提高算法效率，以便使其更好地应用到各个行业中。１．４论文研究的主要内容本论文主要研究关联规则的挖掘算法及其应用，分两步进行。首先，通过分析经典的挖掘频繁项目集算法Ａｐｆｉｏｆｉ算法的性能瓶颈问题，提出一种新的基于Ａｐｆｉｏｆｉ算法的改进算法ＢＭＳＬＡｐｆｉｏｆｉ算法，详尽地分析ＢＭＳＬ并通过实验证明改进的新算法确实优于Ａｐｆｉｏｆｉ算法和其他算法。然后，利用ＭｉｃｒｏｓｏｆｔＳＱＬＳｅｒｖｅｒ２００５和ＶＢ．ＮＥＴ作为开发平台构建一个简单的关联规则挖掘系统，将改进的新算法应用到频繁项目集的生成中，通过挖掘结果来说明新算法较Ａｐｆｉｏｆｉ算法和其他算法确实取得了不错的效果。１．５论文的组织结构根据论文的内容，将其划分为六章，具体组织结构如下。第一章：介绍论文研究的背景、国内外研究现状、当前存在的问题、论文研究的主要内容以及论文的组织结构。第二章：对数据挖掘理论进行简要介绍，如数据挖掘的概念、常用知识表示模式及其方法、体系结构、技术支持等，为论文中的其他内容打好理论基础。第三章：介绍了关联规则挖掘的相关概念与方法、事务数据库中关联规则的挖掘过程，并探讨了关联规则中的约束问题以及一些更深入问题。第四章：这一章是本论文的重点。本章提出了Ａｐｆｉｏｆｉ算法的改进算法ＢＭＳＬＡｐｆｉｏｆｉ算法，通过描述改进算法的基本思想、设计步骤及对其进行性能分析后，我们又用实验来证明新算法的效率确实优于Ａｐｆｉｏｆｉ算法和其他算法。第五章：我们先采用ＭｉｃｒｏｓｏＲＳＱＬＳｅｒｖｅｒ２００５和ＶＢ．ＮＥＴ作为开发平台来构建一个简单的关联规则挖掘系统，然后将ＢＭＳＬＡｐｆｉｏｆｉ算法应用到频繁项目集的生成中，最后通过分析挖掘结果来说明该算法较Ａｐｆｉｏｆｉ算法和其他算法确实取得了不错的挖掘效果。第六章：对本论文进行总结，并展望未来工作。３１绪论１．６本章小结本章主要介绍了课题研究的背景、国内外的研究现状、当前存在的问题、论文研究的主要内容以及本论文的组织结构。４２数据挖掘理论综述２数据挖掘理论综述２．１数据挖掘的概念数据挖掘是一种基于数据库的全新的数据处理技术，是数据库技术的延伸。数据挖掘内涵极其丰富且涉及范围广，不同领域的研究和开发人员会从不同的角度来看待它，因此要科学地说明数据挖掘是什么并不是给它下个定义这么简单。由于数据挖掘是数据库技术和人工智能、机器学习等多个学科相互融合的产物，再加上其在商业应用中取得的巨大成功，所以，我们可以从以下两个方面来说明它的内涵。２．１．１数据挖掘的技术定义在讨论数据挖掘之前，我们首先来认识这样一个名词：数据库中的“知识发现”（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙｉｎＤａｔａｂａｓｅ，ＫＤＤ）。从在第十一界国际人工智能专题讨论会上首次提出ＫＤＤ至今，ＫＤＤ一直是国际上学术研究的热点。关于ＫＤＤ和ＤａｔａＭｉｎｉｎｇ，研究者们各持己见。把ＫＤＤ视为数据挖掘的一个特例或认为ＫＤＤ与ＤａｔａＭｉｎｉｎｇ没有区别，这两种观点都具有片面性；而把数据挖掘看成是ＫＤＤ的一个步骤，这种观点大多数学者都能够接受。事实上，ＫＤＤ包括数据清洗、数据集成、数据选择、数据转换、数据挖掘、模式生成及评估等一系列步骤，是由一些基本功能构件组成的系统化协同工作系统，数据挖掘只是这个系统中的一个关键部分【４】。数据挖掘作为知识发现过程的一个步骤，如图２－１所示。简单来说，数据挖掘就是在原始数据经过相应处理而形成的数据集上对有价值知识进行抽取的一个过程，我们只有准确地定位数据挖掘，才能帮助我们正确理解数据挖掘、锁定研究任务，进而有效地解决问题。因此，从技术角度来看，数据挖掘就是利用一组相关技术从完全没有经过处理的大型数据集上挖掘出我们事先不知道的、有价值的知识的一个整体过程，挖掘出的知识可以用概念、规则、规律和模式等形式来表示【５Ｊ。５２数据挖掘理论综述数据ｊ车：＋．．．．………一＋：．一…．…一…一Ｔ＿……一一…一，图２－１数据挖掘视为知识发现过程的一个步骤Ｆｉ９２—１ＤａｔａＭｉｎｉｎｇａｓａｓｔｅｐｏｆＫＤＤ２．１．２数据挖掘的商业定义数据挖掘从一开始就是面向应用的，因此我们也可以把它看成是一种全新的商业数据处理技术。数据挖掘作为数据库中知识发现ＫＤＤ的一个核心步骤，主要是通过相应的算法来提取数据间的关联或一般性的知识，并且利用这些知识来指导某些商业活动。因此，从商业角度来看，数据挖掘就是按照企业设定好的目标来对企业中的大量数据进行深层次分析，以揭示出蕴藏在其中的有价值的规律，进而利用这些规律来指导商业运作［３１。虽然数据挖掘在各个领域的应用取得了巨大的成功，但是我们要清楚地认识到数据挖掘只是一个工具，我们不能神话了这个工具。我们不能认为有了数据挖掘之后就无所不能，更不能认为挖掘出的知识都是真理，所有这些挖掘出的知识都是相对的，都是有着一定局限性的，它可能只是对特定的应用行为才具有实际意义。２．２数据挖掘的常用知识表示模式及其方法数据挖掘的目的只有一个，那就是采用某些专门的方法来发现隐藏在数据背后的知识，而知识又要通过一定的模式给出。因此，只有精确地分析出数据挖掘譬２数据挖掘理论综述中知识的表示模式及其所采用的方法，我们才能够更深层次地了解数据挖掘系统的运作特点，才能够更好地将其应用到实际的领域当中。２．２．１广义知识挖掘广义知识通常是指一般概括性知识，它主要用来描述某类事物所具有的共同特征【６】。哲学中经常采用的分析方法是从“个别＂到“一般＂、“低层＂到“高层”，因此，我们总是希望通过对数据的某些个别或低层次的特性进行分析来发现它们所蕴含的一般性规律。数据挖掘就是根据数据的这些个别或低层次的特性来发现普遍的、更高层次的规律知识。挖掘出的广义知识可以用直观的图表来描绘，而且这些知识在进行分类或预测等方面也起到了一定的作用。１）概念描述法数据有概念之分，如消费者的概念包括一般性消费者、贵宾式消费者。概念描述就是概括某类对象所具有的内涵特征，它是广义知识挖掘的重要分析方法之一。概念描述由特征性描述和区别性描述组成，“概念”描述某类对象的共同特征，“区别性＂描述不同类对象之间的区别【７Ｊ。那么，我们通过什么方法才能得到概念描述呢？概念描述一般可以通过数据特征化、数据区分以及数据特征化和比较这三种方法得到。其中，数据特征化是指对目标类数据的一般特征进行汇总；数据区分是指通过对比目标类中数据对象与其他类中数据对象的一般特性来找出数据间相互区别的界限【４】。概念描述中最具有代表性的方法是概念归纳法，该方法的研究成果比较多，它也是目前研究的重点方向之一。概念归纳法源自于机器学习，若要把学习算法的思想应用到数据挖掘中，我们就必须要解决两个关键问题，即样本容量和范围的扩大以及负样本和相关度量方法的形成。２）多维数据分析对于事务数据库中的数据，我们不能仅仅从它的某一个角度去分析它。例如你购买的一盒饼干，它有品牌、产地、生产日期等属性，这每一个属性就称为饼干数据的“维＂，而饼干数据就称为“多维数据’’。在决策分析活动中，我们应该挖掘出数据的各个维，并能够找出这些维之间的关联关系。由于多维数据自身的特点，所以多维数据的分析工作相对比较复杂，它就是把各种计算（如计数、求和等）汇集在一起，这样不仅计算量大而且操作具有重复性。因此，我们想到一个办法，那就是把这些经过各种处理而汇到一起的结果存储起来留待以后高级数据的分析和使用。２．２．２关联知识挖掘关联知识就是一个事物和其他事物之间相互联系的知识，数据库中数据间的相互联系就是现实世界中事物间相互联系的一个本质表现【８Ｊ。数据间的关联是繁７２数据挖掘理论综述杂多样的、蕴藏的、事先不知道的，我们必须通过关联分析才能得到它，并且挖掘出数据间的关联关系对于商业决策有着重大的意义。那何谓“关联分析’’呢？关联分析是数据挖掘的本质，是指发现这样一种关联规则，这种规则能够说明属性一值频繁地出现在某数据集中的条件【９】。关联分析着重于刻画数据对象间的关联及关联程度，并广泛地应用于购物篮或事务数据的分析中。那何谓“关联规则＂呢？关联规则是形如ＸｊＹ的蕴涵式，它可以解释为“满足Ｘ条件的数据库数据在某种情况下多半也会满足Ｙ条件＂［４１。关联规则挖掘是数据挖掘研究的重点方向之一，最早由Ａｇｒａｗａｌ等人于１９９３年提出。关联规则挖掘的核心是关联规则挖掘算法，Ａｐｒｉｏｒｉ算法作为经典的关联规则挖掘算法一直在被广泛地讨论和应用，并且它是我们研究其他算法的原型和基础。在关联规则挖掘里我们通常设定两个阈值，即最小支持度和最小可信度，来作为我们提取有实际意义和价值的关联规则的标准。只有同时满足用户指定最小支持度和最小可信度的关联规则才是我们需要的，因为它们分别表示数据间的关联需要满足的最低联系程度和最低可靠程度。关联规则的应用深入到各个领域，是目前备受关注的研究课题之一。２．２．３类知识挖掘类知识是对一类在某种意义上具有共同特征的事物的描述与刻画，每一类事物都有自己的类标识，因而不同类的事物之间可以相互区别。数据挖掘里的类知识主要是指分类和聚类这两种。１）分类分类是数据挖掘的一个重要方法，主要应用在商业中。要实现分类，首先是类知识的获取，我们可以对源数据集进行过滤、抽取、压缩来获取类知识。分类的最终目的是形成一个分类器，该分类器的作用就是将数据库中数据的各个数据项分别映射到给定的类别中，即做到“各归其位＂。因此，我们可以说数据挖掘的任务之一就是根据已形成的类知识来对源数据进行分类，进而也能够预测未来数据属于哪个类。２）聚类与分类一样，聚类也是数据挖掘的重点分析方法之一。聚类主要是根据某种特性把数据对象划分成若干个类别，并且能够令同类数据对象间的差别尽可能小，不同类数据对象问的差别尽可能大，进而使不同类数据对象间有明显的区分标识１１ｕＪ。然而，聚类和分类又有不同：一般情况下，给定的数据样本中不包含类标识，因此聚类只分析数据对象而不考虑类标识；而分类是通过对数据进行分析和比较生成新的类标识。但是，分类和聚类之间的界限也不是绝对的，它们也互有交叉和补充。２数据挖掘理论综述２．２．４特异型知识挖掘特异型知识是指数据中包含的极端特殊的知识，这些知识明显区别于其他正常的用于描述数据规律的知识，它揭示了数据中异常性的存在【１１１。数据库里通常可能会包含这样一些数据，它们与其他绝大多数的数据在某些方面具有非常不一致的行为。一般情况下，我们可能会忽略甚至是丢弃这些特殊数据；但是如果我们能够对这些特殊数据进行检测来发现它们所蕴含的特殊知识，那么就会对我们的工作产生意想不到的效果。例如，可以根据特异型知识来发现是否存在信用卡欺骗的情况，我们对比给定账号与正常付费就可以解决这个问题。我们还可以将特异型知识应用到其他数据挖掘技术中，它们相辅相成，特异型知识很可能伴随着普通知识的产生而产生。１）孤立点分析孤立点通常是指明显不符合数据一般模式的数据，相对于正常的知识而言，它们通常被作为噪声来处理甚至被丢弃【３ｌ。孤立点可以很好地应用到某些系统信息的检测中，如信用欺诈、入侵检测等。因此，孤立点数据分析成为近年来数据挖掘中的又一个研究课题，越来越受到人们的关注。发现和检测孤立点的方法主要有三类，即基于概率统计、基于距离和基于偏差这三类方法。目前，孤立点分析有着广阔的应用前景。２）序列异常分析异常序列分析通常是指在事件或行为序列中发现了明显不符合一般规律的知识ｆ１２１。挖掘出序列异常的特征模式对电信、银行等行业的商业欺诈行为的预防以及网络安全的检测等都是非常有帮助的。２．３数据挖掘系统的体系结构在前面数据挖掘的技术定义中提到，将数据挖掘看成是ＫＤＤ的一个步骤的观点为大多数学者接受并认同。实际上在众多领域中，“数据挖掘＂比“数据库中的知识发现＂更加流行和更加容易被接受。数据挖掘从广义上来讲就是从大型数据集上挖掘出有趣知识的过程【４１。基于这种观点，我们可将数据挖掘系统作如下划分，如图２－２所示。９２数据挖掘理论综述图２－２典型数据挖掘系统的结构Ｆｉ９２—２ｔｙｐｉｃａｌＤａｔａＭｉｎｉｎｇａｒｃｈｉｔｅｃｔｕｒｅ２．３．１数据库、数据仓库或其他信息库数据仓库就是一个面向主题的、集成的、不可更新的、且随时间不断变化的数据集合，它用于支持经营管理中的决策制定；同时数据仓库也是一种管理技术，旨在通过流畅、合理、全面的信息管理来达到有效的决策支持【２】。数据仓库和数据挖掘分别作为决策支持和发现知识的新技术，是结合起来发展的，二者相互影响、相互促进。数据仓库不仅为数据挖掘提供了更好的数据源、决策支持以及新的支持平台，而且还为更好地使用数据挖掘工具提供了方便。但是，数据仓库决不等同于数据挖掘。数据仓库本质上是一种存储技术，是数据挖掘的物质基础，它的数据存储量非常大，且能为各种用户的各种决策需求提供有价值的数据和信息。在这个组成部分里，我们可以对数据进行清理和集成。２．３．２数据库或数据仓库服务器局域网中的数据库服务器是由一台或多台计算机和数据库管理系统软件共同构成的，数据库服务器能够为客户的应用提供多种服务，这些服务包括更新、查询、索引、事务管理、查询优化、高速缓存、安全及多用户存取控制等【ｌ引。数据库服务器的典型结构是客户／服务器结构。在Ｃ／Ｓ模型中，数据库服务器软１０２数据挖掘理论综述件主要用于响应数据查询或数据操纵的请求；与用户交互的部分在用户的工作站上运行。在这里，此组成部分会根据用户的数据挖掘请求来提取相关的数据。２．３．３知识库知识库系统是数据库技术和人工智能相结合的产物，简单来说知识库就是以一定的方式存储在计算机内的知识的集群。一般情况下，知识库中的知识包括概念分层与用户确信方面的知识。其中，概念分层是指将属性或属性值组织成不同的抽象层；而用户确信方面的知识是指用于评估模式兴趣度的知识【４】。因此，我们可以利用知识库中的知识来指导搜索或评估结果模式的兴趣度。２．３．４数据挖掘引擎引擎是我们借用了机器中的同名术语，表明它在整个系统中的核心地位；而数据挖掘引擎是一种挖掘分析技术，它通常用来分析用户所需数据的特点以及抽取信息使用方式，它在实现数据挖掘系统的通用性上起到了重要的作用【１４】。通过刚才的定义我们可知，数据挖掘引擎是数据挖掘系统的核心组成部分。该部分由一组功能模块组成，它在数据挖掘的功能实现中起着至关重要的作用。２．３．５模式评估模块选择适当的数据挖掘方法便可将挖掘模块与模式评估模块集成在一起，而且模式评估模块能够在与数据挖掘模块交互的基础上使用兴趣度度量（支持度、置信度）来将搜索定位在有趣的模式上。那何谓“有趣的模式”呢？一个模式若能易于理解，是新颖的、潜在有用的，且在某种程度上，对新的或测试数据是有效的，则称该模式是有趣的【１５】。因此，模式评估模块可使用兴趣度阈值来过滤发现的模式。●２．３．６图形用户界面图形用户界面实际上就是用户与数据挖掘系统之间的接口。通过与挖掘系统进行交互后，我们便可利用该模块来指定数据挖掘的查询或任务。除了上述功能外，图形用户界面还可以为我们提供信息，帮助我们将搜索定位在某处。另外，图形用户界面也可以根据挖掘的中间结果来进行探索式的数据挖掘，而且允许用户浏览数据库和数据仓库的模式或数据结构、评估挖掘的模式，以及以不同的形式来可视化模式【４】。２．４数据挖掘的技术支持２．４．１粗集理论法粗集理论法是一种数学工具，它用来研究不精确和不确定性的知识。该方法２数据挖掘理论综述的最大优点是它不需要关于数据的任何附加信息，而且比较容易掌握。粗集理论法基于样本数据内部等价类的建立，它通常用于离散值的属性，因而连续值的属性在使用前必须先离散化。粗集理论法可用来发现分类规则，具体过程如下：首先将数据库中数据的属性划分为条件属性和结构属性；然后根据各属性值将数据库中数据划分成相应的子集；最后再对两种属性之间的上下近似关系生成判定规则【５１。另外，粗集理论法也可用于属性子集选择和相关分析。其中，属性子集选择可以识别和删除对样本数据分类没有帮助的属性；相关分析是根据分类任务来评估每个属性的贡献或显著性。２．４．２模糊集方法模糊集方法同样也是针对不确定的问题提出的，它与粗糙集方法既相互独立，又互为补充。模糊集方法需要依赖已获得的知识来定量描述不确定性，系统越复杂，就越难精确化，模糊性也就越强。我们可以将模糊集方法应用到分类等知识发现的过程中，通过模糊推理和分析可有效地发现大量数据中所蕴含的有趣的知识。２．４．３决策树法决策树方法的基础模型是信息论原理，该方法是通过一组相关规则来达到对数据进行分类的目的。决策树方法相对于其他方法而言，不仅构造过程的时间短，结果较容易理解、精度较高，而且还可以可视化数据规则。因此，决策树方法较为广泛地应用于知识发现等系统中。最基础的决策树算法是ＩＤ３算法，它首先检验数据的所有特征，然后再利用互信息最大的特征来建立决策树中的各个节点，务必使得决策树中有最小的节点数，进而使得识别例子的准确率达到最高。另外，Ｇｅｈｒｋｅ等人提出的基于雨林模型的改进算法ＢＯＡＴ也是比较著名的算法之一。但决策树法也有其不足之处：如该方法很难利用多个变量的相互组合来发现关联规则，并且决策树不同分枝之间的裂痕也不平滑【３ｌ。２．４．４神经网络神经网络是人工神经网络的简称，通常用于人类思维的模拟。神经网络采用神经元的数学模型为基础模型并以一定的学习准则为工作原理，在数据编码及神经元迭代求解的基础上，来完成对复杂模式提取的过程【１６１。神经网络主要用于数据挖掘中分类问题的研究，有不少学者提出了利用神经网络来挖掘知识的算法，如Ｌｕ和Ｓｅｔｉｏｎｏ等提出的挖掘事务数据库中关联规则的方法。虽然神经网络具有可解释性差、结构复杂、训练时间长等不足之处，但是它比较容易解决具有上百个参数的问题；同时它在处理噪声数据方面具有低错误率、高承受力、自组织自适应性等优点。神经网络的这些特点相对于其他技术来说比较适合于解决１２２数据挖掘理论综述数据挖掘中的相关问题，因此，近年来它越来越受到人们的关注。神经网络的一般结构，如图２－３所示。输入层中间层输出层图２—３神经网络的结构示意图Ｆｉ９２—３ａｒｃｈｉｔｅｃｔｕｒｅｏｆＡＮＮ２．４．５遗传算法遗传算法以达尔文生物进化论中的自然选择和遗传学机理为基础，是一种找出问题最优解的计算模型。同时，遗传算法也是一种通用的算法，它可以用来解决各种搜索问题。根据数据挖掘的一般性定义，我们可以将许多挖掘问题都看成是搜索问题：即数据库或数据仓库为数据所在的搜索空间，而挖掘知识的算法便是搜索策略。因此，在数据挖掘的过程中我们就可以应用遗传算法来挖掘出数据间有趣的关联知识。遗传算法的工作过程如下：首先进化随机产生的一组规则；然后观察数据库中的所有数据是否都能被这一组规则所覆盖。如果是这种情况，那么我们就可以挖掘出隐藏在数据中的关联规则了。２．４．６类比学习法类比是将一类事物的某些相同方面进行比较，以另一事物的正确或谬误来证明这一事物的正确或谬误。常用的类比学习法是Ｋ＿最邻近方法，它属于懒散学习法，可用于分类和聚类中；相比决策树等急切学习法，它具有训练时间短、分类时间长的特点【１７１。２数据挖掘理论综述２．５数据挖掘的应用在文章的开始部分我们就提到过，数据挖掘本身就是面向应用的。作为一种新兴科技，数据挖掘给我们的生活带来了巨大的变化，使人类的物质文明又向前迈进了一大步。数据挖掘在生物医学、金融业、电信业、零售业、信息安全等领域的应用都取得了丰硕的成果，下面我们就对数据挖掘在这些领域的应用做简要地介绍。２．５．１数据挖掘在生物医学中的应用目前，生物医学领域中的研究人员把大部分精力都放在对ＤＮＡ数据的研究和分析上。通过挖掘分析ＤＮＡ数据，不仅能够帮助研究人员们尽快地发现各种疾病的基因成因，而且也能够帮助他们及时地找到治疗的新方法进而研制新药，物。ＤＮＡ数据分析的关键点之一就是ＤＮＡ序列的研究，ＤＮＡ序列的结构千变万化，把握住ＤＮＡ序列结构变化的特征也是医学研究人员需要攻克的难题。若能够正确、高效地将数据挖掘技术应用到生物医学中，这将会为如何发现特殊疾病所蕴含的基因排列信息指明方向。２．５．２数据挖掘在金融业中的应用金融业是数据挖掘的主要应用领域之一，通过对相对比较完整、可靠且高质量的金融数据进行挖掘，我们不仅可以发现潜在的用户群而且还能够及时地对这些用户做出信用的评估。数据挖掘在金融领域的应用主要有金融投资、贷款偿还预测和客户信用政策分析以及洗黑钱和其他金融犯罪的侦破。金融投资一般采用模型预测方法对该领域中的投资评估和股票交易市场预测进行分析；贷款偿还预测和客户信用政策分析主要是指银行利用数据挖掘中的相关方法，如特征选择或属性计算，来识别对贷款偿还效能和客户信用等级有影响的因素，从而选择适当的客户申请；洗黑钱和其他金融犯罪的侦破是指把多个与侦破工作有关的数据库信息集成起来并利用多种相关分析工具找出其中的异常模式，这样就会有助于侦破人员锁定可疑线索并做进一步处理。２．５．３数据挖掘在电信业中的应用随着计算机技术和通信技术的快速发展，电信业的服务范围迅速扩大，竞争日趋激烈。如何把握住商机并制定相应的营销策略来赢得更多的用户，是目前商家必须考虑的首要问题。将数据挖掘技术应用到电信业中，不仅能够发现新的商机、减少用户营销成本、留住并发展有价值的用户，而且还能够捕捉盗用行为、合理利用资源等【４】。数据挖掘在电信业中的应用主要有电信数据的多维分析、盗用模式分析和异常模式识别等。１４２数据挖掘理论综述２．５．４数据挖掘在零售业中的应用零售业本身较为复杂，在其发展过程中积累了大量且繁琐的销售数据，因此零售业是数据挖掘的主要应用领域之一。挖掘出隐藏在销售数据背后的关联关系有助于商家制定各种相应的营销策略，它也是商家在激烈竞争中处于不败地位的有利武器。数据挖掘在零售业中的应用主要有销售、顾客、产品、时间和地区的多维分析，顾客保持力分析等。２．５．５数据挖掘在信息安全中的应用计算机技术和其他信息处理技术的发展日新月异，网络和系统的安全问题越来越成为人们关注的焦点。为保护信息系统的安全抵御非法行为的入侵，我们希望通过对相关数据进行自动、更高层次的分析，来发现其中具有代表性和概括性的系统特征模式，进而发现新的入侵行为。利用数据挖掘技术我们可以建立一套自适应的且具备优良扩展性能的入侵检测系统，相对于传统的入侵检测系统而言，该系统可以及时有效地发现并阻止非法入侵行为。２．６数据挖掘的社会影响目前，数据挖掘正以一种全新的概念来改变着人类利用数据的方式，我们确实不可以低估它的影响。数据挖掘是我们凭空宣传出来的还是它是真正存在的？数据挖掘作为当今的主流技术它又会碰到哪些障碍呢？既然数据挖掘是发现隐藏在数据背后的有趣知识的过程，那么它会对数据安全和隐私构成威胁吗？下面我们对每个问题做简要分析。２．６．１数据挖掘作为一种商业是否能够持久稳定增长数据挖掘的发展历程和其他技术的发展历程是一样的，都是研究人员在花费大量时间和精力的基础上把一种技术从不为人们所接受转变成人们不仅能够接受而且还能进行很好的应用这样一个过程。数据挖掘的生命周期如图２—４所示，它包括创新者、早期接受者、沟坎、早期多数接受者、后期多数接受者以及落后这六个阶段１４１。目前，有些研究人员认为数据挖掘正处于沟坎阶段。这是因为，虽然市场上出现了很多种功能各异的数据挖掘系统，但是这些数据挖掘系统都只能够解决各种商业应用所表现出来的普遍性问题，即只提供横向解决方案，不能满足特定商业的应用需求。而我们通常关注的则是数据挖掘系统应该具有针对性，它能够对某个特定商业应用所表现出来的特定问题进行解决，即纵向解决方案，最好能做到对症下药。数据挖掘要想“逾越”沟坎，唯一的方法就是把数据挖掘与当今商业技术集成起来。大多数数据挖掘研究人员都一致认为：数据挖掘若要持久稳定地发展下去，唯一的途径就是创建能够提供纵向解决方案的数据挖１５２数据挖掘理论综述掘系统，即把特殊领域的商业技术和数据挖掘系统集成起来。早期创折蓍接受者｝勾坎旦期多数接受者后期多数接受看图２－４技术采纳的生命周期Ｆｉ蜉一４ｌｉｆｅｃｙｅｌｅｏｆｔｅｃｈｎｏｌｏｇｙａｄｏｐｔｉｏｎ２．６．２数据挖掘是知识分子的事还是每个人的事数据挖掘技术有效地帮助了公司管理人员全面、正确地处理市场和商业中的繁多数据，但是数据挖掘不可能成为只由管理人员和商业分析者组成的传统知识分子的专属工具，每个人都有权利使用它。个人可以利用数据挖掘来做的事情有很多，例如，我们可以对家族的医疗史进行挖掘，确定出和遗传有关的医学条件模式，进而重新编排自己的生活方式；我们也可以通过挖掘上市公司的股票或自己所在公司的业绩来进行辅助性的投资。和其他办公软件一样，我们希望可以方便地使用数据挖掘工具，而不需要太多复杂的培训，一些智能软件就可以满足我们的需求。这些软件隐含地把数据挖掘作为它们的功能部件，我们根本感觉不到它的存在，但是却可以有效地帮助我们来执行数据挖掘。２．６．３数据挖掘是否对隐私或数据安全构成威胁任何技术的应用都具有两面性，数据挖掘也不例外，不正确地使用数据挖掘工具有可能对个人隐私和信息安全构成威胁。例如，消费者如果能够得到超市打折回报的话，他（她）将很愿意给超市留下个人信息，这样做的结果就是个人信息很可能会被其他公司收集到，进而有可能给自己带来不便。例如，保险公司若收集到超市某顾客的基本信息以及交易数据的话，它可能根据该顾客购买的食物来确定他（她）的热量消费水平，进而送出相应的保单。因此，为了防止收集数据的误用，很多解决方案被提出用来保证个人数据的安全。相信通过公司和消费者的共同努力，我们一定能够利用好数据挖掘这个工具，使它不仅能够让我们发现新知识，而且还能够为我们节约时间和金钱带来更多的利益。１６２数据挖掘理论综述２．７本章小结数据挖掘作为－－Ｉ＇－Ｊ多学科技术相互融合的新兴学科，有着鲜明的服务性、大众性和利益驱动性。本章首先分别从技术角度和商业角度介绍了数据挖掘的概念，并清楚地说明了“数据挖掘＂与“知识发现’’之间的关系：其次，介绍了数据挖掘的常用知识表示模式及其方法、体系结构、技术支持和应用等；最后，介绍了数据挖掘的社会影响，并指出虽然数据挖掘具有很强的生命力，但是它还存在许多问题，要有待于我们进一步地去分析和研究。３关联规则挖掘研究３关联规则挖掘研究关联规则挖掘是发现大量数据间有趣的关联或相关联系，由Ａｇｒａｗａｌ等人于１９９３年提出，是数据挖掘的热点研究方向之一。“啤酒与尿布”的故事引发了关联规则的产生，在为商家们津津乐道的同时，也使他们从中受到了启发。如今的商家可以利用各种数据处理技术很容易地收集和存储大量的销售数据，他们通过对这些数据进行智能分析来发现顾客购买商品的行为模式，进而利用这种模式来科学地安排进货、库存以及货架设计等。关联规则挖掘在其他领域的应用也很广泛，如关联规则挖掘在生物医学中的应用。医学研究人员希望能够从已有的成千上万份病历中找出患某种疾病的病人的共同特征，期望为治愈这种疾病提供一些解决方法。关联规则挖掘的研究有很多，如关联规则挖掘理论的探索、原有算法的改进及新算法的设计、并行关联规则挖掘等。目前，大多数研究人员对关联规则挖掘的研究主要集中在算法的研究上，对于如何提高算法的效率、适应性和可用性等，研究人员们一直在不懈地努力。３．１关联规则挖掘的相关概念及方法３．１．１关联规则挖掘的相关概念我们通常称关联规则挖掘为事务数据库中的关联规则挖掘，这是因为事务数据库更具普遍性。如超市的交易记录、金融数据等用事务来描述显得更加具体和形象。事务数据库中关联规则的挖掘可做如下描述：设事务数据库Ｄ＝｛＾，ｆ２，…，乙＞是由一组具有唯一标识ＴＩＤ的事务构成，Ｉ＝｛‘，ｆ２，…，０）是Ｄ上的一个项目集合，为全集；每个事务气（Ｊｊ｝＝１，２，…，刀）都对应Ｉ上的一个子集厶，即每个事务都是由若干个项目组成ｆ３】。下面我们就来逐一介绍关联规则挖掘里常用的若干名词。１）项集一个事务由若干个属性来描述，这每一个属性既可以称为字段，也可以称为项；因此，项集我们就可以理解为是属性的集合或字段的集合。若项集里包含ｋ个项，我们就称该项集为ｋ－项集。２）项集的出现频率项集的出现频率是指事务数据库中包含该项集的事务的数目，我们也可以称此数目为项集的支持度计数。３）支持度设Ｉ为事务数据库的项目集合，项目集厶是Ｉ的一个非空子集即１１Ｃ２Ｉ；１１在事务数据库中的支持度是指包含‘的事务数占全体事务数的百分比，即ｓｕｐｐｏｎ（，ｌ酬｛ｆ∈Ｄｌ‘ｃ－，｝Ｉ／ＩＤＪ。１８３关联规则挖掘研究４）频繁项目集、最大频繁项目集对事务数据库Ｄ以及其上的项目集Ｉ，设厶是Ｉ的任意一个非空子集，若厶的支持度大于或等于用户设定的最小支持度（Ｍｉｎｓｕｐｐｏｒｔ），则称正为事务数据库Ｄ的一个频繁项目集（ＦｒｅｑｕｅｎｔＩｔｅｍｓｅｔ）；设厶为事务数据库Ｄ中的任意一个频繁项目集，若厶不被Ｄ中任何一个频繁项目集所包含，则称厶为Ｄ中的最大频繁项目集（ＭａｘｉｍｕｍＦｒｅｑｕｅｎｔＩｔｅｍｓｅｔ）。５）关联规则、可信度设‘和厶分别是项目集Ｉ的两个非空子集，即‘ｃ１，厶ｃ１且有‘ｒ、厶＝ｇ，若‘在满足某种条件下能够推导出厶，即五和厶能够形成形如‘≥厶的蕴涵式，则称该蕴涵式为一条关联规则；正如项目集可以用“支持度＂来表述一样，关联规则可以用“可信度”来表述，可信度是指事务数据库中同时包含厶和厶的事务数与包含厶的事务数之比，即Ｃｏｎｆｉｄｅｎｃｅ（１１ｊ厶）＝ｓｕｐｐｏｒｔ（１１ＵＯ／ｓｕｐｐｏｎ（Ｉ，）。６）强关联规则对事务数据库Ｄ以及其上的项目集Ｉ，若Ｄ中的关联规则同时满足用户指定的最小支持度和最小可信度（Ｍｉｎｃｏｎｆｉｄｅｎｃｅ），则称该关联规则为强关联规则（ＳｔｒｏｎｇＡｓｓｏｃｉａｔｉｏｎＲｕｌｅ），通常我们所说的事务数据库中关联规则的挖掘就是指强关联规则的挖掘。３．１．２关联规则挖掘的方法通常我们称事务数据库中关联规则的挖掘就是指找出满足用户指定的最小支持度和最小可信度的强关联规则的过程。那么我们应该通过什么样的方法来挖掘出事务数据库中的出关联规则呢？一般来说，关联规则的挖掘问题可以划分成这样两个子问题来逐步解决。１）挖掘频繁项目集首先根据用户指定的最小支持度，再采用某种算法找出事务数据库中所有的频繁项目集，即找出支持度大于或等于最小支持度的所有的项目集来构成频繁项目集的集合；然后我们再从所有的频繁项目集中找出那些不被其他频繁项目集所包含的最大频繁项目集，再来构成最大项目集的集合。挖掘出所有的频繁项目集是生成关联规则的前提条件，这一步至关重要；而挖掘出的频繁项目集是否全部都具有实际意义又跟所选取的挖掘频繁项目集算法有很大的联系。因此，第一个子问题是近年来我们研究关联规则挖掘的一个重点问题。２）关联规则的生成根据用户指定的最小可信度，我们可以在频繁项目集的集合里对每一个频繁项目集来寻找可信度大于或等于最小可信度的强关联规则。刚才我们介绍到，第一个子问题是近年来研究关联规则挖掘的重点问题。所以，相对于第一个子问题１９３关联规则挖掘研究而言，第二个子问题就显得比较简单些，且它在内存、Ｉ／Ｏ以及算法效率上没有太大的改进余地【１８１。因此，近年来研究人员将关联规则挖掘的重点主要都放在挖掘频繁项目集算法的研究上，即如何才能快速、高效地挖掘出各种事务数据库中的频繁项目集，为下一步关联规则的生成打好基础。３．２事务数据库中关联规则的挖掘３．２．１经典的挖掘频繁项目集的算法——一Ａｐｒｉｏｆｉ算法挖掘事务数据库中的关联规则分两步进行，第一步就是挖掘出数据库中所有的频繁项目集。Ａｐｆｉｏｒｉ算法是一种最具影响力的挖掘频繁项目集的算法，由Ａｇｒａｗａｌ等人于１９９４年提出，通过该算法挖掘出的关联规则是单维、单层、布尔关联规则【１９１。Ａｐｒｉｏｆｉ算法以Ａｇｒａｗａｌ等人创建的项目集空间理论中的两个核心定理为基础，作为经典的关联规则挖掘理论，这两个定理一直在被广泛地讨论和应用，它们分别如下Ｉ引。定理ｌ如果项目集Ｘ是频繁项目集，那么它的所有非空子集都是频繁项目集。定理２如果项目集Ｘ是非频繁项目集，那么它的所有超集都是非频繁项目集。虽然目前出现了不少关联规则挖掘算法，但是Ａｐｒｉｏｒｉ算法作为经典的关联规则挖掘算法具有里程碑作用，后来的算法大多数都是在原算法的基础上对它进行或多或少地改进而形成的。因此，Ａｐｒｉｏｒｉ算法作为经典的关联规则挖掘算法仍然旧具有很深远的意义。１）基本思想Ａｐｒｉｏｆｉ算法采用逐层搜索的迭代方法，即利用ｋ一频繁项目集来寻找附１）一频繁项目集。首先找出卜频繁项目集的集合厶；其次，厶用来寻找２一频繁项目集的集合厶，而厶用来寻找厶，如此下去，直到不能找到ｋ一频繁项目集的集合厶为止；最后再将所有的频繁项目集的集合进行合并【４】。寻找每一个厶都需要对数据库扫描一次。其中，厶一，用于寻找厶（ｋ≥２）可划分为这样两个步骤：一是先由厶一，寻找ｋ一候选集的集合Ｇ，进而扫描事务数据库对Ｇ中的每个ｋ－候选集进行支持度计数；二是从Ｑ中挑选出支持度计数大于或等于最小支持度计数的ｋ．候选集来构成厶。而厶一。寻找Ｇ又由连接和剪枝这两步组成：连接是指厶一的自身连接，得到可能的ｋ一候选集的集合ｑ：剪枝是指利用项目集空间理论中的核心定理，即定理ｌ和定理２来删除Ｇ中那些（ｋ一１）一子集不在厶一，中的ｋ－候选集。２）算法描述算法１Ａｐｄｏｒｉ算法【２０１（挖掘频繁项目集）。３关联规则挖掘研究输入：事务数据库Ｄ；最小支持度计数：ｍｉｎｓｕｐ＿ｃｏｕｎｔ。输出：频繁项目集的集合Ｌ。（１）厶＝｛ｌａｒｇｅ卜ｉｔｅｍｓｅｔｓ｝；（２）ＦＯＲ（ｋ＝２；厶一ｌ≠ｇ；ｋ＋＋）ＤＯ（３）（４）（５）（６）（７）（８）（９）ＥＮＤＥＮＤ／／卜频繁项目集的集合ＢＥＧＩＮＧ＝ａｐｒｉｏｒｉ—ｇｅｎ（Ｌｋ—１）；／／Ｇ是ｋ＿候选集的集合ＦＯＲａｌｌｔｒａｎｓａｃｔｉｏｎｓｔ∈ＤＤＯＢＥＧＩＮＧ＝ｓｕｂｓｅｔ（ｑ，ｔ）；ＦＯＲａｌｌｃａｎｄｉｄａｔｅｓｃ∈ＣｆＤＯｃ．ｃｏｕｎｔ＋＋；丘＝｛ｃ∈Ｇｌｃ．ｃｏｕｎｔ≥ｒｒｆｉｎｓｕｐ＿ｃｏｕｎｔ｝；（１０）Ｌ＝Ｕ厶；算法２ａｐｒｉｏｒｉ—ｇｅｎ（Ｌｋ—１）（候选集产生）。输入：（ｋ—１）一频繁项目集厶一。。输出：卜候选集的集合Ｑ。（１）ＦＯＲａｌｌｉｔｅｍｓｅｔｐｅ厶一ｌ（２）（３）ＦＯＲａｌｌｉｔｅｍｓｅｔＤＯＤＯｑｅ厶－１ＩＦｐｄｔｅｒ啊＝ｑＪｔｅｍｌ，ｐｉｔｅｍ２＝ｑｄｔｅｍ２，一＂，ｐ２ｔｅｍｋ＿２＝ｑ２ｔｅｍｋ＿２，ｐ，ｉｔｅｍｋｑ＜ｑ２ｔｅｒ唿ｑＴＨＥＮＢＥＧＩＮ（４）（５）ｃ＝ｐｏｏｑ；／／把ｑ的第（ｋ－－１）个元素连到Ｐ后ＩＦｈａｓｉｎｆｒｅｑｕｅｎｔ＿ｓｕｂｓｅｔ（ｃ，厶一１）ＴＨＥＮ（６）ｄｅｌｅｔｅｃ；∥删除（ｋ－－１）一子集不在厶一ｌ中的ｋ－候选集（７）（８）ＥＮＤＥＬＳＥａｄｄｃｔｏＧ；（９）Ｒｅｔｕｒｎｑ；算法３ｈａｓ＿ｉｎｆｒｅｑｕｅｎｔ＿ｓｕｂｓｅｔ（ｃ，厶一１）（ｃ是否为ｋ一频繁项目集的判断）。输入：一个ｋ－候选项目集ｃ，（ｋ一１）一频繁项目集的集合厶一。。输出：ｃ是否从Ｇ中删除的判断。（１）ＦＯＲａｌｌ（ｋ一１）一ｓｕｂｓｅｔｓｏｆｃＤＯ（２）ＩＦＳ芒厶－１ＴＨＥＮＲｅｔｕｒｎＴＲＵＥ；（３）ＲｅｔｕｒｎＦＡＬＳＥ；３）举例说明例１、对表３－１所示的事务数据库Ｄ利用Ａｐｆｉｏｒｉ算法求出所有的频繁项目集，设ｍｉｎｓｕｐｐｏｒｔ＝５０％。２１３关联规则挖掘研究表３－１事务数据库ＤＴａｂｌｅ３一ｌｔｒａｎｓａｃｔｉｏｎＤａｔａｂａｓｅＴＩＤＩｒｅｍｓｅｔ五乏互正｛ＫＡ，Ｄ，Ｂ｝｛ＤＡ，Ｃ，Ｅ，Ｂ）｛ＣＡ，Ｂ，Ｅ）｛ＢＡ，Ｄ）解：由于ｍｉｎｓｕｐｐｏｒｔ＝５０％，所以最小支持度计数为４＊５０％＝２。（１）厶的生成扫描事务数据库生成卜候选集的集合Ｇ，并对Ｃｌ中的每个候选集进行支持度计数，得出Ｃ；＝｛敞４）），徊（４）），｛∞），徊（３）），伍（２）），儆１）））（括号里的数字表示候选集的支持度计数，以下类同）。挑选出支持度计数＞１２的候选集组成卜频繁项目集的集合厶＝｛∽，鼢，鼢，㈣，旧）。（２）厶的生成首先由厶生成Ｃ２。连接：厶吗一｛∽毋，似６３，Ｍ踢，似目，假Ｏ，假四，缇毋，晒毋，犯目，但毋）。剪枝：很容易看出，连接后的集合中每个２一候选集其所有卜子集都在厶中，所以不必删除。所以Ｇ＝｛“壤“Ｑ似壤“壤饵Ｑ饵Ｚｔ，饵毋｛ｃ壤｛Ｇ目，但目），扫描数据库进行计数，Ｇ＝｛“粥｝，“∞｝’“∞），似翰），饵∞），假∞｝，饵翰），｛ｃ∞），犯翰），但珊｝）。挑选出支持度计数＞／２的候选集，则厶＝｛以壤“Ｑ“协“母但ｑ，假ｚｔ，但母，钙助。（３）厶的生成首先由厶生成Ｇ。连接：局鸣＝｛“尽Ｑ以尽毋，似且毋以Ｇ毋，“Ｇ毋“忍目，｛Ｒｅ；ｚ１，假Ｇ目，饵日目）。剪枝：通过分析，只有Ｍ忍Ｃ’，托忍研，托忍毋，以Ｃ，毋，饵Ｇ毋这五个３一候选集它们的所有２一子集都在厶中。所以得出Ｇ＝｛似置Ｃ｝，似忍毋，似忍毋，似Ｇ目，饵Ｇ目），扫描数据库对每个候选集计数得出Ｇ＝｛似Ｒｃｉ２）｝，似忍聊），似尾鹚），ＭＧ翰＞，缇Ｇ段２）））。挑选出支持度计数＞１２的候选集，则厶＝｛似恳Ｑ似恳毋，Ｈ尽毋似Ｇ毋，饵Ｇ目＞。（４）厶的生成首先由厶生成Ｇ。连接：厶鸣＝｛似层Ｇ玩似忍Ｇ毋，似忍忍毋，。剪枝：通过分析，只有似置Ｇ毋这个４一候选集它的所有３一子集都在厶中。３关联规则挖掘研究因此Ｇ＝｛似ａＧＥ）｝，扫描数据库对每个候选集计数得出Ｇ＝｛∽ＥＧ翰＞＞。从Ｃ４中挑选出支持度计数ｔ＞２的候选集组成厶。则厶＝｛似尽Ｇ毋）。（５）厶的生成首先由厶生成Ｇ。连接：厶鸣＝｛似晟Ｃ目Ｍ托马Ｃ毋）＝ａ。因此Ｇ＝ｏ，厶＝ｆ２ｊ，算法停止。所有的频繁项目集为各个频繁项目集的集合。所以，最大频繁项目集为｛似马Ｃ，毋，似忍四）。４）性能瓶颈问题Ａｐｒｉｏｒｉ算法作为经典的挖掘频繁项目集的算法，在关联规则的生成过程中起到了重要的作用。但是随着应用的加深，Ａｐｒｉｏｒｉ算法自身的局限性也逐步暴露出来，它主要存在以下瓶颈问题。（１）需要对事务数据库进行多次扫描，并且造成很大的Ｉ／Ｏ开销对每一次生成的ｋ－候选集的集合ｑ，都需要扫描数据库多次以便得到其中每个ｋ－候选集的支持度计数，进而判断它是否能添加到厶中。就大型事务数据库而言，每次生成的Ｇ中必然包括数量很多的ｋ－候选集，ｋ－候选集的个数也就决定了扫描数据库的次数，这样会大大增加Ｉ／Ｏ开销，降低挖掘效率。（２）可能产生庞大的候选集根据Ａｐｒｉｏｒｉ算法的思想，每一次由厶一。生成厶必须先要经过厶ｑ的自身连接这个步骤，这样每一次就会产生数量庞大的ｋ－候选集。如此庞大的候选集对时间和空间都是一种挑战，直接影响着关联规则的挖掘效率。（３）最小支持度的选取在Ａｐｒｉｏｒｉ算法中，最小支持度的选取也是一个关键问题，因为它是决定挖掘出的关联规则是否具有价值的一个重要因素。如果选取的最小支持度过大，则可能会丢弃掉一些有用的频繁项目集；如果选取的最小支持度过小，则可能会挖掘出较多的没有意义的频繁项目集。无论选取的最小支持度是大还是小，都会直接影响着关联规则的生成。５）前人对Ａｐｒｉｏｒｉ算法的改进（１）基于划分（ｐａｒｔｉｔｉｏｎ）的方法该方法是先把数据库分成多个互不相交的逻辑块，并用Ａｐｒｉｏｒｉ算法求出每块的频繁项目集来作为局部频繁项目集；然后测试每个局部频繁项目集的支持度以便找出适当的支持度来生成全局频繁项目集１３１。划分方法使得只需要扫描数据库两次便可挖掘出全局频繁项目集，如图３－１所示。另外，利用划分技术在合理利用空间、支持并行挖掘算法这两方面都起到了很好的作用。这是因为，数据块可被一次性地导入内存，提高了挖掘的效率；数据库划分为若干块后，由不同的３关联规则挖掘研究处理器并行完成局部频繁项目集的挖掘工作，为开发并行数据挖掘算法提供了良好的应用基础。虽然基于划分的方法在一定程度上提高了挖掘效率，但是它也有不足之处。例如，并行处理器之间要进行通信，而在通信过程中时间是主要的瓶颈；另一方面，每个并行处理器生成频繁项目集的时间也是一个瓶颈。所以，这些问题还有待于我们迸一步去解决。阶段Ｉ阶段Ⅱ将Ｄ划Ｄ中喜务找出局部于每一部分的频繁项集（１故扫描）结合局部频繁项集形成候选项集在候选项集中找出全局频繁项集（１谈扫描）Ｄ中频繁项集分成ｎ部分图３一ｌ通过划分数据进行挖掘Ｆｉ９３—１ＤａｔａＭｉｎｉｎｇｂｙｐａｒｔｉｔｉｏｎ（２）基于散列（Ｈｕｓｈ）的方法Ｐａｒｋ等人于１９９５年通过实验发现挖掘频繁项目集的计算主要在２一频繁项目集的集合厶的生成上，因此，他们在Ａｐｒｉｏｒｉ算法中引入散列技术来改进生成２一频繁项目集的方法。基于散列的方法是先把扫描的项目放入不同的Ｈｕｓｈ桶中，每个桶中只能存放一对特定的项目；然后通过测试桶中的项目来达到降低候选集生成代价的目的【３】。经过实验验证，我们发现这种方法也可以应用到其他ｋ一频繁项目集的生成上。（３）基于采样（Ｓａｍｐｌｉｎｇ）的方法Ｔｏｉｖｏｎｅｎ于１９９６年提出了用于改进Ａｐｒｉｏｒｉ算法的基于采样的方法。该方法是先从数据库Ｄ中随机抽取大小适中的数据样本Ｓ；然后在Ｓ上进行频繁项目集的挖掘，且只需要扫描一次Ｓ即可［４１。虽然基于采样的方法提高了频繁项目集的挖掘效率，但是精度较低。由于是在数据样本Ｓ中而非数据库Ｄ中挖掘频繁项目集，这样有可能会丢失一些全局频繁项目集。因此，我们可以先利用比最小支持度低的支持度闽值来找出数据样本Ｓ中的频繁项目集的集合Ｆ，ｒ即为局部频繁项目集；然后再利用数据库Ｄ的剩余部分计算出ｒ中每个频繁项目集的支持度计数。如果ｒ已经包含了Ｄ中的所有频繁项目集，则只需要扫描一次Ｄ即可；否则，要对数据库Ｄ进行第二次扫描，以便找出第一次扫描时遗漏的频繁项目集。２４３关联规则挖掘研究３．２．２由频繁项目集生成关联规则１）生成步骤・找出每一个频繁项目集ｌ的所有的非空子集。・求出ｌ的每一个非空子集Ｘ的可信度Ｃｏｎｆｉｄｅｎｃｅ（ｘ），若Ｃｏｎｆｉｄｅｎｃｅ（ｘ）≥ｍｉｎｃｏｎｆｉｄｅｎｃｅ，则蕴涵式ｘｊ（１一ｘ）成立。２）算法描述算法１Ｒｕｌｅ—ｇｅｎｅｒａｔｅ（Ｌ，ｍｉｎｃｏｎｔ３【２１１（强关联规则的生成）。输入：频繁项目集的集合；最小信任度ｍｉｎｃｏＲｆｏ输出：强关联规则。（１）ＦＯＲｅａｃｈｆｒｅｑｕｅｎｔ（２）ｉｔｅｍｓｅｔ厶ｉｎＬｇｅｎｒｕｌｅｓ（厶，＆）；ｂｉｔｅｍｓｅｔ，ｘｍ：ｆｒｅｑｕｅｎｔ算法２ｇｅｎｍｌｅｓ（１ｋ：ｆｒｅｑｕｅｎｔｍ－ｉｔｅｍｓｅｔ）（测试步骤）。（１）ｘ＝｛（ｍ一１）－－ｉｔｅｍｓｅｔｓ‰一ｌ（２）ＦＯＲｅａｃｈ‰一ｌｉｎＸＢＥＧＩＮ（３）（４）Ｉ靠一ｌ／ｎ‰）；ｃｏｎｆ＝ｓｕｐｐｏｒｔ（Ｉｋ）／ｓｕｐｐｏｒｔ（ｘ．一１）；ＩＦ（ｃｏｎｆ－＞ｍｉｎｃｏｎｆ）ＴＨＥＮＢＥＧＩＮ（５）ｐｒｉｎｔｔｈｅ（６）（７）（８）（９）ＥＮＤＥＮＤｒｕｌｅ＇’钿砘～），ｗｉｔｈｓｕｐｐｏｒｔ＝ｓｕｐｐｏｒｔ（１ｋ），ｅｏｎｆｉｄｅｎｃｅ＝ｃｏｎｆ＇’；ＩＦ（ｍ一１＞１）ＴＨＥＮｇｅｎｒｕｌｅｓ（‘，‰一１）；３）举例说明例２、对例１生成的最大频繁项目集使用Ｒｕｌｅ—ｇｅｎｅｒａｔｅ算法生成强关联规则，设ｍｉｎｃｏｎｆｉｄｅｎｃｅ＝８０％。（为了不失一般性，在这里我们只讨论最大频繁项目集的情况。）解：例１生成的最大频繁项目集为｛｛Ａ，Ｂ，Ｃ，Ｅ＞，｛Ａ，Ｂ，Ｄ）＞，表３—２给出了关联规则生成过程。３关联规则挖掘研究表３－２关联规则生成过程示意图序号ｌ２３４５６７８９１０１１１２１３１４１５１６１７１８１９２０厶ＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＣＥＡＢＤＡＢＤＡＢＤＡＢＤＡＢＤＡＢＤＸｍ一１ｃｏｎｆｉｄｅｎｃｅ规则（是否为ｓｕｐｐｏｒｔ强规则）ＡＢＣＥＡＢＡＣＡＥＢＣＢＥＣＥＡＢＣＡＢＥＡＣＥＢＣＥＡＢＤＡＢＡＤＢＤ５０％５０％１００％１００％５０％１００％１００％１００％１００％１００％１００％１００％１００％１００％７５％７５％１００％７５％１００％１００％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％５０％ＡｊＢＣＥ（否）ＢｊＡＣＥ（否）ＣｊＡＢＥ（是）Ｅ≥ＡＢＣ（是）ＡＢｊＣＥ（否）ＡＣｊＢＥ（是）ＡＥ≥ＢＣ（是）ＢＣｊＡＥ（是）ＢＥｊＡＣ（是）ＣＥｊＡＢ（是）ＡＢＣ≥Ｅ（是）ＡＢＥｊＣ（是）ＡＣＥｊＢ（是）ＢＣＥ＝＞Ａ（是）Ａ≥ＢＤ（否）ＢｊＡＤ（否）ＤｊＡＢ（是）ＡＢｊＤ（否）ＡＤｊＢ（是）ＢＤｊＡ（是）３．３不产生候选集的关联规则挖掘算法—叫Ｐ—ｇｒｏｗｔｈ算法针对Ａｐｄｏｄ算法重复扫描数据库和可能产生庞大候选集的缺点，２０００年ＪｉａｗｅｉＨａｎ等人提出了频繁模式增长（能ｑｕｅＩｌ＿ｔ＿ｐ舭ｎｇｒｏｗｔｈ）算法，或简称ＦＰ－ｇｒｏｗｔｈ算法。该算法只扫描数据库两次且不产生候选集，直接把数据库压缩成一个频繁模式树，打破了Ａｐｒｉｏｆｉ算法生成频繁项目集的固有模式，有效地提高了频繁项目集的挖掘效率。然后，再根据这棵频繁模式树来生成关联规则。３．３．１基本思想ＦＰ－ｇｒｏｗｔｈ算法采用分而治之的策略。首先扫描数据库两次，将数据库中数据所包含的各个项目作为树节点来形成一棵频繁模式树，即ＦＰ－ｔｒｅｅ；然后再对这棵ＦＰ一仃ｅｅ进行挖掘，找出其中的频繁模式【４】。３．３．２算法描述算法：ＦＰ—ｇｒｏｗｔｈ算法【２２】（使用ＦＰ一树挖掘频繁模式）。输入：事务数据库Ｄ；最小支持度ｍｉｌｌ３关联规则挖掘研究输出：所有的频繁模式。１）按下列步骤构造ＦＰ—ｔｒｅｅ（１）扫描一次事务数据库Ｄ，找出卜频繁项目集的集合Ｆ以及其中每个卜频繁项目集的支持度计数。对Ｆ按支持度计数降序排序，结果为卜频繁项目集列表Ｌ。（２）创建ＦＰ－ｔｒｅｅ的根节点，用“ｎｕｌｌ＂来表示。对于数据库Ｄ中的每个事务Ｔｒａｎｓ，来执行下面步骤。提取Ｔｒａｎｓ中的频繁项目集，且按Ｌ中的顺序来排序。设排序后的频繁项目集列表为Ｉｐｌ尸Ｉ，其中，Ｐ是第一个元素，而Ｐ是剩余元素的列表。调用ｉｎｓｅｒｔｔｒｅｅ（１ｐｌＰｌ，Ｔ）。该过程执行情况如下：如果Ｔ有一个子女Ｎ并且Ｎ．ｉｔｅｍ—ｎａｍｅ＝ｐ．ｉｔｅｍ—ｎａｍｅ，则Ｎ的计数增加１；否则创建一个新节点Ｎ，将其计数设置为ｌ，链接到它的父节点Ｔ，并且通过节点链将其链接到具有相同ｉｔｅｍ－ｎａｍｅ的节点上。如果Ｐ非空，递归地调用ｉｎｓｅｒｔ２）调用ＦＰｇｒｏｗｔｈ（ＦＰＰｒｏｃｅｄｕｒｅ，ｅｒｎｕｌｌｔ．掘挖的ｅ咄ＰＦ现实来）ＦＰ＿ｇｒｏｗｔｈ（Ｔｒｅｅ，Ｑ）ｔｈｅｎ（１）ｉｆＴｒｅｅ含单个路径Ｐ（２）（３）ｆｏｒ路径Ｐ中节点的组合（记作１３）产生模式１３ｕＣＩ．，其支持度计数ｓｕｐｐｏｒｔ小支持度计数；（４）ｅｌｓｅｆｏｒ（５）（６）（７）（８）ｅａｃｈａｌ在Ｔｒｅｅ的头部｛Ｕ产生模式１３＝ｑＱ，其支持度计数ｓｕｐｐｏｒｔ＿ｃｏｕｎｔ＝ａｔ．ｓｕｐｐｏｒｔ＿ｃｏｕｎｔ；构造１３的条件模式基，然后构造Ｂ的条件ＦＰ．ｔｒｅｅＴｒｅｅ日；ｉｆＴｒｅ＆≠０ｔｈｅｎ调用ＦＰ＿＿ｇｒｏｗｔｈ（Ｔｒｅｅｐ，１３）；）３－３．３举例说明例３、对表３－１所示的事务数据库Ｄ使用ＦＰ—ｇｒｏｗｔｈ算法求出频繁模式，设ｍｉｎｓｕｐｐｏｒｔ＝５０％。解：由于ｍｉｎｓｕｐｐｏｒｔ＝５０％，所以最小支持度计数为４＊５０％＝２。１）ＦＰ－树的构造（１）第一次扫描表３—１所示的事务数据库，得出卜频繁项目集的集合Ｌ以及每个卜频繁项目集的支持度计数。Ｌ按支持度计数递减排序，则Ｌ＝｛Ａ：４，Ｂ：４，Ｄ：３，Ｃ：２，Ｅ：２），（冒号后面的数字为卜频繁项目集的支持度计数）。（２）构造ＦＰ－树首先创建树的根节点，记作ＮＵＬＬ。第二次扫描数据库，每个事务中的项按３关联规则挖掘研究Ｌ中的顺序排序，为每个事务创建一个分支。事务一中的项为“ＫＡ，Ｄ，Ｂ”，由于Ｋ的支持度计数为１小于最小支持度计数２，因此Ｋ在事务一中应被删去。所以，此时事务一中的项为“Ａ，Ｄ，Ｂ’’，按Ｌ中的顺序应为“八Ｂ，Ｄ”，创建树的第一个分支＜（Ａ：１），（Ｂ：Ｉ），（Ｄ：１）＞，Ａ链接到根节点，Ｂ链接到Ａ，Ｄ链接到Ｂ。此时树如图３－２所示。ＨＵⅢ）图３－２树的第一个分枝的产生Ｆｉ驴－２ｇｅｎｅｒａｔｉｏｎｏｆｔｈｅｆｉｒｓｔｂｒａｎｃｈｏｆｔｒｅｅ事务二中的项为“ＤＡ，Ｃ，Ｅ，Ｂ’’，按Ｌ中的顺序应为“Ａ，Ｂ，Ｄ，Ｃ，Ｅ”，为事务二创建分支，Ａ链接到根节点，Ｂ链接到Ａ，Ｄ链接到Ｂ，Ｃ链接到Ｄ，Ｅ链接到Ｃ。但是该分支应与事务一已存在的路径共享前缀＜Ａ，Ｂ，Ｄ＞，所以将节点Ａ，Ｂ，Ｄ的计数分别增加ｌ。此时树如图３－３所示。ＮＩ几“）图３－３树的第二个分枝的产生Ｆｉ够一３ｇｅｎｅｒａｔｉｏｎｏｆｔｈｅｓｅｃｏｎｄｂｒａｎｃｈｏｆｔｒｅｅ３关联规则挖掘研究因此，在为事务创建分支时，若有共同前缀则共同前缀上的每个节点的计数分别增加１，为跟随在前缀之后的项创建节点并链接。事务三中的项为“ＣＡ，Ｂ，Ｅ”，按Ｌ中的顺序应为“Ａ，Ｂ，Ｃ，Ｅ＂；事务四中的项为“Ｂ，气Ｄ＂，按Ｌ中的顺序应为“Ａ，Ｂ，Ｄ”，分别为这两个事务创建分支。所以，为事务三创建分支，树如图３—４所示。卜ｒＯＬＬＯ图３＿４树的第三个分枝的产生Ｆｉ９３－４ｇｅｎｅｒａｔｉｏｎｏｆｔｈｅｎＩＭｂｒａｎｃｈｏｆｔｒｅｅ为事务四创建分支，树如图３—５所示。ＮＵ姒）Ｄ：３图３－５树的第四个分枝的产生Ｆｉ９３—５ｇｅｎｅｒａｔｉｏｎｏｆｔｈｅｆｏｕｒｔｈｂｒａｎｃｈｏｆｔｒｅｅ２９３关联规则挖掘研究因此，为了方便树的遍历，我们可以创建一个项头表，使得表中每个项都能通过一个节点链指向它在树中出现的位置。所以，扫描完所有的事务之后得到的ＦＰ－树如图３－６所示，且带有指向树中节点的节点链。因此，数据库频繁模式的挖掘问题就转换成了ＦＰ一树的挖掘问题。项Ｄ●－～，，＿Ｉ●●－－●●●●－，●图３－６存放压缩频繁模式的ＦＰ－树Ｆｉ９３—６ＦＰ－ｔｒｅｅｏｆｓｔｏｒａｇｉｎｇｆｒｅｑｕｅｎｔｐａｔｔｅｒｎ２）ＦＰ－树的挖掘首先从计数为１的频繁模式（计数为１的项节点）开始，构造该频繁模式的条件模式基：然后再构造它的（条件）ＦＰ－树，并递归地在该树上进行挖掘。Ｅ：参照ＦＰ一树，Ｅ的路径由分枝＜（ＡＢＣＥ：１）＞和分枝＜（ＡＢＤＣＥ：１）＞构成，所以Ｅ的条件模式基是｛（ＡＢＣ：Ｉ），（ＡＢＤＣ：Ｉ））。由于Ｄ的支持度计数是１，小于最小支持度计数，因此Ｅ的条件ＦＰ．树为＜Ａ：２，Ｂ：２，Ｃ：２＞。所以，产生的频繁模式为：ＡＥ：２，ＢＥ：２，ＣＥ：２，ＡＢＥ：２，ＡＣＥ：２，ＢＣＥ：２，ＡＢＣＥ：２。Ｃ：参照ＦＰ－树，Ｃ的路径由分枝＜（ＡＢＣ：１）＞和分枝＜（ＡＢＤＣ：Ｉ）＞构成，所以Ｃ的条件模式基是｛（ＡＢ：Ｉ），（ＡＢＤ：Ｉ）｝。由于Ｄ的支持度计数是１，小于最小支持度计数，因此Ｃ的条件ＦＰ一树为＜Ａ：２，Ｂ：２＞。所以，产生的频繁模式为：ＡＣ：２，ＢＣ：２，ＡＢＣ：２。Ｄ：参照ＦＰ一树，Ｄ的路径由分枝＜（ＡＢＤ：３）＞构成，所以Ｄ的条件模式基是｛（ＡＢ：３））。因此Ｄ的条件ＦＰ一树为＜Ａ：３，Ｂ：３＞。所以，产生的频繁模式为：ＡＤ：３，ＢＤ：３，ＡＢＤ：３。Ｂ：参照ＦＰ一树，Ｂ的路径由分枝＜（ＡＢ：４）＞构成，所以Ｂ的条件模式基是｛（Ａ：４）｝。因此Ｂ的条件ＦＰ．树为＜Ａ：４＞。所以，产生的频繁模式为：ＡＢ：４。３０３关联规则挖掘研究最后得出ＦＰ－树的挖掘如表３—３所示。表３－３通过创建条件模式基挖掘ＦＰ一树Ｔａｂｌｅ３－３ＦＰ－ｔｒｅｅｍｉｎｉｎｇｂｙｃｒｅａｔｉｎｇｃｏｎｄｉｔｉｏｎａｌｐａｔｔｅｒｎｂａｓｅＩｒｅｍＥＣＤＢ条件模式基｛（ＡＢＣ：Ｉ），（ＡＢＤＣ：Ｉ））｛（ＡＢ：１），（ＡＢＤ：１），｛（ＡＢ：３））｛（Ａ：４））条件ＦＰ一树＜Ａ：２，Ｂ：２，Ｃ：２＞产生的频繁模式ＡＥ：２，ＢＥ：２，ＣＥ：２，ＡＢＥ：２，ＡＣＥ：２，ＢＣＥ：２，ＡＢＣＥ：２ＡＣ：２，ＢＣ：２．，ＡＢＣ：２ＡＤ：３．ＢＤ：３，ＡＢＤ：３ＡＢ：４＜Ａ：２．Ｂ：》≮Ａ：３．Ｂ：３＞＜Ａ：４＞３．３．４算法性能分析１）ＦＰ－ｇｒｏｗｔｈ算法的优点（１）ＦＰ—ｇｒｏｗｔｈ算法将含有大量数据的数据库压缩成远远小于它且密度高的树结构，大大降低了挖掘频繁模式的时间和空间开销，并且只需扫描数据库两次就能产生频繁模式。在树结构中，该算法将最不频繁的项作为后缀（叶节点），提供了较好的选择性。（２）ＦＰ—ｇｒｏｗｔｈ算法对于挖掘长或短的频繁模式问题都是有效的和可伸展的。该算法比Ａｐｒｉｏｒｉ算法大约快一个数量级；同时，它也比树一投影算法快。（３）ＦＰ—ｇｒｏｗｔｈ算法创造性地使用了分而治之的策略，通过把数据库压缩成树结构来减小问题的规模。另外，该算法将发现长频繁模式的问题转换成递归地搜索一些较短模式、然后连接后缀的问题，避免了庞大候选集的产生。２）ＦＰ—ｇｒｏｗｔｈ算法的缺点如果提供频繁项目集的数据库比较大，那么根据算法构造而成的ＦＰ－树不仅会有非常多的分枝，而且这些分枝还会很长，进而就需要构造出数量巨大的条件ＦＰ一树。这样不仅耗费时间，而且还要占用大量的存储空间，最终导致挖掘效率的低下。另外，由于递归算法的自身原因，也会使得挖掘效率比较低。３．３．５实验结果与分析对Ａｐｒｉｏｒｉ和ＦＰ—ｇｒｏｗｔｈ这两种关联规则挖掘算法进行详细地说明后，现在我们通过一个实验来比较这两种算法的运行时间。我们固定最小支持度，考察不同交易数目下两种算法的运行时间。征得超市负责人的同意后，我们获取了６０００条交易数据。实验中使用的计算机的基本配置是Ｉｎｔｅｌ１ＧＢＰｅｎｔｉｕｍ４２．０ＧＨＺ处理器，ＤＤＲ内存，１２０ＧＩＤＥ硬盘，在ＷｉｎｄｏｗｓＸＰ操作系统和ＭｉｃｒｏｓｏｆｔＳＱＬＳｅｒｖｅｒ２００５系统环境的基础上，我们采用ＶＢ．ＮＥＴ来编程。设定最小支持度为２．５％，则实验结果如图３—７所示。３关联规则挖掘研究图３－７不同交易数下两种算法的运行时间Ｆｉ９３—７ｅｘｅｃｕｔｉｏｎｔｉｍｅｏｆｔｗｏａｌｇｏｒｉｔｈｍｓｏｆｄｉｆｆｅｒｅｎｔｔｒａｎｓａｃｔｉｏｎｎｕｍｂｅｒ从上图中我们可以看出，当交易数目为２０００时，Ａｐｄｏｎ算法和ＦＰ－ｇｒｏｗｔｈ算法的运行时间大致相同，但ＦＰ—ｇｒｏｗｔｈ算法的运行时间要稍微短些。随着交易数目的不断增加，这两种算法的运行时间有了明显的不同。当交易数目逐步增加时，Ａｐｒｉｏｒｉ算法运行时间的变化幅度比较大且运行时间远大于ＦＰ－ｇｒｏｗｔｈ算法，而ＦＰ—ｇｒｏｗｔｈ算法运行时间的变化幅度比较小。这也再一次说明了ＦＰ—ｇｒｏｗｔｈ算法相对于Ａｐｒｉｏｒｉ算法较适合于大型事务数据库中关联规则的挖掘。３．４其他关联规则挖掘算法——Ｃｌｏｓｅ算法Ｐａｓｑｕｉｅｒ等人于１９９９年创建了闭合项目集挖掘理论。在该理论中，他们首次提出了闭合项目集的概念，同时也探讨了闭合项目集格空间上的基本操作算子。基于这种挖掘理论，随后他们又提出了Ｃｌｏｓｅ算法，该算法不仅能够加速频繁项目集的产生，而且也能够有效地减少数据库的扫描次数。３．４．１基本思想实际上，Ｃｌｏｓｅ算法是Ａｐｒｉｏｒｉ算法的一种改进，它也采用逐层搜索的迭代方法即利用闭合频繁ｉ一项目集，记为ＦＣ，，来生成闭合频繁（ｉ＋１）一项目集，记为ＦＣ，＋。（》＝１）。首先生成ＦＣ，；其次由ＦＣ，生成ＦＣ２，ＦＣ２生成ＦＣａ，如此进行下去，直到出现某个值ｒ使得候选闭合频繁ｒ项目集ＦＣＣ，为空；最后，再将所有的频繁闭合项目集进行合并得到ＦＣ。３．４．２算法描述算法ｌＣｌｏｓｅ算法【２３１（闭合项目集挖掘算法）。３２３关联规则挖掘研究（１）ｇｅｎｅｒａｔｏｒｓｉｎ尺■＝｛１一ｉｔｅｍｓｅｔｓ｝；（２）ＦＯＲ（ｉ＝１；只墨．ｇｅｎｅｒａｔｏｒｓ＝①；ｉ＋＋）ＤＯＢＥＧＩＮ（３）（４）ｃｌｏｓｕｒｅｓｉｎｓｕｐｐｏｒｔｓＦＣＣ，＝①；ｉｎ肥Ｃ＝ｏ；（５）尺■＝Ｇｅｎ＿Ｃｌｏｓｕｒｅ（尺一）；（６）（７）（８）ＦＯＲａｌｌｃａｎｄｉｄａｔｅｃｌｏｓｅｄｉｔｅｍｓｅｔｓＣ∈月Ｉ咒ＤＯＢＥＧＩＮｒＦ（ｃ．ｓｕｐｐｏｒｔ＞＝ｍｉｎｓｕｐｐｏｒｔ）ＴＨＥＮＥＮＤＫ＝心ｕ｛ｃ）；∥生成ＦＣＣｔ＋ｌ（９）尺一＋ｌ＝Ｇｅｎ＿Ｇｅｎｅｒａｔｏｒ（ＦＣ＿ｆ）；００）ＥＮＤＯＤＦＣ＝ｔＯｆＦＣ，（ＦＣ，．ｃｌｏｓｕｒｅ，Ｆｑ．ｓｕｐｐｏｒｔ）ｆｒｅｑｕｅｎｔ／／返回ＦＣ∞Ｄｅｒｉｖｉｎｇｉｔｅｍｓｅｔｓ（ＦＣ，Ｌ）；‘ｆｒｅｑｕｅｎｔＧｅｎ＿Ｃｌｏｓｕｒｅ（肥Ｇ）、Ｇｅｎ＿Ｇｅｎｅｒａｔｏｒ（％）和Ｄｅｒｉｖｉｎｇ它们每一个分别进行描述。算法２Ｇｅｎｉｔｅｍｓｅｔｓ是Ｃｌｏｓｅ算法中的三个重要函数。为了正确、深入地理解Ｃｌｏｓｅ算法，我们需要对Ｃｌｏｓｕｒｅ函数。（１）ＦＯＲ２Ｌｌｌｔｒａｎｓａｃｔｉｏｎｓｔ∈ＤＤＯ（２）（３）（４）（５）ＢＥＧＩＮＢＥＧＩＮＧｏ＝Ｓｕｂｓｅｔ（ＦＣＣｆ．ｇｅｎｅｒａｔｏｒ，ｔ）；ＦＯＲａｌｌｇｅｎｅｒａｔｏｒｓＰ∈ＧｏＤＯＩＦ（ｐ．ｃｌｏｓｕｒｅ＝①）ＴＨＥＮｐ．ｃｌｏｓｕｒｅ－－ｔ；ＥＬＳＥＰ．ｃｌｏｓｕｒｅ＝ｐ．ｃｌｏｓｕｒｅｎｔ；（６）Ｐ．ｓｕｐｐｏｒｔ＋＋；（７）ＥＮＤ（８）ＥＮＤ（９）Ａｎｓｗｅｒ＝Ｕ｛ｃｅ尺■ｌｃ．ｃｌｏｓｕｒｅ：／：中，；算法３ＧｅｎＧｅｎｅｒａｔｏｒ函数。ＢＥＧＩＮ（１）ＦＯＲａｌｌｇｅｎｅｒａｔｏｒｓｐＣＦＣＣｊ＋ｌＤＯ（２）（３）（４）Ｓｐ＝Ｓｕｂｓｅｔ（ＦＣｆ．ｇｅｎｅｒａｔｏｒ，ｐ）；ＦＯＲａｌｌＳＥＳｐＤＯＢＥＧＩＮＩＦ（Ｐ∈ｓ．ｃｌｏｓｕｒｅ）ＴＨＥＮ（５）ｄｅｌｅｔｅＰ（６）ＥＮＤｆｒｏｍ凡■＋１．ｇｅｎｅｒａｔｏｒ；（７）ＥＮＤ（８）Ａｎｓｗｅｒ＝Ｏ｛ｃＥ尺■＋ｌ＞；３３３关联规则挖掘研究算法４函数Ｄｅｒｉｖｉｎｇｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓ（ＦＣ，Ｌ）。（１）ｋ－－Ｏ；（２）ＦＯＲａｌｌｆｒｅｑｕｅｎｔｃｌｏｓｅｄｉｔｅｍｓｅｔｓｃ∈ＦＣＤＯＢＥＧＩＮ（３）（４）知ｌ＝／ｌｉｄｕ｛ｃ）；ＩＦ（ｋ＜ｌｌｃ∥根据项的计数归类ｃ１１）ＴＨＥＮｋ＝－ＩＩＩｌ；（５）ＥＮＤ（６）ＦＯＲ（ｉ＝ｋ；ｉ＞１；ｉ一）ＤＯ（７）（８）（９）ＦＯＲａｌｌｉｔｅｍｓｅｔｓＦＯＲＢＥＧＩＮｃ∈厶ＤＯＳａｌｌ（ｉ一１）一ｓｕｂｓｅｔｓｏｆｃＤＯ／／划分全部（ｉ一１）一项目集ＩＦ（ｓ！∈厶一１）ＴＨＥＮＢＥＧＩＮｓ．ｓｕｐｐｏｒｔ－－－－ｃ．ｓｕｐｐｏｒｔ；⑩ＱＤ厶ｑ＝厶一。ｕ｛ｓ｝；ＥＮＤ∥加入厶一。中∞∞三＝ｕ厶∥合并全部厶Ｃｌｏｓｅ算法的最终目的还是要生成频繁项目集，只不过它经过了一个中间步骤，即先生成闭合频繁项目集。因此，我们可以先从闭合频繁项目集中找出项目的最大计数，然后从该计数开始判断是否有频繁子集存在，若存在的话则说明对应的频繁项目集也存在网。３．５关联规则挖掘中的约束问题大型数据库中隐藏着大量的关联知识，如果我们漫无目的地进行挖掘，不仅挖掘的效率低下，而且挖掘到的知识可能有大部分都毫无实用价值。因此，研究人员将约束引入数据挖掘中，使得各种挖掘工作在约束的指导下进行。将数据挖掘与约束结合起来，不仅能够锁定挖掘的任务、提高挖掘的效率，而且还能确保挖掘的精确性，同时又能对系统的使用规模起到控制作用。数据挖掘中的约束包括以下几个方面［４１。１）知识类型约束：指明要挖掘哪种类型的知识。２）数据约束：指明任务中需要用到的数据。３）维／层约束：指明挖掘中需要用到的“维＂或“层＂。４）兴趣度约束：指明挖掘出的规则需满足的度量值。５）规则约束：指明要挖掘的规则具有怎样的形式。本小节着重讨论规则约束。３关联规则挖掘研究３．５．１关联规则的元规则挖掘元规则，简单说来就是规则模板，它形如互Ａ忍Ａ…Ａ另≥ＱＡＱ２Ａ…ＡＱ，其中，ＣＯ＝１，２，…，Ｚ）和Ｑ，（，＝１，２，…，，．）是动词变量【２４１。元规则可以由数据库模式或分析者的经验、期望而自动产生，它可以说明用户对哪种形式的规则感兴趣。例如，作为某超市的分析管理人员，你已经掌握了顾客的基本信息以及他们的购物模式。在分析交易数据中的大量关联知识时，你不需要了解某种联系反映出的所有规则，而只需在这些规则中找出你特别感兴趣的规则即可。一般说来，元规则总是按照用户的期望来设定的，它是一种假设，然后我们可以利用挖掘系统中的相应算法来找出与用户设定规则相匹配的规则。３．５．２约束特例——时态约束关联规则挖掘近年来，约束关联规则挖掘主要研究某种形态下的约束挖掘问题。在我们挖掘关联知识的过程中，时问是一个非常重要的属性，很可能某一个时间段内的数据会对整个挖掘结果起着至关重要的作用。把握住这种规律后，用户将注意力转移到特定时间段内数据的研究和分析中，期望能产生特定数据间的关联规则。因此，研究人员提出了关联规则挖掘中的时态约束问题。利用时态约束不仅能够锁定用户目标、过滤过时的数据，而且还能够加速关联规则的生成。例如，某个数据库表包含了时间字段，该字段能够反映对应项目集被采集或产生的时间范围。那么，我们如何更好地挖掘这样的数据库呢？首先，根据时态区间格空间中的相关理论，我们来定义两个基本时态操作；然后再在数据库的时间区间合并等预处理工作中应用这两个操作【３１。这样，就可以大规模地缩减数据总量，以便顺利进入内存，进而增强挖掘大型数据库的能力。３．６关联规则挖掘中更深入问题的探讨作为决策支持系统的两个重要组成部分，数据仓库技术和ＯＬＡＰ技术近年来得到了快速的发展。通过实际应用我们发现，较高的概念层中往往会产生有价值的关联规则，且这些关联规则可能会提供一般性意义的知识，而在较低的概念层中却几乎没有发现有价值的关联规则。另外，分析出数据包含的各个属性，即从“维＂的角度去把握数据，是近年来数据挖掘研究的一个重要方向，并且对于关系数据库或数据仓库中的挖掘来说显得尤为重要。再者，关系数据库中有许多非离散的数值属性，而这些属性对知识的形成又起着关键的作用。因此，多层、多维及数量关联规则挖掘成为近年来关联规则挖掘研究的重点。在本小节中，我们将对多层、多维及数量关联规则挖掘做简要地介绍。３关联规则挖掘研究３．６．１多层关联规则挖掘多层关联规则挖掘仍旧以“支持度一可信度＂的模式为基础，按照规则对应的层次，我们可以将它分为同层关联规则和层间关联规则。同层关联规则是指对应的项目在同一个层次的关联规则，如图３－８所示的“羽绒服ｊ酸奶＂就是同层次关联规则，它采用两种支持度策略，即统一最小支持度和递减最小支持度【２５】。由于层间关联规则考虑的是不同层次上的问题，因此在设置最小支持度时，应该以较低层次上的最小支持度为标准来设定。如何才能快速、高效地挖掘出多层关联规则呢？我们应该根据应用的特点来灵活巧妙地选择挖掘方法，如自上而下方法，自下而上方法等。另外，多层关联规则的挖掘可能产生冗余问题，因此，我们必须先针对具体的情况来进行分析，然后再确定适合的挖掘策略和方法。图３—８多层次概念示例Ｆｉ９３—８Ｍｕｌｔｉｌｅｖｅｌｃｏｎｃｃｐｔｅｘａｍｐｌｅ３．６．２多维关联规则挖掘ＯＬＡＰ本身就是一个多维多层分析工具，因此挖掘ＯＬＡＰ中的多维、多层关联规则是一件很容易的事情。我们把每个谓词称作维，而把包含单个谓词且该谓词多次出现的规则称作单维规则。例如ｕｓｅｓ（Ｙ’’ｈｐｕｓｅｓ（Ｙ，”ＩＢＭｂ／ｗｎｏｔｅｂｏｏｋｃｏｍｐｕｔｅｒ＇’）ｊｐｒｉｎｔｅｒ＇’）就是一个单维规则。若关联规则包含两个或多个维，那么这种关联规则就叫做多维关联规则；若每个谓词在多维关联规则中仅出现一次，我们则称该规则具有不重复谓词，且称该规则为维间关联规则。如ｈｅｉｇｈｔ（Ｘ，＂１７０ｃｍ…１８０ｃｍ”）八ｓｅｘ（Ｘ，＂ｍａｎｏｒｗｏｍｅｎ＇’）ｊｕｓｅｓ（Ｘ，”ｈｉｇｈｄｅｓｋ＇’）就是一个维间关联规则。另外，挖掘多维关联规则的技术分为使用预定义的概念分层对量化属性离散化、根据数据分布将量化属性离散化到“箱’’、量化属性离散化以紧扣区间数据的语义这三种ｆ２６】。３关联规则挖掘研究３．６．３数量关联规则挖掘数量关联规则的独特之处在于它同时包含了分类属性和数值属性，同时它也能够与多层、多维关联规则相互融合共同来对数据进行挖掘，且挖掘效果非常显著。目前，数量关联规则挖掘主要包括两种技术：一是通过改进原有关联规则算法来解决数量关联规则挖掘问题；二是编写一种新的关联规则算法来解决数量关联规则挖掘问题Ｉ引。另外，挖掘数量关联规则一般分为这样几个步骤：首先，离散化每个数值属性进而再整数化离散区间；其次，根据相应的算法挖掘出离散化数据集上的频繁项目集，再由频繁项目集产生出关联规则；最后，输出感兴趣的关联规则。虽然有关数量关联规则的研究有很多，但是我们目前比较关注和急需解的问题主要是规则的优化、连续数值属性的处理以及如何提高挖掘效率。３．７本章小结本章首先介绍了关联规则的相关概念以及挖掘关联规则的方法；接着重点介绍了事务数据库中关联规则的挖掘，在这一部分中，先介绍了经典的挖掘频繁项目集的算法Ａｐｒｉｏｒｉ算法的相关内容，其次介绍了关联规则的生成；然后又详细地介绍了不产生候选集的关联规则挖掘算法ＦＰ—ｇｒｏｗｔｈ算法的相关内容；最后，介绍了关联规则中的约束问题及一些更深入的问题。３７４Ａｐｒｉｏｆｉ的改进算法—＿ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法４Ａｐｒｉｏｒｉ的改进算法———－ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法早在１９９５年，Ｐａｒｋ等人就通过实验发现挖掘频繁项目集的计算主要在厶的生成上。根据Ａｐｆｉｏｆｉ算法由厶生成厶会产生大量的２一候选集，Ｇ产生后还需扫描数据库多次以便得到其中每个２一候选集的支持度计数，然后通过删除支持度计数小于最小支持度计数的２一候选集来生成厶。再有，厶一．生成Ｇ的连接步中，厶一，里任意两个（ｋ一１）一频繁项目集的连接都要经过（ｋ一１）次的比较，这大大增加了时间开销。有关研究人员曾今分别提出过这样两种观点：１）可用矩阵的方法来获取２一频繁项目集的集合厶¨Ｊ；２）Ｇ由厶一。∞厶一。生成，也可由厶一，吗生成【４ｌ】。鉴于这两种观点，我们对Ａｐｆｉｏｆｉ算法做了如下改进：一是采用数据库的布尔矩阵并编写相应算法来生成厶和厶；二是先证明厶一，生成ｑ的的连接步可用厶一。吗来代替厶一。∞厶一。，若结论成立，则从ｋ≥３起，厶一。生成Ｇ的连接步就用厶一咄来完成，进而改进候选集产生的算法。于是，我们提出Ａｐｆｉｏｆｉ算法的改进算法ＢＭＳＬＡｐｆｉｏｆｉ算法（ＢｏｏｌｅａｎＭａｔｒｉｘＳｉｍｐｌｉｆｉｅｄＬｉｎｋｅｄＡｐｆｉｏｆｉ算法）。这里我们首先介绍何谓“数据库的布尔矩阵＂。数据库的布尔矩阵：数据库可用这样一个矩阵Ａ来表示，项目集、事务均按顺序排好，项目集作为行向量，事务作为列向量；若项目集ｉ在事务ｊ中，则４，的值为１，否则为０，此时Ａ称为数据库的布尔矩阵［２７１。从布尔矩阵中我们很容易得知，每行元素的和即为该行对应项目集的支持度计数。４．１基本思想扫描事务数据库Ｄ，生成１一项目集布尔矩阵Ａ（即行向量为单个数据项）；对Ａ进行相应处理生成卜频繁项目集矩阵Ｂ及厶；令ＢｘＢｒ，从乘积矩阵中获取岛；从ｋ≥３时，沿用Ａｐｆｉｏｄ算法思想，但对厶一。生成Ｇ的连接步进行了改进，来求其他频繁项目集的集合。４．２算法设计步骤４．２．１构造事务数据库Ｄ的１～项目集布尔矩阵算法１Ｂｕｉｌｄ—ＢＭａｔｒｉｘ（）（构造卜项目集布尔矩阵）。（１）扫描事务数据库Ｄ一次；（２）ｉｆ（数据项ｉ在事务ｊ中）ｔｈｅｎ（３）呜２ｌ；（４）ｅｌｓｅ鸣２０；４ｈｐｒｉｏｒｉ的改进算法———。ＢＭｓ∽ｒｉｏｒｉ算法（５）ｒｅｔｕｒｎＡ；／／此时Ａ为％Ｘｎ矩阵对表３－１所示的事务数据库Ｄ执行Ｂｕｉｌｄ—ＢＭａｔｒｉｘ（）过程，为便于读者观看和理解，可将Ｄ的卜项目集布尔矩阵先写成表４—１形式。表４－１卜项目集布尔矩阵表Ｔａｂｌｅ４－１１一ｉｔｅｍｓｅｔｂｏｏｌｅａｎｍａｔｒｉｘｔａｂｌｅ事务列表项集五ＡＢＣＤＥＫ１ｌＯｌ０１正ｌｌｌｌ１０巧ｌｌｌＯ１Ｏ瓦ｌ１０１０Ｏ１１ｌ１１１ｌ１０１１０所以，Ｄ的卜项目集布尔矩阵Ｇ＝１１０ｌ０１ｌＯ１０００４．２．２卜频繁项目集的集合厶的生成根据步骤一生成的卜项目集布尔矩阵Ａ，我们可以做如下处理：对Ａ中的每行元素求和（即求该行对应卜项目集的支持度计数），若和大于或等于最小支持度计数，则将该行中每个元素的值赋给矩阵Ｂ中相应行的各个元素。此时得到的矩阵Ｂ即为卜频繁项目集布尔矩阵，找出Ｂ中每行对应的１一频繁项目集，就可以得到厶。算法２厶Ｐｒｏｄｕｃｅｄ０（生成卜频繁项目集的集合厶）。（１）ｍ２＝１；／／ｍ，作为Ｂ的行数（２）厶＝ｆ２ｊ；（３）ｆｏｒ（ｉ—ｌ；ｉ≤铂；ｉ＋＋）（４）（５）（６）（７）｛ｓｕｍ＝０；ｆｏｒ（ｊ＝ｌｊ≤ｎ；ｊ＋＋）ｓｕｍ＝ｓｕｍ＋Ａ［ｉ］［ｊ］；ｉｆ（ｓｕｍ＞ｉｍｉｎｓｕｐ）ｔｎｔｈｅｎ／／ｍｉｎｓｕｐ．ｃｏｕｎｔｕｏｃ．数计度持支小最为３９４Ａｐｄｏｆｉ的改进算法———ＢＭＳＬ＿Ａｐｄｏｆｉ算法（８）（９）｛ｆ．０ｒ（ｊ＝１；ｊ≤ｎｊ＋＋）Ｂ［他】Ｄ】２Ａ【ｉ】［ｊ】；㈣ＯＤ％Ｈ；＞，∞⑩％＝％一１；⑩∞∞）∥此时Ｂ为鸭×ｎ矩阵∞ｆｏｒ（ｉ＝ｌ；ｉ≤％；ｉＨ）｛ｃ＝Ｂ中第ｉ行对应的卜频繁项目集；厶＝厶ｋ．．／Ｃ；∞ｌ℃ｔｕｒｎ厶；执８Ｔ／１＿Ｐｒｏｄｕｃｅｄ０过程，得出卜频繁项目集布尔矩阵Ｒ＝１０１１０１１０１０１１０。Ｒ的第一行、第二行、第三行、第四行、第五行分别对应卜频繁项目集｛Ａ）、｛Ｂ）、｛Ｃ）、｛Ｄ）、｛Ｅ），所以厶＝｛｛彳），｛Ｂ），｛Ｃ＞，｛Ｄ），｛Ｅ））。４．２．３２一频繁项目集的集合厶的生成对步骤二产生的卜频繁项目集布尔矩阵Ｂ进行转置，得到其转置矩阵Ｂｒ，令Ｐ＝ＢｘＢｒ，则Ｐ中每个元素尸［讲刀＝∑Ｂ［ｉｌ［ｔ］事Ｂ丁［ｆ】［门。１）若ｉ≥ｉ，则说明Ｂ中第ｉ行对应莳１卜项目集大于或等于Ｂｒ中第ｊ列对应的卜项目集，用“连接”的观点来说，这两个卜项目集不符合连接条件，因而不能连接，此时Ｐ【ｉ】Ｄ】＿Ｏ。２）若ｉ＜ｊ，ＪｔＢ［ｉ］［ｔ】一Ｂ１ｆ】［／】一１，则说明Ｂ中第ｉ行对应的卜项目集与矿中第ｊ列对应的卜项目集同时存在于事务ｔ中，那么求得的和即为这两个卜项目集构成的２一项目集的支持度计数。这样得出的矩阵Ｐ是一个上三角矩阵，上三角里的每个数值即为２一项目集的支持度计数。选取上三角中大于或等于最小支持度计数的值所对应的２一项目集来构成厶。算法３厶Ｐｒｏｄｕｃｅｄ０（生成２一频繁项目集的集合厶）。（１）厶＝ｆ２ｊ；（２）ｆｏｒ（ｉ＝１；ｉ吣＜鸭；ｉ＋＋）４Ａｐｒｉｏｒｉ的改进算法———－ＢＭＳＬＡｐｒｉｏｒｉ算法（３）（４）（５）（６）（７）（８）（９）Ｑ回ＱＤｆｏｒ（ｊ＝ｉ＋ｌｊ≤ｎｊ＋＋）｛Ｐ［ｉ】Ｄ】＝ｏ；ｆｏｒ（仁１；ｔ≤ｎ；什＋）∥仅计算上三角元素，节省存储空间Ｐ【ｉ】Ｄ】＝＝Ｐ【ｉ】Ｄ】＋Ｂ【ｆ】［力幸Ｂ１ｐ］【／】；ｉｆ（Ｐ［ｉ］［ｊ］＞ｉｍｉｎｓｕｐ＿ｃｏｕｎｔ）ｔｈｅｎ｛Ｃ－Ｐ［ｉ】Ｄ】对应的２一项目集；厶＝厶ｕｃ；）＞∞ｒｅｔｕｒｎ厶；执行厶＿Ｐｒｏｄｕｃｅｄ（）过程，卜频繁项目集布尔矩阵Ｒ＝Ｉ０１１０１１０１０１ｌＯ的转置矩阵为０４２３２１１０１０１１１１１尺ｒ：１１１０１１１０１００１１０１１０１０００２３２，所以，Ｙ＝ＲｘＲ７’１１１１１＝Ｉ０１１０Ｉ×ｌｌｌ０１１１０ｌ１１０１００００００００００１０００１２。Ｙ第一行中的“４，２，３，２＂分别对应２一项目集｛Ａ，Ｂ＞，｛Ａ，Ｃ，，｛Ａ，Ｄ｝，｛Ａ，Ｅ），且是它们的支持度计数，以下同理。所以，Ｙ第二行中的“２，３，２”对应的２一项目集是｛Ｂ，Ｃ｝，｛Ｂ，Ｄ｝，｛Ｂ，Ｅ＞；第三行中的“ｌ，２’’对应的２一项目集是｛Ｃ，Ｄ｝，｛Ｃ，Ｅ）；第四行中的“１’’对应的２一项目集是｛Ｄ，Ｅ＿｝，选出支持度计数大于或等于最小支持度计数的２一项目集来构成厶。因此，厶＝｛｛彳，研，｛么，Ｃ），弘，研，｛彳，毋，｛Ｂ，Ｃ），｛Ｂ，Ｄ），｛Ｂ，毋，｛Ｃ，毋＞，同前述内容中用ａｐｒｉｏｒｉ—ｇｅｎ（Ｌｋ一。）方法先生成ｃ２，进而再生成厶的结果是一样的。但是，后者在算法效率上却大大提高了。当ｋ≥３时，我们就可按照Ａｐｒｉｏｒｉ算法的思想由厶一．来生成厶。但是，我们在丘一．生成Ｇ的连接步中做了一些改进。定理：厶一，生成Ｇ（ｋ≥３）的过程中，可用厶一．吗来代替厶一。∞厶一。。证明：设有任意卜候选集ｃ∈丘－ｌ∞￡Ｈ，了ｆ且ｆｃｃ，则３ｔ∈厶一ｌ。现假设ｃ岳厶一ｌ唱成立，则ｃ－ｔ诺厶一Ｉ唱一ｆ，进而得出ｃ—ｔ仨厶‘４¨。这显然与ｃ－ｔ的长度是１，即ｃ比ｆ多一个项矛盾，于是鲫！厶一．∞厶不成立，所以ｃ∈Ｌ。一吗。由于ｋ’候选集ｃ的任意性，即ｃ是厶一。咄一。里任意一个元素，又是￡纠噶里任意一个４１４Ａｐｒｉｏｄ的改进算法———‘ＢＭｓ岫一ｏｒｉ算法元素，因此￡¨吗等同于厶～。ｏｏＬｋ一。。所以，厶～，生成ｑ（ｋ≥３）的过程中，可用厶一。∞厶来代替厶一。∞厶一。，命题得证。４．２．４ａｐｒｉｏｄ＿ｇｅｎ（Ｌｋ＿１）算法的改进根据上面证明的结论，下面我们对候选集的产生算法稍做修改。算法４Ｎｅｗ＿ａｐｒｉｏｄ＿ｇｅｎ（Ｌｋ－ｌ，厶）（生成Ｇ的改进算法，ｋ≥３）。（１）ｆｏｒｅａｃｈｉｔｅｍｓｅｔＰ∈厶一ｌ（２）ｆｏｒｅａｃｈｉｔｅｍｓｅｔｑ∈厶（３）ｉｆ（ｐ［ｋ－１】＜ｑ）ｔｈｅｎ（４）｛ｃ＝ｐｏｏｑ；（５）ｉｆｈａｓ＿ｉｎ矗ｅｑｕｅｎｔｓｕｂｓｅｔ（ｃ，丘－１）（６）ｄｅｌｅｔｅｃ；（７）ｅｌｓｅａｄｄｃｔｏＧ；（８））（９）ＦｅｔｕｒｎＧ；根据以上分析，现给出ＢＭＳＬ算法ＢＭＳＬＡｐｒｉｏｒｉ（布尔矩阵简化连接频繁项目集挖掘算法）。输入：事务数据库Ｄ；最小支持度计数ｍｉｎｓｕｐｃｏｕｎｔ。输出：Ｄ中频繁项目集的集合Ｌ。（１）ＢｕｉｌｄＢＭａｔｒｉｘ０：（２）厶＝厶＿Ｐｒｏｄｕｃｅｄ（）；（３）厶＝厶＿Ｐｒｏｄｕｃｅｄ（）；（４）ｆｏｒ（ｋ＝３；厶一ｌ≠ａ；ｋ＋＋）（５）｛ｑ＝Ｎｅｗ＿ａｐｒｉｏｒｉ＿ｇｅｎ（厶＿１，厶）；（６）ｆｏｒｅａｃｈｔｒａｎｓａｃｔｉｏｎｔ∈Ｄ（７）｛Ｇ＝ｓｕｂｓｅｔ（Ｇ，ｔ）；（８）ｆｏｒｅａｃｈｃａｎｄｉｄａｔｅＣ∈Ｃｆ（９）ｃ．ｃｏｕｎｔ斗斗；㈣）ＱＤ厶＝｛ｃ∈ＧＩｃ．ｃｏｕｎｔ＞１ｍｉｎｓｕｐ＿＿ｅｏｕｎｔ｝∞）∞ｒｅｔｕｒｎ上＝ｕ厶；４２４Ａｐｒｉｏｒｉ的改进算法—哪ＭＳＬＡｐｒｉｏｒｉ算法４．３算法性能分析４．３．１避免大量候选集的产生及减少数据库的扫描次数根据Ａｐｒｉｏｒｉ算法由厶生成厶会产生大量的２一候选集，Ｃ’产生后还需扫描数据库多次以便得到其中每个２一候选集的支持度计数；而在ＢＭＳＬＡｐｒｉｏｒｉ算法中，通过卜频繁项目集布尔矩阵与其转置矩阵相乘，我们可以直接从两矩阵相乘的结果中获取每个２一候选集及其支持度计数，进而产生厶。这样不仅避免了大量２一候选集的产生，而且也避免了多次扫描数据库。４．３．２减少了时间开销一方面，根据Ａｐｒｉｏｒｉ算法由厶生成厶需要经过这样一个步骤：首先，厶经过自身连接、剪枝得到Ｃ’；接着，扫描数据库多次，对Ｃ＇中的每个２一候选集进行支持度计数；最后，从Ｃ，中挑选出支持度计数大于或等于最小支持度计数的２一候选集来构成厶。厶生成厶的整个过程大大增加了算法的时间，降低了算法的效率。在ＢＭＳＬＡｐｒｉｏｒｉ算法中，２一候选集及其支持度计数是可以直接获得的，相对于Ａｐｒｉｏｒｉ算法，其时间开销大大减少了。另一方面，在Ａｐｒｉｏｒｉ算法中，厶一生成Ｇ先要进行厶一，ｏｏＬｋ一。；而厶一，中任意两个元素连接前都需要进行（ｋ－－１）次比较，这也增加了时间开销。但是在ＢＭＳＬｋ厶一，∞厶来代替厶＿ｏｏＬｋ－ｌ’这样厶一。和厶中任意两个元素的连接只需比较１次即可，明显地减少了算法的时间开销，提高了算法的效率。４．３．３合理有效地利用了空间在Ａｐｒｉｏｒｉ算法中，厶生成厶所产生的大１２一候选集会占用大量的内存空间，并且也会导致系统不停地进行Ｉ／Ｏ操作；而ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法采用卜频繁项目集布尔矩阵与其转置矩阵相乘的方式直接获得厶，有效地节省了内存空间。通过以上理论性分析，我们可以感受到ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法的效率确实是优于Ａｐｒｉｏｒｉ算法的。４．４实验结果与分析下面我们通过实验来进行ＢＭＳＬｈｐｒｉｏｆｉ算法与Ａｐｒｉｏｒｉ算法、ＢＭＳＬＡｐｒｉｏｒｉ算法与ＣＢＡｐｒｉｏｒｉ算法１２驯（ＣｌｕｓｔｅｒＢａｓｅｄＡｐｒｉｏｒｉ算法）的比较。其中，ＣＢＡｐｒｉｏｒｉ也是Ａｐｒｉｏｒｉ算法的一种改进算法，由我国的一位研究人员于２００６年提出。ＣＢ＿Ａｐｒｉｏｒｉ算法只扫描数据库一次，根据事务的长度生成不同的聚类表来代替原始的数据库，比较聚类表并计算，找出所有的频繁项目集，进而生成关联规则。ＣＢ＿Ａｐｒｉｏｒｉ算法减少了数据库的扫描次数以及减小了数据库的规模，有效地提高４３４Ａｐｒｉｏｒｉ的改进算法—哪ＭＳＬ＿Ａｐｒｉｏｒｉ算法Ｐｅｎｔｉｕｍ４了算法的效率。实验中使用的计算机的基本配置是Ｉｎｔｅｌ２．０ＧＨＺ处理器，１ＧＢＤＤＲ内存，１２０ＧＩＤＥ硬盘；在ＷｉｎｄＯＷＳＸＰ的基础上，我们采用ＭｉｃｒｏｓｏｔｔＳＱＬＳｅｒｖｅｒ２００５和ＶＢ．ＮＥＴ作为开发平台来构建一个简单的关联规则挖掘系统。本实验选用了真实超市交易数据库中的部分数据，在征得超市负责人同意的情况下，我们获取了６０００条交易数据。实验中使用ＥｘｅｃｕｔｉｏｎＴｉｍｅ（Ｓ）表示执行时间，Ｍｉｎｓｕｐ（％）表示最小支持度，ＴｒａｎｓａｃｔｉｏｎＮｕｍ（ｋ）表示交易数。实验一：在交易数目不变的情况下ＴｒａｎｓａｃｔｉｏｎＮｕｍｂｅｒ＝６０００，我们来考察不同最小支持度下ＢＭＳＬ算法、算法与ｉｒｏｉｒＡｐｒｉｏｒｉｐＡ＿时行运ＣＢ．Ａｐｒｉｏｒｉ的法算间，并分别对ＢＭＳＬＡｐｒｉｏｒｉ算法与Ａｐｒｉｏｒｉ算法、ＢＭＳＬＡｐｒｉｏｒｉ算法与ＣＢ４－２算法的运行时间做比较。实验结果分别如图４—１、ｉｒｏｉｒｐＡ．。示所图４一ｌ不同最小支持度下ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法与Ａ研嘶算法的运行时间Ｆｉ酗一１ｅｘｅｃｕｔｉｏｎｔｉｍｅｏｆＢＭＳＬＡｐｒｉｏｒｉａｎｄＡｐｒｉｏｒｉｏｆｄｉｆｆｅｒｅｎｔｍｉｎｓｕｐｐｏｒｔ图４—２不同最小支持度下ＢＭＳＬ＿＿Ａｐｒｉｏｄ算法与ＣＢ—Ａｐｎｏ一算法的运行时间Ｆｉ９４－２ｅｘｅｃｕｔｉｏｎｔｉｍｅｏｆＢＭＳＬＡｐｒｉｏｒｉａｎｄＣＢ＿Ａｐｒｉｏｒｉｏｆｄｉｆｆｅｒｅｎｔｍｉｎｓｕｐｐｏｒｔ４Ａｐｒｉｏｒｉ的改进算法———－ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法从图４－１中我们可以看出，总体上，随着最小支持度的不断减小，Ａｐｒｉｏｒｉ算法和ＢＭＳＬ算法的运行时间都是在不断增加的，但是ｉｒｏｉｒｐＡ．的法Ａｐｒｉｏｒｉ算运行时间长于ＢＭＳＬＡｐｒｉｏｒｉ算法。当最小支持度是４％时，两种算法的运行时间基本相同；当最小支持度是３．５％时，Ａｐｒｉｏｒｉ算法的运行时间比ＢＭＳＬＡｐｒｉｏｒｉ算法的运行时间稍微长些。当最小支持度逐渐减小时，Ａｐｒｉｏｒｉ算法的运行时间是大幅度增长的；ＢＭＳＬＡｐｒｉｏｒｉ算法的运行时间也在增长，只不过变化幅度没有Ａｐｒｉｏｒｉ算法大。由此我们可以得知，在交易数不变的情况下，选取不同最小支持度时，ＢＭＳＬＡ研嘶算法的运行时间总是比Ａｐｒｉｏｒｉ算法的运行时间短。从图４—２中我们也很容易看出，随着最小支持度的不断减小，ＣＢ算法和ＢＭＳＬＡｐｒｉｏｒｉ算法的运行时间都是在不断增加的，但是ｉｒｏｉｒｐＡ．法算ＣＢ．Ａｐｒｉｏｒｉ的运行时间比ＢＭＳＬＡｐｒｉｏｒｉ算法长，并且ＣＢＡｐｒｉｏｒｉ算法运行时间的增长幅度是强于ＢＭＳＬＡｐｒｉｏｒｉ算法的。这就说明ＢＭＳＬＣＢＡｐｒｉｏｒｉ算法。再把图４－１、４—２结合起来看，毕竟ＣＢＡｐｒｉｏｒｉ是Ａｐｒｉｏｒｉ算法的一种改进算法，在相同条件下，ＣＢＡｐｒｉｏｒｉ算法的运行时间还是比Ａｐｒｉｏｒｉ算法的运行时间短。实验二：在最小支持度不变的情况下Ｍｉｎｓｕｐｐｏｒｔ＝２．５％，我们来考察不同交易数下ＢＭＳＬＡｐｒｉｏｒｉ算法、Ａｐｒｉｏｒｉ算法与ＣＢ别对ＢＭＳＬＡｐｒｉｏｒｉ算法与Ａｐｒｉｏｒｉ算法、ＢＭＳＬＡｐｒｉｏｒｉ算法与ＣＢＡｐｒｉｏｒｉ算法的运行时间做比较。实验结果分别如图４－３、４－４所示。图４—３不同交易数下ＢＭＳＬ－Ａｐｒｉｏｒｉ算法与Ａｐｒｉｏｒｉ算法的运行时间Ｆｉ９４—３ｅｘｅｃｕｔｉｏｎｔｉｍｅｏｆＢＭＳＬＡｐｒｉｏｒｉａｎｄＡｐｒｉｏｒｉｏｆｄｉｆｆｅｒｅｎｔｔｒａｎｓａｃｔｉｏｎｎｕｍｂｅｒ４５４Ａｐｒｉｏｒｉ的改进算法———－ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法图４—４不同交易数下ＢＭＳＬ＿Ａ研嘶算法与ＣＢ＿Ａｐｒｉｏｒｉ算法的运行时间Ｆｉ酣一４ｅｘｅｃｕｔｉｏｎｔｉｍｅｏｆＢＭＳＬ＿ＡｐｒｉｏｒｉａｎｄＣＢＡｐｒｉｏｒｉｏｆｄｉｆｆｅｒｅｎｔｔｒａｎｓａｃｔｉｏｎｎｕｍｂｅｒ从图４－３中我们可以看出，总体上，随着交易数目的不断增加，Ａｐｒｉｏｒｉ算法和ＢＭＳＬ行时间长于ＢＭＳＬ算法的运行时间都是在不断增长的，但是ｉｒｏｉｒｐＡ．运的法Ａｐｒｉｏｒｉ算２０００算法。当交易数为ｉｒｏｉｒｐＡ．比间时行运的法算种两，时较接近；当交易数目逐渐增加时，两种算法的运行时间都明显呈上升趋势，但Ａｐｒｉｏｒｉ算法运行时间的增长幅度强于ＢＭＳＬ在最小支持度不变的情况下，当交易数越来越大时，ＢＭＳＬＡｐｒｉｏｒｉ算法的运行时间总是比Ａｐｒｉｏｒｉ算法的运行时间短。这也进一步说明了ＢＭＳＬＡｐｒｉｏｒｉ算法比较适合于大型事务数据库中频繁项目集的挖掘。从图４－４中我们也很容易看出，随着交易数目的不断增加，ＣＢＡｐｒｉｏｒｉ算法和ＢＭＳＬ行时间比ＢＭＳＬＣＢＣＢ算法的运行时间都是在不断增加的，但是ＣＢ．ＡｐｒｉｏｒｉｉｒｏｉｒｐＡ．运的法算ＢＭＳＬ算法长，这就说明ｉｒｏｉｒｐＡ＿于优能性的Ａｐｒｉｏｒｉ法算、４－３４－４ｉｒ算法。再把图ｏｉｒｐＡ．，下件条同相在知得可便，看来起合结算法的运行时间还是比ｉｒｏｉｒｐＡ．。短间时行运Ａｐｒｉｏｒｉ的法算４．５本章小结本章提出了Ａｐｒｉｏｒｉ算法的改进算法ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法。论文首先介绍了ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法的基本思想；然后对该算法的设计步骤做了详细的说明，并给出具体的算法描述；最后进行算法性能分析，在实验的基础上我们确实得出了ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法的效率是优于Ａｐｒｉｏｒｉ算法和其他算法的结论。５改进算法的应用５改进算法的应用“尿布与啤酒”的故事是关联规则的一个经典案例，在它的启发下，商家们都在不断地寻求着纷繁数据里的价值规律。关联规则是伴随着零售业的飞速发展而产生的一种需求，挖掘出隐藏在海量销售数据中的关联规则对商家制定相应的营销策略是非常必要的，它也是商家在激烈的竞争中处于不败地位的有利武器。在前面的内容中，我们较为详尽地阐述了数据挖掘理论和关联规则中的几个重要问题。根据第四章提出的Ａｐｄｏｒｉ算法的改进算法ＢＭＳＬＡｐｒｉｏｒｉ算法，现对我家附近的一所会员制超市进行关联规则挖掘。本论文通过对该超市交易数据库的挖掘来进行顾客忠诚度分析，商家可根据分析结果对价格和商品的花样加以调整，以便留住老顾客，吸引新顾客。顾客忠诚度分析的前提条件是了解每位顾客不同时期购买商品的序列，因此可用序列模式挖掘来分析顾客的消费或忠诚度的变化。于是，每位顾客在不同时期购买的商品便可以成为一个序列。那什么是序列模式挖掘昵？序列模式挖掘是指挖掘相对于时间或其他模式出现频率较高的模式，它有三个重要的参数：第一个参数是时间序列的持续时间，第二个参数是事件重叠窗口，第三个参数是被发现的模式中时间之间的时间间隔【４】。５．１实验的软硬件环境实验中使用的计算机的基本配置是ＩｎｔｅｌＰｅｎｔｉｕｍ４２．０ＧＨＺ处理器，１ＧＢＤＤＲ内存，１２０ＧＩＤＥ硬盘，ＷｉｎｄｏｗｓＸＰ操作系统。我们利用ＭｉｃｒｏｓｏｆｔＳＱＬＳｅｒｖｅｒ２００５和ＶＢ．ＮＥＴ作为开发平台，来构建一个简单的关联规则挖掘系统，对超市交易数据库进行有效的关联规则挖掘。在关联规则挖掘的过程中，我们使用ＢＭＳＬＡｐｒｉｏｄ算法来挖掘频繁项目集。５．２实验的具体过程５．２．１体系结构构建的关联规则挖掘系统体系结构如图５－１所示。首先对超市交易数据库中的数据进行清理、集成并去除污染，形成可用于挖掘的数据库；然后利用Ａｐｒｉｏｒｉ算法的改进算法ＢＭＳＬＡｐｒｉｏｒｉ算法进行关联规则的挖掘：最后将关联规则挖掘的结果以用户界面的形式展示出来，超市管理人员可根据挖掘出的结果来制定相应的销售策略。４７５改进算法的应用ｆ（用户界面／、Ｉ１ｌ｜关联规则挖掘彳、ｌｌ／、（硼谢勰的瓣ＩＺＸ数据清理、集成，去除污染图５一ｌ挖掘实例的系统结构Ｆｉ９５。。１ｍｉｎｉｎｇｅｘａｍｐｌｅａｒｃｈｉｔｅｃｔｕｒｅ５．２．２系统数据库的建立数据库是进行关联规则挖掘的基础，但是数据库中数据的采集要耗费关联规则挖掘过程的大部分时间。通过与我家附近超市负责人的多次协商，我终于获取该超市近期内的大概６０００笔交易记录。但是当前的数据库表结构不能满足关联规则挖掘的需求，因此结合我的挖掘需求，再在超市原有数据库的基础上建立一个适合关联规则挖掘的交易数据库。１）数据的准备数据准备阶段是由４个子步骤构成，即数据集成、数据选择、数据预处理以及数据转换【５】。首先进行数据的集成，将数据库中的数据进行合并，解决数据的语义模糊性，处理数据中的遗漏并对数据进行清洗。其次对数据进行选择，搜集有关数据，缩小处理范围，辨别出需要分析的数据集合，以便提高关联规则挖掘的质量。然后对数据进行预处理，在本系统中，数据预处理主要是针对数据是否存在污染、数据是否丢失的情况，因为在实际的销售系统中，很容易出现库文件受污染或丢失的情况，这样会严重影响挖掘的效果。最后进行数据转换，最重要的就是对数据进行编码，将数据库中属性的不同取值转换成数码形式将有利于数据的搜索。５改进算法的应用２）挖掘系统中数据库表的建立本论文要对顾客的忠诚度进行分析，用于关联规则挖掘的数据库中除顾客的基本信息表和商品基本信息表以外，我们还要建立每位顾客不同时期购买商品的数据，不同时期购买的商品便是～个序列。利用ＭｉｃｒｏｓｏｆｔＳＱＬＳｅｒｖｅｒ２００５来建立挖掘系统中的数据库表，各数据库表分别如图５—２、５—３所示。网。Ｌｒ：Ｉ氇：ｊ胃Ｋ’ｊｌｌ四瞄例ｌ‘性别女男男■～一ｌ■｛一．ｊ１ＤＲＦ９５０００２ＤＢＦ９５０００３ＤＲＦ９５０００４ＤＥＰ９５０００５ＤＲＦ９５０００６ＤＥＦ９５０００７ＤＥＦ９５０００８ＤＥＦ９５０００９ＤＲＦ９５００１０ＤＲＦ９５００１１ＤＢＦ９５００１２颐客编码１年龄２１３４４５３８２８５６４１３６２９６２３３４８５５３０｝体重（单位：斤）Ｉ职业１１８１２０１３８３３２８４２４４３６２５２７３１４５４０１３５籍贯安徽安庆安徽淮南安徽定远安徽台肥安徽芜湖江苏淮安安徽淮南安徽淮南安徽蚌埕安徽舒城安徽淮南安徽桐城上海安徽淮南卜大学生机关人员丈学教授建筑工程师公司会计退休人员中学教师医生机关人员退休人员小学教师中专教师退休人员机关人员男女男女女男女男——＿＿ＤＥＦ９５００１３女女Ｄ髓９５００１４——＿＿～Ｉ・｛Ｉ图５－２顾客基本信息表Ｆｉ９５‘。２ｂａｓｉｃｉｎｆｏｒｍａｔｉｏｎｏｆｃｕｓｔｏｍｅｒｓ，ｒＩｌ班●ｌｕ讳ｌ＾晡ｍＪｊ¨一口Ｊ琳ＤＲＦＭ５０００２ＤＥＦＭ５０００３ＤＲＦＩｄ５０００４ＤＲＦｆｌ５０００５ＤＲＦＭ５０００６ＤＲＦＭ５０００ＴＤＢ，Ｍ５０００８ｍＩＦＭ５０００９ＤＢＦＭＳ００１０班ＩＦＵＳ００ｌ１ＤＲＦＭ５００１２ＤＲＦＵ５００１３ＤＲＦＭ５００１４ＤＲＦＭ５００１５商品价格（单位：元）２．５２０商品产地Ｕ办同尿安徽含肥安徽淮南山东莱阳上海方便面肉松花生油中老年奶粉苹果卫生纸冼发水洁洁剂拖鞋冰棍盒暖瓶三角架冰箱数码相机３ｓ元／斤６８５６３５元／斤山东烟台安徽台肥Ｊ．，－ｏｒｔＪ州Ｊ１８元／袋２２２６３２１６１７３１５２１８０２６７０ｊＫＪ州浙江义乌安徽合肥安徽淮南广东深圳山东青岛北京《ｌ。ｒ中商品的计数，我们看是否能给该商品打折，同时，通过顾客本次购买的商品来发现顾客的购物习惯。每位顾客不同时期的购物记录表如图５—４所示。暇◆翻ⅢⅧｍ－＿＿＿＿＿＿＿＿ｏ…ｎｍ【ｌＩ¨ｌ，ＤＲＦ９５００ｉｉＤＲＦ９５００ｌｌＤＲＦ９５００１ＩＤ王ｉＦ９５００１１ＤＲＦ９５００１ｌＤＲＦ９５００１１ＤＲＦＭ５０００７ＤＲＦＭ５０００１ＤＲＦＭ５０００５ＤＲＦＭ５０００４顾客编码商品编码购物日期０９／０７／２１０９１０７／２１０９１０７／２１０９／０７／２１０９／０８／１５０９／０８／１５０９／０８／１５０９／０９／１８０９１０９／１８０９／０９ｔ１８０９／０９／１８０９／１０１０３０９ｆ１０／０３６１８１１２ｌ１１２６８１８商品计数４购物次数ｍＤ盯Ｍ５０００８ＤⅡＭＳ００１５ＤＲＦＭ５０００３ＤＢＦＭ５０００９Ｄ王：Ｆ９５００１１１ｌＤ盯９５００１Ｄ船９５００ｌＤｍｒＭ５００１０ＤＲＦＭ５０００１ＤＲＦＭ５０００２ＤＲＦＭ５００１３ＤＲＦＭ５０００６Ｄ”９５００１１ｍ口９５００１１ＤⅪ９５００１１Ｄ】强９５００１１０９／１０／０３Ｉ・ｌＩ，厂～一藜事一：图５－５关联规则挖掘系统主界面Ｆｉ茚一５ｍａｉｎｉｎｔｅｒｆａｃｅｏｆＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓｍｉｎｉｎｇｓｙｓｔｅｍ５改进算法的应用图５－６挖掘频繁项目集的流程图Ｆｉ９５—６ｍｉｎｉｎｇｏｆｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓｆｌｏｗｃｈａｒｔ以２一频繁项目集的生成为例，则２一频繁项目集的生成结果如图５－７所示。图５－７２一频繁项目集的生成Ｆｉ莎－７ｇｅｎｅｒａｔｉｏｎｏｆ２一ｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓ５改进算法的应用利用关联规则生成算法来生成有价值的关联规则，生成的关联规则如图５—８所示。最小支持度Ｆ砭一最小可信度『丽～图５—８关联规则的生成Ｆｉ９５—８ｇｅｎｅｒａｔｉｏｎｏｆＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ茎些堡篓ｉ５．２．４挖掘结果的分析图５—８生成的关联规则即为我们挖掘超市数据库得到的结果。以图中的关联规则“卫生纸＝＞清洁剂＂为例，再结合图５—７，可得到这条规则的支持度是１３．４５％，可信度是４５．８３％。从上面的数据信息中，超市负责人可得知：超市一段时间内交易数据中的１３．４５％同时包含了卫生纸和清洁剂；某顾客有４５．８３％的可能在购买了卫生纸后，经过一段时间再买清洁剂。把握住顾客们的购物趋势后，超市负责人应该科学地安排进货、库存以及货架设计等，这样才能达到留住老顾客、吸引新顾客的目的，才能不断为超市盈利；同时，通过这个具体的例子我们再次证明了挖掘过程中ＢＭＳＬＡｐｒｉｏｄ算法的应用较Ａｐｄｏｒｉ算法及其他算法确实取得了不错的挖掘效果。５．３本章小结本章在较好地软硬件环境下构建了一个简单的关联规则挖掘系统。在关联规则生成的过程中，采用了Ａｐｒｉｏｒｉ算法的改进算法ＢＭＳＬ＿Ａｐｒｉｏｒｉ算法来挖掘频繁项目集。通过生成的关联规则结果，我们得出了ＢＭＳＬ＿．Ａｐｄｏｒｉ算法较Ａｐｒｉｏｒｉ算法及其他算法确实取得不错的挖掘效果的结论。５２６总结与展望６总结与展望６．１总结本论文主要研究关联规则算法及其应用，在系统地阐述了数据挖掘和关联规则中相关理论以及详尽地分析了Ａｐｒｉｏｒｉ算法性能瓶颈的基础上，我们从两个方面对Ａｐｒｉｏｒｉ算法做了改进。一方面是厶的生成，新算法打破了ｈｐｒ．ｉｏｒｉ算法的框架，不采用厶的自身连接来产生Ｇ进而产生厶，而采用数据库的布尔矩阵再根据厶Ｐｒｏｄｕｃｅｄ０和厶Ｐｒｏｄｕｃｅｄ０算法来获取厶和厶，减少了数据库的扫描次数以及一定程度上地避免了庞大候选集的产生。另一方面，根据已证明成立的结论，即厶一。生成ｑ的连接步可用厶一。唱来代替厶一，ｍＬｋ一，，从ｋ≥３起，采用Ｎｅｗａｐｒｉｏｒｉｇｅｎ（厶巾厶）算法来生成Ｇ，降低了算法的时间和空间消耗。基于这两方面的改进我们提出了Ａｐｒｉｏｒｉ算法的改进算法ＢＭＳＬＡｐｒｉｏｒｉ算法，在分析该算法性能的同时，我们又通过实验证明了此算法的效率确实是优于Ａｐｒｉｏｒｉ算法和其他算法的。然后，在较好的软硬件环境下构建了一个简单的关联规则挖掘系统，在关联规则生成的过程中利用ＢＭＳＬＡｐｒｉｏｒｉ算法来进行频繁项目集的挖掘。最后，通过得出的关联规则挖掘结果，再次验证了ＢＭＳＬＡｐｒｉｏｒｉ算法较Ａｐｒｉｏｒｉ算法和其他算法确实取得了不错的挖掘效果。６．２展望本论文只是对前人所做的Ａｐｒｉｏｒｉ算法改进工作的一些补充，为其他研究Ａｐｒｉｏｒｉ算法的人们提供一种思路和参考。本人的知识水平有限，再加上时间和精力的局限性，难免会有不足之处，我将会在以后的研究工作中不断地努力和完善。本文下一步希望从以下几个方面进行深入的研究。１）最小支持度和最小可信度的选取：最小支持度和最小可信度的选取不是一件容易的事情，若选取的最小支持度或最小可信度过小，则可能会提取不少没有用处的频繁项目集或关联规则：若选取的最小支持度或最小可信度过大，则可能会丢弃部分有着重要意义的频繁项目集或关联规则。总而言之，最小支持度或最小可信度选取得是否适当将会直接影响着挖掘出的关联规则的价值度。２）如何建立更好的关联规则挖掘结果的用户界面：使关联规则挖掘结果更加清晰、直观，方便用户分析和发现潜在的问题。３）如何构建一个比较完善的关联规则挖掘系统：使得关联规则的挖掘更加方便和精确。５３参考文献参考文献【１】高明．关联规则挖掘算法的研究及其应用【Ｄ】．济南：山东师范大学，２００６：３【２】陈文伟，黄金才．数据仓库与数据挖掘［ＭＩ．北京：人民邮电出版社，２００４：７８－７９［３】毛国君，段立娟等．数据挖掘原理与算法［Ｍ】．北京：清华大学出版社，２００７：７３～７４【４］ＪｉａｗｅｉＨａｒｔ，ＭｉｃｈｅｌｉｎｅＫａｍｂｅｒ．ＤａｔａＭｉｎｉｎｇＣｏｎｃｅｐｔｓａｎｄＴｅｃｈｎｉｑｕｅｓ［Ｍ］．北京：机械工业出版社，２００１：４【５】康晓东等．基于数据仓库的数据挖掘技术［Ｍ】．北京：机械工业出版社，２００４：１３３【６】谭．斯坦巴赫，范明，范宏建．数据挖掘导论ｔＭ］．北京：人民邮电出版社，２００６：１２【７】陈文伟，黄金才，赵新昱．数据挖掘技术【Ｍ】．北京：机械工业出版社，２００２：１４［８］ＡｒｂｅｅＬＰＣｈｅｎ，ＰａｕｒａｙＳＭＴｓａｉ，Ｃｈｉｈ－ＣｈｏｎｇＬｅｅ．Ａｎｅｆｆｉｃｉｅｎｔａｐｐｒｏａｃｈｆｏｒｉｎｃｒｅｍｅｎｔａｌａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｍｉｎｉｎｇ．ＰＡＫＤＤ，１９９９，ＢｅｉｊｉｎｇＣｈｉｎａ：１５５－１５８【９】胡可云．数据挖掘理论与应用【Ｍ】．北京：清华大学出版社，２００８：１５【ｌＯ］ＣＣｌｉｆｔｏｎ，ＲＣｏｏｌｅｙ．Ｔｏｐｃａｔ：ＤａｔａＭｉｎｉｎｇｆｏｒｔｏｐｉｃｉｄｅｎｔｉｆｉｃａｔｉｏｎｉｎａｔｅｘｔｃｏｒｐｕｓ．Ｐｒｏｅ．ｏｆＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙｉｎＤａｔａｂａｓｅｓ，１９９９【１１］Ｋ．ＥＳｏｍａｎ，范明，牛常勇．数据挖掘基础教程［Ｍ】．北京：机械工业出版社，２００９：２０［１２］ＧＧｒａｈｎｅ．Ｅｆｆｉｃｉｅｎｔｍｉｎｉｎｇｏｆｃｏｎｓｔｒａｉｎｅｄｃｏｒｒｅｌａｔｅｄｓｅｔｓ．Ｐｒｏｃ．２０００Ｉｎｔ．Ｃｏｎｆ．ＤａｔａＥｎｇｉｎｅｅｒｉｎｇ．ＳａｎＤｉｅｇｏ，ＵＳＡ．Ｆｅｂ．２０００：４２３－４２８［１３】史嘉权．数据库系统概论【Ｍ】．北京：清华大学出版社，２００６：２７【１４】张英朝，邓苏，张维明，刘青宝．智能数据挖掘引擎的设计与实现阴．计算机科学，２００２，（１０）：１１【１５】张俊妮．数据挖掘与应用【Ｍ】．北京：北京大学出版社，２００９：１８．［１６］ＷＬｉ，ＪＨａｎ，ＪＰｅｉ．ＣＭＡＲ：Ａｃｅｕｒａｔｅａｎｄｅｆｆｉｃｉｅｍｃｌａｓｓｉｆｉｃａｔｉｏｎｂａｓｅｄｏｆｎｍｕｌｔｉｐｌｅｃｌａｓｓ－ａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ．Ｐｒｏｃ．２００１Ｉｎｔ．Ｃｏｎｆ．ｏｎＤａｔａＭｉｎｉｎｇ，ＳａｎＪｏｓｅ，ＣＡ，Ｎｏｖ．２００１【１７】陈京民。数据仓库与数据挖掘技术［Ｍ】．ｊ匕京：电子工业出版社，２００７：１６【１８】章兢，张小刚．数据挖掘算法及其工程应用【Ｍ】。北京：机械工业出版社，２００６：６８【１９】曹馨宇．关联规则挖掘算法的设计与实现［Ｄ】．济南：山东大学，２００６：７【２０】梁循．数据挖掘算法与应用【Ｍ】．北京：北京大学出版社，２００６：７４－－－７５【２１】吕晓玲，谢邦昌．数据挖掘方法与应用【Ｍ】．北京：中国人民大学出版社，２００９：７１～７２【２２］＇ｆｆｌｇ峰晶，于忠清，王金龙．数据挖掘原理与算法［Ｍ】．北京：科学出版社，２００９：１６０－１６１【２３］ＤｅｙｉＬｉ，ＫａｉｃｈａｎｇＤｉ，ＤｅｒｅｎＬｉ，ＸｕｅｍｅｉＳｈｉ．Ｍｉｎｉｎｇａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｗｉｔｈｌｉｎｇｕｉｓｔｉｃｃｌｏｕｄｍｏｄｅｌｓ．ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，ｌ１０２），ｐ１４６－１６２，２０００：２３２－２３４【２４】马刚，李志刚．数据仓库与数据挖掘的原理及应用【Ｍ】一匕京：高等教育出版社，２００８：１７５【２５】薛惠峰，张文字，寇晓东．智能数据挖掘技术【ｌ咽．西安：西北工业大学出版社，２００５：９８【２６】杨风召．高维数据挖掘技术研究［Ｍ】．南京：东南大学出版社，２００７：１６８参考文献［２７１杜习慧，罗坤杰，罗文俊．关联规则挖掘Ａｐｒｉｏｒｉ算法的改进叨．电脑知识与技术，２００９，（０６）：１２９６［２８］陈琦．关联规则挖掘算法的研究与实现【Ｄ】．武汉：华中师范大学，２００６：２３－２４【２９１张掂．数据挖掘及其在客户关系管理中的应用ｏｖｒｌ．上海：复旦大学出版社，２００７［３０］Ｔａｎｇ，Ｚ．Ｈ．，Ｍａｃｃｌｅｎｎａｎ，Ｊ．数据挖掘原理与应用：ＳＱＬ出版社，２００７［３１］ＲｍｉｎｉｎｇＣｏｏｌｅｙ，ＢＭｏｂａｓｈｅｒ，ＪＳｒｉｖａｓｔａｖａ．ＧｒｏｕｐｉｎｇｗｅｂｐａｇｅｒｅｆｅｒｅｎｃｅｓｗｏｒｌｄｉｎｔｏｔｒａｎｓａｃｔｉｏｎａｎｄＤａｔａＳＳｅｒｖｅｒ２００５数据库【Ｍ】．北京：清华大学ｆｏｒｗｉｄｅｗｅｂｂｒｏｗｓｉｎｇｐａｔｔｅｒｎｓ．Ｐｒｏｃ．ｏｆＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇＷｏｒｋｓｈｏｐ，Ｎｅｗｐｏｒｔ【３２１ＳＢｅａｃｈ，ＣＡ，ＩＥＥＥ．１９９７：３３２—０３５ｓｕｒｐｒｉｓｉｎｇＣｈａｋｒａｂａｒｔｉ．Ｍｉｎｉｎｇｐａｔｔｅｒｎｕｓｉｎｇｔｅｍｐｏｒａｌｄｅｓｃｒｉｐｔｉｏｎｌｅｎｇｔｈ．Ｐｒｏｃ．１９９８Ｉｎｔ．Ｃｏｎｆ．ＶｅｒｙｌａｒｇｅＤａｔａｂａｓｅｓ．ＮｅｗＹｏｒｋ，ＵＳＡ．Ａｕｇ．１９９８：３２５—３４２［３３］ＷＷＣｏｈｅｎ，ＹＳｉｎｇｅｒ．Ｃｏｎｔｅｘｔ－ｓｅｎｓｉｔｉｖｅｌｅａｒｎｉｎｇｍｅｔｈｏｄｓｆｏｒｔｅｘｔｃａｔｅｇｏｒｉｚａｔｉｏｎ．Ｐｒｏｃ．ｏｆｔｈｅｆ１９ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＡＣＭＳＩＧｌＲＣｏｎｆｅｒｅｎｃｅＲｅｔｒｉｅｖａｌ，ｐａｇｅｓ３２１－３３２，１９９６ｏｎＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔｉｎＩｎｆｏｒｍａｔｉｏｎ【３４］ＪＨａｎ．Ｍｉｎｉｎｇｆｒｅｑｕｅｎｔｐａ：【ｔｅｍｓｗｉｔｈｏｍｃａｎｄｉｄａｔｅｇｅｎｅｒａｔｉｏｎ．Ｐｒｏｃ．２０００ＡＣＭＳＩＧＭＯＤＩｎｔ．Ｃｏｎｆ．ＯｎＭａｎａｇｅｍｅｎｔｏｆＤａｔａ．Ｄａｌａｓ，ＵＳＡ．Ｍａｙ２０００［３５］ＧｏｒｄｏｎＳ．Ｌｉｎｏｆｆ，ＭｉｃｈａｅｌＪ．Ａ．Ｂｅｒｒｙ．Ｗｅｂ数据挖掘：将客户数据转化为客户价值［Ｍ】．北京：电子工业出版社，２００４：６５－－６６【３６］Ｊ．ｗ．Ｈａｎｄ．ＰｅｉａｎｄＹ．ｗ．ＹｒｇＭｉｎｉｎｇＦｒｅｑｕｅｎｔＰａｔｔｅｎｓｗｉｔｈｏｕｔＣａｎｄｉｄａｔｅＣｅｎｅｒａｔｉｏｎ，ＩｎＳｌＧＭＯＤ，２０００：２３—３４【３７］ＫｏｎＡｌｓａｂｔｉ，ＳＲａｎｋａ，ＶＳｉｎｇｈ．Ａｎｅｆｆｉｃｉｅｎｔｋ－ｍａｎｓｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ．ＩＰＰＳ／ＳＰＤＰＷｏｒｋｓｈｏｐＨｉｇｈＰｅｒｆｏｒｍａｎｃｅＤａｔａＭｉｎｉｎｇ，１９９８，Ｏｒｌａｎｄｏ，Ｆｌｏｒｉｄａｒｕｌｅｓ．ＪｏｕｒｎａｌｏｆＩｎｔｅｌｌｉｇｅｎｔ【３８］ＥＢａｒａｌｉｓ，Ｇ，Ｐｓａｉｌａ．ＤｅｓｉｇｎｉｎｇｔｅｍｐｌａｔｅｓｆｏｒＭｉｎｉｎｇＡｓｓｏｃｉａｔｉｏｎＩｎｆｏｒｍａｔｉｏｎＳｙｓｔｅｍ，９，ｐｐｌ３—２７，１９９７【３９］ＭＳＣｈｅｒｈＪＨａｒｔ，ＰＳＹｕ．ＤａｔａＭｉｎｇ：Ａｎｏｖｅｒｖｉｅｗｆｒｏｍａｄａｔａｂａｓｅｐｅｒｓｐｅｃｔｉｖｅ．ＩＥＥＥＴｒａｎｓ．ｏｎＫｎｏｗｌｅｄｇｅａｎｄＤａｔａＥｎｇｉｎｅｅｒｉｎｇ．１９９６，Ｖ０１．８：５６５—６２３【４０］刘兵，俞勇．Ｗｅｂ数据挖掘【Ｍ】．北京：清华大学出版社，２００９【４１】刘华婷，郭仁祥，姜浩．关联规则挖掘Ａｐｒｉｏｒｉ算法的研究与改进［Ｊ】．计算机应用与软件，２００９，（０１）：１４７［４２］ＡＫＪａｉｎ，ＭＮＭｕｒｔｙ，ＴＰＪＦｌｙｎｎ．Ｄａｔａｅｌｕｓｔｅｒｉｎｇ：Ａｓｕｒｖｅｙ．ＡＣＭｃｏｍｐｕｔｅｒＳｕｒｖｅｙ．１９９９，Ｖ０１．３１．【４３］ＢＤａｔａＯｚｄｅｎ，ＳＲａｍａｓｗａｍｙ，ＡＳｉｂｅｒｓｃｈａｔｚ．Ｃｙｃｌｉｃａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ．Ｉｎｔｅｒｎａｔｉｏｎａｌ１９９８ＣｏｎｆｅｒｅｎｃｅｏｎＭｉｎｉｎｇ，Ａｐｒｉｌ［４４］ＰＢｒａｄｌｅｙ，ＵＦａｙｙａｄ．Ｒｅｆｉｎｉｎｇｉｎｉｔｉａｌｐｏｉｎｔｓｆｏｒｋ－Ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇ．ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅｆｉｆｔｅｅｎｔｈ５５参考文献ｉｎｔｅｍａｔｉｏｎｌｃｏｎｆｅｒｅｎｃｅｏｎｍａｃｈｉｎｅｌｅａｒｎｉｎｇＩＣＭＬ９８，ｐａｇｅ５６－６４．ＭｒｏｇａｎＫａｕｆｍａｎｎ，ＳａｎＦｒａｎｃｉｓｃｏ，１９９８：３８６－３９０［４５１ＰＤｏｍｉｎｇｏｓ，ＭＪＰａｚｚａｎｉ．Ｂｅｙｏｎｄｉｎｄｅｐｅｎｄｅｎｃｅ：ＣｏｎｄｉｔｉｏｎｓｆｏｒｔｈｅｏｐｔｉｍａｌｉｔｙｏｆｔｈｅｓｉｍｐｌｅＢａｙｅｓｉａｎｃｌａｓｓｉｆｉｅｒ．ＩｎＩＣＭＬ９６，ＳａｎＦｒａｎｃｉｓｃｏ，Ｃａｌｉｆｏｒｎｉａ，ｐａｇｅｓｌ３２－１３９，１９９６［４６］Ｗ．Ｈ．ｈｌｍｏｎ．数据仓库［Ｍ】．北京：机械工业出版社，２０００［４７］ＳＢｒｉｎ，ＲＲａｓｔｏｇｉ，ＫＳｈｉｍ．ＭｉｎｉｎｇｏｐｔｉｍｉｚｅｄＧａｉｎｒｕｌｅｓｆｏｒｎｕｍｅｒｉｃａｔｔｒｉｂｕｔｅｓ．ＫｏｒｅａＡｄｖａｎｃｅｄＩｎｓｔｉｔｕｔｅｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＡｄｖａｎｃｅｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙＲｅｓｅａｒｃｈＣｅｎｔｅｒ，ＴｅｃｈｎｉｃＲｅｐｏｒｔ．１９９９［４８］ＪＨａｎ，ＭＫａｍｂｅｒ．ＤａｔａＭｉｎｉｎｇ：ｃｏｎｃｅｐｔａｎｄｔｅｃｈｎｉｑｕｅ．ＭｏｒｇａｎＫａｕｆｍａｎｎＰｕｂｌｉｓｈｅｒｓ，２０００【４９］ＨＪＭｉｌｌｅｒ，ＪＨａｎ．Ｇｅｏｇｒｐｈｉｃｄａｔａｍｉｎｉｎｇａｎｄｋｎｏｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙ．Ｐｈｉｌａｄｅｐｈｉａ：Ｔａｙｌｏｒ，２００１【５０］Ｍ．Ｚａｋｉ，Ｃ．Ｊ．Ｈｓｉａｏ．ＣｈＡＲＭ：ＡｎＥｆｆｉｃｉｅｎｔＡｌｇｏｒｉｔｈｍｆｏｒＣｌｏｓｅｄＩｔｅｒｎｓｅｔＭｉｎｉｎｇ．Ｐｒｏｃ．ＳＩＡＭＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｏｎＤａｔａＭｉｎｉｎｇ，２００２：３４５－３５６［５１］ＲＡｇｒａｗａｌ．ＤａｔａＭｉｎｉｎｇ：Ｃｒｏｓｓｉｎｇｔｈｅｃｈａｓｍ．Ｉｎｖｉｔｅｄｔａｌｋａｔｔｈｅ５ｔｈＡＣＭＳＩＣＫＤＤＩｎｔ’ｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ（ＫＤ９９），１９９９【５２］ＰＫｏｓａｌａ，ＨＢｌｏｃｋｅｅｌ．Ｗｅｂｍｉｎｉｎｇｒｅｓｅａｒｃｈ：Ａｓｕｒｖｅｙ．ＳＩＧＫＤＤ，２（１），２０００：２１６－－２２１［５３］ＲＪＢａｙａｒｄｏ，ＲＡｇｒａｗａｌ，ＤＧｕｎｏｐｕｌｏｓ．Ｃｏｎｓｔｒａｉｎｔ－ｂａｓｅｄｒｕｌｅＭｉｎｉｎｇｉｎＬａｒｇｅ，ＤｅｎｓｅＤａｔａｂａｓｅｓ．Ｐｒｏｅ．ｏｆｔｈｅ１５ｔｈＩｎｔ’ｌＣｏｎｆ．ｏｎＤａｔａＥｎｇｉｎｅｅｒｉｎｇ，１９９９［５４］Ｐ．Ｇｒａｙ，Ｈ．Ｊ．ｗａｔｓｏｎ．数据仓库中的决策支持［Ｍ】．北京：电子工业出版社，２０００：９５～９７【５５］ＪＪＲｏｄｒｉｇｕｅｚ，ＣＪＡｌｏｎｓｏ．Ｂｏｏｓｔｉｎｇｉｎｔｅｒｖａｌ—ｂａｓｅｄｌｉｔｅｒａｌｓ：ｖａｒｉａｂｌｅｌｅｎｇｔｈａｎｄｅａｒｌｙｃｌａｓｓｉｆｉｃａｔｉｏｎ．ＩｎＫＤＳＴＤ０２，Ｌｙｏｎ，Ｆｒａｎｃｅ，ｐａｇｅｓ５５－６２，２００２【５６］ＰＫＡｇａｒｗａｌ，ＣＭＰｒｏｅｏｐｉｕｃ．ＥｘａｃｔａｎｄＡｐｐｒｏｘｉｍｍｉｏｎＡｌｇｏｒｉｔｈｍｓｆｏｒＣｌｕｓｔｅｒｉｎｇ，ＩｎｔｈｅＰｒｏｅ．０ｆＳｏＤＡ，１９９８［５７］ＧＫａｒｙａｐｉｓ．ＥＨＨａｎ，ＶＫ啪ａｒ．ＣＨＡ～正ＬＥＯＮ：Ａｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｕｓｉｎｇｄｙｎａｍｉｃｍｏｄｅｌｉｎｇ．ＣＯＭＰＵＴＥＲ．１９９９，３２（８）：６５－７０【５８］ｗＣＰｅｎｇ，ＭＳＣｈｅｎ．Ｍｉｎｉｎｇｕｓｅｒｍｏｖｉｎｇｐａｔｔｅｒｎｓｆｏｒｐｅｒｓｏｎａｌｄａｔａａｌｌｏｃａｔｉｏｎｉｎａｍｏｂｉｌｅｃｏｍｐｕｔｉｎｇｓｙｓｔｅｍ．Ｐｒｏｃ．ｏｆｔｈｅ２９ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＰａｒａｌｌｅｌＰｒｏｃｅｓｓｉｎｇ，Ａｕｇｕｓｔ，２０００【５９］ＪＰｅｉ．Ｃａｎｗｅｐｕｓｈｍｏｒｅｃｏｎｓｔｒａｉｎｔｓｉｎｔｏｆｒｅｑｕｅｎｔｐａｔｔｅｒｎｍｉｎｉｎｇ？Ｐｒｏｅ．２０００Ｉｎｔ．Ｃｏｎｆ．ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ．Ｂｏｓｔｏｎ，ＵＳＡ，Ａｕｇ．２０００［６０］ｃＨＣａｉ，ＣＨＣｈｅｎｇ，ＷＷＫｏｎｇ．Ｍｉｎｉｎｇａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｗｉｔｈｗｅｉｇｈｔｅｄｉｔｅｍｓ．Ｐｒｏｅ．ｏｆｔｈｅＩｎｔｅｒｎａｔｉｏｎａｌＤａｔａｂａｓｅＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎＳｙｍｐｏｓｉｕｍ，Ｃａｒｄｉｆｆ，Ｗａｌｅｓ，Ｕ．Ｋ．１９９８：５６－６７致谢致谢在这里，我首先要衷心地感谢我的导师陆奎教授。研究生学习期间，陆老师在生活学习的各个方面都给予我极大的关怀与帮助。在论文完成的整个过程中，陆老师付出了大量的精力和心血。陆老师治学严谨、学识渊博，他求真务实的做事态度、兢兢业业的工作精神，将使我受益无穷；陆老师对我的耐心指导和孜孜不倦的教诲，我将永远铭记在心。在此向恩师致以最诚挚的谢意！学习期间，我也得到了实验室里一起学习的同学的帮助，尤其是范志超和孙云霞等，他们给我提供了大量的有关论文的学习资料。在此我也向他们表达我最衷心的感谢。同时我也要感谢在三年研究生学习中给予过无私帮助的所有老师和同学们！我还要感谢我的家人，是他们二直在鼓励我、支持我，给我勇气和信心，是他们对我无私的爱和奉献激励着我顺利完成学业！感谢在百忙之中评审论文并给出宝贵意见的各位老师们！最后，对所有关心、帮助和支持过我的人说一声谢谢１５７作者简介及读研期间主要科研成果作者简介及读研期间主要科研成果作者简介刘芳（１９８０－），女，汉族，安徽省淮南市人，安徽理工大学计算机科学与工程学院计算机应用技术专业硕士研究生。读研期间主要科技成果１．网格技术浅谈．山东科技信息，２００８，２２．２．数据挖掘技术及其在零售业中应用的初步研究．福建电脑，２００９，２５（０８）．数据挖掘中关联规则算法及应用的研究

作者：

学位授予单位：

刘芳

安徽理工大学

引用本文格式：刘芳 数据挖掘中关联规则算法及应用的研究[学位论文]硕士 2010