基于划分的聚类算法.pptVIP

基于划分的聚类算法 黄宗文聚类分析 簇（Cluster）:一个数据对象的集合 聚类分析（定义） 把一个给定的数据对象集合分成不同的簇； 在同一个簇（或类）中，对象之间具有相似性； 不同簇（或类）的对象之间是相异的。 聚类是一种无监督分类法: 没有预先指定的类别 聚类方法 划分方法：给定一个n个对象的集合，划分方法构建数据的k个分区，其中每个分区表示一个簇，并且k=n。基于划分方法采取互斥的簇划分，即每个对象必须恰好属于一个组。大部分划分方法是基于距离的。它采用一种迭代的重定位技术，通过把对象从一个组移动到另一个组来改变划分。常用的划分聚类方法有k-means、k-medoids、k-modes和k-prototypes算法。 层次方法、基于密度的方法、基于网格的方法 K-means:K-均值算法 K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。 该算法认为类是由距离靠近的对象组成的，因此把得到紧凑且独立的类作为最终目标。 各个簇中误差平方和 n：样本数。 k：样本分为k类。 rnk：第n个样本点是否属于第k类，属于则rnk=1， 不属于则rnk=0。 μK：第k个中心点。 K-means:K-均值算法 给定k，算法的处理流程如下: 1.随机的把所有对象分配到k个非空的簇中； 2.计算每个簇的平均值，并用该平均值代表相应的簇； 3.将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中； 4.回到第二步，直到不再有新的分配发生。 K-均值算法 K-均值算法性能 优点 相对高效的: 算法复杂度O(tkn), 其中n 是数据对象的个数, k 是簇的个数, t是迭代的次数，通常k, t n. 算法通常终止于局部最优解； 缺点 只有当平均值有意义的情况下才能使用（即只能处理数值的属性），对于类别字段不适用； 必须事先给定要生成的簇的个数； 对“噪声”和异常数据敏感； 不能发现非凸面形状的数据。 不同初始点，结果不同。 K-means算法，我们在输入的数据集中随机的选择k个点作为初始的聚类中心，但是随机选择初始点可能会造成聚类的结果和数据的实际分布相差很大。k-means++算法选择初始聚类中心的基本思想是：初始的聚类中心之间的相互距离要尽可能的远。K-means算法与k-means++算法选取初始点对比： K-means k-means++ K-modes：K-众数算法 标称属性即分类的，变量结果只在有限目标集中取值 相关性d的计算公式是比较两记录之间所有属性，如果属性不同则给d加1,如相同则不加，所以d越大，记录间的不相关程度越强。假设X，Y是数据集中的两个对象，它们用m维属性描述，则这两个对象之间的相异度为： 更新modes,使用一个簇的每个属性出现频率最大的那个属性值作为代表簇的属性值（如{[a,1][a,2][b,1][a,1][c,3]}代表模式为[a,1]） 重新调整记录所属的簇，知道不再产生变化。 K-prototypes算法 K-Prototype算法是结合K-Means与K-modes算法，针对混合属性的。解决两个核心问题如下： 度量具有混合属性的方法是，数值属性采用K-means方法得到P1，分类属性采用K-modes方法P2，那么D=P1+a*P2,a是权重。如果觉得分类属性重要，则增加a，否则减少a,a=0时即只有数值属性； 更新一个簇的中心的方法，是结合K-Means与K-modes的更新。 K-medoids:K-中心点算法 不采用聚类中对象的平均值作为参照点，而是选用聚类中位置最中心的对象，即中心点（medoid）作为参照点 首先随机选择k个对象作为中心，把每个对象分配给离它最近的中心 然后随机地选择一个非中心对象替换中心对象，计算分配后的距离改进量。聚类的过程就是不断迭代，进行中心对象和非中心对象的反复替换过程，直到目标函数不再有改进为止。 K- medoids算法流程如下：1、任意选取K个对象作为初始中心点（O1,O2,…Oi…Ok）。　　2、将余下的对象分到各个类中去（根据与中心点最相近的原则）；　　3、对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。这样K个中心点就改变了。 其中：p是空间中的样本点， oj是类簇 cj 的中心点。 4、重复2、