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

1、第四章第四章 分类方法分类方法 内容内容 KDD的总体过程的总体过程 数据挖掘数据挖掘知知 识挖掘的核心识挖掘的核心 数据清理数据清理 数据集成数据集成 数据库数据库 数据仓库数据仓库 任务相关数据任务相关数据 选择选择 数据挖数据挖 掘掘 模式评估模式评估 分类分类 分类器的构造依据分类器的构造依据 数据分类的两步过程（数据分类的两步过程（1） 第一步第一步建立模型建立模型 训练数训练数 据集据集 NAME RANKYEARS TENURED MikeAssistant Prof3no MaryAssistant Prof7yes Bill Professor2yes JimAssociat

2、e Prof7yes DaveAssistant Prof6no Anne Associate Prof3no 分类算法分类算法 IF rank = professor OR years 6 THEN tenured = yes 分类规则分类规则 数据分类的两步过程（数据分类的两步过程（2） 第二步第二步用模型进行分用模型进行分 类类 分类规则分类规则 测试集测试集 NAME RANKYEARS TENURED TomAssistant Prof2no Merlisa Associate Prof7no George Professor5yes Joseph Assistant Prof7ye

3、s 未知数据未知数据 (Jeff, Professor, 4) Tenured? 内容内容 朴素贝叶斯分类简介朴素贝叶斯分类简介 本质是一个分类器（分类模型，分类算法均为一个意思）本质是一个分类器（分类模型，分类算法均为一个意思） 基础是概率推理基础是概率推理 先验概率：根据以往经验和分析得到的概率先验概率：根据以往经验和分析得到的概率 客观客观先验概率：由历史资料得到先验概率：由历史资料得到 主观先验概率：由主观经验得到（水果，圆的，甜的，红或绿主观先验概率：由主观经验得到（水果，圆的，甜的，红或绿 的的 是苹果）是苹果） 朴素贝叶斯分类特点：朴素贝叶斯分类特点： 基于独立假设基于独立假设

4、需要知道需要知道先验概率先验概率 按照获得的信息对先验概率进行按照获得的信息对先验概率进行修正修正 分类决策存在错误率分类决策存在错误率 朴素贝叶斯分类模型朴素贝叶斯分类模型 )( )()|( )|( XP HPHXP XHP 样本域：水果样本域：水果 X:红的和圆的（颜色属性取值为红，形状属性取值为圆）红的和圆的（颜色属性取值为红，形状属性取值为圆） H:是苹果（苹果是一个类别）是苹果（苹果是一个类别） P(H|X):反应了当知道水果是红的并且是圆的，则它是苹果的反应了当知道水果是红的并且是圆的，则它是苹果的 概率（置信程度）。这是后验概率概率（置信程度）。这是后验概率 P(H):是先验概率

5、是先验概率 朴素贝叶斯分类过程朴素贝叶斯分类过程 朴素贝叶斯分类过程朴素贝叶斯分类过程 第一步第一步 得到先验概率得到先验概率 性别性别身高身高(英尺英尺)体重体重(磅磅)脚的尺寸脚的尺寸(英寸英寸) 男618012 男5.92 (511)19011 男5.58 (57)17012 男5.92 (511)16510 女51006 女5.5 (56)1508 女5.42 (55)1307 女5.75 (59)1509 第二步第二步 预测预测X属于具有最高后验概率属于具有最高后验概率 的类的类 第二步第二步 预测预测X属于具有最高后验概率属于具有最高后验概率 的类的类 性别性别身高身高(英尺英尺)

6、体重体重(磅磅)脚的尺寸脚的尺寸(英寸英寸) Sample（？）61308 第三步第三步 求求P(X|C1) )|()|( 1 i n k ki CxPCXP 第三步第三步 求求P(X|C1) )|()|( 1 i n k ki CxPCXP x xK K的值可能有两种情况：的值可能有两种情况： （1 1）离散值）离散值 则则P(P(x xk k|C|Ci i)=)=s sik ik|s |si i，其中其中s sik ik是在属性 是在属性A Ak k上具有值上具有值x xk k 的类的类C Ci i的训练样本数，而的训练样本数，而s si i是是C Ci i中的训练样本数中的训练样本数 x

7、 x1 1=6=6英尺英尺 即即P(xP(x1 1|C|C1 1)=)=训练样本中身高为训练样本中身高为6 6英尺并且属于男性英尺并且属于男性 的样本数的样本数/ /男性的样本数男性的样本数= =1/41/4； 此处这么举例，是假设身高的取值都是离散值数据此处这么举例，是假设身高的取值都是离散值数据 性性 别别 身高身高 (英尺英尺) 体重体重 (磅磅) 脚的脚的尺寸尺寸 (英寸英寸) 男618012 男 5.92 (511) 19011 男5.58 (57)17012 男 5.92 (511) 16510 女51006 女5.5 (56)1508 女5.42 (55)1307 女5.75 (

8、59)1509 第三步第三步 求求P(X|C1) )|()|( 1 i n k ki CxPCXP x xK K的值可能有两种情况：的值可能有两种情况： （2 2）连续值）连续值 如果如果A Ak k是连续值属性，则通常假定该属是连续值属性，则通常假定该属 性服从高斯分布。因而，性服从高斯分布。因而， 是高斯分布函数，是高斯分布函数， 分别为平均值和标准差。分别为平均值和标准差。 2 2 )( 2 1 ),()|( i i i ii c ck c cckik x exgCxP ),( ii cck xg ii cc , 性性 别别 身高身高 (英尺英尺) 体重体重 (磅磅) 脚的脚的尺寸尺寸

9、(英寸英寸) 男618012 男 5.92 (511) 19011 男5.58 (57)17012 男 5.92 (511) 16510 女51006 女5.5 (56)1508 女5.42 (55)1307 女5.75 (59)1509 第三步第三步 求求P(X|C1) 性别性别 均值均值 (身高身高) 方差方差 (身高身高) 均值均值 (体重体重) 方差方差 (体重体重) 均值均值 (脚的尺寸脚的尺寸) 方差方差 (脚的尺寸脚的尺寸) 男性5.8553.5033e-02176.251.2292e+0211.259.1667e-01 女性5.41759.7225e-02132.55.5833

10、e+027.51.6667e+00 性别性别身高身高(英尺英尺)体重体重(磅磅)脚的尺寸脚的尺寸(英寸英寸) Sample（？）61308 第三步第三步 求求P(X|C1) 内容内容 规则归纳规则归纳 规则归纳规则归纳 AQ算法算法 AQR算法相关定义算法相关定义 AQR算法相关定义算法相关定义 AQR算法相关定义算法相关定义 AQR算法描述算法描述 算法算法 4-5 AQR： 输入：正例样本输入：正例样本POS； 反例样本反例样本NEG 输出：覆盖输出：覆盖COVER AQR算法描述算法描述 （1） COVER= ；/初始化初始化COVER为空集为空集 （2） WHILE COVER doe

11、s not cover all positive examples in POS DO BEGIN （3） Select a SEED；/选取一个种子选取一个种子SEED，例如没有被，例如没有被COVER覆盖的一个正覆盖的一个正 样例样例 （4） Call procedure STAR（SEED，NEG）；）； /产生一个能覆盖种子而同时产生一个能覆盖种子而同时 排除所有反例的星排除所有反例的星 （5） Select the best Complex BEST from the STAR according to user-defined criteria；/从星中选取一个最好的复合从星中选取

12、一个最好的复合 （6） Add BEST as an extra disjuct to COVER ；/把最好的复合与把最好的复合与COVER 合取，形成新的合取，形成新的COVER （7） END （8） RETURN COVER. AQR算法描述算法描述 算法算法 4-6 STAR： 输入：种子输入：种子SEED；反例；反例NEG 输出：星输出：星STAR AQR算法描述算法描述 （1）初始化）初始化STAR为空为空Complex （2）WHILE one or more Complexes in STAR covers some negative examples in NEG BEGI

13、N /*如果如果STAR中的一个或多个中的一个或多个Complex覆盖覆盖NEG中的负样例中的负样例*/ （3）Select a negative example Eneg covered by a Complex in STAR；/*选取一个被选取一个被STAR中中 的的Complex覆盖的负样例覆盖的负样例*/ （4）Let EXTENSION be all Selectors that cover SEED but not ENEG；/*令令EXTENSION为那为那 些覆盖些覆盖SEED但不覆盖但不覆盖ENEG的的Selectors；*/ （5）Let STAR be the set

14、xy|xSTAR，yEXTENSION； /*令令STAR= xy|xSTAR，yEXTENSION；*/ （6） Remove all Complexes in STAR subsumed by other Complexes in STAR； /*从从STAR中除去被其他中除去被其他Complexes所包含的所包含的Complexes；*/ （7）Remove the worst Complexes from STAR UNTIL size of STAR is less than or equal to user-defined maximum （maxstar）/*删除删除STAR中最

15、坏的中最坏的Complex直到直到STAR的大小等于或小于的大小等于或小于 用户定义的最大数目用户定义的最大数目maxstar*/ （8）END （9）RETURN STAR. /*返回一系列覆盖返回一系列覆盖SEED但不覆盖但不覆盖NEG的规则的规则*/ AQR算法举例算法举例 假设现有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性： size size （属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型） type type （属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑

16、翔机） 正例样本：正例样本： 反例样本：反例样本： SizeTypeClass 巨大巨大型型自行车自行车捷安特两轮车捷安特两轮车 巨大型巨大型摩托车摩托车捷安特两轮车捷安特两轮车 SizeTypeClass 小型小型摩托车摩托车大众交通大众交通 小型小型汽车汽车大众交通大众交通 中型中型汽车汽车大众交通大众交通 微小型微小型喷气式飞机喷气式飞机快速飞机快速飞机 小型小型喷气式飞机喷气式飞机快速飞机快速飞机 中型中型喷气式飞机喷气式飞机快速飞机快速飞机 l 初始化初始化COVER为为，进入循环，进入循环 l 选取选取SEED = size=巨大巨大型型，type=自行车自行车 l 调用调用STA

17、R（SEED,NEG） l初始化初始化STAR为为，进入循环，进入循环 l选取选取STAR覆盖的负样例，如覆盖的负样例，如 ENEG=size=小型小型，type =摩托车摩托车 lEXTENSION为覆盖为覆盖SEED，不覆盖，不覆盖 ENEG的选择的选择 EXTENSION包括包括 size= 巨大巨大型型和和type =自行车自行车 lSTAR=STAR=xy|xSTAR， yEXTENSION STAR= size= 巨大巨大型型type =自行车自行车 l查看查看STAR覆盖的负样例覆盖的负样例 l返回返回STAR=size=巨大巨大型型type=自行自行 车车 巨大巨大型型自行车自

18、行车 小型小型摩托车摩托车 AQR算法举例算法举例 假设现有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性： size size （属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型） type type （属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机） 正例样本：正例样本： 反例样本：反例样本： SizeTypeClass 巨大型巨大型自行车自行车捷安特两轮车捷安特两轮车 巨大型巨大型摩托车摩托车捷安特两轮车捷安特两轮车 SizeTypeClass 小型小型摩托车摩托车大

19、众交通大众交通 小型小型汽车汽车大众交通大众交通 中型中型汽车汽车大众交通大众交通 微小型微小型喷气式飞机喷气式飞机快速飞机快速飞机 小型小型喷气式飞机喷气式飞机快速飞机快速飞机 中型中型喷气式飞机喷气式飞机快速飞机快速飞机 巨大型巨大型自行车自行车 巨大型巨大型摩托车摩托车 l BEST= size=巨大巨大型型 type =自行车自行车 ， COVER = size=巨大巨大型型 type =自行车自行车 l COVER不能不能覆盖到全部的正例覆盖到全部的正例 l 选取另一个选取另一个SEED= size=巨大巨大型型，type = 摩托车摩托车 l 调用调用STAR（SEED,NEG）

20、l初始化初始化STAR为为，进入循环，进入循环 l选取选取STAR覆盖的负样例，如覆盖的负样例，如 ENEG=size=小型小型，type =摩托车摩托车 lEXTENSION包括包括size= 巨大型巨大型 lSTAR= size=巨大巨大型型 l查看查看STAR覆盖的负样例覆盖的负样例 l返回返回STAR=size=巨大巨大型型 小型小型摩托车摩托车 AQR算法举例算法举例 假设现有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性： size size （属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型） type type

21、 （属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机） 正例样本：正例样本： 反例样本：反例样本： SizeTypeClass 巨大型巨大型自行车自行车捷安特两轮车捷安特两轮车 巨大型巨大型摩托车摩托车捷安特两轮车捷安特两轮车 SizeTypeClass 小型小型摩托车摩托车大众交通大众交通 小型小型汽车汽车大众交通大众交通 中型中型汽车汽车大众交通大众交通 微小型微小型喷气式飞机喷气式飞机快速飞机快速飞机 小型小型喷气式飞机喷气式飞机快速飞机快速飞机 中型中型喷气式飞机喷气式飞机快速飞机快速飞机 巨大型巨大型摩托车摩托车 l BEST=si

22、ze=巨大巨大型型，将，将BEST添加到添加到 COVER中，中，COVER = size=巨大巨大型型 type =自行车自行车size=巨大巨大型型= size=巨巨 大大型型 l COVER是否是否覆盖到全部的正例，覆盖到全部的正例，若是，若是， 算法结束。算法结束。 l 输出规则：输出规则：捷安特捷安特两轮车两轮车size=巨大巨大型型 注意：注意：这里仅生成了分类这里仅生成了分类“捷安特捷安特 两轮车两轮车”的规则，需要继续调用算的规则，需要继续调用算 法对其余分类生成相应规则。法对其余分类生成相应规则。 AQR算法举例算法举例 假设现有一个训练集，其包含两种属性：假设现有一个训练集

23、，其包含两种属性： size size （属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型） type type （属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机） 正例样本：正例样本： 反例样本：反例样本： SizeTypeClass 巨大巨大型型自行车自行车捷安特两轮车捷安特两轮车 巨大型巨大型摩托车摩托车捷安特两轮车捷安特两轮车 微小型微小型喷气式飞机喷气式飞机快速飞机快速飞机 小型小型喷气式飞机喷气式飞机快速飞机快速飞机 中型中型喷气式飞机喷气式飞机快速飞机快速飞机 l 初始化初始

24、化COVER为为，进入循环，进入循环 l 选取选取SEED = size=小型小型，type=摩托车摩托车 l 调用调用STAR（SEED,NEG） l初始化初始化STAR为为，进入循环，进入循环 l选取选取STAR覆盖的负样例，如覆盖的负样例，如 ENEG=size=巨大型巨大型，type =自行车自行车 lEXTENSION为覆盖为覆盖SEED，不覆盖，不覆盖 ENEG的选择的选择 EXTENSION包含包含 size=小型和小型和type=摩托车摩托车 lSTAR=STAR=xy|xSTAR， yEXTENSION STAR=size=小小 型型 type=摩托车摩托车 l查看查看STA

25、R覆盖的负样例覆盖的负样例 l返回返回STAR=size=小型小型type=摩托车摩托车 SizeTypeClass 小型小型摩托车摩托车大众交通大众交通 小型小型汽车汽车大众交通大众交通 中型中型汽车汽车大众交通大众交通 小型小型摩托车摩托车 巨大型巨大型自行车自行车 AQR算法举例算法举例 假设现有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性： size size （属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型） type type （属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，

26、喷气式飞机，滑翔机） 正例样本：正例样本： 反例样本：反例样本： SizeTypeClass 巨大巨大型型自行车自行车捷安特两轮车捷安特两轮车 巨大型巨大型摩托车摩托车捷安特两轮车捷安特两轮车 微小型微小型喷气式飞机喷气式飞机快速飞机快速飞机 小型小型喷气式飞机喷气式飞机快速飞机快速飞机 中型中型喷气式飞机喷气式飞机快速飞机快速飞机 l BEST= size=小型小型 type =摩托摩托车车 ， COVER = size=小型小型 type =摩托摩托车车 l COVER不能不能覆盖到全部的正例覆盖到全部的正例 l 选取另一个选取另一个SEED= size=小型小型，type =汽汽 车车

27、l 调用调用STAR（SEED,NEG） l初始化初始化STAR为为，进入循环，进入循环 l选取选取STAR覆盖的负样例，如覆盖的负样例，如 ENEG=size=小型小型，type=喷气式飞机喷气式飞机 lEXTENSION包括包括 type =汽车汽车 lSTAR= type =汽汽车车 l查看查看STAR覆盖的负样例覆盖的负样例 l返回返回STAR= type =汽汽车车 小型小型喷气式飞机喷气式飞机 SizeTypeClass 小型小型摩托车摩托车大众交通大众交通 小型小型汽车汽车大众交通大众交通 中型中型汽车汽车大众交通大众交通 小型小型摩托车摩托车 小型小型汽车汽车 AQR算法举例算

28、法举例 假设现有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性： size size （属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型） type type （属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机） 正例样本：正例样本： 反例样本：反例样本： SizeTypeClass 巨大巨大型型自行车自行车捷安特两轮车捷安特两轮车 巨大型巨大型摩托车摩托车捷安特两轮车捷安特两轮车 微小型微小型喷气式飞机喷气式飞机快速飞机快速飞机 小型小型喷气式飞机喷气式飞机快速飞机快速飞机

29、 中型中型喷气式飞机喷气式飞机快速飞机快速飞机 l BEST= type =汽汽车车 ，将，将BEST添加到添加到 COVER中，中，COVER = size=小型小型type = 摩托摩托车车type =汽车汽车 l COVER是否是否覆盖到全部的正例，覆盖到全部的正例，若是，若是，算算 法结束。法结束。 l 输出规则：输出规则：大众交通大众交通 size=小型小型type = 摩托摩托车车type =汽车汽车 SizeTypeClass 小型小型摩托车摩托车大众交通大众交通 小型小型汽车汽车大众交通大众交通 中型中型汽车汽车大众交通大众交通 小型小型汽车汽车 AQR算法举例算法举例 假设现

30、有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性： size size （属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型） type type （属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机） 正例样本：正例样本： 反例样本：反例样本： SizeTypeClass 巨大巨大型型自行车自行车捷安特两轮车捷安特两轮车 巨大型巨大型摩托车摩托车捷安特两轮车捷安特两轮车 小型小型摩托车摩托车大众交通大众交通 小型小型汽车汽车大众交通大众交通 中型中型汽车汽车大众交通大众交通 l

31、 初始化初始化COVER为为，进入循环，进入循环 l 选取选取SEED = size=微小型微小型，type=喷气式喷气式 飞机飞机 l 调用调用STAR（SEED,NEG） l初始化初始化STAR为为，进入循环，进入循环 l选取选取ENEG=size=巨大型巨大型，type =自行自行 车车 l同理可得同理可得STAR=size=微小型微小型 type= 喷气式飞机喷气式飞机 l查看查看STAR覆盖的负样例覆盖的负样例 l返回返回STAR=size=微小型微小型 type=喷气喷气 式飞机式飞机 SizeTypeClass 微小型微小型喷气式飞机喷气式飞机快速飞机快速飞机 小型小型喷气式飞机

32、喷气式飞机快速飞机快速飞机 中型中型喷气式飞机喷气式飞机快速飞机快速飞机 微小型微小型喷气式飞机喷气式飞机 巨大型巨大型自行车自行车 AQR算法举例算法举例 假设现有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性： size size （属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型） type type （属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机） 正例样本：正例样本： 反例样本：反例样本： SizeTypeClass 巨大巨大型型自行车自行车捷安特两轮车捷安特两

33、轮车 巨大型巨大型摩托车摩托车捷安特两轮车捷安特两轮车 小型小型摩托车摩托车大众交通大众交通 小型小型汽车汽车大众交通大众交通 中型中型汽车汽车大众交通大众交通 l BEST=size =微小型微小型 type =喷气式飞机喷气式飞机 ，COVER =size=微小型微小型 type=喷气式喷气式 飞机飞机 l COVER不能不能覆盖到全部的正例覆盖到全部的正例 l 选取另一个选取另一个SEED= size=小型小型，type =喷喷 气式飞机气式飞机 l 调用调用STAR（SEED,NEG） l初始化初始化STAR为为，进入循环，进入循环 l选取选取ENEG= size=小型小型，type =摩托摩托 车车 lEXTENSION包括包括type =喷气式飞机喷气式飞机 STAR= type =喷气式飞机喷气式飞机 l查看查看STAR覆盖的负样例覆盖的负样例 l返回返回STAR=