面向海量數(shù)據(jù)的推薦系統(tǒng)的研究

摘 要： 在處理大數(shù)據(jù)時(shí)，傳統(tǒng)的推薦系統(tǒng)，如常規(guī)協(xié)同過(guò)濾的推薦性能受到了限制。使用操作簡(jiǎn)便的K均值聚類算法與協(xié)同過(guò)濾構(gòu)成組合推薦算法具有較好的推薦性能，該文使用遺傳算法對(duì)組合推薦算法進(jìn)行優(yōu)化，簡(jiǎn)化組合推薦算法，降低組合算法的復(fù)雜度和成本。同時(shí)，通過(guò)對(duì)遺傳算法進(jìn)行改進(jìn)，以提高遺傳算法的優(yōu)化能力，提高推薦系統(tǒng)性能。最后，通過(guò)MovieLens電影打分?jǐn)?shù)據(jù)集對(duì)該文研究的推薦算法進(jìn)行性能測(cè)試。結(jié)果表明，遺傳算法的優(yōu)化能力得到提升，推薦系統(tǒng)的性能有所提高。

關(guān)鍵詞： 大數(shù)據(jù)； 推薦系統(tǒng)； 協(xié)同過(guò)濾； 遺傳算法； K均值聚類

中圖分類號(hào)： TN911?34； TP18 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）12?0059?03

Abstract： When dealing with large data， the traditional recommendation system， such as conventional collaborative filtering， is limited in its recommendation performance. The combination recommendation algorithm formed by K means clustering algorithm and collaborative filtering algorithm has better recommendation performance. The genetic algorithm is used in this paper to optimize the combination recommendation algorithm to simplify the algorithm so as to reduce the complexity and cost of the combination algorithm. At the same time， the genetic algorithm is ameliorated to improve the optimization ability of the genetic algorithm and the performance of the recommendation system. The performance test of the recommendation algorithm was carried out by means of the MovieLens film scoring data set. The test results show that the optimization ability of the genetic algosithm and the performance of recommendation system have been improved.

Keywords： big data； recommendation system； collaborative filtering； genetic algorithm； K means clustering

0 引 言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，互聯(lián)網(wǎng)信息數(shù)據(jù)量正呈現(xiàn)出爆炸式的增長(zhǎng)，已經(jīng)進(jìn)入了大數(shù)據(jù)時(shí)代，大數(shù)據(jù)正在引領(lǐng)一場(chǎng)新的技術(shù)革命。在互聯(lián)網(wǎng)的海量數(shù)據(jù)中尋找用戶關(guān)心感興趣的信息正是推薦系統(tǒng)誕生的目的。推薦系統(tǒng)經(jīng)過(guò)不斷發(fā)展和更新，已經(jīng)擁有了相對(duì)成熟的技術(shù)，其中最有效的技術(shù)之一即是協(xié)同過(guò)濾。協(xié)同過(guò)濾能夠?qū)τ脩舻膫€(gè)性信息進(jìn)行記錄和提取，并使用這些信息建立用戶模型，使用推薦算法建立的推薦系統(tǒng)將符合用戶興趣的信息主動(dòng)地推薦給用戶。協(xié)同過(guò)濾推薦系統(tǒng)實(shí)際上可以認(rèn)為是一種打分預(yù)測(cè)過(guò)程。以向用戶推薦其感興趣的電影為例，推薦系統(tǒng)能夠根據(jù)用戶觀看的電影歷史信息以及該用戶本身的個(gè)性化信息，并通過(guò)一定的推薦算法向用戶推薦其可能感興趣的電影[1?6]。

在處理大數(shù)據(jù)時(shí)，傳統(tǒng)的推薦系統(tǒng)的性能受到了限制，在大數(shù)據(jù)環(huán)境下的推薦系統(tǒng)需要考慮大數(shù)據(jù)的特性，首先大數(shù)據(jù)環(huán)境下，推薦系統(tǒng)需要有更加強(qiáng)大的數(shù)據(jù)處理性能，因?yàn)樾枰幚淼臄?shù)據(jù)量更加龐大并且存在更高冗余以及噪聲的數(shù)據(jù)。其次大數(shù)據(jù)環(huán)境下，推薦系統(tǒng)需要有更快的更新速度，以滿足海量數(shù)據(jù)處理能力。最后，大數(shù)據(jù)環(huán)境下，推薦系統(tǒng)需要有更加精確的推薦能力，以解決信息過(guò)載問(wèn)題。對(duì)于大數(shù)據(jù)環(huán)境下的推薦任務(wù)，常規(guī)協(xié)同過(guò)濾的推薦效率較低。使用K均值聚類等操作簡(jiǎn)便的聚類算法與協(xié)同過(guò)濾構(gòu)成混合推薦算法具有較好的推薦性能，Google 以及Amazon等大型網(wǎng)絡(luò)公司的推薦系統(tǒng)均使用這樣的混合推薦系統(tǒng)[7?12]。

雖然使用聚類算法與協(xié)同過(guò)濾構(gòu)成混合推薦算法，能夠?qū)Υ髷?shù)據(jù)環(huán)境下的推薦系統(tǒng)的效率進(jìn)行提升，但是混合算法復(fù)雜度較高，導(dǎo)致構(gòu)建成本偏高，未解決這一問(wèn)題，使用遺傳算法對(duì)組合推薦算法進(jìn)行優(yōu)化，簡(jiǎn)化組合推薦算法，提高推薦效率以及推薦質(zhì)量。同時(shí)，本文通過(guò)對(duì)遺傳算法進(jìn)行改進(jìn)，以提高遺傳算法的優(yōu)化能力，提高推薦系統(tǒng)性能。

1 推薦算法

1.1 協(xié)同過(guò)濾算法

協(xié)同過(guò)濾算法通過(guò)對(duì)項(xiàng)目之間的相似度進(jìn)行計(jì)算從而建立一個(gè)數(shù)據(jù)集，該數(shù)據(jù)集表示項(xiàng)目之間關(guān)系的比較。隨后使用該數(shù)據(jù)集以及用戶數(shù)據(jù)對(duì)用戶的可能興趣進(jìn)行推測(cè)。對(duì)協(xié)同過(guò)濾算法計(jì)算加權(quán)打分為：

[ru，i=ki∈Isimi，i′ru，i] （1）

式中：[simi，i′]為項(xiàng)目相似度；[ru，i]為第u個(gè)用戶對(duì)第i個(gè)項(xiàng)目的打分；[k=1i∈Isimi，i′]。

通過(guò)協(xié)同過(guò)濾算法獲取初始種群的個(gè)體，步驟如下：

步驟1：通過(guò)用戶集[U]、用戶對(duì)項(xiàng)目打分集[R]以及項(xiàng)目集[I]得到用戶對(duì)項(xiàng)目打分關(guān)聯(lián)數(shù)組：

[u?i?rating， u∈U，i∈I，rating∈R] （2）

步驟2：由步驟1得到的打分關(guān)聯(lián)數(shù)組得到項(xiàng)目間的比較數(shù)據(jù)集合：

[i?i?simi，i′ ， i，i′∈I] （3）

步驟3：通過(guò)步驟2的比較數(shù)據(jù)集合得到協(xié)同過(guò)濾算法的推薦序列[x1，x2，…，xn]，此序列將作為遺傳算法的初始種群個(gè)體。

1.2 K均值聚類算法

給定一個(gè)由均為d維向量的n個(gè)觀測(cè)對(duì)象組成的觀測(cè)集[x1，x2，…，xn]， 使用K均值算法為了將觀測(cè)集[x1，x2，…，xn]劃分為k個(gè)子集[S=S1，S2，][…，Sk]，并且在分類時(shí)滿足條件：

[minSi=1kxj∈Sixj-μi2] （4）

式中：[μi]為[Si]的中心。

使用K均值聚類算法獲取新的種群個(gè)體。步驟如下：

步驟1：通過(guò)K均值聚類，將項(xiàng)目集合劃分為[k]個(gè)子集[S=S1，S2，][…，Sk]。

步驟2：由遺傳算法的交叉或變異需求，在序列中元素[yi]所在的聚類[Sj]中隨機(jī)搜尋新元素以用于遺傳算法的交叉或變異操作。

步驟3：使用遺傳算法的交叉或變異操作獲取新的種群個(gè)體，即得到新的推薦序列[y1，y2，…，yn]。

1.3 遺傳算法

使用遺傳算法將K均值聚類和協(xié)同過(guò)濾算法進(jìn)行組合。通過(guò)輸入推薦項(xiàng)目集合[I]，獲得推薦項(xiàng)目序列[z1，z2，…，zn]，步驟如下：

步驟1：通過(guò)協(xié)同過(guò)濾算法取初始種群的個(gè)體；

步驟2：對(duì)種群個(gè)體目標(biāo)函數(shù)值進(jìn)行計(jì)算；

步驟3：選取精英種群個(gè)體[y1，y2，…，yn]用于種群的繁殖；

步驟4：由K均值聚類算法進(jìn)行交叉變異操作，獲取新種群個(gè)體；

步驟5：對(duì)獲取新種群個(gè)體目標(biāo)函數(shù)進(jìn)行計(jì)算；

步驟6：獲取新種群個(gè)體代替非精英個(gè)體；

步驟7：得到遺傳算法組合算法優(yōu)化后最優(yōu)個(gè)體，即推薦項(xiàng)目的序列[13]。

1.4 改進(jìn)遺傳優(yōu)化算法

由于常規(guī)遺傳算法存在容易產(chǎn)生早熟以及局部搜索最優(yōu)解的能力弱等問(wèn)題，因此本文改進(jìn)遺傳算法的方法是引入自適應(yīng)對(duì)偶種群以及自適應(yīng)終止條件。

引入對(duì)偶種群[zit]，其對(duì)稱中心的父代種群最優(yōu)的個(gè)體[xkt]，對(duì)偶對(duì)稱中心[xkt]，從而獲得新種群[yit]。若對(duì)偶種群[zit]中的個(gè)體不處于搜索范圍內(nèi)，則隨機(jī)使用處于搜索范圍內(nèi)的個(gè)體代替。

本文改進(jìn)遺傳算法引入的自適應(yīng)終止條件為：

[ffitness_best-ffitness_worst<εi] （5）

式中：[ffitness_best]是第[i]次迭代的最優(yōu)函數(shù)適應(yīng)度；[ffitness_worst]是第[i]次迭代的最次函數(shù)適應(yīng)度；[i]是迭代次數(shù)；[εi]表示精度函數(shù)：

[εi=a+b-alogci+d] （6）

式中：[a]，[b]，[c]，[d]是常數(shù)。

本文改進(jìn)常規(guī)遺傳算法步驟為：

步驟1：初始化遺傳算法的基本參數(shù)，如交叉概率[Pc]、變異概率[Pm]、迭代次數(shù)最大值[G]以及精度函數(shù)的4個(gè)常數(shù)。在遺傳算法初期，精度函數(shù)的值很大，因此遺傳算將進(jìn)行隨機(jī)搜索，隨著迭代次數(shù)的逐漸增長(zhǎng)，精度函數(shù)的值漸漸縮小，遺傳算法逐漸進(jìn)行局部的細(xì)化搜索。

步驟2：對(duì)種群[xit]進(jìn)行初始化，同時(shí)對(duì)個(gè)體進(jìn)行編碼解碼以及求解個(gè)體適應(yīng)度，從而得到種群的最優(yōu)個(gè)體[xkt]。

步驟3：通過(guò)交叉、變異種群[xit]，以獲取新種群[yit]。

步驟4：選取一對(duì)偶種群[zit]，該種群是關(guān)于最優(yōu)個(gè)體[xkt]中心對(duì)稱的；若對(duì)偶種群[zit]中的個(gè)體不處于搜索范圍內(nèi)，則隨機(jī)使用處于搜索范圍內(nèi)的個(gè)體代替。

步驟5：更新迭代次數(shù)及精度函數(shù)等。

步驟6：遺傳算法在滿足結(jié)束條件后終止，否則跳至步驟3。

2 實(shí)驗(yàn)分析

通過(guò)實(shí)驗(yàn)MovieLens電影打分?jǐn)?shù)據(jù)集對(duì)本文研究的推薦算法進(jìn)行性能測(cè)試。MovieLens電影打分?jǐn)?shù)據(jù)集中包括近1 000名用戶以及1 600多部電影（項(xiàng)目）的詳細(xì)信息，以及近1 000名用戶對(duì)這1 600多部電影的100 000次的打分情況。本文使用的用戶特征包括用戶的性別、工作職業(yè)以及年紀(jì)。使用的項(xiàng)目的12個(gè)類型，有恐怖、戰(zhàn)爭(zhēng)、動(dòng)作、科幻、動(dòng)畫、浪漫、兒童、犯罪、喜劇、戲劇、冒險(xiǎn)以及音樂(lè)[14?15]。

本文使用交叉實(shí)驗(yàn)以提高評(píng)分預(yù)測(cè)的可靠性，因此本文將68 156條打分?jǐn)?shù)據(jù)集隨機(jī)C1，C2和C3三個(gè)數(shù)據(jù)集，并進(jìn)行三組多次實(shí)驗(yàn)。第一組實(shí)驗(yàn)將C1和C2數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)集，將C3作為測(cè)試數(shù)據(jù)集；第二組實(shí)驗(yàn)將C1和C3數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)集，將C2作為測(cè)試數(shù)據(jù)集；第三組實(shí)驗(yàn)將C2和C3數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)集，將C1作為測(cè)試數(shù)據(jù)集。

使用沒(méi)有經(jīng)過(guò)優(yōu)化的組合推薦算法、遺傳算法優(yōu)化的組合推薦算法以及本文研究的改進(jìn)型遺傳算法優(yōu)化的組合推薦算法對(duì)上述的三組實(shí)驗(yàn)方案進(jìn)行多次實(shí)驗(yàn)取平均值得到圖1的測(cè)試結(jié)果。

可以看出，使用遺傳算法優(yōu)化組合K均值聚類和協(xié)同過(guò)濾算法的推薦系統(tǒng)的打分預(yù)測(cè)精度要高于使用單純的協(xié)同過(guò)濾算法的推薦系統(tǒng)，并且本文通過(guò)對(duì)遺傳算法進(jìn)行改進(jìn)后，遺傳算法的優(yōu)化能力得以提升，推薦系統(tǒng)的打分預(yù)測(cè)精度有所提高。

3 結(jié) 語(yǔ)

協(xié)同過(guò)濾是最有效的一種推薦技術(shù)之一，其能夠?qū)τ脩舻膫€(gè)性信息進(jìn)行記錄和提取，并使用這些信息建立用戶模型，使用推薦算法建立的推薦系統(tǒng)，將符合用戶興趣的信息主動(dòng)地推薦給用戶。但是對(duì)于大數(shù)據(jù)環(huán)境下的推薦任務(wù)，常規(guī)協(xié)同過(guò)濾的推薦效率較低。一種可行的解決方法是使用K均值聚類算法與協(xié)同過(guò)濾構(gòu)成組合推薦算法。

本文使用遺傳算法對(duì)組合推薦算法進(jìn)行優(yōu)化，以簡(jiǎn)化組合推薦算法，提高推薦效率以及推薦質(zhì)量。同時(shí)，本文通過(guò)對(duì)遺傳算法進(jìn)行改進(jìn)，以提高遺傳算法的優(yōu)化能力，提高推薦系統(tǒng)性能。最后，使用MovieLens電影打分?jǐn)?shù)據(jù)集中的12個(gè)項(xiàng)目類型組成的數(shù)據(jù)集對(duì)推薦系統(tǒng)性能進(jìn)行測(cè)試，結(jié)果表明，使用遺傳算法優(yōu)化組合K均值聚類和協(xié)同過(guò)濾算法的推薦系統(tǒng)的打分預(yù)測(cè)精度要高于使用單純的協(xié)同過(guò)濾算法的推薦系統(tǒng)，并且本文通過(guò)對(duì)遺傳算法進(jìn)行改進(jìn)后，遺傳算法的優(yōu)化能力得以提升，推薦系統(tǒng)的打分預(yù)測(cè)精度有所提高。

參考文獻(xiàn)

[1] 朱揚(yáng)勇，孫婧.推薦系統(tǒng)研究進(jìn)展[J].計(jì)算機(jī)科學(xué)與探索，2015，9（5）：513?525.

[2] 孟祥武，劉樹棟，張玉潔，等.社會(huì)化推薦系統(tǒng)研究[J].軟件學(xué)報(bào)，2015，26（6）：1356?1372.

[3] 孟祥武，紀(jì)威宇，張玉潔.大數(shù)據(jù)環(huán)境下的推薦系統(tǒng)[J].北京郵電大學(xué)學(xué)報(bào)，2015，38（2）：1?15.

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

[5] 張興旺，李晨暉，麥范金.變革中的大數(shù)據(jù)知識(shí)服務(wù)：面向大數(shù)據(jù)的信息移動(dòng)推薦服務(wù)新模式[J].圖書與情報(bào)，2013（4）：74?79.

[6] 胡勛.融合移動(dòng)用戶社會(huì)化關(guān)系的協(xié)同過(guò)濾推薦方法研究[D].北京：北京郵電大學(xué)，2014.

[7] 章詩(shī)杰.移動(dòng)環(huán)境下上下文感知的協(xié)同過(guò)濾推薦模型研究[D].杭州：杭州電子科技大學(xué)，2014.

[8] 齊文.基于聚類免疫算法的個(gè)性化推薦系統(tǒng)研究[D].天津：天津財(cái)經(jīng)大學(xué)，2009.

[9] 李秦.基于用戶行為的全文檢索系統(tǒng)個(gè)性化推薦研究[D].重慶：西南大學(xué)，2009.

[10] 王立才.上下文感知推薦系統(tǒng)若干關(guān)鍵技術(shù)研究[D].北京：北京郵電大學(xué)，2012.

[11] 王泰璐.推薦系統(tǒng)中預(yù)測(cè)算法的改進(jìn)、實(shí)現(xiàn)及應(yīng)用[D].開封：河南大學(xué)，2014.

[12] 陸春，洪安邦，宮劍.基于PSO的協(xié)同過(guò)濾推薦算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（5）：101?107.

[13] 馮智明，蘇一丹，覃華，等.基于遺傳算法的聚類與協(xié)同過(guò)濾組合推薦算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014（1）：35?38.

[14] 劉旭東，葛俊杰，陳德人.一種基于聚類和協(xié)同過(guò)濾的組合推薦算法[J].計(jì)算機(jī)工程與科學(xué)，2010，32（12）：125?127.

[15] 葛潤(rùn)霞.基于內(nèi)容聚類的協(xié)同過(guò)濾推薦系統(tǒng)研究[D].濟(jì)南：山東師范大學(xué)，2008.