0

クラスター内の変動が最小化されるように、整数の入力配列から整数のクラスターを導出する必要があります。(配列内の整数またはデータ値は、都市間を走る 16 台の車のガス使用量に対応しています。最後に、データ値のクラスターに基づいて、16 台の車から 4 つのクラスターを導き出します。)

制約: 要素の数は常に 16 です。クラスターの数は 4 で、クラスターのサイズは 4 です。

私が計画している簡単な方法の 1 つは、入力配列を並べ替えてから、以下に示すように 4 つのグループに分割することです。k-means クラスタリングも使えると思います。

しかし、私が行き詰まった場所は次のとおりです。配列内のデータは時間の経過とともに変化します。基本的に、1 秒ごとにアレイを監視し、それらを再グループ化/再クラスター化して、クラスター内の変動が最小限になるようにする必要があります。さらに、上記の制約を満たす必要があります。このために、私が得ている 1 つのアイデアは、平均と変動に基づいて 2 つのグループを選択し、グループ間でデータ値を移動して、グループ内の変動を最小限に抑えることです。ただし、グループ間で移動するデータ値を選択する方法と、それらのグループを選択する方法についてはわかりません。毎秒NlogNを余裕がないため、毎秒配列にソートを適用することはできません。簡単な解決策を導き出すことができれば幸いです。

sorted `input array: (12 14 16 16 18 19 20 21 24 26 27 29 29 30 31 32)`

cluster-1: (12  14 16 16)
cluster-2: (18 19 20 21)
cluster-3: (24 26 27 29)
cluster-4:  (29 30 31 32)
4

1 に答える 1

2

最初に、少数のオブジェクトのソートは非常に高速であることを指摘しておきます。特に、それらが以前にソートされた場合、「邪悪な」バブルソートまたは挿入ソートは通常線形です。順序が変更された可能性のある場所の数を検討してください。データが CPU の第 1 レベルのキャッシュに収まる場合、古典的な複雑さの議論はすべて実際には当てはまりません。

ほとんどの QuickSort 実装は、小さな配列の挿入ソートにフォールバックすることをご存知ですか? これは、小さな配列に対してかなり適切に機能し、オーバーヘッドがほとんどないためです。

複雑さに関する議論はすべて、非常に大きなデータセットのみを対象としています。実際、それらは無限のサイズのデータ​​に対してのみ証明されています。無限に到達する前に、複雑度の高い単純なアルゴリズムのパフォーマンスが向上する可能性があります。また、n < 10 の場合、2 次挿入ソートは O(n log n) ソートよりも優れていることがよくあります。

ただし、k-means はあまり役に立ちません。

  1. データは 1 次元です。多次元メソッドを見ることさえ気にしないでください。それらは、適切な 1 次元メソッドよりもパフォーマンスが低下します (データを順序付けできることを悪用できます)。
  2. 保証されたランタイムが必要な場合、多くの反復を伴う可能性のある k-means はまったく制御されていません。
  3. 4-cars ルールなどの制約を k-meansに簡単に追加できない

あなたの仕事の解決策は次のとおりだと思います（データが1次元であり、追加した制約のため）：

Sort the integers
Divide the sorted list into k even-sized groups
于 2012-07-16T05:59:43.070 に答える