（计算机应用技术专业论文）基于个性发现的兴趣度研究.pdf

长存工业大学硕士学位论文 摘要 数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐 含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程。数据挖掘提取 的知识可以表示为概念、规律、模式、约束、可视化。数据挖掘的任务是从数据中发 现模式。通过对模式的分析及处理，可以得到人们感兴趣的知识。 关联规则的挖掘是数据挖掘中的一个重要部分，通过挖掘关联规则可以获得数据 间隐藏的联系，这种联系往往是人们感兴趣的。现有的关联规则挖掘基本上分为两步： 首先找出大于支持度闽值的项集，然后根据项集产生强关联规则。分析现有的关联规 则挖掘算法中所存在的问题：首先是关联规则在其表达形式上没有考虑各种可能的反 面示例的影响，因而导致知识表达功能的不够完善；其次是有可能一条规则即使可信 度和支持度都很高，仍没有实际意义，甚至是误导性的。因此，人们又引进了兴趣度 做为第三个阈值，并对兴趣度的定义和使用进行了广泛、深入的研究。 本文在介绍了数据挖掘和关联规则的概念及其相关知识，详细介绍了关联规则挖 掘的经典算法a p r i o r i 算法的基础上，首先给出了基于个体的个性化形式表示方法， 利用个性化形式表示方法可以对个体进行形式化表示，本文将该个体表示与信息论中 的信息表示联系起来，使关联规则的支持度具有了基于个体的个性特点，这样利用该 表示方法对个体进行关联规则挖掘，就会使所得到的规则更具有个体的个性化特点， 更具有实际价值；其次，本文给出了基于信息差异的兴趣度，该兴趣度的定义考虑了 事件及其对立事件产生的信息量差异，并利用信息化表示将规则的信息量差异表示出 来，利用这种信息的差异量确定了兴趣度，并使用该兴趣度作为关联规则的闽值之一， 其中，该兴趣度考虑到挖掘环境的影响，还分成了无条件和有条件两种情况，本文分 别给出了无条件的基于信息差异的兴趣度和有条件的基于信息差异的兴趣度两种情 况的兴趣度定义，并且给出了不同的性质和定理，使得该兴趣度使用起来更加灵活， 应用范围更加广泛；最后，本文利用基于信息差异的兴趣度给出了一种关联规则挖掘 算法，并对该算法进行了验证，效果良好。 关键字：数据挖掘：关联规则；个性化；兴趣度 长春工业丈学硕j = 学位论文 a b s t r a c t d a t am i n i n gr e f e r st oe x t r a c t i n gc o n n o t a t i v ea n du s e f u li n f o r m a t i o na n d k n o w l e d g ef r o ml a r g ea m o u n t so fd a t aw h i c hi si n c o m p l e t e ，n o i s e ，b l u r r ya n d r a n d o m k n o w l e d g ew h i c he x t r a c tt h r o u g hd a t am i n i n gc a ne x p r e s sc o n c e p t ，r u l e s ， p a t t e r n s ，r e s t r i c t i o n ，v i s i b l e d a t am i n i n gt a s ki sd i s c o v e r i n gp a t t e r nf r o m d a t a b ya n a l y s i sa n dd e a lw i t hp a t t e r n sc a ng e tk n o w l e d g ew h i c hp e o p l e i n t e r e s t i n g a s s o c i a t i o nr u l e sm i n i n ga r eo n eo ft h em o s ti m p o r t a n ta s p e c to fd a t a m i n i n g ，t h r o u g hm i n i n ga s s o c i a t i o nr u l e sc a ng e tr e l a t i o n sb e t w e e nd a t a ， p e o p l ea l w a y si n t e r e s t i n gt h e s er e l a t i o n s a s s o c i a t i o nr u l em i n i n gc a nb e v i e w e da sat w o s t e pp r o c e s s ：f i r s t l y ，f i n di t e m s e t sm o r et h a ns u p p o r t t h r e s h o l d ，a n dt h e ng e n e r a t es t r o n ga s s o c i a t i o nr u l e sa c c o r d i n gi t e m s e t a n a l y s i sp r o b l e m se x i s ti na s s o c i a t i o nr u l em i n i n ga r i t h m e t i c ：a tf i r s t ， a s s o c i a t i o nr u l ec a nn o tc o n s i d e ri n f l u e n c eo fv a r i o u so fp o s s i b l ei n v e r s e e x a m p l e s ，t h e nr e s u l ti nk n o w l e d g ee x p r e s s i o nf u n c t i o n sa r ei n c o m p l e t e ：t h e n a l t h o u g har u l e sc o n f i d e n c ea n ds u p p o r ta r eb o t hh i g h ，n oa c t u a lm e a n i n g ， e v e nm i s g u i d e t h u s ，p e o p l ei m p o r ti n t e r e s t i n g n e s sa st h et h i r dt h r e s h o l d ， m o r e o v e r ， r e s e a r c hi n t ot h ed e f i n i t i o na n du s eo fi n t e r e s t i n g n e s sd e e p l y t h i sp a p e ri n t r o d u c et h e c o n c e p ta n dk n o w l e d g eo fd a t am i n i n ga n d a s s o c i a t i o nr u l e ，a n di n t r o d u c ea p r i o r io fa s s o c i a t i o nr u l ei nd e t a i l 。 f i r s t l y 。t h i sp a p e rb r i n gf o r w a r de x p r e s s i o nm e t h o db a s e do ni n d i v i d u a t i o nf o r m o f i n d i v i d u a l ，a n du s i n gi n d i v i d u a t i o nf o r me x p r e s s i o nm e t h o dc a ne x p r e s s f o r m a l i z a t i o nt ot h ei n d i v i d u a l ，a n dc o n t a c ti n d i v i d u a le x p r e s s i o na n d i n f o r m a t i o n e x p r e s s i o n m a k et h es u p p o r to fa s s o c i a t i o nr u l eb a s e do n i n d i v i d u a l i t yo fi n d i v i d u a l ，t h e nd oa s s o c i a t i o nr u l em i n i n gt ot h ei n d i v i d u a l ， c a nm a k et h er u l em o r ei n d i v i d u a l i t ya n dm o r ev a l u a b l e ：s e c o n d l y ，t h i sp a p e r p r e s e n t si n f o r m a t i o no nt h ed i f f e r e n c ei ni n t e r e s t i n g n e s s ，t h ei 力t e r e s t i n g n e s s d e f i n i t i o nc o n s i d e rt h ed i f f e r e n c eo fi n f o r m a t i o nw h i c he v e n ta n do p p o s i t e g e n e r a t e ，a n dm a k eu s eo fi n f o r m a t i o ne x p r e s st h ed i f f e r e n c eo fi n f o r m a t i o n o fr u l e ， m o r e o v e r ， m a k es u r ei n t e r e s t i n g n e s s ，a n dm a k et h ei n t e r e s t i n g n e s s a so n eo ft h ea s s o c i a t i o nr u l et h r e s h o l d ，t h ei n t e r e s t i n g n e s sc o n s i d e ro ft h e i n f l u e n c eo fm i n i n ge n v i r o n m e n t ，d i v i d ei n t ou n c o n d i t i o n a la n dc o n d i t i o n a l ， a n dp r e s e n tt h ed i f f e r e n te x p r e s s i o nf o r ma n dp r o p e r t yt h e o r e m ，m a k et h e i n t e r e s t i n g n e s s m o r e a g i l i t y a n dt h e a p p l i c a t i o ns c o p e m o r e a b r o a d ：f i n a l l y ，t h i sp a p e rb r i n gam i n i n ga s s o c i a t i o nr u l e sa l g o r i t h mu s i n g t h ei n f o r m a t i o no f ft h ed i f f e r e n c ei ni n t e r e s t i n g n e s sa n dt e s tt h ea l g o r i t h m - k e y w o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e s ；i n d i v i d u a l i t y ：i n t e r e s t n e s s l i 长春工业大学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体己经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 论文作者签名： 4 4 差期 日期：础7 年了月岁e t 长春工业大学硕l ：学位论文 第一章绪论 1 1 引言 随着计算机的广泛使用和网络技术的发展，特别是因特网的应用和普及，使得电 子化信息越来越多。庞大的信息积累在给我们带来方便的同时，也使得我们面临着信 息海量和知识贫乏的矛盾。如何管理网络上庞大的信息，并且从来自异构数据源的大 量文本资源中提取出精练简洁的知识，以满足用户不断增长的个性化的信息需求，是 现在数据挖掘技术的一个热门话题。， 用户使用网络资源的行为会反映出用户的偏好及网站的性能、导航模式、服务模 式等。通过对w e b 使用记录的挖掘能够抽取这些有用的模式，向用户做出个性化的推 荐等服务。个性化服务技术已经成为当前信息服务领域的研究热点之一。所谓个性化 服务就是指对不同的用户采取不同的服务策略，提供不同的服务内容“1 。其关键在于必 须知道用户的兴趣，并准确地建立用户兴趣模型。1 。用户兴趣模型能否准确地反映用户 的兴趣决定了系统提供个性化服务的质量。区别于一般信息服务，“个性化”服务在 方法论、检索目的以及评价方法上有明显不同。服务的个性化是基于数据挖掘过程中 发现的隐含的、未知的、有用的知识来实现的。它通过收集和分析记录中的用户信息 来学习和发现用户的兴趣和行为，主动为用户提供不同的适合用户需求的有针对性的 个性化推荐方案，从而能够极大的方便用户。 使用数据挖掘技术可采掘出关联规则，所谓关联规则是指在数据库中具有这种形 式的规则：由于某些事件的发生而引起另外一些事件的发生。它在决策支持系统、专 家系统和智能信息系统等各个方面起着重要的作用，并且，随着数据库应用的普及， 数据采掘的应用范围越来越广，在近几年内倍受人们关注叫。关联规则通常使用置信 度和支持度做为阂值，例如经典的h p r i o r j 算法和d h p 算法“1 。而在实际应用中仅考 虑置信度和支持度是不够的，并且还可能引起误导，于是，人们又引入关联规则的第 三个阈值兴趣度”1 ，来修剪一些无用的，甚至是错误的关联规则，使得我们利用 挖掘技术得来的关联规则更加有意义，更加准确，能够更好的向用户做出“个性化” 的推荐等服务。如何使用兴趣度更加有效地去除无用的关联规则成为现在一个热门的 话题。 1 2 研究的目的 数据挖掘系统中支持度和黄信度是产生强关联规则的评价标准，但是这种方法有 它的局限性。如果把支持度的阈值设的足够低，可以避免不丢失任何有意义的规则， 却有可能产生大量对客户不具有实际应用价值的规则，从而造成计算效率低下的后 果：如果把闽值设的过高，却有可能丢失对客户有应用价值的规则。因此，人们引入 长春工业人学硕上学位论文 了另一评价阈值兴趣度，用来修剪无用的规则。 兴趣度是表征客户对规则的关注程度的度量，这种度量是客户对挖掘出的知识的 新颖性、可用性和可理解性的综合考虑。而实际上客户对规则的兴趣度包括主观兴趣 度和客观兴趣度旧，传统的兴趣度度量方法没有考虑主观因素的影响，即没有考虑客 户个人偏好的影响，本文希望通过利用个性发现技术，对规则的兴趣度进行度量，使 所得规则更符合客户的个人偏好。 1 - 3 论文所作的主要工作 1 ) 本文在信息论的信息量化基础上定义了基于个体的个性化形式表示，该表示 用来实现个体对于事件集内事件的发生概率，从而反映个体在事件集中的偏好。并且， 通过信息论中对信息的量化，将个性化表示形式与项集中项的支持度联系了起来。 2 ) 本文提出了基于信息差异的兴趣度，通过对事件及其对立事件所产生的信息 量差异反映数据的偏好程度。使用该兴趣度还提出了一种关联规则挖掘算法，并利用 某银行数据库对该兴趣度和算法进行了测试。 长存工业大学硕士学位论文 第二章相关知识综述 2 1 概述 关联规则是当前数据采掘研究的主要领域之一，它用于确定数据集中不同领域或 属性之间的联系，找出可信的、有价值的多个领域之间的依赖关系，自从a g r a w a l 等 于1 9 9 3 年首先提出了采掘顾客交易数据库中项集间的关联规则问题。诸多的研究人 员对关联规则的采掘问题进行了大量的研究。 自关联规则的采掘问题被提出后，就不断有人指出关联规则的局限性，为了避免 生成“错觉”的关联规则，人们引入支持度和置信度作为关联规则的阙值，通过对置 信度和支持度度量，过滤出有意义，有价值的关联规则。 由于置信度和支持度本身的局限，使得经过置信度和支持度过滤产生的规则集中 还是有客户不感兴趣的规则，于是人们又引入了兴趣度做为第三个阈值，对规则集进 行再次过滤。 本章将介绍本文所涉及到的相关知识内容。 2 2 数据挖掘 2 2 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。 这个定义包括几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用 户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆 准的知识，仅支持特定的发现问题叫。 2 2 2 数据挖掘的目的 1 挖掘出数据中隐藏的模式，趋势，关系的过程 2 通过自动或半自动的方式在海量数据中发现有用的模式，规则的过程 3 分析普通的数据( 通常是海量的) 来发现数据之间比较稳定地关系，以易于 理解的方式将数据总结出来向数据所有者提供有价值的决策支持。 4 在不需要人或很少地手工干预下通过可行地计算机技术来挖掘开采数据，对 数据进行分析 5 从大量的数据库中抽取出此前还没发现的有效实用的信息，并且此后使用此 信息来帮助制定关键的商业决策的过程 长春工业人学硕i ：学位论文 2 2 3 数据挖掘的过程 过程中各步骤的大体内容如下： 1 确定业务对象： 清晰地定义出业务问题。认清数据挖掘的目的是数据挖掘的重要一步挖掘 的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据 挖掘则带有盲目性，是不会成功的 2 数据准备： 1 ) 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据 挖掘应用的数据 2 ) 数据的预处理 研究数据的质量，为进一步的分析作准备并确定将要进行的挖掘操作的类 型 3 ) 数据的转换 将数据转换成一个分析模型这个分析模型是针对挖掘算法建立的建立一 个真正适合挖掘算法的分析模型是数据挖掘成功的关键 3 数据挖掘： 对所得到的经过转换的数据进行挖掘除了完善从选择合适的挖掘算法外， 其余一切工作都能自动地完成 4 结果分析： 解释并评估结果其使用的分析方法一般应作数据挖掘操作而定，通常会用 到可视化技术 5 知识的同化： 将分析所得到的知识集成到业务信息系统的组织结构中去 2 3 关联规则 2 3 1 关联规则的概念 购物篮分析一引发关联规则挖掘的例子 问题：“什么商品顾客多半会在一次购物中同时购买? ” 购物篮分析：设全域为商店出售的商品的集合( 即项目全集) ，一次购物购买( 即 事务) 的商品为项目全集的子集，若每种商品用一个布尔变量表示该商品的有无，则 每个购物篮可用一个布尔向量表示。通过对布尔向量的分析，得到反映商品频繁关联 或同时购买的购买模式。这些模式可用关联规则描述。 例：购买计算机与购买财务管理软件的关联规则可表示为： 4 长春工业人学硕l 学位论文 c o m p u t e rjf i n a n c i a l _ m a n a g e m e n t s o f t w a r s u p p o r t = 2 ，c o n f i d e n c e = 6 0 一 s u p p o r t 为支持度，c o n f i d e n c e 为置信度。 该规则表示：在所分析的全部事务中，有2 的事务同时购买计算机和财务管理 软件；在购买计算机的顾客中6 0 也购买财务管理软件。 1 、关联规则 关联( a s s o c i a t i o n s ) 分析的目的是为了挖掘隐藏在数据间的相互关系，即对于 给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相 关性。项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切 程度或关系。 定义i 令i = i 1 ，i 2 ，i n ) 是项目集，d 是全体事务的集合。事务t 是i 上的 一个子集，集合t _ i ，每个事务用唯一的标志t i d 来标识。关联规则是形如x = “的 蕴含式，其中x c _ i ，y c i 且x n y = f 弓，x 称为规则的条件，y 称为规则的结果9 1 。 2 、置信度和支持度 定义2 关联规则x j y 对事物集d 的支持度( s u p p o r t ) 定义为d 中包含有事务x 和y 的百分比。关联规则x = “对事务集合d 的置信度( c o n f i d e n c e ) 定义为d 中包 含有x 的事务数与同时包含y 的百分比。即： s u p p o r t ( x ；y ) = ( 包含x 和y 的事务数事务总数) x 1 0 0 c o n f i d e n c e ( x j y ) = ( 包含x 和y 的事务数包含x 的事务数) 1 0 0 定义3 置信度和支持度均大于给定阈值( 即最小置信度阈值和最小支持度阈值) 。 即： s u p p o r t ( x ；y ) = m i n s u p c o n f i d e n c e ( x j y ) = m i n _ c o n f 的关联规则称为强规则；否则称为弱规则。 数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解 某些数据之间的关联程度。 强规则x j y 对应的项集( x u y ) 必定是频繁集。因此，可以把关联规则挖掘划 分为以下两个子问题： ( 1 ) 、根据最小支持度找出事务集d 中的所有频繁项集。一一核心 ( 2 ) 、根据频繁项集和最小置信度产生关联规则。一一较易 3 、关联规则挖掘 关联规则挖掘：给定一组i t e m 和记录集合，挖掘出i t e m 间的相关性，使其置信 度和支持度分别大于用户给定的最小置信度和、最小支持度。 2 3 2 关联规则挖掘的过程 1 、术语 长春工业大学硕上学位论文 关联规则挖掘即给定一组i t e m 和记录集合，挖掘出i t e m 间的相关性，使其置信 度和支持度分别大于用户给定的最小置信度和最小支持度。 定义4 在关联规则挖掘算法中，把项目的集合称为项集( i t e m s e t ) ，包含有k 个 项目的项集称为k 一项集。包含项集的事务数称为项集的出现频率，简称为项集的频率 或支持度计数。如果项集的出现频率大于或等于最小支持度s 与d 中事务总数的乘积， 则称该项集满足最小支持度s 。如果项集满足最小支持度，则称该项集为频繁项集 ( f r e q u e n ti t e m s e t ) 。 一 2 、关联规则的挖掘过程 关联规则的挖掘主要被分解为下面两步： 第l 步：找出所有的频繁项集，即找出支持度大于或等于给定的最小支持度阈值 的所有项集。可以从1 到k 递归查找k 一频繁项集。 第2 步：由频繁项集产生强关联规则，即找出满足最小支持度和最小置信度的关 联规则。对给定的l ，如果其非空子集a c l ，s u p ( l ) 为l 的支持度，s u p ( a ) 为a 的支 持度，则产生形式为a j l _ a 的规则。 3 、频繁项集的性质 a p r i o r i 性质：频繁项集的所有非空子集都必须是频繁的。 a p r i o r i 性质基于如下事实：根据定义，如果项集i 不满足最小支持度阈值 m i n s u p ，则i 不是频繁的，即s u p ( i ) r a i n _ s u p 。如果将项a 添加到i ， 则结果 项集( 即i u a ) 不可能比i 更频繁出现。因此，i u a 也不是频繁的，即s u p ( i u a ) m i n s u p 。 频繁项集的a p r i o r i 性质用于压缩搜索空间( 剪枝) ，以提高逐层产生频繁项集 的效率。 2 3 3 关联规则挖掘的典型算法一a p r i o r i 算法 1 、a p r i o r i 算法的基本思想 a p r i o r i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。它使用一种 称作逐层搜索的迭代算法，k 一项集用于探索( k + 1 ) 一项集“”。 a p r i o r i 算法的基本思想是： a 、首先，通过扫描数据集，产生一个大的候选数据项集，并计算每个候选数据项 发生的次数，然后基于预先给定的最小支持度生成频繁卜项集的集合，该集合记作厶； b 、然后基于厶和数据集中的数据，产生频繁2 一项集厶； c 、用同样的方法，直到生成频繁n 一项集工。，其中己不再可能生成满足最小支持 度的( n + i ) 一项集。 d 、最后，从大数据项集中导出规则。 2 a p r i o r i 算法的执行过程 6 长存t 业大学硕1 二学位论文 1 ) a p r i o r i 算法的关键步骤： a p r i o r i 算法中的关键步骤是由l 。找h ，该步骤可分为两步： 第l 步( 连接) ：为找l k ，通过l 。与自己连接产生候选k 项集的集合。将该候 选项集的集合记作g 。设1 和1 ：是l “中的项集，记号1 。 j 表示1 的第j 项。执行 连接l 。和l 。，其中l 。的元素是可连接，如果它们前( k - 2 ) 个项相同而且第( k 一2 ) 项不同( 为简单计，设1 k 一1 l ： k 一1 ) ，即： 1 ，【1 = 12 1 1 。 2 = l ： 2 八a 1 k - 2 = 1 ： k - 2 八l l k 一1 i ，表明差异越大，规则是新奇的，客户对此规则 越感兴趣。若i z 的绝对值 1 时，说明客户对这条规 则越感兴趣( 其实际利用价值越大) ：当i 。 1 时，说明对这条规则的反面规则越感兴 趣( 其反面规则的实际利用价值越大) 。但该方法不能反映左项与右项的主从关系“”。 3 基于信息量的兴趣度 综合考虑了规则左项x 和右项y 的概率分布的相似程度的兴趣度计算公式为： i 一= p ( x ) p ( y x ) l o g p ( y x ) p ( y ) + ( 1 一p ( y x ) l o g ( 1 一p ( y x ) ) ( 1 一p ( y ) ) 式中p ( x ) 是规则左项x 的简洁性的度量，属性数目越少，规则越简洁，客户感兴趣 度越高。考虑了规则的左项和右项的耦合程度。这种方法忽略了这样的事实：紧密耦 合的事件之间的关系通常是明显的和己知的“。 4 基于综合的兴趣度 对于规则，x y ，s ( y ) 越大，对导致y 的原因可能知道得越多：s ( x ) 越大，规则 越简洁。兴趣度计算公式为： i 。= 1 一s ( y ) ( 1 一s ( x ) ) ( 1 一s ( xuy ) ) i 。值越大，规则越新奇，客户可能对规则的兴趣越高，考虑到了规则的左项x 和右项y 的耦合，相比其它三种模型增大了函数的粒度1 。 2 5 2 主观兴趣度与客观兴趣度 实际上客户对规则的兴趣度包括主观兴趣度和客观兴趣度”。 客观兴趣度主要根据模式或规则的形式和数据库中的数据进行定义，属于数据 驱动；主观兴趣度还要考虑用户的参与等人为因素的影响，属于用户驱动。要综合使 用客观兴趣度和主观兴趣度这两种度量标准，比较合理的方法是首先用客观兴趣度作 为第一级过滤器，选出潜在感兴趣的模式，然后再用主观兴趣度来对它们进行第二级 筛选，得到用户真正感兴趣的知识。 客观度量是度量模式本身的特点，即根据模式的结构和统计特性来确定模式的 兴趣度；主观度量是度量用户对结构的偏好程度，即根据用户对最终结构的确信和偏 好程度来确定模式的兴趣度。挖掘出的关联规则的兴趣度不仅与数据本身有直接联 系，而且与实际的应用环境、用户个人职业特点、个人爱好等有这重要的联系。2 5 1 中介绍的，均为客观兴趣度的模型。 长春工业大学硕l 学位论文 第三章关联规则挖掘与兴趣度 自关联规则的采掘问题被提出后，就不断有人指出关联规则的局限性，为了避免 生成“错觉”的关联规则，人们引入了各种闽值以加强对关联规则的评判。现有的关 联规则采掘算法主要是考虑两个称作可信度和支持度的阈值，但是，我们发现在实际 应用中仅考虑可信度和支持度是不够的，并且还可能引起误导，于是又引入了兴趣度 作为第三个阈值。 本章将深入介绍关联规则的表示及兴趣度的关联规则挖掘。 3 1 关联规则的形式表示 我们以交易类型的数据库为例子来形式化地描述关联规则“。 设i = i 1 ，i 2 ，i m ) 为项集，表示各种商品的集合，d ：( t l ，t 2 ，t n ) 为交易 集，表示每笔交易的集合，其中t i i ( 1 i n ) 。 关联规则是形如式( 1 ) 的蕴含式 p 1 p 2 p n q 1 q 2 q m( 1 ) 其中， p 1 ，p 2 ，p n ci ， q 1 ，q 2 ，q m ) ci ，f p l ，p 2 ，p n n ( q l ，q 2 ，q m ) = o 。 为了进一步说明关联规则的正确程度和支持率，人们引入了可信度和支持度两个概 念。设每个规则蕴含式的左部 p 1 ，p 2 ，p h i 定义的项集为b ，右部 q 1 ，q 2 ，q m ) 定义的项集为h ，它们都是原始项集i 的子集。令g = h u b ，表示同时支持h 和b 的 项集，定义规则的可信度c = i g i 1 b l ，支持度s = i g i 1 d 1 。 从语义的角度来分析，规则的可信度表示这条规则的正确程度；支持度表示用这 条规则可以推出百分之几的目标，即这一原因对于这一结果的重要程度，一般地，用 户可以定义两个阈值，要求数据裁决系统所生成的规则的支持度和可信度都不小于给 定的阈值。 这样，我们就用一个蕴含式，两个闽值唯一标识了每一个采掘出来的关联规则。 3 2 关联规则定义的修改 上面所定义的关联规则的可信度支持度阈值只描述了正项的情况，却不能够显示 否定示例的情况。例如，人们不能采掘出这样的一条关联规则表示“买了键盘的顾客 不买鼠标的可能性是2 8 ，而且在交易记录中有5 2 的记录是买了键盘而没买鼠标”。 显然，这种购买的可能性( 即买了键盘不买鼠标) 在现实生活中是很有可能存在的，但 由于上面的定义表述没有考虑否定情况，那么我们在采掘时就会遗失掉这条很有用的 信息。 下面，我们将否定示例的情况同样考虑进去，并对关联规则的定义形式进行修改， 长春工业大学硕j 二学位论文 定义关联规则是如下形式的蕴含式： p lap 2a ap l 八p q + 1 ) ap u + 2 ) ap n q 1 q 2 八q kag ( t + 1 ) g ( + 2 ) a 人q m( 2 ) 其中， p l ，p 2 ，p n ) ci ， q 1 ，q 2 ，q m 】ci ，( p 1 ，p 2 ，p n ) n q l ，q 2 ，q m ) = 0 ，且对每一条支持该规则的交易记录t ，有p i t ，q j et ，p i 叠t ，q j 匹t ( 1 i 1 ，1 + 1 i n ，1 j k ，k + 1 j m ) 。 可用下面的关联规则表示“买了键盘的顾客不会买鼠标的可能性是2 8 ，且在交易记 录中有5 2 的记录是买了键盘而没买鼠标的”： k e y b o a r d m o u s e ，c = 0 2 8 ，s = 0 5 2 这样，我们就把否定示例的情况也考虑进来，使得采掘出的规则更加全面。 3 3 兴趣度的深入研究 3 3 1 产生的问题 上面对关联规则的定义形式进行了修改，加入了对否定示例情况的考虑，但仍未 圆满地解决否定示例问题“”，下面我们来深入研究一下会产生的问题： 设在一个底层交易数据库中有n 条交易记录，这n 条记录均为购买键盘和购买鼠 标的情况。如表3 1 所示，行k 和k 分别对应购买了键盘和没有购买键盘的记录数， 列m 和聊分别对应购买了鼠标和没有购买鼠标的记录数。 表3 1 购买键盘和鼠标的统计表( ) m 肌 m k 1 552 0 j | 7 55 8 0 k 9 01 01 0 0 我们来研究一下关联规则k e y b o a r d m o u s e 。它的支持度s = 1 5 1 0 0 = 1 5 ，这个 支持度是很高的；它的可信度c = 1 5 2 0 = 7 5 。这个可信度也是很高的。当我们把可 信度和支持度阈值定为低于o 7 5 和0 1 5 时，该规则将会作为目标规则被采掘出来。 从该规则可以得出键盘的销售量增加会使得鼠标的销售量也同样增加，这样我们可以 制定促使键盘销售量增加的销售策略，同时