基于自適應布谷鳥聚類搜索的推薦系統算法的研究

胡安明

摘要：推薦系統本質是一種信息檢索技術，能根據用戶喜好在海量數據中檢索出合適數據推薦給用戶，傳統推薦系統一般使用協同過濾推薦算法，協同過濾推薦算法主要通過挖掘用戶的歷史行為數據進行推薦，但傳統推薦算法存在著稀疏矩陣、冷啟動、實時性等問題困擾[1];因此，本文提出一種基于自適應布谷鳥聚類搜索的改進推薦系統算法，首先對推薦數據進行聚類處理，然后利用布谷鳥算法較強的全局搜索能力，提升推薦系統的準確度，實驗結果表明，引入自適應布谷鳥聚類搜索能對傳統協同過濾算法在推薦精度、召回率等方面指標方面有一定提高，計算效果優于傳統推薦算法。

關鍵詞：布谷鳥搜索算法;推薦系統;聚類

中圖分類號：TP311? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）06-0087-02

開放科學（資源服務）標識碼（OSID）：

近年來，隨著軟件技術和大數據技術的不斷發展，基于大數據平臺的服務推薦系統技術應運而生生，推薦系統技術針對每位用戶提供個性化推薦服務。解決了海量數據情況下，信息過載問題;但如何讓用戶高效精確的訪問到所需的資源，減少搜索時間;如何根據用戶的個人歷史行為數據，結合網絡資源情況，挖掘用戶偏好特點，有效地處理推薦用戶所需的信息資源，仍是目前推薦系統研究的熱點。

傳統推薦算法采用協同過濾算法進行推薦，其原理為：挖掘出數據集中與目標用戶具有相同的興趣愛好、消費行為或社會屬性的用戶數據，將這些用戶感興趣的物品推薦給目標用戶[2]。但隨著數據規模的擴大，海量的信息資源，協同過濾算法需要計算整個項目中所有用戶的數據進行查找推薦，這一過程這就存在著耗時過高，同時海量數據也造成稀疏矩陣，推薦精度下降等問題[3]。因此，必須引入其他智能算法改進推薦系統算法。

1 布谷鳥搜索算法

布谷鳥搜索（Cuckoo Search，CS）算法是Xin-She Yang 等于2009 年在群體智能技術的基礎上提出的搜索算法，CS算法是依據布谷鳥在其他鳥巢中的育雛行為與其他它鳥類的萊維飛行（Levy flight）行為的元啟發類算法，CS算法具有很強的搜索能力，相比其他算法而言，CS算法輸入參數少，結構簡單，易于實現等有點。但CS算法也存在著局部搜索能力差，搜索后期收斂速度慢等缺點。因此，在原始CS算法基礎上進行改進，以適應應用的需求是必須要的。本文使用自適應布谷鳥聚類算法（ K-means Adaptive Cuckoo Search，K-means ACS）與推薦算法相結合，改進推薦系統中存在的長尾分布等問題，提升推薦系統的精度，提升推薦系統效率。

CS算法實現是來源于布谷鳥寄生繁殖行為，在自然界中布谷鳥在寄主鳥鳥巢中產卵繁衍后代，布谷鳥通過模仿寄主鳥蛋的顏色和圖案或選擇合適的時間進行產卵增加后代生存率，布谷鳥尋巢過程就是萊維飛行（Levy flight），萊維飛行是一種隨機行走。

CS算法實現過程就是將現有的寄主鳥巢看作一代，將卵隨機產在寄主鳥巢。目標就是通過不斷的多次迭代尋找出潛在最優鳥巢替代現有鳥巢[4]。CS算法實現過程如下：

（1） 布谷鳥每次產一枚卵，假設有N個鳥巢，原始位置為[Xi=（1，2，3，…）]，寄主鳥發現概率值：[Pa∈（0，1）]，對算法迭代次數和問題維度進行初始化。

（2） 對所有鳥巢位置計算，獲得所有鳥巢位置的函數值，計算所有鳥巢函數值后，對比所得適應度函數值，找出最優函數值，利用萊維飛行的隨機步長計算公式如式（1）：

[xt+1，i=xt，i+a0?Levy（β）]? ? ? ? （1）

其中[xt+1，i]表示，第[i]個鳥巢的[t+1]代的更新位置，[xt，i]表示第[i]個鳥巢的[t]代的位置，[a0]表示步長縮放因子，[?]表示卷積運算操作，[Levy（β）]表示萊維飛行，[β]表示萊維飛行的控制因子。

（3） 其中萊維飛行的路徑具有隨機性，Mantegna在1994年提出一種用正態分布對萊維飛行進行求解，計算公式如式（2）：

[Levyβ=Φ×uv/β]? ? ? ? ? ? ? ? ? ? ?（2）

其中u，v為正態分布隨機量，一般情況下取值在1.5，[Φ]計算過程如式（3）：

[Φ=（Γ（1+β）×sin （π×β/2）β×Γ（1+β2）×2（β-1）/2）1/β]? ? ? ? ? ? ? ?（3）

其中[Γ]為標準的Gamma函數，綜上所述鳥巢的位置計算如式（4）：

[xt+1，i=xt，i+a?Φ×uv/β]? ? （4）

其中a表示步長縮放因子，為（0，1）間的平均分布隨機數;算法通過全局隨機搜索更新每個鳥巢位置，然后依據寄主鳥發現概率值：[Pa]對一部分分解淘汰，再通過局部隨機搜索對淘汰值進行更新[5]。

2 、自適應布谷鳥搜索算法

CS 算法通過模擬布谷鳥的寄生繁衍策略來尋找最優解。在算法求解過程中，是通過萊維飛行來確定下一次飛向的鳥巢位置，萊維飛行隨機步長越長，則搜索的精度越低，越容易搜索全局最優解;飛行步長越短，則會提高搜索精度，但會嚴重影響搜索速度;一般萊維飛行步長通過控制因子a進行控制，但a一般取固定值，這就導致CS算法迭代后期，萊維飛行步長變大，使得算法不易收斂;因此，為了能夠自動適應搜索步長的變化，均衡CS算法的搜索步長，提高算法收斂速度，文獻[6]提出一種自適應調整步長縮放因子的調整策略算法，算法過程如式（5）：

[ai=1tal+au-alFmax-FiFmax-Fmin;i=1，2，…，n] （5）

其中，[al]為預定最小步長因子;[au]為預定最大步長因子：[Fi]為當前鳥巢位置，[Fmax]為本次迭代中鳥巢位置最大值：[Fmin]為本次迭代中鳥巢位置最小值，t為當前迭代次數。

3 基于K-means聚類和自適應布谷鳥搜索的推薦系統算法實現

傳統推薦算法采用協同過濾算法進行推薦，該算法的實現過程是：通過用戶與待推薦物的歷史行為數據，構造協同過濾矩陣，通過每一行用戶對物品的評價，和每一列所有用戶對物品的評價，進行協同過濾計算，從中篩選出用戶可能感興趣的物品。但隨著數據規模的擴大，海量的信息資源，協同過濾算法需要計算整個項目中所有用戶的數據進行查找推薦，這一過程這就存在著耗時過高，同時海量數據也造成稀疏矩陣等問題，導致推薦精度下降等問題。

因此，引入K-means聚類和自適應布谷鳥搜索算法改進推薦系統算法（K-means ACS），實現過程如下：

（1） 提取用戶特征數據，隨機選取n個樣本作為聚類中心點，對用戶數據進行聚類;

（2） 逐個檢查每個聚類樣本與用戶間的距離，確保差異小的用戶聚到一類;

（3） 確定用戶數據聚類數n，即確定n個鳥巢并初始化，及最大迭代次數[Iterator]，發現概率P，最大步長[Fmax]，最小步長[Fmin];

（4） 進行聚類劃分，計算每個鳥巢的適應度值，找出最優鳥巢;

（5） 應用式5自適應布谷鳥搜索算法對其他鳥巢進行搜索更新;

（6） 重復4、5兩步，通過自適應布谷鳥算法優化更新所有鳥巢，即聚類;

（7） 直至迭代次數達到最大[Iterator]迭代次數。

算法實現過程，如圖1所示：

實現過程

4 實驗結果分析

本實驗軟件環境為：Windows10操作系統、Python3.7，硬件環境為：Intel 2.9GHz CPU、16GB RAM、硬盤500GB。實驗數據選擇MovieLens 1MB版本數據集，該數據集是美國明尼蘇達大學GroupLens小組建立的電影影評數據集，共收錄了6，040余名用戶，3706部電影的100萬條評論數據，每條評論包含有發表評論時間。

本文采用絕對平均誤差MAE對算法進行評估，計算公式如式（6）所示，其中[rui]為用戶u對物品i的實際評分，[rui]為用戶u對物品i的推薦預測。

[MAE=1n1nrui-rui] （6）

測試對不同聚類數n情況下進行算法驗證，根據MAE值判斷尋找出最優聚類個數，聚類個數n取值2～70范圍，從圖2中可以看出聚類個數在64個時MAE值最低，達到最優。

K-means聚類和自適應布谷鳥搜索的推薦系統算法（K-means ACS）與傳統ItemCF算法相比，在MovieLens 1MB數據集上，Top-N值分別取10，20，30的情況下，MAE值情況如表1所示：

從實驗結果分析：本文使用MovieLen 1 MB數據集，在Top-N為20時下K-means聚類和自適應布谷鳥搜索算法改進推薦系統算法對傳統協同過濾算法在MAE指標方面有一定提高，計算效果好于傳統推薦算法。

5 結論

本文針對傳統推薦系統算法協同過濾的推薦過程中存在的問題進行分析，在此基礎上引入布谷鳥搜索算法，對布谷鳥搜索算法的原理及實踐應用存在的問題進行分析，引出自適應布谷鳥算法;在此基礎上提出一種K-means聚類和自適應布谷鳥搜索的推薦系統算法，并詳細論述了該算法的實現過程。通過實驗分析，基于K-means聚類和自適應布谷鳥搜索的推薦系統算法對傳統推薦算法有一定改進效果，為傳統的協同過濾算法的改進提供了一些思路。

參考文獻：

[1] 王國霞，劉賀平.個性化推薦系統綜述[J].計算機工程與應用，2012，48（7）：66-76.

[2]蘇慶，章靜芳，林正鑫，等.改進模糊劃分聚類的協同過濾推薦算法[J].計算機工程與應用，2019，55（5）：118-123.

[3] 張玉潔，杜雨露，孟祥武.組推薦系統及其應用研究[J].計算機學報，2016，39（4）：745-764.

[4] 張燕，袁書卷，達列雄，等.基于局部搜索增強策略的自適應反向學習布谷鳥算法[J].數學的實踐與認識，2020，50（20）：191-200.

[5] 向庭立，王紅軍，史英春.基于布谷鳥搜索的混合傳感器網絡覆蓋優化策略[J].計算機工程，2019，45（12）：79-85.

[6] 楊輝華，王克，李靈巧，等.基于自適應布谷鳥搜索算法的K-means聚類算法及其應用[J].計算機應用，2016，36（8）：2066-2070.

【通聯編輯：聞翔軍】