改進的蜂群優化聚類集成聯合相似度推薦算法

王 巖,王聰英,申艷梅

(河南理工大學 計算機科學技術學院,河南 焦作 454000)

0 概述

近年來,隨著計算機技術的飛速發展,各個行業都收集到大量的數據,而在這些大量數據背后隱藏著很多重要的信息,為了更好地利用這些數據對用戶進行精準定位或者為用戶提供個性化服務,推薦系統應運而生。該系統經過多年的積累和沉淀已成功應用于在線視頻、社交網絡和電子商務等諸多領域。協同過濾技術是在推薦系統中應用較成功的技術,同時,聚類分析也是一種重要的技術手段。協同過濾技術是解決信息過載的有效方法之一[1-3],而聚類分析是研究物以類聚的一種科學有效的方法,它可以使得原始無分類、無規律以及錯綜復雜的數據反映出一定的規律性或特殊的分類性。文獻[4]提出將數據挖掘中的K-means++聚類算法應用于入侵檢測系統。為避免K-means++聚類算法陷入局部最優,研究人員采用集成聚類來優化聚類算法,如文獻[5]利用優勢集搜索方法在聚類集成中找出超簇,并找到聚類集成結果。同時,研究人員采用人工蜂群算法來優化協同過濾算法中使用的聚類算法。人工蜂群算法是一種新穎的基于群智能的全局優化算法,它屬于群智能算法的一種。如文獻[6]多次使用歐式距離進行聚類,利用Bagging進行集成學習來改變聚類,以提高聚類效果。文獻[7]在傳統人工蜂群算法[8-9]上進行改進,提出一種基于回溯搜索的人工蜂群算法,該算法對圖像進行處理時,其精度和收斂速度都明顯提高。雖然上述算法都在一定程度上提高了聚類效果,但是在聚類時并沒有充分有效地挖掘數據集的信息,因此在進行推薦時會出現數據稀疏[3]和冷啟動等問題。

針對上述問題,本文提出一種改進的聚類集成聯合相似度推薦算法。采用K-means++算法進行聚類,并利用改進的蜂群算法優化K-means++聚類中心,使用集成方法對聚類進行集成,從而得出最佳聚類結果。同時,在數據集Iris、Red Wine、Australia與MovieLens上驗證聚類集成算法的收斂時間和誤差均值。采用聯合相似度算法計算同類用戶間的相似度,并在MovieLens數據集上驗證本文算法的推薦效果。

1 聚類的個性化推薦

1.1 蜂群優化聯合相似度算法

本文算法依據用戶的歷史行為信息構造出用戶評分矩陣。利用用戶的評分信息和用戶屬性信息進行聚類,并采用改進的蜂群算法對聚類中心進行優化,使得算法能夠解決局部最優的問題,進而提高聚類效果。在此基礎上,依據評價聚類標準CH(Calinski-Harabasz)對改進聚類算法進行評估,通過對訓練數據集進行多次K-means++聚類,利用Bagging方法集成聚類結果,并采用一致性函數進行引導聚合,得到聚類結果k。在同一類別中采用聯合相似度算法計算該類別中的鄰居用戶。為找到效果最佳的相似度算法,本文對多種相似度算法進行對比,從而找到最優搭配相似度。根據相似度值的排序找出與目標用戶鄰近的集合,再通過對最鄰近集合中用戶對項目的評分數據加權得到對未知項目的評分,將計算得到的評分數據用來預測目標用戶對未知項目的評分,將得到的評分與設置閾值相比較,當其大于設置閾值時,則將其推薦給用戶;否則,不能將其推薦給用戶。

1.1.1 K-means++聚類算法

為解決K-means++算法初始點比較敏感的問題,本文選用K-means++聚類算法對初始值進行改進。K-means++聚類算法的描述如下:

輸入無標記的訓練集合U{X1,X2,…,Xi},Xi(i=1,2,…,k)表示隨機挑選一個用戶作為第i個聚類中心點

輸出聚類的數目k

步驟1在所有集合中隨機挑選一個用戶作為第一個聚類中心點X1。

步驟3如果A(Xi)點較大,則很有可能被選擇作為一個新的聚類中心點。

步驟4重復步驟2和步驟3,直至選出k個聚類中心,聚類結束。

1.1.2 改進的人工蜂群算法

由于K-means++算法對數據進行聚類時,得到的聚類中心的計算大多依賴于前面得到的聚類中心,使得在進行大規模數據計算時受到限制,為解決該問題,本文采用人工蜂群算法對K-means++算法進行優化,但是傳統的人工蜂群算法會使聚類中心受到局部限制,因此本文采用改進的人工蜂群算法對聚類中心進行優化,這樣不僅可以對數據進行全面優化,而且還可以解決因全局變量變化引起的局部受限問題。改進的人工蜂群算法主要分為以下4個階段:

1)改進初始化。由于傳統的人工蜂群算法中初始值的設置是隨機產生的,為了提高算法的性能,本文對生成初始值的隨機方式進行改進,具體如下所示:

xij=xminj+random[0,1](xmaxj-xminj)

(1)

2)改進引領蜂。為了尋找在不同時期對種群的調整方式,本文對引領蜂進行線性搜索,使得算法能夠動態調整蜜蜂的采蜜領域范圍,線性調整公式如下所示:

ds=-dmin+(MCN-g)(dmin-dmax)/MCN

(2)

φij=ds-2×ds×rand(-1,1)

(3)

其中,MCN表示最大迭代次數,g表示當前迭代次數,dmin和dmax分別代表鄰域的最小范圍和最大范圍。在每次迭代過程中,對式(3)中的φij進行更新。

在線性調整公式中,前期g值較小,ds值變大,則范圍就越大,蜂群可以在較大鄰域內進行搜索;后期g值變大,ds值變小,則范圍就越小,蜂群可以在該鄰域內進行細致搜索。

蜜源更新是引領蜂依據其記憶中的食物源位置進行鄰居搜索,并找到食物源附近的更好食物源。當引領蜂找到一個食物源之后會評估其適應度值,采用式(4)來確定鄰居食物源:

vij=xij+aφij(xij-xkj)

(4)

其中,a是隨機數,且k≠i,j=(1,2,…,D),φij為隨機數且φij∈(-1,1),xij代表產生的新位置。

由式(4)可知蜜源搜索的新解,它的全局搜索能力較好,但是其局部搜索能力較差。因此,將在搜索策略中引入自適應步長,在搜索中利用新的搜索策略對xij和目前最佳解xbest(ij)進行搜索,進而提高局部搜索策略的效率,其中,加強局部鄰域搜索的表達式為:

vij=λxij+(1-λ)xbest(ij)+

φij((1-λ)(xbest(ij)-xkj))

(5)

3)改進跟隨蜂。為使聚類效果的緊湊度和分離度更加明顯,本文選用適應度函數,使得類內聚類效果更加緊湊,類間分離度更加明顯。假設Ci代表第i個聚類的數據集合,Ii表示第i類的聚類中心,也就是一個蜜源。適應度函數設計為:

(6)

其中,v∈Ci是Ci中的元素。

(7)

當所有的引領蜂搜索完成時,引領蜂會將蜜源信息和其對應的適應度給跟隨蜂,跟隨蜂根據式(8)中的概率計算每個引領蜂被跟隨的概率,概率表達式為:

(8)

其中,fi是蜜源xi對應的適應度值,適應度值的大小與蜜源被選擇的概率大小成正比,SN為訓練樣本的個數。

4)偵查蜂搜索。當某個食物源對應的計數器中的數值大于某個預先設置的閾值時,可以認為當前食物源已經耗盡,放棄該食物源,相應的引領蜂變為偵查蜂,采用式(8)在可行解空間內隨機產生新的食物源。

1.1.3 改進的蜂群聚類算法

改進的蜂群聚類算法的具體步驟為:

步驟1假設引領蜂和跟隨蜂的數量相同,且都為訓練樣本個數SN,設置最大迭代次數為MCN,設置控制參數limit和類別數k。

步驟2蜂群初始化,隨機產生{Z1,Z2,…,ZSN}個初始蜂群,并根據式(7)計算各個蜜蜂的適應度值。

步驟3對適應度值進行排序,將一半適應度范圍作為引領蜂,一半適應度范圍作為跟隨蜂。引領蜂利用式(5)進行鄰域搜索得到新蜜源,如果新蜜源的適應度大于舊蜜源的適應度,則把舊蜜源替換為新蜜源;否則,仍保持不變。當全部引領蜂完成鄰域搜索時,利用式(8)計算概率Pi。

步驟4根據步驟3得出的概率Pi和輪盤賭法則來判斷此處引領蜂的適應度,得出的概率越大則表明引領蜂i的適應度越大,且被跟隨蜂選擇的機率就越大。當跟隨蜂對引領蜂選擇完成時,按照式(5)對引領蜂進行鄰域搜索,并將搜索到的位置作為新蜜源位置。

步驟5將搜索到的蜜源位置初始化為聚類中心,對數據集進行一次K-means++迭代聚類,根據最近鄰原則進行聚類劃分,并找出各聚類中心更新蜂群。

步驟6在迭代limit次后,如果引領蜂的所在位置不變,則將引領蜂變為偵察蜂,并按式(5)產生一個新的蜜源。

步驟7若迭代次數達到MCN,則算法結束,并輸出最后的聚類中心;否則,轉向步驟3,且limit=limit+1。

步驟8基于以上改進的蜂群優化K-means++聚類結果可以找到相對應的值,但是該結果不一定是最優解,因此要使用評估聚類算法對結果進行評估,將簇內的稠密程度和簇間的離散程度即輪廓系數作為該聚類算法的評估標準,它是一種評價聚類效果的方式。本文選用Calinski-Harabasz Index輪廓系數[10]來計算每一個聚類中心聚類結果的輪廓系數。Calinski-Harabasz Index輪廓系數的計算方法如下所示:

(9)

其中,m表示訓練樣本集中聚類的數目,k表示當前聚類數目,Ak表示類與類之間的協方差矩陣,Bk表示每個類內部數據的協方差矩陣,tr表示Ak類和Bk類構成矩陣的跡。式(9)表明tr(Bk)的值越小越好,而tr(Ak)的值越大越好,這樣得出的結果S越好,且其對應的k值越精確,聚類結果更加精確。

1.1.4 改進的蜂群聚類集成算法

本文使用Bagging并行集成學習方法進行聚類集成。集成學習的主要思想是使用不同的方法改變原始訓練樣本的分布,從而構建多個不同的分類器,并將這些分類器線性組合得到一個更強大的分類器作為最后的決策。

使用改進的蜂群優化K-means++聚類算法生成K個基聚類成員,利用Bagging對K個基聚類成員進行集成,并使用投票法對基聚類成員進行聚類集成。聚類集成的基本思想是在數據范圍內進行有放回的再抽樣,假設樣本容量為n,原數據中每個數據被抽到的概率相等,且為1/n,即為bootstrap樣本。

改進的蜂群聚類集成算法的步驟為:

步驟1假設初始訓練數據集數量為n,每次從訓練數據集中使用bootstraping方法抽取b(b

步驟2將K個訓練樣本分別采用改進的蜂群聚類基學習器單獨進行訓練,將初始訓練數據集和聚類數建立為一個n×K的矩陣,該矩陣用于記錄對每個訓練樣本聚類類別的投票,其中,cij表示第i個基學習器的第j個聚類中心。

步驟3為判斷每個訓練樣本的最終聚類類別,本文根據步驟2建立的矩陣,按照投票法則進行判斷。訓練樣本的最終類別是由票數最多的類別決定的,如果某個類別的投票數相同,則隨機選擇一個類別作為該樣本的最終聚類類別。

根據改進的蜂群優化聚類集成算法對數據集進行聚類運算,能夠得到Kn,即用戶n的K個類簇,假設為Fn。改進的蜂群優化聚類集成如圖1所示。

圖1 改進的蜂群優化聚類集成Fig.1 Clustering ensemble optimized by improved bee colony

1.1.5 本文算法

改進的蜂群優化聚類集成聯合相似度推薦算法流程如圖2所示。

圖2 本文算法流程Fig.2 Procedure of the proposed algorithm

1.2 算法復雜度分析

改進的蜂群聚類集成算法假定原始數據集包含n個數據對象,一次聚類集成需要循環t次,每次聚類的數目為k,基聚類成員個數為K。K-means++算法每次迭代的時間復雜度為O(k×n×t),算法通過集成聚類集成K個改進的蜂群優化聚類算法,其總時間復雜度為O(K×n×t×k)。

1.3 用戶聯合相似度計算

傳統的個性化推薦算法在用戶歷史行為記錄較少的情況下,很難準確找到有效信息并將信息推薦給用戶,導致其推薦性能下降。針對上述問題,在同一類中,本文將用戶與用戶之間的相似度和用戶行為相似度進行線性聯合作為聯合相似度,在2種相似度中采用調節參數使得相似度達到最優。相似度表達形式為:

sim(x,y)=sim1(x,y)+sim2(x,y)

(10)

其中,sim(x,y)表示用戶x與用戶y的相似度,sim1(x,y)表示用戶x與用戶y的屬性相似度,sim2(x,y)表示用戶的行為相似度。

將肯德爾相關系數(Kendall)與皮爾遜算法相聯合作為本文的相似度算法,其中,肯德爾相關系數[11]主要用來測量在同一類別中2個用戶之間的相似度值,其表達形式為:

(11)

為了防止在同一類別中未被用戶評分的項目被忽略,本文采用皮爾遜相關系數[12]來描述同一類別中用戶評分間的相似程度。皮爾遜相關系數表達形式為:

(12)

1.4 基于鄰域的評分預測模型

在同一類別中為預測某用戶對某項目的評分,需要考慮與該用戶興趣相似的用戶對該項目的評分。本文采用基于鄰域[13]的評分預測方法進行評分預測,利用改進的蜂群優化K-means++聚類集成算法對用戶進行聚類得到k個類別,然后在同一個簇內計算用戶的加權聯合相似度,并將相似度值按照大小進行排序,取出相似度最高的前n項作為鄰域,再預測用戶對未知項目的評分,其表示方法為:

(13)

2 驗證分析

2.1 數據集及預處理

為驗證本文算法的有效性與可行性,選用Iris、Red Wine、Australia與MovieLens100K數據集進行聚類算法的測試,并采用K-means++聚類算法與改進的蜂群聚類集成算法對上述數據集進行處理。本文選用MovieLens網站提供的電影評分數據集對推薦算法的召回率和精度進行實驗[16]。實驗使用的數據是MovieLens100K數據集,其中包括943位用戶對1 682部電影的100 000個評分,該數據集對各個類別電影的評分值為1～5,考慮到實際仿真的效率,實驗將數據集劃分為訓練數據集和測試數據集,其中,80%的數據集作為訓練集,剩余的20%數據集作為測試集,這樣可以減少偶然因素帶來的不利影響,保證實驗的精確性。

2.2 評價指標

推薦算法的評價指標有多種,準確度、多樣性及新穎性等都可以用來評價推薦算法的推薦質量,本文采用準確度來度量推薦質量的好壞。評價推薦算法的準確度[17-18]比較常用的指標有平均絕對誤差(Mean Absolute Error,MAE)[19]、精度(Precision)與召回率(Recall),MAE是用來衡量推薦給用戶的準確性,能更好地反映預測值誤差的實際情況,且MAE越小,則推薦算法的準確度越高[20],MAE的計算方法為:

(14)

其中,xi表示為某用戶對項目的預測評分集合,設為{x1,x2,…,xm},yi表示用戶對所有項目的實際評分集合,設為{y1,y2,…,ym}。

精度是用戶對某一項目的推薦所占的比例,其計算方法為:

(15)

(16)

其中,Xi(L)表示推薦列表中實際用戶看過的項目數量,L表示該聚類的推薦列表長度。

召回率是對正確推薦項目的一種衡量,其計算方法為:

(17)

2.3 實驗結果與分析

實驗1為驗證本文提出的聚類算法優于K-means++聚類算法,在相同條件下,對本文聚類算法和K-means++聚類算法的收斂時間和聚類誤差均值進行比較。利用不同的數據集來驗證本文聚類算法的聚類效果更優。對于不同的數據集,設置不同規模大小的蜂群,具體如表1所示,且設置最大迭代次數為1 000,limit次數為100。本文聚類算法與K-means++聚類算法對數據集的聚類結果對比如表2所示。從表2可以看出,雖然K-means++聚類算法的收斂速度較快,但是聚類衡量數值的變化較大,因此不同實驗選擇不同的初始聚類中心,對實驗結果的影響較大。同時,K-means++聚類算法容易受初始聚類中心的影響,使算法陷入局部最優。本文采用改進的蜂群優化聚類集成算法,雖然增加了時間的復雜度和聚類屬性,但是降低了聚類誤差的幅度,解決了K-means++聚類算法的缺點,進而改善了聚類效果,使聚類效果更加穩定。同時,在時間復雜度允許的范圍內提高了聚類效果,使聚類效果更加精確,且可以在無監督的情況下進行精確劃分,更好地挖掘數據間的關系。

表1 聚類實驗的數據集信息Table 1 Dataset information of clustering experiment

表2 2種算法對數據集的聚類結果對比Table 2 Comparison of clustering results of two algorithms for dataset

實驗2在相同條件下,實驗通過比較本文聯合相似度算法和其他相似度算法的平均絕對誤差,來驗證本文聯合相似度算法優于單個相似度算法和其他聯合相似度算法。本文選用MovieLens100K數據集進行實驗,并根據實驗1得出的MovieLens100K數據集聚類結果進行相關的實驗驗證。圖3表示基于用戶的皮爾遜相似度和杰卡德相似度聯合的MAE。從圖3可以看出,采用皮爾遜和杰卡德相聯合的相似度,在MAE最低時與杰卡德的單獨相似度等效。因此單個相似度算法優于該聯合相似度算法,且需要改用其他聯合相似度算法使相似度結果達到最優。

圖3 杰卡德和皮爾遜聯合相似度的MAEFig.3 MAE of joint similarity of Jaccard and Pearson

經過大量的實驗驗證了肯德爾和皮爾遜聯合相似度算法優于其他相似度算法,結果如圖4所示,其中,P表示皮爾遜算法,K表示肯德爾算法,J表示杰卡德算法,0.5_P_K表示皮爾遜所占比例是0.5,0.7_P_K表示皮爾遜所占比例是0.7。從圖4可以看出,本文算法比各種相似度算法的MAE小,且當皮爾遜占0.4權重、閾值取0.75時,肯德爾和皮爾遜聯合相似度算法的MAE達到最低。結合圖3和圖4可知,本文提出的肯德爾和皮爾遜聯合相似度算法,比單獨的皮爾遜相似度算法、肯德爾相似度算法、杰卡德相似度算法以及杰卡德和皮爾遜進行聯合得到的相似度算法的MAE均低,因此本文提出的聯合相似度算法具有可行性。

圖4 不同相似度算法的MAEFig.4 MAE of different similarity algorithms

實驗3為驗證本文算法的有效性,在相同參數條件下,實驗比較了本文算法和其他算法的精度以及召回率。由實驗2的結果可以確定,聯合相似度算法優于單個相似度算法,且當皮爾遜占0.4權重、閾值取0.75時,肯德爾和皮爾遜聯合的相似度算法達到最優,因此將其作為本文聯合相似度算法進行實驗。本文算法對精度與召回率的影響分別如圖5、圖6所示。從圖5可以看出,當推薦個數大于6時,本文提出的聚類集成聯合相似度推薦算法的精度高于其他相似度算法,因此,可以根據推薦個數的不同選擇不同的推薦方法,從而提高精度。從圖6可以看出,當推薦個數大于6時,本文算法的召回率優于其他算法,因此,本文算法優于其他4種個性化推薦算法。

圖5 不同算法的精度Fig.5 Precision of different algorithms

圖6 不同算法的召回率Fig.6 Recall rate of different algorithms

綜上所述,改進的蜂群優化聚類集成聯合相似度推薦算法比其他相似度算法以及只有聚類集成算法的精度和召回率都要高,且MAE相對較小,因此,本文推薦算法不僅考慮到用戶的基本屬性特征,還考慮到項目的屬性特征,這樣一方面可以提高本文推薦算法的精度和召回率,另一方面又降低了本文算法的MAE,同時在一定程度上緩解了數據稀疏問題,使得本文推薦算法達到最佳效果。

3 結束語

傳統的協同過濾算法在數據稀疏的情況下,不能及時準確地為用戶推薦其所需項目,且傳統的K-means++聚類協同過濾算法也不能找到最優的k值,從而無法實現最佳推薦。為此,本文提出改進的蜂群優化聚類集成聯合相似度推薦算法。該算法不僅可以緩解推薦算法中的數據稀疏性問題,而且有效提高了推薦質量,還解決了K-means++聚類不佳等問題,改善初始聚類中心不穩定的缺點。下一步將對基于項目聚類的聯合相似度推薦算法進行改進,利用改進的蟻群算法對項目信息進行聚類,以提高推薦算法的準確性和可行性。