（计算机应用技术专业论文）聚类中的特征学习研究.pdf

聚类中的特征学习研究 摘要 人类要认识世界就必须区分不同的事物并认识事物间的相似性，聚类是按 照事物间的相似进行的一种无监督分类，是在对数据不作任何假设的条件下进 行分析的一种工具，聚类已广泛应用于各种工程和科学领域。特征的选择和特 征权值的选定对聚类效果有着较大的影响，而现有特征选择和特征学习又主要 体现在有监督学习中，因此，本文针对特征学习聚类展开了研究，主要工作如 下： ( 1 ) 研究分析了数据挖掘中聚类算法的现状及存在问题，重点阐明划分聚 类算法以及特征学习方法。 ( 2 ) 针对划分聚类算法对初始聚类中心选取敏感，并对特征权值的学习和 聚类质量有着较大的影响，因此，提出一最大距离和初始聚类中心选取法( 新 加入的初始中心与已选入的所有初始中心距离和最大) 。该方法能较好地将初始 聚类中心分在不同的聚类中，并能与划分聚类较能好地结合。 ( 3 ) 为体现数据各特征对类的分离贡献的不同，研究并分析了基于r e l i e f 算法的一些特征评价函数及其存在的问题，为本文特征评价函数的构造奠定的 基础和切入点。此特征评价函数在算法复杂度和类大小相差悬殊的情形下，对 特征的评价均有较好表现。 ( 4 ) 基于新的特征评价函数，运用于特征学习聚类中，以解决特征权值取 值不当对聚类产生的负面影响。并将特征学习聚类拓展到具有类属性数据聚类 中。通过实验，与传统聚类进行对比、分析，证明特征学习聚类算法在提高聚 类精度和特征学习上是可行和有效的。 关键词：聚类算法特征评价函数r e l i e f 算法特征学习聚类 r e s e a r c ho uf e a t u r el e a r n i n gi nc l u s t e r i n g a b s t r a c t w eh a v et od i s e e md i f f e r e n tk i n d so fo b j e c t sa n da n a l y z es i m i l a r i t y , i fw ew a n t t ok n o wo u rr e a l w o r l dw e l l c l u s t e r i n gi saf o r mo fu n s u p e r v i s e dc l a s s i f i c a t i o n a c c o r d i n gt os i m i l a r i t yo fo b j e a s ，a n di ti sa l s oaa n a l y s i st o o lu n d e rw i t h o u ta n y h y p o t h e s i s c l u s t e r i n gh a sb e e nu s e dw i d e l yi i ld i f f e r e n ts u b j e c t s c o n s i d e r i n gt h e i m p o r t a n c eo ff e a t u r es e l e c t i o na n df e a t u r ew e i g h t i n g , f e a t u r es e l e c t i o na n df e a t u r e l e a m i n ga l g o r i t h m sa v a l l a b l ew o r k i n gi ns u p e r v i s ec l a s s i f i c a t i o nm a i n l y , t h ef e a t u r e l e a r n i n gc l u s t e r i n gh a sb e e ns t u d i e da n da c c o m p l i s h e dt h i sc o n t r i b u t i o n sa sf o l l o w s ( 1 ) r e s e a r c ha n da n a l y z et h ep r o b l e m sa n ds t a t eo fc l u s t e r i n ga l g o r i t h m s i l l u m i n a t ec l u s t e r i n ga l g o r i t h m sb a s e do nd i v i s i o na n dt h em e t h o d so ff e a t u r e l e a r n i n g ( 2 ) b e c a u s ec l u s t e r i n ga l g o r i t h ma r es e n s i t i v et ot h ei n i t i a lc e n t e r so fc l u s t e r s ， w h i c ha f f e c t sf e a t u r el e a r n i n ga n dc l u s t e r i n gq u a l i t y , ai n i t i a l c l u s t e r i n g c e n t e r m e t h o d ( t h el o n g e s td i s t a n c es u m m a t i o n ) i sp r o d u c e d t h i sm e t h o dc a ns e p a r a t e i n i t i a lc l u s t e r i n gc e n t e r si nd i f f e r e n tc l u s t e r s ，c o m b i n et om a n yd i v i s i o nc l u m e r i n g a l g o r i t h m sb e t t e r ( 3 ) i no r d e rt oe m b o d yd i f f e r e n tc o n t r i b u t i o no fe a c hf e a t u r e ，w er e s e a r c ha n d a n a l y z ef e a t u r ec r i t e r i o na n di t sw e a k n e s sb a s e do nr e l i e fa l g o r i t h m s t h i se f f o r t s b u i l d st h ef o u n d a t i o no ft h ef o a m mc r i t e r i o nf u n c t i o na n dp o i n to u tt h er e s e a r c h d i r e c t i o n w i t hl o w e rc o m p l e x i t ya n de a s i e ru n d e r s t a n d i n g ，t h ef e a t u r ec r i t e r i o n f u n c t i o nc a nc o m b i n em a n y c l u s t e r i n ga l g o r i t h m si np r a c t i c a la p p l i c a t i o n ( 4 ) i nt h ed i s s e r t a t i o n ，b a s e do nt h en o v e lf e a t u r ec r i t e r i o nf u n c t i o n ，w ea p p l y t h ef u n c t i o ni n t of e a t u r el e a r n i n gc l u s t e r i n gt oc o u n t e r a c tt h en e g a t i v ea f f e c t sb y g i v e nf e a t u r ew e i g h t sw r o n g l y a n dw ee x t e n dt h ef e a t u r el e a r n i n gc l u s t e r i n g a l g o r i t h m i n t od a t a b a s e w i t h c a t e g o r i c a l a t t r i b u t i o n s s o m e e x p e r i m e n t sa r e c o n d u c e da n dc o m p a r et h er e s u l t st ot h a to ft r a d i t i o nc l u s t e r i n ga l g o r i t h m s t h e s e t e s te x p e r i m e n t sd e m o n s t r a t et h en o v e lf e a t u r el e a r n i n g c l u s t e r i n ga l g o r i t h mi s e f f e c t i v ea n df e a s i b i l i t yi np r o m o t i n gc l u s t e r i n gp r e c i s i o na n df e a m r el e a r n i n g k e yw o r d s ：c l u s t e r i n ga l g o r i t h m f e a t u r ec r i t e r i o nf u n c t i o nr e l i e fa l g o r i t h m f e a t u r el e a r n i n gc l u s t e r i n g i i 插图清单 图1 1 数据挖掘一般过程一2 图1 2 聚类的一般步骤5 图1 3 谱系示图6 图2 1k m e a n s 聚类过程1 4 图2 2 特征权值对聚类的影响1 8 图3 1 两类分离效果2 8 图3 2 两类间隙距离2 8 图3 3 样本在某特征下的密度分布2 9 图4 1 迭代次数与目标函数值关系3 4 图4 2 特征学习聚类过程3 5 v i 表格清单 表1 1 各聚类算法的比较 表4 1 不同初始中心选择的比较 表4 2 各算法聚类比较 表4 3k - m e a n s 和f l c 的目标函数值的比较 表4 3k - m e a n s 和f l c 的目标函数值的比较 表4 5 传统基于r d i e f 算法聚类结果 表4 6f l c 聚类结果 表4 7l e d 数据聚类结果 v i i 如卯鲳钔甜m地 一 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金胆王些太堂 或其他教育机构的学位或证书而使用过的材料与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：窆嘉色王签字日期：2 0 0 7 年f 工月7 日 学位论文版权使用授权书 本学位论文作者完全了解金妲王些盍堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金目b 王些盔 当! 一可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名 签字日期：2 0 0 7年f ，月 学位论文作者毕业后去向： 工作单位： 通讯地址： 工多8 泖 导师签名： 签字日 电话 邮编 阳罗日 ( 日 1j-ll 致谢 本人在撰写学位论文的过程中，自始至终得到了我的导师胡学钢教授的悉 心指导，无论从选题、定题，还是到收集资料、论文成稿，都倾注了胡学钢老 师的心血。在论文研究过程中，他总是及时地给我指点迷津、督促指导，对我 提出的问题总是耐心地分析和讲解。在此由衷感谢胡老师在学业指导及各方面 给予我的关心。胡老师以高度负责的工作责任心和精湛的专业水平指导着每一 位学生，他严谨的治学作风、渊博的专业知识、诲人不倦的教育情怀和脚踏实 地的科学态度必将使我终身受益，对我今后的工作、学习和生活产生深远的影 响。 感谢计算机学院和研究生部的全体教师，感谢他们的指导、关心和帮助。 感谢我的妻子和女儿多年来对我学习的支持和生活上的关心，是她们多年 来的辛苦付出和不断的鼓励使我能够克服种种困难，勤奋学习、刻苦钻研。 最后，向所有关心、支持和帮助过我的老师、同学、同事、朋友、亲人表 示真诚的感谢1 1 1 1 作者：吴艳文 2 0 0 7 年1 0 月 第一章绪论 本章首先阐明了本文所选课题的研究背景及其所具有的研究价值，对数据 挖掘，聚类分析的基本概念进行简要的介绍，然后指出本文的组织结构。 1 1 选题背景与本文研究意义 随着信息技术和数据库技术的迅猛发展，人们可以非常方便地获取和存储 大量的数据。而进入9 0 年代，全世界拥有的数据库及其所存储的数据快速增加， 人们受到“信息爆炸”、“混沌信息空间”( i n f o r m a t i o nc h a o t i cs p a c e ) 和“数 据过剩”( d a t ag l u t ) 的巨大压力。传统的数据分析工具( 如信息管理系统) 只 能进行一些表层的处理( 如查询、统计等) ，而不能获得数据之间的内在关系和 隐含的信息。为摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够 智能地自动进行数据转换成有用的信息和知识的技术和工具，对这种强有力的 数据分析工具的迫切需求使得数据挖掘技术应运而生。 聚类就是根据某种相似性准则，将样本空间分成多个子空间，使每个子空 间内部样本点尽可能相似，不同的子空间内样本之间差异尽可能大。聚类分析 作为统计学一个分支，已经广泛研究了许多年。而且，聚类分析已经广泛地应 用到诸多领域中，包括统计、机器学习、模式识别、数据分析、图像处理以及 市场研究。通过聚类人们能够识别数据密集和稀疏的区域，因而发现全局的分 布模式，以及数据属性之间的相互关系。在商务上，聚类能帮助市场分析人员 从客房基本信息库中发现不同的客房群，并且用购买模式来刻画不同的客户群 特征。在生物学上，聚类能用于推导植物和动物的分类。对基因进行分类，获 得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车 保险单持有者的分组，以及根据房屋类型、价值和地理位置对一个城市中房屋 的分级上发挥作用。 作为一个数据挖掘的重要功能，聚类分析作为一个独立的工具来获得数据 分布情况，观察每个类的特点，集中对特定的某些类进一步的分析。如对w e b 上文档进行分类，以发现信息。此外，聚类分析可以作为其它算法( 如关联分 析和分类) 的预处理步骤，这些算法在生成的类上进行处理。这样可以大大提 高算法的执行效率。因此，聚类分析已经成为数据挖掘领域中一个非常活跃的 研究课题【2 】。鉴于以上认识，本文对传统聚类算法以及特征学习进行研究和分 析，在些基础上提出了特征学习聚类。 1 2 数据挖掘概述 数据挖掘( d a t am i n i n g ，d m ) 与“数据库知识发现”( k n o w l e d g ed i s c o v e r y f r o md a t a b a s e s 。k d d ) 密切相关，就是从大量有噪声、不完整、甚至是不一致 数据集合中，挖掘出有意义的模式知识所涉及的概念与技术方法【1 5 】。数据挖掘 着眼于设计高效算法以达到从海量数据中发现知识的目的。 1 2 1 数据挖掘的背景知识 数据挖掘( d a t am i n i n g ) 简单地讲就是从大量数据中挖掘或抽取知识。其 定义1 q 为“数据挖掘是从一个大型数据库中抽取隐含的、事先未知的、具有潜 在的信息或知识的非平凡过程”。数据挖掘的全过程定义描述如下图“】： 数据库目标数据模式 巩固、运用知识 图1 1 数据挖掘一般过程 通过数据挖掘，可以从数据库中挖掘有意义的知识、规律、或更层次的信 息，并可从多角度进行浏览察看。所挖掘的知识可帮助进行决策支持、过程控 制、信息管理、查询处理等等。因此数据挖掘被认为是数据库系统中最重要的 前沿研究领域之一，也是信息工业中最富有前景的数据库应用领域之一。 数据挖掘在很多领域发挥积极作用，尤其在银行、电信、保险、交通、零 售等商业领域，企业市场营销中得到了比较普遍的应用，其中包括：数据库营 销( d a t a b a s em a r k e t i n g ) 、客房群划分( c u s t o m e rs e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、 背景分析( p r o f i l ea n a l y s i s ) 、交叉销售( c r o s s s e l l i n g ) 等市场分析行为，以及 客户流失性分析( c h u r na n a l y s i s ) 、客户信用评分( c r e d i ts c o r i n g ) 、欺诈发现 ( f r a u dd e t e c t i o n ) 等。以上通过收集、加工和处理涉及消费者大量消费习惯、 消费倾向和消费需求，进而推断出下一步消费群体或个体消费行为，然后，以 此为基础，对所识别的消费群体进行特定内容的定向营销，这与传统手段相比。 节省了营销成本，提高的营销效果，从而为企业带来更多的利润。 ( 1 ) 数据预处理 k d d 的处理对象是大量的数据，这些数据一般是存储在数据库系统中，是 长期积累的结果。但往往不适合直接在这些数据上进行知识挖掘，需要做数据 准备工作，一般来说，针对数据进行数据准备主要包括三个方面内容： 数据选择( d a t as e c t i o n ) 现实世界所有业务对象有关的内部和外部数据信息，并从中选择出适用于 数据挖掘的数据来。 数据清洗( 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 ) 其作用就是将来自多个数据源中的相关数据组合到一起 数据转换( d a t at r a n s f o r m a t i o n ) 将数据转换成个分析模型，这个分析模型是针对挖掘算法建立的，建立一 个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 数据预处理是k d d 的第一步骤，也是比较重要的步骤。数据准备是否做好 影响到数据挖掘的效率准确度以及最终模式准确性。 ( 2 ) 数据挖掘 数据挖掘是k d d 最关键的步骤，也是技术难点。研究k d d 的人员中大部 分都在研究数据挖掘技术，采用较多的技术有决策树、分类、聚类、粗糙集、 关联规则、神经网络、遗传算法等。数据挖掘根据k d d 的目标，选取相应算法 的参数，分析数据，得到可能形成知识的模式模型。 ( 3 ) 模型评估 上面通过数据挖掘得到的模式模型，有可能没有实际意义或实用价值，也 可能是其不能反映真实数据意义，甚至在某些情况下与事实相反，因而需要评 估，确定哪些是有效的、有用的模式。评估可以根据用户多年的经验，在些模 式也可用数据来检验其准确性，这个步骤还包括把模式以易于用户理解的方式 呈现给用户。 “) 巩固知识，运用知识 用户理解的、并被认为是符合实际和有价值的模式模型形成知识。在发现 知识的同时还要注意对知识做一致性检验，解决与以前得到的知识相互冲突与 矛盾的地方，使知识得到巩固。发现知识是为了运用，如何使知识能够得到运 用也是k d d 的步骤之一。运用知识有两种方法：一种是只需要看知识所描述的 关系或结果，就可以对决策提供支持另一种是要求对新的数据运用知识，由此 可以产生新的问题，而需要对知识做进一步的优化。 k d d 的过程可能需要多次的循环反复，重新调整，重新执行。 1 2 2 数据挖掘的分类 数据挖掘技术可以帮助获得决策需要的知识，所以对数据挖掘而言应能同 时搜索发现多种模式知识，此外数据挖掘应能挖掘出多种层次的模式知识。因 此数据挖掘研究产生了大量的、各种不同类型的数据挖掘系统。因此，需要对 数据挖掘系统给出一个清楚的分类。根据数据挖掘功能以及能够挖掘的知识类 型，可以分为关联分析、分类与预测、聚类分析、特征化和区分、异类分析、 演化分析等等【1 6 】。 关联分析( a s s o c i a t i o i la n a l y s i s ) 关联分析是从给定的数据集中发现频繁出现的项集模式知识。它展示了数 据间未知数据的依赖关系。根据关联性就可以从任一数据对象的信息来推断另 一数据对象的信息。关联性是一种统计意义上的关系，并以置信度因子衡量关 联的程度。因此，为了发现有意义的关联规则，需要给定两个闽值：最小支持 度和最小可信度。目前，关联分析研究已经从单一概念层次关联规则的发现发 展到多个概念层次的关联规则的发展。关联分析广泛应用于市场营销、事务分 析等应用领域。 分类与预测( c l a s s i f i c a t i o na n dp r e d i c t i o n ) 分类就是找出一组能够描述数据集合典型特征的模型，以便能够分类识别 未知数据的归属或类别。分类是最基本的一种认识形式，作为数据挖掘的一个 重要主题，数据分类在统计学、机器学习、人工智能等得到了较早的研究。分 类分析可采用多种形式来描述，其中主要有：分类规则( 一t h e n ) 、决策树 ( d e c i s i o nt r e e s ) 、数学公式、神经网络。在需要预测某数值属性值时，这样的分 类就称为预测。一般用预测来表示对连续数值的预测，而用分类来表示对离散 值的预测。 聚类分析( c l u s t e r i n ga n a l y s i s ) 聚类分析目的：“各集类内部数据对象间的相似度最大化且各聚类对象间相 似度最小化”。聚类分析与分类分析主要区别在于，分类分析为监督学习，而 聚类分析为非监督学习。而二者所采用的方法相差甚远。数据聚类是将物理的 或抽象的对象分成几个群体，在每个群体内部，对象之间具有较高的相似性， 而在不同的群体之间，则相似度比较低。一般地，一个群体就是一个类，它与 数据分类不同的是，聚类的结果主要是基于当前所处理的数据，我们事先不知 道类的结构及每个对象所属类别。数据聚类计算量巨大，其时间复杂度也比数 据分类大很多。后面我们对聚类的相关知识进行详细讨论。 在解决实际问题中，经常要同时使用多种模式。分类分析和特征提取是使 用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识， 因为在建立模式前数据结果是已知的，可以直接用来检测模式的准确性，模式 的产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数据 作为样本，另一部分数据用来检验、校正模式。聚类分析、关联分析、序列模 式分析则是非监督知识，因为在模式建立前结果是未知的，模式的产生不受任 何监督。 1 3 聚类分析概述 聚类是人类一项基本的认识活动。通过适当的聚类，事物才能便于研究， 事物内部的规律才可能为人类所了解掌握。聚类分析是指将物理或抽象对象的 4 集合分组为由类似的对象组成的多个类过程【l “。简单的说，就是认识别出一组 聚类规则，将数据分成若干类。它于分类分析不同，聚类分析在对数据对象划 分类别之前并不明确知道划分的规则，要通过聚类结果的分析才能最终得出。 由聚类所生成的簇( c l u s t e r ) 是一组数据对象的集合，这些对象于同一簇中对象 相似，与其他簇中的对象相异或称簇内较大的相似性和簇间较大的相异性。 在机器学习中，聚类称为无监督或无导师归纳。因为和分类学习比，分类 学习的数据对象有类别标记，而聚类的数据对象则没有标记，需要由聚类学习 算法来自动确定。所以在聚类分析中，首先要给出有关论域中各元素相似性的 一个度量( 如相似函数) ，然后给出一个聚类的原则，根据其相似性和所给的聚 类原则进行聚类，求出某最优原则下的一个“最优”解。 1 3 1 聚类分析的背景知识 聚类其实质是寻找隐藏在数据 中不同的数据模型，能实现样本空 间的盲分类 3 8 1 。聚类广泛应用于统 计、机器学习、模式识别、数据分 析等领域，聚类分析已成为数据挖 掘研究中一个非常活跃的研究领 域。 目前已有的且应用到多个领域 的聚类算法多达几百种。处理对象 从一般数据库到大规模数据库，从 外存储数据到实时数据流、从低维 数据空间到高维数据空间、从数字 或类属性到多种属性数据等等。但 不同算法有着各自不同的侧重点 聚类算法的一般步骤 聚在分析算法一般经过特征提 取、聚类策略、选取阈值三个步骤： ( 1 ) 特征提取。我们一般要从样 特征提取 ( 知识领域) 聚类策略 ( 计算领域) 选取阈值 ( 知识领域) 图1 , 2 聚类的一般步骤 本中提取我们感兴趣的特征，使用这些特征进行聚类分析计算，特征的选取将 直接影响到聚类的结果，如果我们第一步就选取与聚类要求无关的量，即使后 继步骤多么正确，都将会导致错误的聚类结果。合理的特征选取应当使得分类 结果中同类样本距离较小，异类样本距离较大。我们必须去除我们不感兴趣的 特征，但这些特征往往具有明显的个性，数据千差万别为了使运算方便，往往 把这些数据映射n o ，1 1 区间，即规格化。我们说的特征提取，一般包括从样本 提取原始特征并对其进行规格化。规格化后的数据一般是n x m 矩阵，即1 1 个样 本，每个样本有n l 维特征。这矩阵中的元 素均是介于 0 ，1 1 之间的数据。 ( 2 ) 聚类策略。根据聚类分析的需要合 理选取聚类算法进行聚类运算。目前聚类 分析算法有数千种之多，但很多算法仍不 成熟，选取什么聚类分析算法将直接影响 聚类的结果和结果的有效性。聚类策略实 际上是根据样本的特征对样本进行归类， 经过规格化的数据实际上已没有实际意 义，聚类过程不需要有相关知识领域的专 家参与。聚类结果可以画成一个谱系图。 一 l f 。= 。：j ? 寸 ll ni 23456 7 ( 3 ) 选取阈值。这一步我们要选取合理 的阙值，由于分类要具有现实意义，阙值的选取往往需要有领域专家经验和领 域知识，结合具体情况和应用场所决定阙值的大小，没有领域专家的参与，仅 仅根据聚类谱系图寻找阈值，或者求最小生成树，往往不能得到满意的结果。 领域专家结合领域知识往往可以进一步分析数据，从而加深对样本的了解。 样本矩阵与差异矩阵 设有n 个待分类的样本，有m 个特征指标，得到一个n x l l l 样本矩阵x ，是 一个对象属性结构。如式( 1 3 1 ) 所示： x = 工】1x 1 2 x2 1工2 2 ) h i , x n 2 x l m 一工2 m ： x n t n 为了对它进行分类，我们称矩阵x 中每一行为一个样品，矩阵中的每一列 称为一个特征指标，如第j 列指标为x l i ，x 2 j x 咖换言之，我们研究的对象一样 品，其特征可用m 个指标来表示。从向量空间的观点看，样品实质上就是m 维 空间上一个点。 差异矩阵是一个对象一对象结构，它存放所有n 个对象彼此之间所形成的差 异，采用n x n 矩阵表示，如式( 1 3 2 ) 所示： o d ( 2 ，1 ) 0 d ( 3 1 ) d ( 3 ，2 ) 0 d ( n ，1 ) d ( n ，2 ) 0 ( 1 2 ) 其d ( i , j ) 表示对象i 和对象j 之间的差异。许多算法都是基于差异矩阵进行 6 聚类分析的。如果数据是通过样本矩阵给出需通过先转换为差异矩阵，才能进 行聚类。 对数据规格化计算方法的分析 由于1 t 1 个指标的量纲和数量级不同，直接利用原始的数据进行计算，可能 导致某些数量级大的特征指标对分类的作用较大，降低甚至排斥某些数量级较 小的特征的作用，导致一个指标只要改变一下单位，也会改变分类结果。所以， 必须对原始数据进行无量纲处理，使每一个指标统一于某种相同的数据特征范 围。常见规格化方法有： ( 1 ) 标准差规格化x 0 = x # - - x # ( 1 3 ) 四 其中石2 砉喜勒o j = j i l _ 嘶一纠2 ( 2 ) 极大值规格化】【i i = _ _( 1 4 ) 鼢“ 其中x j 。：= m a 】【 x l j ，x 2 j ，x j ) ( 3 ) 极差规格化x 日= 生! 坐l ( 1 。5 ) x i 瑚x x ir a i n 其中x j 同上，x j m i x = m i x x l j , x 2 j ，舳) ( 4 ) 均值规格化x l j = x _ - - l ( 1 6 ) x j ( 5 ) 中心规格化x 日= x 日- i ( 1 7 ) 样本问。相似度”度量距离的计算方法 设一分类的问题有n 个待分类的样本，有m 维特征指标，即数据集 x 尸 x l x 2 , x n ) c r ”；x k - - - ( x k l , x k 2 ，x h ) r m ，x k j 为x k 样本点的第j 维空间特 征。 这时，每个样本可看成m 维空间中的一个点，1 3 个样本就组成i n 维空间中 的n 个点，我们很自然就用各点之间的距离来衡量各样本之间的靠近程度。 d ( x i , x j ) 为样本点x i 与x j 之间的距离，其满足下列三个条件 ( 1 ) d ( x i , x j ) - 0 且d ( x b x j ) = o 当且仅当x i = 码 距离为非负数 ( 2 ) d ( x l ，x i ) = d ( x j ，x i ) 对象之间的距离为对称函数 ( 3 ) d ( x i ，x j ) d ( x i ，x k ) + d ( x k , x j ) 三角不等式 在聚类分析中常用的距离计算公式有 m i 雌离懈，= 除唰1 9 i 绝对距离d ( x i ，x j ) = 1x n - x q k = l e u c i a 距离d c x t ，均，= 薹i x “一石1 2 j ( 1 8 ) ( 1 9 ) ( 1 1 0 ) c h e b y s h e v 距离d ( x i ，x j y = m a x l x 自一工目i ) ( 1 1 1 ) r1 上 方差加权距离d ( x j 驴瞎k 也丢k 型1 9 ( 1 1 2 ) i - 1 u i 其中蠢为第k 特征的方差 m a h a l a n o i s 距离d ( x i ，x j ) = ( x i - x j ) t s j ( x i - x j ) ( 1 1 3 ) 其中s 为m 个指标协方差对角阵 ( 1 1 4 ) l a n c e 距离d ( x 妒薹篙五引 ( 1 1 5 ) 对相似度计算方法的研究 当对n 个变量进行聚类时，用相似系数来衡量变量之间的关联程度，一般 称r i j 为变量x i 和x j 间的相似系数。r i j 越接近于1 ，说明变量】【i 和x j 问的关系越 密切，反之，r i j 越接近于0 ，则变量x i 和x j 间的关系越疏远，文献【1 硝列举了以 下1 3 种常用的方法，分别为：海明距离法、欧氏距离法、切比雪夫距离法、绝 对值倒数法、绝对值指数法、指数相似系数法，兰氏距离法、数量积法、夹角 余弦法、相关系数法、最大最小法、算术平均最小法、几何平均最小法。 1 3 2 聚类算法分类 在聚类分析算法可以分为以下几大类： 基于划分方法 给定一个包含n 个对象或数据集，划分方法将数据集划分成k 个子集，其 中每个子集均代表一个聚类。每个子集满足以下条件：l 、每子集至少应包含一 个对象；2 、每个对象必须只能属于某个子集( 但在模糊划分中可以放宽) 。如： k - m e a n s 、k - m o d e s 等。 基于层次方法 层次方法就是通过分解给定的数据对象集来创建一个层次。根据层次分解 形成的方式，可以将层次方法分为白下而上和自上而下两种类型。自下而上的 层次方法从每个对象均为一个单独的组开始，逐步将这些对象进行合并，直到 组合到层次的顶端或满足终止条件为止。自上而下方法从所有对象均属于一个 组开始，每次循环将其分解为更小的组，直到每个对象构成一组或满足终止条 件为止，如b i r c h 、c u r e 、c h a m a l e o n 等。以上两种方法均需用户指定所 期望的聚类个数作为聚类过程的终止条件。 例如，c u r e ( c l u s t e r i n gu s m gr e p r e s e n t a t i v e s ) 算法首先把每个数据点看 成一类，然后再合并距离最近的类直到聚类个数为所要求的个数为止。它对类 的表示方法进行了改进，回避了用中心和半径来表示一类，而是抽取固定数量 且分布较好的点作为描述此类的代表点，并将这些点乘以一个适当收缩因子。 使它们更靠近类的中心。将一个类用多个代表点来表示，可使的聚类的外延向 非球形的形状扩展，同时，收缩因子使噪声对聚类影响减小，因此，c u r e 对 异常数据表现得更鲁棒。 基于密度方法 基于密度概念的聚类方法实际上就是不断增长所获得的聚类直到“邻近” 密度小于一定阈值为止。如d b s c a n 、o p t i c s 等，这种方法可以用于消除数 据中的噪声，以及帮助发现任意形状的聚类。 例如，d b s c a n ( d e n s i t y - b a s e ds p a t i a lc l u s t e r i n go f a l g o r i t h mw i t hn o i s e ) 是一组“密度连接”对象，以实现最大化的“密度可达”。d b s c a n 检查数据 库中每个点的近邻，若一个对象p 的e 近邻包含多于m i n p t s ，就创建包含p 的新聚类。d b s c a n 接下来根据这些核对象，循环收集“直接密度可达对象”， 其中涉及若干次“密度可达”聚类的合并。当各聚类再无新对象加入时，聚类 结束。 基于网格方法 这种方法就是将空间划分成有限数目的单元以形成网格结构。所有聚类操 作均是在这一网格结构上进行。例如，s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 算 法是一个基于网格多分辨率的聚类。它将究竟划分为方形单元，不同的层次方 形单元对应不同的层次分辨率。高层次单元被分解形成一组低层次单元。而 c l i q u e ( c l u s t e r i n gi nq u e s t ) 聚类方法。将基于密度方法与基于网格方法结 合在一起，它对处理大数据库中的高维数据比较有效。 基于模型方法 这种方法就是将每个聚类假设一个数据模型，再去发现符合相应数据模型 的数据对象。常见基于模型的聚类方法有：利用概率参数来帮助确定概念或聚 类的统计方法，以及将每个聚类描述成一个例证，每个例证作为聚类的一个典 型的神经网络方法。以下是各聚类算法的比较。 表1 1 各聚类算法的比较 聚类算法算法效率 发现聚类类型异常数据的敏感性 输入顺序敏感性 b 限c h 高凸形或球形不敏感不太敏感 d b s c s n 一般任意形状敏感敏感 c u r e 较高 任意形状不敏感不太敏感 k - m e a n s 较高凸形或球形敏感敏感 s t 呵g 一般任意形状不敏感不敏感 c l i q u e 较低凸形或球形 一般 不敏感 1 3 3 聚类算法研究面临的挑战 聚类算法研究是一个富有挑战的研究领域，它的些潜在应用对聚类算法 提出了特别的要求【1 0 】： ( 1 ) 可扩展性( s e a l a b i u t y ) 。实际应用要求聚类算法能够处理大数据集，且 时间复杂度不能太高，消耗的内存空间有限，目前为将算法应用到超大数据库 ( v l d b ) 领域，研究人员已进行了许多有益的尝试，包括；增量式挖掘、可靠的 采样、数据挤压( d a t as q u a s h i n g ) 等。利用采样方法进行聚类分析可能得到一个偏 差的结果，而数据挤压技术首先通过扫描数据来获得数据的统计信息，然后在 这些统计的基础上进行聚类分析。比如b i r c h 等算法中使用c f 树就是属于数 据挤压技术。 ( 2 ) 能够处理不同类型的属性。现实中数据对象已远远超出关系型数据的范 畴，比如空间数据、多媒体数据、遗传学数据、时间序列数据、文本数据、万 维网上的数据、以及目前逐步兴起的数据流，这些数据对象的属性类型往往是 由多种数据类型综合而成的。但许多算法却针对某种数据类型而设计的，难以 实现对多种数据类型同时处理。 ( 3 ) 能够发现任意形状的簇。许多聚类算法只能发现具有类似大小和密度的 圆形或球形聚类，而实际一些聚类是任意形状，因此设计能发现任意形状和大 小的类的聚类算法是很重要的。 ( 4 ) 尽量减少用于决定输入参数的领域知识。许多聚类算法需要用户输入聚 类分析中需要的一些参数，而这些参数对聚类结果有明显的影响，但这此参数 往往又是难以决定的。这不仅构成对用户的负担，同时又使聚类质量难以控制。 ( 5 ) 能够处理噪声数据及孤立点。在现实世界的数据库中包含异常数据、数 据丢失、噪声数据是极正常现象。如果一聚类算法对这样的数据敏感，势必造 成较差的聚类效果。 0 ( 6 ) 对输入的数据记录的顺序不敏感。一些聚类算法对输入数据的顺序敏 感，即不同的输入顺序导致不同的聚类结果，这也是聚类算法努力需要避免的。 ( 7 ) 高维性( h i g h d i m e n s i o n ) 。许多算法在二维三维这样低维有较好的处理 能力，但在处理高维空间中，特别在高维稀疏或怪异分布的数据对象表现不佳。 随着维数的增加，使提数据分布非常稀疏，不相关属性的出现频率及数量也会 增加，最后导致数据空间中几乎不存在簇。其次，高维使得在低维中很有效的 区分标准在高维空间中失效了，譬如在高维空间中，数据点到最近邻居的距离 与到其他点的距离没有多少区别，从而导致最近邻查询在高维空间中不稳定。 能处理高维数据已成为聚类研究的一项挑战。 在实际应用中由于缺少形成模式过程的知识，或者由于实际工作中的困难， 我们往往只能用没有类标签的样本集进行工作，即使用无监督学习方法( 聚类) 。 然而无论是有监督的分类学习还是无监督的聚类，样本的特征选择强烈地影响 到分类器的设计及其性能。因此，特征选择和学习是模式识别一个关键问题。 由于在很多实际问题中常常不容易找到那些最重要的特征，特征选择和学习的 基本任务是如何从许多特征中找出那些最有效的特征，以及各特征在模式识别 过程中的地位( 权值) 。 1 4 特征的选择、提取与学习 特征的选择、提取是从许多特征中找出那些最有效的特征，而特征学习是 对从多特征进行有效性度量。任何识别过程的第一步，不论用计算机还是由人 去识别，都要首先分析各特征的有效性。显然特征选择、提取和学习对分类器 的性能至关重要。 特征形成根据被识别的对象产生一组基本特征，它可以计算出来的，也 可以是用仪器或传感器测量出来的，这样产生出来的特征叫做原始特征。 特征提取原始特征的数量可能很大，或者说样本处于高维空间中，通过 映射( 或变换) 的方法可以用低维空间来表示样本，这个过程叫做特征提取。 映射后的特征叫做二次特征。所谓特征提取在广义上就是一种变换。著y 是测 量空间，x 是特征空间，则变换a ：y x 就叫做特征提取器。 特征选择从一组特征中挑出一些最有效的特征以达到降低特征空间维数 的目的，这个过程叫做特征选择。最简单的特征选择方法是根据专家的知识挑 选那些对分类最有影响的特征，另一个可能是用数学的方法进行筛选比较，来 找出最有分类信息的特征。 特征学习通过对样本进行分析、总结、归纳，以提高对特征的认知能力， 从而得出在分类或聚类过程中各特征对类的分离度贡献大小，即进行特征有效 性度量。 通常我们希望找出一些实用的标准来衡量各类间的可分离性，我们对可分 离性的判据希望满足以下几条要求： ( 1 ) 与错误概率有单调关系，这样使判据取最大值的效果一般来说错误概率 也最小。 d ( 2 ) 当特征独立时有可加性。即j ( x l ，x 2 ，x d ) = j ( x k ) 西 ( 3 ) 单调性，即加入新的特征时判据不减少。 j ( x l ，x 2 ，x a ) j ( x l , x 2 , x d ，) 时1 ) 特征提取常见方法有：按欧氏距离度量进行特征提取。按概率距离判据的 特征提取，用散度准则函数的特征提取，基于判别熵最小化特征提取等。而特 征学习和选择往往不能严格区分，目前特征选择研究具有一定深度和广泛性， 其常见方法有：最优搜索算法，次优搜索法，模拟退火算法，t a b u 搜索算法， 遗传算法等。 1 5 本文的研究内容与组织结构 本文认真研究和分析了聚类过程中特征的学习以及特征学习对聚类性能的 影响。充分地研究了数据挖掘技术中的聚类方法，并给出了聚类的相关概念和 聚类的一般步骤、样本间相似性度量的各种方法，尤其对基于划分的聚类算法 进行了认真分析和研究，指出它们各自的不足和优点。结合特征学习在聚类中 的重要地位，通过对r e