分类： IT业界
2012-03-17 16:16:30
数据挖掘分类技术
作者：sccot 撰写日期：2012-02-28
1、过分拟合问题：
造成原因有：（1）噪声造成的过分拟合（因为它拟合了误标记的训练记录，导致了对检验集中记录的误分类）；（2）根据少量训练记录做出分类决策的模型也容易受过分拟合的影响。（由于训练数据缺乏具有代表性的样本，在没有多少训练记录的情况下，学习算法仍然继续细化模型就会产生这样的模型，当决策树的叶节点没有足够的代表性样本时，很可能做出错误的预测）（3）多重比较也可能会导致过分拟合（大量的候选属性和少量的训练记录最后导致了模型的过分拟合）
2、泛化误差的估计：
（1）乐观估计（决策树归纳算法简单的选择产生最低训练误差的模型作为最终的模型）（2）悲观误差估计（使用训练误差与模型复杂度罚项的和计算泛化误差）（3）最小描述长度原则（模型编码的开销加上误分类记录编码的开销）（4）估计统计上界（泛化误差可以用训练误差的统计修正来估计，因为泛化误差倾向于比训练误差大，所以统计修正通常是计算训练误差的上界）（4）使用确认集（如2/3的训练集来建立模型，剩下的用来做误差估计）
3、处理决策树中的过分拟合：
A)：先剪枝（提前终止规则）：当观察到的不纯性度量的增益（或估计的泛化误差的改进）低于某个确定的阈值时就停止扩展叶节点。B)：初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树。修剪有两种方法：（1）用新的叶节点替换子树，该叶节点的类标号由子树下记录中的多数类确定；（2）用子树中常见的分支替代子树。当模型不能再改进时终止剪枝步骤。与先剪枝相比，后剪枝技术倾向于产生更好的结果。
4、评估分类器的方法：
（A）：保持方法（用训练集的一部分来做训练一部分做检验，用检验的准确度来评估）（B）随机二次抽样（第一种方法进行K次不同的迭代，取其平均值）（C）交叉验证（每个记录用于训练的次数相同，并且用于检验恰好一次）（D）自助法（有放回抽样）
1.1、决策树分类
算法思想：递归的选择一个属性对对象集合的类标号进行分类，如果分类到某一属性时发现剩下的对象属于同一类，此时就不必再选择属性就行分类，而只用创建一个叶节点并用共同的类来代表。否则，继续选择下一属性进行分类操作，直到某一分类结果全在同一类或者没有属性可供选择为止。根据选择属性的顺序可以将决策树算法分为ID3,C4.5等。其中，决策树算法CART只产生二元划分，它们考虑创建K个属性的二元划分的所有2^(k-1)-1中方法。图1显示了把婚姻状况的属性值划分为两个子集的三种不同的分组方法。对于连续属性来说，测试条件可以是具有二元输出的比较测试（A
问：预测集中的每条记录的属性取值集合是否就和训练集的某一个记录的属性取值集合相等？
答：不一定，一般来说是不可能的。但是建立的决策树一定包含该取值集合（但是可能范围会大些）。因为决策树建过程是只要当前的所有对象属于同一个标号就不再继续选择属性了，所以，实际上建立的决策树所包含的对象是比训练集中的对象要多得多的，这些多余的对象可能就包含当前的预测对象。这也是决策树能够用来进行分类的原因。
决策树归纳的特点：
（1）找到最优决策树是NP完全问题；（2）采用避免过分拟合的方法后决策树算法对于噪声的干扰具有相当好的鲁棒性。
1.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）所采用的基于类的规则定序方法非常适合于处理不平衡的数据集。
1.3、最近邻分类器
算法思想：将要测试的记录与训练集的每条记录计算距离，然后选择距离最小的K个，将K个记录中的类标号的多数赋给该测试记录，如果所有的类标号一样多，则随机选择一个类标号。该算法的变种：先将训练集中所有的记录中相同类标号的记录算出一个中心记录，然后将测试记录与中心记录算距离，取最小的K个就行（这个方法大大的减少了计算量，原来的算法计算量太大了）。
问：该算法没有学习的过程啊？
答：是的。所以这个算法称为消极学习方法，而之前的那些算法称为积极学习方法。
最近邻分类器的特征
最近邻分类器基于局部信息进行预测，而决策树和基于规则的分类器则试图找到一个拟合整个输入空间的全局模型。正因为这样的局部分类决策，最近邻分类器（K很小时）对噪声非常敏感。
1.3、贝叶斯分类器
贝叶斯定理是一种对属性集合类变量的概率关系建模的方法，是一种把类的先验知识和从数据集中收集的新证据相结合的统计原理。贝叶斯分类器的两种实现：朴素贝叶斯和贝叶斯信念网络。贝叶斯定理（如下）(朴素贝叶斯分类的前提假设是属性之间条件独立)：
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之间的平衡。
朴素贝叶斯分类器的特征
（1）面对孤立的噪声点，朴素贝叶斯分类器是健壮的。因为在从数据中估计条件概率时，这些点被平均。通过在建模和分类时忽略样例，朴素贝叶斯分类器也可以处理属性值遗漏问题。（2）面对无关属性，该分类器是健壮的。如果xi是无关属性，那么P(Xi|Y)几乎变成了均匀分布。Xi的条件概率不会对总的后验概率产生影响。（3）相关属性可能会降低朴素贝叶斯分类器的性能，因为对这些属性，条件独立假设已不成立。
贝叶斯信念网络（该方法不要求给定类的所有属性都条件独立，而是允许指定哪些属性条件独立）：
贝叶斯信念网络（BBN）
这个方法不要求给定类的所有属性都条件独立，而是允许指定哪些属性条件独立。贝叶斯信念网络（用图形表示一组随机变量之间的概率关系）建立后主要有两个主要成分：（1）一个有向无环图，表示变量之间的依赖关系（2）一个概率表（每个节点都有），把各节点和它的直接父节点关联起来。一个贝叶斯信念网路的大体样子如下（左边）：其中表右表只是LungCancer节点的概率表
贝叶斯信念网络主要思想
根据已经建立好的贝叶斯信念网络和每个节点的概率表来预测未知记录的分类。主要是按照已建立好的网络根据节点的概率计算先验概率或后验概率。计算概率的方法和前面的朴素贝叶斯计算过程相差无多。
贝叶斯信念网络的建立
网路拓扑结构可以通过主观的领域专家知识编码获得，由于要寻找最佳的拓扑网路有d！种方案计算量较大，一种替代的方法是把变量分为原因变量和结果变量，然后从各原因变量向其对应的结果变量画弧。
BBN的特点:
（1）贝叶斯网路很适合处理不完整的数据。对属性遗漏的实例可以通过对该属性的所有可能取值的概率求或求积分来加以处理。（2）因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过分拟合问题是非常鲁棒的。
问：朴素贝叶斯没有学习的过程，那么是否可以说朴素贝叶斯是消极学习法分类？
答：（1）朴素贝叶斯只是贝叶斯分类的一种实现形式，而实现形式还有贝叶斯网络但是贝叶斯网络是有学习过程的。所以不能说贝叶斯分类时消极学习法。（2）其实朴素贝叶斯是消极学习方法
1.4、人工神经网络（ANN）
ANN是有相互连接的结点和有项链构成。
（1）感知器。感知器的一般模型如下所示：
分类思想：Ij = Sum(Wi*Oi) + a，其中Ij为特定的类标号,Wi为输入向量的权重,Oi为输入属性的值，a为偏置因子。用这个模型就可以对未知的记录分类。图中的激活函数的用处是：将某个Ij的计算值映射到相应的类标号中。在训练一个感知器时，最初将所有的权重随机取值，而训练一个感知器模型就相当于不断的调整链的权值，直到能拟合训练数据的输入输出关系为止。其中权值更新公式如下：Wj(k+1) = Wjk + r(yi - yik)Xij。其中Wk是第k次循环后第i个输入链上的权值，参数r称为学习率，Xij是训练样例的Xi的第j个属性值。学习率值在0到1之间，可以用来控制每次循环时的调整量。自适应r值：r在前几次循环时值相对较大，而在接下来的循环中逐渐减少。
（2）多层人工神经网络
一个多层人工神经网络的示意图如下两图所示：其中左边是多类标号情况，右边是一类情况。
ANN学习中的设计问题：（1）确定输入层的结点数目（2）确定输出层的结点数目（3）选择网络拓扑结构（4）初始化权值和偏置（随机值）（5）去掉有遗漏的训练样例，或者用最合理的值来代替。
ANN的特点:
（1）至少含有一个隐藏层的多层神经网络是一种普适近似，即可以用来近似任何目标函数。（2）ANN可以处理冗余特征，因为权值在训练过程中自动学习。冗余特征的权值非常小。（3）神经网络对训练数据中的噪声非常敏感。噪声问题的一种方法是使用确认集来确定模型的泛化误差；另一种方法是每次迭代把权值减少一个因子。（4）ANN权值学习使用的梯度下降方法经常会收敛到局部最小值。避免方法是在权值更新公式中加上一个自动量。
1.5、支持向量机（SVM）
它可以很好的应用于高维数据，避免了维灾难问题，它使用训练实例的一个子集来表示决策边界，该子集称作支持向量。SVM寻找具有最大边缘的超平面（比那些较小的决策边界具有更好的泛化误差），因此也经常称为最大边缘分类器。最大边缘的决策边界如韩佳伟书P220图6-21所示：分类思想（1）在线性可分的情况下就是要学习（找）到这个最大边缘的决策边界（通过线性规划或拉格朗日乘子来求得），当然也允许有一定的误差（可以有少量的结点分在了它不该在的类，但只要在能够容忍的范围就行），然后利用这个最大边缘的决策边界来分类，结果落在一边的为一类，在另一边的为另一类（2）在线性不可分的情况下，将原来的数据从原先的坐标空间X转换到一个新的坐标空间中，从而可以在变换后的坐标空间中使用一个线性的决策边界来划分样本的类标号（主要技术包括：非线性变换、核技术和Mercer定理）。
SVM的特点:
（1）SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值（2）通过对数据中每个分类属性值引入一个哑变量，SVM可以应用于分类数据
1.6、组合方法
该方法聚集多个分类器的预测来提高分类的准确率，这些技术称为组合或分类器组合方法。组合方法由训练数据构建一组基分类器，然后通过对每个分类器的预测进行投票来进行分类。预测过程如下所示：
由上面的分类过程可以看出当误差率大于0.5时，组合分类器的性能比基分类器更差。组合分类器的性能优于单个分类器必须满足两个必要条件：（1）基分类器之间应该是相互独立的（轻微相关也行）；（2）基分类器应当好于随机猜测分类器。
构建组合分类器的方法
（1）通过处理训练数据集。根据某种抽样分布，通过对原始数据进行再抽样来得到多个训练集（如有放回随机抽样）。一般得到的训练集和原始数据集一样大。然后使用特定的学习算法为每个训练集建立一个分类器（装袋和提升是两种处理训练集的组合方法）。（2）通过处理输入特征。通过选择输入特征的子集来形成每个训练集。对那些含有大量冗余特征的数据集，这种方法的性能非常好（随机深林就是一种处理输入特征的组合方法，它使用决策树作为基分类器）。（3）通过处理类标号。这种方法适用于类数足够多的情况。这种方法先将所有的类划分为两个大类，然后将两个大类的每个大类划分为两个次大类……，预测时按照前面的分类遇到一个分类结点得一票，最后得票数最多的那个就是最终的类。（4）通过处理学习算法。如果在同一个训练集上用同一个学习算法得到的分类器模型不一样，就可以多做几次以建立多个基分类器。
组合方法对于不稳定的分类器效果很好。不稳定分类器是对训练数据集微小的变化都很面干的基分类器。不稳定分类器的例子包括决策树、基于规则的分类器和人工神经网络。
（1）装袋。装袋又称自助聚集，是一种根据均匀分布从数据集中重复抽样的（有放回的）技术。每个自助样本集都和原始数据一样大。然后对每个样本集训练一个基分类器，训练k个分类器后，测试样本被指派到得票最高的类。用于噪声数据，装袋不太受过分拟合的影响。
（2）提升。是一个迭代过程，用来自适应地改变样本的分布，使得基分类器聚焦在那些很难分的样本上。例如开始时所有的样本都赋予相同的权值1/N, 然后按这个概率抽取样本集，然后得到一个分类器，并用它对原始数据集中的所有样本进行分类。每一轮结束时更新样本的权值。增加错误分类的样本的权值，减少被正确分类的样本的权值，这迫使分类器在随后的迭代中关注那些很难分类的样本。通过聚集每一轮得到的分类器，就得到最终的分类器。目前有几个提升算法的实现，它们的差别在于：（1）每轮提升结束时如何更新训练样本的权值；（2）如何组合每个分类器的预测。
Android：在该算法中，基分类器Ci的重要性依赖于它的错误率。算法思想：首先初始化N个样本的权值（w = 1/N），然后对于第i次（总共k次，产生k个基分类器）提升（其他次一样），根据w通过对D进行有放回抽样得到训练集Di,然后根据Di得到一个基分类器Ci,用Ci对训练集D中的样本进行分类。然后计算分类的加权误差，如果加权误差大于0.5，就将所有样本的权值重设为为1/N，否则用ai更新每个样本的权值。得到k个基分类器后，然后合并k个基分类器得到预测结果。Android 算法将每一个分类器Cj的预测值根据 aj进行加权，而不是使用多数表决的方案。这种机制允许Android 惩罚那些准确率很差的模型，如那些在较早的提升轮产生的模型。另外，如果任何中间轮产生高于50%的误差，则权值将被恢复为开始的一致值wi = 1/N，并重新进行抽样。Android 算法倾向于那些被错误分类的样本，提升技术很容易受过分拟合的影响。
（3）随机森林。它是一类专门为决策树分类器设计的组合方法。它结合多颗决策树做出预测。与Android算法使用的自适应方法不同，Android中概率分布是变化的，以关注难分类的样本，而随机森林则采用一个固定的概率分布来产生随机向量。随机森林与装袋不同之处在于（1）装袋可以用任何分类算法产生基分类器而随机森林只能用决策树产生基分类器。（2）装袋最后组合基分类器时用的投票方法二随机森林不一定用投票。（3）随机森林的每个基分类器是一个样本集的随机向量而装袋是用的有放回抽样来产生样本。随机森林的的决策树在选择分类属性时，随机选择F个输入特征（而不是考察所有可用的特征）来对决策树的节点进行分裂，然后树完全增长而不进行任何剪枝，最后用多数表决的方法来组合预测（这种方法叫Forest-RI，其中RI是指随机输入选择）。注意此时如果F太小，树之间的相关度就减弱了，F太大树分类器的强度增加，折中通常F取log2d + 1，其中d是输入特征数。如果d太小，可以创建输入特征的线性组合，在每个节点，产生F个这种随机组合的新特征，并从中选择最好的来分裂节点，这种方法称为Forest-RC。随机森林的分类准确率和Android差不多，但是随机森林对噪声更加鲁棒，运行速度也快得多。
1.6、不平衡类问题
有时候需要准确分类训练集中的少数类而对多数类不是太关心。如不合格产品对合格产品。但是这样建立的模型同时也容易受训练数据中噪声的影响。
新定的指标（过去的指标不顶用如：准确率不顶用）：真正率（灵敏度）、真负率（特指度）、假正率、假负率、召回率、精度。
（1）接受者操作特征（ROC）曲线。该曲线是显示分类器真正率和假正率之间的折中的一种图形化方法。在一个ROC曲线中，真正率沿y轴绘制，而假正率沿x轴绘制。一个好的分类模型应该尽可能靠近图的左上角。随机预测分类器的ROC曲线总是位于主对角线上。
ROC曲线下方的面积（AUC）提供了评价模型的平均性能的另一种方法。如果模型是完美的，则它在ROC曲线下方的面积等于1，如果模型仅仅是简单地随机猜测，则ROC曲线下方的面积等于0.5。如果一个模型好于另一个，则它的ROC曲线下方的面积较大。为了绘制ROC曲线，分类器应当能够产生可以用来评价它的预测的连续值输出，从最有可能分为正类的记录到最不可能的记录。这些输出可能对应于贝叶斯分类器产生的后验概率或人工神经网络产生的数值输出。（绘制ROC曲线从左下角开始到右上角结束，绘制过程见hanjiawei P243）。
（2）代价敏感学习。代价矩阵对将一个类的记录分类到另一个类的惩罚进行编码。代价矩阵中的一个负项表示对正确分类的奖励。算法思想：将稀有的类标号预测错误的代价权值设为很大，则在计算总代价时，它的权值较高，所以如果分类错误的话，代价就较高了。代价敏感度技术在构建模型的过程中考虑代价矩阵，并产生代价最低的模型。例如：如果假负错误代价最高，则学习算法通过向父类扩展它的决策边界来减少这些错误。
（2）代价敏感学习. 主要思想：改变实例的分布，而使得稀有类在训练数据集得到很好的表示。有两种抽样方法：第一种选择正类样本的数目和稀有样本的数目一样多，来进行训练（可以进行多次，每次选择不同的正类样本）。第二种复制稀有样本（或者在已有的稀有样本的邻域中产生新的样本）使得和正类样本一样多。注意，第二种方法对于噪声数据可能导致模型过分拟合。
1.6、多类问题(结果类标号不止两个
解决方法：（1）将多类问题分解成K个二类问题。为每一个类yi Y（所有的类标号集合）创建一个二类问题，其中所有属于yi的样本都被看做正类，而其他样本都被看做负类。然后构建一个二元分类器，将属于yi的样本从其他的类中分离出来。（称为一对其他（1-r）方法）。（2）构建K（K-1）/2个二类分类器，每一个分类器用来区分一对类（yi，yj）。当为类（yi，yj）构建二类分类器时，不属于yi或yj的样本被忽略掉（称为一对一（1-1）方法）。这两种方法都是通过组合所有的二元分类器的预测对检验实例分类。组合预测的典型做法是使用投票表决，将验证样本指派到得票最多的类。
纠错输出编码（ECOC）：前面介绍的两种处理多类问题的方法对二元分类的错误太敏感。ECOC提供了一种处理多类问题更鲁棒的方法。该方法受信息理论中通过噪声信道发送信息的启发。基本思想是借助于代码字向传输信息中增加一些冗余，从而使得接收方能发现接受信息中的一些错误，而且如果错误量很少，还可能恢复原始信息。具体：对于多类学习，每个类yi用一个长度为n的唯一位串来表示，称为它的代码字。然后训练n个二元分类器，预测代码子串的每个二进制位。检验实例的预测类由这样的代码字给出。该代码字到二元分类器产生的代码字海明距离最近（两个位串之间的海明距离是它们的不同的二进制位的数目）。纠错码的一个有趣的性质是，如果任意代码字对之间的最小海明距离为d，则输出代码任意 (d-1) / 2个错误可以使用离它最近的代码字纠正。注意：为通信任务设计的纠正码明显不同于多类学习的纠正吗。对通信任务，代码字应该最大化各行之间的海明距离，使得纠错可以进行。然而，多类学习要求将代码字列向和行向的距离很好的分开。较大的列向距离可以确保二元分类器是相互独立的，而这正是组合学习算法的一个重要要求。
