IEEE Trans Pattern Anal Mach Intell. 2019 Sep;41(9):2273-2279. doi: 10.1109/TPAMI.2018.2851513. Epub 2018 Jun 29.
Multi-dimensional scaling (MDS) plays a central role in data-exploration, dimensionality reduction and visualization. State-of-the-art MDS algorithms are not robust to outliers, yielding significant errors in the embedding even when only a handful of outliers are present. In this paper, we introduce a technique to detect and filter outliers based on geometric reasoning. We test the validity of triangles formed by three points, and mark a triangle as broken if its triangle inequality does not hold. The premise of our work is that unlike inliers, outlier distances tend to break many triangles. Our method is tested and its performance is evaluated on various datasets and distributions of outliers. We demonstrate that for a reasonable amount of outliers, e.g., under 20 percent, our method is effective, and leads to a high embedding quality.
多维缩放（MDS）在数据探索、降维和可视化中起着核心作用。最先进的 MDS 算法对离群值不稳健，即使只有少数几个离群值存在，也会在嵌入中产生显著的误差。在本文中，我们引入了一种基于几何推理的检测和过滤离群值的技术。我们测试了由三个点形成的三角形的有效性，如果其三角形不等式不成立，则标记该三角形为断开。我们工作的前提是，与内点不同，离群点的距离往往会破坏许多三角形。我们的方法在各种数据集和离群值分布上进行了测试和性能评估。我们证明了，对于合理数量的离群值，例如 20%以下，我们的方法是有效的，并导致了高嵌入质量。
