執行離散voronoi鑲嵌的有效方法

Question

假設我在d維空間c_1，c_2，...，c_N中有少量點，其中N大約在50-100。

現在，我在d維空間中有一組樣本x_1，x_2，...，x_M，其中M可以大到1e7。

是否有一種有效的方法來隔離樣本x_1，x_2，...，x_M，使得對於每個j，我們將x_j分配給點c_k，其中從x_j到c_k（對於所有k）的歐式距離是最小的？到目前爲止，我正在使用蠻力方法：對於每個j，我只需計算x_j與所有c_k的距離。在低維度中，我可以使用Matlab中的repmat和一些向量化代碼輕鬆完成此操作。

然而，在高維情況下，當進行repmat時遇到內存問題，特別是當M很大時。結果，運行for循環遍歷每個x_j變得非常緩慢。由於我必須多次執行此聚類過程，因此我的整個模擬過程比一天更長。

有關如何使羣集過程更高效的任何想法？我試着環顧四周，但只發現了與我無關的k-means聚類，因爲c_1，...，c_N都給出了。

Answer 1

像k-d樹那樣的最近鄰結構在高維方面工作得很差（維度詛咒）。我的第一個建議是以足夠大的塊來處理樣本，以避免MATLAB解釋器的開銷，但足夠小以至於它們可以很好地適應緩存。