Hình cầu nhỏ nhất có chứa x% số điểm

Question

Cho một đám mây điểm 3D, làm thế nào tôi có thể tìm thấy hình cầu nhỏ nhất có chứa một tỷ lệ phần trăm nhất định?

I.e. nếu tôi có một đám mây điểm với một số nhiễu, và tôi muốn bỏ qua 5% các ngoại lệ, làm thế nào tôi có thể nhận được quả cầu nhỏ nhất chứa 95% số điểm còn lại, nếu tôi không biết điểm nào là các ngoại lệ?

Ví dụ: Tôi muốn tìm lĩnh vực màu xanh lá cây, không phải là hình cầu màu đỏ:

Tôi đang tìm kiếm một thuật toán nhanh một cách hợp lý và đơn giản. Nó không phải tìm ra giải pháp tối ưu, một sự xấp xỉ hợp lý cũng tốt.

Tôi biết cách tính toán hình cầu giới hạn gần đúng cho 100% số điểm, ví dụ: với thuật toán của Ritter.

Làm cách nào để khái quát hóa thuật toán này thành thuật toán tìm quả cầu nhỏ nhất chứa x% điểm?

Answer 1

Chỉ cần một ý tưởng: tìm kiếm nhị phân.

Trước tiên, sử dụng một trong các hình cầu bao quanh algorithms để tìm quả cầu giới hạn 100% trước tiên.

Khắc phục điểm giữa của quả cầu 95% giống như điểm giữa của quả cầu 100%. (Không có gì đảm bảo, nhưng bạn nói rằng bạn đang ok với câu trả lời gần đúng.) Sau đó, sử dụng tìm kiếm nhị phân trên bán kính của hình cầu cho đến khi bạn nhận được 95% +- epsilon điểm bên trong.

Giả sử các điểm đều được sắp xếp theo khoảng cách của họ (hoặc bình phương khoảng cách, để được nhanh hơn một chút) từ Centerpoint, đối với một bán kính cố định r phải mất O(log n) hoạt động để tìm ra số điểm bên trong hình cầu với bán kính r, ví dụ bằng cách sử dụng tìm kiếm nhị phân khác. Tìm kiếm nhị phân cho chính quyền r yêu cầu số lôgarit của đánh giá đó. Do đó Toàn bộ tìm kiếm sẽ chỉ thực hiện các bước O (log n) sau khi bạn đã tìm thấy quả cầu 100%.

Edit: nếu bạn nghĩ rằng trung tâm của quả cầu giảm có thể là quá xa đầy đủ các lĩnh vực, bạn có thể tính toán lại phạm vi ranh giới, hoặc chỉ là trung tâm của khối lượng của tập điểm, mỗi lần sau khi ném đi một số điểm. Mỗi lần lặp lại không được quá O (n). Sau khi tính toán lại, du lịch các điểm theo khoảng cách từ điểm trung tâm mới. Vì bạn mong đợi chúng sắp được sắp xếp gần, bạn có thể dựa vào sắp xếp bong bóng, cho dữ liệu gần như sắp xếp hoạt động trong O (n + epsilon). Hãy nhớ rằng sẽ chỉ có một số logarit của các xét nghiệm này cần thiết, vì vậy bạn sẽ có thể lấy đi gần với O (n log n) cho toàn bộ điều.

Phụ thuộc vào chính xác hiệu suất bạn đang tìm kiếm và những gì bạn sẵn sàng hy sinh cho điều đó. (Tôi sẽ rất vui khi biết rằng mình sai và có một algortihm chính xác cho việc này.)

Answer 2

Khoảng cách từ vị trí điểm trung bình có thể đưa ra một dấu hiệu hợp lý nếu một điểm là ngoại lệ hay không.

Thuật toán có thể giống như thế:

1. Tìm bounding phạm vi điểm
2. Tìm điểm trung bình vị trí
3. Chọn điểm trên phạm vi ranh giới đó là xa nhất từ ​​vị trí trung bình, loại bỏ nó như một ngoại lệ
4. Lặp lại các bước 1-3 cho đến khi bạn đã xóa 5% số điểm

Answer 3

Tìm Eu cây bao trùm tối thiểu clidean, và kiểm tra các cạnh theo thứ tự chiều dài giảm dần. Đối với mỗi cạnh, hãy xem xét tập các điểm điểm trong hai cây được kết nối mà bạn nhận được bằng cách xóa cạnh.

Nếu tập hợp nhỏ hơn các điểm nhỏ hơn 5% tổng số và hình cầu xung quanh tập hợp các điểm lớn hơn không chồng lên nhau, sau đó xóa nhóm điểm nhỏ hơn. (Điều kiện này là cần thiết trong trường hợp bạn có một 'ốc đảo' của không gian trống ở trung tâm của đám mây điểm của bạn).

Lặp lại điều này cho đến khi bạn đạt đến ngưỡng của mình hoặc độ dài đang nhận được 'đủ nhỏ' mà bạn không quan tâm để xóa chúng.

Answer 4

Thuật toán của ryann không phải là xấu. Tôi đề nghị robustifying với trung bình hình học thì đến phác thảo này:

1. tính NxN liên khoảng cách trong thời gian O (N^2)
2. tổng mỗi hàng của ma trận này (= khoảng cách của một điểm đến những người khác) trong thời gian O (N^2)
3. loại các thu được "đám đông" khoảng cách trong thời gian O (N * log N)
   (điểm với khoảng cách nhỏ nhất là một xấp xỉ của trung bình hình học)
4. tháo 5% lớn nhất trong O (1)
   ở đây chúng tôi chỉ xem xét khoảng cách đám đông lớn nhất là các ngoại lệ,
   thay vì lấy khoảng cách lớn nhất từ ​​trung vị. bán kính
5. tính toán của lĩnh vực thu được trong thời gian O (N)

Tất nhiên, nó cũng bị tiểu tối ưu nhưng cần thực hiện tốt hơn một chút trong trường hợp outlier xa. Tổng chi phí là O (N^2).

Answer 5

tôi sẽ lặp hai bước sau cho đến khi hội tụ:

1) Cho một nhóm các điểm, tìm ra phạm vi nhỏ nhất kèm theo 100% số điểm và làm việc ra trung tâm của nó.

2) Đưa ra một trung tâm, tìm nhóm điểm chứa 95% số gốc gần nhất với trung tâm.

Mỗi bước giảm (hoặc ít nhất là không tăng) bán kính của hình cầu liên quan, vì vậy bạn có thể khai báo sự hội tụ khi bán kính ngừng giảm.

Thực tế, tôi sẽ lặp lại từ nhiều lần khởi động ngẫu nhiên, mỗi lần bắt đầu được tạo ra bằng cách tìm hình cầu nhỏ nhất chứa tất cả các tập con nhỏ của các điểm. Tôi lưu ý rằng nếu bạn có 10 ngoại lệ và bạn chia số điểm của mình thành 11 phần, ít nhất một trong những phần đó sẽ không có bất kỳ ngoại lệ nào.

(Điều này rất lỏng lẻo dựa trên https://en.wikipedia.org/wiki/Random_sample_consensus)