区间值决策表的正域增量式属性约简算法

实际应用中存在大量动态增加的区间型数据，若采用传统的非增量正域属性约简方法进行约简，则需要对更新后的区间值数据集的正域约简进行重新计算，导致属性约简的计算效率大大降低。针对上述问题，提出区间值决策表的正域增量属性约简方法。首先，给出区间值决策表正域约简的相关概念；然后，讨论并证明单增量和组增量的正域更新机制，提出区间值决策表的正域单增量和组增量属性约简算法；最后，通过8组UCI数据集进行实验。当8组数据集的数据量由60%增加至100%时，传统非增量属性约简算法在8组数据集中的约简耗时分别为36.59 s、72.35 s、69.83 s、154.29 s、80.66 s、1498.11 s、4124.14 s和809.65 s，单增量属性约简算法的约简耗时分别为19.05 s、46.54 s、26.98 s、26.12 s、34.02 s、1270.87 s、1598.78 s和408.65 s，组增量属性约简算法的约简耗时分别为6.39 s、15.66 s、3.44 s、15.06 s、8.02 s、167.12 s、180.88 s和61.04 s。实验结果表明，提出的区间值决策表的正域增量式属性约简算法具有高效性。     

一种基于压缩矩阵的Apriori算法改进研究

针对已有基于矩阵的Apriori算法存在的问题,提出了一种改进的基于压缩矩阵的Apriori算法。算法进行了以下方面的改进:增加了两个数组,分别用于记录矩阵行与列中1的个数,使得算法在压缩矩阵时减少了扫描矩阵的次数;在压缩矩阵中,通过增加删除不能连接的项集和非频繁的项集的操作,使得矩阵压缩得更小,提高了空间效率;改变了删除事务列的条件和算法结束的条件,以减少挖掘结果的误差和算法循环的次数。算法性能分析和实验分析证明,改进后的算法能有效地挖掘频繁项集,并且比现有的算法具有更高的计算效率。     

基于差别矩阵启发式决策表属性约简算法

属性约简是粗糙集理论研究的核心内容之一,足知识获取的关键步骤.针对大规模数据集,基于决策表差别矩阵属性约简不具备可操作性缺点;以及基于差别矩阵属性频度的约简算法没有考虑到差别矩阵元素中属性个数多少的缺陷.基于差别矩阵元素的基数越小,其属性越重要的思想,按照基数由小到大的顺序,利用矩阵中具有相同基数的矩阵元素的簇集中属性出现的频度,确定属性的重要度,提出一种快速搜索属性约简算法,能快速搜索到属性的最优或次优约简.实验结果表明算法是可行、有效的.     

一种基于分布数据的正域属性约简算法

由于计算机网络及存储技术的迅猛提高,分布数据处理已经涉及很多领域,如何有效挖掘分布数据的相关知识是人工智能领域研究的一个热点。本文我们首先介绍了如何计算分布数据的等价关系及诱导矩阵的方法,设计了一种基于分布数据的约简算法,然后,给出一些例子来解释计算分布数据的正域的过程,最后,在机器学习网站下载了3个UCI数据集并进行了大量的实验,实验结果表明了该算法能够有效解决分布数据约简问题。     

一种改进的属性约简算法

粗糙集理论是一种有效的信息处理工具,属性约简是粗糙集理论研究的一个核心内容。为了能够较为有效地获得不相容决策表较优的属性约简,在对文献[7]中属性约简算法分析的基础上,根据不相容决策表约简不改变决策表正域的原则,仅考虑相对差异比较表中与正域相关的实例对,同时结合属性重要性作为特征选取的启发式信息,提出了一种改进的启发式属性约简算法。该算法在不增加算法时间复杂度的前提下能够处理不相容决策表。最后,通过实例完整演示了该方法,表明该算法是有效的。     

一种基于GPU的并行算法功耗评估方法

随着软件和硬件的不断发展,图形处理器(GPUs)已经广泛用于通用计算领域,并作为加速器来协助CPU加速程序的运行。为了追求高性能,GPU往往包含成百上千个核心运算单元,高密度的计算资源使其在性能远高于CPU的同时功耗也高于CPU,因此功耗问题已经成为制约GPU发展的重要问题之一。分析了并行程序在GPU上运行时消耗的功耗,提出了并行算法在GPU上运行的功耗评估方法,接着通过并行前缀求和算法对该方法进行了详细的论述与分析。在实验部分通过稀疏矩阵向量乘算法的实际应用对该方法的正确性以及敏感性进行了证明与分析。结果表明,对于给定的程序,在满足性能要求的前提下,最优线程块数、存储访问方式以及任务分配顺序是影响系统功耗的关键因素。     

一种基于决策表的快速属性约简矩阵算法

针对目前基于决策表的属性约简矩阵算法效率不理想的情况,首先引入了简化决策表的概念,有效剔除了决策表中大量重复冗余的对象,并给出了正区域模型下简化矩阵的构造,从而有效地缩小了求解属性约简的搜索空间;然后从理论上详细分析了基于简化矩阵的属性约简与基于正区域的属性约简是一致的,并给出了一种有效的属性重要性度量方法.为此,在简化矩阵的基础上设出了一种快速的属性约简矩阵算法,最后通过实例分析和实验对比说明了算法的有效性和可行性.     

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

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

不完全决策表的一种信息熵属性约简算法

属性约简是粗糙集理论的核心问题之一，也是粗糙集有效算法研究的焦点。为获得最简明的规则集，通常希望能找出最小的属性约简集，但得到最优解NP-hard的问题，通常采取启发式的算法得到近似最优解。文中研究了不完全决策表的属性约简，提出了对不完全决策表的一种基于信息熵的属性约简算法，并通过例子说明算法的具体过程和验证了算法的可行性。对寻找对象的相似类的步骤则在排序和二分查找的基础上提出了一种高效的算法，这样就相应地提高了属性约简算法的效率。     

决策强度的决策表约简设计与比较

在平均决策强度的基础上,提出了决策强度的代数定义,以弥补基于正区域方法的局限性,并且证明了知识的决策强度随着信息粒度变小而非单调递减的规律,在此基础上设计了基于决策强度的约简方法。应用实例分析的结果表明,基于决策强度的属性重要性是一种更优的启发式信息,该方法计算直观有效,时间复杂度较低,有助于搜索最优或次优约简。最后对UCI离散数据集进行约简比较。     

遗传算法在决策表最小约简中的应用

基于粗集理论和扩张矩阵理论,利用遗传算法,提出一种求解最小约简的优化方法,实验说明,此方法能以较大的概率全面获得决策表的最小约简,实用性较强。     

不完备决策表中基于对象矩阵属性约简算法

基于差别矩阵的属性约简是粗糙集属性约简中最常用的方法。对通常给出的以存储条件属性为基础差别矩阵进行比较后,给出一种对象矩阵的定义。对象矩阵从相容类内对象的决策值与条件属性的关系出发,存储的是对象集。给出对象矩阵的属性约简定义,证明了属性约简与基于正区域的属性约简的等价性。给出一个启发式的属性约简算法,其时间复杂度为max(O(|C|2|Upos||U|),O(|C||U|2)),空间复杂度为O(|C||U|2);通过实例说明方法的可行性。     

一种改进的基于正区域的决策树算法

首先分析了基于正区域、基于粗糙边界和基于依赖度的属性选择标准的关系,并证明了这三种属性选择标准彼此等价.然后以正区域的属性选择标准为代表,分析了、基于正区域的决策树生成算法的优点和不足.针对这些不足,给出了一种新的属性选择标准,即基于伴随正区域的属性选择标准.用新的属性选择标准生成的决策树一般具有叶子数目较少,叶子的平均深度也较小,且叶子具有较强的泛化能力.最后,用一实例说明了新的属性选择标准的优越性.     

基于云模型的决策表规则约简

通过对决策表的转换,将规则映射成为云向量,用云向量数字特征间的相似度来度量决策表规则间的等价关系.基于此,提出了基于云模型的决策表规则约简算法,不仅解决了粗集基于严格属性匹配的等价关系不能区分相似关系,也克服了基于模糊集等价关系依赖专家先验知识、对属性值随机性分布考虑不足的缺点.实验说明了该算法的高效性.     

基于模糊集的连续域决策表属性约简算法

把模糊集和粗糙集结合起来,对连续域决策表属性约简算法进行研究。使用三角隶属度函数将连续属性值转化为模糊值。定义两模糊对象间的相似度、模糊对象的相似类以及连续属性在对象集上划分所形成的相似类集组成的特征向量。给出连续型属性的数字特征向量,以此为基础建立连续型属性间的相似矩阵。提出一个新的属性约简算法,并用一个实例加以验证。     

基于改进分辨矩阵的属性约简方法

在分辨矩阵的属性约简算法的研究中,需比较决策系统中各对象生成矩阵元素,导致所得分辨矩阵过于庞大,且造成较大的时间开销.为降低利用分辨矩阵求取属性约简算法的复杂度,依据条件等价类将原决策系统分解为一相容对象集与一非相容对象集,给出条件相对于决策的可辨识关系定义与改进的分辨矩阵定义,将条件相对于决策的可辨识关系变化作为属性约简的判定标准,结果证明改进分辨矩阵的属性约简与保持正域不变的属性约简等价.推理证明与仿真实例说明,改进方法的高效性与完备性.     

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

在基于二进制分辨矩阵的属性约简方法中,删除法即从属性全集中依次删除冗余属性,直至剩余的属性集是一个最小约简.针对传统的基于二进制分辨矩阵的删除法效率较低且得不到最小约简的问题,提出一种改进的二进制分辨矩阵属性约简方法.首先对决策表进行简化,然后给出一种改进的简化二进制分辨矩阵方法;其次通过一个新的属性约简度量方法一次性删除多个属性,并从理论上分析了该方法的可行性;最后通过实验证明了得到的约简结果是最小约简.     

基于Rough集的决策表属性最小约简的整数规划算法

近年来随着知识发现和数据挖掘的广泛应用,在计算机科学中约简算法越来越得到人们的重视。该文依据决策信息系统中属性约简与逻辑运算的关系,提出了一种计算属性集最小约简的整数规划算法,并建议了相应快速的求解方法。该算法能有效地避免大量逻辑运算,在动态环境下更显示其优越性。实例验证了该算法的有效性。