K-means算法在隱語義模型中的應用*

范玉強　龍慧云　吳　云

(貴州大學計算機科學與技術學院　貴陽　550025)

?

K-means算法在隱語義模型中的應用*

范玉強龍慧云吳云

(貴州大學計算機科學與技術學院貴陽550025)

摘要隱語義模型(LFM)是文本挖掘領域的重要模型,將它應用于推薦系統的評分預測具有預測精度高和占用內存小的優點。但由于時間開銷較大,LFM模型并不適合用于處理大規模稀疏矩陣。針對此問題,論文將K-means算法引入到LFM模型的評分數據處理,得到改進模型K-LFM。在K-LFM模型中,利用K-means算法對評分矩陣中的用戶和項目數據進行聚類處理,然后重構評分矩陣降低原始矩陣的稀疏程度和矩陣規模,最后用重構后的評分矩陣訓練模型,預測評分。通過在movielens數據集上實驗發現K-LFM模型在運行時間上較LFM模型有大幅降低,而預測精度沒有受到明顯影響。

關鍵詞隱語義模型; K-means算法; 評分矩陣; K-LFM

Class NumberTP391.1

1　引言

2　算法描述

2.1K-means算法

K-means是一種簡單有效的經典聚類算法。算法采用計算屬性距離的方式來度量樣本屬性間的相似性,距離越短則樣本間的相似性越高。通過計算樣本到簇心的距離可以將n個樣本劃分到指定的k個簇中。

算法:K-means(S,k),S={x1,x2,…,xn}

輸入:數據對象集合S,聚類數目k

輸出:k個聚類中心Zj及k個聚類數據對象集合Cj;

Begin

m=1;

initializeZj,j∈[1,k];

repeat

fori=1 tondo

begin

forj=1 tokdo

computeD(Si,Zj)=|Si-Zj|;

ifD(Si,Zj)=minD(Si,Zj) thenSi∈Cj;

end;

m=m+1

forj=1 tokdo

Until |Jc(m)-Jc(m-1)|<ε;

End

2.2LFM模型

在訓練集上以均方根誤差RMSE作為指標,通過最小化RMSE可以學習獲得P,Q矩陣使訓練集預測誤差最小[8]。即用優化的方法最小化損失函數:

其中λ(‖pu‖2+‖qi‖2)是防止過擬合項,λ是正則化參數。

3　K-LFM模型

為了解決LFM模型在處理規模龐大的稀疏矩陣時效率較低的問題,K-LFM模型采用K-means算法處理評分矩陣。K-LFM模型分別從樣本選取、重構評分矩陣和評分計算三個方面對LFM模型進行了修改。

3.1樣本選取

LFM模型中樣本的選取方法為:對單個用戶U選取所有它有過行為的項目(正樣本)和剩余的項目中隨機的選取等量的項目(負樣本)作為u的訓練集K{(u,i)}[9～10]。這種取樣方法減小了矩陣規模,但忽略了項目的完備性。在K-LFM模型的樣本選取中,我們利用K-means算法將所有的用戶和項目根據屬性進行聚類,把聚類后的結果作為樣本數據訓練模型。

3.2重構評分矩陣

為了減小原始評分矩陣規模,K-LFM模型采用K-means算法重構評分矩陣。在計算用戶類對項目類的評分過程中,活躍用戶和熱門項目對評分影響權較大。所以在重構評分矩陣過程中,以用戶活躍度和項目流行度做為權重加權計算評分。

重構前的原始評分矩陣如圖1所示。

由用戶活躍度和項目流行度重構評分矩陣:

其中ni,nu分別為當前用戶有過評分的項目數目和對當前項目評過分的用戶數目;NI,NU分別為項目數量和用戶數量。

用戶ui對項目類Cij的評分計算方法:

(注:N(Ci)表示項目類Ci中元素的數量)

通過上述處理后原始評分矩陣和重構后的評分矩陣圖2所示,其中k≤m,r≤n。

圖1　原始評分矩陣

圖2　分類后的評分矩陣

3.3評分計算

4　實驗及結果分析

為了充分考慮用戶和項目間的內在屬性,實驗數據集應當包含用戶和項目的屬性信息以及評分信息。Movielens數據集分為100K、1M、10M三個規模,分別包含了1000個用戶對1700部電影的100,000條評分信息,6000個用戶對4000部電影的1,000,000條評分信息和72,000名用戶對10,000部電影的10,000,000條評分信息。本文采用100K規模的數據集進行實驗,并將數據集按4∶1的比例分為訓練集和測試集。訓練集用來訓練LFM的模型參數:隱特征個數(F),學習效率(α),正則化參數(λ),以及迭代次數(k);測試集用來測試模型的推薦效果。

4.1實驗結果

在訓練集上,根據用戶的年齡、性別、職業等屬性信息利用K-means算法將用戶聚類;項目信息則根據影片題材進行劃分。通過實驗發現943位用戶分為60類時具有較好的聚類效果。選取對分類影響最為顯著的年齡和職業屬性畫出聚類結果如圖3所示。在圖3中,不同的形狀和顏色分別代表不同的用戶類,同一類中簇心用大圖案顯示。

圖3　用戶聚類效果圖

利用分類后的結果構造新的評分矩陣R′,原始評分矩陣為R。分別在R和R′上訓練出LFM模型參數。通過實驗我們發現隱含特征個數F對實驗影響較大,固定α=0.002,λ=0.02,k=100。在測試集上,利用RMSE作為衡量指標得到LFM和K-LFM模型的預測精度如圖4所示。

圖4　模型預測精度

在實驗環境為AMD FX(tm)-6100 CPU 4GB RAM電腦上。固定模型參數:F=45,α=0.002,λ=0.02。不同迭代次數下LFM模型和K-LFM模型的執行時間如圖5所示。

圖5　模型運行時間

4.2結果分析

通過實驗發現LFM模型和K-LFM模型在預測精度方面,隨著隱含特征數的增加,模型預測精度都有一定幅度的提高。在運行時間上,LFM模型的運行時間主要來自于模型訓練耗時,所以運行時間與迭代次數成線性增長。而K-LFM模型的運行時間由K-means聚類和模型訓練兩部分構成。雖然K-means在處理數據過程中占據了部分運行時間,但它大大地降低了評分矩陣的規模,降低了模型訓練的總耗時。所以在迭代次數較小的情況下,K-LFM的運行時間略高于LFM,而隨著迭代次數的增加K-LFM的運行時間明顯低于LFM模型。

5　結語

針對傳統LFM模型在處理大規稀疏矩陣時效率較低的問題,本文將算法應用于LFM模型的評分數據處理,提出了K-LFM改進模型。通過實驗發現K-LFM模型在沒有明顯損失預測精度的情況下,運行時間較LFM模型得到大幅降低。對于模型的推薦結果是否能更好地滿足多樣性和個性化的需求,將在下一步的工作中進行研究。

參 考 文 獻

[1] Billsus D, Pazzani M J. Learning collaborative information filter[C]//Proceeding of International Conference on Machine Learning, San Francisco,1998:48-55.

[2] Paterek A. Improving regularized singular value decomposition for collaborative filtering[C]//Proceedings of KDD Cup and Workshop, California,2007:39-42.

[3] 方耀寧,郭云飛,蘭巨龍.基于Logistic函數的貝葉斯概率矩陣分解算法[J].電子與信息學報,2014,36(3):715-720.

FANG Yaoning, GUO Yunfei, LAN Julong. A Bayesian Probablistic Matrix Factorization Algorithm Based on Logistic Function[J]. Journal of Electrionic & Informatiom Technology,2014,36(3):715-720.

[4] Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering mode[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York,2008:426-434.

[5] Jian Cheng. Group latent factor model for recommendation with multiple user behaviors[J]. ACM July,2014.

[6] 張玉芳,毛嘉莉,熊忠陽.一種改進的k-means算法[J].計算機應用,2003,23(8):33-36.

ZHANG Yufang, MAO Jiali, XIONG Zhongyang. An Improved K-means Algorithm[J]. Computer Applications,2003,23(8):33-36.

[7] 魯權,王如龍,張錦.融合領域模型與隱語義模型的推薦算法[J].計算機工程與應用,2013,49(19):101-103.

LU Quan, WANG Rulong, ZHANG Jin. Recommender algorithm combined with neighborhood model and Computer Engineering and Applications[J]. 2013,49(19):101-103.

[8] 項亮.推薦系統實踐[M].北京:人民郵電出版社,2012:18-19.

XIANG Liang. Recommendation System Practice[M]. Beijing: Post & Telecom Press,2012:18-19.

[9] Rong Pan, Martin Scholz. Mind the Gaps: Weighting the unknown in Large-Scale One-Class Collaborative Filtering[C]//KDD’09, New York,2009:65-68.

[10] Quanquan GU, Jie Zhou. Co-Clustering on Manifolds[C]//KDD’09, New York,2009:269-274.

收稿日期:2015年10月8日,修回日期:2015年11月21日

基金項目:貴州省科學技術基金項目(編號:黔科合J字[2010]2100號);貴州大學引進人才科研項目(編號:貴大人基合字(2009)029號)資助。

作者簡介:范玉強,男,碩士研究生,研究方向:人工智能與模式識別。龍慧云,女,副教授,研究方向:Web服務的形式化分析。吳云,男,副教授,研究方向:云計算。

中圖分類號TP391.1

DOI:10.3969/j.issn.1672-9722.2016.04.002

Application of K-means Algorithm in Latent Factor Model

FAN YuqiangLONG HuiyunWU Yun

(College of Computer Science and Technology, Guizhou University, Guiyang550025)

AbstractLatent Factor Model(LFM) is an important model widely used in text mining. It has the advantage of high precision and low memory cost in rating prediction. However LFM model is not suitable for processing large-scale sparse matrix. In order to improve the performance, K-means algorithm is introduced to deal with rating data into LFM. This new model is called K-LFM. First of all, K-means is used to classify user and item information in K-LFM. And then the rating matrices are refactored to reduce the scale and sparse degree of orignal matrix. Finally training model with refactoring matix, can get predict rating. The experiment on public data set movielens shows that K-LFM model is superior to LFM model on processing efficiency. Besides, the prediction accuracy isn’t significantly affected.

Key Wordslatent factor model, K-means algorithm, rating matrix, K-LFM