基于相容矩阵的改进属性约简算法

原属性约简算法在计算相容关系时,存在大量重复计算,从而导致时间复杂度为O(|C|3|U|2)。针对该问题,基于不完备决策表,提出时间复杂度为O(|U|2)的高效相容矩阵计算算法,在此基础上,设计改进的基于相容矩阵的属性约简算法。通过实例证明,当空间复杂度相同时,改进算法的时间复杂度从原有O(|C|3|U|2)降为O(|C|2|U|2)。     

基于分辨矩阵和属性重要度的规则提取算法

研究了Rough集理论中的属性约简和值约简问题,将分辨矩阵引入值约简中,从属性依赖度的角度重新定义了属性重要度,提出了基于分辨矩阵和属性重要度的分类规则提取算法。该算法在保持分类能力不变的前提下,得到最小属性约简,再经过值约简后得到精确的规则,与现有算法相比,能减少时间和空间耗费。实验结果验证了该算法的有效性。     

基于属性重要度的风险决策粗糙集属性约简

基于Pawlak 粗糙集的属性约简一般保持决策表的正区域不变, 然而由于现实中不同用户对不同约简精度的需求, 获取属性值的实际代价与个人偏好可能不同. 针对决策者主观个人偏好、客观约简精度、获取属性值的实际代价和决策表各区域的误判代价等综合情况, 提出新的约简算法, 并讨论约简代价与约简精度间的关系. 通过遗传算法, 采用启发式方法搜索出局部最优约简子集. 仿真实验表明, 所提出的算法操作性强, 更适合处理实际决策问题.

     

基于邻域组合测度的属性约简方法

属性约简是机器学习和知识发现的研究热点, 而属性重要性度量则是构建属性约简算法的关键环节. 针对不完备的混合型信息系统, 在邻域关系下定义了一种新的属性集成重要性度量—–邻域组合测度, 并据此提出一种基于邻域组合测度的属性约简(NCMAR) 算法. 通过多个UCI 数据集上的实验表明, NCMAR算法不仅能够直接处理符号和数值属性共存的混合信息系统, 而且适用于不完备信息系统, 在获得较小约简结果的同时, 能够保证较高的分类精度.

     

相容矩阵的高效属性约简算法

给出完备决策表和不完备决策表的定义并说明相容关系.给出了相容矩阵及其属性约简的定义,同时也给出差别矩阵及其属性约简的定义,证明了基于相容矩阵的属性约简与关于差别矩阵的属性约简定义是等价的,给出了一个计算条件属性的频率的公式,该公式不必计算差别矩阵,而是直接从决策表中计算出各条件属性在差别矩阵中出现的频率.设计一个快速计算条件属性频率的快速算法,在此基础上,设计了一个高效求基于相容矩阵的属性约简算法,并通过实例对该算法进行了验证.实践证明:算法的复杂度都得以降低,该算法的时间复杂度为O(|C|2|U|),空间复杂度为O(|U|).该方法为计算其他的属性约简算法提供了一条新思路.     

基于数据相容填补的极大相容块构造算法

极大相容块技术在不完备信息处理方面具有一定优势,但极大相容块获取本身是个耗时的过程。通过分析不完备信息系统中极大相容块的性质特点,给出极大相容块中不完备数据的相容填补方法;在不完备信息系统中使用相容填补方法,得到一种新的极大相容块构造算法;基于构造算法的特点,引入决策树存储结构对算法进行优化。使用标准的数据集验证了构造算法的有效性。实验结果表明,构造算法在较大规模的数据集上有较好的性能。     

变精度极大相容块粗糙集模型及其属性约简

主要研究不完备信息系统的属性约简问题。首先基于极大相容块构造乐观和悲观两种广义变精度粗糙集模型,分析两种模型之间的关系并研究其主要性质。在此基础上,定义乐观(悲观)β-下分布约简和β-上分布约简并且给出相应的判定定理,进而得到一种保持决策类上(下)近似分布不变的属性约简方法--布尔计算方法。这种构造极大相容块间的辨识矩阵的方法缩小了矩阵的规模,进而简化了计算属性约简的过程,从而能够有效地节省计算时间和存储空间。然后对含有"丢失""不关心"值和只有"不关心"值的两种不完备信息系统进行实例分析,最后从UCI数据集中选取5组不完备信息数据集来验证方法的有效性。     

基于差别信息树的rough set 属性约简算法

差别矩阵为粗糙集属性约简提供了很好的思路, 但差别矩阵中存在冗余的重复和父集元素. 为了消除这些冗余元素, 提出一棵有序树: 差别信息树, 该树能消除差别矩阵中的重复元素, 同时在大多数情况下也能完全消除父集元素, 实现对差别矩阵中非空元素的压缩存储. 为了验证差别信息树的有效性, 提出一种属性约简完备算法, 并使该算法的时间复杂度降为??(∣??∣∣??∣²).

     

改进的相容矩阵的属性约简算法

在粗糙集理论中,知识约简已经成为其核心内容之一。针对相关文献中基于相容矩阵的不完备信息系统属性约简算法,提出了一种新的相容矩阵定义,该矩阵能够减少关注的条件属性。同时,也证明利用该矩阵所求的属性约简与相关文献中的属性约简是等价的。给出了其属性约简算法,提高了属性约简的速度。     

改进的不完备决策表最优规则提取方法

不完备信息系统中的规则提取是粗糙集理论研究的关键问题之一。针对不完备决策表,通过引入广义决策函数,提出了一种不完备决策表的最优规则提取方法。实验结果表明该算法具有良好的求解能力,所获得的决策规则简洁,与缺省值无关。     

基于改进的二进制分辨矩阵属性约简算法

属性约简是粗糙集理论的重要研究内容之一,目前已有许多属性约简算法。但这些算法中主要针对一致决策表,当决策表是不相容的情况下,常用的计算全部属性约简的差别矩阵算法会产生错误的结果。为了解决这个问题,引入了一个改进的二进制分辨矩阵,提出了一种基于改进的二进制分辨矩阵的属性约简算法。并利用上述算法结合实例进行属性约简,证明了算法的正确性和有效性。     

基于二进制可辨矩阵的决策规则约简算法

决策规则的约简是利用决策逻辑分别消去每一条决策规则中的冗余属性值,是粗糙集理论知识约简的重要内容,一般是在属性约简之后采用启发式信息实现决策规则的约简。基于二进制可辨矩阵给出一个简单的直接求取决策规则核的方法,并提出一种决策规则的约简算法。所给算法简单直观,不但适用于相容决策表,也适用于不相容的决策表。     

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

为了解决基于差别矩阵属性约简的计算效率问题,分析了基于差别矩阵的属性约简算法的不足,给出了新的差别矩阵的定义,大大减少了差别矩阵中非空元素的个数,提高了属性约简算法的效率。利用单个属性的不可辨识性来计算出现频率最多的属性,进一步降低差别矩阵的大小,并设计了基于新的差别矩阵的快速属性约简算法。对UCI一些数据库进行了仿真,实验结果表明了新算法具有高效性。     

一种基于改进区分矩阵的属性约简算法

现有的很多约简算法都是由构造决策表的区分矩阵出发,将矩阵中非空元素的合取范式转化为极小析取范式。但是,基于Skowron提出的区分矩阵约简算法对不相容决策表会产生错误的结果。为此,提出一种改进的区分矩阵的定义,以及基于此区分矩阵的属性约简算法,该算法对相容或不相容决策表都是适用的,特别对不相容决策表会得到更加稀疏的区分矩阵,可大大节省计算时间和存储空间,该算法是一种简单、有效、普遍适用的求解属性约简方法。     

序决策信息系统中区间决策规则的获取

在序决策信息系统中, 定义区间为支配一个特定的对象同时又被另一个特定的对象所支配的所有对象的集合. 以区间为基本知识颗粒, 建立新的优势关系粗糙集模型, 并由此获取决策值为特定区间范围的区间决策规则. 提出区间的约简的概念, 构造区分函数计算区间的约简, 并由此计算优化区间决策规则. 该方法比初始的优势关系粗糙集方法适应性更强, 且所得区间决策规则可直接应用于序信息系统的分类问题.

     

基于分明矩阵的属性约简启发式算法

提出了基于分明矩阵的启发式知识约简算法.该算法以分明矩阵中属性出现的频率作为启发信息,通过构造新的决策表,每次选取出现个数最多的属性,直到选取的属性能够保持原决策表的分类能力,此时得到的集合即是一个约简.试验结果表明,该算法在大多数情况下都能够找到最小约简或令人满意的次优解.     

一种不完备决策表的差别矩阵求核算法

计算不完备决策表的核属性是粗糙集理论的重要内容之一。目前关于不完备决策表的求核算法的研究相对较少,而且在一般的求核算法中,其时间复杂度为[O(|C||U|2)]。为了有效地降低算法的时间复杂度,给出了一个不完备决策表的差别矩阵定义和基于差别矩阵的核定义,并证明了该定义与基于不完备决策表的核定义是等价的。在此基础上,利用差别矩阵方法来设计一种计算不完备决策表的求核算法,其时间复杂度降为[O(|C||Upos||U|)]。最后用仿真实例说明了新算法的有效性。     

一种基于C-Tree的属性约简增量式更新算法

针对以往文献为克服基于差别矩阵的属性约简算法存储代价高的不足而提出的基于浓缩树(C-Tree)的高效属性约简算法仅考虑决策表不变的情况,提出了一种基于C-Tree的属性约简增量式更新算法,主要考虑对象动态增加情况下属性约简的更新问题.该算法可通过快速更新C-Tree,在动态求解核的基础上,利用原有的属性约简有效地进行属性约简的增量式更新.理论分析和实验结果表明,所提出的算法是有效可行的.