数据挖掘学习笔记：分类器（一）

分类方法（Classification）用于预测数据对象的离散类别（Categorical Label).

决策树（详细介绍：http://www.tuicool.com/articles/Un6j2a）

决策树归纳是经典的分类算法。它采用自顶向下递归的各个击破方式构造决策树。树的每一个结点上使用信息增益度量选择测试属性。可以从生成的决策树中提取规则。

算法思想：递归的选择一个属性对对象集合的类标号进行分类，如果分类到某一属性时发现剩下的对象属于同一类，此时就不必再选择属性就行分类，而只用创建一个叶节点并用共同的类来代表。否则，继续选择下一属性进行分类操作，直到某一分类结果全在同一类或者没有属性可供选择为止。根据选择属性的顺序可以将决策树算法分为ID3,C4.5等。其中，决策树算法CART只产生二元划分，它们考虑创建K个属性的二元划分的所有2^{^(k-1)}-1中方法。

决策树归纳的特点：

（1）找到最优决策树是NP完全问题；（2）采用避免过分拟合的方法后决策树算法对于噪声的干扰具有相当好的鲁棒性。

基于规则的分类

基于规则的分类使用一组if…then规则来分类记录的技术。

算法思想：先从训练集生成规则集合，规则是使用合取条件表示的：如规则ri：（条件i）->yi,其中r1是如下形式：r1：（胎生=否）^（飞行动物=是）->鸟类;其中左边称为规则前件或前提；规则右边称为规则后件。如果规则r的前件和记录x的属性匹配，则称r覆盖x。当r覆盖给定的记录时，称r被激发或被触发。建立规则集合后，就进行分类。对每个待分类的记录和规则集合中的每条规则进行比较，如果某条规则被触发，该记录就被分类了。

由于规则集中的规则不一定是互斥的，所有有可能分类的时候某条记录会属于多个类（也就是说某条记录会同时触发规则集中的超过1条的过则，而被触发的规则的类标号也不一样），这种情况有两种办法解决。　　　　（1）有序规则。将规则集中的规则按照优先级降序排列，当一个测试记录出现时，由覆盖记录的最高秩的规则对其进行分类，这就避免由多条分类规则来预测而产生的类冲突问题

　　（2）无序规则。允许一条测试记录触发多条分类规则，把每条被触发规则的后件看作是对相应类的一次投票，然后计票确定测试记录的类标号。通常把记录指派到得票最多的类。

假设现在有一个记录它不能触发规则集合中的任何一个规则，那么它该如何就行分类呢？解决办法也有两个：

　　（1）穷举规则。如果对属性值的任一组合，R中都存在一条规则加以覆盖，则称规则集R具有穷举覆盖。这个性质确保每一条记录都至少被R中的一条规则覆盖。

　　（2）如果规则不是穷举的，那么必须添加一个默认规则rd：（）->yd来覆盖那些未被覆盖的记录。默认规则的前件为空，当所有其他规则失效时被触发。yd是默认类，通常被指定为没有被现存规则覆盖的训练记录的多数类。

规则的排序方案：

（1）基于规则的排序方案：根据规则的某种度量对规则排序。这种排序方案确保每一个测试记录都是有=由覆盖它的“最好的”规则来分类。

　　（2）基于类的排序方案。属于同一类的规则在规则集R中一起出现。然后这些规则根据它们所属的类信息一起排序。同一类的规则之间的相对顺序并不重要，因为它们属于同一类。（大多数著名的基于规则的分类器（C4.5规则和RIPPER）都采用基于类的排序方案）。

建立规则的分类器：

（1）顺序覆盖。直接从数据中提取规则，规则基于某种评估度量以贪心的方式增长，该算法从包含多个类的数据集中一次提取一个类的规则。在提取规则时，类y的所有训练记录被看作是正例，而其他类的训练记录则被看作反例。如果一个规则覆盖大多数正例，没有或仅覆盖极少数反例，那么该规则是可取的。一旦找到这样的规则，就删掉它所覆盖的训练记录，并把新规则追加到决策表R的尾部（规则增长策略：从一般到特殊或从特殊到一般）

　　（2）RIPPER算法。(和前面那个差不多，只是规则增长是从一般到特殊的，选取最佳的合取项添加到规则前件中的评判标准是FOIL信息增益，直到规则开始覆盖反例时，就停止添加合取项。而剪枝是从最后添加的合取项开始的，给定规则ABCD->y，先检查D是否应该被删除，然后是CD，BCD等)

基于规则的分类器的特征：

（1）规则集的表达能力几乎等价于决策树，因为决策树可以用互斥和穷举的规则集表示。

　　（2）被很多基于规则的分类器（如RIPPER）所采用的基于类的规则定序方法非常适合于处理不平衡的数据集。

KNN法(K-Nearest Neighbor)

算法思想：将要测试的记录与训练集的每条记录计算距离，然后选择距离最小的K个，将K个记录中的类标号的多数赋给该测试记录，如果所有的类标号一样多，则随机选择一个类标号。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量（N）的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

该算法的变种：先将训练集中所有的记录中相同类标号的记录算出一个中心记录，然后将测试记录与中心记录算距离，取最小的K个就行（这个方法大大的减少了计算量，原来的算法计算量太大了）。

最近邻分类器的特征

最近邻分类器基于局部信息进行预测，而决策树和基于规则的分类器则试图找到一个拟合整个输入空间的全局模型。正因为这样的局部分类决策，最近邻分类器（K很小时）对噪声非常敏感。

贝叶斯分类器

贝叶斯定理是一种对属性集合类变量的概率关系建模的方法，是一种把类的先验知识和从数据集中收集的新证据相结合的统计原理。

贝叶斯分类器的两种实现：朴素贝叶斯和贝叶斯信念网络。

贝叶斯定理（如下）(朴素贝叶斯分类的前提假设是属性之间条件独立)：

P(Y | X) = P(X | Y)P(Y) / P(X)            （1-1）

- 朴素贝叶斯分类分类思想

假设（1-1）中的X为要分类的记录，而Y是训练集中的类标号集合，要将X准确分类就必须使对特定的X和所有的分类标号yi，让P(yi|X)最大的yi即为测试记录的类标号。由（1-1）知道要让左边最大就是让后边最大，而因为X是特定的所以就是使

P(X | Y)P(Y)                           （1-2）

最大。此时的yi即为测试记录的类标号。而要计算(1-2)因为各个属性是独立的，所以直接乘即可（具体见hanjiawei的书P203例6-4）。

在计算（1-2）时假设出现某项是零了怎么办？有两种方法：

　　（1）拉普拉斯校准或拉普拉斯估计法。假定训练数据库D很大，使得需要的每个技术加1造成的估计概率的变化可以忽略不计，但可以方便的避免概率值为零的情况。（如果对q个计数都加上1，则我们必须在用于计算概率的对应分母上加上q）。

　　（2）条件概率的m估计。P(Xi | Yi) = (nc + mp) / (n + m)其中，n是类yi中的实例总数，nc是类yi的训练样例中取值xi的样例数，m是称为等价样本大小的参数，而p是用户指定的参数。如果没有训练集（即n=0）则P(xi|yi)=p。因此p可以看作是在yi的记录中观察属性值xi的先验概率。等价样本大小决定先验概率p和观测概率nc/n之间的平衡。