1 基本概念

     1.1 分类定义

    简言之，确定对象属于哪个预定义的目标类。

    学术一点：通过学习得到一个目标函数f（分类模型），把每个属性集x映射到一个预先定义的类标号y。

    1.2 分类模型的实用性

        非常适合预测或描述二元或标称类型的数据集

        不适合序数性数据集的分类

        不考虑隐含在目标类中的序数关系和继承关系

     1.3 评价分类方法

        预测的准确率：正确地预测新的或先前未见过的数据的类标号的能力

        速度：构件模型的速度；利用模型进行分类的速度

        强壮型：噪声数据或具有空缺值的数据，模型正确预测的能力

        可伸缩性：当给定大量数据时，有效地构造模型的能力

        可解释性：设计学习模型提供的理解和洞察的层次

        混淆矩阵：根据模型正确和错误预测的检验记录进行评估，这些计数放在被称作混淆矩阵（confusion matrix）的表格中

     1.4 常用的分类技术

        决策树

        神经网络

        朴素贝叶斯和贝叶斯信念网络

        支持向量机

        Rule-based methods

        Distance-based methods

        Memory based reasoning

2. 基于决策树的分类方法（局部最优）

   2.1  决策树生成算法：

        Hunt 算法

        CART

        ID3，C4.5

        SLIQ,SPRINT

     优势

        容易创建

        分类速度快

        小容量决策树容易理解

        和其他小数据量的分类算法相比，分类效果可以接受

    2.2 Hunt 算法

    步骤

        Dt ：t点处的训练集

        （1）Dt的记录属于同一类别yt--->结点t成为叶子节点，类别为yt

        （2）Dt的数据集为空集--->结点t成为叶子结点，类别为默认类别yd

        （3）Dt的记录不止一个类--->用某个属性将数据集划分成更小的子集

        （4）重复递归

    存在的问题

        划分数据时，如何选择划分依据，即特征？

        如何评估划分结果，确定结果是不是最好的？

        什么时候停止对数据集的划分？

---

处理方法：

问题一：如何划分？

    划分：依赖于数据的属性类型：名词性；序数性；连续性

    方法：依赖于划分的分支数目：二分 or 多分

（1） 名词属性上划分

        二分：分成两个子集

        多分：分成多份

（2）序数型属性上划分

        二分：分成两个子集

        多分：分成多份 eg：小、中、大

    （3）连续型属性上划分---离散化

        二分：定threshold ---A>t or A<t

        离散化：分成序数型的新属性；预先定义 or 动态划分 -----若干个小区间

   问题二：评估划分结果？

    （1）Gini指数

        划分的结果中，即每个节点，期待节点中的数据属于同一类----->出现“impurity”（不纯性）指标；通过评价impurity来评估划分结果的优劣

Gini Index 基尼指数（p（i|t）表示给定结点t中属于类i的记录所占的比例）  越小越好。

        最大：（1-1/nc） 当类别均匀分布时；分类效果 worst

        最小：（0.0） 当所有记录属于同一类；分类效果best

    多分：

        ni：结点i（子节点）中的记录数

        n：该节点（父节点）的记录总数目

        ni/n：相等于一个权重系数

        穷举法：尝试不同的分类结果，分别计算其Gini指数，选择Gini指数最小的分类方法

    （2）Entropy 熵

        计算公式：

        最大：（lognc） 当类别变量均匀分布时；分类效果worst

        最小：（0.0） 当分类中所有结果属于同一类别；分类效果best

       GAIN 信息增益

            计算公式：

                    p父节点，分成k分

                    ni 结点i中的记录数目

                    ID3，C4.5中使用

                缺点：更加倾向于划分成多个子集，每个子集小而纯

        Gain Ratio

        计算公式：

解决信息增益的缺点

    （3）Misclassification error 误分率

        最大：（1-1/nc） 当分类变量服从均匀分布；分类效果worst

        最小：（0.0） 当分类结果属于同一类别；分类效果best

    问题三：何时停止？

           （1） 当结点中的记录属于同一类别

            （2）所有记录都有相同的属性值

            （3）提前终止

理想的决策树

    （1）叶子节点数最少

    （2）叶子节点深度最小

    （3）叶子节点数最少而且叶子节点深度最小

理想决策树是一个NP难题；只能趋向于最优

3. 算法

3.1 ID3

思想：

        以信息熵为度量，用于决策树结点的属性选择，每次有限选取信息量最多的属性，亦即能死熵值变为最小的属性，构造一颗熵值下降最快的决策树，到叶子结点出的熵值为0.每个叶子结点对应的实例集中的实例属于同一类。

步骤：

（1）决定分类属性

（2）对目前的数据表，建立一个节点N

（3）如果数据库中的数据都属于同一类，N就是树叶，在树叶上标出所属的类别

（4）如果数据表中没有其他属性可以考虑，这N也是树叶，按照少数服从多数的原则在树叶上标出所属类别

（5）否则，根据平均信息期望值E或Gain值选出一个最佳属性作为结点N的测试属性

（6）结点属性选定后，对于该属性中的每个值：从N生成一个分支，将数据表中与该分支有关的数据收集形成分支结点的数据表，在表中删除结点属性那一栏；如果分支数据表非空，运用以上算法从该节点建立子树。

3.2 C4.5算法

从ID3算法演变而来，除了拥有ID3算法的功能外，克服了ID3在应用中的不足，主要体现在：

    （1）用信息增益比例/信息增益率来选择属性，客服了用信息增益选择属性时偏向于选择取值多的属性的不足；

    （2）能够完成对连续属性的离散化处理

    （3）可以处理具有缺少属性值的训练样本

    （4）在树构造过程中或者构造完成之后，进行剪枝以避免树的过度拟合

    （5）采用知识表示形式为决策树，并最终可以形成产生式规则

应用时实际问题

过拟合（训练误差低，泛化误差高）

    原因：噪声，训练样例太小；缺乏代表性样本等

    模型误差：训练误差；泛化误差

    导致决策树更加复杂；

解决手段

（1）及早停止树增长：测试属性的选择方法属于“爬山法”，选择是局部最优，不是全局最优。模型越复杂，过拟合发生的可能性越大。

（2）后修建法

误差分析及模型选择

    乐观法：泛化误差=训练误差

    悲观法：泛化误差=（训练误差+N*x）   N:叶子节点数；x惩罚系数

    REP：使用验证集来评估

    奥卡姆剃刀：当模型泛化误差相等时，模型复杂度小的比大的好。

4.模型评估

关注模型分类效果；而不是分类速度等等

指标

准确率Accuracy=(TP+TN)/(TP+TN+FP+FN)

如果数据集是倾斜数据，分类器分类效果也很好，但是泛化误差很大---仅仅使用准确率的不足

精确率Precision（p）=TP/（TP+FP）

预测正确的结果中，有多少是真正正确的（真正正确的结果在预测正确的结果中所占的比例）

召回率Recall（r）= TP/(TP+FN)

在真正正确的数据中，有多少是预测正确的（预测正确的结果在真正正确的数据集中所占的比例）

F-score（F）=2*r*p/（r+p）