作者簡介

小白，攜程算法工程師，關(guān)注營銷定價領(lǐng)域。

攜程火車票部門為解決智行酒店商戶側(cè)AB實驗中，預(yù)實驗分流中遇到的分流不均、分流組流量交叉問題，提出了一種用于非用戶端AB實驗的分流算法，該算法通過優(yōu)化的隨機抽樣模塊與貪心交換模塊，保證實驗組之間多指標(biāo)的相似性；通過圖算法模塊，降低實驗組之間的流量交叉。通過實證分析，該算法一方面有效的提升了商戶端實驗在多指標(biāo)下的分流效率；另一方面，相比于使用先驗知識進行分流，顯著降低了實驗組之間的流量交叉。

一、背景介紹

1.1 非用戶端AB實驗簡述

在互聯(lián)網(wǎng)行業(yè)中，AB實驗作為效果評估和策略迭代的黃金標(biāo)準(zhǔn)，已成為驅(qū)動業(yè)務(wù)決策的核心工具。通過對比實驗組與對照組在目標(biāo)指標(biāo)上的差異，AB實驗?zāi)軌蚩茖W(xué)量化策略收益、降低決策風(fēng)險，因而廣泛應(yīng)用于推薦系統(tǒng)、搜索排序、廣告投放、用戶增長等關(guān)鍵場景。當(dāng)前行業(yè)實踐中的AB實驗，絕大多數(shù)以用戶為分流單位，即基于用戶唯一標(biāo)識（如UserID、設(shè)備ID）進行哈希取模或分層隨機，確保用戶流量在實驗組與對照組之間均勻分配，同時滿足用戶維度的互斥性與獨立性。

然而，隨著業(yè)務(wù)場景的復(fù)雜化，非用戶維度的實驗需求逐漸凸顯。例如，在電商場景中，針對商品優(yōu)惠額度的策略優(yōu)化實驗，其核心實驗對象并非用戶，而是商品本身——需要將商品劃分為不同實驗組，測試不同優(yōu)惠策略對商品銷量的影響；在商戶營銷活動場景，典型如“裂變”類營銷活動，其不適合對同一個社交圈（如學(xué)校、商業(yè)區(qū)、城市）內(nèi)的用戶施加不同的營銷策略，因此活動主體和分流單位是商戶，需要進行非用戶端分流實驗，且分流過程中為了防止用戶之間相互影響，還需要盡可能避免參加相同活動的商戶同時被多個用戶看到的情況。

類似的場景還包括內(nèi)容池質(zhì)量評估、商家運營策略實驗、廣告創(chuàng)意效果對比等。此類實驗的分流主體從用戶轉(zhuǎn)向業(yè)務(wù)實體（如商品、內(nèi)容、廣告）。

1.2 非用戶端分流與用戶端分流異同

用戶和非用戶作為分流實體存在著核心差異：用戶實體數(shù)量級大，特征變化快，具有豐富的多樣性，且個體之間相互獨立；非用戶實體往往數(shù)量級較小，特征分布更加穩(wěn)定，也更加單一和集中，個體之間很可能存在關(guān)聯(lián)關(guān)系。這導(dǎo)致若直接對非用戶實體進行哈希分流，會面臨以下問題：

1）實驗隨機分流不均衡

以商品實驗為例，若直接對商品進行哈希隨機分流，由于商品特征的穩(wěn)定性和集中性，更容易導(dǎo)致實驗組與對照組的商品池在關(guān)鍵指標(biāo)上存在系統(tǒng)性偏差，一方面無法通過預(yù)留的AA校驗，另一方面導(dǎo)致實驗結(jié)果錯誤。例如，若在有關(guān)“營銷活動對GMV總量影響”的AB實驗中，在隨機分分流時高單價商品集中至實驗組，可能使實驗給出“營銷活動使GMV提升”的錯誤結(jié)論。對比體量更大、特征更多樣的用戶實體，非用戶實體更容易產(chǎn)生分流不均勻的情況。

2）實驗預(yù)分流與其穩(wěn)定性

大部分的用戶端實驗中，都通過在線流量隨機分流，依托于用戶群體的大體量和特征多樣性，不需要進行預(yù)分流。而非用戶實體的特征更為單一和穩(wěn)定，所以非用戶實驗通常要求實驗組與對照組在實驗期間更需要保持固定，以避免策略頻繁切換引入干擾，這就要求在實驗前對實體進行“預(yù)分流”。“預(yù)分流”需要具備一定的穩(wěn)定性，即在分流前（歷史時期）、分流后（實驗期間）的時間段內(nèi)，實驗組和對照組都應(yīng)該是相似的。

3）用戶維度流量交叉需嚴(yán)格約束

用戶端實驗中，用戶一般可以看做獨立的個體，但非用戶端實驗則不然，如電商平臺上的“鼠標(biāo)”和“鼠標(biāo)墊”顯然不具備獨立性，它們極易同時曝光給同一用戶群體，這就導(dǎo)致若商品“鼠標(biāo)”被分至實驗組，而“鼠標(biāo)墊”被分至對照組，且被同一用戶看到，這兩個商品之間就會互相影響，導(dǎo)致實驗結(jié)論可信度降低。因此，當(dāng)實驗對象與用戶存在多對多關(guān)聯(lián)時（用戶可瀏覽多個商品），需確保用戶盡可能少地同時暴露于實驗組與對照組。

上述問題使得傳統(tǒng)基于哈希的隨機分流方法難以直接適用：其無法主動調(diào)控實驗組與對照組的指標(biāo)相似性，也無法有效約束用戶維度的流量交叉。為使得這類需要對非用戶端進行的實驗擁有更高的置信度，解決其預(yù)分流難、分流均勻難、隔離流量的問題，攜程火車票算法團隊提出了一種面向非用戶維度實驗的分流算法，通過結(jié)合隨機抽樣、貪心算法、圖算法，實現(xiàn)實驗組與對照組的高效劃分。該算法能夠保證，在分流實驗組間指標(biāo)平衡的基礎(chǔ)上，顯著降低用戶維度的流量交叉率，提升分流效率和質(zhì)量，為復(fù)雜業(yè)務(wù)場景下的非用戶實驗提供可行的解決方案。

二、問題定義

給定N個待分流的非用戶實體集合，設(shè)其屬性空間由兩類特征構(gòu)成：

需將N個實體劃分為實驗組（Treatment Group）與對照組（Control Group），使得分組結(jié)果滿足如下要求：

2.1 分層指標(biāo)均衡

2.2 用戶流量隔離

對于與用戶行為存在關(guān)聯(lián)的實體（用戶可能同時訪問多個實體），需確保：

實體級互斥：同一實體僅能被分配至實驗組或?qū)φ战M；

三、方法介紹

為了達成上述需要達成的分組目標(biāo)，我們設(shè)計了三個獨立可插拔的算法模塊，并將其結(jié)合作為最終的分流算法。

• 為實現(xiàn)整體指標(biāo)的均衡，使用貪心交換算法，以一個分組的可行解作為起點，不斷貪心交換樣本，使得不同分組的指標(biāo)變量的最大均值相對差異不斷變小，直到滿足預(yù)設(shè)的差異水平。
• 為實現(xiàn)分層指標(biāo)均衡，并加快貪心算法的收斂速度，使用分區(qū)隨機抽樣算法為貪心算法生成初始可行解，使初始解中不同分層的重要指標(biāo)盡可能均衡，實驗組和對照組之間的最大均值相對差異滿足一個更加寬泛的差異水平條件。
• 為實現(xiàn)用戶流量隔離，引入圖的社區(qū)發(fā)現(xiàn)算法，在算法中額外給定用戶和分流實體的歷史交叉信息（如用戶歷史瀏覽的商品，下文用uv數(shù)據(jù)代指該信息），將交叉信息抽象為圖，將原分流單位打包為新的分流單位，讓新的分流實體之間流量交叉盡可能隔離。

下文將依次介紹算法的不同部分，給出算法細節(jié)。

3.1 分區(qū)隨機抽樣算法

在非用戶分流場景中，直接應(yīng)用貪心算法從零開始構(gòu)建實驗組與對照組，可能因初始狀態(tài)隨機性導(dǎo)致收斂速度慢或陷入局部最優(yōu)。為此，我們基于分層抽樣，提出一種優(yōu)化的隨機抽樣初始化方法，算法要達成的核心目標(biāo)是：

算法輸入

核心步驟

步驟4：跨子層隨機組合候選分組

分桶完成后，通過組合不同子層的同序號桶，生成分組結(jié)果。

圖：分區(qū)隨機抽樣算法

3.2 貪心交換算法

在優(yōu)化隨機抽樣生成初始分組后，為進一步降低實驗組與對照組的指標(biāo)差異，需引入貪心交換算法對分組進行精細化調(diào)整。該算法以初始解為起點，通過局部樣本交換逐步逼近全局最優(yōu)解，其核心流程如下：

步驟1：基于分流算法的初始解構(gòu)建

基于隨機分流算法輸出的初始分組（實驗組與對照組），其已通過分層分桶策略確保在分組變量的各組合分區(qū)內(nèi)指標(biāo)分布相對均衡。這一設(shè)計減少了后續(xù)貪心算法的搜索空間，避免算法陷入低效的隨機游走。

步驟2：預(yù)計算與實體分桶

算法迭代開始前，先預(yù)計算兩組在各指標(biāo)變量上的均值（或總值）及相對差距，并將兩組樣本劃分為多個交換桶（也可以根據(jù)給定的分組變量指定交換桶）。交換限制為僅允許同一桶內(nèi)的樣本對進行交換，例如同一商品類目下的實驗組商品只能與同類目的對照組商品交換。此舉通過提前計算指標(biāo)和限制交換樣本的搜索空間，降低了計算復(fù)雜度的同時，維持分區(qū)的原有均衡性。

步驟3：迭代式貪心交換算法進入貪心循環(huán)迭代階段，每輪迭代包含以下操作：

• 候選交換對生成：遍歷所有交換桶，在每個桶內(nèi)枚舉實驗組與對照組樣本的兩兩組合，計算若交換二者后各指標(biāo)變量最大相對差距的變化量，將其作為交換的“收益”。
• 擇優(yōu)交換：從所有候選對中篩選能使相對差距減小的幅度最大，即上文“收益”最大的最優(yōu)樣本對（若同時存在多對，隨機選擇其一），執(zhí)行交換并更新分組狀態(tài)；
• 加速策略：為減少計算量，每輪僅計算部分候選樣本對交換后的收益如每一次迭代中最多比較K個樣本對，若超過該限度，則使用當(dāng)前的局部最優(yōu)樣本對強制進入下一次迭代。

步驟4：終止條件與結(jié)果輸出迭代持續(xù)至滿足以下任一條件則終止：

• 收斂成功：所有指標(biāo)變量的最大相對差距小于給定閾值
• 陷入局部最優(yōu)：當(dāng)前輪次未找到收益超過一定限度的有效交換對。注意，若一輪迭代搜索K個樣本對后沒有找到收益滿足要求的可交換樣本對，則算法應(yīng)無視單次迭代樣本對數(shù)量的限制，繼續(xù)進行下去。
• 迭代次數(shù)限制：算法達到最大迭代次數(shù)。

最終輸出最后一次迭代的分組結(jié)果，確保即使未完全收斂，仍能提供相較于初始解更優(yōu)的可行方案。算法的具體流程如圖所示：

圖：貪心交換算法

3.3 降低流量交叉的圖貪心分流算法

為在進一步降低用戶維度的流量交叉，在貪心交換算法中引入圖的社區(qū)發(fā)現(xiàn)算法，通過重構(gòu)分流單位實現(xiàn)“組內(nèi)高內(nèi)聚、組間低耦合”的流量隔離。

社區(qū)發(fā)現(xiàn)算法（Community Detection）是一種圖分析技術(shù)，旨在將圖中的節(jié)點劃分為若干“社區(qū)”，使得同一社區(qū)內(nèi)的節(jié)點間連接緊密（邊權(quán)重高），而不同社區(qū)間的節(jié)點連接稀疏。在此場景中，該算法通過用戶行為數(shù)據(jù)自動識別出高頻共現(xiàn)的實體群落（例如常被同一用戶瀏覽的商品組合、或內(nèi)容主題高度相關(guān)的短視頻），本質(zhì)上將“用戶行為強關(guān)聯(lián)”的實體打包為更大的分流單位“社區(qū)”。

其降低流量交叉的核心邏輯在于：若兩個實體常被同一用戶訪問，則將其劃分至同一社區(qū)，并確保該社區(qū)整體被分配至實驗組或?qū)φ战M。當(dāng)用戶訪問其中一個實體時，由于同社區(qū)實體已被集中分配，其接觸另一實體時仍處于同一分組內(nèi)，從而盡可能減少跨組曝光的情況發(fā)生。

圖貪心分流算法的其核心步驟如下：

步驟1：基于用戶行為的圖結(jié)構(gòu)建模

以歷史用戶-實體的曝光數(shù)據(jù)數(shù)據(jù)為輸入，構(gòu)建以原始分流實體為節(jié)點（如商品的唯一標(biāo)識ID）、以用戶交叉曝光關(guān)系為邊的加權(quán)圖：

• 圖規(guī)?？刂?/span>：為避免圖結(jié)構(gòu)過于稠密影響圖算法執(zhí)行效率，通過設(shè)定邊權(quán)重閾值（僅保留權(quán)值較大的邊）或隨機采樣（隨機保留部分實體的邊）。

步驟2：社區(qū)發(fā)現(xiàn)與分流單位重構(gòu)

基于圖結(jié)構(gòu)，采用社區(qū)發(fā)現(xiàn)算法（本文選用Louvain算法）將原始實體聚類為新的分流單位：

• 社區(qū)劃分：算法自動識別用戶共現(xiàn)密集的實體群落，使得同一社區(qū)內(nèi)的實體被同一用戶訪問的概率較高，而跨社區(qū)實體共現(xiàn)概率較低。

步驟3：基于新單位的貪心分流

將社區(qū)映射后的新分流單位作為實體，執(zhí)行前述貪心交換算法流程：

• 分流實體還原：若社區(qū)單位被分配至實驗組，則其包含的所有原始實體均歸屬實驗組；對照組同理。因社區(qū)劃分互斥，原始實體僅屬于唯一社區(qū)，故最終分組天然滿足原始實體的互斥要求，作為分流結(jié)果輸出。

總的分流算法示意圖如下，其中分區(qū)隨機抽樣算法被包含在貪心交換算法中，為其提供初始解。

圖：圖貪心分流算法流程

四、實證分析

4.1 對比方法與業(yè)務(wù)背景

對于上述算法，我們將其落地成為通用工具，并對其基于實際業(yè)務(wù)場景進行了全面評測，證明了其解決非用戶端分流問題的可行性。

用于評測和應(yīng)用的業(yè)務(wù)背景是：智行平臺希望針對在該平臺的部分中低價位酒店商戶，參加不同的營銷策略開展AB實驗，因此，需要對部分中低價格段的酒店進行分流。這部分酒店存在著如下的特點：

• 酒店數(shù)量級不超過一百萬，且銷量和曝光的馬太效應(yīng)較為明顯，酒店特征分布穩(wěn)定且單一，不均衡。
• 同一地區(qū)的酒店之間存在著嚴(yán)重的用戶流量交叉，直接用酒店隨機分流會導(dǎo)致實驗組對照組嚴(yán)重不獨立。
• 無論以酒店，還是以交叉程度較低的商業(yè)區(qū)、城市為單位進行預(yù)隨機分流，隨機多次都難以滿足實驗組對照組劃分的相似性和穩(wěn)定性。

因此，我們引入圖貪心分流算法應(yīng)用于該業(yè)務(wù)場景進行分流。在該酒店商戶營銷策略AB實驗場景中，我們需要對比三類算法分流算法的分流效果：

• 圖貪心分流（本文提出的新方法）：基于用戶瀏覽行為構(gòu)建酒店共現(xiàn)圖，通過社區(qū)發(fā)現(xiàn)將酒店打包為群落，對群落執(zhí)行分層初始化與貪心交換。在該實證分析中，為均衡算法效率，只保留了圖中權(quán)重Top 40%的邊來構(gòu)建圖，其余邊被忽略。
• 有先驗知識的貪心分流（不使用圖算法，而使用先驗知識生成新分流實體）：為了降低隨機分組的流量交叉，同時加快分流效率，基于“同一商業(yè)區(qū)酒店用戶重疊較低”的先驗知識，將酒店按商業(yè)區(qū)打包后執(zhí)行貪心交換，直至實驗對照組的指標(biāo)變量差異達到預(yù)設(shè)的標(biāo)準(zhǔn)以下。
• 有先驗知識的隨機分流（此前內(nèi)部AB實驗采用的分流方式）：為了減少流量交叉，同樣適用前面的先驗知識，酒店按商業(yè)區(qū)打包，而后進行隨機分流，直至指標(biāo)差異達到對應(yīng)限度。在本數(shù)據(jù)環(huán)境下，分流效率過低，無法在有限嘗試次數(shù)內(nèi)內(nèi)獲得有效結(jié)果，至少需要重新隨機檢驗200次以上，才有一次可用結(jié)果，絕大部分嘗試既無法滿足誤差限度需要，也無法通過t檢驗。

在展示對比結(jié)果前，我們已經(jīng)可以得出結(jié)論：貪心交換的引入已經(jīng)可以大幅度提高了分流的效率，通過隨機劃分難以實現(xiàn)劃分出變量分布均衡的實驗組和對照組。因此，下文的內(nèi)容更著重于對比使用“先驗知識”和使用“圖算法”后再執(zhí)行貪心交換的結(jié)果差異。

4.2 效果評估維度與指標(biāo)定義

實證分析要從兩方面對比不同的算法分流方式，一方面是流量交叉，另一方面是分流精度。每個方面都有“算法指標(biāo)”和“實證指標(biāo)”兩個指標(biāo)，前者是傾向于算法角度的指標(biāo)（如分類模型的AUC），后者則傾向于業(yè)務(wù)角度的指標(biāo)（如模型上線后的用戶轉(zhuǎn)化率）。

4.2.1 流量交叉評價指標(biāo)

1）算法指標(biāo)——模塊度

想要計算模塊度，需要輸入一張完整的有向無權(quán)圖，和社區(qū)發(fā)現(xiàn)的結(jié)果，即將分流的結(jié)果和用戶的歷史流量數(shù)據(jù)輸入即可計算。

2）實證指標(biāo)——用戶端流量交叉率

我們統(tǒng)計分流時間點前每日實驗組和對照組的用戶重疊比例：

UV交叉率 = 實驗組與對照組當(dāng)日重疊UV數(shù) / 實驗組當(dāng)日總UV數(shù)

最終取實驗前30天的交叉率均值，作為用戶端流量交叉率的指標(biāo)。

4.2.2 分流精度

1）算法指標(biāo)——最大相對差異：

將實驗組和對照組在所有指標(biāo)變量上的最大相對差異D作為“分流精度”，來評價分流算法的分流精度，具體定義在2.1節(jié)中已提到過。該值越低，說明指標(biāo)之間越接近，表示分流精度越高。下述實證分析使用的是基于“總值”的相對差異。

2）實證指標(biāo)——AA校驗通過率

針對實驗組與對照組分多個時間點，選擇部分重要指標(biāo)變量，進行雙樣本T檢驗，若p-value≥0.05則認(rèn)為該指標(biāo)無顯著差異。統(tǒng)計：

分流前t檢驗通過率：分流數(shù)據(jù)時間點7 & 14 & 30 & 60天內(nèi)，兩組分流結(jié)果中所有指標(biāo)變量均通過T檢驗，則視為本次分流“通過”，反之視為不通過，多次反復(fù)分流計算其通過概率。該值是為了刻畫分流結(jié)果在實驗前的一段時間內(nèi)是不是相似。

分流后t檢驗通過率：分流數(shù)據(jù)時間點后14天內(nèi)，兩組分流結(jié)果中所有指標(biāo)變量均通過T檢驗，則視為本次分流“通過”，反之視為不通過，同樣多次反復(fù)分流計算其通過概率。假設(shè)分流后AB實驗的周期是14天，該值是為了刻畫分流結(jié)果在實驗中的一段時間內(nèi)是不是相似。

4.3 對比結(jié)果與分析

4.3.1 算法指標(biāo)評估

圖貪心分流和先驗隨機分流的算法指標(biāo)的對比如下表所示：

表：圖貪心分流VS先驗隨機分流——算法指標(biāo)對比

從通過率（滿足精度要求的分流次數(shù)占比）來看，先驗的貪心分流有著40%的通過率，而使用了圖算法的貪心分流則可以讓分流通過率提升到90%以上。

從通過樣本的分流精度來看，圖算法打包原始酒店為新個體的方式的確對最終精度產(chǎn)生的影響幅度有限。從表中看，分流精度和模塊度二者不存在嚴(yán)格的相關(guān)性，通過與未通過樣本的模塊度都較為接近，這說明分流結(jié)果的流量交叉程度主要和貪心交換前的預(yù)處理相關(guān)。

分析流量交叉情況，經(jīng)過額外的離線測算可知，若不使用任何先驗知識直接進行隨機分流，分流結(jié)果的模塊度在0左右（由于該方法也難以得到滿足精度要求的結(jié)果，同時也無法避免流量交叉，因此此前的AB實驗也不采用該方法，故精度評測結(jié)果沒有在表中給出）；而使用了“不同商業(yè)區(qū)之間的流量交叉較低”先驗知識進行分流的分流算法，能達到0.1左右的模塊度；進而使用圖算法優(yōu)化分流，則能讓模塊度提升到0.3。

總的來講，圖算法在不影響最終分流精度的情況下，大幅度提升了分流通過率與模塊度。

4.3.2 實證指標(biāo)評估

表：圖貪心分流VS先驗隨機分流——實證指標(biāo)對比

圖貪心分流和先驗貪心分流的實證指標(biāo)對比見上表。其中“分流前”指分流數(shù)據(jù)時間點前7、14、30、60天共四個時間點，對這四個時間點業(yè)務(wù)上關(guān)心的核心酒店特征進行抽取，依次進行t檢驗；“分流后”指分流數(shù)據(jù)時間后14天的時間點，進行同樣的特征抽取，進行T檢驗。

分析T檢驗的結(jié)果，兩種分流后的T檢驗通過率都較高，但分流前顯然圖貪心分流更好，這說明圖算法相對于使用先驗知識，有更好的穩(wěn)定性；分析用戶交叉率，圖算法打包分流實體相對于先驗知識打包分流實體，可以將uv交叉率從60%降低至40%。

總的來說，圖算法的分流結(jié)果相對于先驗知識分流具備更好的穩(wěn)定性，以及更小的用戶流量交叉。

五、總結(jié)與展望

5.1 問題定義與場景分析

針對非用戶端AB實驗場景中的分流問題，我們明確定義了其技術(shù)挑戰(zhàn)的核心形式：如何在多實驗并行、流量有限的情況下，確保實驗組與對照組的分流結(jié)果既滿足業(yè)務(wù)指標(biāo)分布的相似性，又能最大限度降低流量交叉干擾。為此，我們提出從兩方面衡量分流效果：指標(biāo)分布相似度與流量交叉程度。這一問題的定義，為后續(xù)方法設(shè)計與效果驗證提供了明確的優(yōu)化目標(biāo)。

5.2 圖貪心分流算法的提出與實現(xiàn)

為解決上述問題，我們提出了一種創(chuàng)新性的圖貪心分流算法，其核心設(shè)計包括：優(yōu)化的隨機分流模塊、貪心分流模塊、圖計算法模塊，三個模塊解決了上述問題，且支持靈活插拔，與特定的業(yè)務(wù)場景適配。

5.3 實證分析與效果驗證

通過對比圖貪心算法、先驗知識貪心算法、先驗知識隨機分流算法的實驗結(jié)果，我們可以得出結(jié)論：相對于隨機劃分，貪心交換算法大幅度提高了分流的效率，圖算法的引入則在不影響最終分流精度的情況下，進一步降低了流量交叉。

5.4 未來研究方向

盡管當(dāng)前方法已取得顯著效果，仍有需要方向值得進一步探索，如：uv數(shù)據(jù)映射為圖的方法，圖算法與貪心算法精度與效率的平衡，分流精度、流量交叉、分區(qū)均勻性的權(quán)衡、算法進一步的部署和平臺化。