LBS 用戶簽到行為相似性匹配

涂巖愷

（1.廈門雅迅網(wǎng)絡股份有限公司，福建廈門361008；2.中國電子科技集團第三十研究所，四川成都610041）

LBS 用戶簽到行為相似性匹配

涂巖愷1，2

（1.廈門雅迅網(wǎng)絡股份有限公司，福建廈門361008；2.中國電子科技集團第三十研究所，四川成都610041）

針對簽到點數(shù)據(jù)不穩(wěn)定，時間跨度大的特征，提出融合時空模式Housdorff距離匹配的方法來衡量LBS用戶行為的相似性，通過實驗比較，效果要優(yōu)于傳統(tǒng)方法.

行為相似性；LBS簽到點；模式匹配；Housdroff距離

0 引言

在互聯(lián)網(wǎng)中，LBS（基于位置的服務）應用每天都會產(chǎn)生大量的簽到數(shù)據(jù).這些數(shù)據(jù)包括時間、位置、簽到點POI屬性等信息，反映了用戶真實的生活軌跡與興趣傾向.對這些基于社交網(wǎng)絡的簽到數(shù)據(jù)進行挖掘，尋找行為興趣相似的人群可以定量和估算人們的社會活動特征，進而發(fā)掘人們的行為規(guī)律，使人們能夠更深層地認知智能化城市中社群的生活軌跡、社交行為、環(huán)境變動等，不僅能夠滿足用戶越來越強烈的個性化、社會化需求，而且能夠為智能商務、個性化推薦提供支持.

由于用戶的簽到記錄是不連貫和碎片化的，時間間隔可能為幾分鐘、幾小時甚至幾天幾個月，在這樣復雜的簽到率下難以還原出用戶的真實行動軌跡，因此采用網(wǎng)格或交通路網(wǎng)匹配的方式試圖還原用戶簽到點之間的軌跡[1，2]，這類方法在簽到點時間間隔較長的情況下會不可避免的產(chǎn)生軌跡估算誤差.通過主題相似性判斷用戶行為相似性[3]，這類方法也要求用戶簽到點時間間隔不能隔的太遠，否則隔幾個月的簽到本身不具有什么主題意義聯(lián)系.如果不恢復用戶軌跡，直接用點集空間關系的相似性進行用戶行為相似性匹配的方法忽略了簽到點的先后時間關系，時間間隔較近的簽到點順序隱含了用戶的行為順序與興趣優(yōu)先信息[4].筆者用簽到點集的時空模式匹配方法進行數(shù)據(jù)的用戶行為挖掘，將同一天內(nèi)的簽到時間順序與簽到點位置數(shù)據(jù)進行融合，提出一種新的融合時空模式的Hausdorff距離匹配方法進行有效的相似判別，無需進行簽到點間的行為軌跡恢復，同時有效的利用了簽到時間順序信息.

1 時空數(shù)據(jù)融合

相對于完全依靠簽到位置時間先后順序的軌跡信息，或完全拋開時間順序的點集匹配，都不能達到實際需求.因此需要將離散化的時間信息與位置信息充分融合處理，盡量保留有用的時間信息，又不會因為簽到時間間隔太遠導致誤導用戶軌跡.

假設某個LBS用戶所有原始簽到點集合按時間順序排列為{P1，P2，P3，...，PM}，每個Pi={x，y，t}（i=1，2，...，M）包含經(jīng)緯度位置信息（x，y）與時間信息t.將簽到點集合經(jīng)處理分成兩類：

1）秩次子集：根據(jù)時間信息t，從Pi中提取出屬于一天（從當天0∶00∶00到23∶59∶59，一般人的生活規(guī)律以天為單位，因此這里也以天為區(qū)間分割出秩次子集）的簽到點構成單獨的子集合Qj={Pj，Pj+1，Pj+2，...，Pj+N}（N≤M），對于構成子集合Qj內(nèi)的簽到點賦予秩次權值rank，即Qj內(nèi)按時間順序第1個簽到點秩次為rank=1，第2個簽到點秩次為rank=2，以此類推，獲得秩次后去除時間信息t，得到新的秩次子集合這樣就將1天內(nèi)連續(xù)簽到的位置與相對時間順序信息融合保留了下來.

2）孤立點：對于不構成子集合的簽到點Pi之間，由于時間隔過遠（大于1天），在時間聯(lián)系上的意義較弱，因此去除時間信息，只保留位置信息，形成孤立簽到點Pi=（x，y）.

2 時空模式匹配

綜合考慮孤立點之間、秩次子集之間，以及孤立點與秩次子集之間的相似性距離，設假用d（P1，P2）表示點P1點與P2點對應位置（x1，y1）與（x2，y2）的地理直線距離，則：

兩個獨立點P1與P2之間的相似性距離Ds直接取地理直線距離：

獨立點Pi與秩次子集之間的相似性距離Db計算公式如下：

在計算孤立點與秩次子集的距離時，利用秩次信息拉大了它們之間的距離，突顯了時間順序差別的特征.在特殊情況下，秩次子集點個數(shù)為1的時候，秩次子集退化為孤立點，（2）式中N=0，rank=1，等價于（1）式，說明孤立點是秩次子集個數(shù)為1時的特殊形式.

在計算帶秩次的點對P′i與P′j的距離時，需要融合秩次相似性權重值wi，j=｜ranki-rankj｜+1，則（4）式中的按如下方法計算：

3 用戶行為相似性比較

設兩個用戶UserA和UserB的簽到集合經(jīng)時空數(shù)據(jù)融合處理后變換為分別包含若干孤立點與若干秩次子集的集合則兩個用戶間的行為相似性比較方法如下：

公式（6）是典型Hausdorff距離公式，但是在具體計算集合內(nèi)部元素距離的時候分別考慮與孤立點與孤立點、孤立點與秩次子集、秩次子集與秩次子集的情況，融合了空間位置與時間秩次信息，因此本文方法本質上是擴展了典型Hausdorff距離方法[5].相似性度量值H值越小，表明用戶簽到行為相似性越高，依據(jù)H值的大小，可以從大量用戶數(shù)據(jù)的比較中得出與當前查詢用戶最相似的用戶（即H值最小的用戶），實現(xiàn)用戶簽到行為相似性挖掘.

4 結語

由于難以準確衡量不同用戶是否真的興趣相似，因此我們實驗測試時采用同一個人不同時段的簽到數(shù)據(jù)進行比較檢索.實驗所有數(shù)據(jù)來源于廈門雅迅網(wǎng)絡股份有限公司“八千優(yōu)惠”LBS應用[6]，用戶數(shù)量20 237個，采用2012年歷史數(shù)據(jù)進行挖掘實驗，平均每個用戶40個以上簽到點.2012年6月之前簽到數(shù)據(jù)做為數(shù)據(jù)庫樣本，2012年6月之后簽到數(shù)據(jù)做為測試樣本.利用測試樣本在數(shù)據(jù)庫樣本中比對，并按相似性排序比對結果，統(tǒng)計同一人的數(shù)據(jù)庫樣本與測試樣本相似性排序在第一位的比率.

本文時空模式方法與軌跡方法、主題相似方法、點集匹配方法的匹配正確率如圖1所示，對于這類高離散化的簽到點行為，軌跡法效果最差，更適合采用本文時空模式融合匹配，取得更為理想的實驗結果.但從實驗也看的出來，由于簽到行為本身具有不穩(wěn)定性，受簽到數(shù)據(jù)質量的影響，依據(jù)簽到行為進行相似度判斷的準確率還不夠高，還沒超過40%，只能在協(xié)同推薦系統(tǒng)中起輔助作用，如果需要高精度挖掘用戶行為相似性，必須在后續(xù)研究中融合其它穩(wěn)定特征.

圖1 實驗結果比較

[1]鄭宇，謝幸.基于用戶軌跡挖掘的智能位置服務[J].中國計算機學會通訊，2010，6（6）：23-30.

[2]鄒永貴，萬建斌，夏英.基于路網(wǎng)的LBSN用戶移動軌跡聚類挖掘方法[J].計算機應用研究，2013，30（8）：2410-2414.

[3]閆光輝，舒昕，馬志程，等.基于主題和鏈接分析的微博社區(qū)發(fā)現(xiàn)算法[J].計算機應用研究，2013，30（7）：1953-1957.

[4]劉樹棟，孟祥武.一種基于移動用戶位置的網(wǎng)絡服務推薦方法[J].軟件學報，2014（11）：2556-2574.

[5]HUTTENLOCHERDP，KLANDERMANGA，RucklidgeWJ.ComparingImagesUsingtheHausdorffDistance[J].PatternAnalysisand MachineIntelligence，IEEETransactionson，1993，15（9）：850-863.

[6]陳典全.LBS中基于軌跡的用戶行為特征分析[J].全球定位系統(tǒng)，2012，36（6）：58-61.

（責任編輯 李健飛）

LBS User's Checking Behavior Similarity Matching

TU Yan-kai1，2
（1.Xiamen Yaxon Network Co.，Ltd.，Xiamen，F(xiàn)ujian 361008，China；2.The 30th Research Institute of China Electronics Technology Group Corporation，Chengdu，Sichuan 610041，China）

According to the characters of instability and large time span of checking points，a time-space fusion matching method based on Housdroff distance is proposed to measure LBS user′s checking behavior similarity.Experiments show that the method has better performance than traditional methods.

behavior similarity；LBS checking point；pattern matching；Hausdroff distance

T391

：A

：1673-1972（2015）06-0044-03

2015-04-03

廈門市科技計劃項目（3502Z20130008）

涂巖愷（1983-），男，福建永安人，工程師，博士，主要從事信號與信息處理研究.