法律状态公告日
法律状态信息
法律状态
2018-07-24
专利权的转移 IPC(主分类):G06F17/30 登记生效日:20180705 变更前: 变更后: 申请日:20140305
专利申请权、专利权的转移
2017-01-25
授权
授权
2014-07-16
实质审查的生效 IPC(主分类):G06F17/30 申请日:20140305
实质审查的生效
2014-06-25
公开
公开
技术领域
本发明涉及一种基于代价敏感的决策树分类方法,主要用于解决信息物理 融合系统中数据高效分类和在分类时产生的损失或代价总和为最小的问题,属 于信息物理融合系统和数据挖掘的交叉技术应用领域。
背景技术
信息物理融合系统被认为是继计算机、互联网之后世界信息技术的第三次浪潮。信息物 理融合系统可以理解为基于嵌入式设备的高效网络化智能信息系统,是具有高度自主感知、 自主判断、自主调节和自治能力,能够实现虚拟世界和现实物理世界互联与协同的下一代智 能系统。信息物理融合系统在功能上主要考虑性能优化,是集计算(Computation)、通信 (Communication)与控制(Control)3C于一体的智能技术。现在,信息物理融合系统技术 已经得到了国际工商业界和许多大型国际公司的高度关注,发展速度极为迅速,已被应用于 交通、医疗、能源等多个重要发展领域,具有广阔的应用前景。
数据挖掘是一个迭代过程,它从大量的数据中搜寻有价值的、非同寻常的新信息,是人 和计算机合作的结果;它在人类专家描述问题和目标的知识与计算机的搜索能力之间寻求平 衡,以求获得最好的结果。数据挖掘是计算机行业中发展最快的领域之一,以前它只是计算 机科学和统计学中的一个主题,现如今,它已经迅速发展成为一个独立的领域。数据挖掘最 强大的一个优势在于它可以把许多方法和技术应用与大量的问题集。数据挖掘是一个在大数 据集上进行的自然行为,所以其最大的目标市场是整个数据仓库、数据集市和决策支持业界, 包括诸如零售、制造、电信、医疗、保险、运输等行业。
分类是一种重要的数据分析形式,它提取刻画重要数据类的模型。这种模型称为分类器, 预测分类的类标号。分类一般分为两个步骤:第一步,我们基于给出的数据建立一个分类模 型;第二步,确定该模型的准确率是否可以接受,如果可以,则使用该模型对新的数据进行 分类。大部分的分类算法是内存驻留的算法,通常假定数据量很小。随着现代技术的不断发 展,数据挖掘研究建立在这些工作基础上,开发了可伸缩的分类和预测技术,能够处理大的、 驻留磁盘的数据。分类有大量应用,包括欺诈检测、目标营销、性能预测、制造和医疗诊断 等。
决策树是一种类似流程图的树结构,它是一种典型的分类方法。它首先对数据进行处理, 利用归纳算法生成可读的规则并建立决策树,然后使用决策对新数据进行分析。本质上决策 树是通过一系列规则对数据进行分类的过程。在20世纪70年代后期和20世纪80年代初期, 机器学习研究院J.RossQuinlan开发了决策树算法,称为迭代的二分器(IterativeDichotomiser, ID3)。Quinlan后来又提出了ID3的后继C4.5成为了新的监督学习算法的性能比较基准。1984 年,多位统计学家出版了《ClassificationandRegressionTrees》(CART),介绍了二叉决策树 的产生。传统的决策树算大多采用了贪心方法,并且使用了自顶向下递归的分治方法构造树 结构。
代价敏感(Cost-SensitiveLearning,CSL)分类问题的原型是医疗诊断问题。在该问题 中,医生得为病人种种医疗测试的可能性、测试代价以及期望得到的测试效果进行权衡。代 价敏感的学习方法主要考虑在分类中,当不同的分类错误会导致不同的惩罚力度时如何训练 分类器。例如在医疗中,“将病人误诊为健康人的代价”与“将健康人误诊为病人的代价”不同; 在金融信用卡盗用检测中,“将盗用误认为正常使用的代价”与将“正常使用误认为盗用的代 价”也不同。不难看出,出现误判的可能性是很小的,但如果不能正确地判断一个潜在的误判, 将会导致一系列的损失,因而以最终的损失作为衡量目标更有现实意义。
自从基于代价敏感的代价学习被提出以来,引起了很多专家的关注,提出了很多新颖的 方法。总的来看,有两类基本思路:一种方法就是不改变经典的分类方法,而只是对原有的 数据集作一定的处理,或者说是在经典的分类算法之外包裹一层算法,使之达到预定的对代 价敏感的目的;另一种思路则是在经典分类算法基础之上,加入一些其它因素,达到代价敏 感学习的目的。
发明内容
技术问题:本发明的目的是提供一种基于代价敏感决策树的信息物理融合系统数据分类 方法,该方法在决策树建立的过程中增加了代价敏感的考虑,以解决信息物理融合系统中数 据高效分类,以及在分类时将产生的损失或代价总和降至最小的问题。
技术方案:本发明所述的基于代价敏感决策树的信息物理融合系统数据分类方法,用户 先在信息物理融合系统中构建多棵决策树,再将这些决策树组成一个组合决策树。在基于代 价敏感的考虑下,通过对组合决策树错误率的计算,对数据进行分类。
本发明所述的信息物理融合系统由若干物理单元和一个信息单元组成,其中所述的物理 单元用于收集数据;所述信息单元用于接收并存储物理单元发送的数据,以及对这些进行分 析和处理。
基于代价敏感决策树的信息物理融合系统数据分类方法包括以下步骤:
步骤1)用户将信息物理融合系统的组成单元划分为多个物理单元和一个信息单元;所 述物理单元用于收集数据,所述信息单元用于分析和处理数据;
步骤2)用户预先将训练样本和测试样本放置在系统中,所述训练样本和测试样本中的 每个样本包括样本号、属性名称、对应的属性值和类别;
步骤3)用户启动每个物理单元收集训练样本数据;
步骤4)每个物理单元将收集到的训练样本数据发送至信息单元,信息单元对不同物理 单元发送来的训练样本数据进行分别存储;
步骤5)信息单元根据分别存储的样本数据分别为这些物理单元建立相应的决策树,所 述决策树为机器学习分类算法中的一种树型结构的分类器,分类器是一种计算机程序,作用 是可自动将数据分到已知类别;
步骤6)信息单元将得到的决策树放置到一个列表中,组成一个决策树列表,所述列表 为数据结构中按照线性顺序,排列而成的数据项的集合,可以在这种数据结构上进行基本操 作包括对元素的的查找、插入和删除;
步骤7)信息单元对每个决策树进行测试。具体步骤如下:
步骤7.1)将一组准备好的测试样本输入到每个建立好的决策树中;
步骤7.2)测试样本经过决策树的决策会得到相应的分类结果;
步骤7.3)将得到的分类结果和测试样本本身的类别进行比对,相同则分类正确,不 同则分类错误;记录错误分类的样本数;
步骤7.4)如果错误分类的测试样本数和总的测试样本数的比值大于10%,则在决策 树列表中删除此决策树,若否则将其保留在决策树列表中;其中将错误分类的测试样本数和 总的测试样本数的比值记为wi,记录在信息单元中,i表示决策树列表里第i个决策树;
步骤8)经过上述步骤后,若决策树列表为空,则选取wi最小的那棵决策树作为最终的 决策树;
步骤9)如果决策树列表只含有一棵决策树,则这课决策树为最终的决策树;
步骤10)如果决策树列表含有两棵或两棵以上的决策树,则将决策树列表中的决策树作 为组合决策树,所述组合决策树为多个决策树组成的分类器,每个决策树有相应的权值,该 权值为错误分类的测试样本数和总的测试样本数的比值;
步骤11)计算组合决策树的错误分类率H,返回H值最小时所对应的类别作为数据的分 类结果;其中H通过计算获得,i表示第i棵决策树;j表示类别;Ci,j表 示通过第i个决策树后得到的分类结果是否为类别j,若是则Ci,j值为1,若否则Ci,j值为0;wi表示之前测试时第i棵决策树中错误分类的测试样本数和总的测试样本数的比值;N表示组 合决策树中分类结果的类别为j的决策树的棵树,argmin表示选择中的最小值作 为最终的H的取值。
有益效果:本发明在对信息物理融合系统数据进行分类的时候,使用了数据挖掘中分类 算法的决策树算法,并引入了关于代价敏感的处理以解决信息物理融合系统中数据高效分类, 以及在分类时将产生的损失或代价总和降至最小的问题。具体来说,本发明所述的基于代价 敏感决策树的信息物理融合系统数据分类方法具有如下的有益效果:
(1)决策树易于理解和实现,使用者在学习过程中不需要了解很多的背景知识,只需要 通过解释后,可以理解决策树所表达的意义即刻。
(2)决策树能够直接体现数据的特点,树型结构易于使用者观察和理解。
(3)对于决策树,数据的准备往往是简单,而且能够同时处理离散型数据或者连续型数 据,在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
(4)决策树易于通过测试来对模型进行评测,可以测定模型可信度。如果给定观察的数 据,那么根据所产生的决策树很容易推出相应的分类规则。
(5)引入的代价敏感学习是通过训练数据集,训练出获得最小错误分类代价的诊断学习 系统,最终是为了追求错误分类代价最小化,降低错误分类的可能性。所以它不再是经典的 分类和预测,而是经典分类的扩展。
附图说明
图1决策树建立过程示意图,
图2基于代价敏感决策树的信息物理融合系统数据分类方法流程图。
具体实施方式
本发明使用结合代价敏感的决策树算法,优化信息物理融合系统数据的分类,减少错误 分类带来的损失。下面根据附图和实施例对本发明作更详细的描述。
本发明根据天气样本数据进行具体描述,天气样本数据包括样本号、属性名称和相对应 的属性值、类别。其中属性包括阴晴(对应的属性值有sunny、overcast、rainy)、温度(对应 的属性值有hot、mild、cool)、湿度(对应的属性值有high、normal)、刮风(对应的属性值 有true、false),类别为是否出去游玩(对应的类别有yes、no)。
1、用户将信息物理融合系统的组成单元划分为多个物理单元和一个信息单元。所述物理 单元用于收集天气数据;所述信息单元用于分析和处理数据。
2、用户预先将天气训练样本和天气测试样本放置在系统中。所述天气训练样本和天气测 试样本中的每个样本包括样本号、属性名称、对应的属性值、类别。
3、用户启动每个物理单元收集天气训练样本数据。
4、每个物理单元将收集到的天气训练样本数据发送至信息单元。信息单元对不同物理单 元发送来的天气训练样本数据进行分别存储。
5、信息单元根据分别存储的天气样本数据分别为这些物理单元建立相应的决策树。所述 决策树为机器学习分类算法中的一种树型结构的分类器,其中根结点包含所有的输入样本数 据,叶子结点为分类的结果,其余结点代表对某个属性的测试。分类器是一种计算机程序, 作用是可自动将数据分到已知类别。具体的每个决策树建立过程如下:
5.1、建立一个结点作为决策树的根结点
5.2、判断训练集中是否只有一个类别,若是则将结点标记为叶子结点,并结束决策树的 构造过程;若否则判断样本是否有属性存在。
5.3、若样本没有属性,则将训练集中拥有个数最多的类别标记为叶子结点,并结束构造 过程;若否则开始寻找最好的分裂规则。
5.4、计算信息增益,选取最大的作为分裂属性建立分支,并从样本数据中的删除此属性。 所述信息增益是一种衡量标准,是看属性能够为分类带来多少信息(此处的信息是指对于最 终分类结果的影响),带来的信息越多(影响越大),该属性越重要。其中信息增益的公式为 D是训练集,pi表示训练集中属于类i的非零概率。所述分裂属性 是指选择某个属性作为决策树树型结构分支的条件,如果属性值是离散的,则一般包含这个 属性所有可能属性值个数的分支;如果是连续数值属性,则通常是判断这个数值是否大于或 则小于等于某个事先定义的常量,给出一个二叉分裂。
5.5、对每个分支进行上述d步骤的操作,并且进行b和c步骤的判断。
6、信息单元将得到的决策树放置到一个列表中,组成一个决策树列表。所述列表为数据 结构中按照线性顺序,排列而成的数据项的集合,可以在这种数据结构上进行基本操作包括 对元素的的查找,插入,和删除。
7、信息单元对每个决策树进行测试。具体步骤如下:
7.1、将一组准备好的天气测试样本输入到每个建立好的决策树中;
7.2、天气测试样本经过决策树的决策会得到相应的分类结果;
7.3、将得到的分类结果和天气测试样本本身的类别进行比对,相同则分类正确,不同则 分类错误;记录错误分类的样本数;
7.4、如果错误分类的天气测试样本数和总的天气测试样本数的比值大于10%,则在决策 树列表中删除此决策树;若否,则将其保留在决策树列表中。其中将错误分类的测试样本数 和总的测试样本数的比值记为wi,记录在信息单元中,其中i表示决策树列表里第i个决策 树;
8、判断决策树列表是否为空,若是则选取wi最小的那棵决策树为最终的决策树。
9、如果判断决策树列表不为空,则继续判断决策树列表是否只含有一棵决策树,若是则 这课决策树为最终的决策树。若否,则将决策树列表中的决策树作为组合决策树。所述组合 决策树为多个决策树组成的分类器,每个决策树有相应的权值(此处为错误分类的测试样本 数和总的测试样本数的比值),数据需要综合每个决策树的分类结果方能得到最后的分类。
10、计算组合决策树的错误分类率H,返回H值最小时所对应的类别作为数据的分类结果。 H通过计算获得,其中i表示第i棵决策树;j表示类别;Ci,j表示通过 第i个决策树后得到的分类结果是否为类别j,若是则Ci,j值为1,若否则Ci,j值为0;wi表示 之前测试时第i棵决策树中错误分类的测试样本数和总的测试样本数的比值;N表示组合决 策树中分类结果的类别为j的决策树的棵树;argmin表示选择中的最小值作为最 终的H的取值。
机译: 数据分类方法和数据管理方法,基于该数据分类方法的数据库和数据存储介质
机译: 基于隐私的决策树基于同名式加密数据的推断
机译: 数据挖掘方法和系统,用于基于最小描述长度和记录预排序为数据记录生成决策树分类器