文档介绍：会计学
1
基于划分的聚类算法
聚类分析
簇（Cluster）:一个数据对象的集合
聚类分析（定义）
把一个给定的数据对象集合分成不同的簇；
在同一个簇（或类）中，对象之间具有相似性；
不同簇（或类）的对象之间是相异的。
聚类是一种无监督分类法: 没有预先指定的类别
第1页/共19页
聚类方法
划分方法：给定一个n个对象的集合，划分方法构建数据的k个分区，其中每个分区表示一个簇，并且k<=n。基于划分方法采取互斥的簇划分，即每个对象必须恰好属于一个组。大部分划分方法是基于距离的。它采用一种迭代的重定位技术，通过把对象从一个组移动到另一个组来改变划分。常用的划分聚类方法有k-means、k-medoids、k-modes和k-prototypes算法。
层次方法、基于密度的方法、基于网格的方法
第2页/共19页
K-means:K-均值算法
K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。
该算法认为类是由距离靠近的对象组成的，因此把得到紧凑且独立的类作为最终目标。
各个簇中误差平方和
n：样本数。 k：样本分为k类。
rnk：第n个样本点是否属于第k类，属于则rnk=1，不属于则rnk=0。 μK：第k个中心点。
第3页/共19页
K-means:K-均值算法
给定k，算法的处理流程如下:
；
，并用该平均值代表相应的簇；
，重新分配到与它最近的簇中；
，直到不再有新的分配发生。
第4页/共19页
K-均值算法
第5页/共19页
K-均值算法性能
优点
相对高效的: 算法复杂度O(tkn), 其中n 是数据对象的个数, k 是簇的个数, t是迭代的次数，通常k, t << n.
算法通常终止于局部最优解；
缺点
只有当平均值有意义的情况下才能使用（即只能处理数值的属性），对于类别字段不适用；
必须事先给定要生成的簇的个数；
对“噪声”和异常数据敏感；
不能发现非凸面形状的数据。
第6页/共19页
不同初始点，结果不同。
第7页/共19页
K-means算法，我们在输入的数据集中随机的选择k个点作为初始的聚类中心，但是随机选择初始点可能会造成聚类的结果和数据的实际分布相差很大。k-means++算法选择初始聚类中心的基本思想是：初始的聚类中心之间的相互距离要尽可能的远。K-means算法与k-means++算法选取初始点对比：
K-means k-means++
第8页/共19页
K-modes：K-众数算法
标称属性即分类的，变量结果只在有限目标集中取值
相关性d的计算公式是比较两记录之间所有属性，如果属性不同则给d加1,如相同则不加，所以d越大，记录间的不相关程度越强。假设X，Y是数据集中的两个对象，它们用m维属性描述，则这两个对象之间的相异度为：
更新modes,使用一个簇的每个属性出现频率最大的那个属性值作为代表簇的属性值（如{[a,1][a,2][b,1][a,1][c,3]}代表模式为[a,1]）
重新调整记录所属的簇，知道不再产生变化。
第9页/共19页