浅谈机器学习--聚类

还不了解机器学习？来看！

一.聚类

二.k均值聚类算法(k-means)

1.k均值聚类算法的流程

二.k均值算法的改进

1.二分k-means算法

2.k-means++算法

3.k-medoids算法

4.Mini Batch k-means算法

三.DBSCAN算法

1.编辑-邻域

2.核心点和边界点

3.直接密度可达

4.密度可达

5.密度相连

6.skearn中的DBSCAN类

四.OPTICS算法

1.核心点距离

2.可达距离

3.OPTICS算法流程

4.skearn中的OPTCS类

五.AGNES算法

1.AGNES算法流程

2.sklearn中的AGNES算法

一.聚类

什么是聚类？我们常说物以类聚，人以群分，这其实也就是聚类最形象的解释。聚类呢，就是按事务的相似性对事务进行分类，它属于无监督学习，是机器学习的入门算法。

这里我们介绍一下聚类算法中比较简单几个算法，以做为进一步学习奠定基础：

k均值聚类算法
DBSCAN算法
OPTICS算法
AGNES算法

二.k均值聚类算法(k-means)

k均值聚类算法是一种迭代的算法，该算法是对样本集进行分簇，样本的相似性差异我们叫做样本距离，有差异就有距离，然后相似性的比较我们叫做距离度量。k均值聚类算法将样本集进过一系列操作后，让每一个样本点都无限地接近一个簇中心，样本集的分簇个数是我们在开始聚类前指定的，称为k，k均值聚类算法的k由此而来。每一个样本点到本簇的中心的距离的平方和称为误差平方和(SSE)

该算法一般采用欧式距离做为样本距离度量的准则，例如样本点 $x_{}i$ 和 $x_{j}$ 的欧式距离定义为：

$L_{2}(x_{i},x_{j})=\sqrt[2]{\sum_{i=1}^{n}(x_{i} -x_{j})^{2}}$

当采用欧式距离，并以误差平方和SSE做为损失函数时，簇中心计算方法如下：

对于第i个簇 $C_{i}$ ，簇中心就是簇内所有点的均值，簇中心第j个特性为, $C_{i}$ 为样本总数：

$u_{i}^{(j)}=\frac{1}{c_{i}}\sum_{x\epsilon x_{i}}^{} x^{j}$

SSE计算方法为：dist[*]为距离计算函数，常用欧式距离（ $L_{2},u_{c_{(i)}}$ ）表示样本 $x_{i}$ 所在的簇中心

$SSE=\sum_{i=1}^{m}[dist(x_{i},u_{c_{(i)}})]^{2}$

1.k均值聚类算法的流程

k均值聚类算法是按事务的相似性进行分组，流程如下：

随机产生k个初始簇中心或者随机选择k个点作为初始簇中心
对于每一个样本点，计算它和所有簇的距离，然后将样本点分配到距离最近的簇
如果没有点发生分配点结果改变，就结束
计算新的簇中心
跳到流程2

k-means算法以重新计算簇中心为一个周期，重复流程，直到簇稳定为准，看下图(忽略背景图上的美女)：

看图，图上的三个红三角是我们事先指定的k，即簇中心，其他点是样本点，我们不断计算每一个样本点到每个红三角簇中心的欧式距离，然后将样本点分配到距离近的簇周变，得到簇稳定后，每一个簇中心边上的样本点就形成了一个相似的集合。黄点在一个区域，绿点和紫点分别在其他区域。如果按我们人的分类，我们可以很轻松地将样本点以不同形状颜色大小进行分类，但机器不行，机器不会区分颜色，看不成形状大小，但，当分簇完成以后，机器就可以按照样本点在不同簇中心周边的分布去判断哪些样本点是一类的或相似的

让我们看看上面这个图的k-means算法实例代码：

import numpy as np
import matplotlib.pyplot as plt


def L2(vecXi, vecXj):
    """
    计算欧氏距离
    para vecXi：点坐标，向量
    para vecXj：点坐标，向量
    retrurn: 两点之间的欧氏距离
    """
    return np.sqrt(np.sum(np.power(vecXi - vecXj, 2)))


def kMeans(S, k, distMeas=L2):
    """
    K均值聚类
    para S：样本集，多维数组
    para k：簇个数
    para distMeas：距离度量函数，默认为欧氏距离计算函数
    return sampleTag：一维数组，存储样本对应的簇标记
    return clusterCents：一维数组，各簇中心
    retrun SSE:误差平方和
    """
    m = np.shape(S)[0]  # 样本总数
    sampleTag = np.zeros(m)

    # 随机产生k个初始簇中心
    n = np.shape(S)[1]  # 样本向量的特征数
    clusterCents = np.mat([[-1.93964824, 2.33260803], [7.79822795, 6.72621783], [10.64183154, 0.20088133]])
    # clusterCents = np.mat(np.zeros((k,n)))
    # for j in range(n):
    #    minJ = min(S[:,j]) 
    #    rangeJ = float(max(S[:,j]) - minJ)
    #    clusterCents[:,j] = np.mat(minJ + rangeJ * np.random.rand(k,1))

    sampleTagChanged = True
    SSE = 0.0
    while sampleTagChanged:  # 如果没有点发生分配结果改变，则结束
        sampleTagChanged = False
        SSE = 0.0

        # 计算每个样本点到各簇中心的距离
        for i in range(m):
            minD = np.inf
            minIndex = -1
            for j in range(k):
                d = distMeas(clusterCents[j, :], S[i, :])
                if d < minD:
                    minD = d
                    minIndex = j
            if sampleTag[i] != minIndex:
                sampleTagChanged = True
            sampleTag[i] = minIndex
            SSE += minD ** 2
        print(clusterCents)
        plt.scatter(clusterCents[:, 0].tolist(), clusterCents[:, 1].tolist(), c='r', marker='^', linewidths=7)
        plt.scatter(S[:, 0], S[:, 1], c=sampleTag, linewidths=np.power(sampleTag + 0.5, 2))
        plt.show()
        print(SSE)

        # 重新计算簇中心
        for i in range(k):
            ClustI = S[np.nonzero(sampleTag[:] == i)[0]]
            clusterCents[i, :] = np.mean(ClustI, axis=0)
    return clusterCents, sampleTag, SSE


if __name__ == '__main__':
    samples = np.loadtxt("kmeansSamples.txt")
    clusterCents, sampleTag, SSE = kMeans(samples, 3)
    # plt.scatter(clusterCents[:,0].tolist(),clusterCents[:,1].tolist(),c='r',marker='^')
    # plt.scatter(samples[:,0],samples[:,1],c=sampleTag,linewidths=np.power(sampleTag+0.5, 2))
    plt.show()
    print(clusterCents)
    print(SSE)

当我们运行后：

迭代一次

又迭代一次

再迭代一次

迭代完成，簇趋于稳定

二.k均值算法的改进

k-means算法的初始簇中心是我们事先指定，不同的簇中心会对算法最后的结果产生不可预料的差异，如下是对该算法的一些改进：

1.二分k-means算法

二分k-means算法是为了试图克服k-means算法收敛于局部最优的值，它的算法是先将所有点看出一个簇，然后将簇一分为二，之后在选择其中一个簇继续分裂，具体选择哪个簇继续分裂，要看分裂簇后能否最大限度地降低SSE值，算法流程如下：

将所有样本点看成一个簇
当簇数量小于k时，进行分裂，计算SSE值，计算减少的SSE值，纪录减少SSE值最多的
对分簇减少SSE最多的簇进行分簇，执行2流程

2.k-means++算法

k-means算法也是克服k-means算法收敛于局部最优的值，该算法流程：

从样本集中随机取一个点放到簇集合中
计算该样本点到簇的距离
将样本点到簇的距离转换为概率
计算使用样本点的概率，最后按概率将样本点放到簇中，按概率的方法有很多种

3.k-medoids算法

该算法和k-means算法差不多，唯一不同的就是k-medoids算法在产生新簇时不同，k-means算法是采取所有样本点均值来产生簇中心，而k-medoids算法是选取一个样本点为簇中心，选取的标准是所有样本点到该簇中心的距离和最小

如图，所有样本点到红点的距离和最小，那么红点就是新的簇中心

4.Mini Batch k-means算法

k- medoids算法在样本点和特征量非常大的时候，簇中心的计算量就会非常大，而Mini Batch k-means算法是采取损失质量优化效率的策略来解决这个问题的算法，它的基本思想是随机选取一部分样本点来计算簇中心，计算过程和k-medoids算法一样。

三.DBSCAN算法

DBSCAN算法是密度聚类算法，它的分簇过程是重复查找核心点并扩展成簇，直到没有核心点为止。接下来我们先了解几个相关的概念

1. $\varepsilon$ -邻域

设 $\varepsilon$ 为距离，在样本中，到x的距离不大于 $\varepsilon$ 的使用样本点在的区域我们就称为是x的 $\varepsilon$ -邻域

2.核心点和边界点

在x的 $\varepsilon$ -邻域内的使用样本点不多于我们事先指定的MinPts的个数，那么该点我们就称为核心点，否则就是边界点

3.直接密度可达

在x的 $\varepsilon$ -邻域内，x是核心点，则任意一个样本点都可以由x直接密度可达，核心点之间的直接密度可达是对称的，而边界点和核心点之间的直接密度可达不对称

4.密度可达

密度可达可以由直接密度可达多次传达得到

5.密度相连

如果存在一个点o使得x和y都可以由o密度可达，那么称x和y密度相连

注：不属于任意簇的样本点称为噪声点

DBSCAN算法的过程：

1.初始当前簇号为0，初始所有样本点的标签为noise，初始种子集合seeds为空集合

2.从样本点选取一个标签为noise的x点，如果没有这样的点则算法结束

3.检查x是否是核心点，如果不是就转到过程2

4.将x邻域内所有样本点表上当前的簇号，然后加到seeds集合中，但不包含x点

5.如果集合seeds为空，将当前簇号加1，转到流程2，否则从seeds中取一个点p

6.如果点p非核心点，从seeds中删除，并转到流程5

7.将点p的邻域内所有标签为noise的样本点标上当前簇号，并入seeds集合，转到流程5

6.skearn中的DBSCAN类

在skearn的cluster包中通过了该算法的实现：

class sklearn.cluster.DBSCAN(eps=0.5,min_samples=5,metric='euclidean',
        metric_params=None,algorithm='auto',leaf_size=30,p=None,n_jobs=None)
fit(self,X[,y,sample_weight])
fit_predict(self,X[,y,sample_weight])
get_params(self[,deep])
set_params(self,\*\*params)
"""
eps和min_samples是邻域距离和MinPts这两个核心参数，metric表示距离度量方法，默认为欧式距离
"""

DSCAN算法实例：

from sklearn.cluster import DBSCAN
import numpy as np
samples = np.loadtxt("kmeansSamples.txt")
clustering = DBSCAN(eps=5,min_samples=5).fit(samples)
import matplotlib.pyplot as plt
plt.scatter(samples[:,0],samples[:,1],c=clustering.labels_+1.5,linewidths=
                    np.power(clustering.labels_+1.5,2))
plt.show()

四.OPTICS算法

OPTUCS算法是BDSCAN算法的派生算法，它通过引入可达距离，巧妙地解决了 $\varepsilon$ 参数的问题，它的基本思想是将每个点离最近聚集密集区的可达距离都计算出来，然后据此进行分簇。这里先介绍几个定义：

1.核心点距离

首先，只有核心点才有核心距离，核心距离是使该点成为核心点的最小距离，一般这个核心距离小于等于 $\varepsilon$

2.可达距离

只有核心点有可达距离，且可达距离是该点核心点的核心距离或者邻域内两点距离的最大值

3.OPTICS算法流程

1.设置邻域半径 $\varepsilon$ 和核心点最小邻域点数MinPts，初始所有样本点可达距离的极大值为inf，然后创建一个有序队列和结果队列

2.从样本点中选取一个核心点x，放入结果队列，如果没有这样的点，算法结束

3.找到x的所有直接密度可达点，如果不在结果队列中，则计算这些直接密度可达点和x的可达距离，并放入有序队列，按距离的大小从小到大排序

4.如果有序队列为空，转到流程2，否则从有序队列中取出一个点p，并放入结果队列，对于p点：

（1）如果p点为非核心点，跳至流程4，否则取出该点的所有直接密度可达点

（2）如果p点的直接密度可达点已经在结果队列中，跳到流程4

（3）如果p点的直接密度可达不在有序队列中，则计算与点p的可达距离，加入有序队列，并对有有序队列按可达距离值按从小到达排序，跳到流程4

（4）如果点p的直接密度可达点已经在有序队列中，则计算与p点的可达距离，如果新的可达距离小于原可达距离，则更新该点的可达距离，并重新排序，跳到流程4

4.skearn中的OPTCS类

class skearn.cluster.OPTICS(min_samples=5,max_eps=inf,metric='minkowski',p=2,
        metric_params=None,cluster_method='xi',eps=None,xi=0.05,predecessor_correction=True
        ,min_cluster_size=None,algorithm='auto',leaf_size=30,n_jobs=None)
fit(self,X[,y])
fit_predict(self,X[,y])
get_params(self[,deep])
set_params(self,\*\*params)
"""
max_eps参数表示邻域半径，min_samples参数为核心点最小邻域点数MinPts，eps表示分簇的距离标准
"""

实例：

from sklearn.cluster import OPTICS,cluster_optics_dbscan
import matplotlib.pyplot as plt
import numpy as np
samples = np.loadtxt("kmeansSamples.txt")
clust = OPTICS(max_eps=np.inf,min_samples=5,cluster_method='dbscan',eps=4)
clust.fit(samples)
reachability = clust.reachability_[clust.ordering_]
labels = clust.labels_[clust.ordering_]

plt.plot(list(range(1,31)),reachability,marker='.',markeredgewidth=3,linestyle='-')
plt.show()
plt.scatter(samples[:,0],samples[:,1],c=clust.labels_+1.5,linewidths=np.power(clust.labels_+1.5,2))
plt.show()

五.AGNES算法

AGNES算法属于层次聚列算法，它先将每个样本点看成一个簇，然后根据簇与簇之间的距离度量将最近的两个簇合并，一组重复合并到预设的聚类簇数为止

1.AGNES算法流程

1.设置终止簇数k，簇距离度量函数DIST

2.将每一个点都设置成一个单独的簇

3.如果簇数等于k，算法结束

4.计算任意两个簇的距离

5.合并距离最小的两个簇，跳至流程3

2.sklearn中的AGNES算法

class sklearn.cluster.AgglomerativeClustering(n_clusters=2,affinity='euclidean',memory=None
            ,connectivty=None,compute_full_tree='auto',linkage='ward',pooling_func='deprecated',
            distance_threshold=None)
fit(self,X[,y])
fit_predict(self,X[,y])
get_params(self[,deep])
set_params(self,\*\*params)
"""
n_clusters表示终止簇数，linkage表示簇的距离度量方法，complete表示簇的最大距离，average表示簇的平均距离，
single表示簇的最小距离
"""