基于自適應(yīng)布谷鳥聚類搜索的推薦系統(tǒng)算法的研究

胡安明

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

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

中圖分類號(hào)：TP311? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）06-0087-02

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

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

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

1 布谷鳥搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 、自適應(yīng)布谷鳥搜索算法

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

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

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

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

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

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

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

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

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

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

（5） 應(yīng)用式5自適應(yīng)布谷鳥搜索算法對(duì)其他鳥巢進(jìn)行搜索更新;

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

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

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

實(shí)現(xiàn)過程

4 實(shí)驗(yàn)結(jié)果分析

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

本文采用絕對(duì)平均誤差MAE對(duì)算法進(jìn)行評(píng)估，計(jì)算公式如式（6）所示，其中[rui]為用戶u對(duì)物品i的實(shí)際評(píng)分，[rui]為用戶u對(duì)物品i的推薦預(yù)測(cè)。

[MAE=1n1nrui-rui] （6）

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4] 張燕，袁書卷，達(dá)列雄，等.基于局部搜索增強(qiáng)策略的自適應(yīng)反向?qū)W習(xí)布谷鳥算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2020，50（20）：191-200.

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

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

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