0 引言

随着互联网时代的到来，以及社交网络的迅速普及与广泛应用，人们的生活方式发生了深刻的改变。越来越多的人习惯每天通过微信、QQ等社交工具与家人、好友、同事进行即时通信，在微博、朋友圈发布信息，在头条、腾讯上阅读新闻并进行评论。一个人往往在多个社交网络中注册账号，进行不同的社交活动，留下了丰富的用户社交元数据信息。然而，目前由于“单点登录”技术还不够完善，同一个用户在不同社交网络中注册的多个账号之间往往是孤立开来的。如果可以跨网络识别用户，即识别出同一个用户在不同网络中的多个账号，就可以实现数据的融合，最大限度地收集、整合与完善用户的个人信息，从而能够对用户海量社交元数据进行充分挖掘。

跨网络用户识别技术在商业应用、信息检索、网络空间安全等许多领域都具有重大的研究意义与实用价值^[1]。按照用户在社交网络中拥有的三种维度的信息，目前跨网路用户识别技术大多可以分为三类：基于网络结构信息^[2-4]、基于属性信息^[5-10]以及基于行为信息^[11-14]的用户身份识别方法。当用户的属性信息可以被利用时，该方法的准确率高于其他两类。目前基于属性信息的用户身份识别方法主要是判断不同网络中两个账号的档案信息是否匹配，用户档案信息通常包括用户名、地址、兴趣等多个属性，把账号档案所有属性项映射到一种多维特征的分向量，向量中的每一维度的值是不同网络中的两个账号在各个属性信息上的相似度，通过给不同属性设定权重融合多个属性的相似度，最终计算得出档案相似度，再与预定阈值相比较，判定是否属于同一用户。相关的研究成果有很多，如Vosecky等^[5]首次提出将用户的档案信息表示为由多个属性字段组成的n维向量，各个用户的相似度用向量相似性计算方法来计算，它的缺点是属性与领域是紧耦合的，每次个性化应用的改变都需要权重的重新计算。Raad等^[6]将用户的配置信息转移到FOAF(Friend-Of-A-Friend)词汇表，利用判定算法计算两个账号的相似度，该方法的问题在于识别时使用电子邮件地址作为用户唯一标识符，而该私人信息能被其他人获取，所以算法的应用受限。Motoyama等^[7]收集了Facebook和Myspace中用户账号的学历程度、职业等档案信息，把它们作为单词集合，通过比较单词的相似度来衡量账号的相似度。Zamani等^[8]综合考虑不同社交网络中用户账号的单位、地址、专业兴趣以及过往经历等信息，并使用了从简单的均等评价模型到复杂的训练混合模型等一系列方法来融合多个档案信息属性的相似度，通过实验验证了准确识别用户身份的可能性。Ye等^[9]提出一种社交网络中主观导向的客观赋权方法用于合成属性信息，计算用户档案相似度。Esfandyari等^[10]则提出了一种新的训练集中反面案例选择方法，相比传统的随机选择法，提出基于重叠属性项的选择方法使得训练出来的模型鲁棒性更强。

目前基于账号属性信息的跨网络用户身份识别方法主要将不同属性的值都看作字符串，通过计算字符串相似度刻画属性相似度。该类处理方法具有计算简单、适用于大规模数据集的特点。此外该方法在融合多个属性信息时，多采用主观导向的客观修正法，即专家根据各属性的重要程度主观确定权重系数，然后根据结果反馈进行权重修正，提高识别准确率。上述方法虽然取得了一定的效果，但是仍然存在以下问题：1) 将属性信息统一按照字符串进行处理，忽略了某些属性的特殊性，在相似度刻画中存在缺陷，造成匹配结果精度受限；2) 主观赋权导向的客观修正法是基于特定网络训练出来的，推广到其他网络中时模型的合理性受到质疑，面对新的网络时需要训练新的模型，会增加复杂度。

针对上述问题，本文基于用户档案中多个属性信息的身份识别问题进行建模与分析，对不同类型的属性制定了适用于账号匹配领域的科学合理的相似度计算方法，并综合考虑了各属性项所含信息量与对账号匹配的贡献程度，提出了一种可以适应不同网络环境、鲁棒性强的基于信息熵的权重赋予方法，通过判定算法计算两个档案的相似度，识别出同一用户在多个网络中的账号身份，从而进一步融合多个社交网络中的用户身份信息，为社交网络的数据挖掘与分析打下坚实基础。本文通过在爬取到的社交网络用户信息真实数据上进行实验，验证了所提算法的有效性。

1 相关工作 1.1 用户属性建模

本文利用账号档案中的多个属性信息构成一个多维特征向量，用来表征用户在特定网络中的身份。

定义1 在某一个特定网络中，用户档案信息共含有n个属性项，则档案信息向量定义为F_j=(a₁^j, a₂^j, …, a_n^j)，其中a_i^j(i=1, 2, …, n)表示账号j档案信息的第i个属性项。

可以被识别的用户是指在目标网络中可以找到一个账号F_d与源网络中的账号F_s相匹配。选取不同网络中账号的用户身份向量，通过计算两个向量中各个属性项的相似度，构建账号相似度向量。

定义2 账号相似度向量定义为V(F_s, F_d)=(v₁^sd, v₂^sd, …, v_n^sd)，其中v_i^sd=SimFunc(a_i^s, a_i^d)(i=1, 2, …, n)，表示账号F_s和账号F_d的档案信息中第i个属性项的相似度，且0≤|v_i^sd|≤1，|V|=|F_s|=|F_d|。

SimFunc()函数用来计算各个属性项的相似度，如果两个属性项完全一致，则SimFunc()函数返回值为1；如果两个属性信息完全不同，则SimFunc()函数返回值为0。不同的属性信息，用来计算相似度的SimFunc()函数形式也会不同。

1.2 字符串相似度计算方法

大多数的属性项都存储为字符串类型，因此利用计算字符串序列之间相似程度就可以获取该属性项的相似度。字符串相似度的计算已经建立了成熟的理论和模型，并且已经被广泛应用，其中来自统计学、数据库、人工智能领域的学者都从自身的研究领域出发，提出了不同的相似度计算方法。常见的字符串距离公式有：

1) Levenshtein距离。Levenshtein距离d_lev又叫作编辑距离，它是通过计算使两个字符串相等所需的单个字符编辑(增加、删除、替换)步数，以此作为操作代价衡量两个字符串的差异性。字符串l_i和l_j的Levenshtein相似度计算方法如式(1)：

${SimFun}{{{c}}_{\text{lev}}}({{l}_{i}},{{l}_{j}})=1-\frac{{{d}_{\text{lev}}}({{l}_{i}},{{l}_{j}})}{\max (\left| {{l}_{i}} \right|,\left| {{l}_{j}} \right|)}$

(1)

其中|l_i|和|l_j|表示字符串中字符的个数。

2) Jaro距离。Jaro距离是基于公共字符的个数与顺序的方法，最初是用在人口普查中判定健康记录中两个名字是否相同，因此非常适用于用户名的匹配。字符串l_i和l_j的Jaro距离计算方法如式(2)：

${{d}_{\text{Jaro}}}({{l}_{i}},{{l}_{j}})=\frac{1}{3}\left( \frac{m}{\left| {{l}_{i}} \right|}+\frac{m}{\left| {{l}_{j}} \right|}+\frac{m-t}{m} \right)$

(2)

其中：|l_i|和|l_j|是每个字符串的长度，m是公共字符的个数，t是换位的个数。字符串l_i和l_j的Jaro相似度计算方法如式(3)：

${SimFun}{{{c}}_{\text{Jaro}}}({{l}_{i}},{{l}_{j}})=1-\frac{{{d}_{\text{Jaro}}}({{l}_{i}},{{l}_{j}})}{\max (\left| {{l}_{i}} \right|,\left| {{l}_{j}} \right|)}$

(3)

3) Dice系数。对于多值属性字符串，Dice系数的计算方式是两个字符串n_i和n_j的交集信息的2倍除以n_i和n_j的元素总和，如式(4)：

${SimFun}{{{c}}_{\text{Dice}}}({{n}_{i}},{{n}_{j}})=2\frac{\left| {{n}_{i}}\bigcap {{n}_{j}} \right|}{\left| {{n}_{i}} \right|+\left| {{n}_{j}} \right|}$

(4)

例如对于两个多值属性字符串“sports music movie”和“music reading traveling”，交集信息为{“music”}, 所以相似度为2/6≈0.33。

对于单值属性字符串，Dice系数的计算方式是两个字符串l_i和l_j的交集信息的2倍除以l_i和l_j的长度总和，如式(5)：

${SimFun}{{{c}}_{\text{Dice}}}({{l}_{i}},{{l}_{j}})=2\frac{\left| {{l}_{i}}\bigcap {{l}_{j}} \right|}{\left| {{l}_{i}} \right|+\left| {{l}_{j}} \right|}$

(5)

其中当定义好字符组包含的字符个数为N时，交集信息|l_i∩l_j|是指两个字符串相同的字符组个数。例如当定义N=2时，对于两个字符串“Jon”和“Jone”，“Jon”的字符组是{“Jo”，“on”}, “Jone”的字符组是{“Jo”，“on”, “ne”}, 交集信息为{“Jo”，“on”}，所以相似度为2×2/5=0.8。

4) MN(Matching Name)距离。MN用户名匹配算法^[5]包括两个步骤：先是预处理，将用户名中含有的特殊字符或表情删除；然后将精确匹配与部分匹配结合，得到最终的匹配结果值。

1.3 图像数据相似度计算方法

图像类数据相似性的计算方法较为复杂，主要是因为不同网络中头像图片的格式、类型可能不同，而且拍摄时角度的不同也会带来图像的差异。

针对各种图像变形的问题，采用两种技术联合计算图像相似度，因为感知哈希算法(Perceptual Hash Algorithm，PHA)^[15]不擅长处理图像角度变换的情况，而尺度不变特征变换(Scale-Invariant Feature Transform, SIFT)算法^[16]不擅长处理计算机生成的图片，两者结合互补可以使相似度算法具有更好的鲁棒性。

1.4 地理位置之间距离计算方法

l_i和l_j分别表示账号i和账号j的地理位置，地点l_i的经纬度坐标为(lat_i, lon_i)，地点l_j的经纬度坐标为(lat_j, lon_j)，两个全球定位系统(Global Positioning System, GPS)坐标之间的距离采用大圆距离的计算方法计算^[17]，大圆距离指的是从地球的一点出发到达球面上另外一点所经过的最短路径长度，计算方法如式(6) 所示，

$\begin{align} &d\left( {{l}_{i}},{{l}_{j}} \right)=2R\times \arcsin \left( {{\sin }^{2}}\left( \frac{{la}{{{t}}_{i}}-{la}{{{t}}_{j}}}{2} \right) \right.+ \\ &\quad \quad \quad \quad {{\left. \cos \left( {la}{{{t}}_{i}} \right)\cos \left( {la}{{{t}}_{j}} \right){{\sin }^{2}}\left( \frac{{lo}{{{n}}_{i}}-{lo}{{{n}}_{j}}}{2} \right) \right)}^{1/2}} \\ \end{align}$

(6)

其中：R为地球半径(6 371 km), d(l_i, l_j)的单位为km。

2 基于信息熵的用户身份识别算法 2.1 身份识别问题建模

用户是现实生活中的真实个体，账号表示该人在虚拟网络中的身份。每个用户在社交网络中存在两种身份标识：一种是特定社交网络中唯一辨识用户身份的ID号；另一种是可以跨网络识别用户的身份标识。前者由社交网站进行管理，而后者实际上并不存在，通过某种技术手段将同一人在不同社交网络中的多个ID号连接起来，可以识别出用户的多个账号身份，从而全面融合用户信息，实现相关的数据挖掘与应用。

用户在各个社交网站中的身份标识集合表示为D={d_i}_i=1^l，其中d_i表示用户在第i个网络中的身份标识。将特定社交网络建模成一个图G=(N, E, F, ϕ)，其中：节点集合N表示网络中的用户；边集合E表示两个用户之间的好友关系；属性集合F={a_j}_j=1ⁿ表示用户在该网站注册的档案信息，a_j表示第j个属性项；ϕ表示从用户虚拟身份到真实身份的映射函数，可以将用户在不同网络中分散的账号身份联系起来ϕ₁(n₁)=ϕ₂(n₂)=…=ϕ_n(n_n)=d。

2.2 属性相似度计算

目前属性信息相似度的测量方法很多，只有针对不同的类型和领域信息选择不同的比较方法，才最能真实地反映相似程度，取得最佳的匹配准确率与效率。本文选择用户的用户名、自我描述、兴趣爱好、网页链接、地理位置、头像共6类属性信息作为账号相似度的衡量基准。按照属性项的数值所属的不同数据类别，可以分为三类：字符串类型、图像类型以及数字类型。其中属于字符串类型的有用户名、自我描述、兴趣爱好和网页链接，属于图像类型的是用户头像，属于数字类型的是地理位置，各自的相似度计算方法如下。

1) 用户名。用户名是最容易获得的属性信息，通常也包含在用户档案主页统一资源定位符(Uniform Resoure Locator, URL)中。相关研究表明，用户在不同网络中注册账号时，倾向于在一个用户名的基础上做一些微小的变化，例如在原有用户名中插入特殊符号、简写部分字符串、改写部分字符、交换部分字符串、添加具有特殊含义的字符串等, 从而衍生出多个相似的用户名。如原有用户名为“Alfred Gin”, 则用户可能会在其他网站中注册账号为“**Alfred Gin**”“A Gin”“Alfr@d Gin”“Twitter Alfred”“Alfred Gin Twitter”等。根据文献[5]的研究表明，与其他算法相比，MN算法计算的用户名相似度更加客观真实、合乎逻辑，所以本文采用MN算法计算用户名相似度。

2) 自我描述。自我描述是一段类似于自我介绍的话，告诉他人自己的兴趣、特长、观点、理念等，向他人“推销”自己，从而吸引志同道合的人添加好友关系。自我描述通常是一段字符串，利用词频-逆文档频率(Term Frequency-Inverse Document Frequency, TF-IDF)构建关键词向量，通过计算向量的余弦相似度作为不同网络中自我描述的相似度。

3) 兴趣爱好。用户在社交网站中会关注自己所感兴趣的话题，加入特定主题的群组，以及经常阅读、分享自己喜欢的文章等，从这些行为中都可以抽取出用户的兴趣爱好。以所有描述用户兴趣主题的词构建“兴趣标签词袋”，每个账号依据各自的兴趣从“兴趣标签词袋”中抽取出部分词标签集，利用Dice算法计算多词属性相似度，作为不同网络中兴趣爱好相似度。

4) 网页链接。网页链接是该用户其他网络中账号主页的URL，它可以唯一标识用户的身份，本文选取的策略为当两个账号的网页链接相同则网页链接相似度为1，否则为0。

5) 地理位置。地址信息是社交网站中常见的属性信息，由于不同网络中地址信息书写格式不同，若采用字符串匹配则会带来误判，而且依据字符串比较不同地理名称的相似性没有实际意义，所以通过百度地图应用程序编程接口(Application Programming Interface, API)将地理名称转化为相应的经纬度坐标，利用式(6) 计算两地之间的距离，从而判断地理位置是否相同。

6) 头像。本文选取的属性中，用户头像属于图像类数据。主要采用两种方法计算头像图片的相似度：一是PHA技术，该技术通过比较图片的“指纹”来判断两幅图片是否相似；另一个是SIFT技术，该技术通过匹配检测出的局部特征来比较两幅图片的相似度。

上述的属性信息中，利用网页链接、地理位置和头像进行身份识别时，由于其现实意义的特殊性，衡量这些属性的相似度应当具有“断层”性质，即大于“断层式”阈值则认定为相同，相似度为1，否则不相同，相似度为0，其余的相似度值对于身份匹配应用而言没有意义。所以本文对于这些属性的利用，在传统的相似度计算基础上，设置了二值判定，从而使得匹配结果更加科学合理。

2.3 信息熵确定属性权重

在确定档案信息中各项属性对于相似度决策判定的权重系数时，传统的专家主观赋权法是与属性领域紧耦合的，算法鲁棒性较差，而客观赋权法依赖于足够的样本数据，通用性和参与性差。

为解决以上问题，本文提出了基于信息熵的赋权方法。熵权法的基本思想是认为指标的差异程度越大越重要, 则权重相应也越大。计算时, 如何实现各指标间熵值与熵权的转换是关键环节, 其直接影响着各指标客观权重的正确性, 进而关系着方案评价的合理性、可靠性。在信息论中, 熵值反映了信息无序化程度：其值越小, 系统越有序, 携带的信息越多；其值越大，系统越混乱，携带的信息越少。故可用信息熵评价所获系统信息的有序度及其效用, 即由评价指标值构成的判断矩阵来确定指标权重, 消除各指标权重计算的人为干扰, 使评价结果更符合实际。

依据信息熵的定义，当系统可能处于多种不同的状态，每种状态j出现的概率为p_ij(j=1, 2, …, n)时，系统的熵为：

${{E}_{i}}=-\sum\limits_{j=1}^{n}{\left( {{p}_{ij}}\times \operatorname{lb}{{p}_{ij}} \right)}$

(7)

其中E_i表示第i个事件。

本文根据用户各属性的相似度确定其权重，匹配账号的相似度与不匹配账号的相似度差别越大，信息越有序，熵值越小，该属性携带的信息越多，该属性越有价值，对用户识别的判断就越准确，所以熵权应该越大；匹配账号的相似度与不匹配账号的相似度差别越小，信息越无序，熵值越大，该属性携带的信息越少，该属性价值越低，对用户识别的判断就越模糊，所以熵权应该越小。基于以上分析，对式(7) 中的p_ij定义为属性相似度出现的概率，如式(8)：

${{p}_{ij}}={{{v}_{i}}^{sj}}/{\sum\limits_{j=1}^{n}{{{v}_{i}}^{sj}}}\;$

(8)

其中v_i^sj表示目标网络中第j个账号F_j与源网络中账号F_s第i个属性的相似度。根据以上定义，式(7) 被重定义为：

${{E}_{i}}^{sj}=-\sum\limits_{j=1}^{n}{\left[ {{v}_{i}}^{sj}/\sum\limits_{j=1}^{n}{{{v}_{i}}^{sj}} \right]\times \operatorname{lb}\left[ {{v}_{i}}^{sj}/\sum\limits_{j=1}^{n}{{{v}_{i}}^{sj}} \right]}$

(9)

由于熵值与权重成反比，所以构建变种熵值R_i^sj：

${{R}_{i}}^{sj}=1/{{E}_{i}}^{sj}$

(10)

通过变种熵值确定待选目标账号的每个公共属性的权值w_i^sj：

${{w}_{i}}^{sj}={{R}_{i}}^{sj}/\sum\limits_{i=1}^{n}{{{R}_{i}}^{sj}}$

(11)

2.4 用户账号匹配

根据相似度向量的定义，则衡量两个账号相似度的计算方法如式(12) 所示：

$\mathit{Similarity}\left( {{\mathit{\boldsymbol{F}}}_{\rm{s}}},{{\mathit{\boldsymbol{F}}}_{\rm{d}}} \right)=\sum\limits_{i=1}^{n}{\left( {{w}_{i}}^{\rm{sd}}\times {{v}_{i}}^{\rm{sd}} \right)}$

(12)

其中w_i^sd表示属性的权重。综上，两个账号相似度的计算方法如下。

算法1 档案相似度计算方法。

输入 源网络账号档案信息向量F_s，目标网络中所有账号的档案信息向量{F_j}_j=1^m，目标网络中待匹配的候选账号档案信息向量F_d；

输出 F_s和F_d两个账号的相似度Similarity(F_s, F_d)。

1)  foreach F_j in {F_j}_j=1^m

2)   for i=1 to n

3)    计算单属性项相似度v_i^sj=SimFunc(a_i^s, a_i^j)

4)   end

    构建账号相似度向量

5)   V(F_s, F_j)=(v₁^sj, v₂^sj, …, v_n^sj)

6)  end

7)  for i=1 to n

8)   利用式(8) 计算属性i相似度出现的概率p_ij

9)   利用式(9) 计算属性i的信息熵值E_i^sj

10)   利用式(10) 计算属性i的变种熵值R_i^sj

11)   利用式(11) 计算属性i的信息熵权重w_i^sd

12)  end

13)  利用式(12) 计算F_s和F_d两个账号的相似度Similarity(F_s, F_d)

14)  return Similarity(F_s, F_d)

通过比较不同账号对之间的相似度值的大小，确定最佳匹配账号对。

基于属性信息的跨网络用户判定流程如下：源网络与目标网络中有两个待识别账号F_s和F_d，从它们的档案信息中抽取属性集合{a₁, a₂, …, a_n}，然后对不同的属性项进行相似度计算v_i^sd=SimFunc(a_i^s, a_i^d)(i=1, 2, …, n)，并赋予不同的权重w(a_i)(i=1, 2, …, n)，最后通过决策判定两个账号是否有可能属于同一个人。

2.5 身份识别过程

基于属性信息的跨网络用户身份识别过程包括三个步骤：账号选择、账号匹配、剪枝过滤。

1) 账号选择。

在对一个网络中的源账号F_s进行用户识别时，如果每次都是从另一个网络中选取所有的目标账号F_d进行关于档案信息中所有属性的相似度计算，则计算量会非常大，尤其是当网络中注册账号的规模十分庞大时，逐一比较更是不现实、不可行的。因此在选取目标账号F_d与源账号F_s进行相似度计算时，有必要根据条件C对另一网络中的目标账号进行筛选，采用单个较为简单的属性作为筛选器，从全集中过滤出与源账号F_s有较高匹配概率的候选账号集合，从而降低计算量。

通过对人们生活习惯的观察与分析，用户在不同网络中倾向于使用相似的用户名，又因为用户名的相似度计算在所有属性中是最简单的，所以本文使用用户名作为筛选器，选择一个合适的阈值来平衡候选集规模与覆盖率之间的关系，求得一个折中值。

2) 账号匹配。

通过账号选择步骤，选出了满足条件C的与源账号F_s有可能匹配的候选账号集合，然后依次对集合中的候选账号与源账号F_s进行基于属性信息的相似度计算，选出其中与源账号F_s相似度最高的候选账号F_d作为待匹配账号，然后与预先设定阈值(通常情况下选取阈值为0.5)，如果大于阈值则判定为匹配，反之不匹配。

3) 剪枝过滤。

得到最终匹配结果后，为了确保精确度，有时需要剪枝过滤的过程去除一些错误的匹配。本文对两个网络G₁和G₂中的账号进行识别时，以网络G₁中的账号F_s作为源账号在网络G₂中寻找匹配的目标账号F_d后，再以网络G₂中的F_d作为源账号在网络G₁中寻找匹配的目标账号，如果匹配的是F_s，则保留该对匹配账号，否则舍弃该对账号。

算法2 基于信息熵的跨网络用户身份识别算法(Information Entropy based Multiple Social Networks User Identification Algorithm, IE-MSNUIA)。

输入 源网络账号档案信息向量F_s，目标网络中所有账号的档案信息向量{F_j}_j=1^m，候选集筛选条件C对应的筛选器属性C_p，筛选器属性匹配阈值T_c，账号匹配阈值T_p；

输出 与F_s匹配的账号F_d。

1)  foeach F_j in {F_j}_j=1^m

2)   根据条件C计算F_s和F_j单属性项C_p相似度v_p^sj=SimFunc(a_p^s, a_p^j)

3)   if v_p^sj≥T_c

4)    c++

5)    将F_j加入匹配候选集{CF_j}_j=1^c

6)  end

7)  max=0

8)  foreach CF_j in {CF_j}_j=1^c

9)   利用算法1计算档案相似度Similarity(F_s, CF_j)

10)   if Similarity(F_s, CF_j)＞max

11)   max=Similarity(F_s, CF_j)，d=j

12)  end

13)  if max≥T_p

14)   return F_d

15)  else return null

3 实验结果及分析 3.1 数据集的获取与设置

在一些社交网络中，用户在填写自己的档案信息时，往往喜欢添加进自己在其他网络中的个人主页链接，意在邀请他人与自己在其他网络中也建立起好友关系，这一行为给验证个人多个账号身份提供了可行性。Google+就是此类型的社交网站，该网站上的用户档案中有一项属性是“链接”，用户可以在此张贴自己在其他社交网站上的个人主页链接。为了验证所提算法的有效性，本文选取从Google+、Facebook和Twitter这三个社交网络中收集的账号属性信息进行用户身份识别的相关实验。文献[18]提供了一份包含5个社交网络账号主页链接的公开数据集，本文以Google+作为收集用户属性信息的源网站，过滤选取其中给出Facebook和Twitter主页链接非空、网页未失效且公开档案信息访问权限的Google+账号，最终得到Google+账号5 916个，Facebook账号4 377个，Twitter账号5 829个。用户属性信息获取流程如下：首先从中抽取出用户主页链接地址URL，然后借助第三方网站查询出对应的用户账号ID，再通过官方提供的API接口爬取档案信息数据，最后将数据存入数据库以供实验使用。

不同的社交网络中用户档案信息的属性项个数与内容并非完全相同，而且同一个用户在不同网络中填写的情况也有差异。网络中经常出现用户属性项缺失的情况，属性项缺失通常是用户漏填或者设定隐私保护造成的，所以爬取到的档案数据并不能直接使用，需要对待匹配的两个网络中的公共属性项进行筛选与语意匹配。通过综合分析，本文最终确定在匹配Google+、Facebook和Twitter网络中账号时，选取三个网络中都具备的、通过API可以获取到且用户填写较为齐全的6种属性项：用户名(username)、自我描述(biography)、兴趣爱好(interests)、网页链接(URL)、地理位置(location)、头像(avatar)。对于这6项属性信息中依然存在的缺失数据以及明显不符属性内容的噪声数据，采用该项属性所有用户的平均值进行补充或者替换。

3.2 评价指标

使用IE-MSNUIA可以判断两个账号是否匹配，如果账号的档案信息相似度大于一定的阈值，则判定为匹配，即两个账号对应于现实生活中的同一个用户，反之则判定为不匹配。本文采用准确率(precision)、召回率(recall)以及综合评价指标F1作为衡量算法性能的评价标准。具体定义如下，

${precision}\text{=}{tp}/\left( {tp}\text{+}{fp} \right)$

(13)

${recall}\text{=}{tp}/\left( {tp}\text{+}{fn} \right)$

(14)

${F}\text{1=2}\times {precision}\times f{recall}/\left( {precision}\text{+}{recall} \right)$

(15)

准确率(precision)是指正确匹配的比率，其中tp表示被算法匹配上并且对应于同一用户的账号对数, fp表示被算法匹配上但是对应于不同用户的账号对数；召回率(recall)是指正确识别的比率，其中fn表示未被算法匹配上的对应于同一用户的账号对数；F1是前两者的调和平均数，是算法性能的综合评价指标。

3.3 实验结果 3.3.1 单属性匹配性能分析

在实验中，首先测试了各个单项属性在账号匹配中的性能，实验结果如图 1所示。其中本文设置二值属性网页链接和头像各自的“断层式”阈值为1和0.9；对于地理位置属性，本文将范围控制在市级单位，即两地相距在80 km以内则认为地理位置相似度为1，否则为0。利用属性项用户名、网页链接和头像在匹配时，同一用户与不同用户的相似度分布集中且差别较大，该项属性在匹配时具有较强的区分性，所以权重应当较大。属性项自我描述和兴趣爱好在匹配时，同一用户与不同用户的相似度分布离散且差别较小；属性项地理位置在匹配时，同一用户与不同用户的相似度有交错现象，这些属性项匹配时的分辨力较弱，所以权重应当较小。

用信息熵确定权重时，对于确定了目标网络以后，每个源网络中待匹配账号F_s都有属于自己的一个权重分配方案。实验选择在Google+和Facebook、Google+和Twitter以及Facebook和Twitter这3组网络中进行账号匹配，图 2是在这3组网络中账号权重分配的分布图，从分布来看，用户名和网页链接的权重都较大，而另外四项属性的权重都较小，这与上面的分析结果是一致的，验证了信息熵权的客观性与合理性。

3.3.2 身份识别算法性能分析

本实验选择的对比算法包括支持向量机(Support Vector Machine, SVM)算法和随机森林(Random Forest，RF)法两种有监督的机器学习算法以及Vosecky等^[5]、Ye等^[9]和Esfandyari等^[10]提出的基于主观赋权的算法。机器学习算法相当于把身份识别看作账号“匹配”与“不匹配”的二分类问题，将各属性项的相似度看作输入的特征数据，把匹配与否作为输出的判别类型，模型训练时正负两类样本比例设为1:1，训练集和测试集的比例设置为3:1。Vosecky等^[5]根据不同属性项的字符串特点，对不同的属性项采取精确匹配、部分匹配和模糊匹配三种不同的方法计算字符串相似度，利用主观经验初始化各属性项的权重，然后再用控制变量法，以准确率为目标对各权重进行修正。Ye等^[9]则是将属性分为决定性属性和非决定性属性两种，赋权方法采用的是主观导向的客观赋权法，即首先依据专家经验赋权，然后依据相似度对其进行反向客观修正。Esfandyari等^[10]在权重选择上参照了Vosecky等^[5]的方法，但是在训练集的选取上有所变化，同时选择正确匹配和错误匹配的数据训练模型，从而使得算法鲁棒性更好。实验在三组数据集(Google+&Facebook、Google+&Twitter、Facebook&Twitter)上进行测试，其中机器学习算法采用10折交叉验证的方法求得最终结果。图 3显示了不同算法在不同数据集上的性能参数对比情况，并且为了表述方便，横轴的算法A~F分别代表SVM算法、RF法、Vosecky等^[5]的方法、Ye等^[9]的方法、Esfandyari等^[10]的方法和本文的IE-MSNUIA。

实验结果显示，本文算法优于对比算法，在不同的数据集上均具有最好的性能。具体分析其原因在于，机器学习算法具有较好的身份识别效果，而且在可用属性信息充足的条件下采用不同机器学习算法进行身份匹配时，匹配效果的变化并不大；然而由于机器学习算法本身存在的缺点，例如SVM算法对缺失数据敏感的问题，以及随机森林法在处理取值划分较多的属性时权重不可信的问题，导致性能受限。此外，机器学习算法性能依赖于训练集数据组成的问题也限制了其应用的广度。

相比较而言，另外三种基于主观赋权修正的对比算法，由于直接对属性赋权，相比分类器算法，省去了模型训练的过程，所以较为简单高效；此外还加入了对权值的修正过程，性能也较分类器算法有一定程度的提升。

本文的IE-MSNUIA综合考虑了不同属性项信息自身的数据特点与现实含义，并没有像三种基于主观赋权修正的对比算法那样将属性统一按照字符串进行处理，而是制定了更科学合理的相似度计算方法，从而实验结果更加精确；另一方面，基于信息熵的赋权方法综合考虑了各属性项所含信息量与对账号匹配的贡献程度，所以各个属性项权重的可信度更高。从实验结果可以看出，本文算法的平均准确率可以达到97.2%，平均召回率可以达到94.1%，平均F1值可以达到95.6%，验证了其有效性。

4 结语

本文提出了一种基于属性信息的跨网路身份识别算法，通过利用不同社交网络开放的API接口可以爬取得到的公共用户属性信息，构建待匹配账号相似度向量，并依据信息熵的思想对不同属性赋予不同权重，计算账号档案信息的整体相似度进行账号匹配，实现了在Google+、Facebook和Twitter三个网络之间的跨网络用户识别。现有的基于属性信息进行身份识别的方法在计算不同类型属性项相似度时统一按照字符串进行处理，而本文则通过分析属性不同的数据类型特征采用不同的相似度衡量策略，实验结果验证了该算法的有效性与合理性。由于本文算法对每个待识别源账号都需要计算一套属性权值分配方案，当社交网络中待匹配的账号规模变大时，属性项权值计算量也会变大，所以下一步的工作将着眼于如何进一步地改进权值计算方法，降低算法的计算开销。