基于种子节点选择和链路预测的多标签分类算法研究

摘要

随着互联网等信息技术的发展，网络数据挖掘占据着越来越重要的地位，并成功应用于用户行为分析，文档分类，图像分类等领域。分类问题可以进一步分为单标签分类和多标签分类。分类任务中，当分类对象属于多个候选类中的一个类别时，该问题称为单标签分类;当分类对象属于多个候选类中的多个类别时，该问题称为多标签分类。集体分类方法将网络中的边视为同质的，能够对相互连接的多个实体同时进行分类，可以取得较好的分类效果，主要适用于同质信息网络中的单标签分类问题。然而现实世界中，人们经常面临的是多关系网络，网络实体一般同时拥有多个标签，实体间的链接往往代表不同的语义含意，链接的类型多种多样。集体分类无法区分多关系网络中边的异构情况，难以获得较高的分类准确率。多关系网络环境下的多标签分类问题，目前已取得了众多学者的广泛关注，并得到了广泛的研究。
　　已有的方法中，通常都是从网络中随机的选取节点作为训练集，分类结果不稳定，分类精度不高。本文借鉴了主动学习思想，提出了SHDA算法，利用网络的拓扑结构，将网络划分为多个affiliations，从每个affiliation中按比例的选取度数高的节点，最后将选择的节点合并处理后得到种子节点。对种子节点进行预先标注并作为训练集进行多标签分类，能够使得分类算法以最小的样本获得最高的分类精度，提高多标签分类的准确率。
　　现实生活中的网络数据可能存在不完备，不全面的情况，网络数据不一定能真实的反应现实世界中实体间的关系。针对这种情况，我们提出了LP-SCRN算法，使用偶数步的链路预测算法为网络预测出部分缺失链接，然后利用实体间社会特征的相似度为预测出的链接赋予权值，根据归一化后的链路权值，结合实体邻居的标签，实体的类传播概率，使用标签松弛法迭代的计算实体属于各个类的概率，最终预测出实体的标签。LP-SCRN算法将链路预测与多标签关系邻居分类器结合起来，真实数据集上的实验表明，该算法能够提升多关系网络中多标签分类的准确率。

目录

声明

致谢

摘要

第一章 绪论

1．1 研究背景、目的及意义

1．2 国内外研究现状

1．2．1 多标签分类

1．2．2 种子节点选择

1．2．3 链路预测

1．2．4 链路预测和多标签分类的结合

1．3 本文主要研究内容

1．4 论文结构

1．5 本章总结

第二章 相关工作

2．1 多标签分类问题的定义

2．2 集体分类

2．2．1 基于局部条件分类器的集体分类方法

2．2．2 基于全局优化的集体分类方法

2．3 关系分类器(Relational Classifiers)

2．4 多关系网络下的多标签分类算法

2．4．1 潜在社会维度(Latent Social Dimensions，LSD)

2．4．2 EdgeCluster算法

2．4．3 Relational Neighbor Classification using Social Context Features(SCRN)

2．4．4 网络交叉验证(Network Cross-Validation，NCV)

2．4．5 评价指标

2．5 本章总结

第三章 基于种子节点选择的多关系网络下多标签分类算法

3．1 概述

3．2 SHDA(Nodes Selection of High Degree from Each Affiliation)算法

3．3 SHDA算法验证

3．4 实验结果

3．4．1 实验结果分析

3．4．2 算法迭代次数分析

3．4．3 算法运行效率分析

3．5 本章总结

第四章 基于链路预测的多关系网络下多标签分类算法

4．1 概述

4．2 链路预测

4．2．1 基于相似性的链路预测指标

4．2．2 κ-折交叉验证

4．2．3 评价指标AUC(Area Under the receiver operating characteristic Curve)

4．3 LP-SCRN算法

4．4 实验设计

4．4．1 数据集

4．4．2 对比算法

4．5 实验结果

4．5．1 实验结果分析

4．5．2 阈值τ的分析

4．6 本章总结

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

攻读学位期间的学术活动及成果情况