[发明专利]一种基于关联矩阵的不确定数据连接合并算法

说明书

技术领域

本发明涉及计算机软件技术领域，具体地，涉及一种基于关联矩阵，确定数据表的连接合并规则，解决不确定数据表的连接合并问题的算法。

背景技术

随着互联网技术的蓬勃发展，我们已经进入了大数据时代，要从海量的数据中提取出有价值的信息变得更加复杂。在网络中存在许多看似相互独立的数据，实际上他们都是对同一类对象从不同方面的描述，例如同一个人或同一件商品在不同的网站，由于网站关注的角度不同，其存储的关于人或商品对象的属性信息也不完全相同。如果能够找到一种方法，整合多个不同来源且数据项含义不明确、数据对象不明确的数据，得到数据描述对象的详细信息，则对人们了解对象全貌有很大的帮助。

其中，不确定数据连接合并算法本质是在数据项含义不明确的数据表间找出关联记录，并将关联记录进行连接合并。对于多个不同来源且数据项含义不明确、数据对象不明确的数据表，要将各表中表示同一对象的记录合并在一起得到对象的全息影像，需要解决两个主要问题，首先如何确定数据表的连接合并顺序，避免可以进行合并的记录被遗漏；其次如何降低大数据应用场景下，表关联操作的计算复杂性问题，对于两个不确定数据表如果直接进行连接匹配计算量非常大，如两个维度分别为m维和n维的数据表，进行连接合并时需要进行m*n次属性值相似匹配。

发明内容

为了克服现有技术的不足，本发明提供一种基于关联矩阵的不确定数据连接合并算法，以解决数据项含义不明确、数据对象不明确的数据难以进行连接合并的问题。

本发明为解决上述技术问题所采用的技术方案是：一种基于关联矩阵的不确定数据连接合并算法，包括以下步骤：

步骤1：引入属性重要度，数据表中数据对象的某一属性的重要度越高则表示该属性对该类数据对象的区分度越大；计算数据表中各属性的重要度，找出数据表所有属性重要度的最大值；

假设对象r1{P₁,P₂}和r2{P₁,P₂}，对应的属性值分别为r1(p₁₁,p₁₂)和r2(p₂₁,p₂₂)，r1和r2表示同一实体时，记为：当对象r1在属性P₁上的取值p₁₁和对象r2在属性P₁上的取值p₂₁相同时，r1和r2表示同一实体的概率为同样

若说明属性P₁相对属性P₂对该类对象具有更大的区分度，则可以将条件概率作为属性P₁的重要度，记为

为了方便计算，我们可以采用以下思路来计算属性重要度：当r1和r2为不同的对象，p₁₁＝p₂₁相等的概率为P(p₁₁＝p₂₁|r1≠r2)，由条件概率知，P(p₁₁＝p₂₁|r1≠r2)与存在反比关系，因此属性P₁的重要度

针对数据表T＝{P₁,P₂,...,P_n}，P_i的取值为统计P_i中每个不同属性值的出现次数，如表1所列：

表1属性P_i的取值分布

由于同一数据表中存在同一对象的概率很小，因此在大数据表中可以认为每一条记录代表一个不同的对象，基于该假设，其值相等的概率为由于可得则属性P_i的重要度为：

由于此值范围较大，不利于后期记录相似度的计算，因此对其进行平滑化处理和归一化处理，得到：

其中W_{p max}表示数据表T所有属性重要度的最大值。

步骤2：确定数据表之间的关联度，并建立关联矩阵；

步骤201，采用杰卡德相似系数来计算属性相似度，并以此确定表间关联属性

杰卡德相似系数是衡量两个集合相似度的一种指标，设表T_i、T_j在某个属性上取值集合分别为PV_ia和PV_jb，它们的交集元素在并集中所占的比例，称为两个集合的杰卡德相似系数，即为属性值集合PV_ia和PV_jb的相似度：