旅客群體中的家庭結構發現

王志偉（北京交通大學計算機與信息技術學院，交通數據分析與挖掘北京市重點實驗室，北京100044）

旅客群體中的家庭結構發現

王志偉
（北京交通大學計算機與信息技術學院，交通數據分析與挖掘北京市重點實驗室，北京100044）

家庭作為一種最常見的出行消費單元，在客運領域擁有相當規模的市場。精準地識別家庭結構，有利于客運企業為旅客提供個性化的出行服務和產品推薦。研究旅客群體中發現家庭結構的問題，提出一種基于關系分類的類型化社區發現方法來確定旅客社會網絡中的家庭結構。在客運領域的一個真實的數據集上進行實驗，證明該方法可以有效地從旅客歷史出行記錄中發現旅客家庭結構。

旅客社會網絡；家庭結構；關系分類；社區發現

1　問題的提出

隨著社會經濟的發展，人們能夠自由選擇的出行方式更加豐富多樣，出行次數也不斷增多。家庭作為一種最常見的出行消費單元，在客運領域擁有相當規模的市場。如果能夠準確地識別出家庭團體，將有利于航空公司為旅客提供個性化的出行服務或產品推薦[1]。例如，家庭成員間傾向于坐在一起，可以為家庭團體預留相鄰座位以提高旅客的滿意度；可以為有老人和孩子的家庭提供便捷值機通道以方便他們出行；可以根據不同的家庭模式（如兩口之家、三口之家、三代同堂等）推薦適合的旅行線路；還可以為高價值的家庭團體提供專門服務等。此外，本研究還可以為相關組織或政府提供決策支持。例如，通過分析不同類型家庭的出行模式，可以輔助航空公司優化產品策略、地方政府完善基礎設施[2]和調整目的地意象（Destination Image）[3]等。

與此同時，企業信息化水平的提高使得其積累的海量旅客信息和歷史出行信息得以有效地利用，為我們從中發現家庭團體提供了有效的途徑。本文將提出一種從旅客歷史出行記錄中發現家庭團體的方法。

2　相關工作

近年來，在旅游市場管理與營銷中關于家庭團體的相關研究不斷涌現。例如，Lehto等人[4]進行了家庭度假活動和家庭凝聚力的研究；Prayag等人[5]研究了中老年人的出行動機。

關系分類一直是社會網絡挖掘中的一個重要研究議題，近年來已經產生了許多關系分類的方法。例如，使用關系馬爾科夫網來預測恐怖分子間的關系類型；利用基于社區結構的條件隨機場模型來判別社會關系類型[6]；在異構網絡中推斷社會關系等。

社區結構是社會網絡乃至復雜網絡研究中的一個熱點問題，近年來涌現了眾多的社區發現算法。一個通用的社區結構發現算法可以看成是一種無監督的學習方法。大量相關通用算法不斷涌現，例如最著名的基于模塊度函數Newman和Girvan方法[7]及其大量變種；基于信息論的Infomap方法[8]，是目前公認的準確率和穩定性最高的社區發現算法之一。然而，通用社區發現算法的目的只是為了找到社區，而不關心社區的類別，因此劃分的社區不具有可解釋性。

本文將從社會網絡的視角，基于關系分類和社區發現的思想，從旅客歷史出行記錄中發現家庭團體。從社會網絡的視角研究旅客之間的關系是一項非常有意義的工作。Lin等人[9]曾利用旅客的歷史出行記錄來構建旅客社會網絡，并在此基礎上推斷大規模旅行團的出行目的，即判斷一個旅行團是商務團還是旅游團。

3　方法

本節將針對旅客社會網絡中的家庭團體發現方法進行詳細的闡述。首先，我們根據旅客歷史出行記錄提取旅客關系，構建旅客共同出行網絡。然后，構建用于旅客關系分類的特征，包括歷史共同出行特征、人口學統計特征以及基于網絡的特征。然后采用協同分類方法對旅客關系進行分類。最后，基于關系分類的結果，采用兩種社區發現的方法來發現家庭團體。

3.1構建共同出行網絡

我們從這些歷史數據中提取旅客間的共同出行關系，構建一種特定類型的大規模旅客社會網絡——共同出行網絡（Co-travel Networks）。該網絡可以在某種程度上從一個側面反映旅客之間的社會關系。旅客間的共同出行關系可以從旅客共同訂票數據中獲取。該網絡以旅客為節點，如果旅客間存在共同出行行為，那么就在旅客間構建一條邊，并將旅客共同出行的次數作為邊的權重。

3.2關系分類

在部分標注的共同出行網絡中，我們已知小部分的關系類型標簽，需要用這部分關系作為訓練集，學習分類器來推斷未知類型的關系。最直接的方法就是假定所有的標簽變量服從獨立同分布，構造關系的各種特征屬性然后利用傳統的分類器進行分類，但在實際的共同出行網絡中，各變量間存在著依賴關系。家庭關系是具有傳遞性的。考慮到上述依賴性，我們采用條件隨機場對共同出行網絡中的所有關系進行協同分類。

（1）構建旅客關系特征

根據關系特征生成機制的不同，我們將旅客關系特征分為三類：歷史共同出行特征、人口學統計特征以及基于網絡的特征。

歷史共同出行特征是基于旅客共同出行行為的統計特征。不同的關系類型可能會呈現不同的出行模式。例如，家人共同出行時經常會選擇一起值機并坐在一起，而同事則不一定，因此值機序號和座位差對于關系分類也尤其重要。本文中考慮了共同出行次數、共同出行里程（均值、最大、最小）、座位差（均值、最大、最小）、值機序號差均值、工作日出行（次數、比例）、周末節假日出行（次數、比例）等指標。

人口學統計特征是基于旅客的靜態屬性（例如年齡、性別、籍貫、姓氏等）的統計特征。不同的關系類型可能具有不同的人口學統計特征。例如，在年齡方面，父母與子女之間的年齡相差較大，子女間的年齡相差較小，而同事間的年齡差則不一定。由此，我們用年齡差、性別組合、籍貫異同以及姓氏異同來表示人口學統計特征。本文中考慮了旅客間的年齡差、籍貫異同、性別組合以及姓氏異同等指標。

上述兩類旅客關系特征都是從關系本身出發，并沒有考慮到某條關系在整個共同出行網絡中的結構特征。事實上，網絡中豐富的鏈接結構信息也有可能生成有利于關系類型推斷的特征。本文中考慮了共同鄰居節點個數，共同鄰居節點度均值以及邊介數幾種常見的邊的網絡結構特征。

（2）條件隨機場

條件隨機場是一種用來標記序列化結構數據的無向圖模型。該模型描述了在給定觀察屬性下的隱藏標簽的條件概率。

①構建條件隨機場

構建條件隨機場時需要定義基團及其勢函數，有兩種類型的基團需要定義，即證據基團和相容基團。證據基團由一個目標變量和與之相關的條件變量構成，表示目標變量對條件變量的單向依賴；而相容基團則由目標變量構成，表示目標變量間的相互依賴。

針對本文的家庭關系識別問題，我們采用家庭關系傳遞性原則定義三元相容基團。如果任意三條關系在共同出行網絡中構成一個環，那么我們就對相應的目標變量建立基團。接下來，我們需要為基團的勢函數定義特征函數。由于我們將家庭關系識別可以看成一個二分類問題，因此只考慮二分類模型的特征函數定義。對于證據基團，我們定義為標簽值與屬性值的乘積；對于相容基團，我們根據三個標簽是否相同來定義特征函數，如果標簽相同則為1，不同則為0。

②學習與推理

最大似然估計（Maximum Likelihood Estimation, MLE）方法可以用來進行條件隨機場的參數學習。在參數學習過程中，計算特征函數的期望的復雜度是指數級的，是一個NP-hard問題，因此無法精確推理，必須采用近似推理算法。信度傳播（Belief Propagation,BP）和馬氏鏈蒙特卡洛（Markov Chain Monte Carlo，MCMC）[10]是兩種最常用的近似推理算法。

Wan等人[11]采用偽似然（Pseudo-Likelihood）技術來近似描述條件隨機場并提出了最大偽似然估計（Maximum Pseudo-Likelihood Estimation，MPLE）參數學習方法，無需使用近似推理算法。同時，為了加快偽似然模型的推理過程的收斂速度，作者還提出了一種迭代推理算法。基于偽似然的條件隨機場模型在損失較小精度的情況下，可以極大地提高模型的學習和推理效率，因此本文在實驗中也采用了這一方法。

3.3類型化社區發現

將介紹如何利用關系分類的結果進行類型化社區發現，確定旅客共同出行網絡中的家庭團體。我們分別采用兩種不同的社區劃分方法，一種是簡單的割邊法，另一種是采用帶權社區發現方法。

（1）割邊

該方法在旅客共同出行網絡中，利用關系分類的標簽結果，保留類標簽值大于某一特定閾值的關系，篩除其余所有關系，剩余邊將自動形成若干獨立的連通子圖，將每個獨立的連通子圖作為類型化社區。本文要檢測共同出行網絡中的家庭團體，則保留類標簽為家庭的關系，篩除非家庭關系，剩余的家庭關系形成的連通子圖社區則為家庭團體。這種方法僅考慮到關系分類的結果，而未充分利用網絡的鏈接結構信息。

（2）帶權社區劃分

對關系進行分類后，得到每條關系屬于每個可能標簽的概率值，選取其中最大的標簽概率值作為該關系的類標簽。標簽的概率值反映了關系屬于某個標簽值的可能性，從而體現了旅客之間在該關系類型下的緊密程度。標簽的取值越大，說明該類型關系的緊密程度越高。因此，我們將關系分類結果的概率值作為網絡中的關系權重,采用帶權社區發現方法來發現家庭團體。為了減少權重偏低的關系對社區發現算法的干擾，我們同樣設置一個閾值，首先將權重小于該閾值的關系從網絡中刪除，然后再運行帶權的社區發現算法。

傳統的社區發現算法單純基于網絡中的鏈接結構進行社區發現，認為網絡中的所有鏈接都是平等的，相比之下，帶權的社區發現算法還考慮了不同鏈接對于網絡社區結構影響的不同，即鏈接權重的重要作用，因此得出的社區結果更加準確合理。我們采用基于關系分類的帶權社區發現算法，可以利用網絡的整體鏈接結構來修正第一種割邊法中因關系分類錯誤而帶來的偏差，使發現的家庭團體更加準確。

4　實驗

在實驗中，我們首先是對網絡中的邊進行關系分類，分別采用了傳統的邏輯回歸分類器和條件隨機場協同分類算法進行二值分類。然后分別采用割邊法和帶權社區發現方法來發現家庭團體。對于帶權社區發現方法，我們采用目前公認準確率和穩定性最高的社區發現算法之一的Infomap算法。

在關系分類過程中，我們分別用邏輯回歸和條件隨機場在已標注的關系集上進行了5重交叉驗證。邏輯回歸方法得到的分類準確率為81.63%，條件隨機場的分類準確率為89.16%（提高了7.53%）。

在條件隨機場的分類結果基礎上，我們分別用割邊法和帶權Infomap算法來發現家庭團體，對家庭團體發現結果，割邊法與帶權社區發現方法的評測結果分別如圖1（a）和圖1（b）所示。

圖1　家庭團體評測

從圖1可以看出，割邊法在閾值為0.6時，發現家庭團體的效果最好，F1值達到最大值為0.913；而帶權社區劃分方法在閾值為0.3時效果最好，F1值達到最大值為0.927。總體而言，從實驗結果我們可以得出如下結論：

（1）針對旅客社會網絡，構建旅客關系特征并且采用條件隨機場協同分類方法能夠有效地對旅客間關系進行分類，并且分類準確率高于傳統的邏輯回歸方法；

（2）基于關系分類的帶權類型化社區發現方法可以非常有效地發現旅客社會網絡中的家庭團體；

（3）在關系分類準確率一定的情況下，帶權社區劃分方法要優于簡單的割邊法。該方法在利用鏈接結構的同時，也考慮到關系權值對網絡社區結構的影響，并能利用鏈接結構來修正關系分類的錯誤帶來的偏差，使得社區劃分結果更加準確合理。

5　結語

本文研究了在客運領域如何利用旅客的歷史出行記錄來發現家庭團體，提出了一種基于旅客社會網絡的家庭團體發現方法。我們首先從旅客的歷史出行記錄中提取旅客共同出行關系，構建旅客共同出行網絡；然后設計了一系列旅客關系特征，并采用條件隨機場協同分類模型對家庭關系進行識別；最后，基于關系分類的結果分別采用割邊法和帶權社區發現方法來發現家庭團體。在客運領域的一個真實的旅客歷史出行記錄數據集上進行了實驗，實驗結果表明，我們所提出的方法可以有效地從旅客歷史出行記錄中發現家庭團體。

[1]R.Nicole,J.Carlson,P.J.Rosenberger,III.Factors Affecting Group-Oriented Travel Intention to Major Events[J].Journal of Travel Tourism Marking,2012,29（2）:185～204

[2]S.I.So,X.Y.Lehto.The Situation Influence of Travel Group Composition:Contrasting Japanese Family Travelers with Other Travel Parties[J].Journal of Travel Tourism Marketing,2007,20:79～91

[3]S.Pike,C.Ryan.Destination Positioning Analysis Through a Comparison of Cognitive,Affective,Conative Perceptions[J].Journal of Travel Research,2004,42:333～342

[4]X.Y.Lehto,Y.-C.Lin,Y.Chen.Family Vacation Activities and Family Cohesion[J].Journal of Travel&Tourism Marketing,2012,29: 835～850

[5]G.Prayag.Senior Travelers'Motivations and Future Behavioral Intentions:the Case of Nice[J].Journal of Travel&Tourism Marketing, 2012,29:665～681

[6]B.Bollobas.Random Graphs,2nd ed.[M].New York,NY:Academic Press,2001

[7]H.Wan,Y.Lin,Z.Wu,H.Huang.A Community-Based Pseudolikelihood Approach for Relationship Labeling in Social Networks[C]. In Proceedings of 2011 European Conference on Machine Learning and Knowledge Discovery in Databases,2011：491～505

[8]M.Rosvall,C.T.Bergstrom.Map of Random Walks on Complex Networks Reveal Community Structure[J].Proceedings of the National Academy of Sciences,2008,105:1118～1123

[9]Y.Lin,H.Wan,R.Jiang,Z.Wu,X Jia.Inferring the Travel Purposes of Passenger Groups for Better Understanding of Passengers[J]. IEEE Transactions on Intelligent Transportation System,2014.Online available:http://dx.doi.org/10.1109/TITS.2014.2329422.

[10]C.P.Robert,G.Casella.Monte Carlo Statistical Methods,2nd ed.[M].New York,NY:Springer,2004

[11]H.Wan,Y.Lin,Z.Wu,H.Huang.Discovering Typed Communities in Mobile Social Networks[J].Journal of Computer Science andTechnology,27（3）:480～491

Passenger Social Networks;Family Structures;Relationship Classification;Community Detection

Family Structures Detection in Passenger Groups

WANG Zhi-wei
（Beijing Key Lab of Traffic Data Analysis and Mining,School of Computer and Information Technology,Beijing Jiaotong University, Beijing 100044）

The families,as a kind of the most common consumer units,have a considerable scale in the field of passenger transportation market.Accurately identifying family structures can help the carriers provide passengers with personalized travel services and product recommendation.Studies the issue of finding family structures in passenger groups and proposes a kind of typed community discovery method based on relationship classification to determine family structures in passenger social networks.Experimental results on a real data set of passenger travel records in the field of passenger transport demonstrate that the method can effectively find family structures from historical travel records.

1007-1423（2015）14-0040-05

10.3969/j.issn.1007-1423.2015.14.010

王志偉（1989-），女，河北衡水人，碩士研究生，學生，研究方向為數據與知識工程

2015-03-17

2015-04-20