（应用数学专业论文）基于等价类的关联规则挖掘矩阵算法的设计及应用.pdf

河南大学研究生硕士学位论文第1 页 摘要 关联规则是最常见的知识表示方法之一，关联规则挖掘技术应用于档案管理 信息系统中可以发现档案利用者使用档案的规律，以便提供主动服务，保护档案 实体安全；发现师资队伍的学缘结构、年龄结构、职称结构是否合理及人才流动 原因等，为领导部门制定相关管理政策提供辅助支持，从而极大地提升我国档案 信息化管理工作的层次和效率。但目前存在的关联规则算法，或需多次扫描数据 库，或产生的候选项集数量巨大，或没有考虑事务间的相关性，而这些相关性在 档案数据库中是普遍存在的，因此，这些算法应用于档案数据挖掘效率较低。如 何改进现有的关联规则算法，从而可以在档案管理信息系统中推广应用成为目前 研究的一个热点问题。 为此，本文提出了基于等价类的关联规则挖掘矩阵算法( a s s o c i a t i o nm i n i n g m a t r i 】 a 1 9 0 工i i t h mb a s e do ne q u i v a l e n c ec 1 a s s ，以下简称e c a m m a 算法) ，该算 法用数据矩阵存储事务集，只需扫描数据库一次，采用等价类划分来约简事务集， 并且运算过程中不产生候选项集。由于最大频繁项集隐含了所有的频繁项集，所 以e c a m m a 算法通过求取最大频繁项集来挖掘关联规则，算法把扫描数据库得到 的数据转换成布尔数据后，用布尔数据矩阵存贮，矩阵的行表示事务，列表示事 务中可能出现的项目，算法充分考虑到事务之间的相关性，采用等价划分的思想， 对数据矩阵进行等价类划分，然后利用矩阵中各行的等价关系和频繁项集性质对 数据矩阵从行和列两个方向进行约简，最后对约简后的数据矩阵自左向右扫描， 利用本文提出的项目相似度在不产生候选项集的情况下，直接求取所有的最大频 繁项集，进而求得关联规则。 实验证明当频繁项集的维数k 大于2 4 时效率比a p r i o r i 算法有显著的提高，当k 大于2 8 时算法的执行效率则比a p r i o r i 算法高出5 倍以上，且k 越大优势越明显。我 们把研究成果初步应用于人事档案管理信息系统中，在对教科研人员基本信息及 其流动信息挖掘等方面，取得了较理想的效果。 本文的主要贡献如下： 1 ) 采用等价划分的思想进行事务集约简。 2 ) 提出项目相似度的概念，利用项目相似度在不产生候选项集的情况下直接 求取最大频繁项集。 第| i 页河南大学研究生硕士学位论文 3 ) 将e c a m m a 算法应用于档案数据挖掘并取得了较理想的效果。 关键词：关联规则；等价类；项目相似度；数据挖掘 河南大学研究生硕士学位论文第1 il 页 a b s t r a c t a s s o c i a t i o nm l e si so n eo ft h em o s tk n o w l e 起er e p r e s e n t a t i o nm e t h o d a p p l i e dt o a r c h i v a li n f 0 m a t i o nm a i l a g e r ，t h e 嬲s o c i a t i o nm l em i i l i i l gt e c l u l o l o g yc a np r 0 v i d e a c t i v es e n r i c ef o rt h eu s e r s 觚df m dt h ea g es t m c t u r e ，p o s ts t m c t u r er e a s o n a b l e0 rn o t 锄dc a nf i n dt h er e a s o no fs o m et e a c h e r so f rt h es c h o o l ，w h i c hw i l lh e l pr e l e v a n t d e p a r n i l e n t st o w o r k0 u tm 锄a g e m e n tp o i i c i e st os n e n 舀h e nt h eb u i l d i n go ft h e c o n t i n g e n to ft e a c h e r s ，t h e r e b y 伊e a t l ye n h a l l c e t h el e v e l 孤dw o r ke m c i e n c yo fo u r a r c h i v ei n f o n n a t i o nm a n a g e m e n t h o w e v e r ，t h ee x i s t i i l ga s s o c i a t i o nm l ea l g o r i t h m s m a yg e n e r a t ea 目? e a tn u m b e ro fc a n d i d a t ei t e m s e t sw h i c ha a e c tt h ee f n c i e n c yo f a l g o r i 山 1 l s ，0 rh a v e n tc o n s i d e r i n gt h er e l a t i o n s h i pb e 铆e e n 位m s a c t i o n s ，w h i c ha r ea l a r g en u m b e r i 1 1s o m ed a t a b a s e ，s u c ha sp e r s o i l i l e la r c h i v ed a t a b a s e s oh o wt oi m p r o v e t h ee x i s t i n ga s s o c i a t i o nm l ea l g o r i t h mt ou s ei nt h ea r c h i v em a n a g e m e n ti n f o m a t i o n s y s t e ma p p l i c a t i o nt ob e c o m eah o ti s s u ei nm ep r e s e n ts t u d y t 1 l ea r t i c l ep r o p o s e da s s o c i a t i o nm i n i n gm 删xa l g o r i t h mb a s e do ne q u i v a l e n c e c l a s s m e r e m a r e r r e f e l l r e dt oe c a m m a a 1 9 0 r i t h m ) t h ea l g o r i t h ms t o r a g e d 咖n s a c t i o ns e t sw i t hb o o ld a l t a m a 埘x ，s e a r c h e d i l lt h ed a t a b a s e s 0 n l y0 n c e ， c o m p a n m e n t a l i z e de q u i v a l e n c ec l a s st oa c h i e v et l l er e d u c t i o no fn 硼s a c t i o na n dd i d n t g i v e nb i n ht oa 1 1 yc a n d i d a t e i t e m s e t sd u r i n go p e r a t i o n b e c a u s ea l lt h e 舶q u e n t i t e m s e t si m p l i e di nm em a x i m a l 丹e q u e n ti t e m s e t s ，t h ea l g o r i t h mm i l l e da s s o c i a t i o n r u l e sb ys e e k i n gt h em a x i m a l 疔e q u e n ti t e m s e t f i r s t 协m s f o 肌t h ed a t aw h i c h9 0 tb y s c a n n i n gd a t a b a s ei n t ob o o ld a t a ，锄dt h e ns t o r a g et h e mi i l t h eb o o ld a t am a t r i x c o n s i d e r i n gt h ec o l l r e l a t i o nb e t w e e nt r a n s a c t i o n s ，t oc o m p a 舳e n t a l i z ee q u i v a l e n c e c l a s sa c c o r d i i l gt od a t am 删x u ，t h e nr e d u c et h ed a t am a t r i x 自o mt h ed i r e c t i o no fr o w a 1 1 dc o l u m nu s i n ge q u i v a l e n c er e l a t i o na 1 1 dt h en a n 鹏o f 行e q u e mi t e m s e t s a tl a s ts c a i l t 1 1 er e d u c t e dd a t am 枷x ，g e tt h em a x i m a l 仔e q u e n ti t e m s e td i r e c t l yw i t h o u tc a n d i d a t e i t e m s e t s ，m o r e o v e rg e tt h ea s s o c i a t i o n1 1 1 1 e s i ti sp r o v e dt h a te c - a m m aa l g o r i t h mc 锄r e d u c em ec o m p l e x 毋0 nt i i i l ea n d r o o me 舵c t i v e l y - t h ee 衔c i e n c yi so v e r6 v et i l i l e st h a l la p r i o r ia l g o r i t w h e nt h e 第lv 页河南大学研究生硕士学位论文 五r e q u e n ti t e m s e t sd i m e n s i o nki sg r e a t e rt h a n2 8 w ei n i t i a l l ya p p l i e dt ot h er e s u l t so f r e s e a r c ho nm e m a n a g e m e n to fp e r s o l l l l e la r c h i v e s ，a i l da c h i e v e db e t t e rr e s u l t s t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： 1 ) u t i l i z i n g t h er e l a t i o no f e q u i v a l e n c ec l a s st or e d l l c et h et r a l l s a c t i o ns e t s 2 ) p 眦i i l gf o n a r dt h ec o n c 印to fi t e ms i i l l i l h d ed e g r e et of i n da l lm o s t 舶q u e n t i t e m s e t sd i r e c t l yw h i t h o u tc a n d i d a t ei t e m s e t s 3 ) a p p l y i l l gt l l ee c a m m a t om i l l ea r c h i v e d a t a b a s ea i l da c h i e v eb e t t e rr e s u l t s k e yw o r d s ： a s s o c i a t i o n1 1 l l e s ；e q u i v a l e n c ec l a s s ；i t e ms i m i l i t u d ed e 伊e e ；d a t am i n i l l g 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研无的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢酌地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学住论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名： 2 0d 学位论文指导教师签名： 王呜够 2 0年月 日 河南大学研究生硕士学位论文第1 页 第1 章绪论 2 l 世纪是以知识经济和信息时代为主要标志的世纪，随着信息技术的高速发 展，在商业管理、政府部门、学校、科学研究和工程开发等领域，应用了数以百 万计的数据库，其数据库应用的规模、范围和深度不断扩大，从而产生了大规模 的数据，这些数据在给人们带来方便的同时也带来了一个严重的问题：数据丰富 而知识贫乏。如何从这些巨大的数据资源中获取有用的、对决策有潜在价值的知 识，并且利用这些知识来指导实际工作，已成为各企事业单位在信息时代是否能 快速发展的决定性因素【i 】。 二十世纪八十年代末兴起的数据挖掘( d a t am i n i n g ，d m ) 技术为这一问题的解 决开辟了一条道路。数据挖掘是指从大量数据中挖掘出隐含的、先前未知的、对 决策有潜在价值的知识和规则的高级处理过程。它不仅是面向特定数据库的简单 检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合 和推理，以试图发现事件间的相互联系，指导实际问题的求解，甚至利用己有的 数据对未来的活动进行预测。例如，超市的经营者利用数据挖掘技术对销售信息 进行挖掘，可以发现商品销售的捆绑关系，从而把经常被同时购买的商品放在一 起，以增加销售等。这样就把人们对数据的应用，从低层次的查询统计操作，提 高到了为各级经营决策者提供决策辅助的层面上来。 在数据挖掘领域，关联规则是最常见的知识表示方法之一，而在具体的应用 中关联规则挖掘算法的效率问题，历来又是数据挖掘研究的重要问题，因此，本 论文以“河南大学人事档案管理信息系统”为支撑，以关联规则挖掘算法作为理 论研究的出发点和立足点，对关联规则挖掘技术在档案管理信息系统中的应用进 行了探讨和研究。需要指出的是本论文中所有的数据均为测试数据，不涉及人事 档案机密信息。 1 1 课题背景 本课题是在河南大学档案馆全面进行数字化档案工程的环境下提出的，这次 河南大学干部人事档案的数字化管理过程，是要在实现档案低层次的数字化管理、 保存、异地查询、核对及简单的统计的基础上，充分利用这些档案中宝贵的原始 数据及档案使用过程中产生的数据进行综合的统计、分析和推理，对未来的活动 第2 页河南大学研究生硕士学位论文 进行预测，为建设一流的师资队伍及提高学校档管理水平提供决策支持。例如， 通过对教科研人员身体状况的分析，找出部分教科研人员身体健康欠佳的原因， 学校据此制定相应的政策来提高教科研人员的身体素质，使他们以一个健康的身 体全身心地投入到工作中去；通过对学校人才流动情况的分析，能够发现调入人 员与毕业院校、调出人员与职称、调出时间等的关系，学校据此可以制定相应的 政策以优化学缘结构及预防人才流失；通过对档案使用数据进行分析，可以将档 案与利用者之间、档案与各种实践活动之间以及档案之间的关系揭示出来，从而 在更深层次上发挥这些档案数据的信息作用等等。总之，在人事档案管理信息系 统中应用关联规则挖掘技术的意义【2 3 】主要在于： 1 ) 为管理部门提供决策辅助。 对人事档案中原始数据所隐藏的规则模式进行挖掘，找出有价值的知识， 为人事管理及学校师资队伍建设提供决策辅助。 2 ) 实现主动档案服务。 通过对档案的利用信息进行挖掘，加强与利用者沟通，依据用户需求加强 相关档案的收集、数字化和编研等工作，实现真正意义上的主动提供档案利用服 务。 3 ) 加强档案实体保护。 通过对档案的利用信息进行挖掘，可以了解档案利用者与档案实体安全之 间的关系，加强档案实体安全的保护。如甲类用户经常查借乙和丙类档案，而当 这类用户提出要查借丁类档案时，应注意有意识地加强监督，保护乙和丙类档案 的安全。 4 ) 改善馆藏，降低档案的收集、保管成本。 通过对档案的利用信息进行挖掘，可以了解各单位档案形成特点和规律， 发现档案收集工作的重点，改善馆藏，降低档案的收集、保管成本。 5 ) 促进高校档案管理的专业化、现代化、具备人事管理的辅助决策能力，使 高校的人事档案管理工作更上一个台阶。 本项目2 0 0 7 年7 月，通过了省级鉴定。 1 2 国内外研究现状 在人事档案管理信息系统中引入关联规则挖掘技术能为档案管理者提供高级 河南大学研究生硕士学位论文第3 页 的数据分析手段，提高档案管理水平及为人事管理部门提供决策辅助支持等，以 下从档案管理和关联规则挖掘技术两个方面来讨论其研究的现状。 1 2 1 档案管理研究现状 档案是指过去和现在的国家机构、社会组织以及个人从事政治、军事、经济、 科学、技术、文化、宗教等活动直接形成的对国家和社会有保存价值的各种文字、 图表、声像等不同形式的历史记录【4 】。二十世纪中后期计算机技术的成熟和发展， 为档案管理提供一种全新的技术手段，使档案作为一种信息逐步在信息时代崭露 头角。美国、加拿大、澳大利亚等经济较发达的国家和地区在二十世纪七十年代 开展了档案计算机管理工作，我国的档案部门也在二十世纪八十年代开始利用计 算机管理档案 5 1 。目前，国内各类档案管理系统己在档案部门被广泛应用，主要从 事对档案资料的数字化存储、检索、编目、利用登记、简单统计等工作。 ，在二十多年的计算机档案管理过程中，各个档案部门形成了大量的数字化信 息，其中既有档案目录信息、档案原文信息，又有档案利用、统计等方面的信息。 根据我国档案馆网的规划布局，各档案馆管理、保存的档案以时间、地域和行业 进行划分，因而馆藏档案绝大部分是不重复的。目前，保守地估计在各个档案部 门存储在计算机中的档案目录数据库多达1 0 亿条，约1 0 0 t b 的数据量。“十五期 间档案馆成为改革开放和现代化建设提供档案信息服务的中心，国家档案局己确 定深圳档案馆为“数字化档案馆系统”工程的第一个试点馆。随着数字化档案馆 建设工作的展开，数字化的档案信息将成倍增涨，而现有档案计算机管理系统只 能对这些信息进行检索和简单的统计分析，缺乏高级数据分析手段，远远不能满 足档案管理工作和档案利用工作的要求，也使得这些档案信息在数字化后不能被 充分利用，造成了大量人力和物力的浪费1 2 j 。 1 2 2 关联规则挖掘研究现状 关联规则作为重要的知识表示方法之一，其挖掘过程能够从数字化档案数据 中挖掘有潜在价值的知识和规则，从而为档案管理提供高级的数据分析手段。最 早开展关联规则挖掘研究的是美国i b ma l m a d e nr e s e a r c hc e n t e r 的a 伊a w a l r 领导 的研究组，他们在1 9 9 3 年给出了一个称为a i s 的算法【6 】，并于1 9 9 4 年提出了挖掘关 联规则的经典算法a p r i o r i 算法7 1 及其改进算法a p r i o r i t i d 【引。后来有不少学者对关联 第4 页河南大学研究生硕士学位论文 规则问题进行了大量的研究。提出了许多a p r i o r i 算法的变形，例如，引入h a s h 方 法、划分技术、随机采样、动态项集计数技术等，旨在提高算法挖掘规则的效率， 但这些算法都不能避免a p r i o r i 系列算法固有的缺陷，即需要多次重复扫描数据库， 而且可能产生大量的侯选项集。 1 9 9 8 年，r 0 b e n o 和b a y a r d o 利用自底向上搜索和项集排序的方法建立了一种挖 掘长型频繁项集的m a x m i n e r 算法【9 】，m a x m i i l e r 算法提出了“向前看 的剪枝策 略，以尽可能早地剪枝无用的候选项集。通常，这种剪枝技术能够有效地缩小算 法索空间。除此之外，m a x m i i l e r 算法还采用了一种启发式重新排序的技术来增加 超集剪枝效果。但是，m a 】( m i n e r 算法使用水平数据库格式和宽度优先( b r e a d t hf i r s t ) 的搜索策略，可能需要多次扫描数据库，并且会产生许多无用的候选项集，带来 代价昂贵的i o 开销以及计算开销。 l i n 和k e d e m 提出了一种双向钳形搜索p i n c e r - s e a r c h 算法【1 0 1 ，利用自底向上搜 索产生的非频繁项集来约束和修剪自顶向下方向的最大候选频繁项集，能够大大 减小扫描数据库的次数。但是，其候选k 项集c k 的生成方法类似于a p r i o r i 算法的方 法，在数据量非常大时，不可避免地将产生“组合爆炸 问题，而且其生成算法 可能会遗漏某些频繁项集，为此，还需要一个“恢复”程序来生成遗漏的项集， 增加了额外的计算量。p i n c e 卜s e a r c h 算法需要维护一个最大频繁模式的超集最大候 选集，其代价通常也是很高的。 2 0 0 0 年j i a w e ih a i l 等人提出了一种不产生候选项集的f p 增长算法【1 1 】，利用扩 展前缀树这种数据结构存储经过压缩的频繁项集关键信息，虽然不需要生成频繁 候选项集且只需要扫描数据库两次，但如果长型项集的数量很多，并且如果由原 数据库得到的f p t r e e 的分支很多且分支很长时，该算法将需要构造出数量巨大的 条件f p 仃e e ，费时且占用大量空间，并且采用递归算法本身效率也较低。 因为最大频繁项集隐含了所有的频繁项集【l 】，所以有很多学者提出了直接挖掘 最大频繁项集的算法，如g u i l o p u l o s 等人提出的随机算法使用了垂直位向量的数据 结构来表示事务数据库，但它无法保证发现所有的最大频繁项集；m a f i a 算法是 b u r d i c k 等人提出来的最大频繁项集挖掘算法，但该算法仍需要多次重复扫描数据 库；d h p 算法利用h a s h 方法来减少2 项集的产生，而且使用剪枝技术来修剪事务数 据库，但构造h a s h 表的开销较大，而且为了剪裁数据库，要扫描数据库中的每个 事务以确定项集在事务中包括那些候选项目；d l g 算法构造关联图来挖掘频繁项 河南大学研究生硕士学位论文第5 页 集，不用生成候选2 项集，且需扫描事务数据库一次，但构造关联图的代价较高且 不易实现。挖掘关联规则的挑战性在于要挖掘的数据量很大，算法的效率是关键， 因此有必要研究出占用内存小、i 0 操作少、执行速度快的高效算法 1 2 3 存在的问题和主要研究的内容 根据以上分析，目前关联规则挖掘算法的主要问题归纳为以下几点： 1 ) 要多次扫描数据库。 2 ) 在关联规则挖掘过程中产生的侯选项集数量巨大。 3 ) 没有考虑事务之间的相关性。 。针对以上问题，本文提出了e c a m m a 算法，它不需要产生候选项集且只需扫 描数据库一次，利用数据矩阵存储事务集，矩阵占用内存小且实现容易，考虑到 事务之间的相关性，使用事务间的等价关系和频繁项集的性质进行矩阵的行列约 简，之后利用项目相似度直接求得最大频繁项目集，使得关联规则挖掘的效率得 到很大地提高。 而在档案管理领域主要存在的问题是缺乏高级数据分析手段，隐藏在档案数 据中的宝贵信息不能被充分利用。 虽然数据挖掘技术在许多行业都得到了巨大的发展和应用，但是在人事档案 管理领域，无论是国际上还是国内，都没有较有影响的、成功的数据挖掘系统。 在对中国期刊全文数据库1 9 9 0 年至2 0 0 7 年共2 9 4 5 4 7 5 4 篇文献( 2 0 0 7 年9 月2 1 日) 的题 录数据库查询中，在标题中出现“数据挖掘 或“知识发现”的6 0 6 8 篇，在主题 词中出现“数据挖掘 或“知识发现的1 8 9 0 8 篇，在标题中出现“档案管理”的 4 1 4 6 3 篇，两者均出现的为2 篇( 检索时间：2 0 0 7 年9 月2 1 日，仅这两篇文章也仅处于 研究阶段) 。这从一定程度上反映出数据挖掘技术在档案管理系统中的应用状况。 造成这种状况的原因主要是： 1 ) 缺乏国内外相关的范例和成功应用。目前应用的所有数据挖掘软件都是来 自其它行业，由于行业上的差异，可借鉴程度不高。 2 ) 档案界的计算机管理系统都是以检索为主要应用的事务型应用系统，原有 的档案数据库无论是从著录的格式还是从数据的质量、数量方面看，都不适用于 进行关联规则挖掘工作。 3 ) 现有的关联规则挖掘算法有其自身的不足，并且不能体现档案数据的特殊 第6 页河南大学研究生硕士学位论文 性，直接应用于档案管理系统中，效率较低。 对此，本文通过广泛的调研来发现关联规则挖掘与档案管理工作和人事管理 工作决策之间的联系，并据此设计了相关的数据库，规范录入的数据和格式，然 后根据数据挖掘的步骤，设计并实现了关联规则挖掘功能模块，模块中利用 e c a m m a 算法来解决常见关联规则挖掘算法进行档案数据挖掘效率低下的问题， 最后把该模块集成到河南大学档案管理信息系统之中，从而使档案管理具备了高 级数据分析的能力，为档案管理及学校师资队伍建设提供决策辅助，这也为关联 规则挖掘技术在档案管理信息系统中的应用提供了一种有效的设计思想。 1 3 论文结构 本文的主要研究内容是提出一种适合于人事档案数据库的关联规则挖掘高效 算法，并将该算法应用于河南大学档案管理信息系统中，从而促进河南大学档案 管理的现代化，并为管理部门的人事决策和师资队伍建设提供决策辅助支持。本 文内容组织如下： 第一章介绍了国内外档案管理及关联规则挖掘技术的研究现状，并分析了关 联规则挖掘技术在档案管理领域没有被充分利用的原因，指出了本文研究的主要 内容。 第二章介绍了关联规则挖掘的部分理论基础，包括关联规则基本概念、关联 规则的分类、关联规则的挖掘过程和关联规则价值衡量的方法等内容，为第三章 分析关联规则挖掘常用算法性能的分析奠定了理论基础。 第三章介绍了关联规则挖掘的常用算法，包括a p r i o r i 算法、f pt r e e 算法、 p a r t i t i o n 算法和矩阵算法等，并分析了这些算法性能，这些算法是第四章e c a m m a 算法提出的基础。 第四章实现了e c a m m a 算法。由于最大频繁项集隐含了所有的频繁项集， e c a m m a 算法就是通过发现最大频繁项集来求得关联规则的。本章阐述了该算法 的相关理论及实现思路，并通过实验比较、分析了该算法进行档案数据关联规则 挖掘的优越性。 第五章简单介绍了基于e c a m m a 算法的河南大学档案管理信息系统的设计 及实现，重点说明了e c a m m a 算法对人事档案个人基本信息的挖掘过程。 第六章是全文的总结，对本文的主要研究工作进行简要的阐述，并探讨和展 河南大学研究生硕士学位论文第7 页 望了在未来时间内继续研究及应当完善的问题。 第8 页河南大学研究生硕士学位论文 2 1 引言 第2 章关联规则挖掘基础 关联规则挖掘就是从大量的数据中挖掘出有价值的用来描述数据项之间相互 联系的知识。自1 9 9 3 年a g r a w a l 等人提出关联规则挖掘技术以来，关联规则挖掘 便引起了信息产业界的极大关注，其主要原因是在商务管理、医疗保险、金融业、 高等院校、政府等部门数据库应用的规模、范围和深度不断扩大，从而生了大规 模的数据，并且迫切需要将这些数据转换成有用的信息和知识，把从低层次的查 询统计操作，提高到为人事部门或经营决策者提供决策辅助支持的层面上来。然 而，应用关联规则挖掘技术，必须先了解关联规则挖掘的原理和方法，所以了解 关联规则相关概念是我们下一步工作的基础。 2 2 基本概念 定义2 1 关联规则挖掘的数据集记为d ( 一般为事务数据库) d = t l ，t 2 ，t k ，t n ) ，t k = i l ，i 2 ，i m ，i p ) ，t k ( 1 ( = l ，2 ，n ) 称为事务( t r a n s a c t i o n s ) ， i m m = 1 ，2 ，p 称为项目( i t e m ) 。 定义2 2 设i = “2 ，i m 是d 中全体项同组成的集合，i 的任何子集x 称为d 中 的项目集( i t e m s e t ) ，i x f k 称为集合x 为k 项目集( k n 唧s e t ) 。设t k 和x 分别为d 中的事 务和项目集，如果x t k ，称事务t k 包含项目集x 。每一个事务都有一个惟一的标识 符，称为t i d 。 定义2 3 数据集d 中包含项目集x 的事务数称为项目集x 的支持数，记为仃。 项目集x 的支持度记为s u p p o n ( x ) ； s u p p o r t ( x ) 2 丘。l ( 或s u p p o r t ( x ) = _ ! l ) ( 2 _ 1 ) dl 口l 其中i d i 是数据集d 的事务数，若s u p p o r t ( x ) 不小于用户指定的最小支持度 ( m i n s u p p o n ) ，则称x 为频繁项目集，简称频集( 或大项目集) ，否则称x 为非频繁项目 集，简称非频集( 或小项目集) 。 河南大学研究生硕士学位论文第9 页 定理2 1 设x ，y 是数据集d 中的项目集： 1 ) 若x y ? 则s u p p o r t ( x ) s u p p o n ( y ) 。 ( 2 2 ) 2 ) 若x y ，如果x 是非频集，则y 也是非频集。 3 ) 若x y ，若y 是频集，则x 也是频集。 由上述定义可知，定理2 1 成立是显然的( 证明略) 。 定义2 4若x ，y 为项目集，且xr 、y = 矽，蕴涵式x j y 称为关联规则，x ，y 分 别称为关联规则x j y 的前提和结论。项目集x u y 的支持度称为关联规则x j y 的 支持度，记作： s u p p o n ( xjy ) 2 s u p p o r t ( xu y ) ( 2 - 3 ) 关联规则x j y 的置信度记作，c o n f i d e n c e ( x j y ) ； c o n f i d e n c e ( xjy ) ：竺堕堕垦奎娑1 o o ( 2 4 ) s u p p o r t ( 五) 通常用户根据挖掘需要指定的最小置信度记为m i n c o n f i d e n c e 。 定义2 5 若s u p p o n ( x j y ) m i n s u p p 嘣且c o n f i d e n c e ( x j y ) m i n c o n f i d e n c e ， 称关联规则x j y 为强规则，否则称关联规则x j y 为弱规则。 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在 整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说，只 有支持度和置信度均较高的关联规则才可能是用户感兴趣、有用的关联规则。 2 3 关联规则的分类 在实际的应用中，根据不同的标准，关联规则可以有以下几种分类方法【l 引。 1 ) 根据规则中所处理的值类型，关联规则可以分为布尔的和量化的。 如果规则考虑的关联是项的存在与不存在，则它是布尔关联规则。例如规则： “牙刷”= “牙膏” s u p p o 佑- 2 0 ，c o 妒沈玎c 萨6 0 】 是由购物篮分析得到的布尔关联规则。 如果规则描述的是量化的项或属性之间的关联，则它是量化关联规则。在这 种规则中，项或属性的量化值划分为区间。下面的规则： 第1o 页河南大学研究生硕士学位论文 呼“3 0 - 4 0 ”) 八i 1 1 c o m e 仪“4 2 群4 8 r ) - 6 缈“乃动删d ，甜f f d k 丁矿) 是量化关联规则的一个例子，其中，艉代表顾客的变量。 2 ) 根据规则中涉及的数据维，关联规则可以分为单维的和多维的。 如果关联规则中的项或属性每个只涉及单个谓词或维，则它是单维关联规则。 注意，“面包”= 牛奶”陋z 华矽d ，产2 0 ，c d 斫如甩c f 6 0 可以写成如下形式： 6 z 筘( x ，“面包”) = b u y s ( x ，“牛奶”) p m 印户2 0 ，c d 驴如门c p = 6 0 】 规则“面包”= 牛奶”是单维关联规则，因为它只涉及一个维b u y s 。i 如果关联规则涉及两个或多个( 不同的) 谓词或维，如维6 z 驴， f 砌p 矿护口珊口甜f d 疗和c 淞幻垅c 口f 曙d 砂，则它是多维关联规则。如规则： 昭p 仪“3 0 - 4 0 ”) 八加c d 加曰4 2 尽4 8 r ) _ 6 缈“办恸陀，d ，扰加k r 矿) 是一个多维关联规则，因为它涉及三个维呼，砌历p 和6 z 筘。 单维关联规则展示的是维内联系( 即同一个属性或维内的关联) ；而多维关联 规则展示的是维间联系( 即属性维之间的关联) 。 根据规则集所涉及的抽象层，关联规则可以分为单层的和多层的。 有些挖掘关联规则的方法可以在不同的抽象层发现规则。例如，假定挖掘的 关联规则集包含下面规则： 孵c 誓“3 0 3 4 ”) 2 6 z 鲈c 墨“，印触 妒甜f ) 孵c 誓“3 0 - 3 4 ”) 2 - 6 z 筘“刀妒“据，- ”) 在上面的两个规则中，购买的商品涉及不同的抽象层( 即“c d 所p 材f ”在比 “卸卸朋p 甜高的抽象层) 。我们称所挖掘的规则集由多层关联规则组成。反 之，如果在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含 单层关联规则。 3 ) 根据关联挖掘的各种扩充，关联挖掘可以扩充为相关分析、最大频繁模式 ( “最大模式”) 和闭频繁项集挖掘。相关分析指出相关项的存在与否；最大模式是 一个频繁模式p ，使得p 的任何真超级都不是频繁的；闭频繁项集是指项集c 是闭的， 如果不存在c 的真超集c ，使得包含c 的予模式的每个事务也包含c 。 2 4 关联规则的挖掘过程 对于给定的一个事务数据库d ，关联规则挖掘过程就是通过用户指定最小支持 度( m i n s u p p o n ) 和最小可信度( m i n c o n f i d e n c e ) 来寻找合适关联规则的过程。 河南大学研究生硕士学位论文第11 页 一般地，关联规则挖掘问题可以划分成两个子问题【6 1 ： 1 ) 发现频繁项目集 通过用户给定的m i l l s u p p 哦，寻找所有频繁项目集( f r e q u e n tn e m s e t ) 即满足 s u p p o r t 不小于m i n s u p p o n 的项目集。事实上，这些频繁项目集可能具有包含关系。 一般地，我们只关心那些不被其它频繁项目集所包含的所谓最大频繁项集 ( m a x i m a lf r e q u e n ti t e m s e t ) 的集合。这些最大频繁项集是形成关联规则的基础。 2 ) 生成关联规则 通过用户给定的m i n c o n f i d e n c e ，在每个最大频繁项目项目集中，寻找c o n f i d e n c e 不小于m i n c o n f i d e n c e 的关联规则。 第一个子问题的任务是迅速高效地找出d 中全部频集，是关联规则挖掘的中心 问题，是衡量关联规则挖掘算法的标准；第二个子问题由式( 2 1 ) 和式( 2 4 ) 可知其 求解是比较容易、直接的，目前所有的关联规则挖掘算法都是针对第一个子问题 而提出的，关联规则挖掘的基本模型如图2 1 ： 图2 - l 关联规则挖掘的基本模型 图中彳堙r 豇向聊1 算法用于挖掘频繁项目集，彳乃矿f 砌聊2 算法用于求取关联规则，聊砌s 印 表示最小支持度，所加c d 彬表示最小可信度。 算法主要考虑的问题有以下两个： 1 ) 减少i o 操作。关联规则挖掘的数据集有时可达g b 甚至t b 数量级，频繁的i o 操作必将影响关联规则的挖掘效率，减少i o 操作的方法主要是减少扫描数据集d 的次数。 2 ) 降低需要计算支持度的项目集( 常称之为候选项目集) 的数量，使其与频繁项 目集的数量接近。候选项目数量的降低可以节省为处理部分候选项目集所需的计 算时间和存储空间。 第12 页河南大学研究生硕士学位论文 2 5 关联规则价值衡量的方法 当用数据挖掘的算法得出了一些结果之后，数据挖掘系统如何知道哪些规则 对于用户来说是有用的、有价值的，这里有两个层面：用户主观的层面和系统客 观的层面【13 1 。 2 5 1 系统客观层面 很多的算法都使用“支持度可信度”的框架。这样的结构有时会产生一些错 误的结果。看如下的一个例子： 例2 1 假设一个提供早餐的零售商调查了4 0 0 0 名学生在早晨进行什么运动，得 到的结果是2 2 0 0 名学生打篮球，2 7 5 0 名学生晨跑，1 8 0 0 名学生打篮球、晨跑。那 么如果设m i n s u p 为4 0 ，m i n c o n f 为6 0 ，我们可以得到如下的关联规则： 打篮球j 晨跑 这条规则，其实是错误的，因为晨跑的学生的比例是6 8 ，甚至大于6 0 。然 而打篮球和晨跑是否一定关联的，即当我们考虑如下的关联时： 打篮球( 不) 晨跑 虽然这条规则的支持度和可信度都比那条蕴涵正向关联的规则“打篮球j 晨 跑 低，但是它更精确。然而，如果把支持度和可信度设得足够低，那么将得到 两条矛盾的规则。但另一方面，如果把那些参数设得足够高，则只能得到不精确 的规则。总之，没有一对支持度和可信度的组合可以产生完全正确的关联。 于是引入了兴趣度，用来修剪无趣的规则，即避免生成“错觉 的关联规则。 一般一条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强度之 比，然而在许多应用中已发现，只要人们仍把支持度作为最初的项集产生的主要 决定因素，那么要是把支持度设得足够的低以使不丢失任何有意义的规则，或者 冒丢失一些重要规则的风险；对前一种情形计算效率是个问题，而后一种情形则 有可能丢失从用户观点来看是有意义的规则的问题。 把兴趣度作为修剪无价值规则的工具，现在已有许多其他的工作来重新认识 项集，如b 血等考虑的相关规则。讨论了蕴涵规则( i m p l i c a t i o nm l e ) ，规则的蕴涵强 度在【0 ，叫之间变化，其中蕴涵强度为1 表示完全无关的规则，表示完备的规则， 如果蕴涵强度大于1 则表示更大的期望存在性。 河南大学研究生硕士学位论文第13 页 另一个度量值“收集强度( c o l l e c t i v es 打e n g t h ) 在文献【1 4 中被定义，他们 设想使用“大于期望值来发现有意义的关联规则。项集的“收集强度”是 0 ，叫 之间的一个数值，其中o 表示完备的否定相关性，而值表示完备的正相关性。详 细的讨论可以在文献【1 4 中找到。 2 5 2 用户主观层面 上面的讨论只是基于系统方面的考虑，但是一个规则的有用与否最终取决于 用户的感觉。只有用户可以决定规则的有效性、可行性。所以应该将用户的需求 和系统更加紧密的结合起来。 可以采用一种基于约束的挖掘。具体约束的内容可以有： 1 ) 数据约束。用户可以指定对哪些数据进行挖掘，而不一定是全部的数据。 2 ) 指定挖掘的维和层次。用户可以指定对数据在哪些维以及在这些维上哪些 层次迸行挖掘。 3 ) 规则约束。可以指定哪些类型的规则是我们所需要的。引入一个模板的概 念，用户使用它来确定哪些规则是令人感兴趣的而哪些则不然：如果一条规则匹 配一个包含的模板，则是令人感兴趣的，然而如果一条规则匹配一个限制的模板， 则被认为是缺乏兴趣的。 其中有些条件可以和算法紧密的结合，从而即提高了效率，又使挖掘的目的 更加的明确化了。其他的方法还有： k l e i n b e r g 等人的工作是希望建立一套理论来判断所得模式的价值，他们认为 这个问题仅能在微观经济学框架里被解决，他们的模型提出了一个可以发展的方 向。他们引入并研究了一个新的优化问题分段问题，这个框架包含了一些标 准的组合分类问题。这个模型根据基本的目标函数，对“被挖掘的数据 的价值 提供一个特殊的算法的视角，显示了从这方面导出的具体的优化问题的广泛的应 用领域。 k 0 m 等就利用猜测误差( 这里他们使用“均方根”来定义) 来作为一些从给定的 数据集中所发现的规则的“好处”的度量，他们所定义的比例规则就是如下的规 则： 顾客大多数分别花费1 ：2 ：5 的钱在“面包：“牛奶 ：“奶油”上。 通过确定未知的( 等价的，被隐藏的，丢失的) 值，比例规则可以用来作决策支 第14 页河南大学研究生硕士学位论文 持。如果数据点线性地相关的话，那么比例规则能达到更紧凑的描述，即关联规 则更好地描述了相关性。 2 6 小结 本章在提出关联规则基本概念的基础上，首先对关联规则的种类进行了分析、 归纳和总结；然后，分析了关联规则的挖掘过程及设计关联规则挖掘算法应主要 考虑的问题，同时给出了关联规则挖掘的基本模型；最后，归纳出关联规则