Web社区中话题的发现与排序

武汉理工大学 硕士学位论文 Web社区中话题的发现与排序 姓名：文利娟 申请学位级别：硕士 专业：应用数学 指导教师：陈盛双 20091101 摘要 随着Web社区的蓬勃发展，互联网正逐步跨入社区时代。Web社区以其开 放性、互动性和共享性深得广大网民的喜爱，成为网民表达思想、获取信息、互 相交流以及建立社交圈的主要平台。如何对社区中的资源进行分类、整理、排序， 将优质、有效的资源推荐给用户，以有效地提高社区资源的分享和利用，具有重 要的意义。 本文面向虚拟社区领域，使用话题发现技术和话题排序技术对其话题信息进 行挖掘。在话题发现中，本文通过选择合适的话题发现模型对从Web页面中提 取的与话题相关的主题进行 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，然后运用单遍聚类算法实现了话题发现；在话 题排序中，本文根据社区网页特点建立了话题排序特征模型，然后根据话题排序 得分实现了话题排序。通过话题发现和话题排序，本文实现了将社区中的信息按 照所表达的主题进行归类和组织，并以有序的形式展现给用户，从而有效地管理 和组织了社区中的信息，可方便用户在动态变化的社区环境下查看自己感兴趣或 需要的信息。 本文的创新点如下： (1)在话题发现和建立话题模型时，将主题与评论相结合，从而使获得的 话题信息更为全面。 (2)在话题排序时，本文通过对Web社区网页进行分析，选出话题的最近 发布时间、最远发布时间、主要发布时间、被点击次数、被评论次数、当前评论 增长速度，平均评论数和当前评论数作为排序特征，从而解决了传统话题排序 中使用单一的点击数或更新时间来进行话题排序的不足。 (3)在确定权重向量时，结合用户参与评判的方法提出了一种新的确定排 序特征向量权重的方法，实验证明，通过该方法得到的权重向量使本文得到了较 好的排序结果。 本文的实验对象为国内最大的三个社区网站：猫扑大杂烩、天涯社区和腾讯 社区。实验证明，本文所提出的社区话题发现和排序方法是可行的，且排序 结果良好。 关键词：Web社区；主题信息提取；主题分析；话题发现；话题排序 Abstract WiththevigorousdevelopmentofWebcommunities，thehateITIetisgraduallv enteringtheeraofthecommunity．Webcommunityisbecomingmoreandmore popularwiththemajorityofInternetusers．Itsopenness，interactionandsharinghas madethembecomeamainplatformforInternetuserstoexpressideas，aceessto mformation，mutualexchange，aswellasestablishtheirsocialcircles．Howto classify,arrangeandranktheresourceincommunitytorecommendtheefficient resourcetousersandimprovethesharingandusingofcommunityresource effectivelyhasimportantsignificance． Thispaperusestopicdetectionandtopicrankingtechniquestominetopic knowledgefromtheCommunity．Intopicdetection，thispaperanalVzethetheme whichisrelatedtothetopicintheWebpagebyselectingaappropriatetopicdetection model，thenusessingle。passclusteringalgorithmtodiscoverythetopic；hatOpic ranking，thispaperaccordingtothecharacteristicsofWebpagetoestablishthetopic rankingfeaturemodel，thenachievedtorankingthetopicsbythetopicrankingscore． Aftertopicdetectingandtopicranking，thispaperachievedtoorganizethe communityinformationbysubjectanddisplaytheminanorderedform，soitcanhelp usersexaminetheirinterestedorneededinformation． Theinnovationofthispaperisasfollows： (1)CombinethemewithcommentinTopicDetectionandtopicmodel．this makesthetopicinformationmorecomprehensive． (2)Inthetopicrankingtechnique，aftertheanalysisofWebcommunitiespage, thispaperselectsthelast，thefirstandthemajortimethatthetopicwasreleased． clicks，thenumberofcomments，thegrowthrateofthecurrentcomments，theaverage numberofcommentsandthecurrentnumberofcommentsasthesortfeatures．nis worksolvesthedeficiencyofrankingtopicsonlybyusingclicksandupdatedtime． (3)Indeterminingtheweightvectors，basedontheuserinvolvementevaluation method，thispaperpresentsanewmethodtodeterminetherankingfeaturevector weights-Theexperimentshowsthattheweightvectorsthatobtainedbvthemethod makesthepapergetgoodrankingresult． Theexperimentalsubjectsofthispaperarethelargestthreecommunitvsites： Mophodgepodge，TianyacommunityandTencentCommunity．Theexperiment Il resultsshowthatthemethodoftopicdetectionandtopicrankingforcommunityin thispaperisfeasibleandthisrankingmethodworkswell． Keywords：Webcommunity；Subjectinformationextraction；Subjectanalysis；Topic detection；Topicranking III 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：主奎2盔置 日期： 2丝Z望：望 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本 学位论文的全部内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存或汇编本学位论文。同时授权经武汉理 工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 (保密的论文在解密后应遵守此规定) 研究生(签名)：受辛．?搦导师( 日期?群．J2．J2 武汉理T大学硕二E学位论文 1．1研究目的和意义 第1章引言 随着计算机尤其是网络技术的发展，在线社区或者称之为虚拟社区(Virtual Community)的应用形式在互联网上蓬勃发展。虚拟社区这种新的电子社会行为 越来越显著的影响着传统社会中的每一个成员，虚拟社区可以给成员带来新的 交流方式、工作方式、协同合作方式，甚至是影响到生活的每一个角落如购物， 交友等。虚拟社区在互联网上以前所未有的速度增长，以至于理论研究远远 落后于应用实践，这为我们提供了许多值得研究的课题。这些研究课题涉及信 息技术、社会学、心理学、经济学、管理学等等各个方面。 最早的关于虚拟社区的定义由瑞格尔德(Rheingold)做出，他将其定义为 “一群主要籍由计算机网络彼此沟通的人们，他们彼此有某种程度的认识、分 享某种程度的知识和信息、在很大程度上如同对待朋友般彼此关怀，从而所形 成的团体。"国外分别有“VirtualCommunity"、“OnlineCommunity"、“Electronic Community"、“CyberspaceCommunity"、“Computer．mediatedCommunity”和“Web community"等名称，而我国则有“在线社区"、“网上社区"、“网络社区"、“虚 拟社区"、“虚拟社群"等不同叫法。 随着社区技术的高速发展和社区应用的普及成熟，互联网正逐步跨入社区 时代。从论坛BBS、校友录、博客(Blog)、个人空间、SNS交友等新旧社区应 用，到社区搜索、社区聚合、社区营销、社区资源共享等话题，都是业界关注 的热点。互联网社区在2008年取得了高速的发展，中国网民对论坛／BBS／讨论组 ／论坛社区等的应用已经超过即时通讯，成为仅次于搜索引擎的互联网基本应用。 以BBS、新闻组为基础应用的论坛类网络社区在中国历经10余年的发展， 拥有了比较庞大的用户群体。根据“中国互联网络信息中心"统计数据【l】，截至 2008年6月，中国有191万家(CNNlC)独立网站，从门户到行业网站，从地 区门户到个人站点，80％以上网站均拥有独立社区。社区类网站月度覆盖人数上 升迅速，社区用户月覆盖人数超过1．4亿。网络社区的开放性、互动性和共享 性深得广大网民的喜爱，网络社区作为广大普通网民发表自身言论和思想的有 效载体和平台，代表着草根文化潜在的巨大价值和影响力，成为网民表达思想、 武汉理工大学硕士学位论文 展示自我、获取信息、与其他网民互动互通以及建立社交圈子的主要平台，在 中国的发展十分迅速。网络社区用户覆盖人数的稳定增长，表明其已经成为主 流网络应用之一。 Web社区成为社会舆论最重要的传播载体。调查显示111，中国网民的主体是 30岁及以下的年轻群体，这一群体占到网民总数的68．6％，他们更加习惯通过 互联网获取新闻信息、表达意见。2008年以来，由于互联网的影响，有些地方 性、局部性的事件一夜之间被放大，成为全国关注的话题。以拉萨“314”事件 和汶川“512"地震为标志，网络社区已经成为社会舆论最重要的策源地。网络 社区正在全面渗透到社会生活的每个方面，并成为社会舆论最重要的传播载体。 网络社区的迅速发展弱化了政府对社会信息的控制力，如何有效的监控、引导、 管理网络社区的舆论发布和传播，如何整治互联网低俗信息的传播【到，具有重要 的研究意义和应用价值。 Web社区中包含了丰富的资源和知识。用户的相互交流、话题和资源的发 布、相互的咨询和帮助、问题的讨论形成了丰富的知识网络，基于Web社区的 讨论有助于提高组织中的协作、知识创新和知识传播。对Web社区内的知识进 行结构化、有序的分析和整理，有效的对Web社区知识进行分享具有重要的意 义。在用户浏览社区资源时，“推荐”、“Top”、“精华’’类型的社区资源受到用 户浏览频次最高，占66．2％131。如何对社区中的资源进行分类、整理、排序，将 优质、有效的资源推荐给用户，以有效地提高社区资源的分享和利用，具有重 要的意义。 Web社区中包含了丰富的用户资源。用户是社区的主体，2008年调查显示 【3】：用户访问社区网站时间在在6小时以下居多，占78．5％，社区的深度用户占 比例也较高，每天访问时间在6小时以上的达到了30．5％。用户在社区种的参 与程度也比较高，其中平均几天参与交流的占24．5％，平均每天交流15次以上 的有16．6％，从来不参与的比例非常低，仅占2．7％。 社区用户根据不同的价值取向和喜好聚集成为圈子或群落，使得在社区中 的广告投放与传统网络广告相比更为精准；社区用户将社区作为发表自己思想、 见解的平台，具有较强的参与性和信息分享性，网民使用产品后在社区中分享 体验己成为其习惯性行为，其发表的观点和经验，J下自觉不自觉地影响着圈子 中其他社区用户的消费理念、消费行为和消费决策【41，具有一定“社区知名度’’ 的活跃用户，这种影响力更为明显。对社区中的用户进行Top．K排序，从社区 中找到关键用户具有良好的商业价值。 2 武汉理工大学硕十学位论文 社区用户在网络交流、资源发布、情绪宣泄时，会表现出一些具有个人特 征的信息。通过对用户的言论、行为、 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 、关系网络进行分析，来得到一些 用户的特征和信息，如：兴趣、特长、领域、性格、地理、年龄、性别、职业、 资产等。这些特征对识别用户需求、用户精准定位，具有广泛的商业价值。 Web社区数量庞大、良莠不齐。根据调查显示，截止2008年，社区应用的 主要方式论坛数量已经达到130万个I引，Blog空间数达到1．07亿【21。社区涉及 的领域也比较广阔，其中排名第一的是门户类，占比达16．9％，其次是互动娱乐 类，为12．5％；IT产业和教育类也都在10％以上。社区的新生和消亡也比较普 遍，2008年成立的网络社区占最大比重，为46．3％，其次为2007年，这两年成 立的社区比重达74．7％。社区的差异主要表现在社区内容数量和质量、社区中用 户状况、社区的结构组成等多个方面，用户在从社区中获取资源和信息时，会 存在难以抉择的问题，如何找到本领域中最优质的网络社区推荐给用户使用， 具有重要的应用价值。 本文重点研究从Web社区中挖掘不同时期的热点话题并对之进行排序的理 论和方法，方便社区用户分享、浏览社区资源，促进Web社区的建设和繁荣。 这对于政府有关部门有效的监控、引导、管理Web社区的舆论发布和传播，整 治互联网低俗信息的传播，具有重要的研究意义和应用价值。 1．2国内外研究现状 1．2．1社区研究现状 目前，Web社区研究，已成为互联网领域的研究热点，国内外学者和产业 界对Web社区的多个方面都展开了研究： 在社区发现方面，目前绝大多数的社区发现研究项目是基于Web页面之间 的链接结构进行的爬行、抽取、挖掘而进行的。YingZhou，JosephDavis【5J提出 了一个在Blog中发现社区的方法。他们将整个Web视为一个有向图，每一个节 点代表一个页面，每个超级链接代表一条边；通过爬行得到Web图的结构，他 们首先从一个种子(seed)Blog的所有页面中找到一个超级链接的候选集合，然 后从候选集合中去掉链回种子或者没有指向Blog的链接，剩下的链接集合指向 了其他的Blog。然后再去掉有向图顶点之间的重复链接，保留重复链接的数量 作为链接权重，并使用islandpartitioningalgorithm分析方法挖掘出网络中存在的 3 武汉理：【大学硕士学位论文 虚拟社区【酣，比较典型的相关分析方法包括改进的PageRank算法I71。此外，还 有基于HITSI引、二分有向图和流量的技术用来挖掘潜在的社区。 在社区搜索方面，是通过集成社区资源形成索引，从而对领域内的所有社 区进行资源检索的功能。目前已有较为成熟的产品。NileshB{insal和NickKoudas 19J提出了一个基于文本文档(Blog)的爬取、过滤、索引和搜索的方法。通过维 护RSS信息来实现信息的集成。刘务华，罗铁坚，王文杰等【10l在分析Web社区 搜索资源分散特点的基础上，运用Web抓取器、向量空间模型和相关性排序等 技术 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 了Web社区搜索引擎的体系结构，实现了一个Web社区搜索引擎系统—ChinalabSearch。 在社区分析方面，包括社区中人和人关系的分析，主题和内容的分析，个 人爱好和信息的分析，组成结构分析等。分析方法包括使用图论来对基于链接 网络的社会关系分析，JureLeskovec等人【11】利用submodularity算法构造突发事 件预警模型，能够低成本的快速发现社区中的突发热门事件；ParagSinglall2l研 究了利用1M进行交流的群体的关联性和兴趣分享，从而实现个人行为的分析； JiaweiHan等人建立了一种基于最优线性组合的学习方法，来对多关联复杂社会 网络中的隐藏信息进行挖掘【13J以及对异构社会网络进行挖掘【14】；RolfA．E． Mueller等人利用供应链模型对社会网络进行分析【15】。还一种分析是使用语义模 型对人们之间的主题和内容进行分析，PeterMika构建了基于语义Web技术的 Flink社会网络抽取和分析系统【16】，以及统一的社会网络语义模型Ontologiesll71。 另外还有利用潜在空间模型对动态社区进行分析【18】，有对社区网络的演变进行 实证分析119】，以及不确定性社区分析【20】等。国内有牛军钰等人对社区用户进行 特征时空建模和挖掘12¨，徐从富等对异构关系的社区挖掘1221。 在社区评价方面，主要是通过用户的反馈和关系密集度来对社区进行评价。 YiweiCao，AnnaGlukhovaI冽等以游戏社区为例子，分析了社区成功的因素，提 出了社区评价的统计方法。RobertMcCann，AnHaiDoanl24J等利用在线问答形式 获得用户的反馈，并利用用户反馈的质量对用户进行评价，获得用户的权重。 GVelayathan和S．Yamadal25J给出了一个基于用户行为的方法用于评价网页的 质量。 与本文相关的研究内容主要包括Web社区中的话题发现和排序两个方面， 下面将进行概述。 4 武汉理J二人学硕十学位论文 1．2．2社区中的话题发现与排序 话题发现源自TDT领域，TDT技术(TopicDetectionandTracking，话题识 别与跟踪)是由美国国防高级研究 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 署(DARPA)倡导的一项研究，涉及到 网络形式的新闻报道，并取得了一定成果【孤捌。话题识别是指自动识别信息片 断集合中的各个未知话题，并能在线 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 出新话题。话题跟踪是指在各种信息 来源中追踪那些讨论目标话题的相关信息片段12引。 自1996年TDT概念提出以来，国内外许多研究机构都参与了这一技术的研 究，大大地推动了相关技术的发展。 JureLeskovec等人【1ll利用submodularity算法构造突发事件预警模型，能够 低成本的快速发现社区中的突发热门事件；多伦多大学的NileshBansal等人【30J， 通过追踪Blog中发表的文章，发现出流行的或者最新的话题、用户组群以及相 关地理信息。R本东京大学的NaohiroMatsumura教授等人[31】提出影响力传播模 型IDM，该模型利用帖子中的关键词反映人物的观点，在帖子线索中关键词传 递的多少反映其影响程度的特点，实现了对BBS上有影响力的人物及其话题的 发现。IDM模型的着眼点在于用户间的交互模式，通过分析帖子或用户所传递 的影响力来发现热门话题或焦点人物。后来国内蒋儿等人利用IDM模型设计并 实现了一个主题发现原型系统【32J，该模型所使用的方法需要反复计算词语以及 词语问的影响力，并重新构造词语结构图，使得计算复杂度较大，不适合大规 模的文本计算。 在国内，邱立坤等人【33】在考虑在BBS的标题、J下文、首帖、回帖中出现的 词分别有着不同的重要性的基础上，改进了传统的向量空间模型，即在聚类时 采用非增量的Single．Pass算法，以各话题中平均相似度最高的帖子线索的标题 作为该话题的标题，然后应用BBS特有的点击数、回复数进行热度排序，再采 用基于标题特征词提取的话题归并方法，归并同一主题而不同视角的话题；针 对Blog文本的特点，丁伟莉等人【34】提出了一种应用于中文Blog的热门话题检 测与排序技术，通过对基于词条的向量空问模型以及词条间相似度的计算方法 的改进，节省了存储空间，减少了相似度的计算量；同时考虑到同义词和近义 词的存在问题，采用了词形和词频相结合的方法进行聚类结束，然后在每个话 题的标题中心向量中选取权重最大的两个词作为最后的话题名；最后选取话题 中的文章数、话题中文章所对应的评论条数之和、话题中的文章所对应的评论 人数之和作为话题排序的特征向量，进行线性加权组合后得到了话题的综合排 5 武汉理T大学硕十学位论文 序。 总的来说，国外对Web社区的研究工作起步不久，国内才刚刚起步，有待 研究的地方还很多。在话题发现和排序的研究中已有的算法在应用到实际中时 还存在很多的不足之处，需要对聚类方法以及排序技术等加以改进。 1．3论文组织结构 本文主要由两部分研究内容构成：第一部分研究如何从信息量庞大的Web 社区实时、动态地发现有意义的话题；第二部分在第一部分研究的基础上设计 合理的排序模型对已发现的话题进行排序，并将排序结果展示给用户。通过对 这两部分内容的研究，力求达到将社区中当前最热门的话题展示给用户，方便 用户浏览的目的。 本文组织结构如下： 第一章是引言，概述了Web社区中的话题发现与话题排序的研究背景和意 义，并介绍了国内外关于Web社区、话题发现和话题排序的研究现状。 第二章介绍了搜集Web社区资源的三个关键技术，即Web资源发现技术、 Web页面净化技术和Web文本处理技术。 第三章主要介绍了本文的话题发现方法，即通过选择合适的话题发现模型 对从Web页面中提取的与话题相关的主题进行特征分析，然后运用单遍聚类算 法实现话题发现。 第四章主要介绍了本文的话题排序方法：首先根据社区网页特点建立话题 排序特征模型，然后对话题排序特征进行标准化处理，并结合用户参与评判的 方法提出了一种新的确定权重向量的方法，最后根据话题排序得分实现话题排 序。 第五章主要是对本文提出的话题发现和话题排序方法进行了实验。实验结 果表明，本文所提出的方法具有可行性，排序结果良好。 第六章总结与展望。 6 武汉理下大学硕士学位论文 第2章Web社区资源的搜集技术 随着因特网的不断普及和发展，网络上存储的数据与信息以前所未有的速度 剧烈膨胀。Web社区可以看作为一个巨大的信息库，其中包含了大量不同类别的 信息，但是它没有合适的索引目录，也没有标准的组织结构，用户在进行Web 信息检索的过程中，很难找到自己所需要的信息。因此需要研究Web资源的搜 集以及管理技术，以方便用户利用社区资源。在本章中，将概述搜集Web社区 资源时要运用到的关键技术，主要包括Web资源发现技术、Web页面净化技术 和Web文本处理技术。下面分别对这些技术进行说明。 2．1Web社区资源的发现技术 Web资源主要有规模大、更新快、内容丰富、信息类型多样、信息寿命短暂、 资源价值不一和资源分布广泛无序这几个特点，这些特点使得Web社区成为一个 巨大而复杂的信息源。如何使用户在Web社区的海洋中找到所需的信息就是Web 资源发现要解决的问题。本文将主要介绍基于链接分析的Web资源发现技术。 为了获取相关主题的Web社区资源，用户希望能够查到与给定主题相关的 Web页面，并且该页面具有较高的质量，称为最具权威的(authoritative)页面。 有意思的是权威性通常隐藏在页面的链接之中，它们不仅由页面组成，还包括页 面之间的超链接。这些超链接包含了大量潜在的人为认可的信息，有助于确定权 威性。当～个页面的作者建立指向另外一个页面的一个链接时，可认为是该作者 对另一个页面的认可。如果将每个网页看作是一个节点，每一个链接看作是一条 有向边，那么整个web就构成了一个巨大的有向图。通过分析Web图链接结构以 确定页面重要程度的技术被称为链接分析技术。下面，介绍基于链接分析的两个 典型算法：PageRank算法和HITS算法。 2．1．1PageRank算法 PageRank算法由Stanford大学的Brin和Page提出的13引，是W曲超链接结 构分析中最早、最成功的算法之一，也是最早并且最成功地将链接接分析技术应 用到商业搜索引擎中的算法。Google搜索引擎就是通过将该算法和链接文本标 记、词频统计等因素相结合的方法对检索出的大量结果进行相关度排序，将价值 度高的网页尽量排在前面。 7 武汉理工大学硕士学位论文 PageRank算法的基本思想是试图为搜索引擎所涵盖的所有网页赋予一个量 化的价值度，每个页面被量化的价值以一种递归方式来定义，由所有链接向它的 网页的价值度所决定，即被大量高价值网页引用(链接)的网页也是具有很高 价值的网页。其理论基础如下： 忽略掉Web页面上的文本和其它内容，只考虑页面间的超链接，构造有向 Web图G=∥，E)，其中顶点y表示所有网页集合，边E表示网页间的链接集合， 网页f中有指向网页j『的链接表示节点f和．f之间存在一条边。节点f的出度是指 从页面i出发的所有超链接(outlink)的总数，而入度则是指所有指向节点f的超 链接(inlink)的总数。假设F。是被网页“链接的网页集合，巨。为链接网页“的 网页集合，令N(u)=IEI，则网页U的权值袱似)为： D／．．、 Pn(u)；dD(u)+(1一d)y二盟(2．1)。、 。魁NO) 上式可以用一种随机网上冲浪者(thesurfers)模型来描述，假设冲浪者跟 随链接进行了若干步的浏览后又转向一个随机网页重新跟随链接浏览，那么一个 网页的价值度就由该网页被这个随机冲浪者所访问的频率所决定。 对于随机访问模型，存在另外两种情况，一是存在这样一类网页，它们没有 指向其它网页的链接，仅在一定范围内相互链接；另一种是出度为零的一类网页。 当用户访问到这两类网页时，按照上述模型进行访问，访问将终止或仅在某一类 网页上徘徊，它们在算法迭代过程中会不断地吸收权值，直到所有的权值都沉积 到它们上面，这种现象被称为权值沉积(RankSinking)。对于这种情况，当一个 随机冲浪者遇到了这种沉积网页时，他可以随机地挑选另一个网页并继续浏览。 为了对所有的网页一视同仁，这种类型的随机访问可以相同的概率在任何一个网 页上发生。从而得到PageRank算法的修正形式如下： n，．．、PR(u)；扣@)+(1一d)罗掣(2．2) 矿邕』V吖' 其中d为跳转概率，通常被置为O．15。上式表明冲浪者以概率d不再跟随链 接浏览而是重新以分布D@)(一般取D似)=1／11)随机地挑选一个网页进行浏览， 以概率1一d继续跟随当前网页中一个链接进行浏览。 PageRank算法实现过程：将网页的URL对应成唯一的整数，然后把每一个 超链接用其整数lD存放到索引数据库中，经过预处理之后，设每个网页的初始 PageRank值为1，按照上面的递归算法计算每一个网页的PageRank值，反复迭 代，直到结果收敛为止。显然，PageRank值越大，表明该页面的权威性越高。 该算法与用户的查询条件无关，只是将每一页面的PageRank值作为搜索引擎结 果排序的一个参考，值越高的页面排序越靠前。 8 武汉理丁大学硕士学位论文 PageRank算法通过分析Web超链接关系可大大提高Web检索的准确性，克 服了基于内容匹配方法的不足。PageRank算法本身是一个著名的页面排序算法， 且与主题无关。TaherH．HaVeliwala【36J认为用户浏览的网上冲浪者模型是基于主 题的，他们任意选择一个与自己感兴趣的主题相关的页面进行浏览，然后沿着其 链接到达与该主题相关的其他页面。根据这一思想，他将PageRank算法改造为 与主题相关的算法，运用该算法可以发现与主题相关的社区： 艘o)=(州／p㈣+(1一占)tv,毛PR(j)万‘2-3) 其中p(f，丁)表示i与主题r的相关度，￡是衰减因子，一般取0．1加．2，力为 有向图G中节点的数量，outlink(j)为节点_『包含的超链接数量。通过判断PR(i) 是否大于阈值来确定是否为主题的社区成员。 2．1．2HITS算法 HITS算法是由Kleinbergl38J在90年代末提出的一种链接分析算法，与前面 介绍的PageRank算法相比，HITS算法提供了一种更加完善的衡量网页重要程度 的度量。HITS算法的基本思想是通过对网页的链接进行分析得出每个网页的权 值从而得出网页的权威性。在HITS算法模型(HypertextInducedTopicSearch) 中，Kleinberg将页面分为两种类型：一种为描述某一主题的权威页面，称为 Authority页面；另一种为能把这些Authority页面联结在一起的页面，称为Hub 页面。HITS算法涉及两个重要的权值概念： Authority：表示一个权威网页被其它网页所引用的加权次数，即该权威网页 的加权入度值。某一网页被引用的次数越多，则该网页的加权入度值越大，即 Authority越大。 Hub：表示一个Web页面指向其它网页的加权数量，即该Web页的加权出 度值，它提供了指向权威页面的链接集合。某一网页的加权出度值越大，则该网 页的Hub值越大。Hub起到了隐含说明某话题权威页面的作用。 HITS算法具体过程：根据用户查询请求，首先用一个现有的商业搜索引擎 进行查询，取约200个查询结果作为算法的根集(RootSet)，记为RQ。由于这 些页面中的许多页面被假定为与搜索内容相关，因此它们中应包含指向最权威页 面的指针。然后，对RQ中每一个节点，将所有指向该节点或该节点所指向的网 页补充进来形成基集(BaseSet)，记为BQ。计算BQ中每一个网页的Authority 权重和Hub权重，这是一个递归的过程。 HITS算法如下： (1)为基集的每个页面赋予一个非负的Authority权重和非负的Hub权重， 9 武汉理T大学硕士学位论文 如对任意一个网页P可令其Authority权重为a，，Hub权重为hP，并将所有的aP 和h，值初始化为同一个常数，如令口，=Lhp=1。 (2)Authority与Hub的权重可按下式计算： 口P．∑．hq (2·4) Iq：q-．P， hP∑口。 (2-5) Iq：q—·pJ 其中P，q代表网页，q—p表示网页g通过链接指向网页P，a，和a。分别表 示网页P和q的Authority权重，％和h，分别表示网页P和口的Hub权重。 (3)每次迭代后进行规范化处理保证不变性，处理公式如下： 罗(口吁)2—1 (2．6) 仍 罗啦)2—1 (2．7) 仍 其中P代表网页， 口。表示网页q的Authority权重，hq表示网页q的Hub 权重。 (4)当口，和Ill，没有收敛时，转到公式(2．4)、(2-5)。 (5)大量实验证明，经过大约10-15次迭代计算，a，和h，的值将趋于稳定， 即迭代结束。此时，可设置阀值丁，将所有口，和h，大于r的网页挑选出来，排 序并输出查询结果。 Kleinberg等人通过大量的实验发现HITS算法对于许多查询具有良好的查准 率和查全率，且通过它所发现的社区主题和HITS算法根基的选择几乎无关。尽 管HITS算法取得了较大的成功，但由于HITS构造的子图通常会包含一些和主 题无关的页面，因此会存在以下一些问题： (1)主题漂移。所谓主题漂移就是给定一个宽主题查询，主题精选算法分 析出的最好的几个权威／中心信息源与用户查询相关度较低或不相关，或者仅包 涵查询宽主题的一个很“偏"的主题。由于HITS算法仅局限于Web页面之间的 链接关系，而没有考虑页面的内容，因而在应用过程中表现出不稳定性，有时会 出现主题漂移问题。 (2)无关链接的影响。在Web中，一个页面上的所有链接并不都与主题相 关，它们包括站点内的导航链接，广告链接等，这些链接会极大地影响HITS算 法的运算效果。站点内的导航链接很好清除，但是有些链接就不那么好过滤了， 需要用到许多其他的技术。 (3)无关页面的影响。无关页面被引入的途径有两个：一是基于相似度的 搜索引擎返回的根集中本身就包含无关页面：二是根据链接关系生成基本集时引 入的。由于HITS算法只是简单地根据链接关系确定权重，缺乏对页面有效性的 10 武汉理上人学硕士学位论文 判断，容易产生无关页面获得较大的Hub权重和Authority权重的结果，从而导 致输出的Hub页面和Authority页面与查询主题无关。 对于主题漂移问题，IBMAlmaden研究中心Clever搜索引擎对HITS算法进 行了一些改进，提出了ARC(AutomaticResourceCompilation)算法【39J。Clever 考虑到两点：第一，降低无关网页的影响，这就需要对不同的链接赋予不同的权 重。第二，在算法中加入内容控制信息，根据内容的相关性调节链接的权值，使 权值的计算具有一定的偏向性。基于这两点，Clever在HITS算法的基础上考虑 了网页超链接的锚(anchor)文本信息对网页排序的影响，利用链接的锚文本及 上下文信息与检索主题的相关程度来确定链接的重要性。Clever认为如果一个链 接的前后文本中都出现了关于主题的描述，则可认为当前网页和目的网页都与主 题相关，应相应地增加这个链接的权重。据此Clever构建了一个新的矩阵，在 计算网页Authority／Hub值时用该矩阵取代原有的网页链接子图的邻接矩阵。 为了减少无关页面的影响， J．Gevrey和S．Ruger于2002年提出了两个基于 超链接和内容的网页排序算法，即Average算法和Sim算法1401。这两个算法与 HITS算法的主要区别在于：向基于内容排序的搜索引擎提交查询主题，获取根 集网页的过程中，会返回每个页面与查询主题的相似度(similarity)值，HITS 算法没有考虑该项信息，仅利用网页间的链接结构来计算网页的Authority／Hub 值，而Average算法和Sim算法在计算网页Authority／Hub值时则利用了该项信 息；在迭代计算网页Authority／Hub值时，HITS算法要求迭代运算至结果收敛， 而Average算法和Sim算法的迭代次数为1，即只考虑网页的相邻页面对结果的 影响。具体计算公式如下： Average算法： 1authority(p)=--罗similatity(q)(2．8)tq：q—pj．筛 Sim算法： 1authority(p)一simila，．ity(q)+_÷罗similatity(q)(2-9) tq：q—’P，q一--·p 其中P，q代表网页，q呻p表示网页q通过链接指向网页P，authority(p)表 示网页P的Authority值，similatity(q)是由基于内容的搜索引擎返回的网页q与 查询主题的相似度值。 ． 2．2Web页面净化技术 Web页面净化是Web社区资源搜集过程中预处理阶段的一个重要组成部分。 武汉理_T大学硕士学位论文 Web页面当中除了用户感兴趣的主题信息之外还会存在很多与内容无关的图片、 动画、导航条、广告、版权信息及站点介绍等。这些噪音信息可能会对试图通过 Web浏览器获取信息的用户带来一些麻烦，不利于他们及时正确地找到所需的文 本信息，但一般不会妨碍他们正常地理解网页的内容。用户可以根据自己的经验 知识过滤噪音文本信息，但机器却无法有效地正确区分出哪些是真正应该获取的 文本信息，哪些是噪音文本信息。因此在从Web页面中分析提取出文本信息后， 还需要进一步地提炼出Web挖掘系统所关心的主题信息，这些文本往往具有一 定的主题意义，集中描述了某个主题的信息。 本文将主要介绍李晓明等人141】提出的基于DocView模型的W曲页面清理技 术，并结合社区中基于回复关系的信息发布特点，对Web页面进行分析，提取 出Web挖掘系统感兴趣的文本信息。 DocView模型包括：网页标识、网页类型、内容类别、标题、关键词、摘要、 正文、相关链接等要素。其中正文和相关链接要素属于网页的内容数据，而其他 6项则属于网页的元数据。下面将对模型中的各个要素作详细描述。 网页标识是对Web上网页的唯一性标识，在DocView模型中使用网页的 URL作为网页标识。 网页类型是根据网页内容的表现形式进行划分的，在本节中将网页分为三 类：有主题网页(topic)、Hub网页(hub)、图片网页(pic)。其中，有主题网 页是指网页中通过文字描述了一件或多件事物，是有一定主题的；如一张具体的 新闻网页就是典型的有主题网页。Hub网页是指专门用来提供网页导向的网页， 因而是超链聚集的网页；如门户网站的首页就是典型的Hub网页。图片网页是 指网页的内容是通过图片的形式体现的，其中文字很少，仅仅是对图片的一个说 明；如某个机构包含图片的人员介绍网页就是典型的图片网页。 将网页分为上述三个类型是因为三类网页在用途和处理方法上存在较大的 差别。其中Hub网页与其它两类网页的区别在于网页在Web上发挥的作用不同， Hub网页通常不会具体的讲述一件事物，而是提供关于相关信息的链接集。而图 片网页与其它两类网页的区别在于处理的方法不同，由于图片网页的内容是通过 图片表达的而不是通过文字，因而，传统信息处理领域的方法对图片网页是不够 有效的。三类网页间的区别导致很多应用领域都会对它们作适当的区别。 内容类别是从语义上对网页的内容进行分类，它是计算机获取网页语义信息 的一个直接手段，在Web上的研究领域中有着广泛的使用。它是通过特定的分 类器对网页内容分类得到的，依赖于一定的分类体系。 标题、关键词和摘要是概括描述Web文档内容的重要的元数据，对于Web 信息检索等领域的工作有非常重要的作用。 12 武汉理工大学硕士学位论文 正文是原始网页中真正描述主题的部分，因此，在某些具体应用中用正文代 替原始网页更为合理。 相关链接是指在本网页中指向与正文内容相关的网页的链接，而非广告等噪 音链接。将正文和相关超链重新组合就得到了净化后的网页。 基于DocView模型的思想，并结合社区中资源的发布特点，本文考虑从以 下几个方面对Web页面进行清理，以提高社区资源的搜集效率。 (1)对于Web网页中的图片网页(pic)，由于其内容是通过图片中的信息 表达的，使得常用的文本挖掘方法无法对其进行处理。因此，当社区中的帖子以 图片形式出现时，需要首先对该Web网页的类型进行判断。当帖子包含的文字 少于一定阈值时，把该网页归类于图片网页，并放弃对其进行挖掘，当帖子包含 的文字大于阈值时，则把网页中所有的图片过滤之后，保留剩余的文本信息。 (2)利用中文分词法得到每个词的词性信息，用以过滤掉一些与网页内容 实际想表达的信息无关的词。如虚词：“了"、“吗’’、“啊’’等；形容词：“美好"、 “漂亮"等；副词：“忽然"等，这些词语对于分析网页的内容没有帮助，它们 只是对网页内容所描述的对象起修饰作用，以帮助用户更好地了解文字所描述的 对象。因此，为了提高挖掘关键词的效率，有必要过滤掉这些非名词词语而只将 名词词语保存到索引表中。 (3)词语在文档中出现的次数或频率通常反映了该词语在文档中的重要程 度。但是文档中往往存在很多频率很高但与文档所表达的内容无关的词语，如 “人"、“中国”等。这些高频词对于区分文档没有太大的作用，在进行传统的文 档分类时一般要通过TF．IDF(termfrequency—inversedocumentfrequency)方法降低 它们的重要度。在分析Web社区内容之前将这些高频词过滤掉，既可以提高信息 提取的准确性又可以减轻文本分析的工作量。 (4)社区论坛中的原帖一般都是包含一定主题的网页，它们通过一定数量 的文字对某个主题进行描述。但有时一些社区用户会发起一些与论坛无关的主 题，如商业广告。另外一些主题虽然与论坛内容相关，但所包含的有用信息太少， 不足以引起其它用户的关注和回帖，也应该在Web挖掘系统分析网页内容之前过 滤掉。因此，应根据原帖所引起的回帖数判断它是否属于有意义的帖子，如果原 帖引起的回帖数少于一定阈值则将被直接删除。 社区论坛中有时还会出现一些恶意回复的帖子，这些帖子的内容多由一些重 复的词语构成。这样的帖子虽然字数很多，但却会干扰Web挖掘系统分析帖子内 容。因此，如果当帖子中所有词的频率都一样时，则将这些词的出现次数设为l， 然后再计算帖子的有效字数，如果字数少于一定阈值则帖子将被直接删除。 13 武汉理rL人学硕十学位论文 2．3Web文本处理技术 2．3．1文本分析技术 目前大部分web文本都是以超文本标记语言(HyperTextMarkupLanguage， HTML)描述的，主要目的是为了方便用户通过浏览器进行浏览。这种描述方式 缺乏对数据本身的描述，没有清晰的语义信息，模式也不太明确，这使得应用程 序无法直接解析并利用Web上海量的信息，造成资源的极大浪费。因此有必要对 Web文本进行处理使之成为结构化、语义更为清晰的形式，为用户在Web社区中 寻找资源提供便利。 目前的文本分析技术主要有GerardSalton和McGill于1969年提出的向量空 间模型(VectorSpaceModel，简称VSM)【42】和基于语义的文本分析，下面分别予 以介绍。 一、向量空间模型 向量空间模型的基本思想是把文档简化为以特征项的权重为分量的向量表 示。在VSM模型中，将每个文本文档d看作由一组特征项瓴，t：，．．．，乙)构成，对 于每一个特征项t，根据其在文档d中的重要程度赋予一定的权值M似)，然后 将所有的权值看成一个，l维坐标系，其对应的坐标值为(M似)，％@)，．．．，M似))， 此时文档空间可以被看作是由一组正交词条矢量所组成的矢量空间，每个文档d 可以表示为其中的一个规范化特征矢量： V(d)=瓴，M@)；f：，％(d)；⋯；乙，％p)) (2—10) 式中fi既可以看是文档d中出现的所有单词，也可以看作是其中出现的所有 短语，以提高特征表示的准确性。 不同的特征项在文本中的重要程度也不同，因此需要对不同的特征项赋予不 同的权值，从而使越重要的特征项所具有的特征权值越大。对特征项赋权值的方 法主要有两种：一种方法是由专家或用户根据自身的经验进行人工赋值。这种方 法的主观性很强，且效率很低，很难用于大规模的文本处理；另一种办法是用统 计的方法，即用文本中的统计信息(如词频，词之间的同现频率等)来计算特征 项的权重。此时M@)被定义为特征项f，在文档d中出现的次数与文档总次数之 比(即出现频率，TermFrequency)坑似)的函数，即嵋(d)=V(坑(d))。一般取 V为TF-IDFi函数，即l王，z坑@)掌log(N／n；)，其中Ⅳ为所有文档的数目，嘎为含 有特征项t的文档数目。 由于11F．IDF公式存在很多变种形式，考虑到文本长度对权重的影响，还可 以对权重公式做归一化处理，这样就可以将各权重值规范N[0，11之间。归一化公 14 武汉理T大学硕十学位论文 式如下： w“，d)：一』丝竺丝丝丝兰坚∑ (2．11) ．／y【矿O，d)宰log(N／n(t)+O．01)12 、f忽 其中，w(t，d)为特征项t在文档d中的权重，矿O，d)表示特征项t在社区文 档d中出现的频率，Ⅳ为文档总数，，l(f)表示出现过特征项t的文档数。 在处理文本时还需要计算文本之间的相似度。文本之间相似度的计算有多种 方法可供选择，最简单的方法是只考虑两个特征矢量中所包含词条的重叠程度， 最常用的方法是考虑两个特征矢量之间的余弦夹角。即：Sim(d州d)；掣 (2-12) IdiI×Id』I 二、基于语义的Web文本分析技术 向量空间模型能够有效的将Web文本以结构化的形式表示，但其对文本的理 解的准确性不够高，容易引起歧义。而语义技术在消除歧义方面有很好的效果， 下面本文将介绍一种基于语义的Web文本分析技术：概念语义技术。 概念语义技术的基本思想是：基于机器学习方法生成概念语义空问【4引，在 概念语义空间中表示文本。 概念语义空间实际上是基于概念空间的语义索引。这是为克服关键词检索过 程中由于检索词的差异导致检索结果差异而建立的支持相关概念的索引机制。这 里所说的概念形式上表现为词，但并不是所有的词都是概念。概念是从语料中抽 取出来的用于表明一类文档特征的标识词，一类文档可能用不同的概念来标识。 例如“5．12汶川大地震"可以用“5．12"或“大地震”来进行标识，但当我们用“大 地震”检索时，会发现并不能返回仅包含“5．12”的文本。解决这一问题的一个 重要途径是共现分析，即通过统计同一类文本中两个词在同一篇文本中的共现 率，以发现它们之间的语义关联。概念语义空间将统计意义上概念或语义相似的 特征项归为同一个语义类别，而将有多个概念或语义指向的特征项归为不同的语 义类别，并给每个特征项赋以不同的权重，这些语义类别称为概念语义。例如， {“5．12"、“地震”、“天灾"】．及相应的权重。通常，概念语义及其权重通过统计 或机器学习方法获得。如果将与概念语义无关的特征项权重设为O，就可以在同 一个特征项集下以特征项为维度将概念语义表示为向量的形式，称之为概念语义 向量。概念语义向量组成的几何空间称为概念语义空间。这样，自然语言中的同 义词被映射到同一个概念语义中消除了表达上的差异，多义词可以通过不同概念 语义的比较来消除歧义。 经典的概念语义生成方法有3种：潜在语义索引(LSI)1441，概率潜在语义 索引(PLSI)1451年rl概念索引(CI)[461。这3种方法在概念语义表示的准确性以及 15 武汉理工大学硕士学位论文 处理大规模文本集时在算法实现上存在一些不足，不能同时满足概念语义表示的 准确性和算法实现的复杂性两方面的要求。为了解决这些问题，近年来一些学者 提出了概念语义生成的一些新方法，详见文献【47】和【48】。 2．3．2文本分类技术 文本分类是文本处理技术的核心，其任务是为文档集合中的每个文档确定一 个类别标识，使得可以通过限制查找范围以提高文档的查找效率，而且还可以方