Commmunication TCP en Java

<<L'observation scientifique est toujours une observation polémique. >>
Gaston Bachelard



Ceci est un tutoriel permettant de concevoir simplement une communication TCP en Java.
Le code est bien commenté et bien indenté ; j'espère qu'il sera compris avec facilité.

Pour en savoir plus sur le protocole TCP, vous pouvez vous référer à l'article TCP/IP.

Le programme serveur se présente ainsi:

import java.io.*;
public class ServeurTCP {
    public static void main(String[] args)throws Exception {
       
        //S'attacher à un port
        ServerSocket ss = new ServerSocket(7500);
        //Attendre les connexion des clients
        System.out.print("Attente connexion...");
       
        /*
         * NB : La methode accept() bloque le programme jusqu'à ce
         * qu'une connexion soit établie
         */
        Socket s = ss.accept();//Bloquant
       
        //Création du flux binaire de lecture
        InputStream is = s.getInputStream();
        //Création du flux binaire d'écriture
        OutputStream os = s.getOutputStream();
       
        /*
         * NB: La nature des filtres dépend de la nature de
         *        l'information initiale 
         */
        //Filtre de lecture de texte
        BufferedReader tmp = new BufferedReader(new InputStreamReader(is));
        //Filtre d'ecriture de texte
        PrintWriter pw = new PrintWriter(os,true);       



        
        //Lecture de la chaine envoyée par le client
        String recep = tmp.readLine();

        //Je me demande bien ce que fait cette ligne ici
        recep = new StringBuffer(recep).reverse().toString();
       
        //Renvoi au client
        pw.println(recep);    
    }
}

Et de son côté, le client TCP (beaucoup plus simple) s'écrit juste en ces quelques lignes:
NB: Je crois qu'il n'y a rien à commenter sur le client !

import java.net.*;
import java.io.*;
public class ClientTCP {
    public static void main(String[] args)throws Exception {
        //Sattacher à un port     (ici peut être?)
        Socket s = new Socket("localhost", 7500);
       
        InputStream is =  s.getInputStream();
        OutputStream os=s.getOutputStream();
       
        BufferedReader tmp = new BufferedReader(new InputStreamReader(is));
       
        PrintWriter pw = new PrintWriter(os,true);
       
        pw.println("Hello World !");
        System.out.print("Reçu du serveur: "+tmp.readLine());
    }
}

Voilà, c'est rien que ça !
Vous avez réussi à implémenter une communication fiable entre un client et un serveur.
C'est fou ce qu'on nous fatigue pour des choses aussi banales ! ;-)
N'hésitez pas à poster vos commentaires et éventuellement de contribuer à ce blog.
Sinon "enjoyez !".

TCP/IP et OSI

A venir ...

Le cloud computing expliqué

<< Etre expert c'est tout l'art s'apprendre une science à des vétérans tout en étant un débutant >> Jdan Noritiov

.

.

.

Depuis quelques années, on entend souvent parler de cloud computing sans qu'on sache vraiment de quoi il s'agit.

Voici quelques explications qui, je l'espère, vous permettront de lever certaines zones d'ombre sur le cloud computing..

Pour commencer, Cloud = nuage

Et donc le «cloud computing »  serait l’ «informatique des nuages » ou plutôt l’«informatique dans nuages ».

 Voici donc à quoi ressemble le cloud computing:

 

 

Voilà c’est tout – vous avez tout compris !!! :-)

…

Compris ??? … Pas vraiment !

En fait cette terminologie (ou cette technologie, concept… tout ce que vous voudrez) va plus loin.

Le cloud computing se définirait comme la délocalisation de son infrastructure informatique sur des serveurs distants.

Aaaaah, là ça devient intéressant !

Mais oui, on fait tous du cloud sans vraiment le savoir. Que croyez-vous faire lorsque vous vous connectez à votre webmail (hotmail, yahoo, gmail…) ? … … « clouder »  bien sûr.

Evidemment on ne peut parler de cloud sans faire allusion au monde de l’entreprise puisque c’est là qu’on s’aperçoit de son véritable impact … sur les dépenses bien sûr. Ah sacrées entreprises !!!

 Imaginez une entreprise qui ne se soucierait plus de son infrastructure informatique. Aucun souci de gestion, de maintenance, de stockage, d’espace … et donc une forte réduction de la CAPEX. 

Plaçons nous maintenant du côté des fournisseurs de service cloud (genre SSII ou autres). Oui, on parle de service maintenant ! Et ces services peuvent être fournis à la même manière qu’EDF nous fournit l’électricité. Ces entreprises possèdent un grand nombre de serveurs et peuvent nous (entreprises et/ou particuliers) procurer un espace selon nos besoins. D’autres aussi nous permettent d’accéder à des programmes via le réseau…

Ok ! Mais qu'est-ce-que j'y gagne dans tout ça ?

Euh doucement ! Les entreprises ou moi en tant que particulier ?

Oui parce que tout ceci n’a pas un très grand impact chez un particulier. Allons plutôt voir ce qui se passe chez les entreprises clientes.

-  Comme cité plus haut, le principal avantage est lié à la réduction de la CAPEX et de l’OPEX.

-  Vient ensuite ce qu’on appelle la « servicisation » des ressources informatiques car les entreprises n’auront plus qu’à faire appel aux services informatiques d’autres entreprises.

-  En outre, on peut aussi noter que les ressources (programmes, fichiers…) ne sont plus sur un terminal local. On eut donc y accéder via tut terminal connecté au réseau internet. Ceci permet d’assurer la tolérance aux pannes.

-  La flexibilité de l’espace de stockage. Les entreprises se verront attribuer un espace sur mesure. On parle alors de stockage à la demande.

Mais LA question d'argent, de money, de diñero est bien le principal soucis. 
Aaaah le capitalisme !!!
On peut se faire une idée des économies que peuvent réaliser une entreprise via le schéma suivant. Entre nous, je crois que ça vaut vraiment le coup.

[source: www.wikipedia.org]

Mais comment utiliser le cloud ?

Nous y voilà enfin !

On note trois modes d’utilisation pour le cloud computing:

-  Infrastructure as a Service (IaaS) :

Dans un tel mode, seules les ressources sont décentralisées. On parle alors de virtualisation des ressources. Ce model demeure le plus répandu. Le fournisseur  s’assure de la partie stockage, de la maintenance mais aussi que les ressources soient prêtes à êtres utilisées (via des machines virtuelles). Le client pour sa part, se charge de l’administration des données, de la mise en marche/arrêt des services…

En guise d’exemple, on a AmazonEC2, Orange Open Cloud…

-   Platfrom as a Service (PaaS):

Ce mode a pour but objectif la mise en place d’environnements de développement spécifiques. Très utile pour les travaux de développement. Le fournisseur met en place des environnements afin que les clients puissent y accéder pour développer des applications, effectuer des tests… Le fournisseur ne se contente plus seulement d’offrir des espaces de stockage mais offre en même temps une plateforme logicielle (middleware) afin de faciliter les travaux des informaticiens.

On peut citer Google Apps, Microsoft Azure…

-   Software as a Service (SaaS):

Dans le mode SaaS, l’utilisateur ne se soucie ni des ressources matérielles ni de l’infrastructure logicielle. En effet, le client n’a plus besoin d’acheter les logiciels (qui coûtent parfois très chers), il les loue.   Ce mode est celui qui génère le plus de revenus. Normal, avec les start-up qui naissent tous les jours. L’avantage pour les clients est qu’ils n’ont plus à se soucier des taches d’installation souvent fastidieuses de même que les mises à jour ; tout relève du domaine du fournisseur.

Exemple : Microsoft Exchange, Sharepoint

Voici un petit récapitulatif des différents modes présentés ci-dessus.

Mode	Utilisateur direct	Visibilité
SaaS	End user	+
PaaS	Développeurs	++
Iaas	Architecte réseau	+++

Autre chose : vous entendrez souvent parler de cloud privé, cloud public et de cloud hybride.

Mais comme ils sont compliqués ! Heureusement que je suis là   :-)

En fait on parle de cloud privé lorsque les ressources matérielles utilisées font partie du patrimoine de l’entreprise cliente ; de cloud publique lorsqu’elles (les ressources) ne font pas partie de leur patrimoine et enfin de cloud hybride lorsqu’une partie des ressources appartient à l’entreprise et une autre partie ne lui appartient pas.

C’est aussi simple que ça !

Mais qu’en est-il de la sécurité des données ?

Et voilà, c’est le point critique du cloud computing. Mais avant, je vous montre un excellent travail réalisé par le club de la sécurité de l’informationfrançais :

En effet, on peut se poser diverse questions du genre :

Où sont stockées mes données ?

Qui aura accès à mes données ?

Qu’arrivera t’il si nous arrêtons notre contrat ?

Mes données sont stockées pendant combien de temps ?

Et bien d’autres…

Avec les différentes lois sur la protection de la vie privée (dépendant de la zone géographique) un vrai problème de sécurité se pose.

Et bien la seule réponse qui tient la route est la suivante : Tout dépend de vos besoins en sécurité, du type de cloud vous souhaitez avoir…  C’est ce qu’on appelle une analyse de risques.

En tout état de causes, la sécurité est partagée entre le fournisseur et le client (tout dépend de leur niveau de contrôle – cf. figure ci-dessus) bien évidemment en mettant en place des mécanismes de contrôle d’accès et de chiffrement des données.

La migration ou le changement de cloud provider s’effectue grâce à un certain nombre d’APIs disponibles sur le marché. Cependant, il est conseillé d’utiliser des APIs standards telles que CDMI (Cloud Data Management Interface) ou encore OVMF (Open Virtual Machine Format) qui permettent l’interopérabilité entre les différents fournisseurs cloud.

Et voilà !
J'espère maintenant que vous aurez plus d'arguments quand vous entendrez parler de cloud computing.
N'hésitez pas à poser vos questions, critiquer, suggérer...

Références Bibliographiques

http://www.cisco.com

http://www.nouslesgeeks.fr

http://www.paroles-experts.fr

http://uottawa.ca

http://www.cloudconsulting.fr

http://www.linformaticien.com

http://www.wygwam.com

http://www.clusif.asso.fr

http://rse-pro.com

http://www.slideshare.net

http://www.enisa.europa.eu/media/press-releases/prs-in-french/20092011CCFR.pdf

...

IPv4 vs IPv6

Nota: Brève présentation des deux principaux protocoles internet. 

<< On ne peut pas faire une théorie scientifique d'un individu, puisque chacun est unique, mais on peut faire une théorie scientifique des conditions universelles d'existence des individus. >> Alain Prochiantz

.

.

.

A)    INTRODUCTION

Pour connecter plusieurs réseaux entre eux, l’IETF (Internet Engineering Task Force) à mis en place un type de lien appelé route. Il s’agit d’un lien virtuel qui raccorde de bout en bout deux entités communicantes. La couche Internet du modèle TCP/IP définit le mode d’acheminement des paquets (ou datagrammes) entre hôte source et hôte destinataire (à travers les différentes routes). Le protocole utilisé à ce niveau est IP (Internet Protocol). La couche IP effectue une transmission des paquets en mode non connecté. Elle effectue sans garantie de bonne fin la transmission de bout en bout des paquets via leurs adresses IPs. Pour ce faire, elle utilise une entête qui contient un certain nombre d’informations telles que l’adresse de l’émetteur, l’adresse du destinataire, la taille des paquets et une indication sur la qualité de service. Le protocole IP existe maintenant sous deux versions: la version 4 (IPv4) et la version 6 (IPv6).

B)    PRÉSENTATION IPv4

La version 4 du protocole internet, qui existe depuis l’origine du réseau Internet est encore largement utilisée (elle est en fait la plus utilisée). En effet, c’est la première version d’IP à avoir été largement déployée. Elle est décrite dans la RFC 791 de septembre 1981.

Le protocole IPv4 utilise une adresse IP sur 4 octets (32bits) ; ce qui limite le nombre d’adresses possibles à 2³²  donc 4.294.967.296 adresses IPv4 possibles.

Il est réparti en trois classes principales:

-          Classe A : Adresses de 0.0.0.0/8 à 127.0.0.0/8

-          Classe B : Adresses de 128.0.0.0/6 à 196.255.0.0/16

-          Classe C : Adresses de 192.0.0.0/16 à 255.255.255.0/16

Le protocole IPv4, bien que largement utilisé, n’intègre aucun mécanisme permettant d’offrir un service de sécurité. En effet, il ne permet ni l’authentification des hôtes, ni la confidentialité des données et des adresses IPs.

Il offre un service non fiable et fonctionne en mode best effort. IPv4 ne garantie pas :

-          La reprise sur erreur ;

-          La livraison au bon destinataire ;

-          Le séquencement correct des données à leur arrivée ;

-          La confidentialité et l’intégrité des données ;

-          L’authentification des communicants ;

-          Un nombre assez important d’adresses IPs : malgré les 2³²  adresses possibles et malgré les techniques de sous adressages, on assiste à un pénurie d’adresses IPv4 ;

-          La qualité de service : car dans le mode non connecté, les données sont envoyées sans s’assurer au préalable de la disponibilité du récepteur.

La structure d’un entête IPv4 est montrée dans la figure ci-dessous :

 Entête IPv4

 

Les différents champs sont les suivants:

Version : il s'agit de la version du protocole utilisé. Ici, la version 4 ;

Header Length : nombre d'octets du header (typiquement 20);

Type Of Service : priorité du paquet (obsolète);

Total Length: longueur totale du paquet, header compris;

Identification, Flags, Fragment Offset: permet de gérer la fragmentation et le réassemblage des paquets;

Time To Live : temps de vie d'un paquet (décrémenté de 1 à chaque traitement, perdu s'il vaut 0);

Protocol: 1 pour ICMP, 6 pour TCP, 17 pour UDP;

Header Checksum: correction d'erreurs;

Options: pour le routage, etc.

Exemple d’adresse IPv4 : 192.168.0.1

C)    PRÉSENTATION IPv6 ou IPnext generation (IPng)

La sécurisation des infrastructures de communication Internet a été clairement établie en 1994 (Report if IAB Workshop on Security in the Internet Achitecture. 8 - 10 Feb 1994) par l’IAB (Internet Activity Board). Ainsi, le nouveau protocole IPv6 a été crée et ses spécifications ont été finalisées dans la RFC 2460 en décembre 1998.

Avec cette innovation de taille et des adresses codées sur 16 octets (128 bits), on dispose ainsi d'environ 2¹²⁸ soit 3,4×10³⁸adresses IPs utilisables; de quoi doter d'adresses IPs les personnes, les oiseaux...

L’enjeu est de taille puisque les deux objectifs majeurs sont :

-          Régler le problème d’espace d’adressage ;

-          Anticiper les besoins futurs de la communication avec les applications multimédias, la mobilité des postes, etc...

Les principales évolutions de IPv6 sont notamment :

-          Un adressage étendu et hiérarchisé ;

-          Des adresses codées sur 16 octets ;

-          L’allocation dynamique de bande passante pour le support d’applications multimédia ;

-          La création de réseaux IPs virtuels ;

-          Le support de procédures d’authentification et de chiffrement ;

-          En-têtes de paquets simplifiés afin de faciliter et accélérer le routage.

Le support des services de sécurité est obligatoire dans IPv6 mais optionnel dans IPv4 et la migration de l’ensemble des infrastructures IPv4 vers IPv6 soulève un problème d’ordre financier et technologique lié à son déploiement massif.

L’adoption de IPv6 impose notamment :

-          la modification du schéma d’adressage et de la gestion des adresses ;

-          le support des versions 4 et 6 pendant la période de transition ;

-          la synchronisation à grande échelle de la migration des versions.

Pour ces raisons, cette version d’IP n’est que faiblement utilisée malgré les menaces de la version 4. Seules des infrastructures privées intègrent IPv6 en mode natif.

La structure d’un en-tête IPv6 est donnée dans le schéma ci-dessous :

 Entête IPv6

 

Les différents champs de l’architecture IPv6 sont :

Version : Ici, il s’agit de la version N°6 ;

Trafic class : Il définit le niveau de priorité du paquet IPv6;

Flow label : Ce champ peut être utilisé par une source pour étiqueter une séquence de paquets ;

Payload length: Il indique le nombre d’octets de données qui suivent l’entête IPv6 (NB : Il est à noter que les options de l’entête IPv6 sont considérées comme de la donnée et font donc partie de ce calcul) ;

Next header: Il identifie le type de données ou de l’option qui se trouve derrière l’entête IPv6 ;

Hop limit: Décrémenté de 1 à chaque fois que le paquet traverse un nœud, il limite donc le nombre maximum de sauts pour un paquet;

Exemple d’adresse IPv6 : 2001:0db8:0000:85a3:0000:0000:ac1f:8001

D)    IPv4 vs IPv6

Du fait de l’avancée timide d’IPv6 et des problèmes de migration complète vers ce protocole, on assiste de plus en plus à une cohabitation entre les  deux versions d’IP au sein du même réseau afin de faciliter la transition. Car maintenir la compatibilité avec IPv4 tout en déployant IPv6 facilitera la migration vers ce dernier. Il existe différentes techniques :

-          Technique Dual-Stack : Les deux versions coexistent dans le même nœud ;

-          Technique de Tunnel : Pour éviter les dépendances dans le déploiement ;

-          Technique de Translation : Permettre des hôtes IPv6 à communiquer avec des hôtes IPv4 ;

En général on utilise une combinaison de ces trois techniques.

a)      La technique Dual-Stack (rfc 3338)

Comme son nom l’indique, cette technologie permet aux équipements réseau de traiter à la fois les piles de protocoles IPv4 et IPv6 en attendant une migration complète vers IPv6. Il y a donc cohabitation des deux versions au sein d’un même équipement.

Il existe une version d’IOS de routeurs CISCO qui ont intégré cette technologie

Cette technique consiste un arrangement à long terme pour le passage vers IPv6 mais consomme des ressources mémoires aux routeurs. Cependant le « Dual-Stack« reste une alternative efficace pour les entreprises ayant opté pour une migration vers IPv6.

           

b)     La technique de tunnel (rfc 2893)

Il s’agit d’une technologie dans laquelle les paquets IPv6 sont encapsulés dans des paquets IPv4 d’où l’appellation 6to4.

 

Mode tunnel

Cette technologie est mieux adaptée pour les extranets et VPN mais nécessite l’utilisation de routeurs spécifiques 6to4.

c)      La technique de translation

Elle est basée sur l’utilisation de translateurs. Il s’agit d’équipements capables d’assurer la translation IPv4 vers IPv6 et inversement. Ils sont censés éliminer les besoins de Dual-Stack mais sont utilisés en dernier recours car cette technologie interfère avec le end-to-end.

 Mode translation

E)    CONCLUSION

La technologie IP version 4 a montré ses limites tant sur le plan sécuritaire que sur les besoins actuels des internautes. Une alternative étant l’adoption d’une nouvelle version d’IP : IPv6 (Internet Protocol version 6).

Cette version apporte tout un tas de solutions quant aux failles de la version antérieure : adressage illimité (ou presque), mécanismes de chiffrement, d’authentification, qualité de service etc…

La tendance actuelle est de migrer complétement vers cette nouvelle version afin de profiter au maximum de ses apports tant attendus. Cependant du fait de l’explosion inattendue de la version 4, une certaine lenteur est observée et des méthodes permettant une cohabitation entre les deux versions ont été mises en place afin de faciliter la transition et éviter (sinon limiter) les dégâts qu’elle pourrait causer.

Références Bibliographiques

http://fr.wikipedia.org

http://tools.ietf.org

http://www.ietf.org

http://www.2000trainers.com

http://www.frameip.com

http://www.afrinic.net

Sécurité informatique et réseaux, Solange Ghernaouti-Hélie, Sciences Sup, Dunod

Architecture et technologie des ordinateurs, Cours et exercices corrigés, Paolo Zanella, Yves Ligier, Sciences Sup, Dunod

...

Classification topologique non supervisée pour des données catégorielles

Nota: Le présent document a été réalisé dans le cadre d'un projet de recherche sur le domaine du Data Mining. Il est certes loin d'être exhaustif mais peut constituer un bon outil de documentation pour quelques uns.

                                                                                              << On ne finit jamais de découvrir. >>

Mots clés

Clustering, Classification, Data mining, Self-Organised-Map, BeSOM, E-M

Notations

X = {X1, ……,Xn} l’ensemble des données (ou individus) ;

Y = {Y1, ……,Yp} l’ensemble des variables ;

C = {C1, ……,Ck} l’ensemble des classes et G = {G1, ……, Gk} leurs centroïdes ;

P = {P1, ……, Pp} les poids des variables

Liste des Sigles et Abréviations

ACM               Analyse des Correspondances Multiples

ACP                Analyse en Composantes principales

BATM             Bernoulli Aspect Topological Model

CAH               Classification Ascendante Hiérarchique

CDH               Classification Descendante Hiérarchique

GTM               Generative Topographic Map

SOM               Self-Organised-Map

STVQ             Soft TopographicVectorQuantization

I.                   INTRODUCTION

            Notre travail de recherche s'articule autour de l'exploration et l'extraction de connaissances à partir de données catégorielles. Nous avons cherché à développer un modèle de représentation qui résume d'une manière globale l'ensemble des données, en identifiant des proximités ou des différences entre des ensembles de données, non étiquetées à priori. Cette recherche comporte deux aspects : un aspect fondamental qui consiste à développer une  technique pour la classification et la visualisation de données catégorielles, et un aspect applicatif qui consiste à valider notre approche sur différents types de données.

L’objectif du travail effectué est d’implémenter un algorithme de clustering sur des données catégorielles et de réaliser des tests. Il relève du domaine du data mining qui peut être défini comme étant l’extraction ou la recherche de connaissances à partir de volumes importants de données. Le data mining se base sur un ensemble de méthodes automatiques ou semi-automatiques pour constituer un outil d’aide à la décision.

Pour réaliser des travaux de data mining, un ensemble de techniques se trouvant à la croisée de la statistique, de l’analyse des données, de l’intelligence artificielle et des bases de données nous est proposé mais dépendant fortement de la nature des données dont on dispose et du type d’étude à entreprendre. Il existe deux grandes familles de techniques de data mining :

- Les techniques descriptives : visent à mettre en évidence des informations présentes mais cachées par le volume des données.

- Les techniques prédictives : visent à extrapoler de nouvelles informations à partir des informations présentes.

Notre travail vise plutôt à traiter des données binaires à partir de techniques descriptives. Pour ce faire, on utilisera un modèle de carte topologique basé sur le modèle de mélange. Ces cartes utilisent toutes un algorithme d’auto-organisation SOM (Self-Organised-Map). Cependant, pour mieux appréhender le thème, une brève présentation des méthodes les plus générales de la classification non-supervisée sera effectuée.

Les techniques du data mining servent principalement dans deux secteurs d’activité : la recherche et les entreprises (les banques, les télécommunications, les E-commerces, etc.)

II.   ÉTAT DE L’ART

            Ce travail représente une approche de classification appliquée aux données binaires. Dans notre contexte où il est question d’étudier de grandes quantités de données et on souhaite projeter les données dans un espace de faible dimension en conservant la notion de voisinage, il serait intéressant d’utiliser des méthodes auto-organisatrices comme par exemple les cartes SOM. Les cartes topologiques utilisent un algorithme d’auto-organisation qui permet de classifier et de projeter les groupes obtenus de façon non linéaire sur une carte tout en respectant la topologie initiale. Des modèles de cartes topologiques pour des données binaires ont été proposés suite à différents travaux de recherche tels que [1] et [2].

Cependant, différentes approches reposant sur le formalisme probabiliste ont été proposées. On peut citer comme référence le GTM même si au départ son champ d’application reste limité à des données continues. Nous pouvons citer [3] qui additionne la log-vraisemblance des données et un terme de pénalité qui applique l’auto-organisation. Il y a aussi le STVQ qui mesure une divergence entre les données élémentaires et les référents. Dans le document [4] les auteurs présentent le modèle BATM qui permet d’accélérer la convergence de l’estimation par une initialisation originale des probabilités en jeu.

Toutes ces études ont permis de donner des méthodes plus ou moins satisfaisantes selon les cas étudiés. Elles sont toutes applicables sur des données binaires et pour certaines uniquement sur ce type de données ; ce qui cause une certaine limite vue que la plupart des données recueillies intègrent à la fois des informations de type quantitative et catégorielle.

III. CLASSIFICATION 

            La classification peut être définie comme étant le regroupement en groupes similaires d’un ensemble de données. Il s’agit en d’autres termes de regrouper les données ayant le plus de similarité de tel sorte que les individus similaires appartiennent à une même classe et sont différents des individus d’autres classes.

Il existe deux grandes familles de méthodes de classification :

-  Les méthodes supervisées ;

-  Les méthodes non supervisées.

            1.          Classification supervisée

            La classification supervisée porte sur une série de méthodes prédictives de classification des données. On parle de prédiction lorsqu’on veut estimer la classe à laquelle appartient une donnée à partir d’un ensemble de données déjà classées. On dispose pour ce faire d’une base de données à priori classée appelée base d’apprentissage qui nous servira de référent et d’un ensemble de données qu’on appellera base de test (qui contient les données à prédire). La problématique sera donc de prédire, pour chaque donnée de la base de test, la classe à laquelle elle appartiendra dans la base d’apprentissage.

 

Elle peut être illustrée comme suit :

 

Il existe plusieurs méthodes proposées, permettant d’effectuer la classification supervisée. On peut ainsi citer quelques unes :

-          Les réseaux de neurones : Ils sont constitués d’un ensemble de «neurones formels». Ce modèle est tiré des neurones biologiques.

 

Fig1: Réseaux de neurones

A chaque donnée  en entrée, on associe un poids  . La sortie y sera la valeur à estimer et dépendra fortement de la fonction d’activation  f du neurone (souvent une sigmoïde) ;

-          Les arbres de décision : Dans ce cas ci, on cherche à homogénéiser les différentes classes obtenues. Notre ensemble de données est séparé de façon récursive suivant des variables déterminées (par exemple on décide de choisir comme variable de séparation la variable la plus fréquente ...).

Arbre de décision [Quinlan 1993]

-     Le KNN (K-Nearest-Neighbour) : Cette méthode suppose qu’une donnée est de  la même classe que celles qui lui sont proches. Autrement dit, la probabilité que les K données les plus proches (du point de vue de leur distance) soient dans une même classe est maximale. Si les K données sont dans des classes différentes, notre donnée sera attribuée à la classe la plus représentée.

          1.               Classification non supervisée

La classification non-supervisée comporte sur un ensemble de méthodes destinées à répartir des données dans une structure plus ou moins organisée, de regrouper les données en sous-groupes de sorte à ce que les données les plus similaires soient associées au sein d’un même groupe homogène et les données considérées comme différentes soient associées dans des groupes différents. Lors de la classification non supervisée on cherche à satisfaire deux objectifs simultanément: une grande homogénéité de chaque classe et une bonne séparation des classes.

L’objectif de la classification non-supervisée est de permettre l’extraction de connaissance à partir de ces données.

La méthode de classification non supervisée se distingue de celle supervisée par le fait qu'il n'y a pas de sortie à priori. En effet, dans une classification non supervisée il y a en entrée un ensemble de données collectées ensuite le programme les traite comme des variables aléatoires et construit un modèle de « densités jointes » pour cet ensemble de données.

Il existe plusieurs types de classification non-supervisée, on cite : Clustering hiérarchique, Clustering K-means, Clustering statistique, Clustering stochastique, etc.

Difficultés de la classification non supervisée 

La classification non supervisée  rencontre différentes difficultés dont les plus essentielles selon notre avis sont les suivantes :

a)    Dans une zone de forte densité  il est naturel de reconnaître des observations regroupées comme appartenant à une même classe, en revanche il n’est pas de même dans une zone  de faible densité. La définition de frontières entre les classes peut être hasardeuse.

b)   Dans le cadre de la classification non supervisée le nombre de classes est inconnu à priori. Ainsi, il est difficile de définir le nombre optimal de classes.

c)  Le critère de validation des résultats constitue également une difficulté pour la classification non supervisée.

d)   Pour certains algorithmes la forte dépendance de la phase d’initialisation constitue un véritable désavantage.

           3.          Étude de quelques algorithmes de classification non supervisée

            Il existe plusieurs algorithmes de classification non supervisée donnant tous des résultats plus ou moins satisfaisants selon le type de traitement souhaité. Dans cette section nous présentons quelques uns de ces algorithmes mais qui sont les plus couramment utilisés.

a.     L’approche K-means

            Aussi connu sous l’appellation k-moyennes, il est l’un des outils de classification les plus utilisés dans les applications scientifiques et industrielles. Le principe étant de découper un ensemble d’observations en k classes distinctes. Son étude introduit les notions d’inertie et de barycentre. Pour rappel, le barycentre d’un nuage de points est un point pour lequel l’inertie totale est minimale ; l’inertie d’un système étant la propriété de ce dernier à rester immobile (ou en équilibre).

Plusieurs méthodes de calcul de l’inertie sont utilisées et se basent toutes sur la notion de métrique (ou distance). La métrique la plus utilisée (et sur laquelle on se basera ici) est le carré de la distance euclidienne.

Si le nombre de classes augmente (plus d’une), on est amené à calculer :

-          L’inertie intraclasse : Représente l’inertie calculée pour les individus appartenant à une même classe. Elle est donnée par :

-      L’inertie interclasse : Représente l’inertie calculée entre les différentes classes. Elle est donnée par la formule suivante :

-          L’inertie totale : Représente l’inertie du système. Elle est donnée par la somme des inerties interclasse et intraclasse. Elle peut aussi être calculée par la formule suivante :

 

K-means comporte deux étapes fondamentales : une étape d’initialisation et une étape d’affectation.

Il existe plusieurs versions de k-means parmi lesquelles :

-          Le k-means incrémental : Où les observations sont ajoutées les unes après les autres et le logiciel recalcule les barycentres après chaque ajout.

-          Les nuées dynamiques : Où on n’initialise pas le traitement avec des observations mais avec des ensembles d’observations représentatives.

Malgré sa grande popularité, sa simplicité, sa rapidité, etc. la méthode du k-means présente néanmoins un certain nombre de désavantages. Par exemple:

1.   

                 1.     Le plus probant est la forte dépendance du nombre k de classes car l’utilisateur devra à priori renseigner le nombre de classes désiré ; ce qui fait que k-means soit le plus souvent précédé d’une ACP ou d’une ACM selon le type de données.

2.           2.     Une autre faiblesse de k-means est liée aux formes des classes car pour des classes étalées, cette méthode renvoie des résultats erronés.

b.      La classification hiérarchique

            C’est en effet la technique de classification la plus ancienne et repose sur une métrique de dissimilarité ; c’est-à-dire définir une grandeur qui permet de différencier le différentes données recueillies. Elle se présente sous la forme d’un arbre binaire (appelé dendogramme), permettant de visualiser les classes sous une forme hiérarchisée. L’intérêt d’une telle classification réside dans la partition de l’ensemble des données en classes compactes, bien séparées et donc facilement interprétables. On en distingue deux types :

-          Classification Ascendante Hiérarchique (CAH)

-          Classification Descendante (ou Agglomérative) Hiérarchique (CDH).

. La classification hiérarchique ascendante

            Le principe du CAH est de réaliser une agrégation deux à deux des individus (ou ensemble d’individus) les plus proches selon des critères d’agrégation à définir. Ces critères se basent sur deux aspects : les individus d’une même classe sont les plus semblables possibles ; les classes sont les plus disjointes possibles. La définition d’un tel critère est primordiale dans la mesure où on sera appelé à répondre à la question qui suit :

Comment calculer la métrique de dissimilarité  entre deux classes ?

Trois critères sont généralement utilisés pour réaliser cette agrégation. Soient deux classes A et B :

-          Critère du lien minimum : D_min (A, B) = min{d(x, y) / x Є A , y Є B}

-          Critère du lien maximum : D_max (A, B) = max{d(x, y) / x Є A , y Є B}

 

-          Critère de Ward : 

Le critère de Ward, plus utilisé, montre ses limites dans le cas où les classes sont allongées et donc le critère minimum de vient plus performant.

.  La classification hiérarchique descendante

            Aussi connue sous le nom d’analyse des associations ou classification par divisions, elle réalise comme son nom l’indique une opération inverse de celle du CAH. Le principe étant de considérer d’abord l’ensemble de données comme un seul cluster et réaliser de façon récursive la segmentation des classes de telle sorte que la dissimilarité soit maximale afin d’obtenir un dendogramme optimal.

Bien que ce type de classification fournisse des résultats cohérents, elle est cependant moins utilisée que la précédente du fait de son temps de calcul très lourd. En effet, si on dispose de N données, il faudrait à cette méthode 2^N-1 -1 bipartitions pour n’en choisir qu’une seule (celle qui répond la mieux au critère de scission).

c.     L’approche SOM (Self-Organised Map)

Plus connue sous le nom de carte auto-organisatrice (ou carte auto-adaptative) de Kohonen (du nom de son inventeur Teuvo Kohonen), cette technique de classification est en fait une version non supervisée des réseaux de neurones. Elle cartographie les classes de données d'entrée en réalisant une projection, depuis leur espace multidimensionnel d'origine, dans l'espace interne de sa mémoire qui est bidimensionnelle. L'algorithme construit un ordonnancement topologique des relations implicites qu'il découvre entre les classes de données. Sa représentation interne facilite l'analyse des relations entre classes, par la réduction dimensionnelle qu'elle leur applique, et minimise les effets de mauvaise classification. La structure bidimensionnelle de l'espace de représentation fournit une interface de visualisation conviviale où la similarité entre les classes de données est encodée dans la proximité entre les amas d'unités distribuées sur la carte : des formes reliées dans l'espace des données sont situées proches les unes des autres dans l'espace de la carte. Les principaux paramètres de ce modèle sont: le nombre de neurones, le maillage des unités de la carte, la topologie de la carte, tore ou plane le taux d'apprentissage, le voisinage, et les fonctions qui déterminent sa décroissance dans l'espace et dans le temps, le rayon de propagation, le nombre d'itérations, le nombre de phases d'apprentissage.

L’algorithme SOM peut être défini comme suit :

IV. NOTIONS GÉNÉRALES SUR LES APPROCHES PROBABILISTES

Dans les approches probabilistes, les données sont considérées comme un échantillon extrait indépendamment d'un modèle de mélanges de plusieurs distributions de probabilités. La région autour de la moyenne de chaque distribution constitue un cluster naturel. Chaque observation contient en plus de ses attributs l’étiquette du cluster. Différentes méthodes ont été proposées afin de découvrir le meilleur optimum.

La classification probabiliste a plusieurs caractéristiques importantes :

-                 Elle peut être modifiée dans le but de raccorder les structures complexes ;

-              Le modèle de mélange intermédiaire peut être utilisé pour affecter des cas à n’importe quelle étape du processus itératif ;

-                  La classification probabiliste a pour résultats un système de classes facilement interprétables.

V.   APPROCHE PROBABILISTE PROPOSÉE  POUR DES DONNÉES       BINAIRES

L’algorithme BeSOM utilisé dans ce travail est un algorithme de cartes topographiques dédié aux données catégorielles codées en binaire de façon à ce que chaque cellule de la carte BeSOM soit associée à une fonction de Bernoulli. Les cartes BeSOM sont  de la famille des cartes topographiques probabilistes et sont entre autre des modèles de mélange. Le problème revient donc à estimer les paramètres de ces modèles.

L’algorithme BeSOM est en réalité une application directe de l’algorithme E-M (Estimation-Maximisation) [5]:

Trois variantes de BeSOM sont proposées:

-         -     La première est développée sous l’hypothèse que le paramètre de probabilité dépend uniquement de la cellule ;

-         -     Dans la deuxième, le paramètre dépend de la cellule et d’une variable ;

-         -     Dans la troisième, le paramètre dépend uniquement de la carte.

Notre étude se base essentiellement sur la première variante.

1.                       Validation expérimentale:

   Pour valider l’approche proposée on a utilisé deux jeux de données extraits du répositoire UCI [7].  Le premier, concerne une base de données composée de chiffres manuscrits ("0"-"9") extraits à partir d’une collection de cartes des services hollandais. On a 200 exemples pour chaque caractère, ainsi on a au total 2000 exemples. Chaque exemple est une imagette binaire (pixel “noir“ ou ”blanc”) de dimension 15 x 16. L’ensemble de données forme une matrice binaire de dimension 2000 x 240. Chaque variable qualitative est un pixel à deux valeurs possibles "On=1" and "Off=0". 

Le deuxième jeu de données utilisé, Zoo data, contient l’information sur 101 animaux décrits par 16 variables qualitatives dont 15 variables sont binaires et une est catégorielle avec 6 modalités. Chaque animal est étiqueté de 1 à 7 conformément à sa classe (son espèce).

On a réalisée plusieurs tests sur ces 2 bases de données et les premiers résultats obtenus sont encourageants.

 

VI. CONCLUSIONS ET PERSPECTIVES

Le travail effectué dans ce projet se situe dans le domaine du data mining, plus précisément dans le cadre de l’apprentissage non supervisé. Il s’agit d’un problème autour du clustering des données.  Le clustering peut être défini comme la segmentation des données en groupes d’objets similaires, d’une telle manière que les objets du même groupe sont similaires entre eux et dissimilaires avec les objets des autres groupes. Ici on s’intéresse plutôt au clustering des données binaires. 

Pour réaliser le travail effectué dans le cadre de ce stage on a suivi la démarche suivante : 

Afin de comprendre la problématique on a étudié et analysé plusieurs approches qui existent dans le domaine. On a implémenté sous Matlab un algorithme de classification non supervisée pour des données catégorielles et les premiers résultats obtenus sont encourageants. En outre, les outils statistiques utilisés (les cartes SOM et algorithme EM) sont relativement faciles à implémenter informatiquement. Enfin, l’algorithme  reste utilisable pour de très grands jeux de données (bien que nous ne l’ayons pas fait ici).

Nous voyons au moins deux directions dans lesquelles ce travail pourrait être poursuivi :

         1.  Dans un premier  temps, on pourrait tester la performance de l’algorithme sur  des très grands jeux de données.

        2.  Par la suite, on pourrait utiliser et tester plusieurs critères de validations ainsi que comparer avec d’autres approches similaires  qui existent dans le domaine.

Références bibliographiques

[1]       M. Lebbah. Carte topologique pour données qualitatives : application à la            reconnaissance automatique de la densité du tra_c routier. Thése de doctorat en Informatique,

           Université de Versailles Saint-Quentin en Yvelines, 2003. 

[2]       Mustapha Lebbah, Aymeric Chazottes, Fouad Badran, and Sylvie Thiria. Mixed

            topological map. In ESANN, pages 357_362, 2005. 

[3]       J.J. Verbeek, N. Vlassis, and B.J.A. Kröse. Self-organizing mixture models. 

            Neurocomputing, 2005 

[4]      M. Nadif, J. Priam Cartes auto-organisatrices probabiliste sur données binaires, 2006.

[5]      A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via

           the EM algorithm. Journal of the Royal Statistical Society, B 39 :1–38, 1977.

[6]       C.L. Blake and C.L Merz. UCI repository of machine learning databases. 

           Technical report. 1998.

[7]       N. Rogovschi, Classi cation à base de modèles de mélanges topologiques des 
            données   catégorielles et continues , 2009

[8]       http://perso.rd.francetelecom.fr

[9]       http://www.grappa.univ-lille3.fr

[10]     http://docs.happycoders.org

[11]     http://liris.cnrs.fr

[12]     http://perso.telecom-paristech.fr

[13]     http://www.math.u-psud.fr

[14]     http://www.jybaudot.fr

[15]     http://www.aiaccess.net

           ...