（计算机应用技术专业论文）关联规则算法研究与应用.pdf

摘要 关联规则算法研究与应用 摘要 数据挖掘是当前k d d 中的一个重要领域，而关联规则挖掘是数据挖掘的一个重要组 成部分。i n t e r n e t 的发展促进了数据库技术的深入应用。由于安全及通信成本、效率等 多方面的原因，大量的分散数据不可能集中起来处理。分布式关联规则的挖掘就是在这 样的背景下提出的，本文主要研究了如何提高分布式关联规则算法的效率和伸缩性。 本文在分析和介绍了关联规则挖掘的基本概念和方法以及分布式关联规则挖掘方 法和技术基础上，提出了中心结点结构的分布式关联规则挖掘的算法( c d a & f p ) 。同时， 分析介绍了基于w e b 文本集的特征关联规则挖掘框架，详细论述了该框架所涉及到的技 术和实现过程中的诸多问题。 a p r i o r i 算法是经典的关联规则算法，而该算法在空间和时间的复杂性有着难以克 服的局限性。文中介绍了一种不需要产生候选项的频繁模式增长算法，将数据库的事务 的信息压缩到f p t r e e ，然后产生频繁模式，从而避免了多次扫描数据库，降低了时间 开销。 对于分布式关联规则挖掘问题，目前的主要算法是c d 算法和f d m 算法。这些算法 都是基于网状结构的分布式关联规则挖掘算法，同时结点都是采用a p r i o r i 算法来挖掘 局部频繁集，因此在结点通讯量和候选频繁集方面存在不足。本文在f p - g r o w t h 算法及 f d m 算法的基础上，提出以中心结点结构的分布式关联规则挖掘算法，并且从算法分析 和实验测试两个方面证明了算法的有效性和可扩展性。 关键词：数据挖掘，分布式关联规则，全局频繁项集，频繁模式增长，w e b 文本挖掘 a b s t r a c t r e s e a r c ha n da p p l i c a t i o no fa s s o c i a t i o nr u l e s a l g o r i t h m a b s t r a c t d a t am i n i n gi sa l li m p o r t a n ta r e ai nk d d ，a n dm i n i n ga s s o c i a t i o nr u l e sm i n i n gi nl a r g e d a t a b a s e si sac r i t i c a la s p e c to fd a t am i i l i n gr e s e a r c h e s t h er a p i dd e v e l o p m e n to fi n t e r n e t m a k e sag r e a tp r o g r e s si nd a t a b a s ea p p l i c a t i o n s s i n c et h es e c u r i t ya n dc o s to fc o m m u n i c a t i o n a n de f f i c i e n c yo ft h ea p p l i c a t i o n s ，c o l l e c t i n ga n di n t e g r a t i n gal a r g ea m o u n to fd a t af r o m i n t e r n e ts i t e sa r en o tp r a c t i c a lw a y s t h ep r o b l e mo fm i n i n ga s s o c i a t i o nr u l e si nd i s t r i b u t e d d a t a b a s e sa r i s e sf r o mt h i ss i t u a t i o n ，t h ec o r eo fd i s s e r t a t i o ni sh o wt oi m p r o v et h ev a l i d i t ya n d s c a l a b i l i t yo fm i n i n ga l g o r i t h mo fd i s t r i b u t e da s s o c i a t i o nr u l e s t h i sd i s s e r t a t i o np r o p o s e st h ed i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n ga l g o r i t h m ( c d a & f p ) i ns t a rs t r u c t u r e ，b a s e do na n a l y s e sa n di n t r o d u c t i o no ft h eb a s i cc o n c e p t sa n da l g o r i t h m so f m i n i n ga s s o c i a t i o nr u l e sa n dm i n i n ga s s o c i a t i o nr u l e si nd i s t r i b u t e dd a t a b a s e sf i r s t a c a l c u l a t i n go fa r c h i t e c t u r eu s e df o rm i n i n ga s s o c i a t i o nr u l e so ft e x tc h a r a c t e r si sp r o p o s e da n d t h em a i nt e c h n i q u e so ft h ra r c h i t e c t u r ea r et h e nd e c r i b e di nd e t a i l t h ea p r i o r ia l g o r i t h mi st h ec l a s s i cm e t h o do ff i n d i n ga s s o c i a t i o nr u l e s ，b u th a st h e d i s a d v a n t a g ei nt h ec o m p l e x i t yo fs p a c ea n dt i m e t h e r e f o r e 。t h i s 也e s i si n t r o d u c e san e w 行e q u e n t p a r e mg r o w t ha l g o r i t h mt h a td o e sn o tn e e dt op r o d u c et h ec a n d i d a t ei t e m s e t s n l i s a l g o r i t h mc o m p r e s s e si n f o r m a t i o ni nd a t a b a s et ot h ef p - t r e e ，t h e np r o d u c e sf r e q u e n tp a t t e m ， c o n s e q u e n t l ya v o i d ss c a n n i n gt h ed a t a b a s em a n yt i m e s ，a n dl o w e r st h et i m ee x p e n s e t h ef d ma n dc da r em a i ns t r e a ma l g o r i t h m sf o rm i n i n ga s s o c i a t i o nr u l e si nd i s t r i b u t e d d a t a b a s e s t h e s et w oa l g o r i t h m sa l lw o r ko nn e ts t r u c t u r en e t w o r k s ，f u r t h e r m o r e ，t h em i n i n g a l g o r i t h mo n t l l ed i s t r i b u t en o d e si sa p r i o r i t h e r e f o r eh a st h ei n s u f f i c i e n c yi nt h ep o i n tt r a f f i c a n dt 1 1 ec a n d i d a t ef r e q u e n tc o l l e c t i o na s p e c t t h ed i s s e r t a t i o n p r o p o s e s t h ec d a & f p a l g o r i t h mt os o l v et h i sp r o b l e m ，b a s e do nf d ma n df p g r o w t h e x p e r i m e n t a lr e s u l t ss h o w m a tt h ep e r f o r m a n c eo ft h ec d a & f pi sa v a i l a b l ea n de x t e n d a b l e k e yw o r d s ：d a t am i n i n g ，d i s t r i b u t e da s s o c i a t i o nr u l e s ，g l o b a lf r e q u e n ti t e m s e t s ，f p - g r o w t h ， w e bt e x tm i n i n g h 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表和撰写的研究成果，也不包含为获得华 东交通大学或其他教育机构的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 本人签名鳓 关于论文使用授权的说明 日期渺多 6 汐 本人完全了解华东交通大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅。学校可以公布论 文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 保密的论文在解密后遵守此规定，本论文保密期1 年。 本人签遒垫导师签名五扎日期 第一章绪论 第一章绪论 1 1前言 计算机技术的发展和普及，使得数据的收集和存储变得越来越容易，但数据规模的 爆炸性增长，远远超出了人们的处理和理解能力。使用传统的方法己经不能从数据中发 现潜在的所隐含的知识。数据挖掘( d a t am i n i n g ，d m ) 就是从大量的数据中发现和提取有 用知识的过程。数据挖掘是为了发现未知的规则和知识，在大量的数据中探索、比较、 挖掘以得到用户所期望的有用的模式和知识。 数据挖掘最初是面向事务数据库应用的，随着i n t e m e t 的普及和发展，w e b 已经发 展成为拥有3 亿页面的分布式信息空间。在这些大量、异质的w e b 信息资源中，蕴含 着具有巨大潜在价值的知识，人们迫切需要能够从w e b 上快速、有效地发现资源和知 识的工具，w e b 上的搜索引擎部分地解决了资源发现问题，但由于精确度不高等原因， 其效果远不能使人满意。此外，搜索引擎的目的在于发现w e b 上的资源，就w e b 上的 知识发现而言，即使检索精度再高，搜索引擎也不能够胜任。为此我们需要开发比信息 检索层次更高的新技术，为了从大量数据的集合中发现有效、新颖、有用、可理解的模 式，数据库领域采用了数据挖掘技术，但数据挖掘的绝大部分工作所涉及的是结构化数 据库，很少有处理w e b 上的异质、非结构化信息的工作，w e b 挖掘作为数据挖掘的一 个新主题，引起了人们的极大兴趣，同时它也是一个有争议的研究方向 1 l 。 本章第二部分是对数据挖掘基本概念的介绍，给出了数据挖掘的定义，描述了数据挖 掘的过程和分类，第三部分是课题研究现状的介绍，最后介绍了本篇论文的主要研究工 作和结构安排。 1 2 数据挖掘的概念 1 2 1 数据挖掘的定义 简单地说，数据挖掘就是从大量的数据中提取或者“挖掘”知识。在许多场合下， 数据挖掘又被称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 。但 更科学的说法是将数据挖掘视为数据库知识发现的一个基本步骤，在产业界、媒体和数 据库研究界，将数据挖掘直接当作数据库中的知识发现更为流行。因此数据挖掘有了一 个更加广泛的概念：数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量数据 中挖掘有趣知识的过程。基于这种观点，一个典型的数据挖掘系统可以由以下几个主要 成分组成( 如图1 1 所示) ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子表格 或其他类型的信息库。可以在数据上进行数据清理和集成。 第一章绪论 图形用户界面 上t 模式评估 上t 数据挖掘引擎 0t 数据库或数据仓库服务器 图1 - 1典型的数据挖掘系统结构 f i g u r e l 1 t y p i c a ls y s t e ms 眦t l i r eo f d a t am i n i n g 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服务器 负责提取相关数据。 数据挖掘引擎：数据挖掘系统基本的部分，由一组功能模块组成，用于特征化、 关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：一般使用兴趣度度量，并与数据挖掘模块交互，以使将搜索聚焦 在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。模式评估模块也可以与挖掘 模块集成在一起，这依赖于所用的数据挖掘方法的实现。 图形用户界面：实现用户和数据挖掘系统之间的通信，允许用户与系统交互，指 定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结果进行探索 式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库模式或数据结构，评估挖 掘的模式，以不同的形式对模式可视化。 1 2 2 数据挖掘的过程 数据挖掘的实施，大体可分为以下三步，如图1 2 所示： ( 1 ) 数据准备( d a t ap r e p a r a t i o n ) 本阶段又可分为两步：数据集成，数据的选择和预分析。 数据集成( i n t e g r a t i o n ) ，在这一步中，将从操作型环境中提取并集成数据，解 决语义的二义性问题，消除脏数据。 数据选择和预分析( d a t as e l e c t i o na n dp r e _ a n a l y s i s ) 这一步负责缩小数据范围， 提高数据挖掘的质量。 第一章绪论 ( 2 ) 挖掘( m i n i n g ) 数据挖掘器( d a t am i n i n gp r o c e s s o r ) 综合利用数据挖掘方法分析数据库中的数据， 选择和使用挖掘算法开采出具体的模式，得到结果后，还要对开采出来的知识进行验证。 确 问 图1 。2 数据挖掘过程 f i g u r e1 - 2 t h ep r o c e s so fd a t am i n i n g 知识 的使 弼和 模型 的苴 拉 ( 3 ) 表述( p r e s e n t a t i o n ) 数据挖掘将获得的信息以便于用户理解和观察的方式反映给用户，这时可利用可视 化工具。这些基于不同数据集合的分析结果除了通过可视化工具提供给用户外可还可以 存储在知识库中，供日后进一步分析和比较。 另外，在确定问题阶段，为了充分利用数据挖掘，用户必须明确表述出目标是什么， 不同的目标将需要不同的模型。一个好的目标应该明确要解决的企业问题，并有可度量 的结果，这些结果能够引发明智的行动，为企业提供有效的帮助。这样的目标应该包括 决策者可能做出的各种错误预测所造成的损失以及由于正确预测所带来的效益。 1 2 3 数据挖掘的功能和分类 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般可以分 为两类：描述和预测1 2 j 。描述性挖掘任务刻画数据库中数据的一般特性，而预测性挖掘 任务则在当前数据上进行推断，以进行预测。 在很多情况，用户并不知道什么样的模式是有趣的，因此可能需要探索多种不同的 模式，以从中选择出自己感兴趣的模式。这就要求数据挖掘系统应该能够挖掘多种类型 的模式，以适应不同的需求。此外，数据挖掘系统应该能够发现各种粒度( 即不同的抽 象层) 的模式，应当允许用户给出提示，指导或聚焦有趣模式的搜索。 数据挖掘的功能以及可以发现的模式类型有：类概念描述、关联分析、分类和预 测、聚类分析、孤立点分析和演变分析1 3 j 。 第一章绪论 1 、类概念描述 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和概念可 能是有用的。这种类或概念的描述称为类概念描述。 这种描述可以通过以下方法得到： 数据特征化：是目标类数据的一般特征或特性的汇总。 数据区分：将目标类对象的一般特性与一个或多个对比类对象的一般特性比较。 数据特征化和区分：同时应用数据特征化和数据区分进行描述。 2 、关联分析 关联分析用于发现关联规则，关联规则描述了给定数据集中项之间的有趣联系。关 联分析广泛应用于购物篮分析或事务数据分析。从大量商务事务记录中发现有趣的关联 关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析等。 3 、分类和预测 分类是找出描述并区分数据类或概念的模型的过程，以便能够使用模型预测类标记 未知的对象类。预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有的 属性值或值区间。分类和预测之间的区别在于，分类是预测类标号( 或离散值) ，而预 测是建立连续值函数模型。 4 、聚类分析 聚类将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相似 度，而不同簇中的对象差别较大。与分类不同的是，它要划分的类是未知的。 5 、孤立点分析 在数据库中经常存在- 些数据对象，它们不符合数据的一般模型。这样的数据对象 被称未孤立点，它们与数据其他的部分不同或不一致。孤立点可能是度量或执行错误所 导致的，也可能是固有的数据变异后的结果。在许多时候，孤立点被视为噪声而被丢弃， 而在一些应用中，孤立点可能会很有用。例如，在医疗分析中，某些对多种治疗方式的 不寻常的反应数据可能成为孤立点，但是这些数据对于治疗却非常重要。对孤立点数据 进行分析称为孤立点分析。 1 3 课题的研究现状 关联规则的研究已经成为数据挖掘领域中的重要研究方向，a g r a w a l 等在1 9 9 3 年提 出了关联规则的基本概念。随后许多研究人员对其进行了大量研究，包括对原有算法进 行优化，如引入随机采样、并行的思想【4 5 6 j 等，以提高算法挖掘的效率；还有就是对关 联规则的应用进行推广等【7 j 。 a g r a w a l 于1 9 9 3 年第一次提出了关联规则的基本概念【8 1 ，并且给出了一个初始的 a i s 算法；a g r a w a l 于1 9 9 4 年提出了经典的a p r i o r i 算澍圳，这个算法奠定了关联规则挖 掘算法的基础，该算法中所使用的思想在其它多个算法中被使用。随后，许多人对a p r i o r i 4 第一章绪论 算法进行了改进，p a r k 等人提出了d h p 算法【l 训。它使用h a s h 树的方法来高效地产生频 繁集。j i a w e ih 提出了f p 。g r o w t h 算法【l ，它不需要产生候选频繁集；通过将数据库压 缩进一棵频繁模式树来产生条件模式基并最终生成频繁集。这些改进算法都是针对 a p r i o r i 算法在执行过程要多次扫描数据库和生成大量的候选频繁项集的瓶颈。 在挖掘关联规则时考虑时间因素在最近几年才逐渐发展成熟，并形成了序列模式的 挖掘算法。文献【1 2 提出了g s p 算法，它借鉴a p r i o r i 算法的思想来进行序列模式的挖 掘。在文献 1 3 中，h a n 等人提出了p r e f i x s p a n 算法，它是应用模式增长来挖掘数据库 中的序列模式。 随着i n t e m e t 技术的成熟和应用，大容量数据库的异构、分布式特点，逐渐形成了 分布式关联规则挖掘算法，为了提高关联规则挖掘的效率，人们对利用多c p u 计算机 系统对关联规则的并行挖掘进行了大量的研究 1 4 , 1 5 】，而并行关联规则的研究促进了分布 式关联规则挖掘的研究。因为分布式关联规则的挖掘其本质上也是一种并行的关联规则 挖掘【1 6 , 1 7 ，是基于计算机网络环境下的关联规则挖掘。 关联规则在国外已进入了产品化阶段，主要有i b m 公司的q u e s t ，加拿大f r e s a r 大学的d b m i n e r 1 8 】，以及用于图像处理的s k i c a t 。关联规则挖掘的研究在我国起步较 晚，目前研究的重点仍集中在对国外算法的理解和改进上，以适合中国数据库系统的实 际情况。对于数据挖掘( 包括关联规则的挖掘) 的实际应用研究得相对较少，最近几年， 国内更全面的数据挖掘产品正在研究和开发之中，但是还没有出现很好地适用于多平台 的产品。目前数据挖掘在我国的应用主要集中在一些信息化建设比较好的行业和部门， 包括银行、金融、电信等。更深层次的应用和对复杂问题的解决方案还有待进一步地研 究和实践。 1 4 论文的研究内容 w e b 文本挖掘在i n t e m e t 上的多种潜在的用途和实际应用面临的诸多问题，使w e b 文本挖掘技术受到越来越多的瞩目。而目前的w e b 文本挖掘大多数是围绕w e b 文本分 类和w e b 文本聚类展开的；同时由于w e b 文本挖掘要处理超巨量的文本数据和w e b 数 据的分布性使得当前的关联规则挖掘算法在处理时有一定的难度。 本文的研究工作就是基于这样的情况，在深入分析关联规则挖掘的相关理论和算法 的基础上，针对w e b 文本集半结构化文件和分布特点，在w e b 文本集特征关联规则挖 掘的框架下，给出了基于分布式的频繁模式增长挖掘方法。具体如下： ( 1 ) 通过系统研究经典的频繁项集挖掘算法a p r i o r i ，f p g r o w t h 等多种算法，分析 了影响频繁集算法效率的因素及优化方法。 ( 2 ) 对比研究了w 曲文本集中的特征关联规则挖掘和传统数据挖掘中关联规则的 异同；引入了用于挖掘特征关联规则的框架，框架以w e b 文本集的结构化和特征化为 支撑，以有效的关联规则挖掘算法为核心。 第一章绪论 ( 3 ) 通过研究分布式关联规则挖掘的原理和基本算法( c d 算法和f d m 算法) ，提 出了基于星型网络结构的分布式算法c d a & f p ，给出f p g r o w t h 算法的分布式实现，算 法减少了结点间的通讯量和优化扫描数据库的方法，大大提高了算法的效率和伸缩性。 ( 4 ) 对c d a & f p 进行了算法分析，同时对此方法进行了推广，给出了树型关联规 则挖掘方法的概念。 1 5 论文的结构安排 第一章绪论 简要介绍了数据挖掘的背景，数据挖掘的基本概念和关联规则的研究现状，并在最 后总结了论文的研究工作和安排。 第二章w - e b 文本挖掘 综述了w e b 文本挖掘技术，简要描述了w e b 文本挖掘的过程，常见的两种w e b 文 本挖掘技术，及w 曲文本挖掘质量的主要评价方法和主要参数。 第三章关联规则的研究 重点介绍了关联规则挖掘的主要思想和典型的频繁集发现算法a p r i o r i 和 f pg r o w t h 的执行过程，并介绍了频集算法的优化方法。 第四章w e b 文本特征关联规则挖掘框架 基于对传统关联规则挖掘和特征关联规则挖掘的比较，提出w e b 文本特征关联规 则挖掘框架，详细描述了w e b 文本集结构化、特征化的主要思想和方法。 第五章分布式关联规则挖掘的主要原理和方法 主要介绍当前分布式关联规则挖掘的主要原理和方法，详细分析了c d 算法和f d m 算法的基本思想和执行情况。 第六章基于星型结构分布式关联规则挖掘 在f d m 算法和c d 算法的基础上，结合f pg r o w t h 算法的特点，提出c d a & f p 算法，并对算法进行了性能分析，用实验证明了算法的有效性，最后结合w e b 文本特征 关联框架给出了c d a & f p 在w e b 文本集中的应用。 第七章结束语 总结了论文的研究工作和展望了将来的研究工作。 6 第二章w e b 文本挖掘 第二章w e b 文本挖掘 2 1概述 数据挖掘是要从大量的数据中发现隐含的规律性的内容，解决数据的应用质量问 题。相对于w e b 的数据而言，传统数据库中的数据结构性很强，其数据为完全结构化 的数据。而w e b 上的数据的最大特点就是半结构化，所谓半结构化是相对于完全结构 化的数据而言，这就造成了面向w e b 的数据控制比面向传统数据库的数据挖掘要复杂 得多。w e b 文本挖掘是一项综合技术，涉及w e b 技术、数据挖掘、计算机语言学、信 息检索、知识管理等多个领域。不同研究者从自身的领域出发，对w e b 文本挖掘的含 义有着不同的理解，项目开发也各有侧重点。 2 1 1 w e b 文本挖掘的定义 w e b 文本挖掘【1 9 1 ，顾名思义就是挖掘和发现w e b 文档中知识和模式，它从数据挖 掘发展而来，但与传统的数据挖掘又存在着一定的差异。 w e b 文本挖掘是指针对包括w e b 页面内容、页面之间的结构、用户访问信息、电 子商务信息等在内的各种w e b 数据，应用数据挖掘方法以发现有用的知识来帮助人们 从大量w e b 文档集合中发现隐含的模式，也即从w e b 信息资源中提取潜在的、有价值 的知识。 w e b 信息的多样性决定了w e b 挖掘任务的多样性，按照处理对象的不同，我们可 以将w e b 挖掘分为三大类：w e b 内容挖掘( w e bc o n t e n t m i n i n g ) 、w 曲访问信息挖掘( w e b u s a g em i n i n g ) 、w _ e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 2 0 1 0w e b 文本挖掘属于w e b 内容 挖掘的范畴，可以对w e b 上大量文档集合的内容进行总结、分类、聚类、关联分析。 2 1 2w e b 文本挖掘特点 w e b 上的数据与传统的数据库中的数据不同，传统的数据库都有一定的数据模型， 可以根据此模型来具体描述特定的数据。而w e b 上的数据非常复杂，没有特定的模型 描述，每一站点的数据都各自独立设计，并且数据本身具有自述性和动态可变性。因而， w e b 上的数据具有一定的结构性，但因自述层次的存在，从而是一种非完全结构化的数 据，也被称之为半结构化数据。半结构化是w e b 上数据的最大特点，也形成了w e b 文本 挖掘的特色。 2 1 3w e b 文本挖掘的一般处理过程 w e b 文本挖掘的一般处理过程如图2 1 所示： 7 第二章w e b 文本挖掘 图2 - 1w e b 文本挖掘过程 f i g u r e2 1 t h ep r o c e s so fw e bt e x tm i n i n g 首先要对挖掘对象建立其特征表示，w e b 文本挖掘对象通常是一组h t m l 格式的文 档集，这样的挖掘对象缺乏像关系数据库中数据的组织规整性，并且文档内容是人类所 使用的自然语言，计算机很难理解其语义。所以我们首先要将文本数据库中的文本转化 为计算机能够处理的形式，为文本建立恰当的数学模型。近年来，矢量空间模型【2 1 】 ( v e c t o rs p a c em o d e l ，v s m ) 是应用较多且效果较好的方法之一。 其次，进行文档向量维数的缩减，即特征子集的选取。在v s m 模型中，文档向量 具有惊人的维数，必须对文档矢量作进一步的约简处理，在保证原文含义的前提下，找 出最能反映文本内容，维数却大大缩减的特征子集。目前特征提取主要有两大类方法： 独立评估方法和综合评估方法。 在完成文档特征向量维数的缩减后，便可利用机器学习的各种方法来提取面向特定 应用目的的知识模式，最后对获取的知识模型进行质量评价。若评价的结果满足一定的 要求，则存储该知识模式；否则返回到以前的某个环节分析改进后进行新一轮的挖掘工 作。 2 2w e b 文本挖掘常用方法 2 2 1 文本分类 文本分类是按照主题的特征规则，对一新w e b 文档进行判断，确定其属于哪一类 主题。分类主要是计算新文档与特征文档的相似性，当相似达到一定阈值就认为该文档 属于主题。文本分类技术可被用于对大量文档进行快速而有效的自动分类，从而提高用 户在限定搜索范围时的查询效率。目前，y a h o o ! 、s o h u 等搜索引擎通过手工对文档进 行分类，其索引页面的覆盖范围远远小于己使用自动分类技术的搜索引擎如a l t a - v i s t a 、 g o o g l e 等。文本分类技术还可以结合机器学习设计用于用户个人的文件过滤系统，通过 用户所看的一定数量的文章总结出该用户的兴趣模型，对用户准备看的每篇文章，计算 出一个兴趣度分值，使用户可以首先阅读他最感兴趣的文章。 2 2 2 文本聚类 文本聚类是指将文档集合分为若干个簇，需要满足簇内文档内容的相似度尽可能的 大，而簇与簇之间的相似度要尽可能的小。研究文本聚类的意义在于：与用户查询相关 的文档通常会聚类比较近，而远离与用户不相关的文档。所以利用文本聚类技术将搜索 引擎的结果划分为若干个簇，用户只需要考虑那些相近相关的簇，从而用户可以大大减 第二章w e b 文本挖掘 少浏览网页的数量。 2 2 3 文本总结 文本总结 2 2 1 技术是指从文档中抽取关键的句子信息，用简洁的形式对文档内容进行 摘要或解释。这样，用户不需要浏览全文就可以了解文档或文档集合的总体内容。文本 总结在有些场合十分有用，例如，搜索引擎在向用户返回查询结果时，通常需要给出文 档的摘要。目前，绝大部分搜索引擎采用的方法是简单地截取文档的前几行。有多种摘 要算法，但关键技术都采用词性标注，进行语义分析；用统计方法提取高频词( 去除停 用词后) ，以确定摘要。文本总结的结果有助于用户在没有通读全文的情况下，快速地 全面地了解文本内容，以决定是否深入了解该文本。 2 2 4 关联分析 关联分析是指从文档集合中找出不同词语之间有趣的关联或相互关系。用户的背景 和目的不同，使得他们研究文档集合的类型和角度不同。基于不同的被处理文档和词语 集合，可分别挖掘不同类型人感兴趣的模式，从中导出各自有兴趣的规律。b r i n 利用一 种挖掘对词语出现模式的算法在w e b 上寻找作者和书名的出现模式，结果发现了数千 本在a m a z o n 网站( 有名的书籍网站) 上找不到的新书籍。w a n gk e 等使用o e m ( o b j e c t e x c h a n g em o d e l ) 模型以w e b 上的电影介绍为测试文档，得出一些关于电影名称、导演、 演员、编剧的出现模式【2 引。 2 3w e b 文本挖掘的相关技术 2 3 1 自动分词 自动分词是指按照特定规范，在中文文本中连续地能够代表语义单元的词或者n 元 词条加入分隔符。中文分词是其他中文信息处理的基础，比如搜索引擎、机器翻译( m t ) 、 语音合成、自动分类、自动摘要、自动校对等等，都需要用到分词。如何把文章切分为 词条，并从中提取特征词条构成特征向量已成为文本处理的关键【2 4 2 引。 2 3 2 特征表示 文本表达了巨大的、丰富的信息，但是要把这些信息编码为一种标准形式是非常困难 的。基于自然语言处理和统计数据分析的文本挖掘中的文本特征表示指的是对从文本中 抽取出的元数据( 特征项) 进行量化，以结构化形式描述文档信息。 从语义的角度看，大多数w e b 文档几乎都是无结构的。h t m l 文件虽然被认为是半 结构化的，但它具有的结构多被用来描述文档的结构和显示方式，而与语义关系不大。 为了便于计算机处理其语义，需要对文本进行处理，抽取代表其特征的元数据，即文本 特征。文本特征分为描述性特征，如文本的名称、日期、大小、类型等；以及语义性特 9 第二章w e b 文本挖掘 征如文本的作者、机构、标题，内容等。与描述性特征相比，语义性特征较难获得。 对于被表示的文本而言，一个有效的特征项集应具有完全性和区分性两个特征。完 全性保证了特征项集能够准确地表示原文档，区分性保证了源文件与其特征项集的一对 一关系。根据这两个特征，可以知道词条对文档内容的贡献与词条在文档中的出现频率 成正比，而且与样本文档集中出现该词条的文档数目成反比。 特征表示的构造过程就是挖掘模型的构造过程。近年采使用的较多的是向量空间模 型( v s m ，v e c t o rs p a c em o d e l ) 。在该模型中，文档被看作由一组词条( t l ，t 2 t n ) 构成，对 于每一词条t i 都依据一定的函数为其赋予权值w i 。因此每一个文档都可以看成是矢量 空间( t 1 ，t 2 t 。) 中的一个点，可表示为：v d ) = ( t l ，w 1 ( d ) ，t 2 ，w 2 ( d ) ，t n ，w n ( d ) ) 。其中，t i 是文档中出现的单词或短语，w i ( d ) 为词条t i 在文档d 中出现频率f i ( d ) 的 函数，即w i ( d ) = 。常见的函数有：布尔函数、平方根函数、对数函数、i f i d f 函数 ( 即= f i ( d ) * l o g ( n n i ) ，其中n 为总文档数目，m 为包含词条t i 的文档数目) 。 2 3 3 特征抽取 词、词组和短语组成文档的基本元素，并且在不同内容的文档中，各词条出现频率 有一定的规律性，不同的特征词条就可以区分不同内容的文本。因此我们可以抽取一些 特征词条构成特征矢量，用这个特征矢量来表示w e b 文本，一个有效的特征词条集， 必须具备以下三个特征： ( 1 ) 完全性：特征词条能够确实表示目标内容； ( 2 ) 区分性：根据特征矢量，能将目标同其它文档相区分； ( 3 ) 精练性：特征矢量的维数应该尽可能的小。 目前文本特征矢量的获取一般是通过一些分词算法和词频统计方法，从文档中选出 尽可能多的词、词组和短语，由它们来构成文档矢量。但是由这种方法来表示文档，矢 量的维数非常巨大。这种未经处理的文档矢量给后续的处理工作带来巨大的计算开销， 使整个处理过程的效率非常低下。 因此我们必须对文档矢量作进一步精化处理，在保证原文含义的基础上，找出最能 反映文本内容，又比较简洁的特征矢量。这样做的目的主要有两个：第一，为了提高程 序的效率，提高运行速度，第二，所有几万个词汇对文本分类的意义是不同的，一些通 用的、各个类别都普遍存在的词汇对分类的贡献小，在某特定类中出现比重大而在其他 类中出现比重小的词汇对文本分类的贡献大。 2 4w e b 文本挖掘的质量评价 2 4 1w e b 文本挖掘的评价方法 w e b 文本挖掘过程中的最后一个且十分重要的过程就是质量评价。常用的方法有预 留法( h o l d o u t ) 和交叉验证法( c r o s s v a l i d a t i o n ) 。在这两种方法中，都是将全部数据分成训 l o 第二章w e b 文本挖掘 练集和测试集两部分。学习和测试循环反复进行。最后用一个平均质量来衡量模型质量 的好环。 ( 1 ) 预留法：从数据集中随机抽取预定大小的一个子集作为测试集，其余的数据 则作为训练集。 ( 2 ) 交叉验证法：整个数据集按照所要进行的学习、测试循环次数分成相当数目 的子集。在每次循环中，选取其中的一个子集作为测试集，而其它子集的并集则作为训 练集。 2 4 2w e b 文本挖掘的评价参数 ( 1 ) 分类正确率 a e c u r a c y ( m ) = 艺p ( p ) 彳c c u r a c y ( m ，p ) = p ( c ( p ) = c ( p ) ) ( 2 2 ) 彳俐川y ( m ，p ) ： 1 ，坠p ) “( p ) ( 2 _ 3 ) 10 ，c ( e ) c ( e ) 其中c ( e ) 为样本类的实际值，c ( 君) 为通过模型m 得到的e 的预测值，p ( e ) 为样本例e 的概率。 ( 2 ) 查准率 反映的是文本检索的正确性。它是检索到的目标样例集中所包含的正确检索的样例 所占比例的大小。形式定义如下【6 】：1 p厂gcis，。甩=i!j!i；毛之铲 c 2 4 ， ( 3 ) 查全率 反映的是文本检索的全面性。它是检索结果中被正确检索的数目与实际存在的满足 查询要求的对象数目的比例。形式定义如下【6 】： r e c 口，： r e l e v 瓦a n _ t c 、 r i e t _ r i e v e d l ( 2 5 ) l r e l e v a n t l 一 ( 4 ) 查准率和查全率的几何平均数2 6 】 也可使用查准率与查全率的几何平均数来衡量模型的质量。 g e op re c i s i o n ( m ) = g e o r e c a l l ( m ) = 其中，c t 为总的类别数。 ( 2 。6 ) ( 2 7 ) 第三章关联规则的研究 第三章关联规则的研究 3 1前言 关联规贝j j ( a s s o c i a t i o nr u l e s ) 的挖掘是数据挖掘研究的重要内容之一，a g r a w a l 等人 在1 9 9 3 年首先提出了从顾客交易数据库中发现用户购买模式的相关性问题，并提出了 基于频繁集的a p f i o f i 算法【8 ，9 】。最初是在超市数据环境下提出的，其目的是发现数据之 间潜在的、隐含的关系。通过分析交易数据库中顾客购买不同商品( 项) 之间的关系， 挖掘得到顾客购买行为模式，“尿布与啤酒 是关联规则挖掘最初成功的的例子。目前 关联规则已不限于事务数据库，还可以用于关系数据库和数据仓库，随着i n t e m e t 的普 及，大量的w e b 数据也可运用关联规则进行挖掘。 在a g r a w a l 提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸多的研究 人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优 化，如引入随机采样、分布式、划分的思想等【4 , 5 , 6 】，以提高算法挖掘规则的效率并对关 联规则的应用进行推广。目前，关联规则挖掘已经应用到企业的经营决策、市场分析、 金融欺诈的检测、生物制药、模式识别等多个领域【| 7 1 ，随着对关联规则挖掘研究及其应 用推广的深入，其重要性及其实用性更加显现出来。 本章第二部分是对关联规则基本概念的介绍，提出了关联规则的分类方法；第三 部分是对关联规则挖掘算法的介绍，在分析了经典的a p f i o f i 算法后，接着介绍了几种 频集算法的优化方法，最后简要介绍了并行关联规则挖掘和分布式关联规则挖掘；第四 部分详细介绍了f pt r e e 算法的主要思想和执行过程，并评价了f pt r e e 算法；第五部分 归纳了关联规则价值衡量方法。 3 2 关联规则基本概念 3 2 1 关联规则的定义和性质 关联规则形式化定义如下： 设i = i l ，i 2 ，i m ) 是项的集合，其中的元素称为项( i t e m ) 。记d 为交易( t r a n s a e f i o n ) t 的集合，交易t 是项的集合，并且t i 。对应每一个交易有唯一的标识，记作t i d 。设 x 是i 中项的一个集合，如果x c _ t ，那么称交易t 包含x 。关联规则是形如x = v y 的 蕴涵式，这里x i ，y c i ，并且x n 弘。 定义3 1关联规则的支持度是交易集d 中包含x 和y 的交易数与所有交易数 之比，记为s u p p o r t ( x ：, y ) 即 s u p p o r t ( x j y ) = i t | xuy c _ tt d i i i d i( 3 1 ) 定义3 2 关联规则的置信度，也称可信度，是指包含x 和y 的交易数与包含x 的 1 2 第三章关联规则的研究 交易数之比，记为c o n f i d e n c e f x ： y ) 即 c o n f i d e n c e ( x j y ) = i tx uy g tt d ) i i t ：x - c tt e d l( 3 2 ) 定义3 3 频繁项集，又称大项集，是指项集的出现频率耋m i n s u p 。频繁k 项集的 集合通常表示为l k ，所有的大项集可表示为：l = ul k ，其中m a x k 是最长大项集的长度。 定义3 4 非频繁项集，又称小项集，是指项集的出现频率 s u p p o r t ( y ) 。 给定一个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定 的最小支持度( m i n s u p p ) 和最小可信度( m i n c o n f ) 的关联规则。 3 2 2 关联规则的分类 我们将关联规则按不同的情况进行分类【2 7 j ； ( 1 ) 基于规则中处理变量的类别，关联规则可以分为布尔型和数值型 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系； 而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理， 将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以 包含种类变量。例如性别= “女”职业= “秘书”，是布