基于主題的軌跡模式挖掘

摘 要：隨著社交網絡中的地理標記信息的增多，傳統的軌跡模式挖掘方法不能處理這些數據中豐富的信息。傳統的軌跡模式挖掘算法能根據GPS數據挖掘出人們的移動模式，但是無法利用文本信息中上下文相關的潛在主題來實現軌跡模式挖掘。本文主要介紹一種基于潛在主題的聚類算法，它能發現地理標記文本信息中的軌跡模式。

關鍵詞：主題；軌跡模式挖掘；聚類；概率模型

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 引言

隨著網絡技術的發展，社交網絡在人類生活中的位置越來越重，微博等社交網絡工具已經成為人們交流的一個重要方式。人們通過移動設備隨時隨地的對自己的狀態進行更新，隨時刷新自己的位置，自己在做的事，以及自己的心情。伴隨著用戶生成的媒體中，越來越多的關于位置信息的文本和照片出現在微博等網絡媒體中，對于用戶的軌跡模式的挖掘，不僅可以使用用戶的位置信息，還可以使用在這些位置上用戶的行為信息。

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

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

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

2 基礎知識

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

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

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

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

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

3 TOPTRAC算法的概率模型

TOPTRAC算法給出了一個概率模型來發現潛在的語義區域。下面是該模型需要用到的定義、公式及具體的概率模型[5]。

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

定義1 軌跡是指一個用戶在給定的時間間隔內給出的一組位置標記信息的序列。endprint

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

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

定義2 語義區域是指一個由具有相同主題的位置標記信息聚類得到的地理位置。

定義3 主題轉變模式是在某個軌跡集合C中的從一個語義區域到另一個語義區域的移動模式。

每個主題轉變模式是指一對實際的位置標記信息，它們表明轉變模式中語義區域的主題。

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

主題軌跡模式挖掘問題可以定義為：給定一個位置標記信息軌跡的集合C，主題軌跡模式挖掘就是發現主題轉變模式以及最能表示每個轉變模式的top-k轉變片段。

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

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

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

4 主題軌跡模式挖掘

通過引入隨機變量可以識別出現在任何位置上的局部無關的信息，而使用轉變概率能對語義區域進行加權，表示用戶從一個語義區域移動到另一個語義區域的可能性。為了找到最有意義的轉變模式，TOPTRAC算法提供一個動態規劃算法，能計算出一個給定的軌跡的潛在語義區域的最可能序列。

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

。對于

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

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

基于最可能的序列可以發現頻繁的轉變模式，對每個轉變模式，選擇能最好的代表該轉變模式的top-k個轉變片段。

5 結束語

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

參考文獻

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

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

[3] 王興，蔣新華，蔡偉文等. 基于后綴自動機的軌跡模式挖掘方法[J].計算機學應用研究，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-），男，副教授，碩士，主要研究領域為數據挖掘和計算機網絡。endprint