番号クラスタリング/パーティショニングアルゴリズム

Question

私は1次元配列の数値を持っています。配列の長さと配列内の数値の値は両方とも任意です。私は数値の値に応じて、配列をk個のパーティションに分割したいと思います。 30％/ 30％/ 20％/ 20％、つまり上位30％の値、その後の30％の値などのように4つのパーティションが必要な場合、kとその分布のパーセンテージを選択します。さらに、アレイ内で同じ番号が複数回表示される場合は、2つの異なるパーティションに含まれるべきではありません。これは、上記の分配率が厳密ではなく、むしろ「目標」または「出発点」であることを意味します。

例えば、私の配列が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-を必要とするように私には思えますアルゴリズムは、標準アルゴリズムが、私のパーセンテージおよび/または複数のクラスタ/パーティションに同じ値を入れることができないという要件を遵守することが保証されていないためです。

このようなクラスタリングのアルゴリズムはありますか？

Answer 1

単純なアプローチは次のように行くだろう：PK ...

セイp1は、あなたのパーティションに対するパーセンテージである（P1 + ... + PK = 1）

あなたは、アレイ内のN個の要素を持っていると言います

0、p1 * N、（p1 + p2）* N、...、N（そこにはk個のパーティションがあるので、配列の終わりを含むそれらのk +いくつかの丸めをするだろう）。

境界を移動するには、境界の両側にある2つの配列要素（移動できるk-1境界）を確認します。 2つの要素が等しい場合は、少なくとも制約が満たされるまで、左右のどちらかの境界に移動する必要があります。素朴なアプローチは、左から開始し、最小限の調整を行うことです（最小の動きを引き起こす側に制約を調整し、境界をそれ以上移動させないでください）。

しかし、このアルゴリズムはパーティションの全領域をカバーしません。それはちょうど1つの解決策を提供します。最良のソリューションを見つけるには、何らかの種類のプルーニング（例えば、初期配列のサブアレイの最適なパーティション分割を覚えている動的プログラミング）を使用して、パーティション空間全体に対してブルートフォース検索を行う必要があります。

Answer 2

クラスタリングアルゴリズムは、多次元データで使用されます。 1次元データの場合、ソートアルゴリズムを使用するだけです。

データを並べ替えます。次に、例のように、配列の一番下から一番上まで直線的に作用するデータセットを分割します。

Answer 3

ここでは、パーツのサイズの誤差の2乗の和を最小にするパーティションを見つける動的プログラミングソリューションがあります。あなたの[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), {})