p202 - p224
今天平平淡淡

第九章 聚类

9.4 原型聚类

“原型”是指样本空间中具有代表性的点。

9.4.1 k-means

针对所得簇最小化平方误差
想要最小化平方误差 是一个NP难问题
因此使用了贪心策略

算法伪码：p203 图9.2

算法开始随机选取样本作为初始均值向量
考察每个样本，与哪个均值向量最近，从而分到哪个簇
分完一轮之后更新均值向量
重复以上过程直至收敛。

9.4.2 学习向量量化（LVQ）

也是试图找到一组原型向量。
但LVQ假设数据样本带有标记，利用这些监督信息来辅助聚类。

LVQ的目的是学得一组n维原型向量，每个向量代表一个簇

算法伪码：p205 图9.4
先初始化原型向量。
每一轮迭代中，随机选取一个有标记的训练样本，找到和他最近的原型向量，并根据两者的类别标记决定如何更新。如果一样，则将原型更靠近一些。不一样，则远离一些。

可以这样理解：每个原型向量定义了与之相关的一个区域。
这些区域形成一个划分。
该划分通常称为“Voronoi划分”

9.4.3 高斯混合聚类

与上两个不同，高斯混合聚类采用概率模型来表达聚类原型。
p206 - 210。
比较数学。

9.5 密度聚类

基于密度的聚类假设聚类结构能通过样本分布的紧密程度来确定。

DBSCAN，基于一组邻域参数来刻画紧密程度。
ε-邻域、核心对象、密度直达、密度可达、密度相连的定义。p212

从而DBSCAN对“簇”进行了定义：
连续性：同一个簇的必然密度相连。
最大性：每个都不可再扩大。

那么如何找到满足上面性质的簇呢？不难证明，由x密度可达的所有样本组成的集合就是一个簇。

于是，DBSCAN先选一个样本作为种子。找簇。一直下去直到找完。

9.6 层次聚类

形成树形的聚类结构。
既可以从上往下，也可以从下往上。

AGNES：从下往上。
把每个样本看成一个初始聚类簇，然后每一步对两个最近的合并。直到簇数达到要求。

簇间距离的刻画：最小距离/最大距离/平均距离。
伪码 p215 图9.11