Locality sensitive hashingLocality sensitive hashing (LSH) est une méthode de recherche approximative dans des espaces de grande dimension. C'est une solution au problème de la malédiction de la dimension qui apparait lors d'une recherche des plus proches voisins en grande dimension. L'idée principale est d'utiliser une famille de fonction de hachage choisies telles que des points proches dans l'espace d'origine aient une forte probabilité d'avoir la même valeur de hachage. La méthode a de nombreuses applications en vision artificielle, traitement automatique de la langue, bio-informatique.
Arbre kdvignette|Partition d'un espace à trois dimensions pour la construction d'un arbre 3-d. En informatique, un arbre k-d (ou k-d tree, pour k-dimensional tree) est une structure de données de partition de l'espace permettant de stocker des points, et de faire des recherches (recherche par plage, plus proche voisin, etc.) plus rapidement qu'en parcourant linéairement le tableau de points. Les arbres k-d sont des cas particuliers d'arbres BSP (binary space partition trees).
Méthode des k plus proches voisinsEn intelligence artificielle, plus précisément en apprentissage automatique, la méthode des k plus proches voisins est une méthode d’apprentissage supervisé. En abrégé KPPV ou k-PPV en français, ou plus fréquemment k-NN ou KNN, de l'anglais k-nearest neighbors. Dans ce cadre, on dispose d’une base de données d'apprentissage constituée de N couples « entrée-sortie ». Pour estimer la sortie associée à une nouvelle entrée x, la méthode des k plus proches voisins consiste à prendre en compte (de façon identique) les k échantillons d'apprentissage dont l’entrée est la plus proche de la nouvelle entrée x, selon une distance à définir.
R-arbreLes R-arbres sont des structures de données sous forme d'arbre utilisées comme méthodes d'exploration spatiale. Elles servent à indexer des informations multidimensionnelles (coordonnées géographiques, rectangles ou polygones). Inventés par Antonin Guttman en 1984, les R-arbres sont utilisés aussi bien dans des contextes théoriques qu'appliqués. Un cas d'utilisation typique des R-arbres est le stockage d'informations géographiques : par exemple l'emplacement des restaurants dans une ville, ou les polygones constitutifs des dessins d'une carte (routes, bâtiments, côtes, etc.
Diagramme de VoronoïEn mathématiques, un diagramme de Voronoï est un pavage (découpage) du plan en cellules (régions adjacentes) à partir d'un ensemble discret de points appelés « germes ». Chaque cellule enferme un seul germe, et forme l'ensemble des points du plan plus proches de ce germe que d'aucun autre. La cellule représente en quelque sorte la « zone d'influence » du germe. Le diagramme doit son nom au mathématicien russe Gueorgui Voronoï (1868-1908). Le découpage est aussi appelé décomposition de Voronoï, partition de Voronoï ou tessellation de Dirichlet.
Fléau de la dimensionLe fléau de la dimension ou malédiction de la dimension (curse of dimensionality) est un terme inventé par Richard Bellman en 1961 pour désigner divers phénomènes qui ont lieu lorsque l'on cherche à analyser ou organiser des données dans des espaces de grande dimension alors qu'ils n'ont pas lieu dans des espaces de dimension moindre. Plusieurs domaines sont concernés et notamment l'apprentissage automatique, la fouille de données, les bases de données, l'analyse numérique ou encore l'échantillonnage.
Partition binaire de l'espacethumb|Partition binaire de l'espace (haut) et arbre BSP correspondant (bas). L'espace contient des segments {A, B1, B2, C1, C2, D1, D2, D3}. Le nœud racine contient le segment A ; les deux sous-arbres correspondent aux zones de part et d'autre de A. thumb|Partition binaire d'un espace à trois dimensions pour la construction d'un arbre k-d. La partition binaire de l'espace (binary space partitioning ou BSP) est un système utilisé pour diviser l'espace en zones convexes.
Réduction de la dimensionnalitévignette|320x320px|Animation présentant la projection de points en deux dimensions sur les axes obtenus par analyse en composantes principales, une méthode populaire de réduction de la dimensionnalité La réduction de la dimensionnalité (ou réduction de (la) dimension) est un processus étudié en mathématiques et en informatique, qui consiste à prendre des données dans un espace de grande dimension, et à les remplacer par des données dans un espace de plus petite dimension.
Space partitioningIn geometry, space partitioning is the process of dividing a space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). In other words, space partitioning divides a space into non-overlapping regions. Any point in the space can then be identified to lie in exactly one of the regions. Space-partitioning systems are often hierarchical, meaning that a space (or a region of space) is divided into several regions, and then the same space-partitioning system is recursively applied to each of the regions thus created.
Système de recommandationLes systèmes de recommandation sont une forme spécifique de filtrage de l'information (SI) visant à présenter les éléments d'information (films, musique, livres, news, images, pages Web, etc) qui sont susceptibles d'intéresser l'utilisateur. Généralement, un système de recommandation permet de comparer le profil d'un utilisateur à certaines caractéristiques de référence, et cherche à prédire l'« avis » que donnerait un utilisateur.
Similarity measureIn statistics and related fields, a similarity measure or similarity function or similarity metric is a real-valued function that quantifies the similarity between two objects. Although no single definition of a similarity exists, usually such measures are in some sense the inverse of distance metrics: they take on large values for similar objects and either zero or a negative value for very dissimilar objects. Though, in more broad terms, a similarity function may also satisfy metric axioms.
Partitionnement de donnéesvignette|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.
Géométrie algorithmiquevignette|Rendu d'un cylindre à l'aide d'un programme d'ordinateur. La géométrie algorithmique est le domaine de l'algorithmique qui traite des algorithmes manipulant des concepts géométriques. La géométrie algorithmique est l'étude des algorithmes manipulant des objets géométriques. Par exemple, le problème algorithmique qui consiste, étant donné un ensemble de points dans le plan décrits par leurs coordonnées, à trouver la paire de points dont la distance est minimale est un problème d'algorithmique géométrique.
