高可信度最小约简属性启发策略

为提高启发式算法计算最小约简的可信度,基于可辨识矩阵,研究了属性之间存在的吸收、排斥以及互斥等特征,分析其与最小约简的关联,提出了对应的最小约简属性启发策略, 建立了各个特征下属性启发策略的可信度计算模型. 在此基础上,按照可信度排序,形成了一种综合的高可信度最小约简属性启发策略,并给出了具体的约简算法. 理论和实验分析表明,本文策略具有可信度高且可信度可以估计等优点,能有效提升最小约简算法的性能.     

变精度粗糙集的属性核和最小属性约简算法

文中深入研究了变精度粗糙集的属性约简问题,给出了3种属性约简的概念,针对不同概念的属性约简,分别提出了两种不同的求解变精度粗糙集最小属性约简算法:基于容差矩阵和属性核的最小约简.提出了变精度粗糙集的属性核思想,对其进行了形式化描述,说明了变精度粗糙集的属性核真正具备了核的本质特征,从而更深层地提出了基于属性核的启发式约简以求解最小约简.理论分析和实例表明,所提出的两种最小约简算法可以减小属性约简的搜索空间,提高约简的效率,使得变精度粗糙集的属性约简具有了实用性.     

属性约简矩阵特征结构及分层约简快速算法

已有的属性约简算法往往只能提供一个可行解,并且不能保证是最小约简解.因此,详细分析属性约简特征并获得最小约简解具有重要意义.本文针对信息系统数据集提出属性约简矩阵,通过矩阵的结构特征分析得到属性的约简特征,因此采用矩阵代数的方法求解属性约简问题,并得到分层约简快速算法.经实例运算可见,矩阵代数的处理和算法大大降低了最小约简解获取的计算量.     

基于相对可辨识矩阵的决策表属性约简算法

针对现有属性约简算法存在的问题,利用信息论和粗糙集理论,提出一种基于相对可辨识矩阵的决策表属性约简算法.该算法以核属性为基础,通过建立相对可辨识矩阵,利用条件信息熵作为启发式信息,减少属性约简过程中的搜索空间,逐个添加条件信息熵最大的属性,直到找出最小约简为止,并分析了该算法的时间复杂度.实例分析结果表明,该算法能有效地对决策表属性进行约简.     

一种基于粗糙集属性频度约简算法的改进

为了获得有效的属性最小相对约简,在基于属性频度的启发式约简算法的基础上,提出了一种同时满足属性重要性和频度改进的启发式约简算法.该算法的基本思想是:以属性的核为基础,以频度作为选择属性的启发信息,即把属性频度最大的属性添加到核属性中,这样就把分类能力较强的属性添加到约简集合中,从而能够获得较优的约简.     

决策系统属性约简优化算法研究

属性约简是粗糙集理论研究的关键问题,针对求取决策系统所有约简的NP问题,基于差别矩阵提出一种决策系统属性约简优化算法.通过改进差别矩阵得到差别集,在获得核与约简候选信息基础上,以属性频度作为启发式信息,快速有效地求取决策系统的所有约简.分析表明了该算法的可行性与有效性.     

基于粗糙集的数据约简方法研究

属性约简是粗糙理论的基础与核心研究问题.针对求取属性最小约简的NP问题,设计一种基于粗糙集的数据约简算法,寻求决策系统的近似最小约简.首先改进差别矩阵快速获取优化差别集,然后利用优化差别集中属性频度作为启发式信息,递归地调用算法寻找当前最重要属性,搜索过程中所有重要属性构成的集合即为最终所求约简.将该算法应用于电子商务用户访问模式数据浓缩,理论分析与仿真实例表明了该算法的可行性和有效性.     

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

属性约简是粗糙集理论研究的核心问题之一,而且现已证明寻找一个决策表的最小约简是NP-hard问题.针对变精度粗糙集理论的属性约简问题,从相对可辨识矩阵,属性的重要度作为启发式的信息,给出变精度粗糙集的属性约简算法的改进,在一定程度上简化了属性约简的计算,提高了属性约简的效率.最后通过实例证明了改进的算法给出信息系统的属性约简结果的正确性.     

基于区分能力的HU差别矩阵属性约简算法

将决策表属性区分能力大小与HU差别矩阵结合起来,建立起属性区别能力与该属性在HU差别矩阵中出现次数之间的关系.提出与HU差别矩阵属性约简相适应,只依赖于等价类基数计算的属性区分能力计算公式,得到HU差别矩阵约简的属性区分能力判定定理.定义了以属性区分能力为基础的属性相对重要性概念,提出以相对重要性为启发式信息的HU属性约简算法.由于该算法不必构造差别矩阵,只依赖于等价类基数的计算,从而大大提高了算法效率.数值算例和实验结果表明,该算法更有利于最优或次优约简结果的搜索.     

基于频率函数循环重计算的属性约简和挖掘算法研究

针对经典HORAFA启发式约简算法在以属性频率为重要启发信息约简时,往往不能获得最优属性约简集的问题,本文提出了基于属性频率函数循环重计算的改进启发式约简和挖掘算法(BRFA算法)。该算法在已约简属性基础上,进行剩余属性频率函数的循环重计算,直至区分矩阵为空,能大大节省决策表的最小约简时间并能得到所有相对约简。通过实例分析和UCI机器学习数据库实验表明,BRFA算法在属性约简和挖掘方面具有较好的性能。     

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

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

     

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

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

     

基于幂图的属性约简

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

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

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

     

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

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

代数约简的知识粒度表示及其高效算法

首先提出了修正相对粒度计算公式,给出其单调性证明以及等号成立的充要条件;然后证明了保持修正相对粒度不变是保持正区域不变的充要条件,并给出代数约简的知识粒度表示;最后讨论了现有相对粒度与修正相对粒度之间的关系,利用修正相对粒度的单调性给出计算属性重要性定义及其递归计算公式,进而利用基排序思想计算等价类,设计出一种计算决策表代数约简的高效算法.实验结果表明该算法是可行且高效的.     

基于属性关联的约简算法

针对启发式约简算法难以获得最小约简的问题,研究属性之间的排斥与吸引等关联特性,给出属性重要度计算指数。在此基础上,结合属性频率方法,提出基于属性关联的启发式约简算法。该算法以最小约简为目标,采取兼顾单个属性的辨识能力以及属性之间关联的约简策略。实验结果表明,该算法比属性频率方法以及一些同类算法具有更少的属性启发次数,计算结果大部分为最小约简。     

基于Bucket Sort的快速属性约简算法

利用桶排序思想设计了一个求解U/C的算法,其时间复杂度降为O(∣C∣∣U∣).由此,给出一种无需求解正域便能判断正域是否变化的方法.基于以上方法,提出一种快速属性约简算法.该算法的求解策略是在每次迭代过程中求解决策表相对核,如果在某次迭代过程中找不到这样的核属性,则任意排除一个条件属性.最后通过实验分析了该算法在最坏情况下的时间复杂性,其复杂性降为O(∣C∣2∣U/C∣).     

基于双重粒化准则的邻域多粒度粗糙集模型

为了从多粒度、多层次的角度有效处理名义型属性和数值型属性并存的混合数据, 首先基于不同的属性集序列和不同的邻域半径构建双重粒化准则, 建立基于双重粒化准则的邻域多粒度粗糙集模型; 然后给出该模型的相关性质, 提出该模型下的属性约简算法, 约简结果可以根据实际问题的需要灵活选择合适的属性集和邻域半径. 实例分析验证了所提出模型和算法的有效性.