基于改進NSGA-II的推薦算法

張海潮，楊連賀

(天津工業大學 計算機科學與技術學院，天津 300387)

0 引 言

推薦算法是根據用戶偏好需求模型來進行項目推薦,與用戶偏好需求越匹配的項目則越傾向于推薦給用戶[1]。傳統的推薦算法大多只將準確率作為評價指標[2]。這類基于準確率的推薦算法雖然能夠保證一定的準確率，但會導致一些無用的推薦。因此，許多研究人員致力于推薦長尾項目或流行度低的項目[3]，而這類推薦會導致準確率降低。在推薦算法中，提高準確率和增加多樣性是兩個相互矛盾的性能指標，為了使這兩個指標都盡可能地達到最優化，需要在其中進行協調和折衷處理。因此許多研究人員將多目標優化引入了推薦系統[4]。文獻[5]提出了一個多目標推薦框架，該框架在推薦長尾項目的同時盡可能地降低精度的損失。文獻[6]提出了一種多目標模擬退火方法，有效地緩解了長尾問題。文獻[7]提出了一種推薦系統的多目標進化算法，該算法相較于傳統算法具有良好的推薦多樣性。文獻[8]提出了一種基于SVD和多目標免疫優化的推薦算法，改善了推薦系統的準確性-多樣性的困境。

遺傳算法是一種全局隨機搜索和優化方法[9]。其中NSGA-II算法由于其自身的簡單有效性，已成功地應用于大量多目標優化問題[10]。

本文首先通過概率矩陣模型對目標用戶產生推薦候選集，將推薦結果的準確率和多樣性作為目標函數，把推薦問題轉化為多目標優化問題，并根據改進的NSGA-II算法對目標用戶產生一組推薦，實驗結果表明了所提算法的有效性。

1 相關技術

1.1 概率矩陣分解模型

概率矩陣分解(probabilistic matrix factorization)是從概率的角度來預測用戶對物品的評分，是隱語義模型的概率化形式[11]。該模型假設用戶U和項目V的特征矩陣均服從高斯分布，通過評分矩陣中的已知值得到U和V的特征矩陣，并用特征矩陣去預測評分矩陣中的未知值。

本文利用概率矩陣分解模型預測評分矩陣中的未知值，并根據預測評分對目標用戶產生推薦項目的候選集。

1.2 多目標優化

多目標優化問題是指使多個目標在給定區域盡可能同時達到最優，然而這些目標通常是相互沖突和影響的。多目標優化問題描述如下

(1)

式中：x=(x1,x2,…,xn)T是決策向量，Ω是x的向量空間，m是目標個數。Pareto支配、Pareto最優解、Pareto最優解集、Pareto前沿定義請參見文獻[12]。

1.3 NSGA-II算法

算法首先隨機產生大小為N的父代種群P0，種群根據非支配性進行排序，每個個體都被分配一個適應度，使用錦標賽選擇、交叉和變異操作產生了大小為N的子代種群Q0。由于引入了精英策略，自初代后的過程有所不同。圖1 描述的是第t代的過程，首先將第t代的父代種群Pt和通過交叉變異產生的子代種群Qt合并為Rt，Rt通過快速非支配排序得到一系列非支配Pareto解集，分別為F1,F2,F3…,它們的等級依次降低，首先選擇F1進入種群Pt+1，如果F1小于N，則繼續選擇F2進入Pt+1，直到F1+F2+…+Fi剛好大于或等于N，這里稱Fi為臨界層，再對臨界層計算擁擠距離，優先選擇擁擠度小的個體先進入Pt+1，直至達到最大迭代次數。

圖1 NSGA-II算法過程

2 存在的問題

2.1 擁擠距離計算

NSGA-II算法的排擠機制是建立在個體的擁擠距離之上的。擁擠距離用于估計總體中某一特定個體周圍的解的密度，第i個個體的擁擠距離是它所在層級的兩個相鄰個體在每個目標上的距離之和。在同一層級上的個體，擁擠距離大的個體被優先選擇。這一策略保留了擁擠度較小的個體。但是該策略存在一定的局限性：由于擁擠距離只計算了一次，如果擁擠距離較小的多個個體集中在了一個區域，那么這些個體將同時被刪除。

2.2 交叉變異算子

遺傳算法在進化代數接近終止代數時，種群接近于一個齊次種群。這是由于在選擇交叉個體時采取精英策略，適應度好的個體更容易進入交配池，所以在交配池中會出現重復的個體，因此，迭代次數越多，個體的重復率越大。一般會通過變異操作改善這種情況，但是傳統的變異算子會設定一個固定值，且變異概率較小，即使進行了變異操作，也會出現種群過早收斂的現象。

3 改進的NSGA-II算法

3.1 改進的擁擠距離計算

為了改善上述關于擁擠距離計算中存在的問題，本文提出了一種動態調整擁擠距離的方法。計算過程如下：

(1)計算相鄰兩個個體之間的歐式距離。假設有n個個體，第k(k∈(2,n-1)) 個個體和第k+1個個體之間的擁擠距離為

(2)

式中：m為目標的數目，fi(k) 為第k個個體在第i個目標上的值，fimin為第i個目標的最小值，fimax為第i個目標的最大值。

(2)找到最小擁擠距離I[k,k+1]， 比較I[k-1,k] 與I[k+1,k+2] 的擁擠距離，若I[k-1,k] 小，則淘汰個體k，否則，淘汰個體k+1。

(3)更新擁擠距離。

(4)判斷是否滿足需要個體的數目。若不滿足，則返回(2)，否則，終止。

例如，在圖2中，I[D,E] 的擁擠距離最小，則比較I[C,D] 與I[E,F] 的擁擠距離，因I[E,F] 的擁擠距離更小，故淘汰個體E，刪除I[D,E] 與I[E,F] 的擁擠距離，并重新計算I[D,F] 的擁擠距離。

圖2 改進的擁擠距離計算

3.2 改進的交叉變異算法

針對遺傳算法中種群過早收斂的問題，本文設計了一種基于近親系數的交叉變異算法。該算法同時考慮了進化代數對交叉變異的影響。為方便描述，本文有如下定義：

定義1 近親系數

(3)

式中：F(Xi,Xj) 表示兩個個體的近親系數，l是個體基因的長度，xik表示個體Xi的第k個基因，μk表示第k個等位基因的權重，μk在本文中取1/l。

定義2 近親個體：若兩個個體的近親系數大于設定閾值，則認為這兩個個體為近親個體。

交叉變異算法描述如下：

(1)隨機選擇兩個父代個體Xi和Xj(個體長度為l)，找到兩個個體相同的等位基因集Ns和不同的等位基因集Nd。

(2)計算近親系數，判斷兩個父代個體是否屬于近親個體，若是，則返回步驟(1)，否則執行步驟(3)。

(3)將Ns中的基因傳入子代個體，并在基因集Nd中隨機選擇l-|Ns| 個基因傳入子代個體。

(4)根據相同等位基因的個數計算需要變異基因的個數，計算公式如下

(4)

式中：Nv表示需要變異的個數。

(5)根據相同等位基因的個數以及當前迭代次數ei計算變異概率，計算公式如下：

(5)

式中：α為一個0～1的系數，eva為總的迭代次數。

(6)根據變異個數和變異概率進行變異。

例如，A和B是兩個父代個體，首先找到它們相同的等位基因集并傳入子代C中(相同基因為5,18,9,2)，再從不同的等位基因集中隨機選擇6個基因傳入子代中(例如：7,35,24,6,16,8)，根據式(4)和式(5)計算變異基因個數和變異概率，分別為2和p′v， 如圖3所示，在位置2和位置6進行了變異。

圖3 改進的交叉變異算法

4 多目標推薦算法

4.1 目標函數

推薦系統主要關注的是推薦的準確率，這里用f1表示推薦的準確率，公式如下

(6)

式中：R表示對用戶i的推薦列表，Rij表示用戶i對項目j的預測評分。

除了推薦的準確率，我們也希望能夠增加推薦的多樣性，這里用f2表示推薦的多樣性。公式如下

(7)

式中：s(j,k) 表示項目j和項目k的相似度。

為提高推薦的準確率，應該使f1盡可能大。為了提高推薦的多樣性，應該使f2盡可能小。但是準確度和多樣性是兩個互相沖突的目標，因此推薦問題轉換成了多目標優化問題

min{-f1,f2}

(8)

4.2 算法流程

Input：Rm×n，User_ID，eva，L，N//輸入評分矩陣，目標用戶ID，最大迭代次數，推薦列表長度，種群規模。

Output：set[]為目標用戶的推薦解集。

步驟1 使用PMF算法產生候選集S；

步驟2 從S中產生N組初始種群P0，并計算初始種群中個體的f1和f2的值；

步驟3 將Pt(初代為P0)進行快速非支配排序，使用錦標賽選擇機制產生規模為N的種群Peli；

步驟4 根據3.2節介紹算法對Peli進行交叉變異操作，得到子代種群Qt(初代為Q0)，大小為N；

步驟5 將Pt和Qt合并為Rt，大小為2N，對Rt進行快速非支配排序，得到的層級為F1,F2,F3…。先將F1中的個體加入到下一次迭代種群Pt+1，若 |F1|

步驟6 根據3.1節中介紹的算法對Fm進行擁擠距離計算，每次刪除一個擁擠度最大的個體并更新擁擠距離，直至Fm中剩余N-(|F1|+|F2|+…+|Fm-1|) 個個體為止；

步驟7 判斷是否達到迭代次數，若沒有，則返回步驟3，否則，終止。

4.3 算法復雜度分析

假設目標函數數目為M，種群大小為N，則改進的NSGA-II算法的時間復雜度計算如下：

非支配排序的時間復雜度為O(M×(2N)2)； 擁擠距離計算的時間復雜度為O(M(2N)log(2N))； 同一層級選擇的時間復雜度為O(2Nlog(2N))； 交叉變異的時間復雜度為O(N)， 所以算法總體的時間復雜度為O(M×(2N)2)。

5 實驗結果及分析

5.1 數據集

為了驗證提出的算法的有效性，本文分別在Movielens數據集和Jester數據集上進行實驗。Movielens數據集包含了943名用戶對1682部電影的10萬條評分數據，所有的評分值落在[0,5]區間內，每位用戶至少對20部電影評分。Jester數據集包含63 978名用戶對150條笑話的超過170萬條評論，所有評分值落在[-10,10]區間內，本文將評分值映射到[0,5]區間上。在本實驗中，將數據集隨機劃分80%的數據作為訓練集，20%的數據作為測試集。

5.2 參數設置

本文參數設置見表1。

表1 實驗參數

5.3 評價指標

本文采用推薦系統中常用的度量指標，準確率、多樣性和新穎度作為推薦結果的評價指標

(9)

(10)

pop=log(1+N(i))

(11)

其中，R表示所有用戶的集合，R(u) 表示在訓練集上通過訓練推薦給用戶的列表，T(u) 表示在測試集上用戶的評價過的項目列表。s(i,j) 表示項目i和項目j的相似度。N(i) 表示評論項目i的用戶數目。

5.4 實驗結果

算法對目標用戶產生一組推薦列表，圖4給出了用戶1的帕累托前沿。

圖4 用戶1的帕累托前沿

圖4中每一個點都代表對目標用戶的一組推薦列表，由于算法是在準確率和多樣性之間進行權衡，所以f1越大，f2就越小。同理，f1越小，f2就越大。

為了驗證所提算法的有效性，下面將本文算法與PMF算法和未改進的基于NSGA-II的推薦算法進行比較。本文算法和基于NSGA-II的推薦算法隨機從測試集中取50個用戶，并求出對每個用戶產生的20組解在評測指標上的平均值，實驗結果如圖5所示。

圖5 3種算法評測指標比較

圖5(a)展示的是3種算法推薦結果的準確率。可以看出，在兩個數據集上PMF算法的準確率最高，基于 NSGA-II 的推薦算法和本文算法的準確率較低，這是由于PMF算法會推薦預測評分最高的10個項目，而另外兩種算法要在準確率和多樣性之間進行權衡，必然會導致準確率的降低。但是本文算法的準確率在兩個數據集上的準確率要高于基于NSGA-II的推薦算法。

圖5(b)展示的是3種算法推薦結果的多樣性。由于本文采用推薦項目之間的相似度衡量推薦結果的多樣性，所以推薦結果的值越小，多樣性就越高。由圖中可以看出，在多樣性方面，無論是在Movielens數據集還是在Jester數據集上，本文算法都優于另外兩種算法。基于NSGA-II的推薦算法在兩個數據集上相較于PMF算法在多樣性方面也有所提高。

圖5(c)展示的是3種算法推薦結果的新穎度。由實驗結果可以看出，在Movielens數據集上PMF算法新穎度略好于其它兩種算法，但是在Jester數據集上PMF算法明顯比另外兩種算法差。本文算法比基于NSGA-II的推薦算法在新穎度方面略好。

實驗結果表明，本文算法雖然在準確率上相較于PMF算法略低，但是在準確率和多樣性上都比基于NSGA-II的推薦算法表現好。因此對于大多數用戶來說，本文算法能夠在不降低準確率甚至有所提高的同時，有效地提高推薦的多樣性，從而驗證了改進算法的有效性。

6 結束語

針對傳統的推薦算法中單一追求推薦結果的準確率而忽略多樣性的情況，本文提出了一種基于改進NSGA-II的算法的推薦算法，通過一次推薦可以對目標用戶產生一組推薦列表。實驗結果表明，在不降低準確率的同時，本文算法能有效提高推薦結果的多樣性。

本文實現的是推薦結果準確率和多樣性兩個性能之間的權衡，在實際的推薦過程中往往要考慮到3個甚至更多的性能需求。在未來，我們的研究將擴展到解決推薦問題的更多目標上。