臺灣博碩士論文加值系統

群眾分類法揭示著一種分散式、去中心化且協同的標記系統，不僅可降低文件認知的花成本，亦可快速適應常用字彙的變化。社群標記系統中的連結關係包含使用者產生的內容、對於文件的評比、以及對於文件的標記。一般傳統利用二分圖來描述使用者與文件之間的評比關係，加入標籤之後，可被視為在使用者與文件之間一種重要的介面，而這種介面以語義的方式描述文件。縱使社群標記網路上的推薦系統已被廣泛地探討，然而個人化行為對於推薦結果的影響仍尚待研究。
我們提出了一個推薦系統Supervised FolkRank，以重啟式隨機漫步(Random Walk with Restart)為基礎，對於重啟的機率、停滯的機率以及使用者與關鍵字的權重進行最佳化。本推薦系統關注所有文件的相關性而非僅止於二元地將文件分為相關與否，如此一來便可掌握整個文件集合就相關性的排序情況，以求得到最佳化效果。除此之外，透過分析每個使用者的最佳化參數向量而獲得這些向量的分佈。透過這些分佈，我們發現肇因於使用者行為的不同，而使得最佳化參數向量存在相當的分歧。從實驗中，比較其他監督式與非監督式的方法，我們所提出的推薦系統表現出較佳的正確率與取回率。

Folksonomy represents a distributed, decentralized, collaborative tagging system, which lowers the cognition cost and has a quick adaption to changes in vocabulary. Social tagging systems contain huge linking relations including user-generated content, ratings and annotations. Beyond the bipartite graphs that describe the ratings of items for users, annotation by tagging could be taken as an important interface to describe content semantically. Although the recommendation in social tagging networks has been studied extensively, the influence of personal behaviors on recommending results is still unexplored.
We propose a recommendation model, Supervised FolkRank, which uses a list-wise approach to formulate the objective function so that the ranking of all items could be considered. By analyzing the relation among restart probability, self-transition probability and the ratio of the target user to the selected query, we discover the divergence of the distribution of parameter vectors with the difference of users’ behaviors. To find the representatives to describe the distribution, clustering is used for analysis.
From our experiments on the LibraryThing social tagging graph, we show that our approach outperforms other recommendation systems including supervised and unsupervised ones. Finally, by showing that the results by the same model vary with different parameter vectors, we demonstrate the influence of the parameter vectors.

Abstract (Chinese) i
Abstract (English) ii
Acknowledgement ii
Table of Contents v
List of Figures ii
Chapter 1 Introduction 1
Chapter 2 Related Work 4
2.1 Recommendation Systems in Folksonomies………………………………....4
2.1.1 Collaborative Filtering…....…………………...……………..…………….4
2.2.2 Random Walk Model………………....………………..………...………...7
2.2 Machine Learning...........................................................................................10
2.2.1 The Pairwise Approach……………………………..………......…...10
2.2.2 The Listwise Approach……………….……….....….........................12
Chapter 3 Supervised FolkRank 14
3.1 Random Walk Model…………………………………………..……..….....14
3.2 The Optimization Problem……………………………………...……..……17
Chapter 4 Methodology 23
4.1 Data Preparation………………………………………………………...…..23
4.2 Measures……………………………………………………………….....…24
4.2.1 The Assumption for Relevance………………………………..24
4.2.2 Normalized Discounted Cumulative……………………………25
4.2.3 Precision and Recall….…………………………………………28
4.3 Evaluation……………………………………………………………..29
Chapter 5 Experiments 39
5.1 Distribution of optimized parameter vector………………………………...39
5.2 Comparison with other methods…………………………………………....46
5.3 The influence of transition matrix…………………………………………..52
Chapter 6 Conclusions and Future Work…………………………………54
Bibliography……………………………………………………………………56

[1] Al-Maskari, A., Sanderson, M. and Clough P. The Relationship between IR effectiveness measures and user satisfaction. In SIGIR ’07: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, p.p. 23-27, 2007.
[2] Backstrom, L. and Leskovec, J. Supervised Random Walks: Predicting and recommending links in social networks. In WSDM ’11: Proceedings of the 4th International Conference on Web Search and Web Data Mining, p.p. 635-644, 2011.
[3] Brin, S. and Page, L. The anatomy of a large-scale hypertextual web search engine. In Computer Networks and ISDN Systems, 30(1-7):107-117, April 1998.
[4] Broyden, C. G. The convergence of a class of double-rank minimization algorithms. In Journal of the institute of Mathematics and Its Applications 6, p.p. 76-90.
[5] Clements, M., Vries, A. P., and Reinders, M. I. J. The influence of personalization on tag query length in social media search. In Information Processing and Management, p.p. 403-412, 2010.
[6] Clements, M., Vries, A. P., and Reinders, M. I. J. The Task-Dependent Effect of Tags and Ratings on Social Media Access. In ACM Transactions on Information Systems, Vol. 28, No. 4, Article 21, Nov. 2010.
[7] Fletcher, R. A New Approach to variable metric algorithms. In Computer Journal 13(3), p.p. 317-322.
[8] Fletcher, Roger. Practical methods of optimization (2nd ed.), New York: John Wiley & Sons.
[9] Goldfarb, D. A family of variable metric updates derived by variational means. In Mathematics of Computation 24 (109), p.p. 23-26.
[10] Herlocker, J. L., Konstan, J. A., Borchers, A., and Riedl, J. An algorithmic framework for performing collaborative filtering. In SIGIR ’99: Proceedings of the 22nd annual international ACM SIGIR conference o Research and development in information retrieval, p.p. 230-247, 1999.
[11] Hotho, A., Jäschke, R., Schmitz, C. and Stumme, G. Information retrieval in folksonomies: search and ranking. In ESWC ’06: Proceedings of the 3rd European conference on The Semantic Web: research and applications, p.p. 411-426, 2006.
[12] Järvelin, K. and Kekäläinen, J. Cumulative gain-based evaluation of IR techniques. In ACM Transactions on Information Systems 20, p.p. 422-446, 2002.
[13] Konstas, I., Stathopoulos, V. and Jose, J. M. On social networks and collaborative recommendation. In SIGIR ’09: Proceedings of the 32th annual international ACM SIGIR conference on Research and development in information retrieval, p.p. 19-23, 2009.
[14] Liu, D. and Nocedal, J. On the limited memory bfgs method for large scale optimization. In Mathematical Programming, pp. 45:503-528, 1989.
[15] Liu, T.Y. Learning to Rank for Information Retrieval. Springer-Verlag Berlin Heidelberg.
[16] Marinho, L. B., Nanopoulos, A., Schmidt-Thieme, L., Jäschke, R., Hotho, A., Stumme, G. and Symeonidis, P. Social tagging recommendation systems. In Recommender System Handbook, p.p. 615-632, 2011
[17] .Milicevic, A. K., Nanopoulos, A. and Ivanovic, M. Social tagging in recommender systems: A survey of the state-of-art and possible extensions. In Artificial Intelligence Review, Volume 33 Issue 3, March 2010, p.p. 187-209, 2010.
[18] Parra, D. and Brusilovsky, P. Collaborative filtering for social tagging systems: An experiment with CiteULike. In RecSys ’09: Proceedings of the 2009 ACM conference on Recommender Systems, p.p. 237-240, 2009.
[19] Parra-Santander, D. and Brusilovsky, R. Improving collaborative filtering in social tagging systems for the recommendation of scientific articles. In IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, vol. 1, pp.136-142, 2010.
[20] Qin T., Liu, T.Y., Li, H. A general approximation framework for direct optimization of information retrieval measures. In Information Retrieval 13(4), p.p. 375-397, 2009.
[21] Rae, A., Sigurbjörnsson, B. and Zwol, R. Improving Tag Recommendation Using Social Networks. In RIAO’ 10: 9th Recherche d'Information Assistée par Ordinateur Conference Adaptivity, Personalization and Fusion of Heterogeneous Information, 2010.
[22] Salton, G. and Buckley, C. Term-weighting approaches in automatic text retrieval. In Information Processing and Management, 24(5), p.p. 513-523, 2010.
[23] Shanno, David F. Conditioning of quasi-Newton methods for function minimization. In Math. Comput. 24(111), p.p. 647-656.
[24] Taylor, M., Guiver, J., et al. Softrank: optimising non-smooth rank metrics. In WSDM ’08: Proceedings of the 1st International Conference on Web Search and Web Data Mining, p.p. 77-86, 2008.
[25] Valizadegan, H., Jin, R., Zhang, R. and Mao J. Learning to rank by optimizing NDCG measure. In Neural Information Processing Systems, 2010.
[26] Wu, X., Zhang, L. and Yu, Y. Exploring social annotations for the semantic web. In WWW ’06: Proceedings of the 15th international conference on World Wide Web, p.p. 417-426, 2006.
[27] Yan, L., Dodier, R., Mozer, M. and Wolniexicz, R. Optimizing classifier performance via an approximation to the Wilcoxon-Mann-Whitney statistic. In ICML ’03: The 20th International Conference on Machine Learning, p.p. 848-855, 2003.