臺灣博碩士論文加值系統

推薦系統(Recommendation Systems)現今在網際網路的商用行為中，經常被用來協助解決資訊過載(Information Overload)、推薦及預測服務，由過去學者的研究發現推薦系統中最常運用相似度量測(Similarity Measure)方法，來找出相似使用者或尋找具有相似行為之鄰居群(Neighborhood)，而這類相似度量測方法，多半利用使用者對產品的評價(rating)通常為顯性評分值(explicit rating)，來找出使用者間的相似度，藉由相似使用者的資訊對目標使用者做預測推薦，因此一個良好的相似度量測方法，往往是決定推薦成效的關鍵所在。
過去學者常用的相似度量測方法最常見的有皮爾森相關係數(Pearson Correlation Coefficient, PCC)、餘弦相似(Cosine Similarity, COS)、限制性皮爾森相關(Constrained Pearson’s Correlation, CPC)、修正餘弦相似(Adjusted Cosine, ACOS)、PIP相似性及歐幾里德距離(Euclidean Distance, ED)等，這些方法在計算使用者相似度時都會以顯性評分來做為計算的依據，但這些方法都有一些問題，例如：(1)未考慮到正向評分值在推薦時的重要性、(2)當資料量大時則計算相似度時間可能會過長、(3)當評分值與平均值相同時會發生除以零的問題等。
為了改善上述所提的問題，本研究提出一個新的以顯性評分為主之相似度量測方法(Rating-based Similarity Measure, RBSM)，本研究提出以快速的二元相似度量測方法為基礎，以正向評分值做為分析相似度之要項，藉由此方法快速找出具推薦價值之相似使用者及其推薦項目，本研究同時也考量使用者的評分特性，將實驗資料依使用者特性分群之後進行相似度計算，以期求得更準確的使用者相似度。利用本研究所提的顯性評分為主之相似度量測方法，經由初步實驗驗證能提升預測的效能，本研究的初步貢獻為經由實驗驗證本研究所提之方法有較高之準確度，同時可以縮短推薦計算之系統執行時間。

Recommendation systems (RS) are usually used for handling the information overloading, for recommendation, and for prediction, especially under current Internet environment. According to previous studies, the most commonly applied method for RS is the similarity measure. Similarity measure is usually used for finding similarity user or neighbors. To apply similarity measure, one of the commonly approach is to used the user rating, which is also call explicit rating for calculation. The rating difference or distance between the active user and the similar user is used for prediction. Therefore, a good similarity measure can affect the result of RS.
It is noticed that the similarity measures such as Pearson Correlation (PCC), Cosine Similarity (COS), Constrained Pearson’s Correlation (CPC), Adjusted Cosine (ACOS), PIP, or Euclidean Distance (ED) are highly used for finding similar users or similar items. These similarity measures usually rely on a user-item matrix in which the explicit ratings are used for calculation. The outcome of recommendation is usually made based on the information of the similar user (item). Hence, the similarity measure for finding the similar user (item) is critical for RS. But, if we examine the traditional similarity measurements, there exists some problems when applying to the RS. (1)They did not take the positive rating and the co-rating count into consideration. (2) When the rating value is equal to the average rating value, the similarity measure of PCC and COS will encounter the problem of division by zero problem, which will cause system failure. (3) The scalability problem is usually not discussed.
In order to handle these problems, this research proposes A Rating-based Similarity Measure (RBSM). Our method transforms the explicit-ratings into binary and considers both the positive-rating and co-rating count for finding the similar user. A simple similarity computation is proposed to find the neighborhood. For finding similar neighbor efficiently, users are divided, based on the co-rating amount, into three groups i.e., high, medium, and low. From the experiments, it is proved that our method has better outcome in recall, F1 value, and MAE value if compare to the traditional methods. Our results also show that the proposed method can handle the scalability problem.

目 錄
摘 要 I
Abstract III
致 謝 V
目 錄 VII
表目錄 X
圖目錄 XII
第一章、緒論 1
1.1導論 1
1.2研究目的 4
1.3研究範圍與限制 4
1.4論文架構 5
第二章、文獻探討 6
2.1相似度量測(Similarity Measure) 6
2.1.1皮爾森相關係數(Pearson Correlation Coefficient, PCC) 8
2.1.2餘弦相似(Cosine Similarity, COS) 9
2.1.3限制性皮爾森相關(Constrained Pearson''s Correlation, CPC) 11
2.1.4歐幾里德距離(Euclidean Distance, ED) 12
2.1.5修正餘弦相似(Adjusted Cosine, ACOS) 13
2.1.6 PIP相似性(Proximity-Impact-Popularity, PIP) 14
2.1.7相似度量測整理 19
2.2推薦系統(Recommendation Systems, RSs) 23
2.2.1推薦系統簡介 23
2.2.2協同過濾式推薦(Collaborative Filtering, CF) 23
2.2.2內容導向式推薦(Content-based Filtering, CB) 27
2.2.3混合式推薦(Mix Approach Recommendation) 27
2.3預測及推薦效能評估 28
第三章、研究方法 31
3.1以顯性評價為主之相似性推薦 31
3.2 研究步驟 32
3.2.1依顯性評分做預處理 33
3.2.2依顯性評分量(Rating count)做資料分群 39
3.2.3判斷目標使用者(Active user)歸屬族群 42
3.2.4依正向co-rating計算相似度 43
3.2.5預測推薦方法 44
第四章、實驗與驗證 45
4.1實驗資料來源與使用工具 45
4.2顯性評分資料預處理 46
4.3實驗步驟 47
4.3.1實驗資料分群 47
4.3.2挑選目標使用者 48
4.3.3使用者相似度計算 49
4.4實驗結果之相似度量測方法比較 49
4.4.1 User-based預測效能比較 51
4.4.2 User-based推薦效能比較 55
4.4.3 Item-based預測效能比較 59
4.4.4 Item-based推薦效能比較 61
4.4.5 相似度量測方法執行時間比較 62
第五章、結論與未來研究 65
5.1研究貢獻 65
5.2未來研究 67
參考文獻 68
 
表目錄
表1、 使用者評分矩陣(User-Item Matrix) 7
表2、 PCC_Sim(ux,uy)公式之符號說明 8
表3、 PCC評分均相同而產生之錯誤問題 9
表4、 COS_Sim(ux,uy)公式之符號說明 10
表5、 CPC_Sim(ux,uy)公式之符號說明 11
表6、 ED_Sim(ux,uy)公式之符號說明 12
表7、 ACOS_Sim(ux,uy)公式之符號說明 13
表8、 PIP各構面之計算求取方法 18
表9、 PIP相似性符號表說明 19
表10、相似度量測方法應用於User-based CF及Item-based CF的情形 20
表11、推薦系統相似度量測方法應用整理 21
表12、相似度量測方法在推薦系統運用之優缺點整理 22
表13、衡量指標變數之示意表 28
表14、MAE符號表 29
表15、原始矩陣資料表 33
表16、RBSM符號定義表 34
表17、使用者評分量(rc)及項目被評分次數(ic)之計算示意表 35
表18、經由 轉換後的二元值矩陣表 37
表19、轉換評分值為二元值偏好值之範例 37
表20、統計使用者正向評分量與負向評分量 38
表21、正向co-rating相似計算符號表 44
表22、直接預測示意表 44
表23、實驗工具介紹 46
表24、資料預處理後實驗資料說明 46
表25、資料分群後情形 48
表26、本研究實驗設計 50

 
圖目錄
圖1、 餘弦相似的問題示意 10
圖2、 Item-based共同評分(co-rating)表示圖 14
圖3、 鄰近度(Proximity) 15
圖4、 影響度(Impact) 16
圖5、 普及度(Popularity) 17
圖6、 Item-based與User-based相似度計算方向 25
圖7、 RBSM顯性評價之相似度計算步驟 32
圖8、 資料分群圖 41
圖9、 判斷目標使用者所歸屬族群之流程 42
圖10、分割實驗資料示意圖 47
圖11、三種類型的目標使用者 49
圖12、針對H群取TOP-1~ TOP-5使用者做預測之平均MAE 52
圖13、針對M群取TOP-1~ TOP-5使用者做預測之平均MAE 53
圖14、針對L群取TOP-1~ TOP-5使用者做預測之平均MAE 55
圖15、針對H群取TOP-1~ TOP-5使用者做推薦之平均F1指標 56
圖16、針對M群取TOP-1~TOP-5使用者做推薦之平均F1指標 58
圖17、針對L群取TOP-1~ TOP-5使用者做推薦之平均F1指標 58
圖18、以Item-based為主取TOP-1使用者做預測推薦之平均MAE 60
圖19、以Item-based為主取TOP-1使用者做預測推薦之平均F1指標 61
圖20、相似度量測方法之執行時間比較(sec) 62

[1]G. Adomavicius and Y. Kwon(2007), “New Recommendation Techniques for Multicriteria Rating Systems,” IEEE Intelligent Systems, vol. 22 , no. 3, pp. 48-55.
[2]H. J. Ahn(2008), “A New Similarity Measure for Collaborative Filtering to Alleviate the New User Cold-starting Problem,” International Journal of Information Sciences, vol. 178, no. 1, pp. 37-51.
[3]G. Boone(1998), “Concept Features in Re: Agent, an Intelligent Email Agent,” Proceedings of the Second International Conference on Autonomous Agents, pp. 10-13.
[4]M. Balabanovic and Y. Shoham(1997), “Fab: Content-based, Collaborative Recommendation,” Communications of the ACM, vol. 40, no.3, pp.66-72.
[5]J. S. Breese, D. Heckerman, and C. Kadie(1998), “Empirical Analysis of Predictive Algorithms for Collaborative Filtering,” Proceedings of The 14th Annual Conference on Uncertainty in Artificial Intelligence, pp. 43-52.
[6]L. Chen and K. Sycara(1998), “Webmate : A Personal Agent for Browsing and Searching,” Proceedings of The 2ed International Conference on Autonomous Agents, pp. 132-139.
[7]M. D’agostino, and V. Dardanoni(2009), “What’s so special about Euclidean distance?,” Social Choice and Welfare, vol. 33, no. 2, pp. 211-233.
[8]A. L. Deng, Y. Y. Zhu, and BL. A. Shi(2003), “Collaborative Filtering Recommendation Algorithm Based on Item Rating Prediction,” Journal of Software, vol. 14, no. 9, pp. 1621-1628.
[9]D. Goldberg, D. Nichols, B.M. Oki, and D. Terry(1992), “Using Collaborative Filtering to Weave an Information Tapestry,” Communications of the ACM, vol. 35, no. 12, pp. 61-70.
[10]N. Good, J. B. Schafer, J. Konstan, A. Borchers, B. Sarwar, J. Herlocker, and J. Riedl(1999), “Combining Collaborative Filtering with Personal Agents for Better Recommendations,” Proceedings of the 16th National Conference on Artificial Intelligence (AAAI-99), Menlo Park, CA, pp. 439–446.
[11]C. Hayes and P. Cunningham(1999), “Smart Radio - A Proposal,” Technical Report, TCD-CS-1999-24, Computer Science, Trinity College Dublin.
[12]C. Hayes and P. Cunningham(2001), “SmartRadio - Community Based Music Radio,” Journal of Knowledge Based Systems, vol. 14, no. 3-4, pp. 197-201.
[13]J. L. Herlocker, J. A. Konstan, J. Riedl(2002),“An Empirical Analysis of Design Choices in Neighborhood-Based Collaborative Filtering Algorithms,” Information Retrieval, vol. 5, no. 4, pp. 287-310.
[14]J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. Riedl(2004), “Evaluation Collaborative Filtering Recommender systems,” ACM Transaction on Information Systems, vol. 22, no. 1, pp. 5-53.
[15]W. Hill, L. Stead, M. Rosenstein, and G. Furnas(1995), “Recommending and Evaluating Choices in a Virtual Community of Use,” Proceedings of The SIGCHI Conference on Human Factors in Computing Systems, Denver, Colorado, pp. 194-201.
[16]T. Joachims, D. Freitag, and T. Mitchell(1997), “WebWatcher: A Tour Guide for the World Wide Web,” Proceedings of the International Joint Conference on Artificial Intelligence, pp. 770-777.
[17]T. Kamba, K. Bharat, and M. Albers(1995), “The Krakatoa Chronicle: An Interactive, Personalized Newspaper on the Web.” Proceedings Fourth International World Wide Web Conference, Boston, Mass, pp. 159-170.
[18]T. Kamba, H. Sakagami, and Y. Koseki(1997), “ANATAGONOMY: Personalized Newspaper on the World Wide Web,” International Journal of Human-Computer Studies, vol. 46, no 6, pp.789-803.
[19]J. A. Konstan, B. N. Miller, D. Maltz, J. L. Herlocker(1997), “GroupLens: Applying Collaborative Filtering to Usenet News,” Communications of the ACM, vol. 40, no.3, pp. 77-87.
[20]Matevž Kunaver, Tomaž Požrl, Matevž Poga cnik, and Jurij Tasi(2007), “Optimisation of Combined Collaborative Recommender Systems,” AEU - International Journal of Electronics and Communications, vol. 61, no. 7, pp. 433-443.
[21]K. Lang(1995), “NewsWeeder: Learning to Filter Netnews,” Proceedings of the Twelfth International Conference on Machine Learning, San Francisco, CA. Morgan Kaufman, pp. 331-339.
[22]H. Lieberman(1995), “Letizia: an Agent that Assists Web Browsing,” Proceedings International Conference on Artificial Intelligence, Montreal, Canada, pp. 924-929.
[23]H. Lieberman, N. van Dyke, and A. Vivacqua(1999), “Let’s Browse: a Collaborative Web Browsing Agent,” Proceedings of the International Conference on Intelligent User Interfaces, pp. 65-68.
[24]G. Lekakos, G. M. Giaglis(2006), “Improving the Prediction Accuracy of Recommendation Algorithms: Approaches Anchored on Human Factors,” Interacting with Computers, vol. 18, no. 3, pp. 410-431.
[25]J. S. Lee and S. Olafsson(2009), “Two-way Cooperative Prediction for Collaborative Filtering Recommendations,” Expert Systems with Applications, vol. 36, no.3, pp. 5353-5361.
[26]T. Q. Lee, Y. Park, and Y. T. Park(2008), “A Time-based Approach to Effective Recommender Systems Using Implicit Feedback,” Expert Systems with Applications, vol. 34, no. 4, pp. 3055-3062.
[27]Y. Li, L. Lu, L. Xuefeng(2005), “A Hybrid Collaborative Filtering Method for Multiple-interests and Multiple-content Recommendation in E-Commerce,” Expert Systems with Applications, vol. 28, no. 1, pp. 67-77.
[28]D. R. Liu, Y. Y. Shih(2005), “Hybrid Approaches to Product Recommendation Based on Customer Lifetime Value and Purchase Preferences,” Journal of Systems and Software, vol. 77, no. 2, pp. 181-191.
[29]D. Mladenic(1998), “Personal Webwatcher: Design and Implementation,” Technical Report, IJS-DP-7472, Department for Intelligent Systems, J. Stefan Institute, Ljubljana.
[30]A. Moukas and P. Maes(1998), “Amalthaea: An Evolving Multi-Agent Information Filtering and Discovery System for the WWW,” Autonomous Agents and Multi-Agent Systems, vol. 1, no. 1, pp. 58-88.
[31]D. W. Oard and G. Marchionini(1996), “A Conceptual Cramework for Text Filtering,” Technical Report, EE-TR-96-25, CAR-TR-830, CLIS-TR-96-02, CS-TR-3643, University of Maryland, College Park, pp. 1-32.
[32]M. Papagelis and D. Plexousakis(2005), “Qualitative Analysis of User-based and Item-based Prediction Algorithms for Recommendation Agents,” Engineering Applications of Artificial Intelligence, vol. 18, no. 7, pp. 781-789.
[33]M. Pazzani and D. Billsus(1997), “Learning and Revising User Profiles: The Identification of Interesting Web Sites,” Machine Learning, vol. 27, no.3, pp. 313-331.
[34]M. Pazzani, J. Muramatsu, and D. Billsus(1996), “Syskill & Webert: Identifying Interesting Web Sites,” Proceedings of the 13th National Conference on Artificial Intelligence, pp. 54-61.
[35]D. M. Pennock, , E. Horvitz, S. Lawrence, and L. Giles(2000), “Collaborative Filtering by Personality Diagnosis: A Hybrid Memory and Model-based approach,” Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, San Francisco, pp. 473-480.
[36]P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl(1994), “GroupLens : An Open Architecture for Collaborative Filtering of Net news,” Proceedings of the CSCW Conference, Chapel Hill, NC, pp.175-186.
[37]B. M. Sarwar, G. Karypis, J. A. Konstan, and J. Riedl(2000), “Analysis of Recommendation Algorithms for E-Commerce,” Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 158-167.
[38]B. M. Sarwar, G. Karypis, J. A. Konstan, and J. Riedl(2001), “Item-based Collaborative Filtering Recommendation Algorithms,” Proceedings of the 10th International Conference on World Wide Web, pp. 285-295.
[39]U. Shardanand and P. Maes(1995), “Social Information Filtering: Algorithms for Automating Word of Mouth,” ACM Conference on Computer Human Interaction (CHI), pp. 210-217.
[40]G. Salton and M. J. McGill(1983), Introduction to Modern Information Retrieval, McGraw-Hill, New York.
[41]I. Schwab, A. Kobsa, and I. Koychev(2001), “Learning User Interests through Positive Examples Using Content Analysis and Collaborative Filtering,” User Modeling and User-Adapted Interaction. To appear.
[42]B. Sheth(1994), “A Learning Approach to Personalized Information Filtering,” Master’s thesis, Massachusetts Institute of Technology, February.
[43]L. Terveent, W. Hill, B. AMENTO, D. Mcodonald, and J. Creter(1997), “PHOAKS: A System for Sharing Recommendations,” Communications of the ACM, vol. 40, pp. 59-62.
[44]C. J. Van Rijsbergen(1979), Information Retrieval, Second ed. Butter-worths, London.
[45]K. Wei, J. Huang, S. Fu(2007), “A Survey of E-Commerce Recommender System,” Proceedings of the International Conference on In Service Systems and Service Management, pp. 1-5.
[46]J. M. Yang and K. F. Li(2008), “Recommendation Based on Rational Inferences in Collaborative Filtering,” Knowledge-Based Systems, vol. 22, pp. 105-114.
[47]C. Zhai(2006), “A Study of Mixture Models for Collaborative Filtering,” Information Retrieval, vol. 9, no. 3, pp. 357-382.
[48]C. Zeng, C. X. Xing, and L. Z. Zhou(2003), “Similarity Measure and Instance Selection for Collaborative Filtering,” Proceedings of the 12th International Conference on World Wide Web, pp. 652-658.
[49]Customer Reviews, 2009, http://www.amazon.com/.
[50]Customer Product Reviews, 2009, http://www.walmart.com/.
[51]MovieLens Data Sets, 2006, http://www.grouplens.org/node/73.