（产业经济学专业论文）数据挖掘中关联规则应用改进的研究.pdf

2 论论 文文 提提 要要 随着市场竞争的日益激烈，企业越来越意识到信息对于企业决策的重要性，企 业的高管人员不能仅凭经验或者直觉来决定企业发展问题，同时，企业多年信息化 的发展，积累了相当数量的数据资源，为科学决策提供了坚实的数据基础，因此数 据挖掘的出现不仅仅是企业信息化的延伸，也是企业自身发展的需要。 本文对数据挖掘中关联规则的应用进行了研究和改进。首先，分析了数据挖掘 的现状，重点分析了国内外目前相关领域的发展动态以及数据挖掘在各个行业中应 用的情况。其次，明确关联规则是数据挖掘的一个分支，重点是对单维布尔关联规 则的挖掘、多层次关联规则的挖掘、多维关联规则的挖掘进行了细致的研究。在此 基础上，针对挖掘单维布尔关联规则的 apriori 规则在应用上可能出现的问题，提 出 apriori 规则应用改进方法；针对多层次关联规则存在的冗余问题，提出在挖掘 关联规则的过程中商业人员的参与是消除冗余问题的根本保证；此外，本文在支持 度和信任度的基础上借助相关性分析，引出新的阈值相关度。 针对关联规则应用改进的研究成果，结合主流设计模式，提出数据挖掘系统解 决方案，该方案分析了系统的关键技术，其中改进后的关联规则应用是核心。 最后，对本文的研究成果进行了总结，展望了数据挖掘未来的五个发展方向， 以及笔者正在从事的研究课题。 关键字：关联规则 数据挖掘 相关度 支持度 信任度关键字：关联规则 数据挖掘 相关度 支持度 信任度 3 abstract for sharpening their competition, more and more enterprises focus their mind on informatization. the application of data mining origins from informatization of enterprises, and it means that scientific making-decision becomes the mainstream inside of enterprises and the improvement of enterprises adaptability and sensitivity. in the thesis, discuss and study the improvement of application of association rules, which is one of data mining functionalities; put forward data mining system solution and standard process in application of data mining. introduction, i explain the cause and purpose of composing the thesis, introducing domestic and overseas development of data mining, and then placing emphasis on its application of various fields. the second part i composed, narrating the inevitability of occurrence concerning data mining and then educing association rules, which is major content of the thesis. association rules is one of data mining functionalities, it consists of mining single-dimensional boolean association rules, mining multilevel association rules, mining multidimensional association rules and from association mining to correlation analysis. thirdly, according to foregoing content and analysis, i put forward suggestion for application of association rules, it consists of three parts. when we use apriori rule to mine single-dimensional boolean association rules, there are some problems, so that the first part is that improves efficiency of apriori by importing some methods and tools; the second is about redundant problem, which we will encounter, when we mine multilevel association rules. the third, based on support and confidence of association rules and correlation analysis, introducing a new variable- correlation, it can improve the effectiveness and accurateness of application during mining association rules, at the same time, it also helps to further development in improvement of application of association rules. fourthly，i draw a conclusion, which is derived from research on improvement of association rules, designing a data mining system solution, which contains an important outcome. i regard data mining as a process of business, so that putting forward a standard process for data mining. at the end of this thesis; it contains the fruit of research and the problems data mining have to face and solve in the future, and what i am studying. key words: association rules data mining correlation support confidence 4 第一章第一章 绪论绪论 2002 年，笔者在一家美国科技公司工作期间，接触了一些关于数据挖掘方面的 项目。随着企业信息化的不断完善和成熟，随着市场竞争日益加剧，企业不得不面 临着一系列重大决策问题，单凭经验或直觉进行决策是不可能的，因此企业越来越 意识到信息对于企业科学决策的重要性。数据挖掘是一种技术，为企业进行分析和 决策提供支持，它是建立在海量数据的基础上，它的出现是企业自身发展的需要， 也是企业信息化的延伸。 数据挖掘是从数据库中发现知识(knowledge discovery in databases, kdd) 1， 该词首次出现在 1989 年举行的第十一届国际联合人工智能学术会议上， 它包括关联 规则、聚类分析、分类和预测、神经元网络等内容。到目前为止，由美国人工智能 协会主办的 kdd 国际研讨会已经召开了 8 次，课题研究重点也逐渐从发现数据挖掘 的方法转向数据挖掘系统的具体实际应用，注重多样数据挖掘策略和新兴技术的集 成，以及各种学科之间的相互渗透、结合。亚太地区也已经召开了 8 次亚太知识发 现和数据挖掘会议。ieee 的 knowledge and data engineering 会刊率先在 1993 年 出版了 kdd 技术专刊。并行计算、计算机网络和信息工程等其他领域的国际学会、 学刊也把数据挖掘和知识发现列为专题和专刊讨论。 gartner group2的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年 内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据挖 掘列为未来五年内投资焦点的十大新兴技术前两位。根据最近 gartner 的 hpc3研究 表明，随着数据收集、传输和存储技术的快速发展，大型系统用户将更多地需要采 用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增 长点。目前美国在数据挖掘方面的研究走在世界的前列，正在研究基于 xml 的面 向 web 的数据挖掘、专门用于知识发现的数据挖掘语言、关联规则中阈值的智能 化以及人工神经网络在数据挖掘中的应用等领域；同时一些国外公司开发了相关的 数据挖掘系统，如 sas 公司的 enterprise miner、ibm 公司的 intelligent miner、sgi 公司的 setminer、 spss 公司的 clementine4等， 这些系统已经应用在各个行业领域了， 并有相关的成功案例。图 1.1 是数据挖掘的应用领域分布图。 5 图 1.1 数据挖掘的应用领域分布图5 目前我国对于数据挖掘的研究刚起步不久，还处于各自为战的状况，有一些相 应的组织机构，正在从事数据挖掘的基础 理论及其应用研究，这些机构包括清华大 学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京 系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也 在开展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中国科技 大学、中科院数学研究所、吉林大学等机构开展了对关联规则挖掘算法的优化和改 造；南京大学、四川联合大学和上海交通大学等机构探讨、研究了非结构化数据的 知识发现以及 web 数据挖掘。现在国内独立的数据挖掘方面的专著较少，翻译国外 的著作较多，还没有形成相应完善的知识体系，现阶段还主要处于介绍和跟随国外 最新的发展动态。在经费方面，国内数据挖掘研究主要来自国家的科研项目经费， 以及学校、科研机构的自筹经费，还没有形成由公司作为主导的发展阶段。国内应 用数据挖掘成功的案例很多，主要是借助于国外的数据挖掘系统和咨询专家，比如： 美国汇丰银行香港分行用 spss 对不断增长的客户数据进行挖掘分析，建立了预测 模型来发现金融产品交叉销售机会；中国银行信用风险评级管理项目和中国电信选 用了数据挖掘产品 clementine 的营销项目6等等。 通过大量的资料阅读及分析研究，使笔者更加明确了商业领域对数据挖掘的需 求、数据挖掘的应用方向和未来数据挖掘发展前景，进而在研究生学习期间，深入 涉足了该领域的研究。在笔者大量翻阅有关数据挖掘的论文和著作的过程中，发现 6 关联规则在应用上存在一定的局限性，遂在导师的指导下，笔者深入研究了关联规 则应用改进的方法，并且设计出数据挖掘系统解决方案和数据挖掘应用标准流程。 本文通过对关联规则应用领域的分析和研究，为今后在商业领域中应用关联规 则积累了理论的知识和实践的技能，同时为今后进一步研究数据挖掘关联规则改进 和进行系统的开发设计打下坚实的基础，这也是笔者这三年学习和研究工作的一个 成果。 7 第二章第二章 关联规则分析关联规则分析 本章分析了数据挖掘出现的必然性和关联规则应用的方向，以及关联规则的相 关知识和分类。 2.1 数据挖掘出现的必然性 2.1 数据挖掘出现的必然性 在过去 10 多年中，以数据交易、存储为目的的联机分析处理系统(oltp)已经发 展得相当成熟，关系型数据库已经应用在各行各业中，其中大型公司或信息部门积 累了大量原始数据。为了充分利用已有大量数据、提供复杂查询、提供更好的决策 支持，出现了数据仓库(data warehouse)。在数据仓库发展的同时，一项从大量数据 中发现知识、规则的技术也在学术领域兴起，这就是数据挖掘。数据挖掘即数据库 知识发现( kdd)，就是将高级智能计算技术应用于大量数据中，让计算机从海量数 据中发现潜在的， 有用的规则(也叫知识)。 从 80 年代末的初露头角到 90 年代末的广 泛应用，以数据挖掘为核心的商业智能(bi)已经成为 it 及其它行业中的焦点。 为了在将来竞争日益激烈的市场中立于不败之地，越来越多企业开始关注数据 挖掘的应用。数据挖掘的应用起始于企业的信息化。企业信息化指的是信息技术在 企业各个运作流程中的有机应用；这些流程包括物流、资金流、信息流、人流、技 术流、客户流等等。纵观企业的信息化建设，大致经历了三个发展阶段。第一个阶 段是办公自动化（oa） ，标志着电子文件的出现和存储。第二个阶段是管理信息系 统（mis）的建立，标志着数据库和网络的发展应用。第三个阶段是 erp 的实施； 标志着企业业务流程的重组和自动化7。接下来将是数据挖掘和企业智能的建设；这 意味着科学决策在企业的广泛应用。 2.2 数据挖掘中关联规则的应用方向 2.2 数据挖掘中关联规则的应用方向 数据挖掘中关联规则主要应用在金融行业、邮电通信、政府机构、教育机构、 医疗卫生、交通运输、市场研究、制造业、电子商务、零售业。作为企业的决策支 持、客户关系管理、市场分析、营销策略和趋势预测等方面的主要决策工具。这里 以应用最多的客户关系管理 （customer relationship management） 为例说明关联规则 的作用。 客户关系管理： 客户获得 （customer acquisition） 、 客户保留(customer retention)、 8 客户发展(customer development)。在现今的银行业、服务业等领域，如何去发现新 客户群体呢？这就需要找出现有客户群体的社会、经济状态和消费特征；然后按照 这些特征去进行有针对性的营销，以便得到潜在的新客户。如何留住已有客户呢？ 一方面，分析流失客户群体的基本信息，搜寻他们的共同特征，以便对已有客户进 行营销，减少客户流失；另一方面，需要分析已有客户的消费习惯和倾向，从而设 计让客户感兴趣的销售计划和优惠策略，使客户能继续使用自己的产品。如何开发 客户的潜在消费能力呢？这需要挖掘客户的各种特征，研究客户的潜在需求，从而 设计跨线销售，刺激客户消费多样产品，使客户的商业价值达到最大化。这三个方 面的每一项都离不开数据挖掘关联规则，因为数据挖掘关联规则和改进可以提供比 较可靠的依据，使企业进行科学化决策，而不再单纯依赖经验直觉。 2.3 关联规则的基本概念 2.3 关联规则的基本概念 关联规则(association rules)就是从企业历史海量数据中挖掘出描述数据项之间 相互联系的有价值的知识。随着收集和存储在数据库中的数据规模越来越大，人们 逐渐对从这些数据中挖掘相应的关联知识越来越有兴趣。 挖掘关联规则的一个典型应用就是市场购物分析。根据每个小票的内容记录数 据而发现的不同商品之间所存在的关联知识无疑将会指导商家的有关人员分析顾客 的购买习惯。如图 2.1 所示，发现常在一起被购买的商品将指导商家制定有针对性 的市场营销策略。比如：顾客在购买牛奶时，是否也可能同时购买面包或会购买哪 个品牌的面包，显然能够回答这些问题的有关信息肯定会有效地指导商家进行有针 对性的促销，以及进行合适的货架商品摆放。如可以将牛奶和面包放在相近的地方， 以便促进这两个商品的共同销售，或者通过分析得出这两件商品顾客在一起购买的 机率很大，就可以把这两件商品放在相对较远的位置，以便顾客在前往购买的过程 中，增加其它商品的购买机率。 图 2.1 市场购物分析 9 本节将介绍关联规则挖掘的基本知识，包括：第一小节要介绍对超市购物小票 中相关交易记录数据的分析，它是关联规则挖掘的起源；第二小节要介绍关联规则 挖掘的一些基本概念；第三小节则要介绍关联规则挖掘的分类。 2.3.1.购物分析 2.3.1.购物分析 超市的高层管理人员，肯定想要知道超市顾客的购物行为（购物时间，购物人 群等方面） ；尤其是希望得到在一次购物过程中，那些商品会在一起被顾客所购买的 信息。为帮助回答这一问题，就需要进行超市购物分析，即对顾客在超市购物交易 记录数据进行分析。所分析的结果将帮助超市制定有针对性的市场营销和广告宣传 计划，以及合适的商品摆放。其中一种策略就是将频繁在一起购买的商品摆放在相 邻近的位置，以方便顾客同时购买这两件商品；如：如果顾客购买小电器的同时常 也会购买一些电池，那么将电池摆放在小电器附近显然将有助于促进这两种商品的 销售；而另一种策略则是将电池与小电器分别摆放在超市的两端，这就会促使顾客 在购买两种商品时，走更多的路从而达到引导他们购买更多商品的目的。再比如： 顾客在决定购买一台小电器之后，在去购买电池的路上可能会看到其他商品，这时 他就有可能购买这一商品。市场购物分析可以帮助超市主管确定哪些物品可以进行 捆绑销售。 首先将超市所有销售商品设为一个集合，每个商品（item）均为一个取布尔值 （true/false）的变量，如果该 item 出现在购物小票中则表示商品被一个顾客购买。 因此每个顾客的购物小票就可以用一个布尔向量来表示。分析相应布尔向量就可获 得那些商品是在一起被购买的购物知识。如顾客购买小电器的同时也会购买电池的 购物知识就可以用以下的关联规则来描述： appliance=battery support=2%, confidence=60% (2.1) 关联规则的支持度（support）和信任度（confidence）是两个度量有关规则的参 数。它们分别描述了一个被挖掘出的关联规则的有用性和确定性。 规则（2.1）的支持度为 2%，它表示所分析的交易记录数据中有 2%交易记录同 时包含小电器和电池（即它们在一起被顾客购买） 。 规则（2.1）的 60%信任度则表示有 60%的顾客在购买小电器的同时还会购买电 池。 通常如果一个关联规则满足最小支持度阈值（minimum support threshold）和最 小信任度阈值（minimum confidence threshold） ，那么就认为该关联规则是有意义的； 而最小支持度阈值和最小信任度阈值由用户或专家根据行业经验设置。 10 2.3.2 什么是关联规则 2.3.2 什么是关联规则 根据上小节的例子，可以归纳出关联规则的基本概念。 设 i= m iii,., 21 为数据集合合；设 d 为与任务相关的数据集合，也就是一个交 易数据库；其中的每个交易(即顾客的购物小票)t 是一个数据项子集，即 ti；每 个交易均包含一个识别编号 tid。设 a 为一个数据集合合，当且仅当 at 时就称 交易 t 包含 a。一个关联规则就是具有“a=b”形式的蕴含式；其中有 ai，bi 且 ab=。规则 a=b 在交易数据集 d 中成立，且具有 s 支持度和 c 信任度。这 也就意味着交易数据集 d 中有 s 比例的交易 t 包含 ab 数据项；且交易数据集 d 中有 c 比例的交易 t 满足“若包含 a 就包含 b 条件” 。具体描述就是： support (a=b) = p (ab) (2.2) confidence (a=b) =p (b|a) (2.3) 满足最小支持度阈值和最小信任度阈值的关联规则就称为强规则(strong)。通常 为方便起见， 都将最小支持度阈值简写为 min_sup； 最小信任度阈值简写为 min_conf。 这两个阈值均在 0%到 100%之间，而不是 0 到 1 之间。 一个数据项的集合就称为数据集合(itemset)； 一个包含 k 个数据项的集合就称为 k集合。因此集合appliance，battery就是一个 2集合。一个集合的出现频度就 是整个交易数据集 d 中包含该集合的交易记录数；这也称为是该集合的支持度 (support count)。而若一个集合的出现频度大于最小支持度阈值乘以交易记录集 d 中 记录数，那么就称该集合满足最小支持度阈值；而满足最小支持度阈值所对应的交 易记录数就称为最小支持频度(minimum support)。满足最小支持阈值的集合就称为 频繁集合(frequent itemset)。所有频繁 k 集合的集合就记为 k l 。 挖掘关联规则的基本步骤： 步骤一：发现所有的频繁集合，根据定义，这些集合的频度至少应等于（预先 设置的）最小支持频度。 步骤二：根据所获得的频繁集合，产生相应的强关联规则。根据定义这些规则 必须满足最小信任度阈值。 由于步骤一的计算量相当大，因此挖掘关联规则的整个性能就是由步骤一中的 操作处理所决定。 11 2.3.3 关联规则挖掘分类 2.3.3 关联规则挖掘分类 市场购物分析仅仅是一种关联规则挖掘的应用。 根据以下标准对这些关联规则挖掘方法进行分类。 （1） 根据关联规则所处理具体值的情况 若一个规则仅描述数据项是否出现的这种情况，那这种关联规则就是一个布尔 关联规则。例如公式(2.1)所表示的就是一条布尔关联规则。 若一个规则描述的是数值数据项之间的关系，那它就是一个数值关联规则。在 这些规则中，数据项的数值可以划分为不同区间范围。规则(2.4)就是一个数值关联 规则例子： age (x,30-34)income (x,42k-48k)=buys(x,computer) (2.4) 这里的数值属性 age 和 income 均已被离散化了。 （2） 根据规则中数据的名词 若一个关联规则中的项（或属性）仅涉及一个名词，那它就是一个单维关联规 则。规则(2.1)由于只涉及一个名词（属性 buys） ，因此它是一个单维关联规则。可以 重写为规则(2.5)形式。 buys (x,appliance)=buys(x,battery) (2.5) 若一个规则涉及二个或更多维，诸如：属性 buys、属性 time_of_transaction 和属 性 customer_category，那它就是一个多维关联规则。规则(2.4)因为它涉及三个维（属 性 age、income 和 buys） ，所以它也是一个多维关联规则。 （3） 根据规则描述内容所涉及的抽象层次分类 一些关联规则挖掘方法可以发现不同抽象层次的关联规则，例如：挖掘出规则 (2.6)和规则(2.7)。 age (x,30-34)=buys (x,notebook_computer) (2.6) age (x,30-34)=buys(x,computer) (2.7) 在规则(2.6)和规则(2.7)中（属性 buys）的数据项描述涉及不同抽象层次内容 （ “computer”是“notebook_computer”的更高抽象层次） ，由于规则(2.6)和规则(2.7) 内容描述由于涉及多个不同抽象层次概念，因此就构成了多层次关联规则；相反若 一个关联规则的内容仅涉及单一层次的概念，那这样的关联规则就称为单层次关联 规则。 12 2.4 单维布尔关联规则挖掘 2.4 单维布尔关联规则挖掘 根据分类规则，单维单层次布尔关联规则是最简单关联规则。本章最初所介绍 的市场购物实例就是挖掘这种关联规则。apriori 规则是挖掘频繁集合的基本规则, 本节将要分析如何根据所挖掘出的频繁集合生成相应的强关联规则。 2.4.1 apriori 规则 2.4.1 apriori 规则 apriori 规则是挖掘产生布尔关联规则所需频繁集合的基本规则；它也是一个很 有影响的关联规则挖掘规则。在 1993 年，r.agrawal 等人首次提出 8。apriori 规则 就是根据有关频繁集合特性的先验知识 9（prior knowledge）而命名的。该规则采 取一个层次顺序搜索的循环方法来完成频繁集合的挖掘工作。这一循环方法就是利 用了 k 集合来产生(k1)集合。 具体步骤是：首先发现频繁 1集合，记为 1 l；然后利用 1 l来发现 2 l，即频繁 2集合；不断如此循环下去，直到无法发现更多的频繁 k集合为止。每发现一层 k l 就需要扫描整个数据库一遍。 apriori 规则利用了一个重要性质，来帮助有效缩小频繁集合的搜索空间，以便 提高按层次搜索并产生相应频繁集合的处理效率。下面分析这一性质并说明它的用 途。 apriori 性质：一个频繁集合中任一子集也应是频繁集合。 根据常识判断：若一个集合 i 不满足最小支持度阈值 s，那么该集合 i 就不是 频繁集合，即 p（i）s；若增加一个 a 项到集合 i 中，那么所获得的新集合 ia 在整个交易数据库中所出现的次数也不可能多于原集合 i 出现的次数， 因此 ia 也 不可能是频繁的，即 p（ia）s。由此推出：即若一个集合不能通过测试，该集 合所有超集也不能通过同样的测试。 为了解释清楚apriori性质如何应用到频繁集合的挖掘中的， 这里就以用 1k l来 产生 k l 来说明具体应用办法。利用 1k l来获得 k l 主要包含两个处理过程，即连接 （join）操作和删除（delete）操作。 （1） 连接操作。为发现 k l ，可以将 1k l中两个集合相连接以获得一个 k l 的候 选集合 k c。设 1 l和 2 l为 1k l中的两个集合（元素） ，记号 i lj表示 i l中的第 j 个项； 如 i lk-2就表示 i l中的倒数第二项。若 1k l的连接操作记为 1k l 1k l，它表示若 1 l 13 和 2 l中的前 （k-2） 项是相同的， 也就是说： （ 1 l1= 2 l1）( 1 lk-2= 2 lk-2) ( 1 lk-1(l-s)” ；其中 min_conf 为最小信任度阈值。 由于规则是通过频繁集合直接产生的，因此关联规则所涉及的所有集合均满足 最小支持度阈值。以表 2.1 所示数据为例，说明关联规则的生成过程。 16 假设频繁集合 l=i1,i2,i5， 则 l 的非空子集为：i1,i2,i1,i5,i2,i5,i1,i2,i5。 计算所获得的关联规则及其信任度。 ? i1i2=i5 confidence=2/4=50% ? i1i5=i2 confidence=2/2=100% ? i2i5=i1 confidence=2/2=100% ? i1=i2i5 confidence=2/6=33% ? i2=i1i5 confidence=2/7=29% ? i5=i1i2 confidence=2/2=100% 如果最小信任度阈值为 70，那么仅有第 2 个、第 2 个和第 6 个规则，由于它 们的信任度大于最小信任度阈值而被保留下来作为最终的输出。 2.5 挖掘多层次关联规则 2.5 挖掘多层次关联规则 对于关联规则应用来讲，由于数据在多维空间中存在多样性，在不同用户的抽 象思维中也存在不同的表现，因此本节将分析多层次关联规则的挖掘。 2.5.1 多层次关联规则 2.5.1 多层次关联规则 我们要从低层次概念上发现强关联规则可能是较为困难的；而根据过高抽象层 次所挖掘出的强关联规则，有可能只表达了一些普通知识。但是针对客户的信息不 对称，也许一个知识对一个用户来讲是常识性知识，可能对另一个用户就是新奇的 知识。因此应该能够在多个不同抽象层次上，挖掘相应关联规则知识；并能够对不 同抽象层次的内容进行浏览与选择。 数据假设来自表 2.1，描述在一个销售电脑超市中，每个购物小票的 tid 所包 含的商品。而相应的商品概念层次 11树如图 2.7 所示。该概念层次树描述了从低层次 概念到高层次概念的相互关系。在概念层次树中，利用高层次概念替换低层次概念 可实现数据的抽象。如图 2.7 所示的概念层次树共有四层，分别为层次 0、1、2 和 3； 层次自顶而下从 0 开始。 树的根结点标记为 all。 层次 1 包括 computer、 software、 printer 和 computer accessory；层次 2 包括：home computer，laptop computer， education software。financial management software，等等；层次 3 描述最具 体的概念层次。概念层次结构可以由熟悉数据组织结构的用户定义。 17 图 2.7 商品概念层次树示意描述 表 2.2 所示的项（商品）都是如图 2.7 所示的概念层次树中最低层次的项（商 品） 。在这样低层次数据中，很难发现有价值的购买知识；因此要挖掘它们之间的强 关联规则是不可能的，于是乎包含ibm home computer, sony b/w printer的集合 不可能满足最小支持阈值。但若考虑将“sony b/w printer”抽象到“b/w printer” ， 那就有可能较为容易地挖掘有关“ibm home computer”和“b/w printer”之间所 存在的强关联。类似的情况中，许多顾客有更大的可能一起购买“computer”和 “printer” ； 即： 包含抽象后商品项的集合， 如： ibm home computer, b/w printer 和computer, printer要比只包含低层次项，诸如：ibm home computer, sony b/w printer，更易满足最小支持阈值，道理是显而易见的。因此我们要挖掘多层次项 之间所存在的有价值关联要比仅在低层次数据上进行挖掘要容易很多，同时挖掘出 来的知识具有现实意义。 表 2.2 与任务相关的数据示意描述 tid 所购买的商品 1 2 3 4 5 ibm home computer, sony b/w printer microsoft educational software, microsoft financial management software logitech mouse computer-accessory, ergo-way wrist pad computer-accessory ibm home computer, microsoft financial management software ibm home computer 由于利用概念层次树所挖掘出的关联规则涉及到多个概念层次，因此这样的关 联规则就称作是多层次关联规则。 18 2.5.2 挖掘多层次关联规则方法 2.5.2 挖掘多层次关联规则方法 结合前面所述的支持度与信任度的挖掘方法，我们作进一步的讨论。一般而言， 利用自上而下方法，即：从最高层次向低层次方向进行挖掘时，对频繁集合出现次 数进行累计以便发现每个层次的频繁集合直到无法获得新频繁集合为止。 也就是说， 要在获得所有概念层次 1 的频繁集合后；在此基础之上，再挖掘层次 2 的频繁集合； 如此下去，不断循环。对于每个概念层次挖掘，可以利用任何发现频繁集合的规则， 如：apriori。 下面将对这类模式作简单的介绍。如图 2.8 到图 2.12 所示，图中矩形代表已 被检查过的一个项或集合。 （1）采用统一的最小支持阈值（对于所有层次） ，即对不同层次频繁集合的挖 掘均使用相同的最小支持阈值，如图 2.8 所示，整个挖掘均使用最小支持阈值 5%； “home computer”不是频繁集合；但“computer”和“laptop”却是频繁的。 图 2.8 利用统一最小支持阈值的多层次挖掘(黑体框表示满足最小支持值) 想这样，采用统一最小支持阈值，可以大大简化整个搜索的过程。由于客户或 者专家只需要设置一个最小支持阈值，因此整个挖掘方法变得比较简单。基于一个 祖先结点是其子结点的超集，可以采用一个优化技术，即可避免搜索其祖先结点包 含不满足最小支持阈值的集合 12。 图 2.9 利用递减阈值的多层次挖掘 但是应用统一最小支持阈值也存在一些问题。在实际中，由于低层次项不可能 19 比相应项的高层次出现的次数更多。如果最小支持阈值设置过高，那就可能忽略掉 低层次中有价值的一些关联知识；而若设置阈值过小，那就可能产生过多的高层次 无价值的关联知识， 。由此也就有了第二种多层次关联规则挖掘方法。 （2）在低层次利用较小的阈值，又称为递减阈值。所谓递减阈值，每一抽象层 次均设定相应的最小支持阈值。抽象层次越低，相应的最小支持阈值也就越小。如 图 2.9 所示， 层次 1 和层次 2 的支持度分别为 5和 3。 这样 “computer” 、“laptop computer”和“home computer”都是频繁集合。 利用递减阈值来挖掘多层次关联知识，可以选择若干搜索策略，这些策略包括： 层次与层次相互之间独立。没有利用任何频繁集合的有关知识、性质来帮助 进行集合的修剪。不管该结点的父结点是否为频繁的，均要对每个结点进行频繁检 查； 利用单项进行跨层次检查。当且仅当相应父结点在（i-1）层次是频繁的，方 才检查在 i 层次的单项。也就是说根据一个更普遍的来确定检查一个更具体的。如 图 2.10 所示。 图 2.10 进行单项跨层次过滤和利用递减阈值的挖掘 利用 n集合进行跨层次过滤。当且仅当相应父 n集合在（i-1）层次是频 繁的，方才检查在 i 层次的 n集合。如图 2.11 所示。 图 2.11 利用递减阈值和进行 n集合跨层次过滤的多层次挖掘 分析层次与层次独立的策略，方法由于过于宽松而必然导致，要检查无数较低 20 概念层次的频繁项；并挖掘出许多没有太大实际价值的关联知识，同时也缺乏效率。 利用 n集合进行跨层次过滤的方法， 允许挖掘系统仅仅检查频繁 n集合的子 结点。由于通常并没有许多 n集合（特别当 n2 时）在进行合并后仍是频繁集合， 所以利用这种方法可能会漏掉一些有价值的知识。 利用单项进行跨层次过滤方法，就是上述两个极端方法的综合。但这种方法有 可能会遗漏有关低层次项之间的关联知识，即这些项在使用递减支持阈值时是频繁 集合；即使它们的祖先结点不是频繁的。 2.6 多维关联规则的挖掘 2.6 多维关联规则的挖掘 本节中将分析含有多个谓词的关联规则的挖掘。 前面所介绍的关联规则都只涉及一个谓词，如 buy 谓词。比如在一个超市的数 据库挖掘中，所挖掘出的布尔关联规则： ibm_home_computer=sony_b/w_printer，也可以改写成： buys(x, “ibm_home_computer”) =buys(x,“sony_b/w_printer”) (2.11) 其中 x 为代表顾客的一个变量；同样一个多层次关联规则 ibm_home_computer=b/w printer 就可以改写为： buys(x, ”ibm_home_computer”)=buys(x, “b/w_printer”) (2.12) 利用多维数据库所使用的术语，这里将规则中每个不同的谓词当作一维。因此 规则（2.11）和规则（2.12）因为都只包含一个特定的谓词（如：buys） ，所以就被 称为是单维关联规则。从前面所介绍的关联规则及其挖掘方法可以看出这类规则都 是从交易记录数据（transaction data）中挖掘出来。 如果不是对交易数据库而是对存储在关系数据库或数据仓库中的销售或其它数 据进行挖掘，这时的数据是以多维形式定义存储的。如为了跟踪销售交易中的被购 商品的踪迹。一个关系数据库可能记录了有关这些商品的其它属性，诸如：被购买 的数量或价格，以及有关购买该商品顾客的附加信息，如：顾客年龄、职业、信用 评级、收入和地址等；如果将数据库或数据仓库中这些属性看成谓词，那么挖掘包 含多个谓词的关联规则可能就是很有价值的。如： age（x,“19-24”）occupation(x,“student”)=buys(x,“laptop”) (2.13) 包含两个或更多的谓词的关联规则就称为多维关联规则。规则（2.13）包含 三个不同谓词（age、occupation 和 buys） 。规则（2.13）中的谓词都只出现一次， 因此它是无重复谓词，而无重复谓词的多维关联规则就称为维内关联规则 （inter-dimension rules） 。含有重复谓词的关联规则就被称为混合维关联规则。 21 规则（2.14）就是这样一条规则，其中 buys 谓词重复多次。 age（x,“19-24”）buys(x,“laptop”)=buys(x,“b/w_printer”) (2.14) 由于数据库中的属性可以是符号型或数值型。符号型属性仅取有限个无序的值 （如： occupation、 brand 和 color） ； 而数值型属性取有大小的数值 （如： age、 income 和 price） 。可以根据如何处理数值量的三种基本方法而对挖掘多维关联规则相关技 术进行分类讨论： （1）第一种方法中，需要利用概念层次树将数值属性离散化。这一离散化过程 需要在数据挖掘之前完成。如：可以利用 income 概念层次树中的区间范围来替换原 来属性取值，即“0k-15k” 、 “16k-30k”和“31k-45k”等来替换 income 属性的具体 取值。这里的离散化是静态的且是事先确定好的。利用区间范围离散化后所获得的 数值型就可以当作符号型。因此这种挖掘就被称为是利用数值属性静态离散化的多 维关联规则挖掘。 （2） 第二种方法中， 基于数据分布而将数值属性离散化到 “bins” 中， 这些 “bins” 在挖掘过程中可以作进一步的组合。这一离散化过程是动态的且可根据一些挖掘要 求，如使所挖掘出的规则信任度最大，来进行实施。由于这种方法仍将数值属性当 作数值而没有当作事先所确定好的范围或符号，因此利用这种方法所挖掘出的关联 规则就称为数值关联规则。 （3）第三种方法中，对数值属性进行离散化以便其能够描述出如此间隔的数据 所具有的实际意义。这一动态离散化过程主要是考虑数据点之间的距离。因此这类 数值关联规则也称为基于距离的关联规则。 现在再研究挖掘多维关联规则的有关方法。这里就仅讨论维内关联规则。与单 维关联规则挖掘相比，多维关联规则挖掘不是搜索频繁集合而是搜索频繁谓词集 （predicatesets） 。 一个 k谓词集就是包含 k 个合取谓词的集合。 如： 规则 （2.13） 包含三个谓词，即（age、occupation 和 buys）就是一个 3谓词集。与集合符号 类似，也可以使用 k l 来表示频繁 k谓词集。 22 第三章第三章 关联规则应用改进关联规则应用改进 在数据仓库系统体系的应用中，包括数据源、数据处理（etl） 、数据仓库、在 线分析处理（olap） 、数据挖掘应用和展现工具。目前，这六部分的发展进度参差 不齐，由于 xml13的出现，使数据的存储和表示有了统一性。随着 xml 的发展和 越来越多的企业采用 xml 作为规范，来标识和存储数据，使得数据处理和数据的 装载入库更加富有效率。现阶段主要是结合行业知识，从海量数据中挖掘和展现有 用的知识或模式，来帮助企业进行分析和决策工作，这是目前的难点和热点。 到目前为止，如果直接应用现有的数据挖掘关联规则来处理商业问题，帮助各 相关行业解决实际中的商业问题，如超市营销、新产品的定位、顾客群体细分、信 用度调查等，还存在一定的不可操作性和局限性，因为关联规则还停留在基础理论 与研究阶段，不能产生实际的效力。因此结合第二章的数据和图表，在本章中进行 了部分关联规则应用局限性和改进的分析研究。 3.1 对于 apriori 规则应用的改进 3.1 对于 apriori 规则应用的改进 在第二章的论证过程中，可以发现 apriori 规则在应用上存在一定的局限性， 现将其局限性总结如下： (1) apriori 规则需多次扫描数据库。所以，其改进的一个方向是减少数据库 扫描的次数。 (2) apriori 规则产生大量的候选项目集，这些频繁项目集的存储和计数的开 销很大。所以，其改进的另一个方向是减少候选项目集的个数。 (3) apriori 规则主要操作是支持度计数，可采用一些技巧来改进支持度计数。 下面就将引入一些改进方法。 3.1.1 改进 apriori 规则的运行效率 3.1.1 改进 apriori 规则的运行效率 (1) 基于哈希 14（hash）表技术 基于哈希表技术可以帮助有效减少候选 k-集合 k c (k1)所占用的空间。比如， 在扫描交易数据库，从候选 1-集合 1 c中产生频繁 1-集合 1 l时，就可以为每个交易 记录产生全部 2-集合，并将它们导入到 hash 表的不同栏目中，且增加相应栏目的 计数。如表 3.1 所示。hash 表中一个存放 2-集合的栏目计数若低于最小支持频度， 23 则表示相应 2-集合为非频繁集合而被移出候选集合。利用这样 hash 表技术