一種社會(huì)網(wǎng)絡(luò)用戶身份特征識(shí)別方法

胡開先梁 英許洪波畢曉迪左 遙

1(中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所) 北京 100190)2(中國(guó)科學(xué)院大學(xué) 北京 100049)(kaixian.hu@gmail.com)

?

一種社會(huì)網(wǎng)絡(luò)用戶身份特征識(shí)別方法

胡開先1,2梁 英1許洪波1畢曉迪1,2左 遙1,2

1(中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所) 北京 100190)2(中國(guó)科學(xué)院大學(xué) 北京 100049)(kaixian.hu@gmail.com)

社會(huì)網(wǎng)絡(luò)是現(xiàn)代信息社會(huì)重要的組成部分.社會(huì)網(wǎng)絡(luò)用戶身份不透明、不可見的特性帶來一系列社會(huì)安全問題.提出了一種社會(huì)網(wǎng)絡(luò)身份特征識(shí)別方法，分別利用基于位置的社會(huì)網(wǎng)絡(luò)和社交關(guān)系進(jìn)行社會(huì)網(wǎng)絡(luò)用戶的身份特征識(shí)別，融合2種識(shí)別結(jié)果推測(cè)社會(huì)網(wǎng)絡(luò)用戶真實(shí)身份.提出了一種基于位置的社會(huì)網(wǎng)絡(luò)用戶身份識(shí)別方法，通過計(jì)算中文分詞和二元組分詞的基本匹配權(quán)重和完全匹配權(quán)重得到近似度權(quán)重，并用它衡量實(shí)體為用戶所屬實(shí)體的可能性；通過實(shí)體名稱聚合算法，對(duì)近似度權(quán)重計(jì)算結(jié)果進(jìn)行優(yōu)化.根據(jù)好友之間傾向于擁有相似的身份特征和相同的興趣愛好的觀察，提出了一種基于社交關(guān)系的多數(shù)投票的身份識(shí)別方法，對(duì)社交關(guān)系中的用戶身份特征進(jìn)行統(tǒng)計(jì)，推測(cè)當(dāng)前用戶的地址信息、實(shí)體信息和用戶興趣.基于微博數(shù)據(jù)，進(jìn)行了樣本數(shù)為1 000名用戶和10 000名用戶的2組實(shí)驗(yàn)，涵蓋了超過250萬條社交關(guān)系.實(shí)驗(yàn)結(jié)果表明，提出的虛實(shí)映射方法有很高的準(zhǔn)確率和覆蓋率，與現(xiàn)有方法相比，該方法著眼于推測(cè)個(gè)人用戶細(xì)粒度的身份特征，具有較高的實(shí)際應(yīng)用價(jià)值.

身份識(shí)別；用戶身份特征；基于位置的社會(huì)網(wǎng)絡(luò)；社交關(guān)系；去匿名化

社會(huì)網(wǎng)絡(luò)在人們生活中扮演著重要的角色，微博、微信、人人網(wǎng)等社會(huì)網(wǎng)絡(luò)已經(jīng)成為人們獲取信息、展示自我和營(yíng)銷推廣的重要途徑.由于社會(huì)網(wǎng)絡(luò)的匿名性，人們可以方便地以虛擬身份自由發(fā)表觀點(diǎn)和意見，每個(gè)人都是信息的生產(chǎn)者和消費(fèi)者.信息的快速發(fā)布和傳播，使社會(huì)網(wǎng)絡(luò)成為一把雙刃劍，它既是應(yīng)對(duì)突發(fā)事件的利器，也是謠言傳播的溫床.例如，新浪微博博主“秦火火”虛構(gòu)的動(dòng)車事故等謠言、微博博主“染香”捏造的“名人被去世”等謠言，這些造謠事件，嚴(yán)重?cái)_亂網(wǎng)絡(luò)秩序、侵害他人名譽(yù)、敗壞社會(huì)風(fēng)氣、危害社會(huì)安全.社會(huì)網(wǎng)絡(luò)的虛擬性和匿名性使之不易追蹤網(wǎng)絡(luò)虛假消息的發(fā)布者、不易定位危害國(guó)家治安言論的發(fā)布者、不易在網(wǎng)絡(luò)中追查違法犯罪行為等.因此，開展識(shí)別用戶社會(huì)網(wǎng)絡(luò)虛擬ID對(duì)應(yīng)的真實(shí)身份的研究，對(duì)于維護(hù)網(wǎng)絡(luò)治安具有積極的社會(huì)意義.

目前，針對(duì)社會(huì)網(wǎng)絡(luò)中用戶身份識(shí)別的研究主要是通過社會(huì)網(wǎng)絡(luò)用戶公開的信息推測(cè)用戶群體的信息或傾向.通過挖掘用戶特征推測(cè)個(gè)體用戶所屬群體，將用戶按興趣愛好分類，可以為用戶提供個(gè)性化的產(chǎn)品營(yíng)銷和廣告投遞等服務(wù)；將用戶按社交關(guān)系分類，可以應(yīng)用于用戶群推薦和用戶群檢測(cè)等服務(wù).通過挖掘用戶地理位置，可以推測(cè)用戶頻繁出現(xiàn)的地區(qū)和事件發(fā)生體.然而，上述方法主要是挖掘用戶的特征屬性對(duì)用戶群體進(jìn)行分類，而不是面向用戶個(gè)體的識(shí)別.

本文提出了一種基于位置和社交關(guān)系的社會(huì)網(wǎng)絡(luò)身份特征識(shí)別方法.通過用戶在社會(huì)網(wǎng)絡(luò)上發(fā)布的帶位置信息的博文，挖掘分析用戶當(dāng)前所屬的學(xué)校和工作單位；同時(shí)利用用戶自身及其社交圈的信息，挖掘分析該用戶的地址信息、學(xué)校、工作單位和興趣；最后融合上述2步結(jié)果對(duì)用戶的真實(shí)身份做出推斷，給出社會(huì)網(wǎng)絡(luò)用戶身份識(shí)別的方法.

1 相關(guān)工作

近年來，對(duì)社會(huì)網(wǎng)絡(luò)的數(shù)據(jù)挖掘和分析受到了學(xué)術(shù)界、工業(yè)界的廣泛關(guān)注，代表性研究包括話題事件分析、情感分析、社交關(guān)系分析、用戶信息檢索推薦等[1].其中，社會(huì)網(wǎng)絡(luò)用戶信息挖掘的相關(guān)研究主要是針對(duì)社會(huì)網(wǎng)絡(luò)用戶的興趣、位置和社交關(guān)系等進(jìn)行分析，推測(cè)個(gè)體用戶所屬群體.由于不同的年齡、性別、教育背景、地理位置和觀點(diǎn)的人群在使用社會(huì)網(wǎng)絡(luò)時(shí)的差異性，通過分析個(gè)體用戶特征、言語行為，對(duì)用戶進(jìn)行群體分類和個(gè)體定位，一方面可以進(jìn)行個(gè)性化服務(wù)、產(chǎn)品營(yíng)銷和廣告投遞等商業(yè)活動(dòng)，另一方面也可以進(jìn)行具有相同興趣愛好、主觀傾向、觀點(diǎn)言論的群體推薦或檢測(cè).

挖掘社會(huì)網(wǎng)絡(luò)用戶興趣一般是利用用戶的歷史地理位置信息或者社交關(guān)系將用戶按照興趣愛好分類，并據(jù)此向用戶作推薦，推薦內(nèi)容包括地理位置、產(chǎn)品、好友等.在根據(jù)興趣推薦地理位置的研究中[2-4],Bao等人[2]研發(fā)了一個(gè)基于位置的興趣認(rèn)知推薦方法，利用用戶的歷史地理位置信息和某地理位置的用戶評(píng)價(jià)，在線為擁有相同興趣愛好的社會(huì)網(wǎng)絡(luò)用戶推薦他們感興趣的地理位置.在根據(jù)興趣推薦興趣點(diǎn)的研究中[5-6]，Wei等人[5]提出了一種基于位置的興趣點(diǎn)標(biāo)識(shí)方法，通過提取訪問興趣點(diǎn)的用戶團(tuán)體的特征描述用戶個(gè)體興趣點(diǎn)的特征，將獲得標(biāo)識(shí)的興趣點(diǎn)推薦給有相同興趣的用戶.在根據(jù)簽到信息推測(cè)用戶傾向的研究中[7-8]，李敏等人[7]通過分析用戶簽到信息和用戶對(duì)簽到位置的評(píng)論，推測(cè)用戶的主觀傾向性，使社會(huì)網(wǎng)絡(luò)能更好地為不同類別的用戶作個(gè)性化推薦.除上述研究方向外，還有通過某用戶社交圈推測(cè)該用戶興趣的研究[9-10]，Xu等人[9]通過某用戶的社交關(guān)系中興趣屬性公開的用戶，利用貝葉斯分類方法推測(cè)該用戶的興趣.

社會(huì)網(wǎng)絡(luò)用戶社交關(guān)系挖掘利用用戶的社交關(guān)系、屬性或歷史地理位置檢測(cè)不同用戶之間的相似性，并在此基礎(chǔ)上向用戶推薦好友.一類是通過用戶行為模式挖掘[11]社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行好友推薦[12-13]，Crandall等人[12]發(fā)現(xiàn)經(jīng)常在相同時(shí)間出現(xiàn)在相同的地理位置上的用戶之間有較強(qiáng)的社交聯(lián)系，并利用此結(jié)論挖掘用戶的社交結(jié)構(gòu)向用戶推薦好友；另一類是通過挖掘社交關(guān)系推薦好友[14-16],王玙等人[14]認(rèn)為擁有相似社交圈的用戶更易成為朋友，并在此基礎(chǔ)上提出了社交圈檢測(cè)算法，定義用戶間的社交圈相似性，根據(jù)相似程度劃分好友圈.另外，一個(gè)用戶通常會(huì)在多個(gè)社會(huì)網(wǎng)絡(luò)注冊(cè)不同賬號(hào)，賬號(hào)對(duì)齊研究通過分析用戶在不同社會(huì)網(wǎng)絡(luò)中的信息，利用社交關(guān)系圖、好友關(guān)系等識(shí)別出同一用戶在不同社交平臺(tái)的身份.如Bayati等人[17]將特征轉(zhuǎn)化為二部圖的一組結(jié)點(diǎn)，待對(duì)齊的所有實(shí)例為另一組結(jié)點(diǎn)，然后根據(jù)結(jié)點(diǎn)的度、排名、權(quán)重、聚類相關(guān)度來對(duì)齊；Korula和Lattanzi[18]利用朋友關(guān)系的網(wǎng)絡(luò)圖將跨社會(huì)網(wǎng)絡(luò)的賬號(hào)映射進(jìn)行了數(shù)學(xué)建模.

社會(huì)網(wǎng)絡(luò)用戶地理位置推測(cè)主要通過某用戶社交圈的地理位置信息來推測(cè)該用戶所在的地理位置[19-21].Backstrom等人[19]利用Facebook上用戶的好友關(guān)系來推測(cè)當(dāng)前用戶的地理位置，該文得到的結(jié)論是：當(dāng)用戶好友關(guān)系中有5個(gè)以上可定位用戶時(shí)能有效利用社交關(guān)系推測(cè)其地理位置，否則應(yīng)當(dāng)使用IP地址推測(cè)其地理位置.Clodoveu,Diogo等人[21]通過Twitter用戶粉絲中可定位的用戶，運(yùn)用多數(shù)投票方法來推斷其他用戶發(fā)布博文的地理位置.

社會(huì)網(wǎng)絡(luò)去匿名化方法研究如何去除匿名化偽裝的影響，根據(jù)已知的用戶信息推測(cè)其敏感信息和傾向.在針對(duì)圖結(jié)構(gòu)數(shù)據(jù)的去匿名化研究中[22-23]，Narayanan等人[22]利用同一人在不同社會(huì)網(wǎng)絡(luò)中社交關(guān)系具有一定相關(guān)性進(jìn)行多賬號(hào)身份識(shí)別，從已知的少量信息出發(fā)，尋找相似結(jié)構(gòu)完成種子節(jié)點(diǎn)映射，通過擴(kuò)散不斷找出新節(jié)點(diǎn)的映射關(guān)系，成功匹配了13同時(shí)使用Twitter和Flicker的用戶.基于文本數(shù)據(jù)的去匿名化研究中，Narayanan等人[24]抽取文本數(shù)據(jù)特征建立高維文本特征向量，用機(jī)器學(xué)習(xí)分類器識(shí)別文本作者或其博客.

除上述研究成果外，也有一些產(chǎn)品化的用戶特征分析工具.iResearch公司提供的網(wǎng)民用戶行為分析工具TargetPlus通過分析網(wǎng)絡(luò)用戶群網(wǎng)絡(luò)行為范式與特點(diǎn)，幫助廣告主了解不同類別的目標(biāo)用戶需求，優(yōu)化網(wǎng)絡(luò)營(yíng)銷策略.Mixpanel公司推出的用戶特征分析工具M(jìn)ixpanel[25]可以分析網(wǎng)站訪客的性別、國(guó)家等信息，對(duì)用戶分類，把相關(guān)信息精確地送達(dá)某一用戶群體.Webtrends公司的Reinvigorate工具和Chartbeat公司的Chartbeat工具可以實(shí)時(shí)監(jiān)測(cè)網(wǎng)站的用戶行為.除此之外，大型電商網(wǎng)站如Amazon、淘寶、eBay、京東等通過分析網(wǎng)站用戶數(shù)據(jù)推測(cè)用戶生活特征和購物興趣或傾向，以此向用戶提供個(gè)性化購物體驗(yàn)和更精確的產(chǎn)品推薦.

綜上所述，關(guān)于社會(huì)網(wǎng)絡(luò)用戶特征屬性挖掘的研究已被廣泛關(guān)注，當(dāng)前研究主要著眼于挖掘用戶群體的信息和傾向，并沒有對(duì)個(gè)體用戶的特征屬性作深入分析；在分析用戶群體特征屬性時(shí)粒度不夠細(xì)化，難以推測(cè)個(gè)體用戶的真實(shí)身份.相比上述研究成果，本文主要貢獻(xiàn)為:

1) 利用用戶的地理位置信息和博文推測(cè)用戶的學(xué)校和工作單位，將地理位置的粒度細(xì)化到具體的某個(gè)實(shí)體；

2) 利用某用戶社交關(guān)系群體特征，推測(cè)該用戶的地址、學(xué)校和工作單位信息；

3) 融合上述2步結(jié)果，對(duì)用戶身份特征做出綜合性推測(cè)，進(jìn)一步縮小用戶真實(shí)身份范圍，建立起社會(huì)網(wǎng)絡(luò)用戶虛擬身份和真實(shí)身份之間的虛實(shí)映射.

2 用戶身份特征識(shí)別方法

2.1 方法概述

為了從社會(huì)網(wǎng)絡(luò)用戶的虛擬身份信息推測(cè)其真實(shí)身份，需要不斷縮小用戶真實(shí)身份的范圍.地址信息、學(xué)校和工作單位對(duì)確定用戶身份具有重要作用，為方便分析，本文將其定義為用戶身份特征，示例如圖1所示.

Fig. 1 Sample of user identity feature.圖1 用戶身份特征示例

定義1. 用戶身份特征(UID).該特征特指地址信息、學(xué)校、工作單位和興趣.可用一個(gè)四元組UID=L,E,W,I描述.其中，L代表該用戶地址信息集合，可表示為：L={(li,Pli)|i=1,2,…,nL} ，li代表省、市、區(qū)、街道和門牌號(hào)等地址信息，Pli代表用戶地址為li的概率；E代表學(xué)校集合，可表示為：E={(ej,Pej)|j=1,2,…,nE}，ej代表用戶畢業(yè)或就讀的學(xué)校，Pej代表用戶畢業(yè)或就讀學(xué)校為ej的概率；W代表工作單位集合，可表示為：W={(wk,Pwk)|k=1,2,…,nW}，wk代表用戶曾經(jīng)工作或在職的工作單位，Pwk為用戶在職或曾經(jīng)工作的單位為wk的概率；I代表用戶興趣集合，可表示為：I={(ik,Pik)|k=1,2,…,nI}，ik代表用戶的興趣，Pik代表用戶興趣為ik的概率.

Fig. 2 Flow chart of user identity feature recognition method.圖2 用戶身份特征識(shí)別方法總體流程圖

定義2. 實(shí)體指學(xué)校和工作單位的集合.該集合是E和W的并集，可表示為：S={SP|SP∈E∪W,P=1,2,…,nE+nW}.

本文從社會(huì)網(wǎng)絡(luò)用戶(簡(jiǎn)稱用戶)的地理位置信息和社交關(guān)系出發(fā)，推測(cè)用戶的地址信息、學(xué)校、工作單位和興趣，以縮小用戶真實(shí)身份的范圍.整體的流程如圖2所示，主要包括數(shù)據(jù)獲取、數(shù)據(jù)分析、結(jié)果融合和結(jié)果推送.

1) 數(shù)據(jù)獲取.通過給定的微博用戶唯一標(biāo)識(shí)(昵稱)獲取該用戶的個(gè)人信息(特征屬性)、粉絲列表、博文內(nèi)容和簽到信息.

2) 數(shù)據(jù)分析.包括2種分析方法：①地理位置方法.通過用戶開啟GPS服務(wù)后博文數(shù)據(jù)帶有的經(jīng)緯度信息得到用戶的頻繁地理位置，進(jìn)而得到該位置周邊的實(shí)體信息，與用戶簽到的實(shí)體信息合并得到候選實(shí)體列表；實(shí)體列表中每個(gè)實(shí)體是用戶可能所屬的學(xué)校和工作單位，用近似度權(quán)重衡量可能性大?。煌ㄟ^實(shí)體名稱聚合算法合并實(shí)體名稱、優(yōu)化近似度權(quán)重計(jì)算結(jié)果，推測(cè)用戶的地址信息、學(xué)校、工作單位和興趣.②社交關(guān)系多數(shù)投票方法.通過用戶的粉絲列表得到用戶的互粉好友，提取用戶互粉好友的用戶身份特征，并對(duì)得到的用戶身份特征集合L,E,W,I進(jìn)行多數(shù)投票，選取各集合中滿足條件且計(jì)數(shù)靠前的各項(xiàng)作為當(dāng)前用戶身份特征.

3) 結(jié)果融合.地理位置方法覆蓋開啟GPS服務(wù)的用戶，社交關(guān)系多數(shù)投票方法覆蓋有健壯社交關(guān)系的用戶(通過粉絲列表中互粉好友數(shù)目體現(xiàn))，通過對(duì)2種方法結(jié)果的融合，能夠提高用戶身份識(shí)別的覆蓋率.

4) 結(jié)果推送.在結(jié)果融合后，整理匯總所得地址信息、學(xué)校、工作單位和興趣，推送給最終用戶.

在2.2節(jié)和2.3節(jié)中，將重點(diǎn)介紹基于位置的身份識(shí)別方法和基于社交關(guān)系的身份識(shí)別方法.

2.2 基于位置的社會(huì)網(wǎng)絡(luò)用戶身份識(shí)別方法

基于位置的社會(huì)網(wǎng)絡(luò)用戶身份識(shí)別方法根據(jù)社會(huì)網(wǎng)絡(luò)用戶的地理位置信息和博文內(nèi)容來推測(cè)該用戶所屬的學(xué)校或工作單位.與社會(huì)網(wǎng)絡(luò)用戶相關(guān)的地理位置信息主要包括2種：1)用戶主動(dòng)分享的數(shù)據(jù)，如簽到信息；2)開啟GPS服務(wù)的代價(jià)，例如博文帶有的地理位置坐標(biāo).本方法同時(shí)用到上述2類地理位置信息，再利用博文內(nèi)容來匹配分詞后的實(shí)體名稱，本方法的主要步驟如下：

步驟1. 從用戶發(fā)布的博文中提取地理位置信息；

步驟2. 對(duì)得到的地理位置信息作頻率統(tǒng)計(jì)，獲得前N個(gè)頻繁的地理位置；

步驟3. 通過新浪微博API獲得這N個(gè)頻繁地理位置周邊的實(shí)體列表；

步驟4. 將上述列表和用戶的簽到信息合并，得到候選實(shí)體列表；

步驟5. 分析候選實(shí)體與用戶博文匹配度，計(jì)算其近似度權(quán)重；

步驟6. 使用實(shí)體名稱聚合算法聚合所有候選實(shí)體信息并去除冗余，優(yōu)化近似度權(quán)重計(jì)算結(jié)果.

最終，根據(jù)新的近似度權(quán)重對(duì)實(shí)體排序，得到降序的候選實(shí)體列表.其中，最為關(guān)鍵的步驟是實(shí)體名稱近似度權(quán)重計(jì)算和實(shí)體名稱聚合，下面我們分別對(duì)這2個(gè)步驟進(jìn)行專門介紹.

2.2.1 近似度權(quán)重計(jì)算

用戶的博文內(nèi)容中包含和用戶直接相關(guān)的信息，如地址信息、學(xué)校、工作單位等.因此，我們可以通過將實(shí)體名稱匹配用戶博文的方法計(jì)算實(shí)體列表中各實(shí)體為用戶所屬實(shí)體的可能性.考慮到實(shí)體全稱在用戶博文中被提到的可能性低，為了提高命中率，我們先對(duì)實(shí)體列表中各實(shí)體名稱進(jìn)行分詞處理(二元組分詞和中文分詞)，并在分詞過程中通過別名詞庫將分詞得到的實(shí)體簡(jiǎn)稱、別名加入到分詞結(jié)果中以防止實(shí)體名稱漏配用戶博文中用戶習(xí)慣用語的情況.匹配的結(jié)果由近似度權(quán)重衡量，近似度權(quán)重越高，對(duì)應(yīng)實(shí)體即為用戶所屬實(shí)體的可能性越大.近似度權(quán)重的大小和匹配內(nèi)容的長(zhǎng)度及匹配次數(shù)成正比，匹配內(nèi)容的長(zhǎng)度越大、次數(shù)越多,近似度權(quán)重越大.

實(shí)體名稱對(duì)應(yīng)的分詞結(jié)果與博文內(nèi)容進(jìn)行匹配分為完全匹配和基本匹配.完全匹配表示實(shí)體名稱的全稱在博文內(nèi)容中得到匹配(博文內(nèi)容包含實(shí)體名稱的全稱“北京大學(xué)”)；而基本匹配表示實(shí)體名稱的分詞結(jié)果中的分詞(不包括實(shí)體名稱的全稱)在博文內(nèi)容中得到匹配(博文內(nèi)容只包含“北京”、“大學(xué)”等詞組).完全匹配的實(shí)體近似度權(quán)重高；基本匹配的實(shí)體近似度權(quán)重低.基于以上分析，設(shè)計(jì)了實(shí)體名稱s完全匹配的近似度權(quán)重Weightf(s)和實(shí)體名稱s的分詞結(jié)果si基本匹配的近似度權(quán)重Weightb(s)為

(1)

(2)

式(1)中，s代表輸入實(shí)體名稱，Weightf(s)代表輸入實(shí)體名稱的近似度權(quán)重，Len(s)代表輸入實(shí)體名稱的長(zhǎng)度；式(2)中，si代表實(shí)體名稱s的一個(gè)分詞結(jié)果，Weightb(s)代表輸入實(shí)體名稱分詞的近似度權(quán)重，n代表實(shí)體名稱s分詞的總數(shù)，msi代表si與博文內(nèi)容的匹配次數(shù).

由式(1)和式(2)得到實(shí)體名稱s的近似度權(quán)重Weight(s)為

(3)

式(3)中，α和β代表可調(diào)參數(shù).其中，α=qm，代表可調(diào)乘數(shù)因子，取值范圍為大于1的實(shí)數(shù)；m代表實(shí)體名稱s與博文內(nèi)容的匹配次數(shù)，取值為正整數(shù)；qm代表權(quán)重增長(zhǎng)的速率.β的取值范圍為大于等于0的實(shí)數(shù).

計(jì)算得到候選實(shí)體列表各實(shí)體名稱的近似度權(quán)重后，對(duì)實(shí)體列表按近似度權(quán)重降序排列，得到用戶可能所屬的實(shí)體名稱列表序列.

2.2.2 實(shí)體名稱聚合算法

對(duì)于具有相同近似度權(quán)重的實(shí)體，需要再次計(jì)算近似度權(quán)重并優(yōu)化排序結(jié)果.在實(shí)際項(xiàng)目中發(fā)現(xiàn)，通過地理位置信息和博文內(nèi)容得到的實(shí)體名稱的粒度可能會(huì)精細(xì)到單位內(nèi)的某個(gè)具體地點(diǎn)，比如“北京大學(xué)食堂”和“北京大學(xué)教學(xué)樓”，本文識(shí)別的是“北京大學(xué)”這個(gè)單位的名稱.因此，提出了一個(gè)實(shí)體名稱聚合算法，通過合并具有相同前綴的實(shí)體名稱，提取表示單位名稱的實(shí)體名稱，濾掉細(xì)粒度的實(shí)體名稱；計(jì)算合并近似度權(quán)重，優(yōu)化實(shí)體名稱排序結(jié)果.

實(shí)體名稱聚合算法用到了Trie樹，又稱字典樹或前綴樹，是一個(gè)利用字符串的公共前綴來描述字符串序列的多叉樹.本文利用Trie樹描述從用戶地理位置信息獲得的實(shí)體序列，并滿足3點(diǎn)性質(zhì)：1)根節(jié)點(diǎn)不包括字符，其他每個(gè)節(jié)點(diǎn)只包括一個(gè)漢字；2)從根節(jié)點(diǎn)到某一個(gè)葉子節(jié)點(diǎn)，路徑上經(jīng)過的漢字連接起來，為一個(gè)實(shí)體；3)每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符串不同.

首先創(chuàng)建前綴樹.在生成實(shí)體序列前綴樹的過程中每個(gè)節(jié)點(diǎn)要記錄漢字出現(xiàn)的頻數(shù)，以及節(jié)點(diǎn)的深度.以具有相同近似度權(quán)重(均為1)的實(shí)體序列“北京大學(xué)食堂”、“北京大學(xué)教學(xué)樓”、“清華大學(xué)圖書館”和“中科院計(jì)算所”為例，圖3展示了該實(shí)體序列對(duì)應(yīng)前綴樹建樹過程，其中節(jié)點(diǎn)右側(cè)標(biāo)注的數(shù)字表示節(jié)點(diǎn)出現(xiàn)的頻數(shù)，圖3最左側(cè)標(biāo)注的數(shù)字表示節(jié)點(diǎn)的深度.

Fig. 3 Building process of trie tree.圖3 前綴樹的建樹過程

前綴樹建立后，合并有最大共同前綴的實(shí)體名稱并計(jì)算對(duì)應(yīng)的近似度權(quán)重.求解最大共同前綴方法的步驟如下：1)尋找出現(xiàn)頻數(shù)最大的節(jié)點(diǎn)；2)如果出現(xiàn)頻數(shù)相同，尋找節(jié)點(diǎn)深度最大的節(jié)點(diǎn)；3)找到上述節(jié)點(diǎn)后，將該節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上經(jīng)過的漢字連接起來即為最大共同前綴；4)如果所有節(jié)點(diǎn)出現(xiàn)頻數(shù)都為1，當(dāng)前實(shí)體序列沒有最大共同前綴；5)如果出現(xiàn)頻數(shù)最大的節(jié)點(diǎn)深度不滿足條件，即最大共同前綴不滿足最短長(zhǎng)度要求或者并不包含于前綴詞庫中，當(dāng)前序列沒有最大共同前綴.在圖3的示例中，“北京大學(xué)”即為最大共同前綴.

得到最大共同前綴后，聚合實(shí)體名稱，其步驟如下：1)合并擁有最大共同前綴的實(shí)體名稱為最大共同前綴；2)計(jì)算1)中被合并實(shí)體名稱近似度權(quán)重之和作為最大共同前綴的近似度權(quán)重；3)根據(jù)新的近似度權(quán)重計(jì)算結(jié)果重新對(duì)候選實(shí)體列表排序.在圖3的示例中，“北京大學(xué)食堂”和“北京大學(xué)教學(xué)樓”合并為“北京大學(xué)”，并計(jì)算其近似度權(quán)重為2.最終得到的實(shí)體序列為“北京大學(xué)”、“清華大學(xué)圖書館”和“中科院計(jì)算所”，相應(yīng)的近似度權(quán)重分別為2，1，1.

在聚合當(dāng)前近似度權(quán)重對(duì)應(yīng)的實(shí)體名稱后，迭代聚合其他近似度權(quán)重對(duì)應(yīng)的實(shí)體名稱.最后，根據(jù)別名詞庫聚合不同近似度權(quán)重間實(shí)體名稱相同或互為別名的實(shí)體名稱，并合并其近似度權(quán)重.接下來根據(jù)近似度權(quán)重計(jì)算對(duì)應(yīng)實(shí)體為當(dāng)前用戶所在實(shí)體的概率PWeight(si)為

(4)

算法1. 實(shí)體名稱聚合算法.

輸入:Sall，P，N;

輸出:MSall.

① while(Sall≠?) /*遍歷Sall*/

②new_tree=createTrie();

/*初始化前綴樹*/

③ while(SWeighti∈Sall且SWeighti≠?)

/*生成前綴樹*/

④ for eachSP∈SWeighti

⑤insertTrie(SP); /*將SP逐字插入前綴樹中*/

⑥ end for

⑦ end while

⑧prefix=new_tree.findMaxPrefix();

/*遍歷前綴樹獲得最大共同前綴*/

⑨ ifLen(prefix)≥Lengthorprefix∈P

then /*最大共同前綴長(zhǎng)度滿足要求*/

⑩ while(SPi∈SWeighti且prefix?SPi)

/*求或包含于前綴詞庫*/

/*計(jì)算最大共同前綴的近似度權(quán)重*/

刪除有最大共同前綴的實(shí)體*/

前綴到實(shí)體列表集合*/

/*合并兩者近似度權(quán)重*/

重新對(duì)Sall排序*/

實(shí)體名稱聚合完成后就得到了最終的實(shí)體排序結(jié)果.

2.3 基于社交關(guān)系的多數(shù)投票身份識(shí)別方法

2.3.1 方法描述

社會(huì)網(wǎng)絡(luò)的發(fā)展把人們的社交圈從現(xiàn)實(shí)生活中映射到網(wǎng)絡(luò)世界，可通過社會(huì)網(wǎng)絡(luò)上互為好友或者互為粉絲等社交關(guān)系體現(xiàn).屬于同一個(gè)社交圈的人擁有更多的共同點(diǎn)，例如居住在較近的地理區(qū)域、就讀或畢業(yè)于相同學(xué)校、在相同的工作單位等.本方法基于社會(huì)網(wǎng)絡(luò)用戶的社交關(guān)系鄰居節(jié)點(diǎn)的屬性信息，利用互粉用戶地址信息條目和實(shí)體信息條目，通過多數(shù)投票的方法推測(cè)當(dāng)前用戶的地址信息、學(xué)校和工作單位.

多數(shù)投票是一種簡(jiǎn)單有效的方法，它利用分類器對(duì)給定的測(cè)試樣本輸出分類類別及各類別的投票結(jié)果.設(shè)當(dāng)前用戶樣本Xu的分類器為C，有m個(gè)類別Tji(j=1,2,3,4;i=1,2,…,nj;nj≤m)，分類器C輸入一個(gè)分類樣本Xu，輸出一個(gè)分類編號(hào)ji，即C(Xu)=ji.每個(gè)類別Tji對(duì)應(yīng)一個(gè)投票計(jì)數(shù)count(Tji)，其中：

count(Tji)=

(5)

其中，xfeature為當(dāng)前用戶待推測(cè)的某個(gè)身份特征的集合，可以取為地址信息L或?qū)W校E或工作單位W或興趣I；xk是xfeature對(duì)應(yīng)的條目；Tji是當(dāng)前用戶所有互粉的身份特征對(duì)應(yīng)的條目，當(dāng)j取不同的值時(shí)，分別代表地址信息L或?qū)W校E或工作單位W或興趣I，如j=1代表地址信息L，Tji可以為北京市海淀區(qū)、北京市中關(guān)村南路80號(hào)等.

(6)

其中，Lv是最低有效投票數(shù).最低有效投票數(shù)限定了地址信息、學(xué)校、工作單位或興趣的計(jì)數(shù)結(jié)果必須超過的數(shù)，如果計(jì)數(shù)結(jié)果小于最低有效投票數(shù)，則結(jié)果無效.

最后，對(duì)j的每一個(gè)取值分別計(jì)算概率Tji為

(7)

對(duì)j的不同取值，按概率結(jié)果降序排序，得到當(dāng)前地址信息地址信息L或?qū)W校E或工作單位W或興趣I的推測(cè)結(jié)果.

2.3.2 參數(shù)選取與結(jié)果判斷

地址信息的最低有效投票數(shù)Lv可以設(shè)為1，因?yàn)槊總€(gè)用戶注冊(cè)信息都有地址信息，有充足的投票數(shù)用來判斷結(jié)果，判斷標(biāo)準(zhǔn)為用戶填寫的地址信息出現(xiàn)在計(jì)算結(jié)果Tj的前3個(gè)條目中就認(rèn)為計(jì)算結(jié)果是準(zhǔn)確的.

學(xué)校工作單位最低有效票數(shù)Lv可通過實(shí)驗(yàn)統(tǒng)計(jì)獲得，實(shí)驗(yàn)結(jié)果如圖4所示：

Fig. 4 The Least effective friends number corresponding to the minimum effective vote count.圖4 各最低有效互粉數(shù)對(duì)應(yīng)的最低有效票數(shù)統(tǒng)計(jì)

由圖4的統(tǒng)計(jì)結(jié)果得到，當(dāng)互粉數(shù)量小于25時(shí)，設(shè)置學(xué)校工作單位最低有效投票數(shù)為2；當(dāng)互粉數(shù)量大于25時(shí)，設(shè)置其最低有效投票數(shù)為4.

用戶興趣的投票結(jié)果通過該用戶的博文內(nèi)容和用戶自己填寫的興趣標(biāo)簽(如果該用戶在信息中填寫了興趣字段)驗(yàn)證其正確性.如果投票結(jié)果和該用戶博文內(nèi)容中出現(xiàn)的高頻詞存在交集或者符合用戶自己填寫的興趣字段，則判定其準(zhǔn)確，反之則判定其不準(zhǔn)確.

2.4 基于概率的結(jié)果融合

(8)

其中，若Lg中的身份特征li在Lr中無對(duì)應(yīng)項(xiàng)，默認(rèn)其概率為0，反之亦如此.計(jì)算方式不變.

為了簡(jiǎn)化表達(dá)方式，我們定義一種新的運(yùn)算符號(hào)⊙表示上述運(yùn)算，則融合結(jié)果為

Lg⊙Lr,Eg⊙Er,Wg⊙Wr,Ig⊙Ir.

(9)

上述規(guī)則中，考慮到地理位置方法獲取的用戶身份特征是近期的、實(shí)時(shí)的，它的時(shí)間屬性比較新；而社交關(guān)系多數(shù)投票方法獲取的用戶身份特征是用戶填寫的，可以包含小學(xué)、中學(xué)等項(xiàng)，有些時(shí)間屬性可能不是最新的.但2種方法得到的結(jié)果都有一定的合理性并可以互補(bǔ)，因此，我們將2個(gè)結(jié)果根據(jù)式(9)計(jì)算平均概率，得到融合后的推測(cè)結(jié)果.

3 實(shí)驗(yàn)與效果評(píng)估

為了準(zhǔn)確評(píng)價(jià)基于位置的方法和基于社交關(guān)系方法的推斷準(zhǔn)確性，我們用新浪微博開放API收集了新浪微博的用戶數(shù)據(jù)，包括用戶信息、用戶簽到信息、用戶博文和用戶的社交關(guān)系.驗(yàn)證基于位置方法的準(zhǔn)確率時(shí)，保留用戶博文內(nèi)容帶有地理位置信息的數(shù)據(jù)；驗(yàn)證基于社交關(guān)系方法的準(zhǔn)確率時(shí)，保留擁有互粉關(guān)系并且互粉數(shù)滿足最低有效互粉數(shù)的用戶數(shù)據(jù).

實(shí)驗(yàn)收集的新浪微博數(shù)據(jù)超過1.2億用戶，我們從中隨機(jī)選擇3組樣本.其中，組1為注冊(cè)用戶，樣本數(shù)為1 000；組2、組3為認(rèn)證用戶，樣本數(shù)分別為1 000和10 000.本文以樣本用戶的互粉列表為基礎(chǔ)，從新浪微博獲得其互粉好友共 2 521 925名用戶信息及其互粉列表.

3.1 數(shù)據(jù)集分析

從新浪微博獲得的2 521 925名用戶中隨機(jī)抽取40 621名用戶用來分析樣本數(shù)據(jù).如圖5所示，縱坐標(biāo)表示用戶數(shù)量的對(duì)數(shù)，橫坐標(biāo)代表統(tǒng)計(jì)量.圖5(a)展示了互粉數(shù)量情況分布；圖5(b)展示了互粉好友的地址信息條目數(shù)的分布情況；圖5(c)展示了互粉好友的學(xué)校工作單位條目數(shù)的分布情況；圖5(d)展示了互粉好友的興趣條目數(shù)的分布情況.圖5(a)和圖5(b)數(shù)據(jù)分布吻合，說明所有的用戶都有地址信息，地址信息的出現(xiàn)率接近100%；從圖5(c)和圖5(d)的數(shù)據(jù)分布可以看出，與圖5(a)和圖5(b)相比，互粉學(xué)校工作單位條目數(shù)和互粉興趣條目數(shù)小于互粉數(shù)和互粉地址信息條目數(shù)，這說明只有部分用戶有學(xué)校工作單位信息和興趣字段.注意到圖5中4幅圖的縱坐標(biāo)刻度是用以10為底的對(duì)數(shù)作為單位，說明滿足條件的用戶數(shù)隨著互粉數(shù)的增加呈指數(shù)下降.

Fig. 5 Data distribution charts.圖5 數(shù)據(jù)分布圖

3.2 實(shí)驗(yàn)與效果評(píng)估

在實(shí)驗(yàn)中，我們使用了第3節(jié)第2段提到的3組樣本用戶作為實(shí)驗(yàn)數(shù)據(jù)，對(duì)實(shí)驗(yàn)效果進(jìn)行驗(yàn)證.我們采用2個(gè)被廣泛使用的指標(biāo)來分析實(shí)驗(yàn)的有效性：準(zhǔn)確率與召回率，考慮到覆蓋率更能體現(xiàn)本文“最低有效互粉數(shù)”的概念，同時(shí)還使用覆蓋率作為實(shí)驗(yàn)效果的衡量指標(biāo).

3.2.1 基于位置的身份識(shí)別方法實(shí)驗(yàn)結(jié)果分析

本方法適用于用戶的博文內(nèi)容中帶有地理位置信息，對(duì)于用戶的互粉關(guān)系并沒有要求.在1 000名認(rèn)證樣本用戶中有地理位置信息的用戶有188名，占18.8%.

在實(shí)驗(yàn)中，我們用2個(gè)指標(biāo)衡量基于位置方法的準(zhǔn)確性，即地址信息推測(cè)的準(zhǔn)確性和學(xué)校工作單位推測(cè)的準(zhǔn)確性.

在地址信息準(zhǔn)確性判斷中，如果有至少1條頻繁地理位置與用戶填寫的地址信息吻合，我們就判定其地址信息推測(cè)是準(zhǔn)確的.

在學(xué)校工作單位準(zhǔn)確性判斷中，我們?cè)O(shè)定了3條判斷標(biāo)準(zhǔn)，如果學(xué)校工作單位推測(cè)滿足下述任何1條，則我們判定其地址信息推測(cè)是準(zhǔn)確的：1)經(jīng)過計(jì)算排序后的候選實(shí)體列表與用戶信息相符；2)候選實(shí)體列表前3名中有完全匹配且實(shí)體名稱滿足一定長(zhǎng)度；3)推測(cè)出的頻繁地理位置信息精確到門牌號(hào).

基于上述判斷標(biāo)準(zhǔn)，我們得到實(shí)驗(yàn)結(jié)果如表1所示.基于位置的身份識(shí)別方法只適用有地理位置信息的用戶，我們選取包含地理位置信息的188個(gè)用戶數(shù)據(jù)做測(cè)試，得到準(zhǔn)確率和召回率，并通過覆蓋率衡量本方法的適用范圍.

Table 1 Experimental Results of Geo-Location Based Identity Recognition Method

從表1中觀察到，地址信息推測(cè)和學(xué)校工作單位推測(cè)覆蓋率都為18.80%，因?yàn)閮烧叩母采w率都取決于開啟GPS服務(wù)的用戶比例.學(xué)校工作單位推測(cè)結(jié)果中，有114例樣本不準(zhǔn)確.其中36.84%的樣本是因地理位置信息過于稀疏(即雖有地理位置信息，但是地理位置信息條目數(shù)不足導(dǎo)致實(shí)體位置推測(cè)不準(zhǔn)確)；39.47%的樣本是因缺少博文信息導(dǎo)致實(shí)體匹配準(zhǔn)確率下降；17.54%的樣本地理位置信息過于稀疏，同時(shí)還缺少博文信息.因此，本方法在用戶有充足地理位置信息和博文信息的時(shí)候最為適用.

3.2.2 基于社交關(guān)系的身份識(shí)別方法實(shí)驗(yàn)結(jié)果分析

基于社交關(guān)系的身份識(shí)別方法中互粉數(shù)的取值對(duì)準(zhǔn)確率、召回率和覆蓋率有一定影響[17].

本文為充分研究互粉數(shù)和實(shí)驗(yàn)結(jié)果之間的關(guān)系，設(shè)置學(xué)校工作單位最低有效互粉數(shù)為0、最低有效投票數(shù)為2作為實(shí)驗(yàn)的基準(zhǔn)情況.實(shí)驗(yàn)中，本文用了2組信息已知的微博認(rèn)證用戶數(shù)據(jù)，樣本數(shù)分別為1 000名用戶和10 000名用戶.實(shí)驗(yàn)結(jié)果如表2所示.注意到表2中實(shí)驗(yàn)只是基準(zhǔn)情況，對(duì)所有用戶都適用，并且都能得到推測(cè)結(jié)果.因此，表2中實(shí)驗(yàn)準(zhǔn)確率和召回率的值相同，實(shí)驗(yàn)覆蓋率均為100%.其中，對(duì)于樣本數(shù)為1 000名用戶的組別，本文使用人工核實(shí)和程序自動(dòng)判斷2種驗(yàn)證方法比較推測(cè)結(jié)果與已知用戶信息是否相符計(jì)算準(zhǔn)確率.表2結(jié)果顯示2種驗(yàn)證方法結(jié)果的誤差不大于3.2%，說明程序自動(dòng)判斷的驗(yàn)證方法可行.

Table 2 Experimental Results of Education and Work Inference Method Based on Social Relationships

從表2中觀察到，學(xué)校工作單位推測(cè)的準(zhǔn)確率低于地址信息推測(cè)的準(zhǔn)確率,這是因?yàn)樘顚憣W(xué)校工作單位信息的用戶少于填寫地址信息的用戶.此外，地址信息推測(cè)準(zhǔn)確率最低為96.10%，學(xué)校工作單位推測(cè)準(zhǔn)確率最低為80.60%，說明在最低有效互粉數(shù)為0、最低有效投票數(shù)為2時(shí)，本方法已經(jīng)有了較高的準(zhǔn)確率.不準(zhǔn)確的情況是因?yàn)橛脩舻纳缃魂P(guān)系不夠健壯，即互粉數(shù)量不足.

考慮到在實(shí)際應(yīng)用中，對(duì)推測(cè)準(zhǔn)確率會(huì)有更高的要求，我們對(duì)不同最低有效互粉數(shù)作了實(shí)驗(yàn)并對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)(見圖6(a)和圖6(b)).從統(tǒng)計(jì)結(jié)果可知：

1) 用戶互粉數(shù)量越多，推測(cè)準(zhǔn)確率越高，覆蓋率越低；

2) 人工核實(shí)和程序自動(dòng)判斷2種驗(yàn)證方法結(jié)果基本相符.

Fig. 6 Precision and coverage of address, education and work inference on 1 000 users with two kinds of verification.圖6 2種驗(yàn)證方法驗(yàn)證1 000名用戶的地址、學(xué)校和工作單位推測(cè)的準(zhǔn)確率和覆蓋率

從圖6(a)可以看到當(dāng)最低有效互粉數(shù)為0時(shí)，地址信息推測(cè)準(zhǔn)確率超過95%，同時(shí)有100%的覆蓋率.從圖6(b)可以看到當(dāng)最低有效互粉數(shù)為30時(shí)，學(xué)校工作單位推測(cè)準(zhǔn)確率超過85%；當(dāng)最低有效互粉數(shù)為70時(shí)，學(xué)校工作單位推測(cè)準(zhǔn)確率達(dá)到88.37%，但是覆蓋率下降到68.80%.結(jié)合上述規(guī)律，在實(shí)際應(yīng)用時(shí)，應(yīng)根據(jù)對(duì)準(zhǔn)確率和覆蓋率的要求選取不同的最低有效互粉數(shù).此外，從圖6中可以看到人工核實(shí)和程序自動(dòng)判斷2種驗(yàn)證方法得到的準(zhǔn)確率結(jié)果誤差不大于3.2%，證明程序自動(dòng)判斷的驗(yàn)證方法是可行的.在此基礎(chǔ)上，本文利用程序自動(dòng)判斷的驗(yàn)證方法計(jì)算樣本數(shù)為10 000名用戶的組別的準(zhǔn)確率和覆蓋率，結(jié)果如圖7所示:

Fig. 7 Inference precision and coverage on 10 000 users verified by program.圖7 程序驗(yàn)證10 000名用戶的推測(cè)準(zhǔn)確率和覆蓋率

從圖7可以看到，隨著最低有效互粉數(shù)的增加，程序驗(yàn)證的推測(cè)準(zhǔn)確率上升、覆蓋率下降.其中當(dāng)最低有效互粉數(shù)為0時(shí)，地址信息推測(cè)準(zhǔn)確率超過95%，學(xué)校工作單位推測(cè)準(zhǔn)確率超過80%，覆蓋率100%；當(dāng)最低有效互粉數(shù)為30時(shí)，學(xué)校工作單位推測(cè)準(zhǔn)確率超過85%，覆蓋率87.47%；當(dāng)最低有效互粉數(shù)為90時(shí)，學(xué)校工作單位準(zhǔn)確率超過90%，覆蓋率下降到61.32%.

從圖8可以看到，用程序自動(dòng)驗(yàn)證的方法推測(cè)不同樣本數(shù)對(duì)應(yīng)的地址信息推測(cè)準(zhǔn)確率、學(xué)校工作單位推測(cè)準(zhǔn)確率和覆蓋率非常接近，證明對(duì)于不同的樣本數(shù)，實(shí)驗(yàn)得到的準(zhǔn)確率和覆蓋率是一致的、有效的.

Fig. 8 Inference precision and coverage comparison between 1 000 users and 10 000 users verified by program.圖8 程序驗(yàn)證1 000名用戶和10 000名用戶結(jié)果對(duì)比

在基于社交關(guān)系的身份識(shí)別方法推測(cè)用戶興趣的實(shí)驗(yàn)中，本文同時(shí)利用認(rèn)證用戶的樣本和注冊(cè)樣本.其中，認(rèn)證樣本中，樣本數(shù)1 000的用戶中有興趣投票結(jié)果的用戶為952名，根據(jù)博文內(nèi)容和用戶信息驗(yàn)證正確的用戶為750名；樣本數(shù)為10 000的用戶中有興趣投票結(jié)果的用戶為9 613名，驗(yàn)證正確的用戶為8 050名.注冊(cè)樣本中，有興趣投票的用戶為889名，驗(yàn)證正確的用戶為640名.為充分研究互粉數(shù)和實(shí)驗(yàn)結(jié)果之間的關(guān)系，設(shè)置最低有效互粉數(shù)為0、最低有效投票數(shù)為3.當(dāng)推測(cè)結(jié)果出現(xiàn)在用戶填寫的興趣信息中或者在博文內(nèi)容中出現(xiàn)3次以上則判定該結(jié)果正確.實(shí)驗(yàn)結(jié)果如表3所示:

Table 3 Experimental Results of Interests Inference Using Method Based on Social Relationships

從表3觀察到認(rèn)證用戶中，樣本數(shù)1 000組推測(cè)準(zhǔn)確率為78.78%；樣本數(shù)10 000組推測(cè)準(zhǔn)確率為83.74%;注冊(cè)用戶樣本推測(cè)準(zhǔn)確率為71.99%，相比認(rèn)證用戶有所降低.考慮到注冊(cè)用戶推測(cè)結(jié)果人工驗(yàn)證很困難，本文下面主要采用認(rèn)證用戶數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，并簡(jiǎn)稱為用戶.在實(shí)際應(yīng)用中，對(duì)推測(cè)準(zhǔn)確率會(huì)有更高的要求，我們對(duì)不同最低有效互粉數(shù)作了實(shí)驗(yàn)并對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)，如圖9所示.從統(tǒng)計(jì)結(jié)果可知用戶互粉數(shù)量越多，推測(cè)準(zhǔn)確率越高，覆蓋率越低.

Fig. 9 Precision and coverage of interests inference.圖9 用戶興趣推測(cè)的準(zhǔn)確率和覆蓋率

從圖9可以看到，隨著最低有效互粉數(shù)增加，2組樣本數(shù)據(jù)準(zhǔn)確率和覆蓋率的變化趨勢(shì)基本相同.1 000名用戶推測(cè)準(zhǔn)確率上漲約20個(gè)百分點(diǎn)，10 000名用戶推測(cè)準(zhǔn)確率上漲11個(gè)百分點(diǎn).1 000名用戶推測(cè)結(jié)果中，當(dāng)最低有效互粉數(shù)為20時(shí)，推測(cè)準(zhǔn)確率超過80%，同時(shí)仍有90%以上的覆蓋率；當(dāng)最低有效互粉數(shù)為70時(shí)，推測(cè)準(zhǔn)確率超過90%，但是覆蓋率下降到70%左右.10 000名用戶推測(cè)結(jié)果中，推測(cè)準(zhǔn)確率在最低有效互粉為0時(shí)就達(dá)到將近85%，同時(shí)有超過95%的覆蓋率.這說明本方法具有很好的泛化能力.

為了進(jìn)一步驗(yàn)證本文方法的效果，我們?cè)谏鲜? 000名用戶的樣本數(shù)據(jù)上，將本文興趣推測(cè)方法和TextRank方法[26]、直接博文推測(cè)方法進(jìn)行對(duì)比實(shí)驗(yàn).根據(jù)相同的驗(yàn)證方法得到的結(jié)果如圖10所示:

Fig. 10 Precision comparison of different interests inference methods on 1 000 users.圖10 1 000名用戶興趣推測(cè)準(zhǔn)確率對(duì)比結(jié)果

從圖10看到，本方法推測(cè)準(zhǔn)確率明顯高于直接用博文推測(cè)的準(zhǔn)確率,且本方法的推測(cè)準(zhǔn)確率高于TextRank方法的推測(cè)準(zhǔn)確率.

綜上實(shí)驗(yàn)結(jié)果表明，用戶的社交關(guān)系越健壯，基于社交關(guān)系的推測(cè)準(zhǔn)確率越高.

3.2.3 方法融合效果分析

基于地理位置的方法和基于社交關(guān)系的方法有不同的適用范圍.基于地理位置的方法要求用戶開啟GPS服務(wù)，因此方法覆蓋率較低；而基于社交關(guān)系的方法只要求用戶有互粉，有較高的覆蓋率.因此，我們?cè)诨谏缃魂P(guān)系的方法推測(cè)結(jié)果的基礎(chǔ)上使用基于地理位置的方法提高相同特征屬性的推測(cè)準(zhǔn)確率和召回率.此外，由于基于地理位置的方法不涉及用戶興趣的推測(cè)，故只針對(duì)地址信息、學(xué)校工作單位信息進(jìn)行討論.

(10)

(11)

圖11和圖12是方法融合前后的實(shí)驗(yàn)結(jié)果對(duì)比，地址信息、學(xué)校工作單位推測(cè)的準(zhǔn)確率和召回率比融合前都有了進(jìn)一步的提升.

Fig. 11 Improvements of inference precision on address, education and work.圖11 地址信息、學(xué)校工作單位推測(cè)準(zhǔn)確率的提升

圖11中準(zhǔn)確率隨著最低有效互粉數(shù)的增加而減少，這是因?yàn)榛谏缃魂P(guān)系的方法準(zhǔn)確率高，基于地理位置的方法準(zhǔn)確率低，隨著最低有效互粉數(shù)的增加適用基于社交關(guān)系方法的用戶N1減少，適用基于地理位置方法的用戶N2增加，使得融合后的準(zhǔn)確率趨向于基于地理位置方法的準(zhǔn)確率.注意到圖11中最低有效互粉數(shù)為10時(shí)，準(zhǔn)確率達(dá)到最高點(diǎn).

Fig. 12 Improvements of inference recall on address, education and work.圖12 地址信息、學(xué)校工作單位推測(cè)召回率的提升

綜上所述，基于位置的方法和基于社交關(guān)系的方法融合后，實(shí)驗(yàn)結(jié)果的準(zhǔn)確率和召回率都有提升，同時(shí)可以得到具有高準(zhǔn)確率及較高召回率和覆蓋率的最低有效互粉數(shù).

通過以上實(shí)驗(yàn)與分析可知，本文提出的基于位置的方法適用于有充足地理位置信息和博文內(nèi)容的用戶，挖掘其所屬學(xué)校和工作單位；基于社交關(guān)系的身份特征識(shí)別方法適用于社交關(guān)系強(qiáng)壯、互粉數(shù)量多的用戶，可以應(yīng)用到學(xué)校、工作單位、興趣等身份特征屬性的推測(cè)，且都有較高的準(zhǔn)確率和覆蓋率，并具有較好的泛化能力.2種方法互補(bǔ)結(jié)合，可以更準(zhǔn)確識(shí)別用戶的身份特征.

3.3 案例運(yùn)行結(jié)果

實(shí)驗(yàn)結(jié)尾，我們用引言中提到的制造“名人被去世”謠言的微博博主“染香”和微博粉絲最多的大V博主“姚晨”為例，運(yùn)用本文提出的方法推測(cè)其用戶身份特征.注意到上述兩者并沒有開啟GPS服務(wù)，因此只適用于基于社交關(guān)系的方法，得到結(jié)果如表4、表5所示：

Table 4 Experimental Results of Case “Ranxiang”

Table 5 Experimental Results of Case “Yao Chen”

從表4觀察到，“染香”地址推測(cè)結(jié)果主要為“北京”和“廣州”.因?yàn)闆]有“染香”的真實(shí)身份官方信息，本文只能根據(jù)現(xiàn)有資料對(duì)實(shí)驗(yàn)結(jié)果作推斷.其中，“北京”符合網(wǎng)絡(luò)猜測(cè)的“染香”的地址，如圖13(a)所示；“廣東廣州”符合網(wǎng)友推測(cè)“染香”身份中的地址，如圖13(b)所示.其學(xué)校工作單位推測(cè)結(jié)果中，“清華大學(xué)”等學(xué)校也符合網(wǎng)絡(luò)對(duì)“染香”真實(shí)畢業(yè)院校的猜測(cè)，如圖13(a)所示.其興趣推測(cè)結(jié)果中“互聯(lián)網(wǎng)”、“讀書”和“媒體”符合其自媒體人的身份.

在上述案例中，本方法計(jì)算出的匿名博主“染香”的用戶身份特征與網(wǎng)絡(luò)猜測(cè)相符，實(shí)名博主“姚晨”的用戶身份特征與其真實(shí)身份相符(如圖14所示)，說明本方法有較高的準(zhǔn)確性和實(shí)用性.

Fig. 13 Guesses on Ranxiang’s real identity.圖13 網(wǎng)絡(luò)對(duì)“染香”身份的猜測(cè)

Fig. 14 Yao Chen’s biography on Sina Weibo and Baidu Baike.圖14 新浪微博大V博主“姚晨”資料

4 結(jié)束語

本文提出了一種基于位置和社交關(guān)系的社會(huì)網(wǎng)絡(luò)用戶身份特征識(shí)別方法.其中基于位置的方法和基于社交關(guān)系的方法通過互補(bǔ)的方式有效推測(cè)用戶的地址信息、學(xué)校、工作單位和興趣等用戶身份特征.與當(dāng)前社會(huì)網(wǎng)絡(luò)用戶信息挖掘方法多著眼于用戶群體不同，本文方法針對(duì)個(gè)體用戶挖掘身份特征推測(cè)出更細(xì)粒度的用戶信息，如學(xué)校和工作單位，能更有效地定位用戶.實(shí)驗(yàn)證明本文方法有較高的準(zhǔn)確率和覆蓋率.

下一步，我們將基于社會(huì)網(wǎng)絡(luò)用戶推文及其他身份特征對(duì)社會(huì)網(wǎng)絡(luò)用戶個(gè)體的身份進(jìn)行挖掘，探索更精準(zhǔn)的社會(huì)網(wǎng)絡(luò)用戶身份的識(shí)別方法.

[1]Ding Zhaoyun, Jia Yan, Zhou Bin. Survey of data mining for microblogs[J]. Journal of Computer Research and Development, 2014, 51(4): 691-706 (in Chinese)

(丁兆云, 賈焰, 周斌. 微博數(shù)據(jù)挖掘研究綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(4): 691-706)

[2]Bao J, Zheng Y, Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C] //Proc of the 20th Int Conf on Advances in Geographic Information Systems. New York: ACM, 2012: 199-208

[3]Ye M, Yin P, Lee W C. Location recommendation for location-based social networks[C] //Proc of the 18th SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2010: 458-461

[4]Zheng Y, Zhang L, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C] //Proc of the 18th Int Conf on World Wide Web. New York: ACM, 2009: 791-800

[5]Wei L Y, Yeh M Y, Lin G, et al. Discovering point-of-interest signatures based on group features from geo-social networking data[C] //Proc of the 18th Conf on Technologies and Applications of Artificial Intelligence (TAAI). Piscataway, NJ: IEEE, 2013: 182-187

[6]Liu B, Xiong H. Point-of-interest recommendation in location based social networks with topic and location awareness[C] //Proc of the 13th Conf on Data Mining(SDM). Philadelphia, PA: SIAM, 2013: 396-404

[7]Li Min, Wang Xiaocong, Zhang Jun, et al. Study on check-in and related behaviors of location-based social network users[J]. Computer Science, 2013, 40(10): 72-76 (in Chinese)

(李敏, 王曉聰, 張軍, 等. 基于位置的社交網(wǎng)絡(luò)用戶簽到及相關(guān)行為的研究[J]. 計(jì)算機(jī)科學(xué), 2013, 40(10): 72-76)

[8]Cheng Z, Caverlee J, Lee K, et al. Exploring millions of footprints in location sharing services[C] //Proc of the 5th Int Conf on Weblogs and Social Media (ICWSM). Menlo Park, CA: AAAI, 2011: 81-88

[9]Xu W, Zhou X. Inferring privacy information via social relations[C] //Proc of the 24th IEEE Int Conf on Data Engineering Workshop. Piscataway, NJ: IEEE, 2008: 525-530

[10]He J, Chu W W, Liu Z V. Inferring privacy information from social networks[G] //Intelligence and Security Informatics. Berlin: Springer, 2006: 154-165

[11]González M C, Hidalgo C A, Albert-László B. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-782

[12]Crandall D J, Lars B, Dan C, et al. Inferring social ties from geographic coincidences[J]. Proceedings of the National Academy of Sciences of the United States of America, 2010, 107(52): 22436-22441

[13]Nathan E, Alex S P, David L. Inferring friendship network structure by using mobile phone data[J]. Proceedings of the National Academy of Sciences of the United States of America, 2009, 106(36): 15274-15288

[14]Wang Yu, Gao Lin. Social circle-based algorithm for friend recommendation in online social networks[J]. Chinese Journal of Computers, 2013, 37(4): 801-808 (in Chinese)

(王玙, 高琳. 基于社交圈的在線社交網(wǎng)絡(luò)朋友推薦算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 37(4): 801-808)

[15]Guy I, Ronen I, Wilcox E. Do you know? Recommending people to invite into your social network [C] // Proc of the 14th Int Conf on Intelligent User Interfaces. New York: ACM, 2009: 77-86

[16]Yoshida T. Toward finding hidden communities based on user profile[J]. Journal of Intelligent Information Systems, 2013, 40(2): 189-209

[17]Bayati M, Gerritsen M, Gleich D F, et al. Algorithms for large, sparse network alignment problems[C] //Proc of the 9th IEEE Int Conf on Data Mining. Piscataway, NJ : IEEE, 2009: 705-710

[18]Korula N, Lattanzi S. An efficient reconciliation algorithm for social networks[J]. Proceedings of the VLDB Endowment, 2014, 7(5): 377-388

[19]Backstrom L, Sun E, Marlow C. Find me if you can: Improving geographical prediction with social and spatial proximity[C] //Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 61-70

[20]MaxMind LLC. GeoIP city accuracy for selected countries[OL]. 2010[2015-03-12]. https://www.maxmind.com/zh/home

[21]Clodoveu A, Diogo R, Rocha O, et al. Inferring the location of Twitter messages based on user relationships[J]. Transactions in GIS, 2011, 15(6): 735-751

[22]Narayanan A, Shmatikov V. De-anonymizing social networks[C] //Proc of the 30th Symp on Security and Privacy. Piscataway, NJ: IEEE, 2009: 173-187

[23]Narayanan A, Shmatikov V. Robust de-anonymization of large sparse datasets[C] // Proc of the 29th Symp on Security and Privacy. Piscataway, NJ: IEEE, 2008: 111-125

[24]Narayanan A, Paskov H, Gong N Z, et al. On the feasibility of internet-scale author identification[C] // Proc of the 23rd Symp on Security and Privacy. Piscataway, NJ: IEEE, 2012: 300-314

[25]Mixpanel Inc. Mixpanel[OL]. 2013[2015-03-12]. https://www.mixpanel.com

[26]Mihalcea R, Tarau P. TextRank: Bringing order into text[C] //Proc of the 42nd Conf on Annual Meeting of the Association for Computational Linguistics. New York: ACM, 2004: 404-411

Hu Kaixian, born in 1989. Received his MSc degree in computer software and theory from the Institute of Computing Technology, Chinese Academy of Sciences in 2015. His main research interests include network data and science, big data, etc.

Liang Ying, born in 1962. Associate professor in the Institute of Computing Technology, Chinese Academy of Sciences. Senior member of China Computer Federation. Her main research interests include data mining, big data process, middleware, service computing, etc.

Xu Hongbo, born in 1975. Associate professor in the Institute of Computing Technology, Chinese Academy of Sciences. Member of China Computer Federation. His main research interests include Web search and data mining, text classification, information filtering, etc (hbxu@ict.ac.cn).

Bi Xiaodi, born in 1992. Master candidate. Student member of China Computer Federation. Her main research interests include network data and science, big data, etc (bixiaodi@ict.ac.cn).

Zuo Yao, born in 1991. Received his MS degree in computer software and theory from the Institute of Computing Technology, Chinese Academy of Sciences in 2016. His main research interests include big data and data mining (laike9m@gmail.com).

A Method for Social Network User Identity Feature Recognition

Hu Kaixian1,2, Liang Ying1, Xu Hongbo1, Bi Xiaodi1,2, and Zuo Yao1,2

1(KeyLaboratoryofNetworkDataScienceandTechnology(InstituteofComputingTechnology,ChineseAcademyofSciences),ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)

Social network is an important part of modern information society. The anonymity of social network users brings a series of problems concerning social security. This paper presents a method to recognize social network user identity feature by location-based social network (LBSN) and social relationships, and combine the results of those two to infer social network user true identity. The method of geo-location uses approximation weight which is calculated by computing full match weight and basic match weight based on Chinese segmentation and bi-word segmentation to evaluate the possibility that the entity is where the user studies or works, and the method uses entity name aggregation algorithm to optimize the result of approximation weight calculation. According to the observation that friend relationship between users on social network tends to indicate a certain same identity features or a share of common interests, the method of social relationships uses majority voting scheme to count user’s friends identity features to infer user address, entity information and interests. Based on microblog data, we conduct experiments on two samples which cover 1 000 users and 10 000 users respectively and involve a total of more than 2.5 million users relationships. Results shows that our method has a high rate of precision and recall. Compared with the existing methods, our method focuses on individual user identity feature and is valuable in practice.

identity recognition; user identity features; location-based social network (LBSN); social relationships; de-anonymizing

2015-03-19；

2015-12-22

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB0800403)；國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2014CB340406,2013CB329602);國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2015AA015803);國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61232010);國(guó)家自然科學(xué)基金面上項(xiàng)目(61173064);國(guó)家科技支撐計(jì)劃基金項(xiàng)目(2015BAK20B03)；山東省自主創(chuàng)新及成果轉(zhuǎn)化專項(xiàng)(2014CGZH1103)

梁英(liangy@ict.ac.cn)

TP391；TP393

This work was supported by the National Key Research and Development Program of China (2016YFB0800403), the National Basic Research Program of China (973 Program) (2014CB340406,2013CB329602), the National High Technology Research and Development Program of China (863 Program) (2015AA015803), the Key Program of the National Natural Science Foundation of China (61232010), the General Program of the National Natural Science Foundation of China (61173064), the National Key Technology R&D Program of China (2015BAK20B03), and the Independent Innovation and Achievement Transformation Project of Shandong Province (2014CGZH1103).