臺灣博碩士論文加值系統

在現今的電子商務(Electronic Commerce)環境中，協同過濾式推薦技術(Collaborative Filtering Recommendation, CF)經常被建構成推薦系統(Recommendation System, RS)，且運用層面相當廣泛，如電影、書籍等推薦運用。協同過濾式推薦之方法，旨在找出與目標使用者(Active User)有類似偏好(Preference)的相似使用者(Similar User)，利用相似使用者的已知評分(Given Rating)記錄，推測目標使用者對尚未評分的項目是否具有偏好，再找出可能偏好的項目，推薦給目標使用者。為了能找出與目標使用者偏好最相近的相似使用者，過去有學者提出許多的相似度量測(Similarity Measure)及挑選相似使用者的方法，這些方法都能評估使用者之間的關係，並找出偏好相似的使用者。然而，隨著推薦系統運作時間的增加，必須處理的資料也日益漸增，導致傳統相似度量測產生計算耗時的問題，因此將對線上的即時推薦效能造成極大的阻礙。
本研究為了強化協同過濾式推薦的推薦效能(Performance)，提出偏好導向相似性量測(Preference Based Similarity Measure, PBSM)的協同過濾式推薦方法。利用使用者對項目的評分，以二元值區別是否對項目具有偏好，同時針對推薦上的考量，篩選出對推薦結果具有影響力的正向評分使用者，再利用反互斥或邏輯運算(Exclusive-NOR, XNOR)，計算使用者的偏好一致性(Conformity)。
透過本研究的實驗證明，偏好導向相似性量測的協同過濾式推薦與傳統相似度量測之協同過濾式推薦互相比較，偏好導向相似性量測不但改善傳統相似度量測的計算複雜度問題，且能保有預測結果的準確性(Accuracy)。在推薦方面，偏好導向相似性量測的推薦成功率亦優於傳統相似度量測，故能同時提昇協同過濾式推薦之推薦效能，增加推薦準確度。此外，由於計算時間的降低，更能符合線上即時推薦的需求。

Collaborative Filtering (CF) recommendation technique is frequently used for building Recommendation Systems (RS). This technique exists for many applications such as recommendations for movies, books, music, and products. The reason of applying CF for recommendations is to find users with similar preferences such that the group of users can be utilized for prediction and the active user’s unrated item is, then, predicted.
To find similar users, the similarity measure must be employed. In the past, many similarity measures are proposed such as Pearson’s Correlation (PCC), Euclidean Distance (ED), Cosine Similarity (COS), or Constrained Pearson’s Correlation (CPC). These methods compute the correlation, distance, or direction for each pair of user’s information. If the number of user is large, the computation will take time. Moreover, as we all know, in e-commerce environment, user information and the amount of users will naturally increase with time. Therefore, a good on-line CF process becomes difficult if the user database grows rapidly.
To improve the performance of CF recommendations, this research proposes the Preference Based Similarity Measure (PBSM) for CF recommendation. The PBSM can distinguish a user’s preferences based on user ratings and can identify the conformity between users’ preferences. This is done by changing user ratings into binary values to represent user’s positive preferences. The proposed method uses the exclusive-NOR (XNOR), the logical operation, to compare the conformity between users’ preferences. Users that have high conformity with the active user are determined to be similar users. The preference of these similar users will be applied for recommendation.
To prove the proposed PBSM can generate better performance, the experiments are designed to allow comparison with traditional similarity measures for CF recommendation. Our experimental results indicate that the proposed PBSM has better prediction outcomes in terms of MAE measure. Also, the PBSM achieves a successful rate which is higher than that of traditional similarity measures. The study proves that the proposed PBSM can enhance the performance of recommendations, and is moreover simple to calculate, which in turn allows for more efficiency than traditional methods.

目 錄
摘 要 ...................................................................................................................... I
Abstract ................................................................................................................ III
誌謝 ....................................................................................................................... V
目 錄 .................................................................................................................. VII
表 目 錄 ............................................................................................................... X
圖 目 錄 ........................................................................................................... XIII
第一章 緒論.......................................................................................................... 1
1.1 導論 .................................................................................................................. 1
1.2 研究目的.......................................................................................................... 6
1.3 研究範圍.......................................................................................................... 6
1.4 論文架構.......................................................................................................... 7
第二章 文獻探討 ............................................................................................... 10
2.1 推薦系統........................................................................................................ 10
2.2 協同過濾式推薦 ........................................................................................... 16
2.3 相似度量測 ................................................................................................... 22
2.3.1 皮爾森相關係數 ........................................................................................ 25
2.3.2 限制性皮爾森相關 .................................................................................... 28
2.3.3 餘弦相似定理 ............................................................................................ 30
2.3.4 調整性餘弦相似定理 ................................................................................ 32
2.3.5 歐幾里德距離 ............................................................................................ 35
2.4 預測及推薦效能評估 ................................................................................... 38
2.4.1 鄰居群範圍設定 ........................................................................................ 38
2.4.2 預測評分 .................................................................................................... 39
2.4.3 預測評估 .................................................................................................... 41
2.4.4 推薦評估 .................................................................................................... 42
第三章 研究方法 ............................................................................................... 44
3.1 偏好導向相似性量測之協同過濾式推薦 ................................................... 46
3.2 研究步驟及流程 ........................................................................................... 49
3.2.1 資料預處理 ................................................................................................ 51
3.2.2 使用者偏好判斷 ........................................................................................ 52
3.2.3 正向評分與推薦影響 ................................................................................ 55
3.2.4 偏好導向相似性測量 ................................................................................ 58
3.2.5 使用者偏好預測及協同過濾式推薦 ........................................................ 62
第四章 實驗結果與分析 ................................................................................... 64
4.1 實驗資料........................................................................................................ 65
4.2 實驗工具........................................................................................................ 66
4.3 實驗流程設計 ............................................................................................... 67
4.4 實驗評估........................................................................................................ 71
第五章 結論與未來研究 ................................................................................... 84
5.1 結論 ................................................................................................................ 84
5.2 未來研究方向 ............................................................................................... 85
參考文獻 .............................................................................................................. 87

表 目 錄
表2.1 內容導向式推薦之優缺點比較 ............................................................. 12
表2.2 推薦系統應用之相似度整理 ................................................................. 15
表2.3 協同過濾式推薦相關應用 ..................................................................... 17
表2.4 使用者評分之冷起始問題(本研究舉例) ............................................... 21
表2.5 協同過濾式推薦之優缺點比較 ............................................................. 22
表2.6 使用者項目矩陣(本研究舉例) ............................................................... 23
表2.7 皮爾森相關係數之變數及定義 ............................................................. 25
表2.8 稀疏的使用者項目矩陣 ......................................................................... 26
表2.9 皮爾森相關係數之評分數量問題(本研究舉例) .................................. 27
表2.10 皮爾森相關係數之使用者評分相同的問題(本研究舉例) ................ 27
表2.11 皮爾森相關係數之使用者的評分趨勢問題(本研究舉例) ................. 28
表2.12 限制性皮爾森相關之變數及定義 ....................................................... 29
表2.13 限制性皮爾森相關之評分與尺度中位數問題(本研究舉例) ............ 30
表2.14 餘弦相似定理之變數及定義 ............................................................... 31
表2.15 餘弦相似定理之共同評分數量問題(本研究舉例) ............................ 31
表2.16 餘弦相似定理之共同評分相同問題(本研究舉例) ............................ 32
表2.17 調整性餘弦相似定理之變數及定義 ................................................... 33
表2.18 調整性餘弦相似定理之資料稀疏性問題(本研究舉例) .................... 34
表2.19 調整性餘弦相似定理之評分相等問題(本研究舉例) ........................ 34
表2.20 歐幾里德距離之變數及定義 ............................................................... 35
表2.21 歐幾里德距離之無法判斷評分高低差異的問題 ............................... 36
表2.22 相似度量測整理比較 ........................................................................... 37
表2.23 離均差之變數及定義 ........................................................................... 39
表2.24 Z-score 之變數及定義 ........................................................................... 40
表2.25 平均絕對誤差之變數及定義 ............................................................... 41
表2.26 推薦系統與使用者選擇之發生情況 ................................................... 43
表2.27 推薦成功率之變數及定義 ................................................................... 43
表3.1 使用者評分之特性(本研究舉例) ........................................................... 48
表3.2 使用者項目矩陣(User-item Matrix) ....................................................... 52
表3.3 使用者項目矩陣之相關變數及定義 ..................................................... 52
表3.4 整體平均評分之相關變數及定義 ......................................................... 53
表3.5 使用者評分轉換二元值之相關變數及定義 ......................................... 55
表3.6 計算使用者正向評分數量之相關變數及定義 ..................................... 57
表3.7 偏好二元值矩陣之正向評分數量 ......................................................... 57
表3.8 判斷偏好一致性結果 ............................................................................. 59
表3.9 偏好導向相似性量測之相關變數及定義 ............................................. 60
表3.10 目標使用者與候選集合裡的使用者 ................................................... 61
表3.11 目標使用者與候選集合使用者的二元值比對 ................................... 61
表3.12 預測評分之相關變數及定義 ............................................................... 63
表4.1 MovieLens 使用者評分資料(部分列舉) ................................................ 65
表4.2 MovieLens 使用者評分轉換成使用者項目矩陣(部分列舉) ................ 66
表4.3 本研究實驗工具及功能說明 ................................................................. 67
表4.4 使用者資料子集的相似使用者數量(單位：人) .................................. 68
表4.5 實驗相關變數之設定及實驗資料之整理 ............................................. 71
表4.6 整體平均評分(GAR)計算結果 .............................................................. 72
表4.7 使用者項目矩陣轉換成偏好二元值矩陣(部分列舉) .......................... 72

圖 目 錄
圖1.1 協同過濾式推薦流程圖 (資料來源：[29]) ............................................ 3
圖1.2 論文架構圖 ............................................................................................... 9
圖3.1 偏好導向相似性量測(PBSM)之協同過濾式推薦系統 ........................ 45
圖3.2 篩選正向評分使用者之示意圖 ............................................................. 48
圖3.3 偏好導向相似性量測(PBSM)之協同過濾式推薦步驟流程圖 ............ 50
圖3.4 資料預處理流程圖 ................................................................................. 51
圖3.5 使用者項目矩陣轉換為偏好二元值矩陣之流程圖 ............................. 53
圖3.6 使用者項目矩陣轉換成偏好二元值矩陣之舉例 ................................. 55
圖3.7 偏好二元值矩陣篩選正向評分使用者之流程圖 ................................. 56
圖4.1 訓練集合及測試集合示意圖 ................................................................. 68
圖4.2 正向評分門檻值之MAE 比較 .............................................................. 73
圖4.3 正向評分門檻值之SR 比較 .................................................................. 74
圖4.4 離均差預測之MAE 比較(鄰居群比例5%) ......................................... 75
圖4.5 離均差預測之SR 比較(鄰居群比例5%) ............................................. 75
圖4.6 離均差預測之MAE 比較(鄰居群比例15%) ....................................... 76
圖4.7 離均差預測之SR 比較(鄰居群比例15%) ........................................... 76
圖4.8 Z-score 預測之MAE 比較(鄰居群比例15%) ....................................... 77
圖4.9 Z-score 預測之SR 比較(鄰居群比例15%) ........................................... 78
圖4.10 已知評分數量之MAE 比較(使用者數量ML100)............................. 79
圖4.11 已知評分數量之SR 比較(使用者數量ML100) ................................. 79
圖4.12 已知評分數量之MAE 比較(使用者數量ML500)............................. 80
圖4.13 已知評分數量之SR 比較(使用者數量ML500)................................. 81
圖4.14 相似度量測計算之執行時間 ............................................................... 82
圖4.15 預測過程之執行時間 ........................................................................... 83

[1]H. J. Ahn (2008), “A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem,” Information Sciences, Vol. 178, No. 1, pp. 37-51.
[2]M. Y. H. Al-Shamri and K. K. Bharadwaj (2008), “Fuzzy-genetic approach to recommender systems based on a novel hybrid user model,” Expert Systems with Applications, Vol. 35, No. 3, pp. 1386-1399.
[3]BookCrossing. (2010), Available at: http://www.informatik.uni-freiburg.de/~cziegler/BX/.
[4]J. Breese, D. Heckerman, and C. Kadie (1998), "Empirical analysis of predictive algorithms for collaborative filtering," Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, pp. 43-52.
[5]R. Burke (2002), “Hybrid recommender systems: Survey and experiments,” User Modeling and User-Adapted Interaction, Vol. 12, No. 4, pp. 331-370.
[6]Y. L. Chen and L. C. Cheng (2008), “A novel collaborative filtering approach for recommending ranked items,” Expert Systems with Applications, Vol. 34, No. 4, pp. 2396-2405.
[7]D. Goldberg, D. Nichols, B. M. Oki, and D. Terry (1992), “Using collaborative filtering to weave an Information tapestry,” Commun. ACM, Vol. 35, No. 12, pp. 61-70.
[8]K. Goldberg, T. Roeder, D. Gupta, and C. Perkins (2001), “Eigentaste: A constant time collaborative filtering algorithm,” Information Retrieval, Vol. 4, No. 2, pp. 133-151.
[9]GroupLens Research. (2010), Available at: http://www.grouplens.org/node/73.
[10]D. Gupta, M. Digiovanni, H. Narita, and K. Goldberg (1999), “Jester 2.0: Evaluation of an new linear time collaborative filtering algorithm,” Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 291-292.
[11]J. Herlocker, J. A. Konstan, and J. Riedl (2002), “An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms,” Information Retrieval, Vol. 5, No. 4, pp. 287-310.
[12]J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl (1999), “An algorithmic framework for performing collaborative filtering,” Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 230-237.
[13]J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. T. Riedl (2004), “Evaluating collaborative filtering recommender systems,” ACM Transactions on Information Systems, Vol. 22, No. 1, pp. 5-53.
[14]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, pp. 194-201.
[15]B. Jeong, J. Lee, and H. Cho (2009), “An iterative semi-explicit rating method for building collaborative recommender systems,” Expert Systems with Applications, Vol. 36, No. 3, Part 2, pp. 6181-6186.
[16]Jester Joke. (2010), Available at: http://goldberg.berkeley.edu/jester-data/.
[17]B. Kim, Q. Li, C. Park, S. Kim, and J. Kim (2006), “A new approach for combining content-based and collaborative filters,” Journal of Intelligent Information Systems, Vol. 27, No. 1, pp. 79-91.
[18]M. Kunaver, T. Pozrl, M. Pogacnik, and J. Tasic (2007), “Optimisation of combined collaborative recommender systems,” AEU-International Journal of Electronics and Communications, Vol. 61, No. 7, pp. 433-443.
[19]K. Kwon, J. Cho, and Y. Park (2009), “Multidimensional credibility model for neighbor selection in collaborative recommendation,” Expert Systems with Applications, Vol. 36, No. 3, Part 2, pp. 7114-7122.
[20]G. Lekakos and 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.
[21]H. Liu and V. Keselj (2007), “Combined mining of web server logs and web contents for classifying user navigation patterns and predicting users'' future requests,” Data and Knowledge Engineering, Vol. 61, No. 2, pp. 304-330.
[22]H. Luo, C. Niu, R. Shen, and C. Ullrich (2008), “A collaborative filtering framework based on both local user similarity and global user similarity,” Machine Learning, Vol. 72, No. 3, pp. 231-245.
[23]M. Montaner, B. López, and J. L. de la Rosa (2003), “A taxonomy of recommender agents on the Internet,” Artificial Intelligence Review, Vol. 19, No. 4, pp. 285-330.
[24]M. P. O''Mahony, N. J. Hurley, and G. C. M. Silvestre (2004), “An evaluation of neighbourhood formation on the performance of collaborative filtering,” Artificial Intelligence Review, Vol. 21, No. 3, pp. 215-228.
[25]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.
[26]C.H. Piao, J. Zhao, and L. J. Zheng (2009), “Research on entropy-based collaborative filtering algorithm and personalized recommendation in e-commerce,” Service Oriented Computing and Applications, Vol. 3, No. 2, pp. 147-157.
[27]P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl (1994), “GroupLens: an open architecture for collaborative filtering of netnews,” Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work, pp. 175-186.
[28]B. Sarwar, G. Karypis, J. Konstan, and J. Reidl (2001), “Item-based collaborative filtering recommendation algorithms,” Proceedings of the 10th International Conference on World Wide Web, pp. 285-295.
[29]B. Sarwar, G. Karypis, J. Konstan, and J. Riedl (2000), “Analysis of recommendation algorithms for e-commerce,” Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 158-167.
[30]J. B. Schafer, J. Konstan, and J. Riedi (1999), “Recommender systems in e-commerce,” Proceedings of the 1st ACM Conference on Electronic Commerce, pp. 158-166
[31]U. Shardanand and P. Maes (1995), “Social information filtering: algorithms for automating “word of mouth”,” Proceedings of the SIGCHI Conference on Human Factors inComputingSystems, pp. 210-217.
[32]P. Symeonidis, A. Nanopoulos, A. Papadopoulos, and Y. Manolopoulos (2008), “Nearest-biclusters collaborative filtering based on constant and coherent values,” Information Retrieval, Vol. 11, No. 1, pp. 51-75.
[33]P. Symeonidis, A. Nanopoulos, A. N. Papadopoulos, and Y. Manolopoulos (2008), “Collaborative recommender systems: Combining effectiveness and efficiency,” Expert Systems with Applications, Vol. 34, No. 4, pp. 2995-3013.
[34]K. Wittenburg, D. Das, W. Hill, and L. Stead (1995), “Group asynchronous browsing on the World Wide Web,” Proceedings of the 4th International World Wide Web Conference, pp. 51-62.
[35]G. R. Xue, C. Lin, Q. Yang, W. Xi, H. J. Zeng, Y. Yu, and Z. Chen (2005), “Scalable collaborative filtering using cluster-based smoothing,” Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development inInformation Retrieval, pp.114-121.
[36]J. M. Yang and K. F. Li (2009), “Recommendation based on rational inferences in collaborative filtering,” Knowledge-Based Systems, Vol. 22, No. 1, pp. 105-114.
[37]A. Zenebe, A. Ozok, and A. F. Norcio (2005), “Personalized recommender systems in e-commerce and m-commerce: A comparative study,” Proceedings of 11th International Conference on Human-Computer Interaction.
[38]L. Zhen, G. Q. Huang, and Z. Jiang (2009), “Collaborative filtering based on workflow space,” Expert Systems with Applications, Vol. 36, No. 4, pp. 7873-7881.