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

2、其日常軌跡之間的相似度，進而使用軌跡序列熵值對用戶每天軌跡的相似度進行加權處理，將其作為朋友之間的關系強度；采用主題模型LDA分別計算朋友之間的基于語義位置和語義標簽的行為模式的相似性，將其作為朋友之間的關系強度；采用集成學習的思想對三個層次的度量結果進行投票，以投票結果作為最終的朋友之間的關系強度；在公開數據集上對FRSHV模型的有效性進行了實驗驗證，結果表明該模型能夠有效地度量朋友之間的關系強度。關鍵詞：關系強度；軌跡相似度；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目前，內嵌了各種各樣傳感器的智能手機已經成為人們日常生活中集通信、計算及感知于一體的移動平臺。通過內嵌的各種傳感器如GPS、加速度、麥克風等可以隨時隨地感知和獲取人們自身及其周圍環境的各種信息，通過智能手機所收集各種數據研究人們之間的日常交互行為和人們之間的社會關系成為普適計算領域當中一個重點研究的問題。RealityMining1基于手機所收集的各種數據推理人們之間的社會交互關系以及群組的活動韻律，從而洞察個人和組織的行為模式； fMRi2研究分析了家庭和朋友圈對個體行為在社交網絡中所受的影響；StudentLife3研究了在校學生的日常活動

8、、交互情況、精神健康與學業成績之間的關系；文獻4則從多渠道、細粒度地收集各種反映在校學生日常活動和交互情況的各種數據，從多個層面真實、全面地反映學生日常活動以及他們之間的交互行為和交互關系。但是，這些研究重點關注的是人們之間的日常交互行為和交互關系，而關系強度度量的是人們之間的親密程度，通過關系強度，我們可以更好地了解人們之間的關系的強弱，進而了解人們之間的親密程度，從而可以更好地預測社會關系的演變以及社交結構的變化，促進信息傳播以及傳染疾病的預防與控制等。社會關系強度理論始于文獻5中對于弱關系的研究，將弱關系和強關系的測量分為四個維度，即交往人員之間的互動頻率、感情的投入程度、關系親密程度和

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

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

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

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

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

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

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

16、戶與朋友之間的關系強度（計算過程見節2.2）。1.3基于主題模型LDA的計算方法在日常生活當中，人們之間尤其是好友之間其行為模式之間具有一定的相似性，如經常在某些時間段（晚上）去一些地方（餐館）等等。基于位置的用戶行為模式一方面能夠反映用戶在物理層次的相遇，另一方面能夠在一定程度上體現用戶的相似性，前文已經從社會心理學的角度闡述了相遇次數與用戶關系強度的關系，文獻14認為人們傾向于喜歡在態度、興趣、價值觀、背景和人格上和其相似的人，因此，在日常生活當中行為相似的人之間更可能成為朋友，而根據社會心理學的研究成果，用戶的相似性對用戶的關系強度也有一定的影響，為此，我們在通過基于用戶軌跡度量用戶之間

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

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

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

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

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

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

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

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

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

26、將Tstracei表示用戶i所有天的語義標簽序列作為用戶ui使用第三層算法計算其與全部好友關系強度的輸入。基站位置數據處理。計算每一個基站對應的語義標簽，其余處理與GPS數據處理完全相同。2.2關系強度計算計算每一個用戶ui與其每一個朋友uk（ukFi）之間的關系強度，并對Fi中的每一個朋友，按照其與ui的關系強度大小按降序排列，使此序列中任意兩個朋友與ui的關系強弱順序盡可能與實際情況一致。基于DTW及序列熵值加權計算用戶之間的關系強度。對用戶ui的每一個好友uk，利用節2.1.1中得到的Ntracei和Ntracek計算其軌跡序列相似度。Ntracei,a表示用戶ui在第a天的數據，其中a

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

28、模型計算用戶之間的關系強度。Tltracei表示用戶ui根據節2.1.2得到的語義位置序列，Tltracek表示用戶uk根據節2.1.2得到的語義位置序列。T(a,p,b,q)表示若用戶ui在a這一天第p個時間段和用戶uk在b這一天第q個時間段數據均存在則為1，否則為0。LLDAK.inf(Tltracei,a,p)表示對Tltracei,a,p推斷得到的主題分布，通常表示為K維的向量，其中K表示主題的個數。基于用戶語義位置的行為模式的關系強度計算方法見公式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)基于用戶語義標簽的行為模式的關系強度計算公式與基于語義位置的關系強度計算公式相似，見公式3。SemLDAui,uk=aDi,bDkSa,bp=q=148Ta,p,b,q*cos(SLDAK.inf(Tstracei,a,p),SLDAK.inf(Tstracek,b,q) (3)我們更關注的是用戶和好友A的關系強度大于或小于用戶與好友B的關系強度，因此實際計算結果為用戶與其全部好友按關系強度降序排列得到的好友序列。對于用戶ui，我們對其全部好友Fi中的每一個朋友uk使用Ent_DTW(ui,uk)計算用戶ui和

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

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

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

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

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

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

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

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

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

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

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

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 對計算結果進行投票上面的實驗分別描述了層級模型FRSHV每一層的實驗結果，在此基礎上，我們使用前面描述的投票規則對三層

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

43、性評分高出近10%。下一步我們將對相關度量方法進行進一步的優化，利用更多的消息如通話記錄，短信等信息，進而對多種數據進行融合來度量用戶之間的關系強度。參考文獻（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