一种改进的分辨矩阵构造及求核算法

史君华， 刘乐群

（合肥师范学院计算机科学与技术系，安徽合肥 230601）

文献［1］提出了一种能处理模糊性和不确定性问题的粗糙集合理论，其核心思想是在保持数据分类能力不变的前提下，通过对知识的化简，导出问题的决策或分类规则。目前粗糙集合理论被广泛应用于机器学习、知识发现、专家系统、数据挖掘、模式识别等研究领域［2］。

约简是粗糙集理论研究的重要内容之一，它包括属性约简和属性值约简，而求取核属性通常是求解决策表约简的关键步骤。多年来，学者们提出了各种利用分辨矩阵求取核属性的方法。文献［3］提出了一种用分辨矩阵表示知识的经典算法，该方法简单、易懂，但时间复杂度较高；文献［4］提出了一种基于Skowron矩阵的简化的差别矩阵方法，该方法简化了矩阵元素的构造；文献［5］指出，当决策表中存在不一致数据，文献［4］中的算法可能存在错误，故通过增加一个函数min｛｜d（xi）｜，｜d（xj）｜｝的计算，提高了算法的正确性，时间开销亦有所增加；文献［6］提出了一种基于二进制分辨矩阵的求核算法，为分辨矩阵及核属性的求解开辟了一条新的道路；另外，还有很多学者提出了各种分辨矩阵及求核算法的改进算法［7－11］。

以上算法中，有些是时间性能不理想，有些是不能将算法应用于不一致的决策表；另外发现，分辨矩阵中很多元素并不需要保存，分辨矩阵的构造过程还可进一步优化。因此，本文提出一种能同时适用于一致和不一致系统的快速构造矩阵并计算核属性的优化算法，其构造方法简单，时间性能较好；并通过实例和实验说明了算法的有效性。

1 粗糙集理论基本概念

别表示条件属性集和决策属性集是属性值的集合，其中Vr表示r∈R的属性值，f：U×R→V是信息函数。同时具有条件属性和决策属性的信息系统称为决策表（系统）。

定义3 令R为等价关系族，设且P≠Ø，则P中所有等价关系的交集称为P上的不可分辨关系，记作IND（P）。

定义4 设R是等价关系族，R∈R，若IND（R）＝IND（R－｛R｝），则称R是R中可省的，否则为不可省的。若R中每个关系都不可省，则称R是独立的，否则为依赖的。

若用RED（P）表示P的所有约简的集合，则有下面关系成立。

定理1 等价关系族P的核等于P的所有约简的交集，则有

定义7 决策表中有关条件属性集C和决策属性集D的一个规则可以表示为α→β。其中，α是一个C－集合（称为规则的前提），β是一个D－集合（称为规则的结论），称α→β为一个CD－规则

定义1 设U为所讨论对象的非空有限集合，称为论域；R为建立在U上的一个等价关系族集，称二元组AS＝（U，R）为近似空间。

定义2 设S＝（U，R，V，f）为一个信息系统，其中U是论域，R＝C∪D是属性集合，C、D分（决策规则）。

定义8 决策表中的一个CD－规则α→β是一致的，当且仅当对任何CD－规则必蕴含β＝β′。如果一个决策表中的所有决策规则都是一致的，则决策表是一致的，否则决策表是不一致的。

2 改进的分辨矩阵构造及求核思想

文献［4］指出，决策表中的不一致数据可能会影响最终核或约简求解的正确性，因此在本文提出的算法中，首先会检查决策表中是否存在不一致数据，对不一致数据加以处理，并在此基础上考虑提高算法的时间性能。

2.1 改进的分辨矩阵

改进的分辨矩阵只存储三角矩阵，假设上三角（即j＞i）部分的每个元素Mij分为Mij1和Mij22项，Mij1负责条件属性部分，Mij2负责决策属性部分，具体构造见定义9（其中，a为条件属性，b为决策属性，xi、xj为2个实例）。

定义9Mij1与Mij2的构造如下：

由以上矩阵定义可得如下性质。

性质1 若Mij1＝0且Mij2＝0，则xi、xj为重复实例，可从原数据表删去第i或j行而不影响求解。

性质2 若Mij1＝0且Mij2＝1，则xi、xj为不一致实例，原数据表删去第i和j行以保持一致性。

性质3 若Mij1为非0的单个属性且Mij2＝0，则该单个属性为可约属性，可不予考虑。

性质4 若Mij1为非0的单个属性且Mij2＝1，则该单个属性为核属性。

其中，性质1、2、3很容易得到，本文对性质4加以证明。

证明 用C和D分别代表某决策表的条件和决策属性集，核集为CORE，xi、xj为任意2个实例。文献［3］中经典Skowron分辨矩阵构造如下：

2.2 基于核和吸收率的分辨矩阵优化构造思想

本算法中基于核属性和吸收率的分辨矩阵优化构造思想如下：首先按定义9构造分辨矩阵，其中一旦有核属性（Mij1为非0的单个属性且Mij2＝1）产生，则在后续分辨矩阵的构造过程中，先判断在该核属性上2个实例取值是否相等。若不等，则跳过该项分辨矩阵的构造（或记标记Ø）；若相等，则继续按定义9构造，另外在构造分辨矩阵的过程中，不断地充实核集，新产生的核对其后续分辨矩阵元素的构造有同样的优化效果。

例1 假设一决策表数据，见表1所列（其中a、b、c、d、e为条件属性；f为决策属性）。

表1 决策表1

已构造的部分分辨矩阵数据，见表2所列。

表2 已构造的部分分辨矩阵

由于M13处分辨矩阵项元素为d1，据定义9中性质4，d为核属性，所以在求M14时，先判断x1和x4在属性d上取值情况。显然，取值不等，因此可直接跳过M14去构造M15，这就是吸收率在构造分辨矩阵过程中的应用。原因是：假设M14按正常方法计算，应为abcde1，则在构造分辨矩阵之后，如果后期计算属性约简，由于d⊆abcde，所以也会删去abcde。因此，将吸收率运用到分辨矩阵的构造过程中，不仅节省时间，而且减少了分辨矩阵包含的项，简化了后面的运算，特别是当核属性出现得较早时，该算法能极大地优化分辨矩阵的构造。

2.3 改进的分辨矩阵构造及求核的优化算法

基于上述思想，本文提出了一种改进的分辨矩阵优化构造及求核算法，具体步骤如下。

本算法中，在构造分辨矩阵每项元素时，都运用核和吸收率作为优化信息，加速矩阵后续项的构造。首先看核集是否为空，若核集不为空，对于核集里的每个核属性，先判断2个实例在核属性上取值是否相同，若在某个核属性上取值不同，则可跳过该项分辨矩阵项元素的构造（或记标记Ø），否则按定义9继续构造该项分辨矩阵元素。另外，在构造分辨矩阵的过程中亦不断地充实核集，这与经典算法相比，不仅可简化后续运算，有更好的时间性能，而且大大减少分辨矩阵项元素所占有的空间。

2.4 实例

以决策表1为例讨论本文提出的算法性能，并与Skowron经典算法比较。对于Skowron经典算法，构造的分辨矩阵见表3所列。

表3 决策表1构造的Skowron分辨矩阵

本文提出的改进的分辨矩阵构造，见表4所列。显然，c、d为核属性，在构造分辨矩阵的过程中，括号内为利用本文算法中吸收率优化构造的分辨矩阵项元素，括号外为不利用吸收率，仅利用定义9构造的分辨矩阵项元素。

表4 本文算法构造的分辨矩阵

与表3比较，本文提出的算法，矩阵内的有效元素已明显减少，因而可大大简化后续运算；且在构造分辨矩阵的过程中，核属性出现得越早，越能减少构造分辨矩阵所花费的时空开销。

2.5 实验结果及分析

本次实验以2.34 GHz、1 G内存为硬件环境，以win XP、JDK6.1为软件开发环境。使用了UCI国际机器学习数据库中的6个数据集，比较并分析了本算法的性能，实验结果见表5所列。从表5可以看出，本文算法对于核属性存在的决策系统、时间性能的改进较明显，原因在于构造分辨矩阵的同时对包含核属性的项运用吸收率，因此比经典算法执行速度加快。但若核为空，该算法的时间性能可能会与经典算法相差不大。设一个决策系统实例个数为｜U｜，条件属性个数为｜C｜，本文提出算法的时间复杂度的上限为O（｜C｜×｜U｜2），实际上通常远远小于该上限。

表5 与经典算法的时间性能比较

3 结束语

本文在对粗集理论中利用构造矩阵求解核属性算法研究的基础上，提出一种基于核属性和吸收率优化的决策表矩阵求核改进算法，通过原理及实验论证，该方法简单、有效，但空间性能仍需改进，使之能适用于更大规模的数据集。

［1］ Pawlak Z.Rough sets［J］.International Journal of Computer and Information Sciences，1982，11（5）：341－356.

［2］ 杨 勇，朱晓钟，李 廉.直觉模糊粗糙集的公理化［J］.合肥工业大学学报：自然科学版，2010，33（4）：590－592.

［3］ Skowron A，Rauszer C.The discernibility matrices and functions in information systems［C］／／Intelligent Decision Support：Handbook of Applications and Advances of the Rough Sets Theory，1992：331－362.

［4］ Hu Xiaohua，Cercone N.Learning in relational databases：a rough set approach［J］.Computational Intelligence，1995，11（2）：323－338.

［5］ 叶东毅，陈昭炯.一个新的差别矩阵及其求核方法［J］.电子学报，2002，30（7）：1086－1088.

［6］ 支天云，苗夺谦.二进制可辨矩阵的变换及高效属性约简算法的构造［J］.计算机科学，2002，29（2）：140－142.

［7］ 王国胤，于 洪，杨大春.基于条件信息熵的决策表约简［J］.计算机学报，2002，25（7）：759－766.

［8］ 徐章艳，杨炳儒，宋 威.一个基于差别矩阵的快速求核算法［J］.计算机工程与应用，2006（6）：4－6.

［9］ 汪小燕.一种改进的差别矩阵及其求核方法［J］.安徽工业大学学报：自然科学版，2009，26（1）：86－95.

［10］ 汪小燕，王 浩.基于二进制可辨矩阵的知识粒度研究及应用［J］.计算机技术与发展，2006，16（10）：91－93.

［11］ 徐章艳，杨炳儒，宋 威，等.几种不同属性约简的比较研究［J］.小型微型计算机系统，2008，5（5）：848－853.