K-Means简介
K-Means 是一种非监督学习。
K 代表的是 K 类，Means 代表的是中心，它有点像全自动分类。聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。
主要思想是:在给定K值和K个初始类簇中心点的情况下，把每个点(也就是数据)分到离其最近的类簇中心点所代表的类簇中，所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点（取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。
基本概念
簇
也就是类，假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是些什么。
K
簇个数，是自己给定的，k是多少就有多少个簇。
质心
均值，即向量各维取平均，即簇中所有点的中心来描述。
距离的度量
常用欧氏距离 ( x 2 + y 2 ) \sqrt{x^2+y^2} ) x2+y2 )和余弦相似度（通过测量两个向量的夹角的余弦值来度量它们之间的相似性）,大多情况下都要先标准化
欧氏距离
假定给定数据样本X，包含了n个对象 X = { X 1 , X 2 , X 3 , . . . , X n } X =\lbrace X_1 , X_2 , X_3 , . . . , X_n \rbrace X={X1,X2,X3,...,Xn},其中每个对象都具有m个维度的属性。Kmeans算法的目标是将n个对象依据对象间的相似性聚集到指定的k个类簇中，每个对象属于且仅属于一个该对象到类簇中心距离最小的类簇中。
对于Kmeans，首先需要初始化k个聚类中心 { C 1 , C 2 , C 3 , . . . , C k } \lbrace C_1,C_2,C_3,...,C_ k \rbrace {C1,C2,C3,...,Ck}，然后通过计算每一个对象到每一个聚类中心的欧式距离，如下式所示：
d i s ( X i , C j ) = ∑ t = 1 m ( X i t − C i t ) 2 dis(X_i,C_j)=\sqrt{\sum_{t=1}^m (X_{it}-C_{it})^2} dis(Xi,Cj)=t=1∑m(Xit−Cit)2
上式中 X i X_i Xi表示第i个对象 1 ≤ i ≤ n 1\leq i \leq n 1≤i≤n
C j C_j Cj表示第j个聚类中心的 1 ≤ j ≤ k 1\leq j \leq k 1≤j≤k
X i t X_{it} Xit表示第i个对象的第t个属性 1 ≤ t ≤ m 1\leq t \leq m 1≤t≤m 表示第j个聚类中心的第t个属性。
比如一组对象是三维空间的许多点，其中一点a具体表示为(
a
1
,
b
1
,
c
1
a_1,b_1,c_1
a1,b1,c1)、b表示为(
a
2
,
b
2
,
c
2
a_2,b_2,c_2
a2,b2,c2)…
其某个聚类中心为o点(
x
0
,
y
0
,
z
(
0
)
x_0,y_0,z_(0)
x0,y0,z(0)，那么a点到o点的距离为：
d i s ( a , o ) = ( a 1 − x 0 ) 2 + ( b 1 − y 0 ) 2 + ( c 1 − z 0 ) 2 dis(a,o)=\sqrt {(a_1-x_0)^2+(b_1-y_0)^2+(c_1-z_0)^2} dis(a,o)=(a1−x0)2+(b1−y0)2+(c1−z0)2
依次比较每一个对象到每一个聚类中心的距离，将对象分配到距离最近的聚类中心的类簇中，得到k个类簇 { S 1 , S 2 , S 3 , . . . , S k } \lbrace S_1,S_2,S_3,...,S_ k \rbrace {S1,S2,S3,...,Sk}
聚类中心计算
Kmeans算法用中心定义了类簇的原型，类簇中心就是类簇内所有对象在各个维度的均值，其计算公式如下：
C
j
=
∑
X
i
∈
S
p
X
i
∣
N
S
p
∣
C_j=\frac{\sum_{X_i\in S_p}X_i}{\lvert{N_{S_p}}\rvert}
Cj=∣NSp∣∑Xi∈SpXi
C j C_j Cj表示第j个聚类中心， 1 ≤ j ≤ k 1\leq j \leq k 1≤j≤k； ∣ N S p ∣ \lvert{N_{S_p}}\rvert ∣NSp∣表示第p个类簇中对象的个数； X i X_i Xi表示第j个类簇中的第i个对象， 1 ≤ i ≤ ∣ N S p ∣ 1\leq i \leq \lvert{N_{S_p}}\rvert 1≤i≤∣NSp∣
比如一个二维平面上某一个聚类中心，里面有10个点，这十个点的聚类中心：
X轴坐标为： x = x 1 + x 2 + . . . + x 10 10 x=\frac{x_1+x_2+...+x_{10}}{10} x=10x1+x2+...+x10
Y轴坐标为： y = y 1 + y 2 + . . . + y 10 10 y=\frac{y_1+y_2+...+y_{10}}{10} y=10y1+y2+...+y10
所以该聚类中心就是 ( x , y ) (x,y) (x,y)
K-Means 工作原理
总结来说：
- 选取 K 个点作为初始的类中心点，这些点一般都是从数据集中随机抽取的；
- 将每个点分配到最近的类中心点，这样就形成了K 个类，然后重新计算每个类的中心点；
- 重复第二步，直到类不发生变化，或者你也可以设置最大迭代次数，这样即使类中心点发生变化，但是只要达到最大迭代次数就会结束。
算法流程
我现在选择了我的桌面对图像进行实例分割
导入图片、查看大小
#导入相关包
from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
#读取图片，转为numpy 数组，向量为长宽的像素值，rgb通道数为3
img = np.array(Image.open("dog.png"))
# 展示图像
plt.imshow(img)
# reshape，将长宽拉成一个一维的向量
x = img.reshape(-1,3)
print(img.shape,x.shape)
图像中每个像素点可以看做是一个数据点（三维向量 x = ( x 0 , x 1 , x 2 ) x=(x_0,x_1,x_2) x=(x0,x1,x2)）总共组成了1212714个三维向量集
生成随机聚类中心
在数据集中随机选取k个中心点, 用Z表示k个三维向量构成的数组
#随机初始化Z
def init_center(x,k):
# 从x的第一维度的长度中随机选k个数
index = np.random.choice(np.arange(x.shape[0]),k)
# 返回x在该行的值
return x[index]
#k 为要聚类的中心数
k = 2
z = init_center(x,k)
z
计算距离
分别计算每个数据点到k个中心点的距离，根据距离对该数据点进行分类。
def classify(x,Z):
Z_new = np.ones(Z.shape[0:])
#计算距离
temp = np.sum((x.reshape(1,-1,3) - Z.reshape(Z.shape[0],-1,3)) ** 2,axis=2)
index = np.argmin(temp,axis=0)
for i in range(Z.shape[0]):
# 同类的向量求和取均值，返回更新的Z与距离
Z_new[i] = np.mean(x[index==i],axis=0)
# 返回更新的Z,距离与分类情况
return Z_new,np.sum(temp),index
Z_new,distant,index = classify(x,z)
print("待更新的Z\n{}\n数据点到聚类中心距离和{}\n分类情况{}".format(Z_new,distant,index))
迭代求中心
def kmean(x,k):
#x （个数，特征维度）
#k 聚类个数
#index （个数，）对应k类别的索引
Z = init_center(x,k)#初始Z
epoch = 100#迭代次数 使用迭代的方法得到最终距离收敛的结果
for step in range(epoch):
Z,D,index = classify(x,Z)
if(step%10==0):
print("第{}次循环，距离{}".format(step+1,D))
return index,D
index,D = kmean(x,k)
结果展示
plt.imshow(index.reshape(img.shape[0:2]))