在圖形上選擇外點的算法（「富」凸包）

Question

我正在尋找一種選擇距離中心最遠的相對大部分點（二維歐幾里德圖）的有效方法。這類似於凸包，但會包含（很多）更多的點。其他條件：

• 選擇/設置（「K」）中的點數必須在指定範圍內。最有可能它不會很窄，但它最適用於不同的範圍（例如0.01 * N < K < 0.05 * N以及0.1 * N < K < 0.2 * N）。

• 該算法必須能夠平衡距離中心和「局部密度」的距離。如果在圖形範圍的上部附近有密集區域，但在下部附近有稀疏區域，則算法必須確保從下部選擇一些點，即使它們比上部的點更接近中心地區。 （見下面的例子）

• 獎勵：而不是簡單的距離中心，考慮到特定點（或點和中心）的距離將是完美的。

我嘗試到目前爲止都集中在使用「對號入座」（圖劃分成CXR箱，分配點基於座標框），然後選擇「外部」複選框，直到我們在設置足夠的積分。但是，我並沒有成功地平衡選擇（因爲固定的盒子大小而過度選擇密集區域），也沒有使用選定的點作爲參考而不是（僅）中心。

我已經（很差）繪製了一個Example：紅點是點，綠色的形狀是我想要的一個例子（綠色=選定的外面）。對於稀疏區域，邊界形狀更接近中心以找到合適的點（但如果它們太靠近中心則不一定會找到任何點）。黃色框是我的Pigeon Holing算法所做的一個例子。即使在嘗試調整稀疏區域時，也不能很好地管理。

歡迎任何想法！

Answer 1

我不認爲有任何標準算法會給你你想要的。你將不得不變得富有創造力。假設你的點嵌入在2D歐氏空間這裏有一些想法：

1. 迭代計算幾個凸包。例如，計算凸包，保留屬於凸包的點，然後計算另一個凸包，忽略原始凸包中的點。繼續做到這一點，直到你有足夠的點數，基本上在每個迭代的邊界上拔掉點。這種方法唯一的問題是它不適用於數據集中的凹陷（例如，您發佈的示例底部的那個凹陷）。

2. 飛度高斯您的數據和把一切都> n標準從平均 偏差值的距離（其中N是你必須 值選擇）。如果你的數據是高斯的，這應該工作得很好。如果 不是，那麼可以用幾個高斯（而不是一個的 ）對它進行建模，並保持聯合概率小於某個閾值的點。使用多個高斯可能會很好地處理凹面。
   參考：
   http://en.wikipedia.org/wiki/Gaussian_function
   How to fit a gaussian to data in matlab/octave? \

3. 使用核密度估計 - 如果你創建一個內核密度 面，你可以片在一定高度的表面（例如，打開 成一個高原），給你周圍的形狀（高原的形狀）在點附近。訣竅是將其切分爲 的正確位置，因爲您最終可能會在形狀外面沒有得到 ，但通過正確的選擇，您可以很容易地獲得您繪製的綠色形狀。如果你明智地選擇切點（這可能很難做到），這種方法可以很好地工作，並給你在你的例子中的綠色形狀。這種方法的一大缺點是計算量非常大。更多信息： http://en.wikipedia.org/wiki/Multivariate_kernel_density_estimation

4. 使用阿爾法形狀得到一般的形狀緊緊地包裹的點集外周邊周圍 。然後侵蝕形狀 很少迫使形狀以外的一些點。我對alpha形狀沒有太多的經驗，但這種方法在計算上也相當昂貴。更多信息： http://doc.cgal.org/latest/Alpha_shapes_2/index.html