（计算机软件与理论专业论文）降维方法在特征提取中的应用研究.pdf

摘要改进的降维方法在特征提取中的应用研究学位专业：计算机软件与理论博士生：王和勇导师：李磊、姚正安教授摘要随着多媒体技术、网络技术的迅速发展，图像信息的应用同益广泛，对规模越来越大的图像数据库中的可视信息进行有效管理成为迫切需要解决的问题，基于内容的图像检索是解决这一问题的关键技术之一。图像特征的提取与表达是基于内容的图像检索技术的基础。一般来说，图像特征的表示均是高维向量，故在进行图像特征的提取与表达时，即使对于低分辨率的图像也常常会产生非常高维的数据。对于大型的图像数据库，高维向量的存储以及高维空间中距离的计算，其空间复杂度和运算复杂度非常高。针对常用的高维特征向量的降维方法，本文提出了以下改进：一、针对主成分分析法( p r i n c i p a lc o m p o n e n ta n a l y sjs ，p c a ) 在处理非线性降维问题上的不足，以及核主成分分析( k e r n e lp c a ，k p c a ) 方法在处理降维问题上计算速度方面的缺陷，提出了基于聚类的核主成分分析方法。试验结果显示：基于聚类的核主成分分析方法具有良好的特征提取性能，相比核主成分分析方法大大提高了特征提取的速度。二、针对局部线性嵌入( l o c a l l y n e a re m b e d d in g ，【i 正) 方法在计算速度和近邻点个数世的选取上的不足问题，研究了该方法的扩展，提出了基于聚类和改进距离的l l e 方法。基于聚类l l e 方法大大缩减了计算【i ，e 方法的时间；改摘要进距离的l l e 方法在近邻点个数取值比较小时的情况下，也可得到良好的效果，而原始的l i 。e 方法要达到棚同的效果，近邻点个数的取值通常要大很多。同时，改进距离的】。l e 方法可以模糊近邻点个数的选取。试验结果显示：基丁聚类和改进距离相结合的l l e 方法相比原来的l l e 方法大大提高了降维速度和扩大r 参数k 的选取。三、图像特征提取的一般方法是把数字图像转化为向量，图像数据集变为向量集，根据向量的距离的远近确定图像属于哪一类。在数字图像转换为向量的过程中，没有考虑图像像素之川的位置关系，这样就会导致图像特征信息的损失。针对这种情况，本文提出了用小矩阵覆盖的方法，对图像的每一个像素都用小矩阵覆盖，然后把各个小矩阵看成数值组成向量( 实际上是矩阵) ，然后针对小矩阵向量进行降维。l l e 方法可以解决把一幅数字图像直接转换为向量的问题，而对小矩阵向量组成的矩阵没有办法解决，对此，本篇文章在基于图像直接转换为向量f | 勺i 上e 的基础上提出了- - e e 新的维数缩减方法，即小矩阵向量的l l e 维数缩减方法( s m a l lm a t r ixv e c t o rl o c a l l yl i n e a re m b e d d i n g ，s m v i l e ) 。州手写数字图像和纹理图像的试验显示：基于小矩阵覆盖的s m v l l e 方法比直接转换为向量的虬e 方法效果好。关键词：数字图像，图像检索，特征提取，维数缩减，k p c a ，l o c f t ll yl i i l e a l -e m b e d d in gt h ea p p l i e dr e s e a r c ho fi m p r o v e dd i m e n s i o nr e d u c t i o no nf e a t u r ee x t r a c t i o nm a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r yn a m e ：w a n gh e y o n gs u p e r v i s o r ：l il e ia n dy a oz h e n g a na b s t r a c tw i t ht h ed e v e l o p m e n to ft e c h n o l o g yo ft h em u l t i m e d i aa n di n t e r n e t ，v i s u a li n f o r m a t i o ni su s e dm o r ea n dm o r ew i d e l y ，a sar e s u l t ，e f f e c t i v em e t h o d so fm a n a g i n gi m a g ed a t a b a s e sa n dv i s u a li n f o r m a t i o na r en e e d e d a sak e yt e c h n i q u e ，c o n t e n t - b a s e di m a g er e t r i e v a l ( c b i r ) h a sb e c o m eo n eo ft h em o s ta c t i v er e s e a r c ha r e a si nt h ep a s tf e wy e a r s a sf o rt h ec o n t e n t b a s e di m a g er e t r i e v a l i ti st h ei m p o r t a n tr e t r i e v a lt e c h n o l o g yo nf e a t u r ee x t r a c t i o no fi m a g e s i ng e n e r a l ，t h ef e a t u r eo fi m a g e si sh i g h d i m e n s i o n a lv e c t o r s oe v e nf o rt h el o w - r e s o l u t i o ni m a g e s ，t h e r ea l s oh a v eav e r yh i g h d i m e n s i o n a ld a t a t h u st h ec o m p u t i n gc o m p l e x i t yo fh i g h d i m e n s i o n a lv e c t o rs t o r a g ea n dh i g h - d i m e n s i o n a ls p a c ed i s t a n c ec a l c u l a t i o n st ol a r g ed a t a b a s eo fi m a g e sw i l lb ev e r yh i g h i no r d e rt oo p t i m i z et h er e d u c t i o no fh i g h d i m e n s i o n a lf e a t u r e sv e c t o r ，s o m ei m p r o v e m e n ti sm a d ei nt h i sp a p e ra sf o l l o w i n g s ：f i r s t l yi tp o i n t so u tt h ed r a w b a c k so ft h eg e n e r a lp r i n c i p a lc o m p o n e n ta n a l y s i s ( p c a ) w h e ni ti su s e dt os o l v en o n l i n e a rp r o b l e m t h ek e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ( k p c a ) a n di t sd r a w b a c k so nc o m p u t i n ga r ee x p l a i n e ds e c o n d l y t h e nk p c ab a s e do uc l u s t e r i n gi sp r o v i d e di nt i r ep a p e r r e s e a r c hr e s u l ts h o w st h a tt h ek 2 c ab a s e do nc l u s t e r i n gh a sm o r ee x c e l l e n tp e r f o r m a n c eo ff e a t u r ee x t r a c t i o nt h a nk p c a s e c o n d l y , t h ee x t e n s i o no fc l u s t e r i n ga n di m p r o v e dd i s t a n c el o c a l l yl i n e a re m b e d d i n g ( l l e ) l b rd i m e n s i o nr e d u c t i o ni si n v e s t i g a t e d l o c a l l yl i n e a re m b e d d i n g( l l e ) i so n eo ft h em e t h o d si n t e n d e df o rd i m e n s i o nr e d u c t i o n ，i t se x t e n s i o no nu s i n gc l u s t e r i n ga n di m p r o v e dl l ef o rd i m e n s i o nr e d u c t i o ni si n v e s t i g a t e d u s i n gc l u s t e r i n gc a nr e d u c et i m e - c o n s u m i n g t h ei m p r o v e dd i s t a n c el l ei ss u i t a b l ef o rs e l e c t i n gt h en u m b e rko ft h en e a r e s tn e i g h b o r s w h e nt h en u m b e rko t lt h en e a r e s tn e i g h b o r si ss m a l l ，i tc a l la l s oo b t a i ng o o dr e s u l t s w h i l et h eo r i g i n a ll l ea l g o r i t h mo b t a i n st h es a m er e s u l t s ，t h en u m b e rko f t h en e a r e s tn e i g h b o r sm a yb em u c hl a r g e r e v e ni ft h en u m b e rko ft h en e a r e s tn e i g h b o r su s i n gt h ei m p r o v e dd i s t a n c el l ei ss e l e c t e dl a r g e r ，t h er e s u l ti ss t i l lr i g h t t h a ti s ，t h ei m p r o v e dd i s t a n c el l ei sn o ts e n s i t i v et ot h es e l e c t i o no fk i ti sa l s os h o w nt h a tt h ei m p r o v e dd i s t a n c el l eb a s e dn nc l u s t e r i n gh a sl e s sc o m p u t i n gt h a nt h eo r i g i n a ll l ea l g o r i t h ma n de n l a r g e st h ec h o s eo f p a r a m e t e rkb ye x p e r i m e n t t h i r d l y ，s m a l lm a h i xv e c t o rl o c a l l yl i n e a re m b e d d i n g ( s m v l l e ) ，i sg i v e ni nt h i sp a p e ri m a g e so ft h eg e n e r a la p p r o a c hi st oe x t r a c tt h ed i g i t a li m a g ei n t ov e c t o ra n de x t l a c ti m a g ed a t as e t si n t ov e c t o rs e t s i nb o t ho ft h e mt i l et y p eo fd i s t a n c ei sa c c o r d i n gt ot h ed i s t a n c ev e c t o ri m a g e s i nt h i sp r o c e s st h er e l a t i o no ft h ei m a g ep i x e l si sn o tc o n s i d e r e d ，t h u sw i l ll e dt ot h el o s so fs o m ei n t b r m a t i o n t h ei m a g e si nt h ed a t a b a s ea r eo f t e nr e p r e s e n t e da sv e c t o r si nah i g h d i m e n s i o n a ls p a c ea n dac l a s s i f i c a t i o ni sa n s w e r e db yc l a s s i f y i n ga l li m a g ev e c t o r st h a ta r ep r o x i m a lt oe a c hc a t e g o r y ，u n d e ras u i t a b l es i m i l a r i t ym e t r i c t oo v e r c o m ep r o b l e m sa s s o c i a t e dw i t hh i g hd i m e n s i o n a l i t y ，s u c ha sh i g hs t o r a g ea n dc l a s s i f i c a t i o nt i m e ，ad i m e n s i o nr e d u c t i o ns t e pi su s u a l l ya p p l i e dt ot h ev e c t o r st oc o n c e n t r a t er e l e v a n ti n t b r m a t i o ni nas m a l ln u m b e ro l d i m e n s i o n s l o c a l l yl i n e a re m b e d d i n g ( l l e ) i saw e l l k n o w nd i m e n s i o nr e d u c t i o ns c h e m e h o w e v e r ，s i n c ei tw 0 1 。k sw i t hv e c t o r e dr e p r e s e n t a t i o n so fi m a g e s ，l l ed o e sn o tt a k ei n t oa c c o u n tt h ei vs p a t i a ll o c a l i t yo f p i x e l si ni m a g e s ，t h u ss o m ei n f o r m a t i o nw i l lb el o s t i nt h i sp a p e l ，an e wd i m e n s i o nr e d u c t i o ns c h e m e ，c a l l e ds m a l lm a t r i xv e c t o rl o c a l l yl i n e a re m b e d d i n g ( s m v l l e ) ，i sp r e s e n t e d t h i ss c h e m ew o r k sd i r e c t l yw i t hi m a g e si nt h e i rn a t i v es t a t e ，b e c a u s eas m a l lm a t r i xv e c t o rc a nr e d u c et h el o s so fs p a t i a ll o c a l i t yr e l a t i o na m o n gp i x e l si nf a c t ，as m a l lm a t r i xv e c t o ri sm a t r i x e x p e r i m e n t so nh a n d w r i t t e nd i g i ti m a g e sa n dt e x t u r ei m a g e ss h o wt h a ts m v l l ei ss u p e r i o rt ol l ei nt e r m so f q u a l i t yo f t h ed i m e n s i o nr e d u c t i o n k e yw o r d s ：d i g i ti m a g e ，i m a g er e t r i e v a l ，f e a t u r ee x t r a c t i o n ，d i m e n s i o nr e d u c t i o n ，k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ，l o c a l l yl i n e a re m b e d d i n gv第章绪论第一章绪论随着多媒体、网络技术的迅速发展，图像信息的应用f | 益广泛，对规模越来越大的图像数据库的可视信息进行有效的管理成为迫切需要解决的问题。灵活、高效、准确的图像检索技术是解决这一问题的关键技术之一。传统的图像检索基于文本方式，使用关键字或自由文本描述图像数据库中的每幅图像，采用文本匹配检索。但目前计算机视觉技术还不成熟，达不到对图像的描述性关键字和语义信息的自动提取，而人工提取方面费时，另方面带有强烈的主观性。信息处理技术的曰益发展和深化，及相应标准的出台，为图像信息的加工、处理和检索提供了条件。但随着对信息需求的不断增加和同益迫切，原有的图像检索系统己远远不能满足要求，由手工进行图像注解这一方法来进行高效的图像检索也将变得同益困难。为了克服这一困难，新兴的基于内容的图像检索技术( c o n t e n t b a s e di m a g er e t r i e v a l ，c b i r ) 1 6 受到人们越来越多的重视。c b i r 是一种信息检索技术，它关注的是以基于内容的方法快速获取目标信息。一般地，图像内容可由一组低层特征来描述，其中包括颜色、形状、纹理、空间位置以及对象间的相互关系等。c b i r 是一种相似匹配，它使用距离度量函数等来计算两个图像间的相似度。c 3 1 r关键的步骤是对图像特征信息的提取。1 1 研究动机特征提取的基本任务是从许多特征中找出那些最有效的特征 7 j 。一般地，对图像特征的表示是高维向量，即使对于低分辨率的图像也常常会产生非常高维的数据。高维数据的负面影响是占用储存空削、运行速度慢，从而对储存和检索带来影响。并且，如果用很多特征进行图像检索，则无论是从计算复杂度还是从对图像检索的设计来说都是不适宜的。因此，研究如何把高维特征空间压缩到低维特征空间以便进行有效的检索是特征提取一个重要的内容。第章绡| 对于大型的图像数据库，高维向量的存储，以及高维空i i l j 中距离的计算，其空削复杂度和运算复杂度都非常高。然而，有意义图像空川( 如指纹图像、脸谱图像等) 的本征维数是相对较低的，即高维图像数据存在相对低维的特征表达空问，存在将高维图像识别问题向低维转化的可能性。高维数据的降维处理是减少“维数灾难”的有效手段。例如，一个文字图像可以有几千个数据 7 ，一个心电波形可能有几千个数据，一个卫星遥感的图像数据量更大。为了有效地进行图像检索，就要对原始数掘进行降维。对于高维数据，为了便于处理，解决问题的方法是降低数据的维数，维数缩减除了可以节省储存空间、提高图像的检索速度外，还具有去噪功能 8 。本文手要是研究特征提取中降维方法的有关问题。在已有降维方法的基础上，进行降维方法的改进和扩展，以便更有效地提取特征，满足分类和检索的需耍。1 2 降维方法研究背景1 2 1 特征提取特征提取的基本任务是从众多特征中求出那些对分类最有效的特征，从而实现特征空川i 维数的缩减。原始特征的数量可能很大，或者说样本是处于一个高维窄川中，通过映射或变换的方法，把高维数据降低到低维空i b j 中的数据，这个过程称为降维，足特征提取方法中的一个重要内容。1 2 2 降维方法的分类传统的降维方法可以分为线性和非线性两类。线r 降方法丰要有：主成分分析( p r i n c i p a lc o m p o n e n ta n a y s ig ，简称p c a ) 9 方法和f 【s h e r 线性判别方法( f is h e r1 【l l e a rd is c r i m i n a n ta n a l y s i s ，简称f l d ) 1 0 等。非线性降维算法 u 】主要有自组织特征映射( s e lf - o r g a n z i n gf l e a t u t em a p ，s o m ) 1 2 ，1 3 、等度栅映射( i s o m e t r cm a p p i n g ， s o m a p ) 】4 、局部线性嵌入( l o c a l yi in e a rg m b e d d i n p ：，l l e ) 1 5 方法等。s o m 计算时问比较k ，js o m a p 力图保持流形的全部几何性质，j 上e 方法力图保持局部几何性质。第章绗恐1 2 3 降维方法的研究情况p c a 是常用的线性特征提取方法。从特征选取1 l 勺评价角度讲，它力图找到方差最大的特征。通过求解样本协方差矩阵的特征值和特征向量。j o l l i f f e 在文献 1 6 中叙述了p c a 的发展历史。奇异值分解( s i n g u l a rv a l u ed e e o m p o s i t i o n ，s v d ) 是p c a 方法的基础，它是由b e l t r a m i 1 7 s n j o r d a n 1 8 各自独立提出的。p c a是由p e a r s o n 1 9 和h o t e l l i n g 2 0 提出。关于p c a 方法的重要的文献在p r e i s e n d o r f e r 和m o b l e y 出版的书 2 1 中有记载。f i s h e r 线性判别方法在文献 2 2 详细而深入地描述了最初出f i s h e r 1 6 所提出的线性可分性方法，文献e 2 3 ，2 4 ，2 5 ，2 6 也进行了这方面的论述，f l d 方法使投影后的模式样本的类间散布矩阵最大而类内散布矩阵最小，也就是说，投影后保证模式样本在新的空间中有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。s o m 女台于2 0 世纪8 0 年代早期，k o h o n e n 发表了一系列关于s o m 的文章 2 7 ，在 2 8 2 9 中可以看到很好的介绍。算法的收敛性在 3 0 中得到证明。s o m 是一种非线性的多维数据可视化方法，该算法的目标是用低维目标空间中的点表示高维空间的点，使得这利一表示尽可能地保留原始的距离和相似性关系。i s o m a p 2 0 是近来用于非线性降维的一个方法。它来源于传统的降维算法m d s ( m u l t i d i m e n s i o n a ls c a l i n g ) 3 l - 3 4 ，骇算法从保持全局结构的角度出发，应用图论的知识完成降维。i s o m a p 先使用一种方法确定每一点的邻域，如k 近邻方法。即寻找在观测空间欧氏距离下最近的k 个点或者阂值的方法，即认为某个半径以内的所有点为近邻；然后认为近邻点是互相连接的，从而得到一个部分连接的图。再利用上一步得到的相连接点的距离构造出来邻接矩阵，接着使用最短路算法计算所有点之间的距离，得到每两点之间的距离，写成一个矩阵，可以认为该方法所描述的距离是最短路径的测地线距离逼近。最后使用多尺度分析算法对该矩阵处理，得到高维数据集在低维空间中的相应坐标。l l e 方法 1 5 是由r o w e i s 和s a u l 于2 0 0 0 年提出的种新的非线性降维方法。它的提出极大地拓展了关于降维的认识，引起人们广泛的注意。通过数据集蕴涵第申埔沦的本质特征来研究降维问题。根据泰勒定理，可微函数具有良好的局部线性，即每点的微小邻域总可以用线性模型柬较好的近似。所以如果数据集合可以是来自某连续可微流行的离散采样，就可以利用数据集的局部线性。l l e 方法就是基于这种考虑，即数据流形的局部线性的一种非线性降维方法。1 2 4 降维方法在本文的扩展对于以上多种降维方法，本文主要研究了p c a 方法和l l e 方法的扩展。其中包括：在p c a 扩展到k p c a 的基础上进行研究，提出了基于聚类的k p c a 方法：在l l e的基础上进行研究，提出了基于聚类和改进距离的l l e 方法；对于特征提取，在i 上e 的基础上提出了小矩阵向量的l l e 维数缩减方法s m v l l e 。1 3 本论文主要成果本论文主要成果主要包括三部分，第一部分是基于聚类的k p c a 、第二部分是聚类和改进距离的l l e 方法，第三部分是小矩阼向量的l l e 维数缩减方法s m v l l e ，下面分别进行描述。1 3 1 基于聚类的k p c a 方法本论文的第三章在p c a 扩展到k p c a 的基础上，提出了基于聚类的k p c a 方法。p c a 方法的基本原理是通过坐标变换，用尽量少的特征( 主成分) 代表尽量多的信息( 方差) 。p c a 的一个不足是只能做线性变换。基于核的主成分分析k p c a ( k e r n e lp r i n c i p a lc o m p o n e n ta n a y s i s ) 3 5 一s 8 解决了这一问题。k p c a利用核函数把p c a 扩展到高维非线性空l 刨。然而k p c a 的一个问题是“特征分解”的计算复杂度与训练样本数量有关，当训练样本变大时，计算时间变长。解决这个问题的方法是：稀疏核矩阵或者减少训练样本数量。本章分析了一般主成分分析方法在处理非线性问题上的不足，阐述了核主成分分析方法及其计算速度的缺陷，提出了基于聚类的核主成分分析方法。试验结果显示：基于聚类的核主成分分析方法具有好的特征提取性能，相比核主成分分析大大提高了特征提取的速度。1 3 2 聚类和改进距离的l l e 方法本论文的第四章提m 了l l e 方法的扩展：基于聚类和改进距离的l l e 方法。第章结沦l l e ( l o c a l l y n e a re m b e d d i n g ) 是解决降维的方法，针对l l e 计算速度和近邻点个数k 的选耿，本章研究了该方法的扩展，提出了基于聚类和改进距离的l l e 方法。基于聚类l l e 方法大大缩减了计算l l e 方法的时间；改进距离的l l e 方法在近邻点个数取值比较小时的情况下，可得到良好的效果，而原始的l l e方法要达到相同的效果，近邻点个数k 的取值通常要大很多。同时，改进距离的l l e 方法可以模糊近邻点个数选取。试验结果显示：基于聚类和改进距离相结合的i 上e 方法相比原来的l l e 方法大大提高了降维速度和扩大了参数k 的选取。1 3 3 小矩阵向量的l l e 维数缩减方法s m v l l e本论文的第五章针对降维中图像到向量的转换问题，在l l e 方法的基础上，提出了小矩阵向量的l l e 维数缩减方法s m v l l e ( s m a l lm a t r i xv e c t o rl o c a l l yl i n e a re m b e d d i n g ) 。图像检索的解决办法通常是把数字图像转化为向量，图像数据集变为向量集，根据向量的距离的远近确定图像属于哪一类。在数字图像转换为向量的过程中，没有考虑图像像素之间的位置关系，这样就会导致图像特征信息的损失。针对这种情况，本章提出了用小矩阵覆盖的方法，对图像的每一个像素都用小矩阵覆盖，然后把各个小矩阵看成数值组成向量( 实际上是矩阵) ，然后针对小矩阵向量进行降维。l l e ( l i n e a rl o c a l l ye m b e d d i n g ) 是著名的维数缩减方法，该方法可以解决把一幅数字图像直接转换为向量的问题，而对小矩阵向量组成的矩阵没有办法解决，对此，本章在基于图像直接转换为向量的l l e 的基础上提出了一种新的维数缩减方法，即小矩阵向量的l l e 维数缩减方法s m g l l e ( s m a l lm a t r i xv e c t o rl o c a l l yl i n e a re m b e d d i n g ) 。对手写数字图像和纹理图像的试验显示，基于小矩阵覆盖的s m v l l e 方法比直接转换为向量的l l e 方法效果好。1 4 本论文的组织结构本论文余下部分的安排为：第二章回顾降维的定义，介绍了聚类的方法。并讨论了一般距离函数定义及相关表示。第三章介绍了p c a 方法及其扩展k p c a 方法，以及两种方法存在的不足，提出了基于聚类的k p c a 方法。本章最后通过实验验证了算法的有效性。籀幽章首先介绍了l l e 方法及其不足，然后提出了基于聚类和改进距离的l l e 方法。通过实验验证算法的有效性。第五章提出了小矩阵向量的l l e 维数缩减方法s m v l l e 。通过现实数据集验证了小矩阵向量的l l e 维数缩减方法s m v l l e 的有效性。第六章全文总结，并在此基础上了提出了下一步的研究方向。第二章降维驶聚类办法第二章降维及聚类方法在本论文研究过程中，主要涉及到降维、聚类和距离的求解等内容和研究方法，所以先做以下概述，以便更好地理解全文。2 1 降维定义定义2 1 对d 维空间上的一个数据集x = x ，x2 ，工。) ，x ，r “数据集y = ( y l ，y2 ，y 。 ，y ，r ”( m d )称映射f ：x yx 卜y ，= f ( x ，)为从到y 的一个降维。2 2 降维方法一般将降维方法分为两类，一类是线性方法，另一类是非线性方法。定义2 2 对数据集x = x 。，x2 ，x 。 ，x r 。，通过映射ff ( x ) =得到低维空间中的数据集f ( x i )f ( x 2 )f ( x 。)f ( x ? ，* ? ，( x ；，工；，= y i ，y2 ，y 。) ，y ，r ”7 ( ；，i = 1 , 2 ，则将m 建立为新的第 + 1 类，即眈+ = ) 。否则将m 归入与y l ，以，以距离为最近的那一类。有了初始分类之后，考虑把聚类中的一个样本j ，从移入r ，以减少对误差平方和带柬的彤向。设从中移出y 后的集合是瓦，它相应的均值是呒，显然晚。+ 志( 训m l式中m 。和r 是l 的样木均值和样本数。r ，接受y 后的集台是亍= ，它相应的均值是既，瘌，一，+ 志( y 一式中m ，和h 。是r ，的样本均值和样本数。由于，的移动只影响r 和1 1 ，两类，而对其它的类是无任何影响的，因此只需计算两类的新的误差平方和工和z 。z = 以一士护1 1 2肝l l7 _ + 点j | y - m , i i y - m , 1 1 2，- ，+ 篇j |。假使嚣”枷c 者| | y - m * 1 1 2第二章降维故聚类办法则把样本从移入到l 就会使误差平方和减少。只有当y 离m ，的距离比离。的距离更近时满足上述不等式。所以，动态七均值算法为：( 1 ) 选择把 个样本分成c 个聚类的初始划分，计算每个聚类的均值朋l ，m ”，幔和t 。( 2 ) 选择一个备选样本y ，设y 现在在r 中。( 3 ) 若”= l ，则转( 2 ) ，否则继续。( 4 ) 计算p 。2矗 m ，1 1 2i n i 。i i y - m , i2j fj = 1( 5 ) 对于所有的，若反成，则把y 从f 中移到c 中去。( 6 ) 重新计算码和的值，并修改。( 7 ) 若连续迭代n 次以不改变，则停止，否则转到( 2 ) 。例如：假设有个分布在空间中的对象集合，如下图2 3 所示。给定七= 3 ，即要求将这些对象聚类为三个簇。根据k m e a n s 算法，任意选择三个对象作为三个初始的簇中心，簇中心在图中用“+ ”来标注。根据与簇中心的距离，每个对象被分配给最近的一个簇。这样的分布形成了如图2 3 中所描述的图形。这样的分组会改变聚类中心，也就是说，每个聚类的平均值会根据类中的对象重新计算。依据这些新f 匀聚类中心，对象被重新分配到各个类中。这样的重新分配形成了图2 - 4 中虚线所描绘的轮廓。以上的过程重复，产生图2 - 5 的情况( 请引用参考文献) 。最后，当没有的重新分配发生时，处理过程结束。聚类的结果被返回。辅二常脐辨成聚黄山法2 4 相似性测度图2 - 3图2 - 4图2 5为了使类分得合理，必须捕述样本之间的亲疏远近的程度。刻画样本点之间的相似性主要有以下两类函数：相似系数：两个样本点愈相似，则相似系数值愈接近1 ；样本点愈不相似第二章降维驶聚类办法则相似系数值愈接近o 。这样就可以使用相似系数值束刻画样本点性质的相似性。距离函数：设使用 个指标特征变量来描述样本，那么就可以把每个样本点看作”维空问中的一个点，进而使用某种距离来表示样本点之问的相似性，距离较近的样本点性质较相似，距离较远的样本点则差异较大。2 4 1 距离定义设数据集x 是空i 白j 月“的一个子集，x = x i ，x2 ，x ， cr “，设札，x ，。用d 女，来表示样本砟，x ，之间的距离。距离甲是一个映射，甲：x 一r + 。它满足如下四条性质：( 1 ) d “0( 非负性)( 2 ) d ，= 0( 3 ) d “= d t k( 4 ) d “s d “+ d ，7当且仅当x 。= -( 非退化性)( 对称性)( 三角不等式)根据不同的应用目的，可以提出许多种满足以上条件的距离函数，列举若干种如下：2 4 2m i n k o w s k y 距离m i n k o w s k y 距离即明氏距离id d ( x k ，x 1 ) = | k i这是若二| 二种距离的通式表示。2 4 3m a n h a t t a n 距离d ( h ，x i )这是m i n k o w s k y 距离当 = 1 时的特例。2 4 4c i t yb l o c k 距离x r | 2( 1 o ：)c ，( z 。，x ) = ：一x ；这是剥m a n h a t t a n ij l t 修作，加上了权重国，( o 甜， 五： 丑，0 ，相应于五，的特征向量为c ，令c =相对于y 的方差为同样有c 1 1c 2 ic i2c 2 2c a lcc 1 2= c 。c ：c 。，】v a r ( c 1 x ) = c l 剃c i = c l r c i ；v a r ( c ，x ) = 丑即对于y ，有最大的方差，y ：有次大的方差，等等，并且有协方差c o v ( c l x ，c ，x ) = c i r c ，( 3 4 )由( 3 3 ) 式得r = 2 , c , c ：，所以( 3 4 ) 式变为：c o v ( c i x 。，c ，) = c i r c j = c ( 丑c ，c ) c ，= ( c ；c ，) ( c ：c ，)变量x ix ：，x ，经过正交变换后得到新的向量y = c l xy 2 = c ；xy “= c a xy l , y ：，y 。彼此不相关，并且y ，的方差为 ，故称儿，y ：，y 。分别为第一，第二，第d 个主分量。3 2 2p c a 方法计算过程设样本矩阵为x第二巅肚_ r 浆类的核主成分分h ix 1 1x l 二x 2 ix 2 2x ic ，x 2 【，x4 “一为样本数，d 为每个样本维数。为了使样本集在降维中所引起的平方误差最小，必须进行两方面的：亡作：一是进行坐标变换，即用雅可比方法求解丁f 交变换矩阵二足选取m ( m 丑： 九0 ，对应于特征值丑的相应特征向量为并且满足c “1 = ( c ”，畔1 ，c j 1 )( _ 1 , 2 ，d )，= c m n ：i= j 渤4 选择m ( m c ，) 个主分量。当| j 1 ：面”7 个主分量z ，z 2 ，z 。( m r l 2 ( z )，( 3 1 6 )( t k f ) ( x ) ：= i 后( x ，工) ( x ) d u ( x )是正的，也就是对所有，厶( z 2 ) ，都有f ，女( 础) 厂( x ) ，( x 胁( x ) 如( z ) o ，( 3 1 7 )则对几乎所有( 除了一个零测度集之外，下文类似) ( x ，x ) z2 ，都有k ( x , x t ) = ：乃 ( x ) 吩( x )( 3 1 8 )其中，表示二次可积函数空间，v j l 2 ( z ) 表示瓦的与特征值 ，( o ) 相对应的归一化f 交特征函数，n t ：en 或m = o o 。山( 3 1 8 ) 式，可以定义m e r c e r 核映射如下：定义3 7 ( m e r c e r 核映射) 假定k 是一个满足m e r c e r 定理的核( 简称为m e r c e r 核) ，定义一个从z 到r 。的映射 z _ 鼍、( 31 9 )x 寸( 删川坼”为m e r c e r 核映射。其中，f ：为二次可和数列空间，n 。妒，的含义同定理3 1 。并且由m e r c e r 定理，有下面的命题成立：命题3 1 9 5 假定k 是一个满足m e r c e r 定理的核，中是由( 3 ，1 9 ) 式所定义的m e r c e r 核映射，则对几乎所有( z ，x ) z 2 ，有第二卷扎r 聚类的槌主成分分柯( 3 2 0 )命题3 1 晚明用m e r c e r 核映身4 可以构建与给定核相关联的f l i i b e r t 空间，并且在这个空间中的内积可以用给定核来表示。m e r c e r 核和f 定核都可以被表示为h i 】b e r t 空l j d o 的内积，而下面的命题则证明了在一定情形下，m e r c e r 核和f 定核是等价的。命题3 2 1 9 5 i l z = h 6 】表示一个紧缩区叫，k ：f “，b x a ，6 一c 是连续函数，则是一个正定核，当且仅当对每一个连续函数厂：z 斗c ，都有ee k ( x ，x ) ，( x ) f ( x ) d x d x o ( 3 2 1 )3 3 3 常用的核函数及其构造前面两节给出了再生核与m e r c e r 核所需满足的条件，本节介绍几种常用的核函数，以及如何从已有的核函数构造新的核函数。常刚的核函数如下 9 5 ：1 多琐式核函数k ( x ，：) = ( ( ) 十c ) “( d e n , c 0 )( 3 2 2 )2 高斯( g a u s s i a n ) 核函数m 一- ( _ 学卜 z 。，3 s i g m o i d 核函数k ( x ，z ) = t a ，1 h ( 口( x ，：) + ) ( 口 o ， 0 )( 3 2 4 )4 一般径向基( r b f ) 核函数( 郴) = e x p ( 一p d ( x ，：) ) ( 胪0 )( 3 2 5 )其中，d ( x ，z ) 可以是任意一利t 距离度量，例如可以取c ( x ，z ) = ，i # 一z ? rf 0 8 5 ) ，取前m ( m n ) 个特征值和对应的标准化后特征向量“。，口：，d 。，其中口，= q 1 ，哆2 ，q ”)( r = l ，2 ，) ，此时对f 空_ f u j 中样木o ( x ，) ( j = 1 ，2 ，n ) 在u ，七投影g ，( x ，) = ( 庐( _ ) q ) = 彰( ( x ，) ( ) ) ，( r = 1 2 ， ) ( 3 3 2 )称毋( x ，) 为对应庐的第r 个非线性主元分量。将所有的投影值形成一个矢量g ( x ，) = ( 蜀( x 9 2 ( x ，) ，g ，( r 作为样本的特征值。根据m e r c e r 9 5 ，9 6 定理用核函数k ( 一，) = ( _ ) 矿( x ) ) 代替f 空i h j 中的内积运算，( 3 3 2 ) 式可写为鼻( ) = ( ( x ，) q ) = 彰目，_ )( 3 3 3 )从上面的计算可以看到，p c a 的协方差矩阵与样本点的维数相关，而核矩阵与样本点的个数相关，p e a 不能解决非线性问题，k p c a 虽能解决，但由于样本点的个数比较火，带来核矩阵的维数比较大，造成计算复杂度增加。为了解决核矩阵的计算复杂性，已经有的方法有疏散的贪婪矩阵近似( s g a ) 9 8 和t o m 方法 9 9 ，根据概率空间提出了疏散的核p c a 方法 1 0 0 等，在木章里，我们使用聚类的方法缩减样本点个数来达到降低核矩阵阶数的目的。第三章策1 i 聚类的核主成分分析3 4 聚类已经有一些研究 9 8 一1 0 0 直接对核矩阵计算进行优化。本章采用减少样本点的个数来降低核矩阵的阶数进行优化计算。为了尽可能多地保持原有的样本点分类信息，使变化后的信息尽量含有原样本点所拥有