日常交互中朋友關(guān)系強(qiáng)度度量方法

1、日常交互中朋友關(guān)系強(qiáng)度度量方法*收稿日期：2015-XX-XX基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61202117，91118008）作者簡介：史殿習(xí)（1966），男，山東龍口人，教授，博士，E-mail：dxshi史殿習(xí)1，楊若松1，莫曉赟1，李寒1，趙邦輝1（1.國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長沙 410073）摘要：關(guān)系強(qiáng)度體現(xiàn)了人們之間的親密程度，對研究人們之間的社會關(guān)系具有重要的意義。本文針對如何度量日常生活中人們之間的關(guān)系強(qiáng)度問題展開研究，提出了一個從日常軌跡、語義位置以及語義標(biāo)簽三個層次度量朋友之間關(guān)系強(qiáng)度的層級模型FRSHV，采用DTW模型通過計(jì)算朋友之間的空間距離來度量

2、其日常軌跡之間的相似度，進(jìn)而使用軌跡序列熵值對用戶每天軌跡的相似度進(jìn)行加權(quán)處理，將其作為朋友之間的關(guān)系強(qiáng)度；采用主題模型LDA分別計(jì)算朋友之間的基于語義位置和語義標(biāo)簽的行為模式的相似性，將其作為朋友之間的關(guān)系強(qiáng)度；采用集成學(xué)習(xí)的思想對三個層次的度量結(jié)果進(jìn)行投票，以投票結(jié)果作為最終的朋友之間的關(guān)系強(qiáng)度；在公開數(shù)據(jù)集上對FRSHV模型的有效性進(jìn)行了實(shí)驗(yàn)驗(yàn)證，結(jié)果表明該模型能夠有效地度量朋友之間的關(guān)系強(qiáng)度。關(guān)鍵詞：關(guān)系強(qiáng)度；軌跡相似度；DTW；熵；LDA；投票中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A文章編號： Measuring Friend Relationship Strength Method

3、In Daily CommunicationDianxi Shi,Ruosong Yang,Xiaoyun Mo,Han Li,Banghui Zhao (College of Computer，National University of Defense Technology, Changsha 410073, China) Abstract: Relationship strength reflects the degree of intimacy between two different persons, which is of great importance in analyzin

4、g humans social relationship as well as social network. In this paper, we proposed Friend Relationship Strength Hierarchy Vote(FRSHV), a hierarchical model measures friend relationship strength by users daily moving track, semantic positions and the corresponding semantic labels. Firstly, we measure

5、d daily track similarity by DTW model using calculating the spatial distance between friends. The results were then weighted by the entropy of track series. Secondly, we inferred the similarity of friends behavior patterns by LDA topic model, respectively using semantic positions and the correspondi

6、ng semantic labels. Finally, we voted on these three similarity results for the ultimate relationship strength. We evaluated FRSHV using an open dataset and the results showed the validity of the model in inferring friends relationship strength.Keywords: relationship strength, trajectory similarity,

7、 DTW, entropy, LDA, vote9目前，內(nèi)嵌了各種各樣傳感器的智能手機(jī)已經(jīng)成為人們?nèi)粘Ｉ钪屑ㄐ拧⒂?jì)算及感知于一體的移動平臺。通過內(nèi)嵌的各種傳感器如GPS、加速度、麥克風(fēng)等可以隨時隨地感知和獲取人們自身及其周圍環(huán)境的各種信息，通過智能手機(jī)所收集各種數(shù)據(jù)研究人們之間的日常交互行為和人們之間的社會關(guān)系成為普適計(jì)算領(lǐng)域當(dāng)中一個重點(diǎn)研究的問題。RealityMining1基于手機(jī)所收集的各種數(shù)據(jù)推理人們之間的社會交互關(guān)系以及群組的活動韻律，從而洞察個人和組織的行為模式； fMRi2研究分析了家庭和朋友圈對個體行為在社交網(wǎng)絡(luò)中所受的影響；StudentLife3研究了在校學(xué)生的日?；顒?/p>

8、、交互情況、精神健康與學(xué)業(yè)成績之間的關(guān)系；文獻(xiàn)4則從多渠道、細(xì)粒度地收集各種反映在校學(xué)生日?；顒雍徒换デ闆r的各種數(shù)據(jù)，從多個層面真實(shí)、全面地反映學(xué)生日?；顒右约八麄冎g的交互行為和交互關(guān)系。但是，這些研究重點(diǎn)關(guān)注的是人們之間的日常交互行為和交互關(guān)系，而關(guān)系強(qiáng)度度量的是人們之間的親密程度，通過關(guān)系強(qiáng)度，我們可以更好地了解人們之間的關(guān)系的強(qiáng)弱，進(jìn)而了解人們之間的親密程度，從而可以更好地預(yù)測社會關(guān)系的演變以及社交結(jié)構(gòu)的變化，促進(jìn)信息傳播以及傳染疾病的預(yù)防與控制等。社會關(guān)系強(qiáng)度理論始于文獻(xiàn)5中對于弱關(guān)系的研究，將弱關(guān)系和強(qiáng)關(guān)系的測量分為四個維度，即交往人員之間的互動頻率、感情的投入程度、關(guān)系親密程度和

9、在互惠互利上的交換程度；文獻(xiàn) 6對這四個維度做了相關(guān)指標(biāo)化；文獻(xiàn)7認(rèn)為關(guān)系強(qiáng)度涉及關(guān)系的數(shù)量以及交往的頻率。隨著關(guān)系強(qiáng)度研究領(lǐng)域的不斷發(fā)展，逐漸形成了以互動頻率、聯(lián)系次數(shù)、親密程度為關(guān)系強(qiáng)度核心測量指標(biāo)的主流研究觀點(diǎn)8。但是，如何度量社會網(wǎng)絡(luò)中人們之間的關(guān)系強(qiáng)度一直是社交網(wǎng)絡(luò)關(guān)系分析中的一個難點(diǎn)問題。通過智能手機(jī)可以隨時隨地的獲取位置、通話記錄、短信、微信等體現(xiàn)人們之間日常交互和社會關(guān)系的各種信息，人們之間的交互頻率、時間、位置、地點(diǎn)、距離以及軌跡相似性等信息能夠直接體現(xiàn)人們之間的交互關(guān)系以及關(guān)系強(qiáng)度，因?yàn)殛P(guān)系密切的人們之間更愿意面對面地進(jìn)行交流，而且朋友之間會經(jīng)常進(jìn)行面對面的交流如聚會、一起

10、游覽等等，通過對這些信息的分析處理，可以更好地度量朋友之間的關(guān)系強(qiáng)度。為了方便描述，我們將本文分析處理的對象稱為用戶，我們認(rèn)為用戶和陌生人之間的關(guān)系強(qiáng)度因?yàn)榛ゲ徽J(rèn)識應(yīng)該為零，但是對一個用戶來說，雖然與一些陌生人不認(rèn)識，也可能會經(jīng)常在一些地方同時出現(xiàn)，因此我們只考慮用戶和其好友之間的關(guān)系強(qiáng)度。本文設(shè)想能夠在一定程度上反映兩個朋友之間的關(guān)系，而非完整全面的度量兩個用戶之間的關(guān)系。我們認(rèn)為使用手機(jī)上所有傳感器的全部數(shù)據(jù)能夠精確的分析朋友之間的關(guān)系強(qiáng)度，軌跡數(shù)據(jù)是手機(jī)傳感器數(shù)據(jù)非常重要的組成部分，本文主要研究如何只使用軌跡數(shù)據(jù)度量朋友之間的親密程度。文獻(xiàn)9認(rèn)為用戶之間的關(guān)系強(qiáng)度與用戶共同出現(xiàn)的時間和共

11、同出現(xiàn)的位置相關(guān)，提出了一個基于GPS軌跡數(shù)據(jù)的層級模型，根據(jù)用戶的GPS軌跡來度量用戶之間的關(guān)系強(qiáng)度，并在仿真數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證。本文在文獻(xiàn)9的基礎(chǔ)上，針對如何度量日常生活中人們之間的關(guān)系強(qiáng)度問題展開研究，提出了一個可以對GPS數(shù)據(jù)和基站數(shù)據(jù)進(jìn)行處理，從日常軌跡、語義位置以及語義標(biāo)簽三個層次度量用戶與朋友之間關(guān)系強(qiáng)度的層級模型FRSHV(Friend Relationship Strength Hierarchy Vote) 。該模型采用DTW模型通過計(jì)算用戶與朋友之間的空間距離來度量其軌跡之間的相似度，進(jìn)而使用軌跡序列熵值對用戶每天軌跡的相似度進(jìn)行加權(quán)處理，并將其作為用戶與其朋友之間的

12、關(guān)系強(qiáng)度；采用主題模型LDA分別計(jì)算用戶與朋友之間的基于語義位置和語義標(biāo)簽的行為模式的相似性，將其作為用戶與朋友之間的關(guān)系強(qiáng)度；最后，采用集成學(xué)習(xí)的思想對三個層次的度量結(jié)果進(jìn)行投票，以投票結(jié)果作為最終的用戶與朋友之間的關(guān)系強(qiáng)度，并在公開數(shù)據(jù)集上對FRSHV模型的有效性進(jìn)行了實(shí)驗(yàn)驗(yàn)證，結(jié)果表明該模型能夠有效地度量朋友之間的關(guān)系強(qiáng)度。本文如下組織：節(jié)1描述了人們之間關(guān)系強(qiáng)度的度量方法；節(jié)2詳細(xì)描述了層級朋友之間關(guān)系強(qiáng)度模型FRSHV；節(jié)3對實(shí)驗(yàn)數(shù)據(jù)集以及評估方法進(jìn)行了描述；節(jié)4對FRSHV模型的有效性進(jìn)行了實(shí)驗(yàn)驗(yàn)證；最后，對全文工作以及下一步的工作進(jìn)行了概括總結(jié)。1 關(guān)系強(qiáng)度度量方法通過對社會心理

13、學(xué)相關(guān)研究成果的分析，我們認(rèn)為人們之間的關(guān)系強(qiáng)度與他們之間的軌跡相似性以及日常行為的相似性密切相關(guān)，因此，為了有效地度量人們之間的關(guān)系強(qiáng)度，我們從人們之間的日常軌跡和日常行為這兩個角度出發(fā)，提出采用不同計(jì)算方法來計(jì)算人們之間的關(guān)系強(qiáng)度。1.1基于DTW模型的計(jì)算方法空間距離能夠直觀反映人們之間在物理世界中的距離，空間距離非常接近的用戶在現(xiàn)實(shí)生活中會有更多的面對面的交互，從而增強(qiáng)兩個人之間的關(guān)系強(qiáng)度。根據(jù)社會心理學(xué)的研究成果，文獻(xiàn)10在一個大型住宅區(qū)研究了接近性效應(yīng)（接近性效應(yīng)指兩個人住的越近越可能是朋友），結(jié)果表明人們居住得越近，不管這種近是物理距離還是功能性距離，人們越容易稱為朋友。文獻(xiàn)11

14、用實(shí)驗(yàn)證實(shí)了單純接觸效應(yīng)，即熟悉性能夠促進(jìn)好感，實(shí)驗(yàn)結(jié)果表明接觸頻率越高喜歡程度越強(qiáng)。DTW(Dynamic Time Warping)是Itakura于1987年12提出的一種距離度量方法，我們可以將用戶的軌跡數(shù)據(jù)看作一個時間序列，因此同樣可以使用DTW方法度量軌跡的相似度，并且將軌跡相似度作為人們之間的關(guān)系強(qiáng)度。通過深入分析DTW算法可知，序列的長度越長，則距離可能越大。因此，我們采用文獻(xiàn)13中的三種歸一化方法對DTW的計(jì)算結(jié)果進(jìn)行進(jìn)一步的處理和優(yōu)化，即DTW結(jié)果除以最優(yōu)變形路徑的長度、DTW結(jié)果除以兩個序列中較短序列的長度以及DTW結(jié)果除以兩個序列中較長序列的長度等三種方法對DTW計(jì)算結(jié)

15、果進(jìn)行歸一化，以便獲得最優(yōu)結(jié)果。1.2基于序列熵值加權(quán)的計(jì)算方法通過日常生活體驗(yàn)很容易發(fā)現(xiàn)，如果兩個人在晚上等休息時間經(jīng)常一起出去，則其關(guān)系可能更親密，因而他們之間的軌跡越可能相似。因此，可以使用熵值來度量用戶每天活動的多樣性，若某天活動越多樣，則該天軌跡的相似度對總體軌跡的相似度貢獻(xiàn)越大，進(jìn)而對人們之間的關(guān)系強(qiáng)度貢獻(xiàn)越大。計(jì)算軌跡序列的熵值的目的是為了對DTW計(jì)算結(jié)果進(jìn)行加權(quán)，因?yàn)橛脩裘刻斓能壽E序列的相似度對其總體相似度的貢獻(xiàn)是不一樣的，如果某一天用戶的軌跡序列的熵值越大，則這一天對總的相似度貢獻(xiàn)越大。因此，使用用戶每天軌跡序列熵值對用戶與朋友之間每天的軌跡相似度進(jìn)行加權(quán)，能夠更真實(shí)地反應(yīng)用

16、戶與朋友之間的關(guān)系強(qiáng)度（計(jì)算過程見節(jié)2.2）。1.3基于主題模型LDA的計(jì)算方法在日常生活當(dāng)中，人們之間尤其是好友之間其行為模式之間具有一定的相似性，如經(jīng)常在某些時間段（晚上）去一些地方（餐館）等等?；谖恢玫挠脩粜袨槟Ｊ揭环矫婺軌蚍从秤脩粼谖锢韺哟蔚南嘤?，另一方面能夠在一定程度上體現(xiàn)用戶的相似性，前文已經(jīng)從社會心理學(xué)的角度闡述了相遇次數(shù)與用戶關(guān)系強(qiáng)度的關(guān)系，文獻(xiàn)14認(rèn)為人們傾向于喜歡在態(tài)度、興趣、價值觀、背景和人格上和其相似的人，因此，在日常生活當(dāng)中行為相似的人之間更可能成為朋友，而根據(jù)社會心理學(xué)的研究成果，用戶的相似性對用戶的關(guān)系強(qiáng)度也有一定的影響，為此，我們在通過基于用戶軌跡度量用戶之間

17、關(guān)系強(qiáng)度的基礎(chǔ)上，進(jìn)一步通過基于位置的用戶日常行為來對度量用戶之間的關(guān)系強(qiáng)度。LDA(Latent Dirichlet Allocation)15是一個針對離散數(shù)據(jù)集合的產(chǎn)生式概率模型。文獻(xiàn)16最先使用LDA主題模型發(fā)現(xiàn)用戶的行為模式，在使用LDA模型發(fā)現(xiàn)用戶基于位置的行為模式基礎(chǔ)上，我們進(jìn)一步使用LDA主題模型來度量用戶之間的關(guān)系強(qiáng)度，其核心思想如下：將每個用戶每天去過的位置（語義位置或語義標(biāo)簽）序列視為一個句子，每個用戶所有天的位置序列視為一篇文檔，對所有用戶所有天的位置序列使用LDA主題模型訓(xùn)練得到若干個主題。在計(jì)算兩個用戶之間的關(guān)系強(qiáng)度時，將這兩個用戶同一天的數(shù)據(jù)按固定長度的時間片劃分

18、，對于每個時間片內(nèi)用戶去過的位置，用訓(xùn)練好的LDA主題模型推斷這些位置對應(yīng)的主題分布，以同一時間片內(nèi)，兩個用戶分別參去過的位置對應(yīng)的主題分布的余弦相似度，作為這兩個用戶之間的關(guān)系強(qiáng)度（計(jì)算過程見節(jié)2.2）。2 關(guān)系強(qiáng)度度量模型框架要真實(shí)全面地反映人們之間的關(guān)系強(qiáng)度，需要從不同角度和不同層次對人們之間的關(guān)系強(qiáng)度進(jìn)行度量，為此，我們提出了一個層次化的、對用戶與朋友之間的關(guān)系強(qiáng)度進(jìn)行度量、并對度量結(jié)果進(jìn)行投票的模型FRSHV(Friend Relationship Strength Hierarchy Vote)，其框架結(jié)構(gòu)如圖1所示。FRSHV模型是一個三層的、能夠?qū)νㄟ^GPS 和基站位置數(shù)據(jù)進(jìn)行

19、處理的度量模型，從軌跡、語義位置以及語義標(biāo)簽三個層次對用戶與朋友之間的關(guān)系強(qiáng)度進(jìn)行度量，并使用集成學(xué)習(xí)的思想對三個層次度量結(jié)果進(jìn)行投票，最終以投票結(jié)果作為用戶與朋友之間的關(guān)系強(qiáng)度。圖1 FRSHV模型框架Figure 1 FRSHV Model Framework在FRSHV模型當(dāng)中，第一層度量主要針對用戶的軌跡序列數(shù)據(jù)，根據(jù)不同用戶軌跡序列的相似度來度量用戶與朋友之間的關(guān)系強(qiáng)度；第二層度量主要針對用戶的語義位置序列數(shù)據(jù)，考慮用戶個人的基于位置的行為模式如經(jīng)常在什么時間出現(xiàn)在哪些位置等，根據(jù)不同用戶行為模式的相似度來度量用戶與朋友之間的關(guān)系強(qiáng)度；第三層度量主要針對用戶的語義標(biāo)簽序列數(shù)據(jù)，物理上

20、不同的位置可能擁有相同的語義標(biāo)簽，“辦公室”、“家”等語義概念在每個用戶軌跡中都可能出現(xiàn)，而這些語義概念在原始數(shù)據(jù)中會表現(xiàn)為不同的基站號和區(qū)域號或不同的GPS經(jīng)緯度，因此用戶的語義標(biāo)簽數(shù)據(jù)更能體現(xiàn)用戶群體的日常習(xí)慣，因此本層考慮的行為模式更傾向于群體的行為模式，從而根據(jù)不同用戶在群體中表現(xiàn)出的行為模式來度量用戶與朋友之間的關(guān)系強(qiáng)度。2.1 GPS及基站位置數(shù)據(jù)處理在日常生活中，用戶的位置既可以通過智能手機(jī)內(nèi)嵌的GPS傳感器獲取，又可以通過用戶所處區(qū)域內(nèi)的通信基站進(jìn)行定位，基站定位更有利于用戶隱私的保護(hù)。為了滿足不同用戶的不同需求，F(xiàn)RSHV模型能夠同時對GPS位置數(shù)據(jù)和基站位置數(shù)據(jù)進(jìn)行處理。設(shè)

21、用戶集合為U，其中n表示用戶個數(shù)，Di表示用戶ui采集數(shù)據(jù)的日期的集合，其中mi表示用戶ui采集數(shù)據(jù)的總天數(shù)。Fi表示用戶ui的全部朋友組成的集合，其中fi表示用戶ui的好友的個數(shù)。所有用戶所有天的軌跡數(shù)據(jù)的集合Trace，其中Tracei 表示用戶ui所有天采集的軌跡序列的集合，Tracei,k表示用戶ui在k這一天的軌跡序列，ni,k表示用戶ui在k這一天采集的軌跡數(shù)據(jù)的條數(shù)。 對于GPS和基站表示的用戶軌跡序列進(jìn)行預(yù)處理時，我們使用以下三種做法分別構(gòu)造三層算法的輸入。2.1.1 軌跡數(shù)據(jù)處理GPS位置數(shù)據(jù)處理。首先，對每個用戶每天的數(shù)據(jù)Tracei,k進(jìn)行濾波，目的是減少數(shù)據(jù)噪聲；而后對

22、濾波后的數(shù)據(jù)按半小時進(jìn)行劃分，將用戶ui的每天數(shù)據(jù)Tracei,k按時間均分為48份，Sep_tracei,k,s表示第i個用戶第k天第s份數(shù)據(jù)；對Sep_tracei,k,s按經(jīng)緯度計(jì)算平均值，并將用戶i在第k天新的軌跡序列表示為Ntracei,k，將Ntracei表示用戶i所有天采集的數(shù)據(jù)作為用戶ui使用第一層算法計(jì)算其與全部好友關(guān)系強(qiáng)度的輸入。基站位置數(shù)據(jù)處理。對每個用戶每天的數(shù)據(jù)按半小時進(jìn)行劃分，即將用戶ui第k天的數(shù)據(jù)Tracei,k按時間均分為48份，Sep_tracei,k,s表示第i個用戶第k天第s份數(shù)據(jù)；對每半個小時內(nèi)數(shù)據(jù)計(jì)算依次不重復(fù)的基站號序列；再將每天48份數(shù)據(jù)重新拼成

23、一個序列Ntracei,k表示用戶i在k這一天采集的全部的數(shù)據(jù)，目的是對每天軌跡序列降維，以降低計(jì)算的復(fù)雜度，將Ntracei表示用戶i所有天的數(shù)據(jù)作為用戶ui使用第一層算法的輸入。2.1.2 語義位置數(shù)據(jù)處理GPS位置數(shù)據(jù)處理。采用文獻(xiàn)17中的聚類方法對所有用戶的軌跡數(shù)據(jù)進(jìn)行聚類，得到全部語義位置序列為Loc。通過聚類得到用戶ui在第k天的語義位置序列Ltracei,k；用戶ui的全部語義位置序列表示Ltracei，所有用戶的所有語義位置序列表示為Ltrace，對序列Ltrace添加對應(yīng)的時間標(biāo)記后記為LLtrace，訓(xùn)練對應(yīng)的LDA主題模型并記為LLDA(K)，K表示主題個數(shù)。對每個用戶每

24、天的數(shù)據(jù)按半個小時進(jìn)行劃分，即將用戶ui的每天數(shù)據(jù)Ltracei,k按時間均分為48份，Sep_tracei,k,s表示第i個用戶第k天第s份數(shù)據(jù)；對每份數(shù)據(jù)計(jì)算不重復(fù)出現(xiàn)的語義位置，并對每個位置加上時間標(biāo)記。用戶ui在第k天第s時間段語義位置序列表示為Tltracei,k,s，將Tltracei表示用戶i所有天的語義位置序列作為用戶ui使用第二層算法計(jì)算其與全部好友關(guān)系強(qiáng)度的輸入?；疚恢脭?shù)據(jù)處理。將每一個基站視為一個語義位置，即Ltrace=Trace，其余處理與GPS位置數(shù)據(jù)處理完全相同。2.1.3 語義標(biāo)簽數(shù)據(jù)處理GPS位置數(shù)據(jù)處理。對前文得到的序列Loc中每一個語義位置采用文獻(xiàn)17中

25、的方法標(biāo)記其語義標(biāo)簽，標(biāo)記語義標(biāo)簽后，用戶ui第k天的語義標(biāo)簽序列表示為Stracei,k，用戶ui的全部語義標(biāo)簽序列表示Stracei，所有用戶的所有語義標(biāo)簽序列表示為Strace，對序列Strace添加對應(yīng)的時間標(biāo)記后記為SStrace，訓(xùn)練對應(yīng)的LDA主題模型并記為SLDA(K)，K表示主題個數(shù)。對每個用戶每天的數(shù)據(jù)按半個小時進(jìn)行劃分，即將用戶ui的每天數(shù)據(jù)Stracei,k按時間均分為48份，Sep_tracei,k,s表示第i個用戶第k天第s份數(shù)據(jù)；對每份數(shù)據(jù)計(jì)算不重復(fù)出現(xiàn)的語義標(biāo)簽，并對每個位置加上時間標(biāo)記。用戶ui在第k天第s時間段內(nèi)的語義位置序列表示為Tstracei,k,s，

26、將Tstracei表示用戶i所有天的語義標(biāo)簽序列作為用戶ui使用第三層算法計(jì)算其與全部好友關(guān)系強(qiáng)度的輸入?；疚恢脭?shù)據(jù)處理。計(jì)算每一個基站對應(yīng)的語義標(biāo)簽，其余處理與GPS數(shù)據(jù)處理完全相同。2.2關(guān)系強(qiáng)度計(jì)算計(jì)算每一個用戶ui與其每一個朋友uk（ukFi）之間的關(guān)系強(qiáng)度，并對Fi中的每一個朋友，按照其與ui的關(guān)系強(qiáng)度大小按降序排列，使此序列中任意兩個朋友與ui的關(guān)系強(qiáng)弱順序盡可能與實(shí)際情況一致。基于DTW及序列熵值加權(quán)計(jì)算用戶之間的關(guān)系強(qiáng)度。對用戶ui的每一個好友uk，利用節(jié)2.1.1中得到的Ntracei和Ntracek計(jì)算其軌跡序列相似度。Ntracei,a表示用戶ui在第a天的數(shù)據(jù)，其中a

27、Di，Ntracek,b表示用戶uk在第b天的數(shù)據(jù)，其中bDk。S(a,b)表示若a=b則取值為1，否則取值為0。DTW(Ntracei,a,Ntracek,b)表示用戶ui在a這一天的軌跡和用戶uk在b這一天的軌跡的相似度, Entropy(Ntracei,a)表示用戶ui在a這一天的軌跡序列的熵值。用戶ui和用戶uk的基于軌跡序列的關(guān)系強(qiáng)度計(jì)算方法見公式1。DTW計(jì)算的是距離，距離越小相似度越大，即該公式值越小，則兩個用戶關(guān)系強(qiáng)度越強(qiáng)。Ent_Dtw(ui,uk)=aDi,bDkS(a,b)DTW(Ntracei,a,Ntracek,b)Entropy(Ntracei,a) (1)基于主題

28、模型計(jì)算用戶之間的關(guān)系強(qiáng)度。Tltracei表示用戶ui根據(jù)節(jié)2.1.2得到的語義位置序列，Tltracek表示用戶uk根據(jù)節(jié)2.1.2得到的語義位置序列。T(a,p,b,q)表示若用戶ui在a這一天第p個時間段和用戶uk在b這一天第q個時間段數(shù)據(jù)均存在則為1，否則為0。LLDAK.inf(Tltracei,a,p)表示對Tltracei,a,p推斷得到的主題分布，通常表示為K維的向量，其中K表示主題的個數(shù)?；谟脩粽Z義位置的行為模式的關(guān)系強(qiáng)度計(jì)算方法見公式2，其中cos表示余弦相似度。LocLDAui,uk=aDi,bDkS(a,b)p=q=148Ta,p,b,q*cos(LLDAK.inf

29、(Tltracei,a,p),LLDAK.inf(Tltracek,b,q) (2)基于用戶語義標(biāo)簽的行為模式的關(guān)系強(qiáng)度計(jì)算公式與基于語義位置的關(guān)系強(qiáng)度計(jì)算公式相似，見公式3。SemLDAui,uk=aDi,bDkSa,bp=q=148Ta,p,b,q*cos(SLDAK.inf(Tstracei,a,p),SLDAK.inf(Tstracek,b,q) (3)我們更關(guān)注的是用戶和好友A的關(guān)系強(qiáng)度大于或小于用戶與好友B的關(guān)系強(qiáng)度，因此實(shí)際計(jì)算結(jié)果為用戶與其全部好友按關(guān)系強(qiáng)度降序排列得到的好友序列。對于用戶ui，我們對其全部好友Fi中的每一個朋友uk使用Ent_DTW(ui,uk)計(jì)算用戶ui和

30、用戶uk之間的關(guān)系強(qiáng)度，對Fi中的每一個朋友按照計(jì)算得到的關(guān)系強(qiáng)度降序排列得到Ei=ud1,udfi。在此基礎(chǔ)上，我們使用LocLDA(ui,uk)計(jì)算用戶ui和用戶uk之間的關(guān)系強(qiáng)度，并對Fi中的每一個朋友按照計(jì)算得到的關(guān)系強(qiáng)度降序排列得到Li=ul1,ulfi，最后我們使用SemLDA(ui,uk)計(jì)算用戶ui和用戶uk之間的關(guān)系強(qiáng)度，并對Fi中的每一個朋友按照計(jì)算得到的關(guān)系強(qiáng)度降序排列得到Si=us1,usfi。2.3 結(jié)果投票我們采用集成學(xué)習(xí)的思想對三個層次的計(jì)算結(jié)果Ei、Li、Si進(jìn)行投票，投票規(guī)則為：對于與用戶ui關(guān)系第k強(qiáng)的好友uvk（k1且Kfi），我們使用三個層次對應(yīng)的方法分

31、別計(jì)算得到udk、ulk和usk，若這三個用戶都不相同，則我們認(rèn)為uvk=udk，若某個用戶比如ulk=usk出現(xiàn)兩次及以上，我們認(rèn)為uvk=ulk，最終以Vi=uv1,uvf1作為投票結(jié)果。3 數(shù)據(jù)集及評估方法3.1 移動數(shù)據(jù)集在實(shí)驗(yàn)驗(yàn)證過程中，我們使用MIT媒體實(shí)驗(yàn)室采集的The Reality Mining Data數(shù)據(jù)集1。實(shí)驗(yàn)中使用到的信息主要包括每個用戶每天由基站號組成的軌跡序列、所有用戶之間的朋友關(guān)系，以及各個用戶的調(diào)查問卷，同時數(shù)據(jù)集中還提供了每個基站號和區(qū)域號對應(yīng)的位置的語義標(biāo)簽。數(shù)據(jù)集1中采集的位置信息是基站信息，雖然基站定位方式的精確度比GPS定位方式低，但更有利于用戶隱

32、私的保護(hù)，這也是我們選擇數(shù)據(jù)集1進(jìn)行實(shí)驗(yàn)的主要原因之一。在對數(shù)據(jù)集的分析過程中，我們發(fā)現(xiàn)朋友關(guān)系信息表中存在如下問題：部分用戶自己和自己是好朋友，另外一部分用戶自己和自己不是好朋友；某用戶和另一個用戶是好朋友，另一個用戶和該用戶不是好朋友。我們認(rèn)為用戶之間的好友關(guān)系應(yīng)該滿足反自反和對稱。經(jīng)過這樣處理后，我們得到好友數(shù)大于1的用戶共有34個，剔除只有一個好友的用戶。在后面的實(shí)驗(yàn)中，我們使用這34個用戶及其全部朋友的數(shù)據(jù)來對FRSHV模型進(jìn)行驗(yàn)證。3.2評估方法與基準(zhǔn)根據(jù)上文提到的社會心理學(xué)一些研究成果，態(tài)度、興趣、價值觀、背景和人格等方面更相似的人關(guān)系更親密，尤其是對生活在一起的一個群體來說，如

33、果在這些方面類似并且對某些問題的看法相似，則其關(guān)系可能就更加緊密。在現(xiàn)實(shí)生活當(dāng)中，通常通過問卷調(diào)查方式來獲得這這些方面的信息，問卷調(diào)查結(jié)果是這些方面的一種真實(shí)體現(xiàn)和反映，因此，我們認(rèn)為問卷調(diào)查結(jié)果越相似的用戶關(guān)系越親密，為此，我們根據(jù)數(shù)據(jù)集1中問卷調(diào)查回答結(jié)果的相似性作為朋友之間真實(shí)的關(guān)系強(qiáng)度。經(jīng)過對數(shù)據(jù)集1中的問卷調(diào)查的仔細(xì)分析，我們發(fā)現(xiàn)問卷調(diào)查中的所有問題基本上可以分為兩類：第一類問題可以用“是”或“否”來回答，另一類問題答案多選，但是每個選項(xiàng)按順序呈現(xiàn)強(qiáng)度增強(qiáng)、次數(shù)增加或者次數(shù)減少。為了計(jì)算用戶與朋友之間的真實(shí)的關(guān)系強(qiáng)度，針對這兩類問題，我們采用不同的評分方法。針對第一類問題當(dāng)中的每一個

34、問題，如果兩個朋友的答案相同，則評分為1，否則評分為0；針對第二類問題當(dāng)中的每一個問題，如果兩個朋友的答案越接近，則評分越高，并且將評分歸一化到0-1之間，使得每個問題在總的關(guān)系強(qiáng)度評分中占有相同的權(quán)重。在完成對所有問題評分基礎(chǔ)上，對所有評分進(jìn)行累加求和，以此作為兩個朋友之間的關(guān)系強(qiáng)度。依次對每個用戶及其所有朋友按上述方法計(jì)算其與每個朋友之間的關(guān)系強(qiáng)度，并對其所有朋友的評分按降序排列，得到一個用戶與其所有朋之間的關(guān)系強(qiáng)度序列，以此序列作為該用戶與其朋友之間真實(shí)的關(guān)系強(qiáng)度。在此基礎(chǔ)上，使用FRSHV模型計(jì)算出來的用戶與朋友之間的關(guān)系強(qiáng)度序列與真實(shí)的關(guān)系強(qiáng)度序列進(jìn)行對比，驗(yàn)證FRSHV模型的有效性

35、。為了度量使用FRSHV模型計(jì)算出來的用戶與朋友之間關(guān)系強(qiáng)度序列Vi與真實(shí)的關(guān)系強(qiáng)度序列Gi的一致性，我們參考文獻(xiàn)18，提出一種基于逆序?qū)?shù)的有序序列一致性度量方法。設(shè)A為一個有N個數(shù)字的有序集(N>1)，且所有數(shù)字均不相同，如果存在正整數(shù)i，j，使得1i<jN，而Ai>Aj，則稱<Ai,Aj>為A的一個逆序?qū)?。A中全部的逆序?qū)Φ膫€數(shù)稱為逆序?qū)?shù)。我們把序列Gi作為有序集，來計(jì)算序列Vi的逆序?qū)?shù)。設(shè)該用戶共有fi個好友，若逆序?qū)?shù)為0，說明實(shí)驗(yàn)結(jié)果與實(shí)際結(jié)果完全一致，若逆序?qū)?shù)為fi*(fi-1)2，則說明實(shí)驗(yàn)結(jié)果恰好是實(shí)際結(jié)果的逆序。我們提出的有序序列一致性度

36、量公式見公式4，其中fi為用戶ui的全部好友的個數(shù)，ki為Vi相對于Gi的逆序?qū)?shù)。對每個用戶可計(jì)算得到一個一致性評分，在此基礎(chǔ)上，對所有用戶的一致性評分取平均值，以此作為模型FRSHV對朋友關(guān)系強(qiáng)度度量有效程度的度量，見公式5。scoreui=1-Kifi(fi-1)/2 (4)score=1ni=1nscore(ui) (5)4 實(shí)驗(yàn)驗(yàn)證及分析實(shí)驗(yàn)環(huán)境為windows 7 64位，4核，3.2GHz主頻，8G內(nèi)存，使用Python編碼實(shí)現(xiàn)。為了確定用戶之間的物理距離，首先要確定基站之間的距離，并以此作為用戶之間的物理距離。我們采取如下方法來定義基站之間的距離，將每天用戶手機(jī)連接過的基站視為

37、一條基站序列，對于基站A和B，我們從所有用戶所有天的基站序列中找到同時出現(xiàn)A和B的序列，計(jì)算每個序列中A和B中間不同的基站號的個數(shù)，取最小值加一作為基站A和基站B之間的距離。若通過上述方法能夠計(jì)算出兩個基站之間的距離，則稱為這兩個基站之間的距離存在。若A和B從未在同一個基站序列中出現(xiàn)過，則定義A和B之間的距離為所有兩個基站距離存在且最大的距離的K倍，K為一個正實(shí)數(shù)參數(shù)，在后面實(shí)驗(yàn)中我們能夠看到該參數(shù)對實(shí)驗(yàn)結(jié)果的影響。4.1 基于軌跡相似性計(jì)算用戶之間的關(guān)系強(qiáng)度通過上文對基站距離的定義，我們使用DTW以及歸一化后的DTW計(jì)算第一層用戶之間的相似度，一致性評分可通過公式4和公式5計(jì)算得到，上文論述

38、到我們使用參數(shù)K定義兩個不存在距離的基站的距離，不同的參數(shù)K以及不同方法對結(jié)果的影響見圖2。圖2 參數(shù)K對一致性評分結(jié)果的影響Figure 2 K influences the consistency在上一個實(shí)驗(yàn)的基礎(chǔ)上，我們對DTW方法以及歸一化的DTW方法使用序列熵值加權(quán)，對應(yīng)2.2節(jié)的Ei，一致性評分的實(shí)驗(yàn)結(jié)果見圖3。圖3 用熵值加權(quán)前后結(jié)果對比（K=2.5）Figure 3 The consistency of weighted and non-weighted (K=2.5)4.2 基于語義位置相似性計(jì)算用戶之間的關(guān)系強(qiáng)度在計(jì)算關(guān)系強(qiáng)度的過程中，使用LDA模型進(jìn)行推斷，因?yàn)橥茢噙^程進(jìn)

39、行隨機(jī)初始化，從而使得LDA模型的每次執(zhí)行結(jié)果不一定完全相同，因此，在實(shí)驗(yàn)中，針對每個不同的參數(shù)值（即主題個數(shù)）執(zhí)行10次，并將每次計(jì)算獲得的Li與Gi進(jìn)行一致性評分，對所有用戶按公式5計(jì)算最終的一致性評分，進(jìn)而取這10個一致性評分的中位數(shù)作為該參數(shù)對應(yīng)的一致性評分，如圖4所示。圖4 主題個數(shù)及對應(yīng)的一致性評分實(shí)驗(yàn)結(jié)果Figure 4 The influence of topic numbers to consistency4.3 基于語義標(biāo)簽相似性計(jì)算用戶之間的關(guān)系強(qiáng)度數(shù)據(jù)集1中提供了基站號和區(qū)域號對應(yīng)的位置的語義標(biāo)簽，對所有語義標(biāo)簽加上時間標(biāo)記，將每個帶時間標(biāo)記的語義標(biāo)簽視為單詞，每天的語

40、義標(biāo)簽序列視為句子，每個用戶所有語義標(biāo)簽序列視為文檔，使用所有用戶的全部文檔對LDA模型進(jìn)行訓(xùn)練，其實(shí)驗(yàn)過程與上面的基于語義位置的實(shí)驗(yàn)過程一樣，對應(yīng)2.2節(jié)的Si并計(jì)算一致性評分。圖5展示了在主題個數(shù)取不同值時所對應(yīng)的一致性評分結(jié)果。圖 5主題個數(shù)和對應(yīng)一致性評分的實(shí)驗(yàn)結(jié)果Figure 5 The influence of topic numbers to consistency語義標(biāo)簽有實(shí)際含義，以主題個數(shù)75為例，通過觀察LDA模型學(xué)習(xí)到的主題，發(fā)現(xiàn)該模型學(xué)習(xí)得到了3個主題，如表1所示，主題1表示的是晚上在實(shí)驗(yàn)室或教室，主題2表示早上和晚上在家，主題3表示的上午在實(shí)驗(yàn)室。表1 LDA模型學(xué)

41、習(xí)到的不同主題示例Table 1 some topics of LDA learned主題1主題2主題3Tech sq_47，Tech sq_46，Tech sq_40，Tech sq_38，Tech sq_39，Tech sq_42home_14，home_15，home_8，home_6，home_0，home_44，Media lab_17，Media lab_16，Media lab_20，Media lab_18，Media lab_19，Tech sq_174.4 對計(jì)算結(jié)果進(jìn)行投票上面的實(shí)驗(yàn)分別描述了層級模型FRSHV每一層的實(shí)驗(yàn)結(jié)果，在此基礎(chǔ)上，我們使用前面描述的投票規(guī)則對三層

42、每層最好的實(shí)驗(yàn)結(jié)果進(jìn)行投票，并以編輯距離19計(jì)算的結(jié)果作為基準(zhǔn)，三層結(jié)果投票的實(shí)驗(yàn)結(jié)果見圖6。圖6 投票結(jié)果及分別只使用一種方法的結(jié)果對比Figure 6 Vote result VS simple method通過實(shí)驗(yàn)結(jié)果我們可以發(fā)現(xiàn)，使用投票方法后，我們可以更好的度量用戶之間的關(guān)系強(qiáng)度，觀察實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)基于投票的方法比編輯距離一致性評分高出近10%。5 結(jié)論本文針對如何度量日常生活中人們之間的關(guān)系強(qiáng)度問題展開研究，提出了一個從日常軌跡、語義位置以及語義標(biāo)簽三個層次度量用戶與朋友之間關(guān)系強(qiáng)度的層級模型FRSHV。我們采用基站數(shù)據(jù)對該模型進(jìn)行了驗(yàn)證，觀察實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)基于投票的方法比編輯距離一致

43、性評分高出近10%。下一步我們將對相關(guān)度量方法進(jìn)行進(jìn)一步的優(yōu)化，利用更多的消息如通話記錄，短信等信息，進(jìn)而對多種數(shù)據(jù)進(jìn)行融合來度量用戶之間的關(guān)系強(qiáng)度。參考文獻(xiàn)（References）1 Eagle N, Pentland A. Reality mining: sensing complex social systemsJ. Personal and ubiquitous computing, 2006, 10(4): 255-268.2 Aharony N, Pan W, Ip C, et al. Social fMRI: Investigating and shaping social me

44、chanisms in the real worldJ. Pervasive and Mobile Computing, 2011, 7(6): 643-659.3 Wang R, Chen F, Chen Z, et al. StudentLife: assessing mental health, academic performance and behavioral trends of college students using smartphonesC/Proceedings of the 2014 ACM International Joint Conference on Perv

45、asive and Ubiquitous Computing. ACM, 2014: 3-14.4 Stopczynski A, Sekara V, Sapiezynski P, et al. Measuring large-scale social networks with high resolutionJ. PloS one, 2014, 9(4): e95978.5 Granovetter M S. The strength of weak tiesJ. American journal of sociology, 1973: 1360-1380.6 Wegner D M. The i

46、llusion of conscious willM. MIT press, 2002.7 Burrows R, Nettleton S, Pleace N, et al. Virtual community care? Social policy and the emergence of computer mediated social supportJ. Information, Communication & Society, 2000, 3(1): 95-121.8 Petróczi A, Nepusz T, Bazsó F. Measuring tie-strength in virtual social networksJ. Connections, 2007, 27(2): 39-52.9 Ma C, Cao J, Yang L, et al. Effective social relationship measurement based o