多示例学习回顾

1、聚类：

刚接触的聚类算法就是K-Means，当时也通过复现了算法代码来理解了原理。在后面的许多论文中，都利用了聚类的思想。聚类的最主要思想为：找到一簇数据中的最具代表性的数据作为代表，并以此来代表某一类别的数据。再通过度量其他数据与这些代表的相似性实现分类。

· K-Means

主要原理见这篇文章，主要是通过这个算法来理解聚类的意义。

· Bamic

该算法是基于包，距离度量方式为豪斯多夫距离。论文阅读见这一篇，代码见这一篇。

这个算法与K-Means有一定关联，因为算法利用K-Medoids算法进行聚类：随机选出K个点作为中心，计算每个簇的平均距离，并通过平均距离找到新的中心，依次迭代，直到中心不再变化为止。

在嵌入方面，Bamic通过计算每个包与k个中心的距离，将包映射为k维的特征向量，每一维都是该包与第k个中心的间距。得到映射向量后，再进行分类处理。

· Density Peak

参考这篇文章，算法的核心思想是：密度比邻居节点高、与比其密度大的点的距离相对大的点是聚类中心。目的是为了找到最具代表性的点 算法中的一些具体细节会在SMDP中提到。

DP算法将密度$\rho$与距离$\delta$组合成为$(\rho ,\delta )$并映射到二维空间中进行决策。

· SMDP

该算法是基于包，距离度量方式为豪斯多夫距离。论文阅读见这一篇，代码在这一篇。 算法以Density Peak为基础，找出数据集中的代表包，并将其利用到多示例学习中。SMDP的算法思想为：通过计算密度选出那些周围包数量多的包作为master，这样的master最具代表性，能够代表周围一圈的包。 然后计算每一个包到它们所属master的距离并映射。最终对映射的向量通过svm等分类器进行分类得到预测结果 。

算法流程图：

由于cutoff kernel得到的是整数，得到的结果是整数，会出现密度相同的情况，而Gaussian kernel很少出现这种情况。因此常选用高斯核为核函数。下面的MIDIE也同样使用了高斯核。

之所以求每个包距其master的距离，就是来度量包与每个代表包的相似度，从而判断这个包的类型。通过距离来侧面体现每个包的特征。

该算法在DP的基础上增加了嵌入，得到每个包的映射向量。最后再对这些向量通过SVM等分类器进行分类。算法利用了聚类的思想，关键就是如何找到最具代表性的包。

· MIDIE

该算法是基于实例 ，距离度量方式为欧氏距离。论文阅读见这一篇，代码见这一篇。算法沿用了SMDP中的聚类思想来找出代表实例 ，且也包含miGraph中的一些方法。

同样，MIDIE通过聚类选出了每个包中最能够代表这个包的实例原型，其中加入了关联性，在miGraph中也有用同样的方式来构建affinity matrix。关联性体现了某个实例与其他实例的关联程度，若某个实例与周围实例的关联性高（距离小于包内实例平均距离），则该实例称为实例原型的几率越大。 MIDIE同时考虑了密度与关联性，从两个角度综合起来选出了一个包中最具代表性的那一个实例原型，构成了实例原型池。

在代表实例选择阶段，则依旧沿用了SMDP中的思想来选出实例原型中的代表实例。这一阶段与SMDP差别不大，同样考虑了每个实例原型的重要性与独立性，都是通过计算密度与距离来计算得分，并选出实例原型。从实例原型池中选出代表实例，更能凸显出代表实例的代表性。

算法流程图：

在映射部分，与SMDP不同，MIDIE是通过差值来体现每个包的特征。若差值较小，则说明该实例与其代表实例差别不大，则为同一类别的可能性越大；反之则越小。

2、嵌入

· Bamic

通过Bamic算法得到k个簇与中心后，通过计算N个包与k个中心的距离，将每个包映射为k维向量，最后再通过预测算法对嵌入后的向量进行处理。

由于每个中心都能够代表一种特征，因此计算每个包与中心的距离就能够体现每个包的所属特征，就能够对该包的向量进行预测。

· SMDP

通过DP聚类得到每个包的master以及它们的距离后，通过计算每个包到$n_c$个中心的距离，映射为$n_c$维特征向量 。最后再通过预测算法对嵌入后向量进行分类处理。

这里的嵌入方式与Bamic类似。

· MIDIE

MIDIE是通过差值来体现每个包的特征。若差值较小，则说明该实例与其代表实例差别不大，则为同一类别的可能性越大；反之则越小。计算每个包中的实例与其对应的实例代表作差值处理，并将每个包中差值处理后的实例叠加，得到这个包的映射向量。

· ELDB

论文阅读在这一篇，代码在这一篇。

算法的映射方式为：计算每个包$B_i$与判别包集合${\mathcal{T}}_e$中之间的平均豪斯多夫距离来度量关联性：
$$f_b({\mathbf{B}}_i,{\mathcal{T}}_e)\mapsto {\mathbf{b}}_i=[b_{i{\zeta }_1},...,b_{i{\zeta }_{\psi }}]$$
其中，$b_{ik}=||\overline{x_i}-\overline{x_k}||$，$\overline{x_i}={\sum }_{j=1}^{n_i}{x}_{ij}/n_i$。

判别包集合就是包集合中最具区分度的包 ，也就是代表包集合，与其他包差别大的包。通过映射，能够得到每个包与代表包之间的差别，映射为向量${\mathbf{b}}_i$。

此外，ELDB拥有判别性分析技术，即使得${\mathcal{T}}_d$中任意两个不同标签的包之间距离累积之和最大；任意两个相同标签的包之间距离累积之和最小：
$$\underset{{\mathcal{T}}_e\subseteq {\mathcal{T}}_d\subset \mathcal{T}}{\max }\mathcal{J}({\mathcal{T}}_d,{\mathcal{T}}_e)=\frac{1}{2}\sum _{B_{{\xi }_i},B_{{\xi }_j}\in {\mathcal{T}}_d}{d}_{ij}{\delta }_{ij}$$
其中，$d_{ij}$为包间距离，${\delta }_{ij}$为bag-link矩阵中对应位置的值。若两个包对应标签相同，则为$\lambda$，否则为$-\lambda$。意味着标签不同的包之间区别越大，这个矩阵也能够凸显包与包之间的区别：
δ i j = { λ i j , y ξ i ≠ y ξ j − λ i j , y ξ i = y ξ j \delta _{ij}=

$$\begin{cases} \lambda _{ij}, y_{\xi _{i}}\ne y_{\xi _{j}}\\ -\lambda _{ij}, y_{\xi _{i}}= y_{\xi _{j}} \end{cases}$$ δij​={λij​,yξi​​=yξj​​−λij​,yξi​​=yξj​​​

· miGraph

论文阅读在这一篇。miGraph提供了一种全新的思路，将包映射为一个affinity matrix：若包内实例间距大于阈值，矩阵对应位置的值置为1，否则为0。这也是MIDIE算法在衡量实例关联性时的做法。

映射部分，miGraph设计了一个Graph Kernel来度量包与包之间的相似性（关联性）。计算每一个包与其他包之间的相似性并映射为向量。该方法依然离不开距离度量，因为核函数中处理了affinity matrix，而affinity matrix中数据是通过距离计算得到的。

3、距离度量

在多示例学习中，常通过距离来衡量相似性，计算包与包、实例与实例、包与实例的距离。但距离函数又不等同于相似度函数。

所以，要度量包间相似度，距离度量是关键一步。距离越近，两个包就越相似。正如疫情期间，那些接触过患者的人往往患病几率就愈大。常通过$d=1-s$、$d=-ln(s)$等来将距离转换为相似度。因为距离$s$越小，相似度$s$就越大，代表越相似。

在机器学习中有许多距离度量方式，这篇文章很好的总结了各自距离度量方法。在目前已经阅读的论文中，最常见的距离公式为Hausdorff Distance与Euclidean Distance 。前者用于度量包间的距离，后者用于度量实例间的距离。在miGraph中使用了Gaussian Distance。

欧式距离计算公式：
$$d(x,y)=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}$$

豪斯多夫距离是基于欧式距离的，用于描述两个集合之间的相似程度，因此也适用于度量多示例学习中包间相似度。又分为：最小Hausdorff距离、平均Hausdorff距离、最大Hausdorff距离。选用哪一种通常是通过做实验后，找出性能最佳的一个作为最终的算法距离度量方式。

由于不同数据集包中的实例分布的不同，需要选择不同的距离度量方式。一般分为：1）数据相关型；2）数据不相关型。

1）数据相关型：指的是计算距离时需要依据其他对象来计算，公式一般为$distance(A,B,媒介)$

2）数据不相关型：指的是直接计算距离而不需要其他对象作为媒介，如豪斯多夫距离，公式一般为$distance(A,B)$

由于距离能够计算包与包的特征值之间的关系，而包的特征值往往能够代表这个包的类别、性质。对于不同的数据分布。这一切都与数据分布有关。可以通过对不同的算法试验不同的距离度量方式，找出最适合算法的距离。