劃分區域以使距離之和最小化的算法

Question

假設我們在平面的有界區域中有n個點。問題是將其劃分爲4個區域（具有水平線和垂直線），使得每個區域中的度量的總和被最小化。

度量例如可以是每個區域中點之間的距離的總和;或關於點的擴展性的任何其他措施。見下圖。

我不知道是否有聚類算法可以幫助我解決這個問題，或者例如它可以被配製成一個簡單的優化問題。其中決策變量是「軸」。

Answer 1

注 - 可能不正確。我會嘗試添加另一個答案

最小化差分平方和的一維版本是凸的。如果從最左側的線開始並將其移到右側，那麼線所穿過的每個點將停止累積與其右側的點之間的差異，並開始累積差異到其左側的點。當你遵循這一點時，左邊的差異會增加，右邊的差異會減小，所以你會得到單調的減少，可能是單一點，可能在線的兩邊，然後單調增加。

我認爲一條線上聚類點的一維問題是凸的，但我不再相信在最佳位置繪製單條垂直線的問題是凸的。我擔心y座標變化的點集合使得左手點大部分高，右手點大部分低點，中點在高點和低點之間交替。如果這不是凸的，則試圖擴展到兩個維度的答案的部分失敗。

因此，對於問題的一維版本，您可以選擇任意一點，並及時制定出O（n）該點是否應該位於最佳分界線的左側或右側。因此，通過二元印章，您可以找到最佳時間線O（n log n）。

我不知道二維版本是凸的還是不是，但是您可以嘗試所有可能的水平線位置，並且對於每個位置，使用類似方法求解垂直線的位置一維問題（現在你有兩個凸函數的總和值得擔心，但這仍然是凸的，所以沒關係）。因此，您最多可以解決O（n）一維問題，給出成本O（n^2 log n）。

如果這些點的分佈並不是很奇怪，我希望通過使用前一次迭代中的一維問題的解作爲下一次解決方案位置的第一次估計，可以節省大量時間迭代。給定一個起點x，你會發現這是否在解決方案的左側或右側。如果它位於解決方案的左側，則執行1,2,4,8 ...步驟以找到解決方案右側的一個點，然後運行二元印章。希望這個兩階段切換比從頭開始整個陣列的二進制切換更快。

Answer 2

我相信這可以被公式化爲MIP（混合整數規劃）問題。

讓我們引入4個象限A，B，C，D。 A是正確的，上面的，B是正確的，下面的，等等。然後定義一個二元變量

delta(i,k) = 1 if point i is in quadrant k 
       0 otherwise 

和連續變量

Lx, Ly : coordinates of the lines 

顯然，我們有：

sum(k, delta(i,k)) = 1 
xlo <= Lx <= xup 
ylo <= Ly <= yup 

其中xlo,xup是最小和最大的x座標。接下來，我們需要實現像含義：

delta(i,'A') = 1 ==> x(i)>=Lx and y(i)>=Ly 
delta(i,'B') = 1 ==> x(i)>=Lx and y(i)<=Ly 
delta(i,'C') = 1 ==> x(i)<=Lx and y(i)<=Ly 
delta(i,'D') = 1 ==> x(i)<=Lx and y(i)>=Ly 

這些可以通過所謂的指示器約束來處理或寫爲線性不等式，例如

x(i) <= Lx + (delta(i,'A')+delta(i,'B'))*(xup-xlo) 

與其他類似。最終目標是

min sum((i,j,k), delta(i,k)*delta(j,k)*d(i,j)) 

其中d(i,j)是點i和點j之間的距離。這個目標也可以線性化。

應用了一些技巧後，我可以使用Cplex在大約40秒內證明100個隨機點的全局最優性。這種方法並不適用於大型數據集（當點數變大時，計算時間會迅速增加）。

我懷疑這不能成爲凸出問題的鞋子。另外我不確定這個目標是否真的是你想要的。它會嘗試使所有羣集的大小相同（向大羣集添加一個點會引入很多要添加到目標的距離;向小羣集添加點很便宜）。可能是每個羣集的平均距離是一個更好的衡量標準（但這會使線性化變得更加困難）。

Answer 3

這是另一個嘗試。佈局一個網格，除了關係的情況外，每個點是其列中唯一的一點，也是其行中唯一的點。假設任何方向都沒有關係，這個網格有N行，N列和N^2個單元格。如果有關係，網格更小，這使生活更輕鬆。

用水平線和垂直線分隔單元格幾乎挑選出一個網格單元格，並說單元格就在單元格的正上方和正好在這些線條交叉的右側，因此大致有O（N^2）可能的這種劃分，我們可以計算每個這種劃分的度量。我聲稱，當度量是羣集中點間距離的平方和時，這個成本幾乎是O（N^2）問題中的一個常數因子，因此檢查每種可能性的全部成本是O（ N^2）。

由分割線形成的矩形內的度量是SUM_i，j [（X_i-X_j）^ 2 +（Y_i-Y_j）^ 2]。我們可以分別計算X貢獻和Y貢獻。如果你做了一些代數（如果你首先減去一個常數，使得所有事物總和爲零），你會發現來自座標的度量貢獻在該座標的方差中是線性的。所以我們要計算每個分區形成的矩形內X和Y座標的方差。 https://en.wikipedia.org/wiki/Algebraic_formula_for_the_variance給了我們一個身份，告訴我們可以計算出每個矩形給出的SUM_i Xi和SUM_i Xi^2的方差（以及y座標的相應信息）。由於浮點四捨五入錯誤，此計算可能不準確，但我將在此忽略。

給定一個與網格中每個單元格相關的值，我們希望能夠很容易計算矩形內這些值的總和。我們可以沿着每一行創建部分和，將0 1 2 3 4 5轉換爲0 1 3 6 10 15，這樣一行中的每個單元格都包含所有單元格的左邊和它自身的總和。如果我們取這些值並對每列進行部分總和計算，那麼對於每個單元格，我們已經計算出其右上角位於該單元格內並延伸至網格底部和左側的矩形的總和。這些在最右邊一列的計算值爲我們提供了與該單元格相同並在其下面的所有單元格的總和。如果我們減去矩形，我們知道如何計算，我們可以找到位於網格右側和網格底部的矩形的值。類似的減法允許我們首先計算出我們選擇的任何垂直線左右兩邊的矩形的值，然後完成由網格中的任意單元格交叉的兩條線組成的一組四個矩形。其中昂貴的部分是計算部分款項，但我們只需要這樣做一次，而且只需花費O（N^2）。用於計算出任何特定度量的減法和查找只具有恆定的成本。我們必須爲每個O（N^2）單元執行一次，但仍然只有O（N^2）。 （因此我們可以通過計算與O（N^2）時間內所有可能聚類相關的度量並選擇最佳值）在O（N^2）時間中找到最佳聚類。