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

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

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

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

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

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

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