k均值介绍了k均值算法是聚类分析中使用最广泛的算法之一。 它根据属性将n个对象分成k个群集,以使得到的群集得到满足。 同一簇内对象相似度高; 不同聚类中的对象相似度很小。 其聚类过程可以用下图表示。
如图所示,数据样本用圆点表示,各聚类的中心点用叉子表示。 ) a )最初是原始数据,杂乱无章,没有标签,看起来都一样,是绿色的。 ) b )假设数据集可以分为K=2两类,在坐标上随机选取两点,作为两个类的中心点。 给出了c-f )聚类的两次迭代。 首先,将每个数据样本划分为最近的中心点群集完成划分后,更新每个群集的中心。 也就是说,将该群集中所有数据点的坐标相加并平均。 这样,继续“拆分-更新-拆分-更新”,直到每个群集的中心不再移动。
求中心点距离一般采用日光之狼算法计算。
k均值算法的缺陷**聚类中心的个数k需要事先给出,但实际上该k值的选定非常难推定,很多情况下事先不知道将给定的数据集分为几个类别是最佳的,k均值是人工决定初始聚类中心的可以用Kmeans算法解决) **针对上述第二缺陷,用Kmeans算法可以解决的**K-Means算法**K-Means算法选择初始seeds的基本想法是,对初始的簇从输入的数据点集合中随机选择一个点作为第一个簇中心,计算数据集中每个点x的最近簇中心指向选定簇中心)的距离d ) x,然后选择新的数据点作为新的簇中心选择原则是: D ) x )较大的点更有可能被选为簇中心,重复2和3以选择k个簇中心。 通过对使用k个初始分簇中心执行标准k均值算法的算法的描述可以看到,该算法的关键是如何在步骤3中,在选择点的概率上反映dx )。 一个算法如下。 首先,从我们的数据库中选择一个随机点作为“种子点”,计算并保存每个点与最近的“种子点”的距离D ) x ),然后再取一个随机值,加权后取下一个“种子点” 该算法首先取落入sumd ) x ) )的随机值Random,然后使用random-=d ) x ),直到其)=0。 此时的点成为下一个“种子点”。 重复2和3以使用这k个初始集群中心运行标准k均值算法,直到选择了k个集群中心