小型搜索引擎设计及实现v1.1ppt课件.ppt

小型搜索引擎设计及实现信息系统建模课程项目,彭祯卫罡薛鲁国柳俊全何浩,01,数据采集与预处理,02,系统模型设计及构建,03,系统实现与可视化,目录,CONTENTS,2,课程项目要求,一个至少能支持10个以上网站的爬虫程序，且支持增量式数据采集；并至少采集10000个实际网页；针对采集回来的网页内容，能够实现网页文本的分类；可进行重复或冗余网页的去重过滤；对经去冗以后的内容建立倒排索引；采用PageRank算法、HITS算法、SALSA算法或其他你认为合适的算法，实现搜索结果的排序；支持自然语言的模糊检索；可实现搜索结果的可视化呈现。可以在线记录每次检索的日志，并可对日志数据进行统计分析和关联挖掘。,数据采集与预处理,系统模型设计及构建,系统实现与可视化,3,项目具体分工,组长：卫罡，系统前端组员：薛鲁国，系统后台：数据采集及预处理，话题发现彭祯，系统后台：elasticsearch，柳俊全，系统前端，系统文档，何浩，系统后台：PageRank，,4,01数据采集与预处理,5,1,2,3,构建数据采集模型,设计数据存储格式,预处理数据并存储,主要工作,6,1.1构建数据采集模型,Spider抓取系统,URL存储系统URL选取系统DNS解析服务系统抓取调度系统网页分析系统URL提取系统URL分析系统网页存储系统,包含8大子系统,7,1.1构建数据采集模型,Scrapy基本框架,1.ScrapyEngine从Scheduler中取出一个URL用于接下来的抓取；2.ScrapyEngine把URL封装成一个Request传给Downloader；3.Downloader下载资源，并封装成Response；4.Spiders解析Response；5.解析出Item，交给Pipeline进行下一步处理；6.解析出URL，把URL交给Scheduler等待抓取。,8,1.1构建数据采集模型,数据采集两种方式累积式采集：从某一个时间点开始，通过遍历的方式抓取系统所能允许存储和处理的所有网页。经过足够时间，该策略可以保证抓取到相当规模的网页集合。由于web数据的动态性，累积式抓取到的网页集合事实上并无法与真实环境中的网络数据保持一致。增量式采集：在一定量规模的网络页面集合的基础上，采用更新数据的方式选取已有集合中的过时网页进行抓取，保证所抓取到的数据与真实网络数据足够接近。累积式爬取一般用于数据集合的整体建立或大规模更新，增量式采集则主要针对数据集合的日常维护与及时更新。,9,1.1构建数据采集模型,增量式数据采集使用MongoDB数据库记录每个爬虫爬取到的新闻的最大时间根据每个新闻网站的更新频率设置爬虫爬取时间间隔，爬取更新的新闻后台持续运行爬虫程序使用布隆过滤器（BloomFilter）去掉重复的URL（BloomFilter保存上一次爬取的数据，根据增量规则对保存的状态数据进行约束，从时间和空间上提升性能）,10,1.1构建数据采集模型,十大站点,爬取网页数据量：3万+,11,1.1构建数据采集模型,九大类别,12,1.2设计数据存储格式,13,1.3数据预处理并存储,数据预处理提取关键词（建立DocView模型）消除重复或冗余网页（根据向量模型计算余弦相似度）链接分析（应用TF-IDF统计方法，提取文本特征，进行文本分类）计算网页重要程度（“被引用得最多的就是最重要的”，PageRank算法）,14,1.3数据预处理并存储,15,02系统模型设计及构建,16,系统模型设计及构建,TextGrocery分类工具,Elasticsearch全文检索,网页文本分类TF-IDF,网页去重过滤,PageRank网页排序,模糊检索,话题发现,17,2.1网页文本分类,Step1预处理,Step2中文分词,Step3结构化表示,Step4TF-IDF策略,Step5SVM分类器,Step6TextGrocery分类工具,1,2,3,4,5,6,得到训练集语料库得到测试集语料库,基于概率图模型的条件随机场（CRF）Jieba分词法,构建词向量空间模型,构建TF-IDF词向量空间生成权重矩阵,二类分模型，特定空间上间隔最大的线性分类器,基于LibLinear和结巴分词,18,2.1网页文本分类,文本特征提取TF-IDF词频-逆文件频率，是一种用于资讯检索与资讯探勘的常用加权技术。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF，某一个给定的词语在该文本中出现的次数。=单词在文本中出现的次数该文本总单词数IDF，包含某一词条文档越少，则IDF越大，该词条具有很好的类别区分能力。=log(语料库文本总数包含该单词文本数),19,2.1网页文本分类,SVM支持向量机是一个二分类的分类模型，定义为特征空间上的间隔最大的线性分类器。给定一个包含正例和反例的样本集合，根据正例和反例寻找一个超平面对样本进行分割。,20,2.1网页文本分类,TextGrocery分类工具基于LibLinear和结巴分词的短文本分类工具，特点是高效易用，同时支持中文和英文语料。API：Grocery，GroceryPredictResult，GroceryTestResult性能，训练集：来自32个类别的4.8万条中文新闻标题；测试集：来自32个类别的41.6万条中文新闻标题。,21,2.2网页去重过滤,余弦相似度也称余弦距离，取值在-1,1，余弦值越接近1，表明夹角接近0度，两个向量越相似。对于二维向量a(1,1)和b(2,2)，它们的夹角余弦计算如下：cos=|b|=12+1212+1222+22对于n维向量a(1,2,)和b(1,2,)，夹角余弦cos=|b|=1n()=1n()2=1n()2,判断条件：cos（0.9，1）表明内容冗余，需删除,22,2.3Elasticsearch全文检索引擎,Elasticsearch是基于Lucene构建，是一个分布式可扩展的实时搜索和分析引擎，提供了RESTAPI操作接口。另外，实现分布式实时文件存储，并将每一个字段都编入索引，使其可以被搜索；实现实时分析；可扩展到上百台服务器，处理PB级别的结构化或非结构化数据。中文分词器一般使用第三方的ik分词器、mmsegf分词器和paoding分词器。本系统选择ik分词器。Elasticsearch使用lucene倒排索引，相比关系型数据库的B-Tree索引快。并支持模糊检索。,23,2.3Elasticsearch全文检索引擎,Lucene倒排索引，通过由属性值来确定记录的位置。是实现“单词-文档矩阵”的一种具体存储形式，可以根据单词快速获取包含这个单词的文档列表。主要由“单词词典”和“倒排文件”组成。,lucene框架,24,2.3Elasticsearch全文检索引擎,(0)设有两篇文章1和2文章1的内容为：TomlivesinGuangzhou,IliveinGuangzhoutoo文章2的内容为：HeoncelivedinShanghai.(1)获取关键字全文分析：由于lucene是基于关键词索引和查询的，首先取得这两篇文章的关键词，通常需要如下处理措施:a.先要找出字符串中的所有单词，即分词。英文单词由于用空格分隔，比较好处理。中文单词间是连在一起的需要特殊的分词处理。b.文章中的”in”,“once”“too”等词没有什么实际意义，中文中的“的”“是”等字通常也无具体含义，这些不代表概念的词可以过滤掉c.用户通常希望查“He”时能把含“he”，“HE”的文章也找出来，所以所有单词需要统一大小写。d.用户通常希望查“live”时能把含“lives”，“lived”的文章也找出来，所以需要把“lives”，“lived”还原成“live”e.文章中的标点符号通常不表示某种概念，也可以过滤掉经过上面处理后:文章1的所有关键词为：tomliveguangzhouiliveguangzhou文章2的所有关键词为：heliveshanghai,25,2.3Elasticsearch全文检索引擎,(2)建立倒排索引有了关键词后，就可以建立倒排索引了。上面的对应关系是：“文章号”对“文章中所有关键词”。倒排索引把这个关系倒过来，变成：“关键词”对“拥有该关键词的所有文章号”。文章1，2经过倒排后变成:通常仅知道关键词在哪些文章中出现还不够，还需要知道关键词在文章中出现次数和出现的位置，通常有两种位置：a)字符位置，即记录该词是文章中第几个字符（优点是关键词亮显时定位快）；b)关键词位置，即记录该词是文章中第几个关键词（优点是节约索引空间、词组（phase）查询快），lucene中记录的就是这种位置。,26,2.3Elasticsearch全文检索引擎,加上“出现频率”和“出现位置”信息后，我们的索引结构变为：以live这行为例我们说明一下该结构：live在文章1中出现了2次，文章2中出现了一次，它的出现位置为“2,5,2”这表示：文章1中出现了2次，那么“2,5”就表示live在文章1的关键词中出现的两个位置，文章2中出现了1次，剩下的“2”就表示live是文章2的关键词中第2个关键字。以上就是lucene索引结构中最核心的部分。我们注意到关键字是按字符顺序排列的（lucene没有使用B树结构），因此lucene可以用二元搜索算法(或叫二分查找/折半查找)快速定位关键词。,27,2.4网页排序,最早的搜索引擎采用分类目录的方法，通过人工进行网页分类并整理出高质量的网站。随着网页越来越多，进入了文本检索时代，通过计算用户查询关键词与网页内容的相关程度来返回搜索结果，但效果不好。谷歌创始人，当时还是美国斯坦福大学(StanfordUniversity)研究生的佩奇(LarryPage)和布林(SergeyBrin)开始了对网页排序问题的研究。他们借鉴了学术界评判学术论文重要性的通用方法，那就是看论文的引用次数。由此想到网页的重要性也可以根据这种方法来评价。于是PageRank的核心思想就诞生了。,28,2.4网页排序,PageRank排序，如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高；如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高。,PageRank算法总的来说就是预先给每个网页一个PR值（下面用PR值指代PageRank值），由于PR值物理意义上为一个网页被访问概率，所以一般是1，其中N为网页总数。一般情况下，所有网页的PR值的总和为1。预先给定PR值后，通过下面的算法不断迭代，直至达到平稳分布为止。,29,2.4网页排序,根据每个网页的超链接信息计算网页的权值，一个页面的得分情况由所有链向它的页面的重要性经过加权计算得到的。,PR=1+()(),PR：页面的PageRank值；：阻尼系数，由于某些页面没有入链接或者出链接，无法计算PageRank值，为避免这个问题（即LinkSink问题），而提出的。阻尼系数常指定为0.85。()：页面Pi的PageRank值；()：页面链出的链接数量；根据引用度做了相关排序,PageRank计算初始值相同,30,3.3可视化之PageRank,31,2.4网页排序,利用PageRank链接增强思想，计算新闻网页权值。,所有节点初始rank值为1，迭代10次后网页结果,32,2.5话题发现,33,2.5话题发现,LDA简介,为主题概率的概率分布，Dirichlet参数d为文档d下的主题概率分布Zd,n为第n个词项文档d产生的主题Wd,n为主题产生的词项，实际变量为主题词项概率分布，为使满足Dirichlet分布的参数,34,03系统实现与可视化,35,系统实现与可视化,整体设计,系统实现,系统可视化,36,3.1系统整体设计,Web系统构架,Web系统采用MVC设计模型，使页面代码与模型相隔离，降低了系统的耦合度，具有较好的扩展性。,37,3.2系统后台实现,Django是使用python的开放源代码的web应用框架Django是MTV结构即Model，Template，ViewModel层：定义数据的存储格式，提供数据库访问的APITemplat