基于HORAFA算法的改进增量数据挖掘算法.pdf

2009 年9 月 四川师m大学学报(自然科学版) Sept. ,2009 第 32 卷第5 期 Joumal of Sichuan Normal University( Natural Science) Vol. 32 ,No. 5 基于 HORAFA 算法的改进增量数据挖掘算法 党圣鸣， 高敬缓， 姚宏 (河北建材职业技术学院，河北秦皇岛 066004) 摘要:数据挖掘技术是机器学习、数据库和统计理论相结合的产物，具有较为广泛的应用前景.粗糙集 理论是80 年代初由波兰数学家首先提出的一种刻画不确定性和不完整性知识的数学工具.研究了基于属 性频率的启发式属性约简算法，此算法提高了挖掘速度. 关键词:数据挖掘;粗糙集;约简; HORAFA 中图分类号:TP181 文献标识码:A 文章编号: 1001-8395(2009) 05 -0707-04 dOÌ:I0. 3969/j. Ìssn.l001 -8395.2009. 05. 034 方法使得更新后的上下近似可以用原属性集合的 1 粗糙集的基本约简算法 上下近似及原属性集合的边界，新增单个属性的上 1. 1 属性约筒 属性约简的方法有很多，但不论 下近似，新增单个属性的边界来表示.这使得增加 采用什么方法，人们对于约简的目的都是一样的: 一个属性时，上下近似的更新只需计算单个属性的 在不损失原有信息系统信息的前提下获取最佳属 上下近似. 性约简.最佳可以指多方面的，比如获得的是含有 计算属性重要性的复杂度:属性的重要性在于 属性最少的约简，或是所得约简可以获得最优的决 去掉该属性后正区域的变化大小，其时间复杂度主 策规则，再或是获得的约简可以使得数据量约简最 要取决于正区域.因此计算属性重要性的时间复杂 大.目前，一般考虑的最佳约简指的是属性最少的 度和计算上下近似的复杂度相同. 约简.但是遗憾的是，研究人员已经证明求取任意 计算核的复杂度:核的计算可以根据属性的重 问题的最佳属性约简是一个 NP 复杂问题，即当数 要性来计算，通过测试核P 中每个属性的重要性来 据库中数据量增大时，该问题的复杂度将以指数增 决定.因此计算核的复杂度为 O( IP 川AIIUllnIUI) ， 加.属性之间可能隐含着潜在的相关性，因此对任 其中 P 是条件属性的子集. 意的信息系统或决策系统只可能求得相对约简集， 1. 3 典型算法 在约简算法中，最直观的就是用 也就是说可能是许多属性的组合. 删除法，这个方法依次从数据表中删除属性，将删 1.2 相关概念的计算复杂度 计算等价关系的复 除属性后的数据表和原数据表的决策类的等价关 2 杂度:求等价