多示例学习距离度量 (distance measures)和集合核 (set-kernel)_集合的核

引入

  汇总一些用到的距离函数或者核函数函数。距离函数中，Hausdorff距离为把包视作点集，另外的距离函数考虑了包的概率分布。
  本文的符号表示如下：

1 相似度函数、距离函数与核函数

  首先需要弄清楚相似度函数$s$与距离函数$d$的区别：简单来说，两个包越相近，距离越近，相似度越高。根据 ¹，两者可以有以下转换关系：

• $d=1-s$
• $d=\frac{1-s}{s}$
• $d=-\ln (s)$
• $d=\arccos (s)$

  基于相似度函数的函数称为核函数$k$，核函数与距离函数的可以有以下的转换关系 ：

$$d(A,B)=\sqrt{k(A,A)-2k(A,B)+k(B,B)}.$$

2 距离函数

2.1 Hausdorff距离

2.1.1 最大Hausdorff距离²

  公式如下：

d m a x ( A , B ) = max ⁡ { h ( A , B ) , h ( B , A ) } . d^{\rm max} (A, B) = \max \{ h (A, B), h (B, A) \}. dmax(A,B)=max{h(A,B),h(B,A)}.其中
$$h(A,B)=\underset{\mathbf{a}\in A}{\max }\underset{\mathbf{b}\in B}{\min }d(\mathbf{a},\mathbf{b})$$该距离易受边缘点的影响。

2.1.2 最小Hausdorff距离³

  公式如下：

$$d^{\min }(A,B)=\underset{\mathbf{a}\in A,\mathbf{b}\in B}{\min }d(\mathbf{a},\mathbf{b}).$$

2.1.3 平均Hausdorff距离⁴

  公式如下：

$$d^{\mathrm{a}\mathrm{v}\mathrm{e}}(A,B)=\frac{\sum _{\mathbf{a}\in A}\underset{\mathbf{b}\in B}{\min }d(\mathbf{a},\mathbf{b})+\sum _{\mathbf{b}\in B}\underset{\mathbf{a}\in A}{\min }d(\mathbf{b},\mathbf{a})}{|A|+|B|}$$

2.1.4 可适应Hausdorff距离⁵

  Zafra等认为，正包与正包、正包与负包、负包与负包之间的距离计算应该是不一样的，因此：
d a d a ( A , B ) = { d m i n ( A , B ) ,      正 包 与 正 包 ; d m a x ( A , B ) ,      正 包 与 负 包 ; d a v e ( A , B ) ,       负 包 与 负 包 ; d^{\rm ada} (A, B) =

$$\begin{cases} d^{min} (A, B) , \ \ \ \ 正包与正包;\\ d^{max} (A, B) , \ \ \ \ 正包与负包;\\ d^{ave} (A, B) , \ \ \ \ \ 负包与负包;\\ \end{cases}$$ dada(A,B)=⎩⎪⎨⎪⎧​dmin(A,B),    正包与正包;dmax(A,B),    正包与负包;dave(A,B),     负包与负包;​

2.1.5 $k$阶Hausdorff距离²

  $k$阶Hausdorff距离为解决边缘点对最大Hausdorff距离距离的影响，其将$h(B_i,B_j)$修改为：

$$h(A,B)=k_{\mathbf{a}\in A}^{th}\underset{\mathbf{b}\in B}{\min }d(\mathbf{a},\mathbf{b}),$$其中$k^{th}$表示第$k$个最大值，自然$k$取最大值时，该距离退化为最大Hausdorff距离。

2.2 基于OWA算子的距离⁶

  OWA (Ordered weighted averaging operators)能够替换Hausdorff距离中的$\max$、$\min$操作，以提高其性能。

  给定长度为$m$的序列$V$，OWA首先对其降序排列得到$C$，再对排序后的序列分配权重$w_i\in [0,1]$，且${\sum }_{i=1}^m{w}_i=1$。加劝平均值的计算如下：

$${\mathrm{O}\mathrm{W}\mathrm{A}}_W(V)=\sum _{i=1}^m{w}_i{c}_i,$$其中$W=⟨w_1,\cdots ,w_m⟩$代表权重向量，$C=⟨c_1,\cdots ,c_m⟩$表示降序排列值。

  OWA运算可以看作是对一组值进行任意的聚合操作的概况。例如求向量$V$中的最大值，只需分配权重$W=⟨1,0,\cdots ,0⟩$即可。

2.2.1 OWA版最大Hausdorff距离

  需要将$h(A,B)$替换为：

$$h^{\mathrm{O}\mathrm{W}\mathrm{A}}(A,B)={\mathrm{O}\mathrm{W}\mathrm{A}}_{W_{\max }}\underset{a\in A}{\underbrace{{\mathrm{O}\mathrm{W}\mathrm{A}}_{W_{\min }}\underset{b\in B}{\underbrace{\Vert a-b\Vert }}}}.$$

2.2.2 OWA版平均Hausdorff距离

$$d_{\text{OWA}}^{\mathrm{a}\mathrm{v}\mathrm{e}}(A,B)=\frac{\sum _{a\in A}{\mathrm{O}\mathrm{W}\mathrm{A}}_{W\min }\underset{b\in B}{\underbrace{\Vert a-b\Vert }}+\sum _{b\in B}{\mathrm{O}\mathrm{W}\mathrm{A}}_{W\min }\underset{a\in A}{\underbrace{\Vert a-b\Vert }}}{|A|+|B|}.$$

2.2.3 权重给定

  权重的设置可以参见⁷，有以下两个版本：

1. $W_{\max }$的线性递减 (Linearly Decreasing)版本：

$$W_{\max -L}=⟨\frac{2}{m+1},\frac{2(m-1)}{m(m+1)},\cdots ,\frac{4}{m(m+1)},\frac{2}{m(m+1)}⟩.$$

2. $W_{\max }$的逆向累加 (Inverse Additive)版本：

$$W_{\max -IA}=⟨\frac{1}{1\sum _{i=1}^m\frac{1}{i}},\frac{1}{2\sum _{i=1}^m\frac{1}{i}},\cdots ,\frac{1}{(m-1)\sum _{i=1}^m\frac{1}{i}},\frac{1}{m\sum _{i=1}^m\frac{1}{i}}⟩.$$对于$W_{\min }$，只需将上述权重向量反向。

2.3 Earth Movers距离⁸

$$d^{\mathrm{E}\mathrm{M}\mathrm{D}}(A,B)=\sum _{a\in A,b\in B}f(a,b)d(a,b),$$其中$d(a,b)$是欧式距离，$f(a,b)$是使得总距离最小的flow，满足以下条件：

min ⁡ D E M D ( A , B ) s . t . { f ( a , b ) ≥ 0 , ∑ a ∈ A f ( a , b ) ≤ 1 n b , ∑ b ∈ B f ( a , b ) ≤ 1 n a , ∑ a ∈ A ∑ b ∈ B f ( a , b ) = 1.

$$\begin{array}{l} \qquad \min D^{\rm EMD} (A, B)\\ s.t.\begin{cases} f (a, b) \geq 0,\\ \sum_{a \in A} f (a, b) \leq \frac{1}{n_b},\\ \sum_{b \in B} f (a, b) \leq \frac{1}{n_a},\\ \sum_{a \in A} \sum_{b \in B} f (a, b) = 1. \end{cases} \end{array}$$ minDEMD(A,B)s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​f(a,b)≥0,∑a∈A​f(a,b)≤nb​1​,∑b∈B​f(a,b)≤na​1​,∑a∈A​∑b∈B​f(a,b)=1.​​

2.4 马氏距离

  用于MIL的马氏距离定义如下为：每个包的分布用具有均值$\mu$和协方差矩阵$\sum$的高斯分布来描述：

$$d^{\mathrm{M}\mathrm{D}}(A,B)={\left({\mu }_a-{\mu }_b\right)}^{\mathrm{T}}{\left(\frac{1}{2}\sum _a+\frac{1}{2}\sum _b\right)}^{-1}\left({\mu }_a-{\mu }_b\right)$$该距离的局限在于当包中实例较少但维度较高时，对协方差矩阵求你是很困难甚至是不可能的。

2.5 Cauchy–Schwarz Divergence

  该距离试图解决高斯分布可能过于restrictive的问题：

$$d^{\mathrm{C}\mathrm{S}\mathrm{D}}(A,B)=-\log \left(\frac{K_{{\sigma }_a+{\sigma }_b}(A,B)}{{\left(K_{2{\sigma }_a}(A,B)K_{2{\sigma }_b}(A,B)\right)}^{1/2}}\right),$$其中

$$K_{\sigma }(A,B)=\sum _{a\in A,b\in B}\frac{\exp \left(\frac{1}{-2{\sigma }^2}(a-b{)}^{\mathrm{T}}(a-b)\right)}{{\left(2\pi {\sigma }^2\right)}^{d/2}}.$$当$A$、$B$来自同一数据集时，有${\sigma }_a={\sigma }_b$ ^{9 10}。

3 核函数

3.1 miGraph

   详情参见：https://blog.csdn.net/weixin_44575152/article/details/106253273。

3.2 Isolation Set-Kernel

  详情参见：https://blog.csdn.net/weixin_44575152/article/details/105624719。

---

1. E. Deza, M.-M. Deza, Dictionary of distances, Elsevier, 2006. doi:https://doi.org/10.1016/B978-0-444-52087-6.X5000-8. ↩︎

2. G. Edgar, Measure, topology, and fractal geometry, 3rd print. Springer-Verlag, Berlin, 1995. ↩︎ ↩︎

3. J. Wang and J.-D. Zucker, “Solving multiple-instance problem: a lazy learning approach,” pp. 1119–1125, 2000. [Online]. Available: http://cogprints.org/2124/ ↩︎

4. M.-L. Zhang and Z.-H. Zhou, “Multi-instance clustering with applications to multi-instance prediction,” Applied Intelligence, vol. 31, no. 1, pp. 47–68, 2009. ↩︎

5. A. Zafra, M. Pechenizkiy, S. Ventura, ReliefF-MI: An extension of ReliefF to multiple instance learning, Neuro computing75(1)(2012)210–218. doi:https://doi.org/10.1016/j.neucom.2011.03.052.
   URL http://www.sciencedirect.com/science/article/pii/S0925231211003997 ↩︎

6. R. R. Yager, J. Kacprzyk, The ordered weighted averaging operators: Theory and applications, Springer Science & Business Media, 2012. ↩︎

7. S. Vluymans, D. S. Tarragó, Y. Saeys, C. Cornelis, F. Herrera, Fuzzy multi-instance classifiers, IEEE Transactions on Fuzzy Systems 24 (6) (2016) 1395–1409. ↩︎

8. Y. Rubner, C. Tomasi, L. J. Guibas, The earth mover’s distance as a metric for image retrieval, International journal of computer vision 40 (2) (2000) 99–121. ↩︎

9. V. Cheplygina, D. M. J. Tax, M. Loog, Multiple instance learning with bag dissimilarities, Pattern Recogn 48 (1) (2015) 264–275. ↩︎

10. M. Budka, B. Gabrys, K. Musial, On accuracy of pdf divergence estimators and their applicability to representative data sampling, Entropy 13 (7) (2011) 1229–1266. ↩︎