鄒偉靜，龐天杰

(太原師范學院 計算機系，山西 晉中 030619)

0 引言

在互聯(lián)網(wǎng)的高速發(fā)展的今天，網(wǎng)絡信息的增長速度呈現(xiàn)爆炸式增長.大數(shù)據(jù)的時代背景下，每天新增的數(shù)據(jù)量字節(jié)數(shù)已經(jīng)達到了1018量級，該數(shù)據(jù)量遠遠超出了人們能接受的范圍，互聯(lián)網(wǎng)出現(xiàn)了信息過載的情況.面對互聯(lián)網(wǎng)上數(shù)量如此龐大的信息，人們會不知所措，不知道如何從中快速地獲取自己需要的信息.針對信息過載現(xiàn)象，如何快速地解決該問題成為了一個熱點話題.解決信息過載問題的手段有很多，推薦算法就是其中最有效的手段之一，并在各個領域得到了廣泛應用，如電影、購物等等.但是隨著用戶和商品的規(guī)模不斷擴大，信息變得越來越稀疏，這是推薦算法面臨的主要問題之一[1-4].比如在一些購物網(wǎng)站，總商品數(shù)量有數(shù)以百萬計，但是用戶買過的商品數(shù)量微乎其微，再加上許多用戶并不會對商品進行評分和評價，這就導致了用戶評分信息矩陣極其稀疏.在實際的用戶數(shù)據(jù)中，不僅有用戶的歷史行為數(shù)據(jù)，而且包括用戶自身的分類屬性.因此用戶數(shù)據(jù)是一種既有評分數(shù)據(jù)又有屬性數(shù)據(jù)的混合數(shù)據(jù).然而在面對用戶數(shù)據(jù)時，傳統(tǒng)的推薦算法往往并沒有充分挖掘用戶信息，只取了用戶的評分數(shù)據(jù)作為相似度計算的依據(jù)，這就使得對用戶信息挖掘不充分，導致實際推薦算法效果不佳.

為了解決推薦算法的數(shù)據(jù)稀疏的問題，聚類算法是十分有效的方法之一.因此許多學者采用聚類的手段來改進推薦算法.文獻[5]通過挖掘用戶的特征信息來改進相似度的計算,并用改進的聚類算法對用戶進行聚類.文獻[6]采用FCM對用戶進行聚類，并采用遺傳算法對聚類算法進行改進防止出現(xiàn)局部最優(yōu)解，最后用實驗結(jié)果證明了改進算法的有效性.文獻[7]首先利用譜聚類對用戶進行聚類分組，再基于聚類對評分矩陣進行降維，最后基于隱語義模型對用戶進行評分預測.文獻[8]采用半監(jiān)督密度峰值聚類算法將用戶按興趣分組，并結(jié)合社交網(wǎng)絡關系建立用戶的信任集合，最后為目標用戶實現(xiàn)協(xié)同過濾推薦.

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

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

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

1.1 構(gòu)建矩陣

用戶-物品評分數(shù)據(jù)中有m個用戶和n個物品.根據(jù)數(shù)據(jù)構(gòu)建出用戶-物品評分矩陣Rm×n.rij表示用戶i對物品j的評分，若用戶i對物品j未評分，則rij記為0.由此可以構(gòu)建出用戶-物品評分矩陣：

1.2 距離和相似度的度量

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

1.2.1 歐式距離

歐式距離是最為常見的度量樣本間距離方法之一.用戶間的歐式距離計算公式如下：

(1)

(1)式中，D(u,v)表示用戶u和用戶v間的歐式距離，rui和rvi分別表示用戶u和用戶v對第i個物品的評分，n表示物品總數(shù).

1.2.2 皮爾森相關系數(shù)

距離度量可以用相關系數(shù)來表示[10].用戶間的皮爾森相關系數(shù)計算公式如下：

(2)

1.3 用戶聚類

利用上文的距離公式對用戶進行聚類，在聚類算法的選取上，以較為常用K-means++聚類算法為例.聚類算法步驟如下：

步驟1 從樣本集U中隨機選取一個點c1作為初始聚類中心；

步驟2 遍歷U中的樣本點，得到當前樣本點和所有聚類中心最近的距離dx；

步驟3 用(3)式計算每一個樣本點作為下一個聚類中心的概率；

(3)

步驟4 根據(jù)輪盤賭算法選出下一個聚類中心ci；

步驟5 重復步驟2-步驟4，直至找到k個初始聚類中心；

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

1.4 預測評分

有了上文的k個聚類簇，在當前聚類簇中選取h個與目標用戶最為相似的用戶并作為該用戶的近鄰集，用評分預測公式為目標用戶進行評分預測，預測公式如下：

(4)

(4)式中，pai表示用戶a對物品i的預測評分，G表示用戶a的近鄰集.

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

在實際的數(shù)據(jù)當中，用戶不僅有評分數(shù)據(jù)，還有其自身的屬性數(shù)據(jù)，這兩種數(shù)據(jù)往往是在一起的，構(gòu)成了用戶的混合數(shù)據(jù).對于該混合數(shù)據(jù)，不同部分需要做不同處理并加以結(jié)合，本文對用戶之間的相似度計算進行了重新定義.此外大數(shù)據(jù)數(shù)據(jù)量大的特點導致了數(shù)據(jù)的稀疏性，采用聚類算法對用戶進行聚類來達到降低數(shù)據(jù)稀疏的效果，將相似的用戶劃分到一個聚類簇中，從而提高推薦算法的準確性.

2.1 相似度計算

根據(jù)上文的分析，在計算用戶之間的相似度時，只用評分對用戶進行相似度的計算并不能將用戶劃分清晰.因此要計算用戶的混合數(shù)據(jù)之間的相似度.混合數(shù)據(jù)由屬性數(shù)據(jù)和評分數(shù)據(jù)構(gòu)成，對這兩部分的相似度方法如下.

從“十八大”以后中央特別注重我國的環(huán)境建設。汽車維修過程中會產(chǎn)生一系列排放物，從環(huán)保角度講，首先要做的是識別，識別出哪些是污染物，哪些是正常的排放物。汽修行業(yè)中，污染物分為三類，分別是液體、固態(tài)物和氣體。

2.1.1 屬性數(shù)據(jù)

對于屬性數(shù)據(jù)的處理，采用如下公式計算用戶之間的屬性相似度：

(5)

(5)式中，sim_a(u,v)表示用戶u和用戶v在屬性a上的相似度，ua和va分別表示用戶u和用戶v在屬性a上的值.

如用戶的年齡屬性特征，由埃里克森八階段理論[11]可知，人的心理社會發(fā)展隨著成長而發(fā)生變化，一共要經(jīng)歷八個階段.于是在數(shù)據(jù)集中便根據(jù)用戶年齡處在的不同階段對用戶年齡進行編碼，以此將不同年齡的用戶劃分到對應的心理社會年齡段中.因此可以得到用戶u和用戶v的年齡屬性特征相似度計算公式：

(6)

(6)式中，au為用戶u的年齡編碼；av為用戶v的年齡編碼.

2.1.2 評分數(shù)據(jù)

對于評分數(shù)據(jù)的處理，一般采用最為常用且效果好的皮爾森相關系數(shù)計算用戶間的相似度.

此外在物品集中，大家對熱門物品的關注度不盡相同，但是對于冷門物品，一般只有相似的人才會關注，因此在評分相似度中加入對熱門物品的懲罰系數(shù)[12]，懲罰系數(shù)如下：

(7)

式中，|D(i)|表示物品i的流行度.

將該懲罰系數(shù)融入評分相似度得到如下評分相似度計算公式：

(8)

將用戶的屬性數(shù)據(jù)特征相似度與評分數(shù)據(jù)特征相似度融合，得到一種新的相似度計算模型，即用戶的混合數(shù)據(jù)特征相似度計算模型，公式如下：

(9)

(8)式中，sim_A(u,v)表示用戶u和用戶v各個維度的屬性相似度的和，|·|表示用戶屬性特征和評分特征的維度.

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

得到了用戶的相似度后，需要對用戶進行聚類.K-means++算法是進行聚類時最常用的算法之一[13].其基于K-means算法并在聚類中心的選擇上做了優(yōu)化，在選擇聚類中心時，使得聚類中心盡可能遠，達到高內(nèi)聚低耦合的效果.相比于K-means算法，K-means++算法具有穩(wěn)定高效的特點，本文采用K-means++算法作為用戶聚類手段.算法步驟如下：

步驟1 從樣本集U中隨機選取一個點c1作為初始聚類中心；

步驟2 遍歷U中的樣本點，得到當前樣本點與所有聚類中心最大的相似度sx；

步驟3 根據(jù)公式計算每一個樣本點作為下一個聚類中心的概率；

(10)

步驟4 根據(jù)輪盤法選出下一個聚類中心ci；

步驟5 重復步驟2-步驟4，直至找到k個聚類中心；

步驟6 將剩余樣本點劃分到最為相似的一類中并得到k個聚類簇.

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

(11)

(11)式中，pai表示用戶a對物品i的預測評分，G表示用戶a的近鄰集.

3 實驗與討論

3.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)選取的是MovieLens ml-100k電影數(shù)據(jù)集[14].該數(shù)據(jù)集包括用戶評分數(shù)據(jù)集和用戶屬性數(shù)據(jù)集，屬于上文提到過的混合數(shù)據(jù)類型.用戶評分數(shù)據(jù)集是由943名用戶對1 682部電影評分共約10萬條評分數(shù)據(jù)構(gòu)成，每個用戶對電影的評分為1-5分.用戶屬性數(shù)據(jù)集包含了用戶的種種屬性，如年齡、性別等.實驗采用五折交叉實驗法驗證算法的有效性，取五次實驗的平均結(jié)果作為實驗的最終結(jié)果.

3.2 評價指標

實驗將采用平均絕對誤差(Mean Absolute Error，MAE)和均方根誤差(Root Mean Square Error，RMSE)作為評價指標[15].評價指標的公式如下：

(12)

(13)

3.3 實驗結(jié)果與分析

由于K-means++算法需設定聚類數(shù)目k，為了能有良好的推薦效果，本文先設置聚類數(shù)目區(qū)間為[5,50]，增量為5.通過輪廓系數(shù)[16]來衡量聚類效果.實驗結(jié)果表1所示.

表1 不同聚類數(shù)目k下的輪廓系數(shù)

由于算法是基于相似度聚類，因此輪廓系數(shù)越低聚類效果越好，根據(jù)實驗結(jié)果可得出結(jié)論，在聚類數(shù)目k=35時輪廓系數(shù)最低，因此將聚類數(shù)目設定為35.

為了驗證提出的推薦算法HDCRA的有效性.將本文算法與傳統(tǒng)的基于用戶的協(xié)同過濾推薦算法(User-based CollaboratIve Filtering，User-CF)和用戶聚類算法(K-means User Clustering，KUC)進行比較，并采用上文所述指標進行對實驗結(jié)果進行分析評價.MAE實驗結(jié)果如圖1所示.

圖1 不同算法下的MAE值對比

由圖1可以看出，三種算法的MAE在實驗數(shù)據(jù)集上的表現(xiàn)均隨著近鄰數(shù)的增大而減少且趨勢逐漸平緩.在近鄰數(shù)相同的情況下，HDCRA的MAE值整體上低于User-CF算法和KUC算法，說明HDCRA在推薦的精度上要優(yōu)于User-CF算法和KUC算法.RMSE的實驗結(jié)果如圖2所示.

圖2 不同算法下的RMSE值對比

由圖2可以看出，三種算法的RMAE在實驗數(shù)據(jù)集上的表現(xiàn)均隨著近鄰數(shù)的增大而減少且趨勢逐漸平緩.在近鄰數(shù)相同的情況下，HDCRA的實驗結(jié)果在整體上要低于User-CF算法和KUC算法，進一步說明HDCRA在推薦的效果上要優(yōu)于User-CF算法和KUC算法.

4 結(jié)語

本文針對推薦算法面對的數(shù)據(jù)稀疏性和推薦質(zhì)量不佳的問題，根據(jù)實際用戶數(shù)據(jù)是一類既有評分數(shù)據(jù)和屬性數(shù)據(jù)的混合數(shù)據(jù)，提出了一種面向用戶及評分信息的混合數(shù)據(jù)聚類推薦算法HDCRA.根據(jù)算法在實驗中的表現(xiàn)發(fā)現(xiàn)，該算法優(yōu)于傳統(tǒng)的推薦算法，彌補了傳統(tǒng)推薦算法的不足，在推薦精度和推薦質(zhì)量上都存在一定優(yōu)勢，進一步驗證了該算法的有效性.