8

不透明なオブジェクトのリストがあります。私はそれらの間の距離を計算することしかできません(問題の条件を設定するだけです):

class Thing {
    public double DistanceTo(Thing other);
}

これらのオブジェクトをクラスター化したいと思います。クラスターの数を制御したいのですが、「近い」オブジェクトを同じクラスターに配置したいと考えています。

List<Cluster> cluster(int numClusters, List<Thing> things);

誰かが私を助けることができるいくつかのクラスタリングアルゴリズム(より単純であるほど良い!)またはライブラリを提案(および;-)にリンクできますか?

明確化ほとんどのクラスタリング アルゴリズムでは、オブジェクトを N 次元空間に配置する必要があります。この空間は、クラスターの「重心」を見つけるために使用されます。私の場合、N が何かも、オブジェクトから座標系を抽出する方法もわかりません。私が知っているのは、2 つのオブジェクトがどれだけ離れているかだけです。その情報のみを使用する優れたクラスタリング アルゴリズムを見つけたいと思います。

オブジェクトの「匂い」に基づいてクラスタリングしていると想像してください。2D 平面上で「においを出す」方法はわかりませんが、2 つのにおいが似ているかどうかはわかります。

4

5 に答える 5

6

K-Medoidsを探していると思います。事前にクラスター数Kを指定するという点で K-means に似ていますが、K-means のようにクラスター化するオブジェクトを「平均化」するという概念は必要ありません。

代わりに、すべてのクラスターには、中央に最も近いクラスターのメンバーである代表的なmedoidがあります。これは、「手段」ではなく「中央値」を見つける K-means のバージョンと考えることができます。必要なのは、物事をクラスター化するための距離メトリックだけです。私は、あなたが引用したのとまったく同じ理由で、これを自分の作品のいくつかで使用しました。

単純な K-medoids は最速のアルゴリズムではありませんが、おそらく目的には十分である高速なバリアントがあります。アルゴリズムの説明と、Rでの実装に関するドキュメントへのリンクを次に示します。

  1. PAMは、K-medoid の基本的な O(n^2) 実装です。
  2. CLARAは、はるかに高速なサンプル バージョンの PAM です。これは、ランダムにサンプリングされたオブジェクトのサブセットを PAM でクラスタリングし、サブセットに基づいてオブジェクトのセット全体をグループ化することによって機能します。これにより、非常に優れたクラスタリングを高速に取得できるはずです。

さらに詳しい情報が必要な場合は、これらおよびその他の K-medoids メソッドの概要を説明している論文を参照してください。

于 2009-04-04T21:21:47.740 に答える
3

これは、重心を見つけるためのK-means要件を持たないクラスタリングアルゴリズムの概要です。

  1. すべてのオブジェクト間の距離を決定します。n個の最も別々のオブジェクトを記録します。
    [クラスターのルートを見つけます。時間O（n ^ 2） ]
  2. これらのn個のランダムポイントのそれぞれをn個の新しい個別のクラスターに割り当てます。
  3. 他のすべてのオブジェクトの場合：
    [オブジェクトをクラスターに割り当て、時間O（n ^ 2） ]
    1. 各クラスターの場合：
      1. クラスター内の各オブジェクトからオブジェクトまでの距離を平均して、クラスターからそのオブジェクトまでの平均距離を計算します。
    2. オブジェクトを最も近いクラスターに割り当てます。

このアルゴリズムは確かにオブジェクトをクラスター化します。ただし、その実行時間はO（n ^ 2）です。さらに、最初に選択したnポイントによってガイドされます。

誰かがこれを改善できますか（実行時のパフォーマンスが向上し、最初の選択にあまり依存しません）？私はあなたのアイデアを見てみたいです。

于 2009-03-28T19:54:03.070 に答える
2

これが簡単なアルゴリズムです。

While (points_left > 0) {
 Select a random point that is not already clustered
 Add point and all points within x distance 
   that aren't already clustered to a new cluster.
}

または、ウィキペディアのページをお読みください。K-means クラスタリングは適切な選択です。

K-means アルゴリズムは、中心 (重心とも呼ばれます) が最も近いクラスターに各ポイントを割り当てます。中心は、クラスター内のすべてのポイントの平均です。つまり、その座標は、クラスター内のすべてのポイントの各次元の算術平均です。

アルゴリズムの手順は次のとおりです。

* Choose the number of clusters, k.
* Randomly generate k clusters and determine the cluster centers, or
  directly generate k random points as cluster centers.
* Assign each point to the nearest cluster center.
* Recompute the new cluster centers.
* Repeat the two previous steps until some convergence criterion is
  met (usually that the assignment hasn't changed).

このアルゴリズムの主な利点は、大規模なデータセットで実行できるシンプルさと速度です。その欠点は、結果のクラスターが最初のランダムな割り当てに依存するため、各実行で同じ結果が得られないことです。クラスター内の分散を最小限に抑えますが、結果の分散が全体的に最小になるわけではありません。別の欠点は、常にそうであるとは限らない、定義可能な平均の概念に対する要件です。このようなデータセットには、k-medoids バリアントが適しています。

于 2009-03-28T00:59:58.350 に答える
1

このアプローチはどうですか：

  1. すべてのオブジェクトを 1 つのクラスターに割り当てます。
  2. 同じクラスターk内にあり、最大距離にある 2 つのオブジェクトaとbを見つけます。明確にするために、クラスタごとに1 つのaとbではなく、セット全体に1 つのaとbが必要です。
  3. クラスターkをk1とk2の2 つのクラスターに分割します。1 つはオブジェクトaで、もう 1 つはオブジェクトbです。
  4. クラスターk内の他のすべてのオブジェクトについて、そのクラスター内の他のすべてのオブジェクトへの最小平均距離を決定することにより、それらをk1またはk2のいずれかに追加します。
  5. N 個のクラスターが形成されるまで、手順 2 ～ 5 を繰り返します。

効率はかなり悪いかもしれませんが、このアルゴリズムはかなり良いクラスタリングを提供するはずだと思います。効率を改善するには、ステップ 3 を変更して、クラスター内に既に存在するすべてのオブジェクトまでの平均距離ではなく、クラスターを開始した元のオブジェクトのみまでの最小距離を見つけることができます。

于 2009-03-28T21:28:13.920 に答える
1

Phylogenetic DNA sequence analysis regularly uses hierarchical clustering on text strings, with [alignment] distance matrices. Here's a nice R tutorial for clustering:

(Shortcut: Go straight to the "Hierarchical Agglomerative" section...)

Here are some other [language] libraries :

This approach could help determine how many [k] "natural" clusters there are and which objects to use as roots for the k-means approaches above.

于 2009-04-04T20:36:44.667 に答える