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

劉姣

摘 要：目前推薦系統研究面臨的主要問題是如何提高推薦準確度和用戶滿意度。為克服原始推薦算法和現存改進算法的局限性，利用一種具有較強全局搜索能力的智能優化算法——布谷鳥搜索算法，結合K-means聚類算法進行改進。在此基礎上，設計了應用于Movielens數據集基于布谷鳥搜索的聚類推薦系統總體框架，對其中關鍵技術和目前存在問題進行了分析，并指出接下來需開展的研究工作。

關鍵詞：推薦系統;布谷鳥搜索;K-means算法;智能優化算法

DOI：10. 11907/rjdk. 182830

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2019）004-0091-04

0 引言

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

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

1 K-means聚類算法概述

K-means聚類算法的基本思想是：首先把每個聚類樣本的數據均值作為初始聚類中心點，利用這些中心點進行新類別構造。然后進行算法的不斷迭代，在每次迭代時都對數據重新規劃，直到劃分出的聚簇滿足準則函數最優解。K-means算法對具有連續型屬性的數據處理得比較理想。具體執行流程為：

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

輸出：滿足方差最小標準的k個聚類。

處理流程：

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

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

（3）迭代（1）、（2）執行過程，等到所有聚類不再發生變化時終止迭代。

K-means算法中的k一般需要提前給出，如果剛開始聚類子集的個數不明確，可以對多個k值嘗試使用K-means算法。結果表明，k值變大過程中誤差平方和準則函數值隨之變小。最終，可以依照準則函數曲線的變化情況和以往經驗，推測出一個較理想的k值。

2 布谷鳥搜索算法概述

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

3 基于K-means與cuckoo的協同過濾推薦框架

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

下一步將布谷鳥搜索優化算法應用于k均值算法結果，以優化結果。

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

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

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

總地來說，本文方法包括K-means聚類技術，通過生物啟發算法——布谷鳥搜索進行優化。圖2給出了框架偽代碼。

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

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

4 結語

為了改善傳統推薦算法的不足，設計了一種基于CS優化算法的聚類推薦算法，本文對K-means聚類算法、布谷鳥搜索算法的研究現狀進行了分析。通過利用布谷鳥搜索算法的特性優化聚類推薦算法結果，并給出了基于布谷鳥搜索的聚類推薦系統總體框架。在今后工作中，將進一步對其算法效率進行研究，以獲得更好的推薦結果。

參考文獻：

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

[2] 陳軍，謝衛紅，陳揚森. 國內外大數據推薦算法領域前沿動態研究[J]. 中國科技論壇，2018 （1）：173-181.

[3] 王曉耘，錢璐，黃時友. 基于粗糙用戶聚類的協同過濾推薦模型[J]. 現代圖書情報技術，2015（1）：45-51.

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

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

[6] 何宏，譚永紅. 一種基于動態遺傳算法的聚類新方法[J]. 電子學報，2012，40（2）：254-259.

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

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

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

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

[11] 馮智明，蘇一丹，覃華，等. 基于遺傳算法的聚類與協同過濾組合推薦算法[J]. 計算機技術與發展，2014（1）：35-38.

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

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

[14] 鄭丹，王名揚，陳廣勝. 基于Weighted-slope One的用戶聚類推薦算法研究[J]. 計算機技術與發展，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] 李煜，馬良. 新型元啟發式布谷鳥搜索算法[J]. 系統工程，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.

（責任編輯：何 麗）