La satisfaction et les clusters

Dans cours

Description

Cette séance de cours traite du concept de seuil de satisfaisabilité, des grappes de solutions aux problèmes de satisfaction et du rôle du paramètre alpha dans le contrôle de la difficulté du problème. Il couvre également le calcul du nombre moyen de clusters auxquels une configuration appartient et la définition d'alpha d. L'instructeur explique comment trouver alpha d à partir d'une expression impliquant le nombre de clusters et comment cela se rapporte à la valeur attendue des configurations appartenant aux clusters.

Connectez-vous pour regarder la vidéo

Enseignants (2)

Source officielle

https://mediaspace.epfl.ch/media/0_fowgniqg

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Séances de cours associées (30)

Concepts associés (19)

Partitionnement de données

vignette|upright=1.2|Exemple de clustering hiérarchique. Le partitionnement de données (ou data clustering en anglais) est une méthode en analyse des données. Elle vise à diviser un ensemble de données en différents « paquets » homogènes, en ce sens que les données de chaque sous-ensemble partagent des caractéristiques communes, qui correspondent le plus souvent à des critères de proximité (similarité informatique) que l'on définit en introduisant des mesures et classes de distance entre objets.

Problème de satisfaction de contraintes

Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable.

K-moyennes

Le partitionnement en k-moyennes (ou k-means en anglais) est une méthode de partitionnement de données et un problème d'optimisation combinatoire. Étant donnés des points et un entier k, le problème est de diviser les points en k groupes, souvent appelés clusters, de façon à minimiser une certaine fonction. On considère la distance d'un point à la moyenne des points de son cluster ; la fonction à minimiser est la somme des carrés de ces distances.

Computation

A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computations are mathematical equations and computer algorithms. Mechanical or electronic devices (or, historically, people) that perform computations are known as computers. The study of computation is the field of computability, itself a sub-field of computer science. The notion that mathematical statements should be ‘well-defined’ had been argued by mathematicians since at least the 1600s, but agreement on a suitable definition proved elusive.

Amas ouvert

En astronomie, un amas ouvert est un amas stellaire groupant environ de 100 à étoiles de même âge liées entre elles par la gravitation, et dont le diamètre varie de 1,5 à 15 pc, avec une moyenne de 4 à 5 pc. Les amas ouverts sont peu lumineux et s’observent essentiellement dans notre Galaxie, où ils se situent dans le plan galactique, et dans les galaxies proches : les deux Nuages de Magellan et la galaxie d’Andromède. On pense qu'ils se forment au sein des nuages moléculaires, les grands nuages de gaz et de poussières qui constituent les nébuleuses diffuses.