|
关键词：粗糙集，决策树理论，救援等级
1粗糙集理论 粗糙集理论[2]是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确、不一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。 1．1信息系统： 信息系统被定义为如下的四元组：S=（U，A，V，f）。其中S为知识表达系统；U=｛x1，x2，…，xn｝为对象的非空有限集合，也称论域；A=｛a1，a2，…，am｝为属性的非空有限集合；V为属性值域，V=∪a∈AVa；f：U×A→V为一信息函数，表示对每一个a∈A，x∈U，f（x，a）∈Va。当信息系统中属性A=C∪D，其中C为条件属性集，D为决策属性集时，信息系统也称为决策系统。 1．2不可分辨关系： 对于信息系统S=（U，A，V，f），P哿A且P≠覫，xi，xj∈U，称二元关系IND（P）＝｛（xi，xj）∈U×U｜a∈P，f（xi，a）＝f（xj，a）｝为关于属性集合P的不可分辨关系。 1．3上、下近似及粗糙度 对于X哿U，R哿A，集合X关于R的下近似定义为R（X）＝∪｛Y哿U／R｜Y哿X｝，其含义是指由那些根据已有知识判断肯定属于X的对象所组成的最大集合。 集合X关于R的上近似定义为R（X）＝∪｛Y哿U／R｜Y∩X≠覫｝，其含义是指由那些根据已有知识判断可能属于X的对象所组成的最小集合。 集合X关于R的边界域定义为：B＝R（X）－R（X） 集合X关于R的近似精度定义为：αR（X）＝R（X） R（X） 集合X关于R的粗糙度定义为：ρR（X）＝1－αR（X） 2决策树理论 决策树方法是数据挖掘的一种，具有易构造、结构简单、易于理解、分类精度高，且易于转化成SQL语句有效地存取数据库，易于实现等优点,在工业决策方面得到广泛应用[3,4]。它是按一定准则选择一个条件属性作为根节点，根据其属性取值将整个例子空间划分为几个子空间，然后递归使用这一准则继续划分，直到所有底层子空间只含有一类例子，决策树构造结束。 国际上最早、最有影响的决策树方法是Quinlan提出的ID3算法[5]。算法引入信息论中的信息增益，作为对实体中选择重要特征的度量，以信息增益最大的特征产生决策树的结点，由该结点的不同取值建立树的分枝，然后对各分枝递归使用该方法建立决策树的结点和分枝，一直到某一子集中的例子属于同一类。因为是利用信息论原理对大量实例的特征进行信息量分析，计算各特征的信息熵，找出反映类别的重要特征，因此抓住了问题的本质，具有建立的决策树少、分类准确率高、生成的规则简单等特点，应用十分广泛。 然而在构造决策树时，按照信息增益最大的原则，ID3算法首先判断的属性有时并不能提供较多的信息。我们对ID3算法作了一些改进，引入粗糙集中的粗糙度，应用于决策树的构造过程中。 3基于粗糙集的决策树构造算法 首先需采集历史数据，然后对数据进行预处理，生成原始数据表，然后用粗糙集属性归约算法中的删除法对数据表进行约简：（1）去除表中的某一属性列；（2）如果数据表不可分辨关系未发生变化，则删除该属性；如果数据表中不可分辨关系发生了变化，则保留该属性。在约简后的数据表的基础上，生成决策树，算法如下： （1）选择决策属性在数据表出现频率最高的属性值，计算条件属性中每个属性关于该决策属性的粗糙度； （2）选择粗糙度最小的条件属性作为当前分支的节点； （3）根据数据表中所选属性的可能取值将数据表分成若干子表，每个取值形成一个子表，在当前分枝构造决策树； （4）对于决策树选择属性的每个分支，如果没有到达叶子节点，则进行递归调用。 该算法的优点： （1）由于在生成决策树前引入了粗糙集的属性约简，可以使数据集中的数据减少，降低了决策树的分枝，从而提高了挖掘效率。 （2）由于在构造决策树时，按照信息增益最大的原则，ID3算法首__ |
|
|
