基于属性划分信息增益的函数依赖挖掘算法研究

发布时间：2021-01-14 07:04

　　随着互联网时代的进一步发展,数据成为了一种新兴的生产资料。当前,各行各业的信息系统中包含了大量的数据,尤以关系型数据为主,这些数据往往存在错误,难以有效利用。因此,人们希望能够找到一些行之有效的策略对数据进行修复,而在关系型数据中,函数依赖扮演了数据修复的重要角色。函数依赖（Functional Dependency）是关系模型中的一个重要概念,可被用于模式泛化,数据清洗,数据修复,数据整合等。关系数据下的函数依赖发现方法已经被研究数十年,并提出了各种函数依赖挖掘方法,但是仍旧残存了一些问题,例如挖掘属性数目庞大的数据库实例中的函数依赖时,算法速度仍然不理想。近年来传统的发现算法如深度优先遍历的DFD,其时间复杂度会呈现指数级上升。针对该问题,本文提出了属性划分信息增益这一概念,将原始DFD函数依赖发现算法和HYFD算法中的集中抽样方法相结合。首选使用属性划分间的信息增益列表改进原始DUCC算法中下一节点选择的随机游走备选策略,以此寻找唯一属性组合MUC,再通过集中抽样处理方法对数据集进行抽样计算得到非函数依赖,最后对单属性主键节点、非单属性主键、非函数依赖节点路线进行剪枝,并参考信息... 

【文章来源】：重庆邮电大学重庆市

【文章页数】：57 页

【学位级别】：硕士

【部分图文】：

adult数据集副本的具体错误数据

订正后的具体数据位置会被标记为绿色。图5.6 和图 5.7 分别为被标记的疑似错误数据和被订正的数据。表 5.3 为原始算法挖掘出的 FD 与插件挖掘出的 FD 的对比，数据中的第一个属性设置为编号 1，第二个属性设置为编号 2，以此类推。结果表明数据修订插件能够完全挖掘出正确的 FD。图 5.6 插件标记的疑似错误数据图 5.7 插件标记的订正数据

别为被标记的疑似错误数据和被订正的数据。表 5.3 为原挖掘出的 FD 的对比，数据中的第一个属性设置为编号 2，以此类推。结果表明数据修订插件能够完全挖掘出正图 5.6 插件标记的疑似错误数据


本文编号：2976455