基于可變網格聚類的協(xié)同過濾算法

基于可變網格聚類的協(xié)同過濾推薦算法

Summary：針對傳統(tǒng)的相似度計量方法根據(jù)用戶評分信息矩陣來計算物品或者用戶相似度，需要考慮所有用戶反饋的歷史信息，提出一種改進的協(xié)同過濾推薦算法。首先，將所有物品度的平均值作為一個閾值，選出高密度閾值物品。其次，使用可變網格的聚類方法將有共同興趣是用戶聚為同一類。最后，在類內用推薦算法對用戶進行物品推薦。實驗結果表明新算法在一定程度上提高了推薦系統(tǒng)的推薦精度和質量。Keys：可變網格；協(xié)同過濾；推薦算法；相似性度量1引言

在電子商務迅猛發(fā)展的今天，幾乎所有的電子商務網站，如京東，淘寶，拼多多，美團等都使用了推薦系統(tǒng)，這些推薦系統(tǒng)都從不同角度為客戶提供了個性化推薦信息。雖然最近已經發(fā)明了多種推薦技術，但是協(xié)同過濾依然是推薦系統(tǒng)中應用最為成功的推薦系統(tǒng)之一。如何快速準確的從海量數(shù)據(jù)中過濾掉無用信息，篩選出有用的信息推薦給用戶成為學者和各大電子商務網站研發(fā)的重點。然而隨著電子商務數(shù)據(jù)的指數(shù)級的增加，用戶-項目評分矩陣愈加稀疏，冷啟動，可擴展性開始顯現(xiàn)，導致推薦質量下降。

為了解決協(xié)同過濾中以上問題，國內外研究學者們提出了很多改進方法和解決方案。文獻[1]提出一種基于半監(jiān)督學習模型的協(xié)同過濾推薦算法.半監(jiān)督學習可以同時利用有標簽和無標簽數(shù)據(jù)，根據(jù)有標簽數(shù)據(jù)的監(jiān)督信息來給無標簽數(shù)據(jù)打上偽標簽，通過對無標簽數(shù)據(jù)的預測，有效緩解數(shù)據(jù)的稀疏性，但可伸縮性能不足。文獻[2]針對用戶項目評分表的稀疏性,使得用戶相似度計算誤差較大的情況,采用一種基于用戶與項目特征興趣的相似度算法。該算法使用余弦相似度方法,由用戶與項目特征興趣矩陣計算得到改進后的用戶相似度，提高了推薦質量。王茜等人[3]提出一種改進的聚類方法,該方法通過應用自構建聚類算法減少了商品的維度,然后直接在聚類上運行推薦算法。該算法提高了推薦算法的效率，但推薦質量有所下降。針對以上存在的問題，本文提出用可變網格的k-means聚類算法與Top-N協(xié)同過濾推薦算法相結合的新算法。有效緩解用戶評分數(shù)據(jù)稀疏性導致的冷啟動問題，克服傳統(tǒng)相似性度量方法的不足，本文通過實驗表明，結合新的聚類算法的Top-N協(xié)同過濾推薦算法得到的推薦結果準確性上有了進一步提高。基于可變網格的用戶聚類算法

用戶的特征影響用戶的行為，用戶的特征包括如：性別，學歷，身高，年齡，職業(yè)等。例如在某電影推薦網上，大多數(shù)男性會選擇動作片或戰(zhàn)爭片，女性大多會選擇家庭片或愛情片，小孩子多會選擇動漫片等。但是很多推薦網站會忽略用戶特征這一推薦維度。本節(jié)對含有K個特征的N個用戶進行有效聚類。

基于可變網格的聚類算法VGOk-means的具體過程為：首先將含N個用戶的數(shù)據(jù)集D的每一維用快速排序法進行升序排序，再等深劃分各維數(shù)據(jù)，計算相鄰區(qū)間段的相似度ρ并與相似度閾值v進行比較，如果ρ>v，則相鄰區(qū)間段進行合并，否則不合并，遍歷所有區(qū)間段，得到合并后的結果。然后計算合并后網格的密度并將結果記錄到集合c中，根據(jù)網格密度，計算網格密度閾值，并將大于密度閾值的網格密度結果放入集合d中，對d中的網格用k-means聚類方法進行網格聚類，結果放入集合e中，得到k個最優(yōu)聚類結果。在基于可變網格的用戶聚類算法中，局部地使用了k-means算法，與k-means算法相比，避免了隨機選取中心點而產生局部最優(yōu)解的可能，得到了更準確的聚類結果?；诳勺兙W格聚類的協(xié)同過濾推薦算法本文提出一種可變網格K-means聚類算法的Top-N協(xié)同過濾推薦算法。算法的基本思想為：首先，把用戶之間的相似度視為距離，利用可變網格K-means聚類算法根據(jù)樣本點之間的距離，將項目矩陣H中的用戶聚類成若干個簇類。然后，當需要為某一個目標用戶進行推薦時，計算該目標用戶與各個聚類中心的距離，從而確定該目標用戶所屬的簇類。最后，在簇內應用Top-N推薦算法為目標用戶進行推薦。基于以上推薦流程的分析，給出基于可變網格的協(xié)同過濾推薦算法，具體算法如下所示。RVM-CF(基于可變網格的協(xié)同過濾推薦算法)輸入：用戶特征矩陣{u1，u2，…，un}，商品項目屬性矩陣{I1，I2，…，In}，期望的推薦集數(shù)N；輸出：Top-N項目推薦集Begin1.利用VGOk-means聚類方法對用戶特征集進行聚類，得到最優(yōu)的k個聚類簇;2.在k個聚類簇中計算用戶u，v之間的相似度，統(tǒng)計出相似度最大的k個用戶作為目標用戶的最近鄰居集KNNv；3.對項目屬性矩陣利用VGOk-means聚類方法聚類，將項目劃分為k個簇,4.在k個簇中計算項目i，j之間的相似度psim(i,j)，選出i在項目簇Pk中相似度最大的k個項目組成項目集KNNi；5.計算最近鄰居的評分情況，并對簇中目標用戶原本未評分項目分別進行預測；6.將所得評分進行降序排列，挑選出前N個高評分項目推薦給目標用戶，即生成Top-N項目推薦集。本節(jié)提出的基于可變網格的協(xié)同過濾推薦算法通過改進相似性計算方法，解決了新用戶或新項目存在的冷啟動問題；同時改進的算法增強了用戶和項目之間的關聯(lián)關系，縮小了查找空間，能夠較為準確的獲得真正相似的近鄰用戶，因此得到的評分預測也更加準確。4實驗分析4.1數(shù)據(jù)集本文的實驗數(shù)據(jù)集采用的是美國明尼蘇達大學提供的Movielens公開數(shù)據(jù)集（）。該數(shù)據(jù)集中包含943個用戶對1682部電影的10萬條評分記錄，并且每個用戶至少對20部電影進行評分，每條數(shù)據(jù)都按照用戶ID、電影ID、評分和時間戳四個變量排列，樣本的排列是無序的。在實驗過程中將數(shù)據(jù)的80%作為訓練集，20%作為測試集進行檢驗。實驗環(huán)境：window10的64位操作系統(tǒng)。采用R語言編程。試驗中計算機的硬件配置為：12GB內存，500G硬盤，處理器是Intel(R)Core(TM)i5。4.2評估標準本文采用的評估標準是用平均絕對誤差和均方誤差來評價推薦質量。用召回率作為評價精度的指標。對目標用戶ui推薦N個物品，記為N(i)。在實驗中取N為10。令目標用戶ui在測試集上喜歡的項目集合為T(i)，召回率的計算方法如下：4.3實驗結果與分析本文中分別將所有用戶聚成2、3、4、5、6個簇，并且可變網格聚類迭代步驟分別設為5、10、…、45步。表4-1是改進的算法在聚類數(shù)分別為2、3、4、5、6時得到的推薦召回率。由表可以看出，當用戶類簇為2時，迭代次數(shù)為10左右時，推薦效果是最佳的。召回率達到了0.11598.比協(xié)同過濾推薦算法提升了2%。很顯然，將用戶聚為2或3個簇時，改進的RVM-CF算法比Top-N推薦算法精度更高。表4-1RVM-CF算法在各聚類情況下推薦結果的召回率Step=5Step=10Step=15Step=20Step=25Step=30Step=35Step=40Step=45CF0.11361K=20.115020.115980.115970.115970.115950.115960.115960.115960.11596K=30.114810.115470.115360.114870.115000.114940.114840.114740.11474K=40.112350.113860.113680.113730.113720.113630.113650.113640.11363K=50.112420.113460.113320.113210.113250.113270.113070.113370.11297K=60.111960.112850.112050.111820.111560.111780.111480.111380.111885總結本文利用可變網格的協(xié)同過濾推薦算法分別對用戶、項目進行聚類分析，針對用戶數(shù)據(jù)采用基于用戶相似性的推薦算法進行最終預測，提高推薦的動態(tài)性和準確性。本文提出的算法在召回率上比傳統(tǒng)的協(xié)同過濾推薦算法提升了2%.證明了提出算法的正確性，提高了推薦質量。Reference：[1]崔瑩瑩,陳卓,王紅霞.基于半監(jiān)督學習模型的協(xié)同過濾推薦算法[J].