問題タブ [hierarchical-clustering]

私のクラスタリングの問題では、ポイントが行き来するだけでなく、機能も削除または追加できます。私の問題に対するクラスタリングアルゴリズムはありますか?

具体的には、これらの種類のクラスタリング アルゴリズムの凝集階層クラスタリング バージョンを探しています。

クラスタリングの結果を比較するために調整済みランド指数を使用しようとしています。ここでは、例としてアイリスデータセットを使用します。これらはコードです：

まず、上の表の値を使用して、ARI（Hubert and Arabie、1985）を手動で計算します。答えは0.7311986です。ただし、Rを使用すると、同じ答えが得られません。

おそらく、私が値を入れる方法が間違っています。Rからの答えが手動計算と同じになるようにこれを実装する方法はありますか？

階層的クラスタリングツリーがあります（リンケージを使用）。各クラスターには、そのクラスターのコストに対応する樹状図の独自のレベルがあります。コストc1のn1クラスター、コストc2のn2クラスター、およびコストc3のn3クラスターの予算があります。問題は、予算を使用してすべての元のアイテムをカバーするクラスターを選択することです。およびc1>c2>c3。コストc1のクラスターは、明らかにc2またはc3クラスターに使用できます。

予算カテゴリが1つしかない場合、解決策は簡単です。ルートから開始し、c1の下に移動するときに各サブツリーに追加します。サブツリーの前にn1カテゴリが終了した場合、解決策はありません。

2つのカテゴリの場合も簡単です。c1コストのすべての候補を検索します。それらにc2サブクラスターの数でラベルを付け、降順で並べ替えます。ラベルが最大のc1カテゴリを選択します。次に、c2クラスターを選択します。

ただし、c2カテゴリの並べ替えは必ずしもc3予算を追跡するとは限らないため、2つ以上のカテゴリの場合は問題が複雑になります。

いくつかのデータ ポイントをクラスター化したいのですが、クラスターあたりのポイントの最大数が制限されています。そのため、クラスターごとに最大サイズがあります。そのためのクラスタリングアルゴリズムはありますか? また、独自のサイズ関数を定義できますか。たとえば、クラスター内のポイントの数をそのサイズと見なす代わりに、クラスター内のすべてのポイントの列を合計したいと考えています。

データセット (列 1 = 遺伝子名、列 2 = 発現値) を使用しており、クラスター プロットを実行しようとしていますが、列の遺伝子 ID ではなく行番号で枝がラベル付けされていることがわかりました。 1.

データセット: https://dl.dropbox.com/u/364456/miRNA.csv

使用:

結果のプロット:

kmeans クラスタリングを実行しようとしましたが、最終的にこのエラーが発生しました。

強制によって導入された NA。

これは、データ ファイルを正しくフォーマットしていないことを示しています。

ここで何が起こっているか知っている人はいますか？

マーカーが紛らわしい方法で重なり合うように、ユーザーがズームアウトした場合でも、正確で読みやすく、高速な方法でマップ上の何千ものアイテムをマークする問題を解決する必要があります。それは AndroidMapViewですが、私の質問はより一般的です。

Fluster、グリッドベースのスキーム、およびさまざまなヒューリスティック を認識しています。

これらのアルゴリズムは、クラスター マーカーが重心に対応していないという点で不正確であるように見えます。私のアプリケーションは安全性が重要であり、マーカーがかなり大きいため、近似では十分ではありません。

アルゴリズムを発明した後、それが最初に使用されたのは 80 年代であることがわかりました。その適切な説明は、「凝集型の階層的な幾何学的重心クラスタリング」です。 疑似コードは次のとおりです。

ここで、各クラスターの重心に 1 つのマーカーを描画します。

(1) を効率的にするために、更新可能な Delaunay 三角形分割と優先キューを使用しましたが、最近、削除を伴う kd ツリーも機能することがわかりました。DT アルゴリズムは、kd ツリーと同じ漸近的な複雑さ (O(n log n) 平均) ですが、実際にはより高速になると思います。

質問：

• クラスターを見つけるためのより良いアルゴリズムはありますか? 貪欲なアルゴリズムでは、最小量でマーカーを分離するために厳密に必要なクラスターよりも少ないクラスターが生成される可能性があります。最大のセットを見つけることは、おそらく NP 困難です。貪欲よりも優れたヒューリスティックはありますか?
• Delaunay 三角形分割の代わりに kd-tree を試す価値はありますか? 10,000 ノードでの DT のパフォーマンスは、高速タブレットではわずかです。ズーム後最大 2 秒です。
• クラスター重心にマーカーを配置する既存のパッケージはありますか?

「調整された完全な」リンケージについて私が見つけることができる唯一の説明は、「完全なリンケージと同じですが、クラスター距離内で最大である」のようなものです。

「クラスター距離内」とはどういう意味ですか？

このリンケージアプローチを使用して、2つのクラスター間の距離は最終的にどのように計算されますか？

返信ありがとうございます！

いろいろ検索しましたが、WEKA HierarchicalClusterer の使い方を説明しているサンプルコードは見つかりませんでした。次の C# コードを使用すると、「agg.buildClusterer(insts);」で IllegalArgumentException が発生します。

スタックトレースは次のように述べています。

ただし、Message または InnerException は指定されていません。変数「insts」はインスタンス オブジェクトであり、同量の数値属性を持つインスタンスのみを保持します。

誰かが私のエラーをすぐに見つけることができますか、またはいくつかのサンプルコードを投稿/リンクしてください? また、LinkType（コメントコード）の設定は正しいですか？

ありがとう、ビョルン

データを階層的クラスターツリーにグループ化できるアルゴリズムがあります。このアルゴリズムは、TobySeagramのProgrammingCollectiveIntelligenceで説明されているものです。ツリー出力は、各ノードに「距離」値を持つ2分木であり、2つの子ノードがどれだけ離れているかを示します。

次に、これを樹状図として表示できます。これにより、値がグループ化されている人間のスポットがかなり簡単になります。ただし、グループを自動的に決定するアルゴリズムを思い付くのは困難です。自動的に判断できるようにしたいと思います。

• グループの数
• 各グループにどのポイントを配置する必要がありますか

このための標準的なアルゴリズムはありますか？