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