8. 聚类

bash

https://gitee.com/fakerlove/machine-learning

8.1 聚类任务

参考资料

bash

https://blog.csdn.net/jmh1996/article/details/83959465

资料参考2

bash

https://zhuanlan.zhihu.com/p/100557559

8.1.1 概念

机器学习里面的聚类是无监督的学习问题，它的目标是为了感知样本间的相似度进行类别归纳。它可以用于潜在类别的预测以及数据压缩上去。

潜在类别预测，比如说可以基于通过某些常听的音乐而将用户进行不同的分类。数据压缩则是指将样本进行归类后，就可以用比较少的的One-hot向量来代替原来的特别长的向量。

聚类，既可以作为一个单独的过程，也可以作为其他机器学习任务的预处理模块。

8.1.2 问题描述

给定一个包含个样本的样本集，要给对这这N个样本给定一个划分方式，将这些样本划分为m类,使得满足

8.1.3 算法分类

聚类算法主要有：

序贯法
层次分析法
基于损失函数最优化的：K-means,概率聚类
基于密度的聚类
其他特殊聚类方法：基因聚类算法，分治限界聚类算法；子空间聚类算法；基于核的聚类方法。

问题的提出

虽然聚类看起来是很棒的，可以进行“物以类分，人以类聚”，但是聚类确守很多方面的影响。例如： 1.属性选择不同，导致不同的结果 2.相似度度量不同，导致不同的结果 3.聚类的方法不同，导致不同的结果
如何衡量无监督学习的指标
性能指标
距离计算

8.1.4 数学准备

样本集合中由n个样本，每个样本由m个属性的特征向量组成，样本集合可以用矩阵X表示：

给定样本集合X,

1) 类或簇

用G表示类或簇，用表示类中的样本，中的样本个数，表示样本与样本之间的距离

类或簇的定义

2) 类或簇的特征

类的均值
类的直径
类的样本散步矩阵
样本协方差矩阵

3) 类与类之间的距离

前四种方法定义的和之间的距离如下表所示。

相似度度量标准(距离大小)
最短距离或单连接(Single-link)	$D_{pq}=min{d_{ij	x_i\in C_p,x_j\in C_q}}$
最长距离或完全连接(Complete-link)	$D_{pq}=max{d_	x_i\in C_p,x_j\in C_q}$
中心距离
平均距离(UPGMA)

8.1.4 性能指标

聚类性能度量大致分两类，一类是将聚类结果与某个"参考模型"，进行比较，称为外部指标，另一类是直接参考聚类结果而不利用任何参考模型，称为内部指标

1) 外部指标

Jaccard系数

FM指数

Ran指数

2) 内部指标

DB指数

Dunn指数

8.1.5 距离计算(相似度)

参考资料

bash

https://zhuanlan.zhihu.com/p/100557559

距离越大，相似度越小

样本集合中由n个样本，每个样本由m个属性的特征向量组成，样本集合可以用矩阵X表示：

给定样本集合X,

1) 性质

非负性
同一性
对称性
直递性

2) 闵可夫斯基距离

欧氏距离

两点之间直线最短

当p=2时称为欧氏距离（Euclidean distance)

曼哈顿距离

当p=1时称为曼哈顿距离（Manhattan distance)

切比雪夫距离

当p=时称为切比雪夫距离（Chebyshev distance)

3) 马哈拉诺比斯距离

给定一个样本集,,其协方差矩阵为S,样本之间的马哈拉诺比斯距离距离定义为

4) 相关系数

样本与样本之间的相关系数定义为：

5) 夹角余弦

8.2 原型聚类(划分式聚类)

8.2.1 K均值(k-means)

1) 概念

K-means是基于损失函数最小化的思想的，给定样本集,聚类划分后簇为，K-means的损失函数定义为：

既然要最小化这个东西，那么只要把各个样本归到离自己最近的那个类别就是啦。

说人话就是

样本之间的欧氏距离为

损失函数为样本与所属类中心之间距离的总和：

为第I类的均值或者中心，称为能量函数

k均值聚类就是求解最优化问题：

2) 算法推导

输入：个样本的集合

输出：样本集合的聚类

初始化,令,随机选择个样本点作为初始聚类中心
对样本进行聚类，对固定的类中心,其中为类的中心，
计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果
计算新的类中心，对聚类结果，计算当前各个类中的样本的均值，作为新的类中心
如果迭代收敛或符合停止条件，输出,后者令

算法复杂度,其中m为样本维数，n为样本个数,k为类别个数

3) 例子

迭代过程

4) 优缺点

优点：

原理比较简单，实现也是很容易，收敛速度快；聚类效果较优；算法的可解释度比较强；主要需要调参的参数仅仅是簇数k。

缺点：

1、聚类中心的个数K需要事先给定，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适；一般通过交叉验证确定；

2、不同的初始聚类中心可能导致完全不同的聚类结果。算法速度依赖于初始化的好坏，初始质点距离不能太近；

3、如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳；

4、该方法不适于发现非凸面形状的簇或大小差别很大的簇，对于不是凸的数据集比较难收敛；

5、对噪音和异常点比较的敏感。

6、需样本存在均值（限定数据种类）。

7、采用迭代方法，得到的结果只是局部最优。

8.2.2 LVQ

8.2.3 高斯混合聚类GMM

资料参考

bash

https://zhuanlan.zhihu.com/p/81255623

资料参考2

bash

https://blog.csdn.net/lotusng/article/details/79990724

1) 介绍

高斯混合模型（GMM）可以看做是k-means模型的一个优化。它既是一种工业界常用的技术手段，也是一种生成式模型。

高斯混合模型试图找到多维高斯模型概率分布的混合表示，从而拟合出任意形状的数据分布。在最简单的场景中，GMM可以用与k-means相同的方式进行聚类。

只是将高斯分布、贝叶斯公式、极大似然法和聚类的思路混合在这一种方法中，容易被绕来绕去感到云里雾里的。

2) 数学准备

a) 高斯分布

首先是高斯分布的概念。高斯分布即正态分布。一般我们最常见最熟知的一元正态分布的标准形式和曲线是这样的：

正态分布可以记为，从上面的公式很明显可以看出一元正态分布只有两个参数和,且这两个参数决定了正态曲线的“宽窄”、“高矮”。曲线下面积为1。

b) 多元高斯分布

资料参考

bash

https://www.cnblogs.com/bingjianing/p/9117330.html
https://www.zhihu.com/question/36339816

先假设n个变量,且服从正态分布（维度不相关多元正态分布），

各个维度的均值，

方差

根据联合概率密度公式：

这样多元正态分布又可以写成一元那种漂亮的形式了(注意一元与多元的差别)：

因为多元正态分布有着很强的几何思想，单纯从代数的角度看待z很难看出z的概率分布规律，这里需要转换成矩阵形式：

等式比较长，让我们要做一下变量替换：

定义一个符号

代表变量的协方差矩阵， i行j列的元素值表示的协方差

因为现在变量之间是相互独立的，所以只有对角线上存在元素，其他地方都等于0，且与它本身的协方差就等于方差

是一个对角阵，根据对角矩阵的性质，它的逆矩阵：

对角矩阵的行列式 = 对角元素的乘积

替换变量之后，等式可以简化为：

代入以z为自变量的标准高斯分布函数中：

一般的多元高斯具有形式：

注意前面的系数变化：从非标准正态分布->标准正态分布需要将概率密度函数的高度压缩倍，从一维 -> n维的过程中，每增加一维，高度将压缩倍

二元高斯曲线如下图。曲线下面积为1。它多了一个变量。例如x轴是身高，y轴是体重，有了身高体重的数据就可以在z轴找到该身高体重在人群中所占的比例（即概率）。同样地，中等身高且中等体重的人在人群中是最常见的，正如路上普普通通的路人。

c) 贝叶斯公式

d) 极大似然

2) 算法推导

n维样本的高斯分布为：

由贝叶斯定理，样本属于i类的后验概率为：

将上式简写为

则样本分类公式为

给每一个分类一个系数，采用对数似然，得

上式分别对求导。令导数为0，得

系数求和为1，引入此约束，对数似然的拉格朗日形式为

3) 例子

代码

bash

import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np

#产生实验数据
from sklearn.datasets.samples_generator import make_blobs
X, y_true = make_blobs(n_samples=700, centers=4,
                       cluster_std=0.5, random_state=2019)
X = X[:, ::-1] #方便画图

from sklearn.mixture import GaussianMixture as GMM
gmm = GMM(n_components=4).fit(X) #指定聚类中心个数为4
labels = gmm.predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis')

它使用EM算法进行迭代：1.选择位置和初始形状2.循环直至收敛：

E步骤：对于每个点，为每个点分别计算由该混合模型内的每个分量生成的概率。

M步骤：调整模型参数以最大化模型生成这些参数的可能性。

该算法保证该过程内的参数总会收敛到一个局部最优解。

例二

参考资料

bash

https://www.cnblogs.com/lunge-blog/p/11792226.html

数据

bash

序号，密度，含糖量
1,0.697,0.460
2,0.774,0.376
3,0.634,0.264
4,0.608,0.318
5,0.556,0.215
6,0.403,0.237
7,0.481,0.149
8,0.437,0.211
9,0.666,0.091
10,0.243,0.267
11,0.245,0.057
12,0.343,0.099
13,0.639,0.161
14,0.657,0.198
15,0.360,0.370
16,0.593,0.042
17,0.719,0.103
18,0.359,0.188
19,0.339,0.241
20,0.282,0.257
21,0.748,0.232
22,0.714,0.346
23,0.483,0.312
24,0.478,0.437
25,0.525,0.369
26,0.751,0.489
27,0.532,0.472
28,0.473,0.376
29,0.725,0.445
30,0.446,0.459

代码

python

file='xigua4.txt'
x=[]
with open(file) as f:
    f.readline()
    lines=f.read().split('\n')
    for line in lines:
        data=line.split(',')
        x.append([float(data[-2]),float(data[-1])])
y=np.array(x)

# 2 算法部分
import numpy as np
import random
 
def probability(x,u,cov):
    cov_inv=np.linalg.inv(cov)
    cov_det=np.linalg.det(cov)
    return np.exp(-1/2*((x-u).T.dot(cov_inv.dot(x-u))))/np.sqrt(cov_det)

def gauss_mixed_clustering(x,k=3,epochs=50,reload_params=None):
    features_num=len(x[0])
    r=np.empty(shape=(len(x),k))
#     初始化系数，均值向量和协方差矩阵
    if reload_params!=None:
        a,u,cov=reload_params
    else:
        a=np.random.uniform(size=k)
        a/=np.sum(a)
        u=np.array(random.sample(list(x),k))
        cov=np.empty(shape=(k,features_num,features_num))
#         初始化为只有对角线不为0
        for i in range(k):
            for j in range(features_num):
                cov[i][j]=[0]*j+[0.5]+[0]*(features_num-j-1)
    step=0
    while step<epochs:
#         E步：计算r_ji
        for j in range(len(x)):
            for i in range(k):
                r[j,i]=a[i]*probability(x[j],u[i],cov[i])
            r[j]/=np.sum(r[j])
             
        for i in range(k):
            r_toal=np.sum(r[:,i])
            u[i]=np.sum([x[j]*r[j,i] for j in range(len(x))],axis=0)/r_toal
            cov[i]=np.sum([r[j,i]*((x[j]-u[i]).reshape((features_num,1)).dot((x[j]-u[i]).reshape((1,features_num)))) for j in range(len(x))],axis=0)/r_toal
            a[i]=r_toal/len(x)
        step+=1
    C=[]
    for i in range(k):
        C.append([])
    for j in range(len(x)):
        c_j=np.argmax(r[j,:])
        C[c_j].append(x[j])
    return C,a,u,cov

验证

python

res,A,U,COV=gauss_mixed_clustering(y)
import matplotlib.pyplot as plt
%matplotlib inline
colors=['green','blue','red','black','yellow','orange']
for i in range(len(res)):
    plt.scatter([d[0] for d in res[i]],[d[1] for d in res[i]],color=colors[i],label=str(i))
plt.scatter([d[0] for d in U],[d[1] for d in U],color=colors[-1],marker='^',label='center')
 
plt.xlabel('density')
plt.ylabel('suger')
plt.legend()

50论过后

python

res,A,U,COV=gauss_mixed_clustering(y,reload_params=[A,U,COV])
for i in range(len(res)):
    plt.scatter([d[0] for d in res[i]],[d[1] for d in res[i]],color=colors[i],label=str(i))
plt.scatter([d[0] for d in U],[d[1] for d in U],color=colors[-1],marker='^',label='center')
plt.xlabel('density')
plt.ylabel('suger')
plt.legend()

8.3 密度聚类

资料参考

bash

https://zhuanlan.zhihu.com/p/104355127

8.3.1 概念

k-means算法对于凸性数据具有良好的效果，能够根据距离来讲数据分为球状类的簇，但对于非凸形状的数据点，就无能为力了，当k-means算法在环形数据的聚类时，我们看看会发生什么情况。

从上图可以看到，kmeans聚类产生了错误的结果，这个时候就需要用到基于密度的聚类方法了，

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法，类似于均值转移聚类算法，但它有几个显著的优点。

常用的密度聚类算法：DBSCAN、MDCA、OPTICS、DENCLUE等。

密度聚类的主要特点是：

发现任意形状的簇
对噪声数据不敏感
一次扫描
需要密度参数作为停止条件
计算量大、复杂度高

DBSCAN算法的核心思想是：用一个点的ε邻域内的邻居点数衡量该点所在空间的密度，该算法可以找出形状不规则的cluster，而且聚类的时候事先不需要给定cluster的数量。

8.3.2 数学准备

资料参考

bash

https://www.jianshu.com/p/5e5bcf3ec9d6

定义一个数据集

密度
领域中x的密度，是一个整数值，依赖于半径
MinPts
ε-邻域内样本个数最小值。也简记为M
核心对象
密度直达
密度可达(density-reachable)
如果存在一个对象链,其中,那么称是从密度可达的。
密度相连(density-connected)
在集合X中，如果存在一个对象o，使得对象x和y是从o关于ε和m密度可达的，那么对象x和y是关于ε和m密度相连的。

可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密度相连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。

从下图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其ϵ-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的ϵ-邻域内所有的样本相互都是密度相连的。

8.3.3 DBSCAN算法推导

资料参考

bash

https://www.cnblogs.com/pinard/p/6208966.html

1、如果一个点x的ε邻域包含多余m个对象，则创建一个x作为核心对象的新簇； 2、寻找并合并核心对象直接密度可达的对象； 3、没有新点可以更新簇的时候，算法结束。

输入:样本集，领域参数,样本距离度量方式
输出:簇划分
初始化核心对象集合,初始化聚类簇k=0,初始化为访问样本集合.簇划分
对于j=1,2,...,m，按照下面的步骤找出所有的核心对象
a) 通过距离度量的方式没找到样本的领域子样本集
b) 如果子样本集样本个数满足，将样本加入核心对象样本集合
如果核心对象集合
在核心对象集合Ω中，随机选择一个核心对象o，初始化当前簇核心对象队列,初始化类别序号k=k+1，初始化当前簇样本集合,更新未访问核心对象为未访问集合。
如果当前簇核心对象队列,则当前聚类簇生成完毕，更新簇划分,更新核心对象集合,转入步骤3，否则更新核心对象集合。
在当前簇核心对象队列中取出一个核心对象。通过领域距离阈值子样本集，令,更新当前簇集合,更新为访问样本集合,更新，转入步骤5
输出结果，簇划分

算法特征描述: 1、每个簇至少包含一个核心对象。 2、非核心对象可以是簇的一部分，构成簇的边缘。 3、包含过少对象的簇被认为是噪声。

8.3.4 例子

8.3.5 优缺点

**优点：**不需要确定要划分的聚类个数，聚类结果没有偏倚；抗噪声，在聚类的同时发现异常点，对数据集中的异常点不敏感；处理任意形状和大小的簇，相对的，K-Means之类的聚类算法一般只适用于凸数据集。

**缺点：**数据量大时内存消耗大，相比K-Means参数多一些；样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合；

代码

python

from sklearn.cluster import DBSCAN
y_pred = DBSCAN(eps=0.1).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

8.4 层次聚类

资料参考

bash

https://blog.csdn.net/AI_BigData_wh/article/details/78073444

8.4.1 概念

层次聚类(Hierarchical Clustering)是聚类算法的一种，通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法，本篇文章介绍合并方法

源数据:

层次聚类:

这里写图片描述

1.凝聚层次聚类：AGNES算法(自底向上)

首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足

2.分裂层次聚类：DIANA算法(自顶向下)

首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。

8.4.2 数学准备

给定聚类簇和，两个簇的距离可以通过以下定义得到

最短距离:

最大距离

均值距离

平均距离

这里写图片描述

显然最小距离是由两个簇的最近样本决定、最大距离由两个簇的最远样本决定、均值距离由两个簇的中心位置决定、而平均距离则由两个簇的所有样本共同决定。当聚类距离由计算时。AGNES算法被相应地称为“单链接”、“全链接”或“均链接”算法。

8.4.3 算法推导

AGNES（自底向上凝聚算法）算法的具体步骤如下所示：输入：包含n个对象的数据库。输出：满足终止条件的若干个簇。 (1) 将每个对象当成一个初始簇； (2) REPEAT(重复) (3) 计算任意两个簇的距离，并找到最近的两个簇； (4) 合并两个簇，生成新的簇的集合； (5) UNTIL 终止条件得到满足。

8.4.4 例子

使用AGNES算法对下面的数据集进行聚类，以最小距离计算簇间的距离。刚开始共有5个簇：

样本点	A	B	C	D	E
A	0	0.4	2	2.5	3
B	0.4	0	1.6	2.1	1.9
C	2	1.6	0	0.6	0.8
D	2.5	2.1	0.6	0	1
E	3	1.9	0.8	1	0

step1.簇和簇的距离最近，将二者合并，得到新的簇结构：

样本点	AB	C	D	E
AB	0	1.6	2.1	1.9
C	1.6	0	0.6	0.8
D	2.1	0.6	0	1
E	1.9	0.8	1	0

Step2. 接下来簇和簇的距离最近，将二者合并，得到新的簇结构：

样本点	AB	CD	E
AB	0	1.6	1.9
CD	1.6	0	0.8
E	1.9	0.8	0

Step3. 接下来簇和簇的距离最近，将二者合并，得到新的簇结构：

样本点	AB	CDE
AB	0	1.6
CDE	1.6	0

Step4. 最后只剩下簇和簇，二者的最近距离为1.6，将二者合并，得到新的簇结构：

这里写图片描述

层次聚类方法的终止条件：

设定一个最小距离阈值，如果最相近的两个簇的距离已经超过，则它们不需再合并，聚类终止。
限定簇的个数k，当得到的簇的个数已经达到，则聚类终止。

python

from sklearn import datasets
from sklearn.cluster import AgglomerativeClustering
import matplotlib.pyplot as plt
from sklearn.metrics import confusion_matrix
import pandas as pd

iris = datasets.load_iris()
irisdata = iris.data

clustering = AgglomerativeClustering(linkage='ward', n_clusters=3)

res = clustering.fit(irisdata)

print "各个簇的样本数目："
print pd.Series(clustering.labels_).value_counts()
print "聚类结果："
print confusion_matrix(iris.target,clustering.labels_)

plt.figure()
d0 = irisdata[clustering.labels_==0]
plt.plot(d0[:,0],d0[:,1],'r.')
d1 = irisdata[clustering.labels_==1]
plt.plot(d1[:,0],d1[:,1],'go')
d2 = irisdata[clustering.labels_==2]
plt.plot(d2[:,0],d2[:,1],'b*')
plt.xlabel("Sepal.Length")
plt.ylabel("Sepal.Width")
plt.title("AGNES Clustering")
plt.show()

8. 聚类 ​

8.1 聚类任务 ​

8.1.1 概念 ​

8.1.2 问题描述 ​

8.1.3 算法分类 ​

8.1.4 数学准备 ​

1) 类或簇 ​

2) 类或簇的特征 ​

3) 类与类之间的距离 ​

8.1.4 性能指标 ​

1) 外部指标 ​

Jaccard系数 ​

FM指数 ​

Ran指数 ​

2) 内部指标 ​

DB指数 ​

Dunn指数 ​

8.1.5 距离计算(相似度) ​

1) 性质 ​

2) 闵可夫斯基距离 ​

3) 马哈拉诺比斯距离 ​

4) 相关系数 ​

5) 夹角余弦 ​

8.2 原型聚类(划分式聚类) ​

8.2.1 K均值(k-means) ​

1) 概念 ​

2) 算法推导 ​

3) 例子 ​

4) 优缺点 ​

8.2.2 LVQ ​

8.2.3 高斯混合聚类GMM ​

1) 介绍 ​

2) 数学准备 ​

a) 高斯分布 ​

b) 多元高斯分布 ​

c) 贝叶斯公式 ​

d) 极大似然 ​

2) 算法推导 ​

3) 例子 ​

8.3 密度聚类 ​

8.3.1 概念 ​

8.3.2 数学准备 ​

8.3.3 DBSCAN算法推导 ​

8.3.4 例子 ​

8.3.5 优缺点 ​

8.4 层次聚类 ​

8.4.1 概念 ​

8.4.2 数学准备 ​

8.4.3 算法推导 ​

8.4.4 例子 ​

8. 聚类

8.1 聚类任务

8.1.1 概念

8.1.2 问题描述

8.1.3 算法分类

8.1.4 数学准备

1) 类或簇

2) 类或簇的特征

3) 类与类之间的距离

8.1.4 性能指标

1) 外部指标

Jaccard系数

FM指数

Ran指数

2) 内部指标

DB指数

Dunn指数

8.1.5 距离计算(相似度)

1) 性质

2) 闵可夫斯基距离

3) 马哈拉诺比斯距离

4) 相关系数

5) 夹角余弦

8.2 原型聚类(划分式聚类)

8.2.1 K均值(k-means)

1) 概念

2) 算法推导

3) 例子

4) 优缺点

8.2.2 LVQ

8.2.3 高斯混合聚类GMM

1) 介绍

2) 数学准备

a) 高斯分布

b) 多元高斯分布

c) 贝叶斯公式

d) 极大似然

2) 算法推导

3) 例子

8.3 密度聚类

8.3.1 概念

8.3.2 数学准备

8.3.3 DBSCAN算法推导

8.3.4 例子

8.3.5 优缺点

8.4 层次聚类

8.4.1 概念

8.4.2 数学准备

8.4.3 算法推导

8.4.4 例子