D-thinker系统Kmeans性能测试

k-means 算法随机选择k个点作为种子点,之后将数据集中n个数据对象通过与K个种子点求距离来划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高,而不同聚类中的对象相似度较小。也就是一个对象到其所属聚类的种子点的距离是最>小的。
聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。
K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果。
假设要把样本集分为c个类别,算法描述如下:
(1)适当选择c个类的初始中心;
(2)在第k次迭代中,对任意一个样本,求其到c各中心的距离,将该样本归到距离最短的中心所在的类;
(3)利用均值等方法更新该类的中心值;
(4)对于所有的c个聚类中心,如果利用(2)(3)的迭代法更新后,值保持不变,则迭代结束,否则继续迭代。
该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

以下实验结果是在迭代次数预先定义为20次。其中tiny类型表示点集数目为10个,质心点两个; small表示点数目为512*1024,质心点20个。
large表示点数目为20480000,质心点1000个。

tiny数据运行时间对比图:

small数据运行时间对比图:

large数据运行时间对比图: