一.聚类的基本概念
聚类是针对给定的样本，依据它们特征的 相似度或距离，将其归并到若千个“类”或“簇”的数据分析问题。一个类是样本的一个子集。直观上，相似的样本聚集在相同的类,不相似的样本分散在不同的类。这里，样本之间的相似度或距离起着重要作用。
1.1 相似度或距离
聚类的对象是观测数据，或样本集合。假设有 n 个样本，每个样本由 m 个属性的特征向量组成。样本集合可以用矩阵 X 表示矩阵的第 j 列表示第 j 个样本， j=1,2,..,n; 第 i 行表示第 i 个属性, i=1,2,...,m; 矩阵元素 xij 表示第 j 个样本的第 i 个属性值， i=1,2,...,m; j=1,2,..,n。
聚类的核心概念是相似度(similarity) 或距离(distance) ，有多种相似度或距离的定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。具体哪种相似度更合适取决于应用问题的特性。
1.闵可夫斯基距离
在聚类中，可以将样本集合看作是向量空间中点的集合，以该空间的距离表示样本之间的相似度。常用的距离有 闵可夫斯基距离，特别是 欧氏距离。闵可夫斯基距离越大相似度越小，距离越小相似度越大。
定义7.1 给定样本集合 X, X 是 m维实数向量空间 Rm中点的集合,其中 x i , x j ∈ X , xi=(x1i,x2i,...,xmi)T, xj=(x1j,x2j,...,xmj)T，样本 xi 与样本xj 的 **闵可夫斯基距离( Minkowski distance)**定义为
这里 p≥1。当 p=2 时称为 欧氏距离( Euclidean distance)，即
当 p = 1 p=1 p=1 时称为曼哈顿距离( Manhattan distance )，即
当p=∞时称为 切比雪夫距离( Chebyshev distance),取各个坐标数值差的绝对值的最大值，即
- 相关系数
样本之间的相似度也可以用 相关系数(correlation cofficient) 来表示。相关系数的绝对值越接近于1,表示样本越相似；越接近于0，表示样本越不相似。
1.2 类或簇
通过聚类得到的类或簇，本质是样本的子集。如果一个聚类方法假定一个样本只能属于一个类，或类的交集为空集，那么该方法称为 硬聚类(hard clustering) 方法。否则，如果一个样本可以属于多个类，或类的交集不为空集，那么该方法称为软聚类(soft clustering) 方法。本章只考虑硬聚类方法。
用 G 表示类或簇(cluster) ，用xi,xj表示类中的样本，用 nG表示G 中样本的个数，用 dij 表示样本 xi 与样本 xj 之间的距离。下面给出 类的定义：
设 T 为给定的正数，若集合 G 中任意两个样本 xi,xj，有
则称 G 为一个类或簇。
类的特征可以通过不同角度来刻画，常用的特征有下面几种:
(1)类的均值
，又称为类的中心
(2)类的直径(diameter) DG
类的直径 DG是类中任意两个样本之间的最大距离，即
1.3 类与类之间的距离
下面考虑类 Gp与类 Gq之间的距离 D(p,q), 也称为连接(linkage)。类与类之间的距离也有多种定义。
(1)最短距离或单连接(single linkage)
定义类 Gp 的样本与 Gq 的样本之间的最短距离为两类之间的距离
(2)最长距离或完全连接(complete linkage)
定义类 Gp 的样本与 Gq 的样本之间的最长距离为两类之间的距离
(3)中心距离
定义类Gp 与类 Gq 的中心
之间的距离为两类之间的距离
(4)平均距离
定义类 Gp 与类 Gq 任意两个样本之间距离的平均值为两类之间的距离
二.层次聚类
层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。层次聚类又有 聚(agglomerative) 或自下而上(ottom-up)聚类、分裂(divisive) 或自上而下(top-down)聚类两种方法。因为每个样本只属于一个类，所以层次聚类属于硬聚类。
2.1 基本概念
聚合聚类开始将 每个样本各自分到一个类；之后将相距 最近的两类合并，建立一个新的类，重复此操作直到满足停止条件；得到层次化的类别。分裂聚类开始将 所有样本分到一个类;之后将已有类中相距 最远的样本分到两个新的类，重复此操作直到满足停止条件;得到层次化的类别。本书只介绍聚合聚类。
聚合聚类的具体过程如下：对于给定的样本集合，开始将每个样本分到一个类；然后按照一定规则，例如类间距离最小，将最满足规则条件的两个类进行合并；如此反复进行，每次减少一个类，直到满足停止条件,如所有样本聚为一类。
由此可知，聚合聚类需要预先确定下面三个要素:
- 距离或相似度;
- 合并规则;
- 停止条件。
根据这些要素的不同组合，就可以构成不同的聚类方法。距离或相似度可以是闵可夫斯基距离、马哈拉诺比斯距离、相关系数、夹角余弦。合并规则一般是类间距离最小，类间距离可以是最短距离、最长距离、中心距离、平均距离。停止条件可以是类的个数达到阈值(极端情况类的个数是1)、类的直径超过阈值。
如果采用 欧氏距离为样本之间距离；类间距离最小为合并规则，其中最短距离为类间距离；类的个数是1，即所有样本聚为一类，为停止条件，那么聚合聚类的算法如下。
2.2 算法描述
算法14.1 (聚合聚类算法)
输入： n n n 个样本组成的样本集合及样本之间的距离;
输出：对样本集合的一个层次化聚类。
2.3 例题
例： 给定5个样本的集合，样本之间的欧氏距离由如下矩阵 D D D 表示:
其中dj表示第 i 个样本与第 j 个样本之间的 欧氏距离。显然 D 为对称矩阵。应用聚合层次聚类法对这5个样本进行聚类。
三.K均值聚类
k均值聚类是基于 样本集合划分 的聚类算法。k 均值聚类将样本集合划分为 k 个子集，构成 k个类，将 n 个样本分到 k 个类中，每个样本到其所属类的中心的距离最小。每个样本只能属于一个类，所以 k 均值聚类是硬聚类。下面分别介绍 k 均值聚类的模型、策略、算法，讨论算法的特性及相关问题。
3.1 模型
给定 n 个样本的集合 X=x1,x2,...,xn 每个样本由一个特征向量表示，特征向量的维数是 m。 k 均值聚类的目标是将 n 个样本分到 k 个不同的类或簇中，这里假设k < n。 k 个类 G1,G2,...,Gk形成对样本集合 X的划分，其中
用 C 表示划分，一个划分对应着一个聚类结果。
划分 C 是一个多对一的函数。事实上，如果把每个样本用一个整数 i∈{1,2,..,n} 表示，每个类也用一个整数 l∈{1,2,..,k} 表示，那么划分或者聚类可以用函数 l=C(i) 表示，其中 i∈{1,2,...,n},l∈{1,2，..,k}。所以 k 均值聚类的模型是一个从样本到类的函数。
3.2 策略
k均值聚类归结为样本集合X的划分，或者从样本到类的函数的选择问题。k均值聚类的策略是通过 损失函数的最小化选取最优的划分或函数C*。
首先，采用 欧氏距离平方(squared Euclidean distance) 作为样本之间的距离d(xi,xj) .
然后，定义样本与其所属类的中心之间的距离的总和为损失函数，即
式中
是第 l 个类的均值或中心，
是指示函数，取值为 1或 0。函数 W(C) 也称为能量，表示相同类中的样本相似的程度。
k均值聚类就是求解最优化问题:
3.3 算法
聚类中心的初始化
样本集 D划分之前，先选择代表点作为初始聚类核心，再将其余样本初始分类。迭代结果与初始代表点选择有关
3.3.1 K-Means ++ 中的聚类中心初始化算法：
3.3.2 聚类数 K 的确定
通常要求事先给定聚类数K，若类别数目未知，可按如下方法确定
- 一般根据领域先验知识确定
-
实验确定:
令k = 1,2，3…分别进行聚类，得 Je(k)，绘制 Je(k)−k曲线图；找出拐点，对应聚类数目为最终类别数。
3.3.3 K均值聚类算法描述
3.4.例题
例： 给定含有5 个样本的集合
试用k均值聚类算法将样本聚到2个类中。
解：
四.密度聚类(DBSCAN)
DBSCAN 算法是一种基于 高密度连通区域的、基于密度的聚类算法。能够将具有足够高密度的区域划分为簇。
4.1 相关概念
给定样本集 D={x1,⋯,xm}
4.2 算法描述
结语
喜欢人工智能的小伙伴记得点赞关注哦~