3、距离度量
1、聚类：
刚接触的聚类算法就是K-Means，当时也通过复现了算法代码来理解了原理。在后面的许多论文中，都利用了聚类的思想。聚类的最主要思想为：找到一簇数据中的最具代表性的数据作为代表，并以此来代表某一类别的数据。再通过度量其他数据与这些代表的相似性实现分类。
· K-Means
主要原理见这篇文章，主要是通过这个算法来理解聚类的意义。
· Bamic
该算法是基于包，距离度量方式为豪斯多夫距离。论文阅读见这一篇，代码见这一篇。
这个算法与K-Means有一定关联，因为算法利用K-算法进行聚类：随机选出K个点作为中心，计算每个簇的平均距离，并通过平均距离找到新的中心，依次迭代，直到中心不再变化为止。
在嵌入方面，Bamic通过计算每个包与k个中心的距离，将包映射为k维的特征向量，每一维都是该包与第k个中心的间距。得到映射向量后，再进行分类处理。
· Peak
参考这篇文章，算法的核心思想是：密度比邻居节点高、与比其密度大的点的距离相对大的点是聚类中心。目的是为了找到最具代表性的点 算法中的一些具体细节会在SMDP中提到。
DP算法将密度 ρ \rho ρ与距离 δ \delta δ组合成为 ( ρ , δ ) (\rho, \delta) (ρ,δ)并映射到二维空间中进行决策。
· SMDP
该算法是基于包，距离度量方式为豪斯多夫距离。论文阅读见这一篇，代码在这一篇。 算法以 Peak为基础，找出数据集中的代表包，并将其利用到多示例学习中。SMDP的算法思想为：通过计算密度选出那些周围包数量多的包作为，这样的最具代表性，能够代表周围一圈的包。 然后计算每一个包到它们所属的距离并映射。最终对映射的向量通过svm等分类器进行分类得到预测结果 。
算法流程图：
由于 得到的是整数，得到的结果是整数，会出现密度相同的情况，而 很少出现这种情况。因此常选用高斯核为核函数。下面的MIDIE也同样使用了高斯核。
之所以求每个包距其的距离，就是来度量包与每个代表包的相似度，从而判断这个包的类型。通过距离来侧面体现每个包的特征。
该算法在DP的基础上增加了嵌入，得到每个包的映射向量。最后再对这些向量通过SVM等分类器进行分类。算法利用了聚类的思想，关键就是如何找到最具代表性的包。
· MIDIE
该算法是基于实例 ，距离度量方式为欧氏距离。论文阅读见这一篇，代码见这一篇。算法沿用了SMDP中的聚类思想来找出代表实例 ，且也包含中的一些方法。
同样，MIDIE通过聚类选出了每个包中最能够代表这个包的实例原型，其中加入了关联性，在中也有用同样的方式来构建 。关联性体现了某个实例与其他实例的关联程度，若某个实例与周围实例的关联性高（距离小于包内实例平均距离），则该实例称为实例原型的几率越大。 MIDIE同时考虑了密度与关联性，从两个角度综合起来选出了一个包中最具代表性的那一个实例原型，构成了实例原型池。
在代表实例选择阶段，则依旧沿用了SMDP中的思想来选出实例原型中的代表实例。这一阶段与SMDP差别不大，同样考虑了每个实例原型的重要性与独立性，都是通过计算密度与距离来计算得分，并选出实例原型。从实例原型池中选出代表实例，更能凸显出代表实例的代表性。
算法流程图：
在映射部分，与SMDP不同，MIDIE是通过差值来体现每个包的特征。若差值较小，则说明该实例与其代表实例差别不大，则为同一类别的可能性越大；反之则越小。
2、嵌入 · Bamic
通过Bamic算法得到k个簇与中心后，通过计算N个包与k个中心的距离，将每个包映射为k维向量，最后再通过预测算法对嵌入后的向量进行处理。
由于每个中心都能够代表一种特征，因此计算每个包与中心的距离就能够体现每个包的所属特征，就能够对该包的向量进行预测。
· SMDP
通过DP聚类得到每个包的以及它们的距离后，通过计算每个包到 n c n_{c} nc个中心的距离，映射为 n c n_{c} nc维特征向量 。最后再通过预测算法对嵌入后向量进行分类处理。
这里的嵌入方式与Bamic类似。
· MIDIE
MIDIE是通过差值来体现每个包的特征。若差值较小，则说明该实例与其代表实例差别不大，则为同一类别的可能性越大；反之则越小。计算每个包中的实例与其对应的实例代表作差值处理，并将每个包中差值处理后的实例叠加，得到这个包的映射向量。
· ELDB
论文阅读在这一篇，代码在这一篇。
算法的映射方式为：计算每个包 B i B_{i} Bi与判别包集合 T e \{T}_{e} Te中之间的平均豪斯多夫距离来度量关联性：
f b ( B i , T e ) ↦ b i = [ b i ζ 1 , . . . , b i ζ ψ ] f_{b}(\ B_{i},\{T}_{e})\ \ b_{i}=[b_{i\zeta_{1}},...,b_{i\zeta_{\psi }}] fb(Bi,Te)↦bi=[biζ1,...,biζψ]
其中， b i k = ∣ ∣ x i ˉ − x k ˉ ∣ ∣ b_{ik}=||\bar{\{\{x}}_{i} }-\bar{\{\{x} }_{k}} || bik=∣∣xiˉ−xkˉ∣∣， x i ˉ = ∑ j = 1 n i x i j / n i \bar{x_{i}}=\sum_{j=1}^{n_{i}}x_{ij}/n_{i} xiˉ=∑j=1nixij/ni。
判别包集合就是包集合中最具区分度的包 ，也就是代表包集合，与其他包差别大的包。通过映射，能够得到每个包与代表包之间的差别，映射为向量 b i \ b_{i} bi。
此外，ELDB拥有判别性分析技术，即使得 T d \{T}_{d} Td中任意两个不同标签的包之间距离累积之和最大；任意两个相同标签的包之间距离累积之和最小：
max T e ⊆ T d ⊂ T J ( T d , T e ) = 1 2 ∑ B ξ i , B ξ j ∈ T d d i j δ i j \max_{\{T} _{e}\ \{T} _{d}\ \{T}}\{J}(\{T}_{d},\{T}_{e})=\frac{1}{2} \sum_{B_{\xi _{i}},B_{\xi _{j}}∈\{T}_{d}}^{} d_{ij}\delta _{ij} Te⊆Td⊂TmaxJ(Td,Te)=21Bξi,Bξj∈Td∑dijδij
其中， d i j d_{ij} dij为包间距离， δ i j \delta _{ij} δij为bag-link矩阵中对应位置的值。若两个包对应标签相同，则为 λ \ λ，否则为 − λ -\ −λ。意味着标签不同的包之间区别越大，这个矩阵也能够凸显包与包之间的区别：
δ i j = { λ i j , y ξ i ≠ y ξ j − λ i j , y ξ i = y ξ j \delta _{ij}=\begin{cases} \ _{ij}, y_{\xi _{i}}\ne y_{\xi _{j}}\\ -\ _{ij}, y_{\xi _{i}}= y_{\xi _{j}} \end{cases} δij={λij,yξi=yξj−λij,yξi=yξj
·
论文阅读在这一篇。提供了一种全新的思路，将包映射为一个 ：若包内实例间距大于阈值，矩阵对应位置的值置为1，否则为0。这也是MIDIE算法在衡量实例关联性时的做法。
映射部分，设计了一个Graph 来度量包与包之间的相似性（关联性）。计算每一个包与其他包之间的相似性并映射为向量。该方法依然离不开距离度量，因为核函数中处理了 ，而 中数据是通过距离计算得到的。
3、距离度量
在多示例学习中，常通过距离来衡量相似性，计算包与包、实例与实例、包与实例的距离。但距离函数又不等同于相似度函数。
所以，要度量包间相似度，距离度量是关键一步。距离越近，两个包就越相似。正如疫情期间，那些接触过患者的人往往患病几率就愈大。常通过 d = 1 − s d=1-s d=1−s、 d = − l n ( s ) d=-ln(s) d=−ln(s)等来将距离转换为相似度。因为距离 s s s越小，相似度 s s s就越大，代表越相似。
在机器学习中有许多距离度量方式，这篇文章很好的总结了各自距离度量方法。在目前已经阅读的论文中，最常见的距离公式为 与 。前者用于度量包间的距离，后者用于度量实例间的距离。在中使用了 。
算法Graph
度量方式
豪斯多夫
欧氏
豪斯多夫
豪斯多夫
高斯
欧式距离计算公式：
d ( x , y ) = ∑ i = 1 n ( x i − y i ) 2 d(x,y)=\sqrt{\sum_{i=1}^{n}(x_{i}-y_{i})^{2}} d(x,y)=i=1∑n(xi−yi)2
豪斯多夫距离是基于欧式距离的，用于描述两个集合之间的相似程度，因此也适用于度量多示例学习中包间相似度。又分为：最小距离、平均距离、最大距离。选用哪一种通常是通过做实验后，找出性能最佳的一个作为最终的算法距离度量方式。
由于不同数据集包中的实例分布的不同，需要选择不同的距离度量方式。一般分为：1）数据相关型；2）数据不相关型。
1）数据相关型：指的是计算距离时需要依据其他对象来计算，公式一般为 d i s t a n c e ( A , B , 媒介 ) (A,B,媒介) (A,B,媒介)
2）数据不相关型：指的是直接计算距离而不需要其他对象作为媒介，如豪斯多夫距离，公式一般为 d i s t a n c e ( A , B ) (A, B) (A,B)
由于距离能够计算包与包的特征值之间的关系，而包的特征值往往能够代表这个包的类别、性质。对于不同的数据分布。这一切都与数据分布有关。可以通过对不同的算法试验不同的距离度量方式，找出最适合算法的距离。
