鄒曉瑜

（廣東工業(yè)大學(xué) 信息工程學(xué)院，廣東 廣州 511400）

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

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

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

1 相關(guān)理論知識

1.1 主成分分析法

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

對PCA主成分部分組成的低維表征Y，在聚類算法中可將其視為聚類成員評價(jià)指標(biāo)的連續(xù)解，PCA與聚類算法可建立聯(lián)系，也為PCA和聚類算法進(jìn)行組合提供了可能性。

1.2 拉普拉斯特征映射

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

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

其中，限定約束條件YYT=I確保目標(biāo)函數(shù)有解。式（3）可通過拉格朗日乘子法求解，將優(yōu)化問題轉(zhuǎn)為廣義特征值求解問題。

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

1.3 圖PCA

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

式（4）設(shè)置系數(shù)η平衡兩個(gè)子式的貢獻(xiàn)程度，并通過求解封閉解實(shí)現(xiàn)降維。圖PCA方法可改善單一降維方法在保留數(shù)據(jù)結(jié)構(gòu)特征上的不足，提高算法性能。

1.4 精確歐式局部敏感哈希

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

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

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

本文提出的協(xié)同過濾改進(jìn)方法，包含基于圖PCA數(shù)據(jù)降維、基于E2LSH相似近鄰搜索及預(yù)測評分3個(gè)部分，接下來對方法的基本流程和關(guān)鍵技術(shù)進(jìn)行詳細(xì)闡述。

2.1 基于圖PCA的數(shù)據(jù)降維

計(jì)算用戶或項(xiàng)目間相似度時(shí)，若直接采用原始高維評分作為特征，會(huì)降低推薦算法的計(jì)算效率，因此，使用圖PCA降維方法進(jìn)行數(shù)據(jù)降維，通過求解目標(biāo)函數(shù)式（4）得到降維后的新表征特征矩陣。先固定參數(shù)Y，求關(guān)于W的最優(yōu)化問題，此時(shí)，目標(biāo)函數(shù)Q對W求偏導(dǎo)的結(jié)果為0，即：

化簡得到XY＝W，再代入求解關(guān)于Y的最優(yōu)化問題，此時(shí)，式（4）轉(zhuǎn)化為：

將式中X－XYYT部分Frobenius范數(shù)轉(zhuǎn)為跡的形式，式（7）最終化簡成：

此時(shí)，圖PCA優(yōu)化問題轉(zhuǎn)為求解-XXT+ηL的特征向量問題。將特征值從小到大排序，依次選擇m個(gè)最小非零特征值對應(yīng)的特征向量則組成原始數(shù)據(jù)的低維表征Y。

2.2 基于E2LSH相似近鄰搜索

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

對目標(biāo)用戶進(jìn)行快速檢索時(shí)，先根據(jù)用戶的哈希索到對應(yīng)哈希桶，將桶中用戶取出并去重后，得到目標(biāo)用戶的相似近鄰用戶。

2.3 預(yù)測用戶評分

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

通過改進(jìn)計(jì)算方法去掉差異較大的樣本結(jié)果后，還慮用戶不同打分習(xí)慣帶來的預(yù)測結(jié)果偏差。本文采用均值化思想預(yù)測評分：計(jì)算得到相似近鄰用戶的改進(jìn)余弦相似度后，根據(jù)相似度結(jié)果從高往低排序，選擇前k個(gè)相似度最高的近鄰客戶，將其評分按相似度進(jìn)行加權(quán)融合，得到目標(biāo)用戶的最終預(yù)測評分，最后根據(jù)各項(xiàng)目預(yù)測所得評分高低，產(chǎn)生推薦結(jié)果。

3 實(shí)驗(yàn)設(shè)置與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

本文實(shí)驗(yàn)在64位Windows7系統(tǒng)下運(yùn)行測試，系統(tǒng)為內(nèi)存8 GB。實(shí)驗(yàn)數(shù)據(jù)使用明尼蘇達(dá)大學(xué)提供的MovieLens電影評分?jǐn)?shù)據(jù)，數(shù)據(jù)集共包含610名用戶對9 724個(gè)電影項(xiàng)目的100 873條評分?jǐn)?shù)據(jù)，評分范圍為0.5～5分，分值越高，表示用戶越喜愛該電影，0分則表示未評分。

3.2 評估指標(biāo)

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

其中，ru,i表示用戶u對項(xiàng)目i的實(shí)際評分，r～u,i表示模型的預(yù)測評分，s則表示測試樣本中數(shù)據(jù)的數(shù)量。

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

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

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

圖1 特征維度對算法運(yùn)行時(shí)間、RMSE的影響

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

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

4 結(jié)語

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