【度量学习】Examples-一一网

下面是度量学习的样例：

使用 Shogun Machine Learning Toolbox 进行度量学习

原文链接：Metric Learning with the Shogun Machine Learning Toolbox

本节介绍使用 Shogun Machine Learning Toolbox 来实现度量学习的分类和特征选择，将使用 Large Margin Nearest Neighbour（LMNN）算法。

理解 LMNN

首先，通过一个简单的例子来介绍 LMNN，使用下面的二维数据集（包含8个特征向量，其中每个特征向量属于三个不同类中的一个，由0、1或2标识）：

先将数据可视化：

上面的图中不同颜色的点代表一个类，可以看到两类的点间距离很接近，而第三个类的点在y轴上距离接近，在x轴上距离很远。

如果在这种数据集上使用KNN，可以预期到使用标准欧式距离会出现很大的分类错误（因为绿色的点距离很远），如下图所示。

一种改进的方法是手动给KNN输入一种距离度量，给予y方向更大的权重，但是如果能够从数据中自动学习到这种距离，那就更好了。因此LMNN就是基于这一种原则：给定若干个近邻 $k$ ，在训练数据集中找到最大化KNN准确率的马氏距离度量（基于 $k$ 的值）。

现在使用Shogun实现的LMNN类来查找距离并绘制其相关的椭圆，如果绘制准确，将看到椭圆只与绿色类的数据点重叠。

首先，需要将数据转换成Shogun的特征和标签对象：

然后进行LMNN训练：

最后，检索 LMNN 在训练过程中学习的距离度量，并将其与数据一起可视化：

超越主旨

LMNN是所谓的线性度量学习方法之一，这意味着我们可以通过两种不同的方式来理解 LMNN 的输出：一是作为一种距离度量；二是作为输入数据的线性映射。和其他线性映射一样，LMNN 的输出可以写成一个矩阵 $L$ 。

换句话说，若输入数据可以表示为矩阵 $X$ ，LMNN可以被理解为：通过 $X’=LX$ 实现的数据转换。约束每一列是一个特征向量，因此 $X$ 的行数等于数据的输入维度，列数等于特征向量数。

距离度量可以被认为是一个矩阵 $M$ ，表示两个向量 $\vec{x}_i,\vec{x}_j$ 间的距离，等同于： $d(\vec{x}_i,\vec{x}_j)=(\vec{x}_i-\vec{x}_j)^T M(\vec{x}_i-\vec{x}_j)$ ，一般而言，这类矩阵称为马氏矩阵（Mahalanobis matrices）。在LMNN中，矩阵 $M$ 恰好是线性转换 $L$ 的平方，即 $M=L^TL$ 。这么做是保证 $M$ 是半正定矩阵（PSD），从而定义一个有效度量为什么马氏矩阵要设置为半正定矩阵

下面使用线性转换解释来可视化LMNN，下面的图中使用 $L$ 转换原始数据并将转换前后的数据一起展示：

上图中透明的点表示原始数据，实心点为LMNN转换后数据，其中的圆是之前的欧式距离。需要注意一点：如果将LMNN作为线性映射，那在投影空间中用作度量的距离就应该是欧式距离度量，同时应用映射和学习到的马氏距离是错误的做法。

邻居图

使用邻居图的方法可以可视化LMNN和kNN结合找到的距离，其思想是在欧式空间中构造一个图，数据集中的样本点为图中节点，从一点到另一个点的有向边表示目的节点是原节点的1-最近邻。

接下来定义一个数据集，这个数据集中欧式距离表现相当糟糕，这个数据集的数据在y方向上有多个层次，每个层次由沿x方向分布的同一类点组成，如下图所示：

在下面的代码块中，创建一个 kNN 分类器的实例，使用欧式距离分类器计算最近邻。然后使用 LMNN 计算的距离， LMNN 给出的线性映射空间结果中的数据集也显示了出来。

可以看到LMNN在这类数据集中表现更好，右侧的图显示了转换空间中各点的位置从这些点可以清楚地看到中间图中的邻里关系。

真实数据集

在Metagenomics中做特征选择

Metagenomics是研究微生物 DNA 的一个现代领域，节选择的数据集包含三种不同类型的类人猿的信息，特别是大猩猩、黑猩猩和倭黑猩猩（gorillas, chimpanzees, bonobos）。

首先，装载猿类数据，数据集包含了来自猿类肠道细菌的特征：

检查一下样本总数和特征总数：

可以看到有1472个特征，特征向量的维度高达1472，显然无法在输入特征空间中可视化。为了实现可视化，应用降维方法，将特征向量嵌入到二维空间中。此处使用t-distributed neighour embedding（或者叫 t-dsne）方法。

在上图中，绿点代表黑猩猩，红点代表倭黑猩猩，蓝点代表大猩猩。根据图中的结果，我们可以迅速得出结论，这三类猿在数据集中很容易区分，因为它们在两个维度上差不多是完全分开的。注意 t-dsne 在嵌入过程中包含随机性，因此在前一个代码块中的实验结果在不同的执行过程后会有所不同。

上面的 kNN 误差在运行中可能有很大的不同(已经观察到几次近20%的变化)，为了得到 kNN 在该数据集上比较稳定的结果，将使用Shogun的评估框架执行交叉验证。

可以 KNN在这个数据集已经执行得很好了，测试分类的平均误差小于2% 。LMNN可能不会有更大的提升，但是LMNN 在这样的数据集中仍然是非常有用的。

对传统的LMNN算法做一点小小的改进，通过LMNN的对角性强调其线性转换。这意味着LMNN可以用来给每个特征赋权，在训练开始后根据特征权重选择哪些特征更适用于kNN，哪些不适用，这是一种特征选择方法。使用Shogun在LMNN中切换到这种对角模式是很简单的，只需要调用set_diagonal(use_diagonal)方法，将其设为True。

因此，根据结果转换，300个首要特征中只有65个是重要的！即使所有的特征在训练开始时都以一个值作为权重，其余的特征也会被赋予一个精确等于零的权重。事实上，如果使用所有的1472个特征，只有158个特征会得到一个非零的权重。

观察一下迭代次数的影响：

在大约前三百次迭代中，目标没有太多的变化。换句话说，目标曲线是非常平坦的。如果，使用的终止标准要求不够，训练可能会停止在这一点上。这将导致错误的结果，因为训练在这个时刻还没有明确收敛。

为避免这种情况发生，在Shoun中LMNN对训练过程的自动终止提出了严格的标准，通过设置步长阈值和设置目标阈值：set_stepsize_threshold, set_obj_threshold。这些方法可以用来修改步长的下限和目标的增量(相对于其绝对值) ，分别停止训练，此外还可以使用 set_maxiter设置迭代次数的硬上限。如果内部终止标准在达到最大迭代次数之前没有触发，将收到一条警告消息，类似于上面所示的消息。