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

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

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

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

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

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

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

0 引言

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

基于k近鄰的推薦算法[1-3]是一種常用的推薦模型，可以分為基于用戶近鄰的推薦算法和基于項(xiàng)目近鄰的推薦算法。基于用戶近鄰的推薦算法主要分為以下步驟：根據(jù)用戶的特征計(jì)算兩兩用戶之間的相似度；針對目標(biāo)用戶，找到與之最相似的用戶近鄰集合；在估計(jì)目標(biāo)用戶對某一項(xiàng)目的評分時(shí)，利用近鄰集合中用戶對該項(xiàng)目的評分，通過相似度加權(quán)，來預(yù)測目標(biāo)用戶的評分。

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

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

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

1 相關(guān)理論

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

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

圖1 SDA神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

SDA的第l層隱層到下一層和第2L-l+1層隱層到下一層構(gòu)成一對編解碼器，編碼函數(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)絡(luò)參數(shù)W和b。Wl是第l層與上一層之間的權(quán)重，Wl和W2L-l+1互為轉(zhuǎn)置，由編碼器和解碼器共享，稱為一對捆綁權(quán)重[12]。hl和h2L-l+1分別是編碼器和解碼器的輸入向量，bl和b2L-l+1是偏置向量。

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

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)是預(yù)訓(xùn)練階段的損失函數(shù)，C(x,x′)是微調(diào)階段的損失函數(shù)，x″是加噪后的輸入，hl是網(wǎng)絡(luò)第l層的數(shù)據(jù)，當(dāng)l=0時(shí)，hl分和h2(L+1)-l分別為整個(gè)網(wǎng)絡(luò)的輸入x和輸出x′。

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

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

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

若‖t-v‖P1；

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

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

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

(6)

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

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

(7)

(8)

2 基于數(shù)據(jù)降維和E2LSH的k近鄰?fù)扑]算法

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

2.1 基本流程

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

圖3 本文方法基本流程

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

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

3)評分預(yù)測。計(jì)算目標(biāo)用戶或項(xiàng)目與相似近鄰之間的相似度，利用相似近鄰的評分記錄，通過相似度加權(quán)來預(yù)測未知評分。

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

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

1)確定SDA的網(wǎng)絡(luò)結(jié)構(gòu)，設(shè)置輸入層維數(shù)、隱藏層個(gè)數(shù)、各隱藏層維數(shù)以及各層的加噪比例。然后融合評分?jǐn)?shù)據(jù)和用戶/項(xiàng)目標(biāo)簽數(shù)據(jù)，對數(shù)據(jù)加噪后以向量的形式作為SDA的輸入。

圖4 SDA訓(xùn)練過程

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

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

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

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

2.3 基于E2LSH的相似近鄰選擇

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

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

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

圖5 索引構(gòu)建示意圖

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

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

2.4 相似度計(jì)算

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

(8)

(9)

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

2.5 評分預(yù)測

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

(10)

(11)

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

3.2 評價(jià)指標(biāo)

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

(12)

3.3 實(shí)驗(yàn)設(shè)置與結(jié)果分析

3.3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

3.3.2 實(shí)驗(yàn)結(jié)果分析

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

圖6 相似度計(jì)算對實(shí)驗(yàn)結(jié)果的影響

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

圖7 基于項(xiàng)目的推薦算法準(zhǔn)確率對比

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

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

4 結(jié)語

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

圖8 基于用戶的推薦算法準(zhǔn)確率對比

圖9 不同推薦算法平均運(yùn)行時(shí)間對比

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] 李遠(yuǎn)博,曹菡.基于PCA降維的協(xié)同過濾推薦算法[J].計(jì)算機(jī)技術(shù)與發(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] 郁雪,李敏強(qiáng).一種結(jié)合有效降維和K-means聚類的協(xié)同過濾推薦模型[J].計(jì)算機(jī)應(yīng)用研究,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] 林建輝,嚴(yán)宣輝,黃波.基于SVD與模糊聚類的協(xié)同過濾推薦算法[J].計(jì)算機(jī)系統(tǒng)應(yī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] 吳月萍,鄭建國.改進(jìn)相似性度量方法的協(xié)同過濾推薦算法[J].計(jì)算機(jī)應(yīng)用與軟件,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] 文俊浩,舒珊.一種改進(jìn)相似性度量的協(xié)同過濾推薦算法[J].計(jì)算機(jī)科學(xué),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].計(jì)算機(jī)應(yīng)用,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] 周杰,李弼程,唐永旺.基于關(guān)鍵證據(jù)與E2LSH的增量式人名聚類消歧方法[J].情報(bào)學(xué)報(bào),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] 鄧俊鋒,張曉龍.基于自動(dòng)編碼器組合的深度學(xué)習(xí)優(yōu)化方法[J].計(jì)算機(jī)應(yīng)用,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] 冷亞軍,梁昌勇,陸青,等.基于近鄰評分填補(bǔ)的協(xié)同過濾推薦算法[J].計(jì)算機(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。

國家社會(huì)科學(xué)基金資助項(xiàng)目(14BXW028)。

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