基于信息量的不完备信息系统属性约简

通过引入信息量和条件信息量,对不完备信息系统中属性的重要性进行了定义;针对不完备数据表和不完备决策表提出了一种基于信息量和条件信息量的属性约简启发式算法,该算法的时间复杂度是多项式的.通过实例说明,该算法能得到信息表的约简和决策表的相对约简.     

基于冲突域渐减的属性约简算法

针对因决策表中存在不一致对象造成的约简求解错误,同时为了进一步提高约简算法求解效率, 首先,给出简化决策表的定义,并证明了简化决策表的核属性和属性约简与原始决策表的核属性和属性约简是等价的. 然后,提出冲突域的概念,分析冲突域的性质,以冲突域中冲突对象个数的变化为度量依据, 研究核属性和属性重要性的性质,同时设计相应的核属性和属性重要性求解算法;在此基础上, 设计基于冲突域渐减式属性约简算法,算法的时间和空间复杂度分别为O(|C|²|U/C|)和O(|U|). 最后的实例和实验结果表明该方法是正确的,高效的.     

一种新的决策表属性约简算法

结合模糊聚类技术与粗糙集中属性重要性思想,对同时含有连续、离散、序数型条件属性的决策表,提出一种属性约简算法,并对算法的时间复杂度进行了分析.该方法首先利用聚类技术将决策表的对象按条件属性进行分类,然后对去掉某属性后的决策表采用同样的方法进行聚类,再结合粗糙集理论进行属性约简.实例说明了该方法的合理性和有效性.     

基于信息量的序信息系统的属性约简

属性约简是粗糙集理论研究的核心内容之一.在序信息系统中引入信息量和属性重要性,给出它们与属性约简之间的关系.针对序信息系统提出了一种基于信息量和属性重要性的属性约简算法,讨论了算法的时间复杂度.实例证明了该算法的有效性.     

属性约简的两阶段遗传算法

属性约简是数据挖掘的一个重要研究内容. 为了解决具有多种属性类型的决策表约简问题,在粗集和二元关系聚合理论的基础上,利用属性重要性作为评价标准,提出了一种两阶段遗传约简算法. 算法的第一阶段是为了找出尽可能多的约简,第二阶段力求寻找最小约简. 根据算法每个阶段的目标设计了编码方案、种群规模、适应度函数、终止条件、选择、变异和修正操作. 实验表明,与标准遗传算法相比,两阶段算法在计算最小约简时更为准确和稳定.     

基于启发式知识的属性约简方法及其在评价体系中的应用

针对知识约简过程中出现的NP问题，提出用于条件属性重要性分析的条件--决策关联度概念，以此作为启发式知识用于决定决策表中冗余属性的约简次序，最终实现快速、高效地对条件属性集进行约简。文末以广东省自然科学基金立项评审系统作为应用对象，说明该算法的有效性。     

基于特征矩阵的决策表约简研究

决策表属性约简是粗集分析的重要内容 .最优属性约简是 NP困难问题 ,目前出现的启发式算法多是以决策表的核为起点 .但对于大型决策表 ,核一般计算量大 ,影响了整个算法的效率 .为此提出了一种分析决策表的属性约简算法 ,它不仅不依赖于核 ,反而为核提供了一种有效的计算方法 .其次 ,对人们容易忽略的含噪声决策表的属性约简也进行了分析 .     

不一致决策表中规则提取的矩阵算法

由于数据采集能力不足等原因,决策表通常都不是一致的。如果将不一致的对象完全删除,则丢失了大量隐含在这些对象中的信息。针对不一致决策表,在分配约简、分布约简和最大分布约简的定义基础上,通过定义相应的决策矩阵并比较它们与条件属性矩阵的关系,得到提取信息系统的所有分配规则、分布规则和最大分布规则的矩阵方法。该方法的优点是直观有效,能获得所有规则,并同时得到相应的约简。     

基于区分矩阵与强等价集的启发式知识约简法

提出了基于区分矩阵与强等价集的启发式知识约简方法。在决策表的相对约简过程中采用区分矩阵来表达知识,并利用区分矩阵中项的长度和每个属性的频率作为启发信息进行属性的选择。同时利用属性加权频率和强等价集概念化简区分矩阵,既减小了计算复杂度又提高了约简效率。现已证明,寻找决策表中最小相对约简问题是典型的问题,采用该算法在大多数情况下能够找到最小约简,即使在未找到最小约简的情况下,也能找到次优解。通过实例分析,证明该算法是求解属性相对约简的快速、有效的方法.     

一种基于分明矩阵的启发式知识约简方法

提出了基于分明矩阵的启发式知识约简方法。在决策表的相对约简过程中采用分明矩阵来表达知识,并利用分明矩阵中项的长度和每个属性的频率作为启发信息进行属性的选择。现已证明,寻找决策表中最小相对约简问题是典型的NP hard问题。所提供的算法在大多数情况下能够找到最小约简,即使在没找到最小约简的情况下,也能找到次优解。通过实例分析,证明该算法是求解属性相对约简的快速有效的方法     

不完备决策系统中规则提取的快速矩阵算法

提出了广义决策的不可分辨关系及其不可分辨类、联合决策相容矩阵等概念以及不完备决策系统中基于联合决策相容矩阵的约简和规则提取的快速矩阵算法.将条件属性相容矩阵和决策属性分配决策矩阵合并到一个矩阵中,大大减少了矩阵生成过程的比较次数,有效的提高了算法的效率.通过一个实例,说明了算法的执行过程;算法复杂度分析以及相应的对比实验,进一步说明了该方法的有效性.     

Joint Decision Matrix Computation for Rules Extraction in Two-Classes Decision Information System

Matrix computation for rules extraction of rough set algorithm's inefficiency restricts the application of rough set theory, so the search for efficient algorithms is of great practical significance. Therefore, the joint decision matrix is defined and a new algorithm JDMCRE for rule extraction is presented on the basis of joint decision matrix for two-classes decision information system. By combining both the conditional attribute equivalent matrix and the decisional attribute ones into one matrix, it can considerably reduce the number of comparison in the process of matrix forming, which can effectively increase the efficiency of algorithm. The complexity analysis and experiment results show that the algorithm is much better than existing matrix algorithms.     

基于粗糙逻辑的增量式属性约简算法

知识约简、决策规则的获取是粗糙集理论研究的核心内容。以粗糙逻辑为基础，首先给出了在新实例加入论域后判断约简变化与否以及判断原极小决策算法中决策规则变化与否的判定依据。在此基础上，提出了一种增量式属性约简算法。该算法能有效地减少计算属性约简与极小决策算法的计算量，提高了计算效率。     

GIS分析与互信息属性约简的停车库选址决策

为了使城区立体车库的选址更加合理,充分发挥其建成后对交通缓解的作用,提出了一种城区立体停车库选址决策方法.通过采用地理信息系统分析方法,建立基于地理信息系统分析的规划选址立体车库属性信息数据,运用模糊粗糙集互信息属性约简算法挖掘出立体车库的选址与多种地理因素的关系知识进行属性约简,从而用地理信息分析和演绎推理相结合的归纳学习算法生成决策树和决策规则进行选址决策的评价及分析.对兰州市规划中的立体停车库选址建模仿真,仿真结果表明该方法能较好地运用在待求解问题中,从而为智能交通系统提供参考依据.     

信息系统的属性约简

粗糙集理论是一种新的处理模糊和不确定知识的数学工具 .属性约简是粗糙集理论研究中的重要内容之一 ,现已证明寻找信息系统的最小约简是 NP-hard问题 .本文提出一个基于信息量的属性约简的启发式算法 ,该算法的时间复杂性为 $O( | A|^3 | U| ^2 )$ .通过例子分析 ,表明该算法是有效的.     

基于遗传算法的不完备信息系统属性约简方法

提出了一种基于遗传算法的属性相对约简算法。通过在不完备信息系统中引入决策属性支持度的概念,来描述由条件属性所提供的知识对整体决策的支持程度,以此作为启发式信息求出相对核,并将相对核加入遗传算法的初始种群中以加快算法的收敛。同时,在适应值函数中引入惩罚函数,可以保证所求约简既含较少的属性又有较强的支持度,能够获得最佳的搜索效果。该算法通过实例分析,证明是求解属性约简问题的快速有效方法。     

粗糙集中属性约简的一个贪心算法

利用单属性的逼近精度、由决策属性定义划分的粗糙逼近精度以及它们的均值和方差 ,给出了属性重要性程度的一种度量方式。在此基础上 ,提出了粗糙集中属性约简的一个贪心算法 ,将各属性按照重要性由大到小依次加入到约简属性集中 ,直到满足约简条件为止 ,其特点是简单、容易实现 ,在条件属性较多的情况下 ,往往能够迅速求得一个属性约简。     

Cooperative extended rough attribute reduction algorithm based on improved PSO

Particle swarm optimization (PSO) is a new heuristic algorithm which has been applied to many optimization problems successfully. Attribute reduction is a key studying point of the rough set theory, and it has been proven that computing minimal reduction of decision tables is a non-derterministic polynomial (NP)-hard problem. A new cooperative extended attribute reduction algorithm named Co-PSAR based on improved PSO is proposed, in which the cooperative evolutionary strategy with suitable fitness functions is involved to learn a good hypothesis for accelerating the optimization of searching minimal attribute reduction. Experiments on Benchmark functions and University of California, Irvine (UCI) data sets, compared with other algorithms, verify the superiority of the Co-PSAR algorithm in terms of the convergence speed, efficiency and accuracy for the attribute reduction.