期末考试复习用~

考试题型

  1. 名词解析（20分）
    • 中文写出英文全称，英文写出中文全称
  2. 简答题（2个*20分）
  3. 综合题（40分）
    • 范围：十大算法、Close算法
    • 内容：算法内容、伪代码

重点算法

  1. ID3：伪代码
  2. k-means：伪代码
  3. apriori：伪代码
  4. PageRank：定义、伪代码
  5. KNN：伪代码
  6. EM：定义
  7. Close：闭合项集

第一章、第二章

只考名词解释

名词解释

  1. 数据挖掘（Data Mining）

    从广义的观点，数据挖掘是从大型数据集（可能是不完全的、有噪声的、不确定性的、各种存储形式的）中，挖掘隐含在其中的、人们事先完全不知道的、对决策有用的知识的完整过程。从狭义的观点，我们可以定义数据挖掘是从特定形式的数据集中提炼知识的过程。

  2. web结构挖掘（Web structure mining）

    Web 结构挖掘是指通过分析不同网页之间 的超链结构，发现许多蕴涵在 Web 内容之外的对我们有潜在价值的模式 和知识的过程。

  3. 大数据（big data）

    指的是在传统数据处理应用软件不足以处理的大或复杂的数据集。大数据也可以定义为来自各种来源的大量非结构化或结构化数据。

  4. 人工智能（Artificial Inteligence）

    人工智能是利用数字计算机或者数字计算机控制的机器模拟、延伸和扩展人的智能，感知环境、获取知识并使用知识获得最佳结果的理论、方法、技术及应用系统。

  5. 机器学习（Machine Leaning）

    机器学习是计算机从数据中学习出规律和模式。以应用在新数据上做预测的任务。

  6. 知识工程（Knowledge Engineering）

    知识工程是运用现代科学技术手段高效率、大容量的获得知识、信息的技术。目的是为了最大限度地提高人的才智和创造力，掌握知识和技能，提高人们借助现代化工具利用信息的能力，为智力开发服务。

  7. 信息检索（Information Retrieval）

    广义的信息检索全称为“信息存储与检索”，是指将信息按一定的方式组织和存储起来，并根据用户的需要找出有关信息的过程。狭义的信息检索为“信息存储与检索”的后半部分，通常称为“信息查找”或“信息搜索”，是指从信息集合中找出用户所需要的有关信息的过程。

  8. 数据可视化（Data Visualization）

    数据可视化，是关于数据视觉表现形式的科学技术研究。其中，这种数据的视觉表现形式被定义为，一种以某种概要形式抽提出来的信息，包括相应信息单位的各种属性和变量。

    ……

第三章 关联规则挖掘理论和方法

基本概念和解决方法

一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找强关联规则地过程。

几个概念：

  • 支持度：项目集$I_1$在数据集D上的支持度是指包含$I_1$的事务在D中所占的比例
  • 频繁项目集：项目集$I$中满足最小支持度的非空子集
  • 最大频繁项目集：频繁项目集中不被其他集合包含的集合
  • 可信度：包含$I_1$和$I_2$ 的事务数与包含$I_1$的事务数之比
  • 强关联规则：$D$ 在$I$上满足最小支持度和最小信任度的关联规则称为强关联规则。

关联规则挖掘问题可以划分为两个子问题：

  1. 发现频繁项目集

    即根据最小支持度找到所有频繁项目集

  2. 生成关联规则

    根据最小可信度，在最大频繁项目集中寻找强关联规则。

项目集空间理论

频繁项目集的子集是频繁项目集，非频繁项目集的超级是非频繁项目集

apriori算法(伪代码必考)

伪代码

image-20221117155706261

主要步骤

image-20221117155759820 image-20221117155940246

Close算法（闭合项集计算必考）

原理

一个频繁闭合项目集的所有闭合子集一定是频繁的，一个非频繁闭合项目集的所有闭合超集一定是非频繁的。

伪代码

image-20221117160655449 image-20221117160732421 image-20221117160752506 image-20221117160818926

算法示例（必考）

image-20221117161340553 image-20221117161409624 image-20221117161452894 image-20221117161525291

计算闭合项集及支持度（P85-P87）

image-20221117162551122

第四章 分类方法

分类的目的是学会一个分类函数或分类模型，该模型能把数据库中的数据项映射到给定类别中的某一个类别。

基本概念和步骤

  1. 基本概念

给定一个数据库$D={t_1,t_2,…,t_n}$和一组类$C={C_1,C_2,…,C_n}$，分类问题是去确定一个映射$f: D\to C$，每个元组$t_i$被分配到一个类中。一个类$C_i$包含映射到该类中的所有元组，即$C_j={f(t_i)=C_j,1 \le i \le n,$且$t_i \in D }$。

  1. 步骤

通常分为两个步骤：建模和使用

  1. 建模
    简历一个模型，描述预定的数据类集或概念集。
    通过分析由属性描述的数据库元组来构造模型。数据元组也称样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。
    通常，学习模型用分类规则、决策树或等式、不等式、规则式等形式提供。这些规则可以为以后的数据样本分类，也能对数据库的内容提供更好的理解。
  2. 使用
    使用模型进行分类。

KNN算法（伪代码必考）

伪代码（必考）

image-20221117164319335

算法示例

image-20221117164409710 image-20221117164433723 image-20221117164454753

ID3算法（伪代码必考）

基本概念

  • 决策树中每一个非叶节点对应着一个非类别属性，树枝代表这个属性的值。一个叶节点代表从树根到叶节点之间的路径对应的记录所属的类别属性值。
  • 每一个非叶节点都将与属性中最大信息量的非类别属性相关联。
  • 采用信息增益来选择出能够最好地将样本分类的属性。

  1. 信息熵：是对随机变量不确定度的度量，熵越大，随机变量的不确定性就越大。如果一个事件发生的概率是$p(x)$，则其信息熵为$H=log\frac{1}{p(x)}$

  2. 信息增益（information gain）：是针对一个一个特征而言的，就是看一个特征，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。

伪代码（必考）

image-20221117165412997

EM算法（定义必考）

贝叶斯定理
$$
P(H|X) = \frac{(PX|H)P(H)}{P(X)}
$$

EM算法定义（必考）

在概率模型中寻找参数最大似然估计或者最大后验预计的算法。用于寻址，依赖于不可观察的隐形变量的概率模型中,参数的最大似然预计。

image-20221117170919238

步骤

步骤（基本必考）：最大期望算法经过两个步骤交替进行计算

  • 第一步是计算期望（E），利用对隐藏变量的现有预计值，计算其最大似然预计值。

    $$
    Q(h\prime|h)\leftarrow E[ln\ P(Y|h\prime)]
    $$

  • 第二步是最大化（M）。最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数预计值被用于下一个E步计算中，这个过程不断交替进行。

第五章 聚类方法

K-means算法（伪代码必考）

算法基本思想

  1. 划分聚类方法

    给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每个划分就代表一个簇，k<=n。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件：

    • 每一个簇至少包含一个对象
    • 每一个对象属于且仅属于一个簇。

    对于给定的k，先初始划分，再反复迭代改变划分，使每一次都比前一次更好。即同一簇中的对象越近越好，不同簇中的对象越远越

    好。最小化所有对象与其参照点之间的相异度之和。

  2. k-平均算法

    • 相似度的计算根据一个簇中对象的平均值来计算

    • 首先随机的选择k个对象，每个对象初始地代表了一个簇地平均值或中心。对剩余地每个对象根据其与各个簇中心的距离，将其赋给最近的簇。然后重新计算每个簇的平均值，不断重复。

    • 准则函数为
      $$
      E = \sum_{i=1}^{k} \sum_{i\in C_i} |x-\overline x_i|^2
      $$

      image-20221117180311620

伪代码（必考）

image-20221117180502715

k-medoids方法(PAM算法)（定义必考）

定义（必考）

k-means算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象于其参照点之间的相异度之和的原则来执行的。

image-20221117180815186 image-20221117181540715

伪代码

image-20221117181144810

AGNES算法

自底向上凝聚算法（AGglomerative NESting）

基本思想

将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。

伪代码

image-20221117181828826

DIANA算法

DIANA（Divisive ANAlysis）算法属于分类地层次聚类。

基本思想

它采用一种自顶向下的策略，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。

伪代码

image-20221117182029041

DBSCAN算法

DBSCAN：Density-Based Spatial Clustering of Applications with Noise，噪声环境下的密度聚类算法

基本思想

image-20221117182915374 image-20221117182953001

描述

image-20221117182634942

伪代码

image-20221117182712477

第六章 时间序列和序列模式挖掘

时间序列数据挖掘通过研究信息的时间特性，深入洞悉事物进化的机制，是获得知识的有效途径。

时间序列挖掘在宏观的经济预测、市场营销、客流量分析、太阳黑子数、月降水量、河流流量、股票价格变动等众多领域得到应用。事实上，社会、科学、经济、技术等领域中广泛存在着大量的时间序列数据有待进一步的分析和处理。

时间序列(Time Series)挖掘：就是要从大量的时间序列数据中提取人们事先不知道的、但又是潜在有用的与时间属性相关的信息和知识，并用于短期、中期或长期预测，指导人们的社会、经济、军事和生活等行为。通过对过去历史行为的客观记录分析，揭示其内在规律，进而完成预测未来行为等决策性工作。

第七章 Web挖掘技术

基本概念

利用数据挖掘的思想和方法，在Web上挖掘出有用的信息

PageRank算法（伪代码必考）

基本思想

如果一个网页被很多其他网页链接到的话说话这个网页比较重要，也就是PageRank值会相对较高②如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高。

伪代码（必考）
image-20221117183844439