一种基于地理位置人群分类的非参数聚类方法

邱运芬 张晖 李波　杨春明　赵旭剑

摘要 地理位置作为用户生活轨迹的具体表现，在人群分类中有着举足轻重的作用。地理位置数据具有高维稀疏性，已有人群分类方法需对位置数据进行特征选择并提前确定特征数，实际应用中存在不便。针对该问题，提出基于地理位置人群分类的一种非参数聚类方法。该方法首先利用分层狄利克雷过程（Hierarchical Dirichlet Process，HDP）无监督学习出最佳特征个数；然后利用潜在狄利克雷分布（Latent Dirichlet Allocation，LDA）对位置数据进行特征选取，同时得到功能特征概率矩阵；最后将其作为聚类权向量计算用户间的相似度，利用亲和力聚类（Affinity Propagation，AP）实现人群分类。实验结果表明，该方法较传统方法消耗时间更少、占用内存更低，且同时具有较高的Fmeasure。

关键词 地理位置；人群分类；分层狄利克雷过程；潜在狄利克雷分布；亲和力聚类

DOI DOI： 10.11907/rjdk.162466

中图分类号： TP301

文献标识码： A 文章编号 文章编号： 16727800（2017）002000704

0 引言

随着移动设备的高速发展和广泛使用，用户的地理位置信息通过手机GPS设备很容易被获取。地理位置作为用户生活轨迹的具体表现，相似的用户通常会频繁出现在相同的地理位置，因此深入挖掘用户地理位置数据，实现基于地理位置的人群分类具有重要意义。但由于地理位置数据具有高维稀疏的特点，如何提前确定最有价值的分类特征个数是进行人群分类的主要任务。

传统的特征选择方法，如非负矩阵分解（Nonnegative Matrix Factorization，NMF）、主成分分析法（Principal Component Analysis，PCA）、奇异值分解（Singular Value Decomposition，SVD）都需要深入挖掘数据集的结构和特征，提前确定特征数量。但在实际应用中，不同的用户位置数据集有不同的最佳特征个数，人为确定特征个数耗时耗力，且不能保证该数据集的最佳特征個数。

针对上述问题，本文提出一种基于地理位置人群分类的非参数聚类方法。首先利用分层狄利克雷过程（Hierarchical Dirichlet Process，HDP）训练出最佳的地理位置特征选取数目，其次利用潜在狄利克雷分布（Latent Dirichlet Allocation，LDA）得到特征概率矩阵；最后，将用户的特征概率向量作为聚类权向量，利用亲和力聚类（Affinity Propagation，AP）进行人群分类。

本文提出一种基于分层狄利克雷过程的地理位置特征提取方法，自动获取特征选取数目，有效弥补传统方法需要预先确定特征个数的不足；同时，计算用户在各地理位置特征上的出现概率，以此作为用户相似性计算标准，可提高人群分类的准确率。

1 相关工作

随着移动设备的普及，用户位置数据更易获取。基于地理位置的人群分类的核心思想是：将用户出现的地理位置坐标作为用户特征，计算用户间的相似性。但由于位置数据集的高维稀疏性，将所有地理位置坐标作为用户特征进行人群分类是不明智的。因此，需针对不同的数据集确定特征数，在此基础上选择聚类特征，实现人群分类。

部分学者认为同类人群应拥有一组相同的地理位置坐标，且这组地理位置坐标会频繁出现，因此可采用频繁模式[14]挖掘用户间相同的地理位置坐标，以此作为用户特征计算用户相似度。宋衡等[5]针对3个年级的学生在学习、生活中产生的位置数据，采用PCA进行特征选择，进而进行年级分类。张成[6]提出了基于PCA的单变量贡献度方法，利用最大似然估计方法进行人群分类。此外，常见的特征选择方法还有奇异值分解SVD，它常用于图片压缩[7]和人脸识别[8]。张慈祥等[8]为有效降低特征向量的维数，提高人脸识别率，提出了一种基于稀疏表示和奇异值分解的人脸识别算法。但SVD较少使用于空间信息降维。同时SVD得到的降维矩阵中包含负值，数据可解释性较差。

综上所述，现有的特征选择方法，不能针对不同的位置数据得到最佳的特征个数；而在进行基于地理位置的人群分类时，由于地理位置数据的高维稀疏性，人为确定最佳特征个数在实际应用中较困难。因此，本文提出了一种基于地理位置人群分类的非参数聚类方法，解决特征选择中特征数目须提前确定的问题。同时，由LDA的方法特性，得到的特征可视为该地理位置坐标隐含的功能特征，具有很好的数据可解释性。

2 人群分类方法

本文提出的人群分类方法主要分为3个步骤：①利用分层狄利克雷过程HDP学习位置数据集中需提取的特征个数K；②利用潜在狄利克雷分布LDA得到K维特征概率矩阵；③将其作为用户相似性度量标准，使用亲和力聚类算法，得到人群分类结果。

2.1 学习特征个数

LDA和其它特征选择方法一样，都需要人为确定特征的选取数目K，参数K的设置决定特征概率矩阵的维数，与人群分类结果息息相关。因此，本文利用分层狄利克雷过程HDP的非参数聚类特性，自适应不同的位置数据集，无监督学习最佳特征数目。本文用户m的位置数据文档表示为um（m=1，2，…，M），其中包含若干地理位置pmn（n=1，2，…，Nm），位置数据集中第m篇位置文档的特征服从θm～Dir（aτ），而每一篇位置文档的先验τ～GEM（α）可以通过排序指示因子zmn=k获得，其中，k∈（1，…，K）。最后，地理位置可聚类成K组特征。采用文献[9]提出的直接后验采样方法，如式（1）所示：

2.2 特征提取及特征概率计算

通过分层狄利克雷过程HDP获取特征个数后，利用狄利克雷分布LDA对位置数据集进行降维，并利用Gibbs采样[1011]计算出用户在选定特征上的概率矩阵。如果概率越大，则说明用户出现在该类特征的地理位置坐标点越频繁，从而实现将高维地理位置数据矩阵降维为K维的特征概率矩阵。

在LDA中引入坐标点间的真实地理距离引导特征概率矩阵计算。遍历每个用户文档m，并设置第一个地理位置为目标坐标。若当前地理坐标p与目标坐标的真实地理距离超过距离阈值，则将p分配给一个新特征，并设置p为目标坐标；反之，则为p分配与目标坐标一样的特征。按照经验值，将距离阈值取值为50。最后，利用Gibbs采样求得特征概率矩阵，如式（2）所示：

2.3 特征概率向量聚类

由于LDA提取的特征可视为地理位置隐含的地区功能特征，同理，特征概率矩阵则表示用户在功能特征空间下的出现概率，如果概率越大，则说明用户出现在该类功能特征的地理位置坐标点越多，访问越频繁。因此，将特征概率向量作为用户相似性计算标准，在降低计算复杂度的基础上，能最大程度保留数据的可解释性。因此，将用户的特征概率向量作为用户位置数据的低维表示，定义为δ={P（k1），P（k2），…，P（kK）}。其中，P（ki）表示用户在特征ki所属地理位置上出现的概率，且P（k1）+P（k2）+…+P（kK）=1。对其使用亲和力聚类算法，即可得到人群分类结果。

3 实验

3.1 实验数据及数据预处理

本文收集了某地域移动用户在20150813至20151010时间段内，使用位置服务App所产生的位置数据，数据中包含经度、纬度、App名称等信息。

在进行具体实验前，首先对位置数据进行噪音去除，只包含经度约为105～106，纬度约为30～31的数据。并从数据集中随机选取1 000个用户的地理位置集进行后期实验。

3.2 评价指标

大多数特征选择方法优劣评判取决于分类结果的准确率，而多数分类方法的准确率依赖于人工标注。而本文从特征选择方法的性能和分类准确率两方面进行人群分类结果评测。

（1） 特征选择方法的性能。从计算时间复杂度和内存消耗两方面进行评测，对于某位置数据集，优秀的特征选择方法应该花费较少的内存、较短时间得到相同维度的分类特征。

（2） 分类准确率：App名称。通过对数据集进行深入分析，采用LDA方法降维后得到的特征与产生该地理位置的App存在联系[12]。因此，本文将App名称作为用户类型判定的基础，用于评测人群分类的准确率和召回率，Fmeasure指标计算公式如下。

其中，P表示准确率，R表示召回率。 通过深入分析，发现在数据集中共包含5种类型的App名称，如表1所示。

3.4 实验结果分析

选取两种特征选择方法与本文的LDA进行对比实验，包括主成分分析PCA、奇异值分解SVD，并将AP[14]作为特征概率矩阵聚类算法。

如前文所述，采用特征选择方法的性能和分类结果的Fmeasure作为评测标准。首先将特征选择方法运行时间和内存消耗作为性能评价指标，实验结果如表2所示。

本文首先采用分层狄利克雷HDP自适应特征数目，其次采用狄利克雷分布计算特征概率矩阵，在时间消耗和内存消耗上均远远小于PCA和SVD。然后，从人群分类的准确率出发，验证将特征概率作为用户相似性计算标准是否能有效提高分类准确率。实验结果如图3所示。

图3 3种算法的Fmeasure

如图3所示，将LDA得到的特征概率向量作为特征进行人群分类，其人群分类结果的Fmeasure高于其它两种特征选择方法。同时，PCA和SVD需要提前确认特征选择的数目，且特征个数的取值与分类结果相关。而本文提出的人群分类方法不需要提前确定功能特征数目，能根据不同的位置数据集得到不同的、最佳的特征个数；其次，将特征概率作为用户相似性度量标准，考虑了用户在不同类型特征下的不确定性。综上所述，本文提出的人群分类方法表现更优。

4 结语

由于地理位置数据集具备高维稀疏性，直接基于地理位置数据矩阵进行人群分类计算复杂，内存消耗大。而传统的特征选择方法需根据数据的结构和特性，人为确定特征数目，难以确定最佳特征数目。本文提出一种自适应不同位置数据集、无监督学习最佳特征数的人群分类方法。相较于传统的特征选择算法，本文方法不需要人为确定特征数量，可根据不同的位置数据集无监督学习出适合的特征数量，无需深入分析数据结构特性。同时，根据潜在狄利克雷分布LDA的特性，所得到的特征可视为地理位置的功能特征，以用户访问功能特征的概率作为用户相似性判斷标准，发现的同类用户相似性更加明显，且计算时间和内存消耗度都远优于传统特征选择方法。

后续研究中，将考虑加入时间属性，研究用户在时间维度上的特征变化轨迹，进一步挖掘用户行为模式及用户特征变化轨迹的相似性。

参考文献 参考文献：

[1] XUE AY，ZHANG RUI，ZHENG YU，et al.Destination prediction subtrajectory synthesis and privacy protection against such prediction [C].Proceedings of the 29th International Conference.Brisbane，ICDE，2013：254265.

[2] ZHENG KAI，ZHENG YU，YUAN NJ.Discovery of gathering patterns from trajectories [C].Proceedings of the 29th International Conference.Brisbane：IEEE，2013：242253.

[3] TANG LUAN，ZHENG YU，YUAN JING，et al.On discovery of traveling companions from streaming trajectories[C].Proceedings of the 2012 IEEE 28th International Conference on Data Engineering.Washington：IEEE，2012：186197.

[4] SHENG CHANG，ZHENG YU，HSU WYNNE，et al.Answering topk similar region queries[C].//Proceedings of the 15th International Conference.Japan：DASFAA，2010：186201.

[5] 宋衡.基于位置数据的人类行为识别和相似性研究[D].上海：上海交通大学，2014.

[6] 张成，刘亚东，谢彦红.基于PCA与MLE方法的人群分类新方法研究[J].沈阳：沈阳化工大学学报：自然科学版，2015，29（2）：168171.

[7] AWWAL MOHAMMED RURAI，GHOLAMREZA ANBARJAFARI，HASAN DEMIREL.Lossy image compression using singular value decomposition and wavelet difference reduction[J].Digital Signal Processing，2014（24）：117123.

[8] 张慈祥，刘辉，强振平.基于稀疏表示和奇异值分解的人脸识别[J].计算机应用，2013（1）：233235.

[9] HEINRICH G.Infinite LDA implementing the HDP with minimum code complexity[EB/OL].http：//arbylon.net/publications/ilda.pdf.

[10] LI CHENGTA，ZHANG JIANWEN，SUN JIANTA，et al.Sentiment topic model with decomposed prior [C].Proceedings of the 2013 SIAM International Conference on Data Mining.Austin，USA：SIAM，2013：767–776.

[11] LIN CHENGHUA，HE YULAN，RICHARD EVERSON，et al.Weakly supervised joint sentimenttopic detection from text [J].IEEE Transactions on Knowledge and Data Engineering，2012，24（6）：11341145.

[12] TOOLE JL，ULM M，GONZALEZ MC，et al.Inferring land from mobile phone activity [C].Proceedings of the ACM SIGKDD International Workshop on Urban Computing.New York：ACM，2012：18.

[13] YANG GUANGBING，WEN DUNWEI，KINSHUK，et al.A novel contextual topic model for multidocument summarization[J].Expert Systems with Applications，2015，42（3）：13401352.

[14] BRENDAN J.FREY，DELLBERT DUERK.Clustering by passing messages between data points[J].Science，2007，315（5814）：972976.

（責任编辑：陈福时）