Explication de l'algorithme de regroupement des leaders

Question

J'essaie de comprendre cet algorithme, mais je n'arrive pas à obtenir les documents et les explications appropriés. Quelqu'un peut-il m'aider s'il vous plaît à comprendre cet algorithme de regroupement.

Answer 1

Affichage de la réponse pour qu'elle soit utile aux autres.

L'algorithme leader est un algorithme de clustering incrémental généralement utilisé pour regrouper de grands ensembles de données. Cet algorithme dépend de l'ordre et peut former des clusters différents en fonction de l'ordre dans lequel l'ensemble de données est fourni à l'algorithme. L'algorithme comprend les étapes suivantes.

Étape 1: Affectez le premier élément de données, P1 au cluster C1. Cet ensemble de données sera le leader du cluster C1. Étape 2: Passez maintenant à l'élément de données suivant, disons P2, et calculez sa distance par rapport à l'amorce P1. Si la distance entre P2 et le leader P1 est inférieure à un seuil spécifié par l'utilisateur (t), le point de données P2 est affecté à ce groupe (groupe C1). Si la distance entre le leader P1 et l'élément de données P2 est supérieure au seuil t spécifié par l'utilisateur, alors formez un nouveau cluster C2 et attribuez P2 à ce nouveau cluster. P2 sera le leader du cluster C2.

Etape 3: Pour tous les éléments de données restants, la distance entre le point de données et l'amorce des grappes est calculée. Si la distance entre les éléments de données et l'un quelconque du repère est inférieure au seuil spécifié par l'utilisateur, le point de données est affecté à ce cluster. Toutefois, si la distance entre le point de données et l'un des leaders du cluster est supérieure au seuil spécifié par l'utilisateur, un nouveau cluster est créé et ce point de données particulier est attribué à ce cluster et considéré comme le leader du cluster.

Étape 4: Répétez l'étape 3 jusqu'à ce que tous les éléments de données soient affectés aux groupes.

Exemple pour clarifier la théorie.

Considérons les motifs sont situés à

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

Soit les données traitées dans l'ordre A, B, C, D, E, F and G, et le seuil spécifié par l'utilisateur T soit 3. A(1, 1) est le premier élément de données traité et il est affecté au cluster C1 et a également fait office de leader de C1.

Pour le deuxième point B, sa distance par rapport au leader A est calculée. En utilisant la formule de distance euclidienne (Distance(a, b)) = √(x - a)² + (y - b)²), nous obtenons la distance comme √(1 - 1)² + (1 - 2)² = 1, c'est inférieur au seuil 3, alors B est affecté au cluster 1.

spécifié par l'utilisateur Pour le troisième point C(2, 2) la distance entre le leader A(1, 1) de le groupe C1 et le point C est calculé. En utilisant la formule euclidienne, la distance est √(1 - 2)² + (1 - 2)² = 1.41, ce qui est inférieur à seuil, donc C est également attribué à C1. La distance entre A et D (√ (1 - 6) ² + (1 - 2) ² = 5,099) est supérieure au seuil spécifié par l'utilisateur 3, un nouveau cluster est créé et D est affecté au cluster C2. D est le leader de ce cluster.

Pour le point E, sa distance par rapport A (leader du C1) et D (chef de C2) est calculé. Depuis Distance(D,E) est inférieur au seuil défini par l'utilisateur 3, il est assigné à se regrouper 2.

La distance F à partir de A (le leader de C1) est 7.07 et de D (le leader de C2) est 4. Ces deux distances sont au-dessus du seuil et par conséquent F est placé dans le nouveau cluster C3 et devient le leader de ce cluster. Pour G les Distance(A,G), Distance(D,G) et Distance(F,G) sont 7.81, 6.41 et 1 respectivement. Depuis Distance(F,G) est inférieur à l'utilisateur spécifié 3 il est affecté à regrouper 3.

On peut voir que si les données avaient été traitées dans un ordre différent, les grappes dirigeants auraient été différentes, même les groupes peuvent varier. Si C s'est produite avant A et B, alors C aurait été le leader de C1. Si D s'est produite avant et la distance entre C et D était inférieure au seuil, il aurait été dans C1. Ce ne peut pas se produire si A est le leader. L'algorithme leader dépend donc de l'ordre et peut donner des résultats différents en fonction de l'ordre de traitement.