聚类（Clustering）

您所在的位置：网站首页 › 英文中心的点 › 聚类（Clustering）

聚类（Clustering）

2023-03-25 14:48| 来源: 网络整理| 查看: 265

无监督学习（Unsupervised learning）：训练样本的标记信息是未知的，目标是为了揭露训练样本的内在属性，结构和信息，为进一步的数据挖掘提供基础。

· 聚类（clustering）

· 降维（dimensionality reduction）

· 异常检测（outlier detection）

· 推荐系统（recommendation system）

监督学习（supervised learning）：训练样本带有信息标记，利用已有的训练样本信息学习数据的规律预测未知的新样本标签

· 回归分析（regression）

· 分类（classification）

聚类：物以类聚。按照某一个特定的标准（比如距离），把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不再同一个簇内的数据对象的差异性也尽可能的大。

簇（或类cluster）：子集合。最大化簇内的相似性；最小化簇与簇之间的相似性。

聚类可以作为一个单独过程，用于寻找数据内在分布结构，也可以作为其他学习任务前驱过程。

聚类和分类的区别：聚类是无监督学习任务，不知道真实的样本标记，只把相似度搞得样本聚合在一起；分类是监督学习任务，利用已知的样本标记训练学习器预测未知样本的类别。

聚类相似度度量：几何距离

几种距离度量方法：

· 欧式距离（Euclidean distance）:p=2的Minkowski距离， $dist_{ms}(\vec{x} , \vec{y} ) = ||\vec{x}- \vec{y}||_{2}=\sqrt{(\sum_{i=1}^n )|x_{i} -y_{i} |^2 }$

· Minkowoski距离： $dist_{ms}(\vec{x} , \vec{y} ) =( \sum_{i=1}^n |x_{i} -y_{i} |^p)^\frac{1}{p}$

· 曼哈顿距离（Manhattan distance）:p=1的Minkowski距离 $dist_{ms}(\vec{x} , \vec{y} ) =||\vec{x}- \vec{y}||_{1}=\sum_{i=1}^n |x_{i} -y_{i} |$

· 夹角余弦： $\cos （\vec{x} ,\vec{y} ）=\frac{\sum_{i}x_{i}y_{i} }{\sqrt{\sum_{i} x_{i} ^2 \sum_{i} y_{i} ^2 } }$

` 相关系数（Pearson correlation coefficient）： $corr(\vec{x} ,\vec{y} )=\frac{\sum_{i}(x_{i}- x )\sum_{i}(y_{i}- y )}{\sqrt{\sum_{i}(x_{i}- x )^2 \sum_{i} (x_{i}- x)^2 } }$ ,等式右面的x其实是 $\bar{x}$ （x方向的均值），y其实是 $\bar{ y }$ （y方向的均值）,简书对于这个表达式很不友好，所以在此说明一下。

聚类类别：

· 基于划分的聚类（partitioning based clustering）：k均值（K-means）, Mean shift

· 层次聚类（hierarchical clustering）：Agglomerative clustering, BIRCH

· 密度聚类（density based clustering）：DBSCAN

· 基于模型的聚类（model based clustering）：高斯混合模型（GMM）

· Affinity propagation

· Spectral clustering

聚类原理：

划分聚类（partition based clustering）：给定包含N个点的数据集，划分法将构造K个分组；每个分组代表一个聚类，这里每个分组至少包含一个数据点，每个数据点属于且只属于一个分组；对于给定的K值，算法先给出一个初始化的分组方法，然后通过反复迭代的的方法改变分组，知道准则函数收敛。

k-mean原理图

K均值算法（Kmeans）:

` 给定样本集：D={ $\vec{x} _{1}$ , $\vec{x} _{2}$ .... $\vec{x} _{m}$ }, k均值算法针对聚类所得簇：C={ $C_{1}$ , $C_{2}$ ... $C_{k}$ }

` 最小化平方差： $E=\sum_{i=1}^k \sum_{x\in C_{i} }||\vec{x} -\mu _{i} ||_{2}^2$ ,其中： $\mu _{i}=\frac{1}{C} \sum_{x\in C_{i} }\vec{x}$ 簇 $C_{i}$ 的质心，上面的2代表平方，下面的2代表范数2.

具体的K均值算法过程：

1. 随机选择K个对子女给，每个对象出事地代表了一个簇的质心，即选择K个初始质心；2. 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；3. 重新计算每个簇的平均值。这个过程不断重复，直到准则函数（误差的平方和SSE作为全局的目标函数）收敛，直到质心不发生明显的变化。

初始质心优化:Kmeans++：

输入：样本集D={ $x_{1}$ , $x_{2}$ ... $x_{m}$ } 聚类簇的数量K

选取初始质心的过程：

1. 随机从m个样本点中选择一个样本作为第一个簇的质心C1；2. 计算所有的样本点到质心C1的距离： $D_{i}^2 = ||x_{i} - C_{i} ||^2$ ;3. 从每个点的概率分布 $D_{2}^i /\sum_{j} D_{j}^2$ 中随机选取一个点作为第二个质心C2。离C1越远的点，被选择的概率越大；4. 重新计算所有样本点到质心的距离；5. 重复上述过程，直到初始的K个质心被选择完成 $D_{i}^2 = min(||x_{i}-C_{1} ||^2,||x_{i}-C_{2} ||^2)$ ；按照Kmeans的算法步骤完成聚类。

输出：C= { $C_{1}$ , $C_{2}$ ... $C_{k}$ }

K均值算法（Kmean）的优缺点：

优点：1. 简单直观，抑郁理解实现；2. 复杂度相对比较低，在K不是很大的情况下，Kmeans的计算时间相对很短；3. Kmean会产生紧密度比较高的簇，反映了簇内样本围绕质心的紧密程度的一种算法。

缺点：1. 很难预测到准确的簇的数目；2. 对初始值设置很敏感（Kmeans++）；3. Kmeans主要发现圆形或者球形簇，对不同形状和密度的簇效果不好；4. Kmeans对噪声和离群值非常敏感（Kmeadians对噪声和离群值不敏感）

层次聚类（hierarchical clustering）：

· 主要在不同层次对数据集进行逐层分解，直到满足某种条件为止；

· 先计算样本之间的距离。每次将距离最近的点合并到同一个类，然后再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成一个类。

· 自底向上（bottom-up）和自顶向下（top-down）两种方法：

top-down：一开始每个个体都是一个初始的类，然后根据类与类之间的链接（linkage）寻找同类，最后形成一个最终的簇

bottom-up：一开始所有样本都属于一个大类，然后根据类与类之间的链接排除异己，打到聚类的目的。

类与类距离的计算方法：

最短距离法，最长距离法，中间距离法，平均距离法

最小距离： $d_{min}(C_{i}, C_{j}) = \min_{x\in C_{i},y\in C_{j} } dist(\vec{x} ,\vec{y} )$

最大距离： $d_{max}(C_{i}, C_{j}) = \max_{x\in C_{i},y\in C_{j} } dist(\vec{x} ,\vec{y} )$

平均距离： $d_{avg}(C_{i}, C_{j}) = \frac{1}{|C_{i} ||C_{j} |} \sum_{x\in C_{i} } \sum_{y\in C_{j} } dist(\vec{x} ,\vec{y} )$

单链接（single-linkage）:根据最小距离算法

全连接（complete-linkage）：根据最大距离算法

均链接（average-linkage）：根据平均距离算法

凝聚层次聚类具体算法流程：

1. 给定样本集，决定聚类簇距离度量函数以及聚类簇数目k；2. 将每个样本看作一类，计算两两之间的距离；3. 将距离最小的两个类合并成一个心类；4.重新计算心类与所有类之间的距离；5. 重复（3-4），知道达到所需要的簇的数目

层次聚类的优缺点：

优点：1.可以得到任意形状的簇，没有Kmeans对形状上的限制；2. 可以发现类之间的层次关系；3.不要制定簇的数目

缺点：1. 通常来说，计算复杂度高（很多merge/split）；2.噪声对层次聚类也会产生很大影响；3.不适合打样本的聚类

密度聚类（density based clustering）:

` 基于密度的方法的特点是不依赖于距离，而是依赖于密度，从而客服k均值只能发现“球形”聚簇的缺点

· 核心思想：只要一个区域中点的密度大于某个阈值，就把它加到与之相近的聚类中去

· 密度算法从样本密度的角度来考察样本的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果

· 对噪声和离群值的处理有效

· 经典算法：DBSCAN（density based spatial clutering of applications with noise）

DBSCAN 基于近邻域（neighborhood）参数（ $\varepsilon ，MinPts$ ）刻画样本分布的紧密程度的一种算法。

基本概念：

· 样本集： D={ $x_{1} ，x_{2}...x_{m}$ }

` 阈值： $\varepsilon$

· $\varepsilon -邻域$ ：对样本点 $x_{j}$ 的 $\varepsilon -邻域$ 包括样本集中与 $x_{j}$ 距离不大于 $\varepsilon$ 的样本

· 核心对象（core object）：如果 $x_{j}$ 的 $\varepsilon -邻域$ 至少包含MinPts个样本，那么 $x_{j}$ 就是一个核心对象 $N_{\varepsilon } (x_{j} ) ={ {x_{i} \in D | dist(x_{i} , x_{j}) \leq \in }}$ ,