基于挖掘异构信息网络中的标签和实例间关系的多标签分类

Severus

论文标题： Multi-Label Classification by Mining Label and Instance Correlations from Heterogeneous Information Networks.

论文链接：文章链接

作者： Xiangnan Kong、Bokai Cao、Philip S. Yu

问题描述：

       在常规的链接预测方法中，要先假设标签之间已经给定了相关性、或者假设这些相关性可以根据计算样本数据标签的共现概率直接预测出来，才能利用不同标签类之间的关联性来进行机器学习。而在现实的多标签分类任务中，这种标签间的相关性是很难得到的。因此针对这样的研究问题，本文提出了挖掘异构网络中关系结构的方法，来获得不同的标签类之间、不同样本数据间的多种关系，再利用这些关系有效预测不同标签类间的相关性，最后根据相关性来进行链接预测。

===========================================================================

一些概念：

1、标签和实例：举例来说，在gene-disease相关预测中，要预测某个基因会引起哪些疾病，那么gene就是实例，disease就是标签，标签就是需要预测出来的东西。

2、用到的变量：假设在一个多标签分类任务中包含n个实例和q个标签；
     
     （1） 一组实例表示为：VI={I1，I2，...，In}，每个实例Ii都有一个特征向量xi；

     （2） 一组备选标签标示为Vl={l1，l2，...，lq}；

     （3） 假定VI中的前nl个实例表示为VIl={I1，...，Inl}∈VI，是已经确定标签的实例；

     （4） 每个实例Ii分别与一组标签相关，标识为Yi={Yi1，...，Yiq}∈{0，1}^q，如果实例Ii的标签集中有第j个标签lj，则Yij=1，否则Yij=0。

       VI中其余的实例是未确定标签的，多标签分类任务就是要预测这些未确定标签的实例的标签集合。

3、meta-path：节点类型i与j之间的每种连接关系都代表了一种二元关系R，R（vip,vjq）表示节点vip与vjq被某一种关系R所连接起来（如Figure 1）。

         
        
          （Figure 1）

4、meta-path-based label correlations：举例来说，在上图中基因节点通过PPI的meta-path直接相关，通过这样的meta-path关联可以发掘出隐藏的节点间关系：连接在一起的基因标签更可能（或更不可能）共同属于同一个化合物的标签集。

5、meta-path-based instance correlations：与label相同，实例节点也可以被确定的meta-path相互关联起来，这样的实例节点的标签集也是相关的。比如Figure 1中
                  chemical compound——（cause side effect）→side effect——（cause side effect -1）→chemical compound
      
      根据这样的关系，可以推测引起相同副作用的化合物更可能（或更不可能）拥有相似的标签集。

===========================================================================

PIPL算法：

         

          （Figure 2 PIPL算法）

1、meta-path construction: 给定一个异构网络，设定最大路径长度p_max，分别提取所有label和instance间长度≤p_max的meta-path，并去掉多余的路径；

2、training initialization：利用下图中的算法，为标签间相关性和实例间相关性构建相关特征。把每个实例xi转化成xik，构建一个q倍扩展的训练集，使得对1≤k≤q，有Dk={（xik，yik）}，使用这个扩展训练集为每个标签训练一个分类器；

         

          （Figure 3 构建相关特征的算法）
                                                                                                ^
3、bootstrap：预测标签集合，对于i∈U：对Yi产生一个预测值Yi；

3、iterative inference：迭代更新测试实例的标签预测结果。

===========================================================================

评价标准：（其中h(xi)表示一个分类器h为xi给出的预测标签集合）

1、Micro F1（值越大性能越好）：

2、Hamming Loss（值越小性能越好）：

3、Subset 0/1 Loss（值越小性能越好）：

===========================================================================

实验结果

       为了证明PIPL算法的性能优势，本文还把这个算法与BSVM、ECC、PISL、ICML、PIML五个算法进行了比较，这五种方法所使用的关系类型各不相同，文中分别用这五个方法进行了两个多标签分类任务：gene-disease关联预测和drug-target结合预测，计算了各个方法性能的平均分和标准差，并对分数进行了排名。结果证明基于meta-path的方法性能要优于不考虑实例和标签间关系的方法，并且在所有方法中PIPL算法的性能最好。另外，在性能稳定性测试中，改变了特征的数量，PIPL算法在不同数量下的数据上均运行良好，证明该算法对数据的数量变化不敏感（对比见Figure 4和5）。
        
         

          （Figure 4）

         

          （Figure 5）

===========================================================================

总结

       文章中提出了一个新的分类算法，我个人理解文中提到的label间、instance间、label和instance间的meta-path其实跟相似性网络和关系网络是一样的，只不过新颖之处在于多了一步构建meta-path和构建相关特征（training initialization）的步骤。传统的方法中要么是假设所有节点间都是相互独立的，要么就是之运用了单一的关系类型，因此性能都没有这个新的算法好。