最適クラスタ化

グラフ（E、V）があります。各エッジ（i、j）に対して、正、ゼロ、または負である支払いP [i、j]が存在する。頂点をクラスターで分割します。 2つの隣接頂点v1およびv2が異なるクラスタに属するたびに、支払いP [v1、v2]を受け取る。合計支払いを最大限にするには？この問題はNP困難ですか？最適クラスタ化

出典

2016-12-13 user31264

あなたは（http://www.cs.cmu.edu/~anupamg/adv-approx/lecture18.pdf）[マルチカット]を探しています。 –

これ以上の制限がない場合（たとえば、結果のクラスタ数がMである必要がある場合など）、エッジを反復して肯定的な支払いをすべて停止するのはなぜですか？実際、まだ連続したグラフ（分割なし）が発生する可能性がありますが、問題は何の制約も課さないため、結果として単一のクラスタが許容されますか？ –

@Adrian Colomitchi私たちは、いくつかのエッジを任意にカットすることはできず、他のものをカットすることもできません。我々は、異なるクラスタからエッジを切断することしかできない。 A-BをカットしてもB-Cをカットしないと、A-Cもカットされます。 – user31264

クラスタリングはしませんが、のカットはです。

エッジカットの重みを最大化することは、一般に「最大カット」と呼ばれます。より一般的な問題は最小カットであり、mincutの問題で表現されるいくつかのクラスタリングアルゴリズムがあります。カットもフローネットワークに関連しています。

コメントに記載されているように、いくつかの境界条件を指定する必要があります。たとえば、ポイントを2つのラベルに切断し、ラベルの異なるエッジのみをカットする必要があります。

はい、これらのカットは通常NPハードです。

https://en.wikipedia.org/wiki/Maximum_cut

出典

2016-12-13 22:21:21

最適クラスタ化

答えて

関連する問題