搜索
搜索技术填空：30；名词解释：20；简答题：40；加粗为重点，加蓝为关键，为加粗为了解即可（有印象和概念）复习大纲：第一讲：搜索引擎：通常指的是收集了因特网上几千万到几十亿个网页并对网页中的每一个词（即关键词）进行索引，建立索引数据库的全文搜索引擎。原理：即经过爬虫爬行和抓取互联网上的网页，对网页的关键词建立索引，用户输入关键词后搜索引擎处理搜索词，从索引数据库中找出所有包含搜索词的网页并根据算法排序，按照顺序返回结果。评价：覆盖面更新周期响应速度排序结果是否满足用户的查询要求检索技术及流程：流程：网页爬取（Nutch；Heritrix）；网页预处理（内容提取（基于正则表达式；使用HTMLDOM）和去噪（VIPS算法））；分词（斯坦福大学自然语言处理；ICTCLAS；庖丁解牛分词；IKAnalyzer）；去停用词；Stem；建立索引（倒排表）；查询；Rank；用户反馈refinequery，relaxingquery。爬虫工作：网页的分析和过滤，URL种子的分析和抓取第二章：信息检索模型：分类：（1）：集合论模型：布尔模型、模糊几何模型、扩展布尔模型（2）：代数模型：向量空间模型、广义向量空间模型、潜在语义标引模型、神经网络模型（3）：概率模型：经典概率模型、推理网络模型、置信（信念）网络模型向量空间模型（VSM）：部分匹配的策略（出现部分词也可以出现在检测结果中），通过给查询或文档中的索引词分配非二值权值来实现（即索引词并不只有“1”和“0”，还有其中间数（相似度））。认为：cos(di,q)cos(dj,q)，则di比dj与q更相关（两者夹角越小，相似度越高）向量计算表示法：因为wij0和wiq0,0=sim(q,dj)=1文档dj的标记词只要能部分匹配查询语句的标记词，相似度大于0，有可能检索到。Tf（突出文档内在的特点），idf（减少所有文档中具有共同的特点的词的影响）tf（i,j）为文档中标记词出现的频率（freq（i,j））/max(（freq（i,j））)出现频率最高的词的频率；idf（i）为log（所有文档数N/ni包含标记词ki的个数）wij=tf(i,j)*idf(i)jdjqtiqijitiqijij),(向量空间模型优缺点：优点:帮助改善了检索结果。部分匹配的文档也可以被检索到。可以基于向量cosine的值进行排序，提供给用户。缺点:这种方法假设标记词是相互独立的，但实际可能不是这样，如同义词、近义词等往往被认为是不相关的词第三章：网页排序PageRank核心思想：PageRank是基于「从许多优质的网页链接过来的网页，必定还是优质网页」的回归关系，来判定所有网页的重要性。反向链接数，反向链接是否来自推荐度高的页面，反向链接源页面的链接数。HITS算法：PageRank算法中对于向外链接的权值贡献是平均的，也就是不考虑不同链接的重要性（有些链接是注释性，有些事导航和广告，若Google全都链接则全都有一样的权重）HITS算法：专注于改善泛指主题检索的结果，对每个网页都有两个值：权威值（authority）和中心值（hub）（权威网页：一个网页被多次引用，则它可能是很重要的；一个网页虽然没有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。这种网页称为权威（Authoritive）网页。Hub网页：提供指向权威网页的链接集合的WEB网页，它本身可能并不重要，或者说没有几个网页指向它，但是它提供了指向就某个主题而言最为重要的站点的链接集合，比如一个课程主页上的推荐参考文献列表。）HITS相比PageRank考虑了链出HITS算法评价：（1）若一个网页由很多好的Hub指向，则其权威值会相应增加(即权威值增加为所有指向它的网页的现有Hub值之和)（2）若一个网页指向许多好的权威页，则Hub值也会相应增加(即Hub值增加为该网页链接的所有网页的权威值之和)（3）HITS算法输出一组具有较大Hub值的网页和具有较大权威值的网页。PageRank与HITS比较：相同：都是基于链接分析的搜索引擎排序算法，并且在算法中两者都利用了特征向量作为理论基础和收敛性依据。不同：HITS算法计算的authority值只是相对于某个检索主题的权重；而PageRank算法是独立于检索主题。其他算法：Hilltop:指导思想与PageRank一致，主题相关网页间的连接权重大于主题不相关DirectHit：结果返回用户，跟踪用户点击，根据网页的浏览时间来增加减少相关度LearningtoRank：机器学习方法评价：查全率和查准率查全率(Recall)：检出的相关文档个数与相关文档集合总数的比值，即R=|Ra|/|R|查准率(Precision)：检出的相关文档个数与检出文档总数的比值，即P=|Ra|/|A|评价：R-查准率（序列中第r个位置的查准率）评价：NDCGDCG：一种总体观察检索排序效果的方法，利用检索序列加和的思路来衡量。面向用户的测度方法：覆盖率（已知）和新颖率（未知）第四章：优化搜索引擎WebSpam（网页作弊，使网页的排名高作弊方法）两个重要指标：1，与用户查询具有高相关性的网页，相关性越高排得越靠前；2，重要的网页，越重要排得越靠前。分类：针对基于相关性的排序策略的spam方法：termspam针对基于连接分析的排序策略的spam方法：linkspamSEO：SearchEngineOptimization搜索引擎优化是指在了解搜索引擎自然排名机制的基础上，对网站进行内部及外部的调整优化，改进网站在搜索引擎中的关键词自然排名。方法：黑帽Spam白帽（内部；外链）灰帽5种SEO手段（只需记住几种即可）：站内优化（静态化网页，去除对搜索引擎干扰的新技术；标明title信息；为图片加alt说明；建议给object标签加注释信息；不建议使用frame和iframe框架结构）网站url（系统中只使用正常形式的的url；）关键词位置，密度，处理（URL中出现关键词，网页标题出现关键词；关键词密度6-8%）内容质量，更新频率，相关性导入链接和锚文本增加反向链接（列表策略（针对某话题参考资料列表，行业专家名字），权威内容（简单易懂，添加“隐私政策”和“关于我们”页，增加权威））新闻和聚合（向高质量新闻门户提交新闻稿，与其他网站交换发表文章）目标、社会化书签（把网站提交给DMOZ-开放目录或其他免费目录；让你的文章加入百度搜藏、雅虎搜藏、Google书签、QQ书签等社会化书签。）合作伙伴、专业交换（交换链接，开发有用工具，发表并留下载地址）免费链接（在百度问答等留下链接）评论（博客评论可留自己名字和链接）会议和社会关系（找出名人的照片，留下自己的解说来吸引人）第五章：图像检索（主要是颜色）CBIR（基于内容的图像检索）CBIR的关键技术:图像特征提取和匹配：图像特征提取低层视觉与图像的具体类型或内容无关，颜色、形状、纹理等某些先验知识（或假设）人的面部特征指纹特征语义内容它包含高层的概念级反应(如“海上升明月”)对物体进行识别和解释，往往要借助人类的知识推理ColorFeatures颜色是彩色图像最底层、最直观的物理特征，通常对噪声，图像质量的退化，尺寸、分辨率和方向等的变化具有很强的鲁棒性，是绝大多数基于内容的图像和视频检索的多媒体数据库中使用的特征之一常用颜色空间：RGB空间；HSI空间（色调，饱和度，强度）；HSV空间（V，亮度（0~255））常用颜色提取特征方法及思想：颜色直方图（在颜色空间中采用一定的量化方法对颜色进行量化，然后统计每一个量化通道在整幅图像中所占的比重；缺点：未考虑空间）颜色相关图（用颜色对相对于距离的分布来描述信息，它反映了像素对的空间相关性，以及局部像素分布和总体像素分布的相关性。）颜色矩（在颜色直方图的基础上计算出每个颜色通的均值、方差、偏差，用这些统计量替代颜色的分布来表示颜色特征；它具有特征量少，处理简单的特点）第六章：文理分析纹理定义：一般说纹理就是指在图像中反复出现的局部模式和它们的排列规则纹理是低级层次的特征：纹理特征也是一种全局特征，它也描述了图像或图像区域所对应景物的表面性质；纹理特征的优缺点：优点：作为一种统计特征，纹理特征常具有旋转不变性，并且对于噪声有较强的抵抗能力。缺点：（1）当图像的分辨率变化的时候，所计算出来的纹理可能会有较大偏差；（2）由于有可能受到光照、反射情况的影响，从2-D图像中反映出来的纹理不一定是3-D物体表面真实的纹理。（虚假的纹理会对检索造成“误导”。）文理分析途径：Structural结构纹理分析：研究组成纹理的基元和它们的排列规则。基元可以是一个像素的灰度、也可以是具有特定性质的连通的像素集合。基元的排列规则常用树文法来描述。适合周期性好的纹理，比如棋盘，布纹适用范围较窄Statistical统计纹理分析应用最广寻找刻划纹理的数字特征，用这些特征或同时结合其他非纹理特征对图像中的区域（而不是单个像素）进行分类。Model-based模型法以图像的构造模型为基础，采用模型的参数作为纹理特征。典型的方法是随机场模型法马尔可夫（Markov）随机场（MRF）模型法Gibbs随机场模型法子回归模型、多尺度子回归模型、分形模型等Transform（Signalprocessingmethods)运用了信号分析的知识，主要包括傅立叶功率谱法、Gabor变换、小波变换等Tamura：Tamura纹理特征中所有纹理特征都在视觉上有意义6个心理学特征对比度(contrast)、粗糙度(coarseness)、方向性(directionality)对于图像检索尤为重要。线像度(1inelikeness)、规整度(regularity)和粗略度(roughness)。灰度共现矩阵：思想：是用不同邻接level灰度值的相邻状况来刻画图像的纹理特征，用有限的矩阵关系（numberoflevel)，表现纹理特征。并能在此基础上给出更多的统计量，进一步来刻画图像的纹理。第七章：形状形状：低级特征又有语义内容被认为是比颜色特征和纹理特征更高一层的特征。一个好的形状描述符应具备独特性、完备性、几何不变性：保持对平移、旋转、尺度变换的不变性。灵活性抽象性形状的描述符大体可以分为两大类：第一类是描述形状目标区域边界轮廓的像素集合，称为基于轮廓的形状描述符；第二类称为基于区域的形状描述符，是对形状目标区域内所有像素集合的描述；形状特征的有效表达必须以对图像中物体或区域的分割为基础。基于轮廓的形状描述：1.链码通过链码提取图像的关键点产生了一种相对于平移、旋转与尺度不变的表示方法链码是通过一个给定的方向上的单位尺寸的直线片段的序列来描述一条曲线或一个二维形状的边界。链码可以有效的描述轮廓形状而且可以大大减少边界所需要的数据量缺点链码对起始点要求很高，对噪声和边界线段的缺陷也很敏感，链码本身不具有旋转不变性。2.基于网格的方法将图像形状边界映射到一个标准的网格上，并将该形状边界调整到网格左上角，然后从左向右，从上到下扫描网格，若某个单元格被形状边界全部或者部分覆盖，则赋值1，否则赋值0，这样就得到了一个0.1组成的串，用来表征形状特征。求异或并统计1的个数判断相似性。该方法具有平移不变性，但是不具有旋转和尺度不变性解决方法：定义形状的主轴。为了得到旋转不变性，旋转改形状，使主轴平行于某特定的直线，例如x轴。为了得到尺度不变性，可以使主轴标准化为一个标准的主轴，固定长度。3.距离直方图求得形状质心，在边界上均匀取特征点，计算特征点到质心距离，建立起距离直方图。具有平移不变性和旋转不变性，为了使其具有尺度不变性，按特征点到质心的最大距离归一化，将所有距离值归一化到[0，1]区间。4.边界矩将边界点到质心的距离理解成一个分布，计算分布的矩。将低阶矩作为特征。5.傅里叶描述子auppien比较了各种典型形状识别方法的能力一，实验表明基于物体轮廓坐标序列的傅立叶描述子具有最佳的形状识别性能