基于最大互信息系數(shù)的信息推送模型構(gòu)建

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

(1.湖南農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院,長(zhǎng)沙410128;2.湖南省農(nóng)村農(nóng)業(yè)信息化工程技術(shù)研究中心,長(zhǎng)沙410128;3.湖南農(nóng)業(yè)大學(xué) 植物保護(hù)學(xué)院,長(zhǎng)沙410128;4.邵陽(yáng)學(xué)院 醫(yī)學(xué)院,湖南 邵陽(yáng)422000)

0 引 言

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

本文引入最大互信息系數(shù)(MIC)[2]作為用戶之間的相似性測(cè)度。MIC測(cè)度來(lái)源于信息論中的互信息測(cè)度,MIC經(jīng)不等間隔尋優(yōu)以矯正,具有能普適性檢測(cè)復(fù)雜非線性關(guān)系以及等價(jià)性的優(yōu)點(diǎn)。基于MIC測(cè)度所選近鄰集合具有信息更完整、準(zhǔn)確的優(yōu)點(diǎn)。本文以開源Movie Lens評(píng)分?jǐn)?shù)據(jù)集為仿真數(shù)據(jù)[3],以多種相似性測(cè)度為參比方法,結(jié)果表明,基于MIC的非線性方法能有效提高評(píng)分預(yù)測(cè)精度。

1 最大互信息系數(shù)(MIC)

1.1 兩變量關(guān)聯(lián)

關(guān)聯(lián)分析一般指基于某種相關(guān)性測(cè)度,評(píng)價(jià)兩個(gè)變量間的相似程度,測(cè)度得分值越大,表示兩個(gè)變量關(guān)聯(lián)程度越大[4]。

關(guān)聯(lián)測(cè)度的優(yōu)劣可采用普適性[5]和等價(jià)性[2]兩個(gè)指標(biāo)來(lái)度量。普適性表示該測(cè)度方法所能檢測(cè)到的函數(shù)關(guān)系的類型數(shù)量,檢測(cè)到的函數(shù)關(guān)系預(yù)測(cè)越多,其普適性越好。如Pearson相關(guān)系數(shù)僅對(duì)線性函數(shù)關(guān)系敏感,不能有效捕獲非線性函數(shù)關(guān)系,普適性較差。公平性表示等噪音的任意函數(shù)具有相等的關(guān)聯(lián)測(cè)度值。

1.2 MIC及其優(yōu)點(diǎn)

為解決大數(shù)據(jù)非線性關(guān)聯(lián)分析,由Reshef等[2]在2011年提出MIC測(cè)度,其本質(zhì)上是計(jì)算兩兩變量間的互信息值,但其在互信息計(jì)算過(guò)程中采用的是不等間隔尋優(yōu)法,并對(duì)互信息值進(jìn)行歸一化矯正,取值范圍為[0,1]。不等間隔尋優(yōu)使得MIC具有普適性的優(yōu)點(diǎn),歸一化矯正使其具有等價(jià)性優(yōu)點(diǎn)。

1.2.1 普適性

普適性是MIC最為重要的優(yōu)點(diǎn),即對(duì)任意函數(shù)關(guān)系,無(wú)論線性、非線性關(guān)系,在無(wú)噪音時(shí),其得分值均最大為1,面對(duì)兩個(gè)無(wú)關(guān)系的獨(dú)立變量,其得分值為0。表1列出了MIC與幾種常用的相關(guān)性測(cè)度[2],如Pearson相關(guān)系數(shù)[6,7]、Spearman相關(guān)系數(shù)[8]、基于核密度估計(jì)的互信息Mutual Information[2]、Cor GC系數(shù)[9]等,對(duì)不同函數(shù)關(guān)系的測(cè)度情況。

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

表1 不同函數(shù)關(guān)系下的多種測(cè)度值Table 1 Values of different functions in different measures

1.2.2 等價(jià)性

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

圖1 不同函數(shù)關(guān)系不同噪音下的MIC值Fig.1 MIC values of different functions under different noise

由圖1可知,隨著噪音增加,變量間的相關(guān)性降低,MIC值降低,對(duì)相同的噪音水平,不同函數(shù)的MIC值接近,顯然MIC具有較好的等價(jià)性。

1.3 MIC近似算法

MIC在本質(zhì)上是基于互信息的,但變量的離散化需要進(jìn)行遍歷尋優(yōu),屬于計(jì)算密集型方法[10]。對(duì)大樣本數(shù)據(jù),遍歷算法并不可行,David等[2]基于動(dòng)態(tài)規(guī)劃算法給出了快速近似算法。對(duì)給定的兩個(gè)變量x1、x2,其離散化分段點(diǎn)尋優(yōu),矯正過(guò)程如下:

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

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

(3)基于動(dòng)態(tài)規(guī)劃的x2變量分段點(diǎn)尋優(yōu)。遍歷上述第(2)步所給定的x2潛在分段點(diǎn)(保持x1均分兩段不變),并計(jì)算每種離散情況下的x1與x2的互信息值,計(jì)算公式如下:

定義最大互信息值對(duì)應(yīng)的分段點(diǎn)為x2分兩段的最優(yōu)分段點(diǎn)。在此基礎(chǔ)上,從剩余潛在分段點(diǎn)中確定最優(yōu)的第3個(gè)分段點(diǎn),直至第B/2－1個(gè)最優(yōu)分段點(diǎn),共劃分為B/2段。

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

(5)互信息矯正。上述得到的互信息經(jīng)最小分段數(shù)矯正即可轉(zhuǎn)換為對(duì)應(yīng)的MIC值,矯正公式為:

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

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

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

2.1 基于MIC的用戶相似性指標(biāo)

假定n個(gè)用戶對(duì)m個(gè)項(xiàng)目評(píng)分,第i個(gè)用戶對(duì)第j個(gè)項(xiàng)目的評(píng)價(jià)得分為R ij,R ij{i＝1,2,…,n;j＝1,2,…,m}。對(duì)目標(biāo)用戶I,可基于MIC得分表示其與其他用戶偏好性的相似程度,分別記為MIC_I_R i{i＝1,2,…,n}。

2.2 近鄰集合選擇

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

3 項(xiàng)目評(píng)分預(yù)測(cè)模型

對(duì)目標(biāo)用戶,每次基于其所有的近鄰集合U I_k作為訓(xùn)練樣本,可對(duì)其未評(píng)分的項(xiàng)目進(jìn)行預(yù)測(cè)評(píng)分。本文采用支持向量機(jī)(Support vector machine,SVM)作為回歸預(yù)測(cè)模型。

3.1 LIBSVM

本文所用SVM算法基于采用林志仁教授等[11]開發(fā)的LIBSVM平臺(tái)實(shí)現(xiàn),該程序包括Svmtrain與Svmpredict兩個(gè)主程序。前者用于模型訓(xùn)練,后者用于預(yù)測(cè)獨(dú)立測(cè)試樣本。

3.2 模型評(píng)價(jià)方式

以均方誤差(Mean square error,MSE)評(píng)價(jià)預(yù)測(cè)模型的優(yōu)劣,真實(shí)值與預(yù)測(cè)值間差異越小,MSE越小,即模型預(yù)測(cè)能力越好,其計(jì)算公式如下:

式中:y i為目標(biāo)用戶對(duì)第i個(gè)項(xiàng)目的真實(shí)評(píng)分;為預(yù)測(cè)的評(píng)分值;n為被預(yù)測(cè)的目標(biāo)用戶數(shù)。

3.3 參比模型

為驗(yàn)證近鄰集合影響項(xiàng)目評(píng)分的預(yù)測(cè)效果,從近鄰集合與建模方法兩個(gè)方向設(shè)計(jì)了參比模型。在近鄰集合篩選方面,選擇MIC、Pearson相關(guān)系數(shù)、互信息(MI)、Cor GC相關(guān)系數(shù)4種關(guān)聯(lián)測(cè)度,預(yù)測(cè)方法均為SVM。基于MIC篩選獲得近鄰集,本文選擇K近鄰法(KNN)、多元線性回歸(MLR)、人工神經(jīng)網(wǎng)絡(luò)(ANN)[12]、SVM四種建模方法?；贛IC近鄰集合篩選的項(xiàng)目評(píng)分預(yù)測(cè)模型構(gòu)建過(guò)程如圖2所示。

圖2 基于MIC的推送模型項(xiàng)目評(píng)分預(yù)測(cè)模型Fig.2 Push model project score prediction model based on MIC

4 結(jié)果與分析

4.1 數(shù)據(jù)來(lái)源

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

表2 前50個(gè)戶對(duì)前20部電影的評(píng)分表Table 2 Scores of top 50 households on top 20 films

表3 合并后的評(píng)分表Table 3 Combined scores

4.2 基于不同相似性測(cè)度的模型預(yù)測(cè)性能

對(duì)每個(gè)待測(cè)樣本,基于給定相似性測(cè)度,從訓(xùn)練集中選擇相似性最大的K個(gè)樣本構(gòu)建SVM預(yù)測(cè)模型。本次仿真K取值為60。4種預(yù)測(cè)模型結(jié)果見圖3。

圖3 不同相似性測(cè)度的預(yù)測(cè)精度Fig.3 Prediction accuracy of different similarity measures

由圖3結(jié)果可知,基于MIC關(guān)聯(lián)測(cè)度的模型預(yù)測(cè)效果最好;Cor GC測(cè)度能部分檢測(cè)非線性關(guān)聯(lián),其篩選近鄰集合的預(yù)測(cè)精度略低于MIC模型,但明顯優(yōu)于線性測(cè)度Pearson相關(guān)系數(shù)和MI。

4.3 不同建模方法預(yù)測(cè)性能比較

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

圖4 不同建模方法預(yù)測(cè)精度Fig.4 Prediction accuracy of different modeling methods

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

4.4 MIC閾值對(duì)模型結(jié)果的影響

設(shè)置不同水平的MIC閾值,得到多個(gè)近鄰集合,以此為預(yù)測(cè)樣本構(gòu)建預(yù)測(cè)模型,結(jié)果見圖5。

圖5 MIC不同閾值對(duì)預(yù)測(cè)精度的影響Fig.5 Effects of different MIC threshold on prediction accuracy

由圖5結(jié)果可知,SVM模型對(duì)MIC閾值不敏感,當(dāng)閾值從0.8增加到0.9時(shí),其預(yù)測(cè)精度小幅度下降,可能是因?yàn)橛?xùn)練樣本減少導(dǎo)致。KNN模型穩(wěn)定性較SVM差。

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

通過(guò)提高待評(píng)價(jià)項(xiàng)目的評(píng)分預(yù)測(cè)精度,可以對(duì)目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目的偏好程度做出準(zhǔn)確的評(píng)估,確保向用戶推送的信息是其真正感興趣的。因此,構(gòu)建準(zhǔn)確的項(xiàng)目評(píng)分預(yù)測(cè)模型是協(xié)同過(guò)濾推薦系統(tǒng)的關(guān)鍵,訓(xùn)練樣本選擇(近鄰集合篩選)的信息完善程度是構(gòu)建高精度項(xiàng)目評(píng)分模型的基礎(chǔ)?；赑earson相關(guān)系數(shù)表征用戶相似性,并以此篩選近鄰集合是最常用的方法。該方法具有簡(jiǎn)單、快速的優(yōu)點(diǎn),但具有普適性差的特點(diǎn),無(wú)法有效地檢測(cè)用戶偏好性的復(fù)雜非線性關(guān)系。本文引入具有普適性優(yōu)點(diǎn)的兩變量關(guān)聯(lián)測(cè)度MIC。仿真結(jié)果表明,相比傳統(tǒng)線性關(guān)聯(lián)測(cè)度,基于普適性測(cè)度MIC所選的近鄰集合,項(xiàng)目評(píng)分預(yù)測(cè)模型精度更高,并具有穩(wěn)定性好的優(yōu)點(diǎn)。

[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]陳誠(chéng),廖桂平,史曉慧.個(gè)性化信息推送服務(wù)的用戶模型研究[J].情報(bào)科學(xué),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的微博信息推送系統(tǒng)用戶興趣模型[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版,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.