面向用戶及評(píng)分信息的混合數(shù)據(jù)聚類推薦算法

鄒偉靜，龐天杰

(太原師范學(xué)院 計(jì)算機(jī)系，山西 晉中 030619)

0 引言

在互聯(lián)網(wǎng)的高速發(fā)展的今天，網(wǎng)絡(luò)信息的增長(zhǎng)速度呈現(xiàn)爆炸式增長(zhǎng).大數(shù)據(jù)的時(shí)代背景下，每天新增的數(shù)據(jù)量字節(jié)數(shù)已經(jīng)達(dá)到了1018量級(jí)，該數(shù)據(jù)量遠(yuǎn)遠(yuǎn)超出了人們能接受的范圍，互聯(lián)網(wǎng)出現(xiàn)了信息過(guò)載的情況.面對(duì)互聯(lián)網(wǎng)上數(shù)量如此龐大的信息，人們會(huì)不知所措，不知道如何從中快速地獲取自己需要的信息.針對(duì)信息過(guò)載現(xiàn)象，如何快速地解決該問(wèn)題成為了一個(gè)熱點(diǎn)話題.解決信息過(guò)載問(wèn)題的手段有很多，推薦算法就是其中最有效的手段之一，并在各個(gè)領(lǐng)域得到了廣泛應(yīng)用，如電影、購(gòu)物等等.但是隨著用戶和商品的規(guī)模不斷擴(kuò)大，信息變得越來(lái)越稀疏，這是推薦算法面臨的主要問(wèn)題之一[1-4].比如在一些購(gòu)物網(wǎng)站，總商品數(shù)量有數(shù)以百萬(wàn)計(jì)，但是用戶買過(guò)的商品數(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)的推薦算法往往并沒(méi)有充分挖掘用戶信息，只取了用戶的評(píng)分?jǐn)?shù)據(jù)作為相似度計(jì)算的依據(jù)，這就使得對(duì)用戶信息挖掘不充分，導(dǎo)致實(shí)際推薦算法效果不佳.

為了解決推薦算法的數(shù)據(jù)稀疏的問(wèn)題，聚類算法是十分有效的方法之一.因此許多學(xué)者采用聚類的手段來(lái)改進(jìn)推薦算法.文獻(xiàn)[5]通過(guò)挖掘用戶的特征信息來(lái)改進(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)行降維，最后基于隱語(yǔ)義模型對(duì)用戶進(jìn)行評(píng)分預(yù)測(cè).文獻(xiàn)[8]采用半監(jiān)督密度峰值聚類算法將用戶按興趣分組，并結(jié)合社交網(wǎng)絡(luò)關(guān)系建立用戶的信任集合，最后為目標(biāo)用戶實(shí)現(xiàn)協(xié)同過(guò)濾推薦.

上述文章中的算法一定程度上提高了推薦系統(tǒng)的預(yù)測(cè)準(zhǔn)確性，但是對(duì)于用戶信息挖掘不夠充分，因?yàn)樵趯?shí)際生活中，用戶數(shù)據(jù)往往是既有評(píng)分?jǐn)?shù)據(jù)又有屬性數(shù)據(jù)的混合數(shù)據(jù)，在挖掘用戶信息的時(shí)候需要從混合數(shù)據(jù)入手.為了解決該問(wèn)題，提出了一種面向用戶及評(píng)分信息的混合數(shù)據(jù)聚類推薦算法，旨在分析用戶的混合數(shù)據(jù)來(lái)提升推薦質(zhì)量.首先通過(guò)分析用戶的混合數(shù)據(jù)，計(jì)算出用戶在混合數(shù)據(jù)上的相似度；然后采用聚類算法對(duì)用戶進(jìn)行聚類并得到多個(gè)聚類簇.最后在聚類簇中對(duì)目標(biāo)用戶實(shí)現(xiàn)協(xié)同過(guò)濾推薦.

1 傳統(tǒng)的基于聚類的協(xié)同過(guò)濾推薦算法

傳統(tǒng)的基于聚類的協(xié)同過(guò)濾推薦算法的基本流程如下：首先利用用戶歷史數(shù)據(jù)，構(gòu)建出用戶-物品評(píng)分矩陣；之后采用聚類算法對(duì)用戶進(jìn)行聚類，得到關(guān)于用戶的聚類簇；然后在一個(gè)聚類簇中計(jì)算用戶間的相似度，并利用協(xié)同過(guò)濾思想為目標(biāo)用戶進(jìn)行評(píng)分預(yù)測(cè)；最后根據(jù)預(yù)測(cè)結(jié)果依照Top-N原則對(duì)目標(biāo)用戶進(jìn)行推薦[9].

1.1 構(gòu)建矩陣

用戶-物品評(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)分矩陣：

1.2 距離和相似度的度量

根據(jù)得到用戶-物品評(píng)分矩陣，獲得每個(gè)用戶的評(píng)分向量.將用戶評(píng)分向量之間的距離和相似度作為用戶間的距離和相似度.常見(jiàn)的距離和相似度度量[10]公式如下.

1.2.1 歐式距離

歐式距離是最為常見(jiàn)的度量樣本間距離方法之一.用戶間的歐式距離計(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ù)來(lái)表示[10].用戶間的皮爾森相關(guān)系數(shù)計(jì)算公式如下：

(2)

1.3 用戶聚類

利用上文的距離公式對(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ù)輪盤(pán)賭算法選出下一個(gè)聚類中心ci；

步驟5 重復(fù)步驟2-步驟4，直至找到k個(gè)初始聚類中心；

步驟6 利用K-means算法步驟得到k個(gè)聚類簇.

1.4 預(yù)測(cè)評(píng)分

有了上文的k個(gè)聚類簇，在當(dāng)前聚類簇中選取h個(gè)與目標(biāo)用戶最為相似的用戶并作為該用戶的近鄰集，用評(píng)分預(yù)測(cè)公式為目標(biāo)用戶進(jìn)行評(píng)分預(yù)測(cè)，預(yù)測(cè)公式如下：

(4)

(4)式中，pai表示用戶a對(duì)物品i的預(yù)測(cè)評(píng)分，G表示用戶a的近鄰集.

2 混合數(shù)據(jù)聚類推薦算法HDCRA

在實(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)行聚類來(lái)達(dá)到降低數(shù)據(jù)稀疏的效果，將相似的用戶劃分到一個(gè)聚類簇中，從而提高推薦算法的準(zhǔn)確性.

2.1 相似度計(jì)算

根據(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ì)這兩部分的相似度方法如下.

從“十八大”以后中央特別注重我國(guó)的環(huán)境建設(shè)。汽車維修過(guò)程中會(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ā)展隨著成長(zhǎng)而發(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ì)熱門(mén)物品的關(guān)注度不盡相同，但是對(duì)于冷門(mén)物品，一般只有相似的人才會(huì)關(guān)注，因此在評(píng)分相似度中加入對(duì)熱門(mén)物品的懲罰系數(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)分特征的維度.

2.2 基于K-means++的用戶聚類

得到了用戶的相似度后，需要對(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ù)輪盤(pán)法選出下一個(gè)聚類中心ci；

步驟5 重復(fù)步驟2-步驟4，直至找到k個(gè)聚類中心；

步驟6 將剩余樣本點(diǎn)劃分到最為相似的一類中并得到k個(gè)聚類簇.

最后根據(jù)聚類結(jié)果預(yù)測(cè)出用戶對(duì)物品的評(píng)分，公式如下所示：

(11)

(11)式中，pai表示用戶a對(duì)物品i的預(yù)測(cè)評(píng)分，G表示用戶a的近鄰集.

3 實(shí)驗(yàn)與討論

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

實(shí)驗(yàn)數(shù)據(jù)選取的是MovieLens ml-100k電影數(shù)據(jù)集[14].該數(shù)據(jù)集包括用戶評(píng)分?jǐn)?shù)據(jù)集和用戶屬性數(shù)據(jù)集，屬于上文提到過(guò)的混合數(shù)據(jù)類型.用戶評(píng)分?jǐn)?shù)據(jù)集是由943名用戶對(duì)1 682部電影評(píng)分共約10萬(wàn)條評(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é)果.

3.2 評(píng)價(jià)指標(biāo)

實(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)

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

由于K-means++算法需設(shè)定聚類數(shù)目k，為了能有良好的推薦效果，本文先設(shè)置聚類數(shù)目區(qū)間為[5,50]，增量為5.通過(guò)輪廓系數(shù)[16]來(lái)衡量聚類效果.實(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é)同過(guò)濾推薦算法(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ì)逐漸平緩.在近鄰數(shù)相同的情況下，HDCRA的MAE值整體上低于User-CF算法和KUC算法，說(shuō)明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ì)逐漸平緩.在近鄰數(shù)相同的情況下，HDCRA的實(shí)驗(yàn)結(jié)果在整體上要低于User-CF算法和KUC算法，進(jìn)一步說(shuō)明HDCRA在推薦的效果上要優(yōu)于User-CF算法和KUC算法.

4 結(jié)語(yǔ)

本文針對(duì)推薦算法面對(duì)的數(shù)據(jù)稀疏性和推薦質(zhì)量不佳的問(wèn)題，根據(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)勢(shì)，進(jìn)一步驗(yàn)證了該算法的有效性.