基于改进差别信息树的粗糙集属性约简算法

差别矩阵为属性约简提供了很好的思路,差别信息树能有效消除差别矩阵中的冗余元素,并实现对差别矩阵的压缩存储.然而,差别信息树既没有考虑“核”属性在消除差别矩阵中冗余元素的作用,也没有考虑属性序在压缩存储差别矩阵中非空元素的作用.对此,基于“核”属性和属性序关系,提出改进差别信息树,该树能进一步实现对差别矩阵中非空元素的压缩存储.最后,给出基于UCI数据库的仿真结果,并通过仿真结果验证该树的有效性.     

差别矩阵约简表示及其快速算法实现

差别矩阵可以拥有不同的信息, 根据差别矩阵描述的区分信息量不同, 给出4 种差别矩阵定义, 并提出相应H-约简、S-约简、B-约简和P-约简的概念; 研究4 种约简之间的关系, 构建通用约简算法模型. 为了提高约简算法的效率, 给出相对分辨能力约简定义(RD-约简), 揭示相对分辨能力约简与4 种差别矩阵约简之间的等价性, 进而设计相对分辨能力快速约简算法. 最后, 通过实例和UCI 数据集验证了所提出约简算法的有效性和时空性能.

     

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

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

信息观下基于不一致邻域矩阵的属性约简

信息观下研究邻域决策系统的属性约简是一种新颖的思路. 通过分析论域下某样本邻域中其他样本与该样本决策属性值的异同, 定义不一致邻域矩阵. 在计算属性重要度时, 利用不一致邻域减少在原条件属性基础上增加一个属性后条件熵的计算时间. 分析得到邻域系统下条件熵与正域的关系, 提出一种信息观下基于不一致邻域矩阵的属性约简算法, 并分析该算法与其他算法的内在联系. 实验结果验证了所提出算法的有效性.

     

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

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

基于信息观差别矩阵的属性约简算法

提出一种信息观下的差别矩阵,并基于该矩阵设计了一种信息观下决策表的属性约简算法,该算法以信息观下属性核为起点,通过计算信息观下差别矩阵中各属性出现的频率确定属性的重要度,进而根据各个属性的重要度来计算属性约简。实验结果表明,该算法可以求出更有效的信息观下属性约简,且计算约简耗时更少。     

基于差别矩阵的约简树构造方法

针对差别矩阵求约简过程中合取范式向析取范式等价转换的难题,提出一种基于差别矩阵构造约简树的有效方法。首先优化改进差别矩阵得到差别集,然后设计约简树描述约简获取的具体过程,最终所得约简树根节点到叶节点的每条路径即对应一个约简。该方法减少了生成和存储差别矩阵的时空开销,简化了获取决策系统全部约简的过程。     

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

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

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

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

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

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

     

基于有序差别集的高效属性约简算法

基于可分辨矩阵的属性约简算法需要占用大量的存储空间,可分辨矩阵中许多元素项对约简是多余的;并且随着问题规模的增大,该类算法的效率并不理想。针对上述不足,提出一种基于有序差别集的属性约简算法,该算法不需要创建可分辨矩阵和生成多余的元素项,大大降低了存储量和计算量,从而提高了属性约简效率,使算法的时间复杂度和空间复杂度分别降为max{O（|C|² |U/C|²）,O（|C|²|MsCount|）}和O（|MsCount|）。实验表明该算法是有效的、高效的。     

基于可辨识矩阵的快速粗糙集属性约简算法

Karno Bozi提出的Core Searching算法在向约简中插入候选属性的时候,根据属性出现次数需要循环查找可辨识矩阵中的所有剩余项,直至矩阵为空,导致计算量较大和结果中冗余属性存在的可能.基于Core Searching算法提出通过给属性设立计数器的基于可辨识矩阵的快速属性约简算法,实例分析表明,该算法与Core Searching算法相比,在计算量减少和循环次数减少的同时能得到更简约的结果,是一种快速、高效的属性约简算法.     

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

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

垂直划分二进制可分辨矩阵的属性约简

针对二进制可分辨矩阵属性约简方法在处理大数据集时的不足,首先给出两种二进制可分辨矩阵属性约简的定义,并证明这两个属性约简定义与正区域的属性约简定义是等价的;然后,给出对二进制可分辨矩阵按条件属性垂直划分后进行属性约简的方法;为了进一步降低空间开销,提出将垂直分解的二进制可分辨矩阵存于外部介质中,在约简过程中,仅将所需部分调入内存,由此设计启发式属性约简算法,其时间和空间复杂度的上界分别为 (∣ ∣∣ ∣2)和 (∣ ∣2);最后,理论分析和实验结果验证了该算法的正确性和高效性.     

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

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

采用布尔矩阵不完备信息系统的属性约简

对于不完备信息系统完备化问题,现在常采用的方法是数据补齐法和扩充法,在研究和分析了其优劣后,提出一种完全依据信息系统提供的信息来产生布尔可辨矩阵的方法。给出一个基于对布尔可辨矩阵进行化简的求属性约简（或最小属性约简）的高效算法。     

基于信息熵的粗糙集属性约简及其应用

粗集约简对噪声非常敏感,因此寻求噪声干扰下,属性间的准确关系和不确定性关系的表达显得十分重要。将粗糙集理论与信息论理论结合起来,发挥各自优势,取长补短,提出了一种改进的属性约简算法,且在此基础上进行了值约简并应用于超大型船舶的旋回性分析。给出了各因素之间的依赖关系,增比特征,及规则分析。取得了很好效果,对船舶操纵和技术研究有良好的实用价值。     

基于幂图的属性约简

针对粗糙集理论中基于差别矩阵的属性约简方法存在的不足,提出一种基于幂图的属性约简算法.首先通过修改样本决策属性值将不相容决策表转化为简化的相容决策表;然后将样本对概念与幂图概念相结合,将基于修正差别矩阵的不相容决策表的属性约简转化为幂图的搜索问题;最后通过实例和实验验证了所提出算法的有效性.     

区分对象对集的不完备决策表属性约简

通过利用粗糙集中差别矩阵的思想,引入不完备决策表的区分对象对集的概念。并给出不完备决策表基于区分对象对集的属性约简定义。同时,也证明了利用该定义得到的不完备决策表的属性约简与基于正区域的属性约简是等价的。相比较基于正区域的不完备决策表属性约简算法,基于区分对象对集的属性约简算法时间复杂度是降低的。最后,用一个实例说明了该算法的合理性。