k-means 算法 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 一．算法简介 k-means算法，也被称为 k-平均或 k-均值，是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。 二．划分聚类方法对数据集进行聚类时包括如下三个要点： （1）选定某种距离作为数据样本间的相似性度量 k-means聚类算法不适合处理离散型属性，对连续型属性比较适合。因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。 假设给定的数据集 ，X中的样本用 d个描述属性 A1,A2„Ad来表示，并且 d个描述属性都是连续型属性。数据样本 xi=(xi1,xi2,„xid), xj=(xj1,xj2,„xjd)其中，xi1,xi2,„xid和 xj1,xj2,„xjd分别是样本 xi和 xj对应 d个描述属性 A1,A2,„Ad的具体取值。样本 xi和 xj之间的相似度通常用它们之间的距离 d(xi,xj)来表示，距离越小，样本 xi和 xj越相似，差异度越小；距离越大，样本 xi和 xj越不相似，差异度越大。 欧式距离公式如下： （2）选择评价聚类性能的准则函数 |1,2,...,mXxmtotal21,dijikjkkd xxxxk-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集 X，其中只包含描述属性，不包含类别属性。假设 X包含 k个聚类子集 X1,X2,„XK；各个聚类子集中的样本数量分别为 n1，n2,„,nk;各个聚类子集的均值代表点（也称聚类中心）分别为 m1，m2,„,mk。 则误差平方和准则函数公式为： （3）相似度的计算根据一个簇中对象的平均值来进行。 1) 将所有对象随机分配到 k个非空的簇中。 2) 计算每个簇的平均值，并用该平均值代表相应的簇。 3) 根据每个对象与各个簇中心的距离，分配给最近的簇。 4) 然后转 2），重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。...
