粗等价类双边剪枝策略下多次Hash 的约简算法

提出一种新的约简算法. 首先以全局等价类为最小计算粒度, 提出粗等价类概念, 深入研究其性质并证明粗等价类下求核和约简与原决策系统等价; 剖析3 类粗等价类与正区域间的内在关联, 设计针对1 和??1 两类粗等价类双边删减下正区域的渐增式等价计算方法, 从而设计双向剪枝策略以及多次Hash 的属性增量划分算法, 基于此给出高效完备的约简算法. 最后用UCI 中20 个决策集、海量、超高维3 类数据集从多个角度进行验证, 结果表明, 所提出的约简算法的完备性和高效性在绝大多数情况下优于现有算法, 尤其适用于海量数据和超高维数据集.

     

一种基于选择排序的快速求核算法

关于求核的算法有很多,本研究利用选择排序的思想设计了求解等价类的算法,其时间复杂度为O（｜C｜｜U｜）。在此基础上,设计的求核算法,算法时间复杂度为O（｜C｜^（2）｜U｜）。通过实验,证明了算法的正确性和高效性。     

基于二进制可分辨矩阵的快速求核算法

目前,求核算法存在以下不足：求得的核与正区域的核不一致,求核算法的时间复杂度和空间复杂度不理想。针对上述问题,给出一种二进制可分辨矩阵的定义及其求核性质,并证明了由该性质获得的核与正区域的核是等价的,然后设计求核算法,该算法的时间复杂度为max{O（|C||U/C|²）,O（|C||U|）},空间复杂度为O（|C||U/C|²）。最后实例说明该方法的可行性和有效性。     

基于可分辨矩阵的快速求核算法

目前求核算法存在以下不足:求得的核与基于正区域的核不一致,算法的时间和空间复杂度不理想.针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的.为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(|C||U|).在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(|C||U/C|2),O(|C||U|)}和O(|C||U/C|2).最后,实例说明了算法的有效性.     

基于二进制的决策表求核算法

决策表属性约简是粗糙集理论中的核心内容之一,其中求核运算是决策表属性约简的基础,提出了基于二进制的新的决策表求核算法,将求核运算转化为数值的比较运算,并给出了属性绝对必要性和相对必要性的新的判定规则,与传统算法相比,其速度更快,效率更高,易于计算机实现,为扩展粗糙集的应用提供了理论基础。     

改进的差别矩阵及其快速求核算法

求核是粗糙集中一个重要的研究内容之一。本文对杨明的基于差别矩阵求核方法进行研究,实例表明其方法还存在一些不完善。为了能够进一步提高求核效率,对差别矩阵进行改进,提出一种简化差别矩阵的定义,并给出求核方法,同时证明了由该方法获得的核与正区域的核是等价的,由此设计求核算法,其时间复杂度为max{O(|C||U|),O(|C||U/C||U′1|)},空间复杂度为O(|C||U/C||U′1|)。实验表明,该算法是有效的、高效的,且能适合大数据集的处理。     

基于等价类矩阵的属性约简

由于不完备信息系统不能完全适用于粗糙集等价类模型,其合理的属性约简方法的研究在当前是一个备受关注的研究热点。文章给出不完备信息系统等价关系的矩阵表示,同时给出了关于等价类矩阵以及核属性的相关定理,给出了应用等价类矩阵进行属性约简的方法和应用举例,为不完备信息系统的属性约简提供了一种新的方法。     

基于二进制的知识表求核算法

求核运算是属性约简的基础,直接影响着知识约简的效率.提出了基于二进制的新的知识表求核算法,将求核运算转化为数值的比较运算,并且利用rough set理论的相关知识得出了一个重要定理,利用此定理,在求必要属性时,只需选取U/IND(R)每个分类中的一个元素进行比较,大大减少了数据处理量.与传统算法相比,其速度更快,效率更高,易于计算机实现,为扩展粗糙集的应用提供了理论基础.     

一个基于差别矩阵思想的高效求核算法

目前,关于属性约简已有不少算法,其中在很多算法中,都要求先求出核属性集,但利用差别矩阵求核属性这一算法中,生成差别矩阵时,有许多不必要的元素被生成,这些无用的元素在求核时又要进行比较,因而效率不高。利用差别矩阵的思想设计一种不必生成那些不必要的元素的求核算法,从而使算法的效率得到提高。最后,给出了一个实例说明新算法的高效性。     

基于压缩树的快速求核算法

利用差别矩阵进行求核运算时,矩阵中大量的空元素和重复差别元素会浪费很多存储空间及计算时间。针对上述问题,结合频繁模式树,设计一种新的数据结构——压缩树(C_Tree),在此基础上提出一种快速求核算法。理论与实例分析结果证明,该算法的时空复杂度取决于求简化决策表和构造C_Tree的时空复杂度,因此求核效率得到较大的提高。     

基于冲突的增量式核属性更新算法

目前的增量式核属性更新算法大多建立在可分辨矩阵的基础上,不利于大数据集处理,而且算法的效率也不理想.为了克服上述不足,在改进的基于冲突域求核算法的基础上,提出了基于冲突的增量式核属性求解算法.该算法不需要创建可分辨矩阵,当有新对象加入时,对决策表仅需进行一次遍历便可完成核属性增量更新.算法的时间和空间复杂度分别为O（｜C‖U′｜）和O（｜C｜）.理论分析和实验结果均表明,所提出的算法是可行且高效的.     

决策粗糙集属性约简算法与属性核研究

属性约简是粗糙集理论的重要研究内容之一。在Pawlak粗糙集模型中,正区域大小随着属性增多而变大,呈现单调性。然而,在决策粗糙集模型中,概率正区域与属性集之间不具有单调性,从而产生各种属性约简定义。为此,深入研究了决策粗糙集属性约简问题,阐述了几种约简定义之间的关系,证明了保持局部最大概率正区域的约简具有较大的代价,指出了保持所有对象的正决策不变的约简呈现稳定性和存在属性核。     

基于属性重要性的Rough集属性约简方法

介绍了属性约简的原理,在此基础上提出了基于重要性的约简方法,它是利用属性重要性原理,求取核属性和最简属性约简。并举例与传统的方法进行比较。     

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

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

基于量子计算的粗糙集核属性求解算法

粗糙集的核属性求解问题在经典计算中是一个NP问题.现有的方法中最优的时间复杂度也需要${\rm O}$ \left(|C||U|\right)$($U$为论域、$C$为属性列数).由于量子计算的并行性特点, 本文致力于采用量子计算的方法来求解粗糙集的核属性, 拟提出了一种基于量子计算的粗糙集核属性求解算法.经过仿真实验, 在任何情况下, 该算法都能以1的总概率得到目标分量; 且通过理论分析证明了算法的时间复杂度不会高于${\rm O}$\left(|\frac{{\rm{ \mathsf{ π}}}}{2\arcsin\sqrt {\frac{M}{C}}}+1||U|\right)$.     

基于优势区分矩阵的求核方法

在提出基于优势关系粗糙集方法下的类区分矩阵概念后,为解决不一致数据问题,新的优势区分矩阵定义及其求核方法被提出,但是该方法计算代价高。为了能够快速求出存在不一致数据的信息系统的核,该文给出改进的优势区分矩阵定义和求核算法,其空间和时间复杂度都优于现有的算法。实验证明,该算法适用于处理大数据集。     

基于粗糙集的不完备信息系统增量式属性约简

属性约简是粗糙集理论在模式识别中一项重要的应用,传统的属性约简算法只适合处理静态的信息系统,而处理不断动态更新的信息系统面临着巨大的挑战。对于不完备信息系统,提出一种增量式的属性约简算法。在不完备信息系统下引入粗糙集理论中关于正区域的概念,针对不完备信息系统中属性增加的情形,提出了基于正区域的增量式属性约简算法。实验结果表明了所提出的增量式属性约简算法比非增量式的算法具有更高的效率,同时比其他同类型的算法具有更高的优越性。     

信息系统属性增量约简算法的设计与实现

信息系统是一种重要的知识表达形式,对它的增量算法研究主要集中在对象的动态增加上。论文分析了信息系统核和约简在增加属性后的变化规律,设计并实现了信息系统的属性增量约简算法。实验表明,该算法能够有效利用原信息系统的知识,快速、准确地计算出新信息系统的核和约简。     

基于SQL的粗糙集属性约简方法

建立粗糙集模型和SQL语言之间的关系,给出信息系统中基于SQL语言的属性集区分能力、对象集的上下近似、属性重要性、核、约简等概念,提出基于属性集区分能力的完备属性约简算法。实验结果表明了该算法的有效性,为粗糙集理论更广泛地应用于具体的实践提供了一种方法。