大数据实体识别相关技术研究.doc

大数据实体识别相关技术研究
摘 要:爆炸式增长的信息量带来严重的数据质量问题。实体识别是数据清洗的一项关键技术,用以识别存在不同形式的同一对象,或区分同一形式的不同对象。介绍了实体识别相关技术,阐述了实体识别技术过程与方法,并实体识别问题可以阐述为将数据源集合D的记录集合R划分为[R′], [R′]中的每个集合与集合E中的物理实体一一对应。因此实体识别算法的输入是R,输出是经过解析的记录集合[R′]{r1,r2,…,r|E|}([R′]是E的不相交子集集合,[R′]所有集合的并集为E)。
2 大数据实体识别过程
大数据实体识别过程为:首先对大数据进行分块预处理,以提高识别效率。然后对分块处理后的数据进行相似关系计算并匹配,匹配成功的数据为同一实体。实体识别过程如图1所示。
预处理阶段
预处理阶段是实体识别过程的关键阶段。在实体识别过程中,一般将实体对逐一比较。假设有大小为x和y的两个数据集需要匹配,则要进行x*y次元组比较。但在大数据环境下,这样比较非常耗时,计算代价高。因此,在实体对比较之前,为避免进行笛卡尔级别运算,提高实体识别效率 ,根据某种知识或规则将数据分成规模更小的数据块(Block),只在块内进行数据比较,这种方法统称为分块技术(Block Technique)[3]。 固定分块方法
最早的分块方法是固定分块方法(Fixed-Sized Partition)[4],按照固定大小将数据分块,每个元组只能插入到一个块中。固定分块方法大大提高了数据处理效率,但缺点也非常明显:容易造成数据浪费及相关信息缺失。
相邻排序方法
为弥补固定分块缺陷,Hernandez & Stolfo[5-6]提出了相邻排序分块方法(Sorted Neighborhood),将元组进行排序,然后采用固定长度滑动窗口方式进行分块,如图2所示。但固定大小的滑动窗口会导致不相近的相似元组不能分到一个块中,因此Yan等[7]提出了根据元组相似度改变滑动窗口大小的分块方法。根据相似元组多少改变滑动窗口大小,这样保证了每个块中包含全部的相似度高的元组。
Canopy聚类方法
数据分块可以看作是將相似元组聚类到一起,因此可使用聚类算法进行分块。大多数聚类算法复杂度高,但分块方法需要低计算复杂度且高速的聚类方法。因此,针对分块特点,Han等[8]提出了Canopy聚类算法:首先将数据集中的每条记录都映射到空间中,通过距离函数distance(x,y)快速计算键值距离,任取记录中的一点并建立新的块,将与该点距离小于一定阈值的并入到块中,删除距离远的点。通过不断迭代重复,将元组插入到不同块中,直到距离大于一定的阈值,但该聚类方法对聚类中心的选取依赖性较高。
基于映射的分块方法
Jin等[9]提出了一种基于映射的分块方法,其基本思想是利用String Map算法将数据字符串映射到多维空间上,这样可以保留字符串之间的原始相似度,然后将相似度大的对象插入到相同类中生成块[10]。这种方法计算复杂度较高,因此在该算法的基础上提出了基于double-embedding的索引技术[11],将映射到多维空间的对象通过FastMap算法映射到更低维度的空间,最后利用KD-tree和近邻相似度方法结合抽取对象从而生成块。
相似匹配阶段
实体进行分块后,便对块中数据进行实体匹配以达到识别效果。数据通过相似匹配方法将元组对分为匹配和不匹配,匹配的元组代表同一实体,不匹配的为不同实体,相关技术介绍如下。
基于阈值方法
基础的实体识别方法是设定阈值,将元组对比较向量中的每个相似度值简单相加得到总的相似度,再与设定的阈值进行比较,根据比较结果判定元组对是否匹配。该方法缺陷显而易见,首先是属性值的简单求和并没有考虑到属性的重要度,因此有很多根据属性重要度设定权重计算相似度大小的改进方法;其次是求和过程中每个单独相似性信息丢失了,因此研究出复杂的实体分类器,通过单个相似度进行实体识别,这种方法对阈值设定的专业度有很强的依赖性。
基于概率方法
通过概率方法可将实体识别问题作为贝叶斯推理问题[12]。设定不匹配U类和匹配M类,x为比较向量,通过判定规则将x划分到U或M类中。当每个类的密度函数是已知时,x在U类和M类中的密度函数是不同的,这样实体识别问题就成为一个贝叶斯推理问题。
判定规则描述如下:
x为元组对<r1,r2>的一个比较向量,如果匹配类M的概率大于U的概率,则x被分到M中,否则分到U中。
利用贝叶斯定理可表示为