基于K-means的矩陣分解推薦算法

張榮梅, 陳 彬, 張 琦

(河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院, 石家莊 050061)

0 引 言

當(dāng)下，隨著大數(shù)據(jù)時(shí)代的來(lái)臨，信息資源過(guò)度膨脹，形成了“信息爆炸”的現(xiàn)象。為了緩解這種情況帶來(lái)的信息過(guò)載、數(shù)據(jù)冗余、選擇困難等問(wèn)題，越來(lái)越多的專(zhuān)家學(xué)者已然開(kāi)始關(guān)注起推薦系統(tǒng)領(lǐng)域的研究。推薦系統(tǒng)是通過(guò)分析用戶的歷史數(shù)據(jù)，以及項(xiàng)目等其它輔助信息，推測(cè)出用戶潛在的偏好需求，進(jìn)而為用戶提供個(gè)性化的項(xiàng)目推薦。常見(jiàn)的傳統(tǒng)推薦技術(shù)是基于內(nèi)容的算法、基于協(xié)同過(guò)濾的算法及混合算法[1]。其中，協(xié)同過(guò)濾算法應(yīng)用較為廣泛，Goldberg等人[2]于1992年提出了協(xié)同過(guò)濾的概念，最初應(yīng)用在Tapestry System上用于過(guò)濾電子郵件。這是通過(guò)引入其它用戶的興趣來(lái)對(duì)當(dāng)前用戶進(jìn)行推薦，只是涉及用戶的歷史交易記錄，而不依賴用戶和項(xiàng)目的屬性特征。但協(xié)同過(guò)濾算法存在數(shù)據(jù)稀疏[3]和冷啟動(dòng)問(wèn)題[4]。于洪等人[5]為了更好地解決物品冷啟動(dòng)問(wèn)題，提出了一種附加用戶時(shí)間權(quán)重的算法，對(duì)用戶評(píng)論時(shí)間與項(xiàng)目發(fā)布時(shí)間加以計(jì)算研究，但由于很多標(biāo)準(zhǔn)數(shù)據(jù)集中缺少時(shí)間戳的屬性，其作用范圍有限。針對(duì)于此，為了改進(jìn)協(xié)同過(guò)濾算法，本文將K-means聚類(lèi)算法與矩陣分解技術(shù)相結(jié)合，提出一種基于K-means的矩陣分解推薦算法(Matrix Decomposition Based on K-means，KMMD)，引入了用戶屬性信息，在提高推薦精度的同時(shí)，有效改善用戶冷啟動(dòng)問(wèn)題。

1 基于K-means的矩陣分解推薦算法(KMMD)

1.1 Funk-SVD矩陣分解算法

基于內(nèi)容的推薦和基于用戶畫(huà)像的推薦[6]都是聚焦于待推薦用戶自身的屬性信息或交易記錄，并沒(méi)有考慮過(guò)其它用戶的數(shù)據(jù)是否會(huì)對(duì)當(dāng)前用戶產(chǎn)生推薦影響，在召回率和精確度上不能進(jìn)一步提高。而矩陣分解[7]作為協(xié)同過(guò)濾的一種重要方法，不僅將待推薦用戶自身的屬性考慮在內(nèi)，還吸收借鑒了其它用戶的數(shù)據(jù)信息，來(lái)實(shí)施推薦。且矩陣分解算法將龐大的用戶-項(xiàng)目評(píng)級(jí)矩陣分解為多個(gè)矩陣存儲(chǔ)，大大減緩了磁盤(pán)存儲(chǔ)壓力。

矩陣分解采用Funk-SVD，是通過(guò)將用戶-項(xiàng)目評(píng)級(jí)矩陣Rm×n進(jìn)行分解，得到可以表示用戶和項(xiàng)目特征的2個(gè)低維的抽象隱因子矩陣：Um×k表示m個(gè)用戶的k維隱因子矩陣，Vn×kT表示n個(gè)項(xiàng)目的k維隱因子矩陣，使得Um×k·Vn×kT≈Rm×n。使用重構(gòu)后的評(píng)級(jí)矩陣來(lái)預(yù)測(cè)用戶對(duì)未知項(xiàng)目的評(píng)分。對(duì)于矩陣中的缺失項(xiàng)，在參數(shù)更新時(shí)選擇忽略不計(jì)，不對(duì)其進(jìn)行操作，而只針對(duì)有效數(shù)據(jù)進(jìn)行參數(shù)訓(xùn)練。

(1)

其中，損失函數(shù)由誤差平方和正則化項(xiàng)組成，引入正則化項(xiàng)可以防止訓(xùn)練結(jié)果的過(guò)擬合。

而訓(xùn)練過(guò)程是使用梯度下降降低損失函數(shù)，其數(shù)學(xué)公式可表示為：

(2)

(3)

其中，α是學(xué)習(xí)率參數(shù)，表示每次更新的快慢。

傳統(tǒng)的矩陣分解算法多采用傳統(tǒng)的SVD矩陣分解方式[8]。傳統(tǒng)SVD分解后會(huì)得到3個(gè)矩陣：U、∑和V。其中，∑是一個(gè)對(duì)角矩陣，表示U和V矩陣在每個(gè)維度上的重構(gòu)重要度可通過(guò)該對(duì)角矩陣進(jìn)行降維，但存在對(duì)矩陣求逆等操作，致使計(jì)算復(fù)雜度高。而本文實(shí)驗(yàn)采用的是Funk-SVD分解方式，借鑒線性回歸的思想，通過(guò)最小化均方誤差來(lái)尋求最優(yōu)的用戶和項(xiàng)目的隱含向量表示，其維度可直接調(diào)整。Funk-SVD用2個(gè)矩陣就可以實(shí)現(xiàn)SVD三個(gè)矩陣的重構(gòu)效果，在一定程度上提高了運(yùn)算效率。

1.2 K-means聚類(lèi)

由于傳統(tǒng)矩陣分解算法只使用用戶對(duì)項(xiàng)目的評(píng)級(jí)信息，其推薦精度上限難以進(jìn)一步提升，所以引入用戶屬性信息，經(jīng)K-means聚類(lèi)分析再進(jìn)行矩陣分解運(yùn)算，提高算法推薦能力。K-means是一種將數(shù)據(jù)按策略劃分為某幾種類(lèi)別的聚類(lèi)算法[9]，其中K表示聚類(lèi)的類(lèi)別種數(shù)，即質(zhì)心的數(shù)量，means表示均值。K-means聚類(lèi)之前的預(yù)處理過(guò)程可分述如下。

(1)提取用戶基本屬性信息，User=(Age,Gender,Occupation)，構(gòu)建用戶屬性矩陣U。

(2)對(duì)于非數(shù)值的離散型數(shù)據(jù)，進(jìn)行one-hot編碼[10]數(shù)值化處理。one-hot編碼是將原某類(lèi)型屬性按照其種類(lèi)進(jìn)行編碼，編碼結(jié)果是只有一位為有效值1，其余位都是0。年齡屬性已經(jīng)是數(shù)值型屬性，所以不做處理。性別是二元屬性，分為“男”和“女”，所以分別編碼為[0]和[1]。職業(yè)屬于標(biāo)稱(chēng)屬性，包含多種類(lèi)別，按照類(lèi)別總數(shù)S構(gòu)建長(zhǎng)度為S的編碼串，并由先后出現(xiàn)順序?yàn)槠渲谩?”編碼，在MovieLens-100K數(shù)據(jù)集中共出現(xiàn)有21種職業(yè)類(lèi)型，數(shù)據(jù)集中最先出現(xiàn)的“technician”職業(yè)的one-hot編碼為[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]，緊接著出現(xiàn)的“writer”職業(yè)的one-hot編碼為[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]，以此類(lèi)推。然后所有屬性拼接組合成稀疏的用戶屬性向量，對(duì)于“年齡=24，性別=男，職業(yè)=技術(shù)員”的用戶User_a=(24, man, technician)，經(jīng)如上處理后得到的用戶屬性向量為User_a′=[24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]。

(3)embedding處理。經(jīng)由one-hot編碼后的數(shù)據(jù)必然是稀疏的，所以將其進(jìn)行embedding處理，即是將原稀疏向量與固定轉(zhuǎn)換矩陣做內(nèi)積變換，轉(zhuǎn)化為稠密向量，即：

(4)

得到由用戶稠密屬性向量構(gòu)建的用戶屬性矩陣，就可以進(jìn)行K-means聚類(lèi)分析了。算法1的設(shè)計(jì)步驟見(jiàn)如下。

算法1K-means。用于聚類(lèi)劃分的K-均值算法，其中每個(gè)簇的中心(質(zhì)心)都用簇中所有對(duì)象元素的均值來(lái)表示[11]

輸入：K表示簇的數(shù)目；D為包含n個(gè)對(duì)象元素的數(shù)據(jù)集

輸出：K個(gè)簇的集合

(1)從D中任意選取K個(gè)對(duì)象作為初始簇的中心；

(2)repeat

(3)根據(jù)簇中對(duì)象元素的均值，將每個(gè)對(duì)象分配到最相似的簇；

(4)更新簇均值，即重新計(jì)算每個(gè)簇中對(duì)象的均值；

(5)until不再發(fā)生變化。

采用K-means聚類(lèi)算法提前對(duì)用戶進(jìn)行聚類(lèi)分析，可減小構(gòu)建的用戶-項(xiàng)目評(píng)級(jí)矩陣規(guī)模，若不做預(yù)處理，則需要對(duì)全部用戶和全部項(xiàng)目信息構(gòu)建評(píng)級(jí)矩陣，這樣在矩陣分解時(shí)會(huì)嚴(yán)重降低算法效率，占用大量?jī)?nèi)存。而通過(guò)聚類(lèi)構(gòu)建小規(guī)模的近鄰用戶-項(xiàng)目矩陣，可加快矩陣分解計(jì)算，利于算法模型的整體效率，且額外的聚類(lèi)代價(jià)遠(yuǎn)遠(yuǎn)小于大規(guī)模矩陣分解的消耗代價(jià)。

K-means聚類(lèi)處理為當(dāng)前用戶構(gòu)建了近鄰集合，由于興趣偏好相似的用戶傾向于購(gòu)買(mǎi)相同項(xiàng)目的思想，所以在近鄰用戶中進(jìn)行數(shù)據(jù)分析，可有效提高推薦的準(zhǔn)確度，實(shí)驗(yàn)證明這樣的設(shè)計(jì)思路的確對(duì)推薦中召回率和精確度有提升效果。

1.3 KMMD算法設(shè)計(jì)

本文將K-means算法與Funk-SVD矩陣分解算法結(jié)合，提出了KMMD算法。算法2的設(shè)計(jì)流程詳見(jiàn)如下。

算法2KMMD, 基于K-means的矩陣分解算法

輸入：User表示包含m個(gè)用戶的用戶屬性(User)數(shù)據(jù)集；Ua表示當(dāng)前待推薦用戶的屬性信息；Ratings表示包含m個(gè)用戶對(duì)n個(gè)項(xiàng)目的部分評(píng)級(jí)數(shù)據(jù)集；L表示推薦列表長(zhǎng)度；K表示聚類(lèi)簇?cái)?shù)

輸出：針對(duì)用戶Ua的推薦列表List

(1)對(duì)User進(jìn)行K-means聚類(lèi)分析，劃分為K個(gè)簇：C1,C2,...,CK；

(2)ifUa== 老用戶 then

(3)提取Ua所在簇Ca的所有對(duì)象元素，并從Ratings中篩選出這些對(duì)象元素的評(píng)級(jí)數(shù)據(jù)，構(gòu)建近鄰用戶-項(xiàng)目評(píng)級(jí)矩陣R；

(4)將R進(jìn)行Funk-SVD分解，得到U和V兩個(gè)低秩矩陣；

(5)矩陣重構(gòu)：R’ =U·V；

(6)在重構(gòu)評(píng)級(jí)矩陣R’中找到對(duì)Ua的重構(gòu)預(yù)測(cè)向量ra；

(7)else將Ua與簇中心求相似度，找到Ua歸屬的簇Ca；

(8)從Ratings中篩選出Ca簇中對(duì)象元素的評(píng)級(jí)數(shù)據(jù)，構(gòu)建近鄰用戶-項(xiàng)目評(píng)級(jí)矩陣R；

(9)將R進(jìn)行Funk-SVD分解，得到U和V兩個(gè)低秩矩陣；

(10)矩陣重構(gòu)：R’=U·V；

(11) 求得Ua與Ca中各對(duì)象元素的相似度Sima,i(i∈Ca)；

(12) 加權(quán)計(jì)算求得Ua的預(yù)測(cè)評(píng)級(jí)：

(5)

(13)end if

(14)對(duì)ra中各個(gè)項(xiàng)目預(yù)測(cè)值排序，選出前L個(gè)項(xiàng)目組成推薦列表List。

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

本實(shí)驗(yàn)采用數(shù)據(jù)集MovieLens-100K，使用召回率和精確度作為模型評(píng)價(jià)指標(biāo)，進(jìn)行參數(shù)影響及參數(shù)確定的實(shí)驗(yàn)，得到效果最佳的KMMD算法模型，并將其與2種傳統(tǒng)算法CBbyPortrait和MFbySVD做了對(duì)比實(shí)驗(yàn)。研究可得解析詳述如下。

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

基于MovieLens數(shù)據(jù)集[12]是由明尼蘇達(dá)大學(xué)的Grouplens研究項(xiàng)目收集整理。數(shù)據(jù)集獲取地址：http://files.grouplens.org/datasets/movielens/。實(shí)驗(yàn)具體選用的是MovieLens-100K。MovieLens-100K數(shù)據(jù)集包含943名用戶對(duì)1 682部電影的10萬(wàn)條評(píng)分記錄，評(píng)分采用5分制(1，2，3，4，5)。該數(shù)據(jù)集主要包含3個(gè)文件：用戶數(shù)據(jù)文件(u.user)、項(xiàng)目數(shù)據(jù)文件(u.item)和評(píng)分文件(u.data)，其中u.user包含用戶的人口統(tǒng)計(jì)信息，字段有：用戶標(biāo)識(shí)(user id)、年齡(age)、性別(gender)、職業(yè)(occupation)和郵編(zip code)；u.item包含電影項(xiàng)目的信息，字段有：電影標(biāo)識(shí)(movie id)、電影標(biāo)題(movie title)、上映日期(release date)、視頻發(fā)布日期(video release date)、數(shù)據(jù)源鏈接(IMDb URL)和類(lèi)別屬性(genres)；u.data包含完整的評(píng)級(jí)數(shù)據(jù)，字段有：用戶標(biāo)識(shí)(user id)、項(xiàng)目標(biāo)識(shí)(item id)、評(píng)分(rating)和時(shí)間戳(timestamp)。

2.2 模型評(píng)估指標(biāo)

本文采用混淆矩陣[13]中的精確度(Precision)和召回率(Recall)進(jìn)行算法模型評(píng)估。涉及到的參數(shù)和計(jì)算方法如下：TP(True Positive)表示將正類(lèi)預(yù)測(cè)為正類(lèi)；TN(True Negative)表示將負(fù)類(lèi)預(yù)測(cè)為負(fù)類(lèi)；FP(False Positive)表示將負(fù)類(lèi)預(yù)測(cè)為正類(lèi)，也稱(chēng)為誤報(bào)；FN(False Negative)表示將正類(lèi)預(yù)測(cè)為負(fù)類(lèi)，也稱(chēng)為漏報(bào)。

其中，召回率(Recall)和精確度(Precision)的計(jì)算公式為：

(6)

(7)

2.3 參數(shù)選取

為了得到KMMD算法的最佳效果，首先進(jìn)行控制變量實(shí)驗(yàn)，測(cè)試重要參變量的取值變化對(duì)算法效果的影響。KMMD算法的重要參變量有3個(gè)：K-means聚類(lèi)的聚類(lèi)種數(shù)K；矩陣分解的訓(xùn)練步數(shù)Steps；推薦列表長(zhǎng)度L。而Funk-SVD的學(xué)習(xí)率參變量α依據(jù)經(jīng)驗(yàn)設(shè)定為0.000 2。實(shí)驗(yàn)隨機(jī)選取MovieLens-100K數(shù)據(jù)集的80%作為訓(xùn)練集，余下20%作為測(cè)試集。研究中，將分3組進(jìn)行控制變量實(shí)驗(yàn)。研究?jī)?nèi)容詳見(jiàn)如下。

(1)Steps固定取50，L固定取10。觀察參數(shù)K的變化影響，結(jié)果如圖1所示。

(a) 粗粒度范圍

(b) 細(xì)粒度范圍

圖1中，實(shí)線實(shí)心倒三角表示精確度的變化趨勢(shì)，虛線實(shí)心圓圈表示召回率的變化趨勢(shì)。圖1(a)是在[5,100]范圍內(nèi)粗粒度驗(yàn)證K值變化對(duì)實(shí)驗(yàn)精度的影響，可以看到，隨著K值逐漸增大，召回率和精確度都是先增后降的趨勢(shì)，其極值在K取25-35的范圍內(nèi)取得。為進(jìn)一步獲取最佳K值的推薦效果，圖1(b)給出了在[25,35]閉區(qū)間范圍內(nèi)細(xì)粒度實(shí)驗(yàn)仿真。由實(shí)驗(yàn)結(jié)果可知，當(dāng)K值取29時(shí)，算法的當(dāng)前推薦效果最佳。

(2)K固定取29，L固定取10。觀察參數(shù)Steps的變化影響，結(jié)果如圖2所示。

圖2 Steps值變化影響

由實(shí)驗(yàn)結(jié)果可知，隨著Steps值的增大，召回率和精確度總體趨勢(shì)都是下降的，當(dāng)Steps值取[80,110]區(qū)間值時(shí)，其實(shí)驗(yàn)效果較好，為方便實(shí)驗(yàn)進(jìn)行，將Steps值取為100。

(3)Steps固定取100，K固定取29。觀察參數(shù)L的變化影響，結(jié)果如圖3所示。

圖3 L值變化影響

由實(shí)驗(yàn)結(jié)果可知，隨著L值的增大，召回率會(huì)呈現(xiàn)遞增趨勢(shì)，而精確度總體是呈現(xiàn)遞減趨勢(shì)，最終逐漸收斂平穩(wěn)。為確定L取具體何值時(shí)，可使推薦的整體效果較好，研究中還對(duì)圖3實(shí)驗(yàn)結(jié)果進(jìn)行F度量表示，即：

(8)

F度量賦予了召回率和精確度相等的權(quán)重，是兩者的調(diào)和均值。其結(jié)果如圖4所示?？芍贚值取15時(shí)，F(xiàn)值最高，綜合推薦效果最好。

圖4 F度量值變化

2.4 對(duì)比實(shí)驗(yàn)

為了驗(yàn)證KMMD算法模型的真實(shí)效果，選取了2種推薦算法模型與本文提出算法進(jìn)行比較。這2種算法的設(shè)計(jì)表述如下。

(1)CB(Content-based Recommendation)：基于內(nèi)容的推薦模型，通過(guò)召回用戶日志文件獲取與用戶有過(guò)交互的項(xiàng)目信息，再根據(jù)項(xiàng)目的屬性特征學(xué)習(xí)用戶的偏好興趣，可構(gòu)建用戶畫(huà)像，并以此計(jì)算用戶與待推薦項(xiàng)目匹配度，推薦與其過(guò)去已購(gòu)買(mǎi)過(guò)物品相似度高的商品。

(2)MF(Matrix Factorization)：傳統(tǒng)基于矩陣分解的推薦模型，通過(guò)用戶對(duì)項(xiàng)目的顯式評(píng)分?jǐn)?shù)據(jù)構(gòu)建用戶-項(xiàng)目評(píng)分矩陣，使用SVD奇異值分解矩陣后再進(jìn)行重構(gòu)，預(yù)測(cè)用戶對(duì)未購(gòu)買(mǎi)過(guò)的商品的評(píng)分，進(jìn)行推薦。

對(duì)比實(shí)驗(yàn)在MovieLens-100K數(shù)據(jù)集下進(jìn)行，使用了十折交叉驗(yàn)證法。根據(jù)控制變量實(shí)驗(yàn)結(jié)果，對(duì)KMMD算法的參數(shù)選取了K=29，Steps=100，L=15。實(shí)驗(yàn)結(jié)果對(duì)比見(jiàn)表1。對(duì)表1分析后可知，其研究結(jié)果的重點(diǎn)陳述見(jiàn)如下。

(1)召回率表現(xiàn)的是推薦效果的靈敏性，從該值的角度來(lái)分析，KMMD算法的效果最好，其相較于CB算法提升了15.64%，相較于MF算法提升了154%。說(shuō)明在靈敏性上，KMMD算法有了很大的提升。

(2)從精確度來(lái)看，KMMD算法的效果遠(yuǎn)高于其它兩個(gè)算法，比CB提升了30.43%，比MF提升了103%?？梢?jiàn)，KMMD算法在推薦的精確度上也有很不錯(cuò)的表現(xiàn)。

由實(shí)驗(yàn)可得，KMMD算法在召回率和精確度上都有很大提升，能為用戶提供更準(zhǔn)確的推薦。

表1 召回率和精確度對(duì)比

2.5 模型預(yù)測(cè)

該部分通過(guò)實(shí)驗(yàn)驗(yàn)證提出的KMMD算法可以對(duì)新用戶進(jìn)行有效推薦。實(shí)驗(yàn)是在包含943名用戶的MovieLens-100K數(shù)據(jù)集基礎(chǔ)上，仿照其數(shù)據(jù)格式，構(gòu)造了2名用戶基本屬性數(shù)據(jù)作為新用戶，作為用戶冷啟動(dòng)實(shí)驗(yàn)對(duì)象，數(shù)據(jù)如下：

(1)用戶a：年齡=24，性別=男(M)，職業(yè)=技術(shù)員(technician);

(2)用戶b：年齡=50，性別=女(F)，職業(yè)=作家(writer)。

實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 用戶冷啟動(dòng)預(yù)測(cè)

實(shí)驗(yàn)結(jié)果說(shuō)明，KMMD算法可以對(duì)新用戶進(jìn)行項(xiàng)目推薦，結(jié)果以評(píng)級(jí)高低排序。KMMD算法有效改善了用戶冷啟動(dòng)問(wèn)題。

3 結(jié)束語(yǔ)

將聚類(lèi)算法與協(xié)同過(guò)濾思想相結(jié)合，提出了一種基于K-means的矩陣分解推薦算法。首先通過(guò)實(shí)驗(yàn)分析不同參數(shù)對(duì)KMMD算法的召回率和精確度變化影響，得出算法的高效率參數(shù)配置。并進(jìn)行對(duì)照實(shí)驗(yàn)，比較傳統(tǒng)推薦算法與KMMD算法在MovieLens公開(kāi)數(shù)據(jù)集上的實(shí)驗(yàn)效果，得出結(jié)論，融合K-means聚類(lèi)后的矩陣分解算法確實(shí)有助于推薦準(zhǔn)確度的提高，且在引入用戶屬性數(shù)據(jù)的條件下，有效改善了用戶冷啟動(dòng)問(wèn)題。但該算法對(duì)項(xiàng)目冷啟動(dòng)問(wèn)題還難以處理。后續(xù)工作是將深度學(xué)習(xí)技術(shù)與推薦算法相融合，構(gòu)建多種推薦算法的組合排序，力求進(jìn)一步提升推薦算法的準(zhǔn)確度，并有效解決項(xiàng)目冷啟動(dòng)問(wèn)題。