Algorithme de clustering Canopy - Canopy clustering algorithm

L' algorithme de clustering canopy est un algorithme de pré- clustering non supervisé introduit par Andrew McCallum , Kamal Nigam et Lyle Ungar en 2000. Il est souvent utilisé comme étape de prétraitement pour l' algorithme K-means ou l' algorithme de clustering hiérarchique . Il est destiné à accélérer les opérations de clustering sur de grands ensembles de données , où l'utilisation directe d'un autre algorithme peut être peu pratique en raison de la taille de l'ensemble de données.

La description

L'algorithme procède comme suit, en utilisant deux seuils (la distance lâche) et (la distance serrée), où . ${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}> T_ {2}}$

1. Commencez par l'ensemble de points de données à regrouper.
2. Supprimez un point de l'ensemble, en commençant une nouvelle «verrière» contenant ce point.
3. Pour chaque point laissé dans l'ensemble, attribuez-le à la nouvelle verrière si sa distance au premier point de la verrière est inférieure à la distance libre .${\ displaystyle T_ {1}}$
4. Si la distance du point est en outre inférieure à la distance étroite , retirez-la de l'ensemble d'origine.${\ displaystyle T_ {2}}$
5. Répétez à partir de l'étape 2 jusqu'à ce qu'il n'y ait plus de points de données dans l'ensemble à mettre en cluster.
6. Ces auvents groupés relativement bon marché peuvent être sous-groupés en utilisant un algorithme plus coûteux mais plus précis.

Une note importante est que les points de données individuels peuvent faire partie de plusieurs auvents. Comme accélération supplémentaire, une métrique de distance approximative et rapide peut être utilisée pour 3, où une métrique de distance plus précise et lente peut être utilisée pour l'étape 4.

Applicabilité

Puisque l'algorithme utilise des fonctions de distance et nécessite la spécification de seuils de distance, son applicabilité aux données de haute dimension est limitée par la malédiction de la dimensionnalité . Ce n'est que lorsqu'une fonction de distance peu coûteuse et approximative - de faible dimension - est disponible, les auvents produits conserveront les clusters produits par K-means.

Ses avantages comprennent:

• Le nombre d'instances de données d'entraînement qui doivent être comparées à chaque étape est réduit.
• Il existe des preuves que les clusters résultants sont améliorés.

Les références