资源描述：
《基于权重的马尔可夫随机游走相似度度量的实体识别方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第34卷/第1期/河北师范大学学报/自然科学版/Vol.34No.12010年1月JOURNALOFHEBEINORMALUNIVERSITY/NaturalScienceEdition/Jan.2010X基于权重的马尔可夫随机游走相似度度量的实体识别方法12111雷钰丽,李阳,王崇骏,刘红星,谢俊元(1.南京大学计算机软件新技术国家重点实验室,江苏南京210093;2.安阳工学院计算机科学与信息工程系,河南安阳455000)摘要:社会网络分析方法是一种量化的社会学分析方法,它将社会行动者映射为图的节点,社会行动者之间的关系映射为图的边
2、,然后利用图论的相关知识来解决社会网络的问题.在算法改进和系统实现层面展开数据挖掘在社会网络分析中的应用研究,在对基于图的实体识别方法进行深入研究的基础上,提出了基于马尔可夫随机游走相似度度量的方法,使其能够应用于有权有向图上的实体识别,并在此基础上提出可以处理多链接属性的实体识别算法.基于电信分析系统平台,重点研究和分析了上述算法的具体应用并在电信数据集上进行测试,应用结果表明上述算法的有效性和实用性.关键词:社会网络分析;数据挖掘;实体识别;马尔可夫;随机游走中图分类号:TP311文献标识码:A文章编号:100025854(2010
3、)0120026205社会网络分析是从社会学研究发展起来的研究社会结构的新方法和新技术,它是以“关系”作为基本的[1]研究单位.处于社会中的个人或者主体根据自己的需要通过自己的通信关系建立起不同的社会关系网络.通过分析这些通信关系,发现社会实体之间存在的相互依赖和联系,是典型的社会网络分析问题.将数据挖掘技术应用于社会网络分析中是目前的一个研究热点,已经有了一些典型的理论与应用成果.社会网络分析方法是一种量化的社会学分析方法.它将社会行动者映射为图的节点,社会行动者之间的关系映射为图的边,然后利用图论的相关知识来解决社会网络的问题.实体
4、识别是社会网络分析中的一个重要研究分支,其目的是在混淆的实体中找出其真正对应的实际实体.传统的实体识别方法根据描述实体的字[225]符串的相似度来表征实体间的相似程度,然后利用相似度度量进行聚类.而目前关于实体识别的研究兴趣主要集中在使用链接或者关系结构来提高实体识别的精度,其出发点主要是:不仅考虑实体的属性之间的相似度,还考虑到与其相连的其他实体对其的影响.文献[6]扩展了基于属性的相似度,既考虑了实体的属性,又把实体之间的链接关系考虑在内.该方法虽然考虑到链接可以增强实体识别的准确度,但没有考虑新识别的实体对未识别实体带来的影响.基
5、于此,文献[728]提出了协同实体识别的思想,其具体做法是在聚类过程中将节点属性、链接属性以及链接结构等因素作为相似性衡量标准来挖掘图结构中数据实体.还有一些研究者采用概率模型来进行实体的识别,基础性的工作是Fellegi和Sunter在继承NewCombe[9]工作的基础上完成的.文献[10]提出了基于NaÇveBayes的混合模型来进行重名的分析.文献[11]借鉴了用于文本聚类的LDA模型并扩展它使其在协同实体识别中得到应用,也取得了很好的效果.随着实体识别领域的扩大,出现了一些新的应用场景,在新的应用场景中,如果采用原先的相似度度
6、量进行模拟,可能会丢失一些有用信息.在原有相似度度量的基础上,把应用场景中一些丢失的有用信息加入到度量标准中来形成新的相似度度量标准.在基于图的实体识别中节点表示实体,边表示实体之间的联系.把链接属性加入到相似度的度量中,就是利用节点的相关联实体来发现实体间的相似度.基于链接的建模方式提高了实体识别的精度,但是前期的X收稿日期:2009205212;修回日期:2009206225基金项目:国家自然科学基金(60875038,60721002,60503021);江苏省高新技术计划(BG2007038)作者简介:雷钰丽(1984-),女,
7、江西丰城人,硕士研究生,研究方向为数据挖掘.·27·研究中,只关注于2个节点或者说2个实体之间相不相关联这种布尔属性,即3个节点的链接属性值包含2种可能:相关联和不相关联.其中相关联就是对应图中2个节点之间有边存在,而不相关联就对应图中2个节点之间无边存在.此建模方式只考虑联系的有无,而没有考虑某些应用场景中首要考虑的实体之间联系紧密程度这个很重要的属性.文献资料数据库中只考虑链接的有效性,但是在很注重通话模式的领域电信系统中,2个节点间的联系紧密度就是很重要的标准.本文针对这种特殊的应用场景,把基于无权重无向图的实体识别问题扩展到有权
8、重图实体识别问题.提出借用马尔可夫随机游走的思想通过概率的形式来表示实体之间的相似性,并在相似度度量基础上把图的权重形式从单一属性扩展到多属性,提出了基于链接多属性的实体识别算法.1基于马尔可夫的随机游走相
