基于數(shù)據(jù)降維與精確歐氏局部敏感哈希的k近鄰推薦方法

郭喻棟，郭志剛，陳 剛，魏 晗

(信息工程大學 信息系統(tǒng)工程學院，鄭州 450002)(*通信作者電子郵箱20374042@qq.com)

基于數(shù)據(jù)降維與精確歐氏局部敏感哈希的k近鄰推薦方法

郭喻棟，郭志剛*，陳 剛，魏 晗

(信息工程大學 信息系統(tǒng)工程學院，鄭州 450002)(*通信作者電子郵箱20374042@qq.com)

針對基于k近鄰的協(xié)同過濾推薦算法中存在的評分特征數(shù)據(jù)維度過高、k近鄰查找速度慢，以及評分冷啟動等問題，提出基于數(shù)據(jù)降維與精確歐氏局部敏感哈希(E2LSH)的k近鄰協(xié)同過濾推薦算法。首先，融合評分數(shù)據(jù)、用戶屬性數(shù)據(jù)以及項目類別數(shù)據(jù)，將融合后的數(shù)據(jù)作為輸入對堆疊降噪自編碼(SDA)神經(jīng)網(wǎng)絡進行訓練，取神經(jīng)網(wǎng)絡編碼部分最后一個隱層的值作為輸入數(shù)據(jù)的特征編碼，完成非線性降維。然后，利用精確歐氏局部敏感哈希算法對降維后的數(shù)據(jù)建立索引，通過檢索得到目標用戶或目標項目的相似近鄰。最后，計算目標與近鄰之間的相似度，利用相似度對近鄰的評分記錄加權得到目標用戶對目標項目的預測評分。在標準數(shù)據(jù)集上的實驗結果表明，在冷啟動場景下，均方根誤差比基于局部敏感哈希的推薦算法(LSH-ICF)平均降低了約7.2%，平均運行時間和LSH-ICF相當。表明該方法在保證推薦效率的前提下，緩解了評分冷啟動問題。

信息推薦；堆疊降噪自編碼器；精確歐氏局部敏感哈希；數(shù)據(jù)降維；冷啟動

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，人們在互聯(lián)網(wǎng)平臺上的活動越來越頻繁，信息推薦在網(wǎng)絡中發(fā)揮的作用也越來越重要。在電子商務領域，商品推薦根據(jù)客戶的注冊信息、商品信息以及客戶對商品的反饋信息等分析客戶的偏好，模擬銷售人員向其提供商品購買建議，從而提高電子商務交易量。在社交網(wǎng)絡領域，好友推薦系統(tǒng)能夠為用戶建立復雜的人際關系網(wǎng)絡圖譜，向用戶推薦可能認識的好友或群體，擴展用戶的交際圈，最終提高用戶對于社交平臺的滿意度。在網(wǎng)絡媒體領域，由于新聞資訊數(shù)量呈爆炸式增長，廣大讀者受到了信息過載問題的困擾，新聞推薦通過分析讀者的行為記錄(瀏覽、分享、點贊、評論等)，識別讀者的興趣點，向他們推薦其感興趣的內容，在讀者目的不明確的情況下，大大提高了其信息獲取的效率，緩解了信息過載問題。

基于k近鄰的推薦算法[1-3]是一種常用的推薦模型，可以分為基于用戶近鄰的推薦算法和基于項目近鄰的推薦算法?；谟脩艚彽耐扑]算法主要分為以下步驟：根據(jù)用戶的特征計算兩兩用戶之間的相似度；針對目標用戶，找到與之最相似的用戶近鄰集合；在估計目標用戶對某一項目的評分時，利用近鄰集合中用戶對該項目的評分，通過相似度加權，來預測目標用戶的評分。

基于項目近鄰的推薦算法與基于用戶近鄰的推薦算法原理大致相同，區(qū)別在于基于項目近鄰的推薦算法通過計算項目之間的相似度來完成預測和推薦。兩種方法的適用場合不同，在實際應用中，需要結合具體的場景進行選擇。在一些系統(tǒng)中，項目的數(shù)量較為穩(wěn)定且遠遠小于用戶的數(shù)量，此時計算項目之間的相似度更節(jié)省時間，適合采用基于項目近鄰的推薦算法。但是還有一些系統(tǒng)，如新聞推薦系統(tǒng)和微博推薦系統(tǒng)，項目的更新速度要遠遠高于系統(tǒng)中用戶的更新速度，且數(shù)量也要遠遠超過用戶的數(shù)量，此時適合選擇基于用戶近鄰的推薦算法。因此需要具體問題具體分析，根據(jù)系統(tǒng)的實際需要選取合適的推薦算法。

k近鄰推薦算法的關鍵在于評分特征提取和相似度計算?；A算法將原始高維稀疏的評分作為用戶和項目的特征，采用余弦相似度進行計算，最后根據(jù)相似度最高的k個近鄰進行評分預測和推薦。這種方法存在空間消耗大、相似度計算不精確、相似近鄰選取效率低等缺點。近年來，國內外學者針對上述關鍵點進行了不同的改進。在特征提取方面，文獻[4-6]分別采用主成分分析(Principle Component Analysis, PCA)和奇異值分解(Singular Value Decomposition, SVD)對數(shù)據(jù)進行降維，提高相似度計算速度和相似近鄰選取效率，但是PCA降維方法假設評分數(shù)據(jù)之間是線性的，而實際中的數(shù)據(jù)可能是非線性的。在相似度計算方面，經(jīng)典的相似度計算方法有余弦相似度、皮爾森相關系數(shù)和修正的余弦相似度等[7]，后續(xù)工作大都在這些基礎上改進，文獻[8]對相似度加權方法進行改進，文獻[9]對項目屬性相似度和評分相似度進行動態(tài)組合，文獻[10]引入Tanimoto系數(shù)進行相似度計算，這些改進能夠提高評分預測的準確率，但都是在原始評分特征上進行的，特征降維以后，這些相似度計算方法便不再適用。另外，上述方法沒有考慮評分冷啟動問題(在評分數(shù)據(jù)過于稀疏或沒有評分數(shù)據(jù)時，無法進行準確推薦)，且在推薦過程中仍然需要大量的相似度計算，不能真正提高推薦效率。

針對上述問題，本文融合了評分數(shù)據(jù)、用戶屬性數(shù)據(jù)和項目類別數(shù)據(jù)，采用堆疊降噪自編碼(Stack Denoising Auto-encoder, SDA)神經(jīng)網(wǎng)絡對上述數(shù)據(jù)進行非線性降維，引入精確歐氏局部敏感哈希(Exact Euclidean Local-Sensitive Hash, E2LSH)快速檢索算法進行相似近鄰檢索，并改進了相似度計算方法，在保證推薦效率的前提下，緩解了評分冷啟動問題。

1 相關理論

1.1 堆疊降噪自編碼網(wǎng)絡

降噪自編碼器(Denoising Auto-Encoder, DAE)是由Vincent等[11]提出的一種由輸入層、隱藏層和輸出層組成的三層神經(jīng)網(wǎng)絡，輸出層是對輸入層的重構，輸入層到隱藏層是編碼器，隱藏層到輸出層是解碼器。DAE向輸入層數(shù)據(jù)中加噪，在學習過程中去噪，這樣能夠消除干擾特征提取的噪聲，學習到的特征更具有代表性。SDA是一種特殊的深度神經(jīng)網(wǎng)絡[12]，其網(wǎng)絡結構可認為是對稱的，前半部分從輸入層到中間層逐層編碼，后半部分從中間層到輸出層逐層解碼，因此通常網(wǎng)絡層數(shù)為2L+1，如圖1所示。

圖1 SDA神經(jīng)網(wǎng)絡結構

SDA的第l層隱層到下一層和第2L-l+1層隱層到下一層構成一對編解碼器，編碼函數(shù)和解碼函數(shù)分別如式(1)和式(2)所示：

hl+1=fl(Wlhl+bl)

(1)

h2(L+1)-l=gl(W2L-l+1h2L-l+1+b2L-l+1)

(2)

其中:f(·)和g(·)分別為編碼器和解碼器函數(shù)，通常采用sigmoid函數(shù)，其自變量為網(wǎng)絡參數(shù)W和b。Wl是第l層與上一層之間的權重，Wl和W2L-l+1互為轉置，由編碼器和解碼器共享，稱為一對捆綁權重[12]。hl和h2L-l+1分別是編碼器和解碼器的輸入向量，bl和b2L-l+1是偏置向量。

SDA的訓練過程分為預訓練和微調兩個階段。預訓練將每一對編碼器和解碼器都當作一個DAE進行訓練，通過隨機梯度下降法最小化單個DAE的損失函數(shù)，如式(3)所示，得到預訓練參數(shù)。微調階段利用預訓練參數(shù)作為網(wǎng)絡的初始化參數(shù)，通過后向傳播算法最小化損失函數(shù)，如式(4)所示，得到最終的網(wǎng)絡參數(shù)。在這種深度神經(jīng)網(wǎng)絡結構下，在預訓練階段，每一個DAE可以看作是一種無監(jiān)督的預訓練過程，依次進行。由于當前DAE的輸入是前面DAE的隱層值，因此，只有當前面的DAE訓練好后，才能開始當前DAE的訓練。具體的訓練步驟將在第2章中詳細闡述。

C(hl,h2(L+1)-l)=-hlln(h2(L+1)-l)+

(1-hl)ln(1-h2(L+1)-l)

(3)

C(x,x′)=xln(x′)+(1-x)ln(1-x′)

(4)

x′=g1°…°gL°fL°…°f1(x″)

(5)

其中:C(hl,h2(L+1)-l)是預訓練階段的損失函數(shù)，C(x,x′)是微調階段的損失函數(shù)，x″是加噪后的輸入，hl是網(wǎng)絡第l層的數(shù)據(jù)，當l=0時，hl分和h2(L+1)-l分別為整個網(wǎng)絡的輸入x和輸出x′。

1.2 精確歐氏局部敏感哈希算法

局部敏感哈希(Local-Sensitive Hash, LSH)算法是一種近似近鄰搜索策略[13]，能夠得到近似卻高效的候選結果，這往往比低效精確的策略更具實際意義。LSH的基本思想是以較大的碰撞概率保證空間中的相似點哈希到同一個哈希桶中，同時過濾掉不相似的點以減少相似性計算，從而快速檢索到相似近鄰。E2LSH是對LSH的一種改進[14]，通過基于p穩(wěn)態(tài)分布的LSH函數(shù)對數(shù)據(jù)進行哈希表示，使相似的數(shù)據(jù)哈希到同一個桶中的概率更高。

位置敏感哈希函數(shù)族是LSH算法的基礎，是根據(jù)一組由點域S到數(shù)集域U的映射函數(shù)定義的，用E={e:S→U}表示。隨機選取哈希函數(shù)族E中的一個，對于數(shù)據(jù)點t,v∈Rd，如果滿足下列條件，則E即為位置敏感哈希函數(shù)族。

若‖t-v‖P1；

若‖t-v‖>d2，則P[e(t)=e(v)]

其中，P[·]表示t和v的哈希值取等時的概率，0

ea,b(v)=?(a·v+b)/w」

(6)

其中:a是從R上的p穩(wěn)態(tài)分布中隨機取樣構成的d維向量，b是從[0,w]上的均勻分布中隨機取樣得到的隨機數(shù)，?·」表示向下取整。函數(shù)e將d維向量v映射成一個整數(shù)，作為該向量的哈希值。由p穩(wěn)態(tài)分布的定義可知，向量v在a方向上的投影av與‖av‖pX同分布，X服從p穩(wěn)態(tài)分布。哈希函數(shù)ea,b(v)的幾何意義如圖2所示，a方向上的實線以w為間隔進行分割，將投影a·v+b所處的間隔作為向量v的哈希值。

圖2 基于p穩(wěn)態(tài)分布的哈希函數(shù)幾何意義

(7)

(8)

2 基于數(shù)據(jù)降維和E2LSH的k近鄰推薦算法

本章首先給出基于數(shù)據(jù)降維和E2LSH的k近鄰推薦算法基本流程，然后對其中的關鍵技術逐一進行詳細闡述。

2.1 基本流程

本文方法的基本流程如圖3所示，對基礎k近鄰推薦算法進行了改進，主要包括數(shù)據(jù)降維、相似近鄰檢索和評分預測三部分。

圖3 本文方法基本流程

1)數(shù)據(jù)降維。通過SDA神經(jīng)網(wǎng)絡對評分數(shù)據(jù)和用戶/項目標簽數(shù)據(jù)融合后所形成的高維稀疏向量進行非線性降維，得到低維稠密的用戶/項目特征向量。

2)相似近鄰檢索。利用精準歐氏局部敏感哈希算法為降維后的數(shù)據(jù)構建索引，通過檢索得到目標用戶或項目的近似近鄰集合。

3)評分預測。計算目標用戶或項目與相似近鄰之間的相似度，利用相似近鄰的評分記錄，通過相似度加權來預測未知評分。

2.2 基于神經(jīng)網(wǎng)絡的數(shù)據(jù)降維

在計算用戶或項目之間的相似度時，若采用原始評分作為特征，隨著推薦系統(tǒng)中用戶數(shù)和項目數(shù)的不斷增多，特征維度將急劇增加，從而降低運算效率，甚至造成維數(shù)災難，因此對評分數(shù)據(jù)進行降維十分必要。傳統(tǒng)的PCA和SVD降維是一種線性模型，而推薦系統(tǒng)中的數(shù)據(jù)可能是非線性的，因此本文引入自編碼神經(jīng)網(wǎng)絡作為一種非線性降維方法。自編碼神經(jīng)網(wǎng)絡有深層和淺層之分，前者能夠擬合更復雜的函數(shù)，降維后得到的特征更具有代表性[16]。所以本文采用深層網(wǎng)絡——SDA對評分數(shù)據(jù)和標簽數(shù)據(jù)進行非線性降維。訓練步驟如下：

1)確定SDA的網(wǎng)絡結構，設置輸入層維數(shù)、隱藏層個數(shù)、各隱藏層維數(shù)以及各層的加噪比例。然后融合評分數(shù)據(jù)和用戶/項目標簽數(shù)據(jù)，對數(shù)據(jù)加噪后以向量的形式作為SDA的輸入。

圖4 SDA訓練過程

2)訓練第一層DAE，即圖4(a)中輸入層N維，隱層N1維的DAE，利用式(1)和式(2)計算網(wǎng)絡的輸出值，通過隨機梯度下降法最小化損失函數(shù)，如式(3)所示。

3)將第一層DAE的隱層數(shù)據(jù)作為第二層DAE的輸入，按照步驟2)中的方法訓練第二層DAE。以此類推，訓練多層DAE。

4)將多層DAE展開成深度網(wǎng)絡的結構，分為編碼和解碼兩部分，如圖4(b)所示。利用步驟2)、3)中得到的權值對深度網(wǎng)絡進行參數(shù)初始化。

5)將輸入數(shù)據(jù)作為深度網(wǎng)絡的整體輸入，通過經(jīng)典的后向傳播算法對網(wǎng)絡參數(shù)進行微調，如圖4(c)所示。將編碼部分最后一個隱層的值保留(即維度為N3的隱藏層的值)，作為輸入數(shù)據(jù)的特征編碼。

2.3 基于E2LSH的相似近鄰選擇

針對傳統(tǒng)的基于余弦相似度來計算近鄰用戶的方法存在計算量大、耗時長的缺點，本文采用E2LSH算法實現(xiàn)相似近鄰的快速檢索。在進行用戶/項目的相似近鄰檢索時，以用戶為例，根據(jù)索引鍵搜索目標用戶u的特征向量所在的L個哈希桶，將這些桶中用戶的并集作為目標用戶的近似近鄰集。具體實現(xiàn)方法如下：

1)初始化函數(shù)φ(v)=(e1(v),e2(v),…,ek(v))，φ(v)將用戶特征向量v哈希成k個整數(shù)，連成一個k維向量。其中，e(·)由式(6)給出，不同的ei(·)和ej(·)彼此隨機獨立產(chǎn)生。

2)隨機獨立的選取L個φ(·)函數(shù)，為每個用戶生成L個k維哈希向量，對應L個哈希表。

圖5 索引構建示意圖

圖5中，每個用戶的特征向量對應高維空間的一個點，根據(jù)索引鍵(Value,Index)將該點分別存入L個哈希表中的其中一個桶。按照此法將所有數(shù)據(jù)點存入哈希桶，同一個桶中的點索引鍵相同，從而完成索引構建。

4)在對目標用戶進行檢索時，根據(jù)目標用戶的索引鍵，找到該用戶所在的L個哈希桶。將這些桶中的所有用戶取出，去掉重復的用戶，剩下的即為目標用戶的相似近鄰。

2.4 相似度計算

本文在余弦相似度的基礎上，為了消除差異較大的相似近鄰對后續(xù)預測評分計算的干擾，對相似度計算公式進行改進，以項目相似度計算為例，改進前后的具體計算方法分別如式(8)和式(9)所示：

(8)

(9)

其中:α和β分別表示兩個項目的特征向量，sim(α,β)表示兩個項目之間的相似度，q表示特征維度的大小，αi和βi分別表示特征向量的第i個元素，當sim(α,β)>0時，說明兩個項目較為相似，否則說明二者差別較大。當某一項目與目標項目差別較大時，該項目對目標項目的評分預測貢獻意義不大，因此本文將它們的相似度置為0，從而減小異類項目對評分預測的干擾。類似地，在計算用戶a與用戶b之間的相似度時，在消除不同用戶平均評分不同的差異的同時，也排除異類用戶對目標用戶評分預測的干擾。

2.5 評分預測

在利用E2LSH得到用戶/項目的相似近鄰后，需要根據(jù)相似近鄰的評分來預測未知評分。評分預測分為基于用戶的評分預測和基于項目的評分預測，計算公式分別如式(10)、(11)所示。對于基于用戶的方法，由于每個用戶的評分習慣不同，例如有的用戶習慣評分較高，有的用戶則習慣評分較低，因此在評分預測在用戶的評分均值的基礎上進行。基于項目的評分預測是利用同一用戶已評價過的項目來預測未評價過的項目，因此不存在這個問題，可直接通過相似度加權進行評分預測。

(10)

(11)

3 實驗結果及分析

3.1 實驗數(shù)據(jù)

本文使用MovieLens100K數(shù)據(jù)集，該數(shù)據(jù)集包含943名用戶對1 682個項目的100 000條真實評分記錄，同時包含用戶和項目的屬性信息。本文設計了熱啟動和冷啟動兩種場景：在熱啟動場景下，將數(shù)據(jù)集分為兩部分，80%用作訓練集，20%用作測試集；在冷啟動場景下，訓練集和測試集都為原始數(shù)據(jù)集的20%。實驗采用5折交叉驗證的平均值作為最終結果。

3.2 評價指標

評分預測的準確率通常采用均方根誤差(Root Mean Square Error, RMSE)計算，誤差越小表示評分預測越準確。230對于測試集Test中的用戶u和項目i，定義為：

(12)

3.3 實驗設置與結果分析

3.3.1 實驗參數(shù)設置

本文結合SDA降維和E2LSH近鄰檢索技術，改進了相似度計算方法，分別實現(xiàn)了基于用戶的k近鄰推薦和基于項目的k近鄰推薦，對比實驗包括傳統(tǒng)的協(xié)同過濾推薦[8]和其他基于數(shù)據(jù)降維的推薦[4,6](基于PCA和基于SVD的推薦)。經(jīng)過大量實驗測試，在保證各算法相對公平的條件下，各算法參數(shù)設置如下：降維后的特征維度大小統(tǒng)一設置為25，DAE實驗中，加噪程度為0.2，梯度下降的學習率為0.8，迭代次數(shù)為15。SDA隱藏層設置為三層，節(jié)點數(shù)分別為300,25,25，三層的加噪程度分別為0.2,0.3,0.3，梯度下降的學習率為0.8，迭代次數(shù)為15。E2LSH算法參考文獻[14]進行參數(shù)設置，哈希表的個數(shù)L設置為20，因為該值過小導致檢索精度不夠，該值過大導致空間浪費且檢索精度并不會顯著提高。g(v)中哈希函數(shù)h(v)的個數(shù)k取5，h(v)中w值取經(jīng)驗值4。

3.3.2 實驗結果分析

圖6顯示了相似度計算方法對不同算法的影響，其中受相似度計算影響較大的兩種算法為基于SVD降維的項目近鄰推薦(記為SVD-ICF)和基于PCA降維的項目近鄰推薦方法(記為PCA-ICF)。采用原始數(shù)據(jù)、DAE降維和SDA降維后的數(shù)據(jù)以及文獻[14]的方法計算得到的近鄰相似度都大于0，因而不受影響。這是由于采用線性降維方法在提取特征時，特征向量的元素出現(xiàn)負值，導致計算相似近鄰時不夠穩(wěn)定和準確，這種情況可以通過本文所提出的相似度計算方法進行彌補，通過消除相似度過低的近鄰對評分預測的干擾，僅考慮相似度更高的近鄰，性能得到較大提升。

圖6 相似度計算對實驗結果的影響

圖7(a)(b)兩圖分別顯示了在熱啟動和冷啟動場景下，基于項目的不同推薦算法的準確率對比。在熱啟動場景下，各算法RMSE相差不大，改進相似度后的線性降維算法PCA-ICF和SVD-ICF的RMSE最小，文獻[14]的方法(LSH-ICF)、非線性降維算法DAE-ICF、本文方法與基本的ICF算法相當，本文方法略好。在冷啟動場景下，算法的預測準確率較于熱啟動有所下降，降維后比降維前的算法準確率高，本文方法較其他算法提升較為明顯，這是由于本文算法融入了項目的類別信息。

圖7 基于項目的推薦算法準確率對比

類似的，圖8(a)、(b)分別顯示了在熱啟動和冷啟動場景下，基于用戶的各種推薦算法的準確率對比。在熱啟動場景下，各算法準確率差異不大。在冷啟動條件下，文獻[14]的方法(LSH-UCF)準確率略高于基于SVD降維的方法(SVD-UCF)，基非線性降維算法的準確率明顯高于其他基于線性降維的算法，由于本文方法結合用戶的屬性信息，故在冷啟動場景下準確率最高。

圖9顯示了不同推薦算法的平均運行時間對比。圖中對比了三種有代表性的推薦算法在平均運行時間上的差異。ICF利用高維稀疏的原始評分數(shù)據(jù)進行推薦，平均運行時間最長；其次是PCA-CF，利用降維后的數(shù)據(jù)進行推薦，縮短了平均運行時間；平均運行時間最短的是本文方法和文獻[14]的方法(LSH-ICF)，兩種方法利用E2LSH檢索到相似近鄰后，僅需計算目標與近鄰之間的相似度，無需計算所有用戶或項目兩兩之間的相似度，從而提高了算法效率。與LSH-ICF相比，本文方法在冷啟動場景下的準確率更高，RMSE指標平均降低了約7.2%。

4 結語

本文提出一種基于SDA數(shù)據(jù)降維與E2LSH的信息推薦方法，該方法將高維稀疏的用戶-項目評分數(shù)據(jù)與用戶屬性、項目類別數(shù)據(jù)融合后作為SDA深度神經(jīng)網(wǎng)絡的輸入，通過迭代訓練得到低維稠密的用戶特征和項目特征。然后利用E2LSH算法對降維后的用戶或項目特征構建索引，通過檢索得到目標用戶或目標項目的相似近鄰。最后根據(jù)目標用戶或項目與相似近鄰之間的相似度，通過相似度加權來預測用戶對項目的評分。實驗結果表明，本文提出的數(shù)據(jù)降維方法能夠較好的提取原始評分數(shù)據(jù)中的有效信息，在降低數(shù)據(jù)維度的同時提高評分預測準確度，尤其是在冷啟動場景下優(yōu)勢較為明顯。另外，本文結合E2LSH檢索算法能夠快速找到目標的相似近鄰，運行效率較高。但是本文僅考慮了推薦準確率和運行效率，實際中推薦性能還受到推薦結果新穎度和覆蓋率的影響。通常情況下，準確率提高會導致新穎度和覆蓋率下降，因此，如何利用多策略推薦方法，在保證準確率的同時提高新穎度和覆蓋率是推薦算法的一個難點，也是未來研究工作的一個重點。

圖8 基于用戶的推薦算法準確率對比

圖9 不同推薦算法平均運行時間對比

References)

[1] MEHTA S J, JAVIA J. Threshold based KNN for fast and more accurate recommendations [C]// Proceedings of the 2015 IEEE 2nd International Conference on Recent Trends in Information Systems. Piscataway, NJ: IEEE, 2015: 109-113.

[2] YANG C, YU X, LIU Y. Continuous KNN join processing for real-time recommendation [C]// Proceedings of the 2014 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2014: 640-649.

[3] ZHU T, LI G, PAN L, et al. Privacy preserving collaborative filtering for KNN attack resisting [J]. Social Network Analysis and Mining, 2014, 4(1): 1-14.

[4] 李遠博,曹菡.基于PCA降維的協(xié)同過濾推薦算法[J].計算機技術與發(fā)展,2016,26(2):26-30.(LI Y B, CAO H. Collaborative filtering recommendation algorithm based on PCA dimension reduction [J]. Computer Technology and Development, 2016, 26(2): 26-30.)

[5] 郁雪,李敏強.一種結合有效降維和K-means聚類的協(xié)同過濾推薦模型[J].計算機應用研究,2009,26(10):3718-3720.(YU X, LI M Q. Collaborative filtering recommendation model based on effective dimension reduction andK-means clustering [J]. Application Research of Computers, 2009, 26(10): 3718-3720.)

[6] 林建輝,嚴宣輝,黃波.基于SVD與模糊聚類的協(xié)同過濾推薦算法[J].計算機系統(tǒng)應用,2016,25(11):156-163.(LIN J H, YAN X H, HUANG B. Collaborative filtering recommendation algorithm based on SVD and fuzzy clustering [J]. Computer Systems & Applications, 2016, 25(11): 156-163.)

[7] SARWAR B, KARYPIS G, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms [C]// Proceedings of the 10th International Conference on World Wide Web. New York: ACM, 2001: 285-295.

[8] WANG B, LIAO Q, ZHANG C. Weight based KNN recommender system [C]// Proceedings of the 2013 5th International Conference on Intelligent Human-Machine Systems and Cybernetics. Washington, DC: IEEE Computer Society, 2013,2: 449-452.

[9] 吳月萍,鄭建國.改進相似性度量方法的協(xié)同過濾推薦算法[J].計算機應用與軟件,2011,28(10):7-8.(WU Y P, ZHENG J G. Collaborative filtering recommendation algorithm on improved similarity measure method [J]. Computer Applications and Software, 2011, 28(10): 7-8.)

[10] 文俊浩,舒珊.一種改進相似性度量的協(xié)同過濾推薦算法[J].計算機科學,2014,41(5):68-71.(WEN J H, SHU S. Improved collaborative filtering recommendation algorithm of similarity measure [J]. Computer Science, 2014, 41(5): 68-71.)

[11] VINCENT P, LAROCHELLE H, BENGIO Y, et al. Extracting and composing robust features with denoising autoencoders [C]// Proceedings of the 25th International Conference on Machine Learning. New York: ACM, 2008: 1096-1103.

[12] BENGIO Y, LAMBLIN P, POPOVICI D, et al. Greedy layer-wise training of deep networks [EB/OL]. [2016- 12- 05]. http://papers.nips.cc/paper/3048-greedy-layer-wise-training-of-deep-networks.pdf.

[13] ANDONI A, INDYK P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions [C]// Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 2006: 459-468.

[14] 李紅梅,郝文寧,陳剛.基于精確歐氏局部敏感哈希的協(xié)同過濾推薦算法[J].計算機應用,2014,34(12):3481-3486.(LI H M, HAO W N, CHEN G. Collaborative filtering recommendation algorithm based on exact Euclidean locality-sensitive hashing [J]. Journal of Computer Applications, 2014, 34(12): 3481-3486.)

[15] 周杰,李弼程,唐永旺.基于關鍵證據(jù)與E2LSH的增量式人名聚類消歧方法[J].情報學報,2016,35(7):714-722.(ZHOU J, LI B C, TANG Y W. Incremental clustering method based on key evidence and E2LSH for person name disambiguation [J]. Journal of the China Society for Scientific and Technical Information, 2016, 35(7): 714-722.)

[16] 鄧俊鋒,張曉龍.基于自動編碼器組合的深度學習優(yōu)化方法[J].計算機應用,2016,36(3):697-702.(DENG J F, ZHANG X L. Deep learning algorithm optimization based on combination of auto-encoders [J]. Journal of Computer Applications, 2016, 36(3): 697-702.)

[17] 冷亞軍,梁昌勇,陸青,等.基于近鄰評分填補的協(xié)同過濾推薦算法[J].計算機工程,2012,38(21):56-58.(LENG Y J, LIANG C Y, LU Q, et al. Collaborative filtering recommendation algorithm based on neighbor rating imputation [J]. Computer Engineering, 2012, 38(21): 56-58.)

RecommendationmethodbasedonknearestneighborsusingdatadimensionalityreductionandexactEuclideanlocality-sensitivehashing

GUO Yudong, GUO Zhigang*, CHEN Gang, WEI Han

(CollegeofInformationSystemEngineering,InformationEngineeringUniversity,ZhengzhouHenan450002,China)

There are several problems in the recommendation method based onknearest neighbors, such as high dimensionality of rating features, slow speed of searching nearest neighbors and cold start problem of ratings. To solve these problems, a recommendation method based onknearest neighbors using data dimensionality reduction and Exact Euclidean Locality-Sensitive Hashing (E2LSH) was proposed. Firstly, the rating data, the user attribute data and the item category data were integrated as the input data to train the Stack Denoising Auto-encoder (SDA) neutral network, of which the last hidden layer values were used as the feature coding of the input data to complete data dimensionality reduction. Then, the index of the reduced dimension data was built by the Exact Euclidean Local-Sensitive Hash algorithm, and the target users or the target items were retrieved to get their similar nearest neighbors. Finally, the similarities between the target and the neighbors were calculated, and the target user’s similarity-weighted prediction rating for the target item was obtained. The experimental results on standard data sets show that the mean square error of the proposed method is reduced by an average of about 7.2% compared with the recommendation method based on Locality-Sensitive Hashing (LSH-ICF), and the average run time of the proposed method is the same as LSH-ICF. It shows that the proposed method alleviates the rating cold start problem on the premiss of keeping the efficiency of LSH-ICF.

information recommendation; Stack Denoising Auto-encoder (SDA); Exact Euclidean Locality-Sensitive Hashing (E2LSH); data dimensionality reduction; cold start

2017- 03- 22;

2017- 05- 22。

國家社會科學基金資助項目(14BXW028)。

郭喻棟(1991—)，男，河南孟津人，碩士研究生，主要研究方向: 機器學習、數(shù)據(jù)挖掘； 郭志剛(1973—)，男，河南鄭州人，副教授，碩士，主要研究方向：智能信息處理、機器學習、數(shù)據(jù)挖掘； 陳剛(1979—)，男，湖北黃岡人，講師，博士研究生，主要研究方向：智能信息處理、機器學習、數(shù)據(jù)挖掘； 魏晗(1981—)，女，河南鄭州人，講師，碩士，主要研究方向：智能信息處理、機器學習、數(shù)據(jù)挖掘。

1001- 9081(2017)09- 2665- 06

10.11772/j.issn.1001- 9081.2017.09.2665

TP391.1

A

This work is partially supported by the National Social Science Foundation of China (14BXW028).

GUOYudong, born in 1991, M. S. candidate. His research interests include machine learning, data mining.

GUOZhigang, born in 1973, M. S., associate professor. His research interests include intelligent information processing, machine learning, data mining.

CHENGang, born in 1979, Ph. D. candidate, lecturer. His research interests include intelligent information processing, machine learning, data mining.

WEIHan, born in 1981, M. S., lecturer. Her research interests include intelligent information processing, machine learning, data mining.