（计算机系统结构专业论文）基于利润分析的多层关联规则研究.pdf

重庆大学硕士学位论文英文摘要 摘要 面对当今竞争激烈的时代，企业无不采取计算机高新技术来提高效益。利用 数据挖掘技术，可以帮助企业获取庞大数据库中隐藏的有用信息，帮助企业决策 者作出正确的决策，因此，数据挖掘成为当今相当热门的研究领域，特别是在关 联规则方面的探讨尤其如此。通过关联规则可以找出数据库中某些商品项目间彼 此的关联性，如消费者的购物习惯等。对于如何才能有效的推导出关联规则，已 经有许多的方法相继被提出。但是大部分的算法都是处理单一层次间的关联规则。 然而因为商品项目众多、数据不够密集，找出的关联规则数目可能会变的较少， 许多隐藏的知识就不能被挖掘出来。多层次关联规则的挖掘技术，是将数据转换 成对应的层次化架构模式，再对各层次使用单层次关联规则算法来获得关联规则。 以往的单层次算法的做法，容易产生太多的候选项集，因而需要多次访问数据库 的操作。数据挖掘处理对象都是大型数据库，反复搜索数据库必将造成输入输出 上大量时间的浪费。而夹击搜索算法( p i n c e r - s e a x c h ) 在搜寻长度较长的频繁集时 效率较之传统算法有很大的提高，因此本文利用它的这个特性将之应用于多层次 架构中做关联规则挖掘，并和以往多层次关联规则的挖掘所采用的算法做分析并 比较其效果，结果发现，夹击搜寻算法的效率要高很多。另外，以往文献中讨论 的关联规则均未考虑购买商品的数量及获利性，然而，在商品交易中数量和获得 的相应利润是商家非常关心的焦点问题。因此，一个能有效挖掘多层次间数据并 包含数量与利润分析的关联规则才能满足企业最大程度上获利的需要。 本论文以作者参与的重庆市医药公司药品配送与零售系统中的药品销售 数据做研究对象，用夹击搜索算法在其上进行多层次关联规则挖掘，并与传统算 法( a p f i o f i ) 进行了实验结果的对照。实验证明，随着数据量的增加和数据层次 的加深，以及层次中类别的增加，夹击搜索算法对多层次a p d o f i 算法的效率优势 越来越明显。 另外，论文提出在挖掘出的关联规则中加入数量和利润来进行分析，并在实 验中通过具体的操作实现了这一点。论文分析了加入数量和利润的因素来重新解 读关联规则的意义。以往的关联规则通常进行的是所谓购物蓝分析，即在一定的 可信度和支持度下顾客在购买一种商品后会继续购买另外一种商品的可能性，也 就是分析顾客的购物习惯，进而做出诸如搭配销售、调整货柜位置等营销策略。 然而，这种分析存在一个缺点，比如在顾客购买第一种商品的利润远远大于他所 购买的后一种商品时，则关联规则给出的购物习惯对整个销售所带来的利润提升 意义不大。而本文中，对关联规则加入了数量和利润来分析，就会将该类无意义 重庆大学硕士学位论文 英文摘要 的关联规则剔除掉。相反的，在以往的讨论中，由于支持度或可信度低于阈值而 不被考虑的关联规则，在加上数量和利润后，有可能变成一个有趣的，有价值的 关联规则。例如：如果顾客购买了一个( 或多个) 利润较低的某种商品后会接着 购买与之相关的另外一种利润较高的商品，因为购买利润低的商品会促进较高利 润的商品的销售，所以这是一条商家乐于见到的关联规则，因为它对企业总体利 润的提升是一个有利的信息。正文中将对加入数量和利润的关联规则进行详细的 论述。 关键词：数据挖掘，关联规则，多层次关联规则，夹击搜索( p i n c e rs e a r c h ) i i 重庆大学硕士学位论文 英文摘要 a b s t r a c t i nt h i s c o m p e t i t i v ee r a , m o s te n t e r p r i s e s u s ec o m p u t e r st o i m p r o v et h e i r p e r f o r m a n c e d a t ar r f i n i n gc a nb eu s e dt of i n du s e f i a li n f o r m a t i o nt h a ti sh i d d e ni nt h e d a t a b a s e t h e t e c h n i q u e o fd a t a m i n i n g i s q u i t e ap o p u l a rr e s e a r c hf i e l d n o w a d a y s e s p e c i a l l yi r it h es t u d yo fa s s o c i a t i o nr u l e s b a s eo na s s o c i a t i o nr u l e s 舯m e i n f o r m a t i o ni nt h ed a t a b a s ec a l lb ed i s c o v e r e d ，f o re x a m p l ec u s t o m e rp u r c h a s i n g p a t t e r n s h o wt of i n do u ta s s o c i a t i o nr u l e se f f e c t i v e l yh a sb e e na c r i t i c a lt o p i c al o to f m e t h o d sh a v e b e e np u b l i s h e d b u tm o s ta l g o r i t h m sa r ed e a l i n g 、v i t hs i n g l e l e v e l a s s o c i a t i o nr u l e s b e c a u s eo ft r e m e n d o u sn u m b e ro fi t e m si n v o l v e da n dt h ed a t aw e r e n o th i g h l yc o n c e n t r a t e d ；t h en u m b e ro fa s s o c i a t i o nr u l e sm i n e dm i g h tn o tb ee n o u g h ， t h a ts o m ei m p o r t a n ti n f o r m a t i o ni nt h ed a t a b a s ew o u l db ec l o a k e d i ng e n e r a t i n g m u l t i l e v e ra s s o c i a t i o nr u l e s ，d a t aa r et r a n s f o r m e df o r mt h em u l t i l e v e la r c h i t e c t u r et oa c o r r e s p o n d i n gf o r m a t u s i n gp o p u l a rs i n g l e - l e v e la s s o c i a t i o nr u l e ss u c ha sa p r i o r i a l g o r i t h m , i ti se a s yt og e n e r a t ea l li t e m s e t sb u td a t a b a s en e e d st ob es e a r c h e dm a n y t i m e s d a t am i n i n gi so f t e nt od e a lw i t hl a r g ed a t a b a s e ，i ti saw a s t et os c a nt a r g e t d a t a b a s er e p e a t e d l y s ot h a tw eu s ep i n c e rs e a r c ha l g o r i t h mf o rs e a r c h i n gl o n gf r e q u e n t i t e m s e t si n s t e a do ft h ea p r i o r if o re f f i c i e n c y f r o mt h el i t e r a t u r e s ，w eb e l i e v ea n e f f e c t i v ea l g o r i t h mi ng e n e r a t i n gm u l t i - l e v e la s s o c i a t i o nr u l e si n c l u d i n gp r o f i to fs a l e s a n dq u a n t i t yo fi t e mp u r c h a s e dw i l lm e e tt h en e e d so fd e c i s i o nm a k e si na l lm a r k e t i n g d e p a r t m e n t i no u re x p e r i m e n t i ti sp r o v e dt h a tw i t ht h ed a t as c a l e sa n dl e v e l sg r o w i n ga n dt h e d a t ac l a s si n c r e a s i n g ，m u l t i - l e v e lp i n c e rs e a r c ha l g o r i t h ms h o w sm o r ea n dm o r ee v i d e n t a d v a n t a g ei ne f f i c i e n c yc o m p a r e dw i t ha p r i o ra l g o r i t h m i nt h i sp a p e r ，w ca d dq u a n t i t ya n dp r o f i tf a c t si na n a l y z i n ga s s o c i a t i o nr u l e s s i m p l y s p e a k i n g ，i fs o m el o wp r o f i ti t e ms u p p o r tt h es a l eo fa n o t h e rh i 曲p r o f i ti t e m ，w es a yi ti s ap r o f i t a b l ea s s o c i a t i o nr u l e o u rn e wa n a l y s i sm e t h o dg i v em o r eh e l pt h a nt h e t r a d i t i o n a lm a k e rb a s k e ta n a l y s i s 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 , m u l t i p l el e v e la s s o c i a t i o nr u l e s , p i n c e rs e a r c h 1 1 1 重庆大学硕士学位论文1 绪论 1 绪论 1 1 论文的研究背景及选题的意义 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，成千上 万的数据库被用于商业管理、政府办公、科学研究和工程开发等等，并且这一势 头仍将持续发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆炸的 时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所 淹没，从中及时发现有用的知识，提高信息利用率呢? 只有使数据真正成为一个公 司的资源，并且充分利用它为公司自身的业务决策和战略发展服务才行，否则大 量的数据可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥 饿于知识”的挑战，数据挖掘和知识发现( d m k d ) 技术应运而生，并得以蓬勃发展， 越来越显示出其强大的生命力。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程。还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、数据 分析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的 源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系数据库中的数 据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异 构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也 可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程 控制等，还可以用于数据自身的维护。因此，数据挖掘是一门很广义的交叉学科， 它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并 行计算等方面的学者和工程技术人员。 数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检索 查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推 理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据 对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大s i r n o n f r a s c r 大学 k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新的电话收费和 管理办法，制定既有利于公司又有利于客户的优惠政策。这样一来，就把人们对 数据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。 这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这里所说的知识 发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定 理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有 重庆大学硕士学位论文1 绪论 特定前提和约束条件、面向特定领域的。 从挖掘的任务可以把数据挖掘分为：聚类、分类发现、和关联规则等三大类。 聚类是把组个体按照相似性归成若干类别，即”物以类聚”。它的目的是使得 属于同类别的个体之间的距离尽可能的小，而不同类别的个体间的距离尽可能 的大。在目前聚类算法的研究中，把聚类方法分成了如下的几类：( 1 ) 划分方法( 2 ) 层次的方法( 3 ) 基于密度的方法( 4 ) 基于网格的方法( 5 ) 基于模型的方法。在聚类数据 挖掘中，所面临的最大问题就是效率不高与准确性低。 关联规则 1 】的目的是描述在大型数据库中数据项之间的关联性如何。使用者可 以利用自定的关联性标准的高低，在数据库中寻找数据项目之间所隐含时的其他 信息以及关联性。最简单的例子就是购物篮分析( m a r k e tb a s k e ta n a l y s i s ) ，通过 顾客购买的交易记录找出商品之间的关联性，作为商品项目之间如何搭配促销或 是考虑商品在商品储存柜的摆放位置，甚至仓库管理的参考依据1 2 1 许多关联规则的数据挖掘技术中相当多的研究都限于在单层次关联规则探讨 上。相对与单层次研究的情况，多层次关联规则的研究显得不那么热烈和深入。 但是为了满足不同的决策方向以及需求，多层次关联规则的研究仍是不可缺少。 针对多层次结构的关联规则算法，是为了满足不同的需求而产生，虽然通过多层 次结构可以将大量琐碎、密集度不高的交易项目做归纳，使得关联性不高的商品 能在使用层次分类后被挖掘出来并提供更多的信息，但是当层次增加以及层次之 间分类项目太多时，对多层次关联规则的求解仍然有缺陷，因此我们尝试利用现 有有效的单层次上寻找频繁高项集的算法，套用在多层次关联规则的架构上，和 以往多层次算法的性能做分析比较。 此外，一般情况下所挖掘出的关联规则知识代表商品项目与项目之间的趋势， 而无法得出关于商品项目的其他的信息，如商品数量、利润等。因此想通过对商 品数量的考察以及对利润的评估，对所挖掘出的关联规则加以分析，满足不同决 策者不同角度的需求，使得关联规则不只是一个大概的趋势分析，而是还可以从 另外的角度来对数据进行分析，作为企业决策者的参考知识。可见本论文研究工 作有重要的实用价值和理论意义。 1 2 国内外现状综述 关联规则是发现交易数据库中不同商品( 项) 之间的联系，这些规则找出顾客 购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以 应用于商品货架设计、货存安排以及根据购买模式对用户迸行分类。 a g r a w a l 等于1 9 9 3 年d i 首先提出了挖掘顾客交易数据库中项集间的关联规则 问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工 2 重庆大学硕士学位论文1 绪论 作包括对原有的算法进行优化，如引入随机采样并行的思想等，以提高算法挖 掘规则的效率；对关联规则的应用进行推广。 最近也有独立于a g r a w a l 的频繁项集方法的工作 4 ，”，以避免频繁项集方法的 一些缺陷。探索挖掘关联规则的新方法；同时随著0 l a p 技术的成熟和应用，将 o l a p 和关联规则结合【6 7 】也成了一个重要的方向；也有一些工作嗍注重于对挖掘到 的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。 a g r a w a l 等于1 9 9 3 年 3 1 首先提出了挖掘顾客交易数据库中项集间的关联靛则 问题，其核心方法是基于频繁项集理论的递推方法以后诸多的研究人员对关联 规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如 引入随机采样、并行的思想等，以提高算法挖掘规则的效率：提出各种变体，如 泛化的关联规则、周期关联规则等，对关联规则的应用进行推广。 a g r a w a l 等 3 1 在1 9 9 3 年设计了一个基本算法，提出了挖掘关联规则的一个重要 方法。这是一个基于两阶段频繁项集思想的方法，将关联规则挖掘算法的设计可 以分解为两个子问题： 1 1 找到所有支持度大于最小支持度的项集( i t e m s e t ) ，这些项集称为频繁项集 ( f r e q u e n ti t e m s e 0 2 ) 使用第l 步找到的频繁项集产生期望的规则 在论文【6 】中，a g r a w a l 等引入了修剪技术( p r u n i n g ) 来减小候选集c k 的大小， 由此可以显著地改进生成所有频繁项集算法的性能算法中引入的修剪策略基于 这样一个性质：一个项集是频繁项集当且仅当它的所有子集都是频繁项集那么， 如果c k 中某个候选项集有一个( k _ 1 ) 一子集不属于l k - 。，则这个项集可以被修剪掉不 再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价文 1 4 1 中， 还引入杂凑树( h a s ht r e e ) 方法来有效地计算每个项集的支持度 虽然a p r i o r i 算法自身已经进行了定的优化，但是在实际的应用中，还是存 在不令人满意的地方，于是人们相继提出了一些优化的方法 1 基于划分的方法s a v a s e r e 等1 9 1 设计了一个基于划分( p a r t i t i o n ) 的算法，这个 算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它 生成所有的频繁项集，然后把产生的频繁项集合并，用来生成所有可能的频繁项 集，最后计算这些项集的支持度这里分块的大小选择要使得每个分块可以被放 入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁项集 至少在某一个分块中是频繁项集保证的。 2 基于h a s h 的方法一个高效地产生频繁项集的基于杂凑o a t h ) 的算法由p a r k 等1 1 0 】提出来通过实验我们可以发现寻找频繁项集主要的计算是在生成频繁2 项 集厶上，p a r k 等就是利用了这个性质引入杂凑技术来改进产生频繁2 一项集的方法 重庆大学硕士学位论文1 绪论 3 基于采样的方法基于前一遍扫描得到的信息，对此仔细地作组合分析，可 以得到个改进的算法，m a n n i l a 等f l7 l 先考虑了这一点，他们认为采样是发现规则 的一个有效途径。随后又由t o i v o n e n 【10 】进一步发展了这个思想，先使用从数据库 中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩 余部分验证这个结果。t o i v o n e n 的算法相当简单并显著地减少了i o 代价，但是一 个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲( d a t as k e w ) 分布在 同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布， 由此而导致的是采样5 的交易数据所花费的代价可能同扫描一遍数据库相近 l i 】l 和d u n h a m 在( _ h 中讨论了反扭t ( a n f i s k e w ) 算法来挖掘关联规则，在那里他们 引入的技术使得扫描数据库的次数少于2 次，算法使用了一个采样处理来收集有 关数据的次数来减少扫描遍数。 b r i n 等口l 】提出的算法使用比传统算法少的扫描遍数来发现频繁项集，同时比 基于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑 是，在计算k - 项集时，一旦我们认为某个( 1 叶1 ) 项集可能是频繁项集时，就并行地 计算这个( k + 1 ) 项集的支持度，算法需要的总的扫描次数通常少于最大的频繁项集 的项数。这里他们也使用了杂凑技术，并提出产生“相关规则( c o r r e l a t i o nr u l e s ) ” 的一个新方法，这是基于他们的【3 】工作基础上的。 4 减少交易的个数减少用于未来扫描的事务集的大小。一个基本的原理就 是当一个事务不包含长度为k 的大项集，则必然不包含长度为k + 1 的大项集，从 而我们就可以将这些事务移去，这样在下一遍的扫描中就可以减少进行扫描的事 务集的个数。这个就是a p r i o r i t i d 的基本思想 上面介绍的都是基于a p r i o r i 的频繁项集方法，即使进行了优化，a p r i o r i 方法 一些固有的缺陷还是无法克服： 1 ) 可能产生大量的候选集当长度为1 的频繁项集有1 0 0 0 0 个的时候，长度 为2 的候选集个数将会超过1 0 m 。还有就是如果要生成一个很长的规则的时候， 要产生的中间元素也是巨大量的。 2 ) 无法对稀有信息进行分析 由于频繁项集使用了参数m i n s u p ，所以就无法 对小于m i n s u p 的事件进行分析；而如果将m i n s u p 设成一个很低的值，那么算法的 效率就成了一个很难处理的问题。 下面两种方法，分别用于解决以上两个问题： 在【l8 j 中提到了解决问题1 的一种方法，采用了一种f p g r o w t h 的方法。他们采 用了分而治之的策略：在经过了第一次的扫描之后，把数据库中的频繁项集压缩 进一棵频繁模式树( f p t r e e ) ，同时依然保留其中的关联信息，随后我们再将f p t r e e 分化成一些条件库，每个库和一个长度为l 的频繁项集相关，然后再对这些条件 重庆大学硕士学位论文1 绪论 库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法，使得一个 f p t r e e 可以放入主存中。实验表明，f p g r o w t h 对不同长度的规则都有很好的适应 性，同时在效率上较之a p r i o r i 算法有巨大的提高。 第二个问题是基于这个的一个想法：a p r i o r i 算法得出的关系都是频繁出现的， 但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不 是频繁出现的在a p r i o r i 算法中，起决定作用的是支持度，而我们现在将把可信 度放在第一位，挖掘一些具有非常高可信度的规则在【1 9 】中介绍了对于这个向题 的一个解决方法整个算法基本上分成三个步骤：计算特征、生成候选集、过滤 候选集。在三个步骤中，关键的地方就是在计算特征时h a s h 方法的使用。在考 虑方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。基本的方 法有两类：m i n _ h a s h i n g ( m h ) 和l o c a l i t y _ s e n s i t i v e _ h a s h i n g ( l s h ) m i n _ h a s h i n g 的 基本想法是：将一条记录中的头k 个为1 的字段的位置作为一个h a s h 函数 l o c a l i t y _ s e n t i t i v e _ h a s h i n g 的基本想法是：将整个数据库用一种基于概率的方法进 行分类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。 我们再对这两个方法比较一下：m h 的遗漏率为零，错误率可以由k 严格控制， 但是时空效率相对的较差；l s h 的遗漏率和错误率是无法同时降低的，但是它的 时空效率却相对的好很多。所以应该视具体的情况而定。最后的实验数据也说明 这种方法的确能产生一些有用的规则。 多层关联规则： 对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次 上发现一些强关联规则，当我们引入概念层次后，就可以在较高的层次上进行挖 掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是 普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多 个层次上进行挖掘的功能。 多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层 关联规则和层问关联规则。 多层关联规则的挖掘基本上可以沿用“支持度可信度”的框架，不过，在支 持度设置的问题上有一些要考虑的东西。 多层关联规则可以采用两种支持度策略： 1 ) 统一的最小支持度对于不同的层次，都使用同一个最小支持度。这样对 于用户和算法实现来说都比较的容易，但是弊端也是显然的。 2 ) 递减的最小支持度每个层次都有不同的最小支持度，较低层次的最小支 持度相对较小，同时还可以利用上层挖掘得到的信息进行一些过滤的工作。 层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来定。 重庆大学硕士学位论文1 绪论 对于多维数据库而言，还有一类多维的关联规则。 关联规则价值衡量的方法 很多的算法都使用“支持度一可信度”的框架，这样的结构有时会产生一些错误 的结果。于是人们引入了兴趣度，用来修剪无趣的规则，即避免生成错误的关联 规则。一般一条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的 强度之比，然而在许多应用中已发现，只要人们仍把支持度作为最初的项集产生 的主要决定因素，那么要么把支持度设得足够低以使得不丢失任何有意义的规触， 或者冒丢失一些重要规则的风险；对前种情形计算效率是个问题，而后一种情 形则有可能丢失从用户观点来看是有意义的规则的问题 在 1 2 】中作者给出了感兴趣的规则的定义( r - i n t e r e s t i n g ) ，在 1 3 j 中他们又对此 作了改进在【io 】中把事件依赖性的统计定义扩展到兴趣度的定义上来： 1 5 1 定义了 否定关联规则的兴趣度。 除了把兴趣度作为修剪无价值规则的工具，现在已有许多其他的工作来重新认 识项集，如b r i n 等考虑的相关规则在1 ”中讨论了蕴涵规则( i i n p l i c a t i o 矗r u l e ) ， 规则的蕴涵强度在【o ，叫之间变化，其中蕴涵强度为1 表示完全无关的规则，m 表示 完备的规则，如果蕴涵强度大于1 则表示更大的期望存在性。 1 3 论文研究的内容及组织 本论文研究的内容有以下两个方面： ( 1 ) 将成熟完善的单层次关联规则挖掘算法应用于多层次关联规则的挖掘。比 较了这种思路的算法与以往多层次关联规则挖掘算法的性能。 ( 2 ) 将商品交易数量和利润率考虑到多层次关联规则的挖掘中，使挖掘出的规 则除了能表示商品之间的联系外还能进一步分析商品利润。使决策者得出更多有 用的信息。 1 4 论文结构 在本论文其他章节中，第2 章将详细介绍文献中数据挖掘在关联规则中所应用 的技术以及多层次关联规则的探讨。第3 章介绍我们提出的构想，对于传统算法 与作者所采用的算法在多层次架构上求取关联规则时性能上的差异。至于构想的 实际模拟以及对于挖掘出的关联规则加上利润和交易商品数量作为考虑因素来做 分析，将在第4 章中说明。第5 章对本论文进行总结并对未来研究的方向进行说 明与展望。 6 重庆大学硕士学位论文 1 绪论 1 5 本章小结 在本章中，主要介绍了本论文的研究背景及其应用价值，并对相关领域的研 究现状作了较详细的阐述。最后说明了本论文的研究内容及文章结构。 重庆大学硕士学位论文2 数据挖掘与关联规贝u 挖掘技术 2 数据挖掘与关联规则挖掘技术 2 1 数据挖掘技术简介 2 1 1 数据挖掘的定义 r r 技术的迅速发展，使数据库的规模不断扩大，产生了巨大的数据洪流。为给决 策者提供一个统一的全局视角，在许多领域建立了数据仓库。大量的数据往往使 人们无法辨别隐藏在数据中的、能对决策提供支持的信息，而传统的查询、报表 工具无法满足发掘这些信息的需求，因此需要一种新的数据分析技术来处理大量 数据，从中抽取有价值的潜在信息，数据挖掘技术由此应运而生。 从技术基础的角度来看：知识发现的技术及算法的发展，使得数据挖掘工具 的功能和实用性得到提高。j o h ah o p f i e l d 在神经元网络方面：b r i e m a n 、f r i e d m a n o l s h e n 和s t o # 等人在决镶树方面以及h o l l a n d 和g o l d b e r g 口1 1 等人在遗传算法方面 所进行的开创性工作大大推进了数据挖掘技术的实际应用。目前在国外已有许多 领域成功采用了数据挖掘这一工具辅助决策，如市场营销、零售业、金融、医疗 保险、政府部门及科学研究等，已充分显示了这一信息技术的优越性，这也促进 了应用和研究的进一步发展。 2 1 2 数据挖掘的任务 数据挖掘的任务常见的有4 种类型： 分类：用于预测事件所属的类5 j j 。其中样本数据中包含标识样本事件所属类别 的数据项，类别是已知的，由数据挖掘根据样本数据构建对这些类别的模式的描 述，再利用所发现的模式，参照新的数据的特征变量，将其映射入已知类别中。 如在医疗应用中，可根据患者的各种特征进行疾病诊断等。 聚类：用于描述和发现数据库中以前未知的数据类别。其中样本数据中不包 含类别变量，数据挖掘将具有共同趋势和模式的数据元组聚集为一类，使类中各 元组相似程度最高，类问差异最大。常用于市场细分。可根据已有顾客的数据， 利用聚类技术将市场按顾客的消费模式的相似性分为若干细分市场，以进行有针 对性的市场营销。 关联规则：用于发现给定事件或纪录中经常一起发生的项目，由此推断事件 间潜在的关联，识别有可能重复发生的模式。关联分析的典型例子是市场篮子分 析描述顾客的购买行为。如尿布与啤酒的故事就属于关联分析，可帮助零售商 决定商品的摆放和捆绑销售策略。 序列模式：与关联分析类似，只是扩展为一段时间的项目集间的关系，常把 片列模式看作由时间变量连接起来的关联。序列分析可分析长时期的相关纪录， 片列模式看作由时间变量连接起来的关联。序列分析可分析长时期的相关纪录， 8 重庆大学硕士学位论文2 数据挖掘与关联规则挖掘技术 2 数据挖掘与关联规则挖掘技术 2 1 数据挖掘技术简介 2 1 1 数据挖掘的定义 i t 技术的迅速发展，使数据库的规模不断扩大，产生了巨大的数据洪流。为给决 策者提供一个统一的全局视角，在许多领域建立了数据仓库。大量的数据往往使 人们无法辨别隐藏在数据中的、能对决策提供支持的信息，而传统的查询、报表 工具无法满足发掘这些信息的需求，因此需要一种新的数据分析技术来处理大量 数据，从中抽取有价值的潜在信息，数据挖掘技术由此应运而生。 从技术基础的角度来看：知识发现的技术及算法的发展，使得数据挖掘工具 的功能和实用性得到提高。j o h nh o p f i e l d 在神经元网络方面；b f i e m a n 、f r i e d m a n o l s h e n 和s t o n e 等人在决策树方面以及h o l l a n d 和g o l d b e r g t “1 等人在遗传算法方面 所进行的开创性工作大大推进了数据挖掘技术的实际应甩。目前在国外已有许多 领域成功采用了数据挖掘这一工具辅助决策，如市场营销、零售业、金融、医疗 保险、政府部门及科学研究等，已充分显示了这一信息技术的优越性，这也促进 了应用和研究的进一步发展。 2 1 2 数据挖掘的任务 数据挖掘的任务常见的有4 种类型： 分类：用于预测事件所属的类别。其中样本数据中包含标识样本事件所属类别 的数据项，类别是已知的，由数据挖掘根据样本数据构建对这些类别的模式的描 述，再利用所发现的模式，参照新的数据的特征变量，将其映射入已知类别中。 如在医疗应用中，可根据患者的各种特征进行疾病诊断等。 聚类：用于描述和发现数据库中以前未知的数据类别。其中样本数据中不包 含类别变量，数据挖掘将具有共同趋势和模式的数据元组聚集为一类，使类中各 元组相似程度最高，类间差异最大。常用于市场细分。可根据已有顾客的数据， 利用聚类技术将市场按顾客的消费模式的相似性分为若干细分市场，以进行有针 对性的市场营销。 关联规则：用于发现给定事件或纪录中经常一起发生的项目，由此推断事件 间潜在的关联，识别有可能重复发生的模式。关联分析的典型例子是市场篮子分 析，描述顾客的购买行为。如尿布与啤酒的故事就属于关联分析，可帮助零售商 决定商品的摆放和捆绑销售策略。 序列一模式：与关联分析类似，只是扩展为一段时间的项目集间的关系，常把 序列模式看作由时间变量连接起来的关联。序列分析可分析长时期的相关纪录， 重庆大学硕士学位论文2 数据挖掘与关联规则挖掘技术 发现经常发生的模式。 2 1 3 数据挖掘的常用方法 数据挖掘的技术基础是人工智能，它利用了人工智能中一些已经成熟的算法 和技术，例如：遗传算法( g e n e t i c a l g o r i t h m s ) 、人工神经网络( n e u r a l n e t w o r k ) 、决 策树( d e c i s i o nt r e e s ) 、邻近搜索方法( n e a r e s tn e i g h b o rm e t h o d ) 、规则推理( r u l e i n d u c t i o n ) 、模糊逻辑( f u z z yl o g i c ) 等，但问题的复杂度和难度却比人工智能降低了 许多，下面是数据挖掘技术中的常用算法： ( 1 ) 遗传算法。 遗传算法是模拟生物进化过程的算法，由三个基本算子组成： 繁殖( 选择) ，即从一个旧群体( 父代) 选出一个生命力强的个体，产生新的种 群( 后代) 的过程。 交叉( 重组) ，即选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成新 个体的过程。 变异( 突变) ，即对某些个体的某些基因进行变异( o 变1 、1 变o ) ，形成新个 体的过程。 这种遗传算法可起到优良后代的作用。这些后代需满足适应值，经过若干代 的遗传，将得到满足要求的后代( 即问题的解) 。遗传算法已在优化计算和分类机器 学习方面发挥了显著作用。 ( 2 ) 人工神经网络。人工神经元网络方法模拟人脑神经元结构，以m p 模型和 h e b b 学习规则为基础，一般分为三种网络模型【2 2 l ： 前馈型网络。一般前馈型网络无反馈的特征，这类网络能够串联地连接起 来以建立多层网络，在这样的网络中，一层的输出是下一层的输入。输入输出节 点可与外界相联，可直接受外界环境的影响，所以可称为可见层，而其中层间与 外问无直接联系，所以称为隐含层。节点有输入、计算单元和输出三类。每一计 算单元可以有任意个输入但只有一个输出，其输出可以耦合到任意多个其他节点 的输入。两层的前馈网络只有单层计算单元，这实际上就是网络最简单的形式 感知器。前馈型网络以感知器、反向传播模型、函数型网络为代表，可用于预测、 模式识别等方面。 反馈型网络。反馈型网络所有节点都是计算单元，同时既可接受输入，又 可向外界输出。通过网络神经元状态的变迁而最终稳定于某一状态，从而得到联 想存储或者神经计算的结果。它以离散型h o p f i e l d 神经元网络和连续模型为代表， 分别用于联想记忆和优化计算。 自组织网络。它以a r t 模型、k o h o l o n 模型为代表，用于聚类分析等方面。 人工神经网络的知识体现在网络连接的权值上，是一个分布式矩阵结构，起 9 重庆大学硕士学位论文2 数据挖掘与关联规则挖掘技术 学习体现在网络权值的逐步计算上。 ( 3 ) 决策树。决策树是通过一系列规则对数据进行分类的过程。采用决策树， 可将数据规则可视化，也不需要长时间的构造过程，输出结果容易理解，精度较 高，因此决策树在知识发现系统中应用较广。然而，采用决策树方法也有其缺点。 决策树方法很难基于多个变量组合发现规则。不同决策树分支之间的分裂也不平 滑。 ( 4 ) 公式发现。即在工程和科学数据库( 由实验数据组成) 中对若干数据项( 变量) 进行一定的数学运算，求得相应的数学公式。 ( 5 ) 统计分析方法。利用统计学中的数学原理对数据库进行分析，有如下方法 】讲l ： 相关分析和回归分析。相关分析是用相关技术来度量变量间的相关程度； 回归分析是用数学方程来表示变量间的数量关系，方法有线性回归和非线性回归。 差异分析。从样本统计量的值得出的差异来确定总体参数之间是否存在差 异( 假设检验) 。典型的方法为方差分析，它是通过分析实验数据中不同来源的变异 对总体变异的贡献大小，从而确定实验中的可控因素( 自变量) 是否对实验结果( 因 变量) 有重要的影响。 因子分析。它是用较少的综合变量来表达多个观察变量，根据相关性大小 把变量分组，使得同组变量之间相关性较高，不同变量间的相关较低。 ( 6 ) 其他技术。 模糊论方法。模糊论在数据挖掘的主要应用是聚类分析，称为模糊聚类。 传统的聚类分析是一种硬划分，也就是说类的划分的界限是分明的，而实际上大 多数对象并没有严格的属性，它们的类属和性态存在着中介性，因此适合于软划 分。模糊集理论的提出为这种划分提供了有力的工具。模糊聚类不但可以从原始 数据中直接提取特征，还可以对特征进行优选和降维操作。模糊聚类既可以提供 最近邻原型分类器，还可以用来进行特征空间划分和模糊规则提取1 2 1 。 粗糙集技术。粗糙集理论作为一种全新的数学概念，为处理具有不完整、 不一致及不确定性特征的信息提供了新的有效工具。它由波兰学者p a w l a k z 在 1 9 8 2 年首次提出，1 9 9 1 年，p a w l a k 教授出版了专著，全面系统地阐述了r s 理 论【2 0 j 。目前有关粗糙集的研究日益受到国内外学术界的重视。在数据挖掘领域， 粗糙集最初主要用于分类，数据的归约，时间序列的数据挖掘。 可视化技术。可视化数据分析技术拓宽了传统的图表功能，使用户对数据 的剖析更清楚。例如把数据库中多维的数据变成多种图形，这对揭示数据中的状 况、内在本质及其规律性都起到了很强的作用。 总的来说，应该根据不同的问题环境和应用层面来选择合适的方法，并且灵 重庆大学硕士学位论文2 数据挖掘与关联规则挖掘技术 活应用来解决数据挖掘中遇到的难题。 2 1 4 数据挖掘的应用 目前，数据挖掘的应用领域包括以下八个方面，而每个领域又都有自己的应 用领域和应用背景口5 j 2 6 】。 ( 1 ) 金融。金融事务需要收集和处理大量的数据，通过对这些数据进行分析， 发现其数据模式及特征，然后可能发现某个客户、消费群体或组织的金融和商业 兴趣，也可观察金融市场的变化趋势。数据挖掘在金融领域的应用广泛，包捂数 据清理、金融市场分析预测、用户分类、信用评估等。 ( 2 ) 医疗保健。医疗保健业有大量的数据需要处理，但这个行业的数据由不同的 信息管理系统管理，数据以不同的格式保存，从总体看，数据是无组织的。在这 个行业中，数据挖掘的关键任务是进行数据清理、预测医疗保健的费用。例如g t e 实验室开发的k e f i r ，它能进行多维分析，用于分析g t e 的医疗保健数据，对比 数据和预测数据，在定量范围内解释偏差，生成超文本报表【2 5 j 。 ( 3 ) 市场业。市场业应用数据挖掘技术进行市场定位、消费者分析、辅助制定 市场营销策略等。 ( 4 ) 零售业。零售业是最早运用数据挖掘技术的行业。目前，主要运用于销售 预测、库存需求、零售点的选择、价格分析等。 ( 5 ) 制造业。制造业应用数据挖掘技术进行零部件故障诊断、资源优化、生产 过程分析等。 ( 6 ) 司法。数据挖掘也可应用于案件调查、诈骗检测、犯罪行为分析等方面， 这些都可以给司法工作带来巨大的利益。 ( 7 ) 工程和科学。在信息量极为庞大的天文、气象、生物技术等领域中，所获 得的大量实验和观察数据用靠传统的数据分析工具难以应付，因此对功能强大的 智能化自动分析工具要求迫切，这种需求推动了d m 技术在科学研究领域的应用 发展，目前已获得了一些重要的研究成果，例如：j e tp r o p u l s i o n 实验室利用决策 树方法对上百万天体数据进行分析，帮助天文学家发现了1 6 个星的星体，效果要 比人工更快，更准确。 ( 8 ) 保险业。对受险人员的分类将有助于确定适当的保险金额度。通过数据挖 掘可以得到对不同行业、不同年龄段、不同社会层次的人，他们的险金应该如何 确定。另外，还可进行险种关联分析，分析购买了某种保险的人是否又同时购买 另一种保险，也可预测什么样的顾客将会购买新险种。 2 2 关联规则挖掘算法 在讨论多层次关联规则算法之前，必须先介绍相关基本概念以及讨论一些常见 重庆大学硕士学位论文2 数据挖掘与关联规则挖掘技术 的单层次关联规则算法。因为以往在多层次关联规则算法的推导中，大多利用层 次化架构的思想来做说明，并且事先对处理的数据形式进