9.1 聚类任务
无监督学习目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律
聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个簇(cluster)，通过这样的划分，每个簇可能对应于一些潜在的概念，这些概念对于算法而言事先是未知的，聚类过程仅能自动形成簇结构，而簇对应的概念语义需要使用者来把握
聚类既能作为一个单独的过程，用于寻找数据内在的分布结构，也可作为分类等其他任务的前驱过程
9.2 性能度量
我们希望聚类结果的簇内相似度(intra-cluster similarity)高且簇间相似度(inter-cluster similarity)低
聚类性能度量大致有两类，一类是将聚类结果与某个参考模型比较，称为外部指标(external index);另一类是直接考察聚类结果而不利用任何参考模型，称为内部指标(internal index)
- Jaccard系数(Jaccard Coefficient,简称JC)
$$JC=\frac{a}{a+b+c}$$ - FM指数(简称FMI)
$$FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}$$ - Rand指数(简称RI)
$$RI=\frac{2(a+d)}{m(m-1)}$$
上述性能度量均在\([0,1]\)之间，值越大越好
- DB指数(DBI):
- Dumn指数(DI):
DBI指数的值越大越好，DI指数的值越小越好
9.3 距离计算
对函数dist(),若它是个距离度量(distance measure),需要满足：
- 非负性
- 同一性
- 对称性
- 直递性
p=2时，闵可夫斯基距离称为欧式距离，p=1时，被称为曼哈顿距离
我们常将属性划分为连续属性(continuous attribute)和离散属性(categorical attribute),在讨论距离计算时，属性上是否定义了序关系，闵可夫斯基适用于有序属性
对无序属性可采用VDM(Value Difference Metric)
需要注意的是通常我们是基于某种形式的距离来定义相似度度量，距离越大相似度越小，然而用于相似度度量的距离未必一定要满足距离度量的所有性质，尤其是直递性
9.4 原型聚类
原型聚类是基于原型的聚类(prototype-based clustering),原型是指样本空间中具有代表性的点。通常情况下，算法先对原型进行初始化，然后对原型进行迭代更新求解，采用不同的原型表示，不同的求解方法将产生不同的算法
9.4.1 k均值算法
最小化式9.24是个NP难的问题，因此k均值算法采用了贪心策略，通过迭代优化来近似求解式9.24
9.4.2 学习向量量化
学习向量量化(Learning Vector Quantization,简称LVQ)也是也是试图找到一组原型向量来刻画聚类结构，LVQ假设数据样本带有类别标记，学习过程利用这些监督信息来辅助聚类
LVQ的关键是如何更新原型向量，直观上看，对样本\(\vec{x_j}\),若最近的原型向量\(\vec{p_{i^} }\)与\(\vec{x_j}\)的类标记相同，则令\(\vec{p_{i^} }\)向\(\vec{x_j}\)的方向靠拢：
学得一组原型向量后，即可实现对样本空间的簇划分，对任意样本\(\vec{x}\),它将被划入与其距离最近的原型向量所代表的簇中，换言之，每个原型向量\(\vec{p_i}\)定义了一个与之相关的区域\(R_i\)，该区域中每个样本与\(\vec{p_i}\)的距离不大于它与其他原型向量\(\vec{p_i^{‘} } (i^{‘} \neq i)\)的距离，即
若将\(R_i\)中的样本全用向量\(\vec{p_i}\)表示，则可实现数据的有损压缩(lossy compression),这称为向量量化，LVQ由此而得名
9.4.3 高斯混合聚类
高斯混合聚类采用概率模型来表达聚类模型
假设样本的生成过程由高斯混合分布给出：首先，根据\(\alpha_1,\alpha_2,…,\alpha_k\)定义的先验分布选择高斯混合成分，其中\(\alpha_i\)为选择第i个混合成分的概率，然后根据被选择的混合成分的概率密度函数进行采样，从而生成相应的样本
高斯聚类是采用概率模型对原型进行刻画，簇划分则由原型对应后验概率确定
采用极大似然估计，即最大化对数似然
9.5 密度聚类
此类算法假设聚类结构能通过样本分布的紧密程度确定
DBSCAN基于一组邻域参数\( (\epsilon,MinPts) \)来刻画样本分布的紧密程度
DBSCAN将簇定义为：由密度可达关系导出的最大的密度相连样本集合，给定邻域参数\( (\epsilon,MinPts) \)，簇\(C \subseteq D\)是满足下列性质的非空样本子集：
实际上若\(\vec{x}\)为核心对象，由\(\vec{x}\)密度可达的所有样本组成的集合记为\(X\),则不难证明\(X\)即为满足连接性与最大性的簇。于是，DBSCAN算法先任选数据集中的一个核心对象为种子(seed),再由此出发确定相应的聚类簇
9.6 层次聚类
层次聚类(hierarchical clustering)试图在不同层次对数据集进行划分，从而形成树形的聚类结构
AGNES是一种采用自底向上聚合策略的层次聚类算法，它先将数据集中的每个样本看作一个初始簇，然后在算法的每一步中找出距离最近的两个聚类进行合并，直到达到预设的聚类簇个数，这里的关键是如何计算聚类簇之间的距离，给定聚类簇\(C_i,C_j\)可通过下面的式子来计算距离：
以西瓜数据集4.0为例，令AGNES算法2一直执行到所有样本出现在一个簇中，即\(k=1\)：
