1. 二分K-Means算法(bisecting K-means)
为解决K-Means算法簇中心敏感问题，二分K-Means算法是一种弱化初始质中心的算法
步骤
5F8035AA-D892-4533-8612-4B459E3CEC41.png
从队列中选择划分簇的规则一般有两种方式
1.对所有簇计算误差和SSE(SSE可认为是距离函数的一种变种)，选择SSE最大的聚簇进行划分操作(优选这种决策)
image.png
- 选择样本数据量最多的簇进行划分操作
2. K-Means++算法
为解决K-Means算法对初始簇心比较敏感的问题，K-Means++算法和K-Means算法的区别在选取k个初始化中心点，K-Means算法使用随机给定的方式, K-Means++算法采用下列步骤给定K个初始质心
D60A5C22-D200-4D5F-B05F-9BA7DADAE156.png
缺点：由于簇类中心点选择过程中存在有序性，在拓展方面存在性能方面的问题(第k个簇类中心点的选择依赖前k-1簇类中心点的值)
3. K-Means|| 算法
解决K-Means++算法缺点而产生的一种算法；主要思路是改变每次遍历时候的取样规则，并非按照K-Means++算法每次遍历只获取一个样本，而是每次获取K个样本，重复该取样操作O(logn)次(n是样本的个数)，然后再将这些抽样出来的样本聚类出K个点，最后使用这K个点作为K-Means算法的初始聚簇中心点。实践证明：一般5次重复采用就可以保证一个比较好的聚簇中心点。
梳理步骤：
1、在N个样本中抽K个样本，一共抽logn次，形成一个新的样本集，一共有Klogn个数据。
2、在新数据集中使用K-Means算法，找到K个聚簇中心。
3、把这K个聚簇中心放到最初的样本集中，作为初始聚簇中心。
4、原数据集根据上述初始聚簇中心，再用K-Means算法计算出最终的聚簇。
4、Canopy算法
Canopy算法属于一种“粗”聚类算法，执行速度较快，但精度较低，算法执行步骤如下：
1、给定样本列表L=x1,x,2...,xm以及先验值r1和r2(r1>r2)；(先验值 - 自己猜的，人为定义的值)；
2、从列表L中获取一个节点P，计算P到所有聚簇中心点的距离(如果不存在聚簇中心，那么此时点P形成一个新的聚簇)，并选择出最小距离D(P,aj)；
3、如果距离D小于r1，表示该节点属于该聚簇，添加到该聚簇列表中。
4、如果距离D小于r2，表示该节点不仅仅属于该聚簇，还表示和当前聚簇中心点非常近，所以将该聚簇的中心点设置为P，并将P从列表L中删除。
5、如果距离D大于r1，那么节点P形成一个新的聚簇。
6、直到列表L中的元素数据不再有变化或者元素数量为0的时候，结束循环操作。
image.png
注意上图中修改一个地方：
本质上，列表中离得近的元素都删了。如果节点P生成了一个新的中心节点，也应该被删除掉。因为这些点已经变成了聚簇中心。
Canopy算法得到的最终结果的值，聚簇之间是可能存在重叠的，但是不会存在
某个对象不属于任何聚簇的情况
image.png
Canopy算法过程图形说明：
image
Canopy算法常用应用场景：
由于K-Means算法存在初始聚簇中心点敏感的问题，常用使用Canopy+K-Means算法混合形式进行模型构建。
1、先使用canopy算法进行“粗”聚类得到K个聚类中心点。
2、K-Means算法使用Canopy算法得到的K个聚类中心点作为初始中心点，进行“细”聚类。
优点：
1、执行速度快(先进行了一次聚簇中心点选择的预处理)；
2、不需要给定K值，应用场景多。
3、能够缓解K-Means算法对于初始聚类中心点敏感的问题。
5、Mini Batch K-Means
Mini Batch K-Means算法是K-Means算法的一种优化变种，采用小规模的数据子集(每次训练使用的数据集是在训练算法的时候随机抽取的数据子集)减少计算时间，同时试图优化目标函数；Mini Batch K-Means算法可以减少K-Means算法的收敛时间，而且产生的结果效果只是略差于标准K-Means算法。
算法步骤如下:
1 首先抽取部分数据集，使用K-Means算法构建K个聚簇点的模型
2 继续随机抽取训练数据集中的部分数据集样本数据，并将其添加到模型中，分配给距离最近的聚簇中心点
3 更新簇的中心点的值
4 循环迭代第二步和第三步操作，直到中心点稳定或者达到迭代次数结束
代码块
# -*- coding: utf-8 -*-
# @Time : 2019/1/22 2:18 PM
# @Author : scl
# @Email : 1163820757@qq.com
# @File : K-Means算法和Mini Batch K-Means算法比较.py
# @Software: PyCharm
import matplotlib
matplotlib.use("TkAgg")
import time
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl
from sklearn.cluster import MiniBatchKMeans, KMeans
from sklearn.metrics.pairwise import pairwise_distances_argmin
from sklearn.datasets.samples_generator import make_blobs
## 设置属性防止中文乱码
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
# 初始化三个中心
centers = [[1,1],[-1,-1],[1,-1]]
clusters = len(centers)
# 产生3000组2维数据 中心三个中心 标准差0.5
X,Y = make_blobs(30000,centers = centers,cluster_std = 0.5,random_state = 12)
# 构建kmeans算法
k_means = KMeans(init = 'k-means++',n_clusters = clusters,random_state = 12)
tk_time = time.time()
k_means.fit(X)
tk_second = time.time()-tk_time
print("kmeans算法模型训练耗时%.4fs"%(tk_second))
# 构建MiniBatchKMeans算法
batch_size = 100
mbk = MiniBatchKMeans(init='k-means++',n_clusters = clusters,batch_size = batch_size,random_state = 12)
mb_time = time.time()
mbk.fit(X)
mb_second = time.time()-mb_time
print("MiniBatchKMeans算法模型训练耗时%.4fs"%(mb_second))
# 预测结果
km_prd = k_means.predict(X)
mb_prd = mbk.predict(X)
print("K-Means算法预测值%s"%km_prd[:5])
print("MiniBatchK-Means算法预测值%s"%mb_prd[:5])
# 获取簇的中心点 并按簇类中心点排序
k_means_cluster_center = k_means.cluster_centers_
mbk_means_cluster_centers = mbk.cluster_centers_
'''
pairwise_distances_argmin默认情况下 该API的功能是将X,Y的元素做一个按大到小的排序
然后将排序后的X,Y的值两两组合
API 实际返回是针对x中的每个元素中的对应y中的每个值得下标索引
'''
order = pairwise_distances_argmin(
X=k_means_cluster_center,Y=mbk_means_cluster_centers)
print(order)
## 画图
plt.figure(figsize=(12,6),facecolor='w')
plt.subplots_adjust(left=0.05,right=0.95,bottom=0.05,top=0.9)
cm = mpl.colors.ListedColormap(['#FFC2CC', '#C2FFCC', '#CCC2FF'])
cm2 = mpl.colors.ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
# 子图1:原始数据
plt.subplot(221)
plt.scatter(X[:,0],X[:,1],c=Y,s=6,cmap=cm,edgecolors='none')
plt.title(u'原始数据分布图')
plt.xticks(())
plt.yticks(())
plt.grid(True)
# 子图2 K-Means算法聚类结果图
plt.subplot(222)
plt.scatter(X[:,0],X[:,1],c=km_prd,s=6,cmap=cm,edgecolors='none')
plt.scatter(k_means_cluster_center[:,0],k_means_cluster_center[:,1],
c=range(clusters),s=60,cmap=cm2,edgecolors='none')
plt.title(u'k-means算法聚类结果图')
plt.xticks(())
plt.yticks(())
plt.text(-2.8,3,'train time:%.2fms'%(tk_second*1000))
plt.grid(True)
# 子图3 mini batch k-means算法聚类算法
plt.subplot(223)
plt.scatter(X[:,0],X[:,1],c=mb_prd,s=6,cmap=cm,edgecolors='none')
plt.scatter(mbk_means_cluster_centers[:,0],mbk_means_cluster_centers[:,1],
c= range(clusters),s=60,cmap=cm2,edgecolors='none')
plt.title(u'mini batch k-means算法聚类结果图')
plt.xticks(())
plt.yticks(())
plt.text(-2.8,3,'train time:%.2fms'%(mb_second*1000))
plt.grid(True)
# 子图4 找到两种算法中预测的不同的样本数目
different = list(map(lambda x: (x!=0) & (x!=1) & (x!=2), mb_prd))
for k in range(clusters):
different += ((km_prd == k) != (mb_prd == order[k]))
identic = np.logical_not(different)
different_nodes = len(list(filter(lambda x:x, different)))
plt.subplot(224)
# 两者预测相同的
plt.plot(X[identic, 0], X[identic, 1], 'w', markerfacecolor='#bbbbbb', marker='.')
# 两者预测不相同的
plt.plot(X[different, 0], X[different, 1], 'w', markerfacecolor='r', marker='.')
plt.title(u'Mini Batch K-Means和K-Means算法预测结果不同的点')
plt.xticks(())
plt.yticks(())
plt.text(-2.8, 2, 'different nodes: %d' % (different_nodes))
plt.show()
效果
k-means与mini batch k-means.png
网友评论