Multi-Label Algorithm [1] – ML-KNN

ML-KNN 是多标记学习中最经典的算法之一,即使是现在以经常出现在 Multi-Label 的论文中,作为 Benchmark 进行比较。
原论文可以从这里拿到 Ml-knn: A Lazy Learning Approach to
Multi-Label Learning

ML-KNN 思路

ML-KNN 借鉴了 KNN 的思路,通过测试样本临近 K 个样本的标记情况估计测试样本与每个待预测标记相关的后验概率。
需要注意的是 ML-KNN 训练与预测的过程中对不同标记分开预测,所以它属于多标记问题的一阶 (First Order) 算法。

算法的过程比较简单,可以直接看 ML-KNN 的伪代码:

ML-KNN Pseudo Code

算法输入 (T, K, t, s) 分别表示训练样本集合 T,考虑临近样本数量 K,测试样本 t,Laplace 平滑处理系数 s(处理好的除 0 的情况)。
算法输出 \left (\vec{y}_t,\vec{r}_t \right ) 分别表示测试样本的预测标记和预测概率。

算法 (1)-(2) 通过训练集估计了样本同每个标记相关 / 不相关的先验概率 P(H_1^l), P(H_0^l)。其中 H_0^l 表示样本同第 l 个标记不相关的事件, H_1^l 表示样本同第 l 个标记相关的事件。
算法 (3)-(13) 通过训练集估计了当样本同第 l 个标记相关时,其 K 临近样本中有 j 个样本也持有标记 l 的后验概率 P(E_j^l | H_1^l) 和当前样本同第 l 个标记不相关时的相同后验概率 P(E_j^l | H_0^l)。其中,E_j^l 表示样本的 K 临近中有 j 个样本持有标记 l 的事件。

算法 (4)-(18) 预测测试样本 t 的标记与对应概率。针对每种标记 l,计算样本 tK 临近中持有标记 l 的数量 $\vec{C}t^l,然后根据这个值找到训练阶段算好的后验概率P(E{\vec{C}t^l}^l | H_1^l), P(E{\vec{C}_t^l}^l | H_0^l)和标记对应的先验概率P(H_1^l), P(H_0^l)
我们要计算出测试样本
tK临近中持有标记l的数量\vec{C}_t^l的情况下自己持有标记l$ 的概率是多少:

\begin{aligned}
P(H_1^l | E_{\vec{C}_t^l}^l )
&= \frac{P(E_{\vec{C}_t^l}^l | H_1^l) P(H_1^l)}{P(E_{\vec{C}_t^l}^l)}\\
&= \frac{P(E_{\vec{C}_t^l}^l | H_1^l) P(H_1^l)}{P(E_{\vec{C}_t^l}^l | H_1^l) P(H_1^l) + P(E_{\vec{C}_t^l}^l | H_0^l) P(H_0^l)}\\
\end{aligned}

当此概率大于 0.5 时,我们就认为此样本持有标记 l

Python 代码实现

代码根据算法 ML-KNN 公开的 Matlab 代码 MLKNN 和论文中伪代码实现。
使用 Python3.7 编写,其中借用 sklearn 中的 KDTree 实现并加速 K 临近的查找。

使用方法和 sklearn 的学习器类似,实现了 fit, predict, predict_proba 三个用于训练和预测函数。
Github链接:MLKNN.py

在按照论文中的设定在多标记数据集 yeast 上进行测试,十折交叉验证后。
Hamming Loss 为 0.195 \pm 0.006,同原文中结果 0.194\pm0.010 基本相同。

简单思考与讨论

  1. 作为将标记独立考虑的多标记算法,ML-KNN 同 KNN 的区别仅在从后验概率的角度对标记进行预测。使用 KNN 单独对每一个标记进行预测和使用 ML-KNN 进行预测的结果是否会相近?

  2. 算法过程中涉及到计算 P(H_1^l), P(H_0^l),如果在训练集合中正样本极度系数,势必导致 P(H_1^l) 非常低,令对应标记的预测结果都是不相关。 ML-KNN 在样本不均衡的情况下效果是否会变差?

  3. ML-KNN 算法现在是不是有一些过时了,现在的论文里不怎么同 ML-KNN 的结果进行比较了。