信息采集 参考:W.Bruce Croft等著,刘挺等译. 搜索引擎-信息检索实践. 机械工业出版社,2010.

Slides:



Advertisements
Similar presentations
醫學美學之我見ー肉毒桿菌 班級:應日三乙 姓名:蔡雅卉 學號: 497E0076. 前言 現在的人,已經把 整型看做是微不足 道的事情了。即使 只是戴牙套、局部 雷射、割雙眼皮、 打美白針、肉毒桿 菌等等,都可以在 身體上做不同的改 變,而讓自己更滿 意自己的外表。
Advertisements

海伦深深地感激自己的老师, 她说:假如给我三天光明,我 首先要长久地凝视我的老师 — — 安妮 · 莎莉文 !
第五章 遵守社会公德 维护公共秩序 主讲人:王海斌.
资源平台应用培训 武汉市交通学校信息化建设指导委员会.
易物之家 有限责任公司.
高等教育出版社《哲学与人生》 第一课《客观实际与人生选择》说课 三原职教中心 许红.
《计算机应用基础》 第七章 计算机网络基础与应用
104年度國立宜蘭大學新進主管研討 主計業務宣導說明
第二章 网页艺术设计的技术基础.
公共部门人力资源管理课程导学 学习本课程的三步 3、利用网络 2、掌握方法 1、了解课程.
劳动关系法务-实操篇 规章制度修审与员工手册撰写.
102年實施之高中職及五專多元入學(含免試入學)之招生機制
读者与图书馆 2009年春季版 总第 15 期 山 东 交 通 学 院 图 书 馆 2009年3月.
姻緣天注定 定婚店 李復言.
讲故事训练 授课人:田轶.
怎样利用搜索引擎检索网络资源 1. 网络的基础知识
第十九讲 道德教育有效性问题研究 问题一 您们对我国 学校德育 的效果怎 样评价? 原因?.
第十一課 菜園 6-11.
Web与信息检索 LJ JUFE-SIT.
校本选修课 第三专题 西藏问题 北京师大二附中 李文燕.
2012级暑期放假安全教育 及宿舍搬迁工作布置会 北京化工大学理学院 辅导员:曹鼎 2013年6月6日.
第七章 人与生物共生.
汇报大纲 一、报送系统总体介绍 二、自查及检查评分报送流程 三、自查及检查方法及关键点 四、建议及注意事项.
第三节 树立正确的恋爱婚姻观 思政课部:陈兰兰.
网页制作与网站设计教学课件 网页制作与网站设计课程组开发
实训十四、IE浏览器的基本应用.
学习情境三:配置WEB服务器 服务器配置与管理.
正修科技大學教學發展中心 教師教學觀摩與經驗分享 電子工程系 張法憲副教授.
俄语字母的发音体系 阅读规则.
中文百科在线介绍 中文百科在线介绍 1 核心竞争力 2 数据优势分析 3 中文百科在线资源 4.
2015年云南财经大学图书馆 新生入馆教育考核试题 答题指南
第8章 信息获取与发布 《大学计算机基础》 桂林电子科技大学 陈辉金 适用教材:周娅等. 大学计算机基础.桂林:广西师范大学出版社,2013
国际关系的决定因素:国家利益 江苏省震泽中学 丛海啸.
中学生网络安全教育.
蘇軾詞的賞析
模块七 信息获取与发布 第8章 计算机网络信息的获取与发布.
柯奕宏(06) 王予亨(13) 郭秉逸(15) 楊雯凈(23) 顏佑瑩(32)
第十五章 传播学调查研究方法.
自然與生活科技領域 認識太陽能 蘇紋琪、石明玉.
Ch1.認識全球資訊網 1.1 「網際網路」與「全球資訊網」 1.2 全球資訊網的基礎 – 網頁與超連結
 全能的天才畫家- 李奧納多‧達文西 (西元1452年-1519年) 指導老師:袁淑芬老師 製作人:饒佩芯.
網站架構與網頁設計基礎 清雲科技大學資管系 歐陽芳泉.
認識網際網路 網際網路(Internet)簡介 WWW簡介 臺灣地區網路資源 網路禮儀與規範 收發電子郵件 相關程式與服務
認識FTP檔案傳輸協定 建立我的部落格 Archie檔案檢索服務 Google搜尋密技 歷久彌新的老朋友-BBS Skype網路電話
考试题型 填空题(30) 选择题(20) 名词解释(10) 问答题(24) 计算题(16) 附加题(30) 成绩核算:
NAMO網頁製作教學簡報 講師:李惠茹.
網頁製作 網頁製作軟體 網頁瀏覽軟體 網頁圖像製作軟體 HTML語言 網站登錄.
認識我的故鄉_台中市.
欢迎各位 Nice to Meet U.
古佳怡 網路爬蟲、分析與視覺化.
实例导入:西部旅游网 | 页面属性的设置|文本的修饰|设置超级链接|制作纯文本网站|使用图像
Web前端开发 第23章:网站发布 阮晓龙 / 河南中医药大学管理科学与工程学科
企业商品网络营销策划实训.
网页设计与制作 Dreamweaver CS6 标准教程
第4章 TCP/IP应用层常用协议 4.1 Telnet 协 议 4.2 文件传输协议FTP 4.3 电子邮件的工作原理及其协议
網路安全期末報告 -網路釣魚     學生:A 蘇育諄     指導教授:梁明章 教授.
精忠报国  演唱:屠洪纲 作词:陈涛 作曲:张宏光  狼烟起 江山北望  龙起卷 马长嘶 剑气如霜  心似黄河水茫茫  二十年 纵横间 谁能相抗  恨欲狂 长刀所向  多少手足忠魂埋骨它乡  何惜百死报家国  忍叹惜 更无语 血泪满眶  马蹄南去 人北望  人北望 草青黄 尘飞扬  我愿守土复开疆  堂堂中国要让四方来贺.
SEO SEO优化演示方案.
2012温州市“深化普通高中课程改革”信息技术学科培训
樂樂請假了 尊重的故事 資料來源:臺北縣國民小學品德教育手冊 故事來源:臺北縣國民小學品德教育手冊 網路小故事
ASP动态网页设计实用教程 主讲教师:贾海陶.
聽聽那冷雨---重點摘要 二愛 王煜榕.
【VA虚拟应用管理平台】专题培训 接入防火墙 陕西益和信息技术开发有限责任公司 2011年2月.
憲政與民主 應化3A 邱泓明.
搜尋引擎最佳化.
大数据应用人才培养系列教材 数据清洗 刘 鹏 张 燕 总主编 李法平 主编 陈潇潇 副主编.
古蹟知性之旅 我和新港奉天宮有個約 報告人:陳 映 竹 傅 湘 甯.
2018选考复习 信息技术基础知识(一).
第1章 WWW和LAMP基本觀念.
第7章 Internet的应用.
Presentation transcript:

信息采集 参考:W.Bruce Croft等著,刘挺等译. 搜索引擎-信息检索实践. 机械工业出版社,2010

主要内容 信息采集(网络爬虫,Crawler) 重复检测 去除噪声

网络爬虫 困难: 规模:网页采集,存在很多特殊问题,最大的问题是互联网的规模。目前“至少”(没人知道多少)有上百亿网页 不受控:不知道一个网站有多少页面,更不知道有哪些页面,有些页面其创建者不希望搜索引擎获取,至少不能频繁地获取以影响网站正常服务 深网:有些数据需要填写表单才能获取

网络爬虫 URL(uniform resource locator) 访问网页的过程 组成:协议方案,主机名,资源名 例:http://sit.jxufe.edu.cn/index.html 访问网页的过程 域名解析:从域名到IP地址 连接服务器:客户端程序连接IP地址所对应的服务器 发送请求:客户端发送请求(如HTTP请求)到服务器,请求页面 返回信息:服务器先发一个简单的头部信息,再将文件的内容返回给客户端 关闭连接。

网络爬虫 从种子集合开始,将种子集合中的URL添加到请求队列。从请求队列中取出 URL,抓取网页,并对网页进行解析,从中提取链接,将有用的URL添加到请求队列中。重复该过程直到队列为空或存储空间用完为止。

信息采集的概念 主要是指通过Web页面之间的链接关系从Web上自动获取页面信息,并且随着链接不断向所需要的Web页面扩展的过程,信息采集系统也常常称为Robot, Spider, Crawler等等 信息采集是搜索引擎获得数据来源的过程,地位相当重要 信息采集的目标:快速获得高质量的网页 信息采集是一项十分繁杂和庞大的工程 不同的协议 不同的网络情况 时效性的要求 网页质量的要求 实际上是图的遍历过程 通过种子页面或站点(Seed),获取更多的链接,将它们作为下一步种子,循环 这个过程一般永远不会结束!

信息采集的基本结构 这个部件主要给待采集的URL排序,并根据一定的策略向协议处理器分配URL 主要通过各种Web协议来完成数据的采集。一般来说协议包括HTTP、FTP、Gopher以及BBS 信息采集的基本结构 内容包括已采集页面的Meta信息、Anchor信息、页面的标题、页面的摘要等。获取它们的主要目的是力图在没有对页面内容语义信息进行理解的前提下,尽可能多的挖掘meta、结构等的语义信息,来为从这些页面中提取出来的URL的好坏,给出一个度量。 语义信息解析就是指对文本内容建立简单的索引

采集的遍历算法 宽度优先vs. 深度优先 网站采集vs. 全局URL采集 宽度优先:先采集完同一层的网页,再采集下一层网页 深度优先:先沿一条路径采到叶节点,再从同层其他路径进行采集 有研究表明:宽度优先的方法得到的网页集合的重要性更好 网站采集vs. 全局URL采集 网站采集:一个网站一个网站采集 全局URL采集:将所有URL放入一个URL池,从中使用某种方法进行选择 网站采集在支持应用方面灵活性大一些,但是采集效率可能不如全局URL采集,通常的搜索引擎采用全局URL采集的方法。

采集网页的更新策略 定期重采:一段时间以后重新采集所有网页,全部采完以后替换原来的网页 增量采集:只按照某种策略采集那些可能新增、变化的网页,并删除那些已经不存在的网页 定期重采非常简单,但是浪费带宽,周期也长;增量采集可以节省带宽,网页更新周期相对较短,但是系统的复杂性增大。 Http协议有个称为HEAD的特殊请求,只返回头信息而不是全部页面,方便检查网页是否更新过。

采集网页的速度保证措施 本地DNS解析:把DNS解析任务放在本地机上,即提交的地址都是解析后的IP地址。 多机分布式并行 单机多程序并行 局域网联接多机进行采集并行 广域网分布式采集 单机多程序并行 多进程并行 多线程并行

采集网页的质量保证措施 减少重复页面的采集 保证重要页面的高优先级 URL重复的检测和排除 内容重复的检测和排除 入度高的网页相对重要 对于完全重复的网页:MD5算法为每个网页生成一个128位的信息摘要 对于近似网页(Broder,1997):先规范化为词条数据流,再提取出子字符串(shingle),比较两个网页中shingle的重叠程度。为每个shigle计算哈希值(64位)。为保证效率,删除其中的大部分shingle(如所有哈希值模m后不为0的,m=25适合web数据) 保证重要页面的高优先级 入度高的网页相对重要 URL浅的网页相对重要 含有被别人广泛映像的内容的网页重要

采集中的“礼貌”问题 遵守网站上发布的Robot.txt采集限制协议 文档信息源 User-agent: * Disallow: /private/ Disallow: /other/ Allow: /other/public/ User-agent: FavoredCrawler (对这个爬虫有以下的规则) … Sitemap:… (网站地图:告诉爬虫网页的位置,更新信息等) 文档信息源 类似于网站地图,主要用于描述那是出版物等时间不敏感的资源。 采集时尽量不要太过密集地采集某个网站,这种密集访问类似于DoS攻击,导致普通用户正常浏览网站产生困难。有些网站会严密控制这种密集访问行为。

信息采集的研究趋势 基于主题的信息采集 深网数据采集 信息采集及抽取 采集某个领域的数据。选择种子、利用页面中的锚文本、页面分类 深层网络的规模是传统网络规模的100倍(估计) 三类: 私人站点:没有指向它的链接,或者需要进行注册 表单结果:向表单中填写数据后才能进入,如销售机票等 脚本页面:使用javascript,链接并不是以HTML语言给出,而是通过在浏览器中运行javascript生成。 信息采集及抽取 采集后提取结构化信息

重复检测 研究表明,在一个大型的信息采集系统中,30%的网页是和另外70%的网页完全重复或近似重复的。 也有估计认为,Web中大概有40%的网页和其他网页重复。 这些重复包括: 抄袭(plagiarism) 垃圾(spam) 镜像(mirror) 种类主要两类:完全重复、近似重复

重复检测 – 完全重复 相对简单,例如使用“检验和”(checksumming)技术 根据文档内容计算一个数值。最直接的就是文档中各字节的和 例如:一个含有文本“Tropical fish”的文件,检验和可以是其中各个词符的ASCII的和(包括空格),即54+72+6F+…+68=508 含有相同文本的任意文档,它们会有相同的检验和。 也存在文本包含的字符相同,但顺序不同,计算的检验和也相同。因此,可以考虑更复杂的检验和函数,比如考虑字节出现的位置。

重复检测 – 近似重复 如何快速判断近似重复? 对于有N个文档的集合,判断其中全部的近似重复文档需要文档两两比较,开销为O(N2) 将长文档用它的“指纹(fingerprint)”来表示,减少两文档比较时的开销。

重复检测 – 近似重复 指纹生成过程 对文档进行分词,删除不是词的内容,如标点、HTML标签、空格 将词组合成n-gram 选择其中的一些n-gram,用于表示该文档。通常不是随机地选择,因为从内容重复的D1和D2两个文档中随机选择n-gram,重复的可能性比较小。更有效的方法是从事先制订的字符组合中选择以这些字符开始的n-gram。这些n-gram就是指纹。 对被选择出来的n-gram进行散列,以提高检索效率,并减少文档大小。每个n-gram对应一个散列值。(选择n-gram也可根据散列值模P为0的原则来选择) 对散列后的指纹进行倒排索引。方便快速匹配。 对于一个文档,要找其近似重复文档,可以先生成该文档的指纹,再根据指纹查倒排索引。然后根据检索的结果判断重复的指纹数量占总数量的比例,做为文档的重复程度。 基于指纹的方法在效果上并不如基于词表的相似度计算(余弦相似度),但效率更高。

重复检测 – 近似重复 Simhash(Charikar, 2002) Simhash指纹生成过程 吸取了基于词的相似度计算的优点,以及基于散列的指纹技术的高效性。 相似的文档具有相似的散列值。 Simhash指纹生成过程 利用具有权值的特征集合表示文档 对每个词,生成b位的散列值 在b维向量V(文档中全部词,每个词b维)中,分别对每维计算:如果相应位的散列值为1,对相应的特征权值做加法,否则,做减法 所有词处理完后,如果向量中的第i维为正,则最终的b位指纹中第i位为1,否则为0

重复检测 – 近似重复 Simhash举例 原始文档:Tropical fish include fish found in tropical environments around the world, including both freshweat and salt water species. 对词加权后:tropical 2 , fish 2, include 1, found 1, environments 1, around 1, world 1, including 1, both 1, freshwater 1, salt 1, water 1, species 1 8位散列: 对权值求和 tropical 01100001 -2 2 2 -2 … fish 10101011 2 -2 2 -2 include 11100110 1 1 1 -1 found 00011110 -1 -1 -1 1 environments 00101101 … around 10001011 world 00101010 including 11000000 both 10101110 freshwater 00111111 salt 10110101 water 00100101 species 11101110 最终的8位指纹是: 10101111 1 -5 9 -9 3 1 3 3

重复检测 – 近似重复 Henzinger(2006)使用了基于大规模网页的评价方法评价simhash,他使用的指纹为384位。如果一个网页和另一个网页的simhash指纹中有多于372位是相同的,那么这两个网页就是近似网页。 研究表明,simhash指纹比n-gram指纹方法有更好的效果。 实验 中的simhash python 程序,基本思路如上所述。知道 全部文档的指纹,要比较与某文档d近似重复度最高的(或高于某阈值)的文档,还是要比较全部文档的指纹与d的指纹(做与运算即可)。 为了进一步提高效率,将b位进行分段并索引存储。对于文档d的指纹,首先分段,然后从索引中检索可能近似重复的文档,只与这些文档的指纹进行比较。

去除噪声 网页中经常包含文本、链接、图片等,真正的内容块所占的比例并不高,还有其它如广告、版权等信息。

去除噪声 基于标签分布(Finn, 2001) 基本思路:网页中主要内容部分的文本会比网页中附加(噪声)内容的文本中含有更少量的HTML标签 右图是http://sit.jxufe.edu.cn/yxjs_show.asp?id=1290的文档斜率曲线(2015-8-30号的网页内容),词素是以字符为单位的,受英文单词、数字影响比较大。对于中文,可以只统计汉字,对于英文,以单词为单位比较好。 如何找到中间的平坦区域?

去除噪声 基于标签分布(Finn, 2001) 检测最大平坦区域 不足: 使用二进制位序列对网页进行表示,bn=1表示第n个词素(汉字、单词)是一个标签,否则bn=0。表示字体变化、标题和表格的标签可以忽略掉,即用0表示,因为它们已经是正文。 主要内容检测可以看成是一个优化问题,即最大化低于i和高于j的标签数量,以及在i和j中间的非标签词素的数量。 𝑛=0 𝑖−1 𝑏𝑛 + 𝑛=𝑖 𝑗 (1−𝑏𝑛) + 𝑛=𝑗+1 𝑁−1 𝑏𝑛 不足: 只有非内容块中文本词素的比例小于标签比例时,上述目标函数才起作用。当然,可以适当增加非标签词素的权重来调整 另外,不能处理网页中有分散的多个内容块的情况。(可以使用窗口来解决)

去除噪声 基于网页结构 DOM(文档对象模型)将网页表示为类似于树的结构,可以用来识别网页中的主要部分。 Gupta等(2003)提出一种方法,递归遍历DOM树,使用不同的过滤技术来删除和修改树中的节点,只留下内容部分。HTML中的图片、脚本等很容易用简单的过滤去掉,而复杂的过滤技术用于去除广告、链接等。 BeautifulSoup是python中用于解析网页的重要工具。 不足:复杂,只是根据格式而没考虑语义。例如,HTML中使用表格,有时只是为了网页的布局。解决方法是结合网页的布局和视觉特征。

基于视觉特征