# 数据类型

数据集就是数据对象(记录，点，向量等等。。)的集合。数据对象用一组刻画对象的基本特性的属性
--变量 特征 字段 维
对象具有属性描述对象的特征特性，明确定义属性需要使用测量标度将属性与数值和符号相关联(属性并非数字和符号，为了表示属性的特征我们使用标度)
属性具有属性类型(测量标度类型)，属性类型告诉我们测量值哪些性质与属性基本一致。
一种指定属性类型的简单有效方法是确定对应属性基本性质的数值性质对于数值型给出下面四种

# 属性描述

区分属性的一种方法:根据可能取值的个数判断

• 离散属性
  • 有无限个值可以取，可以是分类的也可以是数值的
  • 二元属性只可以取真假TrueFalse
• 连续属性
  • 取实数值的属性如温度高度
  • 连续属性通常用浮点变量表示，实践中实数值只能用有限的精度 测量或表示
• 非对称属性
  • 出现非0值属性才是重要的只有非0值才重要的二元属性被称为非对称二元属性

# 数据集

记录数据，基于图形的数据，有序的数据(不止这三种)
重要特性

• 维度
  • 集中数据对象具有的属性数目，过高(多)会形成维灾难，数据分析重要动机之一即维规约(减少维度)
• 稀疏性
  • 重要的的数据占多少，有时候大部分都是不重要的，有特定针对稀疏的算法
• 分辨率
  • 不同分辨率下得到不同的结果肉眼看平整or显微镜看不平整
  • 数据的模式依赖于分辨率，分辨率太高模式看不出或掩埋在噪声里，太低模式不出现

# 记录数据

许多数据挖掘都假定数据集为记录(数据对象)的汇集，每个记录包含固定的(属性)数据字段。对于大部分情况，记录或数据字段之间没有明显的联系 ，并且每个对象(记录)具有相同的属性集。

• 事务数据或购物篮数据
  • 事务数据是特殊的记录数据每个记录涉及一系列的项例如购物篮数据-杂货店的关系。
  • 事务数据是项的集合的集族，也能视为记录的集合，其中记录的字段是非对称的属性，经常是二元的，离散或连续的。
• 数据矩阵
  • 数据集族中所有数据对象都具有相同的数据属性集。则数据对象可以看作多维空间的点m*n的矩阵即数据矩阵or模式矩阵
• 稀疏数据矩阵
  • 是数据矩阵的一种特殊情况，其属性类型相同且非对称，事务数据是仅含0-1元素的稀疏数据矩阵的例子
  • 文档数据 忽略词的次序,每个词都是向量的一个分量(属性)，值是分量出现的次数文档-词矩阵

# 基于图形的数据

图形捕获数据对象之间的联系，或数据本身用图像表示

• 带有对象之间联系的数据
  • 图像之间的联系带有重要信息，一般把数据对象映射为图的结点，节点（对象之间的联系一般用方向权重等表示）
• 具有图形对象的数据
  • 若对象具有结构(对象本身是由包含联系的子对象组成)通常用图形

# 有序的数据

涉及事件或空间的有序数据

• 时序数据(时间数据)
  • 记录的扩充每个记录包含着一个与之相关的时间，帮助我们分析不同时期数据的特征
• 序列数据
  • 序列数据通常是一个数据集合是各个实体的序列只考虑各项的位置而不考虑时间（例:DNA）
• 时间序列数据
  • 特殊的时序数据,m每个记录是一个时间序列(一段时间以来的测量序列)着重考虑时间自相关(在时间上靠近的对象在其他方面具有相似性)
• 空间数据
  • 具有空间属性(位置区域等)有空间自相关性(物理上靠近的对象在其他方面具有相似性)典形例子是科学和工程数据集，其数据自二维或三位网格上规则或不规则分布的点的测量或模型输出
• 非变量数据
  • 在统计时很多属性是相互联系影响的，不能分开来考虑，形成了非变量数据？

# 数据质量

数据收集时可能未有明确目的，可以纠正数据质量或者使用容忍低质量的算法.

# 测量误差和数据收集错误

理解概念:对于连续属性测量值与实际的差值为测量误差，遗漏数据对象与属性值或不当包含其他数据对象是收集错误(这两种可能系统地也可能随机出现)

• 噪声是测量误差的随机部分(参考Au处理的声音)，被扭曲或加入了谬误对象，通常包含与时间空间序列，设计鲁棒算法在噪声下产生可接受的结果
• 错误是更确定性现象的结果，照片上出现的条纹，确定性的失真称为伪像
• 精度是同一个量的重复测量值之间的接近程度，经常用值集合的标准差表示
• 偏移是测量值与被测量之间的系统变差,用值集合均值与测量值之间的差度量，只有通过外部手段能测量到的对象偏倚能确定
• 准确率被测量的测量值与实际值之间的接近程度
  • 依赖于精度和偏倚(两个一般化的概念so没有准确的公式)一个重要方面是有效数字。
• 离群点 在某种意义上具有不同于大部分的数据对象的特征的数据对象or对于该数据对象的典型值的异常值(注意区别噪声和离群点)
• 遗漏就是收集不全
  • 直接删除
  • 估计遗漏值 连续的-近邻平均属性值，分类的-近邻最高频属性值。
  • 设置默认值忽略
• 不一致的值。奇怪的错误例如人的身高是负数等等，可直接纠正或设置默认也可算法校验
• 重复数据，去重（数据库自带去重，numpy，panda，set）主键重复不同对象or相同对象

# 数据预处理

聚集，抽样，维规约，特征子集选择，特征创建，离散化二元化 都是使记录减少。变量变换。这些可以分为选择分析所需的数据对象属性或者创建/改变属性。降低成本提高质量

# 聚集

聚集是将两个或多个对象合并成单个对象(如将各地的商店销售情况聚集为单日销售情况)。在创建聚集事务时，定量属性(如价格)通常通过求和或求平均值进行聚集。定性属性可忽略或者汇总成一个
聚集是删除属性的过程，或是压缩特定属性 不同值个数 的过程(365天压缩为12个月)保持统计意义上不变，规模可能变化，缺点是失去了一些有趣的细节: )

• 为什么要聚合？
  • 减少处理所消耗的时间和内存算力等资源可以使用开销较大的数据挖掘算法
  • 可以改变分辨率，聚集范围转换标度
  • 对象或属性群的行为比单个个体更加稳定

# 抽样

有时候某个数据及分析的时候消耗过大，我们抽一些具有代表性的子集(压缩数据量)来进行分析。
若样本是具有代表性的则使用样本与使用整个数据集效果几乎一样。当样本近似的具有与原数据集相同的(我们感兴趣的)性质，则样本是具有代表性的

• 简单随机抽样(选取任何一个概率都相同)
  • 无放回抽样
  • 有放回抽样当数据量不大的时候两个差不多，有放回简单一些
  • 分层抽样(用于数据类型差别大，种类多)

• 渐进抽样 样本容量可能不好确定，因此要自适应或渐进抽样。先从一个小样本开始，直至样本容量足够大。虽然不需要一开始就确定容量但是需要一个合适的评估样本方法来确定容量已经足够大 例如在某一点之后增加趋势趋于稳定。

# 维规约

有些算法维度越低效果越好，维规约可以删除不相关的特征降低噪声。
避免维灾难，使模型更容易理解。
更容易让数据可视化
降低计算消耗
定义:创建新属性将一些旧属性合并在一起降低数据集维度。通过旧属性得到新属性规约称为特征（子集）选择

• 维灾难
  • 随着维度增加数据变得稀疏，分析变得困难，聚类分类算法准确度降低质量下降。
• 规约的线性代数技术
  • 有高维投影到低维空间(特别是对于连续数据)
  • 主成分分析（PAC）一种用于连续属性的线性代数技术，找出新属性是原属性的线性组合，是相互正交的，捕获了这些属性的最大变差
  • 奇异值分解是一种线性代数技术与PAC有关也用于维规约

# 特征子集选择

注意冗余特征（重复包含了一个或多个属性的信息）和不相关特征（没什么用的特征）理想的选择方法是：将所有可能的特征子集作为感兴趣的数据挖掘算法输入，选取最好的结果子集 大部分情况下因为数量级太大不太可能这样做，所以我们需要其他策略

• 嵌入方法
  • 例如决策树和分类器，在算法过程中，自动决定使用那些忽略那些
• 过滤方法
  • 独立于任务之外，使用算法前手动选择一次属性
• 包装方法
  • 把算法看作黑盒，列举很多个自己可能但不是全部

特征子集选择体系结构

• 子集评估度量值是否最优或超所给定的阈值
• 一个特定大小的子集是否已经得到，大小和评估标准是否同时达到
• 使用搜索策略得到的选择是否可以改进
• 迭代次数

特征加权

# 特征创建

由原来的属性创建新的属性集，以捕获信息

• 特征提取
  • 从原始数据创建特征，识别人脸从像素集合无法识别->与人脸边缘相关的边区域像素点。数据挖掘用于新领域关键任务之一就是开发新特征和新特征提取方法
• 数据映射到新空间
  • 使用不同视角 例：时间序列通常包含周期，单周期+噪声不多=容易检测；大量周期+大量噪声=难检测可以使用傅立叶变换，小波变换
• 特征构造
  • 可能包含信息但是不适合算法，由一个or多个原特征构造新特征。注意特征密度

# 离散化和二元化

有些算法特别是分类属性算法要求数据是分类属性。发现关联算法则要求是二元属性
二元化:将连续或离散属性变成一个或多个二元属性
一种分类属性二元化的简单技术如下：如果有m个分类值，则将每个原始值唯一地赋予区间0.m-1]中的一个整数。如果属性是有序的，则赋值必须保持序关系。(注意，即使属性原来就用整数表示，但如果这些整数不在区间[0，m-1]中，则该过程也是必需的。)然后，将这用个整数的每一个都变换成一个二进制数。由于需要n=[log 2 m]个二进位表示这些整数，因此要使用加个三元属性表示这些二进制数。 这样的变换可能导致复杂化，如无意之中建立了转换后的属性之间的联系。
离散化:连续属性变分类属性

用在分类或关联分析用得到的属性，效果取决于使用的算法。主要两个子任务

1. 决定需要多少个分类值
   • 将值排序后指定n-1个分割点分成n个区间
2. 如何将连续属性的值映射到这些分类值
   • 将一个区间的所有值映射到相同的分类值
   • 例子：按照成绩划分优良中差，确定分割点以及分割点的位置问题

非监督离散化
用于分类离散化方法的根本区别在于使用类信息（监督）还是不使用类信息（非监督）
不使用类信息比如等宽等深等频率等高，K均值聚类等，目测也行....？？
详见p36例2.12
监督离散化
记住目的并使用类标号(附加信息)。使用类信息就要涉及到熵书上给的定义
一种概念上的简单方法是以极大化区间纯度的方式确定分割点。然而，实践中这种方法可能需要人为确定区间的纯度和最小的区间大小。为了解决这一问题，一些基于统计学的方法用每个属性值来分隔区间，并通过合并类似于根据统计检验得出的相邻区间来创建较大的区间。基于熵的方法是最有前途的离散化方法之一，我们将给出一种简单的基于篇的方法。
熵是数据集不确定因素的大小首先，需要定义熵（entropy）。设k是不同的类标号数，mi是某划分的第i个区间中值的个数，而mij是区间i中类的值的个数。第i个区间的熵ei由如下等式给出:

其中pij=mij/mi是第i个区间中类j的概率（值的比例）

# 过多值的分类属性

• 如果是序数属性，可以使用类似于处理连续属性的技术，减少属性个数。
• 如果是标称，就要值聚集(按照特定领域知识聚集)，属性合并成组。

# 相似性和相异性的度量

许多情况下计算出相似性相异性几乎就不再使用原始数据了。
相关和欧几里得距离度量(类似于时间序列的稠密数据)，Jaccard和余弦相似性度量（适用于类似于文档的稀疏数据）

# 定义

• 相似度是这两个对象相似程度的数值度量，越相似相似度越高，非负，通常取(不相似) [0,1] (完全相似)
• 相异度是这两个对象差异程度的数值度量，越相似相异度越低，常用距离作同义词，有时取[0,1]有时取[0,+∞]

# 变换

通过手段把相似度转换为相异度，或者反向转换。
相似相异度可能很好转换(见p39例子)，但是邻近度不好转,需要非线性变换,值之间不再具有相同的联系，邻近度度量的含义可能发生了转变。
一般来说任何单调减函数都可以进行这两者之间变换。

# 简单属性之间的相似度相异度

具有多属性的对象之间的相似度相异度一般用单个属性的邻近度组合来定义，所以着重看单个的。
标称属性之间没什么难的，直接进行值匹配要么有要么没有。对于具有单个序数属性的对象，必须考虑序信息，量化序之间的距离，这些序同城会被映射到0或1开始的连续整数。并且时常要考虑序数之间的区间比率值。
不要无脑对应，两个序数之间的距离通常不是等价的
对于区间或比率属性，两个对象之间的相异性的自然度量是他们的值之差的绝对值。区间、比率属性相似度常常转为相异度。

属性类型	相异度	相似度
标称的
序数的	d=│x-y│/（n-1） 值映射到整数0~n-1 n是值的个数	s=1-d
区间比率的	d=│x-y│

# 数据对象之间的相异度

距离
在高维空间中xy两点的 欧氏距离(欧几里得距离) d:

• r=1，城市街区（也称曼哈顿、出租车、L范数）距离。一个常见的例子是汉明顿距（Hammingdisance）它是两个具有二元属性的对象(即两个二元向量)之间不同的二进制位个数

• r=2，欧儿里得距离（L2范数）。

• r=∞上确界(Lmax或L∞范数）距离。这是对象属性之间的最大距离。更正式地，L距离由下公式定义:

  
  参数r和属性数n 不要混淆,注意表2-10和表2-11和表2-8数据的L1，Lmax邻近度矩阵。
  欧氏距离，闵可夫斯基距离的众所周知(为什么我就不知道，叹气~

• 非负性。（a）对于所有x和y，d（x，y）≥0，（b）仅当x=y时d（x，y）=0。

• 对称性。对于所有x和y，d（x，y）=d（y，x）。

• 三角不等式。对手所有x，y和z，d（x,z）≤d（x，y）+d(y，z）

如果满足了上述的三个属性则可以被称之为 度量，有时候两个属性之间不一定是度量，但这个距离也很有用p42，p43例2.14，2.15

# 数据对象之间的相似度

对于相似度三角不等式通常不成立，对称性和非负性一般成立。如果s(x,y)是数据点x和y之间的相似度，相似度通常具有以下典型性质:

• 仅当x=y时，s（x，y）=1（0<=s<=1）
• 对所有x，y，s（x，y）=s（y，x）

邻近性度量

两个仅包含二元属性的对象之间的相似性度量也称为相似系数取0-1(完全相似) 对象x，y由n个二元属性组成
简单匹配系数SMC

Jaccard系数

余弦相似度
通常文档用向量表示，向量的每一个属性代表一个特定的词(术语)，在文章中出现的频率，分词要用不同的手段，常用词分割，空格分隔等等注意不同的文档长度和稀疏程度。 文档一般都是稀疏的且具有相对较少点非0属性值。相似性不能依赖共享的0个数。

TIP

点积定义

自己计算一下p45例2.18, 一定要做！

广义Jaccard系数
可用于文档数据，在二元属性的情况下可以规约为Jaccard系数。广义Jaccard系数几位EJ

皮尔森相关
4.相关性 两个具有二元变量或连续变量的数据对象之间的相关性是对象属性之间线性联系的度量。
（更一般属性之间的相关性计算可以类似地定义。）更准确地，两个数据对象x和y之间的皮尔森相关（Pearson's correlation）系数由下式定义：

相关性的图表示一般用 散布图

马氏距离
属性具有 不同的值域 时如何处理。（这种情况通常称作“变量具有不同的 尺度 。”）前面，使用欧几里得距离，基于年龄和收入两个属性来度量人之间的距高。 除非这两个属性是 标准化的，否则两个人之间的距离将被收入所左右。 一个相关的问题是，除值域不同外，当某些属性之间还相关时，如何计算距离。当属性相关、 具有不同的值域 （不同的 方差 ）、并且数据分布近似于 高斯（正态）分布 时，欧几里德距离的拓展，Mahalanobis 距离是有用的。具体地说，两个对象（问量）x和y之间的 Mahalanobis

# 组合属性之间的相似度相异度

一般方法

不同类型的时候，可以使用进行计算每个属性的相似度和相异度，使用 导致0-1之间的相似度方法 (什么方法？？？)组合这些相似度，总相似度一般为这些相似度的平均值。不过在非 对称属性 效果不好，如果非对称属性上都是0就可以忽略。
奇怪的公式计算异种对象之间的相似度

• 对于第k个属性，计算相似度s（x，y），在区间[0,1]中。
• 对于第k个属性，定义一个指示变量δk，如下：
  • δk=0,如果第k个属性是非对称属性并组两个对象在该属性上的值都是0，或者如果一个对象的第k个属性具有遗漏值
  • δk=1，否则
• 使用奇怪公式计算:
  

使用权值
某些时候某个属性比其它属性更重要，加权（有道理~
wk和为1的时候，奇怪公式变为:

带权闵可夫斯基距离:

# 选取正确的邻近度度量

数据类型相对应

• 稠密连续的数据
  • 距离度量，欧氏距离
• 连续属性
  • 属性差值
• 稀疏数据，包含非对称属性
  • 忽略0-0匹配的相似性度量。
  • 对于一复杂对象，相似度依赖于他们共有的性质数目，而不是都没有的。

# 第三章

# 期望均值

均值
均值其实是针对实验观察到的特征样本而言的。比如我们实验结果得出了x1,x2,x3…..xn这n个值，那么我们的均值计算是

样本均值





均值公式

期望
一个离散性随机变量的期望值是试验中每次可能的结果乘以其结果概率的总和，期望值像是随机试验在同样的机会下重复多次，所有那些可能状态平均的结果。与概率相关，常常与均值相等但数学含义不一样。

公式 期望=概率*结果 的总和

# 标准差方差

方差
在概率论和统计学中，一个随机变量的方差描述的是它的离散程度，也就是该变量离其期望值的距离。
公式:

性质:

• 方差不会是负的，因为次方计算为正的或为零：
• 一个常数随机变量的方差为零，且当一个数据集的方差为零时，其内所有记录皆为相同数值：
• 如果一个常数被加至一个数列中的所有变量值，此数列的方差不会改变：
• 如果所有数值被放大一个常数倍，方差会放大此常数的平方倍：

标准差

# 极值和极差

极值
极差

# 频率和众数

频率
频数就是在一个样本中某个数据出现的次数。
频率是 众数

# 中位数和截断均值

中位数
截断均值
对于有序数据，考虑值集的百分位数更有意义.
在一组数据所构成的样本集合中，对于其中的一个样本来说，小于这个样本的值的样本应该是整个样本集合的一个子集，
而且我们能够计算出小于这个样本值的样本数量在整个样本集合中占到百分之多少，那么这个样本的值就是这个百分数
所对应的百分位数
截断均值（trimmed mean）：指定0和100之间的百分位数p，丢弃高端和低端(p/2)%的数据，然后用常规的方法计算均值，所得的结果即是截断均值。
中位数是p = 100%时的截断均值，而标准均值是对应于p = 0%的截断均值。
值集的弥散或散布度量。这种度量表明属性值是否散布很宽，或者是否相对集中在单个点（如均值）附近。

# 协方差矩阵和相关矩阵

协方差矩阵
相关矩阵

# 卡方检验和极大似然估计

卡方检验
极大似然估计值

# 第四章

# 决策树

# 前置概念

分类就是通过学习得到一个目标函数f(x)可以把x属性集映射到一个预先的类标号y。目标函数也称分类模型，可用于描述性建模区分不同的对象和预测性建模通过属性描述未知的类标号。适用于二元或标称属性，对序数不太有效，不考虑属性之间的有序。
监督学习，需要用到训练集（已知类标号）和检验集（未知类标号）。常用k折交叉检验设k=10，1-9训练，10用于检验or 1-8训练，9检验。
分类模型的性能根据模型预测正确和错误的记录评估，使用混淆矩阵。进行分类模型的性能度量。

(～﹃～)~zZ	(￣_,￣ )	预测的类	预测的类
😃	(。・・)ノ	类=1	类=0
实际的类	类=1	f11	f10
实际的类	类=0	f01	f00

# 决策树归纳

• 根结点（root node）没有入边，但有零条或多条出边。
• 内部结点（internal node），有一条入边和两条或多条出边。
• 叶结点（leaf node）或终结点(terminal node)恰有一条入边，但没有出边。
• 在决策树中，每全叶结点都赋予一个类标号。非终结点（non-terminal node）（包括根结点和内部结点）包含属性测试系，用以分开具有不同特性的记录。
  例子(周志华-机器学习)

原则上讲，对于给定的属性集，可以构造的决策树的数目达指数级(每个属性都做一次判断，顺序不同)。尽管某些决策树比其他决策树更准确，但是由于搜索空间是指数规模的，找出最佳决策树在并算上是不可行的。一般采用贪心策略找出满足准确率的次最优决策树

# Hunt算法

递归，贪心，次最优。

hunt算法是一类算法的总称。它使用的是一种构建方法可以应用不同的构建标准。
利用熵增益来构建决策是常用的一种方法。
步骤：

1. 遍历一部分属性，计算每个属性分类时的子集纯度。
2. 选择子集纯度最大的属性划分，分成两个较纯的属性集
3. 对这两个属性集递归 循环执行1,2
4. 最后得到的属性序列就是决策树的分类顺序。

大致思路就是这样的，接下来是代码

等以后手动实现一个简单的啥活也不干的决策树原形 

停止:

• 当前结点包含的样本全属于同一类别，无需划分；
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
  • 把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；
• 当前结点包含的样本集合为空，不能划分.
  • 同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别

需要思考的问题就是：如何划分较纯的子集，何时停止，拟合不足和过拟合，误差分析比较。

# 划分子集的标准

最佳划分度量一句子节点的不纯程度，不纯程度越低，类分布越倾斜。
（0.5，0.5）分布的节点不纯度最高，0或1最大
二元属性就只有两个可能的输出，标称属性可能有多个输出，取决于该属性 取值个数 。序数属性可以产生 二元或多元划分 ，只要不违反序数属性的 有序 就行，连续属性需要根据范围进行 离散化

纯度度量的划分

不纯度度量：

• 熵（Entropy）

  
  • aaaa

• 基尼系数（Gini）
  

  
  • aaaa

• 分类错误（Classification error）
  

  
  • aaaa

看不懂去看p97 例4-3
不同纯度度量是一致的，不纯度的增益公式:

其中xxxx

纯度：

• 熵（Entropy）

  
  • aaaa

• 基尼系数（Gini）
  

  
  • aaaa

• 分类错误（Classification error）
  

  
  • aaaa
    
    

纯度:

标称和二元属性的划分
计算Gini指标的加权平均，越低越好。

连续属性的划分

• 穷举，每个属性N画一个，此时O(N)操作，计算复杂度O（N²）
• 可以先排序，消耗O（N㏒N）把两个排过序的属性中间值拿来做划分点
• 仅考虑具有不同类标号的两个相邻记录之间的划分

增益 熵和Gini指标等不纯性度量趋向有利于不同属性值的属性，关联值大量不同的时候：？？？

• 当选则熵为不纯度度量时，熵的差就是信息增益 Δinfo
  

ID3

• CART采取的是限制测试条件只能是二元划分
  

CART

• C4.5采用 增益率 的划分标准评估划分。修改评估划分标准，把属性测试条件产生的输出数也考虑进去
  

C4.5

看一下具体的算法：

# 决策树的特点

特点:

• 决策树是一种构建分类模型的非参数方法
• 不需要昂贵的的计算代价
• 决策树相对容易解释
• 决策树是学习离散值函数的典型代表
• 决策数对于噪声的干扰具有相当好的鲁棒性
• 冗余属性不会对决策树的准确率造成不利影响
• 数据碎片问题。随着数的生长，可能导致叶结点记录数太少，对于叶结点代表的类，不能做出具有统计意义的判决
• 子树可能在决策树中重复多次。使决策树过于复杂
  
  ----数据挖掘导论

# 多变量决策树-斜决策树

多变量决策树
若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界.决策树所形成的分类边界有一个明显的特点： 轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成.

这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值.但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，

若能使用斜的划分边界，则决策树模型将大为简化.多变量决策树（multivariate decision tree）
就是能实现这样的斜划分甚至更复杂划分的决策树.以实现斜划分的多变量决策树为例，在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合（满足某个数学公式）进行测试。每个非叶结点是一个形如是**∑¹(_d=1)wi*ai=t**的线性分类器，其中wi是属性ai的权重，wi和t可在该结点所含的样本集和属性集上学得.。
在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类边界

# 过拟合

# 过拟合和拟合不足

模型的误差分为两种，训练误差和泛化误差，训练误差也称为再带入误差，泛化误差是在未知记录上的期望误差。分类模型需要低训练误差和低泛化误差。

当生成树很小的时候，训练误差和泛化误差都很大，这时候就是拟合不足.树的规模过大虽然训练误差会降低，但是检验误差开始增大，这就是过拟合

接下来看原因:

• 当训练集中有错误的数据（噪声），生成的决策树会偶然的拟合这些数据，造成泛化误差大。这种情况下，仍然是树越小误差越小。
• 样本缺乏代表性或样本过少导致过度细分产生过拟合
• 在多重比较过程中，大量的候选属性和少量的训练记录导致了模型的过分拟合

# 泛化误差估计

再带入估计
理想的复杂度是能最低化泛化误差的模型复杂度。假设训练既可以很好的代替整体数据。
在这个前提下决策树归纳算法简单的选择产生最低训练误差的模型作为最终模型。

计算公式：e（T）=错误的分类/样本数量。
但一般不是很好用。

奥卡姆剃刀
前面说的模型越复杂，出现过拟合的几率就越高，基于这一原则

奥科姆剃刀(节俭原则)定义 采用更简单的模型为一种策略---给定两个相同训练误差的模型，较简单的模型比复杂的可取。

悲观误差评估
使用再代入方法计算训练误差的时候，添加罚项（penalty term）计算泛化误差
--可以看作模型的悲观误差估计（pessimistic error estimate）:

啊

k是决策树叶节点数，e（T）是决策树的总训练误差，Nt是训练记录Q（ti）是每个节点对应的罚项。

对p112-4.2二叉树来说，0.5的罚项意味着只要至少能够改善一个训练记录的分类，结点就应当扩展，因为扩展一个结点等价于总误差增加0.5，代价比个训练错误小
如果对于所有的结点t，Ω（t）=1左决策树的悲观误差估计为eg（TL）=11/24=0458，右边的决策树的悲观误差估计为eg(TR)=10/24=0.417。

因此，右边的决策树比左边的决策树具有更好的悲观错误率。这样，除非能够减少一个以上训练记录的误分类则结点不应当扩展

最小长度描述原则
空间和传输消耗方面进行评估，基于最小长度原则的信息论方法。
A和B都是已知属性x值的给定记录集。另外，A知道每个记录却不知道这些信息。B可以通过请求A顺序传送每个记录的确切类标号而获得类标号。

一条消息需要O（n）比特的信息，其中n是记录总数。
另一种方法是A事先建立好一个分类模型，概括xy的关系。若模型的准确率为1，那么传输代价就是模型编码代价+被分类错误的记录的类标号。
总代价：
Cost（model，data）=Cost（model）+Cost（data|model）
model:编码模型的开销 data:错误分类记录的编码开销

估计统计上界
泛化误差可以用训练误差的统计修正来估计，因为泛化误倾向于比训练误差大，统计修正通常是计算训练误差的上界。

# 剪枝

处理过拟合手段。

• 前剪枝
  • 未完全之前就设置，可以避免过拟合
  • 观察到不纯增益低于某个阈值就停止拓展
  • 阈值难选，过高还是会过拟合，过低拟合不足
• 后剪枝
  • 初始按照最大规模生长
  • 子树替换用新的叶结点整换子树，新结点的类标号由原子树的多数记录的类标号决定
  • 子树提升用子树中最常使用的分支代替子树，模型不能改进就停止 一般来说后剪枝更好用，但是会浪费算力

代码（使用上面的未剪枝CART决策树）
先（预）剪枝

https://blog.csdn.net/wzmsltw/article/details/51057311

后剪枝：

https://blog.csdn.net/wzmsltw/article/details/51057311

# 性能评估