一種融合個體屬性與社交關系的民航旅客價值度量方法

丁建立，劉曉慶，王家亮

1.中國民航大學 計算機科學與技術學院， 天津 300300 2.中國民航大學 天津市智能信號與圖像處理重點實驗室，天津 300300

隨著中國經濟的高速增長和國民收入的普遍提高，民航已不再僅僅是高收入人群的出行選擇，而是成為了一種大眾化、平民化的出行方式，民航和鐵路之間以及各航空公司之間的競爭日趨激烈。旅客資源的質量和數量成為航空公司致勝的關鍵，因此對旅客的細分和研究[1-4]成為當前的研究熱點。如何評估旅客價值、挖掘旅客關系及發現潛在高價值旅客，成為各航空公司搶奪旅客資源、提高核心競爭力的重要因素。

目前國內外對于民航旅客價值的研究主要集中在旅客個體價值層面，通過構建RFM(Recency, Frequency, Monetary)模型，根據旅客乘機時間近度系數R、乘機頻率F、花費金額M等特征，綜合計算旅客個體當前實際產生的價值[5]。為了挖掘旅客潛在價值，徐冰宇等提出構建旅客-航線二部圖[6]，基于隨機游走預測旅客未來出行概率，計算旅客潛在價值，但該模型僅考慮了旅客與航線的關系，忽略了旅客與旅客之間的相互影響。

2014年韓敏提出旅客價值排序Passenger Rank算法[7]，認為旅客除了個體價值外，其在社會網絡中的影響價值也應該考慮在內，該算法分別計算旅客獨飛價值和網絡價值并加權求和獲得旅客總價值，但其將獨飛價值作為旅客個體價值，而實際上旅客獨飛和共飛時自身消費的所有價值都應該屬于旅客個體價值，且在計算旅客網絡價值時，只考慮了旅客拓撲關系，忽略了旅客個體價值的差異導致的影響力差異，僅根據拓撲結構計算節點的網絡價值，不夠準確和全面。

目前國內外對于民航旅客關系網絡構建和旅客價值度量的研究存在以下問題：首先，民航旅客關系網絡的構建只局限于分析PNR(Passenger Name Record)數據，通過旅客同訂單關系，計算旅客間乘機關聯度以量化旅客關系[8]，而實際上，旅客間存在同一訂單的顯式關系和不同訂單的隱式關系，而不同訂單的隱式關系更具挖掘價值；其次，對旅客價值度量的方法過于簡單和單一，沒有綜合考慮旅客個體價值及其在社會關系網絡中的相互影響，而旅客價值既取決于個體價值又受其社交關系的影響。

為了解決以上問題，本文提出了一種融合個體屬性與社交關系的民航旅客價值度量方法，采用改進的RFMc(Recency, Frequency, Monetary, cab class)模型計算旅客個體價值并根據多關系評價(Multi-Relationship Evaluation,MRE)模型獲得旅客關系系數，構建旅客社交關系網絡，采用PageRank算法模型模擬旅客價值的網絡傳遞，最終實現可動態調整旅客個體價值和社交關系權重系數的旅客價值度量方法。

1 PageRank算法

PageRank算法最初用于解決頁面排序問題，它基于網頁之間的鏈接，根據全局網頁的鏈接情況計算各個網頁的重要程度。PageRank算法認為，在Web圖模型中一個網頁入鏈數量越多，則該網頁越重要；鏈入該網頁的網頁質量越高，則該網頁越重要。即網頁的質量由鏈入該網頁的數量和質量共同決定，這就是PageRank算法的數量和質量假設。

基于以上兩個假設，PageRank算法首先賦予所有網頁相同的初始重要性得分，其次通過公式ri+1=Mri迭代計算來更新每個網頁的PageRank得分，直到得分趨于穩定，獲得最終的重要性得分結果，其中r為網頁重要性得分向量，M為轉移概率矩陣。考慮到一些出度或入度為零的網頁(也稱為孤立網頁)，在原基礎上增加了阻尼系數α進行平滑處理，計算公式變為：ri+1=αMri+(1-α)e，其中e表示從任一網頁不經過鏈路而隨機跳到任意網頁的概率向量。這里假設，用戶以等概率跳轉到任意網頁節點，故e取值為[1/N,1/N,…,1/N]，其中N為網頁數量。

PageRank算法的提出吸引了一大批學者對其進行研究，為了解決PageRank算法忽略了主題相關性這一問題，斯坦福大學計算機科學系提出了Topic-sensitive PageRank算法[9]，提高了結果的相關性和主題性，使得用戶的個性化查詢得以實現。Kamvar等在2003年提出基于塊的個性化算法——BlockRank[10]，從更粗粒度的角度提高了算法計算效率。2009年一種基于主題級隨機游走的排序算法[11]被提出，解決了Topic-sensitive PageRank算法中需要預定義主題的問題。朱凡微等在2015年提出基于可用性Hub選擇的有計劃逼近完全個性化PageRank算法[12-13]，使得算法的計算效率和準確度得以動態調整。2016年魏巍等充分運用豐富的節點信息和網絡拓撲信息，提出了一種基于多源異構大規模圖結構的排序算法[14]，實現了半監督的圖節點排序。

PageRank算法的一系列改進使其在對圖結構重要節點排序方面具有高可擴展性和高有效性，因此也越來越廣泛地被應用于各研究領域，包括關鍵字提取[15-17]，作者、論文、期刊等網絡的節點重要性排序[18-20]等。

與網頁排序和其他圖節點排序相似，社交網絡中的旅客對于航空公司的價值，既包含其個體消費價值，又包含其社交關系價值，綜合旅客個體價值和社交關系的綜合度量才是對旅客價值的全面度量。況且，旅客成長趨勢受其所在社交網絡的影響，一個目前個體消費價值較低的旅客與高價值旅客關系越親密，其消費潛力越大，未來成長為高價值旅客可能性就越大。基于這一思想，本文充分挖掘旅客訂票和離港數據，通過RFMc模型計算旅客個體價值，并通過MRE模型分析旅客關系，構建民航旅客社交關系網絡，充分利用PageRank算法在大規模圖節點排序中的高效性和高可擴展性，設計實現民航旅客價值排序(Civil Aviation Passengers Value Rank, CAPV-Rank)算法，通過旅客間的價值傳遞模擬真實世界里旅客間的相互影響，并通過權重因子動態調整旅客個體價值和社交關系對旅客價值度量的權重系數，實現旅客個體價值計算、旅客網絡價值計算、融合旅客個體價值和網絡價值的混合計算等多種旅客價值度量模式，并根據旅客當前個體價值和社交關系預測旅客未來價值，進而挖掘潛在高價值旅客。

2 民航旅客社交關系網絡模型和CAPV-Rank算法

定義1民航旅客社交關系網絡：被定義為無向加權網絡G=(P,E,V,W)，P為所有旅客集合，E為所有旅客關系集合，V為所有旅客個體價值集合，W為所有關系權重集合。

民航旅客社交關系網絡模型包括旅客個體價值計算(RFMc)模型和多關系評價(MRE)模型，是旅客價值排序CAPV-Rank算法設計的基礎。

2.1 RFMc模型

定義2旅客個體價值：根據旅客個體消費數據計算旅客個體對于航空公司的價值，也指旅客對航空公司的利潤貢獻值。

傳統的RFM模型使用顧客消費近度、消費頻率和消費金額來綜合衡量顧客價值。從PNR數據中可以得到旅客的乘機金額、乘機時間和乘機頻率，針對民航的具體情況和特點，引入艙位等級C對應的票價折扣來表示旅客當次消費對航空公司的價值貢獻等級，提出RFMc模型計算民航旅客個體價值，其中MC為結合艙位等級計算得到的旅客相對乘機總金額。

2.1.1 旅客相對乘機總金額MC

考慮到民航的特殊性，不同的飛機艙位等級和折扣為航空公司帶來的實際盈利率不同，因此在分析旅客消費金額時應區別對待。

將艙位等級C(對應票價折扣)作為票價的權重計算旅客相對消費總金額MC：

(1)

式中：ci為旅客第i次乘機的票價折扣；mi為旅客第i次乘機的票價；k為購票次數。

2.1.2 乘機時間近度系數R

定義3最近乘機時間t：旅客最近一次乘機時間與當前時間(使用該模型計算旅客個體價值的時間)間隔。

定義4乘機平均周轉時間t0：旅客相鄰兩次乘機時間間隔的平均值:

(2)

式中：tsum為旅客總乘機次數；ti為旅客第i次和第i+1次乘機時間間隔；ts為預計算得到的全旅客集的平均周轉時間。

定義5乘機時間近度系數R：旅客再次乘機的可能性:

(3)

乘機平均周轉時間t0反應了旅客相鄰兩次乘機間隔的期望值，當最近乘機時間t小于等于平均周轉時間t0時，R值為1；當t大于t0時，旅客再次乘機的可能性逐漸降低，R值逐漸減少。

2.1.3 乘機頻率F

旅客乘機頻率F反應了旅客的活躍度和忠誠度，乘機頻率越大活躍度和忠誠度越高，則該旅客對于航空公司的價值越大。

綜上，將旅客相對乘機總金額、乘機時間近度系數和乘機頻率加權求和，獲得旅客個體價值v：

v=ω1MC+ω2R+ω3F

(4)

式中：ω1、ω2和ω3為各指標的權重系數。考慮到各個指標的測量尺度不同，需將MC、R和F標準化后再加權求和。

2.2 MRE模型

旅客同乘關系包含同訂單的顯式同乘關系和不同訂單的隱式同乘關系，MRE多關系評價模型融合訂單數據和離港數據，量化旅客顯隱式雙層關系并融合時間因素進行多關系的綜合評價。

2.2.1 旅客同訂單關系

定義6旅客同訂單關系：指同一訂單的旅客關系，旅客的一次同訂單關系包括該訂單的旅客數量、旅客艙位等級差和訂單生成日期。

根據PNR數據構建全體旅客的同訂單關系，用Pij表示旅客i和旅客j的同訂單關系序列，Pij[k]={|[ci[k]-cj[k]|,s[k],tp[k]}是序列中的第k項紀錄，表示旅客i和旅客j第k次同訂單的訂單數據，其中：s[k]為該訂單的旅客數量，tp[k]為該訂單生成日期，ci[k]為該訂單中旅客i的艙位等級(對應票價折扣)。

(5)

式中：sp[k]為旅客i和旅客j第k次同訂單關系得分。

2.2.2 旅客同乘關系

定義7同乘關系：指乘坐同一航班的旅客關系，包括碰巧同乘關系和約定同乘關系。一次同乘關系包括該次同乘的航班起飛日期、旅客座位距離、值機序號距離、艙位等級差等屬性。

據離港數據構建全體旅客的同乘關系，用Dij表示旅客i和旅客j的同乘關系序列，Dij[k]={|[dci[k]|,|dseat[k]|,|dclass[k]|,td[k]}是序列中的第k項紀錄，表示旅客i和旅客j第k次同乘時的航班數據，td[k]為該航班起飛日期，dci[k]為旅客i和旅客j的值機序號距離，dseat[k]為旅客i和旅客j航班座位的歐氏距離，dclass[k]為旅客i和旅客j的艙位等級差。

(6)

(7)

2.2.3 融入時間因素的多關系綜合評價

旅客價值按照邊權不均勻傳遞，旅客關系越親密邊權越大則獲得的傳遞價值越大，因此邊權計算的科學性、準確性直接影響旅客價值度量結果。

RFM模型根據顧客消費近度系數R預測顧客再次消費的可能性。同樣，對于民航旅客，本文認為旅客關系也具有時間相關性：最近同行過的旅客，再次同行的可能性更大，關系更親密；相反，即使曾經同行多次，但近兩年都沒有同行記錄，也要考慮是否該旅客關系已經消失。基于以上考慮，設定觀測時間窗口，觀察時間窗口內的旅客關系，引入時間衰減因子τ，使得旅客關系具有時間感知性。

假設旅客旅客i和旅客j最后一次同訂單(或同乘)時間為t，則旅客i和旅客j同訂單(或同乘)關系的時間衰減因子τ可表示為

(8)

式中：T-t′為觀測時間窗口的長度；T為時間窗口的結束時間；t′為時間窗口的起始時間。t≤t′表示在觀測時間窗口內旅客未發生同訂單(或同乘)關系，則認為該關系消失，令τ=0。

引入時間衰減因子后，旅客同訂單關系得分可表示為式(9)，旅客同乘關系得分為式(10)：

(9)

(10)

式中：τPij為旅客i和旅客j同訂單關系的時間衰減因子；τDij為旅客i和旅客j同乘關系的時間衰減因子。

將旅客同乘關系得分和同訂單關系得分規范化后加權求和，獲得旅客關系總得分。計算公式為

(11)

式中：Wij為旅客i和旅客j的關系總得分；ωp、ωd分別為同訂單關系權重、同乘關系權重，ωp<ωd。

2.3 CAPV-Rank算法設計

2.3.1 傳統PageRank算法

有個成語叫狡兔三窟，那是指動物們。現代某些貪官，狡猾地常愛玩腳踏兩只船的伎倆。他們的攀援術是誰有用就依附誰，多頭出擊。他們認為，“腳踏兩只船”是一種生存之道。如果只會死心塌地地踏著一條船劃著一支槳獨行于風雨之中，實在是有些“虛度了豐富多彩的人生”。這些人，生活的理念是，寶貴的生命可不能在一棵樹上吊死。在一艘船里葬身，那多虧！所以，他們的生存之道是，多給自己留條后路，多踩幾條船才會無后顧之憂，哪條船更穩上哪條，不損毫發，何樂而不為？

在Web圖模型中，網頁為節點，網頁間的鏈接關系為邊，節點得分即表示網頁重要性。節點得分通過邊向鄰居節點傳遞，節點i的得分等于其從鄰居節點獲得的得分總和，表達式為

(12)

式中：ri為節點i的得分；N(i)為節點i的鄰居節點；O(j)為節點j的出度。

為了解決懸掛節點，引入阻尼系數α，加入虛鏈路使節點得分不僅可以從鄰居節點沿實際鏈路傳遞獲得，還可以從任意節點沿虛鏈路傳遞獲得，節點i得分表達式為

(13)

式中：α為阻尼系數，表示節點沿實際鏈路繼續傳遞的概率；1-α為沿虛鏈路隨機跳轉概率；N為網頁數量。

推廣至所有節點，節點得分向量計算公式為

(14)

2.3.2 CAPV-Rank算法

1) 引入旅客價值轉移概率矩陣M

(15)

式中：N(i)為節點i的鄰居節點集。由式(15)可知Mij≠Mji，這是因為雖然Wij=Wji，但旅客i和旅客j自身的社交關系不同，該組關系在各自社交關系中所占的比重不同，因此轉移概率不同。

2) 引入個性化轉移向量U

在民航旅客社交關系網絡G中，V為通過RFMc模型計算得到的旅客個體價值集合，vi表示旅客i的個體價值，定義旅客個性化轉移向量為U=[u1u2…un]，n為旅客數量，ui為旅客i的個性化轉移概率，表達式為

(16)

傳統PageRank算法中所有節點得分和為1，由于旅客數為千萬量級，旅客價值規范化和為1會導致各旅客價值極小，不利于收斂性的判定，因此將旅客價值總和初始化為n。

3) 融合旅客個體價值和社交關系計算旅客i的價值得分ri為

(17)

式中：阻尼系數α用來調整社交關系和旅客個體價值對旅客價值度量的影響程度，0≤α≤1。

4) 推廣至全旅客集，融合旅客個體價值和社交關系計算旅客價值得分向量，即

(18)

設置迭代終止條件為

‖Ri+1-Ri‖2≤ε

PageRank算法收斂性已得到證明，CAPV-Rank算法只是基于PageRank算法做了參數調整，顯然也是收斂的。無論賦予怎樣的初值，最終R會趨于一個穩定值，即為旅客價值。

3 網絡模型構建中的問題和算法討論

3.1 旅客身份識別

由于PNR和離港數據中旅客證件信息龐雜，同一旅客每次乘機可能使用不同的證件信息。為了準確計算旅客個體價值和評價旅客關系，旅客身份識別成為網絡模型構建中首要解決的關鍵問題。

本文將PNR數據進行數據關聯和身份聚合，構建旅客證件信息列表，添加旅客序列號PSG_ID作為旅客的唯一標識，如表1所示。

其中旅客序列號[1,2,3,…,n]是旅客的唯一標識，證件號均進行過加密處理。由表1可知，旅客1對應3種證件類型和3個證件號。

表1 旅客證件信息列表樣例Table 1 Example of passenger document information

3.2 旅客關系識別

3.2.1 刪除假隱式關系

由于旅客隱式同乘關系有的特征明顯，例如值機序號相連且座位相鄰，據此可以判斷這兩位乘客可能是約定的同乘關系，具有一定的社會關系；有的隱秘不易被發現，例如雖然同乘時座位和值機序號不都相鄰，但是同乘多次，據此也可判斷乘客之間有一定的社會關系；還有些旅客同乘關系僅有一次，且該次同乘中座位號或值機序號不都相鄰，本文認為這種情況極可能是碰巧同乘而旅客雙方并不存在社會關系。

因此，結合構建好的旅客同乘關系和同訂單關系，若兩位旅客不存在同訂單關系，同乘關系僅有一次且該次同乘值機序號和座位號不都相鄰，則將這兩位旅客視為碰巧同乘并將二者之間的同乘關系刪除。

3.2.2 保護真實旅客關系

有些多于兩人的小團體出行，內部成員不可能兩兩都座位相鄰、值機序號相鄰，但其存在一定的社會關系，為保護這些真實旅客關系不被誤認為假隱式關系，需要在構建旅客同乘關系時，首先識別離港數據中的同行小團體，并將團體內部成員之間的所有同乘關系均設置為值機序號相鄰且座位相鄰。

3.3 模型中的參數設置

對于式(4)中RFMc指標權重的分配問題，由于行業背景不同、對客戶的關注層面不同，因而沒有統一的分配方案。在民航背景下，旅客個體價值體現在旅客對于民航利潤的貢獻值，而旅客相對乘機金額MC是旅客實際消費貢獻值的直觀體現，對民航收益影響最大；其次，旅客乘機頻率F反映了旅客的活躍度和忠誠度，是旅客價值度量需要考慮的重要因素；最后，綜合旅客消費近度系數R和旅客平均周轉時間可以預測旅客再次乘機的概率。因此在民航旅客個體價值計算的權重分配中，應遵循值度最重、頻度次之、近度最次的原則。

對于式(8)，本文將時間窗口長度設為兩年，表示若旅客在最近兩年內沒有發生同乘(或同訂單)關系，則認為旅客關系消失，將曾經積累的關系清零。例如：在2016年5月1日使用本模型評價旅客關系，設定時間窗口為兩年，則時間窗口結束時間T為2016-05-01，起始時間t′為2014-05-01。若旅客i和旅客j最后一次同訂單(或同乘)時間為2015年5月1日，則t=2015-05-01，計算可得τ=365/730=0.5，若t≤t′，表示旅客在觀測時間窗口內沒有發生同訂單(或同乘)關系，即令τ=0。由于本文使用的訓練數據集為一年的數據，時間窗口設為2年，因此τ值均大于0.5。實際應用中，時間窗口的長度可視情況而定。

3.4 CAPV-Rank算法討論

CAPV-Rank算法既可用來進行多模式下的旅客價值度量，又可用來預測旅客未來價值的變化趨勢，挖掘潛在高價值旅客。

3.4.1 旅客價值度量

旅客價值度量幫助航空公司進行旅客管理并制定各種營銷策略，基于不同的業務需要，旅客價值度量的出發點和立足點不同，則度量標準不同。

CAPV-Rank算法可以通過調節α權重因子，靈活調整旅客個體價值和社交關系對旅客價值度量的影響系數：

1) 當α=0時，Ri+1=αMRi+(1-α)U=U，忽略了社交關系對旅客價值的影響，僅通過RFMc模型分析旅客個體實際消費情況來度量旅客價值。與傳統RFM相比，RFMc模型考慮了艙位等級不同而帶給航空公司不同的利潤價值，更適用于民航背景下的旅客價值計算。

2) 當α=1時，Ri+1=αMRi+(1-α)U=MRi，忽略了旅客個體價值，僅根據旅客之間的社交關系采用改進的PageRank算法模型衡量旅客價值。與傳統帶權PageRank算法不同的是，本文構建旅客社交網絡時，分析了PNR數據和離港數據雙數據源，對旅客關系挖掘得更徹底進而價值度量更全面。

3) 當0<α<1時，Ri+1=αMRi+(1-α)U，是融合了旅客個體價值和社交關系的混合度量方法，真正將個體價值融入社交關系網絡并使其參與到旅客價值迭代計算的過程中，對旅客價值度量更全面，且通過α動態調整旅客個體價值和社交關系的權重，滿足多變的業務需求。

3.4.2 旅客價值預測

1) 預測旅客個體價值，挖掘潛在高價值旅客

CAPV-Rank算法認為旅客價值受其所在社交網絡的影響，當前價值較低的旅客與高價值旅客聯系越緊密，消費潛力越大，未來成為高價值旅客的概率越大，因此根據旅客當前個體價值和社交關系預測旅客未來個體價值，通過參數α控制社交關系對旅客價值的影響系數，根據訓練數據和測試數據尋求最佳的α，使其達到較好的預測效果。

根據參數確定后的式(18)計算得到旅客個體價值的預測結果為Rn×1=[r1r2…rn]T，Un×1=[u1u2…un]T為旅客當前個體價值，則旅客的潛在價值向量Tn×1為

Tn×1=Rn×1-Un×1

(19)

從Tn×1中選擇最大的前k個值，即為潛在價值最大的k個旅客。

2) 預測旅客價值相對生長速度

旅客價值相對生長速度是旅客增加的價值和原有價值的比值，當前個體價值越小而潛在價值越大，潛在價值相對生長速度越快。定義旅客潛在價值相對生長速度為RT，表達式為

(20)

從RT中選擇最大的前k個值，即為相對生長速度最快的k個旅客。與旅客潛在價值預測相比，預測旅客相對生長速度，更有助于發現當前價值很小而潛在價值相對較大的旅客。

4 實驗與分析

4.1 實驗數據

本文實驗用到的數據來自于民航訂座系統中2015、2016年旅客訂票(PNR)數據和離港(Departure)數據，其中PNR數據集中每一行是一個旅客關于某次行程的訂票記錄，Departure數據集中每一行是一個旅客關于某次行程的離港記錄。考慮到本文提出的旅客價值度量模型依賴于旅客真實的社交關系網絡，對網絡的完整性要求較高，因此以中國某航空公司為研究目標，從訂座系統的全數據集中提取出該航空公司2015、2016兩年都有乘機記錄的全旅客出行數據集，該數據集共有旅客2千多萬名，旅客出行記錄1.6億多條，其中2015年7千多萬條，2016年8千多萬條。

共生成3個數據集：D1(2015年全旅客出行數據集)，D2(2016年全旅客出行數據集)，D3(2015和2016兩年的全旅客出行數據集)。

根據3.1節構建的旅客證件信息列表，將數據集中的旅客證件號替換為對應的旅客序列號PSG_ID，作為旅客的唯一標識。同時，為方便計算旅客個體價值，將數據集中的艙位等級代碼替換為各代碼對應的票價折扣，其中頭等艙票價為全價的1.5倍，公務艙票價為全價的1.3倍，超級經濟艙票價等于全價的1倍，其他普通經濟艙為全價的0.95～0.25倍不等。

4.2 基準算法

1) RFMc模型。根據旅客歷史消費記錄，獲得旅客乘機時間近度系數R、乘機頻率F和消費金額M度量旅客價值。

2) 加權PageRank算法。分析PNR數據，根據旅客歷史訂單構建旅客同行關系網絡，將旅客同訂單次數作為邊權重，使用加權PageRank算法度量旅客價值。

3) Passenger Rank算法[7]。該算法分為兩個獨立過程：使用RFMc模型計算旅客價值，將獨飛次數占乘機總次數的比例與旅客價值相乘作為旅客個體價值；使用加權PageRank算法計算旅客網絡價值，最后將兩部分加權求和得到旅客總價值。

Passenger Rank算法使用RFM算法與加權PageRank分別單獨計算旅客個體價值與網絡價值再求和，在計算旅客個體價值和網絡價值時都具有局限性：首先，旅客個體價值是旅客個體消費帶給航空公司的利潤價值，因此無論是旅客獨飛還是與他人同行，旅客本身花費的機票價格都應該歸為其個體價值；其次，不同于其他行業，不同艙位等級為航空公司帶來較大的利潤差異，也體現了旅客不同的消費水平，因此也應該作為旅客個體價值的衡量標準之一；最后，計算旅客網絡價值時，不僅應該考慮旅客關系的強弱，還要考慮旅客因個體消費水平不同對網絡的影響力也截然不同。

4) 隨機游走算法。隨機游走算法通過分析旅客個體出行數據，構建旅客-航線二部圖網絡，再使用隨機游走模型預測旅客未來可能選擇的航線，最后根據航線價值預測旅客未來價值。

4.3 算法功能分析和實驗設計

CAPV-Rank算法融合了旅客當前個體價值和社交關系，既可用于旅客價值度量又可進行旅客個體價值預測：① 進行旅客價值度量時，參數α控制旅客個體價值和社交關系對于旅客價值度量的權重分配，參數α的設置主要依托于具體的業務背景和目的，可以根據需要進行調整；② 進行旅客個體價值預測時，參數α協調旅客個體消費的穩定性和社交關系對旅客價值的影響，可以根據訓練數據和測試數據尋求最佳的α，以達到更好的預測效果。

4.3.1 對旅客價值的度量

由于旅客價值是不確定的概念，且在不同的業務需求、業務背景下，由于出發點和立足點不同，對旅客價值的度量標準也不同，因此很難直接證明本文提出的CAPV-Rank算法對旅客價值度量的準確性優于其他算法，但就算法靈活性和穩定性而言，CAPV-Rank算法明顯優于其他算法。

1) 算法靈活性

當前業界對民航旅客價值的研究主要有旅客個體價值度量和網絡價值度量。與傳統度量方法不同的是，CAPV-Rank算法可以通過調節參數α，實現多種旅客價值度量模式，如3.3.1節所述，在α=0時實現旅客個體價值度量，在α=1時實現旅客網絡價值度量，在0<α<1時實現融合旅客個體價值和社交關系的混合價值度量，且在各種模式下，都優于現有算法。

2) 混合價值度量的穩定性

僅根據旅客實際個體消費數據計算旅客個體價值具有滯后性，且由于旅客短期消費不穩定，使得旅客價值計算結果穩定性較差；而融合了旅客個體消費水平和社交關系的總體價值，在事實消費數據的基礎上結合旅客社交關系綜合度量旅客價值，社交關系的影響減弱了旅客個體短期不穩定消費對旅客價值度量的影響，因而對旅客價值度量穩定性更好。

綜上，在旅客價值度量方面主要檢驗：① 參數α對旅客價值度量結果的影響；② CAPV-Rank算法的穩定性與其他基準算法的穩定性比較。

4.3.2 對旅客個體價值的預測

1) 混合算法具有前瞻性，可以根據旅客當前個體價值和旅客社交關系預測旅客未來個體價值，α為進行旅客個體價值預測時，旅客受社交關系的影響系數，也可以稱為旅客向鄰居旅客學習的步長因子，α越大，社交網絡對旅客價值預測結果影響越大。

2) 根據旅客個體價值的預測結果，挖掘潛在高價值旅客和高生長速度旅客。

因此，對旅客價值預測主要檢驗：① 參數α對旅客個體價值預測準確性的影響；② 算法對潛在高價值旅客挖掘和高生長速度旅客發現的準確性與基準算法的比較。

4.4 算法評價指標

本文采用Spearman等級相關系數作為旅客價值度量穩定性和旅客個體價值預測準確性的評價指標，采用Jaccard相似系數作為潛在高價值旅客挖掘和潛在高生長速度旅客發現的準確性評價指標。

4.4.1 Spearman等級相關系數

Spearman等級相關系數用來估計兩個變量X、Y之間的相關性，如果兩個變量取值的兩個集合中均不存在相同的兩個元素，那么當其中一個變量可以表示為另一個變量的很好的單調函數時，兩個變量之間的相關系數可以達到+1或-1。

斯皮爾曼等級相關系數f計算公式為

(21)

本實驗中的Xrank為待檢驗算法(基準算法或者不同α下的CAPV-Rank算法)在數據集D1上計算的旅客價值向量R1的排序結果向量，其中Xrank i為第i個旅客價值在Xrank中的排名。Yrank在進行不同實驗時，分別為：① 進行α因子的影響檢驗時，Yrank為不同α下的CPAV-Rank算法在數據集D1上計算的旅客價值向量R1的排序結果向量；② 進行算法穩定性檢驗時，Yrank為待檢驗算法在數據集D3上計算的旅客價值向量R3的排序結果向量；③ 進行旅客個體價值預測的準確性檢驗時，Yrank為待檢驗算法數據集D2上計算得到旅客個體價值向量U2的排序向量。其中Yrank i為第i個旅客價值在Yrank中的排名。

Spearman等級相關系數越大，說明采用該算法在兩個數據集上計算結果的相關性越大，算法穩定性越好，對旅客個體價值預測越準確。

4.4.2 Jaccard相似系數

Jaccard相似系數核心思想是計算兩個集合A和B的交集元素在A，B的并集中所占的比例，用符號J(A,B)表示。其具體定義為

(22)

本實驗中集合A是指由待檢驗算法在數據集D1上輸出的旅客潛在價值列表T(或相對生長速度列表RT)中潛在價值(或相對生長速度)最大的k個旅客，而集合B是在數據集D1和D2上計算旅客價值U1和U2，獲得旅客實際個體價值變化UG=U2-U1(或旅客實際相對生長速度向量UG/U1)，取出值最大的k個旅客生成的集合。

J(A,B)越大(最大值為1)表示集合A與集合B相同的元素越多，也即算法預測準確性越好。

4.5 實驗與結果分析

實驗共分為兩部分：① 檢驗參數α對算法性能的影響；② 比較本文提出的算法與基準算法在旅客價值度量方面的穩定性和預測的準確性。

4.5.1 參數α對算法性能的影響

1) 對旅客價值度量結果的影響

令α=(0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1)計算旅客價值，并與使用RFMc模型得到的旅客價值做Spearman等級相關性分析，結果見圖1。

當α=0時，R=U，與通過RFMc模型計算旅客個體價值結果相等，故相關性為1。隨著α的增加，CAPV-Rank算法與RFMc算法計算結果相關性逐漸減弱。

圖1 α因子對計算結果的影響Fig.1 Influence of α on calculation result

2) 對預測結果準確性的影響

在不同α下使用CAPV-Rank算法計算旅客個體價值，并與第2年旅客真實個體價值做Spearman等級相關性分析，結果見圖2。

由圖2可以看出當α=0.4時，CAPV-Rank算法在旅客個體價值預測效果最好，因此令α=0.4，在實際應用中，為達到最佳的預測效果，可以進行更細致的參數尋優。

4.5.2 與基準算法的比較

1) 旅客價值度量

分別采用α=0.4下的CAPV-Rank算法、Passenger Rank算法[7]、加權PageRank算法和RFM模型在數據集D1和數據集D3上進行民航旅客價值計算，將計算結果進行Spearman等級相關性分析，Spearman等級相關系數越大，對旅客價值度量的穩定性越好，結果見表2。

圖2 不同α下預測結果的準確性Fig.2 Accuracy of the prediction with different α

表2 度量結果的穩定性Table 2 Stability of measurement results

算法Spearman等級相關系數CAPV-Rank算法(α=0.4)0.822PassengerRank算法0.781加權PageRank算法0.544RFM模型0.693

2) 旅客個體價值預測

分別將采用α=0.4下的CAPV-Rank算法、Passenger Rank算法[7]、加權PageRank算法和RFM模型在數據集D1上進行旅客個體價值計算的結果與在數據集D2采用各自算法計算的旅客個體價值結果進行Spearman等級相關性分析，Spearman等級相關系數越大，對旅客個體價值預測的準確性越好，結果見表3。

隨機游走算法[6]建立旅客-航線二部圖網絡，通過預測旅客未來可能選擇的航線來計算旅客潛在價值，該算法只考慮旅客與航線的關系，忽略了同行旅客之間的相互影響，而且由于絕大多數旅客出行數據極少，導致預測準確率較差。CAPV-Rank算法綜合考慮旅客個體消費水平和同行旅客的影響，對旅客潛在價值具有更好的預測效果。

由表2和表3可以看出，CAPV-Rank算法與其他算法相比，度量穩定性和預測準確性更好。

表3 對旅客個體價值預測的準確性Table 3 Accuracy of individual value prediction

3) 潛在高價值旅客挖掘

分別使用CAPV-Rank算法、隨機游走算法在數據集D1上計算旅客潛在價值，將計算結果與旅客真實價值變化結果作Jaccard相關性分析(k=2 000 000)，結果見表4。

表4 潛在價值預測的準確性Table 4 Accuracy of potential value prediction

4) 潛在高生長速度旅客發現

分別使用CAPV-Rank算法、隨機游走算法在數據集D1上預測旅客價值相對生長速度，將預測結果與旅客真實價值相對生長速度結果作Jaccard相似性分析(k=2 000 000)，結果見表5。

表5 相對生長速度預測的準確性Table 5 Accuracy of relative growth rate prediction

與潛在價值預測相比，潛在生長速度預測有助于發現當前旅客個體價值更小、潛在價值更大的旅客。隨機游走算法僅根據旅客個人消費預測潛在價值，嚴重依賴于旅客個體消費數據，而個體價值更小的旅客出行數據更少，因此預測準確性更差。CAPV-Rank算法構建旅客社交關系網絡，根據旅客真實社交關系預測旅客價值，解決了數據稀疏造成的預測準確率低下的問題，在旅客價值預測、潛在高價值旅客挖掘和潛在高生長速度旅客發現方面更準確。

5 結 論

1) 本文提出的CAPV-Rank算法既可以實現旅客價值度量又可以預測旅客未來個體價值及挖掘潛在高價值旅客。

2) CAPV-Rank算法進行旅客價值度量時，可以根據不同需求和目的，動態調整旅客個體價值和社交關系權重因子，實現旅客個體價值度量、旅客網絡價值度量、融合旅客個體屬性與社交關系的混合價值度量3種度量模式，適應各種業務場景，滿足不同業務需求。

3) 進行旅客個體價值計算時，引入艙位等級C，將傳統RFM模型改進為RFMc模型計算旅客個體價值，更適合民航背景下的旅客個體價值度量。

4) 進行混合價值度量時，CAPV-Rank算法在事實消費數據的基礎上結合旅客社交關系綜合度量旅客價值，社交關系的加入克服了旅客個體短期不穩定消費對旅客價值度量的影響，因而對旅客價值度量穩定性更好。

5) 進行旅客價值預測和潛在高價值旅客發現時，CAPV-Rank算法可以動態調整因子，訓練獲得使預測效果最佳的步長因子α，有效預測旅客價值、挖掘潛在高價值旅客和高生長速度旅客。

6) 本文深入挖掘多數據源中的旅客關系，構建旅客顯隱式雙層關系網絡，解決了非同訂單的旅客同乘關系易被忽略、真實旅客關系難以識別等問題，為今后旅客群體的分類、旅客社交關系識別及旅客行為偏好研究提供了新的解決思路。

[1] 馮霞, 徐冰宇, 盧敏. 民航旅客訂票行為細分及群體特征分析[J]. 計算機工程與設計, 2015, 36(8)： 2217-2222.

FENG X, XU B Y, LU M. Booking behavior subdivision and characteristic analysis of civil aviation passenger[J]. Computer Engineering and Design, 2015, 36(8): 2217-2222 (in Chinese).

[2] 潘玲玲. 基于旅客行為的航空旅客細分模型研究及其實現[D]. 南京： 南京航空航天大學, 2012: 1-57.

PANG L L. The research and realization of civil aviation customer segmentation based on customer behavior[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2012: 1-57 (in Chinese).

[3] 林友芳, 王琨琨, 周超, 等. 基于社交網絡的民航旅客偏好建模[J]. 北京交通大學學報, 2014, 38(6): 33-39

LIN Y F, WANG K K, ZHOU C, et al. Modeling the preference of air passengers based on social network[J]. Journal of Beijing Jiaotong University, 2014, 38(6): 33-39 (in Chinese).

[4] 王坤坤. 民航旅客座位偏好建模與應用研究[D]. 北京： 北京交通大學, 2015: 1-48.

WANG K K. Research of modeling the seat preference of civil aviation passengers and its applications[D]. Beijing: Beijing Jiaotong University, 2015: 1-48 (in Chinese).

[5] 曹衛東, 白亮, 聶笑盈. 基于Map/Reduce的民航高價值旅客發現方法[J]. 計算機工程與設計, 2015, 36(4): 1078-1083.

CAO W D, BAI L, NIE X Y. Method of discovering high-value passengers of civil aviation based on map/reduce[J]. Computer Engineering and Design, 2015, 36(4): 1078-1083 (in Chinese).

[6] FENG X, XU B Y, MIN L, et al. Potential high-value passengers discovery by random walk on passenger-route heterogeneous network[J]. Journal of Computational & Theoretical Nanoscience, 2015, 12(8): 1568-1593.

[7] 韓敏. 基于社會網絡的民航旅客價值排序算法研究與實現[D]. 北京： 北京交通大學, 2014: 22-38.

HAN M. The research and implementation on ranking the aviation passengers’ values based on social network[D]. Beijing: Beijing Jiaotong University, 2014: 22-38 (in Chinese).

[8] 馮霞, 李勇, 陳卉敏. 民航旅客社會網絡構建方法研究[J].計算機仿真, 2013， 30(6): 51-54, 142.

FENG X, LI Y, CHEN H M. Research on constructing social network of airline customers from data of PNR[J]. Computer Simulation, 2013, 30(6): 51-54,142 (in Chinese).

[9] HAVELIWALA T H. Topic-sensitive PageRank[C]∥International Conference on World Wide Web, 2002：517-526.

[10] KAMVAR S D, HAVELIWALA T H, MANNING C D, et al. Exploiting the block structure of the web for computing PageRank[R]. Palo Alto, San Francisco: Stanford University Technical Report, 2003: 1-13.

[11] YANG Z, TANG J, ZHANG J, et al. Topic-level random walk through probabilistic model[M]∥Advances in Data and Web Management. Berlin: Springer Berlin Heidelberg, 2009: 162-173.

[12] 朱凡微, 吳明暉, 應晶. 高效個性化PageRank算法綜述[J]. 中國科技論文, 2012, 7(1): 7-13.

ZHU F W, WU M H, YING J. Efficient personalized PageRank computation: A survey[J]. China Sciencepaper, 2012, 7(1): 7-13 (in Chinese).

[13] ZHU F W, FANG Y, CHANG C C, et al. Scheduled approximation for personalized PageRank with utility-based hub selection[J]. The VLDB Journal, 2015, 24(5): 1-25.

[14] WEI W, GAO B, LIU T Y, et al. A ranking approach on large-scale graph with multidimensional heterogeneous information[J]. IEEE Transactions on Cybernetics, 2016, 46(4): 930.

[15] WAN X, XIAO J. Single document keyphrase extraction using neighborhood knowledge[C]∥National Conference on Artificial Intelligence, 2008: 855-860.

[16] LI D, LI S, LI W, et al. A semi-supervised key phrase extraction approach: learning from title phrases through a document semantic network[C]∥Proceedings of the, Meeting of the Association for Computational Linguistics, 2010: 296-300.

[17] SIDDIQI S, SHARAN A. Keyword and keyphrase extraction techniques: A literature review[J]. International Journal of Computer Applications, 2015, 109(2): 18-23.

[18] MIHALCEA R, TARAU P. TextRank: Bringing order into texts[J]. Unt Scholarly Works, 2004: 404-411.

[19] AMJAD T, DING Y, DAUD A, et al. Topic-based heterogeneous rank[J]. Scientometrics, 2015, 104(1): 1-22.

[20] DING Y. Topic-based PageRank on author cocitation networks[J]. Journal of the Association for Information Science and Technology, 2011, 62(3): 449-466.