Deux des principales techniques descriptives du data mining sont la segmentation et la recherche d'associations.

La segmentation

        C'est l'opération qui consiste à répartir les données en un nombre limité de groupes ou de segments (ou clusters) ayant deux propriétés. D'une part, ils ne sont pas prédéfinis mais découverts automatiquement au cours de l'opération, contrairement aux classes de la Classification. D'autre part, les segments regroupent des données (ou des individus) ayant des caractéristiques similaires pour aboutir à une homogénéité interne et une hétérogénéité externe, ce qui peut être mesuré par des critères tels que celui de Concordet ou de l'inertie interclasse.

Elle est utilisée pour sa capacité à traiter les données sans en privilégier aucune (une variable cible), et pouvoir traiter des données hétérogènes ainsi qu'un grand nombre de variables.

En marketing, par exemple, cette technique descriptive est particulièrement adaptée pour la recherche des différents profils de clients, inconnus à priori.

La définition des segments est loin d'être évidente et peut différer selon l'algorithme, la détermination d'un nombre réel de segments est plus empirique que théorique.

La segmentation relationnelle

Principe

Une Segmentation relationnelle est définie comme une realtion d'équivalence R, où iRj si i et j sont dans le même segment. C'est une relation binaire définie sur un ensemble de n objets, on peut donc lui associer une matrice nxn définie par

mij = 1 si iRj et mij = 0 sinon.

On rappelle qu'une relation d'équivalence est réflexive, transitive et symétrique ce qui se traduit par:

mij = 1

mij = mji

mij + mjk - mik <= 1

La recherche d'une segmentation revient donc à chercher une matrice satisfaisant aux conditions précédentes.

Soit p variables catégoriques (nécessaire à ce type de segmentation). A chacune des p variables correspond une segmentation naturelle c'est à dire un ensemble d'individus ayant la même modalité pour la variable considérée. L'objectif est de trouver un bon compromis entre les p segmentations naturelles initiales. Pour cela, on pose mij le nombre de fois où les individus i et j ont été mis sur a même segment (le nombre de variables pour lesquelles i et j ont les mêmes valeurs).

On pose M' = (m'ij) où m'ij = 2 mij - p

m'ij > 0 si i et j sont dans le même segment où coïncident pour une majorité de variables.

m'ij < 0 si i et j sont dans des segments différents pour une majorité de variables.

m'ij = 0 s'il y a autant de variables pour lesquelles i et j sont réunis et séparés.

Il est naturel de grouper i et j si m'ij est positif et les séparer s'il est négatif. Mais si le critère ne suffit pas pour cause de non transitivité de la règle de majorité (paradoxe de Condorcet): on peut avoir une majorité pour i et j, j et k, mais pas pour réunir i,j et k.

Il faut donc ajouter des contraintes de la relation d'équivalence citée de la forme précédente pour trouver une segmentation satisfaisant au mieux la majorité des p segments initiaux. Ceci se ramène à un problème de programmation linéaire qui se résout bien comme l'ont montré les travaux de Marcotorchino et Michaud.

Mise en oeuvre

Soit une paire d'individus A et B. On commence par poser:

- m(A,B) := Nombre de variables ayant la même valeur pour A et B.

- d(A,B) := Nombre de variables ayant des valeurs différentes pour A et B.

Pour les variables continues on définit leur contribution c(A,B) ci-dessous définie par 1- (2|v(A)- v(B)|/(vmax - vmin)) où vmax, vmin sont les valeurs extrêmes de la variable v.

Le critère de Concordet de deux individus A et B est défini comme étant:

c(A,B):=m(A,B) - d(A,B)

Le critère de Concordet pour un segment S et un individu A est définit comme:

c(A,S) =  Somme sur tous les Bi de S de c(A, Bi)

Ceci posé, on commence la formation des segments en plaçant chaque individu A das le segment où c(A,S) est maximal.

En résumé, on prend un individu A et on le compare à tous les autres individus, pour le regrouper éventuellement avec un autre individu Ba. On prend un deuxième individu B que l'on compare à tous les autres et aux individus Ba et A.

On réitère le processus jusqu'à stabilité, le critère de Concordet ne s'améliore plus où jusqu'à atteindre le nombre maximal d'itérations.

Avantages et inconvénients

Avantages

- Déterminer automatiquement le nombre de segments au lieu de le fixer.

- Temps d'exécution croissant linéairement en fonction de la quantité de données.

- Segmentation globale.

Inconvénients

La redondance de quelques variables va être déterminante dans la mesure où elle oriente les résultats en sa faveur.

La segmentation neuronale

Les réseaux de Kohnen

Avant d'aborder ce thème, il est judicieux d'avoir une idée sur les réseaux neurones incontournables en data mining

C'est un réseau de neurones dit auto adaptatif, qui ne possède pas de variables à prédire donc pas de couches de sortie. Son but est "d'apprendre" la structure des données pour pouvoir y distinguer la structure des segments.

Il se compose de 2 niveaux:

- Une couche d'entrée avec un noeud pour chacune des n variables utilisées.

- Une couche cachée avec des noeuds disposés en grille rectangulaire (de l x m noeuds). Chaque noeud de cette couche est connecté à tous les noeuds de la couche d'entrée avec un poids pijk (i varie de [1, l], j varie de [1, m], k varie de [1, n] ). Les noeuds de la couche cachée ne sont pas connectés entre eux.

On initialise les poids pijk aléatoirement, ensuite pour tout individu (xk) de l'échantillon d'apprentissage, on calcule les distances euclidiennes le séparant des l.m noeuds.

dij(x) = Somme de 1 à n de (xk - pijk)²

Le noeud retenu pour représenter (xk) est le noeud (i,j) pour lequel dij(x) est minimum. Ce noeud et tous les noeuds 8-voisins voient leur poids ajustés afin de les rapprocher de l'individu en entrée mais la taille du voisinage diminue au cours de l'apprentissage, il peut être réduit au noeud lui même.

Les nouveaux poids sont pijk + T (xk-pijk) où T est le taux d'apprentissage variant dans [0,1] évoluant de manière linéaire où exponentielle pour diminuer au cours de l'apprentissage.

C'est l'extension à tout le voisinage du noeud "gagnant " de l'ajustement des poids, qui rapproche les noeuds voisins de (i,j) de l'individu en entrée et qui permet à des individus proches dans l'espace des variables d'être représentés par des noeuds identiques ou voisins de la couche, lesquels noeuds correspondent à des segments d'individus. Le nombre de segments identifié par le réseau pourrait être inférieur à l.m

Tout se passe comme si la grille se déformait pour permettre le passage des nuages d'individus en s'approchant au plus près des individus.

Le réseau de Kohonen fonctionne en représentant chaque individu en entrée per le noeud du réseau qui lui est le plus proche au sens de la distance définie ci-dessus. Ce noeud sera le segment de l'individu.

Avantages et inconvénients

Une des forces des réseaux de Kohonen est de modéliser les relations non linéaires entre les données et permettent de fixer automatiquement le nombre de segments

Toutefois les défauts de cet algorithme sont multiples

- Le nombre d'itérations nécessaire à un résultat satisfaisant est de 5 à 10 itération contre 2 à 3 pour la segmentation relationnelle.

- Un bon apprentissage requière un échantillon de taille conséquente comprenant le plus grand nombre de modalités possibles.

- La distance euclidienne de 2 variables catégoriques n'est pas forcément très significative.

La segmentation hiérarchique ascendante

      Elle produit une suite de partitions emboîtées, entre la partition en n segments où chaque individu est isolé, et la partition en 1 segment qui regroupe tous les individus.

L'algorithme fonctionne en recherchant à chaque étape les deux classes les plus proches pour les fusionner , et le "sel" de cet algorithme réside dans la définition de la distance de deux classes. La notion correspondant le mieux à la segmentation est l'inertie interclasse. Une bonne segmentation est une segmentation pour l'inertie interclasse est élevée. Comme le passage d'une segmentation en k + 1 à une segmentation en k segments ne fait que baisser l'inertie interclasse. Les 2 segments fusionnés seront ceux qui feront le moins baisser cette inertie.

Remarque

Soit I l'inertie de la population qui est la moyenne des carrées des distances des individus au barycentre (centre de gravité) de la population.

L'inertie interclasse Ir est définie comme la moyenne (pondérée par l'effectif de chaque segment ) des carrées des distances des barycentres de chaque segment au barycentre global.

Inconvénients

La complexité algorithmique n'est pas linéaire car pour passer de (k + 1) à ((k + 1)k)/2 distances et réunir les 2 segments les plus proches puis recalculer les distances avant de recommencer.

Les segments construits ont tendance à être de même taille (même problème que la segmentation neuronale)

A chaque étape le critère de partitionnement n'est pas global mais local et dépende des segments déjà obtenus. 2 individus placés dans des segments différents ne seront plus comparés. Cette segmentation n'est jamais la meilleure possible mais la meilleure obtenue entre celles obtenues en réunissant des segments en n+1 segments.

La recherche d'associations

Principe

Une association est une règle du type

"Si pour un individu, la variable A = xa, la variable B = xb, etc, alors dans 80% des cas la variable Z = xz, cette configuration se rencontrant pour 20% des individus."

La valeur 80% est dite indice de confiance et la valeur de 20% est dite indice de support

Une règle est donc une expression de la forme

SI condition alors Résultat

Exemple

SI couches et samedi alors bière

Pour traduire la règle disant que la plupart des gens qui achètent des couches les Samedis achètent de la bière avec.

L'indice de support est la probabilité:

proba(condition et résultat)

l'indice de confiance est la probabilité:

proba(condition et résultat)/proba(condition)

Exemple

Chaque ligne correspond à un ticket de caisse Tx, et chaque colonne à un produit A,B... L'indice de confiance de l'association B -> E est 3/4 et son indice de support est de 3/5.

Indice de confiance de C -> B est de 2/3 et celui de support est de 2/5.

La probabilité d'avoir B est de 0.8 > 2/3 ce qui implique que utiliser la règle C -> B pour prédire B ne sert à rien.

L'amélioration apportée par une règle par rapport à une réponse au hasard est appelée "lift" et vaut

lift(règle) = Indice_confiance (règle)/proba(résultat)

= proba(condition et résultat)/(proba(condition)*proba(résutat)

Si lift < 1, la règle n'apporte rien.

On note que si le lift d'une règle du type (SI condition alors résultat) est < 1alors le lift de la règle inverse (SI condition alors NON résultat) est > 1 puisque

indice_Confiance (règle inverse)= 1 - indice_confiance(règle)

et

proba(Non résultat) = 1 - proba(résultat)

Si une règle n'est pas utile alors on peut toujours essayer la règle inverse.

La principale difficulté de la la mise en oeuvre réside dans le grand nombre de règles d'associations inintéressantes qui submergent celles qui peuvent être utiles.