基于項(xiàng)目云的有序秩聚類在推薦系統(tǒng)中的應(yīng)用

杜宗宴,景英川

(太原理工大學(xué) 數(shù)學(xué)學(xué)院,山西 晉中 030600)

?

基于項(xiàng)目云的有序秩聚類在推薦系統(tǒng)中的應(yīng)用

杜宗宴,景英川

(太原理工大學(xué) 數(shù)學(xué)學(xué)院,山西 晉中 030600)

為進(jìn)一步提高推薦系統(tǒng)的推薦精度,提出一種新的基于項(xiàng)目云的有序秩聚類協(xié)同過(guò)濾推薦算法,其中包括三大步:數(shù)據(jù)處理,有序聚類，生成推薦。該方法不僅借助定性分析思想利用項(xiàng)目云有效地填充了缺失數(shù)據(jù),而且通過(guò)對(duì)項(xiàng)目分布的數(shù)字特征做排序、分割、聚類,在類內(nèi)產(chǎn)生“鄰居”,大大縮短了計(jì)算時(shí)間。通過(guò)在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)表明,在平均絕對(duì)誤差和預(yù)測(cè)精確度上,該算法確實(shí)優(yōu)于傳統(tǒng)推薦算法。

協(xié)同過(guò)濾;云模型;有序秩聚類;評(píng)分可靠度;推薦系統(tǒng)

近年來(lái),隨著科學(xué)技術(shù)的不斷發(fā)展,網(wǎng)絡(luò)數(shù)據(jù)與日俱增。特別是像Facebook, Amazon, Alibaba[1]等這樣的商務(wù)網(wǎng)站,其在線用戶對(duì)產(chǎn)品的評(píng)分?jǐn)?shù)據(jù)更是呈指數(shù)趨勢(shì)迅猛增加。因此,建立一個(gè)有效的個(gè)性化推薦系統(tǒng)對(duì)于商家推廣產(chǎn)品及用戶挖掘新品都是十分重要的。

目前,協(xié)同過(guò)濾是推薦系統(tǒng)中應(yīng)用最廣泛、最成功的一種算法,該算法最初由TYPESTRY提出,它認(rèn)為目標(biāo)用戶會(huì)與其相關(guān)用戶表現(xiàn)出相同偏好[2]。之后,GROUPLENS提出一個(gè)專門(mén)用于推送新聞、電影等的開(kāi)放自主協(xié)同過(guò)濾推薦系統(tǒng),認(rèn)為用戶會(huì)對(duì)相似的項(xiàng)目產(chǎn)生相同興趣[3]?；诖?為進(jìn)一步提高推薦精度,國(guó)內(nèi)外學(xué)者將協(xié)同過(guò)濾算法系統(tǒng)地分為兩大類:基于內(nèi)存和基于模型?；趦?nèi)存的協(xié)同過(guò)濾算法又包括User-based、Item-based協(xié)同過(guò)濾,其實(shí)質(zhì)都是通過(guò)對(duì)用戶-項(xiàng)目信息進(jìn)行統(tǒng)計(jì)分析,最終為目標(biāo)用戶(或目標(biāo)項(xiàng)目)挖掘一些具有歷史相似性行為的用戶(或項(xiàng)目)[4]。而基于模型的協(xié)同過(guò)濾則是依托統(tǒng)計(jì)或機(jī)器學(xué)習(xí)方法,利用歷史數(shù)據(jù)構(gòu)成用戶偏好模型進(jìn)行預(yù)測(cè)與推薦的方法,其中最典型的有基于關(guān)聯(lián)規(guī)則、貝葉斯網(wǎng)絡(luò)等的推薦算法[5]。

協(xié)同過(guò)濾技術(shù)雖已廣泛應(yīng)用于許多電子商務(wù)過(guò)程中,但與之相伴的用戶-項(xiàng)目評(píng)分矩陣的極端稀疏性、冷啟動(dòng)[6]等問(wèn)題也日益凸顯。HUANG et al提出了基于關(guān)聯(lián)規(guī)則的協(xié)同過(guò)濾算法[7];WENG et al深入探索用戶分類與評(píng)分偏好的內(nèi)部關(guān)系[8];BACKSTROM et al采用社交網(wǎng)絡(luò)模型進(jìn)行預(yù)測(cè)和推薦[9];CAI et al提出了基于典型度的協(xié)同過(guò)濾推薦算法[10]。這些方法雖然都不同程度的提高了推薦精度,但并未改善數(shù)據(jù)稀疏性。同時(shí),還有許多學(xué)者試圖從模糊學(xué)的角度來(lái)解除冷啟動(dòng)對(duì)預(yù)測(cè)結(jié)果的影響。張光衛(wèi)等引入了云模型相似性度量方法(LICM)[11];余志虎等提出了云模型數(shù)據(jù)填充算法來(lái)彌補(bǔ)數(shù)據(jù)缺失性[12];孫金剛等提出了基于項(xiàng)目屬性和云填充的協(xié)同推薦算法[13]。這些算法填充數(shù)據(jù)時(shí)均是采用均值填充、眾數(shù)填充或隨機(jī)填充等,并未充分考慮項(xiàng)目本身的性質(zhì)特征,因此預(yù)測(cè)精度也不盡如人意。

基于此,本文借鑒模糊聚類的思想,結(jié)合云模型[14]與有序秩聚類[15]的優(yōu)點(diǎn),提出了一種基于項(xiàng)目云的有序秩聚類協(xié)同過(guò)濾推薦算法(Ordered Rank Cluster in Collaborative Filtering Recommendation Based on Item Cloud, ICORC)。較之于傳統(tǒng)算法,該方法從以下三點(diǎn)進(jìn)行了改進(jìn)。首先,通過(guò)擬合項(xiàng)目的分布情況來(lái)填充原始數(shù)據(jù)矩陣,不僅彌補(bǔ)了原始數(shù)據(jù)矩陣的極端稀疏性,而且緩解了冷啟動(dòng)問(wèn)題引起的推薦不精確;其次,該算法依據(jù)項(xiàng)目分布的統(tǒng)計(jì)信息和評(píng)分概率分布情況恢復(fù)原始項(xiàng)目矩陣,較完整的還原了原始項(xiàng)目的數(shù)據(jù)特征;最后,該算法僅在相鄰用戶間進(jìn)行有序秩聚類為目標(biāo)項(xiàng)目產(chǎn)生最近鄰用戶,大大縮短了計(jì)算時(shí)間。據(jù)了解，目前尚未有研究將有序秩聚類與傳統(tǒng)推薦算法結(jié)合。

1 基于項(xiàng)目云的有序秩聚類協(xié)同過(guò)濾算法

協(xié)同過(guò)濾推薦算法的假設(shè)前提是用戶對(duì)于同類型的項(xiàng)目通常會(huì)表現(xiàn)出相似的興趣。由于用戶評(píng)分行為具有極大的不確定性、主觀性和模糊性,因此,本文從模糊角度出發(fā),提出了一種基于項(xiàng)目云的有序秩聚類協(xié)同過(guò)濾推薦算法。該方法的推薦機(jī)制如下。

1) 通過(guò)項(xiàng)目云數(shù)字特征C(E,En,H)來(lái)擬合每一個(gè)項(xiàng)目的分布情況；

2) 根據(jù)所擬合的項(xiàng)目分布來(lái)生成缺失數(shù)據(jù)以恢復(fù)原始稀疏評(píng)分陣；

3) 將所有的項(xiàng)目按其數(shù)字特征排序,并計(jì)算相鄰兩者間的相似度；

4) 根據(jù)相似度進(jìn)行有序秩聚類；

5) 對(duì)目標(biāo)用戶在類內(nèi)選擇“鄰居”并作出推薦和預(yù)測(cè)。

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

在協(xié)同過(guò)濾推薦系統(tǒng)中,用戶-項(xiàng)目評(píng)分矩陣可以用一個(gè)m×n階矩陣Am×n來(lái)表示,如表1所示。我們將m個(gè)用戶的集合記為U={U1,U2,…,Um},n個(gè)項(xiàng)目的集合記為I={I1,I2,…,In},用戶的評(píng)分集合記為X={xij, i=1,2,…,m; j=1,2,…,n}。其中,xij表示用戶Ui對(duì)項(xiàng)目Ij的評(píng)分值(“NA”表示缺失值)。通常,用戶對(duì)項(xiàng)目的評(píng)分都用1到5之間的整數(shù)值來(lái)表示,即{1,2,3,4,5},且不同分值表示用戶對(duì)項(xiàng)目的不同偏好程度,本文選取的實(shí)證數(shù)據(jù)集采用的正是此種評(píng)分機(jī)制。

表1 用戶-項(xiàng)目評(píng)分矩陣Am×n

1.1.1 數(shù)據(jù)缺失及分布假設(shè)

一般而言,用戶的個(gè)人偏好、周遭環(huán)境、事務(wù)本身等都會(huì)為其行為決策帶來(lái)極大的不確定性和隨機(jī)性?；诖?本文對(duì)數(shù)據(jù)的缺失機(jī)制作出假設(shè),認(rèn)為用戶對(duì)項(xiàng)目是否進(jìn)行評(píng)分是完全隨機(jī)的。換言之,用戶對(duì)某個(gè)項(xiàng)目是否評(píng)分是一個(gè)隨機(jī)事件,且評(píng)分與否并不代表用戶對(duì)該項(xiàng)目的喜惡。但是,用戶的評(píng)分高低卻可以直觀反映其對(duì)項(xiàng)目的偏好程度,即分值越大,表明用戶對(duì)該項(xiàng)目越感興趣;反之,分值越小,興趣越低。因此,本文假設(shè)數(shù)據(jù)的缺失機(jī)制為隨機(jī)缺失。

另外,由于在推薦系統(tǒng)的研究中多數(shù)采用的是用戶對(duì)一些項(xiàng)目的評(píng)分?jǐn)?shù)據(jù),然而在用戶未對(duì)項(xiàng)目作出評(píng)分之前,每個(gè)用戶給出1,2,3,4,5分的可能性是相同的。因此,這些評(píng)分值可看作是相互獨(dú)立的隨機(jī)變量,且事件1, 2, 3, 4, 5的發(fā)生可認(rèn)為是等概率事件。故從理論角度出發(fā),根據(jù)伯努利大數(shù)定律及中心極限定理,我們假設(shè)每一個(gè)項(xiàng)目的用戶評(píng)分均可近似看成是服從正態(tài)分布且相互獨(dú)立的隨機(jī)變量。

1.1.2 數(shù)據(jù)填充

研究資料表明,稀疏性是用戶-項(xiàng)目評(píng)分矩陣最明顯的問(wèn)題,傳統(tǒng)的協(xié)同過(guò)濾推薦算法,雖然采用了多種方法去克服這種稀疏性,但結(jié)果都不理想。原因在于,用戶打分存在主觀性、局限性。特別是當(dāng)用戶參與打分項(xiàng)目較少時(shí),其評(píng)分的可參考價(jià)值就會(huì)很小?；诖?本文提出了用戶評(píng)分可靠度如下,認(rèn)為參與評(píng)分項(xiàng)目越多的用戶,其評(píng)分結(jié)果越具代表性。

定義1(評(píng)分可靠度) 設(shè)用戶Ui對(duì)所有項(xiàng)目的評(píng)分向量為Xi=(xi1,xi2,…,xin),(xij表示用戶Ui對(duì)項(xiàng)目Ij的評(píng)分值,n為項(xiàng)目總數(shù)),記Xi=(xi1,xi2,…,xin)中非零項(xiàng)的個(gè)數(shù)為fi(i=1,2,…,m)(m為用戶總數(shù)),則用戶Ui的評(píng)分可靠度可用ωi來(lái)表示,如式(1),且滿足:

(1)

另一方面,現(xiàn)實(shí)生活中用戶對(duì)項(xiàng)目的評(píng)分行為本身就具有強(qiáng)烈的主觀性、模糊性以及不精確性。因此,我們引入云模型概念以及其基本數(shù)字特征:期望、熵、超熵[14],來(lái)描述項(xiàng)目的分布情況,稱之為項(xiàng)目云。其中,期望E為用戶對(duì)某項(xiàng)目的平均評(píng)分;熵En表示用戶對(duì)該項(xiàng)目評(píng)分的方差;超熵H是熵的熵。本文的研究中將依據(jù)項(xiàng)目云的數(shù)字特征,對(duì)比使用普通云發(fā)生器與加權(quán)云發(fā)生器來(lái)填充缺失值。其具體操作步驟如下:

1) 利用式(2),式(3)逆向云發(fā)生器(Backward Cloud Generator,BCG)來(lái)擬合每一個(gè)項(xiàng)目的分布情況,并通過(guò)云模型數(shù)字特征C(E,En,H)來(lái)表示。其中，ωi為用戶Ui的評(píng)分可靠度；Ej,En，j,Hj分別表示項(xiàng)目Ij的期望、熵、超熵；nj表示項(xiàng)目Ij的評(píng)分中非零值的個(gè)數(shù)；Sj表示項(xiàng)目Ij的標(biāo)準(zhǔn)差；Cj(Ej,En，j,Hj)為項(xiàng)目Ij的分布特征向量。則普通逆向云發(fā)生器計(jì)算見(jiàn)式(2),加權(quán)逆向云發(fā)生器計(jì)算見(jiàn)式(3):

(2)

(3)

2) 利用正向云發(fā)生器(ForwardCloudGenerator,FCG)生成每個(gè)項(xiàng)目對(duì)應(yīng)數(shù)量的隨機(jī)數(shù),并計(jì)算每個(gè)隨機(jī)數(shù)隸屬于該模型的隸屬度

3) 根據(jù)已評(píng)分值中各項(xiàng)目得分情況,對(duì)生成的隨機(jī)數(shù)進(jìn)行劃分和數(shù)值轉(zhuǎn)換,填充缺失值。設(shè)pkj為項(xiàng)目Ij評(píng)分為k(k=1,…,5)的理論概率,若p(k-1)j<μij≤pkj,則xij=k.

在整個(gè)數(shù)據(jù)填充過(guò)程中,我們假設(shè)數(shù)據(jù)缺失機(jī)制為完全缺失;在獲取項(xiàng)目分布時(shí)充分考慮到用戶評(píng)分可靠度,因此對(duì)比采用普通云發(fā)生器和加權(quán)云發(fā)生器分別獲得項(xiàng)目分布,生成缺失數(shù)據(jù),并通過(guò)隸屬度將生成的連續(xù)數(shù)值離散化,最終實(shí)現(xiàn)用戶-項(xiàng)目評(píng)分矩陣的稠密化。

1.2 有序秩聚類

1.2.1 相似度計(jì)算

在之前的討論中,我們已經(jīng)知道可以用項(xiàng)目云C(E,En,H)來(lái)反映項(xiàng)目的性質(zhì)特征。因此,處于相同位置、擁有相似形狀的云,其數(shù)字特征可能更相近,也更可能屬于同一類別?；诖?本文在計(jì)算項(xiàng)目相似度之前,首先將所有項(xiàng)目按一定的排序準(zhǔn)則重新排列,保證相鄰項(xiàng)目盡可能相似。值得注意的是,在項(xiàng)目云數(shù)字特征E、En、H中,E是最能代表用戶對(duì)項(xiàng)目的平均偏好程度,E值越高表明項(xiàng)目越受歡迎,故排序時(shí)優(yōu)先考慮E;其次排列En,因?yàn)镋n代表用戶對(duì)項(xiàng)目評(píng)分的離散程度,En值越小表明該項(xiàng)目評(píng)分值越集中;而H相當(dāng)于En的方差,反映的是用戶對(duì)項(xiàng)目評(píng)分的不確定性,H值越高表明該項(xiàng)目評(píng)分值越不穩(wěn)定,所以最后考慮H值。據(jù)此,本文定義排序準(zhǔn)則如下。

定義2(排序準(zhǔn)則) 設(shè)用戶-項(xiàng)目評(píng)分矩陣Am×n中有n個(gè)項(xiàng)目,Ck(Ek,En,k,Hk)表示第k個(gè)項(xiàng)目的分布特征,k=1,…,n。現(xiàn)將所有項(xiàng)目按Ek從小到大依次排列;當(dāng)Ei=Ej(i,j=1,…,n且i≠j)時(shí),將并列項(xiàng)目按En,k從小到大排列;同理,當(dāng)En,k相同時(shí),再將并列項(xiàng)目按Hk從小到大依次排列,本文將此視為排列準(zhǔn)則。

該準(zhǔn)則通過(guò)簡(jiǎn)單排序方法最大化的實(shí)現(xiàn)了同質(zhì)項(xiàng)目集中化、異質(zhì)項(xiàng)目分散化,完成了項(xiàng)目初次分類,為下一步的相似度計(jì)算奠定了基礎(chǔ)?；诖?提出本文相似度計(jì)算的具體方法:首先,對(duì)填充之后的稠密矩陣Am×n,采用式(2)重新計(jì)算各個(gè)項(xiàng)目的數(shù)字特征Ck(Ek,En，k,Hk),k=1,…,n;其次,按照排序準(zhǔn)則對(duì)所有項(xiàng)目Ck(Ek,En，k,Hk)重新排列,并將排序后的用戶-項(xiàng)目評(píng)分信息用有序云向量C=(C(1),C(2),…,C(n))來(lái)表示;最后,按照式(4)計(jì)算相鄰項(xiàng)目的云相似度,并將所有項(xiàng)目的相似性指標(biāo)記作向量S,如式(5)所示。

(4)

(5)

1.2.2 聚類

聚類分析的實(shí)質(zhì)就是使得類內(nèi)項(xiàng)目差異盡可能小,類間差異盡可能大的一種分類方法。因此,同一類別內(nèi)的項(xiàng)目就很可能擁有相同的性質(zhì),那么將目標(biāo)項(xiàng)目納入某一特定類別就可以為其產(chǎn)生相關(guān)推薦。目前,聚類技術(shù)已經(jīng)廣泛應(yīng)用于協(xié)同過(guò)濾推薦系統(tǒng)中,如K-Means,自組織映射(self-organizingmaps,SOM)等[16]。本文在云模型基礎(chǔ)上,采取有序秩聚類算法[15],并將其與K-Means結(jié)果進(jìn)行對(duì)比。其具體操作步驟如下:

1) 為項(xiàng)目間相似度進(jìn)行排秩。將式(5)得到的相似性指標(biāo)向量S中的所有相似度按照由小及大的原則排秩,即:相似度最小的項(xiàng)秩為1,相似度最大的項(xiàng)秩為(n-1),最終構(gòu)成相似性指標(biāo)的秩向量R=(r1,2,r2,3,…,rn-1,n),其中,ri,i+1表示第i個(gè)項(xiàng)目的秩。由此可知,秩越小,代表相鄰的這兩個(gè)項(xiàng)目之間差異性越大;秩越大,表明相鄰兩項(xiàng)目相似性越大。

2) 確定聚類數(shù)目k,進(jìn)行分類。假設(shè)我們想將所有樣本聚成5類,則就應(yīng)該將有序云C=(C(1),C(2),…,C(n))在其相似度秩為1,2,3,4(即rij=1,2,3,4)的地方同時(shí)斷開(kāi),這樣原始的樣本就被分成了5類。同理,如果我們需要將項(xiàng)目聚成k類,則應(yīng)該在rij=1,2,…,k-1的地方同時(shí)斷開(kāi),這樣相鄰斷點(diǎn)之間的項(xiàng)目就視作一類。

3) 計(jì)算每一類的中心。這個(gè)聚類的過(guò)程可以看作是云聚類,其中每一類別可看做是一個(gè)由成百上千個(gè)項(xiàng)目云滴組成的云團(tuán)。因此,每一類的中心完全可以用綜合云來(lái)代替。令Ct(Et,En，t,Ht)為第t類的綜合云數(shù)字特征,其中t=1,2,…,k,則第t類的中心可以用式(5)來(lái)表示。其中,Nt表示第t類中的項(xiàng)目個(gè)數(shù),Et,En，t,Ht分別表示第t類綜合項(xiàng)目云的期望、熵、超熵,Eti,En，ti,Hti分別表示第t類中第i個(gè)項(xiàng)目的期望、熵、超熵。

(6)

值得注意的是,上述步驟中對(duì)項(xiàng)目相似度進(jìn)行排序時(shí)可能會(huì)出現(xiàn)相同秩的情形,即:ri,i+1=ri+1,i+2…rj-1,j=rj,j+1(i,j=1,…,n-1且i≠j),此時(shí)無(wú)法確定該在i還是j處斷開(kāi)時(shí),就需要分別計(jì)算在i,i+1…j-1,j等處斷開(kāi)時(shí)的分類誤差[15],選擇使得分類誤差達(dá)到最小的劃分方法作為本文的最終分類決策。

1.3 推薦和預(yù)測(cè)機(jī)制

推薦和預(yù)測(cè)是協(xié)同過(guò)濾推薦系統(tǒng)的終極目標(biāo)。本文提出的方法區(qū)別于傳統(tǒng)算法,僅僅在目標(biāo)項(xiàng)目所屬的類內(nèi)尋找鄰居,進(jìn)行推薦。因此,我們首先要計(jì)算目標(biāo)項(xiàng)目與每一類別中心的距離,將其劃入合適的類中;下一步就可以進(jìn)行推薦了。同樣借鑒Top-N推薦算法的思想,但僅在目標(biāo)項(xiàng)目所屬的這一類別內(nèi)選擇與其相似度最為接近的N個(gè)鄰居進(jìn)行推薦。這一新的算法極大的降低了計(jì)算復(fù)雜度,縮短了程序運(yùn)行時(shí)間。

預(yù)測(cè)是根據(jù)最近鄰居的評(píng)分情況來(lái)估計(jì)目標(biāo)項(xiàng)目的可能得分的一個(gè)過(guò)程。眾所周知,目標(biāo)項(xiàng)目與其最近鄰居有極大的相似性,但是,即便如此,不同的鄰居其相似程度還是有所差異。因此,本文將相似度視為權(quán)重對(duì)未評(píng)分項(xiàng)目進(jìn)行加權(quán)預(yù)測(cè),其預(yù)測(cè)式(7)如下:

(7)

式中：rj表示目標(biāo)項(xiàng)目Ij的得分；nj為Ij的最近鄰居數(shù)；sim(i,j)表示目標(biāo)項(xiàng)目Ij與其第i個(gè)鄰居Ii的相似性;ri表示項(xiàng)目Ii的評(píng)分值。綜上所述,將本文提出的基于項(xiàng)目云的有序秩聚類協(xié)同過(guò)濾推薦算法(ICORC)大致分為三大步,數(shù)據(jù)處理,有序秩聚類和推薦與預(yù)測(cè)。其操作步驟可通過(guò)流程圖1來(lái)形象描述。

圖1 ICORC算法流程圖Fig.1 The flow chart of ICORC algorithm

2 實(shí)證分析

2.1 實(shí)驗(yàn)設(shè)計(jì)

為了評(píng)估本文提出的方法ICORC的有效性,我們將采用R語(yǔ)言軟件在MovieLens數(shù)據(jù)集(http:∥movielens.umn.edu)上進(jìn)行試驗(yàn)。該數(shù)據(jù)集要求每個(gè)用戶評(píng)分項(xiàng)目數(shù)至少要20條,其分值從1分到5分不等,分別代表用戶對(duì)項(xiàng)目不同程度的偏好,“1”表示很不喜歡,“5”表示特別喜歡,稀疏度為93.69%。文中將采用EMA(meanabsoluteerror)和P(Precision)來(lái)分別評(píng)估預(yù)測(cè)結(jié)果。EMA為平均絕對(duì)誤差,反映的是樣本實(shí)際值與預(yù)測(cè)值之間的絕對(duì)偏差,因此EMA值越小越好,如式(8)所示,其中pi,xi分別表示第i個(gè)樣本的預(yù)測(cè)值與實(shí)際觀測(cè)值,n為總的樣本數(shù)。P為預(yù)測(cè)精確度,如式(9),其中TP(TruePositive)表示預(yù)測(cè)為推薦項(xiàng)目且實(shí)際也是推薦項(xiàng)目的個(gè)數(shù);FP(FalsePositive)表示預(yù)測(cè)為推薦項(xiàng)目,但實(shí)際為非推薦項(xiàng)目的個(gè)數(shù)。因此,P值反映的是預(yù)測(cè)結(jié)果中能正確推薦的比例,其值越大表明推薦精確度越高,推薦效果越好。

(8)

(9)

在本研究中,將呈現(xiàn)通過(guò)普通填充由基于云模型的有序秩聚類協(xié)同過(guò)濾算法(ICORC)獲得的結(jié)果,以及通過(guò)加權(quán)填充算法(WICORC)得到的結(jié)果,并將其與兩個(gè)經(jīng)典的協(xié)同過(guò)濾算法:基于K-Means聚類的協(xié)同過(guò)濾算法(KMCF)和基于云模型相似度的協(xié)同過(guò)濾算法(LICM)進(jìn)行比較。最終逐一解答以下問(wèn)題:聚類數(shù)K對(duì)推薦質(zhì)量有何影響，最近鄰居數(shù)N對(duì)推薦質(zhì)量有何影響，ICORC在處理數(shù)據(jù)稀疏性問(wèn)題方面是否有效，ICORC是否真的優(yōu)于傳統(tǒng)的CF算法(KMCF,LICM).

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

圖2 聚類數(shù)K對(duì)推薦結(jié)果的影響Fig.2 The influence of cluster number K for recommend result

通過(guò)MovieLensdataset實(shí)驗(yàn)結(jié)果可知,見(jiàn)圖2,隨著聚類數(shù)目的增加,EMA值呈大幅度降低的趨勢(shì),當(dāng)聚類數(shù)K=15時(shí),EMA值已經(jīng)很小,之后EMA值呈現(xiàn)較為平緩的趨勢(shì)。由圖3可以看出,隨著最近鄰數(shù)目的增加,EMA的趨勢(shì)變化較為平緩,且當(dāng)最近鄰居數(shù)目N>15時(shí),EMA值基本不再變化。因此,當(dāng)聚類數(shù)K=15,最近鄰居數(shù)N=15時(shí),EMA值降到穩(wěn)定狀態(tài),推薦結(jié)果達(dá)到最優(yōu)。

圖3 鄰居數(shù)N對(duì)推薦結(jié)果的影響Fig.3 The influence of neighbor number N for recommend result

圖4 鄰居數(shù)N對(duì)預(yù)測(cè)精確度的影響Fig.4 The influence of neighbor number N for precision

對(duì)比四種算法(KMCF,LICM,ICORC,WICORC),綜合圖2-圖4可以看出,無(wú)論聚類數(shù)目,最近鄰居數(shù)如何變化,ICORC都具有最小的EMA和最大的P值。因此認(rèn)為ICORC推薦效果更優(yōu)。且就P值而言,ICORC與WICORC算法都優(yōu)于傳統(tǒng)的LICM和KMCF算法,原因就在于ICORC算法綜合考慮了用戶評(píng)分隨機(jī)性、模糊性等特點(diǎn),最大限度地挖掘用戶評(píng)分信息,獲取每個(gè)項(xiàng)目的近似分布,進(jìn)而去填充原始稀疏矩陣,既保留了原始矩陣的評(píng)分特征,又緩解了推薦中的冷啟動(dòng)問(wèn)題,因此ICORC算法在數(shù)據(jù)稀疏性問(wèn)題上比傳統(tǒng)的LICM和KMCF算法有更好的預(yù)測(cè)效果。

3 總結(jié)及發(fā)展前景

筆者從一個(gè)全新的視角出發(fā),借鑒定性分析與有序秩聚類的思想,提出了一種新型的基于項(xiàng)目云的有序秩聚類的協(xié)同過(guò)濾推薦算法,并將這一算法同傳統(tǒng)的KMCF和LICM算法在MovieLensdata集上做比較。實(shí)驗(yàn)表明,較于傳統(tǒng)的協(xié)同過(guò)濾算法該方法有兩大優(yōu)勢(shì)。

1) 該算法從定性分析的層面考慮,由于不同的用戶其評(píng)分偏好在某種程度上一定存在差異性,因此引入項(xiàng)目云來(lái)填充缺失數(shù)據(jù),不僅能較好地解釋用戶在選擇項(xiàng)目時(shí)的隨機(jī)性,以及用戶評(píng)分的不確定性、模糊性,而且能克服數(shù)據(jù)的稀疏性,同時(shí)高度還原原始評(píng)分矩陣中所含信息的特征。

2) 該算法依據(jù)每個(gè)項(xiàng)目評(píng)分值的分布特征進(jìn)行有序秩聚類,并在類內(nèi)尋找項(xiàng)目“鄰居”,區(qū)別于傳統(tǒng)的計(jì)算所有項(xiàng)目的相似度的聚類算法,該算法僅需要計(jì)算擁有相似特征的相鄰項(xiàng)目間的相似性,其計(jì)算時(shí)間復(fù)雜度為o(n),而傳統(tǒng)算法計(jì)算相似度的時(shí)間復(fù)雜度為o(n2)。因此,該算法不僅能夠緩解數(shù)據(jù)稀疏性以及冷啟動(dòng)問(wèn)題,提高推薦精度,而且能大量節(jié)省時(shí)間。尤其是對(duì)于高維大數(shù)據(jù),ICORC算法的優(yōu)勢(shì)就更為明顯。

在本文的研究中,盡管我們對(duì)原始數(shù)據(jù)的稀疏性進(jìn)行了很大的改善,而且在某種程度上極大的減少了EMA,提高了P值,但依然有許多問(wèn)題亟需解決。首先,本文沒(méi)有充分考慮到用戶之間的潛在關(guān)系;其次,在推薦過(guò)程中,本文也沒(méi)有考慮推薦數(shù)目對(duì)推薦精度的影響,從理論上來(lái)講,應(yīng)該是推薦數(shù)目越多,推薦精度越高。因此,未來(lái)我們可以考慮從這幾個(gè)方向去做深入研究:分析影響用戶評(píng)分的因素;或者探索用戶評(píng)分值的真實(shí)分布。另外,進(jìn)一步提高協(xié)同過(guò)濾推薦系統(tǒng)的推薦精度以及計(jì)算速度仍是我們需要努力的方向。

[1]XURZ,WANGSQ,ZHENGXW,etal.Distributedcollaborativefilteringwithsingularratingforlargescalerecommendation[J].TheJournalofSystemsandSoftware,2014,(95):231-241.

[2]GOLDBERGD,NICHOLSD,OKIBM,etal.Usingcollaborativefilteringtoweaveaninformationtypestry[J].CommunACM,1992,35(12):61-70.

[3]RENSICKP,IACOVOUN,SUCHAKM,etal.GroupLens:anopenarchitectureforcollaborativefilteringofnetnews[C]∥ACM.Proceedingsofthe1994ACMConferenceonComputerSupportedCooperativeWork(CSCW)UnitedStates：NorthCarolina,1994:175-186.

[4]SARWARB,KARYPISG,KONSTANJ,etal.Item-basedcollaborativefilteringrecommendationalgorithms[C].Proceedingsofthe10thinternationalconferenceonWorldWideWeb.HongKong:ACM,2001:285-295.

[5]CECHINELC,SICILIAM,SALVADORSA,etal.Evaluatingcollaborativefilteringrecommendationsinsidelargelearningobjectrepositorise[J].InformationProcessingandManagement,2013(49):34-50.

[6] 孫小華.協(xié)同過(guò)濾系統(tǒng)的稀疏性與冷啟動(dòng)問(wèn)題研究[D].杭州:浙江大學(xué),2005.

[7]HUANGZ,CHENH,ZENGD.Applyingassociativeretrievaltechniquestoalleviatethesparsityproblemincollaborativefiltering[J].ACMTransInformationSystems,2004,22(1):116-142.

[8]WENGLT,XUY,LIY,etal.Exploitingitemtaxonomyforsolvingcold-startprobleminrecommendationmaking[C].Proceedingsofthe20thIEEEInternationalConferenceonToolswithArtificalIntelligence,Dayton,USA,2008:113-120.

[9]BACKSTROML,LESKOVECJ.Supervisedrandomwalks:predictingandrecommendinglinksinsocialnetworks[J].ComputerScience,2011(11):635-644.

[10]CAIY,LEUNGHF,LIQ,etal.Typicality-basedcollaborativefilteringrecommendation[J].IEEETrans.KnowledgeandDataEng,2014,26(3):766-779.

[11] 張光衛(wèi),李德毅,李鵬.基于云模型的協(xié)同過(guò)濾推薦算法[J].軟件學(xué)報(bào),2007,18(10):2403-2411.

[12] 余志虎,戚玉峰.一種基于云模型數(shù)據(jù)填充的算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2010,20(12):34-37.

[13] 孫金剛,艾麗蓉.基于項(xiàng)目屬性和云填充的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用,2012，32(3):658-660.

[14] 王國(guó)胤,李德毅,姚一豫，等.云模型與粒計(jì)算[M].科學(xué)出版社，2012(inChina).

[15] 朱建平,方匡南.有序秩聚類及對(duì)地震活躍期的分析[J].統(tǒng)計(jì)研究,2009，26(1):83-87.

[16]TSAICF,HUNGC.Clusterensemblesincollaborativefilteringrecommendation[J].AppliedSoftComputing,2012(12):1417-1425.

(編輯：朱 倩)

Application of Ordered Rank Cluster in Recommendation Systems Based on Item Cloud

DU Zongyan,JING Yingchuan

(College of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi 030600, China)

In order to further improve recommender accuracy, in this paper we propose a novel ordered rank cluster in collaborative filtering based on the item cloud (ICORC) method, which includes three steps: data processing, ordered rank clustering, and recommendation generating. This method has two advantages. One is that it can tackle the data sparsity problem by filling in missing data using the item cloud. Another distinct feature is that it can save time and obtain more accuracy through finding “neighbors” of items among the clusters, which are formed by sorting, partition and clustering for the numerical characteristics of item distribution. To the best of our knowledge, there has been no prior work on investigating CF recommendation by combining ordered rank cluster.We conducted this experiment on the MovieLens datasets and found that ICORC is superior to other collaborative filtering (CF) algorithms on the mean absolute error and Precision.

collaborative filtering;cloud model;ordered rank cluster;rating reliability;recommender system

1007-9432(2016)05-0673-07

2015-10-06

國(guó)家自然科學(xué)基金資助項(xiàng)目：高維數(shù)據(jù)變量間非線性交互作用的研究(11571009)

杜宗宴(1990- )，女，山西孝義人，碩士，主要從事數(shù)理統(tǒng)計(jì)及數(shù)據(jù)挖掘方向的研究，(E-mail)duzongyan908@126.com

景英川，副教授，主要從事數(shù)理統(tǒng)計(jì)及數(shù)據(jù)挖掘方向的研究，(E-mail)shyjyc1970@163.com,

F224;F713.36

A

10.16355/j.cnki.issn1007-9432tyut.2016.05.021