メトリックが定義された有限数のポイント (クラウド) があります。次のような、このクラウド内のクラスターの最大量を見つけたいと思います。
1) 1 つのクラスター内の任意の 2 点間の最大距離は、与えられたイプシロン ( const )より小さい
2) 各クラスターには正確に k ( const ) 個のポイントがあります
私はあらゆる種類の異なるクラスタリング方法を調べましたが、内部最大距離に制限のあるクラスタリングは問題ではありません (密度ベース)。ただし、2) 制約と「クラスター st の最大量」を見つけるための要件には問題があるようです。効率的な解決策について何か提案はありますか?
ありがとう、あ～
あなたの制約を考えると、解決策がないかもしれません。そして実際、それはかなり頻繁に起こるかもしれません...
k最も明白なケースは、ポイントの倍数がない場合です。
ただし、epsilon設定が低すぎると、クラスターに配置できないポイントが存在する可能性があります。
満足できないかもしれない不当に難しい要件を解決するためのアルゴリズムを探すのではなく、要件と問題を再考する必要があると思います。
また、保証された最大値を見つける必要があるか、それとも単に適切なソリューションを見つける必要があるかを検討してください。
少なくとも適切な近似をすばやく見つける、かなり明白なアプローチがいくつかあります。
実際、@ Anony-Mousse と同じ印象を持っています。問題と要件をまだ理解していません。
クラスターのサイズを にしたい場合k、得られるクラスターの数に疑問の余地はありません。明らかにn /kです。したがって、たとえばこのチュートリアルで説明されているように、同じサイズのクラスターを生成する k-means バリアントの使用を試みることができますn/k。
これは、特定の合理的または優れたクラスタリング アルゴリズムではないことに注意してください。制約を満たすために何かを行いますが、クラスター分析の観点からは、クラスターは実際には意味がありません。これは制約の充足ですが、クラスター分析ではありません。
イプシロン制約も満たすために、この初期ソリューションから始めて (これはおそらく @Anony-Mousse が「明白なアプローチ」と呼んでいるものです)、同じ種類のスワッピング要素による最適化の実行を試みることができます。イプシロン条件を満たすためです。
解決策がない可能性があるため、何度か再起動する必要がある場合があります。
以下も参照してください。
クラスタ サイズが等しい K-means アルゴリズムのバリエーション
本質的に冗長な質問の場合。