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

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

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

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

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

10、游覽等等，通過(guò)對(duì)這些信息的分析處理，可以更好地度量朋友之間的關(guān)系強(qiáng)度。為了方便描述，我們將本文分析處理的對(duì)象稱為用戶，我們認(rèn)為用戶和陌生人之間的關(guān)系強(qiáng)度因?yàn)榛ゲ徽J(rèn)識(shí)應(yīng)該為零，但是對(duì)一個(gè)用戶來(lái)說(shuō)，雖然與一些陌生人不認(rèn)識(shí)，也可能會(huì)經(jīng)常在一些地方同時(shí)出現(xiàn)，因此我們只考慮用戶和其好友之間的關(guān)系強(qiáng)度。本文設(shè)想能夠在一定程度上反映兩個(gè)朋友之間的關(guān)系，而非完整全面的度量?jī)蓚€(gè)用戶之間的關(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)的時(shí)間和共

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

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

13、學(xué)相關(guān)研究成果的分析，我們認(rèn)為人們之間的關(guān)系強(qiáng)度與他們之間的軌跡相似性以及日常行為的相似性密切相關(guān)，因此，為了有效地度量人們之間的關(guān)系強(qiáng)度，我們從人們之間的日常軌跡和日常行為這兩個(gè)角度出發(fā)，提出采用不同計(jì)算方法來(lái)計(jì)算人們之間的關(guān)系強(qiáng)度。1.1基于DTW模型的計(jì)算方法空間距離能夠直觀反映人們之間在物理世界中的距離，空間距離非常接近的用戶在現(xiàn)實(shí)生活中會(huì)有更多的面對(duì)面的交互，從而增強(qiáng)兩個(gè)人之間的關(guān)系強(qiáng)度。根據(jù)社會(huì)心理學(xué)的研究成果，文獻(xiàn)10在一個(gè)大型住宅區(qū)研究了接近性效應(yīng)（接近性效應(yīng)指兩個(gè)人住的越近越可能是朋友），結(jié)果表明人們居住得越近，不管這種近是物理距離還是功能性距離，人們?cè)饺菀追Q為朋友。文獻(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ù)看作一個(gè)時(shí)間序列，因此同樣可以使用DTW方法度量軌跡的相似度，并且將軌跡相似度作為人們之間的關(guān)系強(qiáng)度。通過(guò)深入分析DTW算法可知，序列的長(zhǎng)度越長(zhǎng)，則距離可能越大。因此，我們采用文獻(xiàn)13中的三種歸一化方法對(duì)DTW的計(jì)算結(jié)果進(jìn)行進(jìn)一步的處理和優(yōu)化，即DTW結(jié)果除以最優(yōu)變形路徑的長(zhǎng)度、DTW結(jié)果除以兩個(gè)序列中較短序列的長(zhǎng)度以及DTW結(jié)果除以兩個(gè)序列中較長(zhǎng)序列的長(zhǎng)度等三種方法對(duì)DTW計(jì)算結(jié)

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

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

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

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

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

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

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

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

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

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

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

26、將Tstracei表示用戶i所有天的語(yǔ)義標(biāo)簽序列作為用戶ui使用第三層算法計(jì)算其與全部好友關(guān)系強(qiáng)度的輸入?；疚恢脭?shù)據(jù)處理。計(jì)算每一個(gè)基站對(duì)應(yīng)的語(yǔ)義標(biāo)簽，其余處理與GPS數(shù)據(jù)處理完全相同。2.2關(guān)系強(qiáng)度計(jì)算計(jì)算每一個(gè)用戶ui與其每一個(gè)朋友uk（ukFi）之間的關(guān)系強(qiáng)度，并對(duì)Fi中的每一個(gè)朋友，按照其與ui的關(guān)系強(qiáng)度大小按降序排列，使此序列中任意兩個(gè)朋友與ui的關(guān)系強(qiáng)弱順序盡可能與實(shí)際情況一致?；贒TW及序列熵值加權(quán)計(jì)算用戶之間的關(guān)系強(qiáng)度。對(duì)用戶ui的每一個(gè)好友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ì)算方法見(jiàn)公式1。DTW計(jì)算的是距離，距離越小相似度越大，即該公式值越小，則兩個(gè)用戶關(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得到的語(yǔ)義位置序列，Tltracek表示用戶uk根據(jù)節(jié)2.1.2得到的語(yǔ)義位置序列。T(a,p,b,q)表示若用戶ui在a這一天第p個(gè)時(shí)間段和用戶uk在b這一天第q個(gè)時(shí)間段數(shù)據(jù)均存在則為1，否則為0。LLDAK.inf(Tltracei,a,p)表示對(duì)Tltracei,a,p推斷得到的主題分布，通常表示為K維的向量，其中K表示主題的個(gè)數(shù)?；谟脩粽Z(yǔ)義位置的行為模式的關(guān)系強(qiáng)度計(jì)算方法見(jià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)基于用戶語(yǔ)義標(biāo)簽的行為模式的關(guān)系強(qiáng)度計(jì)算公式與基于語(yǔ)義位置的關(guān)系強(qiáng)度計(jì)算公式相似，見(jià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)系強(qiáng)度大于或小于用戶與好友B的關(guān)系強(qiáng)度，因此實(shí)際計(jì)算結(jié)果為用戶與其全部好友按關(guān)系強(qiáng)度降序排列得到的好友序列。對(duì)于用戶ui，我們對(duì)其全部好友Fi中的每一個(gè)朋友uk使用Ent_DTW(ui,uk)計(jì)算用戶ui和

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

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

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

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

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

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

36、量公式見(jiàn)公式4，其中fi為用戶ui的全部好友的個(gè)數(shù)，ki為Vi相對(duì)于Gi的逆序?qū)?shù)。對(duì)每個(gè)用戶可計(jì)算得到一個(gè)一致性評(píng)分，在此基礎(chǔ)上，對(duì)所有用戶的一致性評(píng)分取平均值，以此作為模型FRSHV對(duì)朋友關(guān)系強(qiáng)度度量有效程度的度量，見(jiàn)公式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)。為了確定用戶之間的物理距離，首先要確定基站之間的距離，并以此作為用戶之間的物理距離。我們采取如下方法來(lái)定義基站之間的距離，將每天用戶手機(jī)連接過(guò)的基站視為

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

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

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

40、義標(biāo)簽序列視為句子，每個(gè)用戶所有語(yǔ)義標(biāo)簽序列視為文檔，使用所有用戶的全部文檔對(duì)LDA模型進(jìn)行訓(xùn)練，其實(shí)驗(yàn)過(guò)程與上面的基于語(yǔ)義位置的實(shí)驗(yàn)過(guò)程一樣，對(duì)應(yīng)2.2節(jié)的Si并計(jì)算一致性評(píng)分。圖5展示了在主題個(gè)數(shù)取不同值時(shí)所對(duì)應(yīng)的一致性評(píng)分結(jié)果。圖 5主題個(gè)數(shù)和對(duì)應(yīng)一致性評(píng)分的實(shí)驗(yàn)結(jié)果Figure 5 The influence of topic numbers to consistency語(yǔ)義標(biāo)簽有實(shí)際含義，以主題個(gè)數(shù)75為例，通過(guò)觀察LDA模型學(xué)習(xí)到的主題，發(fā)現(xiàn)該模型學(xué)習(xí)得到了3個(gè)主題，如表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 對(duì)計(jì)算結(jié)果進(jìn)行投票上面的實(shí)驗(yàn)分別描述了層級(jí)模型FRSHV每一層的實(shí)驗(yàn)結(jié)果，在此基礎(chǔ)上，我們使用前面描述的投票規(guī)則對(duì)三層

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

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