聚类算法
前面介绍的集中算法都是属于有监督机器学习方法，这章和前面不同，介绍无监督学习算法，也就是聚类算法。在无监督学习中，目标属性是不存在的，也就是所说的不存在“y”值，我们是根据内部存在的数据特征，划分不同的类别，使得类别内的数据比较相似。
我们对数据进行聚类的思想不同可以设计不同的聚类算法，本章主要谈论三种聚类思想以及该聚类思想下的三种聚类算法。666
本章主要涉及到的知识点有：
“距离”
K-Means算法
几种优化K-Means算法
密度聚类
算法思想：“物以类聚，人以群分”
本节首先通过聚类算法的基本思想，引出样本相似度这个概念，并且介绍几种基本的样本相识度方法。
算法思想
俗话说：“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题。所谓类，通俗地说，就是指相似元素的集合。例如，我们刚生下来父母就开始教我们分类，给我们买很多卡片，告诉我们：（一定要用现实中的例子说名，注重趣味性）
“这是汽车。”。
“这是飞机。”
“这是鱼类。”
“这是鸟类。”
“这是圆。”
“这是长方形。”
“……。”
可见我们作为一个刚刚进入尘世的人，首先接触的就是分类了。然而到了今天，回顾我们的科学史，我们很多比较重要的就是发现一个新事物，然后给新事物分类。当然，我们眼里所熟悉的类别，都是根据常识，已经做好的分类。对于计算机来说，更具体一些，对于这里聚类算法；来说也是一样，只不过，通过算法把那些相识的数据划分在一起。这是我们本章主要解决的任务。
由上面可得我们本章的重点是将给定的数据划分为不同的数据类别，是类别之间的相识度最小。
如何将数据划分不同类别
通过计算样本之间的相识度，将相识度大的划分为一个类别。衡量样本之间的相识度的大小的方式有下面几种：
- 闵可夫斯基距离（Minkowski距离）也就是前面提到的范式距离
当p=1时为曼哈顿距离，公式如下（以二维空间为例）：
当p=2时，为欧几里得距离，公式如下：
当p=为无穷大时候，为切比雪夫距离，公式如下：
一般情况下用欧几里得距离比较多，当数据量出现扁平化时候，一般用切夫雪比距离。
- 夹角余弦相识度
假设两个样本有2个特征，
则这两个样本的夹角余弦相似度公式如下：
最常见的应用就是计算文本相似度。将两个文本根据他们词，建立两个向量，计算这两个向量的余弦值，就可以知道两个文本在统计学方法中他们的相似度情况。实践证明，这是一个非常有效的方法。
- 杰卡德相似系数（Jaccard）
适用于样本只有（0,1）的情况，又叫二元相似性，计算公式如下：
将杰卡德相似性度量应用到基于物品的协同过滤系统中，并建立起相应的评价分析方法。 与传统相似性度量方法相比，杰卡德方法完善了余弦相似性只考虑用户评分而忽略了其他信息量的弊端，特别适合于应用到稀疏度过高的数据。
类别的定义：簇
前面我们讲到把数据划分为不同类别，机器学习给这个类别定义一个新的名字—簇。
将具有M个样本的数据换分为k个簇，必然k<=M。簇满足以下条件：
q 每个簇至少包含一个对象
q 每个对象属于且仅属于一个簇
q 将上述条件的k个簇成为一个合理的聚类划分
对于给定的类别数目k,首先给定初始划分,通过迭代改变样本和簇的隶属关系,使的每次处理后得到的划分方式比上一次的好(总的数据集之间的距离和变小了）。
下面介绍一种最常用的一种最基本的算法—K-Means算法
K-Means算法
K- means算法,也称为K-平均或者K-均值,是一种使用广泛的最基础的聚类算法,一般作为掌握聚类算法的第一个算法。
K-Means构建步骤
K-Means算法过程
根据构建K-Means算法步骤用图表示出来结果如图所示：
我们用语言和公式来还原上述图解的过程：
原始数据集有N个样本，人为给定两个中心点。
-
分别计算每个样本到两个中心点之间的距离，可选欧几里得距离，计算公式用9.1所提到的公式如下所示：
image.png -
把样本分为了两个簇，计算每个簇中样本点的均值为新的中心点。计算公式如下：
image.png
- 重复以上步骤，知道达到前面所说中止条件。
8.1.1 K-Means的损失函数
我们的目的就是使得最终得到的中心点使得，每个样本到中心点和最小，每个样本到中心点距离公式为：
为了使损失函数最小，求偏导可以得到中心点的更新公式为：
K-Means算法遇到的问题
根据上面我们掌握的K-Means算法原理，发现有两个问题会很大影响K-Means算法。
K- means算法在迭代的过程中使用所有点的均值作为新的质点(中心点),如果簇中存在异常点,将导致均值偏差比较严重。例如：
一个簇中有2、4、6、8、100五个数据,那么新的质点为24,显然这个质点离绝大多数点都比较远;在当前情况下,使用中位数6可能比使用均值的想法更好,使用中位数的聚类方式叫做K- Mediods聚类(K中值聚类)-
初值敏感
K- means算法是初值敏感的,选择不同的初始值可能导致不同的簇划分规则。
为了避免这种敏感性导致的最终结果异常性,可以采用初始化多套初始节点构造不同的分类规则,然后选择最优的构造规则。
又或者改变初始值的选择。这样通过改进的K-Means算法，将在下面进行一一介绍。
下面给出一个初始值敏感的直观例子。给定一定的数据点如图9.3所示，我们明显等看到可以划分为四个区域：
假如我们随机给定的中心点A,B,C,D如图9.3所示：
我们按照 K-Means算法划分的结果如图9.4所示：
K-Means例题
基于scikit包中的创建的模拟数据的API进行数据的创建。使用K-Means对数据进行数据进行划分类，获得聚类中心。
- 数据构建。
创建的团状的数据集合，数据分布呈高斯分布状况。
from sklearn.datasets import make_blobs
N = 1000
centers = 4
创建呈现4个团状共1000个样本数据，样本有两个特征属性，
X, Y = make_blobs(n_samples=N, n_features=2, centers=centers, random_state=0)
- 模型构建
导入K-Means算法包，其底层就是按照前面讲的算法步骤一步一步创建的
from sklearn.cluster import KMeans
给出要划分的中心点树k，也可以给出算法中止条件，迭代次数，或者簇中心变化率。
km = KMeans(n_clusters=centers, init='random', random_state=28)
km.fit(X)
- 模型的预测
y_hat = km.predict(X)
- 求出模型的中心点坐标，并且得到，样本到中心点的总距离，也就是前面提到的损失函数。
print("所有样本距离所属簇中心点的总距离和为:%.5f" % km.inertia_) print("所有的中心点聚类中心坐标:") cluter_centers = km.cluster_centers_ print(cluter_centers) print("score其实就是所有样本点离所属簇中心点距离和的相反数:") print(km.score(X))
得到的结果如下：
所有样本距离所属簇中心点的总距离和为:1764.19457
所有的中心点聚类中心坐标:
[[-6.32351035 7.09545595]
[-7.51888142 -2.01003574]
[ 6.0528514 0.24636947]
[ 4.26881816 1.08317321]]
score其实就是所有样本点离所属簇中心点距离和的相反数:
-1764.19457007324
- 画图，把原始数据和最终预测数据在图上表现出来
import matplotlib.pyplot as plt import matplotlib as mpl
cm = mpl.colors.ListedColormap(list('rgby')) plt.figure(figsize=(15, 9), facecolor='w') plt.subplot(121) plt.title(u'原始数据') plt.grid(True) plt.scatter(X[:, 0], X[:, 1], c=Y, s=30, cmap=cm, edgecolors='none') plt.subplot(122) plt.scatter(X[:, 0], X[:, 1], c=y_hat, s=30, cmap=cm, edgecolors='none') plt.title(u'K-Means算法聚类结果') plt.grid(True) plt.show()
画图的结果如下：
当给定的簇中心的点分别为3，和5结果如下：
K-Means改进的几种算法
前面简单地介绍了一种聚类算法思想K-Means算法，由于K-Means算法的简单且易于实现，因此K-Means算法得到了很多的应用，但是从K-Means算法的过程中发现，K-Means算法中的聚类中心的个数k需要事先指定，这一点对于一些未知数据存在很大的局限性。其次，在利用K-Means算法进行聚类之前，需要初始化k个聚类中心，在上述的K-Means算法的过程中，使用的是在数据集中随机选择最大值和最小值之间的数作为其初始的聚类中心，但是聚类中心选择不好，对于K-Means算法有很大的影响。介绍几种K-Means改进的算法。
K-Means++算法
K-Means++算法在聚类中心的初始化过程中的基本原则是使得初始的聚类中心之间的相互距离尽可能远，这样可以避免出现上述的问题。从而可以解决K- Means算法对初始簇心比较敏感的问题,K- Means++算法和K- Means算法的区别主要在于初始的K个中心点的选择方面。
K- Means算法使用随机给定的方式,K- Means++算法采用下列步骤给定K个初始质点：
q 从数据集中任选一个节点作为第一个聚类中心
q 对数据集中的每个点ⅹ,计算x到所有已有聚类中心点的距离和D(X),基于D(X)采用线性概率（每个样本被选为下一个中心点的概率）选择出下一个聚类中心点距离较远的一个点成为新增的一个聚类中心点)
q 重复步骤2直到找到k个聚类中心点
这种由于依靠中心点和中心点之间的有序性进行中心点的划分，虽然避免了初始值敏感问题，可对于特别离散的数据，效果就不是很好了。
参考文献：Bahman Bahmani,Benjamin Moseley,Andrea Vattani.Scalable K-Means++
K-Meansll算法
k-means++ 最主要的缺点在于其内在的顺序执行特性，得到 k 个聚类中心必须遍历数据集 k 次，并且当前聚类中心的计算依赖于前面得到的所有聚类中心，这使得算法无法并行扩展，极大地限制了算法在大规模数据集上的应用。
这是一种针对K-Means++改进的算法，主要思路是改变每次遍历时候的取样规则,并非按照K- Means++算法每次遍历只获取一个样本,而是每次获取K个样本,重复该取样操作O(klogn)次,然后再将这些抽样出来的样本聚类出K个点,最后使用这K个点作为K- Means算法的初始聚簇中心点。一般情况下，重复几次就可以得到比较好的中心点。
二分K- Means算法
同样是为了解决K- Means算法对初始簇心比较敏感的问题,二分K- Means算法和前面两种寻找其他质心不同，它是一种弱化初始质心的一种算法。
这个算法的思想是：首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大程度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇（或者选择最大的簇等，选择方法多种）。以此进行下去，直到簇的数目等于用户给定的数目k为止。
算法的步骤如下：
q 将所有样本数据作为一个簇放到一个队列中
q 从队列中选择一个簇进行K- means算法划分,划分为两个子簇,并将子簇添加到队列中
q 循环迭代第二步操作,直到中止条件达到(聚簇数量、最小平方误差、迭代次数等)
q 队列中的簇就是最终的分类簇集合
从队列中选择划分聚簇的规则一般有两种方式;分别如下：
（1）对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种),选择SSE最大的聚簇进行划分操作(优选这种策略)
（2）选择样本数据量最多的簇进行划分操作
Canopy算法
Canopy Clustering 这个算法是2000年提出来的，此后与Hadoop配合，已经成为一个比较流行的算法了。确切的说，这个算法获得的并不是最终结果，它是为其他算法服务的，比如k-means算法。它能有效地降低k-means算法中计算点之间距离的复杂度。算法流程如下：
（1）给定样本列表L=x1,,2…,m以及先验值T1和T2(T1>T2)
（2）从列表L中获取一个节点P,计算P到所有聚簇中心点的距离(如果不存在聚簇中心,那么此时点P形成一个新的聚簇),并选择出最小距离D(P,aj)。
（3）如果距离D小于T1,表示该节点属于该聚簇,添加到该聚簇列表中
（4）如果距离D小于T2,表示该节点不仅仅属于该聚簇,还表示和当前聚簇中心点非常近,所以将该聚簇的中心点设置为该簇中所有样本的中心点,并将P从列表L中删除。
（5）如果距离D大于T1,那么节点P形成一个新的聚簇。
（6）直到列表L中的元素数据不再有变化或者元素数量为0的时候,结束循环操作。
该步骤用流程图表示如下图所示：
Canopy算法得到的最终结果的值,聚簇之间是可能存在重叠的,但是不会存在某个对象不属于任何聚簇的情况。
可以看到canopy算法将可以将一堆杂乱的数据大致的划分为几块所以Canopy算法一般会和kmeans算法配合使用来到达使用者的目的在使用Canopy算法时，阈值t1，t2的确定是十分重要的。t1的值过大，会导致更多的数据会被重复迭代，形成过多的Canopy；值过小则导致相反的效果t2的值过大，会导致一个canopy中的数据太多，反之则过少这样的情况都会导致运行的结果不准确。该算法的过程图形说明如图所示：
Mini batch k- Means算法
Mini Batch K-Means使用了一个种叫做Mini Batch（分批处理）的方法对数据点之间的距离进行计算。Mini Batch的好处是计算过程中不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。由于计算样本量少，所以会相应的减少运行时间，但另一方面抽样也必然会带来准确度的下降。这样使用于存在巨大的数据集合的情况下。
实际上，这种思路不仅应用于K-Means聚类，还广泛应用于梯度下降、深度网络等机器学习和深度学习算法。
该算法的算法流程和k- Means类似，流程如下：
（1）首先抽取部分数据集,使用K- Means算法构建出K个聚簇点的模型。
（2）继续抽取训练数据集中的部分数据集样本数据,并将其添加到模型中,分配给距离最近的聚簇中心点。
（3）更新聚簇的中心点值。
（4）循环迭代第二步和第三步操作,直到中心点稳定或者达到迭代次数,停止计算操作。
应用场景，由于Mini Batch KMeans跟K-Means是极其相似的两种聚类算法，因此应用场景基本一致。
后面我们就以 Mini batch k- Means算法为例子，比较一下它和 k- Means算法的区别。
8.1.1 聚类算法评估
有监督的分类算法的评价指标通常是accuracy, precision, recall, etc；由于聚类算法是无监督的学习算法，评价指标则没有那么简单了。因为聚类算法得到的类别实际上不能说明任何问题，除非这些类别的分布和样本的真实类别分布相似，或者聚类的结果满足某种假设，即同一类别中样本间的相似性高于不同类别间样本的相似性。
下面介绍几种常见的评估方法：
- 均一性又叫完整性
一个簇只包含一个类别样本，满足均一性，也可以认为正确率（每个簇中正确分类占该簇总样本的比），公式如下：
- 兰德系数（RI）
兰德系数（Rand index）需要给定实际类别信息C，假设K是聚类结果，a表示在C与K中都是同类别的元素对数，b表示在C与K中都是不同类别的元素对数，则兰德指数为：
分子：属性一致的样本数，即同属于这一类或都不属于这一类。a是真实在同一类、预测也在同一类的样本数；b是真实在不同类、预测也在不同类的样本数；
分母：任意两个样本为一类有多少种组合，是数据集中可以组成的总元素对数；
RI取值范围为[0,1]，值越大意味着聚类结果与真实情况越吻合。
对于随机结果，RI并不能保证分数接近零。为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（Adjusted rand index）被提出，它具有更高的区分度：
ARI取值范围为[-1,1]，值越大意味着聚类结果与真实情况越吻合。从广义的角度来讲，ARI衡量的是两个数据分布的吻合程度。
优点：
（1）对任意数量的聚类中心和样本数，随机聚类的ARI都非常接近于0；
（2）取值在［－1，1］之间，负数代表结果不好，越接近于1越好；
（3）可用于聚类算法之间的比较。
缺点：
ARI需要真实标签
- 轮廓系数 Silhouette Coefficient
轮廓系数适用于实际类别信息未知的情况。
簇内不相似度:计算样本i倒同簇其它样本的平均距离为a;a越小,表示样本越应该被聚类到该簇,簇C中的所有样本的a的均值被称为簇C的簇不相似度。
簇间不相似度:计算样本i到其它簇C的所有样本的平均距离b;b=min{b;1,bi2,bi};b越大,表示样本越不属于其它簇。
轮廓系数:s值越接近1表示样本麇类越合理,越接近-1,表示样本j应该分类到另外的簇中,近似为0,表示样本应该在边界上;所有样本的s的均值被成为聚类结果的轮廓系数。伦敦系数可以写作：
Scikit-learn中有兰求德系数方法metrics.silhouette_score。
Python中实现的代码如下：
from sklearn import metrics from sklearn.metrics import pairwise_distances
from sklearn import datasets
dataset = datasets.load_iris()
X = dataset.data
y = dataset.target
import numpy as np
from sklearn.cluster import KMeans
kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
labels = kmeans_model.labels_
metrics.silhouette_score(X, labels, metric='euclidean')
输出：
兰德系数为：
0.5730973570083832
示例：比较Mini batch k- Means算法和 k- Means算法
要求：给定较多数据，来比较两种算法的聚类速度，且用刚学到的聚类评估算法对，这两种算法进行评估。
两种的算法的API详情可以参考网址：
#第一个参数表示给定中心点的个数，第二个参数给出初始质心怎么给，第三个参数是多套初始质心，第四个代表的是迭代次数
sklearn.cluster.KMeans(n_clusters=8, init=’k-means++’, n_init=10, max_iter=300） [](#sklearn.cluster.MiniBatchKMeans "Permalink to this definition")
1. 导入模块。
#导入我们要用的包，包括算法数据创建模块，算法评估模块，算法模块。
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
2. 创建数据
#创建呈现3个团状共3000个样本数据，样本有两个特征属性，
#初始化三个中心 centers = [[1, 1], [-1, -1], [1, -1]] clusters = len(centers) #聚类的数目为3 #产生3000组二维的数据，中心是意思三个中心点，标准差是0.7 X, Y = make_blobs(n_samples=3000, centers=centers, cluster_std=0.7, random_state=0)
3. 模型构建
#构建kmeans算法 k_means = KMeans(init='k-means++', n_clusters=clusters, random_state=28) t0 = time.time() #当前时间 k_means.fit(X) #训练模型 km_batch = time.time() - t0 #使用kmeans训练数据的消耗时间 print ("K-Means算法模型训练消耗时间:%.4fs" % km_batch)
#构建MiniBatchKMeans算法 batch_size = 100 mbk = MiniBatchKMeans(init='k-means++', n_clusters=clusters, batch_size=batch_size, random_state=28) t0 = time.time() mbk.fit(X) mbk_batch = time.time() - t0 print ("Mini Batch K-Means算法模型训练消耗时间:%.4fs" % mbk_batch)
#输出的结果为：
L- Means算法模型训练消耗时间:0.0416s
M- Mini Batch K-Means算法模型训练消耗时间:0.0150s
4. 模型的预测
#预测结果 km_y_hat = k_means.predict(X) mbkm_y_hat = mbk.predict(X) print(km_y_hat[:10]) print(mbkm_y_hat[:10]) print(k_means.cluster_centers_) print(mbk.cluster_centers_)
#输出的结果：
[0 1 0 2 1 1 1 1 2 1]
[[-1.07159013 -1.00648645]
[ 0.96700708 1.01837274]
[ 1.07705469 -1.06730994]]
[[ 1.02538969 -1.08781328]
[-1.06046903 -1.01509453]
[ 0.97734743 1.08610316]]
5.求出质心得坐标并进行排序：
##获取聚类中心点并聚类中心点进行排序 k_means_cluster_centers = k_means.cluster_centers_#输出kmeans聚类中心点 mbk_means_cluster_centers = mbk.cluster_centers_#输出mbk聚类中心点 print ("K-Means算法聚类中心点:\ncenter=", k_means_cluster_centers) print ("Mini Batch K-Means算法聚类中心点:\ncenter=", mbk_means_cluster_centers) order = pairwise_distances_argmin(k_means_cluster_centers, mbk_means_cluster_centers)
得到的结果如下：
K-Means算法聚类中心点:
center= [[-1.07159013 -1.00648645]
[ 0.96700708 1.01837274]
[ 1.07705469 -1.06730994]]
### Mini Batch K-Means算法聚类中心点:
center= [[ 1.02538969 -1.08781328]
[-1.06046903 -1.01509453]
[ 0.97734743 1.08610316]]
6. 画图，把原始数据和最终预测数据在图上表现出来
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'])
7. 创建各个子图：
#子图1：原始数据 plt.subplot(221) plt.scatter(X[:, 0], X[:, 1], c=Y, s=6, cmap=cm, edgecolors='none') plt.title(u'原始数据分布图') plt.grid(True) #子图2：K-Means算法聚类结果图 plt.subplot(222) plt.scatter(X[:,0], X[:,1], c=km_y_hat, s=6, cmap=cm,edgecolors='none') plt.scatter(k_means_cluster_centers[:,0], k_means_cluster_centers[:,1],c=range(clusters),s=60,cmap=cm2,edgecolors='none') plt.title(u'K-Means算法聚类结果图') plt.text(-3.8, 3, 'train time: %.2fms' % (km_batch*1000)) plt.grid(True) #子图三Mini Batch K-Means算法聚类结果图 plt.subplot(223) plt.scatter(X[:,0], X[:,1], c=mbkm_y_hat, 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.text(-3.8, 3, 'train time: %.2fms' % (mbk_batch*1000)) plt.grid(True)
8. 创建两则分不同的点子图：
different = list(map(lambda x: (x!=0) & (x!=1) & (x!=2), mbkm_y_hat)) for k in range(clusters): different += ((km_y_hat == k) != (mbkm_y_hat == 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='m', marker='.') plt.title(u'Mini Batch K-Means和K-Means算法预测结果不同的点') plt.xticks(()) plt.yticks(()) plt.text(-3.8, 2, 'different nodes: %d' % (different_nodes)) plt.show()
- 输出结果如下：
分析：从上图，我们看出Mini batch k- Means算法比 k- Means算法速度快了不止一倍，而效果还是不错的。
思考：如果出现如图9.7所示出现的数据类型用类 k- Means算法就不能正确地对他们进行聚类了，因为他们属于非凸类数据。这时候就要转变聚类思想了，采用别的聚类方法了。
本章小结
本章主要介绍了聚类中的一种最常见的算法—K-Means算法以及其优化算法，聚类是一种无监督学习的方法。我们通过簇来把数据划分为不同的种类，介绍了该算法的构建流程，根据构建的流程中的初始值敏感问题，我们对最基本的K-Means算法进行了改进，其中Mini batch k- Means算法可以适用于数据量比较多的情况，且效果也不错。
本章的最后我们根据样本不同的特征，有时候不适合采用K-Means算法，我们将在下一章介绍几种其他思想产生的算法。
