（计算机应用技术专业论文）离散化算法研究与应用.pdf

人连理j 【= 大学硕士学位论文 摘要 连续属性离散化算法是数据挖掘和知识发现领域中非常重要的一部分，其性能的好 坏直接影响到机器学习的精度和效率。大部分机器学习的工具是针对具有离散属性值的 数据集设计的，然而现实生活中的数据集往往包含连续属性值( 比如温度，高度等) ， 这给机器学习的效果带来了影响，使其往往不能得到令人满意的精度。因此在进行数据 挖掘之前，通过离散化算法对数据集进行预处理是非常有必要的。 本文分析了现有的大部分离散化算法，并分别从算法时间复杂度，精度及效率等方 面进行了比较，最终选择对c a i m 算法进行改进。c a i m 算法是一种全局的、静态的、 自上而下的有监督离散化算法。相比于其它离散化算法，c a i m 算法具有时间复杂度小， 精度和效率相对较高的特点，但该算法存在着三个不足：首先，在离散化的过程中没有 考虑到属性的重要性；其次，缺乏对决策表不一致率的考虑；最后，采用c a i r n 值作为 离散判别式也有其不合理之处。这常常造成信息丢失，从而影响到机器学习的精度。鉴 于上述三个缺点，本文提出了两种改进的算法。 首先，本文针对上述c a i m 算法的前两个缺点，提出了一种i m p r o v e dc a i m 离散 化算法，该算法根据d s s t 差异相似集理论来度量属性重要性，在考虑决策表不一致率 的情况下对数据进行进一步的离散化。通过使用c 4 5 和支持向量机工具进行性能分析， 相比于c a i m 算法，本文提出的i m p r o v e dc a l m 算法得到了更高的分类识别率。 其次，本文针对c a i m 算法形成离散区间过少导致机器学习得到的精度低的问题， 提出了一种新的基于决策类和属性依赖度的离散化算法一兄c a i m 。该算法采用统计 学中常用的z 相关系数做为离散化判别式，避免了采用c a i r n 值作为离散判别式时产生 的问题。实验表明，该算法在分类学习时得到了更高的分类识别率。 关键词：离散化；c a i m 算法；差异相似集理论；不一致率；名相关系数 离散化算法研究与应用 r e s e a r c ha n da p p l i c a t i o no fd i s c r e t i z a t i o na l g o r i t h m a b s t r a c t t h ed i s e r e t i z a t i o na l g o r i t h mt a k e sa ni m p o r t a n tp a r ti nt h ef i e l do fd 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 , a n di t sp e r f o r m a n c eh a sad i r e c ti m p a c to nt h ea c c u r a c ya n de f f i c i e n c y o fm a c h i n el e a f i n g m o s to fm a c h i n el e a r n i n gt o o l sa r ed e s i g n e df o rt h ed a t a s e t so n l yw i m d i s c e r t ea t t r i b u t ev a l u e s ；h o w e v e r , t h ed a t a s e t sf r o mt h er e a l w o 订do f t e nc o n t a i nc o n t i n u o u s a t t r i b u t ev a l u e s ( s u c h 弱t e m p e r a t u r e ，h e i g h t ，e t e ) m sh a sa l li m p a c to nt h er e s u l t so f m a c h i n el e a r n i n gt h a to f t e nc a l ln o tg e tas a t i s f a c t o r ya c c u r a c y t h e r e f o r e i ti sn e c e s s a r yt o a p p l yt h ed i s c r e t i z a t i o na l g o r i t h mt op r e p r o c e s st h ed a t a s e t sp r i o rt od a t am i n i n g 啦sp a p e l a n a l y z e st h em o s to fe x i s t i n gd i s c r e t i z a t i o n a l g o r i t h m s ，a n dm a k e sa c o m p a r i s o no nt h et i m ec o m p l e x i t y , a c c u r a c ya n de f f i c i e n c yr e s p e c t i v e l y f i n a l l yw ec h o o s e t h ec a i m a l g o r i t h mt om a k eaf u r t h e ri m p r o v e m e n t t h ec a i ma l g o r i t h mi sag l o b a l ，s t a t i c ， t o p d o w na n ds u p e r v i s e d d i s e r e t i z a t i o na l g o r i t h m c o m p a r e dt oo t h e rd i s c r e t i z a t i o n a l g o r i t h m s a l t h o u g ht h ec a ma l g o r i t h mh a ss m a l l e rt i m ec o m p l e x i t y , h i g h e ra c c u r a c ya n d e f f i c i e n c y ，t h e r ea r es t i l lt h r e ed e f t c i e n c i e s ：f i r s to fa 1 1 i ti g n o r e st h ei m p o r t a n c eo fa t t r i b u t e s i nt h ep r o c e s so fd i s c r e t i z a t i o n ；s e c o n d l y , i td o e sn o tt a k eu n c e r t a i n t yo fd e c i s i o nt a b l ei n t o a c c o u n t ；f i n a l l y , u s i n gt h ec a i mv a l u e sa sd i s e r e t i z a t i o nd i s c r i m i n a n ti si n a p p r o p r i a t e t h e s e s h o r t c o m i n g sl e a dt ot h el o s so fi n f o r m a t i o n ，t h u sa f f e c t i n gt h ea c c u r a c yo fm a c h i n el e a r n i n g t o w a r d st h et h r e ea b o v e m e n t i o n e ds h o r t c o m i n g s ，w ep r e s e n tt w oi m p r o v e da l g o r i t h m s f i r s t l y , w ep r o p o s ea ni m p r o v e dc a md i s c r e t i z a t i o na l g o r i t h mf o r t h ef i r s tt w o s h o r t c o m i n g so ft h ec a i ma l g o r i t h m t h ei m p r o v e da l g o r i t h mm e a s u r e st h ei m p o r t a n c eo f a t t r i b u t eb a s e do nd s s t ( d i f f e r e n c es m i l i t u d es e tt h e o r y ) ，c o n s i d e r i n gu n c e r t a i n t yo fd e c i s i o n t a b l ef o rf u r t h e rd i s c r e t i z a t i o n b yu s i n gt h ec 4 5a n dt h es u p p o r tv e c t o rm a c h i n e ，t h e i m p r o v e da l g o r i t h mp r o p o s e di nt h i sp a p e ra c h i e v e dah i g h e rr e c o g n i t i o nr a t e s e c o n d l y , t h ec a i ma l g o r i t h mg e t st o ol i t t l ec u t p o i n t st oa c h i e v eh i g hr e c o g n i t i o nr a t e ， t h u sw ep r o p o s ean o v e la l g o r i t h mc a l l e d 名- c a 订b a s e do ne l a s s a t t r i b u t ei n t e r d e p e n d e n c e t h e 五- c a i ma l g o r i t h mu s e s 五c o n t i n g e n c yc o e f f i c i e n tw h i c hc o m m o n l yu s e di ns t a t i s t i c s a sad i s c r e t ed i s c r i m i n a n t ，a v o i d i n gt h ed e f i c i e n c yb yu s i n gc a l md i s c r i m i n a n t t h er e s u l t s s h o wt h a tt h e 力一c a i m a l g o r i t h mo b t a i n e dh i g h e rr e c o g n i t i o nr a t ei nt h ec l a s s i f i c a t i o n k e yw o r d s ：d i s c r e t i z a t i o n ；c a l ma l g o r i t h m ；d i f f e r e n c es m i l i t u d es e tt h e o r y ； u n c e r t a i n t y ；五c o n t i n g e n c yc o e f f i c i e n t 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 学位论文舯：垫逸篱殛蛊丝图 作者签名： 趸殛日期：2 迸年上l 月三笠日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕+ 学位论文 1绪论 1 1问题的提出及意义 随着电子信息技术和计算机网络技术的迅速发展，数据库系统和因特网中的信息正 在成指数倍的增加，相应的大型存储设备已经被广泛的应用到生产和生活中。如何有效 的从如此海量的信息系统中提取出有用的资源已经成为数据挖掘领域的研究重点。科研 人员经常利用相关的机器学习算法自动的从数据库系统中提取知识。机器学习算法有着 很多方面的应用，其中分类算法是非常重要的一个方面，它广泛的应用于文本摘要、图 片分类和垃圾邮件病毒检测等领域中。 在应用分类算法对数据集进行知识提取和分类时，根据原始数据集的属性特征可分 为数字属性( 如1 ，2 ，3 ) 、名词属性( 如红，黄，蓝) 和连续值属性( 如温度，海拔 等) ，连续值属性和数字属性的元素之间是有次序的，而名词属性的元素之间是没有次 序的。其中，数字属性和名词属性统称为离散值属性。一些分类算法比如a q 算法u 捌 和c l i p 算法【3 州只能处理离散值属性数据集。而另外的一些分类算法既能处理离散值属 性数据集，也能处理连续值属性数据集，但是在处理离散值属性数据集时更高效和精确 【5 1 。在现实生活中，数据集通常既含有离散值属性也含有连续值属性，仅包含离散值属 性的数据集是非常少见的。因此，为了获得精确的分类结果，在应用分类算法之前对连 续值属性进行离散化处理是非常有意义的。 。 离散化算法将连续值属性转化成有限个区间，并赋予每个区间一个离散值，从而完 成离散化过程。可以将离散化算法视为整个机器学习过程中的预处理部分，例如在构建 决策树时，首先需要对数据集进行离散化处理。离散化过程可以通过两种方式来实现： 第一种，人工方式，即通过相关领域专家制定离散化策略，对数据集直接进行人为的离 散化；第二种，机器学习方式，即通过离散化算法对数据集进行自动的离散化。无论采 用何种方式，都是利用离散化过程从原始数据集中提取知识，从而将提取的知识进一步 应用到机器学习过程中去。该过程如图1 1 所示。 图1 1 应用离散化算法的分类学习过程 f i g 1 1 t h ep r o c e s so fc l a s s i f i c a t i o nb a s e do nd i s c r e f i z a f i o na l g o r i t h m 离散化算法研究与应用 离散化算法还能够减少某些机器学习算法的计算成本。例如，在定性推理方法中， 当数据集存在冗余精度时，离散化过程就成为了必不可少的部分。高性能的测量方法往 往会得到过高的精度，被称为冗余精度。通常，冗余精度只有在少数的科研领域中才是 有必要的，而在大多数领域中是不适用的。因为，过高的精度不但意味着过多的信息量， 同时也意味着需要庞大的存储容量和计算能力。过多的信息量不利于科研人员对数据进 行分辨，而且对存储容量和计算能力的要求也提高了硬件的成本。因此，当数据集存在 冗余精度时，应用离散化算法对数据进行处理是非常必要的，不仅能减少不必要的信息 便于科研人员提取知识，同时降低了硬件成本。 相比于连续值属性，离散值属性更利于研究人员理解和使用。通常情况下，利用离 散值属性进行机器学习后得到的结果更加高效和精确。所以，对离散化算法的研究是非 常必要和有意义的。 ( 1 ) 适应分类算法的需要。由于大部分分类算法只能处理离散值属性数据集，而 来自现实生活中的数据集通常同时包含离散值属性和连续值属性，这限制了分类算法的 应用范围。因此在使用分类算法之前进行数据离散化处理是非常必要的。 ( 2 ) 减少信息冗余，降低硬件成本。用连续值属性进行机器学习时，虽然信息丢 失率低，但是造成了过高的精度，这对于很多科研领域来说是不必要的，同时增加了科 研项目的硬件成本。因此，利用离散化算法可以适当减少信息冗余，同时降低对存储空 间的要求，进而能够提高分类学习算法的执行效率和分类精度。 ( 3 ) 便于科研人员对原始信息的理解。利用离散值属性进行分类学习得到的结果 更简洁、更直观、更清晰，便于人们深入理解原始数据本身蕴含的意义，从而降低科研 周期的时间成本。 综上所述，如何对连续值属性进行离散化处理，形成一套高效的离散化算法已经成 为了一个亟待解决的问题。 1 2国内外研究现状与技术分析 1 2 1 离散化算法分类及现阶段发展状况 过去，对于离散化算法的研究并没有得到科研人员广泛的重视，而仅仅被认为是数 据挖掘领域中的一项辅助性工作。但是，随着近年来机器学习和知识发现领域的迅速发 展，有关于离散化算法的研究逐渐走入了人们的视线，并得到了越来越广泛的研究与关 注。究其原因主要是因为来源于现实生活中的数据集经常会涉及到连续值属性，然而目 前常用的机器学习算法却仅能处理只包含离散值属性的数据集，这限制了机器学习算法 的实用性，给数据挖掘的研究带来了不便。所以，在对数据集进行机器学习之前，利用 大连理t 大学硕十学位论文 离散化算法对原始数据集进行预处理，使其成为适用于机器学习算法的离散值属性数据 集是非常有必要的。 目前，随着人们对该领域的广泛关注和深入研究，离散化算法已经得到了很大的发 展，多种基于不用离散方式的算法被提出来。衡量离散化算法的优劣，通常要从两个方 面来考虑：第一，是否能保持原始数据集的信息完整性。由于离散化过程是将连续属性 值划分到离散的区间中，这势必会造成信息的丢失从而影响后续的机器学习算法的有效 性。一个性能好的离散化算法能够将这种信息丢失降到最低，保持信息的完整性从而帮 助科研人员更好的进行后续的机器学习工作；第二，是否具有高效性和准确性。由于现 实中的数据集通常很大，在处理这样的数据集时，高效性的算法占有很大优势。同时， 如何划分离散区间才能使得到的结果适用于后续的机器学习算法也是非常重要的，因此 准确性也成为了必须考虑的一个方面。总之，一个性能好的离散化算法能够在高效性和 准确性两者之间达到平衡，而不是单独的强调其中某一点。 根据不同的划分方式，可以将现有的离散化算法分为以下五类： ( 1 ) 有监督式和无监督式 根据在离散化的过程中，是否考虑到条件属性和决策属性的依赖关系，可以将离散 化算法分为有监督式和无监督式。早期的离散化算法大部分是无监督的，其中著名的算 法有e q u a l w i d t h 和e q u a l f r e q u e n c y 算法【6 】，这些算法具有实现简单和计算耗能低的特 点，但离散化后的结果信息丢失严重，进行后续机器学习时精度偏低，在大多数情况下 难以满足研究人员的要求。而近几年的离散化算法大部分都是有监督的，其中有代表性 的是基于统计学的c h i 2 相关系列算法【7 - l o 】和基于信息熵的算法【1 。 ( 2 ) 自上而下式和自下而上式 根据添加断点的方式，可以将离散化算法分为自上而下式和自下而上式。自上而下 式算法在每次迭代过程中向断点集合中添加合适断点，就好像把区间不断的分裂，因此 也被称为分裂式，典型的分裂式算法有基于类属性关系的c a i m 算法【1 2 】。相反，自下而 上式算法通过迭代向断点集合中删除合适断点，就好像把区间不断的合并，因此也被称 为合并式，其中有代表性的是基于统计学的c h i 2 相关系列算法。 ( 3 ) 全局式和局部式 根据离散化算法在数据集中应用的范围可以分为全局式和局部式。全局式算法使用 数据集中的所有实例形成离散区间，往往与静态式算法结合使用。而局部式算法只使用 数据集部分实例形成离散区间，往往与动态式算法结合使用。通常情况下，全局式离散 化算法的精度要低于局部式离散化算法，但是，全局式离散化算法的执行效率要远远高 于局部式离散化算法，因此在处理大规模数据集时，往往采用全局式离散化算法。 离散化算法研究与应用 ( 4 ) 动态式和静态式 根据离散化算法和后续分类学习算法的执行关系，可以将离散化算法分为动态式和 静态式。动态式算法考虑属性间的依赖关系，离散化过程与分类学习同时进行。静态式 算法对每个属性单独考虑，而不考虑它们之间的依赖关系，离散化过程在分类学习之前 进行。 ( 5 ) 直接式和间接式 根据离散化算法中是否需要人为预先确定参数如离散区间的个数等，可以将离散化 算法分为直接式和间接式。直接式算法需要人为确定离散区间的个数，比如e q u a l w i d t h 、 e q u a l f r e q u e n c y 算法和i d d 算法【1 3 1 。而间接式算法能够自动完成离散化过程，通过迭 代过程形成区间，直到满足某一停止条件时结束离散化。现有的大部分常用的离散化算 法都是间接式的，比如c a i m 算法。 1 2 2 部分离散化算法介绍和比较分析 离散化算法发展至今，已经形成了多种不同的研究方式，比如基于类和属性关系的 c a i m 算法、基于统计学的c h i 2 系列算法和基于信息熵的算法等。如前文所述，大致 上可以把这些方法分为非监督和有监督两类。非监督的方法不考虑条件属性和决策属性 的依赖关系，如早先的等距离和等频率划分算法，还有近年来提出的核密度评估算、法【1 4 】 等。这些方法通常需要人为地确定划分区间的个数，或者需要预先给定一个参数。由于 没有考虑数据集决策表中的分类信息，利用这些方法获得的离散化结果一般难以满足研 究人员的要求。相反，有监督的方法在离散化的过程中考虑了类别的信息，不需要人为 给定参数，整个离散化过程完全是自动进行的，相比于非监督离散化算法，离散化结果 更加合理，并且在机器学习中也得到了更高的精度。鉴于有监督离散化算法的种种优势， 近年来出现的大部分离散化算法都是有监督的。本节简要介绍了六种离散化算法，其中 等距离算法、等频率算法和核密度评估算法是无监督的，而其余的算法都是有监督的。 ( 1 ) 等距离和等频率( e q u a l w i d t ha n de q u a l f r e q u e n c y ) 算法【6 】 这两种算法都是直接式的无监督离散化算法。如上文所述，所谓直接式算法，即需 要预先人为确定离散区间的个数。因此，在使用这两种算法时，研究人员都要事先输入 参数k 来确定离散区间个数。不同的是，等距离算法得到的划分区间具有相同的距离， 即每个区间的间隔是相等的：而等频率划分算法得到的划分区间具有相同的频率，即在 每个区间中出现的实例个数的相等的。 这两种算法都没有考虑信息表达系统的分类信息，一次获取所有断点值。应用这两 种离散化算法进行离散化处理往往会造成原有信息表达系统的信息丢失，因而使得离散 大连理t 大学硕+ 学位论文 化结果无法保障后续学习算法的有效性。这两种算法的时间复杂度为n l o g ( n ) ，其中 为数据集中实例的个数。 ( 2 ) 核密度评估( k e r n e ld e n s i t ye s t i m a t i o n ) 算法【1 4 】 2 0 0 7 年m a r e n g l e l lb i b a 等人提出了核密度评估算法。该方法是一种自下而上的、全 局的、直接式的无监督离散化算法。它利用非参数密度评估来自动选取离散区间，并采 用交叉验证的方式来确定离散区间的个数。该算法通过由当前断点和每个区间各自的核 评估密度得到的密度，对每个候选断点进行计算，从而选择离散断点。核密度评估算法 的时间复杂度为n l o g ( n ) ，其中为数据集中实例的个数。 ( 3 ) 基于信息熵( i n f o r m a t i o ne n t r o p y ) 的算法 1 9 9 3 年，umf a y y a d 等人提出一种基于信息熵的离散化算法【l5 1 。这种算法采用递 归的方式每次仅从单个条件属性的候选断点中选择具有最小信息熵的断点，直到满足某 种停止条件为止。该算法得到的断点数目较多，其时间复杂度为n l o g ( n ) ，其中为数 据集中实例的个数。 ( 4 ) 基于统计量z 2 ( p e a r s o n sz 2s t a t i s t i c s ) 的算法 首先1 9 9 2 年k e r b e r 提出了c h i m e r g e 算法【7 】，它是一种全局的、有监督的自下而上 的算法。该算法应用统计学原理通过检验z 2 分布的显著性水平来判断相邻区间是否应 该合并。但是，c h i m e r g e 算法需预先人为设定合适的显著性水平值和区间数量的上下限， 因此它并不是一种全自动的离散化算法。1 9 9 7 年l i u 等人对此进行了改进，提出了c h i 2 算法 8 】。该算法不需要人为预先设定显著性水平，而是采用令显著性水平值逐渐降低的 方法，最后通过检验数据集的不一致率来确定是否终止离散化过程。但是该算法没有考 虑自由度对离散结果的影响。因此，在此基础上，2 0 0 2 年t a y 等人对c h i 2 算法进行了 进一步的改进，提出了m o d i f i e dc h i 2 算法【9 】。该算法根据相邻区间的类别数，确定z 2 分 布显著性检验的自由度。2 0 0 5 年，s u 等人对m o d i f i e dc h i 2 算法进行了改进，并提出了 相应的e x t e n d e dc h i 2 算法【l o 】。该算法考虑了来源于现实世界中的数据集存在类重叠的 情况，并且采用数据集本身存在的不一致率作为离散化结束的条件。 ( 5 ) i d d ( i n t e r v a ld i s t a n c e b a s e dd i s c r e t i z a i t o n ) 算法 i d d 算法 1 3 】是由f r a n c i s c oj r u i z 等人在2 0 0 8 年提出的，与大多数有监督离散化算 法不同的是，它是一种直接的离散化算法，即需要人为输入参数来确定离散区间的个数。 同时，该算法既不是自上而下式也不是自下而上式，而是一次性找所有合适的断点，这 使得该算法在处理大规模数据集时具有很大的优势。该算法提出了一个名为相邻度 n e i g h b o r h o o d 的概念，并利用这个概念来计算两个相邻区间的距离，从而完成离散化过 程。该算法的另一个新颖之处是考虑了决策属性中不同值的顺序，使得该算法既能处理 离散化算法研究与应用 决策属性值是离散值的数据集，也能处理决策属性值是连续值的数据集。i d d 算法时间 复杂度为n l o g “) ，其中为数据集中实例的个数。 ( 6 ) 基于类和属性依赖度( c l a s s - a t t r i b u t ei n t e r d e p e n d e n c e ) 的算法 这类算法利用类与属性的关系建立二维矩阵，并通过从中提取的信息来衡量类与属 性的依赖程度，从而确定合适的条件作为离散化判别式。首先1 9 9 5 年jyc h i n g 等人提 出了c a d d ( c l a s s d e p e n d e n td i s c r e t i z e r a l g o r i t h m ) 算法【1 6 】，它是一种自上而下的离散 化算法。该算法没有给出初始的划分点集应如何确定，而且在如何进行区间的调整方面 也没有给出有效的方法，实验表明，以c a i r 值作为离散判别式也是不合适的，其会产生 过多的区间而造成训练过度。2 0 0 4 年l u k a s za k u r g a n 等人提出了c a i m ( c l a s s a t t r i b u t e i n t e r d e p e n d e n c em a x i m i z a t i o n ) 算法【1 2 】，它是一种全局的、静态的、自上而下的有监督 离散化算法。该算法以达到类与属性相关度最大化为目标，以c a i r n 值作为离散判别式， 算法的时间复杂度为n l o g ( n ) ，其中为数据集中实例的个数。 相比于其他有监督离散化算法，利用该算法得到的离散化结果在后续的分类学习中 表现的更好。但是，该算法存在着三个不足。首先，在离散化的过程中没有考虑到属性 的重要性；其次，缺乏对决策表不一致率的考虑；最后，c a i m 算法只考虑区间内含有 最多实例的类属性，而忽视了其他类属性的分布情况。这常常造成信息丢失，从而影响 到机器学习的精度。 本文将在2 - 3 节对c a i m 算法进行更详细的介绍。 1 3 本文的工作 本文针对基于类和属性依赖度的c a i m 离散化算法进行了改进，主要做了两点工 作： 第一，在传统c a i m 算法的基础上，本文提出了一种基于属性重要性和决策表不一 致率的算法怕p r o v e dc a l m 算法。该算法根据d s s t 差异相似集理论和决策表理论 来分别度量属性重要性和不一致率，对属性进行排序，是重要的属性得到充分离散化， 当决策表不一致率不再改变时停止对数据集进行进一步的离散化。通过使用c 4 5 和支 持向量机分类工具进行性能分析，本文提出的i m p r o v e dc a i m 算法得到了更高的分类识 别率。 第二，本文提出了一种新的基于类和属性依赖度的离散化算法一旯c a i m 算法， 该算法采用统计学中常用的名相关系数作为离散化判别式，避免了采用c a i r n 值作为离 散判别式时产生的问题。实验表明，见c a i m 算法在分类学习时得到了更高的分类识别 率。该算法与c a i m 算法具有相同的时间复杂度，可用于处理大规模数据集。 大连理工大学硕士学位论文 1 4 论文的组织 第一章，对离散化算法的现状和发展趋势进行了介绍，并重点阐述和分析了六种有 代表性的离散化算法。针对目前尚存在的一些缺陷，介绍了本文在这方面所做的一些工 作。 第二章，介绍了本文的相关工作，首先介绍了数据挖掘中涉及的数据类型以应用范 围，接着分析了离散化的相关概念和评价标准，然后简单介绍了分类学习的知识，最后 重点介绍了本文所要改进的c a i m 算法。 第三章，首先，阐述了信息表达系统中的不一致率和属性重要性等理论背景。然后， 分析了c a i m 算法存在的问题，并提出了一种基于属性重要性和决策表不一致率的算法 h p r o v e dc a i m 算法。最后，实验表明，应用本文提出的i m p r o v e dc a l m 算法得到 的离散化结果在分类学习时取得了更好的效果。 第四章，首先，对相关系数的概念进行了介绍，并重点举例说明了见相关系数的应 用。然后，针对c a i r n 判别式存在的问题，本文提出了一种基于类和属性依赖度的离散 化算法一旯c a i m 算法，该算法以五相关系数作为离散判别式。最后，实验表明，该 算法有效的避免了c a l m 算法存在的问题，在分类学习中取得了更好的效果。 最后，对本文作了总结，并就进一步需要研究的问题和研究方向进行了展望。 离散化算法研究与应用 2 相关工作 在数据挖掘领域中，常常会涉及到不同的数据类型。数据预处理过程能够将原始数 据转换为方便研究人员使用的数据形式。其中，为适应机器学习的需要，大部分连续型 数据需要被转换成离散型数据，因此，离散化过程已经成为数据预处理的一个重要方面。 本章是对相关背景理论的综述，主要介绍了数据、离散化和分类等知识，其中重点介绍 了本文要改进的c a i m 算法，为后续的工作奠定理论基础。 2 1数据 随着计算机技术和网络的迅速发展，每天都会产生大量的信息，而信息在计算机中 的表现形式就是数据。数据作为信息的载体，来源于人们对客观世界的认识。通常情况 下，由于人们对客观世界认识程度有所不用，因此数据的表现形式也往往多种多样，不 同表现形式的数据蕴含着不同程度的信息量。 例如，描述一户住宅的面积时，可以用2 0 0 平方米、2 0 0 5 平方米和2 0 0 5 5 平方米 等数字来描述，也可以用“小户型”和“大户型”等名词来描述。显然，这两种不同的 描述方式所包含的信息量丰富程度是不一样的。 对于前一种数据描述类型，我们称之为定量数据。随着精度越来越高，说明人们对 住宅面积的认识越来越清楚，并且包含的信息量也越来越丰富。这三个值之间存在数学 意义上的大小关系。而对于后一种数据描述类型，我们称之为定性数据，这两个值之间 不存在数学意义上的大小关系，只能说它们所表示的含义即住宅面积的大小。人们对“大 户型”的认识是很模糊的，不同的人对“大户型”会有不同的理解。一些人可能会认为 2 0 0 平方米以上才算是“大户型，而其他人可以会认为4 0 0 平方米以上才算是“大户 型 。因此“大户型 是一个很泛化的数据描述，它是定量数据在某一个合理区间内的 集合。相比之下，“2 0 0 平方米”比“大户型”更能反映出一户住宅的面积。换句话说， “2 0 0 平方米”比“大户型”含有更丰富的信息量。 根据统计学的观点，可以利用两种方法来区分数据类型。首先，根据数据性质可以 分为定性数据和定量数据；其次，根据数据度量标度级别可以分为定类数据、定序数据、 定距数据和定比数据【1 。7 1 。 2 1 。1 定性数据与定量数据 定性数据( 类别数据) ：针对数据的某种特性可以将定性数据被分成不同的类别。 一般情况下，可以对定性数据进行具有某种意义的排序，但是定性数据之间不能进行如 大连理t 大学硕十学位论文 加、减、乘、除等数学运算。定性数据数据在现实生活中广泛存在，如学生的成绩有优 秀、良好、及格；三原色有红、黄、蓝；季节有春、夏、秋、冬。 定量数据( 数值数据) ：与定性数据不同的是，可以对定量数据进行具有数学意义 的有序排列，并且定量数据之间可以进行数学运算。对定量数据进一步分类可以分为离 散型数据和连续型数据。离散型数据是由一些离散的数值组成，该数据类型不能取遍区 间值域上的所有值，而只能取在一些特定的离散点上。如一所大学的教授人数、每年出 生的婴儿个数等。与之相反，连续型数据是由一些连续的数值组成，该数据类型能够取 遍区间值域上的所有值。如人的体温，海平面的的高度等。 2 1 2 度量标度级别 数据也可以按照计算和度量方法分为四种度量标度级别：定类数据、定序数据、定 距数据和定比数据。 ( 1 ) 定类数据：根据定性的原则区分数据集中各实例类别的数据。定类数据的值 只能把数据集中的研究对象分类，也即只能区分研究对象是同类或是不同类，仅仅具有 = 与的数学性质。例如区分性别为男性和女性两类；区分教师职称为教授、副教授和 讲师三类；这些数据只能区分异同，属于定类层次。 ( 2 ) 定序数据：区别同一个类别中各实例等级次序的数据。定序数据能根据实例 的值进行具有数学意义的排列，也就是说定序数据具有 与 或 的性质，却不能度量出大于或小于的 数量或距离。 ( 3 ) 定距数据：区别同一个类别中各实例等级次序及其距离的数据。它能够精确 的测量同一类别中各实例大小次序之间的距离，定距数据除了具有前两种数据类型的特 性以外，还具有加减的性质，即可以用加减运算来测量各实例之间的距离。但是，定距 数据没有一个真正数学意义上的零值，也就是说定距数据中的零值不代表“没有 。比 如，摄氏4 0 度比3 0 度高1 0 度，摄氏3 0 度比2 0 度又高1 0 度，它们之间相差的距离相 等，但是摄氏零度并不代表没有温度。 ( 4 ) 定比数据：也是区分同一类别中各实例等级次序及其距离的数据。与定距数 据不同的是，定比数据具有一个真正的零值，因而它具有乘与除的数学性质。例如工龄 离散化算法研究与应用 和月收入这两个数据，既是定距数据也是定比数据。因为其零值是绝对的，可以作乘除 的运算。如a 的工龄是2 0 年，而b 的工龄是1 0 元，那么我们可以计算出前者的工龄 是后者的两倍。 无论从度量标度级别还是包含信息量多少的角度来说，定类数据都是最低的，而定 比数据是最高的，这四种类型数据呈递增趋势。将以上两种分类方法综合起来，可以看 出定性数据指的是定类数据和定序数据；定量数据指的是定距数据和定比数据。因此， 将度量标度级别高的数据转化为度量标度级别低的数据会导致原始信息的丢失。这也是 离散化过程中需要注意的方面。 2 1 3 数据挖掘中数据的预处理 数据预处理是数据挖掘中非常重要的一部分。由于现实生活中的数据库存储量巨 大，往往存在着噪声数据和丢失数据的情况，这会影响人们高效的使用数据信息。要提 高数据挖掘的质量，就必须提供准确、更有针对性的数据。在数据预处理过程中，可以 对原始数据进行清理和归纳等操作，得到干净、准确的数据供挖掘工具使用。因此，在 数据挖掘之前使用数据预处理技术可以显著地提高挖掘质量，并能减少实际挖掘所需要 的时间。 数据挖掘中数据预处理包括以下几个方面：数据集成、数据清洗、数据转换以及数 据归约，这些步骤是相互关联的【1 8 】。 ( 1 ) 数据集成( d a t ai n t e g r a t i o n ) 数据集成是数据预处理过程中非常重要的一个方面，是将不同来源与不同格式的数 据在逻辑上或物理上进行集成的过程。通过将多个文件或数据库系统中的数据进行整合 处理后，进行统一的存储。该部分主要涉及解决语义模糊性、处理数据中的遗漏和清洗 脏数据等。通过数据集成能够统一原始数据中的不一致情况和冗余，从而把原始数据在 最低层次上加以转换和聚集。 ( 2 ) 数据清洗( d a t ac l e a r i n g ) 数据清洗的目的是消除数据源中所存在的噪声以及纠正不一致的数据，处理遗漏数 据和清洗脏数据，去除空白数据域和知识背景上的白噪声，考虑时间顺序和数据变化等。 数据清洗可以用于填充空缺的值，平滑数据，找出孤立点并纠正数据的不一致性。 ( 3 ) 数据转换( d a t at r a n s f o r m a t i o n ) 数据转换主要是将数据转换为适合挖掘的数据形式。例如，属性数据可以规范化， 使得它们可以落入小区间，如从0 0 到1 0 。在现有的数据不能满足分析需要或者具体的 大连理工大学硕士学位论文 数据挖掘算法需要特殊形式的数据类型时，就需要应用数据变换过程。数据变换主要包 括离散化、平滑、聚集、规格化以及属性构造。 ( 4 ) 数据归约( d a t ar e d u c t i o n ) 数据归约的目的是缩小所挖掘数据集的规模，提高挖掘效率。某些情况下，数据集 中的部分属性对数据挖掘是没有意义的，不但会降低挖掘效率，还有可能会影响挖掘结 果。因此，在数据挖掘前需要对原始数据进行合理的数据归约是非常重要的。数据归约 主要包括数据立方聚集、维数归约、数据压缩以及数据块归约。 2 2 离散化 在详细说明具体的离散化算法之前，本节先描述了离散化的相关概念和评价标准， 并简单的阐述了离散化算法在数据挖掘领域中的重要意义。 2 2 1 离散化概念 设s = 为一决策表，其中u = 瓴，x 2o j 。) 为论域，c = a l , 口2 ，a 。) 和 d ) 分别为条件属性集和决策属性集。假设对于va c ，v o = 【l o , r o ) cr 是实值区间。 属性a 是值域圪上的一个断点可以记为有序对( c ) ，其中a c ，c 为实数集。令只是 z o 的子区间划分，即对于某一个整数k o ，e o 表达为：只= c o ，c ? ) ， c ? ，c ；) ， c 乏，c 乏+ 。) ) ； l o = c ； c 7 c ； c 乏 c 乏+ l = r o ，v o = c ；，c ? ) u c 7 ，c 2 a ) u u c 乏c a + l 】。 因此， p = u e o ( 口r ) 定义了一个新的决策表s p = ，对于vx u ， f o ，七。) ，f 尸( x 。) = i f ( x 。) c ? ，c ；a 。】。这样就把原来含有连续属性的决策表划分 成刀个n ， 其中d 。是连续属性a 的最小值，d 。是最大值。进而，属性a 中的每一个连续值就会被划 分到相应的区间，并被赋予一个唯一的离散值，从而完成离散化过程。 离散化本质上可归结为利用选取的断点来对条件属性的值域进行划分的问题。假设 某个属性有m 个属性值，则在此属性上就有m 一1 个断点可取。选取断点的过程也就是合 并属性值的过程。离散化过程可以适当减少信息冗余，同时降低对存储空间的要求，进 离散化算法研究与应用 而能够提高分类学习算法的执行效率和分类精度。然而，连续属性的最优离散化是一个 n p 完全问题【2 0 1 ，不同的离散化算法得到的结果往往存在差异。 2 2 2 离散化评价标准 由于现有的离散化算法大部分是静态式的，即离散化过程和机器学习过程是相分离 的。因此，在数据挖掘过程中，往往先是单独的进行数据离散化过程，而忽略了对后续 机器学习过程的考虑。这样，在离散化过程中可能会导致一些关键信息的丢失，给后续 的机器学习任务带来巨大的影响。 针对目前提出的各种离散化算法，用一个统一的标准来衡量它们的优劣是非常困难 的。这主要归结于以下三点原因： 第一，数据集的复杂性。现实生活中的数据集一般都是混合型数据，既包括离散型 数据也包括连续性数据。而通常不同连续属性之间的取值范围差别很大，数据之间往往 存在着复杂的依赖关系，对这些不同连续属性的数据进行归一化处理是不可能的，因此 很难选择出一个对所有数据集都有效的离散化算法。 第二，离散化算法的局限性。大部分离散化算法在设计时，只考虑了如何合理的选 取断点，而忽略了后续的学习算法。因此性能的优劣只有通过离散化结果在后续学习中 体现出来。也就是说离散化算法的优劣不仅与本身有关，而且还取决于后续的机器学习 算法。 第三，数据集的特殊性。同样的离散化算法应用到不同的数据集时，结果也存在很 大的差异，现在通常采用u c i 标准数