基于混沌粒子群聚類優化的協同過濾推薦

李建軍，付 佳+，楊 玉，汪校鈴，榮 欣

(1.哈爾濱商業大學 計算機與信息工程學院，黑龍江 哈爾濱 150028； 2.哈爾濱商業大學 黑龍江省電子商務與信息處理重點實驗室，黑龍江 哈爾濱 150028)

0 引 言

隨著移動電子商務的快速發展與移動終端設備的廣泛普及，用戶對于獲取互聯網信息的即時性和個性化需求逐漸提高，用戶希望在最短的時間內獲取自己最需要的信息。相對于PC端來說，移動終端的體積較小，屏幕就相對較小，用戶面對琳瑯滿目的商品或服務信息不知如何挑選，企業需要在有限的空間內向用戶展示用戶需要或感興趣的信息。這種情況就推動了移動推薦領域的發展，針對用戶的不同需求和興趣偏好，為每一位用戶推薦符合需求或興趣點的產品、信息以及服務。現階段針對推薦系統的研究越來越多，越來越復雜，但是無論何種研究方式，核心目標都是針對用戶的需求進行精準化推薦，實施個性化服務，方便用戶瀏覽有效信息。與此同時，企業實施精準推薦，能夠提高企業營銷效果，實現點對點精準營銷，增加用戶對企業產品或服務的粘性，留住高質量用戶的同時發展新用戶。而在移動推薦領域應用最為廣泛和久遠的算法就是協同過濾推薦算法(collaborative filtering，CF)。隨著應用的逐漸增多，協同過濾推薦也暴露出來許多問題，為了避免這些問題影響推薦的準確性，對協同過濾推薦算法進行改進是十分必要的。

本文通過翻閱文獻和查找相關資料，為了讓推薦的效果更好，在協同過濾推薦算法的基礎上做了相關改進，加入了混沌粒子群算法進行聚類優化，后續進行實驗的驗證，改進的算法推薦的效果更好。

1 相關工作

傳統的協同過濾推薦通過收集用戶對項目的評分數據，計算用戶之間的相似度，找到與目標用戶相似的用戶群，或者找到與目標用戶評分過的項目相似的項目群，通過對用戶給項目的評分進行推薦操作。協同過濾推薦的應用十分廣泛，但是隨著數據的擴增，協同過濾推薦也出現了許多問題。最普遍的就是數據比較少的問題和用戶的冷啟動問題。隨著網絡用戶和評分項目種類及數量逐漸增多，很難保證推薦的準確性，為了解決這個問題，本文將傳統粒子群算法進行改進，使用混沌粒子群聚類優化的方法對用戶進行聚類，然后在最優聚類的類簇中再進行協同過濾推薦，這樣不僅可以加快算法運算效率，還可以提高推薦的準確性。所以，本文的創新處在于使用改進之后的混沌粒子群算法對用戶先進行聚類，然后在與目標用戶最相似的聚類中進行協同過濾推薦，保證推薦的準確性。

自從協同過濾算法提出以來，在研究領域針對它的研究就層出不窮。Velammal B.L.[1]運用傳統的協同過濾算法進行書籍的推薦，為了解決協同過濾算法中的冷啟動問題，采用了人口統計過濾方法與協同過濾算法進行結合，能夠為用戶提供更精確的推薦結果。K.G.Saranya等[2]提出了一種基于粗糙集的協同過濾方法來預測用戶的缺失評分，并且用了一種新穎的檢測方法來提高項目排名。Behzad Soleimani Neysiani等[3]改進了基于關聯規則的協同過濾算法，用遺傳算法生成信用關聯規則，解決了協同過濾算法準確率低的問題。翁小蘭等[4]將協同過濾算法的研究進展進行總結，還將算法存在的問題和研究的趨勢進行分析。肖會敏等[5]針對移動電子商務即時性和移動性的特點對協同過濾算法進行了改進，將時間和位置因素加到協同過濾算法中，通過遺忘函數對協同過濾算法進行改進，使算法的精度進一步提高。面對協同過濾算法的數據稀疏性問題，也有很多研究用于改善此問題。蔡雄峰等[6]提出一種按照興趣度的加權填充策略，引用時間因素，將時間數據歸一化處理，重新調整用戶—項目評分矩陣。高倩等[7]考慮數據稀疏的情況，在相似度上面做了改進，除了用戶評分相似度之外，加入了用戶屬性相似度、用戶興趣相似度，將這3種相似度用不同的權重因子進行調節。

粒子群算法(particle swarm optimization，PSO)是基于生物行為而演變來的算法。解空間內存在一群粒子，每一個粒子都代表問題的潛在解，通過適應度函數求得每個解對應的適應度值，適應度值越好，粒子越靠近最優解。將粒子群算法融入到協同過濾算法的研究也有很多，Mohammed Wasid等[8]基于用戶混合特征的協同過濾推薦方法，應用粒子群算法對各種特征的用戶權重進行學習，并運用模糊集表示用戶特征。另外，Mohammed Wasid等[9]還利用粒子群算法開發基于上下文的協同過濾推薦技術，利用混合模糊特點的權重增強協同過濾技術的性能。碩良勛等[10]通過粒子群優化算法選擇最近鄰K值，即選擇與當前用戶相似度最高的前K個用戶作為鄰居進行推薦。吳彥文等[11]在得到最近鄰用戶群的基礎上，采用粒子群算法和分層遺傳算法進行資源推薦，能夠有效地提高資源推薦的質量。李浩君等[12]為了實現推薦個性化學習資源，將協同過濾算法結合二進制粒子算法，調整了慣性權重和種群多樣性，提出了基于多維特征差異的推薦算法。

隨著移動推薦領域的快速發展，對協同過濾算法和粒子群算法進行綜述研究，為了提高推薦的準確性，將傳統協同過濾推薦算法和粒子群算法融合應用，并做一定的算法改進。研究方法是首先將標準粒子群算法進行改進，加入混沌搜索過程，增加粒子多樣性，通過混沌粒子群算法對用戶群體進行聚類分析。此時可以基于一定聚類標準將用戶初步聚類，形成多個類簇和聚類中心。當對目標用戶進行推薦時，只需要計算目標用戶與哪個聚類中心距離近，屬于哪個聚類，將其劃分到所屬聚類中，然后在所屬聚類中進行協同過濾推薦，不僅可以提高推薦的準確性，而且有助于解決協同過濾算法的數據稀疏性和冷啟動問題。

2 混沌粒子群算法(CPSO)

在標準粒子群算法中，粒子通過如下的速度和位置更新公式更新自己的位置，每更新一個位置就需要計算一次適應度值，來更新個體最優和全局最優。標準粒子群算法的速度位置更新公式請參見文獻[13]。

由于標準粒子群算法在優化過程中容易出現過早收斂的現象，影響最優解的輸出，故將混沌搜索應用到粒子群算法中，豐富了粒子的多樣性，使粒子的全局搜索能力有所提高。將混沌搜索代替隨機搜索，最終使粒子群能夠達到最優狀態，本文應用一維混沌系統—Logistic映射，Logistic映射的其中一種形式為

xk+1=μxk(1-xk)

(1)

其中，μ∈[0,4]為分枝參數，當μ=4時為完全混沌狀態。在粒子群算法中，通過上式產生混沌變量，形成混沌序列，并且代替原粒子進行混沌搜索，直到滿足條件為止。

另外，粒子群算法中的慣性權重表示著上一代粒子的速度對當前粒子速度的影響水平，它的大小也直接影響算法的運算結果，w較大，有利于算法早期的全局搜索，但是在算法晚期，需要對w值進行調整，以此提高算法的局部搜索能力，有助于全局最優值的收斂。將w值進行動態調整，有利于最優值的輸出。所以本文應用動態調整慣性權重的方法來改進標準粒子群算法。應用線性遞減權重策略來調整慣性權重，即將慣性權重從前期較大的值逐漸遞減到后期較小的值，一般的調整權重公式為

(2)

其中，K表示最大迭代次數；k表示當前的迭代次數；wmax為初始最大慣性權重，通常取0.9；wmin表示運算結束時(達到最大迭代次數K)的最小慣性權重，通常取0.4。

2.1 算法構建

聚類是根據數據集中的相似性將其劃分為若干類簇的過程，是一種無監督的分類方式。通過聚類進行分類，能夠做到同一個類簇里面數據的相似性高，不同類簇之間的數據相似度盡可能低。然而，在大數據環境下，用戶和項目的數據量日益龐大，數據樣本的數量也逐漸增多的情況，組合類簇的數量也會變得十分巨大，無法做到通過普通聚類操作列舉出所有組合類簇，也很難找到最好的分類。在本文中利用混沌粒子群優化算法的全局搜索能力對樣本數據進行迭代更新，可以避免出現上述現象，經過混沌粒子群進行全局搜索之后，最終得到的最優解就是最優的分類。

在本文的算法中，粒子群中的每個粒子代表一種可能的分類，粒子的維數代表樣本的個數，如下構造粒子

Xi=(p1,p2…pm),0

(3)

其中，n為樣本個數，pi為第i個樣本所屬的類。一個群體表示著一個數據集中的若干分類，粒子會對應自己的適應度值，可以用下面的函數來確定每個粒子的適應度值，適應值的好壞也影響著分類的結果。

使用誤差平方和函數來計算適應度值

(4)

(5)

其中，Xij是從屬第i類的第j個樣本；ni是第i類中的所有樣本個數；mi是第i類的聚類中心。Jc越小，聚類的成效越好。

2.2 算法流程

基于混沌粒子群算法(chaotic particle swarm optimization)進行聚類優化的大致算法流程如圖1所示。

圖1 改進的粒子群聚類算法流程

步驟1初始化粒子群，隨機粒子的初始速度、位置以及聚類中心。按照普遍習慣設置最大迭代次數為K=1000，粒子的學習能力因子c1=c2=1.8，w的初始值設為0.9；

步驟2計算粒子的適應度值，由初始位置將其余粒子進行聚類；

步驟3通過粒子速度位置更新公式[13]更新粒子的速度和位置，產生下一代粒子；

步驟4按照式(2)更新慣性權重；

步驟5根據粒子的新位置(新聚類中心)對其進行聚類；

步驟6計算適應度值，產生當前的個體最優位置和全局最優位置，記錄全局最優位置的聚類信息；

步驟7對粒子進行混沌擾動，得到新的全局最優，并比較最優值的聚類信息；

步驟8判斷粒子是否符合結束條件，若符合，則輸出最優的分類結果和聚類的中心；若不符合，則返回步驟3繼續運算。結束條件為：找到符合條件的最優解或達到最大迭代次數。

3 基于混沌粒子群聚類的協同過濾推薦模型

基于混沌粒子群聚類的協同過濾推薦模型與傳統的協同過濾推薦模型不同的是，通過混沌粒子群算法優化之后，輸出的是最優的分類組和每一個聚類中心。當對用戶進行推薦時，只需要計算目標用戶與聚類中心的相似度，找到相似度高的聚類，將目標用戶劃分到此聚類中，然后建立該聚類的用戶—項目評分矩陣，通過混沌粒子群優化確定最近鄰參數，選擇前K個相似度最高的用戶，然后通過這些用戶對目標用戶的未評分項目的評分進行預測，產生推薦項。

3.1 計算相似度

計算相似度的方法有很多，現階段應用最多的就是歐式距離、余弦距離、皮爾遜相關系數。使用上述方法可以計算目標用戶和聚類中心的距離，將目標用戶分到距離最近的聚類中，再進行下一階段的工作。

(1)歐式距離

(6)

(2)余弦距離

(7)

(3)皮爾遜相關系數

(8)

針對實際實驗需求，本文選取皮爾遜相關系數計算用戶之間的相似度，相較于其它兩種相似度計算方法，它能夠更好地衡量用戶和聚類中心之間的距離，進而確定目標用戶所屬聚類。

3.2 用戶—評分矩陣

協同過濾推薦中存在大量的用戶—項目評分數據，在找到與目標用戶相似度最高的聚類A之后，在A中生成用戶—項目評分矩陣，矩陣的結構包括項目編號(Itemi)、用戶編號(Userj)和用戶—項目評分(Sij)。生成矩陣可以更加直觀看出用戶—項目評分的數據特點。表1為聚類A的用戶—項目評分矩陣。

表1 用戶—項目評分矩陣

3.3 確定最近鄰

此矩陣中的用戶與目標用戶都屬于同一個聚類，所以彼此之間的相似性都較高，但是在實際應用中為了避免過度推薦，引起用戶厭倦心理，需要限制推薦數目。所以現在只需要選取矩陣中與目標用戶最相似的前K個用戶作為最近鄰(K最近鄰算法)，以此確定目標用戶感興趣的項目，但是從以往研究中可以看出K的取值還是比較盲目的，沒有合理的K值可能會導致過度推薦。故應用混沌粒子群優化算法選取合理的K值，能夠有效地提高算法性能，合理有效地進行推薦。

用混沌粒子群優化算法選擇最近鄰K。隨機產生q個粒子，每一個粒子為最近鄰的參數值，粒子的適應度值用K值產生的推薦列表計算的推薦精度來代表。粒子運用上述位置速度更新公式進行一次一次的位置和速度迭代，更新個體最優位置和全局最優位置，并對粒子進行混沌擾動，直到滿足迭代次數或找到最優值，輸出最近鄰參數K值。取與目標用戶相似度最高的前K個用戶組成目標用戶的最近鄰，K(u)={u1,u2,Luk},u∈K(u)。并且最近鄰集合中的用戶uk是根據與目標用戶u的評分相似度sim(u,uk)由大到小排序的[14]

(9)

3.4 預測評分模型

選擇了與目標用戶最相似的前K個用戶之后，根據評分預測公式預測評分，然后向目標用戶推薦評分高的前K個項目

(10)

其中，p(u,n)是鄰居用戶集合中的用戶評分過的項目，但目標用戶沒有評分過的項目的評分預測值。

4 實驗驗證

4.1 實驗數據及評價標準

在驗證本文算法的過程中，本實驗采用MovieLens數據集，數據集中包含用戶、電影以及用戶對電影的評分(1～5分)，可以進行電影的推薦。本次實驗選擇100 000個電影評分數據，進行混沌粒子群的聚類和推薦。其中，每個用戶至少對30部電影做出了評分。算法運行環境為matlab7.1，Windows 8系統。

實驗采用的推薦效果評估標準是平均絕對誤差(MAE)和推薦準確率(Precision)。MAE的值越小，推薦的越準確。準確率則是衡量推薦正確程度的指標

(11)

其中，預測的用戶評分集合為{G1,G2…GN}，實際的用戶評分集合為{H1,H2…HN}

(12)

其中，W(i)為推薦目標用戶的項目集合，T(i)為目標用戶喜歡的項目集合。

4.2 實驗結果

為了更好地突出改進算法的優勢，首先將本文算法(CPSO)與協同過濾(CF)、粒子群算法(PSO)、人工蜂群算法(artificial bee colony，ABC)進行比較，在其它實驗指數都相同的情況下，觀察平均絕對誤差MAE指標的變化，本次實驗以推薦數目為評價自變量，并進行多次實驗進行驗證，如圖2所示，隨著推薦數目的增加，CPSO、PSO、CF算法的MAE值都大體呈現先下降后回升的趨勢，ABC算法呈一直下降的趨勢。在聚類數目為20左右時，各個算法的MAE值都處在底端，并且CPSO算法的MAE值最低，故CPSO的平均絕對誤差最低，推薦的誤差相比最低。可以初步印證CPSO算法的性能相對于其它未改進的算法較好。

圖2 不同推薦數目下不同算法的MAE比較

其次，為了體現本文算法改進的有效性，實驗將從兩個角度比較算法性能。將聚類數目和最近鄰數目分別作為觀察評價標準變化的自變量，為了避免實驗的偶然性，以下實驗均多次進行，并選取出現次數最多的合理結果。

(1)以聚類數目為基準

由于本文的混沌粒子群算法應用于推薦的兩個階段，所以在聚類這一階段，首先按照以往實驗習慣先將最近鄰數目確定為K=20，通過不同的聚類數目來衡量評價標準的優劣，為了更好地分析算法性能，將混沌粒子群聚類優化算法與傳統K-means聚類、標準粒子群和人工蜂群算法比較，觀察MAE與Precision的變化，如圖3、圖4所示。

圖3 不同聚類數目下MAE的變化

圖4 不同聚類數目下Precision的變化

由上述實驗說明，各個算法隨著聚類數目的不斷增加，MAE值呈現先下降后小幅度回升的趨勢，Precision值則是先上升后回落的趨勢，這也符合大多數實驗的規律，即聚類數目的選取應在某個合理范圍內，不宜過大或過小。當最近鄰數目設定為20時，只觀察算法確定的聚類數目對推薦性能的影響，發現本文的混沌粒子群聚類優化算法相較于傳統的K-means聚類算法、標準粒子群算法以及人工蜂群算法有更小的MAE值，更高的推薦準確率，并且，在聚類數為60左右時，評價效果最好，所以在接下來的實驗中，將聚類數目設定為60。

(2)以最近鄰數目為基準

在實驗的第二階段，將聚類數目確定為60，使用混沌粒子群算法選取最近鄰。觀察最近鄰的取值對算法指標的影響，為了與CPSO進行比較分析，選擇傳統的協同過濾算法(CF)和粒子群算法(PSO)進行對比，觀察MAE和Precision的變化情況，如圖5、圖6所示。

圖5 不同最近鄰的數目下MAE的變化

圖6 不同最近鄰的數目下Precision的變化

由于確定了聚類數目，在第二階段的實驗中，可以看出，隨著所選取最近鄰數目的不斷增加，在K=25左右時，各個算法的MAE和Precision值出現極值。其中，CPSO算法的MAE值最低，Precision值最高，這與前一個實驗的數值差異并不大，為了實驗的準確性可以將最近鄰數目確定為20-25之間。在與其它算法的對比中可以看出其它算法在MAE值和準確率上都不如本文算法，且兩次實驗的最近鄰數目相差較大，不利于參數的確定。

5 結束語

為了解決當前協同過濾推薦算法準確率低以及推薦過度的問題，在進行推薦操作之前，采用混沌粒子群算法對用戶群體進行聚類分析，輸出最優的聚類結果和聚類中心，然后根據目標用戶與聚類中心的距離大小，將目標用戶劃分到離他最近的聚類中，在此聚類中進行協同過濾推薦，這樣就可以保證作為推薦參考的用戶與目標用戶的相似度都很高。在進行協同過濾推薦時，涉及到最近鄰參數選擇，為了防止過度推薦，降低目標用戶的興趣度，選擇相似度最高的前K個用戶對目標用戶進行推薦，這樣做不僅使推薦的精度提高，而且有限的推薦有助于目標用戶進行精確選擇，防止過度推薦，用戶產生厭煩心理。故再次應用混沌粒子群算法選擇最近鄰參數。最后，采用MovieLens數據集進行實驗，采用平均絕對誤差和準確率兩個指標對算法進行比較和驗證，實驗也許存在一些的局限性，但是在特定的情況下，還是能夠說明CPSO算法的平均絕對誤差和準確率上都優于其它未改進算法。