模式识别2010聚类分析


2010-10-20 1 模式识别原理模式识别原理 华中科技大学图像识别与人工智能研究所华中科技大学图像识别与人工智能研究所 图像分析与智能系统研究室图像分析与智能系统研究室 曹治国曹治国 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 2010-10-20 3 分类Classification与聚类Clustering分类Classification与聚类Clustering 2010-10-20 4 },...,,{ 21 NxxxX = miCi ,...,2,1 , =∅≠ XCU i m i = =1 mjijiCC ji ,...,2,1, , , =≠∅=∩ 聚类的定义聚类的定义 设X是数据集,即 定义X的m聚类R,将X分割成m个集合(聚类) C1,…Cm, 使其满足下面三个条件: 2010-10-20 8 聚类分析步骤聚类分析步骤 Feature Selection Feature Selection 选择合适的特征描述样本选择合适的特征描述样本 Proximity Measure Proximity Measure 选择合适的测度描述样本之间如选择合适的测度描述样本之间如 何何““相似相似””或或““不相似不相似”” Clustering Criterion Clustering Criterion 选择合适的聚类准则选择合适的聚类准则 Clustering Algorithm Clustering Algorithm 选择特定的算法,用于揭示数选择特定的算法,用于揭示数 据集的聚类结构据集的聚类结构 Validation and Interpretation of the Result Validation and Interpretation of the Result 结果的验结果的验 证与判定证与判定 2010-10-20 9 为什么研究相似性测度为什么研究相似性测度 ““相似相似””、、““不相似不相似””依赖于聚类的类型依赖于聚类的类型 致密型聚类、长条形聚类、球形或椭圆聚类所采用致密型聚类、长条形聚类、球形或椭圆聚类所采用 的相似度会不一样的相似度会不一样 2010-10-20 10 为什么研究聚类准则为什么研究聚类准则 繁衍后代的方式繁衍后代的方式 羊狗猫 蓝鲨 麻雀 蜥蜴 青蛙 海鸥 金鱼 红鲣 毒蛇 金鱼 红鲣 蓝鲨 麻雀 蜥蜴 青蛙 海鸥羊狗猫 毒蛇 肺是否存在肺是否存在 金鱼 红鲣 蓝鲨 麻雀 蜥蜴 海鸥羊狗猫 毒蛇 青蛙 生活环境生活环境 2010-10-20 11 为什么对结果需要验证判定为什么对结果需要验证判定 22类还是类还是44类?类? 专家知识 2010-10-20 12 为什么研究聚类算法为什么研究聚类算法 考虑聚类的数量:考虑聚类的数量: 给定时间和资源,将集合给定时间和资源,将集合XX中的特征向量中的特征向量xixi,,i=1,i=1,……,N,N 到聚类中的最好办法是识别所有的划分,并根据事先确到聚类中的最好办法是识别所有的划分,并根据事先确 定的准则选择最可能的聚类。定的准则选择最可能的聚类。 令令 S(N,mS(N,m) ) 表示将表示将NN个向量聚类到个向量聚类到mm组的所有可能结果组的所有可能结果 S(N,1) = 1S(N,1) = 1;; S(N,N) = 1S(N,N) = 1;; 当当m>Nm>N S(N,mS(N,m)) == 00 令令 表示表示NN--11个向量分到个向量分到kk类的所有可能,类的所有可能,k=mk=m,,mm--11 第第NN个向量个向量 或者添加到或者添加到 中的任一个成员的聚类中中的任一个成员的聚类中 或者对或者对 的的 每个成员形成一个新聚类每个成员形成一个新聚类 k NL 1− m NL 1− 1 1 − − m NL )1,1(),1(),( −−+−= mNSmNmSmNS 2010-10-20 13 为什么研究聚类算法为什么研究聚类算法 上式的解为:上式的解为: (该公式作为习题请课后证明)(该公式作为习题请课后证明) )1,1(),1(),( −−+−= mNSmNmSmNS ∑ = −−= m i Ni m im iCmmNS 0 )1(! 1),( 101 375 2)3,15( =S 901 115 232 45)4,20( =S !!10)5,100( 68=S 如果要评估100个样本分到5类的所有可能聚类,计算机计算每个 聚类需要 秒,则大约 年后才会得到最可判断的聚类1210− 4810 2010-10-20 14 为什么研究聚类算法为什么研究聚类算法 聚类算法可以视为: 通过考虑包含在X中所有可能划分集合 的一小部分,就可以得到可判断聚类的 方案 这个结果依赖于使用的算法和准则 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 )(•d 第2章 聚类分析第2章 聚类分析 聚类测度聚类测度 不相似性测度(不相似性测度(Dissimilarity Dissimilarity Measure,DMMeasure,DM)) 相似性测度(相似性测度(Similarity Measure, SMSimilarity Measure, SM)) 对于对于 XX上不相似性测度可用距离空间上不相似性测度可用距离空间 来度量,它必须满足:来度量,它必须满足: Xzyx ∈∀ ,, ),(),(),()3( ),(),()2( 0),(,0),()1( zydzxdyxd xydyxd xxdyxyxd +≤ = =≠∀> X X 上相似性测度可用上相似性测度可用 来度量,它必须满足:来度量,它必须满足:)(•s ),()],(),([),(),()3( ),(),()2( ),(,),()1( 00 yxszyszxszyszxs xysyxs sxxsyxsyxs +≤ = =≠∀+∞<≤<∞− 一、距离测度一、距离测度 11,欧氏,欧氏(Euclidean)(Euclidean)距离:距离: 22,绝对值距离,绝对值距离:: 33,切氏,切氏((ChebyshevChebyshev))距离距离:: 44,明氏,明氏((MinkowskiMinkowski))距离距离:: 设设 )',,(,)',,( 2121 nn yyyyxxxx == 2/1 1 2 ])([||||),( ∑ = −=−= n i ii yxyxyxd ∑ = −= n i ii yxyxd 1 ||),( ||),( max ii i yxyxd −= m n i m ii yxyxd /1 1 ])([),( ∑ = −= 第2章 聚类分析第2章 聚类分析 2.2 2.2 模式的相似性测度模式的相似性测度 一、距离测度一、距离测度 5, 5, 马氏马氏((MahalanobisMahalanobis))距离距离:: 设设nn维矢量维矢量 是矢量集是矢量集 中的两个矢量中的两个矢量 6, 6, CamberraCamberra距离:距离: ∑ ∑ = = − = −−−= −−= m i i m i ii jijiji xmx xxxxmV xxVxxxxd 1 1 1 1 )')((1 1 )()'(),( )0,0,(|| ||),( 1 ≠+≥+ −= ∑ = iiii n i ii ii yxyxyx yxyxd ji xx , },,,{ 21 mxxx 第2章 聚类分析第2章 聚类分析 2.2 2.2 模式的相似性测度模式的相似性测度 第2章 聚类分析第2章 聚类分析 2.2 2.2 模式的相似性测度模式的相似性测度 二、相似测度二、相似测度 11,角度相似系数:,角度相似系数: 22,相关系数,相关系数:: 33,指数相似系数,指数相似系数:: 44,各特征值非负时的几种相似系数,各特征值非负时的几种相似系数:: (略(略)) 设设 )',,(,)',,( 2121 nn yyyyxxxx == |||||||| '),cos( yx yxyx ⋅= 2/1)]()')(()'[( )()'(),( yyyyxxxx yyxxyxr −−−− −−= ∑ = −−= n i i ii yx nyxe 1 2 2 ])( 4 3exp[1),( σ 第2章 聚类分析第2章 聚类分析 2.2 2.2 模式的相似性测度模式的相似性测度 三、匹配测度三、匹配测度 11,,TanimotoTanimoto测度:测度: 22,,RaoRao测度测度:: 33,简单匹配系数,简单匹配系数:: 44,,DiceDice系数系数:: 55,,KulzinskyKulzinsky系数系数 详见详见《《现代模式识别现代模式识别》》,孙即祥编著,孙即祥编著 当特征只有两个状态时可使用当特征只有两个状态时可使用 第2章 聚类分析第2章 聚类分析 2.2 2.2 模式的相似性测度模式的相似性测度 没有哪个测度是最好的没有哪个测度是最好的 11,简单而易于理解,简单而易于理解 22,易于实现,易于实现 33,满足速度要求,满足速度要求 44,考虑数据的知识,考虑数据的知识 选择时,可考虑以下几点选择时,可考虑以下几点 第2章 聚类分析第2章 聚类分析 2.3 2.3 类的定义与类间距离类的定义与类间距离 2.3.1 2.3.1 类的定义类的定义 定义定义11:集合:集合SS中任两个元素中任两个元素 ,, 的距离的距离 有有 其中其中hh为给定的阈值,称为给定的阈值,称SS对于阈值对于阈值hh组成一类组成一类 定义定义22:集合:集合SS中任一个元素中任一个元素 与与 的距离的距离 有:有: kk为集合为集合SS中元素的个数,中元素的个数, hh为给定的阈值,为给定的阈值, 称称SS对于阈值对于阈值hh组成一类组成一类 模式的特征矢量作为聚合中的元素模式的特征矢量作为聚合中的元素 iX jX ijd hdij ≤ iX jX ijd hdk Sx ij j ≤− ∑ ∈1 1 第2章 聚类分析第2章 聚类分析 2.3 2.3 类的定义与类间距离类的定义与类间距离 2.3.1 2.3.1 类的定义类的定义 定义定义33:集合:集合SS中中 ,, 的距离的距离 有有 ,, 其中其中hh,,rr为给定的阈值,称为给定的阈值,称SS对于阈值对于阈值hh和和rr组成一类组成一类 定义定义44:集合:集合SS中元素对于任一中元素对于任一 ,存在某,存在某 使距离:使距离: 称称SS对于阈值对于阈值hh组成一类组成一类 定义定义55:若将集合:若将集合SS任意分成两类任意分成两类S1,S2S1,S2,这两类的距离,这两类的距离D(S1,S2)D(S1,S2) 满足满足 ,称,称SS对于阈值对于阈值hh组成一类组成一类 iX jX ijd hdij ≤ hdkk SxSx ij jj ≤− ∑∑ ∈∈)1( 1 rdij ≤ SX i ∈ SX j ∈ hSSD ≤),( 21 第2章 聚类分析第2章 聚类分析 2.3 2.3 类的定义与类间距离类的定义与类间距离 2.3.1 2.3.1 类的定义类的定义 类的划分具有人为规定性,这反映在定义的选取及参类的划分具有人为规定性,这反映在定义的选取及参 数的选择上。数的选择上。 一个分类结果的优劣最后只能根据实际来评价,因此一个分类结果的优劣最后只能根据实际来评价,因此 较多地利用研究对象的知识才能选择适当的类的定较多地利用研究对象的知识才能选择适当的类的定 义,从而使分类结果更符合实际。义,从而使分类结果更符合实际。 第2章 聚类分析第2章 聚类分析 2.3 2.3 类的定义与类间距离类的定义与类间距离 2.3.2 2.3.2 类间距离测度办法类间距离测度办法 一、最近距离法:一、最近距离法: 两个聚类两个聚类 和和 之间的最近距离为:之间的最近距离为: 式中式中 表示表示 和和 之间的距离之间的距离 如果如果 是由是由 和和 两类合并而成的,则有两类合并而成的,则有 lωkω ][min ,, jijikl dD = ijd kiX ω∈ ljX ω∈ lω pω qω ],[min kqkpkl DDD = 第2章 聚类分析第2章 聚类分析 2.3 2.3 类的定义与类间距离类的定义与类间距离 2.3.2 2.3.2 类间距离测度办法类间距离测度办法 二、最远距离法:二、最远距离法: 两个聚类两个聚类 和和 之间的最近距离为:之间的最近距离为: 式中式中 表示表示 和和 之间的距离之间的距离 如果如果 是由是由 和和 两类合并而成的,则有两类合并而成的,则有 lωkω ijd kiX ω∈ ljX ω∈ lω pω qω ],[max kqkpkl DDD = ][max , ijjikl dD = 第2章 聚类分析第2章 聚类分析 2.3 2.3 类的定义与类间距离类的定义与类间距离 2.3.2 2.3.2 类间距离测度办法类间距离测度办法 三、中间距离法:三、中间距离法: 四、重心距离法:四、重心距离法: 设设 和和 的重心分别为的重心分别为 和和 ,它们分别有样本,它们分别有样本 和和 个,将个,将 和和 合并为合并为 ,则,则 有有 个样本,则它的重心为:个样本,则它的重心为: 设另一类设另一类 的重心为的重心为 ,则它与,则它与 的距离是:的距离是: 2222 4 1 2 1 2 1 pqkqkpkl DDDD −+= pω qω pX qX pn qn pω qω lω lω qpl nnn += )(1 qqpp qp l XnXnnnX ++= kω kX lω 2 2 22'2 )()( pq l qp kq l q kp l p lklkkl Dn nnDn nDn nXXXXD −+=−−= 第2章 聚类分析第2章 聚类分析 2.3 2.3 类的定义与类间距离类的定义与类间距离 2.3.2 2.3.2 类间距离测度办法类间距离测度办法 五、平均距离法:五、平均距离法: 六、离差平方和法:六、离差平方和法: 第2章 聚类分析第2章 聚类分析 2.3.3 2.3.3 聚类的准则函数聚类的准则函数 为了对模式集进行有效的分类,某些算法需要一个能对分类过为了对模式集进行有效的分类,某些算法需要一个能对分类过 程或分类结果的优劣进行评估的准则函数程或分类结果的优劣进行评估的准则函数 已定义已定义 模式与模式的相似性测度模式与模式的相似性测度 类与类之间的距离类与类之间的距离 第2章 聚类分析第2章 聚类分析 2.3 2.3 类的定义与类间距离类的定义与类间距离 2.3.3 2.3.3 聚类的准则函数聚类的准则函数 一、类内距离准则:一、类内距离准则: 二、类间距离准则:二、类间距离准则: 三、基于类内、类间距离的准则函数:三、基于类内、类间距离的准则函数: 四、基于模式与类核的距离的准则函数:四、基于模式与类核的距离的准则函数: 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 第2章 聚类分析—顺序聚类算法第2章 聚类分析—顺序聚类算法 一、基本的顺序聚类算法一、基本的顺序聚类算法 Basic Sequential Clustering Algorithm (BSAS) 该算法具有以下特点: • 所有的待分类样本只参与算法一次 • 聚类数事先未知,但用户可以确定允许的最大聚类数 q • 令 d (x,C) 表示从向量 x 到聚类C的距离(或不相似性) • 不相似性阈值 Θ 可事先确定 算法思路: 考虑每个样本,根据其到已有聚类的距离将它分配到一个 已有聚类中,或者一个新生成的聚类中。 ¾ Basic Sequential Clustering Algorithm (BSAS) • m=1 \{由算法生成的聚类数}\ • Cm ={x1 } • For i=2 to N − Find Ck : d (xi , Ck )=min1≤j≤m d(xi ,Cj ) − If (d (xi , Ck )>Θ) AND (m= θ lX lXZ =3 ]],...,[min[max 21 ikiiil dddd = |||| 21 ZZdl −> θ lk XZ =+1 NijZXd jiij ,...2,1,...,2,1||,|| ==−= liijjil Xdd ω∈= 则],[min 二、改进的顺序聚类算法二、改进的顺序聚类算法----最大最小距离算法最大最小距离算法 改进的顺序聚类算法可以总结为分成两个步骤:改进的顺序聚类算法可以总结为分成两个步骤: •• 聚类的确定(上述算法描述中的(聚类的确定(上述算法描述中的(11))---- •• 模式分类模式分类 (采用(采用BSASBSAS算法)算法) 算法对样本顺序敏感算法对样本顺序敏感 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 基于准则函数 最优化方法 三、三、kk均值聚类算法均值聚类算法 对于需要进行聚类的数据的一个基本假设: 对于每个 聚类 ,可以选出一个中心点,使得该 聚类中的所有的 点到该中心点的距离小于到其他 聚类的中心的距离。 设有 N 个样本需要分到 K 个聚类中,K均值算法的目标函数: 其中 表示样本 被归类到 第 k类的时候为 1 ,否则为 0 , 为第 k类的中心。 固定 将 对 求导并令导数等于零,得到 最小: nkr nx 2 11 |||| kn K k N n nk xrJ μ −= ∑∑ == kμ nkr J kμ J ∑ ∑= n nk n nnk k r xr μ 算法步骤算法步骤 ((11)任选)任选kk个模式特征矢量作为初始聚类中心:个模式特征矢量作为初始聚类中心: ((22)对待分类的模式特征矢量集)对待分类的模式特征矢量集{Xi}{Xi}中的模式逐个按最小距离原中的模式逐个按最小距离原 则分划给则分划给kk类中的某一类,即:类中的某一类,即: ((33)计算重新分类后的各类心:)计算重新分类后的各类心: ((44)如果)如果 ,则结束;,则结束; 否则,否则,t=t+1, t=t+1, GotoGoto (2)(2) 0,,..., )0()0( 2 )0( 1 =tZZZ k )1()()(,,...2,1],[min +∈== t li t ijj t il XNidd ω 则判如果 kjXnZ t jix it j t j ,...2,1,1 )1( )1( )1( == ∑+∈ + + ω kjZZ t j t j ,...2,1,)()1( ==+ 三、三、kk均值聚类算法均值聚类算法 算法收敛性证明:算法收敛性证明: 三、三、kk均值聚类算法均值聚类算法 初始化状态,随机选取三个类心初始化状态,随机选取三个类心 三、三、kk均值聚类算法均值聚类算法 迭代一次后迭代一次后 三、三、kk均值聚类算法均值聚类算法 再次迭代再次迭代 三、三、kk均值聚类算法均值聚类算法 迭代结束迭代结束 三、三、kk均值聚类算法均值聚类算法 初始状态初始状态 三、三、kk均值聚类算法均值聚类算法 收敛状态,不合适的初始值不能得到满意的聚类结果收敛状态,不合适的初始值不能得到满意的聚类结果 三、三、kk均值聚类算法均值聚类算法 三、三、kk均值聚类法均值聚类法 算法改进的出发点算法改进的出发点 算法的性能与算法的性能与kk及聚类中心初始值、样本顺序有关及聚类中心初始值、样本顺序有关 ((11))kk的调整的调整 ((aa)按先验知识确定)按先验知识确定kk ((bb)让)让kk从小到大逐步增加,每个从小到大逐步增加,每个kk都用都用kk--均值法分类,均值法分类,JJ 随随kk的增加而单调减少,但速度在一定时候会减的增加而单调减少,但速度在一定时候会减 曲率变化最大点对应最优类数曲率变化最大点对应最优类数 三、三、kk均值聚类法均值聚类法 算法改进的出发点算法改进的出发点 ((22)初始聚类中心的选择)初始聚类中心的选择 ((aa)凭经验)凭经验 ((bb)将模式随机分成)将模式随机分成kk类,计算每类中心,作为初始类心类,计算每类中心,作为初始类心 ((cc)求以每个特征点为球心,某一正数)求以每个特征点为球心,某一正数d0d0为半径的球型区域为半径的球型区域 中的特征点个数(即该特征点的密度),选取密度最大的特征点中的特征点个数(即该特征点的密度),选取密度最大的特征点 为第一个初始聚类中心,然后,在与该中心大于某个距离为第一个初始聚类中心,然后,在与该中心大于某个距离dd的那的那 特征点中选取另一个具有最大密度的特征点作为第二个初始聚类特征点中选取另一个具有最大密度的特征点作为第二个初始聚类 中心,直到选取中心,直到选取kk个初始类心个初始类心 ((dd)用相距最远的)用相距最远的kk个特征点作为类心个特征点作为类心 ((ee)当N较大时,先随机地从)当N较大时,先随机地从NN个模式中取出一部分模式用个模式中取出一部分模式用 层次聚类法聚成层次聚类法聚成kk类,以每类的重心作为初始类心类,以每类的重心作为初始类心 ((3)用类核代替类心3)用类核代替类心 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 基于准则函数 最优化方法 四、四、kk中值聚类法中值聚类法 kk均均值聚类算法的类心是:值聚类算法的类心是: KK中中值聚类算法的类心是值聚类算法的类心是从当前从当前类类 中选取这样一个点中选取这样一个点 ————它到它到该类该类其他所有点的距离之和最小其他所有点的距离之和最小 两者的差异:两者的差异: 前者的取值范围可以是连续空间中的任意值,适用于数值 类型的特征 而后者只能在给样本给定的那些点里面选,适用于种类类 型的特征,即其样本表征的是类别特征而非数值特征,如 鱼的种类:鲈鱼、鲑鱼、鲫鱼、草鱼等。 ∑ ∑= n nk n nnk k r xr μ 四、四、kk中值聚类法中值聚类法 KK中值聚类算法的准则函数中值聚类算法的准则函数 假设每一个类选出一个向量表示它,这个向量称为假设每一个类选出一个向量表示它,这个向量称为 ““中值中值””,令,令 表示所有类的表示所有类的““中值中值””集合,定义集合,定义 为待聚为待聚 类的样本集类的样本集XX中包含中包含 点的集合,定义点的集合,定义 为不包含为不包含““中中 值值””点的集合,则准则函数为:点的集合,则准则函数为: Θ ΘI Θ Θ−XI ),( ji IiIj ij xxdrJ X ∑∑ Θ−Θ∈∈ = 1,...Ni,0 ),(min),(,1 = ⎩ ⎨ ⎧ == Θ∈ 其他 若 qiIqji ij xxdxxdr 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 基于准则函数 最优化方法 五、模糊五、模糊CC--均值算法均值算法 ((11)模糊子集)模糊子集 ((22)模糊)模糊CC--均值算法(均值算法(FCMFCM算法)算法) 将将NN个个nn维特征矢量维特征矢量 分成分成CC类,分类结果用分划类,分类结果用分划 矩阵矩阵 表示,表示, 表示样本表示样本 属于属于 类的程度,它满足类的程度,它满足 FCMFCM算法在迭代寻优过程中,使算法在迭代寻优过程中,使 达到最小达到最小 式中:式中: ,, 为为 类的中心矢量,权重类的中心矢量,权重 ,,VV为协方差矩阵为协方差矩阵 },,,{ 21 NxxxX = CNijuU ×= )( iju ix jω 1:)(;,0:)(];1,0[:)( 11 =∀<<∈ ∑∑ == C j ij N i ijij ucjNubua ∑∑ == = C j ij m ij N i m duZuJ 1 2 1 ),( },,,{ 21 czzzZ = jz jω 51 ≤< m )()'(2 jijiij zxVzxd −−= 五、模糊五、模糊CC--均值算法均值算法 ((33))FCMFCM算法步骤算法步骤 ((aa)确定类别数)确定类别数CC,参数,参数mm,矩阵,矩阵VV和适当小数和适当小数 ((bb)置初始模糊分类矩阵)置初始模糊分类矩阵 ,令,令 ((cc)计算)计算 时的时的 :: ((dd)按下面的方法更新)按下面的方法更新 为为 ,, 对对i=1i=1至至NN (i)(i)计算计算 和和 :: (ii)(ii)计算计算 的新隶属度:的新隶属度: 如果如果 ,则:,则: 否则,否则, ((ee)若)若 ,停止。否则,,停止。否则,GotoGoto ((cc)) ix )0(U ))(/(1 1 1 2 ∑ = −= c k m ik ij ij d du 0=k cjuxuz N i m ij N i i m ij k j ,2,1)/()( 11 )( == ∑∑ == iiiji IcIdjI −=== },2,1{},0|{ }{)(k jz iI 0>ε )(kU )(kU )1( +kU iI Φ=iI 1,,0 =∈∀= ∑ ∈ iIj ijiij uIju 并取 ε<− + |||| )1()( kk UU 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 ♦ 六、层次聚类算法 以上算法聚类前如何确定类别数? 第2章 聚类分析----层次聚类算法第2章 聚类分析----层次聚类算法 ♦ 六、层次聚类算法 ♦ 假定 g (C i ,C j ) 是所有可能聚类对的相似性测度. ♦ 通用合并方法(Generalized Agglomerative Scheme, GAS) – 初始化 • 选择初始聚类为 ℜ0 ={{x1 },…,{x N }} • 令t=0 – 重复执行以下步骤 • t=t+1 • 在ℜt-1 所有可能聚类对(C r , C s )中找一种 (C i ,C j )满足 • 定义 C q =C I ∪ C j 并产生新聚类 ℜt =(ℜt-1 -{Ci ,Cj }) ∪{C q } – 直到所有的向量全被加入到单一聚类中. ⎪⎩ ⎪⎨ ⎧ = functionsimaisgifCCg functiondisimaisgifCCgCCg srsr srsr ji .),,(max .),,(min),( , , 第2章 聚类分析----层次聚类算法第2章 聚类分析----层次聚类算法 ♦ 六、层次聚类算法 ♦ 通用合并方法的每个聚类嵌套在它的后续聚类中 ♦ 如果两个向量一起加入t 层次的同一聚类中,可以认为它们 的后续聚类相同。 ♦ 嵌套性质的缺点是不能从一个“坏”的聚类中恢复,“坏”的 聚类产生在更早的层次上。 ♦ 假设在层次t上,有N-t个聚类。为了确定t+1层上要合并的 聚类对,必须考虑以下数量的可能。 ♦ 因此,聚类过程总共要考虑的聚类对的数量为: ♦ 也就是说合并算法的全部运算量在 的数量级上。 2 ()(1) 2Nt NtNtC − − −−= 第2章 聚类分析----层次聚类算法第2章 聚类分析----层次聚类算法 1 22 01 (1)(1) 6 NN Nt k tk NNNCC − − == − +==∑∑ 3N 对通用合并方法中的一些变量给出如下定义: ♦ 待分类的样本集为: , 其中每个样本为: ,这表明样本向量具有l维特征 ♦ 样本矩阵D(X)是 N x l 矩阵,其中第 i 行是X的第 i 个向量 (转置) ♦ 测度矩阵(相似或不相似)P(X)是一个 N x N矩阵,它的 第 (i, j)元素是向量 xi 和向量xj 的相似度 s (xi, xj)或不相似 度 d (xi, xj) 12{ , ,... }NXxxx= 12[, ,...]T iiiilxxxx= 例:有样本集 X={x1 , x2 , x3 , x4 , x5 }, 其中: x1 =[1, 1]T, x2 =[2, 1]T, x3 =[5, 4]T, x4 =[6, 5]T, x5 =[6.5, 6]T. ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 65.6 56 45 12 11 )(XD ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 01.15.27.64.7 1.104.17.54.6 5.24.102.45 7.67.52.401 4.74.6510 )(XP ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 198.090.020.018.0 98.0196.035.021.0 90.096.0144.026.0 20.035.044.0175.0 18.021.026.075.01 )('XP 样本集矩阵 使用欧式距离时的不相似矩阵 使用Tanimoto测度时的相似矩阵 ¾ 阈值图或简单树图是由合并算法生成的聚类顺序 的有效表达. 定义 当两个向量间使用欧氏距离时,由通用合并方法 产生的X聚类顺序如下图: min(, ) (, )ss ij ijgC C d C C= x 1 x 2 x 3 x 4 x5{{ },{ },{ },{ },{ }}xxxxx12345 {{ , },{ },{ },{ }}xx x x x12 3 4 5 {{ , },{ },{ , }}xx x xx12 3 45 {{,},{,,}}xx xxx12 345 {{,,,,}}xxxxx12345 ¾ 下图为例子中聚类X分别使用P΄(X) 和 P(X)时,构成 的相似和不相似树图 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 S i m i l a r i ty s c a l e x1 x2 x3 x4 x 5 10 0 1 2 3 4 5 9 8 7 6 Dissimilarity scale x 1 x2 x3 x4 x 5 (a) (b) ♦ 合并算法主要分为两类: – 基于矩阵理论的算法。 – 基于图论的算法。 以下讨论中我们仅考虑不相似性测度 – 基于矩阵理论的算法. 从不相似矩阵 Pt-1 得到 Pt步骤 • 针对 N个样本集X组成的 N × N 不相似矩阵 P0 =P(X). • 在t级两个聚类 C i 和 C j 合并成聚类 C q时,通过以下步 骤从不相似矩阵 Pt-1 得到 Pt : − 删去对应于C i 和 C j 类对应的两行和两列. − 计算包括新聚类(即C q )和旧聚类Cs(此层未影响 聚类)之间的距离,计算公式如下: d (C q , Cs ) =f ( d (C I ,C s ), d (C j , C s ) , d( C i , C j )) 将其作为新增加的行和列 • 距离函数符合以下更新方程: 当a, b, c取不同值时可得到以下不同算法: ¾ 单连接算法 (ai=1/2, aj=1/2, b=0, c=-1/2).此时 取两个集合中距离最近的两个点的距离作为这两个集合的距离 ¾ 完全连接算法 (ai=1/2, aj=1/2, b=0, c=1/2).此时 取两个集合中距离最远的两个点的距离作为两个集合的距离 (,) (,) (, ) (,) | (, ) ( , )|qs i is j jS i j is jsdC C adCC adC C bdCC c dC C dC C= +++− (,)max{(,),(, )}qs is jSdC C dC C dC C= (,)min{(,),(, )}qs is jSdC C dC C dC C= ♦ 矩阵更新算法(Matrix Updating Algorithm Scheme, MUAS) – 初始化 • 选择初始聚类为 ℜ0 ={{x1 },…,{x N }} • P0 =P(X) • 令t=0 – 重复执行以下步骤 • t=t+1 • 选择C i ,C j, 使之满足 • 合并C i ,C j, 得到聚类C q, 形成 ℜt =(ℜt-1 -{Ci ,Cj }) ∪{C q } • 根据上述步骤从不相似矩阵Pt-1 得到 Pt – 直到形成聚类ℜN-1 即所有的向量全被加入到单一 聚类中. , 1,...,(, )min (, )ij rsN rsdC C dC C== ¾ 例子 (a) 样本集 X. (b) 单连接算 法获得的不相 似树图. (c) 完全连接 算法得到的不 相似树图 ¾单连接算法在低不相似时产生聚类, 这是因为它使用 , 这意味着单连接算法有适应拉长聚类 的趋势。 ¾完全连接算法在高不相似时产生聚类 ,这是因为它使用 ,这意味着完全连接算法倾向于处理 小的致密型聚类 (,)min{ (, ),(, )}qs is jSdC C dC C dC C= (,)max{ (, ),(, )}qs is jSdC C dC C dC C= – 上述两种方法为极端情况,实用性不强 – Group Average:这种方法看起来相对有道理一 些,也就是把两个集合中的点两两的距离全部 放在一起求一个平均值,相对也能得到合适一 点的结果。 – 除合并方法外,还有分裂方法 第2章 聚类分析第2章 聚类分析 •• 聚类分析的概念聚类分析的概念 •• 相似性测度与聚类准则相似性测度与聚类准则 •• 聚类算法聚类算法 顺序聚类算法顺序聚类算法 KK均值算法均值算法 KK中值算法中值算法 模糊模糊KK均值算法均值算法 层次聚类算法层次聚类算法 谱聚类算法谱聚类算法 七、谱聚类算法七、谱聚类算法 1、当前受到广泛关注的聚类算法1、当前受到广泛关注的聚类算法 22、、 很多经典算法都无法完成的应用,它可获得良很多经典算法都无法完成的应用,它可获得良 好的性能好的性能 如如 kk均值聚类易陷入局部极小值均值聚类易陷入局部极小值 33、、 有很多相关理论支撑有很多相关理论支撑 用图表示样本在特征空间中的相互联系用图表示样本在特征空间中的相互联系 将代数(矩阵)理论引入图的世界将代数(矩阵)理论引入图的世界 c 七、谱聚类算法七、谱聚类算法 谱谱-------- 通俗的解释:通俗的解释:如果我们把一个东西看成是一些分量如果我们把一个东西看成是一些分量 加而成,那么这些分量以及它们各自所占的比例,就叫这加而成,那么这些分量以及它们各自所占的比例,就叫这 个东西的谱。个东西的谱。 例,例,频谱,把一个信号分解成多个频率单一的分量。频谱,把一个信号分解成多个频率单一的分量。 矩阵的谱矩阵的谱:用特征值和特征向量反映矩阵特性:用特征值和特征向量反映矩阵特性 如果A v = c v,那么c就是A的特征值,v就叫特征向量。 对于某些向量,矩阵对它的作用很简单,A v = cv,相当于 就把这个向量v拉长了c倍。对新的向量x ,可分解为这些 向量的组合,x = a1 v1 + a2 v2 +...,那么A对x的作用就可 以分解:A x = A (a1 v1 + a2 v2 + ...) = a1 c1 v1 + a2 c2 v2... 所以,矩阵的谱就是用于分解一个矩阵的作用的。 c 77 七、谱聚类算法 图论的基本定义(只涉及与谱聚类算法相关概念) • 用有序对G=(V,E)定义图 G,其中 V={vi , i=1,…,N} 是顶点集合,E是连接这些顶点对的边的集合。连 接顶点vi 和 vj 的边用eij 或者 (vi ,vj )表示。 • 如果vi 和 vj 的顺序无关紧要,则图G是无向图;否 则,图G是有向图。 • 如果图中的边没有代价,则图G是无权图。否则为 有权图。 • 任何两个顶点之间都至少 有一条路径的图为连通图 78 七、谱聚类算法 谱聚类的基本定义 • 令样本集 • 创建一个图G(V,E),图中的每个顶点分别对应于集合 中的点 ,且图G是无向连通图 • 用权值W(i,j)为图的每个边赋权值 ,其中w用来度量 G中各顶点vi 和 vj 之间的相似性。权值的集合定义了 N*N维的相似矩阵W,它带有元素: { } l N RxxxX ⊂= ,...,, 21 X Nixi ...2,1= ije [(,)],, 1,2...W Wij ij N== 2 2 || ||exp( ), || ||(, ) 2 0 , ij ij xx if x xWij otherwise εσ ⎧ −⎪ − −<= ⎨ ⎪⎩ ||。||表示欧几里德范数, 用户定义(, ) ( ,)Wij W ji= ε 79 七、谱聚类算法 谱聚类的任务 • 将样本集 二分为A和B两个聚类 • 在上述定义基础上,基于图的聚类方法由以下两步 组成: • 选择一个合适的聚类准则划分这个图 • 采用一个有效的算法策略来执行划分 { } l N RxxxX ⊂= ,...,, 21 ,ABX AB∪= ∩=∅ 80 七、谱聚类算法 谱聚类的准则----图割 • 简单地说就是把一个 Graph 的一些边切断,让他被 打散成一些独立联通的 sub-Graph ,而这些被切断 的边的权值的总和就被称为 Cut 值。 • 我们可以要求切割所得的 Cut 值最小,亦即:那些 被切断的边的权值之和最小,直观上我们可以知道 ,权重比较大的边没有被切断,表示比较相似的点 被保留在了同一个 sub-Graph 中,而彼此之间联系 不大的点则被分割开来。 81 七、谱聚类算法 谱聚类的准则----图割 • 假设类别为A和B,则他们是 Graph 的两个子集, 且没有交集,那么两者之间的 cut 可以定义为: , (,) (,) iAjB Cut A B W i j ∈∈ = ∑ 聚类准则就是选择A和B,使Cut(A,B)达到最小化,即连接A 中的节点和B中节点的边的集合有最小的权值总和。 其不足之处是:得到的聚类结果可能是很大的区块和一些几 乎是孤立的点 82 七、谱聚类算法 谱聚类的准则----归一化切割 • 定义图G中每个点 的有效性指标: 越高表示第i个点与其他节点的相似性越高,它 越低意味着它是一个孤立点。 • 给定一个聚类A,A中所有点的总有效值测量指标为 V(A)被认为是A的容量或度 • 聚类A与B之间的归一化切割定义为 (,) (,)(,) () () cut A B cut A BNcut A B VA VB=+ ivV∈ (, )ii jV D Wij ∈ = ∑ iiD , () (,)ii iA iAjV VA D Wij ∈∈∈ ==∑ ∑ 如何最小化Ncut 83 七、谱聚类算法 ♦ 谱聚类策略 • 定义 12 1 ,() 1 ,() [, ,...,] i N iAVAy iBVB yyyy ⎧ ∈⎪⎪= ⎨ ⎪− ∈⎪⎩ = 22 11 11 22 22 ()(,)||||(,) (, ) (, ) 2 (, ) 2(,) 2 NN NN Lij ij ii ii ij ij ij ji ij iii jjj ij ij ij T EyyWijyyWij yWijyWij yyWij yD yD yyWi j yLy LDW == == =− =− =+− =+− = ≡− ∑∑ ∑∑ ∑∑ ∑∑ ∑∑ ∑∑ ∑∑ 其中, ,称为图的拉普拉斯矩阵 每个 可以被认为 是 的聚类指示 Nixi ...2,1= iy 84 七、谱聚类算法 ♦ 谱聚类策略 22111()(,)( )(,)2()() T ij iV jV i Aj B y LyyyWij cut A BVA VB∈∈ ∈∈ =− = +∑∑ ∑∑ 22 22 11() ()() () 11 () () T iii jjj iA jB y DyyD y DVAVBVA VB CVA VB ∈∈ =+ = + =+= ∑∑ (,)Ncut A B 最小化相当于 最小化,且约束条件是:TyLy Ty Dy C= 85 七、谱聚类算法 ♦ 谱聚类策略 作如下变量代换,定义: 这里, 称为归一化图的拉普拉斯矩阵 此时,最优问题转换为:最小化 ,约束是 利用拉格朗日乘子法,得无约束准则函数 上式取最小值时,其梯度为零,得: 即: 1/2 1/2 1/2,zDy LD LD−−==和 L Tz Lz Tz zC= ()TTfzLzzzCλ= −− 22 0f Lz zz λ∂ = −=∂ Lzzλ= 86 七、谱聚类算法 ♦ 谱聚类策略 由于 是对称的、非负定的,根据矩阵论可知,它所有的特 征值都是非负的,且特征向量都是相互正交的。 当时, 即最小的特征值 ,它对应的特征向量为 1/2 1/2 1/2 1/2 1/211()10LD D LD D D D W−− −= =−= L 0 0λ = 1/2 1z D= 1/2 1z D= 1/2 , 1, 1, 1,2...iz Dy y y i N=∴=== ∵ 即: 意味着所有的点都映射到同一点,从图上说至少有一条路径连 接到任一一对顶点 可以取第2小的特征值,其对应的特征向量可最小化 Tz Lz 87 七、谱聚类算法 ♦ 谱聚类实现思路 •用图描述特征空间的样本, •用相似矩阵描述样本间的空间关系 •获得归一化图的拉普拉斯矩阵 •找到该矩阵的第二小特征值,然后用相应特征向量 做图的割 •根据特征向量的每个元素是否大于零来确定聚类 88 七、谱聚类算法---- 谱聚类算法步骤 89 七、谱聚类算法---- 谱聚类算法结果 -8 -4 0 4 8 -6 -2 2 6 x1 x2 -8 -4 0 4 8 x1 -6 -2 2 6 x2 -6 -2 2 6 x2 -8 -4 0 4 8 x1()b ()c ()a (a)数据集 (b)谱聚类算法结果 (c)K均值算法结果 90 七、谱聚类算法---- 谱聚类算法优点 1)只需要数据的相似度矩阵。不过一般W并不总是等于 最初的相似度矩阵, 是我们构造出来的 Graph 的邻接矩阵 表示,通常我们在构造 Graph 的时候为了方便进行聚类, 更加强到“局部”的连通性,亦即主要考虑把相似的点连接 一起,比如,我们设置一个阈值,如果两个点的相似度小 这个阈值,就把他们看作是不连接的。 2)抓住了主要矛盾,忽略了次要的东西,性能比传统的 K-means 要好。实际上 Spectral Clustering 是在用特征向量 的元素来表示原来的数据,并在这种“更好的表示形式”上 行 K-means 。实际上这种“更好的表示形式”是用 图的拉普 拉斯矩阵进行降维后的结果,而降维的目的正是“抓住主要 矛盾,忽略次要的东西” 91 七、谱聚类算法---- 谱聚类算法优点 3)计算复杂度比 K-means 要小。这个在高维数据上表现尤为 明显。例如文本数据,通常排列起来是维度非常高(比如,几 千或者几万)的稀疏矩阵,对稀疏矩阵求特征值和特征向量有 很高效的办法,得到的结果是一些 k 维的向量(通常 k 不会很 大),在这些低维的数据上做 K-means 运算量非常小。但是对 于原始数据直接做 K-means 的话,虽然最初的数据是稀疏矩 阵,但是 K-means 中有一个求 类心的运算,就是求一个平均 值:许多稀疏的向量的平均值求出来并不一定还是稀疏向量, 事实上,在文本数据里,很多情况下求出来的 类心向量是非常 稠密,这时再计算向量之间的距离的时候,运算量就变得非常 大,直接影响了普通的 K-means 算法速度,而谱聚类算法虽然 步骤多,但其速度却快得多。

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 15 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

goooodday

贡献于2011-07-25

下载需要 15 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf