問題タブ [kruskals-algorithm]

2Dポイントのセットでkクラスを見つけることを任務とするクラスタリングアルゴリズムを開発しようとしていました（kを入力として）。Kruskalアルゴリズムをわずかに変更して、1つではなくkスパニングツリーを見つけます。

k = 7 の場合、95.5% という結果になりました。比較は以下のリンクで見ることができます。

問題：

セットには、アルゴリズムによって簡単に分類できる 5 つの明確な間隔のクラスターがありますが、k > 5 の場合、結果はかなり期待外れです。私は自分のアルゴリズムが正しいと信じており、おそらくデータはクルスカルのアプローチにとって特に悪いものです. Kruskal のような単一リンケージ凝集クラスタリングは、クラスター品質の評価をポイントのペア間の単一の類似性に還元するため、一部の問題でパフォーマンスが低下することが知られています。

アルゴリズムの考え方は非常に単純です。

• エッジの重みがペア間のユークリッド距離である、データ セットを使用して完全なグラフを作成します。
• エッジ リストを重みで並べ替えます。
• エッジごとに (順番に)、サイクルを形成しない場合はスパニング フォレストに追加します。すべてのエッジがトラバースされたとき、または残りのフォレストに k 個の木があるときに停止します。

結論: アルゴリズムがそのように失敗するのはなぜですか? クラスカルのせい？もしそうなら、なぜ正確に？クラスカルを放棄せずに結果を改善するための提案はありますか?

(1): Gionis、A.、H. Mannila、および P. Tsaparas、クラスタリング集約。ACM Transactions on Knowledge Discovery from Data(TKDD),2007.1(1):p.1-30.

このようなクラスカルアルゴリズムの時間計算量を計算しています（添付の画像のアルゴリズムを参照してください）

CLRS アルゴリズム:

それは正しいですか、それとも何か間違ったことをしていますか教えてください。

私は最小スパニングツリーを学んでいますが、この質問に遭遇し、試してみることにしました...

ランダムに生成された 100 個の頂点と 800 個のエッジの有向グラフ ネットワークに最小スパニング ツリー アルゴリズムを実装する

ランダムなエッジと頂点を生成する方法にこだわっています...提案やアイデアがあれば...

グラフ理論をいじって、クラスカルのアルゴリズムを C++ で実装し、視覚化に GraphViz を使用しましたが、コードを実行して次のコマンドで png ファイルを生成しました。

それはこれを示しています：

これを行うためにubuntu Linuxを使用しています。以下に添付されているのは私のC ++コードです

名前空間が間違っていないと思いますか、それとも他の方法でこれを行うのですか?

グラフのエッジがループを形成しているかどうかを確認する方法についての情報を教えてもらえますか? どの情報も非常に役立ちます。よろしくお願いします。

Kruskal アルゴリズムの実行時間を分析したところ、O(ElogE+Elogv+v) が得られました。

私は教授に尋ねたところ、グラフが非常にまばらで、多くの孤立した頂点がある場合、V が E を支配し、そうでない場合は E が V を支配し、その理由が理解できないと彼は言いました。グラフがまばらではないが、それでも V が E より大きい例を挙げることができます

この混乱を解消するのを手伝ってくれる人はいますか?