分类属于模型挖掘，更确切地讲，是预测建模的过程
预测建模的目的是，根据观察到的对象特征值预测它的其他特征值
例如，根据年龄、收入、是否学生、信用情况这四个方面的特征，预测某个人是否会购买笔记本电脑，这是一个典型的分类问题。
分类：
构造、使用模型来对某个样本的类别进行判别
主要用于对离散的数据进行预测
典型应用：信誉评估、医学诊断
预测：
构造、使用模型来对某个样本的值进行估计，例如预测某个不知道的值或者缺失值
主要用于对连续或有序的数据进行预测
典型应用：性能预测
第一步，建立模型阶段
用来构造模型的数据集被称为训练集
模型一般表示为：分类规则,决策树或者数学公式
第二步，使用模型阶段
首先测试模型的准确性
用测试集和由模型进行分类的结果进行比较
两个结果相同所占的比率称为准确率
测试集和训练集必须不相关
如果准确性可以接受的话, 使用模型对新数据进行分类
分类过程：建立模型阶段：
三种数据集:
数据预处理
数据清洗
对数据进行预处理，去掉噪声，对缺失数据进行处理（用某个最常用的值代替或者根据统计用某个最可能的值代替）
相关分析 (特征选择)
去掉某些不相关的或者冗余的属性（如银行进行贷款信誉评估时不需要考虑属于一周的某一天）
数据转换
对数据进行概括（如将连续的值离散成若干个区域，将街道等上升到城市）
对数据进行规范化，将某个属性的值缩小到某个指定的范围之内
分类方法评价
准确性
速度：构造模型的时间 (训练时间)、使用模型的时间 (预测时间)
鲁棒性：能够处理噪声和缺失数据
可伸缩性：对磁盘级的数据库有效
易交互性：模型容易理解，具有较好的洞察力
常用的分类方法：决策树分类、贝叶斯分类、支持向量机、神经网络、近邻分类
Supervised vs. Unsupervised Learning
Supervised learning (classification)
Supervision: The training data (observations, measurements,etc.) are accompanied by labels indicating the class of the observations
New data is classified based on the training set
Unsupervised learning (clustering)
The class labels of training data is unknown
Given a set of measurements, observations, etc. with the aim of establishing the existence of classes or clusters in the data
决策树模型
顾名思义，决策树（Decision Tree）是基于“树”结构来进行决策的，是人类在面临决策问题时一种很自然的处理机制。
一般地，一颗决策树包含一个根节点、若干个内部节点和若干个叶子节点
叶子节点对应决策结果，其他节点对应一个属性测试
每个节点包含的样本集合根据属性测试的结果被划分到子节点中
根节点包含全部样本集
学习过程：通过对训练样本的分析来确定“划分属性”（即内部结点所对应的属性）
预测过程：将测试示例从根结点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶子结点
第一个决策树算法：CLS (Concept Learning System)
[E. B. Hunt, J.Marin, and P. T. Stone’s book “Experiments in Induction” published by Academic Press in 1966]
使决策树受到关注、成为机器学习主流技术的算法：ID3
[J. R. Quinlan’s paper in a book “Expert Systems in the Micro ElectronicAge” edited by D. Michie, published by Edinburgh University Press in1979]
最常用的决策树算法：C4.5
[J. R. Quinlan’s book “C4.5:Programs for Machine Learning” published by Morgan Kaufmann in 1993]
可以用于回归任务的决策树算法：CART (Classification and Regression Tree)
基于决策树的强大算法：RF (Random Forest)
L. Breiman’s MLJ’01 paper “Random Forest”]
ID3:
Training Dataset：This follows an example of Quinlan’s ID3(Playing Tennis)
决策树分类的主要任务是要确定各个类别的决策区域，或者说，确定不同类别之间的边界。在决策树分类模型中，不同类别之间的边界通过一个树状结构来表示
（1）最大高度=决策属性的个数
（2）树越矮越好
（3）要把重要的好的属性放在树根
因此，决策树建树算法就是： 选择树根的过程
根据树根，划分训练集：
1 开始时，所有的训练集样本都在树根
2 属性都是可分类的属性(如果是连续值的话，先要对其进行离散化)
停止划分的条件：
1 某个节点上的所有样本都属于相同的类别
2 所有属性都用到了– 采用多数有效法对叶子节点分类
3 没有样本了
第一步：选择属性，作为树根
一件事有多种不同的状态，不知道是哪种具体的状态的不确定性，便是熵。而信息是多种可能状态中确定一个具体的状态的物理量。
熵表示一个概率分布X的平均信息量，就是分布中各个取值的信息量的期望。熵就是信息的期望，所以熵也叫信息熵
i: 用于指定第几个具体情况
p_i：第 i 个具体情况的概率
Σ：表示 i 个情况计算出的 p log p 累加起来
之所以前面有负号是因为 log 1/p = log p^-1 = -log p 概率的倒数变成了负号被拿到前面了
熵摘自：http://www.360doc.com/content/19/0610/07/39482793_841453815.shtml
选择树根比较流行的属性选择方法：信息增益
信息增益最大的属性被认为是最好的树根
实际上，给定训练集S，信息增益代表的是在不考虑任何输入变量的情况下确定S中任一样本所属类别需要的信息（以消除不确定性）与考虑了某一输入变量X后确定S中任一样本所属类别需要的信息之间的差。差越大，说明引入输入变量X后，消除的不确定性，该变量对分类所起的作用就越大，因此被称为是好的分裂变量。换句话说，要确定S中任一样本所属类别，我们希望所需要的信息越少越好，而引入输入变量X能够减少分类所需要的信息，因此说输入变量X为分类这个数据挖掘任务带来了信息增益。信息增益越大，说明输入变量X越重要，因此应该被认为是好的分裂变量而优先选择。
因此，计算信息增益的总的思路是：
1）首先计算不考虑任何输入变量的情况下要确定S中任一样本所属类别需要的熵Entropy(S)；
2）计算引入每个输入变量X后要确定S中任一样本所属类别需要的熵Entropy (X,S);
3)计算二者的差，Entropy (S) - Entropy (X, S)，此即为变量X所能带来的信息（增益），记为Gain(X,S)。
用S表示训练集，假设分类属性具有m个不同的值，也就是说共有m个不同的分类 Ci(i = 1, …, m), 用si 表示S中属于分类Ci的样本的个数
则信息收益可以用如下三步求出
（1）求总的熵:
（2）对每个属性，求已知该属性后的熵, 假设属性A的值为{a1,a2,…,av}
（3）对每个属性，求信息增益:
属性选择方法：信息增益计算示例，
由此可知，属性age信息增益最大。继续构建：
Extracting Classification Rules from Trees：
决策树中所蕴含的知识可以表达成IF-THEN规则的形式
从根到叶的一条路径生成一条规则，路径上的属性值由AND连接起来，构成IF部分，叶子节点构成THEN部分，指出所属的分类，Example：
IF age = “<=30” AND student = “no” THENbuys_computer = “no”
IF age = “<=30” AND student = “yes” THENbuys_computer = “yes”
IF age= “31…40” THENbuys_computer = “yes”
IF age= “>40” ANDcredit_rating = “excellent” THENbuys_computer = “yes”
IF age = “<=30” AND credit_rating = “fair” THENbuys_computer = “no”
Avoid Overfitting in Classification：
过拟合（Overfitting）: 有些生成的决策树完全服从于训练集，太循规蹈矩，以至于生成了太多的分支，某些分支可能是一些特殊情况，出现的次数很少，不具有代表性，更有甚者仅在训练集中出现，导致模型的准确性很低
通常采用剪枝的方式来克服过拟合，剪枝有两种方法：
先剪：构造树的过程中进行修剪。不符合条件的分支则不建。
1 训练时间开销降低，测试时间开销降低
2 过拟合风险降低，欠拟合风险增加
后剪：整个树生成之后进行修剪。
1 训练时间开销增加，测试时间开销降低
2 后剪：过拟合风险降低，欠拟合风险基本不变
泛化性能：后剪 通常优于 先剪
西瓜书中ID3决策树的实现
https://blog.csdn.net/leafage_m/article/details/79629074
C4.5
对于具有很多值的属性来说，Information gain比较偏心
为了解决这个问题，C4.5 (ID3的改进) 采用 gain ratio 作为度量手段
nGainRatio(A) = Gain(A)/SplitInfo(A)
Ex.
这里A为income, gain_ratio(income) = 0.029/0.926 = 0.031
具有最大的gain ratio的属性被选为划分属性
数据挖掘领域为什么采用决策树呢?
1 和其他分类方法相比，决策树的学习速度较快
2 可以转换成简单的、易于理解的分类规则
3 可以采用SQL查询访问数据库
4 具有较高的分类准确性
Scalable Decision Tree Induction Methods:
SLIQ (EDBT’96 — Mehta et al.)
为每个属性创建一个索引，内存中只放分类列表和当前属性列表
SPRINT (VLDB’96 — J. Shafer et al.)
构造了一个特殊的属性列表数据结构
PUBLIC (VLDB’98 — Rastogi & Shim)
将建树和剪枝结合起来进行，尽早停止树的生长
RainForest (VLDB’98 —Gehrke, Ramakrishnan & Ganti)
维护了一个AVC-list (attribute, value, class label)结构
