基于属性集等价类划分的数据约简.pdf

《基于属性集等价类划分的数据约简.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2001年6月北京航空航天大学学报June2001第27卷第3期JournaIofBeijingUniversityofAeronauticsandAstronauticsVoI.27No.3基于属性集等价类划分的数据约简张学明施法中（北京航空航天大学机械工程及自动化学院）摘要：由于大型数据库中数据的高维、巨量，使得数据约简在数据库知识发现中起着越来越重要的作用.现有的数据约简方法有3类：穷举选择法、启发式选择法和随机选择法.这些方法效率低，可能丢失重要信息，效果都不理想.属性集等价类划分可以在本质上标识出冗余属性和无关属性，并且可以快速、准确地计算等价类划分个数，使得数据约简更有效

2、，数据挖掘效率更高.关键词：数据约简；数据库；人工智能；等价类划分；数据挖掘中图分类号：TP391文献标识码：A文章编号：1001-596（52001）03-0344-04由于实际大型数据库数据的巨量（记录数可索，测试属性集按其成为候选集的可能性排序，高多达几百万条），高维（每条记录有近一百个属性阶属性优先测试.#随机搜索.在数据约简方面执或称字段），使得在数据库知识发现（KDD，KnowI-行效果都不理想，为此，本文提出基于属性集等价edgeDiscoveryinDataDase，也称数据挖掘）的3个类划分的数据约简法.核心步骤———预处理、数据模式挖掘、后处理［1］中，进行数据约

3、简的预处理过程变得更加重要.它"属性集等价类划分对数据挖掘系统的性能起着非常关键的作用.下面在等价类的定义基础上，引入冗余属性和全值属性的概念，并给出它们的性质和作用.!属性选择与数据约简定义!两行:和U相对于属性集X是等价数据约简包括：删除列（属性），即属性选择；的，如果［:A］=U［A］，任意A!X.任意属性集X把表关系的行划分成等价类［5］，记行:!r相对于删除行，合并类似的记录；减少列中值的个数，包括连续属性离散化.属性选择同时也删除了行，本属性集X"R（R为数据库的关系模式，r为基于文着重讨论数据约简中的属性选择.R的表）的等价类为［:］X，即［:］X=｛U!r［:A］在

4、KDD的分类问题中，数据库表的属性可分=U［A］，任意A!X｝.等价类的集合!X=｛［:］X为条件属性和决策属性［2］~［4］.属性选择是指全:!r｝是r在X下的一个划分，即!X是行的不相部条件属性集中选择一个较好的、有代表性的子交集合（等价类）的集合.记!X为!X的等价类集，一致性地描述表中的数据.实际运用中，数据个数.记录的属性个数可能非常多，而元组的类别只依例1数据库的关系见表1，属性集为｛A，赖少数属性.此时，如果把具有全部属性的原始数表!数据关系表据记录输入到分类器中，将生成无必要复杂的规RowIDABCD则.而属性选择可以减低获取规则的时间（如在神11aThisfI

5、ower21aThattree经网络学习、决策树学习中，少的属性将导致少的32aThishiII接点，从而降低计算复杂性），使得生成的规则更42aThisfIower简洁、有更高的分类准确率［5］.52DThatroad63DThissky属性选择有3种选择（搜索）属性方法：!穷73cThatfIower举搜索，测试从一个属性开始，接着组合两个属83cOtherrose性，直至找到通过冲突分析的属性集."启发式搜收稿日期：2000-01-20作者简介：张学明（1966-），男，安徽绩溪人，博士生，100083，北京.第3期张学明等：基于属性集等价类划分的数据约简345B，C，D｝，R

6、owID为记录号.相对A的整个分类I!｛A，i｝I=I.为!｛A｝=｛｛1，2｝，｛3，4，5｝，｛6，7，8｝｝，相对｛B，C｝必要性.由定义3知，任一i，对应m个相异的划分为!｛B，C｝=｛｛1｝，｛2｝，｛3，4｝，｛5｝，｛6｝，的Ai，从而｛A，i｝共有I·m个不同的组合，即｛7｝，｛8｝｝.｛A，i｝取I·m个相异值，从而I=I·m，故显然，下面的定理1成立.I!｛A｝I·I!｛i｝I=I!｛A，i｝I成立.定理!设有属性集X和Y，如果XY，则充分性.假设I=I·m，但属性A相对决策属I!XII!YI.性i不为全值属性，则依定义3，至少存在属性i定义"称属性A相对于条件属

7、性集X是冗的一个取值i，属性A的某个取值Ai，没有对应的余的，对数据库表r的任意两元组（也称记录）U元组存在.不妨设属性i的其它（I-1）个取值，和1：如果xX，U［x］=［1x］，则有U［A］=满足：i取一个值，A可取m个相异值，从而｛A，［1A］.i｝不取值（Ai，i），｛A，i｝相异取值数为（I-1）·由定义1和定义2，可以得出定理2.m+（m-1）=I·m-1，故I!｛A，i｝I=I·m-1，即定理"属性A相对于条件属性集X是冗余I=I·m-1，矛