的Python：選擇n個點更好地從一堆點

Question

我點的numpy的陣列在XY平面狀的分佈：

我要選擇的n個點（假設100）從更好地分配所有這些點。這是，我希望點的密度在任何地方都是恆定的。

事情是這樣的：

有任何Python的方式或任何numpy的/ SciPy的功能來做到這一點？

Answer 1

除非你給出了定義「更好分佈」的具體標準，否則我們不能給出明確的答案。

短語「任意點的恆定密度」也是誤導性的，因爲您必須指定計算密度的經驗方法。你是否在網格上逼近它？如果是這樣，則網格大小將很重要，並且邊界附近的點不會被正確表示。

一種不同的方法可以如下：

1. 計算所有成對的點
2. 治療該距離矩陣作爲加權網絡之間的距離矩陣，計算數據中的每個點中心性的一定程度的例如eigenvalue centrality，Betweenness centrality或Bonacich centrality。
3. 根據中心度測量按降序對點進行排序，並保持前100個。
4. 重複步驟1-4，可能使用點之間的「距離」和不同的中心度量度的不同概念。

這些函數中的很多直接由SciPy，NetworkX和scikits.learn提供，並且將直接在NumPy數組上工作。

如果您確實承諾以常規間距和網格密度的方式考慮問題，則可以查看quasi-Monte Carlo methods。特別是，您可以嘗試計算一組點的凸包，然後應用QMC技術定期從凸包內的任何位置採樣。但是，這又賦予了該地區的外部特權，該區域的內部應該比內部要少得多。

另一個有趣的方法是簡單地在分散數據上運行K均值算法，使用固定數量的聚類K = 100。算法收斂後，您的空間（每個羣集的平均值）將有100個點。你可以用簇的不同隨機起點重複幾次，然後從更大的可能方法中抽樣。由於您的數據似乎並不是自然地聚類爲100個組件，因此此方法的收斂性不會很好，並且可能需要運行算法以進行大量迭代。這也有一個缺點，即所得到的100個點不一定是來自觀測數據的點，而是多個點的局部平均值。

Answer 2

@EMS是非常正確的，你應該給你很多想法到你想要的。

有更復雜的方法可以做到這一點（EMS的建議非常好！），但是一種蠻力的方法是將這些點分成一個規則的矩形網格，並從每個容器中繪製一個隨機點。

主要的缺點是，你不會得到你要求的點數。相反，你會得到一些小於這個數字的數字。

有點創意索引pandas使這種「網格化」的方法很容易，雖然你當然也可以做到「純」numpy。

作爲最簡單的可能，蠻力的例子，發車辦法：（有很多我們可以做的更好，在這裏。）

import numpy as np 
import matplotlib.pyplot as plt 
import pandas as pd 

total_num = 100000 
x, y = np.random.normal(0, 1, (2, total_num)) 

# We'll always get fewer than this number for two reasons. 
# 1) We're choosing a square grid, and "subset_num" may not be a perfect square 
# 2) There won't be data in every cell of the grid 
subset_num = 1000 

# Bin points onto a rectangular grid with approximately "subset_num" cells 
nbins = int(np.sqrt(subset_num)) 
xbins = np.linspace(x.min(), x.max(), nbins+1) 
ybins = np.linspace(y.min(), y.max(), nbins+1) 

# Make a dataframe indexed by the grid coordinates. 
i, j = np.digitize(y, ybins), np.digitize(x, xbins) 
df = pd.DataFrame(dict(x=x, y=y), index=[i, j]) 

# Group by which cell the points fall into and choose a random point from each 
groups = df.groupby(df.index) 
new = groups.agg(lambda x: np.random.permutation(x)[0]) 

# Plot the results 
fig, axes = plt.subplots(ncols=2, sharex=True, sharey=True) 
axes[0].plot(x, y, 'k.') 
axes[0].set_title('Original $(n={})$'.format(total_num)) 
axes[1].plot(new.x, new.y, 'k.') 
axes[1].set_title('Subset $(n={})$'.format(len(new))) 
plt.setp(axes, aspect=1, adjustable='box-forced') 
fig.tight_layout() 
plt.show() 

---

鬆散的基礎上@ EMS的評論中的建議，這是另一種方法。

我們將使用核密度估計來計算點的密度，然後使用它的倒數作爲選擇給定點的概率。

scipy.stats.gaussian_kde未針對此用例（或通常大量的點）進行優化。這是這裏的瓶頸。可以用幾種方式爲這個特定的用例編寫一個更優化的版本（近似值，成對距離的特殊情況等）。但是，這超出了這個特定問題的範圍。請注意，對於1e5分的特定示例，運行需要一兩分鐘的時間。

該方法的優點是您可以獲得所要求的確切點數。缺點是你可能擁有選定點的本地聚類。

import numpy as np 
import matplotlib.pyplot as plt 
from scipy.stats import gaussian_kde 

total_num = 100000 
subset_num = 1000 
x, y = np.random.normal(0, 1, (2, total_num)) 

# Let's approximate the PDF of the point distribution with a kernel density 
# estimate. scipy.stats.gaussian_kde is slow for large numbers of points, so 
# you might want to use another implementation in some cases. 
xy = np.vstack([x, y]) 
dens = gaussian_kde(xy)(xy) 

# Try playing around with this weight. Compare 1/dens, 1-dens, and (1-dens)**2 
weight = 1/dens 
weight /= weight.sum() 

# Draw a sample using np.random.choice with the specified probabilities. 
# We'll need to view things as an object array because np.random.choice 
# expects a 1D array. 
dat = xy.T.ravel().view([('x', float), ('y', float)]) 
subset = np.random.choice(dat, subset_num, p=weight) 

# Plot the results 
fig, axes = plt.subplots(ncols=2, sharex=True, sharey=True) 
axes[0].scatter(x, y, c=dens, edgecolor='') 
axes[0].set_title('Original $(n={})$'.format(total_num)) 
axes[1].plot(subset['x'], subset['y'], 'k.') 
axes[1].set_title('Subset $(n={})$'.format(len(subset))) 
plt.setp(axes, aspect=1, adjustable='box-forced') 
fig.tight_layout() 
plt.show()