实体识别关键技术的研究

博博博士士士学学学位位位论论论文文文实体识别关键技术的研究RESEARCHONKEYTECHNOLOGIESOFENTITYRESOLUTION黎黎黎玲玲玲利利利哈哈哈尔尔尔滨滨滨工工工业业业大大大学学学2015年年年3月月月国内图书分类号：TP311.13,TP393国际图书分类号：681.5学校代码：10213密级：公开工工工学学学博博博士士士学学学位位位论论论文文文实体识别关键技术的研究博士研究生：黎玲利导师：高宏教授申请学位：工学博士学科：计算机软件与理论所在单位：计算机科学与技术学院答辩日期：2015年3月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP311.13,TP393U.D.C:681.5DissertationfortheDoctoralDegreeinEngineeringRESEARCHONKEYTECHNOLOGIESOFENTITYRESOLUTIONCandidate:LiLingliSupervisor:Prof.GaoHongAcademicDegreeAppliedfor:DoctorofEngineeringSpecialty:ComputerSoftwareandTheoryAffiliation:SchoolofComputerScienceandTechnologyDateofDefence:March,2015Degree-Conferring-Institution:HarbinInstituteofTechnology摘要摘要实体识别在数据质量管理中起着重要地位。它是数据质量管理的重要研究方向。在一个或多个数据库中，同一个现实世界实体可能具有多种描述方式。实体识别的目的是识别出数据集中描述同一真实世界实体的元组。实体识别的结果可以在数据质量管理的其他阶段，例如数据清洗阶段和数据质量评估阶段，得到广泛应用。同一实体具有不同描述的问题在各种应用领域的信息系统中普遍存在。由于实体识别在数据质量管理中具有重要意义，人们已经开始了实体识别的研究。尽管现有的方法能够在很多应用中有效的识别实体，但是还存在如下的不足：1.当前的实体识别存在重名和异名的问题。重名是指描述现实世界不同实体的数据对象的名字相同，而异名是指描述现实世界中相同实体的数据对象的名字不同。目前实体识别的研究或是只解决了重名问题，即对名字相同的数据对象进行实体划分或是只解决了异名问题，即识别出名字不同但描述相同实体的对象集合，而缺少对一般情况（即重名和异名同时存在的情况）的考虑。2.传统实体识别方法往往是基于元组的相似性比较来获得结果的。它们假设数据集满足紧凑集性质，即指代同一实体的元组的相似度比指代不同实体的元组对的相似度更高。然而，在某些情况下，这样的性质并不成立，则传统的实体识别方法不能有效地识别实体。3.当前实体识别方法中所采用的相似性度量并没有考虑不同词之间所具有的相关性以及某些描述实体重要特征的词对识别实体的重要贡献。基于当前的相似性度量方法，往往不能得到有效的实体识别结果。4.目前的数据质量评估只包括一致性，时效性，完整性和精确性。然而通过实体识别的结果可以评估另一类数据质量问题，即指代同一真实世界中的实体的元组在各属性上的值存在冲突的问题。我们将该问题称为冗余数据上的实体描述冲突问题。当前尚无任何评估实体描述冲突的方法提出。综合上述分析，本文将以信息集成和互联网搜索为背景，研究数据质量管理中实体识别的关键技术，以最大化实体识别结果精确度，最小化时间复杂性为目标，研究基于图模型的实体识别框架、基于规则的实体识别算法、基于距离度量的实体识别算法和基于实体识别结果对数据质量的评估。本文的主要研究成果如下：(1)提出了实体识别问题中的异名和重名同时存在的现象，据我们所知，-I-哈尔滨工业大学工学博士学位论文这是首次在实体识别问题中考虑这两类问题同时出现的情况。本文提出了一种普遍适用的实体识别技术框架EIF，该框架通过将元组之间的相似性关系转化为图模型，从而利用图聚类算法解决实体识别问题。基于所提出的EIF框架，本文设计了识别论文作者的算法。该算法有效地利用了作者名字和合作者信息来实现同时具有异名问题和重名问题的论文集合上的作者识别。实验结果表明基于EIF框架的作者识别算法的结果精确度优于现有方法。(2)针对某些难以用元组相似性比较来识别实体的情况，提出了利用实体描述信息所建立的规则来识别指代相同实体的元组的方法。设计了实体识别规则的语法和语义，定义并分析了实体识别规则系统的独立性，一致性，完整性和有效性。提出了一种有效的规则发现算法和基于规则的实体识别算法，并对算法的正确性和复杂度进行了分析。最后提出了一个规则更新策略。在真实数据上的实验对所提出的算法的效率和有效性进行了验证。(3)以词作为描述实体的特征，分别为元组对上的实体识别和元组集合上的实体识别提出了两种基于词特征的距离度量和距离度量的学习算法。在算法中，通过将训练集中的元组或元组对转换成以词为特征的向量，利用学习算法计算出基于词特征的距离度量。在真实数据上的扩展性实验对我们所提出的度量学习算法的有效性进行了验证。(4)定义了实体描述冲突的数学模型。当实体识别结果的精确性不是100%时，提出了实体描述冲突的范围计算问题。为了解决这个问题，提出了四个基本操作并证明了实体描述冲突范围的计算问题是NP难并为四个基本操作提出四个近似算法，给出了近似比。提出了一个基于四个基本操作的计算实体描述冲突范围的框架。在真实数据和合成数据上对所提出的算法的有效性和效率进行了验证。关键词：实体识别；数据质量；质量评估；图聚类；度量学习-II-AbstractAbstractEntityresolutionplaysanimportantroleindataqualitymanagement(DQM).ItisalsoanimportantresearchareainDQM.Areal-worldentitymayappearinoneormul-tipledatabaseswhichmayhavequitedifferentdescriptions.Thegoalofentityresolution(ER)istoidentifytherecordsreferringtothesamereal-worldentityfrommultipledatasources.Theresultofentityresolutioniswidelyusedinotherstepsofdataqualityman-agement,suchasdatacleaninganddataqualityevaluation.Theproblemthatareal-worldentityhavequitedifferentdescriptionsisacommonproblemthatappearsinmanykind-sofapplicationareas.Becauseofitsimportance,entityresolutionhasattractedmuchattentionintheliterature.EventhoughexistingmethodscanperformEReffectivelyinmanycases,theseERapproacheshavefollowinglimitations.1.Therearetwoproblemsinentityresolution,called“tautonymy”and“synonym”.Tautonymyisdifferententitiesmaysharetheidenticalnameandsynonymisdifferentnamesmaycorrespondtotheidenticalentity.However,currentresearchfocusesononlyoneoftheproblems,withoutconsideringthegeneralcaseswherebothoftheproblemsmightexist.2.TraditionalERapproachesobtainaresultbasedonsimilaritycomparisonamongrecords.Theyassumethatrecordsreferringtothesameentityaremoresimilartoeachother,called“compactsetproperty”.However,suchpropertymaynothold,sotraditionalERapproachescannotidentifyrecordscorrectlyinsomecases.3.ThesimilaritymetricsusedbycurrentERapproachesdonotconsiderthecorre-lationbetweenwordsinrecordsandthemajorcontributionofsomespecificwordswhichdescribetheimportantfeaturesofreal-worldentitiesinentityidentification.Asaresult,theentityresolutionapproachesbasedoncurrentmetricssometimescannotachieveahighperformance.4.Currently,thestudyofdataqualityevaluationonlyincludesconsistency,currency,completenessandaccuracy.However,anewkindofdataqualityproblemcanbeevaluatedaccordingtotheresultofentityresolution,thatisduplicateddatahaveconflictingvaluesinthesameattributes.Wecallthisproblemas“theentitydescriptionconflict”.Asfarasweknow,theevaluationapproachofentitydescriptionconflictinduplicateddatahasnotbeenstudied.-III-哈尔滨工业大学工学博士学位论文Onthebasisoftheaboveanalysis,inthebackgroundofinformationintegrationandinternetsearch,focusingontheobjectivesofminimizingtimecomplexitiesandmaximiz-ingtheaccuracyofERresult,thisthesisinvestigatesthegraph-basedentityresolutional-gorithm,therule-basedentityresolutionalgorithm,theentityresolutionalgorithmbasedondistancemetricandthedataqualityevaluationalgorithmbasedonentityresolutionresult.Themaincontributionsofthisthesisareasfollows:(1)Theproblemsof“tautonymy”and“synonym”areintroduced.Asfarasweknow,thisisthefirststudytoaddresstheseproblems.Ageneralentityidentificationframework,EIF,ispresentedinthispaper.Inthisframework,th