數字聚類/分區算法

我有一個有序的一維數組數組。數組的長度和數組的值都是任意的。我想根據數值將數組分成k個分區，例如，假設我想要4個分區，分配爲30％/ 30％/ 20％/ 20％，即前30％的值先後，後面的30％等。我選擇k和分配的百分比。另外，如果相同的數字在數組中出現多次，則不應將其包含在兩個不同的分區中。這意味着上述分配百分比並不嚴格，但如果您願意的話，可以是「目標」或「起點」。例如，假設我的數組是ar = [1, 5, 5, 6, 7, 8, 8, 8, 8, 8]。數字聚類/分區算法

我選擇k = 4，數字應分配到分區A，B，C和D，百分比爲pA = pB = pC = pD = 25%。

鑑於我上面給了限制，導致分區應該是：

A = [1] B = [5, 5] C = [6, 7] D = [8, 8, 8, 8, 8]

，導致（實現/修正）百分率值pcA = 10%, pcB = 20%, pcC = 20%, pcD = 50%

在我看來，我需要改進的K-意味着算法，因爲標準算法不能保證尊重我的百分比和/或要求相同的值不能超過一個集羣/分區。

那麼，有沒有這種聚類算法？

來源

2011-11-15 AsGoodAsItGets

如果指定了4個分區並且有一個數組「'1,1,1,1,1,1,1,8」'，那麼會發生什麼？ – Femaref

首先，您應該創建更多示例來明確要求。例如，當ar = [1,2,3,4,5,6,7,8,9,10]'時，你對k = 4,25％分佈有什麼期望？ –

您需要定義某種度量來量化特定分區與目標的距離。沒有這樣的措施，你就不知道哪個解決方案是「最好的」。天真的方法（根據原始百分比進行分區，然後移動分區邊界以適應約束條件）將始終爲您提供解決方案，您只是不知道它有多好。 – fmr

簡易方法會是這樣的：

說P1 ...... PK是你的分區百分比（P1 + ... + PK = 1）

假設你有一個數組中的N個元素

初始邊界（有k + 1個，包括陣列結尾，因爲你有k個分區）是： 0，p1 * N，（p1 + p2）* N，...，N（there會有一些四捨五入的做法）。

要移動邊界，請查看邊界兩邊的兩個數組元素（對於可移動的k-1邊界）。如果兩個元素相等，則需要移動到邊界，無論是右邊的左邊，至少直到滿足約束條件。一種天真的做法是從左側開始做最小的調整（只需將約束調整到導致最小移動的一側，並且不要再移動邊界）。

這個算法並沒有覆蓋分區的整個空間。它只是給你一個解決方案。要找到最佳解決方案，您需要在整個分區空間上進行強力搜索，並進行某種修剪（例如動態編程，您可以記住初始數組子陣列的最佳分區）。

來源

2011-11-17 17:22:22 fmr

讓我們嘗試一下你的算法： 'ar = [1,8,9,9,9,9,10,10,10,10,10]' 'Pi = 0.25'和' k = 4'，'N = 12'。所以'b0 = 0，b1 = 3，b2 = 6，b3 = 9，b4 = 12'。我們顯然不能改變b0或b4，所以我們從'b1 = 3'開始。 'ar [3] = ar [2] = ar [4] = 9'。我檢查左邊還是右邊？如果我走了，我會在ar [0]處達到1，我的第一個邊界將是'b1 = 8'。如果我去的話，我會在ar [7]達到10，我的第一個邊界將是'b1 = 8'。 – AsGoodAsItGets

很明顯，如果我正確的選擇，我不會有一個最佳的解決方案，甚至沒有關閉，因爲我將無法繼續過去b1，而最終只有兩個分區。如果我走了，我會有一個更好的分區，但仍然只有2個分區。相反，在類似'ar = [1,1,1,1,1,2,2,2,2,2,9,10]的情景中'我會遇到類似的問題。 – AsGoodAsItGets

換句話說，當分佈不均勻時，我不確定這種天真的方法是否有效。此外，將邊界向左或向右移動可能會對最終結果產生重大影響，並且在我看來，有人需要能夠沿相反方向重新開始並重新開始。 – AsGoodAsItGets

聚類算法用於多維數據。對於一維數據，您應該簡單地使用排序算法。

排序數據。然後按照您的示例將從數組底部線性工作的數據集劃分到頂部。

來源

2011-12-10 16:06:22

下面是一個動態編程解決方案，該解決方案可以找到一個最小化部件尺寸誤差平方和的分區。所以在你的[1，5，5，6，7，8，8，8，8，8]的例子中，你需要大小的部分（2.5,2.5,2.5,2。5），並且該代碼給出的結果是（9.0，（1,2,2,5））。這意味着所選的分區大小爲1,2,2和5，總誤差爲9 =（2.5-1）^ 2 +（2.5-2）^ 2 +（2.5-2）^ 2 +（2.5- 5）^ 2。

def partitions(a, i, sizes, cache): 
    """Find a least-cost partition of a[i:]. 

    The ideal sizes of the partitions are stored in the tuple 'sizes' 
    and cache is used to memoize previously calculated results. 
    """ 
    key = (i, sizes) 
    if key in cache: return cache[key] 
    if len(sizes) == 1: 
     segment = len(a) - i 
     result = (segment - sizes[0]) ** 2, (segment,) 
     cache[key] = result 
     return result 
    best_cost, best_partition = None, None 
    for j in xrange(len(a) - i + 1): 
     if 0 < j < len(a) - i and a[i + j - 1] == a[i + j]: 
      # Avoid breaking a run of one number. 
      continue 
     bc, bp = partitions(a, i + j, sizes[1:], cache) 
     c = (j - sizes[0]) ** 2 + bc 
     if best_cost is None or c < best_cost: 
      best_cost = c 
      best_partition = (j,) + bp 
    cache[key] = (best_cost, best_partition) 
    return cache[key] 


ar = [1, 5, 5, 6, 7, 8, 8, 8, 8, 8] 
sizes = (len(ar) * 0.25,) * 4 
print partitions(ar, 0, (2.5, 2.5, 2.5, 2.5), {})

來源

2011-12-10 17:25:42

看起來像你在這裏保羅，謝謝。這是僞代碼還是一些我不知道的新語言（斯卡拉？）我會仔細看看，然後回覆你。 – AsGoodAsItGets

這是python：它並不完全是新的，但在一個美好的一天，它看起來像僞代碼。 – 2011-12-13 20:23:48

數字聚類/分區算法

回答

相關問題