k-means算法.ppt

1、刘奕铮,K-means算法,1,Propagation model,个人总结,2,Propagation model,聚类,聚类定义,聚类的思想和“物以类聚”相似，根据某一种聚类准则将数据对象划分为多个簇，使得同一簇中的数据对象特征尽可能相同，不同簇间的数据对象特征尽可能不同。,聚类形式表述,给定一个数据集X： = 1, 2 ，其中N为数据集中的数据个数，对数据集X聚类就是按照相似度将X中N个数据划分为k个簇1, 2，表述第i个簇。,3,Propagation model,聚类,聚类分析相似度度量,设X=x1，x2，,xn为m维空间中的一组对象，xi、xj是X中的两个对象，d（ xi，xj ）

2、是xi和xj之间的距离。,该距离应满足以下性质：,非负性：距离是一个非负的数值，即d（ xi，xj ）0,最小性：即一个对象与自身的距离是0,对称性：即对于任意对象xi，xj ，恒有 d（ xi，xj ）= d（ xj ，xi）,4,Propagation model,聚类,常用的距离公式,明科夫斯基距离：,曼哈顿距离：,欧式距离：,5,Propagation model,聚类,聚类效果评价准则,K-means 算法的聚类结果评价方法通常采用误差平方和准则函数，目标是使该函数值尽量小。,设数据集为样本集X： X=x1，x2，,xn，根据相似度，该数据集被划分为k簇，其中，1ik，第1至第k簇包

3、含的样本数分别为n1，n2，nk，k个簇中的样本数总和为n且每簇中至少包含一个样本。假设每个簇的中心点为mi，其中1ik，则误差平方和准则函数定义如下：,6,Propagation model,个人总结,7,Propagation model,传统K-means算法,传统K-means算法流程,(1)从给定样本数据集中随机选取 k 个数据点作为初始聚类中心 ； (2)计算数据集中每个数据到这 k 个聚类中心的距离并将每个数据点分配给离它最近的中心点所代表的簇； (3) 计算每个簇中所有数据点的平均值作为每个簇新的中心； (4) 判断聚类准则函数是否收敛或聚类中心点和上次是否完全相同，若收敛或中

4、心点无变化，则算法结束，输出聚类结果，否则转到步骤(2)。,8,Propagation model,传统K-means算法,算法例子,已知一个数据对象集合X=x1，x2，x3，x4，x5，x6，各数据对象的值如下所示，现要求将X划分为2类，即k=2。,首先随机选择两个点作为初始聚类中心，在这里我们选择3 和6分别作为1和2两个簇的初始聚类中心。然后计算1 到 3 和 6 的欧式距离。,9,Propagation model,传统K-means算法,算法例子,重新计算簇 1, 2 中数据对象的均值作为它们新的聚类中心：,根据计算可知，1 距离 3 比距离 6 更近，所以应将 1 划分到 3所表示

5、的簇 1 中，同理将 2, 3, 5 划分到簇 1 中，将 4, 6, 7, 8 划分到簇 2 中。,1= 1, 2, 3, 5 2= 4, 6, 7, 8,10,Propagation model,传统K-means算法,算法优点,K-means 算法在处理大数据集时效率非常高且具有较强的鲁棒性，不仅可以处理数值形式的数据集，而且还适用于文本和图像特征的情况。 在聚类过程中所有数据对象要和聚类中心点计算距离而归类。所以不会因为数据的读入顺序的差异而对聚类结果造成很大的影响。 K-means 算法对聚类的范围没有什么特别的限制，这一优点非常有利于在实际中应用。,11,Propagation m

6、odel,传统K-means算法,算法缺点,初始聚类中心选择 K值的选取 算法易陷入局部最优解 噪声和孤立点的干扰 循环执行数据再操作,12,Propagation model,个人总结,13,Propagation model,改进K-means算法,初始聚类中心选取,基本思想：基于各数据点到原点的距离，均匀的选择 k 个数据点作为初始聚类中心。,14,首先检查所有属性值是否为负值。 对于每个包含负值的属性，找出该属性的最小值。 在每个包含负值的属性值上减去该属性的最小值。 计算每个数据点到原点的距离。 将所有距离从小到大排序。 将排好序的数据点平均分为 k 组。 在每一组中，选取中间的数据

7、点作为初始聚类中心。 计算每个数据点到k个中心点的距离(,),其中 1 。,Propagation model,改进K-means算法,算法例子,已知一个数据对象集合X=x1，x2，x3，x4，x5，x6，各数据对象的值如下所示，现要求将X划分为2类，即k=2。,对于每个包含负值的属性，找出该属性的最小值；为数据集中的每个数据点，在每个包含负值的属性值上减去该属性的最小值。,15,Propagation model,改进K-means算法,算法例子,利用欧式距离公式计算各点到原点距离。,由计算结果可知，数据集中数据点按与原点的距离排序是：2, 4, 5, 1, 6, 3，将其平均分为两组即是：

8、2, 4, 5 和 1, 6, 3 ，取各组的中间数据点作为初始聚类中心，在这里是4 和6。,16,Propagation model,改进K-means算法,数据对象分配,选取好初始聚类中心后，接下来就是将数据集中的数据点分配到合适的簇中。Cluster 和 MinDis，分别代表该数据点所属的簇和当前离最近聚类中心点的距离。,17,对于每个数据点 ，找到离它最近的中心点 ，并将 分配给簇 j； 将该数据点的 Cluster 值设置为 j； 将该数据点的 MinDis 值设置为（, ）； 重新计算每个簇的中心点； 对于每个数据点 ，计算它和现在所在簇的中心点的距离；如果这个距离小于等于目前最

9、短距离，数据点留在该簇中不变；否则对于每个中心点 , (1 ) ，计算 到数据点 的距离 （, ）。,Propagation model,改进K-means算法,K值学习算法,K值学习算法是一个结合遗传算法来确定聚类数k值的算法。,18,（1）编码方式,每个编码即一个染色体代表问题的一个解，也就是k值的大小。本算法中选用8位二进制编码方式。,二进制串,十进制数,K值,例如染色体1= 00000110，它所代表的聚类数 k 为 5。,Propagation model,改进K-means算法,K值学习算法,K值学习算法是一个结合遗传算法来确定聚类数k值的算法。,19,（2）初始种群的确定,在 1

10、, 之间随机生成一个数 ； 生成一条染色体，即一个个体，使其编码串的值等于 ； 重复前两个步骤，直至生成的个体数目等于种群数目大小。,Propagation model,改进K-means算法,K值学习算法,K值学习算法是一个结合遗传算法来确定聚类数k值的算法。,20,（3）适应度函数构造,适应度函数构造为：,最小簇间距D为：,平均簇内距C（x）为：,Propagation model,改进K-means算法,K值学习算法,K值学习算法是一个结合遗传算法来确定聚类数k值的算法。,21,（4）遗传操作,选择算子 交叉算子 变异算子,Propagation model,改进K-means算法,K值学习算法流程,根据设定的最大聚类数随机生成包含若干个体的初始种群。 运用K-means算法进行聚类，计算适应度f。 对种群进行选择、交叉、变异操作形成新一代种群，对新种群计算适应度值，判断是否满足终止条件。 如果满足，则算法终止，输出最优个体，它的值即是最佳聚类数k；如果不满足，则重复上述遗传操作形成新种群以搜索更好个体。,22,Propagation model,改进K-means算法,K值学习算法终止条件,(1) 由用户指定最大进化代数，算法达到这个值时即结束；,23,(2) 种群