Collaborative Filtering for Massive Datasets Based on Bayesian Networks
Tóm tắt
This paper proposes a collaborative filtering method for massive datasets that is based on Bayesian networks. We first compare the prediction accuracy of four scoring-based learning Bayesian networks algorithms (AIC, MDL, UPSM, and BDeu) and two conditional-independence-based (Cl-based) learning Bayesian networks algorithms (MWST, and Polytree-MWST) using actual massive datasets. The results show that (1) for large networks, the scoring-based algorithms have lower prediction accuracy than the CI-based algorithms and (2) when the scoring-based algorithms use a greedy search to learn a large network, algorithms which make a lot of arcs tend to have less prediction accuracy than those that make fewer arcs. Next, we propose a learning algorithm based on MWST for collaborative filtering of massive datasets. The proposed algorithm employs a traditional data mining technique, the “a priori” algorithm, to quickly calculate the amount of mutual information, which is needed in MWST, from massive datasets. We compare the original MWST algorithm and the proposed algorithm on actual data, and the comparison shows the effectiveness of the proposed algorithm.
Tài liệu tham khảo
Agrawal, R., Imielinski, T., and Swami, A. (1993). Mining association rules between sets of items in large databases. In Proceedings of 1993 ACM SIGMOD International Conference on Management of Data (pp.207–216).
Agrawal, R. and Srikant, R. (1994). Fast algorithms for mining association rules in large databases. In Proceedings of 20th International Conference on Very Large Databases (pp.478–499).
Akaike, H. (1974). A new look at the statistical model identification. IEEE Transactions on Automatic Control, 19: 716–723.
Balabanovic, M. and Shoham, Y. (1997). Fab: Content-based, collaborative recommendation. Communications of the ACM, 40(3), 66–72.
Billsus, D. and Pazzani, M. (1998). Learning collaborative information filters. In Proc. Int’l Conf. Machine Learning.
Bouckaert, R. (1994). Probablistic network construction using the minimum description length principle. Technical report ruu-cs-94-27, Utercht University.
Breese, J., Heckerman, D., and Kadie, C. (1998). Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of 14th Conference on Uncertainty in Artificial Intelligence.
Buntine, W.L. (1991). Theory refinement on Bayesian networks. In Proceedings of UAI-91.
Cheng, J. and Greiner, R. (1999). Comparing Bayesian network classifiers. In Uncertainty in Artificial Inteligence (pp. 101–108).
Chickering, D. (1995). Learning Bayesian networks is np-complete. In Learning from Data: Artificial Intelligence and Statistics, volume V (pp. 121–130).
Chow, C.K. and Lin, C.N. (1968). Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, IT-14:462-467.
Cooper, G.F. and Herskovits, E. (1991). A Bayesian method for constructing Bayesian belief networks from databases. In Proceedings of UAI-91.
Cooper, G.F. and Herskovits, E. (1992). A Bayesian methods for the inducation of probabilistic networks from data. Machine Learning, 9, 309–347.
Delgado, J. and Ishii, N. (1999). Memory-based weighted-majority prediction for recommendar systems. In Proc. ACM SIGIR’ 99 Workshop Recommender Systems: Algorithms and Evaluation.
Friedman, N., Geiiger, D., and Goldszmidt, M. (1997). Bayesian network classifiers. Machine Learning, 29, 131–161.
Getoor, L. and Sahami, M. (1999). Using probabilistic relational models for collaborative filtering. In Proc. Workshop Web Usage Analysis and User Profiling (WEBKDD’ 99).
Goldberg, K., Roeder, T., Gupta, D., and Perkins, C. (2001). Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval J., 4(2), 133–151.
Greiner, R., Grove, A., and Schuurmans, D. (1997). Learning Bayesian nets that perform well. In Proceedings of UAI-97.
Heckerman, D., Geiger, D., and Chickering, D. (1995). Learning Bayesian networks the combination of knowledge and statistical data. Machine Learning, 20, 197–243.
Heckerman, D., Meek, C., and Cooper, G. (1997). A Bayesian approach to causal discovery. Technical report msr-tr-97-05, Microsoft. Research.
Hill, W., Stead, L., Rceenstein, M., and Furnas, G. (1995). Recommending and evaluating choioes in a virtual community of use. In Proceedings of the Conference on Human Factors in Computing Systems.
Hofmann, T. (2003). Collaborative filtering via Gaussian probabilistic latent semantic analysis. In Proc. 26th Ann. Int’l ACM SIGIR Conf.
Jensen, F. (1996). An Introduction to Bayesian networks. University College London Press
Marlin, B. (2003). Modeling user rating profiles for collaborative filtering. In Proc. 17th Ann. Conf. Neural Information Processing Systems (NIPS’ 03).
Murphy, K.P., Weiss, Y., and Jordan, M.I. (1999). Loopy belief propagation for approximate inference: An empirical study. In Proceedings of Uncertainty in Artificial Intelligence (pp.467–475).
Nakamura, A. and Abe, N. (1998). Collaborative filtering using weighted majority prediction algorithms. In Proc. 15th Int’l Conf. Machine Learning.
Pavlcv, D. and Pennock, D. (2002). A maximum entropy approach to collaborative filtering in dynamic, sparse, high-dimensional domains. In Proc. 16th Ann. Conf. Neural Information Processing Systems (NIP’ 02).
Pearl, J. (1988). Probabilistic Reasoning Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.
Resnick, P., Iakovou, N., Sushak, M., Bergstrom, P., and Riedl, J. (1994). Grouplens: An open architecture for collaborative filtering of netnwa. In Proceedings of 1994 Computer Supported Coopemtive Work Conference.
Rissanen, J. (1963). A universal prior for integers and estimation by minimum description length. Anmls of Statistics, 11, 416–431.
Shardanand, U. and Maes, P. (1995). Social information filtering: Algorithms for automating’ word of mouth’. In Proceedings of Conference on Human Factors in Computing Systems.
Suzuki, J. (1993). A construction of Bayesian networks from databases on mdl principle. In Proceedings of UAI-93 (pp. 266–273).
Ungar, L. and Foster, D. (1998). Clustering methods for collaborative filtering. In Proc. RecommerAer Systems, Papers from 1998 Workshop. Technical Report WS-98-08.
Weiss, Y. (1997). Belief propagation and revision in networks with loops. Technical report: Aim-1616, Massachusetts Institute of Technology.
Yang, S. and Chang, K.-C. (2002). Comparison of score metrics for Bayesian network lerarning. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humars, 32(3).