王曉云

摘要： 針對以往的推薦算法中存在的“冷啟動”和“數(shù)據(jù)稀疏性”問題提出了一種QPSO（Quantum behaved Particle Swarm Optimization）聚類與協(xié)同過濾相結(jié)合的推薦算法。該算法首先用QPSO 聚類產(chǎn)生中心聚點來解決模糊C均值聚類中初始聚類中心選擇問題，并引入罰函數(shù)的思想來確立目標函數(shù)，再聯(lián)合項目隸屬度矩陣和稀疏的用戶項目評分矩陣構(gòu)造出用戶項目簇矩陣。最后使用協(xié)同過濾算法對用戶項目簇矩陣進行處理，得到目標用戶的推薦項目集合。使用平均絕對誤差和綜合評價指標F對該算法進行驗證，實驗結(jié)果表明，該算法不僅解決了傳統(tǒng)FCM（Fuzzy c-means）算法初始中心選擇問題，還解決了協(xié)同過濾推薦中存在的數(shù)據(jù)稀疏和冷啟動問題，推薦精度也得到了極大提高。

關(guān)鍵詞： 量子粒子群算法;模糊C均值聚類;協(xié)同過濾;視頻推薦

中圖分類號：TP3? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）18-0284-04

Abstract： Aiming at the "cold start" and "data sparsity" problems in the previous recommendation algorithms， a recommendation algorithm combining QPSO clustering and collaborative filtering is proposed. Firstly， the algorithm uses QPSO clustering to generate the central clustering point to solve the initial clustering center selection problem in fuzzy C-means clustering， And introduce the idea of penalty function to establish the objective function .Then joint project membership matrix and the sparse user project scoring matrix construct the user project cluster matrix. Finally， the collaborative clustering algorithm is used to process the user project cluster matrix to obtain the recommended project set of the target user. The algorithm is validated by MAE（mean absolute error）and comprehensive evaluation index F. The experimental results show that the algorithm not only solves the initial center selection problem of traditional FCM（Fuzzy c-means）algorithm， but also solves the problem of data sparseness and cold start in collaborative filtering recommendation. The recommendation accuracy is also greatly improved.

Key words： QPSO algorithm; FCM; Collaborative filtering; recommended algorithm

1 引言

互聯(lián)網(wǎng)中充斥著各種各樣的信息，用戶信息在獲取信息的過程中，往往存在以下幾個問題：用戶在潛意識中更傾向于被動接受而不是主動挖掘新的信息;用戶對于自己想要主動獲取的信息并不能完整的進行描述;總之用戶在龐大的信息量下能發(fā)揮的主觀能動性是非常有限的，這時就需要借助推薦算法。推薦算法的出現(xiàn)一方面可以提高用戶體驗，另一方面也為商家對于產(chǎn)品和信息的推廣助力。

目前的推薦算法主要分為三類：基于人口的統(tǒng)計學(xué)推薦主要利用已有的用戶統(tǒng)計信息粗略的進行推薦;基于內(nèi)容的推薦算法根據(jù)用戶之前的瀏覽記錄，推薦元數(shù)據(jù)中含有與之前記錄中具有相似標簽的項目，不存在冷啟動和數(shù)據(jù)稀疏性問題，但是需要對文件進行建模和特征提取并且只關(guān)注到了項目之間的相似性而忽略了用戶行為。協(xié)同過濾基本原理就是“物以類聚”即把相似的內(nèi)容推薦給同一用戶;“人以群分”給具有相似愛好的用戶推薦同一類內(nèi)容，能夠從大數(shù)據(jù)中挖掘用戶的潛在喜好。

針對數(shù)據(jù)稀疏性問題，主要解決方案分為三類，缺失值填充法[1]，對未評分項目設(shè)定缺省值來填充用戶項目矩陣，填充的數(shù)據(jù)容易忽略特殊性;降維法[2]，通過降低用戶-項目矩陣的維度，因為需要摒棄一些用戶和項目數(shù)據(jù)，推薦精準率受損;聚類法;聚類技術(shù)通過對項目或用戶進行聚類來縮小最近鄰居的查詢范圍。目前，基于聚類的協(xié)同過濾，Sarwar等人[3][4]以目標用戶所在的類簇作為其最近鄰居集 ，然后在鄰居集上進行推薦。Rashid等人[5]首先通過聚類技術(shù)生成目標用戶最相似的代理用戶，然后利用代理用戶尋找目標用戶的最近鄰居。鄧愛林等人[6]以目標項目最相似性的若干個聚類中心尋找目標項目的最近鄰居集。張海燕等人[7]引入了項目屬性特征信息進行模糊聚類。葛林濤等人[8]依據(jù)不同的聚類有效性函數(shù)確定合理的聚類區(qū)間，并在此區(qū)間尋找最佳聚類數(shù)。

針對以往FCM算法存在對初始值敏感且容易陷入局部最優(yōu)的缺點，引入了量子粒子群算法，結(jié)合量子粒子群算法中罰函數(shù)思想把這兩個算法的迭代尋優(yōu)過程轉(zhuǎn)化為解決QPSO算法用于解決非線性約束優(yōu)化的問題，利用產(chǎn)生的目標函數(shù)得到項目聚類結(jié)果，將得到的聚類結(jié)果作為被推薦用戶的相似用戶群進行協(xié)同過濾。

2 基本定義

2.1 QPSO算法

粒子群優(yōu)化算法是在1995年由Eberhart和Kennedy[9]提出，受到鳥群覓食行為的啟發(fā)，利用個體在群體中的信息共享與借鑒，達到群體最優(yōu)的效果。優(yōu)化問題的每個解都可以抽象為一個粒子，定義粒子[i]的位置向量為[Xi=（xi1，xi2，...，xin）]，速度向量為[Vi=（vi1，vi2，...，vin）]，粒子的迭代形式如式1和式2所示：

其中[n]表示優(yōu)化問題的維度;[Pbesti]表示粒子[i]此刻歷史最佳位置，[Gbest]表示群體歷史最佳位置;[ω]是慣性權(quán)重因子，用于調(diào)節(jié)全局和局部的搜索能力所占比重;[c1]，[c2]表示學(xué)習(xí)因子，分別負責(zé)調(diào)節(jié)粒子向[Pbesti]和[Gbest]的步長;[r1]，[r2]為概率隨機因子。

QPSO基于量子學(xué)中量子勢場的原理，粒子處于量子束縛態(tài)時可以出現(xiàn)在空間中的任何點，因此可以建立一個吸引勢場來束縛粒子，這就解決了PSO算法中粒子收斂時只能以軌道形式出現(xiàn)，收斂速度較慢，已陷入局部最優(yōu)無法確認全局最優(yōu)等缺點。處于量子束縛態(tài)的粒子參數(shù)較少，只有位置向量而沒有速度向量，粒子的速度由個體的經(jīng)驗和群體的經(jīng)驗動態(tài)調(diào)整，并且在搜索能力上優(yōu)于已開發(fā)的PSO算法。主要按照以下三個公式進行進化：

其中M表示粒子總數(shù)，D表示粒子的維數(shù);[Pi（t）] ，[Pgj（t）]分別表示第[i]個粒子[t]次迭代時的個體最佳位置和全局最優(yōu)位置;[mbest]表示所有粒子個體最好位置的平均位置[fij（t+1）=radf（）]，[uij（t+1）=radf（）];函數(shù)[radf（）]是[0，1]服從均勻分布的隨機數(shù)，[Rand（t+1）=-1，radf（）≤0.5+1，radf（）>0.5];[α]稱作收縮-擴張系數(shù)，用于表達算法的收斂性，一般采用固定取值和線性減小取值。[α]的表達式如式8所示：

2.2 FCM算法描述

1973年由Bezdek[10]提出，F(xiàn)CM把[n]個向量[Xi（i=1，2，...n）]分為[c]組，[ci]表示第[i]類的中心;用隸屬度[uij]來表示特征點[xj]屬于第[i]個聚類的程度，在[0，1]取值。根據(jù)求得的聚類中心計算個體與聚類中心的距離，使得評價指標的價值函數(shù)取最優(yōu)值。本文選用第[i]個數(shù)據(jù)中心與第[j]個數(shù)據(jù)點間的歐幾里得距離[dij=ci-xj]做為衡量相似性的標準。將數(shù)據(jù)集的隸屬度歸一化后的總和為1，如式9所示：

2.3 量子粒子群聚類算法

FCM算法是一種依靠梯度下降的局部搜索算法，具有運算簡單高速的優(yōu)點，但是也存在過于依賴聚類中心的初始值和容易陷入局部最優(yōu)的缺點，本文中引入QPSO來快速確定初始聚類中心并且利用QPSO優(yōu)秀的全局尋優(yōu)能力來防止FCM算法容易陷入局部最優(yōu)的現(xiàn)象。

（1）目標函數(shù)的確定

模糊聚類問題本質(zhì)上是一個非線性約束優(yōu)化問題，約束函數(shù)的連續(xù)性和可導(dǎo)性較差因此采用隨機性方法[11]。本文采用罰函數(shù)[12]的思想將約束問題通過序列無序最小化技術(shù)轉(zhuǎn)化為無約束問題，廣義的目標函數(shù)形式如式14：

（2）算法的實現(xiàn)過程

種群由M個粒子構(gòu)成，每個粒子[Xi=Vij（j=1，2，...，c）]表示一種聚類結(jié)果，[Vij]表示粒子[i]的第[j]個中心坐標，[c]表示聚類數(shù)目。

1使用QPSO進行隨機初始化，生成包含M個粒子的粒子群，初始化粒子歷史最優(yōu)位置和全局最優(yōu)位置;

2使用FCM算法中的式13計算項目隸屬度矩陣，并根據(jù)式17計算粒子的適應(yīng)值;

3根據(jù)式6，7更新粒子的最優(yōu)位置和群體的最優(yōu)位置，根據(jù)式3計算[mbest]，根據(jù)式4計算粒子的吸引子，根據(jù)式5更新粒子的位置;

4重復(fù)3，直到達到規(guī)定的目標函數(shù)值或者最大迭代次數(shù)。

3 推薦流程

3.1 概念與定義

基于用戶的協(xié)同過濾算法的基本思想是：尋找與該用戶具有相似偏好的用戶，給該用戶推薦相似用戶喜歡且該用戶沒有進行評價過的物品。目前衡量物品相似度主要有歐氏距離，余弦相似性，和皮爾遜相關(guān)系數(shù)。由于實際應(yīng)用數(shù)值存在不同用戶的取值范圍差異過大，初始值缺失等情況，能夠較好地擬合不同用戶的數(shù)據(jù)，文采用了皮爾遜相關(guān)系數(shù)來進行用戶相似度的計算以便能夠較好地擬合不同用戶的數(shù)據(jù);

3.2 推薦流程

（1）根據(jù)所需要評價的項目屬性構(gòu)造出稀疏的項目屬性矩陣用A表示。

（2）對項目屬性矩陣執(zhí)行1.3描述的QPSO-FCM算法使項目分為C個聚類簇，[C=（C1，C2，...Cc）];根據(jù)公式13計算出項目隸屬度矩陣S，[S=（ST1，ST2，....，STc）T]，[Si=（Si1，Si2，...，Sic）]，[Sij]表示項目[i]對于項目簇[j]的隸屬程度。

（3）對隸屬度矩陣[S]進行預(yù)處理，每行的最大值作為該項目的最終隸屬簇 ，如式20所示：

（4）根據(jù)式（21）計算用戶項目簇矩陣U-S*，其中[ri，k]表示用戶[ui]對項目[Ik]的評分值，[Iu]表示項目簇[Cj]中用戶[ui]評價過的項目集合。

（4）根據(jù)式18計算用戶的相似度，選取Top-K用戶作為目標用戶的最近鄰居集合，使用式19對項目進行評分預(yù)測，推薦評分Top-N的項目給該用戶。

4 仿真與驗證

4.1 數(shù)據(jù)來源與評價標準

實驗數(shù)據(jù)集由movielens網(wǎng)站提供的1M數(shù)據(jù)

集ml-latest-small.zip對算法進行驗證，該數(shù)據(jù)集擁有270，000個用戶對45，000部電影的26，000，000個評分和750，000個電影屬性標簽。數(shù)據(jù)集中包含的Movie.CSV文件為生成項目屬性矩陣提供原始數(shù)據(jù)，Rating.CSV為生成用戶-項目評分矩陣提供原始數(shù)據(jù)。數(shù)據(jù)稀疏度表示為：

P表示用戶評分數(shù)量，U表示用戶數(shù)量，I表示項目數(shù)量。本次時延數(shù)據(jù)集的稀疏度為0.9979。根據(jù)試驗需要將20%的數(shù)據(jù)作為測試集，80%作為訓(xùn)練集。

本文對推薦結(jié)果采用的評價標準為：（1）統(tǒng)計精度度量方法，平均絕對偏差（MAE）[13]（2）決策支持精度度量方法，常用的召回率（Recall）[14]準確率（Precision）[15]等。在視頻推薦系統(tǒng)中MAE表示預(yù)測的用戶評分與實際用戶評分的偏差度;Recall表示命中的數(shù)目與測試集的大小的比例，Precision表示推薦命中的數(shù)目與Top-N數(shù)目的比例，用公式表示如下。

4.2 實驗結(jié)果

本文仿真采用數(shù)據(jù)集中電影所屬類別作為項目屬性，根據(jù)文獻[16]中提出的方法確定本文的最佳聚類數(shù)[c=30]，在此基礎(chǔ)上實現(xiàn)了基于QPSO模糊聚類的協(xié)同過濾推薦算法，與其他算法運行結(jié)果對比如下：

4.3 結(jié)果分析

從實驗結(jié)果的MAE來看，本文提出的算法相比于傳統(tǒng)的聚類算法，在最近鄰個數(shù)相同的情況下可以得到較優(yōu)的推薦結(jié)果，且在最近鄰居個數(shù)不同的情況下能夠保持推薦質(zhì)量的穩(wěn)定性，很好的解決傳統(tǒng)算法存在的冷啟動和數(shù)據(jù)稀疏的問題。同時證明了相比于其他聚類算法FCM與QPSO結(jié)合更能發(fā)揮出QPSO算法的優(yōu)勢。觀察綜合指標F的仿真結(jié)果可發(fā)現(xiàn)本文提出的算法推薦效果較好，達到了預(yù)期目的。

5 結(jié)束語

推薦算法的使用已經(jīng)成為互聯(lián)網(wǎng)應(yīng)用提高用戶體驗，獲得更多用戶群體的主要手段之一。考慮實際推薦情景中存在的“冷啟動”，“數(shù)據(jù)稀疏”這兩大問題，本文提出一種全新的高效的推薦算法。首先使用QPSO算法與FCM算法結(jié)合，引入罰函數(shù)的思想來確立QPSO-FCM聯(lián)合算法的目標函數(shù)，來解決傳統(tǒng)的FCM算法中初始聚類中心劃分的問題，稀疏的用戶-項目矩陣與項目屬性矩陣進過一系列計算最終得到項目-項目簇隸屬矩陣與稀疏度遠低與原始數(shù)據(jù)的用戶-項目簇矩陣;根據(jù)用戶-項目簇矩陣使用協(xié)同過濾算法中的相似度計算公式算出該用戶的top-N相似用戶，再根據(jù)項目-項目簇隸屬矩陣選擇項目進行推薦。該算法在時間復(fù)雜度和推薦結(jié)果精度上遠優(yōu)于傳統(tǒng)推薦算法。

使用MAE和綜合指標F作為評價標準，本文提出的算法得到了較好的結(jié)果。但是在最佳聚類數(shù)目的選擇上需要進一步的改進和大量的實驗數(shù)據(jù)驗證來得到更加嚴謹?shù)慕Y(jié)果，進而發(fā)揮該算法的最大優(yōu)勢，同時在其他類型數(shù)據(jù)上的推薦效果有待進一步驗證。

參考文獻：

[1] Sarwar B M. Sparsity， scalability， and distribution in recommender systems[M]. University of Minnesota， 2001.

[2] OConnor M， Herlocker J. Clustering items for collaborative filtering[C]//Proceedings of the ACM SIGIR workshop on recommender systems. UC Berkeley， 1999， 128.

[3] Good N， Schafer J B， Konstan J A， et al. Combining collaborative filtering with personal agents for better recommendations[C]//AAAI/IAAI. 1999： 439-446.

[4] Sarwar B M， Konstan J A， Borchers A， et al. Using filtering agents to improve prediction quality in the grouplens research collaborative filtering system[C]//Proceedings of the 1998 ACM conference on Computer supported cooperative work. ACM， 1998： 345-354.

[5] Rashid A M， Albert I， Cosley D， et al. Getting to know you： learning new user preferences in recommender systems[C]//Proceedings of the 7th international conference on Intelligent user interfaces. ACM， 2002： 127-134.

[6] 鄧愛林， 左子葉， 朱揚勇. 基于項目聚類的協(xié)同過濾推薦算法[J]. 小型微型計算機系統(tǒng)， 2004， 25（9）： 1665-1670.

[7] 張海燕，丁峰，姜麗紅.基于模糊聚類的協(xié)同過濾推薦方法[J].計算機仿真，2005（08）：144-147.

[8] 葛林濤， 徐桂瓊. 基于模糊 C 均值聚類有效性的協(xié)同過濾算法[J]. 計算機技術(shù)與發(fā)展， 2016 （01）： 22-26， 32.

[9] Eberhart R， Kennedy J. A new optimizer using particle swarm theory[C]//Micro Machine and Human Science， 1995. MHS'95.， Proceedings of the Sixth International Symposium on. IEEE， 1995： 39-43.

[10] Bezdek J C， Ehrlich R， Full W. FCM： The fuzzy c-means clustering algorithm[J]. Computers & Geosciences， 1984， 10（2-3）： 191-203.

[11] Fogel D B. An introduction to simulated evolutionary optimization[J]. IEEE Trans Neural Netw， 1994， 5（1）：3-14.

[12] Yeniay ?. Penalty function methods for constrained optimization with genetic algorithms[J]. Mathematical and computational Applications， 2005， 10（1）： 45-56.

[13] 鄧愛林， 朱揚勇， 施伯樂. 基于項目評分預(yù)測的協(xié)同過濾推薦算法[J]. 軟件學(xué)報， 2003， 14（9）：1621-1628.

[14] Chedrawy Z， Abidi S S R. An adaptive personalized recommendation strategy featuring context sensitive content adaptation[C]// International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems. Springer-Verlag， 2006：61-70.

[15] Goldberg K， Roeder T， Gupta D， et al. Eigentaste： A Constant Time Collaborative Filtering Algorithm[J]. Information Retrieval， 2001， 4（2）：133-151.

[16] 于劍， 程乾生. 模糊聚類方法中的最佳聚類數(shù)的搜索范圍[J]. 中國科學(xué)：技術(shù)科學(xué)， 2002， 32（2）：274-280.

【通聯(lián)編輯：代影】