旅客群体中的家庭结构发现

王志伟（北京交通大学计算机与信息技术学院，交通数据分析与挖掘北京市重点实验室，北京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