找工作那些事-by面试

DissertationSubmittedtoHangzhouDianziUniversityfortheDegreeofMasterResearchonRelatenessComputingbetweenChineseWordsandbetweenShortTextsbasedonWikipedia GaoFei Prof.ChenZhiqun性和使用说明性本人郑重：所呈交的，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明的内容外，本不含任何其他个人或集体已经或撰写过的作品或成果对本文的研究做出重要贡献的个人和集申请与资料若有不实之处，本人承担一切相关责任作者签名 日期：年月使用说本人完全了解杭州电子科技大学关于保留和使用的规定，即：研究生在校攻读期间工作的知识单位属杭州电子科技大学本人保证毕业离校后，或使用工作成果时署位仍然为杭州电子科技大学。学校保留送交的复印件，允许查阅和借阅；学校可以的全部或部分内容，可以允许采用影印、缩印或其它保存（在后遵守此规定）年月日年月日Withthecontinuousdevelopmentofnetworkinformationtechnology,textasanimportantcarrierofinformationthenemergeinalargeamount,sotheautomaticprocessingoftext eanimportantfieldofinformationprocessing.Wordsandtextcorrelationcomputingastextinformationprocessingoftheimportantbasicresearchsubject,moreandmorebeconcernedbydomesticandforeignresearchers,whichalsoplaysacriticalroleinmanyNaturalLanguageProcessing(NLP)applications,suchasinformationretrieval,textclassification,wordsensedisambiguation,machinetranslation.InordertoimprovetherelativeNLPtechnology,theresearchofwordsandtextrelatednesscomputingisofgreatworth.Onsemanticrelatednesscomputing,thisprpresentsthewordsrelatednesscomputingbasedonChineseWikipediaclassificationsystemandlinks.Mostoftraditionalstudies,themainmethodisbasedontheHowNet.ThispruseWikipedsemanticresources.Fromtheclassificationlevel,theexplanationlinksoftheconceptandthewordrelatednessofcomprehensiveysis,andcombiningwiththevectorspacemodelandSimilarityofinformationretrievaltechnology,thisprconstructacorrespondingclassificationgraphandsemanticvectorofrelatedwordstowordrelatednesscomputing.Semanticcorrelationofwordscanbeusedforthecalculationofthecorrelationbetweenthetext,especiallyforshorttext.Shorttextasakindoftext,ithastheuniquecharacteristicsofthelanguage,ashorttextusuallyareveryshort,soithasverysparsesamplecharacteristic,anditisdifficulttoaccurayextractthelanguagefeatures.Thisprconsideringthestructureoftheshorttext,andaccordingtothevalueofwordsrelatedness,presentstheumsequencealgorithmanddynamicweightalgorithm.OnWikipedia,thisprextractthelinks,classificationsystem,andredirectlinkssemanticresourcesetc.ExperimentusingthetestsetWordSimilarity-353andtheheadlinesshorttextcorpus,testthewordsrelatednessalgorithmandshorttextrelatednessalgorithm.Theexperimentalresultsshowthatthealgorithmshasacertainfeasibleandeffective.Finally,asummarizationonthemainworkispresented.Theunsolvedproblemsinwordandshorttextrelatednesscomputingarealsoyzedandconsideredasourfutureresearchwork.Keywords：classificationgraph,semanticvetor,dynamicweight,Wikipedia,NaturalLanguageProcessing,correlation 第一章绪 课题研究背景与意 课题研究现状及发展趋 本文的研究内 本文的组 第二章相关工作及研究进 2.1百科简 2.2百科在自然语言处理中的应 词语及文本相关度计算研究现 词语相关度计算方 文本相关度计算方 基于百科的相关度计算方 相关度评测标 本章小 第三章基于中文百科分类体系和文档的词语相关度计 基于分类体系的相关度计 最短路径 深度路径 基于文档的相关度计 3.2.1向量 3.2.2距离 分类图与文档相结合的相关度计 3.3.1分类向 语义向量的构 测试实例及其分 本章小 第四章基于百科的短文本相关度计 传统相似度计算方 最大序列算 相关度特征矩 最大匹配组合选 动态权值算 动态组块概 权重动态分 测试实例及其分 本章小 第五章实验及性能评 实验环 中文百科语义资源整 中文百科的内容结 语料与结构化整 百科分类和结构的抽 词语相关度计算实 Spearman等级相关系 词语相关度结 实验分 短文本相关度计算实 短文本测试 最大序列方法计 动态权值方法计 实验分 本章小 第六章总结与工作展 本文的主要研究工作及成 存在的问题及对将来工作的展 致 参考文 附 第一章课题研究背景与意一个信息化的社会，即使在声音、、图像等信息数据大量增尤其在计算机网络不断普及的今天，文本信息更是呈现出式的增长，而在这个信息网络所拥有的巨大的数据流中，大约有80%的数据以非结构化文本的形式存在着[1]。近些年，尤其是网络上大量短文本的出现，如、即时、标题、博客评论、跟帖、通过网络转发机消息等，成为了新起的文成为当前信息处理领域迫切的需求。文本信息自动处理可以应用在很多领域，如机器翻译、自动、信息检索、文档分类、信息过滤、问答系统等。特征，单条短文本长度一般都非常短（如每条限140字，微软MSN消息允许400个字符，因此样本特征非常稀疏，很难准确抽取有效的语言特征，难以充分挖掘与利用特征之间的关联性。因此词语和短文本相关度计算是非常具有性课题研究现状及发展趋长期以来，由于一些性的原因，在中文信息处理领域，研究者在应用相相似的概念之所以总是被，是因为它们的概念本身既存在着联系又存在着区“度，可以用这两个词语在同一个语境现的可能性来衡量。与此同时，两个语关的词经常是“讲师、课堂、”等；另一方面，两个相关的词往往不一定具目前，已有很多方法可以进行词语与词语之间相关性的计算，如路径的计算方法、信息量计算方法、特征计算方法、网络的计算方法等。这些方法都是利用34方法中，词语之间相关性的计算依赖于人工构建的具有一定逻辑结构的知识库词典主要包括英文的ordNet5]领域的6以及中文《知网（t）[7]和《同义词词林》[8]等。这些知识库词典在词语之间的相关性计算中被广泛的2010应用以上两种资源来进行相关性的计算很难达到一定的覆盖度。应用网络资源的词语相关度计算，虽然可以达到一定的覆盖度，但是由于网络信息的复杂性以及可利用性等因素的影响，计算结果也很难令人满意。产生很大的影响。应用词典进行的词语相关度计算中，由于人工构建等因素的影响，很难达到一定的覆盖度。近些年，国外很多研究把百科融入到自然语言处理中，取得了很好的效果，百科由于其自身作为百科知识库的特点，它的丰富程度以及覆盖度可以将其充分利用到自然语言处理诸多领域中。相似比相关相似比相关判原始文式化表式化表原始文1.11.1系进行深入的思考，目前绝大多数的文本相关性计算方法都要借助相似性的比较因此在强调文本之间关联程度而非相似程度的比较中难以取得很好的计算效果。例如，对于两个短文本“电脑走进了农村孩子的课堂，老师第一次使用PT本片段做出错误的判断，因为它无法挖掘和利用文本中所蕴含的语义信息。在对文本的形式化表示时，从文本的语义层面出发，尽可能挖掘出表达该文本涵义的特息尤其对于特征值较少的短文本1.2本文的研究内文采用外部知识源百科（Wikipedia）[9]来进行相关度计算。本文主要研究和探讨了基于百科的词语以及短文本相关度计算方法，本课题重点开展以下几位和语义单元，词语之间的相关度计算是研究词语相互关系的内容之一。本文将中文百科作为语义资源，利用其分类层次、概念文档之间的来计算汉语词语之间的相关度，在借鉴空间向量模型[43]和谷歌相似度（Similarity短文本相关度计算方法：是本课题研究的重点之一，本文主要面词语相关度计算的基础上，将它应用到短文本相关度计算中来。提出了最大序列算法和以及基于组块的思想，提出动态权值方法来计算短文本相关度。中文百科数据整理：百科是目前最丰富的百科知识库，具有动态性和及时性。百科提供的页面文档以及文档之间的丰富，还有编辑者编辑的分类层次、重定向页面、消歧页面，利用这些结构可以反映很强的语义关联关系文通过中文百科提供的L文档经过繁简体转化抽取能够表达语义关联关系的文档信息、分类层次信息、重定向条目等资源，分别以数据库和文本文件的形式。本文的组第一章绪论：简单介绍了本课题的研究背景、意义、现状、内容等，并同时介绍了本的研究内容及各章节的安排。第二章相关工作及研究进展：首先介绍了百科以及它的文档和分类组织形式。其次介绍了百科在自然语言处理中的应用。最后主要介绍了国内外关于词语以及短文本相关度计算方法、应用百科在相关度计算的常用方法以第三章基于中文百科分类和文档的词语相关度计算：根据百科的结构，分别从百科的分类层次和文档层次以及两者结合出发，首先借鉴传统的应用于词典中相关度计算方法，利用百科分类体系，实现了最短路径方法和深度的路径方法。其次根据百科文档体系，构建向量以及利用距离来分别进行相关度的计算。最后通过百科分类和文，构建分类向量以及相关语义向量来分别进行词语相关度的计算。第四章基于百科的短文本相关度计算：针对传统方法应用于短文本相关度计算中的不足，主要利用基于百科的词语相关度计算结果，提出了通过 实验及性能评价：首先整理面向语义的百科语料资源。其次在对词语相关度评测方面，利用WordSimilarity-353[48]测试集进行各种方法的相关度计算，并采用Spearman等级相关系数[49]来分析和评价。最后在对短文本相关度评 自然语言处理中，研究者利用不同的挖掘技术应用百科取得了丰硕的成果。近些年已有不少研究者利用百科进行语义上的相关度计算，并取得了一定的成果。本章对百科以及百科在自然语言处理中的应用做了简单介绍，接着重点介绍了词语和短文本相关度计算的一些方法，引出利用百科作为语义2.1百科简Wiki技术，Wiki系统是一种有效的协作式知识编辑工具，这意味着任何人都可以编辑百科中的任何文章及条目。百2.1随着百科的快速成长，它吸引了越来越多的编辑者参与更新和，2.1图2.1百科覆盖了广泛领百科是目前最大的免费的知识库。由于百科是采用wiki技术构建的，用户可以非常容易地实时去编辑，因此使 百科作为一个百科知识，覆盖范围广由图2.1可以看出百科几乎覆盖了各个领域方方面面的知，准确度高：Giles[10]，百科在准确度上很接近百科全书Encyclopedia现，而传统的辞典构建的最大就在于很难覆盖新的术语。然而百科可以结构化强：百科具有多样的数据结构。百科中每个条目都有一个唯一的URI作为的资源标识符，所以每个文档页面的URI可以有效的解决一词题。百科除了非结构化的文本之外，它还包括一些比较重要的密集的结构化数据。如结构、层次化的分类等结构化数据。图2.2展示了一个基本的维图2.2百科基本的文档元以上这些特点使得百科可以做为一个非常丰富的语义数据资源，应用到自然语言处理中。百科拥有数百万的百科全书解释页面页面分自然科文历哲会科人文的基本组成单元，而且百科按照概念分类和语义关系建立了分类索引，在解释页面之间添加了丰富的表达语义关系的。百科每篇文档描述一页面分自然科文历哲会科人文世世界数函概抽形而上思物理化图2.3百科分类层次示百科解释页面之间的超级反映了概念之间的关系（如图2.4除了这些概念解释文档和分类，百科百科包含了重定向页面来表示词语之间布布宜诺斯利世界足先阿根守门马拉多足世纪最入齐达2006界界外图2.4百科文档体系示2.2百科在自然语言处理中的应在自然语言处理的相关研究和应用中，百科资源可以被用来作为一个大规模的语料库，同时也可以作为一个包含了世界知识的语义资源，而且在一定程度上可与人工构建的语料库或语义词典相媲美从百科的结构和功能上出发Zesch1]等和e12]等分别分析了百科作为语义知识资源的可行性。rube等从 百科的分类体系出发，通过构建分类图来计算语义相关度，并且证明了的飞速发展，百科不断得到完善，越来越多的研究者将百科应用到自然词义消歧：虽然计算机不能够全面的理解自然语言，但是通过各种方法区分词语的确切含义（词义消歧）还是相对比较容易的。文本中词义的消歧任务一般由于语义词典中通常定义了词语释义以及解释或者关联关系，所以可以为区分不同的释义提供帮助。基于百科可以进行有效的歧义消解，因为百科包含了专门的消歧义页面，消歧义页面中对一词多义的概念进行区分描述，然后通过消歧释页面中人工标记的指向正确的消歧义项。angu等13通过百科的消歧释页面生成每个义项的文档向量，分别与根据词的上下文生成的文档向量，利用向量方法计算文档相似度来进行选择消歧义项。命名实体识别：百科中由于包含着大量的人名、地名、组织名称等概念以及它们的解释文档，因此百科被认为是可用的、最大名实体资源。大上是无法与百科相比的。同时随着百科的不断更新，很多重要人物、地理位置、事件以及等都会不断被更新扩充。将百科应用到命名实体识别、词义消歧等自然语言处理的相关研究和应用中有着巨大的优势。Cucerzan等[24]从百科的文档标题、重定向页面、消歧义页面、词语等位140万个命名实体。语义扩展：在信息检索领域中，大多是基于进行检索，怎样描基于语义信息的检索还有很大。在检索词扩展等方面百科可以达到很好的效果，因为百科的优势在于它有着大规模的可扩展的覆盖以及反映语义关联关系的文档Milne等[18]根据百科的文档间的关系将某个概念的所有扩展的提供给检索引擎，实现检索的语义扩展。文本分类：百科中包含了上百万的解释页面文本语料资源，可有效的用背景知识。传统的文本分类方法一般都是通过获取文档中的高频词语，然后将对应文档转化为一个法无法考虑文档中具有很强语义关系的同义词、近义词等。Gabrilovich和Markovitch提出了明确语义分析（ESA）[20]方法，利用百科在文本分类中进 和（ 大量编辑者提供更新以及完善，从而保证了比较高的度。Buscaldi和Rosso等在他们实现的问答系统QUASAR[22]中，从不同种类的问题出发，然后利用词语及文本相关度计算研究现离）的计算。词语距离是一个[0)0。对于待比较的两个词语wawbSim(wawb,其词语距离为)

其中是一个可调节的参数。这种转换关系并不是唯一的，在这里也只是给 len(LSOw,w Sim(w,w)log a

len(wa)len(wb)aLSOw,w表示词语wa和wbaLeacock和Chodorow等[26]词语相关度计算方法中采用一种深度Sim(w,w)

2depth(w)其中depth(wWordNet基于信息量的计算方法，是利用词典（WordNet等）（InformationContent）作为特征参数的一种相关度计算方法。此种方法最早由Resnik等[27]这种方法利用两个词语wa和wb在词典中的最小公共父节点的

最小父节点的信息量代表了词语wa和wbIC多，表示两个词语之间的相关度就越大，反之信息量IC越少，两个词语之间的相vec(wa)vec(wb)vec(wa)vec(wb基于统计特征的相关度计算方法，是建立在构建相关词向量的相关度计算基础之上的。通常都是在大规模语料中统vec(wa)vec(wb)vec(wa)vec(wb

(w,w)

其中vec(w)度的大小。对于两个词语wa和wb，在搜索引擎中分别以wa和wb、wa、wb作为搜在词语的相关度计算方法中，充分利用各种资源来进行计算可以达到一定的效果，单纯采用其中法很难达到预期的效果。杨冬青教授31基于统计分析词语相关度计算方法中，不仅从统计的角度出发，而且考虑词语之间的距离。作者认为一段话中同时出现的单词才有一定相关意义的存在，并且它们之间基于这样的考虑，建立词语相关度的算法如下：ForDiForSjSim(w,w)Sim(w,w)21/Dis2(w,w wx,wySjwx其中Dis(wx,wy)表示两个词语之间有几个单词的间隔。该算法中，为了更加2再加上新值，词语共现模型32]是基于统计方法的自然语言处理研究领域的重要模型之一。根据词语共现模型，如果几个词语经常在同一单元窗口同出现，那么它们在一定程度上可以表达该文本的语义信息，这是因为作者一般倾向于通过在不同句子中重复那些词语来强调文本。因此，通过词语共现概念与集共同组“护士都是且在同一窗口单元中出现的次数教多（手术医生、护士）为该文档的一组词语共现，由此可推断这是一篇关于医生做手术的文章。在信息检索领域中，这种方法经常被使用。一般信息检索系统中，通常需要（ordist,n维向量来表示，最后通过文档向量和查询向量的相关度来检索出相关文档。共同的词语，甚至没有共现词语。如“苹果公司刚发布了5”和“ipad2的目前在基于语料库的相关度计算方法里面最具代表性的就是LatentSemanticysis（LSA）[34]方法和 是一 线性相关模型，它认为文本中词语与词语之间存在某种潜在的语义Space异值分解（SVD。首先根据语料库构建矩阵A，接下来通过矩阵的奇异值分解把AA=U*S*VS是一个对角矩阵，它由奇S中的最小值来降低矩阵的维数，最后根据已HALLSALSA方示，假设这个语义空间是nn的矩阵，那么某个词语就可以用一个2n维的向量来LSA方法[33]。LiMcLean等[33]给出了一种综合的短文本相关度计算方法。该方法基于词WordNet，针对一些包含基于百科的相关度计算方（ordNet化信息，且在背景知识的覆盖程度和语义关联方面也不是很好。而像知网定的限制，很难覆盖到足够丰富的概念以及各种语义关联关系。百科是目前最丰富的百科知识库，近年来国外很多研究把百科融入到自然语言处理中，Zesch和Gurevyc[11]利用百科的文档和分类体系分别构建了文档图（ordNet这就意味着将百科的文档及分类体系用作语义上的知识资源可以代替哪在语义相关度计算研究中，Strube和Ponzetto[12]是最早利用百科作为语义知识源的。他们将传统上一些经典的相关度计算方法与百科相结合，并且对比分析了百科和WordNet在语义相关度计算上的差别，也在不同的测试集上进行了实验。实验结果显示百科在词语覆盖度大的测试集上的表现优于在WordNet上进行的相关度结果，而在侧重反映语义的测试集上表现较为逊色。维于百科解释文档实现对文档向量进行语义扩展的法，可以实现对单个表示成一个特征的向量，通过计算词语在文档中的频率以及在这个语料库中的频率来给每个词语赋予权值，最后通过计算两个文档向量在空间中过机器学习的技术将词语或者文本到一个百科相关概念序列，然后使用HassanMihalcea[37]提出了突出语义分析（SSA）ESA方法的一种改进该方法通过从百科中收集突出的概念以及概念的解释文档，N篇文N(PPNSim(w,w)

y

P2 y y来实现相关度的计算经过试验结果显示SSA的方法要优于基于文档向量的ESA在短文本相关度计算方法中，Banerje和Ranathn等8等利用百科的解释文档进行短文本相关度的计算。该方法通过收集百科解释文档，然后Lucene3且只利用了百科中的解释文档。综合利用百科中的语义结构信息可以获得更好的效果。目前国内利用百科进行相关度计算的研究较少没有形成一定的规模李赟等40根据百科的分类层次以及文档体系构建了分类图和文档图，通过概念之间的路径信息进行了概念之间的相关度计算。且作者通过挖掘百科文档间相互的关系抽取了近40万对语义相关词，并计算了语义相关度，但是该方法处理比较麻烦，只是单纯利用了文档结构，没有利用到百科类别信息。刘军50]等利用百科的分类系层次，进行倒排索引，然后通过余弦形似度来计算两个词语的语义相关度。等41]从百科中抽取相关概念，并采用统计规律和类别信息想结合的方式来计算词语之间的相关度。并且作者通过建立语义相关概念集合，对短文本向量进行扩展，来实现短文本之间的相关度计算。王锦51]等从百科中抽取概念的类别信息，然后利用这些类别信息来实现对文本特征的扩展，进而计算文本之间的相关度。这些方法都只是直接的利用百科中的分类或者文档体系，并没有进行深入挖掘百科中语义信息，比如解释文档中段落位置及分类层次中概念关系递减等语义信息。的0.88~0.95。WordSimilarit-3342集是应用最广泛的一个，它包括353对英文词对，每个词对由13名-16名对它们的相关度进行打分，得分的平均值作为每个词对的相关度。本文在评测词语之间的语义相关度上采用该测试集。目前，在评测短文本之间的相关度上，没有相关的测试集，本文通过从网络上搜集相关的标题，并经过人工整理进行分类来作为短文本测试集。本章小本章介绍了百科以及它的文档和分类组织形式。其次介绍了百科在方法、应用百科在相关度计算的常用方法以及一些相关度评测标准。为本文第三章基于中文百科分类体系和文档的词语相关用百科作为外部语义知识资源在词语相关度计算中的优势，本章着眼于基于中文百科分类体系和文档的词语相关度计算方法的研究，提出了基于分类体系的相关度计文从中文百科分类体系中抽取分类关系来构建了分类图。由于百科的分的基于语义词典的词语相关度计算方法移植到应用百科来计算相关度的方法12艺术体12艺术体无体体文人类社页面分3453.1（概念.1概念“无声“艺术体操”通过向上不断遍历，可以找到它们的最小公共父分类O，如“人类社会”是它们的公共分类节点。基于这种思想，利用基百科采用最短路径的方法来进行相关度的计算。对于待比较的两个词语wa和wb，在分类图中定位其类别节点并进行广度优先遍历，直到找到两个类别的最近公共节点，遍历路径长度分别记为Len(wa)Len(wb)

len(wa)len(wb

log(len(wa)len(wb

其中log(len(walen(wb深度路径 (w,w)Sim(w,w)

其中depth(wpub)depth(wa)depth(wb)分别为最近公共节点、两个概念节点基于文档的相关度计人。其中最为著名的应用该模型的检索系统是Smart系统[44]。下面是一些VSM模型的基本概念。（erm当档的内容被简单地看作是它含有的基本语言单（字词、词组或者短语等）所组成的集合时，这些基本的语言单位统称为项。因此文档可以用项集（ermist）表示为1,2, ,n)，其中n是项，且1kn。eight： ,Tn)，项常常被赋予一定的权重

，表示它们在文档中的重要程度，即 Tn,Wn)，简单记为DD(W1,W2 ,Wn)，这时可以说项Tk权重为Wk，且1kn Tk在文档中既可以重复出现又应该有先后次序的关系分析起来仍有一定的难度。为了简化分析，可以暂不考虑Tk在文档中的先后顺序并要求Tk互异（没有重复。这时可以把T1,T2, ,Tn看成一个n维的坐标系，而W1,W2, ,Wn为相应的坐标值，因而DD(W1,W2, ,Wn)可以被看成是n中的一个向量（如图3.2中的D1，D2，因此可以称D(W1,W2, ,Wn)为文档D的向量表示。相似度（arity12之间的内容相关程度（ofRelevan常常用它们之间的相似度(1,2)M，可以借助于向量之间的某种距离来表示文档间的相关度，常用向量之间的内积来计算，公式如下：nSim(D1,D2)w1knknnw1k 22k 22kk

3.2θ3.2文档的向量空间模型（VSM）Sim(D1D2整个百科的结构主要围绕着概念的解释文档构成的百科的每一个词档之间的关系可以充分反映两个目标词语的语义相关性。接关系中得到词语文档的条目，针对两个词语wa、wb，可以得到它们的文（3.6pageb[(w21,wt21),(w22,wt22)……(w2n,wt2n

其中w表示文档中的条目，wt为此条目在该概念文档里的频率pageapageb，可以通过计算两个向量的余弦相似度来获得两个词语的相关度。本文称这个方法为Simlinks，如下公式：w1k (w,w) ( w2w2kk

距离法谷歌距离[45]是一种基于搜索引擎[46]的词语相关度衡量算法。该算法主distance借鉴距离计算方法，可设计任意两个词wa和wb的基于百科NGD(w,w)log(max(|Wa|,|Wb|)log(|Wa