基于改進的協同過濾相似性度量算法研究

， ，2，，

(1.湖北大學 計算機與信息工程學院，武漢 430062；2.湖北省教育信息化工程技術研究中心(湖北大學)，武漢 430062)

基于改進的協同過濾相似性度量算法研究

占淵1，肖蓉1，2，繆仲凱1，周雙娥1

(1.湖北大學計算機與信息工程學院，武漢430062；2.湖北省教育信息化工程技術研究中心(湖北大學)，武漢430062)

隨著工程測量和工業控制的發展，在多樣的工程測量環境和工業控制環境中選擇合適的測量和控制理論、方法和技術也將成為難題，推薦技術的引入可以提升工程測量的的自動化程度和工業控制的實時性；但是推薦系統中經典的相似性度量方法在數據稀疏的情況下處理能力較弱，影響了推薦的準確性；針對這一問題，將杰卡徳相似系數加以修正，并利用杰卡德相似系數能夠衡量兩個集合的相似度的特點，將修正后的杰卡德相似系數作為權重系數，對經典的相似性度量方法加以修正，得到新的相似性度量方法；選取5個測評指標，分別在基于用戶和基于項目的協同過濾推薦算法中，對經典的相似性度量方法和改進的相似性度量方法進行測試；對比實驗表明，改進的相似性度量方法表現優于傳統的相似性度量方法，提升比例約為20%。

相似性度量；工程測量；工業控制；杰卡徳相似性

0 引言

隨著信息技術的快速發展，網絡上各種信息暴增，使用戶準確找到自己所需信息成為難題，在工程測量和工業控制中也是如此。為了獲得用戶的依賴，各種服務提供商都不同程度地將個性化推薦算法引入自己的平臺。在眾多推薦算法中，協同過濾推薦是迄今為止應用最為成功的推薦技術之一[1]。在實際的推薦系統中，用戶和項目的不斷增加，使系統中用戶和項目上關于歷史記錄的信息變得稀疏，這是大多數協同過濾推薦系統發展過程中必須面臨的問題。一般情況下，系統中只有極少的項目會被用戶體驗并評分，占總項目的1%左右[2]，這種情況下的評分矩陣非常稀疏，被稱為數據稀疏問題。協同過濾推薦系統通過用戶對項目的評分找到相似鄰居，然后再根據相似鄰居的評分產生推薦。數據稀疏性導致推薦質量被降低的原因有兩點：1)最近鄰居的搜索不夠準確，即搜索到的最近鄰居并非真正意義上的相似；2)獲取的最近鄰居的評分項少，使評分的估計值的誤差較大。那么提高推薦質量的關鍵就變為，在保證推薦準確度的前提下，解決數據稀疏問題。

1 相關研究

許多研究人員都試圖從不同的角度緩和數據稀疏性問題，常見的方法有這樣幾類：填充缺失評分、結合多種推薦結果、與基于內容的推薦相融合和基于圖論的方式。利用填充缺失評分方法的如文獻[3]通過神經網絡獲取用戶之間的信任度，然后填充缺失評分。如文獻[4-5]將其他推薦方法和協同過濾方法相結合來填補矩陣。文獻[6]利用與基于內容的推薦相融合的方法，將關于時間和位置的內容引入到協同過濾推薦系統，緩解了數據稀疏性。文獻[7]通過結合推薦過程中的多種相似性來結合多種推薦結果。文[8]綜合了協同過濾推薦算法中基于用戶的結果和基于項目的結果。文[9]將對分網絡的圖論方法引入推薦系統，幫助協同過濾推薦算法提高了在數據稀疏情況下的推薦準確度。以上眾多方法中，填充缺失值的方法和結合多種推薦結果的方法對數據稀疏問題的改變比較顯著，但是前者的填充值的偏差的積累會降低準確度，后者的可解釋性差。與基于內容的推薦相融合和基于圖論的方式也都能一定程度上緩解數據稀疏問題，但是受非結構化的項目的限制。

還有一種普遍使用的緩解數據稀疏性的方法：在數據稀疏的情況下，提高相似性度量方法的處理稀疏數據的能力。如文獻[10]在最近鄰搜索的過程中，利用提出一種新的相似性度量方法，將越相似的項目賦予更大的權重。文獻[11]將用戶與最近鄰的差異控制在一個有限值，并使相似性之和達到最大。文獻[12]將CF-TPS和WDSM結合起來度量相似性。利用新的相似性方法能充分利用數據信息，雖不能從本質上改變數據的稀疏性，但是能在有限的程度上改善推薦質量。

在計算機化的工程測量和工業控制領域里，引入推薦系統，合理選擇理論、方法和技術，如圖1所示。這將會在很大程度上節省人力資源和時間并提升自動化程度和實時性。

本文提出在計算機化的工程測量和工業控制環境中引入推薦系統的觀點，并在經典的相似性度量方法的基礎上，以修正的Jaccard系數作為權重系數，對傳統的結果做了衰減，并以皮爾遜相關系數為例進行了對比試驗，實驗數據證明了本方法的優勢。

圖1 工程測量和工業控制領域中推薦算法的引入

2 傳統的相似性度量方法

計算用戶或項目之間的相似性的有很多種，其中被普遍認可的方法有3種：余弦相似性、相關相似性和修正的余弦相似性，下面以基于用戶的推薦為例，利用計算用戶間的相似性來介紹這3種方法。用戶間的余弦相似性被定義為：

(1)

(2)

(3)

其中:Iu表示用戶u評分過的項目集合。因為不同的用戶會有不同的評分尺度，修正的余弦相似度通過減去平均評分改善了余弦相似度。

隨著服務商服務范圍的擴大，推薦系統中的用戶和項目的數量劇增，每個用戶評分過的項目占總項目的比例很小，兩個用戶共同評分過的項目占總項目的比例會更小。在這種情況下，因為借助共同評分項目來計算相似度，所以傳統的相似性度量方法會因評分數量過少，將很多原本與目標用戶不相似的用戶，評估為具有很高相似度的最近鄰居。如果這樣的最近鄰居較多，那么推薦質量必然得不到保證。以系統中普遍存在的情況為例：系統中存在用戶u和用戶v，這兩個用戶只共同評分過一個項目i，并且評分值非常接近，現利用傳統的相似度來計算用戶相似度，用戶u和用戶v間的相似度必然是一個很高的值。即當兩個用戶之間的共同評分項目很少，并且評分值接近，兩個用戶之間的相似度會很高，這顯然是很不合理的[13]。但是計算相似性時，基于越多的共同評分項目，所得結果越被認可[14]。

3 改進的相似性度量方法

通過上文對傳統相似性度量方法過程中普遍存在的問題的分析，我們提出一個基本解決策略：對于一個目標用戶，具有越多共同評分項目的用戶，給他們的相似性賦予越高的權重。對于一個目標項目，具有越多共同評分用戶的項目，給他們的相似性賦予越高的權重。實現這個策略的關鍵為如何來確定這個權重。

3.1 杰卡德相似系數的修正

杰卡德相似系數(Jaccard index)最初由Jaccard在1912年提出[15]，由Tan等[16]人將其修正并引入協同過濾系統后，通常用來衡量兩個維度不同的集合的相似度。設兩個不同維度的集合分別為A,B，設Jaccard系數為J(A,B),并可被描述為:

(4)

且有0≤J(A,B)≤1,若|A∩B|越大，即A,B兩個集合之間相同的元素越多，則J(A,B)越大，這一特性正好滿足上述權重的賦予條件，因此將Jaccard系數作為權重引入到相似度的計算。

現思考如下問題：若|A|很大，那么任意較小的B，都會因具有很大的分母，計算出與A很小的J(A,B)。在實際的推薦系統中，普遍存在一些活躍用戶和熱門項目，那么基于這些用戶和項目，計算出來的與其他對象的相似性都會很低，這也會影響推薦系統的準確度。為了讓Jaccard系數適應推薦系統，活躍用戶和熱門項目的評分數量應得到懲罰，Jaccard系數被修正為：

(5)

修正后的Jaccard系數既考慮到共同評分數量對集合的相似性的影響，又考慮到活躍用戶和熱門項目的情況。

3.2 對傳統相似性度量的修正

將修正后的Jaccard系數，作為原有的相似性度量方法的權重系數，這種懲罰方式保留了原有方法的易用性，而且克服了傳統的方法面對稀疏數據的局限。以計算用戶相似度為例，設傳統的相似性度量方法計算出的用戶相似度用表示，sim(u,v)修正的相似度用sim+(u,v)表示，sim+(u,v)被定義為：

(6)

以傳統的PCC為例，設修正的加入Jaccard權重系數的方法為JPCC，那么JPCC的計算公式為：

sim+(u,v)=

(7)

4 實驗和分析

4.1 實驗數據集

由于在工程測量和工業控制領域缺少完備的數據集，因此本文采用Grouplens在MovieLens站點上提供的公用數據集，該數據包含700個用戶對10 000個電影的100 000個評分記錄，評分等級從1到5，系統中的每個用戶至少對20部電影進行了評分，該數據集的稀疏度為1-100 000/(700*10 000)=98.57%。

4.2 測評指標

推薦系統的評測指標有很多，離線測評方式更適用于研究，預測準確度作為離線測評方式的首選測評指標。本文選用評分預測中的2個指標和TopN推薦中的3個指標來全面衡量預測準確度。

4.2.1 評分預測

評分預測的預測準確度通常有兩種指標：均方根誤差(RMSE)和平均絕對誤差(MAE)。MAE是很多學者普遍使用的指標，RMSE因其加大了對系統中預測不準的評分的懲罰而變得更為苛刻。MAE的計算方法如下：

(8)

RMSE的定義為：

(9)

其中:Pu,i是用戶u對項目i的預測評分，Ru,i是用戶u對項目i的實際評分，T代表測試集合，|T|代表測試集合中評分的記錄數量。MAE和RMSE的值越小，說明推薦系統的預測準確度越高。

4.2.2 TopN推薦

采用TopN推薦的系統會對每個用戶生成一個個性化的推薦列表，并通常借助準確率(Precision)和召回率(Racall)來

衡量TopN推薦的預測準確度。Precision定義為推薦列表中真實的評分記錄占測試集合的比例。Recall定義為推薦列表中真實的評分記錄占推薦列表的比例。Precision的計算公式為：

(10)

Racall的計算公式為：

(11)

其中:R(u)代表系統給出的推薦列表，T(u)表示測試集中的行為列表，U表示用戶集合。F指標將兩者綜合起來使用，并能更全面地評價推薦系統的質量。F被定義為：

(12)

在推薦系統中，為了更全面得測評TopN推薦的質量，會在不同N值下的計算這3個指標。這3個指標的值越高，表明TopN推薦的預測準確度越好。

4.3 實驗結果和分析

為了評估不同推薦環境下的改進的度量方法的效果，本文在基于用戶的協同過濾(UBCF)和基于項目的協同過濾(IBCF)中，分別使用PCC和JPCC。通過改變訓練集的大小和最近鄰居的數量，得到不同的MAE值和RMSE值。通過改變推薦列表長度，得到不同的Recall、Precision和F值。為了防止樣品誤差，若實驗不需要改變訓練集大小，則從數據集中抽取90%作為訓練集，10%作為測試集，取10折疊交叉平均實驗結果，若實驗需要改變訓練集大小，則每次隨機選取同樣大小的數據集，取10次的平均實驗結果。

4.3.1 不同訓練集下的測試

將最近鄰居數量取為30，分別取10%,20%,…,90%的數據作為訓練集，在UBCF和IBCF中，分別使用PCC和JPCC作為相似性度量方法，結果如表1。

隨著訓練集的變大，兩種方法的MAE值和RMSE值都趨于變小，即準確度都在提升。在UBCF中，PCC隨訓練集增大，準確度提升得不明顯，而JPCC的提升較為明顯，兩種方法最低的MAE分別為0.867和0.728，RMSE分別為1.076和0.869，在這兩種指標上JPCC相對于PCC推薦準確度的提升比例分別為19.9%和23.8%。在IBCF中訓練集達到90%的時候，PCC和JPCC的MAE值和RMSE都達到最低，MAE分別為0.875和0.718，RMSE分別為1.020和0.856，在這兩種指標上JPCC相對于PCC，推薦準確度的提升比例分別為22.0%和19.1%。

表1 不同數據集大小下PCC與JPCC在UBCF和IBCF中的測試結果

表2 不同鄰居數量下PCC與JPCC在UBCF和IBCF中的測試結果

表3 不同推薦列表長度下PCC與JPCC在UBCF和IBCF中的測試結果

4.3.2 不同鄰居數量下的測試

取90%的數據作為訓練集，鄰居數量取10，20，…,100,在UBCF和IBCF中，分別使用PCC和JPCC作為相似性度量方法，結果如表2。隨著鄰居數量的增大，兩種方法的MAE值和RMSE值都趨于變小，即準確度都在提升，且JPCC的兩個指標值一直小于PCC。在UBCF中，在MAE和RMSE這兩個指標上，JPCC相對于PCC平均下降了25.9%和22.00%。在IBCF中，在MAE和RMSE這兩個指標上，JPCC相對于PCC平均下降了27.8%和23.7%。

4.3.3 不同推薦列表長度下的測試

最近鄰居數量定為30，推薦列表長度取20,40,…,200,觀察不同推薦列表長度下的Recall、Precision和F，結果如表3。不同的推薦列表長度下，雖然JPCC相對PCC，在Precision和F上都有所增加，但是兩種方法的這兩種指標值都比較低，討論意義不大。推薦列表長度越長，在Recall指標上，推薦列表長度越大，JPCC對PCC的提升越明顯。推薦列表長度為200時，在UBCF中，JPCC比PCC提升了23.22%，在IBCF中，JPCC比PCC提升了69.48%。

實驗表明，無論是基于IBCF上的實驗還是基于UBCF上的實驗，無論是訓練集的占比如何，無論最近鄰居的數量如何變化，無論推薦列表的長度如何變化，JPCC都在一定程度上提升了PCC的性能，提升的比例大約為20%。在一個立面結構造型比較復雜、曲面弧形結構較多的小高層建筑施工測量過程中，面對多樣的測量場景，需要選取不同的放線方法，方法的選取會消耗測量員大量的時間。若將推薦系統引入工程測量，推薦系統會根據測量場景和測量員的測量歷史，為其選取合適的放線方法，這必然會節省測量員的人力和時間，從而帶來更大的經濟效益。

5 總結

隨著工程測量和工業控制的發展，在多樣的工程測量環境和工業控制環境中選擇合適的測量和控制理論、方法和技術也將成為難題，本文提出在計算機化的工程測量和工業控制環境中引入推薦系統的觀點，并針對個性化推薦算法中數據稀疏情況下，經典的相似性度量方法的處理能力較弱的問題。將杰卡徳相似系數加以修正，并利用杰卡德相似系數能夠衡量兩個集合的相似度的特點，將修正后的杰卡德相似系數作為權重系數，對經典的相似性度量方法加以修正，得到新的相似性度量方法。實驗表明改進的相似性度量方法優于經典的相似性度量方法。為了證明改進的方法的適用性，后續將在完備的工程測量和工業控制數據集對本方法進行測試。

[1] Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[J]. IEEE Transactions on Knowledge amp; Data Engineering, 2005, 17(6):734-749.

[2] Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]. International Conference on World Wide Web. ACM, 2001:285-295.

[3] Devi M K K, Samy R T, Kumar S V, et al. Probabilistic neural network approach to alleviate sparsity and cold start problems in collaborative recommender systems[C]. IEEE International Conference on Computational Intelligence and Computing Research. 2010:1-4.

[4] Jeong B, Lee J, Cho H. An iterative semi-explicit rating method for building collaborative recommender systems[J]. Expert Systems with Applications, 2009, 36(3):6181-6186.

[5] Fan J, Pan W, Jiang L. An improved collaborative filtering algorithm combining content-based algorithm and user activity[C]. International Conference on Big Data and Smart Computing. IEEE, 2014:88-91.

[6] Yu C, Huang L. A Web service QoS prediction approach based on time- and location-aware collaborative filtering[J]. Service Oriented Computing and Applications, 2016(2):1-15.

[7] Wang J, Vries A P D, Reinders M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion[C]. SIGIR 2006: Proceedings of the, International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, Washington, Usa, August. DBLP, 2006:501-508.

[8] Wang B, Huang J, Ou L, et al. A collaborative filtering algorithm fusing user-based, item-based and social networks[C]. IEEE International Conference on Big Data. IEEE, 2015:2337-2343.

[9] Zhou T, Ren J, Medo M, et al. Bipartite network projection and personal recommendation[J]. Physical Review E Statistical Nonlinear amp; Soft Matter Physics, 2007, 76(2):046115.

[10] Choi K, Suh Y. A new similarity function for selecting neighbors for each target item in collaborative filtering[J]. Knowledge-Based Systems, 2013, 37(1):146-153.

[11] Kaleli C. An entropy-based neighbor selection approach for collaborative filtering[J]. Knowledge-Based Systems, 2014, 56(C):273-280.

[12] Su H, Lin X, Wang C, et al. Parallel Collaborative Filtering Recommendation Model Based on Two-Phase Similarity[M]. Intelligent Computing Theories and Methodologies. Springer International Publishing, 2015:1-6.

[13]Mclaughlin M R, Herlocker J L. A collaborative filtering algorithm and evaluation metric that accurately model the user experience[C]. International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2005:329-336.

[14] Deng A L, Zhu Y Y, Shi B L,et al.基于項目評分預測的協同過濾推薦算法[J]. 軟件學報, 2003, 14(9):1621-1628.

[15] Jaccard P. The Distribution of the Flora in the Alpine Zone[J]. New Phytologist, 2010, 11(2):37-50.

[16] Tan P N, Steinback M, Kumar V. Introduction to Data Mining[J]. Intelligent Systems Reference Library, 2011, 26(25):1-43.

ANewSimilarityMeasurementMethodinCollaborativeFiltering

Zhan Yuan1, Xiao Rong1,2, Miao Zhongkai1, Zhou Shuang’e1

(1.School of Computer and Information Engineering,Hubei University,Wuhan 430062,China; 2.Hubei Education Information Engineering Technology Research Center,Wuhan 430062,China)

With the development of engineering survey and industrial control, selecting the appropriate theories, methods, and techniquese in various engineering survey and industrial control environment will become a problem, the introduction of recommendation technology can improve the degree of automation of engineering survey and real-time performance of industrial control. At the same time, the classical similarity measurement method in recommendation system is weak in the case of sparse data, which affects the accuracy of recommendation. To solve this problem, Jaccard similarity coefficient is improved, because Jaccard similarity coefficient is able to measure the similarity coefficient of two sets, the improved Jaccard similarity coefficient is is used as the weight coefficient of the classical similarity measurement result, and a new similarity measurement method is obtained. MovieLens datasets and 5 evaluation indicators are selected, and the classical similarity measurement methods and the improved similarity measurement methods are tested respectively on the user-based and item-based collaborative filtering recommendation algorithm. The contrast experiment shows that the improved similarity measure is superior to the traditional similarity measure, and the promotion ratio is about 20%.

similarity measurement; engineering survey; industrial control; Jaccard similarity

2017-06-50；

2017-07-21。

占 淵(1996-)，女，湖北谷城人，在讀本科生，主要從事軟件工程方向的研究。

周雙娥(1965-)，女，湖北天門人，博士，教授，主要從事容錯及分布計算方向的研究。

1671-4598(2017)09-0287-04

10.16526/j.cnki.11-4762/tp.2017.09.073

TP273

A