聶曉明 高鵬翔

摘要：針對推薦算法數(shù)據(jù)稀疏及聚類中心點敏感問題，提出了一種基于用戶偏好和麻雀搜索聚類的協(xié)同過濾推薦算法。首先使用評分偏好模型對原用戶項目矩陣進行修正，得到新的用戶偏好-項目矩陣。利用麻雀搜索對聚類中心點進行優(yōu)化，從目標用戶所在簇內(nèi)得到最近鄰，提高了算法迭代速度，改善了聚類中心點敏感的問題。使用相似度公式對目標用戶未評分項目進行預測，并完成推薦。實驗結果表明，相較于其他幾種推薦算法，準確度提高了4到6個百分點。

關鍵詞：評分偏好;麻雀搜索;協(xié)同過濾;推薦精度

中圖分類號：TP391.3

文獻標志碼：A

文章編號：1006-1037（2021）01-0070-07

基金項目：

山東省自然科學基金（批準號：ZR2019PEE018）資助。

通信作者：高鵬翔，男，教授，主要研究方向為人工智能。E-mail：gappengxiang@qdu.edu.cn

近年來，隨著網(wǎng)絡信息數(shù)據(jù)的急劇增長，帶來了大數(shù)據(jù)時代。隨之而來的是用戶的個性化需求不斷提高，如何尋找到用戶真正感興趣的信息已經(jīng)成為一項棘手的難題。為此，人們開發(fā)出了推薦系統(tǒng)[1] （Recommender Systems），根據(jù)不同用戶的個性化需求，推薦用戶最有可能喜歡的條目。推薦系統(tǒng)的技術核心是推薦算法，其中，協(xié)同過濾算法是推薦系統(tǒng)中應用最為廣泛、最成功的技術之一。協(xié)同過濾算法的原理是試圖通過對用戶過去行為的了解，找出相似用戶，分析相似用戶喜歡的項目集合完成推薦項目。但是協(xié)同過濾算法存在一定的不足，如冷啟動、稀疏性以及缺乏定制推薦[2]，仍需要對其不斷完善。為了改善算法的推薦準確性，研究人員從不同的方面做了研究，針對矩陣稀疏的問題，Hu等[3]證明了聚類技術如何改進協(xié)同過濾算法并有效提高在稀疏矩陣中的推薦效果。Xiong等[4]利用統(tǒng)計學聚類算法，提出一種基于項目的協(xié)同過濾推薦系統(tǒng)，有效的解決了數(shù)據(jù)稀疏的問題。Xia等[5-6]提出了一種利用矩陣填充的協(xié)同過濾算法，通過算法模型對缺失的數(shù)據(jù)進行評分的預測填充，以此來緩解數(shù)據(jù)稀疏問題，但由于缺省值的設置導致誤差的產(chǎn)生，預測的評分依然不夠準確。Shi等[7]通過關聯(lián)規(guī)則評估用戶之間的相似性來解決這個問題。使用上述算法對相關聯(lián)項目的權重進行分配和迭代改進，有效地提高了推薦的準確性。針對傳統(tǒng)協(xié)同過濾推薦技術的冷啟動問題，Zhou等[8]將基于人工魚群聚類應用到基于用戶的協(xié)同過濾推薦系統(tǒng)中，提高了推薦結果的準確率。趙亞輝等[9]利用用戶之間的信任信息，更好地找到興趣相似的用戶集，增強推薦效果。林甲祥等[10]提出的結合社交關系和關聯(lián)規(guī)則的推薦算法可以有效解決冷啟動問題，但是算法實現(xiàn)過程較復雜，在實際應用中可能在于系統(tǒng)的吞吐量會受到限制。上述研究都在一定程度上提高了協(xié)同推薦算法的準確性，緩解了協(xié)同過濾算法中的問題。然而，這些方法都忽略了用戶的評分偏好對結相似度計算帶來的影響，以及在面臨聚類時容易出現(xiàn)中心點敏感問題，導致最近鄰居選取不準確，本文提出了一種基于用戶偏好和麻雀搜索聚類的協(xié)同過濾算法（Collaborative filtering algorithm based on user preference and sparrow search clustering，UPSSCA-CF）。利用用戶對評分的偏好屬性修正用戶—項目矩陣，使用麻雀搜索的聚類算法，對修正后的用戶偏好—項目矩陣進行聚類分組，在目標用戶的所屬類簇中，通過相似度和評分預測公式對矩陣中缺失的項目值進行填充，找出目標用戶未評分項目中最高的N個項目，從而完成推薦。通過在MovieLens數(shù)據(jù)集上進行實驗驗證。

1 傳統(tǒng)的基于聚類協(xié)同過濾算法

聚類算法的思想引入推薦系統(tǒng)中，可以很好的找到用戶之間的相似關系。聚類問題[11-12]可以定義為：給定的n維用戶行為矩陣中對用戶進行聚類，計算并比較目標用戶與預設定的k個中心點之間的距離，將行為相近的用戶點劃分到同個簇中，然后從距離最近的k個簇內(nèi)生成最近鄰居集[13]。

（1）產(chǎn)生用戶—項目評分矩陣。假設對項目進行評分的用戶的id集合為U=ui|i∈1，2，…，n，和項目的id集合為i=it|t∈1，2，…，m。用戶對項目的評分矩陣用R=Ri，j|i∈1，2，…，n，j∈1，2，…，m表示，其中元素Ri，j表示ui對項目ij的評分，其范圍為1到5之間的整數(shù)。

（2）計算用戶的相似度。用戶相似度計算是協(xié)同過濾中的關鍵環(huán)節(jié)，需要計算每個用戶和其他用戶之間的相似度。目前應用最廣泛的相似度計算方法有Pearson相似系數(shù)、Jaccard相似系數(shù)和余弦相似系數(shù)[14]等。本文選擇用來計算相似度的是Pearson相似系數(shù)

其中，simu，v表示用戶u和用戶v的Pearson相似度，items表示用戶u和用戶v的共同評分項集合，Ru，i和Rv，i分別表示用戶u和用戶v對項目i的評分分數(shù)，Ru 和Rv 分別表示用戶u和用戶v平均評分[15]。

（3）評分預測推薦。得出用戶之間的相似度后，通常采用KNN推薦模型[16]進行最近鄰集合的選取，從而進行評分預測，將需要推薦的項目與用戶已購買的項目進行比較，在用戶未進行評分的項目中，把預測評分最高的n個項目推薦給目標用戶

其中，Ru，i表示用戶u對產(chǎn)品i的預測評分，SUser表示用戶的最近鄰集合。simu，v表示用戶u和用戶v的相似度，Ru、Rv表示用戶u和用戶v對其他產(chǎn)品打分的均值[17]。

2 UPSSCA-CF

2.1 用戶偏好—項目矩陣

考慮表1中的用戶項目評分矩陣用戶項目評分矩陣相似性矩陣假設，如果用戶u1喜歡某個項目，則會打4分，相反如果不喜歡，則打1分。因此，從表1可以看出，u1喜歡i2，但不喜歡i1。但是如果其他用戶u2喜歡i2和u1喜歡i2一樣多，會給i2打5分。用戶u2不喜歡i2，會將其評為2。因此，u1和u2之間的相似性應該是1，因為他們都喜歡i2不喜歡i1，但顯然通過公式求出兩者的相似性矩陣中的值卻不是1。這種矛盾的發(fā)生是因為用戶對物品的打分習慣是存在差異的[18]。

為此本文使用用戶打分偏好來對用戶—項目矩陣進行修正。引入評分偏好模型[19]，假設評分類別集合為P1，…，P5，若Pj<Pi，表示評分類別Pj小于評分類別Pi。用戶u對評分類別的偏好得分

計算出所有用戶的評分類別偏好后，使用用戶評分類別偏好得分代替用戶—物品矩陣中的原始得分，得到修正后的用戶偏好—項目矩陣，該矩陣元素的值代表用戶對物品的偏好，在一定程度上提高推薦準確率。

2.2 麻雀搜索聚類的協(xié)同過濾算法

本文對上一節(jié)得到的用戶偏好—項目矩陣使用麻雀搜索優(yōu)化K-means算法的中心點的選擇，改善了聚類算法中心點選取敏感問題，增強了聚類效果并提高了推薦算法的可擴展性。該矩陣可表示為X=x1，x2，…，xi，…，xn ，其中xi表示用戶ui對所有項目類型的偏好。

2.2.1 麻雀搜索算法 麻雀搜索算法[20]是一種新型的群智能優(yōu)化算法，受麻雀的覓食行為和反捕食行為的啟發(fā)，模擬了麻雀群覓食的過程。麻雀中負責尋找食物并為整個麻雀種群提供覓食區(qū)域和方向的個體作為發(fā)現(xiàn)者，其他麻雀作為跟隨者，跟隨者則是利用發(fā)現(xiàn)者來獲取食物。同時還疊加了偵查預警機制，種群中選取一定比例的麻雀進行偵查預警，監(jiān)視群體中其它麻雀的危險行為，該種群中的攻擊者會與高攝取量的同伴爭奪食物資源，如果發(fā)現(xiàn)危險則放棄食物，以提高自己的捕食率。

發(fā)現(xiàn)者通常有高水平的能量儲備，并為所有的覓食者提供覓食區(qū)域或方向，負責確定可以找到豐富食物來源的地區(qū)。能量儲備水平取決于對麻雀健康值的評估。一旦麻雀發(fā)現(xiàn)了捕食者，就會發(fā)出警報信號。當報警值大于安全閾值時，發(fā)現(xiàn)者需要將所有麻雀引向安全區(qū)域。每代發(fā)現(xiàn)者的位置更新

其中，t表示當前迭代，j=1，2，…，d，Xti，j表示種群中第t代中第i個麻雀的第j維位置，itermax是迭代次數(shù)最多的常數(shù)。α∈（0，1]是一個隨機數(shù)，R2R2∈[0，1]和STST∈[0.5，1]分別代表報警值和安全閾值，Q為一個標準正態(tài)分布隨機數(shù)。當R2<ST時，說明周圍沒有捕食者，生產(chǎn)者進入廣域搜索模式。如果R2≥ST，說明一些麻雀已經(jīng)發(fā)現(xiàn)了捕食者，所有的麻雀都需要迅速飛到其他安全區(qū)域。

對于跟隨者，一些跟隨者會頻繁地監(jiān)視生產(chǎn)者。一旦發(fā)現(xiàn)生產(chǎn)者找到了好的食物，會立即離開現(xiàn)在的位置去競爭食物。如果贏了，可以立即得到生產(chǎn)者的食物，否則，將繼續(xù)執(zhí)行跟隨能提供最好食物的生產(chǎn)者去尋找食物。跟隨者的位置更新公式

其中，Xt+1P是生產(chǎn)者占據(jù)的最佳位置;Xtworst表示當前全局最差位置;A表示1×d的矩陣，其中每個元素隨機分配1或-1，并且A+=ATAAT-1。當i>n/2時，說明適應值較差的第i個跟隨者最有可能餓死。

麻雀覓食的同時部分麻雀負責警戒，當危險靠近時，麻雀會放棄當前的食物，即無論該麻雀是發(fā)現(xiàn)者還是跟隨者，都將放棄當前的食物而移動到一個新的位置。每代將從種群中隨機選擇Sn個個體進行預警行為。其位置更新公式

其中，Xtbest是當前的全局最優(yōu)位置;β是步長控制參數(shù)，取值是平均值為0、方差為1的隨機數(shù)的正態(tài)分布;K∈-1，1是一個隨機數(shù)表示麻雀移動的方向，也是步長控制系數(shù);fi是目前麻雀的適應值，fg和fworst分別是當前的全局最佳適應值和最差適應值，ε是最小常數(shù)，以避免零除誤差。當fi≠fg表示麻雀位于簇的邊緣。Xtbest顯示了聚類中心的位置，周圍是安全的。fi=fg表明，處于種群中間的麻雀意識到了危險，需要靠近其他麻雀。

2.2.2 麻雀搜索的用戶聚類算法 融合麻雀搜索的用戶聚類算法（User clustering algorithm for sparrow search，SSCA）的算法思想是先利用麻雀搜索算法查找最優(yōu)的初始聚類中心，再使用最優(yōu)的初始聚類中心對用戶進行K-means聚類。麻雀搜索算法中的每一只麻雀表示一個聚類中心矩陣C=C1，C2，…，Cc，在麻雀搜索算法中，每只麻雀有一個位置屬性，代表找到的食物的位置，在D維解空間內(nèi)每只麻雀的位置為適應度值，所有麻雀的適應值可以用以下向量表示

其中，D表示麻雀的數(shù)量，每代選取種群中位置最好的Pm只麻雀作為發(fā)現(xiàn)者，剩余的D-Pm只麻雀作為跟隨者。Fx中每行的值表示個體的適應值。在SSCA算法，具有較好適應值的生產(chǎn)者在搜索過程中優(yōu)先獲得食物，見算法1。

2.3 UPSSCA-CF算法流程

UPSSCA-CF分為以下5步，具體流程如1圖所示。

（1） 首先對原始數(shù)據(jù)列表進行預處理，生成用戶—項目矩陣。然后輸入到評分偏好模型中，對每個用戶的所有評分進行計算，計算得出用戶的評分偏好得分，使用評分偏好代替原來矩陣的評分值，構建用戶偏好—項目矩陣;

（2） 使用算法1，對用戶偏好—項目矩陣中的每一個用戶進行搜索，找到最優(yōu)的位置，作為初始聚類的中心點;

（3） 對用戶偏好—項目矩陣進行聚類，根據(jù)聚類結果將用戶分成不同的簇，并找出目標用戶所在的簇;

（4） 在目標用戶所在簇中，使用式（1）計算相似度，并且按照降序進行排列，采用KNN推薦模型選取與目標用戶最相似的k個用戶作為最近鄰集合;

（5） 在最近鄰集合中，將需要推薦的項目與用戶已購買的項目進行比較，將從用戶未使用過或未購買過的項目中，使用式（2）對項目評分預測，把預測評分最高的n個項目推薦給用戶，完成推薦。

與主流的基于K-means聚類算法 （K-means）對比， UPSSCA-CF算法在聚類分簇之前，使用麻雀搜索算法尋找最優(yōu)的初始中心點，優(yōu)化算法，提高了算法應對聚類中心點敏感這一問題。與主流的粒子群優(yōu)化的協(xié)同過濾算法（ParticleSwarmOptimization，PSO-CF）進行對比，UPSSCA-CF算法增加了評分偏好模型，通過用戶的打分習慣偏好對矩陣進行修正得到用戶偏好—項目矩陣，提高了推薦算法的準確性。

3 實驗及結果

3.1 實驗環(huán)境與數(shù)據(jù)集

本文的實驗環(huán)境為一臺PC機，機器的配置為intel core i5、1.60GHz、8GB，操作系統(tǒng)為windows10，實驗使用Python實現(xiàn)。選取MovieLens數(shù)據(jù)集[21]測試算法準確性。MovieLens數(shù)據(jù)集是公認為評估推薦算法最主要的數(shù)據(jù)集之一，數(shù)據(jù)集的下載鏈接為http：//files.grouplens.org/datasets/movielens/。該數(shù)據(jù)集提供了幾種不同數(shù)量級的數(shù)據(jù)，本文選取的是十萬量級的數(shù)據(jù)集，包括近千個用戶對1 682部帶有標簽的電影提供的評分記錄，為方便推薦算法的使用，該數(shù)據(jù)集的評分范圍為1～5分，1表示不喜歡，5表示很喜歡。該數(shù)據(jù)集可以使用的評分只占6.3%，是一種特別稀疏的數(shù)據(jù)集。本文通過對該數(shù)據(jù)集進行預處理，提取出用戶對項目的評分保存在用戶—項目評分矩陣中。

3.2 實驗方法與度量標準

本文采用k折交叉驗證，將研究數(shù)據(jù)分為k份，再將k份采用不同比例的分割進行交叉驗證。文中k=5，即5折交叉驗證。比如取出1份作為測試集，剩下的4份作為訓練集。每個實驗進行5次試驗，最終對5次實驗的值取平均值，進行比較分析。

為了驗證推薦算法的推薦準確性，采用廣泛應用于比較和測量推薦系統(tǒng)的標準，統(tǒng)計平均絕對誤差（mean absolute error，MAE）度量標準。MAE是對所有測試用戶對測試項目的預測評分和實際評分的平均誤差大小的計算

其中，Tu表示測試集中的用戶數(shù)據(jù)集合，N表示測試集中商品數(shù)量，Ru，i表示用戶u對商品i的預測評分，Qu，i表示真實評分。

3.3 實驗結果

3.3.1 用戶最佳聚類個數(shù)c的確定 為了確定用戶的最佳聚類個數(shù)c，實驗中c值的取值范圍為[3，20]，選取最近鄰居數(shù)量默認設置為20，其MAE結果如圖2所示?？芍?，用戶的聚類個數(shù)為11時，MAE值最小。因此，用戶的最佳聚類個數(shù)為11。

3.3.2 用戶的最佳近鄰個數(shù)k的確定 本文實驗中針對最佳鄰居個數(shù)k值的取值進行限定，取值范圍為（5～60），k取值的不同對MAE的影響如圖3所示?？芍罱従觽€數(shù)k在[5，30]的范圍內(nèi)，MAE隨著k的增加而呈現(xiàn)下降趨勢，表明推薦效果在該范圍內(nèi)隨著最近鄰居個數(shù)的增加而增加，在k=30時，本文算法的MAE最小。而當最近鄰居個數(shù)k在[30，60]范圍內(nèi)，隨著k的增加，MAE呈現(xiàn)緩慢上升的趨勢。因此，在所提算法中最近鄰居個數(shù)k的最佳值為30。

3.3.3 UPSSCA-CF與其他主流協(xié)同過濾算法的對比 為了驗證本文所提UPSSCA-CF算法推薦結果的準確性，實驗中選取了3種主流的推薦算法與其進行對比，包括基于K-means聚類算法 （K-means）、粒子群優(yōu)化的協(xié)同過濾算法（ParticleSwarmOptimization，PSO-CF）和傳統(tǒng)的基于用戶的協(xié)同過濾推薦算法（UBCF）。參數(shù)的設置為：聚類的個數(shù)為11，最近鄰個數(shù)的取值范圍為（5～60）。實驗結果如圖4所示。

通過實驗對比分析，本文算法與其他三種算法在不同的近鄰數(shù)n下的實驗結果，本文提出的算法取得MAE最小，即推薦結果的準確度最高。幾種算法均使用聚類思想，但其余三種僅利用用戶—項目評分矩陣，沒有充分利用用戶潛在信息，造成最近鄰居選取不準確，降低了推薦結果的準確性。而本文充分利用用戶自身的評分偏好形成用戶偏好—項目矩陣，并在此基礎上利用麻雀搜索的用戶聚類算法進行聚類，增強了聚類效果，大大提高了最近鄰選取的準確度。最后，使用用戶相似度模型進行評分預測并做出推薦，進一步提高推薦結果準確性。

4 結論

本文提出的基于用戶偏好和麻雀搜索聚類的協(xié)同過濾算法充分運用用戶偏好的潛在信息，在預測階段，改善了聚類過程初始聚類中心敏感的問題，大大降低算法的計算量，提高了在稀疏矩陣上預測的準確度。在推薦準確率上，UPSSCA-CF優(yōu)于傳統(tǒng)的基于用戶的協(xié)同過濾算法和傳統(tǒng)的基于聚類的協(xié)同過濾算法。本文算法雖然在一定程度上緩解了評分數(shù)據(jù)稀疏性對推薦結果的影響，但由于用戶的興趣愛好存在時間周期性，即同一用戶對同一商品的評分在不同時間段是不一樣的，下一步在改進算法時考慮用戶興趣隨時間的偏移帶來的影響，以提高推薦準確率。

參考文獻

[1]XU H L， WU X， LI X D， et al. Comparison study of internet recommendation system[J].Journal of Software，2009，20（2）：350-362.

[2]DENG A， ZHU Y Y， SHI B. A collaborative filtering recommendation algorithm based on item rating prediction[J]. Journal of Software，2003，14（9）：1621-1628.

[3]HU X， LU H R， CHEN X， et al. K-means item clustering recommendation algorithm with initial clustering center optimized[J]. Journal of Air Force Radar Academy，2014（3）：203-207.

[4]XIONG Z Y， ZHANG FJ， ZHANG Y F. Item clustering recommendation algorithm based on particle swarm optimization[J]. Computer Engineering，2009，35（23）：178-180.

[5]XIA H. Research on recommendation algorithm of matrix factorization method based on mapReduce[J]. Applied Mechanics & Materials， 2014， 631-632：138-141.

[6]WU B， LOU Z Z， YE Y D. Co-regularized matrix factorization recommendation algorithm[J].Journal of Software，2018，29（9）：2681-2696.

[7]SHI J P， LI J， HE F Z. Diversity recommendation approach based on social relationship and user preference[J].Computer Science，2018，45（Z6）：423-427.

[8]ZHOU Y Q， XIE Z C. Improved artificial fish-school swarm algorithm for solving TSP[J]. Systems Engineering & Electronics， 2009， 31（6）：1458-1461.

[9]趙亞輝， 劉瑞. 基于評論的隱式社交關系在推薦系統(tǒng)中的應用[J]. 計算機應用研究， 2016， 33（6）：1628-1632.

[10] 林甲祥，高敏節(jié)，陳崇成，等.個性化旅游景點推薦中考慮約束的關聯(lián)規(guī)則挖掘算法[J].福州大學學報（自然科學版），2019，47（3）：320-326.

[11] 王衛(wèi)紅，曾英杰.基于聚類和用戶偏好的協(xié)同過濾推薦算法[J].計算機工程與應用， 2020，56（3）： 68-73.

[12] 王興茂，張興明，吳毅濤，等.基于啟發(fā)式聚類模型和類別相似度的協(xié)同過濾推薦算法[J].電子學報，2016（7）：1708-1713.

[13] 李改，陳強，李磊.基于評分預測與排序預測的協(xié)同過濾推薦算法[J].電子學報，2017（12）：3070-3075.

[14] 呂誠.基于用戶相似度的加權項目偏差SlopeOne協(xié)同過濾推薦算法[J].南昌大學學報（理科版），2014（4）：342-347.

[15] 郝雅嫻，孫艷蕊.K-近鄰矩陣分解推薦系統(tǒng)算法[J].小型微型計算機系統(tǒng)，2018，39（4）：755-758.

[16] 黃國言，李有超，高建培，等.基于項目屬性的用戶聚類協(xié)同過濾推薦算法[J].計算機工程與設計，2010，31（5）：1038-1041.

[17] 周超，孫英華，熊化峰，等.基于用戶和項目雙向聚類的協(xié)同過濾推薦算法[J].青島大學學報（自然科學版），2018，31（1）：55-60.

[18] 孫蘭蘭.基于用戶協(xié)同過濾的近鄰選擇算法[J].青島大學學報（自然科學版），2018，31（2）：116-120.

[19] REN P.TV recommender system based on confidence user preferencemodel[J].Modern Electronic Technique，2014（16）：30-33.

[20] XUE J， SHEN B. A novel swarm intelligence optimization approach： sparrow search algorithm[J]. Systems ence & Control Engineering An Open Access Journal， 2020， 8（1）：22-34.

[21] 王穎，王欣，唐萬梅.融合用戶自然最近鄰的協(xié)同過濾推薦算法[J].計算機工程與應用，2018，54（7）：77-83.