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

王永貴，劉凱奇

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

1 引言

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

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

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

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

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

2 相關(guān)知識

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

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

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

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

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

表1 用戶項(xiàng)目評分矩陣Rm,n

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

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

2.2 模糊C均值聚類算法

設(shè)數(shù)據(jù)集x={x1,x2,…,xn}?Rn為一個(gè)有限數(shù)據(jù)集合，其中xi={xi1,xi2,…,xin}，n為數(shù)據(jù)樣本個(gè)數(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ù)作為目標(biāo)函數(shù)，定義式如公式（2）所示：

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

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

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

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

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

過程：

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

步驟2隨機(jī)生成初始聚類中心。

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

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

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

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

2.3 花朵授粉算法

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

FPA算法的主要思想：

（1）首先進(jìn)行初始化種群。

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

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

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

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

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

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

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

當(dāng)p

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

3 本文算法

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

圖2 本文算法流程圖

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

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

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

表2 項(xiàng)目類型矩陣Cn,y

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

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

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

其中，r′ui是預(yù)處理后的評分值，rui表示原始用戶對項(xiàng)目i的評分值表示用戶u的平均評分值。因?yàn)樵u分為5分制，所以rˉ定為3。

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

其中，cit=1表示項(xiàng)目屬于類別t。

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

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

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

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

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

FPAFCM算法基本步驟如下：

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

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

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

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

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

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

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

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

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

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

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

3.3 生成目標(biāo)用戶的最近鄰居

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

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

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

3.4 計(jì)算推薦結(jié)果

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

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

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

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

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

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

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

4.2 評價(jià)指標(biāo)

（1）聚類效果評價(jià)指標(biāo)

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

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

（2）推薦質(zhì)量評價(jià)指標(biāo)

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

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

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

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

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

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

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

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

圖5 兩種算法的聚類準(zhǔn)確率對比圖

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

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

5 結(jié)束語

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