引入

  地址：https://www.sciencedirect.com/science/article/pii/S0957417419307444
  期刊：Expert Systems With Applications
  要点：
  1）基于聚类的全新实例选择策略；
  2）多视角特征空间。
  假设：
  标准多示例假设。
  有任何疑问请及时与窝联系~

1 CMIL

  本文符号表如下：

符号	含义
B t r B^{tr} Btr	训练包集合
B t e s t B^{test} Btest	测试包集合
B + t r B_+^{tr} B+tr​	训练正包集合
B − t r B_-^{tr} B−tr​	训练负包集合
B i t r B_i^{tr} Bitr​	第 i i i个训练包
y i ∈ { − 1 , 1 } y_i \in \{ -1, 1 \} yi​∈{−1,1}	训练包标签
X t r X^{tr} Xtr	训练实例集合
X + t r X_+^{tr} X+tr​	训练正实例集合
X − t r X_-^{tr} X−tr​	训练负实例集合
x i = [ x i ( 1 ) , x i ( 2 ) , ⋯   , x i ( v ) ] x_i = [x_i^{(1)}, x_i^{(2)}, \cdots, x_i^{(v)}] xi​=[xi(1)​,xi(2)​,⋯,xi(v)​]	用多视角特征表示的实例
v v v	特征类型数量
G r Gr Gr	聚类集合
P P P	所找到的正实例集合

  训练过程分为两阶段：
  1）正实例选择；
  2）训练SVM。
  首先，正包中的实例通过聚类分簇，其暗含数据集的分布信息 [ 1 ] ^{[1]} [1]。对于每一个簇，首先计算实例对的相似度；其次基于instance ranking algorithm为每个实例打分，并选取高分实例作为正实例；最终，所选择的正实例与余下的负实例用于构建分类器。
  在测试阶段，实例级别的预测算法将用于测试包。基于标准多示例假设，如果当前包有至少一个实例预测为正，则该包为正。

1.1 多视角子空间聚类 (multi-view subspace clustering)

  本文中，多视角子空间聚类算法将同时考虑多视角特征空间及未标记数据。
  令 X l = [ x 1 ( l ) , x 2 ( l ) , ⋯   , x n ( l ) ] ∈ R d × n X^{l} = [x_1^{(l)}, x_2^{(l)}, \cdots, x_n^{(l)}] \in \mathbb{R}^{d \times n} Xl=[x1(l)​,x2(l)​,⋯,xn(l)​]∈Rd×n表示第 l l l类特征， d d d是特征空间维度。根据self-expression property [ 2 ] ^{[2]} [2]， X ( l ) X^{(l)} X(l)可以重表示为：
X ( l ) = X ( l ) Z ( l ) + E , (4) X^{(l)} = X^{(l)} Z^{(l)} + E, \tag{4} X(l)=X(l)Z(l)+E,(4)其中 Z ( l ) Z^{(l)} Z(l)是第 l l l类特征的表示矩阵 (representation matrix)， E E E是误差矩阵。

  多视角子空间的目标函数如下：
min ⁡ Z ( l ) ∑ l = 1 v ∥ X ( l ) − X ( l ) Z ( l ) ∥ F 2 + Ω , (5) \min_{Z^{(l)}} \sum_{l = 1}^v {\| X^{(l)} - X^{(l)} Z^{(l)} \|}_F^2 + \mathbf{\Omega}, \tag{5} Z(l)min​l=1∑v​∥X(l)−X(l)Z(l)∥F2​+Ω,(5)其中 Ω \mathbf{\Omega} Ω是包含不同属性的正则项， norm- F \text{norm-}F norm-F用于评估误差矩阵 E E E。
  通过每个独立的 Z ( l ) Z^{(l)} Z(l)，我们获得 Z \boldsymbol{Z} Z。结合谱聚类，则得到最终的聚类结果。

1.2 多相似性图 (multiple similarity graphs)

  基于聚类结果，本章节对如何构建多相似性图进行介绍。

1.2.1 区分相似性 (discriminative similarity)

  首先说明直接相似性 (directly similarity)：组内实例相似组间实例不同。当然，这也是一种直观的需求。对于直接相似正实例 x i ∈ X + t r x_i \in X_+^{tr} xi​∈X+tr​，则需要与负实例不同。
  因此，区分相似性被定义为如何使得直接相似正实例与负实例不同。本文中，区分相似性的计算如下：
D S ( x i , x j ) = { 1 ϕ ( i , j ) ⋅ ϕ ( j , i )  if  T i , j > 0 , T j , i > 0 0  otherwise, D S\left(x_{i}, x_{j}\right)=\left\{ \begin{array}{ll} \frac{1}{\phi(i, j) \cdot \phi(j, i)} & \text { if } T_{i, j}>0, T_{j, i}>0 \\ 0 & \text { otherwise,} \end{array} \right. DS(xi​,xj​)={ϕ(i,j)⋅ϕ(j,i)1​0​ if Ti,j​>0,Tj,i​>0 otherwise,​其中 T i , j = w i ⋅ x j = f ( x j ) T_{i, j} = w_i \cdot x_j = f (x_j) Ti,j​=wi​⋅xj​=f(xj​)， w i w_i wi​为基于直接正实例与所有负实例所训练的线性SVM模型，实例 x i x_i xi​所对应的权重。
   ϕ ( i , j ) \phi (i, j) ϕ(i,j)的计算示意如图1 (图片源自原论文)：
  1）给定五个实例 x 1 , ⋯   , x 5 x_1, \cdots, x_5 x1​,⋯,x5​；
  2）如果需要计算 D S ( x 1 , x 5 ) DS (x_1, x_5) DS(x1​,x5​)，对于 x 1 x_1 x1​，对其除去其下标所对应元素的其他元素由大至小排列， x 5 x_5 x5​同理；
  3）对于 x 1 x_1 x1​，找到 x 1 , 5 x_{1, 5} x1,5​对应元素在排序数组中的位置，这里的 ϕ ( 1 , 5 ) = 2 \phi (1, 5) = 2 ϕ(1,5)=2；同理 ϕ ( 5 , 1 ) = 1 \phi (5, 1) = 1 ϕ(5,1)=1。

  为了处理多视角特征空间问题，对于每种类型的特征，exemplar-SVMs为实例 x i x_i xi​训练模型，而后获得 T i , j ( l ) = f ( l ) ( x j ) T_{i, j}^{(l)} = f^{(l)} (x_j) Ti,j(l)​=f(l)(xj​)。即多个 S V M SVM SVM基于不同的特征空间训练。最终的区分相似性计算如下：
D S ( x i , x j ) = ∑ l = 1 v D S ( l ) ( x i , x j ) . DS (x_i, x_j) = \sum_{l = 1}^v DS^{(l)} (x_i, x_j). DS(xi​,xj​)=l=1∑v​DS(l)(xi​,xj​).  本文中， ∀ f ( x ) , w = w i \forall f (x), w = w_i ∀f(x),w=wi​.

1.2.2 初始化相似性图

  相似性图被定义为一个无向权图 G = ( V , E ) G = (V, E) G=(V,E)。 e i j e_{ij} eij​表示两个实例之间的边。
  本文基于聚类结果构建多个相似性图，并且对于每个簇中的实例对， D S DS DS被用于初始化 e i j e_{ij} eij​。

  云里雾里吗？巧了，我也是哈哈哈。

1.2.3 区分相似性的一致性

  本文使用quasi-clique来度量 D S ( x i , x j ) DS (x_i, x_j) DS(xi​,xj​)的一致性分数。quasi-clique的定义如下：
  定义1：给定无向图 G = ( V , E ) G = (V, E) G=(V,E)，quasi-clique C γ C_\gamma Cγ​是 V V V的一个子集，且 G ( C γ ) G (C_\gamma) G(Cγ​)有至少 ⌊ γ q ( q − 1 ) 2 ⌋ \lfloor \gamma \frac{q (q - 1)}{2} \rfloor ⌊γ2q(q−1)​⌋条边，其中 q = ∣ C γ ∣ q = | C_\gamma| q=∣Cγ​∣， G ( C γ ) G (C_\gamma) G(Cγ​)是由 C γ C_\gamma Cγ​导出的子图。
  最大quasi-clique的大小定义为一致性得分：
C S ( x i , x j ) = { max ⁡ k { ∣ C k ∣ } ∀ k x i , x k ∈ C k , 0 o t h e r w i s e . (8) CS (x_i, x_j)= \left \{ \begin{array}{ll} \max_k \{ |C_k| \} & \forall k x_i, x_k \in C_k,\\ 0 & otherwise. \end{array} \right. \tag{8} CS(xi​,xj​)={maxk​{∣Ck​∣}0​∀kxi​,xk​∈Ck​,otherwise.​(8)  获得 C S CS CS后，可以基于 G   e i j = α D S ( x i , x j ) + C S ( x i , x j ) G\ e_{ij} = \alpha DS (x_i, x_j) + CS (x_i, x_j) G eij​=αDS(xi​,xj​)+CS(xi​,xj​)来更新相似性图，其中 α \alpha α是一个权衡参数。

  依然蒙蔽，依然不知道他怎么做的。。。

1.3 实例的阶

算法1：实例选择
  
输入：
  训练实例集合 X t r X^{tr} Xtr，聚类中心数 K K K
输出：
  实例选择集合
  
1：

---

参考文献：
[1] Zhou, Z. , & Zhang, M. (2007). Solving multi-instance problems with classifier ensemble based on constructive clustering. Knowledge and Information Systems, 11 (2), 155–170.
[2] Cao, X. , Zhang, C. , Fu, H. , Liu, S. , & Zhang, H. (2015). Diversity-induced multi-view subspace clustering. In IEEE conference on computer vision and pattern recognition, CVPR 2015, boston, ma, usa, june 7–12, 2015 (pp. 586–594)
[3] Pei, J. , Jiang, D. , & Zhang, A. (2005). On mining cross-graph quasi-cliques. In Proceedings of the eleventh ACM SIGKDD international conference on knowledge discovery and data mining, chicago, illinois, usa, august 21–24, 2005 (pp. 228–238).