# 聚类算法K-mean及其变形 -- 潘登同学的Machine Learning笔记 @
无监督机器学习
回顾有监督机器学习
- 给定训练集 X 和 标签Y
- 选择模型
- 学习（目标函数的最优化） - >生成模型（本质上是一组参数）
- 根据生成的一组参数进行预测、分类等任务
无监督机器学习
- 拿到的数据只有X ，没有标签 只是根据X的相似程度做一些事情
- 聚类
- 降维
数据间的相似度
- 每一条数据 都可以理解为多维空间中的一个点
- 可以根据点和点之间的距离来评价数据间的相似度来评
距离公式
闵可夫斯基距离 $$ d(X,Y) = \sqrt[p]{|x_1-y1|^p + |x_2-y_2|^p + \cdots + |x_n-y_n|^p} $$
P=1 曼哈顿距离 $$ d(X,Y) = {|x_1-y1| + |x_2-y_2| + \cdots + |x_n-y_n|} $$
P=2 欧氏距离 $$ d(X,Y) = \sqrt[2]{|x_1-y1|^2 + |x_2-y_2|^2 + \cdots + |x_n-y_n|^2} $$
P=无穷 切比雪夫距离
切比雪夫距离， 选择1-∞维度中差值最大的那个作为距离
- 余弦距离
将数据看做空间中的点的时候，评价远近可以用欧氏距离或者余弦距离
$$ cos\theta = \frac{\vec{a} \cdot \vec{b}}{||a|| \cdot ||b||} $$
越接近1， 就越相似； 越接近-1， 就越相反； 0代表正交；
- 数据相似度 - Jaccard相似系数
用来衡量有限样本集之间的相似程度 $$ J(A,B) = \frac{|A\cap B|}{|A \cup B|} $$ 从公式可以看出, 当A、B互斥的时候， J(A,B) = 0; 当A、B相同时， J(A,B) = 1；
- Jaccard距离 $$ d = 1 - J(A,B) $$
应用: 可以应用于网页去重、文本相似
聚类
- 目标：
- 将N个样本映射到K个簇中
- 每个簇至少有一个样本
- 基本思路：
- 先给定K个划分，迭代样本与簇的隶属关系，每次都比前一次好一些
- 迭代若干次 就能得到比较好的结果
作用:可以提前告知应该怎么划分分组， 所以说聚类可以发现(用于数据探索), 当然也可以预测
K-means聚类
(算法)
输入: 数据点(向量形式)， 聚类的组数K
输出： 数据中心， 数据归属于第几类
- 1.随机选择k个点作为中心
- 2.遍历所有点， 将点分到k个中心点的类别下(依据距离)
- 3.把每个类下的样本的$x,y,\ldots$加和求mean, 改变中心点
- 4.重复2、3 直到算法收敛(中心点位置不变)
K-mean的loss
$$ \begin{aligned} Loss &= \sum_{i=1}^{k}MSE_i(表示样本点到聚类中心的距离)\ &= \frac{1}{2}\sum_{j=2}^{j}\sum_{i=1}^{N_j}(x_i-\mu_j)(\mu_j是聚类中心) \end{aligned} $$
- 不考虑超参k时
这个函数是个非凸函数，根据初始值不同只能得到局部最优解
- 考虑超参k时 很显然是k越大， Loss越小；
K的选取
聚类类别的选取, 依据elbow point法则， 选取收益最大的点
举个栗子:
对鸢尾花数据集， 我们将其聚类为1类至9类
#%% K-means 聚类
import pandas as pd
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
data = pd.read_csv(r'C:/Users/潘登/Documents/python全系列/人工智能/iris.csv')
X = data.iloc[:, 2:4]
Y = data['species']
#%% 计算随着类别的上升, total loss
# 计算聚类中心到各点的距离
def calculate_distance(center, points):
'''
Parameters
----------
center : vector
中心点的向量坐标.
points : list[vector]
同一类别的向量坐标.
Returns
-------
distance: float
聚类中心到各点的距离之和
'''
distance = 0
for i in np.array(points):
distance += (((center-i)**2).sum())**(1/2)
return distance
total_loss = []
for i in range(1, 10):
km=KMeans(n_clusters=i,
init='random',
n_init=10,
max_iter=300,
tol=1e-4,
random_state=0)
y_km=km.fit_predict(X)
centers = np.c_[km.cluster_centers_[:,0],km.cluster_centers_[:,1]]
temp_loss = 0
for n, c in enumerate(centers):
points = X[y_km==n]
temp_loss += calculate_distance(c, points)
total_loss.append(temp_loss)
plt.figure(1)
plt.plot(list(range(1, len(total_loss)+1)), total_loss, 'k-')
plt.show()
- 结果如下：
从这张图中我们应该选取k=3作为我们的k值， 因为1→2：loss减少很多，2→3：loss仍有显著减少， 而3之后减少的就很平缓了， 所以应该选取k=3作为我们的k值；
同时我们注意到， 这张图像人们手臂弯曲时的一张图， 而k=3对应的就是手的肘部， 所以选择他， elbow points因此得名；
- 再来看看聚类算法的分类效果
分为两类
#%% 训练模型(2个类)
km=KMeans(n_clusters=2,
init='random',
n_init=10,
max_iter=300,
tol=1e-4,
random_state=0)
y_km=km.fit_predict(X)
plt.figure(figsize=(4,4))
plt.scatter(X[y_km==0].iloc[:,0],
X[y_km==0].iloc[:,1],
s=50,
c='lightgreen',
marker='s',
edgecolor='black',
label='Cluster 1')
plt.scatter(X[y_km==1].iloc[:,0],
X[y_km==1].iloc[:,1],
s=50,
c='orange',
marker='o',
edgecolor='black',
label='Cluster 2')
plt.xlabel('petal_length')
plt.ylabel('petal_width')
plt.legend(loc='best')
plt.legend()
plt.show()
分为三类
#%% 训练模型(3个类)
km=KMeans(n_clusters=3,
init='random',
n_init=10,
max_iter=300,
tol=1e-4,
random_state=0)
y_km=km.fit_predict(X)
plt.figure(figsize=(4,4))
plt.scatter(X[y_km==0].iloc[:,0],
X[y_km==0].iloc[:,1],
s=50,
c='lightgreen',
marker='s',
edgecolor='black',
label='Cluster 1')
plt.scatter(X[y_km==1].iloc[:,0],
X[y_km==1].iloc[:,1],
s=50,
c='orange',
marker='o',
edgecolor='black',
label='Cluster 2')
plt.scatter(X[y_km==2].iloc[:,0],
X[y_km==2].iloc[:,1],
s=50,
c='lightblue',
marker='v',
edgecolor='black',
label='Cluster 3')
plt.xlabel('petal_length')
plt.ylabel('petal_width')
plt.legend(loc='best')
plt.legend()
plt.show()
acc = ([y_km==1] == np.array([Y=='virginica'])).sum()/150 + \
([y_km==2] == np.array([Y=='setosa'])).sum()/150 + ([y_km==0] == np.array([Y=='versicolor'])).sum()/150
print('分类的正确率:%d%%'%(acc*100/3))
再康康正确答案
其实聚类对正确分类的准确率挺高的
总结
- 优点
- 简单，效果不错
- 缺点
- 对异常值敏感
- 对初值敏感（因为Loss function $\sum_{i=1}^{k}MSE_i$是一个非凸函数
- 对某些分布聚类效果不好
K-Mediods聚类
是K-Means聚类的改进版， 在计算新的簇中心时， 不再使用均值而使用中位数
抗噪能力得到增强
二分K-means
- 主要思想是：
首先将所有点作为一个簇，然后将该簇一分为二。 之后选择能最大限度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇。 以此进行下去，直到簇的数目等于用户给定的数目k为止。
- 具体步骤
- 先对数据集做一个k=2的K-means算法
- 选取MSE大的那部分继续做一个k=2的K-means， 重复直到结束
优点
- 二分K均值算法可以加速K-means算法的执行速度，因为它的相似度计算少了
- 不受初始化问题的影响，因为这里不存在随机点的选取，且每一步都保证了误差最小
K-means++
K-means++在初始化簇中心时的方法总结成一句话就是：逐个选取k个簇中心，且离其它簇中心越远的样本点越有可能被选为下一个簇中心
算法步骤
- 从数据集X中随机选取一个样本点作为第一个初始聚类中心C;
- 接着计算每个样本与当前已有聚类中心之间的最短距离，用$D(x)$表示；然后计算每个样本点被选为下一个聚类中心的概率$P(x)$，最后选择最大概率值所对应的样本点作为下一个簇中心 $$P(x) = \frac{D(x)^2}{\sum_{x\in X}D(x)^2}$$
- 重复第二步直到k个
注意 改进仅仅是改进初始化簇中心的方法， K-mean迭代的方法仍然没变；
还用前面的栗子：
km=KMeans(n_clusters=3,
init='k-means++',
n_init=10,
max_iter=300,
tol=1e-4,
random_state=0)
y_km=km.fit_predict(X)
plt.figure(figsize=(4,4))
plt.scatter(X[y_km==0].iloc[:,0],
X[y_km==0].iloc[:,1],
s=50,
c='lightgreen',
marker='s',
edgecolor='black',
label='Cluster 1')
plt.scatter(X[y_km==1].iloc[:,0],
X[y_km==1].iloc[:,1],
s=50,
c='orange',
marker='o',
edgecolor='black',
label='Cluster 2')
plt.scatter(X[y_km==2].iloc[:,0],
X[y_km==2].iloc[:,1],
s=50,
c='lightblue',
marker='v',
edgecolor='black',
label='Cluster 3')
plt.scatter(km.cluster_centers_[:,0],km.cluster_centers_[:,1],
s=250,
marker='*',
c='red',
edgecolor='black',
label='Centroids')
plt.xlabel('petal_length')
plt.ylabel('petal_width')
plt.legend(loc='best')
plt.legend()
plt.show()
acc = ([y_km==1] == np.array([Y=='virginica'])).sum()/150 + \
([y_km==2] == np.array([Y=='versicolor'])).sum()/150 + ([y_km==0] == np.array([Y=='setosa'])).sum()/150
print('分类的正确率:%d%%'%(acc*100/3))
- 结果如下：
Mini-batch Kmeans
Mini Batch K-Means算法是K-Means算法的一种优化变种，采用小规模的数据子集(每次训练使用的数据集是在训练算法的时候随机抽取的数据子集)减少计算时间，同时试图优化目标函数；Mini Batch K-Means算法可以减少K-Means算法的收敛时间，而且产生的结果效果只是略差于标准K-Means算法。
- 算法步骤如下
- 首先抽取部分数据集，使用
K-Means算法构建出K个聚簇点的模型; - 继续抽取训练数据集中的部分数据集样本数据，并将其添加到模型中，分配给距离最近的聚簇中心点;
- 更新聚簇的中心点值
- 重复2-3步，直到中心点稳定或者达到迭代次数为止。
- 首先抽取部分数据集，使用
#%% mini-batch kmean
import time
import matplotlib.pyplot as plt
import matplotlib
from sklearn.cluster import MiniBatchKMeans
from sklearn.datasets import make_blobs # 导入产生模拟数据的方法
matplotlib.rcParams['font.sans-serif'] = [u'SimHei']
matplotlib.rcParams['axes.unicode_minus'] = False
# 生成模拟数据
k = 5 # 给定聚类数量
X, Y = make_blobs(n_samples=1000, n_features=2, centers=k, random_state=42)
s = time.time()
km = MiniBatchKMeans(n_clusters = k, batch_size = 100)
km.fit(X)
print("用sklearn内置的Mini Batch K-Means算法聚类耗时：", time.time() - s)
# 对比Kmean
s = time.time()
km = KMeans(n_clusters = k)
km.fit(X)
print("用sklearn内置的K-Means算法聚类耗时：", time.time() - s)
label_pred = km.labels_ # 获取聚类后的样本所属簇对应值
centroids = km.cluster_centers_ # 获取簇心
# 绘制Mini Batch K-Means结果
# 未聚类前的数据分布
plt.subplot(121)
plt.scatter(X[:, 0], X[:, 1], s=50)
plt.title("未聚类前的数据分布")
plt.subplots_adjust(wspace=0.5)
plt.subplot(122)
plt.scatter(X[:, 0], X[:, 1], c=label_pred, s=50, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='o', s=100)
plt.title("Mini Batch K-Means算法聚类结果")
plt.show()
聚类结果：
MIni_batch_Kmean聚类与kmean的时间区别
K-mean聚类算法就是这样了, 继续下一章吧！pd的Machine Learning
