BUAA数据挖掘导论（教材）笔记

1 绪论

1.4 数据挖掘任务

预测建模：分类对应离散变量、回归对应连续变量
关联分析：发现数据中强关联特征的模式
聚类分析：旨在发现紧密相关的观测值组群
异常检测：异常点或离群点

2 数据

2.1 数据类型

数据集：数据对象的集合

2.1.1 属性和度量

def 2.1 属性：对象的性质或特性

def 2.2 测量标度：将数值或符号值与对象的属性相关联的规则(函数)

属性的类型：标称序数区间比率

属性层次的变换

标称：唯一标识符( $= | \neq$ ) 一对一变换

序数：属性信息确定序信息（<|>）保序变换，变换函数单调即可

区间：值之间的差具有意义，即存在测量单位( $+ |-$ )线性变换 $new\_value = a \times old\_value + b$

比例：差、比率都有意义( $\times | \space/$ ) $new\_value = a \times old\_value$

用值的个数描述属性

离散的：具有有限或无限可数个值

连续的：取实数值的属性

非对称的属性

出现非0值才是重要的（意为一般情况下均为稀疏，我们只关心1值）

2.1.2 数据集类型

一般特性

维度、稀疏性、分辨率

记录数据

事物数据或购物篮数据：每行一个记录，记录非对称属性

数据矩阵（模式矩阵）：每行为一个对象，每列为一个属性

稀疏数据矩阵

基于图形的数据

带有对象之间联系的数据

具有图形对象的数据

有序数据

时序数据（时间数据）、序列数据、时间序列数据（时间自相关）、空间数据（空间自相关）

非记录数据

2.2 数据质量

第一步对数据的检测和纠正称为数据清理

2.2.1测量和数据收集问题

测量误差和数据收集错误

噪声和伪像

噪声：测量误差的随机部分

伪像：数据的确定性失真

精度、偏倚度、准确率

def 2.3 精度：重复测量值之间的接近程度

def 2.4 偏倚：测量值与被测量值之间的系统偏差

def 2.5 准确率：被测量值的测量值与实际值之间的接近程度

离群点（异常）、遗漏值

有的对象缺少某些属性值

方法：删除数据对象或属性、估计遗漏值、在分析时忽略遗漏值

不一致的值、重复数据

2.2.2 关于应用的问题

时效性、相关性、关于数据的知识

2.3 数据预处理

2.3.1 聚集

定义：将两个或多个对象合并成单个对象

2.3.2抽样

定义：选择数据对象子集进行分析

抽样方法

放回、无放回、分层抽样

渐进抽样

自适应、渐进抽样

2.3.3 维归约

维度：数据属性的个数

维灾难

维归约的线性代数技术

主成分分析（PCA）：原属性线性组合为新属性，尽可能多捕获数据变差(见3.5)

奇异值分解（SVD）：线性代数技术（不知道）

2.3.4特征子集选择

去除冗余特征、不相关特征；具有以下方法：

嵌入方法

作为数据挖掘算法的一部分，算法选择特征（构造决策树分类器）

过滤方法

独立于数据挖掘算法的特征选择算法

包装方法

类似于枚举的黑盒算法

特征子集选择体系结构、特征加权

2.3.5 特征创建

特征提取

映射数据到新的空间

例子：傅里叶变换、小波变换

特征构造

2.3.6 离散化和二元化

二元化

举例：二进制码和独热码

连续属性离散化

连续属性值排序后拆分为多个区间

非监督离散化

等频率-每个区间放入相同数量的对象

等宽-将属性的值划分为具有相同宽度的区间

K均值聚类算法等

※※※监督离散化（一种基于熵的方法）

$e_i=-\sum_{j=1}^{k}p_{ij}\log_{2}p_{ij}$

$e=\sum_{i=1}^nw_ie_i$

$k$ 为类的个数， $p_{ij}$ 为第 $i$ 个区间中类 $j$ 的出现比例；总的熵值为各个区间熵值按每个区间值的个数加权的平均值。

划分属性的方法：切值为两部分，尽可能产生最大熵；再重复选取最大熵区间反复分割的过程。

具有过多值的分类属性

2.3.7 变量变换

简单函数

例子： $x^k$ $\log_{?}x$ $\sqrt{x}$ $1/x$

规范化或标准化

统计学的标准化： $x'=(x-\overline{x})/s_x$ 均值0 标准差1

※※※2.4 相似性及相异性度量

定义术语：邻近度-表示相似性或相异性

2.4.1 基础概念

定义

相似度 $s$ ：两个对象间的相似度意为两个对象间相似程度的数值度量；通常值域为 $[0, 1]$

相异度 $d$ ：两个对象间的差异层度的数值度量，有时取距离作为同义词，通常在 $[0, 1]$ 取值，也有在 $[0, +\infty]$ 取值的

变换

相似度到 $[0, 1]$ 的变换可以由 $s'=(x-min\_s) / (max\_s-min\_s)$ 给出

若为在 $[0, +\infty]$ 的数据，可以由 $d'=d/(1+d)$ 给出，注意原来相异性上较大的值会被压缩到1附近

2.4.2 简单属性之间的相似度和相异度

标称： $d = 1\space if \space x == y \space else \space 0$ $s = \neg\space{d}$

序数： $d = |x-y|/(n-1)$ $s = 1 - d$

区间/比率： $d=|x-y|$ $s=-d \space or \space others$

2.4.3 数据之间的相异度

推广欧几里得距离，得到闵可夫斯基距离：

$d(x,y) = (\sum_{k=1}^{n}|x_k-y_k|^r)^{1/r}$

其中 $r$ 为参数， $r=1$ ：城市距离 $r=2$ ：欧几里得距离 $r=3$ ：上确界距离

2.4.4 数据对象之间的相似度

满足条件： $s = 1 \space only \space if \space x == y$

$s(x,y)=s(y,x)$

※※※2.4.5 邻近性度量的例子

二元数据的相似性度量

（两个仅包含二元属性的对象间的相似性度量也称为相似系数）以下设 $x$ 、 $y$ 为两个对象，有 $n$ 个二元属性，记以下四个量：

$f_{00}、f_{01}、f_{10}、f_{11}$ 为 $x、y$ 分别取两个值的属性个数

我们有以下两个统计量：

简单匹配系数（SMC）

$SMC=\frac{值匹配的个数}{总属性个数}=\frac{f_{00} + f_{11}}{\sum{f_i}}$

Jaccard系数

忽略 $f_{00}$ 即稀疏矩阵中的全0值

$J=\frac{1-1匹配个数}{不涉及0-0匹配个数}=\frac{f_{11}}{f_{01}+f_{10}+f_{11}}$

余弦相似度

用于处理稀疏的非二元向量

$cos(x,y)=\frac{\boldsymbol{x}}{||x||} \times \frac{\boldsymbol{y}}{||y||}$

广义Jaccard系数(Tanimoto系数)

$EJ(x,y) = \frac{\boldsymbol{x}\cdot\boldsymbol{y}}{||\boldsymbol{x}||^2+||\boldsymbol{y}||^2-\boldsymbol{x}\cdot\boldsymbol{y}}$

Bregman散度

计算用一添加过噪声的变量模拟原变量上的失真

$D(\boldsymbol{x},\boldsymbol{y})= \phi(\boldsymbol{x})-\phi(\boldsymbol{y}) - <\nabla\phi(\boldsymbol{y}),(\boldsymbol{x}-\boldsymbol{y})>$

其中， $<>$ 为内积符号，欧几里得空间中，内积即为点积， $\phi$ 为一给定的严格凸函数（ $\phi''>0$ ）

2.4.6 邻近度计算问题

距离度量的标准化和相关性

属性具有不同尺度即距离不同时，且数据分布近似于高斯分布（正态分布）时，将欧几里得距离推广为Mahalanobis距离，定义为：

$mahalanobis(\boldsymbol{x},\boldsymbol{y})= (\boldsymbol{x}-\boldsymbol{y})\sum^{-1}(\boldsymbol{x}-\boldsymbol{y})^T$

其中的 $\sum^{-1}$ 协方差为矩阵的逆

组合异种属性的相似度

$similarity(\boldsymbol{x},\boldsymbol{y})=\frac{\sum_{k=1}^{n}\delta_ks_k(\boldsymbol{x},\boldsymbol{y})}{\sum_{k=1}^n\delta_k}$ ，也可以使用权值和闵可夫斯基距离

其中 $s_k$ 为相似度，系数 $\delta$ 只要 $x$ 、 $y$ 不同时为 $0$ 即取 $1$ ，否则取 $0$

3 探索数据

3.2 汇总统计

3.2.1 频率和众数

频率

$frequency(\mu_{i})=\frac{具有属性值\mu_i的对象数}{m}$ ，其中 $m$ 为对象总数(3.2中下同)

众数

具有最高频率的值

3.2.2 百分位数

$x_p$ 是一个 $x$ 值，使得 $x$ 的所有值的 $p\%$ 观测值小于 $x_p$

3.2.3 位置度量：均值和中位数

均值： $mean(x)=\overline{x}=\frac{1}{m}\sum_{i=1}^{m}x_i$

中位数： $median(x)=x_{(r+1)} \space if \space x = 2r+1 \space else \space \frac{1}{2}(x_{(r)}+x_{(r+1)}) \space when \space x=2r$

截断均值

指定百分位数 $p$ ，丢弃高端低端各 $\frac{p}{2}\%$ 的数据再计算均值，所的结果称为阶段均值

3.2.4 散布度量：极差和方差

极差： $range(x)=max(x)-min(x)$

方差： $variance(x)=s_x^2=\frac{1}{m-1}\sum_{i=1}^m(x_i-\overline{x})^2$

绝对平均偏差AAD

$AAD(x)=\frac{1}{m}\sum_{i=1}^m|x_i-\overline{x}|$

中位数绝对偏差MAD

$MAD(x)=median({|x_1-\overline{x}|,...,|x_m-\overline{x}|})$

四分位数极差IQR

$IQR(x)=x_{75\%}-x_{25\%}$

3.2.5 多元汇总统计

协方差矩阵 $S$

矩阵元素 $s_{ij}=covariance{(x_i,x_j)}=\frac{1}{m-1}\sum_{k=1}^m(x_{ki}-\overline{x_i})(x_{kj}-\overline{x_j})$ ，主要表示线性相关关系

其中 $x_{ki}$ 为 $x$ 第 $k$ 个对象的第 $i$ 个属性的值

注意协方差矩阵的对角线上为属性方差

3.4 OLAP和多元数据分析

OLAP：联机分析处理

3.4.3 分析多维数据

数据立方体：计算聚集量

关心的问题：在多维数据上，我们往往希望计算聚集总和涉及固定某些属性，也即维度的值，而在其余属性（维度）上直接求和。

数据立方体：数据的多维表示，连同所有可能的总和（聚集）称作数据立方体，可能多于或少于三维。

边缘总和：进一步对数据立方体的某些属性求和，边缘求和后的数据立方体是交叉表的典型例子。

维归约和转轴

前述聚集可看作一种形式的维归约

转轴：在除了两个维度外的所有维度上聚集，其结果是一个二维交叉表

切片和切块

切片：对一个或多个维指定特定的值，从整个多维数组中选择一组单元

切块：通过指定属性值区间选择单元子集

上卷和下钻

在一个维度内聚集单元，例如日聚集为月是上卷，月分解为日是下钻

3.5 补充：主成分分析 PCA

来源：清风数学建模课件

目的

原始数据，一行为一个对象共计 $n$ 个对象，一列为一组属性值共有 $p$ 个属性值

$\left[\begin{array}{clr} x_{11}&x_{12}&...&x_{1p}\\ x_{21}&x_{22}&...&x_{2p}\\...&...&...&...\\ x_{n1}&x_{n2}&...&x_{np} \end{array}\right]_{n\times{p}}$

提取新的一组变量：

$\begin{cases} z_1 = l_{11}x_1+l_{12}x_2+...+l_{1p}x_p \\ z_2 = l_{21}x_1+l_{22}x_2+...+l_{2p}x_p \\ ...\\ z_n = l_{n1}x_1+l_{n2}x_2+...+l_{np}x_p \end{cases}$

其中，任意的 $z_i$ 线性无关，且依次为所有线性组合中方差最大者。(要求： $\sum_{i=1}^{p}l_{ki}^2=1$ ， $k$ 取 $[1,n]$ 中任意值对应位第 $k$ 个对象)

则取出的 $z_1、z_2......z_p$ 依次为前 $p$ 个主成分

步骤

矩阵元素标准化 $x_{ij}'=\frac{x_{ij}-\overline{x_j}}{S_{j}}$ $S_j$ 为标准差，并计算其协方差矩阵 $R$ （协方差矩阵性质：半正定，即所有特征值 $\ge0$ ，且 $tr(R)=\sum{\lambda_i}=p$ ）
计算协方差矩阵 $R$ 的 $p$ 个特征值 $\lambda_1\ge\lambda_2\ge\lambda_3\ge...\ge\lambda_p$ ，及对应的特征向量 $a_1,a_2,a_3...a_p$

记 $a_i=\left[\begin{array}{clr} a_{1i}\\ a_{2i}\\...\\ a_{pi} \end{array}\right]_{p\times{1}}$
第 $i$ 个主成分 $F_i=a_{1i}x_{1}+a_{2i}x_{2}+...+a_{pi}x_p$

其贡献率为 $\frac{\lambda_i}{\sum_{k=1}^i\lambda_k}$
累计贡献率接近 $100\%$ 则可较好概括原始变量

注意事项

数学建模中，较困难的点在于如何解释新生成的主成分

PCA为一种降维算法，并可以用于变量属性的聚类分析

4 分类：基本概念、决策树与模型评估

4.1 预备知识

回归：处理连续变量（目标属性必须连续）

分类：处理离散变量（类属性必须离散）

定义：分类任务就是通过学习得到一个目标函数 $f$ ，把每个属性集 $x$ 映射到一个预先的标号 $y$

目标函数也叫作分类模型，可以用于描述型或预测型建模

4.2 解决分类问题的一般方法

采用学习算法，主要的例子：决策树分类法、基于规则的分类法、神经网络、支持向量机、朴素贝叶斯分类法

流程：一组训练集，即已有类标号数据，使用训练集建立分类模型，随后该模型用于检验集，即由类标号未知的记录组成

性能评估：模型正确的错误的检验记录数，存放于混淆矩阵的表格中进行评估，如下：

	预测类=0	预测类=1
实际类=0	$f_{00}$	$f_{01}$
实际类=1	$f_{10}$	$f_{11}$

分析模型可用准确率进而错误率

4.3 决策树归纳

决策树分类法

4.3.1 决策树的工作原理

基本的树的图论模型：根结点、内部结点（非根非叶）、叶结点（终结点）

非叶子结点均包含属性测试条件，根据具有不同特性的记录

4.3.2 如何建立决策树（Hunt算法）

核心思路：通过将训练记录划分为较纯的子集，以递归的方式建立决策树

符号： $D_t$ 是与结点 $t$ 相关联的测试数据集， $y=\{y_1,y_2...y_c\}$ 为类标号

递归定义：

若 $D_t$ 中的所有类都属于一个类，则 $t$ 为叶子结点，用 $y_t$ 标记
如果 $D_t$ 中包含多个类的记录，则选择一个属性测试条件，将记录划分为较小的子集，对于测试条件的输出，创建一个子女节点，并根据测试结果将 $D_t$ 的记录分布到子女节点中，然后对所有子女节点递归调用本算法

初始问题

算法有效条件：属性值全部组合在训练数据中出现，且每种组合都具有唯一的类标号；该条件过于苛刻，寻找附加条件如下：

算法条件二创建的子女结点可能为空，则该节点直接成为叶子结点，类标号为父节点训练集上的多数类
算法条件二若与 $D_t$ 关联二队所有记录都有相同的属性值，则该结点为叶子结点，标号为与该结点相关训练记录中的多数类

4.3.3 表示属性测试条件的方法

决策树算法需要为不同类属性提供表示属性测试属性及其2对应对应输出方法

二元属性

两个可能的输出

标称属性

多路划分、二元分组划分

序数属性

多路划分、二元分组划分；需要注意不违背有序性

连续属性

二元划分（比较测试）、多路划分（范围查询），同样不违背有序性

4.3.4 选择最佳划分的度量

符号： $p(i|t)$ 结点 $t$ 中属于类 $i$ 的记录所占的比例, $c$ 为类的个数

最佳度量一般为：根据划分后子女结点不纯性的程度，不纯性越低，类分布越倾斜

不纯性度量公式（三选一）：

$Entropy(t)=-\sum_{i=0}^{c-1}p({i|t})\log_{2}p({i|t})$

$Gini(t)=1-\sum_{i=0}^{c-1}[p(i|t)]^2$

$Classification error(t)=1-max[p(i|t)]$

量化测试条件分类效果：计算增益，式中 $I$ 不纯性度量值， $N$ 为父节点上记录总数， $k$ 为属性值个数， $N(\mu_j)$ 为与子女结点 $\mu_j$ 相关联的记录个数，下方公式中，使得 $\Delta$ 最大，只需右侧子女结点不纯值对于记录个数的加权平均尽量小即可，因为父节点的不纯值是固定的

$\Delta=I(parent)-\sum_{j=1}^{k}\frac{N(\mu_j)}{N}I(\mu_j)$

选择熵作为不纯性度量时，记 $\Delta$ 为 $\Delta_{info}$ ，即信息增益

标称属性的划分中，往往多路划分的子女结点不纯值更低

连续属性的划分中，以比较测试为例，确定比较值 $\mu$ 时，若朴素算法，对每个候选 $\mu$ ，需要遍历 $N$ 次（设有 $N$ 个记录），又因为对每个记录需要计算不纯值，故复杂度为 $O(N^2)$ ，开销过大。降低方法有：采用排序，复杂度 $O(NlogN)$ ，再依次遍历候选 $\mu$ （一般取两个记录值的中值），这时只需要依次更新两次遍历到的 $\mu$ 的中间记录的大小于情况即可，总复杂度为 $O(NlogN)$

还可以针对以上作进一步优化，仅考虑位于具有不同类标号的两个相邻记录之间的划分点。

增益率

避免因类似于ID的码属性造成干扰，可以采取的策略：只做二元划分（CART算法）、修改评估标准，考虑属性测试条件产生的输出数，即如下定义的增益率（C4.5算法）：

$Gain \space ratio= \frac{\Delta_{info}}{Split \space info}$

其中，划分信息 $Split \space info=-\sum_{i=1}^{k}P(\mu_i)log_2P(\mu_i)$ , $k$ 是划分的总数

4.3.5 决策树归纳算法

def TreeGrowth(E, F):
    if stopping_cond(E, F):
        leaf = createNode()
        leaf.label = Classify(E)
        return leaf
    else:
        root = createNode()
        root.test_cond = find_best_split(E, F)
        E_nxt = dict()
        for e in E: # 遍历所有训练记录
            v = root.test_cond(e)
            E_nxt[v].append(e) if v in E_nxt else E_nxt[v] = []
        for v in E_nxt.keys():
            child = TreeGrowth(E_nxt[v], F)
            root.addchild(child)
    return root

E为训练记录集，F为属性集
createNode()函数建立新结点，决策树的结点若为叶子结点，需要有类标号node.label，若非叶子结点，需要有测试条件node.test_cond
find_best_split()选择应当选用哪些属性作为划分训练记录的条件，例如Gini指标、熵等
Classify()为叶子结点确定类标号，即指派到前文所述具有较多数记录的类
stopping_cond()通过检查所有记录是否都属于一个类，或者都具有相同的属性值，来决策是否终止决策树增长。另一种策略是，设置记录数是否小于某个最小阈值
决策树建立后可以进行树剪枝，以减小决策树规模，后文将提到规模过大时会出现过分拟合现象

4.3.7 决策树归纳特点

无先验假设，无概率分布
NP完全问题（还未被证明是否存在多项式算法能够解决这些问题）
样本在决策树建立后分类最大复杂度 $O(\omega)$ ,其中 $\omega$ 为决策树深度
难以处理的情况：布尔函数，布尔属性 $d$ 则需要 $2^d$ 个结点的完全决策树
对于噪声干扰鲁棒性强
冗余属性影响较小，过多时需要在预处理阶段删除不相关属性
分类多次后，记录过小导致数据碎片
子树重复问题
决策边界：两个不同类的相邻区域间的边界（若测试条件只涉及单个属性则为直线）斜决策树即允许测试条件涉及多个属性

4.4 模型的过分拟合

训练误差（或称再代入误差、表现误差）：训练记录上误分样本比例

泛化误差（或称检验误差）模型在未知记录上的期望误差

模型拟合不足 决策树太小时，训练和检验误差都很大

模型过分拟合 随着决策树结点的增加，训练检验误差都会先减小。但一旦结点数过多时，训练误差还可以继续降低但检验误差会增大。原因有类似于结点数适中时对于噪声的容忍度

4.4.2&3 噪声&缺乏代表性样本导致的过分拟合

4.4.3 过分拟合与多重比较过程

问题：单纯最大化给定的标准 $\gamma_{max}$ ，在样本过大时无法保证选取到的真的是有代表性的数据(抛硬币10次8正，重复50次出现概率约 $94\%$ )，此即多重比较过程的问题

我们在候选集 ${x_1,x_2,x_3...,x_k}$ 中选取 $x_{max}$ ,算出增益实际上是 $\Delta(T_0,T_{max})>\alpha$ ，其中 $\alpha$ 是事先设定的阈值，故实践可算作多重比较过程。故随着候选属性个数增加时，最好根据 $k$ 修改增益函数 $\Delta$ 或者增益函数 $\alpha$

尤其是训练记录少时， $\Delta(T_0,T_{max})$ 的方差大，大量的候选属性与少量的训练记录导致了最终的过分拟合

4.4.4 泛化误差估计

再代入误差估计

使用训练数据集最低误差，通常情况性能较差

结合模型复杂度

奥卡姆剃刀

给定两个具有相同泛化误差的模型，较简单的模型比复杂的模型更可取

悲观误差评估

符号： $n(t)$ 是结点 $t$ 分类的训练记录数， $e(t)$ 是被误分类的记录数，悲观误差估计如下, $N(t)$ 是训练数， $k$ 为叶子结点数， $\Omega_i$ 为每个结点对应的罚项

$e_g(T)=\frac{\sum_{i=1}^{k}[e(t_i)+\Omega(t_i))]}{\sum_{i=1}^{k}n(t_i)}=\frac{e(T)+\Omega(T)}{N(T)}$

注：该项越小越好

最小描述长度原则（MDL）

$Cost(model,data)=Cost(model)+Cost(data|model)$ ,模型开销为传输信息开销与误分类记录编码开销之和

举例：见书P125.T9

估计统计上界（见4.6.1置信区间估计法）

使用确认集

将训练集分为用于训练和确认的两个子集，调整参数使得确认集上的泛化误差最小

4.4.5 处理决策树归纳中的过分拟合

先剪枝（提前终止规则）

后剪枝：自底向上修剪完全增长的决策树，有用新结点替换旧子树、最常用叶结点代替旧子树两种做法

子树提升：多重判断合并在一个结点

子树替换：子树大多出现的分类结果直接替换其根结点

4.5 评估分类器性能

保持方法

训练集中再抽出检验集，在检验集上验证模型性能

随机二次抽样

通过多次重复保持方法改进对分类器的性能估计，设 $acc_i$ 是第 $i$ 次迭代的模型准确率，则总准确率为 $acc_{sub}=\sum_{i=1}^{k}\frac{acc_i}{k}$

交叉验证

采用随机二次抽样的思路，但每个数据集用于训练次数相同且只检验一次。

二折交叉验证：数据集对半分，一个当作训练集，一个当作检验集，然后交换角色

$k$ 折交叉验证：数据等分 $k$ 份，每份数据各用作一次检验，共进行 $k$ 次运行

留一：每次的验证集只有一个数据记录

自助法

与前述所有方法不同，采用放回抽样的思路，即已经训练过的记录放回原来的数据集中。每个记录被抽取的概率为

$1-(\frac{1}{N})^{N}$ ，在 $N$ 充分大时极限为 $1-e^{-1}=0.632$

没有抽中的数据用作检验集，这样一次得到自主样本准确率的一个估计 $\epsilon_i$ ，重复以上过程 $b$ 次得到 $b$ 个自助样本

总准确率：.632分类器方法

符号：自助样本共 $b$ 个，每个自助样本的准确率 $\epsilon_i$ ，总训练集准确率 $acc_s$ ，目标值总准确率 $acc_{boot}$

$acc_{boot}=\frac{1}{b}\sum_{i=1}^{b}0.632\times\epsilon_i+0.368\times acc_s$

4.6 比较分类器的方法

4.6.1 估计准确置信区间

预测检验记录类标号的任务可以看做是二项式实验

检验集记录数共 $N$ ,模型正确预测记录数为 $X$ ,设 $p$ 是模型真正准确率，则 $acc$ 置信区间：

$P(-Z_{\frac{\alpha}{2}}\le\frac{acc-p}{\sqrt{\frac{p(1-p)}{N}}}\le Z_{\frac{\alpha}{2}})=1-\alpha$ ( $U$ 检验)

则 $P$ 置信区间为： $\frac{2\times N \times acc + Z_{\frac{\alpha}{2}}^2\pm Z_{\frac{\alpha}{2}}\sqrt{Z_{\frac{\alpha}{2}}^2+4N \times acc-4N \times acc^2}}{2(N+Z_{\frac{\alpha}{2}}^2)}$

4.6.2 比较两模型性能

考虑两模型 $M_1、M_2$ 在独立检验集 $D_1、D_2$ 上进行评估，记录数分别为 $n_1、n_2$ ,设 $M_1$ 在 $D_1$ 、 $M_2$ 在 $D_2$ 上的错误率分别为 $e_1、e_2$ ，我们要检验： $e_1、e_2$ 的观察差是否显著

若 $n_1、n_2$ 充分大，采取正态近似 $e_1、e_2$ ，错误率的观测差： $d=e_1-e_2$

且 $d\sim N(d_t,\sigma_d^2)$ , $\sigma_d^2=\frac{e_1(1-e_1)}{n_1}+\frac{e_2(1-e_2)}{n_2}$

加法式两项分别为错误率方差，可证明：

在置信水平 $(1-\alpha)\%$ 下， $d_t$ 置信区间如下：

$d_t=d\pm z_{\frac{\alpha}{2}}\sigma_d$

（注：太菜了没看4.6.3）

5 分类：其它技术

5.1 基于规则的分类器

采用一组if...then的模式进行分类，模型的规则用析取范式 $R=(r_1\vee r_2 \vee r_3... \vee r_k)$ 表示，其中 $R$ 称为规则集， $r_i$ 是析取项或分类规则

$r_i:(条件_i) \to y_i$

左边是规则前件或称为前提，右边称作规则后件

$r$ 覆盖 $x$ ：规则 $r$ 的前件与记录 $x$ 的属性相匹配，称作 $r$ 覆盖 $x$

$r$ 覆盖给定的记录时，称 $r$ 被激发或触发

衡量分类规则质量：覆盖率、准确率

给定数据集 $D$ 、分类规则 $r:A\to y$ ，覆盖率：

$Coverage(r)=\frac{|A|}{|D|}$ 其中 $A$ 是满足规则前件的记录数

准确率置信因子定义为触发 $r$ 的记录中类标号等于 $y$ 的记录所占的比例

$Accuracy(r)=\frac{|A\cap y|}{|A|}$ 其中分子为同时满足规则前件后件的记录数

5.1.1 基于规则分类器的工作原理

互斥规则

规则集 $R$ 中不存在两条规则能被同一条记录触发，则称规则集 $R$ 中的规则是互斥的

穷举规则

对于任意一条规则， $R$ 中都存在一条规则将其覆盖

若不满足互斥规则，则有几种方法可以解决问题：

有序规则

规则按照一定顺序，以优先级排列，有序的规则集也叫决策表

无序规则

一条记录可触发多条规则，采用加权“投票”形式确定分类

以下讨论有序规则的基于规则的分类器

5.1.2 规则的排序方案

基于规则的排序方案

依据规则的某种质量度量方案对规则进行排序

基于类的排序方案

属于同一个类的规则在规则集 $R$ 中一起出现，并根据所属的类信息一起排序

5.1.3 如何建立基于规则的分类器

直接方法

直接从数据中提取分类规则，将属性空间分为较小子空间

间接方法

从其他分类模型（诸如决策树、神经网络）中提取分类规则；主要用于为较复杂模型提供简洁描述

5.1.4 规则提取的直接方法

顺序覆盖算法

def sca():  # sequential covering algorithm
    #  E为训练记录，A为属性-值对字典，Y为类的有序列表，下标从0到k,R为规则列表，初始为空
    for i in range(len(Y) - 1):
        while True:
            r = learn_one_rule(E, A, y_i)   # 针对y_i类提取一个规则
            E = del_r(r)                    # 删除r对应的训练记录
            R.append(r)                     # 新规则添加到规则集尾部
            judge_end(y_i)                  # 判断是否满足终止条件
    r = rule(None, Y[-1])                   # 添加由空集推出yk的规则 
    R.append(r)

learn_one_rule()函数

目标：提取分类规则以覆盖规则集中大量正例，少量反例

算法：爆搜复杂度指数级，因此采取贪心方式，先产生规则 $r$ ，再不断求精直至满足某种条件

规则增长策略

分类：从特殊到一般、从一般到特殊

从一般到特殊策略 初始： $\{\}\to y$ ,依次查找所有可能规则，选择最优加入规则的合取项，贪心至满足一定条件止。

从特殊到一般策略 初始：随机选取一个正例作为初始种子，每次贪心删除一个合取项至一定条件止，泛化规则。

束状搜索：避免单次贪心产生的次优规则，算法维护各自独立的 $k$ 个候选规则。

规则评估

需要满足：正确率+覆盖率的要求；方法：似然比、 $Laplace$ 度量、 $m$ 估计等等

似然比

$R=2\sum_{i=1}^kf_ilog(\frac{f_i}{e_i})$

$k$ 是类的个数， $f_i$ 是被规则覆盖的类 $i$ 的样本的观测频率， $e_i$ 是做随机猜测的期望频率

$R\sim\chi^2(k-1)$ （注：不知道为什么摆烂）

Laplace度量和m估计

$Laplace=\frac{f_++1}{n+k}$

$m估计=\frac{f_++kp_+}{n+k}$

$n$ 是规则覆盖的样例数， $f_+$ 是规则覆盖的正例数， $k$ 为类的总数， $p_+$ 是正类的先验概率

FOIL信息增益

假设规则 $r：A\to p_0个正例、n_0个反例 r':A\wedge B\to p_1个正例、n_1个反例$

有： $FOIL$ 信息增益 $=\space p_1\times (log_2\frac{p_1}{p_1+n_1}-log_2\frac{p_0}{p_0+n_0})$

规则剪枝

综合4.4节中估计泛化误差的公式来确认是否需要剪枝

顺序覆盖基本原理

在产生一条规则后，必须删除其覆盖的所有正例与反例，否则会对与其有交集的规则的准确率有影响（分别会使结果低估/高估）

RIPPER算法

首先将训练集切分一部分作为确认集

先对类按照频率进行排列，设排序后为 $(y_1,y_2...y_k)$ ,其中 $y_1$ 为最不频繁的类

迭代从以 $y_1$ 样例为正例、其他类反例开始，通过顺序覆盖算法产生区分正反例的规则；再提取区分 $y_2$ 与其他类的规则

直至剩余 $y_k$ 类，作为默认类

规则增长

从一般到特殊的策略进行规则增长，并通过 $FOIL$ 信息增益选取最佳合取项添加至规则前件中。

开始覆盖反例时，停止添加合取项。

根据在确认集的性能进行剪枝： $\frac{p-n}{p+n}$ ， $p、n$ 分别为规则覆盖的确认集中的正反例数目，从后向前遍历合取项，剪枝后若此值增加则去掉此合取项

建立规则集

终止条件：最小描述长度原则 例如新规则将总规则集描述长度提升了 $d$ 个比特位，则停止加入规则集合；另一个终止条件是确认集上的错误率不超过 $50\%$

5.1.5 规则提取的间接方法

以C4.5算法为例：

从决策树生成规则集的方法：从根结点到叶子结点的每一条路径代表一条规则，考虑去掉某个合取项后的化简规则，只要误差率低于原规则就保留，重复以上规则直至悲观误差率不能再次改进

规则排序 预测同一个类的规则合并到一个子集，为每个类计算描述长度，最后按照每个类总的描述长度由小到大排序，小的类优先。

每个类的总描述长度为： $L_{exception}+g\times L_{model}$ 其中， $L_{exception}$ 为给误分类样例编码所需要的位数， $L_{model}$ 为给模型编码所需要的位数， $g$ 是调节参数，默认为 $0.5$ ；模型冗余属性越多， $g$ 的值越小

5.1.6 基于规则分类器的特征

表达能力约等于决策树
产生的模型往往更易于解释
基于类的规则的定序方法非常适合处理类不平衡的数据集

5.2 最邻近分类器

5.2.1 算法概述

积极学习方法：归纳模型、建立模型

消极学习方法：推迟所需要的建模，直到需要分类测试样例时再进行

Rote分类器：记住训练数据，只对属性完全匹配的情况进行分类

最近邻：找出和测试样例的属性相接近的所有训练样例

分类基本思路：设有 $d$ 个属性，将每个样例看作 $d$ 维空间的数据点，给定一个测试样例，寻找最近的点

k-最近邻：寻找和样例点距离最近的 $k$ 个点。 $k$ 太小，噪声会造成过拟合； $k$ 太大，容易误分类测试样例

def kmiuns():  # 设k为最近邻数目，D为训练样例的列表,测试样例为z=(x,y),其中x为向量
    for e in D: # e为测试样例即e=(x',y')
        records = cal_min_distance(e)       # 计算e与其它所有样例的距离
        record = choose_record(records, k)  # 选择最近的k个集合
        e.res = choos_type(record)          # 选择最近列表中的多数类作为结果（也可使用加权等）

5.2.2 最近邻分类器特征

基于实例的学习
基于局部信息进行学习，且 $k$ 小时对噪声敏感
决策边界具有可变性
需要适当的邻近性度量和数据预处理，否则可能做出错误的预测

5.3 贝叶斯分类器

贝叶斯公式

$P(Y|X) = \frac{P(Y)P(X|Y)}{P(X)} = \frac{P(Y)P(X|Y)}{P(X|Y)P(Y) + P(X|\bar Y)P(\bar Y)}$

5.3.2 贝叶斯定理在分类中的应用

设 $X$ 表示属性集， $Y$ 表示类变量；则 $P(Y)$ 称为 $Y$ 的先验概率； $P(Y|X)$ 称为 $Y$ 的后验概率

通过找出使 $P(Y|X)$ 最大的类 $Y$ ，从而进行分类工作

而由贝叶斯定理，有上方的公式可以计算后验概率，选定一个属性集，则 $P(X)$ 固定，而 $P(Y)$ 可从全部的样例中轻易计算，故核心问题为如何获得 $P(X|Y)$ ,以下有两种方式估算此值，分别为朴素的贝叶斯分类器及贝叶斯信念网络

5.3.3 朴素贝叶斯分类器

前提：假设各个属性间相互独立,条件独立假设

对每个类计算后验概率：

$P(Y|\vec X)=\frac{P(Y)\prod_{i=1}^dP(X_i|Y)}{P(\vec X)}$

而对所有的 $Y$ , $P(\vec X)$ 固定，故只需要找出分子乘积最大的类即可

则对 $P(X_i|Y)$ :

若为离散属性，直接采取样本估计总体的古典方法即可

若为连续属性，可以强行离散化（注意离散化的区间），也可以假设其服从某种分布再进行估计

  常用的假设为**高斯(正态)分布**，则采用样本均值、方差估计总体均值、方差，直接利用概率密度函数(的积分)计算概率：

$P(X_i=x_i|Y_j=y_j)=\frac{1}{\sqrt{2}\pi\sigma_{ij}}e^-{\frac{(x_i-\mu_{ij})^2}{2\times \sigma_{ij}^2}}$

m估计

在训练样例过少时，为解决类似于一个属性的类条件概率为0则总体概率为0的问题，提出 $m$ 估计以优化直接采用条件概率的策略

$P(X_i=x_i|Y_j=y_j)=\frac{n_c+mp}{n+m}$

$n$ 是类 $y_j$ 中的实例总数， $n_c$ 为类 $y_j$ 训练样例中取值 $x_i$ 的样例数， $m$ 称为等价样本大小参数， $p$ 是用户指定的参数。

分类器特征

面对孤立噪声点、无关属性较为健壮
相关属性由于不是完全互相独立的，分类器性能会略微降低

5.3.4 贝叶斯误差率

理想决策边界：若知道支配 $P(X|Y)$ 的真实分布，根据先验概率关系，可计算理想决策边界。分类器的误差率可根据后验概率曲线结合理想决策边界计算

5.3.5 贝叶斯信念网络(BBN)

允许指定部分属性独立从而建模的分类问题，提供一种更灵活的 $P(\vec X|Y)$ 的建模方法。

模型表示

用图模型表示一组变量间的概率关系：其主要成分有一个有向无环图，表示变量间的依赖关系；一个概率表，表示各节点和父节点的关联关系

表示关系：一个节点，若父节点已知，则条件独立于所有非后代节点

节点性质：每个节点关联于一个概率表，若 $X$ 无父母节点，则表中只有先验概率 $P(X)$ ;若有父节点 $\{Y_1,Y_2...Y_k\}$ ,则概率表中有条件概率 $P(X|Y_1,Y_2...Y_k)$

算法步骤

(1) 创建网络结构

(2) 估计每一个节点的概率表概率值

def gen_bayes(T):                           # 设T为k个变量的集合,下标越大，次序越低
    for i in range(k):                      # 按照优先级顺序遍历变量
        for j in range(i + 1, k)：           # 遍历剩余变量，计算相关性
            corr = cal_corr(T[i], T[j])     # 返回相关变量
            for T_re in corr:               # 相关变量与筛选变量间添加边
                add_edge(T[i], T_re)

模型特点

可以由图形模型来捕获特定领域的先验知识的方法
网络结构确定后易于添加新变量
很适合处理不完整的数据
很适合处理模型的过分拟合问题

5.4 人工神经网络(ANN)

5.4.1 感知器

包含结构：几个输入结点，表示输入属性；一个输出结点，表示模型输出。

每个输入结点都通过一个加权的链连接到输出结点。用来拟合神经元间神经键的连接强度。最终训练目的：不断调整链的权值，直到拟合训练数据的输入输出关系为止。

输出的决定式：输入加权求和（权值为可调参数），减去偏执因子 $t$ （参数），得到输出值 $y$ 。具体地：
$\hat y = sign(\sum_{i=1}^{d}w_ix_i-t)$

称作输出神经元的激活函数，更多地，可简写为 $\hat y=(\vec x \cdot \vec x)$ (视 $t=w_0t_0$ )

感知学习算法

随机化初始权值，遍历每个训练样例，计算预测输出 $\hat y$ ，并利用权值更新公式计算更新的权值。
$w_j^{(k+1)}=w_j^{(k)}+\lambda(y_i-\hat{y_i}^{(k)})$
其中 $\lambda$ 是一个 $[0, 1]$ 之间的数字，越靠近 $1$ ，代表受到新值的影响越大。可以使用逐渐减小的 $\lambda$ 值。

问题:只能构造一个超平面，无法对异或（XOR）等复杂问题进行建模

5.4.2 多层人工神经网络

隐藏层：输入层和输出层之间的中间层，内部包含若干隐藏结点。前馈神经网络中，每一层的结点仅和下一层的结点相连。感知器即为一个单层前馈神经网络。在递归神经网络中，允许同一层结点相连或一层的结点连接到前面各层的结点。
复杂激活函数：除了符号函数外，可以使用线性、S型（逻辑斯蒂函数）、双曲正切函数等等

为解决多个超平面的问题等，介绍基于梯度下降的神经网络权值学习方法

学习ANN模型

目的：确定一组权值 $w$ ，最小化误差平方和

选择激活函数后，如何近似寻找 $w$ 的全局最优解：例如采取基于梯度下降的贪心算法的权值更新公式：。
$w_j \leftarrow w_j - \lambda \frac{\partial E(\vec w)}{\partial w_j}$
此式可以渐进地使权值向着总体误差方向减小的方向移动。但若要避免陷入局部最小值，可以采取类似于反向传播的技术：

每次迭代分为两个阶段：前向阶段、后向阶段。

前向阶段：使用前一次迭代的权值计算每个神经元的输出值，即计算是向前进行的。
后向阶段：反向更新权值，先更新后一层的再更新前一层的。

ANN学习中的设计问题

依次考虑以下问题：

确定输入层的结点数目。每一个数值输入，二元输入变量对应一个节点。如果输入变量是分类变量，则可以为每一个分类值创造一个结点。也可以用 $log_2k$ 个编码表示分类值。
确定输出层结点数目。对于二分类问题，一个输出结点即可， $k-$ 类问题则需要 $k$ 个输出结点。
选择网络拓扑结构。例如隐藏层、隐藏结点数，前馈还是递归网络结构。一种方法是采取足够多结点和隐藏层的全连接网络，然后用较少的结点重复该建模过程；另一种是不重复建模过程，而是删除一些结点，然后重复模型评价过程。
初始化权值、偏置。通常可以随机赋值。
去掉有遗漏值的训练样例。

5.5 支持向量机(SVM)

5.5.1 最大边缘超平面

5.6 组合方法

5.7 不平衡类问题

5.8 多类问题

6 关联分析：基本概念和算法

6.1 问题定义

6.2 频繁项集的产生

6.3 规则产生

6.4 频繁项集的紧凑表示

6.5 产生频繁项集的其他方法

6.6 FP增长算法

6.7 关联模式的评估

7 关联分析：高级概念

7.1 处理分类属性

7.2 处理连续属性

7.3 处理概念分层

7.4 序列模式

7.5 子图模式

7.6 非频繁模式

8 聚类分析：基本概念和算法

8.1 概述

8.2 K均值

8.3 凝聚层次聚类

8.4 DBSCAN

8.5 簇评估

9 聚类问题：其他问题与算法

9.1 数据、簇和聚类算法的特性

9.2 基于原型的聚类

9.3 基于密度的聚类

9.4 基于图的聚类

9.5 可伸缩的聚类算法

9.6 使用哪种聚类算法

10 异常检测

10.1 预备知识

10.2 统计方法

10.3 基于邻近度的离群点检测

10.4 基于密度的临近点检测

10.5 基于聚类的技术

最后编辑于：2022.10.13 17:21:36

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,122评论 6赞 505
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,070评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,491评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,636评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,676评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,541评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,292评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,211评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,655评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,846评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,965评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,684评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,295评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,894评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,012评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,126评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,914评论 2赞 355

BUAA数据挖掘导论（教材）笔记

BUAA数据挖掘导论（教材）笔记

1 绪论

1.4 数据挖掘任务

2 数据

2.1 数据类型

2.1.1 属性和度量

2.1.2 数据集类型

2.2 数据质量

2.2.1测量和数据收集问题

2.2.2 关于应用的问题

2.3 数据预处理

2.3.1 聚集

2.3.2抽样

2.3.3 维归约

2.3.4特征子集选择

2.3.5 特征创建

2.3.6 离散化和二元化

2.3.7 变量变换

※※※2.4 相似性及相异性度量

2.4.1 基础概念

2.4.2 简单属性之间的相似度和相异度

2.4.3 数据之间的相异度

2.4.4 数据对象之间的相似度

※※※2.4.5 邻近性度量的例子

二元数据的相似性度量

简单匹配系数（SMC）

Jaccard系数

余弦相似度

广义Jaccard系数(Tanimoto系数)

相关性（Corr）

Bregman散度

2.4.6 邻近度计算问题

距离度量的标准化和相关性

组合异种属性的相似度

3 探索数据

3.2 汇总统计

3.2.1 频率和众数

3.2.2 百分位数

3.2.3 位置度量：均值和中位数

3.2.4 散布度量：极差和方差

绝对平均偏差AAD

中位数绝对偏差MAD

四分位数极差IQR

3.2.5 多元汇总统计

协方差矩阵

相关矩阵

3.4 OLAP和多元数据分析

3.4.3 分析多维数据

3.5 补充：主成分分析 PCA

4 分类：基本概念、决策树与模型评估

4.1 预备知识

4.2 解决分类问题的一般方法

4.3 决策树归纳

4.3.1 决策树的工作原理

4.3.2 如何建立决策树（Hunt算法）

4.3.3 表示属性测试条件的方法

4.3.4 选择最佳划分的度量

4.3.5 决策树归纳算法

4.3.7 决策树归纳特点

4.4 模型的过分拟合

4.4.2&3 噪声&缺乏代表性样本导致的过分拟合

4.4.3 过分拟合与多重比较过程

4.4.4 泛化误差估计

再代入误差估计

结合模型复杂度

最小描述长度原则（MDL）

估计统计上界（见4.6.1置信区间估计法）

使用确认集

4.4.5 处理决策树归纳中的过分拟合

4.5 评估分类器性能

4.6 比较分类器的方法

4.6.1 估计准确置信区间

4.6.2 比较两模型性能

5 分类：其它技术

5.1 基于规则的分类器

5.1.1 基于规则分类器的工作原理

5.1.2 规则的排序方案

5.1.3 如何建立基于规则的分类器

5.1.4 规则提取的直接方法

协方差矩阵 $S$

相关矩阵 $R$