一種基于NSGA-II的協(xié)同過濾推薦算法

摘要：為了提升幾種基本的協(xié)同過濾推薦算法的精確度與召回率，引入了多目標(biāo)遺傳優(yōu)化算法NSGA-II，并利用模型加權(quán)融合的方法實(shí)現(xiàn)了新的協(xié)同過濾算法。實(shí)驗(yàn)證明，該算法相較幾種基本的協(xié)同過濾算法在精確度與召回率上均有所提升。

　　個(gè)性化推薦系統(tǒng)是近年來解決信息超載問題一個(gè)有效途徑,它根據(jù)用戶的信息需求、興趣等歷史行為，主動向用戶推薦其可能感興趣的產(chǎn)品或者信息。不同于用戶利用搜索引擎進(jìn)行主動檢索，推薦系統(tǒng)通過收集用戶的興趣偏好，進(jìn)行個(gè)性化計(jì)算，由系統(tǒng)發(fā)現(xiàn)用戶的興趣點(diǎn)，從而引導(dǎo)用戶被動發(fā)現(xiàn)自己的信息需求。推薦系統(tǒng)根據(jù)用戶興趣和行為特點(diǎn)，向用戶推薦所需的信息或商品，幫助用戶在過載信息中快速發(fā)現(xiàn)真正所需的商品，提高用戶黏性，促進(jìn)信息點(diǎn)擊和商品銷售。

　　現(xiàn)階段廣泛利用推薦系統(tǒng)的領(lǐng)域包括電子商務(wù)、視頻、音樂、社交網(wǎng)絡(luò)、閱讀、基于位置的服務(wù)、個(gè)性化郵件和廣告等。如著名的電子商務(wù)網(wǎng)站亞馬遜，推薦系統(tǒng)深入到了其各類產(chǎn)品中，其中最主要的應(yīng)用有個(gè)性化商品推薦列表和相關(guān)商品的推薦列表。

　　目前常用的推薦算法有基于鄰域的算法與矩陣分解算法^[1]，而基于鄰域的算法又被分為基于用戶的協(xié)同過濾算法(UserCF)與基于物品的協(xié)同過濾算法(ItemCF)^[5]。而根據(jù)常用的評測指標(biāo)精確度(Precision)和召回率(Recall)來看，每種算法均不能在兩個(gè)指標(biāo)上獲取較好的結(jié)果，所以推薦過程中單獨(dú)利用某一種推薦算法都存在一定的局限性。

1 常用推薦算法介紹

1.1 基于鄰域的算法

1.1.1 基于用戶的協(xié)同過濾算法

　　基于用戶的算法分為兩步：首先，找到和目標(biāo)用戶興趣相似的用戶集合，然后找到這個(gè)集合中用戶喜歡的，且目標(biāo)用戶沒有聽過的物品推薦給目標(biāo)用戶^[2]。圖1為基于用戶的協(xié)同過濾推薦原理圖。

　　基于用戶的協(xié)同過濾算法推薦過程分為三步：

　　1.根據(jù)公式1計(jì)算用戶u與用戶v的相似度。

(1)

　　2.根據(jù)用戶相似度，對每個(gè)用戶獲取其固定數(shù)量的相似用戶。

　　3.根據(jù)公式2推算用戶u對物品i的感興趣程度。

(2)

1.1.2 基于物品的協(xié)同過濾算法

　　基于物品的算法也分為兩步:首先，計(jì)算物品之間的相似度，然后根據(jù)物品的相似度和用戶的歷史行為給用戶生成推薦列表[3]。圖2為基于物品的協(xié)同過濾推薦原理圖。

　　基于物品的協(xié)同過濾算法推薦過程分為兩步：

　　1.根據(jù)公式3通過改進(jìn)的余弦相似度公式計(jì)算物品i與物品j的相似度

(3)

　　2.根據(jù)公式4預(yù)測用戶 對物品 的感興趣程度

(4)

1.2 矩陣分解法

　　從矩陣分解角度來說，就是將評分矩陣 分解為兩個(gè)低維矩陣相乘，如公式5所示：

(5)

　　其中P∈R^f×m和Q∈R^f×n是兩個(gè)降維之后的矩陣。用戶因子矩陣表示第u個(gè)用戶對第k個(gè)因子的喜好程度，物品因子矩陣表示第i個(gè)物品中第k個(gè)因子的程度。在圖書推薦系統(tǒng)中，圖書因子可以理解為：圖書的薄厚，距今年代是否久遠(yuǎn)，體裁是小說還是詩歌等。

　　如公式6所示，第u個(gè)用戶對第i個(gè)物品的預(yù)測評分值為：

(6)

　　由于每種算法只能在一個(gè)評測指標(biāo)上獲取較好的結(jié)果，而不能在多個(gè)評測指標(biāo)上獲得突出表現(xiàn)，所以單獨(dú)采用任何一種推薦算法都具有其局限性，所以我們引入多目標(biāo)優(yōu)化遺傳算法對幾種常用推薦算法做了一個(gè)線性加權(quán)操作。

2 NSGA-П算法簡介

　　單目標(biāo)優(yōu)化研究的是單個(gè)目標(biāo)函數(shù)的極值問題, 多目標(biāo)優(yōu)化則要同時(shí)優(yōu)化多個(gè)、可能相互沖突的目標(biāo)函數(shù)，而實(shí)際中的推薦系統(tǒng)就是一個(gè)多目標(biāo)并存的系統(tǒng)。UserCF、ItemCF和MF是推薦系統(tǒng)的三個(gè)基礎(chǔ)算法，在解決在面對多目標(biāo)問題時(shí)往往不能給出相對優(yōu)化的解。

　　NSGA-Ⅱ算法在強(qiáng)大的參數(shù)相互作用下，依然能得到比其他多目標(biāo)遺傳算法更接近于優(yōu)化前沿的解。實(shí)際運(yùn)算證明，該算法能夠較好地解決實(shí)際過程的多目標(biāo)優(yōu)化問題，對此我們提出將NSGA-Ⅱ算法結(jié)合多種基礎(chǔ)推薦算法應(yīng)用在推薦系統(tǒng)中。

　　NGSA-II算法流程：

　　首先初始化種群，再將初始化后的種群在各等級內(nèi)進(jìn)行非支配排序。第一級被完全非支配在當(dāng)前的種群，第二級被第一級內(nèi)的個(gè)體支配，接下來也是。每個(gè)等級的個(gè)體被指定等級(適應(yīng)度)或者根據(jù)個(gè)體所在的等級分配。第一等級的個(gè)體是一級適應(yīng)度，在第二等級的個(gè)體是二級適應(yīng)度等。

　　除了適應(yīng)度，每個(gè)個(gè)體都要計(jì)算一個(gè)新的參數(shù)—擁擠距離[4]。擁擠距離是用來衡量個(gè)體和附近個(gè)體之間的距離值。越大的平均擁擠距離表明種群分布越多樣。

　　根據(jù)適應(yīng)度和擁擠距離，一定數(shù)量的父代種群通過二進(jìn)制錦標(biāo)賽法(種群中被選中的個(gè)體等級比別的個(gè)體小，或者在等級相同的情況下?lián)頂D距離大于別的個(gè)體)從所有種群中選出。選中的個(gè)體經(jīng)過交叉和變異等操作產(chǎn)生同數(shù)量的后代群體。

　　N為種群規(guī)模，目前的種群加上產(chǎn)生的子代將再次根據(jù)適應(yīng)度和擁擠距離被非支配排序，只有最優(yōu)的前N個(gè)個(gè)體會被選中，其他的將被淘汰。

　　然后再次迭代整個(gè)過程，直到達(dá)到最大迭代次數(shù)后退出循環(huán)，取其前最優(yōu)的N個(gè)作為最終解。

3 NSGA-П算法在推薦算法中的應(yīng)用

3.1 權(quán)重系數(shù)的初始化

R₁'、R₂'和R₃'是三種不同的推薦系統(tǒng)算法ItemCF、UserCF和MF得出的三組推薦列表。三組列表推薦方式不同，得出多目標(biāo)函數(shù)值也不同。為了得出多目標(biāo)均較優(yōu)的推薦結(jié)果，利用線性加權(quán)的方法可得到新的預(yù)測評分R''如公式7所示：

(7)

　　其中，λ1, λ2和λ3分別為各數(shù)據(jù)集所代表算法的權(quán)重系數(shù)，并且λ1+λ2+λ3=1。

　　根據(jù)λ1和λ2的值，得出對應(yīng)的推薦列表，計(jì)算每組權(quán)重系數(shù)對應(yīng)的各目標(biāo)函數(shù)值。

3.2 非支配和擁擠距離排序

　　將當(dāng)前權(quán)重系數(shù)種群進(jìn)行非支配排序，每個(gè)權(quán)重系數(shù)被分配到各個(gè)等級中，得到等級變量。然后計(jì)算同一等級內(nèi)，根據(jù)每組權(quán)重系數(shù)的多目標(biāo)函數(shù)值，計(jì)算擁擠距離，根據(jù)結(jié)果進(jìn)行排序。由此產(chǎn)生了整個(gè)種群的排序結(jié)果。

　　判斷當(dāng)前種群數(shù)量是否超過額定種群數(shù)量N，如是，則選取排序列表中前N個(gè)作為本代的結(jié)果。

3.3 子代權(quán)重系數(shù)的產(chǎn)生

　　在遺傳算法中，兩個(gè)父母代可以通過基因重組和遺傳變異產(chǎn)生新的子代。包括以下三個(gè)基本遺傳算子：選擇、交叉和變異[7]。

　　1、選擇。隨機(jī)選取兩組不同的權(quán)重系數(shù)作為父代和母代，λ_p11λ_p12和λ_p21λ_p22。

　　2、交叉。設(shè)置交叉系數(shù)為1，父代和母代在子代中所占的比例相同。故可定義產(chǎn)生的子代權(quán)重系數(shù)為：

(8)

(9)

　　3、變異。實(shí)際中，遺傳變異是個(gè)小概率事件，故考慮設(shè)置變異系數(shù)。每當(dāng)要產(chǎn)生子代前，隨機(jī)產(chǎn)生一個(gè)0到1之間的數(shù)，若該數(shù)小于變異系數(shù)，則發(fā)生遺傳變異，否則跳過此部分。遺傳變異的過程產(chǎn)生的新權(quán)重系數(shù)為：

(10)

(11)

　　產(chǎn)生新的權(quán)重系數(shù)后，再進(jìn)行排序和更新種群，篩選出M 個(gè)最優(yōu)個(gè)體。如此反復(fù)進(jìn)行迭代，不斷產(chǎn)生新的權(quán)重系數(shù)和種群。

4 實(shí)驗(yàn)設(shè)計(jì)與實(shí)驗(yàn)結(jié)果

4.1 評測指標(biāo)

　　本文中選擇了精確度和召回率作為評價(jià)的主要標(biāo)準(zhǔn)。

　　令R(u)是根據(jù)用戶在訓(xùn)練集上的行為給用戶做出的推薦列表，而T(u)是用戶在測試集上的行為列表。

　　那么，推薦結(jié)果的召回率定義為：

(12)

　　推薦結(jié)果的精確度定義為：

(13)

4.2 實(shí)驗(yàn)設(shè)計(jì)

　　(1) 實(shí)驗(yàn)數(shù)據(jù)

　　本文中利用的數(shù)據(jù)是MovieLens數(shù)據(jù)集，用戶對自己看過的電影進(jìn)行評分，分值為1～5，該數(shù)據(jù)是943個(gè)獨(dú)立用戶對1682部電影作的100000次評分的數(shù)據(jù)，其中每個(gè)用戶至少對20個(gè)物品進(jìn)行了評分^[6]。

　　(2) 算法實(shí)現(xiàn)

　　全文的算法設(shè)計(jì)包括以下三個(gè)步驟：

　　1、基礎(chǔ)算法的實(shí)現(xiàn);

　　2、多目標(biāo)遺傳算法—NSGA-П的實(shí)現(xiàn);

　　3、綜合算法的整體實(shí)現(xiàn)。

　　1、基礎(chǔ)算法的實(shí)現(xiàn)

　　ItemCF的實(shí)現(xiàn)：數(shù)據(jù)集的讀入、各物品之間的相似度的計(jì)算以及最終推薦列表的獲得。其中，在獲取推薦列表時(shí)，選取N個(gè)與目標(biāo)物品最相似的物品的過程中，N的值并不固定。取值規(guī)則為，從5-20中選取使得其精確度與召回率最高的那個(gè)值作為N。

　　UserCF的實(shí)現(xiàn)：數(shù)據(jù)集的讀入、各用戶之間的相似度的計(jì)算以及最終推薦列表的獲得。其中，在獲取推薦列表時(shí)，選取N個(gè)與目標(biāo)用戶最相似的用戶的過程中，N的值并不固定。取值規(guī)則為，從5-20中選取使得其精確度與召回率最高的那個(gè)值作為N。

　　MF的實(shí)現(xiàn)：實(shí)現(xiàn)過程包括：數(shù)據(jù)集的讀入、矩陣P與Q的初始化，各用戶負(fù)樣本的設(shè)定。對數(shù)據(jù)集進(jìn)行訓(xùn)練迭代一定的步數(shù)，當(dāng)誤差達(dá)到局部最小或者迭代步數(shù)達(dá)到設(shè)置時(shí)退出訓(xùn)練，利用得到的矩陣P與Q獲取最終的推薦列表。

　　2 多目標(biāo)遺傳算法的實(shí)現(xiàn)

　　多目標(biāo)遺傳算法的實(shí)現(xiàn)包括以下幾個(gè)部分：

　　(1)隨機(jī)產(chǎn)生100組權(quán)重系數(shù)λ₁和λ₂。

　　(2)讀入基礎(chǔ)算法的三組推薦表單，和

　　(3)編寫目標(biāo)函數(shù)和。

　　(4)NSGA-П主函數(shù)部分, 并在其中根據(jù)加權(quán)后的集合獲取最終的推薦表單。

　　(5)輸出10組最好的權(quán)重系數(shù)λ1和λ2，以及對應(yīng)的目標(biāo)函數(shù)值。

　　3 綜合算法的整體實(shí)現(xiàn)

　　對以上五個(gè)數(shù)據(jù)集隨機(jī)初始化100個(gè)權(quán)重系數(shù)，迭代10次，種群規(guī)模為10，交叉概率設(shè)置為1，變異概率設(shè)置為0.1。經(jīng)過交叉和變異，得到五個(gè)數(shù)據(jù)集的權(quán)重系數(shù)，每個(gè)數(shù)據(jù)集有10組最優(yōu)的λ₁和λ₂。對這五個(gè)數(shù)據(jù)集中的權(quán)重系數(shù)進(jìn)行加權(quán)取平均值，得到最終的10組λ₁和λ₂。最后在u1.test，u2.test，u3.test，u4.test，u5.test上重新測試，每組得到10組Recall和Precision值。

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

　　將基本算法得到的推薦表單代入計(jì)算程序，得到Recall和Precision值。表1為u1的實(shí)現(xiàn)結(jié)果。

　　分別對五組數(shù)據(jù)集，各隨機(jī)初始化100組權(quán)重系數(shù)，通過NSGA-П的交叉變異迭代10次，得到最終的10組權(quán)重系數(shù)。表2為ItemCF、UserCF和MF在數(shù)據(jù)集u1上得到的權(quán)重系數(shù)表。

　　從表2可知，多目標(biāo)最優(yōu)化的ItemCF、UserCF和MF分布，MF的權(quán)重值最大，幾乎占到一半，UserCF的權(quán)重值次之，ItemCF的權(quán)重值最小。

　　表3為u1測試集中基礎(chǔ)算法與加權(quán)融合算法計(jì)算出的Recall和Precision值。由表3可以看出在經(jīng)過多目標(biāo)優(yōu)化后，NSGA-П得出的推薦表單相比基礎(chǔ)算法在Recall和Precision值上都有了明顯的提升。

5 結(jié)束語

　　研究了推薦系統(tǒng)的相關(guān)算法。指出了常用推薦算法在多目標(biāo)優(yōu)化時(shí)的不足，然后提出了系數(shù)線性加權(quán)融的協(xié)同過濾推薦算法[8]。并利用NSGA-II算法針對其線性融合系數(shù)進(jìn)行求解，仿真結(jié)果表明加權(quán)融合算法得到的結(jié)果相較幾種基礎(chǔ)的協(xié)同過濾算法在Recall和Precision指標(biāo)上均有明顯的提升。

參考文獻(xiàn)：

　　[1]景民昌.從ACM RecSys2014國際會議看推薦系統(tǒng)的熱點(diǎn)和發(fā)展[J].現(xiàn)代情報(bào)，2015:41-45

　　[2]項(xiàng)亮，推薦系統(tǒng)實(shí)踐[M].北京:人民郵電出版社，2012

　　[3]Toby Segaran(著)，莫映，王開福(譯).集體智慧編程[M].北京:電子工業(yè)出版社，2009

　　[4]Kalyanmoy Deb，Amrit Pratap，Saeer Agarwal，and T.Meyarivan，A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II[J].IEEE，2002:182-187

　　[5]王曉耘，錢璐，黃時(shí)友.基于粗糙用戶聚類的協(xié)同過濾推薦模型[J].現(xiàn)代圖書情報(bào)技術(shù)，2015:45-51

　　[6]宋真真.協(xié)同過濾技術(shù)在個(gè)性化推薦中的應(yīng)用研究[D].合肥:合肥工業(yè)大學(xué)，2008

　　[7]吳蘭蘭.基于遺傳學(xué)方法的個(gè)性化推薦技術(shù)研究[D].沈陽:沈陽航空工業(yè)學(xué)院，2010

　　[8]Hao Wen，Liping Fang，Ling Guan.A hybrid approach for personalized recommendation of news on the Web [J].Expert Systems with Applications，2012:5806-5814

本文來源于中國科技期刊《電子產(chǎn)品世界》2016年第2期第57頁，歡迎您寫論文時(shí)引用，并注明出處。