数据挖掘算法_分类数据挖掘

1、1数据挖掘算法数据挖掘算法分类数据挖掘分类数据挖掘内容提要内容提要分类的概念及其应用分类的概念及其应用分类挖掘的过程与方法分类挖掘的过程与方法基于决策树的分类挖掘方法基于决策树的分类挖掘方法ID3方法原理方法原理2分类（分类（Classification）的概念）的概念n分类是最常见的数据挖掘任务，也是人类众多规则之分类是最常见的数据挖掘任务，也是人类众多规则之一。一。n学科分类n生物分类（瑞典植物学家Carl Linnaeus发明）n分成界、门、纲、目、科、属、种。n动物界，如有脊髓的动物被划分为脊椎动物门；附加的特征用于将脊椎动物进一步细分为鸟、哺乳动物、爬行动物纲；这些纲进一步细分，直到

2、分类学的最底层。n同一种的成员在很多方面存在相似性。如形态、繁殖等n新物种的发现n北京时间12月12日消息，美国时代周刊周二评选出2009年度十大新物种，其中“博萨维毛鼠”位居榜首，迷你霸王龙、重达1吨的史前巨蟒均榜上有名。 3分类（分类（Classification）的概念）的概念n分类包括考察一个新出现的对象的特征，并分类包括考察一个新出现的对象的特征，并归类到已定义类中。归类到已定义类中。n在数据挖掘中，分类的对象通常是数据库表或文件中的记录n分类工作首先要有一个清晰定义的类分类工作首先要有一个清晰定义的类n注意： 类的个数是确定的，预先定义好的n其次，要有一系列已分类实例其次，要有一系

3、列已分类实例4分类的应用分类的应用n分类实际上是分类实际上是n先建立某种模型，即根据数据集的特点构造一个分类函数或分类模型。先建立某种模型，即根据数据集的特点构造一个分类函数或分类模型。n然后将其用于对未分类的数据进行分类，即此分类函数或模型能够把然后将其用于对未分类的数据进行分类，即此分类函数或模型能够把未知类别的样本映射到给定的类别之一。未知类别的样本映射到给定的类别之一。n分类与预测分类与预测n这是两种数据分析的形式这是两种数据分析的形式，用來找出模型以描述，用來找出模型以描述数据数据或或预测预测未來未來的变的变化趋势化趋势。常用于：信誉分析、目标市场、医疗诊断、常用于：信誉分析、目标市

4、场、医疗诊断、性能性能预测等。如预测等。如n将信用卡申请者分为高、中、低风险将信用卡申请者分为高、中、低风险n发现欺诈性理赔申请发现欺诈性理赔申请n将考生成绩分成优、良、中、差将考生成绩分成优、良、中、差nn分分类类n银行信贷员需要分析资料，弄清楚哪些贷款申请是安全的，哪些是有银行信贷员需要分析资料，弄清楚哪些贷款申请是安全的，哪些是有风险的风险的。故。故将贷款申请者分为将贷款申请者分为“安全安全” 和和 “有有风险风险” 两类两类。n预测预测n银行信贷员银行信贷员需要需要预测贷款给某个客户预测贷款给某个客户多少多少钱钱是安全的。是安全的。5分类挖掘的方法分类挖掘的方法n要进行分类，就需要有一

5、个分类的规则。要进行分类，就需要有一个分类的规则。n分类的最终结果取决于分类规则n分类的准确度取决于分类规则的优略。n规则很容易用语言表达规则很容易用语言表达n交流语言（英语、汉语、)n结构化语言 if thenn程序语言。如SQL在特定的类别中检索记录n逻辑表达式n分类规则也可以通过手工的方式辛苦地建立分类规则也可以通过手工的方式辛苦地建立起来，也可以通过某种算法得到起来，也可以通过某种算法得到。6分类器的构造方法n（1）统计方法）统计方法n常见的统计方法有常见的统计方法有knnknn算法算法nkNN(k Nearest Neighbors) 假设每一个类包含多个样本数据，而且每个数据都有一

6、个唯一的类标记表示这些样本是属于哪一个分类， kNN就是计算每个样本数据到待分类数据的距离，取与待分类数据最近的k各样本数据，那么这个k个样本数据中哪个类别的样本数据占多数，则待分类数据就属于该类别。n基于事例的学习方法。基于事例的学习方法。7分类器的构造方法n（2 2）机器学习方法）机器学习方法n决策树法决策树法n归纳法归纳法n（3 3）神经网络方法）神经网络方法n神经网络方法主要是神经网络方法主要是BPBP算法算法n粗糙集粗糙集(rough set)(rough set)知识表示是产生式规则n通常，一个分类模型需要在准确度（通常，一个分类模型需要在准确度（Accuracy）和透明度之间进行

7、权衡。和透明度之间进行权衡。n在某些分类应用中，准确是唯一重要的在某些分类应用中，准确是唯一重要的n如邮件分类。通常不关心该模型是如何工作的。n在另一些应用中，透明度就显得格外重要。在另一些应用中，透明度就显得格外重要。n如考试不及格等8分类模型的构造过程：两个阶段分类模型的构造过程：两个阶段n训练阶段训练阶段n在构造模型前，将数据集随机地分为训练集和测试数据集n训练阶段使用训练数据集，通过分析训练数据集的属性来构造模型n假设每个元组属于一个预定义类，由“类标号”属性来确定。训练集中的单个元组称为训练样本, 一个具体样本的形式可为:( V1, V2, ., Vn; c );其中Vi表示属性值,

8、c表示类别。n由于已提供每个训练样本的标号，故称有指导的学习n通常分类模型以分类规则、判定树、数学公式等形式提供n测试阶段测试阶段n用于评估分类模型的准确率。如果一个分类模型的准确率是可接受的，就可以用此模型来对其他未知类别的元组进行分类9分类的两个阶段分类的两个阶段a.a.模型训练阶段模型训练阶段 训练集训练集b.b.使用模型使用模型 分类阶段分类阶段评估准确率（测试评估准确率（测试集）对类标号未知集）对类标号未知的新数据分类的新数据分类 10资料应用过程举例应用过程举例训练样本训练样本婚姻年龄 收入否是否是未婚已婚3535低高否小康1.建立模型测试样本测试样本2. 模型评估X错误率为错误率

9、为 66.67%3.使用模型11分类的规范化描述分类的规范化描述n给定数据集给定数据集Dt1,t2,tn，元组，元组ti D，类的集合类的集合CC1,Cm，n分类问题定义为分类问题定义为n从数据集到类集合的映射f：DC，n即数据集中的元组ti分配到某个类Cj中，n有Cj ti|f(ti) = Cj，1in，且tiD。12基于决策树的分类方法基于决策树的分类方法n决策树是一种常用的、有力的分类工具。决策树是一种常用的、有力的分类工具。n决策树是一种树形结构，决策树包含一系列规则。n通过应用一些简单的规则，将大型记录集分割为小记录集，通过每一次连续分割，结果集中的成员彼此变得越来越相似。n如生物的

10、分类。n“二十问题二十问题”游戏就是典型的决策树分类游戏就是典型的决策树分类n在游戏中，对第一个问题的回答决定了后续的提问，前面的问题先创建具有许多成员的宽泛范畴，后续问题将宽泛范畴分割为越来越小的集合。n如果精心挑选所问的问题，也许只需几个问题就足以得到正确答案。n一般情况下，很少超过20个提问。13基于决策树的分类方法基于决策树的分类方法n“二十问题二十问题”游戏说明了用树来对记录分类的过程。游戏说明了用树来对记录分类的过程。n在根节点进入n然后运用一个规则来确定接下来进入哪个节点n有很多方法可选，一般情况下，选最能判别的测试规则n上述操作反复进行，直到给定的记录进入叶节点为止。n所有终结

11、于该树某个给定叶的记录，在分类的路线所有终结于该树某个给定叶的记录，在分类的路线上都是相同的；从根到每个叶只有唯一的路径，这上都是相同的；从根到每个叶只有唯一的路径，这个路径就是一个用于分类记录规则的表达式个路径就是一个用于分类记录规则的表达式n需要注意的是，不同的叶可能产生相同的分类，这样就出现了分类规则的置信度问题。n如苹果、西红柿、樱桃可能被分为“红色”。但也有绿苹果、黄西红柿。14决策树的类型决策树的类型n多数情况下，树是一个非均匀深度的二元树多数情况下，树是一个非均匀深度的二元树n即每个叶节点有两个子节点，且叶节点与根节点距离并不相同n原理上，树可以有多个分支，原理上，树可以有多个分

12、支，n如SAS Enterprise Miner就提供多元分支15决策树的类型决策树的类型OutlookovercasthumiditywindyhighnormalfalsetruesunnyrainNNPPPovercast每个样本有四个属性，每个样本有四个属性，outlook、temperature、humidity和和 windy，它们都是分类属性，即属性的取值范围都是离散，它们都是分类属性，即属性的取值范围都是离散值的集合，这里用字符串表示这些离散值。类标号用属性值的集合，这里用字符串表示这些离散值。类标号用属性 play表示，它的取值范围也是离散值的集合。如果用表示，它的取值范围也

13、是离散值的集合。如果用 dom（A）表示属性）表示属性 A的取值范围，那么，的取值范围，那么，dom（ outlook）=sunny，overcast，rainydom（ temperature）=hot，mild，cooldom（ humidity）=high，normaldom（ windy）=true，falsedom（ play）=yes，no分类算法的目的就是根据这些训练样本建立一棵决策树，用分类算法的目的就是根据这些训练样本建立一棵决策树，用来预测在各种天气状况下是出门玩耍（来预测在各种天气状况下是出门玩耍（play=yesplay=yes），还是呆），还是呆在家里（在家里（pla

14、y=noplay=no）。）。16树的生成树的生成n尽管目前决策树的生成算法很多，同一算法尽管目前决策树的生成算法很多，同一算法也有许多变体，但都基本过程是相同的。也有许多变体，但都基本过程是相同的。n相对于目标变量而言，没有新生节点比起原生节点有更高的纯度，通过这样形式，把数据重复地拆分为越来越小的群组。n建树的首要任务就是确定哪一个特征（属性）会产生最佳拆分。n最佳拆分是指：能够把记录很好地分割为不同的群组，使每个群组里的单个类成为主导。17n为了寻找对样本进行分类的最优方法，我们要为了寻找对样本进行分类的最优方法，我们要做的工作就是使对一个样本分类时需要问的问做的工作就是使对一个样本分类

15、时需要问的问题最少（即树的深度最小）。因此，我们需要题最少（即树的深度最小）。因此，我们需要某种函数来衡量哪些问题将提供最为有效的划某种函数来衡量哪些问题将提供最为有效的划分分n衡量最佳拆分的指标衡量最佳拆分的指标n信息增益：Information gain（ID3）n增益比率：Gain ration（C4.5）n基尼指数：Gini index (SLIQ，SPRINT)n属性选择度量标准分支指标18ID3的基本思想nQuinlanQuinlan于于 19791979年提出了著名的年提出了著名的 ID3ID3方法。以方法。以ID3ID3为蓝本的为蓝本的C4.5C4.5是一个能处理连续属性的算法

16、。其他是一个能处理连续属性的算法。其他决策树方法还有决策树方法还有ID3ID3的增量版本的增量版本ID4ID4和和ID5ID5等。在此等。在此主要介绍主要介绍 ID3ID3算法。算法。n基本思想：基本思想：n在决策树的各级节点上选择属性时，用信息增益作为选择标准，以便在对每个非叶节点进行测试时，获得最大的类别信息。n具体方法具体方法n检查所有的属性，选择信息增益最大的属性产生决策树节点，由此属性的不同取值建立分支n再对各分支的子集重复上述操作，建立下一层分支，直到所有子集仅包含同一类别的数据为止。n最后会得到一棵决策树，用于对新样本进行分类19信息量信息量n设设是训练样本数据集，是训练样本数据

17、集，中类别标识属性有中类别标识属性有个独立的取值，也就是说定义了个独立的取值，也就是说定义了个类个类C，=，。设。设S S是是C类（子集）中类（子集）中样本数。样本数。n集合集合在分类中的期望信息量为在分类中的期望信息量为miiiSpSpSS12m21)(log)(S.I），（20熵熵n可见，样本的概率分布越均衡，它的信息量（熵）就越大，样可见，样本的概率分布越均衡，它的信息量（熵）就越大，样本集的混杂程度也越高。因此，熵可以作为训练集的不纯度本集的混杂程度也越高。因此，熵可以作为训练集的不纯度（impurity）的一个度量，熵越大，不纯度就越高。这样，）的一个度量，熵越大，不纯度就越高。这样

18、，决策树的分支原则就是使划分后的样本的子集越纯越好，即它决策树的分支原则就是使划分后的样本的子集越纯越好，即它们的熵越小越好。们的熵越小越好。 设属性设属性A A具有具有n n个取值个取值a1a1，a2a2，,an ,an ，可以用属性，可以用属性A A将将S S划分划分为为n n个子集个子集S1S1，S2S2，SnSn，设，设S Sijij是子集是子集S Sj j中属于类中属于类C Ci i的样的样本数，由本数，由A A划分成子集的熵划分成子集的熵),.,(.)E21121mjjjnjmjjjSSSIsSSSA（21信息增益信息增益nGain（A）I（S1，S2，,Sm）-E(A)22天气天气温度温度湿度湿度风况风况运动运动晴8585无不适合晴8090有不适合多云8378无适合有雨7096无适合有雨6880无适合有雨6570有不适合多云6465有适合晴7295无不适合晴6970无适合有雨7580无适合晴7570有适合多云7290有适合多云817