一種基于地理位置人群分類的非參數聚類方法

邱運芬 張暉 李波　楊春明　趙旭劍

摘要 地理位置作為用戶生活軌跡的具體表現，在人群分類中有著舉足輕重的作用。地理位置數據具有高維稀疏性，已有人群分類方法需對位置數據進行特征選擇并提前確定特征數，實際應用中存在不便。針對該問題，提出基于地理位置人群分類的一種非參數聚類方法。該方法首先利用分層狄利克雷過程（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.

（責任編輯：陳福時）