（管理科学与工程专业论文）连续属性离散化算法比较研究.pdf

连续属性离散化算法比较研究 摘要 连续属性的离散化是数据分析预处理中的一项重要内容，在数据挖掘、机 器学习等领域中具有重要作用。针对离散化问题，研究者提出了很多方法，从 不同的角度看，可以把这些方法划分为不同的种类，如根据离散化处理时是否 以类别信息做参考，可以把离散化方法分为监督的离散化方法和非监督的离散 化方法。由于各种离散化算法侧重点的不同，针对不同结构的数据，不同的离 散化方法往往得出不同效果的离散化结果。由于目前尚没有设计出适合不同数 据结构、不同领域数据的通用离散化方法，因此，对比不同离散化方法的优缺 点，研究各种离散化方法的适用性问题，对选择合适的离散化方法，得到有效 的离散化结果具有重要意义。 本文首先介绍了连续属性离散化任务及目标，描述了离散化问题及本质， 并扶不同的角度上对离散化方法进行了分类，介绍了几种经典的离散化方法。 接着本文根据离散化方法的分类，建立了离散化方法的层次框架。在层次框架 中，首先将离散化方法分为单变量离散化方法和多变量离散化方法，再分为拆 分的离散化方法和归并的离散化方法，再进一步划分为监督的离散化方法和非 监督的离散化方法本文给出单变量拆分方法、单变量归并方法、多变量拆分 方法和多变量归并方法的离散化过程，并分析了一些离散化算法，使用标准数 据给出这些算法的断点。然后本文选取一些单变量离散化算法和多变量离散化 算法进行实验比较和分析。实验比较和分析分为单变量离散化算法的实验比较 与分析、多变量离散化算法的实验比较与分析和单变量与多变量离散化的实验 比较与分析，并对一种离散化算法进行了改进。最后本文介绍了基于粗糙集的 数据挖掘平台。 关键词：离散化；贪心算法；属性重要性；信息熵；聚类；最小描述长度；依 赖度；分箱 s t u d yo nc o m p a r i s o no f d i s c r e t i z a t i o na l g o r i t h m so f c o n t i n u o u sa t t r i b u t e s 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 l li m p o r t a n ti s s u ei nd a t ap r e p r o c e s s i n g ，w h i c h p l a y sa ni m p o r t a n tr o l ei nd a t am i n i n g ，m a c h i n el e a r n i n ga n do t h e rd o m a i n s m a n yr e s e a r c h e r s p r o p o s eal o to fm e t h o d sa b o u tt h ed i s c r e t i z a t i o np r o b l e m ，w h i c hh a v eb e e nd e v e l o p e da l o n g d i f f e r e n tl i n e sd u et od i f f e r e n tn e e d s f o re x a m p l e ，d a t ad i s c r e t i z a t i o nm e t h o d sc a l lb e c 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 dm e t h o d sd e p e n d i n go nw h e t h e rt h ed a t ap r o c e s s e d h a sc l a s si n f o r m a t i o n a m o n gt h e s em e t h o d s 。d i s t i n c tm e t h o d sw i l lg e td i f f e r e n tr e s u l t sw h e n t h ed a t as t r u c t u r ei sd i f f e r e n t u n f o r t u n a t e l y , t h e s em e t h o d sa r ea l ln o tu n i v e r s a la n dm a yg e t b e t t e rr e s u l t so ns o m ed a t aa n dw o r s eo n e so no t h e r s t h e r e f o r e ，t h es t u d yo nt h ec o m p a r i s o n o fd i s c r e t i z a t i o na l g o r i t h mc a ng i v ea d v i c e st os e l e c te f f e c t i v ea l g o r i t h m f i r s t l y , t h ea s s i g n m e n tt a s ka n da i mo fd i s c r e t i z a t i o ni si n t r o d u c e d ，t h ep r o b l e ma n d e s s e n c eo fd i s c r e t i z a t i o na r ed e s c r i b e da n dt h ed i s c r e t i z a t i o nm e t h o d sa r ec l a s s e df r o m d i f f e r e n tv i e w si nt h i s p a p e r s e c o n d l y , an e wh i e r a r c h i c a l f r a m e w o r ki s p r o p o s e df o r d i s c r e t i z a t i o nm e t h o d s i nt h i sf r a m e w o r k , t h ed i s c r e t i z a t i o nm e t h o d sa r ec l a s s e ds i n g l e v a r i a b l ea n dm u l t i v a r i a b l ed i s c r e t i z a t i o nm e t h o d sf i r s t t h e nt h ed i f f e r e n td i s c r e t i z a t i o n m e a s u r e sa r ec l a s s e ds p l i t t i n ga n dm e r g i n g ，a tl a s t ，am e t h o di sc l a s s e dt h es u p e r v i s e da n d u n s u p e r v i s e d t h i r d l y , t h ep r o c e s so fs i n g l e v a r i a b l es p l i t t i n ga n dm e r g i n gd i s c r e t i z a t i o n m e t h o d sa n dm u l t i v a r i a b l es p l i t t i n ga n dm e r g i n gd i s c r e t i z a t i o nm e t h o d sa r ep r o p o s e d a n d t h e ns o m ed i s c r e t i z a t i o na l g o r i t h m sa r ea n a l y s e da n dt h ec u t p i o n t so fs t a n d a r dd a t ai sg i v e n f o u r t h l y , t h ep a p e rs e l e c t ss o m es i n g l ev a r i a b l ea n dm u l t i v a r i a b l ed i s c r e t i z a t i o nm e t h o d st od o c o m p a r i s o ne x p e r i m e n t sf o re x p e r i m e n tc o m p a r i n ga n da n a l y z i n g t h ee x p e r i m e n tc o m p a r i n g a n da n a l y z i n ga r ec l a s s e dc o m p a r i n ga n da n a l y z i n go fs i n g l ev a r i a b l ed i s c r e t i z a t i o nm e t h o d s ， c o m p a r i n ga n da n a l y z i n go fm u l t i v a r i a b l ed i s c r e t i z a t i o nm e t h o d sa n di n t e g r a t e dc o m p a r i n g a n da n a l y z i n go fs i n g l ev a r i a b l ea n dm u l t i v a r i a b l ed i s c r e t i z a t i o nm e t h o d s ，a n dt h i sp a p e rg i v e a ni m p r o v e dd i s c r e t i z a t i o na l g o r i t h m a tl a s t ，t h ep a p e ri n t r o d u c e st h ed a t am i n i n gf l o o r p l a t f o r mw ed e s i g n e dw h i c hb a s e do nt o n g hs e t k e yw o r d s ：d i s c r e t i z a t i o n ，g r e e d y , a l g o r i t h m ，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 f i n f o r m a t i o n ，c l u s t e r i n g ，m d l p , d e p e n d e n c y , b i n n i n g 插图清单 图3 1 单变量连续属性离散化算法分类9 图3 2 单变量连续属性离散化过程l o 图3 - 3 多变量连续属性离散化算法分类 图3 4 多变量连续属性离散化流程1 7 图4 1 四种单变量算法在断点数、测试精度和计算时间上的比较2 8 图4 - 2 四种多变量算法在断点数、测试精度和计算时间上的比较3 0 图4 3 单变量和多变量离散化方法的比较3 1 图4 4 数据挖掘流程3 3 图4 5 基于粗糙集的数据挖掘实验平台主界面3 4 图4 _ 6 数据挖掘平台离散化模块3 5 图4 7 连接数据3 5 图4 - 8 连续数据的显示3 6 图4 - 9 离散结果和断点集3 6 v i 表格清单 表3 1 取算法划分1 2 表3 - 2 等宽算法的i r i s 离散化断点1 2 表3 3 等频算法的i r i s 离散化断点1 2 表3 _ 4 取算法的i r i s 离教化断点1 2 表3 5d 2 算法的i r i s 离散化断点。1 4 表3 - 6m a n t a r a s 算法的i r i s 离散化断点1 4 表3 - 7z e t a 算法举例1 5 表3 - 8z e t a 算法的i r i s 离散化断点1 5 表3 - 9c h i m e r g e 算法的i r i s 离散化断点1 6 表3 1 0 基于信息熵的粗糙集连续属性离散化算法的i r i s 离散化断点1 9 表3 1 l 文献 3 3 1 的i r i s 离散化断点2 1 表3 1 2 列先行后算法的i r i s 离散化断点2 2 表3 1 3 连续属性的整体离散化算法的i r i s 离散化断点2 4 表3 1 4 基于属性重要性算法的i r i s 离散化断点2 5 表4 _ l 数据集的信息2 6 表4 2 四种单变量离散化算法实验结果2 7 表4 3 四种算法实验结果2 9 表4 - 4 单变量与多变量平均结果比较3 1 表4 5 决策表3 2 表4 - 6 原算法与改进后的算法比较3 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果 也不包含为获得金a b 王些太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文储签字磨l 乎 签字日期：7 多阵，如 学位论文版权使用授权书 听日 本学位论文作者完全了解盒b 王些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权盒a 巴王些太 j l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索。可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：侄穹 产、j 蝴期：竹编个 导师签名：刍。l 耖破 l 签字日期2 弘1 7 年月f 日 学位论文作者毕业后去向：霉f 4 彩丫主 工作单位： 通讯地址： 电话： 邮编： 致谢 本论文的撰写是在我的导师刘业政教授的悉心指导下完成的。在近三年的 硕士研究生期间，刘老师在学业上一直对我严格要求，生活上给予无微不至的 关怀，我所取得的每一点进步、每一点成绩都离不开刘老师的谆谆教诲。值此 论文完成之际，我谨向导师刘业政教授表示诚挚的感谢，并致以深深的敬意。 刘老师渊博的知识、严谨的治学态度、敏锐的学术洞察力、积极开拓和忘我的 工作精神，都对我产生很大影响，将使我受益终生。在今后的学习、生活和工 作中，我将以导师为榜样，为社会做出自己的贡献。 感谢合肥工业大学管理学院和电子商务研究所为本人提供的研究条件，感 谢杨善林、赵慧芳、梁昌勇、刘心报、倪志伟、李兴国、何建民、左春荣、张 结魁、凌海峰、赵勇和魏婿等老师对我的关心、帮助和指导。 衷心感谢合肥工业大学管理学院和研究生部领导、老师对本人的关心和帮 助。 林文龙、姜元眷、杨洁琼、马向辉、徐德鹏、钟扬、王卫、郭春根、郑蕊、 唐亮、徐建华，谢珩、余智学等师兄弟对我的学习和生活也给予了很多帮助， 在此一并表示感谢。 在我学习生涯中，我的父母和家人从物质上、精神上给予了我无穷的支持 与鼓励，没有他们背后的支持，我将无法完成我的学业，他们是我的精神支柱。 感谢对论文进行评审、提出宝贵意见的各位专家。 最后，感谢所有帮助和关心过我的人们。 i i i 作者：焦宁 2 0 0 7 年5 月 1 1 研究背景 第一章绪论 离散属性也称是符号的( s y m b o l i c ) 、或名称的( n o m i n a l ) ，类别的( c a t e g o r i c a l ) 属性，这些属性是用少量的离散值表示的，例如颜色、形状等；连续属性也称 是实数的( r e a l ) 、或有序的( o r d e r e d ) 、或数值的( n u m e r i c a l ) 属性，这些属性表示 了对象的一种可测量的属性。其值取自一段连续的区间。将这些连续的属性转 化为离散的属性，这一过程就称为连续属性的离散化。 连续属性的离散化是数据挖掘和机器学习的重要预处理步骤，直接关系到 挖掘或学习的效果。在数据挖掘和机器学习等领域中，许多算法都只能对离散 化的数据进行处理。例如在分类应用中比较好的i d 3 系列决策树法，就只能运 用在离散属性上。p a w l a k z 提出的粗糙集理论为进行数据挖掘提供了一个很好 的工具，但遗憾的是该理论只适用于离散属性，而不能直接处理连续属性，这 就大大限制了粗糙集合理论的应用范围，为了使粗糙集合理论能够处理连续属 性，就需要将连续属性进行离散化。 现在实际的数据库规模往往很大。里面存储了大量的数据，如果直接以这 些数据来进行挖掘获取或进行学习，其时间和空间的代价不言而喻。如果将连 续的属性进行离散化，就能够从这些含有连续属性的数据库中取得好的数据集， 得到简洁且有效的规则。离散化结果将会减小系统对存储空问的实际需求，加 快后继数据挖掘和机器学习算法的运行速度，减小后继算法的空间开销，提高 分类精度。目前，已经出现许多离散化算法，但是连续属性的最优离散化是一 个n p 完全问题【l l ，离散化的方法不同，结果也往往存在差异。因此，连续属性 离散化算法比较研究对不同数据结构的数据集适用哪一种离散化算法有重要意 义，并且对不同的环境下选择合适的离散化算法又指导作用。 1 2 离散化算法的发展与现状 以前，在数据挖掘、机器学习领域中，离散化处理通常被当作一种边缘性 的辅助工作而没有受到应有的重视。然而，现实世界的许多应用中常常涉及连 续的数值属性，目前许多的机器学习算法却要求所处理的属性取离散值。因此， 人们认识到为了能够处理这些现实问题，必需对连续的数值属性进行离散化处 理，使其转变为离散属性。因此，离散化问题得到了较为广泛和深入地研究【2 3 “l ，多种离散化算法被提出来【5 】 上个世纪9 0 年代初期，数值属性的离散化开始受到机器学习界的关注，并 逐步吸收了统计学、信息论等领域的研究成果。一些基于信息熵的方法开始出 现在了离散化处理当中1 6 j 。 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 熵的层次化离散化算法【7 】。这种算法利用“h i l l c l i m b i n g ”搜索法，在 各个属性轴上，寻找连续空间上合适的初始分区，然后在详细的分区上反复的 应用这一方法以获得出色的分区。 c a t l e t t 在1 9 9 1 年研究出了在决策树领域使用基于信息熵的离散化，作为实 现显著加快拥有许多连续属性的大量数据集的归纳的方法【引。他的d 2 离散化使 用多个条件标准一一每个分区的最小示例数、分区的最大数目和最小信息增益 来防止每个属性分区的递归形式。 1 9 9 3 年，f a y y a d 和i r a n i 将递归信息熵最小限度启发式方法应用于离散化处 理，并且把它与最小描述长度标准方法【9 】结合起来，用以控制连续空间中分区 产生的个数最初，这一方法只在树生成时局部的应用于每一个节点。 目前，人们提出了许多经过改进的离散化处理方法。如，针对数值属性的 无监督离散化，提出了基于概率模型的离散化算法。它采用概率生成模型1 1 0 】 描述区间，允许观测值相对于区问的不确定性，便于使用贝叶斯信息准则来评 价、比较不同的概率生成模型，从而为自动确定区间数目、位置、宽度提供了 较为系统的方法 人们对基于粗集模型的离散化方法也进行了相应的研究，并取得了一些有 价值的研究成果l i “。 这些成果大致可以分为两类：其中一类方法很少甚至是完全不考虑粗集理 论的特殊性，直接把其它学科中的相应方法用来对信息系统进行离散化，其结 果往往不能保证原有信息系统的分辨关系；另一类方法则充分考虑了粗集理论 的特殊要求，其结果能够保证信息系统的分辨关系。其中，前一类方法的典型 代表是粗集工具软件r o s e t t a 提供的离散化方法；后一类方法的典型代表是基于 布尔逻辑和粗集理论的离散化方法【1 1 2 】。 1 3 离散化算法比较研究的现状 连续属性的离散化是数据挖掘和机器学习的重要预处理步骤，直接关系到 挖掘或学习的效果。随着数据挖掘，机器学习的发展，连续属性的离散化也快 速发展。迄今为止已经出现了大量的离散化算法。但是连续属性的最优离散化 是一个n p 完全问题【l 】，离散化的方法不同，结果也往往存在差异。因此离散 化算法的比较有重要的意义，它可以帮助用户在对连续属性进行离散化时选择 适当的离散化算法。 近年来出现了大量的离散化算法，这些算法各有自己的优缺点，分别适用 于不同的数据集。为了更加详细地、全面地掌握这些算法的优缺点，已有学者 提出了对离散化算法的比较研究。如文献【1 3 探讨了基于租糙集的局部离散化 算法和整体离散化算法，并用实验验证这两种算法；文献【6 】从非监督和监督的 2 角度来分析离散化，详细分析非监督的分箱离散化算法和监督的基于信息熵的 离散化算法，并比较这两种算法。文献【1 4 1 分析比较了通常用于朴素贝叶斯分 类器的9 种离散化算法，并得出哪些方法适用于朴素贝叶斯分类器。文献 1 5 】 建立了一个离散化框架，对离散化方法进行了划分，并对单变量离散化方法进 行了分析比较研究。 1 4 本文主要研究内容及结构 1 4 1 研究内容 ( 1 ) 介绍离散化算法的发展、现状及离散化算法比较现状； ( 2 ) 抽象描述单变量连续属性和多变量属性离散化过程： ( 3 ) 根据目前存在的离散化算法，建立离散化方法层次框架； ( 4 ) 根据标准数据，通过实验系统地展现各种离散化算法的不同结果，并 分析产生不同结果的原因； ( 5 ) 详细比较实验结果并为不同环境使用不同方法提供指导。 1 4 2 结构安排 第一章，绪论。本章分析了连续属性离散化算法比较研究的背景，描述了 离散化算法的发展与现状，概括了离散化算法比较研究现状并简要介绍研究内 容及结构。 第二章，连续属性的离散化算法。本章介绍离散化算法的任务与目标，描 述了离散化问题及其本质，并对目前存在的离散化算法进行分类，介绍了几种 经典的离散化算法。 第三章，连续属性离散化算法分析比较。介绍了一种离散化算法新的划分 方法，在此基础上建立了一个离散化方法划分的层次框架。 第四章，连续属性离散化算法实验比较。根据标准数据，选出几种离散化 算法进行实验，并解释实验结果。 第五章，总结。 3 第二章连续属性的离散化算法 2 1 离散化算法的任务与目标 2 1 1 离散化算法的任务 连续属性的离散化就是在特定的连续属性的值域范围内设定若干个离散化 划分点，将属性的值域范围划分为一些离散化区间，最后用不同的符号或整数 值代表落在每个子区间中的属性值1 6 l 。对连续属性的离散化过程，从本质上来 看，就是用一定的阀值对属性空间进行划分的过程。 2 1 2 离散化算法的目标 从直观的角度看，可以从以下几点【1 7 】衡量一个离散化算法是否是成功的： ( 1 ) 完全离散化 就是指算法要能够完成数据集的多个连续属性的离散化处理。因为我们不 大可能只需要对数据集的某一个连续属性进行离散化处理，除非数据集只包含 一个连续属性。 ( 2 ) 具有最简单的离散化结果 一般来说，如果离散化处理完成后，属性空间的规模越小，由这些离散化 处理所产生出来的数据所生成的规则就越简单。因此，由这样的属性所获得的 知识就更通用。 ( 3 ) 一致性 具有连续属性的数据集通常都是一致的，如果应用于某个属性的离散化处 理是不成功的，一个不一致的数据集可能就会产生了。当这种情况发生时，我 们就丢失了有价值的信息。因此，离散化处理应该尽可能保证经过离散化处理 后所得到的数据集的一致性水平与原始数据集的一致性水平接近。 ( 4 ) 预测精度 离散化在多大程度上能提高精度，精度可以通过有效模式的分类结果得到。 对一个给定的数据集，存在一种或多种最优的离散化结果，但遗憾的是，人们 已经证明连续属性的最优离散化问题是一个n p 难题【l 】。因此，对具有丰富样本 的信息系统而言，人们只能试图获得一个次最优的离散化算法，在保证离散化 结果性能要求的前提下，用尽可能少的断点将属性空间划分成尽可能少的予空 间，达到前面的四条标准，就成了离散化算法的追求目标。 2 2 离散化问题描述 设s c ，c u 研，以， 为一决策表，其中u ；“x 2 为论域， 4 c = a l , a 2 ，a ，和 d 分别称为条件属性集和决策属性集。假设对于v a e c ， v i = 以，r o ) c r 是实值区间。属性a 的值域圪上的一个断点可以记为有序对 0 ，c ) ，其中a c ，c 为实数集。令只是屹的子区间划分，即对于某一整数k ， 只表达为：e o = 【c ；，c ? ) ，【c ? ，c ；) ，【，c 乏+ 】) = 靠 矸 c ； ，对于v 工u， j 0 ，屯) ， f 7 ( ) = i 营，( x a ) 【c ? ，c 厶) 。这样就把原来含有划分成，1 个铆 c a r d ( u ) ) 区域， 每个区域中对象的决策值相同。事实上，每个这样的区域对应一个离散后决策 系统中一个对象。 2 3 离散化问题的本质 离散化本质上可归结为利用选取的断点来对条件属性构成的空间进行划分 的问题，把拧( 以为连续属性的个数) 维空间划分成有限个区域，使得每个区域 中的对象的决策值相同。假设某个属性有r n 个属性值，则在此属性上就有m 一1 个断点可取，随着属性个数的增加，可取的断点数将随着属性值的个数成几何 增长选取断点的过程也就是合并属性值的过程，通过合并属性值的过程，减 少属性值的个数，减少断点数，从而减小问题的复杂度，这也有利于提高知识 获取过程中所得到的规则知识的适应度。 2 4 离散化算法分类 2 4 1 离散化算法的分类方法 随着数据挖掘、机器学习等领域的迅速发展，对分类的精确度和效率要求 越来越高，离散化技术得到迅速发展。经过这些年的发展，许多离散化算法在 保持分类能力不变的情况下，能够减少大量的数据。由于不同需要，离散化方 法在不同的方向取得了发展。离散化算法根据不同的划分方式，可以分为五类 【1 5 】： ( 1 ) 根据是否利用整个属性空闻进行离散化处理，分为全局离散化和局部 离散化 ( 2 ) 根据离散化处理时是否以类别信息做参考，分为监督离散化和非监督 离散化。 ( 3 ) 根据离散化与决策树的生成是否同时进行，分为静态离散化和动态离 散化。 ( 4 ) 根据是把属性的每个值作为一个离散属性值还是把整个属性值区间当 作一个离散的属性值，分为归并离散化和拆分离散化。 ( 5 ) 根据是直接把连续属性划分为k 个区间还是通过一个递进过程完成简 单的离散化，分为直接离散化和递进离散化。 2 4 2 全局离散化和局部离散化 全局离散化方法，是指应用数据集对象整个空间来进行离散化处理，如等 宽、等频率算法。局部离散化方法，是指在数据集对象的某一局部空间进行离 散化处理。如c 4 5 【1 引，它产生应用于示例空间的局部化区域的分隔于局部离散 化方法。因此，局部离散化方法通常与动态离散化方法相联系。 2 4 3 监督离散化和非监督离散化 监督式方法把类别的信息带到离散化的过程。监督式方法的研究主要是围 绕量化过程中所使用的评价函数和终止条件而展开的，如信息论中的信息熵是 置化算法中常用的一种评价函数。这些方法在对属性离散化的过程中考虑了对 象的分类信息。监督方法主要有：自然算法、半自然算法和布尔推理算法。自 然算法根据需要离散化的某属性值将对象排序，按照对象的顺序，只要对象的 决策值改变，就产生一个新区间，该算法产生保持决策系统一致性水平所需的 所有分割点；半自然算法的思想与自然算法相似，但产生较少的分割点，是自 然算法分割点的子集 布尔推理算法【1 l 是s k o 、r o n 和n g u y e n 根据租集理论和布 尔推理提出的一种离散化方法，并对其进行了一定的改进，这是一种全局有监 督算法。利用布尔推理程序，可以合并一些初始分割点，剩下的分割点是保留 决策系统不可分辨力的最小集合。监督式方法还有信息熵法【2 1 、检验法【3 】和贝 叶斯决策法i l 州等。 非监督方法在离散化过程中不考虑类别属性，其输入数据集中仅含待离散 化属性的值。非监督离散化包括等宽度和等频率离散化。等宽度离散化是将待 离散化属性的值域按相等的数值宽度进行划分，而等频率离散化则是将待离散 化属性的值域范围划分成若干个子区间，使每个子区间包括大致相等的数。非 监督离散化设计思想简单、容易实现，但是在处理带有类别信息的数据集时， 通常很难获得较好的离散化效果。 2 4 4 静态离散化和动态离散化 静态方法又称为预处理型方法，即在数据分类之前先对连续的数据进行离 散化，从而在数据挖掘、机器学习时可大大提高学习效率。 动态方法主要与决策树有关，它是一边生成决策树，一边进行连续值区间 的划分；具体说，决策树法在选择属性值时，对于连续属性，它要寻找一 个断点，该断点把该属性的连续区间划分为两个区间。由于属性值的选择 是随着树的生成而动态变化的，因此该离散化方法属于动态划分法。 6 2 4 5 拆分离散化和归并离散化 拆分法是把整个属性值区间当作一个离散的属性值，然后对该区间进行划 分，一般是一分为二，即把一个区间分为两个相邻的区间，每个区间对应一个 离散的属性值，该划分可以一直进行下去，直到满足某种停止条件，其关键是 对于划分点的选取。归并法是把属性的每个属性值当作一个离散的属性值，然 后逐个反复合并相邻的属性值，直到满足某种停机条件。归并法的关键有两个 要素。一是如何确定应该合并的相邻区间，二是最终的停止判断。 上述两种划分策略，在离散化的开始，都要计算一组断点。根据这些断点 来定义区间。给定某个连续属性的一组互不相同的值x ，而。吒以及它们对应的 类别标记，先对x ，x ：j 。由小到大排序，排序结果为m ，儿。以，再用y i ，儿以构 造一组断点毛，z 2 - z 。( 肌 哟，使得任意相邻的两个断点周围的属性值对应的类 别标记不同。 2 4 6 直接离散化和递进离散化 直接方法是将连续属性划分为k 个区间，如等距离、等频率算法。这种方 法需要人为地规定划分的区间，也就是需要用户预先给定一个参数k ，根据给 定的参数将各个属性的值域划分为若干个离散的区域，不需要设置算法的终止 条件。 递进式方法通过一个递进过程完成简单的离散化，不过需要一个评判值确 定什么时候停止。如基于属性重要性的连续属性离散化算法【2 们。这种算法首先 计算条件属性的重要性，然后根据属性重要性由小到大对条件属性进行排列， 并依次求每个条件属性的断点。由于断点的判定是从它所属的属性的重要性由 小到大的顺序进行的，所以，属性重要性较小的属性的断点被淘汰的可能性更 大，避免了把属性重要性较大的那些属性的属性值去掉。 2 5 几种典型的离散化算法 ( 1 ) 等宽算法 等宽算法是最简单的无监督离散化算法，它根据用户指定的区间数目置， 将数值属性的值域，痂，k 】划分为足个区间，并使每个区间宽度相等。即都 等于一。k ) g 。如c a t l e t t 所指出【2 1 1 ，当存在对于区域来说偏斜极为严重的 点时，这种类型的离散化方法是极为脆弱的。 ( 2 ) 等频算法 与等宽算法相联系的等频算法也是将数值属性的值域化分为髟个小分区， k 同样是用户指定的区间数目。等频算法与等宽算法的不同在于，它不是要求 每个区间宽度相等，而是要求位于每个区间的对象数目相等，就是说，如果属 7 性的整个取值区间内共有m 个点，那么等频区间法所划分出的k 个小区域中， 每个区域含有m ，置个邻近值的点。 这两种算法都容易实现，但因为它们在定义划分区间边界时忽视类别信息， 因而难以将区间的边界设置在最合适的位置上有时，使得与不同类别联系紧 密的一些值被划迸了同一个区域i 孔，在一些情况下。这会使得有效的分类变得 困难所以大多数情况下，它们的性能不能令人满意。 ( 3 ) k - m e a n s 算法 k m e a n s 算法是一种应用广泛的数据聚类算法。在用户指定了离散化产生 的区间数目x 后，k - m e a n s 算法首先从数据集中随机找出x 个数据作为x 个初 始区间的重心；然后，根据与这些重心的欧几里德距离，对所有的对象聚类： 如果数据z 距重心g 最近，则将善划归g f 所代表的那个区间；然后重新计算各 区间的重心，并利用新的重心重新聚类所有样本。这样逐步循环，直到所有区 间的重心不在随算法循环而改变为止。不过，尽管k - m e a n s 算法在聚类分析方 面比较成功，对于数值属性的离散化而言，采用欧几里德距离作为区间划分的 依据，尚缺乏理论根据。此外，该算法依靠用户来指定区间数目，不能自动确 定最适合的区间数。 ( 4 ) c h i m e r g e 算法 c h i m e r g e 系统i 3 t 提供了一种统计合理的启发式有监督离散化算法。算法初 始时将每个观察到的数据放到它自己的区域中，然后，考察z 2 来决定临近区域 是否需要合并。这种方法通过产生期望密度的经验估计来验证两个相邻区间是 不相关的的假设。合并过程受到使用z 2 极限的控制，z 2 极限表示保证合并两个 区间的最大z 2 值。对于随机数据，应该设定一个非常高的极限以避免产生过多 的分区。该算法的缺陷在于每次循环只能归并两个区间，当样本集比较大时离 散化速度较慢。 ( 5 ) s t a t d i s c 算法 另一应用统计学测试来作为决定离散化分区的方法的算法是r i c h e l d i 和 r o s s o t t o 在1 9 9 5 年提出的s t a t d i s c 算法1 2 2 1 。与c h i m e r g e 算法的风格相似，这一基 础方法通过使用作为合并分区的标准的量度。产生一个离散化分区的层次。 s t a t d i s c 算法比c h i m e r g e 算法更通用，它考虑一次与个相邻分区合并，而不 是c h i m e r g e 算法那样，每次只合并两个相邻分区。合并分区直到达到中极限 这样，产生最终的离散化层次并且自动的选择了适合的最后离散化结果。 8 第三章连续属性离散化算法分析比较 在大量连续属性离散化的文献中，连续属性离散化的算法各不相同，从不 同的着眼点会有不同的分类方法。如果在连续属性离散化时，每次仅对一个连 续属性进行操作，我们则认为是单变量连续属性离散化，如果在连续属性离散 化时考虑所有的连续属性，我们则认为是多变量连续属性离散化。对于目前存 在的连续属性离散化算法，我们可以将它们划分为单变量连续属性离散化和多 变量连续属性离散化。 3 1 单变量连续属性离散化 单变量连续属性离散化方法，是指每次仅对某一连续属性进行离散化操 作，不考虑连续属性间的相关性和互补性。 3 1 1 单变量连续属性离散化框架 厂卫 囱回 罪一 图3 - 1 单变量连续属性离散化算法分类 9 3 1 2 单变量连续属性离散化过程 图3 2 单变量连续属性离教化过程 单变量连续属性离散化过程一般包括四个步骤： ( 1 ) 求候选断点集：首先。设候选断点集为空集；然后，求出该连续属性 的候选断点加入候选断点集。在求候选断点时，一般将连续属性进行排序，以 相邻属性值的中值作为候选断点值。对于候选断点的选择，一些文献也提出过 一些方法，如文献 2 3 】。 ( 2 ) 断点选择：得到候选断点集之后，就是寻找最优的断点最优断点是 通过目标函数来进行查找的。首先计算每个断点的目标函数值，并进行比较这 些断点的目标函数值来得到最优断点。 ( 3 ) 删除或添加断点：得到最优断点后，对于属于拆分的方法，会将最优 断点放入最优断点集( 最优断点集初始为空) ，并将该断点从候选断点集中删除。 在这里，最优断点是分割连续属性值的最佳断点，用于离散连续属性的断点是 在最优断点集中。对于属于归并的方法，会将断点直接从初始断点集中删除。 在这里，最优断点是可以将断点两边区间可以合并的最佳断点，离散化需要的 断点是在初始断点集中。 ( 4 ) 停止标准；停止标准确定什么时候停止离散化过程。一般来说区间划 分过少，精度低，易于理解，而区间划分过密，精度高，可理解程度低，通常 我们取两者的折衷。离散化的停止标准可能很简单，如等宽离散化中指定的区 间数目置；也可能是一个比较复杂评估函数，如文献【1 9 】中的评估函数。 1 0 3 1 3 单变量连续属性离散化的拆分方法 拆分方法把整个属性值区间作为一个离散属性值，然后对该区间迸行划 分，一般是一分为二，即把一个区间分为两个相邻的区间，每个区间对应一个 离散的属性值，该划分可以一直进行下去，直到满足某种停止条件。从离散连 续属性所需要的断点角度看，拆分方法是从候选断点集中选择最优断点来进行 离散化。下面给出单变量连续属性离散化拆分方法的一般过程： s i n g l ev a r i a b l es p l i t t i n ga l g o r i t h m s - o n ec o n t i n u o u sa t t r i b u t e c - d e t e r m l n a t e c a n d i d a t e p o i n t se s ) s p l i t t i n g ( s ) 工fs t o p p i n g c r i t e r i o n ( ) 一s a t i s f i e d r e t u r n t - g e t b e s t s p l i t p o i n t ( c ) d e l e t e s p l i t p o i n t( c ，t ) s i - g e t l e f t p a r t ( s ，t ) s 2 - g e t r i g h t p a r t 8 ，t ， s p l i t t i n g ( s 1 ) s p l i t t i n g ( 8 2 ) 单变量连续属性离散化的拆分方法一般包括四个步骤：求候选断点集； 寻找最优断点；根据断点划分连续属性值；当达到停止标准是停止 划分，否则转。拆分算法存在于大量的文献中，如：分箱【2 4 2 5 1 、信息熵【2 8 2 6 2 7 2 引、依赖度【2 9 1 。 ( 1 ) 分箱 分箱法是最简单的连续属性离散化方法。它通过将数据分布到箱中，对数 据集进行离散化。等宽算法和等频算法是最简单的无监督分箱离散化方法。这 两种算法都需要人为地划分维数，指定区间数目k 。在等宽算法中，根据k 值 把连续属性值简单地划分为距离相等的断点段，不考虑每个断点段中属性值个 数的多少。在等频算法中，根据k 值把膨对象分成段，每段中有m k 个对象 这两种算法虽然简单，但是对给定的足值比较敏感。例如等频算法，完全 相同的两个连续属性值可能被划分到不同的箱中。一种解决办法是，当连续属 性值放分配到不同的箱中后，调整相邻两个箱边界值使得完全相同的属性值仅 在一个箱中。 等宽算法和等频算法没有使用类别的信息，属于非监督离散化算法，而i r 则是一种使用分箱的监督离散化算法。这种算法的思想是，首先将连续属性值 排序；然后将连续属性值划分成许多区间，并根据数据集的类别信息来调整区 间与区间之间的边界。在这种算法中，除最后一个区间外，其他区间至少要包 含6 个属性值。在调整时，两个区间相邻，如果第二个区间的第一个属性值的 类别信息与第一个区间的大多数属性值的类别信息相同，则将该属性值划入第 一个区间，重复此过程直至被考察的属性值的类别信息与第一个区间的大多数 属性值的类别信息不同。下面用例子说明，如表3 1 ： 表3 - 1 i r 算法划分 l属性值 l234 5 67 8 9 l o 1 1 1 21 31 41 5 i 类别信息 b b babababbbbaba l 划分后的类 i别信息 b ba 有表3 1 知，i r 方法将属性值分为三个区间，第一个区间包括属性值l 到 7 ，类别信息为b ；第二个区间包括属性值8 到1 4 ，类别信息为b ；第三个区 间仅包含1 5 ，类别信息为a 。其中，第一区间和第二区间可以进一步合并。该 例子中，有4 个属性值的类别信息发生改变。 等宽算法和等频算法是简单的非监督的离散化算法，很容易实现，但是这 两种算法许多不足之处。第一，在离散化前要设置参数置，由于无法确定足的 合适值，所以需要多次尝试。第二，如果数据集的类别信息可以获得，使用这 两种算法效果较差i r 算法则考虑这个问题，它根据类别