（教育技术学专业论文）基于模糊聚类的非监督学习研究.pdf

摘要 学习是人类智能的主要标志和获得智慧的基本手段，是人类具有的一种重要智能行为。 在机器学习中，学习性能的好坏是衡量一个学习系统优劣最重要的指标。作为非监督学习 方法的模糊聚类分析已成为机器学习研究的热点，为提高和改善机器学习性能提供了良好 的理念支持与技术手段。研究模糊聚类算法对于提高和改善机器的学习性能具有重大的理 论和现实意义。 在模糊聚类算法中，由于模糊c 一均值聚类算法( f u z z y c - m e a n c l u s t e r i n g a l g o r i t h m ， f c m ) 计算简单，具有比较直观的几何意义，在许多领域获得了非常成功的廊心。然而基 于传统目标函数的f c m ，采用迭代的爬山技术来寻找展优解，本质上是一种局部搜索算法。 因而其存在着两大致命的问题：一是处理人数据量费时，- 二是对数据初始化敏感，容易陷 入局部极小值。 对此，本论文运用实验和比较方法，着重从以下几个方面对f c m 加以改进： l 、在提高f c m 算法对大数据量的聚类速度方面，通过多次随机取样聚类与数据约减 相结合，以减少f c m 算法收敛所需的迭代次数与运算时间：为了提高f c m 算法的聚类止 确率，对模式分类作出不同贡献的各维犄祉进行加权选择，使得聚类结果更好。 2 、由丁二f c m 会陷入局部最优化，论文采用遗传算法加以解决。将遗传算法与f c m 结合产生基于遗传算法的模糊c 均值聚类算法g f c m ，充分发挥f c m 的局部搜索和遗传 算法的全局搜索能力，提高算法聚类正确率。 3 、针对f c m 对人数据量处理速度慢的缺点，运用神经网络技术改进模糊聚类算法。 将自组织映射神经网络( s e l f - o r g a n i z i n gf e a t u r em 印，s o m ) 与f c m 结合，产生基丁s o m 的模糊c 均值聚类算法f l c c n ，利_ l js o m 的并行计算，以提高聚类算法的速度和效果， 实验结果表明算法有效。 通过对f c m 算法的上述改进，以弥补其局限性，使得算法更具合理，从而减少聚类 时间，提高聚类效果，以此提升非监督学习能力、效率与稳定性，优化机器学习性能。 关键词：非监督学习；模糊聚类；f c m ：遗传算法；神经网络 a b s t r a c t l e a m i n g i s t h e h a l l m a r k o f h u m a n i m e l l i g e n c o 。t h e b a s i c n l e a n s t o g e t h u m a n i n t e l l i g e n c e ，a n d a l li m p o r t a n tb r a i n p o w e ra c t 1 1 ”l e a r n i n gq u a l i wi st h em o s ti m p m t a n ti n d i c a t o ro fq u a l i t yo fa l e a r n i n gs y s t e mi nm a c h i n el e s r a i n g f u z z yc l u s t e r i n ga n a l y s i si so n eo f n ns u p e r v i s e dl e a r n i n g m e t h o d so fm a c h i n el e a r n i n gw h i c hh a sb c c o n l eah o tt o p i co fm a c h i n el e a r n i n gr e s e a r c ha n d p r o v i d e s a l le x c e l l e n tm e a n st oe n h a n c ea n di m p r o v et h ep e r f o o fm a c h i n el e a r n i n g t e c h n o l o g y t h er e s e a r c ha b o u tf u z z yc l u s t e r i n ga l g o r i t h mh a sg r e a tt h e o r e t i c a la n dp r a c t i c a l s i g n i f i c a n c et oe n h a n c er e s e a r c ha n di m p r o v et h el e a r n i n gp e r f o r m a n c e a sf c m a l g o r i t h mh a sm e r i t sl i k es i m p i ea n dv i s u a lg e o m e t r yi nf u z z yc l u s t e r i n ga l g o r i t h m s a ni th a sb e e na p p l i e ds u c c e s s f u l l yi nm a n ya g c a s b u tb e c a u s eb a s e do nt h et r a d i t i o n a lf u n c t i o n o ft h ec l i m b e r sf c mi t e r a t i v et e c h n i q u et of i n dt h eo p t i m a ls o l u t i o n ，al o c a ls e a r c ha l g o r i t h m e s s e n t i a l l y , s ot h e r ea r ct w of a t a lp r o b l e m s ：o n ei ss l o w i n gw h i l ed e a l i n gw i mal a r g ea m o u n to f d a t a ，t h es e c o n di ss e n s i t i z i n gt ot h ei n i t i a l i z a t i o no f d a t aa n de o s i l yg e t t i n gi n t ol o c a lm i n i m u m i nt h i sr e g a r d ，t h i sp a p e rf o c u s e so nt h ef o l l o w i n gw a y st oi m p r o v eo nt h ef c ma l g o r i t h m u s i n gc o m p a r e da n de x p e r i m e n t a lm e t h o d s ： 1 t os p e e du pf c mc l u s t e r i n gv e l o c i t yi nl a r g ea m o u n t so fd a t a r e d u c et h en u m b e ro f i t e r a t i o n sr e q u i r e df o rc o n v e r g e n c ea n dt h ec o m p u t i n gt i m eb yc o m b i n i n gs e v e r a lr a n d o m s a m p l i n gd a t ac l u s t e rw i t hd a t ar e d u c t i o n ；t oi m p r o v et h ef c ma c c u r a c yr a t e w ec h o i c e c h a r a c t e r i s t i c sb yw e i g h i n gt h e i rc o n t r i b u t i o n st op a t t e r nc l a s s i f i c a t i o na n dg e tb e t t e rr e s u l t 2 s o l v i n gt h ep r o b l e mt h a tf c mi sp r o n et of a l li n t ot h el o c a lo p t i m i z a t i o nu s i n gg e n e t i c a l g o r i t h m 。ac o m b i n a t i o no fg e n e t i ca l g o r i t h m sa n df c mc r e a t e sf u z z yc - m e a n sc l u s t e r i n g a l g o r i t h mg f c mb a s e do ng e n e t i ca l g o r i t h m s ，w h i c hc a ng e tb o r e rr e s u l ta n dr a i s ea c c u r a c yo f c l u s t e r i n gf o rm a k i n gf u l lu s eo ff c ml o c a ls e a r c hv i r t u ea n dg e n e t i ca l g o r i t h m s a b i l i t yo f g l o b a ls e a r c h 3 a st ot h ed e f e c tt h a tf c m p r o c e s s e sl a r g ea m o u n t so fd a t as l o w l y , t h ea r t i c l eu s en c n r a l n e t w o r kt e c h n o l o g yt oi m p r o v ef u z z yc l u s t e r i n ga l g o r i t h m ，c r e a t i n gt h ef u z z yc - m e a n s c l u s t e r i n ga l g o r i t h mf k c nb a s e do ns o ma n du t i l i z e sp a r a l l e lc o m p u t i n go fs o m t oe n h a n c e t h es p e e do ft h ec l u s t e r i n ga l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h i ni s e f f e c t i v e 1 1 l ea b o v ei m p r o v e m e n t sa b o u tf c m a l g o r i t h mc o m p e n s a t ef o rt h el i m i t a t i o n so ff c m a n d m a k et h ea l g o r i t h mm o r er e a s o n a b l ef o rr e d u c i n gt h ec l u s t e r i n gt i m ea n dr a i s i n gt h ec l u s t e r i n g e f f e c t i v e t h e r e b y , t h eu n s u p e r v i s e dl e a r n i n g sa h i l i t y , e f f i c i e n c ya n ds t a b i l i t ya r er a i s e da n dt h e p e r f o r m a n c eo f m a c h i n el e a r n i n gi so p t i m i z e d k e y w o r d s ：u n s u p e r v i s e dl e a r n i n g ；f u z z yc l u s t e r i n g ；, f c m ；g e n e t i ca l g o r i t h m s ；n e u r a l n e t w o r k s i i 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名：盥：盔堕 日 期：a 圃：竺j ! 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅：有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名：醢丝笠 日 期：泣丑簟k 1 1 问题提出 第一章绪论 当前，人工智能研究的关键技术和热点方向之一就是机器学习( m a c h i n el e a r n i n g ) ， 它与计算机科学、心理学、认知科学、控制论、神经科学等各种学科都有着密切的联系， 牵涉的面很广，许多理论及技术上的问题尚处丁研究之中。 机器学习就是要使计算机能模拟人的学习行为，自动地通过学习获取知识和技能，不 断改善性能，实现自我完善。1 作为人i ：智能的核心研究领域之一，它不但有深刻的理论内 蕴，也是现代社会中人f j 获取和处理知识的重要技术来源。2 其研究丁作主要嗣绕学习机理、 学习方法、面向任务这二个基本方面而展开研究。学习是系统中的任何改进，这种改进使 得系统在重复同样的i ：作或进行类似的r 作时能完成得更好。 学习是人类智能的主要标：和获得钾慧的基本手段，3 是人类具有的一种重要智能行 为。机器学习是一个有特定目的的知识获取过程，其内部表现为从朱知到已知这样一个知 识增妖过程，其外部表现为系统的某些性能和适应性的改善，使得系统能完成原米不能完 成或更好地完成原来可以完成的任务。在机器学习中，学习性能的好坏是衡量一个学习系 统优劣最重要的指标。如何提高和完善机器的学习性能是当今机器学习研究的重要课题。 模糊聚类分析( f u z z yc l u s t e r i n ga n a l y s i s ) 作为统计学习的一个分支和一种北监督学 习方法已成为机器学习研究的热点，为提高和改善机器学习性能提供了良好的理念支持与 技术手段。为此，研究模糊聚类算法( f u z z y c l u s t e r i n g a l g o r i t h m ) 对于提高和改善机器的 学习性能具有重大的理论和现实意义。 1 1 乍监督学习是当前机器学习研究的重要方向 鉴丁学习能力是智能体应具有的基本特性，机器学习作为提高机器智能的重要手段， 受剑研究人员的广泛注意，成为人一i ：智能领域的研究核心之一。机器学习不仅在人j ：智能 领域，而且在认知科学、心理学、教育学、哲学以及其它相关领域中受到，“泛注意。学习 就是系统在不断重复的i ：作中对本身能力的增强或改进，使得系统在下一次执行同样或相 类似的任务时会比原米做得更好或效率更高。对于学习性能的优化是机器学习首先要解决 好的问题。 非监督学习( u n r v i s e dl e a r n i n g ) 是机器学习的一个重要学习方法，它是指不需要 单独的离线训练过程，也没有带标记的训练数据集，一般用来对数据集进行分析，如聚类， 通过学习从中抽取出相应的内在规律与规则，使得机器做山更为合理的决策。非监督学习 的理论研究一直是机器学习研究的重点和热点，这些研究对于我们理解机器学习的学习机 理以及人机交互都具有重要的理论意义。显然研究非监督学习的各种方法是实现提高和完 善机器学习能力的重要途径和手段。 2 模糊聚类是非监督学习的重要方法 聚类就是按照事物间的相似性进行区分和分类的过程，在这一过程中没有教师指导 因此是一种非监督的学习。聚类分析是用数学方法研究和处理所给定对象的分类。 传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某个类中，具有 1 m i t c h e l l 删机器学习北京：机械工业出版社2 0 0 3 2 王珏，周志华，周傲英机器学习及其应用北京：清华大学出版社，2 0 0 4 ：v 3 蔡自兴，徐光佑人工智能及其应用( 第三版研究生用书) 北京：清华大学出版社，2 0 0 4 ：1 3 非此即彼的性质。而模糊聚类则得到了样本属于各个类别的不确定性程度，表达了样本类 属的中介性，能更客观地反映现实世界，从而成为聚类分析研究的主流。模糊聚类属于机 器学习中的非监督学习，它不需要训练样本，可以直接通过机器学习达到自动分类的目的。 3 模糊聚类算法的现存问题 模糊聚类的有效性将直接影响着机器学习的性能。模糊c 一均值聚类算法( f u z z y c - m e a n c l u s t e r i n g a l g o r i t h m ，f c m ) 作为经典的模糊聚类算法，在许多领域获得了非常成 功的应用。尽管如此，但其也有自身的弱点。比如：初始聚类中心数目和位置不易确定以 及运算时间过长等不足：只用类中心来表示类，这样只适合r 发现球状类型的簇：在很多 情况下，算法对噪音数据敏感；不能保证收敛到目标函数的极小值点，有时会收敛到日标 函数的鞍点。f c m 算法采用了一种迭代的爬山技术( h e r a t i v e c l i m b i n g h i l l t e c h n i q u e ) 来 寻找晟优解，本质上是一种局部搜索算法。因此，它存在着两个致命的弱点：一是处理大 数据量费时，二是容易陷入局部极小值。 1 2 研究现状 1 模糊聚类发展现状 聚类是1 监督机器学习的重要方法，是一个_ 占老的问题，它伴随着人类丰十会的产生和 发展而不断深化，人类要认识世界就必须区别不同的事物并认识事物问的相似性，而每个 概念的最初形成无不借助丁：事物的聚类分析。 模糊划分的概念一经提出，人们就利川这一概念提出了多种模糊聚类方法，比较典型 的有：基丁相似性关系和模糊关系的方法( 包括聚合法和分裂法) 、基丁模糊等价关系的传 递闭包方法、基丁模糊图论最人树方法、以及基t 数据集的凸分解、动态规划和雉以辨识 关系等方法。然而由丁上述方法不适用丁人数据量情况，难以满足实时性要求高的场合， 因此其实际的应用不够广泛，故在该方面的研究也就逐步减少了。实际中受剑拌遍欢迎的 是基丁目标函数的方法，该方法设计简单，解决问题的范围广，最终还可以转化为优化问 题而借助经典数学的1 r 线性规划理论求解，升易丁计算机实现。因此，随着计算机的应埘和 发展，基丁目标函数的方法已成为模糊聚类研究的热点。 2 模糊c 一均值算法的研究现状 在众多基于目标函数的模糊聚类算法中，应用最为广泛而且较成功的是1 9 7 4 年由 d u n n 提出并由b e z d e k 加以推广的模糊c 一均值算法。 f c m 算法计算简单而且运算速度快，具有比较直观的几何意义。但是它只用类中心来 表示类，这样只适合丁发现球状类型的簇。在很多情况下，算法对噪音数据敏感。b e z d e k 等人已经证明了f c m 算法不能保证收敛到目标函数的极小值点，有时会收敛到目标函数 的鞍点。f c m 算法引入了权重指数m ，而m 选择的好坏直接影响聚类的效果。由于f c m 算法存在种种缺陷，许多人对f c m 算法进行改进，井提出了新的模糊聚类算法。 改变度量方式：在噪音环境下，采用欧氏度量的许多聚类方法有时不够稳定，而且对 于算法的初值，类的形状、大小都过于敏感。改变度量方式可以部分地控制这些问题，如 a f c m 2 等1 2 种。 改变隶属度约束条件：归一化约束条件假定每个数据点的影响力是相同的，显然这与 实际情况并不总是一致。如果放松对隶属度函数的要求，则将导致新的聚类算法，f p c m 3 等 1 3 种。 1 高新波模糊聚类分析及其应用西安：西安电子科技大学出版社2 0 0 4 ：7 5 。w uk l ，y a n gm s a i t e m a t i v ec - m e a n sc l u s t e r i n ga l g o r i t h m s p a t t e r nr e c o g n i t i o n 。2 0 0 2 3 5 ( 1 ：2 2 6 7 - - 2 2 7 8 l i us h ，l i nj s v e c t o rq u a n t i z a t i o ni nd c td o m a i nu s i n gf u z z yp o s s i b i l i s t i eo m e a n sb a s e do np e n a l i z e da n d c o m p e n s a t e dc o n s t r a i n t s p a t t e mr e c o g n i t i o n ，2 0 0 2 ，3 5 ( 1 0 ) ：2 2 0 1 - 2 2 11 2 对模糊权值m 的研究：权重指数r a 对f c m 算法的聚类效果有重要影响，但是在理论 上如何选取合适的权重指数是一个悬而朱决的问题。通过对聚类有效性函数的评估实验， p a l l 宣称是最佳的权重指数可能位于区间 1 5 ，2 5 】，大多数研究者使用所= 2 ，于剑2 从理论 上证明并给出了如何选取模糊指标肌的规则。 这些算法与方法的提出，其基本出发点都是为了改进模糊c 均值算法的性能，扩大其 应用领域。尽管这些算法在一定程度上实现了设计者的部分良好愿望，但是我们也遗憾地 看到，f c m 还是存在着很多需要解决的问题。 1 3 研究内容 针对非监督学习方法中模糊聚类的局限性，本文将运用实验和比较方法，着重从以下 几个方面来进行研究： 1 对聚类分析典型代表f c m 算法进行研究，分析现有算法的优缺点，有利于进一步 改进。提出以初始聚类中心的改进方法和对各维特征进行加权选择的方法来分别提高f c m 算法的速度和正确率。 2 由tf c m 会陷入局部最优化问题，采用遗传算法加以解决。遗传算法是建立在生 物进化基础之上基丁- 自然选抒雨i 群体遗传机理的随机搜索算法。由丁它全局升行搜索，故 可以较高的概率获得全局最优解。此外遗传算法还具有简单、通圳和鲁梓性强等优点。遗 传算法与f c m 结合产生基丁遗传算法的模糊c 均值，充分发挥f c m 的局部搜索和遗传算 法的全局搜索能力，使得结果为最好i 人人提高了聚类l e 确率。 3 针对f c m 对人数据量处理速度慢的缺点，运川神经网络技术改进模糊聚类算法。 神经网络具有大规模的并行处理和分布式的信息存储、良好的白适应、白组织性、很强的 学习功能、联想功能和容错功能。在大数据量情况，卜模糊聚类是相当耗时的，川神经网络 实现聚类分析显著的优势在r 神经网络的并行处理。将自组织映射神经网络 ( s e l f - o r g a n i z i n gf e a t u r em a p ，s o m ) 与f c m 结合，产生f k c n 算法，利用s o m 的并行 计算，以提高聚类算法的速度和效果，实验结果表明算法有效。 通过对f c m 算法的上述改进，以弥补其局限性，使得算法更具合理性，从而减少聚类 时间，提高聚类效果，以此提升非监督学习的能力、效率与稳定性，优化机器学习性能。 1 4 研究方法 本论文主要采用以下研究方法： 1 文献分析法 查阅现有的国内外文献，分析对比各种聚类模型与算法的特点，尽可能借鉴前人在机 器学习聚类领域的研究成果。主要包括机器学习理论及学习方法策略；国内外聚类理论及 其应用领域研究；国内外非监督模糊聚类算法研究及在机器学习中的应用研究。 2 比较研究法 通过改进算法并将其进行比较，得出各种算法的优劣，为进一步的研究提供良好的思 路。 3 实验研究法 。p a l n r b e z d e kj c o nc l u s t e r v a l i d i t y f o r t h e f u z z yo - m s m o d e l i e e e t r a n s f u z z y s y s t c m u , 1 9 9 5 ，3 ( 3 ) ： 3 7 0 3 7 9 2 于剑论模糊c 均值算法的模糊指标计算机学报2 0 0 3 2 6 ( 8 ) ：9 6 8 9 7 3 3 通过数据集的实验对比，改进相关参数及算法混合使用，以提高算法效率，优化聚类 效果，提升机器的学习性能。 1 5 论文结构 本文主要是以f c m 算法为中心，对其优缺点进行分析，并以提高聚类速度和正确率 两个方面为切入点，通过对初始化聚类中心、备维特征进行加权选择的研究，结合遗传算 法、神经网络等对f c m 分别进行改进。本文组织如下： 第二章对1 监督学习进行了概述，对聚类分析的概念、作用、分类、研究方向等进行 介绍，对模糊理论进行了回顾，从而引申出模糊聚类分析，并对其一般模型与研究现状进 行了阐述。 第三章详细介绍了基于目标函数的模糊聚类分析的知识，对硬c 均值和模糊c 均值聚 类算法进行论述，重点分析了模糊c 均值聚类算法的优缺点，并从提高聚类速度及l e 确率 两方面对f c m 算法进行了改进，实验结果表明是有效可行的。 第四章首先详细介绍了遗传算法的概念、流稗、算法实现，并将其与f c m 算法结合， 形成基丁- 遗传算法的f c m 算法( g f i ：m ) ，将遗传笄法的全局搜索与f c m 的局部搜索充 分结合，以提高f c m 聚类止确率，显示山新算法g f c m 的优越性。 第五章详细介绍了人f ：神经网络的发展及白组织特征映射神经网络( s o m ) 的概念， 原理与算法实现，并将s o m 与f c m 结合，利用s o m 的并行计算，以提高聚类算法的速 度，实验结果表明新算法有效。 第人章总结论文所涉及的工作与已取得的成果，并指出研究需要继续完善的地方及今 后聚类算法的改进提出设想。 4 第二章非监督学习与模糊聚类分析 现代计算机具有强大的计算和信息处理的能力，但是它在目标识别、环境感知及在复 杂条件下的决策能力远远不如生物系统。目前。已有很多学科分别从不同角度、以不同途 径试图研究和揭示这其中的奥秘，并且希望_ i f i 计算机实现一个具有感知、识别、理解，自 学习和自适应能力的灵活和智能的计算机器。这些学科包括模式识别、人一l ：智能、计算机 视觉、机器学习，心理生物学和认知科学等。而“机器学习”冈其明确的问题定义、严格 的数学笨拙、坚实的理论框架和f “泛的应_ f i 价值，获得越来越多的重视，并成为上述其他 几门学科的中心研究内容之一。在过去的几十年里，机器学习的研究得到迅速发展，并且 已有丰富的理论成果，特别是近几年机器学习理论在数据分析和数据挖掘的实际问题中， 如网页检索和文本分类、基丁生物特征的身份识别、图像检索和视频检索、医学数据处理 等得到广泛应用 2 1 非监督学习 近年米，由于数据分析、金融与经济数据分析、信息安全的需求，以及备类科学与技 术数据的分析，使得机器学习研究的观念发生了很人的改变。处理1 e 线性、海量数据、提 高泛化能力、直接面向用户等目标成为机器学习新的挑战性的问题。止是这些挑战，使得 机器学习的发展极为迅速，应圳亦日盏广泛，并产生很多优秀的学习方法。根据不同的标 准与角度可以将机器学习方法进行不同的划分。其中按有无训练标签来分，可将机器学习 方法大致分为监督学 习( s u p e r v i s e dl e a r n i n g ) 、非监督学习( u n s u p e r v i s e dl e a r n i n g ) 、半监督 学习( s e l n i s u p e r v i s e dl c a m i f i 曲三类。 2 1 i 非监督学习概念 非监督学习是机器学习的一个重要学习方法，它是指不需要单独的离线训练过程，也 没有带标记的训练数据集，一般用来对数据集进行分析，如聚类，通过学习从中抽取出相 应的内在规律与规则，使得机器做出更为合理的决策。1 监督学习的理论研究一直是机器 学习研究的重点和热点。这些研究对于我们理解学习机器的学习机理以及人机交互都具有 重要的理论意义，研究非监督学习的各种方法也是实现提高和完善机器学习能力的重要途 径和手段。 非监督学习是机器学习和模式识别中的重要研究领域，它在理论和实际应用研究中都 获得了长足的发展和进步。非监督学习是相对丁监督学习而言的，监督学习是通过对具有 概念标记的训练集进行学习，以尽可能正确地对训练集之外的示例的概念标记进行预测。 而非监督学习则是通过对没有概念标记的数据集进行学习，以发现数据集中隐藏的结构性 知识。2 由此可见，对非监督学习的研究就是将致力于那些有利于从不可见的数据中区分出那 些模式的算法的分析与发展。新的学习算法是对原有算法在运行时间和正确率的改进基础 1 王珏，石纯一机器学习研究广西师范大学学报( f l ) , 2 0 0 3 ，2 1 ( 2 ) ：i 1 5 2 周志华监督，非监督和强化学习h t t p ：l l w w w c l i n u x o r g f o r u m s h o w t h r c a dp h p ? t h r c a d i d = 4 3 7 5 ，浏览时 间：2 0 0 5 1 1 1 0 5 上提出来的。每一个非监督学习算法都是对结构化数据库( 如判断贷款申请者) 、图像数据 和文本收集的应用。u c l 作为一个维持国际机器学习的数据库，每一个结构体系的数据集 都可以提供相应领域对机器学习算法进行评估。在这个由成千上万的记录和领域的数据组 成的数据库。它们包括商业、医学、工程和科学方面的数据。从这些数据中提取出有用的 信息是一个很重要很有意义的实际问题。研究的主题主要是关注如怎样从数据中建立既精 确又可理解的描述性模型这样的关键性问题。在实际中，对丁= 从理论层面来分析推理过程 和基于算法发展提供一个原则性的基础来说，可能性和统计技术一直扮演着一个重要的角 色。 2 1 2 非监督学习的作用 虽然监督学习方法一直占据着重要位置，很多研究者也习惯于用监督学习方法来解决 一些机器学习问题，但是至少有五个理由使我们相信1 # 监督学习方法是非常有朋的。2 首先，收集并标记火型样本集是个作常费时费力的一：作。比如，记录语音信息是相当 方便的，但是要止确地标记出每个发音所对麻的单词或音素的代价却是巨人的。如果能先 在一个较小的样本空间上粗略地训练个分类器，随后，允许它以白适麻的方式处理人量 的非监督的样本，我f j 就能节省人量的时间和精力。 第二，也许有人希望逆向解决问题：先用人量朱标记的样本集来自动地训练分类器， 再人- t 地标记数据分组的结果。这种方法比较适合“数据挖掘”( d a t a m i n i n g ) 方面的人型应 用，因为这些应h j 常常事先不知道待处理数据的具体情况。 第二，存在很多应用，待分类模式的性质会随着时间发生缓慢的变化。例如，自动食 品分类器中的食鼎会随着季节更换而改变。如果这种性质的变化能在非监督的情况下捕捉 到，分类器的性能就会大幅提升。 第四，可以用1 r 监督的方法提取一些基本的特征，这些特征对进一步的分类会很有用。 事实上很多非监督方法都可以以独立于数据的方式j 作，为后续步骤提供“灵巧预处理” 和“灵巧特征提取”等有效的前期处理。 最后，在任何一项探索性的j ：作中，1 乍监督的方法都可以向我们揭示观测数据的一些 内部结构和规律。如果我们能够通过这些方法得剑一些有价值的信息，那么就能更有效地 设计具有针对性的分类器了。 在很多实际应用中，由于缺少形成模式类的过程的知识，或者由于实际工作中的困难， 人们往往只能用没有类别标签的样本集进行1 ：作。 通过1 f 监督学习，人们把样本集划分为若干个子集( 类别) 后，或者直接用它解决分 类问题，或者把它作为训练样本集进行分类器设计。 2 1 3 非监督学习方法分类 非监督学习通过对数据集进行分析、学习，从中抽取出相应的内在规律与规则，使得 机器做出更为合理的决策。一般来说非监督学习的方法可以分成两人类：即基于概率密度 函数估计的直接方法和基于样本间相似性度量的间接聚类方法。3 。n e w m a nd j h e i a i c hs c ca 1 0 9 9 8 ) u c ir 印o s i t o wo f m a c h i n el e a r n i n gd a t a b a s e s 。i r v i n e 。c a ：u n i v e r s i t yo f c a | i f o m i a , d e p a r t m e n to f i n f o r m a t i o na n dc o m p u t e rs c i e n c e h t t p ：w w w i c s u c ie d u - m l e a m m l r e p o s i t o r y h t m l 浏览时甸：2 0 0 5 1 2 - 2 5 2 d u d ar o ，h a r tp e ，s t o r kd gp a t t e r nc l a s s i f i c a t i o n ( s e c o n de d i t i o n ) 北京：机械t 出版社, 2 0 0 3 ：4 1 6 3 边培棋，张学工模式识别北京：清华大学出版社，2 0 0 0 ：2 3 0 6 通常非监督学习的直接方法是指单峰子集( 类) 的分离方法。概率密度函数估计把数据 划分为着干个密度具有单峰形式的子集的方法。在没有任何类条件概率分布的先验知识情 况下，我们只能把特征空间划分为若干个区域s ，o = 1 ，2 ，3 ，c ) ，在每个区域中的混合密 度应该是单峰的，如图2 - 1 所示： s l s 2 图2 - l 单峰子集分离示意图 人们把这些区域叫做单峰区域。每一个单峰区域鼻和一个类别相对应。有各种算法 来实现这些单峰区域的划分。主要算法包括投影方法、基丁对称集性质的分离方法和单峰 子集分离的迭代算法等。直接方法都是把一个具有混合概率密度函数的集合分解为若干个 子集，对每个子集来说，其概率密度函数都是单峰态的，每个子集就相当是一个类。但是 估计概率密度函数是很困难，计算量也是很大的。 基丁样本间相似性度量的间接聚类方法是指在一定条件下，按照样本间的相似性把集 合划分成若干个子集。划分的结果虑使某种表示聚类质量的准则函数为最大。当_ i j 距离来 表示两个样本间的相似度时，这样做的结果就把特征空间划分成若干个区域，每个区域 相当于一个类别。这种方法就是本论文所讨论与研究的聚类分析。 非监督学习根据分类的不同还包括其它的一些方法如：m d s 、主成分分析( p c a ) 、非 线性映射( n l m ) 、l l e 等。 2 2 聚类分析 2 2 1 聚类分析的基本概念 随着人类社会的发展与科学技术的进步，对分类学的要求也越来越高。有时，只凭经 验或专业知识还不能进行科学有效的分类，于是数学这一有力的一r 具逐渐引入到分类学中， 在2 0 世纪6 0 年代以后，形成了一fj 新兴的学科一数值分类学。随着多元分析方法的引进， 从数值分类学中逐渐分离出了聚类分析这个分支。聚类分析的基本思想是从一批样品的多 个指标变量中定义能度量样品间或变量间相似程度( 或亲疏关系) 的统计量。在此基础上， 求出各样品( 或变量) 之间的相似程度的度量值，按相似程度的太小把样品( 或变量) 逐一归 类，关系密切的类聚集到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到 所有的样品或变量都聚集完毕，把不同的类型一一划分出来，形成一个亲疏关系谱系图， 用以更加直观地显示分类对象( 样品或变量) 的差异和联系。 聚类分析是多元统计分析的一种，也是非监督机器学习的一个重要分支。它把一个没 类别标记的样本集按某种准则划分成若干个子集，使相似的样本尽可能归为一类，而不相 7 似的样本尽量划分到不同的类中。 在实际问题中经常遇到分类的问题，侧如在考古学中，要将某些生物化石进行科学的 分类；在生物学中，要根据各生物体的综合特征进行分类；在经济学中为了研究不同地区 城镇居民的收入及消费状况。往往需要划分为不同的类型去研究；在产品质量管理中，也 要根据各产品的某些重要指标而将其分为一等品、二等品等等。总之，科学的分类方法无 论在自然科学，还是在社会科学中都有着极其广泛的应用。 聚类分析义称群分析和点群分析，它是对样品进行分类或对参数( 因子、指标) 分类的 一种统计方法。它与传统的数理统计的判别分析有较人的差别，也有许多相同之处。判别 分析要用到统计推断的传统的数理统计的方法，而聚类分析，就目前所使用的手段，基本 上还没有用到这种传统的数理统计方法但它们有一个批同点，就是所研究的现象都带有 不同程度的随机性。 “物以类聚，人以群分”，聚类是人类一项最基本的认识活动。通过适当聚类，事物才 便于研究，事物的内部规律才可能为人类所了解掌握。所谓聚类就是按照事物的某些属性， 把事物聚集成类，使类间的相似性尽量小，类内相似性尽量人。聚类是一个1 f 监督的学习 过程，而分类是有监督的学习过程，两者的撤本区别在丁：分类时需要事先知道分类所依 据的属性值，而聚类是要找剑这个分类属性值。对现实事物的聚类，首先需要把事物的属 性抽象出来。一般有两类属性值：一类是数值属性，一类是符号属性。关丁- 数值属性聚类， 有较多的方法，而对符号属性的聚类方法较少，井且常常转化为数值再处理。 目前，聚类统计量种类繁多，聚类方法也五花八fj ，但由丁聚类分析方法能j “泛地虑 用于解决实际问题，它乘i 回l 门分析、判别分析一起被称为多元分析的二人实用方法。 数据聚类分析是一个正在蓬勃发展的领域，它广泛应用f 模式识别、数据挖掘、市场 分析、计算机视觉、空问数据库技术等。国际和国内的学者都对聚类分析的研究1 f 常重视， i e e e 的期刊中模式分析与机器智能( p a m i ) 、系统、人和控制( s m c ) 、模糊系统 ( f s ) 、神经网络( n n ) 、信号处理( s p ) 等杂志中几乎每期都有讨论聚类分析问题 的文章。从1 9 9 2 年开始的由i e e e 和神经网络理事会共同主办的f u z z i e e e 会议，每两 年召开一次，每次至少由二到四个专题讨论聚类和模糊聚类分析的研究进展和发展现状。 另外，我国作为模糊数学研究的大国，不仅在基础理论研究上取得了丰硕的成果，而且在 模糊聚类的应用研究上也有令人瞩目的成果。比如基于模糊聚类的天气预报、矿藏识别希i 医学诊断等等。为了积极引导( 模糊) 聚类分析的研究热潮，国家白然科学基金委还专f j 对“模糊聚类的新方法研究”立了项，( 模糊) 聚类分析研究的意义和实用价值是不言而喻 的。 聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世 界就必须区别不同的事物并认识事物间的相似性，而每个概念的最初形成无不借助下事物 的聚类分析。因此，聚类分析的研究不仅具有重要的理论意义，也具有重要的- i 二程应用价 值和人文价值 2 2 2 聚类分析的作用 聚类分析是根据一批样品的诸多观测目标，按照一定的数学公式具体地计算一些样品 或一些参数( 指标) 的相似程度，把相似的样品或指标归为一类，把不相似的划为不同的类， 所谓“物以类聚”是也。聚类分析对丁：建立完善的分析指标体系有着1 e 常重要的作h j 。 ( 1 ) 可以保持设立统计指标体系的科学性。 高新波，谢维新模糊聚类理论发展及应用的研究发展科学通报，1 9 9 9 ，4 4 ( 2 1 ) ：2 2 4 1 2 2 5 1 8 在建立统计指标体系时，选择哪些指标，多少指标? 并不是指标越多越好，多了，增 加计算的复杂性：少了，不能很好的反映事物的特征。同时要能够删去重复的指标。 ( 2 ) 可以保持设立统计指标的全面性。 统计量要能够全面地反映事物特征，遗漏指标不仅不能反映事物特征，更重要的是 导致聚类分析结果的异常，造成大量的人力物力浪费。 ( 3 ) 可以保持设立统计指标的系统性。 并不是每个统计指标在每次聚类分析中都能用到，适当、适时的选取具有一定逻辑 概念统计指标会缺乏科学性，给聚类结果带来混乱，也缺乏说服力。 2 2 3 聚类算法的分类 聚类分析的历史还很短，由于在其发展过程中首先是着重于应用，冈此相对而言理论 上还不够完善。无论聚类统计量还是聚类的方法，都还朱最终定型。在聚类方法划分上， 目前存在着数千个算法。对丁二聚类算法的选择，取决。r 数据的类型、聚类的目的与应用 目前，聚类分析技术有很多，大致可以分为以- 卜儿类：1 ( i ) 划分方法( p a r t i t i o n i n gm e t h o d ) ：对于一个包含疗个数据对象的数据集，构建 k ( k 刀) 个分组( 簇) ，使得每一个簇中至少包含一个对象，每一个对象属丁且仅属丁一个 簇，并且要求同一个簇中的对象越接近越好、不同簇中的对象越远越好。对1 二给定的k ， 算法首先给出一个初始的分组方法，以后通过反复迭代米政变分组，使得每一次迭代后的 分组方案都较前一次好。分组方案的好坏用一个目标函数来衡量，算法进行反复迭代的过 稃就是最优化目标函数的过程，因此划分方法也称为最优化方法。该类算法有k - m e a n s 算 法、p a m 算法、c