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

邱運(yùn)芬 張暉 李波　楊春明　趙旭劍

摘要 地理位置作為用戶生活軌跡的具體表現(xiàn)，在人群分類中有著舉足輕重的作用。地理位置數(shù)據(jù)具有高維稀疏性，已有人群分類方法需對(duì)位置數(shù)據(jù)進(jìn)行特征選擇并提前確定特征數(shù)，實(shí)際應(yīng)用中存在不便。針對(duì)該問題，提出基于地理位置人群分類的一種非參數(shù)聚類方法。該方法首先利用分層狄利克雷過程（Hierarchical Dirichlet Process，HDP）無監(jiān)督學(xué)習(xí)出最佳特征個(gè)數(shù)；然后利用潛在狄利克雷分布（Latent Dirichlet Allocation，LDA）對(duì)位置數(shù)據(jù)進(jìn)行特征選取，同時(shí)得到功能特征概率矩陣；最后將其作為聚類權(quán)向量計(jì)算用戶間的相似度，利用親和力聚類（Affinity Propagation，AP）實(shí)現(xiàn)人群分類。實(shí)驗(yàn)結(jié)果表明，該方法較傳統(tǒng)方法消耗時(shí)間更少、占用內(nèi)存更低，且同時(shí)具有較高的Fmeasure。

關(guān)鍵詞 地理位置；人群分類；分層狄利克雷過程；潛在狄利克雷分布；親和力聚類

DOI DOI： 10.11907/rjdk.162466

中圖分類號(hào)： TP301

文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào) 文章編號(hào)： 16727800（2017）002000704

0 引言

隨著移動(dòng)設(shè)備的高速發(fā)展和廣泛使用，用戶的地理位置信息通過手機(jī)GPS設(shè)備很容易被獲取。地理位置作為用戶生活軌跡的具體表現(xiàn)，相似的用戶通常會(huì)頻繁出現(xiàn)在相同的地理位置，因此深入挖掘用戶地理位置數(shù)據(jù)，實(shí)現(xiàn)基于地理位置的人群分類具有重要意義。但由于地理位置數(shù)據(jù)具有高維稀疏的特點(diǎn)，如何提前確定最有價(jià)值的分類特征個(gè)數(shù)是進(jìn)行人群分類的主要任務(wù)。

傳統(tǒng)的特征選擇方法，如非負(fù)矩陣分解（Nonnegative Matrix Factorization，NMF）、主成分分析法（Principal Component Analysis，PCA）、奇異值分解（Singular Value Decomposition，SVD）都需要深入挖掘數(shù)據(jù)集的結(jié)構(gòu)和特征，提前確定特征數(shù)量。但在實(shí)際應(yīng)用中，不同的用戶位置數(shù)據(jù)集有不同的最佳特征個(gè)數(shù)，人為確定特征個(gè)數(shù)耗時(shí)耗力，且不能保證該數(shù)據(jù)集的最佳特征個(gè)數(shù)。

針對(duì)上述問題，本文提出一種基于地理位置人群分類的非參數(shù)聚類方法。首先利用分層狄利克雷過程（Hierarchical Dirichlet Process，HDP）訓(xùn)練出最佳的地理位置特征選取數(shù)目，其次利用潛在狄利克雷分布（Latent Dirichlet Allocation，LDA）得到特征概率矩陣；最后，將用戶的特征概率向量作為聚類權(quán)向量，利用親和力聚類（Affinity Propagation，AP）進(jìn)行人群分類。

本文提出一種基于分層狄利克雷過程的地理位置特征提取方法，自動(dòng)獲取特征選取數(shù)目，有效彌補(bǔ)傳統(tǒng)方法需要預(yù)先確定特征個(gè)數(shù)的不足；同時(shí)，計(jì)算用戶在各地理位置特征上的出現(xiàn)概率，以此作為用戶相似性計(jì)算標(biāo)準(zhǔn)，可提高人群分類的準(zhǔn)確率。

1 相關(guān)工作

隨著移動(dòng)設(shè)備的普及，用戶位置數(shù)據(jù)更易獲取。基于地理位置的人群分類的核心思想是：將用戶出現(xiàn)的地理位置坐標(biāo)作為用戶特征，計(jì)算用戶間的相似性。但由于位置數(shù)據(jù)集的高維稀疏性，將所有地理位置坐標(biāo)作為用戶特征進(jìn)行人群分類是不明智的。因此，需針對(duì)不同的數(shù)據(jù)集確定特征數(shù)，在此基礎(chǔ)上選擇聚類特征，實(shí)現(xiàn)人群分類。

部分學(xué)者認(rèn)為同類人群應(yīng)擁有一組相同的地理位置坐標(biāo)，且這組地理位置坐標(biāo)會(huì)頻繁出現(xiàn)，因此可采用頻繁模式[14]挖掘用戶間相同的地理位置坐標(biāo)，以此作為用戶特征計(jì)算用戶相似度。宋衡等[5]針對(duì)3個(gè)年級(jí)的學(xué)生在學(xué)習(xí)、生活中產(chǎn)生的位置數(shù)據(jù)，采用PCA進(jìn)行特征選擇，進(jìn)而進(jìn)行年級(jí)分類。張成[6]提出了基于PCA的單變量貢獻(xiàn)度方法，利用最大似然估計(jì)方法進(jìn)行人群分類。此外，常見的特征選擇方法還有奇異值分解SVD，它常用于圖片壓縮[7]和人臉識(shí)別[8]。張慈祥等[8]為有效降低特征向量的維數(shù)，提高人臉識(shí)別率，提出了一種基于稀疏表示和奇異值分解的人臉識(shí)別算法。但SVD較少使用于空間信息降維。同時(shí)SVD得到的降維矩陣中包含負(fù)值，數(shù)據(jù)可解釋性較差。

綜上所述，現(xiàn)有的特征選擇方法，不能針對(duì)不同的位置數(shù)據(jù)得到最佳的特征個(gè)數(shù)；而在進(jìn)行基于地理位置的人群分類時(shí)，由于地理位置數(shù)據(jù)的高維稀疏性，人為確定最佳特征個(gè)數(shù)在實(shí)際應(yīng)用中較困難。因此，本文提出了一種基于地理位置人群分類的非參數(shù)聚類方法，解決特征選擇中特征數(shù)目須提前確定的問題。同時(shí)，由LDA的方法特性，得到的特征可視為該地理位置坐標(biāo)隱含的功能特征，具有很好的數(shù)據(jù)可解釋性。

2 人群分類方法

本文提出的人群分類方法主要分為3個(gè)步驟：①利用分層狄利克雷過程HDP學(xué)習(xí)位置數(shù)據(jù)集中需提取的特征個(gè)數(shù)K；②利用潛在狄利克雷分布LDA得到K維特征概率矩陣；③將其作為用戶相似性度量標(biāo)準(zhǔn)，使用親和力聚類算法，得到人群分類結(jié)果。

2.1 學(xué)習(xí)特征個(gè)數(shù)

LDA和其它特征選擇方法一樣，都需要人為確定特征的選取數(shù)目K，參數(shù)K的設(shè)置決定特征概率矩陣的維數(shù)，與人群分類結(jié)果息息相關(guān)。因此，本文利用分層狄利克雷過程HDP的非參數(shù)聚類特性，自適應(yīng)不同的位置數(shù)據(jù)集，無監(jiān)督學(xué)習(xí)最佳特征數(shù)目。本文用戶m的位置數(shù)據(jù)文檔表示為um（m=1，2，…，M），其中包含若干地理位置pmn（n=1，2，…，Nm），位置數(shù)據(jù)集中第m篇位置文檔的特征服從θm～Dir（aτ），而每一篇位置文檔的先驗(yàn)τ～GEM（α）可以通過排序指示因子zmn=k獲得，其中，k∈（1，…，K）。最后，地理位置可聚類成K組特征。采用文獻(xiàn)[9]提出的直接后驗(yàn)采樣方法，如式（1）所示：

2.2 特征提取及特征概率計(jì)算

通過分層狄利克雷過程HDP獲取特征個(gè)數(shù)后，利用狄利克雷分布LDA對(duì)位置數(shù)據(jù)集進(jìn)行降維，并利用Gibbs采樣[1011]計(jì)算出用戶在選定特征上的概率矩陣。如果概率越大，則說明用戶出現(xiàn)在該類特征的地理位置坐標(biāo)點(diǎn)越頻繁，從而實(shí)現(xiàn)將高維地理位置數(shù)據(jù)矩陣降維為K維的特征概率矩陣。

在LDA中引入坐標(biāo)點(diǎn)間的真實(shí)地理距離引導(dǎo)特征概率矩陣計(jì)算。遍歷每個(gè)用戶文檔m，并設(shè)置第一個(gè)地理位置為目標(biāo)坐標(biāo)。若當(dāng)前地理坐標(biāo)p與目標(biāo)坐標(biāo)的真實(shí)地理距離超過距離閾值，則將p分配給一個(gè)新特征，并設(shè)置p為目標(biāo)坐標(biāo)；反之，則為p分配與目標(biāo)坐標(biāo)一樣的特征。按照經(jīng)驗(yàn)值，將距離閾值取值為50。最后，利用Gibbs采樣求得特征概率矩陣，如式（2）所示：

2.3 特征概率向量聚類

由于LDA提取的特征可視為地理位置隱含的地區(qū)功能特征，同理，特征概率矩陣則表示用戶在功能特征空間下的出現(xiàn)概率，如果概率越大，則說明用戶出現(xiàn)在該類功能特征的地理位置坐標(biāo)點(diǎn)越多，訪問越頻繁。因此，將特征概率向量作為用戶相似性計(jì)算標(biāo)準(zhǔn)，在降低計(jì)算復(fù)雜度的基礎(chǔ)上，能最大程度保留數(shù)據(jù)的可解釋性。因此，將用戶的特征概率向量作為用戶位置數(shù)據(jù)的低維表示，定義為δ={P（k1），P（k2），…，P（kK）}。其中，P（ki）表示用戶在特征ki所屬地理位置上出現(xiàn)的概率，且P（k1）+P（k2）+…+P（kK）=1。對(duì)其使用親和力聚類算法，即可得到人群分類結(jié)果。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)及數(shù)據(jù)預(yù)處理

本文收集了某地域移動(dòng)用戶在20150813至20151010時(shí)間段內(nèi)，使用位置服務(wù)App所產(chǎn)生的位置數(shù)據(jù)，數(shù)據(jù)中包含經(jīng)度、緯度、App名稱等信息。

在進(jìn)行具體實(shí)驗(yàn)前，首先對(duì)位置數(shù)據(jù)進(jìn)行噪音去除，只包含經(jīng)度約為105～106，緯度約為30～31的數(shù)據(jù)。并從數(shù)據(jù)集中隨機(jī)選取1 000個(gè)用戶的地理位置集進(jìn)行后期實(shí)驗(yàn)。

3.2 評(píng)價(jià)指標(biāo)

大多數(shù)特征選擇方法優(yōu)劣評(píng)判取決于分類結(jié)果的準(zhǔn)確率，而多數(shù)分類方法的準(zhǔn)確率依賴于人工標(biāo)注。而本文從特征選擇方法的性能和分類準(zhǔn)確率兩方面進(jìn)行人群分類結(jié)果評(píng)測(cè)。

（1） 特征選擇方法的性能。從計(jì)算時(shí)間復(fù)雜度和內(nèi)存消耗兩方面進(jìn)行評(píng)測(cè)，對(duì)于某位置數(shù)據(jù)集，優(yōu)秀的特征選擇方法應(yīng)該花費(fèi)較少的內(nèi)存、較短時(shí)間得到相同維度的分類特征。

（2） 分類準(zhǔn)確率：App名稱。通過對(duì)數(shù)據(jù)集進(jìn)行深入分析，采用LDA方法降維后得到的特征與產(chǎn)生該地理位置的App存在聯(lián)系[12]。因此，本文將App名稱作為用戶類型判定的基礎(chǔ)，用于評(píng)測(cè)人群分類的準(zhǔn)確率和召回率，F(xiàn)measure指標(biāo)計(jì)算公式如下。

其中，P表示準(zhǔn)確率，R表示召回率。 通過深入分析，發(fā)現(xiàn)在數(shù)據(jù)集中共包含5種類型的App名稱，如表1所示。

3.4 實(shí)驗(yàn)結(jié)果分析

選取兩種特征選擇方法與本文的LDA進(jìn)行對(duì)比實(shí)驗(yàn)，包括主成分分析PCA、奇異值分解SVD，并將AP[14]作為特征概率矩陣聚類算法。

如前文所述，采用特征選擇方法的性能和分類結(jié)果的Fmeasure作為評(píng)測(cè)標(biāo)準(zhǔn)。首先將特征選擇方法運(yùn)行時(shí)間和內(nèi)存消耗作為性能評(píng)價(jià)指標(biāo)，實(shí)驗(yàn)結(jié)果如表2所示。

本文首先采用分層狄利克雷HDP自適應(yīng)特征數(shù)目，其次采用狄利克雷分布計(jì)算特征概率矩陣，在時(shí)間消耗和內(nèi)存消耗上均遠(yuǎn)遠(yuǎn)小于PCA和SVD。然后，從人群分類的準(zhǔn)確率出發(fā)，驗(yàn)證將特征概率作為用戶相似性計(jì)算標(biāo)準(zhǔn)是否能有效提高分類準(zhǔn)確率。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 3種算法的Fmeasure

如圖3所示，將LDA得到的特征概率向量作為特征進(jìn)行人群分類，其人群分類結(jié)果的Fmeasure高于其它兩種特征選擇方法。同時(shí)，PCA和SVD需要提前確認(rèn)特征選擇的數(shù)目，且特征個(gè)數(shù)的取值與分類結(jié)果相關(guān)。而本文提出的人群分類方法不需要提前確定功能特征數(shù)目，能根據(jù)不同的位置數(shù)據(jù)集得到不同的、最佳的特征個(gè)數(shù)；其次，將特征概率作為用戶相似性度量標(biāo)準(zhǔn)，考慮了用戶在不同類型特征下的不確定性。綜上所述，本文提出的人群分類方法表現(xiàn)更優(yōu)。

4 結(jié)語(yǔ)

由于地理位置數(shù)據(jù)集具備高維稀疏性，直接基于地理位置數(shù)據(jù)矩陣進(jìn)行人群分類計(jì)算復(fù)雜，內(nèi)存消耗大。而傳統(tǒng)的特征選擇方法需根據(jù)數(shù)據(jù)的結(jié)構(gòu)和特性，人為確定特征數(shù)目，難以確定最佳特征數(shù)目。本文提出一種自適應(yīng)不同位置數(shù)據(jù)集、無監(jiān)督學(xué)習(xí)最佳特征數(shù)的人群分類方法。相較于傳統(tǒng)的特征選擇算法，本文方法不需要人為確定特征數(shù)量，可根據(jù)不同的位置數(shù)據(jù)集無監(jiān)督學(xué)習(xí)出適合的特征數(shù)量，無需深入分析數(shù)據(jù)結(jié)構(gòu)特性。同時(shí)，根據(jù)潛在狄利克雷分布LDA的特性，所得到的特征可視為地理位置的功能特征，以用戶訪問功能特征的概率作為用戶相似性判斷標(biāo)準(zhǔn)，發(fā)現(xiàn)的同類用戶相似性更加明顯，且計(jì)算時(shí)間和內(nèi)存消耗度都遠(yuǎn)優(yōu)于傳統(tǒng)特征選擇方法。

后續(xù)研究中，將考慮加入時(shí)間屬性，研究用戶在時(shí)間維度上的特征變化軌跡，進(jìn)一步挖掘用戶行為模式及用戶特征變化軌跡的相似性。

參考文獻(xiàn) 參考文獻(xiàn)：

[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] 宋衡.基于位置數(shù)據(jù)的人類行為識(shí)別和相似性研究[D].上海：上海交通大學(xué)，2014.

[6] 張成，劉亞東，謝彥紅.基于PCA與MLE方法的人群分類新方法研究[J].沈陽(yáng)：沈陽(yáng)化工大學(xué)學(xué)報(bào)：自然科學(xué)版，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] 張慈祥，劉輝，強(qiáng)振平.基于稀疏表示和奇異值分解的人臉識(shí)別[J].計(jì)算機(jī)應(yīng)用，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.

（責(zé)任編輯：陳福時(shí)）