（计算机软件与理论专业论文）不完整数据库中的关联规则挖掘研究.pdf

不完整数据库孛的关联规刘挖掘研究 不完整数据库中的关联规则挖掘研究 计算机软件与理论 硕士生：郑利荣 指导教师：印鉴教授 摘要 数据挖掘是当前计算机学科的一个前沿研究方向，作为- - t q 应用性很强的新 兴技术，它存在很多值得研究的地方。如何合理的应用数据挖掘技术，如何针对 现实生活中的问题改进数据挖掘技术是其中的热点问题。 在大型数据库中快速找出有关的关联规则是数据挖掘技术的一项重要内容。 人们提出了很多方法，但这些方法往往假设数据是精确的，不考虑数据丢失的情 况。但是在现实生活中数据丢失的情况是很常见的，尤其是在商业数据库中，文 件错误、纪录缺失、存储策略的改变等都会引起数据丢失而造成数据库的不完整。 这种数据的不完整性会影响找寻关联规则的过程，因为在有数据缺失时对项集的 支持度以及信任度的计算得不到确定值。进一步，由于支持度以及信任度的不确 定性，还可影响到所挖掘关联规则的可靠性和可信性。因此，有必要对在不完整 数据库中的关联规则挖掘进行支持度及信任度的估算。本文正是基于这一点，把 a p r i o r i 算法应用于不完整数据库，通过引入期望支持度和期望信任度的定义， 提出了一个在不完整数据库中挖掘关联规则的算法。实验结果证明，所提出的算 法具有较好的效果。 关键诃：数据挖掘，关联规则，不完整数据库，期望支持度，期望信任度 不完整数据库中的关联规则挖掘研究 r e s e a r c ho f fm i n i n ga s s o c i a t i o nr u l e si ni n c o m p l e t e d a t a b a s e c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：z h e n gl i r o n g s u p e r v i s o r ：y i nj i a np r o f e s s o r a b s t r a c t t o d a y , d a t am i n i n gi so n eo f t h em o s tp o p u l a rt e c h n o l o g i e so fc o m p u t e rs c i e n c e a san e wt e c h n o l o g y , i th a sm a n yp r o b l e m st ob es t u d i e d h o wt ou s ei tc o r r e c t l y , h o wt om a k ea na p p l i c a t i o n ，a n dh o wt oi m p r o v ei t ，a l lt h e s ep r o b l e m sa t t r a c t c o m p u t e rs c i e n t i s t d i s c o v e r i n ga s s o c i a t i o nr u l e sa m o n gi t e m si nl a r g ed a t a b a s e si sc o n s i d e r e da so n e i m p o g a n ti s s u e i nd a t am i n i n gt e c h n o l o g y m a n yp e o p l eh a v ep r e s e n t e dal o to f m e t h o d s ，b u tt h e s em e t h o d sa l w a y ss u p p o s et h a td a t aa r ea c c u r a t e i nf a c t ，m i s s i n g d a t ao f t e no c c t l ri n r e a ll i f e ，e s p e c i a l l yi nb u s i n e s sd a t a b a s e s m a n yf a c t o r s ，s u c ha s f i l ee r r o r s ，m i s s i n gr e c o r d s ，c h a n g e si nt h ed a t a b a s es c h e m a ，w i l lg i v er i s et om i s s i n g d a t a t h i si n c o m p l e t e n e s so fd a t a b a s e sw i l la f f e c tt h ep r o c e s so fd i s c o v e r i n g a s s o c i a t i o nr u l e sb e c a u s et h es u p p o r tv a l u e sa n dc o n f i d e n c ev a l u e so fi t e m s e t sw i l lb e u n c e r t a i n f u r t h e rm o r e ，t h i su n c e r t a i n t yw i l la f f e c tt h er e l i a b i l i t ya n dc r e d i b i l i t yo f t h er u l e s s oi ti sn e c e s s a r yt of i n dar e l i a b l ea l g o r i t h mt oe v a l u a t et h es u p p o r ta n d c o n f i d e n c ev a l u eo ft h ea s s o c i a t i o nr u l e sd i s c o v e r e di ni n c o m p l e t ed a t a b a s e st oe n s u r e s o m eb a s i cp r o p e r t i e so ft h er u l e s b a s e do nt h i s ，t h et h e s i sa p p l i e st h ea p r i o r i a l g o r i t b a nt oi n c o m p l e t ed a t a b a s ea n dp r o p o s e sa na l g o r i t h mo nm i n i n ga s s o c i a t i o n r u l e si ni n c o m p l e t ed a t a b a s e d e f i n i t i o n so fe x p e c t e ds u p p o r ta n dc o n f i d e n c ev a l u e a r ea l s oi n t r o d u c e d e x p e r i m e n t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi se f f i c i e n t i t 不完整数据库中的关联 | ! i ! 则挖掘副f 究 k e yw 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 ，i n c o m p l e t ed a t a b a s e ，e x p e c t e ds u p p o r t v a l u e ，e x p e c t e dc o n f i d e n c ev a l u e l l i 不完整数据库中的关联规则挖掘研究 1 1 背景 第1 章概述 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个 数据库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将持续 发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆炸的时代，信 息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从 中及时发现有用的知识，提高信息利用率呢? 要想使数据真正成为一个公司的资 源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数 据可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥饿于 知识”的挑战，数据挖掘和知识发现( d m k d ) 技术应运而生，并得以蓬勃发展， 越来越显示出其强大的生命力。 数据挖掘一面世就以其强大的实用性得到了人们的认同。型国财富杂志5 0 0 强之一的第一数据公司( f i r s td a t ac o r p ) 就在为第一国家银行( f i r s tn a t i o n a l b a n k ) 、美国在线交易( a m e r i t r a d eh o l d i n gc o ) 、奥马哈保险公司( m u t u a lo f o m a h a c o 1 等著名的金融证券和保险公司提供数据挖掘的产品服务，这些企业在 风险控制、挖掘客户、降低成本方面的年收益数以亿计。 虽然数据挖掘技术已被广泛接受，但如何合理的应用数据挖掘技术，如何针 对现实问题改进数据挖掘技术仍然有待我们去深入研究。本文详细介绍了作者在 不完整数据库中关联规则挖掘方面的研究工作。 1 2 本文的主要工作 本文把a p r i o r i 算法应用于不完整数据库，通过引入期望支持度和期望信任 度，提出了一个挖掘不完整事务数据库中关联规则的算法。具体说来，本文的工 币完整数据库中的关联规则挖掘研究 作主要体现在： 1 对关联规则挖掘进行了分析，实现了经典的关联规则挖掘算法a p r i o r i 。 2 针对不完整数据库，通过引入期望支持度和期望信任度，提出了一个挖掘不 完整数据库中关联规则的算法i d a 。 3 在所实现的a p r i o r i 算法的基础上，对i d a 算法进行了实验，并给出了实验 结果和分析。 本文余下部分的章节组纵如下： 第二章介绍了数据挖掘的一些相关知识，包括数据挖掘的产生、应用与当 前研究现状。 第三章简要介绍了关联规则挖掘技术的相关知识。 第四章描述了所实现的关联规则挖掘经典算法a p r i o r i 。后面所提出的不完 整数掘库中关联规则挖掘算法将基于此算法。 第五章详细描述了不完整数据库中关联规则挖掘算法i d a 。首先介绍了该 算法所引入概念的一些性质，然后给出了期望支持度和期望信任度 的定义和计算方法，基于期望支持度和期望信任度，给出了挖掘不 完整事务数据库巾关联规则算法。最后，还给出了实验结果和分析。 第六章对本文工作的总结以及展望。 不完整数据库中的关联规则挖掘研究 2 1 数据挖掘背景 第2 章数据挖掘概述 随着时代的进步，人们产生和收集数据的能力迅速提高，越来越多的人加入 到数字世界中，利用计算机提供的各种工具来获得他们所感兴趣的信息。条形码 在大部分商业产品中的广泛使用，许多商务、科学和行政事务的计算机化，以及 由文本和图象扫描平台到卫星遥感系统的数据收集工具的进步，再加上作为全球 信息系统的万维网的流行，w e b 数据的急剧膨胀，已经将我们淹没在数据和信息 的汪洋大海中。数据的丰富带来了对强有力的数据分析工具的需求，传统的数据 库查询手段已经很难满足人们的需要，大量的数据被描述为“数据丰富，但信息 贫乏”。快速增长的海量数据收集、存放在大型和大量的数据库中，却由于缺乏 将这些数据转换成有价值的信息和知识的新技术和自动化工具，使得收集在大型 数据库中的数据变成了“数据坟墓”难得再访问的数据档案：人们迫切需要 一种能够对庞大的数据进行更高层次处理的技术，从中找出规律和模式，以帮助 人们更好地利用数据进行决策管理和研究，而数据挖掘技7 | 一从大量数据中用 非平凡的方法发现有用的知识的出现，引起了人们广泛的关注，导致了数据 挖掘研究的蓬勃发展。 数据挖掘通常又称为数据中知识发现，就是从存储在大型数据库、数据仓库 或其他信息存储容器中的大量的、不完全的、有噪声的、模糊的、随机的数据里 提取人们感兴趣的知识，这些知识是隐含的、事先未知的、对决策有潜在价值的 有用信息1 6 1 。还有很多近似的术语，如从数据库中发现知识( k d d ) 、数据分析、 数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的源 泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系型数据库中的数 据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异 构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的， 不完整数据库中的关联规则挖掘研究 也可以是归纳的。知识用概念、规则、模式、规律等方式来表示。发现了的知识 - _ j 以用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的 维护。 数据库中的知识发现是一个多步骤的处理过程，一般分为： ( 1 ) 问题定义：了解相关领域的有关情况，熟悉背景知识，弄清用户要求。 ( 2 ) 数据提取：根据要求从数据库中提取相关的数据。 ( 3 ) 数据预处理：主要对前一阶段产生的数据进行加工，检查数据的完整 性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补。 ( 4 ) 数据挖掘：运用选定的知识发现算法，从数据中提取出用户所需要的 知识，这些知识可以用一种特定的方式表示或使用一些常用的表示方式。 ( 5 ) 知识评估：将发现的知识以用户能了解的方式呈现，根据需要对知识 发现过程中的某些处理阶段进行优化，直到满足要求。 由此可见，数据挖掘只是数据库中知识发现的一个步骤，但又是最重要的一 步。因此，往往可以不加区别地使用k d d 和数据挖掘。一般在研究领域被称作 数据库中知识发现的，在工程领域则称之为数据挖掘。 数据挖掘是一门广义的交叉学科，涉及多学科技术的集成，包括数据库技术、 人工智能、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索、知识库系统、图象与信号处理和空问数据分析。机器学习和数据分析 的理论及实践是数据挖掘研究的基础，极大的商业应用前景又是数据挖拥研究工 作的巨大推动力。传统的数据库查询和统计、报表的处理方式都是对指定的数据 进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取，因此只能 够提供用户想要的信息，而数据挖掘技术则可以发现用户没有意识到的未知的有 价值信息。作为一种在海量数据中发现知识的手段，与传统的数据分析( 如查洵、 报表、联机应用分析o l a p 等) 的本质区别在于数据挖掘是在没有明确假设的前 提下去挖掘信息、发现知识的，它，_ 以从大型的数据库或数据仓库中提出隐藏的 预测性信息，从浩如烟海的企业信息资料库中挖掘出更有价值的信息，具有广泛 的应用前景。 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性质 的知识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事物 4 不完整数据库中的关联规则挖掘研究 之间属性差别的知识；关联型知识，反映事物之间依赖或关联的知识：预测型知 识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏离常规的 异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升， 从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家 超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客 十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对于 商家开发和实施客户化的销售计划和策略是非常有用的。 数据挖掘所得到的知识应具有先前未知、有效和可实用三个特征。先前未知 是指该知识是预先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信 息或知识，甚至是违背直觉的信息或知识，挖掘得到的知识越是出乎意料，就可 能越有价值。知识的有效性要求挖掘前要对被挖掘的数据进行仔细检查，保证它 们的有效性，才能保证挖掘所得知识的有效性。最为重要的是要求所得的知识有 可实用性，即这些信息或知识对于所讨论的业务或研究领域是有效的，是有实用 价值和可实现的。常识性的结论，早已被人们或竞争对手掌握的或无法实现的事 实都是没有意义的。 数据挖掘起源于2 0 世纪8 0 年代后期，是信息技术自然演化的结果，9 0 年代有 了突飞猛进的发展。自从1 9 9 5 年第一届知识发现和数据挖掘国际会议在加拿大召 开以来，数据挖掘技术已成为机器学习、数据库系统、人工智能等领域内热门的 研究方向。随后，i e e e 、a c m 、a a a i 等国际权威机构纷纷组织专题会议，共同 讨论有关数据挖掘方面出现的问题和所取得的成果。 2 2 数据挖掘的应用与发展 2 2 1 数据挖掘的方法 近年来，数据挖掘技术引起了信息产业界的极大关注，其主要原因是存在大 量数据可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取 的信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工 程设计和科学探索等。而用于发现知识的数据挖掘分析方法包括 1 6 , 1 9 , 2 4 1 ： 5 刁i 完整数据库中的关联规则挖掘研究 1 分类( c l a s s i f i c a t i o n ) 分类反映同类事物共同性质的特征型知识以及不同事物之间的差异型特征 知识。它是这样的一个过程，首先找山描述并区分数据类或概念的模型( 或函数) ， 再使用模型预测类，标记未知的对象类。模型类的个数是确定的，预先定义好的。 一个典型的应用就是银行将信用卡申请者分类为低、中、高风险来标志申请者的 信任度，再根据信任度来给予申请者不同的优惠。 2 估值( e a i m a i i o n ) 估值与分类类似，不同之处在于，分类描述的是离散型变量的输出，而估值 处理连续值的输出：分类的类别是确定的，估值的量是不确定的。一般来说，估 值可以作为分类的前一步工作。给定一些输入数据，通过估值，得到未知的连续 变量的值，然后，根据预先设定的阈值，进行分类。例如：银行对家庭贷款业务， 运用估值，给各个客户记分。然后，根据阈值，将贷款级别分类。 3 演变分析( e v o l u t i o na n a l y s i s ) 数据演变分析也可以认为是以时间为关键属性的关联知识。是根据时间序列 型数据，描述行为随时间变化的对象的规律或趋势，然后对其建模，并由历史的 和当前的数据去推测未来的数据。分析过程可能包含时间相关数据的特征化、区 分、关联、分类和聚类，这类分析的不同特点包括时削序列数据分析、序列或周 期模式匹配和基于类似性的数据分析。演变分析在医疗上有很强的应用前景，例 如通过分析患者以往的医疗数据，可以根据患者的实际情况( 如经济水平、既往 病史、具体病情) ，使用演变分析来提前预测病人手术后的康复避度，合理安排 康复计划、用药计划等。 4 关性分组或关联规则( a f f i n i t y g r o u p i n go r a s s o c i a t i o n r u l e s ) 关联规则是当前数据挖掘研究的主要领域之一，主要作用是确定数据集中不 同领域或属性问的联系，找出可信的、有价值的多个域之问的依赖关系。这些规 则可以找出顾客购买行为模式，如在销售食品柜台发现，在购买牛奶的客户中， 有8 0 的人同时也购买了面包和饼干，用规则：牛奶j 面包+ 饼干表示。发现 这样的规贝q 可以设计方便顾客购物的商品货架、指导商家进货，对于确定市场策 略是很有价值的。关联规则还可以应用到附加邮递、仓储规划以及基于购买模式 对用户进行分类等方面。 不完整数据库中的关联规则挖掘研究 5 聚类分析( c l u s t e r i n g ) 与分类和预测不同，聚类是对记录分组，把相似的记录集中在一个聚类里， 聚类分析数据对象，而不考虑已知的类标已。聚集和分类的区别主要在于聚集不 依赖于预先定义好的类，不需要训练集。聚类分析通常作为数据挖掘的第一步。 例如，“哪一种类的促销对客户响应最好? ”，对于这一类问题，首先对整个客户 做聚类，将客户分组在各自的聚类里，然后对每个不同的聚类回答问题，可能效 果更好。 6 概念描述( c o n c e p td e s c r i p t i o n ) 概念一般是指数据的汇集。而概念描述是指机器自动由现有数据获得需要描 述的概念的定义，即根据数据的微观特性发现其表征的、带有普遍性的、较高层 次概念的、中观和宏观的知识，反映同类事物共同性质，是对数据的概括、精炼 和抽象。例如，对某一个病症，给出一些确诊病人的例子，计算机自动归纳该病 症患者的特征，然后得到一个关于患此类新病症的病人的一个通用的描述。 2 2 2 数据挖掘的研究现状 数据挖掘技术从一开始就是面向应用的。它不仅仅是面向特定数据库的简单 的检索查询或者调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、 综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已 有的数据对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新 的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。美国加州 理工学院喷气推进实验室与天文学家合作开发的s k i c a t 系统通过对几百万个 天体进行分类，已帮助天文学家发现了1 6 个新的类星体。美国n b a 篮球队的教 练，利用某公司提供的数据挖掘技术，临场决定替换队员，一度在数据库界被传 为佳话。最近，还有不少d m k d 产品用来筛选i n t e m e t 上的新闻，保护用户不 受无聊电子邮件的干扰和商业推销，受到极大的欢迎。这样一来，就把人们对数 据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。 这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这里所说的知识 7 不完整数据库中的关联规则挖掘研究 发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定 理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有 特定前提和约束条件、而向特定领域的，同时还要能够易丁二被用户理解，最好能 用自然语言表达发现结果。 目前，国外数据挖掘的发展趋势主要有 1 9 , 2 4 】：对知识发现方法的研究进一步 发展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高； 传统的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合等。在应用方 面包括：k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统， 而不是孤立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。 国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应 的研究中心进行这方面的工作。很多大公司也对数据挖掘应用的研究投入大量精 力，经过十多年的努力，关于数据挖掘技术应用的研究也取得了丰硕的成果。一 些公司已经丌发了多种数据挖掘相关的产品，据不完全统计，目前已经有了数百 个数据挖掘软件产品。如i b m 公司开发的q u e s t 和i n t e l l i o p t tm i n e r ：a n g o s s s o f t w a r e 开发的基于规则和决策树的k n o w l e d g es e e k e r ；a d v a n c e ds o f t w a r e a p p l i c a t i o n 开发的基于人工神经网络的d bp r o f i l e ：加拿大s i m o nf r a s e r 大学开 发的d bm i n e r ：s g i 公司开发的m i n es e t 等。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关 数据挖掘理论方面的研究，大量的文章已经在各级期刊，各种会议发表，应用数 据挖掘技术开发的产品日渐增多，己经有不少含数据挖掘功能的产品问世，如用 于对股票行情进行分析预测的指南针、神光、r m r 等智能股票分析系统。目前 进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划、 “九五”计划等。 一份最近的g a r t n e r 报告中列举了在今后3 5 年内对工、l 蚪苷产生重要影响的 五项关键技术，其中k d d 和人工智能排名第一。l 刊时，这份报告将并行计算机 体系结构研究和k d d 列入今后5 年内公司应该投资的1 0 个新技术领域。可以 看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视，预计在二 十一世纪还会形成更大的高潮，研究焦点可能会集中到以下几个方面：研究专门 不完整数据库中的关联规则挖掘研究 用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化： 寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理解，也便 于在知识发现过程中的人机交互；研究在网络环境下的数据挖掘技术，特别是在 i n t e m e t 上建立d m k d 服务器，与数据库服务器配合，实现数据挖掘；加强对各 种非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数据。但是无论怎 样，需求牵引与市场驱动是永恒的，d m k d 将首先满足信息时代用户的急需， 大量基于d m k d 的决策支持软件工具产品将会问世。 9 不完整数据库中的关联舰则挖掘研究 第3 章关联规则挖掘 3 1 基本概念和问题描述 关联规则挖掘最早是用于发现事务数据库中不同商品( 项) 之间的联系，这 些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。例如， 一条关联规则可能会描述“买了牛奶的顾客中有8 0 同时买了面包”。发现这样 的规则呵以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。 进而可以推广到各个领域，例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新的电话 收费和管理办法，制定既有利于公司又有利于客户的优惠政策。随着全球信息量 的飞速增长，如何从信息海洋中找出有用的信息成为科学研究的迫切议题，数据 挖掘对此提供了一个比较好的解决方法，从而成为当前计算机科学界的一大热 点。 下面，我们给出关联规则挖掘问题的形式描述。 设i = i 1 ，i2 ，i 。) 是互不相同的项( i t e m ) 的集合。记d 为事务( t r a n s a c t i o n ) t 的集合，这里事务t 是项的集合，并且t g i 。对应每一个事务有唯一的标识， 如事务号，记作t i d 。设x 是一个i 中项的集合，如果x _ c t ，那么称事务t 包 含x 。 一个项集x 在数据库d 中的支持度定义为在d 中包含x 的事务的百分比， 用s u p p o r t ( x ) 来表示，s u p p o r t ( x ) = i t ；x c _ t ，t c d i d i 一个关联规则是形如x j y 的蕴涵式，这里x c _ i ，y g i ，并且x n y = 十。规则 x j y 在事务数据库d 中的支持度( s u p p o r t ) 是事务集中包含x 和y 的事务数 与所有事务数之比，记为s u p p o r t ( x j y ) ，即 s u p p o r t ( x j y ) 2 i t ：x u y g t ，t c d ) l l d l 可以看出s u p p o r t ( x j y ) = s u p p o r t ( x u y ) 。 不完整数据库中的关联规则挖掘研究 规则x y 在事务集中的信任度( c o n f i d e n c e ) 是指包含x 和y 的事务数与 包含x 的事务数之比，记为c o n f i d e n c e ( x j y ) ，即 c o n f i d e n c e ( x j y ) = | t ：x u y _ t ，t c _ d i i t ：x t ，t e d l 可以看出c o n f i d e n c e ( x j y ) = s u p p o r t ( x w y ) s u p p o r t ( x ) 。 给定一个事务集d ，关联规则挖掘问题就是产生支持度和信任度分别不小于 用户给定的犀小支持度( m i n s u p p ) l l 最小信任度( m i n c o n f ) 的关联规则。 3 2 关联规则分类 基于不同的情况，关联规则可以分类为 1 6 1 ： 1 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字 段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值 型关联规则中也可以包含种类变量。 例如：性别= “女”j 职业= “公关”，是布尔型关联规则；性别= “女”j a v g ( 收入) = “4 0 0 0 ”，涉及的收入是数值类型，所以是一个数值型关联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：h p 台式机j s o n y 打印机，是一个细节数据上的单层关联规则；而台 式机j s o n y 打印机，则是一个较高层次和细节层次之间的多层关联规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而 在多维的关联规则中，要处理的数据将会涉及多个维。换句话说，单维关联规则 是处理单个属性中的一些关系，多维关联规则是处理各个属性之间的某些关系。 例如：啤酒尿布，这条规则只涉及到用户的购买的物品；性别= “女”j 职业= “公关”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 3 3 关联规则挖掘技术的当前研究 目前，数据库中的关联规则挖掘研究己取得了令人瞩目的成绩，但以下方面 不完整数据库中的关联规则挖掘础f 宄 的研究也将是具有挑战性的工作： 1 设计更高效的挖掘算法 由于关联规则挖掘时要处理的目标数据库一般都十分庞大，挖掘算法的效率 显得尤为重要。单纯从计算机的角度对算法的研究已趋于饱和，有必要加深领域 知识的理解，以提取与我们的挖掘任务有关的数据，有效的降低问题的复杂度， 提高算法的效率 1 7 , 1 8 , 3 0 。在这方面，基于约束的关联规则挖掘有广阔的发展前景。 2 制定更为合理的规则衡量标准 在很多应用场合，衡量关联规则的两个标准，即支持和信任度是不够充分的， 往往会发现大量冗余、虚假或非有趣的规则，有必要制定一些新的衡量标准，但 这可能要和具体的挖掘问题相结合【5 , 3 1 。 3 不同数据源的挖掘 目前大多挖掘算法都足对确定的关系型数据库的挖掘。研究对其他类型数据 库( 如面向对象数据库、多维数据库、数据仓库、w e b 网页等) 的关联规则挖 掘以及对不确定性数据( 如不完整、不精确数据) 的挖掘也将是很实际的工作 2 2 , 2 3 。 4 可视化挖掘 关联规则挖捌的可视化主要是为了提高规则的可理解性，使用户与挖掘系统 有效的交瓦，加强与域专家的合作。人类视觉系统是一个非常宽域的信息通道。 可视化方法就是利用人类这一能力来发现并解释基于图形表示的数据模式和结 构。因此关联规则发现过程的可视化就成为最具潜力的研究方向之一。 不完整数据库中的关联规则挖掘研究 第4 章关联规则挖掘算法a p r i o r i 的实现 4 1 问题描述 在上一章中，我们已给出了关联规则挖掘问题的形式描述。给定一个事务集 d ，挖掘关联规则问题就是产生支持度和信任度分别大于用户给定的最小支持度 和最小信任度的关联规则，这个问题可以分解为阻下两个子问题： 1 找出事务数据库d 中所有大于等于指定最小支持度的项集。具有最小支 持度的项集称为频繁项集( f r e q u e n ti t e m s e t ) 。包含k 介项的项集称为k 一 项集。频繁k 一项集的集合通常记作l k 。 2 用频繁项集生成满足最小信任度的关联规则。方法为： 对于每个频繁项集l ，产生1 的所有非空子集。 对于l 的每个非空子集s ，如果s u p p o r t ( 1 ) s u p p o r t ( s ) m i n c o n f , 则输出规则“s 一 ( 1 - s ) ”。其中，m i n c o n f 是最小信任度。 其中，寻找频繁项集的问题是挖掘关联规则的核心问题。当找到所有的频繁 项集后，关联规则将很容易生成。 4 2 a p r i o r i 算法的实现 4 2 1 a p r i o r i 算法描述 a p r i o r i 算法是一种最有影响的挖掘关联规则频繁项集的算法。算法的基本思 想是：第一步，简单统计所有含一个元素的项集出现的频率，并找出那些不小于 最小支持度的项集，即1 频繁项集。第二步，循环处理直到再没有频繁项集生成， 即在第k 步中，根据第k 一1 步生成的仪1 ) 频繁项集产生k 一候选项集，然后搜索 数据库，计算候选项集的支持度，与最小支持度作比较，从而找到k 频繁项集。 至塞鳖垫塑壁! 塑鲞壁塑型丝塑! ! 塞 算法可描述如下： ( 1 )l l = f r e q u e n t1 - i t e m s e t ； ( 2 )f o r ( k = 2 ；l k l 中；k + + ) d ob e g i n ( 3 )c k = s c c a n d i d a t e ( l k 1 ) ； ( 4 ) f o ra l lt r a n s a c t i o n st e dd ob e g i n ( 5 ) c t = c o u n t _ s u p p o r t ( c k ，t ) ； ( 6 ) f o ra l lc a n d i d a t e sc ec td o ( 7 ) c c o u n t + + ； ( 8 1 e n d ( 9 ) l k = e ec ki c c o u n t m i n s u p ) ( 1 0 ) e n d 新的候选集 事务t 中包含的候选集 ( 11 ) a n s w e r = u k l k ； 其中，k - i t e m s e t 表示k - 项集，l k 表示频繁k - i t e m s e t ，c k 表示候选的k - i t e m s e t ， d 表示事务数掘库，m i n s u p 表示用户指定的最小支持度，a n s w e r 表示所有的频 繁项集。 4 2 2a p r i o r i 算法实现 本文设事务数据库中的项目都是以数字顺序排列的，每个项目用 来标志，这里t i d 表示相应事务的标识符，i t e m 表示项目名称；每个项集的项 目按照数字大小顺序排列，并且每个事务中的项目不允许重复。算法核心是求新 的候选项集的s cc a n d i d a t e 函数和计算候选项集的支持度的c o t m t _ s u p p o r t 函数， 描述如下： s c _ e a n d i d a t e ( lk 1 ) 该函数的参数是l k 1 ，主要是从所有的最大( k 1 ) 一项集中牛成含有k 个项目 的候选项集c k 。其功能分为两步： 第一步：连接( j o i n ) 步。通过对( k 1 ) - 频繁项集进行自连接操作生成c k 。 该步可描述为： i n s e r ti n t oc k 不完整数据库中的关联规则挖掘研究 s e l e c t p i t e m 1 ，p i t e m 2 ， f r o m l k 1p l k i q w h e r ep i t e m 1 】2q i t e m 1 ， q i t e m k 1 ，p i t e m k 一1 】，q i t e m k 一1 】 p i t e m k 一2 = q i t e m k 一2 ，p i t e m k 一1 】 = m i n s u p p o r t ，若a 的子集为a ，则a c o u n t 必然大于或等于m i n s u p p o r t 。所以川也必为频繁项集。 第二步：修剪( p r u n e ) 步。即对任意的c ，c c k ，删除c t 中所有那些( k 1 ) 一子集不在l k 1 中的项集，得到候选项集c k 。该步可描述为： f j ra l l i t e m s e t sc c k d o f o ra l l ( k 1 ) 一s u b s e t sso f cd o i f ( s 不属于l k i ) t h e n d e l e t ec f r o m c k 这里利用了第一步中的性质：频繁项集的子集必为频繁项集。即若某项目集 的( k 一1 ) 一子集不是频繁项集，则该项集不是频繁项集。所以删除。c k 中所有不在 l k _ l 中的( k 一1 ) 一子集。这个修剪过程可以降低计算所有的候选项集的支持度的代 价。 函数最后结果返回含有k 个项目的候选项集c k 。c k 是k 频繁项集的超集， 再通过函数c o u n ts u p p o r t 计算项目的支持度，然后生成l k 。该函数是快速有效 地在事务数据库中寻找频繁项集的关键之一，重点在于对项集进行充分的剪支， 尽最大可能地最小化有用的项集。 e o u n t _ s u p p o r t ( c k ，t ) 该函数的参数是候选项集c k 和任一事务t ，主要是从函数s c _ c a n d i d a t e 提供 的c k 中找到包含在事务t 中所有的候选项集。 除了函数s c c a n d i d a t e ( l k 1 ) 和c o u n t _ s u p p o r t ( c k ，t ) 以外，还有用来产 生关联规则的函数r u l e sg e n ( ) 。该函数利用频繁项集来生成所期望的关联规则， 对每一个频繁项集i ，找到i 的所有非空子集i ，如果比值s u p p o r t ( i ) s u p p o r t 15 不完粘数据库中的关联规则挖掘研究 ( i ) = m i n c o n f 满足最小信任度，就生成关联规则i = = ( i - i ) ，而比值s u p p o r t ( i ) s u p p o r t ( i ) 就是规则i - = ( i - i ) 的信任度。根据前面找到的所有的频繁项集，关联 规则将很容易生成。 4 , 2 3 a p r i o r i 算法的执行 本文作者用c 语言实现了a p r i o r i 算法，下一章的实验将会利用此算法，为 了更好地说明我们后面的实验，下面给出一个a p r i o r i 算法的执行实例。 假设某一事务数据库d ，预定义最小支持度为2 ，最小信任度为0 6 ，其中 有五个事务记录，分别表示为 t i di t e m s ll 13 1 4 22 23 24 31 33 34 35 4l 43 45 53 54 首先，第一步是搜索所有的事务记录，统计每个项目的支持度，由此产生候 不完整数据库中的关联规则挖掘研究 选的l 一项集，即c l ，其中满足最小支持度的项集组合成最大的l 一项集，即l 1 ： c i t e m s e t s u p p o r t l3 2 l 35 4 4 l 1 1 t e m s e t s u p p o r t 13 35 44 为了生成最大的2 一项集，使用了s c c a n d i d a t e 函数中j o i n 步，即：l j j o i n l i ， 并通过p r u n e 步删除那些c 2 的子集不在l 1 中的项集，由此生成了候选项集c 2 。 搜索d 中的五个事务，统计c 2 中每个候选项集的支持度，然后与最小支持度作 比较，生成l 2 ： c 2 l 2 i t e m s e t s u p p o r t 1 ，3 3 1 ，4 2 1 ，5 2 3 , 4 4 3 , 5 2 4 ，5 1 i t e m s e t s u p p o r t 1 ，3 3 1 ，4 2 1 ，5 2 3 , 4 4 3 , 5 2 候选项集c 3 是由l 2 生成的。l 2 中任意两个最大2 项集进行j o i n 操作，要求 第一个项目相同，其中满足该条件的集合有 1 、3 和 l 、4 ) ， l 、3 ) 和 1 、5 ， l 、4 ) 和 1 、5 ) ， 3 、4 1 年 1 3 、5 。经过j o i n 操作后，产生集合 l 、3 、4 ) ， 1 、 3 、5 ) ， 1 、4 、5 ) ， 3 、4 、5 ) 。然后在p r i m e 操作中，测试 1 、3 、4 ) 的2 一子集 1 、3 ) ， l ，4 ) ， 3 ，4 是否在l 2 中，搜索l 2 可以知道 1 、3 ) ， 1 ，4 ，( 3 ， 4 都是最大2 项集。所以 1 、3 、4 ) 是候选3 一项集。同样道理，分别对其他满足 条件的集合施以j o i n 和p r u n e 操作，生成候选3 一项集，然后搜索数据库中所有事 不完整数据库中的关联规则挖掘研究 务记录，