王玉林 王永鑒 柴爭(zhēng)義

（天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387）

基于免疫算法的個(gè)性化推薦系統(tǒng)

王玉林 王永鑒 柴爭(zhēng)義

（天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387）

針對(duì)個(gè)性化推薦系統(tǒng)中用戶的多個(gè)不同需求，提出一種基于免疫算法的求解方法。該算法將要求解的個(gè)性化推薦列表建模成一個(gè)最大化推薦準(zhǔn)確性和多樣性的多目標(biāo)優(yōu)化問(wèn)題，采用基于用戶的協(xié)同過(guò)濾技術(shù)對(duì)用戶進(jìn)行分類，設(shè)計(jì)了適合推薦問(wèn)題求解的抗體編碼方式、克隆、變異算子。仿真實(shí)驗(yàn)結(jié)果表明，所提算法能夠有效求得個(gè)性化推薦的最佳解，達(dá)到可以同時(shí)為多個(gè)用戶提供多個(gè)不同推薦的需求。

免疫算法；多目標(biāo)優(yōu)化；個(gè)性化推薦；協(xié)同過(guò)濾

1 引言

隨著信息技術(shù)的迅猛發(fā)展，人類已經(jīng)進(jìn)入一個(gè)數(shù)據(jù)爆炸的時(shí)代，生活工作中無(wú)處不在的是令人困擾的無(wú)效信息[1]。于是，如何快速高效地找出對(duì)我們有用的信息已經(jīng)成為一個(gè)迫在眉睫的問(wèn)題。推薦系統(tǒng)，使用自動(dòng)統(tǒng)計(jì)和數(shù)據(jù)挖掘技術(shù)，能夠很好地為用戶提供若干有用的推薦，被認(rèn)為是緩解信息過(guò)載最有前程和潛力的工具[2]。它涉及的領(lǐng)域較為廣泛，包括電影，書籍，歌曲，笑話，旅游等等。此外，隨著生活中電子商務(wù)在不斷推進(jìn)，推薦系統(tǒng)也正越來(lái)越多地參與其中，比如著名的電子商務(wù)公司亞馬遜[3]。

通常，傳統(tǒng)的推薦系統(tǒng)的目的是使向某類用戶所推薦的項(xiàng)目精確度最大化[4]。然而，最近研究發(fā)現(xiàn)，只考慮推薦的準(zhǔn)確性已經(jīng)完成不能滿足用戶的需求；必須得針對(duì)性地為每個(gè)用戶“量身定做”項(xiàng)目，并考慮用戶多種的需求，最終才能提供滿意的結(jié)果，這正是個(gè)性化推薦系統(tǒng)所具備的能力。然而，提高準(zhǔn)確度無(wú)疑會(huì)使多樣性降低；同樣，種類越多也會(huì)使準(zhǔn)確性降低。準(zhǔn)確性和多樣性已成為相互制約的要素。于是，如何設(shè)計(jì)出準(zhǔn)確度高、多樣性強(qiáng)的個(gè)性化推薦技術(shù)具有重要的意義。

目前，國(guó)內(nèi)外的一些推薦技術(shù)已經(jīng)設(shè)計(jì)出來(lái)。例如用數(shù)學(xué)方法把準(zhǔn)確度和多樣性建模成二次性方程數(shù)學(xué)問(wèn)題求解。但存在著數(shù)學(xué)約束條件過(guò)高以及參數(shù)難以自動(dòng)調(diào)節(jié)的弊端。個(gè)性化的推薦問(wèn)題已被證明是NP問(wèn)題，更適合智能化方法。免疫算法作為一種高效的智能算法，在許多應(yīng)用領(lǐng)域都有卓越的表現(xiàn)。基于此，本文采用免疫算法對(duì)個(gè)性化推薦問(wèn)題進(jìn)行求解，向用戶提供一組既準(zhǔn)確又豐富的、令人滿意的推薦項(xiàng)目[5]。

2 個(gè)性化推薦系統(tǒng)

個(gè)性化推薦系統(tǒng)是通過(guò)采集記錄并了解掌握用戶的興趣偏好，最終向用戶提供一些可能會(huì)感興趣的推薦項(xiàng)目。推薦問(wèn)題可用形式化加以闡明。C表示用戶集合，S表示項(xiàng)目集合[6]。函數(shù)u作為一個(gè)評(píng)價(jià)函數(shù)，它是用來(lái)表示用戶對(duì)項(xiàng)目感興趣程度。

R是所有用戶對(duì)項(xiàng)目的評(píng)價(jià)集合，rij表示用戶i對(duì)項(xiàng)目j的評(píng)價(jià)值。因此，就可以形成用戶—項(xiàng)目矩陣如表1所示：

表1 用戶—項(xiàng)目矩陣

對(duì)于用戶空間中的每一個(gè)用戶，推薦所要達(dá)到的目的就是從項(xiàng)目空間中尋找能夠使用戶的滿意度和多樣性最大化的商品項(xiàng)目[7]。

多目標(biāo)優(yōu)化問(wèn)題是對(duì)多個(gè)目標(biāo)函數(shù)進(jìn)行同時(shí)優(yōu)化求得最佳解。它是一個(gè)比較復(fù)雜的問(wèn)題，它的約束要求是彼此各自獨(dú)立的，無(wú)法直接比較任意兩個(gè)解的優(yōu)劣，所以只能從解集中找到最為接近最好的折中解，即最佳解[8-9]。

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

3.1 免疫算法

免疫算法是一種經(jīng)典的智能優(yōu)化算法，它是受高級(jí)生物的免疫系統(tǒng)具有自發(fā)、高效、特異性清除異己的原理啟發(fā)而產(chǎn)生的。它把要解決的問(wèn)題看作免疫系統(tǒng)的抗原，把要得到的解看作免疫系統(tǒng)的抗體。通過(guò)免疫反應(yīng)，解決所要處理的問(wèn)題。在資源分配、地址尋址、安全監(jiān)測(cè)等領(lǐng)域中有優(yōu)良的表現(xiàn)，得到了廣泛應(yīng)用[10-11]。

3.2 用戶聚類

為了降低計(jì)算的復(fù)雜度，用聚類技術(shù)將用戶拆分成幾個(gè)集群。過(guò)程采用基于用戶協(xié)同過(guò)濾技術(shù)，通過(guò)度量用戶i和用戶j之間相似性產(chǎn)生用戶分類。首先得到用戶和用戶評(píng)分過(guò)的所有項(xiàng)目，然后通過(guò)余弦相似性函數(shù)計(jì)算出用戶之間的相似性。其公式為：

分母是兩個(gè)用戶向量模的乘積，分子是兩個(gè)用戶向量的內(nèi)積。Ui，Uj分別表示的用戶i，j對(duì)項(xiàng)目評(píng)分集，ru,i，ru,j分別表示的是用戶對(duì)項(xiàng)目的評(píng)分，Uij表示的是用戶i，j均評(píng)價(jià)的項(xiàng)目集。

3.3 抗體編碼

免疫算法中，抗體對(duì)應(yīng)要求解問(wèn)題的解，抗體編碼是免疫問(wèn)題求解的關(guān)鍵技術(shù)。本文考慮到用戶與項(xiàng)目之間的關(guān)系，采用實(shí)數(shù)編碼方式，即推薦列表中的每一個(gè)數(shù)字代表相應(yīng)的項(xiàng)目編號(hào)。例如某個(gè)抗體的編碼表示為，其中a表示的是某個(gè)用戶，ai表示的就是此用戶推薦列表中的項(xiàng)目編號(hào)。

3.4 兩個(gè)目標(biāo)函數(shù)

第一個(gè)目標(biāo)函數(shù)是準(zhǔn)確性。準(zhǔn)確性在很大程度上能夠反映出用戶對(duì)項(xiàng)目的喜愛(ài)程度，也說(shuō)明推薦系統(tǒng)的質(zhì)量好壞，準(zhǔn)確性越好說(shuō)明推薦的能力越優(yōu)秀。用預(yù)測(cè)評(píng)級(jí)機(jī)制來(lái)表示準(zhǔn)確度的測(cè)量標(biāo)準(zhǔn)。對(duì)于一個(gè)用戶i以及一個(gè)項(xiàng)目j來(lái)說(shuō)，用戶i對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)級(jí)用pij來(lái)表示，則在一個(gè)用戶聚類U中，預(yù)測(cè)評(píng)級(jí)的定義是：

第二個(gè)目標(biāo)函數(shù)是多樣性。多樣性能夠反映推薦列表的豐富程度，多樣性越高表示推薦的種類越全面越豐富。給出具體的定義如下：

其中dif表示的是在同一個(gè)聚類U中所推薦的不同項(xiàng)目數(shù)，Total表示的是所有項(xiàng)目的總數(shù)。很明顯，準(zhǔn)確性不變時(shí)，覆蓋率的值越大表明一個(gè)更好的推薦。

3.5 免疫算子

免疫算子包括交叉和變異。操作中相同項(xiàng)目不允許兩次出現(xiàn)在推薦給一個(gè)用戶的列表中[12]。交叉的過(guò)程可以描述如下：首先從兩個(gè)父代個(gè)體中確定彼此相同的項(xiàng)目并直接傳給子代。不同的項(xiàng)目執(zhí)行交叉操作，隨機(jī)數(shù)[0，1]決定產(chǎn)生位置。如果隨機(jī)數(shù)大于0.5，第一個(gè)不同項(xiàng)目交叉；否則不動(dòng)。以此類推完成所有操作。個(gè)體交叉過(guò)程如圖1所示。

圖1 個(gè)體交叉的過(guò)程

變異則是應(yīng)用于單個(gè)個(gè)體。如果一個(gè)等位基因在父代中發(fā)生了突變，則隨機(jī)從項(xiàng)目集中選取一個(gè)可用的項(xiàng)目代替原先的位置，并且所選取的這個(gè)項(xiàng)目在父代中不存在。通過(guò)這種方式，變異算子可以生成可行的解決方案。

3.6 算法描述

多目標(biāo)優(yōu)化問(wèn)題因?yàn)橛卸鄠€(gè)目標(biāo)，所以通過(guò)優(yōu)化得到的解不是唯一的，它需要種群多次迭代后產(chǎn)生得到折中最優(yōu)解。本文算法基本流程如圖2所示，具體步驟如下：

步驟1初始抗體種群由隨機(jī)方式產(chǎn)生。給定抗體種群大小N、最大迭代次數(shù)gmax。

步驟2對(duì)候選抗體種群A(i)進(jìn)行克隆操作，得到種群B(i)。

步驟3對(duì)抗體種群B(i)進(jìn)行變異操作，得到種群C(i)。

步驟4對(duì)種群進(jìn)行克隆選擇：選擇n個(gè)親和度高的抗體組成下一代種群A’(i)。

步驟5判斷終止條件。當(dāng)滿足終止條件時(shí)，輸出親和力最高個(gè)體；否則進(jìn)入步驟2。

圖2 算法流程圖

4 實(shí)驗(yàn)結(jié)果分析

本文使用一個(gè)經(jīng)典基準(zhǔn)數(shù)據(jù)集Movielens來(lái)評(píng)估算法的性能。這個(gè)電影類的數(shù)據(jù)集包含了943個(gè)用戶和1682部電影。隨機(jī)選擇80%的數(shù)據(jù)作為實(shí)驗(yàn)訓(xùn)練集，20%作為實(shí)驗(yàn)探針集。訓(xùn)練集的目的是用來(lái)生成推薦；而探針集則是用來(lái)評(píng)估推薦系統(tǒng)的性能。在實(shí)驗(yàn)中設(shè)置推薦列表長(zhǎng)度L為10，種群大小N為100，交叉概率為0.8，變異概率為0.1，最大迭代數(shù)gmax為500。

在實(shí)驗(yàn)結(jié)果的性能指標(biāo)中，精確度是被用來(lái)作為衡量準(zhǔn)確性的指標(biāo)，它是指推薦列表中用戶感興趣的項(xiàng)目所占的比例大小，即推薦項(xiàng)目既在推薦列表中又在探針集中的項(xiàng)目數(shù)與推薦列表項(xiàng)目數(shù)的比值。覆蓋率是被用來(lái)衡量多樣性的指標(biāo)，它是指推薦列表中不同的項(xiàng)目占所有項(xiàng)目的比例大小，即推薦列表中不同種類的項(xiàng)目數(shù)與所有項(xiàng)目數(shù)的比值。通過(guò)運(yùn)行實(shí)驗(yàn)，推薦算法的性能精確度與多樣性如圖3所示。

圖3 推薦算法的精確度與多樣性

從圖3中可以清晰看出，免疫算法可以有效求得不同的解，即不同的推薦項(xiàng)目。隨著推薦項(xiàng)目精確度的不斷提高，代表多樣性的覆蓋率的值不斷下降，也就說(shuō)明了準(zhǔn)確性和多樣性是存在一定的沖突，符合個(gè)性化推薦的規(guī)律。同時(shí)也可以看出，在圖中數(shù)據(jù)的中間部分，可以獲取得到一些準(zhǔn)確性比較高和多樣性也比較高的值，即滿足準(zhǔn)確性和多樣性的推薦項(xiàng)目。

5 結(jié)論

本文提出了一種同時(shí)優(yōu)化準(zhǔn)確性和多樣性的個(gè)性化推薦模型，并使用免疫算法進(jìn)行了交叉和變異算子的設(shè)計(jì)。為了降低計(jì)算復(fù)雜度，使用協(xié)同過(guò)濾技術(shù)對(duì)用戶進(jìn)行了分類。實(shí)驗(yàn)結(jié)果顯示了算法的有效性。隨著用戶和項(xiàng)目數(shù)量的增加，推薦系統(tǒng)的準(zhǔn)確性和多樣性仍然可以進(jìn)一步提升，這也是我們下一步繼續(xù)深入研究的內(nèi)容。

[1]MF Alhamid，M Rawashdeh，H Dong，MA Hossain．Exploring Latent Preferences for Context-Aware Personalized Recommendation Systems[J]．IEEE Transactions on Human-Machine Systems，2016，46(4)：1-9．

[2]M Gao，B Ling，Q Yuan，Q Xiong，L Yang．A Robust collaborative filtering approach based on user relationships for recommendation systems [J]．Mathematical Problems in Engineering，2014，2014(2)：1-8．

[3]Y Sun，WK Chong，YS Han，S Rho，KL Man．Key factors affecting user experience of mobile recommendation systems[J]．Lecture Notes in Engineering&Computer Science，2015，2 2 16(1)．

[4]J．Bobadilla，F(xiàn)．Ortega，A．Hernando，A．Gutierrez．Recommend system survey[J]．Knowledge-based system．2013，46：10 9-13 2．

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

[6]Y．Guan，D．Zhao，A．Zeng，M．-S．Shang．Preference of online users and personalized recommendations[J]．Physica A．2013，392 (16)：3417-3423．

[7]王國(guó)霞，劉賀平．個(gè)性化推薦系統(tǒng)綜述[J]．計(jì)算機(jī)工程與應(yīng)用，2012，48(7)：66-76．

[8]X．Ren，L．Lu，R．Liu，J．Zhang．Avoiding congestion in recommender systems[J]．New J．Phys．2014，16(6)．

[9]孟祥武，胡勛，王立才，等．移動(dòng)推薦系統(tǒng)及其應(yīng)用[J]．軟件學(xué)報(bào)，2013，2 4(1)：9 1-108．

[10]孟祥武，劉樹(shù)林，張玉潔，等．社會(huì)化推薦系統(tǒng)研究[J]．軟件學(xué)報(bào)，2015，2 6(6)：13 56-13 72．

[11]許海玲，吳瀟，李曉東，等．互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]．軟件學(xué)報(bào)，200 9，2 0(2)：3 50-3 6 2．

[12]F Ricci，L Rokach，B Shapira，PB Kantor．Recommender systems handbook[M]．Springer，2011．

Personalized Recommendation System Based on Immune Algorithm

Wang Yulin Wang Yongjian Chai Zhengyi
（Tianjin Polytechnic University，Tianjin 300387）

To meet different needs of users in the recommendation system,an immune clone algorithm is proposed.The problem is modeled as a multi-objective optimization problem to maximize the accuracy and diversity in the recommendation lists.It uses collaborative filtering technology to finish the user classification.Antibody coding and the immune operator that suitable for solving the problem are designed in the algorithm.The results show that the proposed algorithm can effectively obtain the optimal solutions of personalized recommendation,which satisfies with different needs of multiple users at the same time.

immune algorithm;multi-objective optimization;personalized recommendation;collaborative filtering

TP18

符：A

1008-6609(2016)10-0001-03

王玉林（19 9 1-），男，山西大同人，碩士研究生，研究方向?yàn)橹悄軆?yōu)化算法。

國(guó)家自然科學(xué)基金項(xiàng)目，項(xiàng)目編號(hào)U 150 46 13；中國(guó)博士后科學(xué)基金，項(xiàng)目編號(hào)2015M 58 6 2 2。