读书笔记：大数据清洗技术
作者：哈尔滨工业大学博导王宏志
第三章 实体识别
? ? ? ?上一节主要讲了串行实体识别方法，虽然提出了Gcluester聚类方法减少了相似度计算的数量，但本质上依旧没有解决可拓展性问题，所以本节讲到了能够有效提高可拓展性的并行算法，从两个角度来研究，基于MapReduce的大数据实体识别算法和基于Hyracks的实体识别。主要讲基于MapReduce框架提出的新的EIBM算法，其主要想法是定义了一种新的相似度度量来降低相似度计算量，再解决A与B，B与C的传递性问题，一共分为四个阶段。
基于MapReduce的大数据实体识别算法
一. 初步聚类算法
? ? ? ?想法来源是我们发现属于同一个实体的不同记录必定存在部分相同或相似的属性值。所以从相同属性值入手，通过为每个属性的属性值构造索引表的方法，对可能相似的记录进行初步聚类。可以大大减少冗余计算和记录比较的次数。下图为初步聚类的具体流程。
? ? ? ?用实例进行说明：
? ? ? ?这个例子中我们在初步聚类阶段使用一次MapReduce对其Collaborator这一属性进行排列。我们可以由结果清楚的看到具有同一属性的实体共享同一个索引，在后续识别过程中，只需要对每个属性表中同一属性值下的实体分别进行识别即可。
二. 实体识别算法
? ? ? ?这个阶段总共分为三个步骤分别是抽样，阈值计算和实体识别。前两个步骤是准备工作，主要是为了之后实体识别所服务的，阈值就是进行实体识别计算时的零界点。
1. 抽样
? ? ? ?考虑到大数据体量大，难以在整个数据集合上计算阈值，故在通过机器学习 求得阈值前，需要从大数据库中随机抽取用于学习和对照的样本集合，将其输入机器学习算法中。这里采用的抽样方法是基于动态淘汰策略的抽样算法DESampling：通过维护一个采样池SamplingPool，不断更新池中的元素直到满足采样条件为止。样本要求：从N个元素中抽取k个元素，k个元素中必须含有m对相似实体，其中N为一个很大的未知量。
? ? ? ?其中活跃度主要描述的是该元素相对于这个实体集的相似程度，因为活跃度最低的元素就说明他在每一次挑选相似实体时都没有被选上，可以认为与其他所有元素的相似度不够，可以看作奇异值，替换掉以此来不断更新Samplingpool，增加Samplingpool中所有元素间的相似性。
2. 阈值计算
? ? ? ?阈值获取的目的是在实体识别阶段判定实体对是否相似。基本思想是将样本数据表中计算的相似对相似度标注为高相似度值和低相似度值，构造为二维空间上的两个点集，通过求取两个点集最小覆盖圆对点集进行覆盖。
- 将一维相似度点转化为二维离散点（x=t+rand(), y=t+rand()）。（rand()为随机函数，相似度值加上随机值。）
- 形成高相似度集HSET和低相似度集LSET。
- 计算两个最小覆盖圆的圆心与半径。
- 根据两圆的位置关系求取所需阈值。
我认为这里不直接使用平均相似度的原因有：
- 怕有特别偏的值的影响
- 加上rand()函数可以缓解抽样过程中的随机性因素。
根据两圆的位置关系求取所需阈值主要是依据两个最小覆盖圆间的关系：相离则取两个最小覆盖圆间中点，相交则取其相交弦和圆心连线的交点，相切则取其切点。
?3. 实体识别
?????? 在实际应用中，不同属性对实体识别的影响不同，因此应当为每个属性设定不同的权值，以有效区分每个属性对实体描述的影响程度。对权值的设定，可以根据领域知识人为设定，也可以通过机器学习的方式学习得到。在识别过程中，对每个属性索引表中属性值相同的实体进行扫描，对该位置的任意两个实体均执行一次匹配过程。而后通过实体对共同出现的次数和单独出现的次数计算该属性的相似度。最后根据属性权值计算实体对的全局匹配相似度，通过与阈值大小比较判定是否相似。
- EntityCount过程（MapReduce过程）
输入：某属性的索引表
输出：每个实体和实体对及其出现的次数
- EntityGather1过程（MapReduce过程）
输入：每个实体及所有实体对出现次数
输出：所有第一个实体及其实体对出现次数
?
- EntityGather2过程（MapReduce过程）
输入：所有第一个实体及其实体对出现次数
输出：所有实体对中两个实体出现次数和实体对共同出现次数
计算实体对相似度=实体对出现的次数/两个实体分别出现的次数
计算整体相似度=各属性权值做加权平均
- ComputeSimilarity过程(MapReduce过程)
输入：阈值以及各个属性的权值（该例中为0.4）和实体对
输出：相似实体对及其相似度（不是输出相似度最大的，而是要全部与阈值比较）
l例如：AB=1/(2+2)=0.25
? ? ? ?这就是实体识别这一阶段的三个步骤，实体识别阶段也是最核心的部分，一共用到了4次MapReduce流程，加上初步聚类阶段的一次一共是5次MapReduce，能够很好地切分数据，加快数据运算，加强算法的可扩展性。
三. 实体划分算法
? ? ? ?通过实体识别阶段的输出得到了表示实体间相似关系的实体对以后，实体划分是在对实体对进行关系收缩，得到一个代表统一实体的实体簇，解决传递性问题。
? ? ? ?N(v)表示顶点v在图中的邻居节点集合，并且v∈N(v)。参数λ由人工设定。λ越大实体之间需要满足的划分条件越强，相似度要求越高，精确率提高，召回率降低。如果满足下面这个等式，则将a和b收缩为一个定点，直到没有边满足条件为止。我们也给出一个例子：
四. 概率计算算法
? ? ? ?这一阶段能够快速地给出每条记录属于其所在实体分类地可能性，主要是起到一个验证地效果。
? ? ? ?本节提出的基于MapReduce框架的面向大数据实体识别算法EIBM，通过使用属性索引表快速定位在某个属性上相同的实体，大大降低了相似度计算量，提高了识别效率。同时，基于图聚类的思想通过实体划分算法对相似实体对进行聚集，显著提升了算法的精确率。在真实数据集和人造数据集上的大量实验证明，EIBM算法具有很好的精确率，能够高效处理大数据算法。