陳 友

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

分布式移動(dòng)網(wǎng)絡(luò)用戶行為分析系統(tǒng)

陳 友

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

為使移動(dòng)互聯(lián)網(wǎng)企業(yè)能夠?qū)τ脩籼峁└玫膫€(gè)性化服務(wù)，文中提出了一個(gè)基于數(shù)據(jù)預(yù)處理、上下文、C4.5決策樹(shù)和分布式數(shù)據(jù)處理的分布式移動(dòng)網(wǎng)絡(luò)用戶行為分析系統(tǒng)。該系統(tǒng)主要通過(guò)分布式的開(kāi)源框架Zookeeper、Kafka、Storm進(jìn)行實(shí)現(xiàn)。通過(guò)對(duì)系統(tǒng)的實(shí)現(xiàn)表明，該系統(tǒng)能夠較為精確地分析出移動(dòng)網(wǎng)絡(luò)用戶的興趣分類，即使面對(duì)海量的移動(dòng)用戶行為數(shù)據(jù)也并不會(huì)影響系統(tǒng)性能。

數(shù)據(jù)預(yù)處理；上下文；決策樹(shù)；分布式；用戶行為分析

隨著移動(dòng)網(wǎng)絡(luò)技術(shù)的快速發(fā)展，移動(dòng)網(wǎng)絡(luò)公司通過(guò)移動(dòng)網(wǎng)絡(luò)累積了海量的用戶上網(wǎng)行為數(shù)據(jù)。對(duì)這些數(shù)據(jù)進(jìn)行分析能預(yù)測(cè)用戶的興趣及其需求從而使移動(dòng)網(wǎng)絡(luò)公司對(duì)用戶提供更好的個(gè)性化服務(wù)，提高用戶的滿意度。然而與傳統(tǒng)數(shù)據(jù)相比，這些數(shù)據(jù)具有數(shù)據(jù)量大、數(shù)據(jù)多樣性、增長(zhǎng)快速、價(jià)值密度低等特點(diǎn)。因此，提出一種有針對(duì)性的移動(dòng)用戶行為分析方法已成為移動(dòng)網(wǎng)絡(luò)公司拓展業(yè)務(wù)過(guò)程中亟待解決的問(wèn)題。目前，移動(dòng)網(wǎng)絡(luò)用戶的行為分析方法主要有K-means聚類、決策樹(shù)算法、貝葉斯網(wǎng)絡(luò)建模方法和神經(jīng)網(wǎng)絡(luò)建模方法等[1-3]。但是這些方法在對(duì)用戶興趣提取過(guò)程中忽略了移動(dòng)網(wǎng)絡(luò)上下文[4]對(duì)于用戶行為的影響。

本文提出了一個(gè)分布式的系統(tǒng)架構(gòu)用于對(duì)海量數(shù)據(jù)的處理，并且通過(guò)數(shù)據(jù)預(yù)處理排除噪聲數(shù)據(jù)，提高了算法的分類效率，并且在決策樹(shù)算法中引入了上下文信息，從而提高了移動(dòng)網(wǎng)絡(luò)用戶行為分析的可靠性和準(zhǔn)確性。

1 移動(dòng)網(wǎng)絡(luò)上下文

網(wǎng)絡(luò)上下文是用來(lái)描述用戶、網(wǎng)絡(luò)環(huán)境和上網(wǎng)設(shè)備的狀態(tài)的信息，它包括用戶，時(shí)間，地點(diǎn)，用戶狀態(tài)和相互關(guān)系等。在本文中，將移動(dòng)網(wǎng)絡(luò)上下文分成3類，分別是移動(dòng)網(wǎng)絡(luò)用戶上下文和上網(wǎng)智能設(shè)備上下文和移動(dòng)網(wǎng)絡(luò)環(huán)境上下文。

具體定義如下：

移動(dòng)用戶上下文(Mobile User Context, MUC)=

MUC描述了用戶的一些基本信息，它包括了用戶的年齡，性別，職業(yè)和學(xué)歷，這些用戶的基本信息是用戶在注冊(cè)上網(wǎng)時(shí)主動(dòng)提提供的。

上網(wǎng)智能設(shè)備上下文(Device Context, DC)=

DC描述了用戶使用的上網(wǎng)設(shè)備的基本信息，它包括了設(shè)備的唯一標(biāo)識(shí)mac地址，還有設(shè)備的種類比如手機(jī)、平板電腦等，設(shè)備的品牌，設(shè)備的長(zhǎng)寬高。

移動(dòng)網(wǎng)絡(luò)環(huán)境上下文(Mobile Network Context, MNC)=

MNC描述了用戶所處的移動(dòng)網(wǎng)絡(luò)環(huán)境狀態(tài)及可能影響用戶行為的因素，包括用戶在哪個(gè)地點(diǎn)上網(wǎng)、用戶的IP地址、用戶上網(wǎng)時(shí)間以及當(dāng)前的網(wǎng)絡(luò)文化。

2 移動(dòng)網(wǎng)絡(luò)用戶行為分析

2.1 數(shù)據(jù)預(yù)處理

面對(duì)大量的移動(dòng)網(wǎng)絡(luò)用戶，移動(dòng)網(wǎng)絡(luò)用戶行為數(shù)據(jù)是爆炸性的增長(zhǎng)。然而這些數(shù)據(jù)里面充斥了大量的無(wú)用數(shù)據(jù)，比如：重復(fù)的數(shù)據(jù)、空值的數(shù)據(jù)等。因此，獲得到的數(shù)據(jù)通常是不完整的、噪聲的并且是矛盾的數(shù)據(jù)[5]。

針對(duì)這一系列的問(wèn)題，基于數(shù)據(jù)預(yù)處理[6]的概念，本文設(shè)計(jì)了對(duì)移動(dòng)網(wǎng)絡(luò)用戶行為數(shù)據(jù)的預(yù)處理步驟。首先，對(duì)于每個(gè)移動(dòng)網(wǎng)絡(luò)運(yùn)營(yíng)商提供的不同格式的用戶行為數(shù)據(jù)進(jìn)行數(shù)據(jù)格式轉(zhuǎn)換；其次，對(duì)Dmac值進(jìn)行判斷如果是空則表明它是無(wú)效數(shù)據(jù)并直接丟棄掉；最后，對(duì)重復(fù)數(shù)據(jù)進(jìn)行判斷，這里定義一個(gè)時(shí)間閾值(threshold)，一個(gè)用戶在這個(gè)閾值內(nèi)的行為是不可能發(fā)生改變的。所以當(dāng)同一用戶的行為數(shù)據(jù)的前后時(shí)間相隔不大于時(shí)間閾值時(shí)，只取第一條，后一條到來(lái)的數(shù)據(jù)直接丟棄掉，計(jì)算公式

Idate1-Idate2≤threshold

(1)

通過(guò)這3個(gè)步驟的處理，一方面可以減少不必要的計(jì)算和數(shù)據(jù)存儲(chǔ)空間，減輕系統(tǒng)的負(fù)擔(dān)；另一方面可以提高系統(tǒng)的分析準(zhǔn)確性。

2.2 決策樹(shù)

在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中決策樹(shù)也是一種最普遍的分類算法，它是易于實(shí)現(xiàn)和理解的并且能夠在較短時(shí)間內(nèi)能夠?qū)Υ罅康臄?shù)據(jù)做出可行和良好的結(jié)果[7]。通常情況下，決策樹(shù)通過(guò)啟發(fā)式信息從基于特征的例子中進(jìn)行學(xué)習(xí)和推理[8-9]。C4.5算法是被使用最多的并且是最廣泛的創(chuàng)建決策樹(shù)的算法，所以選擇C4.5來(lái)進(jìn)行決策樹(shù)的創(chuàng)建[10]。C4.5使用一種更為準(zhǔn)確方法去尋找最優(yōu)屬性去做分裂，因?yàn)閷ふ乙恢滦宰钚〉臎Q策樹(shù)問(wèn)題與訓(xùn)練集是NP-完全的[10-11]，這是一個(gè)結(jié)果在接近最優(yōu)的樹(shù)的重要特征。

本文使用C4.5決策樹(shù)算法對(duì)移動(dòng)網(wǎng)絡(luò)用戶行為數(shù)據(jù)進(jìn)行興趣分類，該算法根據(jù)信息增益率來(lái)選擇測(cè)試屬性。該算法的主要步驟為：假設(shè)已知用戶行為樣本集為T，集合的類型為：{C1，C2，C3，…，Ck}。選擇一個(gè)屬性V去分割樣本集T，屬性V有不連續(xù)值{v1,v2,v3,…,vn}，因此將樣本集T分成了n個(gè)數(shù)據(jù)子集，分別為T1，T2，…，Tn。所以|T|就為樣本集T的例子的數(shù)量，然后|Ti|是屬性V=vi的例子的數(shù)量。|Cjv|是種類Cj在V=vi的例子中的數(shù)量。所以

(1)種類Cj出現(xiàn)的概率

P(Cj)=|Cj|/|T|=freq(Cj,T)

(2)

(2)屬性V=vi出現(xiàn)的概率

p(VI)=|tI|/|T|

(3)

(3)類別Cj在V=vi中出現(xiàn)的條件概率

P(Cj|vt)=|(Cjv|/|Ti|)

(4)

(4)信息類型熵的計(jì)算公式

(5)

(5)條件熵的類型

(6)

(6)信息增益

I(C,V)=H(C)-H(C/V)=Info(T)-
Infov(T)=gain(v)

(7)

(7)以屬性V分割后得到的信息熵

(8)

(8)信息增益率

gain_ratio(v)=I(C,V)/H(V)=
gain(v)/split_Info(v)

(9)

3 移動(dòng)網(wǎng)絡(luò)用戶行為分析系統(tǒng)架構(gòu)

3.1 系統(tǒng)整體架構(gòu)

傳統(tǒng)的移動(dòng)用戶行為分析工具并具備分析海量的移動(dòng)用戶行為數(shù)據(jù)，同時(shí)要求所有數(shù)據(jù)都在單一的服務(wù)器上處理，硬件能力造成了數(shù)據(jù)處理的瓶頸。針對(duì)這一問(wèn)題，本文提出了分布式的系統(tǒng)架構(gòu)，增加了系統(tǒng)的伸縮性和擴(kuò)展性，當(dāng)系統(tǒng)集群出現(xiàn)處理瓶頸時(shí)，可以通過(guò)增加機(jī)器節(jié)點(diǎn)從而提高系統(tǒng)的數(shù)據(jù)存儲(chǔ)能力和處理能力。

在分布式的移動(dòng)網(wǎng)絡(luò)用戶分析系統(tǒng)中，采取了分布式的Zookeeper來(lái)協(xié)調(diào)分布式應(yīng)用服務(wù)程序。利用Kafka系統(tǒng)集群實(shí)現(xiàn)信息的接收和存儲(chǔ)，其是一種高吞吐量分布式發(fā)布訂閱的消息系統(tǒng)，即使有TB級(jí)的數(shù)據(jù)它也能夠保持高速和穩(wěn)定的性能。Storm是一個(gè)開(kāi)源的分布式實(shí)時(shí)處理框架，可以高效的處理大量的流式數(shù)據(jù)[12]。圖1展示了整個(gè)系統(tǒng)的架構(gòu)。

圖1 系統(tǒng)整體架構(gòu)圖

3.2Zookeeper集群

在大規(guī)模的分布式應(yīng)用場(chǎng)景下，容易出現(xiàn)服務(wù)協(xié)調(diào)應(yīng)用問(wèn)題。針對(duì)這一問(wèn)題，在分布式移動(dòng)網(wǎng)絡(luò)用戶分析系統(tǒng)中采用了Zookeeper來(lái)解決。Zookeeper是為分布式應(yīng)用提供協(xié)調(diào)管理的服務(wù)[13]。它為該系統(tǒng)中的Kafka和Storm提供了統(tǒng)一配置服務(wù)、集群管理和分布式同步服務(wù)等。在Zookeeper服務(wù)中，包含了兩個(gè)角色分別是leader和follower，其中l(wèi)eader主要負(fù)責(zé)寫服務(wù)和數(shù)據(jù)同步，follower主要提供讀服務(wù)。

Zookeeper的系統(tǒng)架構(gòu)如圖2所示，其中客戶端可以連接到每個(gè)server，每個(gè)server的數(shù)據(jù)完全相同，其中每個(gè)follower都和leader有連接，它們接收l(shuí)eader的數(shù)據(jù)更新操作。Server記錄事務(wù)日志和快照到持久存儲(chǔ)，其中如果有(2n+1)個(gè)服務(wù)的集群，則集群允許n個(gè)服務(wù)失效。

圖2 Zookeeper集群架構(gòu)圖

3.3 Kafka集群

對(duì)于傳統(tǒng)的數(shù)據(jù)收集方式，當(dāng)隨著數(shù)據(jù)的爆炸性增長(zhǎng)時(shí)，會(huì)產(chǎn)生新的數(shù)據(jù)存儲(chǔ)問(wèn)題、擴(kuò)容困難并且隨著數(shù)據(jù)量的增大數(shù)據(jù)接收的速度會(huì)大幅度變慢。針對(duì)這個(gè)問(wèn)題，本文采用了分布式的Kafka對(duì)用戶行為數(shù)據(jù)進(jìn)行收集和存儲(chǔ)。Kafka是一個(gè)分布式的消息系統(tǒng)，使用了發(fā)布-訂閱的模式去收集和分發(fā)數(shù)據(jù)[14]。系統(tǒng)架構(gòu)由生產(chǎn)者(producers)、消費(fèi)者(consumers)和代理人(brokers)組成。為了提高系統(tǒng)性能，它分布在多臺(tái)的計(jì)算機(jī)上[15]。生產(chǎn)者采用推送模式去發(fā)布消息到brokers中，同時(shí)，消費(fèi)者采用拉取模式從brokers中訂閱消息[16]。在Kafka集群中，每個(gè)broker的狀態(tài)都是相同的，所以容易從Kafka集群中添加和刪除一個(gè)broker[17]。Kafka的集群架構(gòu)如圖3所示。

圖3 Kafka集群架構(gòu)

3.4 Storm集群

針對(duì)傳統(tǒng)用戶行為分析架構(gòu)將數(shù)據(jù)放在單一的服務(wù)器上，這樣會(huì)限制系統(tǒng)的性能并且不容易對(duì)整個(gè)系統(tǒng)進(jìn)行擴(kuò)展，因此本文中采取了分布式的Storm框架對(duì)用戶行為數(shù)據(jù)進(jìn)行分析。Storm是最流行的實(shí)時(shí)流處理框架，提供了基本的原語(yǔ)，并且在高容量和關(guān)鍵任務(wù)的應(yīng)用程序中能夠保證一定的容錯(cuò)的分布式計(jì)算[18]。一個(gè)Storm集群由一個(gè)主(nimbus)節(jié)點(diǎn)和一個(gè)或者多個(gè)的工作節(jié)點(diǎn)(supervisors)組成，架構(gòu)如圖4所示。

圖4 Storm集群架構(gòu)

Storm集群中每個(gè)任務(wù)是被分配到不同的組件中執(zhí)行的，每個(gè)組件執(zhí)行特定的任務(wù)。集群中產(chǎn)生源數(shù)據(jù)的組件被稱為spout，在本文提出的系統(tǒng)中，從Kafka集群讀取數(shù)據(jù)。然后spout發(fā)送一連串的tuple給執(zhí)行處理的組件，tuple是一次消息傳遞的基本單元。其中執(zhí)行處理的組件叫做bolt，數(shù)據(jù)預(yù)處理和C4.5決策樹(shù)分類處理邏輯就寫在bolt中。Spout和bolt組合成了一個(gè)topology，是在Storm集群中一個(gè)實(shí)時(shí)應(yīng)用程序，其中可以是一個(gè)或者多個(gè)的spout和bolt。

以本文為例，設(shè)計(jì)了一個(gè)適用的topology。包括了一個(gè)讀取數(shù)據(jù)組件kafkaSpout，數(shù)據(jù)預(yù)處理寫在兩個(gè)組件中，一個(gè)distributeBolt進(jìn)行格式轉(zhuǎn)換和去除空數(shù)據(jù)，一個(gè)deduplicationBolt進(jìn)行用戶行為數(shù)據(jù)去重。對(duì)用戶行為數(shù)據(jù)進(jìn)行分類寫在classficationBolt，圖5展示了本文設(shè)計(jì)的完整的topology結(jié)構(gòu)。

圖5 topology結(jié)構(gòu)

4 系統(tǒng)實(shí)現(xiàn)

為了驗(yàn)證分布式移動(dòng)網(wǎng)絡(luò)用戶行為分析系統(tǒng)的可行性和性能，分別使用3臺(tái)計(jì)算機(jī)用于系統(tǒng)的搭建，3臺(tái)計(jì)算機(jī)配置相同，均為8 GB內(nèi)存和1 TB硬盤。然后按上述系統(tǒng)架構(gòu)在3臺(tái)計(jì)算機(jī)中搭建和配置Zookeeper、Kafka和Storm集群。

系統(tǒng)啟動(dòng)成功后，將準(zhǔn)備好的用戶行為的樣本數(shù)據(jù)輸入到系統(tǒng)中，最后通過(guò)集群的監(jiān)控界面統(tǒng)計(jì)系統(tǒng)運(yùn)行情況。圖6是系統(tǒng)中數(shù)據(jù)存儲(chǔ)和消費(fèi)情況，logsize表示系統(tǒng)接收到了多少數(shù)據(jù)量，lag表示系統(tǒng)中還有多少數(shù)據(jù)沒(méi)有被消費(fèi)，offset表示消費(fèi)了多少數(shù)據(jù)。從圖6結(jié)果中可以知道，當(dāng)系統(tǒng)存儲(chǔ)數(shù)據(jù)增多時(shí)并不會(huì)影響它的接收速度，同時(shí)當(dāng)系統(tǒng)開(kāi)始對(duì)數(shù)據(jù)進(jìn)行處理后，消費(fèi)速度和生產(chǎn)速度基本相同，表明系統(tǒng)運(yùn)行良好并且較為穩(wěn)定

表1顯示了本文設(shè)計(jì)的topology在集群中的運(yùn)行狀態(tài)，通過(guò)結(jié)果可以看出，使用Storm集群處理用戶行為數(shù)據(jù)時(shí)，在短時(shí)間內(nèi)可以處理大量數(shù)據(jù)，并且失敗數(shù)較小，達(dá)到了設(shè)計(jì)系統(tǒng)的預(yù)期效果。

圖6 系統(tǒng)中數(shù)據(jù)存儲(chǔ)和消費(fèi)情況

表1 topology狀態(tài)表

WindowEmittedTransferredcompletelatency/msAckedFailed10m0s140720019375605468.6951407140603h0m0s17665940241065404318.1721766391620241d0h0m0s17665940241065404318.172176639162024Alltime17665940241065404318.172176639162024

如表2所示，當(dāng)僅使用C4.5決策樹(shù)算法對(duì)用戶行為數(shù)據(jù)進(jìn)行分類時(shí)，當(dāng)數(shù)據(jù)量較小時(shí)，準(zhǔn)確率較高，但是數(shù)據(jù)量增大時(shí)，準(zhǔn)確率開(kāi)始下降。當(dāng)在C4.5決策樹(shù)算法之前加入數(shù)據(jù)預(yù)處理后能夠明顯地去除噪聲等無(wú)效數(shù)據(jù)對(duì)分類效果的干擾，但是分類效果并不理想。最后使用數(shù)據(jù)預(yù)處理并且在C4.5決策樹(shù)種增加了移動(dòng)網(wǎng)絡(luò)上下文，隨著數(shù)據(jù)量的不斷增大，分類效果也越來(lái)越準(zhǔn)確，達(dá)到了設(shè)計(jì)的預(yù)期效果。

表2 3種方法的準(zhǔn)確率比較

5 結(jié)束語(yǔ)

本文提出了一個(gè)分布式移動(dòng)網(wǎng)絡(luò)用戶行為分析系統(tǒng)，與傳統(tǒng)的用戶行為分析相比，該系統(tǒng)引入了移動(dòng)網(wǎng)絡(luò)上下文同時(shí)對(duì)海量數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理，最后利用C4.5決策樹(shù)算法進(jìn)行興趣分類，得到了更為可靠和準(zhǔn)確的分析結(jié)果。并且在面對(duì)呈現(xiàn)爆炸性增長(zhǎng)的移動(dòng)網(wǎng)絡(luò)用戶行為數(shù)據(jù)，通過(guò)采用分布式框架對(duì)系統(tǒng)進(jìn)行設(shè)計(jì)，提高了系統(tǒng)處理大數(shù)據(jù)的能力，并且提高了系統(tǒng)的可擴(kuò)展性。最后通過(guò)實(shí)驗(yàn)數(shù)據(jù)表明，移動(dòng)網(wǎng)絡(luò)用戶行為分析系統(tǒng)是一個(gè)切實(shí)可行的方案。

[1] 王攀,張順頤,陳雪嬌.基于動(dòng)態(tài)行為輪廓庫(kù)的Web用戶行為分析關(guān)鍵技術(shù)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(2):20-23.

[2] 王繼民,李雷明子,孟凡,等.基于用戶日志的移動(dòng)搜索行為分析[J].圖書情報(bào)工作,2013,57(19):102-106,120.

[3] 馬安華.基于用戶王繼民行為分析的精確營(yíng)銷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].南京:南京郵電大學(xué),2013.

[4] Anind K Dey.Understanding and using context[J].Personal and Ubiquitous Computing, 2001,5(1):4-7.

[5] 劉明月.基于Web日志的用戶行為分析[D].北京:北京交通大學(xué),2008.

[6] Sanjay Kumar Dwivedi,Bhupesh Rawat.A review paper on data preprocessing:A critical phase in web usage mining process[C].Noida:Green Computing and Internet of Things, IEEE,2015.

[7] Amany Abdelhalim,Issa Traore.A new method for learning decision trees from rules[C].Miami Beach:International Conference on Machine Learning and Applications,IEEE,2009.

[8] Quinlan J R.Induction of decision trees[J].Mach Learn,1986(1):81-106.

[9] Breiman L,Friedman J H,Olshen R A,et al.Classification and regression trees[M]. California:Wadsworth,1984.

[10] Kotsiantis S B.A review of classification techniques[J].International Journal of Computing and Informatics,2007,31(3):249-268.

[11] Quinlan J R.C4.5:programs for machine learning[M].San Francisco:Morgan Kaufmann,1993.

[12] Anderson Q.Storm real-time processing cookbook[M].Birmingham:Packet Publishing,2013.

[13] Patrick Hunt,Mahadev Konar,Flavio P,et al.Zookeeper:wait-free coordination for internet-scale systems[C].Boston:USENIX Annual Technical Conference,2010.

[14] Kreps J,Narkhede N,Rao J,et al.Kafka:a distributed messaging system for log processing[C]. Athens:Workshop on Networking Meets Databases,ACM SIGMOD,2011.

[15] Bellavista P, Corradi A, Reale A.Quality of service in wide scale publish/subscribe systems[J].Communications Surveys and Tutorials,2014(16):1591-1616.

[16] Zhao J,Sun Z,Liao Q.Implementation of k-means based on improved storm model[C].Guilin: Proceedings of ICCT2013,IEEE,2013.

[17] Skeirik S, Bobba R B,Meseguer J.Formal analysis of fault-tolerant group key management using zookeeper[C].Delft:2013 13th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing,IEEE,2013.

[18] Brian O’Neill,P Taylor Goetz.Storm blueprints:patterns for distributed real-time computation[M].UK:Pacekt Publishing Ltd,2014.

Distributed Mobile Network User Behavior Analysis System

CHEN You

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

A distributed mobile network user behavior analysis system based on data preprocessing, context and C4.5 decision tree is proposed to provide better personalized service for mobile Internet users. The system is implemented by the distributed open source framework zookeeper, kafka and storm. Implementation of the system shows the proposed system offers accurate analysis of user interest classification without affecting system performance even in the face of massive user behavior data.

preprocessing; context; decision tree; distributed; user behavior analysis

2016- 08- 09

陳友(1991-)，男，碩士研究生。研究方向：數(shù)據(jù)挖掘。

10.16180/j.cnki.issn1007-7820.2017.05.042

TP393.07

A

1007-7820(2017)05-154-05