Méthodologie pour le placement des capteurs à base de méthodes de classification en vue du diagnostic

Algorithmes par partitionnement 

Un algorithme de classification par partitionnement obtient une unique partition des données au lieu d’une structure hiérarchisée comme dans le cas précédent. Les méthodes de partitionnement ont l’avantage de manipuler une grande quantité d’ensembles de données, pour lesquelles, la construction d’un graphe hiérarchisé permettant de tout couvrir serait difficile. Un des problèmes relatifs aux algorithmes de partitionnement est le choix du nombre de classes désirées en sortie. Dans [Dubes, 1987] un guide pour choisir ce paramètre clé pour la conception est donné. Cette technique produite des classes en optimisant une fonction critère définie soit localement (sur un sous-ensemble d’éléments) soit globalement (définie sur l’ensemble des éléments). L’algorithme est réitéré de multiple fois avec différents nombres de classes de sortie, et la meilleure configuration obtenue est utilisée pour le choix de la classe de sortie. – Algorithmes de minimisation de l’erreur quadratique Cet algorithme est basé sur la minimisation d’un critère quadratique, critère qui est le plus utilisé dans les algorithmes de partitionnement, et qui est bien adapté dans le cas de classes séparées et compactes. L’erreur quadratique pour une classe L parmi K classes d’un ensemble d’éléments H est définie par : 2 j K j 1 nj i 1 (j) i 2 e (H,L) = ∑∑ x − c = = ( 1.1 ) où est le i (j) i x ème élément qui appartient à la j ème classe et cj est le centre de la j ème classe. L’algorithme k-means est le plus simple et le plus connu des algorithmes de minimisation d’un critère quadratique [McQueen, 1967]. Il débute avec une partition initiale aléatoire et il déplace les éléments dans les classes sur la base de la similarité entre l’élément et le centre de la classe par minimisation du critère (( 1.1 ) jusqu’à convergence (quand il n’y a pas de reaffectation d’élément d’une classe à une autre, ou lorsque l’erreur quadratique ne décroit plus significativement après un certain nombre d’itérations ). L’algorithme k-means est populaire parce qu’il est facile à implanter. Un des problèmes majeurs de cet algorithme est qu’il est sensible au choix de la partition initiale et qu’il peut converger vers un minimum local de la fonction critère si la partition initiale n’est pas choisie de manière adéquate. La Figure 1-10 montre sept éléments en deux dimensions. Si nous commençons avec les éléments A, B et comme moyennes initiales les centres, trois classes sont construites, ceci conduit à la partition {{A},{B, C},{D, E, F, G}} où les classes sont représentées par des ellipses. La valeur du critère de l’erreur quadratique est beaucoup plus grande pour cette partition que pour la meilleure partition : {{A, B, C}, {D, E}, {F, G}} représentée par des rectangles, laquelle produit la valeur minimale globale de la fonction critère de l’erreur quadratique pour une classification sur trois classes. La solution correcte (trois classes) est obtenue en choisissant, par exemple, A, D et F comme les moyennes initiales des classes. Figure 1-10 Sensibilité de l’algorithme k-Means à la partition initiale 

Procédure de l’algorithme k-Means

Choisir k centres de classes pour coïncider avec les k points définis aléatoirement dans l’hyper volume contenant l’ensemble d’éléments. 2. Assigner chaque élément au centre de la classe la plus proche. 3. Recalculer les centres des classes en utilisant les nouveaux éléments de la classe. 4. Si un critère de convergence n’est pas satisfait, répéter l’étape 2. Ces critères de convergence typique sont : pas de nouvelle re-affectation d’éléments à un nouveau centre de classe, ou non-évolution du critère de l’erreur quadratique. Plusieurs variantes de l’algorithme k-Means ont été rapportées dans la littérature [Anderberg, 1973]. Quelques algorithmes essaient de choisir une bonne partition initiale, pour que l’algorithme ait plus de possibilité de trouver la valeur du minimum global. Une autre variante est de permettre de diviser et de fusionner les classes résultantes. Typiquement, une classe est divisée quand sa variance est au-dessus d’un seuil préétabli, et deux classes sont fusionnées quand la distance entre leurs centres est au-dessous d’un autre seuil pré-spécifié. En utilisant cette modification, il est possible d’obtenir une partition optimale en commençant par une partition initiale arbitraire, avec des valeurs de seuils correctement choisis. L’algorithme ISODATA [Ball et al., 1965] utilise cette technique pour diviser et fusionner les classes. Si ISODATA prend comme partition initiale les ellipses de la Figure 1-10, il produira la partition optimale composée de trois classes. ISODATA d’abord fusionnera les classes {A} et {B, C} dans une classe parce que la distance entre leurs centres est la plus petite et ensuite divisera la classe {D, E, F, G} qui possède une grande variance, en deux classes : {D, E} et {F, G}.

  Algorithmes issus de la théorie des graphes 

Tout d’abord, définissons un concept important pour ce type d’algorithme. L’algorithme STA (« Spanning Tree Algorithm ») est un protocole de dialogue entre tous les ponts permettant de supprimer des liens redondants et de ne garder que les liens les plus intéressants (lignes de communications les plus rapides, les moins coûteuses, etc.).  Le plus connu de ces algorithmes est basé sur la construction du « MST » (minimal spanning tree) des données [Zahn, 1971]. Les segments du MST avec les plus grandes longueurs sont ensuite supprimés pour produire les classes. La Figure 1-11 représente le MST obtenu à partir de neuf points en deux dimensions. En supprimant le segment étiqueté CD avec une longueur de 6 unités (le segment avec la longueur Euclidienne maximale), deux classes ({A, B, C} et {D, E, F, G, H, I}) sont obtenues. La deuxième classe peut être ultérieurement divisée en deux classes en supprimant la branche EF, laquelle a une longueur de 4.5 unités.