リーダークラスタリングアルゴリズムの説明

Question

私はこのアルゴリズムを理解しようとしていますが、適切な文書と説明を得ることはできません。誰かが私がこのクラスタリングアルゴリズムを理解するのを助けてくれますか？

Answer 1

他人に役立つように投稿する。

リーダーアルゴリズムは、大きなデータセットをクラスタ化するために一般的に使用される増分クラスタリングアルゴリズムです。このアルゴリズムは順序に依存し、データセットがアルゴリズムに提供される順序に基づいて異なるクラスターを形成することがあります。アルゴリズムは、以下のステップからなる。

手順1：最初のデータ項目P1をクラスタC1に割り当てます。このデータセットは、クラスターC1のリーダーになります。

ステップ2：次のデータ項目、たとえばP2に移動し、リーダーP1からの距離を計算します。 P2とリーダーP1との間の距離がユーザ指定の閾値（t）よりも小さい場合、データ点P2がこのクラスタ（クラスタC1）に割り当てられる。リーダーP1とデータ項目P2との間の距離がユーザ指定の閾値tよりも大きい場合、新しいクラスタC2を形成し、この新しいクラスタにP2を割り当てる。 P2はクラスタC2のリーダーになります。

ステップ3：残りのすべてのデータ項目について、データポイントとクラスタのリーダー間の距離が計算されます。データ項目とリーダーのいずれかの間の距離がユーザー指定のしきい値より小さい場合、データポイントはそのクラスターに割り当てられます。ただし、データポイントとクラスタリーダーのいずれかの距離がユーザー指定のしきい値を超える場合、新しいクラスターが作成され、その特定のデータポイントがそのクラスターに割り当てられ、クラスターのリーダーとみなされます。

手順4：すべてのデータ項目がクラスタに割り当てられるまで手順3を繰り返します。

理論を明確にする例。

はパターンが

A (1, 1),B(1, 2), C(2, 2), D(6, 2), E(7, 2), F(6, 6), G(7, 6) 

に配置されている検討データが順A, B, C, D, E, F and Gで処理すること、およびユーザ指定の閾値は3ことTう。 A(1, 1)は、処理された最初のデータ項目であり、クラスタC1に割り当てられ、C1のリーダーにもなります。

Bの2番目のポイントでは、リーダーからの距離がAと計算されます。ユークリッド距離の式（Distance(a, b)) = √(x - a)² + (y - b)²）、我々は√(1 - 1)² + (1 - 2)² = 1として距離が取得を使用 が、これはそうBは、第三の点C(2, 2)リーダーA(1, 1)の間の距離のクラスタ1

に割り当てられ、ユーザ指定のしきい値3未満でありますクラスタC1およびポイントCが計算されます。ユークリッドの公式を使用すると、距離はであり、これは 閾値よりも小さいので、CもC1に割り当てられます。 AとDの間の距離（√（1 - 6）2 +（1 - 2）²= 5.099）がユーザー指定のしきい値3を超えているため、新しいクラスタが作成され、DがクラスタC2に割り当てられます。 Dはこのクラスタのリーダーです。

は点Eについて、A（C1のリーダー）とD（C2のリーダー）からの距離を算出します。 Distance(D,E)がユーザ指定のしきい値3次に小さいので、AからFまでの距離（C1のリーダー）（C2のリーダー）7.07とDからであるクラスタ2

に割り当てられ4あります。 これらの距離はいずれもしきい値を超えているため、Fが新しいクラスタC3に入れられ、このクラスタのリーダーになります。 については、Gについては、Distance(A,G),Distance(D,G)およびDistance(F,G)はそれぞれ7.81,6.41および1である。 Distance(F,G)ので、ユーザ少ないし、データが異なる順序で処理されていた場合は、クラスタ 指導者が異なる-も、クラスターは変え​​ることができたであろうことを。見ることができ、クラスタ3

に割り当てられている3に指定されています AおよびBの前にCが発生した場合、CはC1のリーダーになります。以前にDが発生し、の距離がCとDの間にある場合は、C1になります。この は、Aがリーダーである場合は発生しません。したがって、リーダーアルゴリズムは順序に依存し、処理の順序に基づいて異なる結果を与えることがあります。