Ver el código de «K-medias»

'''''K''-medias''' es un método de [[algoritmo de agrupamiento|agrupamiento]], que
tiene como objetivo la partición de un [[conjunto]] de ''n'' observaciones en '' k '' grupos en el que cada
observación pertenece al grupo cuyo [[valor medio]] es más cercano. Es un método utilizado en [[minería de datos]].

La agrupación del conjunto de datos puede ilustrarse en una partición del espacio de datos en [[Polígonos_de_Thiessen|celdas de Voronoi]].

El problema es computacionalmente difícil ([[NP-hard]]). Sin embargo, hay eficientes
[[Heurística_(informática)|heurísticas]] que se emplean comúnmente y convergen rápidamente a un óptimo local.
Estos suelen ser similares a los algoritmos [[Algoritmo_esperanza-maximización|esperanza-maximización]] de [[mezclas]]
de [[Distribución_normal|distribuciones gausianas]] por medio de un enfoque de refinamiento iterativo empleado por ambos algoritmos.
Además, los dos algoritmos usan los centros que los grupos utilizan para modelar los datos, sin embargo k-medias tiende a encontrar
grupos de extensión espacial comparable, mientras que el mecanismo expectation-maximization
permite que los grupos tengan formas diferentes.

== Descripción ==
Dado un conjunto de observaciones ('''x'''<sub>1</sub>,
'''x'''<sub>2</sub>, …,
'''x'''<sub>''n''</sub>), donde cada observación es un vector real de ''d'' dimensiones, k-medias construye una partición de las
observaciones en ''k'' conjuntos (''k'' ≤ ''n'') a fin de minimizar la suma de los cuadrados dentro de cada grupo (WCSS):
'''S'''&nbsp;=&nbsp;{''S''<sub>1</sub>,&nbsp;''S''<sub>2</sub>,&nbsp;…,&nbsp;''S''<sub>''k''</sub>}

:<math>\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 </math>

donde '''''µ'''''<sub>''i''</sub> es la media de puntos en
''S''<sub>''i''</sub>.

== Historia ==
El término "''k-medias''" fue utilizado por primera vez por James MacQueen en 1967,<ref name="macqueen1967">{{cite conference
 |first=J. B. |last=MacQueen
 |year=1967
 |title=Some Methods for classification and Analysis of Multivariate
Observations
 |url=http://projecteuclid.org/euclid.bsmsp/1200512992
|accessdate=7 de abril de 2009
 |conference=Proceedings of 5th Berkeley Symposium on Mathematical
Statistics and Probability
 |publisher=[[University of California Press]]
 |volume=1 |pages=281–297
 |mr=0214227
 |zbl=0214.46201
}}</ref> aunque la idea se remonta a [[Hugo Steinhaus]] en
1957.<ref>{{cita publicación
 |nombre=H. |apellido=Steinhaus |enlaceautor=Hugo Steinhaus
 |título=Sur la division des corps matériels en parties
 |publicación=Bull. Acad. Polon. Sci.
 |volumen=4 |número=12 |páginas=801–804
 |año=1957
 |mr=0090073
 |zbl=0079.16403 |idioma=francés
}}</ref> El [[#Algoritmo_est.C3.A1ndar| algoritmo estándar]] fue propuesto por primera vez por Stuart Lloyd en 1957 como una técnica para [[modulación por impulsos codificados]], aunque no se publicó fuera de los laboratorios Bell hasta 1982.<ref name="lloyd1957">{{cita publicación
 |nombre=S. P. |apellido=Lloyd
 |título=Least square quantization in PCM
 |publicación=Bell Telephone Laboratories Paper
 |año=1957
}} Publicado mucho más tarde en la revista:
{{cita publicación
 |nombre=S. P. |apellido=Lloyd.

|url=http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf
 |fechaacceso=15 de abril de 2009
 |título=Least squares quantization in PCM
 |publicación=[[IEEE Transactions on Information Theory]]
 |volumen=28 |número=2 |páginas=129–137
 |año=1982
 |doi=10.1109/TIT.1982.1056489
}}</ref> En 1965, E. W. Forgy publicó esencialmente el mismo método, por lo que a veces también se le nombra como Lloyd-Forgy.<ref name="forgy65">{{cita publicación
 |autor=E.W. Forgy
 |título=Cluster analysis of multivariate data: efficiency versus
interpretability of classifications
 |url=https://archive.org/details/sim_biometrics_1965-09_21_3/page/768
 |publicación=Biometrics
 |volumen=21
 |páginas=768–769
 |año=1965}}</ref> Una versión más eficiente fue propuesta y publicada en [[Fortran]] por Hartigan y Wong en 1975/1979.<ref name="hartigan1975">{{cita libro
 |título=Clustering algorithms
 |url=https://archive.org/details/clusteringalgori0000hart
 |autor=J.A. Hartigan
 |año=1975
 |editorial=John Wiley & Sons, Inc.
}}</ref><ref name="hartigan1979" />

== Algoritmos ==

=== Algoritmo estándar ===
El algoritmo más común utiliza una técnica de refinamiento iterativo. Debido a su ubicuidad a menudo se llama el '''algoritmo ''k''-medias''', también se le conoce como '''algoritmo de Lloyd''', sobre todo en la comunidad informática.

Dado un conjunto inicial de ''k'' centroides '''m'''<sub>1</sub><sup>(1)</sup>,…,'''m'''<sub>''k''</sub><sup>(1)</sup> (ver más abajo), el algoritmo continúa alternando entre dos pasos:<ref>{{cita libro
  | apellido =MacKay
  | nombre =David
  | enlaceautor =David MacKay (scientist)
  | título =Information Theory, Inference and Learning Algorithms
  | editorial = [[Cambridge University Press]]
  | año =2003
  | url =http://www.inference.phy.cam.ac.uk/mackay/itila/book.html
  | isbn = 0-521-64298-1
  | capítulo=Chapter 20. An Example Inference Task: Clustering
  |
urlcapítulo=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf

  | páginas=284–292
  | ref=mackay2003
  | mr=2012999
}}</ref>
:'''Paso de asignación''': Asigna cada observación al grupo con la media más cercana (es decir, la partición de las observaciones de acuerdo con el [[diagrama de Voronoi]] generado por los centroides).
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - m^{(t)}_i \big \| 
\le \big \| x_p - m^{(t)}_j \big \| \ \forall\ 1 \le j \le k 
\big\}</math>
:: Donde cada <math>x_p</math> va exactamente dentro de un <math>S^{(t)}_i</math>, incluso aunque pudiera ir en dos de ellos.
:'''Paso de actualización''': Calcular los nuevos centroides como el [[centroide]] de las observaciones en el grupo.
::<math>\mathbf m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf 
x_j \in S^{(t)}_i} \mathbf x_j </math>
El algoritmo se considera que ha convergido cuando las asignaciones ya no cambian.

Los métodos de inicialización de Forgy y Partición Aleatoria son comúnmente utilizados.<ref name="hamerly">
{{Cita web|author=Hamerly, G. and Elkan, C.|year=2002|title=Alternatives to the k-medias algorithm that find better
clusterings|booktitle=Proceedings of the eleventh international conference on
Information and knowledge management (CIKM)|url=http://charlotte.ucsd.edu/users/elkan/cikm02.pdf|access-date=3 de enero de 2013|archiveurl=https://web.archive.org/web/20130201113544/http://charlotte.ucsd.edu/users/elkan/cikm02.pdf|deadurl=yes|fechaarchivo=2013-02-01}}
</ref>
El método Forgy elige aleatoriamente ''k'' observaciones del conjunto de datos y las utiliza como centroides iniciales. El método de partición aleatoria primero asigna aleatoriamente un clúster para cada observación y después procede a la etapa de actualización, por lo tanto calcular el clúster inicial para ser el centro de gravedad de los puntos de la agrupación asignados al azar.
El método Forgy tiende a dispersar los centroides iniciales, mientras que la partición aleatoria ubica los centroides cerca del centro del conjunto de datos. Según Hamerly y compañía,<ref name="hamerly"/> el método de partición aleatoria general, es preferible para los algoritmos tales como los ''k-medias armonizadas'' y
fuzzy ''k-medias''. Para expectation maximization y el algoritmo estándar el método de Forgy es preferible.

<gallery caption="Demostración del algoritmos estándar" widths="150">
Image:K Means Example Step 1.svg|1) ''k'' centroides iniciales (en este caso ''k''=3) son generados aleatoriamente dentro de un conjunto de datos (mostrados en color).
Image:K Means Example Step 2.svg|2) ''k'' grupos son generados asociándole el punto con la media más cercana. La partición aquí representa el [[diagrama de Voronoi]] generado por los centroides.
Image:K Means Example Step 3.svg|3) EL [[centroide]] de cada uno de los ''k'' grupos se recalcula.
Image:K Means Example Step 4.svg|4) Pasos 2 y 3 se repiten hasta que se logre la convergencia.
</gallery>
Como se trata de un algoritmo heurístico, no hay ninguna garantía de que convergen al óptimo global, y el resultado puede depender de los grupos iniciales. Como el algoritmo suele ser muy rápido, es común para ejecutar varias veces con diferentes condiciones de partida. Sin embargo, en el peor de los casos, ''k-medias'' puede ser muy lento para converger: en particular, se ha demostrado que existen conjuntos de determinados puntos, incluso en 2 dimensiones, en la que ''k-medias'' toma tiempo exponencial, es decir {{math|2<sup>O(<var>n</var>)</sup>}}, para converger.<ref>{{cita publicación
 |nombre=A. |apellido=Vattani.
 |url=http://cseweb.ucsd.edu/users/avattani/papers/kmeans-journal.pdf
 |título=k-medias requires exponentially many iterations even in the plane
 |publicación=[[Discrete and Computational Geometry]]
 |volumen=45 |número=4 |páginas=596–616
 |año=2011
 |doi=10.1007/s00454-011-9340-1
}}</ref> Estos conjuntos de puntos no parecen surgir en la práctica: esto se ve corroborado por el hecho de que en la mayoría de los casos el [[tiempo de ejecución]] de ''k-medias'' es polinomial.<ref name="Arthur, D.;
Manthey, B.; Roeglin, H. 2009">{{cite conference | author=Arthur, D.;
 Manthey, B.; Roeglin, H. | year=2009 | title=k-medias has polynomial
smoothed complexity | booktitle=Proceedings of the 50th Symposium on
Foundations of Computer Science (FOCS)}}</ref>

El "paso de asignación" también se le conoce como '''paso expectativa''', la "etapa de actualización", como '''paso maximización''', por lo que este algoritmo una variante del algoritmo generalizado [[expectation-maximization]].

=== Complejidad ===
Respecto a la complejidad computacional, el agrupamiento ''k-medias''
para problemas en espacios de ''d'' dimensiones es:
* [[NP-hard]] en un espacio euclidiano general ''d'' incluso para 2 grupos<ref>{{cita publicación
 |autor=Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P.
 |título=NP-hardness of Euclidean sum-of-squares clustering
 |publicación=[[Machine Learning (journal)|Machine Learning]]
 |año=2009
 |volumen=75 |páginas=245–249
 |doi=10.1007/s10994-009-5103-0}}</ref><ref>{{cita publicación
 |título=Random Projection Trees for Vector Quantization
 |autor=Dasgupta, S. and Freund, Y.
 |publicación=Information Theory, IEEE Transactions on
 |volumen=55
 |páginas=3229–3242
 |fecha = julio de 2009
 |doi=10.1109/TIT.2009.2021326
 |arxiv=0805.1390}}
</ref>
* [[NP-hard]] para un número general de grupos ''k'' incluso en el plano<ref>{{cita publicación
 |autor=Mahajan, M.; Nimbhorkar, P.; Varadarajan, K.
 |título=The Planar k-medias Problem is NP-Hard
 |publicación=[[Lecture Notes in Computer Science]]
 |año=2009
 |volumen=5431 |páginas=274–285
 |doi=10.1007/978-3-642-00202-1_24}}
</ref>
* Si ''k'' y ''d'' son fijados, el problema se puede resolver en un tiempo <math>O(n^{dk+1}log(n))</math>, donde  <math>n</math> es el número de entidades a particionar<ref>{{cite conference
  |author=Inaba, M.; Katoh, N.; Imai, H.
  |year=1994
  |title=Applications of weighted Voronoi diagrams and randomization to
 variance-based ''k''-clustering
  |conference=[[Symposium on Computational Geometry|Proceedings of 10th
 ACM Symposium on Computational Geometry]]
  |pages=332–339
  |doi= 10.1145/177424.178042}}
 </ref>

Por lo tanto, una gran variedad de [[heurísticas]] son usadas generalmente.

* El algoritmo <math>k</math>-means que se discute debajo tiene orden polinomial para la mayoría de los casos. Se ha demostrado que<ref name="Arthur,
 D.; Manthey, B.; Roeglin, H. 2009"/> para un conjunto arbitrario de <math>n</math> puntos en <math>[0,1]^d</math>,
si cada punto es perturbado independientemente por una distribución normal con media <math>0</math> y varianza
<math>\sigma^2</math>, entonces el tiempo de ejecución del algoritmo <math>k</math>-means está acotado por <math>O( 
n^{34}k^{34}d^8 log^4(n)/ \sigma^6 )</math>, que es un tiempo polinomial en <math>n</math>, <math>k</math>,
<math>d</math> y <math>1/\sigma</math>.
* Se han demostrado mejores cotas para casos simples. Por ejemplo,<ref>{{cite conference|author=Arthur; Abhishek Bhowmick|year=2009|title=A theoretical analysis of Lloyd's algorithm for
k-medias clustering|url=http://www.cse.iitk.ac.in/users/bhowmick/lloyd.pdf}}</ref> demuestra que el tiempo de corrida del algoritmo <math>k</math>-means está acotado por <math>O(dn^4M^2)</math> para <math>n</math> puntos enteros en la rejilla <math>\{1,\dots, M\}^d</math>.

=== Variaciones ===
* [[Fuzzy clustering#Fuzzy c-means clustering|Fuzzy C-Means Clustering]] es una versión difusa del k-medias, donde cada punto tiene un grado difuso de pertenecía a cada grupo.
* Modelos de mezclas gausianas entrenadas con el algoritmo [[Algoritmo esperanza-maximización]] presentan una asignación probabilística a cada grupo, en vez de asignaciones deterministas.
* Se han presentado varios métodos para elegir mejor los centroides iniciales. Una propuesta reciente es [[k-medias++]].
* Algoritmos de filtrado utilizan [[kd-tree]]s para mejorar la eficiencia en cada paso del algoritmo.<ref>{{cita publicación
 |autor=Kanungo, T.; [[David Mount|Mount, D. M.]]; [[Nathan
Netanyahu|Netanyahu, N. S.]]; Piatko, C. D.; Silverman, R.; Wu, A. Y.
 |doi=10.1109/TPAMI.2002.1017616
 |url=http://www.cs.umd.edu/~mount/Papers/pami02.pdf
|fechaacceso=24 de abril de 2009
 |título=An efficient k-medias clustering algorithm: Analysis and
implementation
 |publicación=IEEE Trans. Pattern Analysis and Machine Intelligence
 |volumen=24 |año=2002 |páginas=881–892 }}
</ref>
* Algunos métodos también intentan acelerar el algoritmo usando [[coreset]]s<ref>{{Cite conference
 |author    = Frahling, G.; Sohler, C.
 |year    = 2006
 |title    = A fast k-medias implementation using coresets
 |booktitle    = [[Symposium on Computational Geometry|Proceedings of the
twenty-second annual symposium on Computational geometry (SoCG)]]
 |url    = http://www.frahling.de/Gereon_Frahling/Publications_files/A%20fast%20k-medias%20implementation%20using%20Coresets%20(Frahling,%20Sohler).pdf
 }}</ref> or the [[triangle inequality]].<ref>{{Cite conference
 |author = Elkan, C.
 |year=2003
 |title=Using the triangle inequality to accelerate k-medias
 |booktitle=Proceedings of the Twentieth International Conference on
Machine Learning (ICML)
 |url=http://www-cse.ucsd.edu/~elkan/kmeansicml03.pdf
}}</ref>
* Se puede escapar de óptimos locales intercambiando puntos entre los grupos.<ref name="hartigan1979">{{cita publicación
 | first1 = J. A. |last1=Hartigan
 | first2 = M. A. |last2=Wong
 | año = 1979
 | título =  Algorithm AS 136: A k-medias Clustering Algorithm
 | publicación = [[Journal of the Royal Statistical Society]], Series C (Applied Statistics)
 | volumen = 28
 | número = 1
 | páginas = 100–108
 | jstor = 2346830
}}</ref>
* El algoritmo [[Spherical k-medias]] es bastante usado para datos direccionales.<ref>{{cita publicación
 | first1 = I. S. |last1=Dhillon
 | first2 = D. M. |last2=Modha
 | año = 2001
 | título =  Concept decompositions for large sparse text data using clustering
 | publicación = Machine Learning
 | volumen = 42
 | número = 1
 | páginas = 143–175
}}</ref>
* El algoritmo [[Minkowski metric weighted k-medias]] trata el problema del ruido asignando pesos a las componentes de los vectores por grupos<ref>{{cita publicación
 | first1 = R. C. |last1=Amorim
 | first2 = B |last2=Mirkin
 | año = 2012
 | título =  Minkowski metric, feature weighting and anomalous cluster
initializing in k-medias clustering
 | publicación = Pattern Recognition
 | volumen = 45
 | número = 3
 | páginas = 1061–1075
 | doi=10.1016/j.patcog.2011.08.012
}}</ref>

== Discusión ==
[[Archivo:Iris Flowers Clustering kMeans.svg|miniaturadeimagen|450px|agrupamiento ''k-medias''
para [[Iris flower]] y especies actuales utilizando para la
visualización [[Environment for DeveLoping KDD-Applications Supported
by Index-Structures|ELKI]]. Los centroides de los grupos son marcados
usando símbolos semitransparentes un poco más grandes.]]
[[Archivo:ClusterAnalysis Mouse.svg|miniaturadeimagen|450px|agrupamiento ''k-medias'' y
agrupamiento EM en un conjunto de datos artificial ("mouse").
La tendencia del ''k-medias'' a producir grupos con tamaños parecidos
nos lleva a obtener malos resultados, mientras que EM se beneficia de la
distribución gausiana presente en el conjunto de datos.]]

Las dos características claves del ''k-medias'', las que lo hacen eficiente vienen a convertirse en su principal problema:
* La [[distancia euclideana|distancia euclidiana]] se usa como una [[metric (mathematics)|métrica]] y la [[varianza]] es usada como una medida de la dispersión de los grupos.
* El número de grupos ''k'' es un parámetro de entrada: una elección inapropiada puede acarrear malos resultados. Por eso es muy importante cuando corremos el ''k-medias'' tener en cuenta la importancia de [[determining the number of clusters in a data set|determinar el número de grupos para un conjunto de datos]].
* La convergencia a óptimos locales puede traer malos resultados(ver ejemplo en Fig.).

Una limitación clave del ''k-medias'' es su modelo de agrupamiento.
El concepto se basa en grupos esféricos que son separables de una forma
en que el valor de la media converge hacia el centro del grupo.
Se espera que los grupos tengan igual tamaño, por lo que la asignación
al grupo más cercano es la asignación correcta. Cuando por ejemplo
aplicamos ''k-medias'' con un valor de <math>k=3</math> al conjunto de
datos [[Iris flower]], el resultado no es el esperado incluso habiendo
tres especies en el conjunto de datos. Con <math>k=2</math>, los dos
grupos visibles(uno conteniendo dos especies) se pueden observar, mientras
que con <math>k=3</math> uno de los dos grupos se divide en dos partes
iguales. De hecho, <math>k=2</math> es más apropiado para este conjunto
de datos, aunque este último contenga 3 ''clases''. Como con cualquier
otro algoritmo de agrupamiento, el resultado de ''k-medias'' depende del
conjunto de datos para satisfacer las necesidades del algoritmo.
Simplemente trabaja bien en algunos conjuntos de datos mientras que
falla en otros.

El resultado del ''k-medias'' se puede ver como las [[Voronoi diagram|celdas de Voronoi]] de los centroides de los grupos. Como los datos se separan en cierta forma por la media de los grupos, esto puede llevarnos a óptimos locales como se puede ver en el conjunto "mouse". Los modelos gausianos usados por el algoritmo [[Expectation-maximization]] (que puede ser visto como una generalización del ''k-medias'') son más flexibles ya que controlan varianzas y covarianzas. El resultado de EM crea grupos con tamaño variable más fácilmente que ''k-medias'' tanto como grupos correlacionados (no en este ejemplo).

== Aplicaciones del algoritmo ==

Agrupamiento ''k-medias'' cuando se usan heurísticas como el algoritmo de Lloyd es fácil de implementar incluso para grandes
conjuntos de datos. Por lo que ha sido ampliamente usado en muchas áreas como [[segmentación de mercados]], [[visión por computadoras]], [[geoestadística]],<ref>Honarkhah, M and Caers, J, 2010,
''[http://dx.doi.org/10.1007/s11004-010-9276-7 Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling]'', Mathematical
Geosciences, 42: 487 - 517</ref> [[astronomía]] y minería de datos en agricultura. También se usa como preprocesamiento
para otros algoritmos, por ejemplo para buscar una configuración inicial.

Una aplicación más avanzada es la de su uso en el marketing y el análisis geográfico, para hacerlo primero se deben recopilar datos de latitud y longitud de los puntos que se requieren a estudiar, luego por medio de algoritmos no supervisados de machine learning como K-Means en conjunto con Voronoi se pueden obtener los clusters de los datos pero con la diferencia de que estos estarán delimitados por una región de Voronoi, entonces se puede obtener la "dominancia del cluster". Caso similar también  aplica para el marketing, por ejemplo, en lugar de tener «latitud» o «longitud» de datos geoespaciales podríamos tener una relación entre ingresos de un grupo de usuarios y lo que suelen gastar, de forma que se pueda optimizar la publicidad de forma más eficiente usando la región de Voronoi como una ayuda extra para delimitar una publicidad de marketing a un grupo de usuarios.<ref>{{Cita web|url=https://neuralbatch.com/machine-learning/analisis-geoespacial-en-python-cluster-kmeans-voronoi-y-open-street-map/|título=▷ Análisis geoespacial en Python: Cluster K-Means, Voronoi y Open Street Map|fechaacceso=2024-03-01|fecha=2024-01-16|idioma=es}}</ref>

== K-medoides ==

Se trata de una alternativa del algoritmo K-medias. Si <math>(X,d)</math> es un [[espacio métrico]], el medoide de los puntos <math>x_1 ,...,x_n \in X</math> es el punto <math>x_i</math> que minimiza la expresión <math>\sum_{j=1}^n d(x_i ,x_j )</math>. El algoritmo empieza con <math>k</math> centros, escogidos entre las observaciones. Cada observación se agrupa con el centro más próximo. Formados los <math>k</math> grupos se calculan sus respectivos medoides que serán los nuevos centros. El algoritmo se repite hasta que los grupos se estabilizan. 

Nótese que los centros, en este caso, siempre forman parte de las observaciones. Asimismo, este algoritmo, a diferencia de K-medias, funciona para nociones de métrica (o [[Medida de similitud|similitud]]) que no permite calcular medias. En particular, funciona para espacios métricos no [[Espacio euclídeo|euclidianos]].

== Software ==

=== Libre ===
* [[Apache Mahout]] [https://cwiki.apache.org/confluence/display/MAHOUT/k-medias+Clustering k-medias]
* [[CrimeStat]] implementa dos algoritmos espaciales de ''k-medias'', uno de ellos permite al usuario definir los puntos iniciales.
* [[ELKI]] contiene k-medias (con iteracionesd de Lloyd and MacQueen, as'i como diferente inicializaciones, por ejemplo k-medias++) y otros algoritmos de agrupamientos más avanzados.
* [http://www.mlpack.org MLPACK] contiene una implementación del ''k-medias''
* [[R (programming language)|R]] [http://stat.ethz.ch/R-manual/R-patched/library/stats/html/kmeans.html kmeans] implementa una variedad de algoritmos<ref name="macqueen1967"/><ref name="lloyd1957"/><ref name="hartigan1979"/>
* [[SciPy]] [http://docs.scipy.org/doc/scipy/reference/cluster.vq.html vector-quantization]
* [http://www.codeding.com/?article=14 Silverlight widget mostrando el algoritmo ''k-medias'']
* [http://pgxn.org/dist/kmeans/ extensiones PostgreSQL para k-medias]
* [https://web.archive.org/web/20130104141907/http://graphlab.org/toolkits/clustering/ CMU's GraphLab Clustering library] Implementación eficiente para varios processadores.
* [[Weka (machine learning)|Weka]] contiene k-medias y algunas variantes, como k-medias++ y x-means.
* [http://spectralpython.sourceforge.net/algorithms.html#k-medias-clustering Spectral Python] contiene métodos para la [[clasificación no supervisada]] incluyendo el algoritmo k-medias.
* [[KNIME]] [http://www.knime.com/knime-analytics-platform] contiene nodos para la aplicación del algoritmo Kmeans de forma ágil y controlada, así como muchos otros algoritmos de segmentación y minería de datos.

=== Comercial ===
* IDL Cluster, Clust_Wts
* [http://reference.wolfram.com/mathematica/ref/ClusteringComponents.html ''Mathematica'' ClusteringComponents function]
* [[MATLAB]] [http://www.mathworks.com/access/helpdesk/help/toolbox/stats/kmeans.html kmeans]
* [[SAS System|SAS]] [http://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/fastclus_toc.htm FASTCLUS]
* [http://www.visumap.com/index.aspx?p=Products VisuMap kMeans Clustering] {{Wayback|url=http://www.visumap.com/index.aspx?p=Products |date=20130201113544 }}

=== Código fuente ===
* [[ELKI]] and [[Weka]] está escrito en Java y contiene implementaciones del k-medias
* k-medias en PHP,<ref>https://web.archive.org/web/20080208213306/http://www25.brinkster.com/denshade/kmeans.php.htm</ref> using VB,<ref>[http://people.revoledu.com/kardi/tutorial/kMean/download.htm k-medias Clustering Tutorial: Download<!-- Bot generated title -->]</ref> using [[Perl]],<ref>{{Cita web |url=http://www.lwebzem.com/cgi-bin/k_means/test3.cgi |título=Perl script for Kmeans clustering<!-- Bot generated title --> |fechaacceso=3 de enero de 2013 |urlarchivo=https://web.archive.org/web/20120618071332/http://www.lwebzem.com/cgi-bin/k_means/test3.cgi |fechaarchivo=18 de junio de 2012 }}</ref> using C++,<ref>[http://codingplayground.blogspot.com/2009/03/k-medias-in-c.html Antonio Gulli's coding playground: k-medias in C<!-- Bot generated title -->]</ref> using Matlab,<ref>[http://people.revoledu.com/kardi/tutorial/kMean/matlab_kMeans.htm k-medias Clustering Tutorial: Matlab Code<!-- Bot generated title -->]</ref> using Ruby,<ref>[http://ai4r.org/index.html AI4R :: Artificial Intelligence for Ruby<!-- Bot generated title -->]</ref><ref>[http://github.com/reddavis/k-medias/tree/master reddavis/k-medias · GitHub<!-- Bot generated title -->]</ref> using Python with scipy,<ref>[http://docs.scipy.org/doc/scipy/reference/cluster.vq.html k-medias clustering and vector quantization (scipy.cluster.vq) — SciPy v0.11 Reference Guide (DRAFT)<!-- Bot generated title -->]</ref> using X10<ref>{{Cita web |url=http://dist.codehaus.org/x10/applications/samples/KMeansDist.x10 |título=Copia archivada |fechaacceso=3 de enero de 2013 |urlarchivo=https://archive.today/20120709084340/http://dist.codehaus.org/x10/applications/samples/KMeansDist.x10 |fechaarchivo=9 de julio de 2012 }}</ref>
* Una implementación en C<ref>https://web.archive.org/web/20120302183933/http://www.cs.princeton.edu/~wdong/kmeans/</ref>
* Una colección de algoritmos de agrupamientos incluido k-medias, implementado en Javascript.<ref>http://code.google.com/p/figue/ FIGUE</ref> Online demo.<ref>https://web.archive.org/web/20130212004526/http://web.science.mq.edu.au/~jydelort/figue/demo.html</ref>
* [https://neuralbatch.com/machine-learning/analisis-geoespacial-en-python-cluster-kmeans-voronoi-y-open-street-map/ Aplicación de k-medias con Voronoi para obtener la delimitación de la dominancia de los clusters.]

== Referencias ==
{{listaref|2}}

{{Control de autoridades}}
{{DEFAULTSORT:k-medias Clustering}}
[[Categoría:Algoritmos]]
[[Categoría:Estadística]]
[[Categoría:Minería de datos]]