论文部分内容阅读
随着计算机网络技术的快速发展,每时每刻都会产生海量数据,各种工程应用中,需要使用这些数据来实现一些科学研究和商业应用。由于采集全部数据的代价太大或数据在传输的过程中发生丢失等原因,得到的数据往往是缺失的,但这些数据仍然具有很大的研究和分析价值。在异常检测、网络性能分析、计算机视觉、社交网络分析等工程中,通过部分监测的网络数据来推断出全部数据的任务越来越重要。目前,相关领域研究表明,张量填充是一种利用多维数据结构对缺失数据进行更准确推断的有效方法。然而,现有的张量填充算法一般都假设张量数据具有全局低秩的性质,并试图寻找一个整体模型来填充整个张量的数据,忽略了数据间的局部相关性,导致恢复的数据精度太低。在实际的网络流量数据中,局部数据间存在较强的相关性,利用这一性质可以提高数据恢复的精度。本文中,提出局部子张量填充算法(Local Tensor Completion,简称LTC),利用子张量的低秩性实现更加精准的数据恢复。虽然这一技术很有前景,仍然面临两个挑战,一方面,如何从张量数据中提取出具有较强相关性的数据,构建局部低秩子张量;另一方面,如何利用融合填充后的子张量数据对原始张量进行恢复。针对这两个挑战,提出了以下相关解决技术:(1)针对LTC算法中,如何提取局部低秩子张量的问题,提出基于局部敏感哈希(Locality Sensitive Hashing,简称LSH)的候选锚点快速选择算法,利用局部数据间较强的相关性,以锚点为中心构建若干个低秩的子张量,然后对局部子张量进行填充,恢复子张量缺失数据。实验证明,基于LSH的候选锚点选择算法比随机选择锚点算法的收敛速度更快,效果更好。(2)针对如何在稀疏的张量数据中找出相似数据的问题,在LTC算法中提出了一种基于切片编码的新策略并给出了相似距离的定义,利用平行因子分解的方法,实现对稀疏张量数据的编码,克服计算距离困难的挑战。(3)针对LTC算法中,如何利用填充后子张量数据来填充原始张量的问题,给出相似敏感数据融合的算法,对子张量数据进行加权融合,恢复出原始张量;同时,给出基于采样密度和距离的锚点选择算法来进一步提高局部低秩张量填充的精度,并且降低LTC算法的计算复杂度。实验结果表明,LTC算法模型与其他低秩的假设下张量填充算法,例如CP nmu,CP opt,CP als,相比有效的提高数据恢复的精度。