コサイン類似性によるクラスタリング

Question

私はクラスタ化したい大きなデータセットを持っています。私の試運転セットのサイズは2,500オブジェクトです。私はそれを '本物の契約'で実行すると、少なくとも20k個のオブジェクトを処理する必要があります。

これらのオブジェクトは、それらの間にコサインの類似性を持っています。このコサイン類似度は、数学的距離メトリックであるという要件を満たしていない。三角不等式を満たさない。

私は期待していたクラスタの数をあらかじめ指定する必要なしに、類似のオブジェクトをまとめた「自然な」方法でクラスタリングしたいと考えています。

誰でもアルゴリズムを知っていますか？実際には、a）距離メトリックとb）あらかじめ指定された数のクラスタを必要としないアルゴリズムを探しています。

多くの感謝！ （しかし、このソリューションは唯一のK平均クラスタリング提供しています） Clustering from the cosine similarity values 、そしてここに：

この質問は、ここで前に頼まれてい Effective clustering of a similarity matrix （しかし、この解決策はかなり曖昧だった）

Answer 1

Apacheの象使いは番号を持っていますNを指定する必要がなく、距離メトリックを指定できるようなアルゴリズムも含まれます。

平均シフトクラスタリングは、k-meansに似ていますが、あらかじめ指定された数のクラスタがない場合https://cwiki.apache.org/confluence/display/MAHOUT/Mean+Shift+Clusteringです。

さらに一般的には、さまざまなアルゴリズムを試してみたいと思うならば、Rのために利用可能な洗練されたパッケージが絶対に豊富にあります（EMのいくつかの変分的ベイジアン実装を含みます。過去の私の研究のいくつかにとって非常に有用であることが判明しました：http://cran.r-project.org/web/views/Cluster.html。

Answer 2

実際には、「距離関数」を必要とするほとんどのアルゴリズムには、メトリックである必要はありません。

DBSCANは、距離から抽象化されたバージョンにも一般化することができます（Wikipedia参照）。ちょうど何か「密な」概念が必要です。 （DBSCANはあらかじめクラスター数を知る必要はありません）

しかし、k-手段であっても、距離的にも厳密な要件を持っていても、球体k-meansと呼ばれる変形があります。

とにかく、データベースのコンテキストでは、「メトリック」の完全な要件はユートピクになります。現実の世界のデータでは、同じ座標を持つ2つのレコードが存在する可能性があります。したがって、ほとんどの場合、擬似メトリックを持つことになります。三角不等式は、（例えば、厳密な三角不等式要件を有するM-ツリーインデックスを使用するなどして）最適化のための役割を主に果たし、またはこの特性を利用する加速されたk-meansを果たす。

Answer 3

また、Affinity Propagation（http://www.psi.toronto.edu/index.php?q=affinity%20propagation）を試すこともできます。このアルゴリズムは類似行列を入力として受け取り、クラスタの重心の数を自動的に調整することもできます。