基于Minhash的協(xié)同過濾技術(shù)在推薦系統(tǒng)中的應(yīng)用

劉艾俠，劉丹丹 (.寶雞職業(yè)技術(shù)學(xué)院，寶雞 7203； 2. 中國科學(xué)院大學(xué)，北京 00039； 3.中國科學(xué)院 國家授時(shí)中心，西安 70600)

基于Minhash的協(xié)同過濾技術(shù)在推薦系統(tǒng)中的應(yīng)用

劉艾俠1，劉丹丹2，3
(1.寶雞職業(yè)技術(shù)學(xué)院，寶雞 721013； 2. 中國科學(xué)院大學(xué)，北京 100039； 3.中國科學(xué)院 國家授時(shí)中心，西安 710600)

傳統(tǒng)協(xié)同過濾的推薦機(jī)制應(yīng)用在大規(guī)模數(shù)據(jù)上時(shí)，如果在要保證推薦質(zhì)量會(huì)導(dǎo)致占用運(yùn)行時(shí)間和存儲(chǔ)空間的增加。研究分析了Minhash在大規(guī)模數(shù)據(jù)上的降維原理，論證了將minhash應(yīng)用到協(xié)同過濾，設(shè)計(jì)并實(shí)現(xiàn)基于Minhash算法的協(xié)同過濾模型。實(shí)驗(yàn)結(jié)果表明Minhash能在保證推薦質(zhì)量的前提下很大程度上縮短計(jì)算時(shí)間和存儲(chǔ)空間，能有效地?cái)U(kuò)展到大規(guī)模數(shù)據(jù)集。

協(xié)同過濾； 大規(guī)模數(shù)據(jù)集； Minhash

0 引言

協(xié)同過濾技術(shù)基于尋找相似鄰居來預(yù)測(cè)目標(biāo)用戶將來行為，在數(shù)據(jù)集不大，并且類別數(shù)量或者稱為數(shù)據(jù)維度不高的情況下，通過實(shí)驗(yàn)?zāi)茏C明算法的推薦結(jié)果的精準(zhǔn)度比較高，質(zhì)量比較好。但是該算法的運(yùn)算依賴于內(nèi)存，并具有平方數(shù)量級(jí)以上的復(fù)雜度，當(dāng)類別數(shù)量很高的時(shí)候，即使很小數(shù)量級(jí)的數(shù)據(jù)，算法的運(yùn)算時(shí)間都會(huì)遠(yuǎn)遠(yuǎn)超出能接受的范圍，因此很難擴(kuò)展到大規(guī)模的數(shù)據(jù)集上。本文針對(duì)協(xié)同過濾技術(shù)的這點(diǎn)局限性，利用基于概率的聚類方法——minhash來完成高維度數(shù)據(jù)集的降維工作，從而降低在給目標(biāo)用戶尋找最近鄰居花費(fèi)的時(shí)間，提高運(yùn)算效率。

1 基于Minhash的協(xié)同過濾

Minhash是一種概率的聚類方法，根據(jù)兩個(gè)用戶項(xiàng)目行為集合的交集，有一定概率將兩個(gè)行為分到同一個(gè)組。其基本思想是隨即排列一個(gè)用戶Ui的行為集合Si然后計(jì)算hash值并用該值作為Ui的行為集合Cui，前面已經(jīng)證明，兩個(gè)用戶Ui，Uj有相同的Cui的概率和它們之間的相似度一致。因此，Minhash被認(rèn)為是一種概率上的聚類方法，將所有的hash結(jié)果作為一個(gè)簇(如Cui可以看成一個(gè)簇)，兩個(gè)用戶在同一個(gè)簇內(nèi)的概率和他們之間的相似度相等。為了提高精準(zhǔn)度我們可以用p個(gè)hash-key來hash用戶的Si，這樣p個(gè)hash的結(jié)果連接起來作為一個(gè)Cui，這樣兩個(gè)用戶有同一個(gè)Cui的概率，如式(1)。

Pi,j=S(ui,uj)p

(1)

這樣在同一個(gè)簇C的兩個(gè)用戶相似度會(huì)更大。這樣在一個(gè)組內(nèi)尋找相似鄰居，得到的結(jié)果有很高的精準(zhǔn)度，很明顯，設(shè)置Minhash 的獨(dú)立運(yùn)算次數(shù)p能夠提高精準(zhǔn)率，但是同時(shí)，也會(huì)在一定程度上提高相似用戶的丟失率，聚類的召回率就會(huì)降低，為了提高召回率，可以為每個(gè)用戶hash得到q個(gè)簇，每個(gè)簇用p個(gè)hash-key進(jìn)行hash，通過q次重復(fù)hash過程，每個(gè)用戶所屬于的簇增加到q個(gè)。

基于Minhash 的協(xié)同過濾技術(shù)的詳細(xì)推薦過程：

第一步，為方便Minhash運(yùn)算，需要給所有能表示用戶行為的文本或者其他形式對(duì)象分配唯一標(biāo)識(shí)。一般來說，用戶-項(xiàng)目的矩陣內(nèi)容是文本內(nèi)容，所能記錄下的用戶行為都是通過session和用戶輸入的query內(nèi)容，或者點(diǎn)擊的鏈接來表示。如果直接將這些文本導(dǎo)入內(nèi)存再進(jìn)行運(yùn)算會(huì)占據(jù)很大的內(nèi)存，并且在一般的計(jì)算機(jī)內(nèi)存配置達(dá)不到這個(gè)要求，因此可以給用戶和行為分別用十進(jìn)制的id表示，這樣用戶-評(píng)價(jià)的矩陣可以轉(zhuǎn)換成用戶id-項(xiàng)目id的矩陣。為了完成這個(gè)過程我們建立為用戶和項(xiàng)目分別建立一個(gè)目錄，分別表示為Du和Ds如果當(dāng)前用戶或者評(píng)價(jià)在目錄里面找不到，則將其分配一個(gè)最新的id并加入到這個(gè)目錄，如果有記錄則直接將對(duì)應(yīng)的id替換原有的文本。這一步的輸出包括3個(gè)結(jié)果，用戶和評(píng)價(jià)的目錄Du和Ds，另外還有用戶id-評(píng)價(jià)id的對(duì)應(yīng)表。

第二步，利用p*q個(gè)哈希函數(shù)進(jìn)行Minhash運(yùn)算，算法的輸入是一個(gè)表示用戶評(píng)價(jià)的一個(gè)集合，該集合是經(jīng)過Du和Ds映射后的一個(gè)用戶id和一個(gè)表示該用戶評(píng)價(jià)的id的集合I，首先選取第1到第p個(gè)hash函數(shù)運(yùn)算，選擇I中能得到的最小哈希值作為一個(gè)Minhash1，經(jīng)過p次運(yùn)算，分別得到Minhash2，…，Minhashp，這樣p個(gè)Minhash值作為一個(gè)簇號(hào)，然后再選取第p+1到第2p個(gè)hash函數(shù)進(jìn)行運(yùn)算，如此循環(huán)，經(jīng)過q次運(yùn)算，最后會(huì)得到這個(gè)用戶的q個(gè)簇號(hào)，每個(gè)簇號(hào)都由p個(gè)Minhash值連接起來組成的。最后生成了uid-cid的數(shù)據(jù)，表示用戶-簇的對(duì)應(yīng)關(guān)系，倒排uid-cid的結(jié)果，生成cid-uid的文件，這樣就能很方便的查找相似鄰居。

第三步，尋找相似鄰居。從第二步中的uid-cid矩陣中根據(jù)一個(gè)用戶id查到其擁有的簇號(hào)cid，再根據(jù)該cid從cid-uid倒排表中查找所有的相似用戶。聚集所有相似用戶并給這些用戶用其出現(xiàn)的次數(shù)進(jìn)行加權(quán)，選取排行靠前的若干個(gè)用戶作為相似用戶。

第四步，預(yù)測(cè)。這一步驟和協(xié)同過濾基本一致，查找所有相似用戶的評(píng)價(jià)的項(xiàng)目歷史，聚集所有的項(xiàng)目，按項(xiàng)目的的出現(xiàn)的次數(shù)排序，選取前k個(gè)作為預(yù)測(cè)的值，這些預(yù)測(cè)結(jié)果就是給用戶的推薦。

2 Minhash算法設(shè)計(jì)

基于Minhash的協(xié)同過濾工作流程，如圖1所示。

包括用戶數(shù)據(jù)的映射，即：用戶映射到用戶id，項(xiàng)目映射到項(xiàng)目id；中間Minhash模塊的作用就是根據(jù)用戶id-項(xiàng)目id的輸入，運(yùn)算輸出用戶id-簇id；最后最近鄰居尋找，就是生成用戶id-相似用戶id。詳細(xì)過程如下：

(1)在映射階段，需要分別給用戶和項(xiàng)目建立一個(gè)目錄，由于數(shù)據(jù)集中的用戶和項(xiàng)目個(gè)體會(huì)很多，如果在一臺(tái)機(jī)器上維護(hù)這樣兩個(gè)列表，會(huì)占用比較大的內(nèi)存，盡管占用CPU的資源不會(huì)太多，但是占用的內(nèi)存限制了后來的協(xié)同過濾的尋找相似用戶能利用的內(nèi)存空間，為了將內(nèi)存資源盡量多的留給協(xié)同過濾，可以設(shè)計(jì)一個(gè)服務(wù)，開啟一個(gè)遠(yuǎn)程服務(wù)，這個(gè)服務(wù)上維護(hù)一個(gè)用戶和一個(gè)項(xiàng)目的哈希表，每個(gè)表的內(nèi)容是value-key的值，然后利用網(wǎng)絡(luò)協(xié)議進(jìn)行通信，客戶端發(fā)送一個(gè)請(qǐng)求，內(nèi)容是當(dāng)前的用戶或者項(xiàng)目，服務(wù)端接受請(qǐng)求后從目錄表中查找，返回對(duì)應(yīng)id，如果當(dāng)前目錄中沒有包含這個(gè)記錄，則為該記錄新建一個(gè)id并返回，同時(shí)將該記錄和新的id加入到列表中。

圖1 基于Minhash的協(xié)同過濾工作流程

(2)原始數(shù)據(jù)里面有不少對(duì)預(yù)測(cè)的結(jié)果沒有意義數(shù)據(jù)，清洗掉無用的數(shù)據(jù)并從原始數(shù)據(jù)中抽取User-Item的列表，得到用戶和項(xiàng)目對(duì)應(yīng)的ID，將原始數(shù)據(jù)轉(zhuǎn)變成Uid-Rid的列表，同時(shí)根據(jù)Uid將該用戶的所有Rid組成集合。

(3)利用Minhash 模塊，輸入U(xiǎn)id-List，輸出Uid-List，Cid是每次Minhash 的結(jié)果，將hash迭代q次，則每個(gè)Uid的List的大小都為q。將相同Cid 的聚集起來，每個(gè)Cid 的所有Uid都是相似用戶，形成用戶-相似用戶列表。

以上就是基于Minhash 的協(xié)同過濾算法整體流程，圖1中Minhash 模塊的實(shí)際上就是進(jìn)行循環(huán)和迭代的哈希函數(shù)，經(jīng)過Minhash 模塊的處理，用戶在n個(gè)項(xiàng)目上最多可能有n維的向量空間被降維到q維的向量空間。

Minhash算法數(shù)據(jù)處理流程，如表1所示。表1中算法的輸入，輸出和詳細(xì)處理過程如下：

表1 Minhash算法

(1)輸入是Uid-List，表示的是用戶-項(xiàng)目的集合，這個(gè)輸入是在經(jīng)過映射處理后的ID標(biāo)識(shí)的集合。

(2)初始化Minhash的參數(shù)，p，q，隨機(jī)種子m。前述說明p是Minhash的精度系數(shù)，p越大，同一個(gè)簇的用戶相似度越高，但是這樣一個(gè)組的用戶數(shù)量會(huì)越少，必然導(dǎo)致預(yù)測(cè)的結(jié)果不多，致使召回率不高，q是提高召回率的一個(gè)系數(shù)，q指的是Minhash運(yùn)算迭代的次數(shù)，當(dāng)q越大，一個(gè)用戶屬于的簇的數(shù)量越多，這樣會(huì)保證精準(zhǔn)度的前提下提高召回率。m是一個(gè)隨機(jī)種子，在hash運(yùn)算中用來計(jì)算一個(gè)整數(shù)的hash值。

(3)設(shè)置3個(gè)中間變量，用以控制hash計(jì)算的次數(shù)和簇號(hào)生成。首先hash會(huì)迭代計(jì)算q次，每次計(jì)算會(huì)生成一個(gè)簇號(hào)，當(dāng)前簇號(hào)以該次迭代的次序號(hào)開始，如0，1，等等。然后會(huì)隨機(jī)生成兩個(gè)隨機(jī)數(shù)a和b，經(jīng)過p次循環(huán)，每次循環(huán)會(huì)將List中的每一個(gè)Rid經(jīng)過下列運(yùn)算，得到一個(gè)暫時(shí)的值，如公式(2)所示，如式(2)。

f(x)=a+Iidib(modm)

(2)

取所有的temp 中最小的一個(gè)hash 值作為當(dāng)前hash 值，p次循環(huán)后會(huì)得到一個(gè)標(biāo)示，如式(3)。

(3)

然后將以迭代的次序號(hào)起始的字符與該標(biāo)示合并得到這一次迭代的簇號(hào)，如式(4)。

Cidi=i_tempi=i_hash1_hashw_…_hashq

(4)

(4)輸出Uid-List，List的元素?cái)?shù)量為q。

3 Minhash模型設(shè)計(jì)

在實(shí)現(xiàn)基于Minhash 的協(xié)同過濾模型過程中，數(shù)據(jù)可以以文本的形式存儲(chǔ)在磁盤上，在算法中利用I/O操作讀取到內(nèi)存，也有可能存儲(chǔ)在數(shù)據(jù)庫中，利用存儲(chǔ)過程，sql查詢等操作，完成算法的運(yùn)算。因此圖2中的原數(shù)據(jù)文件和中間等所有的文件均可能以別的存儲(chǔ)形式存在。圖2中實(shí)線箭頭表示的是數(shù)據(jù)流，虛線箭頭表示的是工作流，Minhash組件包含三個(gè)主要的模塊：數(shù)據(jù)抽取，Minhash模塊和查詢語句預(yù)測(cè)。每個(gè)模塊的具體功能會(huì)在下面進(jìn)行詳細(xì)敘述。

在具體操作中，可以利用時(shí)間的位移保證相似用戶一定有行為的記錄，可以描述為利用N+M天的數(shù)據(jù)，根據(jù)當(dāng)前第N天到第N+M天的用戶數(shù)據(jù)預(yù)測(cè)用戶未來N天內(nèi)的行為，可以選取的訓(xùn)練數(shù)據(jù)是第1天到第M天。

(1)數(shù)據(jù)抽取

圖2 基于Minhash的協(xié)同過濾模型圖

主要從原始數(shù)據(jù)中抽取M+N天內(nèi)的三個(gè)信息，包括用戶，查詢語句和查詢時(shí)間，在這一步中會(huì)從遠(yuǎn)程服務(wù)器中查找用戶和查詢語句的hash表，同時(shí)將這三列的信息轉(zhuǎn)換成Uid_Rid的數(shù)據(jù)格式。

(2)Minhash

首先聚合一個(gè)用戶在前M天所有的查詢語句的Qid，形成Uid_List，然后給Uid運(yùn)行一遍Minhash算法，得到Uid_List的列表，同時(shí)倒排該列表形成Cid_List。

(3)查詢語句預(yù)測(cè)

根據(jù)每個(gè)用戶，在Uid_List找到所有的Cid，然后在Cid_List中找到所有的相似Uid，最后在Uid_Qid_time中找到所有的Qid，這些Qid按次數(shù)排序，取前面的K的Qid，這k個(gè)Qid就是預(yù)測(cè)的結(jié)果。

4 算法測(cè)試

實(shí)驗(yàn)數(shù)據(jù)集來源于實(shí)際采集的數(shù)據(jù)，數(shù)據(jù)內(nèi)容是用戶在使用搜索引擎的日志。時(shí)間跨度是30天+7天，訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)按用戶的比例是4∶1，數(shù)據(jù)集規(guī)模和內(nèi)容，如表2所示。

表2 測(cè)試和訓(xùn)練數(shù)據(jù)詳細(xì)

經(jīng)過選取不同的p，q值作為Minhash算法的參數(shù)進(jìn)行實(shí)驗(yàn)，對(duì)比發(fā)現(xiàn)分別選取p=4，q=6的時(shí)候，基于Minhash的協(xié)同過濾推薦的結(jié)果精準(zhǔn)度和召回率比較好，因此在本實(shí)驗(yàn)數(shù)據(jù)集的基礎(chǔ)上選取p=4，q=6作為對(duì)比實(shí)驗(yàn)中的Minhash的參數(shù)。

分別在未經(jīng)過數(shù)據(jù)預(yù)處理的原始數(shù)據(jù)集，經(jīng)過預(yù)處理的數(shù)據(jù)集上完成傳統(tǒng)協(xié)同過濾和基于Minhash 的協(xié)同過濾的對(duì)比實(shí)驗(yàn)，分別得到PR曲線，如圖3和4所示。

另外記錄下傳統(tǒng)協(xié)同過濾和基于Minhash的協(xié)同過濾所用的時(shí)間和存儲(chǔ)空間，對(duì)比，如表3所示。

圖3 未經(jīng)數(shù)據(jù)預(yù)處理的對(duì)比實(shí)驗(yàn)

圖4 經(jīng)過數(shù)據(jù)預(yù)處理的對(duì)比實(shí)驗(yàn)

表3 傳統(tǒng)協(xié)同過濾和Minhash性能對(duì)比

從實(shí)驗(yàn)結(jié)果可以看出，盡管基于Minhash的協(xié)同過濾算法在推薦質(zhì)量上比傳統(tǒng)的協(xié)同過濾要稍低一點(diǎn)，但是在性能上卻遠(yuǎn)遠(yuǎn)優(yōu)秀于傳統(tǒng)的協(xié)同過濾算法，從表3可以看出，Minhash占用的內(nèi)存僅僅為不到傳統(tǒng)協(xié)同過濾的1/6，花費(fèi)的時(shí)間不到傳統(tǒng)協(xié)同過濾的1/200。

5 總結(jié)

推薦技術(shù)的研究是當(dāng)前推薦領(lǐng)域的研究熱點(diǎn)，具有巨大的商業(yè)價(jià)值。傳統(tǒng)的協(xié)同過濾雖然在推薦系統(tǒng)中得到廣泛的利用和驗(yàn)證，但是其本身面臨很多的問題，例如數(shù)據(jù)稀疏的局限性，難以向大數(shù)據(jù)集擴(kuò)展。本文通過利用一種概率的聚類方法——minhash方法完成給高維度的用戶數(shù)據(jù)進(jìn)行降維。另外針對(duì)常見的原始數(shù)據(jù)集中存在噪音數(shù)據(jù)設(shè)計(jì)并實(shí)現(xiàn)噪音數(shù)據(jù)過濾程序，對(duì)于常見英文文本的同義性問題利用porter stemming給英文單詞的映射統(tǒng)一規(guī)范的文本。通過實(shí)驗(yàn)，本文論證了在保證推薦質(zhì)量的前提下，minhash對(duì)比傳統(tǒng)的協(xié)同過濾有著更好的性能，minhash可成為協(xié)同過濾向大規(guī)模數(shù)據(jù)擴(kuò)展的一種手段。

[1] Abbattista F, Degemmis, et al. Improving the Usability of an E-commerce Web Site through Personalization [C]. Proceedings of the Workshop on Recommendation and Personalization in Ecommerce,2002.

[2] Songhua Xu, Hao Jiang, Francis C.M. Lau. Personalized Online Document, Image and Video Recommendation via Commodity Eye-tracking [J]. Communication of the ACM, 2008,40(3):83-90.

[3] Balabanovic M, Shoham Y. Fab. Content-based, Collaborative Recommendation [J]. Communication of the ACM, 1997, 40 (3): 66-72.

[4] Konstan A, Miller B, et al. GroupLens: Applying Collaborative Filtering to USENET News [J]. Communication of the ACM, 1997, 40(3): 77-87.

[5] Lewis D D, Yang Y, et al. RCV1: A New Benchmark Collection for Text Categorization Research [J]. Journal Machine Learning Research, 2004, 5 (12): 361-397.

[6] Yu K, Xu X-W, Ester M, et al. Feature Weighting and Instance Selection for Collaborative Filtering: An Information-Theoretic Approach [J]. Knowledge and Information Systems, 2003，25(4)：521-525.

[7] Sarwar B, Karypis G, Konstan J, Reidl J. Item-Based Collaborative Filtering Recommendation Algorithms [C]. Proceedings of the Tenth International World Wide Web Conference (World Wide Web), 2001：314-317.

[8] Sarwar B, Karypis G, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms [C]. Proceedings of the 10th International World Wide Web Conference. 2001. 285-295.

[9] Chickering D, Hecherman D. Efficient approximations for the marginal likelihood of Bayesian networks with hidden variables [J]. Machine Learning, 1997,29(2/3):181-212.

[10] Breese J, Hecherman D, Kadie C. Empirical analysis of predictive algorithms for collaborative filtering [C]. Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI’98). 1998. 43-52.

[11] Breese J, Heckerman D, Kadie C. Empirical Analysis of Predictive Algorithms for Collaborative Filtering [C]. Proc. of the 14th Conf. on Uncertainty in Artifical Intelligence, July 1998：1421-1426.

[12] Karen Sparck Jones. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation [J]. 2004, 60(5)：493-502.

CollaborativeFilteringTechnologyBasedonMinhashandItsApplicationinRecommendSystem

Liu Aixia1, Liu Dandan2,3
(1.Baoji Vocational Technology College, Baoji 721013; 2.University of Chinese Academy of Science, Beijing 10039; 3.National Time ServiceCenter, Chinese Academy of Science, Xi’an 710600)

The traditional collaborative filtering recommendation mechanism, in order to ensure the quality of recommendation for a set of lavge scale data, will lead to increase run time and memory space. This paper analyzes Minhash dimensionality reduction principles for large-scale data, argues to was Minhash for collaborative filtering, and then designs and implements collaborative filtering algorithm based on Minhash model. The results show that Minhash can largely reduce computing time and storage space under the premise of quality assurance, and can effectively extend to large data sets.

Collaborative filtering; Large data sets; Minhash

TP311

A

2017.01.28)

劉艾俠(1982-)，女，周至人，漢族，碩士，講師，研究方向：計(jì)算機(jī)技術(shù)。

劉丹丹(1983-)，女，焦作人，漢族，碩士，助理研究員，研究方向：計(jì)算機(jī)軟件設(shè)計(jì)。

1007-757X(2017)10-0067-04