0

Kruskal の最小スパニング ツリー アルゴリズムを使用して K-Means クラスタリングを実行しようとしています。私の当初の設計では、入力のフルレングスのクラスカル アルゴリズムを実行して MST を生成し、その後、最後の k-1 個のエッジ (または同等に最も高価な k-1 個のエッジ) を削除することでした。

もちろん、これは Kruskal アルゴリズムを実行し、最後の k-1 エッジを追加する直前に停止することと同じです。

2 番目の戦略を使用したいです。つまり、完全な長さの Kruskal アルゴリズムを実行する代わりに、これまでのクラスター数が K に等しくなった直後に停止します。Union-Find データ構造を使用し、この Union-Find データでリスト オブジェクトを使用しています。構造。

このグラフの各頂点は、このリストの現在のクラスターによって表されます。たとえば[1,2,3...]、頂点 1、2、3 が個別の独立したクラスターにあることを意味します。2 つの頂点が結合されている場合、リスト データ構造の対応するインデックスが更新され、これが反映されます。

たとえば、頂点 2 と 3 をマージすると、リスト データ オブジェクトは次のようになります。[1,2,2,4,5.....]

私の戦略は、2 つのノードがマージされるたびに、リスト内の DISTINCT 要素の数を数え、それが目的のクラスターの数と等しい場合は停止することです。私の心配は、これが最も効率的な選択肢ではないかもしれないということです。リスト内の個別のオブジェクトの数を効率的にカウントする方法はありますか?

4

2 に答える 2

2

最も簡単でおそらく最も効率的なのは

len(set(l))

リストはどこにありますかl。適切であれば、そもそもリストではなくセットでデータを格納することを検討できます。

これが機能するには、 の要素lがハッシュ可能である必要があることに注意してください。これは、数値に対しては保証されていますが、一般的な「オブジェクト」に対しては保証されていません。

于 2012-12-14T09:12:59.350 に答える
1

1つの方法は、リストを並べ替えてから、各要素を前の要素と比較して要素を実行することです。それらが等しくない場合は、「個別のカウンター」の合計1になります。この操作はO（n）であり、ソートにはクイックソートやマージソートなどの好みのソートアルゴリズムを使用できますが、使用するライブラリには使用可能なソートアルゴリズムがあると思います。

もう1つのオプションは、ハッシュテーブルを作成し、すべての要素を追加することです。繰り返される要素は挿入されないため、挿入の数は個別の要素になります。これは最良の場合はO（1）だと思うので、おそらくこれがより良い解決策です。幸運を！

お役に立てれば、

DídacPérez

于 2012-12-14T09:17:41.553 に答える