Memoire Online - Application du processus de fouille de données d'usage du web sur les fichiers logs du site cubba

Nous exposons dans ce qui suit les distances les plus usuelles pour les données quantitatives.

Soient I et J deux points dans un espace E d'individus décrit par p variables quantitatives. On note i = (xi1, xi2, ..., _xip) et j = (xj1, xj2, ..., _xjp). La distance entre X et Y peut se calculer selon

+ La distance Euclidienne : qui calcule la racine carrée de la somme des carrés des

+ La distance de Manhattan : qui calcule la somme des valeurs absolues des différences entre les coordonnées de deux points :

+ La distance de Chebychev : qui calcule la valeur absolue maximale des différences entre les coordonnées de deux points :

3.3. Les méthodes hiérarchiques

La classification hiérarchique est une famille de techniques qui génèrent des suites de classes emboîtés les uns dans les autres. Les techniques de classification existantes dans cette famille peuvent être classées dans deux grands groupes : Classification Ascendante Hiérarchique (CAH) ou par agrégation et Classification Descendante Hiérarchique (CDH) ou par division.

Dans le groupe CAH, tous les individus sont initialement considérés comme des classes ne contenant qu'un seul individu. A chaque étape du processus de classification, les deux classes les plus proches au sens d'une mesure d'agrégation sont fusionnées. Le

processus s'arrête quand les deux classes restantes fusionnent dans l'unique classe contenant tous les individus.

Les techniques dans le groupe CDH partent de la partition triviale à une seule classe (contenant toutes les observations). Le processus de classification suit en effectuant de divisions successives des classes jusqu'à ce que soit atteint la partition triviale où chaque observation est une classe. La division d'une classe s'opère de façon à ce que la mesure d'agrégation entre les deux classes descendants soit la plus grande possible, de manière à créer deux classes bien séparés.

Les classes résultants des méthodes de classification hiérarchiques sont souvent représentés par une structure graphique appelé dendrogramme. Les typologies qui ont le plus de chance d'être significatives sont obtenues simplement en traçant une ligne horizontale en travers du dendrogramme, et en retenant dans la typologie les classes terminales justes audessus de cette ligne. En changeant la hauteur de la ligne, l'on change le nombre de classes retenus. Cette pratique constitue un moyen simple pour faire varier la granularité de la typologie finale.

Dans ce groupe, il existe plusieurs méthodes d'agrégation possibles entre deux classes. Le choix de la méthode dépend de la problématique que l'on se pose. En ce qui concerne la distance entre deux individus, la distance euclidienne est la plus utilisée en général.

Parmi les méthodes d'agrégation existantes pour chaque couple de classes, nous citons ciaprès les plus classiques :

d (A; B) = min

i?A;j?B

d(xi; xj)

+ agrégation selon le lien moyen (average linkage) : l'agrégation entre deux classes A et B correspond à la moyenne des distances entre un élément du classe A et un élément du classe B.

+ la méthode de Ward : on choisira de regrouper les deux classes qui génèrent le gain d'inertie intra-classe minimum.

Selon le théorème de Huygens, l'inertie total T d'un ensemble d'individus E est égale à la somme des inerties intra-classe W et inter-classe B de cet ensemble d'individus regroupés dans une partition P.

C'est la moyenne des carrées des distances des individus au centre de gravité .ou T(E) = W(P) + B(P)

g : valeur du centre de gravité de la population %7 l'inertie intra-classes : W(P)

Avec k : le nombre de classes de la population %7 inertie inter-classes : B(P)

g: valeur du centre de gravité de la population initiale. P : poids de la classe

L'inertie intra-classe d'une partition mesure l'homogénéité de l'ensemble de classes. Une classe sera d'autant plus homogène que son inertie intra-classe sera faible. L'inertie interclasse d'une partition mesure la séparation entre les classes qui la composent. Plus l'inertie

interclasse d'une partition est grande plus les classe sont distinctement séparées. Deux cas particuliers sont à considérer :

L'inertie intra-classe d'une partition croit avec la diminution du nombre de classes, où encore, l'inertie intra-classe décroit avec l'augmentation du nombre de classes dans la partition.

Le but de l'algorithme CAH est de passer de la meilleure partition de k classes à la meilleure partition de (k-1) classes selon le critère d'agrégation adopté. Selon ce critère, pour passer d'une partition P^K à une partition P^K-1, on choisira de regrouper les deux classes qui génèrent le gain d'inertie intra-classe minimum. Ce gain est calculé de la façon suivante :

Soit A et B deux classes, uA et uB leurs respectifs poids. Le gain d'inertie intra classe engendré par le regroupement de ces deux classes est donné par l'écart de Ward. L'écart de Ward peut être vu comme une distance entre deux classes si la distance entre deux individus est la distance euclidienne.

Gain (A; B) =_ uAuB

uA+uB

d² (gA ; gB)

iEA

iEB

xiwi

La recherche du nombre approprié de classes dans une partition est une phase indispensable dans la construction d'une classification de données, mais elle est souvent laborieuse et délicate. Si le choix du nombre de classes dans une partition ne correspond pas au vrai nombre de classes existantes dans un ensemble d'individus, alors la partition choisie soit regroupe à tort des classes séparées (pas assez de classes), soit découpe en plusieurs classes des classes homogènes (trop de classes).

Dans les méthodes de classification hiérarchiques, le dendrogramme indique l'ordre dans lequel les agrégations (ou divisions) successives ont été opérées ainsi que la valeur de l'indice à chaque niveau d'agrégation (ou division). La problématique consiste à trouver le meilleur couple de contraintes opposées : inertie intra-classe et nombre de classes dans la partition, puisque à chaque fois que l'on diminue le nombre de classes dans la partition, son inertie intra-classe augmente.

Pour déterminer le bon nombre de classes, Il est pertinent d'effectuer la coupure du dendrogramme après les agrégations correspondant à des valeurs peu élevées de l'indice utilisé et avant les agrégations correspondant à des valeurs élevées de cet indice. En coupant le dendrogramme au niveau d'un saut important de cet indice, on peut espérer obtenir une partition de bonne qualité car les individus regroupés en-dessous de la coupure seront proches, et ceux regroupés au-dessus de la coupure seront éloignés.

D'après application de l'algorithme de CAH avec le critère d'agrégation de Ward, on connait à chaque étape les deux classes à rassembler et l'inertie intra-classe de la partition ainsi composée. La meilleure coupure du dendrogramme sera obtenue par un coude sur les valeurs du critère optimisé. Ce critère est l'inertie intra-classe. L'on trace le graphique des n- 1 gains d'inertie intra-classe obtenus à chaque itération de l'algorithme. Parmi les innombrables règles de détection du nombre adéquat des classes, il y a la fameuse « loi du coude » : nous cherchons visuellement la zone où la variation de courbure est la plus importante, traduisant l'idée d'une modification significative des proximités des variables à l'intérieur des groupes.

Application du processus de fouille de données d'usage du web sur les fichiers logs du site cubba

3.2. Les mesures de distances

3.3. Les méthodes hiérarchiques