从前有一群猴子,过着简单而快乐的生活。有一天,其中两只猴子因为小事争吵起来,最终一发不可收拾,两个猴子势不两立。从此这两只猴子就开始拉帮结派,把觉得和自己合的来的拉到一起,于是猴群分裂成了两拨。第一拨的猴子里面,带头的猴子统治得很顺利,第二拨猴子里面,突然又有一只猴子雄起了,打败了原来的猴王(见图10-1),成为了新的猴王,最终猴群的派系和管理层都稳定了下来,划分成了两拨猴子,完成了聚类。这其实就是个K-Means算法的案例。
K-Means算法是最为经典的基于划分的聚类方法,它的中心思想是,以空间中k个点为中心进行聚类,通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果。简单描述上面提到的猴子拉帮结伙的步骤为:
·首先,从n个数据对象任意选择k个对象作为初始聚类中心;而对于所剩下的其他对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类。
·然后,再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值)。
·不断重复这一过程直到标准测度函数开始收敛为止。
图10-1 猴子争霸
可视化这一过程如图10-2所示。
图10-2 K-Means算法过程演示图