论文研究-基于信息熵的不完备信息系统属性约简算法 .pdf

所需积分/C币:10 2019-08-22 09:16:59 270KB .PDF
6
收藏 收藏
举报

基于信息熵的不完备信息系统属性约简算法,付昂,胡军,从信息论角度出发引入信息熵的概念,定义了知识的熵,提出了基于信息熵的不完备信息系统知识约简算法,该算法支持多种Rough集关系�
山国科技义在线 若∈,y=y,则称是最大分布集。若的任意真子集都不是最大 分布集,则称为最大分布约简。 若∨∈,δ=δ,则称是分配集。若的任意真子集都不是分配集, 则称为分配约简。 若Ⅴ∈,p=p,则称是分配序集。若的任意真子集都不是分配序 集,则称是分配序约简。 由定义知,分布约简保证每个相容类对决策类的隶属程度不变;最大分布约简保持每 个相容类的最大分布决策类不变;分配约简保持每个对象的相容类的所有可能决策类不变, 即不产生新的不一致;分配序约简保持辱个相容类对决策类隶属度大小顺序不变 定理不完备信息系统 ,c,则有以下关系成立 若是分布集,则是分序集; 若是分配序集,则是最大分布集 若是分配序集,则是分配集 现有的亢备信息系统的属性约简方法主要是要保证约简后信息系统的正域不发生变化, 即约简后的决策表系统应和约简前能识别相同的对象。在完备信息系统中,有下面命题成立 命题给定一个完备信息系统 为条件属性集,为决策 属性集,若cc,则 对于不完备信息系统,上述命题不再成立,因此使用止域不发生变化作为约简的定义不 再合适。文献提出了利用系统的近似分类质量不降低作为约简的约束条件,并给出了相应 的知识约简算法。近似分类质量不降低也就保证了能识别的记录个数不减少,这一条件在完 各信息系统和不完备信息系统都是适用的。 基于信息熵的启发式知识约简算法 定义令决策表系统为 ∪是属性集合,子集和分 别为条件属性集和决策属性集,且决策属性的值域为 A,则对于集合 c,定义其信息熵为 其中 为集合中决策属性值为的实例个数, 为集合的基数 一般有 信息熵越小,说明集合中个别决策属性值占导地位,因 此混乱程度越小,特别有当且仅当集合中实例的决策属性值都相同吋 定义令决策表系统为 ,=(是属性集合,子集和分 别为条件属性集和决策属性集,在关系下知识属性集合ε在论域上形成的分类为 A Y。定义知识的熵为 由定义易知。定义反映了知识对信息系统分类能力的强弱。若 越大,则说明由知识在论域上形成的分类中各决策属性值分布越均匀,即混乱程度 越大,故说明知识对信息系统的分类能力越弱;反之,则说明知识对信息系统的分 山国科技义在线 类能力越强。当 时,说明决策表信息系统在知识下所有样例的分类都不存在 不一致的情况,即在知识下该信息系统是确定的,可以从中得到完全确定的规则 定义令决策表系统为 =U是属性集合,子集和分 别为条件属性集和决策属性集,属性集合∝,则对」任意属性∈的重要性 定义为 的值越大,说明属性对属性集合的分类能力影响越大,即对」属性集合 越重要。 将定义给出的属性重要性作为启发知识,以空集为约简的起点,逐个选择最重要的属 性加入约简集合中,直到约简集合的熵不人于整个条件属性集的熵。中此我们给出基于属性 重要性的启发式约简算法,为以后讨论方便简记为 算法。 算法 算法 输入:一个决策表 为论域 是属性集合,子集和 分别为条件属性集和決策属性集 输出:该决策表的一个约简 第步初始化 第步若 ≤,则转第步;否则,转第步; 第步计算每个条件属性 的属性重要性,选取重要性最大君属性重要性相 同,则选取熵值最小的属性, 转第步 第步算法结束。 下面欢 算法的时间复杂度进行分析。该算法核心在于求 ,也即求取 关于属性集的所有划分类。针对完备信息系统,可以应用文畎提出的算法,该算法 的时间复杂度为 算法时间复杂度为 。对于不完备信 息系统,本文以谷差关系为例提出了求取对象谷差类的算法,该算法具有较低的吋间复 杂度,且对于其它扩充关系模型限訇容差关系,非对称相似关系只需作少量变动也是适用 的。 算法计算所有对象的关于属性集的容差类 输入:一个决簧表 是属性集合,子集和分别为 条件属性集和决策属性集,ε且属性 的值域为 值 作为特殊值, A为论域中条件属性值为的实例个数 输出:所有对象的关于属性集的容差类 第步对每一个属性∈,统计 记 最小佰对应的属性为 ′的最大值和最小值分别记为和; 第步建立 个空队列:对论域中每一对象,如果 =*,则分配 到第 队列中去;否则分配到第-队列中去 第步对所有非空队列依次执行循环:设当前非空队列中对象个数为,将队列中第 个对象和第=+A个对象比较,如果满足容差关系,则互相加入对方 山国科技义在线 容差类。 第步将 =的队列即第 +队列中每个对象,依次和前面的 个队列如果该队列非空中每一个对象比较,如果满足容差关系,则互相加入对 方的容差类 第步算法结束。 记属性的值域为 A空值 作为特殊值, A为论 域中条件属性值为的实例个数,且所有条属性中对应的=∑值最小。易知 算法的时问复杂度为 ,由于实际决策表中条件属性的不同属性值个数 通常情况下有>,因此有∑ 。所以,对于不完备信息系统, 算法时间复杂度为 为了说明 算法的性能,在信息系统不完备情況下,我们将该算法和分配约简 算法及黄海提出的启发式约简算法简记为 进行了比较分析和试验对比;在信 息系统亢备情况下,我们将该算法和 算法及苗夺谦等人针对完备信息系统提出的 基于互信息的知识约简算法 进行了分析比较和试验对比。 以上四种算法都風于基于属性重要怛的启发式约简算法,但是它们的理论出发点是不同 的。 算法和 算法从信息论的角度出发,引入了熵的概念,其中 算法以知识的熵为基础定义了属性重要性作为启发式信息,并以≤作为约束条 件; 算法是建立在条件属性与决策属性对于决策的相对重要度基础上,并以此为 启发式信息,以互信息相等作为算法的终止条件。 算法和分配约简算法则是从代 数观的角度出发,其中 算法在近似分类质量的基础上定义属性重要性作为启发式 信息,用近似分类质量不降低作为约朿条件;分配约简算法通过建立属性的分配矩阵,用分 配矩阵之间的距离定义属性重要性作为启发式信息,并以条件属性子集的分配矩阵等于条件 属性集的分配矩阵为算法终止条件。 下血讨论一下以上四种算法的时间复杂性。 算法的时间复杂度前血已讨论过, 算法的时间复杂度为 ,分配约简算法和 算法的时 间复杂度都为 综上所述, 算法的时间复杂度是最低的 仿真实验 实验选用了机器学习数据库中的个数据集,并结合 系统试验平台,分别在 不完备系统情形下和完备系统情形下比较了四科算法的约简结果和约简所需时间。所有数据 集被随机分为两半,一半用于知识约简,一般用于测试。 山国科技义在线 表不完备情况下基于容差关系知识约简算法比较 算法 算法 分配约简算法 样本 数量門简约简时间识别率约简结约简时间识别约简约简时间识别 果 率倮果 表不完备情况下基于限制容差关系知识约简算法比较 据 算法 算法 分配约简算法 样本 数量约简结简时间识别约简结约简时间识别约简结约简时间识别 集序 果 率倮果 果 表不完备情况下基丁相似关系知识约简算法比较 算法 算法 样本 分配约简算法 约简结约简时间识别约简结约简时间识别简结简时间识别 数量 果 率果 率 表完备情形卜约简过程的计算时间比较结果 徼据 算法 算 算法 样本 /数量约简结简时间识别约简结约简时间识别简结简时间识别 集序 果 率果 果 山国武技文在线 实验结果表明,在时间复杂度上,对同一数据集 算法相对是最小的。在数据 集规模较小情况下,算法之间的时间差距不人;随着数据集规模的増人, 算法与 其它算法的差距越明显,说明了 算法在时间效率上的优势。 对于约简结果,由表所示的在限制容差关系下的约简结果可以看出, 算法 和 算法约简结果相当,而且在识别率上都比分配约简要高,这是因为 算 法和 算法约简的依据都是建立在寻找在分类能力上与属性集相当的属性子集,即 保持约简结果的分类能力不降低,而分配约简的依据是建立寻找保持所有可能决策类不变的 最小属性了集,即保持约筍结果不产生新的不·致。由衣所示的在等价关系下的约简结果 可以看出, 算法和 算法约简结果相当,而且在部分数据集上,约简结果 的识别率较 算法低,体现了知识约简在代数观和信息观下的差异。 综上所述,本文提出的 算法对属性约简是可行的,而且在算法效率上相比其 它算法也有一定的提高。 结语 本文从信息论角度出发引入信息熵的概念,定义了知识的熵,提出了基于信息熵的不 完备信息系统知识约简算法,该算法支持多种已有的 集关系扩`展模型,并且适用于 各信息系统。通过与已有的知识约简算法的比较分析,说明了本文提出的算法对于知识约简 是可行的,而且在效率上比其它算法有所提高。 参考文献 王国胤何晓一种不确定性条件下的自主式知识学习模型软件学报 黄兵基于粗糙集的不完备信息系统知识获取理论与方法南京南京理工大学 顾沈明吴伟志髙济不完备信息系统中知识获取算法计算机科学 黄海王国胤吴渝一种不完备信息系统的直接约简方法小型微型计算机系统 李然林和李永礼高效的不完备信息系统知识约简算法计算机工程与应用 闫德勤概率差別矩阵与不完备信息系统属性约简计算机科学 冯朝一梁家荣 基于集合覆盖的不完备信息系统属性约简方法计算机应用 周献中黄兵基于粗集的不完各信息系统属性约简南京理工大学学报 谢宏程浩忠牛东晓基于信息熵的粗糙集连续属性离散化算法讣算机学报 徐章艳刘作鹕杨炳儒等一个复杂度为 的快这属性约简算法 计算机学报 山国武技文在线 作者简介: 付昂,男, 年生,硕士研究生,主要研究方向是智能信息处理,粒计算: 胡军,男 年生,博士研究生,讲师,主要研究方向包括知识发现,粒计算,粗糙集

...展开详情
试读 8P 论文研究-基于信息熵的不完备信息系统属性约简算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840588 如果觉得有用,不妨留言支持一下
2019-08-22
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚积分or赚钱
最新推荐
论文研究-基于信息熵的不完备信息系统属性约简算法 .pdf 10积分/C币 立即下载
1/8
论文研究-基于信息熵的不完备信息系统属性约简算法 .pdf第1页
论文研究-基于信息熵的不完备信息系统属性约简算法 .pdf第2页

试读结束, 可继续读1页

10积分/C币 立即下载 >