1. Distance Measures
目的: 我们通过刻画不同形式的距离度量, 来表征同类样本间的相似性和不同样本间的差异性
1.1. Metric Space
Formally, Metric Space (度量空间) 是一个有序数对 $(X,d)$, 其中 $X$ 是一个集合, $d$ 是定义在 $X$ 上的函数 ($d:X^2\to \mathbb R$). 度量空间满足如下的四条公理:
1.2. Common Metric Functions
- $\text{Euclidean}$ Distance:
- Cosine Similarity:
- $\text{Manhattan}$ Distance:
- $\text{Chebyshev}$ Distance:
- $\text{Mahalanobis}$ Distance:
其中, 欧式距离, 曼哈顿距离和车比雪夫距离都可以算是特殊的 $\text{Mincowski}$ 距离:
2. Clustering Criteria
聚类有了模式的相似性度量/距离度量, 还需要一种基于数值的聚类准则, 才能将相似的样本分在同一类, 相异的
样本分在不同的类. 判別聚类结果好坏的一般标准:
- 类内距离小, 类间距离大
- 或者, 簇内相似度 (intra-cluster sinilarity)高, 簇间相似低 (inter-cluster similarity)
需要一个能对聚类过程或聚类结果的优劣进行评估的准则函数. 如果聚类准则函数选择得好, 聚类质量就会高.
- 试探方法: 凭直观感觉或经验
针对实际问题定义一种距离度量的阈值, 然后按最近邻规则指定某些样本属于某一个聚类类别. 例如对欧氏距离, 它反映了样本间的近邻性, 但将一个样本分到不同类别中的哪一个时, 还必须规定一个距离度量的阈值作为聚类的判别准则., - 聚类准则函数方法: 由于聚类是将样本进行分类以使类别之间的分离性尽可能大
因此聚类准则应是反映类别间相似性或分离性的函数; 每个类別都是由一系列样本组成的, 因此一般来说类别(sample sets) 的可分离性和样本 (samples) 的可分离性是直接相关的; 可以定义聚类准则函数为样本集 $\{\boldsymbol x\}$ 和类别 $\{S_j\mid j=1,2,\ldots,c\}$ 的函数, 从而使聚类分析转化为寻找准则函数极值的最优化问题.,
但是值得注意的是, 聚类的好坏不存在绝对标准,
The goodness of clustering depends on the opinion of the user “ ”
3. Clustering Methods
3.1. Exploration-based Method
基于试探的聚类搜索算法
是一种基于贪心策略的聚类算法, 它通过不断试探和调整聚类中心来实现聚类.
该算法首先随机选择一些数据点作为初始聚类中心, 然后将所有数据点分配到这些聚类中心中最近的一个中心. 接着, 该算法会对每个聚类中心进行试探, 即在该聚类中心的周围随机选择一些点作为备选聚类中心, 并将该聚类中心替换成备选聚类中心. 如果替换后聚类效果变得更好, 则保留该替换, 否则还原聚类中心
该算法重复以上步骤
基于试探的聚类搜索算法的优点是能够避免局部最优解
3.2. Systematic Methods
2.3. Dynamic Methods
4. Clustering Evaluation
聚类结果的评估 (验证) 与聚类本身一样困难
内部“ 评估” 其中聚类被总结为一个单一的质量分数, 外部“ 评估” 其中聚类与现有的, 基准真相(ground truth)“ 分类进行比较” - 由人类专家进行
手动“ 评估” , 间接“ 通过评估聚类在其预期应用中的效用来进行评估” 。
内部评估措施存在一个问题
外部评估也有类似的问题
因此
4.1. 内部评估指标
1. $\small \text{Silhouette Coefficient}$
2. $\small \text{Calinski-Harabaz Index}$
3. $\small \text{Davies-Bouldin Index}$
4.2. 外部评估指标
聚类分析有如下常见的评估指标, 用来衡量聚类算法的优与劣
1. Purity
在聚类结果的评估标准中
其中:
- $N$ 表示样本的总数
- $\Omega=\{\omega_1, \omega_2, ..., \omega_K\}$ 表示聚类后的簇的集合, $\omega_k$ 表示第 $k$ 个簇, $K$ 表示聚类后的簇的总数
- $C=\{c_1, c_2, ..., c_J\}$ 表示正确的类别, $c_j$ 表示第 $j$ 个类别中的真实的样本, $J$ 表示真实样本的总数
更优雅地可以写成这样:
不难发现, 最好的情况是 $P=1$, 最差的情况是 $P=0$. 越大表示效果越好.
2. Rand Index & $\small \text F \mbox-value$
注意到, 任取两个样本点, 得到的结果总是只有四种情况, 即:
- $TP$: 表示两个同类样本点在同一个簇中的情况数量
- $FP$: 表示两个非同类样本点在同一个簇中的情况数量
- $TN$: 表示两个非同类样本点分别在两个簇中的情况数量
- $FN$: 表示两个同类样本点分别在两个簇中的情况数量
兰德指数 ($\text{Rand Index}$) 有如下的定义:
3. Adjusted Rand Index
调整兰德系数 ($\small \text{Adjusted Rand Index}$) 是兰德系数的一个改进版本
![](https://naturalifica.oss-cn-nanjing.aliyuncs.com/~/Users/wuchentian/SoloLearning/Blog/source/imgs/imgsimage-20230417171003651.png)
其中, $X=\{X_1, X_2, ..., X_r\}$ 表示聚类得到的 $r$ 个簇的集合, $Y=\{Y_1, Y_2, ..., Y_s\}$ 表示据正确标签对聚类结果修正后的集合, $n_{ij}=|X_i\cap Y_j|$. 在这样的基础上, $\text{ARI}$ 的定义如下:
其中,
根据平凡的初等代数推导, 可以得到 $\text{ARI}$ 的范围是 $[-1, 1]$, 同时发现对于充分大的样本, 考虑中心极限定理, $\text{ARI}$ 可以接近于 $0$ . $\text{ARI}<0$ 表示聚类的结果比随机选择的结果还要差. 只有当 $\text{ARI}>0$ 时, 聚类才开始发挥作用.
可以得到 $\text{ARI}$ 的等价表达式如下:
如果是高中的时候, 我高低得露两手,
但是现在大二了算不出来了
4. Normalized Mutual Information
$\text{NMI}$ ($\text{Normalized Mutual Information}$) 即归一化互信息. 对于聚类后的簇的集合 $\Omega$ 和正确的集合 $C$, $\text{NMI}$ 有定义如下:
其中, $I$ 表示互信息(Mutual Information), $H$ 为熵 (详细的定义可以查看 第十一章 信息与熵 ). 注意这里的均值并不规定, 也可以为几何均值或任意幂均值. 更具体地说 (其中概率的替换则是由概率的极大似然估计推导而来):
其中,
- $p(\omega)$ 表示样本属于聚类簇 $\omega$ 的概率
- $p(c)$ 表示样本属于类别 $c$ 的概率
- $p(\omega\cap c)$ 表示样本同时属于聚类簇 $\omega$ 和类别 $c$ 的概率
直观地,互信息还可以写成这样的形式: $I(\Omega; C)=H(\Omega)-H(\Omega|C)$.
实际上, $\text{NMI}$ 是对互信息的一些优化. 由互信息的定义不难发现, 当 $\Omega$ 和 $C$ 独立时, 两者的互信息为 $0$, 当 $\Omega$ 完整地复现了 $C$ 时, 互信息取得了最大值, 为 $1$ . 但是当 $|\Omega|=N$ 时, $\text{MI}$ 也能取到最大值, 这是非常不好的, 即它并不对簇数目较大的聚类结果进行惩罚, 因此也不能在其他条件一样的情况下, 对簇数目越小越好的这种期望进行形式化. $\text{NMI}$ 则可以解决上述问题,因为熵会随着簇的数目的增长而增大
用一些分析的手段可以证明, $\text{NMI}\in [0,1 ]$.
5. Adjusted Mutual Information
$\text{AMI}$ ($\text{Adjusted Mutual Information}$) 即调整互信息. 对于聚类后的簇的集合 $\Omega$ 和正确的集合 $C$, $\text{AMI}$ 有定义如下:
同样, 这里的均值也不规定, 也可以为几何均值或任意幂均值. 值得一提的是, 互信息的期望的计算方法如下:
仍然考虑这样的列联表
![](https://naturalifica.oss-cn-nanjing.aliyuncs.com/~/Users/wuchentian/SoloLearning/Blog/source/imgs/imgsimage-20230417171003651.png)
可喜可贺, 上式为笔者自己推导得出