网络数据挖掘考试重点

1、Web Data mining复习与总结一、 课程主要内容数据挖掘概述+WEB数据挖掘数据挖掘（ch1 概述）：又被称为数据库中的知识发现（）。是指从数据源（如DB、文本、图片、万维网等）探寻有用的模式或知识的过程。这些模式必须是有用的、有潜在价值的、并且是可以被理解的。数据挖掘是一门多学科交叉的学科，包括机器学习、统计、数据库、人工智能、信息检索和可视化。WEB数据挖掘（ch6-12）的目标是从web超链接、网页内容和使用日志中探寻有用的信息。依据挖掘过程中使用的数据类别，web挖掘的任务划分为三种主要的类型：web结构挖掘、web内容挖掘和web使用挖掘。web结构挖掘：从表征web结构的

2、超链接中寻找知识。Ch6-ch8：信息检索与web搜索；链接分析；web爬取。web内容挖掘：从网页内容中抽取有用的信息和知识。Ch9-ch11：结构化数据抽取：包装器生成；信息集成；观点挖掘。web使用挖掘：从记录每位用户点击情况的使用日志中挖掘用户的访问模式。Ch12：web使用挖掘二、 各章主要知识点（一） （ch1）概述主要知识点1、 万维网、超文本、超链接、超媒体的概念；2、 HTTP，HTML，URL， WEB，TCP/IP的含义；3、 Web数据的特点：P56；4、 数据挖掘的定义、数据挖掘任务、KDD过程、KDD的数据类型等；5、 Web数据挖掘的定义、分类、web数据挖掘过程

3、等。6、 关联规则、列模式挖掘、分类与预测、聚类挖掘的基本概念及挖掘思想。WEB结构挖掘：包括信息检索与WEB搜索、链接分析、WEB爬取（二） （ch6）信息检索与web搜索1、 基本概念：（1）信息检索IR：即帮助使用者从大号的数据集信息中发现需要的资料。了信息的采集、组织、存储、检索及分发。根据用户的查询信息得到相应的一组文档，得到的结果根据其与用户查询信息的相关程序排序，最常用的用户查询信息是一组关键字（又称词）。其基本信息是单个文档，大量的文档形成文本数据库。（2）web搜索：是信息检索的一个重要分支。区别于信息检索的特点是：效率是WEB搜索的一个最为重要的问题；网页与传统信息检索系统

4、中使用的普通文档不同：（1）具有超链接以及锚文本、（2）网页是半结构化的、（3）网页中的内容基本上是有组织的，并且在一些结构块中出现；作弊技术是网络上的一个重要的问题。（3）IR基本架构：用户查询（关键字查询、布尔查询、短语查询、邻近查询、全文查询、自然语言查询等）+查询操作（作简单预处理如STOP WORDS删除等发送到检索引擎、或处理用户反馈关联性反馈）+索引器（为提高查询效率对原始文档用某种数据结构做索引，形成文档索引返回文档索引，如倒排索引）+检索系统（为每个索引文档计算与查询的相关度分数）关键字查询布尔查询短语查询邻近查询全文查询自然语言查询预处理关联性反馈倒排索引计算文档与查询的相

5、关度分数布尔模型（布尔查询：AND、OR、NOT）向量空间模型（TF表、TFIDF表、查询、相关度排名）语言模型概率模型关联性反馈（4）查全率（recall）、查准率（precision）、查准率查全率曲线（PR曲线）、排名查准率（rank precision）、F-score（5）网页预处理：移除停用词、词干提取、数字、连字号、标点、字符大小写的处理；辨别不同的字段；辨别锚文本；移除HTML标签；辨别主要内容块；（6）副本探测（对整个文本HashMD5算法；基于n元短语的副本探测技术）：即复制页面，可减少索引大小，改善搜索效率； 镜像：复制站点的技术。（7）倒排索引：是一张列表，包含了每一个

6、不同的词和包含该词的文档列表。可加快检索和查询的速度。其本身构建速度也非常快。记录格式：idj,fij,o1,o2,.o|fij|倒排索引的建立及压缩：搜索引擎基于向量空间模型和词匹配模型。爬取网页！元搜索引擎和组合多种排序：略网络作弊的概念及分类：l 内容作弊（词组作弊）：标题、元标记、正文、锚文本、网址。如内容重复、或添加其他不相关的l 链接作弊（影响知名度分数）：链出链接作弊（指向中心页面目录克隆）或链入链接作弊（创建蜜罐、网络目录中添加链接、用户生成内容是添加链接、交换链接、自发添加等）l 隐藏技术：内容隐藏（隐藏垃圾项）、掩饰技术（垃圾网络服务器、重定向技术等）l 抵制作弊：分类处理

7、区别对待内容作弊、链接作弊、隐藏技术等；信任排名方法可用。2、主要知识点（1） IR系统的基本架构及原理l 用户查询的主要形式：关键字查询、布尔查询、短语查询、邻近查询、全文查询、自然语言查询的含义l 查询操作l 索引器l 检索系统（2） 信息检索模型主要有四种信息检索模型：布尔模型、向量空间模型、语言模型、概率模型。熟悉布尔模型、向量空间模型的基本原理，了解统计语言模型、概率模型。布尔模型：文档表示法、布尔查询、文档检索。向量空间模型：文档表示法（词频率表TF、词逆向文档频率TFIDF等）、查询、检出文件以及相关度排名（向量夹角余弦相似度、Okapi相关度计算、旋转标准化权值）（3） 信息检

8、索模型的评估标准查全率（recall）查准率（precision）查准率查全率曲线（PR曲线）排名查准率（rank precision）F-score（4）文本和网页的预处理内容l 停用词移除l 词干提取l 数字的预处理l 连字号的预处理l 标点符号的预处理l 字符大小写的预处理*网页预处理步骤：l 辨别不同的字段：标题、元数据、正文等l 辨别锚文本l 移除HTML标签l 辨别主要内容块（根据视觉线索分块、树匹配）l 副本探测（5）倒排索引及其压缩l 倒排索引的概念：l 使用倒排索引搜索的算法步骤搜索词汇表、结果合并、计算排名分数l 索引的建立方法：使用TRIE数据结构相比其他的结构更加有效。

9、l 索引的压缩方法：常用的有两种，即变位模式（一元编码、Elias gamma编码和delta编码）和变字节模式（整数对应到自定义的二进制编码）。l 索引压缩的解码：一元编码的解码、变字节编码的解码了解（6）隐式主义索引（略）（7）WEB搜索搜索引擎搜索引擎基于向量空间模型和词匹配模型。爬取网页！搜索引擎的工作步骤：分解（parsing）；索引（indexing）；搜索并排序（预处理、利用倒排索引查找含有全部查询词的页面、对页面排序并返回给用户）。其中排序算法是核心。搜索引擎的排序算法：网页质量和网页知名度是排序的重要因素。可利用超链接（链入链接pagerank算法、链出链接） 的数量作为排序

10、网页的指标之一；内容质量可利用（1）出现的形式，如标题、锚文本、网址、正文等；（2）计数：以不同形式出现的词的计数；（3）位置：对于以不同出现形式出现的词的位置记录。基于内容的网页评估分数（IR分数）与知名度分数的加权和以得到网页的排名分数。另见第七章中的计算方法。搜索引擎的两种查询方式：单词语查询和多词语查询。网络作弊技术：使用人为的手段，让一些网页高于其应有的排名。网页作弊的主要形式：内容作弊、链接作弊、隐藏技术（内容隐藏、掩饰技术、重定向）、抵制作弊（信任排名等技术）。（三） （ch7）链接分析1、 基本概念(1)社会关系网：是一门研究社会中社会实体（组织中的人、或者叫参与者）以及他们之

11、间的活动与关系的学问。这种关系或活动可以用网络或图来表示。(2)社会网络分析：分析研究社会关系网络的结构特性，以及每个参与者的职责、位置、威望等属性；找出各种类型的子图。l 社会网络分析方法：中心性和权威性。l 中心性（链出）的概念：链接（连接）、中心参与者。度中心性（有向图、无向图的度中心性）接近中心性（无向图、有向图的接近中心性）中介中心性（无向图、有向图的中介中心性）l 权威性（链入）的概念度权威邻近权威等级权威(pagerank、hits算法)(3)同引分析的概念：用来度量不由自主文档之间的相似性。引文耦合的概念： 将引用同一篇其他论文的两篇论文联系起来。两篇论文引用的相同文章数目越多

12、，它们之间就越相似。Pagerank算法的基本思想Hits算法的基本思想社区发现的相关概念。2、 主要知识点(1)社会网络分析：分析研究社会关系网络的结构特性，以及每个参与者的职责、位置、威望等属性；找出各种类型的子图。(2)络分析方法：中心性和权威性，这两种指标对于网络搜索以及链接分析都有非常密切的关系，是社会关系网中参与者的著名程度进行度量的标准。中心性（链出）的概念：链接（连接）、中心参与者。三种中心性度量：度中心性（有向图、无向图的度中心性）、接近中心性（无向图、有向图的接近中心性）、中介中心性（无向图、有向图的中介中心性）。权威性（链入）的概念：度权威、邻近权威、分级权威(pager

13、ank、hits算法)。度权威：邻近权威：等级权威：(3)同引分析的概念：用来度量不由自主文档之间的相似性。引文耦合的概念： 将引用同一篇其他论文的两篇论文联系起来。两篇论文引用的相同文章数目越多，它们之间就越相似。PAGERANK算法：1998年4月提出。了解基本思想及原理。PAGERANK算法的优缺点PAGERANKT可能改进timed pagerank算法的基本思想。HITS算法：1998年1月提出。了解其基本思想。(4)掌握同引分析与引文耦合与PAGERANK算法和HITS算法的关系。HITS算法的优点、缺点及可能的改进。了解社区发现的基本原理。（四） （ch8）WEB爬取1. 基本概

14、念（1）WEB爬虫（蜘蛛或机器人）：能自动下载网页的程序。（2）WEB爬虫的分类：通用爬虫、限定爬虫、主题爬虫。通用爬虫限定爬虫主题爬虫（3）简单爬虫算法：种子URL、队列、页面获取、网页库等模块。l 宽度优先爬虫l 带偏好的爬虫网页获取/网页解析/删除无用词、词干提取、链接提取和规范化/爬虫陷井网页库爬虫消耗的资源：网络、中CPU和磁盘。(4)爬虫的改进：实现并发性（并行爬虫架构）。通用爬虫：可扩展性、爬虫覆盖率、新鲜度和重要度。限定爬虫：能爬取用户感兴趣的某一类网页。熟悉概念。主题爬虫：带偏好爬取网页的爬虫。熟悉概念。了解通用爬虫、限定爬虫、主题爬虫的联系与区别。2、 主要知识点简单爬虫算

15、法及改进（并行爬虫）。限定爬虫算法的基本思想。主题爬虫的基本原理。三种爬虫算法的联系与区别WEB内容挖掘：包括结构化信息抽取、信息集成、观点挖掘。（五） (ch9)结构化数据抽取：包装器生成1、基本概念（1）WEB信息抽取：从网页中抽取目标信息，包括：从自然语言文本中抽取信息及从网页的结构化数据中抽取信息。l 包装器：抽取结构化数据的程序。l WEB结构化数据：从后台数据库获取的数据记录，它们按照一定的模板被展现在网页上。l 数据记录（2）信息抽取的主要方法：手工方法、包装器归纳（监督学习方法）、自动抽取（无监督学习方法）。l 数据抽取：给定由HTML标记编码的数据（网页），抽取系统恢复数据模

16、型并从编码后的数据记录中抽取数据。即从HTML编码的数据中恢复隐藏的模式。l 列表页l 详情页l 数据模型：嵌套关系；基本类型、元组类型、集合类型、平坦元组类型、平坦集合类型；平坦关系；集合类型实例；元组类型实例等。l 数据实例的HTML编码（3）包装器归纳的概念及基本原理EC树开始规则/结束规则地标通配符析取规则学习抽取规则：正规则、负规则地标提纯拓朴提纯 包装器学习的重要问题之一：手工标注训练样例。费时费力。可能的包装器归纳学习的改进：主动学习或协同测试的方法。l 主动学习：是一种帮助自动识别提供信息的未标注样例的方法。包装器学习中主动学习步骤：从U中随机选取一个较小的未标注样例子集L；手

17、工标注L中的样例，并令UUL；基于标注样例集L学习一个包装器；将W应用于U以找到一个提供信息样例的集合L；如果L，则终止，否则转。 算法的关键是步。l 协同测试的方法可用来识别提供信息的样例。了解其基本思想。l 包装器维护：包装器验证问题、包装器修复问题。学习目标数据项的特征模式，以监视抽取工作以及检验所抽取的数据项是否正确。再标注，再学习。l 基于实例的包装器学习：不用学习抽取规则，而是通过将目标数据项的前缀和后缀标志字符串与对应的标注好的样例进行比较，来从一个新的实例或网页中识别目标数据项。如果一个未标注的样例中，某个数据项不能被识别。则它将被交付标注，这是没有附加机制的主动学习。（4）自

18、动包装生成中的问题：手工标注不适合对大量站点的抽取；包装器维护的开销很大。l 包装器自动生成中的模板：指代网页设计者所采用的隐藏模板。l 包装器自动生成中的模式：指代系统所发现的规则结构。l 包装器的应用两个抽取问题：基于一张列表页的抽取；基于多张网页的抽取。从一组编码好的同种类型的实例中寻找编码模板检测HTML编码字符串中重复出现的模式。l 信息抽取技术：字符串匹配和树匹配。l DOM：文档对象模型标签树。l 字符串的编辑距离：即莱文斯坦距离，定义为将串S1变成串S2所需要的点突变的最少次数。l 点突变是指下列操作之一改变一个字符；插入一个字符；删除一个字符。l 掌握字符串的对齐算法。l 树

19、匹配中的树编辑距离：是将树A变换为树B所需要的最小操作集对应的代价。l 树编辑距离的操作包括：节点删除；节点插入和节点替换。每个操作都被指定了一个代价。l 解树编辑距离问题应时寻找两棵树间的最小代价映射。l 树代价映射的定义l 简单树匹配STM：不允许节点替换和层次交叉，STM的目标是找到两棵树间的最大匹配。l 最大匹配：设A、B是两棵树，而iA和jB是A和B中的两节点，两棵树间的一个匹配定义为一个映射M，使得对每一个节点对（i,j）M,( i,j都不是根节点)，都有（parent(i）,parent(j) M。一个最大匹配就是一个拥有最多节点对的匹配。了解STM算法多重对齐：产生一个对所有字

20、符串或树的全局对齐任务称为多重对齐。 两种多重对齐算法：中星方法和部分树对齐。中星方法部分树对齐方法：构建DOM树标签树。标签树的构建方法：标签方法或用标签和视觉提示的方法。利用标签构建DOM树：HTML编码清理；树的构建。用标签和视觉提示构建DOM树：通过调用浏览器的渲染引擎找到每一个HTML元素长廊形的四个边界；依据开始标签序列进行包含检验以构建标签树。包含检验：是指检验一个长方形是否被另一个长方形包含。基于列表页的抽取：平坦数据记录的抽取假设网页的DOM树已经构建，给定一个含有多个列表，且每个列表含有多个数据记录的列表页，将执行下列任务：（1）识别每个列表（也称为数据区域），即挖掘所有数

21、据区域（挖掘广义节点序列；比较广义节点；）；MDR算法（2）将每个列表或数据区域内的数据记录分段，以及；识别数据记录、（3）对齐数据记录中的数据项以为每一个数据区域产生一个数据表和一个正则表达式。数据项对齐与抽取；冲突消解；利用视觉信息等；基于列表页的抽取嵌套数据记录（NET算法：后序遍历）：了解2 主要知识点信息抽取的主要方法：手工方法、包装器归纳（监督学习方法）、自动抽取（无监督学习方法）。（1）数据抽取：给定由HTML标记编码的数据（网页），抽取系统恢复数据模型并从编码后的数据记录中抽取数据。即从HTML编码的数据中恢复隐藏的模式。列表页/详情页数据模型：嵌套关系；基本类型、元组类型、集

22、合类型、平坦元组类型、平坦集合类型；平坦关系；集合类型实例；元组类型实例等。数据实例的HTML编码（2）包装器归纳的概念及基本原理l EC树l 开始规则/结束规则l 地标l 通配符l 析取规则l 学习抽取规则：正规则、负规则l 地标提纯l 拓朴提纯 包装器学习的重要问题之一：手工标注训练样例。费时费力。可能的包装器归纳学习的改进：主动学习或协同测试的方法。了解主动学习：是一种帮助自动识别提供信息的未标注样例的方法。包装器学习中主动学习的算法步骤：（1）从U中随机选取一个较小的未标注样例子集L；（2）手工标注L中的样例，并令UUL；（3）基于标注样例集L学习一个包装器；（4）将W应用于U以找到一

23、个提供信息样例的集合L；（5）如果L，则终止，否则转（2）。 算法的关键是（4）步。协同测试的方法可用来识别提供信息的样例。了解其基本思想。包装器维护：包装器验证问题、包装器修复问题。学习目标数据项的特征模式，以监视抽取工作以及检验所抽取的数据项是否正确。再标注，再学习。基于实例的包装器学习：不用学习抽取规则，而是通过将目标数据项的前缀和后缀标志字符串与对应的标注好的样例进行比较，来从一个新的实例或网页中识别目标数据项。如果一个未标注的样例中，某个数据项不能被识别。则它将被交付标注，这是没有附加机制的主动学习。（3）自动包装生成中的问题：手工标注不适合对大量站点的抽取；包装器维护的开销很大。包

24、装器自动生成中的模板：指代网页设计者所采用的隐藏模板。包装器自动生成中的模式：指代系统所发现的规则结构。包装器的应用两个抽取问题：基于一张列表页的抽取；基于多张网页的抽取。从一组编码好的同种类型的实例中寻找编码模板检测HTML编码字符串中重复出现的模式。（4）信息抽取技术：字符串匹配和树匹配及相关算法。DOM：文档对象模型标签树。字符串的编辑距离：即莱文斯坦距离，定义为将串S1变成串S2所需要的点突变的最少次数。点突变是指下列操作之一改变一个字符；插入一个字符；删除一个字符。掌握字符串的对齐算法。树匹配中的树编辑距离：是将树A变换为树B所需要的最小操作集对应的代价。树编辑距离的操作包括：节点删

25、除；节点插入和节点替换。每个操作都被指定了一个代价。解树编辑距离问题应时寻找两棵树间的最小代价映射。树代价映射的定义简单树匹配STM：不允许节点替换和层次交叉，STM的目标是找到两棵树间的最大匹配。最大匹配：设A、B是两棵树，而iA和jB是A和B中的两节点，两棵树间的一个匹配定义为一个映射M，使得对每一个节点对（i,j）M,( i,j都不是根节点)，都有（parent(i）,parent(j) M。一个最大匹配就是一个拥有最多节点对的匹配。了解STM算法多重对齐：产生一个对所有字符串或树的全局对齐任务称为多重对齐。 两种多重对齐算法：中星方法和部分树对齐。中星方法掌握运用部分树对齐方法：掌握应

26、用构建DOM树标签树。标签树的构建方法：标签方法或用标签和视觉提示的方法。利用标签构建DOM树：HTML编码清理；树的构建。用标签和视觉提示构建DOM树：通过调用浏览器的渲染引擎找到每一个HTML元素长廊形的四个边界；依据开始标签序列进行包含检验以构建标签树。包含检验：是指检验一个长方形是否被另一个长方形包含。基于列表页的抽取：平坦数据记录的抽取平坦数据记录抽取流程或算法步骤：假设网页的DOM树已经构建，给定一个含有多个列表，且每个列表含有多个数据记录的列表页，将执行下列任务（应尽量细化内核）：（1）识别每个列表（也称为数据区域），即挖掘所有数据区域（挖掘广义节点序列；比较广义节点；）；MDR

27、算法， （2）将每个列表或数据区域内的数据记录分段，以及；识别数据记录、（3）对齐数据记录中的数据项以为每一个数据区域产生一个数据表和一个正则表达式。数据项对齐与抽取；冲突消解；利用视觉信息等；基于列表页的抽取嵌套数据记录（NET算法：后序遍历）：了解（六） (ch10)信息集成1、基本概念（1）信息集成：最初的研究是针对关系数据库和数据仓库。（2）WEB全局搜索界面：是用来产生查询字从而到WEB数据库（深层WEB）中获取相关信息的。全局搜索界面允许用户输入相关的信息，系统根据用户提供的信息自动填写所有的源搜索界面从而从各个站点获取所。各站点返回的数据需要经过集成，展示给用户。（3）样式表匹配

28、：是指对于两个或更多个数据库的样式表建立映射，把具有相同意义的属性（或元素）映射到一起。目的是把多个样式表整合为一张全局的统一的样式表。（4）样式表的匹配方法：半自动化的匹配（有难度，基于启发式的领域知识）或自动匹配（难度很大，产生候选匹配由用户确认）。l 基于输入信息，样式表匹配的不同类型：样式表层次的匹配、领域和实例层次的匹配；样式表、领域、实例整合的匹配。l 样式表匹配的预处理：分词、扩展、移除无用词和词干提取、词的标准化等。l 匹配类型：1：1；1：m；m：1；m：nl 样式表层次的匹配中，主要有两种信息：样式表中属性的名称、描述等的自然语言词汇（基于语言学的算法名称匹配、上位关系、基

29、于描述的匹配等）；样式表中的限制（数据类型和数值范围、唯一性、关系类型的的限制等）。l 基于领域和实例层次的匹配：在WEB数据库中，数据实例易于获得；有些应用中，属性的领域信息也是可获得的。l 属性的领域分为：简单领域和复杂领域。l 简单领域是指该领域中的实例值都是简单的，也就是非合成的。l 数据类型：如果样式表对于属性的类型没有说明，则需要通过属性的实例值来判断元素的数据类型。l 识别数据类型的方法：半自动方法（即正则表达式匹配的方法）和自动化方法（使用机器学习的方法）。l 匹配算法：DI 1DI6 简单领域匹配算法l DI 1使用数据类型作为限制信息，建立对应表来描述一系列预定义好的数据类

30、型之间的兼容度。l DI 2对于数字类型的数据，数值范围、平均值和言状都可以被用来计算他们之间的数据类型的相似度。l DI 3对于不确定的数据类型，可以抽取和比较两个元素的实例值，以决定其属性是否匹配。l DI 4对于字母和数字混杂的数据类型，字符串的长度和字母/非字母的比例都是非常有用的信息。l DI 5对于文本数据，可以用夹角余弦计算属性之间的相似度。l DI 6把样式表元素的名称添加到实例值中进行比较。l 复合的领域和属性：一个K元的复合领域是一个有序的K元组，其中第i个部分是第i个子领域的值，记作di。每个di都是一个简单领域。如果一个属性所有的领域是复合的，则称该属性是复合的属性。l

31、 一个复合领域通常可以通过它的实例值来反映。往往含有各种形式的分隔符，或其他的特殊单词。进行复合领域的匹配时，为了保证分隔的正确性，需要大量的实例值。l 算法DI 7一个简单领域与一个复合领域的相似度是通过比较简单领域和复合领域的各个子领域来实现的。两个复合领域的相似度也是通过比较他们各自所包含的简单子领域的相似性来决定的。l 不同相似度的联合：可通过多种策略实现取最大值的策略；加权和；加权平均；机器学习的方法。l 1：m匹配对于part-of 类型的匹配；对于is-a类型的匹配l 样式表匹配的结果的处理：最热门N个候选；取最大相似度；阈值筛选等。（5）WEB全局搜索界面：把多个搜索界面集成为

32、一个以提供给用户一个全局的搜索因人而异，无需用户逐个手动搜索各个数据源，只需在全局搜索界面上输入所需的信息即可。l WEB全局搜索界面与普通的信息集成的区别：在WEB搜索界面中缩写记号使用非常有限；词汇有限；WEB中有大量的相似数据库（网页）；附加的结构。l WEB全局搜索界面集成的方法：基于聚类的算法；基于互关系的方法；基于实例的方法。l WEB全局搜索界面构建步骤：l 一个良好的全局搜索界面应该满足的条件：结构上的正确性；词汇的正确性和实例的正确性。2、主要知识点（1）信息集成：从单一网站上抽取信息往往是不够的，需要从大量的站点中提取数据，然后对提取出的数据进行集成以便提供增值服务。对不同

33、的数据而言集成意味着匹配出表示同类信息的列，或者匹配出语义相同但是表达方式不同的值，并可能存放在后台数据库中。（2）信息集成的基本方法：样式表匹配抽取样式表样式表预处理样式表层次的匹配（基于语言学的算法、或基于样式表中限制的算法）、基于领域和实例层次的匹配（简单领域匹配方法半自动的方法或自动的方法；复合领域匹配的方法）、样式表/领域/实例整合的匹配； 大量样式表的匹配（借助聚类算法、互关系或模式发现算法）样式表匹配的结果处理（最热门的N个候选；最大相似度；阈值筛选等）用户交互（匹配系统搭建；匹配的后期工作）。（3）WEB搜索界面的集成：全局搜索界面的构建全局搜索界面样式表：全局搜索界面构建：基

34、于聚类的算法、基于互关系的方法、基于实例的方法。基于聚类的算法：了解实现思想基于互关系的方法：了解实现思想基于实例的方法：了解实现思想（七） (ch11)观点挖掘1、基本概念l 背景：从网页中抽取的结构化数据通常在网页设计时是来自于一个后台的数据库，并遵循一定的模板格式显示在网页中。此外，网页中还存在大量的非结构化的文本信息，包括了所有类型的各种有价值的信息，分析这些信息是非常重要的。l 观点挖掘的背景：企业需要了解用户对其产品或服务的评价；新用户需要知道现有用户对某产品或服务的评价；了解评价可为广告放置提供参考等。l 现实性与可能性：网络用户有多种发表观点的方法：商业网站、产品或服务评价、博

35、客、论坛等。本章内容：评估文本、观点搜索、观点欺诈。（1）评估文本的三个挖掘任务：意见分类、基于特征的观点挖掘和摘要、比较性句子和比较关系挖掘。（2）观点挖掘：可以使用户搜索关于任何对象的观点。（3）观点欺诈：欺诈性观点是指有些人为推销自身产品或服务。或者损害竞争对手声誉而发表的那些不切实际的或者怀有恶意的观点。l 意见分类：正面评论、负面评论和中立评论。意见分类主要用于快速判定大众对一个对象的普遍观点。该任务和传统的基于主题的文本分类相似。但有不同。意见分类中主题相关的词汇并不重要，表征正面或负面观点的词汇更加重要。意见分类的研究层次：主要是文档层次；其次还有句子层次的。意见分类的具体方法：

36、基于意见短语的分类；采用文本分类方法进行意见分类；基于评分函数进行分类。l 基于意见短语的分类：基于各个评估文本中正面和负面的意见词和短语。算法步骤：基于调整性标注的自然语言处理技术S1. 抽取包含有形容词和副词的短语，采用宾州树库词性标注集（表11.1）+基于特征的观点摘要（表11.2）；S2. 采用点对互信息估计所抽取的短语的语义倾向（一个短语的语义倾向SO基于它和正面参考词“excellent”与负面词“poor”的关联程度进行计算）；S3. 给定一个评审。算法计算评审中所有短语的平均SO。如果平均SO是正的，则为正面证人否则为负面评价。l 采用文本分类方法进行意见分类：将该问题作为基于

37、主题的文本分类问题，可采用naïve Bayesian, VM, N等方法。l 基于评分函数进行分类：采用通用评分函数，算法步骤为：S1. 在训练集中采用评分公式为每个词赋值，介于11之间；S2.算法将新文档的所有词的评分求和，并给出分类的判断。基于特征的观点挖掘和摘要：一个关于特定对象的正面评估文本并不能说明作者对于该对象的任一方面都有正面的评价。在一个特定产品的评审中，评审人通常会同时给出一个产品的正面或负面评价，挖掘往往作用于句子层面。l 定位和抽取评审者所评论产品的特征产品特征l 判定对于特定特征的评价是正面的、负面的还是中立的。对象：一个对象O是指一个实体,它可以是一个产品

38、、人物、事件、组织或者主题。它关联到一个序对O：（T，A），其中T是一个层次化或者结构化的部件（或者组件）、子部件等。A是一个关于属性的集合，每个部件都拥有它自己的子部件或属性集合。O：数码相机部件：lens,battery,view-finder.Battery: life, size, weight. 显式特征和隐式特征：如果一个特征f出现在一个评估文本r中，则称它是r的一个显式特征。如果f没有在r中出现，则称其为r的一个隐式特征。如 the battery life of this camera is too short. This camera is too large.某一特征的观点

39、段：一个关于对象r的特征f的观点段是r中一组表达了关于f的正面或者负面观点的连续句子。如：the battery quality is good, but the battery life is short.大多数的研究集中在句子上。每个段落由一个单独的句子组成。显式观点和隐式观点：一个关于特征f的显式观点是一个直接表达了正面或负面观点的主观句子。一个关于特征f的隐式观点是一个蕴含了正面或负面观点的客观句子。如：this picture quality of this camera is amazing. The earphone broke in two days.观点持有对象：关于某一特定

40、观点的持有对象是指拥有这一观点的人或组织。一个对象和该对象之上的观点集合的简要模型：一个对象可以被表示为一个关于特征的有限集合Ff1,f2,fn，每一个F中的特征fi都可以表示为一个同义词或者同义短语Wi的集合。即对于n个特征，有一个对应的同义词集合WW1，W2，Wn。由于每个F中的特征fi都有一个名字（标记为fi），可得到fiWi。每个作者或观点持有对象j对一个特征的子集SjÍF进行评论。对于每个观点持有对象进行评论了的特征fkSj，可以从Wk中选择一个词或者短语来描述该特征，并对其表达正面或负面的观点。给定一个评测文本集合D作为输入，则可有如下三个问题：P1：F和W都是未知的，在

41、观点挖掘中需要挖掘的任务T1、T2和T3.T1：从每个评估dD中定位与抽取被评估对象的特征。T2：确定对于该特征的观点是正面的、负面的或中立的。T3：由于不同的人可能采用不同的词或短语来描述同样的特征。需将各个特征的同义词进行归并。P2：F已知而W未知。与P1类似有三个任务，但处理更简单。其中T1与T2同前；但T3可将已发现的特征与给定特征集合F进行匹配而求解。P3：W已知（可以推出F也是已知的）。仅需要进行任务T2，即在抽取所有包含相应特征的句子后，确定一个已知特征上的观点是正面的，负面的还是中立的。基于特征的摘要：形成针对某一对象的各种观点的基于特征的摘要。对象特征提取：主要用在在线产品的

42、评审上。有三种类型的评审格式，不同的评审格式需要不同的技术进行特征提取。格式1：区分正面、负面以及细节的评审。评审者被要求独立地描述正面和负面观点；此外，还要给出细节评审。格式2：区分正面和负面的评审。评审者被要求独立地描述正面和负面观点；但不需要给出独立的细节评审。格式3：自由格式。评审者可以自由地给出评价。不必区分正面或负面观点。格式1中特征抽取算法：S1：用于LSR挖掘的训练数据准备；S2：标记顺序规则挖掘；找到包含特征的规则，词性标注和词形成语言模式； S3：特征抽取，考虑三种情形：l 如果一个句子片段匹配多个规则的处理l 对于没有规则适用的句子片段，如果存在，被词性标注工具标出来的名

43、词和名词短语被抽取为特征；l 对于只有一个词的句子片段，单一词汇被对待为特征。隐式特征匹配同义词分组特征粒度格式2和格式3的特征抽取算法：了解S1：找到所有的调频名词和名词短语；名词和名词短语可能通过词性标注工具勷S2：通过利用意见词找到不频繁出现的特征。意见词（又称观点词）通常表达正面或负面评价的形容词和副词。观点倾向分类：意见词和短语是那些表达了正面或负面意见（观点）的词，通常是形容词和副词，也可是动词或名词。已构建了意见词的集合l 人工找到一个正面或负面词汇、成语的种子集合，为形容词、动词、名词和副词、成语等都准备一个单独的种子集合。l 在WORDNET中迭代地查找它们的同义词和反义词，

44、以此扩展种子集合直到收敛。l 人工检查结果，并去除不正确的词汇。l 识别句子的意见词和短语，是正面的则赋值 +1，负面的赋值 为1，所有的赋值相加，为正则结论是正面的，否则结论为负面的。比较性句子和比较关系挖掘直接表达某一对象的正面或负面观点只是评估的一种形式，将一个对象和其他同等对象进行比较是另一种形式。比较也是更能让人信服的一种方式。分为主观比较和客观比较。如the picture quality of camera x is great. 典型句子主观比较：the picture quality of camera x is better than that of camera y.客观

45、比较：camera Xis 20 grams heavier than camera y.比较性句子和判定比较关系是很难的。很多包含比较级（最高级）的句子并不是比较格式；而不包含这类词的句子却是比较性句子。比较性句子：是一个表达了多个对象之间的相似或者不同关系的句子，比较性句子中的比较关系通常由一个形容词或副词的比较级或最高级来表达。几种重要的比较类型：等级比较和非等级比较，其中等级比较可进一步分为形容词和副词比较。等级比较包括：不相等的等级比较、相等等级的比较、最高级的比较。非等级比较比较了两个或者多个对象的特征，但并不对他们进行分级。可分为三种类型：对象A和对象B在某些特征上相似或者不同；

46、对象A有特征f1，而对象B有特征f2；对象A拥有特征f，但是对象B没有。比较性句子的三种类型：非平等等级比较；平等比较；最高级比较。比较关系的抽取：l 序列数据产生：用于挖掘的顺序数据库创建；在数据中手工标记每个句子的标号词.l LSR的生成挖掘规则系统被用来生成标号顺序规则。l 关系项抽取，如使用规则来匹配句子，并用具有最高置信度的规则来抽取关系项。观点搜索包括：1. 搜索某一特定对象或对象特征上的观点。2. 搜索某一个人或组织对某一特定对象或对象特征的看法。观点欺诈指人们故意误导读者和自动观点挖掘系统的行为（比如撰写欺诈性的评审）。观点欺诈的目的：推销某些目标对象；损害某些其他目标对象的声

47、誉等。观点欺诈的行为：为了推销目标对象撰写一些不切实际的正面评审炒作欺诈；为了诋毁某些目标对象的声誉，撰写一些不公平或者恶毒的反而评审诽谤欺诈。欺诈和欺诈者的种类：人工欺诈和自动欺诈；个人欺诈和群组欺诈。隐藏技巧：欺诈者为了避免被检测出来所采取的预防措施。欺诈检测：面向评论的欺诈检测；面向评论者的欺诈检测；面向服务器的欺诈检测。面向评论的欺诈检测：比较内容相似性；检测评分和内容例外；比较多个网站的平均打分；检测评分例外。面向评论者的欺诈检测：观察早期用户；检测早期修正动作；比较同一评论者对于不同品牌产品的评论打分；比较评论时间。面向服务器的欺诈检测。2、主要知识点（1）意见分类l 基于意见短语

48、的分类算法：基于各个评估文本中正面和负面的意见词和短语。算法步骤：基于调整性标注的自然语言处理技术S1. 抽取包含有形容词和副词的短语，采用宾州树库词性标注集（表11.1）+基于特征的观点摘要（表11.2）；S2. 采用点对互信息估计所抽取的短语的语义倾向（一个短语的语义倾向SO基于它和正面参考词“excellent”与负面词“poor”的关联程度进行计算）；S3. 给定一个评审。算法计算评审中所有短语的平均SO。如果平均SO是正的，则为正面证人否则为负面评价。l 采用文本分类方法进行意见分类：将该问题作为基于主题的文本分类问题，可采用naïve Bayesian, VM, N等方法

49、。l 基于评分函数进行分类：采用通用评分函数，算法步骤为：S1. 在训练集中采用评分公式为每个词赋值，介于11之间；S2.算法将新文档的所有词的评分求和，并给出分类的判断。（2） 基于特征的观点挖掘和摘要：一个关于特定对象的正面评估文本并不能说明作者对于该对象的任一方面都有正面的评价。在一个特定产品的评审中，评审人通常会同时给出一个产品的正面或负面评价，挖掘往往作用于句子层面。l 定位和抽取评审者所评论产品的特征产品特征l 判定对于特定特征的评价是正面的、负面的还是中立的。对象：一个对象O是指一个实体,它可以是一个产品、人物、事件、组织或者主题。它关联到一个序对O：（T，A），其中T是一个层次

50、化或者结构化的部件（或者组件）、子部件等。A是一个关于属性的集合，每个部件都拥有它自己的子部件或属性集合。O：数码相机部件：lens,battery,view-finder.Battery: life, size, weight. 显式特征和隐式特征：如果一个特征f出现在一个评估文本r中，则称它是r的一个显式特征。如果f没有在r中出现，则称其为r的一个隐式特征。如 the battery life of this camera is too short. This camera is too large.某一特征的观点段：一个关于对象r的特征f的观点段是r中一组表达了关于f的正面或者负面观点的

51、连续句子。如：the battery quality is good, but the battery life is short.大多数的研究集中在句子上。每个段落由一个单独的句子组成。显式观点和隐式观点：一个关于特征f的显式观点是一个直接表达了正面或负面观点的主观句子。一个关于特征f的隐式观点是一个蕴含了正面或负面观点的客观句子。如：this picture quality of this camera is amazing. The earphone broke in two days.观点持有对象：关于某一特定观点的持有对象是指拥有这一观点的人或组织。一个对象和该对象之上的观点集合的简要模型：一个对象可以被表示为一个关于特征的有限集合Ff1,f2,fn，每一个F中的特征fi都可以表示为一个同义词或者同义短语Wi的集合。即对于n个特征，有一个对应的同义词集合WW1，W2，Wn。由于每个F中的特征fi都有一个名字（标记为fi），可得到fiWi。每个作者或观点持有对象j对一个特征的子集SjÍF进行评论。对于每个观点持有对象进行评论了