QPSO與FCM融合的協(xié)同過(guò)濾推薦算法

王曉云

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

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

中圖分類號(hào)：TP3? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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)中充斥著各種各樣的信息，用戶信息在獲取信息的過(guò)程中，往往存在以下幾個(gè)問題：用戶在潛意識(shí)中更傾向于被動(dòng)接受而不是主動(dòng)挖掘新的信息;用戶對(duì)于自己想要主動(dòng)獲取的信息并不能完整的進(jìn)行描述;總之用戶在龐大的信息量下能發(fā)揮的主觀能動(dòng)性是非常有限的，這時(shí)就需要借助推薦算法。推薦算法的出現(xiàn)一方面可以提高用戶體驗(yàn)，另一方面也為商家對(duì)于產(chǎn)品和信息的推廣助力。

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

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

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

2 基本定義

2.1 QPSO算法

粒子群優(yōu)化算法是在1995年由Eberhart和Kennedy[9]提出，受到鳥群覓食行為的啟發(fā)，利用個(gè)體在群體中的信息共享與借鑒，達(dá)到群體最優(yōu)的效果。優(yōu)化問題的每個(gè)解都可以抽象為一個(gè)粒子，定義粒子[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í)因子，分別負(fù)責(zé)調(diào)節(jié)粒子向[Pbesti]和[Gbest]的步長(zhǎng);[r1]，[r2]為概率隨機(jī)因子。

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

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

2.2 FCM算法描述

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

2.3 量子粒子群聚類算法

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

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

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

（2）算法的實(shí)現(xiàn)過(guò)程

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

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

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

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

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

3 推薦流程

3.1 概念與定義

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

3.2 推薦流程

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

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

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

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

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

4 仿真與驗(yàn)證

4.1 數(shù)據(jù)來(lái)源與評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

4.3 結(jié)果分析

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

5 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

[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] 鄧愛林， 左子葉， 朱揚(yáng)勇. 基于項(xiàng)目聚類的協(xié)同過(guò)濾推薦算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2004， 25（9）： 1665-1670.

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

[8] 葛林濤， 徐桂瓊. 基于模糊 C 均值聚類有效性的協(xié)同過(guò)濾算法[J]. 計(jì)算機(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áng)勇， 施伯樂. 基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過(guò)濾推薦算法[J]. 軟件學(xué)報(bào)， 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]. 中國(guó)科學(xué)：技術(shù)科學(xué)， 2002， 32（2）：274-280.

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