摘要
在不一致决策表中定义了k阶分配序约简,给出了k阶分配序一致集的判定定理。通过定义k阶分配序区分矩阵,给出了求k阶分配序约简的区分矩阵法。为了克服区分矩阵法时间复杂度过高的缺陷,通过定义属性的相对重要性,提出了一种求k阶分配序约简的启发式算法,分析得到该算法的时间复杂度是多项式的结论。实例验证了算法的有效性。
Knowledge reduction is one of the most important tasks in rough set theory. The k-ordered assignment reduction is defined in inconstant decision tables, which maintains the first k membership orders of the equivalence classes determined by attributes set to the decision classes determined by decision attributes set. The judgment theorem and discernibility matrix with respect to consistent ordered assignment set are obtained, by means of which, the method of k-ordered assignment reduction is presented. To overcome the disadvantage of ordered assignment reduction based on discernibility matrix because the time complexity is exponential, a heuristic algorithm based on the significance of attributes is proposed, which aims at acquiring one of the minimal k-ordered assignment reduction. The time complexity of the algorithm is analyzed. The experimental result shows that the algorithm is valid.
出处
《计算机工程》
CAS
CSCD
北大核心
2007年第5期16-19,共4页
Computer Engineering
基金
国家自然科学基金资助项目(70571032)
江苏省教育厅高校自然科学研究指导性计划基金资助项目(05JKD520102)
中国博士后科学基金资助项目(20060390916)
江苏省博士后科研计划基金资助项目
南京审计学院科学研究基金资助项目(NSK2006/A03)
关键词
信息系统
粗糙集
不一致决策表
k阶分配序约简
区分矩阵
Information systems
Rough sets
Inconstant decision table
k-ordered assignment reduction
Discernibility matrix