7.机器学习--K-means算法（聚类）

聚类分析是在没有给定划分类别的情况下，根据数据相似度进行样本分组的一种方法。与分类模型需要使用有类标记样本构成的训练数据不同，聚类模型可以建立在无类标记的数据上，是一种非监督的学习算法。

聚类的输入是一组未被标记的样本，聚类根据数据自身的距离或相似度将它们划分为若干个簇，划分的原则就是使簇内样本相似性最大，簇与簇之间的相似性最小。

1.数据性能度量

2.聚类主要算法

2.1.k-means聚类算法

2.2.模糊C-means聚类算法（FCM）

2.3.层次聚类算法

2.4.DBSCAN 算法

3.K-means 算法原理

4.引申问题

4.1.k 值应该如何确定？

4.2.如何选取初始中心点？

3.如何实现

5.代码示例

5.1.鸢尾花聚类

5.2.顾客订单聚类

1.数据性能度量

聚类性能度量也称为聚类的“有效性指标”，和监督学习的准确率，查准率等类似，对于聚类结果我们需要有一个明确的评价指标评估聚类好坏，在另一方面，我们可以把性能指标直接作为聚类过程中的优化目标，从而更好地得到符合要求的聚类结果。

聚类性能度量大概可以分为两类，一是将聚类结果与某个“参考模型“进行比较，可以称为”外部指标“；另一类是直接参考聚类簇见的一些特征，称为‘内部指标”

外部指标主要有：

Jaccard系数（Jaccard Coefficient, JC）
FM指数（Fowlkes and Mallows Index, FMI）
Rand指数（Rand Index, RI）
F值（F-measure）

上述性能度量的结果值均在[0,1]区间，值越大越好，值越大表明聚类结果和参考模型（有标签的、人工标准或基于一种理想的聚类的结果）直接的聚类结果越吻合，聚类结果就相对越好。

内部指标有：

紧密度（Compactness）：每个聚类簇中的样本点到聚类中心的平均距离。对应聚类结果，需要使用所有簇的紧密度的平均值来衡量聚类算法和聚类各参数选取的优劣。紧密度越小，表示簇内的样本点月集中，样本点之间聚类越短，也就是说簇内相似度越高。比如我们比较熟悉的欧氏距离、曼哈顿距离等，都是度量簇紧密程度的指标。
分割度（Seperation）：是个簇的簇心之间的平均距离。分割度值越大说明簇间间隔越远，分类效果越好，即簇间相似度越低。
戴维森堡丁指数（Davies-bouldin Index,DBI):该指标用来衡量任意两个簇的簇内距离之后与簇间距离之比。该指标越小表示簇内距离越小，簇内相似度越高，簇间距离越大，簇间相似度低。
邓恩指数（Dunn Validity Index,DVI）:任意两个簇的样本点的最短距离与任意簇中样本点的最大距离之商。该值越大，聚类效果越好。
轮廓系数（Silhouette Coefficient）：对于一个样本集合，它的轮廓系数是所有样本轮廓系数的平均值。轮廓系数的取值范围是[-1,1]，同类别样本距离越相近不同类别样本距离越远，分数越高。

2.聚类主要算法

2.1.k-means聚类算法

K-means 算法是一种最基本的基于距离的划分的无监督聚类算法，为十大数据挖掘算法之一。K-means 算法在对所给数据集进行聚类时，采用的是“非此即彼”的硬聚类方式。其中 K 是指簇的数量，means是指均值。

k-means 算法的优点

简单快捷，容易理解；
可伸缩性好且效率高；
对所有的数据样本都进行聚类；
对满足高斯分布、均匀分布的数据类型聚类效果表较好

k-means算法的缺点

对初始聚类中心敏感；
需要事先确定聚类个数；
对孤立点和噪声点相对敏感；

针对K-means 算法中的K 值及初始中心点的事先确定，已经有很多相关的成熟的理论研究和工程应用。特别地，对K-means 算法在使用时需要事先确定K 值的难点问题，团队在先前的项目中已经做过大量的研究，并提出有效的确定 K 值的方法。

2.2.模糊C-means聚类算法（FCM）

FCM 算法是Bezdek 在1973 年提出的一种基于划分的模糊聚类算法。该算法是采用隶属度来确定每个数据点属于某个聚类程度的一种方法。相比于K-means 算法，FCM则是一种柔性的模糊划分法。思想就是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。模糊C均值算法是普通C均值算法的改进，普通C均值算法对于数据的划分是硬性的，而FCM则是一种柔性的模糊划分。

FCM算法的优点

具有深厚的数学基础；
不易陷入局部最优解；
对满足正态分布的数据聚类效果很好；

FCM算法的不足

对孤立点敏感；
需事先确定隶属度参数m 和聚类数目K；

2.3.层次聚类算法

层次聚类算法是将所有的数据集自底向上合并成一棵树或自顶向下分裂成一棵树的过程，这两种方式分别称为凝聚和分裂。对凝聚层次聚类算法，在初始阶段，将每个样本点分别当作其类簇，然后合并这些原子类簇直到达到预期的类簇数或者其他终止条件；而对于分裂层次的聚类算法，在初始阶段，将所有的样本点当作同一类簇，然后分裂这个大类簇直至达到预期的类簇数或者其他终止条件。

层次聚类算法的优点

不需要预先制定聚类数；
可以发现类的层次关系；
当改变聚类的数目时，不需要再次计算数据点的归属。

层次聚类算法的不足

计算复杂度太高；
算法很可能聚类成链状；
奇异值会对聚类效果有很大的影响。

2.4.DBSCAN 算法

DBSCAN 算法是一种基于密度的空间聚类算法。该算法要求聚类空间中的一定区域内所包含对象（点或其他空间对象）的数目不小于某一给定领域密当改变聚类的数目时，不需要再次计算数据点的归属。度阈值，即将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连点的最大集合。

DBSCAN 算法的优点：

能够识别出噪声点；
可以发现任意形状的簇类；
不需要事先知道要形成的簇类数量。

DBSCAN 算法的不足：

算法的计算复杂度较高；
对不满足给定条件的样本点会作为噪声点剔除；
对稀疏的高维数据性能差，因对高维数据，欧几里得密度定义不能很好理解；
因算法直接对数据库进行操作，当数据量增大时，要求较大的内存支持且I/O消耗也很大；
算法聚类时采用全局性的表征密度参数，当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差；

算法使用首先必须确定 K 的值也就是聚类数量

3.K-means 算法原理

算法的步骤用文字描述可以总结为一下四步：

第一步：初始化聚类中心

根据给定的k值随机选取k个样本作为初始的聚类中心。

第二部：根据聚类中心划分簇

计算每个样本与各个聚类中心之间的距离，把每个样本分配给距离他最近的聚类中心。

第三步：重新选择聚类中心

将每个聚类中所有样本的平均值确定为新的聚类中心

第四步：停止移动

重复第2步，直到聚类中心不再移动或达到最大迭代次数为止。

如下图(a)(b)(c)(d)(e)(f)所示：

用伪代码的形式表示就是：

1选择K个点作为初始质心  
2repeat  
3    将每个点指派到最近的质心，形成K个簇  
4    重新计算每个簇的质心  
5until 簇不发生变化 or 达到最大迭代次数

注意：K-means算采用的是迭代的方法，得到局部最优解

4.引申问题

4.1.k 值应该如何确定？

通常情况下有如下几种思路可以帮助我们确定 k 值：

多次选取尝试不同 k 值，对比聚类效果，选择最优的 k 值；
根据业务特点，比如想聚类划分淘宝购物客户的性别，那么就设定 k = 2；
当选取的 k 值变大超过某个值后，聚类中来的簇平方直径会发生变化，因此可以根据这一特点选取处于平均直径变化临界点的那个 k 值；

4.2.如何选取初始中心点？

在如何选取聚类中心点上午可以引申出K-means的几种改进形式：

K-means++：

根据K-means算法原理可知，这算法存在一个根本缺陷就是极其依赖簇中心的初始化状态，如果很不巧选取的 k 个初始化簇中心都在一个簇中，那么在这种情况下聚类算法很大程度上都不会收敛到全局最小值。考虑到这个问题k-means++要求选择初始的聚类中心之间的相互距离要尽可能的远，其他地方同k-means算法一样
二分K-means：

这个算法的思想是：首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大程度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇（或者选择最大的簇等，选择方法多种）。以此进行下去，直到簇的数目等于用户给定的数目k为止。

3.如何实现

我们这里直接给出 sklearn 朴素贝叶斯分类算法 API：

1sklearn.cluster.KMeans(n_clusters, *, init='k-means++', n_init=10, max_iter=300, random_state=None, n_jobs='deprecated')

这里只列出其中比较重要的几个参数：

n_clusters： int型，生成的聚类数，默认为8
max_iter： int型，执行一次k-means算法所进行的最大迭代数。默认值为300
n_init： int型，用不同的聚类中心初始化值运行算法的次数，最终解是在inertia意义下选出的最优结果。默认值为10
init： 有三个可选值：‘k-means++’、‘random’、或者传递一个ndarray向量。
１）‘k-means++’ 用一种特殊的方法选定初始质心从而能加速迭代过程的收敛
２）‘random’ 随机从训练数据中选取初始质心。
３）如果传递的是一个ndarray，则应该形如 (n_clusters, n_features) 并给出初始质心。
默认值为‘k-means++’。
random_state： 整形或 numpy.RandomState 类型，可选
用于初始化质心的生成器（generator）。如果值为一个整数，则确定一个seed。此参数默认值为numpy的随机数生成器。

我们可以通过下面的实例感受一下k-means的聚类过程👇

5.代码示例

5.1.鸢尾花聚类

Iris 鸢尾花数据集是一个经典数据集，在统计学习和机器学习领域都经常被用作示例。数据集内包含 3 类共 150 条记录，每类各 50 个数据，每条记录都有 4 项特征：花萼长度、花萼宽度、花瓣长度、花瓣宽度，可以通过这4个特征预测鸢尾花卉属于（iris-setosa, iris-versicolour, iris-virginica）中的哪一品种。

特征名称	描述
sepal length (cm)	花萼长度（厘米）
sepal width (cm)	花萼宽度（厘米）
petal length (cm)	花瓣长度（厘米）
petal width (cm)	花瓣宽度（厘米）

1.画出散点图

import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans
#from sklearn import datasets
from sklearn.datasets import load_irisiris = load_iris()
X = iris.data[:] ##表示我们只取特征空间中的后两个维度
#绘制数据分布图
##散点图，plt.scatter(x（横轴数据）,y（纵轴数据）,c="颜色"，marker="点的形状"，labal='点的标签')
plt.scatter(X[:, 0], X[:, 1], c = "red", marker='.', label='see')
##设置x，y轴的名字
plt.xlabel('petal length')
plt.ylabel('petal width')
##设置图的名字
plt.title("Data")
##显示图像
plt.show()

2.K-means聚类

                        #请完成这部分代码，实现构造聚类器,n_clusters定义初始簇心数量为3
n_clusters=3
estimator=KMeans(n_clusters=n_clusters)
estimator.fit(X)#聚类
label_pred = estimator.labels_ #获取聚类标签
#绘制k-means结果
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c = "red", marker='o', label='label0')
plt.scatter(x1[:, 0], x1[:, 1], c = "green", marker='*', label='label1')
plt.scatter(x2[:, 0], x2[:, 1], c = "blue", marker='+', label='label2')
plt.xlabel('petal length')
plt.ylabel('petal width')
plt.legend(loc=2)
plt.show()

3.MiniBatchKMeans聚类

初始化聚类中心：随机选择数据集中的 K 个点作为初始聚类中心。

选择一个 mini-batch：从数据集中随机选择一个包含 n 个样本的 mini-batch。

分配样本到最近的聚类中心：对于 mini-batch 中的每个样本，找到最近的聚类中心，并将样本分配给该聚类。

更新聚类中心：对于每个聚类，计算分配给它的所有样本的平均值，并用这个平均值更新聚类中心。

重复步骤 2 到 4：重复选择 mini-batch、分配样本和更新聚类中心的过程，直到满足停止条件（如达到最大迭代次数或聚类中心的变化小于某个阈值）。

返回聚类结果：最终，每个样本都被分配到一个聚类中心，聚类过程结束。

from sklearn.cluster import MiniBatchKMeans
estimator2 =MiniBatchKMeans(n_clusters=3,batch_size=100)#请完成这部分代码，实现
#构造聚类器,n_clusters定义初始簇心数量为3，batch_size=100定义批量处理数据量，这里请自行了解minibatchKmeans的实现过程label_pred = estimator2.fit_predict(X)   #聚类#获取聚类标签
#绘制k-means结果
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c = "red", marker='o', label='label0')
plt.scatter(x1[:, 0], x1[:, 1], c = "green", marker='*', label='label1')
plt.scatter(x2[:, 0], x2[:, 1], c = "blue", marker='+', label='label2')
plt.xlabel('petal length')
plt.ylabel('petal width')
plt.legend(loc=2)
plt.show()

4.DBSCAN聚类


from sklearn.cluster import DBSCAN
estimator3 = DBSCAN(eps=0.38,min_samples=3)#构造聚类器
#eps定义ϵ-邻域，min_samples定义MinPts，即每个核心对象的ϵ-邻域内至少要有多少个样本label_pred = estimator3.fit_predict(X)  #聚类#获取聚类标签
#绘制k-means结果
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c = "red", marker='o', label='label0')
plt.scatter(x1[:, 0], x1[:, 1], c = "green", marker='*', label='label1')
plt.scatter(x2[:, 0], x2[:, 1], c = "blue", marker='+', label='label2')
plt.xlabel('petal length')
plt.ylabel('petal width')
plt.legend(loc=2)
plt.show()

5.使用AGNES聚类

from sklearn.cluster import AgglomerativeClustering
estimator4 = AgglomerativeClustering(linkage='ward', n_clusters=3)
#n_clusters：聚类个数
#affinity：#计算距离的指标（比如欧式距离）,"euclidean", "l1", "l2","manhattan", "cosine"
#linkage：簇距离计算方式（单连接，全连接，均连接）estimator4.fit(X) #聚类
label_pred = estimator4.labels_ #获取聚类标签
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c = "red", marker='o', label='label0')
plt.scatter(x1[:, 0], x1[:, 1], c = "green", marker='*', label='label1')
plt.scatter(x2[:, 0], x2[:, 1], c = "blue", marker='+', label='label2')
plt.xlabel('petal length')
plt.ylabel('petal width')plt.title("AGNES Clustering")
plt.show()

全部代码：

import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans
#from sklearn import datasets
from sklearn.datasets import load_irisiris = load_iris()
X = iris.data[:] ##表示我们只取特征空间中的后两个维度
#绘制数据分布图
##散点图，plt.scatter(x（横轴数据）,y（纵轴数据）,c="颜色"，marker="点的形状"，labal='点的标签')
plt.scatter(X[:, 0], X[:, 1], c = "red", marker='.', label='see')
##设置x，y轴的名字
plt.xlabel('petal length')
plt.ylabel('petal width')
##设置图的名字
plt.title("Data")
##显示图像
plt.show()#请完成这部分代码，实现构造聚类器,n_clusters定义初始簇心数量为3
n_clusters=3
estimator=KMeans(n_clusters=n_clusters)
estimator.fit(X)#聚类
label_pred = estimator.labels_ #获取聚类标签
#绘制k-means结果
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c = "red", marker='o', label='label0')
plt.scatter(x1[:, 0], x1[:, 1], c = "green", marker='*', label='label1')
plt.scatter(x2[:, 0], x2[:, 1], c = "blue", marker='+', label='label2')
plt.xlabel('petal length')
plt.ylabel('petal width')
plt.legend(loc=2)
plt.show()from sklearn.cluster import MiniBatchKMeans
estimator2 =MiniBatchKMeans(n_clusters=3,batch_size=100)#请完成这部分代码，实现
#构造聚类器,n_clusters定义初始簇心数量为3，batch_size=100定义批量处理数据量，这里请自行了解minibatchKmeans的实现过程label_pred = estimator2.fit_predict(X)   #聚类#获取聚类标签
#绘制k-means结果
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c = "red", marker='o', label='label0')
plt.scatter(x1[:, 0], x1[:, 1], c = "green", marker='*', label='label1')
plt.scatter(x2[:, 0], x2[:, 1], c = "blue", marker='+', label='label2')
plt.xlabel('petal length')
plt.ylabel('petal width')
plt.legend(loc=2)
plt.show()from sklearn.cluster import DBSCAN
estimator3 = DBSCAN(eps=0.38,min_samples=3)#构造聚类器
#eps定义ϵ-邻域，min_samples定义MinPts，即每个核心对象的ϵ-邻域内至少要有多少个样本label_pred = estimator3.fit_predict(X)  #聚类#获取聚类标签
#绘制k-means结果
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c = "red", marker='o', label='label0')
plt.scatter(x1[:, 0], x1[:, 1], c = "green", marker='*', label='label1')
plt.scatter(x2[:, 0], x2[:, 1], c = "blue", marker='+', label='label2')
plt.xlabel('petal length')
plt.ylabel('petal width')
plt.legend(loc=2)
plt.show()from sklearn.cluster import AgglomerativeClustering
estimator4 = AgglomerativeClustering(linkage='ward', n_clusters=3)
# n_clusters：聚类个数
# affinity：#计算距离的指标（比如欧式距离）,"euclidean", "l1", "l2","manhattan", "cosine"
# linkage：簇距离计算方式（单连接，全连接，均连接）estimator4.fit(X)  # 聚类
label_pred = estimator4.labels_  # 获取聚类标签
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c="red", marker='o', label='label0')
plt.scatter(x1[:, 0], x1[:, 1], c="green", marker='*', label='label1')
plt.scatter(x2[:, 0], x2[:, 1], c="blue", marker='+', label='label2')
plt.xlabel('petal length')
plt.ylabel('petal width')plt.title("AGNES Clustering")
plt.show()

5.2.顾客订单聚类


import numpy as np
import pandas as pd
import matplotlib as mpl
import matplotlib.pyplot as pltdata = pd.read_csv(r'C:\pythonProject\机器学习\聚类算法\order.csv')   #加载data/data95120目录下的order.csv文件
# 查看数据
# 选取每个顾客所购买各个商品所占的比重信息来进行聚类
t = data.iloc[:, -8:]
print(t)class KMeans:'''使用python语言实现聚类算法'''def __init__(self, k, times):'''k : int聚类的个数times : int聚类迭代的次数'''self.k = k  # 设置聚类的个数为kself.times = times  # 设置迭代的次数为timesdef fit(self, X):'''根据提供的训练数据，对模型进行训练。Parameters------X : 类数组类型，形状为：[样本数量，特征数量]待训练的样本特征属性。'''X = np.asarray(X)  # 将输入数据转换为NumPy数组# 设置随机种子，以便于可以产生相同的随机序列。（随机的结果可以重现。）np.random.seed(0)# 从随机数组中随机选择k个点作为初始聚类中心。self.cluster_centers_ = X[np.random.randint(0, len(X), self.k)]# 用来存放每个点所处的组或簇self.labels_ = np.zeros(len(X))for i in range(self.times):for index, x in enumerate(X):# 计算每个样本与聚类中心的距离，采用欧式距离dis = np.sqrt(np.sum((x - self.cluster_centers_) ** 2, axis=1))# 将最小的索引赋值给标签数组。索引的值是当前点所属的簇。范围为[0, k - 1]self.labels_[index] = dis.argmin()# 循环遍历每一个簇for i in range(self.k):# 计算每个簇内所有点的均值，更新聚类中心self.cluster_centers_[i] = np.mean(X[self.labels_ == i], axis=0)def predict(self, X):'''根据参数传递的样本，对样本数据进行预测。（预测样本属于哪一个簇中）Parameters-----X : 类数组类型。形状为：[样本数量，特征数量]待预测的特征属性。Returns-----result : 数组类型预测的结果。每一个X所属的簇。'''X = np.asarray(X)  # 将输入数据转换为NumPy数组result = np.zeros(len(X))  # 初始化预测结果数组for index, x in enumerate(X):# 计算样本到每个聚类中心的距离dis = np.sqrt(np.sum((x - self.cluster_centers_) ** 2, axis=1))# 找到距离最近的聚类中心，划分类别。result[index] = dis.argmin()return result  # 返回预测结果kmeans = KMeans(3, 50)
kmeans.fit(t)# 查看某个簇的所有样本数据。
t[kmeans.labels_ == 0]# 简单进行预测
kmeans.predict([[30, 30, 40, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 30, 30, 40], [30, 30, 0, 0, 0, 0, 20, 20]])# 可视化
# 选取 Food% Fresh% 两个特征
t2 = data.loc[:, "Food%":"Fresh%"]
kmeans = KMeans(3, 50)
kmeans.fit(t2)# 如果想显示中文的话，可以看这一段，默认情况下，matplotlib不支持中文显示，进行以下设置
# 设置字体为黑体，以支持中文显示
mpl.rcParams['font.family'] = 'SimHei'
# 设置在中文字体时，能够正常的显示负号（-）
mpl.rcParams['axes.unicode_minus'] = Falseplt.figure(figsize=(10, 10))
# 绘制每个类别的散点图
plt.scatter(t2[kmeans.labels_ == 0].iloc[:, 0], t2[kmeans.labels_ == 0].iloc[:, 1], label='Category 1')
plt.scatter(t2[kmeans.labels_ == 1].iloc[:, 0], t2[kmeans.labels_ == 1].iloc[:, 1], label='Category 2')
plt.scatter(t2[kmeans.labels_ == 2].iloc[:, 0], t2[kmeans.labels_ == 2].iloc[:, 1], label='Category 3')
# 绘制聚类中心
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], marker='+', s=300)
plt.title('Cluster analysis of food and meat purchases')
plt.xlabel('food')
plt.ylabel('meat')
plt.legend()
plt.show()