基于查询—文档异构信息网络的半监督学习

doi:10.3969/j.issn.1000-436x.2014.08.006

摘要/Abstract

摘要：

基于图的半监督学习近年来得到了广泛的研究，然而，现有的半监督学习算法大都只能应用于同构网络。根据查询及文档自身的内容特征和点击关系构建查询—文档异构信息网络，并引入样本的判别信息强化网络结构。提出了查询—文档异构信息网络上半监督聚类的正则化框架和迭代算法，在正则化框架中，基于流形假设构造了异构信息网络上的代价函数，并得到该函数的封闭解，以此预测未标记查询和文档的类别标记。在大规模商业搜索引擎查询日志上的实验表明本方法优于传统的半监督学习方法。

关键词: 异构信息网络, 半监督学习, 信息检索, 点击日志

Abstract:

Various graph-based algorithms for semi-supervised learning have been proposed in recent literatures. How-ever, although classification on homogeneous networks has been studied for decades, classification on heterogeneous networks has not been explored until recently. The semi-supervised classification problem on query-document heteroge-neous information network which incorporate the bipartite graph with the content information from both sides is consid-ered. In order to strengthen the network structure, class information of sample nodes is introduced. A semi-supervised learning algorithm based on two frameworks including the novel graph-based regularization framework and the iterative framework is investigated. In the regularization framework, a new cost function to consider the direct relationship be-tween two entity sets and the content information from both sides which leads to a significant improvement over the baseline methods is developed. Experimental results demonstrate that proposed method achieves the best performance with consistent and promising improvements.

Key words: heterogeneous information networks, semi-supervised learning, information retrieval, click-through data

刘钰峰,李仁发. 基于查询—文档异构信息网络的半监督学习[J]. 通信学报, 2014, 35(8): 40-47.

Yu-feng LIU,Ren-fa LI. Semi-supervised learning by constructing query-document heterogeneous information network[J]. Journal on Communications, 2014, 35(8): 40-47.

图/表 5

表1

表2

表3

表4

表5

参考文献 20

[1]	SUN Y , YU Y , HAN J . Ranking-based clustering of heterogeneous information networks with star network schema[A]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discov-ery and Data mining[C]. Paris, France, 2009. 797-806.
[2]	SUN Y , HAN J . Mining heterogeneous information networks: a struc-tural analysis approach[J]. SIGKDD Explorations, 2012,14(2): 20-28.
[3]	BELKIN M , NIYOGI P , SINDHWANI V . Manifold regularization: a geometric framework for learning from labeled and unlabeled exam-ples[J]. The Journal of Machine Learning Research, 2006,7: 2399-2434.
[4]	ZHOU D , BOUSQUET O , LAL T N , et al. Learning with local and global consistency[J]. Advances in Neural Information Processing Systems, 2004,16: 321-328.
[5]	LI X , WANG Y Y , ACERO A . Learning query intent from regularized click graphs[A]. Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Re-trieval[C]. Singapore, Singapore, 2008. 339-346.
[6]	WU W , LI H , XU J . Learning query and document similarities from click-through bipartite graph with metadata[A]. Proceedings of the Sixth ACM International Conference on Web Search and Data Min-ing[C]. Roman, Italy, 2013. 687-696.
[7]	CHEN Y , WANG L , DONG M . Non-negative matrix factorization for semisupervised heterogeneous data coclustering[J]. Knowledge and Data Engineering, 2010,22(10): 1459-1474.
[6]	DENG H , HAN J , ZHAO B , et al. Probabilistic topic models with biased propagation on heterogeneous information networks[A]. Pro-ceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. San Diego, CA, 2011. 1271-1279.
[9]	DENG H , HAN J , LYU M R , et al. Modeling and exploiting hetero-geneous bibliographic networks for expertise ranking[A]. Proceedings of the 12th ACM/IEEE-CS Joint Conference on Digital Libraries[C]. New York, USA, 2012. 71-80.
[10]	ZHOU Z H , LI M . Semi-supervised learning by disagreement[J]. Knowledge and Information Systems, 2010,24(3): 415-439.
	JOHNSON R , ZHANG T , . Graph-based semi-supervised learning and spectral kernel design[J]. IEEE Transactions on Information Theory, 2008,54(1): 275-288.
[12]	LUCCHESE C , ORLANDO S , PEREGO R , et al. Identifying task-based sessions in search engine query logs[A]. Proceedings of the Fourth ACM International Conference on Web Search and Data Min-ing[C]. Hong Kong ,China, 2011. 277-286.
[13]	BOLDI P , BONCHI F , CASTILLO C , et al. The query-flow graph:model and applications[A]. Proceedings of the 17th ACM Conference on Information and Knowledge Management[C]. Napa Valley ,USA, 2008. 609-618.
[14]	BOLDI P , BONCHI F , CASTILLO C , et al. Query suggestions using query-flow graphs[A]. Proceedings of the 2009 Workshop on WebSearch Click Data[C]. Barcelona, Spain, 2009. 56-63.
[13]	JONES R , KLINKNER K L , et al. Beyond the session timeout: automatic hierarchical segmentation of search topics in query logs[A]. Proceed-ings of the 17th ACM Conference on Information and Knowledge Management[C]. Napa Valley ,USA, 2008. 699-708.
[16]	PAN J , KONG F S , WANG R Q . Locality sensitive discriminant transductive learning[J]. Journal of Zhejiang University, Engineering Science, 2012,46(6): 987-994.
[17]	CHEN X , CHEN S , XUE H , et al. A unified dimensionality reduction framework for semi-paired and semi-supervised multi-view data[J]. Pattern Recognition, 2012,45(5): 2005-2018.
[18]	DENG H , LYU M R , KING I , A generalized Co-HITS algorithm and its application to bipartite graphs[A]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. Paris,France, 2009. 239-248.
[19]	RAZ R . On the complexity of matrix product[J]. SIAM Journal on Computing, 2003,32(5): 1356-1369.
[20]	STREHL A , GHOSH J . Cluster ensembles: a knowledge reuse frame-work for combining multiple partitions[J]. The Journal of Machine Learning Research, 2003,3: 583-617.

类别	旅游	体育	军事	财经	IT
文档	12 004	28 772	12 707	33 381	15 171
查询	3 823	7 719	4 237	9 066	4 487
平均点击数	11.13	12.73	9.96	14.68	12.38

样本百分比/%	LLGC(G_Q)		LLGC(G_QD)		QDGC
样本百分比/%	AC/%	NMI/%	AC/%	NMI/%	AC/%	NMI/%
1	62.2	41.7	52.7	31.5	73.6	59.8
2	65.4	42.7	53.4	32.3	75.3	61.7
3	64.7	413.8	53.5	32.7	74.1	60.2
4	67.3	45.0	58.0	37.4	76.6	63.4
5	68.9	47.5	62.3	44.0	77.8	65.2

样本百分比%	LLGC(G_Q)		LLGC(G_QD)		QDGC
样本百分比%	AC/%	NMI/%	AC/%	NMI/%	AC/%	NMI/%
1	77.5	62.1	56.3	35.5	78.6	65.2
2	78.2	64.7	59.2	40.5	80.7	67.9
3	81.1	69.0	59.9	40.2	81.0	69.1
4	81.9	70.2	62.1	45.8	83.2	73.6
5	82.2	72.1	63.4	46.0	83.1	74.0

样本百分比(q%, d%)	LLGC(G_D)		LLGC(G_QD)		SS-NMF		QDGC		QDGC(G1)
样本百分比(q%, d%)	AC/%	NMI/%	AC/%	NMI/%	AC/%	NMI/%	AC/%	NMI/%	AC/%	NMI/%
(0.1%,0.1%)	35.7	22.5	42.4	27.1	78.3	63.2	64.9	47.4	78.6	63.8
(0.2%,0.2%)	45.0	28.3	47.8	29.4	80.1	65.3	69.2	55.8	81.2	66.2
(0.3%,0.3%)	49.7	31.8	50.1	30.8	84.2	71.1	73.0	61.3	83.4	70.2
(0.4%,0.4%)	54.5	33.2	53.6	32.9	83.0	72.1	74.5	62.6	84.5	72.9
(0.5%,0.5%)	56.2	36.7	58.7	35.6	83.5	73.8	78.2	66.1	84.7	74.5

样本百分比(q%, d%)	LLGC(G_D)		LLGC(G_QD)		SS-NMF		QDGC		QDGC(G1)
样本百分比(q%, d%)	AC/%	NMI/%	AC/%	NMI/%	AC/%	NMI/%	AC/%	NMI/%	AC/%	NMI/%
(0.1%,0.1%)	63.3	42.7	49.0	28.3	79.3	67.5	72.2	60.8	81.1	68.8
(0.2%,0.2%)	69.0	53.5	53.1	32.6	84.4	74.0	75.5	63.6	85.7	74.2
(0.3%,0.3%)	72.7	58.3	54.8	33.0	85.2	74.1	78.4	66.3	86.0	76.0
(0.4%,0.4%)	72.0	58.0	57.2	35.4	85.3	75.7	80.2	69.7	84.6	75.2
(0.5%,0.5%)	73.2	60.6	59.8	41.2	85.9	76.2	83.8	72.2	87.1	77.5