（模式识别与智能系统专业论文）基于ais的分类算法研究.pdf

硕士论文 基于 i s 的分类算法研究 摘要 目前，a i s 作为计算智能研究的一个崭新分支，已在数据挖掘、机器学习、 自动控制、故障诊断等诸多领域显示出强大的信息处理和问题求解能力以及广阔 的研究前景。而采用a i s 模型来完成数据挖掘任务的研究目前主要集中在数据聚 类分析、数据浓缩，分类任务等方面。 本文的工作吸收了来自人工免疫系统中的免疫识别的灵感，给出了一种基于 a i s 的数据挖掘分类算法。该算法的问题表示采用了二进制的位串编码方式，把 从问题空间提取的属性当做基因对待属性间特定的组合就形成了染色体算法 的主要特点就是多次使用了阴性选择机制来充当过滤器。该算法先从预先选定的 一类样本中生成规则集，在这过程中使用了阴性选择算子淘汰了一部分能够发生 免疫识别的个体，然后通过引入了阴性选择算子的遗传算法加以进化，输出最终 的规则集，最后使用了一组u c i 数据库中的数据完成了算法的仿真实验，实验的 结果表明该算法具备较好的分类性能。 关键 司：数据挖掘，分类算法，人工免疫系统，阴性选择算子 堡主堡苎 苎兰! ! ! 燮墨鲨里丝 a b s t r a c t c u r r e n t l y ，a i s h a sb e e nan e wb r a n c hi n t h ef i e l do fc o m p u t i n g i n t e l l i g e n c e ，w h i c h h a s a l r e a d y s h o w nap o w e r f u lc a p a b i l i t y i nt h e i n f o r m a t i o np r o c e s sa n dp r o b l e ms o l u t i o n s ，s u c ha sd a t am i n i n g ，m a c h i n e l e a r n i n g ，a u t o m a t i cc o n t r o la n df a u l td i a g n o s i s t h er e s e a r c h e sb a s e d 0 1 3 a i si nt h ef i e l do fd a t am i n i n gw e r ep u te m p h a s e so nd a t ac l u s t e r i n g ，d a t a c o n c e n t r a t i n ga n dc l a s s i f i c a t i o n t h i sp a p e rd r a w so nt h ei n s p i r a t i o no f a r t i f i c i a l i m m u n e s y s t ，e ma n d b r i n g sf o r w a r dan e wc l a s s i f i c a t i o na l g o r i t h mb a s e do na i s t h ea l g o r i t h m u s et h eb i n a r ys t r i n ga st h ep r o b l e mp r e s e n t a t i o na n dt a k et h ea t t r i b u t e o ft h ep r o b l e ms p a c ea st h eg e n e t h es p e c i a lc o m b i n a t i o no ft h ea t t r i b u t e m a k e su po ft h ec h r o m o s o m e t h ec h a r a c t e r i s t i co ft h ea l g o r i t h mi su s i n g t h en e g a t i r es e l e c t i o nm e c h a n i s ma st h ef i l t e r a tf i r s tt h er u l es e tc o m e s f r o mt h es a m p l e s ，a n dt h e nt h en e g a t i v eo p e r a t o r sa r eu s e dt oe l i m i n a t e ap a r to fr u l e sw h i c hc o u l dm a k et h ei m m u n er e c o g n i t i o n a f t e rt h a tt h e r u l es e ti se v o l v e db yt h eg e n e t i ca l g o r i t h mw i t ht h en e g a t i v eo p e r a t o r s a tl a s tt h ef i n a lr u les e ti sg o t w eu s eag r o u po fd a t af r o mt h eu c i d a t a b a s ef o re x p e r i m e n t s t h er e s u l t so ft h ee x p e r i m e n t ss h o wt h a tt h e ，一 a l g o r i t h mh a sag o o dc l a s s i f i c a t i o nc a p a b i l i t y k e y w o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o na l g o r i t h m s ，a r t i f i c i a li m m u n i t y s y s t e m , ，n e g a t i v es e l e c t i o na l g o r i t h m 、7 i i y 6 2 4 3 13 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：陛呈 。4 年6 月 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：强：墓叼4 年占月j 日 塑圭堡塞 蒸王! 竖堕坌茎竺塑 第一章绪论 1 1 数据挖掘的产生背景 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的 数据量急剧增大。在大量的数据背后隐藏着许多重要的信息，但由于人们目前所 使用工具的局限性而无法将其挖掘出来，而这些重要信息可以很好地支持人们的 决策。数据库系统所能做到的只是对数据库中已有的数据进行存取，数据库只是 针对操作型数据处理而设计的，人们通过这些数据所获得的信息量仅仅是整个数 据库所包含的信息量的一部分。更重要的信息是隐藏在这些数据之后的关于这些 数据的整体特征的描述及对其发展趋势的预测，这些信息在决策生成的过程中具 有十分重要的参考价值。 在数据库技术飞速发展的同时人工智能领域的一个分支一一机器学习的研 究也取得很大进展。机器学习致力于研究建立能够根据经验，自我提高处理性能 的计算机程序。机器学习从不同学科中吸收概念，这些学科包括人工智能、概率 统计、心理学、哲学等，然后根据学习的不同模式提出学习的方法，如：实例学 习、观察和发现学习、神经网络和遗传算法等等。其中某些常用且较成熟的算法 已被人们运用于实际的应用系统及智能计算机的设计和实现中。 数据库管理系统存储的数据，用机器学习的方法来进行分析，挖掘大量数据 背后的知识，这两者的结合促成了数据库中的知识发现k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ) 的产生。实际上，数据库中的知识发现是一门交叉性学 科，涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、 高性能计算、专家系统等多个领域。从数据库中发现出来的知识可以用在信息管 理、过程控制、科学研究、决策支持等许多方面。1 9 8 9 年8 月在美国底特律召 开的第1 1 届国际人工智能联合会议的专题讨论会上首次出现k d d 这个术语。 随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行k d d 专题讨论会，汇集来自各个领域 的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、 知识运用等问题。随着参与人员的不断增多，k d d 国际会议发展成为年会。 有人把数据挖掘视为k d d 的同义词，有人把数据挖掘当做k d d 过程中的 一个步骤，认为k d d = 数据预处理+ 数据挖掘d m + 解释评价。无论是哪种说法都 可以看到数据挖掘d m ( d a t am i n i n g ) 的产生发展和k d d 是密切相关。d m 是目 前国际上数据库和信息决策领域的最前沿研究方向之一，引起了学术界和工业界 的广泛关注。一些国际上高级别的工业研究实验室，例如i b m a l m a d e n 和g t e ， 墅主兰塞 茎三! ! ! 塑坌鲞苎堕竺堕 众多的学术单位，例如u cb e r k e k e y ，都在这个领域开展了各种各样的研究计划a 研究的主要目标是发展有关的方法论、理论和工具，以支持从大量数据中提取有 用的和让人感兴趣的知识和模式。 1 2 国内外数据挖掘的发展状况 数据挖掘d m 的发展和k d d 的发展密切相关。k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上。1 9 9 5 年在加拿大召开了第 一届知识发现与数据挖掘国际学术会议，该会议是由1 9 8 9 至1 9 9 4 年举行的四次 k d d 国际研讨会 p s 8 9 p s 9 1 a ，f u 9 3 ，f u 9 4 1 发展起来的。数据挖掘的研究规模由 原来的专题讨论会发展到国际学术大会，入数由二三十入发展到到七八百人，研 究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略和技术的集成， 以及多种学科之间的相互渗透。 其他内容的专题会议也把数据挖掘d m 和知识发现k d 列为议题之一，成为 当前计算机科学界的一大热点。此外，数据库、人工智能、信息处理、知识工程、 统计学、机器学习等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊领先在1 9 9 3 年出版了k d d 技术专刊， 所发表的5 篇论文代表了当时k d d 研究的最新成果和动态，较全面地论述了 k d d 系统方法论、发现结果的评价、k d d 系统设计的逻辑方法，集中讨论了鉴 于数据库的动态性冗余、高噪声和不确定性、空值等问题，k d d 系统与其它传 统的机器学习、专家系统、人工神经网络、数理统计分析系统的联系和区别，以 及相应的基本对策。 不仅如此，在i n t e m e t 上也有不少k d d 电子出版物，其中以半月刊k d d n u g g e s t s 最为权威，k d d 是一个包含知识发现和数据挖掘有关信息的定期免费 的电子通信。关于订阅的信息，可在h t t p ：w w w k d n u g g e t s c o r n s u b s c r i b e h t m l 一找 到。目前，世界上比较有影响的典型数据挖掘系统有：s a s 公司的e n t e r p r i s e m i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i n e r 、s p s s 公司的 c 1 e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e 5 、 还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i h e r 、q u e s t 等。b ! ! p ；! 璺型：业! 她i n i 蛆2 盐：! 业网站提供了许多数据挖掘系统和工具的性 能测试报告。另份在线周刊为d s * f d s 代表决策支持) ，1 9 9 7 年1 0 月7 日开始 出版，可向d s t r i a l t g c c o r n 提出免费订阅申请。在网上，还有一个自由论坛 d m e m a i l c l u b ，通过电子邮件可相互讨论d m k d 的热点问题。而领导整个潮流 的d m k d 开发和研究中心，当数设在美国e m d e n 的i b m 公司开发部。 随着国外知识发现的兴起，我国也很快罪上了国际步伐。1 9 9 3 年国家自然 2 硕士论文 基于m s 的分类算法研究 科学基金首次支持对数据挖掘领域的项目研究。计算机世界报技术专题版于 1 9 9 5 年3 月发表了由中国电子设备系统工程公司研究所李德毅教授组织的k d d 专题；于1 9 9 5 年4 月发表了由中国科学院史忠植研究员组织的“机器学习、神 经网络”专题：于1 9 9 5 年1 2 月发表了由国防科技大学陈文伟教授组织的“机器 发现和机器学习”，对我国开展知识发现的研究起到了一定的推动作用”1 。目前， 国内的许多科研单位和高等院校竞相开展知识发现k d 的基础理论及其应用研 究。北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究； 北京大学也在开展对数据立方体代数的研究；华中理工大学、复旦大学、浙江大 学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采 算法的优化和改造；南京大学、四川i 联合大学和上海交通大学等单位探讨、研究 非结构化数据的知识发现以及w e b 数据挖掘【2 9 1 。 g a t t n e rg r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未来三到 五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和 数据挖掘列为未来五年内投资焦点的十大新兴技术前两位【2 9 1 。数据挖掘的热点 将集中于网站的数据挖掘( w e bs i t e d a t a m i n i n g ) 、生物信息或基因( b i o i n f o r r n a t i c s g e n o m i c s ) 的数据挖掘及文本的数据挖掘( t e x t u a lm i n i n g ) 。 1 3 本文的研究内容及结构安排 本文利用了人工免疫系统中的阴性选择算子来对数据挖掘分类算法进行改 进并对改进的算法加以详细的描述。本文的组织结构如下： 第一章绪论部分介绍了数据挖掘的产生背景和国内外对数据挖掘的研究状 况，以及本文的主要内容与结构安排。 第二章概要介绍了数据挖掘及相关技术。主要包括数据挖掘的定义、数据挖 掘的方法、数据挖掘的功能以及数据挖掘系统的结构和数据挖掘的步骤。最主要 是对已有的数据挖掘的分类算法进行介绍。 第三章概要介绍人工免疫系统a i s 的基本概念，包括a i s 的产生背景、a i s 的定义和一些常用术语、a i s 的仿生机理以及a i s 常用算法，其中详细介绍了阴 性选择算法。对a i s 在数据挖掘中的已有应用也做了一些说明。 第四章是基于a i s 的数据挖掘分类算法具体描述部分。本章详细介绍了改进 的分类算法，首先给出分类算法的一般步骤，然后对所分类的问题进行描述，其 次给出算法流程，随后对算法中的每一个过程都进行详细描述。最后给出总结， 分析算法的特点。 第五章对第四章给出的算法进行仿真实验。首先描述了所采用的数据来源及 实验环境，其次对所获得的数据进行预处理，给出离散化后的数据区问和分类规 硕士论文 基于m s 的分类算法研究 则实例，然后介绍实验过程、参数的选择，最后给出实验结果图表并对实验结果 进行分析。 在本文结束时给出了以后研究工作的方向。 硕士论文 基于a i s 的分类算法研究 第二章数据挖掘及相关技术 2 1 数据挖掘的相关概念 2 1 1 数据挖掘的定义和特点 数据挖掘d m ( d a t am i n i n g ) 是对数据库中的数据进行一定的处理，从大量的、 不完全的、有噪声的、模糊的、随机的数据中提取隐含的、事先未知的、但又是 潜在有用的信息和知识的过程。确切地讲，d m 是k d d 过程中的一个步骤，其处 理对象是大量的日常业务数据，它主要基于人工只能、机器学习、统计学等技术， 高度自动化地分析原有的海量数据，做出归纳的推理，从中采掘出潜在的模式， 预测未知的行为，提高信息的利用，改变“人们被数据淹没，同时却仍感到知识 饥渴”的资源浪费的局面。k d d 是数据库技术和机器学习两个学科的交叉学科， 由于k d d 使用的数据来自于实际的数据库，所要处理的数据量可能很大，因此 d m 中的学习算法的效率和可扩充性就尤为重要；此外，k d d 所处理的数据由于来 自于现实世界，数据的完整性、一致性和正确性都很难保证，因此数据预处理也 是很有必要的。 2 1 2 数据挖掘的方法 d m 的技术基础包括机器学习、人工智能和统计学。人工智能是以自动机为 手段，通过模拟人类宏观外显的思维行为，从而高效率地解决事实世界问题的科 学和技术。下面介绍数据挖掘和知识发现的几种常用方法。 1 人工翌丝回络血r 土i i i 酊n e u r a l n e t w o r k s ) 神经网络方法是模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础。 它主要有三种神经网络模型： ( 1 ) 前馈式网络。它以感知机、反向传播模型、函数型网络为代表，可用 于预测、模式识别等方面。 ( 2 ) 反馈式网络。它以h o p f i e l d 的离散模型和连续模型为代表，分别用 于联想记忆和优化计算。 ( 3 ) 自组织网络。它以a r t 模型、k o h o l o n 模型为代表，用于聚类分析等 方面。 神经网络的知识体现在网络连接的权值上是个分布式矩阵结构；神经网络 的学习体现在神经网络权值的逐步计算上包括反复迭代或累加计算。 互、遗传算法( g e n e t i ca l g o r i t h m s ) 硕士论文 基于a i s 的分类算法研究 遗传算法是模拟生物进化过程的算法，由三个基本算子( 或过程) 组成： ( 1 ) 选择( s e l e c t i o n ) 。即从一个旧种群( 父代) 选出生命力强的个体， 产生新的种群( 后代) 的过程。 ( 2 ) 交叉( c r o s s o v e r ) 。即对选择的两个不同的个体( 染色体) 的部分( 基 因) 进行交换，形成新个体的过程。 ( 3 ) 变异( m u t a t i o n ) 。即对某些个体的某些基因进行变异( 0 变1 ，或l 变0 ) ，形成新个体的过程。 这种遗传算法可起到产生优良后代的作用。这些后代需满足适应值，经过若 干代的遗传，将得到满足要求的后代。遗传算法已在优化计算和分类机器学习方 面发挥了显著作用。 3 决策树方法( d e c i s i o nt r e e s ) 决策树方法是利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信 息量的属性字段，建立决策树的一个结点，再根据该属性字段的不同取值建立树 的分支。在每个分支集中重复建立树的下层结点和分支的过程。国际上最早的、 也是最有影响的决策树方法是q u i u l a n 研究的i d 3 方法0 3 。 决策树方法在现有的数据挖掘产品中有较为广泛的应用，如b u s s i n e s s o b j e c t 公司在它的o l a p 产品中新增加的一个数据挖掘的模块b u s i n e s sm i n e r ， 其中就采用了一种称为g i n i 的决策数方法。 4 覆盖正例、排斥反例方法 该方法是利用覆盖所有正例、排斥所有反例的恩想来寻找规则。比较典型的 有m i c h a l s k i 的a q l l 方法、洪家荣改进a q l 5 方法，以及洪家荣的a e 5 方法。 a q 系列的核心算法是，在正例集中任选一个种子，到反例集中逐个比较， 对字段取值构成的选择子相容则舍去，相斥则保留。按此思想循环所有正例种子， 将得到正例集的规则。a e 系列方法是用扩张矩阵来完成的。 5 粗糙集( r o u g hs e t s ) 它将知识理解为对数据的划分，每一被划分的集合称为概念，主要思想是利 用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来近似刻划 处理。具体做法是在数据库中，将行元素看成对象，列元素是属性( 分为条件属 性和决策属性) 。等价关系r 定义为不同对象在某个( 或几个) 属性上取值相同， 这些满足等价关系的对象组成的集合称为该等价关系r 的等价类。条件属性上的 等价类e 与决策属性上的等价类y 之间有三种情况：下近似：y 包含e ；上 近似：y 和e 的交非空；无关：y 和e 的交为空。对下近似建立确定性规则， 对上近似建立不确定性规则( 含可信度) ，对无关情况不存在规则。 6 数据可视化( d a t a v i s u a l i z a t i o n ) 6 硕士论文 基于a i s 的分类算法研究 对大批数据进行展现也是数据挖掘的重要方面。就数据可视化系统本身而 言，由于数据量很大，很容易使分析人员面对数据不知所措，可视化工具可以通 过适当的图形来表示数据，并支持多维数据的可视化，为数据分析人员提供很好 的帮助。有些工具甚至提供动画功能，使用户可以“跨越”数据，观看到数据的 不同层次。该方法对揭示数据的状况、内在本质及规律性起到了很强的作用。 7 人工免疫系统模型( a r t i f i c i a li m m u n es y s t e m ) 目前，a i s 已发展成为计算智能研究的一个崭新的分支，在数据挖掘、机器 学习、自动控制、故障诊断等诸多领域，显示出a i s 强大的信息处理和问题求解 能力以及广阔的研究前景。目前，由于认识到a i s 在机器学习与数据挖掘等领域 潜在的应用前景，a i s 的研究得到了许多大学、研究机构和工业界的重视。英国 k e n t 大学的t i 咖i s “1 对基于a i s 的机器学习和数据挖掘技术进行了系统性的理 论研究，并开展了基于a i s 的大规模数据挖掘应用研究。作为计算智能的个崭 新分支a i s 已成为许多国际期刊的重要议题。 在数据挖掘和知识发现中应用的人工智能技术还有邻近搜索方法、规则推 理、模糊逻辑、公式发现等等。 2 1 3 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。数据挖掘的任务 一般可分为两类：描述和预测。描述性挖掘任务刻划数据的一般特性。预测性挖 掘任务是在当前数据上进行推断，用以预测。d 5 f 【所能发现的模式类型包括以下 四种( 根据i b m 的划分方法) ：关联分析( a s s o c i a t i o n s ) ：序列模式分析 ( s e q u e n t i a lp a t t e r n s ) ；分类分析( c l a s s i f i e r s ) ；聚类分析( c l u s t e r i n g ) 。 1 关联分析( a s s o c i a t i o n s ) 顾名思义，关联分析的目的就是为了挖掘出隐藏在数据间的相互关系。关联 分析就是给定一组i t e m 和一个记录集合，通过分析记录集合，推导出i t e m 间的 相关性。该模式侧重于确定数据中不同领域之间的联系，找出满足给定支持度 ( s u p p o r t ) 和置信度( c o n f i d e n c e ) 阈值的多个领域之间的依赖关系。挖掘关联 规则是指在数据库组中挖掘出具有这种形式的规则：由于某些事件的发生而引起 另外一些事件的发生。例如，同时包含a ，b ，c ，d e 的i t e m 占总的i t e m 的百分比 称为规则“由a ，b ，c 推出d ，e ”的支持度。“7 2 包含i t e ma ，b 的记录同时、 也包含i t e md 和e 。”其中百分比7 2 称为规则“包含i t e ma ，b 和c 的记录同 时也包含i t e md 和e ”的置信度，而a ，b ，c 则被称为d ，e 的对立面。 2 序列模式分析( s e q u e n t i a lp a t t e r n s ) 序列模式分析和关联分析法相似，其目的也是为了挖掘出数据之间的联系， 7 堕主堡茎 苎主! ! ! 盟坌耋苎塑 但序列模式分析的侧重点在于分析数据间的前后( 因果) 关系。序列模式分析在 关联分析中增加了时间属性。序列模式分析也可称为时序关联分析。如第一次购 买电脑的顾客中9 5 的人同时购买电脑应用软件，此为简单关联，也就是一般 的关联分析。股票“深发展”一上涨，则第二天金融股票上涨的可能性为8 5 ， 这就是时序关联。由于我们并不知道数据库中数据的关联是否存在精确的关联函 数，即使知道也是不确定的，因此生成的规则带有置信度，置信度级别度量了规 则的强度。 3 分类分析( c l a s s if i e r s ) 假定有组记录集合和一组标记( t a g ) ，所谓标记是指一组具有不同特征的 类别。分类分析时首先为每一个记录赋予一个标记，即按标记分类记录，然后检 查这些标定的记录，描述出这些记录的特征，然后再用这些分类的描述或模型来 对未知的新的数据进行分类。这种描述可能是显式的，例如一组规则定义：或者 是隐式的，例如一个数学模型或公式。利用它可以分类新记录，实际上它就是一 种模式。目前，已有很多种分类分析模型得到应用，其中的几种典型模型是线性 回归模型、决策树模型、基于规则模型和神经网络模型，贝叶斯信念网络模型。 举一个简单的例子，信用卡公司的数据库中保存着各持卡人的记录，并根据 信誉程度( 标记) ，将持卡人分作三类：优，良，中，一般，差。这一过成程实 际就是将持卡人记录标定为五类。分类分析法检查这些记录，然后给出一个对信 誉等级的显式描述；“信誉良的用户是指那些收入在2 5 0 0 0 以上，年龄在4 5 到 5 5 岁之间，居住在x y z 地区附近的人士”。 4 聚类分析( c l u s t e r i n g ) 聚类又称为无指导的分类( u n s u p e r v i s e dc l a s s i f i c a t i o n ) 。与分类分析法 不同聚类分析法的输入集是组未标定的记录，也就是说此时输入的记录还没 有进行任何分类。其目的是根据一定的规则，合理地划分记录集合，并用显式或 隐式的方法描述不同的类别。而所依据的这些规则是由聚类分析工具定义的。由 于聚类分析可以采用不同的算法，所以对于相同的记录集合可能有不同的划分。 可以看出，许多在分类分析法中适用的算法同样适用于聚类分析。聚类方法包括 统计方法、机器学习方法、神经网络方法和面向数据库的方法。 上述的四种分法摘自i b m d a t am i n i n g 版本1 3 o 白皮书。但基于同样 的基本技术，d a t a m a t l 0 n 白皮书将d m 的方法分为以下四种： ( 1 ) 预测模型( p r e d i c t i v em o d e l i n g ) 。在d m 中是归纳推理。可以有多种 算法实现，包括人工神经网络，规则推理等。 ( 2 ) 数据库分段( d a t a b a s es e g m e n t a t i o n ) 。将数据库中的数据自动地分 类，包括分类分析和聚类分析。 硕士论义 基于 i s 的分类算法研究 ( 3 ) 联系分析( l i n ka n a l y s i s ) 。确定数据间的相互关系，包括关联分析 和序列分析。 ( 4 ) 偏差检测( d e v i a t i o ns e g m e n t a t i o n ) 。检测并解释数据分类的偏差一 为什么有些记录不能归入段( s e g m e n t a t i o i l ) 中。 与i b m 自皮书对蹦方法的分类相比，d a t a m a t i o n 白皮书的分类层次更高， 例如数据库分段和联系分析涵盖了分类分析法、聚类分析法、关联分析和序列分 析法，而预测模型在i b m 白皮书中所列的四种方法中都包含了，只不过在 d a t a 凇t i o n 白皮书中被特别提出来了。两种分类法最大的差异在于偏差检测， 这是i b m 白皮书中没有列出来的。 2 2 数据挖掘结构和步骤 2 2 1 数据挖掘系统的结构 如上所述，d m 的核心技术是人工智能、机器学习、统计等，但一个d m 系统 不是多项技术的简单组合，丽是一个完整的整体。它还需要其他辅助技术的支持， 才能完成数据采集、预处理、数据分析、结果表述这一系列任务，最后将分析结 果呈现在用户面前。根据功能，整个d m 系统可以大致划分为三级结构，如下图 图2 2 11 d m 系统的三层结构 9 2 2 2 数据挖掘系统的步骤 1 准备( p r e p a r a t i o n ) 本阶段主要完成数据预处理，包括数据清理，数据集成，数据选择和数据变 换。 2 挖掘( m i n i n g ) 数据挖掘器( d a t am i n i n gp r o c e s s o r ) 综合利用前面提到的四种数据挖掘 方法分析数据库中的数据。 3 表述( p r e s e n t a t i o n ) 数据挖掘将获取的信息以便于用户理解和观察的方式反映给用户，这时可以 利用可视化工具。由于用户要求的不同，d m 分析的数据的范围会有所不同，例 如分析一年内或三个月内的销售情况，再例如分析东部地区或西部地区的销售情 况，这样的d m 系统会得出不同的结论。这些基于不同数据集合的分析结果除了 通过可视化工具提供给用户外还可以存储在知识库中，供日后进一步分析和比 较。 4 评价( a s s e s s ) 如果分析人员对分析结果不满意，可以递归地执行上述三个过程，直到满意 为止。 2 3 分类算法的简介和分析 数据挖掘中的分类方法是根据给出数据集的特点构造分类器，利用分类器对 已知类别的样本进行分类的一种技术。按各种分类算法的技术特点，可将分类 算法分为决策树方法、基于统计概率、基于关联规则、基于数据库技术、基于支 持向量机等几类来叙述。 2 3 1 决策树分类 决策树学习算法包括如i d 3 算法( c 4 5 ) 、s l i q ( s u p e r v i s e dl e a r n i n gi nq u e s t ) 算法。i d 3 算法通过把实例从根节点排列到某个叶子节点来对实例进行分类，叶 子节点即为实例所属的分类。树上的每个节点说明了对实例某个属性的测试，且 该节点后的每个后继分支对应该属性的一个可能值。分类从根节点开始，对所有 的实例通过所选属性进行分割，属性的选择采用最高信息增益( i n f o r m a t i o ng a i n ) 法，停止分割的条件是或者没有属性可以再对实例进行分割或者节点上的实例都 属于同一目标属性类别。 下面简单描述一下i d 3 算法。 堡主丝兰茎! 望! 堑塑塑塑塑翌 i d 3 ( e x a m p l e s ，t - a t t r i b u t e ，a t t r i b u t e ) 创建树r o o t 节点 如果所有实例( e x a m p l e s ) 都为正。则返回l a b e l = + 的单节点树r o o t 如果所有实例( e x a m p l e s ) 都为负，则返回l a b e l = 一的单节点树r o o t 如果属性( a t t r i b u t e ) 为空，则返回单节点树r o o t ，l a b e l = 实例中 最普遍的目标属性值( t a t t r i b u t e ) 否则开始 ( 1 ) 用最高信息增益选出分类实例最好的属性a ( 2 ) 把a 赋给r o o t ( 3 ) 对于a 的每个可能值v ( i ) 在r o o t 下加一个新分支，测试a = v ( 2 ) 令e x a m p l e ，为实例中满足a 属性值为v 。的子集 ( 3 ) 若e x a m p l e ，。为空，在这个新分支下加一个叶子节点，该节点的 l a b e l = 实例中最普遍的t - a t t r i b u t e 值；否则在新分支下加 一个子树i d 3 ( e x a m p l e 。t a t t r i b u t e ，a t t r i b u t e 一 a ) ) 结束返回r o o t i d 3 算法的核心是如何选取树的每个节点的测试属性。期望所选择的属性最 有助于分类。一般采用最高信息增益法来进行选取。 过度拟合( o v e r f i t ) 训练样例是学习中的重要问题。所谓过度拟合指在假 设空间h 上，存在两个假设h 和h ，在训练集上h 错误率小于h ，但在整体 分布上h 错误率小于h ，则称假设h 过度拟合训练数据。出现这种情况很可能 是由于训练样例存在随机错误或噪声导致，也可能是选择的训练样例过于集中， 缺乏共性。在i d 3 算法派生出的c 4 5 算法中采用规则后修剪来避免过度拟合。 i d 3 、c 4 5 这类算法优点是产生的分类规则易于理解。决策树上每个分支对应一 个分类规则，可以得到一个容易理解的规则集，且算法速度相对统计算法较快。 该算法的缺点是只适用驻留内存的数据集使用，该算法受限于对大量的数据集进 行分类。且在决策树构造过程中需要多次顺序扫描和排序，导致低效。 s l i q 算法对c 4 5 算法进行了改进。在决策树构造过程中采用预排序和广度 优先的技术。s l i q 算法中用g i n i 指标( g i n ii n d e x ) 代替最高信息增益 ( i n f o r m a t i o ng a i n ) 对属性进行选择。g i n i 越小，信息增益越大。s l i q 算法 比c 4 ，5 算法能处理更大的数据集，在一定程度上有良好的随记录个数和属性个 数增长的可扩性。但s l i q 算法依然存在缺点，由于类另, j y 0 表存放内存，算法在 一定程度上限制了可处理的数据集大小。并且采用预排序技术的复杂度本身并不 与记录个数成线性关系，因此随记录数目增长的可扩性有限。 硕士论文 基于a i s 的分类算法研究 2 3 2 贝叶斯分类 贝叶斯分类算法是利用概率统计知识进行分类的分类算法，因此如何获得概 率的初始知识是该算法进行分类的一个难点。这类算法利用贝叶斯定理来计算未 知类别样本所属类别的可能性。贝叶斯定理成立依赖很强的独立性假设前提。因 此属性之间的独立性是分类准确与否的另一个难点重点。同时确定贝叶斯最优假 设的计算代价比较大( 与候选假设数量成线性关系) 。 贝叶斯学习算法的特点有 观察到的每个训练实例样本可以增量的降低或升高某个假设的估计概率。 先验知识可以与实例样本数据一起决定假设的最终概率。 贝叶斯方法允许假设做出不确定性的预测( 假定某天下雨的概率9 5 ) 。 新的实例分类可由多个假设一起预测，用它们的概率来加权。 在贝叶斯分类算法中常用朴素贝叶斯分类算法，t a n 算法( t r e ea u g m e n t e d b a y e sn e t w o r k ) 。 采用朴素贝叶斯进行分类时，实例中的每个数据样本都表示成n 维特征向量 x = x 1 ，x 2 ，x 3 x 。) ，每一维的向量x 。都代表样本的一个属性值，假定所有样本 实例分成m 类c i ，c 2 ，c 3 c 。 对于样本实例x 属于类c 。的条件是当且仅当p ( g i x ) p ( c j f x ) ，这里j 【1 , m 】 且j i 。由贝叶斯定理可知p ( c 。i x ) _ p ( x l c ) p ( c 0 p ( x ) ，由于p ( x ) 对于所有类都是 常数，只需求得最大的p ( x i c i ) p ( c i ) ，则样本实例即属于c 。类别。p ( c 。) 值明显可 知，只需求得v ( x i c o ，在计算p ( x c i ) 时假设各属性相互独立( 前提对属性值预 处理，离散化属性值) ，则p ( x c i ) 可用下面公式2 1 求得 p ( x i c i ) 2 兀p ( x k ic i ) k = t 在朴素贝叶斯学习算法中一般用出现频度代替概率，则可知道概率的初始知 识，即可进行分类。由上述公式可以知道朴素贝叶斯算法分类的准确度取决于属 性之间的独立性，独立性好的准确度高。否则偏低。另外和决策树相比，朴素贝 叶斯没有分类规则输出。 由于贝叶斯算法中很依赖属性相互之间的独立性，为了降低独立性假设，有 t a n 算法被提出。t a n 算法通过发现属性间的关联来降低朴素贝叶斯中任意属 性间独立的假设。t a n 在朴素贝叶斯网络结构基础上增加属性对之间的关联边 来实现。由于t a n 算法考虑了两两属性的关联性，该算法对属性间的独立性假 设有一定程度的降低，但是可能存在的其他方面的关联性并未涉及，因此适用范 围有限。 1 2 2 3 3 基于关联规则分类 c b a 算法( c l a s s i f i c a t i o nb a s e d o aa s s o c i a t i o n ) 是基于关联规则的分 类算法。在构造分类器时分两步。第一步：发现所有的右部为类别的类别关联规 则( c l a s s i f i c a t i o na s s o c i a t i o nr u l e s 即c a r ) 。第二步：从c a r 中选择高优 先度的规则覆盖数据集。关联规则发现采用经典算法a p r i o r i ，常采用的最小支 持度为0 ，此时可能会使产生的关联规则占满内存，无法发挥其优化作用。但同 时这也成为该算法的优点：分类准确度较高。因为采用最小支持度为0 可使所发 现的规则相对全面。 l b ( l a r g eb a y e s ) 算法是综合了概率统计和关联规则的知识而提出的分类 算法。在算法训练阶段采用a p r i o r i 来找到所有频繁且有意义的项集，存放频繁 集中。对需分类的样本a 从频繁集中找到包含于a 中的最长项集，计算a 属于各 类别的概率，选用概率最大的类别分类。该算法相比其他的分类算法准确度更佳， 但该算法存在与贝叶斯和c b a 算法相同的缺点。 2 3 4 基于数据库技术分类 在分类算法中利用数据库技术解决分类问题的算法目前有m i n d “”和g a c - - r d b m l 两类。 m i n d ( m i n i n gi nd a t a b a s e ) 算法是采用数据库中用户定义的函数u d f ( u s e r d e f i n e df u n c t i o n ) 发现分类规则的算法。m i n d 采用典型的决策树构造方法构 造分类器，具体步骤同s l i q 类似。其主要区别在于它采用数据库提供的u d f 方 法和s q l 语句来实现树的构造。简要的说就是在树的每一层，为每一个属性建立 一个维表，存放各属性的每个取值属于各个类别的个数以及所属的结点编号。根 据这些信息可以为当前结点计算每种属性的g i n ii n d e x 值，选出最优的属性， 然后据此对结点进行分裂，修改维表中结点编号列的值。上述过程中，对维表的 创建和修改需要进行多次。若用s q l 实现，耗时太多，因此采用u d f 实现。而 用于分类的属性的寻找过程则通过创建若干表和视图，利用连接查询来实现“”。 在决策树的构造过程中，最费时的操作是对每个非终端结点的数据集进行类别分 布信息的统计计算以及对数据集进行分裂。这两种操作在m i n d 算法中都是通过 u d f 实现的。 m i n d 算法的优点是通过采用u d f 实现决策树的构造过程使得分类算法易于 与数据库系统集成。缺点是算法采用u d f 完成主要的计算任务，而u d f 一般由用 户用高级语言实现，无法使用数据库系统提供的查询处理机制，无法利用查询优 化方法，且u d f 的编写和维护相当复杂。另外m i n d 中用s o l 语句实现的那部分 硕士论文 基于a i s 的分类算法研究 功能本身就是比较简单的操作，而采用s o l 的实现方法却相当复杂。 g a c r d b 算法是一种利用s q l 语句实现的分类算法m 1 。g a c - - r d b 算法采用一 种基于分组记数的方法统计训练集中各种属性取值组合的类别分布信息，通过最 小置信度和最小支持度两个阈值找出有意义的分类规则。该算法使用关系数据库 系统提供的聚集运算功能，利用s q l 语句完成主要的计算任务。在该算法中，首 先利用s o l 语句计算出用每个属性进行类别判定的信息含量，从而选择一个最好 的分裂属性，并且按照信息含量的大小对属性进行排序。接着循环地进行属性的 选择、候选分类表的生成、剪裁以及分类误差的计算，直到满足结束条件为止， 如满足壤小误差闽值或误差没有改善则结束。 g a c r d b 算法具有如下优点： 该算法将传统的一次一个样本的处理方式改变为面向集合的关系处理模式。 使得算法具有与其他分类器相同的分类准确度，且执行速度有较大