聚类笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  本文做一些关于聚类的的笔记,具体包括了原型聚类,密度聚类和层次聚类。

聚类任务

  聚类的定义很好理解,就是把数据集中的样本划分为若干个通常是不想交的子集,每个子集也称作为簇(cluster)。聚类既能作为一个单独过程,用于寻找数据内在的分布结构,也可作为分类等其他学习任务的前驱过程。

性能度量

  聚类性能度量亦称聚类有效性指标(validity index),若明确了最终将要使用的性能度量,则可直接将其作为聚类过程的优化目标,从而更好地得到符合要求的聚类结果。
  好的聚类应当是同一簇的样本尽可能彼此相似,不同簇的样本尽可能不同。也就是说聚类结果的簇内相似度(intra-cluster similarity)高且簇间相似度(inter-cluster similarity)低。
  聚类性能度量大致有两类。一类是将聚类结果与某个参考模型进行比较,称为外部指标(external index),另一类是直接考察聚类结果而不利用任何参考模型,称为内部指标(internal index)。
  对数据集\(D=\left\{\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \ldots, \boldsymbol{x}_{m}\right\}\),假定通过聚类给出的簇划分为\(\mathcal{C}=\{C_1,C_2,\cdots,C_k\}\),参考模型给出的簇划分为\(\mathcal{C^*}=\{C_1^*,C_2^*,\cdots,C_k^*\}\),令\(\boldsymbol{\lambda}\)\(\boldsymbol{\lambda}^*\)分别表示对应的簇标记向量。将样本两两配对,定义: \[ \begin{aligned} a &=|S S|, \quad S S=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) | \lambda_{i}=\lambda_{j}, \lambda_{i}^{*}=\lambda_{j}^{*}, i<j\right) \} \\ b &=|S D|, \quad S D=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) | \lambda_{i}=\lambda_{j}, \lambda_{i}^{*} \neq \lambda_{j}^{*}, i<j\right) \} \\ c &=|D S|, \quad D S=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) | \lambda_{i} \neq \lambda_{j}, \lambda_{i}^{*}=\lambda_{j}^{*}, i<j\right) \} \\ d &=|D D|, \quad D D=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) | \lambda_{i} \neq \lambda_{j}, \lambda_{i}^{*} \neq \lambda_{j}^{*}, i<j\right) \} \end{aligned} \]   由于每个样本对仅能出现在一个集合中,因此有\(a+b+c+d=\frac{m(m-1)}{2}\)成立。基于上面四个式子可导出下面这些常用的聚类性能度量外部指标:

  • Jaccard系数(Jaccard Coefficient, JC) \[ JC = \frac{a}{a+b+c} \]
  • FM指数(Fowlkes and Mallows Index, FMI) \[ \mathrm{FMI}=\sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c}} \]
  • Rand指数(Rand Index, RI) \[ RI = \frac{2(a+d)}{m(m-1)} \]   上述性能度量的结果值均在\([0,1]\)区间,值越大越好。
      考虑聚类结果的簇划分\(\mathcal{C}=\{C_1,C_2,\cdots,C_k\}\),定义: \[ \begin{aligned} \operatorname{avg}(C) &=\frac{2}{|C|(|C|-1)} \sum_{1 \leqslant i<j \leqslant|C|} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ \operatorname{diam}(C) &=\max _{1 \leqslant i<j \leqslant|C|} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ d_{\min }\left(C_{i}, C_{j}\right) &=\min _{\boldsymbol{x}_{i} \in C_{i}, \boldsymbol{x}_{j} \in C_{j}} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ d_{\operatorname{cen}}\left(C_{i}, C_{j}\right) &=\operatorname{dist}\left(\boldsymbol{\mu}_{i}, \boldsymbol{\mu}_{j}\right) \end{aligned} \]   其中,\(dist\)用于计算两个样本之间的距离,\(\boldsymbol{\mu}\)代表着簇内中心点的距离。上面四个式子分别代表着簇内样本间的平均距离,簇内样本间的最远距离,簇间样本间的最近距离和簇间中心点的距离。基于这四个式子可导出下面这些常用的聚类性能度量内部指标:

  • DB指数(Davies-Bouldin Index, DBI) \[ \mathrm{DBI}=\frac{1}{k} \sum_{i=1}^{k} \max _{j \neq i}\left(\frac{\operatorname{avg}\left(C_{i}\right)+\operatorname{avg}\left(C_{j}\right)}{d_{\operatorname{cen}}\left(\boldsymbol{\mu}_{i}, \boldsymbol{\mu}_{j}\right)}\right) \]
  • Dunn指数(Dunn Index, DI) \[ \mathrm{DI}=\min _{1 \leqslant i \leqslant k}\left\{\min _{j \neq i}\left(\frac{d_{\min }\left(C_{i}, C_{j}\right)}{\max _{1 \leqslant l \leqslant k} \operatorname{diam}\left(C_{l}\right)}\right)\right\} \]   显然,DBI的值越小越好,而DI则相反,值越大越好。

距离计算

  我们来具体考虑下\(dist\)函数,若它是一个距离度量(distance measure),他需要满足非负性、同一性、对称性和直递性(三角不等式)。下面是几种常见的距离函数:

  • 闵可夫斯基距离(Minkowski distance) \[ \operatorname{dist}_{\mathrm{mk}}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\sum_{u=1}^{n}\left|x_{i u}-x_{j u}\right|^{p}\right)^{\frac{1}{p}} \]
  • 欧氏距离(Euclidean distance),即\(p=2\)的闵可夫斯基距离 \[ \operatorname{dist}_{\mathrm{ed}}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|_{2}=\sqrt{\sum_{u=1}^{n}\left|x_{i u}-x_{j u}\right|^{2}} \]
  • 曼哈顿距离(Manhattan distance),即\(p=1\)的闵可夫斯基距离 \[ \operatorname{dist}_{\operatorname{man}}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|_{1}=\sum_{u=1}^{n}\left|x_{i u}-x_{j u}\right| \]
  • 切比雪夫距离(Chebyshev Distance),即\(p \to \infty\)的情况。

  对于离散属性(categorical attribute),闵可夫斯基距离可应用于类似\(\{1,2,3\}\)的有序属性(ordinal attribute),而不可直接应用于类似\(\{红苹果, 青苹果\}\)这样的无序属性(non-ordinal attribute)。
  对无序属性可采用VDM(Value Difference Metric)方法。令\(m_{u,a}\)表示在属性\(u\)上取值为\(a\)的样本数,\(m_{u,a,i}\)表示在第\(i\)个样本簇 中在属性\(u\)上取值为\(a\)的样本数,则属性\(u\)上两个离散值\(a\)\(b\)之间的VDM距离为: \[ \operatorname{VDM}_{p}(a, b)=\sum_{i=1}^{k}\left|\frac{m_{u, a, i}}{m_{u, a}}-\frac{m_{u, b, i}}{m_{u, b}}\right|^{p} \]   将闵可夫斯基距离和VDM结合即可处理混合属性,假定有\(n_c\)个有序属性、\(n-n_c\)个无序属性,令有序属性排列在无序属性之前,则: \[ \operatorname{MinkovDM}_{p}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\sum_{u=1}^{n_{c}}\left|x_{i u}-x_{j u}\right|^{p}+\sum_{u=n_{p}+1}^{n} \operatorname{VDM}_{p}\left(x_{i u}, x_{j u}\right)\right)^{\frac{1}{p}} \]   当样本空间中不同属性的重要性不同时,可使用加权距离(weighted distance),以加权闵可夫斯基距离为例: \[ \operatorname{dist}_{\mathrm{wmk}}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(w_{1} \cdot\left|x_{i 1}-x_{j 1}\right|^{p}+\ldots+w_{n} \cdot\left|x_{i n}-x_{j n}\right|^{p}\right)^{\frac{1}{p}}(通常w_i \ge 0, \sum_{i=1}^{n} w_{i}=1) \]   需注意的是,通常我们是基于某种形式的距离来定义相似度度量(similarity measure),距离越大,相似度越小。然而,用于相似度度量的距离未必一定要满足距离度量的所有基本性质,尤其是直递性。如下图,在某些任务中我们可能希望有这样的相似度度量:“人”和“马”分别与“人马”相似,但“人”与“马”很不相似。要达到这个目的,可以令“人”和“马”与“人马”之间的距离都比较小,但“人”与“马”之间的距离很大,此时该距离不再满足直递性。这样的跟离称为非度量距离(non-metric distance)。

  此外,我们介绍的距离计算式都是事先定义好的,但在不少现实任务中,有必要基于数据样本来确定合适的距离计算式,这可通过距离度量学习(distance metric learning)来实现。

原型聚类(Protoytpe-based Clustering)

  原型聚类假设聚类结构能够通过一组原型刻画,算法先对原型进行初始化,然后对原型进行迭代更新求解,采用不同的原型表示和不同的求解放时,将会产生不同的算法,下面是几种常见的原型聚类算法。

k均值(K-means)算法

  k均值算法针对聚类所得簇划分\(\mathcal{C}=\left\{C_{1}, C_{2}, \ldots, C_{k}\right\}\)最小化平方误差: \[ E=\sum_{i=1}^{k} \sum_{\boldsymbol{x} \in C_{i}}\left\|\boldsymbol{x}-\boldsymbol{\mu}_{i}\right\|_{2}^{2} \\ \boldsymbol{\mu}_{i}=\frac{1}{\left|C_{i}\right|} \sum_{\boldsymbol{x} \in C_{i}} \boldsymbol{x} \]   上式刻画了簇内样本围绕均值向量的紧密程度,\(E\)值越小则簇类样本相似度越高。最小化上式需要考虑样本集\(D\)所有可能的簇划分,这是个NP难问题,因此k均值算法采用了贪心策略,通过迭代优化来求近似解。具体算法流程图如下图所示:

学习向量量化(Learning Vector Quantization, LVQ)

  与k均值算法类似,LVQ也是试图找到一组原型向量来刻画聚类结构,但与般聚类算法不同的是,LVQ假设数据样本带有类别标记,学习过程利用样本的这些监督信息来辅助聚类。LVQ的目标是学得一组原型向量\(\left\{p_{1}, p_{2}, \ldots, p_{q}\right\}\),具体算法流程图如下所示:

  算法的停止条件可以是己达到最大迭代轮数或原型向量更新很小甚至不再更新等等。我们重点关注下如何更新原型向量。直观上看,对样本\(\boldsymbol{x}_j\),若最近的原型向量\(\boldsymbol{p}_{i*}\)\(\boldsymbol{x}_j\)的类别标记相同,则令\(\boldsymbol{p}_{i*}\)\(\boldsymbol{x}_j\)的方向靠拢,如第7行所示,此时新原型向量为: \[ \boldsymbol{p}^{\prime}=\boldsymbol{p}_{i^{*}}+\eta \cdot\left(\boldsymbol{x}_{j}-\boldsymbol{p}_{i^{*}}\right) \]   \(\boldsymbol{p}^{'}\)\(\boldsymbol{x}_j\)之间的距离为: \[ \begin{aligned}\left\|\boldsymbol{p}^{\prime}-\boldsymbol{x}_{j}\right\|_{2} &=\left\|\boldsymbol{p}_{i^{*}}+\eta \cdot\left(\boldsymbol{x}_{j}-\boldsymbol{p}_{i^{*}}\right)-\boldsymbol{x}_{j}\right\|_{2} \\ &=(1-\eta) \cdot\left\|\boldsymbol{p}_{i^{*}}-\boldsymbol{x}_{j}\right\|_{2} \end{aligned} \]   令学习率\(\eta \in(0,1)\),则原型向量\(\boldsymbol{p}_{i*}\)在更新为\(\boldsymbol{p}^{'}\)之后将更接近\(\boldsymbol{x}_j\)
  类似的,若\(\boldsymbol{p}_{i*}\)\(\boldsymbol{x}_j\)的类别标记不同,则更新后的原型向量与\(\boldsymbol{x}_j\)之间的距离将增大为\((1+\eta) \cdot\left\|\boldsymbol{p}_{i^{*}}-\boldsymbol{x}_{j}\right\|_{2}\),从而更远离\(\boldsymbol{x}_j\)
  在学得一组原型向量\(\left\{p_{1}, p_{2}, \ldots, p_{q}\right\}\)后,即可实现对样本空间\(\mathcal{X}\)的簇划分。对任意样本,它将被划入与其距离最近的原型向量所代表的簇中。每个原型向量\(\boldsymbol{p}_i\)定义了与之相关的一个区域\(R_i\),该区域中每个样本与\(\boldsymbol{p}_i\)的距离不大于它与其他原型向量\(\boldsymbol{p}_{i^{\prime}}\left(i^{\prime} \neq i\right)\)的距离,即: \[ R_{i}=\left\{\boldsymbol{x} \in \mathcal{X} |\left\|\boldsymbol{x}-\boldsymbol{p}_{i}\right\|_{2} \leqslant\left\|\boldsymbol{x}-\boldsymbol{p}_{i^{\prime}}\right\|_{2}, i^{\prime} \neq i\right\} \]   由此可以形成对样本空间\(\mathcal{X}\)的簇划分\(\{R_1,R_2,\cdots,R_q\}\),该划分通常称为Voronoi剖分(Voronoi tessellation)。

若将\(R_i\)中样本全用原型向量\(p_i\)表示,则可实现数据的有损压缩(lossy compression),这称为向量量化(vector quantization),LVQ也由此得名。

高斯混合聚类(Mixture-of-Gaussian)

  与k均值、LVQ用原型向量来刻画聚类结构不同,高斯混合聚类采用概率模型来表达聚类原型。下面是高斯分布的定义,对\(n\)维样本空间\(\mathcal{X}\)中的随机向量\(\boldsymbol{x}\),若\(\boldsymbol{x}\)服从高斯分布,其概率密度函数为: \[ p(\boldsymbol{x})=\frac{1}{(2 \pi)^{\frac{n}{2}}|\mathbf{\Sigma}|^{\frac{1}{2}}} e^{-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu})^{\mathrm{T}} \boldsymbol{\Sigma}^{-1}(\boldsymbol{x}-\boldsymbol{\mu})} \]   其中\(\boldsymbol{\mu}\)\(n\)维均值向量,\(\boldsymbol{\Sigma}\)\(n \times n\)的协方差矩阵,高斯分布完全由这两个参数确定,因此将概率密度函数记为\(p(\boldsymbol{x} | \boldsymbol{\mu}, \boldsymbol{\Sigma})\),高斯混合分布可定义为: \[ p_{\mathcal{M}}(\boldsymbol{x})=\sum_{i=1}^{k} \alpha_{i} \cdot p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \\ \sum_{i=1}^{k} \alpha_{i}=1 \\ \int p_{\mathcal{M}}(\boldsymbol{x}) \mathrm{d} \boldsymbol{x}=1 \]   该分布由\(k\)个混合成分组成,每个混合成分对应一个高斯分布。\(\alpha_i \gt 0\)为相应的混合系数(mixture coefficient)。   假设样本的生成过程由高斯混合分布给出:首先,根据\(\alpha_1,\cdots,\alpha_i\)定义的先验分布选择高斯混合成分,其中\(\alpha_i\)为选择第\(i\)个混合成分的概率。然后,根据被选择的混合成分的概率密度函数进行采样,从而生成相应的样本。
  若训练集\(\alpha_i\)由上述过程生成,令随机变量\(z_j \in \{1,\cdots,k\}\)表示生成样本\(\boldsymbol{x}_j\)的高斯混合成分,其取值未知。显然,\(z_j\)的先验概率\(P(z_j=i)\)对应于\(\alpha_i\)。根据贝叶斯定理,\(z_j\)的后验分布对应于: \[ \begin{aligned} p_{\mathcal{M}}\left(z_{j}=i | \boldsymbol{x}_{j}\right) &=\frac{P\left(z_{j}=i\right) \cdot p_{\mathcal{M}}\left(\boldsymbol{x}_{j} | z_{j}=i\right)}{p_{\mathcal{M}}\left(\boldsymbol{x}_{j}\right)} \\ &=\frac{\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\sum_{l=1}^{k} \alpha_{l} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{l}, \mathbf{\Sigma}_{l}\right)} \end{aligned} \]   \(p_{\mathcal{M}}\left(z_{j}=i | \boldsymbol{x}_{j}\right)\)给出了样本\(\boldsymbol{x}_j\)\(i\)个高斯混合成分生成的后验概率,简记为\(\gamma_{j i}(i=1,2, \dots, k)\)
  当高斯混合分布已知时,高斯混合聚类将把样本集\(D\)划分为\(k\)个簇\(\mathcal{C}=\left\{C_{1}, C_{2}, \ldots, C_{k}\right\}\),每个样本\(\boldsymbol{x}_j\)的簇标记\(\lambda_j\)如下确定: \[ \lambda_{j}=\underset{i \in\{1,2, \ldots, k\}}{\operatorname{argmax}} \gamma_{j i} \]   因此,从原型聚类的角度来看,高斯混合聚类是采用概率模型(高斯分布)对原型进行刻画,簇划分则由原型对应后验概率确定。
  模型参数\(\left\{\left(\alpha_{i}, \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) | 1 \leqslant i \leqslant k\right\}\)可采用极大似然估计,即最大化(对数)似然来求解: \[ \begin{aligned} L L(D) &=\ln \left(\prod_{j=1}^{m} p_{\mathcal{M}}\left(\boldsymbol{x}_{j}\right)\right) \\ &=\sum_{j=1}^{m} \ln \left(\sum_{i=1}^{k} \alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \mathbf{\Sigma}_{i}\right)\right) \end{aligned} \]   常采用EM算法进行迭代优化求解。我们做简单的推导一下。
  若参数\(\left\{\left(\alpha_{i}, \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) | 1 \leqslant i \leqslant k\right\}\)能使\(LL(D)\)最大化,则由\(\frac{\partial L L(D)}{\partial \mu_{i}}=0\)有: \[ \sum_{j=1}^{m} \frac{\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \mathbf{\Sigma}_{i}\right)}{\sum_{l=1}^{k} \alpha_{l} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{l}, \boldsymbol{\Sigma}_{l}\right)}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)=0 \]   由\(\gamma_{j i}=p_{\mathcal{M}}\left(z_{j}=i | \boldsymbol{x}_{j}\right)\)得: \[ \boldsymbol{\mu}_{i}=\frac{\sum_{j=1}^{m} \gamma_{j i} \boldsymbol{x}_{j}}{\sum_{j=1}^{m} \gamma_{j i}} \]   可以看出各混合成分的均值可通过样本加权平均来估计,样本权重是每个样本属于该成分的后验概率。
  类似的,由\(\frac{\partial L L(D)}{\partial \boldsymbol{\Sigma}_{i}}=0\)可得: \[ \boldsymbol{\Sigma}_{i}=\frac{\sum_{j=1}^{m} \gamma_{j i}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\mathrm{T}}}{\sum_{j=1}^{m} \gamma_{j i}} \]   对于混合系数\(\alpha_i\)除了要最大化\(LL(D)\),还需满足\(\alpha_{i} \geqslant 0, \sum_{i=1}^{k} \alpha_{i}=1\)。考虑\(LL(D)\)的拉格朗日形式: \[ L L(D)+\lambda\left(\sum_{i=1}^{k} \alpha_{i}-1\right) \]   对\(\alpha_i\)求偏导并等于0得: \[ \sum_{j=1}^{m} \frac{p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \mathbf{\Sigma}_{i}\right)}{\sum_{l=1}^{k} \alpha_{l} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{l}, \mathbf{\Sigma}_{l}\right)}+\lambda=0 \]   两边同乘以\(\alpha_i\)对所有样本求和可得\(\lambda=-m\),有: \[ \alpha_{i}=\frac{1}{m} \sum_{j=1}^{m} \gamma_{j i} \]   可以看出每个高斯成分的混合系数由样本属于该成分的平均后验概率确定。
  由上述推导即可获得高斯混合模型的EM算法:在每步迭代中,先根据当前参数来计算每个样本属于每个高斯成分的后验概率\(\gamma_{j i}\)(E步),再根据上面三个式子更新模型参数\(\left\{\left(\alpha_{i}, \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) | 1 \leqslant i \leqslant k\right\}\)(M步)。
  高斯混合聚类算法描述如下图所示,停止条件满足可以是已达到最大迭代轮数,或似然函数\(LL(D)\)增长很少甚至不再增长。

密度聚类(Density-based Clustering)

  密度聚类假设聚类结构能通过样本分布的紧密程度确定。密度聚类算法从样本密度的角度来考察样本之间的可连接性,并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

DBSCAN算法(Density-Based Spatial Clustering of Applications with Noise)

  DBSCAN是一种著名的密度聚类算法,它基于一组邻域参数\((\epsilon,MinPts)\)来刻画样本分布的紧密程度。定义以下概念:

  • \(\epsilon\)-邻域:对\(\boldsymbol{x}_{j} \in D\),其\(\epsilon\)-邻域包含样本集\(D\)中与\(\boldsymbol{x}_{j}\)的距离不大于\(\epsilon\)的样本,即\(N_{\epsilon}\left(\boldsymbol{x}_{j}\right)=\left\{\boldsymbol{x}_{i} \in D | \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \leqslant \epsilon\right\}\)
  • 核心对象(core object):若\(\boldsymbol{x}_{j}\)\(\epsilon\)-邻域至少包含\(MinPts\)个样本,即\(\left|N_{\epsilon}\left(\boldsymbol{x}_{j}\right)\right| \geqslant M i n P t s\),则\(\boldsymbol{x}_{j}\)是一个核心对象。
  • 密度直达(directly density-reachable):若\(\boldsymbol{x}_{j}\)位于\(\boldsymbol{x}_{i}\)\(\epsilon\)-邻域中,且\(\boldsymbol{x}_{i}\)是核心对象,则称\(\boldsymbol{x}_{j}\)\(\boldsymbol{x}_{i}\)密度直达。
  • 密度可达(density-reachable):对\(\boldsymbol{x}_{i}\)\(\boldsymbol{x}_{j}\),若存在样本序列\(\boldsymbol{p}_{1}, \boldsymbol{p}_{2}, \dots, \boldsymbol{p}_{n}\),其中\(\boldsymbol{p}_{1}=\boldsymbol{x}_{i}, \boldsymbol{p}_{n}=\boldsymbol{x}_{j}\)\(\boldsymbol{p}_{i+1}\)\(\boldsymbol{p}_{i}\)密度直达,则称\(\boldsymbol{x}_{j}\)\(\boldsymbol{x}_{i}\)密度可达。
  • 密度相连(density-connected):对\(\boldsymbol{x}_{i}\)\(\boldsymbol{x}_{j}\),若存在\(\boldsymbol{x}_{k}\)使得\(\boldsymbol{x}_{i}\)\(\boldsymbol{x}_{j}\)均由\(\boldsymbol{x}_{k}\)密度可达,则称\(\boldsymbol{x}_{i}\)\(\boldsymbol{x}_{j}\)密度相连。

  上图给出了上述概念的直观显示,\(MirtPts = 3\),虚线显示出\(\epsilon\)-邻域,\(\boldsymbol{x}_{1}\)是核心对象,\(\boldsymbol{x}_{2}\)\(\boldsymbol{x}_{1}\)密度直达,\(\boldsymbol{x}_{3}\)\(\boldsymbol{x}_{1}\)密度可达,\(\boldsymbol{x}_{3}\)\(\boldsymbol{x}_{4}\)密度相连。
  基于这些概念,DBSCAN将簇定义为:由密度可达关系导出的最大的密度相连样本集合。给定邻域参数\((\epsilon, MinPts)\),簇$$是满足以下性质的非空样本子集:

  • 连接性(coriiiectivity):\(\boldsymbol{x}_{i} \in C, \boldsymbol{x}_{j} \in C \Rightarrow \boldsymbol{x}_{i}\)\(\boldsymbol{x}_{j}\)密度相连。
  • 最大性(maximality):\(\boldsymbol{x}_{i} \in C, \boldsymbol{x}_{j}\)\(\boldsymbol{x}_{1}\)密度可达\(\Rightarrow \boldsymbol{x}_{j} \in C\)。   若\(\boldsymbol{x}\)为核心对象,由\(\boldsymbol{x}\)密度可达的所有样本组成的集合记为$\(,不难证明\)X\(即为满足连接性与最大性的簇,以此来从数据集\)D$中找出满足条件的聚类簇。具体算法如下图所示:

层次聚类(Hierarchical Clustering)

  层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构。数据集的划分可采用自底向上的聚合策略,也可采用自顶向下的分拆策略。

AGNES(AGgomerative NESting)

  AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作个初始聚类簇,然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并,该过程不断重复,直至达到预设的聚类簇个数。
  关键是如何计算聚类簇之间的距离,每个簇是一个样本集合,因此,只需采用关于集合的某种距离即可.例如,给定聚类簇\(C_i\)\(C_j\),可通过下面的式子来计算距离: \[ \begin{aligned} 最小距离: \qquad d_{\min }\left(C_{i}, C_{j}\right) &=\min _{\boldsymbol{x} \in C_{i}, \boldsymbol{z} \in C_{j}} \operatorname{dist}(\boldsymbol{x}, \boldsymbol{z}) \\ 最大距离: \qquad d_{\max }\left(C_{i}, C_{j}\right) &=\max _{\boldsymbol{x} \in C_{i}, \boldsymbol{z} \in C_{j}} \operatorname{dist}(\boldsymbol{x}, \boldsymbol{z}) \\ 平均距离: \qquad d_{\mathrm{avg}}\left(C_{i}, C_{j}\right) &=\frac{1}{\left|C_{i}\right|\left|C_{j}\right|} \sum_{\boldsymbol{x} \in C_{i}} \sum_{\boldsymbol{z} \in C_{j}} \operatorname{dist}(\boldsymbol{x}, \boldsymbol{z}) \end{aligned} \]   当聚类簇距离由\(d_{min}\)\(d_{max}\)\(d_{avg}\)计算时,AGNES算法被相应地称为单链接(single-linkage)、全链接(complete-linkage)或均链接(average-linkage)算法。具体算法如下图所示。

同一样本空间中间的集合\(X\)\(Z\)之间的距离还可通过豪斯多夫距离(Hausdorff Distance)计算: \[ \begin{array}{c}{\operatorname{dist}_{\mathrm{H}}(X, Z)=\max \left(\operatorname{dist}_{\mathrm{h}}(X, Z), \operatorname{dist}_{\mathrm{h}}(Z, X)\right)} \\ {\operatorname{dist}_{\mathrm{h}}(X, Z)=\max _{x \in X} \min _{z \in Z}\|\boldsymbol{x}-\boldsymbol{z}\|_{2}}\end{array} \]

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 聚类任务
  3. 3. 性能度量
    1. 3.1. 距离计算
  4. 4. 原型聚类(Protoytpe-based Clustering)
    1. 4.1. k均值(K-means)算法
    2. 4.2. 学习向量量化(Learning Vector Quantization, LVQ)
    3. 4.3. 高斯混合聚类(Mixture-of-Gaussian)
  5. 5. 密度聚类(Density-based Clustering)
    1. 5.1. DBSCAN算法(Density-Based Spatial Clustering of Applications with Noise)
  6. 6. 层次聚类(Hierarchical Clustering)
    1. 6.1. AGNES(AGgomerative NESting)
  7. 7. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 609.8k 字啦

载入天数...载入时分秒...