r - 如何找到覆盖R中一组点的给定分数的最小椭圆？

Question

我在想:是否有一些函数/聪明的方法可以找到覆盖 R 中一组 2d 点的给定分数的最小椭圆？ 最小的意思是面积最小的椭圆。

澄清:如果点数很大，我可以使用近似正确的解决方案(因为我猜一个精确的解决方案必须尝试所有点子集的组合)

这个问题听起来像是问题 Ellipse containing percentage of given points in R 的重复。但该问题的措辞方式最终的答案不会导致最小的椭圆。例如，使用提供给 Ellipse containing percentage of given points in R 的解决方案:

require(car)
x <- runif(6)
y <- runif(6)
dataEllipse(x,y, levels=0.5)

由此产生的椭圆显然不是包含一半点的最小椭圆，我猜这将是一个覆盖左上角三个点的小椭圆。

Answer 1

我想我有一个需要两个函数的解决方案，cov.rob来自 MASS包装和 ellipsoidhull来自 cluster包裹。 cov.rob(xy, quantile.used = 50, method = "mve")从 xy 中的 2d 点总数中找到大约“最佳”的 50 个点包含在最小体积椭圆中。然而，cov.rob不直接返回这个椭圆，而是从最佳点估计的其他一些椭圆(目标是稳健地估计协方差矩阵)。为了找到实际的最小椭圆，我们可以给 ellipsoidhull 最好的点。找到最小椭圆，我们可以使用 predict.ellipse获取定义椭圆 shell 的路径坐标。

我不是 100% 确定这个方法是最简单的和/或它 100% 有效(感觉应该可以避免使用 ellipsoidhull 的第二步，但我还没有弄清楚如何。)。它似乎至少适用于我的玩具示例......

话不多说，代码如下:

library(MASS)
library(cluster)

# Using the same six points as in the question
xy <- cbind(x, y)
# Finding the 3 points in the smallest ellipse (not finding 
# the actual ellipse though...)
fit <- cov.rob(xy, quantile.used = 3, method = "mve")
# Finding the minimum volume ellipse that contains these three points
best_ellipse <- ellipsoidhull( xy[fit$best,] )
plot(xy)
# The predict() function returns a 2d matrix defining the coordinates of
# the hull of the ellipse 
lines(predict(best_ellipse), col="blue")

看起来不错!您还可以检查 ellipse对象以获取更多信息

best_ellipse
## 'ellipsoid' in 2 dimensions:
##  center = ( 0.36 0.65 ); squared ave.radius d^2 =  2 
##  and shape matrix =
##         x      y
## x 0.00042 0.0065
## y 0.00654 0.1229
##   hence, area  =  0.018 

这是一个方便的函数，它向现有的基本图形绘图添加一个椭圆:

plot_min_ellipse <- function(xy, points_in_ellipse, color = "blue") {
  fit <- cov.rob(xy, quantile.used = points_in_ellipse, method = "mve")
  best_ellipse <- ellipsoidhull( xy[fit$best,] )
  lines(predict(best_ellipse), col=color)
}

让我们在更多点上使用它:

x <- runif(100)
y <- runif(100)
xy <- cbind(x, y)
plot(xy)
plot_min_ellipse(xy, points_in_ellipse = 50)