基于有效特征子集提取的高效推薦算法①

于 旭,王前龍,徐凌偉,田 甜,徐其江,崔煥慶

1(青島科技大學 信息科學與技術學院,青島 266061)

2(山東科技大學 山東省智慧礦山信息技術重點實驗室,青島 266590)

3(山東建筑大學,濟南 250101)

4(山東信息職業技術學院 軟件系,濰坊 261061)

隨著互聯網的快速發展,人們正處于一個信息爆炸性增長的時代.人們從海量信息中獲取對自己有價值的信息越來越困難.推薦系統[1,2]正是當前解決這一問題最有效的技術之一.當前在電子商務[3]、餐飲[4]、交通運輸[5]等領域都存在著各種形式的推薦系統,但人們對當前推薦系統的效果還不能完全滿意,而且大部分推薦系統僅服務于單一領域.協同過濾(collaborative filtering)算法[6]是推薦系統中使用最廣泛、最成功的方法之一,它可以歸結為分析表格數據,即用戶項目評分矩陣.

然而,在現實生活中,人們往往很少對項目進行評分,這導致了用戶項目評分矩陣非常稀疏.稀疏化情況的加劇,使得近鄰尋找的復雜度急劇增加,推薦系統的性能顯著下降,稀疏性已經成為大多數單領域域協同過濾算法的一個瓶頸[7].為了緩解這一問題,最近人們提出了一些跨域推薦方法.跨域推薦是將多個領域的數據聯合起來,共同作用于目標域的推薦系統.這些方法有效的緩解了目標域的稀疏性問題.目前對此方面的研究主要有:Berkovsky 等人[8]提到一個基于鄰居的CDCF(N-CDCF),可以被視為基于內存的方法的跨領域擴展,即N-CF.Hu 等[9]提到基于矩陣分解的CDCF(MF-CDCF),其可以被視為矩陣分解方法的跨領域版本.Singh 和Gordon[10]提出了一種集體矩陣分解(CMF)模型.CMF 將用戶維度上所有域的評估矩陣相結合,以便通過普通用戶因子矩陣傳遞知識.Li 等人[11]提出了一種用于推薦系統的基于碼本的知識轉移(CBT).他們首先將輔助評級矩陣中的評級壓縮為被稱為碼本的信息豐富且緊湊的集群級評分模式表示.香港科技大學潘微科等人提出了一種對二元信息矩陣(喜歡與不喜歡,購買與不購買等)和評分矩陣進行聯合分解的方案[12],也有效地降低了目標領域數據稀疏所帶來了的問題,但是該模型要求兩個矩陣中的用戶、項目必須嚴格一致.文獻[13]則同時對兩個領域中的二元信息矩陣和用戶評論信息進行聯合簡歷模型,得到用戶的特征向量；并訓練得到兩個非線性的映射函數,一個用于將源領域中的用戶偏好信息映射到目標領域中,另一個則用于將源領域中的用戶興趣轉換為目標領域中用戶的興趣.然而,他們僅僅是對特征進行隨機或者是簡單的選取,并沒有對選取的特征進行有效的評判.

但由于每個領域都有大量的評分數據,當我們將這些領域聯合進行處理的時候,會有更高維度的特征空間,這不僅產生高額的計算開銷,甚至可能會導致推薦系統崩潰.因此進行合理有效的特征子集選取成為跨域推薦系統必須要解決的問題.

在本文的研究中,我們假設兩個具有強相關性的領域,比如圖書和電影,他們具有相似的體裁和特性,所以我偶們認為圖書和電影是具有高相關性的領域.本文我們采用在不同領域上共享用戶的亞馬遜數據集,基于特征之間的相關性分析,對輔助域特征以無監督聚類的方式進行特征子集選取,刪除掉相關性較大和冗余的特征,篩選出對目標域最有價值的信息,來提高推薦的準確率和效率.實驗結果表明,我們提出的基于有效特征子集選取的高效推薦算法比目前的推薦算法有更好的性能.

本文的安排如下:第2 節我們介紹相關的背景知識,第3 節來詳細闡述本文提出的基于有效子集提取的高效推薦算法,第4 節我們做了一些實驗來測試我們提出的模型的性能,我們將在第5 節中給出結論.

1 相關的背景知識

1.1 特征子集選取的相關知識

特征選擇[14,15](feature selection)也稱特征子集選擇(Feature Subset Selection,FSS),或屬性選擇(attribute selection).是指從已有的M個特征(feature)中選擇N個特征使得系統的特定指標最優化,是從原始特征中選擇出一些最有效特征以降低數據集維度的過程,是提高學習算法性能的一個重要手段,也是模式識別中關鍵的數據預處理步驟.目前已有不少文獻中提出了有監督學習的特征選擇算法,但是僅有少數文章對于無監督學習的特征選擇問題做了研究.無監督學習的特征選擇問題就是依據一定的判斷準則,選擇一個特征子集能夠最好地覆蓋數據的自然分類.目前的方法有基于遺傳算法的特征選擇方法[16]、基于模式相似性判斷的特征選擇方法[17]和信息增益的特征選擇方法[18],這幾種方法沒有考慮特征之間的相關性和特征對分類的影響.

1.2 UV 分解技術

矩陣的UV 分解技術[19]是將原始用戶-項目評分矩陣R分解為用戶特征矩陣P和項目特征矩陣Q,即每個用戶u(或者項目i)由一個實數向量pu(或者qi)表示,而這個向量的維度遠遠小于用戶或者商品的個數.對于用戶u來說,pu代表用戶u的用戶的喜好,類似,對于項目i,qi代表項目i的特性.他們的內積qTipu表示用戶u對項目i的評分,所以,用戶的評分可以用如下公式表示:

是模型的預測評分矩陣.

為了得到P和Q,我們采用最小化的方法為:

其中,rui是評分矩陣R的第u行、第i列的已知打分值,pu是用戶特征矩陣P的第u行；qi是項目特征矩陣Q的第i行；是為了避免過擬合而附加的正則項.

由于輔助域是稀疏度相對較低,所以我們可以利用UV 分解技術對輔助域進行數據的填充,這非常有利于對輔助域進行聚類,提取更好的有用信息.

1.3 協同過濾算法的相似度計算

我們采用基于用戶的協同過濾算法[20]進行推薦,首先要計算出用戶(項目)之間的相似度.常用的計算相似度的方法主要有歐式距離、余弦相似度和皮爾遜相關系數等.本文采用的皮爾遜相關系數作為用戶相似度的度量方法.皮爾遜相關系數其度量方法表示為:

其中,Iuv表示用戶u和v共同評分的項目,rui,rvi分別表示用戶u和v對項目i的評分,和分別表示用戶u和v對項目的平均評分.

推薦系統就是為用戶提供可靠準確的服務,使用戶可以高效的從海量信息中快速得到自己想要的信息.推薦系統算法常用的標準之一就是平均絕對誤差MAE,它通過計算真實評價與預測評價之間的誤差來衡量推薦結果的準確性.平均絕對誤差越小,推薦結果的準確性就越高.假設用戶的評分集合表示為{v1,v2,…,vN},對應的預測評分集合為{p1,p2,…,pN}則具體的MAE計算公式為:

2 基于有效特征子集選取的高效推薦算法

2.1 有效特征子集的選取

傳統的跨域推薦系統在進行特征選擇時,往往是將輔助域和目標域特征進行聯合選取,這樣會使得在目標域上稀疏數據的有效信息進一步減少,這將會大大降低推薦精度.為了保護目標域數據,我們的模型僅對輔助域進行特征選取,盡可能的提取輔助域上對目標域有用的信息,提高推薦的準確率和效率.由于目標域和輔助域不存在明顯的指標,所以我們要進行無監督的特征提取.為了獲取輔助域上最有效的信息,最大限度的降低冗余和相關特征,我們采用K-means 算法來獲取特征子集.

2.1.1 填充輔助域的缺失值

由于提取的輔助域信息存在有很多缺失值,如果對這些數據直接進行聚類會大大降低聚類的效果,所以我們要對缺失值進行填充,處理缺失值的方法有很多,本文采用矩陣UV 分解的方法對缺失值進行填充.將填充后的矩陣進行下一步的處理.

2.1.2 估計聚類趨勢

聚類趨勢度量指數據集是否有聚類的價值,如果數據集是隨機均勻地分布,則聚類的價值很低.我們常用空間隨機性的統計檢驗來實現,基于這種思想,我們采用一種簡單有效的統計量,霍普金斯統計量.計算霍普金斯統計量的步驟是:

(1)均勻的從D的空間中抽到n個點p1,…,pn.也就是說,D空間中的每個點都以相同的概率包含在這個樣本中,對于每個點pi(1＜=i＜=n),我們找出pi在D中的最近鄰,并令xi為pi與它在D中的最近鄰之間的距離,即xi=min(dist(pi,v)),v屬于D.

(2)均勻地從D中抽到n個點q1,…,qn.對于每個點qi(1＜=i＜=n),我們找出qi在D-{qi}中的最近鄰之間的距離,即yi=min(dist(qi,v)),v屬于D,v不等于qi.

(3)計算霍普金斯統計量:

2.1.3 確定聚類簇數k的大致區間

對于K-means 算法來說,聚類數k的確定無疑是最重要的一個步驟.為了得到更好的分類簇數,我們將選用肘方法來得到k,獲取對目標域最有價值的信息.肘方法的原理是,當我們增加簇數的時候,數據集的簇內方差之和會降低,以簇數為自變量,簇內方差為因變量做一條曲線,這條曲線會隨簇數的增加而下降.生成的這條曲線會有一個明顯的拐點,這個拐點附近就是我們要找的k.

2.1.4 利用K-means 算法進行特征子集選取

為了最大可能的減少輔助域的相關特征,提取對目標域最有價值的信息,我們首先對輔助域進行聚類.因為目標域和輔助域雖然在具體項目上可能不同,比如圖書和電影,但是他們在題材標簽上是非常相似的.所以我們首先通過聚類方法來獲取題材標簽tag={t1,t2,…,tm},然后用每個標簽的平均值作為用戶ui對此標簽tj的評分vij.

對于初始點k的選取,我們應做到盡可能的選擇相互距離較遠的點.在選擇k個初始點的時候,首先隨機選擇一個點作為初始簇中心,然后選擇距離該點相對較遠的那個店作為第二個初始類簇中心,然后選擇距離該兩點相對較遠的點作為第三個初始類簇中心,以此類推,直至找到k個初始類簇中心.

K-means 算法產生聚類簇的過程:

1)在所有的項目中挑選k個項目作為初始聚類點；

2)計算每個聚類中心與其他項目的相似度,依據相似度將項目分配到相應的類簇；

3)計算生成的類簇的中心點.

重復2),3)操作,直到各個類簇的中心點不再發生變化.

在圖1中我們假設輔助域中用戶u對項目I的評分為rij,{I1,I3,…,In}為一類,我們通過聚類生成標簽t1,對于用戶ui對標簽t1的評分為vi1,vi1是ui對I1,I3,…,In的平均值,也就是說聚類后的項目標簽評分矩陣為U×T-＞V,用戶對標簽的評分計算公式為:

這里t表示生成的標簽,N 表示屬于第j個標簽的項目數.

為了得到用戶標簽評分矩陣,我們首先將用戶項目評分矩陣進行轉置,得到項目用戶矩陣,然后對項目進行聚類,得到項目標簽,我們對提取的項目標簽用這一標簽內的項目評分均值作為標簽矩陣,也就是標簽用戶矩陣,最后將用戶標簽矩陣對目標矩陣進行擴展,作為推薦算法的輸入數據.

圖1 Kmeans 聚類模型

2.2 推薦算法

我們將得到的輔助域特征子集對目標域進行擴展,得到擴展的用戶項目評分矩陣,用戶還是{u1,u2,…,um},我們對項目進行了擴展{i1,i2,…,in,t1,t2,…,tk}共有m+k個項目,用戶ui對項目j的評分為vij,分值在0-5 之間.

得到擴展的用戶評分矩陣之后,我們用式(1)來計算用戶之間的相似度,最后選擇與目標用戶最相似的n個用戶為最近鄰集合.通過擴展后的用戶項目評分矩陣獲取最近鄰之后,我們對目標用戶進行評分預測,并向目標用戶推薦前N項結果.評分預測公式為:

其中,sim(a，b) 表示用戶a和b的相似性,是用戶b的平均分,N表示用戶a的近鄰集合.這個公式考慮了與用戶a最相似的N個近鄰的評分偏差.

從算法的復雜度來看,如果將未處理的目標域和輔助域進行聯合,那么我們采用基于用戶的協同過濾方法來進行實驗的算法復雜度為O(m2×(n+L)),其中m為用戶數,n為目標域的項目數,L為輔助域的項目數.本文將輔助域的項目進行了提取,輔助域提取信息時,矩陣分解的復雜度為O(m×L×k),其中L為輔助域的項目數,k為聚類的簇數,可以視為常數.輔助域進行K-means 聚類的復雜度為O(m×L),進行輔助域的特征提取之后,與目標域聯合進行協同過濾的復雜度為O(m2×(n+k)),其中k為聚類的簇數,視為常數,所以復雜度為O(m2×n).綜上本文的計算復雜度為O(m2×n).所以本文在計算復雜度上與已有的跨域推薦算法有一定的降低.

2.3 算法步驟

本文提出了基于有效特征子集選取的高效推薦算法,該算法有效的解決了推薦算法常見的數據稀疏性和特征冗余問題,不僅提高了系統的運算效率而且也提高了推薦的準確率.具體步驟如下:

1)根據原始文本數據中提取目標域和輔助域的用戶項目評分矩陣.

2)對輔助域數據進行缺失值的填充.

3)在輔助域上進行聚類并獲得標簽數據和評分,并對目標域數據進行擴充.

4)根據用戶項目評分矩陣進行相似度計算,創建目標用戶的最近鄰集合.

5)對目標用戶項目進行評分預測.

6)對推薦結果進行分析,計算得到MAE.算法流程圖,如下所示:

圖2 算法流程圖

3 實驗

3.1 數據準備

數據的完整性和真實性對實驗的成功至關重要.本文最終采用爬取的亞馬遜數據集作為實驗數據.亞馬遜數據集包含1555 多萬個用戶對753 243 個項目的評分,其中項目包含圖書,電影,音樂等方面.這其中包含物品的ID,分類號(ASIN),標題(title),分類(group),用戶的評分等信息.

我們對以上文本類數據進行了提取并合并了用戶在每個領域的評分,得到用戶-項目評分矩陣(u,i,r),r是用戶u對項目i的評分.本實驗的前提是數據集之間需要有較強的相關性,所以我們采用評分數據相對較多的圖書作為輔助域,較稀疏的DVD 作為目標域.

本文篩選出1410 個用戶1000 本圖書作為輔助域,稀疏度為23.3%,DVD 則選擇1410 個用戶和3000 個項目作為目標域,稀疏度為2.667%,將以上數據作為本 文的實驗數據.

圖3 實驗源數據格式

3.2 實驗結果及分析

實驗使用10 折交叉驗證的方法,我們將數據集的75%作為訓練集,25%作為測試集.訓練集的數據用來對算法各個步驟的參數進行計算和對測試集的評分進行預測；測試集則用來衡量算法的推薦質量.

我們對輔助域進行聚類,首先來估計輔助域的聚類趨勢.通過對輔助域的計算得到霍普金斯統計量為0.2185＜0.5,說明輔助域的數據分布是不均勻的,可以對輔助域進行聚類分析.

本實驗采用肘方法來確定聚類數k的大致聚類區間 ,最終我們得到如圖4所示.

圖4 聚類數k 的大致區間

由圖4可以看出,k的大致取值范圍在10 左右,所以我們在聚類時,在k=10 周圍進行選取最佳的值,并與其他數據點進行比較.

本實驗的目的是結合輔助域的信息標簽,對目標域采用協同過濾方法對目標用戶進行推薦,并與單域上基于用戶的協同過濾(CF-U),傳統的跨域協同過濾(CDCF)和基于矩陣分解的協同過濾方法做比較.我們分別選取聚類數k={8,10,15,25,35},近鄰數N={5,10,20,30,40,50,60,70,80}來進行實驗,最終平均絕對偏差(MAE)隨我們選擇不同的近鄰用戶數N和聚類數k的變化如表1所示.

表1 亞馬遜數據集的實驗結果

我們選擇表1中具有代表性的結果以折線圖的形式展現,我們可以直觀的看到MAE 隨著k和N值的變化曲線:

圖5 實驗結果折線圖

從圖5看出,單域上基于用戶的協同過濾(CFU)算法隨著近鄰數N 的增加先減小后增加,但是整體上,單域的協同過濾算法MAE 高于跨域的協同過濾算法.說明引入輔助域信息可以提高推薦系統的準確率.傳統的跨域協同過濾算法CDCF 和基于矩陣分解的跨域推薦算法MF-CDCF 雖然比單域的推薦效果好,但是MAE 值還是較高.從圖4中可以看出,本文所提出的算法依賴于所選擇的聚類數k值,如果k值選取不合適,可能會使得推薦算法的質量下降.基于有效子集選取的高效推薦算法(FSERA)只要選取合適的k值,本系統的MAE 值就遠遠低于其他算法,這也表明了FSERA 可以為用戶提供較好的推薦.

隨著聚類數k值的增加,改進的協同過濾MAE 會逐漸上升,當k=10 時,MAE 的曲線最低,此時的算法質量最好；當選取的近鄰數N 逐漸增加時,跨域推薦系統的MAE 值在不斷增加.我們從圖5中也可以看出,當引入輔助域后,協同過濾的MAE 會減小,引入輔助域增加了系統的信息,使得協同過濾算法在計算相似度時有了更多的有用數據.輔助域聚類數為10 時,本文提出的FSERA 算法的推薦質量最高.

從圖5中我們可以看出,基于有效子集提取的高效推薦算法在選取合適的參數時,MAE 可以達到0.77 左右,這說明本文的方案是可行的.但是從特征選的的角度來看,本文所采用的K-means 方法來提取特征,具有一定的局限性,特征提取的方法有很多種,在本文提取特征中,選取K-means 聚類方法有很好的效果,但是也有一定的不足,比如輔助域的數據也很稀疏,聚類效果不佳,可以考慮加入這種缺失信息的方法來達到更好的效果.

通過與其他推薦算法的比較可以看出,本文所提出的FSERA 在推薦質量上略優于其他算法,但是此算法對輔助域進行了特征選擇,使得算法的復雜度大大降低,極大的提高了系統的運算速度,使推薦效率有了大幅度的提升.

4 結束語

傳統的協同過濾方法在應用于推薦系統時,存在著若干問題,比如數據稀疏,數據冗余等問題.本文提出了基于有效特征子集選取的高效推薦算法,有效的將輔助域信息遷移到目標域中,對目標域數據進行了擴展.并解決了豐富的輔助域信息直接對目標域進行擴展帶來的數據冗余等問題.不僅降低了運算的復雜度,并且提高了推薦效率.在amazon 數據集上的實驗表明,該算法很好的挖掘了用戶的興趣,有效的降低了平均絕對偏差,在一定程度上緩解了數據稀疏性問題,該方法在電子商務系統中有一定的實用價值.但是本文在特征選取時采用了K-means 聚類方法有一定的局限性,我們可以嘗試更多的特征選擇方法來進行選擇,找到更多能提高推薦效果的方法,這也將是我以后研究的工作.