基于并行约简的概念漂移探测

数据流挖掘是当前数据挖掘研究的一个热点,概念漂移检测是数据流挖掘的一个重要研究方向.虽然有不少概念漂移的探测方法,但是它们都有一些共同的缺陷:没有整体上删除冗余属性以及利用外部属性去探测概念漂移(比如利用对外部数据的分类准确率)等.利用粗糙集和F-粗糙集的基本原理和基本方法,把数据流中的滑动窗口当成决策子表簇,提出了一种对数据流进行并行约简、整体删除冗余属性的方法,并运用并行约简后数据流决策子表簇中属性重要性的变化探测概念漂移现象.与传统的方法不同,新方法利用数据的内部特性对概念漂移进行探测.实验结果显示,该方法能够有效地整体删除冗余属性、探测概念漂移现象,并且基于互信息的属性重要性在概念漂移探测效果方面比基于正区域的属性重要性要好些.     

基于三支标签传播的半监督属性约简

属性约简是粗糙集理论的重要应用之一.为了对部分标记的数据进行属性约简,一些基于粗糙集的半监督属性约简方法相继被提出,但这些方法在数据信息利用、运行代价、约简质量等方面仍然存在挑战.本文针对混合型分类数据,提出了一种新的基于三支标签传播的半监督属性约简(3WLPME)方法.该方法包括两个过程:三支标签传播(3WLP)和基于混合熵的启发式属性约简(MEHAR).其中,3WLP在经典标签传播算法的基础上,结合三支决策和主动学习思想,对无标签数据进行标注,并更新有标签集和无标签集.迭代执行上述过程直至收敛,可以提升最终的伪标签准确率.在MEHAR中,属性重要度由混合熵度量.基于依赖度和条件熵定义的混合熵,融合了粗糙集的代数表示和信息表示,能更深刻地反映属性的分类能力.本文对3WLP算法和MEHAR算法的有效性进行了理论分析.在UCI数据集上进行了以下仿真实验:3WLP与随机标签传播在伪标签准确率上的对比;不同属性约简算法在约简质量上的对比;3WLPME与其他基于粗糙集的半监督属性约简方法,在约简质量上的对比.实验结果验证了3WLP能获得较高的伪标签准确率;MEHAR在不降低分类准确率的前提下,能获得较小的约简;3WLPME在半监督约简过程中具有更高的效率和稳定性,说明本文所提方法是有效的.     

不完备邻域粗糙集的不确定性度量和属性约简

针对现有的属性约简算法不适合处理数值型属性和符号型属性共同存在的不完备数据,提出了一种拓展不完备邻域粗糙集模型。首先,通过考虑属性值的概率分布来定义缺失属性值之间的距离,可以度量具有混合属性的不完备数据;其次,定义了邻域混合熵来评价属性约简的质量,分析证明了相关的性质定理,并构造了一种基于邻域混合熵的不完备邻域粗糙集属性约简算法;最后从UCI数据集中选取了7组数据进行实验,并分别与基于依赖度的属性约简（ARD）、基于邻域条件熵的属性约简（ARCE）、基于邻域组合测度的属性约简（ARNCM）算法进行了比较。理论分析和实验结果表明,所提算法约简属性比ARD、ARCE、ARNCM分别减少了约1,7,0个,所提算法的分类精度比ARD、ARCE、ARNCM分别提高了约2.5,2.1,0.8个百分点。所提算法不仅能够获得较少的约简属性,同时具有较高的分类精度。     

邻域粗糙集的加权依赖度及其启发式约简算法

邻域粗糙集是数值型属性数据处理的有效工具.基于邻域粗糙集,传统依赖度及其约简未考虑邻域覆盖的绝对结构,由此文中建立加权依赖度及其启发式约简算法.首先,提出加权依赖度并得到其度量改进性与粒化单调性,定义相关的属性约简.然后,分析邻域半径的自适应取值,构造基于加权依赖度的启发式约简算法(NWDR).最后,在UCI数据集上进行对比实验,验证加权依赖度的单调性与NWDR的有效性.实验证明,加权依赖度改进传统依赖度的不确定性表示能力,NWDR具有较高的分类准确率与较强的应用适应性.     

基于强化正域的属性约简方法

属性约简是粗糙集理论的核心内容之一。通过对多种约简方法进行比较,为了得到更好的结果,在传统基于属性依赖度的约简方法基础上,定义更精确的强化正域概念。通过对边界域的精确划分,得出各条件属性对决策属性的强化依赖度,并用自顶向下的启发式搜索算法得到约简结果。采用UCI标准数据集对基于强化正域约简方法REPR进行测试,约简数据后构建的决策树规模小,分类精度高。实验结果表明,相比于经典方法,REPR能更有效地对决策表进行属性约简。     

一种直觉模糊粗糙集属性约简新算法

将信息熵理论与直觉模糊粗糙集结合起来,提出一种基于互信息的直觉模糊粗糙集属性约简新算法.给出了在直觉模糊环境下,基于互信息的属性重要度和属性依赖度的度量准则.本文所提出的算法以属性重要度和依赖度为双重度量标准,采取可增可删的双向回归算法,在保持分类精度不变的情况下,最后得到决策表的最小属性约简.实例表明在多属性的决策表约简中,在本文提出的算法得到的属性约简的基础上而得到的决策规则是较简捷、较完备的.     

基于粗糙集理论的属性约简算法

粗糙集理论是一种新的数据挖掘方法,其主要思想是保持分类能力不变的情况下,通过属性约简,达到发掘知识并简化知识的目的.从大量数据发现知识时,属性约简是一个关键问题.在理解和分析基于粗糙集理论的数据挖掘算法基础上,提出了一个基于属性依赖度的属性约简算法.实验结果表明,该算法能更有效地对决策系统进行约简.     

粗糙集属性依赖度强化的应急数据挖掘模型

在粗糙集的核心方法属性约简理论中,针对次要属性过多时属性依赖度一致引发的约简困难现象,以粗糙集属性依赖度强化为基本方法构建数据挖掘模型。模型中,计算各属性在组合中的依赖度,将组合中的依赖度合并于各属性从而强化属性依赖度。为合理化计算过程,给出一种离散化方法并构建探索模型进行实验,缩小离散量范围与属性组合范围。最后所得依赖度作为属性重要性,挖掘重要属性。实验证明,在部分地区5级以上震后经济损失影响因素分析中,比较传统属性约简,该模型可更有效地分析属性之间的重要性,解决了约简困难的问题,使用测试数据时该模型与传统方法的结果有86%的一致性。     

基于邻域粗糙互信息熵的非单调性属性约简

属性约简是粗糙集理论一项重要的应用,目前已广泛运用于机器学习和数据挖掘等领域,邻域粗糙集是粗糙集理论中处理连续型数据的一种重要方法.针对目前邻域粗糙集模型中属性约简存在的缺陷,构造一种基于邻域粗糙集的邻域粗糙熵模型,并基于此给出邻域粗糙联合熵、邻域粗糙条件熵和邻域粗糙互信息熵等概念.邻域粗糙互信息熵是评估属性集相关性的一种重要的方法,具有非单调性变化的特性,对此,提出一种基于邻域粗糙互信息熵的非单调性属性约简算法.实验分析表明,所提出算法不仅比目前已有的单调性属性约简算法具有更优越的属性约简结果,而且具有更高的约简效率.     

互信息的序决策信息系统属性约简研究

优势关系粗糙集理论是粗糙集理论有意义的推广,决策信息系统知识约简是粗糙集理论的核心内容之一.通过在协调序决策信息系统中引入条件熵、互信息概念,给出了基于条件熵、互信息的协调序决策信息系统属性约简算法,并通过学生评价决策信息系统验证了该算法的有效性,使协调序决策信息系统的属性约简得到了扩展.在不协调序决策信息系统中引入限定条件熵、限定互信息概念,并给出基于限定互信息的不协调序决策信息系统属性约简算法,为不协调序决策信息系统的属性约简的应用提供了可行的解决方法.     

Conditional entropy for incomplete decision systems and its application in data mining

Rough set theory is a useful mathematic tool for dealing with vague and uncertain information. Shannon's entropy and its variants have been applied to measure uncertainty in rough set theory from the viewpoint of information theory. However, few studies have been carried out on information-theoretical measure of attribute importance in incomplete decision system (IDS) considering the relation between decision attribute and condition attributes. In this paper, we introduce the concept of conditional entropy together with entropy and joint entropy in IDSs. By using the new conditional entropy, we propose a measure for attribute importance. Based on the measure, a heuristic attribute reduction algorithm is presented. Some test experiments on real-lift data-sets show the effectiveness of the algorithm. The attribute importance measure and the attribute reduction algorithm can be used in data mining or machine learning for handling incomplete data.     

Approaches to knowledge reduction of covering decision systems based on information theory

In this paper, we propose some new approaches for attribute reduction in covering decision systems from the viewpoint of information theory. Firstly, we introduce information entropy and conditional entropy of the covering and define attribute reduction by means of conditional entropy in consistent covering decision systems. Secondly, in inconsistent covering decision systems, the limitary conditional entropy of the covering is proposed and attribute reductions are defined. And finally, by the significance of the covering, some algorithms are designed to compute all the reducts of consistent and inconsistent covering decision systems. We prove that their computational complexity are polynomial. Numerical tests show that the proposed attribute reductions accomplish better classification performance than those of traditional rough sets. In addition, in traditional rough set theory, MIBARK-algorithm [G.Y. Wang, H. Hu, D. Yang, Decision table reduction based on conditional information entropy, Chinese J. Comput., 25 (2002) 1-8] cannot ensure the reduct is the minimal attribute subset which keeps the decision rule invariant in inconsistent decision systems. Here, we solve this problem in inconsistent covering decision systems.     

证据理论与熵值融合的知识约简新方法

求解决策表的最小约简已被证明是NP-hard问题,在粗糙集和证据理论的基础上提出了一种知识约简的启发式算法。利用粗糙集等价划分的概念给出属性的信息熵,定义每个属性的熵值重要性并由此确定知识的核。引入二分mass函数对每个属性建立一个证据函数,证据融合得到每个属性的证据重要性。以核为起点,以证据重要性为启发,依次加入属性直至满足约简条件。实例表明,该方法能够快速找到核和相对约简,并且该约简运用到分类上正确率也是较高的。     

基于邻域近似条件熵的启发式属性约简

目前粗糙集的研究局限于有限集,且现有的邻域粗糙集属性约简算法中属性重要性度量方式单一。针对邻域粗糙集存在的问题,提出了基于无限集的邻域近似条件熵模型。该模型以邻域近似条件熵下的属性重要度为启发条件,构造了一种基于邻域近似条件熵的前向贪心搜索属性约简算法。利用熵的单调性,证明了算法的正确性,并分析了算法的时间复杂度。通过实例分析和多个UCI数据集上的实验表明,所提出的算法是可行的,能有效减少属性数量,与现有的算法相比,不仅能够获得较小的属性约简结果,而且具有较好的分类性能。     

非完备决策信息系统中的不确定性度量

针对粗糙集数据分析中的不确定性度量问题。本文首先构造一种新型的考虑条件属性缺失度的目标概念条件熵和决策知识条件熵。在此基础上,提出基于条件熵的属性权重确定技术和最小条件熵非完备属性取值补充方法,用以解决属性权重完全未知的非完备多属性决策问题。应用实例分析表明:该方法能有效结合粗粒度的初步分级信息,客观地确定决策因素取值,具有很强的解释意义,得到的决策结果更为合理有效。     

基于信息熵的一种属性约简算法

文章针对Rough Set理论的核心内容之一属性约简进行了研究。结合信息论的有关知识,研究了在属性约简过程中决策属性集相对条件属性集的条件熵的变化规律,在此基础上提出了新的属性约简算法。实验分析表明,在多数情况下这种算法都能够得到决策表的最小约简,同时还对算法复杂度做了简单的分析。     

以互补条件熵为启发信息的正域属性约简

属性约简是一种特殊的特征选择方法,是粗糙集理论中的核心内容之一。正域约简是一类常见的启发式的约简方法,它通常采用前向贪婪搜索策略产生候选的属性子集,以相对正域作为启发信息和停止条件。根据互补条件熵的随划分的变化规律,分四种情况分析了约简过程中某个属性加入属性子集后,相对正域和互补条件熵的变化,并在此基础上提出了一种以互补熵为启发信息的正域属性约简方法。实验分析表明,新方法与传统的正域约简算法相比,可以得到属性数量更少且决策性能非常接近的约简,同时可以有效地提高约简计算效率。     

新的信息熵属性约简

在粗糙集不确定性度量公式中,模糊熵和模糊度是重要的度量方式。根据粗糙集不确定性度量中模糊熵和新的模糊度公式,提出了在决策信息系统中修正条件信息熵和相对模糊熵的概念,并分别用两种方式证明了熵在属性约简过程中的单调性。然后利用向前添加属性算法进行属性约简,约简结果在RIDAS(roughset based intelligent data analysis system)平台上进行识别率测试,通过实验对比分析了两种新的信息熵与条件信息熵的约简结果,为基于信息熵的属性约简提供了参考。