旅客群體中的家庭結(jié)構(gòu)發(fā)現(xiàn)

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

旅客群體中的家庭結(jié)構(gòu)發(fā)現(xiàn)

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

家庭作為一種最常見的出行消費單元，在客運領(lǐng)域擁有相當(dāng)規(guī)模的市場。精準(zhǔn)地識別家庭結(jié)構(gòu)，有利于客運企業(yè)為旅客提供個性化的出行服務(wù)和產(chǎn)品推薦。研究旅客群體中發(fā)現(xiàn)家庭結(jié)構(gòu)的問題，提出一種基于關(guān)系分類的類型化社區(qū)發(fā)現(xiàn)方法來確定旅客社會網(wǎng)絡(luò)中的家庭結(jié)構(gòu)。在客運領(lǐng)域的一個真實的數(shù)據(jù)集上進行實驗，證明該方法可以有效地從旅客歷史出行記錄中發(fā)現(xiàn)旅客家庭結(jié)構(gòu)。

旅客社會網(wǎng)絡(luò)；家庭結(jié)構(gòu)；關(guān)系分類；社區(qū)發(fā)現(xiàn)

1　問題的提出

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

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

2　相關(guān)工作

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

關(guān)系分類一直是社會網(wǎng)絡(luò)挖掘中的一個重要研究議題，近年來已經(jīng)產(chǎn)生了許多關(guān)系分類的方法。例如，使用關(guān)系馬爾科夫網(wǎng)來預(yù)測恐怖分子間的關(guān)系類型；利用基于社區(qū)結(jié)構(gòu)的條件隨機場模型來判別社會關(guān)系類型[6]；在異構(gòu)網(wǎng)絡(luò)中推斷社會關(guān)系等。

社區(qū)結(jié)構(gòu)是社會網(wǎng)絡(luò)乃至復(fù)雜網(wǎng)絡(luò)研究中的一個熱點問題，近年來涌現(xiàn)了眾多的社區(qū)發(fā)現(xiàn)算法。一個通用的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法可以看成是一種無監(jiān)督的學(xué)習(xí)方法。大量相關(guān)通用算法不斷涌現(xiàn)，例如最著名的基于模塊度函數(shù)Newman和Girvan方法[7]及其大量變種；基于信息論的Infomap方法[8]，是目前公認(rèn)的準(zhǔn)確率和穩(wěn)定性最高的社區(qū)發(fā)現(xiàn)算法之一。然而，通用社區(qū)發(fā)現(xiàn)算法的目的只是為了找到社區(qū)，而不關(guān)心社區(qū)的類別，因此劃分的社區(qū)不具有可解釋性。

本文將從社會網(wǎng)絡(luò)的視角，基于關(guān)系分類和社區(qū)發(fā)現(xiàn)的思想，從旅客歷史出行記錄中發(fā)現(xiàn)家庭團體。從社會網(wǎng)絡(luò)的視角研究旅客之間的關(guān)系是一項非常有意義的工作。Lin等人[9]曾利用旅客的歷史出行記錄來構(gòu)建旅客社會網(wǎng)絡(luò)，并在此基礎(chǔ)上推斷大規(guī)模旅行團的出行目的，即判斷一個旅行團是商務(wù)團還是旅游團。

3　方法

本節(jié)將針對旅客社會網(wǎng)絡(luò)中的家庭團體發(fā)現(xiàn)方法進行詳細(xì)的闡述。首先，我們根據(jù)旅客歷史出行記錄提取旅客關(guān)系，構(gòu)建旅客共同出行網(wǎng)絡(luò)。然后，構(gòu)建用于旅客關(guān)系分類的特征，包括歷史共同出行特征、人口學(xué)統(tǒng)計特征以及基于網(wǎng)絡(luò)的特征。然后采用協(xié)同分類方法對旅客關(guān)系進行分類。最后，基于關(guān)系分類的結(jié)果，采用兩種社區(qū)發(fā)現(xiàn)的方法來發(fā)現(xiàn)家庭團體。

3.1構(gòu)建共同出行網(wǎng)絡(luò)

我們從這些歷史數(shù)據(jù)中提取旅客間的共同出行關(guān)系，構(gòu)建一種特定類型的大規(guī)模旅客社會網(wǎng)絡(luò)——共同出行網(wǎng)絡(luò)（Co-travel Networks）。該網(wǎng)絡(luò)可以在某種程度上從一個側(cè)面反映旅客之間的社會關(guān)系。旅客間的共同出行關(guān)系可以從旅客共同訂票數(shù)據(jù)中獲取。該網(wǎng)絡(luò)以旅客為節(jié)點，如果旅客間存在共同出行行為，那么就在旅客間構(gòu)建一條邊，并將旅客共同出行的次數(shù)作為邊的權(quán)重。

3.2關(guān)系分類

在部分標(biāo)注的共同出行網(wǎng)絡(luò)中，我們已知小部分的關(guān)系類型標(biāo)簽，需要用這部分關(guān)系作為訓(xùn)練集，學(xué)習(xí)分類器來推斷未知類型的關(guān)系。最直接的方法就是假定所有的標(biāo)簽變量服從獨立同分布，構(gòu)造關(guān)系的各種特征屬性然后利用傳統(tǒng)的分類器進行分類，但在實際的共同出行網(wǎng)絡(luò)中，各變量間存在著依賴關(guān)系。家庭關(guān)系是具有傳遞性的?？紤]到上述依賴性，我們采用條件隨機場對共同出行網(wǎng)絡(luò)中的所有關(guān)系進行協(xié)同分類。

（1）構(gòu)建旅客關(guān)系特征

根據(jù)關(guān)系特征生成機制的不同，我們將旅客關(guān)系特征分為三類：歷史共同出行特征、人口學(xué)統(tǒng)計特征以及基于網(wǎng)絡(luò)的特征。

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

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

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

（2）條件隨機場

條件隨機場是一種用來標(biāo)記序列化結(jié)構(gòu)數(shù)據(jù)的無向圖模型。該模型描述了在給定觀察屬性下的隱藏標(biāo)簽的條件概率。

①構(gòu)建條件隨機場

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

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

②學(xué)習(xí)與推理

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

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

3.3類型化社區(qū)發(fā)現(xiàn)

將介紹如何利用關(guān)系分類的結(jié)果進行類型化社區(qū)發(fā)現(xiàn)，確定旅客共同出行網(wǎng)絡(luò)中的家庭團體。我們分別采用兩種不同的社區(qū)劃分方法，一種是簡單的割邊法，另一種是采用帶權(quán)社區(qū)發(fā)現(xiàn)方法。

（1）割邊

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

（2）帶權(quán)社區(qū)劃分

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

傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法單純基于網(wǎng)絡(luò)中的鏈接結(jié)構(gòu)進行社區(qū)發(fā)現(xiàn)，認(rèn)為網(wǎng)絡(luò)中的所有鏈接都是平等的，相比之下，帶權(quán)的社區(qū)發(fā)現(xiàn)算法還考慮了不同鏈接對于網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)影響的不同，即鏈接權(quán)重的重要作用，因此得出的社區(qū)結(jié)果更加準(zhǔn)確合理。我們采用基于關(guān)系分類的帶權(quán)社區(qū)發(fā)現(xiàn)算法，可以利用網(wǎng)絡(luò)的整體鏈接結(jié)構(gòu)來修正第一種割邊法中因關(guān)系分類錯誤而帶來的偏差，使發(fā)現(xiàn)的家庭團體更加準(zhǔn)確。

4　實驗

在實驗中，我們首先是對網(wǎng)絡(luò)中的邊進行關(guān)系分類，分別采用了傳統(tǒng)的邏輯回歸分類器和條件隨機場協(xié)同分類算法進行二值分類。然后分別采用割邊法和帶權(quán)社區(qū)發(fā)現(xiàn)方法來發(fā)現(xiàn)家庭團體。對于帶權(quán)社區(qū)發(fā)現(xiàn)方法，我們采用目前公認(rèn)準(zhǔn)確率和穩(wěn)定性最高的社區(qū)發(fā)現(xiàn)算法之一的Infomap算法。

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

在條件隨機場的分類結(jié)果基礎(chǔ)上，我們分別用割邊法和帶權(quán)Infomap算法來發(fā)現(xiàn)家庭團體，對家庭團體發(fā)現(xiàn)結(jié)果，割邊法與帶權(quán)社區(qū)發(fā)現(xiàn)方法的評測結(jié)果分別如圖1（a）和圖1（b）所示。

圖1　家庭團體評測

從圖1可以看出，割邊法在閾值為0.6時，發(fā)現(xiàn)家庭團體的效果最好，F(xiàn)1值達(dá)到最大值為0.913；而帶權(quán)社區(qū)劃分方法在閾值為0.3時效果最好，F(xiàn)1值達(dá)到最大值為0.927?？傮w而言，從實驗結(jié)果我們可以得出如下結(jié)論：

（1）針對旅客社會網(wǎng)絡(luò)，構(gòu)建旅客關(guān)系特征并且采用條件隨機場協(xié)同分類方法能夠有效地對旅客間關(guān)系進行分類，并且分類準(zhǔn)確率高于傳統(tǒng)的邏輯回歸方法；

（2）基于關(guān)系分類的帶權(quán)類型化社區(qū)發(fā)現(xiàn)方法可以非常有效地發(fā)現(xiàn)旅客社會網(wǎng)絡(luò)中的家庭團體；

（3）在關(guān)系分類準(zhǔn)確率一定的情況下，帶權(quán)社區(qū)劃分方法要優(yōu)于簡單的割邊法。該方法在利用鏈接結(jié)構(gòu)的同時，也考慮到關(guān)系權(quán)值對網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的影響，并能利用鏈接結(jié)構(gòu)來修正關(guān)系分類的錯誤帶來的偏差，使得社區(qū)劃分結(jié)果更加準(zhǔn)確合理。

5　結(jié)語

本文研究了在客運領(lǐng)域如何利用旅客的歷史出行記錄來發(fā)現(xiàn)家庭團體，提出了一種基于旅客社會網(wǎng)絡(luò)的家庭團體發(fā)現(xiàn)方法。我們首先從旅客的歷史出行記錄中提取旅客共同出行關(guān)系，構(gòu)建旅客共同出行網(wǎng)絡(luò)；然后設(shè)計了一系列旅客關(guān)系特征，并采用條件隨機場協(xié)同分類模型對家庭關(guān)系進行識別；最后，基于關(guān)系分類的結(jié)果分別采用割邊法和帶權(quán)社區(qū)發(fā)現(xiàn)方法來發(fā)現(xiàn)家庭團體。在客運領(lǐng)域的一個真實的旅客歷史出行記錄數(shù)據(jù)集上進行了實驗，實驗結(jié)果表明，我們所提出的方法可以有效地從旅客歷史出行記錄中發(fā)現(xiàn)家庭團體。

[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-），女，河北衡水人，碩士研究生，學(xué)生，研究方向為數(shù)據(jù)與知識工程

2015-03-17

2015-04-20