基于决策表相容度和属性重要度的连续属性离散化算法*

王成宇 林名驰

（1.海军工程大学管理工程与装备经济系 武汉 430033）（2.92690部队施工管理室 三亚 572000）

1 引言

粗糙集理论（Rough Sets）是波兰数学家Pawlak教授[1]于1982年提出的一种处理不精确、不完全与不相容知识的数学理论，其属性约简和属性重要度的概念在预测模型的筛选和组合[2]具有较强的应用价值，对于舰船维修费预测意义重大。粗糙集理论只能用于处理离散型数据，对于连续型数据难以有效应用，然而实际的舰船维修费用数据却是连续型数据，所以，对于连续型数据的离散化处理便成为了对该类问题进行数据预处理的重要环节，且连续属性的最优离散化问题是一个NP-hard问题[3]，其对于其他功能的实现具有重要意义。

针对连续属性离散化问题，按照离散化过程是否考虑决策表中条件属性与决策属性之间的关系可以分为无监督离散化和有监督离散化，其中无监督离散化的常用方法有等距法、等频法等，该类方法易于理解、计算简便，但是离散化过程可能改变原决策表的不可分辨关系，导致决策表不相容的问题。有监督离散化算法在过程中对条件属性与决策属性的关系予以考虑，避免了决策表不相容问题的出现，衣晓等[4]提出一种改进的基于断点重要性的离散化方法，通过对每个条件属性逐一判断其断点的重要性以达到离散化的目的，通过实例分析证明了该方法的有效性；刘静等[5]提出基于断点辨别力的离散化算法，以断点辨别力表征断点的重要性，以加入断点后各等价类中实例是否相同作为算法终止条件，能够保证决策表的分辨关系且不改变其相容度。部分学者以无监督离散化算法为基础，同样得到了较好的离散化效果，陶志等[6]提出一种领域独立的基于决策属性支持度的连续属性离散化算法，通过实例分析比较，说明了该算法的有效性；苗夺谦[7]利用决策表的不相容度作为反馈信息，提出一种基于动态层次聚类的连续属性离散化算法，该算法通过在过程中对决策表及各条件属性不相容度的判别避免了离散化处理后决策表不相容的情况。

属性约简是粗糙集理论的重要功能之一，决策表中各条件属性对于决策属性的重要性是不同的，属性约简的目的是在保持决策表分类能力不变的前提下，剔除掉冗余的条件属性，保留对于决策属性更重要的条件属性，最终简化决策表。在基于粗糙集理论的舰船维修费用预测模型筛选和组合预测问题中，需要在多个单项预测模型中筛选出若干预测模型进行组合预测模型的构建，若采用常用的有监督的离散化算法进行处理则可能存在一个问题，即离散化后的每一个条件属性均能保证在原有分类能力不变的情况下完成对于决策属性的分类，且各条件属性对于决策属性的重要度相同，难以对决策表进行属性约简，便无法达到简化决策表并筛选模型进行组合预测的目的。无监督离散化算法对于决策表中条件属性和决策属性的离散过程是相互独立的，不考虑二者之间的相对关系，故不会出现前述情况，所以本文以无监督离散化算法为基础进行改进来处理此类数据表。除常用的无监督离散化算法存在的可能导致决策表不相容的问题以外，文献[4]中的改进算法在初次离散化时取最大分割点数，且采用逐个将条件属性加入到决策表后判别决策属性支持度再调整分割点数的方法，可能产生冗余的分割点，导致离散化结果不够简化；文献[7]中所提改进算法需要分别对决策表的不相容度、各条件属性的不相容度进行计算与判别，计算过程较为复杂。

针对无监督离散化算法自身存在的可能造成决策表不相容的问题以及文献[4]、[7]中存在的诸多问题，本文尝试引入决策表相容度的概念作为反馈信息，从决策表的整体出发来计算相容度，首先选取数值合理的断点数对数据表进行初始离散化，同时以各模型的属性重要度作为表征其重要程度的度量对条件属性进行排序，通过对决策表相容度的判别，依排序情况逐个地对各条件属性的离散化断点数进行调整，并结合实例进行应用分析。

2 粗糙集及离散化的相关概念

2.1 粗糙集理论

决策表是一个由四元组（U，R，V，f）构成的信息表知识表达系统，其中U=｛x1，…，xn｝是有限的对象集合即论域。R=C∪｛d｝是属性集合，子集C和｛d｝分别被称为条件属性集合决策属性集。是属性值的集合，VA表示属性A∈R的属性值范围，即属性A的值域；f：U×A→V是一个信息函数，它指定U中每个对象x的属性值。

2.2 离散化问题的描述

2.3 决策表的相容性

在一个决策表S=（U，C，D，V，f）中，对于 ∀ci∈C，x，y∈U，若所有f（x，ci）=f（y，ci），均有f（x，D）=f（y，D），则该决策表成为相容决策表，或一致决策表，表中所有的规则均为确定性规则；对于∀ci∈C，x，y∈U，若存在f（x，ci）=f（y，ci），但f（x，D）≠f（y，D），则称该决策表为不相容决策表，或不一致决策表，其不一致项所构成的规则为不确定性规则。

3 传统的无监督离散化算法及其改进算法的问题

传统的无监督离散化算法有等距法和等频法，其中等距法离散化的步骤如下。

取各条件属性对应属性值的最大值ximax和最小值ximin（i=1，2，…，m，表示条件属性的序号），确定类别数k，将属性值的取值范围进行划分，得到分段区间，则每个划分区段的断点值为ximin+lΔi（l=1，2，…，k），将各属性值分别归入相应划分区段内并赋予特征值l（l=1，2，…，k），即得到离散化后的决策表。

但是由于在该离散化过程中不考虑条件属性与决策属性之间的关系，所以可能改变决策表的原有不可分辨关系，造成决策表不相容的问题。现举例对该问题进行简要说明。现有数据表见表1。

表1 数据表

采用等距法对其进行离散化处理，为使离散化后类别不致过于集中或过于分散，选取k=2，得到决策表见表2。

表2 离散化后的决策表

由决策表可知，对象1和2、3和4具有相同的条件属性值，但是对象1、2与对象3、4的决策属性值不同，该决策表不相容，故经过等距法离散化后改变了原决策表的不可分辨关系，造成了原决策表信息的损失，若直接根据属性约简的定义进行计算，可得属性b的支持度r{b}=rC=0.2，所以属性b是该决策表约简结果，而属性a和c均为冗余属性，但是如果｛a，b｝或｛b，c｝构成约简属性集时，对象1、4和对象2、3之间是可以区分的，而属性b却无法单独区分对象1、4和对象2、3，显然a、c又不应该被约简掉，故不相容决策表可能会产生错误的约简结果。

文献[4]在等距法的基础上引入了决策表支持度的概念，并以此为反馈信息对决策表的相容性进行控制，但是该方法在初次离散化时选取最大分割点数，再通过逐次对决策表支持度进行判别，减少各条件属性分割点的数量，这种方法能够达到简化离散化类别的目的，但是也可能造成分割点的冗余。

文献[7]以层次聚类法为基础，引入了决策表不相容度的概念，并以此为反馈信息对决策表的相容性进行控制，但是该方法需要分别对决策表的不相容度以及各条件属性的不相容度进行计算并判别，计算过程相对复杂。

根据已有的无监督离散化算法及其改进算法存在的诸多问题，本文尝试进一步对前述算法进行改进，使新的算法能够符合舰船维修费预测值数据表的离散化及约简要求。

4 基于决策表相容度和属性重要度的连续属性离散化算法

4.1 决策表的相容度

针对前述问题，本文首先引入决策表相容度[8]的概念。

假设X是由决策表中各条件属性按属性值相等确定的等价关系簇，X中等价关系的交仍是一个等价关系，用P表示。用Q表示由决策属性按属性值相等确定的等价关系，且由Q确定的等价类子集簇为｛Y1，Y2，…，Yr（d）｝，则决策表的相容度定义如下：

其中，|U|表示论域的基础；P—(Yi)表示子集Yi在等价关系P下的下近似集；|P—(Yi)|表示P—(Yi)的基数，0 ≤dP（Q）≤ 1，当dP（Q）=1时决策表是相容的。

有效的连续属性离散化的前提是保证决策表的不可分辨关系不变，即保证决策表整体的规则不发生变化，也即决策表的整体信息不产生损失，由决策表相容度的概念可知，保证决策表的不可分辨关系不变就是保持决策表相容度不变。由此，本文拟将决策表相容度作为反馈信息，从决策表整体出发来计算相容度，通过判别相容度是否发生变化来确定是否需要对离散化过程进行调整。从整体出发计算决策表相容度的做法可以有效地简化计算过程，避免了对决策表和各条件属性分别进行运算，同时能够从整体上保证决策表中的不可分辨关系不发生变化、信息不产生损失。

4.2 断点设置原则和基于属性重要度的条件属性排序依据

根据连续属性离散化的原则“在不改变原有不可分辨关系的前提下，利用尽可能少的断点集对连续属性值构成的空间进行划分”，为了控制断点数量，同时保证各条件属性的断点数相对均匀，不致出现断点分布极端不均的情况，本文尝试采用如下措施进行离散化处理。

首先，在确定初次离散化的断点数时，根据数据表规模确定较为合理的数值，使离散化后的类别不致过于集中或过于分散，该原则不同于文献[4]选取最大断点数进行划分，同时，根据决策表相容性的判定结果，拟采用逐个调整的方法增加各条件属性的断点数，为避免选取条件属性的盲目性，需要对所有条件属性进行排序，对于重要性较高的条件属性，优先增加其断点数。属性重要度的度量众多，如信息熵[9]、互信息[10]、依赖度[11]等，此处同样采用属性重要度作为排序依据，因属性频率[12]计算简便、易于理解，故此处采用属性频率作为属性重要度的度量。文献[12]对属性频率的概念进行了详细的介绍，属性频率指单个条件属性在差别矩阵中出现的频率，单个条件属性若在差别矩阵中出现，则表示该属性可以区分某对对象，即构成对象在决策属性中的分类，属性出现的频率越高，其中差别矩阵的定义如下：

然而不相容对象的存在会对属性重要度的计算造成干扰，因此在计算属性重要度时，暂时将不相容对象从决策表中剔除，再进行属性频率的计算，重新离散化时一并参与调整，当出现所有对象均不相容的情况时，则对所有对象重新进行离散化，再进行后续计算。

先选取较为合理的断点数进行划分，再依据决策表相容度的判别情况增加断点数可以保证断点的数量一直处于可控状态，从而有效控制断点数量；以属性重要度为依据对条件属性排序后再按排序情况逐个对条件属性的断点数进行调整，对于重要度较高的条件属性，优先增加其断点数，这样可以使重要程度较高的条件属性更充分地离散化，同时使断点分布更加均匀，不致出现极端不均的情况，避免了属性重要度相差过大从而影响后续属性约简过程的问题。

4.3 基于决策表相容度和属性重要度的连续属性离散化算法的具体步骤

基于决策表相容度和属性重要度的连续属性离散化算法的具体步骤如下。

第一步：根据式（2）计算原数据表的初始相容度dP0（Q）；

第二步：根据数据表规模确定离散化类别数k，采用等距法对各条件属性及决策属性进行离散化处理，构建决策表；

第三步：根据决策表，由式（2）计算决策表的相容度dP（Q），并与原数据表的相容度dP0（Q）进行比较：

若dP（Q）≠dP0（Q），则转至第四步；

若dP（Q）=dP0（Q），则算法终止，转至第五步；

第四步：根据式（3）和所得差别矩阵计算各条件属性的属性重要度，并按属性重要度对条件属性进行降序排列，同时取k=k+1，按排序对各条件属性重新进行离散化处理，并逐次计算相容度，当所有条件属性均重新离散化后，转至第三步；

第五步：所得决策表即为离散化后的决策表。

5 例证分析

采用某型舰船小修费用数据为样本，分别采用移动平均法、一元线性回归法、ARIMA法、多层感知器和RBF神经网络进行预测，各单项预测方法标记为 a，b，c，d，e，实际值序列标记为 f，同上取2012-2020年间的数据进行分析，预测结果见表3。

表3 某型舰船小修费用预测值数据表

采用本文提出的改进算法对表3中数据进行离散化处理。

第一步：根据式（2）计算原数据表的相容度dP0（Q）=1。

第二步：根据决策表规模，为了使离散化后类别不致过于分散或过于集中，取k=3，采用等距法对各条件属性及决策属性进行离散化处理，构建决策表见表4。

表4 决策表

第三步：根据式（2）计算所得决策表的相容度dP（Q）=0.625，可知该决策表不相容，不相容对象为4、5、6，则将这三个对象从决策表中剔除后得到决策表见表5。

表5 剔除不相容对象后的决策表

同时计算得到各条件属性的属性重要度为θ=[0.142857，0.178571，0.214286，0.214286，0.25]，得到条件属性按属性重要度的排序结果为E=｛e，c，d，b，a｝；

第四步：判别可得dP（Q）≠1，则取k=4，再次对条件属性e进行离散化，并重复前述步骤，直到dP（Q）=1，算法终止。

此处，若采用文献[4]中算法，所得决策表的断点总数为26，而本文算法所得决策表的断点总数为16，故本文提出的改进算法可以得到更少的断点数，离散化效果更好；若采用文献[7]中算法，则计算步骤更为繁琐，需要逐次对各条件属性和整个决策表的不相容度进行判定，而本文方法只需从整个决策表出发进行判定便可达到充分离散化的目的，计算过程更为简洁。

第五步：最终得到的决策表见表6。

表6 最终决策表

由实例分析可知，经调整后的决策表是相容的，保持了原有的不可分辨关系，避免了重要数据表中重要信息的损失，为后续的筛选和组合环节奠定了良好的基础。

6 结语

针对基于粗糙集理论的舰船维修费单项预测模型筛选和组合预测模型构建过程中涉及到的连续属性离散化问题，本文对有监督与无监督离散化算法的适用性及特点进行了分析，指出有监督离散化算法在处理该类数据表的局限性以及无监督离散化算法的可行性，同时指出传统的无监督离散化算法存在的可能导致决策表不相容的问题和两种改进算法[2～3]存在的分割点冗余及计算过程复杂的问题。引入决策表相容度的概念，并以此作为反馈信息，从整体上对决策表的相容性进行判别，通过判别决策表的相容性，决定是否对条件属性进行调整，在保证决策表整体相容性不变的前提下，简化了计算过程；在初次对各条件属性进行离散化时，根据数据表规模确定较为合理的断点数值，而不是选取最大值在逐渐删减，避免了断点的冗余；以属性重要度为依据对条件属性进行排序，并依据决策表相容性判别情况逐个对条件属性的离散化断点数进行调整，使重要程度较高的条件属性得到更充分的离散化，同时能够保证断点分布更为均匀，不致出现断点分布极端不均的情况，便于后续属性约简的顺利进行。通过实例分析，验证了改进算法对于此类数据表处理的有效性。