Web 数据挖掘

Web 数据挖掘总结

Chapter 1 概述

万维网：一个在世界范围内的超媒体信息获取平台，他提供一种获取海量文档的统一途径。

超文本：一种允许网页作者创建指向世界上热河计算机上相关文档的链接的一种文档结构

超链接：作者创建指向世界上热河计算机上相关文档的链接

超媒体：超文本中包含的媒体，包括音频、视频、图片等

HTTP：超文本传输协议（HyperText Transfer Protocol）

HTML:超文本标记语言（HyperText Markup Language）

URL：统一资源定位符（Universal Resource Locator）

WEB：web（World Wide Web）即全球广域网，也称为万维网，它是一种基于超文本和HTTP的、全球性的、动态交互的、跨平台的分布式图形信息系统。

TCP/IP：传输控制协议/互联网协议（Transmission Control Protocol/Internet Protocol）

Web数据的特点：

（1）数量巨大并且不断增长

（2）存在各种类型的数据

（3）信息异构，内容相同，形式不同。

（4）绝大部分信息是相互连接的

（5）存在着噪音

（6）提供商业服务

（7）具有动态性

（8）不仅仅是数据信息服务，也包括人、组织和自动化系统之间的交互，是一个虚拟社会

数据挖掘

（1）定义：又被称为数据库中的知识发现。是指从数据源中探寻有用的模式或知识的过程。这些模式必须是有用的、有潜在价值的，并且是可以被理解的。数据挖掘是一门多学科交叉的学科，包括机器学习、统计、数据库、人工智能、信息检索和可视化。

（2）任务：监督学习、无监督学习、关联规则挖掘、序列模式挖掘

​ 第一类是描述性挖掘任务：刻划数据库中数据的一般特性；

	第二类是预测性挖掘任务：在当前数据上进行推断，以进行预测。

（3）KDD 过程：预处理》数据挖掘》后续处理

（4）KDD 的数据类型：数据库、文本、图片、万维网等

Web 数据挖掘

（1）定义：从 Web 超链接、网页内容和使用日中中探寻有用的信息。

（2）分类：依据挖掘过程中使用的数据类别，web 挖掘的任务主要有三类：Web 结构挖掘、Web 内容挖掘和 Web 使用挖掘。

• Web结构挖掘：从表征 Web 结构的超链接中寻找知识。（CH6-CH8信息检索、Web 搜索，链接分析，Web 爬取）
• Web 内容挖掘：从网页内容中抽取有用的信息和知识。（CH9-11结构化数据抽取：包装器生成、信息集成、观点挖掘）
• Web 使用挖掘：从记录每位用户点击情况的使用日志中挖掘用户的访问模式。（CH12web 使用挖掘）

（3）过程：爬取大量网页形成数据源，然后按照数据挖掘的流程

关联规则：数据中所蕴含的一类重要规律，在数据项目中找出所有的并发关系。

序列模式挖掘：在数据中找出所有的顺序关系。

分类与预测：利用机器学习，实现类似于人类从过去经验中获取知识以用于提高解决现实问题的能力。

聚类挖掘：一种发现数据内在结构的技术，把全体数据示例组织成一些相似组

Chapter 6 信息检索与 Web 搜索

基本概念

信息检索 IR：帮助使用者从大量数据集信息中发现需要的资料。作为一门学科包含了信息的采集组织、存储、检索及分发。根据用户查询信息得到相应的一组文档，得到的结果根据其与用户查询的相关程序排序，最常用的用户查询信息是一组关键字。其基本信息是单个的文档，大量的文档形成文本数据库。

**Web 搜索：**是信息检索的一个重要分支。区别于信息检索的是：效率是 Web 搜索的一个最为重要的问题；网页和传统信息检索系统中使用的普通文档不同（具有超链接的及锚文本；网页是半结构化的；网页的内容基本上是有组织的，并且在一些结构块中出现；作弊技术是网络上的一个重要问题）

IR 的基本结构：

• 用户查询（关键词查询、布尔查询、短语查询、邻近查询、全文查询、自然语言查询）
• 查询操作（作简单预处理如 stopwords 删除等发送到搜索引擎、或处理用户反馈—关联性反馈）
• 索引器（为提供查询效率对原始文档用某种数据结构做的索引，形成的文档索引-返回文档索引，如倒排索引）
• 检索系统（为每个索引文档计算与查询的相关度分数）

查全率：R

查准率：P

PR曲线/F-score

网页预处理：移除无用词、提取词干

倒排索引

四种 IR 模型：

布尔模型：文档表示法、布尔查询、文档检索

• 文档表示
• • 一个文档被表示为关键词的集合
• 查询式表示
• • 查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序
• 匹配
• • 一个文档当且仅当它能够满足布尔查询式时，才将其检索出来
  • 检索策略基于二值判定标准
• 优点
  • 由于查询简单，因此容易理解
  • 相当有效的实现方法，相当于识别包含了一个某个特定term的文档
  • 经过某种训练的用户可以容易地写出布尔查询式
  • 布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”
• 缺点
  • 主要问题在于不支持部分匹配，而完全匹配会导致太多或者太少的结果文档被返回
  • • 非常刚性: “与”意味着全部; “或”意味着任何一个
  • 很难控制被检索的文档数量
  • • 原则上讲，所有被匹配的文档都将被返回
  • 很难对输出进行排序
  • • 不考虑索引词的权重，所有文档都以相同的方式和查询相匹配
  • 很难进行自动的相关反馈
  • • 如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢

空间向量模型：文档表示法（词频率表TF、词逆向文档频率TF－IDF等）、查询、检出文件以及相关度排名（向量夹角余弦相似度、Okapi相关度计算）

Pros：

• 术语权重的算法提高了检索的性能
• 部分匹配的策略使得检索的结果文档集更接近用户的检索需求
• 可以根据结果文档对于查询串的相关度通过Cosine Ranking等公式对结果文档进行排序

Cons：

• 标引词之间被认为是相互独立
• 随着Web页面信息量的增大、Web格式的多样化，这种方法查询的结果往往会与用户真实的需求相差甚远，而且产生的无用信息量会非常大
• 隐含语义索引模型是向量空间模型的延伸

语言模型：

概率模型：

Chapter7 链接分析

基本概念

(1)社会关系网：是一门研究社会中社会实体（组织中的人、或者叫参与者）以及他们之间的活动与关系的学问。这种关系或活动可以用网络或图来表示。

(2)社会网络分析：分析研究社会关系网络的结构特性，以及每个参与者的职责、位置、威望等属性；找出各种类型的子图。

• 社会网络分析方法：中心性和权威性。
• 中心性（链出）的概念：链接（连接）、中心参与者。
• 度中心性（有向图、无向图的度中心性）
• 接近中心性（无向图、有向图的接近中心性）
• 中介中心性（无向图、有向图的中介中心性）
• 权威性（链入）的概念
• 度权威

(3)同引分析的概念：用来度量不由自主文档之间的相似性。

• 引文耦合的概念： 将引用同一篇其他论文的两篇论文联系起来。两篇论文引用的相同文章数目越多，它们之间就越相似。
• Pagerank算法的基本思想
• Hits算法的基本思想

PageRank 方法实现

HITS 方法实现

Chapter8 Web爬取

基本概念

（1）WEB爬虫（蜘蛛或机器人）：能自动下载网页的程序。

（2）WEB爬虫的分类

• • 通用爬虫：可扩展性、爬虫覆盖率、新鲜度和重要度。
  • 限定爬虫：能爬取用户感兴趣的某一类网页
  • 主题爬虫：带偏好爬取网页的爬虫。
  • 了解通用爬虫、限定爬虫、主题爬虫的联系与区别。

（3）简单爬虫算法：种子URL、队列、页面获取、网页库等模块。

（4）宽度VS 广度优先爬虫

（5）实现问题：网页获取/网页解析/删除无用词、链接提取和规范、爬虫陷井、网页库

（6）爬虫的改进：实现并发性（并行爬虫架构）。

Chapter9 包装器

基本概念

（1）WEB信息抽取：从网页中抽取目标信息，包括：从自然语言文本中抽取信息及从网页的结构化数据中抽取信息。

• • 包装器：抽取结构化数据的程序。
  • WEB结构化数据：从后台数据库获取的数据记录，它们按照一定的模板被展现在网页上。
  • 数据记录

（2）信息抽取的主要方法：手工方法、包装器归纳（监督学习方法）、自动抽取（无监督学习方法）。

• • 数据抽取：给定由HTML标记编码的数据（网页），抽取系统恢复数据模型并从编码后的数据记录中抽取数据。即从HTML编码的数据中恢复隐藏的模式。
  • 列表页、详情页
  • 数据模型：嵌套关系；基本类型、元组类型、集合类型、平坦元组类型、平坦集合类型；平坦关系；集合类型实例；元组类型实例等。
  • 数据实例的HTML编码

（3）包装器归纳的概念及基本原理

• • EC树、开始规则/结束规则、地标、通配符、析取规则
  • 学习抽取规则：正规则、负规则、地标提纯、拓朴提纯
  • 包装器学习的重要问题之一：手工标注训练样例。费时费力。可能的包装器归纳学习的改进：主动学习或协同测试的方法。
  • 主动学习：是一种帮助自动识别提供信息的未标注样例的方法。
  • 包装器学习中主动学习步骤：①从U中随机选取一个较小的未标注样例子集L；②手工标注L中的样例，并令U＝U－L；③基于标注样例集L学习一个包装器；④将W应用于U以找到一个提供信息样例的集合L；⑤如果L＝Ф，则终止，否则转②。 ——算法的关键是④步。
  • 协同测试的方法可用来识别提供信息的样例。
  • 包装器维护：包装器验证问题、包装器修复问题。——学习目标数据项的特征模式，以监视抽取工作以及检验所抽取的数据项是否正确。再标注，再学习。
  • 基于实例的包装器学习：不用学习抽取规则，而是通过将目标数据项的前缀和后缀标志字符串与对应的标注好的样例进行比较，来从一个新的实例或网页中识别目标数据项。如果一个未标注的样例中，某个数据项不能被识别。则它将被交付标注，这是没有附加机制的主动学习。

（4）自动包装生成中的问题：手工标注不适合对大量站点的抽取；包装器维护的开销很大。

• • 包装器自动生成中的模板：指代网页设计者所采用的隐藏模板。
  • 包装器自动生成中的模式：指代系统所发现的规则结构。
  • 包装器的应用——两个抽取问题：基于一张列表页的抽取；基于多张网页的抽取。从一组编码好的同种类型的实例中寻找编码模板——检测HTML编码字符串中重复出现的模式。
  • 信息抽取技术：字符串匹配和树匹配。

Chapter11 观点挖掘

• 观点的基本要素

• • 观点持有者: 对于特定对象持有特定观点的个人或组织.
  • 对象: 观点表达的作用者
  • 观点: 观点持有者对一个对象的一种看法、态度或评价.

• 观点挖掘的目标: 很多 …

• • 文档层次的目标: 评论的情感分类
  • 句子层次的目标: 主观或客观句子的识别, 主观句子的情感分类
  • 特征层次的目标: 识别对象特征, 找对象特征的同义词, ……

• 观点挖掘的任务

  • 在文档(或评论)层次:

    ​ 任务: 对整个评论作情感分类

  • • • 类: 正面, 负面, 中立
      • 假设: 每个文档 (或评论) 仅针对单一对象并且仅包含单一观点持有者的观点.

  • 在句子层次:

    ​ 任务1: 识别主观的/含观点的句子

  • • • 类: 客观的, 主观的(含观点的)
    • 任务2: 句子的情感分类
• • • 类: 正面, 负面, 中立
    • 假设: 一个句子仅含有一个观点。在很多情况下不成立, 我们可以进一步考虑分句或短语.

• 在特征层次:

  ​ 任务1: 识别和抽取被观点持有者(即评论人)评价的对象特征.

  ​ 任务2: 判定针对该特征的观点是正面的, 负面的还是中立的.

  ​ 任务3: 对特征的同义词作分组, 产生多个评论的基于特征的观点汇总.

Chapter 12 Web 使用挖掘

1、基本概念

（1）WEB使用（用法）挖掘是指自动发现和分析模型，这些模式来自于收集的点击流和相关数据或用户与一个或多个网站互动的结果。其目标是捕捉、建模并分析用户与网站交互的行为模式和模型。所发现的模式常常被表示成有着共同需求或兴趣的一群用户频繁访问的页面、对象或资源的集合。

（2）WEB用法挖掘的过程：数据收集和预处理——模式发现——模式分析。

• • 预处理：点击流数据被整理并分割为一组用户事务集合，用来表示每个用户对站点的不同访问；网站内容、结构、本体的语义领域知识等也被收集并整理。
  • 模式发现：利用统计学、数据库及机器学习等方法发现反映用户特定行为的隐藏模式以及WEB资源、会话和用户的简要统计。
  • 模式分析：已发现的模式和统计信息被进一步处理、过滤，进而得到聚集的用户模型以投入使用。

（3）数据来源和类型：

• • WEB用法挖掘的主要数据来源是：服务器日志文件。
  • 日志文件包括：WEB服务器访问日志和应用服务日志。
  • • 具体为：网站文件和元数据、操作数据库、应用程序模板和领域知识等。
  • 数据的分类：使用记录数据；内容数据；结构数据；用户数据。

（4）WEB使用记录数据预处理的关键元素：

• • 数据整合和清理、页面访问识别、用户识别、会话识别、事务识别、路径完善、数据整合

（5）WEB使用记录挖掘的数据建模：

• • WEB用法模式的发现和分析：
  • 常用的模式发现类型及分析技术：
  • • 会话和访问者分析、聚类分析和访问者分割、关联及相关度分析、序列和导航模式分析、基于WEB用户事务的分类和预测：

Other 推荐系统

• 定义：它是利用电子商务网站向客户提供商品信息和建议，帮助用户决定应该购买什么产品，模拟销售人员帮助客户完成购买过程。
• 推荐系统有3个重要的模块：用户建模模块、推荐对象建模模块、推荐算法模块。
• 推荐系统把用户模型中兴趣需求信息和推荐对象模型中的特征信息匹配，同时使用相应的推荐算法进行计算筛选，找到用户可能感兴趣的推荐对象，然后推荐给用户。

推荐系统 VS 搜索引擎

• 相同点：
• • • 都是一种帮助用户快速发现有用信息的工具
• 不同点：
• • • 搜索引擎需要用户主动提供准确的关键词来寻找信息
    • 推荐系统不需要用户提供明确的需求，而是通过分析用户的历史行为给用户的兴趣建模
• 从某种意义上说，推荐系统和搜索引擎对于用户来说是两个互补的工具
• • • 搜索引擎满足了用户有明确目的时的主动查找需求
    • 推荐系统能够在用户没有明确目的的时候帮助他们发现感兴趣的新内容

用户模块：

• 获取模型输入数据的方式有显式获取、隐式获取
• 显式的获取方式：用户主动告之
• • • 优点：简单而直接的做法，能相对准确地反映用户的需求，同时所得的信息比较具体、全面、客观，结果往往比较可靠
    • 缺点：很难收到实效，主要原因就是很少用户愿意花时间或不愿向系统表达自己的喜好
• 隐式获取法：指系统通过跟踪用户行为，通过推理获取用户的兴趣偏好
• • • 优点：减少用户很多不必要的负担，不会打扰用户的正常生活
    • 缺点：跟踪的结果未必能正确反映用户的兴趣偏好

基于用户的协同推荐

基于物品的协同推荐

基于内容的推荐

推荐系统评测：指标（预测准确度指标？覆盖率计算?）