Ir al contenido

Diferencia entre revisiones de «K-means++»

De Wikipedia, la enciclopedia libre
Explorar historial interactivamente
← Ir a diferencia anterior
Contenido eliminado Contenido añadido
VisualWikitexto
m Bot: 8 - Estandarizaciones y otras mejoras automatizadas
InternetArchiveBot (discusión · contribs.)
Bots
2 074 506 ediciones
Rescatando 1 referencia(s) y marcando 0 enlace(s) como roto(s)) #IABot (v2.0.9.5
 
(No se muestran 19 ediciones intermedias de 11 usuarios)
Línea 1: Línea 1:
En [[minería de datos]], '''''k''-means++'''<ref><span class="citation conference" contenteditable="false">Arthur, D. and Vassilvitskii, S. (2007). [http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf "''k''-means++: the advantages of careful seeding"] (PDF). </span></ref><ref>http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Slides for presentation of method by Arthur, D. and Vassilvitskii, S.
En [[minería de datos]], '''''k''-means++'''<ref><span class="citation conference">Arthur, D. and Vassilvitskii, S. (2007). [http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf "''k''-means++: the advantages of careful seeding"] {{Wayback|url=http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf |date=20170821210702 }} (PDF). </span></ref><ref>http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Slides for presentation of method by Arthur, D. and Vassilvitskii, S.
</ref> es un algoritmo que se utiliza para la selección de los valores iniciales (o "semillas") en el algoritmo [[K-means|''k''-means clustering]]. Fue propuesto en 2007 por David Arturo y Sergei Vassilvitskii, como un algoritmo de aproximación para el problema [[NP-hard|NP-duro]] ''k''-means—una forma de evitar los agrupamientos pobres a veces encontrados por el algoritmo k-means estándar. Es similar al primero de tres métodos para encontrar semillas propuestos, en 2006,<ref><span class="citation conference" contenteditable="false">Ostrovsky, R., Rabani, Y., Schulman, L. J. and Swamy, C. (2006). </span></ref> por Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy. (La distribución de la primera semilla es diferente).<span class="cx-segment" data-segmentid="10"></span>
</ref> es un algoritmo que se utiliza para la selección de los valores iniciales (o "semillas") en el algoritmo [[K-means|''k''-means clustering]]. Fue propuesto en 2007 por David Arthur y Sergei Vassilvitskii, como un [[algoritmo de aproximación]] para el problema [[NP-hard|NP-duro]] ''k''-means—una forma de evitar los agrupamientos pobres a veces encontrados por el algoritmo k-means estándar. Es similar al primero de tres métodos para encontrar semillas propuestos, en 2006,<ref><span class="citation conference">Ostrovsky, R., Rabani, Y., Schulman, L. J. and Swamy, C. (2006). </span></ref> por Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy. (La distribución de la primera semilla es diferente).


== Base ==
== Base ==
El problema k-means consiste en encontrar grupos de puntos tal que se minimice la varianza intra-grupo, es decir, minimizar la suma de las distancias al cuadrado de cada punto al centro más cercano a él. Aunque la búsqueda de una solución exacta al problema de k-means para una entrada arbitraria es NP-duro,<ref><span class="citation journal" contenteditable="false">Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V. (2004). </span></ref>el enfoque estandar de encontrar una solución aproximada (a menudo llamado el algoritmo de Lloyd o el algoritmo k-means) es utilizado ampliamente y con frecuencia encuentra soluciones razonables rápidamente.
El problema k-means consiste en encontrar grupos de puntos tal que se minimice la varianza intra-grupo, es decir, minimizar la suma de las distancias al cuadrado de cada punto al centro más cercano a él. Aunque la búsqueda de una solución exacta al problema de k-means para una entrada arbitraria es NP-duro,<ref><span class="citation journal">Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V. (2004). </span></ref> el enfoque estándar de encontrar una solución aproximada (a menudo llamado el algoritmo de Lloyd o el algoritmo k-means) es utilizado ampliamente y con frecuencia encuentra soluciones razonables rápidamente.


Sin embargo, el algoritmo k-means tiene por lo menos dos grandes deficiencias teóricas:
Sin embargo, el algoritmo k-means tiene por lo menos dos grandes deficiencias teóricas:
* Primero, ha sido mostrado que, en el caso peor, el tiempo de corrida del algoritmo es súper-polinomial en el tamaño de la entrada.<ref><span class="citation" id="CITEREFArthur.2C_D._and_Vassilvitskii.2C_S.2006" contenteditable="false">Arthur, D. and Vassilvitskii, S. (2006), "How slow is the ''k''-means method?"</span></ref>
* Primero, ha sido mostrado que, en el caso peor, el tiempo de corrida del algoritmo es súper-polinomial en el tamaño de la entrada.<ref><span class="citation" id="CITEREFArthur.2C_D._and_Vassilvitskii.2C_S.2006">Arthur, D. and Vassilvitskii, S. (2006), "How slow is the ''k''-means method?"</span></ref>
* Segundo, la aproximación encontrada puede ser arbitrariamente mala con respecto a la función objetivo comparado al agrupamiento óptimo.<br>
* Segundo, la aproximación encontrada puede ser arbitrariamente mala con respecto a la función objetivo comparado al agrupamiento óptimo.
El algoritmo k-means++ aborda la segunda de estas deficiencias mediante la especificación de un procedimiento para inicializar los centros de los conjuntos antes de proceder con las k-means iteraciones de optimización estándar . Con la inicialización de k-means++ , el algoritmo está garantizado para encontrar una solución que es O (log k) competitiva a la solución óptima de k-means.<span class="cx-segment" data-segmentid="26"></span>
El algoritmo k-means++ aborda la segunda de estas deficiencias mediante la especificación de un procedimiento para inicializar los centros de los conjuntos antes de proceder con las k-means iteraciones de optimización estándar . Con la inicialización de k-means++ , el algoritmo está garantizado para encontrar una solución que es O (log k) competitiva a la solución óptima de k-means.


== Algoritmo de inicialización ==
== Algoritmo de inicialización ==
La intuición detrás de este enfoque es que la expansión de los k iniciales centros de conjuntos es una buena idea: el primer centro de conjunto se obtiene con una variable aleatoria uniforme desde los puntos que están agrupados, después de esto cada centro de grupo siguiente se elige desde el resto de los puntos con probabilidad proporcional a su distancia al cuadrado desde del centro de conjunto existente más cercano del punto.
La intuición detrás de este enfoque es que la expansión de los k iniciales centros de conjuntos es una buena idea: el primer centro de conjunto se obtiene con una [[variable aleatoria]] uniforme desde los puntos que están agrupados, después de esto cada centro de grupo siguiente se elige desde el resto de los puntos con probabilidad proporcional a su distancia al cuadrado desde del centro de conjunto existente más cercano del punto.


El algoritmo exacto es como sigue:
El algoritmo exacto es como sigue:
# Escoger un centro de entre los puntos de datos utilizando una variable aleatoria uniforme.
# Escoger un centro de entre los puntos de datos utilizando una variable aleatoria uniforme.
# Para cada punto x, calcular D(x), que es la distancia entre x y el centro más cercano que ya ha sido seleccionado.
# Para cada punto x, calcular D(x), que es la distancia entre x y el centro más cercano que ya ha sido seleccionado.
# Escoger un nuevo punto al azar (con variable aleatoria uniforme) como nuevo centro, utilizando una distribución de probabilidad ponderada donde un punto x es escogido con la probabilidad proporcional a D(<span class="texhtml " contenteditable="false"><var>x</var></span><span class="texhtml " contenteditable="false"></span>)<sup>2</sup>.
# Escoger un nuevo punto al azar (con variable aleatoria uniforme) como nuevo centro, utilizando una [[distribución de probabilidad]] ponderada donde un punto x es escogido con la probabilidad proporcional a D(<span class="texhtml "><var>x</var></span>)<sup>2</sup>.
# Repetir paso 2 y 3 hasta que se hayan seleccionado k centros.
# Repetir paso 2 y 3 hasta que se hayan seleccionado k centros.
# Ahora que los centros iniciales han sido elegidos, continuar utilizando [[K-means|''k''-means clustering]] estándar.
# Ahora que los centros iniciales han sido elegidos, continuar utilizando [[K-means|''k''-means clustering]] estándar.
Este método produce una mejora considerable en el error final de k-means. Aunque la selección inicial en el algoritmo toma tiempo extra, k-means converge muy rápidamente después de la selección de puntos iniciales y por lo tanto este algoritmo reduce el tiempo de cálculo. Los autores probaron su método con conjuntos de datos reales y sintéticos y obtuvieron mejoras de 2-veces en la velocidad, y para ciertos conjuntos de datos, cerca de 1000 veces mejoras en error. En estas simulaciones el nuevo método casi siempre se ejecuta al menos tan bien como vainilla k-means, tanto en la velocidad y como en el error.
Este método produce una mejora considerable en el error final de k-means. Aunque la selección inicial en el algoritmo toma tiempo extra, k-means converge muy rápidamente después de la selección de puntos iniciales y por lo tanto este algoritmo reduce el tiempo de cálculo. Los autores probaron su método con conjuntos de datos reales y sintéticos y obtuvieron mejoras de 2-veces en la velocidad, y para ciertos conjuntos de datos, cerca de 1000 veces mejoras en error. En estas simulaciones el nuevo método casi siempre se ejecuta al menos tan bien como vainilla k-means, tanto en la velocidad y como en el error.


Además, los autores calculan una relación de aproximación para su algoritmo. El algoritmo <span class="texhtml " contenteditable="false"><var>k</var></span>-means++ garantiza una relación de aproximación O (log k) a la espera (más de la aleatoriedad del algoritmo), donde k es el número de grupos utilizados. Esto está en contraste con vainilla k-means, el cual puede generar grupos arbitrariamente peor que la solución óptima.<ref name="kanungo">T. Kanungo, D. Mount, N. Netanyahux, C. Piatko, R. Silverman, A. Wu [http://www.cs.umd.edu/~mount/Papers/kmlocal.pdf "A Local Search Approximation Algorithm for ''k''-Means Clustering"] 2004 Computational Geometry: Theory and Applications.</ref>
Además, los autores calculan una relación de aproximación para su algoritmo. El algoritmo <span class="texhtml "><var>k</var></span>-means++ garantiza una relación de aproximación O (log k) a la espera (más de la aleatoriedad del algoritmo), donde k es el número de grupos utilizados. Esto está en contraste con vainilla k-means, el cual puede generar grupos arbitrariamente peor que la solución óptima.<ref name="kanungo">T. Kanungo, D. Mount, N. Netanyahux, C. Piatko, R. Silverman, A. Wu [http://www.cs.umd.edu/~mount/Papers/kmlocal.pdf "A Local Search Approximation Algorithm for ''k''-Means Clustering"] {{Wayback|url=http://www.cs.umd.edu/~mount/Papers/kmlocal.pdf |date=20060209181757 }} 2004 Computational Geometry: Theory and Applications.</ref>


== Ejemplo caso peor ==
== Ejemplo caso peor ==
Para ilustrar el potencial del algoritmo de k-means para agrupar arbitrariamente mal (con respecto a la función objetivo de minimizar la suma de las distancias al cuadrado de los puntos al centroide de sus grupos), considere el ejemplo de cuatro puntos en '''R'''<sup>2</sup> que forman un rectángulo cuya anchura es mayor que su altura.
Para ilustrar el potencial del algoritmo de k-means para agrupar arbitrariamente mal (con respecto a la función objetivo de minimizar la suma de las distancias al cuadrado de los puntos al [[centroide]] de sus grupos), considere el ejemplo de cuatro puntos en '''R'''<sup>2</sup> que forman un rectángulo cuya anchura es mayor que su altura.


Si k = 2 y los dos centros iniciales de conjuntos se encuentran en los puntos medios de los segmentos de línea superior e inferior del rectángulo formado por los cuatro puntos, el algoritmo k-means converge inmediatamente, sin mover estos centros de los conjuntos. En consecuencia, los dos puntos de fondo se agrupan juntos y los dos puntos que forman la parte superior del rectángulo se agrupan juntos, un agrupamiento subóptimo debido a que la anchura del rectángulo es mayor que su altura.<span class="cx-segment" data-segmentid="61"></span>
Si k = 2 y los dos centros iniciales de conjuntos se encuentran en los puntos medios de los segmentos de línea superior e inferior del rectángulo formado por los cuatro puntos, el algoritmo k-means converge inmediatamente, sin mover estos centros de los conjuntos. En consecuencia, los dos puntos de fondo se agrupan juntos y los dos puntos que forman la parte superior del rectángulo se agrupan juntos, un agrupamiento subóptimo debido a que la anchura del rectángulo es mayor que su altura.


Ahora, considera extender el rectángulo horizontalmente a un ancho arbitrario. El algoritmo k-means estándar continuará a agrupar los puntos suboptimalmente, y por incrementar la distancia horizontal entre los dos puntos en cada grupo, podemos hacer que el algoritmo agrupe arbitrariamente mal con respecto a la función objetivo del k-means
Ahora, considera extender el rectángulo horizontalmente a un ancho arbitrario. El algoritmo k-means estándar continuará a agrupar los puntos suboptimalmente, y por incrementar la distancia horizontal entre los dos puntos en cada grupo, podemos hacer que el algoritmo agrupe arbitrariamente mal con respecto a la función objetivo del k-means


== Aplicaciones ==
== Aplicaciones ==
El enfoque de k-means++ se ha aplicado desde su propuesta inicial. En una revisión por Shindler<ref>http://web.archive.org/web/20110927100642/http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf Approximation Algorithms for the Metric ''k''-Median
El enfoque de k-means++ se ha aplicado desde su propuesta inicial. En una revisión por Shindler<ref>https://web.archive.org/web/20110927100642/http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf Approximation Algorithms for the Metric ''k''-Median
Problem</ref> que incluye muchos tipos de algoritmos de agrupamiento, el método se dice que supera con éxito algunos de los problemas asociados con otras formas de definir centros iniciales de conjuntos para k-means clustering. Lee et al.<ref>http://sir-lab.usc.edu/publications/2008-ICWSM2LEES.pdf Discovering Relationships among Tags and Geotags, 2007</ref> Informe de una aplicación de k-means++ para crear grupos geográficos de fotografías sobre la base de la información de latitud y longitud unido a las fotos. Una aplicación para la diversificación económica es reportado por Howard y Johansen<ref>http://www.cse.ohio-state.edu/~johansek/clustering.pdf Clustering Techniques for Financial Diversification, March 2009</ref> Otro tipo de apoyo para el método y en curso de discusión también está disponible en línea<ref>http://lingpipe-blog.com/2009/03/23/arthur-vassilvitskii-2007-kmeans-the-advantages-of-careful-seeding/ Lingpipe Blog</ref> dado que la inicialización de k-means++ necesita k pasadas por encima de los datos no se escala muy bien a conjuntos grandes de datos Bahman Bahmani et al. ha propuesto una variante escalable de k-means++ llamada k-means || que ofrece las mismas garantías teóricas y sin embargo es altamente escalable.<ref name="kmeans||">B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii [http://vldb.org/pvldb/vol5/p622_bahmanbahmani_vldb2012.pdf "Scalable K-means++"] 2012 Proceedings of the VLDB Endowment.</ref>
Problem</ref> que incluye muchos tipos de [[Algoritmo de agrupamiento|algoritmos de agrupamiento]], el método se dice que supera con éxito algunos de los problemas asociados con otras formas de definir centros iniciales de conjuntos para k-means clustering. Lee et al.<ref>http://sir-lab.usc.edu/publications/2008-ICWSM2LEES.pdf {{Wayback|url=http://sir-lab.usc.edu/publications/2008-ICWSM2LEES.pdf |date=20160303223350 }} Discovering Relationships among Tags and Geotags, 2007</ref> Informe de una aplicación de k-means++ para crear grupos geográficos de fotografías sobre la base de la información de latitud y longitud unido a las fotos. Una aplicación para la diversificación económica es reportado por Howard y Johansen<ref>{{enlace roto|1=http://www.cse.ohio-state.edu/~johansek/clustering.pdf |2=http://www.cse.ohio-state.edu/~johansek/clustering.pdf |bot=InternetArchiveBot }} Clustering Techniques for Financial Diversification, March 2009</ref> Otro tipo de apoyo para el método y en curso de discusión también está disponible en línea<ref>http://lingpipe-blog.com/2009/03/23/arthur-vassilvitskii-2007-kmeans-the-advantages-of-careful-seeding/ Lingpipe Blog</ref> dado que la inicialización de k-means++ necesita k pasadas por encima de los datos no se escala muy bien a conjuntos grandes de datos Bahman Bahmani et al. ha propuesto una variante escalable de k-means++ llamada k-means || que ofrece las mismas garantías teóricas y sin embargo es altamente escalable.<ref name="kmeans||">B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii [http://vldb.org/pvldb/vol5/p622_bahmanbahmani_vldb2012.pdf "Scalable K-means++"] 2012 Proceedings of the VLDB Endowment.</ref>


== Software ==
== Software ==
* Scikit-learn tiene un K-means que usa k-means++ por defecto.
* [[Scikit-learn]] tiene un K-means que usa k-means++ por defecto.
* ELKI minería de datos contiene múltiples variaciones de k-means, incluyendo k-means++ para inicialización.
* ELKI minería de datos contiene múltiples variaciones de k-means, incluyendo k-means++ para inicialización.
* [[R (lenguaje de programación)|GNU R i]]<nowiki/>ncluye k-means, y el paquete "flexclust" puede hacer k-means++.
* [[R (lenguaje de programación)|GNU R i]]<nowiki/>ncluye k-means, y el paquete "flexclust" puede hacer k-means++.
* [[OpenCV]], [http://docs.opencv.org/modules/core/doc/clustering.html#kmeans implementación]
* [[OpenCV]], [http://docs.opencv.org/modules/core/doc/clustering.html#kmeans implementación]
* [[Weka (aprendizaje automático)|Weka]] contiene k-means (con k-means++ opcional) y x-means clustering.
* [[Weka (aprendizaje automático)|Weka]] contiene k-means (con k-means++ opcional) y x-means clustering.
* La implementación de [http://www.stanford.edu/~darthur/kmpp.zip David Arthur's] <sup class="noprint Inline-Template" contenteditable="false">&#x5B;''[[Ayuda:Cómo recuperar un enlace roto|<span title=" since May 2013">dead link</span>]]''&#x5D;</sup>
* La implementación de [{{Enlace roto|1=http://www.stanford.edu/~darthur/kmpp.zip |2=http://www.stanford.edu/~darthur/kmpp.zip |bot=InternetArchiveBot }} David Arthur's] <sup class="noprint Inline-Template">&#x5B;''[[Ayuda:Cómo recuperar un enlace roto|<span title=" since May 2013">dead link</span>]]''&#x5D;</sup>
* [http://commons.apache.org/proper/commons-math/javadocs/api-3.3/org/apache/commons/math3/ml/clustering/KMeansPlusPlusClusterer.html La implementación de Apache Commons Math Java<br> ]
* [http://commons.apache.org/proper/commons-math/javadocs/api-3.3/org/apache/commons/math3/ml/clustering/KMeansPlusPlusClusterer.html La implementación de Apache Commons Math Java ] {{Wayback|url=http://commons.apache.org/proper/commons-math/javadocs/api-3.3/org/apache/commons/math3/ml/clustering/KMeansPlusPlusClusterer.html |date=20160304050233 }}
* [http://docs.graphlab.org/clustering.html CMU's GraphLab] eficiente, la agrupación de código abierto en multinúcleo
* [{{enlace roto|1=https://web.archive.org/web/20141203225249/http://docs.graphlab.org/clustering.html |2=https://web.archive.org/web/20141203225249/http://docs.graphlab.org/clustering.html |bot=InternetArchiveBot }} CMU's GraphLab] eficiente, la agrupación de código abierto en multinúcleo


== Referencias ==
== Referencias ==
{{listaref}}
<div data-template-mapping="{&quot;targetname&quot;:&quot;Reflist&quot;}" class="reflist" style="list-style-type: decimal;">
<div data-template-mapping="{"targetname":"Reflist"}" class="reflist" style="list-style-type: decimal;">
<references></references></div>
</div>


{{Control de autoridades}}
[[Categoría:Algoritmos]]
[[Categoría:Algoritmos]]

Revisión actual - 04:26 11 jul 2024

En minería de datos, k-means++[1]​[2]​ es un algoritmo que se utiliza para la selección de los valores iniciales (o "semillas") en el algoritmo k-means clustering. Fue propuesto en 2007 por David Arthur y Sergei Vassilvitskii, como un algoritmo de aproximación para el problema NP-duro k-means—una forma de evitar los agrupamientos pobres a veces encontrados por el algoritmo k-means estándar. Es similar al primero de tres métodos para encontrar semillas propuestos, en 2006,[3]​ por Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy. (La distribución de la primera semilla es diferente).

Base

[editar]

El problema k-means consiste en encontrar grupos de puntos tal que se minimice la varianza intra-grupo, es decir, minimizar la suma de las distancias al cuadrado de cada punto al centro más cercano a él. Aunque la búsqueda de una solución exacta al problema de k-means para una entrada arbitraria es NP-duro,[4]​ el enfoque estándar de encontrar una solución aproximada (a menudo llamado el algoritmo de Lloyd o el algoritmo k-means) es utilizado ampliamente y con frecuencia encuentra soluciones razonables rápidamente.

Sin embargo, el algoritmo k-means tiene por lo menos dos grandes deficiencias teóricas:

  • Primero, ha sido mostrado que, en el caso peor, el tiempo de corrida del algoritmo es súper-polinomial en el tamaño de la entrada.[5]​
  • Segundo, la aproximación encontrada puede ser arbitrariamente mala con respecto a la función objetivo comparado al agrupamiento óptimo.

El algoritmo k-means++ aborda la segunda de estas deficiencias mediante la especificación de un procedimiento para inicializar los centros de los conjuntos antes de proceder con las k-means iteraciones de optimización estándar . Con la inicialización de k-means++ , el algoritmo está garantizado para encontrar una solución que es O (log k) competitiva a la solución óptima de k-means.

Algoritmo de inicialización

[editar]

La intuición detrás de este enfoque es que la expansión de los k iniciales centros de conjuntos es una buena idea: el primer centro de conjunto se obtiene con una variable aleatoria uniforme desde los puntos que están agrupados, después de esto cada centro de grupo siguiente se elige desde el resto de los puntos con probabilidad proporcional a su distancia al cuadrado desde del centro de conjunto existente más cercano del punto.

El algoritmo exacto es como sigue:

  1. Escoger un centro de entre los puntos de datos utilizando una variable aleatoria uniforme.
  2. Para cada punto x, calcular D(x), que es la distancia entre x y el centro más cercano que ya ha sido seleccionado.
  3. Escoger un nuevo punto al azar (con variable aleatoria uniforme) como nuevo centro, utilizando una distribución de probabilidad ponderada donde un punto x es escogido con la probabilidad proporcional a D(x)2.
  4. Repetir paso 2 y 3 hasta que se hayan seleccionado k centros.
  5. Ahora que los centros iniciales han sido elegidos, continuar utilizando k-means clustering estándar.

Este método produce una mejora considerable en el error final de k-means. Aunque la selección inicial en el algoritmo toma tiempo extra, k-means converge muy rápidamente después de la selección de puntos iniciales y por lo tanto este algoritmo reduce el tiempo de cálculo. Los autores probaron su método con conjuntos de datos reales y sintéticos y obtuvieron mejoras de 2-veces en la velocidad, y para ciertos conjuntos de datos, cerca de 1000 veces mejoras en error. En estas simulaciones el nuevo método casi siempre se ejecuta al menos tan bien como vainilla k-means, tanto en la velocidad y como en el error.

Además, los autores calculan una relación de aproximación para su algoritmo. El algoritmo k-means++ garantiza una relación de aproximación O (log k) a la espera (más de la aleatoriedad del algoritmo), donde k es el número de grupos utilizados. Esto está en contraste con vainilla k-means, el cual puede generar grupos arbitrariamente peor que la solución óptima.[6]​

Ejemplo caso peor

[editar]

Para ilustrar el potencial del algoritmo de k-means para agrupar arbitrariamente mal (con respecto a la función objetivo de minimizar la suma de las distancias al cuadrado de los puntos al centroide de sus grupos), considere el ejemplo de cuatro puntos en R2 que forman un rectángulo cuya anchura es mayor que su altura.

Si k = 2 y los dos centros iniciales de conjuntos se encuentran en los puntos medios de los segmentos de línea superior e inferior del rectángulo formado por los cuatro puntos, el algoritmo k-means converge inmediatamente, sin mover estos centros de los conjuntos. En consecuencia, los dos puntos de fondo se agrupan juntos y los dos puntos que forman la parte superior del rectángulo se agrupan juntos, un agrupamiento subóptimo debido a que la anchura del rectángulo es mayor que su altura.

Ahora, considera extender el rectángulo horizontalmente a un ancho arbitrario. El algoritmo k-means estándar continuará a agrupar los puntos suboptimalmente, y por incrementar la distancia horizontal entre los dos puntos en cada grupo, podemos hacer que el algoritmo agrupe arbitrariamente mal con respecto a la función objetivo del k-means

Aplicaciones

[editar]

El enfoque de k-means++ se ha aplicado desde su propuesta inicial. En una revisión por Shindler[7]​ que incluye muchos tipos de algoritmos de agrupamiento, el método se dice que supera con éxito algunos de los problemas asociados con otras formas de definir centros iniciales de conjuntos para k-means clustering. Lee et al.[8]​ Informe de una aplicación de k-means++ para crear grupos geográficos de fotografías sobre la base de la información de latitud y longitud unido a las fotos. Una aplicación para la diversificación económica es reportado por Howard y Johansen[9]​ Otro tipo de apoyo para el método y en curso de discusión también está disponible en línea[10]​ dado que la inicialización de k-means++ necesita k pasadas por encima de los datos no se escala muy bien a conjuntos grandes de datos Bahman Bahmani et al. ha propuesto una variante escalable de k-means++ llamada k-means || que ofrece las mismas garantías teóricas y sin embargo es altamente escalable.[11]​

Software

[editar]

Referencias

[editar]
  1. ↑ Arthur, D. and Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding" Archivado el 21 de agosto de 2017 en Wayback Machine. (PDF).
  2. ↑ http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Slides for presentation of method by Arthur, D. and Vassilvitskii, S.
  3. ↑ Ostrovsky, R., Rabani, Y., Schulman, L. J. and Swamy, C. (2006).
  4. ↑ Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V. (2004).
  5. ↑ Arthur, D. and Vassilvitskii, S. (2006), "How slow is the k-means method?"
  6. ↑ T. Kanungo, D. Mount, N. Netanyahux, C. Piatko, R. Silverman, A. Wu "A Local Search Approximation Algorithm for k-Means Clustering" Archivado el 9 de febrero de 2006 en Wayback Machine. 2004 Computational Geometry: Theory and Applications.
  7. ↑ https://web.archive.org/web/20110927100642/http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf Approximation Algorithms for the Metric k-Median Problem
  8. ↑ http://sir-lab.usc.edu/publications/2008-ICWSM2LEES.pdf Archivado el 3 de marzo de 2016 en Wayback Machine. Discovering Relationships among Tags and Geotags, 2007
  9. ↑ http://www.cse.ohio-state.edu/~johansek/clustering.pdf (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). Clustering Techniques for Financial Diversification, March 2009
  10. ↑ http://lingpipe-blog.com/2009/03/23/arthur-vassilvitskii-2007-kmeans-the-advantages-of-careful-seeding/ Lingpipe Blog
  11. ↑ B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii "Scalable K-means++" 2012 Proceedings of the VLDB Endowment.
Obtenido de «https://es.wikipedia.org/eswiki/w/index.php?title=K-means%2B%2B&oldid=161243415»