大数据

当前位置:首页 > 大数据

《数据挖掘导论》第四章 续3

4.6 基于关联的分类方法

关联规则挖掘是当前数据挖掘中一个重要而又活跃的研究领域。本书的第五章将要详细介绍几种主要的关联规则挖掘算法。近年来,已开始将关联挖掘方法应用到分类方法中,以获得新的数据挖掘技术。本节将要介绍基于关联的分类方法。

QQ截图20220413153507.jpg

-4.12  网络规则抽取过程示描述

一种基于关联的分类方法,称为关联分类(association classification)。它主要包括两大处理步骤:第一步利用标准关联规则挖掘算法(如:Apriori 修改版本)挖掘出有关的关联规则;第二步就是基于所挖掘出的关联规则构造一个分类器。

设 D 为训练数据集,Y 为 D 中所有的类别集合。算法将符号属性映射为连续正整数,同样连续属性被离散化并作类似映射。D 中的每个数据样本是用一组属性-值对(称为项)和一个类别 y 来表示的。设 I 为 D 中所有属性-值对(项) 集合。一个关联分类规则(简称 CAR )具有“ condset ⇒ y ”形式;其中 condset 为一组项,即有 condset ⊆ I 和 y ∈Y ,因此这类规则可以通过“< condset,y >” 形式来加以描述(简称规则项集)。

一条 CAR 规则也具有信任度c ,它表示 D 中有 c% 的样本包含属于类别 y 的 condset 。一个 CAR 规则还具有支持度 s ,它表示 D 中有 s% 的样本包含 condset 且属于类别 y 。一个 condset 的支持度为 D 中包含 condset 的样本数(记为 condsupCount )。一个规则的支持度为 D 中包含 condset 且属于类别 y 的样本数 (记为rulesupCount)。满足最小支持度的规则项集称为频繁规则项集。若一组规则项目集具有相同的condset,那么选择其中具有最大信任度的规则作为可能规则(possible rule, 简称PR)来表示这一组规则项集。满足最小信任度的规则称为准确的。

关联分类规则挖掘方法的第一步就是发现所有的频繁和准确的可能规则 (PR),它们是类别关联规则(简称CARs)。若一个规则项目集中的 condset 包含 k 个项目,就称这一规则项目集为 k-ruleitems 。算法利用与 Apriori 算法类似的循环过程,只是用规则项集替换了其中的项。算法扫描数据库,搜索 k-ruleitems , 对于 k = 1,2,...。直到所有频繁 k-ruleitems 均被发现出来。对每一个 k值也需要进行一次数据库扫描,利用 k-ruleitems 产生(k+1)-ruleitems。在第一遍扫描数据库后,获得 1-ruleitems 的支持度;之后就是候选 2-ruleitems (C2)。有关频繁规则项集性质的知识可以用来帮助消减候选规则项目集(小于支持度),这一知识就是:所有频繁规则项目集的子集也应是频繁规则项目集。再次扫描数据库,以确定每个候选规则项目集是否为频繁  2-ruleitems (F2)。不断重复这一过程,即利用频繁项集 Fi来产生候选项集Ci+1,直到不再发现新的频繁项集为止。满足最小信任度的频繁规则项集就构成了类别关联规则集合(CARs)。

关联分类规则挖掘第二步就是对所获得的 CARs 进行处理以便构造一个分类器。由于为获得最准确的规则集而要对所有规则子集进行检查,这样所要处理的规则数目极为庞大。因此这里采用了一个启发知识。首先定义一个规则优先概 念,即规则 ri 比规则 rj 优先,记为:QQ截图20220413155926.jpg。条件是:(1) ri  的信任度大于 rj 的 信任度;或(2)两规则信任度相同,但  ri  的支持度更大;或(3)  ri  和 rj 的信任度和支持度都相同,但 ri  产生的比 rj 早。算法通常选择一组能覆盖 D 中样本且具有高优先值的规则(CARs)。算法需要扫描数据库一遍以上以便确定最后的分类器。分类器对所选的规则按优先值从高到低排列。当进行分类时,先使用优先值大且满足条件的规则进行分类。此外分类器还包含一个缺省规则(具有最低优先值),当其它规则都不满足时,利用这一缺省规则对数据对象进行分类。

通常,以上介绍关联分类方法对一些数据集的测试结果,要比 C4.5 算法更准确;且(算法)上述两个步骤都具有线性可扩展性。

基于聚类的关联规则挖掘也可应用到分类问题上。关联规则聚类(简称 ARCS )可以挖掘具有“ Aquan1 ∧ Aquan2 ⇒ Acat ”的关联规则。其中 Aquan1 和 Aquan2 是对定量属性范围的测试(这里的范围是动态决定的); Acat 根据训练样本将一个类别(值)赋给一个符号属性。

还可以将关联规则用一个二维方格表示出来。算法扫描整个方格集合,寻找长方形规则聚类。在一个规则聚类中的相邻范围的定量属性将被合并。由 ARCS 所获得的聚类关联规则也可应用于分类问题。ARCS 的预测准确率与所使用的离散化方法有关。在可扩展性方面,ARCS 需要一块确定大小的内存,但与数据库大小无关。与 ARCS 相比,C4.5 的运算时间呈指数增长,而需要的存储空间为 数据库大小的若干倍(且需要整个放入内存中)。因此关联规则挖掘是产生准确和具有可扩展性分类器的一个重要策略。


4.7 其他分类方法

将要要介绍一其它的分类方法。这其中包括:k 最近邻分类、基于示例理、遗传算法、粗糙集和模集合方法。一,这些方法在商用数据挖掘系统中用的所介绍的方法小许多。例如k 最近邻分类方法,需要存所有的训练样本,这在处理大规模数据集时就会出现问题。而其它象基于示例理、遗传算法和粗糙集等用于分类的方法,型研究阶段这些方法受到多的重


4.7.1 k-最近邻方法

k最近邻分类器是基于类学习的分类方法。训练样本是个数值属性所描述。每个n 维空中的一个,这所有的就被n 维空中。当给定一个未知(类别)数据对象,一个 k- 最近邻分类器n 维空并从k 个与未知数据对象最为近的训练样本,这 k 训练样是未知数据对象的k个最近邻。所最近n 维空中两之间欧氏离, n 维空中两点X={x1,x2,...,xn}Y={y1,y2,...,yn}之间欧氏是:

QQ截图20220413162319.jpg

未知类别的数据对象就被归属于这k个最近邻中出现数最多的类别。而当 k=1 ,未知类别的数据对象就被归属于最近它的一个训练样本所具有的类别。

最近邻分类器是基于实例学习或懒惰学习(lazy learning)方法,为它实际并有(据所给训练样本)构造一个分类器,而是将所有训练样首先来,要进行分类进行计算处理。与积极学习方法,如决策树归纳方法和神经网络方法相比后者在进行分类前已构造一个分类模型;懒惰学习方法,在当训练样本数目速增加时就会导最近邻的计算速增懒惰学习方法需要有索引方法支学习而懒惰学习方法积极学习方法要懒惰学习方法在进行分类,需要进行大的计算,它要积极学习方法许多。此外与决策树归纳方法和神经网络方法不同是,最近邻分类器认为每个属性的作用都是相同的(赋予相同值),这在属性集包含有许多不相关属性就会误导分类学习过程。

最近邻分类器也可以用于预测,也是可以回一个实数值作为一个未知数据对象的预测值。这时就可以取这k个最近邻出实数值(作为类别值) 值作为出。


4.7.2 基于示例推理

基于示例理(case_ based resoning, 简称CBR)分类器,不同于最近邻分类器,后者训练样本存为欧氏中的;而 CBR 所存的示例常常涉符号描述。CBR 在商业上有许多用,如:客中的问题,或与故障诊断问题等。此外 CBR 还可用于程、法等领域,在这些领域中示例通都是技术设计方或法律案等。

当给定一个未知示例需要分类,一个基于示例的理器将首先一个相同训练样本存在,,则训练样本中所包含的决方法;相同训练样本存在,寻找示例的组成相似之处的训练样本,意义,这些训练样本也是(示例的)最近邻。如示例可以用图来示的那么就涉到相似子图的。基于示例的理器将图对最近邻的若干解方法进行合出一个(示例)决方法。各示例回方法容, 必须溯搜其它的决方法。基于示例的理器可以利用背景知识和问题来帮助获得一个可行的决方法。

基于示例理分类方法中所存在的问题包括:寻找相似度方法(如)、开发快速索引技术和求方法的合等。


4.7.3 遗传运算

遗传算法借鉴的基本。遗传算法学习过程

1建一个初生物,其中包含生的规则集。每规则可以用bits)来示。一个简单,一个给定训练样本可以用两个A1 A2 ,以及两个类别 C1 和 C2 来描述。那么规则IF A1 and not  A2 THEN C2可以示为100”位;其中左边分别示属性 A1 A2 ,最右边示类别。类似地,规则IF not A1 and not A2,THEN C1示为001一个属性具有 k 不同取值(k > 2 ),那么就可以使k 示(编码属性的值,同样也可以类似地进行编码。 

2)基于生存的则,前生物的生物,其中包含了的规则集;这些规则一分来来的规则,分则是生的规则 又称规则的)。规则的合fitness)是通过对一组训练样本的分类准确确定的。

3)生物则是通过利用遗传操作,如:crossover)、变异 mutation)。在操作中,来一对规则的编码进行以形成新的一对规则。而在变异操作中,选择一个规则的编码进行求而得一个规则。

4)基于前生物(规则集)来不断生物(规则),生物群 P阶段P 中的每个规则均满足的一个值。

遗传算法实现算,也可以用于分类等化问题的求。在数据挖掘中,它也可用于对其它算法的应度进行评估。

相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~