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

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

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

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

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

1 常用推薦算法介紹

1.1 基于鄰域的算法

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

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

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

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

(1)

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

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

(2)

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

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

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

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

(3)

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

(4)

1.2 矩陣分解法

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

(5)

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

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

(6)

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

2 NSGA-П算法簡(jiǎn)介

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

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

　　NGSA-II算法流程：

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

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

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

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

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

3 NSGA-П算法在推薦算法中的應用

3.1 權重系數的初始化

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

(7)

　　其中，λ1, λ2和λ3分別為各數據集所代表算法的權重系數，并且λ1+λ2+λ3=1。

　　根據λ1和λ2的值，得出對應的推薦列表，計算每組權重系數對應的各目標函數值。

3.2 非支配和擁擠距離排序

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

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

3.3 子代權重系數的產(chǎn)生

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

　　1、選擇。隨機選取兩組不同的權重系數作為父代和母代，λ_p11λ_p12和λ_p21λ_p22。

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

(8)

(9)

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

(10)

(11)

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

4 實(shí)驗設計與實(shí)驗結果

4.1 評測指標

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

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

　　那么，推薦結果的召回率定義為：

(12)

　　推薦結果的精確度定義為：

(13)

4.2 實(shí)驗設計

　　(1) 實(shí)驗數據

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

　　(2) 算法實(shí)現

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

　　1、基礎算法的實(shí)現;

　　2、多目標遺傳算法—NSGA-П的實(shí)現;

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

　　1、基礎算法的實(shí)現

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

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

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

　　2 多目標遺傳算法的實(shí)現

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

　　(1)隨機產(chǎn)生100組權重系數λ₁和λ₂。

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

　　(3)編寫(xiě)目標函數和。

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

　　(5)輸出10組最好的權重系數λ1和λ2，以及對應的目標函數值。

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

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

4.3 實(shí)驗結果

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

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

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

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

5 結束語(yǔ)

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

參考文獻：

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

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

　　[3]Toby Segaran(著(zhù))，莫映，王開(kāi)福(譯).集體智慧編程[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]王曉耘，錢(qián)璐，黃時(shí)友.基于粗糙用戶(hù)聚類(lèi)的協(xié)同過(guò)濾推薦模型[J].現代圖書(shū)情報技術(shù)，2015:45-51

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

　　[7]吳蘭蘭.基于遺傳學(xué)方法的個(gè)性化推薦技術(shù)研究[D].沈陽(yáng):沈陽(yáng)航空工業(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

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