粗等价粒度下基于多种加速策略的增量式求核算法

• 作者: 张恺航 徐克付 梁俊杰 董振宁 赵洁
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 粗糙约简 粗等价类 渐增式求核 Hash
• 年，卷（期）: 2017,（1）
• 所属期刊栏目: 人工智能
• 页码范围: 226-234,258
• 页数: 10页
• 分类号: TP311
• 字数: 12617字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2017.01.043

摘要

提出一种全新的渐增式求核算法.首先基于全局等价类提出粗等价类概念并分析其性质,研究粗等价类下的求核与约简;深入研究3类粗等价类与核属性的内在联系,设计粗等价类下判断核属性的等价方法和渐增式求核方法,通过该方法可在一次增量计算中求得多个非核属性,从而设计双向剪枝策略;可从属性和实体双方面缩减计算域,无需遍历全部属性和实体,在无核情况下,剪枝策略仍然有效.设计多次Hash的属性增量划分算法来完成上述增量式计算,基于此给出完整的渐增式求核算法.最后用UCI中20个决策表及海量、超高维3类数据集从多个角度进行验证,实验结果证明了所提算法的有效性和高效性,其尤其适用于大型决策表,大多数情况下优于现有算法.算法可进一步作为新型约简和优化算法的基础.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	董振宁		53	170	7.0	11.0
2	赵洁		32	151	8.0	10.0
3	张恺航	中国科学院信息工程研究所	4	3	1.0	1.0
4	徐克付	中国科学院信息工程研究所	14	162	6.0	12.0
5	梁俊杰		4	12	2.0	3.0