樊鴻

摘要：該文在分析推薦系統(tǒng)和進化計算理論的基礎上，提出一種多目標優(yōu)化思路，給出一種基于進化多目標優(yōu)化的推薦系統(tǒng)算法。該算法同時考慮推薦的精確度和推薦的新穎度，既要保證精確率又要盡可能地推薦新的物品給用戶，算法力求在兩者之間得到一種平衡。該文給出算法的設計思想和算法流程，并對算法進行了模擬數(shù)據(jù)的測試。

關鍵詞：推薦系統(tǒng)；進化優(yōu)化

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）10-2342-05

Abstract： Based on the theoretical analysis and recommendation system evolution， this paper has proposed a multi-objective optimization idea and an evolutionary multi-objective optimization based recommendation algorithm is proposed. This algorithm simultaneously considers the recommendation precision and novelty， it not only preserves precision but also recommend new items to user， it makes effort to obtain the tradeoff between these two objectives. This paper presents the design of algorithms and algorithmic thinking processes， and tests the algorithm with simulation data.

Key words： recommendation systems； evolutionary optimization

推薦系統(tǒng)是大數(shù)據(jù)處理和社會計算的一種重要技術和手段，在信息高速發(fā)展和個性化的需求之下，推薦系統(tǒng)地位日趨顯赫。經(jīng)過多年的發(fā)展，業(yè)界已涌現(xiàn)多種推薦算法，還有更加新穎的推薦算法被不斷提出，而推薦算法效率優(yōu)劣與否直接關系到推薦系統(tǒng)的性能及應用，從目前的參考文獻分析中可以得出，這些算法沒有考慮將推薦過程建模成數(shù)學優(yōu)化問題，更沒有考慮用優(yōu)化算法去解決這種問題。該文試圖從進化多目標優(yōu)化的角度出發(fā)，將多目標優(yōu)化融入到推薦過程中，提出了一種進化多目標優(yōu)化的推薦算法。

1 設計背景

1）推薦系統(tǒng)定義及分類

推薦系統(tǒng)是在信息革命的背景下應運而生的，推薦系統(tǒng)可以理解為自動聯(lián)系用戶和物品的一種工具，是一種緩解信息過載問題的技術或者平臺。目前，業(yè)界對推薦系統(tǒng)的定義很多，但是在1997年由Resnick和Varian歸納總結得出：“推薦系統(tǒng)是利用電子商務網(wǎng)站向客戶提供商品信息和購買方面的建議，輔助用戶決策購買合適的產(chǎn)品，充當模擬銷售人員的身份幫助客戶完成購買過程”被廣泛認可和接受。

按照推薦系統(tǒng)采集的用戶的行為數(shù)據(jù)的類型，一般按以下五類劃分推薦系統(tǒng)：

① CBF [1]—基于內容過濾的推薦系統(tǒng)。

② SRS—社會推薦系統(tǒng)。

③ KBRS—基于知識的推薦系統(tǒng)

④ HRS—混合推薦系統(tǒng)。

⑤ CFRS[2]—基于協(xié)同過濾的推薦系統(tǒng)。

2）主要推薦方法對比

如表1所示。

3）推薦系統(tǒng)存在的問題

推薦系統(tǒng)主要存在冷啟動和數(shù)據(jù)稀疏兩方面的問題。

① 冷啟動問題

在推薦系統(tǒng)中，冷啟動問題主要分為3類[3]：用戶冷啟動、項目冷啟動和系統(tǒng)冷啟動。用戶冷啟動，即用戶剛剛使用系統(tǒng)，自身的信息才被記錄。另外一個冷啟動就是項目冷啟動，即某一項目第一次出現(xiàn)在系統(tǒng)中。另外系統(tǒng)冷啟動主要解決如何在一個新開發(fā)的系統(tǒng)或網(wǎng)站上設計個性化推薦系統(tǒng)。

② 系統(tǒng)稀疏性問題

對于一個真正的推薦系統(tǒng)而言，推薦系統(tǒng)中的物品個數(shù)要遠大于用戶的數(shù)目，反過來，用戶更不可能去購買所有的物品，其直接導致的后果是生成的用戶與物品評分矩陣是一個超級稀疏的矩陣，因此會導致在計算用戶與用戶之間的相似度時結果并不符合真實情況。

4）基于帕累托占優(yōu)的進化多目標算法

Pareto最優(yōu)的思想被引入到進化多目標優(yōu)化中，是一種很好的求解多目標優(yōu)化的思想。圖1以兩目標優(yōu)化問題為例展示了Pareto占優(yōu)的思想。圖中所有的點表示Pareto最優(yōu)解，所有的解組成的一個面叫做Pareto面，稱PF面。圖中，Pareto最優(yōu)解A和B由于彼此不能判定誰比誰好，所以它們被稱為Pareto最優(yōu)解，A和B之間互相都不能支配誰。

2 算法設計

1）個體表示和適應度函數(shù)

表2給出了一個m個用戶對n個物品的評分數(shù)據(jù)統(tǒng)計情況，第i行第j列的元素代表用戶i對項目j的喜好情況評分。

表所示的矩陣數(shù)據(jù)是很多推薦系統(tǒng)算法的輸入，即這些算法試圖通過已經(jīng)得到的評分矩陣通過某種方式或者策略估計用戶對其他目前用戶還沒有評分或者購買或者使用的物品的評分，根據(jù)這些估計值來排序，從而按照排序結果給優(yōu)化進行推薦。該文的設計思路卻不一樣，該文的算法試圖讓算法一次運行能夠給出很多不同的推薦方案供決策者去自主選擇。該文算法個體的編碼方法如下：

表所示的個體編碼采用的是二進制編碼，這樣做的好處就是易于理解，物品被推薦就用1表示，不推薦就用0表示，另外這樣的編碼方法很好解碼，操作方便。對于一個進化多目標優(yōu)化算法來講，算法一次運行能夠得到多個甚至很多個Pareto最優(yōu)解，每個解都是一種推薦方案，決策者可以根據(jù)不同的用戶的喜好來選擇合適的方案來對用戶進行推薦。

進化多目標優(yōu)化通常要求待優(yōu)化目標之間具有沖突或者部分沖突，對于推薦系統(tǒng)而言，目標函數(shù)的確立就更加至關重要了。目前關于用多目標求解推薦的算法基本就沒有，因為推薦系統(tǒng)目前的評價指標比較少，而且現(xiàn)存的指標很難建模成一個多目標優(yōu)化問題。該文算法力求尋找一種多目標解決方案。

按照推薦系統(tǒng)的推薦原則，該文設計的第一個目標函數(shù)就是精確度，精確度越高，推薦效果越好。該文設計了另外一個指標叫新穎度，此新穎度是針對用戶的，不是針對物品而言的。因此，該文算法定義的多目標函數(shù)如下：

[maxf1=（R+L）/Lf2=（R-L）/R] （1）

上式中，R表示一個推薦物品列表，L表示目標用戶喜歡的物品列表。從上式可以看出，若要f1最大化，理想情況就是推薦列表包含用戶目前所有喜歡的物品，而f2最大化的理想情況是推薦列表不包含用戶喜歡的物品，這一點正好符合多目標優(yōu)化多目標的要求。該文算法力求尋找f1和f2之間的一組折中解。

2）遺傳操作

本文算法中使用的交叉操作的步驟就是選擇一個位置，然后從該位置開始到一個個體的最后一位，交換兩個個體這個位置區(qū)域之間的編碼內容。

本文算法中使用的變異操作的步驟就是選擇一個位置，若隨機數(shù)大于變異概率，則將個體該位置的編碼由原始的0變?yōu)?或者由原始的1變?yōu)?，否則不做任何操作，該變異操作非常簡單。

3）算法流程

本文算法提出的是一種進化多目標優(yōu)化推薦系統(tǒng)解決方案。按照本文算法具體的操作步驟，下面給出了算法的整體流程圖如圖3所示。

按照圖3的算法流程圖，該文算法的具體操作步驟如下：

Step 1）數(shù)據(jù)讀?。簭奈募x取用戶—物品評分矩陣M，其中M是一個[n×m]的矩陣，n表示用戶個數(shù)，m表示物品個數(shù)；

Step 2）初始化種群：將種群的每個個體隨機初始化為二進制隨機序列；

Step 3）保持非支配解：開辟一個外部種群，按照非支配關系確定非支配解，將非支配解存儲在外部種群中；

Step 4）遺傳操作：對當前種群進行遺傳操作，即每隔兩個個體，對該兩個個體進行交叉操作，整個種群交叉操作完畢則對種群每個個體進行變異操作；

Step 5）適應度計算：對新產(chǎn)生的種群的個體計算適應度；

Step 6）更新外部種群：計算經(jīng)過遺傳操作之后的新種群的非支配解，并用這些非支配解更新外部種群的歷史非支配解；

Step 7）終止條件：為終止條件不滿足則跳至步驟4，否則輸出算法得出的所有推薦方案，并且選擇精確度最大的解作為最終的解。

3 實驗測試

1）實驗平臺

1） 參數(shù)設置

種群大小popsize：100

外部種群archive：500

迭代次數(shù)loopgene：100

交叉概率pc：0.8

變異概率pm：0.2

2） 軟件平臺

編程工具：Matlab7.0

操作系統(tǒng)：Windows 7

3） 硬件平臺

中央處理器：Intel（R） Core（TM） i3 CPU 3.2GHz

內存：4GB

硬盤：500G

2）實驗數(shù)據(jù)

實驗模擬數(shù)據(jù)是電影推薦數(shù)據(jù)。該數(shù)據(jù)是8用戶觀看8部電影后，給出的記錄打分集合，用戶及電影名稱信息集如表3所示。

由于原始數(shù)據(jù)是記錄的形式給出的，所以要得到矩陣數(shù)據(jù)需要對原始數(shù)據(jù)進行預處理。經(jīng)過數(shù)據(jù)預處理之后得到的數(shù)據(jù)矩陣如表4所示。

3）實驗結果

程序是在matlab7.0軟件中實現(xiàn)的，最終的結果都是在matlab界面中顯示的。因為程序是基于數(shù)學建模的，結果的輸出區(qū)域是兩個目標函數(shù)的坐標系中，該文設定的橫坐標是精確度，也即目標參數(shù)f1；縱坐標是新穎度，也即是目標函數(shù)f2。輸出結果是進化迭代的最后一組非支配解，也就是一系列的坐標點（f1，f2）；其數(shù)學含義是這些點互不支配，屬于目標函數(shù)組的一組折中解。每個坐標點代表一種推薦方案，根據(jù)算法的設計，算法保留著這些非支配解對應的種群，種群在算法中就是一個行向量為種群大小，列向量為物品個數(shù)的矩陣。目標函數(shù)值是通過種群矩陣中的行向量與用戶-物品評分列表中的行向量集合運算得到的。其中種群中行向量是一個0、1的序列，對應著用戶不喜歡或喜歡該物品，所以（f1，f2）解集對應的就是針對單個用戶相應的物品推薦方案，驗證了本文算法一次運行得到多個推薦解的結果。

圖4的PF面的結果可以看出，該文提出的算法可以得到比較理想的推薦情況，因為從進化多目標優(yōu)化的角度來看，該文算法得到的PF比較光滑，而且數(shù)據(jù)之間的分布也比較均勻。

從圖4可以看出，該文算法一次運行可以得到一組推薦方案，而傳統(tǒng)方法一次運行只能得到一種推薦方案，這樣就不利于決策者進行決策，而本文算法可以在保證高的正確率情況下給出多種個性化推薦方案。

4 結論

本文系統(tǒng)講述了推薦系統(tǒng)的相關理論及知識，將推薦系統(tǒng)的推薦過程建模成了一個多目標優(yōu)化問題，并提出了一種進化多目標求解算法。該文提出的算法一次運行就可以得到很多不同的推薦方案供決策者選擇，因此本文提出的算法比傳統(tǒng)的協(xié)同過濾推薦算法更具有意義，更適合實際應用情況。

該算法的本質是用進化多目標優(yōu)化算法去優(yōu)化本文建模的兩個推薦系統(tǒng)推薦指標。雖然實驗部分證明本文提出的算法是有效的，但是仍然還具有許多需要改進的地方，比如，目標函數(shù)的設計。該文設計的目標函數(shù)很簡單，對于實際中的應用應該考慮一些個性化元素，將這些個性化元素融入到目標函數(shù)中，這樣得到的推薦方案將會更具有個性化。另外，對于真實的推薦系統(tǒng)而言，由于現(xiàn)實中的推薦系統(tǒng)的數(shù)據(jù)都是很大的，而進化算法都是一類隨機搜索算法，如何更好的設計算法，讓算法能夠處理大規(guī)模數(shù)據(jù)也是一項值得研究的內容，比如可以考慮加入局部搜索算子加速算法收斂，比如對算法進行并行化，提高算法的執(zhí)行時間等。

參考文獻：

[1] Koren Y， Bell R， Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer， 2009， 42（8）： 30-37.

[2] Boussa?d I， Lepagnot J， Siarry P. A survey on optimization metaheuristics[J]. Information Sciences， 2013.

[3] Chen Y. L.， Cheng L. C. A novel collaborative filtering approach for recommending ranked items[J]. Expert System with Applications， 2008， 34 （4）： 2396-2405.