则待分类元组就属于哪个类别算法算法 4-2 k-近邻分类算法输入： 训练数据T；近邻数目k；待分类的元组t 输出： 输出类别c （1）N=；（2）FOR each d ∈T DO BEGIN（3） IF |N|≤k THEN（4） N=N∪{d}； （5） ELSE（6） IF u ∈N such that sim(t，u)〈sim(t，d) THEN BEGIN （7） N=N-{u}；（8） N=N∪{d}；（9） END（10）END（11）c=class to which the most u∈N. pkNN的例子的例子假如只用假如只用“高度高度”参于距离参于距离计算，算，k=5，， k-近邻分类算法对近邻分类算法对分分类的过程如下：类的过程如下： •对样本数据对样本数据T前前k=5个记录，得到个记录，得到N={、、< Jim，男，，男，2>、、< Maggie，女，，女，1.9>、、< Martha，女，，女，1.83>和和< Stephanie，女，，女，1.7>}。
•对第对第6个记录个记录d=< Bob，男，，男，1.85>，得到，得到N={、、< Bob，男，，男，1.85>、、< Maggie，女，，女，1.9>、、< Martha，女，，女，1.83>和和< Stephanie，女，，女，1.7>}•对第对第7个记录个记录d=< Kathy，女，，女，1.6>，得到，得到N={、、< Bob，男，，男，1.85>、、< Kathy，女，，女，1.6>、、< Martha，女，，女，1.83>和和< Stephanie，女，，女，1.7>}姓名性别身高(米)类别姓名性别身高(米)类别Kristina女1.6矮Worth 男2.2高Jim男2高Steven 男2.1高Maggie 女1.9中等Debbie 女1.8中等Martha 女1.83中等Todd 男1.95中等Stephanie 女1.7矮Kim 女1.9中等Bob 男1.85中等Amy 女1.8中等Kathy 女1.6矮Wynette女1.75中等Dave 男1.7矮使用下表中的样本数据，对使用下表中的样本数据，对1.6>进行分类。
进行分类 pkNN的例子的例子•对第对第8个记录个记录d=< Dave，男，，男，1.7>，得到，得到N={、、< Dave，男，，男，1.7>、、< Kathy，女，，女，1.6>、、< Martha，女，，女，1.83>和和< Stephanie，女，，女，1.7>}•对第对第9和和10个记录，没变化个记录，没变化•对第对第11个记录个记录d=< Debbie，女，，女，1.8>，得到，得到N={、、< Dave，，男，男，1.7>、、< Kathy，女，，女，1.6>、、< Debbie，女，，女，1.8>和和< Stephanie，女，，女，1.7>}•对第对第12到到14个记录，没变化个记录，没变化•对第对第15个记录个记录d=< Wynette，女，，女，1.75>，得到，得到N={、、< Dave，男，，男，1.7>、、< Kathy，女，，女，1.6>、、< Wynette，女，，女，1.75>和和< Stephanie，女，，女，1.7>}最后的输出元组是最后的输出元组是姓名性别身高(米)类别Kristina女1.6矮Dave 男1.7矮Kathy 女1.6矮Wynette女1.75中等Stephanie 女1.7矮在这五项中，四个属于矮个、一个属于中等。
最终在这五项中，四个属于矮个、一个属于中等最终k kNNNN方法认为方法认为PatPat为矮个 n决策树表示与例子决策树表示与例子•决策树（决策树（Decision Tree）的每个内部结点表示在一个属）的每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布树的最顶层结点是根结点点代表类或类分布树的最顶层结点是根结点•buys_computer的决策树示意的决策树示意 决策树分类算法决策树分类算法 决策树分类的特点决策树分类的特点•决策树分类方法采用自顶向下的递归方式，在决策树的内决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点得到结论所以从决策点向下的分枝，在决策树的叶结点得到结论所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则决策树就对应着一组析取表达式规则•基于决策树的分类算法的一个最大的优点就是它在学习过基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要用户了解很多背景知识（这同时也是它的最大程中不需要用户了解很多背景知识（这同时也是它的最大的缺点），只要训练例子能够用属性的缺点），只要训练例子能够用属性-结论式表示出来，结论式表示出来，就能使用该算法来学习。
就能使用该算法来学习•决策树分类模型的建立通常分为两个步骤：决策树分类模型的建立通常分为两个步骤：–决策树生成决策树生成–决策树修剪决策树修剪 n决策树生成算法决策树生成算法决策树生成算法决策树生成算法算法 Generate_decision_tree(samples, attribute_list) /*决策树生成算法*/输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list输出：一棵决策树1） 创建结点N；（2） IF samples 都在同一个类C THEN 返回N 作为叶结点，以类 C标记；（3） IF attribute_list为空 THEN 返回N作为叶结点，标记为samples中最普通的类；//多数表决（4） 选择attribute_list中具有最高信息增益的属性test_attribute；（5） 标记结点N为test_attribute；（6） FOR each test_attribute中的已知值ai 由结点N长出一个条件为test_attribute=ai的分枝；（7）设si是samples 中test_attribute =ai的样本的集合；//一个划分（8）IF si 为空 THEN 加上一个树叶，标记为samples中最普通的类；（9）ELSE 加上一个由Generate_decision_tree(si， attribute_list-test_attribute)返回的结点； •构造好的决策树的关键在于如何选择好的逻构造好的决策树的关键在于如何选择好的逻辑判断或属性进行树的拓展。
研究结果表明，辑判断或属性进行树的拓展研究结果表明，一般情况下树越小则树的预测能力越强由一般情况下树越小则树的预测能力越强由于构造最小的树是于构造最小的树是NP-难问题，因此只能采难问题，因此只能采取用启发式策略来进行取用启发式策略来进行•属性选择依赖于各种对例子子集的不纯度度属性选择依赖于各种对例子子集的不纯度度量方法，包括信息增益、信息增益比、量方法，包括信息增益、信息增益比、Gini-index、距离度量、、距离度量、J-measure、、G统计、统计、χ2统计、证据权重、最小描述长度、正交法、统计、证据权重、最小描述长度、正交法、相关度和相关度和 Relief等 n 决策树修剪算法决策树修剪算法•基本的决策树构造算法没有考虑噪声，因此生成的基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练例子拟合在有噪声情况下，将决策树完全与训练例子拟合在有噪声情况下，将导致过分拟合导致过分拟合,即对训练数据的完全拟合反而使对现即对训练数据的完全拟合反而使对现实数据的分类预测性能下降实数据的分类预测性能下降•现实世界的数据一般不可能是完美的，可能某些属现实世界的数据一般不可能是完美的，可能某些属性字段上缺值、数据不完整、不准确、含有噪声甚性字段上缺值、数据不完整、不准确、含有噪声甚至是错误的。
至是错误的•剪枝是一种克服噪声的基本技术，同时它也能使树剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解得到简化而变得更容易理解 •有两种基本的剪枝策略：有两种基本的剪枝策略：–预先剪枝：在生成树的同时决定是继续对不纯的训练子集进行划分还预先剪枝：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机–后剪枝：是一种拟合后剪枝：是一种拟合+化简（化简（fitting-and-simplifying）的两阶段方法的两阶段方法 step1:生成与训练数据完全拟合的一棵决策树生成与训练数据完全拟合的一棵决策树; step2:从树的叶子开始剪枝，逐步向根的方向剪剪枝时要用到一个从树的叶子开始剪枝，逐步向根的方向剪剪枝时要用到一个测试数据集合（测试数据集合（Tuning Set或或Adjusting Set）如果存在某个叶子剪）如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机则剪去该叶子；否则停机 •理论上讲，后剪枝好于预先剪枝，但计算复杂度大。
理论上讲，后剪枝好于预先剪枝，但计算复杂度大•剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）要防止过分剪枝（要防止过分剪枝（Over-Pruning）带来的副作用带来的副作用 nID3算法算法pID3是是J.R.Quinlan提出的一个著名决策树生成方法：提出的一个著名决策树生成方法：Ø决策树中每一个非叶结点对应着一个非类别属性，决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值一个叶结点代表从树根树枝代表这个属性的值一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性到叶结点之间的路径对应的记录所属的类别属性值Ø每一个非叶结点都将与属性中具有最大信息量的每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联非类别属性相关联Ø采用信息增益来选择能够最好地将样本分类的属采用信息增益来选择能够最好地将样本分类的属性 n信息增益的计算信息增益的计算 信息增益基于信息论中熵的概念信息增益基于信息论中熵的概念ID3ID3总是选择具有最高总是选择具有最高信息增益的属性作为当前结点的测试属性该属性使得对结信息增益的属性作为当前结点的测试属性。
该属性使得对结果划分的样本分类所需的信息量最小这种信息论方法使得果划分的样本分类所需的信息量最小这种信息论方法使得对一个对象分类所需的期望测试数目达到最小对一个对象分类所需的期望测试数目达到最小, ,并尽量确保找并尽量确保找到一棵简单的数来刻画相关的信息到一棵简单的数来刻画相关的信息 设设S是是s个数据样本的集合，假定类标号属性具有个数据样本的集合，假定类标号属性具有m个不个不同的值同的值,定义定义m个不同类个不同类Ci（（i=1，，2，，…，，m），设），设si是是Ci类中类中的样本数对给定的样本的样本数对给定的样本S所期望的信息值由下式给出：所期望的信息值由下式给出：其中其中pi是任意样本属于是任意样本属于Ci的概率：的概率： si / s •设属性设属性A具有具有v个不同值个不同值{a1, a2, …, av} ，可以用属性，可以用属性A将样本将样本S划分为划分为v个子集个子集{S1, S2, …, Sv} ，其中：，其中： Sj包含包含S中这样一些中这样一些样本，它们在样本，它们在A上具有上具有aj的值。
如果的值如果A作为测试属性，则这作为测试属性，则这些子集对应有包含集合些子集对应有包含集合S的结点生长出来的分支的结点生长出来的分支•设设sij 是是Sj中中Ci类的样本数，则由类的样本数，则由A划分成子集的熵由下式给划分成子集的熵由下式给出：出：其中，期望信息：其中，期望信息： •由期望信息和熵值可以得到对应的信息增益值由期望信息和熵值可以得到对应的信息增益值对应在对应在A上分支将获得的信息增益值为：上分支将获得的信息增益值为： ID3算法计算每个属性的信息增益，并选取具有最高增益算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的属性作为给定集合S的测试属性对被选取的测试属性的测试属性对被选取的测试属性创建一个结点，并以该属性标记，对该属性的每个值创建创建一个结点，并以该属性标记，对该属性的每个值创建一个分支，并据此划分样本一个分支，并据此划分样本 ID3算法例子样本数据样本数据warm_bloodedfeathersfurswimslays_eggs123456101111101100000001010010111100•例子中有例子中有6个样本个样本,5个属性个属性,每个属性取值为每个属性取值为0或或1。
•假设目标分类属性是假设目标分类属性是lays_eggs，有，有4个样本取值为个样本取值为1，，2个样本取个样本取值为值为0为计算每个属性的信息增益，首先计算样本按为计算每个属性的信息增益，首先计算样本按lays_eggslays_eggs分类所需的期望分类所需的期望信息：信息： 类似的，类似的，Gain(feathers)=0.459； Gain(fur)=0.316； Gain(swims)=0.044这种划分的信息增益是：这种划分的信息增益是：接下来计算每个属性的熵观察接下来计算每个属性的熵观察warm_bloodedwarm_blooded的每个样本值的分布：的每个样本值的分布：当当warm_blooded=1warm_blooded=1时，有时，有3 3个个lays_eggslays_eggs =1=1，，2 2个个lays_eggslays_eggs =0=0，即：，即：当当warm_blooded=0warm_blooded=0时，有时，有1 1个个lays_eggslays_eggs =1=1，，0 0个个lays_eggslays_eggs =0=0，即：，即：因此，如果样本按因此，如果样本按warm_blooded划分，对一个给定的样本分类对应划分，对一个给定的样本分类对应的熵为：的熵为： 由于由于feathers在在属性中具有最高的信息增益，所以它首先属性中具有最高的信息增益，所以它首先被选作测试属性。
并以此创建一个结点，数据集被划分成被选作测试属性并以此创建一个结点，数据集被划分成两个子集两个子集 1 0 0 1 1 0 0 1 1 0 0 1 Warm_blooded fur swims lay_eggs T1 =0 Feathers？ 0 0 1 1 1 0 1 0 1 1 0 0 Warm_blooded fur swims lay_eggs T2=1 •根据根据feathers的取值，数据集被划分成两个子集的取值，数据集被划分成两个子集ü对于对于feathers=1的所有元组，其目标分类属性的所有元组，其目标分类属性lays_eggs均为均为1。
所以，得到一个叶子结点所以，得到一个叶子结点 ü对于对于feathers=0的右子树，计算其他属性信息增益：的右子树，计算其他属性信息增益：•Gain(warm_blooded)=0.918•Gain(fur)=0.318•Gain(swims)=0.318•根据根据warm_blooded的取值，的取值，左右子树均可得到叶子左右子树均可得到叶子结点，结束结点，结束Lays_eggs=1feathersWarm_blooded=1=0=1=0Lays_eggs=1Lays_eggs=0 ID3算法的性能分析算法的性能分析•ID3算法的假设空间包含所有的决策树，它是关于现有属性的有限离算法的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间所以散值函数的一个完整空间所以ID3算法避免了搜索不完整假设空间算法避免了搜索不完整假设空间的一个主要风险：假设空间可能不包含目标函数的一个主要风险：假设空间可能不包含目标函数•ID3算法在搜索的每一步都使用当前的所有训练样例，大大降低了对算法在搜索的每一步都使用当前的所有训练样例，大大降低了对个别训练样例错误的敏感性因此，通过修改终止准则，可以容易地个别训练样例错误的敏感性。
因此，通过修改终止准则，可以容易地扩展到处理含有噪声的训练数据扩展到处理含有噪声的训练数据•ID3算法在搜索过程中不进行回溯所以，它易受无回溯的爬山搜索算法在搜索过程中不进行回溯所以，它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优而不是全局最优中的常见风险影响：收敛到局部最优而不是全局最优•ID3算法只能处理离散值的属性算法只能处理离散值的属性•信息增益度量存在一个内在偏置，它偏袒具有较多值的属性例如，信息增益度量存在一个内在偏置，它偏袒具有较多值的属性例如，如果有一个属性为日期，那么将有大量取值，这个属性可能会有非常如果有一个属性为日期，那么将有大量取值，这个属性可能会有非常高的信息增益假如它被选作树的根结点的决策属性则可能形成一颗高的信息增益假如它被选作树的根结点的决策属性则可能形成一颗非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的分类性能可能会相当差分类性能可能会相当差•ID3算法增长树的每一个分支的深度，直到恰好能对训练样例完美地算法增长树的每一个分支的深度，直到恰好能对训练样例完美地分类当数据中有噪声或训练样例的数量太少时，产生的树会过渡拟分类。
当数据中有噪声或训练样例的数量太少时，产生的树会过渡拟合训练样例合训练样例 C4.5算法对算法对ID3的主要改进的主要改进•C4.5算法是从算法是从ID3算法演变而来，除了拥有算法演变而来，除了拥有ID3算法算法的功能外，的功能外，C4.5算法引入了新的方法和增加了新的算法引入了新的方法和增加了新的功能：功能：•用信息增益比例的概念；用信息增益比例的概念；•合并具有连续属性的值；合并具有连续属性的值；•可以处理具有缺少属性值的训练样本；可以处理具有缺少属性值的训练样本；•通过使用不同的修剪技术以避免树的过度拟合；通过使用不同的修剪技术以避免树的过度拟合；•K交叉验证；交叉验证；•规则的产生方式等规则的产生方式等 p信息增益比例信息增益比例是在信息增益概念基础上发展起来的，是在信息增益概念基础上发展起来的，一个属性的信息增益比例用下面的公式给出：一个属性的信息增益比例用下面的公式给出：其中其中 假如以属性假如以属性A的值为基准对样本进行分割的化，的值为基准对样本进行分割的化，Splitl (A) 就是前面就是前面熵的概念熵的概念 p合并具有连续值的属性合并具有连续值的属性，对于连续属性值，，对于连续属性值，C4.5其处理过程如下：其处理过程如下：–根据属性的值，对数据集排序；根据属性的值，对数据集排序；–用不同的阈值将数据集动态的进行划分；用不同的阈值将数据集动态的进行划分；–当输出改变时确定一个阈值；当输出改变时确定一个阈值；–取两个实际值中的中点作为一个阈值；取两个实际值中的中点作为一个阈值；–取两个划分，所有样本都在这两个划分中；取两个划分，所有样本都在这两个划分中；–得到所有可能的阈值、增益及增益比；得到所有可能的阈值、增益及增益比；–在每一个属性会变为取两个取值，即小于阈值或大于在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。
等于阈值 •简单地说，针对属性有连续数值的情况，则在训简单地说，针对属性有连续数值的情况，则在训练集中可以按升序方式排列如果属性练集中可以按升序方式排列如果属性A共有共有n种种取值，则对每个取值取值，则对每个取值vj（（j =1，，2，，… ，，n），将所），将所有记录进行划分：一部分小于有记录进行划分：一部分小于vj；一部分则大于或；一部分则大于或等于等于vj 针对每个针对每个vj计算划分对应的增益比率，选计算划分对应的增益比率，选择增益最大的划分对属性择增益最大的划分对属性A进行离散化进行离散化 p处理含有未知属性值的训练样本处理含有未知属性值的训练样本处理含有未知属性值的训练样本处理含有未知属性值的训练样本 C4.5处理的样本中可以含有未知属性值，其处理方法是处理的样本中可以含有未知属性值，其处理方法是用最常用的值替代或者是将最常用的值分在同一类中用最常用的值替代或者是将最常用的值分在同一类中具体采用概率的方法，依据属性已知的值，对属性和每具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取得这些概率，取得这些概率依一个值赋予一个概率，取得这些概率，取得这些概率依赖于该属性已知的值。
赖于该属性已知的值p规则的产生规则的产生 一旦树被建立，就可以把树转换成一旦树被建立，就可以把树转换成if-then规则规则存规则规则存储于一个二维数组中，每一行代表树中的一个规则，即储于一个二维数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径表中的每列存放着树中的结从根到叶之间的一个路径表中的每列存放着树中的结点 C4.5算法例子算法例子样本数据样本数据OutlookTemperatureHumidityWindPlayTennisSunnyHot85falseNoSunnyHot90trueNoOvercastHot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercastCool65trueYesSunnyMild95falseNoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercastMild90trueYesOvercastHot75falseYesRainMild80trueNolOutlook(Outlook(离散属性离散属性) )lTemperature(Temperature(离散属性离散属性) )lHumidity(Humidity(连续属性连续属性) )lWind(Wind(离散属性离散属性) )lPlayTennisPlayTennis( (类别属性类别属性) ) •（（1））首先对首先对Humidity进行属性离散化，针对上面的训练集合，通过检进行属性离散化，针对上面的训练集合，通过检测每个划分而确定最好的划分在测每个划分而确定最好的划分在75处，则这个属性的范围就变为处，则这个属性的范围就变为{（（<=75 ，，>75））}。
•（（2）计算目标属性）计算目标属性PlayTennis分类的期望信息：分类的期望信息： 接下来计算属性接下来计算属性Outlook的的SplitI值值:ü对于对于Outlook=Sunny,Outlook=Sunny,有有ü对于对于Outlook= Outlook= OvercastOvercast, ,有有ü对于对于Outlook=Rain,Outlook=Rain,有有对于决策属性对于决策属性PlayTennisPlayTennis来说来说, ,计算计算OutlookOutlook属性每个分布的期望信息属性每个分布的期望信息 选取最大的选取最大的GainRatio，根据，根据Outlook的取值，可以得到三的取值，可以得到三个分支再扩展各分枝节点，得到最终的决策树再扩展各分枝节点，得到最终的决策树 因此因此, ,可得到可得到OutlookOutlook属性的熵属性的熵: :对应的信息增益为对应的信息增益为: :最后得到信息增益比例为最后得到信息增益比例为: :0.0483 Humidity)GainRatio(=0.0248 e)TemperaturGainRatio(=；049. 0)(=；windyGainRatio同理同理, ,可计算出可计算出 TemperatureHumidityWindy PlayTennisHot＞＞75falseNoHot＞＞75trueNoMild＞＞75falseNoCool≤75falseYesMild≤75trueYesTemperatureHumidityWindyPlayTennisMild ＞＞75falseYesCool ＞＞75falseYesCool≤ 75trueNoMild＞＞ 75falseYesMild＞＞ 75trueNoTemperatureHumidityWindyPlayTennisHot＞＞75falseYesCool ≤ 75trueYesMild＞＞75trueYesHot≤75falseYes=RainOutlook？=Sunny=OvercastT1T3T2对于第一棵子树，对于第一棵子树，1 Humidity)GainRatio(=0.244 e)TemperaturGainRatio(=；0206. 0)(=；windyGainRatio，选择，选择HumidityHumidity作为决策属性，得到两个叶结点。
作为决策属性，得到两个叶结点对于第二棵子树，所有样本都属于同一类（对于第二棵子树，所有样本都属于同一类（PlayTennisPlayTennis=Yes=Yes），），直接得到叶结点直接得到叶结点对于第三棵子树，对于第三棵子树，0.446 Humidity)GainRatio(=0.0206 e)TemperaturGainRatio(=； . 1)(=；windyGainRatio，选择，选择WindWind作为决策属性，得到两个叶结点作为决策属性，得到两个叶结点 =RainOutlook？=Sunny=OvercastT1T3T2YesYesYesYesNoNoWind？=true=falseYesYesNoNoHumidity？＞75≤75最终生成的决策树最终生成的决策树: : •贝叶斯方法提供了一种概率手段贝叶斯方法提供了一种概率手段,基于如下的假定基于如下的假定:待考察的量遵循某概率分布待考察的量遵循某概率分布,且可根据这些概率及且可根据这些概率及已观察到的数据进行推理已观察到的数据进行推理,以作出最优的决策这以作出最优的决策这个分析过程开始是先给出一个待分析数据集的概个分析过程开始是先给出一个待分析数据集的概率分布。
因为这个概率分布是没有考虑任何数据率分布因为这个概率分布是没有考虑任何数据而给出的，所以称而给出的，所以称先验分布这个新的数据集将先验分布这个新的数据集将先验分布修正后得到后验分布先验分布修正后得到后验分布贝叶斯理论提供贝叶斯理论提供了一种计算假设概率的方法了一种计算假设概率的方法,基于假设的先验概率基于假设的先验概率,给定假设下观察到不同数据的概率以及观察到的给定假设下观察到不同数据的概率以及观察到的数据本身先验概率和后验概率数据本身先验概率和后验概率贝叶斯分类贝叶斯分类 •定定义义 设设X是是类类标标号号未未知知的的数数据据样样本本设设H为为某某种种假假定定，，如如数数据据样样本本X属属于于某某特特定定的的类类C对对于于分分类类问问题题，，我我们们希希望望确确定定P(H|X)，，即即给给定定观观测测数数据据样样本本X，，假假定定H成成立立的的概概率率贝贝叶叶斯斯定定理理给给出出了了如如下下计计算算P(H|X)的简单有效的方法的简单有效的方法:•P(H)是是先先验验概概率率，，或或称称H的的先先验验概概率率P(X|H)代代表表假假设设H成成立立的的情情况况下下，，观观察察到到X的的概概率率。
P(H|X)是是后验概率后验概率，，或称条件或称条件X下下H的后验概率的后验概率 •例例如如，，假假定定数数据据样样本本域域由由水水果果组组成成，，用用它它们们的的颜颜色色和和形形状状来来描描述述假假定定X表表示示红红色色和和圆圆的的，，H表表示示假假定定X是是苹苹果果，，则则P(H|X)反反映映当当我我们们看看到到X是是红红色色并并是是圆圆的的时时，，我我们们对对X是是苹果的确信程度苹果的确信程度•贝贝叶叶斯斯分分类类器器对对两两种种数数据据具具有有较较好好的的分分类类效效果果：：一一种种是是完完全全独独立立的的数数据据，，另另一一种种是是函函数数依赖的数据依赖的数据 朴素贝叶斯分类朴素贝叶斯分类朴素贝叶斯分类的工作过程如下：朴素贝叶斯分类的工作过程如下：•(1) 假假设设有有一一组组m个个元元素素的的样样本本S= {S1, S2, … , Sm}（（训训练练样样本本集集）），，其其中中每每个个数数据据样样本本Si用用一一个个n维维特特征征向向量量X= {x1, x2, … , xn}表示，分别与样本属性表示，分别与样本属性A1, A2, … ,An相对应•(2) 假假定定有有k个个类类C1, C2, …, Ck，，每每个个样样本本属属于于其其中中一一个个类类。
给给定定一一个个数数据据样样本本X（（它它的的类类是是未未知知的的）），，可可以以用用最最高高的的后后验验概概率率（（条条件件X下下））来来预预测测X的的类类也也就就是是说说，，朴朴素素贝贝叶叶斯斯分分类类将将未未知知的的样样本本分分配配给给类类Ci（（1≤i≤k））当当且且仅仅当当P(Ci|X)>P(Cj|X)，，对对任任意意的的j=1，，2，，…，，k，，j≠i这这样样，，最最大大化化P(Ci|X)其其P(Ci|X)最最大大的的类类Ci称称为为最最大大后后验验假假定定根根据据贝贝叶斯定理叶斯定理 •(3) 由由于于P(X)对对于于所所有有类类为为常常数数，，只只需需要要P(X|Ci)*P(Ci)最最大大即即可可如如果果Ci类类的的先先验验概概率率未未知知，，则则通通常常假假定定这这些些类类是是等等概概率率的的，，即即P(C1)=P(C2)=…=P(Ck)，，因因此此问问题题就就转转换换为为对对P(X|Ci)的的最最大大化化（（P(X|Ci)常常被被称称为为给给定定Ci时时数数据据X的的似似然然度度，，而而使使P(X|Ci)最最大大的的假假设设Ci称称为为最最大大似似然然假假设设））。
否否则则，，需需要要最最大大化化P(X|Ci)*P(Ci)注注意意，，类类的的先先验验概概率率可可以以用用P(Ci)=si /m计计算算，，其其中中si是是类类Ci中中的的训训练练样样本本数数，，而而m是训练样本总数是训练样本总数 •(4) 给给定定具具有有许许多多属属性性的的数数据据集集，，计计算算P(X|Ci)的的开开销销可可能能非非常常大大为为降降低低计计算算P(X|Ci)的的开开销销，，可可以以做做类类条条件件独独立立的的朴朴素素假假定定（（零零假假设设）），，假假定定样样本本属属性性值值之之间间条条件件独独立立，，即即在在属属性性间间，，不不存存在在依依赖赖关关系系利利用用这这个个假假定定，，可可以以用用下下式式来来计计算算P(X|Ci)其中其中xt是样本是样本X的属性值，概率的属性值，概率P(xt|Ci)可由训练样本集来可由训练样本集来估算 •(5) 对对未未知知样样本本X分分类类，，也也就就是是对对每每个个类类Ci，，计计算算P(X|Ci)*P(Ci)样样本本X被被指指派派到到类类Ci，，当当且且仅仅当当P(Ci|X)>P(Cj|X)，，1≤j≤m，，j≠i，，换换言言之，之，X被指派到其被指派到其P(X|Ci)*P(Ci)最大的类。
最大的类 例：已知例：已知7个四元样本训练数据集个四元样本训练数据集样本样本属性属性1（（A1））属性属性2 （（A2））属性属性3 （（A3））类类（（C））11211200113212241212501216222271031预测新样本预测新样本X={1，，2，，2，，C=？？}；对于每个样本，；对于每个样本， A1 ，，A2 ，，A3是输入元，是输入元，C是输出分类是输出分类 在在本本例例中中，，仅仅有有两两个个类类，，C=1或或C=2，，故故只只需需找找出出P(X|Ci)*P(Ci) （（i=1，，2）中的最大值中的最大值ü先计算每个类的先验概率先计算每个类的先验概率P(Ci):P(C=1)=4/7=0.5714; P(C=2)=3/7=0.4286ü用训练集计算所给新样本用训练集计算所给新样本X={1，，2，，2，，C=？？}的每个属性值的每个属性值的条件概率的条件概率P(Xt|Ci):P(A1=1|C=1 )=2/4=0.50; P(A1=1|C=2 )=1/3=0.33P(A2=2|C=1 )=1/4=0.25; P(A2=2|C=2 )=2/3=0.66P(A3=2|C=1 )=1/4=0.25; P(A3=2|C=2 )=2/3=0.66ü在零假设下在零假设下,条件概率条件概率P(X|Ci)为为:P(X|C=1)= P(A1=1|C=1 )* P(A2=2|C=1 )* P(A3=2|C=1 )=0.03125P(X|C=2)= P(A1=1|C=2 )* P(A2=2|C=2 )* P(A3=2|C=2 )=0.14375 ü最后最后,用相应的条件概率用相应的条件概率P(X|Ci)乘以先验概率乘以先验概率P(Ci) :P(C1|X)≈ P(X|C=1)*P(C=1)=0.03125*0.5714=0.0179 P(C2|X)≈ P(X|C=2)*P(C=2)=0.14375*0.4286=0.0616ü最大值为最大值为P(C2|X) =0.0616,于是预测新样本于是预测新样本X={1，，2，，2，，C=？？}属于类属于类C=2。
朴素贝叶斯分类举例Ageincomestudentcredit_ratingbuy_computer1<=30 High NoFairNo2<=30 High NoExcellentNo331~40 High NoFairYes4>40MediumNoFairYes5>40LowYesFairYes6>40LowYesExcellentNo731~40LowYesExcellentYes8<=30MediumNoFairNo9<=30LowYesFairYes10>40MediumYesFairYes11<=30MediumYesExcellentYes1231~40MediumNoExcellentYes1331~40 High YesFairYes14<=30MediumNoExcellentNoü数据样本用属性数据样本用属性age，，income，，student和和credit_rating描述ü类标号属性类标号属性buys_computer具有两个不同值（即具有两个不同值（即{yes，，no}）设设C1对应于类对应于类yes，，而而C2对应于类对应于类 “no”ü希望分类的未知样本为希望分类的未知样本为:X=(<=30，，medium，，yes，，fair，，C=?)。
朴素贝叶斯分类举例(1) 需要最大化需要最大化P(X|Ci)*P(Ci)，，i=1，，2每个类的先验概率每个类的先验概率P(Ci)可以根据训练样本计算：可以根据训练样本计算：P(buys_computer=”yes”)=9/14=0.643，，P(buys_computer=”no”)=5/14=0.357 (2) 为计算为计算P(X|Ci)，，i=1，，2，，我们计算下面的条件概率：我们计算下面的条件概率：P(age<=30|buys_computer=”yes” )=2/9=0.222，，P(age<=30”|buys_computer=”no” )=3/5=0.600，，P(income=”medium”|buys_computer=”yes” )=4/9=0.444，，P(income=”medium”|buys_computer=”no” )=2/5=0.400，，P(student=”yes”|buys_computer=”yes” )=6/9=0.677，，P(student=”yes”|buys_computer=”no” )=1/5=0.200，，P(credit_rating=”fair”|buys_computer=”yes” )=6/9=0.667P(credit_rating=”fair”|buys_computer=”no” )=2/5=0.400。
(3) 假设条件独立性，使用以上概率，得到：假设条件独立性，使用以上概率，得到：P(X|buys_computer=”yes” )=0.222*0.444*0.667*0.667=0.044P(X|buys_computer=”no” )=0.600*0.400*0.200*0.400=0.019 P(X|buys_computer=”yes” )*P(buys_computer=”yes” ) =0.044*0.643=0.028 P(X|buys_computer=”no” )*P(buys_computer=”no” )= 0.019*0.357=0.007 因此，对于样本因此，对于样本X，，朴素贝叶斯分类预测朴素贝叶斯分类预测buys_computer=”yes” • 常见的采用规则表示的分类器构造方法有常见的采用规则表示的分类器构造方法有:–利用规则归纳技术直接生成规则利用规则归纳技术直接生成规则–利利用用决决策策树树方方法法先先生生成成决决策策树树，，然然后后再再把把决决策策树树转转换换为规则；为规则；–使用粗糙集方法生成规则；使用粗糙集方法生成规则；–使用遗传算法中的分类器技术生成规则等。
使用遗传算法中的分类器技术生成规则等• 本本节节将将只只讨讨论论规规则则归归纳纳方方法法我我们们这这里里讨讨论论的的规规则则归归纳纳算算法法，，可可以以直直接接学学习习规规则则集集合合，，这这一一点点与与决决策策树树方方法法、、遗遗传传算法有两点关键的不同算法有两点关键的不同–它它们们可可学学习习包包含含变变量量的的一一阶阶规规则则集集合合：：这这一一点点很很重重要要，，因为一阶子句的表达能力比命题规则要强得多因为一阶子句的表达能力比命题规则要强得多–这这里里讨讨论论的的算算法法使使用用序序列列覆覆盖盖算算法法：：一一次次学学习习一一个个规规则，以递增的方式形成最终的规则集合则，以递增的方式形成最终的规则集合规则归纳规则归纳 •规则归纳有四种策略：减法、加法，先加后减、先减后加规则归纳有四种策略：减法、加法，先加后减、先减后加–减减法法策策略略：：以以具具体体例例子子为为出出发发点点，，对对例例子子进进行行推推广广或或泛泛化化，，推推广广即即减减除除条条件件（（属属性性值值））或或减减除除合合取取项项（（为为了了方方便便，，我我们们不不考考虑虑增增加加析析取取项项的的推推广广）），，使使推推广广后后的的例例子子或或规规则则不不覆盖任何反例。
覆盖任何反例–加加法法策策略略：：起起始始假假设设规规则则的的条条件件部部分分为为空空（（永永真真规规则则）），，如如果果该该规规则则覆覆盖盖了了反反例例，，则则不不停停地地向向规规则则增增加加条条件件或或合合取取项，直到该规则不再覆盖反例项，直到该规则不再覆盖反例–先先加加后后减减策策略略：：由由于于属属性性间间存存在在相相关关性性，，因因此此可可能能某某个个条条件件的的加加入入会会导导致致前前面面加加入入的的条条件件没没什什么么作作用用，，因因此此需需要要减减除前面的条件除前面的条件–先先减减后后加加策策略略：：道道理理同同先先加加后后减减，，也也是是为为了了处处理理属属性性间间的的相关性•典型的规则归纳算法有典型的规则归纳算法有AQ、、CN2和和FOIL等 AQ算法v AQ算算法法利利用用覆覆盖盖所所有有正正例例，，排排斥斥所所有有反反例例的的思思想想来来寻寻找找规规则则比比较较典典型型的的有有Michalski的的AQ11方方法法，，洪洪家家荣荣改改进进的的AQ15方方法法以以及及洪洪家家荣荣的的AE5方法vAQR是是一一个个基基于于最最基基本本AQ算算法法的的归归纳纳算算法法,采采用用了了基基本本AQ算算法法，，和和其其它它方方法法比比较较而而言言，，AQR更加简单一些。
更加简单一些 CN2算法描述v CN2使使用用一一种种基基于于噪噪音音估估计计的的启启发发式式方方法法，，可可不不用用对对所所有有的的训训练练样样本本进进行行正正确确的的区区分分，，但但是是规规约约出出的的规规则则在在对对新新数数据据的的处处理理上上有有很很好好的的表现vCN2结结合合了了ID3算算法法处处理理数数据据的的效效率率和和处处理理噪噪音数据的能力，以及音数据的能力，以及AQ算法家族的灵活性算法家族的灵活性 q分类数据预处理分类数据预处理•分类的效果一般和数据的特点有关，有的数据噪声分类的效果一般和数据的特点有关，有的数据噪声大，有的有空缺值，有的分布稀疏，有的字段或属大，有的有空缺值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值性间相关性强，有的属性是离散的而有的是连续值或混合式的目前普遍认为不存在某种方法能适合或混合式的目前普遍认为不存在某种方法能适合于各种特点的数据因此，在分类以前需要做一些于各种特点的数据因此，在分类以前需要做一些数据的预处理数据的预处理– 数据清理数据清理•主要是消除或减少数据噪声和处理空缺值主要是消除或减少数据噪声和处理空缺值。
与分类有关的问题与分类有关的问题 q分类数据预处理分类数据预处理– 特征选择特征选择•从已知一组特征集中按照某一准则选择出有很从已知一组特征集中按照某一准则选择出有很好的区分特性的特征子集好的区分特性的特征子集•或按照某一准则对特征的分类性能进行排序，或按照某一准则对特征的分类性能进行排序，用于分类器的优化设计用于分类器的优化设计 –数据变换数据变换•就是通过平滑、聚集、数据概化、规范化、特征就是通过平滑、聚集、数据概化、规范化、特征构造等手段将数据转化为适合于挖掘的形式构造等手段将数据转化为适合于挖掘的形式–平滑：去掉数据中的噪声平滑：去掉数据中的噪声–聚集：对数据进行汇总和聚集聚集：对数据进行汇总和聚集–数据概化：使用概念分层，用高层次的概念替换低层数据概化：使用概念分层，用高层次的概念替换低层次的次的““原始原始””数据–规范化：将属性数据按比例缩放，使之落入一个特定规范化：将属性数据按比例缩放，使之落入一个特定的区间–特征构造：构造新的属性值，帮助数据挖掘过程特征构造：构造新的属性值，帮助数据挖掘过程q分类数据预处理分类数据预处理 q分类器性能的表示分类器性能的表示•对同样的数据，不同的分类器算法可能产生不同的对同样的数据，不同的分类器算法可能产生不同的分类结果。
分类结果姓名性别身高(米)分类结果1分类结果2Kristina女1.6矮中等Jim男2高中等Maggie 女1.9中等高Martha 女1.83中等高Stephanie 女1.7矮中等Bob 男1.85中等中等Kathy 女1.6矮中等Dave 男1.7矮中等Worth 男2.2高高Steven 男2.1高高Debbie 女1.8中等中等Todd 男1.95中等中等Kim 女1.9中等高Amy 女1.8中等中等Wynette女1.75中等中等 q分类器性能的表示分类器性能的表示•分类器性能的评价方法类似信息检索系统的评价方法，可以分类器性能的评价方法类似信息检索系统的评价方法，可以采用采用OC曲线和曲线和ROC曲线、混淆矩阵等曲线、混淆矩阵等•定义定义4-3 给定一个类给定一个类Cj和一个数据库元组和一个数据库元组ti，，ti可能被分类器可能被分类器判定为属于判定为属于Cj或不属于或不属于Cj，其实，其实ti本身可能属于本身可能属于Cj或不属于或不属于Cj，这样就会产生如下一些情况：，这样就会产生如下一些情况：–真正真正: 判定判定ti在在Cj中，实际上的确在其中中，实际上的确在其中–假正假正: 判定判定ti在在Cj中，实际上不在其中。
中，实际上不在其中–真负真负: 判定判定ti不在不在Cj中，实际上不在其中中，实际上不在其中–假负假负: 判定判定ti不在不在Cj中，实际上的确在其中中，实际上的确在其中•在上述定义的基础上，人们经常使用在上述定义的基础上，人们经常使用OC曲线和曲线和ROC曲线表曲线表示示“假正假正”和和“真正真正”的关系OC曲线通常用于通信领域曲线通常用于通信领域来测试误报率来测试误报率OC曲线的水平轴一般表示曲线的水平轴一般表示“假正假正”的百分的百分比，另外一个轴表示比，另外一个轴表示“真正真正”的百分比的百分比 •混淆矩阵是另外一种表示分类准确率的方法假定有混淆矩阵是另外一种表示分类准确率的方法假定有m个个类，混淆矩阵是一个类，混淆矩阵是一个 m m 的矩阵，的矩阵，Cij表明了表明了D中被分到中被分到类类Cj但实际类别是但实际类别是Ci的元组的数量显然地，最好的解决的元组的数量显然地，最好的解决方案是对角线以外的值为全零方案是对角线以外的值为全零•假定分类结果假定分类结果1是实际情况，而分类结果是实际情况，而分类结果2是某分类算法的是某分类算法的结果，下表给出了对它评价的混淆距阵结果，下表给出了对它评价的混淆距阵。
混淆矩阵示例混淆矩阵示例实 际 分分 类矮矮中等中等高高矮矮040中等中等053高高012 分类器性能的评估•分类器的性能与所选择的测试集和训练集有直接的关分类器的性能与所选择的测试集和训练集有直接的关系一般，先用一部分数据建立模型，再用剩余的数系一般，先用一部分数据建立模型，再用剩余的数据来测试和训练该模型如果使用相同的训练和测试据来测试和训练该模型如果使用相同的训练和测试集，则模型的准确度就很难令人信服保持法和交叉集，则模型的准确度就很难令人信服保持法和交叉验证是两种基于给定数据随机选样划分的、常用的评验证是两种基于给定数据随机选样划分的、常用的评估分类方法准确率的技术估分类方法准确率的技术1）保持法）保持法 把给定的数据随机地划分成两个独立的集合：把给定的数据随机地划分成两个独立的集合：训练集和测试集通常，三分之一的数据分配到训训练集和测试集通常，三分之一的数据分配到训练集，三分之二分配到测试集使用训练集得到分练集，三分之二分配到测试集使用训练集得到分类器，其准确率用测试集评估类器，其准确率用测试集评估 （（2）交叉验证）交叉验证 先把数据随机分成不相交的先把数据随机分成不相交的n份，每份大小基份，每份大小基本相等，训练和测试都进行本相等，训练和测试都进行n次。
比如，如果把数次比如，如果把数据分成据分成10份，先把第一份拿出来放在一边用作模型份，先把第一份拿出来放在一边用作模型测试，把其他测试，把其他9份合在一起来建立模型，然后把这份合在一起来建立模型，然后把这个用个用90%的数据建立起来的模型用上面放在一边的的数据建立起来的模型用上面放在一边的第一份数据做测试这个过程对每一份数据都重复第一份数据做测试这个过程对每一份数据都重复进行一次，得到进行一次，得到10个不同的错误率最后把所有数个不同的错误率最后把所有数据放在一起建立一个模型，模型的错误率为上面据放在一起建立一个模型，模型的错误率为上面10个错误率的平均个错误率的平均。