（计算机软件与理论专业论文）聚类分析和离群点识别技术研究及其应用.pdf

哈尔滨工程大学硕士学位论文 摘要 离群点识别和聚类分析是数据挖掘研究的重要方面，基于离群点分析的 各种数据挖掘算法的研究已经成为研究热门方向。但是目前大多数的离群点 分析算法只是针对于静态数据集的操作，对于动态数据集一般采取对整个数 据集重新进行离群点分析的方式，因此随着数据量的不断增大以及对数据集 实时数据挖掘的需求不断加大，增量式离群点分析技术正越来越引人关注。 本文首先总结、探讨关于数据挖掘、离群点分析、聚类算法以及计算机 审计等方面取得的己有主要研究成果，并详细阐释了基于密度的聚类算法 d b s c a n 和基于密度的离群点识别算法l o f 的主要思想、。算法流程，并在 此基础上，提出了基于局部密度的增量式离群点识别算法i n c r e m e n t a l l o f ， 并结合社会保障联网审计系统f n s a s ) ，通过实验验证了l o f 与 i n c r e m e n t a l l o f 在离群点分析结果上的一致性，和i n c r e m e n t a l l o f 在大数据 量环境下更加卓越的性能，以及i n c r e m e n t a l l o f 能对所提供的数据进行挖掘， 得出一些反常的、隐藏在大数据后的有违规缴费等可能的信息，为社保审计 提供可靠依据，提高审计工作效率，规范社会保险业务，减少社会保险金欺 诈等。 关键词：离群点；增量式数据挖掘；局部密度；社保审计 哈尔滨工程大学硕士学位论文 a b s t r a c t o u t l i e ri d e n t i f i c a t i o na n dc l u s t e ra n a l y s i sa r ei m p o r t a n ta s p e c t so fd a t a m i n i n g ，t h eo u t l i e r sa n a l y s i so fd a t am i n i n ga l g o r i t h m sb e c o m ep o p u l a rr e s e a r c h d i r e c t i o n m o s to ft h eo u t l i e ra n a l y s i sa l g o r i t h mi s s p e c i f i ct ot h eo p e r a t i o no f s t a t i cd a t as e t s d y n a m i cd a t as e t sc a no n l yb e t a k e no nt h ee n t i r ed a t as e t r e a n a l y s i s w i t ht h eg r o w i n gv o l u m eo fd a t aa n dt h ei n c r e a s i n gd e m a n do fd a t a m i n i n ga l g o r i t h m so fr e a l - t i m ec o l l e c t i o n , i n c r e m e n t a lo u t l i e ra n a l y s i st e c h n o l o g y i si n c r e a s i n g l yo fc o n c e r n t h i st h e s i ss u m m a r i z et h ed a t am i n i n g ，o u t l i e ra n a l y s i sa n dc l u s t e r i n g a l g o r i t h ma n dt h e i ro w nm a j o rs t u d yr e s u l t s ，a n de x p l a i n et h ed e t a i lo ft h em a i n i d e a sa n dt h ea l g o r i t h mp r o c e s s e so fd b s c a nw h i c hi sad e n s i t y b a s e d c l u s t e r i n ga l g o r i t h ma n dl o fw h i c hi sad e n s i t y b a s e do u t l i e ri d e n t i f i c a t i o n a l g o r i t h m o nt h i sb a s i s ，t h e s i s a d o p t e dh a c r e m e n t a l l o fw h i c hi s al o c a l d e n s i t y b a s e di n c r e m e n t a l o u t l i e r a n a l y s i sa l g o r i t h m ，a n dc o m b i n e 诚t l lt h e n e t w o r k - b a s e ds o c i a l - s e c u r i t ya u d i ts y s t e m , e x p e r i m e n t a lr e s u l t ss h o wt h el o f a n di n c r e m e n t a l l o fi no u t l i e ra n a l y s i so ft h ee f f e c th a v et h ec o r l s i s t e l l c y ，a n d i n c r e m e n t a l l o fi nt h el a r g ev o l u m eo fd a t ae n v i r o n m e n te v e nm o r es u p e r i o r p e r f o r m a n c e a r i di n c r e m e n t a l l o fc a nb ep r o v i d ei n t ot h ei n c r e m e n t a ld a t a m i n i n g ，d r a ws o m eu n u s u a l ，h i d d i n gi nt h ed a t aw e r ep o s s i b l ei r r e g u l a r i t i e s ，s u c h a sp a y m e n ti n f o r m a t i o n i tc a np r o v i d ear e l i a b l eb a s i sf o rt h es o c i a ls e c u r i t ya u d i t ， i m p r o v et h ea u d i tw o r ke f f i c i e n c y , a n ds t a n d a r d i z et h eb u s i n e s s ，t h er e d u c t i o no f s o c i a li n s u r a n c ef r a u d k e y w o r d s ：o u t l i e r ；i n c r e m e n t a ld a t am i n i n g ；l o c a ld e n s i t y ；s o c i a l s e c u r i t ya u d i t 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指 导下，由作者本人独立完成的。有关观点、方法、数据 和文献的引用已在文中指出，并与参考文献相对应。除 文中已注明引用的内容外，本论文不包含任何其他个人 或集体己经公开发表的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者( 签字) ： 夏勇 日期：2 矽口g 年，歹月铲日 哈尔滨工程大学硕士学位论文 1 1 课题背景 第1 章绪论 随着经济的发展，企业活动日益错综复杂，交易数量愈加庞大，同时， 由于计算机技术、数据库技术及数据存储技术的不断发展，信息技术正在以 前所未有的速度广泛地应用于社会经济生活的各个领域，有力地推动着人类 社会的发展。人们产生和收集数据的能力得到迅速提高，很多企业开始引入 计算机技术进行管理，如企业资源计划系统( 企业资源规划) 和供应链管理系 统( 供应链管理) 等。这些系统使企业业务信息系统和财务系统高度集成，在 会计信息处理上抛弃了以往手工记账的模式，会计信息的记载、处理、传递 和输出形式发生了质的变化，由此出现的数据海量化的趋势已不可逆转。数 据正在_ 以惊人的速度增长，堆积如山，展现在人们面前的已不是局限于本部 门、本单位和本行业的庞大数据库，而是互相交织的信息海洋。 有调查显示，全球数据存储量以年均8 0 的速度递增，1 9 9 9 年，全球数 据存储总量为18 4 6 4 1t b ，而到2 0 0 4 年已经达到2 0 0 0 0 0 0 t b 。面对这极度膨 胀的数据量，人们受到“信息爆炸”、“混沌信息空间 和“数据过剩 的巨 大压力，不同领域的人们都在期待着从这些数据中得到自己想要的信息。 作为行使独立监管职能的审计机关如何应对被审单位数据日益海量化的 挑战，如何对被审单位的海量数据进行可靠有效地审计分析是一个亟待解决 的问题。为了适应这种审计需求的变化，急需对传统的审计方式、手段进行 革命性的变革，创新审计理念、模式、方式与技术。 技术进步源于实际的应用需求，技术的进步又促进应用的日臻完善。计 算机审计技术的发展也不例外。正是由于信息化水平的飞速发展，计算机在 各行各业中的应用所导致的数据海量化趋势，使得传统审计理论和实务遇到 了前所未有的挑战，在被审单位海量的数据中进行可靠的、高效的审计成为 一种新的需求。这种需求导致了计算机审计技术的产生和不断发展，数据挖 掘技术应用于计算机审计领域正是这种发展的结果。正如李金华审计长指出 哈尔滨t 程大学硕士学位论文 的，“计算机审计是一场革命”，“审计人员不掌握计算机，将要失去审计的资 格 。对计算机审计应用数据挖掘技术进行系统而深入地研究，无论是对于丰 富和发展审计理论，还是对于开展审计工作都有着十分重要的意义。 计算机审计是信息技术应用在审计实务中产生的一个新概念，自从出现 “计算机审计”一词来，对计算机审计的概念一直存在着模糊不清的认识， 随着理论和实践的不断发展，人们对计算机审计理解逐步深入。就目前而言， 计算机审计可以定义为，被审计对象运用信息技术进行财务工作和经营时， 审计人员为了实现其审计目的，收集必要的审计证据，采取必要的审计程序， 对企业的信息系统的合规性以及利用信息系统生成的生产信息、财务信息进 行审计的工作。 因此，计算机审计主要包括两方面的内容，一是指审计人员使用审计软 件来检查被审单位的信息系统，是对被审计单位经济活动和会计资料是否真 实、正确、合法和有效所进行的审计，这与传统的审计内容上是基本一致的， 只是手段发生了变化，一般称为计算机辅助审计；二是对电子信息系统本身 进行测试和评价，指通过搜集并评价审计证据，以判断与被审计单位信息系 统有关的资源与资产的安全、资料与系统的完整性等。 目前，计算机审计软件多是利用审计人员的经验和计算机查询技术相结 合的方法对被审计单位电子数据进行审计。发现其中的异常情况。但这存在 多处不足：一是审计人员的经验和知识是“有限的”，被审计对象行业跨度大。 各单位情况千差万别，当审计经验无法运用时，面对海量数据真有如“瞎子 摸象；二是数据是不断发展的，审计经验相对于数据往往是滞后的，这种不 同步性给审计带来巨大的潜在风险：三是对同一数据审计，不同的审计人员 可能会得出完全不同的审计结论，知识结构的不同无法保障审计质量：四是 传统的数据分析方法无法处理庞大的数据库系统，技术工具的落后性势必影 响审计的广度和深度：五是我国经济的飞速发展，金融和各类市场的发育使 审计的范围和规模逐步扩大，信用危机以及各式各样的金融犯罪也对审计提 出了更高的要求，电子化和网络化环境使得作弊手法越发隐蔽，数据难以追 踪，审计无从下手。 社会保障制度是关系国家发展、社会稳定的重要保障。一方面，国家为 建立社保体系每年要投入大量资金，中央财政每年投入5 0 0 多亿，地方财政 哈尔滨工程大学硕士学位论文 也要拿出很大一笔资金，另一方面，单位及参保人员还要缴纳保险费。社保 资金的管理、征缴、使用既体现国家的利益，也直接关系到参保人员的个人 利益。因此，对社保资金的审计是审计机关的重要职责和任务。 1 2 课题研究的目的和意义 在当前国家建设和谐社会的背景下，社会保障基金作为人民大众的“保 命钱 越来越受到重视。但是，以上海、云南等地的社会保障基金案件为代 表的一系列案件表明，社会保障基金的管理并不尽如人意。如何开展针对社 会保障的审计、提高对社会保障基金监督的力度，已经成为一件事关民心、 攸关社会稳定的大事。但社会保障的审计需要处理非常庞大的信息量，因此 传统的手工审计方式并不适用。现有的计算机审计技术则主要是转化手工审 计方法；其工作模式是被动执行，并不能处理新出现的或特殊的社会保障业 务，因此不能很好的处理全国各地社会保障业务间存在的众多差异。 本文提出基于数据挖掘中的离群点识别技术辅助审计人员开展针对社会 保障的审计，从而提高计算机审计技术的智能化、适应力、可靠性和效率。 当前，数据挖掘技术已经取得了非常大的进展，在商业、工业、医学等 领域有着成功的应用。这些成就让我们相信，数据挖掘技术应用于审计领域 能够发现海量社会保障数据中的异常与规律，据此做出审计判断。 但是，以社会保障和审计为代表的政务领域与商业、工业等领域间存在 着非常明显的差异。社会保障数据有明确的现实含义，数据项间通常有较强 的线性关系，反映了社会保障制度规则。通常缺少领域专家的有力支持，全 国范围内同时精通数据挖掘、审计和社会保障的专家凤毛麟角，配置一组各 领域的专家对审计工作的人力要求过于苛刻。因此，利用数据挖掘技术分析 社会保障数据并不是一个简单的问题。遗憾的是，这方面的研究非常稀少。 本文将在下述方面展开研究：分析社会保障的核心业务和审计所需的核 心数据，作为离群点识别分析的对象：在拥有少量专家经验或在缺少指导的 情况下，采用离群点识别技术，发现海量社会保障数据中的异常，作为审计 依据；研究聚类技术与离群点识别技术的互补结合分析社会保障数据的策略。 研究成果能够提高对社会保障审计的效率，弥补传统审计方法的一些重 哈尔滨工程大学硕士学位论文 要缺欠，提高对社会保障基金管理的监管力度；拓展了数据挖掘技术的应用 领域，对数据挖掘算法的研究成果有助于解决现有技术的一些缺欠，对相关 领域有借鉴意义。因此，本课题具有明显的理论意义和实用价值，能够产生 较大的社会效益和经济效益。 1 3 国内外研究现状 1 3 1 计算机审计研究现状 国外对计算机审计的研究始于2 0 世纪6 0 年代，虽然在各国计算机审计 发展历史并不久远，但对其研究已有相当规模和成果。 美国己普遍实行了计算机审计，政府审计机构和大型会计师事务所可以 把自己的计算机终端联接到大型计算机网络上，审计人员只要在自己的终端 上就可以调取被审计单位的有关资料进行审计，实现了审计的动态监控。 瑞典国家审计署建设的“梦想蓝图”工程，计划实现审计人员无论身处 何地，都可以通过访问被审单位的中央数据库信息进行实时监控和审计，要 求被审单位以审计人员可以访问的方式存储数据，目前这一工程已成功地开 发了相关审计支持软件系统。 加拿大也是对计算机审计进行研究较早的国家之一。加拿大审计长公署 每年都要对计算机应用比较普遍的企业进行广泛的调查。具体实施审计时， 特别注重系统内部控制制度的审查与评价。在开发利用计算机辅助审计技术 方面，加拿大审计长公署提出了开发目标是有利于提高审计的效果和效率， 计算机辅助审计技术应满足实施数据抽样、验证数据整体的完整性，以及对 关键经济业务进行检索的要求。 在国内，从1 9 9 8 年开始，审计署提出审计信息化建设的相关意见，并开 始筹备金审工程。金审工程是审计信息化系统建设项目的简称，是国家信 息化领导小组关于我国电子政务建设指导意见中确定的十二个重点业务系 统之一。金审工程利用先进的计算机技术、通讯技术、网络技术、多媒体和 流媒体技术、数据库技术，依托政府电子政务网络平台，建成对财政、银行、 税务、海关等部门，重点国有企事业单位以及其他重点被审计单位的财务信 息系统及相关电子数据进行密切跟踪，实施有效审计监督的信息化系统。 4 哈尔滨工程大学硕士学位论文 2 0 0 2 年，我国正式启动金审工程一期建设项目，重点实施了网络系统、 应用系统、安全系统、机房设施、人员培训等内容，开展了联网审计的应用 试点，在联网审计技术上有了一些初步的尝试。本课题即来源于国家审计署 金审一期重点项目：社保联网审计系统烈s a s ) 。+ 金审二期工程新建项目的主要内容就是计算机联网审计，重点建设集中 在数据挖掘、数据共享、数据中心方而，最终目标是利用信息网络技术，及 时地发现和查处大案要案，把好审计的关口，从事后的规范转变到事中控制， 避免经济损失后再审计监督。 在我国学者对计算机审计的研究中，武海平和余宏亮等人【u 分析了计算 机联网审计应用系统的特点，提出了一种适用于计算机联网审计系统的海量 数据存储与管理策略，并着重对计算机审计系统的基本构成、物理设计与逻 辑设计进行了描述。曹洪泽和刘强口1 运用信息系统开发的理论与方法，提出 了联网审计的实施部署方案，并结合审计业务的具体模式，重点分析了审计 业务网组网技术、被审计单位端数据采集技术、审计端数据处理技术等。薛 婷婷p 1 提出了计算机审计审前信息系统调查方法。李娅，孙玉星州在分析分布 式数据库技术基础上，讨论了实现在分布式数据库下计算机审计的可能性和 相关实现技术，同时也考虑了计算机审计安全方面的问题。 我国对计算机审计的研究起步较晚，而且也缺乏系统性。计算机审计在 现行审计理论框架中还是一个新概念，在审计实践中，计算机审计也还处在 起步阶段。各界对计算机审计的研究才刚刚开始，其相关理论尚未形成完整 体系，技术也尚不完善，还有待进一步的研究与实践。 1 3 2 数据挖掘研究现状 数据挖掘在研究和应用方面发展迅速，尤其在商业和银行领域，其应用 比研究的发展速度还要快。目前，根据国际上数据挖掘发展趋势，其研究内 容主要有以下几个方面：对聚类技术p 捌的进一步研究，如对聚类边界点f 1 的 识别研究；。对知识发现方法的进一步研究，如近年来注重对b a y e s ( i ) - i 叶斯l 方法口3 1 以及b o o s t i n g t 2 9 1 方法的研究和提高；传统的统计学回归法在数据挖掘 中的应用；高维数据中的数据挖掘1 3 4 等。在应用方面包括数据挖掘商业软件 工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。 哈尔滨工程大学硕士学位论文 用户主要集中在大型银行、保险公司、电信和销售行业，制造业的应用也在 逐渐展开。国外很多计算机和软件公司也非常重视数据挖掘的开发和应用， i b m 和微软都成立了相应的研究中心进行这方面的工作。 离群点识别技术在国外也获得了广泛的研究和应用，代表性的算法有t j o h n s o n 的d e e p l o c t 0 1 、mm b r e u n i g 的o p t i c s - o f 9 1 、dy u 的f i n d o u t 1 0 1 、 ek n o r r 的f i n d a l l o u t s d 1 、hpk r i e g e l 的l o f 1 2 1 、mj o s h i 的n p r u l e ”1 等。 当前，离群数据挖掘已经应用在电信和信用卡欺骗检测、贷款审批、破产欺 骗检测、电子商务中的犯罪活动的检测、网络入侵检测、市场定制、客户分 类、药物研究及天气预报等领域中。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体的力量，1 9 9 3 年 国家自然科学基金首次支持该领域的研究项目。目前，国内许多科研单位和 高等院校竟相开展知识发现的基础理论及其应用研究，如清华大学、中科院 计算技术研究所、空军第三研究所、海军装备论证中心等；北京大学也在开 展对数据立方体代数的研究；青岛大学数据仓库与数据挖掘相结合方面的研 究取得了较大进展，目前，正积极推动研究成果在金融、统计、商业和制造 业领域的应用。离群数据挖掘是数据挖掘的一个重要方面，与关联规则、分 类、类描述等数据挖掘不同，离群数据挖掘用来检测数据集中小部分对象， 即数据集中显著不同于其它数据的可疑的数据对象。 1 9 9 1 年，数据挖掘的出现为欺诈侦测和预防分析研究注入了新的活力， 提供了新的思路。国内许多学者纷纷采用数据挖掘技术，对原始的应用业务 数据进行处理，挖掘蕴函在交易数据背后反映交易规则的数据对象，以实现 对业务中可疑行为进行侦测和预测，最终达到指导中防范诈骗的目的。 在增量数据挖掘的研究方面，文献 1 4 1 1 5 1 1 6 研究了数据挖掘的增量式 挖掘算法，分别讨论了数据库记录增加情况下规则的获取算法和记录不增加 而支持度和信任度变化下规则的获取算法。周斌、吴泉源、高洪奎m 1 根据数 据集的渐进性和算法参数的相似性，提出了序列模式的增量式挖掘算法设计 的4 项原则。徐雄、王锁萍、曹磊u 副研究了联机数据挖掘系统中的并行和增 量聚类算法，并给出了算法伪码，证明了联机增量聚类算法相对于传统的 a p r i o r i 算法具有较大优势，同时证明了增量聚类算法及其联机数据挖掘系统 的实用性。徐新华、谢永红u 川提出了增量聚类算法等价性概念，针对用于批 6 哈尔滨工程大学硕士学位论文 量更新的增量d b s c a n 聚类算法，提出了用插入更新数据集生成的子模式 调整原聚类模式的方法。 国内数据挖掘在计算机审计的应用的研究也取得了一定的成果。王忠、 武哲脚1 提出了一种应用模糊神经网络与遗传算法相结合的方法来解决在海量 数据条件下的审计数据的总体分析问题。胡荣，陈月昆球”论述了数据挖掘在 审计中的应用过程模型，总结了数据挖掘在审计中可采用的方法以及可发现 的知识类型。汪加才，朱艺华田1 分析了数据挖掘服务的构造、发现、合成、 移动之后，给出了一个基于移动数据挖掘服务的计算机审计框架模型。 1 5 本文的主要内容和组织结构 本文共分为四个章节： 第1 章主要介绍课题的背景和意义，并从计算机审计，数据挖掘的研究 以及数据挖掘在计算机审计中的应用研究等方面对国内外理论研究和实践情 况进行了概括和综述。 j 第2 章介绍数据挖掘的概念、方法、技术，以及相关的一些应用等，重 点分析聚类分析与离群点识别的原理和相关算法。 第3 章在前文基础上，结合基于密度的聚类算法d b s c a n 和基于密度 的局部离群点识别算法l o f ，提出一种增量式离群点识别算法。 第4 章利用v c + + n e t 编程环境和前一章所提出的增量式离群点识别算 法实现了增量式离群点识别系统，并结合社会保障联网审计系统m s a s ) 项 目的工作成果用实验对算法的正确性、效率等进行了验证。 结论部分总结了本文在数据挖掘算法，尤其是聚类和离群点识别算法， 在计算机审计中的应用方面所作的研究工作，并对以后的研究方向提供了建 议。 哈尔滨工程大学硕士学位论文 第2 章聚类分析和离群点识别 2 1 数据挖掘 人们根据各自的理解提出了多种数据挖掘的定义，例如：美国s a s 软件 研究所提出数据挖掘是“在大量相关数据基础之上进行数据探索和建立相关 模型的先进方法”，b h a v a n i 提出数据挖掘是“使用模式识别技术、统计和数 学技术，在大量的数据中发现有意义的新关系、模式和趋势的过程 ，以及 m i c h e a lj a b e r r y 和g o r d o ns l i n o f f 提出的数据挖掘是“探查和分析大量数 据一发现有意义的模式和规则的过程”等。 1 9 9 6 年u m f a y y a d 给出了目前公认的定义：数据挖掘是从数据集中识 别出有效的、新颖的、潜在有用的、以及最终可理解的模式的非平凡过程， 也就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中发 现隐含的、规律性的、”人们事先未知的、但又是潜在有用的并且最终可以被 人们所理解的信息和知识的过程。这一定义己经被广大的数据挖掘专家所认 可。 数据挖掘的诞生是人们对数据库技术进行长期研究和开发的结果，而数 据挖掘技术发展的同时又反过来促使数据库技术进入了一个更高级的阶段。 传统的数据环境基本上是数据操作型的，传统的信息系统只负责数据的增加、 删除及修改操作，而在数据库的基础上可实现的工作就是联机事务处理 ( o n l i n et r a n s a c t i o np r o c e s s i n g ，o l t p ) 。现在由于数据积累的不断增多，人们 需要分析型的数据环境，于是就出现了由数据库导出的数据仓库，以此为基 础则可以实现联机分析处理( o n l i n ea n a l y t i c a lp r o c e s s i n g ，o l a f ) 。随着海量 数据搜集的可能、计算机处理技术的增强和先进数据挖掘算法的提出，数据 挖掘技术不仅能对过去的数据进行查询和遍历，而且能够找出过去数据之问 潜在有价值的联系，并以一定的形式表现出来，从而极大的满足了人们对知 识的迫切需求，也为企业、商家的决策者提供了有效的决策支持。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面 8 哈尔滨工程大学硕士学位论文 向特定数据库的简单检索查询调用，而且是对这些数据进行微观或宏观的统 计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关 联，甚至利用已有的数据对未来的活动进行预测。数据挖掘是一个工具，而 不是有魔力的权杖。它不会坐在数据库上一直监视数据库，然后当它发现有 意义的模型时发一封电子邮件。它仍然需要了解业务，理解数据，弄清数据， 弄清分析方法。数据挖掘只是帮助用户更深入、更容易地分析数据，它无法 告诉某个模型对用户的实际价值，而且数据挖掘中得到的模型必须要在现实 生活中进行验证。 2 2k 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 k d d ) 是知识信息处理的关 键问题之一。它是一个从大型的数据库中智能地和自动地抽取有用的、可信 的、有效的和可以理解的模式的过程。广义上的数据挖掘代表了数据库中的 知识发现的整个过程，狭义上的数据挖掘是数据库中知识发现的一个处理过 程，也是k d d 的一个重要的环节。在不产生歧义的情下，我们都认为知识 发现和数据挖掘是同一个过程。 k d d 的过程可由以下几个步骤的迭代序列组成，如图2 1 所示。 ( 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 as e l e c t i o n ) ，这一阶段的主要作用是从数据库中提取与 分析任务相关的数据，去掉与挖掘主题明显无关的数据； ( 4 ) 数据变换( d a t at r a n s e f o r m a t i o n ) ，这一阶段的主要作用是将待分析的 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作； ( 5 ) 数据挖掘( d a t am i n i n g ) ，这是k d d 中最重要最基本的步骤，其作应 使用智能方法提取数据模式或规律知识； ( 6 ) 模式评估( p a t t e r ne v a l u a t i o n ) ，这一阶段的作用石根据某种评估标准， 识别提供知识的真正有价值的模式； 9 哈尔滨工程大学硕士学位论文 ( 7 ) 9 5 1 1 识表示( k n o w l e d g ep r e s e n t a t i o n ) 这一阶段使用可视化和知识表示技 术，将数据挖掘的结果呈现给用户。 i - 。一。l 。一一一t 。一一一一一。l 一一 ：lli， 换式 数据厍 图2 1 数据挖掘作为知识发现的一个过程 数据清理、。数据集成、数据选择和数据变换式数据预处理的不同形式， 为数据挖掘准备数据。数据挖掘步骤可能与用户或知识库交互。有价值的模 式提供给用户，或作为新的知识存放在知识库中。 k d d 表示了从低层数据抽象到高级知识的过程。k d d 过程必然是重复 的数据挖掘的结果可能会要求在数据准备阶段作某些必要的变化模式的 后处理也可能导致用户对模式类型作适当的修改等等。 2 3 数据挖掘的方法和技术 2 3 1 数据挖掘的方法 数据挖掘的方法很多，主要有分类、关联规则、聚类、序列模式、时间 序列模式等。具体表述如下： ( 1 ) 分类：分类模式把数据集中的数据项映射到某个给定的类上分类模 式往往表现为一棵分类树，从树根开始搜索，沿着数据满足的分支走，走到 树叶就能确定类别。已有许多数据分类方法，如决策树方法、统计方法及粗 1 0 伊。i。1穸 邓liiljilj 哈尔滨工程大学硕士学位论文 糙集方法等。 ( 2 ) 关联规则是描述事物之间同时出现的规律的知识，关联分析的目的是 为了挖掘出隐藏在数据间的相互关系。关联分析就是给定一组对象和一个记 录集合，通过分析记录集合，推导出对象间的相关性。 ( 3 ) 聚类模式：把数据划分到不同的组中，组之间的差别尽可能大，组内 的差别尽可能小。与分类模式不同，进行聚类前并不知道将要划分成几个组 和什么样的组，也不知道根据哪些数据项来定义组。 ( 4 ) 序列模式：与关联模式相似，它把数据之间的关联性与时间联系起来。 为了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的 时间。 ( 5 ) 时间序列模式：根据资料随时间变化的趋势预测将来的值。其中要考 虑时间的特殊性质，只有充分考虑时间因素，利用现有的数据随时间变化的 一系列值，才能更好的预测将来的值。 2 3 2 数据挖掘的技术 1 统计技术 数据挖掘涉及的科学领域和技术很多，如统计技术。统计技术对数据集 进行挖掘的主要思想是：统计的方法对给定的数据集合假设了一个分布或者 概率模型( 例如一个正态分布) 然后根据模型采用相应的方法来进行挖掘。 2 基于历史的分析 基于历史的分析m b r ( m e m o r y b a s e dr e a s o nin g ) 先根据经验知识寻找相 似的情况，然后将这些情况的信息应用于当前的例子中。这个就是 m b r ( m e m o r y b a s e dr e a s o n i n g ) 的本质。m b r 首先寻找和新记录相似的邻居， 然后利用这些邻居对新数据进行分类和估值。使用m r r 有三个主要问题， 寻找确定的历史数据；决定表示历史数据的最有效的方法；决定距离函数、 联合函数和邻居的数量。 3 遗传算法 基于进化理论，并采用遗传结合、遗传变异、以及自然选择等设计方法 的优化技术。主要思想是：根据适者生存的原则，形成由当前群体中最适合 的规则组成新的群体，以及这些规则的后代。典型情况下，规则的适合度 哈尔滨t 程大学硕士学位论文 ( f i t n e s s ) 用它对训练样本集的分类准确率评估。 4 连接分析 连接分析( l i n ka n a l y s i s ) ，它的基本理论是图论。图论的思想是寻找一个 可以得出好结果但不是完美结果的算法，而不是去寻找完美的解的算法。连 接分析就是运用了这样的思想：不完美的结果如果是可行的，那么这样的分 析就是一个好的分析。利用连接分析，可以从一些用户的行为中分析出一些 模式；同时将产生的概念应用于更广的用户群体中。 5 决策树 决策树是一个类似流程图的树型结构，其中每个内部节点表示在一个属 性上的测试，每个分枝代表1 个测试输出，而每个树叶点代表类或类分布。 树的最顶层节点是根节点。目前，在数据挖掘中使用的决策树方法有多种， 典型的在国际上影响较大的决策树方法是q u i n l a n 研制的i d 3 算法。 6 神经网络 在结构上，可以把一个神经网络划分为输入层、输出层和隐含层。输入 层的每个节点对应一个个的预测变量。输出层的节点对应目标变量，可有多 个。在输入层和输出层之间是隐含层( 对神经网络使用者来说不可见) ，隐含 层的层数和每层节点的个数决定了神经网络的复杂度。除了输入层的节点， 神经网络的每个节点都与很多它前面的节点( 称为此节点的输入节点) 连接在 一起，每个连接对应一个权重w x v ，此节点的值就是通过它所有输入节点的 值与对应连接权重乘积的和作为一个函数的输入而得到，我们把这个函数称 为活动函数或挤压函数。 7 粗糙集 粗糙集理论基于给定训练数据内部的等价类的建立。形成等价类的所有 数据样本是不加区分的，即对于描述数据的属性，这些样本是等价的。给定 现实世界数据，通常有些类不能被可用的属性区分。粗糙集就是用来近似或 粗略地定义这种类。 8 模糊集 模糊集理论将模糊逻辑引入数据挖掘分类系统，允许定义“模糊 域值 或边界。模糊逻辑使用0 0 和1 0 之间的真值表示一个特定的值是一个给定 成员的程度，而不是用类或集合的精确截断。模糊逻辑提供了在高抽象层处 1 2 哈尔滨工程大学硕+ 学位论文 理的便利。 9 回归分析 回归分析分为线性回归、多元回归和非线性回归。在线性回归中，数据 用直线建模，多元回归是线性回归的扩展，涉及多个预测变量。非线性回归 是在基本线性模型上添加多项式项形成非线性回归模型。 10 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后 者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中 所有对象的共性。 2 4 聚类方法 聚类隋馏1 ( c l u s t e r i n 曲是数据挖掘领域最为常见的方法之一，用于发现在数 据库中未知的对象类。通过聚类形成的每一个组称为一个类簇( c l u s t e r ) ，在 同一簇中的对象具有较高的相似度，而不同簇中的对象相差较大。人们通过 聚类识别密集的或稀疏的区域，从而发现全局的分布模式，以及数据属性之 间有趣的相互关系。目前的聚类方法已经广泛应用在如数据挖掘、统计学、 机器学习、空间数据库技术、生物学以及入侵检测和天气预报等等相关领域 中，取得了很大的成功和实用价值。 在本节中，本文大致介绍了一些目前在聚类研究中出现的著名的算法。 聚类算法大体上可分为基于划分的方法、基于层次的方法、基于密度的方法、 基于网格的方法、基于模型的方法。其中，基于密度的聚类算法能发现任意 形状、大小的聚类，基于网格的聚类算法具有高效率等优点而使它们受到很 大的关注。 2 4 1 划分方法 给定一个n 个对象或元组的数据集，划分方法构建数据的k 个划分，每 个划分表示一个聚类，并且k - - n 。也就是说，它将数据划分为k 个组，同时 满足如下要求：( 1 ) 每个组至少包含一个对象：( 2 ) 每个对象必须属于且只属于 一个组。 哈尔滨工程大学硕士学位论文 该类算法的具体思路为：给定k ，即要构建的划分数目，首先创建一个 初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间的移动 来改进划分。一个好的划分的一般准则是：在同一类的对象之间的距离尽可 能小，而不同类的对象之间的距离尽可能大。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际 上，绝大多数应用采用以下两个比较流行的启发式算法：( 1 ) k - m e a n s 算法( k - 平均算法) ，该算法中，每个簇用该簇中对象的平均值来表示。( 2 ) k m e d o i d s 算法( 1 ( 中心点算法) ，在该算法中，每个簇用接近聚类中心的一个对象来表示。 这些启发式聚类方法很适合在中小规模的数据集中发现球状簇。为了对大规 模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一 步的扩展。 k m e a n s 是一种基于质心的技术。处理大数据集时，该算法是相对可伸 缩的和高效率的，且算法经常以局部最优结束。但是，该算法不适合于发现 非凸面形状的簇，或者大小差别很大的簇。而且，它对于噪声或离群点数据 是敏感的，即使少量的噪声数据也会对平均值产生极大的影响。 k - m e a n s 方法有很多变种。它们可能在初始k 个平均值的选择、相异度 的计算、计算聚类平均值的策略上有所不同。如k m o d e s ，k - m e d o i d s ，e m ， 二分k m e a n s 等。 k m o d e s 用模式来代替类的平均值，采用新的相异度来度量分类性质的 数据，采用基于频率的方法来修改聚类模式。e m ( e x c e p t i o nm a x i m i z a t i o n ) 算法以一种方式对k m e a n s 方法进行了扩展。它不把对象分给一个确定的簇， 而是根据对象与簇之间的隶属关系发生的概率来分派对象。k m e d o i d s 选用簇 中位置最中心的对象代替簇中对象的平均值，降低k - m e a n s 对噪声的敏感度。 p a m ( p a r t i t i o n i n ga r o u n dm e d o i d ) 是最早提出的k o m e d o i d s 之一，它选用 簇中位置最靠近中心的对象作为代表对象( 中心点) ，然后反复用非代表对象 ( 非中心点) 代替中心点，直到找到最合适的中心点。p a m 算法有效地消除了 对离群点数据的敏感性，比k - m e a n s 方法更健壮，不易受极端数据的影响。 但是，p a m 只对小数据集非常有效( 如1 0 0 个对象聚成5 类) ，对大数据集效 率并不高。 c l a r a ( c l u s t e rl a r g e r a p p l i c a t i o n ) ，也是基于k - m e d o i d s 类型的算法， 1 4 哈尔滨工程大学硕士学位论文 是对p a m 的改进，c l a r a 算法的思想就是用实际数据的抽样来代替整个数 据，然后再在这些抽样的数据上利用k - m e d o i d s 算法得到最佳的m e d o i d s ，能 处理较大的数据集合。其复杂度是o ( k s 2 + k ( n 。k ) ) ，其中s 是样本大小。 c l a r a n s 是c l a r a 算法的一个改进算法，c l a r a n 的主要思想是：不 考虑整个数据集合，选择实际数据的一小部分作为数据的样本，然后用p a m 方法从样本中选取中心点。两者的区别在于：c l a r a 在搜索的每个阶段有 _ 固定的样本，而c l a r a n s 则是随机地抽取样本。c l a r a n s 算法的计算 复杂度大约是o ( n 2 ) 。n 是对象的数目。该算法的优点是能处理更大的数据集 合，能探测离群点。缺点是计算复杂度较大，且其聚类质量取决于所用的抽 样方法。 2 4 2 层次方法 一般来说，有两种类型的层次聚类方法： 一是凝聚的层次聚类。这种自底向上的策略首先将每个对象作为一个簇， 然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者 某个终结条件被满足。绝大多数层次聚类属于这种方法，它们只是在簇间相 似度的定义上有所不同。 二是分裂的层次聚类。这种自顶向下的策略与凝聚层次聚类不同，它首 先将全部对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象 自成一簇或达到了某个终结条件，如达到了某个希望的簇数目，或者两个最 近的簇之间的距离超过了某个阈值。 层次方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤 销。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价 会较小。但是该技术的一个主要问题是它不能更正错误的决定。有两种方法 可以改进层次聚类的结果：( 1 ) 在每层划分中，仔细分析对象间的关联。( 2 ) 综合层次凝聚和迭代的重定位方法。 基于层次聚类的方法有：c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e - 利用代表 点聚类) 、b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s 利用层次方法的平衡迭代约减和聚类) 、c h a m e l e o n ( 利用动态模型的层次聚类) 等。 哈尔滨工程大学硕士学位论文 b i r c h 口纠算法是一个综合的层次聚类方法。其主要思想是：扫描数据库， 建立一个初始存放于内存中的c f 树，然后采用某个聚类算法对c f 树的叶 子结点进行聚类。算法的计算复杂度为o ( n ) 。该算法通过聚类特征可以方便 地进行中心、半径、直径及类内、类间距离的运算。算法具有对对象数目的 线性伸缩性，及良好的聚类质量。但由于受c f 树节点大小的限制，c f 树节 点并不总对应于用户认为的一个自然聚类。而且，如果簇不是球形，b i r c h 算法不能很好地工作。 c u r e 刚算法选择基于质心和基于代表对象方法之间的中间策略。该算 法主要思想是：首先把每个数据点看成一簇，然后再以一个特定的收缩因子 向中心“收缩”它们，即合并两个距离最近的代表点的簇。c u r e 的复杂度 是o ( n ) ，n 是对象的数目。c u r e 算法的优点是对离群点的处理更加健壮，而 且可以识别非球形和大小变化较大的簇，对于大型数据库具有良好的伸缩性。 缺点是参数设置对聚类结果有显著影响，不能处