kmeans的基本原理
K均值算法的主要原理：首先假设一组向量作为所有簇的簇均值向量，然后根据这一组假设的簇均值向量给出数据集D的一个簇划分，然后根据这个簇的划分计算真正的簇均值向量，如果真实的簇均值向量与假设的簇均值向量相等则假设正确，根据假设给出的划分是原问题的解，如果不相等，则可以将真实的簇均值向量作为新的假设簇均值向量，继续求解。
kmeans的算法过程
创建k个点作为初始的质心点（随机选择）
-
当任意一个点的簇分配结果发生改变时
对数据集中的每一个数据点，对每一个质，计算质心与数据点的距离，将数据点分配到距离最近的簇，对每一个簇，计算簇中所有点的均值，并将均值作为质心
判断是否让每个数据点到质心的距离最小或者判断两次所选择的质心点是否相等如果相等则算法收敛
kmeans的缺点
经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
聚类中心的个数K 需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适
Kmeans需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（可以使用Kmeans++算法来解决）
补充 kmeans++
k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。
算法过程 ：
从输入的数据点集合中随机选择一个点作为第一个聚类中心
对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
重复2和3直到k个聚类中心被选出来
然后利用这k个初始的聚类中心来运行标准的k-means
从上面的算法描述上可以看到，算法的关键是第3步，如何将D(x)反映到点被选择的概率上，一种算法如下：
先从我们的数据库随机挑个随机点当“种子点”
对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
重复2和3直到k个聚类中心被选出来
利用这k个初始的聚类中心来运行标准的k-means算法
可以看到算法的第三步选取新中心的方法，这样就能保证距离D(x)较大的点，会被选出来作为聚类中心了
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets.samples_generator import make_blobs
from sklearn import cluster
from sklearn.metrics import adjusted_rand_score
from sklearn import mixture
def create_data(centers,num=100,std=0.7):
X , labels_true=make_blobs(n_samples=num,centers=centers,cluster_std=std)#make_blobs函数产生分割的高斯分布聚类簇
return X,labels_true
def plot_data(*data):
X,labels_true=data
labels=np.unique(labels_true)
fig=plt.figure()
ax=fig.add_subplot(1,1,1)
colors='rgbyckm'
for i ,label in enumerate(labels):
position=labels_true==label
ax.scatter(X[position,0],X[position,1],label="cluster %d " % label,color=colors[i%len(colors)])
ax.legend(loc='best',framealpha=0.5)
ax.set_xlabel("X[0]")
ax.set_ylabel("Y[1]")
plt.show()
def test_kmeans(*data):
X,labels_true=data
clst=cluster.KMeans()
clst.fit(X)
predicted_labels=clst.predict(X)
print("ARI:%s"% adjusted_rand_score(labels_true,predicted_labels))
print("sum distance %s" % clst.inertia_)
#X,labels_true = create_data([[1,1],[2,2],[1,2],[10,20]],1000,0.5)
#test_kmeans(X,labels_true)
def test_kmeans_nclusters(*data):
X,labels_true=data
nums=range(1,50)
ARIs=[]
Distance=[]
for num in nums :
clst=cluster.KMeans(n_clusters=num)
clst.fit(X)
predicted_labels = clst.predict(X)
ARIs.append(adjusted_rand_score(labels_true,predicted_labels))
Distance.append(clst.inertia_)
fig=plt.figure()
ax=fig.add_subplot(1,2,1)
ax.plot(nums,ARIs,marker='+')
ax.set_xlabel("n_clusters")
ax.set_ylabel("ARI")
ax=fig.add_subplot(1,2,2)
ax.plot(nums,Distance,marker='o')
ax.set_xlabel('n_clusters')
ax.set_ylabel('inertia_')
plt.show()
X,labels_true = create_data([[1,1],[2,2],[1,2],[10,20]],1000,0.5)
test_kmeans(X,labels_true)
test_kmeans_nclusters(X,labels_true)
