（管理科学与工程专业论文）基于聚类的增量数据挖掘研究.pdf

中文摘要摘要聚类分析向来是数据挖掘研究的重要方面，基于聚类的各种数据挖掘算法的研究历来也是研究重点。但是，目前大多数的聚类分析算法只是针对于静态数据集的操作，对于动态数据集却只能采取对整个数据集重新进行聚类的方式，因此随着数据量的不断增大以及对数据集实时数据挖掘的需求不断加大，增量式数据挖掘技术正越来越引人关注。基于聚类的增量式数掘挖掘继承了已有聚类的执行成果，通过对新增数据的逐个或者批量考查，可在很大程度上避免大量的重复计算，减少了计算量，节省了系统开支，提高了效率，尤其数据量越大时，增量式的数据挖掘技术就越能体现出其优越性，也更能为有数据挖掘需求的用户提供及时、快捷、有价值的信息内容。本文首先主要总结、探讨了关于数据挖掘以及聚类算法等方面取得的已有主要研究成果，并详细阐释了基于密度的聚类算法d b s c a n 的主要思想、算法流程，并给出了实例以演示算法。在此基础上，提出了基于d b s c a n 的增量式聚类算法i n c r e m e n t a l d b s c a n ，由于i n c r e m e n t a l d b s c a n 采用了逐个考察新增数据的处理方式，为了达到更好的运行效率，进一步提出了i n c r e m e n t a l d b s c a n 的批量处理算法。最后，通过实验验证了d b s c a n 与i n c r e m e n t a ld b s c a n 在聚类效果上的一致性，以及i n c r e m e n t a ld b s c a n 在大数据量环境下更加卓越的性能。关键词：聚类；增量式数据挖掘；密度；d b s c a n 算法英文摘要r e s e a r c ho fi n c r e m e n t a ld a t am i n i n gb a s e do nc l u s t e r i n ga b s t r a c tc l u s t e r i n ga n a l y s i si sa l w a y sm a i na s p e c to fd m ( d a t am i n i n g ) r e s e a r c h ，a n dt h er e s e a r c ho fs e v e r a ld ma r i t h m e t i cb a s e do nc l u s t e r i n gi sa l s oi nf o c u s b u ta tp r e s e n tm o s to ft h ec l u s t e r i n ga r i t h m e t i cs t y l e sa r ea p p l i e df o rs t a t i cd a t as e t s ，i no t h e rh a n d ，a sf o rt h ed y n a m i cd a t as e t s ，t h eo n l yw a yi st or e d ot h ep r o c e s so fc l u s t e r i n go nt h ew h o md a t as e t ，s oa st h eq u a n t i t yo fd a t as e tb e c o m e sm o r ea n dm o r eh u g e ，a n dd e m a n d i n gf o rd mi nt i m e t h ei n c r e m e n t a ld mb e c o m em o r ea n dm o r ea t t r a c t i v e 髓ei n e r e m e n t a ld mb a s e do i lc l u s t e r i n gi n h e r i t st h ef o r m e rd u s t e r i n gr e s u l t a n dt h e nc h e c kt h en e wa d d e dd a t ai t e mo n eb yo n e ，i nt h i sw a y , ag r e a ta n a o u n to fc o m p u t a t i o nc a l lb ea v o i d e d s ot h ec o m p u t e rs y s t e mr e s o u r c e sc a r tb es a v e dt o o e s p e c i a l l yw h e nt h ed a t as e ti su n e x p e c t e d l yh u g c ，t h ei n e r e m e n t a ld mc a ns h o wi t se x c e l l e n c e ，s u c ha st h ei n s t a n ta n dv a l u a b l ei n f o r m a t i o nr o o t e di nd mp r o c e s sf o ru s e r s f i r s t l y , t h i sp a p e rs l i m 8u pt h em a i nr e s e a r c ha c h i e v e m e n to fd ma n dc l u s t e r i n ga n a l y s i s ，a n dg i v e st h ed e t a i l e da r i t h m e t i ct h e o r yo fd b s c a nw h i c hi sb a s e do nf u z z y a n dt h e ng i v e st h ec o r r e s p o n di n c r e m e n t a lc l u s t e r i n ga r i t h m e t i c ：i n c r e m e n t a ld b s c a no na c c o u n to ft h ep r o c e s s i n gm a n n e ro fc h e c kt h ed a t ai t e mo n eb yo n e ，i tm t r c h d u c et h eb a t c ha r i t h m e t i ci no r d e rt om o s t l yi m p r o v et h ee f f i c i e n c y a “t 。t h ed b s c a na n di n c r e m e n t a ld b s c a na r i t h m e t i ca l ea p p r o v e da c c o r d a n tw i t he a c ho t h e r , b e s i d e s ，t h ei n c r e m e n t a ld b s c a ni sm u c hm o l ee f f i c i e n c yw i t hg r e a td a t as e t k e yw o r d s c l u s t e r i n g ti n c r e m e n t a ld a t am i n i n g ：d e n s i t y ld b s c a n大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博= l z 硕士学位论文：基王丞羞的擅量麴握控坦班究：。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律责任由本人承担。论文作者签名：荩孓a 帕7 年立月加日学位论文版权使用授权书本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。保密口，在年解密后适用本授权书。本学位论文属于：保密口不保密i ( 请在以上方框内打“”)论文作一：氍喝铷躲移勿e t 期：州7 年乡月日基丁二聚类的增量数据挖掘研究第1 章绪论1 1 引言数据挖掘历来是数据仓库研究中的热点问题。数据挖掘的目标就是从海量数据中抽取潜在的、有价值的模式和知识。通过数据挖掘所获得的这些模式和知识在各行各业的决策活动中发挥着日益重要的作用。可以说，数据挖掘是数据仓库的最终目的。聚类分析是数据挖掘的重要手段，它按照人为定义的某些关注点把各事物对象聚集成类，形成若干个相似性很好的类。但目前业已广泛应用的聚类算法，往往只能适用于静态数据集的聚类，对动态数据集，新增数据后则会造成前期聚类结果可靠性的丧失，而如果重新进行聚类必然会造成效率低下和计算资源的浪费。因此，在聚类分析中引入了增量式数据挖掘的概念，可以解决上述问题，对于大型数据库或数据仓库的数据挖掘，增量式的数据挖掘是一个实用性很强的策略。简言之，增量式数据挖掘就是针对大数据集( 数据库或数据仓库) ，当数据递增的时候，增量地更新数据挖掘结果，而不是对每次更新后地整个数据集进行再挖掘。而聚类与数据挖掘之间是通过增量式聚类联系起来，达成统一，增量式聚类是利用己取得的聚类结果，对新发生的数据进行逐个或逐批次地进行聚类。运用聚类分析方法对动态数据库进行增量式的数据挖掘，是数据挖掘技术逐步走向深入的一个重要层次，也是数据仓库技术不断发展的结果。它是适应大数据集的发展趋势的。研究基于聚类分析方法的增量式数据挖掘中对于避免重复聚类造成的计算资源浪费，增强数据挖掘的时效性，提高数据挖掘效率等方面都具有十分重要的意义。本课题力求在数据挖掘中从聚类的研究分析上入手，通过对聚类的相关技术以及国内外研究现状进行认真的归纳总结，对能够适用于动态海量数据的增量式聚类方法进行研究。第1 章绪论1 2 增量式数据挖掘技术增量式挖掘技术，就是对于大数据集( 数据库或数据仓库等) ，当数据递增的时候，增量的更新数据挖掘结果，而不是对每次更新后的整个数据集进行挖掘。对于许多种类的大型数据库或数据仓库挖掘，增量数据挖掘是一个诱人的目标。典型地，一个数据仓库不是立即更新的，当对数据库进行插入和删除操作的时候，更新是按批模式定期的收集和应用到数据仓库中，那么，用数据挖掘算法从数据仓库推导出的所有模式被更新。这种更新必须能及时有效地完成，使得用户使用数据仓库的时候，数据是可靠的。由于数据集庞大，增量执行这些更新是吸引人的，这样就仅仅考虑原有类和一天中插入删除的对象，而不是对更新后的整个数据库或数据仓库进行聚类挖掘。本文中考虑的任务是基于密度的聚类，也就是说根据密度把数据库中的对象分组成有意义的子类。由于基于密度的特点，对象的插入删除操作仅影响该对象的邻居中的类，从而使得该技术较简单易行。1 3 国内外研究现状国际上第一次关于数据挖掘与知识发现的研讨会于1 9 8 9 年8 月在美国底特律召开，数据挖掘一词也是在这次会议上正式形成的。国际数据挖掘学术会议起初每两年召开一次，1 9 9 3 年后每年召开一次。在几次国际数据挖掘学术会议上讨论的问题有：( 1 ) 定性知识和定量知识的发现。( 2 ) 数据汇总。( 3 ) 知识发现方法。( 4 ) 数据依赖关系的发现和分析。( 5 ) 发现过程中知识的应用。( 6 ) 交互式的知识发现系统。( 7 ) 知识发现的应用。1 9 9 5 年，在加拿大召开了第一届知识发现和数据挖掘国际学术会议。由于数据库中的数据被形象地喻为矿床，因此数据挖掘一词很快流传开来。1 9 9 5 年以来，基于聚类的增量数据挖掘研究国外在数据挖掘知识发现方面的论文非常多，己形成了热门研究方向。1 9 9 7 年，亚太地区举行了第一届知识发现和数据挖掘国际会议( p a k d d ：p a c i f i c a s i ac o n f e r e n c eo nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) ，在欧洲也举办有类似的国际会t g p k d d ( e u r o p e a nc o n f e r e n c eo np r i n c i p l e so f 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 ) 。1 9 9 8 年，a c m ( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y ) 正式成立了有关k d d 的特别兴趣小组s i g k d d ( s p e c i a li n t e r e s tg r o u po nkk n o w l e d g ed i s c o v e r yi n d a t aa n d d a t a m i n i n g ) 。此外，数据库、人工智能、情报检索等领域的国际学术团体也将k d d 和数据挖掘作为研究讨论的热点问题【1 】。目前，有关数据挖掘讨论的问题主要集中在因特网应用和科学研究应用方面。在因特网应用方面包括数据挖掘在电子商务中的应用、w e b 挖掘、w e b 语义学、x m l与数据挖掘；科学研究主要集中于生物信息学中的数据挖掘应用。除了传统的研究方向如数据和知识表达、元数据、数据缩减和维数缩减、预处理和后处理技术、挖掘语言一大家最新关注的问题还包括己发现知识的管理和精炼、文本挖掘用于知识管理、数据挖掘中的安全和隐私保护等。随着国外知识发现的兴起，我国也很快跟上了国际步伐。计算机世界报技术专题版于1 9 9 5 年3 月发表了由中国电子设备系统工程公司研究所李德毅教授组织的k d d 专题；于t 9 9 5 盆e 4 月发表了由中国科学院史忠植研究员组织的“机器学习、神经网络”专题；于1 9 9 5 年1 2 月发表了由国防科技大学陈文伟教授组织的“机器发现和机器学习”专题，于1 9 9 9 年在北京召开的第三届p a k d d 国际学术会议，都对我国开展知识发现的研究起到了一定的推动作用2 ，3 1 。近几年，国内各计算机学术刊物也纷纷刊登有关知识发现和数据挖掘的论文，所涉及的研究领域集中于学习算法的研究和有关数据挖掘的理论研究。1 4 本文主要内容及研究工作国内外众多的学者已经对传统的各种聚类分析方法进行了深入广泛的研究，取得了丰硕的成果，但在对增量式聚类分析方面的研究还比较欠缺。本论文主要依据改进传统的基于密度的聚类算法d b s c a n 提出使之能够增量式地对新增数据聚类的算法思想，并通过实例模拟来验证算法的有效性和高效性。一3 -第1 章绪论增量式聚类挖掘技术是基于聚类挖掘的，它的基本思路是：使用聚类挖掘技术对原始数据集d 进行挖掘，得到一些类白，c 2 , ，g 新的数据集d 来到时，使用增量式聚类挖掘方法对d - 和( c l ，c z , ，g ) 进行处理，在处理的过程中，使两次聚类的效果迭加起来，形成最后的结果。增量式聚类挖掘技术的总体结构流程如图1 1 所示：图1 1 增量式聚类挖掘的总体结构流程f i g 。1 1t h ef l o wo f i n c r e m e n t a ld a t am i n i n gb a s e do nc l u s t e r i n g本文主要研究了数据挖掘中基于密度的聚类算法d b s c a n 以及其对应的增量式i n c r e m e n t a ld b s c a n 算法，并予以了实现、对比。主要包括：( 1 ) 数据挖掘技术涉及的多个方面的综述。诸如数据挖掘的概念、方法、技术，以及相关的一些应用等。( 2 ) 适用于数据挖掘的常用聚类算法的讨论与分析总结。这些常用的聚类算法包括传递闭包法、最大树法、c 一均值法、f c m 、基于网格的聚类算法等。( 3 ) 基于密度的典型聚类算法d b s c a n 及实例解析。( 4 ) 基于d b s c a n 聚类算法的增量形式：i n c r e m e n t a ld b s c a n 。( 5 ) 算法实验验证。包括d b s c a n 与i n c r e m e n t a ld b s c a n 对比及参数对聚类效果的影响两方面的验证。- 4 基于聚类的增量数据挖掘研究第2 章数据挖掘技术综述2 1 数据挖掘概述数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系，从而促进信息的传递。现在数据挖掘技术在商业应用中已经可以马上投入使用，因为对这种技术进行支持的三种基础技术已经发展成熟，他们是：( 1 ) 海量数据搜集。( 2 ) 强大的多处理器计算机。( 3 ) 数据挖掘算法。商业数据库现在正在以一个空前的速度增长，并且数据仓库正在广泛地应用于各种行业；对计算机硬件性能越来越高的要求，也可以用现在已经成熟的并行多处理机的技术来满足；另外数据挖掘算法经过了这l o 多年的发展也已经成为一种成熟，稳定，且易于理解和操作的技术。在海量的数据中，是否隐藏着有价值的东西? 如何充分有效地使用这些数据，并从中发现内在的关系及其可以说明的问题呢? 数据挖掘技术可以解决这个问题。数据挖掘( d a t a m i n i n g ) 又称知识发现( k d d ，k n o w l e d g e d i s c o v e r y i n d a t a b a s e ) ，从广义来说，就是从巨大的数据库中提炼我们感兴趣的东西，或者提炼出我们不易观察或断言的关系，最后给出一个有用的并可以解释的结论；简单地说就是在数据中发现模式、知识或数据间的关系h 5 1 。在新的数据库研究方向上，数据挖掘和数据库已经走得很近。比如数据仓库技术可以看成是数据挖掘的一个预处理的过程，移动数据库、互联网数据库、海量数据库、并行数据库、空间数据库等新型数据库的挖掘方法是数据挖掘的前沿课题之一。数据挖掘的特点有三个方面 6 1 ：第2 章数据挖掘技术综述( 1 ) 数据挖掘的数据量是巨大的。因此，如何高效率地存取数据，如何根据一定应用领域找出数据关系即提高算法的效率，以及是使用全部数据还是部分数据，都成为数据挖掘过程中必须考虑的问题。( 2 ) 数据挖掘面临的数据常常是为其他目的而收集的数据，这就为数据挖掘带来了一定的困难，即一些很重要的数据可能被疏漏或丢失。因此未知性和不完全性始终贯穿数据挖掘的全过程。( 3 ) 数据挖掘常常要求算法主动地提示一些数据的内在关系。新颖性是衡量一个数据挖掘算法好坏的重要标准。显然，数据挖掘有别于传统的数据分析方法，它常常是在没有前提假设的情况下，从事信息的挖掘与知识提取。数据挖掘工具能够对将来的趋势和行为进行预测，从而很好地支持人们的决策；比如经过对公司整个数据库系统的分析，数据挖掘工具可以回答诸如“哪个客户对我们公司的邮件推销活动最有可能做出反应，为什么”等类似的问题。有些数据挖掘工具还能够解决一些很消耗人工时间的传统问题，因为它们能够快速地浏览整个数据库，找出一些专家们不易察觉的极有用的信息。综上，数据挖掘的定义可以从技术和商业两个方面来考量：( 1 ) 技术上的定义数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程n 司。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。( 2 ) 商业角度的定义数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决基于聚类的增量数据挖掘研究策的关键性数据【9 ，姗。数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。2 2 数据挖掘的过程数据挖掘是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。图2 1 数据挖掘主要步骤f i g 2 1m l a i np r o c e s s e so fd m如图2 1 ，整个数据挖掘的主要步骤有 2 j 4 , 1 5 j 6 ：( 1 ) 数据清洗( d a t ac l e a n i n g ) ，其作用就是清除数据噪声和与挖掘主题明显无关的数据。( 2 ) 数据集成( d a t ai n t e g r a t i o n ) ，其作用就是将来自多数据源中的相关数据组合到一起。( 3 ) 数据转换( d a t a t r a n s f o r m a t i o n ) ，其作用就是将数据转换为易于进行数据挖第2 章数据挖掘技术综述掘的数据存储形式；也就是将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。( 4 ) 数据挖掘( d a t am i n i n g ) ，它是知识挖掘的一个基本步骤，其作用就是利用智能方法挖掘数据模式或规律知识。( 5 ) 模式评估( p a t t e r ne v a l u a t i o n ) ，其作用就是根据一定评估标准( i n t e r e s t i n gm e a s u r e s ) 从挖掘结果筛选出有意义的模式知识；其使用的分析方法一般应作数据挖掘操作而定，通常会用到可视化技术。( 6 ) 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ，其作用就是利用可视化和知识表达技术，向用户展示所挖掘出的相关知识。2 3 数据挖掘的任务数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差分析等。( 1 ) 关联分析( a s s o c i a t i o na n a l y s i s )关联规则挖掘是由r a k e s h a p w a l 等人首先提出的。两个或两个以上变量的取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规则的相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。( 2 ) 聚类分析( c l u s t e r i n g )聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性之间的相互关系。( 3 ) 分类( c l a s s i f i c a t i o n )分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预测。8 -基于聚类的增营数据挖掘研究( 4 ) 预测( p r e d i c a t i o n )预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种类及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。( 5 ) 时序模式( t i m e - s e r i e sp a t t e m )时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不同。( 6 ) 偏差分析( d e v i a t i o n )在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结果与参照之间的差别。2 4 数据挖掘对象知识发现的范围非常广泛，可以是社会科学、商业、科学处理产生的数据或卫星观测得到的数据。它们的数据结构也各不相同，可以是层次的、网状的、关系的和面向对象的数据。就目前来看，数据挖掘未来的几个热点包括数据仓库的数据挖掘、网站的数据挖掘( w e bs i t ed a t am i n i n g ) 及其文本的数据挖掘( t e x t u a lm i n i n g ) 。下面就这几个方面加以简单介绍。( 1 ) 数据仓库从数据仓库进行知识发现就是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。从关系数据库中进行数据挖掘是当前研究的比较多的，目前研究的主要问题：1 ) 超大数据量。数据库中数据的迅速增长是数据挖掘得以发展的原因之一，这也正是对数据挖掘研究的挑战。枚举法、经验分析法对数兆字节、数以t 计字节的数据显得无能为力，此时数据挖掘系统必须采用一定的数据汇集方法，根据用户定义的发现任务，选择有关的域空间，采取随机抽样的方法，对样本进行分析。2 ) 动态变化的数据。数据的动态变化是大多数数据库的一个主要特点，一个第2 章数据挖掘技术综述联机系统应能够保证数据的变化不会导致错误的发生。3 ) 噪声。由于人为因素的影响，如数据的手工录入以及主观选取数据等引起的错误数据，使得数据具有噪声。带噪声的数据会影响抽取的模式的准确性，可造成最终结果的不确定性。发现和表示这样的模式要用概率的方法，用概率来表示。4 ) 数据不完整。数据库中某些记录的属性域可能存在空值现象，另外对某一发现来说还可能完全不存在其所必须的记录域，这造成了数据的不完整。这些都给发现、评价和解释一些重要的模式带来困难。5 ) 冗余信息。数据库中同一信息有时存储在多个地方。函数依赖就是一个通常的冗余形式。冗余信息可能造成错误的知识发现，至少有些发现是用户完全不感兴趣的。为避免这种情况发生，系统需要知道数据库中有那些固有的依赖关系。6 ) 数据稀疏。数据库对应于可能的巨大发现空间，它的实际数据记录的密度非常稀疏。( 2 ) 文本的数据挖掘( t e x t u a lm i n i n g )页面模式抽取需要经过文本分析过程。文本分析过程就是分析文本，从中找出一些特征，以利于将来的使用。举个例子，在客户服务中心，把同客户的谈话转化为文本数据，再对这些数据进行挖掘，进而了解客户对服务的满意程度和客户的需求以及客户之间的相互关系等信息。从这个例子可以看出，无论是在数据结构还是在分析处理方法方面，文本数据挖掘和其他方面谈到的数据挖掘相差很大。一般地，文本分析有以下几个基本过程：1 ) 语种识别语种识别工具能自动发现文本使用的是何种语种。它利用文本内容的一些线索去识别语种。如果文本使用两种语种，它能确定哪部分使用哪种语种，这个确定过程是根据相应语种的训练文本训练的，同时还能通过训练识别其他语种。它可以根据不同的语种自动组织索引数据，不同的语种有不同的查询结果，能将文本提交给语种翻译器。基于聚类的增量数据挖掘研究2 ) 特征提取特征提取主要是识别文本中词项的意义，提取过程是自动的。提取的特征与分析文本的领域有关，且大部分就是文本集中表示的概念，因此特征提取是一种强有力的文本挖掘技术。自动识别的特征可能包括如下几部分：人名、组织名、地名、多字词、缩写，其他如日期、货币等。分析一文本时，特征识别工具采取两种模式：一个是单独分析该文本；另一个是先根据其他相似的文本自动建立一个词典，然后在该文本找到词典中出现的词项。如果分析的是文集，特征提取工具则先从许多文本中找到一些特征，然后取最优的词汇。例如，它经常监测到几个不同的词确实是同一特征的不同变形，那么就可以取其中一个( 通常是最长的一个) 作为该特征的规范形式。另外，也可以给每一个词赋予一个统计测度，该统计测度是具有同一意义的单词、词组的测度之和。3 ) 聚类聚类是把一个文本集合分成几组的过程。每组中的文本在某种情况下相似。如果把文本内容作为聚类的基础，那么不同的组就对应文本集中不同的主题。因此聚类可用来找到集合包含什么内容，即通过识别在文本组中常用的一系列术语或单词来描述主题。聚类也可以通过文本的长度、日期等特征来进行。因此，聚类可以描述整个文本集的内容，找到其中隐含的相似关系，从而更容易找到相似或相关的信息。聚类后，组内的文本相似度极大，组间的文本相似度极小。4 ) 分类分类工具是把文本分配到己存在的类中，即己存在的“主题”中。如果由人工分类，处理如此多的数据将是一个很巨大的工程，很不实际，而通过自动组织，把文本分到相应的主题中，使之更容易浏览、查询，是一种数据组织的有力手段。目前关于文本分类的文献较多：a p t 用决策树技术来获取分类器；y a n g 构造了一种近邻算法进行分类；l e w i s 采用了一个线性分类器；c o h e n 设计了一种建立在权值更新基础上的休眠专家算法。用以上所提及的一些方法对文本分类时，首先将网页表示为关键词或概念向量，然后计算向量之间在向量空间中的距离，作为分类依据，如y a n g 距离计算训练集中每一向量与待分类向量的距离，然后选取k 个第2 章数据挖掘技术综述最近距离进行综合分类；而l e w i s 先构成类别向量，然后以向量的内积计算待分类向量与类别向量的距离。( 3 ) w e b 信息随着网络的不断发展，网络数据的规模呈指数级增长。用户面对如此众多的资源，一方面为能获得丰富的信息而感到高兴，但另一方面又为如何从这些信息资源中快速地找到自己所需要的东西而担忧，因此迫切需要一种高效快速的信息资源分析工具帮助用户快速浏览网络，并能从这些大量的信息中找出隐含的内容，减少用户的负担。面对这种需求，w e b 信息挖掘技术应运而生。它是根据面向i n t e r n e t 的分布式信息资源特点的一种模式抽取过程，它不仅能查找到分布式信息资源中已经存在的信息，还能识别出大量存在于数据中的隐含的、有效的规律。目前己有一些机构开展了w e b 信息挖掘工作。i b m 公司建造了一个名为i n t e l l i g e n tm i n e r 的工具，它主要从四个方面分析文本：从文本中抽取关键信息；根据主题组织文本；从文本集中找到一个模式描述该集合；使用强有力的查询来检索文本。c m u 的d a y n ef r e i t a g 则利用一阶谓词，对大学生主页定义类与类间关系，找出一些规律，构成知识库。e t z o n i 等则通过挖掘用户访问站点的记录信息改善站点的设计，帮助用户更快地浏览该站点。2 5 数据挖掘的方法( 1 ) 神经网络方法神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以h o p f i e l d 的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以a r t 模型、k o h o l o n 模型为代表的，用于聚类的自组织映射方法。神经网络方法的缺点是”黑箱”性，人们难以理解网络的学习和决策过程 1 7 , 1 8 。( 2 ) 遗传算法遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生基于聚类的增量数据挖掘研究全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中被加以应用。s u n i l 已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一【1 9 2 , o l 。遗传算法的应用还体现在与神经网络、粗集等技术的结合上。如利用遗传算法优化神经网络结构，在不增加错误率的前提下，删除多余的连接和隐层单元；用遗传算法和b p 算法结合训练神经网络，然后从网络提取规则等。但遗传算法的算法较复杂，收敛于局部极小的较早收敛问题尚未解决。( 3 ) 决策树方法决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。最有影响和最早的决策树方法是由q u i n l a n 提出的著名的基于信息熵的i d 3 算法。它的主要问题是：i d 3 是非递增学习算法；i d 3 决策树是单变量决策树，复杂概念的表达困难；同性间的相互关系强调不够；抗噪性差。针对上述问题，出现了许多较好的改进算法，如s c h l i m m e r 和f i s h e r 设计了i d 4递增式学习算法；钟鸣，陈文伟等提出了i b l e 算法等。( 4 ) 粗集方法粗集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。粗集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基础。但粗集的数学基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在的。因此连续属性的离散化是制约粗集理论实用化的难点。现在国际上已经研制出来了一些基于粗集的工具应用软件，如加拿大r e g i n a 大学开发的k d d r ；美国k a n s a s 大学开发的l e r s 等1 5 卫1 1 。( 5 ) 覆盖正例排斥反例方法它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合第2 章数据挖掘技术综述中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则保留。按此思想循环所有正例种子，将得到正例的规则( 选择子的合取式) 。比较典型的算法有m i c h a l s k i 的a q l l 方法、洪家荣改进的a q l 5 方法以及他的a e 5方法。( 6 ) 统计分析方法在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性关系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用统计( 求大量数据中的最大值、最小值、总和、平均值等) 、回归分析( 用回归方程来表示变量间的数量关系) 、相关分析( 用相关系数来度量变量间的相关程度) 、差异分析( 从样本统计量的值得出差异来确定总体参数之间是否存在差异)等。( 7 ) 模糊集方法即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础上，提出了定性定量不确定性转换模型一云模型，并形成了云理论。2 6 数据挖掘的应用数据挖掘在应用上已取得一批丰硕成果，特别在超大型数据库方面。芬兰著名学者k o h o n e n 教授采用“自组织映射( s o m ) ”神经网络实现超大型数据库的数据挖掘，颇受人们重视。他提出了一个实例，描述一个数据的组织系统和按内容访问的存储器。该系统由两层s o m 体系结构组成，文本由上层的网络节点映射，其几何图形位置的顺序反映了内容的相似性；下层网络节点是对文字进行映射，将文字聚成若干类。使用该系统对报纸和新闻进行分类，得到1 1 0 万条信息。约2亿文字。信息采掘系统按其语义、内容聚类，经过主体筛选，最终送s o i l 处理的有6 万多个文字。这个网络很大，第一级输入有2 7 0 个节点，第二级输入有3 1 5个节点，输出最终达1 0 万个。该系统可用于查询，人们将来可用来建立个人信箱。基于聚类的增量数据挖掘研究如果需要专门收集某一方面的信息，该系统可在信息海洋中查询，自动将你感兴趣的数据信息送到你的信箱中。而空间数据挖掘的目的则是空间数据库发现各种隐含知识，如空间对象的位置关系、特征模式等，可广泛应用千地理信息系统、图象数据库探索、医学图象处理等方面。由于空间数据库具有数据量大、空间数据类型和空间存取方法复杂等特点，空间数据算法的效率是其中最富有挑战性的问题。数据挖掘在i n t e m e t 中的应用也日益增多，国外已研制开发出h a r v e s t ，s h o p b o t ，a h o y 等系统。其中，h a r v e s t 系统是较为典型的数据挖掘信息提取系统。它处理的对象是半结构化的文档。每天它都利用手工编写的w r a p p e r 分析一批固定的w e b 资源。在l a t e x 文档中，它可以找到作者、标题等信息；在p o s t s c r i p t 文档中，它可以找到格式、位置等信息。另外，数据挖掘还可以用于金融业、大型连锁商场等。例如，利用可试化技术将银行的存款、贷款、利率、投资基金、信托基金等数据关联里现出来，使银行更好地安排和管理业务。证券业采用数据挖掘技术，对全球股市、期货市场实时数据进行提取，借助人的智慧和经验进行判断，揭示其内在规律性，以取得最大收益。大型连锁商场则可用此技术找出各种商品销售之间的关联以及分析商品的资金占有比例，以达到最佳的资源配置。第3 章聚类分析相关概念及算法第3 章聚类分析相关概念及算法聚类( c l u s t e r i n g ) 是对物理的或抽象的对象集合分组的过程。聚类生成的组称为簇( c l u s t e r ) ，簇是数据对象的集合。簇内部的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象之间具有较高的相异度。相异度可以根据描述对象的属性值计算，对象间的距离是最常采用的度量指标。在实际应用中，经常将一个簇中的数据对象作为一个整体看待。虽然用聚类生成的簇来表达数据集不可避免地会损失一些信息，但却可以使问题得到必要的简化。3 。1 聚类分析概述3 1 1 简介聚类分析是数据分析中的一种重要技术，它的应用非常广泛。许多领域中都会涉及聚类分析方法的应用和研究工作。如统计学、模式识别、生物学、空间数据库技术、电子商务等。在统计分析中，聚类也称为聚类分析，它是多元分析的三大方法之一( 另外两种是回归分析、判别分析) ，已经有很多年的历史。主要研究基于距离和基于相似度的聚算法。传统的统计聚类方法包括：系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这些聚类方法是一种基于全局比较的聚类方法，它需要考察所有个体才能决定类的划分，因此它要求所有的数据必须事先给定，而不能动态增加新数据对象。这样的聚类分析方法不具有线性的计算复杂度，难于适应数据库非常大的情况。从机器学习的角度看，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程，称作无监督或无教师归纳。与分类学习相比，分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法自行确定。从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。例如，在科学数据探测、信息检索、文本挖掘、空间数据库分析、w e b 数据分析、客户关系管理( c r m ) 、生物学等方面的数据挖掘软件中，聚类分析技术起着重要作用，并且算法效率不断地被提高，应用范围也越来越广泛。基于聚类的增量数据挖掘研究在商务上，聚类能帮助市场分析人士从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群特征。在生物学上，聚类能用于推导动物和植物的分类，对基因进行分类，获得种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。随着i n t e m e t 的不断发展和普及，聚类也可以用于对w e b 上的文档进行分类，以发现有用的信息，作为一个数据挖掘功能，聚类分析能作为一个独立的工具来获得数据分布情况观察每个簇的特点，集中对某个类做进一步的分析。此外，聚类分析可以作为其它算法( 如特征和分类等) 的预处理步骤，这些算法再在较高粒度的数据一类上进行处理。3 1 2 聚类处理的数据结构聚类算法通常采用两种具有代表性的数据结构：一个是数据矩阵，一个是相异程度矩阵。在考察一个实体集时，选用p 个属性来描述实体，集合中的每个成员都可以用一组有序的属性值来表示，记为一个向量。假设该实体集有拧个成员，就可以用n 个含有p 个元素的向量来表示该实体集，这厅个向量组成的矩阵即为数据矩阵，如下所示：( 行代表实体)x u j x a 9五1 嘞l 为了考察实体集中成员间的近似性，引入相异度矩阵进行度量，该矩阵是一胛厅的矩阵，如下所示：d ( 1 ， )d ( 2 ，1 )4 3 ，n )oo ；ddd动力笱也oq ；“巩。邪；如d 力力0qg ；“o谁弗；如第3 章聚类分析相关概念及算法其中，4 i ，j ) 表示集合成员f 与j 之间相异性的量化表示，通常为非负数，且d ( f ，j ) = d ( j ，f ) ，d ( f ，f ) = o ，成员间相似度越高，则d ( f ，f ) 越趋近于0 ，反之，d ( f ，f )值越大。聚类算法中许多都是以相异程度矩阵为基础的，但评价集合成员间的相似程度时很难定义“足够相似了”，只能凭主观确定。3 1 3 聚类处理的数据类型聚类分析通常都是针对具体问题进行处理的，要进行聚类的数据集的数据类型也多种多样。对待不同的数据类型，其相应的聚类处理方法也有所不同。通常来说，数据集是由多个数据样本所构成的集合，每个样本又包含多个属性值，其结构类似于数据库的结构。数据集的数据类型主要是指样本属性的取值类型，通常有多种类型，如数值型、文字型等。对这些属性取值的详细分类有助与分析样本间的区别，进而有助于设计相应的聚类模型和算法。假设数据集x 中有厅个数据样本，工和y 表示其中两个样本，且石，y 可以表示成工= k ，x 2 , - - , x p ) 雨 1 y = ( y 1 ，y 2 ，y ，) 的形式，其中而，只分别表示工和y 的第f个属性值。则可将样本的属性取值分为以下4 种类型 2 2 , 2 3 , 2 4 ：( 1 ) 连续型即属性的两个不同取值之间有无穷个其它的取值，例如温度、高度等。这一类型的属性通常用数值( 实数或整数) 来表示，又称为定量型变量。一般来说，对定量型变量进行适当的数学计算是有