一种基于结构和属性相似度的用户实体解析方法

摘要

本发明公开了一种基于结构和属性相似度的用户实体解析方法，通过对社交网络的分析和建模，结合了社交网络中的好友关系和用户个人资料，即结构信息和属性信息，实现了跨社交平台的用户实体解析的目的。在实体解析的过程中，引入了动态阈值的概念，在迭代的不同时期使用不同的阈值来适应当前情况下的数据特点，调控属性和结构所占比重，以获得更为准确地结果。

说明书

技术领域

本发明属于实体解析技术领域，更为具体地讲，涉及一种基于结构和属性相似度的用户实体解析方法。

背景技术

在数据集中，数据所指向的现实世界中的对象，一般称之为实体(Entity)。对于同一实体，在不同甚至同一数据集中，可能存在多种不同的表现或描述形式，当将多个不同来源的数据集进行合并以分析处理时，这些对于同一实体的描述则会混杂在一起，造成一定程度的重复现象。实体解析(Entity Resolution)，就是对数据集中的多种不同的描述进行识别、连接，确定哪些描述映射于现实世界中的同一实体的过程。实体解析是数据预处理过程中的一个重要步骤，主要用于解决数据的重复冗余等质量问题。

随着社交网络的快速发展，实体解析在社交网络方面的应用逐渐受到了关注。大部分社交网络用户不仅仅使用一个社交网络，而是根据自己的兴趣和需要，同时使用多个社交网络，而不同的社交平台之间的信息是孤立的、不互通的，因此没有办法直接识别同一个用户在不同平台的虚拟身份。社交网络的跨平台实体解析问题，就是匹配和识别在不同社交平台上的属于同一用户实体的账户，即用户识别或账户匹配。通过账户身份的匹配，能够实现对用户的个性化服务，并且也有助于解决社交网络的一些安全问题。

实体解析这一概念最早被提出于1959年。Newcombe等人在《科学》上发表的文章首次提出了这个概念，并认为实体解析是一个统计问题，从概率的角度阐述了实体解析问题。十年后的1969年，Fellegi和Sunter首次对实体解析问题做出了规范化和公式化，他们将其视为一个机器学习中的分类问题并且在他们的文章中规范了实体解析的一系列符号和定义，建立了经典的Fellegi-Sunter模型。在此之后的研究中，有很多研究者对Fellegi-Sunter模型进行了改进和补充，主要有Jaro，Winkler，Belin和Rubin，Ravikumar，Larsen，Sadinle等人，其中，Winkler做了大量的工作，采用贝叶斯统计模型，对Fellegi-Sunter模型的参数计算和匹配规则等做了一系列的改进。

针对社交网络的实体解析研究，主要于近些年展开。大部分研究者着眼于社交网络的属性、结构和社交内容这几个方面展开研究。属性指的是用户的个人资料，如头像、用户名、性别、生日、教育背景、所在地等，结构指的是社交网络中账户与账户间的好友关系，而社交内容指的是用户在社交活动中产生的文本、图片等信息，如博客、评论、地理位置等。

基于属性的算法主要利用的是社交网络中用户的个人资料信息，将每一项描述信息分别视为用户的一个属性，把问题转化为属性字段的匹配。如Zafarani和Liu利用用户名和用户个人主页的URL，提出了用户实体解析算法。Goga等人提出了适用于大规模身份识别的算法。基于结构的算法就是主要利用社交网络的好友关系信息，把社交网络抽象成图结构，利用一些图结构信息来实现用户实体解析。Narayanan和Shmatikov^[13]以及Bartunov等人从这个角度研究了相关的算法。基于社交内容的算法利用对文本风格的分析，以及时间、地理位置等信息，实现用户实体解析。如Almishari和Tsudik提出了一种通过分析作者写作风格，在不同社交平台识别用户的方法。Goga等人提出了利用用户发布内容时的地理定位、时间戳，以及内容的写作风格来联合实现用户识别的工作。

对于着眼于属性信息的算法，由于社交平台上的账户个人资料存在一定程度的缺失和不准确，这类异常的数据会对算法性能造成影响，并且这种来自数据本身的影响是很难去除的。从结构出发的算法避免了信息的不准确，但当存在人数不多的小团体中，可能多个账户之间几乎形成了全连接的情况，那么这些账户之间如何区分则成了一个十分困难的问题。因此基于结构的算法在好友关系十分密集的情况下，难以很好的发挥作用。而基于内容的方法，相关数据难以获取且难以处理，不便于使用。本发明提出的方法，有机的结合了属性和结构两类信息，尽可能避免了各种方法的缺陷。

发明内容

本发明的目的在于克服现有技术的不足，提供一种基于结构和属性相似度的用户实体解析方法，结合属性和结构两方面信息，来解决社交网络跨平台的用户实体解析问题。

为实现上述发明目的，本发明一种基于结构和属性相似度的用户实体解析方法，其特征在于，包括以下步骤：

(1)、建立属性相似度矩阵和邻接矩阵

根据社交平台A和社交平台B上的所有账户两两之间的属性相似度，构建属性相似度矩阵S^m×n，其中，m和n分别为平台A和B中的账户总数，S^m×n中的元素表示对应两个账户间的属性相似度；

分别根据社交平台A和社交平台B上的所有账户两两之间是否为好友关系，建立邻接矩阵和其中，邻接矩阵的每一行、每一列都代表该平台内的一个账户，邻接矩阵中元素表示该平台内对应两个账户之间是否为好友关系，如果为好友关系，则该元素值为1，如果不为好友关系则该元素值为0；

(2)、建立关联矩阵

根据邻接矩阵和先验匹配对，建立社交平台A和社交平台B中未识别账户与已识别账户之间的关联矩阵其中，τ表示先验匹配对的个数，关联矩阵的每一行代表未识别账户，每一列都代表已识别账户，关联矩阵中元素表示未识别账户与已识别账户之间是否为好友关系，如果为好友关系，则该元素值为1，如果不为好友关系则该元素值为0；

(3)、建立共同好友矩阵

根据关联矩阵和先验匹配对，建立社交平台A和社交平台B中未识别账户的共同好友矩阵；

其中，()^T表示转置，共同好友矩阵的每一行代表社交平台A中的一个未识别账户每一列代表社交平台B中的一个未识别账户共同好友矩阵中元素f_ij表示和在先验匹配对中的共同好友个数；

(4)、从共同好友矩阵中选出最大非零元素对应的两个未识别账户组成的账户对，并存放在账户对集合Q中，Q＝{(i,j)|f_ij＝max(F^{(m-τ)×(n-τ)})}；

(5)、在属性相似度矩阵S^m×n中，取出账户对集合Q中所有账户对之间的属性相似度，并存放在相似度集合S^*中，S^*＝{s_ij|s_ij∈S^m×n,(i,j)∈Q}；

(6)、根据预设的初始阈值，将相似度集合S^*中低于初始阈值的元素删除，同时将账户对集合Q中的对应元素删除；

(7)、判断账户对集合Q是否为空，如果为空，则将共同好友矩阵中的最大非零元素置0，再返回步骤(4)；如果不为空，则进入步骤(8)；

(8)、取出相似度集合S^*中的最大元素max(S^*)，并在账户对集合Q中选出与max(S^*)对应的账户对(i,j)，则(i,j)对应的一组账户标记为匹配成功，并加入到本轮迭代的结果集M中；

(9)、账户对集合Q中删除加入到结果集M中的账户对(i,j)，以及与(i,j)有共同账户的账户对，同时删除相似度集合S^*中对应元素；

(10)、判断账户对集合Q中是否还存在元素，如果存在，则返回步骤(8)；如果不存在，则输出结果集M；

(11)、将结果集M中对应的账户对加入到先验匹配对中，再返回步骤(2)，进行本轮的下一次迭代，当结果集M中没有新的匹配对输出时本轮迭代结束；

(12)、修改初始阈值的大小，再返回步骤(2)，进行下一轮的迭代，当通过修改初始阈值后，结果集M中仍然没有新的匹配对输出时迭代结束，完成用户实体解析。

本发明的发明目的是这样实现的：

本发明一种基于结构和属性相似度的用户实体解析方法，通过对社交网络的分析和建模，结合了社交网络中的好友关系和用户个人资料，即结构信息和属性信息，实现了跨社交平台的用户实体解析的目的。在实体解析的过程中，引入了动态阈值的概念，在迭代的不同时期使用不同的阈值来适应当前情况下的数据特点，调控属性和结构所占比重，以获得更为准确地结果。

同时，本发明一种基于结构和属性相似度的用户实体解析方法还具有以下有益效果：

(1)、结合了属性和结构两方面的信息，避免了单一信息的缺陷和对结果准确性造成的不利影响，如属性缺失造成的影响以及好友关系密集带来的影响。

(2)、引入了动态阈值的概念，在迭代的过程中，属性相似度阈值并非始终不变，而是随着产生结果的增多，在一定的范围内逐渐变化，以适应不同迭代时期的特点。阈值起初从以上界开始执行，获得最为准确的结果，随后逐渐下降，以收纳更多属性相似度不够高的真实匹配对。

(3)、以先验匹配对作为迭代起点，每次迭代都将结果反馈到已知条件当中，不需要比较大量的已知条件或训练数据建立模型，仅需要较少的真实匹配对即可实施方法，避免了已知条件不足的问题。

附图说明

图1是本发明基于结构和属性相似度的用户实体解析方法流程图；

图2是示例中的两个社交平台的好友关系结构图。

具体实施方式

下面结合附图对本发明的具体实施方式进行描述，以便本领域的技术人员更好地理解本发明。需要特别提醒注意的是，在以下的描述中，当已知功能和设计的详细描述也许会淡化本发明的主要内容时，这些描述在这里将被忽略。

实施例

图1是本发明基于结构和属性相似度的用户实体解析方法流程图。

在本实施例中，我们先对一些名称的定义进行描述：

将一个社交平台建模成一个无向图的形式，账户对应节点，账户间的好友关系对应节点间的边，即G＝{V,E}，其中G表示社交平台，V为该平台中账户的集合，E为该平台中好友关系的集合。社交平台中的好友关系分为单向和双向两种类型。对于单向好友类型，理论上应该抽象化为有向图，但在本算法中，好友关系是用户实体解析的十分重要的依据，考虑到只有单向关注的账户之间，其亲密程度不足，不能很好的反映账户所属的用户真实的交友情况，因此，在单向连接的社交平台中，本算法只考虑互相关注的账户，并将这样的关系等价于双向连接中的好友关系，仍然将其建模成为一个无向图。

将社交平台中的每一个账户拥有的一系列个人资料统一称为节点的属性，每一项属性表现账户的某一项资料，如用户名、性别、年龄等。C表示属性的集合，C＝(C₁,C₂,C₃,…)，其中，C_i表示一项属性的名称。

同时本文将社交网站中的账户在真实世界中的所有者，即使用该账户的人，定义为用户实体。用户实体的集合用U表示，U＝(u₁,u₂,u₃,…)。

假设两个社交平台分别为A和B，则分别属于两个社交平台的两个账号，和如果它们指向同一个实体，即他们为真实世界中的同一个人所拥有，则称和匹配，表示为或M_A,B(i,j)，相反若不匹配，则表示为或UM_A,B(i,j)。如果匹配账号在真实世界中对应的用户实体是u_k，则可以表示为：

在进行账户匹配之前，一般需要一部分事先已经知道的正确匹配的账户对，这些匹配对一般被称为先验账户匹配对，或种子匹配对。在实际的用户实体解析过程中，先验账户匹配对的获取比较难以解决，除了人为手动的标注一些先验匹配对以外，主要的方法是找到一种能够确定用户实体的唯一标识，如电子邮箱，绑定账号，或IP地址等，但这类信息一般比较难以获得，因此需要考虑新的方法予以替代。

在没有可以直接确定先验匹配对的信息的情况下，可以考虑使用账户的属性相似度来获取先验匹配对。本文算法对先验匹配对的数量要求并不高，因此可以首先通过属性相似度，选出相似度最高的一部分账户匹配对，并在其中选取好友数最多的一部分账户对视为先验匹配对，以保证在网络中的重要地位，随后进行算法的执行。这样选取出的匹配对虽不能够保证准确的指向一个实体，但一定程度上能够解决先验匹配对较难获得的问题。

下面结合图1所示，对本发明一种基于结构属性相似度的用户实体解析方法进行详细说明，具体包括以下步骤：

S1、建立属性相似度矩阵和邻接矩阵

首先根据社交平台A和社交平台B上的所有账户两两之间的属性相似度，构建属性相似度矩阵S^m×n，本例中m和n均为7，这里直接给出属性相似度矩阵中除去先验匹配对的部分，用表格的形式展示，如表1所示。

表1是属性相似度矩阵的主要部分。

表1

接下来根据图2中两个平台的结构关系，如图2(a)和图2(b)所示，建立邻接矩阵和分别为：

S2、建立关联矩阵

根据邻接矩阵和先验匹配对，建立社交平台A和社交平台B中未识别账户与已识别账户之间的关联矩阵在本实施例中，先验匹配对为(1,1)和(2,2)两组，在图2中以实心节点表示，则关联矩阵分别为：

S3、建立共同好友矩阵

根据关联矩阵和先验匹配对，建立社交平台A和社交平台B中未识别账户的共同好友矩阵；

S4、从共同好友矩阵中选出最大非零元素对应的两个未识别账户组成的账户对，并存放在账户对集合Q中，Q＝{(i,j)|f_ij＝max(F^{(m-τ)×(n-τ)})}；

S5、在属性相似度矩阵S^m×n中，取出账户对集合Q中所有账户对之间的属性相似度，并存放在相似度集合S^*中，S^*＝{s_ij|s_ij∈S^m×n,(i,j)∈Q}；

S6、设定初始阈值，本实施例中将阈值的上界和下界分别设置为0.8和0.2，则初始阈值为0.8。将相似度集合S^*中低于初始阈值的元素删除，同时将账户对集合Q中的对应元素删除，此时Q＝{(3,3),(4,4)}，S^*＝{0.85,1}；

S7、判断账户对集合Q是否为空，如果为空，则将共同好友矩阵中的最大非零元素置0，再返回步骤S4；如果不为空，则进入步骤S8；

S8、取出相似度集合S^*中的最大元素max(S^*)，即1，并在账户对集合Q中选出与1对应的账户对(4,4)，则(4,4)对应的一组账户标记为匹配成功，并加入到本轮迭代的结果集M中；

S9、账户对集合Q中删除加入到结果集M中的账户对(4,4)，以及与(4,4)有共同账户的账户对，同时删除相似度集合S^*中对应元素，此时Q＝{(3,3)}，S^*＝{0.85}；

S10、判断账户对集合Q中是否还存在元素，如果仍有元素存在，返回步骤S8重复执行；如果没有元素存在，则本次迭代结束后，将(3,3)和(4,4)加入结果集M，并输出结果集M；

S11、将结果集M中对应的账户对加入到先验匹配对中，再返回步骤S2，重新构建关联矩阵和共同好友矩阵，进行本轮的下一次迭代，重复执行上述步骤，最终当没有新的结果产生时，本轮迭代结束，此时有(3,3),(4,4),(5,5)三组账户对被加入到结果集M中；

S12、修改初始阈值的大小，再返回步骤S2，进行下一轮的迭代；

修改阈值的公式为：

其中，th表示修改后的阈值，th_u和th_l分别为初始阈值的上界和下界，|M_c|表示当前结果集M中匹配对的个数，min(N_A,N_B)表示社交平台A和B的账户数量中较小的值，τ表示先验匹配对的个数。

根据公式，下一轮迭代使用的阈值为：

将M中的三组账户对加入到先验匹配对中，返回步骤S2并以新的阈值执行后续步骤。

第二轮迭代会将(6,6)这一组账户对加入到结果集中，新一次的迭代没有结果产生，而改变阈值为0.32后，执行新一轮迭代依旧没有结果产生，此时迭代结束，最终产生了(3,3),(4,4),(5,5),(6,6)这四组账户匹配结果。

尽管上面对本发明说明性的具体实施方式进行了描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。