图像聚类方法整理-前置过程

本文最后更新于745 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com

用于图像的聚类方法整理-前置过程

聚类（Clustering）：指按照某个特定的标准把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，不在同一个簇中的数据对象的差异性也尽可能地大；聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。

完整的聚类过程：

数据准备：特征标准化、降维
特征选择：从最初的特征中选择最有效的特征，并将其存储在向量中
特征提取：通过对选择的特征进行转换形成新的突出特征
聚类：基于某种距离函数进行相似度度量，获取簇
聚类结果评估：分析聚类结果，如距离误差和SSE等

1. 数据准备

1.1 特征标准化

特征标准化是特征工程中的一部分，顾名思义，就是指对原始数据进行一系列工程处理，将其进行提炼。本质上来讲，特征工程是一个数据表示和展现的过程。实际使用中，特征工程旨在剔除原始数据中的冗余和杂质，进而提炼出更具表征力的特征。

常用的几种标准化方法：

线性函数归一化（Min-Max Scaling）

对原始特征进行线性变换，将结果映射到 $[0,1]$ 的范围上，从而实现对原始特征的等比例缩放。公式如下：

该方法不足之处在于，当有新数据引入时，所有特征值都需要重新定义。

零均值标准化（Z-Score Normalization）

一种基于原始特征的均值和标准差进行标准化的方法，它会将特征映射到均值为0，偏差为1的分布上。具体来说，假设特征的均值为 $\mu$ ，标准差为 $\sigma$ ，那么归一化的公式为;

在使用梯度下降的方法求解最优化问题时，标准化/归一化可以加快梯度下降的求解速度，提升模型收敛速度。

$L_1/L_2$ 范数标准化

如果只是为了统一量纲，那么通过 $L_2$ 范数整体标准化也是可以的，具体方法是求出每个样本特征向量 $x$ 的 $L_2$ 范数 $||x||^2$ ，然后用 $x/||x||^2$ 代替原本特征即可。当然 $L_1$ 范数标准化也是可以的，即用 $x/||x||^1$ 代替原本特征。

中心化

主要是在PCA降维中，此时我们求出特征 $x$ 的平均值 $mean$ 后，用 $x-mean$ 代替原特征，也就是特征的均值变成了0，但是方差并不改变。

其它

在实际案件中可以根据输入数据的情况，形式，一些先验特征来选择特征归一化的方式。其实特征归一化本质上也就是一种映射方式。特征标准化也就是一个预处理的方式，可以对案件最后的输出数据产生有益效果才是根本目的。比如通过 $Sigmoid$ 函数进行归一化映射，只保留注意区域。或是通过 $tanh$ 或是 $log$ 进行映射，都是可取的方法。

1.2 特征降维

在实际应用中，当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差。

对于高维数据，维度灾难使解决模式识别问题非常困难，此时往往要求首先降低特征向量的维度。

降低特征向量维度的可行性分析：

特征向量往往是包含冗余信息的
有些特征可能与分类问题无关
特征之间存在着很强的相关性

降低维度的方法：

特征组合：讲几个特征组合在一起，形成新的特征
特征选择：选择现有的特征集的一个子集

针对不同目标有不同的训练算法：

最小化重构误差（主成分分析，PCA）
最大化类别可分性（线性判别分析，LDA）
最小化分类误差（判别训练，discriminative training）
保留最多细节的投影（投影寻踪，projection pursuit）
最大限度地使各特征之间独立（独立成分分析，ICA）

2. 特征选择

特征选择是特征工程中的重要问题，其目标是寻找最优特征子集。特征选择能剔除不相关或冗余的特征，从而达到减少特征个数，提高模型精确度，减少运行时间的目的

一般流程：

生成子集：搜索特征子集，为评价函数提供特征子集
评价函数：评价特征子集的好坏
停止准则：与评价函数相关，一般是阈值，评价函数达到一定标准后就可停止搜索
验证过程：在验证数据集上验证选出来的特征子集的有效性

三大类方法：

过滤法（Filter）：按照发散性或相关性对各个特征进行评分，设定阈值或者待选择特征的个数进行筛选
包装法（Wrapper）：根据目标函数（预测效果评分）,每次选择若干特征，或者排除若干特征
嵌入法（Embedded）：先使用某些机器学习的模型进行训练，得到各个特征的权值系数，根据系数从大到小选择特征（类似于Filter不过需要通过训练获取系数）

2.1 过滤法

过滤法的基本思想是：分别对每个特征 $x_i$ ，计算 $x_i$ 相对于类别标签 $y$ 的信息量 $S(i)$ ，得到 $n$ 个结果。然后将 $n$ 个 $S(i)$ 按照从大到小排序，输出前 $k$ 个特征。显然，这样复杂度大大降低。那么关键的问题就是使用什么样的方法来度量 $S(i)$ ，我们的目标是选取与 $y$ 关联最密切的一些特征 $x_i$ 。

Pearson相关系数

皮尔森相关系数是一种最简单的，能帮助理解特征和响应变量之间关系的方法，衡量的是变量之间的线性相关性，结果的取值区间为 $[-1,1]$ ， $-1$ 表示完全的负相关(这个变量下降，那个就会上升)， $+1$ 表示完全的正相关， $0$ 表示没有线性相关性。Pearson Correlation速度快、易于计算，经常在拿到数据(经过清洗和特征提取之后的)之后第一时间就执行。

Pearson相关系数的一个明显缺陷是，作为特征排序机制，他只对线性关系敏感。如果关系是非线性的，即便两个变量具有一一对应的关系，Pearson相关性也可能会接近 0 。

卡方验证

经典的卡方检验是检验类别型变量对类别型变量的相关性。假设自变量有 $N$ 种取值，因变量有 $M$ 种取值，考虑自变量等于 $i$ 且因变量等于 $j$ 的样本频数的观察值与期望的差距，构建统计量：

不难发现，这个统计量的含义简而言之就是自变量对因变量的相关性。

互信息和最大信息系数

经典的互信息也是评价类别型变量对类别型变量的相关性的，互信息公式如下：

想把互信息直接用于特征选择其实不是太方便：

它不属于度量方式，也没有办法归一化，在不同数据及上的结果无法做比较
对于连续变量的计算不是很方便（ $X$ 和 $Y$ 都是集合， $x_i$ ， $y$ 都是离散的取值），通常变量需要先离散化，而互信息的结果对离散化的方式很敏感

最大信息系数克服了这两个问题。它首先寻找一种最优的离散化方式，然后把互信息取值转换成一种度量方式，取值区间在 [0,1] 。

距离相关系数

距离相关系数是为了克服Pearson相关系数的弱点而生的。在 $x$ 和 $x^2$ 这个例子中，即便Pearson相关系数是 0 ，我们也不能断定这两个变量是独立的（有可能是非线性相关）；但如果距离相关系数是 0 ，那么我们就可以说这两个变量是独立的。

尽管有MIC和距离相关系数在了，但当变量之间的关系接近线性相关的时候，Pearson相关系数仍然是不可替代的。

第一、Pearson相关系数计算速度快，这在处理大规模数据的时候很重要。

第二、Pearson相关系数的取值区间是[-1，1]，而MIC和距离相关系数都是[0，1]。这个特点使得Pearson相关系数能够表征更丰富的关系，符号表示关系的正负，绝对值能够表示强度。当然，Pearson相关性有效的前提是两个变量的变化关系是单调的。

方差选择法

过滤特征选择法还有一种方法不需要度量特征 $x_i$ 和类别标签 $y$ 的信息量。这种方法先要计算各个特征的方差，然后根据阈值，选择方差大于阈值的特征。

例如，假设我们有一个具有布尔特征的数据集，并且我们要删除超过80％的样本中的一个或零（开或关）的所有特征。布尔特征是伯努利随机变量，这些变量的方差由下式给出:

2.2 包装法

基本思想：基于hold-out方法，对于每一个待选的特征子集，都在训练集上训练一遍模型，然后在测试集上根据误差大小选择出特征子集。需要先选定特定算法，通常选用普遍效果较好的算法，例如Random Forest，SVM，KNN等等。

2.3 嵌入法

基于惩罚项的特征选择法，通过 $L_1$ 正则项来选择特征： $L_1$ 正则方法具有稀疏解的特征，因此天然具备特征选择的特性。
基于学习模型的特征排序，这种方法的思路是直接使用要用的机器学习算法，针对每个单独的特征征和响应变量建立预测模型。假如某个特征和响应变量之间的关系是非线性的，可以用基于树的方法（决策树、随机森林）、或者扩展的线性模型等。基于树的方法比较易于使用，因为他们对非线性关系的建模比较好，并且不需要太多的调试。但要注意过拟合问题，因此树的深度最好不要太大，再就是运用交叉验证。通过这种训练对特征进行打分获得相关性后再训练最终模型。

3. 特征提取

通过对选择的特征进行转换形成新的突出特征

在图像处理中，可以将特征分为

初级特征：

灰度值
梯度值（ $x$ 方向， $y$ 方向，幅值）
像素位置
梯度方向

局部特征：

描述一块区域，使其具有高可区分度。局部特征应有特点：可重复性，可区分性，准确性，有效性，鲁棒性。

SIFT特征描述子（尺度不变特征变换）
HOG特征
SURF特征描述子
ORB特征描述子
LBP特征描述子
HAAR

上述所有特征都是已有的一些特征提取手段，各自有其自身的特性。但是实际情况是多变的，需要考虑的方面有很多，适用程度不同，所以也就需要通过上述特征标准化、降维，特征选择以及这一步特征提取获取实际问题中需要的特征。这一步骤中每一个特征都可以进行展开，在这些特征的基础上进行改进。而在改进的过程中还会有若干个问题有待解决。

在使用这些特征的时候一定要想好这个特征代表了什么，这些特征相近的集合（簇类）能够代表什么。一切使用都要在有逻辑支撑的条件下。

4. 聚类

聚类是一种目的，将一组数据通过无监督的方式聚成若干簇类。获取簇类有很多种方法，不过无论通过哪种聚类方法都离不开数据的相似度度量。

4.1 数据相似度度量方法

4.1.1 $L_p$ 范数/闵可夫斯基（Minkowski）距离

其中在 $p=1,2,\infty$ 时，分别对应了曼哈顿距离，欧几里得距离与切比雪夫距离。

这几个距离的缺点：

没有考虑各个特征之间的量纲，不过在特征标准化时就可以解决此问题
没有考虑各个特征分布的期望和方差等统计量

4.1.2 杰卡德相似系数（Jaccard）

杰卡德相似系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量具体差异值的大小，只能获得是否相同这个结果。

4.1.3 余弦相似度（cosine sililarity）

余弦相似度用向量空间中两向量夹角的余弦值作为衡量两个个体之间差异的大小。余弦值越接近1表示两个向量越相似。

余弦相似度相比于距离度量，其更加注重两个向量在方向上的差异，而非距离或者长度差异。

4.1.4 皮尔逊相关系数（Pearson Correlation Coefficient）

皮尔逊相关系数（Pearson Correlation）是衡量向量相似度的一种方式。输出范围为-1到+1，其中0代表无相关性，负值代表负相关，正值代表正相关。皮尔逊相关系数在欧几里德距离上做出了优化，对向量的值做了中心化处理，即对两个向量中的所有维度都减去元素的平均值，中心化后所有维度的平均值基本为0；然后对中心化结果求余弦距离，但余弦距离的计算要求每个向量中所有的值都必须非空，若两个向量v1=(3,2,4)、v2=(-1,2,null)，则无法进行余弦距离计算的。皮尔逊相关系数把向量中所有null维度赋值为0，再对结果进行余弦计算。

两个向量X、Y，计算出的皮尔逊相关系数含义做如下理解：

当相关系数为0时，X和Y两向量不相关
当X的值增大（减小），Y值减小（增大），X和Y两向量负相关，相关系数在-1.0到0.0之间。
当X的值增大（减小），Y值增大（减小），X和Y两向量正相关，相关系数在0.0到+1.0之间。

通常通过以下取值范围判断向量的相关程度：

0.8-1.0 极度相关
0.6-0.8 强相关
0.4-0.6 中等程度相关
0.2-0.4 弱相关
0.0-0.2 极弱相关或无相关

4.1.5 相对熵（K-L距离）

4.1.6 Hellinger距离

4.2 簇间距离度量

在数据相似度度量确定之后对于聚类来说还需要确定一种簇间距离度量方式，以下是现有的一些度量方式。（ $C_i,C_j$ 为两个簇）

Single-link：两个簇间的距离为两个簇间距离最近的两个点之间的距离，会在聚类过程中产生链式效应，可能会出现非常大的Cluster。

Complete-link：两个簇间的距离为两个簇间距离最远的两个点之间的距离，可以避免链式效应，对异常样本点非常敏感，容易产生不合理的Cluster。

UPGMA：Single-link与Complete-link的折中，两个簇间的距离为两个簇间所有点距离的均值

WPGMA ：两个簇间的距离的加权平均值，加权是为了使两个簇对距离的计算的影响在同一层次上，而不受簇大小的影像，具体公式和采用的权重方案有关。