臺灣博碩士論文加值系統

線上資訊的急遽成長促進了個人化服務與推薦系統的發展。為了切合使用者不同的需求以減輕資訊負載的問題，推薦技術被相繼地提出以提供使用者更適切的服務。在眾多被提出的推薦技術中，以項目為基礎的協同過濾推薦方法(item-based collaborative filtering approach)是最成功且最常被採用的推薦技術。然而，這種方法卻會因為使用者偏好評價(preference rating)的缺乏而降低推薦品質，此外，當新進的使用者未給予足夠的喜好評價之前，此種方法卻缺乏對其做推薦的能力，此即個人化服務之稀疏問題。

在此篇論文中，我們提出了一種新的推薦技術用以解決上述的稀疏問題。我們藉由整合圖書資訊專家的階層化分類知識來加強書本之間的相似度計算，接著利用其與使用者偏好的關聯度對偏好評價表(preference rating table)的遺失值(missing value)做估算，最後以估算後的評價表作為協同過濾推薦方法的輸入評價表，以改善偏好稀疏的問題。藉由實驗的分析結果，證明我們所提出的推薦技術確實提升了推薦的數量和品質，改善了因稀疏的使用者偏好評價所造成的問題。

Exponential growth of data on the Web has stimulated the development of personalization. Among different recommendation technologies in personalization, item-based collaborative filtering approach is the most successful and widely adopted one to date. Despite the effectiveness, it still suffers from the problem of sparse preference ratings and lacks the ability to provide recommendations for new items and users. Item-based collaborative filtering approach recommends items based on users’ preference ratings and similarities between items derived from the preference rating table. That is, if the preference ratings are insufficient, the similarity calculation will be unreliable and deteriorate the recommendation quality.
In this study, we devise a methodology in recommender systems designed to alleviate the sparsity and cold-start problems. The expertized hierarchical classification information in Library Science is introduced and associated to enhance the similarity computation between books. The enhanced similarities and preference ratings are used to estimate the missing values of preference rating table. Then by feature-augmentation hybridization technique, the estimated preference rating table is taken as input to the item-based collaborative filtering approach to make recommendations. To prove the performance, our evaluation is conducted offline on existing data set. From the experimental results, our proposed recommendation system outperforms the classic item-based collaborative filtering approach in both recommendation quantities and qualities.

Abstract………………………………………………………………I Acknowledgements…………………………………………………III
Contents………………………………………………………………VI
List of Figures…………………………………………………VIII
List of Tables………………………………………………………IX
CHAPTER1 Introduction……………………………………………………1
1.1 Overview of Recommendation Techniques…………………… 3
1.1.1 Content-based Approach…………………………………………3
1.1.2 Collaborative Filtering Approach……………………………5
1.1.3 Hybrid Approach……………………………………………………7
1.2 The challenges of Collaborative Filtering Approaches………8
1.3 Motivations……………………………………………………………9
1.4 Goals……………………………………………………………………11
1.5 Outline of the Thesis……………………………………………12
CHAPTER2 Background ……………………………………………………13
2.1 Collaborative Filtering Approach……………………………14
2.2 The Sparsity Problem and Related Work……………………17
2.3 Domain Knowledge of Book Classification…………………20
CHAPTER3 Associating Expertized Information on Preference Estimation……23
3.1 Overview of the Proposed Recommendation system………26
3.2 Preference Rating Table Condenser……………………………28
3.2.1 Item Classification Retriever………………………………30
3.2.2 Classification Similarity Calculator……………………34
3.2.3 Preference Rating Estimator…………………………………38
3.3 Collaborative Filter………………………………………………39
3.3.1 Neighborhood Formation……………………………………………40
3.3.1.1 Item-Item Similarity Computation………………………41
3.3.1.2 Neighborhood Selection………………………………………44
3.3.2 Recommendation Generation……………………………………44
3.4 Characteristics of the Proposed Methodology……………45
3.5 Comparisons with Other Methods………………………………48
CHAPTER4 Experiments……………………………………………………50
4.1 Description of Data Set………………………………………………51
4.2 Evaluation Design……………………………………………………52
4.2.1 Predictive Accuracy………………………………………………53
4.2.2 Classification Accuracy…………………..………………………54
4.3 Experimental Setup I……………………………………………………56
4.4 Experimental Setup II……………………………………………………62
CHAPTER5 Discussion and Conclusion…………………………………66
5.1 Discussion……………………………………………………………66
5.2 Conclusion……………………………………………………………70
5.3 Further Work…………………………………………………………71
REFERENCES.............................................72

[1] P. Maes, “Agents that reduce work and information overload,”
Communications of the ACM, vol. 37, issue 7, pp. 30-40, July
1994.
[2] M. Montebello, “Information Overload--An IR Problem?,” SPIRE (
String Processing and Information Retrieval: A South American
Symposium), vol. 00, p. 0065, 1998.
[3] Y. Yang, J. Z. Li, “Interest-based Recommendation in Digital
Library,” Journal of Computer Science, vol. 1, issue 1, pp. 40-
46, 2005.
[4] M. Rigou, S. Sirmakessis, A. Tsakalidis, “A Computational
Geometry Approach to Web Personalization,” In Proceedings of the
IEEE International Conference on E-Commerce Technology
(CEC’04), pp. 377-380, 2004.
[5] M. Garden, G. Dudek, “Semantic Feedback for Hybrid
Recommendations in Recommendz,” In Proceedings of the IEEE
International Conference on e-Technology, e-Commerce and e-
Service (EEE’05), pp. 754-759, 2005.
[6] Recommendz, the Movie Recommender,
available at http://recommendz.mcgill.edu:8080/prototype.
[7] CDnow, personalized recommendation on CDs,
available at http://www.CDnow.com.
[8] P. Resnick, N. Iacovou, M. Suchak, P. Bergstorm, J.
Riedl, “GroupLens: An Open Architecture for Collaborative
Filtering of Netnews,” In Proceedings of ACM Conference on
Computer Supported Cooperative Work, pp. 175-186, 1994.
[9] E. Rich, “User Modeling via Stereotypes,” Cognitive Science,
vol. 3, no. 4, pp. 329-354, 1979.
[10] G. Salton, Automatic Text Processing, Addison-Wesley, New York,
1989.
[11] E. Vozalis, Margaritis K. G.., “Analysis of Recommender
Systems’ Algorithms,” In Proceedings of the 6th Hellenic-
European Conference on Computer Mathematics and its
Applications (HERCMA03), 2003.
[12] G. Adomavicius, A.Tuzhilin, “Recommendation Technologies:
Survey of Current Methods and Possible Extensions,” working
paper, Stern School of Business,New York University, available
at http://www.stern.nyu.edu/oldciio/WorkOnline/2004/CeDER-04-
01.pdf.
[13] G. Adomavicius, A.Tuzhilin, “Toward the Next Generation of
Recommender Systems: A Survey of the State-of-the-Art and
Possible Extensions,” IEEE Transactions on Knowledge and Data
Engineering, vol. 17, no. 6, pp. 734-749, 2005.
[14] N.J. Belkin, W.B. Croft, “Retrieval Techniques,” In Annual
Review of Information Science and Technology 22, pp. 109-145,
New York: Elsevier & ASIS, 1987.
[15] D. Mladenic, “Text-learning and related intelligent agents: a
survey,” IEEE Intelligent Systems, vol. 14, no. 4, pp. 44-54,
1999.
[16] N. Good, J. Schafer, J. Konstan, and A. Borchers, “Combining
collaborative filtering with personal agents for better
recommendations,“ In Proceedings of the 16th National
Conference on Artificial Intelligence, pp. 439-446, 1999.
[17] M. Balabanovic, Y. Shoham, “FAB: Content-based, collaborative
recommendation,” Communications of the ACM, vol. 40, no. 3,
pp.67-72, 1997.
[18] R. J. Mooney, L. Roy, “Content-based book recommending using
learning for text categorization,” In Proceedings of the 5th
ACM Conference on Digital Libraries, pp.195-204, 2000.
[19] M. Kwak, D. S. Cho, “Collaborative Filtering with Automatic
Rating for Recommendation,” In Proceeding of 2001 IEEE
International Symposium on Industrial Electronics, pp. 625-628,
2001.
[20] M. J. Pazzani, J. Muramatsu; D. Billsus, “Syskill & Webert:
Identifying interesting Web Sites,” In Proceedings of the 13th
National Conference on Artificial Intelligence (AAAI-96),
pp.54 – 61, 1996.
[21] D. Mladenic, “Personal WebWatcher: Design and Implementation,”
Technical Report: IJS-DP-7472, Dept. of Computer Science, J.
Stefan Inst., 1996, available at
http://www.ijs.si/DunjaMladenic/home.html.
[22] R. Barrett; P. Maglio; D. Kellem “How to Personalize the Web,”
In Proceedings of the 6th ACM Conference on Human Factors in
Computing Systems, pp. 75 – 82, 1997.
[23] M. Pazzani; D. Billsus, “Learning and Revising User Profiles:
The Identification of Interesting Web Sites,” Machine Learning
27, Kluwer Academic Publishers, pp. 313-331, 1997.
[24] P. Resnick; N. Iacovou; M. Suchak; P. Bergstrom; J.
Riedl, “GroupLens: An Open Architecture for Collaborative
Filtering of Netnews,” In Proceedings of the ACM Conference on
Computer Supported Cooperative Work, pp. 175-186, 1994.
[25] U. Shardanand, P. Maes, “Social information filtering:
Algorithms for automating `word of mouth',” In Proceedings of
the ACM SIGCHI Conference on Human Factors in Computing
Systems, pp. 210-217, 1995.
[26] B. Sarwar, G. Karypis, J. Konstan, J. Reidl, “Analysis of
recommendation algorithms for e-commerce,” In Proceedings of
the ACM Conference on Electronic Commerce, pp. 158-167, 2000.
[27] D. Billsus, M. J. Pazzani, “Learning Collaborative Information
Filters,” In Proceedings of the 15th International Conference
on Machine Learning, pp. 46-54, 1998.
[28] A. Gokhale, M. Claypool, “Thresholds for More Accurate
Collaborative Filtering,” In Proceedings of International
Conference on Artificial Intelligence and Soft Computing, 1999.
[29] L. Terveen, W. Hill, B. Amento, D. McDonald, J.
Creter, “PHOAKS: A System for Sharing Recommendations,”
Communications of ACM, vol. 40, no. 3, pp. 59-62, 1997.
[30] J. Canny, “Collaborative filtering with privacy via factor
analysis,” In Proceedings of the 25th Annual International ACM
SIGIR Conference on Research and development in Information
Retrieval, pp. 238-245, 2002.
[31] H. Polat, W. Du, “Privacy-Preserving Collaborative Filtering
using Randomized Perturbation Techniques,” In Proceedings of
the 3rd IEEE International Conference on Data Mining (ICDM),
pp.625-628, 2003.
[32] H. Polat, W. Du, “Privacy-Preserving Collaborative
Filtering,” Accepted by the International Journal of Electronic
Commerce (IJEC), 2005.
[33] C-N Ziegler, S.M. McNee, J.A. Konstan, G. Lausen, “Improving
Recommendation Lists Through Topic Diversification,” In
Proceedings of the 14th International World Wide Web Conference
(WWW2005),pp. 22-32, 2005.
[34] J. A. Konstan, B. N. Miller, D. Maltz, J. L.
Herlocker, “GroupLens: Applying Collaborative Filtering to
Usenet News,” Communications of ACM, vol. 40, no. 3, , pp. 77-
87, 1997.
[35] J. Rucker, M. J. Polanco, “Siteseer: Personalized Navigation
for the Web,” Communications of ACM, vol. 40, no. 3, pp. 73-76,
1997.
[36] J. Kautz, B. Selman, M. Shah, “Referral Web: Combing Social
Networks and Collaborative Filtering,” Communications of ACM,
vol. 40, no. 3, pp. 63-65, 1997.
[37] X. Fu, J. Budzik, J. K. Hammond,“Mining Navigation History for
Recommendation,” In Proceedings of the International Conference
on Intelligent User Interfaces, pp. 106-112, 2000.
[38] C. Basu, H. Hirsh, and W. Cohen, ”Recommendation as
Classification: Combining Social and Content-Based Information in Recommendation,” In Proceedings of the 15th National /10th Conference on Artificial Intelligence /Innovative Applications of Artificial Intelligence, pp. 714-720,1998.
[39] R. Burke, “Hybrid Recommender Systems: Survey and Experiments,” In User Modeling and User-Adapted Interaction, vol. 12, pp. 331-370, 2002.
[40] M. Pazzani, “A framework for collaborative, content-based and demographic filtering,” Artificial Intelligence Review, 13 (5-6),pp.393-408, 1999.
[41] Special issue on Personalization System, Communications of the ACM, vol. 43, no. 8, August 2000.

[42] R. Armstrong, D. Freitag, T. Joachims, T. Mitchell, “Webwatcher: A Learning Apprentice for the World Wide Web,” AAAI Spring Symposium on Information Gathering from Heterogeneous Distributed Environments, March 1995.
[43] M. Balabanovic, Y. Shoham, “Learning Information Retrieval Agents: Experiments with Automated Web Browsing,” AAAI 1995 Spring Symposium Information Gathering from Heterogeneous, Distributed Environments, pp. 13-18, 1995.
[44] S. E. Middleton, H. Alani, N. R. Shadbolt, D. C. De Roure, ”Exploiting Synergy Between Ontologies and Recommender Systems,” In Proceedings of ACM 11th International World Wide Web Conference (WWW2002)/ Sementic Web Workshop 2002, 2002.
[45] A. I. Schein, A. Popescul, L. H. Ungar, D. M. Pennock, “Methods and metrics for cold-start recommendations,” In Proceedings of the 25th Conference on Research and Development in Information Retrieval (SIGIR 2002),pp. 253-260, 2002.
[46] S. Chakrabarti, B. Dom, R. Agrawal, P. Raghavan, “Scalable Feature Selection, Classification and Signature Generation for Organizing Large Text Databases into Hierarchical Topic Taxonomies,“ VLDB Journal (Very Large Data Bases), vol. 7, no. 3, pp.163-178, 1998.
[47] M. Eirinaki, M. Vazirgiannis, I. Varlamis, “SEWeP: Using Site Semantics and a Taxonomy to Enhance the Web Personalization Process,” In Proceedings of the 9th SIGKDD Conference, 2003.
[48] W. Hill, L. Stead, M. Rosenstein, G. Furnas, “Recommending and evaluating choices in a virtual community of use,” In Proceedings of the ACM CHI’95 Conference on Human Factors in Computing Systems, pp.194-201, 1995.
[49] C. J. Tseng, Cluster-based Collaborative Filtering Recommendation Approach, Master Thesis, National Sun Yat-Sen University, 2003.
[50] B. M. Sarwar, G. Karypis, J. A. Konstan, J. Riedl, “Item-based collaborative filtering
recommendation algorithms,” In Proceeding of the 10th International World Wide Web Conference (WWW10), pp. 285-295, 2001.
[51] J. Herlocker, J. A., Konstan, J. Riedl, “Empirical Analysis of Design Choices in
Neighborhood-Based Collaborative Filtering Algorithms,” Journal of Information Retrieval, vol. 5, issue 4, pp. 287-310, 2002.
[52] J. S. Breese, D. Heckerman, C. Kadie, “Empirical Analysis of Predictive Algorithms for Collaborative Filtering,” In Proceeding of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI), pp. 43-52, 1998.
[53] B. M. Sarwar, J. A. Konstan, A. Borchers, J. Herlocker, B. Miller, J. Riedl, “Using Filtering Agents to Improve Prediction Quality in the GroupLens Research Collaborative Filtering System,” Computer Supported Cooperative Work, 1998.
[54] J. Herlocker, J. Konstan, A. Borchers, J. Riedl, “An Algorithmic Framework for Performing Collaborative Filtering,” In Proceedings of the 22nd Conference on Research and Development in Information Retrieval(SIGIR’99), pp. 230-237, Aug. 1999.
[55] Z. Huang, H. C. Chen, D. Zeng, “Applying Associative Retrieval Techniques to Alleviate the Sparsity Problem in Collaborative Filtering,” ACM Transactions on Information Systems, vol. 22, no.1, pp. 116-142, 2004.


[56] M. Papagelis, D. Plexousakis, T. Kutsuras, “Alleviating the Sparsity Problem of Collaborative Filtering using Trust Inferences,” In Proceedings of I-Trust, pp.224-239, 2005.
[57] M. Papagelis, D. Plexousakis, I. Rousidis, E. Theoharopoulos, “Qualitative Analysis of User-based and Item-based Prediction Algorithms for Recommendation Systems,” In Proceedings of the 3rd Hellenic Data Management Symposium (HDMS’04), 2004.
[58] K. Goldberg, T. Roeder, D. Gupta, C. Perkins, “Eigentaste: A Constant Time Collaborative Filtering Algorithm,” Journal of Information Retrieval, vol. 4, no. 2, pp. 133-151, 2001.
[59] B. Sarwar, G. Karypis, J. Konstan, J. Riedl, “Application of Dimensionality Reduction in Recommender Systems: A Case Study,” In Proceedings of the WebKDD Workshop at the ACM SIGKKD, 2000.
[60] C. C. Aggarwal, J. L. Wolf, K-L Wu, P. S. Yu,”Horting Hatches an Egg: A New Graph-Theoretic Approach to Collaborative Filtering,” In Proceedings of the 5th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’99), pp. 201-212, 1999.
[61] Z. Huang, W.Y Chung, T-H Ong, H. Chen, “A Graph-based Recommender System for Digital Library,” In Proceedings Joint Conference on Digital Libraries, pp. 65-73, July 2002.
[62] S. C. Hu, H. T. Wu, Introduction of Library Science, Hahn-Me, Taipei, 1991.


[63] Book-Crossing Data Set, available at
http://www.informatik.uni-freiburg.de/~cziegler/BX/.
[64] M. K. Condliff, D. D. Lewis, D. Madigan, C. Posse, “Bayesian Mixed-Effects Models for Recommender Systems,” In Proceedings of the ACM SIGIR Workshop on Recommender System, 1999.
[65] H. Liu, L. Yu, “Toward Integrating Feature Selection Algorithms for Classification and Clustering,” IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 3, pp. 1-12, 2005.
[66] D. Pavlov, D. Pennock, “A Maximum Entropy Approach to Collaborative Filtering in Dynamic, Sparse, High-Dimensional Domains,“ In Advances in Neural Information Processing(NIPS-02), vol. 15, 2002.
[67] Book-Crossing Community, available at http://www.bookcrossing.com/.
[68] Library of Congress Online Catalog, available at http://catalog.loc.gov/.
[69] About the Library of Congress, available at http://www.loc.gov/about/.
[70] J. Herlocker, J. Konstan, L. Terveen, J. Riedl, “Evaluating Collaborative Filtering Recommender Systems,” ACM Transactions on Information Systems, vol. 22, no.1, pp. 5-53, January 2004.
[71] Sung Ho Ha, “Helping online customers decide through Web personalization,” In IEEE Intelligent Systems, vol. 17, no.6, pp. 34-43, 2002.