关于周志华老师的《机器学习》这本书的学习笔记
记录学习过程
本博客记录Chapter9

1 聚类任务

聚类任务（clustering）是一类典型的”无监督学习“任务，其训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律：将数据集中的样本划分为若干个通常是互不相交的子集，每个子集称为一个簇。

形式化地说，假定样本集$D=\{x_1,x_2,…,x_m\}$包含$m$个无标记样本，每个样本$x_i=(x_{i1},x_{i2},…,x_{in})$是一个$n$维地特征向量。则聚类算法将样本集$D$划分为$k$个不相交的簇$\{C_l|l=1,2,…,k\}$。我们用$\lambda_j\in \{1,2,…,k\}$表示样本$x_j$的”簇标记“（cluster label），即$x_j \in C_{\lambda_j}$。于是聚类的结果可以用包含$m$个元素的簇标记向量$\lambda = \{\lambda_1,\lambda_2,…,\lambda_j\}$表示。

2 性能度量

聚类性能度量亦称为”有效性指标“（validity index）。针对聚类问题，直观上看，我们希望”物以类聚“，即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同。换言之，聚类结果的”簇内相似度“应该比较高，并且”簇间相似度“应该比较低。

聚类性能度量的指标大致有两类：

• 外部指标（external index）：将聚类结果与某个参考模型（reference model）进行比较
• 内部指标（internal index）：直接考察聚类结果而不利用任何参考模型

对于数据集$D=\{x_1,x_2,…,x_m\}$，假定通过聚类得出的簇划分为$C=\{C_1,C_2,…,C_k\}$，参考模型给出的簇划分$C^*=\{C_1^*,C_2^*,…,C_s^*\}$，相应的，令$\lambda$与$\lambda^*$表示$C$与$C^*$的簇标记向量。我们将样本两两配对考虑，定义：