問題はおそらく、完全な 2D 距離行列 (単純に倍精度で約 8 GB) を計算しようとすることであり、O(n^3)いずれにせよアルゴリズムは時間内に実行されます。
別のクラスタリング アルゴリズムの使用を真剣に検討する必要があります。階層クラスタリングは遅く、通常、結果はまったく説得力がありません。特に何百万ものオブジェクトの場合、デンドログラムを見て適切なカットを選択することはできません。
あなたが本当に階層的クラスタリングを続けたいのなら、ELKI (ただし Java) には のO(n^2)実装があると思いSLINKます。これは、100 万個のオブジェクトで約 100 万倍高速になるはずです。彼らもすでに持っているかどうかはわかりませんCLINK。O(n^3)また、シングルリンクと完全リンク以外のバリアントのサブアルゴリズムが実際に存在するかどうかはわかりません。
他のアルゴリズムの使用を検討してください。たとえば、k-means はオブジェクトの数に非常によく対応します (データが非常にクリーンで規則的でない限り、通常はあまり良くありません)。パラメータの感触がつかめば、私の意見ではかなり良いと思いますDBSCAN。OPTICSデータ セットの次元が低い場合は、適切なインデックス構造を使用して高速化できます。クエリ時間O(n log n)のあるインデックスがある場合は、で実行する必要があります。O(log n)これは、大規模なデータセットに大きな違いをもたらす可能性があります. 私は個人的OPTICSに 110k の画像データ セットを問題なく使用したので、システム上で 100 万までスケールアップできると想像できます。
O(n^2) を打ち負かすには、最初に 1M ポイント (ドキュメント) を、たとえば、それぞれ 1000 ポイントの 1000 の山、またはそれぞれ 10k の 100 の山に減らす必要があります
。2 つの可能なアプローチ:
たとえば 15k ポイントから階層ツリーを構築し、残りを 1 つずつ追加します: time ~ 1M * treedepth
最初に 100 個または 1000 個のフラット クラスターを構築し、次に 100 個または 1000 個のクラスター センターの階層ツリーを構築します。
これらのいずれかがどれだけうまく機能するかは、ターゲット ツリーのサイズと形状 (レベルの数、葉の数) に大きく依存します。
使用しているソフトウェアは何ですか?また、クラスタリングを行うのに何時間/何日かかりますか?
フラットクラスターアプローチの場合、 K-d_treeは 2d、3d、20d、さらには 128d のポイントに対して正常に機能します-あなたの場合ではありません。テキストのクラスタリングについてはほとんど何も知りません。 地域に敏感な_ハッシング?
scikit-learn クラスタリングを見てみましょう。これには、DBSCAN を含むいくつかの方法があります。
追加:
google-all-pairs-similarity-searchも参照してください
。「スパース ベクトル データ内のすべての類似したベクトルのペアを見つけるためのアルゴリズム」、Beyardo et al. 2007
SO 階層クラスタ化ヒューリスティック