《数据仓库与数据挖掘》(分类规则)
- 格式:doc
- 大小:1.86 MB
- 文档页数:50
数据仓库与数据挖掘数据仓库和数据挖掘是现代企业中重要的信息技术工具,用于管理和分析大规模数据集。
数据仓库是一个集成的、主题导向的、时间变化的数据集合,用于支持管理决策和业务分析。
而数据挖掘则是在数据仓库中发现隐藏在数据中的有价值的信息和模式的过程。
一、数据仓库1. 定义数据仓库是一个面向主题的、集成的、稳定的、非易失的数据集合,用于支持管理决策和业务分析。
它是从多个数据源中提取、清洗、转换和加载数据,以便用户可以方便地访问和分析数据。
2. 架构数据仓库的架构通常包括以下几个组件:- 数据源:数据仓库从多个数据源中提取数据,包括关系型数据库、文件系统、Web服务等。
- 数据清洗:数据清洗是将数据进行去重、纠错、格式化等处理,以确保数据的质量和一致性。
- 数据转换:数据转换是将清洗后的数据进行转换和整合,以适应数据仓库的结构和格式。
- 数据加载:数据加载是将转换后的数据加载到数据仓库中,通常使用批量加载或增量加载的方式。
- 数据存储:数据存储是数据仓库的核心组件,通常使用关系型数据库或列式数据库来存储数据。
- 元数据管理:元数据是描述数据仓库中数据的数据,包括数据的结构、关系、来源等信息。
- 查询和分析:数据仓库提供了灵活的查询和分析功能,用户可以根据需要进行多维分析、数据挖掘等操作。
3. 优势数据仓库的优势包括:- 集成性:数据仓库可以将来自不同数据源的数据进行整合和统一管理,提供一致的数据视图。
- 面向主题:数据仓库以主题为导向,将数据组织成易于理解和分析的形式,方便用户进行决策和分析。
- 非易失性:数据仓库中的数据是非易失的,即使在数据源发生故障或丢失时,仍然可以恢复和重建数据。
- 支持决策:数据仓库提供了强大的查询和分析功能,可以帮助用户进行决策和业务分析。
- 高性能:数据仓库使用优化的存储和查询技术,可以提供快速的数据访问和查询响应时间。
二、数据挖掘1. 定义数据挖掘是从大规模数据集中发现隐藏在数据中的有价值的信息和模式的过程。
数据仓库与数据挖掘教学大纲引言概述:数据仓库与数据挖掘是现代信息技术领域中的重要概念,对于培养学生的信息分析和决策能力具有重要意义。
因此,制定一份完善的数据仓库与数据挖掘教学大纲对于高等教育机构来说至关重要。
本文将从四个方面详细阐述数据仓库与数据挖掘教学大纲的内容。
一、数据仓库的基本概念1.1 数据仓库的定义和特点数据仓库是指将多个数据源中的数据集成到一个统一的、面向主题的、稳定的、非易失的数据存储中,以支持决策支持系统和数据分析。
数据仓库的特点包括数据集成、面向主题、稳定性和非易失性等。
1.2 数据仓库的架构和组成数据仓库的架构包括数据源层、数据集成层、数据存储层和数据展示层。
数据源层用于获取和整合各种数据源的数据,数据集成层负责将数据进行清洗和转换,数据存储层用于存储清洗后的数据,数据展示层则是为用户提供数据查询和分析的接口。
1.3 数据仓库的设计和建模数据仓库的设计和建模是指根据业务需求和数据分析目标,对数据仓库的结构和内容进行设计和建模。
数据仓库的设计和建模需要考虑数据模型、维度建模、事实表与维度表的设计等方面。
二、数据挖掘的基本概念2.1 数据挖掘的定义和目标数据挖掘是指从大规模数据集中发现隐藏于其中的有用信息和模式的过程。
数据挖掘的目标包括分类、聚类、关联规则挖掘、异常检测等。
2.2 数据挖掘的方法和技术数据挖掘的方法和技术包括统计分析、机器学习、人工智能等。
其中,统计分析包括描述统计和推断统计,机器学习包括监督学习和无监督学习,人工智能包括神经网络和遗传算法等。
2.3 数据挖掘的应用领域数据挖掘的应用领域广泛,包括市场营销、金融风险管理、医疗诊断、社交网络分析等。
数据挖掘在各个领域的应用可以帮助企业和组织做出更准确的决策和预测。
三、数据仓库与数据挖掘的关系3.1 数据仓库与数据挖掘的联系数据仓库与数据挖掘是相辅相成的关系,数据仓库提供了数据挖掘的数据源,而数据挖掘则可以从数据仓库中发现有用的信息和模式。
数据仓库与数据挖掘数据仓库和数据挖掘是现代信息技术领域中的重要概念,它们在企业和组织中扮演着关键角色。
数据仓库是一个用于存储、管理和分析大量数据的集中式数据库系统,而数据挖掘则是通过应用统计学、机器学习和人工智能等技术,从数据仓库中发现隐藏的模式、关联和趋势。
数据仓库的标准格式通常包括以下几个组成部分:1. 数据源:数据仓库的数据源可以来自多个不同的系统和应用程序,如企业资源计划(ERP)系统、客户关系管理(CRM)系统、销售和市场数据等。
这些数据源需要经过提取、转换和加载(ETL)的过程,以便将数据导入到数据仓库中。
2. 数据模型:数据仓库的数据模型是一个逻辑结构,用于描述数据之间的关系和组织方式。
常见的数据模型包括星型模型和雪花模型。
星型模型由一个中心事实表和多个维度表组成,而雪花模型在星型模型的基础上进一步细化维度表的结构。
3. 数据存储:数据仓库通常使用关系数据库管理系统(RDBMS)作为数据存储的基础。
常见的RDBMS包括Oracle、MySQL和SQL Server等。
数据存储的设计需要考虑数据的容量、性能和查询需求等因素。
4. 数据访问:数据仓库的数据可以通过多种方式进行访问和查询,如结构化查询语言(SQL)、在线分析处理(OLAP)和数据挖掘工具等。
这些工具可以帮助用户从数据仓库中提取所需的信息,并进行多维分析和数据挖掘。
5. 数据质量:数据仓库的数据质量是保证数据准确性和一致性的关键因素。
数据质量管理包括数据清洗、去重、校验和修复等步骤,以确保数据仓库中的数据是可信的和可用的。
而数据挖掘的标准格式通常包括以下几个步骤:1. 目标定义:在进行数据挖掘之前,需要明确挖掘的目标和问题。
例如,预测销售额、发现市场细分、识别欺诈行为等。
2. 数据准备:数据挖掘需要准备和清洗数据,以确保数据的质量和可用性。
这包括数据清洗、数据集成、数据转换和数据规范化等步骤。
3. 特征选择:在数据挖掘过程中,需要选择最相关和有价值的特征变量。
数据仓库与数据挖掘教学大纲引言概述:数据仓库与数据挖掘是现代信息技术领域中的重要概念,对于培养学生的数据分析和决策能力具有重要意义。
因此,制定一份完善的数据仓库与数据挖掘教学大纲是必不可少的。
本文将从数据仓库与数据挖掘的基本概念、教学目标、教学内容、教学方法和评价方式五个方面,详细阐述数据仓库与数据挖掘教学大纲的内容。
一、基本概念1.1 数据仓库的定义与特点数据仓库是指将各类数据按照一定的结构和规范集成到一个统一的存储空间中,以支持决策分析和业务智能的技术体系。
它具有数据集成、主题导向、面向决策支持等特点。
1.2 数据挖掘的定义与作用数据挖掘是指通过自动或者半自动的方式,从大规模数据中发现隐藏的模式、关联和规律,用于预测、分类、聚类和异常检测等任务。
它可以匡助人们更好地理解数据,提供决策支持和业务洞察。
1.3 数据仓库与数据挖掘的关系数据仓库提供了数据挖掘所需的高质量、一致性和集成性数据,而数据挖掘则通过对数据仓库进行分析和挖掘,发现有价值的信息和知识。
二、教学目标2.1 知识目标学生应该掌握数据仓库和数据挖掘的基本概念、原理和方法,了解数据仓库与数据挖掘在实际应用中的意义和作用。
2.2 技能目标学生应该具备数据仓库和数据挖掘的建模、设计和实施能力,能够运用相应的工具和算法进行数据分析和挖掘。
2.3 态度与价值观目标学生应该培养数据驱动决策的思维方式,注重数据的质量和准确性,提高数据分析和决策的能力。
三、教学内容3.1 数据仓库的建设与管理包括数据仓库的设计原则、数据抽取与清洗、数据集成与转换、数据加载与更新、数据仓库的查询与分析等内容。
3.2 数据挖掘的基本方法与算法包括分类与预测、聚类分析、关联规则挖掘、时序模式挖掘等数据挖掘的基本方法和常用算法。
3.3 数据挖掘的应用案例通过实际案例的分析和讨论,让学生了解数据挖掘在不同领域中的应用,如市场营销、金融风控、医疗健康等。
四、教学方法4.1 理论讲授予案例分析通过教师的讲解和案例的分析,向学生介绍数据仓库与数据挖掘的基本概念和方法,培养学生的理论思维和实际应用能力。
数据仓库与数据挖掘一、数据仓库数据仓库是指将企业的各类数据集中存储、整合和管理的系统。
它是一个面向主题的、集成的、稳定的、随时间变化的数据集合,用于支持企业决策和分析。
数据仓库的建设和维护需要遵循一定的标准和规范。
1. 数据仓库架构数据仓库的架构是指数据仓库系统的组成和结构。
常见的数据仓库架构包括三层架构和星型架构。
三层架构由数据源层、数据存储层和数据应用层组成。
数据源层负责从各个数据源(如数据库、文件等)抽取数据,数据存储层用于存储和管理数据,数据应用层提供各类决策支持和分析功能。
星型架构由中心事实表和多个维度表组成。
中心事实表包含了业务过程中的关键指标,维度表描述了这些指标的上下文信息。
2. 数据抽取与清洗数据仓库的数据抽取与清洗是指从各个数据源中提取数据,并进行清洗和转换,以适应数据仓库的需求。
数据抽取与清洗的过程需要确保数据的准确性、一致性和完整性。
数据抽取可以通过批量抽取、增量抽取和实时抽取等方式进行。
数据清洗包括数据去重、数据格式转换、数据合并和数据校验等操作。
3. 数据存储与管理数据仓库的数据存储与管理是指将清洗后的数据存储到数据仓库中,并进行管理和维护。
数据存储可以采用关系型数据库、多维数据库或者列式数据库等。
数据管理包括数据的备份与恢复、数据的索引与分区、数据的压缩与加密等操作。
同时,数据的质量管理也是数据存储与管理的重要内容,包括数据的准确性、一致性、完整性和可靠性等方面。
4. 数据查询与分析数据仓库的数据查询与分析是指通过各类分析工具和技术,对数据仓库中的数据进行查询、分析和挖掘,以支持企业的决策和分析需求。
常见的数据查询与分析工具包括在线分析处理(OLAP)、数据挖掘工具、报表工具和可视化工具等。
这些工具可以帮助用户从不同的角度和维度对数据进行多维分析、趋势分析和关联分析等。
二、数据挖掘数据挖掘是指从大量的数据中发现隐藏在其中的有价值的信息和知识的过程。
数据挖掘技术可以帮助企业发现潜在的商机、改进产品和服务、提高决策的准确性和效率。
数据仓库与数据挖掘中的关联规则数据是当今社会中最重要的资源之一,每天,我们都在不知不觉中产生大量的数据,例如浏览网页、使用社交媒体、进行购物、使用手机等等。
这些数据是非常有价值的,因为它们可以被用来揭示用户的行为与偏好,帮助企业更好地理解他们的客户、预测市场趋势和做出更准确的商业决策。
然而,这种大规模的数据分析是一项极为复杂的任务,需要运用一系列的技术和工具来帮助用户快速、准确地发现有用的信息。
数据仓库是一种用于存储和管理大量数据的系统,它是数据挖掘技术的基础。
数据仓库通常是一个基于数据库的系统,它可以从多个数据来源中抽取、转换和加载数据,并将其存储在一个单独的、集中的存储器中。
这些数据可以是来自各种不同的数据源,如企业资源计划(ERP)系统、客户关系管理(CRM)系统、人力资源管理(HRM)系统等。
数据仓库具有高度的灵活性和可扩展性,可以随着企业的数据需求而不断增加。
与数据仓库紧密相关的技术是数据挖掘。
数据挖掘是一种从数据库中挖掘知识、信息和模式的技术,它能够帮助用户发现隐藏在数据背后的规律,从而使企业更好地理解其客户行为和市场趋势。
数据挖掘技术包括分类、聚类、关联规则发现等,其中关联规则发现是数据挖掘的一个重要技术,在数据挖掘中有着广泛的应用。
关联规则发现是一种发现事物关联性的技术,主要是为了找出输入数据之间的共同关系。
通俗理解就是发现购物清单中购买了A商品,很可能会购买B商品的规律。
关联规则在购物篮分析、市场策略、天气预报、医学等领域都有广泛的应用。
在数据挖掘领域,关联规则发现可以用来分析大量的数据,以了解哪些数据项一起出现的可能性最大。
这种技术可以为广告定位、生产预测、金融风险评估等提供有效的决策支持。
关联规则算法的核心思想是:在给定数据集中,发现各种项之间的关系。
数据集通常包含很多事务,每个事务由一些项组成。
例如,在一个购物清单数据集中,每件商品可以表示为一个“项”,而单个购物车可以表示为一个“事务”。
第9章分类规则挖掘与预测主要内容●分类与预测的基本概念●决策树方法●分类规则挖掘的ID3算法●其他分类规则挖掘算法●分类规则的评估●微软决策树及其应用9.1分类与预测的基本概念1. 什么是分类数据分类(data classfication)是数据挖掘的主要内容之一,主要是通过分析训练数据样本,产生关于类别的精确描述。
这种类别通常由分类规则组成,可以用来对未来的数据进行分类和预测。
数据分类(data classfication)是一个两个步骤的过程:●第1步:建立一个模型,描述给定的数据类集或概念集(简称训练集)。
通过分析由属性描述的数据库元组来构造模型。
每个元组属于一个预定义的类,由类标号属性确定。
用于建立模型的元组集称为训练数据集,其中每个元组称为训练样本。
由于给出了类标号属性,因此该步骤又称为有指导的学习。
如果训练样本的类标号是未知的,则称为无指导的学习(聚类)。
学习模型可用分类规则、决策树和数学公式的形式给出。
●第2步:使用模型对数据进行分类。
包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。
训练数(a)学习2. 常用的分类规则挖掘方法分类规则挖掘有着广泛的应用前景。
对于分类规则的挖掘通常有以下几种方法,不同的方法适用于不同特点的数据:●决策树方法●贝叶斯方法●人工神经网络方法●约略集方法●遗传算法典型的分类规则挖掘算法有:●ID3●C4.5●DBlearn等3. 什么是预测预测(prediction)是构造和使用模型评估无标号样本类,或评估给定的样本可能具有的属性或区间值。
分类和回归是两类主要的预测问题。
分类是预测离散值,回归用于预测连续或有序值。
4. 分类和预测数据的预处理●数据清理:使用平滑技术消除或减少噪声;处理空缺值。
●相关性分析:删除与分类或预测无关的属性;删除冗余属性。
●数据变换:使用概念分层将数据概化到高的层次;连续值属性概化为离散区间;数据规范化,即将某一属性的所有值按比例缩放,使其落入指定的区间。
数据仓库与数据挖掘
(DataWarehouseandDataMining)
总学时:48学时理论:48学时实验(上机、实习等):。
学时
学分:3
课程主要内容:
数据仓库(DW)与数据挖掘(DM)是20世纪90年代中期兴起的新技术。
数据仓库用于决策分析,数据挖掘用于从数据库中发现知识。
数据仓库和数据挖掘的结合为决策支持系统(DSS)开辟了新方向,它们也是商业智能(B1)的主要技术。
数据仓库与数据挖掘是计算机专业的选修课程,本课程主要讲述:数据仓库的基本概念、原理及应用;各类数据挖掘的分类、原理与方法。
介绍数据仓库的概念、特征、存贮结构及数据分析的手段。
重点介绍数据挖掘中的分类挖掘、聚类挖掘、关联规则挖掘的概念、原理、方法及应用特征。
简单介绍WEB挖掘、空间数据挖掘、时序数据挖掘等的基本原理与方法。
同时,结合高级语言与SQ1编写锻炼学习者在数据库中对数据进行提取与分析能力。
先修课程:
≪C语言程序设计》、《离散数学》、《数据结构》、《数据库系统原理》、《操作系统原理》等。
适用专业:
计算机科学与技术
教材:
MargaretH.Dunham著,郭崇慧等译.《数据挖掘教程》.北京:清华大学出版社,2005教学参考书:
[1]范明等译.《数据挖掘概念与技术》.北京:机械工业出版社,2008。
第9章分类规则挖掘与预测主要内容●分类与预测的基本概念●决策树方法●分类规则挖掘的ID3算法●其他分类规则挖掘算法●分类规则的评估1微软决策树及其应用23 9.1分类与预测的基本概念1. 什么是分类数据分类(data classfication )是数据挖掘的主要内容之一,主要是通过分析训练数据样本,产生关于类别的精确描述。
这种类别通常由分类规则组成,可以用来对未来的数据进行分类和预测。
数据分类(data classfication )是一个两个步骤的过程:● 第1步:建立一个模型,描述给定的数据类集或概念集(简称训练集)。
通过分析由属性描述的数据库元组来构造模型。
每个元组属于一个预定义的类,由类标号属性确定。
用于建立模型的元组集称为训练数据集,其中每个元组称为训练样本。
由于给出了类标号属性,因此该步骤又称为有指导的学习。
如果训练样本的类标号是未知的,则称为无指导的学习(聚类)。
学习模型可用分类规则、决策树和数学公式的形式给出。
● 第2步:使用模型对数据进行分类。
包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。
(a )学习 训练数据图9-1 数据分类过程2. 常用的分类规则挖掘方法分类规则挖掘有着广泛的应用前景。
对于分类规则的挖掘通常有以下几种方法,不同的方法适用于不同特点的数据:●决策树方法●贝叶斯方法●人工神经网络方法●约略集方法4●遗传算法典型的分类规则挖掘算法有:●ID3●C4.5●DBlearn等3. 什么是预测预测(prediction)是构造和使用模型评估无标号样本类,或评估给定的样本可能具有的属性或区间值。
分类和回归是两类主要的预测问题。
分类是预测离散值,回归用于预测连续或有序值。
4. 分类和预测数据的预处理●数据清理:使用平滑技术消除或减少噪声;处理空缺值。
●相关性分析:删除与分类或预测无关的属性;删除冗余属性。
●数据变换:使用概念分层将数据概化到高的层次;连续值属性概化为离散区间;数据规范化,即将某一属性的所有值按比例缩放,使其落入指定的区间。
55. 分类方法的评估标准●准确率:模型正确预测新数据类标号的能力。
●速度:产生和使用模型花费的时间。
●健壮性:有噪声数据或空缺值数据时模型正确分类或预测的能力。
●伸缩性:对于给定的大量数据,有效地构造模型的能力。
●可解释性:学习模型提供的理解和观察的层次。
9.2决策树方法决策树方法的起源是概念学习系统CLS,然后发展到由Quiulan研制ID3方法,然后到著名的C4.5算法,C4.5算法的一个优点是它能够处理连续属性。
还有CART算法和Assistant算法也是比较有名的决策树方法。
1. 什么是决策树决策树(Decision Tree)又称为判定树,是运用于分类的一种树结构。
其中的每个内部结点(internal node)代表对某个属性的一次测试,每条边代表一个测试结果,叶结点(leaf)代表某个类(class)或者类的分布(class distribution),最上面的结点是根结点。
6决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。
下例是为了解决这个问题而建立的一棵决策树,从中可以看到决策树的基本组成部分:决策结点、分支和叶结点。
〖例〗图9-2 给出了一个商业上使用的决策树的例子。
它表示了一个关心电子产品的用户是否会购买PC (buys_computer)的知识,用它可以预测某条记录(某个人)的购买意向。
图9-2 buys_computer的决策树7这棵决策树对销售记录进行分类,指出一个电子产品消费者是否会购买一台计算机“buys_computer”。
每个内部结点(方形框)代表对某个属性的一次检测。
每个叶结点(椭圆框)代表一个类:buys_computers=yes 或者buys_computers=no在这个例子中,样本向量为:(age, student, credit_rating; buys_computers)被决策数据的格式为:(age, student, credit_rating)输入新的被决策的记录,可以预测该记录隶属于哪个类。
2. 使用决策树进行分类构造决策树是采用自上而下的递归构造方法。
以多叉树为例,如果一个训练数据集中的数据有几种属性值,则按照属性的各种取值把这个训练数据集再划分为对应的几个子集(分支),然后再依次递归处理各8个子集。
反之,则作为叶结点。
决策树构造的结果是一棵二叉或多叉树,它的输入是一组带有类别标记的训练数据。
二叉树的内部结点(非叶结点)一般表示为一个逻辑判断,如形式为(a = b)的逻辑判断,其中a 是属性,b是该属性的某个属性值;树的边是逻辑判断的分支结果。
多叉树(ID3)的内部结点是属性,边是该属性的所有取值,有几个属性值,就有几条边。
树的叶结点都是类别标记。
使用决策树进行分类分为两步:●第1步:利用训练集建立并精化一棵决策树,建立决策树模型。
这个过程实际上是一个从数据中获取知识,进行机器学习的过程。
●第2步:利用生成完毕的决策树对输入数据进行分类。
对输入的记录,从根结点依次测试记录的属性值,直到到达某个叶结点,从而找到该记录所在的类。
问题的关键是建立一棵决策树。
这个过程通常分为两个阶段:●建树(Tree Building):决策树建树算法见下,可以看得出,这是一个递归的过程,最终将得到一棵树。
●剪枝(Tree Pruning):剪枝是目的是降低由于训练集存在噪声而产生的起伏。
9.3 分类规则挖掘的ID3算法由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法。
ID3即决策树归纳(Induction of Decision Tree)。
早期的ID算法只能就两类数据进行挖掘(如正类和反类);经过改进后,现在ID算法可以挖掘多类数据。
待挖掘的数据必须是不矛盾的、一致的,也就是说,对具9有相同属性的数据,其对应的类必须是唯一的。
在ID3算法挖掘后,分类规则由决策树来表示。
1. ID3算法的基本思想由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间,该搜索空间是针对某一特定问题而提出的。
系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的。
评价函数一般依据分类的准确度和树的大小来决定决策树的质量。
如果两棵决策树都能准确地在测试集进行分类,则选择较简单的那棵。
相对而言,决策树越简单,则它对未知数据的预测性能越佳。
寻找一棵“最好”的决策树是一个NP完全问题。
ID3使用一种自顶向下的方法在部分搜索空间创建决策树,同时保证找到一棵简单的决策树—可能不是最简单的。
ID3算法的基本思想描述如下:step 1.任意选取一个属性作为决策树的根结点,然后就这个属性所有的取值创建树的分支;step 2.用这棵树来对训练数据集进行分类,如果一个叶结点的所有实例都属于同一类,则以该类为标记标识此叶结点;如果所有的叶结点都有类标记,则算法终止;step 3.否则,选取一个从该结点到根路径中没有出现过的属性为标记标识该结点,然后就这个属性所有的取值继续创建树的分支;重复算法步骤step 2;10这个算法一定可以创建一棵基于训练数据集的正确的决策树,然而,这棵决策树不一定是简单的。
显然,不同的属性选取顺序将生成不同的决策树。
因此,适当地选取属性将生成一棵简单的决策树。
在ID3算法中,采用了一种基于信息的启发式的方法来决定如何选取属性。
启发式方法选取具有最高信息量的属性,也就是说,生成最少分支决策树的那个属性。
2. ID3算法的描述算法:Generate_decision_tree由给定的训练数据产生一棵决策树输入:训练数据集samples,用离散值属性表示;候选属性的集合attribute_list。
输出:一棵决策树方法:(1)创建结点N;(2)if samples 都在同一个类C then(3)返回N作为叶结点,用类C标记;(4)if attribute_list 为空then(5)返回N作为叶结点,标记samples中最普通的类;//多数表决11(6)选择attribute_list中具有最高信息增益的属性test_attribute;//用信息增益作为属性选择度量(7)标记结点N为test_attribute;(8)for each test_attribute中的已知值ai //划分samples(9)由结点N生长出一个条件为test_attribute=ai的分枝;(10)设si为samples中test_attribute=ai的样本集合;//一个划分(11)if si为空then(12)加上一个叶结点,标记为标记samples中最普通的类;//多数表决(13)else 加上一个由Generate_decision_tree(si, attribute_list-test_attribute)返回的结点;2. 属性选择度量在Generate_decision_tree算法的Step 6,算法需选择attribute_list中具有最高信息增益的属性test_attribute。
ID3算法在树的每个结点上以信息增量(information gain)作为度量来选择测试属性。
这种度量称为属性选择度量或分裂的优良性度量。
选择具有最高信息增益(或最大熵压缩)的属性作12为当前结点的测试属性。
该属性使得对结果划分中的样本分类所需要的信息量最小,并确保找到一棵简单的(但不一定是最简单的)决策树。
Information Gain指标的原理来自于信息论。
1948年,香农(C. E. Shannon)提出了信息论。
其中给出了关于信息量(Information)和熵(Entropy)的定义,熵实际上是系统信息量的加权平均,也就是系统的平均信息量。
设S是有s个训练样本数据的集合,类标号属性具有m个不同值,定义m个不同类Ci(i=1,2,…,m),si是类Ci中的样本数,则对一个给定的训练样本分类所需要的期望信息为:I (s1, s2, … , s m)=-ΣM i=1 pi log2(pi)i其中pi是任意样本属于Ci的概率,可用si/s来估计。
设属性A具有k个不同值{a1,a2,…,ak},则可用属性A将S划分为k个子集{S1,S2,…,Sk},Sj中包含的样本在属性A上具有值aj。
如果选择A作为测试属性,则这些子集对应于由包含集合S的结点生长出来的分枝。
设s ij是子集Sj中类Ci的样本数,则按照A划分成子集的熵为:E(A)=ΣM i=1((s1j+ s2j +…+s mj)/ s1j)* I (s1, s2, … , s m)信息增益(Information Gain),表示系统由于分类获得的信息量。