机器学习20：聚类(k-means模型、高斯混合聚类模型）

二、常用的聚类算法：

1，原型聚类：K-means

2，模型聚类：高斯混合聚类(GMM)

3，其他聚类形式

三、code：K-means

一、聚类概述：

在无监督学习中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据内在的性质及规律，其中，应用最广的是聚类算法。

聚类的一个重要应用是用户的分组与归类。

聚类算法涉及两个基本问题：性能度量和距离计算。使得类内差异应尽可能小，类间差距应尽可能大。

1，性能度量：

聚类的性能度量又称为聚类有效性指标(validity index)，若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。聚类结果应当满足簇内想瓷都高，且簇间相似度底。

聚类性能度量大致分两类，外部指标：将聚类结果与某个参考模型进行比较；内部指标：直接考察聚类结果而不利用任何参考模型。

1.1，外部指标：

外部指标需要一个参考模型，这个参考模型通常是由专家给定的，或者是公认的参考模型比如公开数据集。对于聚类的结果所形成的簇集合（这里叫做簇A），对于参考模型的簇集合（这里叫做B），对这两个模型结果的样本进行两两配对比较。

常用的聚类性能外部指标：

Jaccard系数(JC):

相似度越小，则距离越大：

JC又称为Jaccard相似系数（Jaccard similaritycoefficient）用于比较有限样本集之间的相似性与差异性。Jaccard系数值越大，样本相似度越高。

此外，外部指标还有FM指数、Rand指数等，值区间均在[0,1]区间，值越大越好。

1.2，内部指标：

内部指标则只考虑聚类之后这些簇之间的效果，通常用距离来度量：

avg(C):簇C样本间的平均距离 diam(C):簇C样本间的最远距离 dmin(ci,cj):簇间最近样本间的距离 dcen(ci,jc)：簇间中心点之间的距离

常用的聚类性能内部指标：

DB指数(Davies-Bouldin Index，DBI)：

Dunn指数(Dunn Index，DI)：

DBI的值越小越好，而DI的值越大越好

2，距离计算：

计算簇之间的相似性和差异性时常常要使用距离来进行度量，内部指标也都是以距离度量为基础的。

常用的距离计算方式有：

闵可夫斯基距离：

当p=1时，为曼哈顿距离；当p=2时，为欧式距离；当p=无穷大时，为切比雪夫距离。对于多个具有不同重要性的属性来说，可以使用加权距离：

二、常用的聚类算法：

根据形成聚类的不同方式分类：原型聚类、密度聚类、层次聚类、网格聚类、模型聚类、谱聚类等。

1，原型聚类：K-means

原型聚类假设聚类结构能通过一组原型刻画，聚类任务重最常见。通常情况下，该算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法。

K-means包含一下假设：每个簇至少包含一个对象；每个对象属于且仅属于一个簇；将满足上述条件的k个簇成为一个合理的聚类划分。

对于给定的类别数目k，首先给定初始划分，通过迭代改变样本和簇 的隶属关系，使的每次处理后得到的划分方式比上一次的好(总的数据集之间的 距离和变小了)

K-means算法步骤：

1)，记K个簇中心分别为a1,a2,...ak；每个簇的样本数量为N1,N2,...,NK；

2)，使用平方误差作为目标函数(使用欧几里得距离)，公式为：

3)，要获取最优解，也就是目标函数需要尽可能的小，对J函数求偏导数，可以得到 簇中心点a更新的公式为：

4)，要获取最优解，也就是目标函数需要尽可能的小，对J函数求偏导数，可以得到 簇中心点a更新的公式为：

中止条件：即k-means算法收敛条件，包括迭代次数、簇中心变化率、MSE、MAE等

K-means算法是初值敏感的，选择不同的初始值可能导致不同的簇划分规则。因此，K-Means算法有大量的变体，本文就从最传统的K-Means算法讲起，在其基础上讲述K-Means的优化变体方法。包括初始化k个初始点优化K-Means++, 距离计算优化elkan K-Means算法、k值优化canopy算法和大数据情况下的优化Mini BatchK-Means算法。

2，模型聚类：高斯混合聚类(GMM)

高斯混合聚类采用概率模型来表达聚类原型。换句话说，GMM聚类方法最终得到的是样本属于每个类别的概率，而不是像K均值那样将它直接归化为某一类别，因此也称为软聚类。

高斯混合分布的模型参数{(αi,μi,Σ)|1≤i≤k}{(αi,μi,Σi)|1≤i≤k}。αi 代表各个混合成分的系数(mixture coefficient)，αi满足性质αi>0,Σαi=1，μi代表各个混合成分的n维均值向量，Σi代表n×n协方差矩阵。

高斯混合聚类步骤：

1)，E步（计算ai）：

2)，M步（反推各个混合成分的参数）：

重复上述E~M步直至中心点更新移动的距离小于阈值ϵϵ或者迭代次数到达最大迭代次数时结束迭代过程（停止迭代条件与K均值差不多）。 最后根据各个样本由各个混合成分组成的后验概率来划分类别:λj=argmaxγji，i∈1,2,…,k。

3，其他聚类形式：

3.1，密度聚类：DBSCAN、OPTICS、局部密度聚类、密度最大值聚类(MDCA,MaximumDensityClustering Application)、

3.2，层次聚类：BIRCH算法

层次聚类（可分为自底向上（AGNES凝聚）和自顶向下（DINAN分裂））。

层次聚类降低了对初始中心点的依赖，层次聚类适用于大数据的优化方法有BIRCH算法（平衡迭代聚类树，CF-tree，B+树）

凝聚的方法：也称自底向上的方法，首先将每个对象作为单独的一个聚类，然后根据性质和规则相继地合并相近的类，直到所有的对象都合并为一个聚类中，或者满足一定的终止条件。经典的层次凝聚算法以AGNES算法为代表，改进的层次凝聚算法主要以BIRCH,CURE,ROCK,CHAMELEON为代表。

3.3，网格聚类：STING（STatistical INformation Grid）和CLIQUE（CLustering In QUEst）

3.4，谱聚类（spectral clustering）

三、code：K-means

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

# 1,生成数据：
N = 1500
centers = 4
data,y = ds.make_blobs(N, n_features=2, centers=centers, random_state=28)
data2,y2 = ds.make_blobs(N, n_features=2, centers=centers,  random_state=28)
data3 = np.vstack((data[y == 0][:200], data[y == 1][:100], data[y == 2][:10], data[y == 3][:50]))
y3 = np.array([0] * 200 + [1] * 100 + [2] * 10 + [3] * 50)

# 2，模型训练：
km = KMeans(n_clusters=centers, init='random',random_state=28)
km.fit(data, y)

y_hat = km.predict(data)  # 预测
cluster_centers = km.cluster_centers_

print ("所有样本距离聚簇中心点的总距离和:", km.inertia_, "距离聚簇中心点的平均距离:", (km.inertia_ / N),"聚簇中心点：", cluster_centers)

def expandBorder(a, b):
    d = (b - a) * 0.1
    return a-d, b+d

# 3、画图:
cm = matplotlib.colors.ListedColormap(list('rgbmyc'))
plt.figure(figsize=(15, 9), facecolor='w')
plt.subplot(221)
plt.scatter(data[:, 0], data[:, 1], c=y, s=30, cmap=cm, edgecolors='none')

x1_min, x2_min = np.min(data, axis=0)
x1_max, x2_max = np.max(data, axis=0)
x1_min, x1_max = expandBorder(x1_min, x1_max)
x2_min, x2_max = expandBorder(x2_min, x2_max)
plt.xlim((x1_min, x1_max))
plt.ylim((x2_min, x2_max))
plt.title(u'原始数据')
plt.grid(True)

plt.subplot(222)
plt.scatter(data[:, 0], data[:, 1], c=y_hat, s=30, cmap=cm, edgecolors='none')
plt.xlim((x1_min, x1_max))
plt.ylim((x2_min, x2_max))
plt.title(u'K-Means算法聚类结果')
plt.grid(True)