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

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

（中國民航大學(xué)，天津 300300）

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

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

（1）傳統(tǒng)航線收益評價(jià)方法[2]，其核心思想是只考慮單航線歷史的收益，航線收益好，公司就繼續(xù)經(jīng)營甚至投放更多的運(yùn)力擴(kuò)大經(jīng)營規(guī)模，反之，減少運(yùn)力投放，縮小經(jīng)營規(guī)模；

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

（3）設(shè)計(jì)融入航線運(yùn)營成本的多指標(biāo)決策問題模型[4]。

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

1 基于旅客出行意圖發(fā)現(xiàn)的航線價(jià)值計(jì)算

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

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

1.2 問題建模

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

1.3 航線價(jià)值的計(jì)算方法

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

其中：

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

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

u—表示具體某個(gè)旅客；

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

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

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

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

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

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

1.4 模型優(yōu)化及參數(shù)求解

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

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

1.4.1 基于Map-reduce和LDA的航線價(jià)值計(jì)算方法

（1）輸入航班數(shù)據(jù)；

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

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

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

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

1.4.2 基于Map-reduce的民航旅客訂票日志數(shù)據(jù)處理

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

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

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

學(xué)習(xí)過程：給定一個(gè)旅客集合，旅客乘坐航線是可以觀察到的已知變量，α和β根據(jù)經(jīng)驗(yàn)給定，其他的變量Z（出行意圖）、θ和φ都是未知的隱含變量，需要根據(jù)觀察到的變量來學(xué)習(xí)估計(jì)的。根據(jù)LDA的圖模型，可以寫出所有變量的聯(lián)合分布：

其中：

圖1 Map-reduce處理過程

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

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

因?yàn)橐鈭D分布θ，確定具體意圖，且β產(chǎn)生的航線分布φ，確定具體航線，所以式（2）等價(jià)于式（3）所表達(dá)的聯(lián)合概率分布：

公式的物理含義為：第1項(xiàng)因子表示的是根據(jù)確定的意圖和航線分布的先驗(yàn)分布參數(shù)采樣航線的過程，第2項(xiàng)因子是根據(jù)意圖分布的先驗(yàn)分布參數(shù)采樣意圖的過程，這兩項(xiàng)因子是需要計(jì)算的兩個(gè)未知參數(shù)。

根據(jù)推算得到P(,)的聯(lián)合分布結(jié)果為：

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

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

經(jīng)推導(dǎo)得到結(jié)果：

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

2 試驗(yàn)與分析

2.1 數(shù)據(jù)及其預(yù)處理結(jié)果

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

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

表1 經(jīng)過Map-reduce預(yù)處理過的數(shù)據(jù)示例

2.2 傳統(tǒng)方法

基于航班次數(shù)統(tǒng)計(jì)的航線價(jià)值計(jì)算方法：統(tǒng)計(jì)各航線的旅客乘坐次數(shù)，進(jìn)而計(jì)算P(a)。

2.3 評價(jià)指標(biāo)

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

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

當(dāng)集合A，B都為空時(shí)，J(A,B)定義為1。

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

2.4 實(shí)驗(yàn)設(shè)置

（1）參數(shù) α， β 的設(shè)置

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

（2）參數(shù)k的設(shè)置

k值為主題數(shù)，其值會影響θ矩陣的列數(shù)和φ矩陣的行數(shù)，取值范圍根據(jù)內(nèi)存大小而定，實(shí)驗(yàn)中取值為 ：10、20、50、80、100。

2.5 實(shí)驗(yàn)結(jié)果

（1）熱點(diǎn)航線挖掘

以航線潛在價(jià)值（預(yù)測序列）為鍵進(jìn)行排序得到表2，并與其對應(yīng)真實(shí)航線乘坐次數(shù)進(jìn)行對比，可以發(fā)現(xiàn)兩者并不完全正比，說明航線潛在價(jià)值會受其他因素影響，傳統(tǒng)算法具有一定局限性。

（2）性能對比

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

2.6 實(shí)驗(yàn)參數(shù)分析

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

表2 航線潛在價(jià)值排名top20

表3 實(shí)驗(yàn)性能對比

通過實(shí)驗(yàn)數(shù)據(jù)發(fā)現(xiàn)，不同范圍內(nèi)算法性能也不一樣，α、β、k三者同時(shí)影響航線價(jià)值?？梢钥闯?，k=10的記錄占top rank的大部分（實(shí)驗(yàn)中，k=10、50、80、100），意味著旅客出行的潛在意圖的數(shù)量占10個(gè)的概率極大。

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

表5 性能評估, 旅客乘坐次數(shù)5次以上

3 實(shí)驗(yàn)結(jié)果分析

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

4 結(jié)束語

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