基于清洗规则和主数据的数据修复算法实现

为了有效地清洗数据,此前已经提出了很多的完整性约束规则,例如条件函数依赖、条件包含依赖.这些约束规则虽然可以侦测出错误的存在,但是不能有效地指导用户纠正错误.实际上,基于约束规则的数据修复可能最终得不到确定性的修复结果,相反会引入新的错误,因此很大程度上降低了数据修复的效率.针对以上不足,提出了一种有效的数据清洗框架:首先基于Editing Rules和Master Data对数据进行清洗操作,最终得到确定性的修复;然后依据条件函数依赖来修复遗漏的错误,此种修复结果是不确定的,但是相比之下该框架不仅可以有效地保证数据修复的精确性与唯一性,而且提高了数据修复的效率.     

基于等价关系的关联规则挖掘算法研究

文章在现有关联规则挖掘算法的基础上,基于等价关系和等价类来生成侯选频繁项目集,它可以减少系统的开销;并利用参照数据集代替原始交易数据库进行侯选频繁项目集中支持度计数的测试,以此来减少对原始交易数据库的扫描次数。这种方法对于挖掘关联规则是有效的。     

基于等价类规则树的高效关联规则挖掘算法

传统的类关联规则挖掘方法在挖掘完整的规则数据集时往往需要消耗很长的时间。为了解决这个问题,提出一种高效的基于等价类规则树的类关联规则挖掘算法。首先,通过分析等价类规则树挖掘类关联规则算法存在的耗时问题,设计一个树结构存储数据集的频繁项集;接着,基于这棵树推导出一些修正树上节点和减少节点信息计算量的定理;最后,利用这些定理得到一个有效的适用于挖掘类关联规则的算法。实验结果表明,与其他较为先进的基于等价类规则树的关联规则挖掘算法相比,所提算法更加高效。     

基于函数依赖与条件约束的数据修复方法

随着经济与信息技术的发展,在许多应用中均产生大量数据.然而,受硬件设备、人工操作、多源数据集成等诸多因素的影响,在这些应用之中往往存在较为严重的数据质量问题,特别是不一致性问题,从而无法有效管理数据.因此,首要的任务就是开发新型数据清洗技术来提升数据质量,以支持后续的数据管理与分析.现有工作主要研究基于函数依赖的数据修复技术,即以函数依赖来描述数据一致性约束,通过变更数据库中部分元组的属性值（而非增加/删除元组）来使得整个数据库遵循函数依赖集合.从一致性约束描述的角度来看,函数依赖并非是唯一的表达方式,还存在其他表达方式,例如硬约束、数量约束、等值约束、非等值约束等.然而,随着一致性约束种类的增加,其处理难度也远比仅有函数依赖的场景要困难.本文考虑以函数依赖与其他一致性约束共同表述数据库的一致性约束,并在此基础上设计数据修复算法,从而提升数据质量.实验结果表明,本文所提方法的执行效率较高.     

基于Eclat算法的多种约束关联规则挖掘算法研究

在Eclat算法的基础上,将多种约束条件（反单调约束、单调约束、简洁性约束、可转变的约束）整合到关联规则的挖掘过程中,并给出了Eclat A、EclatM、EclatS、EclatCA等相应约束条件下的挖掘算法;实验结果表明所提出的算法是一种十分有效的解决基于多种约束条件下的关联规则挖掘算法。     

基于关联规则的条件函数依赖发现及数据修复

大数据时代,数据的来源复杂,数据质量存在严重问题,有些数据不准确、缺失或存在错误。不正确的数据严重影响了数据挖掘的质量,给决策造成重大的影响。关于缺失数据的修复方法很多,其中条件函数依赖就是一个有效的方法,在如何发现条件函数依赖方面已经有了很多研究成果。文中提出一种应用关联规则构建条件函数依赖的方法,由于关联规则通过数据挖掘得到,具有一定的隐蔽性,不是一般的方法能够发现,所以,由关联规则构建的条件函数依赖具有一定的应用价值,文中给出了构建方法,并通过实验证明其有效性。     

单调和反单调约束条件下关联规则的挖掘算法分析

本文充分利用了 Eclat算法的概念格理论和等价类划分方法,将约束条件融入基于垂直数据分布的关联规则挖掘算法中。提出了一种新的反单调和单调约束条件下关联规则的挖掘算法,分别为EclatA算法和EclatM算法。算法采用自底向上的搜索方法,在发现频繁项集的同时进行约束条件的检验。数据库的扫描次数较少,无需对候选项集进行剪枝,占用内存较小。实验证明:该算法的执行效率比已有算法有显著提高。     

大型数据库中多层关联规则的挖掘算法

将基于垂直数据分布的关联规则的发现从单层概念扩展到多层概念,提出了自顶向下的、用等价类生成频繁项目集的发现算法,无需复杂的Ｈａｓｈ数据结构。该算法减少了项目的匹配计算,提高了挖掘的效率。     

大数据环境下关联规则并行分层挖掘算法研究

为满足大数据实时处理的需求,提出了一种基于划分的关联规则并行分层挖掘算法(Parallel Hierarchical Association Rule Mining,PHARM)。首先,将整个数据库D随机分割成若干个非重叠区域,并行挖掘出局部频繁项集;然后利用先验性质,连接局部频繁项集得全局候选项集;再次扫描D统计出每个候选项集的实际支持度,以确定全局频繁项集。最后,建模分析了该算法的高效性。     

条件函数依赖及其在领域无关数据清洗中的应用

条件函数依赖(Conditional Functional Dependeny,CFD)是对函数依赖(Functional Depencency,FD)加入语义约束扩展而来,它在数据库一致性检测、数据清洗方面更优于后者.讨论了条件函数依赖的相关概念及其基本性质,讨论如何将它应用于数据清洗,并对已提出的基于CFD的数据清洗方案提出改进措施,并通过实验说明改进措施的可行性.     

两两比较模型的Why-not问题解释及排序

由于数据缺失,数据库用户通常无法获得查询结果中的预期答案.它被称为\"Why-not问题\",即\"为什么预期的元组不会出现在结果中\".现有的方法通过列举可能的元组值来解释Why-not问题.枚举所给出解释的数量往往太大,无法由用户探索.完整性约束,如函数依赖,被用来排除不合格的解释.然而,许多属性在简化后解释中仅仅表示为变量,用户可能仍然无法理解.由于数据稀疏性,许多不合理的解释也会被推荐给用户.提出通过研究元组间两两比较关系,从而对Why-not问题的解释进行排序的方法.首先,重新定义为什么Why-not问题解释的形式没有变量,以便于用户理解;其次,对元组中的相等/不相等关系进行表示,提出在{0,1}表示的元组对的基础上学习统计模型,从而解决直接在原始数据上学习所带来的稀疏性问题,许多模型可以被用来推断概率,包括统计分布、分类和回归;最后,根据推断的概率对解释进行评价和排序.实验结果证明：利用统计、分类和回归方法计算两两关系概率分布的方法,可以为用户寻找Why-not问题的解释并返回较为高质量的解释.     

一种条件函数依赖挖掘算法的分析与实现

条件函数依赖(Conditional Functional Dependence,CFD)的挖掘是一种重要的数据库分析技术,它是在函数依赖(Functional Dependence,FD)挖掘的基础上加入条件分析功能扩展而来,当前被应用于数据质量检测.CFD挖掘是在FD挖掘的基础上通过条件分析进行更细粒度的信息挖掘,其时间复杂度较高.文章详细介绍一种经典的CFD挖掘方法(即CTANE算法),对其实现方法提出了优化措施,并通过实验比较了不同实现方法的效率,得出了优化措施改进效率的结论.     

基于条件函数依赖的隐私保护模型

数据拥有者发布的数据中如果包含条件函数依赖会导致数据的隐私受到攻击,由条件函数依赖产生的属性间的关联会带来潜在的隐私泄露问题。针对现有的隐私保护方法均无法保护包含条件函数依赖的数据的隐私,形式化地定义了基于条件函数依赖的隐私攻击,提出了隐私保护模型l-deduction来对包含条件函数依赖的数据进行隐私保护;并设计了相应的匿名算法来实现l-deduction模型。理论分析和实验结果表明,该方法既能保护包含条件函数依赖的数据的隐私,又具有较小的信息损失度。     

分布式数据库中冲突检测技术研究

数据冲突是数据库中数据质量中心问题之一。在集中式数据库中,基于SQL技术可以有效地检测出违背给定条件函数依赖集的元组。然而,当数据库中数据被水平或垂直划分且分布在不同站点时,检测数据冲突将面临更大的挑战,常常需要将数据从一个站点移动到另外一个站点。提出了分布式数据库中条件函数依赖冲突检测算法,该算法不仅能有效地检测出水平划分数据中条件函数依赖冲突,而且能减少数据传输。实验结果证实算法是有效的。     

基于相关性分析的不完整数据函数依赖挖掘方法

函数依赖（FD）挖掘方法通常专注于发现所有满足函数依赖语法特征的结果,在数据不完整的情况下常导致大量成立但无意义的FD。针对挖掘无效FD的问题,提出基于相关性分析的不完整数据FD挖掘方法。利用概率图模型构建具有缺失值属性的概率分布,通过相关性分析捕捉属性之间的关联关系,避免枚举所有可能性,以挖掘具有统计学意义的FD。实验结果表明,提出方法可以更准确的定位到有意义的FD,与最先进的FD发现方法相比F1分数平均提高1.5倍。     

基于常量条件函数依赖的冲突消解算法

目前绝大部分冲突消解方法都是基于迭代计算数据源可靠度和事实可信度的机制。当数据源较少时,数据源的可靠度难于进行评估,仅凭投票来消解冲突往往会造成较大误差。针对数据源较少时的冲突消解问题,提出基于常量条件函数依赖的冲突消解算法。根据多个数据源之间的冲突,找出冲突匹配对及对应的冲突候选值集合。考虑常量条件函数依赖中具体到部分实例子集的约束关系,将常量条件函数依赖集作为先验知识,通过判断候选值是否符合常量条件函数依赖来选择正确的候选值,避免了错误数据比例较大时直接投票选择产生的误差。通过两个真实数据集上的对比实验验证了上述算法的有效性。     

基于条件函数依赖的CTANE算法研究与应用

针对复杂庞大有研究价值的数据,查找其中蕴含的条件函数依赖可以有效地利用这些有价值的数据。但现有的条件函数依赖搜索算法在面对庞大的数据时查找效率较慢,所以对现有的算法的改进意义重大。针对水利普查数据的特点对查找条件函数依赖的算法进行了改进,在原有算法的基础上加入了剪枝策略。实验和理论证明,改进后的算法相比传统的搜索算法在保证搜索质量的前提下加快了搜索速度,使得查找数据中的条件函数依赖更加快捷便利。