机器学习与数据挖掘考试复习

引言之前

这门课谁选谁傻逼
如果你恨一个人，那就快让他来选zjk老师的机器学习与数据挖掘吧！
明年一定不选了

引言

1.数据挖掘中知识发现的几个步骤。

• 确定知识发现的目标：确定知识发现的目的，要发现哪些知识。

• 数据采集： 从网络爬虫、数据库导出、CSV文件等数据源获取目标数据采集到指定的系统中。“数据质量决定数据挖掘的上限，而算法仅仅是逼近这个上限。”

• 数据探索：采集到的数据往往不可以直接使用，需用采用可视化技术，将数据的特征展现出来，探索数据特征的基本统计描述、数据特征间的相似性/相异性。

• 数据预处理：主要包括数据清理、数据集成、数据规约、数据变换和离散化等几个部分(1) 数据清理：主要包括缺失值与异常值的清理(2) 数据集成：将多种数据源集到一起，放在一个数据仓库的过程。在数据集成的过程中会出现实体识别（Entity Resolution）、冗余属性识别、数据值冲突等问题。(3) 数据规约：在保证原始数据信息不丢失的前提下，减少分析使用的数据量。数据规约中最常使用的方式是维归约。维归约的含义是将原先高维的数据合理地压缩成低维数据，而减少数据量，常用的方法为特征的提取，如线性判别分析LDA和主成分分析PCA。(4) 数据的变换：将原始的特征数据进行归一化和标准化的操作。(5) 数据的离散化可通过聚类、直方图、分箱等方法完成。

• 数据挖掘（模型选择）：对预处理后的数据进行挖掘的过程。传统的数据挖掘将算法大体分为有监督的学习与无监督的学习两种。

• 模型评估：对数据挖掘结果的评价，也是评价模型效果好与坏的标准，常见的评估指标有精度、召回率等。

• 原文链接

2.数据挖掘的应用

• 目标检测
• 文本识别
• 语音识别
• 自动驾驶
• 疾病诊断
• 社交网络推荐
• ……

学习的可行性

1. Hoeffding不等式

Hoeffding不等式给出了随机变量的和(随机变量的和)与其期望值偏差的概率上限。

一般形式：
令$X_1,……,X_n$为独立的随机变量，且有$X_i\in [a,b]，i=1,……,n$。这些随机变量的和为：

$$S_n=X_1+X_2+…+X_n$$

此时，霍夫丁不等式可表示为：

$$\forall t>0,P(S_n-E[S_n]\geq t)\leq exp({-\frac{2t^2}{\sum_{i=1}^{n}(b_i-a_i)^2}})$$

2. 使用Hoeffing不等式说明学习的可行性

关键是从$h(x)$在训练样本上的错误率推导到对于全体样本的错误率。由霍夫丁不等式可知这两个错误率是PAC的，所以，当对于训练样本，$h(x)$的错误率可以接受时，对于全体样本，$h(x)$的错误率就也就还凑合。

假设有一个假设空间$H$，机器学习的任务可以抽象为从训练样本$D$中学习到一个函数$h(x)$，使得这个函数与目标函数$f(x)$相等，此训练样本中包括$N$个样本。当学习到的函数$h(x)=f(x)$时，认为是正确的。但是我们不关注正确的情况，我们关注的是错误率。在这里，定义两个错误率：
$E_{in}(h \neq f)$代表h在训练样本上的错误率；

$E_{out}(h \neq f)$代表h在全体样本上的错误率。
由Hoeffding不等式：

$$P[|E_{in}(h\neq f)-E_{out}(h\neq f)|\geq \epsilon]\leq 2exp(-2\epsilon^2N)$$

其中，$N$为训练样本集中的样本数。当$N$足够大时，有：

$$P[ E_{in}(h\neq f)-E_{out}(h \neq f) \geq \epsilon]\simeq 0$$

可以认为$h(x)$对于训练样本的错误率和对于全部样本的错误率是PAC的。此时，机器学习是可行的。

数据与数据预处理

1.有哪四种不同的属性类型？分别可以进行什么操作？

• 标称属性：标称属性的值往往代表了物体的某种状态，不具有有意义的序而且不是定量的。如人类的头发颜色，可分为黑色，黄色，棕色，金色等；对标称属性的值一般进行众数，熵，列联相关，卡方检验操作。
• 序数属性：序数属性的值之间具有有意义的序，但是相继值之间的差未知。比如买衣服分为小号，中号和大号。对于序数属性的值，一般进行求中值，求百分位，秩相关，游程检验，符号检验等操作。
• 区间标度属性：区间标度属性首先是一种数值属性，可以用实数值表示，可以计算不同值之间的差值，但是，区间标度属性不做比例讨论，比如温度和日期；对于区间标度属性，我们一般采用均值，标准差，皮尔逊相关，t和F检验等操作。
• 比例标度属性：比例标度属性也是一种数值属性，但是这种属性的值可以描述一个值与另一个值之间的倍数关系，如货币，重量，高度等；对于比例标度属性的值，我们一般进行几何平均，调和平均，百分比变差等操作。
  

2.非对称属性？

非对称属性是指，只有非零数据属性重要的属性，比如二元属性就是一种非对称属性。

3.数据对象之间的相似度和相异度计算。（可能会考计算？）

相似度：评价两个数据对象之间有多相似，通常落在区间[0,1]上。
相异度：评价两个数据对象之间有多不同，最小值通常为0，最大值可能为$+\infty$
为了评价相似度和相异度，通常引入邻近性的概念。

4.数据预处理的主要任务。

• 数据清洗
• 数据整合
• 数据转化
• 数据约减
• 数据离散化
• 数据清理（data cleaning）例程通过填写缺失的值，光滑噪声数据，识别或删除利群点，并解决不一致性来清理数据。如果用户认为数据是脏的，则他们可能不会相信这些数据上的挖掘结果。此外，脏数据可能使挖掘过程陷入混乱，导致不可靠的输出。尽管大部分挖掘例程都有一些过程用来处理不完整数据或噪声数据，但是他们并非总是鲁棒的（Robust,系统的健壮性）。相反，他们更致力于避免被建模的函数过分拟合数据。因此，一个有用的预处理步骤旨在使用数据清理例程处理你的数据。分析使用来自多个数据源的数据，涉及集成多个数据库、数据立方体或文件，即数据集成（data integration）。代表同一概念的属性在不同的数据库中可能具有不同的名字，导致不一致性和冗余。命名的不一致还可能出现在属性值中。包含大量冗余数据可能降低知识发现过程的性能或使之陷入混乱。显然，除了数据清理之外，必须采取措施避免数据集成时的冗余。通常，在为数据仓库准备数据时，数据清理和集成将作为预处理步骤进行。还可以再次进行数据清理，检测和删去可能由集成导致的冗余。在为分析而选取的数据集是巨大的，这肯定会降低数据挖掘过程的速度。数据归约可以降低数据集的规模，而又不损害数据挖掘的结果。数据归约（data reduction）得到数据集的简化表示，它小得多，但能够产生同样的（或几乎同样的）分析结果。数据归约策略包括维归约和数值归约。在维归约中，使用数据编码方案，以便得到原始数据的简化或“压缩”表示。例子包括数据压缩技术（例如，小波变换和主成分分析），以及属性子集选择（例如，去掉不相关的属性）和属性构造（例如，从原来的属性集导出更有用的小属性集）。在数值归约中，使用参数模型（例如，回归和对数线性模型）或非参数模型（例如，直方图、聚类、抽样或数据聚集），用较小的表示取代数据。对于数据挖掘而言，离散化与概念分层产生是强有力的工具，因为它们使得数据的挖掘可以在多个抽象层上进行。规范化、数据离散化和概念分层产生都是某种形式的数据变换（data transformation）。数据变换操作是引导挖掘过程成功的附加的预处理过程。

5.处理缺失值的方法。

• 删除数据对象或者属性 一种简单而行之有效的方法就是直接删除具有遗漏值的数据对象。然而，即使是不完整的数据对象中也可能包含着一些有用的信息，并且，如果许多对象都有遗漏值，则很难甚至不可能进行可靠的分析。因此，在进行删除操作时应该谨慎的考虑是否合算。
• 估计遗漏值 有时，遗漏值何以可靠的估计。例如，考虑大致以平滑方式变化的，具有少量但分散遗漏值的时间序列时，可以通过其他存在的值对遗漏值进行插值操作。如果属性值是连续的，可以取平均值进行代替，如果属性是分类的，则可以使用最近邻中最经常出现的属性值。
• 在分析时忽略缺失值 直接将缺失值置零，除非遗漏值的数量很大，否则这样处理的误差并不大。

决策树学习

1.决策树学习的基本思想

原文链接
决策树又称为判定树，是运用于分类的一种树结构，其中的每个内部节点代表对某一属性的一次测试，每条边代表一个测试结果，叶节点代表某个类或类的分布。决策树的决策过程需要从决策树的根节点开始，待测数据与决策树中的特征节点进行比较，并按照比较结果选择选择下一比较分支，直到叶子节点作为最终的决策结果。
本质上，决策树算法就是不断地在数据集中寻找最优划分的过程，使划分后得到的子数据集的不确定性不断下降，直到分类完成。

2.分类错误率，熵，信息增益，如何根据不同的度量选择最佳划分

分类错误率：

$$错误率=\frac{错误预测数}{预测总数}$$

熵：信息熵使度量样本集合纯度最常用的一种指标。假定当前样本集合$D$中第$k$类样本所占的比例为$p_k(k=1,2,3…,\lvert \gamma \rvert)$，则$D$当前的信息熵定义为：

$$Ent(D)=-\sum_{k=1}^{|\gamma|}p_klog_2p_k$$

信息增益：假定离散属性$a$有$V$个可能的取值$\left\lbrace a^1,a^2,…,a^V \right\rbrace$，若使用$a$来对样本集$D$进行划分，则会产生$V$个分支节点，其中第$v$个分支节点包含了$D$在属性$a$上的所有取值为$a^v$的样本，记为$D^v$，计算$D^v$的信息熵，在考虑不同分支节点包含的样本数不同对分支节点赋予权重，即可计算出用属性$a$对样本集$D$进行划分得到的信息增益:

$$Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$$

无论使用什么度量进行表述，我们都希望决策树的分支结点所包含的样本尽可能属于同一类别，即不纯度越低越好。

3.缺失值对决策树的影响

缺失值对决策树的影响体现在三个方面：

• 影响不纯度的计算
• 影响属性含有缺失值的实例向子结点的分类
• 影响属性含有缺失值的测试实例的分类

4.给定混淆矩阵，分类效果度量不同指标的含义和计算方法。

$$Recall=\frac{TP}{TP+FN}$$ $$Acurracy=\frac{TP+TN}{TP+FN+TN+FP}$$

5.评估分类器性能的留一法和k折交叉验证

• 留一法：假定数据集D中包含m个样本，若令k=m，则得到了交叉验证法的一个特例：留一法（Leave-One-Out，简称LOO）。显然，留一法不受随机样本划分方式的影响，因为m个样本只有唯一的方式划分为m个子集——每个子集包含一个样本；留一法使用的训练集与初始数据集相比只少了一个样本，这就使得在绝大多数情况下，留一法中被实际评估的模型与期望评估的用D训练出的模型很相似。因此，留一法的评估结果往往被认为比较准确。
• k折交叉验证：首先，将数据集$D$划分为$k$个大小相等的部分，然后使用每种分类方法在$k-1$份数据上构建模型，并在剩余的划分上进行检验，将这个步骤重复$k$次，每次使用不同的划分进行检验。

6.过拟合和欠拟合

原文链接
过拟合：具体表现就是最终模型在训练集上效果好；在测试集上效果差。模型泛化能力弱。
欠拟合：欠拟合是指对训练样本的一般性质尚未学好。在训练集及测试集上的表现都不好。

神经网络

1.神经网络如何学习 有何特点

• 如何学习
  神经网络的学习指的是从训练数据中自动获取最优权重参数的过程。学习的目的是以损失函数为基准，找出能使它的值达到最小的权重参数，采用函数斜率的梯度法可以找出使损失函数尽可能小的权重参数的值。

• 特点
  • 人工神经网络由许多相互连接的神经元模型构成，这些神经元模型之间通过加权互连。
  • 人工神经网络具有并行结构和并行处理机制，人工神经网络不仅在结构上是并行的，在处理顺序上也是并行的。
  • 人工神经网络可以通过调节神经元之间的连接权重来进行学习

2.梯度下降算法

原文链接
寻找损失函数的最低点，就像我们在山谷里行走，希望找到山谷里最低的地方。那么如何寻找损失函数的最低点呢？在这里，我们使用了微积分里导数，通过求出函数导数的值，从而找到函数下降的方向或者是最低点（极值点）。

损失函数里一般有两种参数，一种是控制输入信号量的权重(Weight, 简称 $w$ ），另一种是调整函数与真实值距离的偏差（Bias，简称 $b$ ）。我们所要做的工作，就是通过梯度下降方法，不断地调整权重 $w$ 和偏差$b$，使得损失函数的值变得越来越小。

假设某个损失函数里，模型损失值 $L$与权重 $w$ 有下图这样的关系。实际模型里，可能会有多个权重 $w$ ，这里为了简单起见，举只有一个权重 $w$ 的例子。权重$w$ 目前的位置是在A点。此时如果求出A点的梯度 $\frac{dL}{dw}$ ，便可以知道如果我们向右移动，可以使损失函数的值变得更小。

公式太多了，好好看

3.多层神经网络使用什么算法进行训练？

逆误差传播算法

算法过程：
1：在（0,1）区间内随机初始化网络中的所有连接权值和阈值
2：repeat
3：    for all (xk,yk) ∈ D do
4：        根据当前参数和公式计算输出
5：        计算输出层神经元的梯度项gj
6：        计算隐藏层神经元的梯度项eh
7：        计算和更新连接权值ωhj、νih和阈值θj γh
8：    end for
9：until 达到停止训练的条件

贝叶斯学习

1.根据贝叶斯理论，如何计算一个假设$h$成立的后验概率

先验概率（prior probability）：指根据以往经验和分析。在实验或采样前就可以得到的概率。
后验概率（posterior probability）：指某件事已经发生，想要计算这件事发生的原因是由某个因素引起的概率。
由贝叶斯定理：

$$P(B|A)=\frac{P(A|B)P(B)}{P(A)}$$

2.极大后验概率假设和极大似然假设有何区别

最大后验概率假设即求参数$\theta$，使后验概率$P(\theta|X)$最大，由上文所述，

$$P(\theta|X)=\frac{P(X|\theta)P(\theta)}{P(X)}$$

式中，$P(X)$已知，所以极大后验概率假设就是求取$P(X|\theta)P(\theta)$最大时参数$\theta$的值。
极大似然假设即求似然函数$P(X|\theta)$最大时参数$\theta$的值。
两种假设方法的不同之处在于极大后验概率假设在计算时考虑了先验概率参数$P(\theta)$，极大后验概率假设认为参数$\theta$的值是服从某种分布的，而极大似然假设认为参数$\theta$的值是一个定值。当参数$\theta$服从均匀分布时，可以认为这两种假设就是相同的。

3.最小描述长度的基本思想

最小描述长度( MDL) 原理是 Rissane 在研究通用编码时提出的。其基本原理是对于一组给定的实例数据 D ， 如果要对其进行保存 ，为了节省存储空间， 一般采用某种模型对其进行编码压缩，然后再保存压缩后的数据。同时， 为了以后正确恢复这些实例数据，将所用的模型也保存起来。所以需要保存的数据长度( 比特数) 等于这些实例数据进行编码压缩后的长度加上保存模型所需的数据长度，将该数据长度称为总描述长度。最小描述长度( MDL) 原理就是要求选择总描述长度最小的模型。
如果将贝叶斯网络作为对实例数据进行压缩编码的模型， MDL原理就可以用于贝叶斯网络的学习。该度量被视为网络结构的描述长度和在给定结构下样本数据集的描述长度之和。一方面，用于描述网络结构的编码位随模型复杂度的增加而增加 ； 另一方面， 对数据集描述的编码位随模型复杂度的增加而下降。因此，贝叶斯网络的 MDL总是力求在模型精度和模型复杂度之间找到平衡。构建贝叶斯网络首先定义一个评分函数， 该评分函数描述了每个可能结构对观察到的数据拟合， 其目的就是发现评分最大的结构，这个过程连续进行到新模型的评分分数不再比老模型的高为止。

4.贝叶斯最优分类器的基本思想

贝叶斯决策论考虑在所有的相关概率已知的情况下，基于这些概率和误判损失来确定最优的类别标记。
假设有$N$种可能的类别标记，即$\mathcal{Y} = [ c_1,c_2,...,c_N]$
$\lambda_{ij}$是将一个$c_i$错分为$c_j$产生的损失，则在样本$x$上产生的条件风险为：

$$R(c_i|x)=\sum_{j=1}^{N}\lambda_{ij}P(c_j|x)$$

贝叶斯最优分类器的思想就是寻找一个判定准则$h:\mathcal{X}\mapsto\mathcal{Y}$，最小化总体风险：

$$R(h)=\mathbb{E}_x[R(h(x)|x)]$$

对于每个样本$x$,若分类器$h$能够最小化条件风险$R(h(x)|x)$，则总体风险$R(h)$也将被最小化。这样就产生了贝叶斯判定准则：为最小化总体风险，只需在每个样本上选取那个能使条件风险最小的类别标记，即：

$$h^*(x)=argmin_{c \in \mathcal{Y}}R(c|x)$$

此时，$h^*(x)$记为贝叶斯最优分类器。

5.朴素贝叶斯分类算法

为了解决直接使用贝叶斯公式计算后验概率时，可能遇到的类条件概率难以计算问题朴素贝叶斯分类器采用了属性条件独立性假设：对已知类别，假设所有的属性都相互独立。此时后验概率将十分便于计算。

$$P(c|x)=\frac{P(c)}{P(x)}\prod_{i=1}^{d}P(x_i|c)$$

式中:$d$为属性的个数，$x_i$为样本$x$在第$i$个属性上的取值。
此时，基于贝叶斯判定准则：

$$h_{nb}(x)=argmax_{c \in \mathcal{Y}}P(c)\prod^d_{i=1}P(x_i|c)$$

这就是朴素贝叶斯分类器的表达式。

6.贝叶斯信念网络的预测和诊断

直接使用贝叶斯网定义的联合概率分布来精确计算后验概率
但是，当贝叶斯网结点很多且连接稠密时，后验概率就很难以进行精确计算。
应该引入Gibbs采样算法（但是ppt上没有说怎么对贝叶斯网进行gibbs采样，猜测应该不考）。
基本上就是使用全概率公式结合贝叶斯网给出的CPT来计算吧，还是比较简单的
ppt上的几道计算：

基于实例的学习

1.K近邻学习算法

k近邻算法是数据挖掘和机器学习中十分常用的一种学习算法，是一种无参数的懒惰学习算法，在学习阶段仅仅是将数据保存起来，训练时间的开销为0，待收到样本后再进行处理。这种算法的基本思想是找到距离样本最近的k个点，基于这k个邻居的标签进行投票。票数最多的标签即为预测结果。

• KNN的优点：
  • knn算法原理十分简单，易于解释结果。
  • 懒惰学习，在训练过程中不对基础的数据模式做出假设，训练过程的复杂度为O(n)。
  • 既可用于分类，也可用于回归；既可用于数值型数据，也可用于离散性数据。
  • 对异常值不敏感。
• KNN的缺点：
  • 计算复杂性高，空间复杂性高。
  • 当样本不平衡时，有的类别的样本数量很多，其他样本的数量很少，可能会导致分类出错。
  • 计算量较大，需要计算每个样本到所有点的距离，再对距离排序才能求得k个近邻点。

2.为什么在使用K近邻算法时要对距离进行归一化

当样本有多个特征值时，其中某个特征数量级比较大，其他特征较小时，分类结果会被数量级比较大的特征值所主导，而弱化了其他特征的影响，这是各个特征值的量纲不同所致，需要将数据归一化处理

3.局部加权线性回归

线性回归的一个问题是有可能出现欠拟合，因为它求的是具有最小均方误差的无偏估计，显然模型欠拟合将无法做出很好的回归预测，所以有些方法允许在估计中引入一些偏差，从而降低预测的均方误差。局部线性加权的思想是对待预测点附近的每个点赋予一个权重，然后在带权的样本上基于最小均方误差来进行回归.
对于一个数据点，与其靠近的点，权重大，与其相距较远的点，权重小，从而优化问题会有所偏倚，靠近的点对该数据点的回归拟合起较大作用，而相距较远的点由于权数很小，造成的影响基本可以忽略不计，这样就等同于每个点的回归都是基于与其相距较近的点为基础，而忽略了较远的点，这也就是局部加权线性回归局部的由来，因为它着重考虑目标点局部的数据点为回归基础.
局部加权回归在选择到合适的k时，回归拟合的效果比普通线性回归好很多，但是有一点需要注意，就是局部线性加权回归的计算量很大，因为对于每个数据点，都需要计算与其他数据点的距离矩阵θ，即遍历整个数据集，因此我们还需要探索更加高效简介的算法，减小时间空间开销.
原文链接

4.懒惰学习和积极学习的区别

• 积极学习：这种学习方法是指在利用算法进行判断之前，首先通过训练集的数据训练得到一个目标函数，在需要进行判断是利用已经训练好的函数进行决策，这种方法需要在开始的时候进行一些工作，在后期使用时十分方便。

• 消极学习：这种学习方法在最开始的时候不会根据已有的样本数据构建目标函数，只是简单的把训练好的样本储存好，后期对新加入的样本进行判断时，才分析新进入样本与已存在样本之间的关系。据此确定新进入样本的目标函数值。

集成学习

1.集成学习的定义

集成学习就是说将多个 “单个学习器（Individual Learner）”用某种策略来结合起来，组成一个“学习委员会（committee）”，使得整体的泛化性能得到大大提高。

2.集成学习的两个主要问题

准确性和多样性。
准确性：个体学习器不能太差，要有一定的准确度（即不能有一个太短的短板）
多样性：个体学习器之间的输出要具有差异性（各有所长的意思，不能所有的学习器的优点都是一样的）

3.bagging基本思想和伪代码

bagging方法：bagging方法是并行式集成学习方法中最著名的代表。给定包含$m$个样本的数据集，我们先随机的从中取出一个样本放入采样集中，再把该样本放回初始数据集。使得下次采样时该样本一九有可能被选中。这样，经过$m$次操作，我们就得到了含$m$个样本的采样集，初始训练集中有的样本在采样集中多次出现，有的则从未出现。基于每个采样集训练出一个基学习器，再将这些学习器进行结合。

4.boosting基本思想和伪代码

boosting方法：boosting方法是一种具有代表性的序列化方法。可以将弱学习器提升为强学习器。先从初始训练集中训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的样本在后续训练的过程中受到更多的关注，基于调整后的样本再训练下一个基学习器；如此重复，直到基学习器的数量达到事先指定值$T$，最终将这$T$个基学习器进行加权结合。（adaboost算法）

5.为何集成学习有效

当集成学习中集成的个体分类器数目足够多时，集成的错误率将指数级下降，趋向于0。
以简单的二分类问题为例：
考虑简单的二分类问题$y \in [ -1,+1 ] $和真实函数$f$，假定基分类器的错误率为$\epsilon$,则对于每个基分类器$h_i$都有：

$$P(h_i(x)\neq f(x))=\epsilon$$

集成学习通过简单投票法结合$T$个基分类器，若有超过半数的基分类器正确，则集成分类器就正确：

$$H(x)=sign(\sum_{i=1}^{T}h_i(x))$$

假设基分类器的错误率之间相互独立，由Hoeffding不等式可知，集成分类器的错误率：

$$\begin{align*} P(H(x)\neq f(x))&=\sum_{k=0}^{[T/2]}\begin{pmatrix} T\\ k \end{pmatrix}(1-\epsilon)^{k}\epsilon^{1-k}\\ &\leq exp(-\frac{1}{2}T(1-2\epsilon)^2) \end{align*}$$

由上述公式可得，当集成学习中基分类器的数目$T$增大时，集成学习的错误率将指数级下降。因此，集成学习比单个模型更加有效。

分类技术

1.基于规则的分类器有何优点，需要解决什么问题

规则集的表达能力等价于决策树
基于规则的分类器通常用于产生更易于解释的描述性模型，而模型的性能却可与决策树分类器相媲美。
很多基于规则的分类器（如RIPPER）采用的基于类的规则定序方法非常适用于处理类分布不平衡的数据集

在规则的增长过程中，需要一种评估度量来确定应该增加或者删除哪个规则。准确率就是一种很常用的选择。但是，在使用准确率作为评估度量时，算法可能会受到一些覆盖率较低，但是准确率十分高的规则的欺骗。在这时，我们常常使用统计检验剪除覆盖率较低的规则，或者转而采用一些考虑规则覆盖率的评估度量。

2.序列覆盖算法

算法开始时决策表R为空，接下来用函数提取类的覆盖当前训练记录集的最佳规则。在提取规则时，类的所有训练记录被看做是正例，而其他类的训练记录则被当成反例。如果一个规则覆盖大多数正例，没有或者仅覆盖极少数反例，那么该规则是可取的。一旦找到这样的规则，就删掉它所覆盖的训练记录，并把新规则追加到决策表R的尾部。重复这个过程直到满足终止条件。

原文链接

3.支持向量机的基本原理

SVM的一般做法是：将所有待分类的点映射到“高维空间”，然后在高维空间中找到一个能将这些点分开的“超平面”，这在理论上是被完全证明了是成立的，而且在实际计算中也是可行的。

聚类分析

1.聚类的定义

无监督学习中，训练样本的信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。应用最广也是研究最多的是——-聚类

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”。聚类过程只能形成簇结构，而簇对应的概念语义需要由使用者来把握和命名。聚类既可以作为一个单独过程用来寻找数据内部的分布结构，也可以作为分类等其他学习任务的前驱过程。（西瓜书）

2.聚类的类型

• 基于划分的聚类/基于层次的聚类
• 互斥的/重叠的/模糊的
• 完全的/部分的
  
  

3.簇的类型

4.层次聚类的两种主要类型

5.计算簇间相似性的单链和全链方法

单链方法：该方法中两个簇的邻近度定义为两个不同簇中任意两点之间的最短距离。
全链方法：该方法中两个簇的邻近度定义为两个不同簇中任意两点之间的最长距离。

6.K均值和K中心点算法

• K均值算法：
  给定样本集$D=\left{x_1,x_2,…x_m\right}$,k均值算法即针对聚类所得的簇$\mathcal{C}=\left{C_1,C_2,…,C_k\right}$划分最小化平方误差 $$E=\sum^k_{i=1}\sum_{x \in C_i}||x-\mu_i||^2_2$$ 最小化上式是NP难的，所以采用迭代方法进行求解。其步骤是，预将数据分为K组，则随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。
• K中心点算法：
  K-中心点算法也是一种常用的聚类算法，K-中心点聚类的基本思想和K-Means的思想相同，实质上是对K-means算法的优化和改进。在K-means中，异常数据对其的算法过程会有较大的影响。在K-means算法执行过程中，可以通过随机的方式选择初始质心，也只有初始时通过随机方式产生的质心才是实际需要聚簇集合的中心点，而后面通过不断迭代产生的新的质心很可能并不是在聚簇中的点。如果某些异常点距离质心相对较大时，很可能导致重新计算得到的质心偏离了聚簇的真实中心。
  K-中心聚类算法计算的是某点到其它所有点的距离之和最小的点，通过距离之和最短的计算方式可以减少某些孤立数据对聚类过程的影响。从而使得最终效果更接近真实划分，但是由于上述过程的计算量会相对大于K-means，大约增加O（n）的计算量，因此一般情况下K-中心算法更加适合小规模数据运算。

8.聚类评估

• 相似性矩阵
• SSE
• Cohesion & Separation
• SC
• Entropy Purity

链接

关联分析

1.概念

• 项集： 一个或几个项目的集合
• 频繁项集：支持度大于或等于最小阈值的项集
• 支持度：项集出现的频率
• 置信度：置信度表示在先决条件X发生的情况下，由关联规则”X→Y“推出Y的概率。表示在发生X的项集中，同时会发生Y的可能性，即X和Y同时发生的个数占仅仅X发生个数的比例
• 最大频繁项集：如果频繁项集L的所有超集都是非频繁项集，那么称L为最大频繁项集或称最大频繁模式
• 闭频繁项集：所谓闭项集，就是指一个项集X，它的直接超集（最小的严格超集）的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的，也就是它的支持度大于等于最小支持度阈值，那它就称为闭频繁项集。

2.apriori算法

Apriori是一种常用的数据关联规则挖掘方法，它可以用来找出数据集中频繁出现的数据集合。找出这样的一些频繁集合有利于决策，例如通过找出超市购物车数据的频繁项集，可以更好地设计货架的摆放。需要注意的是它是一种逐层迭代的方法，先找出频繁项集L1，再利用L1找出频繁2项集，以此类推。
原文链接

3.FP增长算法

原文链接

4.关联模式评估

• 使用interesting measures对派生模式进行修剪和排名
• 使用支持度和置信度对关联模式进行评估

维度约减

1.过滤法和包裹法

过滤法：过滤法就是按照发散性或者相关性对各个特征进行评分，设定阈值或者选择阈值的个数，完成特征选择。根据选择的评估标准不同，有方差法，相关系数法，互信息法。优点：不依赖于任何机器学习方法，且不需要交叉验证，计算效率比较高。缺点：没有考虑机器学习算法的特点

包裹法：包裹法是选择一种算法，然后再根据算法效果来选择特征集合。就是通过不断的启发式方法来搜索特征，主要分为如下两类。方法一：选择一些特征，逐步增加特征保证算法模型精度是否达标。方法二：删除一些特征，然后慢慢在保持算法精度的条件下，缩减特征。缺点1.需要对每一组特征子集训练一个模型，计算量很大2.样本不够充分的情况下容易过拟合3.特征变量较多时计算复杂度太高

2.五种不同的特征搜索方法，基本思想和伪代码

前向搜索，后向搜索，浮动搜索，双向搜索，增L去R搜索
原文

3.维度约减效果评估

真的讲了吗？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？