（计算机应用技术专业论文）基于协同聚类的支持向量机分类方法的研究.pdf

r e s e a r c ho nt h es u p p o r tv e c t o rm a c h i n e c l a s s i f i c a t i o nm e t h o db a s e do nt h e c l a s s i l l c a t i 0 1 1 c o o p e r a t i v ec l u s t e r i n g at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em sd e g r e e 觑c o m p u t e rs c i e n c e b y l in a p o s t g r a d u a t ep r o g r a m c o m p u t e r s c i e n c ed e p a r t m e n t c e n t r a lc h i n an o r m a l u n i v e r s i t y s u p e r v i s o r ：d a is h a n g p i n g a c a d e m i ct i t l e ：a s s o c i a t ep r o f e s s o r s i g n a t u r e a p p r o v e d m a y , 2 0 1 1 m7i3 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 懈名：鲰 日期：加i 年岁月彬日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 糊糨巍干 日期：0 1 1 年多月；日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程” 中的规定享受相关权益。回意诠塞握交厦溢卮! 旦圭生；旦二生；旦三生蕉查。 作者签名栅导师豁暂尹 日期：加、年岁月名日 日期：扣l 年莎月弓日 魏戤沙 硕士学位论文 m a s t e r st h e s i s 摘要 目前，数据挖掘技术越来越为人们所重视。而分类是数据挖掘领域当中一个非 常重要的问题，聚类算法和支持向量机在处理分类问题上都表现地非常的出色，成 了当今数据分类的两种十分有利的工具。其中，聚类算法能够把大量数据点的集合 分成若干类，使得每个类中的数据之间最大程度地相似，而不同类中的数据之间最 大程度地不同。而支持向量机作为目前统计学习理论的v c 维理论和结构风险最小 化原则的具体实现算法，它能够很好的解决传统机器学习中的维数灾难和局部极小 值等问题，并且建立预测准确率高的分类器。 针对大规模数据集学习时，支持向量机难以满足实际应用的需求。针对此问题， 在研究和分析目前有关算法的基础上，将支持向量机和聚类算法相结合，提出了基 于协同聚类的支持向量机分类方法。并在u c i 数据集上，将该分类方法与s m o 算 法以及r s v m 算法相比较，验证了该分类方法能够有效的简约支持向量的数量，提 高分类精度，减少分类时间。 本文所做的工作主要有： ( 1 ) 对最小二乘支持向量回归算法( l s s v r ) 进行了改进，对l s s v r 的最 优化问题作了一定的改进，得到一个线性方程组。改进后的l s s v r 只需要对这个 线性方程组求解，大大简化了求解过程。 ( 2 ) 提出了基于协同聚类的二类支持向量机( c c s v m ) ，通过协同聚类算法得 到的类中心来取代简化的支持向量机( r s v m ) 中随机选取的候选支持向量。通过 实验证明，c c s v m 算法能够有效的简约支持向量的数量，提高分类效率。同时： 将分类问题进一步的推广到支持向量机的多类分类问题，提出了基于协同聚类的多 类支持向量机。 ( 3 ) 提出了基于协同聚类的支持向量回归机( c c s v r ) ，首先利用l s s v m 算法进行回归，再进行协同聚类，最后利用改进的l s s v r 进行回归。通过实验证 明，基于协同聚类的支持向量回归机( c c s v r ) 较之于单纯的l s s v r 回归，能 够有效的简约支持向量的数量，提高分类速度。 关键词：分类，协同聚类，支持向量机，支持向量回归机 硕士学位论文 m a s t e r st h e s i s a b s t r a c t n o w a d a y s ，p e o p l ep l a c em o r ea n dm o r ea t t e n t i o nt od a t am i n i n g c l a s s i f i c a t i o ni sa v e r yi m p o r t a n tp a r to fd a t am i n i n ga r e a s ，a n dt h ep e r f o r m a n c eo fc l u s t e r i n ga l g o r i t h m a n ds u p p o r tv e c t o rm a c h i n ei nd e a l i n gw i t ht h ep r o b l e m so fc l a s s i f i c a t i o ni se x c e l l e n t ， a n dn o wt h e yb e c a m et w ok i n d so fe x t r e m e l ya d v a n t a g e o u st o o lf o rd a t ac l a s s i f i c a t i o n a m o n gt h e m ，c l u s t e r i n ga l g o r i t h mc a np u ta c o l l e c t i o no fd a t ap o i n t si n t os e v e r a lc l a s s e s t h a td a t ai ne a c hc l a s sc a nb et h eg r e a t e s te x t e n ts i m i l a r , a n dt h ed a t et h a ta l ei nd i f f e r e n t c l a s sa r et h eg r e a t e s te x t e n td i f f e r e n t a n dt h es u p p o r tv e c t o rm a c h i n e ，a sc u r r e n t l y c o n c r e t ei m p l e m e n t a t i o na l g o r i t h m so fs t a t i s t i c a ll e a r n i n gt h e o r yv cd i m e n s i o nt h e o r y a n ds t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e ，i tc a nw e l ls o l v et h ep r o b l e m so fd i m e n s i o n d i s a s t e r sa n dl o c a lm i n i m u mv a l u e si s s u e si nt h et r a d i t i o n a lm a c h i n el e a r n i n g ，a n di ta l s o c a ne s t a b l i s hc l a s s i f i e rt h a th a sh i g hf o r e c a s ta c c u r a t y w h e nl e a r n i n gf o rm a s s i v ed a t a s e t s ，s u p p o r tv e c t o rm a c h i n e ( s v m ) i sd i f f i c u l tt o m e e tt h ep r a c t i c a la p p l i c a t i o nr e q u i r e m e n t s t os o l v et h i sp r o b l e m , i nt h er e s e a r c ha n d a n a l y s i so ft h ep r e s e n tr e l e v a n ta l g o r i t h m , c o m b i n a t i n gs u p p o r tv e c t o rm a c h i n e ( s v m ) a n dc l u s t e r i n ga l g o r i t h m , w ep r o p o s e dt h es u p p o r tv e c t o rm a c h i n ec l a s s i f i c a t i o nm e t h o d b a s e do nc o o p e r a t i v ec l u s t e r i n g a n di nt h eu c id a t as e t , t h ec l a s s i f i c a t i o nm e t h o di s c o m p a r e d 谢廿ls m oa l g o r i t h ma n dr s v ma l g o r i t h m ，t h er e s u l ts h o w st h i sc l a s s i f i c a t i o n m e t h o dc a ne f f e c t i v e l yc o n t r a c t e dt h eq u a n t i t yo fs u p p o r tv e c t o r ，i m p r o v i n gt h ea c c u r a c y o fc l a s s i f i c a t i o n , r e d u c ec l a s s i f i c a t i o nt i m e ，n l em a j o rw o r k s d o n ei nt h i sp a p e ra r ea sf o l l o w s ： ( 1 ) l e a s ts q u a r e ss u p p o r tv e c t o rr e g r e s s i o na l g o r i t h m ( l s s v r ) w a si m p r o v e d , a n d t h eo p t i m i z a t i o np r o b l e mo ft h el s s v rw a si m p r o v e d ，t h e nw eg e tal i n e a re q u a t i o n t h ei m p r o v e dl s - s v r o n l yn e e dt os o l v et h el i n e a re q u a t i o na n di tc a ng r e a t l ys i m p l i f y t h es o l v i n gp r o c e s s ( 2 ) c c - s v ma l g o r i t h mi sp u tf o r w a r di nt h i sp a p e r , t h ec l u s t e r i n gc e n t e rw h i c hi s g e tf r o mc ca l g o r i t h mr e p l a c et h ec a n d i d a t es u p p o r tv e c t o rw h i c hi ss e l e c t e dr a n d o m l y i nr s v ma l g o r i t h m n l cr e s u l t so fe x p e r i m e n t ss h o wt h a tc c - s v ma l g o r i t h mc a n e f f e c t i v e l yc o n t r a c t e dt h eq u a n t i t yo fs u p p o r tv e c t o r , i m p r o v i n gt h e c l a s s i f i c a t i o n e f f i c i e n c y m e a n w h i l e ，t h ec l a s s i f i c a t i o np r o b l e mf u r t h e re x t e n d e dt om u l t - c l a s ss u p p o r t i i 硕士学位论文 m a s t e r st h e s i s v e c t o rm a c h i n e s ，t h ec l a s s i f i c a t i o no fm u l t - c l a s s s u p p o r tv e c t o rm a c h i n eb a s e do i l c o o p e r a t i v ec l u s t e r i n gi sp r o p o s e d 0 ) c c s v ra l g o r i t h mi sp r o p o s e d , f i r s tu s i n gr e g r e s s i o no fl s - s v ma l g o r i t h m ， a n dt h e nu s i n gt h ec o o p e r a t i v ec l u s t e r i n g ，f i n a l l yl l s i n gt h ei m p r o v e dl s s v rr e g r e s s i o n 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 t c o m p a r e dw i t ht h ep u r el s s v rr e g r e s s i o n a l g o r i t h mc c s v rc a ne f f e c t i v e l yc o n t r a c t e dt h eq u a n t i t yo fs u p p o r tv e c t o ra n di n c r e a s e t h ec l a s s i f i c a t i o ns p e e d k e yw o r d s ：c l a s s i f i c a t i o n , c o o p e r a t i v ec l u s t e r i n g ，s u p p o r tv e c t o rm a c h i n e ( s v m ) ， s u p p o r tv e c t o rr e g r e s s i o nm a c h i n e ( s v r ) i i i 硕士学位论文 m a s t e r ? st h e s i s 摘要 a b s t r a c t 目录 第1 章绪论 i i i 1 1 研究背景1 1 2 研究现状和研究意义2 1 2 1 研究现状2 1 2 2 研究意义：4 1 3 本文所做工作和内容组织5 第2 章协同聚类算法7 2 1 聚类分析7 2 1 1 聚类分析的概念和应用7 2 1 2 聚类算法的发展7 2 2 聚类分析算法8 2 2 1 划分方法8 2 2 2 层次方法1o 2 2 3 模糊c 均值聚类( f c m ) 。10 2 3 协同聚类算法( c i ? 算法) 一1 2 2 3 1c c 算法的主要思想1 3 2 3 2c c 算法的描述1 4 2 4 本章小结1 5 第3 章支持向量机的分类1 6 3 1 支持向量机1 6 3 1 1 线性可分情况1 6 3 1 2 线性不可分情况1 7 3 2 支持向量回归机1 9 3 2 1 最小二乘支持向量回归机( l s s v r ) 1 9 3 2 2 改进的最d x - - 乘支持向量回归机2 0 3 3 支持向量机的训练算法2 1 3 3 1 经典训练算法2 2 3 3 2 简化的支持向量机( r s v m ) 2 4 硕士学位论文 m a s t e r st h e s i s 3 4 多类支持向量机分类方法2 6 3 5 本章小结2 9 第4 章基于协同聚类的支持向量机分类方法。3 0 4 1 聚类算法和s v m 所存在的问题3 0 4 1 1 聚类算法所存在的问题一3 0 4 1 2s v m 所存在的问题3 0 4 2 基于协同聚类的二类支持向量机3 1 4 2 1 算法的主要思想3 1 4 2 2 算法的描述3 2 4 2 3 实验3 3 4 3 基于协同聚类的多类支持向量机。3 4 4 3 1 算法的主要思想。3 4 4 3 2 算法的描述一3 5 4 4 基于协同聚类的支持向量回归机3 7 4 4 1 算法的主要思想一3 7 4 4 2 实验3 9 4 5 本章小结4 0 第5 章实验结果与分析 4 1 5 1 分类实验4 1 5 1 1 实验数据。4 1 5 1 2 实验结果4 1 5 1 3 实验分析4 4 5 2 回归实验4 5 5 2 1 实验数据一4 5 5 2 2 实验结果及分析4 5 5 3 本章小结4 6 第6 章总结和展望4 7 6 1 主要研究工作4 7 6 2 展望4 8 参考文献4 9 硕士期间发表的论文和参与科研项目5 3 致谢。5 4 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景 第1 章绪论 随着当今知识经济时代的发展，信息作为社会三大资源要素之一，它越来越显 现出重要性以及支配力，信息这种资源将人类社会由工业化时代迈向了信息化时 代。由于现在人类活动范围的扩大、社会节奏的加快、计算机科学技术的进步，使 得现在的数据信息量以指数形式增长着。一些企业在经营过程中收集到的以及所生 成的很多资料数据，通常都是以超载和非结构化的形态存在着，使得企业的决策部 门没有办法有效率的利用储存数据中所包含的大量有用信息；甚至有的公司因此使 得其决策行为产生混乱；形成了我们通常所说的数据爆炸但知识贫乏的现象。实际 上，在这些大量的数据之后更为我们所重视的是这些数据整体所显现出的特征的描 述以及对这些数据的发展趋势的预测，这些信息是在生成决策的过程当中起着非常 重要的作用。因此就需要我们在这些大量的数据当中去寻找其固有的联系，挖掘其 潜藏的规律，提取其内在的规则，为决策者做出决策的时候提供数据上的基础，在 这样的基础上才能做出恰当的决策。这所有的一切推动了现在的数据库当中知识发 现( k d d ) i l l 的诞生，在k d d 的理论当中，我们将知识学习的这一个阶段称之为数 据挖掘。数据库当中知识发现( 1 d ) 其实就是从大量的、己经存在的数据中、数 据库或着仓储数据当中去发现未知的、并且具有其潜在的应用价值的信息或者模 式。所以说目前k d d 是一门新的、而且来自于不同的知识领域的交叉性学科，k d d 这一领域已经涉及到了机器学习、模式识别、统计学、知识获取、专家系统等多个 不同的领域，目前，k d d 这门学科己经成为了当今国内外学术界所研究的一个热 点问题，并不断的有新内容、新方法、新技术涌现出来，目前己经形成了一定规模的 数据挖掘的理论和方法体系，现在已经被广泛地应用于金融、财经、电子、商务圈、 医学诊断、生产过程、产品信息、优化控制、模式识别、工程数据计算与分析等各 个领域当中。 聚类( c l u s t e r i n g ) 2 1 作为当今数据挖掘研究领域中的一个热点，通过聚类人们 可以发现隐藏在数据库中的一些不为人们所知的一些深层次的信息，并且概括出每 一类的特点，或把注意力关注在某一特定的类上去做进一步的分析和研究，也可以 将聚类分析作为数据挖掘算法当中其他的分析算法的一个预处理步骤。随着科学技 术的不断发展，人们每天都要处理越来越多的各种各样的信息，如何从这些海量的 数据中得到以及分析出为人们所需要的一些有价值的信息，这个时候，就需要我们 硕士学位论文 m a s t e r st h e s i s 的数据挖掘技术 3 1 。它其实就是从大量的无序的数据当中去发现隐含在其中的有效 地有价值的模式，通过这样的模式去发现更多的有用的知识，并且可以从中得出时 间段趋势和这些知识之间的一些关联，这些所得到的有用的知识可以为用户提供求 解问题的决策支持的能力。根据e l 前聚类算法的基本思想，将该算法分为五类：即 分割聚类算法、机器学习中的聚类算法、基于约束的聚类算法、层次聚类算法以及 应用于高维数据的聚类算法1 5 j 。 支持向量机( s u p p o r tv e c t o rm a c h i l i e s ，即s v m ) 1 6 删e19 9 2 年的计算机学习理 论会议上被v a p n i k 等人介绍进入到机器学习领域的，支持向量机是在统计学习的基 础上的机器学习的方法。根据v a p n i k 所提出的结构风险最小化的原则，为了达到 结构风险最小的目的、基于有限数目的样本信息，在模型的复杂性以及其学习能力 之间寻找最佳折衷，并且实现了经验风险和置信范围的最小化，因此，它在统计样本 量比较少的情况下，能够获得比较好的统计规律以及更良好的泛化能力。s v m 能 成功地处理以及解决分类问题以及回归问题，支持向量机的优势是基于统计学习理 论的，主要是为了寻求小样本条件下的统计规律和学习方法。支持向量机不像传统 的统计学那样，传统的统计学解决问题的前提是需要具有足够多的样本，比如说传 统的神经网络等。因为支持向量机所表现出来的突出的学习性能，此技术己经得到 了最为广泛的应用，支持向量机技术现在已经成功的应用于很多模式识别问题中， 比如说：手写字符识别、计算机视觉领域、网页或者文本自动分类技术、目标识别、 基因分类、人脸检测以及识别技术、遥感成像分析等。在函数回归方面、估计、密 度估计、函数逼近、非线性系统控制、时间序列预测等问题当中，都得到了成功的 应用，并且在数据挖掘、数据压缩、文本过滤、计算机入侵检测、股市预测等问题 中，表现出了非常良好的性能，成为了机器学习界的一个研究热点 7 1 。它已经被认 为是解决分类以及回归问题的强有力的工具。 1 2 研究现状和研究意义 1 2 1 研究现状 数据挖掘( d a t am i n i n g ) j 概念是随着知识发现概念的出现而出现的。数据挖掘 是从海量的数据当中去发现有用的知识，这些知识通常情况下具有未知性、潜在性 以及可用性等特点，通过数据挖掘技术提取出来的知识一般可以通过模式、规律、 规则、概念等一些形式表示出来。从这个意义上来讲，数据挖掘的对象被定义为大 型数据库。但是从更广泛的意义上来说，从一些组织在一起的数据集合中找寻模式 的决策支持过程可以作为数据挖掘技术更为抽象的定义【s j 。数据挖掘这个领域是一 2 个融合了多门技术的交叉性学科，各个不同领域的科学研究者们都致力于此领域的 研究，特别是人工智能、并行计算、数据库、数理统计等方面的研究学者和工程技 术人员。 聚类作为数据挖掘中的一个重要的模块，也引起了大家的充分关注以及研究学 习。人们将聚类分析又称做是群分析，聚类分析是目前研究分类问题的一个统计分 析的方法。聚类分析【9 】是起源于分类学，在古老以及原始的分类学当中，人们主要 是通过依靠经验以及所学习到的专业知识来完成分类的过程，实际上很少利用数学 工具去做定量的分类研究。但是，随着人类科学技术的不断发展，人们对分类的要 求越来越高，导致之前的仅仅凭借经验和所学习到的专业知识非常难以准确地进行 分类，因此，人们渐渐地将数学工具引入到了分类学当中，形成了现在我们所说的 数值分类学，在这之后，又将多元分析技术引进到了数值分类学中，形成了聚类分 析。聚类分析的内容十分丰富，有模糊聚类法、系统聚类法、动态聚类法、聚类预报 法、序样品聚类法、图论聚类法等等【l o 】。目前，我们所使用到的聚类算法有：划分 方法、基于网格的方法、层次方法、基于模型的方法、基于密度的方法等。c u r e ， c h a m e l e o n 和r o c k 算法是聚类算法当中非常具有代表性的三个方法。在19 9 8 年，c u r e 等人提出了c u r e 算法【1 1 】。此种算法中，一个聚类并不是用单个的中心 或者对象来表示，而是通过选取数据空间当中固定数目的的并且有代表性的一些点 来共同的表示相应的类，通过这样的方法，可以识别出复杂形状的聚类。r o c k 算 法是根据c u r e 算法进行一定程度的改进而来的，它具有c u r e 算法的很多优点， 同时也适用于类别属性的数据。1 9 9 9 年，k a r y p i s 等人提出了c h a m n l e o n 算法， 此算法将动态建模技术运用到聚合聚类的过程中。 支持向量机( s v m ) 是一种十分重要的分类方法，它是建立在统计学习理论基础 之上的机器学习方法。通过此种机器学习算法，支持向量机可以自动的寻找出那些 对分类有比较好区分能力的向量，并且将它们做为支持向量，由这些支持向量来构 造分类器，这个分类器能够使得两个类之间的间隔达到最大，因此，支持向量机有 非常好的推广性能以及学习能力和非常高的分类准确率。s v m 的主要思想是针对 两类分类问题的，通过将低维空间中的向量映射到高维空间中去，并且在高维空间 当中寻求一个超平面作为两个类的分割面，以最大程度的保证分类的正确性。同时， s v m 另个优势在于它能够解决线性不可分的问题。s v m 目前已经成为了机器学 习领域的一个研究热点。目前，支持向量机已经成功的应用于文本自动分类、手写 体数字识别、人脸检测、三维物体识别、时间序列分析、遥感图像分析、蛋白质结 构预测等方面1 1 2 1 。 3 硕士学位论文 m a s t e r st h e s i s 1 2 2 研究意义 支持向量机和聚类是目前被公认为十分有效的数据挖掘算法。支持向量机作为 目前统计学习理论的v c 维理论和结构风险最小化原则的具体实现算法，支持向量 机能够很好的处理小样本，非线性，高维数和局部极小值等问题。由于支持向量机 所具有的突出的学习能力，目前支持向量机的理论在国内外学术界受到了广泛的重 视。所以学习、研究统计学习理论和支持向量机具有理论意义。虽然研究者对支持 向量机算法做了大量的研究以及改进，但是其仍然存在一些不足之处，如：训练速 度慢，在多类分类问题上，支持向量机在构造分类器的效率低等问题。因此，如何 提高训练速度以及如何构造多类分类器是目前需要解决的两个问题。 聚类算法是数据挖掘中常用的数据分析的工具，该算法的基本思想是将一个数 据集当中的大量的数据点划分成若干个类，在这些类当中，在同一个类当中的数据 具有最大程度的相似性，而处于不同的类当中的数据之间必须最大程度地不同。对 于高维数据聚类而言，它所存在的问题主要有两个方面： 一、在高维属性空间中， 存在着一些无关的属性，这些无关的属性使得聚类的过程变的困难起来；二、在 高维空间中，数据之间如何进行区分，这个区分的界限比较模糊。通过对目前所有 的聚类算法进行比较，我们可以知道，在不同的应用领域当中，每一种聚类算法都 表现出了不同的性能，也就是说，就目前来讲很少有一种算法能够同时的适用于多 个不同的应用背景当中。因此，怎样去寻求某一类聚类算法，这种算法能够在聚类 的质量和算法时间复杂度上都表现出很好的性能，是一个很值得研究的重要的问 题。 在本文中，针对目前支持向量机和聚类算法中存在的问题，对支持向量机的分 类和聚类进行了研究分析，给出了基于协同聚类的支持向量机的分类方法，训练算 法以及多类分类器的构造方法，并且分析了协同聚类算法和支持向量机各自的优缺 点，由于两者间存在着一定的互补性，因此，将这两种方法结合起来处理数据分类 的问题，在本文中提出了基于协同聚类的支持向量机的分类算法，该算法能够使得 训练过程中的支持向量的数量大大的减少，进而能够很好的提高支持向量机的分类 速度。对于如何对多类进行分类的问题，我们将该分类算法做了进一步的推广，提 出了基于协同聚类的多类支持向量机。针对回归问题，提出了基于协同聚类的支持 向量回归机。通过在u c i 数据集上的实验，我们验证了基于协同聚类的支持向量机 分类方法得到了较好的效果。 4 硕士学位论文 m a s t e r st h e s i $ 1 3 本文所做工作和内容组织 本文采用协同聚类算法和支持向量机的理论作为分类数据挖掘的理论工具，将 这两者有机的结合起来，提出了基于协同聚类的支持向量机分类方法，主要的研究 内容如下： ( 1 ) 对聚类算法进行了深入的研究，详细介绍了一些经典的分类算法，具体 分析了模糊c 均值聚类，并且在此基础上，分别对两类样本中随机地选取样本点进 行协同聚类，通过协同聚类，在保证支持向量机分类精度的情况下，使得支持向量 的数目能够大大的减少，并且能够使得支持向量机的分类速度提高。 ( 2 ) 对支持向量机的分类进行了研究，详细介绍了支持向量机以及支持向量 回归机，提出了改进的最d x - 乘支持向量回归机；讨论了支持向量机的一些经典的 训练算法以及简化的支持向量机r s v m ，并且介绍了目前的多类支持向量机的分类 方法的基本思想。 ( 3 ) 结合协同聚类和支持向量机理论各自的优缺点，提出了基于协同聚类的 支持向量分类方法，对此分类方法的算法进行了详细的阐述，针对支持向量机二类 和多类的分类情况，在本文中分别的提出了基于协同聚类的二类支持向量机和多类 支持向量机。同时，对于回归问题，提出了基于协同聚类的支持向量回归机。并在 u c i 数据集上验证了基于协同聚类的支持向量机分类方法分类精度的高效性。 全文主要分为六个章节，下面是全文的组织和各章的主要内容： 第一章“绪论 主要了讨论了分类数据挖掘，聚类和支持向量机的研究背景以 及其国内外研究现状，以及本课题的研究意义所在，最后介绍了论文所做工作和其 组织结构。 第二章“协同聚类算法”主要分析了协同聚类算法( c c 算法) 、算法的基本思 想和算法的主要内容。首先分析了模糊c 均值聚类，并且在此基础上，分别在两类 样本当中随机地选取一些样本点，对这些被选取的样本点进行协同聚类，通过协同 聚类算法我们可以确定支持向量，再根据这些支持向量以及训练样本来训练支持向 量机。 第三章搿支持向量机的分类阐述了最典型的支持向量机的理论基础，以及支 持向量回归机；详细介绍了支持向量机算法，讨论了当前几种主要的支持向量机的 变形，对最d x - 乘支持向量回归机进行了改进，并且比较了各种变形算法的特点和 所存在的问题。 第四章“基于协同聚类的支持向量分类方法 结合协同聚类和支持向量机理 5 硕士学位论文 m a s t e r st h e s i s 论各自的优缺点，提出了基于协同聚类的支持向量分类方法，对此分类方法的算法 进行了详细的阐述，针对支持向量机二类和多类的分类情况，分别的提出了基于协 同聚类的二类支持向量机和多类支持向量机。同时，对于回归问题，本文提出了基 于协同聚类的支持向量回归机。并且通过实验，证明了该分类方法能够有效的简约 支持向量的数量，提高分类效率。 第五章“实验结果与分析通过利用u c i 数据集和d e l v e 数据集验证在本文中 所提出来的分类方法的有效性，对本文当中所提出来的分类和回归算法分别进行验 证，并且对实验结果进行了详细的分析。 第六章“总结和展望给出了全文的总结和展望。 6 硕士学位论文 m a s t e r st h e s l s 第2 章协同聚类算法 2 1 聚类分析 2 1 1 聚类分析的概念和应用 聚类分析是根据数据之间的相似性，对数据进行划分的一种工具。它是利用数 据点之间的相似程度进行自动的分类。也可以说聚类分析是通过运用数据之间的相 似性的度量方法。聚类的主要思想是使得类中的数据点之间能够最大程度的相似， 而不同的两个类之间能够最小程度的相似。一般情况下，聚类分析算法是采用欧几 里德距离来衡量两个数据元素之间的相似度。 聚类应用的领域是非常广泛的，比如：聚集、机器学习、模式分析的浏览、模 式分类、数据挖掘、决策制定、文件恢复、图像分割等，同时，聚类分析还可以运 用在数据分析、模式识别、w e b 应用等领域【1 3 1 。聚类分析作为数据挖掘这个领域 当中不仅可以作为独立的分类工具去发现数据分布的隐含的有价值的信息，概括出 这些数据中每一个类的特点，还可以专注于某一特定的类，对这个特定的类作更深 层次的分析。 聚类分析的用途也是相当的广泛的。在商业领域中，聚类分析可以从消费者数 据库当中帮助市场分析人员去区分不同的消费群，并且可以分门别类地概括出消费 者的消费习惯和模式等；在地理学领域，聚类分析可将地理数据库中具有相似土地 特征的区域进行分类；在生物学领域，聚类分析可以协助研究者们对动、植物、相 似功能的基因以及人群当中的某些潜在的结构等进行分类。 2 1 2 聚类算法的发展 传统的聚类算法可分为划分方法、基于网格的方法、基于密度的方法、层次方 法以及基于模型的方法等几类【1 4 1 。通过以上的几种方法所得到的簇都是边界明确的 簇。即每个数据点都与簇之间的包含关系是明确的，并且不同簇之间的边界也是完 全清晰且不相互重叠。这样的聚类方法称之为“硬聚类 。硬聚类有其自身的优点， 就是算法清晰而且结果明确。但是并不是所有的问题都能够通过硬聚类的方法得到 解决。它的缺点就是现实世界当中的事物通常有很多并不能够非常明确的将其归到 某一个类中去。在遇到这样的问题时，传统的聚类方法就显得有些爱莫能助。于是， 就产生了另外种聚类算法，我们将它称之为“软聚类 。 随着模糊理论的不断发展，模糊集和粗糙集得到了广泛认同及应用。虽然聚类 7 硕士学位论文 m a s t e r st h e s i s 算法产生了“硬聚类“和“软聚类 两种算法，但是在实际应用中，许多对象很 难明确地判断它们属于哪一类，而且边界具有模糊性。针对这种情况，由z a d e h 所 提出的模糊集理论【l5 】为解决这一难题提出了可行的解决方法。模糊聚类分析，即利 用模糊数学的方法所做的聚类分析，常用的方法是模糊c 均值聚类算法( f c m ) ，其 基本思想为用隶属度作为确定每个数据点属于哪一个类的聚类算法【1 6 1 。模糊c 均值 聚类算法f f c m ) 与以往经典的聚类算法有所区别，为区别起见，经典的聚类算法记 为“硬聚类，在硬聚类中，对象与类或簇的关系是明确的。而引入模糊聚类分析 概念之后，聚类，如模糊c 均值聚类算法( f c m ) 等方法称做“软聚类 ，与硬聚类 不同的是，软聚类中不同的簇之间并没有明确的边界，即使处在边界的数据点也并 不能确定为属于哪一个簇。模糊c 均值聚类算法( f c m ) 也被大量的应用于海量数据 聚类和w e b 聚类中。 2 2 聚类分析算法 2 2 1 划分方法 划分方法属于我们上文所介绍的硬聚类算法。也就是说：对于每一个簇拥有哪 些节点是确定的，并且簇与簇之间不会出现重叠现象，边界非常清晰。 我们假设有一个数据集，该数据集拥有刀个对象。那么划分方法就会将数据首 先划分为k ( k - - _ 作为初始聚类中 心，并且对这七个对象 w 1 ，w 2 ，) 进行初始化 ( 2 ) 使得每一个聚类c ，与聚类中心形相对应 r e p e a t ( 3 ) 对每个输入向量，其中f ( 1 ，2 ，埘) ，将分配给最近的聚类中心所属的类q ( 4 ) 将每一个聚类c ，其中j e ( 1 ，2 ，j ) ，利用当前的c ，中的所有的样本的质心点来 替换聚类中心 同时，计算如下的错误函数： e = i 吩1 2 9 硕士学位论文 m a s t e r st h e s i s ( 5 ) 止到错误函数e 的值不再明显的改变或者聚类成员不再变化，算法结束。 2 2 2 层次方法 层次方法的主要思想是：对于一个给定的数据集，对数据集进行层次分解，当 它满足某种条件时，层次分解将结束。层次方法具体的又可以将其分为：自上而下 和自下而上两种方式。自下而上的层次方法也被称为合并。它的工作流程是这样的： 首先，将数据集当中的每一个对象都当作是一个簇，然后，将这些子簇合并成越来 越大的簇，直到将数据集当中的所有的对象都合并到了一个簇中，合并结束；或者 是当满足某一个条件时，则终止合并。自上而下的层次方法也被称之为分解。它的 工作流程是这样的：首先，将数据集当中的所有的对象都放在同一个簇当中，然后， 将这一个簇逐渐细分成为越来越小的簇，直到数据集当中的每一个对象都自成一 簇，分解结束；或者是当满足某一个终止条件时，则终止分解。为了弥补分解与合 并这两种方法所存在的不足之处，层次和合并的方法，通常情况下都是要和其它的 聚类方法结合在一起使用的。 在本文中，我们主要介绍c u r e ( 利用代表点聚类) 方法，它是层次方法当中具 有代表性的一种方法。c u r e 方法也是我们在上一小节当中所提到的一种硬聚类 算法。c u r e 方法能够很好的解决偏好球形和与球形相似形状的这一类问题。同时， 在处理孤立点的问题上，c u r e 算法也表现的非常的健壮。 c u r e 算法的基本思想如下： ( 1 ) 对于每一个数据对象而言，它就是一个独立的类，然后，合并与这个数据对象最 相似的数据对象。 ( 2 ) 对于大规模的数据集的问题，子类是通过利用随机抽样以及分割的方法来形成 的，然后，通过利用这些子类进行重新聚类而形成新的类。 (