胡朝舉+孫克逆

摘 要：推薦系統(tǒng)是根據(jù)用戶的歷史瀏覽記錄或?qū)?xiàng)目的評(píng)分記錄，自動(dòng)為用戶推送需要的信息，完成個(gè)性化推薦功能，是信息獲取領(lǐng)域非常重要的技術(shù)。首先對(duì)用戶進(jìn)行模糊C均值聚類操作，將用戶分為用戶簇。將加權(quán)的歐氏距離替換傳統(tǒng)的歐氏距離計(jì)算方法，在目標(biāo)用戶所在的用戶簇內(nèi)進(jìn)行協(xié)同過(guò)濾推薦，得到Top-n推薦集，為用戶完成項(xiàng)目推薦。實(shí)驗(yàn)結(jié)果表明，該方法可以提高推薦精度，減少評(píng)分誤差，提高推薦質(zhì)量，優(yōu)化推薦效果。

關(guān)鍵詞：模糊聚類；推薦系統(tǒng)；協(xié)同過(guò)濾；加權(quán)歐氏距離

DOIDOI：10.11907/rjdk.172225

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）002-0031-04

0 引言

隨著Web2.0的飛速發(fā)展，互聯(lián)網(wǎng)技術(shù)日益成熟，人類進(jìn)入信息超載（Information Overload）時(shí)代。如何在爆炸的信息中獲取想要的信息，是信息時(shí)代面臨的最大挑戰(zhàn)。人們通過(guò)搜索引擎找到自己感興趣的信息[1]，但搜索引擎并不能完全滿足需求，因?yàn)橛袝r(shí)需求并不是很明確，無(wú)法通過(guò)搜索引擎搜索，于是推薦系統(tǒng)應(yīng)運(yùn)而生。通過(guò)分析用戶的一些行為習(xí)慣自動(dòng)給用戶推薦各種信息，且推薦內(nèi)容根據(jù)用戶的行為變化實(shí)時(shí)更新，能夠最大程度地提高用戶體驗(yàn)，為用戶帶來(lái)最精準(zhǔn)的互聯(lián)網(wǎng)信息。

當(dāng)今的推薦技術(shù)中，協(xié)同過(guò)濾是最為成熟、應(yīng)用最成功的技術(shù)。該技術(shù)主要針對(duì)用戶-項(xiàng)目評(píng)分矩陣進(jìn)行推薦[2]，但該技術(shù)有很多不足，如最典型的稀疏性問(wèn)題和實(shí)時(shí)性問(wèn)題。由于用戶不可能對(duì)每個(gè)項(xiàng)目進(jìn)行評(píng)分，所以當(dāng)項(xiàng)目評(píng)分矩陣比較稀疏時(shí)，進(jìn)行用戶相似度計(jì)算會(huì)產(chǎn)生較大的誤差，且在整個(gè)用戶中尋找相似用戶花費(fèi)時(shí)間較長(zhǎng)，從而影響推薦效率。

本文在進(jìn)行協(xié)同過(guò)濾推薦前，首先對(duì)用戶進(jìn)行聚類操作，通過(guò)模糊聚類算法把興趣愛(ài)好類似的用戶分到一類，即同一個(gè)簇中；針對(duì)待推薦用戶所在的簇，通過(guò)協(xié)同過(guò)濾算法進(jìn)行用戶相似度計(jì)算，最后得到待評(píng)價(jià)項(xiàng)目的預(yù)測(cè)值，產(chǎn)生Top-N推薦[3]。聚類技術(shù)的引入可以縮小相似鄰居的計(jì)算范圍，從而減少推薦算法的時(shí)間。同時(shí)，本文針對(duì)聚類中距離的計(jì)算進(jìn)行了改進(jìn)。實(shí)驗(yàn)表明本文方法可以優(yōu)化聚類效果，提高推薦質(zhì)量。

1 基于用戶模糊聚類的協(xié)同過(guò)濾推薦

1.1 模糊C-均值聚類（FCM）

模糊聚類的本質(zhì)就是針對(duì)對(duì)象的某些屬性來(lái)構(gòu)建模糊矩陣，然后通過(guò)一定的方法進(jìn)行分類操作，模糊聚類算法分類比較簡(jiǎn)單且分類效果較好。

模糊C-均值聚類（FCM）是J.C.Dunn按照E.Ruspini[4]定義的模糊劃分集合的概念，從硬C-均值聚類算法推廣得到的，最大的不同是在隸屬度uij上乘一個(gè)權(quán)重值m[5]。FCM的數(shù)學(xué)模型如下：

1.2 FCM在用戶-項(xiàng)目評(píng)分矩陣中的應(yīng)用

1.2.1 用戶-項(xiàng)目評(píng)分問(wèn)題的數(shù)學(xué)模型

將模糊聚類引入評(píng)分矩陣X中，該矩陣表示n個(gè)用戶對(duì)m個(gè)項(xiàng)目進(jìn)行評(píng)價(jià)，（xik）n表示用戶i對(duì)項(xiàng)目k的評(píng)分，需要根據(jù)用戶對(duì)各個(gè)項(xiàng)目的評(píng)分對(duì)用戶進(jìn)行聚類，將用戶分為c個(gè)簇，使得同一個(gè)簇中的用戶相似性最高，并且把聚類的結(jié)果通過(guò)矩陣U表示出來(lái)，其中uki表示用戶i對(duì)用戶簇k的隸屬度。

針對(duì)用戶模糊聚類的函數(shù)為：

式（10）中：uki表示用戶i在用戶簇k中的隸屬程度，dki表示用戶i與用戶簇k的聚類中心距離（通常為歐幾里德距離），ck表示用戶簇k的中心點(diǎn)，即該簇的聚類點(diǎn)，m表示決定聚類結(jié)果模糊度的權(quán)重指數(shù)，一般1.25≤m≤2.5。參考國(guó)內(nèi)外文獻(xiàn)和實(shí)驗(yàn)，將m設(shè)為2。

本模糊聚類的基本原理為：計(jì)算用戶與各個(gè)聚類中心間的距離，通過(guò)得到的距離值計(jì)算用戶和各個(gè)聚類中心的隸屬度，通過(guò)比較隸屬度高低，將用戶分到最高的隸屬度用戶簇中，使同一個(gè)用戶簇中的用戶之間相似度最高，減少不同簇用戶之間的相似度。

所以，要求得用戶-評(píng)分模糊聚類的最優(yōu)值，只需找到最佳的聚類中心點(diǎn)ck，k∈1，c和各個(gè)用戶對(duì)聚類中心的隸屬度uki，i∈1，n即可。

1.2.2 FCM聚類算法

為了解得模糊聚類目標(biāo)函數(shù)的最優(yōu)值，利用模糊聚類法則，在極值的約束條件[7] ∑ck=1uki=1下，求min{Jm（U，c）}，構(gòu)建拉格朗日函數(shù)，如式（11）所示：

1.3 基于用戶的協(xié)同過(guò)濾算法

基于用戶的協(xié)同過(guò)濾算法是分析其他用戶觀點(diǎn)，為目標(biāo)用戶產(chǎn)生推薦[9]，其基本思想是：如果某幾個(gè)用戶對(duì)項(xiàng)目的評(píng)分類似，則稱他們?yōu)椤班従佑脩簟保麄冎g就可能會(huì)有相同的興趣愛(ài)好，就可以把其他用戶喜歡的推薦給目標(biāo)用戶。

1.3.1 用戶相似度

協(xié)同過(guò)濾算法中最主要的是用戶最近鄰查詢，本文只需在目標(biāo)用戶所在簇中計(jì)算出與目標(biāo)用戶最相近的鄰居，然后進(jìn)行預(yù)測(cè)評(píng)分。度量?jī)蓚€(gè)用戶之間的相似度需要首先獲得兩個(gè)用戶對(duì)項(xiàng)目的所有評(píng)分，然后通過(guò)相似度度量公式計(jì)算兩個(gè)用戶之間的相似度，記為sim（i，j），其中i，j分別代表兩個(gè)用戶。用戶相似度計(jì)算方法有很多，本文采用相關(guān)相似性來(lái)度量，計(jì)算公式如下：

1.3.2 預(yù)測(cè)評(píng)分

在利用協(xié)同過(guò)濾算法完成用戶相似性度量之后，下一步就是預(yù)測(cè)評(píng)分，利用公式（16）對(duì)目標(biāo)用戶未評(píng)分的項(xiàng)目進(jìn)行預(yù)測(cè)，將評(píng)分按降序排列，把排名前n個(gè)項(xiàng)目推薦給用戶。

2 相關(guān)算法改進(jìn)

2.1 模糊聚類距離計(jì)算方法改進(jìn)

模糊C均值算法最重要的步驟是距離計(jì)算，計(jì)算各個(gè)用戶與聚類簇中心點(diǎn)的距離。距離的計(jì)算方法有很多，如歐氏距離、馬氏距離、相關(guān)系數(shù)法、最小算術(shù)平均法等，其中最常用的就是歐氏距離，計(jì)算公式如下[11]：

歐氏距離使用方便，計(jì)算簡(jiǎn)單，但是也有非常嚴(yán)重的缺陷。它將用戶對(duì)不同項(xiàng)目的興趣愛(ài)好視為“一般重要”，這樣不能體現(xiàn)出不同項(xiàng)目對(duì)不同用戶的重要程度，所以在一些情況下使用歐氏距離公式計(jì)算距離，聚類結(jié)果效果不理想。endprint

本文用加權(quán)的歐氏距離來(lái)替換傳統(tǒng)的歐氏距離，通過(guò)對(duì)不同的分量進(jìn)行不同的權(quán)重分配，改進(jìn)了聚類效果，計(jì)算公式如下：

式（17）中，si是對(duì)應(yīng)的方差，可將方差的倒數(shù)看作一個(gè)權(quán)重，彌補(bǔ)歐氏距離的缺陷，提高聚類效果。

2.2 推薦過(guò)程

首先通過(guò)模糊C均值聚類算法將用戶進(jìn)行分類，然后在各個(gè)用戶簇中使用協(xié)同過(guò)濾算法進(jìn)行用戶推薦，算法流程如圖1所示。

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

3.1 數(shù)據(jù)集

本文實(shí)驗(yàn)采用的數(shù)據(jù)集為MovieLens網(wǎng)站提供的電影評(píng)分?jǐn)?shù)據(jù)集，該數(shù)據(jù)集包括各種用戶對(duì)各個(gè)類別電影的評(píng)分，分值為1-5，本文使用932個(gè)用戶對(duì)1538部電影超過(guò)9000次的評(píng)分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn)。將所有的數(shù)據(jù)平均分為5組，每次選擇其中4組作為訓(xùn)練集，另外一組作為測(cè)試集，進(jìn)行5次實(shí)驗(yàn)。

本實(shí)驗(yàn)采用的衡量標(biāo)準(zhǔn)為平均絕對(duì)偏差（MAE），其基本原理是通過(guò)計(jì)算整個(gè)算法對(duì)目標(biāo)項(xiàng)目的預(yù)測(cè)值，和用戶實(shí)際評(píng)分值之間的誤差來(lái)衡量整個(gè)算法的優(yōu)劣。MAE值越低，說(shuō)明推薦的準(zhǔn)確度越高。計(jì)算公式如下：

3.2 實(shí)驗(yàn)結(jié)果

對(duì)用戶進(jìn)行模糊C均值聚類，采用相關(guān)相似性計(jì)算方式進(jìn)行相似度計(jì)算。由于分成不同數(shù)量的簇可能會(huì)對(duì)推薦結(jié)果產(chǎn)生較大的影響，所以本實(shí)驗(yàn)將分別對(duì)不同數(shù)量的聚類中心進(jìn)行測(cè)試，通過(guò)與傳統(tǒng)的協(xié)同過(guò)濾以及以普通歐氏距離為聚類距離計(jì)算的算法對(duì)比，驗(yàn)證本方法的優(yōu)劣。本實(shí)驗(yàn)測(cè)試的聚類中心個(gè)數(shù)為5-50，間隔為5，實(shí)驗(yàn)結(jié)果如圖2所示。

從圖2可以看出，隨著聚類中心的增加，MAE值呈變大的趨勢(shì)，說(shuō)明推薦的精度越來(lái)越低，推薦質(zhì)量越來(lái)越差。由折線圖可以看出，本文使用加權(quán)歐氏距離推薦算法，在推薦精度上要高于傳統(tǒng)的模糊聚類推薦算法，所以本算法可以提高推薦系統(tǒng)的推薦質(zhì)量。

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

本實(shí)驗(yàn)通過(guò)不斷的對(duì)比測(cè)試驗(yàn)證本算法的優(yōu)勢(shì)，通過(guò)實(shí)驗(yàn)結(jié)果可以得出，本文的推薦算法跟傳統(tǒng)的協(xié)同過(guò)濾算法以及傳統(tǒng)歐氏距離的模糊聚類推薦算法相比，在推薦精度上具有一定的提高。

因?yàn)閭鹘y(tǒng)歐氏距離計(jì)算的是各個(gè)點(diǎn)之間的絕對(duì)距離，未考慮到樣本之間不同屬性的差別，所以未滿足實(shí)際需求。本文將加權(quán)的歐氏距離代替?zhèn)鹘y(tǒng)的歐氏距離計(jì)算，彌補(bǔ)了傳統(tǒng)歐氏距離的缺陷，提高了推薦質(zhì)量。

參考文獻(xiàn)：

[1] 馮剛.基于J2EE的多語(yǔ)種元搜索引擎的研究與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2006.

[2] 劉明.基于聚類和會(huì)話情景的混合推薦算法研究[D].武漢：華中科技大學(xué)，2013.

[3] 李華，張宇，孫俊華.基于用戶模糊聚類的協(xié)同過(guò)濾推薦研究[J].計(jì)算機(jī)科學(xué)，2012，39（12）：83-86.

[4] ABBATTISTA F，DEGEMMIS M，LICCHELLI O.Improving the usability of an E-commerce web site through personalization[C].Proceedings of Workshop on Recommendation and Personalization in E-commerce，2002：231-278.

[5] 范九倫，吳成茂.FCM算法中隸屬度的新解釋及其應(yīng)用[J].電子學(xué)報(bào)，2004，32（2）：350-352.

[6] 熊擁軍，劉衛(wèi)國(guó)，歐鵬杰.模糊C-均值聚類算法的優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（11）：124-128.

[7] 張乾君.模糊聚類分析在企業(yè)競(jìng)爭(zhēng)情報(bào)系統(tǒng)中的應(yīng)用研究[D].西安：西安電子科技大學(xué)，2011.

[8] 孫靜.基于模糊聚類的電子商務(wù)協(xié)同過(guò)濾推薦研究[D].天津：河北工業(yè)大學(xué)，2011.

[9] 薛扣平.具有可信機(jī)制的推薦系統(tǒng)及其應(yīng)用研究[D].南京：東南大學(xué)，2008.

[10] 胡斌.基于用戶和資源權(quán)重的協(xié)同過(guò)濾推薦系統(tǒng)的研究與設(shè)計(jì)[D].武漢：武漢理工大學(xué)，2009.

[11] 光俊葉，劉明霞，張道強(qiáng).基于有效距離的譜聚類算法[J].計(jì)算機(jī)科學(xué)與探索，2014，8（11）：1365-1372.endprint