基于相似紧邻的缺失数据填补关键技术研究

Incomplete information often occurs along with incomplete entry, inaccurate extraction or heterogeneous schemas. Applications built upon such data with missing information are not reliable. As one of the fundamental aspects in data quality, missing data imputation has been highlighted in both academy and industry. The idea of data imputation is to fill the missing data with the values of its neighbors who share the same information. Unfortunately, owing to data sparsity, the number of neighbors (identified w.r.t. value equality) is rather limited, especially in the presence of data values with variances. In this proposal, we argue to extensively enrich similarity neighbors by similarity rules with tolerance to small variations. More fills can thus be acquired that the aforesaid equality neighbors fail to reveal. To the best of our knowledge, this is the first study on imputing missing data by similarity neighbors. With both theoretical and practical concerns, we propose to study the problem of similarity neighbor-based data imputation in the following aspects: (1) the hardness analysis on solving and approximating the problem, (2) exact algorithms for tackling the problem, and (3) efficient approximation with performance guarantees. We believe that our proposed theoretical results and effective methods can be applied in various applications such as the cleaning and management of personal information on the Web, or event log in enterprise systems.

由于不完整输入、数据抽取错误、异质数据格式等众多原因，数据缺失的情况非常普遍，严重影响各种应用的可靠性。缺失数据填补作为数据质量管理的基础问题之一，引起学术界和工业界广泛关注。现有的数据填补方法受数据稀疏性和多样性所限，紧邻缺乏，导致大量空值无法被填补。本项目首次提出基于相似紧邻的填补策略，即利用数据之间的相似关系（而非传统的相等关系），识别更多的紧邻，从而增加缺失数据填补的机会。基于相似紧邻的缺失数据填补在国际上是首次被提出，面临许多新的挑战，亟待解决。本项目拟从理论和实践的角度，对相似紧邻填补问题进行如下研究：(1) 相似紧邻填补问题的复杂度、可近似度等理论基础分析；(2) 基于相似紧邻的最优填补计算方法；(3) 高效率近似填补算法及其近似比率保证等。最终形成一套完整的相似紧邻填补理论成果和高效率填补计算方法，并应用于互联网个人信息、企业日志信息的清理与管理等社会生活和生产的重要领域。

由于不完整输入、数据抽取错误、异质数据格式等众多原因，数据缺失的情况非常普遍，严重影响各种应用的可靠性。缺失数据填补作为数据质量管理的基础问题之一，引起学术界和工业界广泛关注，被认为是影响数据质量的一个重要问题。数据填补的常用方法是利用和不完整元组相似的其他元组中含有的相似信息来填补缺失数据。这些邻居通常可以通过编辑规则或者相似关系来确定。然而现有的数据填补方法受数据稀疏性和多样性所限，紧邻缺乏，导致大量空值无法被填补。为了应对这一问题，得到更丰富的填补候选值以更好地填补缺失数据，本项目首次提出基于相似紧邻的填补策略，即利用数据之间的相似关系（而非传统的相等关系），识别更多的紧邻，从而增加缺失数据填补的机会。本项目在相似紧邻度量、紧邻约束规则修复、相似紧邻识别、相似紧邻数据填补修复等几个方面都取得了重要进展，同时对事件类型、关系类型、时序类型、图谱类型等多种类型数据的填补修复展开如下研究：(1) 相似紧邻填补问题的复杂度、可近似度等理论基础分析；(2) 基于相似紧邻的最优填补计算方法；(3) 高效率近似填补算法及其近似比率保证和时间复杂度分析等。最终形成一整套完整的相似紧邻填补理论成果和高效率填补计算方法，并应用于金风科技有限公司、上海地铁、石家庄天远科技有限公司等多家企业，解决风机数据、地铁数据和车辆运载数据中存在的缺失信息问题。综上所述，本项目提出的基于相似紧邻的缺失数据填补技术能够应对数据缺失问题带来的损失和危害，服务于社会实际生产生活的多个领域，不仅具有学术研究价值更带来了重要的实际应用价值。