基于聚類分析的協(xié)同過濾算法研究

顏 穎

基于聚類分析的協(xié)同過濾算法研究

顏 穎

（福建水利電力職業(yè)技術(shù)學(xué)院，福建永安 366000）

電子商務(wù)推薦系統(tǒng)憑借著“智能感知”用戶的興趣和需求的能力，實現(xiàn)個性化商品推薦。傳統(tǒng)算法以協(xié)同過濾作為主要技術(shù)手段實現(xiàn)個性化推薦功能，但是隨著電商業(yè)務(wù)的發(fā)展，數(shù)據(jù)稀疏性和推薦的實時性倍受挑戰(zhàn)。據(jù)此，結(jié)合聚類分析的優(yōu)點，改進(jìn)傳統(tǒng)算法，提出一種聚類分析與協(xié)同過濾相結(jié)合的推薦算法。實驗表明，改進(jìn)后的算法具有較好的推薦準(zhǔn)確性。

協(xié)同過濾；聚類；個性化推薦

推薦系統(tǒng)早就應(yīng)用于電子商務(wù)領(lǐng)域，并獲得了良好的發(fā)展。該系統(tǒng)是建立在海量數(shù)據(jù)挖掘基礎(chǔ)上的一種高級智能技術(shù)，通過收集客戶和商品信息及消費(fèi)記錄，研究興趣需求，進(jìn)行個性化推薦計算，從而將其感興趣的產(chǎn)品推薦給目標(biāo)用戶。部分的電商平臺、網(wǎng)站都提供了相應(yīng)的推薦服務(wù)來引導(dǎo)用戶進(jìn)行購物。該推薦系統(tǒng)研究的關(guān)鍵是如何提高推薦算法的質(zhì)量和效率，因此推薦算法是整個推薦系統(tǒng)的主體部分，推薦算法的優(yōu)劣決定著推薦系統(tǒng)的性能。

1 相關(guān)算法介紹

目前在電子商務(wù)推薦系統(tǒng)中使用的推薦算法有：Bayesian網(wǎng)絡(luò)、關(guān)聯(lián)規(guī)則、聚類分析、Horting圖、協(xié)同過濾推薦算法等。目前，商家應(yīng)用較多、較為著名的一種推薦技術(shù)是協(xié)同過濾（Collaborative Filtering）。

1.1 協(xié)同過濾推薦算法介紹

協(xié)同過濾推薦算法是基于興趣愛好相似的用戶可能具有相似的購物行為的原理。它的實現(xiàn)過程是通過對用戶歷史行為數(shù)據(jù)的挖掘發(fā)現(xiàn)用戶的偏好，在海量數(shù)據(jù)中挖掘出與目標(biāo)用戶品位最為相近的k個“鄰居”，然后分析這些“鄰居”的興趣偏好，利用公式預(yù)測某些未瀏覽項目的評分值，從而形成關(guān)于該指定用戶的喜好預(yù)測，并為其推薦喜好評分排序在前的N件商品。

協(xié)同過濾的實現(xiàn)過程主要要經(jīng)過以下三個步驟：獲取用戶信息、選擇近鄰和預(yù)測推薦。

1.1.1 獲取用戶信息

在電子商務(wù)網(wǎng)站上，用戶信息的來源有多種，每天服務(wù)器、代理服務(wù)器以及客戶終端就會生成日志文件和Cookies，這些日志文件和Cookies記錄了用戶瀏覽電子商務(wù)網(wǎng)站的來源網(wǎng)站、對每個頁面的訪問次數(shù)、對某種商品單擊的次數(shù)以及放入購物車的物品名稱和數(shù)量等信息，從而搜集到用戶的瀏覽行為與習(xí)慣。

通過獲取的用戶評價信息得到“用戶——項目評分矩陣Rmxn（UI）”，如表1所示。在該矩陣中行表示用戶，列表示商品即項目，元素rij表示用戶Ui對項目Ij的評分值，一般用[1，5]的數(shù)值表示，分?jǐn)?shù)越高則表示越喜歡這個項目。

表1 用戶——項目評分矩陣表

1.1.2 尋找近鄰

近鄰是指與目標(biāo)用戶偏好最為接近的用戶，協(xié)同過濾推薦的關(guān)鍵步驟在于準(zhǔn)確定位目標(biāo)用戶的最近鄰居集SNIu。確定近鄰的基礎(chǔ)思路是：依據(jù)公式計算目標(biāo)用戶u與數(shù)據(jù)庫中其他所有用戶v間的相似度sim（u,v），根據(jù)計算的 sim（u,v）值，選擇值最大的前 k個的用戶作為最近鄰居集SNIu。因此相似性的準(zhǔn)確與否對推薦精度有著關(guān)鍵性的影響。實驗表明，皮爾遜相關(guān)系數(shù)能更好地衡量用戶間的相似程度，相關(guān)系數(shù)越高，則兩者的相似性越大；反之，則相似性越小。因此本文也采用皮爾遜系數(shù)進(jìn)行實驗對比分析。其計算公式如下：

其中，PUV表示評分項目集合，Ru,α和Rv,α表示對商品項目α的評分，R表示平均分。

1.1.3 預(yù)測推薦

依據(jù)之前找到的目標(biāo)用戶u的最近鄰居集SNIu，實現(xiàn)智能推薦功能。利用近鄰v對項目i的歷史評分值，預(yù)測目標(biāo)用戶u對該項目的評分值，其計算公式如下：

根據(jù)計算結(jié)果Pu,i的高低，選擇評分值最高的前N項（top—N）商品作為結(jié)果向客戶進(jìn)行推薦。

相比于其他的推薦算法，傳統(tǒng)的協(xié)同過濾算法考慮了歷史行為數(shù)據(jù)，推薦過程是完全自動的，并且對推薦對象沒有特殊要求，尤其是一些難以進(jìn)行內(nèi)容分析的抽象項目也能夠?qū)崿F(xiàn)推薦。但它過于依賴相似度的計算準(zhǔn)確性，數(shù)據(jù)稀疏性和系統(tǒng)可擴(kuò)展性仍然是它所面臨的挑戰(zhàn)。

1.2 聚類分析

聚類分析是基于“物以類聚”的原理，按照某種屬性或規(guī)律（例如歐幾里德距離）將一組個體劃分成相對同質(zhì)的群組（也就是簇）的統(tǒng)計分析技術(shù)。同一個簇內(nèi)的對象具有較高的同質(zhì)性，而不同簇間的對象有很大的異質(zhì)性。因此同一簇中的元素可以互為近鄰。其目標(biāo)是在相似的基礎(chǔ)上將數(shù)據(jù)劃分到不同的類，聚類的結(jié)果使得同一類中的對象相似性盡可能大，而不同類間的對象相似性最小。因此通過聚類分析，可以區(qū)分具有不同特征的客戶群，并且通過購買模式刻畫不同的客戶群的特征，并概括出每類群體的消費(fèi)模式即消費(fèi)習(xí)慣，進(jìn)而為各個群體提供可行的營銷方案與可靠依據(jù)。通過聚類，人們能夠識別數(shù)據(jù)對象密集的和稀疏的區(qū)域，因而發(fā)現(xiàn)全局的對象分布模式，以及數(shù)據(jù)屬性之間的相互關(guān)系。聚類基本操作步驟：

1）計算n個樣品兩兩間的距離，得到樣品間的距離矩陣；

2）初始n個樣品各自看成一類，共有n類，此時類間的距離就是樣品間的距離；

3）將類間距離最小的兩類進(jìn)行并類，其余不變，這時類的個數(shù)減少一個，即得到n-1類；

4）按照之前的計算方法，計算新類與其它各類之間的距離，再將關(guān)系最為密切的兩類合并為一類，其余不變，即得到n-2類，如此下去直到最后所有的樣品都?xì)w為一類為止；

5）畫譜系聚類圖；

6）決定分類的個數(shù)和各類的成員。

聚類算法的復(fù)雜度較低，因為基于聚類的推薦不是在數(shù)據(jù)庫中搜索所有用戶集和目標(biāo)用戶進(jìn)行相似性比較，而是在相對小的范圍內(nèi)，只在包含有目標(biāo)用戶的簇中進(jìn)行相似性計算，減少了異類數(shù)據(jù)間的相似性計算，提高了推薦速度。但是使用聚類分析時，用戶只能屬于一個單獨的類別，不符合用戶多興趣的特點。另外當(dāng)用戶處于一個聚類的邊緣時，推薦質(zhì)量也比較低。聚類推薦將同一簇中的用戶平等看待，但事實是簇中的用戶間的距離是不同的。

2 問題陳述

協(xié)同過濾算法被應(yīng)用在電子商務(wù)推薦系統(tǒng)中，但是隨著電商業(yè)務(wù)的發(fā)展，網(wǎng)絡(luò)平臺上參與交易的用戶和商品項數(shù)量較多，傳統(tǒng)協(xié)同過濾算法的缺點開始顯現(xiàn)出來，推薦質(zhì)量落后于用戶和商家的期望。

在協(xié)同過濾算法計算過程中，利用公式（1）求得兩兩間的相似性問題來尋找鄰居，計算量會隨著用戶和商品的增加而呈線性增長。該算法理論上能為幾千名用戶提供較好的推薦服務(wù)，但是如今網(wǎng)絡(luò)中用戶數(shù)或商品數(shù)量通常都較大，在用戶——項目評分矩陣中，用戶U和項目I的維數(shù)都較大，海量用戶數(shù)據(jù)模型勢必對系統(tǒng)造成性能壓力，給傳統(tǒng)的推薦系統(tǒng)增加負(fù)擔(dān)，無法滿足存儲空間的要求，傳統(tǒng)的協(xié)同過濾算法的性能就開始急劇下降，很難滿足用戶實時性的推薦要求，面臨著可擴(kuò)展問題。

另一方面，在相似度計算公式（1）中，需要用到兩個用戶對共同的項目集合進(jìn)行評分，但是我們知道，在網(wǎng)站中商品項目較多，用戶的歷史記錄數(shù)據(jù)占整個商品集較小的一部分。因此在用戶——項目評分矩陣中，每行用戶只對較少的項目作出評分，這就面臨著數(shù)據(jù)稀疏性問題。數(shù)據(jù)稀疏性導(dǎo)致兩個用戶共同評價的項目數(shù)量較少，因此利用公式（1）尋找最近鄰居時，一方面會造成信息的丟失，另一方面計算時會耗費(fèi)很大，使得推薦效果大打折扣。

以上兩點正是傳統(tǒng)的基于協(xié)同過濾技術(shù)在實際中所面臨的挑戰(zhàn)。任何單種的推薦方法總有它自身的優(yōu)缺點，聚類分析過程是將目標(biāo)用戶的最近鄰搜索空間局限在某一個簇中，對數(shù)據(jù)源進(jìn)行“瘦身”，有效的減少了搜索空間，因此在擴(kuò)展性和實現(xiàn)性能上比傳統(tǒng)的協(xié)同過濾技術(shù)略顯優(yōu)勢。

3 算法改進(jìn)

單一推薦算法各有優(yōu)劣，為了彌補(bǔ)協(xié)同過濾推薦算法所面臨的可擴(kuò)展性和數(shù)據(jù)稀疏性方面的缺陷，本文綜合傳統(tǒng)的協(xié)同過濾和聚類分析技術(shù)優(yōu)點，提出了一種將聚類分析與協(xié)同過濾相結(jié)合的推薦算法，希望能夠提升商品的推薦質(zhì)量，從而達(dá)到揚(yáng)長避短的目的。

改進(jìn)后算法的基本思路：事先給定一個包含有n個樣本對象的數(shù)據(jù)庫，和要劃分的簇的數(shù)目k（k＜=n）。首先使用聚類算法對數(shù)據(jù)對象進(jìn)行預(yù)處理，把項目劃分到k個簇里面。項目分類后，選擇該用戶的興趣簇作為數(shù)據(jù)源進(jìn)行推薦計算。在這個興趣簇中建立用戶——項目評分矩陣。使用基于項目的協(xié)同過濾算法預(yù)測未評價項目的評分值，填充至用戶——項目評分矩陣，獲得密度更高的新的用戶——項目評分矩陣。使用基于用戶的協(xié)同過濾算法計算目標(biāo)項的預(yù)測值，選取預(yù)測值排名前N項進(jìn)行推薦。改進(jìn)后的算法一方面有效解決了算法的可擴(kuò)展性問題，又滿足用戶只對某幾類商品感興趣的特性。以下為算法的具體實現(xiàn)步驟：

3.1 數(shù)據(jù)預(yù)處理

該階段主要針對初始的用戶信息，對用戶——項目評分矩陣?yán)锏乃许椖窟M(jìn)行聚類操作，原先的用戶——項目評分矩陣被劃分為幾個子矩陣。

1）從初始數(shù)據(jù)中，獲取n個項目集合；

2）從n個項目中任意選取k個項目作為聚類中心，執(zhí)行聚類操作步驟中的3）和4）操作，最終確定每個聚類包含的對象。

3.2 降低數(shù)據(jù)稀疏性

上一步驟獲取的子矩陣比較稀疏，針對數(shù)據(jù)稀疏問題，可以利用基于項目的協(xié)同過濾算法，對用戶未評價項目進(jìn)行預(yù)測評分，將預(yù)測結(jié)果填充進(jìn)之前的子矩陣中，從而生成較為稠密的用戶——項目評分矩陣。此過程的計算量比較小，可以獲取較好的性能。

1）計算與目標(biāo)項目相似度最高的前N項作為鄰居；

2）根據(jù)相鄰項的評分值，使用預(yù)測值公式計算未評價項的預(yù)測值，選取預(yù)測值最大的前N個預(yù)測值作為推薦評價集合；

3）將多個推薦評價集合進(jìn)行合并，從這些推薦評價集合中選取前N個預(yù)測值組成最終推薦評價集合；

4）把推薦評價集合里的預(yù)測值填入該用戶——項目評分矩陣中，形成新的較為稠密的用戶——項目評分矩陣。

3.3 產(chǎn)生推薦

通過降低數(shù)據(jù)稀疏性處理可以獲得較為稠密的用戶——項目評分矩陣，使用基于用戶的協(xié)同過濾算法，計算未評價項目的預(yù)測值。對預(yù)測值進(jìn)行降序排列，選取前N項進(jìn)行推薦。

1）找出目標(biāo)用戶a所在的用戶——項目評分矩陣，對在該矩陣中目標(biāo)用戶a未評分過的項目j，采用預(yù)測值公式計算預(yù)測值Paj；

2）如果項目j屬于多個類別則選取Paj=max（Paj1，Paj2，···，Pajk）；

3）對每一類別的Paj值進(jìn)行計算后降序排列，選取Paj最高的前N個項目作為top-N推薦集推薦給用戶。

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

4.1 實驗數(shù)據(jù)選取

本文采用GroupLens項目組提供的電源評價數(shù)據(jù)集作為本次實驗數(shù)據(jù)。數(shù)據(jù)集中數(shù)據(jù)的分布情況如表2所示。該數(shù)據(jù)集包含了隨機(jī)挑選了600個用戶對1600部電影的7萬條評價數(shù)據(jù)。這些評價以5分制為基準(zhǔn)，即每部電影的評分范圍為0—5分。將獲取的這些評分?jǐn)?shù)據(jù)轉(zhuǎn)換成用戶——項目評分矩陣，該評分矩陣密度為7.3%，是典型的稀疏矩陣。

表2 數(shù)據(jù)集中數(shù)據(jù)分布情況表

4.2 評價準(zhǔn)則

平均絕對偏差（MAE）值用來反映推薦系統(tǒng)計算出的預(yù)測評分值與用戶對該項目的實際評分值之間的平均偏差，常常用于刻畫推薦系統(tǒng)的準(zhǔn)確性，是較常用的度量推薦質(zhì)量的方法之一。本文選取MAE指標(biāo)作為度量本次實驗輸出結(jié)果優(yōu)劣的標(biāo)準(zhǔn)。MAE值越小，說明對用戶評分的預(yù)測更精確，推薦質(zhì)量也相應(yīng)越好。假設(shè)用戶 i的預(yù)測評分集為{P1，P2，…PN}，用戶 i的實際評分集為{q1，q2，…qN}，則 MAE 的計算公式如下：

4.3 實驗結(jié)果分析

在本次實驗中，我們設(shè)定用戶聚類數(shù)k=12，推薦集合N=19，鄰居集數(shù)量從10取到50，為了驗證改進(jìn)算法的有效性，分別采用傳統(tǒng)的算法和改進(jìn)后的算法進(jìn)行實驗，用MAE指標(biāo)來評價算法的推薦準(zhǔn)確性。測試結(jié)果如表3所示，兩種算法在MAE指標(biāo)中的比較情況如圖1所示。

表3 最近鄰居集大小不同所得的測試數(shù)據(jù)表

圖1 兩種算法在MAE指標(biāo)中的比較情況示意圖

通過上述的對比實驗可以看出，在鄰居集大小變化的情況下，改進(jìn)后的MAE值整體小于傳統(tǒng)算法的值，這說明改進(jìn)后算法的推薦準(zhǔn)確率優(yōu)于傳統(tǒng)協(xié)同過濾算法，并且改進(jìn)后的算法受鄰居集數(shù)量的影響稍大一些。但是不管采用哪種算法，MAE的值都隨著鄰居集數(shù)量的增加而逐漸減小，并且變化值會不斷趨于平緩，也就是推薦的準(zhǔn)確性也就越高。

5 結(jié)語

任何單一的推薦算法總有它的優(yōu)缺點，為了彌補(bǔ)單個算法的缺陷，一些學(xué)者將多種算法或推薦系統(tǒng)整合起來。本文在前人研究的基礎(chǔ)上，結(jié)合協(xié)同過濾推薦技術(shù)和聚類分析技術(shù)的優(yōu)勢，改進(jìn)傳統(tǒng)算法。實驗對照發(fā)現(xiàn)，對傳統(tǒng)算法加以改進(jìn)，推薦質(zhì)量能獲得顯著的提高，一定程度上減少了數(shù)據(jù)稀疏性和可擴(kuò)展性方面的弱點，達(dá)到較好的預(yù)期目的。但是在數(shù)據(jù)冷啟動等方面仍然存在問題，有待進(jìn)一步解決。

[1]何安.協(xié)同過濾技術(shù)在電子商務(wù)推薦系統(tǒng)中的應(yīng)用研究[D].杭州：浙江大學(xué),2007.

[2]楊芳.電子商務(wù)系統(tǒng)協(xié)同過濾推薦算法研究[D].天津：河北工業(yè)大學(xué),2006.

[3]李聰.電子商務(wù)協(xié)同過濾可擴(kuò)展性研究綜述[J].現(xiàn)代圖書情報技術(shù),2010(11):37-44.

[4]邢瓊香.基于信任的協(xié)同過濾算法在電子商務(wù)推薦系統(tǒng)中的研究[D].南昌：南昌大學(xué),2014.

[5]李容.協(xié)同過濾推薦系統(tǒng)中稀疏性數(shù)據(jù)的算法研究[D].成都：電子科技大學(xué),2016.

[6]王曉耘,錢璐,黃時友.基于粗糙用戶聚類的協(xié)同過濾推薦模型[J].現(xiàn)代圖書情報技術(shù),2015(1):45-51.

[7]李清霞,魏文紅,蔡昭權(quán).混合用戶和項目協(xié)同過濾的電子商務(wù)個性化推薦算法[J].中山大學(xué)學(xué)報(自然科學(xué)版),2016(5):37-42.

Research on coordination filtering algorithm based on clustering analysis

YANYing
（Fujian College ofWater Conservancyand Electric Power,Yongan,Fujian,China 366000）

The E-commerce personalized recommendation system relies on the ability of intellisense about the users'interest and demand to realize personalized commodity recommendation.The traditional algorithm takes coordination filtration as the main technical method to realize the personalized recommendation function.But with the development of E-commerce,data sparsity and recommendation timeliness are challenged.With the advantages of cluster analysis,the traditional algorithm is improved and a recommendation algorithm is put forward which combines cluster analysis with coordination filtration.The experiment shows that the improved algorithmhas a good recommendation accuracy.

coordination filtration;cluster;personalized recommendation

10.3969/j.issn.2095-7661.2017.04.013】

TP391.3;F713.36

A

2095-7661（2017）04-0040-04

2017-08-06

顏穎（1982-），女，福建永安人，福建水利電力職業(yè)技術(shù)學(xué)院實驗師，碩士，研究方向：電子商務(wù)實踐教學(xué)。

2016年福建省中青年教師教育科研項目（科技類）階段成果（項目編號：JAT160777）。