人工智能在搜索引擎资源获取中的应用.docx

人工智能在搜索引擎资源获取中的应用 1、A*算法概述 A*算法是对估价函数加上一些限制后得到的一种启发式搜索算法。 假设f*(n)为从初始节点S出发，约束经过节点n到达目标节点的最小代价值。估价 函数f(n)则是f* (n)的估计值。明显，f* (n应由以下两部分所组成:一部分是从初始 节点S到节点n的最小代价，即为g* (n);另一部分是从节点n到目标节点的最小代价， 记为h* (n)，当有多个目标节点时，应该取其中代价最小的一个。因此有 f* (n=g*(n)+h*(n) 把f(n)与f* (n相比，g(n)是对g*(n)的一个估计，h(n)是对h*(n)的一个估计。 于是，当要求估价函数f(n)中的h(n)都小于等于h*(n)即 时，就得到了A*算法。 如果某一问题有解，那么利用A*搜索算法对该问题进行搜索则一定能搜索到解，而 且一定能搜索到最优的解。 2、*A算法的程序编写 有八数码问题:在一个3/3的九宫中有1一8这8个数及一个空格随机的摆放 在其中的格子???，如下图左图所示。现在要求实现这个问题:将该九宫格调整为如下 图右图所示的形式。调整的规则是:每次只能将与空格(上、下、或左、右)相邻的 一个数字平移到空格中。 图3.4 用A*算法求解，必须先设计估价函数，设估计函数f (n)=g (n)+h (n) 其中，g (n)为表示搜索树中节点的深度，h (n)表示节点n中放错的数码个数。 由此可以得到以下状态空间的搜索过程图。 每个状态被标上了相应的估价函数值。实线路径为A*算法的搜索路径。 3、web页面中链接的特点 明显在web页面中，链接不是单纯的以链接暴露给用户，而是以相关的文字信息表 示，比如在yahoo中，shopping的链接是/r/sh这样可以使用户在看 到文字信息的时候大体知道该链接指向的是什么方面的内容。Shopping表示的就是购物 方面的内容。因此这部分的信息对自动化的网络爬虫来说也是相当重要的。在实际设计 爬虫中要考虑链接的这些特点。 另外，除去链接的文本信息，链接本身也能提供一些关于该链接中内容的相关信息， 比如这个链接，我们可以发现，里面包含了一个shoppnig的关 键字，该链接指向的页面为购物相关的页面，因此链接有时候也能提供页面的内容信息。 所以在设计的时候要考虑以上两种特征。在估值函数中必须要对链接文本的信息和链接本身的信息作出判断。因此必须建立一个相关的知识库，在试验中以保存在文本中的关键字来表示，这些知识库为爬虫程序提供了对链接判断的依据。以shopping为例，相关的关键字应该包括，shop store sell buy等。 4、估价函数的内部流程 当获取一URL后，估值函数对其进行判断，如果为门户型网站则获取其站内链接， 对这些链接进行判断，是否含有关键字表中所列的关键字，如果有则对该url的估价值加 20。没有则返回。如果该链接是一般的主题网站网址，则获取其外部链接，如果这些链 接中含有关键字，则该链接的估价值加10。站内的链接估价值要比外部的高，因为这样 可以使该站有价值的页面尽快被访问，而不需要等以后访问其他网页后重新访问。可以 减少客户和服务器重新链接带来的开销。 5、页面判断中使用的智能代理技术 在系统获取URL，对该URL进行访问后，要判断该页面到底是否属于想要获取的网 站，那么这就要对该页面的内容进行分析判断。 智能代理技术是人工智能中一个比较新的技术，可以代表用户，完成相应的任务。 浙江大学硕士学位论文人工智能在搜索引擎资源获取中的应用 它能够感知周围环境，并且作用于环境。智能代理需要通过内建的知识库和感知到的信 息来采取行动。一个好的智能代理系统，应当有学习的能力，通过感知到的知识不断学 习，从而适应环境的不断变化情况。在本文所提到的页面判断智能代理中，为了简化问 题的复杂性，只使用内建知识库来判断所要处理的网站是否是需要的那种类型的网站。 6、文本表示方法 文档表示模型一般有两种，向量空间模型和布尔模型。在本文中，使用向量空间模 型来表示。 向量空间模型的基本思想是以向量来表示文本:(W1，W2，W.3··…Wn)，其中Wi为第i 个特征项的权重，那么选取什么作为特征项呢，根据实验结果，普遍认为选取词作为特 征项要优于字和词组，因此，要将文本表示为向量空间中的一个向量，就首先要将文本 分词，由这些词作为向量的维数来表示文本，最初的向量表示完全是O、1形式，即， 如果文本中出现了该词，那么文本向量的该维为1，否则为O。这种方法无法体现这个 词在文本中的作用程度，所以逐渐O、1被更精确的词频代替，在本文中，使用该词出 现的次数当作词频v]l。 单词是一个文档的基本元素，分析文档的特性就是分析其所包含的各种单词情况。 一般来说，常用词有较高的出现频率，孤僻