（计算机软件与理论专业论文）文本关联分析中频繁项集挖掘算法的研究与改进.pdf

太原理i ：大学硕十研究生学位论文 文本关联分析中 频繁项集挖掘算法的研究与改进 摘要 信息时代为我们带来了海量数据，如何帮助人们有效地收集和选择感 兴趣的信息，并且在日益增多的信息中发现潜在有用的知识已经成为信息 技术领域的热点问题。面对这样的挑战，数据挖掘和知识发现技术应运而 生，并得以蓬勃发展。文本关联分析是文本挖掘领域的重要挖掘任务之一， 它是从文档集合中找出不同词语之间的关系的过程。其多数方法是从数据 挖掘领域的关联规则挖掘借鉴而来。 首先，本文对基于关键字的文本关联分析的特点进行了研究，它与传 统关系数据库项集间的关联分析类似。可以把文本看成事务、文本中的关 键词看成事务中的项，这样文本数据库中关键字的关联分析问题就转化成 事务数据库中事务项的关联分析问题。但由于文本数据库的高维稀疏性， 对不同的文本集使用相同的最小支持度阈值而产生的频繁项集，其规模大 小相差甚远。因此阈值的设定成为文本关联分析的一个难点。 其次，本文重点研究了n 个最频繁项集挖掘算法- - i n t v m a t r i x 。该算法 使用了阈值动态调整策略，这样就解决了阈值难以设定的问题，从而可以 通过指定的频繁项集数目n 来控制产生频繁项集的规模。但其缺点是构造 倒排矩阵容易造成空间上的浪费，并且倒排矩阵中建立项之间的联系又需 要多次扫描数据库，造成了时间上的浪费。 然后，针对i n t v m a t r i x 算法存在的问题，本论文提出了一种基于改进 的f p t r e e 挖掘n 个最频繁项集的算法。先对文本数据库的事务项以及整 个数据库进行排序，同时将非频繁项删除，这样就大大减少了生成f p t r e e 时搜索共享前缀的时间。接着在改进的f p t r e e 的基础上来构造局部频繁 项的c o f i t r e e ，就可以省去对非频繁项集的扫描。本算法依然采用了阈值 动态调整这一策略，从而在技术上为产生n 个最频繁项集作了保证。 太原理i ：人学硕士研究生学位论文 最后，通过在同一文本数据库的基础上设置不同频繁项集数n ，对改 进后的算法与i n t v m a t r i x 算法进行分析与比较。实验结果证明，由于采用 改进后的f p t r e e 来构造局部c o f i t r e e ，以及对算法中数据结构的优化， 在挖掘文本数据库时，算法的时间和空问利用率得以提高。 关键字：数据挖掘，文本挖掘，文本关联分析，n 个最频繁项集，f p t r e e ， c o f i t r e e 太原理工大学硕士研究生学位论文 r e s e a r c ha n di m p r o v e m e n ta b o u tt h e a l g o r i t h mo fm i n i n gf r e q u e n ti t e ms e t s i nt e x ta s s o c i a t l 0 na n a l y s i s a bs t r a c t i nt h ei n f o r m a t i o ne r a ，ag r e a td e a lo fd a t aa r eb r o u g h tt ou s ，i ta l r e a d y b e c o m ei n f ot e c h n i q u ef i e l d 7sh o ti s s u et h a th o wt oh e l pp e o p lec o l l e c ta n d s e l e c ti n t e r e s t e di n f o r m a t i o n ，a n dd i s c o v e r yu n d e r l y i n g ，u s e f u lk n o w l e d g ei n i n c r e a s i n g l yi n f o r m a t i o n i nt h i ss i t u a t i o n ，d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y i nd a t a b a s e se m e r g ea st h et i m e sr e q u i r e 。t e x ta s s o c i a t i o na n a l y s i st h a tf i n d s c o n n e c t i o nb e t w e e nd i f f e r e n tw o r d sf r o md o c u m e n tm a r s h a li sai m p o r t a n tt a s k i nt h ea r e ao ft e x tm i n i n g m a j o r i t ym e t h o d su s et h ea s s o c i a t i o nr u l eo fn o r m a l d a t am i n i n gf i e l d f i r s t ，t h i sp a p e rr e s e a r c h e st h ec h a r a c t e r i s t i c so ft e x ta s s o c i a t i o na n a l y s i s w h i c hb a s e do nk e y w o r d s ，i t sj u s tl i k et h ec o n v e n t i o n a la s s o c i a t i o na n a l y s i s w ec a nr e g a r dt e x ta sa f f a i r , k e y w o r d sa si t e m s ，t h u st h ek e y w o r d sa s s o c i a t i o n a n a l y s i so f t e x td a t a b a s et r a n s f o r mt h en o r m a ld a t a b a s ea s s o c i a t i o na n a l y s i s b u t b e c a u s eo ft h eh i g hd i m e n s i o na n ds p a r s i t yc h a r a c t e r , u s i n gt h es a m em i n s u p p o r tt h r e s h o l do nd i f f e r e n tt e x td a t a b a s ew i l ll e a df r e q u e n ti t e m ss i z eh a v i n g h u g ed i s c r e p a n c y s oe n a c t m e n ts u p p o r tt h r e s h o l db e c o m ead i f f i c u l t yo f t e x t a s s o c i a t i o na n a l y s i s s e c o n d ，t h i sp a p e rr e s e a r c h e st h ea l g o r i t h mo fm i n i n gnm o s tf r e q u e n ti t e m s e t s i n t v m a t r i x t h i sa l g o r i t h mu s et h es t r a t e g yo fd y n a m i ca d j u s t i n gs u p p o r t t h r e s h o l d ，t h e r e b yw ec a nc o n t r o lt h ed i m e n s i o n so ff r e q u e n ti t e m s e t sb y i l l 太原理工大学硕士研究生学位论文 i n p u t t i n gt h en u m b e rn i t sd e f e c ti st h a ts t m c t u r ei n v e r s em a t r i xc a nb r i n go n s p a c ew a s t i n g ，a n db u i l d i n ga f f i l i a t i o nb e t w e e ni t e m sn e e d ss c a nd a t a b a s em a n y t i m e s ，i tw i l lb r i n go nt h ew a s t eo ft i m e t h i r d ，a i m i n ga tt h ep r o b l e m so fi n t v m a t r i x ，t h i sp a p e ra d v a n c eak i n do f a l g o r i t h mw h i c hc a l l e dm i n i n gnm o s tf r e q u e n ti t e ms e t sb a s e di m p r o v e d f p t r e e ，i ta r r a n g et h eo r d e ro fi t e m sa n dt h ew h o l ed a t a b a s e ，m e a n w h i l ed e l e t e t h enonf r e q u e n ti t e m s ，t h u si tc a nr e d u c et h et i m ew h e nw es e a r c hs h a r ep r e f i x a l ， t h e ni tc o n s t r u c tt h ec o f i t r e eo fl o c a lf r e q u e n ti t e m sb a s e do nf p - t r e e t h i s a l g o r i t h ms t i l lu s et h es t r a t e g yo fd y n a m i ca d j u s t i n gs u p p o r tt h r e s h o l d ，i tm a k e s g u a r a n t e eo nt e c h n o l o g yo fp r o d u c i n gn m o s tf r e q u e n ti t e ms e t s f i n a l l y , w ei n p u tt h ed i f f e r e n tn u m b e rno ff r e q u e n ti t e ms e t so nt h es a m e t e x td a t a b a s e ，a n dc o m p a r et h en e wa l g o r i t h mw i t hi n t v m a t r i x t h er e s u l t ss h o w t h a tt h en e wa l g o r i t h m st i m ea n ds p a c eu s i n gq u o t i e t ya r ei m p r o v e d ，b e c a u s e a d o p ta m e l i o r a t i v ef p t r e et os t r u c t u r el o c a lc o f i t r e e ，a l o n gw i t ho p t i m i z e d d a t as t r u c t u r e k e yw o r d s ：d a t a m i n i n g ，t e x td a t am i n i n g ，t e x ta s s o c i a t i o na n a l y s i s ，nm o s t f r e q u e n ti t e ms e t s ，f p - t r e e ，c o f i t r e e i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：盏：塑垫 日期： 论文作者签名：翌逭：翌全! 日期：硼鼍。芏、| 9 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为：目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：滋王i 习；帮枫日期：塑星：! 堡 导师繇墨垒乙嘞 ，勘。f 一2 太原理：l ：大学硕+ 研究生学位论文 第一章绪论 随着电脑的普及与网络技术的发展，电子化文本文档的规模急剧增长，这些文档包 括研究报告、学术论文、在线文献库、e m a i l 、w e b 页面、公司内部公告、会议纪要等。 它们包含了大量的信息，是重要的知识源。但是很多情况下，由于文档的数量非常庞大、 缺乏组织整理并且格式多种多样，因而不能充分利用。人们迫切需要研究出方便有效的 工具去从大规模文本信息资源中提取符合要求的简洁、精练、可理解的知识，文本挖掘 就是为解决这个问题而产生的研究方向。它致力于从文本数据中发现新的事实和知识， 帮助我们在文本的“大山”中探测并采掘有价值的“金矿”。 1 1 研究背景 文本挖掘必须从数据挖掘谈起。数据挖掘，又称为数据采掘、数据开采，相近的 术语有k d d ( 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 ，数据库知识发现) 、数据分析、数据融 合( d a t af u s i o n ) 等。根据w j f r a w l e y 和gp s h a p i r o 等人的定义，数据挖掘是指从 大型数据库的数据中提取人们感兴趣的知识，而这些知识是隐含的、事先未知的、潜在 的有用信息。 从广义的角度来讲，数据挖掘意味着在一些事实或观察数据的集合中寻找模式的决 策支持过程。因而，数据挖掘的对象不仅是数据库，还可以是任何组织在一起的数据集 合，如w w w 信息资源等。目前数据挖掘工具能处理数值型的结构化数据，而文本、 图形、数学公式、图像或w w w 信息资源等半结构、无结构的数据形式将是数据挖掘 的挑战之一。文本挖掘作为数掘挖掘的一个新的领域应运而生。 文本挖掘处理的是非结构化的文本信息，它的主要任务是分析文本的内容特征，发 现文本数据库中概念、文本之间的相互关系和相互作用，为用户提供相关知识和信息。 因此，文本挖掘和数据库挖掘在目标上具有相似性，在技术实现上具有一定的差异。 关联规则挖掘是数据挖掘领域重要的挖掘技利引，与之类似，将非结构化的文本内 容转化成结构化的特征向量形式后，也可以在大规模文本集中发现基于特征词的频繁模 式或关联规则。然而，由于文本集的维数较高，传统的关联规则挖掘算法应用于文本数 据还存在一些不足。 太原瑷一l ：大学硕士研究生学位论文 1 。2 文本挖掘的主要应用 随着文本型信息的迅速增加，特剐是互联网的发展，文本信息已经成为一种重要的 知识来源。由于文本信息存储量大、变化快、从中获取知识十分困难，因此，文本挖掘 逐渐成为一个研究热点，并在多个领域广泛应用。目前文本挖掘处理主要集中于信息自 动导航、可视化信息检索、信息提取、信息分类、文本聚类等方面【3 1 。 文本挖掘可以给政府部门的同常工作带来便利，如帮助对于政府部门在大量的公文 信息中寻找相关文件和群众的反响，提高政府机关的效率。 文本挖掘可以给企业办公带来许多便利。例如，企业收集和存储的文本信怠 受多， 既包括大量的电予邮件、企业内部的备忘录和周期总结等，也包括关子竞争对手的报纸 和新闻、技术报告和专利资料等，利用文本挖掘技术可以使得人们能够更加方便地从海 量文本中发现隐含的知识，为企业的战略决策提供竞争情报支持，从而能够提高海量非 结构化信息源的利用价值。 文本挖掘也可以用于网络信息收集。互联网是一种重要的情报来源，利用文本挖掘 技术可以大大降低对这类信息源的收集和处理的时间，提高收集的准确率，增强情报分 析的深度，提高获取竞争情报的效率。同时，利用文本挖掘技术既可以提供网络的个性 化服务能力，屏蔽无关信息，也可以帮助企业在网上挖掘市场信息，寻求市场变动的规 律l 戤。 人们已经开发出许多基于文本挖掘技术的实用软件，如基于用户兴趣的文本过滤 器、基于语义和统计相结合的文本摘要系统、基于各种机器学习算法的文本分类系统、 可视化的中文文本挖掘系统等。这些软件或使用某种文本挖掘技术，或综合使用多种文 本挖掘技术，其中一些作为核心功能部件被集成到其他类型的应用软件中，成为职能搜 索引擎、网络信息智能过滤系统、知识管理系统、电子商务应用系统、电子政务应用系 统、办公自动化系统和竞争情报系统等软件系统的一部分。 但是，文本挖掘技术现有的水平与理想的目标还存在差距。 影响文本挖掘发展的主要原因如下【3 】： f i 文本数量巨大，结构不统一，动态变化，这导致从中获取知识院较困难。 ( 2 ) 基于语法、逻辑和统计的传统自然语言理解理沦、方法与技术虽然在语言表层 和浅层进行了大量的研究，但并未在这一关键问题上取得实质性的进展。同时，自然语 言理解理论在语言的深层处理方面也没有取得根本性的突破，这使得基于自然语言处理 的文本处理的准确度还不够高，使得文本挖掘的效果还不够理想。 2 太原理1 ：大学硕+ 研究生学位论文 然而，这些因素并不影响文本挖掘在多个领域的成功应用。 1 3 国内外研究现状 文本挖掘主要处理半结构化、无结构化和字符型数据。它将数据挖掘技术与信息检 索技术相结合，开扩了数据挖掘新的应用领域。其特点是能够更加有效地对文本数据( 例 如w e b 页面) 进行分析，从而弥补信息检索技术的缺陷与不足。 国外已经有了一定数量的文本挖掘工具f 4 】，并且出现了很多融合文本挖掘思想和技 术的应用。s e m i o 公司研发的s e m i o m a d 工具，可以提供自动的文本处理；i b m 公司出 品的智能化文本挖掘器( i n t e l l i g e n tm i n e rf o rt e x t ) ，适合大型软件公司的开发人员使用； b r i g h t w a r e 公司的产品b r i g h t w i n g e ，是一个自动的电子邮件阅读和解释系统。国内进行 文本挖掘的研究较国外晚，但是在国内对于中文文本挖掘取得了最初成果，如中科院计 算机语言信息工程研究中心研究的内容是汉语分词、自然语言接口、句法分析、语义分 析、音字转换、自动分词；清华大学电子工程系的丁晓青、吴佑寿研究的内容是手写汉 字识别( 动态匹配) 、汉字识别多分类器集成( 综合识别法) 、名片自动录入系统的实现 笙f 3 】 寸o 目前，对文本挖掘的理论方法和技术实现国内外都在进行深入地研究和探讨。研究 表明文本挖掘技术可以应用于【5 】：基于内容检索：由于仅用几个关键词难以充分描述 具有丰富内涵的信息，而且关键词的选取也有很大的主观性，故文本挖掘技术采用区别 于传统检索手段的基于内容的检索技术。尽管目前基于内容的检索技术还很初级，只能 利用一些相对简单的特征来进行检索，但随着研究的深入，必将可以从文本信息中抽取 一些更为详细的、经过特殊加工的特征信息，大大提高检索的全面性和准确性。信息 智能代理：主要为在分布式信息网络环境下的信息的查询服务。信息智能代理使用户可 以不知道所要检索信息的具体形式，存储于何处、何种介质中，只要用户提出查找要求， 文本挖掘技术会自动地把各种信息源中各种形式的相关信息检索出来，供用户使用，使 用户可以立即获得较为满意的检索结果。信息过滤：根据用户需要，通过对多个不同 信息集之间的比较，进行信息过滤，产生适量的、合乎用户需求的信息。文本信息文 摘：用包括题目和具有代表性的关键词( 字) ，进行抽取、计算和表达，自动选择重要 的句子，产生文本信息摘要。信息表现：信息挖掘技术关心的是信息的方方面面，力 求从多角度表现信息的本质和特征。文本挖掘技术能动态地、实时在线地表现信息的相 关属性，使用户及时地发现信息，更新信息并且发现信息的演变方向。 3 太原瑗 ：人学硕士研究生学侮论文 1 4 论文的研究内容及组织 1 4 1 论文的研究内容 本沦文研究文本关联规则挖掘算法，主要对挖掘n 个最频繁项集的算法作了研究与 改进，即基于改进的f p t r e e 挖掘n 个最频繁项集。本文首先对当前常见的几种关联规 则以及应用于文本的关联规则挖掘算法进行了比较详细的介绍，分析了这些算法的不足 之处；然后提出了一个基于改进的f p t r e e 挖掘n 个最频繁项目集的算法。随后的实验 结果证明，改进后的算法在挖掘高维稀疏的文本数据集时具有优势。 1 4 。2 论文的组织 论文其余部分按以下方式组织： 第二章：首先介绍了数据挖搦的相关内容，包括数据挖掘和知识发现的关系以及数 据挖掘的概念；然后叙述了弓l 发数据挖掘的挑战和数据挖掘所面向的四个对象；接着对 数据挖握的主要任务和常用黪方法作了介绍；最后激明了数据挖掘的应用领域及发展的 趋势。 第三章：对相关技术做了介绍。首先是文本挖掘的概念，一般过程及其特点和分类， 还有文本挖掘的主要应用以及对信息检索的影响。接着对文本关联分析作了介绍，包括 关联规则的基本概念及其分类，并且对关联规则挖掘算法按照其搜索和计数方式进行了 分类，描述了经典的关联规则挖掘算法a p r i o r i 和f p g r o w t h ，以及基于关键字的文本关 联分析。最后，介绍了文本预处理，由于文本关联分析是要在经过预处理的文本集的基 础上来进行，所以对文本预处理的介绍也是必要的。 第四章：叙述了频繁项目集及其相关摄念，然后介绍了n a p r i 蕊算法和i n t v m a t r i x 算法，并盈分析了它们的不足之处，最蜃详细阐述了基于改进的f p - t r e e 挖掘n 个最频 繁项集的算法。 第五章：在本章中首先对f p t r e e 的数据结构进行了分析，找寤最优的存储方式并 应用于本实验中，然后通过实验将新的算法与西前较优的i n t v m a t r i x 算法进行了性能对 比分析。 第六章：总结全文并展望未来进步的研究方向。 4 太原理工大学硕上研究生学位论文 第二章数据挖掘背景知识研究 数据收集和数据存储技术的快速进步使得各组织机构可以积累海量数据。然而，提 取有用的信息已经成为巨大的挑战。一般的，由于数据量太大，无法使用传统的数据分 析工具和技术处理它们。有时，即使数据集相对较小，由于数据本身的非传统特点，也 不能使用传统的方法处理。在另外一些情况下，需要回答的问题不能使用已有的数据分 析技术来解决。这样，就需要开发新的方法来解决这些问题。 数据挖掘是一种信息处理技术，它将传统的数据分析方法与处理大量数据的复杂算 法相结合。数据挖掘为探查和分析新的数据类型以及用新方法分析旧有数据类型提供了 令人兴奋的机会。 2 1 数据挖掘与知识发现 数据挖掘是在大型数据存储中，自动地发现有用信息的过程。数据挖掘技术用来探 查大型数据库，发现先前未知的有用模式。数据挖掘还具有预测未来观测结果的能力， 例如，预测一位新的顾客是否会在一家百货公司消费5 0 0 元以上。 并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查找个别 的记录，或通过因特网的搜索引擎查找特定的w e b 页面等就是信息检索( i n f o r m a t i o n r e t r i e v a l ) 领域的任务。虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构， 但是它们主要依赖传统的计算机科学技术和数据的明显特征来创建索引结构，从而有效 地组织和榆索信息。尽管如此，数据挖掘技术也已用来增强信息检索系统的能力1 6 】。 数据挖掘是数据库中知识发现( 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 ) 过程不可缺 少的一部分，而知识发现是将未加工的数据转换为有用信息的整个过程，如图2 1 所示。 该过程包括一系列转换步骤，从数据的预处理到数据挖掘结果的后处理i lj 。 5 _ 太原理工大学硕士研究生学位论文 输入数据 图2 1 数据席中知识发现的过程 f i g u r e2 - 1t h ep r o c e s so f k d d 佑息 输入数据可以以各种形式存储( 平展文件、电子数据表或关系表) ，并且可以驻留 在集中的数据存储库中，或分布在多个站点上。数据预处理( p r e p r o c e s s i n g ) 的目的是 将未加工的输入数据转换成适合分析的形式。数据预处理设计的步骤包括融会来自多个 数据源的数据，清洗数据以消除噪声和重复的观测值，选择与当前数据挖掘任务相关的 纪录和特征。由于收集和存储数据的方式可能有许多种，数据预处理可能是整个知识发 现过程最费力、最耗时的步骤。后处理可以确保只将那些有效的和有用的结果集成到决 策支持系统中。后处理的一个例子是可视化，它使得数据分析者可以从各种不同的视角 攘查数据和数据挖掘结果。在后处理阶段，还能使用统计度量或假设检验，删除虚假的 数据挖掘结果f 7 1 。 2 2 引发数据挖掘的挑战 正如前砸所提到的，当砸临瓶的数据集提出的挑战时，传统的数据分析技术常常遇 到实际l 壅l 难。下两一些特定的挑战【8 】，弓| 起了人们对数据挖擒的研究的渴望。 可伸缩。由于数据产生和收集技术的进步，数吉字节、数太字节甚至数拍字节的数 据集越来越簧遍。如果数据挖掘算法要处理这些海量数据囊，则算法必须是可伸缩的 ( s c a l a b l e ) 。谗多数据挖掘算法使用特殊的搜索策略处理指数性搜索问题。霹 审缩可能 还需要实现叛的数据结构，以有效访阚个别记录。例如，当要处理的数据不能放进内存 时，可能需要甚 内存算法。使用抽样技术或开发并行和分- 匆雾法也可竣提高可 孛缩程度。 高维性。现在，常常遇到其有数以百计或数以千诗属性l 窍数据集，谣不是数十年前 常觅的只具有少量属性的数据集。在生物信怠学领域，微阵到技术的进步已经产生了涉 及数干特征的基因表达数据。具有时闻或空间分量的数掇集泡趋向于具有很高的维度。 例妇，考虑包含不同地区的温度测量的数据集。如果温度在一个相当长的时阀周期内蓬 复地测量，则维度( 特征数) 的增长正比于测量的次数。为觚维数据开发的传统的数据 6 太原理：f ：人学硕十研究生学位论文 分析技术通常不能很好地处理这样的高维数据。此外，对于某些数据分析算法，随着维 度( 特征数) 的增加，计算复杂性迅速增加。 异种数据和复杂数据。通常，传统的数据分析方法只处理包含相同类型属性的数据 集，或者是连续的，或者是分类的。随着数据挖掘在商务、科学、医学和其他领域的作 用越来越大，越来越需要能够处理异种属性的技术。近年来，已经出现了更复杂的数据 对象。这些非传统的数据类型的例子包含有半结构化文本和超链接的w e b 页面集、具 有序列和三维结构的d n a 数据、包含地球表面不同位置上的时间序列测量值( 温度、 气压等) 的气象数据。为挖掘这种复杂对象而开发的技术应当考虑数据中的联系，如时 间和空间的自相关性、图的连通性、半结构化文本和x m l 文档中元素之间的父子联系。 数据的所有权与分布。有时，需要分析的数据并非存放在一个站点，或归属一个单 位，而是地理上分布在属于多个机构的资源中。这就需要开发分布式数据挖掘技术。分 布式数据挖掘算法面临的主要挑战包括：( 1 ) 如何降低执行分布式计算所需的通信量? ( 2 ) 如何有效地统一从多个资源得到的数据挖掘结果? ( 3 ) 如何处理数据安全性问题? 非传统的分析。传统的统计方法基于一种假设一检验模式。换句话说，提出一种假 设坼设计实验来收集数据，然后针对假设分析数据。但是，这一过程劳力费神。当前的 数据分析任务常常需要产生和评估数以千计的假设，因此希望自动地产生和评估假设导 致了一些数据挖掘技术的开发。此外，数据挖掘所分析的数据集通常不是精心设计的实 验的结果，并且它们通常代表数据的时机性样本( o p p o r t u n i s t i cs a m p l e ) ，而不是随机样 本( r a n d o ms a m p l e ) 。而且，这些数据集常常涉及非传统的数据类型和数据分布。 2 3 数据挖掘的对象、任务以及方法 2 3 1 数据挖掘的对象 数据挖掘可以针对任何类型的数据库来进行，既包括传统的关系数据库，也包括非 数据库组织的文本数据源、w e b 数掘源以及复杂的多媒体数据源等【3 】【9 1 。 ( 1 ) 关系数据库 关系数据库因为具有坚实的数据基础、统一的组织结构、完整的规范化理论、体 化的查询语言等优点，成为当前数据挖掘最重要、最流行，也是信息最丰富的数据源， 并且也是人们对数据挖掘研究的主要形式之一。 ( 2 ) 数据仓库 数据仓库是数据库技术发展的高级阶段，它是面向主题的、集成的、内容相对稳定 7 太原疆i ：大学硕士研究生学位论文 的、隧时潮变化的数据集合，可以用来支持管理决策的制定过程。数据仓库系统允许将 各种应用系统、多个数据库集成在一起，为统一的历史数据分橱提供坚实的平台。 数据挖掘需要有“纯净弦的数据和良好的数据组织，数据的质量直接影响到数据挖 掘的效果，而数据仓库的特点恰恰最符合数据挖掘的要求，它从各类数据源中抓取数据， 经过清洗、集成、选择、转换等处理，为数据挖掘所需要的高质量数据提供了保证。可 以说，数据挖掘为数据仓库提供了有效的分析处理手段，数据仓库为数据挖掘准备了良 好的数据源。因此，随着数据仓库与数据挖掘的协调发展，数据仓库必然成为数据挖掘 的最佳环境。 ( 3 ) 文本数据库 文本数据库所记载的内容均为文字，这些文字并不是篱单的关键谲，藤是长句子、 段落甚至全文，文本数据库多数为非结构化的，也有些是半结构化的，如h t m l 、e - m a i l 等。w e b 网页也是文本信息，把众多的w e b 网页组成数据库就是最大的文本数据库。 如果文本数据具有良好的结构，可以使用关系数据库来实现。 ( 4 ) 复杂类型数据库 复杂类型的数据库是指非单纯文本的数据库或能够表示动态的序列数据的数据库， 主要有如下几类【1 0 1 。 1 ) 空闻数据库。主要指存储空间信息的数据库，其中数据可熊以光栅格式提供， 也可熊用矢量图型数据表示。例如，地理信息数据库、卫星图像数据库、城市地下管道、 下求道及各类地下建筑分布数据库等。对空闻数据库的挖掘可以为城市规划、生态规划、 道路修建提供决策支持。 2 1 时序数据库。主要用于存放与时问相关的数据，它可用束反映随时问变化的即 时数据或不同时间发生的不同事件。例如，连续的存放即时的股票交易信息、卫星轨道 信息等。对时序数据的挖掘可以发现事件的发展趋势、事物的演变过程和隐藏特征，这 些信息将对事件的计划、决策和预警是非常有用的。 3 ) 多媒体数据库。用于存放图像、声音和视频信息的数据库。由于多媒体技术的 发展，以及相关研究( 如可视化债息检索、盘拟现实技术) 豹成就，多媒体数据痒也逐 渐普及，并应沼于许多重要研究领域。晷前，多媒体数据的挖掘主要放在对鹰像数据的 检索与匹配上，随着研究的深入将会拓展到对声音、视频信息豹挖掘处理。 2 。3 2 数据挖掘的任务 数据挖掘的任务一般分为以下两大类哆 8 太原理i ：大学硕士研究生学位论文 预测任务：这些任务的目标是根据其他属性的值，预测特定属性的值。被预测的属 性一般称目标变量( t a r g e tv a r i a b l e ) 或因变量( d e p e n d e n tv a r i a b l e ) ，而用来做预测的属 性称之为说明变量( e x p l a n a t o r yv a r i a b l e ) 或白变量( i n d e p e n d e n t v a r i a b l e ) 。 描述任务：这里，目标是导出概括数据中潜在联系的模式( 相关、趋势、聚类、轨 迹和异常) 。本质上，描述性数据挖掘任务通常是探查性的，并且常常需要后处理技术 验证和解释结果。 我们介绍四种主要的数据挖掘任务：预测建模、关联分析、聚类分析和异常检测 7 1 1 1 i 】 o ( 1 ) 预测建模( p r e d i c t i v em o d e l i n g ) ，涉及以说明变量函数的方式为目标变量建立模 型。有两类预测建模任务：分类( c l a s s i f i c a t i o n ) ，用于预测离散的目标变量；回归 ( r e g r e s s i o n ) ，用于预测连续的目标变量。例如，预测一个w 曲用户是否会在网上书店 买书是分类任务，因为该目标变量是二值的。另一方面，预测某股票的未来价格是回归 任务，因为价格具有连续值属性。两项任务目标都是训练一个模型，使目标变量预测值 与实际值之间的误差达到最小。预测建模可以用来确定顾客对产品促销活动的反映，预 测地球生态系统的扰动，或根据检查结果判断病人是否患有某种特定的疾病。 ( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) ，用来发现描述数据中强关联特征的模式。所发 现的模式通常用蕴涵规则或特征子集的形式表示。由于搜索空间是指数规模的，关联分 析的目标就是以有效的方式提取最有趣的模式。它的应用包括找出具有相关功能的基因 组、识别一起访问的w e b 页面，理解地球气候系统不同元素之间的联系等。比如，通 过在一家杂货店收银台收集的销售数据，关联规则可以用来发现顾客频繁地同时购买的 商品，我们可能发现规则 尿布 - ， 牛奶 。该规则暗示购买尿布的顾客多半会购买牛奶。 这种类型的规则可以用来发现相关商品中可能的交叉销售的机会。 ( 3 ) 聚类分析( c l u s t e ra n a l y s i s ) ，旨在发现紧密相关的观测值组群，使得与属于不 同簇的观测值相比，属于同一簇的观测值之间尽可能类似。聚类可用来对相关的顾客分 组、找出显著影响地球气候的海洋区域以及压缩数据等。 ( 4 ) 异常检测( a n o m a l yd e t e c t i o n ) 的任务是识别其特征显著不同于其他数据的观测 值。这样的观测值称为异常点( a n o m a l y ) 或离群点( o u t l i e r ) 。异常检测算法的目标是 发现真正的异常点，而避免错误地将正常的对象标注为异常点。换言之，一个好的异常 检测器必须具有高检测率和低误报率。异常检测的应用包括检测欺诈、网络攻击、疾病 的不寻常模式和生态系统扰动等。 9 太原理。l ：人学硕士研究生学位论文 2 3 3 数据挖撬的方法 当今先进的数据挖掘工其都提供多种可供选择的数据挖掘算法。这是因为一种算法 不可能完成所有不同类型的数据挖掘任务，没有种数据挖掘的方法可以应付所有的要 求。对于某一问题，数据本身的特性会影响用户所选用的工具。所以用户可能会需要用 到许多不同的工具以及技术，从数据中找到最佳的模式。这犀简要介绍当今最流行的几 种数掘挖掘方法，包括神经网络、决策树和遗传算法等。 ( 1 _ ) 神经网络方法【1 2 1 。神经网络出于本身良好的鲁棒性、自组织自适应性、并行处 理、分布存储和高度容错等特性非常适合解决数据挖掘战闻题，因此近年来越来越受到 人们豹关注。典型豹神经鼹络模型主要分3 大类：以感知机、b p 反向传播模型、溺数 型网络为代表的，用予分类、预测和模式识别酶前馈式神经网络模型；以h o p f i e l d 的离 散模型和连续模型为代表的，用子聚类的自组织映射方法。神经网络方法的缺点是“黑 箱 性，入们难以理解网络的学习和决策过程。 ( 2 ) 遗传算法阮引。遗传算法是一种基于生物自然选择与遗传机理的随机搜索算 法，是一种仿生全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性 质使得它在数据挖掘中被加以应用。 s u n i l 已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对鼹个飞机 失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法 之一。遗传算法的应用还体现在与神经掇络、凝糙集等技术的结合上。如利用遗传算法 优化神经网络结构，在不增加错误率的前提下，删除多余的链接和隐层单元；用遗传算 法和b p 算法结合训练神经网络，然后从网络提取规燹| j 等。但遗传算法的算法较复杂， 收敛于局部极小的较早收敛问题尚未解决。 ( 3 ) 决策树方法f 。决策树是一种常用于预测模型的算法，它通过将大量数据有目 的的分类，从中找到一些有价值的、潜在的信息。它的主要优点是描述简单，分类速度 快，特别适合大规模的数据处理。最有影响和最早的决策树方法是由q u i n l a n 提出的著 名的基于信息熵的i d 3 算法。它的主要问题是：1 d 3 是j 暑递增学习算法；i d 3 决策树是 单变量决策树，复杂概念的表达鼹难；同性阍的相互关系强调不够；抗嗓性差。针对上 述闯题，嵩现了许多较好的改进算法，如s c h l i m m e r 和f i s h e r 设计了i d 4 递增式学习算 法。 ( 4 ) 粗糙集方法 3 1 1 秘j 。糯糙集理论是一种研究不精确、不确定知识的数学工具。粗 糙集方法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易 lo 太原理1 i 大学硕士研究生学位论文 于操作。粗糙集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系 统和新发展起来的数据仓库管理系统为粗糙集的数据挖掘奠定了坚实的基础。但粗糙集 的数学基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在 的。因此连续属性的离散化是制约粗糙集理论实用化的难点。现在国际上已经研制出来 了一些基于粗糙集的工具应用软件，如加拿大r e g i n a 大学开发的k d d r ；美国k a n s a s 大学开发的l e r s 等。 ( 5 ) 统计分析方法。数据库字段项之间存在两种关系：函数关系( 能用函数公式 表示的确定性关系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对 它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行 常用统计( 求大量数据中的最大值、最小值、总合、平均值等) 、回归分析( 用回归方 程来表示变量间的数量关系) 、相关分析( 用相关系数来度量变量间的相关程度) 、差异 分析( 从样本统计量的值得出差异来确定总体参数之间是否存在差异) 等。 ( 6 ) 模糊集方法【l 】。即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模 糊模式识别和模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用 隶属度来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础 上，提出了定性定量不确定性转换模型一云模型，并形成了云理论。 ( 7 ) 关联分析【l5 1 。关联分析可以分为两种，即关联规则和时序分析。关联规n i l 在 当前记录的各个特征间寻找内在的联系，如“包含特征a 和d 的9 8 的记录中必定包 含特征b 和e ”；时序分析即在历史数据中寻找具有时间上相关的记录间的规律性。如 “如果a 公司的股票上涨1 5 ，而b 公司的股票连续2 天不下跌，则c 公司的股票在 第3 天必定下跌。” 实现关联分析的技术主要是统计学中的置信度和支持度分析。支持度和置信度是描 述连接分析的两个重要概念，前者用于衡量连接分析在整个数据集中的统计重要性，后 者用于衡量连接分析的可信程度。般来说，只有支持度和置信度均较高的关联规则才 可能是用户感兴趣的、有用的连接规则。 ( 8 ) 覆盖正例排斥反例方法i l6 。它是利用覆盖所有正例、排斥所有反例的思想来寻 找规则。首先在正例集合中任选一个中子到反例集合中逐个比较。与字段取值构成的选 择子相容则舍去，相反则保留。按此思想循环所有正例种子，将得到j 下例的规则( 选择 子的合取式) 。比较典型的算法有m i c h a l s k i 的a q l l 方法、洪家荣改进的a q l 5 方法以 及他的a e 5 方法。 太原璞l ：入学硕+ 研究生学位论文 2 4 数据挖掘的应用领域及发展趋势 2 4 1 数据挖掘的应用领域 数据挖掘技术的应用领域十分广泛，在政府管理决策、商业经营、科学研究和工业 企业决策支持等各个领域都可以应用数据挖掘技术。以下简单介绍目前发展的比较活跃 的数据挖掘应用领域： ( 1 ) 科学应用( 1 】。在科学研究( 特别是实验科学和计算科学的研究) 中，需要分析 各种大量的实验或观测数据，如双测卫星、遥感器、d n a 分子技术等，传统的数据分 析工具效率较低甚至无能为力，嚣此必须有强大的智能型自动数据分析工具菇行。 ( 2 ) 市场销售【耀。市场销售是数据挖掘技术应用最早也是最重要的领域。主要功能 是：市场定位、消费者分析、预测销售趋势、优化营销策略、分析库存需求、识别顾客 的购买行为模式、协助货架布置、制定促销活动时问、促销商品组合以及了解畅销和滞 销商品状况等商业活动。 ( 3 ) 金融1 1 1 。典型的金融分析领域有投资评估和股票交易市场预测，分析方法一般 采用模型预测法( 如神经网络或统计回归技术) 。这方面的系统有f i d e l i t ys t o c k s e l e c t o r ， 任务是使用神经网络模型选择投资；l b sc a p i t a lm a n a g e m e n t 使用了专家系统、神经网 络和基因算法技术辅助管理多达6 亿美元的有价证券。 ( 令欺诈甄别l 嘲。分析银行或保险客户的