鄒偉靜,龐天杰
(太原師范學(xué)院 計(jì)算機(jī)系,山西 晉中 030619)
在互聯(lián)網(wǎng)的高速發(fā)展的今天,網(wǎng)絡(luò)信息的增長速度呈現(xiàn)爆炸式增長.大數(shù)據(jù)的時(shí)代背景下,每天新增的數(shù)據(jù)量字節(jié)數(shù)已經(jīng)達(dá)到了1018量級(jí),該數(shù)據(jù)量遠(yuǎn)遠(yuǎn)超出了人們能接受的范圍,互聯(lián)網(wǎng)出現(xiàn)了信息過載的情況.面對(duì)互聯(lián)網(wǎng)上數(shù)量如此龐大的信息,人們會(huì)不知所措,不知道如何從中快速地獲取自己需要的信息.針對(duì)信息過載現(xiàn)象,如何快速地解決該問題成為了一個(gè)熱點(diǎn)話題.解決信息過載問題的手段有很多,推薦算法就是其中最有效的手段之一,并在各個(gè)領(lǐng)域得到了廣泛應(yīng)用,如電影、購物等等.但是隨著用戶和商品的規(guī)模不斷擴(kuò)大,信息變得越來越稀疏,這是推薦算法面臨的主要問題之一[1-4].比如在一些購物網(wǎng)站,總商品數(shù)量有數(shù)以百萬計(jì),但是用戶買過的商品數(shù)量微乎其微,再加上許多用戶并不會(huì)對(duì)商品進(jìn)行評(píng)分和評(píng)價(jià),這就導(dǎo)致了用戶評(píng)分信息矩陣極其稀疏.在實(shí)際的用戶數(shù)據(jù)中,不僅有用戶的歷史行為數(shù)據(jù),而且包括用戶自身的分類屬性.因此用戶數(shù)據(jù)是一種既有評(píng)分?jǐn)?shù)據(jù)又有屬性數(shù)據(jù)的混合數(shù)據(jù).然而在面對(duì)用戶數(shù)據(jù)時(shí),傳統(tǒng)的推薦算法往往并沒有充分挖掘用戶信息,只取了用戶的評(píng)分?jǐn)?shù)據(jù)作為相似度計(jì)算的依據(jù),這就使得對(duì)用戶信息挖掘不充分,導(dǎo)致實(shí)際推薦算法效果不佳.
為了解決推薦算法的數(shù)據(jù)稀疏的問題,聚類算法是十分有效的方法之一.因此許多學(xué)者采用聚類的手段來改進(jìn)推薦算法.文獻(xiàn)[5]通過挖掘用戶的特征信息來改進(jìn)相似度的計(jì)算,并用改進(jìn)的聚類算法對(duì)用戶進(jìn)行聚類.文獻(xiàn)[6]采用FCM對(duì)用戶進(jìn)行聚類,并采用遺傳算法對(duì)聚類算法進(jìn)行改進(jìn)防止出現(xiàn)局部最優(yōu)解,最后用實(shí)驗(yàn)結(jié)果證明了改進(jìn)算法的有效性.文獻(xiàn)[7]首先利用譜聚類對(duì)用戶進(jìn)行聚類分組,再基于聚類對(duì)評(píng)分矩陣進(jìn)行降維,最后基于隱語義模型對(duì)用戶進(jìn)行評(píng)分預(yù)測.文獻(xiàn)[8]采用半監(jiān)督密度峰值聚類算法將用戶按興趣分組,并結(jié)合社交網(wǎng)絡(luò)關(guān)系建立用戶的信任集合,最后為目標(biāo)用戶實(shí)現(xiàn)協(xié)同過濾推薦.
上述文章中的算法一定程度上提高了推薦系統(tǒng)的預(yù)測準(zhǔn)確性,但是對(duì)于用戶信息挖掘不夠充分,因?yàn)樵趯?shí)際生活中,用戶數(shù)據(jù)往往是既有評(píng)分?jǐn)?shù)據(jù)又有屬性數(shù)據(jù)的混合數(shù)據(jù),在挖掘用戶信息的時(shí)候需要從混合數(shù)據(jù)入手.為了解決該問題,提出了一種面向用戶及評(píng)分信息的混合數(shù)據(jù)聚類推薦算法,旨在分析用戶的混合數(shù)據(jù)來提升推薦質(zhì)量.首先通過分析用戶的混合數(shù)據(jù),計(jì)算出用戶在混合數(shù)據(jù)上的相似度;然后采用聚類算法對(duì)用戶進(jìn)行聚類并得到多個(gè)聚類簇.最后在聚類簇中對(duì)目標(biāo)用戶實(shí)現(xiàn)協(xié)同過濾推薦.
傳統(tǒng)的基于聚類的協(xié)同過濾推薦算法的基本流程如下:首先利用用戶歷史數(shù)據(jù),構(gòu)建出用戶-物品評(píng)分矩陣;之后采用聚類算法對(duì)用戶進(jìn)行聚類,得到關(guān)于用戶的聚類簇;然后在一個(gè)聚類簇中計(jì)算用戶間的相似度,并利用協(xié)同過濾思想為目標(biāo)用戶進(jìn)行評(píng)分預(yù)測;最后根據(jù)預(yù)測結(jié)果依照Top-N原則對(duì)目標(biāo)用戶進(jìn)行推薦[9].
用戶-物品評(píng)分?jǐn)?shù)據(jù)中有m個(gè)用戶和n個(gè)物品.根據(jù)數(shù)據(jù)構(gòu)建出用戶-物品評(píng)分矩陣Rm×n.rij表示用戶i對(duì)物品j的評(píng)分,若用戶i對(duì)物品j未評(píng)分,則rij記為0.由此可以構(gòu)建出用戶-物品評(píng)分矩陣:
根據(jù)得到用戶-物品評(píng)分矩陣,獲得每個(gè)用戶的評(píng)分向量.將用戶評(píng)分向量之間的距離和相似度作為用戶間的距離和相似度.常見的距離和相似度度量[10]公式如下.
1.2.1 歐式距離
歐式距離是最為常見的度量樣本間距離方法之一.用戶間的歐式距離計(jì)算公式如下:
(1)
(1)式中,D(u,v)表示用戶u和用戶v間的歐式距離,rui和rvi分別表示用戶u和用戶v對(duì)第i個(gè)物品的評(píng)分,n表示物品總數(shù).
1.2.2 皮爾森相關(guān)系數(shù)
距離度量可以用相關(guān)系數(shù)來表示[10].用戶間的皮爾森相關(guān)系數(shù)計(jì)算公式如下:
(2)
利用上文的距離公式對(duì)用戶進(jìn)行聚類,在聚類算法的選取上,以較為常用K-means++聚類算法為例.聚類算法步驟如下:
步驟1 從樣本集U中隨機(jī)選取一個(gè)點(diǎn)c1作為初始聚類中心;
步驟2 遍歷U中的樣本點(diǎn),得到當(dāng)前樣本點(diǎn)和所有聚類中心最近的距離dx;
步驟3 用(3)式計(jì)算每一個(gè)樣本點(diǎn)作為下一個(gè)聚類中心的概率;
(3)
步驟4 根據(jù)輪盤賭算法選出下一個(gè)聚類中心ci;
步驟5 重復(fù)步驟2-步驟4,直至找到k個(gè)初始聚類中心;
步驟6 利用K-means算法步驟得到k個(gè)聚類簇.
有了上文的k個(gè)聚類簇,在當(dāng)前聚類簇中選取h個(gè)與目標(biāo)用戶最為相似的用戶并作為該用戶的近鄰集,用評(píng)分預(yù)測公式為目標(biāo)用戶進(jìn)行評(píng)分預(yù)測,預(yù)測公式如下:
(4)
(4)式中,pai表示用戶a對(duì)物品i的預(yù)測評(píng)分,G表示用戶a的近鄰集.
在實(shí)際的數(shù)據(jù)當(dāng)中,用戶不僅有評(píng)分?jǐn)?shù)據(jù),還有其自身的屬性數(shù)據(jù),這兩種數(shù)據(jù)往往是在一起的,構(gòu)成了用戶的混合數(shù)據(jù).對(duì)于該混合數(shù)據(jù),不同部分需要做不同處理并加以結(jié)合,本文對(duì)用戶之間的相似度計(jì)算進(jìn)行了重新定義.此外大數(shù)據(jù)數(shù)據(jù)量大的特點(diǎn)導(dǎo)致了數(shù)據(jù)的稀疏性,采用聚類算法對(duì)用戶進(jìn)行聚類來達(dá)到降低數(shù)據(jù)稀疏的效果,將相似的用戶劃分到一個(gè)聚類簇中,從而提高推薦算法的準(zhǔn)確性.
根據(jù)上文的分析,在計(jì)算用戶之間的相似度時(shí),只用評(píng)分對(duì)用戶進(jìn)行相似度的計(jì)算并不能將用戶劃分清晰.因此要計(jì)算用戶的混合數(shù)據(jù)之間的相似度.混合數(shù)據(jù)由屬性數(shù)據(jù)和評(píng)分?jǐn)?shù)據(jù)構(gòu)成,對(duì)這兩部分的相似度方法如下.
從“十八大”以后中央特別注重我國的環(huán)境建設(shè)。汽車維修過程中會(huì)產(chǎn)生一系列排放物,從環(huán)保角度講,首先要做的是識(shí)別,識(shí)別出哪些是污染物,哪些是正常的排放物。汽修行業(yè)中,污染物分為三類,分別是液體、固態(tài)物和氣體。
2.1.1 屬性數(shù)據(jù)
對(duì)于屬性數(shù)據(jù)的處理,采用如下公式計(jì)算用戶之間的屬性相似度:
(5)
(5)式中,sim_a(u,v)表示用戶u和用戶v在屬性a上的相似度,ua和va分別表示用戶u和用戶v在屬性a上的值.
如用戶的年齡屬性特征,由埃里克森八階段理論[11]可知,人的心理社會(huì)發(fā)展隨著成長而發(fā)生變化,一共要經(jīng)歷八個(gè)階段.于是在數(shù)據(jù)集中便根據(jù)用戶年齡處在的不同階段對(duì)用戶年齡進(jìn)行編碼,以此將不同年齡的用戶劃分到對(duì)應(yīng)的心理社會(huì)年齡段中.因此可以得到用戶u和用戶v的年齡屬性特征相似度計(jì)算公式:
(6)
(6)式中,au為用戶u的年齡編碼;av為用戶v的年齡編碼.
2.1.2 評(píng)分?jǐn)?shù)據(jù)
對(duì)于評(píng)分?jǐn)?shù)據(jù)的處理,一般采用最為常用且效果好的皮爾森相關(guān)系數(shù)計(jì)算用戶間的相似度.
此外在物品集中,大家對(duì)熱門物品的關(guān)注度不盡相同,但是對(duì)于冷門物品,一般只有相似的人才會(huì)關(guān)注,因此在評(píng)分相似度中加入對(duì)熱門物品的懲罰系數(shù)[12],懲罰系數(shù)如下:
(7)
式中,|D(i)|表示物品i的流行度.
將該懲罰系數(shù)融入評(píng)分相似度得到如下評(píng)分相似度計(jì)算公式:
(8)
將用戶的屬性數(shù)據(jù)特征相似度與評(píng)分?jǐn)?shù)據(jù)特征相似度融合,得到一種新的相似度計(jì)算模型,即用戶的混合數(shù)據(jù)特征相似度計(jì)算模型,公式如下:
(9)
(8)式中,sim_A(u,v)表示用戶u和用戶v各個(gè)維度的屬性相似度的和,|·|表示用戶屬性特征和評(píng)分特征的維度.
得到了用戶的相似度后,需要對(duì)用戶進(jìn)行聚類.K-means++算法是進(jìn)行聚類時(shí)最常用的算法之一[13].其基于K-means算法并在聚類中心的選擇上做了優(yōu)化,在選擇聚類中心時(shí),使得聚類中心盡可能遠(yuǎn),達(dá)到高內(nèi)聚低耦合的效果.相比于K-means算法,K-means++算法具有穩(wěn)定高效的特點(diǎn),本文采用K-means++算法作為用戶聚類手段.算法步驟如下:
步驟1 從樣本集U中隨機(jī)選取一個(gè)點(diǎn)c1作為初始聚類中心;
步驟2 遍歷U中的樣本點(diǎn),得到當(dāng)前樣本點(diǎn)與所有聚類中心最大的相似度sx;
步驟3 根據(jù)公式計(jì)算每一個(gè)樣本點(diǎn)作為下一個(gè)聚類中心的概率;
(10)
步驟4 根據(jù)輪盤法選出下一個(gè)聚類中心ci;
步驟5 重復(fù)步驟2-步驟4,直至找到k個(gè)聚類中心;
步驟6 將剩余樣本點(diǎn)劃分到最為相似的一類中并得到k個(gè)聚類簇.
最后根據(jù)聚類結(jié)果預(yù)測出用戶對(duì)物品的評(píng)分,公式如下所示:
(11)
(11)式中,pai表示用戶a對(duì)物品i的預(yù)測評(píng)分,G表示用戶a的近鄰集.
實(shí)驗(yàn)數(shù)據(jù)選取的是MovieLens ml-100k電影數(shù)據(jù)集[14].該數(shù)據(jù)集包括用戶評(píng)分?jǐn)?shù)據(jù)集和用戶屬性數(shù)據(jù)集,屬于上文提到過的混合數(shù)據(jù)類型.用戶評(píng)分?jǐn)?shù)據(jù)集是由943名用戶對(duì)1 682部電影評(píng)分共約10萬條評(píng)分?jǐn)?shù)據(jù)構(gòu)成,每個(gè)用戶對(duì)電影的評(píng)分為1-5分.用戶屬性數(shù)據(jù)集包含了用戶的種種屬性,如年齡、性別等.實(shí)驗(yàn)采用五折交叉實(shí)驗(yàn)法驗(yàn)證算法的有效性,取五次實(shí)驗(yàn)的平均結(jié)果作為實(shí)驗(yàn)的最終結(jié)果.
實(shí)驗(yàn)將采用平均絕對(duì)誤差(Mean Absolute Error,MAE)和均方根誤差(Root Mean Square Error,RMSE)作為評(píng)價(jià)指標(biāo)[15].評(píng)價(jià)指標(biāo)的公式如下:
(12)
(13)
由于K-means++算法需設(shè)定聚類數(shù)目k,為了能有良好的推薦效果,本文先設(shè)置聚類數(shù)目區(qū)間為[5,50],增量為5.通過輪廓系數(shù)[16]來衡量聚類效果.實(shí)驗(yàn)結(jié)果表1所示.
表1 不同聚類數(shù)目k下的輪廓系數(shù)
由于算法是基于相似度聚類,因此輪廓系數(shù)越低聚類效果越好,根據(jù)實(shí)驗(yàn)結(jié)果可得出結(jié)論,在聚類數(shù)目k=35時(shí)輪廓系數(shù)最低,因此將聚類數(shù)目設(shè)定為35.
為了驗(yàn)證提出的推薦算法HDCRA的有效性.將本文算法與傳統(tǒng)的基于用戶的協(xié)同過濾推薦算法(User-based CollaboratIve Filtering,User-CF)和用戶聚類算法(K-means User Clustering,KUC)進(jìn)行比較,并采用上文所述指標(biāo)進(jìn)行對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析評(píng)價(jià).MAE實(shí)驗(yàn)結(jié)果如圖1所示.
圖1 不同算法下的MAE值對(duì)比
由圖1可以看出,三種算法的MAE在實(shí)驗(yàn)數(shù)據(jù)集上的表現(xiàn)均隨著近鄰數(shù)的增大而減少且趨勢逐漸平緩.在近鄰數(shù)相同的情況下,HDCRA的MAE值整體上低于User-CF算法和KUC算法,說明HDCRA在推薦的精度上要優(yōu)于User-CF算法和KUC算法.RMSE的實(shí)驗(yàn)結(jié)果如圖2所示.
圖2 不同算法下的RMSE值對(duì)比
由圖2可以看出,三種算法的RMAE在實(shí)驗(yàn)數(shù)據(jù)集上的表現(xiàn)均隨著近鄰數(shù)的增大而減少且趨勢逐漸平緩.在近鄰數(shù)相同的情況下,HDCRA的實(shí)驗(yàn)結(jié)果在整體上要低于User-CF算法和KUC算法,進(jìn)一步說明HDCRA在推薦的效果上要優(yōu)于User-CF算法和KUC算法.
本文針對(duì)推薦算法面對(duì)的數(shù)據(jù)稀疏性和推薦質(zhì)量不佳的問題,根據(jù)實(shí)際用戶數(shù)據(jù)是一類既有評(píng)分?jǐn)?shù)據(jù)和屬性數(shù)據(jù)的混合數(shù)據(jù),提出了一種面向用戶及評(píng)分信息的混合數(shù)據(jù)聚類推薦算法HDCRA.根據(jù)算法在實(shí)驗(yàn)中的表現(xiàn)發(fā)現(xiàn),該算法優(yōu)于傳統(tǒng)的推薦算法,彌補(bǔ)了傳統(tǒng)推薦算法的不足,在推薦精度和推薦質(zhì)量上都存在一定優(yōu)勢,進(jìn)一步驗(yàn)證了該算法的有效性.