基于K-means聚類與張量分解的社會(huì)化標(biāo)簽推薦系統(tǒng)研究

孫玲芳, 李爍朋

(江蘇科技大學(xué) 經(jīng)濟(jì)管理學(xué)院, 江蘇 鎮(zhèn)江 212003)

隨著Web 2.0技術(shù)的發(fā)展,含有社會(huì)化標(biāo)簽(social tag)數(shù)據(jù)的大眾標(biāo)注(folksonomy)網(wǎng)站在電子商務(wù)領(lǐng)域蓬勃發(fā)展.為了給用戶提供有效的項(xiàng)目信息,多種推薦技術(shù)被廣泛運(yùn)用在電子商務(wù)領(lǐng)域.而在大眾標(biāo)注網(wǎng)站中,用戶通常會(huì)對自己感興趣的對象有一個(gè)標(biāo)注行為,所產(chǎn)生的標(biāo)簽(tag)數(shù)據(jù)會(huì)對推薦系統(tǒng)的推薦效果產(chǎn)生較大影響[1].而傳統(tǒng)的推薦方法,例如協(xié)同過濾系統(tǒng)通過計(jì)算用戶之間或是項(xiàng)目之間的相似度來完成推薦過程,若在大眾標(biāo)注網(wǎng)站中忽略了大量的標(biāo)簽數(shù)據(jù),則評價(jià)矩陣的數(shù)據(jù)稀疏性問題依然存在,并且會(huì)影響到推薦精度[2].提高推薦精度的傳統(tǒng)方法之一是利用矩陣奇異值分解(singular value decomposition， SVD),對數(shù)據(jù)矩陣進(jìn)行分解后將無用數(shù)據(jù)去除，達(dá)到降噪和降低稀疏性的目的,但是對含有標(biāo)簽數(shù)據(jù)集的多元數(shù)據(jù)矩陣改進(jìn)效果不佳．奇異值分解對二維矩陣稀疏問題具有良好處理特性，在此基礎(chǔ)上,文中首先對標(biāo)簽數(shù)據(jù)進(jìn)行K-means聚類,然后以用戶(user)、標(biāo)簽(tag)、項(xiàng)目(item)數(shù)據(jù)建立多維張量模型,運(yùn)用K-means HOSVD(high order singular value decomposition)對模型進(jìn)行分解運(yùn)算,兩個(gè)算法皆是保證數(shù)據(jù)的非稀疏性.以書簽標(biāo)注網(wǎng)站Decilous.com的數(shù)據(jù)為測試集對該模型的推薦效果進(jìn)行檢驗(yàn).

1 大眾標(biāo)注概念

1.1 大眾標(biāo)注和標(biāo)簽

SNS(social network service)網(wǎng)站的出現(xiàn)給用戶之間的交互過程提供了一個(gè)嶄新平臺(tái),網(wǎng)絡(luò)社區(qū)由此建立,大眾標(biāo)注的概念也因此而產(chǎn)生.大眾標(biāo)注是眾多信息用戶根據(jù)自己的需求,選擇合適的網(wǎng)絡(luò)信息資源,并根據(jù)自己的認(rèn)知水平,確定與之相匹配的社會(huì)化標(biāo)簽進(jìn)行標(biāo)注的過程[3].用戶根據(jù)自身的理解與喜好程度，對自身感興趣的網(wǎng)絡(luò)資源添加“標(biāo)簽”,便會(huì)對其他用戶共同所感興趣的對象提供一種推薦與參考.大眾標(biāo)注研究最早起源于國外學(xué)者對Web 2.0系統(tǒng)的研究,其基本要素包括：含有標(biāo)簽信息的元素、眾多用戶自下而上對資源進(jìn)行標(biāo)注與共享的過程,以及以人為本提供組建網(wǎng)絡(luò)社區(qū)與構(gòu)建關(guān)系網(wǎng)絡(luò)等服務(wù)[4].

標(biāo)簽的范圍也隨著大眾標(biāo)注網(wǎng)站的發(fā)展而不斷擴(kuò)大,從對書籍共享網(wǎng)站進(jìn)行標(biāo)注所形成的“書簽”,到音樂、照片、視頻、博客網(wǎng)站中各種信息資源形成的一種標(biāo)注信息[5].國外學(xué)者認(rèn)為,標(biāo)簽是一種以自然語言形式出現(xiàn)的關(guān)鍵詞元數(shù)據(jù),概念、類別、分面與實(shí)體都可以成為標(biāo)簽的要素[6].由于“標(biāo)簽”的表述使用正常語言而非抽象的代碼,因此用戶之間通過標(biāo)簽可以輕易挖掘出與自身喜好相近的其他用戶和資源,從而為構(gòu)建網(wǎng)絡(luò)社區(qū)提供了基本群體要素.

1.2 標(biāo)簽數(shù)據(jù)的特點(diǎn)

大眾標(biāo)注網(wǎng)站不同于其他電子商務(wù)網(wǎng)站,擁有標(biāo)注數(shù)據(jù)的社區(qū)網(wǎng)站通常含有大量的語義分析元素.此時(shí)，用戶把在電子商務(wù)平臺(tái)中對商品或?qū)ο筮M(jìn)行評分的過程,改為對自身感興趣的項(xiàng)目進(jìn)行標(biāo)注的行為[7].傳統(tǒng)算法,如協(xié)同過濾推薦系統(tǒng)是基于分析近鄰用戶之間的相似偏好來過濾信息,達(dá)到向其他用戶推薦的目的;但是標(biāo)簽不是確定的評分?jǐn)?shù)值而是含有大量語義信息的文本數(shù)據(jù),若仍采用傳統(tǒng)的推薦方法，雖也有一定的推薦效果,但推薦精度會(huì)隨著矩陣數(shù)據(jù)稀疏性的增加而下降.兩者數(shù)據(jù)類型之間的差異如表1，2.

Movie Lens是一個(gè)在線的電影評分網(wǎng)站;Last FM是基于用戶標(biāo)簽的音樂網(wǎng)站,用戶對自己喜愛的歌手添加標(biāo)簽，并與在線的其他用戶進(jìn)行共享.

表1 數(shù)據(jù)來源為Movie Lens網(wǎng)站

表2 數(shù)據(jù)來源為Last FM網(wǎng)站

從表中數(shù)據(jù)可以看出兩者的差別之處,大眾標(biāo)注網(wǎng)站包含更多的語義信息,因此兩者的推薦系統(tǒng)模型也有所差別.如何在大眾標(biāo)注網(wǎng)站的海量信息中進(jìn)行有效推薦,以及如何有效解決數(shù)據(jù)矩陣的稀疏性問題,是當(dāng)前電子商務(wù)推薦系統(tǒng)研究的熱點(diǎn)問題.

2 電子商務(wù)推薦系統(tǒng)算法的研究

Resnick & Varian于1997年首次定義了電子商務(wù)推薦系統(tǒng)[8],該系統(tǒng)利用網(wǎng)站平臺(tái)向客戶推薦相關(guān)的商品信息，以幫助客戶完成購買過程.推薦系統(tǒng)通過分析相關(guān)數(shù)據(jù)得到顧客的購買偏好,然后針對性地進(jìn)行商品推薦.傳統(tǒng)的個(gè)性化推薦技術(shù)主要有以下3種：

1) 基于規(guī)則推薦.該算法對不同情況下如何提供不同的服務(wù)定義了許多規(guī)則,系統(tǒng)利用這些規(guī)則來產(chǎn)生推薦,因此推薦的質(zhì)量依賴于規(guī)則的質(zhì)量和數(shù)量.但是該方法所推薦的商品一定是曾經(jīng)被其他用戶瀏覽過的,所以新的商品在任意客戶瀏覽之前便無法獲得推薦,導(dǎo)致該算法個(gè)性化程度較低.規(guī)則數(shù)量隨著商品數(shù)量的添加而增多,規(guī)則質(zhì)量難以保障,系統(tǒng)也趨于繁雜.

2) 內(nèi)容過濾推薦.該算法通過相關(guān)特征的屬性來定義商品或項(xiàng)目,系統(tǒng)基于用戶評價(jià)商品的特征學(xué)習(xí)用戶興趣,依據(jù)用戶資料與待預(yù)測商品的匹配程度進(jìn)行推薦.基于內(nèi)容的推薦算法也存在缺點(diǎn):模型有效性和過度特征化問題使得模型當(dāng)中信息之間的關(guān)聯(lián)性無法很好體現(xiàn),導(dǎo)致系統(tǒng)無法識(shí)別客戶新發(fā)現(xiàn)的興趣資源;自主進(jìn)化能力較差.若新的商品數(shù)量迅速增加,系統(tǒng)不能對這樣的新特征產(chǎn)生進(jìn)化能力．

3) 協(xié)同過濾推薦.采用最近鄰技術(shù)利用客戶的歷史偏好信息計(jì)算用戶之間的距離.然后利用目標(biāo)客戶的最近鄰居對商品評價(jià)的加權(quán)平均值來預(yù)測他對特定項(xiàng)(商品)的偏好程度.系統(tǒng)根據(jù)這一偏好程度來對目標(biāo)客戶進(jìn)行推薦[9].協(xié)同過濾推薦主要有3個(gè)步驟:① 評分矩陣，根據(jù)系統(tǒng)中用戶和評分的數(shù)據(jù)可以建立一個(gè)M×N階矩陣R來表示;② 相似度計(jì)算，相似度計(jì)算用來發(fā)現(xiàn)最近鄰居用戶,一般有余弦相似度和相關(guān)相似性2種方法;③ 最后是top-n推薦生成.

3 HOSVD模型

高階奇異值分解：HOSVD是在矩陣奇異值分解SVD的概念上的延伸.對于任意N階張量Y∈RI1×I2×IN,其中ai1, i2,iN為張量Y中的元素，定義張量Y的n-模(n-mode)分解矩陣A,把張量Y沿第n模式展開的矩陣A的操作稱為張量展開[10].

令U∈RJn×In,則A可表示為Y×nU.A的結(jié)果是一個(gè)(I1×I2×…×In-1×Jn×In+1×…×IN)階張量,張量Y與矩陣U的第n模式的Tucker積可由下列公式得到：

(1)

在大眾標(biāo)注網(wǎng)站中,數(shù)據(jù)結(jié)構(gòu)為用戶、標(biāo)簽和項(xiàng)目的三元數(shù)據(jù),所以取n∈ {1, 2, 3},則展開矩陣A分別為A1∈RI1×I2I3,A2∈RI2×I1I3,A3∈RI3×I1I2.

當(dāng)張量為2階時(shí),對2維矩陣進(jìn)行SVD分解,可得

F=S×1U(1)×2U(2)

(2)

Y′=S×1U(1)×2U(2)×3U(3)

(3)

式中：U(1)，U(2)和U(3)均是對分解矩陣A1，A2和A3在列空間向量上的正交化處理,包含1-模、2-模和3-模的奇異值向量；S是具有完整正交性的核心張量,控制各子空間矩陣間的相互作用,類似于SVD中的奇異值矩陣,但不是對角結(jié)構(gòu)；Y′是對張量Y的重新構(gòu)建,包含了新的數(shù)據(jù)信息.

4 基于K-means HOSVD的推薦模型設(shè)計(jì)

4.1 K-means聚類

K-means聚類是一種經(jīng)典的距離聚類方法，在很多領(lǐng)域得到廣泛運(yùn)用[11].文中根據(jù)大眾標(biāo)注網(wǎng)站數(shù)據(jù)中所提供的標(biāo)簽和項(xiàng)目之間的權(quán)重值來建立項(xiàng)目—標(biāo)簽權(quán)重矩陣Wm×n(表3)，其中M行代表M個(gè)項(xiàng)目,N列代表N個(gè)標(biāo)簽,Wi,j表示項(xiàng)目Ii對標(biāo)簽Tj的標(biāo)簽權(quán)重.對該矩陣進(jìn)行K-means聚類，將眾多分散的標(biāo)簽和項(xiàng)目進(jìn)行初步聚類得到相對密集的數(shù)據(jù)集,使數(shù)據(jù)具有初始的聚合性.

表3 項(xiàng)目—標(biāo)簽權(quán)重矩陣Wm×n

基于項(xiàng)目—標(biāo)簽矩陣Wm×n的K-means聚類過程如下:

輸入為項(xiàng)目聚類的數(shù)目K，用戶-標(biāo)簽矩陣Wm×n

輸出:K個(gè)聚類.

方法:

1) 從矩陣Wm×n中檢索得到全部M個(gè)項(xiàng)目數(shù),記為I={i1,i2,…,in};

2) 從矩陣Wm×n中檢索得到全部N個(gè)標(biāo)簽項(xiàng),記為T={t1,t2,…,tn};

3) 隨機(jī)選擇K個(gè)項(xiàng)目作為初始聚類中心,記為集合Q={q1,q2,…,qk};

4)K個(gè)聚類P1,P2,…,Pk均初始化為空,各聚類與其聚類中心相對應(yīng);

5) 計(jì)算項(xiàng)目ii與各個(gè)聚類中心qj之間的歐氏距離如下式：

(4)

式中：Tij表示項(xiàng)目ii與作為聚類中心的項(xiàng)目qj共同標(biāo)注過的標(biāo)簽集合,Wii和Wqj分別是項(xiàng)目ii和qj的標(biāo)簽權(quán)重；

6) 若D(ii,qj)=max {D(ii,q1),D(ii,q2), …,D(ii,qk)},則項(xiàng)目ii屬于聚類Pj;

7) 計(jì)算相同聚類中所有項(xiàng)目的標(biāo)簽權(quán)重平均值,生成新的聚類中心;

8) 若聚類中心不再發(fā)生改變,則退出;否則轉(zhuǎn)到第5)步重新計(jì)算.

初始聚類完成后,將聚類數(shù)據(jù)輸入數(shù)據(jù)庫建立聚類信息表.通過對項(xiàng)目的初始聚類,可以將擁有相似標(biāo)簽的項(xiàng)目分配到同一聚類中,使得同一聚類中的項(xiàng)目相似性盡可能高.同時(shí),通過參照聚類后的標(biāo)簽—權(quán)重?cái)?shù)據(jù)可以確定項(xiàng)目所對應(yīng)的標(biāo)簽,再根據(jù)項(xiàng)目—標(biāo)簽定位出用戶,此時(shí)用戶在一定程度上也完成了初始聚類.

4.2 張量分解模型

根據(jù)先前的聚類數(shù)據(jù),將K組數(shù)據(jù)集中進(jìn)行推薦,通過用戶、標(biāo)簽和項(xiàng)目數(shù)據(jù)建立一個(gè)初始張量Bu×t×i[12].為了更好地表達(dá)模型概念,隨機(jī)從聚類數(shù)據(jù)集中選取4組數(shù)據(jù)為例進(jìn)行建模(表4).

表4 用戶標(biāo)注示例

注：數(shù)據(jù)來源為Delicious.com

表4中共有3個(gè)用戶,對2個(gè)項(xiàng)目用3個(gè)標(biāo)簽做出了4次標(biāo)注．設(shè)產(chǎn)生標(biāo)注的權(quán)重為1,沒有產(chǎn)生標(biāo)注的權(quán)重為0．則初始張量B如圖1.

圖1 張量B的圖例

B中的各個(gè)元素均為每個(gè)用戶用標(biāo)簽標(biāo)注項(xiàng)目后產(chǎn)生的權(quán)重．得到初始張量B后,將其沿第1,2,3模式展開得到3個(gè)展開矩陣A1,A2和A3如下：

S=Y×1(U(1))T×2(U(2))T×3(U(3))T

(5)

將核心張量S帶入公式(3),計(jì)算重新構(gòu)建的張量Y′(圖2).

圖2 新的張量Y′圖例

在{U2,I2,T2}以及{U3,I1,T3}項(xiàng)的值由原來的0變?yōu)?.7,因此新的推薦生成.

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

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

文中采用Decilious.com網(wǎng)站的標(biāo)簽數(shù)據(jù)進(jìn)行分析.該網(wǎng)站是在線網(wǎng)頁書簽網(wǎng)站,用戶可以對各種網(wǎng)頁鏈接進(jìn)行標(biāo)注是該網(wǎng)站的一大特點(diǎn).該數(shù)據(jù)包含165個(gè)用戶,368個(gè)書簽以及760個(gè)標(biāo)簽.本實(shí)驗(yàn)將數(shù)據(jù)集劃分為訓(xùn)練集和測試集,其中75%作為訓(xùn)練集,25%作為測試集.

5.2 評估標(biāo)準(zhǔn)

推薦系統(tǒng)的準(zhǔn)確性和有效性一般用精確度(Precision,P)、召回率(Recall,R)來測量,精確度的定義如下：

P=(命中的數(shù)目)/(推薦的數(shù)目)
R=(命中的數(shù)目)/(測試集的大小)

為避免精確度和召回率之間相互沖突,設(shè)定新的F測度,F的指標(biāo)越好則模型的推薦質(zhì)量越好．如下式：

(6)

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

K-means聚類的聚類數(shù)目K的選擇是一個(gè)關(guān)鍵,由于預(yù)處理數(shù)據(jù)中的三組數(shù)據(jù)相對于平均值有大于等于或小于兩種情況,因此設(shè)定K為2×2×2=8.在分析過程中對聚類結(jié)果的類別間距離進(jìn)行方差分析,類別間距離差異的概率值均小于0.05,即聚類效果好.

在HOSVD模型中,對展開矩陣A進(jìn)行SVD分解得到酉矩陣U的維數(shù)K進(jìn)行實(shí)驗(yàn)確定.保留的維數(shù)很重要,若K太小, 則不能得到評分矩陣中的重要結(jié)構(gòu);若K太大,則失去了矩陣降維的意義[13].

本實(shí)驗(yàn)以經(jīng)典的協(xié)同過濾算法為比較對象,采用相同的數(shù)據(jù)集和評估標(biāo)準(zhǔn).實(shí)驗(yàn)按照top-n的值分別取3,5,10,15和20進(jìn)行計(jì)算分析,計(jì)算結(jié)果見表5.根據(jù)表5可以得出文中算法和傳統(tǒng)算法的性能比較(圖3).

表5 兩種算法的F值比較

圖3 兩種算法性能比較

實(shí)驗(yàn)數(shù)據(jù)證明,文中算法在推薦不同項(xiàng)目個(gè)數(shù)top-n的情況下具有較大的F值,因此文中的高階奇異值推薦算法比傳統(tǒng)推薦方法更加有效．

6 結(jié)論

針對傳統(tǒng)推薦算法中存在的數(shù)據(jù)稀疏性導(dǎo)致推薦效果下降的問題,文中結(jié)合大眾標(biāo)注網(wǎng)站中含有標(biāo)簽的數(shù)據(jù),將K-means聚類和高階奇異值分解相結(jié)合對推薦算法進(jìn)行了改進(jìn),使得原始數(shù)據(jù)中包含的標(biāo)簽信息能夠充分利用,從而達(dá)到更好的推薦效果．

隨著電子商務(wù)網(wǎng)站數(shù)據(jù)量的不斷攀升,以及標(biāo)簽作為重要的項(xiàng)目信息得到越來越廣泛的運(yùn)用,傳統(tǒng)的推薦系統(tǒng)在處理此類問題上受到了挑戰(zhàn)．如何有效提高推薦精度是當(dāng)前推薦系統(tǒng)研究的熱門話題．文中算法以高階奇異值分解為基礎(chǔ)加入對原始數(shù)據(jù)的聚類步驟,以求進(jìn)一步解決數(shù)據(jù)稀疏性問題．在今后的研究工作中還可以將其他算法進(jìn)行揉合改進(jìn)推薦系統(tǒng),以取得更加有效的推薦精度．

[1] 竇玉萌,趙丹群. 協(xié)作標(biāo)注系統(tǒng)研究綜述[J]. 現(xiàn)代圖書情報(bào)技術(shù),2009,175(2):9-17.

[2] Vozalis M G, Margaritis K G. Using SVD and demographic data for the enhancement of generalized collaborative filtering[J].InformationSciences,2007,177(15):3017-3037.

[3] 黃國彬. 大眾標(biāo)注研究進(jìn)展[J]. 圖書情報(bào)工作,2008,52(1):13-15.

[4] Mangold W G, Faulds D J. Social media: The new hybrid element of the promotion mix[J].BusinessHorizons,2009,52:357-365.

[5] Meo P D, Nocera A. Recommendation of similar users, resources and social networks in a social internetworking scenario[J].InformationSciences,2011,181(7):1285-1305.

[6] 程慧榮,黃國彬,孫坦. 國外基于大眾標(biāo)注系統(tǒng)的標(biāo)簽研究[J]. 圖書情報(bào)工作,2009,53(2):121-124.

[7] Nan Zheng,Qiudan Li. A recommender system based on tag and time information for social tagging systems[J].ExpertSystemswithApplications,2011,38(4):4575-4587.

[8] Resnick P,Hal R V. Recommender system[J].CommunicationsoftheACM,1997,40(3):56-58.

[9] 孫玲芳,張婧. 基于RFM 模型和協(xié)同過濾的電子商務(wù)推薦機(jī)制[J]. 江蘇科技大學(xué)學(xué)報(bào):自然科學(xué)版,2010,24(3):285-289.

Sun Lingfang, Zhang Jing. Electronic recommendation mechanism based on RFM model and collaborative filtering[J].JournalofJiangsuUniversityofScienceandtechnology:NaturalScienceEdition,2010,24(3):285-289.(in Chinese)

[10] Symeonidis P, Nanopoulos A, Manolopoulos Y. A unified framework for providing recommendations in social tagging systems based on ternary semantic analysis[J].TransactionsonKnowledgeandDataEngineering,2010,22:179-191.

[11] 吳文亮. 聚類分析中K-均值與K-中心點(diǎn)算法的研究[D]. 廣州:華南理工大學(xué),2011:15-18.

[12] Symeonidis P, Ruxanda M, Nanopoulos A. Ternary semantic analysis of social tags for personalized music recommendation [J].KnowledgeRepresentation,Tags,Metadata,2008(2):219-224.

[13] Markaki M, Stylianou Y. Discrimination of speech from nonspeeech in broadcast news based on modulation frequency features[J].SpeechCommunication, 2011,53:726-735.