Soutenance mémoire
Les familles d’algorithmes du data mining
La segmentation
La segmentation, aussi souvent appelée « clustering », consiste en une séparation d’un ensemble ou groupe de données en plusieurs sous-ensembles. Ces sousensembles, les clusters, sont des regroupements d’éléments ou individus homogènes entre eux, mais qui diffèrent des autres sous-ensembles [31]. L’objectif est donc de regrouper les données en « grappes » (clusters) pour former un nouvel attribut, en minimisant l’inertie intra-classe pour former des clusters et en maximisant l’inertie intra-classe pour obtenir des sous ensembles très différents les uns des autres [39]. La segmentation est non supervisée, c’est-à-dire qu’on ne connaît pas les nouvelles classes qui seront créées. Cette méthode peut être utilisée en termes d’exploration de données ou comme étape de prétraitement pour d’autres algorithmes. Il peut s’avérer plus facile d’extraire des informations en créant préalablement des clusters, puisque plusieurs modèles peuvent être en compétition, ce qui complexifie l’extraction de connaissances [13].
Il existe deux grandes catégories d’algorithmes de segmentation : la méthode hiérarchique et le partitionnement [31, 40]. D’une part, la méthode hiérarchique produit une hiérarchie de clusters et non seulement une partition unique d’objets. De plus, le nombre de clusters(K) n’est pas obligatoirement donné, ce qui constitue un avantage considérable par rapport à certains algorithmes comme K-means. La représentation du résultat est un arbre de clusters, appelé dendrogramme. En ce qui concerne le partitionnement, il faut donner au préalable le nombre de clusters pour l’algorithme. Cependant, cet aspect accélère le traitement puisque les données sont divisées en groupes qui ne se chevauchent pas.
Pour évaluer les meilleurs groupements de données, la stratégie le plus souvent utilisée est une fonction de distance, appliquée à chaque donnée. Tout d’abord, il faut préciser cette notion de distance. La distance doit être supérieure ou égale à 0 (1). La distance vaut 0 si l’élément x est égal à l’élément y (2). La distance est la même si l’élément x et y sont interchangé (3). La distance entre x et y est inférieure ou égale à la somme de la distance entre x et y et la distance entre y et z (4).
(l)d(x,y)>0
(2)d(x,y) = 0Six = y
(3)d(x,y) = d(y,x)
(4)d(x,y)<d(x,y) + d(y,z)
Les algorithmes de segmentation
Le choix de l’algorithme est un facteur déterminant pour la suite du processus. Plusieurs algorithmes existent pour la segmentation, mais il serait trop long de tous énumérer. C’est pourquoi il sera question de deux algorithmes en particulier, K-means et EM.
L’algorithme K-means
K-means, l’un des algorithmes les plus utilisés en data mining [42], consiste à diviser l’ensemble des données en un nombre prédéfini de clusters, appelé k [41]. Tous les k points sont ensuite positionnés semi-aléatoirement (1) (se référer à la figure 3 de la page suivante). Ces points, les centroides [31], deviennent les centres des nouveaux clusters crées. Chaque élément est par la suite rattaché à l’un de ces nouveaux groupes, selon la méthode de distance utilisée (2). On replace ensuite le centre de gravité pour qu’il se retrouve au centre des individus de son groupe (3). On répète l’étape 2 et 3 jusqu’à l’algorithme converge et que les centres ne se déplacent plus ou presque, ou jusqu’à ce qu’une fonction avec critère d’arrêt soit activée. Pour un algorithme itératif, il n’est pas certain que l’algorithme atteigne un minimum global pour enclencher l’arrêt [23]. Cependant, en pratique, l’algorithme converge rapidement vers un résultat.
L’Algorithme EM
L’algorithme EM est une approche générale qui effectue un calcul itératif pour trouver des estimateurs du maximum de vraisemblance lorsque les données sont incomplètes ou manquantes. Il tient cette appellation du fait que l’algorithme consiste en une étape de calcul d’espérance et une de maximisation [8].
La classification
Le but de la classification est de prendre plusieurs attributs pour représenter une classe. En fait, il faut prédire si une donnée ou un individu appartient à un groupe ou à une catégorie donnée. Pour ce faire, le processus se réalise en deux étapes. La première partie est de créer un modèle sur un ensemble d’apprentissages (ou training set en anglais). Chaque élément doit donc appartenir à une classe prédéfinie. Cet ensemble ne comprend pas toutes les données, puisqu’une partie est nécessaire pour tester l’efficacité du modèle. Le modèle résultant peut être représenté comme un arbre de décision, des règles de classifications, des fonctions mathématiques, etc. Par la suite, il faut tester avec un deuxième ensemble, l’ensemble de tests. Cette étape permet d’évaluer le taux d’erreur. Le taux d’erreur est obtenu avec le pourcentage de données de tests incorrectement évaluées par le modèle. Une notion reste néanmoins importante pour l’élaboration des ensembles d’entraînement et de test : la notion d’induction. L’induction qui consiste à déterminer les attributs pertinents qui permettront de former le modèle de prédiction. La taille des deux ensembles est un réglage important. Si le modèle d’apprentissage est trop complexe, alors il n’y aura aucun apprentissage ou un risque de surapprentissage puisqu’il s’agit d’un calque sur les données. D’un autre côté, si le modèle est trop simple et qu’on ne peut faire des liens entre les attributs, alors on peut comparer la tâche à une sélection de classe aléatoire. Il faut donc un compromis entre ces deux cas de figure. Il faut que le modèle soit de taille moyenne et qu’il prenne un recul face aux données [13]. Si la taille de l’échantillon est trop petite, il existe des méthodes pour tenter de pallier au problème. L’une d’entre elles s’appelle le « bootstrap ». Cet algorithme utilise un principe de pige avec remise pour construire un grand ensemble de données d’entrainement. De ce fait, certaines données apparaîtront de multiples fois dans cet ensemble. Par la suite, les données n’ayant jamais été pigées se retrouvent dans l’ensemble de tests [37]. Grâce à ces ensembles, des évaluations du modèle peuvent être effectuées pour tester le taux d’erreur. Ce processus est ensuite exécuté en boucle pour obtenir plusieurs modèles. Finalement, on calcule l’erreur moyenne de chacun des modèles obtenus et celui se rapprochant le plus de ce taux d’erreur est sélectionné comme « modèle moyen ». Cette solution nous permet donc de croiser les données de différentes manières afin de simuler un plus grand échantillon de données. Par contre, ceci reste une simulation et ne fournit pas toujours un résultat réaliste.
Algorithme Knn, plus proche voisin
L’algorithme des K-plus proches voisins est un algorithme simple, mais qui peut donner des résultats intéressants si l’étendue des données est assez grande. Il s’agit d’une méthode de classification largement utilisée dans plusieurs domaines et qui se retrouve aussi parmi les 10 meilleurs algorithmes de fouille de données [42]. Pour faire une analogie, il est possible de comparer cet algorithme à un quartier. Normalement, les maisons se retrouvant proches les unes des autres ont des caractéristiques semblables. On peut donc les regrouper et leur donner une classification. L’algorithme utilise cette même logique pour tenter de regrouper les éléments se trouvant près les uns des autres .
CONCLUSION
La fouille de données est un domaine qui est utilisé depuis quelques années et on commence à comprendre toute la force que ce procédé peut avoir. Même s’il s’avère difficile de l’appliquer dans le monde réel, l’idée générale et les découvertes qui ont pu ressortir avec les techniques sont surprenantes. Pour un domaine comme celui du marketing par exemple, être en mesure de reconnaître les traits d’un acheteur procure un avantage non négligeable. Il existe de nombreuses techniques de fouille de données, autant pour la segmentation que pour la classification. Les recherches ne cessent de progresser et les techniques se peaufinent avec les nouvelles découvertes et les améliorations des algorithmes. Les algorithmes comme K-means , EM , C4.5 ou l’approche des plus proches voisins ont été utilisés à de nombreuses reprises et on fait leur preuve quant à leur efficacité. Dans ce chapitre, un retour sera fait sur les objectifs réalisés, sur les limitations et les projets futurs qui pourraient être réalisés.
|
Table des matières
CHAPITRE 1 INTRODUCTION
1.1 Contexte de recherche
1.2 Le forage de données
1.3 Résumé de la revue littéraire
1.4 Contribution du mémoire
1.5 Méthodologie de la recherche
1.6 Organisation du mémoire
CHAPITRE 2 LA DÉCOUVERTE DE NOUVELLES CONNAISSANCES
2.1 Mise en contexte
2.2 Processus et techniques
2.3 Les familles d’algorithmes du data mining
2.4 Exemple d’application enjeu vidéo
2.5 Conclusion
CHAPITRE 3 MODÈLE PROPOSÉ ET VALIDATION
3.1 Les données
3.2 Développement et mise en place
3.3 Implementation
3.4 Conclusion
CHAPITRE 4 EXPÉRIMENTATION ET ANALYSE DES RÉSULTATS
4.1 Contraintes
4.2 Objectifs expérimentaux
4.3 Protocole detest
4.4 Résultats expérimentaux
4.5 Analyse comparative et discussion
CHAPITRE 5 CONCLUSION
Télécharger le rapport complet
