《典型聚类算法及其应用研究》由会员分享，可在线阅读，更多相关《典型聚类算法及其应用研究（76页珍藏版）》请在金锄头文库上搜索。
1、摘要摘要聚类是知识工程和模式识别中一个重要的研究领域，在对大量数据进行分析和处理时有其独特的地位。 聚类领域方面的研究经过上世纪8 0 到9 0 年代的突飞猛进的发展之后， 产生了种类和用途繁多的聚类算法， 然而，由于聚类本身属于无指导性学习，其处理问题的方式， 以及获得解的可靠性大多是经验性的， 而且通常算法过度依赖于具体的应用背景。 论文针对聚类算法研究现状， 围绕聚类算法及其相关问题， 总结和评价现 有聚类算法，以及影响聚类分析的各个环节， 探讨改进制约聚类性能的关键因素， 并论文对普适性较好的聚类算法进行改进。由于现在存在聚类算法众多， 论文首先对各种聚类算法分门别类进行分析讨论， 每
2、 类算法以其中较为典型的算法为例， 在分析总结评价算法优缺点的同时， 还剖析聚类算法的具有各种特性的原因; 虽然， 聚类在许多没有先验知识的应用环境下是不可或缺的，但在没有先验知识的环境下解决问题， 从直觉上比有先验知识下解决问题更困难。 对此，论文从理论上分析了聚类问题的规模和难度。 并且分析得出， 基于划分和基于密度的算 法具有良 好的特性，对这两类典型算法的研究和改进具有重要意义。多维检索结构是制约众多聚类算法效率的关键环节， 论文分析讨论了两类现有的多 维索引结构， 在此基础上提出了一种简单有效的多维索引结构， 并将其用于一个视频关键帧的匹配问题上，同时讨论了它在提高聚类效率上可行的应
3、用。K平均聚类算法是一类重要的聚类算法，它是目 前应用最广的基于划分的聚类算法，论文在研究和总结最近聚类算法的研究进展上，提出了一种改进的 K平均聚类算法，并将它应用到文本聚类上，论文还分析对比了该方法的有效性。另外，Me a n S h i ft算法是一种基于密度的聚类算法， 最近的研究表明它可以成功的应用到诸如图像分割的 问题上，论文将K平均聚类算法和Me a n S h i ft聚类算法相结合，提出一种新的可变带 宽策略对已 有M e a n S h if t 算法进行有效改进， 并将它应用到图像分割上: 虽然， K平均聚类算法得到广泛应用，但其迭代过程的收敛性很少有研究者提及，论文将其
4、归结为Me a n S h i ft迭代过程的一个特例从而分析了它的收敛性。关键字: 聚类， K平均，多维检索结构， 优化， R B - K平均， M e a n S h i f t ，收敛性摘要Ab s t r a c tC l u s t e r i n g i s a n u n s u p e r v i s e d c l a s s i f i c a t i o n o f p a t t e r n s ( o b s e r v a t i o n s , d a t a i t e ms , o r f e a t u r ev e c t o r s ) i n t o
5、g r o u p s ( c l u s t e r s ) . U p t o d a t e , t h e r e a r e m a n y i m p o r t a n t a p p l i c a t i o n s o f c l u s t e r i n g a l g o r i t h m s , s u c h a s i m a g e s e g m e n ta t i o n , o b j e c t r e c o g n i t i o n , a n d i n f o r m a t i o n r e t r i e v a l . I t s
6、a p p l i c a b l e d o m a i n i s s t i l l e x p a n d i n g . T h e c l u s t e r i n g p r o b l e m h a s b e e n a d d r e s s e d i n m a n yc o n t e x t s a n d b y r e s e a r c h e r s i n m a n y d i s c i p l i n e s . H o w e v e r , c l u s t e r i n g i s a d if f i c u l t p r o b
7、l e mc o m b i n a t o r i a l l y , a n d d i f f e r e n c e s i n a s s u m p t i o n s a n d c o n t e x t s i n d i f f e r e n t c o m m u n i t i e s h a v em a d e th e t r a n s f e r o f u s e f u l g e n e r i c c o n c e p t s a n d me t h o d o l o g i e s s l o w t o o c c u r . T h i
8、s t h e i s s e t si t s f o c u s o n c l u s t e r i n g p r o b l e m a n d e x t e n d s t o k e y f a c t o r s r e l a t e d t o i t . P r o p e rt i e s o f t y p i c a lc l u s t e r i n g a l g o r it h m s h a v e b e e n d i s c u s s e d i n d e t a i l s .T h e n n e w m e t r i c s a r
9、 e p r o p o s e d b a s e d o nt h e s e a n a l y s i s t o e n h a n c e t h e i r e f f e c t i v e n e s s a n d e f f i c i e n c y .F i r s t l y , t h i s t h e s i s g i v e s a s y s t e m a t i c a l l y o v e r v i e w o n t h i s a r e a . S i n c e t h e r e a r e m a n yr e l a t e d
10、t o p i c s w i t h t h i s f i e l d , i t f i r s t l y d i s c u s s e s th e s e r e l a t e d t o p i c s u n d e r t h e c l u s t e r i n gc o n t e x t . A f t e r t h a t , v a r i o u s o f c u r r e n t c l u s t e r i n g m e t h o d s a r e d i v i d e d in t o 4 k i n d s , f o r e a c
11、 h o f t h e m , a d e t a i l e d a n a l y s i s o f i t s s t r o n g p o i n t s a s w e l l a s w h e r e i t f a i l s i s p r e s e n t e d . B y t h a t , i tl a y s o u t a c l e a r p i c t u r e o f t h i s f i e l d .S c a l a b i l i t y t o d a t a s i z e a n d f e a t u r e d i m e n
12、 s i o n s i s a n e n q u i r e m e n t h a r d t o m e e t w i t h , i f n o tt h e m o s t , s i n c e t h e c u r s e o f d i m e n s i o n s t i l l o c c u r d e s p i t e m a n y m u l t i - d i m e n s i o n i n d e x i n gm e t h o d s , s u c h a s R - T r e e , R * - T r e e , X - T r e e
13、 h a v e b e e n p r o p o s e d . M u t i - d i m e n s i o n a l I n d e x i n gS t r u c t u r e p l a y s a c r i t i c a l r o l e i n c l u s t e r i n g f i e l d , a n d h a s b e e n d i s c u s s e d i n m a n y c o n t e x t s . F o r th a t r e a s o n , t h i s t h e s i s a l s o p r e
14、 s e n t s a n o v e r v i e w o n t h a t . T h e n , a n e w M u l t i - d i m e n s i o nI n d e x i n g S t r u c t u r e , n a m e l y S H S ( S i m p l e H a s h i n g S t r u c t u r e ) i s p r o p o s e d . Wh e n a p p l y i n g i t ina K e y f r a me m a t c h i n g p r o b l e m , c o m
15、p a r i n g t h e m a t c h i n g w i t h o u t S H S , a l o t o f t i m e i s s a v e du p . A t t h e e n d o f t h a t c h a r p t e r , t h e f e a s i b i l i t y t h a t a p p l i e s i t t o c l u s t e r i n g a l g o r i t h m s i sa n a l y s e d .P a r t i t i o n b a s e d a l g o r i t
16、 h m s a re K - m e a n s a n d i t s v a r i a n t s , a r e t h e m o s t w i d e l y u s e dm e t h o d s f o r t h e i r s i m p l i c i t y a n d e f f e c t i v e n e s s . B a s e d o n t h e s u r v e y o f t h e s t a t e o f a rt i nC h a r p t e r 4 , w e p r e s e n t a n i m p r o v e d K - m e a n s v a r i a n t . I t s e f f e c t i v e n e s s i s v e r i f i e d b ye x p e r i me n t s o n m a n y d a t a s e t s . C o m p a r i n g w i t h o t h e r v a r i a n t s o f K - m e
