作者：2018级本科生 刘坤瓒 电子系

指导老师：谷源涛 电子系

关键词：随机投影、离群点检测、子空间聚类、降维

摘要

子空间学习相关领域在子空间模型基本假设下应运而生，目前已经在图像分割、人脸识别等领域有着较多的应用，本项目将关注子空间学习中的离群点检测问题。目前的基于自表示的离群点检测算法保证了较高的成功率，但是其效率会随着数据维数的增加而大大下降，本项目提出了一种压缩离群点检测算法，它能够同时保证较高的成功率和较少的计算时间。我们的主要贡献是在理论上证明了此算法的可靠性，同时还设计了真实数据集上的实验确认了其良好的表现。

图1 子空间学习应用于人脸识别等领域

背景简介

离群点检测问题是在处理现实数据集中的重要问题，我们可以想象，如果能在处理数据前，例如聚类，将数据中的“噪声”进行检测和摘除，我们后续的处理将变得更加准确和高效。目前离群点检测算法主要是基于自表示的离群点检测，算法的准确率随着损失函数的改进在一步步增加。

随机投影方法是一种将数据进行降维的方法。目前对随机投影的研究主要集中在随机矩阵的优良性质，例如子空间保距、保角，它们为子空间学习中的许多问题提供了理论基础。

图2 随机投影具有子空间保距、保角等基础性质

压缩离群点检测

压缩离群点检测的实现基于三个步骤。第一步，随机投影，将数据实现降维；第二步，自表示，确定数据之间的内在联系；第三步，随机游走，基于离群点的特殊性通过有向图上随机游走将其确定。

图3 压缩离群点检测算法

核心创新点

本作品的主要贡献是在理论上证明了算法的高效性和可靠性。根据我们的调研，这是降维方法首次在离群点检测问题中使用，我们的计算证明了子空间保持性质在随机投影后仍然以大概率成立，这拓宽了随机投影的应用场景，尤其是在更多的子空间学习问题中的使用。

图4 基于自表示的压缩离群点检测

联系方式：lkz18@mails.tsinghua.edu.cn

相关资料下载地址：liukunzan.github.io