基于区分对象对集的高效属性约简算法

给出区分对象对集的定义和基于区分对象对集的属性约简的定义,证明该定义与基于正区域的属性约简定义等价.由于求区分对象对集时,要求出U/C,故设计一个高效的求U/C的算法,其时间复杂度降为O(| C | | U |).进而提出一个基于区分对象对集的高效属性约简算法,其时间和空间复杂度分别降为O(|C| | U |)+O(| C| | U/C|2)和O(| U |)+O(| U/C |2).用1实例说明该算法的高效性.     

基于简化的二进制差别矩阵的快速属性约简算法

目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义，证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中，要先求出IND（C），故设计了一个较好的求IND（C）的算法，其复杂度被降低为O（｜U‖U｜）。在此基础上设计了一个快速属性约简算法，其时间复杂度和空间复杂度分别被降为max{O（｜C｜^2（｜U＇pos‖U/C｜））,O（｜C‖U｜）}和max{O｜U｜},O（｜C｜（｜U＇pos‖U/C｜））}。     

基于简化差别矩阵的完备属性约简算法

由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出IND(C),故设计了一个较好的求IND(C)的算法,其复杂度被降为O(｜C‖U｜)。在此基础上设计了一个完备属性约简算法,其时间复杂度和空间复杂度分别被降为max｛O(｜C｜2(｜U′pos‖U/C｜)),O(｜C‖U｜)｝和max｛O(｜U｜),O(｜C｜(｜U′pos‖U/C｜))｝。     

Apriori算法的三种优化方法

通过对Apriori算法的思想和性能的分析,认为Apriori算法存在以下三点不足:(1)由K阶频繁集生成K+1阶候选频繁集时,在K+1阶候选频繁集中过滤掉非频繁集的策略值得进一步改进;(2)连接程序中相同的项目重复比较太多,因而其效率值得进一步改进;(3)在回扫数据库时有许多不必比较的项目或事务重复比较。根据上述三点不足,提出了相应的三种优化策略来优化Apriori算法,得到一效率较高的改进Apriori算法。     

基于区分对象对集的不完备决策表求核算法

在不完备决策表中对求核算法的研究较少,且时间复杂度都相对较高.为此,根据不完备决策表中差别矩阵及其核的定义,给出条件属性的区分对象对集的定义,并得出其与决策表核属性的关系,从理论上证明求解不完备决策表的核可以转化到求条件属性的区分对象对集上.结合不完备决策表差别矩阵核的性质,提出一种基于区分对象对集的不完备决策表求核算法.实验结果表明,该算法的时间复杂度优于同类算法的时间复杂度.     

Vague集之间的相似度量

分析了Chen给出的一种度量Vague集(值)之间相似程度的度量方法,指出了这种相似度量方法所存在的缺陷.在此基础上,给出了一种新的相似度量方法.由于该方法具有较好的性质,更具合理性,因而是一种较为理想的检测Vague集(值)之间相似程度的度量方法.     

基于分段线性插值的规则库缩减方法

分析了Koczy和Hirota提出的规则库缩减原理,提出了一种新的采用论域分区并用分段线性插值迭代来实现缩减规则库的方法。通过同一个实例的缩减比较,表明我们的算法的计算复杂性要小得多。     

基于数据库技术的属性约简算法

为弥补传统属性约简模型的不足,一些学者提出了基于系统熵的属性约简和基于数据库模型的属性约简定义.基于数据库模型的属性约简的主要优点是能结合高效的数据库技术,使得相应的属性约简算法效率较高.为能利用高效的数据库技术来设计基于系统熵的属性约简算法,证明了两种属性约简的等价性.然后利用数据库中的相关操作设计了一个基于系统熵的高效属性约简算法,并用实例说明了新算法.     

一种快速计算HU差别矩阵的属性约简算法

在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度, 首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.     

一种新的信息系统启发式属性约简算法

为降低信息系统属性约简算法的时间复杂度,首先引入简化信息系统的概念,然后定义了简化信息系统中属性集的区分对象数,证明了基于简化信息系统区分对象数的属性约简与原属性约简是等价的.进而定义了简化信息系统的属性重要性,并设计了一个快速求属性重要性的算法.同时,以属性重要性为启发式信息,设计了一个新的属性约简算法.新算法的时间复杂度降为max{O(|C||U|),O(|C|2|U|C|)}.最后用一个实例说明了新算法的有效性.