Heterogeneous source consensus learning via decision propagation and negotiation

ABSTRACT

Nowadays, enormous amounts of data are continuously generated not only in massive scale, but also from different, sometimes conflicting, views. Therefore, it is important to consolidate different concepts for intelligent decision making. For example, to predict the research areas of some people, the best results are usually achieved by combining and consolidating predictions obtained from the publication network, co-authorship network and the textual content of their publications. Multiple supervised and unsupervised hypotheses can be drawn from these information sources, and negotiating their differences and consolidating decisions usually yields a much more accurate model due to the diversity and heterogeneity of these models. In this paper, we address the problem of "consensus learning" among competing hypotheses, which either rely on outside knowledge (supervised learning) or internal structure (unsupervised clustering). We argue that consensus learning is an NP-hard problem and thus propose to solve it by an efficient heuristic method. We construct a belief graph to first propagate predictions from supervised models to the unsupervised, and then negotiate and reach consensus among them. Their final decision is further consolidated by calculating each model's weight based on its degree of consistency with other models. Experiments are conducted on 20 Newsgroups data, Cora research papers, DBLP author-conference network, and Yahoo! Movies datasets, and the results show that the proposed method improves the classification accuracy and the clustering quality measure (NMI) over the best base model by up to 10%. Furthermore, it runs in time proportional to the number of instances, which is very efficient for large scale data sets.

REFERENCES

• 1: J. Barthelemy and B. Leclerc. The median procedure for partition. Partitoning Data Sets, AMS DIMACS Series in Discrete Math., 19:3--34, 1995.
• 2: Eric Bauer , Ron Kohavi, An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants, Machine Learning, v.36 n.1-2, p.105-139, July-August 1999 [doi>10.1023/A:1007515423169]
• 3: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 4: C.-C. Chang and C.-J. Lin. Libsvm: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 5: Thomas G. Dietterich, Ensemble Methods in Machine Learning, Proceedings of the First International Workshop on Multiple Classifier Systems, p.1-15, June 21-23, 2000
• 6: Carlotta Domeniconi , Muna Al-Razgan, Weighted cluster ensembles: Methods and analysis, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-40, January 2009 [doi>10.1145/1460797.1460800]
• 7: Xiaoli Zhang Fern , Carla E. Brodley, Solving cluster ensemble problems by bipartite graph partitioning, Proceedings of the twenty-first international conference on Machine learning, p.36, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015414]
• 8: Vladimir Filkov , Steven Skiena, Integrating Microarray Data by Consensus Clustering, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.418, November 03-05, 2003
• 9: K. Ganchev, J. Graca, J. Blitzer, and B. Taskar. Multi-view learning over structured and non-identical outputs. In Proc. of UAI' 08, pages 204--211, 2008.
• 10: Jing Gao , Wei Fan , Jing Jiang , Jiawei Han, Knowledge transfer via multiple model local structure mapping, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401928]
• 11: A. Genkin, D. D. Lewis, and D. Madigan. Bbr: Bayesian logistic regression software. http://stat.rutgers.edu/~madigan/BBR/.
• 12: Aristides Gionis , Heikki Mannila , Panayiotis Tsaparas, Clustering aggregation, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.4-es, March 2007 [doi>10.1145/1217299.1217303]
• 13: J. Hoeting, D. Madigan, A. Raftery, and C. Volinsky. Bayesian model averaging: a tutorial. Statist. Sci., 14:382--417, 1999.
• 14: T. Joachims. Transductive learning via spectral graph partitioning. In Proc. of ICML' 03, pages 290--297, 2003.
• 15: G. Karypis. Cluto - family of data clustering software tools. http://glaros.dtc.umn.edu/gkhome/views/cluto.
• 16: Tao Li , Chris Ding , Yi Zhang , Bo Shao, Knowledge transformation from word space to document space, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390368]
• 17: Charles X. Ling , Qiang Yang, Discovering Classification from Data of Multiple Sources, Data Mining and Knowledge Discovery, v.12 n.2-3, p.181-201, May 2006 [doi>10.1007/s10618-005-0013-7]
• 18: Bo Long , Zhongfei (Mark) Zhang , Philip S. Yu, Combining Multiple Clusterings by Soft Correspondence, Proceedings of the Fifth IEEE International Conference on Data Mining, p.282-289, November 27-30, 2005 [doi>10.1109/ICDM.2005.45]
• 19: Ping Luo , Fuzhen Zhuang , Hui Xiong , Yuhong Xiong , Qing He, Transfer learning from multiple source domains via consensus regularization, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458099]
• 20: Sofus A. Macskassy , Foster Provost, Classification in Networked Data: A Toolkit and a Univariate Case Study, The Journal of Machine Learning Research, 8, p.935-983, 5/1/2007
• 21: Andrew Kachites McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, Automating the Construction of Internet Portals with Machine Learning, Information Retrieval, v.3 n.2, p.127-163, July 2000 [doi>10.1023/A:1009953814988]
• 22: Jennifer Neville , David Jensen, Relational Dependency Networks, The Journal of Machine Learning Research, 8, p.653-692, 5/1/2007
• 23: Christine Preisach , Lars Schmidt-Thieme, Ensembles of relational classifiers, Knowledge and Information Systems, v.14 n.3, p.249-272, March 2008 [doi>10.1007/s10115-007-0093-3]
• 24: Alexander Topchy , Anil K. Jain , William Punch, Clustering Ensembles: Models of Consensus and Weak Partitions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.12, p.1866-1881, December 2005 [doi>10.1109/TPAMI.2005.237]
• 25: P. Sen, G. M. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective classification in network data. Technical Report CS-TR-4905, University of Maryland, College Park, 2008.
• 26: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003
• 27: D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. SchOlkopf. Learning with local and global consistency. In Proc. of NIPS' 04, pages 321--328, 2004.
• 28: Shenghuo Zhu , Kai Yu , Yun Chi , Yihong Gong, Combining content and link for classification using matrix factorization, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277825]
• 29: X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
classification, consensus, ensemble, heterogeneous sources