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

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

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

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

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

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

1 推薦算法

1.1 協(xié)同過濾算法

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

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

式中：[simi，i′]為項目相似度；[ru，i]為第u個用戶對第i個項目的打分；[k=1i∈Isimi，i′]。

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

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

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

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

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

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

1.2 K均值聚類算法

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

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

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

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

步驟1：通過K均值聚類，將項目集合劃分為[k]個子集[S=S1，S2，][…，Sk]。

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

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

1.3 遺傳算法

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

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

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

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

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

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

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

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

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

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

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

本文改進(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個常數(shù)。在遺傳算法初期，精度函數(shù)的值很大，因此遺傳算將進(jìn)行隨機(jī)搜索，隨著迭代次數(shù)的逐漸增長，精度函數(shù)的值漸漸縮小，遺傳算法逐漸進(jìn)行局部的細(xì)化搜索。

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

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

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

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

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

2 實驗分析

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

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

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

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

3 結(jié) 語

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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