K-means.md

引入K-means思想

• 牧师-村民模型

• 有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的村民，于是每个村民到离自己家最近的布道点去听课。听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的村民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。 牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个村民又去了离自己最近的布道点…… 就这样，牧师每个礼拜更新自己的位置，村民根据自己的情况选择布道点，最终稳定了下来

• 牧师的做法主要就是为了找到一个点/这个点接近于所有村民的一个中心点

算法表述

• 初始化k个样本作为初始的聚类中心点
• 对于数据集合中的每一个样本计算他到k个聚类中心的距离/然后选择距离最小的聚类中心所在的类别
• 对于上一部聚类的结果,进行平均计算,得出该类别的新的聚类中心
• 重复上述两步/直到迭代结束

优缺点

• 优点
  • 当样本空间是高斯分布的时候/效果较好
  • 时间复杂度低
  • 简单容易/效果也还可以
• 缺点
  • K值设定玄学
  • 初试簇的选择对结果会有影响
  • 不适合多分类
  • 对异常值敏感/出现异常值会极大影响整个算法

使用sklearn进行简单演示

from sklearn.cluster import KMeans
import numpy as np
X = np.array([[1, 2], [1, 4], [1, 0],
               [4, 2], [4, 4], [4, 0]])
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
kmeans.labels_
>>>array([0, 0, 0, 1, 1, 1], dtype=int32)
kmeans.predict([[0, 0], [4, 4]])
>>>array([0, 1], dtype=int32)
kmeans.cluster_centers_
array([[ 1.,  2.],
       [ 4.,  2.]])