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

为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|)。其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O|C|2Σ0≤i相似文献   

基于改进差别矩阵的属性约简增量式更新算法

针对目前基于差别矩阵的属性约简算法需要耗费大量的时间和空间,粗糙集中求属性核和属性约简更新效率低以及有关属性约简的增量式更新算法目前还比较少等问题,提出了一种基于改进差别矩阵的属性约简增量式更新算法.该算法在更新差别矩阵时,仅须插入某一行及某一列,或删除某一行并修改相应的列,因而可有效地提高核和属性约简的更新效率.然后在分析新增对象x与原决策系统对象的关系的基础上,给出了属性约简增量更新算法.理论与实验分析表明,提出的算法提高了属性约简的更新效率,明显降低了时间和空间复杂度.     

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

为获取一个较优的属性约简集,在对粗糙集中基于差别矩阵的属性约简算法研究的基础上,文中提出了一种新的属性约简算法.该算法对由差别矩阵得到的属性差别集进行运算,得到一种集合内元素之间没有包含关系的新集合,在分析该集合性质的基础上,给出针对该集合的一个较优属性约简集.最后对时间复杂度进行了分析,并给出了完备性证明.     

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

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

基于差别矩阵的动态约简及规则提取算法

属性约简与规则提取是粗集研究的重要内容。该文在分析基于差别矩阵的约简及规则提取算法的基础上提出了一种改进算法,提高了规则的挖掘效率,获得了更简单的规则集,并通过实例证明了该算法的有效性、实用性。     

一种基于差别矩阵的启发式属性约简算法

为了获得决策系统中更好的相对属性约简,本文提出了一种基于差别矩阵的启发式属性约简算法。该算法以求差别矩阵为基础,不仅考虑了所选择条件属性与决策属性的互信 息,还考虑了其取值的分布情况,从信息论角度定义了一种新的属性重要性度量方法,将其作为启发式信息,最终求得属性约简集。实例表明,算法能够有效地对决策系统进进行约简,获得比较理想的约简结果,同时约简后的决策规则数目较少。     

基于差别矩阵的属性约简算法及其应用

铝电解过程中存在着各种相互影响的工艺参数,如何从中选择一部分参数进行分析,对铝电解生产有着重要的意义。提出了一种改进的基于差别矩阵的属性约简算法,避免了普通差别矩阵中的重复元素。用真实的铝电解生产数据对提出的算法进行了验证,效果良好。     

一种基于改进差别矩阵的核增量式更新算法

提出一种基于改进差别矩阵的核增量式更新算法,主要考虑对象动态增加情况下核的更新问题．该算法在更新差别矩阵时仅须插入某一行及某一列,或删除某一行并修改相应的列,因而可有效地提高核的更新效率．理论分析和实验结果表明,该算法是有效可行的．     

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

为获取一个较优的属性约简集,在对粗糙集中基于差别矩阵的属性约简算法研究的基础上,文中提出了一种新的属性约简算法.该算法对由差别矩阵得到的属性差别集进行运算,得到一种集合内元素之间没有包含关系的新集合,在分析该集合性质的基础上,给出针对该集合的一个较优属性约简集.最后对时间复杂度进行了分析,并给出了完备性证明.     

一种基于改进差别矩阵的属性约简增量式更新算法

粗糙集方法提供了一种新的处理不精确、不完全与不相容知识的数学工具.属性约简是粗糙集理论的重要研究内容之一,已有的大多数属性约简算法主要考虑信息系统(或决策表)不变的情况,有关属性约简的增量式更新算法却报道不多.为此,文中提出一种基于改进差别矩阵的属性约简增量式更新算法,主要考虑对象动态增加情况下属性约简的更新问题.该算法可通过快速更新差别矩阵,在动态求解核的基础上,利用原有的属性约简有效地进行属性约简的增量式更新,因而可提高属性约简的更新效率.理论分析表明,该文提出的算法是有效可行的.     

基于优化可辨识矩阵和改进差别信息树的属性约简算法

运用可辨识矩阵表示信息系统中所有对象的区分信息,为研究属性约简提供了新方向。然而,传统的可辨识矩阵在构造结束后才利用核属性消除冗余元素项,忽略了核属性在矩阵构建过程中的作用。针对这一问题,文中做了以下研究:1)优化可辨识矩阵的构造方式,在计算任意两个对象的区分信息之前,先判断核属性上的取值是否相等,如果不相等,则直接将对应元素项记为Φ,忽略对其他条件属性的判断;2)提出属性加权重要度的概念,综合考虑每个条件属性占可辨识矩阵中非空元素项的比率(称为宏观重要度)与每个属性对区分对象的贡献程度(称为微观重要度),并通过例子说明了该度量方法的合理性;3)针对优化后的矩阵仍然存在大量冗余元素和空集这一缺陷,结合差别信息树的概念提出基于优化可辨识矩阵和属性加权重要度的差别信息树。按照属性加权重要度对优化可辨识矩阵中所有非空元素项进行排序,使得重要度高的属性被更多的节点共享;且在构建过程中将不包含核属性的元素项映射到树中的一条路径上,而包含核属性的元素项则被直接忽略。最后,提出基于优化可辨识矩阵和改进差别信息树的约简算法HSDI-tree。在UCI的5个数据集上分别比较了HSDI-tree算法与CDI-tree,DI-tree和IDI-tree算法的约简结果和节点个数,实验结果表明HSDI-tree算法能有效找到最小属性约简且空间压缩能力更好。     

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

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

一种基于属性重要性的变精度粗糙集属性约简算法

结合胡可云算法中对属性重要性的描述,以条件属性在可辩识矩阵中出现的频率作为启发信息,提出一种基于变精度粗糙集模型的属性约简算法.实验证明,该方法能够有效地对决策表进行属性约简,并具有一定的抗噪声能力.     

基于辨识矩阵的不完备多粒度约简

面向具有缺失属性值的不完备数据,文中从辨识矩阵的角度构造不完备信息系统和不完备决策系统的多粒度约简结构.首先,讨论基于悲观和乐观多粒度近似的不完备信息系统的约简性质,构造不完备信息系统和不完备决策系统的3种多粒度辨识矩阵.然后,理论性证明通过对构造的辨识矩阵进行析取、合取逻辑运算,可精确得到不完备信息系统和不完备决策系统的所有多粒度近似约简.最后通过实例验证文中多粒度约简方法的有效性和实用性.     

基于可辨识矩阵的启发式属性约简方法及其应用

在基于可辨识矩阵的属性约简算法的基础上，提出了基于可辨识矩阵的计算属性重要性的方法，并以此作为启发式知识来约简决策表中的冗余属性。这种方法直接源于评审数据，思路清晰，拟合结果表明本约简算法合理、可靠。     

基于关系数据库的粗糙集约简改进算法

以粗糙集约简和关系数据库为研究对象,提出了一种带有数据预处理和新启发式信息值的粗糙集约简改进算法.通过应用了该改进算法的DBRuduct工具进行实验,实验数据表明决策表的对象个数和约简计算时间之间成近似线性的关系;以Rosetta中的遗传算法求得的约简作为实验参照,该算法不但可以在含有不一致数据的情况下获得正确的核属性,而且还使约简算法求得的约简更加趋向于最小约简.     

云计算环境下差别矩阵知识约简算法研究

知识约简是粗糙集理论的重要研究内容之一。经典的差别矩阵知识约简算法只能处理小数据集,而已有的任务并行的知识约简算法是假设所有数据一次性装入内存中,这显然不适合处理海量数据。为此,剖析了差别矩阵元素的特性,根据属性(集)的不可辨识性和云计算技术MapRcducc设计了适合数据并行的差别矩阵,并首次提出了面向大规模数据的差别矩阵知识约简算法。实验结果表明该知识约简算法是有效可行的,且具有较好的可扩展性。     

广义约简、核与分辨矩阵

针对粗糙集理论中计算决策表核属性时出现的若干问题,讨论并分析了这些问题产生的原因.在此基础上,给出了不同目标下的广义约简定义,提出了必要区分关系和非必要区分关系等概念,由此给出了一般意义下的分辨矩阵定义.根据广义约简的定义,将已有的改进差别矩阵求核方法与早期Skowron等人提出的经典分辨矩阵求核方法作了对比,证明了两种方法完全相I司.