聚类总结
聚类分析的思路：
- 相似性衡量
相似性衡量又可以细分为直接法和间接法:直接法是直接求取input data的相似性,间接法是求取data中提取出的feature的相似性.但无论是求data还是feature的相似性,方法都是这么几种:
- 距离.距离主要指Minkovski距离，Manhattan距离,欧氏距离,这些试试上都是和Lp norm相关的计算
- 相似系数:主要有夹角余弦和相关系数.相关系数的应用也非常广泛,其主要优势是它不受原线性变换的影响,而且可以轻松地转换为距离,但其运算速度要比距离法慢得多,当维数很高的时候.
- 核函数K(x,y).定义在$R^d×R^d$上的二元函数,本质上是反映x和y的距离.核函数的功能就是把数据从低维空间投影到高维空间
- DTW(dynamic time warping):之所以把DTW单独拿出来,是因为它是一种非常特殊的距离算法,他可以计算两个不同长度的向量的距离,也可以对两对向量中不同时间段内的数据做匹配.
- 聚类算法
Hierarchical methods:该主要有两种路径:agglomerative和divisive,也可以理解为自下而上法(bottom-up)和自上而下(top-down).自下而上法就是一开始每个个体都是一个类,然后根据linkage寻找同类,最后形成一个类。自上而下就是反过来,一开始所有个体都属于一个“类”,然后根据linkage排除异己,最后每个个体都成为一个类.至于根据linkage判断类的方法就是最短距离法、最长距离法、中间距离法、类平均法等等(其中类平均法往往被认为是最常用也是最好的方法,一方面因为其良好的单调性,另一方面因为其空间扩张/浓缩的程度适中).
Partition-based methods:其原理简单来说就是,想象你有一堆散点需要距离,想要的聚类效果就是“类内的点都足够近，类间的点都足够远.”首先你要确定这堆点最后聚成几类,然后挑选几个点作为初始中心点,再然后依据预先定好的启发式算法给数据点做迭代重置,直到最后达到”类内的点都足够近,类间的点都足够远”的目标效果.
Density-based method:该方法同时也对噪声数据的处理比较好。其原理简单说画圈儿,其中要定义两个参数;一个是圈儿的最大半径,一个是一个圈儿最少应容纳几个点.最后再一个圈里的,就是一个类.DBSCAN就是其中的典型
- Grid-based methods:这类方法的院级就是把数据空间划分为网格单元,将数据对象集映射到网格单元,并计算每个单元的密度.根据预设的阈值判断每个网格单元是否为高密度单元,由近邻的稠密单元组成”类”。该方法的优点是执行效率高,因为其速度与数据对象的个数无关,而只依赖于数据空间中每个维上单元的个数.但缺点也是不少,比如对参数敏感、无法处理不规则分布的数据、维数灾难等.
- Model-based methods:这一类方法主要是指基于概率模型的方法和基于神经网络模型的方法,尤其以基于概率模型的方法居多.这里的概率模型主要指概率生成模型(generative Model),同一”类”的数据术语同一种概率分布.这种方法的优点就是对”类”的划分不那么”坚强”，而是以概率形式表现,每一类的特征也可以用参数来表达;但缺点就是执行效率不高;特别是分布数量很多并且数据量很少的时候.其中最典型、也最常用的方法就是高斯混合模型(GMM).基于神经网络的方法主要就是指SOM(self Organized Maps)了,也就是我们所知的唯一一个非监督学习的神经网络.
- 数据简化(data reduction),这个环节optional.其实第二部分提到的有些算法就是对数据做了简化,才得以具备处理大规模数据的能力,比如BIRCH.但其实你可以任意组合,所以理论上把数据简化的方法和上面提到的几种聚类方法结合使用.
- 变换(Data Transformation)：离散傅里叶变换可以提取数据的频域(freaquency domain)信息,离散小波变换除了频域之外,还可以提取到时域信息。
- 降维(Dimensionality Reduction):如PCA,SVD,MDS(Multi-Dimensional Scaling)什么的.这些常常都是线性的降维方法.而非线性降维方法主要是流形学习。流形学习主要的方法包括:ISOMAP、LLE、kernel PCA等。
聚类结果评价
聚类往往不像分类一样有一个最优化目标和学习过程，而是一个统计方法，将相似的数据和不相似的数据分开。就我个人理解，在数据质量高的情况下，一个好的聚类结果表明了数据中相对稳定的某种“模式 or 分布”，这个模式不会因为个别数据点的增删改而改变，且能够将数据尽可能分开。
关于无监督聚类的评价指标，在完全没有ground-truth的情况下，我了解到的方法有以下几个：
聚类质量:
因为没有标签,所以一般通过评估类的分类情况来决定聚类质量。类内越紧密,类间距离越小,质量越高.交叉验证
这个验证主要是针对kmeans等划分聚类方法.参见《数据挖掘:概念与计数》中的10.6.2,原文如下:
首先，把给定的数据集D划分成m个部分。然后，使用m-1各部分建立一个聚类模型，并使用剩下的一部分检验聚类的质量。例如，对于检验集中的每个点，我们可以找出最近的形心。因此，我们可以使用检验集中的所有点与他们的最近形心之间的距离的平方和来度量聚类模型拟合检验集的程度。对于任意整数k>0，我们依次使用每一部分作为检验集，重复以上过程m次，导出k个簇的聚类。取质量度量的平均值作为总体质量度量。聚类稳定性
参见论文《clustering stability: an overview》。使用稳定评估的前提是我们所要聚类的数据出自同一个underlying model或者data generating process.论文中给出的例子比较明白:
在这个例子中,数据点是红色方块儿,underlying model(也就是这些点本应该属于的类)是4个圆圈.如果我们让聚类算法k=2,那可能给sample1用水平虚线分,给sample2用竖线分,两次对”相同”数据的聚类完全不同,那就是不稳定的.如果k=5,聚类结果可能出现上图所示,可以看到下面两个圆圈被聚类的结果不变.因此k=5比k=2要稳定.
也就是说，聚类结果的稳定性越高，引入新的（来自相同underlying model）后再次聚类结果越不容易被改变。
关于稳定性如何计算有很多种方法，文章中总结的大致思想如下：
输入:给定聚类数目的聚类算法A,原始数据集S
- 根据原始数据集S产生n个不同的数据集S1,S2,…,Sn(取样或者加噪声等方法)
- 对于b=1,2,…n,对数据集Sb用算法A聚类,得到聚类结果Cb
- 对于b=1,2,…n,计算不同聚类结果之间的距离$d(C_b,C_{b’})$
- 计算不稳定性(instability):$Instab=\frac{1}{n^2}\sum_{b,b’=1}^nd(C_b,C_{b’})$