夏小娜 鄒 麒

1(曲阜師范大學(xué)統(tǒng)計學(xué)院 山東 曲阜 273165)2(曲阜師范大學(xué)信息科學(xué)與工程學(xué)院 山東 日照 276826)

0 引 言

個性化推薦是大數(shù)據(jù)和在線應(yīng)用的關(guān)鍵技術(shù)。通過捕捉用戶的行為偏好與目標(biāo)需求，自主為用戶提供合適的服務(wù)。這里涉及兩個需求背景：一是用戶知道自己需要的具體是什么，二是用戶并不知道。這兩方面都需要有效的推薦策略。推薦時需要綜合考慮用戶自身的潛在需求，也要考慮受鄰近用戶的影響。但無論是面對怎樣的需求背景，當(dāng)大量的服務(wù)結(jié)果呈現(xiàn)在用戶面前時，用戶并不能客觀評估排序潛在的大量可供選擇的服務(wù)?；诮y(tǒng)計預(yù)測的推薦策略幫助用戶從海量候選結(jié)果中提供有用和有效的建議，或者做有意義的引導(dǎo)和啟發(fā)。

協(xié)同過濾是實現(xiàn)個性化統(tǒng)計、預(yù)測和推薦常用的方法之一，它對群體進行搜索，從中找出與用戶興趣偏好近似的其他用戶作為“興趣近鄰”，對近鄰所偏好的相關(guān)內(nèi)容進行分析和考察，將它們組合起來，計算近似度和推薦權(quán)重，構(gòu)造出排序的候選列表[1]。

在對大數(shù)據(jù)集進行分析并生成推薦列表時，基于物品的過濾推薦方法明顯要比基于用戶的更快，但存在維護物品相似度表的額外開銷?；谖锲返耐扑]和基于用戶的推薦，對于數(shù)據(jù)集的稀疏性處理存在差異，但算法的本質(zhì)是類似的[2-3]，在搜索鄰近用戶時，以基于用戶或物品的相似度為基礎(chǔ)，所實現(xiàn)的推薦效果取決于相似度度量的準(zhǔn)確性和有效性，以及關(guān)于相似度空間搜索和計算過程的能力。鄰近用戶的“鄰近”體現(xiàn)為用戶間關(guān)于目標(biāo)的近似選擇，以此所體現(xiàn)的近似興趣偏好，是圍繞用戶興趣借助算法實現(xiàn)的用戶鄰近域界定，即為“興趣近鄰”[4-5]。

有關(guān)在線平臺的服務(wù)推薦，無論是基于用戶的推薦還是基于物品的推薦，相關(guān)的評分向量都是高維的，在高維數(shù)據(jù)空間中做到快速地定位相似的用戶或者物品，一般情況下有兩種解決思路：最近鄰域檢索和近似最近鄰檢索。因檢索過程是個NP問題，因此通常采取近似最近鄰方式。LSH(Locality-Sensitive Hash)[6]就是其中有效的研究方法。LSH的含義表征為將高維空間中鄰近的點HASH映射到低維空間后仍距離較近，原本較遠的點映射后仍具有較遠的距離[7]。本文改進LSH應(yīng)用模型，充分計算用戶需求域的鄰近關(guān)聯(lián)信息，結(jié)合用戶自身的潛在偏好趨向，構(gòu)造自主的統(tǒng)計預(yù)測機制，設(shè)計了ILSH算法。

1 相關(guān)工作

基于分布式敏感哈希，設(shè)計隱私保護和可拓展的服務(wù)推薦方法[8]。有效降低實時推薦的運算復(fù)雜度，提高評分?jǐn)?shù)據(jù)在高維空間中的相似性查詢效率；通過運用兩個LSH策略分類高維數(shù)據(jù)[13]，加入增量聚類算法，批量合并相似度矩陣以合并離線聚類算法；LSH兩級結(jié)構(gòu)可以提高檢索效率[15]，將提取的特征外包給云服務(wù)器還需要做深入的研究，以便于減輕數(shù)據(jù)所有者和數(shù)據(jù)用戶的負(fù)擔(dān)；進一步，使得LSH用于視頻的異常檢測方法[17]，將正?；顒由⒘械蕉鄠€特征桶中，過濾異?；顒?，以此實現(xiàn)在線更新程序融入適應(yīng)視頻場景變化的LSH框架。

基于鄰近搜索機制，可實現(xiàn)多對象優(yōu)化算法和局部敏感哈希的協(xié)同，解決“一對多”“多對一”動態(tài)選擇和傳遞問題[9-10]。利用LSH發(fā)現(xiàn)真正感興趣的事件，加快集群發(fā)現(xiàn)過程，保持聚類質(zhì)量[11]。但該方法并沒有應(yīng)用于多個社交媒體數(shù)據(jù)集，無法比較同一事件在多個平臺的效果，方法還需要充分檢驗以擴展到更復(fù)雜的情形。

LSH在Web服務(wù)中也得到了有效運用。針對Map-Reduce中聚類大規(guī)模數(shù)據(jù)集時的有效分布式密度峰值問題[12]，設(shè)計LSH進化算法，以支持用戶指定所期望的近似準(zhǔn)確度，減少清洗數(shù)據(jù)和計算消耗；設(shè)計基于MapReduce編程模型的LSH并行集合相似度關(guān)聯(lián)方法，可以減少計算相似度時需求比較的次數(shù)；實現(xiàn)LSH在WoS(Web of Science)和Scopus匹配中的應(yīng)用[16]，實現(xiàn)檢測精確匹配，利于衡量高頻數(shù)據(jù)的重疊情況。

SLH已得到了廣泛應(yīng)用，許多有關(guān)SLH的研究，多半是局限于某一領(lǐng)域或者特定數(shù)據(jù)集參數(shù)的調(diào)優(yōu)，或者直接用于部分?jǐn)?shù)據(jù)的處理[18]，并沒有從SLH數(shù)據(jù)結(jié)構(gòu)和算法流程上進行調(diào)整和改進，在應(yīng)用過程中，同樣也帶來了其他沒有解決的問題。

SLH已得到了廣泛應(yīng)用，許多有關(guān)SLH的研究，多半是局限于某一領(lǐng)域或者特定數(shù)據(jù)集參數(shù)的調(diào)優(yōu)，或者直接用于部分?jǐn)?shù)據(jù)的處理[18]，并沒有從SLH數(shù)據(jù)結(jié)構(gòu)和算法流程上進行調(diào)整和改進，在應(yīng)用過程中，同樣也帶來了其他沒有解決的問題。本文從SLH設(shè)計結(jié)構(gòu)出發(fā)，擴展優(yōu)化算法，在提高統(tǒng)計預(yù)測運算效率的前提下，提高興趣相似度的有效傳遞。

2 局部敏感哈希

2.1 基本定義

定義1敏感的函數(shù)族

給定一族哈希函數(shù)，是一個從歐式空間到哈希編碼空間的映射。如果以下兩個條件都滿足，則稱此哈希函數(shù)為敏感的函數(shù)族[12]。

(1) 若p∈B(q,r1)，則PrH[h(q)=h(p)]≥p1；

(2) 若p?B(q,r2)，則PrH[h(q)=h(p)]≤p2。

定義中B表示的是以q為中心，r1或r2為半徑的空間，圖1是該定義的坐標(biāo)系分布描述。

圖1 定義1圖例

定義2給定數(shù)據(jù)集S及相關(guān)的局部敏感哈希族x,y∈S，若數(shù)據(jù)對象x,y∈S成立，應(yīng)滿足定義為[13]:

Ph∈H[h(x)=h(y)]=sim(x,y)

(1)

上述兩種定義的定義角度不同使得這兩種定義在形式上差距很大，但是本質(zhì)上是一致的，即越相近的數(shù)據(jù)對象發(fā)生哈希沖突的概率越高。

2.2 基本思想

在進行預(yù)測推薦時，無論是user-base還是item-base，預(yù)測過程的相似度計算其本質(zhì)都是基于物品的評分向量，由用戶和評分形成矩陣，具有高維的特點。要實現(xiàn)快速尋求相似的用戶或者物品，需要圍繞用戶或者物品進行近鄰檢索。

LSH的核心理念是通過一組哈希函數(shù)，把相似的數(shù)據(jù)對象哈希到相同的哈希桶中，越相似的對象被哈希到相同桶中的概率越高。這些桶中的數(shù)據(jù)對象構(gòu)成目標(biāo)候選集，從而過濾掉大量的相似概率很低的數(shù)據(jù)對象。

一般情況下，使用HASH技術(shù)有效避免沖突，如使用HashTable實現(xiàn)與Redis的一致性哈希過程。若經(jīng)過Hashing后，兩組數(shù)據(jù)具有相同的HASH VALUE，則LSH認(rèn)為同兩對象是具有相似性的。這樣，對每一次近似近鄰的查詢過程只需要對待檢測的對象進行同樣的哈希過程，直接從對應(yīng)的HASH VALUE特征桶中找到相似的對象。

建立一個哈希函數(shù)族，每個函數(shù)隨機生成不同的邊界，邊界之間形成區(qū)域。每個函數(shù)進行向量運算，生成一條有向線，如圖2所示，這些有向線的集合即是哈希族。生成有向線的條數(shù)是窮舉過程，目的是找到一個合適的位置，最終被圈在同一區(qū)域的點將視為相鄰的。

圖2 LSH算法思想的幾何圖形解釋

LSH運算快，可以跨平臺實現(xiàn)合作推薦，而不破壞用戶的隱私。但LSH隨機分域過程也可能存在錯誤。解決這個問題有兩個思路：一是使用多個獨立的哈希表，進行多次區(qū)域分割；二是推薦前的多檢索策略，對于每一次檢索進行評分預(yù)測，求取平均。

2.3 增強局部敏感哈希

局部敏感哈希的定義中不難看出，LSH雖然是近似最優(yōu)技術(shù)，但是并不能保證計算結(jié)果的精確性，通過LSH我們能得到一個或多個Hash表，一次哈希會有很大的可能性將非相似的數(shù)據(jù)哈希到相同的哈希桶中，這種將非相似數(shù)據(jù)對象哈希到相同哈希桶中的情形稱為納偽(False Positive)。同時未將真正相似的對象哈希到相同哈希桶中的情形稱為拒真(False Negative)。為了保證局部敏感哈希的查詢質(zhì)量，需要盡量降低False Positive和False Negative，也就是實現(xiàn)LSH的增強。常用的增強LSH的方法有使用多個獨立的哈希表，運用AND、OR、XOR等操作以及這些操作的級聯(lián)運算。

增強局部敏感哈希的執(zhí)行過程體現(xiàn)為：

輸入: “user-item”評分記錄，pool_size代表每個哈希表所對應(yīng)哈希函數(shù)的個數(shù)，hash_count是哈希表的個數(shù)。

輸出: 具有hash_count個數(shù)目的哈希索引結(jié)構(gòu)。

過程:

Step1算法初始化。將“user-item”評分記錄轉(zhuǎn)換為“user-item”評分矩陣，具有m個用戶、n個項目的評分矩陣Dm×n表征為：

對于一個用戶，其評分記錄可以表示為向量uk=(itemk,1.q,itemk,2.q,…,itemk,m.q)，其中itemk,l.q(1≤l≤n，1≤k≤m)表示用戶k對于物品的評分，若該用戶從未評議過該項目則該評分為0。

Step2LSH構(gòu)造。對于每個用戶u∈U，根據(jù)既定的哈希函數(shù)族{hk(u)}將評分記錄向量uk映射到哈?？臻g中。hk(u)計算公式表示為：

(2)

式中：v是一個m維向量(v1,v2,…,vm)，(1≤i≤m),其中vi的取值范圍為[-1,1]，運算符°表示對兩個向量進行點積運算。

對于式(2)可以用一下物理模型進行描述：

向量v是一個對高維空間進行分割的超平面，LSH的過程即是將分布在高維評分空間中的用戶評分點集進行區(qū)域劃分，基于前文中關(guān)于LSH基本思想的闡述，如果兩個點相似，則會有極高的概率被超平面劃分到同一個區(qū)域當(dāng)中。

Step 3LSH索引構(gòu)建。對于Dm×n中的每一個評分向量uk=(itemk,1.q,itemk,2.q,…,itemk,m.q)，利用哈希函數(shù)進行映射，并對每個哈希表進行分桶構(gòu)建索引。

Step 4用戶的興趣相似性檢索。有關(guān)用戶的興趣相似性檢索，只需將hash_count個哈希表中處于一個桶中的所有用戶的并集作為待預(yù)測目標(biāo)用戶的興趣最近鄰集合。在此基礎(chǔ)上，運用上述三步，計算目標(biāo)最鄰近用戶的在線哈希族函數(shù)個數(shù)N，找到規(guī)模等于N的哈希桶，將用戶作為相似的候選“近鄰”放進哈希桶。

3 ILSH統(tǒng)計預(yù)測算法

現(xiàn)實中的推薦系統(tǒng)的物品遠遠多于用戶，而對于單個用戶而言，其評分向量往往是極其稀疏的。單純通過LSH算法找到目標(biāo)用戶的相似用戶進而對所有物品進行無差別的加權(quán)相加預(yù)測評分，并沒有考慮到用戶會對特定的產(chǎn)品存在一定的愛好偏差這一基本消費心理。因此，本文的ILSH只將相似用戶對相似物品進行平均加權(quán)取值，用以描述用戶對特定物品的愛好偏差。

設(shè)定待預(yù)測目標(biāo)用戶u的最近鄰集合表示為U，目標(biāo)物品i的最近鄰集合為I，Rvi是近鄰用戶v對物品i的評分，則用戶u對i的預(yù)測評分為：

(3)

基于改進LSH(后文用ILSH表示)的統(tǒng)計預(yù)測算法主要分為四個步驟，偽碼描述如算法1-算法4。

算法1構(gòu)建LSH-family

Hash_count： 哈希表的個數(shù)

Pool_size： 每個哈希表中哈希函數(shù)的個數(shù)，即哈希值

Dimensions： 評分向量維度

H(·)： LSH函數(shù)族

Fork=1toHash_count

Forg=1topool_size

Forl=1toDimensions

Pkgl=random[-1,1]

EndFor

vk=(Pkg1,Pkg2,…,Pkgdimensions)

EndFor

Hk=(v1,v2,…,vpool_size)

EndFor

算法2分別對user和item構(gòu)建索引

u(j)：用戶j的評分向量

i(k)：物品k的評分向量

Hu(·)：根據(jù)用戶評分向量建立的LSH-family

Hi(·)：根據(jù)物品評分向量建立的LSH-family

Users：用戶列表

Items：為物品列表

/*根據(jù)用戶評分向量和物品評分向量建立不同

維度的LSH-family和哈希表*/

Foru(j)inUsers

Hj(u(j))=(v1·u(j),v2·u(j),…)

Ubucket[Hj(u(j))]·append(userj)

Fori(k)inItems

Hk(i(k))=(v1·i(k),v2·i(k),…)

Ibucket[Hk(i(k))]·append(itemk)

算法3相似性檢索

Utarget： 目標(biāo)用戶

Itarget： 目標(biāo)物品

Forx=1toHash_count

hvu=Hu(Utarget)

uset+=Ubucke[hvu]

EndFor

Fory=1toHash_count

hvi=Hi(Itarget)

Iset+=Ibucket[hvi]

Endfor

EndFor

算法4統(tǒng)計預(yù)測評分

similar_ratings=rating[uset,:]

similar_ratings=similar_ratings[:,Iset]

p_rating=similar_ratings

[similar_ratings.nonzero()]mean()

4 實 驗

4.1 訓(xùn)練數(shù)據(jù)集及評價指標(biāo)

ILSH算法的實驗數(shù)據(jù)集選自University of Minnesota的GroupLens課題組提供MovieLens(http://grouplens.org/datasets/movielens/)，涉及6 040個用戶關(guān)于3 706部電影的評議投票，共包括1 000 000個評分記錄，設(shè)定電影的評分?jǐn)?shù)值分布在區(qū)間[0, 5]。評分越高，則表明某用戶對某電影的興趣偏好度越大。

有關(guān)用戶的評分統(tǒng)計度量標(biāo)準(zhǔn)定位于平均絕對誤差(Mean Absolute Error, MAE)，通過計算興趣偏好近似用戶的評分與待評估的目標(biāo)用戶評分之間的偏差，根據(jù)此偏差大小預(yù)測準(zhǔn)確性。平均絕對誤差的數(shù)值越小，推薦準(zhǔn)確性越高。假設(shè)待預(yù)測的用戶評分表示為向量表達式p=(p1,p2,…,pm)，實際的用戶評分向量為r=(r1,r2,…,rm)，則平均絕對誤差為：

(4)

4.2 實驗設(shè)計及結(jié)果分析

4.2.1pool_size和hash_count的選擇

為了提高哈希的查詢質(zhì)量，盡量降低False Positive和False Negative，在實施中，通常會采用兩種策略[14]：

(1) 在一個Hash表內(nèi)使用更多的哈希函數(shù)；

(2) 建立多個Hash表。

本文實驗主要考察pool_size和hash_count兩個參數(shù)對實驗結(jié)果的影響，訓(xùn)練過程如圖3-圖5所示。用PYTHON實現(xiàn)本文算法，從實驗數(shù)據(jù)的訓(xùn)練結(jié)果中可以看出，當(dāng)相關(guān)參數(shù)值分別設(shè)定為pool_size=7, hash_count=12， 所得到的MAE結(jié)果值最低，也是最好的實驗結(jié)果。通過取不同的參數(shù)值訓(xùn)練數(shù)據(jù)可以看出，對于興趣度相似或近似的用戶，可以取得更好的檢索準(zhǔn)確率，從而確保較高的目標(biāo)服務(wù)推薦質(zhì)量，提高用戶的滿意度。

圖3 不同參數(shù)對MAE的影響

圖4 不同參數(shù)對MAE的影響

圖5 不同參數(shù)對MAE的影響

4.2.2與傳統(tǒng)基于用戶/物品的協(xié)同過濾算法的對比

為檢驗ILSH算法的優(yōu)勢，在算法訓(xùn)練中，我們劃定不同用戶評分的稀疏數(shù)據(jù)矩陣展開針對性檢驗。稀疏數(shù)據(jù)并非無用數(shù)據(jù)，數(shù)據(jù)的稀疏度指的是不存在數(shù)據(jù)的多維結(jié)構(gòu)的單元的相對百分比，在數(shù)據(jù)稀疏的前提下從多維結(jié)構(gòu)中能否學(xué)習(xí)并挖掘出更多有效數(shù)據(jù)，是算法的一個重要衡量指標(biāo)。這里我們設(shè)定稀疏度計量區(qū)間為[0.100,0.300]，步長為0.025，在近似用戶評分矩陣的刪除數(shù)據(jù)比例上，比較用戶評分矩陣的稀疏度所實現(xiàn)的數(shù)據(jù)獲取效果，即對比本文提出的ILSH與傳統(tǒng)的基于用戶PCC(User-based Pearson Correlation Coefficient, UPCC)的協(xié)同過濾算法和基于物品(Item-based Peason Correlation Coefficient, IPCC)的協(xié)同過濾算法的MAE值。根據(jù)4.2.1節(jié)的實驗結(jié)果，設(shè)定hash_count=12，pool_size=7。

實驗結(jié)果如圖6所示，當(dāng)數(shù)據(jù)稀疏度逐漸上升時，UPCC、IPCC、ILSH的MAE都會有一定程度的上升，但本文提出的ILSH算法的MAE一直處于較小的水平，且比傳統(tǒng)的UPCC和IPCC的MAE低很多。

圖6 UPCC、IPCC、ILSH的MAE隨著 數(shù)據(jù)稀疏度變化的對比

4.2.3ILSH與最新LSH改進算法的比較

為將ILSH同最新LSH算法的執(zhí)行結(jié)果進行有效比較，采用了與4.2.1節(jié)相同的實驗方案，選取不同的用戶評分矩陣稀疏度，比較用戶評分矩陣在不同的稀疏度下兩種算法的MAE，實驗對比結(jié)果如圖7所示。

圖7 相關(guān)LSH算法與ILSH算法的MAE應(yīng) 對數(shù)據(jù)稀疏度的變化對比

從圖7中可以看出，本文提出的ILSH算法的MAE值一直處于較低的水平且一直比IPLSH和UPLSH要低。這驗證了ILSH算法的相對穩(wěn)定性和準(zhǔn)確性。

5 結(jié) 語

針對物品推薦體系中高維的用戶評分?jǐn)?shù)據(jù)以及物品選擇和管理的數(shù)據(jù)稀疏性對推薦決策帶來的影響，本文基于最新LSH優(yōu)化算法提出了基于ILSH的統(tǒng)計預(yù)測算法。實驗表明，本文提出的ILSH能很好地應(yīng)對海量高維數(shù)據(jù)近似計算，有效減少數(shù)據(jù)稀疏度對統(tǒng)計預(yù)測精度的影響。今后將基于興趣偏好的“近鄰的近鄰也是我的近鄰”這一理論，結(jié)合機器學(xué)習(xí)算法提高用戶興趣統(tǒng)計預(yù)測結(jié)果的準(zhǔn)確性和智能性。