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

模式识别中的常见聚类算法,赵英刚整理,聚类问题的描述（1）,聚类问题的描述（2）,聚类问题：根据给定的数据集，要求寻找T上的一个“好”的划分(划分成m个类；m可以是已知的，也可以是未知的），满足约束条件：,聚类问题的描述（3）,模糊聚类问题：根据给定的数据集，要求寻找T上的一个“好”的模糊划分(划分成m个模糊集），满足约束条件：,模糊聚类问题可以看成是前面聚类问题（硬聚类）的一个推广，当uj的值域限制为0,1时，模糊聚类就是硬聚类.,聚类问题的要点,样本间的接近度（ProximityMeasures）聚类评价准则：“好”的聚类指什么？聚类算法聚类有效性检验（统计假设检验）聚类结果解释（结合专家知识）聚类的泛化能力或一致性或抗扰动能力,样本间的接近度度量,差异性度量（DissimilarityMeasure,DM）对称性自己与自己的差异性最小例子：距离差异性度量相似性度量（SimilarityMeasure，SM）对称性自己与自己的相似性最大例子：高斯径向基函数,常用的接近度度量,点与点之间点与集合之间集合与集合之间,点与点之间DM,点与点之间SM,点与集合之间,集合与集合之间,聚类评价准则,类内样本间的接近度大，类间样本间的接近度小,主要聚类算法(1),N个样本聚为m类的可能聚类数S(N,m):,S(15,3)=2375101;S(20,4)=45232115901S(25,8)=690223721118368580;S(100,5)1068枚举聚类是行不通的！,主要聚类算法(2),顺序聚类（SequentialCluteringAlgorithms）分层聚类（HierachicalCluteringAlgorithms）模型聚类（basedoncostfunctionoptimization)其他,顺序聚类,最基本的顺序聚类算法（1）第1个样本归为第1类；（2）计算下一个样本到己有类的最短距离，若其距离小于给定的域值，则将该样本归为其对应的类，否则增加一个新类，并将该样本归为新类。（3）重复（2），直到所有样本都被归类。特点聚类结果与样本的顺序和给定的域值有关；聚类速度快,分层聚类,将数据对象按层次进行分解，形成一个分层的嵌套聚类(聚类谱系图或聚类树状图)，可分为凝聚算法（AgglomerativeAlgorithms）开始将每个对象作为一个类，然后相继地合并上轮中最相近的两个类，直到所有的类合并为一个类或者达到某个终止条件。分裂算法（DivisiveAlgorithms）开始将所有对象置于一个类中；然后将上轮的每个类按某个准则分裂为两类，在从中选择其中最好的一个分裂，作为该轮的类分裂；直到每个对象都在单独的一个类中或达到某个终止条件。缺点在于一旦一个合并或分裂完成，就不能撤销，导致分层聚类方法不能更正错误的决定。,分层（凝聚）聚类的一些结论,聚类结果和样本点间距离函数以及类间距离函数的关系：一般来讲，最短距离法使用于长条状或S形的类，最长距离法，重心法，类平均法，离差平方和法适用于椭球型的类。我们用Dk表示第k次并类操作时的距离，如果一个系统聚类法能够保证Di是单调上升的，那么我们称之为具有单调性。可以证明，最短距离法，最长距离法，类平均法，离差平方和法具有单调性，重心法和中间距离法不具有单调性。从聚类谱系图中可以看出，不具有单调性表现为出现一个凹陷，并且不容易划分类。,分层（凝聚）聚类的一些结论,有人从极端距离矩阵的观点出发，认为相比于其他方法，类平均法既不太浓缩，也不太扩张，比较适中；因而从空间的浓缩和扩张的角度，他们推荐类平均法。有人证明与初始距离矩阵A最接近的极端距离矩阵，恰好是使用最短距离法得到的极端距离矩阵，而其他的凝聚型分层聚类法都不具有这个最优性质。从这个角度出发，最短距离法比较受到推崇。,模型聚类,K-meansClusteringK-中心点聚类模糊K-均值聚类或ISODATA,K-meansClustering模型,将N个样本x1,xN划分到m个类C1,Cm中，最小化评分函数,这里c1,cm是C1,Cm的质心，是划分到类Cj的样本,K-meansClustering实现,随机选择m个样本点作为m个初始质心c1,cm；按距离最近原则，将所有样本划分到以质心c1,cm为代表的m个类中；重新计算m个类的质心c1,cm；重复（2）和（3）直到质心c1,cm无改变或目标函数J(c1,cm)不减小。,K-meansClustering特点,优点：当类密集，且类与类之间区别明显（比如球型聚集）时，聚类效果很好；强的一致性算法的复杂度是O(Nmt)(t为迭代次数)，对处理大数据集是高效的。缺点：结果与初始质心有关；必须预先给出聚类的类别数m；对“噪声”和孤立点数据敏感，少量的这些数据对平均值产生较大的影响；不适合发现非凸面形状的聚类,K-中心点聚类,避开k-均值聚类对“噪声”和少数孤立点的敏感性，将类中各个对象的平均值（质心）更改为类中各个对象的中心点。但运算代价比k-均值聚类大。,模糊k-均值聚类（ISODATA）,谱聚类,谱聚类,可以看成是特征空间中的聚类问题原空间不具备球型（或椭球型）的聚类问题，可通过映射将其转化为特征空间中的球型（或椭球型）聚类问题,基于密度的方法,Step1:寻找数据集中的核心对象(即其-邻域包含较多对象的对象)p1,pm，形成以这些核心对象为代表的类；Step2:反复寻找从这些核心对象直接密度可达的对象（在核心对象的-邻域中），这期间可能涉及一些密度可达类的合并，该过程直到没有新的点可加入到任何类中时结束。,