k均值聚类精选.ppt

K-means算法研究K值优化 目录 相关概念 基本思想 算法步骤 K值优化 聚类 聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程，聚类就是一种发现这种内在结构的技术，聚类技术经常被称为无监督学习。 K-均值聚类又称为C-均值聚类,是根据函数准则进行分类的聚类算法, 使聚类准则函数最小化. 基本思想 其基本思想是：通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。 K-均值聚类算法准则函数 聚类集中每个样本点到该类聚类中心的距离平方和,对于第j个聚类集,准则函数定义为 其中Sj表示第j个聚类集,聚类中心为Zj；Nj为第j个聚类集Sj中包含的样本数。 对所有K个模式类有 K-均值聚类算法准则函数 聚类中心Zj的选择应使准则函数J极小,也就是使得Ji的值极小,要满足这一点,应有 ,即 解得 上式表明，Sj类的聚类中心应选为该类样本的均值。 K-均值聚类算法步骤 设共有N个模式样本,计算步骤如下: (1)任选K个初始聚类中心Z1(l)Z2(l)..Zk(l),KN。 括号内的序号代表了寻找聚类中心的迭代运算的次序号。一般可选择样本集中前K个样本作为初始聚类中心。 (2)按最小距离原则将其余样本分配到K个聚类中心中的某一个中心所对应的类别中，即如果 . 其中K为迭代运算的次序号,若第一次迭代则K代表了聚类中心的个数. K-均值聚类算法步骤 (3) 计算各个中心的新向量值Zj(k+1), j=1,2..K.即均值向量作为新的聚类中心.这一步要分别计算K个聚类中的样本均值向量,故该算法称为K-均值算法. (4) 如果 ,则回到步骤(2),将样 本逐个重新分配,并重复迭代计算；如果Zj(k+1)=Zj(k),j=1,2..K,算法收敛,计算完毕. 聚类示意图（二维） K-均值聚类 Bandyopadhyay 等提出了基于遗传算法的GCUK 算法。该算法的染色体采用字符串方式编码， 即将每一个初始聚类中心的坐标按顺序编码，没有作 为初始聚类中心的数据点则以符号“#”表示，编码完 成后在逐代交叉中最终得到最佳的 K 值。 该算法的缺 点是染色体的字符串表示方法大大增加了算法的开销。为了解决该问题，Lin 等采用了二进制方式进 行染色体编码。该编码方案采用染色体长度作为数据 集的大小，被选为初始聚类中心的数据点编码为 1，否则为 0。 Liu 等在此基础上提出了 AGCUK 算法，在染色 体编码时为每一个染色体选用 K × m 个基因( K 为随 机选取的聚类数目，m 为数据点的维度) ，前 m 个基因 表示第一个初始聚类中心的坐标，接着 m 个基因表示 第二个初始聚类中心的坐标，以此类推完成编码， 此外，在遗传过程中 算法还运用了最佳个体保留法，把具有最高适应度的个体不经交叉直接遗传到下一代，最终即可得到最佳的K值。 而巩敦卫等在 Merwe 的研究基础上提出了一种基于微粒群的优化算法。微粒群优化算法是一种群智能优化算法，其算法思想类似于 遗传算法，由 Merwe 等首次将其运用于聚类。 首先初始化微 粒群，随机产生一个 K 值，这个K 值在［2，根号N］区 间 内。随机选取 K 个初始聚类中心，按照事先确定的微 粒编码方式编码并在微粒群上运行 K-means 算法，更 新微粒的编码结构以及微粒的速度和位置。在算法中引入了一种不同于传统微粒群优化算法的微粒更新运算，即通过新定义的 + 、－ 运算可以动态改变此前随机 选取的 K 值，随后逐代迭代以上步骤，最终使目标函数收敛。 综合上述研究可以发现，学界已经提出了多种 K值选取方法，并分别基于不同的思想。基于聚类有效 性函数的解决方法算法思想简单，但是需要付出较大 的时间开销，遗传算法作为一种优秀的优化算法，应用 于 K 值的确定是十分有效的。 谢谢观赏 * *