臺灣博碩士論文加值系統

Recommendation research has achieved successful results in many application areas. However, for supermarkets, since the transaction data is extremely skewed in the sense that a large portion of sales is concentrated in a small number of best selling items, collaborative filtering based customer-triggered recommenders usually recommend hot sellers while rarely recommend cold sellers. But recommenders are supposed to provide better campaigns for cold sellers to increase sales.

In this thesis, we propose an alternative ``item-triggered'' recommendation to identify potential customers for cold sellers. In item-triggered recommendation, the recommender system will return a ranked list of customers who are willing to buy a given item. This problem can be formulated as a problem of classifier learning, but due to the skewed distribution of the transaction data, we need to solve the rare class problem, where the number of negative examples is much larger than the positive ones. We present a boosting algorithm to train an ensemble of SVM classifiers to solve the rare class problem and compare the algorithm with its variants. We apply our algorithm to a real-world supermarket database and use the area under the ROC curve (AUC) metric to evaluate the quality of the output ranked lists. Experimental results show that our algorithm can improve from a baseline approach by about twenty-three percent in terms of the AUC metric for cold sellers which is as low as 0.64\% of customers have ever purchased.

1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Bayesian Optimal Recommendation . . . . . . . . . . . . 14
1.3.2 Types of Recommender . . . . . . . . . . . . . . . . . . 17
1.4 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Related Work 22
2.1 Recommender System . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.2 Taxonomy of Recommendation Techniques . . . . . . . . 24
2.1.3 Content-Based Recommendation . . . . . . . . . . . . . . 27
2.1.4 Collaborative Filtering Based Recommendation . . . . . . 28
2.2 Support Vector Machine . . . . . . . . . . . . . . . . . . . . . . 30
2.3 Rare Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4 Boosting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Item-triggered Recommendation 42
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2 System Framework . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Boosting SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4 Varation of Boosting SVM . . . . . . . . . . . . . . . . . . . . . 52
3.5 From item-triggered to customer-triggered . . . . . . . . . . . . . 54
4 Experiments 55
4.1 Ta-Feng Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Cold Sellers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3 Experiment Environment . . . . . . . . . . . . . . . . . . . . . . 63
4.4 Evaluation Methodology . . . . . . . . . . . . . . . . . . . . . . 64
4.5 Potential Customer of Cold Seller Detection . . . . . . . . . . . . 66
4.6 Targeted Advertisement of Unsought Products . . . . . . . . . . . 69
4.7 Cold Sellers Recommendation . . . . . . . . . . . . . . . . . . . 74
4.7.1 Removing Hot Sellers from Data . . . . . . . . . . . . . . 75
4.7.2 Only Recommend Cold Sellers . . . . . . . . . . . . . . . 80
5 Conclusion and FeatureWork 84

[1] George S. Almasi and Alvert J.Lee. A pda-based personalized recommender
agent. In Proceedings of the Fifth International Conference on the Practical
Application of Intelligent Agent and Multi Agent Technology, pages 299–309,
April 2000.
[2] Liliana Ardissono, Cristina Gena, Pietro Torasso, Fabio Bellifemine,
A. Chiarotto, A. Difino, and B. Negro. Personalized recommendation of TV
programs. In AI*IA 2003: Advances in Artificial Intelligence, pages 474–486,
2003.
[3] Ricardo A. Baeza-Yates and Berthier A. Ribeiro-Neto. Modern Information
Retrieval. ACM Press / Addison-Wesley, 1999.
[4] Marko Balabanovi’c; and Yoav Shoham. Fab: content-based, collaborative
recommendation. Communications of the ACM, 40(3):66–72, 1997.
[5] Nicholas J. Belkin and W. Bruce Croft. Information filtering and information
retrieval: two sides of the same coin? Communications of the ACM,
35(12):29–38, 1992.
[6] John S. Breese, David Heckerman, and Carl Kadie. Empirical analysis of
predictive algorithms for collaborative filtering. Technical report, Microsoft
Research, One Microsoft Way, Redmond, WA 98052, 1998.
[7] John S. Breese, David Heckerman, and Carl Kadie. Empirical analysis of
predictive algorithms for collaborative filtering. In Proceedings of the 14th
Conference on Uncertainty in Artificial Intelligence, pages 43–52, 1998.
[8] Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140,
Augest 1996.
[9] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library
for support vector machines, 2001. Software available at
http://www.csie.ntu.edu.tw/ cjlin/libsvm.
[10] Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, and W. Philip
Kegelmeyer. Smote: Synthetic minority over-sampling technique. Journal
of Artificial Intelligence and Research, 16:321–357, 2002.
[11] Jacques Cohen. Special issue on information filtering. Communications of
the ACM, 35(12), December 1992.
[12] Mukund Deshpande and George Karypis. Item-based top-n recommendation
algorithms. ACM Transactions on Information Systems, 22(1):143–177,
2004.
[13] Thomas G. Dietterich. Ensemble methods in machine learning. Lecture Notes
in Computer Science, 1857:1–15, 2000.
[14] Bradley Efron and Robert J. Tibshirani. An Introduction to the Bootstrap.
Chapman & Hall, 1993.
[15] Christos Faloutsos and Douglas W. Oard. A survey of information retrieval
and filtering methods. Technical Report CS-TR-3514, University of Maryland,
College Park, MD, USA, 1995.
[16] Wei Fan, Salvatore J. Stolfo, Junxin Zhang, and Philip K. Chan. Adacost:
Misclassification cost-sensitive boosting. In ICML ’99: Proceedings of the
Sixteenth International Conference on Machine Learning, pages 97–105, San
Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.
[17] Peter Flach. The many faces of ROC analysis in machine learning, Tutorial
in ICML2004, 2004.
[18] Yoav Freund. Boosting a weak learning algorithm by majority. Information
and Computation, 121(2):256–285, September 1995.
[19] C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: an automatic
citation indexing system. In DL ’98: Proceedings of the third ACM
conference on Digital libraries, pages 89–98. ACM Press, 1998.
[20] David Goldberg, David Nichols, Brian M. Oki, and Douglas Terry. Using
collaborative filtering to weave an information tapestry. Communications of
the ACM, 35(12):61–70, 1992.
[21] Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. Eigentaste:
A constant time collaborative filtering algorithm. Information Retrieval,
4(2):133–151, 2001.
[22] L. K. Hansen and P. Salamon. Neural network ensembles. IEEE Transactions
on Pattern Analysis and Machine Intelligence, 12(10):993–1001, October
1990.
[23] Jonathan L. Herlocker, Joseph A. Konstan, Al Borchers, and John Riedl. An
algorithmic framework for performing collaborative filtering. In SIGIR ’99:
Proceedings of the 22nd annual international ACM SIGIR conference on Research
and development in information retrieval, pages 230–237, New York,
NY, USA, 1999. ACM Press.
[24] Jonathan L. Herlocker, Joseph A. Konstan, Al Borchers, and John Riedl. An
algorithmic framework for performing collaborative filtering. In SIGIR’99:
Proceedings of the 22nd annual international ACM SIGIR conference on Research
and development in information retrieval, pages 230–237. ACMPress,
1999.
[25] Jonathan L. Herlocker, Joseph A. Konstan, and John Riedl. Explaining collaborative
filtering recommendations. In CSCW ’00: Proceedings of the 2000
ACM conference on Computer supported cooperative work, pages 241–250.
ACM Press, 2000.
[26] Jonathan L. Herlocker, Joseph A. Konstan, Loren G. Terveen, and John T.
Riedl. Evaluating collaborative filtering recommender systems. ACM Transactions
on Information Systems (TOIS), 22(1):5–53, 2004.
[27] C.-W. Hsu, C.-C. Chang, and C.-J. Lin. A practical guide to support vector
classification. Technical report, Department of Computer Science and Information
Engineering, National Taiwan University, July 2003.
[28] Chun-Nan Hsu, Hao-Hsiang Chung, and Han-Shen Huang. Mining skewed
and sparse transaction data for personalized shopping recommendation. Machine
Learning, 57(1-2):35–59, 2004.
[29] Zan Huang, Wingyan Chung, and Hsinchun Chen. A graph model for ecommerce
recommender systems. Journal of the American Society for Information
Science and Technology, 55(3):259–274, 2004.
[30] Nathalie Japkowicz. The class imbalance problem: Significance and strategies.
In Proceedings of the 2000 International Conference on Artificial Intelligence
(IC-AI’2000), volume 1, pages 111–117, 2000.
[31] Mahesh V. Joshi, Vipin Kumar, and Ramesh C. Agarwal. Evaluating boosting
algorithms to classify rare classes: Comparison and improvements. In ICDM,
pages 257–264, 2001.
[32] Huang Juny-Ing. The world of Marketing. Commonwealth Publishing Company,
2 edition, 2003.
[33] Ron Kohavi, Llew Mason, Rajesh Parekh, and Zijian Zheng. Lessons and
challenges from mining retail e-commerce data. Machine Learning, 57(1-
2):83–113, 2004.
[34] Yufeng Kou, Chang-Tien Lu, Sirirat Sirwongwattana, and Yo-Ping Huang.
Survey of fraud detection techniques. In Porceedings of the 2004 International
Conference on Networking, Sensing, and Control, pages 749–754,
March 2004.
[35] Miroslav Kubat, Robert Holte, and Stan Matwin. Learning when negative
examples abound. In European Conference onMachine Learning, pages 146–
153, 1997.
[36] Miroslav Kubat, Robert C. Holte, and Stan Matwin. Machine learning for
the detection of oil spills in satellite radar images. Machine Learning, 30(2-
3):195–215, 1998.
[37] Miroslav Kubat and Stan Matwin. Addressing the curse of imbalanced training
sets: one-sided selection. In Proceedings of the 14th International Conference
on Machine Learning, pages 179–186. Morgan Kaufmann, 1997.
[38] R. D. Lawrence, G. S. Almasi, V. Kotlyar, M. S. Viveros, and S. S. Duri.
Personalization of supermarket product recommendations. Data Mining and
Knowledge Discovery, 5(1-2):11–32, 2001.
[39] Steve Lawrence, C. Lee Giles, and Kurt Bollacker. Digital libraries and autonomous
citation indexing. Computer, 32(6):67–71, 1999.
[40] C.-J. Lin. A guide to support vector machines. Technical report, Department
of Computer Science and Information Engineering, National Taiwan University,
November 2004.
[41] Greg Linden, Brent Smith, and Jeremy York. Amazon.com recommendations:
item-to-item collaborative filtering. Internet Computing, IEEE,
7(1):76–80, 2003.
[42] Charles X. Ling and Chenghui Li. Data mining for direct marketing: Problems
and solutions. In Knowledge Discovery and Data Mining, pages 73–79,
1998.
[43] Shoshana Loeb and Douglas Terry. Information filtering. Commun. ACM,
35(12):26–28, 1992.
[44] Marcus A. Maloof. Learning when data sets are imbalanced and when costs
are unequal and unknown. In ICML-2003 Workshop on Learning from Imbalanced
Data Sets II, 2003.
[45] David Maltz and Kate Ehrlich. Pointing the way: Active collaborative filtering.
In CHI’95: Proceedings of the SIGCHI conference on Human factors in
computing systems, pages 202–209. ACM Press/Addison-Wesley Publishing
Co., 1995.
[46] Ron Meir and Gunnar Ratsch. An introduction to boosting and leveraging.
pages 118–183, 2003.
[47] Bradley N. Miller, Istvan Albert, Shyong K. Lam, Joseph A. Konstan, and
John Riedl. Movielens unplugged: experiences with an occasionally connected
recommender system. In IUI ’03: Proceedings of the 8th international
conference on Intelligent user interfaces, pages 263–266. ACM Press, 2003.
[48] Bradley N. Miller, Joseph A. Konstan, and John Riedl. Pocketlens: Toward a
personal recommender system. ACM Transactions on Information Systems,
22(3):437–476, 2004.
[49] Raymond J. Mooney and Loriene Roy. Content-based book recommending
using learning for text categorization. In Proceedings of DL-00, 5th ACM
Conference on Digital Libraries, pages 195–204, San Antonio, US, 2000.
ACM Press, New York, US.
[50] Rajatish Mukherjee, Gerdur Jonsdottir, Sandip Sen, and Partha Sarathi.
Movies2go: an online voting based movie recommender system. In Proceedings
of the 5th international conference on Autonomous agents, pages
114–115. ACM Press, 2001.
[51] Michael J. Pazzani. A framework for collaborative, content-based and demographic
filtering. Artificial Intelligence Review, 13(5-6):393–408, 1999.
[52] Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, and John
Riedl. Grouplens: an open architecture for collaborative filtering of netnews.
In CSCW ’94: Proceedings of the 1994 ACM conference on Computer supported
cooperative work, pages 175–186. ACM Press, 1994.
[53] James Rucker and Marcos J. Polanco. Siteseer: Personalized navigation for
the Web. Communications of the ACM, 40(3):73–76, March 1997.
[54] Gerard Salton. Automatic Text Processing – The Transformation, Analysis,
and Retrieval of Information by Computer. Addison–Wesley, Boston, MA,
USA, 1989.
[55] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Analysis of
recommendation algorithms for e-commerce. In Proceedings of the 2nd ACM
conference on Electronic commerce, pages 158–167. ACM Press, 2000.
[56] J. Ben Schafer, Joseph A. Konstan, and John Riedl. E-commerce recommendation
applications. DataMining and Knowledge Discovery, 5(1-2):115–153,
2001.
[57] Robert E. Schapire. The strength of weak learnability. Machine Learning,
5(2):197–227, June 1990.
[58] Robert E. Schapire. A brief introduction to boosting. In IJCAI ’99: Proceedings
of the Sixteenth International Joint Conference on Artificial Intelligence,
pages 1401–1406, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers
Inc.
[59] Robert E. Schapire and Yoram Singer. Improved boosting algorithms using
confidence-rated predictions. Machine Learning, 37(3):297–336, 1999.
[60] Barry Smyth and Paul Cotter. Personalized electronic program guides for
digital TV. AI Magazine, 22:54–61, 2001.
[61] Tong Sun and Andr’e Trudel. An implemented e-commerce shopping system
which makes personal recommendations. In Proceedings of the Internet and
Multimedia Systems and Applications, pages 58–62. IASTED/ACTA Press,
2002.
[62] Loren Terveen, Will Hill, Brian Amento, David McDonald, and Josh Creter.
PHOAKS: A system for sharing recommendations. Communications of the
ACM, 40(3):59–62, 1997.
[63] C. J. van Rijsbergen. Information Retrieval. Butterworths, 1979.
[64] Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer-
Verlag, 1995.
[65] Ting-Fan Wu, Chih-Jen Lin, and Ruby C. Weng. Probability estimates for
multi-class classification by pairwise coupling. The Journal of Machine
Learning Research, 5:975–1005, 2004.
[66] Rong Yan, Yan Liu, Rong Jin, and Alex Hauptmann. On predicting rare
classes with SVM ensembles in scene classification. In IEEE ICASSP2003,
volume 3, pages 21–24, 2003.
[67] Yiming Yang and Xin Liu. A re-examination of text categorization methods.
In SIGIR’99: Proceedings of the 22nd annual international ACM SIGIR con-
ference on Research and development in information retrieval, pages 42–49.
ACM Press, 1999.