基于最大互信息系數的信息推送模型構建

譚泗橋,張 席,李 釬,艾 陳

(1.湖南農業大學 信息科學技術學院,長沙410128;2.湖南省農村農業信息化工程技術研究中心,長沙410128;3.湖南農業大學 植物保護學院,長沙410128;4.邵陽學院 醫學院,湖南 邵陽422000)

0 引 言

基于內容的推薦系統與基于協同過濾的推薦系統是信息推送服務的兩種主要形式。協同過濾系統推薦過程簡單,可提供個性化搜索服務,較前者應用更廣泛。協同過濾推薦系統一般包括兩個主要步驟:①基于用戶已評分項目計算用戶間的相似性系數,并以相似性最大原則篩選目標用戶的近鄰集合(用戶偏好相似);②基于鄰居集合的已評分項目為目標用戶篩選潛在的推送信息。因此,對于協同過濾推薦系統,選擇信息完善的近鄰集合是保證推薦信息的整體質量的關鍵點,若獲得的最近鄰集合信息不完整,則后續預測得到的感興趣信息錯誤概率會顯著增加,導致信息推薦失敗。在傳統協同過濾推薦系統中,與目標用戶相似性最高的K個用戶可入選近鄰集合[1],但均采用Pearson相關系數、cosine相似性和均方差相似性等線性相似性測度,存在無法呈現用戶間復雜非線性關系的缺陷,篩選出的近鄰集合信息不完整,導致推薦準確度不高。

本文引入最大互信息系數(MIC)[2]作為用戶之間的相似性測度。MIC測度來源于信息論中的互信息測度,MIC經不等間隔尋優以矯正,具有能普適性檢測復雜非線性關系以及等價性的優點。基于MIC測度所選近鄰集合具有信息更完整、準確的優點。本文以開源Movie Lens評分數據集為仿真數據[3],以多種相似性測度為參比方法,結果表明,基于MIC的非線性方法能有效提高評分預測精度。

1 最大互信息系數(MIC)

1.1 兩變量關聯

關聯分析一般指基于某種相關性測度,評價兩個變量間的相似程度,測度得分值越大,表示兩個變量關聯程度越大[4]。

關聯測度的優劣可采用普適性[5]和等價性[2]兩個指標來度量。普適性表示該測度方法所能檢測到的函數關系的類型數量,檢測到的函數關系預測越多,其普適性越好。如Pearson相關系數僅對線性函數關系敏感,不能有效捕獲非線性函數關系,普適性較差。公平性表示等噪音的任意函數具有相等的關聯測度值。

1.2 MIC及其優點

為解決大數據非線性關聯分析,由Reshef等[2]在2011年提出MIC測度,其本質上是計算兩兩變量間的互信息值,但其在互信息計算過程中采用的是不等間隔尋優法,并對互信息值進行歸一化矯正,取值范圍為[0,1]。不等間隔尋優使得MIC具有普適性的優點,歸一化矯正使其具有等價性優點。

1.2.1 普適性

普適性是MIC最為重要的優點,即對任意函數關系,無論線性、非線性關系,在無噪音時,其得分值均最大為1,面對兩個無關系的獨立變量,其得分值為0。表1列出了MIC與幾種常用的相關性測度[2],如Pearson相關系數[6,7]、Spearman相關系數[8]、基于核密度估計的互信息Mutual Information[2]、Cor GC系數[9]等,對不同函數關系的測度情況。

由表1可知,以上5種測度均能有效檢測出線性函數關系“Linear”。Pearson相關系數屬于經典的線性相關測度,僅能較好地檢出“Linear”線性關系,對Cubic、Exponential、Parabolic擬線性關系有部分檢測能力,對其他復雜非線性關系基本無法檢測。Mutual Information互信息、Cor GC測度較Pearson線性關系普適性有提升,對Parabolic等非線性函數關系有一定的檢測能力,但其普適性均弱于MIC測度。對于表中全部函數關系,MIC得分值均為1,表明了其優異的普適性特征。

表1 不同函數關系下的多種測度值Table 1 Values of different functions in different measures

1.2.2 等價性

如表1所示,互信息測度除存在普適性差的缺陷外,其得分值為[0,＋∞],存在不同數據間可比性差的缺點。給定兩種函數關系,若加上等水平的噪音,其相關系數理應相同,若某一測度指標計算獲得的相關系數差異越小,表明該測度等價性越高,反之等價性越差。圖1基于6種函數關系示例了MIC的等價性[2]。

圖1 不同函數關系不同噪音下的MIC值Fig.1 MIC values of different functions under different noise

由圖1可知,隨著噪音增加,變量間的相關性降低,MIC值降低,對相同的噪音水平,不同函數的MIC值接近,顯然MIC具有較好的等價性。

1.3 MIC近似算法

MIC在本質上是基于互信息的,但變量的離散化需要進行遍歷尋優,屬于計算密集型方法[10]。對大樣本數據,遍歷算法并不可行,David等[2]基于動態規劃算法給出了快速近似算法。對給定的兩個變量x1、x2,其離散化分段點尋優,矯正過程如下:

(1)x1均分。假定x1僅離散化為兩段,首先按升序排列變量x1,再根據樣本數量相等的原則,按排序均分x1為兩段,該過程即固定x1為兩段。

(2)在x1均分兩段情況下,確定變量x2潛在分段點。互信息具有分段數越多得分越高的特點,為保證MIC得分的準確性,規定x1變量與x2變量的分段數必須滿足限制x×y≤B(B＝n0.6),x表示變量x1的分段數,y表示變量x2的分段數,n表示成對的樣本數目。例如,在x1已均分兩段時,變量x2最多可劃分B/2段。一方面為保證x2分段準確性,另一方面為降低計算復雜度,采用均分的原則,可將x2平均分為c×B/2個小簇,c可根據數據樣本數自行給定,如5或15等,并且在均分x2過程中,對應x1取值相等的樣本應劃分在同一個小簇中。這些將x2劃分為不同小簇的樣本點即為x2的潛在分段點。

(3)基于動態規劃的x2變量分段點尋優。遍歷上述第(2)步所給定的x2潛在分段點(保持x1均分兩段不變),并計算每種離散情況下的x1與x2的互信息值,計算公式如下:

定義最大互信息值對應的分段點為x2分兩段的最優分段點。在此基礎上,從剩余潛在分段點中確定最優的第3個分段點,直至第B/2－1個最優分段點,共劃分為B/2段。

(4)x1變量均分多段尋優。當x2僅離散化為兩段時,x1最多可被均分B/2段,依次將變量x1均分為3,4,…,B/2段,并重復第(2)(3)步,獲得對應x2變量的最優離散化段數。最終可獲得一個不完全的尋優互信息得分矩陣I ij,矩陣中的每一元素為x1均分為i段、x2離散化j段時x1與x2之間的互信息值。

(5)互信息矯正。上述得到的互信息經最小分段數矯正即可轉換為對應的MIC值,矯正公式為:

(6)均分方向互換,將x2均分,尋優x1變量,重復第(2)～(5)步,可獲得均分x2方向的MIC得分矩陣。

(7)MIC得分定義為上述兩個得分矩陣中最大的得分值。

2 基于MIC相似性的近鄰集合選擇

2.1 基于MIC的用戶相似性指標

假定n個用戶對m個項目評分,第i個用戶對第j個項目的評價得分為R ij,R ij{i＝1,2,…,n;j＝1,2,…,m}。對目標用戶I,可基于MIC得分表示其與其他用戶偏好性的相似程度,分別記為MIC_I_R i{i＝1,2,…,n}。

2.2 近鄰集合選擇

按MIC_I_R i大小排序,目標用戶I的近鄰集合則為與其相似性最高的K個用戶,記為U I_k,對不同的閾值,1≤K≤n。

3 項目評分預測模型

對目標用戶,每次基于其所有的近鄰集合U I_k作為訓練樣本,可對其未評分的項目進行預測評分。本文采用支持向量機(Support vector machine,SVM)作為回歸預測模型。

3.1 LIBSVM

本文所用SVM算法基于采用林志仁教授等[11]開發的LIBSVM平臺實現,該程序包括Svmtrain與Svmpredict兩個主程序。前者用于模型訓練,后者用于預測獨立測試樣本。

3.2 模型評價方式

以均方誤差(Mean square error,MSE)評價預測模型的優劣,真實值與預測值間差異越小,MSE越小,即模型預測能力越好,其計算公式如下:

式中:y i為目標用戶對第i個項目的真實評分;為預測的評分值;n為被預測的目標用戶數。

3.3 參比模型

為驗證近鄰集合影響項目評分的預測效果,從近鄰集合與建模方法兩個方向設計了參比模型。在近鄰集合篩選方面,選擇MIC、Pearson相關系數、互信息(MI)、Cor GC相關系數4種關聯測度,預測方法均為SVM。基于MIC篩選獲得近鄰集,本文選擇K近鄰法(KNN)、多元線性回歸(MLR)、人工神經網絡(ANN)[12]、SVM四種建模方法。基于MIC近鄰集合篩選的項目評分預測模型構建過程如圖2所示。

圖2 基于MIC的推送模型項目評分預測模型Fig.2 Push model project score prediction model based on MIC

4 結果與分析

4.1 數據來源

本文所用仿真數據為Movie Lens網站開源的電影評分數據,數據集包含了943位用戶對1682部電影的100 000條評分記錄,評分值分為5個等級,用1～5代表,用戶對某部電影越感興趣,評分值越大。表2為部分用戶對20部電影的評分情況。為降低數據稀疏性,將1682部電影合并為Action、Children′s、Crime、Documentary、Sci-Fi、War等18種類型。每個類型的評分值為用戶對該類型電影評分的平均值。表3為部分合并后的評分矩陣。將全部數據隨機分成兩部分,80%用戶作為訓練集,20%用戶作為測試集。

表2 前50個戶對前20部電影的評分表Table 2 Scores of top 50 households on top 20 films

表3 合并后的評分表Table 3 Combined scores

4.2 基于不同相似性測度的模型預測性能

對每個待測樣本,基于給定相似性測度,從訓練集中選擇相似性最大的K個樣本構建SVM預測模型。本次仿真K取值為60。4種預測模型結果見圖3。

圖3 不同相似性測度的預測精度Fig.3 Prediction accuracy of different similarity measures

由圖3結果可知,基于MIC關聯測度的模型預測效果最好;Cor GC測度能部分檢測非線性關聯,其篩選近鄰集合的預測精度略低于MIC模型,但明顯優于線性測度Pearson相關系數和MI。

4.3 不同建模方法預測性能比較

MIC測度所選近鄰集合預測精度最高,因此,選擇該近鄰集合作為訓練樣本,用于比較不同建模方法預測性能。圖4為KNN、ANN、MLR和SVM四種方法的預測效果。

圖4 不同建模方法預測精度Fig.4 Prediction accuracy of different modeling methods

在4種建模方法中,MLR模型預測精度最差,MSE為2.115,該模型屬于典型線性模型,表明用戶評分之間呈現復雜非線性關系,SVM模型屬于非線性模型,其預測精度在參比模型中最優。KNN以近鄰集合項目評分均值作為預測樣本,信息完整性不足,影響預測精度。MIC測度能普適性檢測線性、非線性關系,能篩選信息完整的近鄰集合,所以KNN模型也能獲得較優結果。

4.4 MIC閾值對模型結果的影響

設置不同水平的MIC閾值,得到多個近鄰集合,以此為預測樣本構建預測模型,結果見圖5。

圖5 MIC不同閾值對預測精度的影響Fig.5 Effects of different MIC threshold on prediction accuracy

由圖5結果可知,SVM模型對MIC閾值不敏感,當閾值從0.8增加到0.9時,其預測精度小幅度下降,可能是因為訓練樣本減少導致。KNN模型穩定性較SVM差。

5 結束語

通過提高待評價項目的評分預測精度,可以對目標用戶對未評分項目的偏好程度做出準確的評估,確保向用戶推送的信息是其真正感興趣的。因此,構建準確的項目評分預測模型是協同過濾推薦系統的關鍵,訓練樣本選擇(近鄰集合篩選)的信息完善程度是構建高精度項目評分模型的基礎。基于Pearson相關系數表征用戶相似性,并以此篩選近鄰集合是最常用的方法。該方法具有簡單、快速的優點,但具有普適性差的特點,無法有效地檢測用戶偏好性的復雜非線性關系。本文引入具有普適性優點的兩變量關聯測度MIC。仿真結果表明,相比傳統線性關聯測度,基于普適性測度MIC所選的近鄰集合,項目評分預測模型精度更高,并具有穩定性好的優點。

[1]Ahn H J.A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem[J].Information Sciences,2008,178(1):37-51.

[2]David N R,Yakir A R,Hilary K F,et al.Detecting novel associations in large data sets[J].Science,2011,334:1518-1541.

[3]Sarwar B,Karypis G,Konstan J,et al.Item-based collaborative filtering recommendation algorithms[C]∥Proc of the 10th International Conference on World Wide Web,Hong Kong,China,2001:285-295.

[4]Hastie T,Tibshirani R,Friedman J H.The Elements of Statistical Learning:Data Mining,Inference,and Prediction[M].New York:Springer Verlag,2009.

[5]陳誠,廖桂平,史曉慧.個性化信息推送服務的用戶模型研究[J].情報科學,2014,32(11):71-76.Chen Cheng,Liao Gui-ping,Shi Xiao-hui.Model of user for personalized information push service[J].Information Science,2014,32(11):71-76.

[6]Sedgwick P.Pearson′s correlation coefficient[J].Bmj,2012,345:e4483-e4484.

[7]Mudelsee M.Estimating Pearson′s correlation coefficient with bootstrap confidence interval from serially dependent time series[J].Mathematical Geology,2003,35(6):651-665.

[8]繆平,陳盛雙,何云麗.基于SVMs的微博信息推送系統用戶興趣模型[J].武漢理工大學學報:信息與管理工程版,2013,35(4):547-550.Miao Ping,Chen Sheng-shuang,He Yun-li.User interest model in MICroblog information push system based on SVMs[J].Journal of Wuhan University of Technology(Information&Management Engineering),2013,35(4):547-550.

[9]Delicado P,Smrekar M.Measuring non-linear dependence for two random variables distributed along a curve[J].Statistics and Computing,2009,19(3):255-269.

[10]Yuan C,Ying Z,Feng L,et al.A new algorithm to optimize maximal information coefficient[J].Plos One,2016,11(6):e0157567.

[11]Chang C C,Lin C J.LIBSVM:a library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,27(2):1-27.

[12]Ji L,Wang X D,Yang X S,et al.Back-propagation network improved by conjugate gradient based on genetic algorithm in QSAR study on endocrine disruptingche MICals[J].Chinese Science Bulletin,2008,53(1):33-39.