（计算机应用技术专业论文）基于序列模式的正负关联规则挖掘技术.pdf

山东轻工业学院硕十学位论文 摘要 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，应运而生了数 据挖掘技术。通过数据挖掘我们可以找到对于商业销售及生产极为有效的一些信 息，从而可以提高销售和生产效率，降低成本，取得最大的商业效益。 其中，序列模式的挖掘是一个非常活跃的分支。对企业来说，序列模式可预 测顾客的购买行为，促进销售量。比如彳鞘，这条规则是指顾客在购买了商品彳 之后，往往会接着买商品口。商家可根据这条规则制定销售策略，促进蹲个商品的 销售。然而有时还会出现以下情况，顾客在购买了商品a 之后，往往不会买商品c ， 这条规则记为a - - , c ，这就足序列模式的负关联规则。在企业制定决策时，序列 模式的负关联规则对于如何减少负面因素，最大限度的增加正面效益尤为重要。 然而目前的序列模式研究，都是形如么劫封的基于序列模式的正关联规则。 关于序列模式的负关联规则的研究尚未展开。本文分别对现有的序列模式算法和 负关联规则挖掘算法进行了研究，并利用相关性的定义，剔除其中相互矛盾的关 联规则，将两种算法相结合，应用到序列模式的挖掘中，从而可以同时挖掘出基 于序列模式的正、负关联规则。最后给出了应用实例，具体说明算法的实现过程。 关键词：数据挖掘；序列模式；关联规则；相关性；负关联规则 i i i a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n db r o a da p p l i c a t i o no f d a t a b a s e m a n a g e m e n ts y s t e m ，d a t a b a s em i n i n gw a sb o r n w ec a ng e tv e r yi m p o r t a n t i n f o r m a t i o nf o rs a l e sa n d p r o d u c t i o nt h r o u g hd a t a b a s em i n i n gi nc e r t a i np a t t e r n ，s oa st o i m p r o v es a l e sa n dp r o d u c t i o ne f f i c i e n c y ，a n dr e d u c ec o s t sf o rm a x i m u mc o n h n e r c i a l b e n e f i t s e q u e n t i a lp a t t e r n s m i n i n gi sa l la c t i v eb r a n c ho fd a t a b a s em i n i n g t h r o u g h m i n i n gs e q u e n t i a lp a t t e r n sb e t w e e nf r e q u e n ti t e m s e t s ，b u y e r ss h o p p i n gp a t t e r nc a nb e p r e d i c t e d ；q u a n t i t yo fs a l ec a l lb ep r o m o t e d f o re x a m p l e 彳二垴。t h i sr u l er e f e r s c u s t o m e r st ob u ym e r c h a n d i s ea ，t h e no f t e nb u yb b u s i n e s s e sc a nc o n s t i t u t es a l e s s t r a t e g ya c c o r d i n gt ot h i sr u l et op r o m o t es a l e so ft h et w op r o d u c t s b u t ，s o m e t i m e s c u s t o m e r sb u ym e r c h a n d i s ea ，t e n dn o tt ob u yc ，t h i sr u l ei sd e n o t e da sa = n c 。w e c a l l i t n e g a t i v ea s s o c i a t i o nr u l e sb a s e do ns e q u e n t i a lp a t t e r n s i nt h eb u s i n e s so f d e c i s i o n - m a k i n g ，t h en e g a t i v ea s s o c i a t i o nr u l e sb a s e do ns e q u e n t i a lp a t t e r no nh o wt o r e d u c et h en e g a t i v ef a c t o r s ，a n di n c r e a s eb e n e f i ti nt h em a x i m u ma r ep a r t i c u l a r l v i m p o r t a n t n o w , m o s tr e s e a r c h e sa b o u ts e q u e n t i a lp a t t e r n sa r ec o n c e n t r a t e do nt h ep o s i t i v e a s s o c i a t i o nr u l e s ，n e g a t i v ea s s o c i a t i o nr u l e sb a s e do ns e q u e n t i a lp a t t e r n sh a v en o ty e t c o m m e n c e dr e s e a r c h t h et h e s i ss t u d i e dt h ee x i s t i n gs e q u e n t i a lp a t t e r n sa l g o r i t h ma n d n e g a t i v ea s s o c i a t i o nr u l e sm i n i n g ，u s e dt h ed e f i n i t i o no fc o r r e l a t i o nt or e m o v e c o n f l i c t i n ga s s o c i a t i o nr u l e s ，a n dc o m b i n e dt h e s et w oa l g o r i t h m s ，g a v ea na l g o r i t h mo f m i n i n gp o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e sb a s e do ns e q u e n t i a lp a t t e r n s f i n a l l y , g a v ea ne x a m p l e so ft h ea p p l i c a t i o n ，s p e c i f i e dt h ei m p l e m e n t a t i o no ft 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 ；s e q u e n t i a lp a t t e m ；a s s o c i a t i o nr u l e s ；c o r r e l a t i o n ；n e g a t i v e a s s o c i a t i o nr u l e s i v 学位论文独创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。文中 引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已 属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果，与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属山东轻工业 学院。山东轻工业学院享有以任何方式发表、复制、公开阅览、借阅以及申请专 利等权利，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名 单位仍然为山东轻工业学院。 论文作者签名： 导师签名：盗丝盗 山东轻工业学院硕l ：学位论文 1 1 数据挖掘概述 第1 章绪论 随着计算机技术的发展，各行各业都开始采用计算机及相应的信息技术进行 管理和运营，这使得企业生成、收集、存贮和处理数据的能力大大提高，数据量 也与日俱增。这些企业数据实际上是企业的经验积累，对企业来说，是宝贵的资 源。要想使数据真正成为一个企业的资源，只有充分利用它为企业自身的业务决 策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此， 面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘技术应运而生，并得 以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 数据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程。还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、数据分 析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的源 泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系型数据库中的数 据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异 构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的， 也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过 程控制等，还可以用于数据自身的维护。因此，数据挖掘是- - i - j 广义的交叉学科， 它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并 行计算等方面的学者和工程技术人员。 数据挖掘所涉及的学科领域和方法很多，以下四种是非常重要的发现任务。 1 关联规则 若两个或多个数据项的取值重复出现且概率很高时，它就存在着某种关联， 可以建立起这些数据项的关联规则，一个典型例子就是：“9 0 的客户在购买面包 和黄油时也会购买牛奶”。关联分析的目的是找出数据库中隐藏的关联网，在大型 数据库中，这种关联规则是很多的，一般用“支持度”和“置信度”两个阈值来淘汰那 些无用的关联规则。 2 分类 分类就是对一个事件或一组对象进行归类。它代表了这类数据的整体信息， 即该类的内涵描述，一般用规则或决策树模式表示。一个类的内涵描述分为特征 性描述和区别性描述。特征性描述是对类中对象的共同特征的描述，区别性描述 是对两个或多个类之间的区别的描述。 第1 幸绪论 3 聚类 数据库中的数据可分为一系列有意义的子集，或称为类。在同一类别中，个 体之间的距离较小，而不同类别的个体之间的距离偏大。聚类增强了人们对客观 现实的认识，即通过聚类建立宏观概念。 4 时序模式 通过时间序列搜索出重复发生概率较高的模式，这罩强调时间序列的影响， 例如“在所有购买激光打印机的人中”半年后有8 0 的人再购买新硒鼓，2 0 的人用 旧硒鼓装碳粉。 数据挖掘的过程如下： 第一步，确定业务对象。清晰地定义出业务问题，认清数据挖掘的目的是数据 挖掘的重要一步。挖掘的最后结构是不可预测的，但要探索的问题应是有预见的。 第二步，数据准备。( 1 ) 数据的选择，搜索所有与业务对象有关的内部和外部 数据信息，并从中选择出适用于数据挖掘应用的数据。( 2 ) 数据的预处理，研究数 据的质量，为进一步的分析做准备。并确定将要进行的挖掘操作的类型。( 3 ) 数据 的转换，将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。建 立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 第三步，数据挖掘。对所得到的经过转换的数据进行挖掘。除了完善合适的 挖掘算法外，其余一切工作都能自动地完成。 第四步，结果分析与表达。解释并评估结果。确认其是否真正实现了预定的 商业目的，并将有价值的信息用易于理解的方式表达出来，帮助决策者制定正确 的决策。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商 业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问， 进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶 段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在 联系，从而促进信息的传递。现在数据挖掘技术在商业应用中已经可以马上投入 使用，因为对这种技术进行支持的三种基础技术已经发展成熟，它们是： ( 1 ) 海量数据搜集。 ( 2 ) 强大的多处理器计算机。 ( 3 ) 数据挖掘算法。 以下是数据挖掘中常用的技术： 1 决策树l 1 j 决策树是通过一系列规则对数据进行分类的过程。它以信息论中的互信息( 信 息增益) 原理为基础寻找数据库中具有最大信息量的字段，建立决策树的一个结 点，再根据字段的不同取值建立树的分枝；在每个分枝中集中重复建树的下层结 2 山东轻t 业学院硕十学位论文 点和分枝的过程，即可建立决策树。采用决策树，可以将数据规则可视化，其输 出结果也容易理解。该方法的实用效果好，影响较大。 2 人工神经网络法i z j 人工神经网络建立在可以自学习的数学模型的基础之上，它可以对大量复杂 的数据进行分析，并可以完成对人脑或其他计算机来说极为复杂的模式抽取及趋 势分析。神经网络系统由一系列类似于人脑神经元的处理单元组成，并称之为节 点( n o d e ) 。这些节点通过网络彼此互连，如果有数据输入，它们便可以进行确 定数据模式的工作。神经网络的处理过程主要是通过网络的学习功能找到一个恰 当的连接加权值来得到最佳结果。其比较典型的学习方法是回溯法。它通过将输 出结果同一些已知值进行一系列比较，加权值不断调整，得到一个新的输出值， 再经过不断的学习过程，最后得到一个稳定的结果。 3 遗传学算法【3 j 这是模拟生物进化过程的算法，由三个基本算子组成：a 繁殖( 选择) 是从_ 个 旧种群( 父代) 选出生命力强的个体，产生新种群( 后代) 的过程。b 交叉( 重组) 选 择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成新个体。c 变异( 突变) 对某些 个体的某些基因进行变异( 1 变o 、0 变1 ) 。遗传算法可起到产生优良后代的作用。 这些后代需满足适应值，经过若干代的遗传，将得到满足要求的后代( 问题的解) 。 4 统计学方法 利用统计学原理对数据库中的信息进行分析。可进行常用统计( 求大量数据 中的最大值、最小值、总和、平均值等) 、回归分析、相关分析、差异分析等。 5 可视化技术 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清楚。 但一个数据挖掘系统不是多项技术的简单组合，而是一个完整的整体，它还 需要其他辅助技术的支持，力能完成数据采集、预处理、数据分析、结果表述这 一系列任务，最后将分析结果呈现在用户面前【4 j 。 鉴于数据挖掘任务和数据挖掘方法的多样性，给数据挖掘提出了许多具有挑 战性的课题。数据挖掘语言的设计，高效而有效的数据挖掘方法和系统的开发， 交互和集成的数据挖掘环境的建立，以及应用数据挖掘技术解决大型应用问题， 都是目前数据挖掘员，系统和应用开发人员所面临的主要问题。未来的数据挖掘 技术主要有以下的几个发展趋势1 5 ，6 j ： 1 应用的探索：数据挖掘目前正探索扩大其应用范围，如生物医学、电信等 领域。通用数据挖掘在处理特定应用问题时有其局限性，因此，目前的一种趋势 是开发针对特定应用的数据挖掘系统。 2 可伸缩的数据挖掘方法：数据挖掘的一个重要研究方向是基于约束的挖掘 ( c o n s t r a i n t b a s e dm i n i n g ) ，该方向致力于在增加用户交互的同时改进挖掘处理的总 第1 章绪论 体效率。它提供了额外的控制方法，允许用户说明和使用约束，引导数据挖掘系 统对感兴趣模式的搜索。 3 数据挖掘与数据库系统、数据仓库系统矛u w e b 数据库系统的集成：数据库 系统、数据仓库系统和w w w 已经成为信息处理系统的主流。数据挖掘系统的理想 体系结构是与数据库和数据仓库系统的紧耦合方式。 4 数据挖掘语言的标准化：标准的数据挖掘语言或其他方面的标准化工作将 有助于数据挖掘的系统化开发，改进多个数据挖掘系统和功能间的互操作，促进 数据挖掘系统在企业和社会中的教育和使用。 5 可视化数据挖掘：可视化数据挖掘是从大量数据中发现知识的有效途径。 6 复杂数据类型挖掘的新方法：复杂数据类型挖掘是数据挖掘中一项重要的 前沿研究课题。 7 w e b 挖掘：有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务， 将成为数据挖掘中一个最为重要和繁荣的子领域。 8 数据挖掘中的隐私保护与信息安全：随着数据挖掘工具和电信与计算机网 络的日益普及，数据挖掘要面对的一个重要问题是隐私保护与信息安全。需要进 一步开发有关方法，以便在信息访问和挖掘过程中确保隐私保护与信息安全。 1 2 序列模式概述 一个大型超市的管理者经常需要考虑这样的问题，如卖什么商品、如何设计 购物优惠券、如何摆放商品等等。通过分析过去一段时间内顾客的购物情况可以 帮助管理者更好的解决这些问题。条形码技术的出现使得零售机构能够收集和储 存大量这种销售数据，顾客的每一次购物称为一次“事务”( t r a n s a c t i o n ) ，每一次事 务发生可以记录下该事务的发生时间，顾客i d 号、所购商品代号等等，这些数据 称为“购物篮数据”( b a s k e t d a t a ) ，一般都储存在数据库中。数据库管理系统虽然能够 提供高效的查询或更新，但却缺乏有效的分析工具，不能从这些数据中发现有价 值的信息，从而更好的为超市管理者服务。 为了解决这个问题，1 9 9 3 年，a g r a w a l 等人提出了关联规则挖掘问题，希望能 从事务数据库中发现有关顾客购买行为方面的知识，从而指导超市的经营策略。 一个关联规则的例子是“购买了牛奶和面包的顾客有9 0 的可能会购买黄油”，“ 牛 奶，面包 j 黄油) ”就是一个关联规则。但是，关联规则讨论的只是一次事务内部 的模式，有时随着时间的推移，事务之间也会有某种联系或者发展趋势，关联规 则无法揭示其中的规律。 基于序列模式的关联规则挖掘主要是挖掘数据i 、日j 的前后或因果关系。序列分 析要求购买商品记录是按时间次序登记的【7 1 。比如，超市中有6 0 的客户在第一次 4 山东轻工业学院硕十学位论文 交易中购买了商品a ，其中又有8 0 的客户在第二次交易中购买了商品b ，即序列 模式是么勒。显然，通过序列模式分析，超市可以发现客户潜在的购买模式。再 如一个实例，顾客租借录像带的一个典型的顺序是先租“星球大战”，然后是“帝国反 击战”，再是“杰达武士归来”这三部影片是以故事发生的时间先后而情节连续的。 值得注意的是租借这三部电影的行为并不一定需要是连续的。在任意两部之间插 租了任何电影，仍然满足这个序列模式，并且扩展一下，序列模式的元素也可以 不只是一个物品如一部电影，它也可以是一个物品或行为的集合。比如说这些集 合是一位客户连续的购物行程的采购列表。作为一个典型业务实例，一个列表的 集合可以是有关电脑的采购：首先是“十二月份买的电脑”，接着“一月份买的电脑 游戏和游戏杆”，再是“三月份买附加电脑内存，以及更大的硬盘驱动”。 在1 9 9 5 年举行的第1 1 届数据工程国际会议上，a g r a w a l 和s r i k a n t l 8 9 1 首先提出了 序列模式挖掘问题，提出了序列模式发现的经典算法a p r i o r i a l l 。不久，又对序列 模式挖掘的问题进以下扩展：引入了序列模式间相邻元素之间的最大或最小时间间 隔约束，放松了序列模式元素中所有项目必需来自同一事务的限制，在项目间引 入了分类机制。 基本的序列模式模型研究的是在同一字段上的序列模式，即单维的序列模式。 实际应用中的数据集是一个多维的空间，例如超市数据中每个顾客都有与之联系 的相关信息，如年龄、职业、教育层次等。结合这种多维信息来发现序列模式将 具有更实际的意义。h p i n t 等人对此做了研刭j 。 基本序列模式是基于某一特定支持度的。一旦用户指定了支持度阈值，算法 将发现满足该值的全部序列模式。一般来说，短的序列模式只有在较高支持度时 才有意义，而长序列模式在相对较小的支持度时仍是有意义的。 发现序列模式的目的是为了寻找一段特定时间以外的可预测行为模式。这就 意味着在给定时间内的一种特定行为有可能产生其他行为或在一段时间框架内的 连续行为。这种规则生成方法是关联技术的变体。其会根据不同的因素如随时间 的变化来分析客户的购物行为。 目前，基于序列模式的关联规则挖掘是数据挖掘领域中一个非常活跃的分支。 它被广泛地应用于各个领域。如顾客购买行为的分析【l ，根据客户资料和购物历 史数据进行数据挖掘，寻找企业最有价值的目标客户群，发掘目标客户群的商品 购买模式，预测目标客户群的商品购买趋势，挖掘目标客户群的购买力，为企业 提供动态、实时和准确的促销决策支持；股票交易分析 1 2 1 ，通过序列模式挖掘， 发现股票交易数据间的内在相互联系，进而对交易投资与决策有一定的指导作用 和参考价值：网络访问模式分析【1 3 】，将序列模式挖掘技术用于w - e b 日志文件的挖掘， 提出一个简单高效的序列模式挖掘算法，此算法具有较快的响应速度，可以满足 实时页面推荐的需要，同时还可以进行增量挖掘；另外在工艺设计自动化4 。、疾 第1 章绪论 病治疗的早期诊断、自然灾害的预测等方面序列模式挖掘都得到了应用。 以上研究都是形如彳瑚c 的序列模式的正关联形式，有关序列模式的负 关联规则挖掘的研究尚未展开。 1 3 本文的主要工作 数据挖掘是在数据库中发现离散数据项之间所存在的内在规律性的联系，通 过数据挖掘来发现对企业决策活动( 如客户分类、关系管理、制订市场营销策略和 服务水平等) 有用的数据集。挖掘序列模式的关联规则，可找出企业以往的成败经 验，预测将柬的发展方向，更好的为企业决策服务。本文正是围绕这一问题，通 过对现有的基于序列模式的关联规则挖掘算法，负关联规则挖掘算法的研究，将 两者进行结合，找出一种有效的挖掘基于序列模式的正负关联规则的方法。 6 山东轻工业学院硕士学位论文 第2 章序列模式相关概念 本章简述了关联规则，序列模式的相关概念，并将两者进行比较。2 1 节对 关联规则的一些知识进行叙述，包括基本概念、相关分类等；2 2 节介绍了序列 模式的相关概念；2 3 节将关联规则与序列模式进行了比较；2 4 节对本章进行了 小结。 2 1 关联规则 关联规, 贝q ( a s s o c i a t i o nr u l e ，a r ) 是由a g r a w a l 等人于1 9 9 3 年首先提出i l 引。关联 规则挖掘是指发现大量数据中项集之问有价值的关联或相关联系。一个关联规则 是形如a j b ( s u p p o r t ，c d 研d e n c e ) 的蕴涵式，例如：关联规则“牛奶面包 ( s u p p o r t = 2 0 ，c d 刀力d e n c e = 8 5 ) ，说明在所有的顾客事务中，有2 0 的顾客同 时购买了牛奶和面包，其支持度s u p p o r t = 2 0 ，而购买了牛奶的顾客中有8 5 的 顾客也购买了面包，其置信度c d 够d e n c e = 8 5 ”，这就是有名的支持度一置信度 框架( s u p p o r t c o n f i d e n c ef r a m e w o r k ) 。 通过关联分析，可以发现三种规则：有用的、价值不高的、费解的。它在数 据挖掘中是一个重要的课题。 价值不高的规则往往是对一些商业领域内众所周知的规则的重现。比如，今 天是情人节，那么鲜花的价格肯定会暴涨，这样的规则已经为人们所感知并运用 到了商业运作中。 费解的规则往往是数据中一些偶然的东西。比如：有一天某个超市发现购买 消夏商品的顾客增加，但是只有这一天销量特别突出，前后几天的销量都趋于平 常。造成这种偶然的情况的原因很可能是偶然的，如附近的几个居民区那天停电 脑 1 亍。 对于这样费解的规则，因为它出现的概率很低，我们没有必要对其进行分析， 也没有必要采取什么行动。 只有在事物之间潜在的经常发生的规则才是有用的规则，“潜在的”就是说别人 还没有发现的，还没有广泛的应用到商业运作中。“经常发生的”说明规则发生的概 率很大，我们对其采取行动产生的效益可能也很大。 我们将关联规则按不同的情况进行分类。 1 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系。 7 第2 章序列模式相关概念 数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进 行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关 联规则中也可以包含种类变量。 例如：性别= “女”职业= “秘书”，是布尔型关联规则；性别= “女”a v g ( 收 入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联舰则。 在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的 层次的。 在多层关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机j s o n y 打印机，是一个细节数据上的单层关联规则；台 式机j s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维关联规则中，我们只涉及到数据的一个维，如用户购买的物品。 在多维关联规则中，要处理的数据将会涉及多个维。 换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则 是处理各个属性之间的某些关系。 例如：啤酒j 尿布，这条规则只涉及到用户的购买的物品；性别= “女”j 职业 = “秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层 次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行 挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说 是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在 多个层次上进行挖掘的功能。 a g r a w a l 等人于1 9 9 3 年首先提出的a p r i o r i 算法【1 5 】，并于1 9 9 4 年做了改进【l 6 1 。 其核心是基于两阶段频繁项集思想的递推算法。通过遍历一大堆事务数据中，从 一个一个的单个项开始记数，每次遍历完所有的事务后，裁减掉支持度记数少于 用户给定的支持度的项，然后逐步扩展到多项事务。最后保留下来的频繁项集， 通过子集产生法来产生关联规则，然后去掉其中置信度低于用户指定的最低置信 度的关联规则，最后剩下的就是满足用户需要的关联规则。 此后关于关联规则的算法多是在原算法基础上的进一步改进。如文献【1 7 j 给出 了一种简单的关联规则定义，从而减少了挖掘时间，提高了效率。文献【l8 】提出了 加权关联规则模型，根据每个数据项的重要程度不同赋予不同的权值，并给出了 挖掘加权频繁项集的m w f i 算法。另外还有并行发现算法 嘲，增量式更新算法【2 明， 多值关联规则挖掘算法【2 l 】等等。 最新的一些研究工作提出数据项间的关联关系存在正关联和负关联，并且， 8 山东轻工业学院硕士学位论文 负关联规则的研究正成为新的研究热点。通过研究负关联可有效避免负面影响， 增加正面效益。本文将在第3 章对负关联规则进行详述。 2 2 序列模式 序列模型分析同关联规则类似，但是它更侧重于分析事物之间的前因( 后果) 关系。关联规则只是说明了事物之间存在联系，而没有更进一步指明关系是说明 类型。 为了更加准确和形象的描述序列模式挖掘问题，首先介绍一个小型的事务数 据库，该数据库中包含三个属性：顾客i d 、事务发生时间、该次事务发生时所购商 品代号，并以顾客i d 和事务发生时间为关键字进行排序。假设这个数据库描述了 从8 月1 0 日到9 月2 5 同这一段时间内所有购物信息，如第一条记录表示顾客1 在8 月2 5 日购买了商品3 0 。具体细节如表2 1 ： 表2 1 一个小型的事务数据库 以下是序列模式的相关概念。 事务数据库( t r a n s a c t i o nd a t a b a s e ) ：序列模式挖掘的数据库，记为d ，d = t l ， t 2 ，t k ，t n ) ，其中k = l ，2 ，n 。t k ( k = l ，2 ，n ) 为一条事务。如表2 1 中每一条记录就是一次事务。 项( i t e m ) ：表示一个商品被购买或没有购买，通常用i j o = lt om ) 表示。 项集( i t e m s e t ) ：由项( i t e m ) 组成的一个非空集合。 序y u ( s e q u e n c e ) ：不同项目集( i t e m s e t ) 的有序排列，