基于螢火蟲聚類的協同過濾推薦算法

魏濤 劉亞軍 葉傳標 曹陽

摘要：針對基于聚類的協同過濾推薦算法在進行聚類代價函數優化時容易陷入局部最優的問題，將具有良好全局最優搜索能力的螢火蟲優化算法與聚類算法相互結合，提出一種基于螢火蟲聚類的協同過濾推薦算法，實驗結果表明，所提出的算法優于基于聚類的協同過濾推薦算法，其推薦準確率更高，完成實時推薦所花費的時間更少。

關鍵詞：協同過濾;推薦系統;聚類;螢火蟲算法

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

文章編號：1009-3044（2019）33-0289-03

1概述

隨著電子商務中的商品種類和數量快速增長，為便于客戶快速選中心儀的商品，推薦系統應時而生。協同過濾推薦技術是推薦系統中的一個重要技術，該技術基于已有客戶群過去的商品選擇數據，去預測某個客戶最可能感興趣或者喜歡的商品。

協同過濾技術目前已經在推薦系統中得到廣泛應用，該技術不依賴于商品本身的信息，當商品信息殘缺時，仍然可以根據最近鄰客戶的評價值進行推薦，但該技術也存在數據稀疏和冷啟動問題，尤其是當電子商務中客戶數量急劇膨脹時，在較大的客戶空間上搜索最近鄰客戶將變得非常耗時，這使得推薦系統的實時性等性能指標難以得到保證。

為了縮小客戶搜索空間，國內外一些研究者將聚類技術引人協同過濾推薦算法中，提出了一些協同過濾推薦算法的改進算法，這些改進算法先將客戶按照對商品評價的相似性進行聚類，接著判斷目標客戶所屬的聚類，最后在其對應或鄰近的聚類中進行最近鄰客戶的搜索，從而縮小了客戶搜索空間，保證了推薦系統實時性等性能指標。

雖然這些基于聚類的協同過濾算法提高了推薦系統的推薦性能，但這些算法中使用的聚類算法容易陷人局部最優而達不到全局最優。為此，本文提出一種基于螢火蟲聚類的協同過濾推薦算法，螢火蟲算法屬于群智能優化算法，它通過螢火蟲群體中每個個體間信息交互合作來尋優，其良好的全局最優搜索能力能夠使基于客戶聚類的協同過濾算法中的聚類代價優化函數容易陷入局部最優的不足之處得到解決。

2基于螢火蟲聚類的協同過濾推薦算法

2.2客戶集合k均值聚類

利用k均值聚類將客戶集合u劃分為k個簇來縮小客戶搜索空間，首先隨機選取k個客戶作為k個簇的初始聚類中心，然后計算每個客戶與這些聚類中心的距離，把每個客戶分配給距離最近的聚類簇，分配客戶后聚類簇的中心將重新計算。以上過程重復迭代進行，最終目的是使得聚類代價函數最小，聚類代價函數如式（3）所示，其定義為各個客戶距離所屬簇中心點的誤差平方和。

2.3螢火蟲算法

螢火蟲算法是一種利用自然界中螢火蟲發光行為所設計出的群體搜索智能優化算法，這種算法用螢火蟲來模擬搜索空間中的點，通過亮度低的螢火蟲向亮度高的螢火蟲移動來求得最優解，亮度和吸引度是螢火蟲算法的兩個重要參數。

螢火蟲算法中的亮度參數表示螢火蟲所表示解的優劣程度，亮度越高，表示螢火蟲所代表的解越好，亮度低的螢火蟲因被吸引向亮度高的螢火蟲移動，故而，螢火蟲的亮度參數決定螢火蟲的移動方向，螢火蟲算法中的吸引度參數表示被吸引螢火蟲移動量的數值，螢火蟲算法的亮度、吸引度公式如式（4）、（5）所示。

由圖1所示，當最近鄰個數較小時，兩種算法的平均絕對誤差MAE均較大，隨著最近鄰個數的增多，兩種算法的平均絕對誤差MAE均逐漸減小，本文所提出的基于螢火蟲聚類的協同推薦算法比基于聚類的協同過濾推薦算法的平均絕對誤差MAE低。

為了測試本文所提出算法的實時性性能，在測試實時性性能的實驗中，最近鄰個數為30，聚類的數目以15為間隔，依次從15增加到150，基于聚類的協同過濾推薦算法與本文所提出的算法完成實時推薦所花費時間的實驗結果如圖2所示。

由圖2所示，當聚類數目較小時，兩種算法完成實時推薦所花費的時間均較大，隨著聚類數目的增多，兩種算法完成實時推薦所花費的時間均逐漸減小，本文所提出的算法完成實時推薦所花費的時間比基于聚類的協同過濾推薦算法完成實時推薦所花費的時間少。

4總結

本文提出一種基于螢火蟲聚類的協同過濾推薦算法，該算法通過螢火蟲群體中每個個體間信息交互合作來尋優，從而解決了基于聚類的協同過濾算法中的聚類算法代價優化函數容易陷入局部最優的缺點，實驗結果表明，本文所提出的算法比基于聚類的協同過濾推薦算法推薦準確率更高，完成實時推薦所花費的時間更少。