馮興+周繼恩+方亞超

摘 要：傳統(tǒng)的匹配技術因規(guī)則和參數(shù)固定，匹配性能和效果很不理想?；趯崟r大數(shù)據(jù)和機器學習技術，提出了一種新的分布式智能匹配系統(tǒng)，該系統(tǒng)根據(jù)實時匹配成功率和用戶反饋進行自我優(yōu)化。實驗表明，系統(tǒng)性能可水平擴展，匹配正確率顯著提高。

關鍵詞：智能匹配；實時大數(shù)據(jù)；機器學習；分布式協(xié)調(diào)；Spark Streaming

DOIDOI：10.11907/rjdk.171722

中圖分類號：TP303

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0005-04

0 引言

人們通過打車軟件可以匹配到最佳司機出行，亦可通過拼單軟件湊團優(yōu)惠秒殺；金融機構根據(jù)海量歷史交易構造模型，實時偵測詐欺交易；商戶根據(jù)客戶群體特征分析消費趨勢，從而進行精準營銷。這一切，都離不開匹配技術。

匹配指事物之間有相符合或相配合的關系，匹配技術旨在以一定的目標、遵循一定的規(guī)則建立事物之間的關聯(lián)，從而產(chǎn)生“協(xié)同效應”[1]。匹配技術一般遵循如下流程：從不同的事物中按照一定的規(guī)則提煉出特征，然后按照一定的目標去組合這些特征，能夠滿足預期目標則表示匹配成功[2]。傳統(tǒng)匹配技術采用固定的規(guī)則和方法，規(guī)則不會隨著實際情況發(fā)生調(diào)整和改變。實時匹配成功率較低，未成功的匹配只有等待T+1日的批量流程完成處理，難以應對越來越多的（T+0）實時場景需求。實時大數(shù)據(jù)技術[3]可以將歷史匹配記錄和實時信息結(jié)合起來分析，動態(tài)調(diào)整匹配規(guī)則和方法，提升了匹配的實時性和成功率，也提高了匹配效果和用戶體驗。

實時匹配系統(tǒng)大多基于實時處理框架自行開發(fā)。滴滴的實時打車平臺根據(jù)地理位置、歷史評分撮合乘客、司機、代駕者，采用迭代反饋算法[4]，算法分批次迭代進行，每次的參數(shù)都由系統(tǒng)動態(tài)生成。比如，系統(tǒng)在匹配失敗后會適當增加距離，降低評分要求，通過調(diào)整參數(shù)提高匹配成功概率。滴滴打車平臺基于Lambda架構[5]設計，將實時數(shù)據(jù)和歷史數(shù)據(jù)結(jié)合應用，提升匹配效果，增強用戶體驗，同時獲取更多有價值的數(shù)據(jù)。

微軟的實時數(shù)據(jù)質(zhì)量監(jiān)控平臺是典型的“模型匹配”[6]系統(tǒng)。平臺后端連接實時機器學習算法，通過分析實時數(shù)據(jù)和歷史數(shù)據(jù)，不斷完善風險模型；將結(jié)果數(shù)據(jù)與風險模型動態(tài)匹配，可監(jiān)控數(shù)據(jù)質(zhì)量并發(fā)出預警。

實時匹配實現(xiàn)具有兩個特點：①結(jié)合實時數(shù)據(jù)和歷史數(shù)據(jù)共同分析；②可動態(tài)調(diào)整參數(shù)，優(yōu)化匹配效果。但是，由于匹配技術多是公司的核心技術和商業(yè)秘密，現(xiàn)有成果大多閉源，對匹配技術的研究和應用也各自為攻，因此，業(yè)內(nèi)尚未形成一個主流成熟的框架。

1 實時大數(shù)據(jù)

大數(shù)據(jù)（Big Data）技術是一種數(shù)據(jù)存儲和分析技術，具有5V特性[7]。大數(shù)據(jù)技術能在每日幾百TB的數(shù)據(jù)增長情況下高效分析數(shù)據(jù)，并從低價值密度的海量數(shù)據(jù)中挖掘出有利于企業(yè)戰(zhàn)略的信息。

2011年興起的流式計算[8]，被稱為是后Hadoop時代的實時云計算。大數(shù)據(jù)流式計算引擎將多種數(shù)據(jù)源的數(shù)據(jù)整合并切割成小塊，進而對數(shù)據(jù)進行并行處理，在流數(shù)據(jù)不斷變化過程中進行實時分析，捕捉并返回可能對用戶有用的信息。流式計算技術百花齊放，種類繁多，如Yahoo的S4、Twitter的Storm、Facebook的Puma，以及被稱為“Hadoop替代者”的Spark和Spark Streaming[9]。其中，S4不支持“至少遞送一次”的規(guī)則[10]，導致其有丟失事件的風險；盡管Storm應用較多，但其性能差強人意；相較而言，Spark Streaming采用“微批量”的處理技術，處理性能較高，應用非常廣泛。此外，Spark和圖算法、機器學習算法天然具備兼容性，生態(tài)發(fā)展較好。

Spark是一個類似MapReduce的并行計算框架，其核心數(shù)據(jù)結(jié)構是彈性分布式數(shù)據(jù)集（Resilient Distributed Datasets， RDD），提供比MapReduce更豐富的模型，可在內(nèi)存中對RDD進行多次計算和迭代，并支持復雜的圖算法和機器學習算法。

Spark Streaming是一個建立在Spark之上的實時計算框架，它擴展了Spark處理大規(guī)模流式數(shù)據(jù)的能力，復用Spark接口實現(xiàn)復雜的實時算法，且與Spark生態(tài)中的其它組件兼容性好。Spark Streaming處理原理如圖1所示，將數(shù)據(jù)流按時間片劃分為若干段數(shù)據(jù)，每一段數(shù)據(jù)作為一個RDD，處理引擎對每個RDD進行Filter、Map、Reduce等算法操作后，將其作為Spark Job提交給Spark引擎進行計算。Spark Streaming支持數(shù)百節(jié)點的分布式實時計算，具備計算的高可用、容錯特性。因此，本文采用Spark Streaming作為主要的實時計算技術。

2 智能匹配系統(tǒng)

2.1 匹配流程

匹配系統(tǒng)流程如下：通過規(guī)則提取源消息的特征向量，放置于撮合引擎[11]中；撮合引擎以預先設定的目標匹配特征向量；如果匹配結(jié)果達到目標要求，則判定為匹配成功；否則，匹配失敗，進入下一次匹配。

傳統(tǒng)匹配技術采用固定的特征向量提取方式，在撮合系統(tǒng)中也使用固定的參數(shù)去匹配特征向量[12]。以拼單系統(tǒng)為例，用戶有一張滿500減200的優(yōu)惠券，但預期消費只有300元，期望通過實時拼單系統(tǒng)找到附近的人一起共享優(yōu)惠券，傳統(tǒng)匹配技術算法[13]如下：

輸入：特征向量

<優(yōu)惠券金額，預期消費， 經(jīng)度，維度>

輸出：匹配結(jié)果

（1） 提取特征向量。

（2）將特征向量導入撮合引擎。

（3）撮合引擎根據(jù)預先設置參數(shù)（如向量權重，超時時間）匹配附近的人。

（4）匹配成功，則返回配對信息。

（5）匹配失敗且未超時，則返回步驟（2）繼續(xù)匹配。endprint

（6）匹配失敗且超時，則返回匹配失敗。

如果參數(shù)配置不合理，將可能導致客戶等待時間太長、匹配失敗、距離太遠、總體消費金額太多等問題，從而導致客戶流失。此外，由于客戶向系統(tǒng)發(fā)送的數(shù)據(jù)僅是固定的特征向量，客戶的其它信息（如歷史消費次數(shù)、信用等級、消費路線等）并未在匹配算法中占有權重，可能使不誠信用戶被頻繁推送，從而導致拼單系統(tǒng)無法精準推送優(yōu)惠券，用戶體驗效果不佳。

可見，傳統(tǒng)匹配技術無法跟上服務升級速度[14]，也無法滿足需求的時效性和準確性，本文提出基于實時大數(shù)據(jù)的智能匹配系統(tǒng)，能有效解決以上問題。

2.2 匹配系統(tǒng)總體設計

2.2.1 節(jié)點設計

智能匹配系統(tǒng)采用分布式部署結(jié)構，有3類角色：

（1）中央控制節(jié)點：負責存放當前的特征提取規(guī)則以及匹配參數(shù)（向量因子權重、超時時間等），實時接收采集節(jié)點和撮合節(jié)點反饋，調(diào)用后端機器學習算法調(diào)整模型，并修正規(guī)則和參數(shù)。

（2）采集節(jié)點：負責從多個客戶端收集用戶請求信息，從中央控制節(jié)點獲取特征提取規(guī)則，按規(guī)則對信息進行特征提取，并生成統(tǒng)一格式的報文通過Kafka發(fā)送給撮合節(jié)點。采集節(jié)點會收集用戶的反饋信息，并向中央控制節(jié)點進行反饋。

（3）撮合節(jié)點：撮合節(jié)點負責接收采集節(jié)點發(fā)過來的信息，按照一定規(guī)則，以預先設定的目標進行撮合。撮合節(jié)點和中央控制節(jié)點保持通信，隨時根據(jù)中央控制節(jié)點參數(shù)調(diào)整撮合行為。撮合節(jié)點根據(jù)匹配成功率、匹配效果向中央控制節(jié)點反饋。

2.2.2 運行機制

用戶將匹配請求發(fā)送到采集節(jié)點，采集節(jié)點根據(jù)從中央控制節(jié)點獲取的特征提取規(guī)則，對原始請求進行規(guī)則提取和規(guī)范化處理，得到特征向量，并將這些特征向量按不同主題發(fā)送給不同的撮合節(jié)點。撮合節(jié)點根據(jù)從中央控制節(jié)點獲取的匹配參數(shù)（例如向量中不同特征的權重）及匹配目標，將采集節(jié)點傳來的特征向量流封裝成若干分布式彈性數(shù)據(jù)集（RDD）以及一系列操作[15]，將其提交給Spark Streaming進行匹配處理。Spark Streaming分為多個微批次進行處理，每次處理后都會存在一些匹配失敗的特征向量。撮合節(jié)點將這些向量暫時緩存在Redis[16]，積累到一定數(shù)量后，根據(jù)機器學習算法結(jié)果調(diào)整參數(shù)，再次封裝為RDD提交給Spark進行二次匹配。撮合節(jié)點還會根據(jù)匹配成功率、匹配效果向中央控制節(jié)點進行反饋，以幫助中央控制節(jié)點標記參數(shù)樣本[17]，進行自我優(yōu)化。系統(tǒng)整體設計如圖2所示。

以實時拼單系統(tǒng)為例。實時拼單系統(tǒng)能夠幫助用戶湊單消費優(yōu)惠券，例如用戶A發(fā)布了一個請求：持有一張滿500元減200元優(yōu)惠券，且期望消費300元。理想狀態(tài)是系統(tǒng)能幫助A找到一位期望消費200元的搭檔B，但實際情況可能找到的是消費230元的用戶B。這次匹配也是成功的，只是匹配效果有所下降。此外，智能拼單系統(tǒng)能通過地理位置、歷史評價等信息綜合匹配，同時能根據(jù)用戶反饋和實時匹配成功率進行自我優(yōu)化。本方法中，多名用戶各自提交原始請求到采集節(jié)點，采集節(jié)點根據(jù)特征向量提取規(guī)則提取出特征向量λ=<票券門檻，期望消費，經(jīng)度，緯度，評價分>，將票券類型哈希后發(fā)送到某個撮合節(jié)點（哈?？梢员ＷC同一類型的票券都落在同一個撮合節(jié)點上）。采集節(jié)點同時也會接收用戶的反饋信息，并通知給中央控制節(jié)點。撮合節(jié)點從中央控制節(jié)點獲取匹配參數(shù)，例如向量中的5個因子對匹配結(jié)果的影響權重，將特征向量流封裝為RDD，將匹配算法封裝為基于RDD的運算，將其提交給Spark Streaming進行運算。本次運算未能匹配成功的向量將被緩存到Redis中進行下一次運算；同時撮合節(jié)點將向中央控制節(jié)點反饋匹配結(jié)果。

3 智能匹配系統(tǒng)實現(xiàn)

3.1 中央控制節(jié)點

中央控制節(jié)點主備2個，只有一個節(jié)點處于活躍狀態(tài)，另一個節(jié)點隨時處于待命狀態(tài)，主備節(jié)點共享存儲。中央控制節(jié)點用于存放當前的特征提取規(guī)則以及匹配參數(shù)（向量因子權重、超時時間等），實時接收采集節(jié)點和撮合節(jié)點反饋，調(diào)用后端機器學習算法調(diào)整模型，并修正規(guī)則和參數(shù)。機器學習算法持續(xù)接收反饋，不斷迭代更新模型，直到模型穩(wěn)定。每當規(guī)則和參數(shù)發(fā)生變化時，都會發(fā)起一次同步請求，將信息同步到采集節(jié)點和撮合節(jié)點。

3.2 采集節(jié)點

采集節(jié)點收集用戶原始請求，并根據(jù)最新的提取規(guī)則提取出特征向量，將向量規(guī)則化后通過Kafka發(fā)送給撮合節(jié)點。采集節(jié)點同時會收集用戶的反饋信息，比如匹配結(jié)果是否滿意、等待時間是否太長等，同時向中央控制單元匯報。

采集節(jié)點可通過Redis緩存一些用戶請求，然后集中進行處理后發(fā)至Kafka隊列，以提升系統(tǒng)吞吐量；接收數(shù)據(jù)時，也可一次接收多個用戶請求，再逐一通知給用戶，如圖3所示。

3.3 撮合節(jié)點

撮合節(jié)點封裝了核心匹配算法。Spark Streaming將撮合節(jié)點接收到的流數(shù)據(jù)劃分成段，每一段對應一個RDD，撮合算法只需要定義基于這些RDD的運算即可。簡單撮合算法思路是：先對數(shù)據(jù)集進行排序，然后從頭遍歷數(shù)據(jù)集，對每一個元素從尾部尋找和它匹配的元素；如果匹配，則移除匹配成功的所有元素，如果不匹配，則該元素進入下一次匹配。整個過程迭代數(shù)次，直至結(jié)果集穩(wěn)定，偽代碼如下：

sort（dataSet）

while（iteration_times>0）

do

for（ element in dataSet）

find element from the dataset match the destination from the tail

if（match）

remove matched elements

fi

doneendprint

done

由于傳入的向量是多維度的，上述代碼需要修改為：在滿足既定條件情況下，按照其它因子選取最優(yōu)解。例如在拼單系統(tǒng)中，兩名用戶的湊單金額高于消費券的最低消費額即為匹配成功，但是兩位用戶的距離和信用評價將影響最優(yōu)匹配結(jié)果，而這些因子的權重是由中央控制節(jié)點提供的。撮合節(jié)點不斷反饋匹配成功率和匹配效果，以使中央控制單元不斷優(yōu)化參數(shù)，具體實現(xiàn)如圖4所示。

此外，RDD中應包含實時數(shù)據(jù)和歷史數(shù)據(jù)。算法在處理用戶的實時請求時，可根據(jù)用戶的關鍵域信息（例如用戶ID、活躍時間等）從HBase中查詢到該用戶的歷史請求明細，并分析該用戶的信用、行為、消費習慣、偏好等特征，從而為用戶選擇更合適的匹配對象。

撮合節(jié)點對一個RDD的匹配計算不一定讓所有消息都完美匹配，那些沒有匹配成功的消息將被緩存進Redis，加入下一次匹配。

4 實驗分析

4.1 實驗環(huán)境

實驗節(jié)點標準配置：主處理器4核心3.2GHz主頻，內(nèi)存16G；實驗載體為本文實時拼單系統(tǒng)；以卷積神經(jīng)網(wǎng)絡（CNN）作為后端機器學習引擎的實現(xiàn)技術。

4.2 實驗1：性能測試

實驗目的：測試本系統(tǒng)性能和水平擴展性。

實驗配置：（初始）4個采集節(jié)點，2個撮合節(jié)點，40節(jié)點Spark集群。

實驗過程：①客戶端不斷增加模擬用戶請求，直至性能瓶頸；②橫向擴容采集節(jié)點和撮合節(jié)點，觀察實時TPS。

實驗數(shù)據(jù)：初始配置（6節(jié)點），匹配成功的TPS峰值為4.2萬左右；擴容系統(tǒng)至9節(jié)點，TPS峰值為6.5萬左右；擴充系統(tǒng)至12節(jié)點，TPS峰值為7.9萬左右；最終擴充到21個節(jié)點時，TPS的峰值為12萬左右。實驗結(jié)果如圖5所示。

圖5 性能測試 圖6 動態(tài)優(yōu)化

在該過程中，系統(tǒng)處理延遲基本處于穩(wěn)定狀態(tài)，隨機用戶的期望匹配延遲小于1.6s。

實驗結(jié)論：本系統(tǒng)處理性能優(yōu)異。根據(jù)已公布數(shù)據(jù)，本系統(tǒng)相比于滴滴實時匹配系統(tǒng)，相同集群規(guī)模的吞吐量提升了41%，處理延遲減少了25%～60%。

實驗分析：本系統(tǒng)采用Spark Streaming微批量處理技術，相比于滴滴的Smaza，極大提升了處理能力；采用流批數(shù)據(jù)并行處理的設計思想，極大減少了處理延遲。

4.3 實驗2：動態(tài)優(yōu)化

實驗目的：證明本系統(tǒng)可根據(jù)實時匹配率和用戶評價進行反饋式學習，不斷優(yōu)化自身參數(shù)，提升匹配效果。

實驗配置：4個采集節(jié)點，2個撮合節(jié)點，40節(jié)點的Spark集群，20節(jié)點的CNN深度學習網(wǎng)絡。

實驗過程：啟動系統(tǒng)，記錄實時匹配成功率和TPS，持續(xù)60分鐘。

實驗現(xiàn)象：開始時匹配成功率較低且劇烈震蕩，隨著深度學習算法的運行，參數(shù)不斷調(diào)整，成功率開始顯著提升，60分鐘時趨于穩(wěn)定，成功率大約在78%左右，實驗結(jié)果如圖6所示。

實驗結(jié)論：本系統(tǒng)能根據(jù)實時匹配結(jié)果進行自我優(yōu)化，能夠自動提升匹配成功率。

實驗分析：本系統(tǒng)能根據(jù)實時匹配結(jié)果進行反饋式分析，動態(tài)調(diào)整匹配參數(shù)，增加匹配成功率；并能結(jié)合用戶的歷史信息進行分析，做到“投其所好”，提供更人性化的匹配結(jié)果。

5 結(jié)語

傳統(tǒng)的匹配技術因規(guī)則和參數(shù)固定，匹配性能和效果很不理想；基于實時大數(shù)據(jù)的匹配技術是各公司的核心技術和商業(yè)秘密，現(xiàn)有成果大多閉源，研究和應用也各自為攻，尚未形成一個主流成熟的框架。本文提出了一種基于大數(shù)據(jù)匹配技術的通用技術框架。該框架易搭建，采用分布式架構，支持水平擴展，性能優(yōu)異，相對于業(yè)界主流系統(tǒng)，吞吐量提升了41%，匹配延遲減少了25%以上；結(jié)合實時數(shù)據(jù)和歷史數(shù)據(jù)分析，匹配結(jié)果更精確；后端搭配機器學習算法，可主動優(yōu)化匹配效果。

參考文獻：

[1] 朱海燕， 蔡銘， 金連甫. 網(wǎng)絡化制造系統(tǒng)中的服務智能匹配技術研究[J]. 計算機工程與應用， 2004， 40（18）：137-140.

[2] 郭會， 王麗俠. 基于個性化需求的拼車路徑匹配算法研究[J]. 計算機技術與發(fā)展， 2017（1）：57-60.

[3] 邱雪濤， 趙金濤. 基于實時大數(shù)據(jù)處理的交易欺詐偵測的研究[J]. 軟件產(chǎn)業(yè)與工程， 2013（4）：36-40.

[4] 顧軍華， 任超， 譚慶. 基于正反饋機制的遺傳算法[J]. 計算機工程與應用， 2007， 43（14）：73-74.

[5] 蘇樹鵬. 基于Lambda架構的移動互聯(lián)大數(shù)據(jù)平臺架構的設計與應用[J]. 企業(yè)科技與發(fā)展， 2016（6）：66-68.

[6] 方幼林， 楊冬青， 唐世渭，等. 數(shù)據(jù)倉庫中數(shù)據(jù)質(zhì)量控制研究[J]. 計算機工程與應用， 2003， 39（13）：1-4.

[7] 孟小峰， 慈祥. 大數(shù)據(jù)管理：概念、技術與挑戰(zhàn)[J]. 計算機研究與發(fā)展， 2013， 50（1）：146-169.

[8] 孫大為. 大數(shù)據(jù)流式計算：應用特征和技術挑戰(zhàn)[J]. 大數(shù)據(jù)， 2015， 1（3）：99-105.

[9] 夏俊鸞， 邵賽賽. Spark Streaming：大規(guī)模流式數(shù)據(jù)處理的新貴[J]. 程序員， 2014（2）：44-47.

[10] NEUMEYER L， ROBBINS B， NAIR A， et al. S4：distributed stream computing platform[C].IEEE International Conference on Data Mining Workshops，IEEE Computer Society， 2010：170-177.

[11] 吳媛，李雄德， 陳正軍. 信息供需互助平臺中智能撮合算法研究與設計[J]. 中國陶瓷， 2009（4）：36-38.

[12] 唐亮貴，李雙慶， 程代杰. 基于多主體的撮合交易模型及算法研究[J]. 計算機工程與應用， 2003， 39（23）：145-147.

[13] 李世梁.實時全額支付系統(tǒng)中基于基本環(huán)的高效多邊撮合算法分析和設計[J]. 計算機應用與軟件， 2016， 33（9）：296-300.

[14] 佚名.大數(shù)據(jù)時代[J]. 中國電子科學研究院學報， 2013， 8（1）：27-31.

[15] S GUPTA. Learning real-time processing with spark streaming[EB/OL].http：//www.bokus.com/.

[16] CARLSON J L. Redis in action[J]. Media，johnwiley， 2013（3）：157-159.

[17] 尹寶才， 王文通， 王立春. 深度學習研究綜述[J]. 北京工業(yè)大學學報， 2015（1）：48-59.endprint