Présentation sur BIRCH (Balanced Iterative Reducing and clustering using hierarchies)

Résumé du document

Comment évaluer une méthode de clustering ?
- L'homogénéité intra cluster et l'hétérogénéité inter cluster.
- L'insensibilité à l'ordre des objets.
- Connaissances minimales du domaine pour définir les paramètres.
- Résultat interprétable et utilisable.

Pour les bases de données de grand volume :
- Utilisation optimisée de l'espace mémoire.
- Minimisation du temps requis pour les opérations d'ES

(...)

- Un noeud interne est un cluster composé de sous clusters organisés sous forme d'entrées.
- Chaque entrée dispose d'un pointeur vers un noeud fils.
- Le nombre de sous clusters par noeud interne ne dépasse pas B : "Branching Factor".
- Une feuille est un cluster composé de sous clusters organisés sous forme d'entrées.
- Chaque entrée dispose de 2 pointeurs : "previous" et "next".
- Le nombre de sous clusters par feuille ne dépasse pas L.

(...)

- Si l'insertion de O dans le sous-cluster entrainerait la violation du seuil T (rayon max) ?
. Créer un nouveau sous-cluster (sc),
. Sc contient seulement O.

- Si la création de sc entrainerait la violation de L (nbre max de sous-cluster dans une feuille) ?
. Scinder la feuille (split).

(...)

Extraits

[...] Le vecteur CF du cluster obtenu par l'union des clusters A et B est : CF1 + CF2 = ( N1 + N LS1+ LS SS1+ SS2 ) Si alors 05/11/19 < number > Etape Construction de CF Tree Pour chaque objet Traverser l'arbre de la racine vers une feuille en choisissant à chaque niveau le sous-cluster le plus proche. O est inséré dans le sous-cluster le plus proche de la feuille. MAJ le CF du sous-cluster, de la feuille et des nœuds parents. Parcours des objets et insertion un par un dans CF Tree. [...]

[...]  Connaissances minimales du domaine pour définir les paramètres.  Résultat interprétable et utilisable . 05/11/19 < number > Introduction Pour les bases de données de grand volume :  Utilisation optimisée de l'espace mémoire.  Minimisation du temps requis pour les opérations d'E\S ( accès aux données sur disque) Fournir le résultat du clustering en minimisant le temps de réponse. 05/11/19 < number > Birch (1996)  Algorithme hiérarchique hybride ( agglomération + division  Algorithme incrémental.  Conçu principalement pour les BD volumineuses. [...]

[...] Le CF Tree est chargé en MC au lieu des données originales. 05/11/19 < number > CF Tree  Un nœud interne est un cluster composé de sous clusters organisés sous forme d'entrées.  Chaque entrée dispose d'un pointeur vers un nœud fils.  Le nombre de sous clusters par nœud interne ne dépasse pas B : ‘Branching Factor'.  Une feuille est un cluster composé de sous clusters organisés sous forme d'entrées.  Chaque entrée dispose de 2 pointeurs : ‘previous' et ‘next'. [...]

[...] minimiser le coût d'entrée/sortie en travaillant sur un résumé compact des données Limites: Dépendance de l'ordre des objets Ne traite que les données numériques. 05/11/19 < number > Bibliographie BIRCH: An Efficient Data Clustering Method for Very Large Databases : Tian Zhang Raghu Ramakrishnan Miron Livny , Computer Sciences Dept, Univ. of Wisconsin-Maciison. Data Mining lecture notes : Samuel Kleiner, Lauren Foutz, Jason Forbes, Rensselaer Polytechnic Institute , Computer Science Department, NY. Cours de Classification non-supervisée : Andreea B. DRAGUT, Université de la Méditerrannée (IUT Aix), Laboratoire d'Informatique Fondamentale. [...]

[...] Reconstruction de l'arbre pour qu'il puisse accueillir le reste des objets. 05/11/19 < number > Reconstruction de l'arbre 3 paramètres: Taille de l'arbre (nombre de pages): Taille d'un nœud (facteur de branchement Seuil d'absorption Dépendent des ressources Dépend de l'algorithme  Augmenter T  arbre plus petit. 05/11/19 < number > Reconstruction de l'arbre Copier chaque chemin allant de la racine vers une feuille de l'ancien arbre ti vers le nouvel arbre ti+1. Essayer de faire absorber les sous-clusters des feuilles du chemin copié par les sous-clusters des feuilles de ti+1 (nouveau seuil Terminer le parcours des objets restants. [...]