天天看點

《推薦系統:技術、評估及高效算法》一2.2 資料預處理

本節書摘來自華章出版社《推薦系統:技術、評估及高效算法》一書中的第2章,第2.2節,作者 [ 美]弗朗西斯科·裡奇(francesco ricci)利奧·羅卡奇(lior rokach)布拉哈·夏皮拉(bracha shapira)保羅 b.坎特(paul b.kantor),更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

我們把資料定義為一組對象及其屬性的集合,其中屬性定義為性質或者是對象的特征。對象的其他名稱包括記錄、物品、得分、樣本、觀察值或者執行個體。屬性也可以稱為變量、字段、特性或者特征。

真實資料通常需要經過預處理,以便于機器學習技術在分析階段使用。本節緊緊圍繞推薦系統設計三個尤為重要的問題展開。首先,我們回顧不同的相似度,或者距離度量方式。其次,我們需要讨論抽樣問題,一種可以減少大資料集中物品數量并保持其主要特征的方法。最後,我們将闡述降維方法中最常用的技術。

協同過濾推薦備受青睐方法之一是使用knn分類,我們将在2.3.1節中讨論。這種分類技術(如同大多數的分類和聚類技術)主要取決于定義合适的相似度或者距離度量方法。

最簡單、最常用的距離度量是歐幾裡得距離:

《推薦系統:技術、評估及高效算法》一2.2 資料預處理

其中,n是維數(屬性數),xk和yk分别是資料對象x和y的第k個屬性值(分量)。

闵可夫斯基距離是歐幾裡得距離的推廣:

《推薦系統:技術、評估及高效算法》一2.2 資料預處理

其中,r是距離的度(參數)。取決于r值的不同,一般的闵可夫斯基距離有專用的名稱:

r=1,城市街區(也叫曼哈頓、計程車、l1範數)距離。

r=2,歐幾裡得距離(l2範數)。

r=∞,上确界(lmax或l∞範數),這是任意次元對象屬性間的最大距離。

馬氏距離定義如下:

《推薦系統:技術、評估及高效算法》一2.2 資料預處理

其中,σ是資料的協方差矩陣。

另一個常用的方法是把物品看作n維空間的文檔向量,并且計算它們相似度作為形成夾角的餘弦值,其公式如下:

《推薦系統:技術、評估及高效算法》一2.2 資料預處理

其中,•表示向量的點積,x是向量x的長度。這個相似度稱為餘弦相似度或者是l2範數。

物品之間的相似度還可以用他們的相關度計算,用以度量對象間的線性關系。盡管有幾個相關系數可能被應用,但皮爾遜相關性系數是最常用的。給出點x和y的協方差及它們的标準差σ,我們用以下公式計算皮爾遜相關性:

《推薦系統:技術、評估及高效算法》一2.2 資料預處理

 

推薦系統一般會使用餘弦相似度式(2.4)或者是皮爾遜相關性(或者它們的許多變種方法中的一種,如權重方案)。第4和5章詳述在協同過濾中不同距離函數的使用。但是,前面提到的大部分其他距離度量方法都可能用到。spertus等[69]在orkut社交網絡的環境中做了大規模的研究來評估六種不同的相似度度量方法。盡管由于實驗的特殊設定,結果會有偏差,但有趣的是餘弦相似度是其中效果最好的度量方法。lathia等[48]也做了一些相似度度量的研究,其總結,在一般的案例中,推薦系統的預測精确性不受相似度度量方法選擇的影響。事實上,在他們的工作中,使用随機的相似度度量有時會産生比使用已知任何衆所周知的方法更好的結果。

最後,在一些隻有二進制屬性的物品案例中,可以采用幾個相似度度量方法。首先,計算m01、m10、m11和m00數量,其中m01代表x是0同時y是1這個屬性的數量,m10代表x是1同時y是0這個屬性的數量,以此類推。根據這些數值我們可以計算得到:簡單比對系數smc=number of matchesnumber of attributes=m11+m00m01+m10+m00+m11;jaccard系數jc=m11m01+m10+m11。廣義jaccard(tanimoto)系數,是jc關于連續值屬性或計數屬性的一個變型,計算為d=x•yx2+y2-x•y。

抽樣是資料挖掘從大資料集中選擇相關資料子集的主要技術。它用于資料預處理和最終解釋步驟中。之是以使用抽樣是因為處理全部資料集的計算開銷太大。它也可以被用來建立訓練和測試資料集。這個情況下,訓練集被用于分析階段學習參數或配置算法,而測試集被用來評估訓練階段獲得的模型或者配置,確定它在将來産生的未知資料上運作良好。

抽樣的關鍵是發現具有整個原始資料集代表性的子集,也就是說,其具有與整個資料集大概類似的興趣屬性。最簡單的抽樣技術是随機抽樣,任意物品被選中的機率相同。但也有更複雜的方法。例如,在分層抽樣中資料基于特殊特征被分成幾個部分,之後對每個部分獨立進行随機抽樣。

最常用的抽樣方法包含使用無取代的抽樣:當物品被選擇的時候,物品被從整體中取走。但是,執行取代抽樣也是可以的,物品即使被選擇也不用從整體中去除,允許同樣的樣本被選擇多次。

在分離訓練集和測試集時,通常做法是使用80/20的訓練集和測試集比例,并使用無替代的标準随機抽樣。這意味着我們使用無替代随機抽樣方法去選擇20%的執行個體為測試集,把剩下的80%進行訓練。80/20的比例應該作為一個經驗規則,一般來說,超過2/3的任何值作為訓練集是合适的。

抽樣可能導緻過特殊化劃分的訓練和測試資料集。是以,訓練過程可以重複好幾次。從原始資料集中建立訓練集和測試集,使用訓練資料進行模型訓練并且使用測試集中的樣例進行測試。接下來,選擇不同的訓練/測試集進行訓練/測試過程,這個過程會重複k次。最後,給出k次學習模型的平均性能。這個過程是著名的交叉驗證。交叉驗證技術有很多種。在重複随機樣本中,标準的随機抽樣過程要執行k次。在n折交叉校驗中,資料集被分成n份。其中一份被用來測試模型,剩下n-1份被用來進行訓練。交叉驗證過程重複n次,n個子樣本中每一個子樣本都隻使用一次作為驗證資料。最後,留一法(loo)可以看作n折交叉驗證的極端例子,其中n被設定為資料集中物品的數量。是以,算法運作許多次而每次資料點隻使用其中一個作為測試。我們需要注意的是,正如isaksson等讨論的那樣[44],除非資料集足夠大,否則交叉驗證可能不可信。

在推薦系統中常用的方法是從使用者中抽取可用的回報以使用者評分的形式來劃分訓練和測試。交叉驗證的方法同樣也很常見。盡管在一般的案例中标準随機抽樣是可接受的,但是在其他場景中我們需要用不同的方法定向調整抽樣出來的測試集。例如,我們可能決定隻抽樣最近的評分資料,因為這些是現實情況下我們需要預測的。我們可能還有興趣確定每個使用者的評分比例被儲存在測試集,是以需要對每一個使用者使用随機抽樣。然而,所有這些涉及評估推薦的問題仍是一個探讨和研究點。

推薦系統中不僅有定義高維空間特征的資料集,而且在空間中資訊非常稀疏,例如,每個對象就那麼幾個有限的特征有值。密度,以及點之間的距離,這些對于聚類和孤立點檢測非常重要,但在高維空間中的意義并不大。這就是著名的次元災難。降維技術通過把原始高維空間轉化成低維有助于克服這類問題。

稀疏和次元災難是推薦系統中反複出現的問題。即使在最簡單的背景下,我

們很可能都會有成千上萬行的行和列稀疏矩陣,其中大部分值是零。是以,降低次元就自然而然了。應用降維技術帶來這樣的結果,其也可以直接适用于計算推薦的預測值,即它可以作為推薦系統設計的方法,而不僅是資料預處理技術。

接下來,我們概述兩個在推薦系統中最相關的降維算法:主成分分析(pca)和奇異值分解(svd)。這些技術可以單獨作為推薦方法使用,或作為在本章提到的其他任何技術的預處理步驟。

主成分分析(pca)[45]是一種經典統計方法,用來發現高維資料集中的模式。主成分分析可以獲得一組有序的成分清單,其根據最小平方誤差計算出變化最大的值。清單中第一個成分所代表的變化量要比第二個成分所代表的變化量大,以此類推。我們可以通過忽略這些對變化貢獻較小的成分來降低次元。

圖2.2顯示了通過高斯合并産生的二維點雲中的pca分析結果。資料集中之後,主要成分由u1和u2來表示。考慮到新坐标軸的長度所涉及的能量被包含在它們的特征向量中。是以,對于圖2.2中列舉的特殊例子,第一個成分u1占能量的83.5%,這意味着移除第二個成分u2将隻失去16.5%的資訊。根據經驗規則選擇m′以便于累計能量超過一定的門檻值,一般是90%。pca允許我們把資料投影到新的坐标系中來重新表示原始資料矩陣:x′n×m′=xn×mw′m×m′。新的資料矩陣x′降低了m-m′次元并保證包含大部分的原始資料x的資訊。

pca是一種強大的技術,但也有重要的限制。pca依賴于以線性合并為基礎的經驗資料集,盡管一般的非線性pca方法已經提出。pca的另一個重要假設是原始資料集是從高斯分布中抽取出來的。當這個假設不正确時,就無法保證主要成分的有效性。

盡管目前的趨勢似乎表明其他的矩陣分解技術更受歡迎,如svd或者非負矩陣分解,但是早期用得最多還是pca。goldberg等在線上笑話推薦的内容中提出使用pca方法[37]。他們的系統,著名的eigentaste,開始于标準的使用者評分矩陣。然後從所有使用者都評分過的item裡選出一個子集作為測試集。這個新矩陣被用來計算全局相關矩陣,這些矩陣使用了标準的二維pca。

《推薦系統:技術、評估及高效算法》一2.2 資料預處理

奇異值分解[38]是一個強大的降維工具。它是矩陣分解方法的特殊實作,是以它也和pca相關。在svd分解中的關鍵問題是發現低維特征空間,這些新特征代表概念以及在集合内容中的每一個概念強度都是可計算的。因為svd可以自動擷取到低維空間上的語義概念,它可以被用來當作潛在語義分析的基礎,潛在語義分析[24]是一種在資訊檢索中非常受歡迎的文本分類技術。

svd的核心算法基于以下的理論:把矩陣a分解成a=uλvt是可行的。給出n×m矩陣的資料a(n個物品,m個特征),我們可以獲得一個n×r的矩陣u(n個物品,r個概念),一個r×r的對角矩陣r(概念的長度),以及m×r的矩陣v(m特征,r概念)。圖2.3闡述了這個想法。r的對角矩陣包含奇異值,其總是為正并且是降序排列。u矩陣可以解釋成物品概念相似矩陣,矩陣V是特征概念相似性矩陣。

《推薦系統:技術、評估及高效算法》一2.2 資料預處理

為了計算矩形矩陣a的svd,我們考慮如下公式aat和ata。u的列是aat的特征向量,v的列是ata的特征向量。矩陣對角線上的奇異值是aat和ata非零特征值的平方根。是以,為了計算矩陣a的svd,首先計算aat(t)以及ata(d),然後計算t和d的特征向量和特征值。

在λ中的特征值r是有序遞減的。是以,初始矩陣a可以通過截取前k個特征值來近似構造。截取的svd構造了一個近似矩陣a的k秩矩陣ak=ukλkvt。ak是最近似原始矩陣的k秩矩陣。最近似表達的是最小化a與ak元素之間的平方差之和。被截取的svd代表降維成k維空間後的潛在結構,這一般意味着特征向量中的噪聲被降低。

使用svd作為工具來提高協同過濾已經有一段時間了。sarwar等[66]在論文中描述了使用svd的兩種不同方法。首先,svd可以用來發現使用者與産品之間的潛在關系。為了完成這個目的,他們首先用物品平均評分值去填充使用者物品矩陣的0值項,然後通過減去使用者對所有物品平均評分來正規化這些矩陣。這些矩陣用svd來分解,其分解結果在一些細微的操作之後可以直接用來計算預測值。其他方法是使用從svd中提取出的低維空間中的結果來提高在knn方法的鄰居資訊。

正如sarwar等[65]描述的那樣,svd的一大優勢是有增量算法來計算近似的分解。這使得我們在接收到新使用者或者是評分的時候,沒有必要重新計算用先前存在的資料建構的模型。同樣的想法後來被brand[14]的線上svd模型擴充和正式采納。在成功應用到netflix prize之後,增量svd方法的使用最近已經成為常用的方法。simon funk的簡單增量svd方法的發表被标志為競賽中的轉折點[35]。自從它發表之後,在該領域已經發表了幾篇改進的svd(詳細資訊可以參考paterek的全部svd的算法[56],或者是kurucz等的svd參數評估[47])。

最後,應該注意的是矩陣分解(mf)的不同變化方法,如非負的矩陣分解(nnmf)已經被使用[74]。本質上來說,這些算法類似于svd。最基本的想法是把評分矩陣分解成兩個部分:一個部分包含描述使用者的特征,另一個部分包含描述物品的特征。矩陣分解通過引入偏項到模型中來處理缺失資料比svd方法要好。但是,svd方法中也可以在預處理階段通過用物品的平均值來取代零值來處理。需要注意的是svd和mf都可能産生過拟合的問題。但是已存在改進的mf,如正規化核心矩陣分解,能有效地避免這個問題。mf和svd方法的主要問題是,由于計算的複雜性每次資料更新更新時重新計算分解是不現實的。但是,rendle和schmidt-thieme[62]提出一種線上的方法允許不用重新計算所有整個模型來更新分解近似值。

第5章會詳細介紹在netflix prize的環境中svd和mf的使用,是對本章簡介的詳細補充。

資料挖掘中采集的資料可能會有各種噪聲,如缺失資料,或者是異常資料。去噪是非常重要的預處理步驟,其目的是在最大化資訊量時去除掉不必要的影響。

在一般意義上我們把噪聲定義為在資料收集階段收集到的一些可能影響資料分析和解釋結果的僞造資料。在推薦系統的環境中,我們區分自然的和惡意的噪聲[55]。前者提到的噪聲是使用者在選擇偏好回報時無意産生的。後者是為了偏離結果在系統中故意引入的。

很顯然惡意的噪聲能夠影響推薦的輸出。但是,我們的研究推斷正常的噪聲對推薦系統性能的影響是不可忽略的[4]。為了解決這個問題,我們設計了一個去噪方法,能夠通過要求使用者重新評價一些物品來提高精确度[5]。我們推斷通過預處理步驟來提高精确度能夠比複雜的算法優化效果要好得多。

繼續閱讀