張澤西，汪 蕓

(1.東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189;2.東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息集成教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 211189)

0 引言

在智能城市的遠(yuǎn)景規(guī)劃下，手機(jī)網(wǎng)絡(luò)正在逐漸成長(zhǎng)為一個(gè)巨大的無處不在的感知平臺(tái)。這得益于手機(jī)在全世界范圍內(nèi)尤其是人口稠密的城市地區(qū)極高的持有率，由于與人類活動(dòng)緊密的連通性，使得越來越多的大規(guī)模應(yīng)用和研究通過手機(jī)網(wǎng)絡(luò)提供的數(shù)據(jù)對(duì)人類群體和個(gè)體的屬性進(jìn)行分析，比如理解用戶行為［1-2］、城市不同地區(qū)的活動(dòng)類型［3］、預(yù)測(cè)用戶位置［4］等。其研究手段往往是通過對(duì)記錄在基站網(wǎng)絡(luò)上的用戶呼叫詳細(xì)記錄(Call Detail Records，CDRs)數(shù)據(jù)集進(jìn)行分析和數(shù)據(jù)挖掘。相似用戶查詢作為一種數(shù)據(jù)分析的基本方法，返回與被查詢的興趣用戶最相似的K個(gè)用戶，可應(yīng)用于用戶分群、異常檢測(cè)、基于用戶的推薦、觀察特定用戶群體行為特征等方向。大多數(shù)針對(duì)CDR的分析和查詢假設(shè)數(shù)據(jù)為中心存儲(chǔ)，即數(shù)據(jù)中心需要定期收集CDR數(shù)據(jù)進(jìn)行集中存儲(chǔ)，再在這些歷史數(shù)據(jù)上進(jìn)行查詢。然而，CDR數(shù)據(jù)在手機(jī)網(wǎng)絡(luò)中為分布式產(chǎn)生和存儲(chǔ)，用戶的每一次手機(jī)接入電信網(wǎng)的操作(接打電話、收發(fā)短信)，都會(huì)在連接的基站(Cell)上產(chǎn)生一條CDR記錄用于記賬系統(tǒng)進(jìn)行計(jì)費(fèi)服務(wù)。因此一個(gè)用戶在一段時(shí)間內(nèi)的所有通信數(shù)據(jù)可能分布地存儲(chǔ)于多個(gè)不同的基站上。即使在一天之中，一個(gè)用戶在不同時(shí)間產(chǎn)生的CDR記錄也可能存儲(chǔ)于不同的基站上(比如工作地點(diǎn)附近的基站和居住地點(diǎn)附近的基站)，相比于全部收集到中心之后的全局用戶數(shù)據(jù)，這些分布在各個(gè)基站上的CDR數(shù)據(jù)僅記錄這個(gè)用戶的局部呼叫數(shù)據(jù)。

本文所要解決的問題就是如何在這樣的環(huán)境下，充分利用分布存儲(chǔ)的用戶局部呼叫數(shù)據(jù)，進(jìn)行分布式的相似用戶查詢。本文的目標(biāo)是以較低的通信代價(jià)，高效地找出與被查詢興趣用戶相似的一批用戶。傳統(tǒng)的相似性用戶查詢技術(shù)依賴于集中存儲(chǔ)的用戶數(shù)據(jù)，數(shù)據(jù)收集會(huì)導(dǎo)致高昂的通信代價(jià)。而純粹的在各個(gè)分布的基站上進(jìn)行相似用戶查詢又受限于用戶的局部數(shù)據(jù)，導(dǎo)致查詢結(jié)果不夠準(zhǔn)確。為了解決這一問題，本文提出一種基于局部數(shù)據(jù)的相對(duì)相似用戶分布式查詢方法(RSU-DQ)。整個(gè)查詢過程由3個(gè)階段組成:(1)數(shù)據(jù)中心僅收集被查詢的興趣用戶的全部局部數(shù)據(jù)，建立興趣用戶模型;(2)將興趣用戶模型發(fā)送至相關(guān)基站，各個(gè)基站上獨(dú)立運(yùn)行相似性查詢算法得到候選用戶和對(duì)應(yīng)的相似度;(3)數(shù)據(jù)中心匯聚各基站的候選用戶和對(duì)應(yīng)的相似度，排序并返回查詢結(jié)果。

本文結(jié)合真實(shí)手機(jī)網(wǎng)絡(luò)CDR記錄的產(chǎn)生和存儲(chǔ)特性，定義基于局部呼叫數(shù)據(jù)的相似用戶分布式查詢問題;分析用戶局部呼叫數(shù)據(jù)與全局用戶數(shù)據(jù)的關(guān)系，提出并實(shí)現(xiàn)一種低通信代價(jià)的高效相對(duì)相似用戶分布式查詢方法(RSU-DQ)，以真實(shí)數(shù)據(jù)完成RSUDQ的評(píng)估，驗(yàn)證其低時(shí)間代價(jià)、低通信代價(jià)和高準(zhǔn)確率的特性。

1 相關(guān)研究

在分布式搜索領(lǐng)域有很多研究工作，本文重點(diǎn)關(guān)注分布式模式匹配和分布式時(shí)空相似性搜索兩類工作。分布式模式匹配主要研究如何在分布式存儲(chǔ)系統(tǒng)或分布式數(shù)據(jù)庫(kù)中快速定位查找“類似”對(duì)象，通常以子序列匹配的形式闡述。文獻(xiàn)［5］通過對(duì)時(shí)間序列數(shù)據(jù)的索引完成一個(gè)快速的子序列匹配;文獻(xiàn)［6］用部分關(guān)鍵字匹配技術(shù)結(jié)合特定的P2P網(wǎng)絡(luò)層次結(jié)構(gòu)進(jìn)行高效率的字符串匹配;文獻(xiàn)［7］用多維度二叉樹來提前降低匹配過程計(jì)算代價(jià);文獻(xiàn)［8］提出了一種基于排序的分布式數(shù)據(jù)管理的匹配算法，其基本思路是利用降維的方法，把高維的矩陣降為低維(一維)的序列之后應(yīng)用經(jīng)典的匹配算法。文獻(xiàn)［9］在電信數(shù)據(jù)的環(huán)境下提出不完整數(shù)據(jù)集的概念數(shù)據(jù)作為數(shù)據(jù)源，其匹配算法的核心在于采用帶權(quán)重的布隆過濾器作為容器，將待匹配的模式集合的全組合映射進(jìn)布隆過濾器之后，再將該布隆過濾器傳輸?shù)礁鞴?jié)點(diǎn)上進(jìn)行精確匹配。

分布式時(shí)空相似性的搜索主要處理時(shí)空數(shù)據(jù)(Spatio-temporal Data)。文獻(xiàn)［10］針對(duì)物體的移動(dòng)軌跡(Trajectory)提出了基于最長(zhǎng)公共子序列(LCSS)距離度量的分布式時(shí)空相似搜索;文獻(xiàn)［11］利用GPS日志，計(jì)算出用戶的位置信息并按時(shí)間順序?qū)⒂脩糗壽E定義為興趣地點(diǎn)的序列，在此基礎(chǔ)上計(jì)算其編輯距離;文獻(xiàn)［12］針對(duì)一個(gè)游客信息交流系統(tǒng)設(shè)計(jì)了一套基于時(shí)空近鄰性的推薦系統(tǒng)，游客在對(duì)地點(diǎn)打分和評(píng)價(jià)后通過Ad-hoc網(wǎng)絡(luò)和機(jī)會(huì)信息共享將本地存儲(chǔ)的信息與同地點(diǎn)的游客進(jìn)行交換。

上述研究都或多或少依賴于分布式節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)，即存在中繼節(jié)點(diǎn)或分布節(jié)點(diǎn)之間可以相互通信。而本文所考慮的基站網(wǎng)絡(luò)環(huán)境中，各基站只與數(shù)據(jù)中心進(jìn)行通信;用戶的呼叫數(shù)據(jù)在時(shí)間上并不具有連續(xù)性，各基站的范圍過大，并且各基站僅包含用戶的局部數(shù)據(jù)，現(xiàn)有的軌跡聚類方法并不適用于全局相似用戶的查詢。

2 系統(tǒng)模型

2.1 CDR 數(shù)據(jù)集

當(dāng)用戶使用手機(jī)連入基站網(wǎng)絡(luò)時(shí)，會(huì)在其接入的基站上留下一條呼叫詳細(xì)記錄。包括主叫號(hào)碼、被叫號(hào)碼、呼叫起始時(shí)間、呼叫終止時(shí)間、呼叫時(shí)長(zhǎng)(以秒為單位)、呼叫類型、連接的基站號(hào)等信息。其中基站信息常被用來計(jì)算用戶粗略的地理位置，在隱私保護(hù)和可獲得性方面優(yōu)于GPS信息(很多手機(jī)用戶常常關(guān)閉GPS定位功能而CDR數(shù)據(jù)優(yōu)于運(yùn)營(yíng)商計(jì)費(fèi)需要一定會(huì)產(chǎn)生)。

本文使用的CDR數(shù)據(jù)集由安徽省某城市電信運(yùn)營(yíng)商提供，記錄了38萬用戶一個(gè)月的通話詳細(xì)記錄。用戶主叫和被叫號(hào)碼等隱私相關(guān)信息已被加密。原始的CDR數(shù)據(jù)集具有以下特點(diǎn):

(1)分布式。CDR數(shù)據(jù)產(chǎn)生并存儲(chǔ)的各個(gè)基站上，通常以較長(zhǎng)的周期(一個(gè)月)上傳回?cái)?shù)據(jù)中心或者直接拋棄。因此一個(gè)人在觀察周期內(nèi)的通信記錄常常分布地存儲(chǔ)于多個(gè)不同基站。

(2)不斷進(jìn)化。在手機(jī)網(wǎng)絡(luò)中，每當(dāng)用戶打一次電話就會(huì)產(chǎn)生一條新的CDR記錄，即其數(shù)據(jù)集是不斷在增加和變化的。因此定期匯聚基站數(shù)據(jù)的數(shù)據(jù)中心往往只能處理歷史數(shù)據(jù)。

(3)大規(guī)模。由于用戶數(shù)量巨大，CDR數(shù)據(jù)的量往往很龐大，有些市中心的基站一天之內(nèi)產(chǎn)生的數(shù)據(jù)量就超過了2G，因此搜索過程中必須要考慮數(shù)據(jù)傳輸代價(jià)。

2.2 用戶模型

不同的應(yīng)用和研究目的可能導(dǎo)致對(duì)相似用戶的定義有所不同，然而對(duì)于關(guān)注用戶位置信息的應(yīng)用［3，11，13］和以用戶移動(dòng)性(Mobility)為主要目的研究［1-2，4］來說，用戶在不同時(shí)間段的位置信息是至關(guān)重要的數(shù)據(jù)。本文關(guān)注的是在同樣的時(shí)間段出現(xiàn)在相同基站附近的用戶，因此需要從CDR中提取呼叫時(shí)間和基站號(hào)建立用戶模型。然而，通過對(duì)數(shù)據(jù)的初步觀察(見3.2節(jié))，本文發(fā)現(xiàn)有很多基站在觀察時(shí)間內(nèi)含有非常少量的用戶呼叫數(shù)據(jù)，表明這些地區(qū)可能并不是用戶在日常生活中經(jīng)常出現(xiàn)或者訪問的地區(qū)。為了將這些地區(qū)與用戶經(jīng)常出現(xiàn)的地區(qū)進(jìn)行區(qū)分，在用戶建模過程中還需要從用戶的CDR中引入額外的屬性以建立用戶在不同地區(qū)的活躍度。

通過對(duì)眾多基于CDR的研究的調(diào)查，可以發(fā)現(xiàn)最常用于建立用戶模型的屬性包括觀測(cè)時(shí)間間隔內(nèi)的呼叫次數(shù)(Number of Calls，NoC)、呼叫時(shí)長(zhǎng)(Duration of Calls，DoC)、呼叫人數(shù)(Persons of Called，PoC)等。因此本文使用這3個(gè)基本屬性，結(jié)合呼叫行為發(fā)生的時(shí)間和記錄的基站信息(隱含呼叫行為發(fā)生時(shí)的位置信息)，建立用戶在特定時(shí)間和地區(qū)的活躍度模型。

定義1 在時(shí)間間隔t，基站Cp上用戶Ui包含屬性集合={，，…，}，f 表示屬性的個(gè)數(shù)。則該用戶在此時(shí)此基站的活躍度為:

其中 ωd為屬性的權(quán)重。用戶 Ui在觀察周期 T 內(nèi)在基站Cp上的用戶局部模型由各時(shí)間間隔活躍度組成，=，…，，…，}，可以根據(jù)相似性用戶查詢的應(yīng)用類型對(duì)選用屬性的個(gè)數(shù)f和每個(gè)屬性的權(quán)重ωd進(jìn)行調(diào)節(jié)。本文選用時(shí)間間隔內(nèi)的呼叫次數(shù)和呼叫時(shí)長(zhǎng)的均值作為其活躍度，即f=2。用戶在不同基站上的局部模型組成用戶的全局模型gUMi={，，…，}，mi為存有用戶 Ui的CDR記錄的基站個(gè)數(shù)。按此定義建立的用戶模型實(shí)際上隱式地表達(dá)著用戶在不同地區(qū)的周期性活躍度。

2.3 相似性定義

用戶間相似性一般通過用戶模型間的相關(guān)系數(shù)或距離來表達(dá)。本文定義的相對(duì)相似性是指用戶全局模型的相似度，計(jì)算用戶間的全局相似度依賴于各基站上用戶間的局部模型相似度。用戶Ui和用戶Uj全局相似度為:

其中 Simp(，)表示用戶 Ui和用戶 Uj在基站Cp的局部相似度，φp為該基站在興趣用戶全局模型中的權(quán)重。注意到全局相似度是一種非對(duì)稱性相似度［14］，gSim(Ui，Uj)不一定等于 gSim(Uj，Ui)，即如果用戶Uj是興趣用戶Ui的全局相似用戶，則表明Uj在Ui的所有局部模型所在的基站上都與Ui相似，反之則不一定成立。本文稱這種全局相似度為相對(duì)相似度(Relative Similarity，RS)，gSim(Ui，Uj)稱為用戶Uj相對(duì)于興趣用戶Ui的全局相似度。

若用戶Uj在基站Cp沒有局部模型，則其與興趣用戶在該基站的局部相似度為零;若存在則視和為2個(gè)時(shí)間序列，計(jì)算其歐式距離并使用公式(3)轉(zhuǎn)化為局部相似度。對(duì)于其他的距離測(cè)度或相似性測(cè)度將在將來的工作中予以探討。

3 相對(duì)相似用戶分布式查詢問題

在給出基于局部數(shù)據(jù)的分布式相似用戶查詢問題(Relative Similar User Distributed Query problem，RSU-DQ problem)的正式定義之前，首先考慮一個(gè)應(yīng)用情景:運(yùn)營(yíng)商希望使用某種基于相似用戶(使用2.3節(jié)中的相對(duì)相似用戶定義)的協(xié)同過濾算法為某一個(gè)(一群)興趣用戶做地點(diǎn)推薦。這就需要在分布式的基站網(wǎng)絡(luò)中運(yùn)行相似用戶查詢來找到與目標(biāo)興趣用戶，即在分布式基站網(wǎng)絡(luò)中，哪些手機(jī)用戶是全局模型相對(duì)于目標(biāo)興趣用戶的全局模型最相似的用戶?

由于用戶的每一次呼叫都會(huì)產(chǎn)生一條新的CDR，導(dǎo)致用戶全局模型隨著時(shí)間流逝在不斷進(jìn)化。因此對(duì)于運(yùn)營(yíng)商和諸多應(yīng)用來說，更為近期的用戶模型往往比歷史數(shù)據(jù)建立的模型具有更多的商機(jī)，因此對(duì)于查詢的快速響應(yīng)就顯得頗為重要。

3.1 問題定義

本文考慮的環(huán)境是分布式基站網(wǎng)絡(luò)，共有M+1個(gè)節(jié)點(diǎn):一個(gè)節(jié)點(diǎn)是數(shù)據(jù)中心C0，其他M個(gè)節(jié)點(diǎn)是基站節(jié)點(diǎn)C1，C2，…，CM。所有的基站加起來掌握著一個(gè)n個(gè)用戶的集合USet={U1，U2，…，Un}，每個(gè)Ui都包含一組T內(nèi)的用戶全局模型gUMi={，，…，}，其中 1≤mi≤M。每個(gè)用戶模型都表示該用戶Ui在對(duì)應(yīng)的基站Cp上的一系列活躍度序列。若用戶Ui在基站Cp有記錄(即有局部模型)，稱用戶 Ui存在于基站 Cp。

輸入一個(gè)興趣用戶Ui和參數(shù)K，基于局部數(shù)據(jù)的分布式相似用戶查詢(Top-K Query)要能夠找出一組用戶集合包含所有的用戶中相對(duì)于興趣用戶的全局模型最相似的K個(gè)用戶。該查詢由數(shù)據(jù)中心C0發(fā)出，最后的響應(yīng)也由C0作出。用戶Uj相對(duì)于用戶Ui全局相似當(dāng)且僅當(dāng)他們?cè)诿恳粋€(gè)Ui存在的基站上都相似。相似度的具體計(jì)算方法如2.3節(jié)所述，將局部模型視為定長(zhǎng)的浮點(diǎn)數(shù)組成的向量，用于計(jì)算局部模型之間的歐氏距離。

3.2 分析和觀察

直覺上，有兩種思路可以用來完成在分布式基站網(wǎng)絡(luò)上的相似性用戶查詢，集中式的查詢和分布式查詢。

(1)集中式查詢:將所有基站上的全部CDR數(shù)據(jù)傳輸至數(shù)據(jù)中心，在集中存儲(chǔ)的數(shù)據(jù)集上運(yùn)行集中式查詢算法，計(jì)算所有用戶模型與興趣用戶模型的相對(duì)相似度，排序后取得最相似的K個(gè)用戶作為結(jié)果返回。這種方式顯然不夠高效，由于基站數(shù)量很大并且海量用戶的CDR數(shù)據(jù)總量規(guī)模龐大，傳輸全部基站數(shù)據(jù)到數(shù)據(jù)中心帶來巨大的通信代價(jià)，導(dǎo)致集中式的查詢可行性不高。

(2)分布式查詢:每一個(gè)基站在自己本身含有的局部數(shù)據(jù)上獨(dú)立地執(zhí)行相似性查詢算法，數(shù)據(jù)中心收集各基站的查詢結(jié)果，找出相對(duì)于興趣用戶全局模型最相似的K個(gè)用戶作為結(jié)果返回。這種方式的好處在不需要提前將基站上存儲(chǔ)的CDR數(shù)據(jù)傳輸?shù)綌?shù)據(jù)中心，極大地降低了數(shù)據(jù)通信代價(jià)，并且契合于本文所關(guān)注的相對(duì)相似性定義，即與興趣用戶相對(duì)相似的用戶需要在興趣用戶所在的各個(gè)基站上具有相似性。然而，由于每個(gè)基站只擁有用戶的局部數(shù)據(jù)，因此收集的各基站獨(dú)立查詢得到的結(jié)果可能導(dǎo)致準(zhǔn)確度不高，“相似”的用戶可能會(huì)被漏報(bào)。

無論是哪種方式，數(shù)據(jù)中心都依賴于來自分布式基站的通信消息來獲取查詢結(jié)果。從以上的分析中可以看出，將全部用戶的CDR數(shù)據(jù)包含進(jìn)通信消息的集中式查詢效率很低，而在通信消息中僅包含局部查詢結(jié)果的分布式查詢則有可能準(zhǔn)確度不高。因此本文提出優(yōu)化的分布式查詢方法，本質(zhì)上需要在降低通信代價(jià)的同時(shí)保證傳輸?shù)男畔⒅邪銐驑?gòu)建用戶全局相似性的信息，即通信消息要“少而精”。

圖1 隨機(jī)8個(gè)用戶的各基站活躍度柱狀圖

對(duì)CDR數(shù)據(jù)集進(jìn)行分析后觀察到用戶在少數(shù)基站上的活躍度主導(dǎo)了其總活躍度這個(gè)現(xiàn)象。圖1展示了從所有用戶中隨機(jī)選取的8個(gè)用戶在其各自所在的基站上的活躍度(觀察周期為一周)。X軸為用戶在觀察周期內(nèi)存在過的基站號(hào)，Y軸為用戶在各基站上的總活躍度。從圖1中可以發(fā)現(xiàn)用戶在各個(gè)基站上的活躍度并不平均，在少數(shù)基站上的活躍度占據(jù)了其總活躍度的很大比重。為了進(jìn)一步研究這一現(xiàn)象是否普遍存在于所有的用戶數(shù)據(jù)中，本文對(duì)真實(shí)數(shù)據(jù)統(tǒng)計(jì)了每個(gè)用戶最活躍的前3個(gè)基站和最活躍的前25%的基站上的活躍度在該用戶總活躍度中所占的比例，并依此繪制了其互補(bǔ)累計(jì)積分分布圖(Complementary Cumulative Distribution Function，CCDF)(圖2)，X軸為用戶在最活躍的幾個(gè)基站上的活躍度之和占該用戶總活躍度的比重，Y軸為互補(bǔ)累計(jì)分布函數(shù)中的百分比。從圖2中可以觀察到，將近60%的用戶在其最活躍的前3個(gè)基站上的活躍度超過了其總活躍度的80%;將近78%的用戶在其最活躍的前25%個(gè)基站上的活躍度超過其總活躍度的80%。這一現(xiàn)象在現(xiàn)實(shí)生活中并不難理解，用戶在某些地區(qū)(工作地點(diǎn)、家庭住址等)停留的時(shí)間越長(zhǎng)，在其附近基站上留下的記錄就越多，導(dǎo)致在這些基站上的活躍度明顯高于其他基站。

圖2 用戶最活躍的前3個(gè)基站和前25%個(gè)基站上的活躍度占總活躍度比例的互補(bǔ)累計(jì)積分分布(CCDF)圖

本文所提出的分布式查詢方法充分利用這一特性，對(duì)興趣用戶的全局模型進(jìn)行主要基站分析(Prime Cell Analysis，PCA):選擇那些在用戶總活躍度中占主要成分(活躍度之和占用戶總活躍度的比重大于閾值θ)的基站運(yùn)行局部的相對(duì)相似度計(jì)算，從而降低通信代價(jià)。同時(shí)為了體現(xiàn)各基站在用戶Ui全局模型中的不同重要程度，本文引入基站權(quán)重φp，定義如下:

4 相對(duì)相似用戶分布式查詢方法

相對(duì)相似用戶分布式查詢方法(Relative Similar User Distributed Query，RSU-DQ)主要由4個(gè)階段組成(見圖3)。數(shù)據(jù)中心接收到要查詢的興趣用戶的用戶ID后:(1)向各基站收集該用戶的CDR數(shù)據(jù)并建立用戶全局模型;(2)對(duì)該用戶全局模型運(yùn)行PCA算法并計(jì)算每個(gè)基站的權(quán)重;(3)由選擇出來的基站執(zhí)行本地查詢算法計(jì)算局部相似度;(4)各基站獨(dú)自計(jì)算出來的結(jié)果傳輸回?cái)?shù)據(jù)中心(傳遞消息以＜用戶ID，局部相似度＞的形式)，由數(shù)據(jù)中心匯聚后確定最相似的K個(gè)用戶。階段2和階段4均發(fā)生在數(shù)據(jù)中心，階段1和階段3則需要分布式基站的參與。

圖3 相對(duì)相似性用戶分布式查詢方法概覽

階段1 興趣用戶建模。

對(duì)興趣用戶的建模發(fā)生在數(shù)據(jù)中心。數(shù)據(jù)中心接收到待查詢的興趣用戶ID后，將ID號(hào)和建模參數(shù)(觀察時(shí)間T、時(shí)間間隔Δt、建模屬性集合A和各屬性權(quán)重等)發(fā)送給所有基站，由存在興趣用戶CDR記錄的基站進(jìn)行響應(yīng)，按照公式(1)獨(dú)立完成相應(yīng)局部模型的建立后傳輸回?cái)?shù)據(jù)中心。

階段2 主要基站分析。

數(shù)據(jù)中心收集了興趣用戶的全部局部模型之后建立用戶的全局模型，并對(duì)其進(jìn)行主要基站分析:按公式⑷計(jì)算各基站的權(quán)重，并以用戶在各基站上的活躍度排序;選擇最活躍的m個(gè)基站使得用戶在這m個(gè)基站上的活躍度之和超過該用戶總活躍度的閾值θ。視這m個(gè)基站為主要基站(Prime Cells，PC)，由PC執(zhí)行接下里的局部相似度計(jì)算。舉例說明，假設(shè)興趣用戶Ui存在于3個(gè)基站{C1，C2，C3}，在每個(gè)基站上的活躍度占總活躍度比重分別為{12%，70%，18%}。若θ=80%則PCA選擇{C2，C3}作為主要基站;若 θ=90%，則 PCA 選擇{C2，C3，C1}全部3個(gè)基站作為主要基站。

階段3 計(jì)算局部相似度。

局部相似度的計(jì)算是分布式的，由各PC獨(dú)立完成:首先遍歷基站上所有的用戶局部模型，按照公式(3)計(jì)算其與興趣用戶在該基站上的局部模型的局部相似度;計(jì)算完成后得到一張表，包含該基站上所有用戶的用戶ID及對(duì)應(yīng)的相對(duì)于興趣用戶的局部相似度，將整張表傳輸回?cái)?shù)據(jù)中心。

從計(jì)算過程可以看出，局部相似度計(jì)算過程的時(shí)間代價(jià)和傳輸代價(jià)取決于該基站上所存儲(chǔ)的用戶數(shù)量，存在于該基站的用戶越多，時(shí)間代價(jià)和傳輸代價(jià)越大。

階段4 匯聚基站返回結(jié)果。

在接收到主要基站的計(jì)算結(jié)果之后，數(shù)據(jù)中心對(duì)所有結(jié)果進(jìn)行匯聚:對(duì)于所有局部計(jì)算結(jié)果中的每一個(gè)用戶ID，按公式(2)計(jì)算其相對(duì)于興趣用戶的全局相似度;按全局相似度降序排列所有用戶;取前K個(gè)用戶(即相對(duì)與興趣用戶最相似的K個(gè)用戶)作為查詢結(jié)果作出響應(yīng)。

5 實(shí)驗(yàn)評(píng)估

本節(jié)用真實(shí)的CDR數(shù)據(jù)集對(duì)提出的相對(duì)相似用戶分布式查詢方法進(jìn)行評(píng)估。首先對(duì)實(shí)驗(yàn)進(jìn)行描述，包括數(shù)據(jù)集、實(shí)驗(yàn)環(huán)境和比較方法;其次在準(zhǔn)確度、時(shí)間代價(jià)和通信代價(jià)方面對(duì)本文所提出的分布式查詢方法進(jìn)行評(píng)估。

5.1 實(shí)驗(yàn)描述

(1)數(shù)據(jù)描述:實(shí)驗(yàn)的數(shù)據(jù)集大小為5.67 GB。從CDR數(shù)據(jù)(詳細(xì)描述見2.1節(jié))中可以提取出呼叫發(fā)起時(shí)間、基站ID和必要的用戶屬性用以完成用戶模型的建立(見2.2節(jié))。評(píng)估實(shí)驗(yàn)中使用的數(shù)據(jù)集是安徽省某城市電信運(yùn)營(yíng)商提供的2012年2月的全部CDR數(shù)據(jù)集，覆蓋了38萬用戶和6萬個(gè)基站。

(2)實(shí)驗(yàn)環(huán)境描述:一臺(tái)配備三代酷睿i5處理器(主頻2.5 GHz)和8 GB主存的筆記本電腦。實(shí)驗(yàn)使用一個(gè)獨(dú)立的線程作為一個(gè)主要基站進(jìn)行獨(dú)立的局部相似度計(jì)算。

(3)比較方法:以集中式查詢(見3.2節(jié))作為基線方法，在準(zhǔn)確度、時(shí)間代價(jià)和通信代價(jià)方面與本文提出的分布式查詢做比較。為了進(jìn)一步觀察PCA階段閾值θ對(duì)結(jié)果的影響，實(shí)驗(yàn)還對(duì)比了θ=80%和θ=90%的時(shí)候RUS-DQ方法的準(zhǔn)確度和效率。

5.2 準(zhǔn)確度和效率評(píng)估

本文從3個(gè)方面對(duì)準(zhǔn)確度和效率進(jìn)行評(píng)估:精度(Precision)、時(shí)間代價(jià)(Time Cost)和通信代價(jià)(Communication Cost)。對(duì)于準(zhǔn)確度的衡量本文使用精度的概念，即正判率/(正判率+誤判率);時(shí)間代價(jià)則為被評(píng)估的查詢方法運(yùn)行一次查詢所用的時(shí)間;通信代價(jià)為各基站和數(shù)據(jù)中心之間所傳輸?shù)耐ㄐ畔⒌臄?shù)量。

圖4 準(zhǔn)確度和效率評(píng)估

在圖4中，X軸為興趣用戶Ui局部模型的個(gè)數(shù)mi。對(duì)于每一個(gè)mi(從1到60)，隨機(jī)選擇20個(gè)局部模型個(gè)數(shù)為mi用戶作為興趣用戶進(jìn)行查詢，取均值作為平均的準(zhǔn)確度、時(shí)間代價(jià)和通信代價(jià)。從圖4(a)中可以看出，集中式查詢具有最高的準(zhǔn)確度，因?yàn)榧惺讲樵儗⑺谢旧系娜繑?shù)據(jù)都傳輸回?cái)?shù)據(jù)中心后再進(jìn)行查詢算法，擁有全局用戶模型。本文提出的分布式查詢方法在主要基站閾值θ=80%的時(shí)候精度保持在90%左右(均值為91.6%)，當(dāng)θ=90%時(shí)RSU-DQ方法能夠保持96%左右的準(zhǔn)確度。準(zhǔn)確度的提升并不難以理解，較高的閾值意味著有更多的基站被視為主要基站執(zhí)行局部相似度的計(jì)算，尤其在興趣用戶的局部模型比較少的時(shí)候(少于20個(gè))，調(diào)高主基站閾值對(duì)于準(zhǔn)確度的提升效果更加顯著，然而隨著更多的基站參與計(jì)算，RSU-DQ方法的總時(shí)間代價(jià)和通信代價(jià)也隨之增加。圖4(b)的Y軸為平均查詢時(shí)間，可以觀察到RSU-DQ方法明顯優(yōu)于集中式查詢，隨著興趣用戶局部模型的增加，查詢時(shí)間的增長(zhǎng)也相對(duì)平緩，當(dāng)主基站閾值較高時(shí)，查詢時(shí)間稍有增長(zhǎng)但依然遠(yuǎn)遠(yuǎn)低于集中式查詢。圖4(c)的Y軸為通信代價(jià)(以占集中式的查詢的通信代價(jià)的比例的形式)，可以看出RSU-DQ方法比集中式查詢的通信代價(jià)要小得多，原因在于RSU-DQ只要求與少數(shù)的主要基站進(jìn)行大量數(shù)據(jù)的傳輸，而集中式查詢需要提前將所有基站上的CDR數(shù)據(jù)搜集起來之后再進(jìn)行查詢?？梢钥闯?，當(dāng)興趣用戶的局部模型比較少的時(shí)候，較高的主基站閾值θ引起的時(shí)間代價(jià)和通信代價(jià)的增加并不明顯。

通過上述實(shí)驗(yàn)評(píng)估和分析可以看出，RSU-DQ方法能夠達(dá)到高準(zhǔn)確率、低時(shí)間代價(jià)和低通信代價(jià)的目標(biāo);隨著興趣用戶局部模型的增加，穩(wěn)定的準(zhǔn)確度和平緩增加的時(shí)間通信代價(jià)也保證了RSU-DQ的擴(kuò)展性;設(shè)置一個(gè)較高的主基站閾值θ可以進(jìn)一步提高RSU-DQ的準(zhǔn)確率。

6 結(jié)束語

本文結(jié)合對(duì)真實(shí)手機(jī)網(wǎng)絡(luò)中的呼叫詳細(xì)記錄的分析，提出了基于局部呼叫數(shù)據(jù)的相似用戶分布式查詢問題。為了解決這一問題，本文分析了用戶局部呼叫數(shù)據(jù)與全局用戶數(shù)據(jù)的關(guān)系，根據(jù)分析結(jié)果，提出并實(shí)現(xiàn)了一種基于用戶局部數(shù)據(jù)的相對(duì)相似用戶分布式查詢方法RSU-DQ。通過用真實(shí)數(shù)據(jù)做的一系列實(shí)驗(yàn)，本文展示了RSU-DQ的高準(zhǔn)確度、低時(shí)間代價(jià)和低通信代價(jià)的特點(diǎn)。

在今后的工作中，將繼續(xù)研究更多的應(yīng)用場(chǎng)景，比如考慮批量查詢、其他的相似度定義以及相似度定義和各基站權(quán)重之間的關(guān)系等。

［1］Candia J，Gonzalez M C，Wang P，et al.Uncovering individual and collective human dynamics from mobile phone records［J］.Journal of Physics A:Mathematical and Theoretical，2008，41(22):Article 224015.

［2］Gonzalez M C，Hidalgo C A，Barabasi A L.Understanding individual human mobility patterns［J］.Nature，2008，453(7196):779-782.

［3］Phithakkitnukoon S，Horanont T，Di Lorenzo G，et al.Activity-aware map:Identifying human daily activity pattern using mobile phone data［C］//Proceedings of the 2010 International Workshop on Human Behavior Understanding.Istanbul，Turkey，2010:14-25.

［4］Ficek M，Kencl L.Inter-call mobility model:A spatiotemporal refinement of call data records using a Gaussian mixture model［C］//Proceedings of the 31st Annual IEEE International Conference on Computer Communications.Orlando，USA，2012:469-477.

［5］Faloutsos C，Ranganathan M，Manolopoulos Y.Fast subsequence matching in time-series databases［C］//Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data.Minneapolis，USA，1994:419-429.

［6］Ahmed R，Boutaba R.Distributed pattern matching:A key to flexible and efficient P2P search［J］.IEEE Journal on Selected Areas in Communications，2007，25(1):73-83.

［7］Van Hook D J，Rak S J，Calvin J O.Approaches to RTI implementation of HLA data distribution management services［C］//Proceedings of the 15th Workshop on Standards for the Interoperability of Distributed Simulations.Orlando，USA，1996:535-544.

［8］Raczy C，Tan G，Yu J.A sort-based DDM matching algorithm for HLA［J］.ACM Transactions on Modeling and Computer Simulation(TOMACS)，2005，15(1):14-38.

［9］Liu S，Kang L，Chen L，et al.Distributed incomplete pattern matching via a novel weighted Bloom filter［C］//Proceedings of the 2012 IEEE 32nd International Conference on Distributed Computing Systems.Macau，China，2012:122-131.

［10］Zeinalipour-Yazti D，Lin S，Gunopulos D.Distributed spatio-temporal similarity search［C］//Proceedings of the 15th ACM International Conference on Information and Knowledge Management.Arlington，USA，2006:14-23.

［11］Li Q，Zheng Y，Xie X，et al.Mining user similarity based on location history［C］//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Irvine，USA，2008:Article No.34.

［12］De Spindler A，Norrie M C，Grossniklaus M，et al.Spatiotemporal proximity as a basis for collaborative filtering in mobile environments［C］//Proceedings of the Workshop on Ubiquitous Mobile Information and Collaboration Systems(UMICS 2006).2006.

［13］Isaacman S，Becker R，Caceres R，et al.Identifying important places in people’s lives from cellular network data［C］//Proceedings of the 9th International Conference on Pervasive Computing.San Francisco，USA，2011:133-151.

［14］Heck T.A comparison of different user-similarity measures as basis for research and scientific cooperation［C］//Proceedings of the 2011 International Conference on Information Science and Social Media.2011.