聚类
原理
9.1 聚类任务
- 在“无监督学习”(unsupervised learning)中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”(clustering)。
- 聚类试图将数据集中的样本划分成若干个通常是不想交的子集，每个子集称为一个“簇”(cluster)。通过这样的划分，每个簇可能对应于一些潜在的概念（类别）；需要说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇所对应的概念语义需由使用者来把握和命名。
- 聚类既能作为一个单独过程，用于寻找数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。
9.2 性能度量
- 聚类性能度量亦称聚类“有效性指标”(validity index)。与监督学习中的性能度量作用相似，对聚类结果，我们需通过某种性能度量来评估其好坏；另一方面，若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。
- 直观上看，我们希望“物以类聚”，即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同。换言之，聚类结果的“簇内相似度”(intra-cluster similarity)高且“簇间相似度”(inter-cluster similarity)低。
- 聚类性能度量大致有两类。一类是将聚类结果与某个“参考模型”(reference model)进行比较，称为“外部指标”(external index)；另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”(internal index)。
- 外部指标
- Jaccard 系数 (Jaccard Coefficient, JC)
- FM 指数(Fowlkes and Mallows Index, FMI)
- Rand指数(Rand Index, RI)
- 内部指数
- DB指数 (Davies-Bouldin Index, DBI)
- Dunn指数(Dunn Index, DI)
9.3 距离计算
- 对函数dist(. , .)，它是一个“距离度量”(distance measure)，则需满足一些基本性质：
- 非负性：dist(xi, xj) >= 0
- 同一性：dist(xi, xj) = 0 当且仅当 xi = xj
- 对称性：dist(xi, xj) = dist(xj, xi)
- 直递性：dist(xi, xj) <= dist(xi, xk) + dist(xk, xj)
- 最常用的是“闵可夫斯基距离”(Minkowski distance)。当p=2时，闵可夫斯基距离即欧式距离(Euclidean distance)。当p=1时，闵可夫斯基距离即曼哈顿距离(Manhattan distance)。
- 我们常将属性划分为“连续属性”(continuous attribute)和“离散属性”(categorical attribute)，前者在定义域上有无穷多个可能的取值，后者在定义域上是有限个取值。然而，在讨论距离计算时，属性上是否定义了“序”关系更为重要。例如定义域为{1, 2, 3}的离散属性与连续属性的性质更接近一些，能直接在属性值上计算距离：“1”与“2”比较接近，与“3”比较远，这样的属性称为“有序属性”(ordinal attribute)；而定义域为{飞机, 火车, 轮船}这样的离散属性则不能直接在属性值上计算距离，称为“无序属性”(non-ordinal attribute)。显然，闵可夫斯基距离可用于有序属性。
- 对无序属性可采用VDM。
- 需要注意的是，通常我们是基于某种形式的距离来定义“相似度度量”(similarity measure)，距离越大，相似度越小。然而，用于相似度度量的距离未必一定要满足距离度量的所有基本性质，尤其是直递性。这样的距离称为“非度量距离”(non-metric distance)。
9.4 原型聚类
- 原型聚类亦称“基于原型的聚类”(prototype-based clustering)，此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。通常情况下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解放松，将产生不同的算法。
9.4.1 k均值算法
- 给定样本集 D = {x1, x2, ..., xm}，“k均值”(k-means)算法最小化误差。在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，E值越小则簇内样本相似度越高。
- 最小化k-means并不容易，找到它的最优解需考察样本集 D 所有可能的簇划分，这是一个 NP 难问题。因此，k均值算法采用了贪心策略，通过迭代优化来近似求解。
9.4.2 学习向量量化
- 与k均值算法类似，“学习向量量化”(Learning Vector Q uantization, LVQ)也是试图找到一组原型向量来刻画聚类结构，但与一般聚类算法不同的是，LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。
9.4.3 高斯混合聚类
- 与k均值、LVQ用原型向量来刻画聚类结构不同，高斯混合(Mixture-of-Gaussian)聚类采用概率模型来表达聚类原型。
9.5 密度聚类
- 密度聚类亦称“基于密度的聚类”(density-based clustering)，此类算法假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
- DBSCAN 是一种著名的密度聚类算法，它基于一组“邻域”(neighborhood)参数来刻画样本分布的紧密程度。
9.6 层次聚类
- 层次聚类(hierarchical clustering)试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。
- AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇个数。这里的关键是如何计算聚类簇之间的距离。实际上，每个簇是一个样本集合，只需采用关于集合的某种距离即可。最小距离由两个簇的最近样本决定，最大距离由两个簇的最远样本决定，而平均距离则由两个簇的所有样本共同决定。
