8

私はいくつかのより大きなデータセットをクラスター化しようとしています。次元7の50000個の測定ベクトルで構成されています。さらに処理するために、約30〜300個のクラスターを生成しようとしています。

私は運が悪かった次のクラスタリングの実装を試してきました：

  • Pycluster.kcluster（データセットに空でないクラスターを1〜2個だけ指定します）
  • scipy.cluster.hierarchy.fclusterdata（実行時間が長すぎます）
  • scipy.cluster.vq.kmeans（メモリ不足）
  • sklearn.cluster.hierarchical.Ward（実行時間が長すぎます）

私が見逃すかもしれない他の実装はありますか？

4

5 に答える 5

11

50000インスタンスと7次元はそれほど大きくはなく、実装を強制終了するべきではありません。

Pythonバインディングはありませんが、ELKIを試してみてください。彼らがホームページで使用しているベンチマークセットは、8次元で110250インスタンスであり、明らかに60秒でk-meansを実行し、350秒ではるかに高度なOPTICSを実行します。

階層的クラスタリングは避けてください。これは実際には小さなデータセット専用です。行列演算で一般的に実装される方法はですO(n^3)。これは、大規模なデータセットには非常に適していません。だから私はあなたのためにこれらの2つがタイムアウトしたことに驚かない。

インデックスサポートを使用して実装した場合のDBSCANおよびOPTICSはO(n log n)です。素朴に実装された場合、それらはにありO(n^2)ます。K-meansは非常に高速ですが、多くの場合、結果は満足のいくものではありません（常に中央で分割されるため）。O(n * k * iter)通常、あまり多くの反復で収束しない状態で実行する必要があります（ iter<<100）。ただし、ユークリッド距離でのみ機能し、一部のデータ（高次元、離散、バイナリ、サイズの異なるクラスターなど）ではうまく機能しません。

于 2012-06-19T06:06:18.593 に答える
6

すでにscikit-learnを試しているので、マルチコアマシンでの並列フィッティングsklearn.cluster.KMeansよりも拡張性が高く、サポートされているはずです。それでも良いですが、ランダムに再起動することはありません。WardMiniBatchKMeans

>>> from sklearn.cluster import MiniBatchKMeans
>>> X = np.random.randn(50000, 7)
>>> %timeit MiniBatchKMeans(30).fit(X)
1 loops, best of 3: 114 ms per loop
于 2012-06-19T08:42:14.590 に答える
3

私のパッケージミルクはこの問題を簡単に処理します。

import milk
import numpy as np
data = np.random.rand(50000,7)
%timeit milk.kmeans(data, 300)
1 loops, best of 3: 14.3 s per loop

50kポイントはそれほど多くないので、50万データポイントを書き込むつもりだったのではないかと思います。その場合、ミルクはもう少し時間がかかります（〜700秒）が、データと重心以外のメモリを割り当てないため、それでもうまく処理されます。

于 2012-09-21T16:50:05.853 に答える
0

OpenCVにはk-means実装、Kmeans2があります

予想される実行時間はO(n**4)-のオーダーです。桁違いの概算では、1000ポイントをクラスター化するのにかかる時間を確認し、それに700万を掛けます（50 ** 4を切り上げ）。

于 2012-06-19T02:16:25.120 に答える
0

実際の大規模な状況に対する本当の答えは、効率的な類似性検索と高密度ベクトルのクラスタリングのために、FacebookResearchのライブラリであるFAISSのようなものを使用することです。

https://github.com/facebookresearch/faiss/wiki/Faiss-building-blocks:-クラスタリング、-PCA、-量子化を参照して ください

于 2021-07-13T23:10:20.677 に答える