基于线性相关思想的属性约简算法.pdfVIP

第 25卷 第 4期 广西师范大学学报 ：自然科学版 VO1．25 No．4 2007年 12月 JournalofGuangxiNormalUniversity：NaturalScienceEdition Dec．2007 基于线性相关思想的属性约简算法 周 涛 (陕西理工学院数学系，陕西 汉中723000) 摘 要：通过对粗糙集中属性约简理论的研究，定义了等价类矩阵、等价类的线性表示、划分的线性相关、空划 分等概念，给出了等价类矩阵构造算法并讨论了其性质，最后给出了基于线性相关思想的属性约简算法。 关键词：粗糙集；属性约简；等价类矩阵；划分的线性相关 中图分类号：TP318 文献标识码：A 文章编号：1001—6600(2007)04—0044—04 属性集的约简n剀(attributereduct)是粗集理论口 ]中关键的问题之一。其主要思想是在保持分类能 力不变的前提下，通过属性约简，导出问题的决策或分类规则。所谓约简是属性集的子集，它与原属性集具 有同样的分辨能力。约简反映了一个信息系统的本质信息，求解一个信息系统的全部约简或计算出最佳约 简都是NP一难题。这里定义等价类矩阵、等价类的线性表示、划分的线性相关、空划分等概念，讨论了属性 等价类矩阵的性质，给出了等价类矩阵构造算法的基础上，最后给出一种新的基于线性相关思想的属性约 简新算法，这对约简算法无疑有十分重要的意义。 1 粗糙集属性约简理论 粗糙集理论[3 中的知识表达方式一般采用信息表或称为信息系统的形式，它可以表示为四元有序 组K一(，A，V，D』)，其中： 是对象的全体，即论域；A是属性全体；V=UV，V 是属性的值域；D』：U×A — 是一个信息函数， ：— ，,95∈U，反映了对象,95在 中的完全信息，其中 ()一，9(，)。有时属性 集 还分为条件属性C和决策(结论)属性D，这时的信息系统称为决策表 ，常记为( ，CUD，V，D』)。无决 策的数据分析和有决策的数据分析是粗糙集理论在数据分析中的两个主要应用。粗糙集理论给出了对知 识 (或数据)的约简和求核的方法，从而提供了从信息系统中分析多余属性的能力。 一 个知识库可定义为一个关系系统 K一(，A)，其中 ≠ 称为全域 (universe)，是所有要讨论的个 体集合， 是 上的等价关系集(叫做 的知识)，r∈A。U／r表示全体域 根据r所得的等价类划分，令 U／r一{ ，。，。，…， )，其中 是等价类(叫做概念或范畴)，≠ ，n ，一 并且U 一U(≠ ，i，J 一 1，…，)。 ](∈ )表示含有个体 的r等价类，即： ]一{Y∈U： rY)。设P R，且P≠ ，则P 中所有等价关系对应的等价类交集就是P上的一种不可区分关系，记作 IND(P)。实际上，IND(P)就是 根据P所作的等价类划分。 定义 1[7 设P是等价关系集，关系r∈P，若 IND(P)一IND(P一{r))，则称r在P中是可省的，否 则就是不可省的。 定义2[7 若P中每个关系都是不可省的，则称P是独立的，否则就是依赖的或非独立的。 定义 3[7 若 Q(Q P)足独立的，且 IND(Q)一IND(P)，则称 Q是 P的一个约简(reduct)，记作 Q —red(P)。 定义 4[7叫 在等价关系集 P中所有不可省的关系集合称为P的核(core)，记作core(P)。不难看出， P有多个约简，且core(P)一nred(P)，其中red(P)是所有 P约简的族集。 定义5 当关系系统K一((，T，R)的约简不唯一时，把保留等价关系个数最少的约简叫做最小约简。 收稿 日期 ：200705—30 基金项 目：国家 自然科学基金资助项 目；陕西理工学院科研基金资助项 目(SLG0631) 通讯联系人：周涛(1977一)，男(回族)，宁夏同心人，陕西理工学院讲师，博士研究生。E—mail：zhoutl23@gamit．tom 第 4期 周 涛：基于线性相关思想的属性约简算法 通常所求得的约简都不是最小约简，因为至今为止，还没有找到一