大量数据中具有"相似"特征的数据点或样本划分为一个类别。聚类分析提供了样本集在非监督模式下的类别划分。聚类的基本思想是"物以类聚、人以群分"，将大量数据集中相似的数据样本区分出来，并发现不同类的特征。
聚类模型可以建立在无类标记的数据上，是一种非监督的学习算法。尽管全球每日新增数据量以PB或EB级别增长，但是大部分数据属于无标注甚至非结构化。所以相对于监督学习，不需要标注的无监督学习蕴含了巨大的潜力与价值。聚类根据数据自身的距离或相似度将他们划分为若干组，划分原则是组内样本最小化而组间距离最大化。
- 常用于数据探索或挖掘前期
- 没有先验经验做探索性分析
- 样本量较大时做预处理
- 解决问题
- 数据集可以分几类
- 每个类别有多少样本量
- 不同类别中各个变量的强弱关系如何
- 不同类型的典型特征是什么
- 应用场景
- 群类别间的差异性特征分析
- 群类别内的关键特征提取
- 图像压缩、分割、图像理解
- 异常检测
- 数据离散化
- 缺点
- 无法提供明确的行动指向
- 数据异常对结果有影响
本文将从算法原理、优化目标、sklearn聚类算法、算法优缺点、算法优化、算法重要参数、衡量指标以及案例等方面详细介绍KMeans算法。
KMeans
K 均值（KMeans）是聚类中最常用的方法之一，基于点与点之间的距离的相似度来计算最佳类别归属。
KMeans算法通过试着将样本分离到
个方差相等的组中来对数据进行聚类，从而最小化目标函数 (见下文)。该算法要求指定集群的数量。它可以很好地扩展到大量的样本，并且已经在许多不同领域的广泛应用领域中使用。
被分在同一个簇中的数据是有相似性的，而不同簇中的数据是不同的，当聚类完毕之后，我们就要分别去研究每个簇中的样本都有什么样的性质，从而根据业务需求制定不同的商业或者科技策略。常用于客户分群、用户画像、精确营销、基于聚类的推荐系统。
算法原理
- 从
个样本数据中随机选取
个质心作为初始的聚类中心。质心记为
- 定义优化目标
- 开始循环，计算每个样本点到那个质心到距离，样本离哪个近就将该样本分配到哪个质心，得到 K 个簇
- 对于每个簇，计算所有被分到该簇的样本点的平均距离作为新的质心
- 直到
收敛，即所有簇不再发生变化。
KMeans迭代示意图
优化目标
KMeans 在进行类别划分过程及最终结果，始终追求"簇内差异小，簇间差异大"，其中差异由样本点到其所在簇的质心的距离衡量。在 KNN 算法学习中，我们学习到多种常见的距离 ---- 欧几里得距离、曼哈段距离、余弦距离。
在 sklearn 中的KMeans使用欧几里得距离：
则一个簇中所有样本点到质心的距离的平方和为：
其中，
为一个簇中样本的个数，
是每个样本的编号。这个公式被称为簇内平方和
(cluster Sum of Square)， 又叫做
Inertia。
而将一个数据集中的所有簇的簇内平方和相加，就得到了整体平方和(Total Cluster Sum of Square)，又叫做Total Inertia。Total Inertia 越小，代表着每个簇内样本越相似，聚类的效果就越好。因此 KMeans 追求的是，求解能够让Inertia最小化的质心。
K-means 有损失函数吗？
损失函数本质是用来衡量模型的拟合效果的，只有有着求解参数需求的算法，才会有损失函数。Kmeans 不求解什么参数，它的模型本质也没有在拟合数据，而是在对数据进行一 种探索。
另外，在决策树中有衡量分类效果的指标准确度
accuracy，准确度所对应的损失叫做泛化误差，但不能通过最小化泛化误差来求解某个模型中需要的信息，我们只是希望模型的效果上表现出来的泛化误差 很小。因此决策树，KNN 等算法，是绝对没有损失函数的。
虽然在 sklearn 中只能被动选用欧式距离，但其他距离度量方式同样可以用来衡量簇内外差异。不同距离所对应的质心选择方法和Inertia如下表所示, 在K-means中，只要使用了正确的质心和距离组合，无论使用什么样的距离，都可以达到不错的聚类效果。
| 距离度量 | 质心 | Inertia |
|---|
| 欧几里得距离 | 均值 | 最小化每个样本点到质心的欧式距离之和 |
| 曼哈顿距离 | 中位数 | 最小化每个样本点到质心的曼哈顿距离之和 |
| 余弦距离 | 均值 | 最小化每个样本点到质心的余弦距离之和 |
sklearn.cluster.KMeans
语法：
sklearn.cluster.KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=None, algorithm='auto')
参数与接口见文末原文
例：
>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
... [10, 2], [10, 4], [10, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([1, 1, 1, 0, 0, 0], dtype=int32)
>>> kmeans.predict([[0, 0], [12, 3]])
array([1, 0], dtype=int32)
>>> kmeans.cluster_centers_
array([[10., 2.],
[ 1., 2.]])
k-means++聚类算法
由KMeans算法原来可知，KMeans在聚类之前首先需要初始化
个簇中心，因此
KMeans 算法对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。若初始化是个随机过程，很有可能
个簇中心都在同一个簇中，这种情况
KMeans 聚类算法很大程度上都不会收敛到全局最小。
为了优化选择初始质心的方法，2007 年 Arthur, David, and Sergei Vassilvitskii 三人发表了论文“k-means++: The advantages of careful seedinghttp://ilpubs.stanford.edu:8090/778/1/2006-13.pdf，sklearn.cluster.KMeans 中默认参数为 init='k-means++' ，其算法原理为在初始化簇中心时，逐个选取
个簇中心，且离其他簇中心越远的样本越有可能被选为下个簇中心。
算法步骤：
- 从数据即
中随机（均匀分布）选取一个样本点作为第一个初始聚类中心
- 计算每个样本与当前已有聚类中心之间的最短距离
；再计算每个样本点被选为下个聚类中心的概率
，最后选择最大概率值所对应的样本点作为下一个簇中心
- 重复上步骤，直到选择
个聚类中心
k-means++算法初始化的簇中心彼此相距都十分的远，从而不可能再发生初始簇中心在同一个簇中的情况。
code：
def InitialCentroid(x, K):
c1_idx = int(np.random.uniform(0, len(x))) # Draw samples from a uniform distribution.
centroid = x[c1_idx].reshape(1, -1) # choice the first center for cluster.
k = 1
n = x.shape[0] # number of samples
while k < K:
d2 = []
for i in range(n):
subs = centroid - x[i, :] # D(x) = (x_1, y_1) - (x, y)
dimension2 = np.power(subs, 2) # D(x)^2
dimension_s = np.sum(dimension2, axis=1) # sum of each row
d2.append(np.min(dimension_s))
new_c_idx = np.argmax(d2)
centroid = np.vstack([centroid, x[new_c_idx]])
k += 1
return centroid
重要参数
1、初始质心
KMeans 算法的第一步"随机"在样本中抽取k 个样本作为初始质心，因此并不符合"稳定且更快"的需求。因此可通过random_state参数来指定随机数种子，以控制每次生成的初始质心都在相同位置。
一个random_state对应一个质心随机初始化的随机数种子。如果不指定随机数种子，则 sklearn中的KMeans并不会只选择一个随机模式扔出结果，而会在每个随机数种子下运行多次，并使用结果最好的一个随机数种子来作为初始质心。我们可以使用参数n_init来选择，每个随机数种子下运行的次数。
而以上两种方法仍然避免不了基于随机性选取 k 个质心的本质。在sklearn中，我们使用参数init ='k-means ++'来选择使用k-means ++作为质心初始化的方案。
「init」: 可输入"k-means++"，"random"或者一个n维数组。这是初始化质心的方法，默认"k-means++"。输入"k- means++":一种为 K 均值聚类选择初始聚类中心的聪明的办法，以加速收敛。如果输入了n维数组，数组的形状应该是(n_clusters，n_features)并给出初始质心。
「random_state」: 控制每次质心随机初始化的随机数种子。
「n_init」: 整数，默认 10，使用不同的质心随机初始化的种子来运行KMeans算法的次数。最终结果会是基于Inertia来计算的n_init次连续运行后的最佳输出。
2、迭代停止
「max_iter」: 整数，默认 300，单次运行的KMeans算法的最大迭代次数。
「tol」: 浮点数，默认1e-4，两次迭代间Inertia下降的量，如果两次迭代之间Inertia下降的值小于tol所设定的值，迭代就会停下。
衡量指标
聚类模型的结果不是某种标签输出，并且聚类的结果是不确定的，其优劣由业务需求或者算法需求来决定，并且没有永远的正确答案。那么如何衡量聚类的效果呢?
衡量簇内差异来衡量聚类的效果
簇内平方和：Total_Inertia
「肘部法（手肘法）认为图上的拐点就是 K 的最佳值」
# 应用肘部法则确定 kmeans方法中的k
from scipy.spatial.distance import cdist # 计算两个输入集合的每对之间的距离。
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from sklearn.datasets import make_blobs
plt.style.use('seaborn')
plt.rcParams['font.sans-serif']=['Simhei'] #显示中文
plt.rcParams['axes.unicode_minus']=False #显示负号
X, y = make_blobs(n_samples=5000, centers=4, cluster_std = 2.5, n_features=2,random_state=42)
K=range(1,10)
# 直接计算sse
sse_result=[]
for k in K:
kmeans=KMeans(n_clusters=k, random_state=666)
kmeans.fit(X)
sse_result.append(sum(np.min(cdist(X,kmeans.cluster_centers_,'euclidean'),axis=1))/X.shape[0])
plt.figure(figsize=(16,5))
plt.subplot(1,2,1)
plt.plot(K,sse_result,'gp-')
plt.xlabel('k',fontsize=20)
plt.ylabel(u'平均畸变程度')
plt.title(u'肘部法则确定最佳的K值(1)',fontdict={'fontsize':15})
# 第二种，使用inertia_
L = []
for k in K:
kmeans = KMeans(n_clusters=k, random_state=666)
kmeans.fit(X)
L.append((k, kmeans.inertia_))
a = pd.DataFrame(L)
a.columns = ['k', 'inertia']
plt.subplot(1,2,2)
plt.plot(a.k, a.inertia,'gp-')
plt.xlabel('k',fontsize=20)
plt.ylabel('inertia')
plt.title(u'肘部法则确定最佳的K值(2)',fontdict={'fontsize':15})
plt.xticks(a.k)
plt.show();
输出结果
但其有很大的局限：
- 它的计算太容易受到特征数目的影响。
- 它不是有界的，
Inertia是越小越好，但并不知道合适达到模型的极限，能否继续提高。 - 它会受到超参数 K 的影响，随着
K越大，Inertia注定会越来越小，但并不代表模型效果越来越好。 - Inertia 对数据的分布有假设，它假设数据满足凸分布，并且它假设数据是各向同性的 (
isotropic)，所以使用Inertia作为评估指标，会让聚类算法在一些细长簇，环形簇，或者不规则形状的流形时表现不佳。
其他衡量指标
1、真实标签已知时
可以用聚类算法的结果和真实结果来衡量聚类的效果。但需要用到聚类分析的场景，大部分均属于无真是标签的情况，可到原文里查看模型评估指标了解即可。
2、真实标签未知时
「轮廓系数」
对没有真实标签的数据进行探索，常用轮廓系数评价聚类算法模型效果。
- 样本与其自身所在的簇中的其他样本的相似度
a，等于样本与同一簇中所有其他点之间的平均距离 。 - 样本与其他簇中的样本的相似度
b，等于样本与下一个最近的簇中的所有点之间的平均距离。
根据聚类的要求"簇内差异小，簇外差异大"，我们希望b永远大于a，并且大得越多越好。
单个样本的轮廓系数计算为:
取值范围
越大越好。
- 越接近 1 表示样本与自己所在的簇中的样本很相似，并且与其他簇中的样本不相似，当样本点与簇外的样本更相似的时候，轮廓系数就为负。
- 当轮廓系数为 0 时，则代表两个簇中的样本相似度一致，两个簇本应该是一个簇。
from sklearn.metrics import silhouette_score
# 返回所有样本的轮廓系数的均值
from sklearn.metrics import silhouette_samples
# 返回的是数据集中每个样本自己的轮廓系数
silhouette_score(X,y_pred)
silhouette_score(X,cluster_.labels_)
silhouette_samples(X,y_pred)
例：
L = []
for i in range(2, 20):
k = i
kmeans = KMeans(n_clusters=i)
kmeans.fit(X)
L.append([i, silhouette_score(X, kmeans.labels_)])
a = pd.DataFrame(L)
a.columns = ['k', '轮廓系数']
plt.figure(figsize=(8, 5), dpi=70)
plt.plot(a.k, a.轮廓系数,'gp-')
plt.xticks(a.k)
plt.xlabel('k')
plt.ylabel('轮廓系数')
plt.title('轮廓系数确定最佳的K值',fontdict={'fontsize':15})
输出结果：
轮廓系数看出，k=3时轮廓系数最大，肘部法的拐点亦是k=3，从数据集可视化图（文末案例）中也能看出数据集可以清洗分割 3 个簇（虽然初始创建了四个簇，但上面两个簇边界并不清晰，几乎连到一起）。
轮廓系数有很多优点，它在有限空间中取值，使得我们对模型的聚类效果有一个"参考"。并且，轮廓系数对数据的分 布没有假设，因此在很多数据集上都表现良好。但它在每个簇的分割比较清洗时表现最好。
「其它评估指标」
这里简单介绍「卡林斯基-哈拉巴斯指数」，有
个簇的聚类而言，
Calinski-Harabaz指数
写作如下公式:
其中
为数据集中的样本量，
为簇的个数(即类别的个数)，
是组间离散矩阵，即不同簇之间的协方差矩阵， 是
簇内离散矩阵，即一个簇内数据的协方差矩阵，而
表示矩阵的迹。在线性代数中，一个
矩阵
的主对角线(从左上方至右下方的对角线)上各个元素的总和被称为矩阵 A 的迹(或迹数)，一般记作
。
数据之间的离散程度越高，协方差矩阵的迹就会越大。组内离散程度低，协方差的迹就会越小，
也就越小，同时，组间离散程度大，协方差的的迹也会越大，
就越大，因此
「Calinski-harabaz指数越高越好」
虽然calinski-Harabaz指数没有界，在凸型的数据上的聚类也会表现虚高。但是比起轮廓系数，其计算非常快速。
K-Means 算法的优缺点
优点
- k-means 算法是解决聚类问题的一种经典算法， 算法简单、快速 。
- 算法尝试找出使平方误差函数值最小的 k 个划分。 当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好 。
缺点
- k-平均方法只有在簇的平均值被定义的情况下才能使用，且对有些分类属性的数据不适合。
- 要求用户必须事先给出要生成的簇的数目 k 。
- 对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。
- 不适合于发现非凸面形状的簇，或者大小差别很大的簇。
- 「KMeans 本质上是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性影响。「所以在聚类前对数据（「具体的说是每一个维度的特征」）做归一化和单位统一至关重要。此外，异常值会对均值计算产生较大影响，导致」中心偏移」，因此对于"噪声"和孤立点数据最好能提前过滤 。
原文链接
机器学习 | KMeans聚类分析详解mp.weixin.qq.com
猜你喜欢
机器学习合集mp.weixin.qq.com
转播
