数据挖掘课程复习笔记

大纲

1.认识数据挖掘

1、数据挖掘的定义 2、有指导学习和无指导学习 3、数据挖掘的过程

2.基本数据挖掘技术

1、决策树概念和C 4.5算法的一般过程 2、决策树关键技术：最大增益率 3、决策树规则：决策树，产生式规则，正确率和覆盖率 4、Apriori算法的基本思想 5、关联规则及其置信度和支持度 6、K-means算法的基本思想 7、K-means聚类分析实例

3.数据库中的知识发现

1、KDD的定义(了解) 2、数据预处理：直方图归约、数据规范化和数据平滑

5.评估技术

1、评估分类类型输出模型：混淆矩阵和分类正确率、查准率和查全率 2、评估数值型输出模型：平均绝对误差，均方误差，均方根误差

6.神经网络

1、人工神经元模型(会画会计算) 2、BP神经网络结构（会画，比如一个输入一个输出两个包含三个神经元隐层），前向计算过程 3、BP算法的一般过程 4、卷积神经网络的基本操作——卷积和池化，卷积特征（局部感受野、权值共享）

7.统计技术

1、一元线性回归、多元线性回归——最小二乘法 2、贝叶斯分析：贝叶斯分类器 3、凝聚聚类算法的一般步骤、例题 4、Cobweb分层聚类算法：CU值的计算

第1章 认识数据挖掘

数据挖掘的定义

技术角度：利用计算机技术，从数据中自动分析并提取信息的处理过程；目的是发掘数据中潜在的有价值的信息；一般使用机器学习、统计学、模式识别等多种方法来实现。 学科角度：交叉学科，设计人工智能、统计学、可视化、并行计算等。 商业角度：揭示隐藏的、未知的或验证已知的规律；

有指导学习和无指导学习

机器学习中的基本方法有：概念学习、归纳学习、有指导学习和无指导学习。

有指导学习：通过对大量已知分类或输出的实例进行训练，调整分类模型的结构，达到建立准确分类或预测位置模型的目的；这种基于归纳的概念学习过程被称为有指导学习。 无指导学习：在学习训练之前，无预先定义好分类的实例。数据实例按照某种相似度度量方法，计算相似程度，将最为相似的实例聚类在一个簇中，再解释和理解每个簇的含义，从中发现聚类的意义。（K-Means，凝聚聚类，概念分层Cobweb，EM算法）

数据挖掘的过程

四个步骤：

1. 准备数据，包括训练数据和检验数据；
2. 选择一种数据挖掘技术或算法，将数据提交给挖掘软件；
3. 解释和评估模型；
4. 模型应用； 准备数据可从数据库、数据仓库、平面文件收集； 选择技术与算法需要考虑：

• 判断学习是有指导还是无指导的；
• 数据集中怎样划分训练、测试、检验数据；
• 如何设置数据挖掘算法的参数；

数据挖掘的作用（种类分类，非技术）

• 有指导学习
  • 分类
  • 估计
  • 预测
• 无指导聚类
• 关联关系分析

第2章 基本数据挖掘技术

决策树

1、决策树概念和C 4.5算法的一般过程 2、决策树关键技术：最大增益率 3、决策树规则：决策树，产生式规则，正确率和覆盖率

概念

决策树是一个树状结构的模型，每个节点表示对象的某个属性，分支表示属性的某个可能取值，叶节点的取值就是决策树的输出结果。

C4.5算法

（1）给定一个表示为“属性-值”格式的数据集T。数据集由多个具有多个输入属性和一个输出属性的实例组成。 （2）选择一个最能区别T中实例的输入属性，C4.5使用增益率来选择该属性。 （3）使用该属性创建一个树节点，同时创建该节点的分支，每个分支为该节点的所有可能取值。 （4）使用这些分支，将数据集中的实例进行分类，成为细分的子类。 （5）将当前子类的实例集合设为T，对数据集中的剩余属性重复（2）（3）步，直到满足以下两个条件之一时，该过程终止。创建一个叶子节点，该节点为沿此分支所表达的分类类别，其值为输出属性的值。

• 该子类中的实例满足预定义的标准，如全部分到一个输出类中，或者分到一个输出类中的实例达到某个比例；
• 没有剩余属性。

关键技术

选择最能区分实例属性的方法

优先选择具有最大增益率的属性来使数据的概化程度最大（层次和节点数最小）。 信息熵 熵是不确定程度的度量，越大则信息量越大，传输的信息越多； $$H(x)=-\sum_{i=1}^n {p(x_{i})log_{2}(p(x_{i}))}$$ 信息增益 增益越大，熵降越快，越利于分类。 $$Info(I)=-\sum\frac{出现在i类中的数量}{实例总数}log_{2}\frac{出现在i类中的数量}{实例总数}$$ $Info(I)$为当前数据集所有实例表达的信息总量； $$Info(I,A)=\sum\limits_{j=1}^{k}\frac{出现在j类中的实例个数}{所有实例总数}Info(j类)$$ $Info(I,A)$为根据属性A的k个取值分类I后的信息量； $$SplitsInfo(A)=-\sum\limits_{i}^{k}\frac{出现在j类中的实例个数}{所有实例总数}log_{2}\frac{出现在j类中的实例个数}{所有实例总数}$$ $SplitsInfo(A)$是对A属性的增益值的标准化； $$Gain(A)=Info(A)-Info(I,A)$$ $$GainRatio(A)= \frac{Gain(A)}{SplitsInfo(A)}$$

剪枝方法

检验方法

• 百分比检验
• 交叉验证 k折 留出 留一

决策树规则

将决策树翻译成规则，计算正确率与覆盖率；

1
2
3

IF Courses <≤5 and Weather = Rain THEN Play = No
正确率：3/5 = 60% 覆盖率：3/8 = 37.5%
正确率:满足整句/满足前半句 覆盖率：满足整句/满足后半句

优缺点（了解）

优点 （1）容易被理解和被解释，并且可以被映射到一组更具吸引力的产生式规则。 （2）不需要对数据的性质作预先的假设。 （3）能够使用数值型数据和分类类型数据的数据集建立模型。 局限性 （1）输出属性必须是分类类型，且输出属性必须为一个。 （2）决策树算法是不稳定（Unstable）的。 （3）用数值型数据集创建的树较为复杂（如例2.3中的未剪枝的决策树），因为数值型数据的属性分裂通常是二元分裂。

关联规则

Apriori算法的基本思想

• 生成条目集。条目集是符合一定的支持度要求的“属性-值”的组合。那些不符合支持度要求的组合被丢弃，因此规则的生成过程可以在合理的时间内完成。
• 使用生成的条目集依据置信度创建一组关联规则。

关联规则及其置信度和支持度

支持度：满足整句/满足后句 置信度：满足整句/满足前句

在实际使用时，依次生成单项、双项、三项条目集，以生成的条目集为基础创建关联规则。

1
2
3
4
5
6
7

以双项条目集中的第一条条目生成的两条规则——
IF Book =1 THEN Earphone = 1 （置信度：4/5 = 80%，保留）
IF Earphone = 1 THEN Book =1（置信度：4/7 = 57.1%，删除）
以三项条目集中的第一条条目生成的三条规则——
IF Book =1 & Earphone = 1 THEN DVD = 1（置信度：4/4 = 100%，保留）
IF Book =1 & DVD = 1 THEN Earphone = 1（置信度：4/4 = 100%，保留）
IF Earphone = 1 & DVD = 1 THEN Book =1（置信度：4/6 = 66.7%，删除）

聚类技术

K-means算法的基本思想

1. 随机选择一个K值，用以确定簇的总数。
2. 在数据集中任意选择K个实例，将他们作为初始的簇中心。
3. 计算这K个簇中心与其他剩余实例的简单欧式距离。用这个距离作为实例之间相似性的度量，将与某个簇相似度高的实例划分到该簇中，成为其成员。
4. 使用每个簇中的实例来计算新的簇中心。
5. 如果得到的新的簇中心等于上次迭代的簇中心，终止算法。否则，用新的簇中心重复3~5.

K-means聚类分析实例

优缺点

优势 非常受欢迎的算法，容易理解，实现简单。 局限性 （1）只能处理数值型数据，若数据集中有分类类型的属性，要么将该属性删除，要么将其转换成等价的数值数据。 （2）算法开始前，需要随机选择K值作为初始的簇个数（带有随意性，错误的选择将影响聚类效果）。通常选择不同的K值进行重复实验，期望找到最佳K值。 （3）当簇的大小近似相等时，K-means算法的效果最好。 （4）对于聚类贡献不大的属性可能会对聚类效果造成影响（孤立点）。在聚类之前需对属性进行选择。 （5）簇的解释困难。可使用有指导的挖掘工具对无指导聚类算法所形成簇的性质作进一步的解释。

第3章 数据库中的知识发现

KDD的定义(了解)

Knowledge Discovery in Data，从数据集中提取可信的、新颖的、具有潜在价值的、能被人理解的、非繁琐的处理过程（大部分步骤由系统自动执行）。

KDD过程模型

经典模型

CRISP-DM商业模型

联机模型OLAM

数据预处理：直方图归约、数据规范化和数据平滑

分箱法：（噪声处理->数据平滑） 将==数据排序==，如3，6，12，22，24，26，27，30，30 “等高度”划分成三个箱，每个箱子中的数据个数相同； “等宽度”，每个箱子跨越的范围固定； 均值、最值、保留最值做边界其余靠拢等方式平滑。

直方图规约 划分等宽或等深的桶，计数，画直方图

数据标准化

1. 最小-最大缩放（Min-Max Scaling）：将数据缩放到0-1之间的范围，通过对原始数据进行线性变换来实现。具体来说，最小-最大缩放将原始数据v缩放到新的取值范围v’，计算公式为$v_{i}^{’}=\frac{v_{i}-minA}{maxA-minA}(b-a)+a$，其中b-a是区间长度，a是区间起始点，这样可以把规范化的结果映射到某一段区间内，如果没有说明，可以忽略区间的参数。

2. Z-score标准化（Z-score normalization）：将数据缩放为均值为0、标准差为1的分布，使得数据分布在以0为均值，1为标准差的正态分布中。具体来说，Z-score标准化将原始数据x标准化为新的取值范围y，计算公式为y = (x - μ) / σ，其中μ和σ分别是原始数据的均值和标准差。

3. 小数定标标准化（十进制缩放）（Decimal scaling）：通过移动小数点的位置，将数据缩放到[-1,1]或[-0.5,0.5]之间的范围。具体来说，小数定标标准化将原始数据x乘以10的k次方，得到新的取值范围y，计算公式为y = x / 10^k，其中k是满足10^(k-1) ≤ |x| < 10^k的整数。根据最大值决定移动的位数。

4. 对数标准化是一种将数据转换为对数的数据预处理方法，常用于将非负数数据进行平滑处理，使其更易于比较和分析。具体来说，对数标准化将原始数据x取对数，得到新的取值范围y，计算公式为y = log(x)。

5. 归一化（Normalization）：将数据缩放到单位长度或者单位范围内，常用的归一化方法包括L1范数归一化和L2范数归一化。具体来说，L1范数归一化将原始数据x缩放为新的取值范围y，计算公式为y = x / (|x1| + |x2| + … + |xn|)；L2范数归一化将原始数据x缩放为新的取值范围y，计算公式为y = x / sqrt(x1^2 + x2^2 + … + xn^2)。

第5章 评估技术

评估分类类型输出模型

评估数值型输出模型

$$MAE=\frac{|a_{1}-c_{1}|+|a_{2}-c_{2}|+…+|a_{n}-c_{n}|}{n}$$ $$MSE=\frac{(a_{1}-c_{1})^2+(a_{2}-c_{2})^2+…+(a_{n}-c_{n})^2}{n}$$ $$RMS=\sqrt{MSE}=\sqrt{\frac{(a_{1}-c_{1})^2+(a_{2}-c_{2})^2+…+(a_{n}-c_{n})^2}{n}}$$

第6章 神经网络

人工神经元模型

R个输入$p_i∈R$，即R维输入矢量p n: net input, $n=wp+b$。 R个权值$wi∈R$，即R维权矢量w 阈值b 输出a=f(n), f: transfer function 常用的激活函数 $$a=f(n)=hardlim(n)=\begin{cases} {1},n>=0 \ {0} ,n<0\ \end{cases}$$ $$a=f(n)=hardlim \quad s(n)=\begin{cases} {1},n>=0 \ {-1} ,n<0\ \end{cases}$$ $$a=f(n)=n$$ $$a=f(n)=\frac{1}{1+e^{-n}}$$ Sigmoid函数最重要的特征就是无限可微。

BP神经网络

BP神经网络结构，前向计算过程

注意，每一个神经元都与后一层全连接，同一层之间不连接。

BP算法的一般过程

B-P算法的学习过程如下： （1）选择一组训练样例，每一个样例由输入信息和期望的输出结果两部分组成。 （2）从训练样例集中取一样例，把输入信息输入到网络中。 （3）分别计算经神经元处理后的各层节点的输出。 （4）计算网络的实际输出和期望输出的误差。 （5）从输出层反向计算到第一个隐层，并按照某种能使误差向减小方向发展的原则，调整网络中各神经元的连接权值。 （6）对训练样例集中的每一个样例重复（2）—（5）的步骤，直到对整个训练样例集的误差达到要求时为止。

CNN

卷积

第一种神器叫做局部感受野。因为在一个图像中，距离较近的像素联系较为紧密，而距离较远的像素相关性则较弱。因而，每个神经元其实没有必要对全局图像进行感知，只需要对局部进行感知，然后在更高层将局部的信息综合起来就得到了全局的信息。 第二级神器，即权值共享。 怎么理解权值共享呢？我们可以把卷积操作看成是提取特征的方式，该方式与位置无关。这其中隐含的原理则是：图像的一部分的统计特性与其他部分是一样的。这也意味着我们在这一部分学习的特征也能用在另一部分上，所以对于这个图像上的所有位置，我们都能使用同样的学习特征。 权重共享有什么好处呢？一方面，重复单元能够对特征进行识别，而不考虑它在可视域中的位置。 另一方面，权值 共享使得我们能更有效的进行特征抽取，因为它极大的减少了需要学习的自由变量的个数。通过控制模型的规模，卷积网络对视觉问题可以具有很好的泛化能力。 解释卷积层的最好方式是想象一个手电筒正在图像的左上方进行照射，假设手电照射的区域是5 x 5的范围。再想象下这个手电筒在输入图像的各个区域进行滑动。在机器学习术语中，这个手电筒叫做滤波器（有时候也称为神经元或者卷积核），它照射着的区域被称为感受野。这个滤波器也是一系列的数据（这些数据被称为权重或者参数)。

池化/采样

最大池化就是选择池化窗口中的最大值作为采样值 平均池化就是将池化窗口中所有值相加取平均，以平均值作为采样值。 池化可以降低参数量、减少过拟合的风险。

第7章 统计技术

回归分析

回归分析是一种统计分析方法，用来确定两个或两个以上变量之间的定量的依赖关系，并建立一个数学方程来概化一组数值数据。 最小二乘法 构造误差函数做目标函数（一般是二阶的），对自变量求偏导

贝叶斯分析

一种参数估计方法，将关于未知参数的先验信息与样本信息结合（列表），根据贝叶斯公式，计算条件概率，得出后验信息，从而推断未知参数； $$P(H|E)=\frac{P(E|H)P(H)}{P(E)}$$ 存在的问题：

1. 概率为0–加小常数
2. 数据缺失–简单忽略，概率记为1

聚类技术

聚类有划分聚类（K-Means）、分层聚类(凝聚、分裂）、模型聚类（EM算法）三大种；

凝聚聚类算法 一种无指导聚类算法。 开始时，每个实例在不同的分类中，各自单独成一簇； 找两个最相似的簇，合并，直到满足要求或合并成一类为止

Cobweb分层聚类 一种增量式分层聚类算法。使用分类树对实例进行分类，分类树的构造过程是一种概念分层的过程。树的根节点是概念最高层次，包含所有域实例的汇总信息；除了叶节点，其他节点都是树的基层节点，表达了概念划分的层次。使用评价函数来度量概念层次的质量。分类对象必须是分类类型的。 算法：

• 建立一个类，使用第一个实例作为它的唯一成员；
• 对于剩余实例。在每个树层次（概念分层）上，用评价函数决定执行下列动作之一：
  • 将新的实例放到一个已存在的簇中；
  • 创建一个只有这个新实例的新概念簇；

CU值的计算： $$CU=\frac{\sum\limits_{k=1}^{m}P(C_k)(\sum\limits_{i}\sum\limits_{j}P(A_{i}=V_{ij}|C_{k})^{2}-\sum\limits_{i}\sum\limits_{j}({A_{i}=V_{ij})^2})}{m}$$ $P(A_{i}=V_{ij}|C_k)$表示在$C_k$类的全体成员中，属性$A_i$取值为$V_{ij}$的概率 $P(A_{i}=V_{ij})$表示在整个数据集中，属性$A_i$取值为$V_{ij}$的概率 $P(C_k)$表示每个类$C_k$的概率

优势：能够自动调整类（簇）的个数，不会因为随机选择分类个数的不合理性而造成聚类结果的不理想。 局限性：

• 对实例顺序敏感，需要引入两种附加操作——合并和分解降低敏感性。
• 假设每个属性的概率分布是彼此独立的，而实际这个假设不总是成立；
• 类（簇）的概率分布的表示、更新和存储的复杂程度，取决于每个属性取值个数。当属性取值较多时，算法的时间和空间复杂度会很大。
• 偏斜的实例数据会造成概念分层树的高度不平衡，也会导致时间和空间复杂度的剧烈变化。