属性序下的快速约简算法

将分治法的思想溶入Rough集算法中,在给定属性序下,提出了基于分治策略的属性约简算法.利用该算法可以计算给定属性序下的唯一约简,并能快速得到海量数据的属性约简.在一次性将决策表的所有数据调入计算机内存的情况下,算法的平均时间复杂度为O(|U|×|C|×(|C| log|U|)),空间复杂度为O(|U| |C|).仿真实验结果说明了算法的高效性.     

基于MapReduce改进离散型萤火虫算法和多重分形的属性约简方法

针对大数据环境下属性约简问题,提出基于MapReduce改进离散型萤火虫算法(IDGSO)和多重分形(MFD)的属性约简方法.首先,通过对萤火虫个体的移动方式进行离散化改进,引入迁徙策略和高斯变异策略,避免陷入局部最优,并提出改进离散型萤火虫算法.然后,将IDGSO结合MFD应用于属性约简中.最后,针对大数据环境下属性约简问题,采用MapReduce编程模式,实现对IDGSO和MFD的并行化.在UCI数据集和实际气象数据集上的实验表明,文中算法约简性能较优,运行效率较快,具有较好的有效性和可行性.     

基于改进属性约简的细粒度并行AP聚类算法

Affinity Propagation(AP)聚类算法将所有数据点作为潜在的聚类中心,在相似度矩阵的基础上通过消息传递进行聚类.与传统聚类方法相比,对于规模很大的数据集,AP是一种快速、有效的聚类方法.正是这样,属性约简对于AP算法非常重要.另外,在大规模并行系统的设计中,细粒度并行是实现高性能的基本策略.提出了一种基于改进属性约简的细粒度并行AP聚类算法(IRPAP),将粒度思想引入到并行计算中.首先分析了并行计算中的粒度原理.然后用改进的属性约简算法对数据集预处理.此算法并行计算并选择差别矩阵元素,降低了时间空间复杂度,最后用AP算法聚类.整个IRPAP算法将任务划分到多个线程同时处理.实验证明,对于大规模数据集的聚类,IRPAP算法比AP算法效率更高.     

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

实际应用中存在大量动态增加的区间型数据，若采用传统的非增量正域属性约简方法进行约简，则需要对更新后的区间值数据集的正域约简进行重新计算，导致属性约简的计算效率大大降低。针对上述问题，提出区间值决策表的正域增量属性约简方法。首先，给出区间值决策表正域约简的相关概念；然后，讨论并证明单增量和组增量的正域更新机制，提出区间值决策表的正域单增量和组增量属性约简算法；最后，通过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。实验结果表明，提出的区间值决策表的正域增量式属性约简算法具有高效性。     

基于粗糙集理论的条件属性动态约简算法

粗糙集理论是一种新的处理含糊和不确定性问题的数学工具,可以有效地分析和处理不完备信息.条件属性约简是粗糙集理论算法研究的重点.在启发式条件属性约简算法的基础上提出了动态条件属性约简算法,算法以一个信息大的属性作为基础,不断添加条件属性,并对新增加的条件属性进行修正,找到约简条件属性,目的为了进行遥感数据的动态分类做基础.文中在VC 6.0开发环境下实现了两种算法,用HSV和Iris数据验证了算法的有效性,并分析了算法的时间和空间复杂度.     

一种并行的信息系统属性约简算法*

属性约简是信息系统中的一个重要操作,而分类是属性约简的基础,且直接在大数据集上进行属性约简往往存在效率低下的问题。故以分类为基础提出了一种基于信息熵的信息系统并行属性约简算法。该算法通过信息熵的计算,在属性约简的同时对原信息系统逐层分解成尽量均匀的子表,从而实现了属性约简的并行计算并缩小了搜索空间。对该算法的时间复杂度进行了分析,实验表明,该算法在效率方面优于传统算法。     

增量式的高效属性约简算法

属性约简是Rough集理论的核心内容之一，计算所有的属性约简已经被证明是NP完全问题．在深入研究Rough集理论的基础上，仔细分析了对象集的增加与属性约简的关系，给出了增量式属性约简的判定定理，从而提供了计算所有属性约简的增量式算法，分析了算法的时间复杂度．理论分析和实验结果表明，该约简算法在效率上较现有的算法有显著提高．     

基于集合枚举树的最小属性约简算法

为了寻找一种有效的最小属性约简方法,给出了条件属性集上的属性重要度序关系,基于此序关系构建了属性集上的集合枚举树,提出了一种快速的最小属性约简算法,该算法采用至上而下、层次优先策略搜索集合枚举树寻找属性最小约简。为了提高算法性能,该算法采用核和父集剪枝策略减少搜索空间,采用优化计算来确保同一集合的正域只计算一次。基于UCI数据的实验结果表明,该算法是有效的。     

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

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

一种新的启发式粗集决策表属性约简算法

粗集理论通过对原始决策表的约简从而获取规则知识,其核心部分是属性约简.经过约简后的数据更有价值,更能准确地获取知识.文中提出了一种新的启发式属性约简算法,并给出了算法的详细步骤和具体的实验示例.该算法通过不一致计数和互信息增量的计算来衡量属性的重要性,避免了对属性之间随机组合情况的搜索,可以提高求解速度.实验结果表明,相比较于动态约简算法和标准遗传算法,所提出的算法获得的约简属性集更加简洁和高效.     

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

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

一种基于浓缩树结构的属性约简算法

属性约简是粗糙集理论的重要研究内容之一,其中基于区分矩阵的约简算法是一种高效的约简算法,但算法具有很高的空间复杂度.为了减少区分矩阵的空间开销,利用浓缩树结构,结合区分矩阵单个属性一定为核属性的特征,提出改进的生成浓缩树算法,压缩存储区分矩阵中的非空数据项,且不丢失原区分矩阵的所有信息;利用生成的浓缩树结构结合启发式策略,给出属性约简算法.实验结果表明,算法正确有效并且空间复杂度有明显降低.     

变精度下不完备混合数据的增量式属性约简方法

为了解决当不完备混合决策系统中数据动态增加时,静态属性约简方法的计算复杂度高的问题,提出变精度下不完备混合数据的增量式属性约简方法。首先,在变精度模型下给出了利用条件熵度量属性的重要性程度;然后,详细分析和设计了当数据动态增加时条件熵的增量式更新变化情况和属性约简的更新机制;在此基础上,利用启发式贪心策略构造了增量式的属性约简算法,实现了不完备的数值型和符号型混合数据下属性约简的动态更新。通过UCI数据集中五个真实的混合型数据集的实验比较和分析,在约简效果方面,利用增量式属性约简算法处理Echocardiogram、Hepatitis、Autos、Credit和Dermatology数据集的增量规模为90%+10%时,数据集的原属性个数分别由12、19、25、17和34个约简至6、7、10、11和13个,分别占原属性集的50.0%、36.8%、40.0%、64.7%和38.2%;在执行时间方面,增量式算法在五个数据集的平均耗时分别为2.99 s、3.13 s、9.70 s、274.19 s和50.87 s,静态算法的平均耗时分别为284.92 s、302.76 s、1062.23 s、3510.79 s和667.85 s,且增量式算法的耗时与数据集的实例规模、属性个数和属性值类型的分布相关。实验结果表明,增量式属性约简算法在计算耗时方面要显著优于静态算法,且能有效剔除数据中的冗余属性。     

基于属性重要性的决策表属性约简算法

提出一种基于粗糙集属性重要性的属性约简算法。该算法以所有条件属性为初始约简集合,以属性重要性为迭代准则,通过逐步缩减来求取约简。同时给出了该算法的时间复杂度分析,并举例验证了所提出算法的有效性和实用性。     

基于粗糙集理论的条件属性动态约简算法

粗糙集理论是一种新的处理含糊和不确定性问题的数学工具,可以有效地分析和处理不完备信息。条件属性约简是粗糙集理论算法研究的重点。在启发式条件属性约简算法的基础上提出了动态条件属性约简算法,算法以一个信息大的属性作为基础,不断添加条件属性,并对新增加的条件属性进行修正,找到约简条件属性,目的为了进行遥感数据的动态分类做基础。文中在VC＋＋6．0开发环境下实现了两种算法,用HSV和Iris数据验证了算法的有效性,并分析了算法的时间和空间复杂度。     

有序不可区分串的属性约简增量更新算法

当有新增对象加入到决策表时,已有的属性约简将会发生变化,为保证约简结果的正确性,需对其进行动态更新。差别矩阵算法通常以可区分元素的多少作为属性重要性的依据,每次选择可区分信息最多的属性加入约简集,导致有较高的时间复杂度。为此,提出了有效比较元素对及不可区分串定义,以不可区分串长短为属性重要性选择的依据,并证明了其有效性;然后分析了增量更新的不同情况,将新增对象加入简化决策表,按相应条件动态变化约简集,由此设计了基于有序不可区分串的增量更新算法;最后通过实验比较和实例分析了增量更新算法的可行性和有效性。     

基于属性重要性的决策表属性约简算法

提出一种基于粗糙集属性重要性的属性约简算法。该算法以所有条件属性为初始约简集合，以属性重要性为迭代准则，通过逐步缩减来求取约简。同时给出了该算法的时间复杂度分析，并举例验证了所提出算法的有效性和实用性。     

基于粗糙集的决策表属性约简方法的研究

求核和属性约简是粗糙集理论研究的一个核心问题。文中主要针对现有的一些决策表属性约简算法存在的不足,尤其是基于信息熵的属性约简算法在较大数据集上效率不高的问题提出改进。主要通过结合粗糙集的相关理论来改进原有的属性约简算法在求核中的约束条件,进而在原有算法的基础上提出了一种改进算法。在求约简属性集时,利用新提出的约简算法,使计算复杂度降低,同时保持了高效的决策准确率。实验结果表明改进后的决策表属性约简方法能够更加快速有效地找到约简集。     

基于知识粒化的信息系统增量式属性约简

传统的属性约简算法不能适用于动态变化的信息系统。为了对属性集不断动态增加的信息系统进行更高效的属性约简,基于粒计算模型中知识粒化的视角,提出一种知识粒度的增量式属性约简算法。在信息系统中引入知识粒度度量的概念,当信息系统属性集增加时,研究了知识粒度的增量式更新方法,理论分析了这种更新方法的高效性,根据知识粒度的增量式更新提出一种增量式属性约简算法。仿真实验结果表明该算法具有较高的属性约简性能。     

基于云理论的数据属性约简

提出了一个基于云模型的数据属性约简新算法,该算法借助云模型将每个连续属性上的定量数据转化为定性概念,然后利用此定性概念计算每个条件属性对决策属性的重要性,最后以贪婪算法的思想求解约简属性,从而解决了当前约简算法对连续属性必须离散化的问题.同时对算法中可能遇到的冲突问题给出了初步的解决方案.实验表明,该算法在降低时间复杂度的同时能求出更好的属性集约简.