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

目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义，证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中，要先求出IND（C），故设计了一个较好的求IND（C）的算法，其复杂度被降低为O（｜U‖U｜）。在此基础上设计了一个快速属性约简算法，其时间复杂度和空间复杂度分别被降为max{O（｜C｜^2（｜U＇pos‖U/C｜））,O（｜C‖U｜）}和max{O｜U｜},O（｜C｜（｜U＇pos‖U/C｜））}。

基于简化的二进制差别矩阵的快速求核算法

目前,基于二进制差别矩阵的求核算法有如下不足:算法的时间和空间复杂度不理想;所得到的核与基于正区域的核不一致.叶东毅教授提出了一个新的二进制差别矩阵并证明了在新的二进制差别矩阵中定义的核与基于正区域的核是一致的,但计算新的二进制差别矩阵除了具有和原方法相同的存储空间外,还增加了额外的计算.本文给出一个简化的二进制差别矩阵和相应的求核算法,并证明了所求的核是基于正区域的核.新算法的时间复杂度和空间复杂度分别被降为m ax{O(C(U’p os‖U/C)),O(C‖U)}和m ax{O(U),O(C(U’p os‖U/C))}.

基于信息熵的二进制差别矩阵属性约简算法

给出一个简化的二进制差别矩阵的属性约简定义,并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵,设计了一个快速求简化决策表的算法,其时间复杂度为O(|C||U)|。在此基础上,设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法,其时间复杂度和空间复杂度分别为max{O(|C||U)|,O(|C|2|U/C|2)}和max{O(|C||U/C|2),O(|U)|},最后用一个实例说明了新算法的高效性。

一种使用二进制差别矩阵的属性约简方法

针对区分矩阵属性约简算法中区分矩阵存在空值元素和重复元素等缺点,提出了一种基于二进制差别矩阵的属性约简算法.该算法不仅保证了属性约简的完整性和正确性,同时也降低了运算所需的时间和空间.

简化的二进制差别矩阵属性约简算法的改进

目前,基于二进制差别矩阵的属性约简算法有以下不足:所得到的属性约简与基于正区域的属性约简不一致。文献[7]中给出一种基于简化的二进制差别矩阵的快速属性约简算法,但该算法不完备。分析了算法不完备的原因,在此基础上,提出了一种改进的完备算法,该算法的时间复杂度为max(O(∣C||U∣),O(∣C∣2∣U pos||U/C))。

一个基于修正的二进制差别矩阵的快速求核方法

本文研究了二进制差别矩阵中核属性的性质,指出并证明了二进制差别矩阵求核的理论依据,在此基础上给出了一种二进制差别矩阵的修正方法及求核方法。该方法不仅适用于任何决策表信息系统(相容决策表和不相容决策表),而且有效地降低了计算代价。

不完备决策表的扩展差别矩阵规则获取方法

针对不完备决策表,通过引入扩展差别矩阵,利用基数排序对广义决策值进行划分,只比较广义决策值不同的对象,并且记录对应的条件属性值,克服了计算过程中反复检查属性值对与广义决策值是否冲突的缺点,从而优化了算法。实例分析结果说明了该方法的正确性和优越性。

基于浓缩差别矩阵的规则获取算法

基于HU的差别矩阵方法不仅构造费时且占用空间大,使得执行效率不高。利用元素间两两比较的方法构造浓缩差别矩阵的算法则时间复杂度过高,不适用大数据的处理。而将差别元素压缩存储在一棵FP树上,却无法去除无用的元素。为此,引入二叉树的思想,对短差别集依次建树,长差别集依次进行比较查找,提出一种改进的浓缩差别矩阵算法,在此基础上,给出扩展的二进制差别矩阵,直接从矩阵中提取规则。实验结果证明,该算法不仅降低了时间复杂度,还能够去掉无用元素,减少存储空间。

基于二进制链表的粗糙集属性约简

差别矩阵是很多学者用来计算粗糙集属性约简的一种方法,该方法因其简单、直观、易于理解而得到广泛应用,但是包含在差别矩阵中的冗余元素不仅对属性约简不起作用反而增加存储空间,为消除这些冗余元素提出了一种新的存储结构:二进制链表,通过位运算将差别矩阵中所有的重复元素和父集元素删除,降低差别信息的存储空间。为验证二进制链表的有效性,提出了一种新的属性约简算法。通过UCI数据库中多组数据集对该方法进行测试,并将实验结果与其他算法进行比较,提出的算法可以更快地得到属性约简集并且能够有效地降低存储空间。

海量大数据定向采样有差别挖掘算法仿真

在大数据中,不同类别之间可能存在数据分布不均衡的情况,即某些类别的数据样本数量远远少于其他类别。这种情况下,传统的采样方法无法正确反映所有类别的特征和差异。为提升大数据信息的应用性,文中研究海量大数据定向采样有差别挖掘算法。以网站统一资源定位器(URL)初始化为基础,在网络上抓取网页,采集网页的超文本标记语言(HTML)数据,提取定向数据的相关链接,并将其导入URL队列。根据网络搜索策略,实施相关的数据搜索和处理。完成数据搜索后,将自动进行下一网页的URL,继续进行海量大数据定向采样。结合模糊特征匹配与检测滤波方法实现大数据定向采样过程中的抗干扰处理。采用粗糙集算法实施挖掘,利用扩展差别矩阵对大数据决策表内的值实施约简,实现海量大数据的模式分类。实验结果显示,该算法数据采集过程中的丢包率基本控制在0.2%以下,具有较高的鲁棒性。

一种基于决策表的核增量式高效更新算法

引入简化决策表,结合简化二进制差别矩阵设计思想,提出一种基于决策表的核增量式高效更新算法.该算法在更新简化的二进制差别矩阵时,只需在原决策表基础上对记录进行相应的更新,不需要重复计算原决策表的二进制差别矩阵.采用边更新简化二进制差别矩阵边计算核,显著地提高了算法的效率和灵活性.新算法的时间复杂度和空间复杂度分别为O(|C||U′|)和O(|C||U′pos||U′|).最后用一个实例说明了新算法的高效性.

一种基于决策表的属性约简增量式快速更新算法

针对实际的决策表中的对象通常是动态变化的情况,首先引入了简化的决策表,然后在动态更新核的基础上,结合简化二进制差别矩阵和位图运算的设计思想,提出了一种快速的属性约简增量式更新算法.当有新对象加入决策表时,新算法只需验证新增的对象和原决策表中的对象是否一致性,然后采用在计算二进制差别矩阵的同时对原属性约简进行动态更新,从而有效地降低算法的时空复杂度,最后用实例说明了新算法的可行性和高效性.

一种增量更新算法在数据挖掘中的应用

引入扩展差别矩阵和扩展决策矩阵,提出了新的属性约简算法和增量更新算法,即基于扩展差别矩阵的属性约简算法和基于扩展决策矩阵的增量式规则提取算法,讨论了规则的增量更新算法。由于使用了增量更新算法和并行处理技术,从而提高了数据挖掘的效率,降低了时间复杂度。通过实验说明此算法是有效和可行的。

基于知识粒度的不完备决策表求核方法

为降低不完备决策表求核算法的时间复杂度,本文构造了粒度二进制的差别矩阵。然后定义属性重要性及相应的核,由此设计了一个基于不完备决策表的粒度二进制差别矩阵的求核算法,并分析新算法的时间复杂度,其时间复杂度降为max{O(C U Upos),O(K C U)},优于同类算法的时间复杂度,最后用实例说明了该算法的有效性。

一种基于不完备决策表的求核方法

求核是粗糙集理论的重要研究内容之一,现有的求核算法大部分都是基于完备决策表的,对基于不完备决策表的求核研究很少。提出了不完备决策表二进制差别矩阵的构造方法,在此基础上,利用二进制差别矩阵设计了一种不完备决策表的求核算法。从理论上证明了基于二进制差别矩阵的求核与基于正区域的求核是相等的。新算法的时间复杂度是O(|C||U|2),用实例分析说明了新算法的正确性。

区间值决策系统下最短约简算法的研究

属性约简可以选出保持分类能力不变的属性子集,而最短约简不仅可以选出保持分类能力不变的属性子集,还可以最大程度地删除冗余属性、压缩决策表,选出最优的属性子集。本文在区间值决策系统的数据背景下,分别对针对决策属性的全部决策类和特定决策类构建二进制差别矩阵,结合SRA算法分别提出了基于二进制差别矩阵的最短约简算法和特定类最短约简算法。为了验证算法的有效性,选取8组UCI数据集分别从算法的约简结果长度和约简效率两方面进行对比,实验结果证明了算法的可行性和有效性。