El algoritmo KMeans y el problema de los centroides iniciales

==1 Introducción==

El big data está inmerso hoy en día en las áreas de investigación de las distintas ramas de las matemáticas aplicadas, es un tema relevante de investigación actual. Sin embargo, abordar o estudiar conjuntos de datos inmensos con técnicas computacionales en forma secuencial e incluso con hardware especializado, ya no es un camino viable. Es por eso que en las distintas áreas de la matemática aplicada surge el problema de cómo obtener información relevante en las distintas bases de datos que se tengan del estudio de algún fenómeno o problema a estudiar. Uno de ellos es el problema de agrupamiento de datos cuya solución resuelve e incentiva a la mejora en la toma de decisiones dando una metodología de clasificación de ellos.

El problema puede ser tratado utilizando computadoras personales con recursos computacionales rápidos y eficientes que obtienen buenos resultados. Sin embargo, este problema demanda alto desempeño al recurso físico (hardware), por medio de lógica computacional escrita en diversos lenguajes de programación de alto nivel, generando así altas demandas de procesamiento y por tanto es necesario disponer de una capacidad de cómputo mayor. Este poder de cómputo lo puede ofrecer un arreglo de PCs interconectadas bajo una red de área local. A este tipo de interconexión de computadoras se le conoce como Cluster de PCs (computadoras personales interconectadas para obtener un comportamiento único). Un tipo de estos clusters de PCs son los llamados cluster beowulf diseñados para cálculo numérico intensivo.

El agrupamiento de estos datos (clustering) es una metodología ampliamente utilizada, que resuelve los problemas antes mencionados. Entre los algoritmos de clustering más simples y fáciles de implementar computacionalmente está el llamado KMeans. Es uno de los algoritmos de Machine Learning no supervisados más utilizados por la Ciencia de Datos y que además es muy fácil de usar como de interpretar. Su objetivo es agrupar observaciones similares para descubrir patrones que a simple vista se desconocen. Para conseguirlo, el algoritmo busca un número fijo (<math display="inline">k</math>) de clusters en una base de datos. Sin embargo, las aplicaciones del mundo real producen grandes volúmenes de datos, por lo tanto, el cómo tratar con estas grandes cantidades de datos el problema de agrupamiento es un problema significativo y desafiante

Una metodología para trabajar con altas prestaciones de datos, escalabilidad y portabilidad es Apache Spark, ideal para interconectar PCs y que unidas trabajen en un mismo problema. Por lo tanto, con la unión de Apache Spark y el algoritmo KMeans, se puede abordar el problema de agrupamiento de datos, que es el tema inicial en este trabajo que aún se encuentra en desarrollo y una primera etapa en él es comenzar por estudiar el algoritmo KMeans.

==2 Preliminares==

En esta sección se presenta el algoritmo KMeans. Se describe la idea general del algoritmo por medio de una descripción textual y puntualizando los conceptos de centroide y métrica utilizada. Esto hace evidente la idea geométrica detrás del algoritmo KMeans y que se describe por medio de los diagramas de Voronoi y la envoltura convexa.

===2.1 El algoritmo===

El algoritmo KMeans es uno de los más simples y conocidos algoritmos de agrupamiento. Utiliza una forma fácil y sencilla para dividir un conjunto de datos en <math display="inline">k</math> grupos (<math display="inline">k</math> fijado de antemano)<span id='citeF-1'></span>[[#cite-1|[1]]]. El método se basa en la idea de que los elementos de un cluster están agrupados alrededor de un centro o centroide geométrico. La tarea entonces es encontrar dichos centroides. Para ello se definen <math display="inline">k</math> centroides iniciales, luego se toma cada punto del conjunto de datos y se sitúa en la clase del centroide más cercano. El paso siguiente consiste en recalcular el centroide de cada grupo y volver a distribuir todos los objetos según el centroide más cercano <span id='citeF-2'></span><span id='citeF-1'></span>[[#cite-2|[2,1]]]. El proceso se repite una y otra vez hasta que ya no haya cambio en los grupos de un paso al siguiente.

Conviene puntualizar lo que se entiende por un centroide y que el criterio de cercanía está basado en la distancia euclidiana, a menos que se señale otra cosa <span id='citeF-1'></span><span id='citeF-3'></span>[[#cite-1|[1,3]]]. La idea más importante es que a cada grupo se le puede asignar un centroide, que corresponde al promedio de los datos de cada grupo. A continuación se presenta la definición de centroide.

Definición 1: El centro o centroide de una clase <math display="inline">\pi _{i}</math> se define como:

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>  c_{i}=\frac{1}{n_{i}}\sum \limits _{v\in \pi _{i}}a_{v} </math>
|}
|}

donde <math display="inline">n_{i}</math> es el número de elementos de la clase <math display="inline">\pi _{i}=\{ v|a_{v} \;\mbox{pertenece al grupo i} \} </math>.

Otro concepto a tomar en cuenta es la métrica, con ella se determina si un punto del conjunto de datos está más próximo a uno de los centroides, en tal caso ese punto pertenecerá al grupo de dicho centroide, la métrica utilizada para este trabajo es la euclidiana que se define de la manera siguiente<span id='citeF-2'></span>[[#cite-2|[2]]].

Definición 2: En el espacio euclidiano la distancia entre dos puntos <math display="inline">X=(x_{1},x_{2},\ldots ,x_{n})</math> y <math display="inline">Y=(y_{1},y_{2},\ldots ,y_{n})</math> se define así:

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math> d_{E}(X,Y)=\sqrt{\sum \limits _{i=1}^{n}(y_{i}-x_{i})^{2}}   </math>
|}
|}

Un ejemplo sencillo de aplicación del algoritmo es el siguiente. Se toma un conjunto de datos en <math display="inline">\mathbb{R}^{2}</math>, en donde a sus coordenadas <math display="inline">(x,y)</math> se les conoce como atributos de los datos (ver Figura [[#img-1|1]]). Para encontrar los centroides, seguimos los pasos siguientes<span id='citeF-1'></span>[[#cite-1|[1]]]:

<ol>

<li>Se escoge <math display="inline">k</math> centroides iniciales de manera arbitraria <math display="inline">(k=4)</math> </li>
<li>Se forman cuatro grupos de la forma siguiente: se toman las distancias de un dato a los <math display="inline">k</math> centroides y ese dato pertenecerá al grupo del centroide más cercano, así se construyen los grupos. </li>
<li>Se toma el promedio de cada grupo y estos serán los centroides siguientes. </li>
<li>Se repiten los pasos 2 y 3 hasta que los centroides ya no cambian. </li>

</ol>

<div id='img-1'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-generapuntosepsconvertedto.png|179px|]]
|[[Image:Review_139704671734-centrosini.png|100px|]]
|[[Image:Review_139704671734-grupo1-4.png|100px|]]
|[[Image:Review_139704671734-grupo2-1.png|100px|]]
|[[Image:Review_139704671734-grupo3-4.png|100px|Ejemplo de conjuntos de puntos en el plano y su proceso de agrupamiento con KMeans. Fuente: Elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="5" | '''Figura 1:''' Ejemplo de conjuntos de puntos en el plano y su proceso de agrupamiento con KMeans. Fuente: Elaboración propia.
|}

Con el ejemplo anterior se ha descrito de una manera simple el funcionamiento del algoritmo KMeans. Ahora se está en condiciones de mostrar el algoritmo, que de acuerdo a la literatura consultada <span id='citeF-1'></span>[[#cite-1|[1]]], está definido de la siguiente manera.

'''Paso 1. Inicialización:''' Se define un conjunto de datos a particionar, el número de grupos y un centroide por cada grupo de forma arbitraria o aleatoria.

'''Paso 2. Clasificación:''' Para cada dato del conjunto, se calcula su distancia a cada centroide, se determina el centroide más cercano, y el conjunto es incorporado al grupo relacionado con ese centroide.

'''Paso 3. Cálculo de centroides:''' Para cada grupo generado en el paso anterior se vuelve a calcular su centroide.

'''Paso 4. Condición de convergencia:''' El algoritmo  converge cuando no existe un intercambio de objetos entre los grupos, si la condición de convergencia no se satisface, se repiten los pasos 2 y 3 del algoritmo.

===2.2 Diagramas de Voronoi===

Definición 3: El diagrama de Voronoi de <math display="inline">P=\{ p_{1},p_{2},\ldots ,p_{n} \} </math>, está formado por todos los puntos <math display="inline">x</math> que equidistan de los dos elementos de <math display="inline">P</math> más cercanos a <math display="inline">x</math>.

En la Figura [[#img-2|2]] se muestran ejemplos de diagramas de Voronoi en el plano: para dos, tres y cuatro puntos, siendo las lineas rojas los diagramas de Voronoi.

<div id='img-2'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-dospuntos.png|100px|]]
|[[Image:Review_139704671734-trespuntos.png|129px|]]
|[[Image:Review_139704671734-cuatropuntos.png|168px|Ejemplos de los diagramas de Voronoi en el plano. Fuente: Elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="3" | '''Figura 2:''' Ejemplos de los diagramas de Voronoi en el plano. Fuente: Elaboración propia.
|}

Cada punto <math display="inline">p_{i} \in P</math> determina una región en el plano, a saber los puntos del plano que están más cerca de <math display="inline">p_{i}</math> que del resto de los puntos de <math display="inline">P</math>; a esto se le conoce como ''Celdas de Voronoi'' y se definen de la manera siguiente.

Definición 4: Sea <math display="inline">p_{i}\in P</math>

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math> V(p_{i})=\{ p| \; d(p,p_{i})\leq d(p,p_{j}),\; p_{j}\in P \}  </math>
|}
|}

===2.3 Envoltura Convexa===

Definición 5: Se llama envoltura convexa de un conjunto dado <math display="inline">X</math> al menor (por inclusión) conjunto convexo que contiene a <math display="inline">X</math> y se define como:

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>conv(X)=\{ tx+(1-t)y|x,y\in X, t\in [0,1] </math>
|}
|}

si <math display="inline">X\subseteq P</math>, y <math display="inline">P</math> es un conjunto convexo, entonces <math display="inline">X \subseteq conv(X) \subseteq P</math>.

Las Figura [[#img-3|3]] representa un ejemplo de envolturas convexas de varios conjuntos de puntos en el plano.

<div id='img-3'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-ejem2puntos.png|112px|]]
|[[Image:Review_139704671734-ejem2convexhull.png|101px|Ejemplos de la cascara convexa de puntos en el plano. Fuente: Elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="2" | '''Figura 3:''' Ejemplos de la cascara convexa de puntos en el plano. Fuente: Elaboración propia.
|}

==3 Objetivos==

===3.1 Objetivo General===

* Estudiar el problema de agrupamiento de datos utilizando el algoritmo KMeans

===3.2 Objetivos Específicos===

* Revisar literatura especializada sobre el algoritmo KMeans.
* Caracterizar el algoritmo KMeans.
* Estudiar la idea geométrica del algoritmo.
* Presentar el marco de trabajo llamado ApacheSpark.

==4 Metodología==

En esta sección se presenta la metodología a utilizar para llevar a cabo este trabajo. Se describe el proceso de la búsqueda de bibliografía y la idea del algoritmo. El algoritmo tiene la característica de ser simple, compacto y fácil de implementar computacionalmente. Sin embargo no está exento de limitaciones, es por eso que se hace la siguiente pregunta ¿Cuando funciona el algoritmo?, y se da una respuesta en base a la idea geométrica del mismo. Así mismo se presenta el marco de trabajo computacional en el cual se basará el trabajo, el llamado Apache Spark.

<div id='img-4'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-MtdGael.png|512px|Metodología de trabajo para el desarrollo de esta investigación. Fuente: Elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figura 4:''' Metodología de trabajo para el desarrollo de esta investigación. Fuente: Elaboración propia.
|}

===4.1 Revisión de la literatura===

La revisión de la literatura para esta investigación se realiza utilizando los motores de búsqueda especializados como Google Académico, Journal of citation of reports (JCR) y otros como Latinindex. La busqueda se realiza mediante los criterios siguientes:

* Frases claves en inglés como ''Unsupervised algorithms'', ''kmeans aplications''. ''paralel kmeans''.
* Análisis de la información centrado en las algoritmos no supervisados de tipo particionales, enfocándose en aspectos tales como: (i) geometrías, (ii) centroides iniciales y (iii) posibles aplicaciones.
* Se indagó sobre el problema de agrupamiento poco estudiadas como lo son los algoritmos en paralelo y algoritmos robustos.

===4.2 La idea del KMeans===

El problema es encontrar grupos en un conjunto de datos. Una pregunta que surge de manera natural es la siguiente: ¿Cómo encontrar grupos en un conjunto de datos óptimos de manera automatizada? Veámoslo por medio de un ejemplo.

Tenemos un conjunto de datos (Tabla [[#table-1|1]]), cada dato se representa como un punto en el plano cartesiano con coordenadas <math display="inline">(x,y)</math>, y lo que se quiere realizar con dicho conjunto de datos, es encontrar grupos de manera automatizada.


{|  class="floating_tableSCP wikitable" style="text-align: center; margin: 1em auto;min-width:50%;"
|+ style="font-size: 75%;" |<span id='table-1'></span>Tabla. 1 Representación de los datos en coordenadas <math>(x,y)</math>.
|- style="border-bottom: 2px solid;"
| style="border-right: 2px solid;" |   x 
| style="border-left: 2px solid;" |  1   
|  2   
|  2   
|  3   
|  3   
|  3 
|  2 
|  3 
|  3 
|  3 
|  4 
|  4 
|  4 
|  5 
|  6 
|  6 
|  6 
|  7 
|  7 
|  8 
|  8 
|  8 
|  9 
|  9 
|  10
|- style="border-top: 2px solid;"
| style="border-right: 2px solid;" |   y  
| style="border-left: 2px solid;" |  2.5 
|  2.3 
|  1.5 
|  2.5 
|  3.5 
|  7 
|  6 
|  7 
|  8 
|  6 
|  6 
|  8 
|  7 
|  2 
|  3 
|  4 
|  2.5 
|  3.5 
|  6 
|  7 
|  8 
|  6.5 
|  7.5 
|  7 
|  7  
|}

La representación de los puntos de la Tabla [[#table-1|1]] en el plano cartesiano es la siguiente:

<div id='img-5'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-generapuntos.png|224px|Representación gráfica del conjunto de datos en el plano de la forma (x,y) de la Tabla [[#table-1|1]].]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figura 5:''' Representación gráfica del conjunto de datos en el plano de la forma <math>(x,y)</math> de la Tabla [[#table-1|1]].
|}

En la Figura [[#img-5|5]] es fácil localizar visualmente cuatro grupos. Sin embargo, aún en dos dimensiones no siempre está claro cuántos cluster hay y cómo se agrupan los datos. Por ejemplo, del siguiente conjunto de datos, se requiere encontrar los grupos asociados a ellos.

<div id='img-6'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-Datos2D.png|153px|Conjunto de datos a agrupar.]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figura 6:''' Conjunto de datos a agrupar.
|}

De la Figura [[#img-6|6]], se pueden citar aquí cuatro opciones distintas de agrupar los datos que se observan a continuación:

<div id='img-7'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-Datos2D-1.png|115px|]]
|[[Image:Review_139704671734-Datos2D-2.png|115px|]]
|[[Image:Review_139704671734-Datos2D-3.png|115px|]]
|[[Image:Review_139704671734-Datos2D-4.png|115px|Distintos agrupamientos.]]
|- style="text-align: center; font-size: 75%;"
| colspan="4" | '''Figura 7:''' Distintos agrupamientos.
|}

Para problemas de mayor dimensión, encontrar grupos se vuelve mucho más complicado, porque no podemos apoyarnos de la parte visual, como en los casos de dos dimensiones <math display="inline">\mathbb{R}^{2}</math> y en los de tres dimensiones <math display="inline">\mathbb{R}^{3}</math>.

===4.3 Ejemplo===

En el artículo <span id='citeF-3'></span>[[#cite-3|[3]]] se plantea un ejemplo numérico del algoritmo, veamos este ejemplo. Se supone en él que se tienen cuatro tipos de medicamentos con dos atributos cada uno a saber (Peso e Índice PH) como se muestra en la tabla siguiente:


{|  class="floating_tableSCP wikitable" style="text-align: center; margin: 1em auto;min-width:50%;"
|- style="border-top: 2px solid;"
|  Medicina 
| Peso 
| Índice PH  
|- style="border-top: 2px solid;"
|  A 
| 1 
| 1 
|-
| B 
| 2 
| 1 
|-
| C 
| 4 
| 3 
|-
| D 
| 5 
| 4 
|}

Se quieren encontrar dos grupos basados en los dos atributos de los datos. Cada medicamento puede ser representado como un punto en el plano cartesiano de la manera siguiente:

<div id='img-8'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-medicamentos.png|224px|Representación gráfica de los atributos de los medicamentos en R². Fuente Elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figura 8:''' Representación gráfica de los atributos de los medicamentos en <math>\mathbb{R}^{2}</math>. Fuente Elaboración propia.
|}

==Iteración 1==

Se elige el número de grupos que se desea encontrar, es decir el valor del número <math display="inline">k</math>, en este caso <math display="inline">k=2</math>. Se seleccionan dos centroides iniciales, que en este caso serán los primeros dos medicamentos, es decir:

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>c_{1}=(1,1) \qquad \qquad c_{2}(2,1)</math>
|}
|}

<div id='img-9'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-mediciniciales.png|224px|Elección de los centroides iniciales, en este caso son los primeros dos medicamentos que están coloreados de color rojo. Fuente: Elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figura 9:''' Elección de los centroides iniciales, en este caso son los primeros dos medicamentos que están coloreados de color rojo. Fuente: Elaboración propia.
|}

Para encontrar los grupos se calcula las distancias de los datos a los centroides <math display="inline">c_{1}</math> y <math display="inline">c_{2}</math>, tomando la distancia mínima para asignarlos al centroide más cercano.


{|  class="floating_tableSCP wikitable" style="text-align: left; margin: 1em auto;min-width:50%;"
|+ style="font-size: 75%;" |<span id='table-2'></span>Tabla. 2 
|-
| style="border-right: 2px solid;" | 
| style="border-left: 2px solid;" | <math>c_{1}</math>
| <math>c_{2}</math>
|- style="border-top: 2px solid;"
| style="border-right: 2px solid;" |     A 
| style="border-left: 2px solid;" | 0       
| 1    
|-
| style="border-right: 2px solid;" | B 
| style="border-left: 2px solid;" | 1       
| 0    
|-
| style="border-right: 2px solid;" | C 
| style="border-left: 2px solid;" | 3.61    
| 2.83  
|-
| style="border-right: 2px solid;" | D 
| style="border-left: 2px solid;" | 5       
| 4.24    
|}

Los nuevos grupos son <math display="inline">G_{1}=\{ A \} </math> y <math display="inline">G_{2}=\{ B,\; C,\; D \} </math>

==Iteración 2==

En el grupo 1 solo se tiene a un miembro, el centroide de ese grupo será nuevamente

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>c_{1}=(1,1)</math>
|}
|}

Mientras en el grupo 2, se tienen tres miembros que son <math display="inline">B(2,1)</math>, <math display="inline">C(4,3)</math>, <math display="inline">D(5,4)</math>

Para calcular <math display="inline">c_{2}</math> lo hacemos de la manera siguiente

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>c_{2}=\left(\frac{2+4+5}{3},\frac{1+3+4}{3}\right)=\left(\frac{11}{3},\frac{8}{3}\right)</math>
|}
|}

Por lo tanto los nuevos centroides son: <math display="inline">c_{1}=(1,1)</math> y <math display="inline">c_{2}=(\frac{11}{3},\frac{8}{3})</math>

<div id='img-10'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-medic1itera.png|224px|Calcular los nuevos centroides c₁ y c₂ calculando la distancia de ellos a todos los datos y en base a la distancia mínima. Fuente: Elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figura 10:''' Calcular los nuevos centroides <math>c_{1}</math> y <math>c_{2}</math> calculando la distancia de ellos a todos los datos y en base a la distancia mínima. Fuente: Elaboración propia.
|}

Se vuelven a encontrar nuevos grupos calculando las distancias de los datos a los centroides <math display="inline">c_{1}</math> y <math display="inline">c_{2}</math>


{|  class="floating_tableSCP wikitable" style="text-align: left; margin: 1em auto;min-width:50%;"
|-
| style="border-right: 2px solid;" | 
| style="border-left: 2px solid;" | <math>c_{1}</math>
| <math>c_{2}</math>
|- style="border-top: 2px solid;"
| style="border-right: 2px solid;" |     A 
| style="border-left: 2px solid;" | 0       
| 3.14    
|-
| style="border-right: 2px solid;" | B 
| style="border-left: 2px solid;" | 1       
| 2.36    
|-
| style="border-right: 2px solid;" | C 
| style="border-left: 2px solid;" | 3.61    
| 0.47  
|-
| style="border-right: 2px solid;" | D 
| style="border-left: 2px solid;" | 5       
| 1.89    
|}

Los nuevos grupos son <math display="inline">G_{1}=\{ A,\; B \} </math> y <math display="inline">G_{2}=\{ C,\; D \} </math>

==Iteración 3==

El grupo 1 tiene como miembros <math display="inline">A=(1,1)</math>, <math display="inline">B=(2,1)</math>

Para calcular <math display="inline">c_{1}</math> lo hacemos de la manera siguiente

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>c_{1}=\left(\frac{1+2}{2},\frac{1+1}{2}\right)=\left(\frac{3}{2},1\right)</math>
|}
|}

El grupo 2 tiene dos miembros que son <math display="inline">C=(4,3)</math>, <math display="inline">D=(5,4)</math>

Para calcular <math display="inline">c_{2}</math> lo hacemos de la manera siguiente

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>c_{2}=\left(\frac{4+5}{2},\frac{3+4}{2}\right)=\left(\frac{9}{2},\frac{7}{2}\right)</math>
|}
|}

Por lo tanto, los nuevos centroides son: <math display="inline">c_{1}=\left(\frac{3}{2},1\right)</math> y <math display="inline">c_{2}=\left(\frac{9}{2},\frac{7}{2}\right)</math>

<div id='img-11'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-medic2itera.png|224px|Elección de los nuevos centroides en base al procedimiento basado en la Iteración 2. Fuente: Elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figura 11:''' Elección de los nuevos centroides en base al procedimiento basado en la Iteración 2. Fuente: Elaboración propia.
|}

Se vuelve a encontrar nuevos grupos calculando las distancias de los datos a los centroides <math display="inline">c_{1}</math> y <math display="inline">c_{2}</math>


{|  class="floating_tableSCP wikitable" style="text-align: left; margin: 1em auto;min-width:50%;"
|-
| style="border-right: 2px solid;" | 
| style="border-left: 2px solid;" | <math>c_{1}</math>
| <math>c_{2}</math>
|- style="border-top: 2px solid;"
| style="border-right: 2px solid;" |     A 
| style="border-left: 2px solid;" | 0.5     
| 4.30    
|-
| style="border-right: 2px solid;" | B 
| style="border-left: 2px solid;" | 0.5      
| 3.54    
|-
| style="border-right: 2px solid;" | C 
| style="border-left: 2px solid;" | 3.20    
| 0.71    
|-
| style="border-right: 2px solid;" | D 
| style="border-left: 2px solid;" | 4.61    
| 0.71    
|}

Nuevos grupos <math display="inline">G_{1}=\{ A,\; B \} </math> y <math display="inline">G_{2}=\{ C,\; D \} </math>

Es fácil ver que en el paso siguiente los centroides no cambian, por lo tanto tampoco los grupos, de tal forma que el proceso termina.


{|  class="floating_tableSCP wikitable" style="text-align: center; margin: 1em auto;min-width:50%;"
|- style="border-top: 2px solid;"
| style="border-right: 2px solid;" |     Medicina 
| style="border-left: 2px solid;" | Peso 
| style="border-right: 2px solid;" | Índice PH 
| style="border-left: 2px solid;" | Grupo 
|- style="border-top: 2px solid;"
| style="border-right: 2px solid;" |     A 
| style="border-left: 2px solid;" | 1 
| style="border-right: 2px solid;" | 1 
| style="border-left: 2px solid;" | 1 
|-
| style="border-right: 2px solid;" | B 
| style="border-left: 2px solid;" | 2 
| style="border-right: 2px solid;" | 1 
| style="border-left: 2px solid;" | 1
|-
| style="border-right: 2px solid;" | C 
| style="border-left: 2px solid;" | 4 
| style="border-right: 2px solid;" | 3 
| style="border-left: 2px solid;" | 2
|-
| style="border-right: 2px solid;" | D 
| style="border-left: 2px solid;" | 5 
| style="border-right: 2px solid;" | 4 
| style="border-left: 2px solid;" | 2    
|}

Los medicamentos <math display="inline">A</math> y <math display="inline">B</math> difieren en una unidad en la propiedad de peso, mientras que en la propiedad del índice PH son iguales, por esa razón son muy parecidos y el algoritmo KMeans los clasifica en un mismo grupo, mientras que los medicamentos <math display="inline">C</math> y <math display="inline">D</math> difieren en una unidad en ambas propiedades, quedando así en el segundo grupo. Como puede observarse los medicamentos con características similares pertenecen al mismo grupo.

Con el ejemplo se ha mostrado el funcionamiento del algoritmo KMeans, en donde cada medicamento se representa como un punto en el plano <math display="inline">\mathbb{R}^{2}</math>. Se pudo graficar cada dato debido a la naturaleza de los mismos. En el caso en donde los datos son de mayor dimensión, esa representación visual no puede auxiliarnos, esto no es un impedimento ya que el algoritmo puede realizar agrupamientos en cualquier dimensión.

===4.4 ¿Cuándo funciona?===

Se presentó la idea del algoritmo KMeans, su definición y se mostró un ejemplo de como se utiliza, para encontrar grupos de conjuntos de datos. KMeans encuentra buenos agrupamientos y malos agrupamientos también, la cuestión es ¿Cuándo hace buenos agrupamientos?

A continuación se presenta un ejemplo donde el algoritmo hace un buen agrupamiento y otro ejemplo donde hace un mal agrupamiento.

<div id='img-12'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-buenagrup2grp.png|115px|]]
|[[Image:Review_139704671734-dona1agrupada.png|134px|Ejemplos en R² donde el algoritmo KMeans agrupa bien y otro ejemplo donde agrupa mal. Fuente: elaboración propia.]]
|- style="text-align: center; font-size: 75%;"
| colspan="2" | '''Figura 12:''' Ejemplos en <math>\mathbb{R}^{2}</math> donde el algoritmo KMeans agrupa bien y otro ejemplo donde agrupa mal. Fuente: elaboración propia.
|}

En el caso del buen agrupamiento ver Figura [[#img-12|12]] es posible trazar una línea recta que divide al plano por regiones, cada una de estas regiones contendrá a uno de los grupos. Por lo contrario, no será posible trazar una línea recta con las características mencionadas. Esta es una característica relevante para dar respuesta a esta cuestión.

<div id='img-13a'></div>
<div id='img-13b'></div>
<div id='img-13'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-buenagrup2grp.png|115px|]]
|[[Image:Review_139704671734-buenagrup3grp.png|148px|]]
|- style="text-align: center; font-size: 75%;"
| (a) 
| (b) 
|- style="text-align: center; font-size: 75%;"
| colspan="2" | '''Figura 13:''' Ejemplos de buenos agrupamientos porque los datos están linealmente separados. Fuente: Elaboración propia
|}

Estos conjuntos se consideran linealmente separables en el plano, dada la existencia de una recta tal que cada grupo incluido en el semiplano diferente, como se observa en la Figura[[#img-13|13]] a). En el conjunto <math display="inline">\mathbb{R}^{n}</math> se dice que dos conjuntos son linealmente separables si existe un hiperplano tal que cada grupo cae en uno de los subconjuntos determinados dicho hiperplano.

Una colección de estos grupos es linealmente separable, si cada par de ellos es linealmente separable, ver Figura[[#img-13|13]] b). Esta idea se puede observar más fácilmente con diagramas de Voronoi.

===4.5 Agrupamiento y Celdas de Voronoi===

Si se considera el diagrama de Voronoi de los centroides de un agrupamiento, a este diagrama lo llamamos ''diagrama de Voronoi del agrupamiento''. Se considera como ejemplo el grupo de datos siguiente, el agrupamiento de datos, el agrupamiento junto con el diagrama de Voronoi y por ultimo el diagrama de Voronoi de este agrupamiento, con respecto a sus centroides, Figura [[#img-14|14]].

<div id='img-14a'></div>
<div id='img-14b'></div>
<div id='img-14c'></div>
<div id='img-14d'></div>
<div id='img-14'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-datosagrupamiento.png|189px|Conjunto de datos.]]
|[[Image:Review_139704671734-agrupamiento.png|182px|Agrupamiento de los datos]]
|[[Image:Review_139704671734-voronoiagrupamiento.png|164px|Diagramas de Voronoi y el agrupamiento]]
|- style="text-align: center; font-size: 75%;"
| (a) Conjunto de datos.
| (b) Agrupamiento de los datos
| (c) Diagramas de Voronoi y el agrupamiento
|-
| colspan="3"|[[Image:Review_139704671734-soloagrupamiento.png|164px|Diagrama de Voronoi del agrupamiento]]
|- style="text-align: center; font-size: 75%;"
| (d) Diagrama de Voronoi del agrupamiento
|- style="text-align: center; font-size: 75%;"
| colspan="3" | '''Figura 14:''' Buenos agrupamientos y su diagrama de Voronoi. Fuente: Elaboración propia.
|}

Cuando el algoritmo KMeans proporciona un mal agrupamiento, es fácil observarlo mediante los diagramas de Voronoi. Se puede observar un ejemplo de mal agrupamiento en la Figura [[#img-15|15]] (b), que corresponde al conjunto de datos a agrupar con KMeans de la Figura [[#img-14|14]] (a).

<div id='img-15a'></div>
<div id='img-15b'></div>
<div id='img-15c'></div>
<div id='img-15'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-ejemplo4grupos.png|119px|Conjunto de datos a agrupar.]]
|[[Image:Review_139704671734-agrupamiento4grpmal.png|124px|Agrupamiento de los datos con KMeans.]]
|[[Image:Review_139704671734-voronoiagrupamiento4grpmal.png|129px|Agrupamiento de datos y diagramas de Voronoi.]]
|- style="text-align: center; font-size: 75%;"
| (a) Conjunto de datos a agrupar.
| (b) Agrupamiento de los datos con KMeans.
| (c) Agrupamiento de datos y diagramas de Voronoi.
|- style="text-align: center; font-size: 75%;"
| colspan="3" | '''Figura 15:''' Malos agrupamientos y su diagrama de Voronoi. Fuente: Elaboración propia.
|}

En la Figura [[#img-16|16]] (a) se muestra el mismo conjunto de datos, pero con un buen agrupamiento con KMeans. Ver su diagrama de Voronoi en la Figura  [[#img-16|16]] (b).

<div id='img-16a'></div>
<div id='img-16b'></div>
<div id='img-16'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-agrupamiento4grpbueno.png|117px|Conjunto de datos bien agrupados con KMeans]]
|[[Image:Review_139704671734-voronoiagrupamiento4grpbueno.png|132px|Buen agrupamiento y su diagrama de Voronoi]]
|- style="text-align: center; font-size: 75%;"
| (a) Conjunto de datos bien agrupados con KMeans
| (b) Buen agrupamiento y su diagrama de Voronoi
|- style="text-align: center; font-size: 75%;"
| colspan="2" | '''Figura 16''' 
|}

Los grupos que produce KMeans siempre están en distintas celdas de Voronoi generadas por los centroides del agrupamiento <span id='citeF-4'></span>[[#cite-4|[4]]]. Por lo tanto, KMeans agrupa bien cuando los grupos están en diferentes celdas de Voronoi, o bien cuando están linealmente separados dos a dos.

Otra forma de ver la separación lineal es mediante la envoltura convexa (''convex hull'') de los conjuntos que conforman el agrupamiento.

===4.6 Agrupamiento y envoltura convexa===

Es evidente observar que dos conjuntos de puntos son linealmente separables si su cascaras convexas no se intersectan. Es decir, dado un agrupamiento, se considera linealmente separable si estas envolturas de sus grupos no se intersectan dos a dos.

Se considera los siguientes 4 grupos y sus envolturas correspondientes. Estos grupos están linealmente separados y sus envolturas convexas no se intersectan dos a dos. Ver Figura [[#img-17|17]]

<div id='img-17a'></div>
<div id='img-17b'></div>
<div id='img-17'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:Review_139704671734-agrupamiento4grpbueno.png|117px|Buen agrupamiento con KMeans]]
|[[Image:Review_139704671734-convexhullagrupamiento4grpbueno.png|114px|Buen agrupamiento y su envoltura convexa]]
|- style="text-align: center; font-size: 75%;"
| (a) Buen agrupamiento con KMeans
| (b) Buen agrupamiento y su envoltura convexa
|- style="text-align: center; font-size: 75%;"
| colspan="2" | '''Figura 17:''' Ejemplo de conjunto de puntos en el plano que son linealmente separables. Fuente: Elaboración propia.
|}

==5 Algunas limitaciones==

A pesar de ser utilizado ampliamente en una gama de aplicaciones, el algoritmo KMeans no está exento de limitaciones. Algunos de estos inconvenientes han sido ampliamente descritos en la literatura <span id='citeF-5'></span>[[#cite-5|[5]]], y son los siguientes:

'''Número de clusters:''' El número de clusters tiene que ser conocido por el algoritmo en su inicialización. Por lo tanto, <math display="inline">k</math> tiene que ser un parámetro de entrada del algoritmo. '''Centroides iniciales:''' Sensibilidad a la inicialización de los centroides. '''Sensibilidad a outliers (ruido):''' La existencia de un conjunto pequeño de datos que distan mucho de las clases afecta el desempeño del algoritmo.

==6 El Marco de trabajo llamado Apache Spark==

El rápido aumento de usuarios de internet en los últimos años, combinado con la gran cantidad de datos que se generan, ha creado la necesidad de servicios, herramientas para proporcionar y procesar de manera confiable grandes conjuntos de datos. La computación en la nube cumple este propósito como un conjunto compartido de recursos informáticos (redes, servidores, almacenamiento, aplicaciones, servicios, etc.) que se puede alimentar e interactuar inmediatamente utilizando el concepto de computación en la nube, que permite el acceso a internet bajo demanda a la red <span id='citeF-6'></span>[[#cite-6|[6]]].

Uno de los marcos más utilizados para aplicaciones de análisis de datos basados en la nube es Apache Spark <span id='citeF-7'></span><span id='citeF-8'></span>[[#cite-7|[7,8]]]. Es una potente plataforma informática Hadoop de código abierto escrita en el lenguaje de programación Scala. Como Apache Spark es una infraestructura de propósito general para clústeres de computadoras, se utiliza principalmente para diversas aplicaciones. Además, el desarrollo de infraestructuras de computación en la nube ha llevado a la creación de nuevas técnicas y algoritmos para el procesamiento y análisis de datos, así como bibliotecas de aprendizaje automático destinadas a explotar su potencial <span id='citeF-9'></span>[[#cite-9|[9]]].

Desde el punto de vista del aprendizaje automático, Apache Spark proporciona a los usuarios técnicas tradicionales, como clasificación, agrupamiento y regresión, que constituyen la llamada biblioteca MLlib <span id='citeF-10'></span>[[#cite-10|[10]]]. Este marco de trabajo se caracteriza por altas velocidades de ejecución, paralelización de tareas y utilización de la memoria caché del sistema al implementar diferentes algoritmos.

Por lo descrito anteriormente, es de gran interés en esta investigación implantar y conocer este tipo de herramientas computacionales dada la necesidad constante de obtener información oculta en los datos y tener mayor conocimiento de algún problema en particular haciendo que los mismos datos de problema, muestren indicios o correlaciones importantes para encontrar los grupos de datos de interés.

==7 Consideraciones finales==

KMeans es un algoritmo heurístico que ha demostrado que tiene relación con otros métodos de agrupamiento como factorizaciones matriciales no negativas y análisis de componentes principales, por ejemplo. Este último será de especial interés en este trabajo en desarrollo.

El análisis de componentes principales (PCA) es una técnica estadística ampliamente utilizada para la reducción de dimensiones no supervisada. La agrupación de KMeans es una agrupación de datos de uso común para tareas de aprendizaje no supervisadas. Uno de los objetivos de este trabajo es mostrar que los componentes principales pueden ser una solución óptima a la inicialización de los centroides para la agrupación de KMeans, tal como lo indican diversos autores <span id='citeF-11'></span><span id='citeF-12'></span>[[#cite-11|[11,12]]] y que es un punto inicial del cual se partirá para seguir con este trabajo..

En esta investigación se estudiará la conexión entre estos dos métodos ampliamente utilizados. Se estudiará si la reducción de dimensiones no supervisada está estrechamente relacionada con el aprendizaje no supervisado.

Por otro lado, los datos de alta dimensión a menudo se transforman en datos de menor dimensión mediante el análisis de componentes principales (PCA) (o descomposición de valores singulares), donde se pueden detectar patrones coherentes con mayor claridad. Esta reducción de dimensiones no supervisada se utiliza en áreas muy amplias como la meteorología, el procesamiento de imágenes, el análisis genómico y la recuperación de información. También es común que se utilice PCA para proyectar datos a un subespacio de dimensiones inferiores y luego se aplique KMeans en el subespacio, pero esto es un trabajo futuro en este trabajo inicial y sustentado en diversas publicaciones base para su desarrollo <span id='citeF-11'></span><span id='citeF-13'></span>[[#cite-11|[11,13]]].

Por último se implementará una metodología basada en el cómputo en la nube. Implantando un marco de trabajo llamado Apache Spark para el trabajo con grandes cantidades de datos implantándolo en un cluster de computadoras personales y que será del tipo Beowulf para el alto desempeño de cálculo numérico. Es por eso que en este trabajo se implantará un cluster de computadoras instalando este marco de trabajo para trabajar con alta densidad de datos y poder estudiar el problema de los centróides iniciales usando la técnica de PCA dado que se espera que esta técnica proporcione centroides iniciales óptimos para realizar buenos agrupamientos con KMeans.

===BIBLIOGRAFÍA===

<div id="cite-1"></div>
'''[[#citeF-1|[1]]]''' Gan, Guojun and Ma, Chaoqun and Wu, Jianhong. (2007) "Data clustering: theory, algorithms, and applications", Volume 20. Society for Industrial and Applied Mathematics

<div id="cite-2"></div>
'''[[#citeF-2|[2]]]''' Elden, Lars. (2019) "Matrix Methods in Data Mining and Pattern Recognition". SIAM-Society for Industrial and Applied Mathematics, 2nd Edition

<div id="cite-3"></div>
'''[[#citeF-3|[3]]]''' Teknomo, Kardi. (2006) "K-Means Clustering Tutorial", Volume 100. Medicine 4 3

<div id="cite-4"></div>
'''[[#citeF-4|[4]]]''' Wikipedia "KMeans" http://es.wikipedia.org/wiki/K-means

<div id="cite-5"></div>
'''[[#citeF-5|[5]]]''' Pérez, J and Henriques, MF and Pazos, R and Cruz, L and Reyes,  G and Salinas, J and Mexicano, A. (2007) "Mejora al algoritmo de agrupamiento K-means mediante un nuevo criterio  de convergencia y su aplicación a bases de datos poblacionales  de cáncer". II Taller Latino Iberoamericano de Investigación de Operaciones

<div id="cite-6"></div>
'''[[#citeF-6|[6]]]''' Rashid, Aaqib and Chaturvedi, Amit. (2019) "Cloud computing characteristics and services: a brief review", Volume 7. International Journal of Computer Sciences and Engineering 2 421&#8211;426

<div id="cite-7"></div>
'''[[#citeF-7|[7]]]''' Dritsas, Elias and Livieris, Ioannis E and Giotopoulos, Konstantinos and Theodorakopoulos, Leonidas. (2018) "An apache spark implementation for graph-based hashtag sentiment classification on twitter". Proceedings of the 22nd Pan-Hellenic Conference on Informatics 255&#8211;260

<div id="cite-8"></div>
'''[[#citeF-8|[8]]]''' Ntaliakouras, Nikolaos and Vonitsanos, Gerasimos and Kanavos, Andreas and Dritsas, Elias. (2019) "An apache spark methodology for forecasting tourism demand in greece". IEEE. 2019 10th International Conference on Information, Intelligence, Systems and Applications (IISA) 1&#8211;5

<div id="cite-9"></div>
'''[[#citeF-9|[9]]]''' Salloum, Salman and Dautov, Ruslan and Chen, Xiaojun and Peng, Patrick Xiaogang and Huang, Joshua Zhexue. (2016) "Big data analytics on Apache Spark", Volume 1. Springer. International Journal of Data Science and Analytics 145&#8211;164

<div id="cite-10"></div>
'''[[#citeF-10|[10]]]''' Meng, Xiangrui and Bradley, Joseph and Yavuz, Burak and Sparks, Evan and Venkataraman, Shivaram and Liu, Davies and Freeman, Jeremy and Tsai, DB and Amde, Manish and Owen, Sean and others. (2016) "Mllib: Machine learning in apache spark", Volume 17. JMLR. org. The journal of machine learning research 1 1235&#8211;1241

<div id="cite-11"></div>
'''[[#citeF-11|[11]]]''' Chen, Jingwei and Zhu, Jianyong and Jiang, Hongyun and Yang, Hui and Nie, Feiping. (2022) "Sparsity Fuzzy C-Means Clustering with Principal Component Analysis Embedding". IEEE. IEEE Transactions on Fuzzy Systems

<div id="cite-12"></div>
'''[[#citeF-12|[12]]]''' Lu, Shizeng and Yu, Hongliang and Wang, Xiaohong and Zhang, Qiang and Li, Fanjun and Liu, Zhao and Ning, Fangqian. (2018) "Clustering method of raw meal composition based on PCA and Kmeans". IEEE. 2018 37th Chinese control conference (CCC) 9007&#8211;9010

<div id="cite-13"></div>
'''[[#citeF-13|[13]]]''' Divya, V and Devi, K Nirmala. (2018) "An Efficient Approach to Determine Number of Clusters Using Principal Component Analysis". IEEE. 2018 International Conference on Current Trends towards Converging Technologies (ICCTCT) 1&#8211;6