现实世界中的数据存在各式各样的错误,例如数据不一致、数据不准确、数据分类错误等,因此数据清洗在数据分析与管理的过程中显得尤为重要。传统的数据清洗算法存在错误检测不完全和清洗方式不正确的问题,且大多不能有效地利用外部资源(例如知识库和用户)来清洗数据。为了提高清洗的准确度并应对大数据时代的挑战,本文从三个方面研究结构化数据的清洗技术,包括基于完整性约束的数据清洗、基于规则的数据清洗和人机协作的数据清洗,同时设计了高效的算法和索引技术。具体来说,本文的主要研究内容和贡献包括:1.基于函数依赖的数据冲突检测与消除:目前基于函数依赖的清洗算法大多存在错误检测不完全的问题,因此本文重新定义了函数依赖下的数据冲突和数据一致性,这种新的定义基于字符串相似度,而不是传统的基于字符串相等的冲突检测方式。本文提出了一种新的代价模型来衡量数据清洗的代价,并证明在这种新的模型下,寻找到对应修改代价最小的清洗结果是NP难问题。因此,本文提出了扩展算法和贪心算法分别找到最优的和近似最优的清洗方式,并设计了索引和优化技术以提高算法效率。实验表明,本文提出的清洗模型可以更好地检测和修复错误,大幅度提高清洗的精确率和召回率。2.基于知识库的错误数据检测与修复:本文研究了如何利用知识库检测和修复关系表中的错误数据,同时标记正确的数据。本文提出了一种新的数据清洗规则,它通过在关系表和知识库之间建立联系来检测数据的正误。本文给出了该规则的形式化定义,同时研究了该规则的基本性质,例如规则一致性和蕴含性。本文设计了利用该规则来清洗关系表的高效清洗算法并讨论了规则的生成问题。在真实数据集和合成数据集上的实验结果证明了该规则在实际应用中的准确性和效率。3.人机协作的错误数据检测与消除:本文研究了人机协作的错误分类实体的发现问题。本文提出一种基于规则的框架来解决此问题:该框架首先利用正规则对实体进行分组,包含实体数量最多的组即是正确分类的组,也称为中心分区,然后利用负规则找到与中心分区中的实体不相似的记录,这些记录会交由用户判断是否为错误分类的实体。本文设计了高效的基于签名的“过滤-验证”框架,以提高正/负规则的执行效率。通过用户的数据检测记录,本文还讨论了如何生成正/负规则。在真实数据集上的实验证明了此解决方案的有效性。