基于特征降維和精確歐式局部敏感哈希的協同過濾推薦算法研究

鄒曉瑜

（廣東工業大學 信息工程學院，廣東 廣州 511400）

隨著網絡技術的高速發展，社交媒體、電商等領域也不斷研究從海量數據中挖掘有利于商業推廣的信息。協同過濾算法[1-2]作為經典推薦算法，可從數據上得到偏好信息，進而為用戶推薦與偏好相似的項目，邏輯友好清晰，在商業領域有著廣泛應用。然而，隨著數據規模不斷擴大，遍歷計算相似度將導致協同過濾算法的計算成本呈倍數增長，對此，專家學者們不斷研究并提出新的改進。

在特征工程上，李遠博等[3]提出了使用（Principal Component Analysis ，PCA）對數據進行特征降維，提高相似度計算速度，但僅適用于線性數據降維，多數商業數據可能是非線性的；郭喻棟等[4]和林建輝等[5]分別采用堆疊降噪自編碼神經網絡和奇異值分解完成數據降維；針對高維稀疏數據，吳湖等[6]提出使用非負矩陣分解技術預測用戶評分，但在相似度度量上仍采用傳統方法，推薦效果不夠好。

本文從商業數據規模龐大、高維稀疏的特點出發，使用P CA與流形學習相結合的特征降維方法進行數據降維[7-8]，盡可能同時保留數據的整體結構和局部特征，再使用精確歐式局部敏感哈希（Exact Euclidean Locality Sensitive Hashing，E2LSH）檢索方法[9]進行相似鄰近搜索，快速得到相似近鄰用戶。在確保推薦效果的同時，本文算法可有效降低計算成本，提高運行效率。

1 相關理論知識

1.1 主成分分析法

PCA是重要的特征降維技術之一，可通過從冗余特征中提取最主要的成分，完成特征降維，保留數據整體信息。對于數據集X=(x1,x2,…,xn)∈RP×n，可從X的主成分方向W=(w1,w2,…,wk)∈RP×k定義一個最優低維子空間，將n維數據X投影至k維空間（k＜n），得到Y=(y1,y2,…,yn)∈RP×k。PCA通過最小化樣本投影距離構造目標函數，找到符合條件的W和Y：

對PCA主成分部分組成的低維表征Y，在聚類算法中可將其視為聚類成員評價指標的連續解，PCA與聚類算法可建立聯系，也為PCA和聚類算法進行組合提供了可能性。

1.2 拉普拉斯特征映射

PCA本質上屬于線性降維技術的一種，但實際數據大多是非線性結構。拉普拉斯特征降維作為流形學習方法中一種，可通過圖拉普拉斯算子實現非線性流形降維。對原始數據集X∈Rp×n，拉普拉斯特征映射將其轉為圖的形式，并設置鄰接矩陣W∈Rn×n來表示圖中n個頂點的相互連接關系。降維后數據設為Y=(y1,y2,…,yn)∈Rk×n，則可通過式（2）獲得W和Y：

設定度矩陣D，其中，由拉普拉斯矩陣定義L=D－W，得到拉普拉斯矩陣L，則式（2）可轉化為：

其中，限定約束條件YYT=I確保目標函數有解。式（3）可通過拉格朗日乘子法求解，將優化問題轉為廣義特征值求解問題。

從圖論角度上看，聚類問題可看做是圖分割問題，因而對聚類算法而言，拉普拉斯特征降維后的特征向量Y，可作為聚類算法中最優聚類劃分指標的松弛解，與PCA和聚類算法之間的聯系相似。

1.3 圖PCA

由于PCA中參數W和Y在拉普拉斯特征降維中作用一致，筆者通過整合式（1）和式（3），將兩類方法進行組合，得到組合特征降維方法圖PCA的目標函數：

式（4）設置系數η平衡兩個子式的貢獻程度，并通過求解封閉解實現降維。圖PCA方法可改善單一降維方法在保留數據結構特征上的不足，提高算法性能。

1.4 精確歐式局部敏感哈希

局部敏感哈希算法（Locality sensitive Hashing，LSH）是一種近似近鄰搜索方法，精確歐式局部敏感哈希（(Exact Euclidean Locality Sensitive Hashing，E2LSH）算法則是LSH中的一種，主要通過基于p-穩定的LSH函數對數據進行哈希，使相似樣本有更高概率哈希至同一個桶中，實現快速檢索。通過構造下述LSH函數，E2LSH可將一個d維向量v映射到一個整數集上：

式中，b是從[0,w]中均勻選取的一個實數。為了拉大相似樣本碰撞概率與不相似樣本碰撞概率間的差距，E2LSH選取k個哈希函數進行組合，構造哈希函數組G={g:S2→Uk}，其中，g(v)={h1(v),h2(v),…,hk(v)}。對原始d維空間樣本，使用g(v)映射降至k維后，得到新樣本u={u1,u2,…,uk}。為了進一步提高檢索精確率，E2LSH. 從G中隨機選取L個函數，對應L個哈希表，數據經哈希處理后存入L個哈希表對應的哈希桶中，最后通過定義H1，H2兩個哈希函數完成哈希分桶。

2 基于組合特征降維和E2LSH的協同過濾推薦方法

本文提出的協同過濾改進方法，包含基于圖PCA數據降維、基于E2LSH相似近鄰搜索及預測評分3個部分，接下來對方法的基本流程和關鍵技術進行詳細闡述。

2.1 基于圖PCA的數據降維

計算用戶或項目間相似度時，若直接采用原始高維評分作為特征，會降低推薦算法的計算效率，因此，使用圖PCA降維方法進行數據降維，通過求解目標函數式（4）得到降維后的新表征特征矩陣。先固定參數Y，求關于W的最優化問題，此時，目標函數Q對W求偏導的結果為0，即：

化簡得到XY＝W，再代入求解關于Y的最優化問題，此時，式（4）轉化為：

將式中X－XYYT部分Frobenius范數轉為跡的形式，式（7）最終化簡成：

此時，圖PCA優化問題轉為求解-XXT+ηL的特征向量問題。將特征值從小到大排序，依次選擇m個最小非零特征值對應的特征向量則組成原始數據的低維表征Y。

2.2 基于E2LSH相似近鄰搜索

使用g(·)函數將降維矩陣Y映射至k維，并選取L個g(·)函數生成k維向量，分別對應L個哈希表。再計算主哈希函數H1:{0,1,…,tablesize－1}.次哈希函數H2:{0,1,…,C}，分別得到哈希表索引以及表中的哈希桶索引，當兩個函數值相等時，對應數據存至同一哈希桶中。

對目標用戶進行快速檢索時，先根據用戶的哈希索到對應哈希桶，將桶中用戶取出并去重后，得到目標用戶的相似近鄰用戶。

2.3 預測用戶評分

E2LSH得到近鄰用戶后，需結合近鄰用戶相似度信息預測評分。相似度計算方法種類多樣，其中，基于余弦的相似度計算方法應為廣泛。本文考慮余弦相似度算法難以消除差異大的評分對預測評分的干擾，故在其基礎上稍作改進：

通過改進計算方法去掉差異較大的樣本結果后，還慮用戶不同打分習慣帶來的預測結果偏差。本文采用均值化思想預測評分：計算得到相似近鄰用戶的改進余弦相似度后，根據相似度結果從高往低排序，選擇前k個相似度最高的近鄰客戶，將其評分按相似度進行加權融合，得到目標用戶的最終預測評分，最后根據各項目預測所得評分高低，產生推薦結果。

3 實驗設置與分析

3.1 實驗數據與環境

本文實驗在64位Windows7系統下運行測試，系統為內存8 GB。實驗數據使用明尼蘇達大學提供的MovieLens電影評分數據，數據集共包含610名用戶對9 724個電影項目的100 873條評分數據，評分范圍為0.5～5分，分值越高，表示用戶越喜愛該電影，0分則表示未評分。

3.2 評估指標

本文采用均方根誤差（Root Mean Square Error，RMSE）衡量算法預測結果的準確率，RMSE越小，表示預測結果越準確。RMSE定義為下式：

其中，ru,i表示用戶u對項目i的實際評分，r～u,i表示模型的預測評分，s則表示測試樣本中數據的數量。

3.3 實驗結果與分析

實驗考慮評分數據集高維稀疏特點及運行內存大小，在E2LSH檢索部分，根據經驗設定哈希表個數L=10，k=15，確保檢索精度。實驗先選取不同的維度n對數據集進行降維，通過分析不同特征維度下的評分誤差，選擇最合適的維度。由圖1可得，從運行時間上看，隨著特征維度的增加，算法運行時間也在不斷增加；從RMSE上看，n取值為[50,150]時，算法預測結果不夠穩定，當n＞150維時，RMSE明顯增加，因此，數據降維至150維時，算法預測效果最佳。

為了驗證本文算法的有效性和運行效率，實驗選取協同過濾算法、基于E2LSH的推薦方法與本文算法進行對比，分析不同近鄰用戶時3類算法的性能，如圖2所示。

圖1 特征維度對算法運行時間、RMSE的影響

圖2 不同鄰近用戶3類算法的性能對比

實驗結果顯示，隨著近鄰用戶數的增加，3類算法的RMSE差別不大，其中，CF算法的平均RMSE預測準確率最高，基于E2LSH的推薦算法次之，本文算法的平均RMSE比CF算法高約8.4%。從運行時間上看，E2LSH檢索需遍歷計算哈希索引并分桶，使用的運行時間最長，而本文算法平均運行時間僅為對比CF算法降低了約90.9%，因此，在3類推薦算法的預測誤近情況下，本文提出的推薦算法可顯著提升運行效率，快速得到準確度較高的結果。

4 結語

本文介紹了協同過濾算法在大規模高維稀疏數據集下推薦效果和計算效率方面的缺點，提出一種基于圖PCA和E2LSH的協同過濾推薦方法。實驗結果表明，對比傳統的相似用戶查找方式，使用圖PCA特征降維去除冗余特征后，再結合E2LSH進行樣本相似近鄰檢索，不僅可以得到準確率較高的推薦結果，還可有效提高運行效率，快速得到推薦結果，適用于稀疏型數據集的推薦系統運行。