（计算机应用技术专业论文）一种基于聚类的支持向量机反问题求解算法.pdf

河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文巾不包含其他 人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 j j f i 使j i - ij 立的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了：! j j 确 的谚0 明并表示了致谢。 作者签名： 线。蕴。日期：埠年厶月l r 学位论文使用授权声明 本人完全了f 0 4 - n - t l ；大学有关保留、使用学位论文的规定，即：学校有权保留并向围 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公以j 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 l 、保密口，在年月n 解密后适用本授权声明。 2 、不保密时。 ( 清在以上相应方格内打“d ) 作者签名： 导师签名： 煞丛， ： 盘修么一 日期：遮年丘月坠同 日期：丛望年互月业闩 摘要 蔓曼! ! 曼曼! 曼曼皇! ! 曼! 曼曼曼曼曼皇曼曼曼! 曼! ! ! 皇曼曼曼曼量! ! 蔓曼! 曼! 皇曼曼曼! 曼曼曼曼曼曼曼曼曼曼i 一 一= 一 一曼i 皇! 曼曼 摘要 支持向量机( s v m ) 是机器学习领域- ；f , p - - 1 p - 常重要的分类算法，它的出现是以统计 学习理论为基础的。由于其良好的泛化能力，使得这种分类方法在很多领域都有应用。 f 盟是f l 寸问复杂度高的缺点一直是困扰这种优秀的分类器进一步发展的原因。支持向量机 反问题的提出是希望作为一种启发式而产生一种有更强泛化能力的决策树，其本质是如 何将个事例集分为两部分，才能便这两部分之间的l 、n j 隔最大。但是惊人的时f u j 复杂度 使得这种算法很难应刚到具有一定规模的数据集上。本课题针对如何提高该算法的求解 效率做了有意义的探索。 本文存深入分析支持向量机反问题求解过程的基础j 二，提出了一种基于聚类的支持 向最机反问题求解算法。首先对支持向量机反问题高时问复杂度的原冈进行了探讨，发 现主要原闪足需要枚举出所有可能的划分。然后，通过分析核聚类的特点，发现核聚类 对f 减少支持向量机反问题的时洲复杂度很有帮助，提出了先聚类再求反问题的策略： 川核聚类算法列数据进行预处理，把数据聚成有限数量的几簇，在簇之问做划分，取代 了原订的在所有点之f j 做划分的枚举算法。最后，给出了本文算法的实现过程及其实验 结果，并与j h j lk m e a n s 聚类方法作为数据预处理的方法做了比较，测试数据表 刿该算法 叫行、有效。 关键词支持向量机；支持向量机反问题；核聚类算法；k m e a n s 聚类算法； 时问复杂度 a b s t r a c t a b s t r a c t s u p p o r tv e c t o rm a c h i n e sa r ev e r yi m p o r t a n tc l a s s i f i c a t i o nt e c h n i q u ei nt h ef i e l do f m a c h i n el e a r n i n g ，t h i st h e o r yi sb a s e do ns t a t i s t i c a l l e a r n i n gt h e o r y b e c a u s eo fi t sg o o d g e n e r a l i z a t i o nc a p a b i l i t y , t h i sc l a s s i f i c a t i o nt e c h n i q u eh a sb e e na p p l i e dt om a n yf i e l d s b u tt h e d i s a d v a n t a g eo fh i g ht i m ec o m p l e x i t yi st h e r e a s o nw h yt h i se x c e l l e n tc l a s s i f i c a t i o nt e c h n i q u e c a n th a v ef u r t h e rd e v e l o p m e n t t h ep r o p o s i t i o no fi n v e r s ep r o b l e mo fs v m s i sm o t i v a t e db v d e s i g n i n gah e u r i s t i ca l g o r i t h mf o r g e n e r a t i n gd e c i s i o nt r e e s w i t h h i g hg e n e r a l i z a t i o n c a p a b il i t y t h ei n v e r s ep r o b l e mi sh o wt os p l i tag i v e nd a t a s e ti n t ot w oc l u s t e r ss u c ht h a tt h e m a r g i nb e t w e e nt h et w oc l u s t e r sa t t a i n sm a x i m u m t h ei n c r e d i b l et i m ec o m p l e x i t ym a k e si t d i f f i c u l tt oa p p l yt ot h ed a t aw i t hc e r t a i ns c a l e o u rw o r k sc o n c e m sh o wt o i m d r o v et h e e f f i c i e n c yo fs o l v i n gt h ei n v e r s ep r o b l e mo fs v m s a ni m p r o v e da l g o r i t h mf o ri n v e r s ep r o b l e mo fs v m sb a s e do nc l u s t e r i n gi s p r o p o s e d b a s e do nt h et h o r o u g hr e s e a r c ht ot h ei n v e r s e p r o b l e m f i r s t ，t h er e a s o nw h vt i l et i m e c o m p l e x i t yo fs o l v i n gt h i sp r o b l e mi sv e r yh i g hi s d i s c u s s e d ；e n u m e r a t i n ga l l t h ep o s s i b l e c a s e si sr e c o g n i z e da st h ep r o b l e m s e c o n d ，t h ec h a r a c t e r i s t i co f c l u s t e r i n gi sa n a l y z e d a n d f i n d i n gt l m tc l u s t e r i n g i sh e l p f u lt od e c r e a s et h et i m e c o m p l e x i t yo fs o l v i n gt h ei n v e r s e p r o b l e m an e ws t r a t e g yi s p r o p o s e da s f o l l o w s ：p e r f o r m i n gt h e d a t a p r e p r o c e s s i n g ， c o n v e r g i n gt h ed a t ai n t ol i m i t e dn u m b e ro fc l u s t e r s ，w er e p l a c et h eo r i g i n a la l g o r i t h mw h i c h e n u m e r a t i n ga l lt h es p l i t t i n gi na l lp o i n t sb yg e t t i n gt h eb e s ts p l i t t i n gi na l lc l u s t e r s f i n a l l y ， t h ep r o p o s e da l g o r i t h mi s i m p l e m e n t e da n ds o m ee x p e r i m e n t sa r ep r e s e n t e d a l s ow e c o m p a r i n gi tw i t ht h ea l g o r i t h mw h i c hc o n v e r g i n gt h ed a t ab yk m e a n sc 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 tr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi se f f i c i e n ta n dr e a s o n a b l e k e y w o r d s ：s u p p o r tv e c t o rm a c h i n e s ；i n v e r s ep r o b l e mo fs v m s ；k e m e lc l u s t e r i n g ； k m e a n sc l u s t e r i n g ；t i m ec o m p l e x i t y 目录 目录 第1 章绪论1 1 1课题来源1 1 2研究现状2 1 2 1 支持向量机的研究现状2 1 2 2 聚类算法的研究现状2 1 3本文研究的主要内容3 第2 章支持向量机及其反问题一5 2 1支持向量机( s v m ) 5 2 1 1标准支持向量机5 2 1 1 1 线性s v m 5 2 1 1 2 非线性s v m 7 2 1 2 多分类支持向量机9 2 2支持向量机反问题，lo 第3 章聚类算法l2 ： 1 数抛挖掘概述1 2 ：t2聚类分析概述13 ：；3主要聚类方法的分类1 4 3 ： 1 划分的方法( p a r t i t i o nm e t h o d ) 1 4 ：3 3 2 层次的方法( t l i e r a r c h i c a lm e t h o d ) 1 7 3 ： 3 基于密度算法( d e n s i t y b a s e dm e t h o d ) 1 8 ：j 3 4 基于网格的方法( g r i d b a s e dm e t h o d ) 1 9 3 3 5 基于模型的方法( m o d e l - b a s e dm e t h o d ) 2 0 ：j 4 核聚类算法的描述2 l ：j 4 1 核函数映射2 l 3 1 2m e r c e r 核2l 目录 3 4 3 核聚类算法2 3 第4 章基于聚类的支持向量机反问题解法2 5 4 1 算法描述2 5 4 2 仿真实验2 7 第5 章结论与展望3l 参考文献3 2 攻读硕士学位期间发表论文情况3 4 致谢： 5 第1 章绪论 曼曼曼曼曼曼曼曼曼曼皇曼! 曼! 曼曼曼曼曼曼曼曼曼皇舅i i； 一i 曼皇曼曼! 曼曼曼舅曼曼皇曼曼篡曼曼曼曼曼曼 1 1 课题来源 第1 章绪论 机器学习主要研究如何从一些观测数据出发，得出目d ，j 尚不能通过原理分析得到的 规律，利用这些规律去分析客观现象，对未知数据或无法观测的数据进行预测。现实世 界存在大量人类尚无法确认但却可以进行观测的事物，因此机器学习在现代科学、技术 到社会、经济等各领域都有着十分重要的应用。比如集成了表示与逻辑推理的专家系统， 基 二自然语言处理理论f f , j y t 器翻译系统等等。将研究的规律抽象成分类关系时，这种机 器学习问题就演变为分类问题，或称模式识别。 决策树学习是机器学习领域的研究热点之一，其基本算法采用自顶向下的贪婪搜索 方法遍j 万可能的决策空问，或者说，它以白顶向下递归的各个击破方式构造决策树。生 成决策树的一般过程是：首先，将所有训练事例作为树的根结点；然后根据某一肩发式 信息，将根节点向下划分成若干个子结点，若子结点的事例都属于一类，则此节点被看 作一个叶子结点，否则继续划分下去，直到f j j 现叶子结点为止。最著名的算法是i d 3 算 法，它选j f 】最小信息熵作为启发式信息。这种方法的优点足生成的决策树规模小而且计 算复杂度低，缺点是泛化能力不佳。 支持阳量机【2 1 1 3 j ( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 是一类新皋, j i f l 9 学习机器，囚其杰m 的，i l l ：u 匕j f 起广泛的关注。支持向量机是由贝尔实验室的v a p n i k 等人提出的一种新型机 器学习算法，它与传统的神经网络方法采，f j 的经验风险最小化归纳原则不同，实现了结 构风险最小化的归纳原则。支持向量机的基本思想是，对于一个给定的具有有限数量训 练样本的学习任务，如何在准确性( 对于给定训练集) 和机器容量( 机器可无错误的学 习任意训练集的能力) 之问进行折衷，以得到最佳的泛化能力。支持向量机最仞用来解 决模式谚 别的问题，目的是发现泛化性能好的决策规则。由于其优秀的泛化能力，支持 向量机已经被广泛的应用于其它的领域。 考虑到s v m 分类问隔与泛化能力之间的关系，可以设想使用s v m 最大问隔作为 决策树学习的启发式f 4 1 以s v m 理沦为基础，利用其反问题，将一个事例集划分为两 部分，通过求解s v m 反问题即可得到最大的问隔以及相应的划分。在本文中，我们提 - i - i l 人学l ：学硕十学位论文 i t ：了一科- 基于聚类的求解s v m 反问题的算法。 1 2 研究现状 1 2 1 支持向量机的研究现状 统计学是目前针对小样本统计估计和预测学习的最佳理论，系统的研究了经验j x l 险 最小化原则成立的条件、有限样本下经验风险与期望风险的关系以及如何利用这些理沦 找到新的学习原则和方法等问题。支持向量机作为统计学习理论的实现方法克服了神经 网络分类和传统统计分类方法的许多缺点，具备较高的泛化能力【5 j 。进入9 0 年代，该理 论在解决一系列实际问题中获得成功，表现出极好的学习能力尤其是泛化能力，从而引 起人们对这一领域的极大关注。目f j 这一领域正在快速发展，并且在许多领域都有应1 - j ， 比如模式识别【6 】f 7 1 、入侵检测【8 j 等。 s v m 的应用同其理论的发展相对比要滞后许多，其应用的范围和取得的效果同 s v m 的优越性很不匹配，主要原因是算法的限制，运行效率低是主要原因。因为标准 s v m 运行要消耗大量的时问，并且随着训练样本数量的增j j l l i j i i 练时间也会增加，尤其 对大量数据的处理更为棘手。现实当中所处理的问题一般数据量是非常火的，所以舀：很 多情况中受到约束。 目前，对s v m 的研究主要集中在以下几个方面1 9 】：改进训练算法；提高测试速 度1 ；核函数的构造、改进以及相应参数的调整1 1 2 】【1 3 1 ；利用s v m 解决多类问题。 1 2 2 聚类算法的研究现状 数据挖掘技术( d a t am i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机的实 际应用数据中，发现并提取隐含在其中未知的、可信的、有用的模式过程【1 4 l 。从上1 j j ：纪 七十年代开始至今，数据挖掘已取得了丰硕的成果并广泛应用于很多领域如：大中型企 业、银行保险、医学等。 聚类是数据挖掘中的一类重要技术，是分析数据并从中发现有用信息的一种有效手 段。它将数据对象分组成为多个类或簇，使得在同一个簇中的对象之间具有较高的相似 度。而不同簇之问差3 0 t t 曼大【1 4 l 。聚类在统计学、模式识别、图像处理、机器学习、生物 第l 章绪论 学、市场营销等许多领域都有广泛的应用。在数据挖掘中，聚类分析能作为一个独立的 - i ：乒b 来获得数据分们j 的情况，观察每个簇的特点，集中对特定的某些簇做特定的分析。 聚类分析还能够成为其他算法的预处理步骤，使其他的算法能够在生成的簇上进行进一 步f l 勺处理。 1l j 订已经提出的聚类算法有很多，主要是基于以下几利，方法l l 5 】： ( 1 ) 划分的方法：给定一个有n 个元组或者记录的数据集，构造k ( k n ) 个分组，每 一个分组代表一个聚类。对于给定的k ，可以给出一个初始的分组方法，以后通过反复 迭代来改变分组，使得每一次改进之后的分组方案都较d 订次好。 ( 2 ) 层次的方法：对给定的数据集进行层次似的分解，直到某种条件满足为止。 初始时每一个数据i 己录都组成一个单独的组，在接下来的迭代中，把那些相互邻近的组 介，i ：成一个组，直到所有的记录组成一个分组或者某个条件满足为止。 ( 3 ) 基于密度算法：能够帮助发现具有任意7 髟状的聚类。一般在一个数据空洲中， ，萄密叟f t l x q 象区域被低密度( 稀疏) 的对象区域( 通常就认为足噪声数据) 所分隔。 ( 4 ) 基于l 卅格的方法：首先将数掘空问划分成为有限个单元( c e 1 ) 的网格结构， 所仃f 1 j 处理都足以单个的单元为对象的，从而使得处理速度加快。 ( 5 ) 基于模型的方法：给每一个聚类假定一个模型，然后去习一找能够很好的满足 这个模型的数据集。这样一个模型可能是数据点在空间r i j 的密度分斫j 函数或者其它。它 的4 个潜在的假定就是：目标数据集足山一系y , j f j j 概率分斫i 所决定的。通常有两种尝 试方案：统计的方案和神经网络的方案。 1 3 本文研究的主要内容 支持向量机反问题( i n v e r s ep r o b l e mo fs v m s ) 在决策树的生成过程当中可以作 为非常有效的一种启发式。但是由于其本身运行的时f j 复杂度相当高，使得其在具有一 定舰模的数据集上运行相当困难，并且运行时问会随着数据量的增加成指数型上升。提 高反问题求解速度，降低时问复杂度成为亟待解决的问题，本文的主要工作是：利用聚 类算法来解决由于对所有数据进行划分而引起的高时问复杂度的问题，具体的章节结构 安排如下： 第l 章主要介绍了该课题的背景、意义以及与木课题相关的国内外研究状况。 1 河北人学l ：学硕十学何论文 第2 章介绍了支持向量机以及其反问题的一些相关概念和理论。 第3 章介绍了聚类算法的一些理论以及相关知识。 第4 章首先设计并实现了一种基于聚类的s v m 反问题求解算法，然后做相关的测试实 验，并对实验结果做了分析和说明。 第5 章是本文的总结与展望。 第2 章支持向鼙机及其反问题 第2 章支持向量机及其反问题 2 1 支持向量机( $ v m ) 支持向量机主要是用来处理二类问题的。在原始数据空i b j 中，如果存在一个线性函 数无错凝的把数据分开，那么称该数据集完全线性可分；如果存在一个线性函数可以以 低错误率把数据分开，则称该数据集足近似线性可分；如果存在非线性函数把数据集分 = j f ：，则称该数据集非线性可分。以下我们将详细介绍支持向量秒l f l 9 分类模型。 2 1 1 标准支持向量机 2 1 1 1线i 生s v m l 线性! 可分问题 刘于给定的一组数据 ( x l 。y i ) ，( x 2 ，y 2 ) ( 誓，”，) ，x r ”，y + 1 ，一l 】 i i j 。以被一个超j f 面 ( x ) + b o = 0 ( 2 - 1 ) 分j r 如果这个向量集合可以被超平面没有错误的分开，并且离超平面最近的向量与超平 i f j i 之l i j j 的足旺离( m a r g i n ) 是最大的，则我们说这个向量集合被这个最优超平面( 或最大 i l i j l ；j , 3 超i l z 面) 分丌。在超玉1 7 而一卜的点我们称为支持向量( s u p p o r tv e c t o r s ) ，如图1 所示： 间隔 图2 is v m 卅j 意图 。第一类 第二类 一 河北人学i ：学硕十；乏何论文 我们用下面的方式来描述分类超平面h 2h 3 黑患b o1 - i 三：- i 弦2 ， ( m 7 ) + 只= 一 、。 并且有紧凑形式： 只 ( w ，一) + 6 0 】ii = 1 ，2 ，3 ，7 ( 2 3 ) 为了求得m a r g i n 我们设x 一是h 2 上的一点，x + 是h 3 上距离x 一最近的点。能够得到 ( ，x 一) + 6 0 i ( 2 - 4 ) ( ，x + ) + 6 0 1 ( 2 5 ) m a r g i n = 0 5 母lx + 一x 一|( 2 - 6 ) x + = x 一+ 九”， ( 2 7 ) 由( 2 - 4 ) 、( 2 - 5 ) 、( 2 6 ) 、( 2 7 ) 可得： m a r g i n = 1 石而 ( 2 - 8 ) t 扫- t m a r g i n 越大分类器的泛化能力越强，要得到最大的朋n 曙砌只需要使l ，j 最小。我们 可以通过求解以下的最优化问题来得到最优解。 m i n b ( u ，) = i 1 ( w ，) s u b j e c tt o( 2 - 9 ) ” ( w ，一) + 6 】l，= l ，2 ，3 玎 利用l a g r a n g e 优化方法可以把上述最优分类面问题转化为其对偶问题即： m a x i m u m m ，( 口) = a ，一i 1 y , y ，a ，a ，( x ，) t = l 二，= i 。 ( 2 1 0 ) s u b j e c tt o y ，a = o ；c a ，o ，= 1 2 ，n a ，为原问题中与每个约束条件对应的l a g r a n g e 乘子。这是一个不窖式约束条件下的二 次函数寻优问题，存在唯一解。容易证明，解中将只有一部分( 通常是少部分) 乜不为 零，对应的样本就是支持向量。解上述问题后得到的最优分类函数是： 第2 章支持向鼙机及其反问题 ( x ) = 只a ? ( 一x ) + h o ( 2 1 1 ) r = l 式i l ，的求和实际上只对支持向量进行。b 是分类闽值，可以用任一个支持向量满足( ( 2 3 ) 。f j 的等号) 求得，或通过两类中任意一对支持向量求得。在训练得到最优平面后，对于 给定的未矢样本x ，只需要计算s i g n ( , 4 ，x + b ) ，即可判定x 所属的类别。 2 线性i 不可分问题 最大问隔超平面是在线性可分的前提下讨论的，在线性不可分的情况下，日标函数 i t ( 0 ) 的值将是无穷大的。可以在约束条件上加入一个松弛变量毒，0 ，这时的最大辐 超i i 而称为广义最优分类超平面。 m i n 卅，) ：委( w ) + c n ， ，= l s u b j e c tt o ( 2 1 2 ) 只【( w x ) + b 】l 一考， f = 1 ，2 ，3 ，7 我们引入考，的目的就是允许错分的情况出现，c 是一个t l jj 订广e j 己选择的惩罚参 数，( 1 越大意味着对错误出现进行的惩罚更i 苛，参数c 也可以被认为是一个调整因子。 s v m 更倾向j j ：在使分类川霸m a r g i n 最人化的f j ，j 提下使c 最小。( 越- 人 ；现错分数据的 i t j 能性也就越小。 4 l i 应的，广。义最优分类超平丽可以通过解下而的对偶问题得到： m a v i m u mw ( a ) = a ，一i 1 ”即，c c 胁x ，) 7 2 。 “2 1 ( 2 1 3 ) s u b j e c tt o y ，a ，= 0 ；c 0 ，o ，i = 1 2 ，n l l l 此可得的最优分类超二i 面的形式同( 2 1 1 ) 。 2 1 1 2 非线性s v m 对于非线性问题，可以通过非线性变换转化为某个高维空阳j 中的线性问题，在变换 空f i i j 求最优分类面。这种变换可能比较复杂，因此这种思路在一般情况下都不容易实现， 化是注意到在以上的对偶问题中，无论寻求最优函数还足分类函数部只涉及到训练样本 7 洞，l 匕人学f ：学硕十学何论文 之问的内积，这样，在高维空问实际只需要进行内积运算，而这种内积运算是可以在原 空间中的函数实现的，甚至没有必要知道变化的形式。即使变换空间的维数增加很多， 在其求解最优分类面的问题中并没有增加多少的计算复杂度。其基本思想如下：支持向 量机利用某种事先选择的非线性映射，将输入向量x 映射到一个高维特征空间，然后在 高维空问中求最优分类面。如图2 2 ： 特征窄问中最优超r - 咖 i 。 ooo o 输入窄问 特缸窄问 幽2 - 2 义持向量机对数据的1 f 线忭映牙于 根据l b e r t s c h m i d t 定理，在h i l b e r t 空问中两个点的内积有下面的等价形式： ( z l ，z 2 ) = ( 1 r z ，( x 1 ) z ，( x 2 ) c x ( x i ，x 2 ) ( 2 1 4 ) 其中k ( x 。，叠) 称为核函数。 在高维空f n j 中，最优分类超平面有如下形式： f ( x ) = ( 庐( x ) ) + b 0 ( 2 1 5 ) 求解最优化问题的形式如下： m i n 驴( ，) ：昙( ，) + c n 考， 二t=l s z ，b j e c tt o 只【( ，庐( x ) ) + b 】1 一号， f = 1 ，2 ，3 ，7 二次规划问题的对偶形式： m a x f 研z ，朋w ( 口) ：兰a ，一1 窆( 咖( 一) 驴( _ ) ) 一， y , y j a , a j t = l = 1 s l t b j e c tt o y ，a ，= o ；c a ，o ，净1 ，2 ，n = 1 r ( 2 1 6 ) ( 2 1 7 ) 筇2 章支持向鲢机及其反问题 k ( 一，x ，) = ( 誓) ( 恐) 得在特征空间中的最优分类如下； 厂( x ) = y # o k ( x , x ) + b o ，= l ( 2 1 8 ) ( 2 1 9 ) 采用不同的内积函数会导致不同的支持向量机算法，内积核函数一般叫做核函数， f i l 玎的核函数主要有以下几种： 多项式核函数：k ( x ，工，) = 【( j x ，) + 1 ， 高斯核函数：k ( 忙一x , 1 1 ) = e x p ( 一厂忙二一| 2 j 其中r 为常数 两层 ：f i i 经刚络核函数：k ( x ，x ，) = s u ( x x ，) + c 】其中z ，为常数，s 为s i g m o i d 函数。 2 1 2 多分类支持向量机 s v m 本身是解决两类分类问题的，人们在两类算法的基础上，对多类算法进行了 深入的研究。目6 仃处理多类s v m 问题的方法主要有一对一方法、一对多方法、有向无 ， 付吲疗法、层次方法和纠错编码方法等。以下我们主要介绍一对一万法、一对多方法。 一对多的方法( o n e a g a i n s t t h e r e s tm e t h o d ) 支持向量机多类分类方法最早使删的算法就是一刘多方法，要构造多类分类器，通 常的方法是构造一系列的两类分类器，其中的每一个分类器都把其中的一类同余下的各 类分歼。然后根据此推断输入的向量归属。一对多的方法是对二j ：k 类问题构造k 个分类器， 在构造某个分类器的时候，将属于这类的数据样本标记为矿类，彳i 属于此类的样本标记 为负类。测试时，对测试数据分别计算各个子分类器的决策函数值，选取函数值最大所 对应的类别为测试数据的类别。 此种算法一个很明显的优点是只需要训练k 个两类分类器，所以得到的分类函数的 个数也比较少，分类速度也比较快。 这种算法的缺点也是很明显的，每个分类器的训练都是将全部的样本作为训练样 本，这样就需要求解k 个n 个变量i f , j - - 次规划问题，因为支持向量机的训练时f h j 是随着训 练样本数量的增加而增j j 订的，所以这科，方法的训练时州比较长。另外，此种算法还会出 河北人学i ：学硕十学传论文 曼舅舅曼i i 曼曼皇曼曼曼曼曼曼曼皇曼皇! 曼曼曼曼曼曼皇! ! ! 曼曼! 曼曼曼曼皇! 曼寰舅曼寰曼皇曼曼曼! ! 曼曼皇曼皇舅曼曼曼皇曼曼皇曼皇皇曼曼! ! 曼曼曼曼 现不对称的问题，处理这类问题的时候我们通常采用的方法是对不同类别使用不同的惩 罚因子。 一对一的方法( o n e a g a i n s t t h er e s tm e t h o d ) ： 这种方法也是基于两类问题的分类方法，不过这罩的两类问题是从原来的多类问题 中抽取的。具体做法是：分别选取两个不同类别构成一个子分类器。，这样共有k ( k 1 ) 2 个s v m 予分类器。在构造类别i 和类别j 的s v m 予分类器时，在样本数据集中选取属于 类别i 、类别j 的样本数据作为训练数据，并将属于类别i 的数据标记为f ，将属于类y ，, f 1 一 的数据标记为负。 测试时，将测试数据对k ( k 1 ) 2 个s v m 子分类器分别进行测试，并累计各类剔的投 票，选择得分最高者所对应的类别为测试数据。 在一对一的方法中，需要多个两类的分类器。对k 类问题我们就需要构造k ( k 1 ) 2 个两类分类器，比我们介绍的一对多的分类方法得到的分类器数目多很多，但是每个分 类器的规模却要小很多。如果k 很大就会严重的影响算法的执行速度。 总的来说，这种方法的优点是其训练速度较一对多方法快，缺点是分类器的数| = l k ( k 一1 ) 2 随分类数k 急剧增加，导致在决策时速度很慢，且存在不可分区域。 此外还有其它的一些方法，基于二叉树的多类支持向量机分类方法，这种方法需要 训练的两类支持向量机的数量少，随着训练的进行，总共训练样本数和一对多方法棚比 减少了许多。多级支持向量机方法，采用先聚类再分类的策略，不存在明显的不可分区 域。因此它n , j n 试精度明显高于上述几种方法，而且测试速度也较快。但是，这种方法 在处理维数很高的数据时需要构造邻接矩阵，这就导致训练时间比较长。对于大规模问 题，一对一方法和决策有向无环图方法更适于实际应用。二者所需自, j i j i i 练时问相当，测 试阶段决策有向无环图方法更快些，但其结构使实现过程更为复杂。 2 2 支持向量机反问题 对于给定的一组没有决策属性的样本点，我们可以随机的把其分为两类。此时我们 可以利用前面的知识来求出最优分类超平面，并计算出最大间隔。若划分为两类的样本 点线性不可分，间隔计为0 。显然，问隔的大小取决于对原样本点的随机划分，支持向 量机反问题就是如何对样本点进行划分，才能使最优分害q 超平而的帕j 隔达到最大。对支 一1 0 一 第2 蕈支持向量机及其反问题 持向量机反问题的研究是源自于设计一种新的决策树生成算法。现有的很多决策树算法 如c 4 5 ，往往得不到好的执行效果，山于支持向量机中最优超平面的1 1 i j 隔与其推广能力 的关系，具有最大问隔的样本划分，被认为是生成决策树的新的启发式信息。 支持向量机足一个优化问题，其数学描述如下：设s = ，x ：，靠) 为一个包含个 事例的给定数据集合，且置r ”，= l ，2 ， 另外 q = i 厂括口 u n c t i o n 歹。0 1 7 1 s i o l ，一1 ) ) 对j j ：给定的一个函数厂q ，样本集s 被划分为两个子集，并可以汁算f 1 相应的阳j 隔 ( m a r g i n ) ，我们用m a r g i n ( f ) 表示由函数厂所决定的问隔( 泛函) ，那么s v m 反问题 就足要求解如下问题： m a x i m u n t 2 ( ma r gi n ( f ) ) ( 2 - 2 0 ) 岍- - f 此优化| 、u j 题的复杂度随着训练样本个数的增加而千i - 1j 4 h 1 - - , 数级增长，枚举出q 中所有的 函数来求最大洲隔是不现实的，而且目自仃也很难给出一个十分严e 格的算法，但足我们可 以川减少qr 。i j 函数个数的方法来降低其复杂度。本文提 f j 了一种利用聚类来求解s v m 反l u j 题的办法。 - a t 人学i ：学硕十学位论文 3 1 数据挖掘概述 第3 章聚类算法 计算机技术和通信技术的迅猛发展将人类社会带入到了信息时代。在最近的十几年 晕，随着数据库技术的成熟和数据应用的普及，人类积累的数据量急剧增加。据统计， 全球棚有的数据量每2 0 个月就可以翻一番。我们拥有了数量极其庞大的数据，而且数 据类型也越来越复杂、结构越来越多样。但是，如果没有有效的办法从这些快速增长的 海量数据中提取有用的信息和知识，我们就会感到面对信息海洋像大海捞针一样束手无 策，大量的数据被捕述为“数据丰富，但信息贫乏”，数据也就变成了“数据坟墓”。而 对如此巨大的数据资源，人们迫切需要一种新技术和自动工具，以便能够利用智能技术 帮助我们将这巨火数据资源转换为有用的知识与数据资源，从而可以帮助我们科学的进 行各种决策。于是数据挖掘( d a t am i n i n g ，简称d m ) 便应运而生了【1 6 1 。 。数据挖掘的定义包含了以下四个层次： ( 1 ) 数据源必须足真实的、大量的、含噪声的； ( 2 ) 发现的是用户感兴趣的知识； ( 3 ) 发现的知识是可以接受、可理解、可运用的，最好能用自然语言表达发现结 果的； ( 4 ) 所有发现的知识都足相对的，是有特定前提、约束条件、面向特定领域的。 一般的数据挖掘过程可用如下的处理过程加以说明： ( 1 ) 首先熟悉应用领域的数据、背景知识，明确要完成的k d d d m 任务性质； ( 2 ) 数据选择根据用户要求，从数据库中提取与k d d 相关的数据，k d d4 9 - 从这些数 据巾进行数据提取； ( 3 ) 数据预处理与转换，从与k d d 相关的数据集合中除去明显错误的数据和冗余 的数据，进一步精简所选数据中的有用部分，并将数据转换成为有效形式，以使数据挖 掘更为有效； ( 4 ) 数据挖掘根据知识发现任务的要求，选择合适的数据挖掘算法( 包含合适的 模型和参数) ，在数据库中寻求感兴趣的模型，并用一定的方法表达成某种易于理解的 1 2 第3 章聚类算法 j 侈j 弋： ( 5 ) 模式解释对发现的模型进行解释和评估，必要时需要返回前面处理中的某些 步骤以反复提取； ( 6 ) 知谚 评价将发现的知谚 以，h 户能够理解的方式提供给用户。 3 2 聚类分析概述 将物理或抽象的集合分组成为山类似的对象组成的多个类的过程称为聚类。由聚类 所，卜产的足一组数据对象的组合，这些对象与同一个簇中的对象彼此4 1 1 1 l 2 ，与其它簇中 的对象桐异。在订：多应刚中，可以将一个簇的数据对象作为一个整体来对待。 聚类分析与分类不同，它要划分的类别是未知的。聚类分析源于许：多研究领域，包 指数据挖掘、统计学、生物学、以及机器学习。它在很多方面有着广泛的应用。例如对 j ，卜物研究，聚类能 ：j 于推导植物希j 动物的分类，对撼囚进行分类，获得对种群r i j 固有 结构的认以：聚类在地球观测数据库, i ，, i i - i b 2 的地区的定位；汽车保险单持有者的分组； q 还- 可以从一个城市的房地产信息数据库中，根据房子的类型、价值及地理位置分成不同 f f , j 类；此外，聚类还可以月】来对w e b 上不同类型的文档进行归类。 聚类分析是一个具有很强挑战性的领域，它列一些潜在的应用分析算法提出了特别 的要求，数据挖掘对聚类的典型要求如下i l6 j ： ( 1 ) 可仲缩性：诌：多聚类算法对于小于2 0 0 个数据刈象的较小数据集能够很好的 进行聚类，但是，一个大型数据集l - - j | j z 4 匕包含几百万、几干万乃至更多的对象。虽然通 j t 1 1 1 f f - ：可以减少要处理的数据量，但是抽样会刘。聚类的结果带来影响甚至会产生错误的 结果。因此，我们需要具有较高的可伸缩性的聚类算法。 ( 2 ) 处理不同字段类型的能力：影i ：多算法是设计来对数值型数据进行聚类的。然 而，在询：多应用巾待聚类的数据可能是二值型、枚举型、序数型，或者这些数据类型的 混合。聚类算法需要具有处理这些数据的能力： ( 3 ) 发现具有任意形状的聚类能力：许多聚类算法采用基于欧几罩得距离或者曼 i l 合坦距离的相似性度：量：方法来确定聚类，而这类算法发现的聚类通常是球状的、大小和 密度近似的。然而，聚类可能是各种形状的。这就要求聚类算法能够发现任意形状的聚 类。 1 3 j 司北人警l ：学硕十学1 谚论文 ( 4 ) 输入参数对领域知识的弱依赖性：许多聚类算法要求用户输入一定的参数， 如需要发现的聚类数目、结果的支持度及置信度等。而聚类结果通常对这些输入的参数 非常敏感。但另一方面，这些参数往往很难确定，尤其对于高维数据集更是如此。这不 仅给用户带来了难题，也使得聚类的结果难以控制。一个好的聚类算法应该给出一个j ( ， 的解决方法。 ( 5 ) 能够处理异常数据：现实世界的许多数据中都包含一些异常或错误的数据， 有些聚类算法对这些数据非常敏感，可能会产生错误的聚类结果。 ( 6 ) 对输入顺序不敏感：有些聚类算法对数据的输入顺序非常敏感，例如，对于同 一个数据集，用不同的顺序输入到某个算法中，就可能会产生完全不同的聚类结果，这 是我们不希望的。 ( 7 ) 处理高维数据的能力：数据库或者数据仓库中的数据可以有几十乃至成阿上 千个维度或属性。许多聚类算法只擅长处理低维数据，在高维数据空间中，数据可f j 8 ；l l 常稀疏并且高度扭曲。因此，高维空间中数据的聚类是一个很大的挑- 饯。 ( 8 ) 基于约束的聚类：在现实世界中的一些应用，可能需要在一些约昧件下来 进行聚类分析。例如要在一个城市巾为给定数目的a t m 机选择位置，我们就要刘住宅 区进行聚类，同时考虑河流、公路等问题。我们希望聚类算法可以在考虑这些约束条件 的情况下，仍有较好表现。 ( 9 ) 可解释性和可用性：用户希望聚类结果是可解释的，可理解和可用的。也就 是说，聚类可能需要和特定语义解释和应用相联系。应用目标如何影响聚类方法的选择 也是一个重要的研究课题。 3 3 主要聚类方法的分类 目前已经存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应用。 大致可以分为以下几种：划分的方法、层次的方法、基于密度的方法、基于网格的方法 和基于模型的方法。 3 3 1 划分的方法( p a r titio nm e t h o d ) 给定一个，7 个对象或元纽的数据库，一个划分方法构建数据的k 个划分，每个划分 1 4 第3 节聚类羿法 表示一个类( 簇) ，且七，7 。也就是说，它将数据划分为足个组，同时满足两个要求， 首先，每个组至少包含一个对象。其次，每个对象必须属于且只属于一个组。 给定要构建的划分的数日七，首先要创建一个初始的划分，然后采