论文部分内容阅读
摘 要 针对大多数属性约简算法时间复杂度比较高的问题，利用粗糙集理论提出了一种新的解决办法，该方法基于相似矩阵概念，利用属性在相似矩阵中出現的频率给出了属性重要性的计算公式，以此作为启发式知识来约间决策表中的冗余属性，并将折半查询的思想运用到算法中以加快约简的速度。实验表明该算法是简单有效的。
关键词 粗糙集；相似矩阵；折半属性约简
中图分类号：TP18 文献标识码：A 文章编号：1671-7597（2013）16-0051-01
粗糙集理论是一种能有效地分析不精确、不一致、不完整等各种不完备信息、揭示潜在规律的处理不确定性和模糊性数据的工具。属性约简是粗糙集理论研究的核心内容之一，到目前为止，已经提出了多种改进型的属性约简算法。
本文提出了一种新的属性约简算法，在文中给出了相似矩阵的定义，从另一个角度来计算属性的重要性，并且将折半查找的思想运用到算法中，加快了筛选候选属性的速度。
1 基于相似矩阵的折半属性约简算法
1.1 算法的基本思想
可辨识矩阵主要是从对象与对象之间的差别来研究属性约简。
1.1.1 相似矩阵的定义
cij= {a∈C | xi（a）=xj（a）}，xi（d）≠xj（d）；
cij=|，其他
Cij代表两个对象之间的相似点，也就是不能辨别对象的属性集。根据相似矩阵的定义，得到下面的结论：属性在相似矩阵中出现的次数越多，在相似矩阵中的项长度越短，则代表该属性在反映对象相似性上起的作用越大，因此在区别对象时，重要性就越小。根据上述观点，本文基于相似矩阵的属性频率给出了属性重要性的计算公式：
F（a）= -
其中，当a时，=0；否则=1。card（）表示包含属性的个数。
推论1：当且仅当card（）=card（c）-1时，C-属于核属性。
1.1.2 折半约简概述
现在很多约简算法都是从R=核（core（c））开始，判断R是否为一个约简，是则终止，否则根据属性的重要性定义，将重要性最大的一个加入到R中，再次测试是否为约简，若是则终止，否则，继续上述过程。
1.2 算法过程描述
本文提出具体过程描述：
输入：一致决策表S=（U，C∪D，V，F），其中C = {a1，a2，…，an}
输出：决策表的约简集合R
Step 1：决策表S转换为相应的相似矩阵M，求出核属性core（C），并计算剩余属性的属性重要度，然后将剩余属性根据重要度由大到小进行排序，放进数组Z.
Step 2：初试化R=core（c），如果=，则执行步骤step4，否则执行步骤step3。
Step 3：初试化min=1；max=card（C）-card（core（C））
while（true）{
Tempt=R； //保存改变前的R
Mid=min+max/2；
将数组z中第min个到第mid个加入到R中， 计算；
If（<）{
If（max-mid<=1）{
① 将数组z中第max个加入R中；
② 退出循环； //退出位置一
}
else {
min=mid+1；
} }
Else if（=）{
If（max-mid<=1）{
③ 退出循环；//退出位置二
}
Else{
④ max=mid；
R=tempt； //将R还原为本次改变前的状态
}}}
Step4：程序结束，R就是要求的约简。
1.3 算法时间复杂度分析
该算法step1所需的时间复杂度为O（|C|*|U?|*|U|），进入是step2后，关键的步骤是求取属性的近似精度，求取近似精度的时间复杂度为O（|u|*|u|*|u|）。由于采用了折半查找的思想，使得在最坏的情况下，不需要遍历整个条件属性集，只需遍历log|C|次，故时间复杂度为O（log|C|*|u|*|u|*|u|）。
2 算法实例分析
给定一致信息表S=（U，A，V，F），其中U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}，A = {a，b，c，d，e，f，g，h}，其中条件属性C={a，b，c，d，e，f，g}，决策属性D={h}，由表1给出。
首先执行step1与step2，得到相似矩阵，并求出核属性core（C）={A}，及C/core（C）属性的重要性，得到：f（b）、f（c）、f（d）、f（e）、f（f）、f（g），将候选属性按重要性的定义由到大到小排序放进数组Z.={a，b，e，f，d，c，g}，直至max-mid<=1，则将第max个加入到R中，退出循环，R={a，g，b，e}。
可以看到仅经过两次扩展计算，就得到了最后的约简，如果按传统的算法得扩展三次。可见，提高了约简的速度。当候选属性更多时，本算法的优越性越明显。
参考文献
[1]曾黄麟.粗集理论及其应用（修订版）[M].重庆大学出版社，1998.
[2]刘震宇.粗糙集约简算法在知识发现中的研究与应用[D].西安：西安电子科技大学，2002.
[3]苗夺谦，胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展，1999，36（6）：681-684.
关键词 粗糙集；相似矩阵；折半属性约简
中图分类号：TP18 文献标识码：A 文章编号：1671-7597（2013）16-0051-01
粗糙集理论是一种能有效地分析不精确、不一致、不完整等各种不完备信息、揭示潜在规律的处理不确定性和模糊性数据的工具。属性约简是粗糙集理论研究的核心内容之一，到目前为止，已经提出了多种改进型的属性约简算法。
本文提出了一种新的属性约简算法，在文中给出了相似矩阵的定义，从另一个角度来计算属性的重要性，并且将折半查找的思想运用到算法中，加快了筛选候选属性的速度。
1 基于相似矩阵的折半属性约简算法
1.1 算法的基本思想
可辨识矩阵主要是从对象与对象之间的差别来研究属性约简。
1.1.1 相似矩阵的定义
cij= {a∈C | xi（a）=xj（a）}，xi（d）≠xj（d）；
cij=|，其他
Cij代表两个对象之间的相似点，也就是不能辨别对象的属性集。根据相似矩阵的定义，得到下面的结论：属性在相似矩阵中出现的次数越多，在相似矩阵中的项长度越短，则代表该属性在反映对象相似性上起的作用越大，因此在区别对象时，重要性就越小。根据上述观点，本文基于相似矩阵的属性频率给出了属性重要性的计算公式：
F（a）= -
其中，当a时，=0；否则=1。card（）表示包含属性的个数。
推论1：当且仅当card（）=card（c）-1时，C-属于核属性。
1.1.2 折半约简概述
现在很多约简算法都是从R=核（core（c））开始，判断R是否为一个约简，是则终止，否则根据属性的重要性定义，将重要性最大的一个加入到R中，再次测试是否为约简，若是则终止，否则，继续上述过程。
1.2 算法过程描述
本文提出具体过程描述：
输入：一致决策表S=（U，C∪D，V，F），其中C = {a1，a2，…，an}
输出：决策表的约简集合R
Step 1：决策表S转换为相应的相似矩阵M，求出核属性core（C），并计算剩余属性的属性重要度，然后将剩余属性根据重要度由大到小进行排序，放进数组Z.
Step 2：初试化R=core（c），如果=，则执行步骤step4，否则执行步骤step3。
Step 3：初试化min=1；max=card（C）-card（core（C））
while（true）{
Tempt=R； //保存改变前的R
Mid=min+max/2；
将数组z中第min个到第mid个加入到R中， 计算；
If（<）{
If（max-mid<=1）{
① 将数组z中第max个加入R中；
② 退出循环； //退出位置一
}
else {
min=mid+1；
} }
Else if（=）{
If（max-mid<=1）{
③ 退出循环；//退出位置二
}
Else{
④ max=mid；
R=tempt； //将R还原为本次改变前的状态
}}}
Step4：程序结束，R就是要求的约简。
1.3 算法时间复杂度分析
该算法step1所需的时间复杂度为O（|C|*|U?|*|U|），进入是step2后，关键的步骤是求取属性的近似精度，求取近似精度的时间复杂度为O（|u|*|u|*|u|）。由于采用了折半查找的思想，使得在最坏的情况下，不需要遍历整个条件属性集，只需遍历log|C|次，故时间复杂度为O（log|C|*|u|*|u|*|u|）。
2 算法实例分析
给定一致信息表S=（U，A，V，F），其中U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}，A = {a，b，c，d，e，f，g，h}，其中条件属性C={a，b，c，d，e，f，g}，决策属性D={h}，由表1给出。
首先执行step1与step2，得到相似矩阵，并求出核属性core（C）={A}，及C/core（C）属性的重要性，得到：f（b）、f（c）、f（d）、f（e）、f（f）、f（g），将候选属性按重要性的定义由到大到小排序放进数组Z.={a，b，e，f，d，c，g}，直至max-mid<=1，则将第max个加入到R中，退出循环，R={a，g，b，e}。
可以看到仅经过两次扩展计算，就得到了最后的约简，如果按传统的算法得扩展三次。可见，提高了约简的速度。当候选属性更多时，本算法的优越性越明显。
参考文献
[1]曾黄麟.粗集理论及其应用（修订版）[M].重庆大学出版社，1998.
[2]刘震宇.粗糙集约简算法在知识发现中的研究与应用[D].西安：西安电子科技大学，2002.
[3]苗夺谦，胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展，1999，36（6）：681-684.