华中科技大学 硕士学位论文 基于Web的社会网络搜索中人名同一性判断方法研究 姓名：庞永杰 申请学位级别：硕士 专业：计算机软件与理论 指导教师：张晓芳 2011-01-17 I 摘摘 要要 随着计算机科学与互联网技术的不断进步， 人们彼此之间可以通过各种各样的软 件和方式进行在线交互，不再受到时间和地域的限制。随着人们在互联网上的行为日 益丰富，互联网上的社交行为和关系逐渐的接近传统的客观世界的社交网络，并能够 真实反映出人与人之间在客观世界的真实关系。 可以从互联网中通过搜索的方式来构 建一个真实客观世界的社会网络。 社会网络搜索技术及其方法逐渐成为目前的研究热 点，互联网中的丰富信息大都包含在Web中，可以从Web中获取关于某个人的社会网 络信息，然而多个人会具有一个相同的名字，那么如何对每个Web进行人名同一性判 断就称为了社会网络搜索的关键技术。为了能准确地进行社会网络搜索，研究了人名 同一性判断技术的实现。 介绍了信息检索领域中的向量空间模型。 为了从文本中抽取准确的特征并降低向 量维度， 给出一个基于Cvalue和词频IDF的特征向量权值计算方法。 实现了基于余 弦夹角的相似度计算的算法； 通过对文本聚类算法中层次聚类算法和划分聚类算法的 研究，给出一种改进的层次聚类算法来实现人名同一性判断；为了提高聚类算法的收 敛速度，给出一种聚类中心的计算方法。 为了实现社会网络搜索，设计了一种基于Web的社会网络搜索系统框架。为了能 获取包含社会网络信息的Web文档，给出一种Web下载器的实现方法；通过使用 ICTCLAS-API完成对Web的中文分词处理；根据Cvalue和词频IDF计算词项权值， 并根据特征选择条件选择特征词项作为向量；通过使用聚类算法进行Web文档分类完 成人名同一性判断；给出人物关系强度定义，通过使用现有商用搜索引擎，设计并实 现了人物关系获取和关系强度计算的具体算法。 为了说明使用*Cvalue IDF权值计算方法和改进的层次聚类算法对人名同一性 判断性能的影响，以搜索引擎的人名检索结果进行测试。说明了基于改进的层次聚类 算法的人名同一性判断能有效降低人名判断的时间，但是以损失部分准确率为代价。 关键词：关键词： 社会网络，向量空间模型，同一性判断，层次聚类 II Abstract As the progressing of the computer science and internet technology and the growing, people can do online communicate with each other via kinds of software and type no more be restricted by time and region. As the increase of activity on internet from people, the social contact base on internet close in on the external world. We can structure a real social network via search technology from internet. social network has caused a large number of researcher attentions which focus on social relationship network search. Rich information has be included in Web page, so we can acquire a people social network information by Web mining. When you search for information regarding a particular person on the Web, a search engine returns mayn pages. Some of these pages may be for people woth the same name. How can we disambiguate these different people with the same name has be the key technology in social network search. In order to construct a accurate social network for person, we research the person name identical judgement technology. This paper presents an unsupervised hierarchical algorithm base on vector space modle to disambiguate different people with the samename. In order to reduce the dimension of vector, paper presents using C-value and IDF to calculate weight of character which extracted from the Web page. We calculate the similarity via calculate the cosine of angle on two vector. Combining the hierarchical and partitional clustering, this paper presents a improved hierarchical clustering algorithm to implement person name identical judgementing. For reducing the time complexity of clustering algorithm, this paper presents an new method on calculating core of cluster. This paper presents a system framework to implement person social network search. Introducting a method to implement Web page download from Web search engine so we can to acquire the social network information. Using the api which provided by ICTCLAS to complete chinese word segmentation and calculate weight of the character III word. Finally using the method which this paper presented disambiguate different name via document classification. The framework using the commercial Web search engine to calculate relationship between two people. At last this paper evlated the algorithm on a collection of documents retrevied from the Web. Experimental results show a significant improvement over the existing methods proposed for this task. Key words: social network，vector space model，identical judgement, hierarchical clustering 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 本论文属于 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 1 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论绪论 1.1 课题背景和意义课题背景和意义 近年来，复杂网络已逐渐成为一种研究复杂系统的重要方法，对复杂网络的 研究正受到来自不同领域的越来越多的研究人员关注，复杂网络已经成为一个跨 学科的研究热点。现实世界中的很多系统都可以用复杂网络的形式来描述，这些 复杂网络具有网络平均路径长度较小、聚类系数较大、节点度分布服从幂律分布 等相同特性。社会网络（Social Network）也是是一种复杂网络，反映了社会成员 及其相互关系，是社会成员及联结他们的各种关系的集合。通过对社会网络的理 论研究，尝试挖掘隐藏在表面关系之下的隐形关系，可进行电子商务、信息推荐 等有益的应用。社会网络在人们的日常生活中扮演了重要的角色，人们通过社会 关系，与朋友、家人、同事、商业伙伴交流、共享信息。人们的生活受到了社会 网络的深刻影响，这些影响是与人们所掌握知识的多少和程度是无关的。社会网 络在信息系统中的存在潜在应用1， 例如通过社会网络进行病毒式营销2和基于社 会网络进行电子邮件过滤等。 社交网络服务（SNS）现在成为Web网络的关注热点。作为一种基于社会网络 的网络应用，SNS网站通常要求用户在进行注册时候提供已经在该系统上完成注 册的朋友和熟人的信息；这类系统为用户和好友之间提供了便捷的的信息交换功 能，如发送电子邮件，阅读好友的网页博客等。 Friendster和Orkut是最早也是最 成功的SNS网站。逐渐地，SNS网站会更多的关注如何加强和扩大好友之间其他领 域的交流，如音乐，医学和商务。存在大量的信息，如私人照片、日记和研究笔 记既不是完全开放的也不是完全保密，这使得信息共享将成为SNS网站具有广阔 前景的应用34：信息可以在用户与其的朋友，同事和熟人之间进行一种松散的共 享。一些商业SNS网站如Imeem和Yahoo360为用户提供文件共享功能，并且这种功 能具有完整的访问控制权限。在语义Web环境中，社会网络是实现网络信任机制 的关键，通过社会网络可以判断信息是否是可信任、可依赖的5。因为任何人都 可以通过网络发言，基于社会网络的信任机制可