基于興趣相似度傳遞的增強(qiáng)LSH統(tǒng)計(jì)預(yù)測算法

夏小娜 鄒 麒

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

LSH在Web服務(wù)中也得到了有效運(yùn)用。針對(duì)Map-Reduce中聚類大規(guī)模數(shù)據(jù)集時(shí)的有效分布式密度峰值問題[12]，設(shè)計(jì)LSH進(jìn)化算法，以支持用戶指定所期望的近似準(zhǔn)確度，減少清洗數(shù)據(jù)和計(jì)算消耗；設(shè)計(jì)基于MapReduce編程模型的LSH并行集合相似度關(guān)聯(lián)方法，可以減少計(jì)算相似度時(shí)需求比較的次數(shù)；實(shí)現(xiàn)LSH在WoS(Web of Science)和Scopus匹配中的應(yīng)用[16]，實(shí)現(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)和算法流程上進(jìn)行調(diào)整和改進(jìn)，在應(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)和算法流程上進(jìn)行調(diào)整和改進(jìn)，在應(yīng)用過程中，同樣也帶來了其他沒有解決的問題。本文從SLH設(shè)計(jì)結(jié)構(gòu)出發(fā)，擴(kuò)展優(yōu)化算法，在提高統(tǒng)計(jì)預(yù)測運(yùn)算效率的前提下，提高興趣相似度的有效傳遞。

2 局部敏感哈希

2.1 基本定義

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

給定一族哈希函數(shù)，是一個(gè)從歐式空間到哈希編碼空間的映射。如果以下兩個(gè)條件都滿足，則稱此哈希函數(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ù)對(duì)象x,y∈S成立，應(yīng)滿足定義為[13]:

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

(1)

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

2.2 基本思想

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

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

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

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

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

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

2.3 增強(qiáng)局部敏感哈希

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

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

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

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

過程:

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

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

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

(2)

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

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

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

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

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

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

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

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

(3)

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

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

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

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

Dimensions： 評(píng)分向量維度

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分別對(duì)user和item構(gòu)建索引

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

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

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

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

Users：用戶列表

Items：為物品列表

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

維度的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)計(jì)預(yù)測評(píng)分

similar_ratings=rating[uset,:]

similar_ratings=similar_ratings[:,Iset]

p_rating=similar_ratings

[similar_ratings.nonzero()]mean()

4 實(shí) 驗(yàn)

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

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

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

(4)

4.2 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

4.2.1pool_size和hash_count的選擇

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

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

(2) 建立多個(gè)Hash表。

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

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

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

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

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

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

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

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

4.2.3ILSH與最新LSH改進(jìn)算法的比較

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

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

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

5 結(jié) 語

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