模式识别中的常见聚类算法.ppt

聚类问题的描述（1）第2页,共27页，星期六，2024年，5月聚类问题的描述（2）聚类问题：根据给定的数据集，要求寻找T上的一个“好”的划分(划分成m个类；m可以是已知的，也可以是未知的），满足约束条件：第3页,共27页，星期六，2024年，5月聚类问题的描述（3）模糊聚类问题：根据给定的数据集，要求寻找T上的一个“好”的模糊划分(划分成m个模糊集），满足约束条件：模糊聚类问题可以看成是前面聚类问题（硬聚类）的一个推广，当uj的值域限制为{0,1}时，模糊聚类就是硬聚类.第4页,共27页，星期六，2024年，5月聚类问题的要点样本间的接近度（ProximityMeasures）聚类评价准则：“好”的聚类指什么？聚类算法聚类有效性检验（统计假设检验）聚类结果解释（结合专家知识）聚类的泛化能力或一致性或抗扰动能力第5页,共27页，星期六，2024年，5月样本间的接近度度量差异性度量（DissimilarityMeasure,DM）对称性自己与自己的差异性最小例子：距离差异性度量相似性度量（SimilarityMeasure，SM）对称性自己与自己的相似性最大例子：高斯径向基函数第6页,共27页，星期六，2024年，5月常用的接近度度量点与点之间点与集合之间集合与集合之间第7页,共27页，星期六，2024年，5月点与点之间——DM第8页,共27页，星期六，2024年，5月点与点之间——SM第9页,共27页，星期六，2024年，5月点与集合之间第10页,共27页，星期六，2024年，5月集合与集合之间第11页,共27页，星期六，2024年，5月聚类评价准则类内样本间的接近度大，类间样本间的接近度小…………第12页,共27页，星期六，2024年，5月主要聚类算法(1)N个样本聚为m类的可能聚类数S(N,m):S(15,3)=2375101;S(20,4)=45232115901S(25,8)=690223721118368580;S(100,5)≈1068枚举聚类是行不通的！第13页,共27页，星期六，2024年，5月主要聚类算法(2)顺序聚类（SequentialCluteringAlgorithms）分层聚类（HierachicalCluteringAlgorithms）模型聚类（basedoncostfunctionoptimization)其他第14页,共27页，星期六，2024年，5月顺序聚类最基本的顺序聚类算法（1）第1个样本归为第1类；（2）计算下一个样本到己有类的最短距离，若其距离小于给定的域值，则将该样本归为其对应的类，否则增加一个新类，并将该样本归为新类。（3）重复（2），直到所有样本都被归类。特点聚类结果与样本的顺序和给定的域值有关；聚类速度快第15页,共27页，星期六，2024年，5月分层聚类将数据对象按层次进行分解，形成一个分层的嵌套聚类(聚类谱系图或聚类树状图)，可分为凝聚算法（AgglomerativeAlgorithms）开始将每个对象作为一个类，然后相继地合并上轮中最相近的两个类，直到所有的类合并为一个类或者达到某个终止条件。分裂算法（DivisiveAlgorithms）开始将所有对象置于一个类中；然后将上轮的每个类按某个准则分裂为两类，在从中选择其中最好的一个分裂，作为该轮的类分裂；直到每个对象都在单独的一个类中或达到某个终止条件。缺点在于一旦一个合并或分裂完成，就不能撤销，导致分层聚类方法不能更正错误的决定。第16页,共27页，星期六，2024年，5月分层（凝聚）聚类的一些结论聚类结果和样本点间距离函数以及类间距离函数的关系：一般来讲，最短距离法使用于长条状或S形的类，最长距离法，重心法，类平均法，离差平方和法适用于椭球型的类。我们用Dk表示第k次并类操作时的距离，如果一个系统聚类法能够保证{Di}是单调上升的，那么我们称之为具有单调性。可以证明，最短距离法，最长距离法，类平均法，离差平方和法具有单调性，重心法和中间距离法不具有单调性。从聚类谱系图中可以看出，不具有单调性表现为出现一个凹陷，并且不容易划分类。第17页,共27页，星期六，2024年，5月分层（凝聚）聚类的一些结论有人从极端距离矩阵的观点出发，认为相比于其他方法，类平均法既不太浓缩，也不太扩张，比较适中；因而从空间的浓缩和扩张的角度，他们推荐类平均法。有人证明与初始距离矩阵A最接近的极端距离矩阵，恰好是使用最短距离法得到的极端距离矩