本文简单记录了数据挖掘的基本概念和基础算法，主要起记录作用。

一、概念问题

（一）数据挖掘

它是数据库知识发现（Knowledge-Discovery in Databases KDD）中的一个步骤。

数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。

数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、机器学习、专家系统（依靠过去的经验法则）和模式识别等诸多方法来实现上述目标。

（二）机器学习

机器学习这门学科所关注的问题是：计算机程序如何随着经验积累，自动提高性能。——Tom Mitchell

（三）有监督学习

（四）无监督学习

聚类就是无监督学习。

聚类是一种发现数据集之中的内在结构的技术，聚类是一个将数据集中某些方面相似的数据成员进行分类组织的过程。

（五）分类

分类是数据挖掘中的一种主要分析手段，分类的任务是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号。

（六）回归

回归是Frances Galton提出的一种统计方法。回归分析可以对预测变量和响应变量之间的联系建模。

在数据挖掘环境下：

预测变量是描述样本的感兴趣的属性，一般，预测变量的值是已知的，响应变量是我们要预测的那个。

---

分类和回归都有预测的功能，但是：

• 分类预测的输出为离散或标称的属性；

• 回归预测的输出为连续属性值；

（七）关联规则、序列模式

• 关联规则

关联规则是形如X→Y的蕴涵式，其中， X和Y分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。其中，关联规则XY，存在支持度和信任度。

• 序列模式

假定有一个数据集D，它含有n个序列Sequence，Sequence由多个事件组成，Sequence中的多个事件是时间有序的。可以认为事件号（eventid）更大的事件在eventid小的事件之后发生。

如果有一个序列S，它是数据集D的序列的子序列，那么它的支持度的计算方式为：

support(s) = s在n个序列中出现的次数

如果spport(s)>min_support，则我们可以把它称为频繁序列，或者序列模式。

（八）关联规则的支持度、序列模式的支持度

• 关联规则的支持度

关联规则在D中的支持度(support)是D中事务同时包含X、Y的百分比，即概率；

• 序列模式的支持度

序列s的支持度指包含s的所有数据序列（与单个数据对象（上例中的A/B/C）相关联的事件的有序列表）所占的比例

（九）关联规则的置信度

置信度(confidence)是D中事务已经包含X的情况下，包含Y的百分比，即条件概率。

（十）分类器的准确率

$$Accucacy = \frac{TP+TN}{TP+TN+FP+FN}​$$

（十一）分类器的精确率

$$Precision = \frac{TP}{TP+FP}$$

（十二）分类器的召回率

$$Recall = \frac{TP}{TP+FN}$$

---

Precision和Recall的区别：

实际上非常简单，精确率是针对我们预测结果而言的，它表示的是预测为正的样本中有多少是真正的正样本。那么预测为正就有两种可能了，一种就是把正类预测为正类(TP)，另一种就是把负类预测为正类(FP)，也就是

$$P=\frac{T P}{T P+F P}$$
而召回率是针对我们原来的样本而言的，它表示的是样本中的正例有多少被预测正确了。那也有两种可能，一种是把原来的正类预测成正类(TP)，另一种就是把原来的正类预测为负类(FN)。

$$R=\frac{T P}{T P+F N}$$

在信息检索领域，精确率和召回率又被称为查准率和查全率，

查准率＝检索出的相关信息量 / 检索出的信息总量

查全率＝检索出的相关信息量 / 系统中的相关信息总量

（十三）过拟合、欠拟合

• 过拟合

当模型把训练样本自身的一些特点。当做所有潜在样本的共同性质时，学习器的泛化性能下降。这种现象被称为过拟合。

• 欠拟合

当模型没有捕捉、学习到训练样本的一般性质、特征时，不能很好地拟合数据。这种现象被称为欠拟合。

（十四）n折交叉验证

n折交叉验证（n-fold cross validation）。

在机器学习中，将数据集A分为训练集B（training set）和测试集C（test set），在样本量不充足的情况下，为了充分利用数据集对模型进行测试，把样本集S分成n份，分别使用其中的(n-1)份作为训练集，剩下的1份作为交叉验证集。取n次结果的平均误差，来评估这个模型。

（十五）集成学习

• 同质的集成
  • 基学习器
• 异质的集成
  • 组件学习器

（十六）离群点

nHawkins的定义：离群点是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。

nWeisberg的定义：离群点是与数据集中其余部分不服从相同统计模型的数据。

nSamuels的定义：离群点是足够地不同于数据集中其余部分的数据。

nPorkess的定义：离群点是远离数据集中其余部分的数据

二、原理性问题

（一）数据预处理的任务（数据清洗、数据转换、……）、目的，数据缺失的原因

a、数据预处理任务

• 数据清理

填写空缺数据，平滑噪声数据，识别、删除孤立点，解决不一致性

• 数据集成

集成多个数据库，数据立方体或文件

• 数据变换

规范化和特征构造

• 数据归约

得到数据集的压缩表示及特征选择

• 数据离散化

通过概念分层和数据离散化来规约数据，对数值数据特别重要

b、数据预处理目的

数据挖掘的目的是在大量的、潜在有用的数据中挖掘出有用的模式或信息，挖掘的效果直接受到源数据质量的影响。

高质量的数据是进行有效挖掘的前提，高质量的决定必须建立在高质量的数据上。

c、数据缺失原因

• 引起空缺值的原因
  • 设备异常
  • 与其它已有数据不一致而被删除
  • 因为误解而没有被输入的数据
  • 在输入数据时，有些数据认为得不到重视而没有被输入
  • 对数据的改变没有进行日志记载

（二）数据清洗的任务（噪声过滤、缺失值处理、…）、目的和方法

a、任务

• 填补缺失值
• 光滑噪声数据
• 平滑或删除离群点
• 解决数据的不一致性

b目的

• 现实世界的数据是“肮脏的”

  • 不完整的：有感兴趣的属性缺少属性值（缺失值）
  • 含噪声的：包含错误的或是“孤立点”（噪声数据、离群点）
  • 不一致的：在命名或是编码上存在差异（不一致性）

• 意义：

  • 数据清理的目的就是试图填充缺失值、去除噪声并识别离群点、纠正数据中的不一致值。

c、方法

• 缺失值处理

  • 忽略元组：当缺少类标号时通常这样处理(在分类任务中)。除非同一记录中有多个属性缺失值，否则该方法不是很有效。
  • 忽略属性列：如果该属性的缺失值太多，如超过80%，则在整个数据集中忽略该属性。
  • 人工填写缺失值：通常情况下，该方法费时费力，并且当数据集很大或缺少很多值时，该方法可能行不通。
  • 自动填充缺失值
    • 策略一：使用一个全局常量填充缺失值，将缺失的属性值用同一个常数替换。
    • 策略二：使用与给定记录属同一类的所有样本的均值或众数填充缺省值。
    • 策略三：用可能值来代替缺失值：可以用回归、基于推理的工具或决策树归纳确定。

• 噪声数据处理

  • 分箱：分箱方法通过考察“邻居”(即周围的值)来平滑有序数据的值。
  • 聚类：聚类将类似的值组织成群或“簇”。
  • 回归：让数据适合一个函数来平滑数据。
• 离群点检测
  • 简单统计分析：根据箱线图、各分位点判断是否存在异常，例如pandas的describe函数可以快速发现异常值。
  • 3 $\sigma$ 原则：若数据存在正态分布，偏离均值的3 $\sigma$之外. 通常定义 $P(|x-\mu|>3 \sigma)<=0.003$ 范围内的点为离群点。
  • 基于绝对离差中位数（MAD）：这是一种稳健对抗离群数据的距离值方法，采用计算各观测值与平均值的距离总和的方法。放大了离群值的影响。
  • 基于距离：通过定义对象之间的临近性度量，根据距离判断异常对象是否远离其他对象，缺点是计算复杂度较高，不适用于大数据集和存在不同密度区域的数据集
  • 基于密度：离群点的局部密度显著低于大部分近邻点，适用于非均匀的数据集
  • 基于聚类：利用聚类算法，丢弃远离其他簇的小簇。

（三）数据转换的任务（离散化、数据规约（抽样、属性选择）、……）、目的和方法

a、数据规约

从记录和维度两个方面减少数据量

• 维度规约：维度(数据特征的数目)归约是指通过使用数据编码或变换，得到原始数据的归约或“压缩”表示。

  • 如果维度较低，许多数据挖掘算法效果会更好。
  • 维归约使模型涉及更少的特征，因而可以产生更容易理解的模型。
  • 使用维归约可以降低数据挖掘算法的时间和空间复杂度。

• 抽样：用数据较小的随机样本表示大的数据集

  • 有效抽样原理
    • 如果样本是有代表性的，则使用样本与使用整个数据集的效果几乎一样
    • 如果数据对象的均值是感兴趣的性质，而样本具有近似于原数据集的均值，则样本是有代表性的
    • 抽样是一个统计过程，特定样本的代表性是变化的
  • 简单随机抽样
    • 无放回抽样
      • 随着每个项被抽出，它被从构成总体的所有对象集中删除
    • 有放回的抽样
      • 对象被选中时不从总体中删除
    • 分层抽样
      • 特点
        • 总体由不同类别的对象组成
        • 每种类型的对象数量差别很大
      • 先对数据集进行分组：数据集D被划分为互不相交的“层”，则可通过对每一层按一定比例简单随机选样得到D的分层选样
      • 利用聚类实现分层抽样：将数据集D划分成m个不相交的簇，再在聚类结果的簇上进行简单随机抽样

• 特征选择

  从一组已知特征集合中选择最具代表性的特征子集，使其保留原有数据的大部分信息，即所选特征子集可以像原来的特征全集一样用来正确区分数据集的每个数据对象。通过特征选择，一些和任务无关或是冗余的特征被删除，从而提高数据处理的效率。

  理想的特征子集：每个有价值的非目标特征与目标特征强相关，而非目标特征之间不相关或是弱相关

  • 通过删除不相干的属性或维减少数据量
  • 属性子集选择
    • 找出最小属性集，使得数据类的概率分布尽可能的接近使用所有属性的原分布
    • 减少出现在发现模式上的属性的数目，使得模式更易于理解
  • 启发式（探索式）搜索方法
    • 逐步向前选择
    • 逐步向后删除
    • 向前选择和向后删除相结合
    • 判定归纳树

• 数据压缩

  • 有损压缩
    • 小波变换
    • 主成分分析
  • 无损压缩

b、数据变换

• 平滑：去除数据中的噪声数据
• 聚集：汇总，数据立方体的构建
• 离散化于概念分层
  • 离散化：通过将属性域划分为区间，减少给定连续属性值的个数。区间标号可以代替实际的数据值。
  • 概念分层：通过使用高层的概念（比如：老年，中年，青年）来替代底层的属性值（比如：实际的年龄数据值）来规约数据
• 规范化：将数据按比例缩放，使之落入一个小的特定区间（消除量纲的影响）
  • 最小-最大规范化
  • Z-score规范化
  • 小数定标规范化
• 属性构造：通过现有属性构造新的属性，并添加到数据集中
  • 特征提取(Feature Extraction)：由原始数据创建新的特征集
  • 映射数据到新的空间：从不同视角提示重要和有趣的特征
    • 傅里叶变换(Fourier Transform)
    • 小波变换(Wavelet Transform)
  • 特征构造：由一个或多个原始特征共同构造新的特征

（四）距离或者相似度的度量方法

a、距离（相异度）度量

• 类间距离（欧氏、马氏距离）

  • 欧氏距离

    定义在两个向量（两个点）上：点$x$和点$y$的欧氏距离为：

    $$d_{\text {Euclidean }}=\sqrt{(\mathbf{x}-\mathbf{y})^{\top}(\mathbf{x}-\mathbf{y})}$$

  • 闵可夫斯基距离

    Minkowski distance， 两个向量（点）的$p$阶距离：

    $$d_{\text {Minkowski}}=\left(|\mathbf{x}-\mathbf{y}|^{p}\right)^{1 / p}$$

  • 曼哈顿距离

    当$p=1$时就是曼哈顿距离，

  • 切比雪夫距离

    当$p=\infin$时就是欧氏距离。

  • 马氏距离

    定义在两个向量（两个点）上，这两个点在同一个分布里。点$x$和点$y$的马氏距离为：

    $$d_{\text {Mahalanobis}}=\sqrt{(\mathbf{x}-\mathbf{y})^{\top} \Sigma^{-1}(\mathbf{x}-\mathbf{y})}$$
    其中，$\Sigma$是这个分布的协方差。

    当时，马氏距离退化为欧氏距离。

b、相似度度量

• 连续属性的相关度计算

  • 线性相关系数

$$r=\frac{\sum{i}\left(x{i}-\overline{x{i}}\right)\left(y{i}-\overline{y{i}}\right)}{\sqrt{\sum{i}\left(x{i}-\overline{x{i}}\right)^{2}} \sqrt{\sum{i}\left(y{i}-\overline{y_{i}}\right)^{2}}}$$

• 余弦相似度

• 离散属性的相关度计算

  • 信息增益
    • $I G(X | Y)=H(X)-H(X | Y)$
    • 其中，x的信息熵$H(X)=-\sum_{i} P\left(x_{i}\right) \log {2}\left(P\left(x{i}\right)\right)$；已知y后x的条件信息熵$H(X | Y)=-\sum_{j} P\left(y_{j}\right) \sum_{i} P\left(x_{i} | y_{j}\right) \log {2}\left(P\left(x{i} | y_{j}\right)\right)$
  • 互信息
    • $S U(X, Y)=2\left[\frac{I G(X | Y)}{H(X)+H(Y)}\right]$

• 二值属性的相关度计算

  • 简单匹配系数(Simple Matching Coefficient,SMC)

    • SMC = 值匹配的属性个数 /属性个数 = (M11 + M00) / (M01 + M10 + M11 + M00)

（五）决策树算法的基本思想，需要剪枝的原因，剪枝的方法

a、基本思想

决策树的构建过程就是不断对训练集进行划分，使得划分后的各个子集尽可能纯。所谓纯的子集，指的是子集内所有数据的类标相同。

不断的划分，遵循了分而治之的思想。

决策树的生成是一个递归的过程。

信息熵就是度量子集纯度的指标。

b、剪枝的原因

在构造决策树的过程中，为了更好地进行划分，往往会造成决策树的分支过多、过深，从而导致过拟合。

为了解决过拟合问题，就对决策树进行剪枝，将决策树的子树或者分支删除。

c、剪枝的方法

预剪枝

在构建决策树的过程正进行评估，评估的方法是留出法、交叉验证法、自检法等等。

后剪枝

在构建决策树之后，对各子节点进行评估，评估的方法是留出法、交叉验证法、自检法等等。

（六）信息增益作为衡量属性分类能力的指标，优点和缺点

a、优点

信息增益使用信息熵，度量了在某个条件下，信息复杂度减少的程度。这种衡量标准能够帮助决策树选择枝干，即更重要的特征。

b、缺点

信息增益对可取值较多的属性有所偏好。信息增益在类别值多的属性上计算结果大于类别值少的属性上计算结果，这将导致决策树算法偏向选择具有较多分枝的属性，因而可能导致过度拟合。在极端的情况下，如果某个属性对于训练集中的每个元组都有唯一的一个值，则认为该属性是最好的，这是因为对于每个划分都只有一个元组(因此也是一类)。

（七）朴素贝叶斯方法的基本思想，朴素性的体现 – 独立性假设

a、基本思想

用概率的视角分析分类任务，分类任务变成了求关于测试样例$d$对于类别$c$的后验概率：已知测试样例$d$，求$d$关于类别$c$的后验概率。哪个类别对应的后验概率大，则将该样例分类为该类别。

$$\begin{array}{c} \operatorname{Pr}\left(C=c_{j} | A_{1}=a_{1}, \cdots, A_{|A|} = a_{|A|}\right) \ =\frac{\operatorname{Pr}\left(A_{1}=a_{1}, \cdots, A_{|A|} a_{|A|} | C=c_{j}\right) \operatorname{Pr}\left(C=c_{j}\right)}{\operatorname{Pr}\left(A_{1}=a_{1}, \cdots, A_{|A|}=a_{|A|}\right)} \end{array}$$
问题变成了，如何求得$\operatorname{Pr}(A_{1}=a_{1}, \cdots, A_{|A|} = a_{|A|} | C=c_{j})$

b朴素性体现

为了计算该概率，提出独立性假设。

独立性假设，即假设所有类别都条件独立于分类结果。

因此，上式就可以变成：

$$\begin{aligned} & \operatorname{Pr}\left(A_{1}=a_{1}, \cdots, A_{|A|}=a_{|A|} | C=c_{j}\right) \ =& \prod_{i=1}^{|A|} \operatorname{Pr}\left(A_{i}=a_{i} | C=c_{j}\right) \end{aligned}$$

（八）基于划分的聚类，基于密度的聚类分别有哪些具体的算法

聚类(Clustering)是将数据集划分为若干相似对象组成的多个组(group)或簇(cluster)的过程，使得同一组中对象间的相似度最大化，不同组中对象间的相似度最小化。

a、基于划分的聚类

基本概念

给定一个 n 个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类，并且k<=n。也就是说，它将数据划分为k个组，同时满足如下的要求：

(1)每个组至少包含一个对象；

(2)每个对象必须属于且只属于一个组。

划分式聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。这类方法分为基于质心的(Centroid-based)划分方法和基于中心的(Medoid-based)划分方法。

算法

• k-means
• 二分k-means
• k-summary
• K-medoids

b、基于密度的聚类

通常将簇看作是数据空间中被低密度区域(代表噪声)分割开的稠密对象区域。

基于密度的方法典型的包括

• DBSCAN (Density-Based Spatial Clustering of Applications with Noise)
• OPTICS(Ordering Points to Identify the Clustering Structure)

（九）不带类标的数据为什么对分类模型的训练会有帮助？

半监督学习

未标签数据与有标签数据都是从同样的数据源独立同分布采样出来的，他们所包含的关于数据分布的信息对于模型学习大有裨益。

（十）什么是PU学习？什么是LU学习？

a、PU学习

模型通过有标签数据和无标签数据学习。在这个学习任务中，数据集包含少量的有标签数据和大量的无标签数据，目的在于利用无标注数据，提高模型的能力。

b、LU学习

在二分类任务中，模型通过正例和无标签数据学习。在这个学习任务中，数据集包含少量的正例数据和大量的无标签数据。目的是，在没有反例的情况下，得到一个精确的二分类器。

（十一）集成学习在什么情况下有效？

个体学习器应该“好而不同”，即不同的个体学习器，不仅要保持一定的准确率，还要保持多样性，学习到的特征各具差异。

三、算法

（一）决策树 – ID3、C4.5 – 分类

a、ID3

ID3算法的核心是在决策树各级结点上选择属性，用信息增益作为属性选择的标准，使得在每个非叶节点进行测试时能获得关于被测数据最大的类别信息，使得该属性将数据集分成子集后，系统的熵值最小。

信息增益：

$$\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)$$
其中：
$$
\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log {2} p{k}
$$

• 优点
  • 理论清晰，方法简单，学习能力较强。
• 缺点
  • (1)算法只能处理分类属性数据，无法处理连续型数据；
  • (2)算法对测试属性的每个取值相应产生一个分支，且划分相应的数据样本集，这样的划分会导致产生许多小的子集。随着子集被划分得越来越小，划分过程将会由于子集规模过小所造成的统计特征不充分而停止；
  • (3)ID3算法中使用信息增益作为决策树节点属性选择的标准，由于信息增益在类别值多的属性上计算结果大于类别值少的属性上计算结果，这将导致决策树算法偏向选择具有较多分枝的属性，因而可能导致过度拟合。在极端的情况下，如果某个属性对于训练集中的每个元组都有唯一的一个值，则认为该属性是最好的，这是因为对于每个划分都只有一个元组(因此也是一类)。

b、C4.5

基于ID3算法中存在的不足，Quinlan提出了改进的决策树分类算法C4.5，该算法继承了ID3算法的优点，并在以下几个方面对ID3算法进行了改进：

• 能够处理连续型属性数据和离散型属性数据；
• 能够处理具有缺失值的数据；
• 使用信息增益率作为决策树的属性选择标准；
• 对生成的树进行剪枝处理，以获取简略的决策树；
• 从决策树到规则的自动产生。

对于连续值的处理

如果属性A为连续型数据，则按属性A的取值递增排序，将每对相邻值的中点看作可能的分裂点，对每个可能的分裂点，计算：
$$
\text {Entropy}{A}(S)=\frac{\left|S{L}\right|}{|S|} \operatorname{Entropy}\left(S_{L}\right)+\frac{\left|S_{R}\right|}{|S|} \operatorname{Entropy}\left(S_{R}\right)
$$
其中$S_L$和$S_R$分别对应于该分裂点划分的左右两部分子集，选择EntropyA(S)值最小的分裂点作为属性A的最佳分裂点，并以该最佳分裂点按属性A对集合S的划分熵值作为属性A划分S的熵值。

信息增益率

将ID3的信息增益改为信息增益率：

$$\begin{array}{l} \text { Gain_ratio }(D, a)=\frac{\operatorname{Gain}(D, a)}{\mathrm{IV}(a)} \ \mathrm{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|} \end{array}$$
虽然属性$a$的取值越多，信息增益越大，但是$IV(a)$同时也在增大，能够约束其信息增益的变化。

• 优点：
  • 产生的分类规则易于理解，准确率较高。
• 缺点：
  • 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序（计算信息增益率时，需要扫描两次），因而导致算法的低效。
  • C4.5只适合于能够驻留与内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

（二）朴素贝叶斯 – 分类

$$c=\underset{\epsilon_{j}}{\operatorname{argmax}} \operatorname{Pr}\left(C=c_{j}\right) \prod_{i=1}^{|A|} \operatorname{Pr}\left(A_{i}=a_{i} | C=c_{j}\right)$$

a、小概率相乘

朴素贝叶斯分类算法在计算概率的时候存在概率为0及概率值可能很小的情况，因此在某些情况下需要考虑条件概率的Laplace估计以及解决小概率相乘溢出问题。

$$P\left(X_{i} | Y_{j}\right)=\frac{n_{c}+l \times p}{n+l}$$
其中$n$是类$Y_j$中的实例总数，$n_c$是类$Y_j$的训练样例中取值为$X_i$的样例数，$l$是称为等价样本大小的参数，而$p$是用户指定的参数。如果没有训练集(即n=0)，则$P(X_i|Y_j)=p$。因此$p$可以看作是在类$Y_j$的记录中观察属性值$X_i$的先验概率。等价样本大小$l$决定先验概率$p$和观测概率$n_c/n$之间的概率。

或者：

$$\begin{aligned} \hat{P}(c) &=\frac{\left|D_{c}\right|+1}{|D|+N} \ \hat{P}\left(x_{i} | c\right) &=\frac{\left|D_{c, x_{i}}\right|+1}{\left|D_{c}\right|+N_{i}} \end{aligned}$$
其中$N$表示$c$可以取的属性种类数目，$N_i$表示$x_i$可以取得属性种类数目。

b、溢出问题

即使每一个乘积因子都不为零，但当$n$较大时也可能几乎为零，此时将难以区分不同类别。

因此使用log计算，使得相乘变成相加：

$$\log P\left(X | C_{i}\right)=\log \left(P\left(C_{i}\right) \prod_{k=1}^{n} P\left(x_{k} | C_{i}\right)\right)=\log P\left(C_{i}\right)+\sum_{k=1}^{n} \log P\left(x_{k} | C_{i}\right)$$

• 优点：
  • 容易实现
  • 在大多数情况下所获得的结果比较好
• 缺点：
  • 算法成立的前提是假设各属性之间互相独立
  • 当数据集满足这种独立性假设时，分类准确度较高
  • 而实际领域中，数据集可能并不完全满足独立性假设

（三）KNN - 分类

• K-最近邻算法的基本思想是：

  • 对于未知类标号的样本，按照欧几里得距离找出它在训练集中的k个最近邻，将未知样本赋予k最近邻中出现次数最多的类别号。

• 优点：

  • 算法思想简单，易于实现。
• 缺点：
  • 最近邻分类对每个属性指定相同的权重。
  • 而数据集中的不同属性可能需要赋予不同的权值；
  • 由于K-NN存放所有的训练样本，直到有新的样本需要分类时才建立分类，因此当训练样本数量很大时，该学习算法的时间复杂度为n2。

（四）前馈神经网络、反向传播算法（BP算法）、交叉熵损耗、均方误差损耗

a、BP算法

• 优点：
  • 理论基础牢固，推导过程严谨，物理概念清晰，通用性好等。所以，它是目前用来训练前向多层网络较好的算法。
• 缺点：
  • 1)学习算法的收敛速度慢；
  • 2)网络中隐含节点个数的选取尚无理论上的指导；
  • 3)从数学角度看，BP算法是一种梯度最速下降法，这就可能出现局部极小的问题。所以BP算法是不完备的。

b、交叉熵损耗

$$L=-\sum_{i=1}^{N} y^{(i)} \log \hat{y}^{(i)}+\left(1-y^{(i)}\right) \log \left(1-\hat{y}^{(i)}\right)$$

c、均方误差损耗

$$E=\frac{1}{2} \sum_{k=1}^{l}\left(y^{(i)}-\hat{y}^{(i)}\right)^{2}$$

（五）K-均值 - 聚类

简单

也是一种EM算法

（六）Apriori – 关联规则

a、关联规则的任务

给定一个事务集合T，关联规则挖掘的目标是寻找所有满足下面条件的规则

支持度 ≥ minsup（支持度阈值）

置信度 ≥ minconf（置信度阈值）

b、两步方法

1. 频繁项集的产生

产生 支持度 ≥ minsup 的所有项集

2. 规则的产生

由每个频繁项集产生 置信度 ≥ minconf 的规则

c、产生频繁项集的Apriori算法流程

• 设定k=1
• 扫描事务数据库一次，生成频繁的1-项集
• 如果存在两个或以上频繁k-项集，重复下面过程：
  • [候选产生] 由长度为k的频繁项集生成长度为k+1的候选项集
  • [候选前剪枝] 对每个候选项集，若其具有非频繁的长度为k的子集，则删除该候选项集
  • [支持度计算] 扫描事务数据库一次，统计每个余下的候选项集的支持度
  • [候选后剪枝] 删除非频繁的候选项集，仅保留频繁的(k+1)-项集
  • 设定k = k+1

d、产生规则的Apriori算法流程

同上，只是计算置信度，而不是支持度

e、强关联规则

1. 由Apriori算法（当然别的也可以）产生频繁项集

2. 根据选定的频繁项集，找到它所有的非空子集

3. 强关联规则需要满足最小支持度和最小置性度 （假设关联规则是：A=>B ， support（A=>B）= { P(AUB) } confidence（A=>B）=P(B|A)={ P(AUB)/P(A) } 。这里求概率都可以替换为求支持度计数（就是统计在源数据表中各个出现的次数，例如:P(AUB) 就找A和B在源数据表中同时发生了多少次)

4. 找到所有可能性的关联规则（一个关联规则的reverse是不同的关联规则，比如A=>B和B=>A是不同的）。例如：频繁项集为：{1,2,3} ——–>非空子集则为：{1,2},{1,3},{2,3},{1},{2},{3}———->可能的关联规则为：{1,2}=>3 , {1,3}=>2 , {1,3}=>2 , 1=>{2,3},2=>{1,3},3=>{1,2}

5. 最后计算所有可能的关联规则的置信度，找到符合最小置信度（会给出）的规则，它们则为强关联规则。

（七）GSP算法 – 挖掘序列模式

和apriori算法步骤相同，特殊的一点是“合并”步骤，即，将k-频繁序列中的各序列合并为候选(k+1)-频繁序列的步骤，如下：

（八）Bagging算法、AdaBoost算法

a、Bagging

基本思想

装袋又称自助聚集，是一种根据均匀概率分布从数据中重复抽样(有放回)的技术。

每个自助样本集都和原数据集一样大。由于抽样过程是有放回的，因此一些样本可能在同一个训练集中出现多次，而其它一些却可能被忽略。在每一个抽样生成的自助样本集上训练一个基分类器，对训练过的k个基分类器投票，将测试样本指派到得票最高的类。

特点

• 装袋通过降低基分类器的方差改善了泛化误差。
• 装袋的性能依赖于基分类器的稳定性。
  • 如果基分类器是不稳定的，装袋有助于降低训练数据的随机波动导致的误差；
  • 如果基分类器是稳定的，则集成分类器的误差主要是由基分类器的偏倚所引起的。
  • 另外由于每一个样本被选中的概率相同，因此装袋并不侧重于训练数据集中的任何特定实例。因此对于噪声数据，装袋不太受过分拟合的影响。

b、AdaBoost

https://blog.csdn.net/px_528/article/details/72963977

基本思想

Adaboost算法基本原理就是将多个弱分类器（弱分类器一般选用单层决策树）进行合理的结合，使其成为一个强分类器。

Adaboost采用迭代的思想，每次迭代只训练一个弱分类器，训练好的弱分类器将参与下一次迭代的使用。也就是说，在第N次迭代中，一共就有N个弱分类器，其中N-1个是以前训练好的，其各种参数都不再改变，本次训练第N个分类器。其中弱分类器的关系是第N个弱分类器更可能分对前N-1个弱分类器没分对的数据，最终分类输出要看这N个分类器的综合效果。

两个权重

Adaboost算法中有两种权重，一种是数据的权重，另一种是弱分类器的权重。

其中，数据的权重主要用于弱分类器寻找其分类误差最小的决策点，找到之后用这个最小误差计算出该弱分类器的权重（发言权）。分类器权重越大说明该弱分类器在最终决策时拥有更大的发言权。

数据权重

所谓“数据的权重主要用于弱分类器寻找其分类误差最小的点”，其实，在单层决策树（一般使用单层决策树作为弱分类器）计算误差时，Adaboost要求其乘上权重，即计算带权重的误差。

举个例子，在以前没有权重时（其实是平局权重时），一共10个点时，对应每个点的权重都是0.1，分错1个，错误率就加0.1；分错3个，错误率就是0.3。现在，每个点的权重不一样了，还是10个点，权重依次是[0.01,0.01,0.01,0.01,0.01,0.01, 0.01,0.01,0.01,0.91]，如果分错了第1一个点，那么错误率是0.01，如果分错了第3个点，那么错误率是0.01，要是分错了最后一个点，那么错误率就是0.91。这样，在选择决策点的时候自然是要尽量把权重大的点（本例中是最后一个点）分对才能降低误差率。由此可见，权重分布影响着单层决策树决策点的选择，权重大的点得到更多的关注，权重小的点得到更少的关注。

在Adaboost算法中，每训练完一个弱分类器都就会调整权重，上一轮训练中被误分类的点的权重会增加，在本轮训练中，由于权重影响，本轮的弱分类器将更有可能把上一轮的误分类点分对，如果还是没有分对，那么分错的点的权重将继续增加，下一个弱分类器将更加关注这个点，尽量将其分对。

分类器权重

由于Adaboost中若干个分类器的关系是第N个分类器更可能分对第N-1个分类器没分对的数据，而不能保证以前分对的数据也能同时分对。所以在Adaboost中，每个弱分类器都有各自最关注的点，每个弱分类器都只关注整个数据集的中一部分数据，所以它们必然是共同组合在一起才能发挥出作用。所以最终投票表决时，需要根据弱分类器的权重来进行加权投票，权重大小是根据弱分类器的分类错误率计算得出的，总的规律就是弱分类器错误率越低，其权重就越高。

如何优化分类器？

分类器一般为单层决策树。

遍历所有属性的属性值，得到一个阈值，使得分错率最小，其中分错率通过数据权重计算。

如何计算分类器权重？

$$\alpha_{t}=\frac{1}{2} \ln \left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right)$$

其中参数$\epsilon_{t}$为第$t$轮的误差，即弱分类器和全体分类器对于训练集中样本$x_i$的预测结果不一样的概率，可以公式化为：
$$
\epsilon_{t}=P_{\boldsymbol{x} \sim \mathcal{D}{t}}\left(h{t}(\boldsymbol{x}) \neq f(\boldsymbol{x})\right)
$$

如何计算数据权重？

$$
\begin{aligned}
\mathcal{D}{t+1}(\boldsymbol{x}) &=\frac{\mathcal{D}(\boldsymbol{x}) e^{-f(\boldsymbol{x}) H{t}(\boldsymbol{x})}}{\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{\left.-f(\boldsymbol{x}) H{t}(\boldsymbol{x})\right]}\right.} \
&=\frac{\mathcal{D}(\boldsymbol{x}) e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})} e^{-f(\boldsymbol{x}) \alpha_{t} h_{t}(\boldsymbol{x})}}{\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H{t}(\boldsymbol{x})}\right]} \
&=\mathcal{D}{t}(\boldsymbol{x}) \cdot e^{-f(\boldsymbol{x}) \alpha{t} h_{t}(\boldsymbol{x})} \frac{\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H{t-1}(\boldsymbol{x})}\right]}{\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{\left.-f(\boldsymbol{x}) H{t}(\boldsymbol{x})\right]}\right.}
\end{aligned}
$$

（九）EM半监督学习

（十）规则序列覆盖算法 – 产生决策表