bonsoir , s'il vous plait qui pouvez m'aider à programmer en langage C un problème d'une application en datamining : il traite en fonction d'une base de données fichier.txt contient 5690 enregistrement(chercheurs) et 24 attributs (18 catégorielles et 6 attributs de buts quantitatifs) un ensemble de conditions (une combinaison entre les différents attributs pour trouver des résultats souhaitables .
merci d'avance , ce qui pouvez m'aider voila mon email:abdellah.chebbab@gmail.com
pour plus d’explication voici une ma partie du PFE :
Une règle est considérée comme surprenante, contredisant les impressions générales de
l'utilisateur, dans la mesure où Ri et GI j ont des antécédents similaires mais des
conséquences contradictoires. En d'autres termes, plus la similarité entre les antécédents de
Ri et de GI j est importante et plus le degré contradictoire des conséquences de Ri et de
GI j est important, plus le degré de surprise de Ri par rapport à GI j est élevé.
Pour chaque paire de règles Ri et GI j , avec i variant de 1 à ∣R∣ et j variant de 1 à
∣GI∣ , l'algorithme génétique calcule le degré de surprise de Ri par rapport à GI j en
trois étapes :
1ère étape : trouver les impressions générales dont les conséquences contredisent la
conséquence de Ri .
La conséquence de Ri contredit la conséquence d'une impression générale GI j si et
seulement si Ri et GI j ont le même attribut de but mais une valeur différente pour cet
attribut. Par exemple, cela se produirait dans l'exemple suivant : si Ri prédit que "salaire =
bas" et que GI j prédit quant à lui que "salaire = élevé".
Si Ri et GI j prédisent des attributs de but différents ou si ils prédisent la même valeur
pour le même attribut de but, alors elles ne sont pas considérés comme contradictoires. Dans
ce cas, le degré de surprise de Ri par rapport à GI j est considéré comme nul (il vaut 0), et
l'étapes 2 et 3 sont ignorées.
2ième étape : calculer le degré de similarité entre les antécédents de Ri et GI j
Pour chaque impression générale GI j trouvée à l'étape précédente (c'est-à-dire pour chaque
impression générale GI j contredite par Ri ), on calcule le degré de similarité entre les
antécédents de Ri et de GI j . Ce degré de similarité, noté ASi , j , est calculé par la
formule suivante :
ASi , j= ∣Ai , j∣
max∣Ri∣,∣GI j∣
où ∣Ri∣ est le nombre de conditions (doublets attribut-valeur) de la règle Ri , ∣GI j∣ est le
nombre de conditionsdans l'impression générale GI j et ∣Ai , j∣ est le nombre de conditions
qui sont exactement identiques (c'est-à-dire qui ont le même attibut et la même valeur pour cet
attribut) dans Ri et GI j .
3ième étape : calculer le degré de surprise de Ri par rapport à GI j .
Soit Surp(i,j) le degré de surprise de Ri par rapport à GI j . Surp(i,j) dépend de ASi , j ,
calculée dans la deuxième étape, et de la différence entre les conséquences de Ri et GI j
calculée dans la première étape.
Les valeurs de l'attribut de but dans les conséquences de Ri et de GI j peuvent être soit une
valeur de l'ensemble {bas, élevé} soit une valeur de l'ensemble {bas, moyen, élevé}, cela
dépend de l'attribut de but (le choix entre ces 2 domaines pour un attribut est fait par
l'utilisateur pour chaque attribut).
Si la différence entre les conséquences de Ri et GI j est que l'une vaut bas et l'autre vaut
élevé, caractérisant la plus grande différence possible entre ces conséquences, alors Surp(i,j) sa
voit assignée la valeur de ASi , j . Si la différence entre les conséquences de Ri et GI j est
que l'une vaut moyen et l'autre vaut bas ou élevé, caractérisant une différence plus limitée entre
ces conséquences, alors Surp(i,j) se voit assignée la moitié de la valeur de ASi , j , c'est-àdire
que Surpi , j =0.5∗ASi , j .
Une fois que ces 3 étapes ont été faites pour toutes les impressions générales, par rapport à une
règle donnée Ri , ont été calculé tous les degrés de surprise de Ri par rapport à chaque
impression générale de l'utilisateur. On est donc en mesure de calculer le degré de surprise de
Ri par la formule suivante :
Surpi=max[ ASi , j]
j=1
∣GI∣
Sélection, croisement et mutation et autres opérateurs :
L'algorithme génétique fait appel à la méthode des tournois pour effectuer une sélection, cela
fonctionne de la manière suivante : tout d'abord k individus sont choisis au hasard et avec remise
(typiquement 2 dans notre cas). L'individu ayant la plus grande fitness parmi les k individus tirés au
hasard gagne le tournoi. Ce processus est répété P fois où P est la taille de la population, puis les P
individus se voient appliquer l'opérateur de croisement puis celui de mutation.
L'algorithme génétique utilise des opérateurs de croisement et de mutation relativement simples.
Pour le croisement il utilise la méthode du croisement uniforme. On fixe une probabilité de
croisement entre 2 individus et une probabilité d'échange entre chaque paire de gènes (les 2 gènes
représentant une valeur particulière pour le même attribut). La première est fixée à 0.85 et la
seconde à 0.5 . Le choix du croisement uniforme est motivé par le fait qu'avec cette méthode la
probabilité d'échange chaque paire de gènes, d'attributs, est indépendante de leur position dans le
génome. Ceci est souhaitable dans notre exemple où les antécédents de règle représentés par le
génome consiste en une ensemble non-ordonné de conditions.
L'opérateur de mutation se contente quant à lui de transformer de manière aléatoire la valeur d'un
attribut (d'un gène) en une autre valeur appartenant au domaine de l'attribut.
En plus des opérateurs de croisement et de mutation, l'algorithme génétique utilise également des
opérateurs chargés d'insérer ou de supprimer certaines conditions d'une règle. Le premier fait passer
à true le booléen d'un gène (d'une condition d'antécédent), la rendant par la même présente, alors
que le second le fait passer à false, supprimant cette condition de l'antécédent de la règle. Ces 2
opérateurs réalisent donc respectivement une opération de spécialisation et de généralisation. En
conséquence de quoi ils contribuent à une exploration plus large de l'espace de recherche, facilitant
l'exploration de zones de l'espace de recherche qui n'aurait pas été accessible aussi facilement en
utilisant seulement le croisement et la mutation.
Algorithme abstrait :
Spécifier, avec l'aide de l'utilisateur, les fonctions d'appartenance des attributs devant être flouttés.
Obtenir les impressions générales de l'utilisateur.
PourChaque conséquence de règle (doublet attribut de but - valeur) faire
Calculer la fréquence relative de la valeur de cet attribut de but dans l'ensemble qu'on étudie
au travers du data-mining.
Générer aéatoirement la population.
Appeler la fonction Calcule_Fitness.
Pour g de 1 à nombre de générations à engendrer faire
Générer une nouvelle population.
Appliquer l'opérateur de sélection.
Appliquer l'opérateur de croisement.
Appliquer l'opérateur de mutation.
Appliquer l'opérateur d'insertion de conditions dans une règle.
Appliquer l'opérateur de suppression de conditions d'une règle.
Appeler la fonction Calcule_Fitness.
FinPour
Renvoyer à l'utilisateur la règle ayant la fitness maximale avec les contraintes suivantes :
(Surp > 0) ET (Acc > max(0.5, FreqRel))
FinPourChaque
Procédure Calcule_Fitness
Calculer la précision (Acc) de chaque règle (individu) en réalisant une mise en correspondance
floue entre chaque règle et les données de l'ensemble étudié au travers du data-mining.
Calculer le degré de surprise (Surp) de chaque règle en mettant en correspondance la règle avec
chaque impression générale de l'utilisateur.
Calculer la fitness de chaque règle.
FinProcédure
Chaque itération de la boucle principale (la boucle PourChaque) cherche à découvrir la meilleure
règle possible (au niveau de la précision et de la surprise) prédisant une conséquence donnée.
L'algorithme renvoie une règle pour chaque conséquence devant être prédite. La règle renvoyée doit
satisfaire à 2 conditions : Surp > 0 et ACC > max(0.5, FreqRel). La première condition requiert
simplement que le degré de surprise de la règle soit supérieur à 0, de sorte à ce que cette règle
puisse être au moins considérée comme potentiellement intéressante à défaut de l'être réellement.
L'intérêt de la deuxième condition peut être exposé en étudiant 2 cas bien précis.
Premier cas :
supposons que la fréquence relative (dans l'ensemble de données sur lequel on travaille) de la
valeur
de l'attribut de but prédit par cette règle soit supérieure à 0.5. Il est alors logique de demander à ce
qu'une règle prédite par l'algorithme génétique ait une précision supérieure à sa fréquence relative
d'apparition dans l'ensemble de données sur lequel on travaille.
Deuxième cas :
suppossons maintenant que la fréquence relative de la valeur de l'attribut du but prédit par cette
règle soit inférieure à 0.5. Il est toujours logique de demander à ce que la précision de la règle
prédite par l'algorithme génétique soit supérieure à sa fréquence relative d'apparition dans
l'ensemble de donnés qu'on étudie, mais maintenant cette condition est beaucoup plus facile à
satisfaire. Par exemple si la fréquence relative vaut 0.2 et que la précision de la règle produite par
l'algorithme génétique vaut 0.3 alors la condition (précision > fréquence relative) serait satisfaite,
mais la règle resterait quand même une mauvaise règle car ayant une précision faible. C'est pour
cela qu'on force la précision de la règle devant être prédite à être supérieure à 0.5, pour imposer que
les règles prédiction découvertes par l'algorithme génétique aiant toujours une précision acceptable,
raisonnable. La condition Acc > max(0.5, FreqRel) nous permet donc d'imposer ces deux
contraintes en une formule simple et concise.
Résultats :
Les 3 chercheurs ont effectué des tests de leur algorithme génétique sur une base de données de
5690 enregistrements. Chaque enregistrement contenait des attributs décrivant un chercheur et sa
production scientifique. De cette base de données ils ont dégagés 24 attributs et toutes les
enregistrements de la base de données ne contenant pas une valeur pour chacun de ces 24 attributs
ont été éliminés.
Parmi ces 24 attributs, 6 ont été utilisés comme des attributs dont on devait prédire la valeur à l'aide
d'une règle de prédiction que l'algorithme génétique devait se charger de découvrir, et les 18 autres
ont été utilisés comme des attributs servant à déduire les valeurs des 6 autres.
Parmi les 18 attributs servant à prédire les valeurs des 6 autres, 8 étaient catégoriel et donc stricts :
• la nationalité du chercheur,
• son continent d'origine,
• son sexe,
• l'état dans lequel il/elle vit,
• la ville dans laquelle il/elle vit,
• son niveau d'anglais écrit,
• si il/elle a déjà été à la tête d'une équipe de recherche,
• son domaine de recherche.
Les 10 autres étaient continus et ont donc été flouttés en 2 termes linguistiques {low, high} ou en 3
termes linguistiques {low, medium, high}, grâce aux informations données par l'utilisateur
(fonctions d'appartenance); voici la liste de ces 10 attibuts continus :
• le niveau d'instruction,
• le nombre d'années depuis le dernier diplôme obtenu,
• l'âge,
• le nombre de projets techniques menés à bien,
• le nombre de cours donnés,
• le nombre de thèses supervisées,
• le nombre de masters supervisés,
• le nombre d'essais de recherche supervisés (à un niveau diplômant),
• le nombre de projets de fin de premier cycle supervisés,
• le nombre d'étudiants de premier cycle encadrés avec un projet de recherche.
Les 6 attributs de but dont on doit prédire les valeurs pour un chercheur donné en se basant sur les
informations dont on dispose dans la base de données, notés G1 , ... , G6 ,sont les suivants :
• G1 est le nombre d'articles publiés dans des journaux nationaux, il peut prendre trois valeurs
floues différentes : low, medium, ou high.
• G2 est le nombre d'articles publiés dans des journaux internationaux, il peut prendre trois
valeurs floues différentes : low, medium, ou high.
• G3 est le nombre de chapitres écrits dans des livres édités au niveau national, il peut prendre
trois valeurs floues différentes : low, medium, ou high.
• G4 est le nombre de chapitres écrits dans des livres édités à un niveau international, il peut
prendre 2 valeurs floues différentes : low ou hogh,
• G5 est le nombre de livres écrits qui sont édités au niveau national, il peut prendre 2 valeurs
floues différentes : low ou high.
• G6 est le nombre de livres écrits qui sont édités à un niveau international, il peut prendre 2
valeurs floues : low ou high.
Tous les résultats obtenus ont été comparés avec ceux obtenus par un algorithme de construction
d'arbres de décision très connu du data-mining, mais qui n'est pas un algorithme génétique,
l'algorithme J4.8, voivi les résultats qu'ils ont obtenus :
Figure 24 : Taux de précison des prédictions réalisées par l'algorithme génétique et l'algorithme J4.8
La première colonne identifie l'attribut de but prédit par la règle de prédiction découverte, la
deuxième identifie la valeur prédite pour cet attribut, la troisième donne la valeur de la fréquence
relative de cet attribut de but dans la base de données qu'on étudie, enfin la quatrième et la
cinquième colonne donne le taux de précision de la prédiction effectuée respectivement par
l'algorithme J4.8 et par l'algorithme génétique.On voit que sur ce point là les résultats fournit par les
2 algorithmes se valent.
Figure 25: Mesure de l'intérêt des règles découvertes par l'algorithme J4.8 et de celles
découvertes par l'algorithme génétique.
La première colonne identifie l'attribut de but prédit par la règle de prédiction découverte, la
seconde et la troisième donne le degré d'intérêt (surprise et contradiction des impressions générales,
des connaissances initiales de l'utilisateur) des règles découvertes respectivement par l'algorithme
génétique J4.8 et par l'algorithme génétique.
Sur ce point la supériorité de l'algorithme génétique sur l'algorithme J4.8 apparait nettement.
Au travers de ces résultats les chercheurs ont observés que plus une règle est simple (c'est-à-dire
qu'elle a un petit nombre de conditions dans son antécédent), plus elle est intéressante pour
l'utilisateur. Les chercheurs ont alors comparé l'intérêt d'une règle en fonction de son nombre du
nombre de conditions qu'elle contient dans son antécédent et là l'avantage de l'algorithme génétique
sur l'algorithme J4.8 est vraiment flagrant.
Figure 26: Analyse de la simplicité d'une règle découverte par l'algorithme J4.8 en fonction du nombre de
conditions qu'elle contient dans son antécédent.
Figure 27: Analyse de la simplicité d'une règle découverte par l'algorithme génétique en fonction du
nombre de conditions qu'elle contient dans son antécédent.
En conclusion, au niveau de la précision des règles de prédictions découvertes, les deux
algorithmes se valent, mais en ce qui concerne l'intérêt pour l'utilisateur de ces règles, l'algorithme
génétique présente un intérêt flagrant sur l'algorithme J4.8, et par la même son choix semble
s'imposer comme une évidence dans le cadre d'un data-mining guidé par l'utilisateur comme par
exemple celui effectué par des sites de vente en ligne comme Amazon. En effet, sur ce site, les
goûts, les impressions générales de l'utilisateur, de l'acheteur, sont déterminés en se basant sur les
articles qu'il achète et sur les articles dont il consulte la page. Le site tente alors de proposer à
l'acheteur des articles pouvant l'intéresser car en rapport avec ses goûts qu'on a pu observer jusque
là, et même lui proposer des articles par lesquels il n'aurait jamais cru pouvoir être intéressé mais
qu'il va finalement apprécier et se décider à acheter !
Conclusion
On sait que les applications des algorithmes génétiques sont multiples : optimisation de fonctions
numériques difficiles , traitement d’image , optimisation d’emplois du temps, contrôle de systèmes
industriels [Beasley, 1993a], cryptographie, apprentissage des réseaux de neurones [Renders, 1995],
etc.
Nos exemples d'application nous ont permis de nous rendre compte que le codage des données pour
modéliser un probléme est comlexe. D'autre part, nous nous sommes aussi aperçus des difficultés
pour choisir pertinemment de bons paramètre pour les divers opérateurs ( mutation , croisement ,
séléction , remplacement ). Des choix par rapport aux opérateurs eux mêmes sont aussi à gérer,
sachant que certains sont plus appropriés au problème et qu'il permettent d'optimiser.
Les algorithmes génétiques seuls ne sont pas très efficaces dans la résolution d'un problème. Ils
apportent cependant assez rapidement une solution acceptable. Néanmoins, il est possible de
l'améliorer assez efficacement en le combinant avec un algorithme déterministe.