共查询到20条相似文献,搜索用时 125 毫秒
1.
不完备信息系统中的属性约简是粗集理论应用的难点。通过引入信息熵和条件信息熵,对信息系统中属性的必要性进行了定义,提出了一种基于条件信息熵的属性约简启发式算法。通过引入相对正域,有效地解决了不一致系统属性约简过程中产生的冗余属性问题,并分析了该算法的时间复杂度。最后,通过实例说明该算法能得到不完备决策表的最小相对约简。 相似文献
2.
3.
4.
基于同可区分度的属性约简算法 总被引:4,自引:0,他引:4
从知识区分能力角度提出同可区分度的概念,并对其性质进行分析。利用同可区分度来刻画信息系统中属性的相对重要性,设计了一种基于信息论观点的启发式约简算法。该算法直接对原信息系统进行约简,不需要预处理,且对完备和不完备信息系统都适用,在保证较高约简率的同时使得信息论观点的约简算法在完备信息系统中的最坏时间复杂度降为公式最后用实例说明该算法的高效性。 相似文献
5.
一种基于知识粒度的不完备信息系统的属性约简算法 总被引:4,自引:1,他引:3
在不完备信息系统中,通过引入知识粒度的概念,对属性的重要性进行了定义,并以属性重要性为启发式信息,提出一种基于知识粒度的属性约简启发式算法,该算法的时间复杂度是多项式的,最后通过例子说明,该算法能得到不完备信息系统的一个约简。 相似文献
6.
7.
在现实应用中许多数据往往是动态变化的,静态的属性约简算法处理此类数据需消耗大量的计算时间和存储空间。针对集值决策信息系统中数据的动态变化情况,通过引入条件信息量和属性重要性概念,提出了一种启发式的动态属性约简算法,当新的属性集增加到决策信息系统时,算法能够利用原系统的属性约简结果,快速更新属性集增加后的属性约简,并对更新后的属性约简中可能存在的冗余属性进行反向剔除,保持了知识获取的简洁,提高了算法的计算效率。最后,通过实例验证进一步分析了算法的有效性和可行性。 相似文献
8.
一种基于Rough集理论的属性约简启发式算法 总被引:9,自引:1,他引:9
属性约简是知识发现中的关键问题之一.为了能够有效地获取决策表中属性的最小相对约简,在Rough集理论的基础上构造了一个新的算子,将信息论角度定义的属性的重要性作为启发式信息,来描述在决策表中条件属性所提供的知识对决策属性的影响;并采用宽度优先搜索策略,提出了一种新的属性约简启发式算法.以原始条件属性集为起点并结合算子,通过向属性核的递减式逼近,得到属性的最小相对约简.实例分析表明,该算法能有效地对决策表属性进行约简. 相似文献
9.
全粒度粗糙集时空复杂度较高,难于计算属性约简.针对此问题,文中利用等价类定义信息系统中的可区分度,并研究其性质,证明基于可区分度的属性约简等价于绝对约简.定义决策系统中的正区域可区分度,并探究其性质,证明基于正区域可区分度约简是全粒度Pawlak约简的超集,但绝大部分情况下等于全粒度Pawlak约简,可作为全粒度Pawlak约简的近似.理论分析和实验表明,相比其它属性约简算法,基于正区域可区分度约简在计算复杂度和分类准确率等方面具有较大优势. 相似文献
10.
11.
对于不完备决策表,给出了区分对象对集和基于区分对象对集约简的定义,并证明出基于区分对象对集的属性约简定义等价于基于广义决策的属性约简定义。在此基础上,提出一种基于区分对象对集的新算法。新算法以区分度[K(ci)]和完备度[P(ci)]为启发信息,结合基数排序,使得算法最终时间复杂度为[O(|C||U|2)],相比传统的算法时间复杂度[O(|C|3|U|2)]和[O(|C|2|U|2)],时间复杂度有效降低。通过实例说明了新算法的正确性和有效性。 相似文献
12.
13.
14.
对Skowron可辨识矩阵方法进行分析,并应用反例说明基于Skowron可辨识矩阵的属性约简算法对不相容决策表的属性约简,可能会导致错误的结果。针对这一问题,提出了一种基于改进可辨识矩阵的属性频率约简算法。该算法以改进的可辨识矩阵为基础,以属性频率作为启发信息,同时在算法中加入消除冗余属性二次约简过程。提供了实例分析,验证了该算法能够有效地对相容与不相容的决策表进行属性约简。 相似文献
15.
在不一致决策表中,以知识的包含度为基础,将一致和不一致对象分开,定义了一种新的属性重要性;为克服区分矩阵法时间复杂度随系统大小增加而指数增长的缺陷,给出分布约简的数学判定定理,提出了一种求分布约简的启发式方法。实例验证分析表明,新的属性重要性是一种更有效的启发式信息,该方法时间复杂度较低,有助于搜索最小或次优约简。 相似文献
16.
针对现有属性约简算法存在的问题,利用信息论和粗糙集理论,提出一种基于相对可辨识矩阵的决策表属性约简算法.该算法以核属性为基础,通过建立相对可辨识矩阵,利用条件信息熵作为启发式信息,减少属性约简过程中的搜索空间,逐个添加条件信息熵最大的属性,直到找出最小约简为止,并分析了该算法的时间复杂度.实例分析结果表明,该算法能有效地对决策表属性进行约简. 相似文献
17.
一种快速计算HU差别矩阵的属性约简算法 总被引:7,自引:0,他引:7
在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度, 首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性. 相似文献
18.
为了获得决策系统中更好的相对属性约简,本文提出了一种基于差别矩阵的启发式属性约简算法。该算法以求差别矩阵为基础,不仅考虑了所选择条件属性与决策属性的互信 息,还考虑了其取值的分布情况,从信息论角度定义了一种新的属性重要性度量方法,将其作为启发式信息,最终求得属性约简集。实例表明,算法能够有效地对决策系统进进行约简,获得比较理想的约简结果,同时约简后的决策规则数目较少。 相似文献
19.
属性约简是粗糙集理论研究的关键问题,针对求取决策系统所有约简的NP问题,基于差别矩阵提出一种决策系统属性约简优化算法.通过改进差别矩阵得到差别集,在获得核与约简候选信息基础上,以属性频度作为启发式信息,快速有效地求取决策系统的所有约简.分析表明了该算法的可行性与有效性. 相似文献
20.
目前已有蚁群算法优化的特征选择方法,大多采用的是以属性依赖度和信息熵属性重要度作为路径上启发搜索因子,但这类搜索方法在某些决策表中存在算法早熟或搜索到的特征子集包含了冗余特征,从而导致选择精度显著下降。针对此类问题,根据条件属性在分辨矩阵中的占比提出了一种属性重要度的度量方法,以分辨矩阵重要度作为路径上启发因子,设计了一种基于分辨矩阵与蚁群算法优化的特征子集搜索方法。该算法从特征核出发,蚁群依次选择概率大的特征加入特征核集,直至找到最小特征子集算法终止。通过实例验证和UCI数据集实验结果表明,与基于属性依赖度和信息熵属性重要度的特征选择方法相比,在通常情况下,该算法能较小代价找到最小特征子集,并且可以有效减少计算工作量。 相似文献