一種基于動機感知的用戶識別實時算法①

張夢菲 邱 強 肖茁建 姚 曉 方金云

(*中國科學院計算技術(shù)研究所 北京 100190) (**中國科學院大學 北京 100190)

0 引 言

Web數(shù)據(jù)挖掘一直是學術(shù)界和工業(yè)界研究的熱點之一。隨著大數(shù)據(jù)技術(shù)的發(fā)展,面向電子商務(wù)的Web數(shù)據(jù)挖掘在智能推薦、廣告投放等領(lǐng)域發(fā)揮著越來越重要的作用。截至2018年12月,我國網(wǎng)絡(luò)購物用戶規(guī)模達到6.10億,電子商務(wù)已成為大數(shù)據(jù)的重要來源[1]。用戶識別技術(shù)作為Web日志挖掘的基礎(chǔ), 是從大量無序的數(shù)據(jù)中分析出匿名用戶的獨立行為軌跡和特征,并最終識別出唯一的用戶個體。其結(jié)果的準確性直接影響了后續(xù)數(shù)據(jù)挖掘和個性化服務(wù)的效果。因此,研究電商平臺的用戶識別具有重要的應(yīng)用價值。

用戶識別技術(shù)的研究主要集中在Web數(shù)據(jù)挖掘[2]、電子設(shè)備[3-5]、文本信息中匿名作者[6，7]以及共享賬戶[8]等領(lǐng)域。在Web挖掘領(lǐng)域中的用戶識別方法主要有2種：(1)基于啟發(fā)式規(guī)則的方法[9，10]；(2)根據(jù)用戶行為模式的方法。基于啟發(fā)式規(guī)則的識別算法利用IP、用戶代理(userAgent)、cookie技術(shù)識別用戶，userAgent是用戶的操作系統(tǒng)及其版本信息和瀏覽器及其版本信息。Yen等人[10]在啟發(fā)式規(guī)則中證明了cookie技術(shù)比IP+userAgent方法具有更高的識別用戶準確率，然而由于用戶隱私問題，很難獲得cookie數(shù)據(jù)的完整數(shù)據(jù)項。肖慧等人[11]提出了重寫URL的IASR(IP，agent, session and referrer)算法用戶跟蹤方法，在啟發(fā)式規(guī)則中引入用戶會話(session)來識別用戶，該方法在服務(wù)器端支持session的情況下提高了準確率，但是實際情況中難以保證session的完整性和實效性。基于行為模式的用戶識別算法根據(jù)用戶興趣和習慣的獨特性[12]和穩(wěn)定性[13]，并利用數(shù)據(jù)挖掘和機器學習算法對點擊流數(shù)據(jù)分類和預(yù)測來識別用戶。Yang[14]提出了一種用戶畫像識別用戶的算法，通過對時間T之前已知用戶會話行為建立用戶畫像來預(yù)測未知用戶，該方法對小規(guī)模數(shù)據(jù)取得了不錯的效果，但對于規(guī)模較大的網(wǎng)站該算法不具備可行性。Naini等人[12]將數(shù)據(jù)劃分成匿名和已知用戶數(shù)據(jù)，并用直方圖展示用戶2個星期內(nèi)訪問不同網(wǎng)站的習慣和行為信息，把問題轉(zhuǎn)化為2個圖的最小帶權(quán)匹配問題，準確率達到90.0%，但該算法主要針對的是用戶在多個網(wǎng)站的訪問行為，實際用戶在一個電商網(wǎng)站的訪問行為要更復(fù)雜。

在電商平臺中，用戶識別面臨著以下的問題：(1)“多用戶問題”和“單用戶問題”，同一個用戶在不同的時間內(nèi)通過在地址欄輸入URL或從收藏夾中進入網(wǎng)頁會被識別為多個用戶，即“多用戶問題”；多個用戶共享一個IP甚至使用同種設(shè)備和瀏覽器可能會被識別為一個用戶，即“單用戶問題”。(2)效率問題，關(guān)鍵績效指標(key performance indicater, KPI)指數(shù)在百萬級別以上的情況下，對用戶識別算法的效率提出了更高的要求。Web日志處理也越來越趨于實時化[15，16]。

針對以上問題，本文以義烏購小商品官網(wǎng)電商平臺義烏購(www.yiwugo.com)的實際運營數(shù)據(jù)為研究對象，提出了基于Spark[17]的啟發(fā)式和用戶動機感知相結(jié)合的通用用戶識別算法(Spark based user identification by Heuristic rules and user motivation perception，SHUMP)。SHUMP算法采用初次匹配、精確識別的二階段模式來實時識別用戶。在初次匹配階段,利用用戶IP、用戶代理(userAgent)、cookie、用戶會話(session)、引用(referer)等信息匹配用戶。在精確識別階段,提取每條點擊流日志的URL特征,通過感知用戶動機來精確識別用戶身份。對于“多用戶問題”和“單用戶問題”，該算法在用戶的session或者cookie缺失、用戶設(shè)備相同、引用信息無法匹配的情況下，根據(jù)用戶的行為動機來區(qū)分用戶，將動機相似的識別為同一個用戶，從而解決“多用戶問題”；將動機不同的識別為多個用戶，從而解決“單用戶問題”；并對上述算法在Spark計算框架下進行了優(yōu)化。

本文第1節(jié)介紹用戶識別中的概念和問題定義。 第2、3節(jié)分別介紹了SHUMP算法中2個階段的具體技術(shù)細節(jié)。第4節(jié)介紹為解決實時化用戶識別算法效率設(shè)計的分布式計算方法。第5節(jié)對本文算法進行實驗驗證和分析。第6節(jié)總結(jié)并展望本文的用戶識別算法。

1問題定義

定義1日志的用戶訪問記錄集合I=，其中m為記錄的個數(shù)，pi(1≤i≤m)是每個用戶的一次頁面訪問記錄。

定義2網(wǎng)站每個用戶的一次頁面訪問記錄表示為：pi=,pi的各個數(shù)據(jù)項記錄了用戶單次訪問的行為信息,包括時間(time)、地點(IP和userAgent)、用戶(userId)、來源(referer)、內(nèi)容(URL)、會話ID(sessionId)、cookie、狀態(tài)(status)等信息。

定義3電商平臺中用戶類型集合如圖1所示，其中U1是已識別用戶，對應(yīng)定義2中userId數(shù)據(jù)項不為空的記錄；U2是可追蹤用戶，對應(yīng)定義2中cookie數(shù)據(jù)項不為空的記錄，系統(tǒng)可以通過cookie數(shù)據(jù)項追蹤用戶；U3是未識別用戶，對應(yīng)定義2中userId和cookie數(shù)據(jù)項都為空的記錄，網(wǎng)站只能獲取這類用戶的IP和userAgent信息。

定義4定義3中的U2、U3是本文的研究對象。用戶識別是將定義2中userId數(shù)據(jù)項為空的記錄與其他記錄進行分析，判定哪些是同一個用戶的行為記錄，并為這些用戶生成唯一的ID編碼，即userId。

圖1 用戶類型集合

2 基于啟發(fā)式規(guī)則的初次匹配算法

本文對電商平臺的所有日志數(shù)據(jù)分別根據(jù)IP+userAgent、cookie和userId劃分為三級桶，其中在二、三級桶數(shù)據(jù)劃分時，第1個階段按照啟發(fā)式規(guī)則進行初步匹配，第2個階段用URL動機感知的算法來精確識別用戶。

基于啟發(fā)式規(guī)則的初次匹配算法是以userId、cookie、session和網(wǎng)站拓撲結(jié)構(gòu)信息為用戶初次識別的4個維度值，并根據(jù)相關(guān)規(guī)則進行匹配。具體步驟見算法1。

算法1啟發(fā)式規(guī)則的初次匹配算法輸入:2個用戶的行為特征feature1和feature2輸出:feature1和feature2是否匹配 1.if(f==0){key1= l1.cookie,key2 = l2.cookie} else {key1= l1.userId,key2= l2.userId} 2.if(key1!= null&key1== key2){return true} 3. if(l1.session == l2.session){return true} 4.if(l1.referer == l2.url){return true} 5. if((l1.referer == l2.referer)&(l1.url == l2.url)){returntrue}

算法輸入為定義1中的2條日志l1和l2標志位f,f代表要匹配的是cookie還是userId。如果非空的userId、cookie或者session相同,算法直接判定為同一個用戶;否則,按照網(wǎng)站的拓撲結(jié)構(gòu),如果當前URL可以由上一條記錄到達,則匹配。

3 基于動機感知的精確用戶識別算法

3.1 動機感知模型

電商平臺的用戶動機主要反映在URL中,URL中包括了用戶瀏覽、搜索、點贊、購物車等行為信息,通過感知用戶的動機,將用戶訪問行為反饋到用戶識別。本文通過對每條URL提取出類型(type)、網(wǎng)站版塊(block)、訪問的商鋪ID(shopId)、訪問的商品ID(productId)、搜索關(guān)鍵詞(word)5個特征來構(gòu)建用戶的訪問動機模型。具體步驟見算法2。

算法2動機獲取算法輸入:URL輸出:該URL所反映的用戶動機 1.對每條URL提取出特征type 2.如果type = 4, 提取block 3.如果type = 3,解析搜索詞word 4.如果 type = 7,提取shopId和productId

算法2構(gòu)建了每條點擊流日志5個維度的用戶動機模型，其中特征type代表用戶的不同行為類型,如表1所示，以電商網(wǎng)站為例,當type=4時,表示用戶在瀏覽網(wǎng)站的版塊(block),如:論壇、采購、投訴等版塊。shopId、productId、word 3個特征包含了用戶感興趣的商鋪、商品和搜索求購信息。表2展示了3種不同類型訪問記錄的動機解析結(jié)果，其中空白部分表示對應(yīng)的信息不存在，shopId和productId提供的用戶動機信息還需根據(jù)3.2節(jié)內(nèi)容來計算。

表1 典型的電商網(wǎng)站URL類型解析

表2 義烏購URL動機解析示例

3.2 相似度計算

用戶訪問動機是指在一定時間閾值T范圍內(nèi)的用戶訪問軌跡，本文取閾值T=30 min。用戶動機中如果不包含shopId、productId、word 3個特征，則匹配URL的type和block;否則根據(jù)shopId、productId、word 3個特征對應(yīng)的商鋪主營范圍、商品標題、搜索詞來計算動機的相似度矩陣。

相似度矩陣是通過計算2個用戶行為動機模型的相異數(shù)來確定用戶動機的距離。文獻[18]提出了利用相異數(shù)計算2個詞的距離，相異數(shù)越小，說明距離越小，2個詞越相似。算法提取了商品標題、商鋪主營范圍、搜索詞等短文本的核心詞集合，并把核心詞映射到商品分類樹的節(jié)點上，計算樹的各個節(jié)點之間的距離,得到基礎(chǔ)相異數(shù)；并利用式(1)，從基礎(chǔ)分析、文本分析、維度分析和擴展分析4個角度修正相異數(shù)，其中tagi是核心詞、id是核心詞在分類詞庫中的詞碼，disij是基礎(chǔ)分析得到的相異數(shù)，f1、f2、f3、f4分別是從詞頻分析、位置分析、附屬維度和品牌維度得到的計算因子，表示該核心詞在短文本中的重要程度,具體描述見算法3。

(1)

算法3相似度計算算法輸入:2個用戶行為的特征feature1和feature2輸出: 2個行為是否匹配 1. 初始化閾值threshold 2. if (feature1和feature2的word、shopId、productId的任何一個特征同時存在){轉(zhuǎn)至第4步} else {轉(zhuǎn)至第3步} 3. if(feature1.match(feature2)){return true} else{return false} 4. T1=提取feature1的核心詞集合 T2=提取feature2的核心詞集合 5. 計算T1和T2的相異數(shù)value; 6. if(value> threshold){return false} else{return true}

表3～表5是商鋪主營、商品標題、搜索詞3種用戶行為動機模型的提取核心詞示例,其中商品標題的核心詞用相異數(shù)修飾其在標題中的重要程度。表6是用戶行為動機相似度矩陣計算結(jié)果，P1、P2、S1、S2、W1、W2代表表3～表5提取的核心詞，S1指

表3 商鋪核心詞提取示例

表4 商品相異數(shù)示例

表5 搜索詞核心詞提取示例

表6 用戶行為相似度矩陣計算結(jié)果

一條URL代表的用戶行為是訪問了一個商鋪，該商鋪的主營是S1。表中的值代表用戶行為相異數(shù)，S1和P1的用戶行為相異數(shù)是0。當type和block相等或用戶行為相異數(shù)小于閾值threshold時,則判定兩條URL為同一個用戶。

4 二階段識別算法的實時化

二階段識別算法的復(fù)雜度為O(n2)，如何滿足在線訪問用戶的實時識別直接關(guān)系到電商平臺推薦系統(tǒng)的用戶體驗。本文在Spark分布式計算框架下對算法進行了優(yōu)化,算法流程如圖2所示。

步驟1數(shù)據(jù)清洗,Spark Streaming從Kafka中并行讀取實時數(shù)據(jù)流,并調(diào)用filter 算子,將日志爬蟲和異常信息過濾,得到真實用戶訪問的數(shù)據(jù)流normalDStream;

步驟2一級桶劃分,將日志數(shù)據(jù)以IP+userAgent作為key值,對相同的key進行數(shù)據(jù)劃分,產(chǎn)生一級桶數(shù)據(jù)b11，b12，…，b1n，數(shù)據(jù)集合為IADStream;

步驟3數(shù)據(jù)匹配，調(diào)用groupBykey算子和mapValues算子，在每個桶b1i中進行數(shù)據(jù)匹配,數(shù)據(jù)匹配包括初次匹配和URL動機相似度計算;

步驟4二、三級桶劃分,對一級桶b1i進行桶劃分的原則是:假設(shè)pi∈b1i并且pj∈b1j，則在b1i中總是存在記錄pk(i≤k≤j),pi和pk相互匹配并且pk和pj相互匹配。通過判斷第2節(jié)中算法1 (l1,l2,f)的f標志位，并按照cookie和userId劃分成二、三級桶數(shù)據(jù)b2i，和b3i;

步驟5userId生成，為所有匿名用戶生成userId，登錄用戶的userId保持不變。

SHUMP算法利用Spark將日志數(shù)據(jù)劃分成大小均衡的DStream數(shù)據(jù)流，分配到指定多個節(jié)點的內(nèi)存中，并利用轉(zhuǎn)換算子對數(shù)據(jù)進行三級桶劃分和用戶識別，從而找到用戶各自所屬的類別。

圖2 SHUMP算法并行計算流程

5 實驗結(jié)果與分析

5.1 實驗數(shù)據(jù)集與環(huán)境

本文采用義烏購(www.yiwugo.com)網(wǎng)站的nginx日志數(shù)據(jù),該網(wǎng)站依托全球最大的小商品批發(fā)市場——義烏小商品城。網(wǎng)站每天產(chǎn)生百萬級別的真實點擊流日志記錄，其數(shù)據(jù)格式如表8所示，每一條日志對應(yīng)定義2中的pi。

本文從用戶識別的準確性和效率2個方面進行了實驗驗證。在由7臺服務(wù)器搭建的集群環(huán)境中，每臺節(jié)點都配置jdk1.8、Hadoop-2.7.0、Zookeeper-3.4.8和Spark-2.2.0相關(guān)環(huán)境，采用主從方式進行實驗。表7是實驗所用服務(wù)器的硬件配置信息。

表7 服務(wù)器硬件配置信息

5.2 準確性驗證

5.2.1 準確率驗證

在準確率實驗中,本文將日志按照天進行分割,對2017年10月1日至10月31日31天的日志進行預(yù)處理,抽取出登錄用戶的日志,并將日志中的userId數(shù)據(jù)項清除。式(2)是準確率計算公式,其中,originalNum為清除userId數(shù)據(jù)項之前的原始用戶數(shù)量,SHUMPNum為經(jīng)過SHUMP算法計算得到新的用戶數(shù)量。算法準確率最高達99.97%,月平均值為97.89%(圖3)。

accuracy=

(2)

表8 義烏購電商平臺nginx日志格式

圖3 1個月內(nèi)SHUMP算法的準確率變化圖

5.2.2 對比驗證

文獻[12]構(gòu)建用戶之間訪問路線的二部圖結(jié)構(gòu)，然后計算二部圖的最大匹配，但是實驗數(shù)據(jù)將用戶訪問的URL加密，每個網(wǎng)站作為最小單位，計算匿名用戶訪問不同網(wǎng)站的統(tǒng)計信息，并且數(shù)據(jù)量小，極大簡化了用戶識別的問題，然而并不適用于內(nèi)容繁多、頁面鏈接復(fù)雜的的Web場景。文獻[14]將用戶識別問題轉(zhuǎn)化監(jiān)督問題，基于用戶行為預(yù)先建立用戶畫像，然后按照session進行匹配得到分數(shù)，并分類到已知的用戶中，在小數(shù)據(jù)集比如2個用戶的識別上準確率最高達到99.30%，低于本文算法的準確率，然而該算法隨著數(shù)據(jù)量增大，準確率下降，僅在100個用戶的數(shù)據(jù)集上準確率就下降至87.36%。以上方法不僅存在大數(shù)據(jù)量的可擴展性問題，效率也沒有得到驗證。與監(jiān)督學習不同的是，本文的方法并非將測試數(shù)據(jù)分類到正確的類別上，而是將一組用戶同時找到它們各自所屬的：“類別”，它們可能為同一個用戶，也可能屬于獨特的一個用戶，本文方法能找出并賦予它們獨特的ID。在對比實驗中，本節(jié)與復(fù)現(xiàn)的文獻[11]進行實驗對比，驗證SHUMP算法的時間效率和用戶數(shù)量，同時將與部署的百度統(tǒng)計結(jié)果進行對比，進一步驗證算法的可靠性。

表9展示了原始記錄數(shù)為500萬條的日志經(jīng)過IASR算法和SHUMP算法之后的數(shù)據(jù)，SHUMP算法處理速度明顯高于IASR算法，識別的用戶數(shù)量多于IASR算法，由于IASR算法僅僅考慮傳統(tǒng)的啟發(fā)式匹配規(guī)則，對于IP地址和設(shè)備相同的用戶，如果用戶禁用cookie等信息，或者從網(wǎng)頁收藏夾直接進入網(wǎng)站造成引用信息無法獲取，該算法無法區(qū)分不同的用戶，無法解決“單用戶問題”和“多用戶問題”，而SHUMP算法則會根據(jù)用戶的動機進行相似度匹配計算，可以識別出更多的真實用戶，提高識別準確率。

表9 SHUMP與IASR算法效率和準確率對比

另外，本文在義烏購網(wǎng)站中部署百度統(tǒng)計對比識別出的網(wǎng)站用戶個數(shù)，實驗通過計算網(wǎng)站14天的用戶識別數(shù)量與百度統(tǒng)計相同時間段內(nèi)的用戶數(shù)量對比如圖4所示。可以看出指標的趨勢基本一致，但本文數(shù)據(jù)比百度統(tǒng)計略高，這是因為百度統(tǒng)計依賴于瀏覽器設(shè)置cookie、JavaScript、圖片等，如果瀏覽器禁用，則無法獲取訪問數(shù)據(jù)，本文直接分析實際的日志文件，不受瀏覽器的限制,數(shù)據(jù)更加完整。因此本文的用戶識別算法是可靠的。

圖4 百度統(tǒng)計與SHUMP算法識別出的用戶數(shù)量對比圖

5.3 效率驗證

實驗將一段時間的日志數(shù)據(jù)預(yù)處理之后得到正常數(shù)據(jù)，并分成20份，從50萬條日志增大到1 000萬條。實驗分別用單線程、多線程、Spark框架實現(xiàn)二階段用戶識別算法，并按式(3)計算3個算法的處理時間。其中，Ti代表各個數(shù)據(jù)量的算法處理時間，Ti由統(tǒng)計10次處理時間求平均并4舍5入求整得到。

(3)

圖5為3種二階段用戶識別算法效率隨著數(shù)據(jù)量大小的變化趨勢，其中，HUMP with single thread和HUMP with multi-thread為二階段用戶識別算法的單線程和多線程實現(xiàn)版本，統(tǒng)稱為單機算法(HUMP)，SHUMP是二階段用戶識別算法在Spark上的優(yōu)化?？梢钥闯觯嗑€程HUMP算法處理時間低于單線程HUMP算法，但二者皆在數(shù)據(jù)量達到900萬條之后處理時間陡增，而SHUMP算法處理時間遠遠低于HUMP算法，集中在0～1 s，表10詳細記錄了其執(zhí)行時間。在百萬級別的數(shù)據(jù)情況下SHUMP算法耗時始終保持毫秒級，可以滿足用戶實時識別的場景。

6 結(jié) 論

本文采用啟發(fā)式規(guī)則初次匹配和用戶動機精確識別的二階段識別用戶算法。對于cookie相同或者session相同或者符合網(wǎng)站拓撲結(jié)構(gòu)或者訪問動機相同的用戶,算法分配相同的ID。用戶動機分析有效解決了相同IP地址的多個用戶使用同種操作系統(tǒng)和瀏覽器訪問網(wǎng)站會被認為是單用戶的問題以及當一個用戶多次直接進入網(wǎng)頁被認為是多用戶的問題。實驗表明SHUMP算法具有較高的準確率和處理效率,比百度統(tǒng)計結(jié)果更可靠。SHUMP算法已經(jīng)應(yīng)用在義烏購電商平臺。

圖5 SHUMP算法與HUMP單線程和多線程算法隨著數(shù)據(jù)大小變化執(zhí)行時間變化圖

表10 SHUMP算法隨數(shù)據(jù)量大小變化處理時間分布

本文提出的SHUMP算法為用戶行為分析和商品推薦奠定了基礎(chǔ),算法對電商網(wǎng)站的用戶識別具有一定的通用性。但受電商業(yè)務(wù)影響,用戶動機模型不盡相同,用戶的個性化訪問習慣也增加了用戶識別的難度,這將是下一步研究的內(nèi)容。