王 巧, 謝穎華, 于世彩

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 上海 201620)

結(jié)合用戶聚類和項(xiàng)目類型的協(xié)同過濾算法①

王 巧, 謝穎華, 于世彩

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 上海 201620)

為了解決協(xié)同過濾算法中數(shù)據(jù)稀疏性問題, 提高推薦效果, 提出一種改進(jìn)的協(xié)同過濾算法. 該算法首先通過一種新的相似度計(jì)算方法來計(jì)算項(xiàng)目類型相似度, 將相似度大于某閾值的項(xiàng)目作為目標(biāo)項(xiàng)目的鄰居; 然后根據(jù)目標(biāo)用戶對(duì)鄰居項(xiàng)目的評(píng)分信息來預(yù)測(cè)該用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分值, 并將預(yù)測(cè)值填入稀疏的用戶項(xiàng)目評(píng)分矩陣; 最后對(duì)填充后的評(píng)分矩陣采用基于用戶聚類(K-means聚類)的協(xié)同過濾算法做出最終的預(yù)測(cè)評(píng)分進(jìn)行推薦.在Movielens 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證, 結(jié)果表明該算法能夠很好地緩解數(shù)據(jù)稀疏性、降低計(jì)算復(fù)雜度, 提高推薦精度.

數(shù)據(jù)稀疏性; 協(xié)同過濾; 項(xiàng)目類型; K-means聚類; Movielens 數(shù)據(jù)集

隨著信息技術(shù)的迅猛發(fā)展, 網(wǎng)絡(luò)成為人們生活中必不可少的一部分, 其產(chǎn)生的信息數(shù)據(jù)也呈指數(shù)型增長(zhǎng). 面對(duì)海量的信息, 用戶在選擇自己想要的東西時(shí),很難快速抉擇, 即產(chǎn)生了“信息過載”[1]現(xiàn)象. 針對(duì)該問題, 推薦系統(tǒng)[2]應(yīng)運(yùn)而生. 它通過記錄用戶行為信息,分析得出用戶偏好, 然后向用戶推薦其可能感興趣的信息, 避免出現(xiàn)用戶不需要的信息, 進(jìn)而更好地滿足用戶的個(gè)性化需求. 不同的推薦系統(tǒng)對(duì)應(yīng)不同的推薦技術(shù), 最常見的有關(guān)聯(lián)規(guī)則[3]、協(xié)同過濾技術(shù)、神經(jīng)網(wǎng)絡(luò)技術(shù)、貝葉斯網(wǎng)技術(shù)、圖模型技術(shù)等. 其中應(yīng)用最廣泛最成功的就是協(xié)同過濾技術(shù), 尤其是在電商領(lǐng)域中. 協(xié)同過濾算法主要包括兩方面: 基于模型的協(xié)同過濾和基于內(nèi)存的協(xié)同過濾[4]. 基于模型的協(xié)同過濾算法不受數(shù)據(jù)稀疏的影響, 多采用離線建模, 但計(jì)算復(fù)雜度高, 時(shí)效性低. 基于內(nèi)存的協(xié)同過濾算法以用戶項(xiàng)目評(píng)分為操作基礎(chǔ), 包括基于用戶(user-based CF)和基于項(xiàng)目(item-based CF)兩種. 該方法簡(jiǎn)單方便易實(shí)現(xiàn), 因而被廣泛采用.

協(xié)同過濾算法的基本思想是利用用戶項(xiàng)目評(píng)分矩陣, 找出與目標(biāo)用戶(項(xiàng)目)相似度最高的K個(gè)近鄰,利用近鄰的評(píng)分信息預(yù)測(cè)目標(biāo)用戶(項(xiàng)目)的評(píng)分信息,并將top-N[5]反饋給用戶作為推薦. 傳統(tǒng)的協(xié)同過濾算法在計(jì)算相似度時(shí)依賴于評(píng)分矩陣, 而實(shí)際數(shù)據(jù)中用戶評(píng)分信息很少, 使得推薦精度大大降低, 這就是所謂的數(shù)據(jù)稀疏性問題. 此外, 該算法還存在冷啟動(dòng)、擴(kuò)展性和實(shí)時(shí)性等問題[6]. 本文針對(duì)數(shù)據(jù)稀疏問題, 先利用項(xiàng)目類型相似性填充用戶評(píng)分矩陣, 然后對(duì)新矩陣基于用戶聚類, 不僅緩解了數(shù)據(jù)稀疏性 , 且聚類技術(shù)[7]的使用降低了計(jì)算復(fù)雜度、節(jié)省了時(shí)間, 實(shí)驗(yàn)證明該改進(jìn)的算法提高了推薦效果.

1 傳統(tǒng)的協(xié)同過濾算法

1.1 基于用戶的協(xié)同過濾算法

使用該算法的前提是認(rèn)為如果用戶的行為屬性相似, 那么他們興趣愛好也就相似, 在選擇某商品時(shí)他們可能更傾向于同一類, 對(duì)商品的評(píng)分值也相近. 所以在給目標(biāo)用戶做出推薦時(shí), 可以利用鄰居用戶的評(píng)分信息來對(duì)目標(biāo)用戶的評(píng)分進(jìn)行預(yù)測(cè). 這種算法思路簡(jiǎn)單清晰, 主要分三步: 構(gòu)建用戶項(xiàng)目評(píng)分矩陣、查找用戶鄰居、預(yù)測(cè)評(píng)分做出推薦.

① 建立用戶項(xiàng)目評(píng)分矩陣: 利用用戶購買商品的信息建立m×n評(píng)分矩陣,m代表用戶數(shù),n代表項(xiàng)目數(shù),Rij表示用戶i對(duì)項(xiàng)目j的評(píng)分值. 評(píng)分值的范圍通常在1—5之間, 為整數(shù)數(shù)值表示, 當(dāng)沒有評(píng)分信息時(shí)通常以0代替.

② 尋找鄰居用戶: 利用評(píng)分矩陣計(jì)算用戶間的相似度, 得出與目標(biāo)用戶最相似的K個(gè)最近鄰居.

③ 預(yù)測(cè)評(píng)分做出推薦: 根據(jù)鄰居用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分預(yù)測(cè)目標(biāo)用戶對(duì)該項(xiàng)目的評(píng)分值, 作出Top—N 項(xiàng)目推薦列表. 預(yù)測(cè)評(píng)分計(jì)算公式: 假設(shè)N(u)=（u1,u2,L,uk）為目標(biāo)用戶的最近鄰居集,則用戶u 對(duì)未評(píng)分項(xiàng)目i的預(yù)測(cè)評(píng)分Pu,j[8]可表示為:

其中,sim(u,v)表示目標(biāo)用戶u與用戶v的相似度,表示用戶v對(duì)項(xiàng)目i的實(shí)際評(píng)分,表示目標(biāo)用戶u在所有已評(píng)分項(xiàng)目中的平均評(píng)分,表示鄰居用戶v在所有已評(píng)分項(xiàng)目中的平均評(píng)分.

1.2 相似性計(jì)算方法

最常見的相似度計(jì)算方法有三種: 相關(guān)相似性(也稱Pearson系數(shù)相關(guān)性)、余弦相似性和修正的余弦相似性[9].

① 相關(guān)相似性: 在用戶共同評(píng)過分的項(xiàng)目集上,計(jì)算兩者的皮爾森相關(guān)系數(shù), 即為相似度. 其計(jì)算公式如下所示.

② 余弦相似性: 通過計(jì)算兩評(píng)分向量夾角的余弦值, 來度量用戶間的相似度, 夾角越小相似度越大.其計(jì)算公式如式(3).

③ 修正的余弦相似性: 每個(gè)人的評(píng)分標(biāo)準(zhǔn)和尺度不一樣, 比如說A非常喜歡某項(xiàng)目, 他會(huì)給出4分的評(píng)價(jià); 而B也非常喜歡該項(xiàng)目, 他會(huì)給出5分的評(píng)價(jià).從評(píng)分?jǐn)?shù)據(jù)來看,B比A更喜歡該項(xiàng)目, 但實(shí)際上A的喜好程度不亞于B, 這是因?yàn)閮烧叩脑u(píng)分標(biāo)準(zhǔn)不同.針對(duì)該問題, 提出修正的余弦相似性計(jì)算方法, 即將余弦相似性中的向量減去用戶平均評(píng)分向量后再計(jì)算夾角余弦值. 其計(jì)算公式如式(4)所示.

以上3個(gè)公式中Rui表示用戶u對(duì)項(xiàng)目i的評(píng)分值,表示用戶v對(duì)項(xiàng)目i的評(píng)分,表示用戶u的平均評(píng)分,表示用戶v的平均評(píng)分,表示用戶u和v共同評(píng)過分的項(xiàng)目集合,Iu、Iv分別表示用戶u、v的評(píng)分項(xiàng)目集,n是用戶u、v共同評(píng)過分的項(xiàng)目數(shù).

2 本文改進(jìn)的結(jié)合用戶聚類和項(xiàng)目類型的協(xié)同過濾算法

為了解決傳統(tǒng)算法中的數(shù)據(jù)稀疏問題, 本文提出了一種結(jié)合用戶聚類和項(xiàng)目類型的協(xié)同過濾算法, 即先利用項(xiàng)目類型相似性來填充稀疏的評(píng)分矩陣, 然后再用基于用戶聚類的協(xié)同過濾算法對(duì)新矩陣計(jì)算預(yù)測(cè)評(píng)分, 產(chǎn)生推薦.

2.1 算法步驟:

第一步: 填充稀疏的評(píng)分矩陣

① 計(jì)算項(xiàng)目相似度, 查找鄰居

把兩項(xiàng)目相同類型個(gè)數(shù)與兩項(xiàng)目具有的類型總數(shù)的比值作為項(xiàng)目相似度的計(jì)算方法. 若項(xiàng)目i具有的類型個(gè)數(shù)為n1, 項(xiàng)目j具有的類型數(shù)為n2, 項(xiàng)目i和j共同具有的類型數(shù)為n, 則兩者的相似度計(jì)算公式為:

設(shè)定閾值, 若項(xiàng)目相似度sim（i,j）大于該值, 即為目標(biāo)項(xiàng)目的鄰居.

② 根據(jù)目標(biāo)用戶對(duì)鄰居項(xiàng)目的評(píng)分信息預(yù)測(cè)目標(biāo)用戶對(duì)該項(xiàng)目的評(píng)分值, 將預(yù)測(cè)值填充稀疏的評(píng)分矩陣.

預(yù)測(cè)評(píng)分計(jì)算公式:

當(dāng)用戶u對(duì)鄰居項(xiàng)目j的評(píng)分為0, 且不為零時(shí),該公式的分子為:

當(dāng)用戶u對(duì)項(xiàng)目j的評(píng)分不為0時(shí), 則公式的分子為:

則用戶u對(duì)未評(píng)分項(xiàng)目i的預(yù)測(cè)評(píng)分為:

其中表示目標(biāo)用戶u的平均評(píng)分,表示用戶對(duì)項(xiàng)目j的平均評(píng)分,表示用戶u對(duì)項(xiàng)目j的評(píng)分值,I為項(xiàng)目i的鄰居集.

第二步: 對(duì)新矩陣進(jìn)行基于用戶聚類

協(xié)同過濾技術(shù)中經(jīng)常使用聚類算法來緩解數(shù)據(jù)稀疏性, 降低計(jì)算復(fù)雜度, 提高系統(tǒng)實(shí)時(shí)性. 聚類就是將一個(gè)龐大的群體按照某種特征分為若干個(gè)小群體,使群內(nèi)成員具有較高的相似度, 群與群之間差別較大.該算法適合大規(guī)模的數(shù)據(jù)集, 在電子商務(wù)網(wǎng)站中使用尤為普遍. 其中K-means聚類法由MacQueen[10]首先提出, 是目前使用最多的聚類算法. 該算法把小群體稱之為簇, 每個(gè)小群體內(nèi)的成員互為鄰居. 本文使用K-means聚類法先對(duì)新矩陣基于用戶聚類, 然后再尋找鄰居進(jìn)行預(yù)測(cè)推薦.

① K-means聚類步驟

a.先在數(shù)據(jù)集中隨機(jī)選擇出K個(gè)元素作為聚類中心; b.計(jì)算其余元素與聚類中心的距離, 并將該元素劃分到與其距離最小的簇中(一個(gè)聚類中心代表一個(gè)簇); c.取每個(gè)簇中所有元素的均值作為新的K個(gè)聚類中心; d.若聚類中心變化, 重復(fù)步驟b和c, 直至聚類中心不再變化或者收斂公式小于某一值.

其中距離計(jì)算方法有多種: 如明科夫斯基距離、曼哈頓距離、切比雪夫距離、歐式距離[11]. 本文使用最常用的歐氏距離法, 公式為:

公式中dij表示元素i和j之間的距離, 兩個(gè)元素集合分別為:

K-means聚類法使用距離平方和最小作為聚類收斂準(zhǔn)則, 表達(dá)式為:

表達(dá)式中p代表數(shù)據(jù)集中待分配的元素,m表示簇的中心點(diǎn),C表示簇.

② 尋找鄰居進(jìn)行預(yù)測(cè)推薦

a. 根據(jù)新的評(píng)分矩陣, 使用上述K-means聚類法將用戶分為若干簇.

b. 計(jì)算目標(biāo)用戶與每個(gè)簇中心的距離, 找到距離最小相似度最大的一個(gè)或若干個(gè)簇.

c. 在這些相近的簇中計(jì)算每個(gè)用戶與目標(biāo)用戶的相似性.

d. 根據(jù)Top-N或閾值法選出目標(biāo)用戶的n個(gè)鄰居用戶. Top-N法是將與目標(biāo)用戶相似度最大的前N個(gè)用戶作為鄰居; 閾值選擇法是把相似度大于某個(gè)閾值的用戶選為鄰居. 本文實(shí)驗(yàn)中采用Top-N法確定用戶鄰居.

e. 預(yù)測(cè)評(píng)分做出推薦. 根據(jù)用戶鄰居對(duì)目標(biāo)項(xiàng)目的評(píng)分信息, 加權(quán)平均預(yù)測(cè)目標(biāo)用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分值, 并根據(jù)預(yù)測(cè)結(jié)果做出推薦.

2.2 改進(jìn)算法的分析

本文算法首先根據(jù)項(xiàng)目本身類型, 找到鄰居項(xiàng)目,然后根據(jù)目標(biāo)用戶對(duì)鄰居項(xiàng)目的評(píng)分值, 計(jì)算其對(duì)未評(píng)分項(xiàng)目的評(píng)分值, 并將其填充原評(píng)分矩陣, 得到一個(gè)較為稠密的評(píng)分矩陣. 該法克服了數(shù)據(jù)稀疏性問題,還在新項(xiàng)目冷啟動(dòng)方面起到了一定的緩解作用. 傳統(tǒng)的基于項(xiàng)目的協(xié)同過濾算法依賴于評(píng)分值計(jì)算項(xiàng)目相似度, 評(píng)分值的稀疏性使得對(duì)同一項(xiàng)目評(píng)分的用戶數(shù)量很少, 影響著相似度計(jì)算精度; 而該算法采用新的公式計(jì)算項(xiàng)目相似度, 完全不受評(píng)分值的影響, 提高了相似度計(jì)算精度. 很多研究學(xué)者采用矩陣降維法、平均值填充等方法來填充稀疏的矩陣, 相對(duì)于這些方法來說, 該算法計(jì)算簡(jiǎn)單, 且充分考慮了項(xiàng)目類型信息, 有著較強(qiáng)的可行性. 然后, 對(duì)新矩陣操作時(shí)引入聚類技術(shù). 通過聚類, 大的用戶集合變?yōu)槿舾蓚€(gè)小的用戶集合, 在查找目標(biāo)用戶的鄰居時(shí), 不需要對(duì)每個(gè)用戶操作, 只需在與目標(biāo)用戶相近的一個(gè)或若干個(gè)簇中計(jì)算簇內(nèi)元素與目標(biāo)用戶的相似度. 并且, 聚類的過程可以離線完成, 在線只是查找鄰居進(jìn)行預(yù)測(cè)推薦,這就減少了計(jì)算復(fù)雜度, 節(jié)省了時(shí)間和空間, 提高了推薦實(shí)時(shí)性.

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

在協(xié)同技術(shù)研究中, Movielens數(shù)據(jù)集被廣泛使用,權(quán)威性較強(qiáng). 本文采用的數(shù)據(jù)是從該數(shù)據(jù)集隨機(jī)抽取的100, 000條評(píng)分記錄, 包含943個(gè)用戶對(duì)1682部電影的評(píng)估, 其中每個(gè)用戶都至少評(píng)論了20部影片. 電影共有19個(gè)類型,每部電影可以同時(shí)具有多種類型;用戶評(píng)分共有5個(gè)等級(jí)(1-5), 評(píng)分越高, 則用戶的喜好程度越大. 評(píng)分矩陣的稀疏度計(jì)算公式為: 評(píng)分矩陣中沒有評(píng)分值的個(gè)數(shù)/總的評(píng)分記錄數(shù); 則該數(shù)據(jù)集的稀疏性為1-100000/(943×1682)=0.93695. 該實(shí)驗(yàn)數(shù)據(jù)集包括訓(xùn)練集和測(cè)試集, 比例為4:1.

3.2 實(shí)驗(yàn)度量指標(biāo)

本實(shí)驗(yàn)中,采用MAE(平均絕對(duì)誤差)對(duì)算法的精度進(jìn)行評(píng)估.若預(yù)測(cè)評(píng)分集合為實(shí)際評(píng)分集合為則用戶u預(yù)測(cè)的MAE[12]表達(dá)式為:

MAE是根據(jù)預(yù)測(cè)評(píng)分值和實(shí)際評(píng)分值之間的偏離程度來計(jì)算預(yù)測(cè)精度的,MAE值越小, 與真實(shí)值相差越小, 預(yù)測(cè)精度越高, 推薦效果越好.

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

本文實(shí)驗(yàn)在Movielens數(shù)據(jù)集上進(jìn)行, 訓(xùn)練集和測(cè)試集為4:1, 共有5組數(shù)據(jù)進(jìn)行重復(fù)實(shí)驗(yàn), 最后將5組實(shí)驗(yàn)的均值作為最終的結(jié)果.

在填充稀疏的評(píng)分矩陣時(shí), 為了保證評(píng)分矩陣不被過分優(yōu)化, 影響推薦精度, 經(jīng)過多次試驗(yàn)選取項(xiàng)目相似度閾值為0.6, 將相似度大于該值的作為目標(biāo)項(xiàng)目的鄰居, 低于該值的舍棄. 這個(gè)閾值相當(dāng)于項(xiàng)目A有8個(gè)類型, 項(xiàng)目B有8個(gè)類型, 項(xiàng)目A和B共同具有的類型數(shù)是6個(gè), 只有2個(gè)類型不同, 可見大于該閾值的項(xiàng)目具有較高的相似性. 這也保證了預(yù)測(cè)值的可靠性,不至于出現(xiàn)填充過優(yōu), 推薦背離的現(xiàn)象.

本實(shí)驗(yàn)在查找用戶鄰居時(shí)引用了聚類技術(shù)來降低計(jì)算復(fù)雜度, 聚類數(shù)影響推薦效果, 根據(jù)已有研究學(xué)者的結(jié)論, 通常聚類數(shù)為7時(shí)具有較低的MAE值, 推薦效果較好[13]. 所以, 本實(shí)驗(yàn)中先使用聚類數(shù)7來進(jìn)行驗(yàn)證.

① 相似度比較

在聚類數(shù)為7的條件下, 通過5次實(shí)驗(yàn), 鄰居數(shù)從10到60, 分別對(duì)相關(guān)相似性、余弦相似性和修正的余弦相似性進(jìn)行實(shí)驗(yàn), 計(jì)算其MAE值, 結(jié)果取5次實(shí)驗(yàn)的平均值, 如下圖1所示.

圖1 三種相似度對(duì)比圖

由圖1可以觀察到, 隨著鄰居數(shù)的增加, 三條折線都呈下將趨勢(shì). 其中余弦相似性MAE值最高, 修正的余弦相似性次之, 相關(guān)相似性MAE值最低.MAE值越低, 與真實(shí)值越接近, 預(yù)測(cè)精度越高, 所以, 接下來的實(shí)驗(yàn)均采用相關(guān)相似性進(jìn)行用戶相似度的計(jì)算.

用戶相似度計(jì)算結(jié)果部分截圖如圖2所示, 從圖中可以看到相似度值范圍為-1到1. 其中0代表不相關(guān);負(fù)值表示負(fù)相關(guān), 即用戶興趣愛好相反; 正值表示正相關(guān), 且相似性大小跟數(shù)值大小成正比.

圖2 用戶相似度部分截圖

② 聚類數(shù)的選擇

為了驗(yàn)證聚類數(shù)7是比較理想的選擇, 我們?cè)谏鲜鼋Y(jié)論的條件下, 使用相關(guān)相似性, 分別對(duì)聚類數(shù)6、7、8進(jìn)行實(shí)驗(yàn), 用戶鄰居范圍選為10—60, 結(jié)論如圖3.3所示. 由實(shí)驗(yàn)結(jié)果可以得出, 同等條件下, 聚類數(shù)為7時(shí)MAE值最低, 即聚類數(shù)7是本實(shí)驗(yàn)最好的選擇,因此下面實(shí)驗(yàn)均采用聚類數(shù)7進(jìn)行.

圖3 聚類數(shù)的選擇對(duì)比圖

③ 本文算法與傳統(tǒng)的協(xié)同過濾算法結(jié)果對(duì)比

為了驗(yàn)證本文提出算法比傳統(tǒng)的協(xié)同過濾算法具有更好的推薦效果, 在①和②的結(jié)論下, 取聚類數(shù)7,相關(guān)相似性計(jì)算法, 鄰居數(shù)10—80, 分別對(duì)兩種算法進(jìn)行實(shí)驗(yàn), 畫出結(jié)果圖如下所示.

圖4 本文算法與傳統(tǒng)的協(xié)同過濾算法結(jié)果對(duì)比

由圖4可以看出, 本文算法MAE值較小, 表明本文算法具有優(yōu)越性, 能夠提高推薦質(zhì)量.

4 小結(jié)

本文首先介紹了協(xié)同過濾算法的實(shí)現(xiàn)過程和存在的不足, 然后針對(duì)稀疏性問題提出改進(jìn)的結(jié)合用戶聚類和項(xiàng)目類型的協(xié)同過濾算法, 并通過一系列實(shí)驗(yàn),證明了該算法的優(yōu)越性. 主要工作為: a、針對(duì)評(píng)分矩陣的稀疏性問題, 本文有效地利用項(xiàng)目類型相似性,根據(jù)用戶對(duì)鄰居項(xiàng)目的評(píng)分預(yù)測(cè)其對(duì)未評(píng)分項(xiàng)目的評(píng)分值, 并將其填充原矩陣, 得到較為稠密的新的用戶評(píng)分矩陣. b、傳統(tǒng)的協(xié)同過濾算法依賴于評(píng)分值計(jì)算項(xiàng)目相似度, 而評(píng)分矩陣的稀疏性嚴(yán)重影響著項(xiàng)目相似性計(jì)算的精度. 本文提出的改進(jìn)的算法, 有效地利用項(xiàng)目屬性信息, 采用新的項(xiàng)目相似度計(jì)算公式, 簡(jiǎn)單可行, 不依賴于評(píng)分值, 避免了“相似而不相同”現(xiàn)象的出現(xiàn), 且對(duì)新項(xiàng)目冷啟動(dòng)問題起到了一定的緩解作用. c、本文算法對(duì)新矩陣先聚類用戶, 然后在簇內(nèi)查找鄰居, 降低了近鄰查詢空間和計(jì)算復(fù)雜度, 提高了系統(tǒng)實(shí)時(shí)性. 最后在Movielens數(shù)據(jù)集上驗(yàn)證了該算法的優(yōu)越性.

1 藺豐奇,劉益.信息過載問題研究述評(píng).情報(bào)理論與實(shí)踐, 2007,30(5):710–714.

2 劉建國(guó),周濤,汪秉宏.個(gè)性化推薦系統(tǒng)的研究進(jìn)展.自然科學(xué)進(jìn)展,2009,19(1):1–15.

3 索琪,盧濤.基于關(guān)聯(lián)規(guī)則的電子商務(wù)推薦系統(tǒng)研究.哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào), 2005,21(2):50–53.

4 段瑋.基于協(xié)同過濾的個(gè)性化推薦算法研究[碩士學(xué)位論文].武漢:華中科技大學(xué),2009.

5 Liu DR, Shih YY. Hybrid approaches to product recommendation based on customer lifetime value and purchase preferences. The Journal of Systems and Software, 2005, 77 (2): 181–191.

6 曾小波,魏祖寬,金在弘.協(xié)同過濾系統(tǒng)的矩陣稀疏性問題的研究.計(jì)算機(jī)應(yīng)用,2010,30(4):1079–1082.

7 張亮.基于聚類技術(shù)的推薦算法研究[碩士學(xué)位論文].成都:電子科技大學(xué),2012.

8 Hyung JA. A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem. Information Sciences, 2008, 178(1): 37–51.

9 黃正.面向數(shù)據(jù)稀疏的協(xié)同過濾推薦算法研究與優(yōu)化[碩士學(xué)位論文].廣州:華南理工大學(xué),2012.

10 MacQueen J. Some methods for classification and analysis of multivariate observations. The 5th Berkeley Symposium on Mathematical Statistics and Probability. 2015, 1. 281–297.

11 黃洋.基于聚類和項(xiàng)目類別偏好的協(xié)同過濾推薦算法研究[碩士學(xué)位論文].杭州:浙江理工大學(xué),2013.

12 Papagelis M, Plexousakis D. Qualitative analysis of user-based and item-based prediction algorithms for recommendation agents. Engineering Application of Artificial Intelligence, 2005, 18(7): 781–789.

13 袁利.基于聚類的協(xié)同過濾個(gè)性化推薦算法研究[碩士學(xué)位論文].武漢:華中師范大學(xué),2014.

Collaborative Filtering Algorithm Combined with the User Clustering and Item Types

WANG Qiao, XIE Ying-Hua, YU Shi-Cai
(School of Information Science and Technology, Donghua University, Shanghai 201620, China)

In this paper, in order to solve the problem of data sparseness and improve the effect of recommendation, an improved collaborative filtering algorithm is put forward. Firstly, this algorithm calculates the item-types similarities through a new calculation method and the items whose similarities are greater than a certain threshold value will be considered as neighbors of the target-item. Secondly, the system predicts target-user’s score values for the target-item according to the scores for the neighbors of target-item, and the predicted values will be filled in the sparse score matrix. Finally, this algorithm clusters the new matrix (K-means clustering) based on the users, to predict target-user’s score values and make recommendations. The experimental results on the Movielens dataset show that this algorithm can effectively alleviate the data sparseness, reduce the computational complexity and improve recommendation accuracy.

data sparseness; collaborative filtering; item-types; K-means clustering; Movielens dataset

2016-03-14;收到修改稿時(shí)間:2016-04-27

10.15888/j.cnki.csa.005478