Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

CHAPITRE 2 : LA CLASSIFICATION AUTOMATIQUE 1 I. INTRODUCTION La classification

CHAPITRE 2 : LA CLASSIFICATION AUTOMATIQUE 1 I. INTRODUCTION La classification automatique (appelée clustering en anglais) est une méthode mathématique d’analyse de données. Pour faciliter l’étude d’une population d’effectif important (animaux, plantes, malades, gènes.. .), on regroupe les individus qui la forment en plusieurs classes de telle sorte que les individus d’une même classe soient les plus semblables possibles et que les classes soient les plus distinctes possibles les unes des autres. Regrouper des éléments entre eux facilite mieux l’interprétation d’une grande quantité de données. Ainsi, les objectifs de la classification sont de regrouper les individus décrits par un ensemble de variables, ou regrouper les variables observées sur des individus et d'interpréter ces regroupements par une synthèse des résultats. L'intérêt de regrouper les individus est ici de les classer en conservant leur caractère multidimensionnel, et non pas seulement à partir d'une seule variable. Si les variables sont nombreuses il peut être intéressant de les regrouper afin de réduire leur nombre pour une interprétation plus facile. II. STRUCTURES DE DONNEES Les objets (échantillons, mesures, modèles, événements) sont représentés comme des points (vecteurs) dans un espace multidimensionnel, où chaque dimension représente un attribut distinct (variable, mesure) décrivant l'objet. Ainsi, un ensemble d'objets est représenté comme une matrice mxn, avec m lignes, une pour chaque objet et n colonnes, une pour chaque attribut. Cette matrice est appelée matrice de données ou jeu de données. La figure ci-dessous, fournit un exemple concret d’une matrice de données. Matrice de données III. MATRICE DE PROXIMITE Plusieurs algorithmes de clustering utilisent la matrice de données originale et beaucoup d’autres emploient une matrice de similarité, ou une matrice de dissimilarité. Pour la convenance, les deux matrices sont généralement mentionnées comme une matrice de proximité P. Une matrice de proximité P est une matrice mxm contenant toutes les dissimilarités ou les similarités entre les objets considérés. Si pi et pj sont le ième et le jème objets, respectivement, alors l' entrée à la ième ligne et la jème colonne de la matrice de proximité est la similarité, ou la dissimilarité, entre pi et pj. Matrice de proximité                   np x ... nf x ... n1 x ... ... ... ... ... ip x ... if x ... i1 x ... ... ... ... ... 1p x ... 1f x ... 11 x                 0 ... ) 2 , ( ) 1 , ( : : : ) 2 , 3 ( ) ... n d n d 0 d d(3,1 0 d(2,1) 0 CHAPITRE 2 : LA CLASSIFICATION AUTOMATIQUE 2 IV. DISTANCE ET SIMILARITE En classification, que les données se présentent initialement sous forme d'un tableau individus-variables ou non, toute l'information utile est contenue dans un tableau nxn donnant les dissemblances entre les n individus à classer. On appelle distance sur un ensemble M toute application d : M2 → [0, ∞[ telle que :  pour tout (x, y) ∈ M2, on a d(x, y) = 0 si et seulement si x = y.  pour tout (x, y) ∈ M2, on a d(x, y) ≥ 0.  pour tout (x, y) ∈ M2, on a d(x, y) = d(y, x).  pour tout (x, y, z) ∈ M3, on a d(x, y) ≤ d(x, z) + d(z, y). Lorsque l’on a seulement les trois conditions ci-dessous vérifiées, on parle de dissimilarité.  pour tout (x, y) ∈ M2, on a d(x, y) = 0 si et seulement si x = y.  pour tout (x, y) ∈ M2, on a d(x, y) ≥ 0.  pour tout (x, y) ∈ M2, on a d(x, y) = d(y, x) . Une similarité est une application s telle que:  pour tout (x, y) ∈ M2, on a s(x, y) = 0 si et seulement si x = y.  pour tout (x, y) ∈ M2, on a s(x, y) ≥ 0.  pour tout (x, y) ∈ M2, on a s(x, y) = s(y, x) Par exemple, soient m ∈ N∗, x=(x1, . . ., xm)∈ Rm et y=(y1, . . . , ym) ∈ Rm. On appelle distance euclidienne entre x et y la distance Elle est d’autant plus petite que les deux individus sont semblables (du point de vue des valeurs des deux critères retenus) et d’autant plus grande qu’ils sont différents. On peut associer à chaque nuage d’individus une matrice D dite matrice des distances. C’est une matrice à n lignes et n colonnes à coefficients positifs, symétrique vue que d(x,y) = d(y,x) et nulle sur la diagonale vu que d(x,y)=0. Pour un nuage d’effectif n, il y a donc n (n−1) / 2 distances à calculer. A coté de la distance euclidienne, on peut définir d’autres distances et donc d’autres matrices des distances. Plusieurs distances existent dans la littérature, à titre d’exemple nous citons quelques distances classiques: Distance de Manhattan Soient m ∈ N∗, x=(x1, . . ., xm)∈ Rm et y=(y1, . . . , ym) ∈ Rm. On appelle distance de Manhattan (p=1) entre x et y la distance Distance de Minkowski (généralisation de la distance euclidienne) Soient m ∈ N∗, q ≥ 1, x=(x1, . . ., xm) ∈ Rm et y=(y1, . . . , ym) ∈ Rm. On appelle distance de Minkowski (généralisation de la distance euclidienne) entre x et y la distance CHAPITRE 2 : LA CLASSIFICATION AUTOMATIQUE 3 Distance de Camberra Soient m ∈ N∗, x=(x1, . . ., xm)∈ Rm et y=(y1, . . . , ym) ∈ Rm. On appelle distance de Camberra entre x et y la distance Distance maximum Soient m ∈ N∗, x=(x1, . . ., xm)∈ Rm et y=(y1, . . . , ym) ∈ Rm. On appelle distance maximum entre x et y la distance V. TYPES DE DONNEES La mesure de proximité et le type de clustering utilisé dépendent des types des attributs de données . On retrouve cinq types d'attributs à savoir :  Variables numériques Ex : poids, taille, longitude, latitude, etc.  Variables binaires : une valeur parmi deux possibles. La variable absente est représentée par 0 et la variable présente est représentée par 1.  Variables nominale : les valeurs sont juste des noms différents. Par exemple : les codes postaux, les couleurs, le sexe. La valeur est prise dans une liste finie , Ex : couleur : « vert, bleu, rouge, jaune, noir »  Variables ordinales : les valeurs reflètent un ordre, rien plus. Par exemple: bon, meilleur, mieux. L’ordre des valeurs est plus important.  Variables ratios : rapport entre deux grandeurs. par exemple : les quantités monétaires, comme le salaire et le bénéfice et beaucoup de quantités physiques comme le courant électrique, la pression, etc. VI. Similarités entre objets décrits par des variables numériques continues  Normalisation des données Elle consiste à mettre les valeurs dans un intervalle entre 0 et1. CHAPITRE 2 : LA CLASSIFICATION AUTOMATIQUE 4 Exemple : ID Sexe Age Salaire 1 F 27 19 000 2 M 51 64 000 3 M 52 100 000 4 F 33 55 000 5 M 45 45 000 dist(ID2, ID3) = sqrt((0-0)2 + (51-52)2 + (64 000-100 000)2 ) = sqrt( 0 + 1 + (36 000)2) =.sqrt(1296000001)= 36 000. dist(ID2, ID4) = sqrt((0-1)2 + (51-33)2 + (64 000-55 000)2 ) = sqrt( 1 + (18)2+ (9)2) =sqrt(406)= 20,14. On conclut que ID2 ressemble plus à ID4 qu’à ID3. Afin de normaliser les données, on calcule : Max salaire – Min salaire : 100000-19000 = 79000 Max âge – Min âge: 52-27 = 25 Et, on obtient le tableau normalisé suivant : ID Sexe Age Salaire 1 1 0,00 0,00 2 0 0,96 0,56 3 0 1,00 1,00 4 1 0,24 0,44 5 0 0,72 0,32 dist(ID2, ID3) = sqrt((0-0)2 + (0.96-1,00)2 + (0.56-1,00)2 ) = sqrt( 0 + (0.04)2 + (0.44)2) = 0.44. dist(ID2, ID4) = sqrt((0-1)2 + (0.96-0,24)2 + (0.56-0,44)2 ) = sqrt( 1 + (0.72)2+ (0.12)2) = 1.24. On conclut que ID2 ressemble plus à ID3 qu’à ID4.  Standardisation des données On égalise le poids des variables pour assurer l’indépendance par rapport aux unités de mesures. Pour ceci, on utilise l'écart type (possible aussi avec l'écart absolu moyen) CHAPITRE 2 : LA CLASSIFICATION AUTOMATIQUE 5 où Puis on calcule la mesure standardisée (z-score) : VII. SIMILARITES ENTRE OBJETS DECRITS PAR DES VARIABLES BINAIRES Dans le cas où n individus sont décrits par la présence ou l'absence de p caractéristiques. De nombreux indices de similarité ont été proposés qui combinent de diverses manières les quatre nombres suivants associés à un couple d'individus: a = nombre de caractéristiques communes; b = nombre de caractéristiques possédées par i et pas par j ; c = nombre de caractéristiques possédées par j et pas par i ; d = nombre de caractéristiques que ne possèdent ni i et uploads/s3/ clustering-tchi-drive.pdf