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

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

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

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

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

1 常用推薦算法介紹

1.1 基于鄰域的算法

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

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

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

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

(1)

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

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

(2)

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

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

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

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

(3)

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

(4)

1.2 矩陣分解法

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

(5)

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

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

(6)

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

2 NSGA-П算法簡介

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

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

　　NGSA-II算法流程：

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

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

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

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

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

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

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

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

(7)

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

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

3.2 非支配和擁擠距離排序

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

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

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

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

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

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

(8)

(9)

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

(10)

(11)

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

4 實驗設計與實驗結(jié)果

4.1 評測指標

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

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

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

(12)

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

(13)

4.2 實驗設計

　　(1) 實驗數(shù)據(jù)

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

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

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

　　1、基礎算法的實現(xiàn);

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

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

　　1、基礎算法的實現(xiàn)

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

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

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

　　2 多目標遺傳算法的實現(xiàn)

　　多目標遺傳算法的實現(xiàn)包括以下幾個部分：

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

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

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

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

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

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

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

4.3 實驗結(jié)果

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

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

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

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

5 結(jié)束語

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

參考文獻：

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

　　[2]項亮，推薦系統(tǒng)實踐[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]王曉耘，錢璐，黃時友.基于粗糙用戶聚類的協(xié)同過濾推薦模型[J].現(xiàn)代圖書情報技術(shù)，2015:45-51

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

　　[7]吳蘭蘭.基于遺傳學方法的個性化推薦技術(shù)研究[D].沈陽:沈陽航空工業(yè)學院，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頁，歡迎您寫論文時引用，并注明出處。