グループ平均クラスタリングのアルゴリズム的複雑度

Question

最近、について、single-linkage clusteringとgroup average clusteringのようにさまざまなものを読んでいます。一般的に、これらのアルゴリズムは拡張性に優れていません。ほとんどの階層的クラスタリングアルゴリズムの純粋な実装はO(N^3)ですが、シングルリンケージクラスタリングはO(N^2)時間に実装できます。

また、グループ平均クラスタリングはO(N^2 logN)時間に実装できると主張されている。これは私の質問についてです。

私はこれがどうして可能かわかりません。

のような説明の後に説明、：

http://nlp.stanford.edu/IR-book/html/htmledition/time-complexity-of-hac-1.html

http://nlp.stanford.edu/IR-book/completelink.html#averagesection

https://en.wikipedia.org/wiki/UPGMA#Time_complexity

は...グループ平均の階層的クラスタリングは、プライオリティキューを使用してO(N^2 logN)時間で行うことができると主張しています。しかし、私が実際の説明や擬似コードを読むと、いつもそれはO(N^3)より優れていると私には思われます。

次のように基本的に、アルゴリズムは次のとおりです。

For an input sequence of size N: 

Create a distance matrix of NxN #(this is O(N^2) time) 
For each row in the distance matrix: 
    Create a priority queue (binary heap) of all distances in the row 

Then: 

For i in 0 to N-1: 
    Find the min element among all N priority queues # O(N) 
    Let k = the row index of the min element 

    For each element e in the kth row: 
    Merge the min element with it's nearest neighbor 
    Update the corresponding values in the distance matrix 
    Update the corresponding value in priority_queue[e] 

---

だから、それは私には、このO(N^3)アルゴリズム作るように思われる、その最後のステップです。優先度キューがバイナリヒープであると仮定して、O(N)時間にキューをスキャンせずに、優先度キューの任意の値を「更新」する方法はありません。 （バイナリヒープはmin要素に常にアクセスし、​​の挿入/削除を行いますが、単にO(N)時間よりも良い値で要素を見つけることはできません）。各行要素の優先度キューをスキャンするので、各行に対して(O(N^3))が得られます。

プライオリティキューは、距離値によってソートさ - が、当該アルゴリズムは、最小要素の距離行列の行インデックス、kに対応するプライオリティキュー内の要素を削除するための呼び出し。この場合も、O(N)スキャンを実行しないとキュー内のこの要素を見つける方法はありません。

他の人がそうでないと言っているので間違っていると思います。誰かがこのアルゴリズムが何らかの形でどのように説明できるかはO(N^3)ではありませんが、実際にはO(N^2 logN)？

Answer 1

ヒープ内のエントリを更新するには、それを見つけなければならず、発見に時間がかかる（O（N））という問題があると思います。これを実現するためにできることは、各項目iに対してヒープ内の位置heapPos [i]を与える索引を維持することです。ヒープ不変を復元するために2つのアイテムを交換するたびに、ヒープで行われた作業の定数ファクタであるため、インデックスを正しく保つためにheapPos [i]の2つのエントリを変更する必要があります。

Answer 2

いいえ、距離行列が対称であるためです。

行0の最初のエントリが列5、距離1、それがシステム内で最も小さい場合、行5の最初のエントリは、列0の補完エントリであり、距離は1でなければなりません。

実際にハーフマトリックスが必要です。

Answer 3

位置をヒープに格納すると（別のO（n）メモリが追加されます）、変更された位置でのみスキャンせずにヒープを更新できます。これらの更新は、ヒープ上の2つのパス（1つの削除、1つの更新）に制限され、O（log n）で実行されます。あるいは、古い優先度でバイナリ検索することもできます。これはO（log n）でも可能です（ただし、上記のアプローチはO（1）です）。

だから、実際にはこれらをO（n^2 log n）に実装できます。しかし、実装ではまだ多くのメモリ（O（n^2））が使用され、O（n^2）のどれもではなく、のスケールが使用されます。通常、 O（n^2）のメモリがある場合は、時間がなくなる前にメモリが不足します。

これらのデータ構造の実装は非常に難しいです。そして、うまくいけば、これは理論的に悪いアプローチよりも遅くなるかもしれません。例えば、フィボナッチヒープ。彼らは紙に良い性質を持っていますが、支払うには高額の固定費があります。