ML-KNN(多标签分类)
ML-kNN 多标签k近邻算法 MLL Week 1
学习张敏灵老师的《ML-kNN: a lazy learning approach to multi-label learning》的学习笔记。
传统kNN
k近邻算法(k-Nearest Neighbour, KNN)是机器学习中最基础，最简单的常用算法之一。其思想非常直接：如果一个样本在特征空间中的k个最相似(即特征空间中距离最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
如下图的Xu，它最近的邻居中属于ω1的最多，因此他被归类于ω1类。
这个思想很容易理解，就是俗话中常说的“近朱者赤，近墨者黑”。在单标签学习中，与一个实例在特征空间中越相近(即距离越近)的实例，他们之间标签相同的可能性就越大。
多标签kNN
而在多标签问题中，我们仍可根据这个思想推导出多标签学习的kNN算法，即ML-kNN算法。
多标签kNN的主要思想是对于每一个新实例(instance)，距离它最近的k个实例(特征空间中与它的距离最小的k个实例)可以首先得到，然后得到这些实例的标签集合，之后通过最大后验概率准则来确定新实例的标签集合。
这里给出算法的具体数学计算方法：
变量定义：
k为取最近邻个数
Y为所有标签的集合，总标签个数可以定义为n
l为一个标签，l∈Y
x为一个实例
Yx为实例x对应的标签集合，Yx∈Y
y⃗ x为x的标记向量，是一个1×n的行向量，它的元素y⃗ x(l)若为1，代表l∈Yx，若为0，则l∉Yx
N(x)记录x的k个最近邻的索引
然后，我们可以得到对应k近邻实例的标签信息：
这里，C⃗ x是一个1×n的行向量，它的元素C⃗ x(l)指的是对于标签l，x的k个近邻中有多少个近邻拥有这个标签。
则，对于新的实例t，首先得到其k个近邻索引集合N(t)，定义事件Hl1为t有标签l，事件Hl0为t无标签l，定义事件Elj ( j∈{0,1,⋯,k})为对于标签l，k个近邻中有j个包含这个标签。则基于向量C⃗ t，可以通过最大后验概率准则和贝叶斯准则得到：
其中，y⃗ t(l)即为我们要求的结果，代表t实例是否有l标签。
本人注释:注意,这里的Elj
千万不要理解为针对实例t,而是针对整个数据集而言的,即任一数据点,其k近邻中有j个包含标签l这一事件,因此后边的条件概率就是在实例t的状态下
()
因此上述式子本质上是个联合概率,参数是b,即实例t含l标签或者不含l标签,目标是实例t的状态和与t同一状态(指与t同含标签l或者同不含标签l)的任一的数据点k近邻中标签l数量与实例t相等这一事件的联合分布.
其实这个问题可以这样考虑，给定实例t,考察其是否含有标签l,假设其k近邻中含有标签l的有j个,那么我们就考察任抽一数据点其含有标签l&&其k近邻有j个含有标签l这个事件的概率P1，以及任抽一数据点其不含有标签l&&其k近邻有j个含有标签l这个事件的概率P2。若P1概率大,则我们认定实例t应含有标签l,否则实例t应不含有标签l.
Elj
其中P(Hlb)代表t是否有l标签的先验概率，可以用l标签在整个训练集上出现的次数除以标签总次数来求出。
本人注释:此处似乎有误,H右下标应为b,而不是1,虽然b要么是0要么是1.这里的先验概率实际上有两个值,分别对应b=0和b=1.
即样本中拥有l标签的向量数目除以向量总数。
后验概率P(ElC⃗ t(l)|Hlb)计算方法为：
本人注释:上述公式有误,左边条件概率中H右下标应为b,所以这个后验概率实际上有两个值,分别对应b=0和b=1.P(Hlb)
其中c[j]的j等于C⃗ t(l)，即t的k近邻中有标签l的个数。
c[]的意思是：若xn的k近邻中有l标签的个数为δ，且xn有标签l，则c[δ]+1，n∈{1,2,…,m}。
则c[j]代表的就是所有向量中，其k近邻有j个l标签，且其自身也有l标签的向量的个数。
由此，∑kp=0c[p]即为这个向量有l标签，其k近邻有0∼m个有l标签的情况的向量个数总和。
算出P(Hlb)P(ElC⃗ t(l)|Hlb)之后，我们只需看b={0,1}中哪种情况使得这个乘积值最大，若b=1时最大，则向量t有l标签，反之则没有。
本文转载自:http://blog.csdn.net/Kodoo/article/details/49905877