数据挖掘之回归聚类算法总结

线性回归模型

回归分析

当变量之间存在互相依赖关系的时候，这时候可以进行回归分析。回归分析与相关分析在理论和方法上具有一致性，变量之间没有关系，就谈不上回归分析或者建立回归方程；相关程度越高，回归效果就越好，而且相关系数和回归系数方向一致，可以互相推算。

相关分析中的两个变量之间的地位是对等的，即变量 𝐴 与变量 𝐵 相关等价于变量 𝐵 与变量 𝐴 相关，相关分析的两个变量均为随机变量；而回归分析中要确定自变量和因变量，通常情况下只有因变量是随机变量，人们可以利用回归分析来对研究对象进行预测或控制。

回归分析往往是通过一条拟合的曲线来表示模型的建立 回归分析的参数估计 我们把因变量的观测值记为 𝑦𝑖 ，其期望值记为 𝑦¯ ,把估计值（用回归方程获得的预测值）记为 𝑦𝑖^ 。那么为了可以找到最代表原始数据信息的回归直线我们可以通过最小二乘法的方式来估计我们的参数

回归方程的检验及模型预测

对于估计出来的回归方程，可以从模型的解释程度，回归方程总体显著性以及回归系数的显著性等几个方面进行检验。

回归方程的拟合优度判定
回归方程的拟合优度主要用于判定 𝑦𝑖^ 估计 𝑦 的可靠性问题，可以用来衡量模型的解释程度。我们通过以下公式来表示回归方程的拟合程度
𝑅2=∑(𝑦𝑖−𝑦¯)2∑(𝑦𝑖−𝑦¯)2=1−∑(𝑦𝑖−𝑦𝑖)2∑(𝑦𝑖−𝑦¯)2

其中 𝑅2 的取值范围为 [0,1] 。 𝑅2 越接*于1，说明变量之间的相互依存关系越密切，回归方程的拟合程度越好
回归方程总体显著性检验
利用最小二乘法拟合出来的回归方程，都是由样本数据进行的，那么用它来对总体进行推断是否显著呢？因此可以对回归方程整体的显著性进行检验。其原假设和备择假设如下：
𝐻0:𝛽1=𝛽2=…=𝛽𝑖=0,𝐻1:𝛽𝑖不全为0

回归方程系数显著性检验
如果模型的线性关系显著，还应对模型参数估计的结果即回归方程的系数进行显著性检验，用于考察单个自变量的线性关系是否成立。其原假设和备择假设如下
𝐻0:𝛽𝑖=0(𝑖=1,2,…,𝑘)𝐻1:𝛽𝑖≠0(𝑖=1,2,…,𝑘)

回归方程系数显著性检验要求对所有估计出来的回归系数分别进行检验（截距项通常不进行显著性检验）可以利用 𝑡 统计量及检验 𝑃 值。如果当前系数对应的 𝑃 值小于显著性水平 𝑎 值，可以认为再显著性水平 𝑎 下，该回归系数是显著的。
回归方程的预测
回归预测是一种有条件的预测，依据估计出来的回归方程，在给定自变量数值的条件下对因变量进行预测。

一元线性回归

一元线性回归分析主要考察单独一个自变量对因变量的影响。其模型形如
𝑦=𝑎+𝛽𝑥+𝜀

其中： 𝑎,𝛽 是回归模型的参数，称为回归系数( 𝑎 也可以称为截距项)。而 𝜀 是随机误差项或随机扰动项，反映除了 𝑥 和 𝑦 之间的线性关系外的随机因素或不可观测因素
一元线性回归分析的基本步骤如下：

依据变量之间的关系，判断其是否是线性关系。
如果是线性关系，可以利用 𝑂𝐿𝑆 方法或者其他方法进行回归模型的参数估计
然后根据参数估计的结果进行检验

线性回归

用简单的术语定义线性回归，它是用来描述两个或多个变量之间关系的线性模型的*似值。在一个简单的线性回归中，有两个变量，因变量可以被看作是我们研究和尝试预测的 “状态 “或 “最终目标 “，自变量也称为解释变量，可以看出作为 “现象 “的 “原因 “。

当存在多个自变量时，该过程称为多重线性回归。当预测多个因变量时，该过程称为多变量线性回归。

简单线性模型的最为熟悉的方程是

𝑌=𝑎𝑋+𝑏

其中Y是因变量，X是自变量， a和b 是我们调整的参数。 a 被称为 “斜率 “或 “梯度 “， b 被称为 “截距 “。您可以将此方程解释为Y是X的函数，或Y是与X相关的。

如果您绘制模型，您将看到它是一条线，通过调整”斜率”参数，您将更改直线和独立变量轴之间的角度，”截距参数”将影响它穿过因变量的位置轴。

非线性回归是独立变量 𝑥 和因变量 𝑦 之间的关系，其导致非线性函数建模数据。基本上任何非线性的关系都可以称为非线性关系，并且通常用多项式 𝑘 来表示程度。这个表达式可以在方程的右边进一步变换，这个函数被称为由 𝑓 表示的链接函数。一些众所周知的链接函数是sigmoid（在统计世界中也被称为logit）、对数函数、互补对数和指数函数。
𝑦=𝑓(𝛽0+𝛽1𝑥+𝛽2𝑥2+…+𝛽𝑘𝑥𝑘)… (1)
其中， 𝛽𝑖 ‘s是要估计的参数，使模型与基础数据完全匹配。 让我们考虑非线性多项式回归的度数为2（二次方）和3（三次方），并且链接函数为恒等式的简单情形之一，因此方程式可简写为：
𝑦=𝛽0+𝛽1𝑥+𝛽2𝑥2+…+𝛽𝑘𝑥𝑘

非线性回归

非线性回归
现实生活中，很多变量之间的关系并不一定就像是我们在线性回归中描述的那样是线性关系，变量之间还可能存在非线性关系。如人的生长曲线，经济增长会随时间的推移而发生周期性的波动等。如果存在非线性关系的情况下去使用线性回归拟合曲线，则会丢失数据之间大量有用的信息，甚至会得出错误的结论。这种情况下，可以使用非线性回归分析来对数据之间的统计关系进行考察。

非线性形式的变量关系一般可以通过变量代换或转换的方式转化为线性关系。常见的一种模型为
𝑦=𝑎𝑥𝛽+𝜀

其中 𝑎,𝛽 为模型参数， 𝜀 为残差项
在实际建模过程中，可以把上述模型左右同时去对数，可得：
𝑙𝑛𝑦=𝑙𝑛𝑎+𝛽𝑙𝑖𝑛𝑥+𝜀→𝑦′=𝑎′+𝛽𝑥′+𝜀

其中 𝑦′=𝑙𝑛𝑦,𝑥′=𝑙𝑛𝑥,𝑎′=𝑙𝑛𝑎 ，转化之后的模型我们采取和线性回归一样的方式来进行参数估计和模型检验

对于其他的非线性模型比如对数模型 𝑦=𝑎+𝛽𝑙𝑛𝑥+𝜀 也可以转化成 𝑦=𝑎+𝛽𝑥+𝜀 包括其他类型的非线性模型都可以转化为一元线性回归。类似的存在多个自变量情形下的非线性回归，也可以按照上述变量转换和代换的方式把多元线性模型转化为多元线性模型。在statsmodels的ols中，用户可在建模的过程中张子杰把自变量和因变量按照指定方式转换并进行回归分析，其分析过程与之前的线性回归中介绍的内容无异。

逻辑回归

Logistic回归是数据科学中最重要的技术之一。它通常用于解决经典的分类问题。

线性回归和logistic回归之间有什么不同？

线性回归适用于估计连续值（例如估算房价），但它不是预测观测数据点类别的最佳工具。为了估计分类，我们需要一些关于该数据点最可能的类别的指导。为此，我们使用Logistic回归。

回想一下线性回归：

线性回归找到一个函数，它将连续因变量 y_与某些预测变量（自变量 _x1, _x2_等）相关联。简单的线性回归假设了以下形式的函数：

𝑦=𝑤0+𝑤1∗𝑥1+𝑤2∗𝑥2+…

并找到_w0_, w1, w2_等的值。术语_w0_是”截距”或”常数项”（在下式中显示为_b）：

𝑌=𝑊𝑋+𝑏

Logistic回归是线性回归的变体，当观察到的因变量y是分类时是有用的。它产生一个预测类标签作为自变量函数的概率的公式。

尽管名称 logistic 回归 ，它实际上是一个概率分类模型。 logistic回归通过采用线性回归拟合特殊的S形曲线，并使用以下函数将数值估计转换为概率：

𝑃𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑦𝑂𝑓𝑎𝐶𝑙𝑎𝑠𝑠=𝜃(𝑦)=𝑒𝑦1+𝑒𝑦=𝑒𝑥𝑝(𝑦)/(1+𝑒𝑥𝑝(𝑦))=𝑝
它产生0（如y接负无穷）和1（随着y接正无穷）之间的p值。这现在成为一种特殊的非线性回归.

在这个等式中，y 是回归结果（由系数加权的变量之和），exp是指数函数以及 𝜃(𝑦) 是 logistic 函数，也称为logistic曲线。这是一种常见的”S”形（S形曲线），最初是为模拟人口增长而开发的。

在另一个配置中，您可能也会看到过此函数：

𝑃𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑦𝑂𝑓𝑎𝐶𝑙𝑎𝑠𝑠=𝜃(𝑦)=11+𝑒−𝑥

因此，简而言之，Logistic回归通过logistic/sigmoid 传递输入，但将结果视为概率：

多项式回归模

多项式回归
理论上来说我们可以运用非线性回归中学到的方式对任何曲线进行拟合，但前提条件是必须要对模型有正确的判断，即知道非线性模型的参数设置。在一般情况下通过绘制散点图可以做到这一点。但是在更一般的情况下，如有多个自变量的情况下，无法绘制散点图，同时也很难对模型进行预估，这个时候可以使用本次实验中所介绍的方法。根据数学的相关理论，任何曲线均可以使用多项式进行逼。这种逼的分析过程即多项式回归
多项式回归类似于可线性化的非线性模型，可通过变量代换的方式使用普通最小二乘对参数进行估计。设有因变量 𝑦 和自变量 𝑥 ，它们之间的关系为 𝑛 次多项式的关系，则有如下模型
𝑦=𝑎+𝛽1𝑥+𝛽2𝑥2+𝛽3𝑥3+…+𝛽𝑛𝑥𝑛+𝜀

我们令 𝑥1=𝑥,𝑥2=𝑥2…𝑥𝑛=𝑥𝑛 ，则多项式模型就转化为如下的多元线性模型
𝑦=𝑎+𝛽1𝑥1+𝛽2𝑥2+𝛽3𝑥3+…+𝛽𝑛𝑥𝑛+𝜀

对于多元的多项式模式
𝑦=𝑎+𝛽1𝑥1+𝛽2𝑥2+𝛽3𝑥21+𝛽4𝑥1𝑥2+𝛽5𝑥22+…+𝛽𝑚𝑥𝑛𝑚+𝜀

同样可以作变量代换，令 𝑧1=𝑥1,𝑧2=𝑥2,𝑧3=𝑥21,𝑧4=𝑥1𝑥2,𝑧5=𝑥22,…..,𝑧𝑚=𝑥𝑛𝑚 ，则有
𝑦=𝑎+𝛽1𝑧1+𝛽2𝑧2+𝛽3𝑧3+…𝛽𝑚𝑧𝑚+𝜀

转化之后的模型同样可以按照多元线性回归模型进行分析。当多项式回归阶数过高时，待估计参数过多，在样本不大的情况下会比较困难，这是多项式回归的一大缺陷。因此，一般的多项式回归模型很少应用到三阶以上。

贝叶斯模型的理

贝叶斯心态

贝叶斯世界观将概率解释为事件中可信度的度量，即我们对事件发生的信心。而且这种信度是会跟着对客观世界的观察发生改变的。

𝑃(𝐴): 表示这段复杂的代码存在错误的概率，这是先验概率（然而这个概率是未知的）。
𝑋 表示发生的事件，这里即为这段代码通过了3轮测试。
𝑃(𝐴|𝑋): 表示在已经得知了 𝑋 事件后，代码没有错误的概率，这是条件概率。

贝叶斯公式
上述所说的更新对某事件的信念的过程，遵循以下的贝叶斯定理：
𝑃(𝐴|𝑋)=𝑃(𝑋|𝐴)𝑃(𝐴)𝑃(𝑋)∝𝑃(𝑋|𝐴)𝑃(𝐴)(∝表示成正比 )
其中，𝑃（𝐴） 表示先验概率，𝑃（𝐴|𝑋）表示后验概率。

朴素贝叶斯(Naive Bayes)

贝叶斯分类是一种分类算法的总称，这种算法均已贝叶斯定理为基础，故统称为贝叶斯分类。
贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为对象所属的类。

朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练数据集，首先基于特征条件独立假设学输入/输出的联合概率分布，然后基于此模型，对给定的输入𝑥，利用贝叶斯定理，利用贝叶斯定理求出后验概率最大的输出𝑦
在所有的机器学分类算法中，朴素贝叶斯（Naive Bayesian Model，NBM）和其他绝大多数的分类算法都不同。对于大多数的分类算法，比如决策树,KNN,逻辑回归，支持向量机等，他们都是判别方法，也就是直接学*出特征输出Y和特征X之间的关系，要么是决策函数𝑌=𝑓(𝑋),要么是条件分布𝑃(𝑌|𝑋)。但是朴素贝叶斯却是生成方法，也就是直接找出特征输出Y和特征X的联合分布𝑃(𝑋,𝑌),然后用𝑃(𝑌|𝑋)=𝑃(𝑋,𝑌)/𝑃(𝑋)得出。

朴素贝叶斯很直观，计算量也不大，在很多领域有广泛的应用。

条件概率公式（Condittional probability），是指在事件B发生的情况下，事件A发生的概率，用𝑃(𝐴|𝐵)来表示。

根据文氏图可知：在事件B发生的情况下，事件A发生的概率就是𝑃(𝐴|𝐵)除以𝑃(𝐵)。
𝑃(𝐴|𝐵)=𝑃(𝐴∩𝐵)𝑃(𝐵)=>𝑃(𝐴∩𝐵)=𝑃(𝐴|𝐵)𝑃(𝐵)
同理可得：
𝑃(𝐴∩𝐵)=𝑃(𝐵|𝐴)𝑃(𝐴)
所以，
𝑃(𝐴|𝐵)𝑃(𝐵)=𝑃(𝐵|𝐴)𝑃(𝐴)=>𝑃(𝐴|𝐵)=𝑃(𝐵|𝐴)𝑃(𝐴)𝑃(𝐵)

全概率公式

如果事件𝐴1,𝐴2,𝐴3,,𝐴𝑁构成一个完备事件且都有正概率，那么对于任意一个事件𝐵则有：
𝑃(𝐵)=𝑃(𝐵𝐴1)+𝑃(𝐵𝐴2)+…+𝑃(𝐵𝐴𝑛)=𝑃(𝐵|𝐴1)𝑃(𝐴1)+𝑃(𝐵|𝐴2)𝑃(𝐴2)+…+𝑃(𝐵|𝐴𝑛)𝑃(𝐴𝑛)
𝑃(𝐵)=∑𝑖=1𝑛𝑃(𝐴𝑖)𝑃(𝐵|𝐴𝑖)
贝叶斯公式推断

根据条件概率和全概率公式，可以得到贝叶斯公式如下：
𝑃(𝐴|𝐵)=𝑃(𝐴)𝑃(𝐵|𝐴)𝑃(𝐵)
转换为分类任务的表达式：
𝑃(类别|特征)=𝑃(类别)𝑃(特征|类别)𝑃(特征)
𝑃(𝐴𝑖|𝐵)=𝑃(𝐴𝑖)𝑃(𝐵|𝐴𝑖)∑𝑛𝑖=1𝑃(𝐴𝑖)𝑃(𝐵|𝐴𝑖)
P(A)称为”先验概率”（Prior probability），即在B事件发生之前，我们对A事件概率的一个判断。

P(A|B)称为”后验概率”（Posterior probability），即在B事件发生之后，我们对A事件概率的重新评估。

P(B|A)/P(B)称为”可能性函数”（Likely hood），这是一个调整因子，使得预估概率更接*真是概率。

朴素贝叶斯算法
输入：训练数据𝐷={(𝑥1,𝑦1),(𝑥2,𝑦2),⋯,(𝑥𝑁,𝑦𝑁)}，其中𝑥𝑖=(𝑥(1)𝑖,𝑥(2)𝑖,⋯,𝑥(𝑛)𝑖)，𝑥(𝑗)𝑖是第𝑖个样本的第𝑗个特征，𝑥(𝑗)𝑖∈{𝑎𝑗1,𝑎𝑗2,⋯,𝑎𝑗𝑆𝑗}𝑇，𝑎𝑗𝑙是第𝑗个特征可能取的第𝑙个值，𝑗=1,2,⋯,𝑛，𝑙=1,2,⋯,𝑆𝑗，𝑦𝑖∈{𝑐1,𝑐2,⋯,𝑐𝐾}；实例𝑥=(𝑥(1),𝑥(2),⋯,𝑥(𝑛))𝑇
输出：实例𝑥的分类

算法步骤如下：

计算先验概率即条件概率
𝑃(𝑌=𝑐𝑘)=∑𝑁𝑖=1𝐼(𝑦𝑖=𝑐𝑘)𝑁,𝑘=1,2,⋯,𝐾
𝑃(𝑋(𝑗)=𝑎𝑗𝑙|𝑌=𝑐𝑘)=∑𝑁𝑖=1𝐼(𝑥(𝑗)𝑖=𝑎𝑗𝑙,𝑦𝑖=𝑐𝑘)∑𝑁𝑖=1𝐼(𝑦𝑖=𝑐𝑘)
𝑗=1,2,⋯,𝑛;𝑙=1,2,⋯,𝑆𝑗;𝑘=1,2,⋯,𝐾

对于给定的实例𝑥=(𝑥(1),𝑥(2),⋯,𝑥(𝑛))𝑇，计算：
𝑃(𝑌=𝑐𝑘)∏𝑗=1𝑛𝑃(𝑋(𝑗)=𝑥(𝑗)|𝑌=𝑐𝑘),𝑘=1,2,⋯,𝐾

确定实例𝑥的类
𝑦=argmax𝑐𝑘𝑃(𝑌=𝑐𝑘)∏𝑗=1𝑛𝑃(𝑋(𝑗)=𝑥(𝑗)|𝑌=𝑐𝑘),𝑘=1,2,⋯,𝐾

K*邻算法(KNN)

K-Nearest Neighbors是一个有监督学算法。该方法的主要思想是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻)的样本中的大多数属于某一个类别，则该样本也属于这个类别。即是给定一个训练数据集，对新的样本属于哪一类，在训练数据集中找到与该样本最邻*的K个样本,这K个样本的多数所属的类，即可认为新样本也属于这一类。
下面是K-Nearest Neighbors算法的可视化。

在这种情况下，我们有A类和B类数据点。我们想要预测星（测试数据点）属于哪一类。 如果我们考虑k值为3（3个最*的数据点），星将被预测属于B类。但是如果我们考虑k值为6，星将被预测属于A类。

从这个意义上讲，考虑k的值很重要。 但希望从这个图中，您应该了解K-最*邻居算法是什么。

KNN的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最*邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，通常k是不大于20的整数，最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

算法关键：

预测数据与样本数据之间的相关性，我们通过两者间的距离来衡量，距离*的比距离远的相关性强。计算距离的方法有很多种，这里列出较常用的两种。
欧几里得度量（ Euclidean Distance ）

又被称作出租车几何，用以标明两个点在标准坐标系上的绝对轴距总和
𝑑12=∑𝑘=1𝑛|𝑥1𝑘−𝑥2𝑘|
绿色线表示的是欧几里得距离，而其他红、蓝、黄色线表示的是曼哈顿距离
2. 距离排序
在这个计算的过程中，需要将最终的计算进行一个排序的。为下一步操作做好准备。
3. K的选择
很明显，对于这算法，K的选取决定了整个算法分类预测的准确性，可以说是其核心参数。从上面的例子也可以看出来，K=3和K=5得到的决然不同的结果的。
算法步骤:
（1）初始化距离
（2）计算待分类样本和每个训练集的距离
（3）排序
（4）选取K个最邻*的数据
（5）计算K个训练样本的每类标签出现的概率
（6）将待分类样本归为出现概率最大的标签，分类结束。
输入：训练数据集
𝑇=(𝑥1,𝑦1),(𝑥2,𝑦2),⋯,(𝑥𝑁,𝑦𝑁)
其中， 𝑥𝑖∈ ∈Rn为实例的特征向量， 𝑦𝑖∈y=𝑐1,𝑐2,⋯,𝑐𝐾 为实例的类别, 𝑖=1,2,⋯,𝑁 ；实例特征向量 𝑥 ；

输出：实例 𝑥 所属的类 𝑦
（1）根据给定的距离度量，在训练集 𝑇 中找出与 𝑥 最*邻的 𝑘 个点，涵盖这 𝑘 个点的 𝑥 的邻域记作 𝑁𝑘(𝑥) ；
（2）在 𝑁𝑘(𝑥) 中根据分类决策规则（如多数表决）决定 𝑥 的类别 𝑦 ： 𝑦=argmax𝑐𝑗∑𝑥𝑖∈𝑁𝑘(𝑥)𝐼(𝑦𝑖=𝑐𝑗)，𝑖=1,2,⋯,𝑁；𝑗=1,2,⋯,𝐾

注：
K邻算法的特殊情况是 𝑘=1 的情形，称为最邻算法，对于输入的实例点（特征向量） 𝑥 ，最邻算法将训练数据集中与 𝑥 最邻点的类作为 𝑥 的类。
K*邻模型的特征空间一般是n维实数向量空间 𝑅𝑛 ,使用的距离是欧式距离。

线性支持向量机

SVM 最早是由 Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 在1963年提出，目前的版本(soft margin)是由 Corinna Cortes 和 Vapnik 在1993年提出，并在1995年发表。深度学（2012）出现之前，SVM 被认为机器学中*十几年来最成功，表现最好的算法。

支持向量机（SVM）是一种二类分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器。支持向量机还包括核技巧，这使它成为实质上的费线性分类器。支持向量机的学策略就是间隔最大化，可形式上化为一个求解凸二次规划的问题，即支持向量机的学算法就是求解凸二次规划的最优化算法。

线性可分支持向量机（也称为硬间隔支持向量机）：当训练数据线性可分时，通过硬间隔最大化，学得一个线性可分支持向量机。
线性支持向量机（也称为软间隔支持向量机），当训练数据*似线性可分时，通过软间隔最大化，学得一个线性支持向量机。
非线性支持向量机：当训练数据线性不可分时，通过使用核技巧以及软间隔最大化，学得一个非线性支持向量机。
支持向量与超平面

在了解svm算法之前，我们首先需要了解一下线性分类器这个概念。比如给定一系列的数据样本，每个样本都有对应的一个标签。为了使得描述更加直观，我们采用二维平面进行解释，高维空间原理也是一样。

举个例子，假设在一个二维线性可分的数据集中，如下图图A所示，我们要找到一个超平面把两组数据分开，这时，我们认为线性回归的直线或逻辑回归的直线也能够做这个分类，这条直线可以是图一B中的直线，也可以是图一C中的直线，或者图一D中的直线，但哪条直线才最好呢，也就是说哪条直线能够达到最好的泛化能力呢？那就是一个能使两类之间的空间大小最大的一个超平面。

这个超平面在二维平面上看到的就是一条直线，在三维空间中就是一个平面…，因此，我们把这个划分数据的决策边界统称为超平面。离这个超平面最*的点就叫做支持向量，点到超平面的距离叫间隔。支持向量机就是要使超平面和支持向量之间的间隔尽可能的大，这样超平面才可以将两类样本准确的分开，而保证间隔尽可能的大就是保证我们的分类器误差尽可能的小，尽可能的健壮。

点到超平面的距离公式

最大间隔的优化模型

现在我们已经知道了如何去求数据点到超平面的距离，在超平面确定的情况下，我们就能够找出所有支持向量，然后计算出间隔margin。每一个超平面都对应着一个margin，我们的目标就是找出所有margin中最大的那个值对应的超平面。因此用数学语言描述就是确定w、b使得margin最大。这是一个优化问题其目标函数可以写成：
max𝑤,𝑏(𝑚𝑖𝑛[𝑦∗(𝑤𝑇𝑥+𝑏)]1||𝑤||)
类别标签用-1、1，是为了后期方便𝑦∗(𝑤𝑇𝑥+𝑏)的标识和距离计算；如果𝑦∗(𝑤𝑇𝑥+𝑏)>0表示预测正确，否则预测错误。

𝐿(𝑤,𝑏,𝛼)=12∗||𝑤||2+∑𝑖=1𝑛𝛼𝑖∗[1−𝑦∗(𝑤𝑇𝑥+𝑏)]
求L关于求偏导数得：
{∂𝐿(𝑤,𝑏,𝛼)∂𝑤=0⇒𝑤=∑𝑛𝑖=1𝛼𝑖𝑦𝑖𝑥𝑖∂𝐿(𝑤,𝑏,𝛼)∂𝑏=0⇒∑𝑛𝑖=1𝛼𝑖𝑦𝑖
带入计算得：
𝐿(𝛼)=12∑𝑖,𝑗,=1𝑛𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗−∑𝑖,𝑗=1𝑛𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗−𝑏∑𝑖,𝑗=1𝑛𝛼𝑖𝑦𝑖+∑𝑖=1𝑛𝛼𝑖=∑𝑖=1𝑛𝛼𝑖−12∑𝑖,𝑗=1𝑛𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗
现在转化到对偶问题的求解
𝑚𝑎𝑥𝐿(𝛼)𝑠.𝑡=∑𝑖=1𝑛𝛼𝑖−12∑𝑖,𝑗=1𝑛𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗
{∑𝑛𝑖,𝑗=1𝛼𝑖𝑦𝑖=0𝛼𝑖>0,𝑖=1,2…𝑛

到此，这里有个假设：数据必须是百分之百可分的。但是实际中的数据几乎都不那么”干净”，或多或少都会存在一些噪点。为此下面我们将引入了松弛变量来解决这种问题。

松弛变量(slack variable)

由上一节的分析我们知道实际中很多样本数据都不能够用一个超平面把数据完全分开。如果数据集中存在噪点的话，那么在求超平的时候就会出现很大问题。从下图中课看出其中一个蓝点偏差太大，如果把它作为支持向量的话所求出来的margin就会比不算入它时要小得多。更糟糕的情况是如果这个蓝点落在了红点之间那么就找不出超平面了。

因此引入一个松弛变量𝜉来允许一些数据可以处于分隔面错误的一侧。这时新的约束条件变为:
𝑦𝑖(𝑤𝑇𝑥𝑖+𝑏)≥1−𝜉𝑖𝑖=1,2…𝑛
式中𝜉的含义为允许第i个数据点允许偏离的间隔。如果让𝜉任意大的话，那么任意的超平面都是符合条件的了。所以在原有目标的基础之上，我们也尽可能的让𝜉的总量也尽可能地小。所以新的目标函数变为：
𝑚𝑖𝑛12||𝑤||2+𝐶∑𝑖=1𝑁𝜉𝑖
其中的C是用于控制”最大化间隔”和”保证大部分的点的函数间隔都小于1″这两个目标的权重。将上述模型完整的写下来就是：
𝑚𝑖𝑛12||𝑤||2+𝐶∑𝑖=1𝑁𝜉𝑖
𝑠.𝑡,𝜉≥0,𝑖=1,2…𝑛
𝑦𝑖(𝑤𝑇𝑥𝑖+𝑏)≥1−𝜉𝑖,𝑖=1,2…𝑛
常量C是 惩罚因子, 表示离群点的权重（用于控制”最大化间隔”和”保证大部分点的函数间隔小于1.0″ ）

𝑦∗(𝑤𝑇𝑥+𝑏)>1and 𝛼=0 (在边界外，就是非支持向量)
𝑦∗(𝑤𝑇𝑥+𝑏)=1and 0

我们看到，目标函数控制了离群点的数目和程度，使大部分样本点仍然遵守限制条件。例如：正类有10000个样本，而负类只给了100个（C越大表示100个负样本的影响越大，就会出现过度拟合，所以C决定了负样本对模型拟合程度的影响！，C就是一个非常关键的优化点。）

经过添加松弛变量的方法，我们现在能够解决数据更加混乱的问题。通过修改参数C，我们可以得到不同的结果而C的大小到底取多少比较合适，需要根据实际问题进行调节。

（1）线性可分支持向量机
输入：线性可分训练数据集𝑇={(𝑥1,𝑦1),(𝑥2,𝑥2),⋯,(𝑥𝑁,𝑦𝑁)}
输出：最大几何间隔的分离超平面和分类决策函数
算法步骤如下：
（1）构造并且求解约束最优化问题：
min𝛼⃗ 12∑𝑖=1𝑁∑𝑗=1𝑁𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗(𝑥𝑖·𝑥𝑗)−∑𝑖=1𝑁𝛼𝑖
𝑠.𝑡.∑𝑡=1𝑁𝛼𝑖𝑦𝑖=0
𝛼𝑖≥0,𝑖=1,2,⋯,𝑁
求解最优解𝛼⃗ ∗=(𝛼∗1,𝛼∗2,⋯,𝛼∗𝑁)𝑇
（2）计算
𝜔⃗ ∗=∑𝑖=1𝑁𝛼∗𝑖𝑦𝑖𝑥𝑖
同时选择𝛼∗的一个正的分量𝛼∗𝑗>0，计算
𝑏∗=𝑦𝑗−∑𝑖=1𝑁𝛼∗𝑖𝑦𝑖(𝑥𝑖·𝑥𝑗)
（3）由此得到最大几何分割分离超平面：𝜔⃗ ∗·𝑥+𝑏∗=0，以及分类决策函数𝑓(𝑥⃗ )=𝑠𝑖𝑔𝑛(𝜔⃗ ∗·𝑥+𝑏∗)
（2）线性支持向量机

输入：线性可分训练数据集𝑇={(𝑥1,𝑦1),(𝑥2,𝑥2),⋯,(𝑥𝑁,𝑦𝑁)}和惩罚参数𝐶>0
输出：软间隔最大化分离超平面和分类决策函数
算法步骤如下：
（1）构造并且求解约束最优化问题：
min𝛼⃗ 12∑𝑖=1𝑁∑𝑗=1𝑁𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗(𝑥𝑖·𝑥𝑗)−∑𝑖=1𝑁𝛼𝑖
𝑠.𝑡.∑𝑡=1𝑁𝛼𝑖𝑦𝑖=0
𝐶≥𝛼𝑖≥0,𝑖=1,2,⋯,𝑁
求解最优解𝛼⃗ ∗=(𝛼∗1,𝛼∗2,⋯,𝛼∗𝑁)𝑇
（2）计算
𝜔⃗ ∗=∑𝑖=1𝑁𝛼∗𝑖𝑦𝑖𝑥𝑖
同时选择𝛼∗的一个正的分量𝐶>𝛼∗𝑗>0，计算
𝑏∗=𝑦𝑗−∑𝑖=1𝑁𝛼∗𝑖𝑦𝑖(𝑥𝑖·𝑥𝑗)
（3）由此得到最大几何分割分离超平面：𝜔⃗ ∗·𝑥+𝑏∗=0，以及分类决策函数𝑓(𝑥)=𝑠𝑖𝑔𝑛(𝜔⃗ ∗·𝑥+𝑏∗)
（3）非线性支持向量机
输入：线性可分训练数据集 𝑇={(𝑥1,𝑦1),(𝑥2,𝑥2),⋯,(𝑥𝑁,𝑦𝑁)} 和惩罚参数 𝐶>0
输出：分类决策函数
算法步骤如下：
（1）选择适当的核函数 𝐾(𝑥,𝑧) 并且求解约束最优化问题：
min𝛼⃗ 12∑𝑖=1𝑁∑𝑗=1𝑁𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝐾(𝑥𝑖,𝑥𝑗)−∑𝑖=1𝑁𝛼𝑖
𝑠.𝑡.∑𝑡=1𝑁𝛼𝑖𝑦𝑖=0
𝐶≥𝛼𝑖≥0,𝑖=1,2,⋯,𝑁
求解最优解 𝛼⃗ ∗=(𝛼∗1,𝛼∗2,⋯,𝛼∗𝑁)𝑇
（2）计算
𝜔⃗ ∗=∑𝑖=1𝑁𝛼∗𝑖𝑦𝑖𝑥𝑖
同时选择 𝛼∗ 的一个正的分量 𝐶>𝛼∗𝑗>0 ，计算
𝑏∗=𝑦𝑗−∑𝑖=1𝑁𝛼∗𝑖𝑦𝑖𝐾(𝑥𝑖,𝑥𝑗)
（3）构造分类决策函数 𝑓(𝑥⃗ )=𝑠𝑖𝑔𝑛(∑𝑁𝑖=1𝛼∗𝑖𝑦𝑖𝐾(𝑥𝑖,𝑥)+𝑏∗)

非线性支持向量机

SVM 最早是由 Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 在1963年提出，目前的版本(soft margin)是由 Corinna Cortes 和 Vapnik 在1993年提出，并在1995年发表。深度学（2012）出现之前，SVM 被认为机器学中*十几年来最成功，表现最好的算法。

支持向量机(support vector machines,SVM)是一种二分类模型，当然如果进行修改之后也是可以用于多类别问题的分类。它的基本类型是定义在特征空间上的间隔最大的线性分类器。支持向量机可以通过核技巧，转换成非线性分类器。它属于二分类算法，可以支持线性和非线性的分类。其主要思想为找到空间中的一个更够将所有数据样本划开的超平面，并且使得本本集中所有数据到这个超平面的距离最短。实际上有许多条直线（或超平面）可以将两类目标分开来，我们要找的其实是这些直线（或超平面）中分割两类目标时，有最大距离的直线（或超平面）。我们称这样的直线或超平面为最佳线性分类器。

支持向量回归（SVR）算法

支持向量机不仅用于分类问题，也可以用于回归问题。给定训练数据集𝑇={(𝑥1,𝑦1),(𝑥2,𝑦2),⋯(𝑥𝑁,𝑦𝑁)},𝑥𝑖∈∈ℝ𝑛,𝑦𝑖∈∈ℝ,𝑖=1,2,⋯,𝑁，其中𝑥𝑖=(𝑥(1)𝑖,𝑥(2)𝑖,⋯,𝑥(𝑛)𝑖)𝑇。对于样本(𝑥𝑖,𝑦𝑖)通常根据模型输出𝑓(𝑥𝑖)与真实值𝑦𝑖之间的差别来计算损失，当且仅当𝑓(𝑥−𝑖)=𝑦𝑖时损失才为零。而支持向量回归的基本思路时：允许输出𝑓(𝑥𝑖)与真实值𝑦𝑖之间最多有𝜀的偏差。即仅当|𝑓(𝑥𝑖)−𝑦𝑖|>𝜀时才计算损失。当|𝑓(𝑥𝑖)−𝑦𝑖|≤𝜀时，才认为预测正确。

用数学语言描述SVR问题：

min𝜔,𝑏12∥𝜔∥22+𝐶∑𝑖=1𝑁𝐿𝜀(𝑓(𝑥𝑖)−𝑦𝑖)
其中𝐶≥0为惩罚项常数，𝐿𝜀为损失函数，𝐿𝜀定义为：
𝐿𝜀(𝑧)={0|𝑧|−𝜀|𝑧|≤𝜀|𝑧|>𝜀
支持向量回归

输入：线性可分训练数据集𝑇={(𝑥1,𝑦1),(𝑥2,𝑥2),⋯,(𝑥𝑁,𝑦𝑁)}、选择适当的𝜀>0和惩罚参数𝐶>0
输出：决策函数
算法步骤如下：
（1）构造并求解最优化问题：
max𝛼⃗ ,𝛼⃗ ̂ ∑𝑖=1𝑁[𝑦𝑖(𝛼̂ 𝑖−𝛼𝑖)−𝜀(𝛼̂ 𝑖+𝛼𝑖)]−12∑𝑖=1𝑁∑𝑗=1𝑁(𝛼̂ 𝑖−𝛼𝑖)(𝛼̂ 𝑗−𝛼𝑗)𝑥𝑖·𝑥𝑗
𝑠.𝑡.∑𝑡=1𝑁(𝛼̂ 𝑖−𝛼𝑖)=0
0≤𝛼𝑖,𝛼̂ 𝑖≤𝐶,𝑖=1,2,⋯,𝑁
求解最优解𝛼⃗ ∗=(𝛼∗1,𝛼∗2,⋯,𝛼∗𝑁)𝑇,𝛼⃗ ̂ ∗=(𝛼̂ ∗1,𝛼̂ ∗2,⋯,𝛼̂ ∗𝑁)𝑇
（2）在𝛼⃗ ∗=(𝛼∗1,𝛼∗2,⋯,𝛼∗𝑁)𝑇中，找到𝛼∗的一个正的分量𝐶>𝛼∗𝑗>0，则有
𝑏∗=𝑦𝑗+𝜀−∑𝑖=1𝑁(𝛼̂ ∗𝑖−𝛼∗𝑖)𝑥𝑖·𝑥𝑗
（3）构造决策函数𝑓(𝑥)=∑𝑁𝑖=1(𝛼̂ ∗𝑖−𝛼∗𝑖)𝑥𝑖·𝑥+𝑏∗
更进一步，如果考虑使用核技巧，给定核函数𝐾(𝑥𝑖,𝑥)，则SVR可以表示为：
𝑓(𝑥)=∑𝑖=1𝑁(𝛼̂ ∗𝑖−𝛼∗𝑖)𝐾(𝑥𝑖,𝑥)+𝑏∗

决策树算法

决策树(decision tree)是功能强大而且相当受欢迎的分类和预测方法，它是一种有监督的学*算法，以树状图为基础，其输出结果为一系列简单实用的规则，故得名决策树。决策树就是一系列的if-then语句，决策树可以用于分类问题，也可以用于回归问题。本文主要讨论分类决策树。

决策树模型基于特征对实例进行分类，它是一个树状结构。决策树的优点是可读性强，分类速度快。学决策树时，通常采用损失函数最小化原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。

训练集用𝐷表示，𝑇表示一棵决策树
假设，给定训练集𝐷={(𝑥1,𝑦1),(𝑥2,𝑦2),⋯,(𝑥𝑁,𝑦𝑁)}，其中𝑥𝑖=(𝑥(1)𝑖,𝑥(2)𝑖,⋯,𝑥(𝑛)𝑖)为输入实例，𝑛为特征个数；𝑦𝑖∈{1,2,⋯,𝐾}为类标记，𝑖=1,2,⋯,𝑁；𝑁为样本容量基尼指数

假设有𝐾个分类，样本点属于第𝑘类的概率为𝑝𝑘=𝑃(𝑌=𝑐𝑘)。则概率分布的基尼指数定义为
𝐺𝑖𝑛𝑖(𝑝)=∑𝑘=1𝐾𝑝𝑘(1−𝑝𝑘)=1−∑𝑘=1𝐾𝑝2𝑘
对于二分类的问题，若样本点属于第一个类的概率是𝑝，则概率分布的基尼指数为
𝐺𝑖𝑛𝑖(𝑝)=2𝑝(1−𝑝)
对于给定的样本集合𝐷，其基尼指数为
𝐺𝑖𝑛𝑖𝑛(𝐷)=1−∑𝑘=1𝐾(|𝐶𝑘||𝐷|)2
这里，𝐶𝑘是𝐷中属于第𝑘类的样本子集，𝐾是类的个数

如果样本集合𝐷根据特征𝐴是否取某一可能值𝑎被分割成𝐷1,𝐷2两部分，即

𝐷1={(𝑥,𝑦)∈𝐷|𝐴(𝑥)=𝑎},𝐷2=𝐷−𝐷1
则在特征𝐴的条件下，集合𝐷的基尼指数定义为
𝐺𝑖𝑛𝑖(𝐷,𝐴)=|𝐷1||𝐷|𝐺𝑖𝑛𝑖(𝐷1)+|𝐷2||𝐷|𝐺𝑖𝑛𝑖(𝐷2)
基尼指数𝐺𝑖𝑛𝑖(𝐷)表示集合𝐷的不确定性，基尼指数𝐺𝑖𝑛𝑖(𝐷,𝐴)表示经𝐴=𝑎分割后集合𝐷的不确定性。基尼指数值越大，样本集合的不确定性也就越大。

CART生成算法
输入：训练数据集𝐷，停止计算的条件；
输出：CART决策树

根据训练数据集，从根节点开始，递归敌对每个结点进行以下的操作，构建二叉决策树：
（1）设结点的训练数据集为𝐷，计算现有特征对该数据集的基尼指数。此时，对每个特征𝐴，对其可能去的每个值𝑎，根据样本点对𝐴=𝑎测试为”是”或”否”将𝐷分割成𝐷1,𝐷2两部分,利用𝐺𝑖𝑛𝑖(𝐷,𝐴)=|𝐷1||𝐷|𝐺𝑖𝑛𝑖(𝐷1)+|𝐷2||𝐷|𝐺𝑖𝑛𝑖(𝐷2)计算𝐴=𝑎时的基尼指数。
（2）在所有可能的特征𝐴以及它们所有可能的切分点𝑎中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子节点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归地调用（1），（2），直到满足停止条件。
（4）生成CART决策树
CART剪枝算法
输入：CART算法生成的决策数 𝑇0 ；
输出：最优决策树 𝑇𝛼
（1）设 𝑘=0,𝑇=𝑇0
（2）设 𝛼=+∞
（3）自下而上地对个内部结点 𝑡 计算 𝐶(𝑇𝑡) ， |𝑇𝑡| 以及
𝑔(𝑡)=𝐶(𝑡)−𝐶(𝑇𝑡)|𝑇𝑡|−1
𝛼=𝑚𝑖𝑛(𝛼,𝑔(𝑡))
这里， 𝑇𝑡 表示以 𝑡 为根结点的子树， 𝐶(𝑇𝑡) 是对训练数据的预测误差， |𝑇𝑡| 是 𝑇𝑡 的叶节点个数， 𝑔(𝑡) 表示剪枝后整体损失函数减少的程度
（4）对 𝑔(𝑡)=𝛼 的内部结点 𝑡 进行剪枝，并对叶结点 𝑡 以多数表决法觉定其类，得到树 𝑇
（5）设 𝑘=𝑘+1,𝛼𝑘=𝛼,𝑇𝑘=𝑇
（6）如果 𝑇𝑘 不是由根结点及两个叶结点构成的树，则回到步骤（2）；否则令 𝑇𝑘=𝑇𝑛
（7）采用交叉验证法在子树序列 𝑇0,𝑇1,⋯,𝑇𝑛 中选取最优子树 𝑇𝛼

基于ID3的决策树分类

决策树是属于机器学监督学分类算法中比较简单的一种，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 是通过一系列规则对数据进行分类的过程。

决策树是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对样本进行分类的过程。目前常用的决策树算法有ID3算法、改进的C4.5算法和CART算法。
在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法的核心是信息墒，在决策树各级节点上选择属性时，用信息增益作为属性的选择标准，使得在每一个非节点进行测试时，能获得关于被测试记录最大的类别信息。认为增益高的是好属性，易于分类。每次划分选取信息增益最高的属性作为划分标准，进行重复，直至生成一个能完美分类训练样历的决策树。
具体方法是：从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
简单理解：

ID3的特点：
优点：理论清晰，方法简单，学能力较强
缺点*
信息增益的计算比较依赖于特征数目比较多的特征
ID3为非递增算法
ID3为单变量决策树
抗糙性差
熵和信息增益

信息熵

在概率论中，信息熵给了我们一种度量不确定性的方式，是用来衡量随机变量不确定性的，熵就是信息的期望值。若待分类的事物可能划分在N类中，分别是 𝑥1,𝑥2,……,𝑥𝑛，每一种取到的概率分别是𝑝1,𝑝2,……,𝑝𝑛，那么数据集D的熵就定义为：
𝐻(𝐷)=−∑𝑖=1|𝑛|𝑝𝑖𝑙𝑜𝑔𝑝𝑖
从定义中可知：0≤𝐻(𝐷)≤𝑙𝑜𝑔(𝑛)
当随机变量只取两个值是，即D的分布为𝑃=(𝐷=1)=𝑝,𝑃(𝐷=0)=1−𝑝,0≤𝑝≤1，则熵为：
𝐻(𝐷)=−𝑝𝑙𝑜𝑔2𝑝−(1−𝑝)𝑙𝑜𝑔2(1−𝑝)
熵值越高，随机变量的不确定性越大，则数据混合的种类越高，其蕴含的含义是一个变量可能的变化越多（反而跟变量具体的取值没有任何关系，只和值的种类多少以及发生概率有关），它携带的信息量就越大。

条件熵（局部，现象发生的前提下的熵）
假设有随机变量(𝑋,𝑌)，其联合概率分布为：

𝑃(𝑋=𝑥𝑖,𝑌=𝑦𝑖)=𝑝𝑖𝑗，𝑖=1,2,…,𝑛，𝑗=1,2,…𝑚
则条件熵𝐻(𝑌|𝑋)表示在已知随机变量X的条件下随机变量Y的不确定性，其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望：

𝐻(𝑌|𝑋)=∑𝑖=1𝑛𝑝𝑖𝐻(𝑌|𝑋=𝑥𝑖)
当信息熵和条件熵中的概率由数据估计得到时（如极大似然估计），所对应的信息熵熵与条件熵分别称为经验熵和经验条件熵。若概率为0，令0log0=0

信息增益

定义：信息增益(information gain)表示得知特征X的信息后，而使得Y的不确定性减少的程度。定义为:

𝐺𝑎𝑖𝑛(𝐷,𝐴)=𝐻(𝐷)−𝐻(𝐷|𝐴)
即集合D的经验熵𝐻(𝐷)与特征A给定条件下D的经验条件熵𝐻(𝐻|𝐴)之差。

理解：选择划分后信息增益大的作为划分特征，说明使用该特征后划分得到的子集纯度越高，即不确定性越小。因此我们总是选择当前使得信息增益最大的特征来划分数据集。

缺点：信息增益偏向取值较多的特征（原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分后的熵更低，即不确定性更低，因此信息增益更大）。

信息增益准则的特征选择方法:

对数据集D，计算每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。

ID3算法和决策树的流程:

数据准备：需要对数值型数据进行离散化
ID3算法构建决策树：
如果数据类别完全相同，则停止划分。
否则，继续划分：
计算信息墒和信息增益来选择最好的数据集划分方法
划分数据集
创建分支节点
对每个分支进行判定类别相同。相同停止划分，不同则按照上述方法进行划分。

K均值聚类算法（K-Means）

给定样本集𝐷=𝑥1,𝑥2，⋯,𝑥𝑁，其中𝑥𝑖=(𝑥(1)𝑖,𝑥(2)𝑖,⋯,𝑥(𝑛)𝑖)假设聚类的簇划分𝒞=𝐶1,𝐶2,⋯,𝐶𝐾。K-Means算法的目标是最小化平方误差。

现在要求最优化问题：

min𝒞∑𝑘=1𝐾∑𝑥𝑖∈𝐶𝑘∥𝑥𝑖−𝜇𝑘∥22
其中𝜇𝑘=1|𝐶𝑘|∑𝑥𝑖∈𝐶𝑘𝑥𝑖
该问题的求解需要考察样本集合𝐷的所有可能的簇划分。K-Means算法采用贪心策略，通过迭代优化来*似求解。其原理为：K-Means算法首先假设一组向量作为所有簇的簇均值向量，然后根据假设的簇均值向量给出了数据集D的一个簇划分，再根据这个簇划分来计算真实的簇均值向量

如果真实的簇均值向量等于假设的簇均值向量，则说明假设正确。根据假设簇均值向量给出的数据集D的一个簇划分确实是原问题的解
如果真实的簇均值向量不等于假设的簇均值向量，则可以将真实的簇均值向量作为新的假设簇均值向量，继续求解。
K-Means算法的策略是：样本离哪个簇的簇均值向量*，则该样本就划归到那个簇

输入：样本集 𝐷={𝑥1,𝑥2，⋯,𝑥𝑁} ；聚类簇数 𝐾
输出：簇划分 𝒞
算法步骤：

从 𝐷 中随机选择 𝐾 个样本作为初始簇均值向量 𝜇1,𝜇2,⋯,𝜇𝐾
重复迭代直到算法收敛，迭代内容如下:
初始化阶段：取 𝐶𝑘=𝜙,𝑘=1,2,⋯,𝐾
划分阶段：令 𝑖=1,2,⋯,𝑁
计算 𝑥𝑖 的簇标记如下：
𝜆𝑖=argmin𝑘∥𝑥𝑖−𝜇𝑘∥2,𝑘∈1,2,⋯,𝐾

然后将样本 𝑥𝑖 划入相应的簇：
𝐶𝜆𝑖=𝐶𝜆𝑖⋃{𝑥𝑖}

重计算阶段：计算 𝜇̂ 𝑘=1|𝐶𝑘|∑𝑥𝑖∈𝐶𝑘𝑥𝑖
终止条件判断：

如果对所有的 𝑘∈1,2,⋯,𝐾 ,都有 𝜇̂ 𝑘=𝜇𝑘 ，则算法收敛，终止迭代；否则重复制 𝜇𝑘=𝜇̂ 𝑘

K-Mediods算法

k-means算法对于异常值十分敏感，因为具有极大值的对象可能会产生严重扭曲的数据分布。因此我们可以使用 k-medoids算法，它是集群中位于最中心的对象，而不是将集群中的平均值作为参考点。因此，分区的方法仍然可以基于最小化每个对象与其参考点之间的不相似程度之和的原理来进行。这构成了k-medoids方法的基础。

聚类算法可以将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个”簇”(cluster)，通过这样的划分，每个簇可能对应于一些潜在的概念或类别。也可以对数据进行数据归约，即在尽可能保证数据完整的前提下，减少数据的量级，以便后续处理。也可以对聚类数据结果直接应用或分析。

聚类算法可以被分为那么几种，比如基于划分方法的、基于层次方法的、基于密度方法的、基于网格方法的、基于模型方法的；K-mediods算法就是基于划分方法的一种聚类算法，确切的说，是对K-means算法的一种改进算法。本章节将会介绍K-mediods算法。

关于K 中心点算法（ K-medoids ）正好能解决 k-means 算法中的 “噪声”敏感这个问题。解决过程如下：

我们得介绍下 k-means 算法为什么会对”噪声”敏感。K-means 寻找质点的过程中，对某类簇中所有的样本点维度求平均值，即获得该类簇质点的维度。当聚类的样本点中有”噪声”（离群点）时，在计算类簇质点的过程中会受到噪声异常维度的干扰，造成所得质点和实际质点位置偏差过大，从而使类簇发生”畸变”。例子如下：

类簇 𝐶1中已经包含点 𝐴(1,1)、𝐵(2,2)、𝐶(1,2)、𝐷(2,1) 假设 𝑁(100,100)为异常点，当它纳入类簇𝐶1时，计算质点

𝐶𝑒𝑛𝑡𝑟𝑜𝑖𝑑((1+2+1+2+100)/5,(1+2+2+1+100)/5)=𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑(21,21)
此时可能造成了类簇𝐶1质点的偏移，在下一轮迭代重新划分样本点的时候，将大量不属于类簇 C1 的样本点纳入，因此得到不准确的聚类结果。

为了解决该问题， K 中心点算法（ K-medoids ）提出了新的质点选取方式，而不是简单像 k-means 算法采用均值计算法。在 K 中心点算法中，每次迭代后的质点都是从聚类的样本点中选取，而选取的标准就是当该样本点成为新的质点后能提高类簇的聚类质量，使得类簇更紧凑。该算法使用绝对误差标准来定义一个类簇的紧凑程度。

K-medoids对噪声和孤立点不敏感，但是事情都具有两面性，这种聚类准确性的提高是牺牲聚类时间来实现的，不难看出K-medoids需要不断的找出每个点到其他所有点的距离的最小值来修正聚类中心，这大大加大了聚类收敛的时间。但K-medoids对于大规模数据聚类就显得力不从心，只能适应较小规模的数值聚类。

K-mediods算法处理过程

首先，随机选择k个对象作为初始的k个簇的代表点，将其余对象按与代表点对象的距离分配到最*的簇；

然后，反复用非代表点来代替代表点，以改进聚类质量。(用一个代价函数来估计聚类质量，该函数度量对象与代表点对象之间的平均相异度。)

目标函数仍然可以采用平方误差准则。

• 输入：n个对象的数据库，期望得到的k个聚类簇
• 输出：k个簇，使所有对象与其所属簇中心点的偏差总和最小化

方法：

层次聚类算法

层次聚类的应用广泛，核心思想是通过对数据集按照层次，把数据分到不同层的簇，从而形成一个树形的聚类结构。层次聚类算法可以揭示数据的分层结构，在树形结构上不同层次进行划分，可以得到不同粒度的聚类结果。按照层次聚类的过程分为自底向上的聚合聚类和自顶向下的分裂聚类。

本实验主要介绍的是自底向上的层次聚类–凝聚法(AGglomerative NESting,AGNES)

AGENS算法原理：AGENS首先将数据集中的每个样本看做一个厨师的聚类簇，然后在不断地找出距离最*的两个聚类簇进行合并。就这样不断地合并直到达到预设的聚类簇的个数。

算法描述:

输入：

算法步骤如下:

初始化：将每个样本都作为一个簇
𝐶𝑖={𝑥𝑖},𝑖=1,2,⋯,𝑁

迭代，终止条件为聚类簇的数量为K。迭代过程如下：
计算聚类簇之间的距离，找出距离最*的两个簇，将这两个簇合并。

密度聚类算法

基于密度的聚类算法利用密度思想，将样本中的高密度区域（及样本点分布稠密的区域）划分为簇，将簇看作是样本空间中被稀疏区域（噪声）分隔开的稠密区域。这一算法的主要目的是过滤样本空间中的稀疏区域，获取稠密区域作为簇。基于密度的聚类算法是根据密度而不是距离来计算样本相似度，所以基于密度的聚类算法能够用于挖掘任意形状的簇，并且能够有效过滤掉噪声样本对于聚类结果的影响。DBSCAN是一种著名的密度聚类算法。

DBSCAN采用基于中心的密度定义，样本的密度通过核心对象在𝜀半径内的样本点个数（包括自身）来估计。DBSCAN算法基于邻域来描述样本的密度，输入数据集𝐷={𝑥1,𝑥2,⋯,𝑥𝑁}，其中𝑥𝑖=(𝑥(1)𝑖,𝑥(2)𝑖,⋯,𝑥(𝑛)𝑖)，参数(𝜀,𝑀𝑖𝑛𝑃𝑡𝑠)刻画邻域的样本分布密度，其中，𝜀表示样本的邻域距离阈值，𝑀𝑖𝑛𝑃𝑡𝑠表示对于某一样本𝑝，其𝜀-邻域中样本个数的阈值。

属性定义

DBSCAN算法的簇定义：给定邻域参数(𝜀,𝑀𝑖𝑛𝑃𝑡𝑠)，一个簇𝐶⊆𝐷是满足下列性质的非空样本子集：

连接性：若𝑥𝑖∈𝐶,𝑥𝑗∈𝐶，则𝑥𝑖∼𝑥𝑗
最大性：若𝑥𝑖∈𝐶，且𝑥𝑖⇝𝑥𝑗，则𝑥𝑗∈𝐶。
一个簇是由密度可达关系导出的最大的密度相连样本集合

DBSCAN算法思想：

若𝑥为核心对象，则𝑥密度可达的所有样本组成的集合记作𝑋={𝑥′∈𝐷|𝑥⇝𝑥′}，可以证明𝑋就是满足连接性和最大性的簇。于是DBSCAN算法首先任选数据集中的一个核心对象作为种子，在由此出发确定相应的聚类簇。
算法
DBSCAN算法如下：

• 输入：数据集 𝐷={𝑥1,𝑥2,⋯,𝑥𝑁} ，其中 𝑥𝑖=(𝑥(1)𝑖,𝑥(2)𝑖,⋯,𝑥(𝑛)𝑖) ，参数 (𝜀,𝑀𝑖𝑛𝑃𝑡𝑠)
• 输出：簇划分

算法步骤：

初始化核心对象集合为空集： Ω=𝜙
寻找核心对象：遍历所有样本点 𝑥𝑖,𝑖=1,2,⋯,𝑁 ，计算 𝑁𝜀(𝑥𝑖) ，如果 |𝑁𝜀(𝑥𝑖)|≥𝑀𝑖𝑛𝑃𝑡𝑠 ，则 Ω=Ω⋃{𝑥𝑖}
迭代：以任一未访问的核心对象为出发点，找出有其密度可达的样本生成的聚类簇，直到所有核心对象都被访问为止。

Original: https://www.cnblogs.com/lang12/p/15597386.html
Author: Aurora*
Title: 数据挖掘之回归聚类算法总结