（计算机软件与理论专业论文）基于数据仓库的关联规则挖掘研究.pdf

华中科技大学硕士学位论文 捅璺 厂 绪合数据仓库鞫数攒挖弱的优势，邋行鏊于数裙仓库静数据挖掘的研究具有重要 意癸j 基于数摄仓露豹数据挖掘熬体系结构包括数据豹提取转羧和糖载、元数据、 数据仓库、知识库、数据可视化、o l a p 、数据挖掘和图形用户界蘧等部分 关联规则发现是数据挖掘中的重要课题。挖掘关联规则问题就是产生支持度和可 信度分别大于用户给定的最小支持度和最小可信度的关联规则。从用户与系统交互 的角度来看。关联规则的发现可以分为传统的关联规则发现和可交互的关联规则发 孺。为了产生相对少丽又有趣的关联蕊刚，有必簧采用可交互的关联瓶剩发现。 蹋户在哥交互静关联勰刚发现巾藏辍各种约慕。约寨分为个数魏寐、矮蠢终柬帮 霜数约束三类。失了终约束缀妻 越摊进到算法中，震要分蝣约寒弱挫质。约隶具有 反单调性、单调性、簧涨性、可转变性和不可转变性。其中，单调、反单调和简洁 的约束可以很好地推进到a p r i o r i 类算法中；可转变的约束只能猩f p - g r o w t h 类算法 中实现；不可转变的约束现在还没有很好的解决办法。 在个数约柬、项目约束和溺数约束中的支持废和可信度约束下，i s a r s 算法输出 了满是约寐的襁对，j 、酌关联撬燹| j 集嚣。在用户按讶信发由裔到低进行该灞时，霖帮 没香麓讫豹符会绞索豹关联撬粼集是等效豹。i s a r s 算法采用候选树佟失存继续秘， 势运用约窳熬菠单谰性秘筵漕性、霆的特性来握蹇算法性能。由于搜索范围的缩小 和搜索层次的减少、没有生成所有的频繁项集而且对产生的频繁项集没有生成所有 可能的规则，i s a r s 算法的性能得到了改进。该算法扫描数据库的次数取决于用户 给出的个数约束。实验结果证明，1 s a r s 算法比a p r i o r i 算法快大约7 倍。 、7 关键字：数循仑璋；数嚣狯掘；关联筑翔；算法 华中科技大学硕士学位论文 a b s t r a c t c o m b i n i n g t h ea d v a n t a g e so fd a t aw a r e h o u s ea n dd a t am i n i n g ，i ti ss i g n i f i c a n tt o s t u d yd a t am i n i n gb a s e do nd a t aw a r e h o u s e t h es y s t e ms t r u c t u r eo fd a t am i n i n gb a s e d o nd a t aw a r e h o u s ec o n s i s t so f e t l , m e t ad a t a ，d a t aw a r e h o u s e ，k n o w l e d g eb a s e ，d a t a v i s u a l i z a t i o n ，0 l a p d a t am i n i n ga n dg u i a s s o c i a t i o nr u l e sm i n i n gi sc o n s i d e r e dt ob eo n eo ft h em o s ti m p o r t a n tt a s k so fd a t a m i n i n g ，w h i c hi s t of i n dt h er u l e sw i t ht h es u p p o r ta n dc o n f i d e n c eg r e a t e rt h a nt h e t h r e s h o l d s f r o mt h ev i e wo f i n t e r a c t i o n ，a s s o c i a t i o nr u l e sm i n i n gc a nb ed i v i d e di n t ot h e t r a d i t i o n a la s s o c i a t i o nr u l e sm i n i n ga n dt h ei n t e r a c t i v ea s s o c i a t i o nr u l e sm i n i n g t og e t l e s sw h i l em o r e i n t e r e s t i n gr u l e s ，t h ei n t e r a c t i v ea s s o c i a t i o nr u l e sm i n i n g i sa g o o d c h o i c e u s e r s p u t f o r w a r dc o n s t r a i n t si nt h ei n t e r a c t i v ea s s o c i a t i o nr u l e s m i n i n g t h e c o n s t r a i n t sc a nb ed i v i d e di n t ot h en u m b e rc o n s t r a i n t s ，t h ei t e mc o n s t r a i n t sa n dt h e f u n c t i o nc o n s t r a i n t s a n d a c c o r d i n g t ot h e i r p r o p e r t i e s ，t h e y c a nb ea n t i - m o n o t o n e ， m o n o t o n e ，s u c c i n c t ，c o n v e r t i b l ea n di n c o n v e r t i b l e t h ea n t i - m o n o t o n e ，m o n o t o n ea n d s u c c i n c tc o n s t r a i n t sc a na l lb e p u s h e dd e e p i n t ot h ea na p r i o f i m i n i n ga l g o r i t h m ，w h i l et h e c o n v e r t i b l ec o n s t r a i n t sc a no n l yb ep u s h e di n t of r e q u e n t p a t t e r ng r o w t hf r a m e w o r ka n d t h ei n c o n v e r t i b l ec o n s t r a i n t sc a nb ed o n ei nn e i t h e r u n d e rt h en u m b e rc o n s t r a i n t s ，t h ei t e mc o n s t r a i n t sa n dt h es u p p o r ta n dc o n f i d e n c e c o n s t r a i n t si nt h ef u n c t i o nc o n s t r a i n t s ，t h ea l g o r i t h mi s a r si st of i n dt h es m a l l e s tr u l es e t r w i t ht h ed e s c e n d i n gc o n f i d e n c e ，t h eu s e r sw i l lg e tt h es a m ep r e d i c t i o nf r o mt h es e tr a st h ec o m p l e t es e t t h ea l g o r i t h mi s a r st a k e st h ec a n d i d a t ef l e ea st h es t o r a g es t r u c t u r e a n dm a k e su s eo fp r o p e r t i e so fc o n s t r a i n t sa n dt h es e trt ot h e i re f f i c i e n c y t h e e x p e r i m e n t a lr e s u l t ss h o w i tw o r k sa sq u i c k l ya se i g h tt i m e so f a p r i o r i k e y w o r d s ：d a t aw a r e h o u s e ；d a t am i n i n g ；a s s o c i a t i o nr u l e a l g o r i t h m 华中科技大学硕士学位论文 1 1研究背景 1绪论 无论是商业企业、科研机构或者政府部门，在过去若干年的时间里都积累了海量 的、以不同形式存储的数据资料。近年来，各种信息急剧增加，数据库的规模日益 扩大，形成“数据爆炸知识贫乏”的现象。因此，从已有的资料中发现有价值的信 息或知识，达到为决策服务的目的，成为迫切的任务【“。 但是传统的数据库技术并不能很好地完成这一任务。这是因为数据库系统作为数 据管理手段，从它的诞生开始，就主要用于事务处理。而事务处理环境并不适宜决 策支持系统( d e c i s i o ns u p p o r ts y s t e m ，简记为d s s ) 的应用。因此，数据仓库和数 据挖掘技术应运而生1 2 l i 3 1 。 数据仓库是计算机应用领域的新概念。所谓数据仓库( d a t aw a r e h o u s e ，简记为 d w ) 是指这样一种数据的存储池，来自于异地、异构的数据源或数据库的数据经加 工后在数据仓库中存储、提取和维护【引。传统数据库主要面向业务处理，而数据仓库 面向复杂数据分析、高层决策支持。数据仓库提供来自种类不同的应用系统的集成 化和历史化的数据，为有关部门或企业进行全局范围的战略决策和长期趋势分析提 供了有效的支持。数据仓库使用户拥有任意提取数据的自由，而不干扰业务数据库 的正常运行。为高级的决策支持服务是数据仓库的最终目的。数据仓库的产生和发 展为o l a p ( o n l i n ea n a l y t i c a lp r o c e s s i n g ) 和数据挖掘技术开辟了新的战场，同时 也提出了新的要求和挑战娜“。 联机分析处理( o l a p ) 是指一系列交互的查询过程，是使用户能够快速、交互 地、方便地获取他们所需数据的一些技术的综合。在查询过程中需要将数据在不同 层次、不同阶段上进行分析处理，从而获得高度归纳的信息。o l a p 在实质上也可以 说是多维数据分析工具，它的关键技术围绕着“维”这一概念。o l a p 的目标是实现 多维环境中的特殊查询及报表需求，并以此支持管理决策。o l a p 是在数据仓库基础 上进行深入的数据分析，获得关键信息以支持决策分析的主要手段之一1 7 j 。 数据挖掘( d a t am i n i n g ，简记为d m ) ，指的是从大型数据库或数据仓库等数据存 华中科技大学硕士学位论文 口目自= = ；l = = = = = = ；= = = = = ；= = = = ；： ： 贮中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息。数据 挖掘是目前国际上数据库和信息决策领域的最前沿研究方向之一，数据挖掘在此前 的研究主要是面向一般的数据库系统，现在平台已经转移到数据仓库上来，并相应 地发展起来一系列的理论和方法1 8 i 【9 j 【1 0 1 。 随着中国加入w t o 和以及风起云涌的技术进步，中国证券行业正面临前所未有 删b 战：如何加强公司的核心竞争力，如何加强公司业务监督管理，如何有效地防 范和规避市场风险，如何获得更大的经济效益，以及如何最有效地进行客户服务等 等这些重要的课题都摆在了每个证券公司面前。如何将数据仓库和数据挖掘技术 应用于证券行业，具有重大意义。因此，科技部将数据仓库在证券行业中的应用方 法研究列为十五预研项目之一。这正是本课题的来源。 1 2 国内外研究概况 1 2 1 数据仓库的国内外研究概况 数据仓库是一个为决策支持系统和联机分析处理提供数据源的结构化数据环境。 业界公认的数据仓库概念创始人w h i n m o n 在建立数据仓库一书中对数据仓库 的定义是：数据仓库是面向主题的、集成的、不可更新的( 稳定性) 、随时间不断变化 ( 不同时间) 的数据集合，用以支持经营管理中的决策制定过程。 数据仓库中的数据面向主题，与传统数据库面向应用相对应。主题是一个在较高 层次上将数据归类的标准，每一个主题对应一个宏观的分析领域；数据仓库的集成 特性是指在数据进入数据仓库之前，必须经过数据加工和集成，这是建立数据仓库 的关键步骤，首先要统一原始数据中的矛盾之处，还要将原始数据结构做一个从面 向应用到面向主题的转变；数据仓库的稳定性是指数据仓库包含历史数据，而不是 日常事务处理产生的数据，数据经加工和集成进入数据仓库后是极少或根本不修改 的；数据仓库是不同时间的数据集合，它要求数据仓库中的数据保存时限能满足进 行决策分析的需要，而且数据仓库中的数据都要标明该数据的历史时期l l ”。 数据仓库最根本的特点是物理地存放数据，而且这些数据并不是最新的、专有的， 而是来源于其它数据库的。数据仓库的建立并不是要取代数据库而是建立在一个 较全面和完善的信息应用的基础上，用于支持高层决策分析，而事务处理数据库在 2 企业的信息环境中承担的是日常操作性的任务。数据仓库是数据库技术的一种新的 应用。 近年来，数据仓库技术引起了学术界的极大兴趣，国际上许多重要的学术会议， 如超大型数据库国际会议( v l d b ) 、数据工程国际会议( d a t ae n g i n e e r i n g ) 等，都 出现了专门研究数据仓库( d w ) 、联机分析处理( o l a p ) 和数据挖掘( d m ) 的论 文。 目前各大数据库厂商纷纷宣布产品支持数据仓库并提出一整套用以建立和使用 数据仓库的产品，主要有o r a c l e 、i b m 、s y b a s e 、l n f o r r n i x 和m i c r o s o f t 公司等。 1 o r a c l e o r a c l e 公司的数据仓库解决方案包含了业界领先的数据库平台、开发工具和应用 系统，它能够提供一系列的数据仓库工具集和服务。它具有多用户数据仓库管理能 力、多种分区方式、较强的与o l a f 工具的交互能力、及快速和便捷的数据移动机 制等特性。 o r a c l e 公司提供了一系列的数据仓库工具：o r a c l e8 i 是数据仓库的核心。o r a c l e w a r e h o u s eb u i l d e r 集成数据建模、数据抽取、数据转移和装载、聚合、元数据的管 理等功能。o r a c l ed e v e l o p e rs e r v e r 是企业级的应用系统开发工具，支持面向对象和 多媒体，可同时生成c l i e n t s c r v e r 及w e b 下的应用，具有极高的开发效率及网络伸 缩性。o r a c l ed i s c o v e r 是最终用户查询、报告、深入、旋转和w e b 公布工具，能够 帮助用户迅速访问关系型数据仓库，从而使他们作出基于充分信息的决策。o r a c l e d a r w i n 是基于数据仓库的数据挖掘工具，具有简单易用的图形化界面，提供决策树、 神经网络等多种数据挖掘方法，支持海量数据的并行处理，而且分析结果可以和现 有系统集成。 o r a c l e 的数据转移工具需手工编写s q l 脚本，在处理复杂的数据转换需求时困 难很多。o r a c l e 的前端工具易用性较差，需较多地依赖第三方产品。 2 i b m i b m 公司提供了一套基于可视数据仓库的商业智能( b i ) 解决方案，具有集成 能力强、高级面向对象s q l 等特性。 i b m 提供的v i s u a lw a r e h o u s e ( v w ) 是一个功能很强的集成环境，既可用于数 华中科技大学硕士学位论文 据仓库建模和元数据管理，又可用于数据抽取、转换、装载和调度。e s s b a s e d b 2o l a p s e r v e r 支持多维数据库，它是一个r o l a p 和m o l 廿混合的h o l a p 服务器，在 e s s b a s e 完成数据装载后，数据存放在系统指定的d b 2u d b 数据库中。q u e s t 是 i b m 公司a l m a d e n 研究中心开发的一个多任务数据挖掘系统，目的是为新一代决策 支持系统的应用开发提供高效的数据挖掘基本构件。系统提供多种挖掘功能，挖掘 算法可适用于任意大小的数据库。 i b m 公司自己并没有提供完整的数据仓库解决方案。但是它可以使用第三方的 数据仓库工具。例如，查询工具使用b u s i n e s so b j e c t s 的b u s i n e s so b j c c t s ，统计分析 工具使用s a s 公司的s a s 系统。 3 s y b a s e s y b a s e 公司提供的数据仓库解决方案以能够支持多种关系型数据库而受到业界 推崇。它能够同时处理几十个即时查询，其b i tw i s e 技术和垂直数据存储技术使系 统只访问特定的少量数据，使得查询速度比传统的关系型数据库管理系统快1 0 0 倍。 w a r e h o u s ea r c h i t e c t 是p o w e r d e s i g n e r 中的一个设计模块。利用它，数据集市或 数据仓库设计者可以自动地对已有的关系数据库进行逆向工程，建立目标数据库设 计、物理设计和d d l 。p o w e r s t a g e 、r e p l i c a t i o n s e r v e r 、c a r l e t o np a s s p o r t 是数据 抽取与转换工具。a d a p t i v e s e r v e re n t e r p r i s e 是s y b a s e 企业级关系数据库，它通过多 线索体系、并行操作以及对系统的内存、处理器和磁盘资源使用进行控制等手段增 强了资源利用率。a d a p t i v e s e r v e ri q 是s y b a s e 公司专为数据仓库设计的关系数据库。 p o w e r d i m e n s i o n s 、e n g l i s h w i z a r d 、i n f o m a k e r 、p o w e r d y n a m o 是数据分析与展现工具。 w a r e h o u s ec o n t r o lc e n t e r 、s y b a s ec e n t r a l 、d i s t r i b u t i o nd i r e c t o r 是数据仓库的维护与 管理工具。 s y b a s e 的i n d u s t r yw a r e h o u s es t u d i o 包括相应行业所需的商业智能应用软件和数 据分析模型，可以针对不同行业进行业绩分析、促销活动分析、用户群分析、销售 分析和收益分析等，具有数据仓库设计、元数据管理等功能，支持广泛的应用软件 和报表，并提供w a r e h o u s es t u d i o 和w a r e h o u s ec o n t r o lc e n t e r 等工具，使企业能够 进一步扩展数据模型和应用系统，以适应各种商业活动的实际需要。 4 i n f o r m i x 4 华中科技大学硕士学位论文 l n f o r m i x 公司发布了一个集成的、可伸缩的f a s ts t a r t 数据仓库解决方案，以使用 户能快速而便捷地设计开发具有可伸缩性的数据仓库或数据集市。采用r o l a p 的星 型模式与l n f o r m i xi d s 、i d s a d 紧密集成，提供预先汇总、抽样、后台查询等性能 优化手段。l n f o r m i x 产品能够集成m i c r o s o f ti i s 或n e t s c a p ee n t e r p r i s e f a s t t r a c k 服务 器，从而支持w e b 访问。i n f o r m i x 没有提供自己的报表和数据挖掘工具，它可以集 成第三方产品( 例如结合b r i o 的前端数据分析和报表功能，结合s a s 的数据挖掘功 能) 。而且i n f o r m i x 向客户提供一套完整的咨询服务包。 m e t a c u b er o l a p o p t i o n 为基于i n f o r m i x 的数据仓库或数据中心提供了全面、简 便易用、可扩展和自动化的商业分析环境。i n f o r m i x i n f o m o v e r 是一套集成工具，用 于从多个工作资源中抽取、转换和维护数据。s e a g a t ec r y s t a ll n f o 是企业级报表分析 系统。i d s 以及a d x p 是i n f o r m i x 数据仓库系统的核心，提供数据仓库数据的存储 功能。 采用i n f o l m i x 数据仓库解决方案可以使数据仓库系统具有高性能、高可扩展性和 高开放性，并可以自己进行定制。同时，i n f o r m i x 提供专业数据仓库咨询服务，将 有助于快速、及时地建设数据仓库系统，并真正发挥作用。 5 m i c r o s o f t m i c r o s o f t 公司的s q l s e r v e r 2 0 0 0 已经在性能和可扩展性方面确立了世界领先的 地位，是一套完全的数据库和数据分析解决方案，使用户可以快速创建下一代的可 扩展电子商务和数据仓库解决方案。m i c r o s o f t 将o l a p 功能集成到m i c r o s o f ts q l s e r v e r 中，提供可扩充的基于c o m 的o l a p 接口。m i c r o s o f to f f i c e2 0 0 0 套件中的 a c c e s s 和e x c e l 可以作为数据展现工具，另外s o ls e r v e r 还支持第三方数据展现工 具。 s q ls e r v e r 通过一系列服务程序支持数据仓库应用。数据传输服务d t s ( d a t a t r a n s f o r m a t i o ns e r v i c e s ) 提供数据输入，输出和自动调度功能，在数据传输过程中可 以完成数据的验证、清洗和转换等操作，通过与m i c r o s o f tr e p o s i t o r y 集成、共享有 关的元数据；m i c r o s o f tr e p o s i t o r y 存储包括元数据在内的所有中间数据；s q l s e r v e ro l a ps e r v i c e s 支持在线分析处理；p i v o t t a b l es e r v i c e s 提供客户端o l a p 数 据访问功能，通过这一服务，开发人员可以用v b 或其他语言开发用户前端数据展 5 华中科技大学硕士学位论文 现程序，p i v o t t a b l es e r v i c e s 还允许在本地客户机上存储数据： m m c ( m i c r o s o f t m a n a g e m e n tc o n s o l e ) 提供日程安排、存储管理、性能监测、报警和通知的核心管理 服务。 数据仓库是m i c r o s o f t 公司刚刚进入的一个全新领域，与该公司的传统产品差别 较大。同时，也相对缺少在数据仓库实施方面的咨询经验。 1 2 2 数据挖掘的国内外研究概况 数据挖掘就是从数据中发现信息或知识。数据挖掘( d m ) 又称为知识发现( k d d ) ， 是人工智能、机器学习与数据库技术相结合的产物。k d d 一词首次出现在1 9 8 9 年 举行的第十一届国际联合人工智能学术会议上。到目前为止，由美国人工智能协会 主办的k d d 国际研讨会规模越来越大，由原来的专题讨论会发展到国际学术大会， 研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及 多种学科之间的相互渗透。1 9 9 9 年，亚太地区在北京召开的第三届p a k d d 会议收 到1 5 8 篇论文，空前热烈。i e e e 的k n o w l e d g e a n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络、信息工程等其他领域的国际学会 或学刊也把数据挖掘和知识发现列为专题和专刊讨论。此外，在i n t e r a c t 上还有不 少k d d 电子出版物，其中以半月刊k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威 ( h t t p ：w w w k d n u g g e t s c o m s u b s c r i b e h t m l ) 。 目前，数据挖掘发现的模式类型主要有：概念，类描述、关联规则、分类和预测、 聚类分析、孤立点分析、演变分析等。世界上比较有影响的典型数据挖掘系统有： s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i n e r 、 s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司 的s e e 5 、还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r y w o r k b e n c h 、d b m i n e r 、 q u e s t 等。 与国外相比，国内对数据挖掘的研究稍晚一点。1 9 9 3 年国家自然科学基金首次 支持对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识发 现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、空 军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在知 识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究， 6 华中科技大学硕士学位论文 j _ _ _ _ i i i i i ii,i_z_目_|_-_自；|_-j 华中科技大学、复照大学、淤江大学、中国科技大学、中科院数学职究所、吉抟大 学等单位开展了对关联规则发现算法的优化和改造；南京大学、四川联合大学和上 海交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘等。 1 3 关联规则发现的研究工作 关联蹴羹| j ( a s s o c i a t i o nr u l e s ) 静挽黧是数据挖摇中瓣一个重簧豹鞫题。稀找密满 是最，l 、支撩度秘最小霹傣发要求静关联规爨l j ，是关联援受| 发现黪硪究嚣橱。一般邈， 关联规则发现分为找出频繁项集郓生成规则獗个步骤。藤找出频繁项集是关联规则 算法的性能瓶颈。因此绝大部分对关联规则算法的研究都集中在第一步，即如何在 保证精度的基础上提高算法的运行效率，其中精度是指所找出的频繁项集的满足要 求的程度。 1 9 9 3 年，a g r a w a l 等褥出了关联规剃发现闯趱l 埘，间时提出了第一个频繁磺集发 现算法。诧看，在各种| 蠢麓鹜景下，霭绕着箍离箨法效率耪结祭翡鸯瘸校( 鄂怒户 对其感兴趣程发) ，研究嚣妇提出了各耱凝繁顼集发理筹法。摄掇这些冀法的残究重 点不同，趣将其分为垫奉频然项集发现算法墨l i 增强频繁项集发现箨法。藤者致力予 设计备种冀法梃架，高效地发现所有支持度大于巢个不变的最小支持度的频簸项集。 后者致力干提高发现结果的有用性。基本频繁项集发现算法的缩果往往不能满足用 户要求，比如所发现的频繁项集的有用性不高、发现的频繁项集数蠢过多、遗漏翔 户感兴趣的频繁项集等等，增强频繁顼集发糯算法通过弓i 入概念瑶次结构、终柬条 件、哥变支持壤等方式来克溅这些缺陷。 蒸本鬏繁磺集发瑷算法是在单数据烽、攀壤念层次秘最基本簧求 一s u p ( x o y ) s u p ( x ) 。 绘定一个交易集d ，关联媲剥的发现就是产生支持度秘可信度分别大子用户绘定 的最小支持度( m i n s u p p ) 和最小可债度( m i n c o n o 的关联规则 3 。1 。2 关联规则的分类 按照不弱豹标准，关联规划窍不同的分类方法。具体奔缨如下： 1 基于规则巾处理的变量的类别，可以分为布尔型关联规则和数假型关联规 则。 布尔型关联规则处理的慎都魑离散的、种类化的，它显示了这些变量之间的关系； 华中科技大学硕士学位论文 i i 1 _ _ _ - - i _ _ _ _ _ _ _ _ - _ 自_ = 口自# - _ _ _ _ - - _ _ _ _ _ _ - _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ l 自i 而数值型关联舰则可以和多维关联舰则或多层关联规则结食起来，对数值型字段进 行处理，祷其避行动态酚分割，或者直接对原始的数精迸彳亍处理，当然数值型关联 液羽审氇萄戳键含种类交藿。 恻如：牲甏= “女”一敬数= “秘书”，楚毒尔型关联戴爨l l ；链裂= “女”一8 v 鐾 ( 收入) = 2 3 0 0 ，涉及的收入是数馕类型，联以是一个数值型关联靓则。 2 。基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层关联规则中。所有的变量都没有考虑到现实的数搬是具有多个不同的层次 的；而在多层关联娥则中，对数据的多层性融经进行了充分的考虑。 例如：i b m 台式机= * s o n y 打印机，是一个细节数据上的单层关联规则；台式机 = * s o n y 打印机，是一个较高朦次和细节层次之间的多层关联规则。 3 基于麓掰中涉及掰豹数稽的维数，爵戳分为擎维关联麓辩和多维关获麓剃。 在萃缭关联筑蚕| j 中，廷涉及到数据豹一个维，絮用户赡买豹镌菇；焉奁多绻关联 翘刚巾，耍处毽熬数摆掩会涉及多令维。换成男一每落，攀维关联裁则是处理肇令 属蛙中的一些关系；多维关联规则是处理各个属性之闻的菜些关系。 例如：啤酒一屎森，这条规则只涉及到用户的购买的物品； 性别= “女”碲职 业= “秘书”，这条规则就涉及剡两个字段的信息，是两个维上的一条关联规则。 布尔型关联规则相对简化闷题，是其他关联规则的基础，因此下面研究的是布尔 型的关联规则。 3 。2 约束及其性质 3 2 1施绷约束的源西疑方式 3 1 节介绍了不隧类黧的关联麓劂。那么在发现这魏关联规剃的过程孛，甭户扮 演了 中么角色弦2 菠热在2 2 节中掰介绥豹，在传统豹关联援剐发现串，用户饺仅设 篷了裙始溺篷( 寇撼支持疫、霹信痰) ，然爱裁是等德系统交幸幸最终熬结果。系统往 往震要足令小时或毳更多戆对闽寒产生大量的关联援则，聪在这些关联规则中，往 差只夜小部分楚用户震要的。显然，如聚用户能谯关联规则的发现过程中进行指导 的话，产嫩的关联舰则数目将大大减少，也熨符含用户的需要。 华中科技大学硕士学位论文 那么，用户将以怎样的方式介入关联规则的挖掘过程睨? 一种可能的方式是使用 某种数攒挖掘查询语言。这需要用户其有一定的数攒挖掘的专业知识。另一种就艇 使埔图形用户界面。这相对不够烫活，但怒对用户来说很直观。为了使糟方便，在 本系统串采焉图形用户界面。 必予磷究的震螫，下嚣讨谂约束熬定义与分类。 3 。2 2 约束酌定义与分类 类骰文献湖，给崮交易集上约束酌定义。 定义l 约束对确定熬交易集d ，终寒c 怒在2 上熊甄富。姿基仪当c x ) 为 真时，称项集x 满足约柬c 。设s 2 7 ，蒯乏姆) - x s l 燃足c 。当s - 2 时t 翻咒岱) 简写为s a t , 例如定义c 脚为项集必须满足最小支持度d ；定义c 岱) 为s 2 也剐，即 只在项“，i 2 ，) 中挖掘关联规则。e 。- f i ，f 2 ，f ， ，即簧挖掘的关联规则的右部 ( r h s ) 在 i l ，i 2 ，毛) 中。 从形式上看，将约柬分为以下三类 4 8 j 。 1 个数约束( n u m b e r c o n s t r a i n t s ) ；关联规娴中涉及韵项的个数限翻； 2 项目约束( i t e mc o n s t r a i n t s ) ：关联撬羽的左部( l h s ) 耩右都( r h s ) 所满 类鞘静鞭铺； 3 。糖数终紊( f u n c t i o nc o n s t r a i n t s ) ：关联艇粼除类别以辩豹鼹剿以及矮蘩阋翳 相嚣关系，逶寒为函数形式。 例如，用户可以提出这样的挖掘请求：请找出食品一食品的关联规则，其中， 支持度为0 4 ，可信废为0 5 ，且最多考虑5 种食品。在这里，要求规则的左部和右 部均为食品，这是项目约束。最多考虑5 种食晶这是个数约束。要求支持度和可 信魔分别为0 4 、0 5 ，这是函数约束。 在这里主耍考虑个数约束、项目约束、函数约束中的支持度和研信泼约束。 3 2 3 约束的性质 3 2 2 节对约束从形式上进行了分类讨论，但是怎么找出符合这魑约束的关联规 华中科技大学硕士学位论文 则呢? 显然，进行约束性关联规则发现的算法要具有健壮性，即仅仅找出符合约束 的关联规则；要具有完全性，即要找出所有满足约束的关联规则。一个最简单的办 法就是先找出所有的频繁项集或关联规则，然后一个个地进行检验，输出满足约束 的结果。显然，这是最低效的办法。更高效的解决办法是分析约束的性质，将约束 尽可能深地推进到算法中。因此有必要来讨论约束的各种性质。 通过分析发现，约束具有以下五种性质： 1 反单调性( a n t i - - m o n o t o n e ) 。 如果一个项集不满足该规则约束，那么它的任何超集也不满足该约束，如果一个 约束具有这一性质，则称它是反单调的。 例如s u m ( 1 p r i c e ) 1 0 0 ，那么，该k 项集的超集( k + 1 ) 项集，要比k 项集多一些项，显然就 更贵，因此也不满足该约束。 反单调性是一个非常重要的性质，在算法i s a r s 中就大量地应用了这个性质。 因此，下面给出反单调性的形式化定义【4 7 】，并证明项目约束等是反单调的。 定义2约束的反单调性如果对于所有项集z ，z ，约束c 都有 似z 蹦足c ) 一x 满足c ，那么约束c 是反单调的。 显然频繁约束c 腑是反单调的，这就是著名的a p r i o r i 性质。a p r i o r i 算法运用 a p r i o r i 性质大大压缩了搜索空间。类似地，可以运用具有反单调性的约束来提高算 法效率。在这里，可以证明项目约束是反单调的。根据项目约束的定义，限定关联 规则的右部( r h s ) 所属类别就是约束c i 。；而限定关联规则的左部( l h s ) 所属 类别可以由限定挖掘范围c j ， ) 和限定关联规则的右部c l 。得出。根据约束的反 单调性定义，显然约束e 。和c i 眦。都是反单调的。所以项目约束是反单调的。算法 i s a r s 中将运用项目约束的反单调性。 2 单调性( m o n o t o n e ) 。 如果一个项集满足该约束，那么它的所有超集也满足该约束，如果一个约束具有 这一性质，则称它是单调的。 这样。对于满足单调性约束的项集，可以直接将它们挑选出来，仅对其考虑其他 华中科技大学硕士学位论文 的约束。 3 简洁性( s u c c i n c t ) 。 对于这类约束，可以列出并且仅仅列出所有确保满足该约束的集合。 这样，在支持计数开始之前，就可以直接精确地产生满足它的集合，这样就避免 了生成一检验方式的过大开销。换言之，这种约束是计数前可剪枝的。例如对 m i n ( j p r i c e ) = 5 0 0 ，在计数前就可以判断某个项集是否满足该约束了，如果不满足， 可以直接剪去。 4 可转变性( c o n v e r t i b l e ) 。 有些约束不属于以上三种，然而，如果项集中的项以特定的次序排列，约束可能 成为单调的或反单调的。 例如a v g ( 1 p r i c e ) 既不是反单调的，也不是单调的。然而，如果事务中的项以单价 的递增序添加到项集中，则约束a v g ( i p r i c e ) v ，则按递增的次序，该项集的超集必 然是在原来的项集中添a n tp r i c e 更大的项，显然该超集也是不能满足该约束的，因 此是反单调地，故该约束是可转化的反单调约束。同理，如果事务中的项以单价的 递减序添加到项集中，则该约束就成了可转化的单调约束。 5 不可转变性( i n c o n v e r t i b l e ) 。 不属于以上四类的约束，将其都归为不可转化的约束。 不同类型的约束之问的关系如图3 1 所示。 。通过研究发现，单调、反单调和简洁的约束可以很好地推进到a p r i o r i 类算法中； 可转变的约束只能在f p g r o w t h 类算法中实现；不可转变的约束现在还没有很好的解 决办法p 8 1 。 对于个数约束、项目约束、函数约束中的支持度和可信度约束，个数约束是反单 调的，项目约束是反单调的简洁的，支持度约束是反单调的。显然，它们可以很好 地推进到一个a p r i o r i 类算法框架中。 华中科技大学硕士学位论文 3 3 小结 图3 - 1 不同类型的约束关系 关联规则的挖掘是数据挖掘中的一个重要的问题。个关联规则是形如z y 的蕴涵式。规则x y 在交易集d 中的支持度是交易集中包含x 和y 的交易数与所 有交易数之比，可信度是包含包含x 和】，的交易数与包含x 的交易数之比。给定一 个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小 支持度和最小可信度的关联规则。 根据不同的分类标准，关联规则可以分为布尔型关联规则和数值型关联规则、单 层关联规则和多层关联规则、单维关联规则和多维关联规则等。 为了产生相对少而又有趣的关联规则，用户有必要在关联规则的发现过程中进行 指导，即用户对关联规则的发现施加约束。交互的方式可以是使用某种数据挖掘查 询语言或者图形用户界面。 约束是在交易集上的断言。从形式上看，约束分为个数约束、项目约束和函数约 束三类。 为了将约束很好地推进到算法中，需要分析约束的性质。约束具有反单调性、单 华中科技大学硕士学位论文 调性、简洁性、可转变性和不可转变性。其中，单调、反单调和简洁的约束可以很 好地推迸到a p r i o r i 类算法中；可转变的约束只能在f p g r o w t h 类算法中实现；不可 转交的约柬现在还浚有缀好的解决办法。 瓣于令数约束、项曩终寒、函数约寒中豹支持度郓霹绩度终寒，令数终衷蹩反擎 调的，项圈约束是反单调的麓洁的，支持度约束匙反单调的。显然，一个a p r i o r i 类 算法框架是合适的。这正是i s a r s 算法采用a p r i o r i 类算法框架的原因。 华中科技大学硕士学位论文 口目i _ _ _ _ _ 目= = 自i = = = # = ；_ 目目#_ a ； ： 4 交互式的最小关联规剩集的挖掘算法i s a r s 4 。1 算法恶想 在个数约束、项耳约束、函数约束中的支持度和可信度约束下考虑挖掘算法。 显然，算法成当满足用户给定的约束。在指定交易集中进行挖掘，输出会乎约束的 关联规则集。第3 章分析了，对于所给定的三类约束，一个a p r i o r i 类算法框架是含 适的。t 觏就魑说，因为有个数约束，驻然，一个按屡搜索的算法是很好的选择。对 于项目约束，应当充分和甭它的反单调住和简洁往来剪税。对于函数约束，也应当 穰掰支持度之类静爰萃调往约束。那么，壹接将约束推进搿h p d o d 算法巾码? 葺然， 这撵是霹蠢戆。实际上，有入已经进露了将反攀调露筵渍瓣终寨推避到a p r i o r i 算法 孛鲍工撵1 3 6 l 。这捞擞虽然爆户能褥到艨毒瀵足终束黪关联翅则，但是其巾缀多援则 在使用上将是重复的。 例如，考虑规则集 a b c ( o 2 ，0 7 ) ，a jc ( o 2 , 0 7 ) ，规贝a l a b 姊c ( o 。2 ，0 7 ) 就是 可以忽略的，因为4 一c ( o 2 , 0 7 ) 比它更一般，且具有相同的可信度。 也就是说考虑到性能问题，没必要输出所有可能产生的关联规则，只要输出的 关联规则集在用户进行预测时等效就可以了。也就是说输出的关联舰则集只怒满足 约束的关联规则集的子集，德在用户使用时，它们是等效的。 著名的a p r i o r i 算法是一种按层搜索的算法h 4 1 。它由找颓繁项集和生成关联规则 集两步缎成。为了改进效率或满足特筑需求，徽多算法被提出来。大部分算法末簧 研究第一步，稀离羧遮筏出频繁瑷集。豁努算法考惠载了潜关联撬辩集靛籁豫。鞠 论文1 4 9 就藿按在挖掘过程中修剪搏不嚣要豹关联规则，生成了翅予鞭测熬关联援剡 售惠集。这是个鸯蕴黪痿示，尤其是关联热烈馈息集豹壤念。关联规蜓僚息集是关 联规则集的