（计算机软件与理论专业论文）基于品类信息的关联规则挖掘算法及其应用.pdf

基于品类信息的关联规则算法及其应用 中文摘要 中文摘要 市场竞争日趋激烈，商家需要充分了解自己的顾客，很多商家应用关联规则挖 掘来分析顾客的购买行为。目前，如何提高关联规则的挖掘效率仍然是研究的重点。 本文提出了一种基于品类聚类的关联规则优化算法。该算法首先根据文中定义的品 类特征向量，用结构化的数据来表示事务：然后根据一种基于密度的聚类算法，对 结构化的数据进行聚类，同时将对应的原始事务进行聚类；最后根据聚类后得到的 类的长度以及用户指定的最小支持度，确定类内的最小支持度，在类内挖掘关联规 则。实验结果表明，与传统算法相比，该算法效率较高，具有一定的实用价值。 本文的应用背景是货物进出口检验检疫系统，在检验检疫过程中，物品名称都 是由几个词语构成，如果能找出某几个单词与某一个编码之间的关系，将对物品的 自动编码提供很大的帮助。本文提出了一种方案，基于物品名称的品类信息，结合 上海浦东国际机场检验检疫局h s 商品编码辅助决策系统的需求。将基于品类聚类的 关联规则算法，应用到上述系统当中，有效地找出了某几个单词之间的关联规则， 利用这些关联规则优化规则库，实现了待检验商品的智能化编码。 关键词：品类信息，事务聚类，关联规则，商品编码，检验检疫 基于品类信息的关联规则算法及其应用 a b s t r a c t a b s t r a c t d u et ot h ef i e r c ec o m p e t i t i o n ，e n t e r p r i s e sn e e dt ok n o wm o r ea b o u tt h e i rc u s t o m e r s al o to f e n t e r p r i s e sa p p l ya s s o c i a t i o nr u l e st oa n a l y z et h eb e h a v i o r so ft h e i rc u s t o m e r s n o w , i ti ss t i l lh o tt h a t h o wt om a k et h ea l g o r i t h mo fm i n i n ga s s o c i a t i o nr u l e sm o r ee f f e c t i v e b a s e do l lt h e r e q u i r e m e n to fa p p l y i n ga s s o c i a t i o nr u l e sa n dt h ec h a l l e n g eo fm a k i n gt h ea l g o r i t h mo f m i n i n ga s s o c i a t i o nr u l e sm o r ee f f e c t i v e ，ac a t e g o r y - b a s e da l g o r i t h mi sp r o p o s e di nt h i s p a p e rt o e n h a n c em i n i n ga s s o c i a t i o nr u l e sf o rm a r k e tb a s k e ta n a l y s i sa n ds p a c e m a n a g e m e n t t h i sa l g o r i t h mi n v o l v e st h r e es t e p so fp r o c e s s i n g ：t r a n s a c t i o n sa r ef w s t r e p r e s e n t e da st r a n s a c t i o n c a t e g o r yp o i n t sb a s e do nt h ep r e d e f i n e dc a t e g o r yf e a t u r e v e c t o r s ；t h e s et r a n s a c t i o n c a t e g o r yp o i n t sa n dt r a n s a c t i o n sa r et h e nc l u s t e r e dw i t ht h e a p p l i e dc l u s t e r i n ga l g o r i t h m ；f i n a l l y , t h em i n i m u ms u p p o r to ft h ec l u s t e ri sc a l c u l a t e d b a s e do nt h er e s u l tn u m b e ro fp o i n t si nas p e c i f i e dc l u s t e ra n dt h eu s e r - d e f i n e dm i n i m u m s u p p o r t ，a n dat r a d i t i o n a la l g o r i t h mi sa p p l i e dt og e ta s s o c i a t i o nr u l e si nt h ec l u s t e r t h e e x p e r i m e n t a lr e s u l ts h o w st h a tt h i sa l g o r i t h mi se f f e c t i v ea n dp r a c t i c a l i np r o c e s so fe x p r e s si n s p e c t i o na n dq u a r a n t i n e ，t h en a m e so fg o o d sa r ec o m p o s e d o fs e v e r a lw o r d s m i n i n gt h ea s s o c i a t i o nr u l e sb e t w e e nw o r d sc o u l da d dv a l u et o a u t o m a t i cc o d i n go fg o o d s b a s e do nt h ec a t e g o r yi n f o r m a t i o n ，a c c o r d i n gi ot h e r e q u i r e m e n to fh si n t e l l i g e n tc o d i n gs y s t e m ，t h ea l g o r i t h mb a s e do nc a t e g o r yc l u s t e r i n g f o rm i n i n ga s s o c i a t i o nr u l e si sa p p l i e dt om i n et h ea s s o c i a t i o nr u l e sb e t w e e nw o r d so f g o o d s ，a n dt h e nt h er u l e si su s e dt oo p t i m i z et h eh s t r e ei no r d e rf o ra u t o m a t i cc o d i n g k e yw o r d ：c a t e g o r yi n f o r m a t i o n ，t r a n s a c t i o nc l u s t e r i n g ，a s s o c i a t i o nr u l e s + h s c o d i n g ，i n s p e c t i o na n dq u a r a n t i n e 基f 品类信息的关联规则算法及其应用 1 1 研究背景 第一章绪论 绪论 数据挖掘技术从其诞生开始就很自然地应用到决策支持系统中。目前数据挖掘 技术的应用研究主要针对金融、零售、电信等行业，因此在这些行业的决策支持系 统中获得了广泛的应用。比如，在银行和金融机构中产生的金融数据通常比较完整， 可靠和高质量，这就大大方便了系统化的数据分析和数据挖掘，使银行可以推出丰 富多样的储蓄和投资服务。在零售业中，也积累了大量的销售数据，顾客购买历史 记录，货物进出，消费与服务记录等，在这些数据上进行挖掘，可以识别顾客购买 行为，发现顾客购买模式和趋势，提高货物销量比率，减少商业成本。关联规则的 发现是数据挖掘的重要内容，在零售业、保险业、医疗业、物流业，关联规都得到 了极为广泛的应用。尤其在零售业，关联规则的应用能够辅助企业进行商场货架的 组织、布局和穿行路线的设计等。 本文提出一种基于品类聚类的关联规则算法，采取一种分而治之的策略。该算 法基于事务的品类信息，根据算法定义的基于密度的聚类算法，对事务数据进行聚 类，将具有关联信息的的数据聚成一个个类，然后在类内挖掘关联规则。 本文的具体应用背景为海关进出口监管中的h s 自动编码业务。t t s 目录通过5 7 层分类，系统化的国际贸易中的产品进行了归类和编码。日前，h s 编码已经被世界 上大多数国家用于海关进出口监管和统计。面对工作量巨大的i s 编码查询和确认工 作，海关，检验部门以及国际贸易代理都需要一个自动化的h s 编码查询工具来提高 j ； l k 务效率。在货物进出口检验检疫过程中，我们可以通过对历史数据进行挖掘， 找出货物名称与h s 编码的潜在联系，以此实现待检验物品的自动编码，然后通过编 码来决定该物品的检验检疫策略。在物 编码的数据挖掘中，发现和利用关联规则 是非常重要的内容。 1 2 研究目的 如何提高关联规则挖掘效率是关联规则挖掘的研究热点之一，本文拟利用品类 信息提高关联规则挖掘的效率。然后针对上海浦东国际机场检验检疫局出入境快件 第l 页共4 0 页 基0 ：品类信息的关联规则算法及其应用 绪论 检验检疫电子监管系统的具体需求，将优化后的算法应用于上述系统的h s 智能编码 予系统中。本文研究的目的在于：充分利用商品的品类信息，提高关联规则挖掘的 效率；根据挖掘出的关联规则，优化h s 规则库，提高匹配的精度，实现自动化编码。 1 3 研究内容 本文的工作主要集中在两方面，一方面是理论研究，研究如何利用品类信息对 数据进行聚类，通过分而治之的策略提高关联规则算法的效率，然后，以模拟数据 为挖掘对象，通过与传统算法的比较，对本文提出算法的效率进行评估；另一方面 是应用研究，研究如何将上述算法应用到上海浦东国际机场检验检疫局出入境快件 检验检疫电予监管系统，加强该系统h s 商品编码辅助决策模块的自动编码功能，以 实现待检验商品的智能化编码。 1 3 1 基于品类聚类的关联规则算法 本文的研究对象为一种基于品类聚类的关联规则算法。该算法基于事务的品类 信息，根据算法定义的基于密度的聚类算法，对事务数据进行聚类，将具有关联信 息的的数据聚成一个个类，然后在类内挖掘关联规则。在研究算法的基础上，通过 实验数据将该算法与传统关联规则算法相比，考察其关联规则挖掘的效率以及扩展 性。 1 3 2 算法在上海检验检疫局h s 商品编码辅助决策系统中的应用 h s 商品编码辅助决策系统是某出入境快件检验检疫电了监管系统的了系统之 一一。它使用了一种面向查验的实现方法，结合了知识库，语义分析和语义分类：该 方法首先对商品名称进行分析，识别出关键语素。然后根据识别出的语素搜索规则 库，找到置信度最高的规则，并给出相应的h s 编码。该系统实现了a 动化的h s 编 码查询，大大提高了海关进出口监管的业务效率。 货物进出口检验检疫过程中，物品名称都是由几个词语构成，如果能找出某几 个单词与某一个编码之间的关系，将对物品的自动编码提供很大的帮助。本文基于 物品名称的品类信息，结合上海浦东国际机场检验检疫局出入境快件检验检疫电了 监管系统的需求，探讨如何将基于品类聚类的关联规则算法，应用到上述系统当中， 找出某几个单词之间的关联规则，并利用这些关联规则优化规则库，以实现待检验 第2 页共4 0 页 基于品类信息的关联规则算法及其应用 商品的智能化编码。 1 4 章节安排 绪论 论文其余章节的安排如下： 第二章对数据挖掘和关联规则挖掘的研究现状进行了总结，并分析了目前关 联规则挖掘存在的问题。 第三章提出一种基于品类聚类的关联规则算法，采取一种分而治之的策略。 该算法基于事务的品类信息，根据算法定义的基于密度的聚类算法，对事务数据进 行聚类，将具有关联信息的的数据聚成一个个类，然后在类内挖掘关联规则。最后 通过实验证明，该算法与传统关联规则算法相比，能够提高关联规则挖掘的效率， 并具有较好的扩展性。 第四章结合上海浦东国际机场检验检疫局出入境快件检验检疫电了监管系统 的需求，将基于品类聚类的关联规则算法，应用到上述系统当中，找出某几个单词 之间的关联规则，利用这些关联规则优化规则库，以实现待检验商品的智能化编码。 第五章对目前研究工作进行了总结并对未来研究工作进行了展望。 第3 页共4 0 页 基于品类信息的关联规则算法及其应用 关联规则挖掘技术现状 第二章关联规则挖掘技术现状 2 1 数据挖掘研究现状与挑战 随着现代信息科学技术的发展，数据库管理系统在电予政务和电予商务中的应 用越来越广泛，数据库的规模也在不断地扩大。许多大型数据库的容量都已经达到 7 t b 级，积累了海量的业务数据，例如客户数据、交易历史数据、销售记录等等。 这些数据库中蕴含着大量有价值的信息。但是，目前应用的数据库系统尽管可以高 效的实现数据录入、查询、统计等功能，却无法发现数据中存在的关系和规则，无 法根据现有的数据预测未来的发展趋势。使得数据的拥有者不得不面对“数据丰富， 知识匾乏”的尴尬处境。面对这种数据的汪洋大海，如何从中发现有价值的信息成 为政府或企业巫需解决的一个重要问题。在这种应用需求的驱动下，数据挖掘( d a t a m i n i n g ，简称叫) 研究应运而生。 历史上，从数据中发现模式的提法很多，如知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ，简称k d d ) 、知识提取、信息收割、数据采集等等。在数据库领域一般 称为数据挖掘，而在机器学习领域则更多地称作知识发现。 知识发现一词首次出现在1 9 8 9 年举行的第十一届国际联合人工智能学术会议 上。到甘前为止，由美国人工智能协会丰办的k d d 国际研讨会已经召开了8 次，规模 由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系统应 用，注重多种发现策略和技术的集成，以及多种学科之间的相瓦渗透。从大型数据 库中发现信息或知识已经成为数据库和机器学习领域的一个重要的研究课题：同时 许多公司也意识到数据挖掘是提高公司决策能力增加企业收益，提高企业竞争力的 一个重要方面。数据挖掘发现的知识可以应用于信息管理、决策支持、过程控制等 领域，包括数据库领域、机器学习、统计学、知识工程与知识管理、人工智能等领 域的专家都对数据挖掘产牛了浓厚的兴趣。 2 1 1 数据挖掘的定义 数据挖掘概念有广义和狭义之分。目前比较公认的是w f r a w l e y 等人提出的广 义的数据挖掘概念，即从大型的数据库中发现潜在的、新颖的、有价值的、可用的、 第4 页共4 0 页 基于t 讯类信息的关联规则算法及其应用 关联规则挖掘技术现状 能被用户理解的模式和信息的过程狭义的数据挖掘是指数据库中的知识发现的一个 重要步骤。数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各 种商业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问， 进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段， 它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系， 从而进一步深化了对数据的理解。 下面对数据挖掘定义作详细的解释： 数据：数据是指一个有关事实的集合，描述事物有关方面的信息，一般来说这 些信息应该是准确无误的。数据是挖掘的对象，它不仅仅只是数据库，也可以是文 件系统。或是其他任何组织在一起的数据集合，例如w e b 信息资源等。 模式：对于集合f 中的数据，我们可以用l 来描述其中的数据的特征。表达式 ( e 三) 所描述的数据是集合f 的一个予集b 。只有当表达式e 比列举足中所有 元素的描述更为简单时，才可以称之为一个模式。 处理过程：数据挖掘是个多阶段的处理过程，包括数据预处理、模式提取、 知识评价和过程优化等步骤。 可用性：经过数据挖掘得来的模式必须是有一定的有效程度。否则数据挖掘就 毫无意义。可以通过新增数据来检验模式的正确性。 新颖性：通过数据挖掘产牛的模式必须是新颖的。模式是否新颖可以通过两个 途径来衡量，其一是得到的数据，通过对比当前得到的数据和以前数据中期望得到 的数据来判断该棋式的新颖性，二是通过其内部所包含的知识，通过对比发现的模 式与已有模式的关系来判断。 可理解：数据挖掘的一个重要目标是将数据中聪藏的模式以可被人理解的形式 表现出来，从而帮助人们更好地理解数据中包含的信息。所以挖掘结果应避免过于 复杂和抽象。 2 1 2 数据挖掘的分类 从不同的角度看，数据挖掘技术有多种不同的分类方法，根据发现的知识的种 类分类，数据挖掘的丰要研究内容分为： ( 1 ) 总结( s u m m a r i z a t i o n ) 规则挖掘 ( 2 ) 特征( c h a r a c t e r i z a t i o n ) 规则挖掘 第5 页共4 0 页 基于品类信息的关联规则算法及其应用关联规则挖掘技术现状 ( 3 ) 关联( a s s o c i a t i o n ) 规则挖掘 ( 4 ) 分类( c l a s s i f i c a t i o n ) 挖掘 ( 5 ) 聚类( c l u s t e r i n g ) 挖掘 ( 6 ) 趋势( t r e n d ) 分析 ( 7 ) 偏差( d e v i a t i o n ) 分析 ( 8 ) 模式分析( p a t t e r na n a l y s i s ) ， 如果以挖掘知识的抽象层次划分，又有： ( 1 ) 原始层次( p r i m i t i r el e v e l ) 的数据挖掘 ( 2 ) 高层次( h i g hl e v e l ) 的数据挖掘 ( 3 ) 多层( m u l t i p l el e v e l ) 数据挖掘。 根据挖掘的数据库类型分类。数据挖掘基于的数据库类型有： ( 1 ) 关系型( r e l a t i o n a l ) 数据库 ( 2 ) 事务型( t r a n s a c t i o n a l ) 数据库 ( 3 ) 面向对象( o b j e c t e d o r i e n t e d ) 数据库 ( 4 ) 丰动型( a c t i v e ) 数据库 ( 5 ) 空间( s p a t i a l ) 数据库 ( 6 ) 时态( t e m p o r a l ) 数据库 ( 7 ) 文本型( t e x t u a l ) 数据库 ( 8 ) 多媒体( m u lt i p l e m e d i a ) 数据库。 根据采用的技术分类，常用的数据挖掘技术包括： ( 1 ) 人工神经网络：它从结构上模仿牛物神经网络，是一种通过训练学习的 非线性预测模型。它可以完成分类、聚类、特征挖掘等仟务。 ( 2 ) 决策树：用树形结构来表示决策集合。这些决策集合通过对数据集的分 类产q i 规则。典型的决策树方法有分类回归树( c a r t ) 、i d 3 神1 c 4 5 。 ( 3 ) 遗传算法：是模拟牛物进化过程的算法，在设计中使用抽象于牛物进化 过程的、基于自然选择和牛物遗传机制的一种新的优化技术。基于牛物进化的概念 设计了一系列的过程来达到优化的目的。这些过程有基因组合、交叉、变异和自然 选择。为了应用遗传算法，需要把数据挖掘仟务表达为一种搜索问题而发挥遗传算 法的优化搜索能力。 ( 4 ) 规则归纳：通过统计方法归纳、提取有价值的i f t h e n 规则。规则归纳的 技术在数据挖掘中被广泛使用，例如关联规则挖掘。 ( 5 ) 最近邻技术：这种技术通过k 个最与之相近的历史记录的组合来辨别新的 第6 页共4 0 页 基于品类信息的关联规则算法及其应用 记录。这种方法主要应用在聚类和偏差分析等挖掘任务。 ( 6 ) 其他方法，例如粗集等。 2 1 3 数据挖掘的过程 关联规则挖掘技术现状 数据挖掘是一个多阶段数据处理过程，主要包括以下几个步骤： 第一步：了解应用领域的知识。在开始知识发现之前最先的同时也是最重要的 就是了解你的数据和业务问题。 第二步：数据集成与数据清洁。数据集成将与研究问题相关的多文件或多数据 库运行环境的数据进行合并处理，数据清洁则解决数据中的语义模糊j 性、处理数据 中的遗漏、噪声和脏数据等 第三步：数据选择与预处理。数据选择的目的是辨别出需要分析的数据集合， 缩小处理范围，提高数据挖掘的质量。预处理则是针对特定的算法对数据进行有序 的组织和排列。 第四步：选择数据挖掘功能。根据挖掘任务的需要选择相应的挖掘功能，例如 分类或关联规则挖掘等。 第五步：选择数据挖掘算法进行数据挖掘。 第六步：模式评估。对挖掘出来的模式进行评估，可视化、转换和知识的表达。 第七步：知识的应用。 图2 1 显示了数据挖掘的基本过程。 第7 页共4 0 页 基于品类信息的关联规则算法及其应用 2 1 4 数据挖掘的应用 图2 1 数据挖掘的基本过程 关联规则挖掘技术现状 数据挖掘技术的应用领域非常广泛，在政府管理决策、商业运营决策、科学研 究和工业企业决策支持等各个领域都能应用数据挖掘技术。其中应用比较广泛的方 向包括： 市场营销：通过对顾客交易的数据进行分析可以有效地对顾客群体进行划分， 预测不同群体的购买行为和需求大小，进行有针对性的营销设计。运用模式识别和 聚类分析的方法，通过提取客户资料，对客户和它们对几种不同商品的兴趣进行聚 类分析，可以发现潜在客户的具体特征，从而对这些潜在客户进行相应的促销宣传。 优化网站结构：网站作为电了商务的基础平台，它的设计与调整直接影响着电 了商务的正常开展。通过应用网络挖掘我们可以从用户的访问信息中发现有价值的 知识，从而指导网站设计者更新网站结构与内容，更好地与客户进行交流。，而且 可以进一步实施针对于个性化用户或用户群的访问界面，从而开展有针对性的电了 第8 页共4 0 页 基 ：孤类信息的关联规则算法及其应用关联规则挖掘技术现状 商务以满足访问者的需求。 欺诈侦测：在电子商务中，电子交易是其中的一个重要组成部分，而信用卡又 在电子交易中扮演了重要的角色。通过运用数据挖掘中的离群数据挖掘方法或聚类 方法总结正常交易行为和诈骗行为之间的关系，获取诈骗行为的一些特性。利用这 些知识去分析和判断现有交易中，哪些具有诈骗的倾向，如发现某项业务符合这些 特征时，可以向决策人员提出警告。 通信网络管理：在通信网络运行过程中，由于设备、环境和操作等因素会产生 一系列警告，运用数据挖掘技术可以通过分析己有的警告信息的正确处理方法以及 警告之间的前后关系的记录，得到警告之间的关联规则，这些有价值的信息可用于 网络故障的定位检测和严重故障的预测等任务中，使通信网络得以安全运转。 牛产、销售和零售业：预测销售额；企业产品库存决策、批发点分布的规划、 调度和调整。 制造业：预测机器故障，发现影响生产能力的主要因素。 保险业：分析决定医疗保险额的丰要因素，预测顾客的保险模式，有针对性的 设计险种。 交通业：航空公司可以利用数据挖掘技术寻找乘客的旅行模式，改进航线的设 置和票价的制定，以吸引更多的旅客。 科学研究：利用数据挖掘技术可以处理大量的数据，例如在牛物d n a 分析、新 药的药理分析和治疗机理和天文学研究等领域都可以找到数据挖掘技术的应用空 间。目前己经有一些数据挖掘系统在科学研究和牛产实践中发挥着重要的作用 2 1 5 数据挖掘面i 临的挑战 目前数据挖掘研究还很不成熟，其应用还有较大的局限性，目前数据挖掘研究 面临的问题与挑战丰要包括： ( 】) 处理不同类型的数据 i j 前绝大多数数据库系统是关系型数据库，对数据挖掘系统最摹本的要求就是 能够处理关系型的数据f u 同时随着数据库技术的发展许多数据库系统包含着复杂 的数据类型，包括文本数据、多媒体数据、空间数据和时态数据。数据挖掘系统对 这些数据库的操纵能力是至关重要的。一个好的数据挖掘系统要求能够有效地挖掘 各种不同的数据类型并处理不同类型的数据和数据源。 第9 页共4 0 页 基于品类信息的关联规则算法及其应用关联规则挖掘技术现状 ( 2 ) 基于不同的概念抽象层次进行交互式的知识挖掘 由于在数据挖掘过程中我们无法准确预知挖掘的结果，一个基于高度抽象层次 的数据挖掘查询可以为进一步的挖掘提供有价值的线索。交互式的挖掘允许用户在 挖掘过程中交互地定义挖掘任务并动态地调整挖掘任务的焦点。、使用户可以从不同 的角度和不同的抽象层次上浏览数据和挖掘结果。 ( 3 ) 数据挖掘结果的有效表示 通过数据挖掘可以发现各种不同的知识，有效地表示这些知识可以使用户更好 地理解挖掘结果，这就要求数据挖掘系统要用高度语言化和图形化的表示方式向用 户显示挖掘结果。 ( 4 ) 算法效率和可伸缩性 数据挖掘与传统的机器学习的区别在于：数据挖掘是直接面向海量数据库系统 的这类数据库通常有上百个属性和数百万个记录，并且数据表之间包含复杂的关系 这就必然导致数据挖掘过程中搜索维数和搜索空间的激增，为了有效地从数据库中 发现信息，数据挖掘算法必须是有效的和可度量的。也就是说基于大型数据库的数 据挖掘算法的运行时间必须是可以预测的和可以接受的。同时大量的属性和记录的 存在也增加了出现不确定性和病态模式的可能性。因此提高算法的效率以及具有规 模伸缩性是它们在实际应用中必须面对的巨大挑战。 ( 5 ) 数据的私有性和安全性 数据挖掘能从不同的角度、不同的抽象层上看待数据，这会潜在地影响到数据 的私有性和安全性。研究数据挖掘可能导致的非法数据入侵，同样是实际应用过程 中亟待解决的问题 ( 6 ) 国际互联网上的数据挖掘 瓦联网规模的爆炸性增长，使其成为一个全球规模的信息源，从中可以发现大 量的新知识，因此，国际瓦联网数据挖掘具有诱人的前景，正吸引越来越多研究人 员的兴趣。 ( 7 ) 数据挖掘系统交瓦性 数据挖掘是一个复杂的过程，数据挖掘过程中操作者的适当参与是必不可少的 系统的交瓦能力对系统的性能是至关重要的，一方面，交互界面接收用户的检索、 查询要求和数据挖掘策略，为用户提供方便的于段来表达其要求和策略是这方面的 关键，另一方面，交互界面又把牛成的结果显示给用户，在这里，由于牛成的结果 是多种多样的，因此，准确而直观地描述挖掘的结果和友好而高效的用户界面一直 是这方面研究的重要课题。 第1 0 页共4 0 页 基于t n i 类信息的关联规则算法及其应用 关联规则挖掘技术现状 关联规则挖掘是数据挖掘的重要内容之一，同样面临上述问题，如何解决这些 问题同样也是关联规则挖掘研究的热点。 2 2 关联规则挖掘的现状与挑战 关联规则挖掘就是从大量的数据中挖掘出有价值的、描述数据项之间相互联系 的有关知识。随着收集和存储在数据库中的数据规模越来越大。人们对从这些数据 中挖掘相应的关联知识越来越有兴趣。 关联规则挖掘眭t a g r a w a l 等人对市场购物篮分析( m a r k e tb a s k e ta n a l y s i s ) 时首先提出“1 ，用以发现商品销售中的顾客购买模式。关联规则可以发现存于数据 库的项目( i t e m s ) 或属性( a t t r i b u t e s ) 间的有趣的关系，这些关系是预先未知的 和隐藏的，也就是说不能通过数据库的逻辑操作( 例如表的连接) 或统计的方法得 出。这说明他们不是基于数据库本身的固有属性( 如函数依赖关系) ，而是基于数 据库中数据项目的同时出现的特征，所发现的关联规则可以辅助人们进行市场运作 ( m a r k e t i n g ) ，决策支持( d e c i s i o ns u p p o r t ) ，及商业管理( b u s i n e s sm a n a g e m e n t ) 和网站设计( w e bs i t ed e s i g n ) 等等。 目前关联规则挖掘问题己经引起了数据库、人工智能、统计学、信息检索、可 视化及信息科学诸多领域的广大学者及研究机构的格外重视，并取得不少的研究成 果。由于关联规则形式简洁、易于解释和理解并可以有效捕捉数据间的重要关系， 因此从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘领域的一个热 点。 2 2 1 关联规则挖掘定义与示例 一、关联规则的基本概念和问题描述 设，= 记，i 2 ，i ，i 是由女个不i 司项目组成的集合，其中的元素称为项( it e m ) 记d 为交易( t r a n s a c t i o n ) 的集合，这里交易7 1 是项的集合，并且t c ，。对应 每一个交易有唯一的标识，如交易号，记作1 、i d 。设是一个，中项的集合如果 x c t ，那么称交易r 包含x 一个关联规则是形如x jy 的蕴涵式，这里x c ，。y c ，并且x n y = 巾。 称为规则的前提，r 称为规则的结果。 为了进一步说明关联规则的支持率和正确程度，人们引入了支持度和置信度两 第1 i 页共4 0 页 基于丌i 类信息的关联规则算法及其应用关联规则挖掘技术现状 个概念。 定义2 1 ： 规则x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的 交易数与所有交易数之比，记为s u p p o r f ( xj y ) ，即 ，l，一，、ip：xuyr，tdisu p p 州引卜百主高矛 定义2 2 ： 规则x j y 在交易集中的置信度( c o n f i d e n c e ) 是指包含x 和y 的交易数与 包含x 的交易数之比，记为c o n f i d e n c e ( xjy 1 ，即 c o n f i d e n c e ( x ；y ) = 警帮 定义2 3 ： 事务数据库上的关联规则x j y 的支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 同时满足最小支持度阈值( m i n s u p ) 和最小置信度阈值( m i n c o n f ) 时，称关联规则 x jy 为强关联规则。 例2 1 ：以下是一个关联规则的例予 a g e ( t ，“2 0 3 9 ”) a n dr o l e ( t ，“学生”) jp r o d u c t ( t ，“m p 3 播放器”) 。 此处r 是表示事务记录的变量，它对应了某个用户的一次购买行为这种情况 下，数据库中的项目是用户购买的商品，每一条记录则表示了一个用户购买的所有 商品的集合。该规则的含义是，如果某位顾客( t ) 年龄在2 0 一3 9 岁之间，而且是一 个学牛。则很可能购买m p 3 播放器。 通常为了表示方便，关联规则中都省略r ，上例将如下表示： a g e ( t ，“2 0 3 9 ”) a n dr o l e ( t ，“学牛”) jp r o d u cl ( t ，“p 3 播放器”) 给定一个交易集d ，挖掘关联规则问题就是产牛支持度和置信度分别大于用户 给定的最小支持度( m i n s u p ) 和最小置信度( m i n c o n f ) 的关联规则。每条关联规则 可以由一个蕴含式、两个阙值唯一的表示。 关联规则的支持度反映了规则在数据库中出现的频度，在而它的可信度反映以 整个规则的正确程度。一个关联规则必须具有足够大的支持度及可信度。只有满足 规则的支持度和可信度大于给定的最小支持度和最小可信度时，关联规则才成立。 关联规则挖掘问题可分解为两个了问题 第1 2 页共4 0 页 基于讯类信息的关联规则算法及其应用 关联规则挖掘技术现状 1 ) 生成支持度大于给定支持度的项集。给定的支持度叫做最小支持度 ( m i n s u p ) ，生成的项集叫频繁项集( 1 a r g ei t e m s e t ) ： 2 ) 对于给定的频繁项集，从中生成关联规则。 由于发现频繁项集是整个关联规则挖掘过程中最消耗时间和计算成本的一步， 而第二个问题相对比较简单，所以目前专家学者研究的主要问题就集中在如何以最 小的计算成本和最短的计算时间来实现频繁项集的发现过程。 二、频繁项集挖掘示例说明 下面以表2 1 所给出的示例交易数据库讨论频繁项集的挖掘 表2 1 交易号( t r a n s a c t i o ni d )项集( i t e m s e t ) 1 abde 2abcde 3abce 4ab de 5bc e 6bc d 7a bde 8 bce 设定支持度为0 5 ，即要求至少有4 个以上的交易支持该项集才为频繁项集。挖 掘结果见表2 2 表2 2 频繁项集( l a r g ei t e m s e t ) 支持度( s u p p o r t ) a 0 6 2 5 b l c0 6 2 5 d 0 6 2 5 e 0 8 7 5 a b0 6 2 5 a d o 5 a e 0 6 2 5 第1 3 页共4 0 页 基于品类信息的关联规则算法及其应用关联j ! i ! 则挖掘技术现状 b c0 6 2 5 b d0 6 2 5 b e0 8 7 5 c e0 5 d eo 5 a b d 0 5 a b e0 6 2 5 a d e0 5 b c eo 5 b d eo 5 a b d e0 5 从表2 2 e e 可以看出，挖掘出的频繁项集中绝大多数都是冗余项集从这些冗 余项集中发现的关联规则存在很大的重复性，给用户有效地理解挖掘结果带来了很 大的网难。目前，很多学者都致力于研究如何有效地发现最大频繁项集和频繁闭项 集。 2 2 2 关联规则挖掘分类与研究现状 在数据挖掘的研究领域中关联规则挖掘研究是一个非常重要的研究课题；它起 源于超级市场的购物篮问题，是指从数据库中的各项中发现有价值的关联关系。这 一问题最早是由a g r a w a l 在1 9 9 3 年首先提出。立刻就引起了数据库与机器学习领域的 专家的注意。研究成果不断涌现。从数据中发现的规则可以不仅可以应用于商业决 策、市场分析等领域，还在化学药物分析、天文学、d n a 分析等领域有着广阔的应用 前景。关联规则挖掘的一个典型的例了就是“有9 0 的顾客在购买了面包的同时也购 买了牛奶”。 一、关联规则挖掘的分类 关联规则挖掘研究根据处理的数据集的性质和挖掘结果的不同有不同的分类 方式”1 ： ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型关联规则和数 值型关联规则0 1 。 布尔型关联规则处理的变量的取值都是离散的、种类化的，它显示了这些变量 第1 4 页共4 0 页 基于品类信息的关联规则算法及其应用 关联规则挖掘技术现状 之间存在的相互依存的关系；例如关联规则：购买面包j 购买牛奶( 支持度为2 0 ， 可信度为6 0 ) 就是一个典型的布尔型关联规则。面包和牛奶只是超市中商品的一个 分类名称。 而现实中数据库中存储的数据不全是布尔型的变量，绝大多数数据是连续型的 数值( 如工资、年龄、商品价格) 。数值型关联规则处理的变量的取值就是连续的， 数值化的。例如一条关联规则：性别= “女”j 平均收入= “2 3 0 0 ”，涉及的收 入是数值类型，所以是一个数值型关联规则。对于数值型关联规则挖掘最主要考虑 的问题是如何把连续的数值属性在值域上进行划分，将每一个划分的区间映射到布 尔属性的取值。对于一个数值属性来讲如果在值域上划分的区间过多的话，每一个 区间的支持度就会很小，导致包含该属性的关联规则由于不能满足支持度要求而不 能被发现。而区间划分过大时，一些有价值的规则又由于不能满足可信度的要求而 无法发现。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则”。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的 层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机j s o n y 打印机，是一个细节数据上的单层关联规则；台式机 j s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维关联规则和多 维关联规则“1 。 在单维关联规则挖掘中，我们只涉及到数据的一个维，如用户购买的物品：而 在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规 则是处理单个属性中的一些关系。 而多维关联规则挖掘是处理数据中各个属性之间的某些关系。例如：性别= “女”j 职业= “秘节”，这条规则就涉及到两个字段的信息，是两个维上的 条关联规则。 二、关联规则挖掘的研究现状 ( 一) 频繁项集挖掘算法 传统的关联规则挖掘算法丰要的问题是处理的数据集非常庞大，所以目前的研 究丰要集中在如何有效地提高算法的效率。在关联规则挖掘过程中如何发现频繁项 集是整个挖掘过程的核心。目前的频繁项集发现算法可以分为以下2 类： ( 1 ) 完全频繁项集挖掘算法 第1 5 页共4 0 页 基- j ：品类信息的关联规则算法及其应用关联规则挖掘技术现状 这一类算法的代表是a g r a w a l 在1 9 9 4 年提出的a p r i o r i 算法，该算法利用宽度 优先，向下关闭的策略，通过多次扫描数据库，计算项集的支持度来发现所有的频 繁项集。每一次新的候选集由上一次扫描数据库生成的频繁项集通过j o i n 操作生成， 然后利用“任何一个频繁项集的子集都是频繁项集，任何一个非频繁项集的超集都 是非频繁项集”这一定理对候选集进行过滤，去掉那些包含非频繁子集的候选集， 最后扫描次数据库计算候选集的支持度确定频繁项集。反复执行生成候选集、扫 描数据库计算频繁项集这一过程直到发现所有的频繁项集。 基于a p r i o r i 算法又出现了许多衍生算法。p a t t i t i o n 算法”1 先将交易数据库分 割成若干个互不重叠的予数据库，分别进行频繁项集挖掘：最后将所有的局部频繁项 集合并作为整个交易库的候选项集。扫描一遍原始数据库计算候选集的支持度。算 法牛成整个交易数据库的频繁项集只需要扫描数据库两次。d r i p 算法0 1 通过使用h a s h 技术，可以在生成候选集时过滤掉更多的项集。所以每一次生成的候选集都更加逼 近频繁集。这种技术对于2 项候选集的剪枝尤其有效。另一方面d h p 技术还可以有效 地削减每一次扫描数据库的规模。抽样( s a m p l e ) 算法是从整个数据库中随机选择 个样本来代替整个数据库进行频繁项集的挖掘，然后扫描剩余的数据计算这些频 繁项集在其余数据中的支持度，最终生成整个数据库的绝大多数频繁项集。一般情 况下在样本数据库中使用个较低的支持度阈值，这样可以保证基于样本数据库牛 成的频繁项集是整个数据库频繁项集的超集。d i c 算法“将候选集的牛成与候选集的 计数集成到了一起。这样每一次扫描都有不同的项集进行计数操作，大大减少了扫 描数据库的次数。 2 0 0 0 年以后，在关联规则挖掘领域出现了一些新的算法，不再是经过多次扫描 数据库来发现频繁项集，而是将原始数据库或其重要信息压缩在一个新的数据结构 l 】基于新的数据结构进行挖掘。r a w e ih a r t 提出了一个叫做f p - g r o w t h 的算法i 。 它的綦本思路是通过两次扫描数据库将原始交易数据库中的频繁项集的信息压缩在 一个称为频繁模式树f p t r e e 的数据结构中。然后基于f p t r e e 牛成所有的频繁项集。 该算法只需扫描二次数据库，而且牛成的f p - t r e e 的规模远远小于原始数据库，所以 算法效率较多次扫描数据库的方法高。类似的算法还有t r e ep r o j e c t i o n 算法： ( 2 ) 频繁项集的更新挖掘算法 a g r a w a l 等的算法能有效地挖掘出静态事务数据库中的关联规则，然而，在现 实世界事务数据库中，数据是随时间的变化而变化的。交易行为的模式很可能随时 间呈现出某种发展趋势，同时我们设定的最早支持度也会随需求不同而有所变化。 这样使得当前已发现的关联规则可能不再牛效，而可能存在新的有效关联规则待于 第1 6 页共4 0 页 基 ：品类信息的关联规则算法及其应用 关联规则挖掘技术现状 进一步去发现。因此，需要设计高效的算法来更新、维护和管理已挖掘出来的频繁 项集或关联规则。频繁项集的更新挖掘包括两个方面，一是频繁项集的增量更新， 即由于新的数据的产生，使得原有的频繁项集可能不再频繁，而原来不频繁的项集 可能变得频繁。d a y i d c h e u n g 提出t f u p 和f u p 2 算法1 ，算法利用已经挖掘出的频 繁项集对更新后的数据库的频繁候选项集进行剪枝，有效地减少了候选项集的规模。 但算法仍延用了a p r i o r i 算法的思路。朱玉全等提出了基于频繁模式树的关联规则增 量式更新算法”“。 ( 二) 序列关联规则挖掘 传统的关联规则挖掘过程发现的是交易内的频繁模式，而序列关联规则挖掘过 程发现的是交易间的频繁模式，即发现在一定期间内频繁发牛的一系列交易。一个 典型的序列关联规则是凡是租了星球大战影碟的顾客在一个月之内又租了星际前 传。又比如一个网站的w e b 访问数据库，保存着用户访问网站中感兴趣网页的顺序， 序列模式挖掘可以发现其中访问频率较高的网页的顺序，可以用来指导网站结构优 化建立符合用户个性化需要的网页链接顺序。代表性的序列模式挖掘算法是 a p r i o r i a i i “”，具体三个步骤组成：一是发现所有的频繁项集，二是转换数据库使 得每一个交易由包含在其中的所有的频繁项集的集合替代，最后从中发现所有的频 繁项集。此外，g s p 算法“”也用于挖掘序列关联规则。第一次扫描数据库发现所