Problème du sac à dos – Algorithme en Python (knapsack problem)

Le problème du sac à dos en algorithmique (et son implémentation python) est intéressant et fait parti du programme de Sciences numériques et informatique de première.

Ce problème illustre les algorithmes gloutons qui énumèrent toutes les possibilités de résolution d’un problème pour trouver la meilleure solution.

Le problème du sac à dos algorithme python est un problème d’optimisation, c’est à dire une fonction que l’on doit maximiser ou minimiser et des contraintes qu’il faut satisfaire.

Le problème du sac à dos – algorithme Python

Pour un sac à dos de capacité maximale de P et N articles chacun avec son propre poids et une valeur définie, jetez les articles à l’intérieur du sac à dos de telle sorte que le contenu final ait la valeur maximale.

Le problème du sac à dos - algorithme Python

Exemple d’énoncé :

  • Capacité maximum du sac à dos : 11 unités
  • Nombre d’objet : 5
  • Valeurs des objets : {10,50,20,30,60}
  • Poids des objets : {1,5,3,2,4}

Quelles est la valeur maximum qu’il est possible de mettre dans le sac à dos en considérant la contrainte de capacité maximum du sac qui est de 11 ?

Algorithme glouton python

Une solution efficace consiste à utiliser un algorithme glouton. L’idée est de calculer le rapport valeur / poids pour chaque objet et de trier l’objet sur la base de ce rapport calculé .

On prends l’objet avec le ratio le plus élevé et on ajoute jusqu’à ce qu’on ne puisse plus en ajouter.

En version fractionnaire il est possible d’ajouter des fractions d’article au sac à dos.

Implémentation du problème du sac à dos Python – version non fractionnaire

Voici une implémentation du problème du sac à dos python en version non fractionnaire, c’est à dire qu’on ne peut pas ajouter de fraction d’un objet dans le sac. Seul des objets entiers peuvent être ajoutés.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 120

Implémentation du problème du sac à dos python – version fractionnaire

En version fractionnaire de l’agorithme du sac à dos python on peut ajouter des fractions d’objet au sac à dos.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
            else: 
                fraction = capacite / poidsCourant 
                compteurValeur += valeurCourante * fraction 
                capacite = int(capacite - (poidsCourant * fraction)) 
                break
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 140.0

Liens internes algorithme python :

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/2021/01/21/algorithme-glouton-python/
http://128mots.com/index.php/2021/01/19/levenshtein-python/
http://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/

Liens externes algorithme python :

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Construire une application décentralisée full-stack pas à pas (Ethereum Blockchain Dapp) en plus de 128 mots – Partie 3

Cet article fait suite aux deux premiers articles sur le sujet :

Les 2 premiers articles permettent de mieux comprendre le concept de blockchain et d’application décentralisée.

Création du projet

On crée un répertoire pour le projet d’application de vote sur des chansons.

mkdir vote-chanson-dapp

Pour accélérer le développement on va utiliser une « truffle box » : https://www.trufflesuite.com/boxes

C’est en quelques sorte un modèle, un canevas d’application qui vous permet de vous focaliser sur la Dapp en ayant une structure déjà créée.

Je vais baser mon explication sur la pet-shop box disponible ici : https://www.trufflesuite.com/tutorials/pet-shop. C’est un des premiers tutos de truffle pour créer une Dapp.

Cette truffle box comprend la structure de base du projet ainsi que le code de l’interface utilisateur.

Utilisez la commande truffle unbox :

truffle unbox pet-shop

Pour rappel l’installation de truffle est possible via la commande :

npm install -g truffle

Si vous ouvrez le dossier vote-chason-dapp avec vscode vous obtenez alors l’arborescence suivante :

Arborescence du projet de l’application Dapp exemple (basée sur pet-shop de truffle)
  • contract : stockage du smart contract de l’application
  • migration : Les migrations permettent de transférer les smarts contracts vers la blockchain Ethereum (en local test ou mainnet). Les migrations permettent également de relier des smart contrats avec d’autres smarts contracts et de les initialiser.
  • node_modules : Le dossier node_modules contient les bibliothèques téléchargées depuis npm.
  • src : Répertoire de l’application front-end (client)
  • test : Stockage des tests pour l’application
  • truffle-config.js : fichier Javascript qui peut exécuter tout code nécessaire pour créer votre configuration.

Création du smart contract

Pour rappel nous développons une application qui permet d’élire la chanson préférée des électeurs.

Nous allons créer dans un premier temps la partie qui permet de créer un vote pour la meilleure chanson basée sur 3 chansons éligibles.

Le contrat écrit en solidity est le suivant :

contract TopChanson {
        struct Chanson {
        uint identifiant;
        string titre;
        uint compteur;
    }
    uint public compteurDeChansons;
    mapping(uint => Chanson) public chansons;

    function ajouterChansonElligible (string memory nomChanson) private {
        compteurDeChansons ++;
        chansons[compteurDeChansons] = Chanson(compteurDeChansons, nomChanson, 0);
    }

    function TopChansons() public {
        ajouterChansonElligible("Au clair de la lune");
        ajouterChansonElligible("Maman les p'tits bateaux");
        ajouterChansonElligible("Ah ! Les crocodiles");
    }

}

A noter l’utilisation de « mapping(uint => Chanson) public chansons; »

A lire : https://solidity.readthedocs.io/en/v0.6.6/types.html#mapping-types

Cette structure de donnée va nous permettre de stocker les titres des chansons éligibles à la façon d’une table de hachage. C’est à dire un tableau qui prend pour clé d’accès dans notre cas un uint qui est l’identifiant de la chanson et permet de récupérer la valeur qui est un type Chanson structuré.

Le type Chanson est structuré, voir la documentation solidity : https://solidity.readthedocs.io/en/v0.6.6/types.html#structs

Ici il y a un cas particulier sur la fonction ajouterChansonElligible, elle prends en argument le nom de la chanson qui est une chaine de caractère STRING. Si on ajoute pas le mot clé « memory » on obtient l’erreur suivante:

TypeError: Data location must be « storage » or « memory » for parameter in function, but none was given.

Pour les paramètres de fonction et les variables de retour, l’emplacement des données doit être explicité pour toutes les variables de type (struct, mapping, string).

La migration du contrat s’effectue via la commande :

truffle migrate --reset

On obtient alors :

Compiling your contracts...
===========================
> Compiling ./contracts/Migrations.sol
> Compiling ./contracts/TopChanson.sol

A suivre …

Construire une application décentralisée full-stack pas à pas (Ethereum Blockchain Dapp) en plus de 128 mots – Partie 2

Cet article fait suite au premier article sur le sujet : http://128mots.com/index.php/2020/03/30/construire-une-application-decentralisee-full-stack-pas-a-pas-ethereum-blockchain-dapp-en-plus-de-128-mots-partie-1/

Exemple d’application décentralisée (Dapp) de vote

L’utilisateur de l’application décentralisée a besoin d’un portefeuille qui contient des Ether. Comme indiqué dans le premier article il est possible de se créer facilement un wallet sur https://metamask.io/.

Dans un premier temps nous utiliserons le réseau ropsten. Ropsten Ethereum, également connu sous le nom de «Ethereum Testnet», est comme son nom l’indique, un réseau de test qui exécute le même protocole qu’Ethereum et est utilisé à des fins de test avant de se déployer sur le réseau principal (Mainnet). https://ropsten.etherscan.io/

L’utilisation va nous permettre de créer et d’utiliser gratuitement notre application avant d’éventuellement la diffuser sur le réseau principal d’Ethereum.

Lorsque l’utilisateur se connecte à notre application et au réseau il envoie son vote et doit payer quelques frais via son portefeuille afin d’écrire sa transaction dans la Blockchain (Appelé « Gas », ce terme se réfère aux frais pour mener à bien une transaction ou exécuter un contrat sur la blockchain Ethereum).

Architecture de l’application Dapp

L’architecture de l’application se compose d’un front-end qui sera en HTML et Javascript. Ce Frontend dialoguera directement avec la blockchain ethereum local que nous installerons.

Architecture de l’application DAPP

Comme indiqué dans le premier article les règles métier et la logique seront codées dans un Smart Contract. Le Smart Contract est rédigé avec le langage de programmation solidity : https://solidity.readthedocs.io

Création du Front-End

Le front-end sera simple il permet d’afficher le résultat du vote pour sa chanson préférée sous forme d’une liste et de choisir dans une liste déroulante la chanson pour laquelle on souhaite voter.

Vérifier l’installation de node

node -v

Si node n’est pas installé vous pouvez vous référer à mon article sur angular : http://128mots.com/index.php/2020/02/27/angular-en-plus-de-128-mots-partie-1/

Installation de Metamask : il s’agit d’installer https://metamask.io/ en tant qu’extension de votre navigateur

Installation du framework truffle : Truffle est un environnement de développement, un cadre de test et un pipeline d’actifs pour Ethereum, visant à vous faciliter la vie en tant que développeur Ethereum. Il fournit des outils qui nous permettent d’écrire des contacts intelligents avec le langage de programmation Solidity.

Il sera également utilisé pour développer le front-end de l’application.

npm install -g truffle

Installation de Ganache :

Ganache est une blockchain personnelle pour le développement Ethereum que vous pouvez utiliser pour déployer des contrats, développer vos applications et exécuter des tests.

https://www.trufflesuite.com/ganache

Cela va vous permettre d’avoir une blockchain locale avec 10 comptes qui sont alimenté avec des faux Ether.

J’ai démarré l’application et j’ai cliqué sur Quick Start

On voit s’afficher les différents comptes de notre blockchain locale.

Construire une application décentralisée full-stack pas à pas (Ethereum Blockchain Dapp) en plus de 128 mots – Partie 1

Cet article a pour objectif d’expliquer les concepts clés de la blockchain, des dapp (decentralized app), des smart contract et de la tokenisation.

Blockchain

Une blockchain est une base de donnée décentralisée, elle est partagée entre plusieurs nœuds qui possède une copie de cette base de donnée.

Block

Une demande d’ajout de donnée dans la base par un utilisateur est une transaction. Les transactions sont regroupées et ajoutées à un block dans la blockchain.

A noter que toutes les données de ce registre partagé qu’est la blockchain, sont sécurisées par hachage cryptographique et validées par un algorithme qui fait consensus entre les utilisateurs du réseau.

Concept de block dans une blockchain

Mineur

Les mineurs sont des utilisateurs du réseau qui mettent, grâce à un programme, les ressources de leur ordinateur pour valider les nouvelles transactions et les enregistrent sur le registre partagé (blockchain).

Exemple de ferme de mineur équipée pour calculer des transactions sur la blockchain (via la résolution de problème mathématique et cryptographique complexe), les mineurs reçoivent une « récompense » pour leur travail.

Blockchain Ethereum

Ethereum est une plate-forme open source qui utilise la technologie blockchain pour éxecuter des applications décentralisées (dapps).

Cette plateforme se base sur la création de Smart Contract, c’est un programme qui contient des données et des fonctions appelées par des applications.

Se basant sur la blockchain il n’y a pas de base de donnée centralisée mais un registre partagé et maintenu en peer to peer par les utilisateurs.

Cette technologie peut être utilisée pour échanger des devises ou pour créer des applications décentralisées qui appellent des smarts contracts et qui stockent leurs données dans des blocs de la blockchain.

Blockchain publique

Dans une blockchain publique il n’y a pas d’autorisation, tout le monde peut rejoindre le réseau de blockchain, ce qui signifie qu’il peut lire, écrire ou participer avec une blockchain publique.

Les Blockchain publiques sont décentralisées, personne n’a de contrôle sur le réseau et elles restent sécurisées car les données ne peuvent pas être modifiées une fois validées sur la chaîne de blocs.

Les plates-formes publiques de blockchain comme Bitcoin, Ethereum, Litecoin sont des plateformes de blockchain sans autorisation, elles s’efforcent d’augmenter et de protéger l’anonymat de l’utilisateur.

Blockchain privée

Dans une blockchain privée il y a des restrictions pour filtrer qui est autorisé à participer au réseau et à quelles transactions.

Les blockchains privées ont tendance à être associées à des outils de gestion des identités ou une architecture modulaire sur laquelle vous pouvez brancher votre propre solution de gestion des identités.

Il peut s’agir d’un fournisseur de services d’adhésion à une solution OAuth qui utilise par exemple Facebook, LinkedIn,…

Token Ethereum

Les tokens ou jetons Ethereum sont des actifs numériques qui sont construits à partir de la blockchain Ethereum. Ce sont des jetons qui attestent que vous possédez une valeur (économique par exemple). Ces jetons sont basés sur l’infrastructure existante d’Ethereum.

Pour stocker, recevoir, envoyer les ether (cryptomonnaie sur la blockchain ethereum) ou les tokens (qui sont des jetons qui sont des actifs numérique), il vous faut a minima un compte. Le plus simple moyen de créer un compte est :

Il est possible de créer son propre token pour créer son application décentralisée qui utilise la blockchain publique ethereum.

Tokenisation des actifs financier

La tokenisation est une méthode qui convertit les droits d’un actif (financier, immobilier …) en jetons numériques (tokens).

Exemple pour un appartement de 400 000 Euros. Le tokeniser consiste à le transformer en 400 000 tokens (le nombre est arbitraire, l’Émission peut être de 4 millions ou 100 jetons).

Les tokens sont émis sur une sorte de plate-forme prenant en charge les contrats intelligents, par exemple sur Ethereum. Le but est que les tokens puissent être librement échangés.

Lorsque vous achetez un token, vous achetez en fait une part de la propriété de l’actif (de l’appartemment de 400 000 euros).

Achetez 200 000 jetons et vous possédez la moitié des actifs. La Blockchain est registre partagé qui est immuable, il garantit qu’une fois que vous achetez des tokens, personne ne peut supprimer votre propriété.

Application décentralisée

Les applications décentralisées sont des applications qui communiquent avec la blockchain. L’interface des applications décentralisées est similaire à n’importe quel site Web ou application mobile.

Le Smart Contract représente la logique centrale de l’application décentralisée.

Illustration of a DApp that uses a blockchain with smart contracts combined with the pillars of Swarm and Whisper.
Source: Ethereum Stack exchange

Smart Contract

Les Smart Contract contiennent toute la logique métier d’une DApp. Ils sont chargés de lire et d’écrire des données dans la blockchain, aussi ils exécutent la logique métier.

Les contacts intelligents sont écrits dans un langage de programmation appelé SOLIDITY https://solidity.readthedocs.io, proche de Javascript.

A lire sur le sujet :

ANGULAR en moins de 128 mots – TypeScript – Angular Partie 8

Cet article fait suite aux sept premiers sur le sujet ANGULAR et porte sur le langage TypeScript :

Templates et interpolation

L’interpolation est l’incorporation d’expressions dans du texte balisé. Par défaut, l’interpolation utilise comme délimiteur les doubles accolades, {{ et }}.

<h3>Client n° : {{ numeroClient }}</h3>

Exemple de directive avec itération :

<li *ngFor="let client of listeClients">{{client.nom}}</li>

Services :

Les services permettent de découpler le composant de l’appel à un service, ils sont ainsi réutilisables.

ng generate service client
import { Injectable } from '@angular/core';

@Injectable({
  providedIn: 'root',
})
export class ClientService {

  constructor() { }

}

La logique est alors découplée du service qui est injectable via l’injection de dépendance.

Injection de dépendance

Exemple d’injection de la dépendance ClientService dans un composant ClientComponent

import { Component, OnInit } from '@angular/core';

import { Hero } from '../hero';
import { HeroService } from '../hero.service';
import { MessageService } from '../message.service';

@Component({
  selector: 'app-heroes',
  templateUrl: './heroes.component.html',
  styleUrls: ['./heroes.component.css']
})
export class ClientComponent implements OnInit {

...

  getClients(): void {
    this.clientService.getClients();
  }
}

Typescript Getter Setter ANGULAR

Cet article fait suite aux six premiers sur le sujet ANGULAR Typescript Getter Setter et porte sur le langage TypeScript :

typescript getter setter

Constructeur :

Le constructeur est la méthode appelée à la création de l’instance d’un objet

class Point {
    x: number;
    y: number;

    constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
    }
    ajouter(point: Point) {
        return new Point(this.x + point.x, this.y + point.y);
    }
}

var p1 = new Point(30, 5);
var p2 = new Point(14, 21);
var p3 = p1.ajouter(p2);

Paramètre optionnel :

Si un paramètre est déclaré optionnel alors tous les paramètres déclarés à sa droite sont optionnels. Exemple du paramètre name dans le constructeur.

class Point {
    x: number;
    y: number;
    name: string;

    constructor(x: number, y: number, name?:string) {
        this.x = x;
        this.y = y;
        this.name = name;
    }
}

Visibilité :

Par défaut la visibilité du paramètre est publique, on peut utiliser des « access modifier » pour la modifier.

class Point {
    private x: number;

Les modificateurs d’accès peuvent être positionnés sur les méthodes, les variables et les propriétés.

class Point {
...
     private ajouter(point: Point) {
        return new Point(this.x + point.x, this.y + point.y);
    }
}
class Point {
...
    constructor(private x: number, private y: number) {
...

L’ajout d’un modificateur d’accès (public / privé / protégé / en lecture seule) à un paramètre constructeur affectera automatiquement ce paramètre à un champ du même nom.

Typescript getter setter :

TypeScript prend en charge les getters / setters comme moyen d’intercepter les accès à un membre d’un objet.

Cela permet d’avoir un contrôle plus fin sur la façon dont un membre est accédé sur chaque objet.

const longueurMaxDuNom = 10;

class Salarie {
    private _nomComplet: string;

    get nomComplet(): string {
        return this._nomComplet;
    }

    set nomComplet(nouveauNom: string) {
        if (nouveauNom && nouveauNom.length > longueurMaxDuNom) {
            throw new Error("Erreur Longueur maxi du nom atteinte, longueur max autorisee = " + longueurMaxDuNom);
        }
        
        this._nomComplet = nouveauNom;
    }
}

let salarie = new Salarie();
salarie.nomComplet = "Toto Hello";
if (employee.nomComplet) {
    console.log(employee.nomComplet);
}

Références à lire :

Typescript getter setter : liens internes

http://128mots.com/index.php/category/graphes/

http://128mots.com/index.php/category/python/

Typescript getter setter Plus d’informations:

Le stockage des classes peut se faire dans des fichiers séparés, dans ce cas il s’agit d’une déclaration de module.

Les modules permettent de rendre accessible la classe en dehors du fichier. La classes doit dans un premier temps être exportée via « export » pour être visible exemple de personne.ts:

Utilisation des classes

Comme dans les autres langages une classe permet de créer des objets et regroupe des variables et des fonctions qui sont fortement liées « Highly Related »

TypeScript est un langage à typage fort typé, orienté objet et compilé. TypeScript est un sur-ensemble typé de JavaScript compilé en JavaScript. TypeScript est JavaScript et quelques fonctionnalités supplémentaires.

La documentation de typescript est disponible sur ce lien : https://www.typescriptlang.org/docs/home.html

Angular est un framework pour construire des applications clientes, il se base sur HTML/CSS et JavaScript/TypeScript.

Angular propose les avantages suivants :

  1. Revealing Module Pattern : permet d’organiser le code en un ou plusieurs modules et donne une meilleure structure.
  2. Architecture propre et structurée.
  3. Code réutilisable.
  4. Application plus facilement testable.

ANGULAR en moins de 128 mots – Composants Angular – Partie 6

Construction d’application par bloc

Les composants sont comme des blocs de construction dans une application Angular.

Les composants sont définis à l’aide du décorateur @component. Un composant possède un sélecteur, un modèle, un style et d’autres propriétés, à l’aide desquels il spécifie les métadonnées requises pour traiter le composant.

Exemple d’architecture en bloc de composant Angular

AppComponent est le composant racine de notre application. C’est la base de l’arborescence des composants de l’application Angular.

https://angular.io/guide/architecture-modules

Pour générer un composant la commande est :

ng g component MyComponent

Exemple de composant :

import { Component } from "@angular/core";

@Component({
  selector: "articles",
  template: "<h2>Article</h2>"
})
export class ArticlesComponent {
}

A noter que si vous n’avez pas utilisé la commande de génération de composant, il faut alors manuellement ajouter le composant dans le fichier src/app/app.module.ts dans les imports

import { BrowserModule } from "@angular/platform-browser";
import { NgModule } from "@angular/core";
import { AppComponent } from "./app.component";
import { ArticlesComponent } from "./articles.component";

@NgModule({
  declarations: [AppComponent, ArticlesComponent],
  imports: [BrowserModule, ArticlesComponent],
  providers: [],
  bootstrap: [AppComponent]
})
export class AppModule {}

ANGULAR en moins de 128 mots – TypeScript – Partie 5

Cet article fait suite aux quatre premiers sur le sujet ANGULAR et porte sur le langage TypeScript :

Utilisation des classes

Comme dans les autres langages une classe permet de créer des objets et regroupe des variables et des fonctions qui sont fortement liées « Highly Related »

Exemple de classe

class Personne {
  nom: string;
  prenom: string;

  sePresenter() {
    console.log('Mon nom est ' + this.nom + ' ' + this.prenom);
  }
}

Modules :

Le stockage des classes peut se faire dans des fichiers séparés, dans ce cas il s’agit d’une déclaration de module.

Les modules permettent de rendre accessible la classe en dehors du fichier. La classes doit dans un premier temps être exportée via « export » pour être visible exemple de personne.ts:

export class Personne {
  nom: string;
  prenom: string;

  sePresenter() {
    console.log('Mon nom est ' + this.nom + ' ' + this.prenom);
  }
}

exemple de fichier main.ts qui importe la classe Personne :

import { Personne } from "./personne";

let personne = new Personne();

A noter qu’il existe des modules Angular qui seront importés avec la mention @angular exemple :

import { Component } from '@angular/core';

A lire :

https://www.typescriptlang.org/docs/handbook/modules.html

https://www.angularchef.com/recette/50/

Algorithme KNN Python : k plus proches voisins

L’algorithme knn python d’apprentissage des k plus proches voisins (KNN) est utilisé pour effectuer de la classification de données.

algorithme knn python

Introduction

Pour prédire la classification d’une nouvelle donnée, l’algorithme se base sur les k enregistrements issus de l’ensemble de données d’apprentissage sont alors localisés les plus similaires à ce nouvel enregistrement.

La similitude entre les enregistrements peut être mesurée de différentes manières. Et généralement un bon point de départ est la distance euclidienne.

L’algorithme knn python :

Pour une entrée x quelle est sa classe y si je me base sur les k voisins les plus proches de x ?

  1. Trouver les k entrée partie les données d’entrainement qui sont les plus « proches » de mon entrée x (ici on utilisera par exemple la distance euclidienne)
  2. Faire voter chacune de ces données d’entrainement pour sa classe y.
  3. Retourner la classe majoritaire

Ainsi, Le succès de l’algorithme va reposer sur la quantité de donnée d’entrainement et sur la qualité de la mesure de la distance entre 2 vecteurs x.

Implémentation python de l’algorithme knn des k plus proches voisins.

Finalement, Voici un exemple d’utilisation et d’implémentation Python sur la base de données qui concerne l’accord d’un crédit en fonction de l’age et du montant demandé. La classe correspond à la réponse OUI ou NON.

from math import sqrt
 
# Faire une predicition de la classification
def predire_classification(donnee_test, entrainement, nombre_voisins_vote):
	voisins = recherche_voisins(entrainement, donnee_test, nombre_voisins_vote)
	sortie = [vecteur[-1] for vecteur in voisins]
	prediction = max(set(sortie), key=sortie.count)
	return prediction


 #Distance euclidienne de 2 vecteurs
def distance_euclidienne(vecteur1, vecteur2):
	distance = 0.0
	for i in range(len(vecteur1)-1):
		distance += (vecteur1[i] - vecteur2[i])**2
	return sqrt(distance)
 

# Recherche les voisins
def recherche_voisins(entrainement, donnee_test, nbVoisins):
	distances = list()
	for ligneEntrainement in entrainement:
		dist = distance_euclidienne(donnee_test, ligneEntrainement)
		distances.append((ligneEntrainement, dist))
	distances.sort(key=lambda tup: tup[1])
	kVoisins = list()
	for i in range(nbVoisins):
		kVoisins.append(distances[i][0])
	return kVoisins
 
 
# Données d'entrainement
donneesApprentissage = [[25,40000,'NON'],
		   [30,60000,'OUI'],
		   [35,80000,'NON'],
		   [45,50000,'NON'],
		   [20,60000,'NON'],
		   [60,15000,'NON'],
		   [70,5000,'OUI'],
		   [80,1000,'NON'],
		   [33,80000,'OUI'],
		   [32,10000,'NON']]

prediction = predire_classification(donneesApprentissage[1], donneesApprentissage, 3)
print('On devrait trouver %s, la prediction est : %s.' % (donneesApprentissage[1][-1], prediction))

Liens externes :

https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins

https://www.python.org/

Liens internes :

http://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/
http://128mots.com/index.php/2020/10/09/pytorch-comment-charger-un-modele-pre-entraine/

http://128mots.com/index.php/category/python/

Implémentation Python de l’algorithme de Dijkstra

Cet article fait suite à l’article suivant sur l’algorithme de Dijkstra : http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Voici l’implémentation Python de l’algorithme

from collections import deque

def dijkstra(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    while queue:
        t = queue.popleft()
        print("On visite le sommet " + str(t))
        for voisin in graph[t]:
                queue.append(voisin)
                nouvelle_distance = distance[t] + graph[t][voisin]
                if(voisin not in distance or nouvelle_distance < distance[voisin]):
                    distance[voisin] = nouvelle_distance
                    print("Met à jour le sommet " + str(voisin) + " avec la distance : " + str(nouvelle_distance))
                    
    return distance



#Liste d'ajacence du graphe
graph = {'A':{'B':15,'C':4},'B':{'E':5},'C':{'E':11,'D':2},'D':{'E':3},'E':{}}
distance = dijkstra(graph,'A')
print("Distances" + str(distance))