涂巖愷

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

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

涂巖愷1，2

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

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

行為相似性；LBS簽到點(diǎn)；模式匹配；Housdroff距離

0 引言

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

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

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

相對(duì)于完全依靠簽到位置時(shí)間先后順序的軌跡信息，或完全拋開時(shí)間順序的點(diǎn)集匹配，都不能達(dá)到實(shí)際需求.因此需要將離散化的時(shí)間信息與位置信息充分融合處理，盡量保留有用的時(shí)間信息，又不會(huì)因?yàn)楹灥綍r(shí)間間隔太遠(yuǎn)導(dǎo)致誤導(dǎo)用戶軌跡.

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

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

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

2 時(shí)空模式匹配

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

兩個(gè)獨(dú)立點(diǎn)P1與P2之間的相似性距離Ds直接取地理直線距離：

獨(dú)立點(diǎn)Pi與秩次子集之間的相似性距離Db計(jì)算公式如下：

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

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

3 用戶行為相似性比較

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

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

4 結(jié)語

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

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

圖1 實(shí)驗(yàn)結(jié)果比較

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

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

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

[4]劉樹棟，孟祥武.一種基于移動(dòng)用戶位置的網(wǎng)絡(luò)服務(wù)推薦方法[J].軟件學(xué)報(bào)，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.

（責(zé)任編輯 李健飛）

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

廈門市科技計(jì)劃項(xiàng)目（3502Z20130008）

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