クラスターが特定のサイズに制限されている場合、特定のデータセットの最も多くのポイントを含む N 個のクラスターを見つけることを任されました。現在、データを kd ツリーにプラグインし、データを繰り返し処理して最も近い隣人を見つけ、それらが作成するクラスターが制限を超えていない場合はポイントをマージすることで、これを実行しようとしています。このアプローチがグローバルなソリューションを提供してくれるかどうかわからないので、微調整する方法を探しています。これがどのような種類の問題になるか教えていただければ、それも素晴らしいことです。
1417 次
3 に答える
7
手始めにscipy.clusteringをチェックしてください。キーワード検索では、そこで使用されているさまざまなアルゴリズムに関する多くの情報を得ることができます。クラスタリングは大きな分野であり、多くの研究と実用的なアプリケーションがあり、かなりうまく機能することがわかっている多くの単純なアプローチがあるため、自分で作成することから始めたくない場合があります。
とはいえ、クラスタリング アルゴリズムは一般にプログラミングがかなり簡単であり、独自のプログラミングを行いたい場合は、k-means と凝集クラスタリングがすぐに実行できるお気に入りの 1 つです。
最後に、特定のサイズで区切られた正確に N 個のクラスターというあなたの考えが自己一貫性があるかどうかはわかりませんが、「サイズ」と「クラスター」の意味に正確に依存します (単一点はクラスターですか?) .
アップデート：
以下のOPのコメントに従って、最適化できるポイント間の「距離」の連続的なメトリックがないため、標準のクラスタリング方法ではこの問題の最適な解決策が得られないと思います。場合によっては、良い解決策や近似値が得られることもありますが。クラスタリング アプローチの場合、この方法の前提は N が固定されているため、k-means を試します。
しかし、クラスタリングの代わりに、これはカバーの問題のように見えます(つまり、固定サイズの N 個の長方形があり、それらですべての点をカバーしようとしている) が、私はこれらについてあまり知りません。誰かに任せます。
于 2010-10-08T15:05:36.957 に答える
0
link text実は、これは 2 つの主要な前提条件があれば非常に簡単だと思います。
1）「特定のサイズ」によって、「どのクラスターも半径rの円内に完全に含まれる必要がある」と言うことができると仮定します。
2) すべてのポイントは、クラスターの中心にある候補の「シード」ポイントです。
最初に、すべてのポイント間で r 未満のすべての距離を計算します。ここで、r 未満の実行可能エッジのみを使用してセット カバーリング問題を解きます。r の距離よりも離れた最近傍点が存在する場合、その点は独自のクラスターを形成します。
于 2010-10-08T20:41:28.187 に答える
0
クラスターの数が固定されていて、これらのクラスターにあるポイントの数のみを最大化したい場合は、貪欲なソリューションが良いと思います:
- 最大数の点を含むことができる長方形を見つけ、
- これらの点を取り除き、
- 次の長方形を見つける
- ...
では、最大数のポイントを含む最大面積 A の長方形 (実際には、各長方形にはこの面積があります) を見つける方法は?
四角形はユークリッド距離ではあまり一般的ではありません。これを解決する前に、本当に四角形が必要なのか、それともクラスタ サイズの制限が必要なのかを正確に教えていただけますか? 円/楕円は機能しますか?
編集：欲張りは機能しません（以下のコメントを参照）。実際には長方形である必要があります...
于 2010-10-08T18:52:20.500 に答える