（计算机应用技术专业论文）基于投影的聚类算法研究及应用.pdf

摘曼 摘要 随着信息技术飞速发展，在信息处理过程中，人们发觋信息的数据量越来越大庞 大。如何从大量的信息数据中获取人们所需要的知识? 如：数据的分布，数据发展趋势 等等，因而聚类作为一门数据分析工具也就应运而生，所诮聚类就是将物理或抽象对象 的集合组成由类似的对象构成的多个类或簇的过程】。目的是使得属于同一类别的个体 之间的差别尽可能的小而不同类别的个体之问的差别尽可能的大。 目前聚类分析中大部分聚类算法都是针对低维数据的，而现实中涉及到信息处理 数据大部分都是高维的，这就向传统的聚类算法提出了挑战。文献f 2 】中提到，用传统的 聚类算法如k m e a n s 和k - m e d o i d 方法直接处理这些高维数据效果非常不理想，于是人 们采用“特妊提取”方法来降低数据集的维度，例如p c a 算法，但这种降维方法很容 易导致数据的信息丢失。最近的研究表明，在特定条件f 高维数据的聚类都隐含在低维 的子空间内，如何找出这些有效的低维子窄问? a g r a w a l 等人【3j 提出了投影聚类方法。 投影聚类是把数据集通过映射变换投影到低维子空问内，然后借助各种方法划分 出该子空间内的聚类，能够有效的降低数据集的维度，同时减少数据处理的复杂度。现 有的投影聚类算法有：c l i q u e l 3 1 ，p r o c l u s 4 1 ，o r c l u s l 5 和e p c h l 2 等。c l i q u e 算法 是首次涉及投影聚类与子空间问题，但是该算法要求子空问的延伸方向必须要与坐标轴 平行，并且还需要用同一个极限值来划分不同投影维度的子空间，这显然是不合理的； 而p r o c l u s 和o r c l u s 算法则主要通过寻找中心点来得到投影聚类和它们相关的子 空间。p r o c l u s 要求发现投影的子空间延伸方向必须与平行，但o r c l u s 算法没此限 制，可以是任意延伸方向的子空间。e p c h 算法i 】也是用来解决同样的问题，但它与前 几个算法相比不仅复杂性降低了，而且有效性和精确性有很大的改进。通过分析e p c h 算法，结合投影聚类的思想，我们采用不同的方法来划分子空问，提出了两个改进算法， 分别是： 1 ) 基于p a r z e n 窗的投影聚类方法：该方法用投影聚类将高维数据投影到低维子空间， 再用概率密度估计函数p a r z e n 模拟子空j r j 样本分布，通过合并密度区域得到聚类结 果，实验证明其具有比e p c h 更为精确的效果。 2 ) 基于m e a n s h i f t 的投影聚类算法：该算法提出了一种用核函数将高维数据空间转化 为低维空间，然后将低维子空削中数据划分到中心点代表的区域中，得到合并的聚 类结果，实验证明其有效性。 本文主要是介绍聚类分析的基奉概念、各种聚类算法及本人提出的两个改进算法。 关键字：聚类予空闻划分直方图p a r z e n 窝m e a n s h i f t 投影聚类 江南人学硕卜学位论义 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , t h ed a t aq u a n t i t yt h a tp e o p l e u s ei nt h ei n f o r m a t i o np r o c e s s i n gc a nb em o r ea n dm o r e h o wt og e tt h en e e d f u li n f o r m a t i o n f r o mt h em a s s i v ed a t a ，s u c ha s ：t h ed a t ad i s t r i b u t i o n ，t h et r e n do fd a t ad e v e l o p m e n t ? t h e c l u s t e ri sj u s tp r o p o s e da st h ed a t aa n a l y s i st 0 0 1 t h ed u s t e ri st h ep r o c e s st h a tu s et h e p h y s i c a le i t h e rt h ea b s t r a c to b j e c ts e t t of o r mc l a s s e so rc l u s t e r sw h i c ha r ec o m p o s e do ft h e s i m i l a ro b j e c t ，a n dt h eg o a li se n a b l e st h ed i f f e r e n c eo fi n d i v i d u a li nt h es a m ec a t e g o r ya s s m a l la sp o s s i b l e ，t h e r ew i t ht h ed i f f e r e n c eo fi n d i v i d u a li nt h ed i f f e r e n tc a t e g o r ya sb i ga s p o s s i b l e a tp r e s e n t ，m o s to fc l a s s i cc l u s t e r sa l g o r i t h m sa r ea i ma tt h el o wd i m e n s i o nd a t a ，b u tt h e d a t ai nt h er e a l i t yi sm o s t l yi nt h eh i g hd i m e n s i o n t h e r e f o r ei ti sac h a l l e n g et ot h ec l a s s i c c l u s t e ra l g o r i t h m s ( i nl i t e r a t u r eb i t p o i n t so u tt h a tt h de f f e c ti sn o ti d e a lv i at h ec l a s s i c c l u s t e ra l g o r i t h ml i k ek - m e a n sa n dt h ek m e d o i d ，a n di th a sp r o p o s e dn e wm e t h o dt h a tu s e t h ec h a r a c t e r i s t i ce x t r a c t i n gt or e d u c et h ed a t ad i m e n s i o n ，s u c ha sp c a a l g o r i t h m ，y e tt h i s m e t h o dc a nb ee a s yt ol o s et h ei n f o r m a t i o no fd a t a t h er e c e n tr e s e a r c hi n d i c a t e st h a tt h ed a t a c l u s t e ro ft h eh i g h e rd i m e n s i o nc o n c e a l si nt h es u b s p a c eo ft h el o w e rd i m e n s i o nd a t a h o wt o f i n dt h ee f f e c t i v es u b s p a c e ? a g r a w a l1 3 1h a sp r o p o s e dt h ep r o j e c t i o nc l u s t e rm e t h o d t h e p r o j e c t i o nc l u s t e rp r o j e c t st h ed a t as e ti n t ot h es u b s p a c eo fl o wd i m e n s i o nt h r 0 1 i g ht h e m a p p i n gt r a n s f o r m a t i o n ，a n dt h e nd i v i d e st h ec l u s t e ri n t h i ss u b s p a c ew i t ht h ea i do fe a c h m e t h o d t h i sp r o j e c t i o nm e t h o dc a nn o to n l yr e d u c et h ed i m e n s i o no ft h ed a t as e te f f e c t i v e l y , d i m e n s i o n ，b u ta l s or e d u c et h ec o m p l e x i t yo ft h ed a t ap r o c e s s i n g t h ee x i s t i n gp r o j e c t i o n c l u s t e ra l g o r i t h mi n c l u d e ：c l i q u e 【3 】 p r o c l u s1 4 1 ，o r c l u s1 5 1a n de p c h 2 1e t c t l l e c l i q u ea l g o r i t h mi st h ef i r s ta l g o r i t h mt h a ti n v o l v e st h ep r o j e c t i o nc l u s t e ra n dt h es u b s p a c e q u e s t i o n ，b u ti tr e q u e s t st h ed i r e c t i o no fs u b s p a c ee x t e n d i n gm u s tb ep a r a l l e lw i t ht h ea x i sa n d i ta l s on e e d st ou s eal i m i t e dv a l u et od i v i d et h es u b s p a c eo fd i f f e r e n td i m e n s i o n ，s oi t , i s i n c o n s e q u e n c e ；t h ep r o c l u sa l g o r i t h ma n dt h eo r c l u sa l g o r i t h mu s em a i n l yt h e c e n t r a l p o i n t t oo b t a i nt h ep r o j e c t i o nc l u s t e ra n dt h e i ri n t e r r e l a t e d s u b s p a c e t h e p r o c l u s a l g o r i t h mr e q u e s t st h ed i r e c t i o no fp r o j e c t i o ns u b s p a c ee x t e n d i n gm u s tb ep a r a l l e lw i t ha x i s ， h o w e v e rt h eo r c l u sa l g o r i t h mh a sn o tt h i sl i m i t ，i t ss u b s p a c ed i r e c t i o nc a nb ed i s c r e t i o n a l t h ee p c ha l g o r i t h m1 2 1a l s oi su s e dt os o l v et h es a m ep r o b l e m c o m p a r i n gw i t ht h ef o r m e r a l g o r i t h m s ，n o to n l yi t sc o m p l e x i t yr e d u c e s ，b u ta l s ot h ev a l i d i t ya n dt h ea c c u r a c yh a v e p r o m i n e n ti m p r o v e m e n t t h r o u g ha n a l y z i n gt h ee p c ha l g o r i t h m ，w ea d o p td i f f e r e n tm e t h o d t od i v i d et h es u b s p a c ea n dp r o p o s e dt w ok i n d so fs u b s p a c ed i v i s i o na l g o r i t h m ： 1 ) t h em e t h o do fp r o j e c t i v ec l u s t e rb a s e do np a r z e nw i n d o wp r o j e c td a t aw i t hh i g h d i m e n s i o ni n t os u b s p a c ew i t ht o wd i m e n s i o n i tu s e sp r o b a b i l i t yd e n s i t yf u n c t i o nt os i m u l a t e s u b s p a t i a ls a m p l ed i s t r i b u t i o na n dg e t t h ec l u s t e rr e s u l t s b ym e r g i n gd e n s i t ya r e a s t h e e x p e r i m e n td e m o n s t r a t e st h a ti th a sm o r ep r e c i s ee f f e c tt h a ne p c h 2 ) t h ea l g o r i t h mo fp r o j e c t i v ec l u s t e rb a s e do nm e a n - s h i f tt r a n s f o r m sh i g hd i m e n s i o nd a t a s p a c et ol o wd i m e n s i o nd a t as p a c eb yn u c l e a rf u n c t i o n t h e nt h ed a t ai nt h es u b s p a c eo ft h e l o w e rd i m e n s i o nw o u l db ed i v i d e di n t or e g i o n sw i t hc e n t e rp o i n ta n dg e tt h em e r g i n gr e s u l t i i a b s t r a c f t h e e x p e r i m e n tp r o v e di t sv a l i d i t y t h i st h e s i sm a i n l yi n t r o d u c e st h eb a s i cc o n c e p to fc l u s t e r , e a c hk i n do fc l u s t e ra l g o r i t h m a n dt w oi m p r o v e m e n ta l g o r i t h m sip r o p o s e d k e y w o r d ：s u b s p a c ep a r t i t i o n ，h i s t o g r a m s ，p a r z e nw i n d o w , m e a n - s h i f t ，p r o j e c t i v ec l u s t e r i n g ， c l u s t e r 1 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 、 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：董查厘日期：2 吣+ 年 月侈日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：蓥耋垡i导师签名： 日期：2 胡年6 月l 雪日 第一章绪论 第一章绪论 近年来，随着通信技术和网络技术的飞速发展，人们面临着大量的信息数据，而 这些数据大部分都没有经过任何处理，如何从这些数据中得到人们需要的知识? 这对我 们来说是个很大的挑战，因而需要一个强有力的工具来对它进行分析，自然就出现了数 据分析技术。数据分析技术有两种：第一种是探讨性的数据分析技术；第二种是验证性 的数据分析技术。其中聚类分析( c l u s t e ra n a l y s i s ) 是属于探讨性的数据分析技术，它是 根据研究对象的特征对研究对象进行聚类的多元分析技术的总称，它把性质相近的个体 归为一类，使得同一类型中的个体具有高度的同质性，不同类型之间的个体具有高度的 异质性。 1 1 研究背景和意义 信息时代，人们广泛使用大量的数据库系统导致了海量信息数据出现，人们希望在 这些海量信息数据集中获取其隐含的和有价值的知识，这给“聚类分析技术”的发展带 来机遇。 聚类作为一门工具，已被运用到各种数据分析领域【6 , 7 , 8 , 9 , 1 0 , 1 1 , 1 2 】，比如：数据挖掘， 模式识别，图像分割等等。经过十几年聚类分析技术的研究，人们提出了很多经典的聚 类算法如k - m e a n s 和c 均值等。然而人们发现用这些经典算法来处理高维数据时，带 来意料不到的结果是高维聚类的结果非常差，很显然，我们知道高维数据由于本身的性 质如稀疏性，用传统的聚类方法直接去处理，结果差是很明白的，这是因为传统的聚类 算法是建立在低维数据的基础上的。现实中人们处理的数据对象不仅从总体数量上的增 加，并且单个数据对象的维度也是不断膨胀的，到目前为止，还没有提出有效的针对高 维数据的聚类算法，因此在这个领域的任何技术和方法的创新，必将带来理论和现实意 义。 目前，高维数据的聚类通常采用两种方法：一是，通过“降维”方式来降低数据的 维度，把高维数据“变成”低维数据，比如：主成分分析法( p c a ) ，卡诺图法，多因子 降维法( m d r ) 等：二是，通过“投影? 方式把高维数据投影到低维子空间，在低维子空 间里聚类来获得整个数据集的聚类结果，比如：p r o c l u s ，o r c l u s 和e p c h 等。 1 2 国内外研究现状 1 2 1 国外的研究动向 信息技术和互连网技术最早是出现在国外，人们为了要从未知的信息中去发现有价 值的知识，必然会驱使人们去研究，给数据分析技术出现带来契机。随着信息技术和网 络发展到现在，人们所面临的是“数据丰富，知识贫乏”的现状，为了寻求解决方法， 各个国家都投入更多的人力和物力来发展这个技术，作为数据分析技术的一个分支，聚 类分析有个更加广阔的应用前景按照数据分析的对象来说，丌始人们研究聚类的各种 1 =一竖查盔兰塑生兰!堡鉴一一 ( a ) 在x - y 平面上的交集r ( b ) 在x - z 平面上的交集q 图1 1 ：投影聚类在子空间x - y 与x z 算法是针对低维数据的。并且数据量也不是很大，而现在人们所接触的数据，不仅是量 上发生了很大的变化，并且所涉及的数据维度也是越来越高韵，从最初的几维，十凡维 到现在几十维，甚至上百维，给聚类研究带来了很大的困难，这就是我们通常说的“维 度灾难”，为了解决这个问题，人们提出了“特征提取”和“降维”的方法，把高维数 据转化到低维空闽里研究，这样翦期傲的理论又可以适用这种新的变化下，但在“降维” 和“特征提取”的过程中，又出现了新的问题，看图1 1 ，一个3 一维数据集通过“降维” 和“特征提取”后在两个不同的坐标系中，会出现两个不同聚类的月和q ，研究发现会 导致信息的丢失，即每个数据维度至少涉及到一个分类，为实现有效的处理，a g r a w a l 等人圆中提出了投影聚类方法。目前投影聚类的算法有：c l i q u e ，p r o c l u s ，和 o r c l u s 。这几个算法对投影到子空间的聚类形状都有要求，有待深入的研究。 2 第一章绪沦 1 2 2 国内的研究动向 与国外相比，囡内从事聚类分析领域起步比较晚，现在国内基本上没有专门从事这 个方面设计和实现的公司，大部分研究都是集中在高校和科研单位，其研究方向都是集 中在聚类算法的实现，并在基础上进行创新，基本上大体研究思路与国外相同。其中特 别要提到的是中国香港地区，它在投影聚类算法这个领域做的非常出色，提出e p c h 算 法不仅理论简单明了，并且对投影后形成的子空间罩聚类没有形状和延伸方向的限制， 实现也简单。 1 3 本文主要内容 本文有六个部分组成，从第二章起，该部分主要介绍聚类分析技术的基本概念和主 要的算法，对它们进行了一个简单的了解和认识，尤其要说明是高维数据的聚类算法， 这是本文研究的重点，对其进行详细的说明，让读者明白投影算法的思想；第三章阐述 的是e p c h 算法，这个算法是后文提出的两个改进算法的切入点，通过对这个算法的分 析和研究，发现能够改进该算法的思路，为后文提出的两个改进算法做铺热；第四章介 绍第一个改进算法p c p w ，该算法是引进p a r z e n 窗函数作为投影，把高维数据投影到低 维子空间晕。然后借助e p c h 算法中的定义极限值方式划分低维子空间晕的密度区域， 通过合并合并密度区域代号得到整个数据集的聚类结果；第五章叙述的是第二个改进算 法p c m f ，这个算法利用核函数把高维数据空间转化为低维予空间晕，在低维子空问里， 采用m e a n s h i f t 方法寻找子空间里的密度区域中心点，然后借助“距离”的定义来获得 密度区域：第六章是结论部分，主要是对所做的研究工作给出总结。 江南人学颁 ：学位论文 第二章聚类分析 俗话说：“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问 题。所谓类，通俗地说，就是指相似元素的集合。聚类分析又称为群分析，它是研究( 样 品或指标) 分类问题的一种统计分析方法。聚类分析起源于分类学，在早期的分类学中， 人们主要依靠经验和专业知识来实现分类，很少利用数学工具进行定量的分类。随着人 类科学技术的发震，对分类的要求越来越高，以至于有时仅凭经验和专业知识难以确切 地进行分类，于是人们逐渐地把数学工具引用到了分类学中，形成了数值分类学，之后 又将多元分析的技术引入到数值分类学形成了聚类分析。 2 1 聚类分析的基本撅念 2 1 1 聚类的定义 聚类作为数据分析技术中的一个重要研究方法，越来越受到入们的关注。所谓聚 类 3 1 1 ，在某个数据空间d 中，数据集x 由许多样本点组成的，样本点 x ，= 柑，z 州) e d ，其中x 州表示样本点在某个维度空间上的性质特征，它可以是数 值型的，也可以是枚举型的。假设数据集的样本总数是，那么数据集z 就是个矗的 矩阵，通过定义准则函数把数据集x 划分成c 个类别c ，( i - 1 ，c ) ，也有部分数据样本 点没有划分到c ；中，我们把记为噪声c 。，则所有的类别和噪声的并集就是整个数据集x ， 并且类别之间不存在交集既： f x c ，u - - u c ，u c ， 1c 。n c ，。妒，( f ，) 这些类别就是聚类的结果。 2 1 2 聚类分析算法的要求 聚类分析是一个具有挑战性的研究领域，它所研究的对象大到宇宙星际，小到分子 基因，几乎无所不包，那么从事聚类分析的研究得至g 越来越多的青睐也是必然的。由于 研究对象隐含着特殊的数据结构和其本身的性质，所以对聚类的算法也有其特殊的要 求： 1 ) 伸缩性： 目酶有许多聚类算法对小规模数据集的处理效果还是令人满意的，但是现实中 一个大型数据库包含的数据量是几f 万，甚至是上百万的，虽然可以采用抽取样本 的形式来代替整个数据集，但是这样对聚类的结果估计带来影响甚至是错误的结果， 因此需要高伸缩性的聚类算法。 2 ) 混合数据： 许多聚类算法都是针对数值型的研究对象，然而现实中人们进行聚类的对象有 4 第二币聚类分析 ? 的是枚举型，二值型，序数型，有的对象甚至是这些类型构成的混合类型，人们研 究的聚类算法需要有处理各种数据对象的能力。 3 ) 任意形状的聚类： 很多聚类算法都是采用相似性度量方法来确定聚类的，而这类算法发现的聚类 通常是球状的，大小和密度都很相近，像前面我们提到的c l i q u e ，p r o c l u s ，和 o r c l u s 算法要求聚类的形状必须是平行于坐标轴的，否则聚类的结果就不是很理 想。 4 ) 参数 许多聚类算法要求在聚类分析前输入参数，比如类别数，置信度等，有的还需 要先验知识或模型来训练，而聚类的结果对这些参数非常敏感，然而有些时候这些 参数是无法确定的，比如高维数据的聚类，通常不知道分类的数目，这不仅给分类 带来的难题，而且聚类的结果也不好控制。 5 ) 噪声数据： 在聚类算法处理的数据对象时，其中某些数据对象中包含一些异常数据或错误 数据，聚类算法对某些数据不敏感，在处理过程中把噪声数据一起划到分类中，这 样导致聚类的正确率下降，甚至导致错误的聚类结果。 6 ) 输入顺序的不敏感： 有些聚类算法对数据对象的顺序很不敏感，比如：若把同一个数据集按照两种 不同顺序给放到聚类的算法中去，你就会发现划分出的类别中的数据对象会发生改 变，设计出这样的聚类算法显然不是我们需要的。 7 ) 高维数据： 当今信息时代，数据量都是以海量存储的，就是一个简单的数据库系统所包 含的数据维数都是几十维，有的甚至是上百维的，用我们以前研究的聚类方法去 处理的话，效果就不一定很好，这一面是数据集的本身稀疏性的性质造成的，另 外一方面是聚类设计的算法问题，就是因为这个存在很大的挑战，所以值得去研 究的课题。 8 ) 约束条件 聚类在处理现实问题时，通常要考虑到问题的实际约束条件，我们希望设计的 聚类算法即能满足这些约束条件，又能得到很好的聚类结果。 9 ) 解释性和可用性 聚类的结果是面向用户的，最终要被用户所理解，因此要有很好的解释性和可 用性，这要求聚类算法必须具有一定的语义环境和语义的相关性。 ! 1 3 聚类的数据类型 聚类算法处理的数掘对象可分为两大类型：数据矩阵和相异度矩阵。 根据上文所述的聚类定义：在给定数据集空间中，数据集石是有个样本点组成的， ! 三堕苎堂堡! ：兰堡丝兰 并且每个样本点有d 个维度构成的，即：z ，1 “j ，- ，x i 。) ，+ ，表示第i 个样本 点在j 维上的性质或特征，则这j v 个对象组成的观察值可以看成是n d 的矩阵： x i lx 1 2 x 2 tx 2 2 x lx n 2 上面的矩阵就被称为数据矩阵，它是变量数据结构的表达式。 聚类常用的另外一种数据结构就是相异度矩阵。它存储的是个样本两两之间的相 似关系，表示为： o d ( 2 ，1 ) 0 o ( 3 ，1 ) d ( 3 ，2 ) 0 d ( n ，1 ) d ( n ，2 ) d ( n ，3 ) 0 其中d q ，) 表示两个样本之间相异程度，若样本i 和样本，之间越来越相近，j j j a d ( i ，) 的值就越接近o ：如果两个样本i 和j 之间差别越来越大，那么o ( i ，j ) 就会不断的趋近1 。 可以看出用相似度来度量样本之闽的矩阵是个实对称矩阵，这是因为d 往，) 的值只能取 【0 ，1 1 ，相异度矩阵是对象对象的一种数据表达式。 从上面的分析知道：第一种数据结构类型很容易构造。直接把所有样本点组合成 即可；第二种数摄结构类型就比较麻烦，需要借用其他的方法来求两个样本之间的相异 度。在聚类分析中，可以借助聚类统计量来定量的刻画两个样本之问的相似度。通常采 用是距离的方法和相似系数来衡量样本相异度，借用上文定义中d 维空间中的个样本， 假设现有两个样本工，o u ，工啦，玉，d ) 和z ，o ，z 坩，工，。) 则度量这两个样本相异度 的方法有： 1 距离方法： 1 ) 明氏( m i n k o w s k i ) 距离。 。 。，x ，) 巾一x - ( 耄l x , - x , 1 2 r ( 2 1 ) 当q11 时，为曼哈： h _ ( m a n h a n t t a n ) 距离： d ( x ，盖，) - t l x t x 罐- 陆* 一z 业l ( 2 2 ) 当g - 2 时，为欧几罩德( e u c l i d ) 距离： 哗沪忱_ 州蹇k 嗨1 2 ) ( 2 3 ) 当日。3 时，为切比雪夫( c h e b y s h e v ) 距离： ； 、r 第一章聚类分析 。( x , , x j ) - i i x , - x j l l ；( 妻l x 。一x 业1 3 ) ”3 ( z 4 ) 当各变量的测量值相差悬殊时，采用明氏距离来定义是不合理，需要先对数据标准 化，然后用标准化后的数据来计算距离。 明氏距离特别是其中的欧氏距离是人们较为熟悉的，也是使用最多的距离，但明氏 距离存在不足之处，主要表现在两个方面： 第一：它与各指标的量纲有关。 第二：它没有考虑指标之间的相关性，欧氏距离也不例外。 2 ) 马氏距离 设表示协方差矩阵即； z ：( ) 。，其中嘞= 击三慨一置) 一弓) ，f ，吐一，d 墨_ 古著工“，i ，。古荟工。 ( 2 5 ) 如果z 。存在，则两个样品之阳j 的马氏距离为 d ；( x ，x ，) 一o 。一并，) e - 1 0 ，一x ，) ( 2 6 ) 上式中的x 。为样本x 。的d 个指标组成的向量，即原始数据阵的第i 行向量。样品x ， 类似。顺便给出样品x 到总体g 的马氏距离定义为： d 2 ( x ，g ) 。( x p ) f 1 ( x 一群)( 2 7 ) 其中：肛为总体的均值向量，为协方差阵。 马氏距离既排除了各各样本间相关性的干扰，而且还不受各样本中的向量影响。除 此之外，它还有一些优点，如将原数掘集作线性交换，马氏距离仍不变等。 3 ) 兰氏距离 吣一h i 荟d 掣f ， ( 2 8 ) 此距离仅使用于一切而f ，0 的情况，这个距离有助于克服各指标之怕j 量纲的影响， 但没有考虑指标之阳j 的相关性。 2 相似系数： 1 ) 夹角余弦 将任何两个样本x ，与x i 看成d 维空间的两个向量，这两个向量的央角余弦用c o s o q 表示为： c o s o i ，一 d 荟 辱2 ，x 黔2 ( 2 9 ) 江南人学颅i ：学位论文 m 0 1sc o s 0 ? 1 。 当c o s 8 0 - 1 ，说明两个样品x 与x ，完全相似；c o s 接近1 ，说明两个样品墨与x 相似密切：c o s o ? - o ，说明x l 与x j 完全不一样； c o s e 0 接近0 ，说明x 与x i 差别大。 把所有两两样品的相似系数都算出，可排成相似系数矩阵： 一 c o s o l l c o s 0 2 l c o s 吼n c o s 吼 c o s 8 n lc o s e n ! - c o s e n n 其中c o s 0 1 l c o s 0 2 2 一c o s = 1 。h 是一个实对称阵，所以只须计算上三角形部分 或下三角形部分。 2 ) 相关系数 通常所说相关系数，一般指变量问的相关系数，作为刻画样品间的相似关系，也可 类似绘出定义，即第f 个样品与第个样品之问的相关系数定义为： d - ，一1 5 0 1( 2 1 0 ) 其中五- 荟工膻，暑。 荟z 肚。 实际上，r i 就是两个向量x 。一置与x ，一i ，的夹角余弦，其中墨国，焉y ， j ，一仃，i 。若将原始数据标准化，则置一x 一，0 ，这时，c ，- c o s 。把所有两两样品 的相关系数都算出来，可排成样品相关系数矩阵： 2 1 4 聚类的一般步骤 r - ( ) = 在实际聚类分析过程中，根据有无知识领域参与可将整个过程分解为三个环节，每 一个环节都有其明确的任务，对于整个聚类一般过程【3 3 j 就会有更清晰的认识，如下图 2 1 所示： 8 一 兰三里型鲞坌塑 第一步特征提取： 它的输入是原始样本，由专家决定使用那些特征来深刻地刻画样本的本质性质和结 构。它的结果输出是一个矩阵，矩阵的每一行是一个样本。每一列是一个特征指标变量。 选取特征的好坏将直接影响以后的分析和决策。如果第一步就选择了和聚类意图根 本无关的特征变量，那企图得到良好的聚类结果则无异是缘木求鱼。合理的特征选取方 案应当使得同类样本在特征空间中相距较近，不同类样本则相距较远。 第二步执行聚类算法，获得聚类谱系图： 它的输入是一个样本矩阵，它要求把任意一个样本想像成特征变量空问中一个点。 聚类算法的目的是获得能够反映在某些维度空问中这些样本点之间最本质的“簇成一 团”性质。这一步没有专家的参与，它除了几何知识外不考虑任何领域知识，不考虑特 征变量在其领域中的特定含义，仅仅认为它是特征空间中一维。聚类算法的输出一般是 一个聚类谱系图。 第三步选取合适的阈值： 在得到聚类谱系图之后，专家凭借经验和领域知识，根据具体的应j 【= f j 场合，决定 阀值的选取。选定阀值之后，就能够从聚类谱系图上直接看出分类方案。专家还可以对 聚类结果结合领域知识进行进一步的分析，从而加深样本点和特征变量的认识。 总之，实际应用聚类分析是一个需要多方参与的过程，它无法脱离领域专家的参 与，聚类算法仅仅是整个聚类流程中的一环，光依靠聚类算法一般是得不到令人满意的 效果。 9 江南人学蛳 ：学位论文 2 2 聚类分析的主要算法 目前有很多聚类算法 1 1 , 1 2 , 1 3 , 1 4 】。如何选取恰当的聚类算法取决于：处理的数据类型、 聚类的目的以及应用领域等各方面。如果聚类分析被用作描述或探查的工具，可以对同 一个数据集尝试多种不同类型的聚类算法，可以发现数掘集内在隐含的信息或知识，因 而把聚类算法分成有参数的方法和非参数的方法。参数的方法试图获得最小化一个代价 函数或优化标准：非参数的方法是基于数据相似度或距离的方法。对聚类算法的分类并 不是很严格，有些算法可能同时包含于多个分类算法中。 2 2 1 层次算法 层次聚类算法是个非参数估计算法，它的定义：对于给定的n 个样本，首先将有所 有样本分成h 类，每类正好包含有一个样本；其次将样本分成 j 类，接着分成n - 2 类， 直到所有的样本都被分成一类为止。我们称聚类数目c = n k + l 对应层次结构的第k 层， 对层次结构的任意一层及其该层中的任意两个样本，如果它们在该层中属于同一个类， 而且在更高的层次一直属于同一类，那么这样的序列则称为“层次聚类”1 1 那。最自然的 表达“层次聚类”的方式就是树，另一种表达方式是集合。该方法通过两个途径来实现： 合并( a g g l o m e r a t i v e ) 和分裂( d i v i s i v e ) 。 1 ) 合并的层次聚类：这种自底向上的策略首先将每个对象作为单独的一个簇，然 后采用距离的方法合并这些原子簇为越来越大的簇，直到所有的对像都在一个 簇中，或者达到某个终止条件。 2 ) 分裂的层次聚类：这种自顶而下的策略与凝聚的层次聚类相反，它首先将所有的 对象置于一个簇中。然后逐渐细分为越来越小的簇，直到每个对象在单独的个 簇中，或者达到一个终止条件，如达到了某个希望的簇数目后者两个簇之间的距 离超过了某个阀值。 层次聚类算法尽管简单，但经常会遇到合并或分裂点选择的困难。这个选择有时是 非常关键的，因为一旦一组对象( 合并或分裂) 完成，它就不能被撤销，下一步的处理 将是在新构造的簇上继续进行这个过程。这个严格规定是有用的，由于不用担心组合数 目的不同选择，计算代价会比较小，但是已做的处理不能被撤消，聚类之间也不能交换 对象。如果在某一步没有很好的选择合并或分裂的决定，可能会导致低质量的聚类结果。 而且，这种聚类不具有很好的可伸缩性。因为合并或分裂的决定需要检查和估算大量的 对象或结果。 改进层次聚类算法的质量，一个有希望的方向是将层次聚类和其他聚类技术集成。 有两种方法可以改进层次聚类的结果： 第一种方法：在每层划分中，仔细分析对象问的“联接”，例如c u r e l l 6 啤c h a m c l c o n 1 7 l 中的做法。 第二种方法：综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用 迭代的重定位来改进结果。例如b i r c h l “l 中的方法。 ，o 第二：章梨类分析 2 2 2 划分算法 给定一簇样本集或对象的数据集，用一个划分方法构建数据的k 个划分，每个划分 表示一个聚类簇，并且ks n 。即：它将数据集划分为k 个组，同时满足如下要求： 第一点：每个划分至少要包含一个样本。 第二点：每个样本必须且只属于一个划分中。 给定要构建的划分数目k ，划分方法首先创建一个初始划分。然后采用一种迭代的 重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分一般准则是：在同 一类中的对象之间尽可能“接近”或相关，而不同类别中的对象之间尽可能“远离”或 “不同”。 为了达到全局最优，基于划分的聚类会要求穷举出所有可能性的划分。实际上，绝 大多数采用以下两个比较流行的启发式方法： 1 ) 采用质心的技术：k 均值法 均值法以k 为参数，把n 个对象分为k 个聚类簇，目的使簇内具有较高的相似度， 而簇帕j 的相似度较低。相似度的计算根据一个簇中对象的平均值( 被看作簇的重心) 来 进行。 女均值法的处理流程如下。首先，随机地选择k 个对象，每个对象初始地代表一个 簇的平均值或中心：其次，对剩余的每个对象，根据其与各个簇中心的距离，将它赋给 最近的簇；然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。通 常采用平方误差准则，其定义如下： k e - l p m f l 。 i - 1 p c f 上式中e 是数据库中所有样本的平方误差的总和，p 是空间的点，表示给定的数据 样本，m ，是簇c ，的平均值( p 和m ；都是多维的) 。这个准则是使生成的结果簇尽可能的 紧凑和独立。 这个算法尝试找出是平方误差函数值最小的k 个划分，当结果簇是密集的，而簇与 簇之间区别明显时，它的效果较好。对处理大数据集，该算法是相对可伸缩的和高效率 的，因为它的复杂程度是o ( n k t ) 。其中，n 是所有对象的数目，k 是簇的数目，t 是迭代 的数目。 2 ) 基于有代表性的样本的技术：七中心点方法1 3 2 i 把簇中位置靠最中心的样本，作为参照点即中心点，这样划分依然是基于最小化所 有样本与参照点之阳j 的相异度之和的原则来执行的，这是t 一中心点的基础。它的基本思 想是：首先为每个簇任意选择一个代表样本；其次剩余样本根据与代表对象的距离分配 给最近的一个簇：然后反复用非代表样本替代代表样本，以改进聚类的质量。聚类结果 的质量用一个代价函数来f 占算，陔函数度量样本与参照样本之间的平均相异度。为了判 定一个非代表样本是否为当| j 一个代表样本的好的替代，对于每一个非中心点样本p ， 下面的四种情况将被考虑： 江南人学坝i j 学位论义 第一种：p 当前隶属于中心点0 ，。如果0 ，被o r a n d o m 所代替作为中心点，且p 离一个 d 。最近，i _ 那么p 被重新分配给d 。 第二种：p 当前隶属于中心点0 ，如果0 ，被o r a n d o m 代替作为中心点，且p 离o r a n d o m 最近，那么p 被重新分配给o r a n d o m 。 第三种：尸当前隶属于中心点o ；，i - j 。如果0 ，被o r a n d o m 代替作为一个中心点，而 p 依然离0 ，最近，那么对象的隶属不发生变化。 第四种：p 当前隶属于中心点q ，i _ ，。如果0 ，被o r a n d o m 代替作为一个中心点，且 尸离o r a n d o m 最近，那么p 被重新分配给o r a n d o m 。 “那个方法更有健壮性：k 平均值或者k 中心点? ”如果研究对象中存在“噪声” 和孤立点数据时，k 中心点比k 平均更健壮，这是因为中心点不像平均值那样容易受 到极端数据影响；但是，k 中心点的执行代价比k 平均方法高。 这些启发式方法用来处理中小型规模的数据库以发现球状聚类簇非常实用的。为了 对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的 扩展。 2 2 3 基于密度的算法 大部分划分算法都是基于样本之间的距离进行聚类，只能发现球状的聚类簇，而不 能发现任意形状的聚类簇。基于密度的方法可用来过滤“噪声”数据和孤立点数据，可 以发现任意形状的聚类，其主要思想是：只要邻近区域的密度( 对象或数据点的数目) 超出了