胡安明

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

關鍵詞：布谷鳥搜索算法;推薦系統(tǒng);聚類

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

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

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

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

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

1 布谷鳥搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 基于K-means聚類和自適應布谷鳥搜索的推薦系統(tǒng)算法實現(xiàn)

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

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

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

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

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

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

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

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

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

算法實現(xiàn)過程，如圖1所示：

實現(xiàn)過程

4 實驗結果分析

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

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

[MAE=1n1nrui-rui] （6）

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

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

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

5 結論

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

參考文獻：

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

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

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

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

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

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

【通聯(lián)編輯：聞翔軍】