⼿写算法-python代码实现Kmeans++以及优化
⼿写算法-python代码实现Kmeans++以及优化
聚类结果不稳定的优化⽅法
上篇⽂章，我们列举了Kmeans的不⾜之处，也⽤python代码实现了Kmeans聚类，但是跑出来的聚类结果不稳定，详情请看：链接:
今天，我们来解决这个问题。
⼀次优化：kmeans++
问题点：随机选取k个数据，导致结果⽆法收敛。
因为随机选取，可能会使选取的⼏个数据点都⾮常靠近，不仅导致算法收敛很慢，还会导致结果只收敛到局部最⼩值。
解决思路：
使⽤Kmeans++的⽅法初始质⼼，流程如下：
1、从输⼊的数据点集合中随机选择⼀个点作为第⼀个聚类中⼼；
2、对于数据集中的每⼀个点xi，计算它与已选择的聚类中⼼中最近聚类中⼼的距离D(x)；
3、 选择⼀个新的数据点作为新的聚类中⼼，选择的原则是：D(x)较⼤的点，被选取作为聚类中⼼的概率较⼤；
4、重复b和c直到选择出k个聚类质⼼；
5、利⽤这k个质⼼来作为初始化质⼼去运⾏标准的K-Means算法；
按照上⾯的流程，我们来修改Kmeans代码，实现Kmeans++。
import numpy as np
from sklearn.datasets import make_blobs
from matplotlib import pyplot as plt
#⽆监督算法，学习过程就是训练质⼼的位置，进⾏聚类
class Kmeans:
#添加init参数，默认init = 'random'就是标准Kmeans，init = 'Kmeans++'则为Kmeans++
def __init__(self,k,init='random'):
self.k = k
self.init = init
def calc_distance(self,x1,x2):
diff = x1 - x2
distances = np.sqrt(np.square(diff).sum(axis=1))
return distances
def fit(self,x):
self.x = x
m,n = shape
if self.init == 'random':
#随机选定k个数据作为初始质⼼，不重复选取
#默认类别是从0到k-1
elif self.init == 'Kmeans++':
first = np.random.choice(m)
#储存在⼀个列表中
index_select = [first]
#继续选取k-1个点
for i in range(1,self.k):
all_distances = np.empty((m,0))
for j in index_select:
#计算每个数据点到已选择的质⼼的距离
#计算每个数据点到已选择的质⼼的距离
distances = self.calc_distance(self.x,x[j]).reshape(-1,1)
#把每个数据点到已选择的质⼼的距离储存在数组中，每个质⼼⼀列
all_distances = np.c_[all_distances,distances]
#到每个点到已选择质⼼的最⼩距离
min_distances = all_distances.min(axis=1).reshape(-1,1)
#在min_distances⾥⾯选取距离较⼤的点作为下⼀个质⼼，我们就选最⼤的点
index = np.argmax(min_distances)
index_select.append(index)
#⽣成Kmeans++⽅法的初始质⼼，默认类别是从0到k-1
while True:
#初始化⼀个字典，以类别作为key，赋值⼀个空数组
dict_y = {}
for j in range(self.k):
dict_y[j] = np.empty((0,n))
for i in range(m):
distances =self.calc_distance(x[i],iginal_center)
#把第i个数据分配到距离最近的质⼼，存放在字典中
label = np.argsort(distances)[0]
dict_y[label] = np.r_[dict_y[label],x[i].reshape(1,-1)]
centers = np.empty((0,n))
#对每个类别的样本重新求质⼼
for i in range(self.k):
center = np.mean(dict_y[i],axis=0).reshape(1,-1)
centers = np.r_[centers,center]
#与上⼀次迭代的质⼼⽐较，如果没有发⽣变化，则停⽌迭代（也可考虑收敛时停⽌）
result = np.all(centers == iginal_center)
if result == True:
break
else:
#继续更新质⼼
def predict(self,x):
y_preds = []
m,n = x.shape
for i in range(m):
distances =self.calc_distance(x[i],iginal_center)
y_pred = np.argsort(distances)[0]
y_preds.append(y_pred)
return y_preds
代码修改完毕，现在我们再次请出上篇⽂章⽤到的数据集，验证修改后，聚类结果稳不稳定：
#再次⽤到此数据集
x,y = make_blobs(centers=5,random_state=20,cluster_std=1)
plt.scatter(x[:,0],x[:,1])
plt.show()
model = Kmeans(k=5,init = 'Kmeans++') model.fit(x)
y_preds = model.predict(x)
plt.scatter(x[:,0],x[:,1],c=y_preds)
plt.show()
可以看到，不管执⾏多少遍，聚类结果都是稳定的，证明我们修改的Kmeans++成功！⼆次优化：添加参数n_init
这是什么意思呢，意思很简单：
就是我执⾏n_init次，最终结果取最优的⼀次，最优怎么理解呢？
简单地说，就是所有样本点到所属的聚类质⼼的距离之和最⼩，即为最优。
在Kmeans++⽅法选取质⼼的基础上，再添加参数n_init，双重保险，万⽆⼀失！哈哈。。。到n_init次运⾏中，J最⼩时，对应的聚类质⼼，即为最优解。
继续修改代码如下：
#⽆监督算法，学习过程就是训练质⼼的位置，进⾏聚类
class Kmeans:
#添加init 参数，默认init = 'random'就是标准Kmeans ，init = 'Kmeans++'则为Kmeans++
def __init__(self,k,n_init,init='random'):
self.k = k
self.n_init = n_init
self.init = init
def calc_distance(self,x1,x2):
diff = x1 - x2
distances = np.sqrt(np.square(diff).sum(axis=1))
return distances
def fit(self,x):
m,n = x.shape
if self.init == 'random':
#随机选定k 个数据作为初始质⼼，不重复选取
快速排序python实现iginal_ = np.random.choice(m,self.k,replace=False)
#默认类别是从0到k-1
elif self.init == 'Kmeans++':
first = np.random.choice(m)
#储存在⼀个列表中
index_select = [first]
#继续选取k-1个点
for i in range(1,self.k):
all_distances = np.empty((m,0))
for j in index_select:
#计算每个数据点到已选择的质⼼的距离
distances = self.calc_distance(x,x[j]).reshape(-1,1)
#把每个数据点到已选择的质⼼的距离储存在数组中，每个质⼼⼀列
all_distances = np.c_[all_distances,distances]
#到每个点到已选择质⼼的最⼩距离
min_distances = all_distances.min(axis=1).reshape(-1,1)
#在min_distances ⾥⾯选取距离较⼤的点作为下⼀个质⼼，我们就选最⼤的点
index = np.argmax(min_distances)
index_select.append(index)
#⽣成Kmeans++⽅法的初始质⼼，默认类别是从0到k-1
while True:
#初始化⼀个字典，以类别作为key ，赋值⼀个空数组
dict_y = {}
for j in range(self.k):
dict_y[j] = np.empty((0,n))
for i in range(m):
distances =self.calc_distance(x[i],iginal_center)
#把第i 个数据分配到距离最近的质⼼，存放在字典中
label = np.argsort(distances)[0]
dict_y[label] = np.r_[dict_y[label],x[i].reshape(1,-1)]
centers = np.empty((0,n))J =min ∣∣x −i =1∑m
i μ∣∣c i 2

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。