数据挖掘分类方法修改.ppt

《数据挖掘分类方法修改.ppt》由会员分享，可在线阅读，更多相关《数据挖掘分类方法修改.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘分类方法修数据挖掘分类方法修改改现在学习的是第1页，共46页内容内容l l回顾基本概念回顾基本概念l l贝叶斯分类贝叶斯分类l l规则归纳规则归纳l l总结总结现在学习的是第2页，共46页KDD的总体过程的总体过程数据挖掘数据挖掘知识知识挖掘的核心挖掘的核心数据清理数据清理数据集成数据集成数据库数据库数据仓库数据仓库任务相关数据任务相关数据选择选择数据挖掘数据挖掘模式评估模式评估现在学习的是第3页，共46页分类分类为什么要进行分类？为什么要进行分类？为什么要进行分类？为什么要进行分类？分类是数据挖掘中的重要任务之一分类是数据挖掘中的重要任务之一分类是数据挖掘中的重要任务之一分类是数据挖

2、掘中的重要任务之一很多数据挖掘问题都可以转化为分类问题很多数据挖掘问题都可以转化为分类问题很多数据挖掘问题都可以转化为分类问题很多数据挖掘问题都可以转化为分类问题分分分分类类类类的的的的目目目目的的的的在在在在于于于于用用用用分分分分类类类类方方方方法法法法构构构构建建建建一一一一个个个个分分分分类类类类函函函函数数数数或或或或分分分分类类类类模模模模型型型型（分分分分类类类类器器器器），该该该该分分分分类类类类器器器器可可可可以以以以将将将将输输输输入入入入数数数数据据据据（数数数数据据据据库库库库中中中中的的的的数数数数据据据据项）映射到给定类别中的一个类别。项）映射到给定类别中的一个类别

3、。项）映射到给定类别中的一个类别。项）映射到给定类别中的一个类别。现在学习的是第4页，共46页分类器的构造依据分类器的构造依据统计方法：贝叶斯方法和非参数法等统计方法：贝叶斯方法和非参数法等机器学习方法：决策树法和规则归纳法机器学习方法：决策树法和规则归纳法神经网络方法神经网络方法其他：粗糙集等其他：粗糙集等现在学习的是第5页，共46页数据分类的两步过程（数据分类的两步过程（1）l l第一步，建立一个模型，描述预定数据类集和概念集第一步，建立一个模型，描述预定数据类集和概念集第一步，建立一个模型，描述预定数据类集和概念集第一步，建立一个模型，描述预定数据类集和概念集l l假定每个元组属于一个预

4、定义的类，由一个类标号属性确定假定每个元组属于一个预定义的类，由一个类标号属性确定假定每个元组属于一个预定义的类，由一个类标号属性确定假定每个元组属于一个预定义的类，由一个类标号属性确定l l基本概念基本概念基本概念基本概念l l训练数据集训练数据集训练数据集训练数据集：由为建立模型而被分析的数据元组形成：由为建立模型而被分析的数据元组形成：由为建立模型而被分析的数据元组形成：由为建立模型而被分析的数据元组形成l l训练样本训练样本训练样本训练样本：训练数据集中的单个样本（元组）：训练数据集中的单个样本（元组）：训练数据集中的单个样本（元组）：训练数据集中的单个样本（元组）l l学习模型可以用

5、分类规则、判定树或数学公式的形式提供学习模型可以用分类规则、判定树或数学公式的形式提供学习模型可以用分类规则、判定树或数学公式的形式提供学习模型可以用分类规则、判定树或数学公式的形式提供现在学习的是第6页，共46页第一步第一步建立模型建立模型训练数训练数据集据集分类算法分类算法IF rank=professorOR years 6THEN tenured=yes 分类规则分类规则现在学习的是第7页，共46页数据分类的两步过程（数据分类的两步过程（2）l l第二步，使用模型，对将来的或未知的对象进行分类第二步，使用模型，对将来的或未知的对象进行分类第二步，使用模型，对将来的或未知的对象进行分类第

6、二步，使用模型，对将来的或未知的对象进行分类l l首先评估模型的预测准确率首先评估模型的预测准确率首先评估模型的预测准确率首先评估模型的预测准确率l l对对对对每每每每个个个个测测测测试试试试样样样样本本本本，将将将将已已已已知知知知的的的的类类类类标标标标号号号号和和和和该该该该样样样样本本本本的的的的学学学学习习习习模模模模型型型型类类类类预预预预测测测测比较比较比较比较l l模模模模型型型型在在在在给给给给定定定定测测测测试试试试集集集集上上上上的的的的准准准准确确确确率率率率是是是是正正正正确确确确被被被被模模模模型型型型分分分分类类类类的的的的测测测测试试试试样本的百分比样本的百分比

7、样本的百分比样本的百分比l l测测测测试试试试集集集集要要要要独独独独立立立立于于于于训训训训练练练练样样样样本本本本集集集集，否否否否则则则则会会会会出出出出现现现现“过过过过分分分分适适适适应应应应数数数数据据据据”的的的的情情情情况况况况现在学习的是第8页，共46页第二步第二步用模型进行分用模型进行分类类分类规则分类规则测试集测试集未知数据未知数据(Jeff,Professor,4)Tenured?现在学习的是第9页，共46页内容内容l l回顾基本概念回顾基本概念l l贝叶斯分类贝叶斯分类l l规则归纳规则归纳l l总结总结现在学习的是第10页，共46页朴素贝叶斯分类简介朴素贝叶斯分类简

8、介l l本质是一个分类器（分类模型，分类算法均为一个意思）本质是一个分类器（分类模型，分类算法均为一个意思）本质是一个分类器（分类模型，分类算法均为一个意思）本质是一个分类器（分类模型，分类算法均为一个意思）l l基础是概率推理基础是概率推理基础是概率推理基础是概率推理l l先验概率：根据以往经验和分析得到的概率先验概率：根据以往经验和分析得到的概率先验概率：根据以往经验和分析得到的概率先验概率：根据以往经验和分析得到的概率客观先验概率：由历史资料得到客观先验概率：由历史资料得到客观先验概率：由历史资料得到客观先验概率：由历史资料得到主观先验概率：由主观经验得到（水果，圆的，甜的，红或绿的主观

9、先验概率：由主观经验得到（水果，圆的，甜的，红或绿的主观先验概率：由主观经验得到（水果，圆的，甜的，红或绿的主观先验概率：由主观经验得到（水果，圆的，甜的，红或绿的 是苹果）是苹果）是苹果）是苹果）l l朴素贝叶斯分类特点：朴素贝叶斯分类特点：朴素贝叶斯分类特点：朴素贝叶斯分类特点：基于独立假设基于独立假设基于独立假设基于独立假设需要知道先验概率需要知道先验概率需要知道先验概率需要知道先验概率按照获得的信息对先验概率进行修正按照获得的信息对先验概率进行修正按照获得的信息对先验概率进行修正按照获得的信息对先验概率进行修正分类决策存在错误率分类决策存在错误率分类决策存在错误率分类决策存在错误率现在

10、学习的是第11页，共46页朴素贝叶斯分类模型朴素贝叶斯分类模型样本域：水果样本域：水果X:红的和圆的（颜色属性取值为红，形状属性取值为圆）红的和圆的（颜色属性取值为红，形状属性取值为圆）H:是苹果（苹果是一个类别）是苹果（苹果是一个类别）P(H|X):反应了当知道水果是红的并且是圆的，则它是苹果的概率（置信反应了当知道水果是红的并且是圆的，则它是苹果的概率（置信程度）。这是后验概率程度）。这是后验概率P(H):是先验概率是先验概率现在学习的是第12页，共46页朴素贝叶斯分类过程朴素贝叶斯分类过程实例：性别分类实例：性别分类问问题题描描述述：通通过过一一些些测测量量的的特特征征，包包括括身身高高

11、、体体重、脚的尺寸，判定一个人是男性还是女性。重、脚的尺寸，判定一个人是男性还是女性。现在学习的是第13页，共46页朴素贝叶斯分类过程朴素贝叶斯分类过程问题数学表示：问题数学表示：问题数学表示：问题数学表示：类别类别类别类别:可以从可以从可以从可以从C C C C1 1 1 1到到到到C C C Cn n n n ，在我们的问题中即，在我们的问题中即，在我们的问题中即，在我们的问题中即C C C C1 1 1 1=男性男性男性男性 C C C C2 2 2 2=女性女性女性女性样样样样本本本本表表表表示示示示：每每每每个个个个数数数数据据据据样样样样本本本本（某某某某元元元元组组组组）用用用用

12、一一一一个个个个n n n n维维维维特特特特征征征征向向向向量量量量X=X=X=X=xxxx1 1 1 1，x x x x2 2 2 2，x x x xn n n n 表表表表示示示示，分别描述对分别描述对分别描述对分别描述对n n n n个属性个属性个属性个属性A A A A1 1 1 1，A A A A2 2 2 2，A A A An n n n样本的样本的样本的样本的n n n n个度量。个度量。个度量。个度量。比比比比如如如如样样样样本本本本X=xX=xX=xX=x1 1 1 1,x,x,x,x2 2 2 2,x,x,x,x3 3 3 3=1=1=1=1米米米米73,6073,607

13、3,6073,60千千千千克克克克，20202020厘厘厘厘米米米米 （分分分分别别别别对对对对应应应应身身身身高高高高体体体体重重重重和和和和脚脚脚脚长长长长三三三三个属性的度量）个属性的度量）个属性的度量）个属性的度量）分类模型：分类模型：分类模型：分类模型：现在学习的是第14页，共46页第一步第一步得到先验概率得到先验概率训练数据集：得到先验概率，按照频率来算。训练数据集：得到先验概率，按照频率来算。训练数据集：得到先验概率，按照频率来算。训练数据集：得到先验概率，按照频率来算。P(CP(C1 1)=0.5P(C)=0.5P(C2 2)=0.5)=0.5性别身高(英尺)体重(磅)脚的尺寸

14、(英寸)男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现在学习的是第15页，共46页第二步第二步预测预测X属于具有最高后验概率属于具有最高后验概率的类的类 朴朴素素贝贝叶叶斯斯分分类类将将未未知知的的样样本本分分配配给给类类C Ci i（1im1im1im1im）当当且且仅仅当当P(CP(CP(CP(Ci i i i|X)|X)|X)|X)P(CP(CP(CP(Cj j j j|X)|X)|X)|X)，对对对对任任任任意意意意的的的的j=1j=1j=1

15、j=1，2 2 2 2，m m m m，jijijiji。这这样样，最最大大化化P(CP(CP(CP(Ci i i i|X)|X)|X)|X)。其其其其P(CP(CP(CP(Ci i|X)|X)最大的类最大的类C Ci i称为最大后验假定。称为最大后验假定。称为最大后验假定。称为最大后验假定。现在学习的是第16页，共46页第二步第二步预测预测X属于具有最高后验概率的属于具有最高后验概率的类类在在在在这这这这个个个个性性性性别别别别分分分分类类类类问问问问题题题题中中中中即即即即：比比比比较较较较P(CP(CP(CP(C1 1 1 1|X)|X)|X)|X)和和和和P(CP(CP(CP(C2 2

16、 2 2|X)|X)|X)|X)的的的的值值值值(X=6,130,8)(X=6,130,8)(X=6,130,8)(X=6,130,8)，采采采采用用用用贝贝贝贝叶斯公式：叶斯公式：叶斯公式：叶斯公式：P(CP(CP(CP(C1 1 1 1|X)=P(X|C|X)=P(X|C|X)=P(X|C|X)=P(X|C1 1 1 1)*P(C)*P(C)*P(C)*P(C1 1 1 1)/P(X)/P(X)/P(X)/P(X)其中其中其中其中 先验概率先验概率先验概率先验概率P(CP(CP(CP(C1 1 1 1)=0.5)=0.5)=0.5)=0.5 P(X|CP(X|CP(X|CP(X|C1 1

17、1 1)=?()=?()=?()=?(还未知还未知还未知还未知)P(X)P(X)P(X)P(X)对对对对于于于于所所所所有有有有类类类类来来来来说说说说都都都都是是是是一一一一样样样样的的的的即即即即P(X)=P(CP(X)=P(CP(X)=P(CP(X)=P(C1 1 1 1)*P(X|C)*P(X|C)*P(X|C)*P(X|C1 1 1 1)+P(C)+P(C)+P(C)+P(C2 2 2 2)*P(X|C)*P(X|C)*P(X|C)*P(X|C2 2 2 2)（全全全全概概概概率率率率公公公公式）式）式）式）所以为了得到最大后验假定，问题转化为求所以为了得到最大后验假定，问题转化为求

18、所以为了得到最大后验假定，问题转化为求所以为了得到最大后验假定，问题转化为求P(X|CP(X|CP(X|CP(X|C1 1 1 1)的最大值的最大值的最大值的最大值未分类的样本：未分类的样本：未分类的样本：未分类的样本：性别身高(英尺)体重(磅)脚的尺寸(英寸)Sample（？）61308现在学习的是第17页，共46页第三步第三步求求P(X|C1)问问问问题题题题就就就就转转转转换换换换为为为为对对对对P(X|CP(X|CP(X|CP(X|Ci i i i)的的的的最最最最大大大大化化化化（P(X|CP(X|CP(X|CP(X|Ci i i i)常常常常被被被被称称称称为为为为给给给给定定定定

19、C C C Ci i i i时时时时数据数据数据数据X X X X的似然度，而使的似然度，而使的似然度，而使的似然度，而使P(X|CP(X|CP(X|CP(X|Ci i i i)最大的假设最大的假设最大的假设最大的假设C C C Ci i i i称为最大似然假设）。称为最大似然假设）。称为最大似然假设）。称为最大似然假设）。因为类的条件是相互独立的所以可以用如下公式计算：因为类的条件是相互独立的所以可以用如下公式计算：因为类的条件是相互独立的所以可以用如下公式计算：因为类的条件是相互独立的所以可以用如下公式计算：在我们的问题里面比如在我们的问题里面比如在我们的问题里面比如在我们的问题里面比如X

20、=6X=6X=6X=6英尺，英尺，英尺，英尺，130130130130磅，磅，磅，磅，8 8 8 8英寸英寸英寸英寸 P(X|CP(X|CP(X|CP(X|C1 1 1 1)=P(x)=P(x)=P(x)=P(x1 1 1 1|C|C|C|C1 1 1 1)*P(x)*P(x)*P(x)*P(x2 2 2 2|C|C|C|C1 1 1 1)*P(x)*P(x)*P(x)*P(x3 3 3 3|C|C|C|C1 1 1 1)表示表示表示表示C C C C1 1 1 1时样本时样本时样本时样本X X X X的似然度的似然度的似然度的似然度现在学习的是第18页，共46页第三步第三步求求P(X|C1)

21、x xK K的值可能有两种情况：的值可能有两种情况：（1 1）离散值）离散值则则P(xP(xk k|C|Ci i)=s)=sikik|s|si i，其中其中s sikik是在属性是在属性A Ak k上具有值上具有值x xk k的类的类C Ci i的的训练样本数，而训练样本数，而s si i是是C Ci i中的训练样本数中的训练样本数x x1 1=6=6英尺英尺即即P(xP(x1 1|C|C1 1)=)=训练样本中身高为训练样本中身高为6 6英尺并且属于男性的样本英尺并且属于男性的样本数数/男性的样本数男性的样本数=1/4=1/4；此处这么举例，是假设身高的取值都是离散值数据此处这么举例，是假设

22、身高的取值都是离散值数据性别身高(英尺)体重(磅)脚的尺寸(英寸)男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现在学习的是第19页，共46页第三步第三步求求P(X|C1)x xK K的值可能有两种情况：的值可能有两种情况：（2 2）连续值）连续值如果如果A Ak k是连续值属性，则通常假定该属性服从是连续值属性，则通常假定该属性服从高斯分布。因而，高斯分布。因而，是高斯分布函数，是高斯分布函数，分别为平均值和标准差。分别为平均值和标准差。性别身高(英

23、尺)体重(磅)脚的尺寸(英寸)男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现在学习的是第20页，共46页第三步第三步求求P(X|C1)假设训练集样本的特征满足高斯分布，得到下表：假设训练集样本的特征满足高斯分布，得到下表：假设训练集样本的特征满足高斯分布，得到下表：假设训练集样本的特征满足高斯分布，得到下表：性别均值(身高)方差(身高)均值(体重)方差(体重)均值(脚的尺寸)方差(脚的尺寸)男性5.8553.5033e-02176.251.2292e

24、+0211.259.1667e-01女性5.41759.7225e-02132.55.5833e+027.51.6667e+00性别身高(英尺)体重(磅)脚的尺寸(英寸)Sample（？）61308现在学习的是第21页，共46页第三步第三步求求P(X|C1)分别求得类别分别求得类别分别求得类别分别求得类别C1C1C1C1和和和和C2C2C2C2的似然度的似然度的似然度的似然度男性似然度计算项：男性似然度计算项：男性似然度计算项：男性似然度计算项：女性似然度计算项：女性似然度计算项：女性似然度计算项：女性似然度计算项：男性和女性的似然度：男性和女性的似然度：男性和女性的似然度：男性和女性的似然度

25、：可可可可以以以以看看看看到到到到女女女女性性性性的的的的似似似似然然然然度度度度更更更更大大大大，更更更更具具具具贝贝贝贝叶叶叶叶斯斯斯斯分分分分类类类类模模模模型型型型我我我我们们们们显显显显然然然然可可可可以以以以得得得得到到到到，女女女女性性性性的的的的后后后后验验验验概概概概率更大，所以该样本分类为率更大，所以该样本分类为率更大，所以该样本分类为率更大，所以该样本分类为女性女性女性女性。现在学习的是第22页，共46页内容内容l l回顾基本概念回顾基本概念l l贝叶斯分类贝叶斯分类l l规则归纳规则归纳l l总结总结现在学习的是第23页，共46页l l常见的采用规则表示的分类器构造方法

26、常见的采用规则表示的分类器构造方法常见的采用规则表示的分类器构造方法常见的采用规则表示的分类器构造方法l l利用规则归纳技术直接生成规则；利用规则归纳技术直接生成规则；利用规则归纳技术直接生成规则；利用规则归纳技术直接生成规则；l l利利利利用用用用决决决决策策策策树树树树方方方方法法法法先先先先生生生生成成成成决决决决策策策策树树树树，然然然然后后后后再再再再把把把把决决决决策策策策树树树树转转转转换换换换为为为为规规规规则；则；则；则；l l使用粗糙集方法生成规则；使用粗糙集方法生成规则；使用粗糙集方法生成规则；使用粗糙集方法生成规则；l l使用遗传算法中的分类器技术生成规则等。使用遗传算

27、法中的分类器技术生成规则等。使用遗传算法中的分类器技术生成规则等。使用遗传算法中的分类器技术生成规则等。规则归纳规则归纳现在学习的是第24页，共46页l l规规规规则则则则归归归归纳纳纳纳有有有有四四四四种种种种策策策策略略略略：减减减减法法法法、加加加加法法法法、先先先先加加加加后后后后减减减减、先先先先减后加减后加减后加减后加策略策略策略策略。l l减减减减法法法法策策策策略略略略：以以以以具具具具体体体体例例例例子子子子为为为为出出出出发发发发点点点点，对对对对例例例例子子子子进进进进行行行行推推推推广广广广或或或或泛泛泛泛化化化化，推推推推广广广广即即即即减减减减除除除除条条条条件件件

28、件（属属属属性性性性值值值值）或或或或减减减减除除除除合合合合取取取取项项项项（为为为为了了了了方方方方便便便便，我我我我们们们们不不不不考考考考虑虑虑虑增增增增加加加加析析析析取取取取项项项项的的的的推推推推广广广广），使使使使推推推推广广广广后后后后的的的的例例例例子子子子或或或或规规规规则则则则不不不不覆盖任何反例。覆盖任何反例。覆盖任何反例。覆盖任何反例。l l加加加加法法法法策策策策略略略略：起起起起始始始始假假假假设设设设规规规规则则则则的的的的条条条条件件件件部部部部分分分分为为为为空空空空（永永永永真真真真规规规规则则则则），如如如如果果果果该该该该规规规规则则则则覆覆覆覆盖盖

29、盖盖了了了了反反反反例例例例，则则则则不不不不停停停停地地地地向向向向规规规规则则则则增增增增加加加加条条条条件件件件或或或或合合合合取取取取项，直到该规则不再覆盖反例。项，直到该规则不再覆盖反例。项，直到该规则不再覆盖反例。项，直到该规则不再覆盖反例。规则归纳规则归纳l l先先先先加加加加后后后后减减减减策策策策略略略略：由由由由于于于于属属属属性性性性间间间间存存存存在在在在相相相相关关关关性性性性，因因因因此此此此可可可可能能能能某某某某个个个个条条条条件件件件的的的的加加加加入入入入会导致前面加入的条件没什么作用，因此需要减除前面的条件。会导致前面加入的条件没什么作用，因此需要减除前面

30、的条件。会导致前面加入的条件没什么作用，因此需要减除前面的条件。会导致前面加入的条件没什么作用，因此需要减除前面的条件。l l先减后加策略：道理同先加后减，也是为了处理属性间的相关性。先减后加策略：道理同先加后减，也是为了处理属性间的相关性。先减后加策略：道理同先加后减，也是为了处理属性间的相关性。先减后加策略：道理同先加后减，也是为了处理属性间的相关性。l l典型的规则归纳算法有典型的规则归纳算法有典型的规则归纳算法有典型的规则归纳算法有AQAQAQAQ、CN2CN2CN2CN2和和和和FOILFOILFOILFOIL等。等。等。等。现在学习的是第25页，共46页l lAQAQ算算算算法法法

31、法利利利利用用用用覆覆覆覆盖盖盖盖所所所所有有有有正正正正例例例例，排排排排斥斥斥斥所所所所有有有有反反反反例例例例的的的的思思思思想想想想来来来来寻寻寻寻找找找找规规规规则则则则。比比比比较较较较典典典典型型型型的的的的有有有有AQ11AQ11方方方方法法法法，AQ15AQ15方方方方法法法法以以以以及及及及AE5AE5方法。方法。方法。方法。l lAQRAQR是是是是一一一一个个个个基基基基于于于于最最最最基基基基本本本本AQAQ算算算算法法法法的的的的归归归归纳纳纳纳算算算算法法法法。很很很很多多多多的的的的算算算算法法法法都都都都采采采采用用用用了了了了基基基基本本本本AQAQ算算算算

32、法法法法，如如如如AQ11AQ11和和和和GEMGEM。但但但但AQRAQR更更更更为为为为简简简简单单单单，AQ11AQ11使使使使用用用用了了了了一一一一种种种种复复复复杂杂杂杂的的的的包包包包括括括括置置置置信信信信度度度度的规则推导方法。的规则推导方法。的规则推导方法。的规则推导方法。AQ算法算法现在学习的是第26页，共46页AQRAQR为每一个分类推导出一条规则，每一条规则形式如下：为每一个分类推导出一条规则，每一条规则形式如下：为每一个分类推导出一条规则，每一条规则形式如下：为每一个分类推导出一条规则，每一条规则形式如下：if then predict if then predic

33、t 在一个属性上的基本测试被称为一个选择值（在一个属性上的基本测试被称为一个选择值（在一个属性上的基本测试被称为一个选择值（在一个属性上的基本测试被称为一个选择值（SelectorSelector）。）。）。）。例子：例子：例子：例子：60 60AQRAQR允许测试做允许测试做允许测试做允许测试做=，AQR算法相关定义算法相关定义现在学习的是第27页，共46页 选选选选择择择择值值值值（SelectorSelector）的的的的合合合合取取取取被被被被称称称称为为为为复复复复合合合合（ComplexComplex），ComplexesComplexes之间的析取被称为覆盖（之间的析取被称为覆盖

34、（之间的析取被称为覆盖（之间的析取被称为覆盖（CoverCover）。）。）。）。如如如如果果果果一一一一个个个个表表表表达达达达式式式式对对对对某某某某个个个个样样样样本本本本为为为为真真真真，则则则则我我我我们们们们称称称称其其其其为为为为对对对对这这这这个个个个样样样样本本本本的的的的一一一一个个个个覆覆覆覆盖盖盖盖。这这这这样样样样，一一一一个个个个空空空空ComplexComplex覆覆覆覆盖盖盖盖所所所所有有有有的的的的样样样样本本本本，而而而而一一一一个个个个空空空空CoverCover不不不不覆盖任何样本。覆盖任何样本。覆盖任何样本。覆盖任何样本。AQR算法相关定义算法相关定义

35、现在学习的是第28页，共46页 在在在在AQRAQR中，一个新样本被区分是看其由哪个规则推导出来的。中，一个新样本被区分是看其由哪个规则推导出来的。中，一个新样本被区分是看其由哪个规则推导出来的。中，一个新样本被区分是看其由哪个规则推导出来的。如如如如果果果果该该该该样样样样本本本本只只只只满满满满足足足足一一一一条条条条规规规规则则则则，则则则则这这这这个个个个样样样样本本本本就就就就属属属属于于于于这这这这条条条条规规规规则则则则；如如如如果果果果该该该该样样样样本本本本满满满满足足足足多多多多条条条条规规规规则则则则，则则则则被被被被这这这这些些些些规规规规则则则则所所所所预预预预测测测

36、测的的的的最最最最频频频频繁繁繁繁的的的的分分分分类类类类被被被被赋赋赋赋予予予予这这这这条条条条规规规规则则则则；如如如如果果果果该该该该样样样样本本本本不不不不属属属属于于于于任任任任何何何何规规规规则则则则，则则则则其其其其分分分分类类类类为为为为样样样样本集中最频繁的分类。本集中最频繁的分类。本集中最频繁的分类。本集中最频繁的分类。AQR算法相关定义算法相关定义现在学习的是第29页，共46页AQR算法描述算法描述 算法算法 4-5 AQR：输入：正例样本输入：正例样本POS；反例样本反例样本NEG 输出：覆盖输出：覆盖COVER现在学习的是第30页，共46页AQR算法描述算法描述（1）

37、COVER=；/初始化初始化COVER为空集为空集（2）WHILE COVER does 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-d

38、efined criteria；/从星中选取一个最好的复合从星中选取一个最好的复合（6）Add BEST as an extra disjuct to COVER；/把最好的复合与把最好的复合与COVER合取，形成新的合取，形成新的COVER（7）END（8）RETURN COVER.现在学习的是第31页，共46页AQR算法描述算法描述算法算法 4-6 STAR：输入：种子输入：种子SEED；反例；反例NEG 输出：星输出：星STAR现在学习的是第32页，共46页AQR算法描述算法描述（1）初始化）初始化STAR为空为空Complex（2）WHILE one or more Complexes

39、 in STAR covers some negative examples in NEG BEGIN /*如果如果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但不覆但

40、不覆盖盖ENEG的的Selectors；*/（5）Let STAR be the set x y|x STAR，y EXTENSION；/*令令STAR=x y|x STAR，y EXTENSION；*/（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

41、to user-defined maximum（maxstar）/*删除删除STAR中最坏的中最坏的Complex直到直到STAR的大小等于或小于用户定义的最大数目的大小等于或小于用户定义的最大数目maxstar*/（8）END（9）RETURN STAR./*返回一系列覆盖返回一系列覆盖SEED但不覆盖但不覆盖NEG的规则的规则*/现在学习的是第33页，共46页AQR算法举例算法举例假设现有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性：size size（属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型）type type

42、（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：正例样本：反例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车SizeTypeClass小型摩托车大众交通小型汽车大众交通中型汽车大众交通微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机l初始化初始化COVER为为，进入循环，进入循环l选取选取SEED=size=巨大巨大型型，type=自行车自行车l调用调用STAR（SEED,NEG）l初始化初始化STAR为为，进入循环，进入循环l选取选取STAR覆盖的负样例，如覆盖的

43、负样例，如ENEG=size=小型小型，type=摩托车摩托车lEXTENSION为覆盖为覆盖SEED，不覆盖，不覆盖ENEG的的选择选择EXTENSION包括包括size=巨大巨大型型和和type=自行车自行车lSTAR=STAR=x y|x STAR，y EXTENSIONSTAR=size=巨大巨大型型 type=自行车自行车l查看查看STAR覆盖的负样例覆盖的负样例l返回返回STAR=size=巨大巨大型型 type=自行车自行车巨大型自行车小型摩托车现在学习的是第34页，共46页AQR算法举例算法举例假设现有一个训练集，其包含两种属性：假设现有一个训练集，其包含两种属性：size s

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

45、巨大型型 type=自行车自行车lCOVER不能不能覆盖到全部的正例覆盖到全部的正例l选取另一个选取另一个SEED=size=巨大巨大型型，type=摩托车摩托车l调用调用STAR（SEED,NEG）l初始化初始化STAR为为，进入循环，进入循环l选取选取STAR覆盖的负样例，如覆盖的负样例，如ENEG=size=小小型型，type=摩托车摩托车lEXTENSION包括包括size=巨大型巨大型lSTAR=size=巨大巨大型型l查看查看STAR覆盖的负样例覆盖的负样例l返回返回STAR=size=巨大巨大型型小型摩托车现在学习的是第35页，共46页AQR算法举例算法举例假设现有一个训练集，其

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

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

48、e size（属性值：微小型，小型，中型，大型，巨大型，庞大型）（属性值：微小型，小型，中型，大型，巨大型，庞大型）type type（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）（属性值：自行车，摩托车，汽车，喷气式飞机，滑翔机）正例样本：正例样本：反例样本：反例样本：SizeTypeClass巨大型自行车捷安特两轮车巨大型摩托车捷安特两轮车微小型喷气式飞机快速飞机小型喷气式飞机快速飞机中型喷气式飞机快速飞机l初始化初始化COVER为为，进入循环，进入循环l选取选取SEED=size=小型小型，type=摩托车摩托车l调用调用STAR（SEED,NEG）l初始化初始化STAR为为，进入

49、循环，进入循环l选取选取STAR覆盖的负样例，如覆盖的负样例，如ENEG=size=巨巨大型大型，type=自行车自行车lEXTENSION为覆盖为覆盖SEED，不覆盖，不覆盖ENEG的的选择选择EXTENSION包含包含size=小型和小型和type=摩托车摩托车lSTAR=STAR=x y|x STAR，y EXTENSIONSTAR=size=小型小型 type=摩托车摩托车l查看查看STAR覆盖的负样例覆盖的负样例l返回返回STAR=size=小型小型 type=摩托车摩托车SizeTypeClass小型摩托车大众交通小型汽车大众交通中型汽车大众交通小型摩托车巨大型自行车现在学习的是第

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