如果您的数据包含单个异常值，则可以使用您建议的方法可靠地找到它（尽管没有迭代）。一个正式的方法是

库克，R.丹尼斯 (1979)。线性回归中的有影响的观察。美国统计协会杂志（美国统计协会）74（365）：169-174。

多年来，为了找到一个以上的异常值，主要的方法是所谓的估计系列方法。这是一个相当广泛的估计器家族，包括 Huber 的估计器、Koenker 的 L1 回归以及 Procastinator 在他对您的问题的评论中提出的方法。具有凸函数的估计量的优点是它们具有与常规回归估计大致相同的数值复杂性。最大的缺点是他们只能在以下情况下可靠地找到异常值：$M$$M$$M$$\rho$

• 您的样品的污染率小于其中是设计变量的数量，$\frac{1}{1+p}$$p$
• 或者如果异常值在设计空间中不异常（Ellis 和 Morgenthaler (1992)）。

您可以在( )包 ( ) 回归估计的良好实现。$M$$l_1$robustbasequantregR

如果您的数据包含多于异常值，也可能在设计空间外，那么，找到它们相当于解决组合问题（等效于估计器的解决方案）降序/非凸函数）。 $\lfloor\frac{n}{p+1}\rfloor$$M$$\rho$

在过去 20 年（特别是最近 10 年）中，已经设计了大量快速可靠的异常值检测算法来近似解决这个组合问题。这些现在已在最流行的统计软件包（R、Matlab、SAS、STATA...）中广泛实施。

尽管如此，使用这些方法查找异常值的数值复杂性通常为数量级。大多数算法可以在实践中用于青少年中期通常，这些算法在（观察次数）中是线性的，因此观察次数不是问题。一个很大的优势是这些算法中的大多数都是令人尴尬的并行。最近，已经提出了许多专门为高维数据设计的方法。$O(2^p)$$p$$n$

鉴于您没有在问题中指定，我将列出案例的一些参考资料。以下是这些系列评论文章中更详细地解释了这一点的一些论文：$p$$p<20$

Rousseeuw, PJ 和 van Zomeren BC (1990)。揭露多元异常值和杠杆点。美国统计协会杂志，卷。85，第 411 期，第 633-639 页。

Rousseeuw, PJ 和 Van Driessen, K. (2006)。计算大型数据集的 LTS 回归。数据挖掘和知识发现档案第 12 卷第 1 期，第 29 - 45 页。

Hubert, M.、Rousseeuw, PJ 和 Van Aelst, S. (2008)。高分解鲁棒多变量方法。统计科学，卷。23, 1 号, 92–119

埃利斯 SP 和 Morgenthaler S. (1992)。L1 回归中的杠杆和分解。 美国统计协会杂志，卷。87，第 417 期，第 143-148 页

最近一本关于异常值识别问题的参考书是：

Maronna RA、Martin RD 和 Yohai VJ（2006 年）。稳健统计：理论与方法。威利，纽约。

这些（以及这些方法的许多其他变体）在包中实现（除其他外）。robustbase R

对于简单回归（单个 x），Theil-Sen 线在对 y 异常值和影响点的稳健性以及与斜率的 LS 相比通常具有良好的效率（在正常情况下）方面有一些话要说。斜坡的破裂点接近 30%；只要拦截（人们使用过多种可能的拦截）没有较低的故障，整个过程就可以很好地应对相当大一部分的污染。

它的速度可能听起来很糟糕 -斜率的中位数看起来是即使使用中位数 - 但我记得它可以更快地完成如果速度真的是一个问题（，我相信）$\binom{n}{2}$$O(n^2)$$O(n)$$O(n \log n)$

编辑：user603 要求 Theil 回归优于 L1 回归。答案是我提到的另一件事——影响点：

红线是拟合（来自包中的函数）。果岭与泰尔斜坡相得益彰。所需要的只是 x 值中的一个拼写错误——比如输入 533 而不是 53——这样的事情就可能发生。因此，拟合对于 x 空间中的单个错字并不稳健。$L_1$rqquantreg$L_1$

你看过RANSAC（维基百科）吗？

即使存在大量异常值和噪声，这也应该擅长计算合理的线性模型，因为它建立在只有部分数据实际上属于该机制的假设之上。

我发现惩罚误差回归最好。您也可以迭代使用它并重新加权样本，这与解决方案不是很一致。基本思想是用错误来扩充你的模型： 其中是未知的错误向量。执行回归 。有趣的是，当您可以提前估计测量的确定性并将其作为权重放入并解决新的略有不同的任务 $l_1$

$$y=Ax+e$$ $e$ $$\parallel y-Ax-e \parallel_2^2+ \lambda \parallel e \parallel_1$$ $$W=diag(w_i)$$ $$\parallel y-Ax-e \parallel_2^2 + \lambda \parallel W e \parallel_1$$

更多信息可以在这里找到：http ://statweb.stanford.edu/~candes/papers/GrossErrorsSmallErrors.pdf