作者簡介

小白，攜程算法工程師，關注營銷定價領域。

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

一、背景介紹

1.1 非用戶端AB實驗簡述

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

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

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

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

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

1）實驗隨機分流不均衡

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

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

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

3）用戶維度流量交叉需嚴格約束

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

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

二、問題定義

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

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

2.1 分層指標均衡

2.2 用戶流量隔離

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

實體級互斥：同一實體僅能被分配至實驗組或對照組；

三、方法介紹

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

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

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

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

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

算法輸入

核心步驟

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

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

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

3.2 貪心交換算法

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

步驟1：基于分流算法的初始解構建

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

步驟2：預計算與實體分桶

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

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

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

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

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

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

圖：貪心交換算法

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

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

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

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

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

步驟1：基于用戶行為的圖結構建模

以歷史用戶-實體的曝光數據數據為輸入，構建以原始分流實體為節(jié)點（如商品的唯一標識ID）、以用戶交叉曝光關系為邊的加權圖：

• 圖規(guī)模控制：為避免圖結構過于稠密影響圖算法執(zhí)行效率，通過設定邊權重閾值（僅保留權值較大的邊）或隨機采樣（隨機保留部分實體的邊）。

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

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

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

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

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

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

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

圖：圖貪心分流算法流程

四、實證分析

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

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

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

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

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

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

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

4.2 效果評估維度與指標定義

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

4.2.1 流量交叉評價指標

1）算法指標——模塊度

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

2）實證指標——用戶端流量交叉率

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

UV交叉率 = 實驗組與對照組當日重疊UV數 / 實驗組當日總UV數

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

4.2.2 分流精度

1）算法指標——最大相對差異：

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

2）實證指標——AA校驗通過率

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

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

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

4.3 對比結果與分析

4.3.1 算法指標評估

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

表：圖貪心分流VS先驗隨機分流——算法指標對比

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

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

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

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

4.3.2 實證指標評估

表：圖貪心分流VS先驗隨機分流——實證指標對比

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

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

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

五、總結與展望

5.1 問題定義與場景分析

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

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

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

5.3 實證分析與效果驗證

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

5.4 未來研究方向

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