K-means

En statistiques et en apprentissage automatique, l'algorithme K-means de partitionnement de données est une méthode dont le but est de diviser des observations en K partitions (clusters) dans lesquelles chaque observation appartient à la partition avec la moyenne la plus proche. Les nuées dynamiques sont une généralisation de ce principe, pour laquelle chaque cluster est représenté par un noyau pouvant être plus complexe qu'une moyenne. L'algorithme classique de K-means est le même que l'algorithme de quantification de Lloyd-Max.

Sommaire

1 Description
2 Algorithme
- 2.1 Algorithme standard
- 2.2 Complexité algorithmique
3 Implémentations
- 3.1 Libres
- 3.2 Commerciales

Description

Etant donné un ensemble d'observations (x₁, x₂, …, x_n), où chaque observation est un vecteur de dimension d, l'algorithme k-means de regroupement vise à partitionner les n observations dans k ensembles (k ≤ n) S = {S₁, S₂, …, S_k} afin de minimiser la somme des carrés à l'intérieur de chaque partition :

$\underset{\mathbf{S}}{\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x_j \in S_i} \left\| \mathbf x_j - \boldsymbol\mu_i \right\|^2$

où μ_i est la moyenne des points dans S_i.

Algorithme

Algorithme standard

Choisir k moyennes m₁⁽¹⁾,…,m_k⁽¹⁾ initiales (au hasard par exemple)
Répéter jusqu'à convergence:

- assigner chaque observation à la moyenne la plus proche (i.e effectuer une partition de Voronoï selon les moyennes).

$S_i^{(t)} = \left\{ \mathbf x_j : \big\| \mathbf x_j - \mathbf m^{(t)}_i \big\| \leq \big\| \mathbf x_j - \mathbf m^{(t)}_{i^*} \big\| \text{ for all }i^*=1,\ldots,k \right\}$

- mettre à jour la moyenne de chaque cluster

$\mathbf m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf x_j \in S^{(t)}_i} \mathbf x_j$

La convergence est atteinte quand il n'y a plus de changement.

Complexité algorithmique

Le problème du clustering par les K-means est NP-difficile dans le cas général. Il est donc fréquemment fait usage d'heuristiques en pratique.

Implémentations

Libres

R Programming Language kmeans fournit divers algorithmes
Apache Mahout k-Means
SciPy vector-quantization
Silverlight widget demonstrating k-means algorithm
OpenCV fourni une implémentation de l'algorithme.

Commerciales

Portail de l’informatique

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article K-means de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

means — W2S2 [mi:nz] n plural means ▬▬▬▬▬▬▬ 1¦(method)¦ 2¦(money)¦ 3 by all means! 4 by no means/not by any means 5 by means of something 6 a means to an end 7 the means of production ▬▬▬▬▬▬▬ 1.) … Dictionary of contemporary English
means — [ minz ] (plural means) noun *** 1. ) count a method for doing or achieving something: WAY: Information is not easily obtained by any other means. an effective means for finding qualified job applicants means of: What means of transportation is… … Usage of the words and phrases in modern English
means — [miːnz] noun [plural] the money and resources that a person or organization has available: means to do something • Large corporations have the means to pay large fines without suffering hardship. • The group has limited means. • young families… … Financial and business terms
Means (band) — Means Also known as Means 2 An End Origin Regina, Saskatchewan, Canada Genres Christian Hardcore Post hardcore Metalcore Melodic Hardcore Pop Punk (early … Wikipedia
Means (surname) — Means is a surname, and may refer to Carey Means, an American voice actor David Means, an American writer Gardiner Means (1896–1988), an American economist Gaston Means (1879–1938), an American private detective, bootlegger, and con artist Jimmy… … Wikipedia
means — 1. When the meaning is ‘financial resources’, means is treated as plural: Their means are somewhat limited. When the meaning is ‘a way or method’ it can operate as a singular noun (when preceded by a determiner such as a, any, or every) or as a… … Modern English usage
Means Racing — Owner(s) Jimmy Means Base Forest City, North Carolina Series Nationwide Series Race drivers 52. Bobby Santos III/Tim Schendel/Daryl Harr/Kevin Lepage Sponsors … Wikipedia
Means Street Historic District — U.S. National Register of Historic Places U.S. Historic district … Wikipedia
means-test — ˈmeans test noun [countable] an official check in order to find out if someone is poor enough to receive welfare benefit S (= payments from the state when you are ill, without work etc): • He has made proposals for means tests for Social Security … Financial and business terms
means-testing — means test ˈmeans test noun [countable] an official check in order to find out if someone is poor enough to receive welfare benefit S (= payments from the state when you are ill, without work etc): • He has made proposals for means tests for… … Financial and business terms
means — [mēnz] pl.n. 〚/span> MEAN3, n.〛 1. [with sing. or pl. v.] that by which something is done or obtained; agency [the fastest means of travel] 2. resources or available wealth; often, specif., great wealth; riches [a person of … Universalium

Dictionnaires et Encyclopédies sur 'Academic'

K-means

Sommaire

Description