机器学习_聚类_k-means

聚类算法

（1）k-means

http://www.cnblogs.com/lc1217/p/6893924.html

1.简介

K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。

2. 算法大致流程为：

   1）随机选取k个点作为种子点(这k个点不一定属于数据集)

   2）分别计算每个数据点到k个种子点的距离，离哪个种子点最近，就属于哪类

   3）重新计算k个种子点的坐标(简单常用的方法是求坐标值的平均值作为新的坐标值)

   4）重复2、3步，直到种子点坐标不变或者循环次数完成

   重新计算种子点的坐标值，可以使用平均坐标距离公式闵可夫斯基距离(Minkowski Distance)

     https://blog.csdn.net/Losteng/article/details/50893931

import numpy as np
import matplotlib.pyplot as plt##样本数据(Xi,Yi)，需要转换成数组(列表)形式
Xn=np.array([2,3,1.9,2.5,4])
Yn=np.array([5,4.8,4,1.8,2.2])#标识符号
sign_n = ['A','B','C','D','E']
sign_k = ['k1','k2']##数据点分类
def start_class(Xk,Yk): #Xk，Yk是指中心点坐标向量（在此例子中指的是k1,k2）cls_dict = {}  # 字典##离哪个分类点最近，属于哪个分类for i in range(len(Xn)):temp = [] # 链表listfor j in range(len(Xk)):d1 = np.sqrt((Xn[i]-Xk[j])*(Xn[i]-Xk[j])+(Yn[i]-Yk[j])*(Yn[i]-Yk[j]))  #点与各分类点的距离temp.append(d1) # 所有距离链表，从首部开始推入，pop从尾部开始推出min_dis=np.min(temp) #从点与各分类点的距离与计算的聚类中选择其最小的那个min_inx = temp.index(min_dis)  #识别最小的是与哪个分类点cls_dict[sign_n[i]]=sign_k[min_inx] #用分类点来标记该点#循环结束#print(cls_dict)   return cls_dict  ###重新计算分类的坐标点
def recal_class_point(Xk,Yk,cls_dict):  num_k1 = 0  #属于k1的数据点的个数num_k2 = 0  #属于k2的数据点的个数x1 =0       #属于k1的x坐标和y1 =0       #属于k1的y坐标和x2 =0       #属于k2的x坐标和y2 =0       #属于k2的y坐标和##循环读取已经分类的数据for d in cls_dict:  #d是'A','B','C','D','E'kk = cls_dict[d]  #kk是k1/k2标签##读取d的类别## 按照分类求同一分类的坐标值的平均值作为新的分类点的坐标值# 求k1及k2的累积坐标和if kk == 'k1':idx = sign_n.index(d) #读取d在数据集中的索引x1 += Xn[idx]         ##累加x值y1 += Yn[idx]         ##累加y值num_k1 += 1           ##累加分类个数else :idx = sign_n.index(d) #读取d在数据集中的索引x2 += Xn[idx]         ##累加x值y2 += Yn[idx]         ##累加y值num_k2 += 1           ##累加分类个数##求平均值获取新的分类坐标点k1_new_x = x1/num_k1 #新的k1的x坐标k1_new_y = y1/num_k1 #新的k1的y坐标k2_new_x = x2/num_k2 #新的k2的x坐标k2_new_y = y2/num_k2 #新的k2的y坐标##新的分类数组Xk=np.array([k1_new_x,k2_new_x])Yk=np.array([k1_new_y,k2_new_y])return Xk,Ykdef draw_point(Xk,Yk,cls_dict):#画样本点plt.figure(figsize=(5,4)) #设置图像尺寸大小plt.scatter(Xn,Yn,color="green",label="数据",linewidth=1)  #画散点图plt.scatter(Xk,Yk,color="red",label="分类",linewidth=1)plt.xticks(range(1,6))  #为x轴的主刻度和次刻度设置颜色、大小、方向，以及标签大小plt.xlim([min(Xn)-1,max(Xn)+1])  plt.ylim([min(Xn)-1,max(Xn)+1])plt.legend()  #显示图中标签#给图中点标签for i in range(len(Xn)):plt.text(Xn[i],Yn[i],sign_n[i]+":"+cls_dict[sign_n[i]]) #给A:k1标签for i in range(len(Xk)):plt.text(Xk[i],Yk[i],sign_k[i])plt.show()if __name__ == "__main__":##种子分类点Xk=np.array([3.3,3.0])Yk=np.array([5.7,3.2])for i in range(3):  #循环3次cls_dict =start_class(Xk,Yk)Xk_new,Yk_new =recal_class_point(Xk,Yk,cls_dict)Xk=Xk_newYk=Yk_newdraw_point(Xk,Yk,cls_dict)

4.K-Means的不足

     K-Means算法的不足，都是由初始值引起的：

    1）初始分类数目k值很难估计，不确定应该分成多少类才最合适(ISODATA算法通过类的自动合并和分裂，得到较为合理的类型数目k。这里不 讲这个算法) https://www.cnblogs.com/huadongw/articles/4101306.html

    2）不同的随机种子会得到完全不同的结果(K-Means++算法可以用来解决这个问题，其可以有效地选择初始点)

5.K-Means++算法

   算法流程如下：

    1）在数据集中随机挑选1个点作为种子点

    2）计算剩余数据点到这个点的距离d(x),并且加入到列表

    3）再取一个随机值。这次的选择思路是：先取一个能落在上一步计算的距离列表求和后(sum(dis_list))的随机值rom，然后用rom -= d(x)，直到rom<=0，此时的点就是下一个“种子点”

    4）重复第2步和第3步，直到选出k个种子

 5）进行标准的K-Means算法。

下面完整代码

import numpy as np
import matplotlib.pyplot as plt##样本数据(Xi,Yi)，需要转换成数组(列表)形式
Xn=np.array([2,3,1.9,2.5,4])
Yn=np.array([5,4.8,4,1.8,2.2])#标识符号
sign_n = ['A','B','C','D','E']
sign_k = ['k1','k2']##随机挑选一个数据点作为种子点
def select_seed(Xn):idx = np.random.choice(range(len(Xn)))return idx##计算数据点到种子点的距离
def cal_dis(Xn,Yn,idx):dis_list = []for i in range(len(Xn)):       d = np.sqrt((Xn[i]-Xn[idx])**2+(Yn[i]-Yn[idx])**2)dis_list.append(d)return dis_list##随机挑选另外的种子点
def select_seed_other(Xn,Yn,dis_list):d_sum = sum(dis_list)rom = d_sum * np.random.random()idx = 0for i in range(len(Xn)):rom -= dis_list[i]if rom > 0 :continueelse :idx = ireturn idx##选取所有种子点
def select_seed_all(seed_count):##种子点Xk = []  ##种子点x轴列表Yk = []  ##种子点y轴列表idx = 0  ##选取的种子点的索引dis_list = [] ##距离列表##选取种子点#因为实验数据少，有一定的几率选到同一个数据，所以加一个判断idx_list = []flag = Truefor i in range(seed_count):if i == 0:idx = select_seed(Xn)dis_list = cal_dis(Xn,Yn,idx)Xk.append(Xn[idx])Yk.append(Yn[idx])idx_list.append(idx)else :while flag:idx = select_seed_other(Xn,Yn,dis_list)if idx not in idx_list:flag = Falseelse :continuedis_list = cal_dis(Xn,Yn,idx)Xk.append(Xn[idx])Yk.append(Yn[idx])idx_list.append(idx)##列表转成数组       Xk=np.array(Xk)Yk=np.array(Yk)return Xk,Ykdef start_class(Xk,Yk):##数据点分类cls_dict = {}##离哪个分类点最近，属于哪个分类for i in range(len(Xn)):temp = []for j in range(len(Xk)):d1 = np.sqrt((Xn[i]-Xk[j])*(Xn[i]-Xk[j])+(Yn[i]-Yk[j])*(Yn[i]-Yk[j]))temp.append(d1)min_dis=np.min(temp)min_inx = temp.index(min_dis)cls_dict[sign_n[i]]=sign_k[min_inx]#print(cls_dict)return cls_dict##重新计算分类的坐标点
def recal_class_point(Xk,Yk,cls_dict):  num_k1 = 0  #属于k1的数据点的个数num_k2 = 0  #属于k2的数据点的个数x1 =0       #属于k1的x坐标和y1 =0       #属于k1的y坐标和x2 =0       #属于k2的x坐标和y2 =0       #属于k2的y坐标和##循环读取已经分类的数据for d in cls_dict:##读取d的类别kk = cls_dict[d]if kk == 'k1':#读取d在数据集中的索引idx = sign_n.index(d)##累加x值x1 += Xn[idx]##累加y值y1 += Yn[idx]##累加分类个数num_k1 += 1else :#读取d在数据集中的索引idx = sign_n.index(d)##累加x值x2 += Xn[idx]##累加y值y2 += Yn[idx]##累加分类个数num_k2 += 1##求平均值获取新的分类坐标点k1_new_x = x1/num_k1 #新的k1的x坐标k1_new_y = y1/num_k1 #新的k1的y坐标k2_new_x = x2/num_k2 #新的k2的x坐标k2_new_y = y2/num_k2 #新的k2的y坐标##新的分类数组Xk=np.array([k1_new_x,k2_new_x])Yk=np.array([k1_new_y,k2_new_y])return Xk,Ykdef draw_point(Xk,Yk,cls_dict):#画样本点plt.figure(figsize=(5,4)) plt.scatter(Xn,Yn,color="green",label="数据",linewidth=1)plt.scatter(Xk,Yk,color="red",label="分类",linewidth=1)plt.xticks(range(1,6))plt.xlim([1,5])plt.ylim([1,6])plt.legend()for i in range(len(Xn)):plt.text(Xn[i],Yn[i],sign_n[i]+":"+cls_dict[sign_n[i]])for i in range(len(Xk)):plt.text(Xk[i],Yk[i],sign_k[i])plt.show()def draw_point_all_seed(Xk,Yk):#画样本点plt.figure(figsize=(5,4)) plt.scatter(Xn,Yn,color="green",label="数据",linewidth=1)plt.scatter(Xk,Yk,color="red",label="分类",linewidth=1)plt.xticks(range(1,6))plt.xlim([1,5])plt.ylim([1,6])plt.legend()for i in range(len(Xn)):plt.text(Xn[i],Yn[i],sign_n[i])plt.show()if __name__ == "__main__":##选取2个种子点Xk,Yk = select_seed_all(2)##查看种子点draw_point_all_seed(Xk,Yk)##循环三次进行分类for i in range(3):cls_dict =start_class(Xk,Yk)Xk_new,Yk_new =recal_class_point(Xk,Yk,cls_dict)Xk=Xk_newYk=Yk_newdraw_point(Xk,Yk,cls_dict)

6. sklearn包中k-Means算法

1）函数：sklearn.cluster.KMeans

   2）主要参数

           n_clusters：要进行的分类的个数，即上文中k值，默认是8

           max_iter  ：最大迭代次数。默认300

           min_iter   ：最小迭代次数，默认10

           init：有三个可选项

                   'k-means ++'：使用k-means++算法，默认选项

                   'random':从初始质心数据中随机选择k个观察值

                   第三个是数组形式的参数

            n_jobs: 设置并行量 （-1表示使用所有CPU）

     3）主要属性：

          cluster_centers_ ：集群中心的坐标

          labels_ : 每个点的标签

      4）官网示例：  

      

>>> 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.]])