机器学习(六)：K-means聚类原理及案例分析

2019-12-19 本文已影响0人风之舟

一、算法简介

1、监督学习和非监督学习

监督学习

监督学习是根据已有的数据集，知道输入和输出结果之间的关系。根据这种已知的关系，训练得到一个最优的模型。也就是说，在监督学习中训练数据既有特征又有标签，通过训练，让机器可以自己找到特征和标签之间的联系，在面对只有特征没有标签的数据时，可以判断出标签。监督学习中的常用算法包括线性回归、逻辑回归、朴素贝叶斯、支持向量机、人工神经网络和随机森林。在回归和分类中，目标都是找到输入数据中的特定关系或结构，以便我们有效地生成正确的输出数据。

非监督学习

非监督学习是我们不知道数据集中数据和特征之间的关系，而是要根据聚类或一定的模型得到数据之间的关系。在非监督学习中，我们知识给定了一组数据，我们的目标是发现这组数据中的特殊结构。例如我们使用非监督学习算法会将这组数据分成两个不同的簇，这样的算法就叫聚类算法。

2、K-means算法

K均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法，是非监督学习算法的一种，其算法思想大致为：先从样本集中随机选取K个样本作为簇中心，并计算所有样本与这k个"簇中心"的距离，对于每一个样本，将其划分到与其距离最近的"簇中心"所在的簇中，对于新的簇计算各个簇的新的"簇中心"。
根据以上描述，我们大致可以猜测到实现kmeans算法的主要三点：

簇个数k的选择
各个样本点到"簇中心"的距离
根据新划分的簇，更新"簇中心"

二、算法原理

1、原理

随机设置K个特征空间内的点作为初始的聚类中心
对于其他每个点计算到k个中心点的距离，选择最近的一个聚类中心点作为标记类别
接着对着标记的聚类中心，重新计算出每个聚类点的平均值
如果计算得出的新中心点与原中心点一样，那么结束，否则把新的平均值点作为新的中心，重新进行第二步过程

2、优化目标
$min\sum_{i=1}^K\sum_{x\in C_{i}}dist(C_{i},x)^2$
注：K是中心点，即簇数目； $C_{i}$ 表示每个簇内的中心点，x属于每个簇内的样本点；我们的目的是优化每个簇的点使得它到样本中心点的距离是最短的。
3、算法的性能评估指标
轮廓系数：
$SC_{i}=\frac{b_{i}-a_{i}}{max(b_{i},a_{i})}$ 注：对于每个点 $i$ 为已聚类数据中的样本， $b_{i}$ 为 $i$ 到其他簇群的所有样本的距离最小值， $a_{i}$ 为i到本身簇的距离平均值，最终计算出所有的样本点的轮廓系数平均值。
这里我们举个例子说明：

上图我们按照评估指标看一下，以蓝色样本为例，
1、计算蓝1到自身类别的点距离的平均值记为
2、计算蓝1分别到紅色类别，绿色类别所有点的距离，求出平均值,取其中最下的值记为
我们讨论一下极端的情况：

好情况（ $b_{i}$ >> $a_{i}$ ）
$SC_{i} =1$
坏情况（ $b_{i}$ << $a_{i}$ ）
$SC_{i} =-1$
所以轮廓系数的取值范围应该在[-1,1]之间，越靠近1说明聚类的效果越好。
关于轮廓系数的求解，sklearn算法包中有封装好的轮廓系数API，我们可以直接调用:
sklearn.metric.sihouette_score(X,labels)
计算所有样本的平均轮廓系数
X：特征值
labels:被聚类标记的目标值

4、算法的使用
关于k-means算法的使用，由于k-means比较简单，我们这里仍然使用sklearn包中封装好的k-means的API,
sklearn.cluster.KMeans(n_clusters=8,init='k-means++')

n_clusters：开始的聚类中心数量
init：初始化方法，默认为'k-means++'
labels_：默认标记的类别，可以和真实值比较（不是值的比较）

接下来，我们用实例来看一下API的使用。

三、案例讲解

案例用到的数据集是给出啤酒的一些成分，将这些啤酒进行聚类，首先我们先看一下数据集，这个数据集非常小，只有19个样本，我们进行简单的演示，

首先我们先用k-means算法进行聚类，

import pandas as pd
from pandas.plotting import scatter_matrix
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
def kmeans():
    """
    Kmeams聚类分析啤酒
    :return:
    """
    #读取数据
    data = pd.read_table('../../../数据集/机器学习/聚类算法/啤酒成分和价格/beer.txt',sep=' ',error_bad_lines=False)
    print(data)

    #提取特征值
    X = data.loc[:,['calories','sodium','alcohol','cost']]
    # print(x)

    #使用Kmeans聚类
    kmean = KMeans(n_clusters=3)
    km = kmean.fit(X)
    data['cluster'] = km.labels_
    centers = data.groupby("cluster").mean().reset_index()
    # print(centers)
    #画图，四个特征量量比较
    plt.rcParams['font.size'] = 14
    colors = np.array(['red','green','blue','yellow'])
    plt.scatter(data['calories'],data['alcohol'],c=colors[data["cluster"]])
    plt.scatter(centers.calories,centers.alcohol,linewidths=3,marker='+',s=300,c='black')#中心点
    plt.xlabel("Calories")
    plt.ylabel("Alcohol")
    plt.show()
    return None

if __name__ == "__main__":
    kmeans()

我们顺便用图像画一下聚类的效果，

我们还可以将四个特征两两比较，

import pandas as pd
from pandas.plotting import scatter_matrix
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
def kmeans():
    """
    Kmeams聚类分析啤酒
    :return:
    """
    #读取数据
    data = pd.read_table('../../../数据集/机器学习/聚类算法/啤酒成分和价格/beer.txt',sep=' ',error_bad_lines=False)
    print(data)

    #提取特征值
    X = data.loc[:,['calories','sodium','alcohol','cost']]
    # print(x)

    #使用Kmeans聚类
    kmean = KMeans(n_clusters=3)
    km = kmean.fit(X)
    data['cluster'] = km.labels_
centers = data.groupby("cluster").mean().reset_index()
    # print(centers)
    # 画图，四个特征量量比较
    plt.rcParams['font.size'] = 14
    colors = np.array(['red','green','blue','yellow'])
    plt.scatter(data['calories'],data['alcohol'],c=colors[data["cluster"]])
    plt.scatter(centers.calories,centers.alcohol,linewidths=3,marker='+',s=300,c='black')#中心点
    plt.xlabel("Calories")
    plt.ylabel("Alcohol")
    #
    scatter_matrix(data[['calories','sodium','alcohol','cost']],s=100,alpha=1,c = colors[data["cluster"]],figsize=(15,15))
    plt.suptitle("初始化成3类")
    plt.show()
    return None

if __name__ == "__main__":
    kmeans()

我们可以通过横纵坐标进行两两特征的比较。
我们还可以对数据进行标准化，然后对比没有进行标准化后的效果。
我们先看一下标准化后的数据（标准化的代码在后面有），

接下来我们对标准化后的数据进行聚类看一下轮廓系数评估结果，

import pandas as pd
from pandas.plotting import scatter_matrix
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
def kmeans():
    """
    Kmeams聚类分析啤酒
    :return:
    """
    #读取数据
    data = pd.read_table('../../../数据集/机器学习/聚类算法/啤酒成分和价格/beer.txt',sep=' ',error_bad_lines=False)
    #print(data)

    #提取特征值
    X = data.loc[:,['calories','sodium','alcohol','cost']]
    # print(x)

    #使用Kmeans聚类
    kmean = KMeans(n_clusters=3)
    km = kmean.fit(X)
    data['cluster'] = km.labels_
    #我们进行标准化看看效果
    std = StandardScaler()
    x = std.fit_transform(X)
    # print(x)
    kms = kmean.fit(x)
    data["cluster_std"] = kms.labels_
    #print(data)
    #使用轮廓系数进行评估
    sht = silhouette_score(X,data.cluster)  #没有进行标准化的评估值
    sht2 = silhouette_score(x,data.cluster_std)
    print(sht)
    print(sht2)
    return None

if __name__ == "__main__":
    kmeans()

第一个是没有标准化的数据聚类后的效果0.67，第二个是标准化后的数据聚类结果0.44，通过结果来看，数据标准化不一定会使结果更优。
我们还可以比较一下将K值设置的更大的时候的效果，举例将k设置为[2,19]并将效果图画出来看一下，

import pandas as pd
from pandas.plotting import scatter_matrix
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
def kmeans():
    """
    Kmeams聚类分析啤酒
    :return:
    """
    #读取数据
    data = pd.read_table('../../../数据集/机器学习/聚类算法/啤酒成分和价格/beer.txt',sep=' ',error_bad_lines=False)
    # print(data)

    #提取特征值
    X = data.loc[:,['calories','sodium','alcohol','cost']]
    # print(x)

    #使用Kmeans聚类
    kmean = KMeans(n_clusters=3)
    km = kmean.fit(X)
    data['cluster'] = km.labels_
    
    scores = []
    for i in range(2,19):
        labels = KMeans(n_clusters=i).fit(X).labels_
        score = silhouette_score(X,labels)
        scores.append(score)
    print(scores)

    plt.plot(list(range(2,19)),scores)
    plt.xlabel("Number of Clusters Initialized")
    plt.ylabel("Sihouette Score")
    plt.show()
    return None

if __name__ == "__main__":
    kmeans()

通过图像可以看出来，随着k值的增大，效果反而并没有变得更好，所以k值的选取是一个很重要的点。

总结

这里我们对k-means聚类进行总结一下，

优点：简单，快速，适合常规数据集，迭代式算法非常实用
缺点：k值难确定，复杂度与样本呈线性关系，很难发现任意形状的簇，而且容易收敛到局部最优解（可以多次聚类）

四、补充（DBSCAN聚类算法）

1、简介

这里我们补充一种聚类算法,DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。比如下图，我们希望将下面的圆环分成两个部分，一个是里面的内核，一个是外面的环状，但是我们用k-means聚类之后，只能分成下面的形状，而且通过理解k-means聚类原理，我们知道k-means是做不到我们想要的结果的，这时我们就可以使用DBSCAN算法了。

DBSCAN效果图

2、算法原理

DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。
基本上这就是DBSCAN算法的主要内容了，是不是很简单？但是我们还是有三个问题没有考虑。
1、第一个是一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。
2、第二个是距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。
3、第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于ϵϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说BDSCAN的算法不是完全稳定的算法。

这里还有几个重要概念需要了解一下：

核心对象：若某个点的密度达到算法设定的阈值则其为核心点(即r领域内点的数量不小于minPts)

领域的距离阈值：设定的半径r

直接密度可达：若某点p在点q的r领域内，且q是核心点则p-q直接密度可达

密度可达：若有一个点的序列q0,q1,...,qk，对任意qi-qi-1是直接密度可达的，则称从q0到qk密度可达，这实际上是直接密度可达的"传播"

聚类算法对比
通过上图对比我们发现，DBSCAN聚类比Kmeans还要强大，这也是我们讲的主要原因。

3、工作流程

参数D：输入数据集
参数 $\epsilon$ :制定半径
MinPts:密度阈值
1、标记所有对象为unvisited;
2、Do
3、随机选择一个unvisited对象p;
4、标记p为visited;
5、if p 的 $\epsilon-$ 领域至少有MinPts个对象
6、    创建一个新簇C，并把p添加到C；
7、    令N为p的 $\epsilon-$ 领域中的对象集合;
8、    For N 中每个点p
9、          if p 为unvisited
10、            标记p为visited
11、             if p的 $\epsilon-$ 领域至少有MinPts个对象，把这些对象添加到N；
12、             如果p还不是任何簇的成员，把p添加到C；
13、   End For;
14、   输出C；
15、Else 标记p为噪声；
16、Until没有标记为unvisited的对象；

4、API

sklearn包中有封装好的DBSCAN算法from sklearn.cluster import DBSCAN
DBSCAN算法适合检测异常点和离群点
参数选择：
1）eps： DBSCAN算法参数，即我们的ϵ-邻域的距离阈值，和样本距离超过ϵ的样本点不在ϵ-邻域内。默认值是0.5.一般需要通过在多组值里面选择一个合适的阈值。eps过大，则更多的点会落在核心对象的ϵ-邻域，此时我们的类别数可能会减少，本来不应该是一类的样本也会被划为一类。反之则类别数可能会增大，本来是一类的样本却被划分开。
2）min_samples： DBSCAN算法参数，即样本点要成为核心对象所需要的ϵ-邻域的样本数阈值。默认值是5. 一般需要通过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下，min_samples过大，则核心对象会过少，此时簇内部分本来是一类的样本可能会被标为噪音点，类别数也会变多。反之min_samples过小的话，则会产生大量的核心对象，可能会导致类别数过少。

5、案例分析

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.cluster import KMeans
from sklearn.cluster import DBSCAN

def dbs():
    """
    用一组随机数来验证DBSCAN算法与Kmeans算法
    :return:
    """
    X1, y1=datasets.make_circles(n_samples=5000, factor=.6,
                                          noise=.05)
    X2, y2 = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[1.2,1.2]], cluster_std=[[.1]],
                   random_state=9)

    X = np.concatenate((X1, X2))
    plt.scatter(X[:, 0], X[:, 1], marker='o')
    plt.show()
    #使用K-means算法
    x_pred = KMeans(n_clusters=3, random_state=9).fit_predict(X)
    plt.scatter(X[:, 0], X[:, 1], c=x_pred)
    plt.show()
    #使用DBSCAN算法
    y_pred = DBSCAN().fit_predict(X)
    plt.scatter(X[:, 0], X[:, 1], c=y_pred)
    plt.show()
    return None

if __name__ == "__main__":
    dbs()

我们看一下输出结果，

原始数据

Kmeans聚类

DBSCAN聚类

通过上面与原始数据对比发现，K-means的效果并不好，比DBSCAN效果要差，但是DBSCAN的效果也不是很理想，我们的理想状态是可以分成三部分（内环、外环、右上角），接下来，我们可以通过调整一下参数来实现，我们在DBSCAN算法里，加上一些参数经过不断的优化，最后实现的下面的效果。

y_pred = DBSCAN(eps=0.1,min_samples=10).fit_predict(X)
    plt.scatter(X[:, 0], X[:, 1], c=y_pred)
    plt.show()

6、总结

优点
- 不需要指定簇的个数
- 可以发现任意形状的簇
- 擅长找到离群点（检测任务）
- 两个参数就够了
缺点
- 高维数据有些困难（可以做降维）
- 参数难以选择（参数对结果的影响非常大）
- Sklearn中效率很慢（数据削减策略）

K-means算法到这里就结束了，有不懂的同学可以在下方留言。
注：最后这个案例是引用的博客刘建平老师的博客。