ML-KNN:A lazy learning approach to multi-label learning

1 MLKNN简介

多标签学习来源于文本分类问题,一个文档可能同时属于几个不同的类别。在多标签学习中,训练集中的每个样例有多个标签,我们的主要任务是预测测试样本的标签集合。
多标签数据学习方法主要分为两种,一种问题转换法,包括转换为二分类、转换为标签排序、转换为多分类。另一种是算法适应法,包括Lazy learning(如ML-KNN)、Decision tree(如ML-DT)、Kernel learning(如Rank-svm)、Neural network(如BP-MLL)、information-theoretic(如CML)、Spectral analysis(如MLLS)。
MLKNN是由传统的K近邻(K-nearest neighbor,KNN)发展而来的,对于每一个测试样本,在训练集中找到它的K近邻。然后,基于邻居样本的统计信息,如属于相同类别的邻居的个数,用最大后验概率原则(MAP)决定测试样本的标签集合。

2 评价指标

多标签学习系统的评价指标与传统的单个标签学习系统不同,单标签任务常见的评价指标有accuracy、precision、 recall 、F-measure。多标签任务的评价指标更为复杂,主要有海明损失(Hamming loss,HL)、1-错误率(One-error,OE)、覆盖率(Coverage)、排序损失(Ranking loss,RL)、平均精度(Average precision,AVP)。

2.1 海明损失(Hamming loss,HL)

海明损失可以用来评估一个样本被错分多少次,例如,一个样本不属于标签A但是被错分成标签A,或者是,一个样本属于标签A,但是没有被预测为标签A。
也可以说,用海明损失来计算分类器预测出的结果序列与结果序列之间的数值上的距离。海明损失越小,预测结果越好。
$$HL=\frac{1}{m}.\sum_{i=1}^{m}\frac{|Y_i\Delta Z_i|}{M}$$
m–样本个数
M–所有标签总个数
$Y_i$–样本i实际标签的集合
$Z_i$–样本i预测标签的集合
$\Delta$–两个集合的对称差,异或

2.2 1-错误率(One-error,OE)

1-错误率可以用来评估在输出结果中排序第一的标签并不属于实际标签集中的概率。相当于单标签分类问题中的评价指标error。1-错误率越小,预测结果越好。
$$
one-error=\frac{1}{m}.\sum_{i=1}^{m}g( \quad(\arg\max_{y\in Y}f(x_i,y))\notin Y_i\quad)
$$
$$
g(x)=\begin{cases}
0& \text{x为假}\\
1& \text{x为真}
\end{cases}
$$

2.3 覆盖率(Coverage)

覆盖率评价我们平均还差多远,在排序列表中向下,直接覆盖了所有与这个样本相关的标签。覆盖率越小,预测结果越好。
$$
coverage=\frac{1}{m}.\sum_{i=1}^{m}\max_{y\in Y_i}rank_f(x_i,y)-1
$$

2.4 排序损失(Ranking loss,RL)

表示有多少不相关的标签排序高于相关的标签。排序损失用来表示在结果排序中,不属于相关标签集中的项目被排在了属于相关标签集中项目的概率的平均。排序损失越小,预测结果越好。
$$
\begin{aligned}
RL=\frac{1}{m}.\sum_{i=1}^{m}\frac{1}{|Y_i||\overline{Y_i}|}|\{\quad (y_1,y_2)\quad |f(x_i,y_1)\le f(x_i,y_2),(y_1,y_2)\in Y_i\times \overline{Y_i} \}\quad |
\end{aligned}
$$
$\overline{Y_i}$是$Y_i$相对于所有类别标签集合L的补集。

2.5 平均精度(Average precision,AVP)

在所有的预测结果排序中,排序排在相关标签集的标签前面,且属于相关标签集的概率,该指标反映了分类标签的平均精确度。这个指标最初用于信息检索(IR)系统,用来评估检索的文本排序性能。平均精度越大,预测效果越好。
$$
\begin{aligned}
AVG&=\frac{1}{m}\sum_{i=1}^{m}\frac{1}{|Y_i|}\times\sum_{y \in Y_i} \frac{|y^{‘}\quad|\quad rank_f(x_i,y^{‘})\le rank_f(x_i,y),y^{‘}\in Y_i)|}{rank_{f}(x_i,y)}
\end{aligned}
$$

3 ML-KNN

给定样本x和它的类别集合$Y\subseteq\Omega$,令$\overrightarrow{y_x}$表示x的类别向量,如果标签$\iota \in \Omega$,那么$\overrightarrow{y_x}(\iota)(\iota\in\Omega)$的值为1,否则为0。
令N(x)表示样本x在训练集中的K近邻,根据这些邻居的标签集,可以计算属于第$\iota$个类别的邻居个数,用公式表示为:
$$\overrightarrow{C_x}(\iota)=\sum_{a\in N(x)}\overrightarrow{y_a}(\iota)$$
对于一个测试样本t,用最大后验概率原则(MAP)决定测试样本是否有类别标签$\iota$,使用如下公式:
\begin{aligned}
\vec y_{t}(L) &= \arg\max \limits_{b\in\{0,1\}} p(H_{b}^L | E_{\vec C_{t} (L)}^L)
\\&=\arg\max \limits_{b\in\{0,1\}} p(H_{b}^L).p(E_{\vec C_{t} (L)}^L | H_{b}^L)
\end{aligned}
其中,$H_{1}^L $表示t中包含情绪标签L,$H_{0}^L $表示t不包含情绪标签L。 $E_{j}^L $($j\in\{0,1,…,k\} $ )表示在t的k近邻中,有j个样本有标签L。$\vec C_{t}^L $ 用来计算t的k个近邻中含有情绪L的近邻个数,$\vec C_{t}^L=\sum_{a\in N(t)}\vec y_{a}(L) $ 。先验概率$p(H_{b}^L) $ 和后验概率 $p(E_{\vec C_{t} (L)}^L | H_{b}^L) $可以从训练集中计算频度得到。具体的ML-KNN算法过程如图所示:
mlknn 图片中,s为平滑参数,可被设为1。$\vec r_t$是一个真实值向量,用来排序$\Omega$中的标签。c[j]统计训练集样本中,满足自己含有标签$\iota$,且它的K近邻正好有j个标签l这两个条件的样本的个数。$c^{‘}[j]$统计训练集样本中,满足自己含有标签$\iota$,且它的K近邻正好有j个标签$\iota$这两个条件的样本的个数.

4 代码实现

我尝试用python编程实现本文的多标签学习评价指标以及MLKNN算法,详见github,欢迎交流指教。

5 参考资料

[1] Zhang M L, Zhou Z H. ML-KNN: A lazy learning approach to multi-label learning[J]. Pattern recognition, 2007, 40(7): 2038-2048.
[2] 姚源林. 面向微博文本的情绪分析方法研究[D]. 哈尔滨工业大学, 2014.

此条目发表在学术分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注