异构信息网络上基于图正则化的半监督学习
刘钰峰;李仁发
【摘 要】Heterogeneous information networks ,composed of multiple types of objects and links ,are ubiquitous in real life .Therefore ,effective analysis of large‐scale heterogeneous information networks poses an interesting but critical challenge . Learning from labeled and unlabeled data via semi‐supervised classification can lead to good knowledge extraction of the hidden network structure . How ever ,although semi‐supervised learning on homogeneous netw orks has been studied for decades , classification on heterogeneous networks has not been explored until recently . In this paper , we consider the semi‐supervised classification problem on heterogeneous information networks with an arbitrary schema consisting of a number of object and link types .By applying graph regularization to preserve consistency over each relation graph corresponding to each type of links separately , we develop a classifying function which is sufficiently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points .We propose an iterativ
e framework on heterogeneous information network in which the information of labeled data can be spread to the adjacent nodes by iterative method until the steady state .We infer the class memberships of unlabeled data from those of labeled ones according to their proximities in the network .Experiments on the real DBLP data set clearly show that our approach outperforms the classic semi‐supervised Learning methods .%现实世界中存在着大量包含多种类型的对象和联系的异构信息网络，从中挖掘信息获取知识已成为当前的研究热点之一．基于图正则化的半监督学习在近年来得到了广泛的研究，然而，现有的半监督学习算法大都只能应用于同构网络．基于同构节点和异构节点的一致性假设，提出了任意结构的异构信息网络上的半监督学习的正则化分类函数，并得到分类函数的闭式解，以此预测未标记节点的类别．提出了异构信息网络上的半监督学习的迭代框架，标记节点的信息可以在邻近的节点上迭代传播，直至达到稳定状态，并证明了迭代算法将收敛于正则化分类函数的闭式解．DBL P数据集上的实验表明该方法优于经典的半监督学习算法．
【期刊名称】《计算机研究与发展》
【年(卷),期】2015(000)003
【总页数】8页(P606-613)
【关键词】异构信息网络;同构信息网络;半监督学习;正则化框架;聚类
【作 者】刘钰峰;李仁发
【作者单位】正则化半监督方法湖南大学信息科学与工程学院长沙 410082;湖南大学信息科学与工程学院长沙 410082; 湖南大学嵌入式系统与网络实验室长沙 410082
【正文语种】中 文
【中图分类】TP391.4
现实世界中存在着许多包含大规模数据的信息网络，例如社会网络、WWW网络、生物网络以及基于学术论文的引文网络等.很显然，信息网络已成为信息社会中普遍存在的关键性组成部分，从大型信息网络中抽取知识已经吸引了大量计算机科学、社会科学以及生物科学研究人员的注意［1－3］.
在当前的研究中，信息网络通常被认为是同构网络，即网络中的节点是同一类型，其连接关
系也是同一种类型，研究者在此领域取得了巨大的成就，例如：PageRank，Hits以及谱聚类等.然而，在现实世界中更多的是异构网络，即网络中包含多种类型的节点，典型的如学术论文数据集（DBLP），其中就包含作者、论文、主题词以及会议等诸多异构数据及其之间的联系［4］.近年来，研究者在异构信息网络上开展了一系列工作，试图根据数据自身特征及相互关系挖掘有用的信息［5－7］.文献［7］提出了一种把排序信息用于聚类的方法Rankclus，这种策略能直接应用于异构的二部图和星形图的聚类.文献［8］基于标签和Web对象的二部图开展了异构Web对象的分类研究.文献［1］把节点的内容信息和Hits算法结合起来，构造了一种能为异构的二部图节点进行排序的算法Co-Hits.文献［9］在此基础上发展了一种能为多种异构数据进行排序的算法MultiRank.然而，以上的研究局限于特定的网络结构，不能推广到任意的异构信息网络上.文献［10］建立了异构网络上的主题传播模型（topic model with biased propagation，TMBP），该模型能同时利用异构网络及网络节点上的内容信息对作者、论文以及会议进行聚类.文献［11］在此基础上进一步分析异构网络上的排序问题用于专家推荐.文献［2］指出了异构信息网络上挖掘的主要任务，并总结了在异构信息网络上挖掘信息的方法学.
在一些应用场景中可以获得少量的标记数据，学习器对标记数据进行学习，借此对数据进行
分类有助于研究者发现信息网络中隐藏的结构，并进一步理解不同数据节点的作用，这一方法称为半监督学习，基于图正则化的半监督学习也是近年来的研究热点之一［12－13］.这种方法往往通过数据之间的特征构造相似矩阵，然后根据数据的几何结构进行聚类.文献［14］基于数据的局部和全局的一致性提出了一种从标记节点进行学习的迭代算法和正则化框架局部全局一致性学习（learning with local and global consistency，LLGC）.文献［15］基于图正则化构建图的关系矩阵，然后使用非负矩阵分解（non-negative matrix factorization，NMF）来探寻图的几何结构用于聚类，该方法称为GNMF（graph regularized NMF）.谱图聚类是另一种基于图的聚类方法，其本质是将聚类问题转化为图的最优划分问题.Kamvar［16］以及Chen［17］等人在此基础上发展了基于谱聚类的半监督学习算法SL（spectral learning）.文献［18］提出了一种基于正则化的半监督多标记学习方法（multilabel semi-supervised，MASS），该  方  法引  入 2 种正则项分别用于描述多个标记的共性信息和约束相似样本应拥有相似的结构化多标记输出.在基于图正则化的半监督学习领域，图的构造对算法的性能有较大的影响，文献［19］采用b-Matching方法产生平衡的正则图，获得了比传统的k-近邻法和ε近邻法方法更好的鲁棒性.当我们把基于同构网络的算法应用到异构网络上时，通常采用以下2种方法：1）抽取异构网络中的同构子网进行分析，但这
样往往会忽略掉许多对挖掘数据关联有用的信息，例如在DBLP网络中我们不仅可以借助于论文之间的引用关系进行聚类，还可以借助于作者与论文、主题词与论文的关系进行聚类；2）忽略节点的类型，把整个异构网络视为同一种类型进行分析.这种方法忽略了节点之间连接的语义信息，往往把各种连接信息统一的进行规范化，文献［7］认识到这可能导致性能下降.
本文的目标是在给定少量节点类别标记的情况下预测异构信息网络上未标记节点类别.我们首先给出了异构信息网络的定义，并提出了同构节点和异构节点上的一致性假设，在此基础上分别构建了正则化框架和迭代算法.在正则化框架中构造了同构节点上和异构节点之间的代价函数，并得到了该框架的闭式解，同时证明了迭代算法将收敛于该闭式解.分析了正则化框架和迭代算法的时间复杂度，结果表明在大规模稀疏网络中迭代算法更有优势.在DBLP数据集上的实验表明本文方法优于传统的半监督学习方法.
1 基于图正则化的半监督学习
本节首先给出异构信息网络的定义及相关的概念和符号，然后提出异构信息网络上的一致性假设，并根据一致性假设给出异构信息网络上半监督学习的正则化框架和迭代算法.
1.1 问题描述
本节我们介绍相关的概念和符号以及异构信息网络上半监督学习问题的定义.
给定一个图G＝（V，E），其中V表示数据对象的边的集合.当N＝1时，该信息网络被称为同构信息网络，当N≥2时，该网络被称为异构信息网络［2］.
在给定了一个异构信息网络G＝（V，E）及类别标记的数据子集V′⊆V＝i∪＝1Xi的情况下，预测未标记的数据子集V－V′的过程，即为异构信息网络上的半监督学习.假设我们需要把数据划分为c个类别，则对于类型为Xi的数据，假定该类型上的数据共有Ni个，则我们需要得到Xi的类别指示矩阵F（i）∈RNi×c，整个数据集上的类别指示矩阵表示为F＝（F（1），F（2），…，F（N））T.在此，F 为一个向量函数：F：V→Rc，聚类问题可以描述为对V中的顶点vi根据yi＝arg mca  xFij进行类别推断.根据先验知识，可以由用户对V中的若干数据先进行标记，我们使用Y（i）∈RNi×c表示类型为 Xi 的数据的初始化标记矩阵.如果初始标记Xi中的第p个数据属于第q类，则令Yp（iq）＝1，其他情况下都令Yp（iq）＝0，整个数据集上的 类 别 指 示 矩 阵s 表 示 为Y ＝ （Y（1），Y（2），…，Y（N））T.需要注意的是在Y中既包含了标记数据，也包含了未标记的数据.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。