第9章 聚类

  • 聚类既能作为一个找寻数据内在分布结构的单独过程,也可以作为其他学习任务的前驱过程.
  • 我们希望"物以类聚",也就是聚类结果的"簇内相似度"高且"簇间相似度"低.聚类性能度量大致有两类.一类是将聚类结果与参考模型进行比较,称为外部指标,常用的有JC,FMI,RI;另一类是直接考察聚类结果,称为内部指标,常用的有DBI,DI.
  • 有序属性距离计算最常用的是闵可夫斯基距离,当p=2时即欧氏距离,当p=1时即曼哈顿距离.
  • 对无序属性可采用VDM(Value Difference Metric),将闵可夫斯基距离和VDM结合即可处理混合属性,当不同属性的重要性不同时可使用加权距离.
  • 我们基于某种形式的距离来定义相似度度量,但是用于相似度度量的距离未必一定要满足距离度量的基本性质,尤其是直递性.在现实任务中有必要通过距离度量学习来基于数据样本确定合适的距离计算式.
  • 原型聚类假设聚类结构能通过一组原型刻画.通常算法先对原型进行初始化,然后对原型进行迭代更新求解.常用的原型聚类算法有k均值算法,学习向量量化,高斯混合聚类.
  • 密度聚类假设聚类结构能通过样本分布的紧密程度确定.通常从样本密度的角度来考察样本之间的可连接性,并基于可连接样本不断扩展聚类簇.常用算法有DBSCAN
  • 层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构.代表算法有AGNES.
一、聚类任务
聚类既能作为一个单独过程，用于找寻数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。

二、性能度量
对聚类结果，我们需通过某种性能度量来评估其好坏；另一方面，若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得副符合要求的聚类结果。

外部指标：将 聚类结果与某个 “ 参考模型 ”（reference model）进行比较。
内部指标：直接考察聚类结果而不利用任何参考模型。
三、距离计算
距离度量函数d i s t ( ⋅ , ⋅ ) dist(\cdot,\cdot)dist(⋅,⋅)的基本性质：

非负性
同一性
对称性
直递性
聚类的核心概念是相似度或距离。

闵可夫斯基距离
d i j = ( ∑ k = 1 m ∣ x k i − x k j ∣ p ) 1 p    这 里 p ≥ 1 d_{ij}=\Big(\sum_{k=1}^m|x_{ki-x_{kj}}|^p\Big)^{\frac1p}\\\;\\这里p\ge1

这里p≥1
当p = 2 p=2p=2时称为欧氏距离
当p = 1 p=1p=1时称为曼哈顿距离
当p = ∞ p=\inftyp=∞时称为切比雪夫距离（取坐标数值差的绝对值的最大值）

马哈拉诺比斯距离
d i j = [ ( x i − x j ) T S − 1 ( x i − x j ) ] 1 2 d_{ij}=[(x_i-x_j)^TS^{-1}(x_i-x_j)]^{\frac12}

其中
样 本 集 合 为 ： X = [ x i j ] m ∗ n , S 为 协 方 差 矩 阵 x i = ( x 1 i , x 2 i , ⋯   , x m i ) T , x j = ( x 1 j , x 2 j , ⋯   , x m j ) T 样本集合为：X=[x_{ij}]_{m*n},S为协方差矩阵\\x_i=(x_{1i},x_{2i},\cdots,x_{mi})^T,x_j=(x_{1j},x_{2j},\cdots,x_{mj})^T

    
 
当样本数据哥哥分量互相独立且各个分量的方差为1时，马氏距离就是欧式距离，所以马氏距离时欧氏距离的推广。

样本系数
r i j = ∑ k = 1 m ( x k i − x ˉ i ) ( x k j − x ˉ j ) [ ∑ k = 1 m ( x k i − x ˉ i ) 2 ∑ k = 1 m ( x k j − x ˉ j ) 2 ] 1 2 r_{ij}=\frac{\sum_{k=1}^m(x_{ki}-\bar x_i)(x_{kj}-\bar x_j)}{\Big[\sum_{k=1}^m(x_{ki}-\bar x_i)^2\sum_{k=1}^m(x_{kj}-\bar x_j)^2\Big]^{\frac12}}

夹角余弦
s i j = ∑ k = 1 m x k i x k j [ ∑ k = 1 m x k i 2 ∑ k = 1 m x k j 2 ] 1 2 s_{ij}=\frac{\sum_{k=1}^mx_{ki}x_{kj}}{\Big[\sum_{k=1}^mx_{ki}^2\sum_{k=1}^mx_{kj}^2\Big]^{\frac12}}

簇或类

类与类之间的距离

最短距离或单连接
最长距离或完全连接
中心距离
平均距离
四、原型聚类
k均值算法
学习向量量化
高斯混合聚类（采用概率模型来表达聚类原型）
五、密度聚类
DBSCAN
六、层次聚类
层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构．数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。


第10章 降维与度量学习

  • 懒惰学习在训练阶段只把样本保存起来,训练时间开销为零,待收到测试样本后再进行处理,如k近邻学习(kNN).急切学习则在训练阶段就对样本进行学习处理.
  • 若任意测试样本x附近任意小的δ距离范围内总能找到一个训练样本,即训练样本的采样密度足够大,或称为密采样,则最近邻分类器(1NN)的泛化错误率不超过贝叶斯最优分类器的错误率的两倍.
  • 在高维情形下出现的数据样本稀疏,距离计算困难等问题称为"维数灾难".处理高维数据的两大主流技术是降维和特征选择.
  • 降维亦称维数约简,即通过某种数学变换将原始高维属性空间转变为一个低维子空间.能进行降维的原因是与学习任务密切相关的或许仅仅是数据样本的某个低维分布,而不是原始高维空间的样本点.
  • 多维缩放是一种经典的降维方法.它使原始空间中样本之间的距离在低维空间中得以保持.
  • 主成分分析(PCA)是最常用的一种降维方法.如果要用一个超平面对所有样本进行恰当的表达,这个超平面应该具有最近重构性和最大可分性两种性质.基于这两种性质可以得到主成分分析的等价推导.PCA可以使样本的采样密度增大,同时在一定程度上起到去噪的效果.
  • 线性降维方法有可能丢失低维结构,因此要引入非线性降维.一种常用方法是基于核技巧对线性降维方法进行核化.如核主成分分析(KPCA).
  • 流形学习(manifold learning)是一类借鉴了拓扑流形概念的降维方法.流形在局部具有欧氏空间性质.将低维流形嵌入到高维空间中,可以容易地在局部建立降维映射关系,再设法将局部映射关系推广到全局.常用的流形学习方法有等度量映射和局部线性嵌入等.
  • 对高维数据进行降维的主要目的是找到一个合适的低维空间.事实上,每个空间对应了在样本属性上定义的一个距离度量,度量学习直接尝试学习出一个合适的距离度量.常用方法有近邻成分分析(NCA).