（计算机应用技术专业论文）使用长度递减支持度挖掘兴趣频繁模式和子空间.pdf

亘主整燕盘芏塑硷塞 擅墨 摘要 频繁模式是指数据集合中的项集、子序列或者子结构j 它们出现的频繁度不少 于用户设置的阈值。频繁模式在挖掘关联规则、相关规则和数据间的其它有趣关系 方面扮演着重要角色，此外它还可用于数据检索、分类、聚类等其它挖掘任务。因 此，频繁模式挖掘是一项重要的数据挖掘任务，且已成为数据挖掘研究中的焦点课 题。 本文对如何挖掘兴趣频繁模式及其在子空间聚类中的应用进行了研究。重点研 究了以下两个阀题：l d s 一闭包频繁项集的垂直挖掘算法；如何使用l d s 频繁项集 评估子空间的质量。本文的研究成果及创新内容主要包括以下几个方面： 【1 】提出了l d s 闭包频繁项集的垂直挖掘算法l d sc l o s e d 。 【2 】提出了两种新的搜索空间剪裁方法：无效前缀剪裁和基于s v e 性质的剪裁。 【3 】试验结果表明，l d s _ c l o s e d 不仅能够有效地控制频繁模式的数量，而且 运行效率也远高于闭包频繁模式挖掘算法。 4 提出了一种适用于分类数据集的予空间质量度量方法；其特点是无需用户输 入一些难以估计的参数，很好地体现了“无指导学习”的观点。 【5 】在子空间质量与l d s 一( 闭包) 频繁项集之间建立起联系，从而解释了使用 l d s 约束条件的合理性。 关键词：兴趣频繁模式，长度递减支持度，分类数据集，子空间聚类 辽宁科技大学硕士论文 a b s t r a c t f r e q u e n tp a t t e r n sa l ei t e m s e t s ，s u b s e q u e n c a s ，o rs u b s t r u c t u r e st h a ta p p e a r i nad a t a s e t w i t hf r e q u e n c yn ol e s st h a nau s e r - s p e c i f i e dt h r e s h o l d f r e q u e n tp a t t e r n sm i n i n gp l a ya l l i m p o r t a n tr o l ei nm i n i n ga s s o c i a t i o nr u l e s ，c o r r e l a t i o nr u l e s ，e n do t h e ri n t e r e s t i n gr e l a t i o n s a m o n gd a t a , e n dc o u l db eu s e di nd a t ai n d c x i n g ，c a t e g o r i z a t i o n , c l u s t e r i n ge n do t h e r m i n i n g t h e r e f o r e ，f r e q u e n tp a t t e r nm i n i n gi sac r i t i c a lm i n i n ge n dh a sb e c o m eaf o c u s e d t h e m ei nd a t am i n i n g i nt h i st h e s i s ，w es t u d yo nh o wt of i n di n t e r e s t i n gf r e q u e n tp a t t e r n se n da p p l yt h e mi n s u b s p a c es e l e c t i o n w ep r o p o s ean e wa l g o r i t h mw h i c hm i n e sl d s d o s e df r e q u e n t i t m s e t se n dc r e a t ean o v e ls u b s p a e eq u a l i t ym e a s u r eo nc a t e g o r i c a ld a t a s e t su s i n gl d s f r e q u e n ti t e m s e t s m a i nc o n t r i b u t i o n si n t h et h e s i si n c l u d e ： 1 】av e r t i c a lm i n i n ga l g o r i t h mc a l l e dl d s _ c l o s e dh a sb e e np r o p o s e d , w h i c h c o u l df i n dl d s d o s e df r e q u e n ti t e m s e t sv e r ye f f i c i e n t l y 【2 】t w o n o v e l m e t h o d s ，l n v a l i d p r e f i x p r u n i n g e n d p r u n i n g b a s e d 0 7 1 s i z e p r o p e r t y , h a v eb e e np u tf o r w a r dt oe f f i c i e n t l yp r u n es e a r c h i n gs p a c e 【3 】e x p e r i m e n t a lr e s u l t so nr e a ld a t a s e t ss h o wt h a t , l d s c l o s e dn o to n l yg e t s m o r ec o n c i s e p a a e ms e t , b u ta l s op e r f o r m sm o r ee f f i c i e n t l yt h a nt h ea l g o r i t h m st h a tm i n e d o s e df r e q u e n ti t e m s e t s 4 】an o v e ls u b s p a e eq u a l i t ym e a s u r eo i lc a t e g o r i c a ld a t a s e t sa l ep r o p o s e d , w h i c h r e q u i r en op a r a m e t e r sh a r dt op r e d i c t s ot h en e wm e a s u r es h o w h o n - s u p o r v i s e d l e a r n i n g b e t t e r 【5 】t h er e l a t i o n s h i pb e t w e e ns u b s p a c eq u a l i t ya n dl d s - f r e q u e n ti t c m s e t sh a sb e e n b u i kw h i c h e x p l a i n sw h yt h ei t e m s e t s n o t s a t i s f y i n gl e n g t h - d e c r e a s i n gs u p p o r t c o n s t r a i n t sc o u l db e p r u n e d k e yw o r d s ：i n t e r e s t i n gf r e q u e n tp a t t e r n s ，l e n g t h - d e c r e a s i n gs u p p o r t , c a t e g o r i c a l d a t a s e t , s u b s p a e ec l u s t e r i n g 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得辽 宁科技大学或其它教育机构的学位或证书而使用过的材料，与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意。 签名； 关于论文使用授权的说明 本人完全了解辽宁科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵守此规定) 签轹匀邋师签名：至蒸2日期：塑兰、 辽宁科技大学硕士玲文 第一章绪论 1 1 研究背景 第一章绪论 计算机与信息技术在过去几十年中得到了迅速发展，给人类社会带来了巨大的 变革和影响由工业化社会转向信息化社会。随着技术的进步，计算机的能力越 来越强、运算速度越来越快，加之超大容量的存储介质，人们产生和收集数据的能 力空前提高。此外随着万维网的流行，人们迫切需要将海量数据转换成有用的信息 和知识。 1 9 9 5 年，在美国计算机年会( a c m ) 上，正式提出了数据挖掘( d a t am i n i n g ) 的概 念。简单地说，数据挖掘是从大量数据中提取或“挖掘”知识。数据挖掘是一门交 叉学科，范围涉及机器学习、模式识别、统计学、知识获取、专家系统、数据可视 化和高性能计算多个领域。自提出以来，数据挖掘一直是信息科学与技术领域最具 挑战性的课题。 频繁模式挖掘是数据挖掘领域的一个基本问题。它首先由a g r a v a l 等人在1 9 9 3 年以关联规则的形式提出【”，当时用来做购物篮分析。通过研究顾客购物篮中不同 物品的相关性，从而发现顾客的购物习惯。比如说，一个顾客买了牛奶，他还有多 大的可能去买谷类食品( 以及买什么样的谷类食品) ? 这样的信息可帮助零售商合 理地安排货架的位置以提高销售额。 频繁模式是指数据集合中的项集、子序列或者子结构，它们出现的频繁度不少 于用户设置的闽值。比如说项集“牛奶、面包”是一个频繁项集，因为它们在事务 数据集中频繁地一起出现。像首先买p c ，然后是数码相机，然后是存储卡，如果它 频繁地出现在商店的历史数据库中，那么这就是一个频繁子序列。一个子结构可能 有多种结构形式，比如说子树、子格或者子图；此外，它们还可能与项集、子序列 掺杂在一起。如果一个子结构频繁地出现在一个图数据库中，那么它称为一个( 频 繁) 结构模式。 频繁模式在挖掘关联规则、相关规则和数据间的其它有趣关系方面扮演着重要 角色。另外，它还可用于数据检索、分类、聚类等其它挖掘任务。因此，频繁模式 挖掘是一项重要的数据挖掘任务，且已成为数据挖掘研究中的焦点课题。 辽宁科技大学硕士论文第一章绪论 1 2 国内外研究现状 过去十几年中，人们针对特定领域的应用开发了许多专用的数据挖掘工具，包 括生物医学、d n a 分析、金融、零售业和电信。这些实践将数据分析技术与特定的 领域知识结合在一起，提供了满足特定任务的数据挖掘解决方案。还有一些研究人 员致力于建立数据挖掘的理论基础，并且已经提出了一些有意义的成果，包括数据 规约，模式发现，概率理论，数据压缩，微观经济理论，以及归纳数据库。h a r t 在 数据挖掘：概念与技术【2 】一书中概括介绍了数据挖据技术的各方面。 数据挖掘发展趋势包括：新应用的探索和处理复杂数据类型的新方法，算法的 可伸缩性，基于约束的挖掘和可视化方法，数据挖掘与数据仓库和数据库系统的集 成，数据挖掘语言的标准化，以及数据隐私保护与安全。 自从频繁模式挖掘提出以来，人们开发了许多高效的频繁模式挖掘算法【3 】【4 】嘲。 目前，此类算法的瓶颈已经不在执行效率方面，而是在于如何处理如此庞大的挖掘 结果。 为了有效地去除冗余的频繁模式，研究人员提出了闭包频繁模式挖掘【6 1 和最大 频繁模式挖掘【_ 7 l 的概念。从闭包频繁模式集合能够推出所有的频繁模式以及它们的 支持度，并且闭包频繁模式的数量要远远少于频繁模式的数量，因此闭包频繁模式 是频繁模式的一种好的替代。最大频繁模式虽然有助于发现较长的模式，但是丢失 了短模式的部分信息支持度。 人们通常只希望看到或使用自己感兴趣的频繁模式，然而怎样的模式才是有趣 的呢? 不同的用户或者应用领域对于同模式有着不同的兴趣程度。最近有许多工 作研究如何定义兴趣频繁模式以及如何有效地挖掘它们。这些工作包括挖掘基于约 束的频繁模式、挖掘不完全或压缩模式( 枷i n i n gi n c o m p l e t eo rc o m p r e s s e dp a t t e r n s ) 、 兴趣度和相关性分析。 直观上，具有高支持度的短模式通常是有趣的，而具有相对低支持度的长模式 也仍然是有趣的。这就要求支持度阈值随着模式长度的增加而减小。于是，有人提 出了在长度递减支持度( l e n g i l l - d e c r e 鹪i n gs u p p o r t ，简写为l d s ) 绚g 条件下挖掘频 繁项集和闭包频繁项集的观点1 8 】。本文称之为l d s ( 闭包) 频繁项集挖掘，它属于 兴趣频繁模式挖掘中的基于约束的频繁模式挖掘方法。 2 辽宁科技大学硕士论文 第一章绪论 1 3 本文的工作 1 3 1 研究目标 在上一部分提到的l d s ( 闭包) 频繁项集挖掘算法都使用了水平格式表示数据 集，而对于另外一种重要的数据表示形式垂直格式，还没有对应的l d s ( 闭包) 频繁项集挖掘算法。使用垂直格式表示数据集的理由如下： 1 】挖掘结果含有支持 频繁模式的事务集合，而不仅仅是支持度；这对于某些应用可能很有用。 2 更重 要的是，它能够支持一种节省存储空间的闭包检测方法。传统的闭包检测方法需要 将已挖掘出的闭包频繁项集缓存起来，当挖掘结果的规模越来越大，闭包检测的效 率下降得很快。 长度递减支持度约束条件不受领域知识的限制，因此具有一般性。过去的研究 只是在直观上说明了使用长度递减支持度约束条件有助于剪裁掉某些无趣的模式； 对于为什么能够剪裁掉那些不满足l d s 约束条件的频繁模式，并没有给出真正合理 的解释。这也是需要解决的闯题之一。 1 3 2 研究内容 通过对研究现状和研究目标的分析，下面给出本文的主要研究内容： 【l 】提出种l d s 闭包频繁项集的垂直挖掘算法i d sc l o s e d 。该算法采 用垂直位图( v e r t i c a lb i t m a p ) 表示、压缩数据集，并使用l d s 约束条件和闭包性质对 “冗余的”频繁项集进行剪裁。 【2 】针对高维分类数据，提出一种新的子空间质量度量标准，并在该标准与l d s ( 闭包) 频繁项集之间建立起联系。 1 3 3 组织结构 本文内容i 弱绕在长度递减支持度约束条件下频繁模式挖掘的方法与应用展开， 总分为六章，具体安排如下： 第一章绪论 介绍了数据挖掘的研究背景，概述了国内外最近有关的研究动态，介绍了本文 的主要研究内容。 3 辽宁科技大学硕士论文 第一章绪论 第二章预备知识：频繁模式挖掘 该章介绍了频繁模式挖掘的相关研究内容，包括高效频繁模式挖掘方法、兴趣 频繁模式挖掘、频繁模式对数据分析和挖掘任务的影响、频繁模式的应用，以及未 来的研究方向。 第三章在长度递减支持度约束条件下挖掘频繁闭包项集 该章首先介绍了l d s ( 闭包) 频繁模式挖掘的相关研究工作；然后提出了一种 l d s 闭包频繁模式垂直挖掘算法一l d sc l o s e d ，并详细介绍了它使用的各种 策略；最后通过试验进行了算法的比较分析。 第四章子空间聚类分析 该章首先介绍了子空间聚类分析的理论基础；然后分别介绍了针对数值型数据 和分类型数据的子空间聚类方法，以及兴趣子空间选择算法；最后介绍了子空间聚 类方法的应用。 第五章l d s 频繁模式在子空间聚类中的应用 该章首先分析了已有聚类算法的不足和分类型数据集的特点，提出了针对分类 数据的子空间质量度量标准；然后给出了频繁模式挖掘与该子空间质量度量标准之 间的联系；最后提出了几个需要解决的重要问题。 第六章总结与展望 该章对全文的工作进行了总结，并对今后的工作提出了新的研究方向。 4 辽宁科技大学硕士论文 第二章预备知识：频繁模式挖掘 第二章预备知识：频繁模式挖掘 频繁模式挖掘的概念于1 9 9 3 年由a g r a v a l 等人首先提出【i j 。频繁模式是指数据 集合中的项集、子序列或者子结构，它们出现的频繁度不少于用户设置的阈值。自 从这项新的挖掘任务提出以来，出现了大量扩展和应用频繁模式的研究：具有良好 伸缩性的数据挖掘算法，不种数据类型的处理方法，各种扩展的挖掘任务，以及各 种各样的新应用。可将关于频繁模式挖掘的研究分为以下五个方面：【l 】1 频繁模式 的高效挖掘算法； 2 挖掘兴趣频繁模式；【3 频繁模式挖掘对于数据分析和挖掘应 用的影响：【4 应用；【5 研究方向。 本章内容主要参照韩家炜的频繁模式挖掘一文【9 】。 2 1 频繁模式的高效挖掘算法 2 1 1 基本挖掘方法：a p r i o r i , f p - g r o w t h , e c l a t a p r i o r i 性质、a p f i o f i 算法及其扩展 1 9 9 4 年，a g r a w a l 和s r i k a n t 发现了关于频繁k 项集的向下闭包性质：如果k 项集是频繁的，则它的所有子集都是频繁的；并称之为a p r i o r i 。挖掘步骤如下：首 先检查数据库找出所有的频繁1 项集，然后使用频繁1 项集生成候选频繁2 项集， 再次检查数据库获得所有的频繁2 项集。直到没有l c - 项集是频繁的，挖掘过程终止。 这就是a p r i o r i 算澍3 】的要点。 自从a p r i o r i 算法提出之后，出现了大量基于a p r i o r i 的改进或扩展算法。比如 说哈希技术，划分技术，抽样技术，动态项集计数，增量挖掘，并行分布式挖掘等。 g e e r t s 等人还研究了候选模式数量的上界问题( 1 0 1 ，此结果能够有效减少数据库的扫 描次数。 无候选生成的频繁项集挖掘方法 虽然利用a p f i o f i 性质能够有效地减少候选项集的数量，然而有两种计算代价不 能忽略：【l 】大量的候选项集；【2 重复扫描数据库并通过模式匹配方法检查候选项 集。h a n 等提出了无候选项生成的频繁项集挖掘算法f p g r o w i l l 【4 】。 f p g r o w t h 采用了分治策略。第一遍扫描数据库生成了一张由频繁项目组成的 表，并且表中的项目按频度递减的顺序排列。根据这张表，数据库被压缩成一棵频 5 辽宁科技大学硕士论文第二章预备知识：频繁模式挖掘 繁模式树_ f p t r e e 。对f p - i r e e 的挖掘从每一个频繁1 模式( 作为初始后缀模式) 开始，并建造它的条件模式库( 子数据库，由所有在f e - t r e e 中有此后缀模式的前缀 路径组成) ，然后构造它的条件f p t r e e ，并且在这棵树上递归调用挖掘算法。将后 缀模式同由条件f p - t r e e 生成的频繁模式串联起来就增加了模式的长度。f p g r o w t h 算法将长频繁模式的挖掘过程转化成递归地搜索短频繁模式并将其与后缀串联的过 程。 有许多f p g r o w t h 方法的变种和扩展，其中包括：a g a r w a l 等( 2 0 0 1 ) 提出的频繁 项集深度优先生成算法f l l 】；p e i 等( 2 0 0 1 ) 提出的频繁模式超结构挖掘算法【1 2 】：关于模 式增长方法中树的自顶向下和自底向上遍历策略的研究”1 4 】；基于数组的前缀树 结构挖掘方法n 卯。 使用垂直数据格式挖掘频繁项集 a p r i o r i 和f p g r o w t h 方法都是从水平格式( 也就是说， t d ：i t e m s e t ) 的事物 集合中挖掘频繁模式；还有的挖掘方法使用垂直格式( 也就是说， i t e m ：t i ds e t ) 表示的数据集。 2 0 0 0 年，z a k i 提出了e c l a t 算法 5 1 。第一遍扫描数据库建立每一项目的t i ds e t 。 从l - 项集开始，按照深度优先策略，根据a p r i o r i 性质由k - 项集生成频繁的( k + 1 ) - 项 集。计算过程就是对频繁k 项集的t i ds e t 求交集，从而生成对应( k + l 卜项集的 t i d _ s e t ；重复此过程，直至没有频繁项集或候选项集为止。 除了利用a p r i o r i 性质，e c l a t 方法的另一优点是在生成候选( 1 ( + 1 ) - 项集时不用再 次扫描数据库。这是因为k - 项集的t i d _ _ s e t 包含了计算( k + 1 ) 项集支持度的所有信 息。 2 1 2 挖掘闭包和最大频繁项集 从大规模数据集挖掘频繁模式的主要挑战是生成了满足最小支持度阈值的大量 模式，特别是当设置了一个较小支持度闽值的时候。这是因为一个频繁模式包含了 指数级数量的较小的频繁子模式。为了克服这个问题，有人提出了闭包频繁模式和 最大频繁模式挖掘。 模式口是闭包频繁模式当且仅当口是频繁模式并且不存在与口有相同支持度 的超模式a 模式口是最大频繁模式当且仅当口是频繁模式并且不存在口的超频繁模 式。x 寸= j = n - - 个的最小支持度阈值，闭包频繁模式包含了对应频繁模式的完整信息： 最大频繁模式虽然更为简洁，却没有包含对应频繁模式的完整信息。 p a s q u i e r 等人在1 9 9 9 年提出了挖掘闭包频繁模式的概念，并给出了一个基于 6 辽宁科技大学硕士论文 第二章预备知识：颇繁模式挖掘 a 谢谢的算法一a l o s d e 。其它的闭包模式算法包括：c l o s e 3 1 6 1 ，c h a r m m ， c l o s e t - 1 a 1 8 1 ，f p c l o s e 【1 5 ) 和a f o p t t l 4 1 。闭包频繁模式挖掘的一个重要问题是要检 查模式是否是闭包模式。这个问题的解决方法有两种：【l 】保存模式的t i d 列表，用 哈希表建立t i d 值的索引。c h a r m 采用此方法，并使用了一种称为d i f f s e t 的t i d 列 表压缩结构。 2 】使用类似于f p 树的模式树结构来保存已发现的模式。c l o s e t + ， a f o p t 和f p c i o s e 都采用了此方法。挖掘闭包项集为挖掘频繁项集提供了一种有 趣并且重要的替换方法，因为闭包频繁项集集合拥有与频繁项集集合等同的分析能 力，并且它的规模要小很多。 b a y a r d o ( 1 9 9 8 ) 首先提出了挖掘最大模式的算法一m a x m i 一”。m a x m i n e r 是- - 个基于a p n o d 性质的广度优先搜索算法，它利用超集频繁性剪裁和子集非频繁性剪 裁两种方法剪枝搜索空间。m a f i a 是另一个挖掘最大模式的高效算、法【旧。它使用垂 直位i 虱( v e r t i c a lb i t m a p s ) 压缩事务d 列表，大大提高了支持度的计算效率。y a n g 分析 了挖掘最大模式的( 最坏情况) 时间复杂度 2 0 l ，分析表明列举最大项集是一个n p 困难问题。还有研究人员对( 最大) 频繁项集长度的分布情况进行了研究1 2 1 。 2 1 3 频繁序列 一个序列数据库包含了有序元素或事件。有许多关于序列数据的应用，比如说 顾客的购买序列，网络点击流，生物序列。序列模式挖掘，也就是挖掘频繁出现的 有序事件或子序列，首先由a g r a w a l 和s r i k a n t 在1 9 9 5 年提出圈。现在已成为数据 挖掘中的一个重要课题。下面是有关序列模式的基本概念。 设i = 瓴，) 是所有项目的集合。1 的子集称为巧礁。序绕亿= ( ，o ) ( 量d 是一个有序的列表。序列中的项集代表了发生在同一时间标记中的事件集合，而不 同的项集发生在不同的时刻。比如顾客购买序列可能是每一次到商店里买凡件商品， 并且要像这样购买几次。例如，买一台p c 和一些软件工具，接着是买一台数码相 机和一张存储卡，最后买一台打印机和一些书。 不失一般性，假设每一项集中的项目按照某种特殊的序( 比如按字母顺序) 排 列。序列口= 如，胡。) 是另一序列= 瓴，吒) 的子序列，记作技6 ( 如果盯， 写成研夕) ，当且仅当蟊，乇，使得1 s i ts 嚣并且q 屯，a m 气。我们 也将称为口的危蒯或卢宫j 争口。给定一个序列数据库d = b ，j ：，矗) ，序列 o r 的之桡爱定义为数据库d 中包含盯的序列数目。如果序列口满足预先定义的最小 支持度阈值，那么a 是一个频繁序列模式。 1 9 9 6 年，s r i k a n t 和a g r a w a l 提出了序列模式挖掘算法g s p 2 3 。g s p 利用序 7 辽宁科技大学硕士论文 第二章 预备知识：频繁模式挖掘 列模式的向下闭包性质，采用了一种多遍扫描数据库、生成和测试候选项的方法。 g s p 还包括了时间约束条件“一个滑动时间窗口”和用户定义的分类。 z a k i 在2 0 0 1 年提出了序列模式的垂直挖掘方法s p a d e 【2 4 】。在垂直数据格式中， 数据库被转换成以( i t e r n s e t ：( s e q u e n c e i d ，e v e n t x d ) ) 为形式的元素的集合。项集 d 对的集合形成了该项集的d 列表。为了发现长度为k 的序列，s p a d e 将任意两 个长度为k 1 的子序列的d 列表合并。这样得到的新d 列表的长度就等于长度为 k 的序列的支持度。当没有频繁序列被发现或者不能通过合并生成新的序列时，挖 掘过程结束。使用垂直格式减少了对序列数据库的扫描次数，因为d 列表包含了 计算候选序列支持度的必要信息。s p a d e 与g s p 都采用了广度优先策略，为了生 成更长的序列，它们都需要生成大量的候选序列。 p r e f i x s p a n 1 2 】瞄1 是一种基于模式增长的序列模式挖掘算法，它由p e i 等提出并改 进。p r e f i x s l c i a n 采用了分治策略。第一遍扫描数据库生成了长度为1 的序列模式。 每一个序列模式被看作是一个前缀，根据不同的前缀可将序列模式的完全集合划分 为不同的子集。为了挖掘序列模式的子集，需要递归地建造和挖掘对应的投影数据 库。 y a n 等( 2 0 0 3 ) 提出了一个挖掘闭包序列模式的算法c l o s p a n 【2 6 】。该算法基于 一个被称作“投影数据库等价类”的性质。该性质的描述如下：两个投影数据库 s i 。= s i p , 口6 是等价的，当且仅当s l 。中的项目总数等于s b 中的项目总数。这里， s l 是关于前缀口的投影数据库。利用这条性质，c l o s p a n 能够剪裁掉非闭包的序列 模式。 w a n g 和h a n ( 2 0 0 4 ) 提出了挖掘频繁闭包序列的双向搜索算法一b i d e t 2 7 1 。 关于序列模式挖掘的研究在很多方面都有扩展，其中周期分析是一个很有趣的 课题。 ， 2 1 4 挖掘结构模式：图、树、格 在对复杂结构建模方面，图作为一种一般的数据结构变得越来越重要。应用领 域包括：化学信息学、生物信息学、计算机视觉、视频索引、文本检索，还有网络 分析。 在众多的图模式中，频繁子结构是最基本的模式。以下是几个关于频繁子结构 的挖掘算法：w a s h i o 和m o t o d a 对基于图的数据挖掘方法进行了调查研究【2 引。h o l d e r 等人提出了搜索近似子结构模式的算法s u b d u e 2 9 】，该算法基于最小描述长度以 及背景知识。研究人员还通过挖掘频繁子结构预测化学致癌性f 3 0 】。 8 辽宁科技大学硬士论文 第z - 章预备知识：频繁模式挖掘 除此之外，解决频繁子结构挖掘问题有两种基本的方法：基于a p r i o r i 的方法和 基于模式增长的方法。 基于a p d o r i 的频繁子结构挖掘算法与基于a p d o r i 的频繁项集挖掘算法有着相 似的性质。搜索频繁图从小“尺寸”的图开始，以一种自底向上的方式进行。在每 一次迭代，新发现的频繁子结构的尺寸都要增加l 。首先将两个有细微差别的子图 合并成新的子结构，然后计算该结构的频繁度。基于a l m o r i 性质的经典频繁子结构 挖掘算法包括：a g m 3 ”，f s g 【3 羽，还有e d g e - d i s j o i n tp a t h - j o i n 算法【3 3 】。 【1 】a g m 使用了基于结点的候选生成方法，每次迭代将一个新结点加入子结构。 候选子图由两个大小为k ，并且包含有相同( k - 1 ) 子图的频繁图相结合生成。这里图 的尺寸( 或大小) 等于图中节点的个数。 2 f s g 使用了基于边的候选生成方法，每次迭代将一条新边加入子结构。如果 两个大小为k 的模式都含有k 1 条相同的边，那么可将这两个模式合并。 【3 】力不描! 坌璐径方法将图的集合按照每个图所包含的不相交路径数量划分。如 果两条路径没有任何公共边，那么这两条路径是边不相交的。具有k + 1 条不相交路 径的子结构模式通过合并具有k 条不相交路径的子结构生成。 基于a p r i o r i 的算法在挖掘过程中生成了大量的候选子结构，为了克服这个缺点， 人们提出了基于模式增长的挖掘算法。基于模式增长的挖掘算法通过在每一个可能 的位置增加一条新的边扩展一个频繁图。关于边扩展方法的一个重要问题：可能重 复搜索到同一个子图。g s p a n 算法弓 入了最右扩展技术来解决这个问题，也就是只 扩展最右端的路径。最右路径从开始节点v 0 出发，按照深度优先搜索策略，到达 最后的节点v n 。 除了频繁子结构挖掘算法，人们还提出了基于约束的子结构挖掘算法。y a h 和 h a r t ( 2 0 0 3 ) 提出了闭包图挖掘算法c l o s e g r a p h 3 5 】，该算法从g s p a n t 3 4 a n dc l o s p a n 2 6 】 演变而来。h u a n 等人( 2 0 0 4 ) 研究了一致子图的挖掘算法闭。还有挖掘关系图的算 法l o s e c u t 和s p l a t 3 7 】，它们可在关系图集合中发现精确密集频繁子结构。为了 对大规模图数据库进行挖掘，有人提出了基于大容量磁盘的频繁图挖掘算法【3 8 】。j i n e ta 1 ( 2 0 0 5 ) 提出了算法t s m i n e r t 删，用来从图数据库中挖掘频繁大规模结构( 称为 拓扑结构) 。还有的技术加入约束和指定近似匹配【柏】【4 l 】。 2 2 挖掘兴趣频繁模式 人们通常只希望看到或使用自己感兴趣的频繁模式。怎样的模式是有趣的，或 者说如何删除无趣的模式? 如何有效地挖掘它们? 最近有许多工作研究这些问题， 9 辽宁科技大学硕士论文 第二章预备知识：频繁模式挖掘 包括： 1 】基于约束的挖掘，【2 】挖掘不完全或压缩模式，【3 】兴趣度和相关性分析。 2 2 1 基于约束的挖掘 只挖掘那些满足用户指定的约束条件的模式的挖掘方法称为基于约震彩嬲 根据约束条件如何同挖掘过程相互作用，可把约束条件分为几类。s u c c i n c t 约束能 够在挖掘开始时用于i n i t i a ld a t as e l e c t i o np r o c e s s 。反单调性可在挖掘过程中用于控制 模式数量的增长。为了避免对进一步的模式作更多的约束条件检测，约束条件如果 满足单调性的话，可用单调的约束条件【4 2 】【4 3 】。挖掘相关频繁项集的单调约束条件的 研究在【删中可以找到。通过按升降序排列事务中的项目，可将可转化的约束条件加 入挖掘过程。通常使用的约束条件都属于上述种类。b u c i l ae ta 1 ( 2 0 0 3 ) 提出了一种 双向挖掘方法【4 5 】。由b o n c b ie ta 1 ( 2 0 0 3 ) 提出了算法e x a n t e 嗍，使用强制性的单调 约束条件对搜索空间进行剪枝。b o n c h i 和l u c c h c s e ( 2 0 0 4 ) 也提出了一种在单调约束 条件下挖掘闭包模式的算法【4 7 】。y u na n dl o g g e r ( 2 0 0 5 ) 将权重概念加入挖掘过程， 同时保留了向下闭包性质，提出了一种带权重的频繁项集挖掘算法【椰1 。基于约束的 挖掘还出现在序列模式挖掘中。 2 2 2 挖掘压缩的模式或近似的模式 为了减少挖掘过程所产生的频繁项集的巨大数量，并且保证模式的质量，最近 的研究集中在挖掘频繁模式的压缩或近似集合。一般地，模式的压缩可分为两种： 无损失的压缩和有损失的压缩。同所有频繁模式的集合相比，结果集合含信息量的 多少。闭包模式的挖掘就属于对频繁模式的无损失压缩。因为从结果模式的集合以 及它们的支持度可推出所有的频繁模式及其支持度。例如：c a l d e r sa n dg o e t h a l s ( 2 0 0 5 ) 提出了一种挖掘非衍生项集的算法f 4 9 。l i ue ta 1 ( 2 0 0 6 ) 提出使用频繁生成员 的正边界形成频繁项集的无损表示【5 0 j 。 大多数的频繁模式压缩算法都属于有损压缩。比如说，b a y a r d o ( 1 9 9 8 ) 的最大 模式，w a n ge ta 1 ( 2 0 0 5 ) 的k 个最频繁闭包项集【5 q ，p e ie ta 1 ( 2 0 0 2 ) 的压缩模式 ( c o n d e n s e dp a t t e r n ) 1 5 2 ，a f i a t i 的k 概括模式0 c s u m m a r i z e dp a t t e r n s ) 1 5 3 ，y a ne ta 1 ( 2 0 0 5 1 的k - s u m m a r i z e dp a t t e r np r o f i l e s 【州，) ( i ne ta 1 ( 2 0 0 5 ) 的基于聚类的压缩模式【5 5 】。 为了挖掘k 个最频繁的闭包模式。t f p 算法搜索k 个长度不少于r a i nl 的最频 繁闭包模式。t f p 在挖掘过程中逐渐提高支持度，并且在构造f p 树的过程中和过 程后剪裁f p 树。 1 0 辽宁科技大学硕士论文 第二章预备知识：频繁模式挖掘 由于项集的频繁度分布是非均匀的，k 个最频繁的模式通常不是k 个最具有代 表性的模式。压缩工作的另一个分支采取了“总结”的方法。它的目标是生成能够 覆盖整个( 闭包) 频繁项集集合的k 个代表。人们可以很容易地解释和使用这k 个 代表。a f r a t ie ta 1 ( 2 0 0 4 ) 提出了使用k 个项集近似整个频繁项集集合f 5 3 1 。近似度被 定义为k 个项集所覆盖的集合的大小。y a ne ta 1 ( 2 0 0 5 ) 提出了一种用k 个项集近似 所有频繁项集的基于p r o f i l e 的方法【蚓：一组相似项集的p r o f i l e 定义为这组项集的并， 以及项目在支持集上的概率分布。基于p r o f i l e 方法的特点在于它能够恢复单个项集 的支持度，而这种恢复只有较小的误差。 还有的研究将频繁模式看作是根据模式的相似度和频繁支持度聚在一起的模式 的集合。基于压缩模式的方法【5 2 】首先根据支持度将模式分类，然后在每一类中寻找 最具代表性的模式。由x j ne ta 1 提出的代表模式方法【5 5 垤用某种紧缩度量艿，根据 模式相似度和频繁支持度，对频繁项集的集合聚类；代表模式可从每一个簇( 称作艿 簇) 中选出。s i e b e se ta 1 ( 2 0 0 6 ) 提出一种满足m d l 原则的公式惭】，m d l 原则指最 好的频繁项集集合能够对数据库进行最好的压缩。 既然真实的数据中不可避免地混有噪音和测量误差，理论结果表明：即使仅存 在低程度的噪音，大的频繁项集都会被分成对数级数量的片段。这样通常的频繁项 集挖掘程序都不能恢复原来的项集。y a n g e la 1 ( 2 0 0 1 ) 提出了两个容错模型，并称之 为弱容错项集( w e a ke r r o r - t o l e r a n ti t e m s e t s ) 和强容错项集( s t r o n ge r r o r - t o l e r a n ti t e m s e t s ) i 轫。s t e i n b a c he t a l ( 2 0 0 4 ) 提出了对称的e t i 模型【5 8 】，这种模型允许行和列有一定的误 差比例。s e p p a n e na n dm a n n i l a ( 2 0 0 4 ) 提出了噪音存在的情况下挖掘密度项集( d e n s e i t e m s e t s ) l 拘算法【5 9 】，密度项集指其有一个足够大的，并且超过了现有属性的给定密 度阀值的子矩阵。l i ue ta 1 ( 2 0 0 6 ) 提出了挖掘近似频繁项集的一般模型a f i i 删；在 由事务和项目构成的矩阵中，a f i 在两个方向都控制误差。 2 2 3 从频繁模式到兴趣度和相关性分析 自然地，由挖掘频繁项集导致了存在于大型事务数据集中项目间的关联规则和 相关性的发现。有趣的关联规则和相关规则可用于商业中的决策制定，像c a t a l o g d e s i g n , c r o s s - m a r k e t i n g 和消费者购物行为分析。 根据关联规则的定义，大多数研究将频繁模式挖掘作为关联规则挖掘的十分关 键的第一步工作。然而，并不是所有生成的关联规则都是有趣的，特别是当用低支 持度阀值进行挖掘或者挖掘较长模式的时候。为了挖掘有趣的规则，相关性度量可 用来改进关联规则的支持度信任度框架。这就引出了相关规则的形式：口j 支 1 1 辽宁科技大学硕士论文 第二章预备知识：颏繁模式挖掘 持度，置信度，相关度】。有许多不同的相关性度量方式，包括够，z 2 ，c o s i n e 和 a l l c o n f i d e n c e 。 已经有许多研究者研究规则兴趣度的问题。p i a t e t s k i s h a p i r o 提出将规则的统计 独立性作为兴趣度的度量“。b r i ne ta 1 ( 1 9 9 7 ) 提出用，沂和z 2 作为相关性度量【回。 a g g a r w a la n dy u ( 1 9 9 8 ) 研究了支持度置信度框架的弱点，提出了强集合项集模型 ( s t r o n g l yc o l l e c t i v ei t e m s e tm o d e l ) 【6 3 】。其它替代支持度置信度框架的方法可在【6 2 】【删 中找到。还有的工作比较分析了不同兴趣度度量方法f 6 5 】。一个项目出现在一个事 务中的可能性通常非常小。相关性度量不应该被n u l l - t r a n s a c t i o n s 影响。 n u l l - t r a n s a c t i o n s 指的是那些不包括任何被检查规则中的项目的事务。 a h c o n f i d e n c e ，c o h e r e n c e ，c o s i n e 是空不变量( n u l l i n v a r i a n t ) ，因此是挖掘事务数 据库中相关规则的好的度量方法【圃1 6 7 f 删。有人提出用数据驱动方法估计关联规则 的兴趣度，使用基于项目之间关系的关联性评估关联规则的兴趣度【叫。b l a n c h a r de t a 1 ( 2 0 0 5 ) 基于信息论设计了一个规则兴趣度度量方法d i r e c t e di n f o r m a t i o nr a t i o ，这 个方法能够过滤掉祖先和子孙是负相关的规则，还有那些反例比正例多的规贝l j t 7 0 j 。 g i o n i se ta 1 ( 2 0 0 6 ) 最近提出了一个新的意义评估方法，它不仅依赖于个别的属性， 还依赖于整个数据集f 7 1 j 。 还有的研究挖掘相对于用户的先验知识，挖掘有趣的或者说非期望的模式。 w a n ge ta 1 ( 2 0 0 3 ) 定义了一个偏好模型，这个偏好模型抓住了“非期望，出乎意料” 的概念；并给出了挖掘所有非期望规则的算法，这些规则要满足用户指定的最小“非 期望意义”和“非期望强度”【捌。还有的研究人员用贝耶斯网络表示用户的先验知 识【7 3 1 【7 4 】，项集的兴趣度被定义为从数据和从贝耶斯网络估得的支持度之间的绝对差 值。另外，用户对兴趣度的反馈也能够指导发现有趣的模式1 7 5 。 2 3 频繁模式对数据分析和挖掘任务的影晌 通过挖掘过程发现的频繁模式不仅自身是有趣的，而且对其它数据分析和挖掘 任务也很有用处。应用包括基于频繁模式的分类和聚类等。 2 3 1 基于频繁模式的分类 既然可用关联规则分类，所以说频繁模式对于分类十分有用。这类算法的大致 思路是：既然能够发现频繁模式和类标识间的强关联性，那么关联规则就可以用于 预测。许多研究都表明，关联性分类( a 鹃o c i a t i v ed 勰s i f i c a t i o n ) 比某些传统的分类方 1 2 辽宁科技大学硕士论文 第二章预备知识：频繁横式挖掘 法( 比如c 4 5 ) 都要准确。 l i ue ta