K-means

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

Description

Etant donné un ensemble d'observations (x1, x2, …, xn), où chaque observation est un vecteur de dimension d, l'algorithme k-means de regroupement vise à partitionner les n observations dans k ensembles (kn) S = {S1S2, …, Sk} 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

μi est la moyenne des points dans Si.

Algorithme

Algorithme standard

  • Choisir k moyennes m1(1),…,mk(1) 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

Commerciales


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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”