Please use this identifier to cite or link to this item:
標題: 一個應用三角不等式的個人本體論相似度演算法
A Fast Similarity Algorithm for Personal Ontologies Using Triangle Inequality
作者: 王煥宇
Wang, Huan-Yu
關鍵字: Personal ontology
Collaborative filtering
Tree distance
Triangle inequality
出版社: 資訊科學與工程學系所
引用: 1. 中文部分 [1] 陳慧玲,<基植於個人本體論的圖書推薦系統-以中興大學圖書館為例>,中興大學資訊科學研究所,碩士論文,2007。 [2] 許正怡,<植基於個人本體論模型與合作式過濾技術之中文圖書館推薦系統>,中興大學資訊科學與工程研究所,碩士論文,2008。 [3] 廖宜恩、許雯絞、鄭名珊,<植基於個人本體論與合作式過濾的英文館藏推薦系統>,成功大學,二○○八數位生活科技研討會,2008.6.6。 [4] 何光國,<圖書館學理論基礎>,三民書局,1999。 [5] 鄭惠珍,<中國圖書分類法>之探討-以實例論證,大學圖書館3卷3期,1999。 [6] 賴永祥編訂、黃淵泉、林光美協編,「中國圖書分類法」,台北市:文華圖書館管理,2001。 [7] 阮明淑、溫達茂,<Ontology應用於知識組織之初探>,佛教圖書館館訊第32期,2002。 [8] 金芝,<知識工程中的本體論>,2001。 [9] 韓瑛馡、高國峰、廖宜恩。「圖書館網站個人化推薦系統研究」。台灣網際網路研討會,TANNET2005。2005。 2. 西文部分 [10] Shu-Chuan Liao, I-En Liao, Kuo-Fong Kao, Hui-Lin Chen, and Shu-O Huang, “PORE: A Personal Ontology Recommender System for Digital Library,” The Electronic Library, Vol. 27, No. 3, 2009. [11] I-En Liao, Shu-Chuan Liao, Kuo-Fong Kao, and Ine-Fei Harn, “A Personal Ontology Model for Library Recommendation System,” Proceedings of 9th International Conference on Asian Digital Library, S. Sugimoto et al. (Eds.), Lecture Notes in Computer Science, Vol. 4312, Springer-Verlag, November 2006, pp. 173-182. [12] P. Lakkaraju, S. Gauch, and M. Speretta, “Document Similarity Based on Concept Tree Distance,” HT’08, Pittsburgh, Pennsylvania, USA, June 19–21, 2008, pp. 127-131. [13] B. Chandrasekaran, J. R. Josephson, and V. R. Benjamins, “What are ontologies, and why do we need them?” IEEE Intelligent Systems, Vol. 14, Issue 1, January 1999, pp. 20-26. [14] R. Poli, “Ontology for knowledge organization,” R. Green(ed.), Knowledge organization and change, Indeks, Frankfurt, 1996, pp. 313-319. [15] S. William and T. Austin, “Ontology,” IEEE Intelligent systems, Jan/Feb, 1999, pp. 18-19. [16] M. Bunge, Treatise on Basic Philosophy: Vol.3: Ontology I: The Furniture of the World, Boston, MA: Reidel, 1977. [17] M. Uschold and M. Gruninger, “Ontologies: Principles, Methods, and Applications,” Knowledge Engineering Review, Vol. 11, No. 2, 1996, pp. 93-155. [18] T. Berners-Lee, J. Hendler, and O. Lassila, “The Semantic Web,” Scientific American, May 2001, pp. 35-43. [19] N. Guarino, “Formal Ontology and Information Systems,” Guarino, N.(ed.), Proceedings of the 1st International Conference on Formal Ontology in Information Systems, Trento, Italy, 6-8, IOS Press(amended version), June 6-8, 1998, pp. 3-15. [20] B. Chandrasekaran, J. R. Josephson, and V. R. Benjamins, “What are ontologies, and why do me need them ?” IEEE Intelligent systems, Jan/Feb, 1999, pp. 20-25. [21] T. R. Gruber, “Toward principles for the design of ontologies used for knowledge sharing,” International Journal Human-Computer Studies, August 23, 1993, pp. 907-928. [22] N. F. Noy and D. L. McGuinness, “A Guide to Creating Your First Ontology,” 2002, [23] N. Guarino, “Understanding, Building, And Using Ontologies,” International Journal Human-Computer Studies, Vol. 46, Issue 2-3, Feb./March 1997, pp. 293-310. [24] R. M. Bell, Y. Koren, and C. Volinsky, “Modeling Relationships at Multiple Scales to Improve Accuracy of Large Recommender Systems,” KDD’07, San Jose, California, USA, August 12–15, 2007, pp. 95-104. [25] N. J. Belkin and W. B. Croft, “Information filtering and information retrieval: two sides of the same coin?,” Communications of the ACM, Vol. 35, Issue 12, Special issue on information filtering, December 1992, pp.29-38. [26] P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl, “GroupLens: An Open Architecture for Collaborative Filtering of Netnews,” Proceedings of the 1994 ACM conference on Computer supported cooperative work, Chapel Hill, North Carolina, United States, October 22-26, 1994, pp. 175-186. [27] R. M. Bell and Y. Koren, “Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights,” IEEE International Conference on Data Mining, IEEE, 2007. [28] Y. Koren, “Factor in the Neighbors: Scalable and Accurate Collaborative Filtering,” 2008, [29] Y. Koren, “Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model,” Proceedings 14th ACM Int. Conference on Knowledge Discovery and Data Mining, ACM press, 2008. [30] Y. Koren, “Tutorial on Recent Progress in Collaborative Filtering,” RecSys’08, Lausanne, Switzerland, October 23-25, 2008. [31] D. Goldberg, D. Nichols, B. M. Oki, and D. Terry, “Using Collaborative Filtering to Weave an Information Tapestry,” Communications of the ACM, Vol. 35, Issue 12, December 1992, pp.61-70. [32] U. Shardanand and P. Maes, “Social Information Filtering: Algorithms for Automating ’Word of Mouth’,” Proceedings of the Conference on Human Factors in Computing Systems (CHI95), 1995, pp.210-217. [33] M. Deshpande and G. Karypis, “Item-Based Top-N Recommendation Algorithms,” ACM Transactions on Information Systems, Vol. 22, Issue 1, January 2004, pp. 144-176. [34] J. Wang, A. P. Vries, and M. J. T. Reinders, “Unifying User-based and Item-based Collaborative Filtering Approaches by Similarity Fusion,” Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, Washington, USA, August 6-11, 2006, pp. 501-508. [35] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Item-based Collaborative Filtering Recommendation Algorithms,” Proceedings of the 10th International World Wide Web Conference, Hong Kong, May 1-5, 2001, pp. 285-295. [36] J. L. Herlocker, J. A. Konstan, and J. Riedl, “Explaining collaborative filtering recommendations,” Proceedings of the ACM 2000 Conference on Computer Supported Cooperative Work, 2000, pp. 241-250. [37] J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl, “An algorithmic framework for performing collaborative filtering,” Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, 1999, pp. 230-237. [38] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Analysis of recommendation algorithms for E-Commerce,” Proceedings of the 2nd ACM conference on Electronic commerce, 2000, pp. 158-167. [39] G. Karypis, “Evaluation of item-based Top-N recommendation algorithms,” Proceedings of Conference on Information and Knowledge Management, 2001, pp. 247-254. [40] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Item-based collaborative filtering recommendation algorithms,” Proceedings of the 10th international conference on World Wide Web, 2001, pp. 285-295. [41] J. S. Breese, D. Heckerman, and C. Kadie, “Empirical analysis of predictive algorithms for collaborative filtering,” Proceedings of the 14th Annual conference on Uncertainty in Artificial Intelligence, 1998, pp. 43-52. [42] D. Billsus and M. J. Pazzani, “Learning collaborative information filters,” Proceedings of the 15th International Conference on Machine Learning, 1998, pp. 46-54. [43] B. M. Sarwar, G. Karypis, J. A. Konstan, and J. T. Riedl, “Application of dimensionality reduction in recommender system - a case study,” ACM WebKDD 2000 Web Mining for E-Commerce Workshop, 2000. [44] P. S. Yu, “Data mining and personalization technologies,” Proceedings of the 6th International Conference on Database Systems for Advanced Applications, 1999, pp. 6-13. [45] A. Ansari, S. Essegaier, and R Kohli, “Internet recommendation systems,” Journal of Marketing Research, Vol. 37, No. 3, 2000, pp. 363-375. [46] A. Mild and M. Natter, “Collaborative filtering or regression models for Internet recommendation systems?,” Journal of Targeting, Measurement and Analysis for Marketing, Vol. 10, No. 4, Jun 2002, pp. 304-313. [47] J. B. Schafer, J. A. Konstan, and J. Riedl, “E-commerce recommendation applications,” Journal of Data Mining and Knowledge Discovery, Vol. 5, No. 1, January 2001, pp. 115-153. [48] J. A. Konstan, B. N. Miller, D. Maltz, J. L. Herlocker, L. R. Gordon, and J. Riedl, “GroupLens : applying collaborative filtering to usenet news,” Communications of the ACM, Vol. 40, Issue 3, March 1997, pp. 77-87. [49] L. Terveen, W. Hill, B. Amento, D. McDonald, and J. Creter, “PHOAKS: a system for sharing recommendations,” Communications of the ACM, Vol. 40, Issue 3, March 1997, pp. 59-62. [50] J. Rucker and M. J. Polanco, “Siteseer: personalized navigation for the Web,” Communications of the ACM, Vol. 40 , Issue 3, March 1997, pp. 73-75. [51] H. Kautz, B. Selman, and M, Shah, “Referral Web: combining social networks and collaborative filtering,” Communications of the ACM, Vol. 40 , Issue 3, March 1997, pp. 63-65. [52] M. Popescu, J. M. Keller, and J. A. Mitchell, “Fuzzy Measures on the Gene Ontology for Gene Product Similarity,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 3, No. 3, July-September 2006, pp. 263-274. [53] P. Ganesan, H. Garcia-Molina, and J. Widom, “Exploiting Hierarchical Domain Structure to Compute Similarity,” ACM Transactions on Information Systems, Vol. 21, No. 1, January 2003, pp. 64–93. [54] Y. Guan, X. Wang, and Q. Wang, “A New Measurement of Systematic Similarity,” IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, Vol. 38, No. 4, July 2008, pp. 743-758.
摘要: 本論文以中興大學圖書館的館藏與讀者相關資料為基礎,延續本實驗室已開發的圖書館推薦系統(PORE: Personal Ontology Recommender System),著重在改善個人本體論相似度計算時間的研究。PORE系統可區分為以內容為基礎(content-based)的個人本體論模型推薦模式,及以結合合作式過濾(collaborative filtering)為基礎的推薦模式。由於合作式過濾需要比對所有使用者之間的相似度,而中興大學圖書館大約有3萬位使用者有借閱紀錄,及30多萬中英文館藏,其兩兩比對的計算,往往需要非常久的時間。 本論文在已開發的個人本體論合作式過濾推薦系統上,設計並實作了一個改善個人本體論相似度計算時間的演算法。因為個人本體論可看成一個樹狀的結構,所以此演算法採用樹距離(tree distance)的概念,重新定義了使用者的相似度,並運用了三角不等式(triangle inequality)的原理,省略了部份明顯不相似的使用者之間的相似度計算。從實驗結果得知,本研究的方法相較於暴力破解法,在計算分群後的本體論相似度之效能上有顯著的改善,且約可節省88%的使用者相似度比對的運算。
The Personal Ontology Recommender System (PORE) currently operated in the library of National Chung Hsing University is a recommender system developed by our research team. The system consists of content-based recommendation model based on personal ontology and collaborative filtering recommendation model. For collaborative filtering, the recommender system needs to compute the similarity between any two users. That will incur lots of computations because the library currently has more than thirty thousands of users and three hundred thousands of collections. The purpose of this thesis is to design an efficient algorithm for computing the similarity between two users. A personal ontology representing the favorites of a user in PORE is a tree structure. In this thesis, we define tree distance for measuring the dissimilarity between two users. We then propose an efficient algorithm for calculating ontology similarities using triangle inequality. The experimental results show that the proposed method can save up to 88% of comparisons compared to that of brute force algorithm.
其他識別: U0005-0208200902072900
Appears in Collections:資訊科學與工程學系所



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.