一種優(yōu)化聚類的協(xié)同過濾推薦算法

王永貴，劉凱奇

遼寧工程技術(shù)大學 軟件學院，遼寧 葫蘆島 125105

1 引言

隨著大數(shù)據(jù)時代快速發(fā)展，互聯(lián)網(wǎng)產(chǎn)生的海量信息與日俱增，網(wǎng)絡(luò)覆蓋率日益增高。信息檢索已經(jīng)不能滿足用戶日益增長獲取個性化信息的需求，由此個性化推薦系統(tǒng)應(yīng)運而生[1]。成功應(yīng)用于電子商務(wù)、在線音樂、視頻網(wǎng)站、購物商城、社交網(wǎng)絡(luò)等各個領(lǐng)域。它已經(jīng)逐步成為各種網(wǎng)絡(luò)平臺中必不可少的核心功能，力求為用戶提供最優(yōu)的決策支撐與信息服務(wù)。個性化推薦不需要用戶提供明確的需求，而是根據(jù)用戶的興趣偏好和歷史行為，向用戶推薦感興趣的信息和商品。

目前，個性化的推薦技術(shù)又分為基于內(nèi)容的推薦[2]、協(xié)同過濾推薦[3]和混合推薦技術(shù)[4]。基于內(nèi)容的推薦算法不需要依據(jù)用戶對項目評分，而是通過抽取項目的屬性進行特征學習，獲得用戶的興趣資料。基于協(xié)同過濾推薦算法是根據(jù)與其興趣相似，擁有共同經(jīng)驗之群體的喜好來推薦給目標用戶感興趣的信息。它不需要太多的特定領(lǐng)域知識，可通過基于統(tǒng)計的機器學習算法得到較好推薦效果。而混合推薦算法是將不同的推薦方法進行組合，綜合利用基于內(nèi)容推薦算法和基于協(xié)同過濾推薦算法的優(yōu)點進行推薦。但往往會出現(xiàn)推薦時間增長、平衡不易實現(xiàn)、算法復雜度提高等問題。

協(xié)同過濾推薦算法是目前發(fā)展最成熟、應(yīng)用最廣泛的個性化推薦技術(shù)之一[5]。它最大的優(yōu)點在于不需要提取內(nèi)容的信息和項目的特征來構(gòu)建用戶興趣偏好模型，因此適用于音樂、電影、圖片等非文本結(jié)構(gòu)項目。而且具有出色的健壯性和魯棒性，在各大推薦系統(tǒng)中廣泛應(yīng)用。協(xié)同過濾推薦算法包括基于記憶的推薦算法、基于模型的推薦算法。基于記憶的協(xié)同過濾推薦算法可以分為基于用戶[6]和基于物品[7]的協(xié)同過濾推薦算法。它依靠用戶項目評分矩陣計算用戶或項目之間的相似度進行推薦。但在現(xiàn)實應(yīng)用中，伴隨著用戶和項目數(shù)量的大幅度增加，卻只有一小部分用戶對少部分項目評分或評論，因此協(xié)同過濾技術(shù)存在明顯的數(shù)據(jù)稀疏性、冷啟動[8]以及擴展性的問題[9]。基于上述問題，許多研究人員從不同方面將基于模型的算法引入到基于記憶的協(xié)同過濾算法中，例如聚類模型、貝葉斯分類模型[10]、隱語義模型[11]、圖模型[12]、關(guān)聯(lián)規(guī)則挖掘[13]等技術(shù)。基于模型的推薦算法利用歷史行為數(shù)據(jù)訓練得到模型，并利用該模型進行實時推薦。

其中Wu等人[14]證明基于聚類的協(xié)同過濾推薦算法在解決數(shù)據(jù)稀疏問題上推薦效果更好。駱孜等人[15]在原有非負矩陣分解的模型上，根據(jù)用戶的評分數(shù)據(jù)對用戶進行聚類，充分挖掘了用戶之間的相關(guān)關(guān)系，有效緩解數(shù)據(jù)的稀疏性。龔敏等人[16]提出利用最小生成樹K-means聚類算法對用戶進行聚類，然后再利用Slope One算法填充原始評分矩陣，降低數(shù)據(jù)的稀疏性并提高算法的擴展性。楊興雨等人[17]利用二分K均值聚類算法降低原始用戶項目評分矩陣的維數(shù)，在線推薦時根據(jù)隨機森林的模型規(guī)則進行評分預測，提高推薦的效率。吳月萍等人[18]在協(xié)同過濾推薦算法中運用群集智能算法，利用改進的人工魚群算法實現(xiàn)用戶聚類，為后來研究人員提供了新方向。Wang等人[19]提出PCA主成分分析和遺傳優(yōu)化K-means聚類混合推薦算法，提高推薦的準確性。郭磊等人[20]通過人工蜂群算法對項目聚類，大大縮小項目的空間，提高推薦的實時性。然而，以上使用的聚類算法都是硬聚類，將每個用戶或項目劃分到一個簇中，與實際情況不符。Verma等人[21]提出一種模糊C-means聚類和協(xié)同過濾推薦算法的混合推薦系統(tǒng)。FCM是一種軟聚類算法，能根據(jù)隸屬度的不同，將用戶劃分到多個簇中。李華等人[22]提出一種基于用戶情景模糊聚類的協(xié)同過濾推薦算法，改善數(shù)據(jù)的稀疏性和實時性問題。林建輝等人[23]提出一種基于SVD與模糊聚類的協(xié)同過濾推薦算法，通過縮小搜索的鄰居范圍和改進Pearson相關(guān)系數(shù)來提高推薦質(zhì)量。Birtolo等人[24]提出模糊C均值和信任感知的聚類協(xié)同過濾方法，提高推薦的質(zhì)量和覆蓋范圍。Katarya等人[25]將基于粒子群優(yōu)化的模糊C均值聚類算法應(yīng)用于基于用戶的協(xié)同過濾推薦算法中，粒子群優(yōu)化算法提供最優(yōu)初始聚類中心并優(yōu)化模糊C均值聚類，提高推薦的準確率。

然而，上述大多數(shù)研究是根據(jù)用戶對項目的評分進行聚類，沒有考慮用戶或項目之間的隱含信息，且用戶或項目在聚類時容易導致目標數(shù)據(jù)陷入局部最優(yōu)，造成最近鄰選取不正確，降低推薦的準確性。因此，本文提出一種優(yōu)化聚類的協(xié)同過濾推薦算法。首先預處理原始項目評分矩陣，同項目類型矩陣構(gòu)造的用戶類別偏好矩陣更好反映用戶的興趣偏好；然后在該矩陣上利用花朵授粉優(yōu)化的模糊聚類算法對用戶進行聚類；最后改進基于用戶的相似度計算公式和評分預測公式，既融合項目屬性隱含的信息，又考慮時間因素對用戶興趣變化的影響，提高推薦的準確性。

2 相關(guān)知識

2.1 基于用戶的協(xié)同過濾推薦算法

在日常生活中，人們在購買商品或獲取所需信息時，通常會借鑒與自己喜好相似或志趣相投的朋友所選擇的商品或獲取相關(guān)信息。基于用戶的協(xié)同過濾推薦算法就是利用這種群體智慧，它的基本思想就是根據(jù)目標用戶歷史行為信息，挖掘與目標用戶興趣相似度高的近鄰用戶集合，然后根據(jù)鄰居用戶對此項目的評分來預測目標用戶的相應(yīng)評分，從這些預估評分中選擇分數(shù)靠前的Top-N個推薦給目標用戶。

假設(shè)用戶A喜歡項目a、項目b和項目d，用戶B喜歡項目c，用戶C喜歡項目a和項目d，從這些用戶歷史偏好數(shù)據(jù)中，可以發(fā)現(xiàn)用戶A和用戶C都喜歡項目a和項目d，他們的偏好比較相似，因此也可以認為用戶C也會喜歡項目b，所以將項目b推薦給用戶C。圖1表示此算法的原理。

圖1 基于用戶協(xié)同過濾推薦算法原理

基于用戶的協(xié)同過濾推薦算法主要步驟：首先把用戶評分數(shù)據(jù)轉(zhuǎn)化成m行n列用戶項目評分矩陣Rm,n，如表1所示；然后根據(jù)評分矩陣計算目標用戶和其他用戶之間的相似度，根據(jù)相似度的大小獲得目標用戶最近鄰用戶集合Nu；最后通過鄰居用戶對項目的評分預測目標用戶的評分。

表1 用戶項目評分矩陣Rm,n

為了基于用戶項目評分矩陣計算出用戶之間的相似性，相似度計算方法主要分為余弦相似度、改進的余弦相似度、皮爾遜相關(guān)系數(shù)等。皮爾遜相關(guān)系數(shù)用于度量兩個變量之間的線性相關(guān)性，與改進的余弦相似度計算公式都是去中心化和進行歸一化的結(jié)果，差別在于去中心化的不同。Herlocker等人[26]的實驗表明，在基于用戶的協(xié)同過濾推薦算法中，選擇皮爾遜相似度最為適合，計算公式表示如下：

其中，Iu,v表示用戶u與用戶v共同評分項目構(gòu)成的集合；Rui表示用戶對項目i的評分；Rvi表示用戶v對項目i的評分。 分別表示用戶u和用戶v對所有評分過的項目評分平均值。

2.2 模糊C均值聚類算法

設(shè)數(shù)據(jù)集x={x1,x2,…,xn}?Rn為一個有限數(shù)據(jù)集合，其中xi={xi1,xi2,…,xin}，n為數(shù)據(jù)樣本個數(shù)，c(2 ≤c≤n)是聚類數(shù)，聚類中心為C={c1,c2,…,cn} ，隸屬度矩陣為U=(uij)c×n，uij∈[0,1] ，i=0,1,2,…,n；j=1,2,…,c。FCM算法采用誤差平方和函數(shù)作為目標函數(shù)，定義式如公式（2）所示：

聚類是對數(shù)據(jù)處理的一種方式，它能夠?qū)o規(guī)則的數(shù)據(jù)根據(jù)相似度高低分成若干個數(shù)據(jù)組，同一組內(nèi)的數(shù)據(jù)特征相似度最高。聚類技術(shù)分為硬聚類技術(shù)和軟聚類技術(shù)。對于一個不能明確目標數(shù)據(jù)對象關(guān)系的數(shù)據(jù)集，使用硬聚類劃分就不能符合實際問題的需求。模糊C均值聚類算法（Fuzzy C-means Clustering Algorithm）是在硬C均值聚類算法模型基礎(chǔ)上進一步推理得到。硬聚類要求每個用戶只能明確歸屬于一個聚類之中，而模糊聚類是一種軟聚類，其中的模糊C均值聚類算法應(yīng)用最廣泛且較為成功。它可以將每一個目標數(shù)據(jù)對象以不同的隸屬度聚到多個類中。FCM聚類算法在每次迭代時，會計算得到一個隸屬度矩陣和一個聚類中心的集合。根據(jù)算出的隸屬度矩陣和聚類中心集合求出目標函數(shù)的值。算法最終目的是盡可能找到較小的目標函數(shù)值。

其中，m是模糊聚類中的模糊指數(shù)，它的作用是平滑隸屬函數(shù)、抑制噪音等。取值范圍是[1.25，2.5]。使得公式（2）取得最優(yōu)解過程是：首先計算各個用戶和聚類中心之間的距離，然后生成用戶對各個聚類中心的隸屬度矩陣，比較用戶在各個聚類中心隸屬度的大小，將用戶分配到隸屬度最大的用戶簇中，使得同一個用戶簇中用戶的相似度最高，減少不同用戶簇中用戶之間的相似度。將公式（2）求導，可以得到隸屬度和聚類中心分別為：

FCM聚類算法基本步驟如下：

輸入：數(shù)據(jù)集和聚類數(shù)目c。

輸出：使得Jm(u,c)最小的聚類中心集合Cj。

過程：

步驟1確定目標簇的個數(shù)為c，模糊指數(shù)m。

步驟2隨機生成初始聚類中心。

步驟3用公式（3）計算得出隸屬度矩陣。

步驟4用公式（4）計算得出各類的聚類中心。

步驟5如果迭代時前后兩次的目標函數(shù)值之差比最初設(shè)置的最小值小則終止迭代，否則返回步驟3。

步驟6輸出結(jié)果。

2.3 花朵授粉算法

開花植物進化通過花粉傳播來繁衍后代。授粉過程主要有生物和非生物兩種形式。大部分植物是生物授粉，依靠動物來完成。也有少部分植物是非生物授粉，受到自然界的影響，如風和自然擴散等。花朵授粉算法（Flower Pollination Algorithm）就是模擬大自然中顯花植物授粉的群智能優(yōu)化算法。顯花植物的授粉包括自花授粉和異花授粉兩種。自花授粉也稱為局部授粉，不需要授粉者，在同一種植物之間傳播；異花授粉也稱為全局授粉，主要是昆蟲或鳥類攜帶花粉并通過萊維飛行進行傳播。算法中的局部搜索過程和全局搜索過程由轉(zhuǎn)換概率P決定。在現(xiàn)實中，每朵花可能產(chǎn)生數(shù)百萬甚至是更多花粉，為了簡化問題，花朵授粉算法假設(shè)每顆顯花植物僅開一朵花，每朵花只產(chǎn)生一個花粉配子，就是說一朵花為求解優(yōu)化問題的一個解。

FPA算法的主要思想：

（1）首先進行初始化種群。

（2）然后對種群個體進行適應(yīng)值評價，找出適應(yīng)值最優(yōu)的個體作為當前全局的最優(yōu)解。

（3）最后通過轉(zhuǎn)換概率p∈[0,1]，完成全局搜索與局部搜索之間的轉(zhuǎn)換，不斷地迭代直到滿足收斂條件為止。

下面由數(shù)學公式描述花朵授粉的算法：

當p>rand時，算法執(zhí)行全局授粉，公式如下所示：

其中，分別為花粉在第t+1次、第t次迭代的位置，g*為當前全局最優(yōu)解，γ為控制移動步長的比例因子。L(λ)為對應(yīng)花朵個體的萊維飛行步長矢量，當L>0時，其表達式如下：

其中，，Γ(λ)為標準伽馬函數(shù)，S為移動步長，采用曼特尼亞算法產(chǎn)生最有效的步長，公式如下所示：

其中，U服從均值為零，標準差是σ2的高斯分布，V服從標準正態(tài)分布。σ2由以下公式得出：

當p

其中，ε∈[0,1]，是服從均勻分布的常數(shù)，是種群的兩個隨機解，代表同一品種植物不同花朵的花粉。

3 本文算法

利用原始用戶項目評分矩陣和項目類型矩陣構(gòu)造用戶類別偏好矩陣，其中考慮用戶的評分差異，對用戶項目評分矩陣進行預處理。在得到用戶類別偏好矩陣基礎(chǔ)上，通過FPAFCM算法對用戶進行聚類，該算法是利用花朵授粉FPA算法去優(yōu)化模糊聚類FCM算法。改進基于用戶的相似度計算公式，將項目偏好隱性信息相似度加入到項目評分矩陣相似度計算公式中，得到K個最近鄰居。評分預測時考慮時間因素對用戶興趣變化的影響，將預測評分值最高的N個項目推薦給目標用戶。本文算法框圖如圖2所示。

圖2 本文算法流程圖

3.1 構(gòu)造用戶類別偏好矩陣

傳統(tǒng)的協(xié)同過濾推薦算法依賴于用戶項目評分矩陣，但是現(xiàn)實中用戶評分項目很少，不同用戶在同一項目上共同評分則更少。所以基于用戶項目評分矩陣會受到數(shù)據(jù)稀疏性帶來的嚴重影響。而且它通常只考慮到共同評分項目對相似性的影響，共同評分項目所占比例越高，與目標用戶就會越相似。事實上，盡管用戶評價的不是同一個項目，如果這些項目風格類型相似，同樣可以說明用戶之間有相似的興趣愛好。比如用戶u1喜歡觀看電影“疾速備戰(zhàn)”和“驚奇隊長”，并給出了很高的評價，而用戶u2喜歡觀看“蜘蛛俠”和“巴爾干邊界”，同樣也給出了很高的評分。因為這四部電影屬于動作片，可以認為用戶u1和用戶u2具有相似的興趣偏好。然而傳統(tǒng)的協(xié)同過濾推薦算法會因為他們沒有共同評分而忽略它們之間的相似度，用戶u1和用戶u2就不能成為最近鄰居。構(gòu)建用戶類別偏好矩陣對用戶進行聚類，一是因為喜歡的類別相同也具有相似性，二是項目的類型數(shù)量遠小于項目數(shù)量且比較穩(wěn)定，構(gòu)造出更加稠密的用戶類別偏好矩陣達到降維效果，緩解數(shù)據(jù)的稀疏性。

用戶類別偏好矩陣Pm,y可以通過原始用戶項目矩陣Rm,n和項目類型矩陣Cn,y構(gòu)造。設(shè)評分系統(tǒng)中項目的集合為I={i1,i2,…,in}，項目類別集合為T={t1,t2,…,ty} 。項目與類別之間的關(guān)系用一個n×y的矩陣表示，這個矩陣稱作項目類型矩陣Cn,y，如表2所示。矩陣中每個元素cit表示電影i是否屬于類別t，可以表示為：

表2 項目類型矩陣Cn,y

用戶與項目類別之間關(guān)系用m×y的矩陣表示，記作矩陣Pm,y，如表3所示。矩陣中元素put表示用戶u對項目類別t的偏愛程度。

表3 用戶類別偏好矩陣Pm,y

由于用戶對項目的評分尺度沒有明確標準，是由用戶主觀給出項目的評分，所以不同用戶的評分尺度存在一定的差異，導致計算出的興趣最相似近鄰集合出現(xiàn)很大偏差。為了克服用戶評分差異對推薦結(jié)果造成的影響，根據(jù)指定評分平均值對用戶項目評分矩陣中的非零評分值進行預處理，得到用戶項目評分矩陣R′m×n，用戶評分處理后的公式如下所示：

其中，r′ui是預處理后的評分值，rui表示原始用戶對項目i的評分值表示用戶u的平均評分值。因為評分為5分制，所以rˉ定為3。

在得到的用戶項目評分矩陣R′m×n上計算用戶類別偏好矩陣元素的值。用戶u所有評分項目集合用Iu表示，將預處理后評分值小于均值的項目過濾后，得到的項目集合表示為：

其中，cit=1表示項目屬于類別t。

為了區(qū)分用戶對項目類別的偏好程度，并且避免直接使用評分數(shù)據(jù)對計算造成偏差。將規(guī)范化后的評分劃成不同區(qū)間，并設(shè)置相應(yīng)的權(quán)值。α(r′ui) 計算公式為：

其中，|Lut|表示集合Lut中元素個數(shù)；對Put進行歸一化處理，將分母乘以α(r′ui)的最大值作為歸一化因子，取值為3。

3.2 花朵授粉算法優(yōu)化的用戶模糊聚類推薦算法

FCM聚類算法在對給定的目標數(shù)據(jù)進行聚類時，初始化參數(shù)的選取會對最后聚類結(jié)果產(chǎn)生很大影響，且容易導致目標對象的數(shù)據(jù)陷入局部最優(yōu)值。花朵授粉算法剛好能解決以上出現(xiàn)的問題，因此將兩種算法融合到一起，對用戶進行聚類。

FPAFCM算法思想：先利用花朵授粉算法找到最優(yōu)的初始聚類中心，再通過最優(yōu)的初始聚類中心對用戶進行模糊C均值聚類。花朵授粉算法的每一朵花表示一個聚類中心矩陣C={c1,c2,…,cc}，并且將適應(yīng)度函數(shù)設(shè)置如下所示：

FPAFCM算法基本步驟如下：

輸入：用戶類別偏好矩陣，花粉種群規(guī)模S，最終目標簇的個數(shù)c，隸屬度矩陣指數(shù)m，最大迭代次數(shù)MCN。

輸出：用戶簇隸屬度矩陣U。

步驟1隨機產(chǎn)生初始花粉種群S。

步驟2根據(jù)隸屬度矩陣的計算公式（3）得到一個當前循環(huán)的隸屬度矩陣。

步驟3根據(jù)公式（2）對每個花粉的適應(yīng)度值進行計算，找到最小的值及其對應(yīng)的個體作為全局最優(yōu)解。

步驟4當轉(zhuǎn)換概率p>rand條件時，按照公式（5）～（8）進行全局授粉過程更新花粉位置，對解進行越界處理。

步驟5當轉(zhuǎn)換概率p

步驟6根據(jù)步驟4或者步驟5得到更新之后的解，計算得到的相應(yīng)隸屬度矩陣，最后計算對應(yīng)的目標函數(shù)值。當目標函數(shù)值小于歷史目標函數(shù)值，用更新后的值代替?zhèn)€體當前最優(yōu)值。如果不是，則保留當前結(jié)果。

步驟7將更新后的值和歷史全局最優(yōu)解進行比較，更新或保留歷史全局最優(yōu)解。

步驟8判斷是否滿足算法終止條件。如果不滿足則轉(zhuǎn)向步驟4繼續(xù)迭代，滿足則輸出結(jié)果。

步驟9對步驟8輸出的最優(yōu)隸屬度矩陣去模糊化處理，進而完成聚類。

3.3 生成目標用戶的最近鄰居

根據(jù)用戶聚類的結(jié)果，找出目標用戶候選鄰居簇，然后根據(jù)目標用戶與簇中候選鄰居之間的相似度計算，按照降序排列，將前K個作為目標用戶的最近鄰居。計算相似度時將用戶對項目屬性類型偏好信息反映的相似度同用戶對項目評分反映的相似度進行加權(quán)求和。既包含原始用戶項目評分矩陣的顯性信息，又考慮到用戶和項目類別之間的隱性信息，增加最近鄰居搜索的準確度。改進后相似度計算公式如下所示：

其中，λ為比例因子，取值范圍是[0，1]，λ表示原始評分矩陣計算出的用戶相似度在相似度公式中所占比例，(1-λ)表示用戶類別偏好矩陣計算出的用戶相似度在相似度公式中所占的比例。simr(u,v)是根據(jù)用戶評分矩陣計算出的相似度，如公式（1）所示。simt(u,v)是根據(jù)用戶類別偏好矩陣計算出的相似度，如下面公式（18）所示：

其中，Eu,v代表用戶u和用戶v共同評價過的項目類別集合，Put、Pvt分別表示用戶u和以及用戶v對類型為t的項目偏好值，分別代表用戶u和用戶v對評價過的項目類別偏好平均值。

3.4 計算推薦結(jié)果

傳統(tǒng)的協(xié)同過濾推薦算法在預測評分時，不考慮評分時間，忽略用戶興趣變化對預測評分的影響，推薦的結(jié)果具有片面性。實際上，用戶感興趣的項目會隨著時間而發(fā)生變化，過去感興趣的項目現(xiàn)在不一定會感興趣，所以在進行評分預測時要考慮到時間因素。根據(jù)人類記憶遺忘曲線提出的一種模擬人類興趣變化的時間函數(shù)，將該函數(shù)融入到傳統(tǒng)協(xié)同過濾推薦算法的評分預測。通過給予不同評分時間不同得分權(quán)重，來模擬用戶的興趣變化。模擬人類的興趣變化函數(shù)公式如下所示：

其中，tui表示用戶u對項目i的評分時間，tug表示用戶u對項目最早評分時間，f(tui)表示預測評分中的時間權(quán)重因子。f(tui) 的取值范圍是（0，1），隨著tui的增大，權(quán)重因子f(tui)也在不斷增大。將公式f(tui)引入到傳統(tǒng)評分預測公式中，得到改進后評分預測公式（20）如下所示：

其中，Nu表示用戶u的最近鄰居集，sim(u,v)表示用戶u和用戶v之間相似度，rvi表示用戶v對項目i評分，表示用戶u平均評分值，表示用戶v平均評分值。

從公式中可以看出，隨著時間的推移，時間權(quán)重因子越小，預測的評分值越低。該公式符合用戶的興趣變化，更能準確預測用戶對項目的評分。

4 實驗及結(jié)果分析

4.1 數(shù)據(jù)集簡介

MovieLens是一個基于評分的電影推薦系統(tǒng)，由美國明尼蘇達州大學GroupLens研究小組創(chuàng)建，其中包括100 KB、1 MB、10 MB三個規(guī)模的數(shù)據(jù)集，專門用于研究推薦技術(shù)。本文使用的是MovieLens 100k數(shù)據(jù)集驗證算法的性能，此數(shù)據(jù)集被公認是評估推薦算法的主要數(shù)據(jù)集。其中包括1 943名用戶對1 682部電影的100 000個評分記錄，且數(shù)據(jù)集的每個用戶至少對20部電影進行評分，評分范圍是1～5分，用戶對某電影的評分值越高則說明用戶越喜歡這部電影。本數(shù)據(jù)集構(gòu)建的用戶項目評分矩陣稀疏度為93.7%。在實驗前把數(shù)據(jù)集按照9∶1的比例分割對數(shù)據(jù)進行交叉驗證，即將90%的數(shù)據(jù)作為訓練集，剩余的部分作為測試集。

4.2 評價指標

（1）聚類效果評價指標

在實驗中使用聚類的準確率來衡量聚類的效果。聚類準確率是指正確劃分的樣本個數(shù)占總體樣本數(shù)的比例，公式如下：

其中，NUCF表示通過基于用戶的協(xié)同過濾推薦算法得出的相似用戶鄰居集合；NFPAFCM表示本文算法得出的相似用戶鄰居集合。

（2）推薦質(zhì)量評價指標

本文選擇平均絕對誤差MAE（Mean Absolute Error）作為評價推薦質(zhì)量優(yōu)劣的指標。通過計算訓練集中預測評分和測試集中真實評分之間的平均絕對誤差度量評分預測的準確性，預測評分與實際評分越接近，MAE值越小，推薦效果越好。假設(shè)用戶U預測評分表為Pu={PU1,PU2,…,PUT}，實際評分表為Qu={QU1,QU2,…,QUT}，T為測試集的評分數(shù)量，平均絕對誤差MAE的定義為：

4.3 實驗結(jié)果與分析

在實驗中，本文算法的參數(shù)設(shè)置m=2，S=20，MCN=500,p=0.8。

通過實驗檢驗相似度計算公式中比例因子λ對推薦結(jié)果的影響，確定λ的最優(yōu)值。實驗中選取最近鄰數(shù)量為40，當用戶的聚類個數(shù)為5、10、15、20時，隨著比例因子λ從0遞增到1，遞增間隔為0.1，MAE的變化情況如圖3所示。

從圖3可以看出，無論用戶的聚類個數(shù)為多少，當比例因子λ在[0，0.4]范圍內(nèi)時，MAE隨著λ的增加而減小，說明推薦效果越來越好；當比例因子λ在[0.4，1]范圍內(nèi)時，MAE值隨著λ的增加而變大，顯示推薦效果逐漸減弱。因此，本文算法的比例因子λ的最優(yōu)值為0.4。

圖4的橫坐標表示用戶的聚類數(shù)c，顯示出實驗中c值選取6、8、10、12、14、16時，MAE值的變化情況。實驗結(jié)果表明用戶聚類數(shù)c的確定對推薦算法的準確性有直接的影響，c值過大或是過小都會引起MAE值的升高，也就是誤差會增加。根據(jù)圖4可知，隨著用戶聚類數(shù)的增加，當用戶聚類數(shù)在[6，10]時，MAE值相應(yīng)減小；當用戶聚類數(shù)在[10，16]時，MAE值相應(yīng)增大。用戶聚類數(shù)為10時，MAE值達到最小。所以聚類個數(shù)為10時，推薦效果最佳。

圖3 MAE隨比例因子λ的變化情況

圖4 MAE隨用戶聚類個數(shù)的變化情況

圖5 兩種算法的聚類準確率對比圖

圖5 描述了FCM聚類算法和FPAFCM聚類算法在avg、low、high三種數(shù)據(jù)統(tǒng)計情況下的聚類準確率的變化情況。實驗統(tǒng)計數(shù)據(jù)是將30次的實驗結(jié)果取平均值，這樣可以避免數(shù)據(jù)隨機性造成的誤差。橫坐標avg表示統(tǒng)計數(shù)據(jù)的平均值；low表示統(tǒng)計最低值數(shù)據(jù)的平均值；high表示統(tǒng)計最高值數(shù)據(jù)的平均值。縱坐標cor表示聚類準確率，計算公式如式（21）所示。從圖5中顯示在avg、low、high三種數(shù)據(jù)統(tǒng)計的情況下，F(xiàn)PAFCM聚類算法與FCM聚類算法對應(yīng)的聚類準確率cor相比有明顯的提升。這是因為FPAFCM聚類算法利用花朵授粉算法找到了最優(yōu)的初始聚類中心，有效地避免陷入局部最優(yōu)值，再通過優(yōu)化的模糊C均值算法對用戶聚類，從而有效提高聚類的準確率。

為了驗證本文算法推薦的準確性，將基于用戶的協(xié)同過濾推薦算法（UserCF）[27]、基于模糊C均值聚類推薦算法（FCM）[28]、基于粒子群優(yōu)化模糊均值聚類算法（PSOFCM）[25]與本文的算法進行對比實驗。設(shè)置最近鄰個數(shù)從10遞增到35，遞增間隔為5。圖6反映了隨著最近鄰個數(shù)的增加，MAE值的變化情況。可以看出實驗中UserCF、FCM、PSOFCM和文中的算法都隨著目標用戶最近鄰個數(shù)增加而降低并且逐漸趨于穩(wěn)定。本文提出算法在不同最近鄰居個數(shù)下的MAE值都明顯低于其他三種算法，推薦結(jié)果準確性最高。FCMCF算法是在基于用戶的協(xié)同過濾推薦算法中加入模糊C均值聚類算法，PSOFCM算法則是在基于用戶的協(xié)同過濾算法中加入了粒子群優(yōu)化的模糊聚類算法，但是本文在預處理的用戶類別偏好矩陣基礎(chǔ)上，利用花朵授粉優(yōu)化的模糊聚類算法對用戶進行聚類，增強聚類的效果。計算相似度時，將用戶偏好信息的相似度與項目評分矩陣的相似度加權(quán)求和，評分預測融合時間因素對用戶興趣變化的影響，改進相似度計算公式和評分預測公式，進一步提高推薦的準確性。

5 結(jié)束語

本文提出一種優(yōu)化聚類的協(xié)同過濾推薦算法。首先根據(jù)用戶評分的差異，對評分進行預處理，構(gòu)造用戶類別偏好矩陣，充分利用用戶和項目之間的隱含信息，并通過降維有效緩解數(shù)據(jù)的稀疏性。然后在該矩陣上利用花朵授粉算法優(yōu)化的模糊聚類算法對用戶聚類，增強了用戶的聚類效果。將項目的類別屬性信息融入到傳統(tǒng)的協(xié)同過濾推薦算法用戶之間相似度的計算。最后充分考慮時間因素對用戶評分預測的影響，使推薦準確性有很大的提高。在未來的工作中，對于更大數(shù)據(jù)規(guī)模，可以通過spark分布式平臺實現(xiàn)，進而提高推薦的質(zhì)量和效率。