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

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

2、其日常軌跡之間的相似度，進而使用軌跡序列熵值對用戶每天軌跡的相似度進行加權(quán)處理，將其作為朋友之間的關(guān)系強度；采用主題模型LDA分別計算朋友之間的基于語義位置和語義標簽的行為模式的相似性，將其作為朋友之間的關(guān)系強度；采用集成學(xué)習的思想對三個層次的度量結(jié)果進行投票，以投票結(jié)果作為最終的朋友之間的關(guān)系強度；在公開數(shù)據(jù)集上對FRSHV模型的有效性進行了實驗驗證，結(jié)果表明該模型能夠有效地度量朋友之間的關(guān)系強度。關(guān)鍵詞：關(guān)系強度；軌跡相似度；DTW；熵；LDA；投票中圖分類號：TP391 文獻標志碼：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īng)成為人們?nèi)粘Ｉ钪屑ㄐ拧⒂嬎慵案兄谝惑w的移動平臺。通過內(nèi)嵌的各種傳感器如GPS、加速度、麥克風等可以隨時隨地感知和獲取人們自身及其周圍環(huán)境的各種信息，通過智能手機所收集各種數(shù)據(jù)研究人們之間的日常交互行為和人們之間的社會關(guān)系成為普適計算領(lǐng)域當中一個重點研究的問題。RealityMining1基于手機所收集的各種數(shù)據(jù)推理人們之間的社會交互關(guān)系以及群組的活動韻律，從而洞察個人和組織的行為模式； fMRi2研究分析了家庭和朋友圈對個體行為在社交網(wǎng)絡(luò)中所受的影響；StudentLife3研究了在校學(xué)生的日?；顒?/p>

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

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

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

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

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

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

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

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

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

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

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

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

20、不同的位置可能擁有相同的語義標簽，“辦公室”、“家”等語義概念在每個用戶軌跡中都可能出現(xiàn)，而這些語義概念在原始數(shù)據(jù)中會表現(xiàn)為不同的基站號和區(qū)域號或不同的GPS經(jīng)緯度，因此用戶的語義標簽數(shù)據(jù)更能體現(xiàn)用戶群體的日常習慣，因此本層考慮的行為模式更傾向于群體的行為模式，從而根據(jù)不同用戶在群體中表現(xiàn)出的行為模式來度量用戶與朋友之間的關(guān)系強度。2.1 GPS及基站位置數(shù)據(jù)處理在日常生活中，用戶的位置既可以通過智能手機內(nèi)嵌的GPS傳感器獲取，又可以通過用戶所處區(qū)域內(nèi)的通信基站進行定位，基站定位更有利于用戶隱私的保護。為了滿足不同用戶的不同需求，F(xiàn)RSHV模型能夠同時對GPS位置數(shù)據(jù)和基站位置數(shù)據(jù)進行處理。設(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和基站表示的用戶軌跡序列進行預(yù)處理時，我們使用以下三種做法分別構(gòu)造三層算法的輸入。2.1.1 軌跡數(shù)據(jù)處理GPS位置數(shù)據(jù)處理。首先，對每個用戶每天的數(shù)據(jù)Tracei,k進行濾波，目的是減少數(shù)據(jù)噪聲；而后對

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

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

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

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

26、將Tstracei表示用戶i所有天的語義標簽序列作為用戶ui使用第三層算法計算其與全部好友關(guān)系強度的輸入?；疚恢脭?shù)據(jù)處理。計算每一個基站對應(yīng)的語義標簽，其余處理與GPS數(shù)據(jù)處理完全相同。2.2關(guān)系強度計算計算每一個用戶ui與其每一個朋友uk（ukFi）之間的關(guān)系強度，并對Fi中的每一個朋友，按照其與ui的關(guān)系強度大小按降序排列，使此序列中任意兩個朋友與ui的關(guān)系強弱順序盡可能與實際情況一致?；贒TW及序列熵值加權(quán)計算用戶之間的關(guān)系強度。對用戶ui的每一個好友uk，利用節(jié)2.1.1中得到的Ntracei和Ntracek計算其軌跡序列相似度。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)系強度計算方法見公式1。DTW計算的是距離，距離越小相似度越大，即該公式值越小，則兩個用戶關(guān)系強度越強。Ent_Dtw(ui,uk)=aDi,bDkS(a,b)DTW(Ntracei,a,Ntracek,b)Entropy(Ntracei,a) (1)基于主題

28、模型計算用戶之間的關(guān)系強度。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ù)。基于用戶語義位置的行為模式的關(guān)系強度計算方法見公式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)基于用戶語義標簽的行為模式的關(guān)系強度計算公式與基于語義位置的關(guān)系強度計算公式相似，見公式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)系強度大于或小于用戶與好友B的關(guān)系強度，因此實際計算結(jié)果為用戶與其全部好友按關(guān)系強度降序排列得到的好友序列。對于用戶ui，我們對其全部好友Fi中的每一個朋友uk使用Ent_DTW(ui,uk)計算用戶ui和

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

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

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

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

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

35、。為了度量使用FRSHV模型計算出來的用戶與朋友之間關(guān)系強度序列Vi與真實的關(guān)系強度序列Gi的一致性，我們參考文獻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作為有序集，來計算序列Vi的逆序?qū)?shù)。設(shè)該用戶共有fi個好友，若逆序?qū)?shù)為0，說明實驗結(jié)果與實際結(jié)果完全一致，若逆序?qū)?shù)為fi*(fi-1)2，則說明實驗結(jié)果恰好是實際結(jié)果的逆序。我們提出的有序序列一致性度

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

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

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

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

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

41、習到的不同主題示例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 對計算結(jié)果進行投票上面的實驗分別描述了層級模型FRSHV每一層的實驗結(jié)果，在此基礎(chǔ)上，我們使用前面描述的投票規(guī)則對三層

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

43、性評分高出近10%。下一步我們將對相關(guān)度量方法進行進一步的優(yōu)化，利用更多的消息如通話記錄，短信等信息，進而對多種數(shù)據(jù)進行融合來度量用戶之間的關(guā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