（计算机软件与理论专业论文）粗糙集中基于nbc聚类的连续属性离散化方法研究.pdf

摘要 摘要 连续属性的离散化一般是做为机器学习、数据挖掘的一项重要的预处理步骤， 针对离散化问题，研究者们提出了诸多方法，例如早期的等宽等频算法及后来的利 用遗传算法进行离散化等。根据离散化过程中是否应用了类别信息，把离散化算法 分为监督的离散化算法和非监督的离散化算法。 本文首先介绍了连续属性离散化的评价标准、几种经典的离散化方法及粗糙集 的相关知识；其次着重介绍了n b c 聚类算法的算法思想及及基本概念，并结合粗 糙集理论，提出了一种基于n b c 的离散化算法a d b n b c ( a l g o r i t h mf o rd i s c r e t i z a t i o n o f c o n t i n u o u s a t t r i b u t e sb a s e do n n b cc l u s t e r i n g ) 。最后本文对不同的离散化方法进 行实验比较和分析，通过比较实验说明了该算法的有效性。 关键词连续属性离散化属性重要度信息熵 聚类 a b s t r a c t a b s t r a c t d i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e si sa ni m p o r t a n tp r e p r o c e s s i n gi nm a c h i n e l e a n i n ga n dd a t am i n i n g ，r e s e a r c h e r sp r o p o s em a n ya l g o r i t h m sa b o u tt h ed i s c r e t i z a t i o n p r o b l e m ，f o re x a m p l e ，e q u a l w i d t h - i n t e r v a l sa l g o r i t h ma n de q u a l f r e q u e n c y - i n t e r v a l s a l g o r i t h mi ne a r l yt i m ea n dd i s c r e t i z a t i o na l g o r i t h mb a s e do ng aa n ds oo ni np r e s e n t d i s c r e t i z a t i o na l g o r i t h m sc a nb ec l a s s i f i e di n t os u p e r v i s e da n du n s u p e r v i s e da l g o r i t h m s a c c o r d i n gt ow h e t h e rc o n s i d e r i n gc l a s si n f o r m a t i o ni nd i s c r e t i z a t i o np r o c e s s i nt h i s p a p e r , f i r s t l y , e v a l u a t i o nc r i t e r i a o fd i s c r e t i z a t i o n ，s e v e r a lc l a s s i c a l d i s c r e t i z a t i o na l g o r i t h m sa n dr si s i n t r o d u c e d ；s e c o n d l nt h ea l g o r i t h mt h o u g h ta n d b a s i cc o n c e p ta b o u tn b c ( n e i g h b o r h o o d - b a s e dc l u s t e r i n g ) i si n t r o d u c e d ，an e w a l g o r i t h ma d b n b c ( a l g o r i t h mf o rd i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e sb a s e do n n b cc l u s t e r i n g ) i sp r o p o s e da n da p p l yi ti n t or o u g hs e tt h e o r y ；a tl a s t ，c o m p a r i s o n e x p e r i m e n t sh a v eb e e nd o n ea b o u td i f f e r e n td i s c r e t i z a t i o na l g o r i t h m si nt h ee n do ft h e p a p e r , t h er e s u l to ft h ee x p e r i m e n t ss h o w st h ea l g o r i t h mi se f f e c t i v e k e y w o r d sc o n t i n u o u sa t t r i b u t e s d i s c r e t i z a t i o n s i g n i f i c a n c eo fa t t r i b u t e s e n t r o p yo fi n f o r m a t i o nc l u s t e r i n g 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：蠢霞嘘 日期：丛学年上月j 红日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密订。 ( 请在以上相应方格内打“4 ) 保护知识产权声明 本人为申请河北大学学位所提交的题目为雅圜莲瓢苦蜘b 鼹j 蚕i ；瘟锄粤毒 的学位溅是我个人蜊币四熙凰指导并荆币靡僦果， 。 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人：绰爱l 日期：业乒月丘日 作者签名：羞避 导师签名： 日期：垡挚年l 月生日 日期：麟年l 月丘日 i 第1 章绪论 第1 章绪论 1 1 研究背景 连续属性通常被称为实数的、有序的或数值的属性，它表示了对象的可测量值，而 离散属性又称为是类别的、符号的，或名称的属性，也就是用少量的离散值来表示信息 系统中某一属性的一段取值或某特征的取值，例如大小、颜色、形状等，连续的属性 值取自一段连续的区间，属性值之间没有明显的分割特征，是“杂乱的”，但是将这些 连续的属性值根据某些方法可转化为不就交的子区间，每个子区间用一个整数表示，这 一过程就称为连续属性的离散化。 连续属性的离散化是机器学习、数据挖掘的重要预处理步骤，离散化的好坏直接关 系到数据挖掘或机器学习的效果，但在数据挖掘和机器学习的过程中，遇到的数据往往 又是连续的，而大多数算法却只能处理离散化的数值，这就要求必须对连续数据进行离 散化，因此，连续属性的离散化的处理技术就越来越受到人们的重视。 自从波兰数学家p a w l a k z 的粗糙集理论提出后，这个理论就成为进行数据挖掘的 一个很好的工具，但是该理论不能直接处理连续属性，而只能处理离散属性值，这样就 大大限制了粗糙集理论的应用，为了拓宽粗糙集理论的应用范围，使粗糙集理论能够处 理连续属性，也必须将连续的属性进行离散化处理。在实际的使用中，我们得到的数据 库中的数据往往是很多的，里面存储了大量的、看似毫无规律可言的数据，如果不对这 些数据进行简单化处理而是直接从数据中提取可用的信息，则消毫的时间和空间不言而 喻，只有将连续的属性数据进行离散简单化，才能够从这些含有连续属性的数据库中取 得较好的数据集，从而得到效果好且简洁的规则，从这一方面说，离散化的结果将会减 小数据存储对空间的占用，加快数据挖掘和机器学习算法的运行速度，减小算法的空间 开销，并且可以提高分类精度。 针对这个问题，目前己经出现了许多离散化算法，但找到一种通用的、效果好的离 散化问题则不是一件容易的事，有专家证明，连续属性的最优离散化是一个n p 难【1 4 】问 题，面对的数据不同，所适用的离散化方法也可能不同，因此，在实际应用中，对于不 同数据，选取不同的离散化方法也是非常重要的。 河北大学工学硕十学位论文 1 2 离散化算法的发展与现状 离散化研究初期，连续属性的离散化并没有引起足够重视，而只是被当作数据挖掘、 机器学习中的一种边缘性辅助工作。随着社会的不同需求，在现实中所涉及更多的是连 续的数值属性，而更多算法又只能处理离散值，例如机器学习、数据挖掘算法要求所处 理的属性是离散值，于是人们认识到，为了能够处理这些现实问题，必须对连续的数值 属性进行离散化处理，使其转变为离散属性。因此，离散化问题得到了较为广泛和深入 地研究，多种离散化算法被提了出来。 起初，人们提出的是一些简单的离散化算法，如等宽和等频【4 】算法，随后，人们还 提出了许多方法对这些方法进行改进，如针对数据库中数据集的无监督离散化，提出了 一种基于概率模型的离散化算法【2 3 1 ，这种算法采用了概率生成模型来描述区间，在这种 方法中，使用了贝叶斯信息准则来进行评价、比较各种概率生成的模型，观测值在相对 的区间中可以有不同程度的不确定性，这就为区间数目、位置、宽度的自动确定提供了 较为系统的方法。 研究者们对基于粗糙集模型的离散化方法也进行了相应的研究，并且取得了一定的 研究成果，这些成果一般可以分为两类：一类方法是把其它学科中的相应方法直接用来 对信息系统进行离散化，很少或者是完全不考虑粗集理论所特有的属性，这种做法的结 果往往是不能保证原有信息系统的分辨关系和分辩关系，典型代表是粗集工具软件 r o s e t t a 或r o s e 2 提供的离散化方法；而另一类方法却是充分考虑了粗集理论【l3 】的特殊 性，其结果能够很好地保持原有信息系统的分辨能力和分辨关系，应用较多的典型代表 是粗集理论中基于布尔【2 川逻辑的离散化方法。 二十世纪九十年代初期，连续属性的离散化开始受到机器学习领域关注，并把数学、 信息论和统计学等领域的研究成果加以溶和，与此同时，开始出现了基于信息熵的离散 化算法。例如，c h i u 、c h e u n g 和w o n g 等人在1 9 9 0 年提出了一种基于覆盖离散化空间 的最大化s h a n n o n 熵的层次化离散化算法 2 3 1 ，这种算法的思想是：在每个属性轴上，寻 找连续空间上合适的初始分区，然后再在详细的分区上反复的应用“h i l l c l i r n b”搜索mg 法以获得更好的分区。 在1 9 9 1 年，c a t l e t t 提出了把基于信息熵的离散化【碉方法应用于决策树领域，这种 离散化算法中，使用了信息熵增益大小、区间内对象个数等多个条件来防止每个属性分 第1 章绪论 区的递归形式。 在1 9 9 3 的，f a y y a d 和i r a n i 将递归信息熵最小限度启发式方法应用于离散化的处理 中，在这种算法中，信息熵的应用主要是用以控制连续空间中子区间产生的个数，这一 方法起初只是在树生成时应用于局部的每一个节点，随后几年这一方法便得到了广泛的 应用。 近年来出现的较常用的离散化算法还有很多，例如有基于遗传算法【2 1 1 ，1 2 1 的离散化 算法，基于断点重要性的离散化方法【1 1 ，基于信息熵的离散化算法，基于属性重要度的 离散化算法以及基于聚类的离散化方法【9 】等，总体上说，这些算法各有自己的优缺点， 分别适用于不同的数据集，还没有出现通用的离散经算法，因此，寻求新的离散化算法， 对这类算法进行进一步的研究仍然是至关重要的。 1 3 本文主要研究内容及结构 1 3 1 研究内容 ( 1 ) 介绍离散化算法的发展和现状。 ( 2 ) 对离散化算法进行了简单分类。 ( 3 ) 介绍几种经典的离散化算法，并对这些算法进行了简单的描述。 ( 4 ) 介绍了一种新的聚类方法郴c 聚类方法，并分析了这种方法的优缺点以及 利用该方法进行离散化的可行性。 ( 5 ) 把n b c 算法应用到连续属性的离散化中，提出了基于其的一种新离散化方法一 a d b n b c ( a l g o r i t h m f o rd i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e sb a s e do nn b c c l u s t e r i n g ) 算法，并进行了离散化实验，把它与部分离散化算法的结果进行了详细比较，分析了该 算法的时间复杂度，通过实验系统地展现了离散化算法的不同结果，并为不同环境使用 不同方法提供指导。 1 3 2 结构安排 本文的结构安排如下： 第一章，绪论。本章分析了连续属性离散化算法的研究，描述了离散化算法的发展 与现状，简要介绍了本文的研究内容及结构。 第二章，连续属性的离散化算法。本章首先说明了离散化算法的评价标准，并对目 前存在的离散化算法进行了简单划分，进而介绍了几种经典的离散化算法。 气 河北大学工学硕士学位论文 第三章，n b c 聚类算法介绍。本章主要介绍了本论文的关键技术n b c 聚类算法的 原理及基本概念。 第四章，a d b n b c 算法及离散化结果比较。本章在n b c 算法的基础上提出了一种 新的离散化方法( a d b n b c ) ，并把这种算法与部分离散化算法的实验结果进行了比较 分析。 第五章，总结。 第2 章连续属性的离散化算法 第2 章连续属性的离散化算法 从第一章可以看到，随着p a w l a k z 粗糙集理论的提出，连续属性的离散化处理也 随之变得至关重要，离散化处理使得信息系统在一定程度上实现了不同程度的简单化， 简化了规则的提取，达到了降低问题复杂度的目的。 2 1连续属性离散化问题描述 设信息系统s = ，u = 红。，x ：，吒 为所有对象的非空有限集合，c 是 条件属性集，d 是决策属性集。假设对于任意c c 的属性，均有形= b 力cr ，r 是 实数集，则e 为一连续属性。设9 是k 上的分割点集合，即： 9 = c o ，r ，f ，矽 则9 将k 分为置个区间( 如图2 2 1 ) ，这里e i = c ，o 一 f 矿= 厂，毛为分割 点数，用来表示离散化程度，也就是按属性q 将对象集合u 分成毛个类。 e = c ，o 一 f p = ，jijlv ， 图2 2 i 连续属性q 被分割点集q 分割成t 个区间 对于需要离散化的连续属性集c 互c ，其分割点集合记为： q = u c ) 尸= u ( c ，r ) ，c ，一) ，( c ，f ) ，( e ，t ) ) 0 q ” 将属性的连续取值映射到离散空间，即对于任意对象以u ( k = 1 ，2 ，川，如果其属 性e 的取值在区间【。，) ( ( 1 ，2 ，尼) ) 内，则将此对象的属性值记为j 。用这种方法就 可以把原来含有连续属性的样本数据集s 转换成离散化的数据集酽。 2 2 离散化算法优劣的评价标准 近年来，连续属性离散化处理的研究已逐渐趋向成熟，不同的离散化方法逐渐涌现， 但遗憾的是，连续属性的最优离散化问题是一个n p 难题。因此，对于现实中具有丰富 样本的信息系统来说，人们只可能尽最大努力获得一个次最优的离散化算法，即在保证 气 河北大学工学硕七学位论文 离散化结果性能要求的前提下，用尽可能少的断点将属性空间划分成尽可能少的子空 间，就成为了离散化算法所追求的目标。 评价一个离散化算法是否是成功的，可以从以下几点进行考察： ( 1 ) 离散化后的测试精度和训练精度 在离散化问题中，离散化结果的好坏，在很大程度上是通过离散化后的测试精度和 训练精度进行评价的。离散化的最终目标是处理所面临的连续属性问题，而这一问题处 理的好坏往往是通过实验结果的训练精度和测试精度加以说明，因此，精度是评价离散 化优劣的最重要标准之一。 ( 2 ) 离散化结果是否是最简单的 对于一个信息系统来说，对其进行离散化的结果可以有多种，一般来说，分割点个 数越少，产生出来的数据所生成的规则【l5 】就越简单，因此，在保持原有信息系统分辩能 力的前提下，应当选取其中最简单的离散化结果。 ( 3 ) 是否保持了原信息系统的一致性 具有连续属性的未进行处理的原数据集通常都是一致的，对一个数据集进行离散化 处理后，如果与原信息系统出现了不一致的结果，说明处理过程中丢失了一些重要的信 息，该离散化处理是不成功的，因此，离散化处理还应该保持原信息系统的一致性水平。 ( 4 ) 是否完全离散化 完全离散化【6 】就是指算法要能够对多个连续属性进行离散化处理。对于一个数据集 来说，在实际应用中需要对每个连续属性进行离散化，除非数据集只包含一个连续属性。 2 3 几种经典的离散化算法 研究人员从不同的领域提出了多种离散化方法，典型的有等区间方法、基于遗传算 法的离散化方法、基于聚类的离散化方法、基于信息熵的离散化方法、基于属性重要度 的离散化方法、统计分析方法、超平面搜索方法以及用户自定义区间等。根据是否使用 了决策属性，可以把离散化算法分为监督与非监督式方法。如图2 3 1 第2 章连续属性的离散化算法 图2 3 1 ( 1 ) 等宽的离散化方法 等宽和等频方法是最典型的无监督离散化方法。等宽分割是将连续属性的值域等分 成皇( 七，) 个区间，墨一般是由用户确定的。假设某个属性的最大属性值为m ，最小 属性值为n ，用户给定的分割点参数为k ，则 d i s p ( a r e a ) = ( 历一，2 ) 后 p。加t尼，=一nu+；d、is几p，。(，atre“a。习)矽。口rp口，i_1盱：二。，；k小于 其中d i s p ( a r e a ) 表示区间间隔大小，p o i n ( k , ) 表示第i 个分隔点 ( 2 ) 等频离散化方法 等频算法首先将该属性值从小到大进行排序，然后将属性值域分成若干个区间，每 河北大学工学硕士学位论文 个区间包含相同数量的属性值。假设对象个数为n ，分成的区间数为k ，则每个区间内 含有的对象个数为n k 。分隔点为： p o i n ( k ) = ( 口( 。) + 口( 。) ) 2 ，f k 其中a c ，p o i n ( k , ) 表示第i 个分隔点。 以上这两种方法最简单，但由于离散化过程不考虑属性之间的依赖关系、不考虑决 策属性对离散化过程的影响，使得离散化处理结果的质量缺少保障，一般不能得到满意 的结果。 在1 9 9 3 年由h o l t e 提出的1 r d ( o n er u l ed i s c r e t i z e r ) 方法对等频方法曾进行了改进， 1 r d 方法是一种全局的、静态的、有导师离散化方法，具体来说，这种方法首先是用贪 心算法将选定属性分成多个区间，每个区间至少包含m 个属性值，其中m 是用户事先 指定的参数，且绝大多数对象来自一个决策类，这些决策类是根据决策属性进行划分的。 在实际算法执行过程中，在初期先进行区间的初始化，使每个区间包含m 个属性值， 然后根据某一规则移动分割点，使主决策类对象增加、非主决策类对象减少，区间内对 象所属决策类尽可能单一。另外还有一些专家也对这种算法进行过改进，如c h i n g 等人 也提出了类依赖离散化算法【8 】对等区间和等信息量方法进行改进。以上这些方法的改进 概括起来主要由三部分构成：区间初始化、区间重构和区间约简。 ( 3 ) 统计试验方法 统计试验【2 3 1 分析方法是根据决策属性来分析区间划分之间的独立程度，从而来确 定分割点的有效性的方法，在这种算法中，区间的独立程度是一个很重要的参数，这种 算法的思想是： 对于任意分割点0 只( o ， 置) ，均可将i s , ，q ) 分成2 个区间丘= i s ，q ) 和r = ( 0 ，q ) ， 两区间的独立程度为： 序壹主掣 1 ，i j 一0 其中：z 2 表示两区间的独立程度，是决策类数目，e 表示第，区间中属于第，决 策类的对象数的期望值。r i l l 是在第，区间中属于第_ ，决策类的对象数。 e 的计算公式如下： 8 第2 章连续属性的离散化算法 ，2 一上1 _ 一! ! 一 一f 一厂一一 玎拥 k = lm = l 如果e = 0 ，贝0 取毛= o 1 基于统计试验的离散化方法是将z 值较大的分割点作为有效分割点，由于该方法利 用了决策类的信息，且面对的是某一个局部空间的数据，所以这种方法从总体上属于局 部的、监督的离散化方法。 ( 4 ) 基于信息熵的离散化方法 基于信息熵的离散化方法目前被研究得最为广泛。该方法的基本思想是应用类信息 熵作为分割点优劣的评价标准。由属性q 的分割点c je p , ( o 1n d f ( p ) = 1n d f ( p ) 1 ) 、 平均型点( n d f ( p ) = 1 ) 和稀疏型点( n d f ( p ) 1 ) 。 3 2 n b c 聚类算法( n e i g h b o r h o o d b a s e dc l u s t e r i n ga l g o r i t h m ) 的优点 与n b c 算法类似的有d b s c a n t 3 1 算法，这是一种基于密度的聚类算法的典型代表， d b s c a n 是利用全局性密度来进行的，与d b s c a n 相比，n b c 具有以下优点： 1 n b c 能自动找出任意分布形状的类，在同一数据库中，它也能找出不同局部密 度的聚类：然而d b s c a n 使用全局变量，不能从一个大的稀蔬的类中区分出小的、比 较临近的、稠密的类，从这方面来说，n b c 比d b s c a n 更有效。 2 、n b c 需要的仅仅是一个参数，而d b s c a n 需要三个参刻3 1 ，也就是说，n b c 需要更少的参数输入，因此，n b c 算法比d b s c a n 更简单方便。 3 、n b c 用基于信元的结构和v a 文件以组织目标数据，这就使它对于较大的、高 维数据库也十分有效。 3 3n b c 聚类算法步骤 n b c 是一种用于聚类的算法，核心概念是周边环境密度因子，利用该算法进行聚 类的过程p 1 如下： s t e p l ：计算所有点的n d f 值。 s t e p 2 ：在所有未分类的对象点中随机选择一个对象点。 s t e p 3 ：判断该对象的n d f 值，如果大于或等于l ，则产生一个新类，给p 点标上 相平应的类别，否则转s t e p 2 。 s t e p 4 ：找出p 的所有直接可达点，如果这些可达点的n d f 值大于或等于1 ，则给 这些点标上相应的类标，且放到一个队列中。 s t e p 5 ：如果队列非空，则从队列中取出第一个数a ，设置p = a ，转s t e p 4 。 s t e p 6 - 如果队列为空，则该类成功分离出来。 s t e p 7 ：从剩余的点中再随机选择一个点，转s t e p 3 。 第3 章n b c 聚类算法介绍 s t e p 8 ：当剩余点的n d f 值都小于1 时，聚类结束。 注：没有类别的点称为噪声点。 河北大学t 学硕+ 学位论文 第4 章a d b n b c 算法及离散化结果比较 第二章对目前存在的离散化算法进行简单的总结，第三章对n b c 算法进行了详细 的说明，本章将提出基于n b c 聚类的一种离散化算法a d b n b c 算法，并把这种算法与 其它常用离散化算法进行实验比较。 4 1a d b n b c 算法 把聚类算法应用到连续属性离散化中已成为诸多研究者的研究对象，本文提出了在 离散化问题中结合粗糙集理论应用n b c 聚类算法对连续数据进行离散化处理。由第三 章可知，在n b c 算法中需要输入一个参数k ，但参数的好坏需要一个评价标准，在粗 糙集理论中，对原信息系统的离散化结果要求生成的后继信息系统能够最大限度地保持 原信息系统对实例的分辨能力和分辨关系，因此根据粗糙集理论，把信息系统中决策属 性对条件属性集合的依赖度作为评价聚类结果的尺度。 基于n b c 算法的离散化过程大致如下：首先给定一个初始参数值( k ) ，利用该值 对信息系统中的实例进行聚类，然后根据相应的聚类结果对信息系统中的连续属性进行 离散化，计算离散化后信息系统决策属性对条件属性集合的依赖度，由于粗糙集理论的 离散化要求离散化后的新系统能够最大限度地保持原信息系统对实例的分辨能力和分 辨关系，那么如果聚类后决策属性对条件属性集合的依赖度小于原信息系统的依赖度， 则调整算法参数k ( 利用程序依次改变k 的取值) ，然后再利用上述算法对信息系统中 的实例重新进行聚类，如此反复调整算法的参数，直至最终得到的信息系统决策属性对 条件属性集合的依赖度满足所规定的要求。采用n b c 算法对信息系统中的实例进行聚 类，充分利用了决策属性对条件属性的依赖度，兼顾了属性之间的相关关系，并从整个 信息系统的角度加以考虑，因而这种算法是全局的，有监督的，利用这种方法离散化的 结果较为合理。 在根据聚类结果对连续属性进行离散化的基础上，还可以对离散化的结果进行进一 步的优化。优化方法如下，由基于n b c 聚类的算法进行离散化后，得到一个初始的离 散化结果，但这种离散化结果可能不是最简的，继续考察连续属性的相邻离散区间，如 果相邻两个离散区间的实例在决策属性上的取值相同，则将这两个相邻离散区间合并为 一个离散区间。由粗糙集理论的相关理论【l8 】可以证明，在决策信息系统中，如果某连续 第4 章a d b n b c 算法及离散化结果比较 属性的相邻离散区间所对应实例的决策属性相同，则将这两个区间合并后，决策属性对 于条件属性集合的依赖度并不发生变化，因此，这样的处理并不会降低信息系统的分辨 能力，反而进一步降低了断点的数目，我们把以上这种基于n b c 聚类的离散化方法叫 做a d b n b c ( a l g o r i t h mf o rd i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e sb a s e do nn b c c l u s t e r i n g ) 算法。 综上所述，基于n b c 聚类的连续属性离散化方法( a d b n b c ) 主要由两个部分构 成：第一步采用n b c 算法聚类，根据属性依赖度动态调整此算法参数k ，根据最终聚类 结果对连续属性进行离散化处理；第二步，合并具有相同决策属性值的相邻离散区间， 降低断点数目。具体算法可以描述如下： 输入：决策信息系统1 = ( u ，a ，v ，厂) 和参数k 。 输出：连续属性的离散化区间。 第一步：对所有属性的取值区间进行归一化处理。 第二步：算信息系统s 中决策属性对条件属性集合的依赖度： 以妒笔裟挚 第三步：据邻域内包含的最小实例个数k 对信息系统中的所有实例进行聚类。 第四步：根据聚类结果对连续属性进行离散化，得到离散化后的新信息系统。s ： 第五步：计算s 中决策属性对条件属性集合的依赖度。 第六步：对离散化前后信息系统的依赖度进行比较，如果 ，调整k 的大小，重新 对信息系统中的实例进行聚类，转入第三步。 第七步：对于每个连续属性a c ，逐个检查相邻的离散区间，如果两个相邻离散 区间对应实例的决策属性值都相同，则将其合并为一个离散区间。 第八步：输出所有连续属性的离散区间。 在此算法中，需要对参数k 进行调整，k 取值时，需要考虑整个数据空间对象的个 数，数值过大，聚类结果太粗糙，某些较特殊的类不能被被发现，数值过小，聚类的个 数太多，也失去了离散化的意义，在实验中我们发现，当k 取数字1 2 0 时，可以取 得较好的离散结果。因此，在聚类时，我们一般使得k 从1 开始循环，直到信息系统决 策属性对条件属性集的依赖度不小于原信息系统为止。 河北大学t 学硕士学位论文 4 2 实验设计 由于目前出现的离散化算法较多，我们不可能把每种算法都进行比较，在本文中， 我们仅选取了其中的一部分算法作为代表来进行实验比较。在这里我们选取了基于属性 重要度的离散化算法，基于遗传算法的离散化算法，先行后列算法、基于信息熵的连续 属性离散化算法以及基于n b c 聚类的连续属性离散化算法，这些算法均采用相同的运 行环境，编程语言采用v c 6 0 实现。 4 3 数据集的选择 实验的数据选取的是最常用的数据库，分别是g l a s s ，w i n e ，h e a r t ，i r i s 。这四个数 据集的一些基本信息如表4 3 1 所示。 表4 3 1 所选用的数据集信息 数据集样本个数连续属性个数决策类别数 g l a s s 2 1 496 w m e1 7 81 33 h e a r t2 7 01 32 m s1 5 0 4 3 由表4 3 1 可以看出，g l a s s 中包括6 个类、9 个连续属性和2 1 4 个对象，w i n e 中包括3 个类、1 3 个连续属性和1 7 8 个对象，h e a r t 包括2 个类、1 3 个连续属性和2 7 0 对象，i r i s 中 包括3 个类、4 个连续属性和1 5 0 个对象。 4 4 实验步骤 实验过程分为四个步骤： ( 1 ) 样本的划分。将所用到的四个数据库中的数据按7 ：3 的比例进行划分，7 0 的数 据作为训练样本，剩余3 0 的数据作为测试样本。 ( 2 ) 应用a d b n b c 及选取的离散化方法对训练样本进行离散化，得到断点集和离散 化后的训练样本。 2 n 第4 苹a d b n b c 算法及离散化结果比较 ( 3 ) n j i l 练样本的断点集对相应的测试样本进行离散化。 ( 4 ) 用相观方法从训练样本中获取规则。并对搠0 试样本进行规则测试，求得样本的i ) i l 练精度和测试精度。 表4 4 i 数据集划分信息 数据集样本个数训练样本数钡4 试样本数连续屈性个数 剖拈s 9 】7 81 2 55 3 1 3 h e a r t2 7 01 8 9 4 5 实验比较与分折 同时基于n b c 的离散化方法也分别在四个数据库上进行了实验，实验的部分运 行界面如下，在对不同的数据库进行离散化时，可以在程序中动态选择不同的数据库， 然后进行聚类，如图45 1 所示： 凹45 】 根据聚类结果，进行离散化，且可以查看离散化后的表的信息： 型些垒尘! 茎雪圭耋堡尘三 图4 52 数据库离散化化的结果可以动态在下一个窗口显示出来，其中包括各个属性分割点 的个数与分割点数值： 刚4 53 离散化后的表，运用精糙集的方法对之进行处理，提取规则，并对测试数据也进行相应 的处理，最后进行精度的计算： 至：耋：坚：墨鎏墨基墼些篷墨! ! 彗 最终结果如表4 51 和表4 5 2 ： 图4 54 表45 数据集g l a s s 断点数 1 3 6 a 训练精度( )8 87 测试精度( ) 5 99 8 829 1 4 断点数 b 训练精度( ) 7 3 】 删试精度( )9 28 断点数 训练精度( )8 769 25 测试精度( ) 断点数 1 26 训练精度( ) 7 07 s 819 45 测试精度( )8 789 】3 上表中“a ”代表支献 8 的先行后列法；b 代表文献 7 】中的基于属性重要性的 离散化算法；“c ”代表文献【11 的基于遗传算法的离散化算法；d 代表文献 6 】的基 于信息熵的离散化算法 河北大学1 二学硕七学位论文 表4 5 2n b c 离散化结果 k 断点数训练精度( 呦 测试精度( ) 数据集 82 77 4 27 0 8 g l a s s 1 03 69 0 19 0 7 w l n e 93 39 3 29 0 6 f l o w e r 8 1 1 9 6 49 4 6 m s a d b n b c 算法的时间复杂度分析。本算法的过程主要由两部分构成：利用n b c 算 法进行聚类，由参考文献 5 】可知，聚类的时间复杂度为o ( m n ) ；然后根据聚类结果对 原信息系统进行离散化，这部分的时间复杂度为d ( ) ，在本算法中，虽然k 的取值不 是一个固定的数，需要在程序中根据信息系统的依赖度进行调整，但在最坏的情况下， k 最大也是取整数，( k 的取值范围一般是1 - 2 0 ) 。由以上可得，整个算法的时间复杂 度为o ( m n ) 。 以上我们用实验比较分析了一些离散化算法，然而，在实际应用中要想选择一个合 适的离散化算法一般来说是比较困难的，不同的离散化算法对于不同的数据集效果可能 相差甚远，一个算法的选择主要依赖于用户的需要以及数据集的特点。在数据集方面， 如果所使用的数据集不带有类别信息，则会选择使用非监督的离散化方法，而带有类别 信息的数据集可以使用监督的离散化方法，这种方法得出的结果较为合理；在时间方面， 若对时间要求比较严格，可以使用基于属性重要性的离散化算法，这个算法运行时间较 短，但它是以测试精度的降低为代价的，如果对时间要求不是很严格，也可以使用其他 的离散化算法，如基于信息熵的算法等，这些算法通常能够得到较高的训练精度和测试 精度。 利用n b c 算法对连续的属性进行离散化，通过调整参数k 的值，在保存原有信息 系统分辩能力和分辨关系的同时，可以较成功地对连续的数据进行离散化，但所得到的 分割点数，比基于属性重要度的方法、基于信息熵的方法等得出的分割点多，这一点与 d b s c a n t 3 l 的算法有点类似，但训练精度和测试精度却有一定程度的上升，因此，如果 想得到较高的训练精度和测试精度，可以考虑使用这种方法。 2 4 第5 章总结 第5 章总结 目前数据挖掘、机器学习被深入广泛的研究，并已成功应用于诸多领域，但这些算法 多数要求所处理的数据为离散值，然而现实世界的许多应用中却常常涉及到连续的数值 属性，这就必须对连续的数据进行离散化处理，以加快后继数据挖掘和机器学习算法的运 行速度，减小后继算法的空间开销，提高分类精度。离散化数据处理是数据挖掘、机器 学习中的一个重要的预处理过程。由于连续属性的最优离散化是一个n p 完全问题【1 1 】， 所以在众多的离散化算法中，很难找到通用的离散化算法在不同的数据集以及不同的领 域都有较好的效果。因此挖掘新的离散化处理方法，把离散化方法进行比较，找出各种 离散化方法的优点和缺点，对于我们在面对不同类型的数据集时选择一种较合适的离散 化方法是非常必要的。一般来说，如果数据集中的对象在在空间的分布比较均匀，则离 ：j ， 散化的结果不是很令人满意，如果数据集中的对象在空间分布的类别信息很明显：则离 散化的效果比较好，另外，如果数据集的决策属性的类别信息较多，则离散化的效果较 差，如果数据集的决策属性的类别信息较少，则离散化的效果较好。 本文提出的这种基于n b c 聚类的离散化方法( a d b n b c 算法) ，虽然在所选的数据 库上效果较好，但是同时也存在着不足之处：首先，由于目前的离散化算法很多少我们 不可能对每一个离散化算法进行分析，仅仅是从每一类离散化方法中，选出一部分离散 化算法进行了分析比较，而所选的离散化算法的代表性可能不能覆盖所有离散化算法。 其次，本文所用的只是有限的数据库，所得到的结果可能比较片面，要想从根本上验证 算法的可行性，只有深入研究，加大数据信息量，找出算法在不同数据集类型中的运用 规律。 河北大学t 学硕士学位论文 参考文献 【1 】聂红梅，周家庆粗糙集理论中一种连续属性离散化算法现代电子技术2 0 0 7 。 2 】任永功，王杨，闫德勤基于遗传算法的粗糙集属性约简算法小型微型计算机系统2 0 0 6 。 3 张静，王建民，何华灿基于d b s c a n 聚类的连续属性离散化算法计算机工程与应用2 0 0 6 。 【4 李国和基于对象分布的连续属性离散化方法计算机应用研究2 0 0 6 。 5 s z h o u ，y z h a o ，j g u a n ，j h u a n g an e i g h b o r h o o d - b a s e dc l u s t e r i n ga l g o r i t h m p a k d d 2 0 0 5 。 【6 】谢宏，程浩忠，牛东晓基于信息熵的粗糙集连续属性离散化算法计算机学报2 0 0 5 。 【7 】孟祥萍，鞠传香，王贤勇，任纪川粗糙集理论中基于属性重要性的离散化方法东北电力学院 学报2 0 0 5 。 【8 】于锟，刘知贵，黄正良 粗糙集理论应用中的离散化方法综述西南科技大学学报2 0 0 5 。 【9 】项新建，s t o l l e m 一种基于聚类的粗糙集连续属性的离散化算法浙江科技学院学报2 0 0 3 。 【1 0 】马帅，王腾蛟，唐世渭等一种基于参考点和密度的快速聚类算法软件学报2 0 0 3 。 1 1 】赵卫东，戴伟辉，蔡斌遗传算法在决策表连续属性离散化中的应用研究系统工程理论与实 践2 0 0 3 。 1 2 】代建华，李原香，刘群遗传算法在决策系统离散化中的应用微电子学与计算机2 0 0 3 。 1 3 】赵军，王国撤，吴中福等基于粗集理论的数据离散化新算法重庆大学学报( 自然科学 版) 2 0 0 2 。 【1 4 】l i uh ，h u s s a i nf ，t a ncle ta 1 d i s c r e t i z a t i o n ：a ne n a b l i n gt e c h n i q u e d a t am i n i n ga n d k n o w l e d g ed i s c o v e r y 2 0 0 2 。 1 5 】李龙澍，程慧霞，卢冰原基于凸r o u g h 集的数据约简和规则发现研究东南大学学报( 自然 科学版) 2 0 0 2 。 【1 6 】h a r tj w ，k a m b rm d a t am i n i n gc o n c e p t sa n dt e c h n i q u e s s a n f r a n c i s c o ，c a ：m o r g a nk a u f m a n n p u b l i s h e r s ，i n c ，2 0 0 1 。 【1 7 】王国胤r o u g h 集理论与知识获取西安交通大学出版社2 0 0 1 。 1 8 】刘清r o u g h 集及r o u g h 推理科学出版社2 0 0 1 。 1 9 】侯利娟，王国胤，聂能粗糙集理论中的离散化问题计算机科学2 0 0 0 。 【2 0 n g u y e nhs ，s k o w r o na q u a n t i z a t i o no fr e a l - v a l u e da t t r i b u t e s ，r o u g h s e ta n db o o l e a nr e a s o n i n g a p p r o a c h e s i n ：p r o co ft h es e c o n dj o i n t a n n u a lc o n f e r e n c eo ni