基于旅客出行意圖的潛在高價值航線挖掘

盧 敏，李照宇，劉康超，李 純

（中國民航大學，天津 300300）

我國雖然已形成覆蓋沿海發達城市以及重要省會城市的20家區域性樞紐空港，但航線布局呈東密西疏、沿海密內陸疏的發展態勢，且航空運輸干支網絡缺乏有效銜接，使得各個航線不能充分的體現其價值，也無法發揮樞紐機場的中轉功能和航空網絡的整體效能[1]。因此，如何幫助航空公司合理安排航班航線，減少各航空公司間航班的重疊率，成為航空公司收益管理的重要組成部分。

民航航線挖掘任務是發現具有潛在高收益的航線，進而為航空公司航線開辟提供理論依據，其核心問題是如何準確評估航線的價值。已有的方法可以概括為3大類：

（1）傳統航線收益評價方法[2]，其核心思想是只考慮單航線歷史的收益，航線收益好，公司就繼續經營甚至投放更多的運力擴大經營規模，反之，減少運力投放，縮小經營規模；

（2）在航線收益基礎上，融入起飛機場和目的機場的經濟特性等知識[3]；

（3）設計融入航線運營成本的多指標決策問題模型[4]。

由于旅客乘坐的航線本質由旅客的出行需求決定，為此本文提出基于旅客出行意圖發現的航線價值計算方法。其核心初衷是：旅客出行受出行目的、季節性、年齡段、出差、旅游等因素的影響，而上述因素最終表現為旅客出行意圖，因此航線價值較大程度上取決于旅客的出行意圖。

1 基于旅客出行意圖發現的航線價值計算

1.1 LDA算法（定義）及其核心思想

概率主題模型最早起源于潛在語義分析（LSI，Latent semantic Indexing）[5], 旨在解決信息檢索中面臨的一詞多義和多詞同義的語義問題。在此基礎之上，研究者提出更多的概率主題模型，其中經典的概率主題模型是潛在狄利克雷分配（LDA）[6]。它可以將文檔集中每篇文檔的主題以概率分布的形式給出，從而通過分析一些文檔抽取出它們的主題（分布）出來后，便可以根據主題（分布）進行主題聚類或文本分類。同時，它是一種典型的詞袋模型，即一篇文檔是由一組詞構成，詞與詞之間沒有先后順序的關系。針對詞條件獨立的約束，研究者分別提出考慮syntax的主題模型[7]、引入word correlation的主題模型[8]以及term selection的主題模型[9]。針對文檔相互獨立的假設，由于很多實際應用中文檔間存在引用和鏈接關系，研究者分別提出link-based LDA[10]以及author-topic LDA[11]。針對主題相互獨立的約束，提出 topic-link LDA[12]、correlated LDA[13]、hierarchy LDA[14]等。針對沒有充分利用文檔標注信息，研究者提出supervised LDA[15]。除上述研究之外，研究者還研究了大規模數據上的LDA近似計算及推理模型[16]，以及將LDA模型應用于社交網絡分析[17-18]。

1.2 問題建模

采用P(a)描述航線a未來旅客的乘坐概率，取值越大表示航線潛在價值越高，其中航線是由起始機場和目的機場決定的，如PEK#SHA表示北京PEK到上海虹橋SHA的航線。航線的價值體現為現在和將來選擇乘坐該航線上航班的旅客數量，而航班記錄僅是由已乘坐的旅客組成，很多旅客當前未乘坐該航線上航班，并不代表這些旅客將來不會選擇該航線，故而不能根據航班記錄簡單的統計直接得出結論。因此，航線a的潛在價值應該為所有旅客乘坐航線a的概率和，即：P(a)=∑up(a,u)。

1.3 航線價值的計算方法

根據用戶出行意圖和貝葉斯全概率公式，將航線概率P(a)展開為：

其中：

a—表示航線，如PEK#SHA表示北京到上海的航線；

P(a)—表示航線 a的價值；

u—表示具體某個旅客；

P(u)—表示用戶乘坐所有航線的次數，即在航班記錄中的乘坐次數，也是用戶的重要度；

zu—表示用戶u的潛在出行意圖z，在LDA中，每位旅客都有對應的出行意圖z∈{1, 2, …, K}，即LDA中總有K個出行意圖，每條航線只能選擇其中一個意圖，意圖標號依次是1, 2, …,K；

P(a|zu)—表示潛在出行意圖zu下的航線a分布；P(zu|u)—表示用戶u的潛在出行意圖zu分布。

公式的物理含義為：用戶u乘坐航線a的概率P(a,u)，直接由旅客出行意圖影響。由于旅客的出行意圖zu是不可見的，使用LDA主題模型從預處理過的民航旅客訂票日志中挖掘，并根據貝葉斯全概率公式P(a,u)= ∑zup(a, zu,u)和條件獨立的假設，進一步展開求解p(a, zu,u)=P(zu|u)P(u)。

旅客u在潛在出行意圖zu下選擇航線a的概率p(a, zu,u)本質是兩階段形成的：旅客u首先確定潛在出行意圖zu，然后才會根據出行意圖再選擇航線a。在此基礎之上，使用貝葉斯條件概率公式將上述概率進一步展開，則p(a, zu,u)=p(a|zu)p(zu|u)。其中，p(zu|u)表示用戶u選擇潛在出行意圖zu的可能性，而p(a|zu)為當前意圖zu下選擇航線a的概率。

基于上述假設，式(1)中需要求解的是P(u),p(a|zu)和p(zu|u)，其中，p(a|zu)和p(zu|u)可通過主題模型LDA進行挖掘。

1.4 模型優化及參數求解

為了快速求解參數P(u),p(a|zu)和p(zu|u)，提出基于Map-reduce和LDA的航線價值計算方法。

Map-reduce是一種編程模型，用于大規模數據集（大于1 TB）的并行運算。概念“Map（映射）”和“Reduce（歸約）”，是它們的主要思想，都是從函數式編程語言和矢量編程語言里借來的特性。它極大地方便了編程人員在不會分布式并行編程的情況下，將自己的程序運行在分布式系統上。 當前的軟件實現是指定一個Map（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定并發的Reduce（歸約）函數，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。

1.4.1 基于Map-reduce和LDA的航線價值計算方法

（1）輸入航班數據；

（2）Map處理：將乘客的每一條乘坐記錄單獨分割；

（3）reduce處理：以每一個乘客的id作為鍵，乘坐記錄作為值，將旅客所乘坐的所有航班的飛行航線篩選出來合并到一起；

（4）基于LDA的旅客出行意圖挖掘，計算p(a|zu)和p(zu|u)；

（5）根據公式(1)，計算航線乘坐概率P(a)。

1.4.2 基于Map-reduce的民航旅客訂票日志數據處理

民航旅客訂票日志（PNR）是旅客乘坐航班的信息，對于如此龐大的數據量，一般算法用于有限內存，難以得出LDA的數據源。Map-reduce是基于分布式的針對這種場景的算法，將航班數據文件切割成小段，再對其每一段進行運算，統計每位旅客乘坐的所有航線的集合，得出結果后以旅客身份證（加密）為鍵值進行歸并得到最終的LDA輸入數據源，即一行為一個旅客的所有乘坐記錄，而每一行內單個詞則是旅客的一次乘坐記錄，Map-reduce處理過程如圖1所示。

1.4.3 基于LDA的旅客出行意圖挖掘

LDA有兩個先驗參數α和β。參數α決定了旅客的意圖概率先驗分布，而參數β則描述某出行意圖下的航線概率先驗分布。最終通過LDA模型訓練得到旅客-意圖概率θ和意圖-航線概率φ。 用Gibbs采樣估計兩個未知參數，主要思想是貝葉斯估計。貝葉斯估計把待估計參數看作是服從某種先驗分布的隨機變量。

學習過程：給定一個旅客集合，旅客乘坐航線是可以觀察到的已知變量，α和β根據經驗給定，其他的變量Z（出行意圖）、θ和φ都是未知的隱含變量，需要根據觀察到的變量來學習估計的。根據LDA的圖模型，可以寫出所有變量的聯合分布：

其中：

圖1 Map-reduce處理過程

Zm,n—表示從意圖的多項分布?m取樣生成旅客m第n個可選航線的意圖；—表示從狄利克雷分布β中取樣生成意圖Zm,n對應的航線分布；

wm,n—表示旅客m最終選擇的航線n。

因為意圖分布θ，確定具體意圖，且β產生的航線分布φ，確定具體航線，所以式（2）等價于式（3）所表達的聯合概率分布：

公式的物理含義為：第1項因子表示的是根據確定的意圖和航線分布的先驗分布參數采樣航線的過程，第2項因子是根據意圖分布的先驗分布參數采樣意圖的過程，這兩項因子是需要計算的兩個未知參數。

根據推算得到P(,)的聯合分布結果為：

有了P(,)聯合分布，便可以通過聯合分布來計算在給定可觀測變量w下的隱變量z的條件分布（后驗分布）P(,)，進行貝葉斯分析。

先定義幾個變量：?i表示除去i的航線，。排除當前航線的意圖分配，即根據其他航線的意圖分配和觀察到的航線來計算當前航線的意圖的概率公式為：

經推導得到結果：

其中，是旅客m的意圖數向量，是意圖k下的航線項數向量。Gibbs Sampling通過求解出意圖分布和航線分布的后驗分布，從而成功解決意圖分布和航線分布這兩參數未知的問題。

2 試驗與分析

2.1 數據及其預處理結果

對中國民航信息股份有限公司（TravelSKY Technology Limited）2010—2011年共計48 G的航班記錄做預處理，將乘坐次數5次和10次以上的旅客記錄借助Map-reduce算法在Hadoop分布式平臺上分別篩選出來，然后以旅客身份證號（加密）將篩選過的航班記錄的特征性信息（每個旅客乘坐過的航線）提取出來，整個文檔中每一行表示一個旅客，行中每一詞即是該旅客乘坐過的航班航線。

表1是原始數據經過Map-reduce平臺進行數據預處理，篩選出來的乘坐次數大于等于5次的航班記錄。第1行為旅客總數量，其他每行則是單一旅客乘坐過的航班航線記錄。每條航線記錄由6個大寫英文字符構成，前3個字符是出發機場三字碼，后3個則是到達機場三字碼，如NKGSZX表示從南京（NKG）到深圳（SZX）的航線。

表1 經過Map-reduce預處理過的數據示例

2.2 傳統方法

基于航班次數統計的航線價值計算方法：統計各航線的旅客乘坐次數，進而計算P(a)。

2.3 評價指標

Jaccard index又稱為Jaccard相似系數（Jaccard similarity coefficient），用于比較有限樣本集之間的相似性與差異性，Jaccard系數值越大，樣本相似度越高。

給定兩個集合A、B，Jaccard 系數定義為A與B交集的大小與A與B并集的大小的比值，定義如下：

當集合A，B都為空時，J(A,B)定義為1。

真實列表通過統計航線熱度（即航線乘坐次數）并倒序處理得到；而本文的航線預測列表則是首先通過公式（1）計算所有航線的價值，然后按照價值從高到低進行降序排列。為了更加彰顯算法的性能優勢，本文選擇排序列表的前TopK個航線計算Jaccard 系數。

2.4 實驗設置

（1）參數 α， β 的設置

α和β是LDA模型中旅客出行意圖分布θ和意圖下航線分布φ的先驗分布的先驗參數，這兩個參數的設置會影響θ和φ的生成，從而影響最終航線價值，α和β取值范圍皆為0.1～0.9。

（2）參數k的設置

k值為主題數，其值會影響θ矩陣的列數和φ矩陣的行數，取值范圍根據內存大小而定，實驗中取值為 ：10、20、50、80、100。

2.5 實驗結果

（1）熱點航線挖掘

以航線潛在價值（預測序列）為鍵進行排序得到表2，并與其對應真實航線乘坐次數進行對比，可以發現兩者并不完全正比，說明航線潛在價值會受其他因素影響，傳統算法具有一定局限性。

（2）性能對比

3組最優LDA模型與傳統算法的性能對比見表3，可以發現，與傳統算法相比，本文算法在top100內參數設置為α=0.8, β=0.3,k=20時指標提升2%，但在top500和top1 000范圍內性能與傳統算法相差無幾，可見這組模型在top100是性能表現最優。另外兩組模型類似，分別在top500和top1 000內達到性能最優，并且性能指標分別高于傳統算法2%和1%，說明LDA模型可以通過調整先驗參數可以挖掘不同范圍內比傳統算法更加有效的航線潛在價值。

2.6 實驗參數分析

進行多組實驗，將旅客乘坐次數大于10次以上和5次以上的篩選出來，作為LDA模型輸入，并對結果進行統計分析，得到top100、top500、top1 000下各模型的性能，如表4、表5所示。通過表4可以發現，本文算法在top100時能夠取得92%的Jacarrd相似系數，說明算法有效。

表2 航線潛在價值排名top20

表3 實驗性能對比

通過實驗數據發現，不同范圍內算法性能也不一樣，α、β、k三者同時影響航線價值。可以看出，k=10的記錄占top rank的大部分（實驗中，k=10、50、80、100），意味著旅客出行的潛在意圖的數量占10個的概率極大。

表4 性能評估，旅客乘坐次數為10次以上

表5 性能評估, 旅客乘坐次數5次以上

3 實驗結果分析

通過實驗可以發現，雖然傳統算法計算的航線價值實現簡單，并且準確度也不低，但其挖掘潛在價值的方式是基于航線的歷史使用情況，所以預測效果存在偏差；而LDA與傳統算法比較，準確度較高，能挖掘出更多的航線，并且算法模型可控，能夠適應旅客基于多種潛在出行意圖下的航線價值，同時具有可擴展性，可以通過詞擴充來提高航線的概率。綜上所述，LDA算法對于挖掘潛在模式具有一定的優勢。

4 結束語

本文從旅客出行行為的角度出發，將出行的不同因素歸結為出行意圖，從而利用出行意圖得到航線數據。（1）構建了面向大規模民航旅客訂票數據分析的Map-reduce平臺，處理中航信2010年和2011年的48 G訂票日志。（2）提出了基于旅客出行意圖發現的潛在高價值航線挖掘算法，通過挖掘在大規模旅客訂票日志的旅客出行意圖，計算航線未來潛在概率，豐富了機場的航線營銷和航空公司的航線網絡布局技術。（3）面向大規模的LDA主題模型構建方法，豐富了主題模型構建方法，可拓展到其他大規模數據的主題模型中。