基于粗糙集的属性约简算法综述

属性约简是粗糙集中的一个重要研究方向.本文从8个方面对基于粗糙集的属性约简算法进行归纳,即:不完备决策信息表,不相容决策信息表,连续型属性决策信息表,动态决策信息表,有序型属性决策信息表,基于粗糙扩展模型的属性约简,基于属性重要度的属性约简,结合智能优化算法的属性约简,这对进一步深入研究粗糙集的属性约简算法具有积极意义.     

一种基于粗糙集的纳税人属性约简方法．

基于粗糙集理论,对基于属性重要度的启发式属性约简算法进行了改进,并将改进后算法运用于纳税人属性约简的实际工作中.该算法解决了原有基于属性重要度的启发式属性约简算法结果中存在冗余属性问题,实现了属性选择较小化,并保持原有数据分类能力不发生大的变化.通过属性约简实验结果和实际工作情况对比,证明该算法具有很好的性能.     

基于粗集可辨识矩阵的属性频率约简算法

针对信息系统在属性约简过程中存在属性频率值相同的问题进行改进.改进后的算法在基于可辨识矩阵属性频率约简算法的基础上.引进强等价集概念,以属性在可辨识矩阵中出现的次数越多其重要性越大为启发式信息,利用强等价集中的属性是可以约简的特性,在属性频率约简过程中判断具有相同属性频率属性是否最终包含在核属性集里,提出改进的属性频率约简算法.通过理论和实例的分析证明,该算法在保持时间复杂度不变的情况下,处理具有相同属性频率信息系统的属性约简,使其准确性得到提高,与原算法相比,改进后的算法可以得到一个更为精准的约简结果.     

基于互信息下粒子群优化的属性约简算法

最小属性约简是粗糙集理论中属性约简的优化问题.在寻找最小属性约简的问题上,基于粒子群优化的属性约简算法（ARPSO算法）优于传统的属性约简算法.在现有的ARPSO算法中,正域部分通常被作为启发式信息,但是它并不能够很好地衡量不确定性,而互信息是粗糙集理论中一种更有效的度量不确定信息的重要工具.为此,提出基于互信息下的粒子群优化的属性约简算法（MIPSO算法）,该算法把互信息作为适应度函数,通过增强粒子能迅速靠近吸引子的这一特性,改进了内嵌区域震荡搜索的粒子群优化算法（简记为RSPSO算法）,防止算法较早的陷入局部最优,使得粒子群中的粒子更快的找到最优值,因此使得算法尽可能实现全局收敛.实验结果表明,该算法不仅提高了寻优的能力,加快了算法的速度,提升了算法的精度,而且也能够使得约简后剩余属性的互信息值与约简前所有属性的互信息值近似相等.     

基于分明矩阵的序贯属性约简算法

根据决策表信息系统的分明矩阵及序贯思想,提出了序贯属性约简算法,该算法首先构造递增序列的分明函数,然后利用逐次增加的属性核对分明函数进行分支运算,并建立属性约简树,从而求出所有约简.该算法避免了大量的逻辑运算,实现了高维数据的高效属性约简.理论分析和实验结果表明该算法具有更高的运行效率.     

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

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

一种基于知识粒度的决策系统属性约简算法

本文针对决策系统给出了一种新的知识粒度模型,并给出了知识粒度下的核属性定义和分析了知识粒度模型的属性约简与正区域模型的属性约简的等价性.在此基础上利用知识粒度的重要性作为启发式信息构造了决策系统的属性约简算法.算法能够快速获取决策系统的属性约简,算例分析进一步说明了算法的可靠性.     

混合数据的邻域区分度增量式属性约简算法

增量式属性约简是一种针对动态环境下的数据挖掘方法.目前已经提出的增量式属性约简算法仅适用于符号型的信息系统,而很少有对混合信息系统进行相关的研究,这促使在混合信息系统下构建相关的增量式属性约简算法.区分度是用于设计属性约简的一种重要方法,本文将传统的区分度在混合信息系统下进行推广,提出邻域区分度的概念,然后分别研究了邻域区分度在混合信息系统下对象增加和对象减少时的增量式学习,最后根据这种增量式学习分别提出了对应的增量式属性约简算法.UCI数据集上的相关实验结果表明,所提出的增量式属性约简比非增量式属性约简能够更快速的更新约简结果.     

一种基于粗糙集理论的双向选择属性约简算法

文章首先对粗糙集的基本理论进行了简要介绍,然后重点讨论粗糙集理论中的属性约简问题,在总结分析现有属性约简算法的基础上,提出了一种双向选择属性约简算法--BSARA,并用一个例子与其它算法进行了对比分析,结果表明该算法是可行和有效的.     

决策表中基于条件信息熵的近似约简

属性约简是粗糙集理论的重要研究内容,已有效应用于机器学习、数据挖掘等领域.基于条件信息熵的属性约简可有效推广代数观下的属性约简,但存在抗噪声弱且某些情况下冗余属性多的不足.为此,本文在引入决策表中基于条件信息熵的近似约简概念后,提出决策表中基于条件信息熵的近似约简算法,该算法可有效增强抗噪性,且可依据实际应用的需要有效地对冗余属性进行取舍.最后,本文侧重通过选择不同精度下的约简属性子集在Benchmark上进行了分类器的性能测试.     

最优化问题算法重用研究

为提高算法设计的效率以及缩小设计所需的时间,提出了算法重用的思想,即通过解决同一类型问题的算法框架来生成具体算法。并以N皇后问题的回溯算法为实例,介绍了算法设计过程。通过算法重用,文中可在解决这类问题的算法框架下,根据自身选择的实现函数,在框架下填充算法的具体细节,从而避免了算法设计的重复性工作,节省了设计所需的时间,提高了设计效率。     

基于遗传_蚁群算法的多QoS约束组播路由优化算法

提出了一种将遗传算法与蚁群算法融合的新算法,用以满足多QoS约束的组播路由优化。算法首先利用遗传算法生成若干组优化解,将其转换成蚁群算法的信息素初值,然后利用蚁群算法来求取满足QoS约束的最优解。仿真结果表明此算法是有效的,其性能优于文献[6]中算法。     

基于EGA与Alopex算法的非可微函数混合全局优化算法

遗传算法是一种全局化算法,能以较大概率搜索到全局最优解。本文将Alopex算子嵌入到保留最优个体遗传算法（EGA）中,对非可微或求导困难函数从而得到既能以较大概率搜索全局极值,又能进行局部细致搜索的混合全局优化算法;并对其全局收敛性和计算效率作了证明与分析。数值计算结果表明该算法优于求解函数优化的EGA和Alopex算法。     

改进的KFCM算法及其在感兴趣区域提取中的应用

基于核函数的FCM算法(KFCM)是一种常用的聚类算法,它需要人为地确定分类数,对噪声比较敏感。针对感兴趣区域提取问题,提出一种改进的KFCM算法,该算法先用k'-means算法估计分类数,再用KFCM算法进行聚类,改进隶属度函数,使新算法的隶属度为其邻域隶属度的平均值,提高了算法的抗噪能力。将新算法应用到感兴趣区域提取中,实验结果表明,新算法不需要人为地确定分类数,并且相比传统的FCM算法和KFCM算法能更有效地抑制噪声。     

基于改进的模糊C均值聚类图像分割新算法

模糊C均值（FCM）聚类算法广泛用于图像的自动分割,但是传统的FCM算法没有考虑像素的空间信息,因而对噪声十分敏感。为了克服上述问题,提出了一种新的基于改进的FCM图像分割算法。该方法将空间的信息融入到标准的FCM算法中,通过引入表征邻域像素对中心像素作用的先验概率来重新确定当前像素的模糊隶属度值,该概率在算法执行过程中根据模糊隶属度值自动地予以确定。算法中使用基于统计直方图的快速FCM算法进行初始化,收敛速度大大提高。人造图像和实际图像的实验结果表明该方法的有效性和对噪声具有较强的鲁棒性。     

Otsu准则下分割阈值的快速计算

传统Otsu法在确定阈值时需要穷举计算图像中每个灰度值为阈值时的类间方差.文中利用Otsu阈值的性质,提出了一个新算法以快速计算Otsu阈值.新算法搜寻出与两类类内均值的平均值的整数部分相等的阈值,从中确定一个符合Otsu准则的阈值.传统Otsu法在对梯度图像中的小目标分割时分割性能不佳,文中提出了一个Otsu阈值的改进算法,该算法使用快速计算Otsu阈值的新算法递归求解分割阈值.实验结果表明,与传统Otsu算法相比,计算Otsu阈值的快速算法速度更快,而阈值的改进算法对梯度图像中的小目标分割效果更好.     

量遗传算法及其在无约束优化问题中的应用

量子遗传算法（QGA）是量子计算和遗传算法相结合的产物，将量子的态矢量表示引入到遗传算法中，具有比遗传算法更好的搜索效率和收敛性。本文首先介绍了量子遗传算法的基本原理，讨论了基于量子遗传算法的一系列改进，然后将量子遗传算法应用于无约束优化问题，实例计算表明了算法在该类问题中的有效性和可行性。     

基于DSP的新型SPWM算法研究与实现

通过分析各种SPWM采样算法的优点与缺陷,提出了一种新的SPWM采样算法,并采用Matlab软件计算出在该算法下开关器件的开通与关断时刻点,同时将其与规则采样法、切线采样法的时刻点比较。结果表明：新型的采样算法产生的SPWM脉冲比规则采样法、切线采样法更接近自然采样算法产生的脉冲,计算量远远小于自然算法,体现了该新型采样算法的优越性。最后通过DsP验证该新型算法的可行性。     

图像边缘检测算法的设计和研究

针对经典的边缘检测算法均涉及梯度的运算,存在对噪声敏感、计算量大等缺点的问题,为了找到一种检测效果好、计算量相当的图像边缘算法,提出了只基于对周边像素的灰度比较,完全不涉及梯度运算的SUSAN算法。主要研究了SUSAN算法,并比较了主流的Prewitt算子,Gauss—laplace算子,Canny算子的边缘检测算法,经Matlab仿真实验后,确定该算法不需要计算微分,计算量小,进一步减少了噪声的影响,且SUSAN算子控制参数的选择很简单,任意性较小,所以比较容易实现自动化的选取,是一种非常有效的算法。     

基于混沌自适应变异粒子群优化的解相干算法

针对相干信源波达方向估计的需要,结合粒子群优化算法,论文提出了一种基于混沌自适应变异粒子群优化的广义极大似然算法(CAMPSOGML),算法对阵列的几何结构没有任何约束,分辨的信源数可大于阵元数,算法把混沌初始化和自适应变异策略引进粒子群算法中,有效地提高了收敛速度,克服了粒子群算法容易陷入局部最优值的缺点。计算机仿真表明：与基于实数遗传算法和粒子群算法的广义极大似然估计方法相比,CAMPSOGML算法在收敛速度和估计精度上都有优势,是一种新颖的有效的解相干算法。