数据挖掘-分类方法(修改)

第四章分类方法小组成员：庞春霞万凯明委佩涛彭朋内容回顾基本概念贝叶斯分类规则归纳总结KDD的总体过程数据挖掘——知识挖掘的核心数据清理数据集成数据库数据仓库任务相关数据选择数据挖掘模式评估分类为什么要进行分类？分类是数据挖掘中的重要任务之一很多数据挖掘问题都可以转化为分类问题分类的目的在于用分类方法构建一个分类函数或分类模型（分类器），该分类器可以将输入数据（数据库中的数据项）映射到给定类别中的一个类别。分类器的构造依据统计方法：贝叶斯方法和非参数法等机器学习方法：决策树法和规则归纳法神经网络方法其他：粗糙集等数据分类的两步过程（1）第一步，建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以用分类规则、判定树或数学公式的形式提供第一步——建立模型训练数据集分类算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分类规则数据分类的两步过程（2）第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况第二步——用模型进行分类分类规则测试集未知数据(Jeff,Professor,4)Tenured?内容回顾基本概念贝叶斯分类规则归纳总结朴素贝叶斯分类简介本质是一个分类器（分类模型，分类算法均为一个意思）基础是概率推理先验概率：根据以往经验和分析得到的概率客观先验概率：由历史资料得到主观先验概率：由主观经验得到（水果，圆的，甜的，红或绿的是苹果）朴素贝叶斯分类特点：基于独立假设需要知道先验概率按照获得的信息对先验概率进行修正分类决策存在错误率朴素贝叶斯分类模型样本域：水果X:红的和圆的（颜色属性取值为红，形状属性取值为圆）H:是苹果（苹果是一个类别）P(H|X):反应了当知道水果是红的并且是圆的，则它是苹果的概率（置信程度）。这是后验概率P(H):是先验概率朴素贝叶斯分类过程实例：性别分类问题描述：通过一些测量的特征，包括身高、体重、脚的尺寸，判定一个人是男性还是女性。

朴素贝叶斯分类过程问题数学表示：类别:可以从C1到Cn，在我们的问题中即C1=男性C2=女性样本表示：每个数据样本（某元组）用一个n维特征向量X={x1，x2，……，xn}表示，分别描述对n个属性A1，A2，……，An样本的n个度量。比如样本X={x1,x2,x3}={1米73,60千克，20厘米}（分别对应身高体重和脚长三个属性的度量）分类模型：

第一步得到先验概率训练数据集：得到先验概率，按照频率来算。P(C1)=0.5P(C2)=0.5性别身高(英尺)体重(磅)脚的尺寸(英寸)男618012男5.92(5'11")19011男5.58(5'7")17012男5.92(5'11")16510女51006女5.5(5'6")1508女5.42(5'5")1307女5.75(5'9")1509第二步预测X属于具有最高后验概率的类朴素贝叶斯分类将未知的样本分配给类Ci（1≤i≤m）当且仅当P(Ci|X)>P(Cj|X)，对任意的j=1，2，…，m，j≠i。这样，最大化P(Ci|X)。其P(Ci|X)最大的类Ci称为最大后验假定。第二步预测X属于具有最高后验概率的类在这个性别分类问题中即：比较P(C1|X)和P(C2|X)的值(X={6,130,8})，

采用贝叶斯公式：P(C1|X)=P(X|C1)*P(C1)/P(X)其中

先验概率P(C1)=0.5 P(X|C1)=?(还未知) P(X)对于所有类来说都是一样的即P(X)=P(C1)*P(X|C1)+P(C2)*P(X|C2)（全概率公式）所以为了得到最大后验假定，问题转化为求P(X|C1)的最大值未分类的样本：性别身高(英尺)体重(磅)脚的尺寸(英寸)Sample（？）61308第三步求P(X|C1)

问题就转换为对P(X|Ci)的最大化（P(X|Ci)常被称为给定Ci时数据X的似然度，而使P(X|Ci)最大的假设Ci称为最大似然假设）。因为类的条件是相互独立的所以可以用如下公式计算：在我们的问题里面比如X={6英尺，130磅，8英寸}P(X|C1)=P(x1|C1)*P(x2|C1)*P(x3|C1)表示C1时样本X的似然度第三步求P(X|C1)

xK的值可能有两种情况：（1）离散值则P(xk|Ci)=sik|si，其中sik是在属性Ak上具有值xk的类Ci的训练样本数，而si是Ci中的训练样本数x1=6英尺即P(x1|C1)=训练样本中身高为6英尺并且属于男性的样本数/男性的样本数=1/4；此处这么举例，是假设身高的取值都是离散值数据性别身高(英尺)体重(磅)脚的尺寸(英寸)男618012男5.92(5'11")19011男5.58(5'7")17012男5.92(5'11")16510女51006女5.5(5'6")1508女5.42(5'5")1307女5.75(5'9")1509第三步求P(X|C1)

xK的值可能有两种情况：（2）连续值如果Ak是连续值属性，则通常假定该属性服从高斯分布。因而，

是高斯分布函数，分别为平均值和标准差。性别身高(英尺)体重(磅)脚的尺寸(英寸)男618012男5.92(5'11")19011男5.58(5'7")17012男5.92(5'11")16510女51006女5.5(5'6")1508女5.42(5'5")1307女5.75(5'9")1509第三步求P(X|C1)

假设训练集样本的特征满足高斯分布，得到下表：性别均值(身高)方差(身高)均值(体重)方差(体重)均值(脚的尺寸)方差(脚的尺寸)男性5.8553.5033e-02176.251.2292e+0211.259.1667e-01女性5.41759.7225e-02132.55.5833e+027.51.6667e+00性别身高(英尺)体重(磅)脚的尺寸(英寸)Sample（？）61308第三步求P(X|C1)

分别求得类别C1和C2的似然度男性似然度计算项：

女性似然度计算项：男性和女性的似然度：可以看到女性的似然度更大，更具贝叶斯分类模型我们显然可以得到，女性的后验概率更大，所以该样本分类为女性。内容回顾基本概念贝叶斯分类规则归纳总结常见的采用规则表示的分类器构造方法利用规则归纳技术直接生成规则；利用决策树方法先生成决策树，然后再把决策树转换为规则；使用粗糙集方法生成规则；使用遗传算法中的分类器技术生成规则等。规则归纳规则归纳有四种策略：减法、加法、先加后减、先减后加策略。减法策略：以具体例子为出发点，对例子进行推广或泛化，推广即减除条件（属性值）或减除合取项（为了方便，我们不考虑增加析取项的推广），使推广后的例子或规则不覆盖任何反例。加法策略：起始假设规则的条件部分为空（永真规则），如果该规则覆盖了反例，则不停地向规则增加条件或合取项，直到该规则不再覆盖反例。规则归纳先加后减策略：由于属性间存在相关性，因此可能某个条件的加入会导致前面加入的条件没什么作用，因此需要减除前面的条件。先减后加策略：道理同先加后减，也是为了处理属性间的相关性。典型的规则归纳算法有AQ、CN2和FOIL等。AQ算法利用覆盖所有正例，排斥所有反例的思想来寻找规则。比较典型的有AQ11方法，AQ15方法以及AE5方法。AQR是一个基于最基本AQ算法的归纳算法。很多的算法都采用了基本AQ算法，如AQ11和GEM。但AQR更为简单，AQ11使用了一种复杂的包括置信度的规则推导方法。AQ算法AQR为每一个分类推导出一条规则，每一条规则形式如下：if<cover>thenpredict<class>在一个属性上的基本测试被称为一个选择值（Selector）。例子：<Cloudy=yes>

<Temp>60>AQR允许测试做{=，≤，≥，≠}AQR算法相关定义

选择值（Selector）的合取被称为复合（Complex），Complexes之间的析取被称为覆盖（Cover）。如果一个表达式对某个样本为真，则我们称其为对这个样本的一个覆盖。这样，一个空Complex覆盖所有的样本，而一个空Cover不覆盖任何样本。AQR算法相关定义

在AQR中，一个新样本被区分是看其由哪个规则推导出来的。

如果该样本只满足一条规则，则这个样本就属于这条规则；如果该样本满足多条规则，则被这些规则所预测的最频繁的分类被赋予这条规则；如果该样本不属于任何规则，则其分类为样本集中最频繁的分类。AQR算法相关定义AQR算法描述

算法4-5AQR：输入：正例样本POS；反例样本NEG输出：覆盖COVERAQR算法描述（1）COVER=Φ；//初始化COVER为空集Φ（2）WHILECOVERdoesnotcoverallpositiveexamplesinPOSDOBEGIN（3）SelectaSEED；//选取一个种子SEED，例如没有被COVER覆盖的一个正样例（4）CallprocedureSTAR（SEED，NEG）；//产生一个能覆盖种子而同时排除所有反例的星（5）SelectthebestComplexBESTfromtheSTARaccordingtouser-definedcriteria；//从星中选取一个最好的复合（6）AddBESTasanextradisjucttoCOVER；//把最好的复合与COVER合取，形成新的COVER（7）END（8）RETURNCOVER.AQR算法描述算法4-6STAR：输入：种子SEED；反例NEG输出：星STARAQR算法描述（1）初始化STAR为空Complex（2）WHILEoneormoreComplexesinSTARcoverssomenegativeexamplesinNEGBEGIN/*如果STAR中的一个或多个Complex覆盖NEG中的负样例*/（3）SelectanegativeexampleEnegcoveredbyaComplexinSTAR；/*选取一个被STAR中的Complex覆盖的负样例*/（4）LetEXTENSIONbeallSelectorsthatcoverSEEDbutnotENEG；/*令EXTENSION为那些覆盖SEED但不覆盖ENEG的Selectors；*/（5）LetSTARbetheset{x∧y|x∈STAR，y∈EXTENSION}；/*令STAR={x∧y|x∈STAR，y∈EXTENSION}；*/（6）RemoveallComplexesinSTARsubsumedbyotherComplexesinSTAR；/*从STAR中除去被其他Complexes所包含的Complexes；*/（7）RemovetheworstComplexesfromSTARUNTILsizeofSTARislessthanorequaltouser-definedmaximum（maxstar）/*删除STAR中最坏的Complex直到STAR的大小等于或小于用户定义的最大数目maxstar*/（8）END（9）RETURNSTAR./*返回一系列覆盖SEED但不覆盖NEG的规则*/AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车SizeTypeClass小型摩托车大众交通小型汽车大众交通中型汽车大众交通微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机初始化COVER为{}，进入循环选取SEED={size=巨大型，type=自行车}调用STAR（SEED,NEG）初始化STAR为{}，进入循环选取STAR覆盖的负样例，如ENEG={size=小型，type=摩托车}EXTENSION为覆盖SEED，不覆盖ENEG的选择EXTENSION包括size=巨大型和type=自行车STAR=STAR={x∧y|x∈STAR，y∈EXTENSION}STAR={size=巨大型∧type=自行车}查看STAR覆盖的负样例返回STAR={size=巨大型∧type=自行车}巨大型自行车小型摩托车AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车SizeTypeClass小型摩托车大众交通小型汽车大众交通中型汽车大众交通微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机巨大型自行车巨大型摩托车BEST={size=巨大型∧type=自行车}，COVER={size=巨大型∧type=自行车}COVER不能覆盖到全部的正例选取另一个SEED={size=巨大型，type=摩托车}调用STAR（SEED,NEG）初始化STAR为{}，进入循环选取STAR覆盖的负样例，如ENEG={size=小型，type=摩托车}EXTENSION包括size=巨大型STAR={size=巨大型}查看STAR覆盖的负样例返回STAR={size=巨大型}小型摩托车AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车SizeTypeClass小型摩托车大众交通小型汽车大众交通中型汽车大众交通微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机巨大型摩托车BEST={size=巨大型}，将BEST添加到COVER中，COVER={size=巨大型∧type=自行车∨size=巨大型}={size=巨大型}COVER是否覆盖到全部的正例，若是，算法结束。输出规则：捷安特两轮车

size=巨大型注意：这里仅生成了分类“捷安特两轮车”的规则，需要继续调用算法对其余分类生成相应规则。AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机初始化COVER为{}，进入循环选取SEED={size=小型，type=摩托车}调用STAR（SEED,NEG）初始化STAR为{}，进入循环选取STAR覆盖的负样例，如ENEG={size=巨大型，type=自行车}EXTENSION为覆盖SEED，不覆盖ENEG的选择EXTENSION包含size=小型和type=摩托车

STAR=STAR={x∧y|x∈STAR，y∈EXTENSION}STAR={size=小型∧type=摩托车}查看STAR覆盖的负样例返回STAR={size=小型∧type=摩托车}SizeTypeClass小型摩托车大众交通小型汽车大众交通中型汽车大众交通小型摩托车巨大型自行车AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机BEST={size=小型∧type=摩托车}，COVER={size=小型∧type=摩托车}COVER不能覆盖到全部的正例选取另一个SEED={size=小型，type=汽车}调用STAR（SEED,NEG）初始化STAR为{}，进入循环选取STAR覆盖的负样例，如ENEG={size=小型，type=喷气式飞机}EXTENSION包括type=汽车STAR={type=汽车}查看STAR覆盖的负样例返回STAR={type=汽车}小型喷气式飞机SizeTypeClass小型摩托车大众交通小型汽车大众交通中型汽车大众交通小型摩托车小型汽车AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机BEST={type=汽车}，将BEST添加到COVER中，COVER={size=小型∧type=摩托车∨type=汽车}COVER是否覆盖到全部的正例，若是，算法结束。输出规则：大众交通

size=小型∧type=摩托车∨type=汽车SizeTypeClass小型摩托车大众交通小型汽车大众交通中型汽车大众交通小型汽车AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车小型摩托车大众交通小型汽车大众交通中型汽车大众交通初始化COVER为{}，进入循环选取SEED={size=微小型，type=喷气式飞机}调用STAR（SEED,NEG）初始化STAR为{}，进入循环选取ENEG={size=巨大型，type=自行车}同理可得STAR={size=微小型∧type=喷气式飞机}查看STAR覆盖的负样例返回STAR={size=微小型∧type=喷气式飞机}SizeTypeClass微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机微小型喷气式飞机巨大型自行车AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车小型摩托车大众交通小型汽车大众交通中型汽车大众交通BEST={size=微小型∧type=喷气式飞机}，COVER={size=微小型∧type=喷气式飞机}COVER不能覆盖到全部的正例选取另一个SEED={size=小型，type=喷气式飞机}调用STAR（SEED,NEG）初始化STAR为{}，进入循环选取ENEG={size=小型，type=摩托车}EXTENSION包括type=喷气式飞机STAR={type=喷气式飞机}查看STAR覆盖的负样例返回STAR={type=喷气式飞机}SizeTypeClass微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机微小型喷气式飞机小型喷气式飞机小型摩托车假设现有一个训练集，其包含两种属性：size（属性值：微小型，小型，中型，大型，巨大型，庞大型）type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：反例样本：AQR算法举例SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车小型摩托车大众交通小型汽车大众交通中型汽车大众交通BEST={type=喷气式飞机}，将BEST添加到COVER中，COVER={size=微小型∧type=喷气式飞机∨