分类算法

• 决策树

算法：
用一个属性划分数据集，可以产生分类更纯的子集。（不纯性度量）因此，不断划分，就能确定分类。
为了更有效地选择属性进行划分，以不纯性的增益or增益率来衡量。
~
特点：
a.以不纯性的增益or增益率来衡量，通常可以很好地选择属性，因此冗余属性通常不会对决策树的准确性造成影响。但不相关的属性很多，可能会被选中，影响决策树的准确性。
b.划分产生的决策边界是直线的，因此会限制了复杂关系了建模能力。可以采用“构造归纳”方法，提供一些由复杂模型构造的新属性。
c.分治划分策略，可能会产生子树重复的问题。
d.不断划分导致样本太小时，不能再进行有效的划分，“数据碎片”问题，可以当样本数小于某个特定的阈值停止分裂。
~
步骤：
一、对于特点a,b，需要对数据进行预处理，删除冗余属性，尝试构建新属性
二、对于特点c,d，需要在决策树归纳过程中处理，可以采用：
1.先剪枝：设定停止增加叶节点的条件：不纯性度量增益低于特定阈值等
2.后剪枝：用叶节点替换子树、用子树中最常使用的分支替换子树
三、模型外的措施：
1.多次重复建模，估计泛化误差：随机二次抽样、交叉验证、自助法...
2.比较多个模型进行选择：估计泛化误差的置信区间、比较两种分类法性能差异的显著性

• 基于规则的分类器

算法：
在相同的分类中，寻找规则，使之有较优的覆盖率和准确率。
～
规则评估：似然比统计量、laplace、m统计量、FOIL信息增益
RIPPER算法：
1.按类的频率对类进行排序，从最不频繁的类开始提取规则
2.从一般到特殊的策略进行规则增长，使用FOIL信息增益进行评估
3.以最小描述长度原则作为终止条件

• 最近邻分类器

消极学习算法（lazy learner）
算法：
当一个需要预测一个测试样例的时候，在训练集中找到相似的K个样例，以多数表决的方式进行预测。
也可以用，距离加权表决。
特点：
1.不需要建立模型，但分类测试样例的开销很大。
2.基于局部的信息进行预测，对噪声的非常敏感。
3.需要采用适当的邻近性度量和数据预处理，否则很可以做出错误的预测。

• 贝叶斯分类器

在条件X（属性X＝x1）成立的时，以某分类的频率，作为概率。
~
A.朴素贝叶斯分类器
P(Y|X) = P(X|Y)P(Y)/P(Y|X)
假设属性之间条件独立
P(Y|X) = P(Y)πP(Xi|Y)/P(X)
连续属性的条件概率：属性离散化、对于每一类，用高斯分布拟合
某些类属性样本较少，用m估计来估计条件概率，防止为0。
~
特征：
1.对孤立的噪声点，估计条件概率时这些点会被平均，朴素贝叶斯分类器是健壮的
2.对于无关属性，均匀分布不会影响条件概率
3.贝叶斯假设条件独立，相关属性会降低朴素贝叶斯分类器的

• 人工神经网络ANN

核心思想：
1.感知器：根据感知器的输出与目标的差异来更新输入链的权值
2.多层神经网络，能够近似任何函数，处理冗余特征，本质上是在构造复杂的特征，需要防止过拟合。
3.对噪声十分敏感，使用确认集来确定模型的泛化误差
4.经常收敛到局部最小值，在权值更新公式中加上一个动量项。

• 组合方法

核心思想：