计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2010年
6期
120-123
,共4页
钱文彬%徐章艳%黄丽宇%杨炳儒
錢文彬%徐章豔%黃麗宇%楊炳儒
전문빈%서장염%황려우%양병유
粗糙集%信息熵%简化的二进制差别矩阵%属性约简%算法复杂度
粗糙集%信息熵%簡化的二進製差彆矩陣%屬性約簡%算法複雜度
조조집%신식적%간화적이진제차별구진%속성약간%산법복잡도
rough set%information entropy%simplified binary discernibility matrix%attribution reduction%algorithm complexity
给出一个简化的二进制差别矩阵的属性约简定义,并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的.为求出简化的二进制差别矩阵,设计了一个快速求简化决策表的算法,其时间复杂度为O(│C││U│).在此基础上,设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法,其时间复杂度和空间复杂度分别为max{O(│C││U│),O(│C│~2│U/C│~2)}和max{O(│C││U/C│~2),O(│U│)},最后用一个实例说明了新算法的高效性.
給齣一箇簡化的二進製差彆矩陣的屬性約簡定義,併證明該屬性約簡的定義與基于信息熵的屬性約簡的定義是等價的.為求齣簡化的二進製差彆矩陣,設計瞭一箇快速求簡化決策錶的算法,其時間複雜度為O(│C││U│).在此基礎上,設計瞭基于信息熵的簡化二進製差彆矩陣的快速屬性約簡算法,其時間複雜度和空間複雜度分彆為max{O(│C││U│),O(│C│~2│U/C│~2)}和max{O(│C││U/C│~2),O(│U│)},最後用一箇實例說明瞭新算法的高效性.
급출일개간화적이진제차별구진적속성약간정의,병증명해속성약간적정의여기우신식적적속성약간적정의시등개적.위구출간화적이진제차별구진,설계료일개쾌속구간화결책표적산법,기시간복잡도위O(│C││U│).재차기출상,설계료기우신식적적간화이진제차별구진적쾌속속성약간산법,기시간복잡도화공간복잡도분별위max{O(│C││U│),O(│C│~2│U/C│~2)}화max{O(│C││U/C│~2),O(│U│)},최후용일개실례설명료신산법적고효성.
The definition of attribution reduction of simplified binary discernibility matrix is provided.At the same time,it is proved that the above definition of attribution reduction is the same as the definition of attribution reduction based on information entropy.In order to compute simplified binary discernibility matrix,a quick algorithm for simplified decision table is designed,its time complexity is O(│C││U│).In this condition,a quick attribution reduction algorithm based on simplified binary discemibility matrix of information entropy is designed,the time complexity and space complexity of the new algorithm are max{O(│C││U│),O(│C│~2│U/C│~2)} and max{O(│C││U/C│~2),O(│U│)} respectively.At last,an example is used to illustrate the efficiency of the new algorithm.