基于布谷鳥搜索的聚類推薦算法研究綜述

劉姣

摘 要：目前推薦系統(tǒng)研究面臨的主要問(wèn)題是如何提高推薦準(zhǔn)確度和用戶滿意度。為克服原始推薦算法和現(xiàn)存改進(jìn)算法的局限性，利用一種具有較強(qiáng)全局搜索能力的智能優(yōu)化算法——布谷鳥搜索算法，結(jié)合K-means聚類算法進(jìn)行改進(jìn)。在此基礎(chǔ)上，設(shè)計(jì)了應(yīng)用于Movielens數(shù)據(jù)集基于布谷鳥搜索的聚類推薦系統(tǒng)總體框架，對(duì)其中關(guān)鍵技術(shù)和目前存在問(wèn)題進(jìn)行了分析，并指出接下來(lái)需開展的研究工作。

關(guān)鍵詞：推薦系統(tǒng);布谷鳥搜索;K-means算法;智能優(yōu)化算法

DOI：10. 11907/rjdk. 182830

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）004-0091-04

0 引言

推薦系統(tǒng)已成為電子商務(wù)應(yīng)用中不可或缺的組成部分。推薦算法作為推薦系統(tǒng)的核心內(nèi)容，算法性能優(yōu)劣直接影響系統(tǒng)推薦的信息準(zhǔn)確性。因此，各學(xué)者提出了許多性能優(yōu)越的推薦算法，為用戶提供更準(zhǔn)確、更高效的推薦服務(wù)，協(xié)同過(guò)濾算法是推薦系統(tǒng)領(lǐng)域應(yīng)用最廣泛也是最成功的推薦算法，但是仍然存在數(shù)據(jù)稀疏性、算法可擴(kuò)展性與冷啟動(dòng)等許多問(wèn)題。隨著推薦系統(tǒng)規(guī)模不斷擴(kuò)大，協(xié)同過(guò)濾算法推薦時(shí)需要在整個(gè)用戶空間或項(xiàng)目空間查找目標(biāo)最近鄰居，這一查找過(guò)程將隨著系統(tǒng)中用戶和項(xiàng)目不斷增多而變得十分耗時(shí)，從而導(dǎo)致推薦系統(tǒng)的實(shí)時(shí)性難以保障。然而，推薦系統(tǒng)的評(píng)分?jǐn)?shù)據(jù)一般十分稀疏，又會(huì)導(dǎo)致協(xié)同過(guò)濾算法的推薦精度變差。文獻(xiàn)[1-2]介紹了協(xié)同過(guò)濾算法的一些研究情況。近年來(lái)許多學(xué)者將數(shù)據(jù)挖掘中的聚類算法引入推薦系統(tǒng)，通過(guò)對(duì)用戶或者項(xiàng)目進(jìn)行聚類以緩解上述問(wèn)題[3]。由于同一個(gè)類中各用戶或項(xiàng)目之間相似度較大，因此在搜索最近鄰時(shí)只需要搜索與目標(biāo)最相近的幾個(gè)類即可，從而縮小了搜索空間，大大提高了最近鄰的搜索效率，而且還能有效保證推薦結(jié)果的準(zhǔn)確度。K-means算法因其典型的基于劃分思想，具有易于實(shí)現(xiàn)、思路簡(jiǎn)單、收斂速度快、時(shí)間復(fù)雜度接近線性等優(yōu)點(diǎn)，但仍主要存在以下兩個(gè)問(wèn)題：①若初始聚類中心選取不恰當(dāng)，則易導(dǎo)致聚類結(jié)果陷入局部最優(yōu)，因而影響聚類準(zhǔn)確率;②當(dāng)數(shù)據(jù)量較大時(shí)，串行算法的計(jì)算能力有限，效率太低，無(wú)法快速響應(yīng)用戶需求。

針對(duì)以上問(wèn)題，科研人員對(duì)K-means算法嘗試了多種行之有效的改進(jìn)方法[4-9]，也將改進(jìn)算法與推薦算法結(jié)合[10-14]。布谷鳥搜索算法（Cuckoo search algorithm，CS）是一種元啟發(fā)優(yōu)化算法，能夠在局部搜索戰(zhàn)略與整個(gè)搜索空間的高效探索之間保持好平衡，常用于求解各類優(yōu)化問(wèn)題，非常適用于提高K-means 算法的全局尋優(yōu)能力，不僅可以提高推薦準(zhǔn)確率，而且可以提高推薦結(jié)果的覆蓋率，從而減小推薦系統(tǒng)的馬太效應(yīng)[15-18]。

1 K-means聚類算法概述

K-means聚類算法的基本思想是：首先把每個(gè)聚類樣本的數(shù)據(jù)均值作為初始聚類中心點(diǎn)，利用這些中心點(diǎn)進(jìn)行新類別構(gòu)造。然后進(jìn)行算法的不斷迭代，在每次迭代時(shí)都對(duì)數(shù)據(jù)重新規(guī)劃，直到劃分出的聚簇滿足準(zhǔn)則函數(shù)最優(yōu)解。K-means算法對(duì)具有連續(xù)型屬性的數(shù)據(jù)處理得比較理想。具體執(zhí)行流程為：

輸入：X={xm|m=1，2，…，n}表示的數(shù)據(jù)集，不過(guò)數(shù)據(jù)樣本并沒(méi)有包括類別屬性，而只包括描述屬性;聚類數(shù)量k。

輸出：滿足方差最小標(biāo)準(zhǔn)的k個(gè)聚類。

處理流程：

（1）從數(shù)據(jù)集X中隨機(jī)抽取k個(gè)樣本并將其視為最初聚集中心，每個(gè)中心分別表示一個(gè)類別。

（2）遍歷X中的其它樣本，分別計(jì)算它們與k個(gè)最初聚類中心的距離，找出距離最近的聚類中心，然后將其劃分到該聚類中心所代表的類中。

（3）迭代（1）、（2）執(zhí)行過(guò)程，等到所有聚類不再發(fā)生變化時(shí)終止迭代。

K-means算法中的k一般需要提前給出，如果剛開始聚類子集的個(gè)數(shù)不明確，可以對(duì)多個(gè)k值嘗試使用K-means算法。結(jié)果表明，k值變大過(guò)程中誤差平方和準(zhǔn)則函數(shù)值隨之變小。最終，可以依照準(zhǔn)則函數(shù)曲線的變化情況和以往經(jīng)驗(yàn)，推測(cè)出一個(gè)較理想的k值。

2 布谷鳥搜索算法概述

布谷鳥搜索算法是由英國(guó)學(xué)者Yang等[19-20]提出的一種元啟發(fā)算法。它主要源于布谷鳥巢寄生繁殖行為和列維飛行（Levy flights）搜索機(jī)理。巢寄生是指某些鳥類將卵產(chǎn)在其它鳥的巢中，由其它鳥代為孵化和養(yǎng)育幼鳥的繁殖行為，某些類別布谷鳥就是采用這種方式繁衍后代的。在繁殖期間，布谷鳥不筑巢，而是尋找與孵化期和育雛期相似、雛鳥食性相近、鳥蛋形狀和顏色也比較類似的宿主，尋找到合適宿主的巢之后，會(huì)趁宿主離巢外出時(shí)快速產(chǎn)卵，并讓宿主鳥代替自己孵化幼鳥。通常，布谷鳥只在一個(gè)寄生巢里產(chǎn)一枚蛋，而且之前會(huì)把宿主鳥蛋移走或全部移出巢外。列維飛行是動(dòng)物界一種覓食隨機(jī)游走的方式，游走步長(zhǎng)滿足一個(gè)重尾的穩(wěn)定分布，在游走過(guò)程中，短距離探索與偶爾長(zhǎng)距離行走相間，它也是一種最為理想的覓食搜索方式，在智能算法中采用列維搜索方式能夠克服容易陷入局部最優(yōu)解的缺點(diǎn)。

3 基于K-means與cuckoo的協(xié)同過(guò)濾推薦框架

為了克服協(xié)作推薦系統(tǒng)的局限性，設(shè)計(jì)了一種混合聚類與優(yōu)化算法的技術(shù)以提高推薦準(zhǔn)確性。使用K-means作為聚類算法和布谷鳥搜索作為優(yōu)化算法，最初將K-means聚類算法用來(lái)處理數(shù)據(jù)集，以便將用戶聚類到不同集群中。首先隨機(jī)選擇聚類中心，然后通過(guò)計(jì)算其評(píng)級(jí)和聚類中心的差異逐一檢查用戶，如果差異最小，則該用戶被分配到其最接近的集群。但是，此時(shí)不能確保每個(gè)用戶都被分配到具有最小聚類中心差異的真實(shí)集群。因此，將每個(gè)用戶的距離與其集群平均值進(jìn)行比較，并與其它集群進(jìn)行比較，用與任何集群平均值的最小距離表示并重新定位用戶，然后進(jìn)行算法的不斷迭代，在每次迭代時(shí)都對(duì)數(shù)據(jù)重新進(jìn)行規(guī)劃，直到劃分出的聚簇滿足準(zhǔn)則函數(shù)最優(yōu)解。

下一步將布谷鳥搜索優(yōu)化算法應(yīng)用于k均值算法結(jié)果，以優(yōu)化結(jié)果。

使用適應(yīng)度函數(shù)準(zhǔn)備聚類，該函數(shù)有助于改善用戶的質(zhì)心距離，而適應(yīng)度函數(shù)在有限次數(shù)迭代中改變先前的質(zhì)心（將質(zhì)心重新定位到用戶）。然后，通過(guò)計(jì)算最小質(zhì)心差異或應(yīng)用k均值再次對(duì)用戶進(jìn)行分類。布谷鳥搜索算法可以使用以下3個(gè)理想規(guī)則描述：①設(shè)定每只布谷鳥每次只產(chǎn)下一個(gè)蛋，并且對(duì)放入蛋的鳥巢選擇是隨機(jī)的;②將能夠最好地孵化蛋的鳥巢即最優(yōu)巢保留到下一代;③布谷鳥能選擇的可用于放蛋的宿主巢數(shù)量是固定的，且宿主發(fā)現(xiàn)布谷鳥放的蛋非親生的概率為Pα∈（0，1）。

在框架中，將每一個(gè)用戶視為鳥蛋，每個(gè)嵌套都可以看作一個(gè)簇。圖1展示了布谷鳥搜索算法的基本步驟。該過(guò)程從初始化開始，其中引入n個(gè)宿主巢的隨機(jī)群體，并且獲得列維飛行行為方程，然后使用適應(yīng)度函數(shù)獲得適應(yīng)度以求得最優(yōu)解。Lévy飛行是隨機(jī)游走，其中步長(zhǎng)根據(jù)Lévy分布，可以借助拉普拉斯和傅立葉變換計(jì)算步長(zhǎng)與Lévy穩(wěn)定分布。它已經(jīng)在布谷鳥優(yōu)化算法中實(shí)現(xiàn)，飛行長(zhǎng)度為x（N）～N1/α，其中0<α<2，x是隨機(jī)變量，N是步長(zhǎng)。布谷鳥行進(jìn)距離可以使用上述等式計(jì)算每次迭代。選擇一個(gè)隨機(jī)的巢，比如j，然后比較布谷鳥蛋（進(jìn)入新的解決方案）的適合度與巢中宿主蛋的適應(yīng)度。在這種情況下，布谷鳥蛋的適應(yīng)度函數(shù)值小于或等于隨機(jī)選擇的嵌套適應(yīng)度函數(shù)值，然后隨機(jī)選擇的嵌套j由等式（1）中給出的新分辨率替換。

當(dāng)適應(yīng)度函數(shù)值趨于零時(shí)，解之間的偏差隨著迭代次數(shù)增加而減少，并且如果布谷鳥蛋與正常蛋相似，則主鳥難以區(qū)分蛋。適應(yīng)性是解決方案的不同之處，如果布谷鳥蛋的適應(yīng)性大于隨機(jī)選擇的巢，則新的解決方案被隨機(jī)選擇所取代，宿主鳥可以區(qū)分宿主和布谷鳥蛋。

總地來(lái)說(shuō)，本文方法包括K-means聚類技術(shù)，通過(guò)生物啟發(fā)算法——布谷鳥搜索進(jìn)行優(yōu)化。圖2給出了框架偽代碼。

通過(guò)興趣相似性對(duì)用戶進(jìn)行分類的聚類類似于宿主鳥巢，并且每個(gè)蛋類似于布谷鳥優(yōu)化算法中的用戶，最初分類的用戶被認(rèn)為是寄主鳥蛋，選擇一些隨機(jī)用戶初始化集群（嵌套）。初始化集群并實(shí)施K-means以對(duì)最初選擇的用戶進(jìn)行分類，如算法中所示。未選擇的用戶是隨機(jī)選擇的。對(duì)于每個(gè)隨機(jī)選擇的用戶，隨機(jī)選擇一個(gè)簇和適應(yīng)度函數(shù)。根據(jù)計(jì)算該用戶適應(yīng)度函數(shù)，宿主鳥可以檢測(cè)到蛋（用戶），或者它可以保留在巢中。一旦布谷鳥蛋孵化，它就會(huì)試圖將其它蛋隨機(jī)地從巢中扔出來(lái)。如果布谷鳥蛋適應(yīng)度優(yōu)于集群中已存在的多個(gè)用戶的預(yù)定義百分比，則在算法中完成此操作。

圖3展示了算法應(yīng)用于Movielens數(shù)據(jù)集的流程。通過(guò)讀取文件，記錄Movielens數(shù)據(jù)集，并且使用k均值聚類到k個(gè)聚類中，將數(shù)據(jù)集劃分為聚類，使得每個(gè)聚類具有聚類中心。計(jì)算用戶與聚類中心之間的距離，并將用戶放置在聚類中心距離最近的簇中。當(dāng)所有用戶都被重新定位時(shí)，重新定位聚類中心并計(jì)算新的位置。計(jì)算用戶給出的估計(jì)評(píng)級(jí)，并且使用布谷鳥搜索算法進(jìn)行優(yōu)化。

4 結(jié)語(yǔ)

為了改善傳統(tǒng)推薦算法的不足，設(shè)計(jì)了一種基于CS優(yōu)化算法的聚類推薦算法，本文對(duì)K-means聚類算法、布谷鳥搜索算法的研究現(xiàn)狀進(jìn)行了分析。通過(guò)利用布谷鳥搜索算法的特性優(yōu)化聚類推薦算法結(jié)果，并給出了基于布谷鳥搜索的聚類推薦系統(tǒng)總體框架。在今后工作中，將進(jìn)一步對(duì)其算法效率進(jìn)行研究，以獲得更好的推薦結(jié)果。

參考文獻(xiàn)：

[1] 王凌，沈婧楠，王圣堯，等. 協(xié)同過(guò)濾算法研究進(jìn)展[J]. 控制與決策，2015，30（2）：193-202.

[2] 陳軍，謝衛(wèi)紅，陳揚(yáng)森. 國(guó)內(nèi)外大數(shù)據(jù)推薦算法領(lǐng)域前沿動(dòng)態(tài)研究[J]. 中國(guó)科技論壇，2018 （1）：173-181.

[3] 王曉耘，錢璐，黃時(shí)友. 基于粗糙用戶聚類的協(xié)同過(guò)濾推薦模型[J]. 現(xiàn)代圖書情報(bào)技術(shù)，2015（1）：45-51.

[4] 喻金平，鄭杰，梅宏標(biāo). 基于改進(jìn)人工蜂群算法的K-均值聚類算法[J]. 計(jì)算機(jī)應(yīng)用，2014，34（4）：1065-1069+1088.

[5] 劉靖明，韓麗川，侯立文. 基于粒子群的K均值聚類算法[J]. 系統(tǒng)工程理論與實(shí)踐，2005，25（6）：54-58.

[6] 何宏，譚永紅. 一種基于動(dòng)態(tài)遺傳算法的聚類新方法[J]. 電子學(xué)報(bào)，2012，40（2）：254-259.

[7] 郭凱，李海芳，王會(huì)青. 一種人工免疫的自適應(yīng)譜聚類算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2013，34（4）：856-859.

[8] 王彩霞. 基于改進(jìn)引力搜索的混合 K-調(diào)和均值聚類算法研究[J]. 計(jì)算機(jī)應(yīng)用研究，2016，33（1）：118-121.

[9] 王日宏，崔興梅，李永珺. 自適應(yīng)調(diào)整的布谷鳥搜索K-均值聚類算法[J/OL]. 計(jì)算機(jī)應(yīng)用研究，2018， 35（12）. [2017-12-08]. http：//www.arocmag.com/article/02-2018-12-038.html.

[10] 任帥，王浙明，王明敏. 基于用戶行為模型和蟻群聚類的協(xié)同過(guò)濾推薦算法[J]. 微型電腦應(yīng)用，2014（3）：5-8.

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

[12] 喬平安，曹宇，任澤乾. 融合隱語(yǔ)義模型和K-meansplus聚類模型的推薦算法[J]. 計(jì)算機(jī)與數(shù)字工程，2018（6）：1108-1111.

[13] 丁小煥，彭甫镕，王瓊，陸建峰. 基于平行因子分解的協(xié)同聚類推薦算法[J]. 計(jì)算機(jī)應(yīng)用，2016，36（6）：1594 -1598+1604.

[14] 鄭丹，王名揚(yáng)，陳廣勝. 基于Weighted-slope One的用戶聚類推薦算法研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2016 （4）：51-55.

[15] GANDOMI AH， YANG X S， ALAVI AH. Cuckoo search algorithm： a meta heuristic approach to solve structural optimization problems[J]. Engineering with Computers，2013;29：17-35.

[16] 李煜，馬良. 新型元啟發(fā)式布谷鳥搜索算法[J]. 系統(tǒng)工程，2012，30（8）：64-69.

[17] FENG D， QI R， LIMIN D U. Binary cuckoo search algorithm [J].? Journal of Computer Applications， 2013， 33 （6）： 1566-1570.

[18] SURESH S， LAL S， REDDY C S， et al. A novel adaptive cuckoo search algorithm for contrast enhancement of satellite images [J].? IEEE Journal of Selected Topics in Applied Earth Observations & Remote Sensing，2017 （99）：1-12.

[19] YANG X S，DEB S. Cuckoo search via lévy flights[C].? Nature & Biologically Inspired Computing，2009：210-214.

[20] YANG X S，DEB S. Engineering optimization by cuckoo search[J]. International Journal of Mathematical Modelling and Numerical Optimization，2010，1（4）：330-343.

（責(zé)任編輯：何 麗）