（应用数学专业论文）关于时态数据关联规则挖掘研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 时态数据挖掘已成为数据挖掘领域一个重要分支和较新的研究方向。 目前有关它的关联规则挖掘研究大多比较零散，缺乏统一的理论框架，而 且由此所建立的模型及相应算法只是适用于某一特殊的数据类型，缺乏可 扩展性：此外，随着f u z z y 集和r o u g h 集理论的引入，如何结合不确定性 理论进行挖掘也是尚待探索等等。 本论文，首先通过对基于相关集合事务数据库关联规则挖掘这一方法 的研究，借助不确定性推理中包含度理论将之所建立的信任度与r o u g h 集中精度进行对比分析，发现它们在数学计算上是相同的，此外，还推导 了信任度的增量计算。 在时间序列挖掘中，借助r o u g h 集理论，将传统的纯数学方法转向人 工智能技术与数学相结合的方法。研究了使用r o u g h 集进行挖掘的思想、 方法及某些方面的改进，并总结了利用r o u g h 集进行挖掘的常用策略。 其次，为了更好地刻画关联规则的时效性问题，研究了由此而建立的 时态型和相应的支持度、信任度及不同类型的时态数据关联规则的描述， 通过将它运用于事务数据库中，发现这种描述具有较好的理论分析与实际 应用价值。 最后，探讨了模糊思想引入时态数据关联规则挖掘的必要性。 关键词：相关集合，支持度，信任度，时态关联规则 西南交通大学硕士研究生学位论文第l l 页 a b s t r a c t t e m p o r a ld a t a m i n i n g h a sb e c o m ea n i m p o r t a n t b r a n c ha n dq l 妇a u d yc i r c t 呦a c eo f d a t a m i n i n gf i e l d a tp r e s e n t , m o s to f t l l es t t l d l e sa b o u t i t sa s s o c i a t i o nr u l e 倒n i n gl a c ku n i t e d t h e o r e t i c a l f i a m e w o r k s , a n d m o d e l a n d c o r r e s p o n d i n g a l g o r i t h m b a s e d o n t e m p o r a l d a t a a r e o r d y a p p l i e d t os o m e s p e d a ld mt y p e w h o sm o r e , a l o n g w i t hi n t r o d u c i n go f f u = ys e ta n d r o u g h s e t t h e o r y , h o w t o a p p l i e d t m c e r t a i n t y 廿h e o r y t o m i n e i m t a l s o s o l v e d e t c i n | t x i s t h e s i s , a t f a s t b y m e a 【l s o f 锄母萄s a n ds t l 】d y o f i d 趋o f 弧j o c 虹i e o f 蛔i l s 粕 d a t a b a s eb a s e do n m u t u a l i t ys e ta n d w i t ht h ea i do f i n c l u d i n gd e g r e eo f t m c e r t a i n t y m 笛。曲喀， c o t l f i d e n c ed e g r e eb a s e do ni n c l u d i n gd e g r e ei sc o m p 舒耐w i t ha c e t r d e yo fr o u g hs e t w e d i s c o v e rt h a tl t a e ya r et h es a m ef o r m u l ao fm 珊坷1 】鲥c sd e r i v a l i o r lw 埘m o r e i n c r e m e n t c o m p u t i n g f o r m u l a s o f c o n f e r e e d e g r e e i s d e d a x ：e d 。 i n t h es t u d i e s o f m i n i n g o f l i m e s e r i e s , w i l h t h e a i d o f r o u g h s e t t h e o r y , p u r e n l ：a t h e m a t i c s m e l h o d so ft r a d i t i o na r et m n s f o r m e di n t oa r t i f i c i a l i n t e l l i g e n c e a n dn 咀豫m 刮j c sm e t h o d s m i n i n g t h o u g h t s a n d m e t h o d s w i t h r o u g hs e t t h e o r y a r e s t u d i e d t a c t i c s o f m i n i n g w i t h r o u g h s e t a r e s u m m a r 醢d s e c o n d l y ，向t h e i s s u eo f d e p i c t i n gv a l i d - t i m eo f a s s o d a f i o nr u l e , s c i e n c ed e s c 啦栅o f t a 珥埘吐1 ) 1 p e a n d a c c 0 柑i i 】g 驯删d 舭、c o n f i d e r r x d e g r e e a n d a s s o c i a t i o n r u l e o f t e m p o r a l d a t ao f d i f f e r e n t t y p ea r es t u d i e d b y 印龇t h e mt o 衄噬m d d a t a b a s e ，w e d i s c o v e rt h a t t h e y p o s s e s s b 酣e r m a l y s i s a n d a p p l i e d v a l u e a t l a s t ，i t i sr e c e s s a r y t o a p p l y f u z z y i d e a i n t o m i n i n g o f a s s o c i a t i o n r u l e o f t e m p o r a l d a t a k e y w o r d s ：m t 衄a l i t y s e t , s u p p o r t d e g r e e , c o n f i d e n c e d e g r e e ，把m p 0 耐a s s o c i a t i o n r u l e 西南交通大学硕士研究生学位论文第1 页 1 1 形成本论文的背景 第1 章绪论 面对信息社会中数据和数据库的爆炸式增长，人类分析数据和从中提取 有用信息的能力远远不能满足实际需要。虽然数据库管理系统( d b m s ) 可以 高效实现数据录入、检索和维护等管理功能，但不能发现数据中的关联和规 则，也不能根据现有的数据预测未来的发展趋势。所以，迫切需要一种能够 智能地、自动地把数据转换成有用信息和知识的技术和工具。需求是发展之 母，数据库管理系统和人工智能中机器学习两种技术的结合和发展，促成了 在数据库中知识发现( k d d ) 这一新技术的诞生。 数据挖掘是2 0 世纪9 0 年代中期兴起的一项新技术，它是知识发现过程 中的关键步骤。所谓数据挖掘，就是从数据库中抽取隐含的、以前未知的、 具有潜在应用价值的信息的过程。近些年来，它引起了信息产业界和理论界 的极大关注，并吸引了一大批研究者和开发者。 关联规则挖掘作为数据挖掘的一种重要模式，已成为数据挖掘领域的一 个非常重要的研究课题。所谓关联规则挖掘是：从海量数据库提取给定数据 项集的有趣模式。它在管理、生产控制、市场分析、工程设计、科学探索等 领域都有着重要的应用。目前又逐渐向生物医学、金融设计、电信等领域渗 透。 由于现实世界是不断演变进化的，时间是那些反映现实世界信息的基本 部分，因而大多数数据库应用程序都有时态的特性，例如：会计，银行等财 经类的应用程序；人事培训、酒店预定、项目管理等记录性应用程序，天气 监测等科学类应用程序。传统的数据库管理系统对时态信息的存储、处理和 操作都十分有限，正因为传统数据库缺乏对时态数据的支持，因而在很多方 面产生了很多问题，例如：它把时间数据作为一个字段的值进行存储和管理， 只反映了对象某一个时刻或当前时刻的信息和状态，不联系对象的历史、现 在和将来，无法将对象的历史、现在和将来作为对象的一个发展过程来看待， 而这样做有助于揭示事物发展的本质规律，抓住事物的发展趋势( 这一点对 于像决策支持系统这类的应用程序来说是很基本、很重要的) ：同时要求管理 数据库系统中元事件的时态信息，例如数据库被查询修改的时刻，时间区间。 多用户系统中对锁定排队以及资源竞争协调的时标等，这些时态数据也有助 于提高数据库系统的可靠性和效率。随着数据库技术的不断发展，人们开始 西南交通大学硕士研究生学位论文第2 页 逐渐意识到有必要为时态数据建立时态数据挖掘模型，或者在现有的数据库 模型上加以改造。 基于以上情况，本论文结合粗糙集、模糊集和不确性推理等理论就时态 数据关联规则挖掘中的一些模型与算法等问题进行研究。 1 2 目前国内外研究现状分析 时态数据目前大体分为三大类【lo 】：一是数值型序列，即传统意义上狭义 的时间序列；二是事务型序n ；- - 是事件型序列。 关联规则挖掘起源于事务型序列，最早提出是1 9 9 3 年i b m 公司a l m a d e n 研究中心r a m a k r i s hs t r i k a n t 和r a k e s h a g r a w a l 提出的经典关联规则挖掘算法 a 研o r i 算法【2 1 。该算法的核心是寻找频繁项目集，主要基于这样一个性质 ： 频繁项目集的所有非空子集必为频繁项目集。但由于该算法效率比较低，产 生太多冗余规则，并且缺乏可靠性及可扩展性，因此众多的研究者提出了许 多改进策略，它们的主要有：基于采样的策略；基于分片的策略【3 卅；动态项目集 计算策略m ；剪枝策略；基于h a s h 表的项目集计算策略【4 7 ，4 9 1 ；项目集与标号集同 时使用策略；基于限制的策略【4 6 】等等。 在这些思想的推动下也就产生了许多比较有名的算法象基于闭项目集的 c h a r m 算法；f p g r o w t h 算法 i , 2 1 ；c l o s e t 算法1 ；g e n m a x 算法m 1 和 m a g n u m o p w s 算法【l 2 】等等。在这些算法中给出了关联规则挖掘领域中几种 好的理念，其它对它们的改进算法都从某种程度上提高了算法的性能。从它们 研究思路来讲有这样几个着眼点【9 】： ( 1 ) 数据库的处理技术。如整个数据库的采样；有效的剪枝策略减小搜索 空间；数据库分片( 并行处理) ；对数据库进行压缩( 内存中处理) ；多处理 器搜索数据库等。 ( 2 ) 搜索策略。如深度优先：广度优先：自底向上；自顶向下等。 ( 3 ) 支撑度、信任度的计算方法。h a s h 法；标号法；频繁法等。 应用的发展促进了相关理论的建立、发展和完善。就其理论研究而言， m a n n i l a 等人做了一些有益的工作。总的来说有以下几种观斛l 】：数据挖掘的 统计和机器学习观点；概率分布观点；数据压缩观点；微观经济观点；归纳 数据库观点；和比较重要的闭频繁项集挖掘中正规概述分析等。 数据库领域国际知名学者加拿大s i m o n f r a s e r 大学的m k a m b e r t 4 ”和h a n j i a w e i ( 韩家炜) 在2 0 0 1 年提出，一个理想的理论框架应满足如下要求： ( 1 ) 能够对典型的数据挖掘任务( 如关联、分类和聚类) 进行建模； 西南交通大学硕士研究生学位论文第3 页 ( 2 ) 有一个概率特性； ( 3 ) 能够处理不同形式的数据，并且对数据挖掘的反复和交互的本质加 以考虑。 就现有的理论来说，还没有一种理论框架能同时满足这3 条要求。 普遍认为：数据挖掘作为数据库技术、人工智能、统计学等学科的交叉 学科，很难找到一个合适的、全面的理论框架。这一框架必须建立在这几门 学科相关概念、思想的基础之上。首先需要解决的问题是怎样对数据挖掘各 种任务给一个比较形式化的描述，然后考虑数据挖掘的整个过程才能建立一 个合理的数据挖掘理论框架。因此总的来说，关联规则挖掘的理论框架乃至 整个数据挖掘理论都有很长的路要走，这也是目前数据挖掘领域一个具有挑 战性的工作。 关联规则的成功应用也促使了它向其它类型数据库渗透比如时态数据库 中的时间序列和具有时态约束的数据处理。 在时间序列分析领域，由于实际应用中时间序列具有不规则、混沌等非 线性特征，使得预测系统未来的全部行为几乎不可能，对系统行为的精确预 测效果也难以令人满意，传统的时间序列分析方法不再适应。这使得人们不 得不在解决时间序列问题的思路上，由原来的应用概率论、随机过程等纯数 学的方法逐渐转向为引入模式识别、机器学习等人工智能技术和数学手段结 合的方法。在这方顽比较成功的应是1 9 9 9 年r i c h a r dj p o v i n e l l i 在他的博士论 文中提出了一种时间序列数据挖掘( t i m es e r i e s d a t a m i n i n g ) 的框架( 这只是一 个方面) 。从本质上讲，他是将时序分析预测目标的范围由原来的系统未来行 为的全集缩减到满足事件闽值的子集，而相应的时序建模也由原来的数学表 达式改为由规则表示的模式集表达。他的这一尝试引起诸多学者的兴趣。 用基于r o u g h 集理论来分析时间序列，目前也取得了一些成果：文 3 0 1 使用动态编程方法来检测时间序列的模式；文【2 3 使用r o u g h 集利用动态简约 对市场数据进行了分析，取得了成功；文【2 4 】提出了时态信息系统( t e m p o r a l i n f o r m a t i o ns y s t e m ：t i s ) 和实时时态信息系统( r e a l t i m et e m p o r a li n f o r m a t i o n s y s t e m ：r t t i s ) 的概念等等。 关于时态约束的数据采掘国内外都已经有了些研究，但是对于时态约束 的关联规则研究并不很多，主要存在以下几个问题：时态关联规则的科学描 述问题，如何给出有效快速的算法，规则如何评价与分析等等。目前国内欧 阳为民与盂志青取得了许多成果1 2 7 , 2 8 , 3 4 j 8 j 8 1 ， 由于人类知识的固有特点，即不完全性、不确定性和不一致性，因而导 西南交通大学硕士研究生学位论文第4 页 致在数据源中模糊性随处可见，将模糊思想引入关联规则的挖掘已成为一个 较新的研究内容。 因此，关联规则挖掘主要存在以下几个方面问题【7 ，9 j ： ( 1 ) 算法在性能上有待改进，尤其是并行性和可扩展性： ( 2 ) 整个数据挖掘算法目前还没有一个统一的理论框架，这不仅包括算 法理论基础及其模型，还包括算法复杂性问题、取样定理的研究等。 ( 3 1 关联规则挖掘的新的应用领域。 基于此，关联规则目前和今后一段时间的发展主要集中在【7 ，9 】： ( 1 ) 寻找高性能的关联规则挖掘算法。 ( 2 1 建立关联规则挖掘乃至整个数据挖掘的理论框架。 ( 3 ) 模式或规则的兴趣度的研究。 ( 4 ) 寻找与其它类型数据库的融合。 ( 5 ) 开拓新的应用领域。 1 3 本论文的主要内容 本论文主要对时态数据关联规则中一些模型与算法进行探讨、对比、研 究。内容作如下安排： 一、基于相关集合的事务数据库挖掘 研究了相关集合这一挖掘思想的方法；借助包含度推导了由此建立的信 任度与r s ( t o u g hs e t ) 精度的联系：分析一种融合挖掘分类与关联的方法。 二、基于r s 的时间序列的挖掘 介绍r s 及时态信息系统与实时时态信息系统的有关概念；改进和推广了 一种更具有实用价值由t i s 转化为i s ，r t t i s 转化为t i s 的方法；总结了基 于时间窗口技术的r s 挖掘时间序列常用策略。 三、时态关联规则挖掘 研究了时态型、时态空间和一般时态关联规则的定义，并将其运用到事 务数据库中，研究了时态关联规则的时效性的一种处理方法，并就时态关联 规则的有效性问题给出了它的算法与应用。 四、模糊关联规则挖搌 根据国内程继华等人对模糊关联规则及挖掘算法实现的研究，以其为例 探讨了模糊思想引入数据挖掘的方法。 西南交通大学硕士研究生学位论文第5 页 第2 章基于相关集合的事务数据库挖掘 在事务数据库中挖掘频繁项就是要发现满足用户最小支持度m i n s u p p 的 所有项目集，特别是发现最大频繁项集。这一任务包含两方面的要求：事务 组合数的要求和项目组合的要求，支持度的本质是对事务组合数的要求，最 大频繁项是对项目组合的要求。因此挖掘最大频繁项就是发现满足条件：( 事 务项的组合下界 一m i n s u p p ) n ( 项目组合长度 o ) 的所有项目集合。 这样一个给定的事务数据库关联规则挖掘本质上不仅体现在频繁项的计 数特征上，而且体现在事务项组合和项目组合的结构信息上。相关集合的思 想将为它建立了较好的理论基础，尤其重要的是由它所定义的信任度通过包 含度将粗糙集中的精度联系了起来。 本章在介绍相关集合思想的基本理论下，通过包含度理论将它与r o u g h 集精度联系起来进行对比分析，同时运用包含度推导了该思想下的增量支持 度、信任度的计算公式。 2 1 相关集合定义 定义2 1 el m s 设t 是由n 个事务项( 标识) 组成的一个事务项集合，称其 幂集p ( t ) 为事务空间或t 空间。 定义2 2 【l i - ”j 设x 是由m 个物品项目( 标识) 组成的一个项目集合，称 其幂集p ( x ) 为项目空间或x 空间。 这样一个给定的事务数据库本质是建立在t 、x 两个空间上的一个关系。 设项目集x = x l ，x 。 ，事务集t = t l t 。) ，那么事务数据库就是定义在t x 上的一个关系r ，r c ：。t x 。 定义2 3 n - 1 6 1 ( 事务相关集和项目相关集) 设项目集x = x l x 。) ，事务集 t = t 1 t 。) ，事务数据库r t x 。把所有与t i 有关系的项目用集合表示出来， 即【t i r = x i l ，x i p ) ，称为事务t i 的相关集合：同理，把所有与x j 有关系的 事务项用集合表示出来，得 x j 】r = l 一，q q ) 集合，被称为项目x j 的相关集 合。 这样，一个具体的商品集x 另一方面又是所有与x 有关系的所有事务集。 2 2 基于相关集合的支持度和信任度 关联规则是形如x j y 的蕴涵式，由上述分析x ，y 既是交易商品，同时 西南交通大学硕士研究生学位论文第6 页 又是事务集合，x ct ，y t 因此相应的支持度s u p p o r t ( x j y ) 和可信度 c o n f i d e n c e ( x jy 1 可表示为： s u p p o r t ( x j y ) = ix n yl iti c o n f i d e n c e ( x 寸y ) = ix n y1 ixl 它们分别表示事务库中同时包含x 和y 的事务数与所有事务数之比，和 包含x 和y 的事务与包含x 的事务之比。 注意2 1 ：x 和y 在这里表示的是它的相关集合即事务集合而不是商品i 集所以一般x n y 巾。 注意2 2 ：x 和y 本身又代表具体的商品，是一种或几种商品标识构成 的符号串，并且不重复。例如x = x l x 2 代表标识为x - x 2 的两种商品，从集合 上说是x 又是x l ，x 2 两个事务集的交集。 2 3 集合映射及性质 2 3 1 集合映射 定义2 3 1 5 】给定项目集合x 和事务集合t ，称映射f x t 为x 到t 的 集合映射，简记为x t 映射。 定义2 4 【1 1 1 5 】给定项目空间x 和事务空间t ，称映射g ：t x 为t 到x 的集合映射，简记为t x 映射。 注意2 3 ：f 是一个为2 x 到2 1 的集合映射，g 是一个2 1 到2 x 的集合 映射。 定义2 5 1 1 1 - 1 5 1 给定一个事务数据库，如果项目集x = x i , x 2 。，x p ) ，每个项 目相关集【x j l r _ b 1 ，t j , ) j = 1 , - - p ，令f ( x ) = 【x 1 an 【x 2 h n 【x p r = t i l , - - , t j q ) ， 那么 t j l t j 。) 是x 的一个相关集合，f 是事务数据库的x t 映射。 同理，如果t _ t 1 ，q ，令g ( t ) = 【h r t n t 2 h n 【t s 】r _ x l ，x i k ，那么 x 1 1 ， x i k ) 是事务集t 的一个相关集合，g 是事务数据库的t x 的映射。 这样任给一个项目集合，利用x 到t 的映射f i x ) ，必有一个事务集与之对 应；反之给定一事务项集t = t l ，一t q ) ，利用t x 映射可以求出t 对应的所有 相关项目集x 。 这个定义在事务数据库关联规则挖掘中有较重要的理论分析价值。显然 这里的f ，g 是相关集合之间的一种映射。下面讨论它们的有关性质。 2 3 2 映射的性质 西南交通大学硕士研究生学位论文第7 页 性质2 1 1 5 1 如果x - - - - 一a lux 2 , 那么“x ) = “x 1 ) nf ( x 2 ) 。 证明设x l = x l l ，x 1 2 x 1 p ) ，x 2 = x 2 1 ，x 2 2 x 2 。) ，那么x = x lux 2 = x i i , x 1 2 x l p ，x 2 b x 2 2 x 2 q ，f ( x ) 2 f ( x i u x 2 ) = f ( x l l ，x 1 2 x l p ，x 2 1 ，x 2 2 x 2 。 ) = i x l l 】r n 【x 1 2 rn 。一n x i p rn 【x 2 1 rn 【x 2 2 rn n 【x 2 q r 2 ( x 1 1 rn x 1 2 rn n x i p 】r ) f 7 ( 【x 2 1 rn 【x 2 2 rn f 7 x 2 q j r ) 2f ( x 0nf ( x 2 ) ，其中f ( x 0 2 【x 1 1 rf l 【x 1 2 rn n 【x l p r ，f ( x 2 ) 2 x 2 1 rn 【x 2 2 rn n x 2 q r 。 性质2 2 如果t = hu t 2 ，那么g ( t ) = g ( t 1 ) n g ( t 2 ) 。 证明略。 性质2 3 如果x i x 2 ，那么f ( x 2 ) - g - f ( x i ) ；反之如果f ( x 2 ) 量f 心1 ) ，那 么x l x 2 。 证明略 定理2 1 【l l - 1 5 】设r 是事务数据库，t 是事务集合，x 是项目集合。如果t 中，g ( t ) = x 巾，那么t f ( x ) = f ( g ( t ) ) ；反之，如果x 巾，f f x ) - = t 巾，那么 x g ( t ) = g ( f ( t ) ) 证明略 该定理说明在t ，x 集合映射过程中支持度不会减小，项目长度也不会减 短。也就是说，若x 不变，则lf ( x ) i 是x 的最大支持度；若t 不变，g ( t ) 是t 对应的最大项目集。f ，g 不是互逆的映射。 定理2 2 设r 是事务数据库，x 是r 的一个频繁项，如果lf ( x ) i = m i n s u p p ， 那么g ( f ( x ) ) 是含有x 的最大频繁项，并且是唯一的最大频繁项。其中，f ( x ) 和g ( t ) 分别是x t 映射和t x 映射。 证明略。 定理2 3 1 1 - 15 1 设r 是事务数据库，x 1 x 2 是r 的2 个频繁项集，如果 f ( x 1 ) f 2 ) ，那么x lux 2 是一个更大的频繁项集。其中，f ( x ) 是x t 集合映 射。 证明设x 1 = x 1 1 x 1 2 x i p ) ，x 2 = x 2 1 ，x 2 2 x 2 q ) ，则x = x lu x 2 = x i i ，x 1 2 x i p x 2 1 ， x 2 2 ，x 2 q ) ，f ( x ) = f ( x l u x 2 ) = f ( x l l ，x 1 2 x 1 p x 2 1 ，x 2 2 x 2 0 2 【x d r n 【x 2 ：f ( x 1 ) f 7 f ( x 2 ) 因为f ( x 1 ) f ( x 2 ) 所以f 球) = f ( x 1 ) n f ( x 2 ) = f ( x 0 又因为x 1 x 2 是频繁项集， s u p p o r t ( x 1 ) 大于用户给定的最小支持度，所以if ( x ) l - 1f ( x t ) i 大于最小支持 度，x = x 1 u x 2 是频繁项。 推论设r 是事务数据库，x l ，x 2 是r 的2 个频繁项集，如果f ( 。1 ) f ( x 2 ) ，x = x lu x 2 , 那么g ( f ( x 1 ) ) 是支持度为if ( x 1 ) f 且含有x iu x 2 的大频繁项。其 中，“x ) 是x t 集合映射。 西南交通大学硕士研究生学位论文第8 页 定理2 4 【l 。”1 设r 是事务数据库，t l , t 2 是r 的2 个事务项集，如果 g ( t 1 ) 互g ( t 2 ) ，那么t lu t 2 是支持g ( t i ) 的事务项集，或者说g ( t 1 ) 的支持度为it lu t 11 。因为g ( t ) 是t x 集合映射。 证明设x 1 2 9 ( t 1 ) ，t = t lut 2 因为g ( t lut 2 ) = g ( t 1 ) f 7g ( t 2 ) ，g ( t 1 ) g ( t 2 ) ，所以 g ( t ) = g ( h o t 2 ) = g ( h ) n g ( t 2 ) = g ( t 1 ) ，所以g ( t 1 ) 是t 1 的相关项目集，也是t = t l u t 2 的相关项目集。因此x l = g ( t 1 ) 的支持度为lt 1u t 2l 。 推论设r 是事务数据库，t l ，t 2 是r 的2 个事务项集，如果x = g ( t 1 ) n g ( t 2 ) 中，那么t l u t 2 是支持x = g ( h ) 1 7 9 ( t 2 ) 的事务项集，或者说x 的支持度为i t 1 u t 2i 。其中，g ( t ) 是t x 集合映射。 定理2 5 。5 j 设r 是事务数据库，t l 是r 的1 个事务项集，如果i “g ( t 1 1 ) i = m i n s u p p ，那么g ( t 1 ) 是由t l 确定的晟大频繁项，并且是唯一的最大频繁项。 其中，f ( x ) 和g ( t ) 分别是x t 映射和t x 映射。 推论设r 是事务数据库，t l 是r 的1 个事务项集，如果if ( g ( t 1 ) ) i m i n s u p p ，那么g ( t 1 ) 是由t l 确定的频繁项，最大支持度是if ( g ( t i ) ) 1 其中f ( x ) 和g ( t ) 分别是x t 映射和t x 映射。 推论设r 事务数据库，t 是r 的1 个事务项集，if ( g ( t ) ) i = m i n s u p p ，x = g ( t ) 是频繁项，如果t l 是r 的1 个事务项集，t 2 是包含t l 的任意事务项集，x l = g ( t 1 ) ， x 2 = g ( t 2 ) ，如果x lc _ x ，x _ g ( t ) ，if ( g ( t ) ) i 一m i n s u p p ，那么x 是包含x 2 的大频繁项 集，也就是说x 包含了由t 生成的所有频繁项集。 证明因为x 2 9 ( t ) ，1f ( g ( t ) ) 1 m i n s u p p ，所以x 是频繁项。又x l s x x l 也是频繁项。又t - 至，t t 得g ( tz ) c _ g ( t 。) ，所以x 。互x ，x ，即x 。是频繁 项，x 是包含x 2 的大频繁项集。因为t 2 是包含t 的任意事务项集，也就是说所 有含有t 的任意事务项集t z 所对应的项目集g ( t 2 ) 都是x 频繁项的子集，x 包含 了由t 。生成的所有频繁项集证毕 2 4 基于相关集合的挖掘方法 通过上述理论分析：挖掘频繁项可以通过t , x 集合映射在两个不同集上 进行搜索，由于这两映射充分利用了事务项集和项目集两个集合结构上的有 用信息，从而压缩了频繁项的搜索空间。 。 根据搜索的次序可以分为项目优先搜索和事务优先搜索两种基本方法。 下面仅就基于项目优先的搜索方法进行讨论，事务优先搜索类似。 西南交通大学硕士研究生学位论文第9 页 2 4 1 项目优先搜索算法设计 l 、计算每一个项目的事物相关集： x j 】r - l t j ；) j = 1 m ： 2 、算每一个事务项的项目相关集：【t i r = x i l x i p ) ，i _ 1 n ； 3 、设用户给定的最小支持度为m i n s u p p ，删除l x j rl ( m i n s u p p 的项 目，k = 2 ： 4 、a p r i o r i 方法把项目 x j r 组合成长度为k 的频繁项集：l k = c k l , c k 2 c k q ) ，ll ki2 q ； 5 、对l k 中的每个频繁项计算：f ( c k j ) ( i - 1 ，2 ，q ) ，按lf ( c k i ) i ( 频繁项所 含事务项的多少) 由小到大分成3 类： l k l 频繁项满足lf ( c k oi = m i n s u p p ( i = l r 0 ，有r 1 个； l k 2 频繁项满足l “c k j ) i = m i n s u p p + 1 ( j = l r 9 ，有r 2 个； l k 3 频繁项满足lf ( c k l ) i ) m i n s u p p + l ( 1 = 1 r 3 ) ，有r 3 个； 合起来r l + r 2 + r 3 = q ： 6 、优化：从l 小l i c 3 中分别减去包含c k i ( c k i l k l ) 的频繁项集； f o r i - - 1t or 1 f o r j 2 1t 0 1 2 i f f ( l k t + c k i ) e f ( l l a c k j ) t h e nl k 2 ：2l k 2 - - c k j e n d f o r f o r i = it or 3 i f f ( l k t c k i ) ) f ( l m + c k l ) t h e nl k 3 ：= l k 3 一c 1 c 】 e n d f o r e n d f o r p ：= ll k 2l 从l k 3 中减去包含c k i ( c k j l k 2 ) 的频繁项集； f o r j 2 1t o p f o r l = 1t 0 1 3 i ff ( i 地c k j ) f ( l k 3 c k ot h e nl k 3 ：= l k 3 一c k l e n d f o r e n d f o r 7 、分类处理频繁项集l k ； ( 1 ) 对l k l 频繁项，计算g ( f ( c k i ) ) ，把映射结果添加到l k 中； ( 2 ) 对l k 2 频繁项，如果r 2 = i 那么 a 、把集合f ( c k j ) 组合成r 2 个长度为m i n s u p p 的事务项( 满足最小支 西南交通大学硕士研究生学位论文第1 0 页 持度的) 相关集t i ； b 、对每个事务项集计算g ( t i ) ( 映射) ( t x 频繁项) ，得项目相 关集； c 、同l k 中的频繁项相比较，如果结果没有新的频繁项，那么转3 ： d 、对新频繁项，用f ( g ( t i ) ) ( x t 映射) 把项目相关集转换成事务相 关集； e 、再用t x 映射，事务相关集转换为项目相关集；并添加到l k 中； ( 3 ) 对l ”频繁项，按a p r i o r i 方法把l k 3 频繁项合成长度为k + 1 的新频 繁项； 8 、果新频繁项集非空，那么k - - k + l ，转5 ，否则转9 ； 9 、输出频繁项批； 1 0 、结束算法。 2 4 2 应用举例 例2 1 设有事务数据库如图2 。l 所示。给定最小支持度为3 ，求所有最大频 繁项集合。 t i d i t e m s t 1x 1x 2x 3x 4x 5 t 2x 2x 3x 4 t 3x 3x 4x 5 t 4x 1x 2 t 5x 1x 3x 5 t 6x 1x 3x 4x 5 - 图2 1 事务数据库 解：( 1 ) 计算相关集合： 【x 1 r 2 t 1 ，“，t 5 ，t 6 ) ； x 2 r = t l ，t 2 ，t 4 ) ；【x 3 r = t l ，t 2 ，t 3 ，t 5 ，t 6 ， 【x 4 a = t l ，t 2 ，t 3 ，t 6 ) ；【x 5 r = t l ，t 3 ，t 5 ，t 6 ，) ； t 1 r 2 x l ，x 2 ，x 3 ，x 4 ，x 5 ) ；【t 2 r = x 2 ，x 3 ，x 4 ；【t 3 r 。 x 3 ，x 4 ，x 5 ) ； 【t 4 r 2 x l ，x 2 ) ；【t 5 】r 2 x l ，x 3 ，x 5 ) ；【t 6 r = x l ，x 3 ，x 4 ，x 5 ) ； 西南交通大学硕士研究生学位论文第1 1 页 ( 2 ) 计算k - - 2 时的频繁项：l k = x l x 3 ，x l x 5 ，x 3 x 4 ，x 3 x 5 ，x 4 x 5 ； ( 3 ) 由映射f 做x t 转换： f f x l x 3 ) 。 t l ，t 5 ，t 6 1 ，f f x l x 5 ) 3 t l ，t 5 ，t 6 ，) ，f ( x 3 x 4 ) 2 t l ，t 2 ，t 3 ，t 6 ) f f x 3 x 5 ) = t l ，t 3 ，t 5 ，t 6 ) ；f f x 4 x s ) = t l ，t 3 ，t 6 ； ( 4 ) 排序、分类：l k l = x l x 3 ，x l x 5 ，x 4 x 5 ) ；l k 2 = x 3 x 4 ，x 3 x 5 ) ( 5 ) 优化：因为f ( l k l x l x 3 ) c _ f ( l k 2 x 3 x 5 ) ，f ( l k | 。x 4 x 5 ) c f ( l k 2 x 3 x 4 ) ， 所以，l l 【2 = x 3 x 4 ，x 3 x 5 一( x 3 x s 一 x 4 x 5 2 0 ； ( 6 ) 分类处理。只有1 类恰好满足最小支持度：l k ! = x l x 3 ，x l x 5 ，x 4 x 5 ) ； 计算t - x 映射：g ( t 1 $ 5 ，t 6 ) = x l ，x 3 ，x 5 ，g ( t l ，t 3 ，t 6 ) = x 3 ，x 4 ，x 5 ) ； 因此，最大频繁项为： x l ，x 3 ，x 5 ) ，和 x 3 ，x 4 ，x 5 ) ； 全部频繁项为： x l ，x 3 ； x l ，x 5 ； x 4 ，x 5 ； x 3 ，x 4 ) ， x 3 ，x 5 ) ； x l x 3 ，x 5 ) ； x 3 ，x 4 ，x s 2 5 包含度与信任度、r o u g hs e t 精度 2 5 1 包含度的定义 定义2 6 1 1 7 - 1 9 | 包含度是指一个集合a 包含于一个集合b 的程度，记为 d ( b a ) 。它是一种处理不确定性研究的方法，是对“包含关系”的扩充，从 而包容了“关系”的不确定性，满足以下公理： 公理2 1 0 d 0 3 a ) 一1 公理2 2ac b 时d ( b a ) = i 公理2 3a 亡bc c 时d ( a c ) 一 d ( a b ) 公理2 4ac b 时对于任意c 有d ( a c ) d ( b c ) 上面四条公理是针对经典子集定义的，公理2 1 是包含度的规范化，包含 度在【o ，1 】中取值；公理2 2 是包含度和经典包含的协调性，经典包含关系是包 含度为1 的特殊情况：公理2 3 、公理2 4 是包含度的单调性。粗略地说，一 个较小集合比较容易包含于一个比较大的集合中。 若a 、b 是经典有限集，通常情况下，用以下方法来定义一个集合b 包 含集合a 的程度： 西南交通大学硕士研究生学位论文第12 页 ri a n bl lala 巾 d ( b a ) = l 1a = 中 这里lai 表示集合a 的基数，它在数据挖掘方面具有重要的应用价值。 它具有如下的运算性质： 性质2 4 d ( a a ) = i ，一般有o d ( ) ( a ) 1 证明略。 性质2 5d ( x a ) = i 一( 1 la1 ) ( ia u xi lx1 ) 证明因为ia n xl = lal + ix1 一la u xi ，所以ia n x i ，lai = 1 + ( 1 ia1 ) ( 1xi ia u x1 ) = 1 - ( 1 iai ) ( 1a u x i lx i ) 同理可证明下面的性质 性质2 6 d ( x i ( a i n a j ) ) = 1 - - ( 1 la i na j1 ) ( 1 ( a i na j ) u x i ix1 ) 性质2 7 d ( x ( a i na j ) ) 一- ( 1 ia i ua ji ) ( ia i ua j u xl lx1 ) ( 1 ia i ua ji ) ( ia l l d ( x a i ) + la jid ( x a j ) ) d ( x a i ) + d ( x a j ) 性质2 8 d ( ( x ln x 2 ) a ) = ix l n x 2 n ai la i = ( 1 ( ) ( 1n x 2 ) n ai l x l n x 21 ) ( 1x ln x 2l ，ia1 ) = d ( a ( x i n x 2 ) ) ( ix ln x 2l lai ) 性质2 9 如果集合x l x 2 呈u 和任意集合a ，则d ( x l a ) d ( x 2 a ) 性质2 1 0 如果集合x l ，x 2 u ，则对于任意集合a ，有d ( ( x i n x 2 ) a ) = d ( ) ( 1 a ) + d ( x 2 a ) 一d ( ( x i u x 2 ) a ) ，d ( x i a ) + d ( x 2 a ) d ( ( x 1 u x 2 ) a ) o 。 性质2 11d ( ( x l u x 2 ) a ) = d ( x l a ) + d ( x 2 a ) 一d ( ( x l n x 2 ) a ) = d ( x , a ) + d ( x f f a ) 一d ( a ( x l n x 2 ) ) ( 1x l n x 2i i ai ) 显然，如果x l n x 2 = 由， 则d ( ( x 1 u x 9 a ) = d ( x 1 a ) + d ( x 2 a ) 2 5 2 信任度、r o u g hs e t 精度与包含度 由前所定义的基于相关集合的信任度c o n f i d e n c e ( x o y ) = lx nyl lxi 。它体现的是包含x 事务数集中包含y 事务数集的程度。显然它是一 种包含度。在r o u g h s e t