（计算机应用技术专业论文）布尔关联规则挖掘的研究及在股票价格分析中的应用.pdf

论文题目：布尔关联规则挖掘的研究及在股票价格分析中的应用 专业：计算机应用技术 硕士生：孔祥纯 指导教师：龙熙华 摘要 ( 签名) 盈盔越 ( 签名) 础嵫 关联规则挖掘经过十几年的发展，取得了丰硕成果。其中的布尔关联规则挖掘是关联 规则挖掘中研究比较多的一种。通过数据离散化和符号化，把时间序列数据转换为布尔 型数据，从而使时阅序列数据成为适合布尔关联规则挖掘的数据源。股票价格是典型的 时间序列数据。随着我国股票市场进入新的发展时期，对股票市场的分析对我国的经济 发展有着更加重要的意义。本文对布尔关联规则算法进行了研究，把研究成果应用在股 票价格分析中研究的工作、成果主要体现在以下三个方面： 在i o d l g 算法的基础上生成一种改进算法：d l g * 算法。通过对i o d l g 算法的搜 索策略进行改进，将i o d l g 算法与a p r i o r i 性质相结合，构造了d l g * 算法。通过实验 证明d l g * 算法比i o d l g 算法更适合长频繁项集的挖掘。 在d l g 算法、d m f i 算法、m a f i a 算法的基础上生成一种改进算法：v m - d l g 算 法。将d l g 算法的存储策略、m a f i a 算法深度优先的搜索策略和d m f i 算法的宽度优 先的搜索策略相结合，构造了m - d l g 算法。通过实验证明m - d l g 算法比m a f i a 算法 和d m f i 算法在运行效率上有了一定的提高。 把布尔关联规则挖掘应用在股票价格分析中。针对股票价格特点，开发了一个简单的 股票价格分析系统原型，工作集中在数据预处理和算法实现上。以实际的股票价格数据 进行了实验，实验表明该系统原型对股票价格分析是有效的。 关键词：关联规则；时间序列；最大频繁项集；股票价格分析 研究类型：应用研究 s u b j e c t ：b o o l e a nm i n i n ga s s o c i a t i o nr u l e sa n di t sa p p l i c a t i o ni ns t o c k p r i c ea n a l y s i s s p e c i a l t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：k o n gx i a n g c h u n ( s i g n a t u r e ) i n s t r u c t o r ：l o n gx i h u a ( s i g n a t u r e a b s t r a c t w i t had e c a d eo f d e v e l o p m e n t , m i n i 】n ga s s o c i a t i o nr u l e sh a v em a d em u c ha c h i e v e m e n t a m o n 8t h e s er u l e s ，b o o l e a n 【i n i n ga s s o c i a t i o nr u l e sa r cm o 糟f r e q u e n a ys t u d i e dt h a n o t h e l 瞎t h r o u g ht h ed i s c r e t ea n ds y m b o l i z e dt e c h n o l o g yn u m e r i c a ld a t ac a nb ec o n v e r t e dt o b o o l e a nd a t a ，m a k i n gt i m es e r i e sd a t at h em a i nd a t as o u i c eo f m i n i n ga s s o c i a t i o nr u l e s s t o c kp r i c ei sat y p i c a lt i m e - s e r i e sd a t a a sc h i n a ss t o c km a r k e te n t e r san f we r ao f d e v e l o p m e n t , t h ea n a l y s i so ft h es t o c km a r k e ti so fg r e a ts i g n i f i c a n c et oc h i n a se c o n o m i c d e v e l o p m e n t t h i sp a p e rc o n d u c t e das t u d yo nm i n i n ga s s o c i a t i o nr u l e s , a p # y i n gr e s e a r c h r e s u l t si nt h ea n a l y s i so fs t o c kp r i c e t h ee f f o r ta n da c h i e v e m e n ti sm a i n l ym a n i f e s t e di nt h e f o l l o w i n gt h r e ea s p 魄 1 d l g * a l g o r i t h m , 觚i m p r o v e da l g o r i t h m , i sg e n e r a t e do nt h eb a s i so fi o d l g a l g o r i t h ma n d t h ed l g a l g o r i t h m ni sc o n s u u e t 司t h r o u g ht h ei m p r o v e m e n to f t h e 辩缸c h i n g s t r a t e g yo f t h ei o d l ga l g o r i t h ma n dt h ec o m b i n a t i o no f i o d l ga l g o r i t h ma n dt h en a t u r eo f a 皿o r i e x p e r i m e n t sh a v ep r o v e dt h a td l ga l g o r i t h mh a sn 均a d v a n t a g e st h a ni o d l g a l g o r i t h mi nl o n gf i e q u e n c yi t e m s e tm i n i n g 2 m - d l ga l g o r i t h m , a n o t h e rn f wa l g o r i t h m , i sg e n e r a t e d 丘o md m f ia l g o r i t h m , m a f i aa l g o r i t h ma n dt h ed l ga l g o r i t h m i ti sc r e a t e dt h r o u g ht h ec o m b i n a t i o no fd l g s t o r a g es t r a t e g i e s , t h ed e p t h - f i r s ts e a r c hs t r a t e g yo f m a f i aa l g o r i t h ma n dt h eb r e a d t h f i r s t s e a r c hs w a t e g yo fd m f i e x p e r i m e n t sh a v ep r o v e dt h a tm - d l ga l g o r i t h mh a sb e e ng r e a t l y i m p r o v e di np e r f o r m a n c et h a nm a f i aa l g o r i t h ma n dd m f ia l g o r i t h m 3 b o o l e a nm 缸n ga s s o c i a t i o nr u l e sa r ea p p l i e di nt h ea n a l y s i so fs t o c kp r i c e a s i m p l i f i e ds t o c kp d a n a l y s i sp r o t o t y p ei s c r e a t e db a s e do nt h ep r e v i o u sa c h i e v e m e n t s , f o c u s i n go nd a t ap r e p r o c e s s i n ga n da l g o r i t h mr e a l i z a t i o n e x p e r i m e n t sh a v ep r o v e dt h a tt h i s p r o t o t y p e i s q u i t e e f f e c t i v e i n t h e a n a l y s i s o f s t o c k p r i c e k e yw o r d s ：m i n i n g a s s o c i a t i o nr u l e sb o o l e a nm i n i n ga s s o c i a t i o nr u l e s d l g a l g o r i t h m m - d l g a l g o r i t h m s t o c kp r i c ea n a l y s i sp r o t o t y p e 妻斜技太肇 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名矧廖珲磋月期：7 ，年印曰p 目 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名j ，；心力军夕n 指导教师签名：，t 乏坠隼 f 7 年z 月罗6 日 i 绪论 1 i 选题背景及研究意义 l 绪论 在人类社会的不断发展过程中，人类以不同的方式存储着大量的数据。目前，数据 量达到了人们已经无法想象的地步，使现有发现知识的方法已经显得力不从心。随着数 据库、信息技术、计算机技术的发展，出现了数据挖掘技术。这种技术专门针对大量数 据进行分析处理，从而提取数据中的有用知识。经过二十年的发展，数据挖掘研究内容 变得十分丰富，其中关联规则挖掘是数据挖掘研究的方向之一。它是数据挖掘从技术角 度划分的一种数据挖掘l l w 。 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不 停地收集和存储，许多人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量 事务记录中发现有趣的关联关系，可以帮助许多决策的制定，如交叉购物、贱卖分析、 股票价格的预测等【4 】关联规则按不同的角度分为：单维与多维、单层与多层、布尔数 据与数值数据、兴趣度、最大频繁项集等关联规则挖掘布尔关联规则挖掘做为一种定 性分析，由于其研究的成果相对易于转化为生产力，所以研究及应用的发展比较快。其 主要方法分为有候选项集和无候选项集。无候选项集是以树型的逻辑结构把数据库事务 一次全部放入到内存中，但随着数据量的增大，遍历树的开销削弱了它的优点。随着计 算机技术的发展，可以把数据库事务以位存储的方式一次全部存储在内存当中，使有候 选项集的算法得到了优化。最大频繁项集挖掘是关联规则挖掘研究的子问题利用 恕 r i 砸性质，采用最大频繁项集挖掘不仅扩展了关联规则挖掘的应用范围，并且提高了 挖掘的效率。所以本文基于有候选项集的方法，在挖掘频繁项集及最大频繁项集两个方 面展开研究。 在现实世界中，数据有很大一部分是与时间相联系的，一部分以等时间间隔测得的 数据被称为时间序列数据【l i 随着离散技术、符号化技术的出现，以及时间序列数据对 定性分析的需求，使关联规则挖掘应用在时间序列数据成为一种必然。随着经济社会的 发展，股票市场早已成为西方经济发达国家经济的晴雨表。处于社会主义市场经济下的 我国股票市场发展才刚刚开始。随着股票市场改革的深入，股票市场进入到了一种良性 发展状态中，这为股票价格的分析打下了良好的基础。股票价格数据是一种时问序列数 据，并且数据量十分庞大，这恰适合作为数据挖掘的数据源，所以本文开发了一种时间 序列关联规则挖掘的系统原型用于股票价格的分析。本文的系统原型的主要工作：一是 把d l g * 算法应用在原型中，二是针对股票价格数据的特点进行针对性的数据预处理。 西安科技大学硕士学位论文 1 2 关联规则挖掘的研究现状 自从a g r a w a lr 等人提出了关联规则挖掘问题后，该方向上的研究至今有了很大的 发展。首先要提到的是a p r i o r i 算法【5 期，它是1 9 9 4 年a g r a w a l 等人提出来的一种关联 规则算法。a p r i 谢算法是基于有候选项集的算法，有很多技术应用在此算法上生成了不 同的改进算法。例如：利用哈希表技术、基于划分技术、抽样技术、动态项集等，这些 改进算法在性能上有了很大的提高。但是，a p r i o r i 算法有两个很大的缺陷：一是要多次 扫描数据库，二是产生很大的候选项集。因此在2 0 0 0 年j i a w e ih a r t 等人提出f p _ g r o w t h 算法【刀，这种算法基于不产生候选项集的方法来进行挖掘。这种算法只需扫描二次数据 库，把数据库的事务数据以树的逻辑结构一次全部存储在内存当中，从而不需要产生候 选项集。这种算法虽然克服了a p r i o r i 算法的缺陷，但是这种用树的逻辑结构来存储数 据本身消耗的内存就比较大，当短项集比较多时会产生大量的分枝，占用的内存空间就 更大了；当长项集比较多时，由于算法本身以递归的方式遍历树也会增加内存的占用。 所以该算法扩展性不是很好。有些学者利用a p r i o r 性质，直接挖掘最大频繁项集从而提 高效率。这方面的算法有：m a x - m i n e 算法 s l 、p i n c e r - s e a r c h 算法1 9 、m a f i a 算法l l 川、 d m f i 算法【1 1 、d m f i a 算法【1 2 1 等。m a x - m i n e 算法使用水平数据库格式和宽度优先的搜 索策略，可能需要多次扫描数据库，并且会产生许多无用的候选项目集；p i n c e r - s e a r c h 算法需要维护一个最大频繁项集的超集最大候选项集，其代价通常也是很高的；m a f i a 算法是b u r d i c k 等人提出的最大频繁项集挖掘算法，该算法仍需要多次重复扫描数据库； d m f i 算法也需要多次重复扫描数据库；d m f i a 算法只需扫描数据库两次，但需要生成 数量庞大的最大频繁候选项集。为了减少内存的占用量、提高效率，有些学者提出了用 位矩阵一次存储数据库事务的算法，相关算法有d l c j ”i 、i o d l c 1 4 1 等。d l g 算法有效 的提高了挖掘的效率，但此算法是在存储上进行优化，没有充分考虑到关联图的特性。 曹馨宇等人提出了i o d l g 算法，该算法利用关联图的特性减少了候选项集的大小。但 该算法是利用项集中的两点来进行考察，当长项集比较多时必然带来一定的冗余。 1 3 本文研究内容及章节安排 本文首先对关联规则挖掘算法进行了研究，然后把研究成果应用在时间序列挖掘问 题上。研究的内容如下： ( 1 ) 在i o d l g 算法的基础上生成一种改进算法：d l g * 算法。通过对i o d l g 算法的 搜索策略进行改进，将i o d l g 算法与a p r i o r i 性质相结合，构造了d l g * 算法。通过实 验证明d l g * 算法比i o d l l 3 算法更适合长频繁项集的挖掘。 ( 2 ) 在d l g 算法、d m f i 算法、m a f i a 算法的基础上生成一种改进算法：m - d l g 算法。将d l g 算法的存储策略、m a f i a 算法深度优先的搜索策略和d m f i 算法的宽度 2 1 绪论 优先的搜索策略相结合，构造了m - d l g 算法。通过实验证明m - d l g 算法比m a f i a 算 法和d m f i 算法在性能上有了定的改善。 ( 3 ) 把布尔关联规则挖掘应用在股票价格分析中。在分析了已有成果的基础上1 1 5 ，1 6 】， 生成了一个简单的股票价格分析系统原型，主要工作集中在数据预处理和算法实现上。 通过实验证明该系统原型对股票价格分析是有效的 为完成上述工作，本文章节安排如下： 第一章绪论。本章主要介绍了选题的背景、研究现状及研究意义。 第二章关联规则挖掘。本章介绍了关联规则挖掘相关知识及与本文相关的算法。 第三章基于关联图的挖掘频繁项集的d l g * 算法。本章对i o d l g 算法进行了改进、 在利用实际股票价格数据进行实验的基础上，对比了d l g 算法、d l g * 算法和i o d l g 算法的性能。 第四章基于位存储的挖掘最大频繁项集的m - d l g 算法。本章将d l g 算法、d m f i 算法、m a f i a 算法结合，构造了m - d l g 算法。在利用实际股票价格数据进行实验的基 础上，对比了m a f i a 算法、d m f i 算法和m d l g 算法的性能。 第五章关联规则挖掘在股票价格分析中的应用。本章介绍了有关时间序列的知识； 在对时间序列的关联分析的基础上，开发了简单的股票价格分析系统原型，利用实际股 票价格数据进行实验并对结果进行了分析。 第六章结论。总结了全文并展望了下一阶段的工作。 西安科技大学硕士学位论文 2 1 关联规则挖掘概述 2 关联规则挖掘 2 1 1 关联规则挖掘的相关概念 关联规则挖掘作为数据挖掘的一个重要的研究方向，有其独特的特点：首先，由于 关联规则的基本模式比较简单，所以更容易被人理解并加以应用；其次，关联规则的蕴 涵模式与实际中的事物问的联系更具有相似性，更容易从理论向实际转化。因为本文主 要研究的是关联规则挖掘，所以本小节就关联规则挖掘的一般性概念【4 】加以介绍： 定义2 1 项与项集：数据库中的事务或其它数据源的数据的属性，称作项。而项的 集合称为项集( i t c m s c t ) 。一般用i 表示项的集合，i f i ，i 2 , i m ，其中m 为事务包含的项 的数目。包含k 个项的项集称为k - 项集。例如：集合 p r i c e , a m o u n t 是一个2 项集。一 般用d 来表示与任务相关的数据库事务的集合，而用t 表示单个事务。t 是项的集合， 既t e l 。为了区分每个事务，用一个标识符来表示，记作t i d ，即t = ( t i d ，d 定义2 2 关联规则：蕴涵式a b 是关联规则的表现形式。其中a c i ，b c i ，并且 a n b f f i a ，a - - - a i n a 2 n n a i ，b = b t nb 2 n nb j ，a i e i ，b ! i i 。一般a 称作前件， b 称作后件。整个蕴涵式表示出现a 会出现b 。 定义2 - 3 兴趣度：用户对在数据挖掘过程中产生的某些模式感兴趣的程度称为兴趣 度。由于在挖掘过程中会出现大量的项集，而对用户有用的( 感兴趣的) 只是一部分。用 兴趣度可以有效把挖掘出的大量项集控制在用户有用的范围内。兴趣度度量是评估模式 的简洁性、确定性、实用性和新颖性。在关联规则中实用性表现为支持度，确定性表现 为置信度。 定义2 4 支持度：在d 中，同时出现a 和b 的事务数占d 的百分比称作支持度s 记作s u p ( a = b ) ，即公式化为： s u p p ( a j b 户p ( a ub )( 2 1 ) 其中a c i ，b c i ，a u b 表示同时出现a 和b 的事件。注意：a 并b 的事件在支 持度概念下表示的是集合论中的交集事件。倒如：股市中钢铁板块与煤炭板块的综合价 格指数同时上涨的可能性是6 5 ，即s l l p ( a j b 户6 5 ，其中a = v a l u e ( d a y , 钢铁板块综 合价格指数) ，b = v a l u e a y , 煤炭板块综合价格指数) 。 定义2 5 置信度：在d 中，包含a 和b 的事务数与包含a 事务数的比称作支持度c 记作c o n f ( ab ) ，即公式化为： c o n f ( a j b ) = p ( b a ) ( 2 2 ) 2 关联规则挖掘 其中a c i ，b c i 。支持度c 实际上就是在a 出现的前提下出现b 的条件概率。例 如：在股市中钢铁板块综合价格指数上涨的前提下煤炭板块的综合价格指数上涨的可能 性是4 2 ，即c o n f ( a b ) = 4 2 ，其中a = v a l u e ( d a y ，钢铁板块综合价格指数) ，b = v a l u e ( d a y ，煤炭板块综合价格指数) 。 与支持度和置信度有关的还有两个概念：最小支持度( r a i n _ s u p ) 和最小置信度 ( m i nc o n f ) 。这两个噪声阈值可以按用户的意图有效的把挖掘出的频繁项集限定在一个 可控的范围内。 定义2 6 项集的计数：在给定d 中包含特定项集i 的事务数，称作项集i 的计数。 在有的文献【2 】中把项的出现的频率称作项集的支持计数，或项集出现的频率，实际上就 是支持度等式的分予 定义2 7 频繁项集：如果项集满足最小支持度，则称作频繁项集( f i 屯q u e n ti t m s e t ) 。 如果项集的出现频率大于或等于m i n _ s u p 与d 中事务总数的乘积，则称项集满足最小支 持度。 定义2 8 强关联规则：同时满足最小支持度阈值和最小置信度阈值的关联规则称作 强关联规则。 2 1 2 关联规则的分类 ( 1 ) 根据挖掘时项集中项的性质 布尔关联规则( b o o l e a na s s o c i a t i o nr u l e ) ，如果挖掘规则时考虑的是关联规则中项 的存不存在，则称这种规则为布尔关联规则。例如： v a l u e ( 首都机场) v a l l l c ( 白云机场)( 2 3 ) 量化关联规贝i j ( q u a n t i t i a t i v ea s s o c i a t i o nr u l e ) ，如果挖掘规则时考虑的是被量化的 项之间的关联时，则称这种规则为量化关联规则。例如： 硼砌吼啦，q 万6 万 ) j v a l u e ( x )( 2 4 ) ( 2 ) 根据规则中涉及的数据的维度 单维关联规则( s i n g l e - d i m e n s i o n a la q s o 铡o nr u l e ) ，如果关联规则中的每个项只涉 及一个维，则称这样的关联规则为单维关联规则。上面的规则( 2 3 ) 是单维关联规则的一 个例子 多维关联规则( m u l d d i m e n s i o n a l 雒s o c i 砒i r u l e ) ，如果关联规则中涉及两个或多 个维时，称这样的关联规则为多维关联规则。上面的规则( 2 4 ) 是多维关联规则的一个例 子。 ( 3 ) 根据项集中的项是否涉及多个概化层 单层关联规贝1 ( s i n g l e - l e v e ra s s o c i a t i o nr u l e ) ，如果在给定的规则集中，规则不涉 及某个或某些项的多个概化层时，称这样的关联规则为单层关联规则。上面的( 2 3 ) 到( 2 4 ) 西安科技大学硕士学位论文 都是单层关联规则的例子。 多层关联规贝l j ( m u l f i l e v e la s s o c i a t i o nr u l e ) ，如果在给定的规则集中，规则涉及某 个或某些项的多个概化层时，称这样的关联规则为多维关联规则。例如： w d u e ( d a y 3 ，第二产业) j 训l 】c ( d a y 5 ，金融业) ( 2 5 ) 根据关联规则的不同相应的产生了不同的关联规则挖掘。在对关联规则挖掘扩展后 又形成了：最大频繁项集挖掘和频繁闭项集挖掘。最大频繁项集是频繁模式p ，使得p 的任何真超项集都不是频繁的。频繁闭项集是一个频繁的闭的项集，其中项集c 是闭的， 如果不存在c 的真超集c ，使得每个包含c 的事务也包含c 。使用最大频繁项集和频 繁闭项集可以有效的压缩挖掘出的频繁项集数【1 ，2 1 1 4 1 2 1 3 关联规则挖掘思想 对于数据挖掘来说，有两个客观条件：数据量庞大和有大量现有的资源和研究成果。 基于这两个客观条件产生了相关的问题： ( 1 ) 如何利用庞大的数据量? c 2 ) 现有的资源和研究成果是可用的吗? 依据以上两个问题人们提出了解决数据挖掘效率问题的思想： ( 1 ) 把庞大的数据量减少到可分析的范围，即把问题规模减小到可接受的范围来提 高挖掘效率。 ( 2 ) 事物是普遍存在联系的，有一部分资源和研究成果一定可以被用来提高挖掘的 效率。 下面就根据这两个思想列举了相关的一些挖掘方法。 ( 1 ) 产生候选项集的方法 这种方法体现在a g r a w a l 等人提出的a p r i o r i 及其改进算法中。通过产生候选项集 的方法来减少被挖掘的项集的规模，从而有效的提高挖掘效率。这种方法以宽度优先的 搜索思想( 从频繁k 项集找到频繁( 1 【+ 1 ) - 项集，直到找到的n 频繁集为空集) 循环的找到 所有的频繁项集。 ( 2 ) 不产生候选集的方法 这种方法的产生是针对产生候选项集方法中存在的一些缺点提出的。具有代表性的 算法是f p 增量算法。通过一次性把所有的信息加载到内存中，从而减少c p u 访问外部 存储器的次数以提高挖掘效率。 ( 3 ) 并行挖掘的方法【1 7 1 这种方法来源于并行操作系统。一方面可以有效的利用可用的资源达到资源的共 享；另一方面使问题的规模通过划分减小到可接受的程度。目前提出的基于并行挖掘关 联规则的算法有：a g r a w a l 等人提出的c d ( c o u n td i s t r i b u t i o n ) 、c a d ( c a n d i d a t e 6 2 关联规则挖掘 d i s t r i b u t i o n ) 、d d ( d a t ad i s t r i b u t i o n ) 、p a r k 等人提出的算法d m a ( d i s t r i b u t e dm i n i n go f a s s o c i a t i o nr u l e s ) ，虽然是基于分布式数据库的挖掘算法，但属于并行挖掘。 ( 4 ) 增量式更新的方法【1 7 1 当数据源被更新时，如何有效的利用已有的挖掘结果来进行挖掘是该方法产生的动 力。一方面利用现有的成果可以有效的节省和利用资源；另一方面利用已有成果可能会 有效的增加解决问题的效率。 ( 5 ) 基于约束的方法【1 硼 利用提出一些前提条件使问题的规模减小，并且指导挖掘向用户感性趣的方向进 行。这些约束包括： 知识类型约束：制定要挖掘的知识类型，如关联规则。 数据约束：指定任务相关的数据库事务集。 维层约束：指定所用的维和概念分层结构的层 兴趣度约束：指定规则兴趣度阈值或统计量，如关联度、置信度等。 规则约束：指定要挖掘的规则形式。例如：关联规则的前件的数量、性质等。 2 2a p r i o r i 算法及改进 在对关联规则挖掘有了概念上整体的了解后，有必要对基本算法有个清晰的认识 本文的算法改进是在有候选项集的方法的基础之上进行的改进，而a p r i o r i 算法是关联 规则中最基本的有候选项集的算法，一大部分的算法都是在其上的改进，或是利用其算 法思想。所以下面就详细的讲述这种算法。 2 2 1a p r i o r i 算法 ( 1 ) a p r i o r i 算法的思想及性质 在关联规则挖掘中最简单的关联规则方法是a p r i o r i 算法。该算法是由a g r w a l 等人 提出来的。a p r i o r i 算法是一种搜索频繁项集的基本方法。该算法运用宽度优先、逐层搜 索的方法，由低数量级的项集找到高数量级的项集。即先找出频繁1 项集的集合，该集 合记作l 1 利用频繁1 项集找到频繁2 一项集k ，由k 找到l 3 ，逐次递增直到找到频繁 项集k 项集k ，并且l k 为空集。 a 皿o r i 性质：频繁项集的所有非空子集都必然是频繁的。 ( 2 ) a p r i o r i 算法的实现 a p r i o r i 算法分为两个步骤：连接和剪枝，具体如下所述： 连接步骤：为了找l t ，通过l l 与自己连接产生候选l 【项集的集合该候选项 集的集合记作c k 。l l 和1 2 是【- l 中的项集。记号l m d 】表示l m 的第j 项为了方便计算， 假定事务或项集中的项按字典次序捧序执行连接b , i x b , b 其中l b l 的元素是可连接 7 西安科技大学项士学位论文 的，如果它们前( k - 2 ) 个项相同。即是，k l 的元素l l 和1 2 是可连接的，如果 o l 【l 】= 1 2 【1 】) a ( 1 1 1 2 1 = 1 2 1 2 ) ( 1 l k - 2 = 1 2 k - 2 ) o i k - 1 = k 。这样就有效的压缩了候选项的数目例如： 如图2 3 事务集d 的频繁2 项集的 i l ，i 3 ) ，寻找u 使得 i 3 ，u 在关联图中有边，候选的 项是i 4 和i 5 ，但v 5 o u t p u t = 1 ，v = v l 炮，v n 为g 的顶点集，顶点v i 代表 频繁l 一项集的元素i i ；e = e t , e 2 。南d 为g 的边集，m 为频繁2 - 项集元素的个数。当v l 和 v j 对应的项集 i i i j ) 是频繁2 项集的元素时，顶点v 与顶点v j 之间有边q 连通。 定义3 3 有向关联图g ： 称e i 尸锄妒是一条有向边，如果v i 作为起点，v j 作为 终点做一条边。有向边的集合记做e 则有向关联图g & 、e 定义3 4 顶点出度值和入度值：在g 中以v i 为起点的有向边v i 、p 的个数称为v i 的出度值；记作；矿( v i ) 以v i 为终点的有向边的个数称为v i 的入度，记作：d ( v i ) 其 中j - - 1 , 2 n 定义3 5 顶点的度：设v i 为d 的一个顶点，以v i 为起点和终点的有向边的条数称 为v i 的度，记作：记作d ( v i ) 。根据定义有d + ( v i 卜d ( v i ) = d “) 。 定义3 6 项的事务向量：设d ； t i , t 2 ， ，n 表示数据库的事务数；数据库的项集 i = i t i 2 , , i m ，m 表示项的个数；t 。= k 证明：设有频繁k 项集k ，组成其元素的项为 i k l ，砬，诚 ，在不引起混淆的情况 下表示为i 矿 i k l ，h 岛，址 ，并且h 属于i 。频繁2 项集对应的有向图为d = 。 在本章节中，假设d 中事务的项是有序摔列的，即l = 性质1 由 垴，心，i 娃) 所组成的2 - 项集也是频繁的 一 垴，i 也) ， k l ，i b ) ， i k l ，i 址) e l 2 v k lv 驴， m t n _ s u p 时， 把 i i 加入到频繁2 项集中 ( 3 ) 创建有向关联图g 设 i ii j ) 为频繁2 一项集的元素，则项i i 冉对应关联图 的顶点v i i 和、， j ，并且建立一条起点为v i i 终点为、，i j 的有向边。频繁2 颂集所有的元素对 应的顶点和边构成了有向关联图g 。g 可用矩阵b 的形式表示。b 的行和列都表示组成 频繁2 项集的的元素的项，并且按在数据库事务中出现的次序有序捧列。矩阵b 的元素 b i j - l 表示以为起点为终点的有项边。矩阵b 是一个上三角矩阵。这有利于压缩存 储空间 ( 4 ) 通过g 及频繁l 【项集找到频繁畔1 ) - 项集。d 的项集i = i t , i 2 ，j n 所以k k 时，与顶点 对应的项i j 才会出现在频繁o 【+ 1 ) 项集中这样就减小了候选集范围；其次，检查( k + 1 ) 项集的子集是否是频繁项集。由性质l 可知，如果( k + 1 ) 项集的任一子集不是频繁的，则 o 【+ 1 ) 项集也不可能是频繁( k + 1 ) 项集的元素。这样就进一步压缩了候选空间 ( 5 ) 生成关联规则根据给定的m i n 和 来提取d 的关联规则。_ s u p r a i nc o n f 由于产生频繁集是关联规则挖掘的主要步骤，所以本文仅就前四个步骤给出算法流 程图，如图3 1 。 输入：d 、最小支持阈值r a i ns u p ； 输出：d 中所有频繁l 【- 项集( 1 【1 ) 3 基于关联图的挖掘频繁项目集的d l g * 算法 图3 1d l g * 算法流程图 1 7 西安科技大学硕士学位论文 图3 2 确定频繁l - 项集l i 图3 3 确定频繁l - 项集k l s 3 基于关联图的挖掘频繁项目集的d l g * 算法 3 4 举例验证和实验及结果分析 ( 1 ) 举例： 现在就图3 4 所示的d 对d l g * 作一简单例证： 设m i ns u p = 3 第一步；扫描d 生成位矩阵a ( 事务向量组) ，如图3 4 1 1 d 项列表 t 一 t 1 1 2 1 2 ，l ，i j 矩阵行1 1 t t l l 3 i ，i 表示事 1 2 1 t 1 1 4 i l 1 2 1 3 ，i ，i ， 务集，列i ， 】 t 1 1 5 i l ，1 2 ( t 1 1 6 i l ，b ，1 表示项 i t 1 1 7 1 2 ，k i i 集 1 5 1 一 t 1 1 3 i i k i i ， 项表度数 t l l 9 1 2 ，k i 1 5 2 i l t 1 2 0 1 2 ，i b i ，i ， 3 1 2 ( a ) 事务集t b 4 i 4 ( d ) 度数表 b 3 白台奋珞每母岛 - - - - - - 一 v 3 图3 a 由事务集生成关联图及矩阵的过程 第二步；生成频繁2 项集。首先作a 的行的与运算，例如，对行d l 和d 2 ，使两行按 位做与运算，即d l f l d z f f i ( ( 0 f 、1 ) ，( o n o ) , 0 n 1 ) ，( 1 n 1 ) ，( 1 no ) ，( o n l ) ，( 1 n o ) ，( o n l ) ( o n