论文部分内容阅读
近年来,随着互联网、物联网的迅速发展,数据产生方式日益多样化的同时数据可用性问题日益突出。数据可用性的一个重要方面是数据完整性,由于机器故障、隐私涉及、人为错误和信息自动化提取整合技术的广泛使用,不完整数据普遍存在。如何从不完整数据中高效的获取用户所需的信息成为我们亟需解决的重要问题。Skyline查询可以为用户提供有效的决策分析以及符合用户偏好的查询结果,可以应用在多目标决策、环境监测、市场分析和数据挖掘等多个领域中。数据清洗、修复等预处理是一种常见的不完整数据处理方法,再在清洗修复后的数据集上进行各种查询操作。这类方法不仅会产生巨额代价而且会引入新的‘噪声’,导致查询效率低、误差大,查询结果不能满足用户需求。目前,从不完整数据中获取个性化信息缺乏高效准确的处理策略。本文提出了一种不完整数据的Skyline偏好查询算法(Skyline preference query based on incomplete dataset,以下简称SPQ-I算法),在不完整数据集上基于用户偏好提取个性化信息的同时提高Skyline查询效率。首先,对划分后的数据集按照不同的重要程度分别进行不同的聚类,聚类过程中把被支配的元组剪枝,缩小Skyline查询空间;然后,对聚类得到的两个查询子空间分别执行查询准确度高的基于数据元组排序的Skyline查询算法和简化高效的基于支配程度计算的Skyline查询算法,得到两个局部Skyline查询结果集;最后,根据两个结果集的交集是否为空进行全局Skyline查询结果的选择,如果交集不为空,交集作为全局最优解返回给用户;如果交集为空,进行基于泛化中心的次优解选择。大量实验结果表明,本文提出的SPQ-I算法可以根据不同的用户偏好分别得到符合用户需求的查询结果,确保了查询准确度,与SIDS算法和CDSkyline算法相比在处理高维不完整数据时查询性能更优。