如何利用“圖計算”實現(xiàn)大規(guī)模實時預(yù)測分析

一、何為“圖計算”

相比起“Hadoop、Spark”這種流行的大數(shù)據(jù)處理平臺，說起“圖計算”，可能許多人還比較陌生。甚至有人會誤把它當(dāng)成專門進行“圖像”處理的技術(shù)。首先我們互聯(lián)網(wǎng)上通常的定義來說明一下圖計算：

“圖計算”是以“圖論”為基礎(chǔ)的對現(xiàn)實世界的一種“圖”結(jié)構(gòu)的抽象表達，以及在這種數(shù)據(jù)結(jié)構(gòu)上的計算模式。通常，在圖計算中，基本的數(shù)據(jù)結(jié)構(gòu)表達就是：

G = （V，E，D） V = vertex （頂點或者節(jié)點）    E = edge  （邊） D = data （權(quán)重）。比如說：對于一個消費者的原始購買行為，有兩類節(jié)點：用戶和產(chǎn)品，邊就是購買行為，權(quán)重是邊上的一個數(shù)據(jù)結(jié)構(gòu)，可以是購買次數(shù)和最后購買時間。對于許多我們面臨的物理世界的數(shù)據(jù)問題，都可以利用圖結(jié)構(gòu)的來抽象表達：比如社交網(wǎng)絡(luò)，網(wǎng)頁鏈接關(guān)系，用戶傳播網(wǎng)絡(luò)，用戶網(wǎng)絡(luò)點擊、瀏覽和購買行為，甚至消費者評論內(nèi)容，內(nèi)容分類標(biāo)簽，產(chǎn)品分類標(biāo)簽等等。

圖數(shù)據(jù)結(jié)構(gòu)很好的表達了數(shù)據(jù)之間的關(guān)聯(lián)性( dependencies between data )，關(guān)聯(lián)性計算是大數(shù)據(jù)計算的核心——通過獲得數(shù)據(jù)的關(guān)聯(lián)性，可以從噪音很多的海量數(shù)據(jù)中抽取有用的信息。比如，通過為購物者之間的關(guān)系建模，就能很快找到口味相似的用戶，并為之推薦商品；或者在社交網(wǎng)絡(luò)中，通過傳播關(guān)系發(fā)現(xiàn)意見領(lǐng)袖。但現(xiàn)有的并行計算框架像MapReduce還無法滿足復(fù)雜的關(guān)聯(lián)性計算。比如，筆者曾經(jīng)發(fā)現(xiàn)有公司利用MapReduce進行社交用戶推薦，對于5000萬注冊用戶，50億關(guān)系對，利用10臺機器的集群，需要超過10個小時的計算。

最近有許多新型的基于圖的計算平臺和引擎出現(xiàn)，來應(yīng)對這種復(fù)雜的需求。比如開始有專注與圖結(jié)構(gòu)化存儲與查詢的圖數(shù)據(jù)庫 Neo4j，infinitegraph等。Google為了應(yīng)對圖計算的需求，推出了新的“計算框架”——Pregel。CMU給出了一個開源的版本——GraphLab，雖然二者都是對于復(fù)雜機器學(xué)習(xí)計算的處理框架，用于迭代型（iteration）計算，但是二者的實現(xiàn)方法卻采取了不同的路徑——Pregel是基于大塊的消息傳遞機制，GraphLab是基于內(nèi)存共享機制。同樣的，最近非?；鸬摹癝park”也有支持圖計算機器學(xué)習(xí)的模塊——GraphX，可以實現(xiàn)復(fù)雜的圖數(shù)據(jù)挖掘。

二、業(yè)務(wù)挑戰(zhàn)

時趣SocialTouch是數(shù)據(jù)驅(qū)動的移動營銷解決方案提供商。所涉及的客戶數(shù)據(jù)源涵蓋了自媒體行為，關(guān)系，內(nèi)容。企業(yè)內(nèi)部營銷，銷售，售后數(shù)據(jù)，以及其他第三方和廣告投放數(shù)據(jù)。數(shù)據(jù)來源結(jié)構(gòu)復(fù)雜。數(shù)據(jù)的應(yīng)用類型也比較多樣化，主要包括：消費者畫像，交互式消費者洞察分析，潛在消費群體挖掘，個性化內(nèi)容等等。因此，從業(yè)務(wù)出發(fā)面臨許多現(xiàn)實的技術(shù)挑戰(zhàn)：

1、大數(shù)據(jù)量：SocialTouch提供的是SaaS 模式的數(shù)據(jù)管理平臺，那么對于不同的應(yīng)用，可能會用到不同的算法策略。而一家客戶的數(shù)據(jù)平均都在100T以上，同時還在持續(xù)增加。如何利用不同的算法策略在同樣的數(shù)據(jù)結(jié)構(gòu)之上進行計算，而不是為了使用不同的算法需要修改和遷移海量的數(shù)據(jù)。需要我們采取一致性的數(shù)據(jù)結(jié)構(gòu)。

2、動態(tài)變化：營銷的核心是研究“人”，而對人的描述的主要數(shù)據(jù)是行為數(shù)據(jù)。SocialTouch通常會根據(jù)客戶的需求，持續(xù)采集消費者的行為數(shù)據(jù)。而用戶行為往往是實時動態(tài)發(fā)生，因此需要數(shù)據(jù)與模型也能夠?qū)崟r更新。

3、實時性：對于數(shù)據(jù)分析人員來說，往往許多分析的維度不是事先預(yù)定的，需求總是不斷在變化。能夠進行交互式的數(shù)據(jù)的鉆取，無疑有助于更好的發(fā)現(xiàn)營銷“真相”。因此，對于大數(shù)據(jù)量的實時計算就成為了一個挑戰(zhàn)。同時，基于消費者個體畫像和當(dāng)前的“上下文”觸發(fā)的個性化營銷也是移動營銷的主流需求。因此，這就需要服務(wù)器端在毫秒級別內(nèi)給出個性化的預(yù)測結(jié)果。目前針對復(fù)雜機器學(xué)習(xí)的“圖計算”雖然可以支持“批處理”模式的迭代計算，比如著名的PageRank模型。但對于實時分析和預(yù)測，并不是最好的解決方法。

4、關(guān)聯(lián)性：對于營銷來說“預(yù)測性”分析不僅僅是發(fā)現(xiàn)營銷的好壞，更重要的是發(fā)現(xiàn)為何好，以進行優(yōu)化。比如“歸因分析”和“相似人群”等預(yù)測性模型，都需要關(guān)聯(lián)計算的支持。而且，這種關(guān)聯(lián)性計算也對實時性有一定的要求。雖然一些圖數(shù)據(jù)庫可以支持圖數(shù)據(jù)結(jié)構(gòu)的讀取訪問，但對于大數(shù)據(jù)量的關(guān)聯(lián)計算支持較差。

三、CrowdGraph——從業(yè)務(wù)出發(fā)的選擇

為了應(yīng)對以上業(yè)務(wù)需求。SocialTouch從構(gòu)建大數(shù)據(jù)架構(gòu)開始，就啟動研發(fā)了專利技術(shù)——CrowdGraph，專業(yè)應(yīng)對消費者行為數(shù)據(jù)處理的實時圖計算引擎。并成功應(yīng)用于SocialTouch BI，社會化聆聽，數(shù)據(jù)管理平臺等產(chǎn)品中。下圖給出了CrowdGraph的邏輯架構(gòu)：

整體架構(gòu)從邏輯上劃分為4層， 分別為應(yīng)用服務(wù)層，計算查詢層，索引管理層和索引層。應(yīng)用服務(wù)層提供穩(wěn)定高效的網(wǎng)絡(luò)服務(wù)和相關(guān)的Query解析，查詢計算層負(fù)責(zé) 查找、篩選、分組過濾、游走等算法。索引管理層主要負(fù)責(zé)索引段的管理和適配，保證索引的靈活使用。索引分為vertex和edge兩種類型，vertex、edge的屬性支持Scheme定義，索引建立支持采用hadoop離線完成。 整體上索引和算法是核心。

以微博用戶的影響力標(biāo)簽計算為例子，只需要簡單的三步：

第一步：用戶以等邊上概率游走到粉絲，根據(jù)粉絲屬性值計算此步游走的權(quán)重。

第二步：粉絲以等邊概率游走到標(biāo)簽，根據(jù)標(biāo)簽的屬性值計算此步的權(quán)重。

第三步：對相同相同標(biāo)簽所在的路徑的權(quán)值累加后，對候選標(biāo)簽進行排序、過濾。

在實踐應(yīng)用中，GrowdGraph主要用于存儲各種對象（用戶，信息（商品頁面，廣告頁面）之間的互動關(guān)系，經(jīng)過測試，它具有以下特點：

• 高性能與實時：由于本身就是專為挖掘關(guān)系設(shè)計的數(shù)據(jù)系統(tǒng)， CrowdGraph預(yù)先建立和存儲了對象關(guān)系數(shù)據(jù)，同時考慮了塊讀取和內(nèi)存加速，所以與關(guān)系型數(shù)據(jù)庫相比，具有更高的查詢性能和無法比擬的計算性能，比如計算超過百萬潛在的消費者的屬性分布，只需要秒級返回結(jié)果，是傳統(tǒng)數(shù)據(jù)庫查詢的60—1200倍。
• 靈活性：與傳統(tǒng)BI系統(tǒng)和數(shù)據(jù)倉庫相比，由于CrowdGraph不必預(yù)先設(shè)計表格的結(jié)構(gòu)，所以可以動態(tài)的插入任意關(guān)系類型，非常適合存儲動態(tài)變化的信息（如人的行為）。
• 抽象性： CrowdGraph高度抽象了各種關(guān)系，不必定義結(jié)構(gòu)，就可以可以很好的表達人的行為，屬性，社會活動，廣告點擊，內(nèi)容瀏覽和商品交易等各種抽象關(guān)系。
• 精準(zhǔn)性：與其他開源的圖數(shù)據(jù)庫不同， CrowdGraph中間包括了相關(guān)算法框架層，可以直接支持實時聚類，歸因分析，貝葉斯網(wǎng)絡(luò)等模型。同時避免直接訪問抽象的數(shù)據(jù)，可以提供面向業(yè)務(wù)邏輯的精準(zhǔn)預(yù)測服務(wù)。

四、結(jié)束語

 圖是一種抽象人類行為的方法，就像一句諺語所說“知道的越多，未知的就更多。對人類的行為的分析不是一個簡單的“分類”問題，而是一種概率預(yù)測和排序問題。圖計算的應(yīng)用才剛剛開始，隨著大數(shù)據(jù)研究和應(yīng)用的發(fā)展，我們相信更多的支持“圖計算”的系統(tǒng)會被大量使用。如果你有興趣參與其中，希望和我們一起探討。