摘 要：隨著社交網(wǎng)絡(luò)中的地理標(biāo)記信息的增多，傳統(tǒng)的軌跡模式挖掘方法不能處理這些數(shù)據(jù)中豐富的信息。傳統(tǒng)的軌跡模式挖掘算法能根據(jù)GPS數(shù)據(jù)挖掘出人們的移動(dòng)模式，但是無法利用文本信息中上下文相關(guān)的潛在主題來實(shí)現(xiàn)軌跡模式挖掘。本文主要介紹一種基于潛在主題的聚類算法，它能發(fā)現(xiàn)地理標(biāo)記文本信息中的軌跡模式。

關(guān)鍵詞：主題；軌跡模式挖掘；聚類；概率模型

Abstract： With the increasing of geo-tagging messages in social network， traditional trajectory pattern mining methods can not deal with these rich data. Traditional trajectory pattern mining algorithms can find the patterns of peoples movements using GPS data， but latent topics in text messages posted with local contexts have not been utilized. In this paper， a latent topic-based clustering algorithm is introduced. It can find trajectory pattern in geo-tagged text messages.

Keywords： Topic； Trajectory Pattern Mining； Cluster； Probabilistic Model

1 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，社交網(wǎng)絡(luò)在人類生活中的位置越來越重，微博等社交網(wǎng)絡(luò)工具已經(jīng)成為人們交流的一個(gè)重要方式。人們通過移動(dòng)設(shè)備隨時(shí)隨地的對自己的狀態(tài)進(jìn)行更新，隨時(shí)刷新自己的位置，自己在做的事，以及自己的心情。伴隨著用戶生成的媒體中，越來越多的關(guān)于位置信息的文本和照片出現(xiàn)在微博等網(wǎng)絡(luò)媒體中，對于用戶的軌跡模式的挖掘，不僅可以使用用戶的位置信息，還可以使用在這些位置上用戶的行為信息。

對于GPS傳感器收集到的軌跡數(shù)據(jù)進(jìn)行研究，挖掘用戶的軌跡模式一直是很多應(yīng)用的研究重點(diǎn)，這些應(yīng)用需要分析用戶的位置信息，如移動(dòng)導(dǎo)航系統(tǒng)，城市交通分析以及颶風(fēng)追蹤等等。但是這種傳統(tǒng)的軌跡模式挖掘技術(shù)主要是根據(jù)GPS傳感器的數(shù)據(jù)來分析移動(dòng)物體的軌跡模式，這些數(shù)據(jù)非常頻繁，足以支撐對應(yīng)的模式分析對數(shù)據(jù)量的需求。而且，這種軌跡模式的挖掘也不考慮位置信息的語義含義。

在社交網(wǎng)絡(luò)中，對用戶的軌跡模式的分析能為其他用戶提供路線推薦或發(fā)現(xiàn)有趣的軌跡模式，這種軌跡模式挖掘已經(jīng)成為一個(gè)新的研究熱點(diǎn)。但是，在社交網(wǎng)絡(luò)中，由于用戶提供的帶有位置信息的文本和照片是稀疏的，在該信息中，對于語義的理解和表示也存在著差異，因此，對這些具有主題的軌跡模式進(jìn)行分析可以得到很多有用的信息[1]。

本文主要探討在社交網(wǎng)絡(luò)中，對于用戶提供的帶有語義的位置信息進(jìn)行基于主題的軌跡模式挖掘問題。首先介紹軌跡模式挖掘的相關(guān)工作成果，然后分析基于主題的軌跡模式挖掘問題面對的難題，最后介紹一種基于概率模型的主題軌跡模式挖掘方法，并分析其性能。

2 基礎(chǔ)知識

對移動(dòng)對象的GPS數(shù)據(jù)進(jìn)行軌跡模式挖掘已經(jīng)有了廣泛的研究，最初的挖掘算法只使用GPS位置數(shù)據(jù)，這些挖掘算法通常把相似的位置信息進(jìn)行聚類，找到共同的、普通的軌跡模式。有的聚類算法不僅能找出相似軌跡模式的類，還能找出具有相似子軌跡的類。有的算法基于HIT算法發(fā)現(xiàn)共同的軌跡模式，還有算法能找出給定的兩個(gè)位置之間最流行的路徑。然而，這些軌跡模式挖掘算法都僅僅關(guān)注從GPS傳感器得到的數(shù)據(jù)，這些數(shù)據(jù)記錄的位置信息非常頻繁，數(shù)據(jù)量也很大。

隨著網(wǎng)絡(luò)的發(fā)展，在微博等服務(wù)上出現(xiàn)了大量的具有位置標(biāo)記的信息，這些數(shù)據(jù)是稀疏的，并且具有語義信息。為了挖掘這些數(shù)據(jù)中的軌跡模式，軌跡模式挖掘算法不僅需要使用位置數(shù)據(jù)，還要能使用位置的語義信息。最近出現(xiàn)的軌跡模式算法中，有的算法能通過圖片中的GPS位置信息找到語義模式，發(fā)現(xiàn)用戶生成標(biāo)簽的順序模式；有的算法能發(fā)現(xiàn)社交媒體中的多樣性的短軌跡模式；有的算法能基于用戶生成的位置類別，對用戶的軌跡模式進(jìn)行很好的聚類[2]。

使用社交媒體紅的位置標(biāo)記信息挖掘軌跡模式，主要有三個(gè)問題：如何找到主題一致的區(qū)域；如何處理噪音信息；如何解決軌跡模式的稀疏問題[3]。

由于位置標(biāo)記是一對分別表示經(jīng)度和緯度的實(shí)數(shù)，所以首先對相近位置主題相近的位置標(biāo)記信息進(jìn)行聚類，并把這些具有一致主題的區(qū)域稱為語義區(qū)域。由于在微博等服務(wù)上的大部分信息是關(guān)于個(gè)人的，很難把這些信息按同一個(gè)主題來聚類，另外，在帶有噪音的語句信息中挖掘出軌跡模式也使問題的難度加大。

為了從位置標(biāo)記信息中挖掘與主題相關(guān)的軌跡模式，文[4]給出了一個(gè)稱為LGTA的基于概率模型的聚類算法，該算法能把具有相同主題的相似位置的位置標(biāo)記信息進(jìn)行聚類[4]。但是LGTA算法不能處理帶噪音的數(shù)據(jù)，也不能處理軌跡稀疏問題。而TOPTRAC算法不僅能發(fā)現(xiàn)用戶一致主題的潛在的語義區(qū)域，還能發(fā)現(xiàn)在多個(gè)語義區(qū)域內(nèi)用戶的各種移動(dòng)模式，找到用戶參觀一個(gè)區(qū)域的各種的目的。TOPTRAC算法發(fā)現(xiàn)主題一致的語義區(qū)域具有很好的粒度，該算法通過對同一語義區(qū)域中出現(xiàn)過的信息進(jìn)行加權(quán)實(shí)現(xiàn)語義區(qū)域之間的粒度。

3 TOPTRAC算法的概率模型

TOPTRAC算法給出了一個(gè)概率模型來發(fā)現(xiàn)潛在的語義區(qū)域。下面是該模型需要用到的定義、公式及具體的概率模型[5]。

首先給出描述收集到的社交媒體中位置標(biāo)記信息的符號。

定義1 軌跡是指一個(gè)用戶在給定的時(shí)間間隔內(nèi)給出的一組位置標(biāo)記信息的序列。endprint

其中，時(shí)間間隔可以是一天或一周，并且位置標(biāo)記信息是按時(shí)間順序列出的。

設(shè)是N個(gè)軌跡的集合，其中每個(gè)軌跡用表示，。設(shè)是軌跡集合中至少出現(xiàn)一次的詞的序號的集合。因此，軌跡是由個(gè)位置標(biāo)記信息組成的，其中中的第i個(gè)信息表示為。每個(gè)位置標(biāo)記信息由一個(gè)位置標(biāo)記和一個(gè)詞袋組成。其中是一個(gè)二維向量，分別表示位置信息中的緯度和經(jīng)度。是一個(gè)詞袋，包括一共個(gè)詞，而表示中的第j個(gè)詞，并且它是所有詞的集合V中的一個(gè)。

定義2 語義區(qū)域是指一個(gè)由具有相同主題的位置標(biāo)記信息聚類得到的地理位置。

定義3 主題轉(zhuǎn)變模式是在某個(gè)軌跡集合C中的從一個(gè)語義區(qū)域到另一個(gè)語義區(qū)域的移動(dòng)模式。

每個(gè)主題轉(zhuǎn)變模式是指一對實(shí)際的位置標(biāo)記信息，它們表明轉(zhuǎn)變模式中語義區(qū)域的主題。

由于長的軌跡模式在低樣本空間中很少出現(xiàn)，因此TOPTRAC算法專注于挖掘長度為2的軌跡模式。

主題軌跡模式挖掘問題可以定義為：給定一個(gè)位置標(biāo)記信息軌跡的集合C，主題軌跡模式挖掘就是發(fā)現(xiàn)主題轉(zhuǎn)變模式以及最能表示每個(gè)轉(zhuǎn)變模式的top-k轉(zhuǎn)變片段。

TOPTRAC算法的概率模型假設(shè)每個(gè)位置標(biāo)記信息序列都是由用戶獨(dú)立生成的，序列中的每個(gè)位置標(biāo)記信息依靠該序列中該位置標(biāo)記信息前面的信息來處理。假設(shè)位置標(biāo)記信息軌跡的集合C中，有M個(gè)潛在的語義區(qū)域和K個(gè)隱藏的主題。K個(gè)主題在一個(gè)語義區(qū)域r中的分布表示為，其中，是語義區(qū)域r中主題k被選中生成一個(gè)文本信息的概率。一個(gè)主題k在詞匯的集合V上的分布表示為，其中，表示一個(gè)詞t被主題k選中的概率。

假設(shè)表示潛在的語義區(qū)域的隨機(jī)變量，表示為軌跡中中信息選中的潛在主題。對于C中的每個(gè)序列，假設(shè)存在一個(gè)伯努利分布，該分布能反應(yīng)中的每個(gè)位置標(biāo)記信息是否與語義區(qū)域相關(guān)。如果與局部上下文無關(guān)，則隨機(jī)變量=0，否則=1。

如果一個(gè)信息不屬于任何潛在的語義區(qū)域，那么的區(qū)域以概率1/M被選為區(qū)域M中的一個(gè)區(qū)域，的位置標(biāo)記也均勻分布概率生成。如果信息有局部的上下文，則根據(jù)它先前的信息是否與該語義區(qū)域相關(guān)，來選擇一個(gè)潛在的語義區(qū)域。如果信息是序列中的第一個(gè)信息或者它先前的信息與局部的上下文不相關(guān)，則根據(jù)潛在語義區(qū)域M上的類別分布選擇潛在的語義區(qū)域。對于一個(gè)選中的區(qū)域，選擇一個(gè)服從的主題，選擇服從的中的每個(gè)詞。

4 主題軌跡模式挖掘

通過引入隨機(jī)變量可以識別出現(xiàn)在任何位置上的局部無關(guān)的信息，而使用轉(zhuǎn)變概率能對語義區(qū)域進(jìn)行加權(quán)，表示用戶從一個(gè)語義區(qū)域移動(dòng)到另一個(gè)語義區(qū)域的可能性。為了找到最有意義的轉(zhuǎn)變模式，TOPTRAC算法提供一個(gè)動(dòng)態(tài)規(guī)劃算法，能計(jì)算出一個(gè)給定的軌跡的潛在語義區(qū)域的最可能序列。

給定一個(gè)帶有n個(gè)位置標(biāo)記信息的序列，對于信息與局部的上下文無關(guān)的情況，隨機(jī)變量=0，生成序列的最大概率pi由和決定，計(jì)算公式為

。對于

信息由局部的上下文決定的情況，隨機(jī)變量=1，需要分的先前信息是否與該語義區(qū)域相關(guān)兩種情況來選擇最可能的區(qū)域，即=0和=1。對于=0的情況，由于它之前的信息與語義區(qū)域無關(guān)，所以可以不考慮和來計(jì)算最大概率p[i，r，k]。對于=1的情況，由于是依據(jù)和來選擇的，因此，最大概率p[i，r，k]的計(jì)算需要通過枚舉出每一對和生成的最大概率來得到。因此，p[i，r，k]的計(jì)算公式為

由于的計(jì)算不依賴于k，因此它可以通過一次計(jì)算，為后面的算法一直使用。

基于最可能的序列可以發(fā)現(xiàn)頻繁的轉(zhuǎn)變模式，對每個(gè)轉(zhuǎn)變模式，選擇能最好的代表該轉(zhuǎn)變模式的top-k個(gè)轉(zhuǎn)變片段。

5 結(jié)束語

隨著帶有位置標(biāo)記信息的社交網(wǎng)絡(luò)資源的增加，對這些信息進(jìn)行軌跡模式挖掘有了越來越多的應(yīng)用。在對位置標(biāo)記信息進(jìn)行軌跡挖掘過程中，把位置的語義信息也放入到模式挖掘的算法中能提高挖掘的模式的效果，找到更多的讓用戶感興趣的模式。但是能實(shí)現(xiàn)主題軌跡模式挖掘的算法還不是很多，在未來的工作中，可以針對主題軌跡模式挖掘進(jìn)行進(jìn)一步的研究。

參考文獻(xiàn)

[1] 張晨逸，孫建伶，丁軼群.基于 MB-LDA 模型的微博主題挖掘[J].計(jì)算機(jī)研究與發(fā)展，2015， 48（10）：1795-1802

[2] 牛新征，牛嘉郡，蘇大壯等.基于FP-Tree模型的頻繁軌跡模式挖掘方法[J].電子科技大學(xué)學(xué)報(bào)， 2016，45（1）：86～90，134

[3] 王興，蔣新華，蔡偉文等. 基于后綴自動(dòng)機(jī)的軌跡模式挖掘方法[J].計(jì)算機(jī)學(xué)應(yīng)用研究，2016， 33（2）：409-412，416

[4] Z Yin， L Cao， J Han， etc. Geographical topic discovery and comparison[A]. The International Conference of World Wide Web， 2011： 247-256

[5] Y Kim， J Han， C Yuan. TOPTRAC： Topical trajectory pattern mining[A]. Conference on Knowledge Discovery and Data Mining， 2015：587～596

作者簡介

馬愷（1978-），男，副教授，碩士，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘和計(jì)算機(jī)網(wǎng)絡(luò)。endprint