一种基于核值的粗糙集填补方法

摘 要 利用粗糙集的知识来进行缺失数据填补的方法很多，但很多都没有考虑到决策规则。文章利用核值的重要性，通过构造可辨识矩阵，使得填补的数据更好的遵循决策规则，消除噪音数据。

关键词 核值；极大完备子系统；可辨识矩阵

中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2014）08-0061-01

1 粗糙集相关知识

在现今社会中，各个行业都会用数据库来保存大量的历史数据。然而，这些数据总会在不经意间有所缺失，可能是环境因素，也可能是人为缺失。缺失的数据都蕴含着大量宝贵有用的信息，与企业经营成果息息相关，因此很多企业都采用数据挖掘等技术，从缺失的数据中挖掘出有价值的信息。

粗糙集理论是继概率论，模糊集，证据理论之后的又一个处理不确定性的数学工具，其作为一种较新的软计算方法，其被有效的运用到数据预处理中，为不完备信息的填补开辟了另一条途径。

在基于粗糙集的属性约简过程中，核值才是最有用的数据。本文提出了一种基于核值的重要性的填补方法，较好的保持信息表的决策规则。

该算法主要涉及到极大完备子系统和可辨识矩阵等粗糙集知识，相关的定义如下。

定理1 任一信息系统=，若增加一条对象，构成一个新的信息系统=<，，，>，其中，则的核值必是的核值。

推论 不完备信息系统S=，=是其极大完备子系统，则的核值必是S的核值。

2 基于核值的ROUSTIDA算法描述

2.1 算法描述

由上述推论可以表明将不完备信息系统S分离成其极大完备子系统和待补系统，而的核值必是S的核值，这说明在的核值的基础上引进不可分辨关系不影响S的核值。

该算法是以可辨识矩阵为基础，基本流程如下。

输入：不完备信息系统；

输出：完备信息系统；其中，前者是条件属性集，后者为决策属性集；

第一步 核值化：

将分离成它的极大完备子系统和待补系统。将看作是一个独立系统，建立它的核值体系，然后再将非核值的数据改为“*”，这样就会得到一个新的系统，将组合成一个新的信息系统=<，，，>.

第二步 求矩阵，，；r=0；

第三步

1）针对所有，求得，；

2）生成

（1） 对于所有，有=，；

（2） 对于所有，对做循环；

①若=0，=*；

②否则若，则

（1）若，则；

（2）若，则；

（3）否则；

③若某一对象与多个对象存在不可分辨关系，则将此对象的缺失属性值用其余对象的此属性的均值填补；

第四步 决策表中对象独立性的判断：

1）对上述；若=0，则如存在，使=时，都有，将=*转步骤3，否则转2；若有（），将（）整行删去；否则转2；

2）若=转步骤5；否则，计算，，，，转到第三步；

第五步 如果有遗失值，可用其他算法处理；

第六步 结束。

2.2 算法分析

算法主要解决使ROUSTIDA算法失效的不完备数据。可以通过以下图表来说明问题。包括原始的不完备信息表，经过步骤一得出的基于核值的不完备信息系统，以及最终得到的完备信息表。

表1 原始表

U a1 a2 a3 a4

1 0 1 0 1

2 * 2 1 0

3 * 0 0 0

4 0 * 1 0

5 1 0 1 2

表2 基于核值的不完备信息表

U a1 a2 a3 a4

1 0 1 0 1

2 * 2 1 0

3 * 0 0 0

4 0 1 1 1

5 1 0 1 2

表3 结果表

U a1 a2 a3 a4

1 0 1 0 1

2 0 2 1 0

3 0 0 0 0

4 0 1 1 0

5 1 0 0 2

与原ROUSTIDA算法比较，该算法能使更多的缺失项得到科学的填补，且该算法在缺失项填补过程中，基于可辨识矩阵，以核值为比较对象，这样填补可保留更多的核值，从而使填补的值与决策规则更为贴近。同时第四步对决策表中对象独立性的判断，使该算法避免了应用其他方法可能导致的决策规则矛盾的问题。

但该算法也存在一定的缺点：1）计算较为复杂，比原ROUSTIDA算法计算繁琐；2）该算法仅对缺损数据较少时适用，若缺损较多，则对于初始计算极大完备子系统时存在的困难较大，甚至可能无法操作。

3 结论

一般的填补数据方法有时容易引起信息表内容的冲突，本算法是基于核值的基础上进行缺失数据填补的，能够保持更多的核值，并且更好的避免了信息表的冲突，又较好的反映了信息表所蕴含的决策规则。

参考文献

[1]Pawlak Z. Rough Sets and Fuzzy Sets. Fuzzy Sets and Systems， 1985（17）：99-102.

[2]Krysikiewicz M. Rough Set Approach to Incomplete Information System. Information Sciences， 1998（112）：39-49.

[3]王国胤.Rough集理论与知识获取[M].西安：西安交通大学出版社，2005.

[4]张文修，吴伟志，梁吉业，等.粗糙集理论与方法[M].北京：科学出版社，2006.

[5]曾黄麟.粗糙集理论及其应用[M].重庆：重庆大学出版社，1996.

作者简介

席宁（1977-），女，汉族，辽宁锦州人，副教授，硕士，主要从事计算机网络，数据挖掘，计算机应用设计。

摘 要 利用粗糙集的知识来进行缺失数据填补的方法很多，但很多都没有考虑到决策规则。文章利用核值的重要性，通过构造可辨识矩阵，使得填补的数据更好的遵循决策规则，消除噪音数据。

关键词 核值；极大完备子系统；可辨识矩阵

中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2014）08-0061-01

1 粗糙集相关知识

在现今社会中，各个行业都会用数据库来保存大量的历史数据。然而，这些数据总会在不经意间有所缺失，可能是环境因素，也可能是人为缺失。缺失的数据都蕴含着大量宝贵有用的信息，与企业经营成果息息相关，因此很多企业都采用数据挖掘等技术，从缺失的数据中挖掘出有价值的信息。

粗糙集理论是继概率论，模糊集，证据理论之后的又一个处理不确定性的数学工具，其作为一种较新的软计算方法，其被有效的运用到数据预处理中，为不完备信息的填补开辟了另一条途径。

在基于粗糙集的属性约简过程中，核值才是最有用的数据。本文提出了一种基于核值的重要性的填补方法，较好的保持信息表的决策规则。

该算法主要涉及到极大完备子系统和可辨识矩阵等粗糙集知识，相关的定义如下。

定理1 任一信息系统=，若增加一条对象，构成一个新的信息系统=<，，，>，其中，则的核值必是的核值。

推论 不完备信息系统S=，=是其极大完备子系统，则的核值必是S的核值。

2 基于核值的ROUSTIDA算法描述

2.1 算法描述

由上述推论可以表明将不完备信息系统S分离成其极大完备子系统和待补系统，而的核值必是S的核值，这说明在的核值的基础上引进不可分辨关系不影响S的核值。

该算法是以可辨识矩阵为基础，基本流程如下。

输入：不完备信息系统；

输出：完备信息系统；其中，前者是条件属性集，后者为决策属性集；

第一步 核值化：

将分离成它的极大完备子系统和待补系统。将看作是一个独立系统，建立它的核值体系，然后再将非核值的数据改为“*”，这样就会得到一个新的系统，将组合成一个新的信息系统=<，，，>.

第二步 求矩阵，，；r=0；

第三步

1）针对所有，求得，；

2）生成

（1） 对于所有，有=，；

（2） 对于所有，对做循环；

①若=0，=*；

②否则若，则

（1）若，则；

（2）若，则；

（3）否则；

③若某一对象与多个对象存在不可分辨关系，则将此对象的缺失属性值用其余对象的此属性的均值填补；

第四步 决策表中对象独立性的判断：

1）对上述；若=0，则如存在，使=时，都有，将=*转步骤3，否则转2；若有（），将（）整行删去；否则转2；

2）若=转步骤5；否则，计算，，，，转到第三步；

第五步 如果有遗失值，可用其他算法处理；

第六步 结束。

2.2 算法分析

算法主要解决使ROUSTIDA算法失效的不完备数据。可以通过以下图表来说明问题。包括原始的不完备信息表，经过步骤一得出的基于核值的不完备信息系统，以及最终得到的完备信息表。

表1 原始表

U a1 a2 a3 a4

1 0 1 0 1

2 * 2 1 0

3 * 0 0 0

4 0 * 1 0

5 1 0 1 2

表2 基于核值的不完备信息表

U a1 a2 a3 a4

1 0 1 0 1

2 * 2 1 0

3 * 0 0 0

4 0 1 1 1

5 1 0 1 2

表3 结果表

U a1 a2 a3 a4

1 0 1 0 1

2 0 2 1 0

3 0 0 0 0

4 0 1 1 0

5 1 0 0 2

与原ROUSTIDA算法比较，该算法能使更多的缺失项得到科学的填补，且该算法在缺失项填补过程中，基于可辨识矩阵，以核值为比较对象，这样填补可保留更多的核值，从而使填补的值与决策规则更为贴近。同时第四步对决策表中对象独立性的判断，使该算法避免了应用其他方法可能导致的决策规则矛盾的问题。

但该算法也存在一定的缺点：1）计算较为复杂，比原ROUSTIDA算法计算繁琐；2）该算法仅对缺损数据较少时适用，若缺损较多，则对于初始计算极大完备子系统时存在的困难较大，甚至可能无法操作。

3 结论

一般的填补数据方法有时容易引起信息表内容的冲突，本算法是基于核值的基础上进行缺失数据填补的，能够保持更多的核值，并且更好的避免了信息表的冲突，又较好的反映了信息表所蕴含的决策规则。

参考文献

[1]Pawlak Z. Rough Sets and Fuzzy Sets. Fuzzy Sets and Systems， 1985（17）：99-102.

[2]Krysikiewicz M. Rough Set Approach to Incomplete Information System. Information Sciences， 1998（112）：39-49.

[3]王国胤.Rough集理论与知识获取[M].西安：西安交通大学出版社，2005.

[4]张文修，吴伟志，梁吉业，等.粗糙集理论与方法[M].北京：科学出版社，2006.

[5]曾黄麟.粗糙集理论及其应用[M].重庆：重庆大学出版社，1996.

作者简介

席宁（1977-），女，汉族，辽宁锦州人，副教授，硕士，主要从事计算机网络，数据挖掘，计算机应用设计。

摘 要 利用粗糙集的知识来进行缺失数据填补的方法很多，但很多都没有考虑到决策规则。文章利用核值的重要性，通过构造可辨识矩阵，使得填补的数据更好的遵循决策规则，消除噪音数据。

关键词 核值；极大完备子系统；可辨识矩阵

中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2014）08-0061-01

1 粗糙集相关知识

在现今社会中，各个行业都会用数据库来保存大量的历史数据。然而，这些数据总会在不经意间有所缺失，可能是环境因素，也可能是人为缺失。缺失的数据都蕴含着大量宝贵有用的信息，与企业经营成果息息相关，因此很多企业都采用数据挖掘等技术，从缺失的数据中挖掘出有价值的信息。

粗糙集理论是继概率论，模糊集，证据理论之后的又一个处理不确定性的数学工具，其作为一种较新的软计算方法，其被有效的运用到数据预处理中，为不完备信息的填补开辟了另一条途径。

在基于粗糙集的属性约简过程中，核值才是最有用的数据。本文提出了一种基于核值的重要性的填补方法，较好的保持信息表的决策规则。

该算法主要涉及到极大完备子系统和可辨识矩阵等粗糙集知识，相关的定义如下。

定理1 任一信息系统=，若增加一条对象，构成一个新的信息系统=<，，，>，其中，则的核值必是的核值。

推论 不完备信息系统S=，=是其极大完备子系统，则的核值必是S的核值。

2 基于核值的ROUSTIDA算法描述

2.1 算法描述

由上述推论可以表明将不完备信息系统S分离成其极大完备子系统和待补系统，而的核值必是S的核值，这说明在的核值的基础上引进不可分辨关系不影响S的核值。

该算法是以可辨识矩阵为基础，基本流程如下。

输入：不完备信息系统；

输出：完备信息系统；其中，前者是条件属性集，后者为决策属性集；

第一步 核值化：

将分离成它的极大完备子系统和待补系统。将看作是一个独立系统，建立它的核值体系，然后再将非核值的数据改为“*”，这样就会得到一个新的系统，将组合成一个新的信息系统=<，，，>.

第二步 求矩阵，，；r=0；

第三步

1）针对所有，求得，；

2）生成

（1） 对于所有，有=，；

（2） 对于所有，对做循环；

①若=0，=*；

②否则若，则

（1）若，则；

（2）若，则；

（3）否则；

③若某一对象与多个对象存在不可分辨关系，则将此对象的缺失属性值用其余对象的此属性的均值填补；

第四步 决策表中对象独立性的判断：

1）对上述；若=0，则如存在，使=时，都有，将=*转步骤3，否则转2；若有（），将（）整行删去；否则转2；

2）若=转步骤5；否则，计算，，，，转到第三步；

第五步 如果有遗失值，可用其他算法处理；

第六步 结束。

2.2 算法分析

算法主要解决使ROUSTIDA算法失效的不完备数据。可以通过以下图表来说明问题。包括原始的不完备信息表，经过步骤一得出的基于核值的不完备信息系统，以及最终得到的完备信息表。

表1 原始表

U a1 a2 a3 a4

1 0 1 0 1

2 * 2 1 0

3 * 0 0 0

4 0 * 1 0

5 1 0 1 2

表2 基于核值的不完备信息表

U a1 a2 a3 a4

1 0 1 0 1

2 * 2 1 0

3 * 0 0 0

4 0 1 1 1

5 1 0 1 2

表3 结果表

U a1 a2 a3 a4

1 0 1 0 1

2 0 2 1 0

3 0 0 0 0

4 0 1 1 0

5 1 0 0 2

与原ROUSTIDA算法比较，该算法能使更多的缺失项得到科学的填补，且该算法在缺失项填补过程中，基于可辨识矩阵，以核值为比较对象，这样填补可保留更多的核值，从而使填补的值与决策规则更为贴近。同时第四步对决策表中对象独立性的判断，使该算法避免了应用其他方法可能导致的决策规则矛盾的问题。

但该算法也存在一定的缺点：1）计算较为复杂，比原ROUSTIDA算法计算繁琐；2）该算法仅对缺损数据较少时适用，若缺损较多，则对于初始计算极大完备子系统时存在的困难较大，甚至可能无法操作。

3 结论

一般的填补数据方法有时容易引起信息表内容的冲突，本算法是基于核值的基础上进行缺失数据填补的，能够保持更多的核值，并且更好的避免了信息表的冲突，又较好的反映了信息表所蕴含的决策规则。

参考文献

[1]Pawlak Z. Rough Sets and Fuzzy Sets. Fuzzy Sets and Systems， 1985（17）：99-102.

[2]Krysikiewicz M. Rough Set Approach to Incomplete Information System. Information Sciences， 1998（112）：39-49.

[3]王国胤.Rough集理论与知识获取[M].西安：西安交通大学出版社，2005.

[4]张文修，吴伟志，梁吉业，等.粗糙集理论与方法[M].北京：科学出版社，2006.

[5]曾黄麟.粗糙集理论及其应用[M].重庆：重庆大学出版社，1996.

作者简介

席宁（1977-），女，汉族，辽宁锦州人，副教授，硕士，主要从事计算机网络，数据挖掘，计算机应用设计。