（计算机应用技术专业论文）粒计算在数据挖掘中的应用研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 粒计算是美国s a nj o s es t a t e 大学教授t y l i n 在1 9 9 7 年第一次提出，标志 着涉及多学科的一个应用研究领域产生。粒计算是信息处理的一种新的概念和 计算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究，是研究模 糊的、不精确的、不完整的及海量的信息处理的一个新型的重要工具。 数据挖掘是挖掘海量信息的重要工具，一些挖掘方法已逐渐趋向成熟。近 年来，国外诸多学者对粒计算在数据挖掘中的应用进行了探讨与研究，提出了 一些模型和方法，使粒计算在数据挖掘中得到了广泛的应用。 粒计算理论对一些传统的数据挖掘方法进行了革新，粒计算采用粒度的思 想来处理问题和解决问题。针对一个或某些问题或理论，来设计与构造粒或粒 度，利用构造好的粒或粒度对问题进行计算，分析等，最终获得问题解。 本文首先介绍了数据挖掘中的关联规则提取分析和文本聚类方法，然后系 统地论述了粒计算理论及粒计算在数据挖掘中的应用情况，在此基础上，提出 基于粒计算w e b 文档聚类方法( 、v d c g r c ) 和基于粒计算高效挖掘决策型关系 数据库中关联规则方法。 基于粒计算w e b 文档聚类方法，通过t f i d f 法则计算文档词条的权值， 采取设定文档阈值和平均权值相结合的方法实行降维，抽取出每篇文档的主干 词；建立了文档的主干词和二进制粒之间的转换，提出了基于粒计算提取文档 间的关联规则算法来获取文档间的频繁项集，通过本文提出的聚类方法获得聚 类结果。该方法具有一定的通用性。实验结果表明，该方法切实有效，聚类质 量较好。 基于粒计算从决策型关系数据集中快速提取关联规则方法，按照属性利用 等价类对实体进行分类，利用分类后的属性值来构建粒，提出了基于粒计算提 取决策型关系数据库的关联规则算法，来提取决策型关系数据集的关联规则， 该方法弥补了目前提取关系数据库中关联规则的部分不足。 关键词：粒计算；数据挖掘：聚类；关联规则： 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t g r a n u l a rc o m p u t i n gw a sf i r s tp u tf o r w a r di n1 9 9 7b yt x l i n ，ap r o f e s s o ri nt h e u n i v e r s i t yo fs a nj o s es t a t e ，u s a , w h i c hh a sm a r k e dt h ee m e r g e n c eo fa na p p l i e d r e s e a r c ha r e ai n v o l v i n gm u l t i s u b j e c t s g r a n u l a rc o m p u t i n gi sa l le m e r g i n gr e s e a r c h m e t h o dt od e a lw i t hi n f o r m a t i o na n dk n o w l e d g ep r o c e s s i n gw h i c hi sa nu m b r e l l a t e r mt oc o v e ra n yt h e o r i e s ，m e t h o d o l o g i e s ，t e c h n i q u e sa n dt o o l st h a tm a k eu s eo f g r a n u l e si np r o b l e ms o l v i n g i tp l a y sa ni m p o r t a n tr o l ei nt h ep r o c e s s i n gf o rf u z z y , u n c e r t a i n ，p a r t i a l ，a n dh u g ei n f o r m a t i o n d a t am i n i n gs e r v e sa sa ni m p o r t a n tt o o lf o rm i n i n gn u m e r o u sd a t a , a n ds o m e m e t h o d sh a v eb e e nw e l le s t a b l i s h e d i nr e c e n ty e a r s ，m a n yr e s e a r c h e r sa b r o a dh a v e e x p l o r e da n di n v e s t i g a t e dt h ea p p l i c a t i o no fg r a n u l a rc o m p u t i n gt od a t am i n i n g t h e y h a v ep u tf o r w a r ds o m em o d e l sa n dm e t h o d s 。e n a b l i n gg r a n u l a rc o m p u t i n gt ob e w i d e l yu s e di nd a t am i n i n g t h et h e o r yo fg r a n u l a rc o m p u t i n g , w h i c ha d o p t st h ep r i n c i p l eo fg r a n u l a r i t yt o d e a lw i t ha n ds o l v em a t t e r s i sa l li n n o v a t i o no fs o m et r a d i t i o n a lw a y so fd a t am i n i n g i td e s i g n sa n dc o n s t r u c t sg r a n u l eo rg r a n u l a r i t ya c c o r d i n gt oo n eo rm o r em a t t e r so r t h e o r i e s ，a n di t u n t i l i z e st h ec o n s t r u c t e dg r a n u l eo rg r a n u l a r i t yt oc o m p u t ea n d a n a l y z et h em a t t e r s ，w h i c hi nt h ee n dl e a d st oas o l u t i o n t h ep r e s e n tt h e s i sf i r s ts y s t e m a t i c a l l yc l a r i f i e st h et e x tc l u s t e r i n gm e t h o da n d t h ea n a l y s i so fd r a w i n ga s s o c i a t i o nr u l e s s e c o n d l y , t h et h e s i sg i v e sad e t a i l e d i n t r o d u c t i o no ft h et h e o r i e sr e l a t e dt og r a n u l a rc o m p u t i n ga n dt h es t a t u so fi t s a p p l i c a t i o nt od a t am i n i n g b a s e do nt h es t u d ya b o v e ，t h et h e s i sf u r t h e rp u t sf o r w a r d am e t h o do fw e bd o c u m e n tc l u s t e r i n gb a s e do ng r a n u l a rc o m p u t i n g ( w d c g r c ) a n da m e t h o db a s e do ng r a n u l a rc o m p u t i n gt o e f f i c i e n t l y o b t a i na s s o c i a t i o nr u l e si n d e c i s i o n m a k i n gr e l a t i o nd a t a s e t i nt h i sp a p e r ，am e t h o do fw e bd o c u m e n tc l u s t e r i n gb a s e do nt h eg r a n u l a r c o m p u t i n gi sp r e s e n t e d t h em e t h o dc o m p u t e st h ew e i g h tv a l u eo ft h ew o r d si n d o c u m e n t sb ya d o p t i n gt h et f i d fp r i n c i p l e m e a n w h i l e ，c o m b i n i n gw a y sd e f i n i n g d o c u m e n t st h r e s h o l da n da v e r a g ew e i g h tv a l u ea r ea d o p t e dt or e d u c ed i m e n s i o n sa n d e x t r a c tt h ek e y w o r d si ne a c hd o c u m e n t t h em e t h o de s t a b l i s h e st h et r a n s f o r m a t i o n 西南交通大学硕士研究生学位论文第1 i i 页 b e t w e e nt h ek e y w o r d si nd o c u m e n t sa n dt h eb i n a r yg r a n u l e s ，a n da d o p t st h e a l g o r i t h mo fa s s o c i a t i o nr u l e sb a s e do ng r a n u l a rc o m p u t i n gt o o b t a i nf r e q u e n t i t e m s e t sb e t w e e nd o c u m e n t s am e t h o do ft h ec l u s t e r i n gi sp r e s e n t e di nt h ep a p e rt o o b t a i nt h ec l u s t e r i n gr e s u l t t h ee x p e r i m e n ts h o w st h a tt h em e t h o di sp r a c t i c a la n d f e a s i b l e ，w i t hg o o dq u a l i t yo fc l u s t e r i n g 1 1 l ep a p e rh a sp r e s e n t e dam e t h o db a s e do ng r a n u l a rc o m p u t i n gt oe f f e c t i v e l y o b t a i na s s o c i a t i o nr u l e si n d e c i s i o n m a k i n gr e l a t i o nd a t a s e t b a s e d o ng r a n u l a r c o m p u t i n g , t h e m e t h o dc o n s t r u c t sm o d e l sf o rt h er e l a t i o nd a t a s e t , u t i l i z e s e q u i v a l e n c ec l a s st oc l a s s i f yt h ee n t i t yb a s e do na t t r i b u t es oa st oc o n s t r u c tg r a n u l e s ， a n db r i n g sf o r w a r dt h ea l g o r i t h mb a s e do ng r a n u l a rc o m p u t i n gt oo b t a i na s s o c i a t i o n r u l e si nd e c i s i o n m a k i n gr e l a t i o nd a t a s e t ，t h ew a y sr e m e d yp a r ti n a d e q u a t ee x t r a c t a s s o c i a t i o nr u l e so ft h ec u r r e n tr e l a t i o n a ld a t a b a s e k e yw o r d s ：g r a n u l a rc o m p u t i n g ；d a t am i n i n g ；c l u s t e r i n g ；a s s o c i a t i o nr u l e s 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 本文研究背景 粒计算f 1 】( g r a n u l a rc o m p u t i n g ，g r c ) 是美国s a nj o s es t a t e 大学教授 t y l i n 在1 9 9 7 年第一次提出，标志着涉及多学科的一个应用研究领域产 生。粒计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度 的理论、方法、技术和工具的研究【甜，是研究模糊的、不精确的、不完整 的及海量的信息处理的重要工具。 国外的诸多学者对它进行了广泛的研究与探讨，提出了许多有关粒计 算的理论模型，逐步完善粒计算的相关理论研究，粒计算理论也得到了切 实而广泛应用。数据挖掘是挖掘海量信息的重要工具，一些挖掘方法已逐 渐趋向成熟。粒计算理论对一些传统的数据挖掘方法进行了革新，粒计算 采用粒度的思想来处理问题和解决问题。针对一个或某些问题或理论，来 设计与构造粒或粒度，利用构造好的粒或粒度对问题进行计算，分析等， 最终获得问题解。 粒计算在数据挖掘领域中有着广泛的应用前景，目前，国际上已形成 专门的研究群体，定期召开一定的学术会议，发表的相关文献越来越多， 但在粒的计算方面，所提出的一些近似推理方法在理论上还缺乏完备性， 同时也缺少高效的粒计算算法，这也是本文的研究背景。 而国内，对粒计算的研究刚刚开始，目前还仅局限于理论方面的研究， 对粒计算的应用很少涉及，本文针对国内的这种情况，对粒计算在数据挖 掘中的应用情况进行了深入的研究与探讨，在此基础上，提出了基于粒计 算w e b 文档聚类方法( w d c g r c ) 和基于粒计算高效挖掘关系数据库中的 关联规则等。 1 2 国内外研究现状 1 9 7 9 年，美国控制论专家l a z a d e h 第一个介绍了信息粒化 ( i n f o r m a t i o ng r a n u l a t i o n ) 的概念p 1 ，并认为它在f u z z y 集中有着潜在的应 用；1 9 8 2 年，美国s t a n f o r d 大学教授h o b b s 在第九届国际人工智能大会上提 出了粒度( g r a n u l a r i t y ) 理论i ，该理论抓住了粒计算的基本特征，以不 同的粒度来概化世界，以粒度之问的交换来处理问题；1 9 9 6 年，z a d e h 提 出了一个新的研究分支词计算( c w ) 1 5 1 ，其目的：为将来的智能计算以 西南交通大学硕士研究生学位论文第2 页 及基于词的信息系统实现计算建立一个理论基础，标志着模糊粒度化理论 的诞生：1 9 9 7 年，z a d e h 重新阐述了信息粒化的重要性f 6 】，z a d e h 的工作激 发了学者对粒度计算的研究兴趣。粒计算和词计算的重要性在于它能达到 高档机器智商m i q ( m a c h i n ei n t e l l i g e n c eq u o t i e n t ) 的目标，就是通过重新 标记人的能力实现不用任何测量和任何复杂计算就能达到的目标【1 ”。 t y l i n 在文献【8 9 】中，提出了使用邻域来作为粒计算的表达，它是 基于r o u g h 集划分理论的一个扩展：加拿大r e g i n a 大学教授y y y a o 在文献 【2 】中，讨论了粒计算的基本问题，阐述了粒的构建和粒的计算，提出了基 于幂代数概念下粒计算的集合理论模型。随后，粒计算的研究迅速发展， 研究成果不断涌现。 国外学者针对粒计算在数据挖掘中的应用，也进行了广泛的研究。 1 9 9 8 年，t y l i n 提出了基于二进制邻域系统的二进制粒结构1 8 ，随后， t y l i n 着重阐述了二进制邻域系统的表示【9 】，该文中，用表的格式来表示 二进制关系，这个表将被称为信息表的扩展，这样，信息表处理将扩展为 二进制关系粒结构的处理。1 9 9 9 年，t y l i n 在文献【1 0 】中提出了一个新的 数据挖掘理论，在原有的关系数据库中，附加了粒计算的概念和二进制邻 域系统，用粒计算来处理二进制关系，一系列二进制关系就是粒结构，数 据挖掘就是粒结构的处理。该理论为基于粒计算基础上的数据挖掘提供了 导向。2 0 0 1 年，y y y a o 提出了一个基于粒计算规则挖掘的一个框架【1 1 】。 该框架是基于粒计算模型的概念的外延来定义的，称为：基于粒计算模型 的数据挖掘，提出的模型可能被认为数据挖掘形式和数学建模的第一步。 它通过内涵和外延的一部分作为特征，信息表被使用定义精确的内涵和外 延，语言的公式来定义内涵，论域对象的子集来定义外延，通过概念的内 涵来表达挖掘规则，通过概念的外延来解释，随着这个模型被提出，数据 挖掘一些存在的方法可以被比较和分析。 而国内，对粒计算的研究刚刚开始，张钹院士和张铃教授提出了基于 商空间的粒度世界模型【j ，在此基础上，于2 0 0 3 年在文献 1 4 】中，把粒度 世界模型理论推广到模糊商空间理论模糊粒度计算方法，给出了模糊 商空间的结构，证明了利用模糊等价关系可以将原来的商空间理论推广成 模糊商空间理论，并给出了模糊商空白j 理论的几个基本定理，这些定理为 粒度计算提供了强有力的数学模型和工具。刘清教授在文献 1 5 】中，重点 西南交通大学硕士研究生学位论文第3 页 阐述了粒及粒计算在逻辑推理中的应用，讨论了信息粒的结构及其实例， 基于r o u g h 集方法定义了决策规则粒，构造了决策规则粒库，定义了粒语 言，描述了这种语言的语法、语义、粒语句的运算法则和粒相关的几个性 质，基于这些概念，构造了一种逻辑推理的新模型。 国内，粒计算在数据挖掘中的应用文献很少涉及，这也是本文的研究 的出发点。 1 3 本论文的组织 本论文的主要研究工作包括几个方面： 第1 章为本文绪论部分。首先分析了本文的选题背景和研究意义，然 后介绍了国内外研究现状。 第2 章是数据挖掘相关理论论述。本章首先阐述了数据挖掘基本概念 与发展趋势，然后针对本课题研究所涉及到的相关理论进行了重点阐述。 包括1 ) 关联规则提取及主要算法分析；2 ) 文本挖掘；3 ) 文本聚类算法 等。 第3 章是粒计算理论及其应用。详细阐述了粒计算相关理论、粒计算 模型与方法、粒计算在数据挖掘中的应用以及粒计算的发展方向等。 第4 章针对本文提出的基于粒计算w e b 文档聚类，从以下几个方面 重点进行了阐述：1 ) w e b 文档建模；2 ) 文档粒的构建；3 ) 生成频繁项 集；4 ) 聚类。 第5 章针对本文提出的基于粒计算高效挖掘决策型关系数据库中的关 联规则。从以下几个方面重点进行了阐述：1 ) 引言部分，对提取关系数 据库中的关联规则进行了分析；2 ) 基于粒计算对数据进行建模；3 ) 提取 关联规则； 第6 章是实验与评价部分，本部分包括：1 ) 基于粒计算w e b 文档聚 类，对聚类结果和其他算法聚类结果进行对比，最后给出了性能评价；2 ) 基于粒计算与a p r i o r i 算法提取医学数据集中的关联规则对比实验。 第7 章是本文的总结与展望，该章总结了全文，对全文的工作给出了 评价并指出今后所做的工作。 西南交通大学硕士研究生学位论文第4 页 第2 章数据挖掘相关知识背景 2 1 数据挖掘基本概念与发展趋势 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据 中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和 知识的过程。从商业角度上讲，数据挖掘可以定义为：按企业既定业务目 标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知 的规律性，并进一步将其模型化的先进有效的方法i 拍l 。 数据挖掘是一门交叉学科，它汇聚了数据库、人工智能、机器学习、 统计学、模式识别、可视化、并行计算和神经网络等不同学科和领域，近 年来受到各界的广泛关注。同时，数据挖掘也为这些学科的发展提供了新 的机遇和挑战。 数据挖掘的研究正方兴未艾，其发展前景已经在国际上得到了确认。 目前，国内外很多大学、研究机构和公司都已经在这个方面进行了实质性 的研究和产品开发。研究焦点可能会集中到以下几个方面： ( 1 ) 研究在网络环境下的数据挖掘技术，特别是在因特网上建立数据挖 掘服务器，并且与数据库服务器配合，实现w e b 挖掘( w e bm i n i n g ) 。 ( 2 ) i j f l 强对各种非结构化数据的开采，文本挖掘成为了一个目前研究的 热点。其它的非结构化数据有图形数据、视频图像数据、声音数据乃至综 合多媒体数据的开采。 ( 3 ) 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语 言，也许会像s q l 语言一样走向形式化和标准化。 ( 4 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户 理解，也便于在知识发现的过程中进行人机交互。 ( 5 ) 处理的数据将会涉及到更多的数据类型，这些数据类型或者比较复 杂，或者是结构比较独特。为了处理这些复杂的数据，就需要一些新的、 更好的分析和建立模型的方法，同时涉及到为处理这些复杂或独特数据所 做的费时和复杂数据准备的一些工具和软件。 ( 6 ) 交互式发现。 ( 7 ) 知识的维护更新。 西南交通大学硕士研究生学位论文第5 页 2 2 关联规则提取分析及算法 2 2 1 关联规则的基本概念 关联规则数据挖掘首先由a g r a w a l ，i m i e h s k i 和s w a m i l 1 提出。关联规 则的挖掘是对给定的一个交易数据库d ，求出所有满足最小支持度和最小 可信度的关联规则的过程。该问题可分解为两个子问题： ( 1 ) 根据给定的最小支持度，按项目数自小而大的顺序找出数据库d 中频繁项目集； ( 2 ) 根据频繁项目集和指定的最小可信度生成关联规则。 设有i = i l ，1 2 ，i 。 是由m 个不同的项组成的集合。给定一个事务数据 库d ，其中每一个事务t 是i 中一组项的集合，即t i ，t 有一个唯一的 标识符t i d 。若项集a i 且a t ，则称事务t 包含项集a 。如果项集a 中包含k 个项，则称为k 项集。 定义2 1 ：关联规则是形如a = b 的蕴涵式，其中a c i ，b c i ，a nb = o 。 关联规则a = b 在事物数据库d 中的支持度是d 中事务包含a u b 的百分 比，它是概率p ( a u b ) ，记作：s u p p o r t ( a = b ) = p ( a u b ) = i a u b h d i 。 定义2 2 ：关联规则a = b 在事务数据库d 中的可信度是d 中包含a 的事务同时也包含b 的百分比，它是条件概率p ( b i a ) ，记 作：c o n f i d e n c e ( a = b ) = p ( b i a ) = i a u b i i a 。 ， 定义2 3 ：如果事物数据库d 上的关联规则a = ) b ，同时满足大于最 小支持度阂值( m i n _ s u p ) 和最小置信度闽值( r a i n c o n o 的关联规则为强关联 规则。最小支持度表示项集在统计意义上的最低重要性，最小可信度表示 规则的最低可靠性。 关联规则挖掘过程就是从中产生所有强关联规则的过程。即在事物数 据库d 中找出所有具有用户给定的最小支持度m i n s u p 和最小可信度 r a i nc o n f 的关联规则。这样，每一条被挖掘出来的关联规则就可以用一个 蕴含式，两个阈值唯一标识。 可信度是对关联规则f 确程度的衡量，表示规则的强度；支持度是对关 联规则重要性的衡量，表示规则的频度。规则的支持度说明它在所有事务 西南交通大学硕士研究生学位论文第6 页 中有多大的代表性，其值越大，关联规则越重要。如果关联规则的可信度 很高，但支持度很低，说明该关联规则实用机会很小：如果支持度很高，而 可信度很低，则说明该规则不可靠。 定义2 4 ：如果一个项目集a 满足最小支持度阈值r a i ns u p ，即 s u p p o r t ( a ) - - - 毛n i u s u p ，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。频繁k 项集 通常记为l k 。反之，如果个项目集a 不满足最小支持度，则称为非频 繁项集。 定义2 5 ： 候选项集是潜在的频繁项集的集合，是频繁k 1 项集的超 集( s u p e r s e t ) ，含有k 项的候选项集表示为c k ，由它构成频繁k 项集l k 。 2 2 2 关联规则主要算法 由于挖掘算法在数据挖掘过程中起着至关重要的作用，因此自从 a g r a w a l 等提出挖掘交易据库中项集间的关联规则问题以后，很多人对此 进行了研究，这些研究包括：关联规则的挖掘理论的探索、原有算法的改 进和新算法的设计、并行关联规则挖掘( p a r a l l e la s s o c i a t i o nr u l em i n i n g ) 以及量化关联规则挖掘( q u a n t i t i v ea s s o c i a t i o nr u l em i n i n g ) 等。 经典的a p r i o r i 算法由a g r a m a l 和s r i k a n t 1 8 1 提出。该算法是一种挖掘 布尔关联规则频繁项集的算法。它利用频繁项集性质的先验知识，使用一 种称为逐层搜索的迭代方法来找出所有的频繁项集。首先扫描事务数据库 d ，统计库中事务的数量和各个不同的项( 1 项集) 所出现的次数，进而根据 最小支持度r a i n s u p 获得所有的频繁1 项集l l 。然后用l 1 查找频繁2 项 集l 2 ，如此下去，直到不能找到频繁k 项集。找每个h 需要一次数据库 扫描。 a p r i o r i 算法的具体描述如下： 输入：事务数据库d ；最小支持度阈值r a i ns u p ； 输出：d 中的频繁项集l 。 l l = f i n d f r e q u e n t 一1 i t e m s e t s ( d ) ； 频繁1 项集 f o r ( k = 2 ；l 1 a ；k + + ) 西南交通大学硕士研究生学位论文第7 页 c k = a p r i o r i _ g e n ( l k 1r a i n s u p ) ；，新的候选项集 f o re a c ht r a n s a c t i o nt d c t = s u b s e t ( c k ，t ) ；事务t 中包含的候选项集 f o re a c hc a n d i d a t ec c 。 c c o u n t + + ； h = c c k ic c o u n t = m i n s u p ) r e t u r n l ：uk l k ； a p r i o r i _ g e n 算法 p r o c e d u r ea p r i o r i _ g e n ( i a 1 ：f r e q u e n t ( k 一1 ) 一i t e m s e t ；m i n s u p ：s u p p o r t ) f o re a c hi t e ms e t1 1 l k - 1 f o re a c hi t e ms e t1 2 l k 1 i f ( 1 1 【l 】= 1 2 【1 】) ( 1 1 【2 = 1 2 【2 】) a a ( i x 【k - 2 = 1 2 【k - 2 】) ( i l 【k 1 】1 2 【k - 1 1 ) t h e n c ：i ：葡2 ；，连接步：产生候选项集集合 i f h a s i n f r e q u e n t s u b s e t ( c ，h 1 ) t h e n d e l e t ec ：剪枝步：删除非频繁候选项集 e l s ea d dc t o c k ； r e t u r nc k ； 判断候选k 项集的k i 子项是否都在频繁k 一1 项集中 p r o c e d u r eh a s i n f r e q u e n t s u b s e t ( c ：c a n d i d a t ek i t e ms e t ；h 1 ：f r e q u e n t ( k - 1 ) 一i t e ms e t ) 西南交通大学硕士研究生学位论文第8 页 f o re a c h ( k 1 ) s u b s e t so fc i fs t l k 1t h e n r e t u r nt r u e ； r e t u r nf a l s e ： 该算法中有两个关键步骤：连接步和剪枝步。 ( 1 ) 连接步：为找出h ( 频繁k 项集) ，通过l k 1 与自身连接( h 窘h 1 ) 产生候选k 项集，该候选项集记作c k 其中，h 1 的元素是可连接的。 ( 2 ) 剪枝步：c k 是l k 的超集，即它的成员可以是也可以不是频繁的， 但所有的频繁k 项集都包含在c k 中。扫描数据库，确定c k 中每一个候选 的计数，从而确定h ( 计数值不小于最小支持度计数的所有候选是频繁的， 从而属于k ) 。然而，c k 可能很大，这样所涉及的计算量就很大。为压缩 c k ，使用a p r i o r i 性质：任何非频繁的( k 一1 ) - 项集都不可能是频繁k 项集的子 集。因此，如果一个候选k 项集的( k 1 ) 项集不在k 1 中，则该候选项也 不可能是频繁的，从而可以由c k 中删除。这种子集测试可以使用所有频 繁项集的散列树快速完成。 一旦从数据库d 中的事务中找出频繁集，就可以由它们的产生强关联 规则。 该算法的缺点： ( 1 ) 它可能产生大量的候选项集； ( 2 ) 重复扫描数据库； 为了避免每次都要扫描数据库，于是产生了a p r i o r i 的改进算法：主 要有a p r i o r i t i d 18 j 和a p r i o r i h y b i r d 1 9 1 算法。该算法也使用了a p r i o r i g e n 函数以便在遍历之前确定候选项目集。这个算法的新特点是在第一次遍历 之后就不使用数据库d 来计算支持度，而是用集合c k 来完成。 目前，关联规则挖掘方面的研究己经取得了较大的进展，但对下列问 题仍有待于进一步研究，如挖掘算法高效性，挖掘对象的广泛性，挖掘的 西南交通大学硕士研究生学位论文第9 页 可视化问题，模式评估等。 2 3 文本挖掘 文本是存储和交换信息的最自然的方式，i n t e r n e t 上大部分信息也都 是存储在文本中，因此文本挖掘是一个比较热门的研究课题。当数据挖掘 的对象完全是文本数据时，这个挖掘的过程就是文本挖掘。文本挖掘是指 从大量的文本数据中挖掘出潜在的、事先未知的、对用户有用的知识的过 程。一些传统的挖掘任务包括简单的关键字搜索、相似性度量、聚类和分 类等。文本最复杂的一层就是把自然语言处理技术应用到文本挖掘中，以 发现文本中隐含的语义，例如语音自动问答系统。 文本挖掘包括：文本总结技术，文本分类技术，文本聚类技术。文本 总结技术是指从文档中抽取出关键信息，然后以简洁的形式对文档的信息 进行摘要或表示：文本分类技术是指按照预先定义的主题类别，利用计算 机自动为文档集合中的每一个文档进行分类；而文本聚类指的是将文档集 合中的文档分为更小的簇，要求同一簇内的文档之间的相似性尽可能大， 而簇与簇之间的相似性尽可能小。 与数据库中的结构化数据相比，文本是半结构化的或者就没有结构。 即使具有一些结构，也是着重于文本的格式，而并非文档内容，不同类型 文档的结构也不一致。文档的内容是人类所使用的自然语言，计算机很难 直接处理其语义，因此，现有的数据挖掘技术无法直接对其挖掘，我们需 要对文本进行预处理，抽取能代表文本特征的元数据。 文本特征分为描述性特征和语义性特征。描述性特征是指文本的名 称、日期、大小、类型等；语义性特征是指文本的作者、机构、标题、内 容等。通常描述性特征我们比较容易得到，而语义性特征则较难得到。因 此在对文本进行挖掘之前，首先要找到一种能够被计算机所能处理的表示 方法，先对文档中的信息进行预处理，即去掉一些标记，例如h i m l 中的 t a g 等，提取出结构中各个标记符中的文本信息，然后按照普通文本的处 理方式表示出来。对文本进行预处理主要是识别文本中词条的意义，而且 提取的多数是文本集中表示的概念，从文本的内容抽取出来一些能代表文 本内容的词条，通过分析这些特征词条，达到分析文本内容的目的。 2 4 文本聚类算法 聚类( c l u s t e r i n g ) 是一个将数据集划分为若干组( c l a s s ) 或类( c l u s t e r ) 的 西南交通大学硕士研究生学位论文第1 0 页 过程，并使得同一个组内的数据对象具有较高的相似度：而不同组中的数 据对象相似度较低。相似或不相似的描述是基于数据描述属性的取值来确 定的，通常是利用( 各对象问) 距离来进行表示的。聚类与分类相似，都是 将数据进行分组。但与分类的根本不同在于：分类问题中我们知道训练集 的分类属性，而聚类问题则需要我们从数据集中找这个分类属性【2 0 】【2 1 】【2 2 1 。 聚类中的分组也称为簇。簇的定义如下：一些相似成员的集合，不同簇中 的成员是不相似的；簇中两点之间的距离要小于簇中的一点与簇外任一点 之间的距离。 聚类在本质上是一种通过对对象集合按照某种规则进行划分或覆盖 从而发现隐含的潜在有用的信息的一种知识发现的方法。文档集合作为一 种特殊的对象集合，它拥有适合自身特征的聚类算法：层次聚类法、平面 划分法、简单贝叶斯法和神经网络聚类方法【2 3 1 。 2 4 i 层次聚类法 层次聚类法是建立在给定数据对象集合的一个层次性的分解，根据层 次分解的形成过程，这类方法可分为分裂( 自顶向下) 的，或合并( 自底向上) 的。为了弥补合并或分裂的严格性，层次聚类方法的聚类质量可以通过分 析每个层次划分中的对象链接，或集成其它的聚类技术来改进。 对于给定的文档集合d = ( d 1 ，d 2 , d 3 ，d 。) ，层次聚类的具体过程如下： ( 1 ) 将d 中的每个文档d i 看作一个具有单个成员的类c i - d i ，这 些类构成了d 的一个聚类c = ( c 1 ) c 2 ，c 。) ； ( 2 ) 计算c 中每对类c i ，c j 之间的相似度s i m ( c i ，c j ) ； ( 3 ) 选取具有最大相似度的类对a r g m a x s i m ( c i ，c j ) ，并将c j 和q 合并 为一个新的类c k = c i uo j ，从而构成d 的一个新的聚类c = ( c l ，c 2 ，c 丑) ； ( 4 ) 重复上述步骤，直至c 中剩下一个类为止。 该过程构造出一颗生成树，其中包含了类的层次信息以及所有类内和 类间的相似度。层次聚类方法是最常用的聚类方法，它能够生成层次化的 嵌套类，而且准确度高。但是，在每次合并时，需要全局地比较所有类之 间的相似度，并选择出最佳的两个类，因此运算速度比较慢，不适合大量 文档的集合。 2 4 2 平面划分法 平面划分法与层次聚类法的区别在于，它将文档集合水平地分割为若 西南交通大学硕士研究生学位论文第1 1 页 干类，而不是生成层次化的嵌套类。它首先得到初始k 个划分的集合， 参数k 是要构建划分的数目，然后它采用迭代重定位技术，试图通过将 对象从一个簇( c l u s t e r ) 移到另一个簇来改进划分的质量。对于给定的文档 集合d = ( a l l , d 2 ，d 3 ，d 。) ，平面划分法的具体过程如下： ( 1 ) 确定要生成的类的数目k ； ( 2 ) 按照某种原则生成k 个聚类中心作为聚类的种子s = ( s l ，s 2 ，s 3 ，s k ) ； ( 3 ) 对d 中的每个文档d i ，依次计算它与所有各个种子s i 的相似 度s i m ( d i ，s j ) ； ( 4 ) 选取具有最大相似度的种子a r g m a x s i m ( c i , s j ) ，将d i 归入以s i 为聚 类中心的类c j ，从而得到d 的一个聚类c = ( c 1 ，c 2 ，c 。) ( 5 ) 重复步骤2 、3 、4 若干次，以得到比较稳定的聚类结果。 该方法的运行速度快，但是必须事先确定k 的取值，且种子选取的 好坏对聚类结构有较大的影响。其典型代表就是k m e a n s 聚类和模糊c 均值聚类【2 4 1 。 2 4 3 简单贝叶斯法 若文档采用d f 向量表示法，即文档向量的分量为一个布尔值，0 表 示相应的关键字在该文档中未出现，1 表示出现，则文档d 属于c 类文 档的概率为： p ( c ) 几p ( d ( f j ) i c ) 以c id ) 。可前丽 ( 2 - 1 p ( d 酬c ) - 眢( 2 - 2 ) 其中p ( d ( f j ) i c ) 是在c 类文档中特征f j 出现的条件概率的拉普拉 斯概率估计，n ( d ( f j ) l c ) 是c 类文档特征中f j 出现的文档数，d c 为c 类文档所包含的文档数目 2 5 1 。若文档采用t f 向量表示法，即文档向量的 分量为相应的关键字在该文档中出现的频度，则文档d 属于c 类的概 率为： 西南交通大学硕士研究生学位论文第1 2 页 尸( c ) 丌p ( d ( 厉) lc ) 阡4 尸( c l 咖可商而而而而 ( 2 。) 7公 p ( 厅i c ) - 两i + 两r f ( f 币, i c 历) ( 2 - 4 、 其中p ( c ) 代表一个文档属于c 类的概率；p ( f jl c ) 是对在c 类文 档中特征f i 出现的条件概率的拉普拉斯概率估计；t f ( f j ，c ) 是c 类文 档中特征f i 出现的频度，v 为单字辞典集的大小，等于文档表示中所包 含的不同特征总数目，t f ( f j ，d ) 是在文档d 中特征f i 出现的频度。由于 关键字辞典集v 中许多的特征f i 均不出现在文档d 中，从而t f ( f j ，d ) = 0 ，所以上式变为： 尸( c ) 兀p ( d ( ，) i c ，” 删妒雨卉而矛 ( 2 。5 ) 2 4 4 神经网络聚类方法 目前用于文本聚类的神经网络方法主要有两种：第一种是竞争学习 ( c o m p e t i t i v el e a r n i n g ) ，第二种是自组织特性映射( s e l f - o r g a n i z i n gf e a t u r e m a p ，简称s o m ) 。下面主要介绍s o m l 26 1 。s o m 聚类是一种无监督的聚 类方法，其聚类过程是通过若干个单元竞争当前对象来进行的。权重向量 最接近当前对象的单元成为活跃的或获胜的单元。为了更接近输入对象， 对获胜单元及其最近的邻居的权重进行调整。s o m 假设在输入对象中存 在一些拓扑结构或顺序，单元将最终在空间呈现这种结构。单元的组织形 成一个特性映射。s o m 被认为类似于大脑的处理过程，很适合处理二维 或三维空间中的可视化高维数据。s o m 网络的基本结构由输入层和竞争 层组成。输入层由1 1 个输入神经元组成，竞争层由m x m = m 个输出神 经元组成，构成一个二维平面阵列。输入层的各神经元与竞争层的各神经 元之间实现全互连接。有时竞争层各神经元之间还实行侧抑制连接。网络 中有两种连接权值，分别是神经元对外部输入反应的连接权值和神经元之 间的连接权值，它的大小控制着神经元之间的交互作用的大小。根据学习 规则，该网络对输入模式反复学习，能捕捉住各个输入模式特征，并对其 进行自组织学习。竞争层的任一神经元都可以代表聚类结果，在竞争层中 西南交通大学硕士研究生学位论文第1 3 页 进行自动聚类并将聚类结果表现出来。设网络的竞争层神经元向量为b i = ( b j l ，b j 2 9o - ，b j