维普资讯 http://www.cqvip.com 第２８卷第２期 ２００８年２月 文章编号：１００１—９０８１（２００８）０２—０５２５—０３ 一计算机应用 Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ Ｖｏ１．２８ Ｎｏ．２ Ｆｅｂ．２０ｏ８ 种新的不一致决策表属性约简算法 汪小燕，杨思春 （安徽工业大学计算机学院，安徽马鞍山２４３００２） （ｗｘｙ￣ｘ＠ａｈｕｔ．ｅｄｕ．ｃｎ） 摘要：针对目前求核方法存在的问题，提出一种基于分布函数的用于计算核属性的改进的二进制可辨矩阵。 改进的二进制可辨矩阵不仅规模小，而且适用于任何决策表求核。在获取核属性的基础上，提出一种新的不一致决 策表的属性约简算法，只要在用于计算核属性的改进的二进制可辨矩阵中简单增加相应的行，就可以利用逻辑运算 来获取属性约简。并将吸收律应用于属性约简，较大提高了属性约简的效率。 关键词：粗糙集；不一致决策表；二进制可辨矩阵；核；属性约简 中图分类号：ＴＰ３０１ 文献标志码：Ａ Ｎｅｗ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｉｎ ｉｎｃｏｎｓｉｓｔｅｎｔ ｄｅｃｉｓｉｏｎ ｔａｂｌｅｓ ＷＡＮＧ Ｘｉａｏ—ｙａｎ．ＹＡＮＧ Ｓｉ—ｃｈｕｎ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ａｎｈｕｉ Ｕｎｉｖｅｍｉ￣ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｍａ ａｎｓｈａｎ Ａｎｈｕｉ ２４３００２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｃｏｒｒｅｃｔ ｓｏｍｅ ｐｒｏｂｌｅｍｓ ｏｆ ｃｏｍｐｕｔｉｎｇ ｔｈｅ ｃｏｒｅ ｏｆ ａ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ，ａｎ ｉｍｐｒｏｖｅｄ ｂｉｎａｒｙ ｄｉｓｃｅｒｎａｂｌｅ ｍａｔｉｘ ｄｅｆｒｉｎｉｔｉｏｎ ｂａｓｅｄ ｏｎ ｄｉｓｔｉｂｕｔｉｒｏｎ ｆｕｎｃｔｉｏｎ ｆｏｒ ｃｏｍｐｕｔｉｎｇ ｔｈｅ ｃｏｒｅ ｗａｓ ｐｕｔ ｆｏｒｗａｒｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｔｈｅ ｉｍｐｒｏｖｅｄ ｂｉｎａｒｙ ｄｉｓｃｅｒｎａｂｌｅ ｍａｔｉｘ ｉｒｓ ｎｏｔ ｏｎｌｙ ｓｍａｌｌ ｉｎ ｓｃａｌｅ ｂｕｔ ａｌｓｏ ｓｕｉｔａｂｌｅ ｆｏｒ ａｎｙ ｄｅｃｉｓｉｏｎ ｔｂｌａｅｓ ｆｏｒ ｃｏｍｐｕｔｉｎｇ ｔｈｅ ｃｏｒｅ．Ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｏｒ ａｔｆｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｉｎ ｉｎｃｏｎｓｉｓｔｅｎｔ ｄｅｃｉｓｉｏｎ ｔｂｌａｅｓ ｗａｓ ａｌｓｏ ｐｒｅｓｅｎｔｅｄ ｂａｓｅｄ ｏｎ ｇｅｔｔｉｎｇ ｔｈｅ ｃｏｒｅ．Ｏｎｌｙ ｉｎｃｒｅａｓｉｎｇ ａｐｐｒｏｐｒｉａｔｅ ｒｏｗｓ ｉｎ ｔｈｅ ｉｍｐｒｏｖｅｄ ｂｉｎａｒｙ ｄｉｓｃｅｒｎａｂｌｅ ｍａｔｒｉｘ ｆｏｒ ｃｏｍｐｕｔｉｎｇ ｔｈｅ ｃｏｒｅ，ａｔｔｒｉｂｕｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ｗｉｌｌ ｂｅ ｏｂｔａｉｎｅｄ ｂｙ ｕｔｉｌｉｚｉｎｇ ｌｏｇｉｃ ｏｐｅｒａｔｉｏｎ．Ａｎｄ ｔｈｅ ａｂｓｏｒｐｔｉｖｅ ｌａｗ Ｗａｓ ｕｓｅｄ ｉｎ ａｔｔｒｉｂｕｔｉｏｎ ｒｅｄｕｃｔｉｏｎ，ｗｈｉｃｈ ｒａｉｓｅｄ ｔｈｅ ｅｆｉｃｉｆｅｎｃｙ ｏｆ ａｔｔｉｂｕｔｅ ｒｅｄｕｃｔｉｒｏｎ ｇｒｅａｔｌｙ． Ｋｅｙ ｗｏｒｄｓ：ｒｏｕｇｈ ｓｅｔ；ｉｎｃｏｎｓｉｓｔｅｎｔ ｄｅｃｉｓｉｏｎ ｔａｂｌｅｓ；ｂｉｎａｒｙ ｄｉｓｃｅｒｎａｂｌｅ ｍａｔｒｉｘ；ｃｏｒｅ；ａｔｔｉｒｂｕｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ０ 引言 粗糙集理论是由文献［１］提出的处理不确定、不精确和 不完全数据的一种新的数学工具，主要用于知识的简化及知 识依赖性的分析。粗糙集的主要思想是，在保持信息系统分 类能力不变的前提下，通过属性约简，导出问题的决策或分类 规则。属性约简是粗糙集挖掘知识的核心内容之一，它通过 对决策表进行压缩，以最少的条件属性来表达原决策表的全 部信息。在属性约简算法中，搜索一个属性约简集通常是从 核开始的。因此，求核运算成了属性约简的关键步骤。文献 是一个信息函数，它指定Ｕ中每一个对象 的属性值。 ｒ（ ）是对象 在属性ｒ上的值，Ｄ（ ）是记录 在Ｄ上的值。 定义２ 令Ｓ＝（Ｕ，Ｒ＝Ｃ ｕ Ｄ，ｖＪ）是一个信息系统， — ［２—４］对核属性的计算都进行了专门的研究。但存在的不 足要么是求核属性的算法只适合一致性决策表，要么是算法 的时间和空间复杂度不理想。本文结合分布函数的定义，提 出一种改进的二进制可辨矩阵及其核属性计算方法，该矩阵 不仅规模小，而且实现简单，适用于任何决策表（一致与不一 致决策表）求核。改进的二进制可辨矩阵不能直接用于属性 约简，本文在获取核属性的基础上，提出一种新的不一致决策 表的属性约简算法，只要在改进的二进制可辨矩阵中简单增 加相应的行，就可以利用逻辑运算来获取属性约简。为简化 对任意Ｐ Ｃ或Ｐ Ｄ，关于属性子集Ｐ的二元关系 称为 不可分辨关系，定义： Ｒ ＝｛（ 。， ，） ，Ｐ）＝，（ ，，Ｐ），Ｖｐ∈Ｐ｝。 不可分辨关系 是Ｕ上的等价关系，它构成对Ｕ的划分 ｉ己为：Ｕ／ＲＰ＝｛［ ］Ｐ Ｉ ∈Ｕ｝。 定义３ 令Ｓ＝（Ｕ，Ｒ：Ｃ ｕ Ｄ，ｖＪ）是一个信息系统， 对任意口∈Ｃ，若ＰＯＳｃ Ｉ（Ｄ）＝ＰＯＳｃ（Ｄ），称口在Ｃ中是不 必要的，否则。在Ｃ中是必要的。Ｃ的所有必要属性组成的集 合称为Ｃ的核，记为ＣＯＲＥ（Ｃ）。 定义４ 令Ｓ：（Ｕ，Ｒ＝Ｃ ｕ Ｄ，ｖＪ）是一个信息系统， 若 。，则称决策表是一致的，否则称决策表是不一致 的。 逻辑运算，提高属性约简的效率，新算法将命题演算中的吸收 律应用于消除冗余的析取式，最后通过实例验证了该算法。 定义５ 令Ｓ＝（Ｕ，Ｒ＝Ｃ ｕ Ｄ，ｖＪ）是一个信息系 统， Ｃ，Ｕ／Ｒ。＝｛Ｄ ，Ｄ：，…，Ｄ ｝，分布函数 （ ）＝ ｛Ｄ（ＤＩ／ ］／［ ），Ｄ（Ｄ：／［ ］ ），…，Ｄ（Ｄ ／ ］ ）， ∈Ｕ｝ 其中Ｄ（Ｄ ／ ］ ）＝Ｉ Ｄ。ｎ［ ］ ｆ／ｌ［ ］ Ｉ，显然 （ ） 是Ｕ／Ｒ。上的概率分布。 定理１｜６ 对属性ｏ∈Ｃ，ｏ是不可缺少的，当且仅当存在 ∈ｃ （ｉ∈［１，ｋ］）时，使得下列条件之一成立： １）存在 ∈［１，ｋ］且 ≠ｉ，使得［ ］ｃ＿】口｝ｎ ≠ ； ２）［ ］Ｃ－｛ａｌ ｎ（Ｕ— ）≠ 。 １ 相关理论 定义１ 令Ｓ＝（Ｕ，Ｒ， ）是一个信息系统，Ｕ为论域 且Ｕ＝｛ ， ：，…， ｝，Ｒ＝Ｃ ｕ Ｄ是属性集合，子集Ｃ和Ｄ 分别是条件属性集和决策属性集，Ｖ＝ｕ Ｖｒ是属性值的集 ２ 改进的二进制可辨矩阵及求核方法 定义６决策表 相应的二进制可辨矩阵Ｍ 构造如下： 合， 表示属性ｒ∈Ｒ的属性值范围，即属性ｒ的值域ｆ：Ｕ× 收稿日期：２００７—０９—０３；修回日期：２００７—１２—０６。 基金项目：安徽省教育厅自然科学基金资助项目（ＫＪ２００７Ｂ２４５）。 作者简介：汪小燕（１９７４一），女，安徽桐城人，讲师，硕士，主要研究方向：数据挖掘，粗糙集理论；杨思春（１９７０一），安徽六安人，男，副教 授，主要研究方向：自然语言处理、自动问答和信息检索、数据挖掘。 维普资讯 http://www.cqvip.com ５２６ 计算机应用 第２８卷 矩阵Ｍ 的每一列对应一个条件属性，共有ｍ列（ｍ为条件属 Ｄ ，Ａ １，Ａ， １，因此ｍ （（ｉ， ）， ）：１。若条件（２）成 性韵个数）。每一行对应论域中的一个对象对（ ， ，），且 立，则存在Ａ ，使得任意ｎ∈Ｃ一｛ｃ ｝，有 （Ａ ，ｎ）＝ ｄ（ ）≠ｄ（ ，），Ｍ 至多有ｎ（ｎ一１）／２行（ｎ为决策表中实例 （Ａ ，口）且 （Ａ ，ｃ ）≠ （Ａ ，ｃ ），由于Ａ Ｄ ，Ａ 为不一致 个数），矩阵元素为： 当 ，ｃ ）≠ ，，ｃ ）时， 对象类，故（Ａ ，）∈Ｄ ，其中Ａ １，Ａ ，因此 ｍ（（ｉ， ）， ）＝１，否则，ｍ（（ｉ，Ｊ）， ）＝０。 文献［７］中提出利用定义６中的二进制可辨矩阵来计算 ｍＩ＊（（ｉ，Ｊ）， ）＝１。所以ＣＯＲＥ（Ｃ） ＳＭ（Ｃ）。 故ＳＭ（Ｃ）＝ＣＯＲＥ（Ｃ）得证。 核的方法。但是，由于存在不一致对象的比较会导致核属性计 实例１ 表１为某一决策表，其中条件属性集Ｃ＝｛ｃ．， 算的错误。为了能改进定义６中的二进制可辨矩阵对计算不 ｃ ，ｃ ｝，决策属性集Ｄ＝｛ｄｆ。 一致决策表的核属性的不足，同时又能比定义６中的二进制 可辨矩阵的规模小，本文提出一种新的用于求核的改进的二 表１决策表 进制可辨矩阵Ｍ 。 定义７ 令Ｓ＝（Ｕ，Ｒ＝Ｃ ｕ Ｄ，ｖ，ｆ）是一个信息系统， Ｕ／Ｒｃ＝｛Ａｌ，Ａ２，…，Ａ ｝，Ｕ／Ｒ。＝｛Ｄ ，Ｄ２，…，Ｄ ｝，记Ｄ ＝ ｛［ ］ ，［ｙ］ ：ＩＸ （ ）≠ （ｙ）｝，用 （Ａ ）表示属性ｃ 关于Ａ 的取值。定义二进制可辨矩阵Ｍ ＝｛ｍ （（ｉ， ）， ）｝为：矩 阵Ｍ 的每一列对应一个条件属性，每一行对应条件属性等 价类的一个对象对（Ａ ，Ａ，），矩阵中元素取值表示如下： Ｍ１＂（（ｉ， ）， ）＝ ｒ１， （Ａ ）≠ （Ａ，），（Ａ ，Ａｊ）∈Ｄ ， ｌ Ａ Ｕ１，Ａｊ Ｕ１或Ａ， Ｉ２２ １ ０， （Ａ ）＝ （Ａ，），（Ａ ，Ａ，）∈Ｄ ， Ｌ Ａ １，Ａ． １或Ａ， 其中：Ｕ１＝Ｕ ，／７２＝Ｕ—ＵＩ。 ｉ＝１ ㈤麓 性质１ 令Ｓ＝（Ｕ，Ｒ＝Ｃ ｔＪ Ｄ，ｖ，ｆ）是一个信息系统， Ｕ／Ｒｃ＝｛Ａｌ，Ａ２，…，Ａ ｝，Ｕ／Ｒ。＝｛Ｄｌ，Ｄ２，…，Ｄ ｝，记Ｄ ＝ ３ 新的属性约简算法 ｛［ ］ ，［ｙ］ ： （ ）≠ （ｙ）｝，若Ａ １，Ａ， Ｕ１（ｉ≠ ） 且Ａ 和Ａ，属于不同的决策类，则（Ａ ，Ａ ）∈Ｄ ；若Ａ １， 定义７所定义的二进制可辨矩阵肘 ，不包含对象对（Ａ ， Ａ， Ｕ２（ｉ≠ ），则（Ａ ，Ａｊ）∈Ｄ 。 Ａ，）（（Ａ ，Ａ，）∈Ｄ 且Ａ ，Ａ （ｉ≠ ））所在的行， 证明 由分布函数的定义可证。 所以一般用于决策表计算核属性，不能直接用于决策表属性 实际上，利用定义７建立二进制可辨矩阵时，不需要计算 约简。故提出另外一种改进的二进制可辨矩阵Ｍ ，使得该矩 每个实例对象的分布函数，根据性质１就可以判断：（Ａ ，Ａ ） 阵能用于不一致决策表属性约简。 ∈Ｄ 是否成立，这样可有效降低改进的二进制可辨矩阵的 定义８ 令Ｓ＝（Ｕ，Ｒ＝Ｃ Ｕ Ｄ，ｖ，ｆ）是一个信息系统， 计算复杂度。 Ｕ／Ｒ ＝｛Ａｌ，Ａ２，…，Ａ ｝，Ｕ／Ｒ。＝｛Ｄｌ，Ｄ２，…，Ｄ ｝，记Ｄ’＝ 定理２ 令Ｓ＝（Ｕ，Ｒ＝Ｃ Ｕ Ｄ， ）是一个信息系统， ｛［ ］ ，［ｙ］ ：ＩＸ （ ）≠ （ｙ）ｆ，用 （Ａ ）表示属性ｃ 关于Ａ 对于其改进的二进制可辨矩阵Ｍ ，若某一行中只有一个元 的取值。定义二进制可辨矩阵Ｍ ＝｛ｍ２ （（ｉ， ）， ）｝为：矩 素为１，其他为０，则称元素１所在列对应的条件属性为特征属 阵Ｍ 的每一列对应一个条件属性，每一行对应条件属性等 性。若记ＳＭ（Ｃ）＝｛所有特征属性的集合｝，则有ＳＭ（Ｃ）＝ 价类的一个对象对（Ａ ，Ａ，），矩阵中元素取值表示如下： ＣＯＲＥ（Ｃ）。 。，，． 、，、 ｆ１， （Ａ ）≠ （Ａ，） （Ａ ，Ａ，）∈Ｄ 证明 设Ｕ／Ｒ。：｛Ｄｌ，Ｄ２，…，Ｄ ｝，Ｕ／Ｒｃ：｛Ａｌ，Ａ２，…， 。 。Ｌ０， （Ａ ）＝ （Ａｊ），（Ａ。，Ａｊ）∈Ｄ Ａ ｝。若任意ｃ ∈ＳＭ（Ｃ），则存在ｍｌ＊（（ｉ， ）， ）＝１，即对任 实际上，当决策表为一致时，利用定义８所建立的二进制 意口∈Ｃ一｛ｃ ｝，有 （Ａ ，口）＝ （Ａｊ，口）。 ∈Ａ ， ∈Ａ ，由 可辨矩阵等价于文献［２］提出的二进制可辨矩阵。 定义７知：Ａ １，设 ∈ｃｏ （Ｐ∈［１， ］）， ∈［ ］ｃ， 隹 性质２ 在二进制可辨矩阵Ｍ 中增加对象对（Ａ ， ［ ］ｃ，但 ，∈［ ］ｃ＿Ｉｃ ｝。若 ，∈Ｕ１，由（Ａ ，Ａ，）∈Ｄ 知： Ａ ）（（Ａ ，Ａ，）∈Ｄ 且Ａ ，Ａ， ／Ｊ２（ｉ≠ ））所在的行，所 ，Ｄ）≠ ，，Ｄ），存在ｑ［１， ］且ｑ≠Ｐ，使得 ∈ｃｏ ，则 ［ ］ …ｎ ｃＤ。≠ 成立，由定理１知，ｃ 是不可缺少的，即 得到的矩阵等价于 。 ｃ ∈ＣＯＲＥ（Ｃ）。若 ，∈ ，则［ ｃ ｝ｎ ≠ 成立，由定 证明 由定义７和定义８可证。 理１知，ｃ 是不可缺少的，即ｃ ∈ＣＯＲＥ（Ｃ），则ＳＭ（Ｃ） 根据性质２，在对不一致决策表进行属性约简时，不需要 ＣＯＲＥ（Ｃ）。 按照定义８重新建立二进制可辨矩阵Ｊｌｊｆ ，只要在用于求核的 若任意ｃ ∈ＣＯＲＥ（Ｃ），由定理１知：存在 ∈ｃ二进制可辨矩阵Ｍ 中增加相应的行就可以了。 ｏ （ｉ∈ ［１，七］）使得下列条件之一成立： 性质３ 当决策表中只有一个不一致等价类或者所有不 一１）存在 ∈［１， ］且 ≠ｉ，使得［ ］ ＿】Ⅱ｝ｎ Ｄ，≠ ； 致等价类中对象的分布函数都相等，则根据二进制可辨矩 阵Ｍ 计算出的属性约简就是该决策表的属性约简。 ２）［ ］Ｃ－ｌ ａｌ ｎ（Ｕ— ）≠ 。 证明 当决策表中只有一个不一致等价类或者所有不 若条件１成立，则存在Ａ。 Ｄｉ，Ａ Ｄ，，使得任意ｎ∈ 一致等价类中对象的分布函数都相等时，二进制可辨矩阵 Ｃ一｛ｃ ｝，有 （Ａ ，ｎ）＝ （Ａ ，ｎ）且 （Ａ ，ｃ ）≠ （ ，ｃ ）， Ｍ 和Ｍ 是等价的，根据Ｍ 计算出的属性约简就是该决策 由于 Ｄ ，Ａ， Ｄ，，故 （Ａ ，Ｄ）≠ （Ａ，，Ｄ），则（ ，Ａ，）∈ 表的属性约简。 维普资讯 http://www.cqvip.com 第２期 汪小燕等：一种新的不一致决策表属性约简算法 ５２７ 用于不一致决策表属性约简的新算法思想如下：利用二 进制可辨矩阵Ｍ＝：ｌ计算出核属性，再在矩阵Ｍ＝：ｌ中增加对象 对（Ａ ，Ａ，）（（Ａ。，Ａｉ）∈Ｄ 且Ａｌ ，Ａ ／５２（ｉ≠ ））所在 的行对应－＇Ｃ．Ｖ ｃ３，ｃ．包含于ｃ．Ｖ ｃ３中，故删除ｃ Ｖ ｃ３，则该 决策表的属性约简为｛Ｃ ，Ｃ：｝。 的行形成矩阵Ｍ 。最后利用矩阵Ｍ 进行属性约简。 算法步骤描述如下： １）为决策表建立二进制可辨矩阵Ｍ ，计算出核属性。 ２）在矩阵Ｍ 中增加对象对（Ａ。，Ａｉ）（（Ａ。，Ａｊ）∈Ｄ 且 ４ 结语 针对目前大量存在的不一致决策表，结合分布函数的定 义，提出一种用于求核的改进的二进制可辨矩阵，该矩阵不仅 规模小，而且实现简单，适用于任何决策表求核。并通过理论 和实例证明了求核方法的正确性。用于求核的改进的二进制 可辨矩阵不能直接应用于属性约简，本文在该矩阵的基础上， 通过增加分布函数不相等的不一致对象类所对应的行形成新 的矩阵，利用新矩阵，在获取核属性的基础上，提出一种新的 Ａ ，Ａ Ｕ２（ｉ≠ ））所在的行形成矩阵Ｍ 。若核属性 为空，则转第４步。 ３）消除矩阵Ｍ 中所有包含核属性的行。 ４）将矩阵Ｍ 中余下的各行表达成析取式，依次检查每 个析取式是否包含于其他的析取式中，将所有包含该析取 式的其他的析取式删除。 ５）将剩下的析取式进行合取运算，得一合取范式，再将 一不一致决策表的属性约简算法，并将吸收律应用于属性约简， 大大提高了属性约简的效率。如何将用于属性约简的新矩阵 应用于不一致决策表增量式属性约简，将另文介绍。 参考文献： ［１】ＰＡＷＬＡＫ Ｚ．Ｖａｇｕｅｎｅｓｓ ａｎｄ ｕｎｃｅｒｔａｉｎｔｙ：ａ ｒｏｕｇｈ ｓｅｔ ｐｒｏｓｐｅｃｔｉｖｅ［Ｊ】． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｉｎｔｅｒｌｌｉｇｅｎｃｅ，１９９５，１ １（２）：３７— ４１． 合取范式转换为析取范式，若核属性不为空，则析取范式中的 每一个合取项加上核属性为一个属性约简；否则析取范式中 的每一个合取项就是一个属性约简。 实例２ 对表１中的决策表进行属性约简。 ［２】ＨＵ Ｘ Ｈ，ＣＥＲＣＯＮＥ Ｎ．Ｌｅａｒｎｉｎｇ ｉｎ ｒｅｌａｔｉｏｎａｌ ｄａｔａｂａｓｅｓ：ａ ｒｏｕｇｈ ｓｅｔ ａｐｐｒｏａｃｈ［Ｊ】．Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９５，１１（２）：３２３—３３７． 按照算法在矩阵Ｍ 中增加（Ａ．，Ａ：）和（Ａ．，Ａ，）对象对 所在的行建立的矩阵Ｍ 如下： ＣＩ —Ｃ２ Ｃ３ ［３】 叶东毅，陈昭炯．一个新的差别矩阵及其求核算法［Ｊ】．电子学 报，２００２，３０（７）：１０８６—１０８８． ０ １ ０ Ａ４，Ａｌ １ １ ０ Ａ４，Ａ２ １ １ １ Ａ４，Ａ３ １ ０ ０ Ａｌ’Ａ２ —１ Ｏ １ ｌ， ３ 由实例１计算得表１的核属性ＣＯＲＥ（Ｃ）＝｛Ｃ ｝，新增加 的对象对（Ａ．，Ａ：）所在的行对应－＇Ｃ ，而对象对（Ａ ，Ａ，）所在 （上接第５２４页） ［４】 赵军，王国胤，吴中福，等．一种高效的属性核计算方法［Ｊ】．小型 微型计算机系统，２００３，２４（１１）：１９５０—１９５３． ［５】 张文修，米据生，吴伟志．不协调目标信息系统的知识约简［Ｊ】． 计算机学报，２００２，２６（１）：１２—１８． ［６】 杨明，孙志挥．改进的差别矩阵及其求核方法［Ｊ】．复旦学报：自 然科学版，２００４，４３（５）：８６５—８６８． ［７】 支天云，苗夺谦．二进制可辨矩阵的变换及高效属性约简算法的 构造［Ｊ】．计算机科学，２００２，２９（２）：１４０—１４２． ， 通过线程及Ｊａｖａ ３Ｄ 对动画效果、交互式操作、形体组合、 复杂的应用程序的支持等来实现仿真（模型显示于界面右 部），并可通过按钮和菜单对仿真的过程进行控制。图６为系 统运行实例。 参考文献： ［Ｉ】 任松涛．ＮＣ代码编译器的设计与实现［Ｄ】．西安：西北工业大 学，２００７． ［２】ＬＥＥＷ Ｂ，ＧＡＯ Ｄ，ＬＩ Ｊ Ｇ．Ａｎ ＮＣｔｏｏｌ ｐａｔｈｔｒａｎｓｌａｔｏｒｆｏｒ ｖｉｔｒｕａｌｍａ－ ｃｈｉｎｉｎｇ ｏｆ ｐｒｅｃｉｓｉｏｎ ｏｐｔｉｃａｌ ｐｒｏｄｕｃｔｓ［Ｊ】．Ｊｏｕｒｎａｌ ｏｆ Ｍａｔｅｒｉｌｓａ Ｐｒｏ— ｃｅｓｓｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ，２００３，１４０（１／３）：２１ １—２１６． ［３】ＬＩＵ Ｙ，ＧＵＯ Ｘ，ＬＩ Ｗ，ｅｔ ａ１．Ａｎ ｉｎｔｅｌｌｉｇｅｎｔ ＮＣ ｐｒｏｇｒａｍ ｐｒｏｃｅｓｓｏｒ ｆｏｒ ＣＮＣ ｓｙｓｔｅｍ ｏｆ ｍａｃｈｉｎｅ ｔｏｏｌ［Ｊ】．Ｒｏｂｏｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ－Ｉｎｔｅｇｒａｔｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ，２００７，２３（２）：１６０—１６９． ［４】 杨旭东，廖文和．仿真系统中通用ＮＣ代码处理技术的研究［Ｊ】． 机械制造与自动化，２００３（１）：４９—５１． ［５】 金龙飞，刘磊．编译器前端构造工具及ＪＬＵＣＣ的实现［Ｊ】．吉林 大学学报：信息科学版，２００５（４）：４２９—４３５． ［６】ＰＡＲＲ Ｔ．ＡＮＴＬＲ ｒｅｆｅｒｅｎｃｅ ｍａｎｕａｌ［ＥＢ／ＯＬ】．［２００７一Ｏ７一Ｏ８】．ｈｔ－ （ａ）实例１ （ｂ）实例２ ｔｐ：／／ｗｗｗ．ａｎｔｌｒ．ｏｒｇ／ｄｏｃ／ｇｌｏｓｓａｒｙ．ｈｔｍ１． 图６系统加工仿真实例 ［７］ 许宇胜，杨文通，王蕾，等．一个ＮＣ代码翻译模块的设计与开 发［Ｊ］．机床与液压，２００５（７）：５５—５６． ［８］ 南雁．基于虚拟数控加工的ＮＣ代码翻译［Ｄ］．西安：西北工业 大学，２０ｏ５． ４ 结话 ●ｔ、一 在分析ＮＣ代码组成及特点基础上，通过ＥＢＮＦ定义了 ＮＣ程序的语法规则，并使用Ａｎｔｌｒ技术快速构建编译器框架。 采用Ｊａｖａ语言，在Ｅｃｌｉｐｓｅ开发平台上通过插件的辅助，简单 高效地开发了一个ＮＣ编译器原型系统。以ＦＡＮＵＣ规范ＮＣ 程序作为输入对其进行测试，试验结果表明：该ＮＣ代码编译 器具有匹配速度快、精度高、通用性和兼容性好的特性；可以 准确地对ＮＣ程序进行翻译；通过扩展ＥＢＮＦ定义的ＮＣ程序 语法规则增强了系统的可扩展性，采用模块化的设计以接口 的方式提供各种功能有利于系统的维护和二次开发。 ［９］葛研军．数控加工关键技术与应用［Ｍ］．北京：科学出版社， ２０ｏ５：２２９—２４８． ［１０］ＧＵＯ ＤＥ—ＧＵＩ，ＷＡＮＧ ＳＨＥＮＧ－ＪＵＮ．Ｐｒｅｃｅｄｅｎｃｅ ｇｒａｍｍａｒ ａｎｄ ｉｔｓ ｔｒａｎｓｆｏｒｍａｔｉｏｎ［Ｃ］／／Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｒｅｓｅａｒｃｈ，Ｍａｎａｇｅｍｅｎｔ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ．Ｌｏｓ Ａｎｇｅｌｅｓ：ＩＥＥＥ Ｐｒｅｓｓ，２００６：１７１—１７６． ［１ １］沙智华，张生芳，葛研军，等．通用数控代码编译系统研究与 实现［Ｊ］．中国机械工程，２００３，（９）：７６３—７６６． ［１２］梁宏宝，杨胡坤，刘丽娜，等．虚拟加工中ＮＣ代码转化技术研 究［Ｊ］．计算机仿真，２００４，２１（１１）：２１９—２２２． ［１３］何同林，张绪冰．基于Ｊａｖａ３Ｄ三维虚拟场景的研究【Ｊ１．计算机 应用，２００７，２７（６）：２９１—２９２．
