什么是聚类

k-means算法

主要思想

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

基本原理

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

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

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

dis(xi,μj)=∣∣xi−μj∣∣=∑τ=1p(Xiτ−μjτ)2dis(x_{i},\mu_{j})=||x_i-\mu_j||=\sqrt{\sum_{\tau=1}^{p}(X_{i\tau}-\mu_{j\tau})^{2}}

从而得到xix_i应当归类的类簇标记λi\lambda_i：

λi:=arg⁡min⁡jdis(xi,μj)\lambda_i:=\arg \min_j dis(x_i,\mu_j)

根据标记1≤λi≤k1\leq\lambda_i\leq k将xix_i划分到{C1,C2,...,Sk}\left \{ C_{1},C_{2},...,S_{k}\right\}中的CλiC_{\lambda_i}中。

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

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

μi←∑x∈Cix∣Ci∣\mu_i\leftarrow\frac{\sum_{x\in C_i}x}{|C_i|}

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

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

kmeans伪代码

分析得到：

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

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

函数调用

Python

1
2
3
4
5
6
7
8
9
10
11
12
# 从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_ # 获取聚类准则的总和

Matlab

1
2
3
4
5
Idx = Kmeans(X,K)
[Idx,C] = Kmeans(X,K) 
[Idx,C,sumD] = Kmeans(X,K) 
[Idx,C,sumD,D] = Kmeans(X,K) 
[…] = Kmeans(…,’Param1’,Val1,’Param2’,Val2,…)

详见官方文档：Kmenas函数

层次聚类

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

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

AGNES

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

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

dmin⁡(Ci,Cj)=min⁡a∈Ci,b∈Cjdist(a,b)dmax⁡(Ci,Cj)=max⁡a∈Ci,b∈Cjdist(a,b)davg(Ci,Cj)=∑a∈Ci∑b∈Cjdist(a,b)∣Ci∣∣Cj∣\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：取dmin⁡d_{\min}计算。

    这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。

  • Complete Linkage：取dmax⁡d_{\max}计算。

    Complete Linkage的问题也与Single Linkage相反，两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。

  • Average Linkage：取davgd_{avg}计算。

    这种方法计算量比较大，但结果比前两种方法更合理。

AGNES算法伪代码如下：

AGNES伪代码

DIANA

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

函数调用

Python

1
2
3
4
5
6
7
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)

主要参数

  1. n_clusters：聚类的个数，即kk

  2. affinity：计算距离的方法

    • “euclidean”（即 “l2”，欧氏距离）
    • “manhattan”（即 “l1”，曼哈顿距离，有利于稀疏特征或稀疏噪声，例如文本挖掘中使用稀有词的出现作为特征时，会出现许多 0）
    • “cosine”（余弦距离）
    • “precomputed”（预先计算的 affinity matrix）
    • 如果 linkage = "ward"，只能选择 “euclidean”，选择度量标准的方针是使得不同类样本之间距离最大化，并且最小化同类样本之间的距离

  3. memory： None, str or object with the joblib

    如果给定一个地址，可以将层次聚类的树形图缓存到相应地址

  4. linkage：指定层次聚类判断相似度的方法，有以下三种：
    ward：组间距离等于两类对象之间的最小距离。（即single-linkage聚类）
    average：组间距离等于两组对象之间的平均距离。（average-linkage聚类）
    complete：组间距离等于两组对象之间的最大距离。（complete-linkage聚类）

主要属性

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

Matlab

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
X = randn(6,2); %随机生成6个2维数据集

distX = pdist(X); %计算X中两两对象的距离
				  %pdist(X,'metric')
				  %可选多种距离，默认为欧氏距离
				  
squareform(distX) %用距离矩阵的方式显示距离Y

tree = linkage(distX); %根据两两距离生成层次数tree
					   %linkage(distX,'method')
					   %可选聚类规则，默认是最短距离single
					   
dendrogram(tree) %可视化层次聚类树tree

ans = cluster(tree,k) %创建k分类

ans = clusterdata(X,k) %一次聚类
					   % 等价于:
					   % Y = pdist(X,’euclid’);
					   % Z = linkage(Y,’single’);
					   % T = cluster(Z,cutoff);

DBSCAN 算法

Python

1
2
3
4
5
6
7
8
9
from sklearn.cluster import DBSCAN

DBSCAN(eps=0.5,min_samples=5,metric='euclidean',mtric_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 算法

谱聚类

参考

  1. Kmeans聚类算法详解|CSDN
  2. MATLAB K-means聚类的介绍与使用|CSDN
  3. scikit-learn中的KMeans聚类实现
  4. 聚类算法(原型、密度、层次聚类)|知乎
  5. Matlab聚类分析_层次聚类|CSDN
  6. 聚类分析初探（一）引言|CSDN
  7. Sklearn(二): sklearn.cluster 各种聚类方法解析|CSDN