聚类及其常见算法 | Clustering | SLie's Blog|琴弦之轮

什么是聚类

k-means算法

主要思想

在给定 $k$ 值和 $k$ 个初始类簇中心点的情况下，把每个点分配到离其最近的类簇中心点所代表的类簇中。所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。

基本原理

假定给定数据样本 $X$ ，包含了 $n$ 个对象 $X=\left \{ x_{1} ,x_{2},x_{3},...,x_{n}\right \}$ ，其中每个对象 $x_i$ 都是具有 $p$ 个维度属性的数据(向量)。 $Kmeans$ 算法的目标是将 $n$ 个对象依据对象间的相似性聚集到指定的 $k$ 个类簇中，每个对象属于且仅属于一个其到类簇中心距离最小的类簇中。首先需要初始化 $k$ 个聚类中心：

$\left \{ \mu_{1} ,\mu_{2},...,\mu_{k}\right \}\quad(1<k\leq n)$

然后通过计算第 $i$ 个对象到第 $j$ 个聚类中心的欧式距离：

$dis(x_{i},\mu_{j})=||x_i-\mu_j||=\sqrt{\sum_{\tau=1}^{p}(X_{i\tau}-\mu_{j\tau})^{2}}$

从而得到 $x_i$ 应当归类的类簇标记 $\lambda_i$ ：

$\lambda_i:=\arg \min_j dis(x_i,\mu_j)$

根据标记 $1\leq\lambda_i\leq k$ 将 $x_i$ 划分到 $\left \{ C_{1},C_{2},...,S_{k}\right\}$ 中的 $C_{\lambda_i}$ 中。

依次比较每一个点到每一个聚类中心的距离，从而分配对象后，完成一次迭代。

接下来根据每个类簇 $C_i$ 中被划分的点重新更新聚类中心 $\mu_i$ ：

$\mu_i\leftarrow\frac{\sum_{x\in C_i}x}{|C_i|}$

式中， $|C_i|$ 为属于类簇 $C_i$ 的对象个数。

于是可以总结得到 $K-means$ 算法的伪代码如下：

kmeans伪代码

分析得到：

时间复杂度 $O(tknp)$ ， $t$ 为迭代次数

空间复杂度 $O(p(n+k))$ .

Python API

# 从sklearn库中导入cluster中的kmeans
from sklearn.cluster import KMeans

# 传入期望分类的类簇数k(此处取k=3)以构造聚类器estimator
estimator = KMeans(n_clusters=3)
# 对传入数据(矩阵) X 进行聚类
estimator.fit(X)

label_pred = estimator.labels_ # 获取聚类标签
label_pred = estimator.labels_ # 获取聚类标签
centroids = estimator.cluster_centers_ # 获取聚类中心
inertia = estimator.inertia_ # 获取聚类准则的总和

层次聚类

层次聚类(Hierarchical Clustering)是通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树从而实现聚类目标的算法。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。

层次聚类算法相比划分聚类算法的优点之一是可以在不同的尺度上（层次）展示数据集的聚类情况，这来源于其算法思想。该算法对数据集的划分可分为自底向上和自顶向下的两种分拆策略。

AGNES

AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集 $X=\left \{ x_{1} ,x_{2},x_{3},...,x_{n}\right \}$ 中的每个对象看作一个初始聚类簇，即 $C_i=\{x_i\},i=1,2,...,n$ ，然后在算法的每一步中找出距离最近的两个聚类簇 $C_i$ 和 $C_j$ ，将其进行合并。不断重复，直至达到预设的聚类簇个数 $k$ 。

其中在合并时选择的用于度量的距离有如下选择：

$\begin{aligned} d_{\min}(C_i,C_j)&=\min_{a\in C_i,b\in C_j}dist(a,b)\\ d_{\max}(C_i,C_j)&=\max_{a\in C_i,b\in C_j}dist(a,b)\\ d_{avg}(C_i,C_j)&=\frac{\sum_{a\in C_i}\sum_{b\in C_j}dist(a,b)}{|C_i||C_j|} \end{aligned}$

选择不同的度量距离，对应着不同的聚类结果，对此有着如下的定义：

Single Linkage：取 $d_{\min}$ 计算。
这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。
Complete Linkage：取 $d_{\max}$ 计算。
Complete Linkage的问题也与Single Linkage相反，两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。
Average Linkage：取 $d_{avg}$ 计算。
这种方法计算量比较大，但结果比前两种方法更合理。

AGNES算法伪代码如下：

AGNES伪代码

DIANA

DIANA是一种采用自顶向下分裂策略的层次聚类算法。

Python API

from sklearn.cluster import AgglomerativeClustering

# 创建聚类器
estimator = AgglomerativeClustering(n_clusters=2, affinity='euclidean', memory=None, connectivity=None, compute_full_tree='auto', linkage='ward', pooling_func='deprecated')

# 对传入数据(矩阵) X 进行聚类
estimator.fit(X)

主要参数

n_clusters：聚类的个数，即 $k$
affinity：计算距离的方法
- “euclidean”（即 “l2”，欧氏距离）
- “manhattan”（即 “l1”，曼哈顿距离，有利于稀疏特征或稀疏噪声，例如文本挖掘中使用稀有词的出现作为特征时，会出现许多 0）
- “cosine”（余弦距离）
- “precomputed”（预先计算的 affinity matrix）
- 如果 linkage = "ward"，只能选择 “euclidean”，选择度量标准的方针是使得不同类样本之间距离最大化，并且最小化同类样本之间的距离
memory： None, str or object with the joblib
如果给定一个地址，可以将层次聚类的树形图缓存到相应地址
linkage：指定层次聚类判断相似度的方法，有以下三种：
ward：组间距离等于两类对象之间的最小距离。（即single-linkage聚类）
average：组间距离等于两组对象之间的平均距离。（average-linkage聚类）
complete：组间距离等于两组对象之间的最大距离。（complete-linkage聚类）

主要属性

labels_：每个数据的分类标签
n_leaves_：分层树的叶节点数量
n_components：连接图中连通分量的估计值
children：一个数组，给出了每个非节点数量

DBSCAN 算法

Python API

from sklearn.cluster import DBSCAN

DBSCAN(eps=0.5,min_samples=5,metric='euclidean',metric_params=None,algorithm='auto',leaf_size=30,p=None,n_jobs=1)

#eps：对象半径；
#min_samples：一个核心对象应该拥有的最少sample数；
#metric：计算样本之间距离的公式；{precomputed,callable}
#algorithm：用来找最近邻样本点算法{'auto','ball_tree','ke_tree'}
#leaf_size：kd_tree或ball_tree中的叶子节点数；决定了搜索快慢；

OPTICS 算法

谱聚类

模糊C均值聚类

软聚类，待更

模糊C均值聚类（Fuzzy C-means）算法（FCM）_模糊c均值聚类算法-CSDN博客

Python API

1
2
3

# !pip install -U scikit-fuzzy
from skfuzzy.cluster import cmeans
center, u, u0, d, jm, p, fpc = cmeans(data=data.T, c, m=2, error=0.005, maxiter=1000)

c 为所需要聚类的个数， data为用于训练的数据。
注意！ 参数data的

参数

data：训练数据，shape是 (num_features, num_samples)，与其他很多API的shape相反！所以传入时需要取转置。
c：需要指定的聚类个数。
m：隶属度指数，是一个加权指数，一般为2 。
error：当隶属度的变化小于此则提前结束迭代。
maxiter：最大迭代次数。

返回值

cntr：聚类中心
u：最后的隶属度矩阵
u0：初始化的隶属度矩阵
d：是一个矩阵，记录每一个点到聚类中心的欧式距离
jm：是目标函数的优化历史
p：p是迭代的次数
fpc：全称是fuzzy partition coefficient，是一个评价分类好坏的指标，它的范围是0到1, 1表示效果最好，可以通过它来选择聚类的个数。