Facul ad de Ciencias
G ado en ma em´
a icas
TRABAJO DE FIN DE GRADO:
EL M´
ETODO DE KMEDIAS
AUTOR:
Ca la Pe ucha Ju jo
TUTOR:
Ca los Ma ´an Bea
Julio 2022
´
Indice
1. In oducci´on 2
2. P esen aci´on del m´e odo de kmedias 4
2.1. Plan eamien o in ui i o del p oblema de ag upaci´on . . . . . . . . . . . . . . . . . . 4
2.2. La media como ep esen an e de los da os . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3. Aplicaciones de kmedias ................................. 7
3. Es udio e´o ico de kmedias 10
3.1. Plan eamien o del modelo gene al de kmedias ..................... 10
3.2. P opiedades ma em´a icas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.1. Exis encia de kmedias............................... 13
3.2.2. Unicidad del p oblema de kmedias........................ 16
3.2.3. Pun os on e a en e clus e s . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3. Consis encia del m´e odo de k-medias........................... 25
3.3.1. Con e gencia de k-ϕ-medias emp´ı icas a k-ϕ-medias e´o icas . . . . . . . . . . 29
4. Algo i mo de kmedias 32
4.1. Necesidaddealgo i mos.................................. 32
4.2. T es algo i mos pa a el p oblema de kmedias...................... 34
4.2.1. El algo i mo de Lloyd (1957) . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.2. El algo i mo de MacQueen (1967) . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.3. El algo i mo de Ha igan-Wong (1979) . . . . . . . . . . . . . . . . . . . . . . 36
4.3. P incipales ca encias de kmedias............................. 37
4.3.1. Conjun os de da os ap opiados pa a kmedias.................. 37
4.3.2. Elecci´on de k, el n´ume o de g upos a busca . . . . . . . . . . . . . . . . . . . 39
4.3.3. Fue e dependencia de la inicializaci´on . . . . . . . . . . . . . . . . . . . . . . 42
4.4. Implemen aci´on....................................... 44
5. M´e odos y es a egias pa a mejo a la inicializaci´on 52
5.1. Algunos m´e odos pa a la inicializaci´on de kmedias................... 52
5.1.1. P incipales p ocedimien os pa a la inicializaci´on . . . . . . . . . . . . . . . . 53
5.2. El p ocedimien o de kmedias++............................. 54
5.2.1. Ma co e´o ico de kmedias++........................... 57
5.2.2. Una co a supe io pa a el p oblema . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.3. Una co a in e io pa a el p oblema . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2.4. Algunas gene alizaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2.5. Ejemplos de la aplicaci´on de kmedias++ .................... 72
6. Ap´endice 75
6.1. Algunos esul ados auxilia es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.2. Algunas nociones sob e complejidad compu acional . . . . . . . . . . . . . . . . . . . 78
1
1. In oducci´on
En las ´ul imas d´ecadas, hemos sido es igos de un a ance ecnol´ogico monumen al y un c eci-
mien o exo bi ado del mundo digi al. Aplicaciones como b´usquedas en in e ne , c eaci´on de p´aginas
web, p ocesamien o de im´agenes, igilancia po ideo... han gene ado conjun os de da os de ama˜no
ex ao dina io. De igual mane a, no solo se ha egis ado un c ecimien o en la can idad de in o ma-
ci´on sino que ambi´en se ha inc emen ado la a iedad de ipos de da os ( ex o, imagen, ideo).
Debido a es e aumen o an o de olumen como de a iedad en los ipos de da os, la u ilizaci´on
de las ´ecnicas p opias del An´alisis de Da os se ha gene alizado en odo ipo de es udios e in es i-
gaciones. El An´alisis Clus e o de Conglome ados ocupa un luga des acado en es a ciencia: es la
´ecnica mul i a ian e enca gada del es udio de m´e odos y algo i mos dise˜nados pa a ag upa obje os
de acue do con sus ca ac e ´ıs icas in ´ınsecas. Pa a ealiza un An´alisis Clus e , pa imos de nindi-
iduos de los cuales hemos omado medidas en d a iables, en b´usqueda de la ag upaci´on na u al de
los obje os, buscamos asigna cada obje o a un clus e (o g upo) de al mane a que los miemb os de
un mismo g upo sean lo m´as homog´eneos posibles y lo m´as di e en es posibles a los indi iduos de
los o os g upos.
El An´alisis Clus e se encuad a en e los m´e odos de clasi icaci´on no supe isada: nues a in en-
ci´on es ag upa indi iduos en clus e s homog´eneos sin ene un conocimien o a p io i de las ca ego ´ıas
o ipolog´ıas de los obje os con los que abajamos.
De las muchas ´ecnicas de ag upamien o ela i as al An´alisis Clus e , en es e abajo es udia e-
mos de enidamen e el m´e odo de kmedias. La media de un conjun o de da os p e ende se el mejo
ep esen an e de es os de acue do con el c i e io de m´ınimos cuad ados. Pa iendo de es o, el p oce-
dimien o de kmedias ex iende la idea na u al de media y busca el mejo ep esen an e o mado po
no uno sino kelemen os del espacio. De es a mane a, una ez escogidos es os kpun os denominados
cen oides, se gene a una pa ici´on del conjun o de da os en kg upos o clus e s donde asignamos
cada pun o al ep esen an e m´as “simila ” a ´el. Es un m´e odo muy in e esan e debido a su senci-
llez concep ual, el amplio es udio que se ha ealizado en cuan o a su compo amien o asin ´o ico, su
simplicidad de implemen aci´on y el hecho de que, a pesa de se un p oblema compu acionalmen e
di ´ıcil, exis en nume osas heu ´ıs icas e icien es que pe mi en una con e gencia ´apida a un ´op imo
local. Si bien es un p ocedimien o que se publica po p ime a ez en 1955, es a d´ıa de hoy uno de los
m´as u ilizados en el campo del An´alisis Clus e .
El p oblema de kmedias y sus di e en es aspec os an o e´o icos como compu acionales siguen
siendo obje o de es udio a d´ıa de hoy, po lo que encon amos a ´ıculos bas an e ecien es que ecogen
nue os esul ados del m´e odo o p esen an p opues as de algo i mos m´as e icien es en la inicializaci´on.
Es e documen o iene como obje i o in oduci el p ocedimien o de kmedias y ecoge algunos de
los esul ados ma em´a icos m´as in e esan es, incluyendo algunos menos comunes, ya que el m´e odo
de kmedias es a ado habi ualmen e desde la pe spec i a algo ´ı mica y no muy ecuen emen e
encon amos esul ados e´o icos en los manuales de kmedias.
Desde el pun o de is a compu acional, el p oblema de encon a k ep esen an es que consigan
sa is ace el c i e io de m´ınimos cuad ados es NP-Ha d. Los algo i mos exis en es son i e a i os y
pa en de una inicializaci´on de kelemen os escogidos alea o iamen e con el in de llega a una solu-
ci´on ´op ima localmen e. Cabe en onces p egun a se si una buena inicializaci´on p opo ciona mejo as
2
no ables en la pos e io ag upaci´on de indi iduos u ilizando el m´e odo. La espues a es cla amen e
a i ma i a y mos a emos algunos de los p ocedimien os m´as exi osos a la ho a de selecciona cen-
oides iniciales adecuados, p o ocando as´ı no solo una mejo a en la soluci´on sino meno iempo de
ejecuci´on del algo i mo.
Pa a conclui es a in oducci´on, deci que en es e documen o hemos gene ado mul i ud de ejem-
plos isuales empleando el lenguaje de p og amaci´on R, ampliamen e u ilizado en es ad´ıs ica. En
es e en o no de p og amaci´on exis en m´ul iples paque es que implemen an algo i mos de clus e ing
(en pa icula kmedias) y unciones pa a isualiza sus esul ados. En es e documen o se emplean
los siguien es:
s a s: con iene las unciones dis () pa a calcula ma ices de dis ancias, kmeans() y, a pesa
de que no se ´an u ilizados en es e abajo, unciones que nos pe mi en aplica o o ipo de
p ocedimien os como hclus (), cu ee() pa a c ea los clus e s y plo .hclus () pa a isualiza
los esul ados.
ac oex a: con iene las unciones iz clus e () pa a elabo a elegan es isualizaciones de las
ag upaciones en clus e s, iz nbclus () pa a de e mina y isualiza el n´ume o ´op imo de
clus e s, y o as muchas unciones ela i as a o as ´ecnicas mul i a ian es.
lexclus : Con iene la unci´on kcca() que pe mi e ejecu a el algo i mo de kmedias con una
a ian e in e esan e denominada kmedias++ que pe mi e una elecci´on de cen os iniciales
mucho m´as sa is ac o ia cuando las condiciones son las adecuadas.
3
2. P esen aci´on del m´e odo de kmedias
En es a secci´on, expond emos un p ime ejemplo que nos ace ca ´a de mane a in ui i a al An´alisis
Clus e y al p op´osi o de busca ag upaciones en un conjun o de indi iduos. Ve emos ambi´en c´omo
a la ho a de abaja con conjun os de da os, a menudo es amos in e esados en encon a un ep e-
sen an e de es os que pe mi a desc ibi los de la mejo mane a posible, pues esumi la in o maci´on
nos pe mi e comp ende la. Las medidas de cen alizaci´on ienen un papel impo an e en es a sin e-
izaci´on que a amos de elabo a ya que nos p opo cionan un ep esen an e ubicado en el “cen o”
del conjun o de los da os. En pa icula , la media esul a se el m´as in e esan e seg´un el c i e io
de m´ınimos cuad ados. P esen a emos ambi´en en es a secci´on un p ime ace camien o a kmedias
desde la pe spec i a de cons ui una gene alizaci´on del concep o de media, cuyo papel es el de se el
ep esen an e na u al de un conjun o de da os. Como ya hemos comen ado, los ejemplos expues os
a lo la go de es e abajo se ´an p ocesados con el lenguaje de p og amaci´on R, de uso ex endido en
el ´ambi o de la es ad´ıs ica.
2.1. Plan eamien o in ui i o del p oblema de ag upaci´on
Al inicio de es e documen o, comen ´abamos que el p op´osi o del An´alisis Clus e o de Conglome-
ados es busca ag upaciones na u ales que puedan se i pa a halla elaciones en un conjun o de
da os que sean ´u ilies a la ho a de clasi ica los. Pa a comenza , p esen amos un conjun o de da os
cons i uido po 150 obse aciones de indi iduos a los que hemos medido alo es en 2 a iables, X
eY, y plan ea emos la mane a in ui i a de busca ag upaciones en e los indi iduos a endiendo a
los alo es que oman en es as dos a iables. Es as se ´ıan algunas de las p ime as obse aciones del
conjun o de da os y la ep esen aci´on de los 150 indi iduos si los conside amos como pun os en R2:
(a) Rep esen aci´on en el plano de los indi iduos (b) Encabezado de los da os
Figu a 1
Nues o obje i o es encon a una ag upaci´on de los indi iduos de al mane a que aquellos que
4

se encuen en en el mismo g upo sean lo m´as homog´eneos en e s´ı, a endiendo a los alo es que
oman en las dos a iables que es amos conside ando. Es os g upos de indi iduos eciben el nomb e
de clus e s en la Ciencia del An´alisis de Conglome ados.
Cuando uno a a de ag upa los indi iduos de ca ac e ´ıs icas simila es a endiendo al g ´a ico, se
hace pa en e que exis e un conjun o de obse aciones cuyas medidas an o en la a iable Xcomo
en la a iable Yson cla amen e meno es. Pa ece l´ogico euni odos es os indi iduos en un mismo
g upo ya que se pa ecen en e s´ı y sus medidas son muy di e en es de las del es o de indi iduos.
En segundo luga , al ez con un poco m´as de es ue zo, epa amos en que hay unas cuan os
indi iduos con mediciones in e medias de ambos alo es y o os an os cuyas medidas en las dos
a iables son bas an e m´as al as. Al con a io que an es, no es cla a la sepa aci´on en e es os dos
g upos: pa ece que indi iduos del segundo g upo con alo es ela i amen e al os en las a iables se
con unden con indi iduos del e ce g upo con alo es ela i amen e bajos de las a iables. Aun as´ı,
somos capaces de “co a ” es e g upo y, con lo mencionado an e io men e, elabo a una clasi icaci´on
in ui i a de los indi iduos en es g upos.
Figu a 2: Ag upaci´on in ui i a que pod ´ıamos hace
Dos medidas muy impo an es que u ilizamos pa a medi la simila idad en e indi iduos son la
dis ancia in a-clus e y la dis ancia in e -clus e : Nos pa ece na u al euni indi iduos cuyos alo es
en las a iables dis an poco en e s´ı y que se di e encian mucho de las mediciones en las a iables de
o os indi iduos. Po lo an o, nues o m´e odo de clus e ing debe ´a ene como obje i o minimiza
las dis ancias en e indi iduos de una misma ag upaci´on y maximiza la dis ancia en e indi iduos
de di e en es g upos.
2.2. La media como ep esen an e de los da os
Como ya se ha comen ado, la media de un conjun o de da os suele u iliza se como un ep esen an e
na u al de es os. La jus i icaci´on se encuen a en el hecho de se el elemen o que minimiza la dispe si´on
5
cuad ´a ica media:
P oposici´on 1. Sea C={x1, .., xn}un conjun o con npun os de Rd,w1, .., wn∈Rcon wi≥0
∀i= 1, .., n yPn
i=1 wi= 1, y sea m=Pn
i=1 xiwi. En onces
m= a g min
a∈Rd
n
X
i=1
wi∥xi−a∥2(1)
Demos aci´on
Sea F:Rd−→ Rla unci´on de inida po
F(y) =
n
X
i=1
wi∥xi−y∥2
Podemos eesc ibi la unci´on Fen coo denadas como
F(y) =
n
X
i=1 

d
X
j=1
wi(xi,j −yj)2

Pa a es udia los pun os c ´ı icos de F, dado que es de i able en Rd, calculamos su g adien e ∇F(y) =
∂F
∂y1, .., ∂F
∂ydy lo igualamos a ce o. Pa a k= 1, .., d, enemos que
∂F
∂yk
=∂
∂yk

n
X
i=1
d
X
j=1
wi(xi,j −yj)2
= 2yk
n
X
i=1
wi−2
n
X
i=1
xi,kwi= 0 ⇒yk=
n
X
i=1
xi,kwi
Po lo an o,
y= (y1, .., yd) = n
X
i=1
xi,1wi, ..,
n
X
i=1
xi,dwi!=
n
X
i=1
(xi,1, .., xi,d)wi=
n
X
i=1
xiwi=m
Dado que mes el ´unico pun o c ´ı ico y esul a que l´ımy→∞ F(y) = l´ımy→−∞ F(y) = ∞, debe se un
m´ınimo y queda p obado el esul ado. □
Su ge en onces ambi´en de o ma na u al la b´usqueda de un ep esen an e de nues o conjun o
de da os o mado po kelemen os del espacio. Un esumen en k ep esen an es de un conjun o de
pun os nos da ´a m´as in o maci´on y pe mi i ´a desc ibi mejo las obse aciones sob e odo en el caso
en el que exis an di e encias signi ica i as en e los alo es que oman en las a iables. Es deci ,
si deno amos Bkcomo la clase de conjun os con kelemen os de Rd, de inimos una kmedia de un
conjun o de da os {x1, .., xn} ⊂ Rddados pesos wicomo hemos desc i o an e io men e como un
conjun o H∈ Bkque e i ica
H= a g min
G∈Bk
n
X
i=1
wim´ın
g∈G∥xi−g∥2(2)
6
Con es a de inci´on, seguimos buscando la mejo desc ipci´on de acue do con el c i e io de m´ıni-
mos cuad ados, es a ez a a ´es de kelemen os. Es e plan eamien o pa ece in e esan e desde la
pe spec i a no solo de ob ene un esumen en kpun os de un conjun o de da os sino de es ablece
un ep esen an e de cada clus e y asocia cada obse aci´on al conjun o cuyo ep esen an e es m´as
pa ecido. El p ocedimien o que a a de o maliza es a idea na u al es el m´e odo de kmedias. El
e ec o que p oduci ´ıa el c´alculo de k= 3 ep esen an es (igual al n´ume o de g upos que hab´ıamos
o mado) en el ejemplo an e io se ´ıa el siguien e, pa a el cual hemos u ilizado la unci´on kmeans de
Rcuya misi´on es busca en es e caso 3 ep esen an es denominados cen oides y ag upa las obse -
aciones en unci´on de qu´e cen oide dis a menos de cada una:
Figu a 3: T es ep esen an es del conjun o de da os y la ag upaci´on que p o ocan.
2.3. Aplicaciones de kmedias
Podemos p egun a nos si el p ocedimien o de ag upaci´on que hemos lle ado a cabo al inicio del
apa ado con el in de consegui c ea ipolog´ıas o clases de obje os simila es en e s´ı nos ayuda a
clasi ica indi iduos cuando los da os poseen una o ganizaci´on subyacen e o si la ag upaci´on que
hemos ealizado no iene nada que e . En nues o caso, el conjun o de da os con el que hemos
abajado es una educci´on a dos a iables del bien conocido conjun o de da os “I is”, disponible en
R. En ´el se ecogen 150 obse aciones de es especies de lo es bas an e simila es en e s´ı: se osa,
e sicolo y i ginica. Pa a cada ipo de lo , se ha medido la longi ud y la anchu a de sus p´e alos.
Pa a que la clasi icaci´on ue a no supe isada (el caso en el que desconocemos a p io i a qu´e especie
de lo pe enece cada una de las obse aciones), simplemen e hab´ıamos eliminado la ´ul ima columna
del conjun o de da os que e ique aba cada indi iduo, po lo que no en´ıamos conocimien o a p io i
ni de cu´an as especies de lo es hab´ıamos podido ecoge ni de cu´ales e an.
7
Figu a 4: Eliminaci´on de e ique as y de a iables “La gu a de s´epalo” y “Anchu a de s´epalo”
Realiza una clasi icaci´on (o en nues o caso, una ag upaci´on) de los indi iduos a endiendo a sus
medidas en dos a iables cob a sen ido aho a que conocemos la na u aleza de las obse aciones, ya
que pa ece azonable pensa que la longi ud y la anchu a de los p´e alos de un ipo de lo pueda
ca ac e iza una especie y di e encia la de o os ipos de lo es. De es a o ma, es l´ogico oma unos
ep esen an es del conjun o de indi iduos pa a ealiza un esumen de qu´e di e en es lo es hemos
podido ecoge y a la ez ayuda nos a ag upa las seg´un sus simili udes en e s´ı. De es a mane a
end ´ıamos, de acue do con las dos a iables, es ep esen an es del conjun o de lo es: aquellas con
pe alos peque˜nos y es echos, aquellas con p´e alos medianos y aquellas con p´e alos g andes y anchos.
Es o nos pe mi e es ablece es g upos y asocia cada obse aci´on al conjun o cuyo ep esen an e
es m´as pa ecido.
E ique amos aho a cada obse aci´on con la especie a la que pe enece con la ayuda de la columna
que hab´ıamos eliminado en nues os da os y compa amos con el esul ado ob enido an e io men e
po kmeans. Ma camos con un pun o elleno aquellos indi iduos que kmedias ha conseguido cla-
8
>ZB0
ϕ(∥x−h0∥)dP(x) + ZBc
0
´ın
h∈Hϕ(∥x−h∥)dP(x)
Si ag upamos ambos ozos, llegamos a la siguien e desigualdad:
Wk
ϕ(H, P)>Zm´ın{ϕ(∥x−h0∥),´ın
h∈H(ϕ(∥x−h∥)}dP(x) = Z´ın
h∈H∪h0
ϕ(∥x−h∥)dP(x) = Wk+1
ϕ(H∪h0, P)
Con lo que concluimos la demos aci´on.
□
Demos aci´on
Demos a emos el Teo ema (1). Buscamos p oba que en la exp esi´on Vk
ϕ(P) = ´ın G∈BkWk
ϕ(G, P),
es e in e io ealmen e es un m´ınimo. Conside emos Hn={hn
1, .., hn
k} ∈ Bk al que Wk
ϕ(Hn, P)−→
´ın G∈BkWϕ(G). Sea I={i∈ {1, .., k}/l´ım in n∥hn
i∥<∞}.
Se iene que Ies no ac´ıo: Si es o no ocu ie a, ∀i∈ {1, .., k} esul a ´ıa que l´ım in n∥hn
i∥=∞.
Veamos que si es o ue a as´ı, Vk
ϕ(P) no se ´ıa el in e io . Tenemos, aplicando el Lema de Fa ou
Vk
ϕ(P) = l´ım in
nWk
ϕ(Hn, P) = l´ım in
nZ´ın
i=1,..,k ϕ(∥x−hn
i∥)dP(x)≥Zl´ım in
n´ın
i=1,..,k ϕ(∥x−hn
i∥)dP(x)
Dado que (y) = ´ın i=1,..,k ϕ(y) es una unci´on con inua, se iene que
Zl´ım in
n´ın
i=1,..,k ϕ(∥x−hn
i∥)dP(x) = Z´ın
i=1,..,k ϕ(l´ım in
n∥x−hn
i∥)dP(x)
Aplicamos a con inuaci´on la segunda desigualdad iangula y el hecho de que I=∅:
Vk
ϕ(P)≥Zϕ( ´ın
i=1,..,k l´ım in
n∥x−hn
i∥)dP(x)≥Zϕ( ´ın
i=1,..,k(l´ım in
n∥hn
i∥−∥x∥))dP(x) = Zϕ(∞)dP(x)
Pe o es o es absu do, pues Vk
ϕ(P) no se ´ıa el in e io .
Po lo an o, sabemos que Ino es ac´ıo: Exis e al menos un ´ındice icon l´ım in n∥hi∥<∞. Es
deci , exis e M > 0 y una subsucesi´on {hnk
i}k al que ∥hnk
i∥< M pa a k≥k0. De es a subsucesi´on
aco ada, po el Teo ema de Bolzano-Weie s ass, podemos ex ae una subsucesi´on con e gen e. Pa a
simpli ica la no aci´on, segui emos denomin´andola {hn
i}n. De inamos J={i∈ {1, .., k}/hn
i−→ h0
pa a un cie o h0}={1, .., s}si los o denamos adecuadamen e. Po lo que acabamos de deci , Jes
no ac´ıo dado que Ino lo es.
Pa a los ´ındices i∈J, ya que hn
i−→ h0
i, ealizando un azonamien o simila al an e io po
medio del Lema de Fa ou
Vk
ϕ(P) = l´ım in
nWk
ϕ(Hn, P) = l´ım in
nZ´ın
i=1,..,k ϕ(∥x−hn
i∥)dP(x)≥
≥Zl´ım in
n´ın
i=1,..,k ϕ(∥x−hn
i∥)dP(x) = Z´ın
i=1,..,s ϕ(∥x−h0
i∥)dP(x)≥Vs
ϕ(P)
15

Po el lema (2), sabemos que ene kpun os disminuye el po encial penalizado po ϕ en e a
ene spun os , po lo que necesa iamen e se iene Vk
ϕ(P) = Vs
ϕ(P) y as´ı
Ws
ϕ({h0
1, .., h0
s}, P) = l´ım
n→∞ Ws
ϕ({hn
1, .., hn
s}, P) = Vs
ϕ(P)
Tenemos dos opciones:
Si k=s, el conjun o H0={h0
1, .., h0
k} e i ica Wk
ϕ(H0, P) = Vk
ϕ(P) y po lo an o es una
k-ϕ-media de X.
Si s < k, dado que Vk
ϕ(P) = Vs
ϕ(P), po el lema (2) necesa iamen e Vs
ϕ(P) = 0 y podemos
a˜nadi m´as pun os a los sque ya en´ıamos has a llega has a k, con lo que segui mos eniendo
ga an izada la exis encia de una k-ϕ-media.
□
3.2.2. Unicidad del p oblema de kmedias
Plan eadas las hip´o esis bajo las cuales exis en las k-ϕ-medias de un ec o alea o io X, nues a
siguien e p egun a se ´a si el p oblema de encon a un conjun o Hde kpun os que minimice el po-
encial penalizado po ϕde nues o ec o alea o io (bajo las condiciones que asegu an su exis encia)
end ´a una ´unica soluci´on o si po el con a io exis en a ios conjun os de es as ca ac e ´ıs icas con los
que se alcanza el m´ınimo. El in e ´es que enemos al espec o no es solo e´o ico, sino que ambi´en se ´a
in e esan e desde el pun o de is a compu acional debido a que la mul iplicidad de soluciones puede
p o oca un mayo iempo de ejecuci´on. En el ma co p ´ac ico nos p egun a emos si, dependiendo de
la inicializaci´on que omemos, somos capaces de encon a m´as de una soluci´on ´op ima. La espues a
es cla amen e a i ma i a, an o si conside amos una mues a de npun os como si pensamos en la
k-ϕ-media de una dis ibuci´on de p obabilidad.
Algunos ejemplos
Conside emos en p ime luga el caso en el que enemos un conjun o de da os. Supongamos que
que emos halla una 2-media del conjun o de pun os {(−1,0),(0,0),(1,0)}, cuya ep esen aci´on en
el plano es la siguien e:
16
Figu a 6
Supongamos que la medida de disimila idad que u ilizamos es la dis ancia Eucl´ıdea. Dado que
los pun os es an colocados de mane a que uno equidis a de dos de ellos, m´as alejados en e s´ı, es
cla o que exis en dos soluciones ´op imas:
1. C1={(−1,0)}yC2={(0,0),(1,0)}y cen os h1= (−1,0), h2= (0′5,0)
2. C1={(−1,0),(0,0)}yC2={(1,0)}y cen os h1= (−0′5,0), h2= (1,0)
dado que, en ambos casos, P3
i=1 m´ınj=1,2∥xi−hj∥2= 1 es m´ınima.
Al busca una ag upaci´on y dos cen oides con kmeans de R ob enemos los dos esul ados ejecu ando
el p og ama dos eces:
(a) P ime a Soluci´on (b) Segunda Soluci´on
Figu a 7
17
En un caso an sencillo como es e emos cla o que la unicidad del p oblema no se da y exis en
dos soluciones que nos pe mi en llega a un po encial m´ınimo. La ob enci´on de dos soluciones pa ece
consecuencia de la p esencia de un pun o que equidis a de dos. Uno pod ´ıa pensa en clasi ica ese
indi iduo del medio en dos g upos simul ´aneamen e. Es deci , coloca los cen oides en los pun os
(−1
2,0) y (1
2,0) y deja ese pun o en la on e a de ambos clus e s:
Figu a 8
Sin emba go, el m´e odo de kmedias e i a si uaciones as´ı: Ve emos m´as adelan e c´omo la on e a
de un g upo end ´a siemp e p obabilidad ce o si calculamos los clus e s u ilizando el algo i mo.
Es o que acabamos de obse a no solo ocu e al calcula las kmedias de un conjun o de da os
sino cuando nos plan eamos si las kmedias de una dis ibuci´on de p obabilidad son ´unicas. P esen-
amos el siguien e ejemplo pa a ilus a c´omo la espues a a es a cues i´on a menudo es nega i a y
adem´as deja pa en e que, sal o en casos muy conc e os, no enemos esul ados sob e la unicidad del
p oblema.
Conside amos el expe imien o consis en e en selecciona un pun o al aza en el c´ı culo de adio
unidad cen ado en el o igen de coo denadas (denomimamos Ba es a bola).
18
Figu a 9
Sean XeYla abscisa y o denada espec i amen e del pun o elegido. La elecci´on comple amen e
al aza de un pun o en el c´ı culo sin que haya zonas con m´as p e e encia que o as puede modeliza se
a a es de la unci´on de densidad conjun a
X,Y (x, y) = 1
πsi x2+y2≤1
0si x2+y2>1
Sea x = (x, y). Nues o obje i o es encon a una 2-media de (X, Y ) ( omamos como media de
disimila idad la dis ancia Eucl´ıdea al cuad ado), es deci , halla M1yM2en Bde al mane a que
minimicen Rm´ıni=1,2∥x −Mi∥2dP(x).
Calculamos en p ime luga las densidades ma ginales de Xy de Y:
X(x) = 2
πp1−x2,−1<x<1
Y(y) = 2
πp1−y2,−1< y < 1
A con inuaci´on, hallamos la espe anza de (X, Y ), sabiendo que E(X, Y )=(E(X),E(X)). As´ı
pues
E(X) = Z1
−1
xdP(x) = Z1
−1
x X(x)dx =Z1
−1
2
πxp1−x2dx = 0
De mane a an´aloga, se iene E(Y) = 0 y con ello, E(X, Y ) = (0,0).
19
Es cla o que es os dos pun os M1yM2di iden a Ben dos subconjun os:
A1={x ∈B/∥x −M1∥2≤ ∥x −M2∥2}, A2={x ∈B/∥x −M1∥2≥ ∥x −M2∥2}
Donde Mise ´ıa la media del conjun o Aipa a i= 1,2, es deci , E((X, Y )/Ai) = Mi. Adem´as,
el conjun o A1∩A2 iene p obabilidad ce o. De es e modo, u ilizando espe anzas condicionadas,
podemos exp esa E(X, Y ) como combinaci´on lineal con exa de M1yM2, ya que P(A1)=1−P(A2):
E(X, Y ) = E((X, Y )|A1)P(A1) + E((X, Y )|A2)P(A2)
Es o supone que ambos pun os deben es a en un di´ame o de la ci cun e encia. Sin p´e dida de
gene alidad, supond emos que es el co espondien e al eje de abscisas. As´ı, los pun os M1yM2son
de la o ma
M1= (m1,0), M2= (m2,0), m1, m2∈R
A su ez, g acias a es a conside aci´on podemos eesc ibi los conjun os A1yA2:
A1={x ∈B/x ≤m1+m2
2}, A2={x ∈B/x ≥m1+m2
2}
Podemos eesc ibi la exp esi´on a minimiza de es e modo:
ZB
m´ın
i=1,2∥x −Mi∥2dP(x) = ZA1
∥x −M1∥2dP(x) + ZA2
∥x −M2∥2dP(x) (7)
Sin emba go, obse amos que solo depende de la densidad de la p ime a coo denada y coincide,
sal o po una cons an e, con la exp esi´on co espondien e a la 2-media de la dis ibuci´on ma ginal
co espondien e. De es a mane a, hemos log ado plan ea el p oblema en ´e minos de una sola di-
mensi´on. En es as condiciones, exis en esul ados in e esan es que nos ga an izan la unicidad de la
2-media de (X, Y ) y m´as gene almen e de la kmedia. El que amos a u iliza apa ece en el a ´ıculo
[16] en el que g acias a esul ados p e iamen e p obados po B. Flu y, se es ablece el siguien e lema:
Lema 3. Sea Xuna a iable alea o ia uni a ian e y su unci´on de densidad. Suponemos que
es sim´e ica en o no al o igen y log-c´onca a. En onces, iene dos ´unicos pun os p incipales
(denominados 2-media en nues o caso) que son sim´e icos espec o del o igen.
Dado que X(x) sa is ace es as hip´o esis, podemos aplica el lema y a i ma que exis en dos ´uni-
cos pun os m1ym2que minimizan la exp esi´on (7) y que e i ican adem´as que m1=−m2.
Desa ollando la exp esi´on a minimiza y ealizando algunos c´alculos engo osos pe o sencillos, se
p ueba que en es e p oblema en conc e o m1=−4
3πym2=4
3π.
El hecho de que m1=−m2y con ello m1+m2
2= 0, implica que los dos g upos ob enidos A1yA2
se ´ıan exac amen e los semic´ı culos de Bdelimi ados po el eje de o denadas. Hab´ıamos supues o
que el di´ame o que un´ıa M1yM2e a p ecisamen e el eje de abscisas, pe o aplicando una o aci´on
aM1,M2y al di´ame o, exis en in ini os pa es de pun os que consiguen minimiza la exp esi´on (7).
Po lo an o, es cla o que exis en in ini as soluciones al p oblema. Pa a ilus a lo, gene amos 50000
pun os en Buni o memen e y aplicamos kmeans de R ei e adamen e. Ob enemos an o cen oides
como pa iciones de Bcomple amen e di e en es en cada caso.
20

Figu a 10
Exis en pocos esul ados ela i os a la unicidad de k-ϕ-medias. Algunos de los exis en es exigen
condiciones m´as ue es sob e la unci´on de densidad de p obabilidad. O os, como el que p esen amos
a con inuaci´on, demandan p opiedades m´as ue es de la unci´on ϕy educen sus esul ados al caso
k= 1.
P oposici´on 3. Si la unci´on ϕes es ic amen e con exa, en onces la ϕ-media de Pes ´unica.
Demos aci´on
Supongamos que enemos mym∗∈Rddos ϕ-medias de Xdi e en es y omemos λ∈(0,1).
C eamos una combinaci´on lineal con exa de mym∗,mλ=λm + (1 −λ)m∗. Reco demos que la
de inici´on de que msea ϕ-media de X, en es e caso media, es
Zϕ(∥x−m∥)dP(x) = Zϕ(∥X−m∥)dP≤Zϕ(∥X−g∥)dP
pa a cualquie elemen o g∈R.
Dado que la unci´on ϕes es ic amen e con exa y c ecien e, sumando y es ando λx, y aplicando
la desigualdad iangula , enemos que
Zϕ(∥x−mλ∥)dP(x) = Zϕ(∥x−(λm+(1−λ)m∗)∥)dP(x) = Zϕ(∥x−λm−m∗+λm∗+λx−λx∥)dP (x)≤
≤Zϕ(∥λx −λm∥+∥x−m∗+λm∗−λx∥)dP(x) = Zϕ(λ∥x−m∥+ (1 −λ)∥x−m∗∥)dP(x)
Como ϕes es ic amen e con exa, se iene que
Zϕ(λ∥x−m∥+ (1 −λ)∥x−m∗∥)dP(x)≤λZϕ(∥x−m∥)dP(x) + (1 −λ)Zϕ(∥x−m∗∥)dP (x)
21
Ya que an o mcomo m∗son ϕ-medias, esul a que
λZϕ(∥x−m∥)dP(x) + (1 −λ)Zϕ(∥x−m∗∥)dP(x) = Zϕ(∥x−m∥)dP (x)
Y, po lo an o, podemos a i ma que
Zϕ(∥x−mλ∥)dP(x)≤Zϕ(∥x−m∥)dP(x)
Dado que ϕes es ic amen e con exa, sal o que ∥x−m∥=∥x−m∗∥P−c.s., la desigualdad es es ic a.
Como mes una ϕ-media, necesa iamen e debe cumpli se ∥x−m∥=∥x−m∗∥con p obabilidad 1:
si no, hab ´ıamos encon ado un alo que minimiza a´un m´as la exp esi´on. De inimos el conjun o
A={y∈Rd/∥y−m∥=∥y−m∗∥P−c.s.}
Pe o podemos eesc ibi lo como
B={y∈Rd/∃x∈Rdcon ⟨x, m −m∗⟩= 0 e y =x+m+m∗
2P−c.s.}
Donde ⟨·,·⟩ deno a el p oduc o escala euclideo ( ´ease la demos aci´on en el Ap´endice, (5)).
Pe o en onces, esul a que si ∥y−m∥=∥y−m∗∥P−c.s., podemos esc ibi y=x+m+m∗
2P−c.s.
con ⟨x, m −m∗⟩= 0. De es e modo, desa ollando de nue o el p oduc o escala
∥x+m+m∗
2−mλ∥2=∥(x+m+m∗
2−m∗)−λ(m−m∗)∥2=
=∥x+m+m∗
2−m∗∥2+ 2λ⟨(x+m+m∗
2−m∗), m∗−m⟩+λ2∥m∗−m∥2
Dado que ∥y−m∥=∥y−m∗∥P−c.s., podemos eesc ibi la exp esi´on an e io como
∥x+m+m∗
2−m∥2+λ2∥m∗−m∥2+ 2λ⟨x, m −m∗⟩ − λ∥m∗−m∥2
Sabemos que ⟨x, m −m∗⟩= 0 P−c.s., po lo que cancelamos el ´e mino. Como λ∈(0,1), se
iene que λ2< λ, po lo que
∥x+m+m∗
2−m∥2+λ2∥m∗−m∥2−λ∥m∗−m∥2<∥x+m+m∗
2−m∥2
Es deci , hemos llegado a que la siguien e desigualdad se e i ica con p obabilidad 1. Dado que ϕes
es ic amen e con exa, podemos a i ma
∥x+m+m∗
2−mλ∥2<∥x+m+m∗
2−m∥2⇒ϕ(∥x+m+m∗
2−mλ∥2)< ϕ(∥x+m+m∗
2−m∥2)
De es e modo, llegamos a un absu do ya que me a ϕ-media de X, po lo que debe se inalmen e
m=m∗.□
22
3.2.3. Pun os on e a en e clus e s
Hemos comen ado que la soluci´on del p oblema de kmedias no es necesa iamen e ´unica y que a
pesa de que pod ´ıa pa ece posible encon a pun os a la misma dis ancia de dos cen os de clus e y
de alg´un modo “ epa i ” su masa de p obabilidad en e ambos g upos, el m´e odo e i a es as si ua-
ciones y la on e a de un clus e siemp e end ´a p obabilidad ce o. En es e apa ado p e endemos
demos a es o ´ul imo plan eando qu´e condiciones debemos impone sob e ϕpa a pode asegu a
es o. Pa a ello, nos apoya emos en la p oposici´on demos ada en el apa ado an e io que asegu a
la unicidad de la ϕ-media en el caso de se ϕcon exa, y a su ez usa emos que la ϕ-media de un
conjun o A si exis e, siendo ϕcon exa, siemp e es ´a en A(Ve p oposici´on (6) en el Ap´endice). Es e
esul ado sob e la p obabilidad de los pun os en la on e a de dos clus e s se encuen a en [3] en el
caso de k-ϕ-medias eco adas.
Teo ema 2. Sea X ec o alea o io, ken e o posi i o y ϕ:R+−→ R+una unci´on c ecien e, con i-
nua, al que ϕ(0) = 0 y con exa. Supongamos adem´as que se e i ica R´ın g∈Gϕ(∥x−g∥)dP (x)<∞
pa a alg´un G∈ Bkcon el in de asegu a la exis encia de la k-ϕ-media. Sea H={h1, .., hk}∈Bk
una k-ϕ-media de XyC={C1, .., Ck}la pa ici´on de Rdinducida po H. Supongamos adem´as que
la de i ada de ϕexis e, es con inua y que hi=hjsi i=j.
En onces, P({x∈Rd/∥x−hi∥=∥x−hj∥})=0si i=j. Es deci , los pun os en la on e a de
dos o a ios clus e s ienen p obabilidad 0.
Demos aci´on
Sea Ciel clus e co espondien e al cen o hiy suponemos que RCidP(x)>0 pa a e i a el caso
i ial, al igual que hi=hjsi i=j. Sea Bi,j ={x∈Rd/∥x−hi∥=∥x−hj∥}, es deci , la on e a
en e los clus e s CiyCj. Si conside amos qu´e elemen o de Hminimiza la in eg al en Ci∪Cj,
llegamos a que dependiendo de que xcojamos, elegi emos bien hio bien hj:
ZCi∪Cj
m´ın
l=1,..,k(ϕ(∥x−hl∥)dP(x) = ZCi∪Cj
m´ın(ϕ(∥x−hi∥, ϕ(∥x−hj∥))dP(x)
Podemos esc ibi Ci∪Cj= (Cj∪Bi,j)⊔(Ci−Bi,j), donde ⊔deno a la uni´on disjun a. De es a
mane a esc ibi ´ıamos
ZCi∪Cj
m´ın(ϕ(∥x−hj∥), ϕ(∥x−hi∥))dP(x) = ZCj∪Bi,j
ϕ(∥x−hj∥)dP(x)+ZCi−Bi,j
ϕ(∥x−hi∥)dP(x)
Se iene que la ϕ-media de Ci∪Bi,j, la de Ci−Bi,j yhideben coincidi (De mane a an´aloga pa a
hj). Si es o no ue a as´ı, pod ´ıamos cambia hiyhjen Hpo las espec i as ϕ-medias de Cj∪Bi,j
yCi−Bi,j, deno ando ese nue o conjun o de Bkpo H∗. De es a mane a, dado que la ϕ-media de
un conjun o es ´unica, Hno se ´ıa una k-ϕ-media:
ZCi∪Cj
m´ın
h∈H(ϕ(∥x−hl∥)dP(x)>ZCi∪Cj
m´ın
h∈H∗(ϕ(∥x−hl∥)dP(x)
Sea h0la ϕ-media de Ci−Bi,j. Vamos a comp oba que si la p obabilidad de los pun os on e a
en e clus e s CiyCjes es ic amen e posi i a, en onces h0no se ´a ϕ-media de Ci∪Bi,j y po lo
23
an o llega ´ıamos a un absu do. Deno amos po h1la ϕ-media de Bi,j, que ambi´en necesi a emos
pa a las demos aciones.
En p ime luga , comp obamos que RCi−Bi,j dP(x)>0. Reco demos que hi∈Cipo se ϕ-
media de Ciy no emos que Bi,j =Bi,j po se ce ado. Si ue a RCi−Bi,j dP(x) = 0, necesa iamen e
hi∈Bi,j. De lo con a io, hi∈Ci−Bi,j pe o RCi−Bi,j ϕ(∥x−h∥)dP(x) = 0 pa a cualquie h∈Rd,
po lo que exis i ´ıan in ini as ϕ-medias y es o es absu do.
Pe o si hi∈Bi,j, en onces hicumpli ´ıa ∥hi−hj∥=∥hi−hi∥= 0 y esul a ´ıa hi=hj, po lo que
llega ´ıamos a un absu do. Es deci , necesa iamen e RCi−Bi,j dP(x)>0.
Adem´as, sabemos que h0=h1. Si no, esul a ´ıa que
ZCi−Bi,j
ϕ(∥x−h0∥)dP(x)+ZBi,j
ϕ(∥x−h1∥)dP(x) = ZCi
ϕ(∥x−h0∥)dP(x)≤ZCi
ϕ(∥x−hi∥)dP(x)
Donde la desigualdad es es ic a a no se que hi=h0po se la ϕ-media de un conjun o ´unica. Dado
que hies ϕ-media, se iene que e i ica h0=h1=hi. Pe o en onces como h1∈Bi,j, necesa iamen e
hi∈Bi,j y azonando como an es llega ´ıamos a un absu do.
Como h1=h0, podemos escoge una base o ogonal {e1, .., ed}de al mane a que las coo dena-
das en es a base de h0sean (0,0, .., 0) y e1=h1−h0= (1,0, .., 0).
A con inuaci´on, cons uimos la unci´on :R−→ Rdde inida como ( )=( , 0, .., 0) = h y esc ibi-
mos
ϕ′(∥x− ( 0))∥) = d
d ϕ(∥x−h )∥)| = 0
De inimos las siguien es unciones
H1( ) = ZCi−Bi,j
ϕ(∥x−h ∥)dP(x), H2( ) = ZBi,j
ϕ(∥x−h ∥)dP(x)
Adem´as, dado que ϕ′exis e y es con inua, las de i adas de H1( ) y de H2( ) ambi´en exis en y son
con inuas
H′
1( ) = ZCi−Bi,j
ϕ′(∥x−h ∥)dP(x), H′
2( ) = ZBi,j
ϕ′(∥x−h ∥)dP(x)
Como h0es ϕ-media de Ci−Bi,j, minimiza la unci´on ϕ(∥x−h ∥) en Ci−Bi,j. Po lo an o,
podemos asegu a que H′
1(0) = 0.
Veamos que H2( ) es es ´ıc amen e con exa en [0,1]. Dados , ∈[0,1], que emos e que
H2(λ + (1 −λ) )< λH2( ) + (1 −λ)H2( )
Como h = ( , 0, .., 0), en onces hλ +(1−λ) = (λ +(1−λ) , 0, .., 0) = λ( , 0, .., 0)+(1−λ)( , 0, .., 0) =
λh +(1−λ)h . De es e modo, u ilizando que ϕes es ic amen e con exa pa a es ablece la desigual-
dad, se iene
H2(λ + (1 −λ) ) = ZBi,j
ϕ(∥x−hλ +(1−λ) ∥)dP(x) = ZBi,j
ϕ(∥x−λh + (1 −λ)h ∥)dP(x)≤
24
Si se die a que E( (Yω
0)) <∞, dado que H0es ijo, la Ley Fue e de los G andes N´ume os
asegu a ´ıa que
Z (x)dPω
n(x)c.s.
−−→ Z (x)dP0(x) = Zϕ( ´ın
h∈H0
∥x−h∥)dP0(x) = Zϕ( ´ın
h∈H0
∥Yω
0−h∥)dλ, ω ∈Ω0
Y con ello, end ´ıamos la condici´on eque ida en (3). Veamos que e ec i amen e E( (Yω
0)) <∞.
Si no lo ue a, dado que H0es la k-ϕ-media de Yω
0, se e i ica ´ıa
∞=E( (Yω
0)) = Z (x)dP(x) = Zϕ( ´ın
h∈H0
∥Yω
0−h∥)dλ ≤Zϕ(´ın
g∈G∥Yω
0−g∥)dλ
pa a cualquie conjun o G∈ Bkpo de inici´on de k-ϕ-media. Es o es absu do, ya que cualquie
conjun o de kelemen os se ´ıa una k-ϕ-media de Yω
0y hab´ıamos supues o la unicidad de H0.
Po lo an o, debe da se E( (Yω
0)) <∞y con ello log amos sa is ace la e ce a hip´o esis del
Teo ema.
□
31

4. Algo i mo de kmedias
Aho a que hemos p esen ado el modelo e´o ico de kmedias y es udiado sus p opiedades ma-
em´a icas, nos p egun amos c´omo halla de mane a p ´ac ica una soluci´on al p oblema de kmedias.
In oduci emos di e en es algo i mos i e a i os que consiguen encon a soluciones ´op imas local-
men e y expond emos algunas unciones que encon amos en el lenguaje de p og amaci´on R a la
ho a de lle a a cabo es a labo . Habla emos po ´ul imo de las p incipales di icul ades p opias del
p ocedimien o de kmedias.
(a) (b) (c)
Figu a 11: E oluci´on de los g upos en un conjun o de da os al busca los cen os de clus e median e
un algo i mo i e a i o
4.1. Necesidad de algo i mos
Conside emos de nue o el conjun o de da os con el que abaj´abamos al inicio de es e documen o
y eamos qu´e p oblemas encon amos a la ho a de busca de mane a p ´ac ica es ep esen an es del
conjun o de obse aciones y la pa ici´on en es g upos de los indi iduos. P incipalemn e, exis en
dos azones po las que esul a necesa io ealiza el p oceso de ag upaci´on de un conjun o de da os
po el m´e odo de kmedias de o ma au om´a ica:
1. Imposibilidad de encon a ag upaciones isualmen e si abajamos con m´as de
dos a iables
Hab´ıamos conside ado an e io men e que los 150 indi iduos del conjun o de da os omaban
medidas en XeY. En ese caso, consegu´ıamos ealiza una ag upaci´on in ui i a g acias a la
isualizaci´on en dos dimensiones de es os indi iduos. Sin emba go, en el momen o en el que
aumen amos el n´ume o de a iables, la b´usqueda de pa ones isuales se hace impensable. Si
a˜nadimos al conjun o de da os las mediciones en las a iables que al an (es o es, aho a aba-
jamos con las a iables X, Y, W, Z) y ep esen amos las obse aciones po pa es de a iables,
nos encon amos con la a ea p ´ac icamen e imposible de busca ag upaciones isualmen e
32
(12a). En la igu a de la de echa, u ilizamos el p ocedimien o de 3-medias pa a halla es
ep esen an es (ma cados con una X) y la di isi´on en es g upos que inducen:
(a) Obse aciones sin ag upa (b) Una ag upaci´on dada po kmedias
Figu a 12: Indi iduos con alo es en 4 a iables en luga de 2
Es o nos da una idea de cu´an o necesi amos p ocedimien os au om´a icos de ag upamien o o
clus e ing ya que, llegados a cie o pun o de complejidad, somos incapaces de busca esos pa-
ones isuales que nos pe mi en c ea g upos de indi iduos.
2. Can idad deso bi ada de posibilidades pa a elegi k ep esen an es
Una p ime a idea ingenua que pod ´ıamos ene pa a consegui k ep esen an es se ´ıa ealiza
odas las posibles combinaciones de ag upaciones en kg upos del conjun o de da os y queda nos
con aquellas que minimizan el k-ϕ-po encial del conjun o de da os. Sin emba go, es a pe spec-
i a no es en absolu o ealis a ya que el n´ume o de posibilidades se dispa a deso bi adamen e.
Analicemos qu´e ocu e en el ejemplo. Debemos halla odas las posibles combinaciones de 150
elemen os en 3 g upos. Con ija las posibilidades pa a los dos p ime os g upos, el e ce o queda
ya elegido. Sean C1yC2dos de los g upos, sea k1el n´ume o de pun os de C1yk2el n´ume o de
pun os de C2. En p ime , luga escoge emos k1pun os de los 150, cosa que podemos hace de
150
k1 o mas. A con inuaci´on, de los 150 −k1pun os es an es, elegimos k2: enemos 150−k1
k2
posibilidades. Dado que solo necesi amos que k1, k2>0 y que k1+k2< n pa a cons ui los
33
es g upos, el n´ume o o al de combinaciones pa a o ma los es clus e s se ´ıa
X
k1,k2>0
k1+k2<n 150
k1150 −k1
k2
Es cla o que esul a imposible calcula odas las opciones y comp oba cu´al esul a la mejo
po el c i e io de m´ınimos cuad ados, po lo que necesi amos con ecciona algo i mos que nos
den una ap oximaci´on de la soluci´on o consigan una soluci´on ´op ima localmen e.
4.2. T es algo i mos pa a el p oblema de kmedias
Conside emos a pa i de aho a X={x1, .., xn}un conjun o de pun os de Rd,kun en e o po-
si i o y ijemos como unci´on de disimila idad ϕla no ma eucl´ıdea al cuad ado. Asignamos peso 1
n
a cada uno de los pun os del conjun o de da os X. Sea H={h1, .., hk} ⊂ Ry sea C={C1, .., Ck}
pa ici´on asociada a Hde X.
Una ez desc i o el ma co de abajo con el que con inua emos de aho a en adelan e, si Pndeno a
la p obabilidad mues al que asigna peso 1
na cada xi∈ X, esc ibi emos Wk(H) = Wk
ϕ(H, Pn) a in
de acili a la lec u a. Llamamos k-po encial de Xpo HaWk(H).
Encon a Hque minimice el k-po encial de Xes equi alen e a encon a Hque minimice la
suma de dis ancias al cuad ado en cada uno de los clus e s Cj:
H= a g min
G∈Bk
n
X
i=1
m´ın
j=1,..,k∥xi−gj∥2= a g min
G∈Bk
k
X
j=1 X
x∈Cj
∥x−gj∥2(9)
Demos amos en la p oposici´on (1) que la media a i m´e ica de los da os, m=1
nPn
i=1 xi, e i i-
caba
m= a g min
a∈Rd
n
X
i=1
∥xi−a∥2
Po lo an o, si que emos minimiza (9), cada cen o de clus e hjdebe ´a co esponde se con el
p omedio de los pun os de Cj, es o es:
hj=1
|Cj|X
x∈Cj
x
Es o nos pe mi e plan ea el p oblema desde la pe spec i a de encon a una pa ici´on del con-
jun o Xde al mane a que se minimice la unci´on obje i o, donde los kcen oides se co esponde ´an
con el p omedio de los pun os asignados a cada clus e . Los es algo i mos m´as conocidos de k
medias que p esen a emos a con inuaci´on ienen como com´un denominado el c´alculo i e a i o de los
cen oides como media de los pun os de cada espec i o clus e y la easignaci´on de los da os a los
cen oides una ez ac ualizados.
34
4.2.1. El algo i mo de Lloyd (1957)
Es e algo i mo es el p ocedimien o de c´alculo de cen oides m´as conocido y ex endido. Los pasos
pa a encon a los cen os de clus e son los siguien es:
1. Escoge alea o iamen e kcen oides iniciales H={h1, .., hk}.
2. Pa a cada pun o xi,i= 1, .., n
Pa a cada j= 1, .., k, calcula la dis ancia di,j de xia cada cen o hj.
Asigna xial clus e Cjcuyo cen o hjes m´as ce cano
3. Pa a cada cen o hj,j= 1, .., k
Recalcula el cen o de masa de cada clus e y asigna a hjese alo . Es o es
hj:= 1
|Cj|X
x∈Cj
x
4. Repe i los pasos 2) y 3) has a que Hse es abilice.
4.2.2. El algo i mo de MacQueen (1967)
El algo i mo de Lloyd iene la incon eniencia de que cuando ac ualiza la asignaci´on de los da os
no ac ualiza los cen oides, po lo que podemos llega a asocia obse aciones inco ec amen e a un
cen oide simplemen e po que es e no es aba ac ualizado.
El algo i mo de MacQueen (1967) sol en a es a ca encia i e ando sob e los pun os del conjun o
de da os y co igiendo en ese mismo momen o el cen oide co espondien e: Una ez easignamos un
pun o a un clus e , ecalculamos su espec i o cen oide. En es e caso, la i e aci´on se epi e has a
que ning´un pun o cambia de g upo. Cabe obse a ambi´en que la e si´on de MacQueen conlle a un
n´ume o m´as ele ado de ope aciones que el algo i mo de Lloyd. Los pasos pa a calcula los cen os
de clus e seg´un MacQueen son los siguien es:
1. Escoge alea o iamen e kcen oides iniciales H={h1, .., hk}.
2. Pa a cada pun o xi,i= 1, .., n
Pa a cada j= 1, .., k, calcula la dis ancia di,j de xia cada cen o hj.
Asigna xial clus e Cjcuyo cen o hjes m´as ce cano
Recalcula el cen o de masa del clus e Cjy asigna a hjese alo . Es o es
hj:= 1
|Cj|X
x∈Cj
x
3. Repe i 2) has a que ning´un pun o cambie de g upo.
35
4.2.3. El algo i mo de Ha igan-Wong (1979)
Tan o el m´e odo de Lloyd como el de MacQueen eligen los cen oides iniciales escogiendo kob-
se aciones alea o iamen e. El algo i mo de Ha igan-Wong p opone asocia un n´ume o del 1 a k
a cada pun o del conjun o de da os y oma como cen oide inicial hila media de los pun os a los
que hab´ıamos asociado la e ique a i: de es a mane a, casi odos los cen oides se si ´uan po la zona
cen al de la nube de da os y el algo i mo es menos p openso a con e ge a un ´op imo local. Al igual
que MacQueen, ac ualiza los cen oides en el momen o en el que cada pun o es easignado.
El algo i mo de Ha igan-Wong incluye o a modi icaci´on que hace al m´e odo m´as lexible en e a
los o os dos algo i mos. Reco demos que la unci´on obje i o que a ´abamos de minimiza es la suma
de dis ancias al cuad ado desde cada pun o has a su cen oide asignado. Ha igan-Wong pe mi e que
un pun o se pueda asigna a un cen oide incluso si es e no es el m´as ce cano si disminuye la unci´on
obje i o en mayo medida. De es a mane a, esul a m´as so is icado al conside a el impac o global
que end ´ıa asigna una obse aci´on a un cen o de clus e .
1. Pa a cada i= 1, .., n, asigna alea o iamen e un n´ume o desde 1 has a ka cada pun o xi.
2. Pa a cada j= 1, .., k, cons uimos Cjel conjun o de pun os a los que hemos asignado el n´ume o
j. Calculamos el cen oide hjcomo
hj:= 1
|Cj|X
x∈Cj
x
3. Pa a cada pun o xi,i= 1, .., n
Pa a cada cen o hj,j= 1, .., k
- Asigna xial clus e Cj.
- Calcula el alo de la unci´on obje i o, Wi,j, dada es a asignaci´on.
Asigna xial clus e Cjcuyo Wi,j es meno .
Recalcula el cen o de masa del clus e Cjy asigna a hjese alo . Es o es
hj:= 1
|Cj|X
x∈Cj
x
4. Repe i 3) has a que ning´un pun o cambie de g upo.
Al se el m´as e inado de los es algo i mos que hemos p esen ado, aca ea un n´ume o mayo de
ope aciones. En el caso de con a con un conjun o de da os en el que los g upos son ´aciles de sepa a ,
el algo i mo de Lloyd se ´a p obablemen e m´as ´apido a la ho a de encon a una ag upaci´on. Sin
emba go, Ha igan-Wong es m´as lexible y complejo po lo que esul a m´as ecomendable u iliza lo
cuando no enemos in o maci´on sob e el conjun o de da os.
36

4.3. P incipales ca encias de kmedias
El m´e odo de kmedias es un p ocedimien o muy ´u il a la ho a de busca ag upaciones en nume-
osos conjun os de da os, pe o debido a sus ca ac e ´ıs icas in ´ınsecas p esen a cie as de iciencias y
debilidades con de e minados conjun os de da os. En es e apa ado, es udiamos cuales son los ac o-
es m´as impo an es que de e io an el uncionamien o del algo i mo. A su ez, deja emos el camino
p epa ado pa a habla de m´e odos ela i os a la inicializaci´on que consiguen subsana en nume osas
ocasiones es as de iciencias, un asun o que a a emos en secciones pos e io es. Supond emos en odo
momen o que la medida de disimila idad u ilizada es la dis ancia eucl´ıdea al cuad ado.
4.3.1. Conjun os de da os ap opiados pa a kmedias
Pa a en ende un poco mejo qu´e es uc u a in ´ınseca deben ene los da os que a amos de
ag upa pa a que kmedias consiga su come ido, debemos a a de en ende c´omo hemos cons uido
el algo i mo y qu´e disposiciones iende a a o ece po ello. Una ez asignamos pun os a un cen o
de clus e en pa icula , dado que el c i e io elegido ha sido aquel de minimiza la dis ancia eucl´ıdea
al cuad ado y sabemos que los subconjun os de la o ma {x∈Rd/∥x−C∥2≤R2}son bolas en el
espacio, la apa iencia de los g upos que o ma kmedias es es ´e ica. Po ejemplo, conside amos el
conjun o de da os con 200 obse aciones de X1∼N((6,0),Σ) y o as 200 de X2∼N((0,0),Σ), con
ma iz de co a ianza com´un Σ = 2 0
0 2 . En es e caso, el algo i mo clasi ica co ec amen e debido a
la apa iencia es ´e ica de los g upos.
Figu a 13
Debido a es a p edilecci´on po es uc u as es ´e icas, en el momen o en el que nos en en amos
a un conjun o de da os con una o ma “complicada”, kmedias suele alla en la ag upaci´on (Ve
Shaped Se s, Spi al N=312, k=3, D=2 en [8]):
37
Figu a 14
Sin emba go, no hace al a busca conjun os de da os con o mas dispa a adas: Supongamos que
con amos con 200 obse aciones de X1∼N((6,0),Σ) y o as 200 de X2∼N((0,0),Σ), con ma iz
de co a ianza com´un Σ = 0,5 0
0 20 . Dado que Σ nos indica una a iabilidad mucho m´as al a en
la segunda coo denada de los da os que en la p ime a, sabemos a p io i que an a se g upos con
apa iencia “ala gada”. Debido a que no son es ´e icos, kmedias simplemen e op a po pa i los a la
mi ad alej´andose po comple o de la soluci´on:
Figu a 15
Pa a es a ca encia del m´e odo, se han in oducido modelos m´as ambiciosos que pe mi en o mas
38
elipsoidales di e sas pa a cada ag upamien o.
A su ez, es un m´e odo muy sensible an e con aminaciones o peque˜nas des iaciones del modelo,
ya que si exis en pun os aislados del es o, su apo aci´on al po encial se ´a muy g ande y pa a
disminui lo, el m´e odo de kmedias ende ´a a desplaza sus cen os en esa di ecci´on a in de educi lo.
Es e p oblema se puede sol en a a a ´es de p ocedimien os de eco e, que podemos encon a en
a ´ıculos como [4].
4.3.2. Elecci´on de k, el n´ume o de g upos a busca
A la ho a de busca ag upamien os con el algo i mo de kmedias en un conjun o de da os, hemos
supues o que enemos un n´ume o en e o posi i o kp e ijado que se co esponde con el n´ume o de
g upos a busca . En algunas ocasiones, desea emos pa iciona un conjun o de obse aciones en un
n´ume o ijo de g upos con alguna inalidad, pe o el caso m´as com´un es aquel en el que el n´ume o
de clus e s iene de e minado po la na u aleza de los da os y las elaciones que albe gan los indi i-
duos en e s´ı. Po ello, necesi amos dispone de alg´un c i e io que nos pe mi a es ablece en cu´an os
g upos pa ece m´as c e´ıble pa iciona un conjun o de da os.
(a) (b) (c)
Figu a 16: Posibles elecciones de kpa a un mismo conjun o de da os.
La elecci´on de kes un p oblema in ´ınsecamen e imposible de esol e si conside amos un conjun-
o de da os a bi a io, ya que depende de la es uc u a del conjun o de da os y el n´ume o de g upos
a de e mina debe ´a se elegido a medida en cada caso: no exis e un m´e odo gene al. Es cla o que
es e n´ume o no puede es ima se con el in de minimiza el k-po encial, ya que la o ma de hace lo
se ´ıa oma an os g upos como obse aciones consiguiendo siemp e un k-po encial de 0.
Pa a a a de sol en a es o, exis en a ias soluciones ad hoc que pe mi en es ablece un c i e io
pa a la elecci´on de k. No p opo cionan siemp e una soluci´on del odo sa is ac o ia ya que su buen
uncionamien o es ´a supedi ado a la es uc u a in ´ınseca del conjun o de da os. P esen amos es
39
de las m´as u ilizadas:
1. C i e io del Codo
Buscamos ealiza un es que compa e la mejo a al elegi k+1 g upos en e a elegi kcompa-
ando la dis ancia in a-clus e ob enida a iando el n´ume o de g upos. Pa a ello, ejecu amos
el algo i mo de kmedias pa a pa a di e en es alo es de k, calculamos la dis ancia in a-clus e
ob enida en cada caso y ep esen amos ambos da os en un g ´a ico. Pa a el conjun o de da os
de la imagen de a iba, se end ´ıa la siguien e ep esen aci´on:
Figu a 17
En es a g ´a ica se debe ´ıa de ap ecia un cambio b usco en la e oluci´on del po encial, eniendo
la l´ınea ep esen ada una o ma simila a la de un b azo y su codo. El pun o en el que se
obse a ese cambio b usco se ´a aquel que selecciona emos como n´ume o de clus e s a busca
en el conjun o de da os, en es e caso k= 3. Es ecomendable ejecu a es e p ocedimien o epe-
idas eces, dado que una mala inicializaci´on pa a alg´un alo de kpuede al e a el esul ado.
Podemos encon a m´as in o maci´on sob e es e c i e io p.ej. en [1].
2. M´e odo de la Silue a
El M´e odo de la Silue a de ine pa a cada pun o del conjun o de da os una medida de simila idad
en e ´el y los dem´as indi iduos del mismo clus e en compa aci´on con aquellos de clus e s
di e en es. A cada pun o se le asigna un alo en e -1 y 1 denominado ´ındice de silue a, donde
un alo al o equi ale a una mejo coincidencia con el clus e en el que debe clasi ica se y meno
disposici´on a pe enece a o o g upo. La media del ´ındice de silue a de odos los pun os se
u iliza pa a indica la calidad de la ag upaci´on.
Dado un conjun o de da os {x1, .., xn}, si pa a un pun o xideno amos po aila media de las
dis ancias de xial es o de pun os del clus e al que ha sido asignado, y po bila media de las
dis ancias de xia pun os de g upos di e en es al suyo, el ´ındice de silue a de xise calcula del
siguien e modo, donde kes el n´ume o de g upos:
s(xi, k) = bi−ai
m´ax{bi, ai}(10)
40
Figu a 22: Elecci´on des a o able de los cen os
Si buscamos una unci´on que ealice es e p oceso sin necesidad de p og ama la noso os desde
ce o, podemos acudi al paque e s a s de R que con iene, en e o as, la unci´on llamada kmeans.
La unci´on kmeans pa iciona un conjun o de da os dado en kg upos. Su uso es sencillo y
adem´as es muy e s´a il, ya que nos p opo ciona la opci´on de escoge los cen os iniciales, el n´ume o
m´aximo de i e aciones que que emos ealiza y el algo i mo conc e o pa a busca los cen oides (Los
desc i os an e io men e:“Lloyd”, “MacQueen” y “Ha igan-Wong”, jun o con o o debido a Fo gy).
Es a unci´on de uel e un da a ame en el que es ´an p esen es
Un ec o que indica a qu´e clus e en iamos cada pun o.
Una ma iz con los cen oides inales.
El po encial co espondien e a esa ag upaci´on en clus e s.
La dis ancia in a-clus e , pa a cada clus e .
La dis ancia in e -clus e , pa a cada clus e .
Un ec o con el n´ume o de obse aciones asignadas a cada clus e .
N´ume o de i e aciones lle adas a cabo.
47

Po ejemplo, si aplicamos kmeans de R en la e si´on de Lloyd al conjun o de da os con el que
es ´abamos abajando, ob enemos lo siguien e:
K-means clus e ing wi h 3clus e s o sizes 50,46,54
Clus e means:
X Y
1 1.462000 0.246000
2 5.626087 2.047826
3 4.292593 1.359259
Clus e ing ec o :
[1]111111111111111111111111111111111111
[37]111111111111113333333333333333333333
[73]333332333332333333333333333322222232
[109]222222222223222322332222222222322222
[145]222222
Wi hin clus e sum o squa es by clus e :
[1]2.02200 15.16348 14.22741
(be ween_SS / o al_SS = 94.3 %)
A ailable componen s:
[1]"clus e " "cen e s" " o ss" "wi hinss"
[5]" o .wi hinss" "be weenss" "size" "i e "
[9]"i aul "
O o paque e in e esan e que p opo ciona unos g ´a icos y isualizaciones muy in ui i as es ac o-
ex a. En ´el, encon amos la unci´on iz clus e que pe mi e e las ag upaciones m´as cla amen e,
e ique ando el n´ume o de obse aci´on a la ho a de e ec ua el g ´a ico:
48
Si aplicamos el p ocedimien o de kmedias al conjun o de da os o iginal, aquel con cua o a ia-
bles X, Y, W yZ, y a amos de ilus a g ´a icamen e lo que ocu e, ob enemos una ep esen aci´on
isual dada po pa es de a iables que puede esul a menos in ui i a a la ho a de pensa qu´e es ´a
pasando con nues os da os.
La unci´on iz clus e que mencion´abamos an e io men e nos o ece una soluci´on in e esan e
pa a obse a en un solo g ´a ico la ag upaci´on e ec uada po kmedias u ilizando An´alisis en Compo-
nen es P incipales (PCA). Es un p ocedimien o mul i a ian e cuyo obje i o undamen al es educi
la dimensi´on del conjun o de da os minimizando la p´e dida de in o maci´on pa a consegui una des-
c ipci´on m´as sencilla de los mismos. Pa a ello, se cons uye un nue o conjun o de a iables a pa i
de combinaciones lineales de las a iables o iginales que ecojan la mayo can idad de in o maci´on
posible y se escogen an as di ecciones o componen es sean necesa ias pa a exp esa la in o maci´on
y ep esen a la. En nues o caso pa a pode e una ep esen aci´on en dos dimensiones, buscamos
ex ae las dos p ime as componen es p incipales. Aplicando la unci´on iz clus e conseguimos el
esul ado. Obse amos que en el caso del g ´a ico con PCA queda ecogida el 86.7 % de la in o ma-
ci´on, po lo que puede se in e esan e u iliza lo cuando necesi emos una isualizaci´on sencilla de las
ag upaciones.
49
(a) G ´a ico de pa es de a iables (b) G ´a ico con PCA
Figu a 23: Una o ma m´as c´omoda de isualiza los esul ados
Po o o lado, en es e mismo paque e, encon amos la unci´on iz nbclus que elabo a de mane a
au om´a ica un diag ama pa a elegi k. Nos pe mi e elegi el m´e odo pa a de e mina el n´ume o
´op imo de clus e s: Dis ancia In a-clus e ,M´e odo de la Silue a oM´e odo de Es ad´ıs ica de B echa
(Es a ´ul ima compa a la a iaci´on in a-g upo o al pa a di e en es alo es de kcon sus alo es
espe ados bajo una dis ibuci´on sin ag upamien o ob io; Encon amos de allado el p ocedimien o en
[14]). En el ejemplo que nos ocupa, pa a el caso de dos a iables X, Y , el esul ado se ´ıa el siguien e:
50
(a) M´e odo de dis ancia In a-clus e (b) M´e odo de la Silue a (c) M´e odo de Es ad´ıs ica de B echa
Figu a 24: Di e en es m´e odos en R pa a elegi el n´ume o de g upos
Po lo an o, en es e caso pa ece adecuado busca 2 o 3 g upos en el conjun o de da os.
51
5. M´e odos y es a egias pa a mejo a la inicializaci´on
El obje i o de es a secci´on es desc ibi some amen e algunos de los m´e odos de inicializaci´on
m´as comunes a la ho a de elegi los cen oides iniciales pa a ejecu a el algo i mo de kmedias.
Despu´es, p o undiza emos en el p ocedimien o de kmedias++, p esen ando los pasos pa a lle a lo a
cabo e implemen a lo. A con inuaci´on, expond emos los p incipales esul ados ma em´a icos espec o
a la aco aci´on que podemos consegui del alo medio del po encial hallado con el algo i mo y,
pa a e mina , comen a emos algunos ejemplos con di e en es conjun os de da os que nos pe mi i ´an
obse a las en ajas de kmedias++ en e a kmedias “s anda d”. Dado que en ocasiones ha emos
e e encia a cues iones del campo de la complejidad compu acional, se ha incluido en el anexo un
apa ado donde se ecopilan aquellas nociones m´as impo an es con las que abaja emos.
5.1. Algunos m´e odos pa a la inicializaci´on de kmedias
Es sabido que kmedias p esen a de iciencias con cie os conjun os de da os, como pueden se
los g upos no es ´e icos, g upos desequilib ados... Sin emba go, no es el ´unico algo i mo al cual le
sucede es o. A la ho a de p egun a nos si exis e un m´e odo de clus e ing que sea mejo que odos
los dem´as, la espues a es nega i a: debido a c´omo se cons uyen los p ocedimien os de clus e ing
y en qu´e es a egia basan su ag upaci´on de indi iduos, siemp e podemos encon a o cons ui un
conjun o de da os que sea comple amen e des a o able pa a halla una ag upaci´on buena u ilizando
un algo i mo en pa icula . Exis en o os algo i mos dis in os de kmedias bien conocidos que en
muchos casos p opo cionan mejo es esul ados que kmedias. Sin emba go, es e es muy popula po
a ias azones:
1. Su implemen aci´on es muy sencilla y es posible cons ui una unci´on kmedias en cualquie
lenguaje de p og amaci´on.
2. Es uno de los algo i mos m´as es udiados, an o de mane a p ´ac ica con di e en es conjun os
de da os como de mane a e´o ica. Exis en pocos p ocedimien os de clus e ing pa a los cuales
se hayan p obado an os esul ados de con e gencia, exis encia, p obabilidad de pun os on-
e a en e clus e s... Es l´ogico p e e i usa un p ocedimien o es udiado exhaus i amen e que
p esen a alguna limi aci´on an es que un algo i mo po encialemn e bueno que puede p esen a
alg´un incon enien e “ocul o” o oda ´ıa no examinado.
3. La ac uaci´on de kmedias mejo a no ablemen e con una buena elecci´on de cen os iniciales,
adem´as de ealizando el p ocedimien o epe idas eces pa a pode elegi la opci´on que m´as
minimiza nues o po encial.
Es po ello po lo que ponemos empe˜no en busca ´ecnicas pa a elegi cen oides iniciales de
mane a in eligen e en luga de simplemen e ealiza un so eo y escoge kpun os como hab´ıamos
hecho has a aho a. Exis en muchos p ocedimien os pa a la inicializaci´on y a a emos de ecoge
algunos de los p incipales. Sus desc ipciones, p incipales en ajas y algunas de sus insu iciencias han
sido ex aidas del a ´ıculo How much can k-means be imp o ed by using be e ini ializa ion and
epea s? [8], donde se ecoge mucha m´as in o maci´on al ensaya el po cen aje de ´exi o que iene cada
algo i mo de inicializaci´on con cada ipo de conjun o de da os.
52

5.1.1. P incipales p ocedimien os pa a la inicializaci´on
Comen a emos algunos de los m´e odos m´as conocidos pa a elegi los cen oides iniciales. Como
hemos comen ado an es, ambi´en es in e esan e epe i kmedias pa a ob ene soluciones di e sas
con di e en es inicializaciones.
Los equisi os que le pedimos a un algo i mo de inicializaci´on son, en e o os, que sea simple
de implemen a , que su complejidad sea como mucho la de kmedias y que no sea necesa io ning´un
pa ´ame o adicional que los que ya enemos pa a pode ejecu a lo. Comen a que la ´ecnica que
es ´abamos lle ando a cabo has a aho a se denomina Random Cen oids y consis e en eo dena
alea o iamen e los da os y escoge los kp ime os.
Random Pa i ion
Consis e en gene a una pa ici´on alea o ia del conjun o de da os y calcula sus cen oides. Su
en aja es que e i a coge pun os no ep esen a i os de la mues a (ou lie s), pe o p o oca una
aglome aci´on de cen oides en la zona cen al del conjun o de da os.
Fu hes Poin Heu is ic
Es e p ocedimien o elige un pun o alea o iamen e de la mues a y lo escoge como cen oide y
a a˜nadiendo el es o. El siguien e cen o de cus e que elijamos se ´a el pun o que m´as dis a
de los cen oides ya elegidos. De es a mane a conseguimos espa ci los cen os, pe o es un
p ocedimien o con endencia a coge ou lie s.
So ing Heu is ic
Consis e en o dena los pun os de la mues a de acue do con un c i e io (Dis ancia al cen o,
densidad, cen alidad, mayo a ianza...) y escoge bien los kp ime os, bien uni o memen e
(pun os en la posici´on N
k)... Funciona adecuadamen e cuando los clus e s es ´an bien sepa ados
y ienen alo di e en e espec o al c i e io de o den que u ilizamos.
P ojec ion Based Heu is ics
Consis e en p oyec a los pun os sob e un eje, como pod ´ıa se po ejemplo una di ecci´on
p incipal (Ui ilizando An´alisis en Componen es P incipales) y pa iciona es e eje en kseg-
men os del mismo ama˜no. A con inuaci´on, se calculan los cen oides de los pun os asociados
a cada segmen o del eje. Es un m´e odo in e esan e cuando los da os ienen una es uc u a
“Unidimensional” (Se en bien ep esen ados en una sola dimensi´on).
Densi y Based Heu is ics
Calcula la “densidad” de cada pun o (Po ejemplo, seg´un cu´an os o os pun os de la mues a
hay en la bola de adio ϵ, di idi en celdas los da os y calcula la can idad de pun os que hay,
calcula la dis ancia media de los pun os a sus k ecinos m´as p ´oximos...). No esul a del odo
in e esan e ya que en dimensiones al as equie e un n´ume o muy ele ado de ope aciones.
Inicializaci´on kmeans++
El p ocedimien o busca elegi los cen os de o ma que pun os m´as alejados de los cen oides
ya escogidos engan p obabilidad m´as al a de se seleccionados. Pa a ello se o o ga una pon-
de aci´on a cada pun o en unci´on de cuan o dis a del cen oide m´as ce cano. Po lo gene al,
mejo a no ablemen e
53
5.2. El p ocedimien o de kmedias++
Una buena inicializaci´on del algo i mo de kmedias pe mi e no solo una con e gencia m´as ´api-
da del m´e odo hacia una soluci´on ap oximada sino una mejo a conside able del e o come ido. El
algo i mo de inicializaci´on que p esen amos a con inuaci´on ue p opues o en 2007 po Da id A hu
y Se gei Vassil i skii como una soluci´on a las ca encias que p esen a el algo i mo de kmedias. El
p ocedimien o de kmedias++ especi ica un p ocedimien o pa a la elecci´on de cen os de clus e
iniciales an es de ejecu a el m´e odo de kmedias como al, pe mi iendo as´ı encon a una soluci´on
“O(log k) compe ei i a” a la soluci´on ´op ima de kmedias.
In ui i amen e, e´ıamos que la expansi´on de los cen oides a la ho a de inicializa el algo i mo
pa ec´ıa una buena idea a in de se capaz de “cub i ” odas las zonas y asigna un cen o de clus e
pos e io men e a cada g upo. Conside emos el siguien e conjun o de da os con 15 g upos y 600
indi iduos en o al (conjun o de da os p esen e en [8]: Shaped Se s, R15 N=600, k=15, D=2). A la
ho a de halla ag upaciones en el es e conjun o de da os, a pesa de se odos los g upos es ´e icos y
bien di e enciados, kmedias lo encuen a muy di icil si inicialmen e no si ´ua un cen oide en cada
uno de los g upos m´as alejados, pues el algo i mo alcanza un m´ınimo local y no desplaza los cen os
hacia esas zonas:
Figu a 25: Ac uaci´on de kmedias an e 15 clus e s di e enciados pe o muy sepa ados
La p egun a adica en onces en c´omo log a implemen a es a idea de espa ci los cen oides de
mane a que sea un p ocedimien o alea o io, consigamos cub i odas las zonas y no caigamos (o al
menos no siemp e) en elegi ou lie s que segu amen e o men g upos po si solos al es a mucho m´as
alejados del es o de pun os. La iloso ´ıa de kmedias ++ se basa en la idea de elegi los cen os
de al mane a que la p obabilidad de coge nue os cen oides alejados de los pun os ya elegidos sea
54
mayo . El algo i mo iene po lo an o las siguien es e apas:
1. U ilizando una a iable alea o ia Xcon dis ibuci´on uni o me, escogemos un cen o en e los
pun os de la mues a.
2. Dada una obse aci´on xde la mues a, se de ine la dis ancia D(x) = ´ın c∈C{d(x, c)}: es deci ,
la dis ancia en e un pun o xy el cen oide m´as ce cano de los que ya hemos seleccionado.
3. Cons uimos la a iable alea o ia Yque o o ga p obabilidad p opo cional a D(x)2a cada pun o
xa´un no escogido.
4. Se epi en los pasos 2 y 3 has a que se hayan seleccionado k cen os.
5. Una ez enemos los cen os iniciales, se p ocede con el m´e odo de kmedias al y como lo
conocemos.
Es un p ocedimien o in e esan e ya que el algo i mo de kmedias con e ge muy ´apidamen e
despu´es de la selecci´on de pun os iniciales y adem´as con conside ables mejo as en las soluciones
ob enidas, ya que imos que kmedias es capaz de gene a soluciones a bi a iamen e peo es que la
soluci´on ´op ima si la elecci´on de cen os iniciales es desa o unada (V´ease el ejemplo de los cua o
pun os).
Al igual que imos que e a ´acil implemen a kmedias en el en o no es ad´ıs ico R, de igual mane a
se ´a sencillo cons ui una unci´on kmedias plus que nos p opo cione kcen os elegidos siguiendo
los pasos desc i os an e io men e. En es e caso, u ilizamos la unci´on sample bien conocida en R
que nos pe mi e ealiza un mues eo con una dis ibuci´on pe sonalizada, en nues o caso, aquella
ponde aci´on que hemos denominado D2. Un posible c´odigo pa a consegui lo se ´ıa el siguien e:
kmedias_plus <- unc ion (da os,k,N){
n<- n ow(da os) # Cu´an as obse aciones enemos
index <- sample(n, size=1)
cen oide <- da os[index,] # So eo pa a elegi el p ime cen o
A<- ma ix(NA,n ow=n ow(da os),ncol=ncol(da os))
H<- ma ix(NA,n ow=k,ncol=ncol(da os))
dx2<- ma ix(NA,n ow=n ow(da os),ncol=1)
#esc ibimos los da os en una ma iz en luga de abaja con da a ames:
H[1,] <- unlis (as. ec o (cen oide))
dis ancia <- ma ix(NA,n ow=n, ncol=k) #dis ancias pun o-cen oide
o (i in 1:n){A[i,]<-unlis (as. ec o (da os[i,])) }
o (i in 2:k){ #Pa a los k-1 cen os es an es
odos<- bind(A,H)
o (s in 1:n){
o (j in 1:k-1){
55
dis ancia[s,j]<- dis ( odos[c(s,n+j),])
}
dx2[s]<- min(dis ancia[s,],na. m=TRUE)^2# Nos quedamos con la m´ınima
}
denominado <- sum(dx2^2)
ponde acion<- dx2/denominado
# Mues eo con dis ibuci´on pe sonalizada:
nue o_cen o<- sample(n, size=1, p ob=ponde acion)
H[i,]<- A[nue o_cen o,] # Tomamos nues o siguien e cen o
}
e u n(H)
}
T as ejecu a es a unci´on y consegui los cen os, s´ımplemen e debe ´ıamos u iliza kmeans o
la e si´on que hab´ıamos elabo ado pa a consegui aplica el p ocedimien o en e o. En el ejemplo
an e io , si u ilizamos la unci´on que acabamos de p esen a pa a elegi los cen os (T i´angulos
neg os en el g ´a ico de la izquie da), obse amos como exis e una endencia muy a o able a coge
cen os de g upos alejados y, con ello, mejo a cla amen e el esul ado:
Figu a 26
De nue o, en R exis en unciones enca gadas de ealiza el p ocedimien o de kmedias++. En
es e caso, se ´a necesa io ins ala la lib e ´ıa lexclus , en la cual encon amos la unci´on kcca. Su
56
As´ı, end ´ıamos que en el caso de coge el cen o en un clus e sin cub i , el alo medio del
nue o po encial es a ´ıa aco ado de la siguien e mane a:
E(Ws+1(H′)|Z= 1) ≤8·Ws
OP T (Xu) + Ws(H, Xc)
b) Si escogemos h′cogemos en un clus e ya cubie o, dado que H⊂H′, end ´ıamos que
E(Ws(H′)|Z= 0) ≤E X
x∈X
m´ın
h∈H∥x−h∥2|Z= 0!=E(Ws(H)|Z= 0) = Ws(H)
Ya que qui a un cen o puede deja Wigual o empeo a la. De es e modo, si alo amos ambos
dos casos, el alo medio del nue o po encial queda aco ado como sigue
E(Ws+1(H′) = P(Z= 0) ·E(Ws+1(H′)|Z= 0) + P(Z= 1)E·(Ws+1(H′)|Z= 1) ≤
≤Pc·Ws(H) + Pu(8 ·Ws
OP T (Xu) + Ws(H, Xc)) ≤Ws(H, Xc) + (8 ·Ws
OP T (Xu) + Ws(H, Xc))
Po lo que queda p obada la desigualdad.
Con es o, es amos en disposici´on de p oba el paso de inducci´on. Supongamos que se cumple la
desiguadad pa a ( −1, u) y pa a ( −1, u −1), y eamos que es cie o pa a ( , u).
Tenemos uclus e s sin cub i y escogemos cen os. Sean A1, .., Aulos clus e s sin cub i , es deci
Xu=∪u
i=1Ai. De mane a simila al paso an e io , deno amos con 0 el suceso “Toma el p ime o de
los cen os en un clus e cubie o” y con ipa a i= 1, .., u el suceso “Toma el p ime o de los
cen os en el clus e sin cub i Ai”. De inimos en onces la a iable alea o ia Zcomo aquella que
oma el alo 0 con p obabilidad Pcy el alo icon p obabilidad PAi=Ws+ (H′,Ai)
Ws+ (H′).
De es e modo, de mane a an´aloga, esc ibimos
E(Ws+ (H′)) = EZ(E(Ws+ (H′))|Z)) = P(Z= 0)·E(Ws+ (H′)|Z= 0)+
u
X
i=1
P(Z=i)·E(Ws+ (H′)|Z=i) =
=Pc·E(Ws+ (H′)|Z= 0)+
u
X
i=1
PAi·E(Ws+ (H′)|Z=i) = PcE(Ws+ (H′)|Z= 0)+Pu
u
X
i=1
E(Ws+ (H′)|Z=i)
Nues a misi´on se ´a aco a E(Ws+ (H′)|Z=i) pa a i= 0, .., u.
Supongamos que hemos omado nues o p ime cen o, h′, en un clus e ya cubie o (Es o
quie e deci que, Z=icon i= 1, .., u). Deno amos po H′′ =H− {h′}.
Resul a que
Ws+ (H′) = X
x∈X
m´ın
h∈H′∥x−h∥2≤X
x∈X
m´ın
h∈H′−{h′}∥x−h∥2=Ws+ −1(H′′)
63

De es e modo, se iene que
E(Ws+ (H′)|Z= 0) ≤E(Ws+ −1(H′′)|Z= 0)
Pe o hemos is o que Ws+ −1(H′′) no depende de h′, po lo que
E(Ws+ −1(H′′)|Z= 0) = E(Ws+ −1(H′′)|“Elijo h′en Xc”) = E(Ws+ −1(H′′))
Pe o Ws+ −1(H′′) es el po encial co espondien e a a˜nadi −1 cen o y ene uclus e s sin
cub i . Po lo an o, nos encon amos en la si uaci´on ( −1, u) y podemos aplica la hip´o esis
de inducci´on:
E(Ws+ (H′)|Z= 0) ≤(Ws(H, Xc)+8Ws
OP T (Xu))(1 + H −1) + u− + 1
u·Ws(H, Xu)
Supongamos que hemos omado nues o p ime cen o en un clus e no cubie o, digamos Ai
(Es o es, Z=icon i= 1, .., u). Sea Yla a iable alea o ia que elige un pun o a∈Aicon
p obabilidad pacomo p ime cen o, es deci , P(Y=a|Z=i). Po lo an o, c1=ay podemos
exp esa el alo medio de Ws+ (H′) sabiendo que elegimos el p ime cen o en el conjun o Ai,
como
E(Ws+ (H′)|Z=i) = EY(E((Ws+ (H′)|Y)|Z=i)) = X
a∈Ai
pa·E(Ws+ (H′)|Y=a)
Es udiamos c´omo aco a E(Ws+ (H′)|Y=a). Deno amos po H′el conjun o de cen os que ya
en´ıamos a˜nadiendo los nue os cen os, H =H∪ {a, c2, .., c }jun o con los nue os cen os
a˜nadidos. Es deci , en es e caso el nue o po encial W′es
Ws+ =X
x∈X
m´ın
h∈H∪{a,c2,..,c }∥x−h∥2
Pa a pode aplica la hip´o esis de inducci´on, conside amos Aicubie o y a˜nadimos aal conjun o
de cen os de clus e ijos, es deci H′′ =H∪{a}. Po lo an o, H′=H′′∪{c2, .., c }. Deno amos
Ws+
a(H′) = Px∈Aim´ınh∈H′′∪{c2,..,c }∥x−h∥2, es deci , la apo aci´on de Aial po encial as
habe a˜nadido aal conjun o de cen os. De es e modo, si adem´as pa imos la suma en Ai,Xc
yXu, enemos
Ws+ (H′) = X
x∈Xc
m´ın
h∈H′′∪{c2,..,c }∥x−h∥2+X
x∈Ai
m´ın
h∈H′′∪{c2,..,c }∥x−h∥2+X
x∈Xu−A
m´ın
h∈H′′∪{c2,..,c }∥x−h∥2
=W(s+1)+( −1)(H′,Xc) + W(s+1)+( −1)
a(H′) + W(s+1)+( −1)(H′,Xu−Ai)
De es a mane a, esul a que el n´ume o cen os ijos es s+ 1, de clus e s sin cub i es u−1 y
el n´ume o de cen os que hemos a˜nadido es −1, po lo que podemos aplica la hip´o esis de
inducci´on. Si lo incluimos en la exp esi´on an e io , end ´ıamos que
X
a∈Ai
pa·E(Ws+ (H′)|Y=a)≤X
a∈Ai
pa·[(Ws(H, Xc) + Ws+
a(H′)+8Ws
OP T (Xu)]−
64
−X
a∈Ai
pa[8 ·Ws
OP T (A)(1 + H −1)] + ·[u−
u−1·(Ws(H, Xu)−Ws(H, Ai))]
Al aplica la p opiedad dis ibu i a y u iliza que Pa∈Aipa= 1, solo al a e qu´e ocu e con
el ´e mino Pa∈AipaWs+
a(H′). Pe o esul a que es exac amen e
X
a∈Ai
paWs
a(H) = X
a∈Ai
pa·E(Ws+
a(H′)) = X
a∈Ai
P(Y=a|Z=i)·E(Ws+
a(H′)|Y=a)
=EY(E(Ws+
a(H′)|Y)|Z=i) = E(W(AiWs+
a(H′)|Z=i)≤8Ws
OP T (Ai)
Siendo la ´ul ima desigualdad consecuencia del lema an e io . As´ı, si ecopilamos las exp esiones,
se iene
X
a∈Ai
pa·E(Ws+ (H′)|Y=a)≤(Ws(H, Xc)+8·Ws
OP T (Xu))(1+H −1)+ u−
u−1·(Ws(H, Xu)−Ws(H, Ai))
As´ı, en la exp esi´on an e io , se iene
u
X
i=1
Ws(H, Ai)
Ws(H)·E(Ws+ (H′)|Z=i)≤
u
X
i=1
Ws(H, Ai)
Ws(H)(Ws(H, Xc)+8·Ws
OP T (Xu))(1+H −1)+
+
u
X
i=1
Ws(H, Ai)
Ws(H)
u−
u−1·(Ws(H, Xu)−Ws(H, Ai))
Dado que la suma de Ws(H, Ai) en odos los clus e s Aino cubie os es Ws(H, Xu), la l´ınea
an e io se esc ibe equi alen emen e como
Ws(H, Xu)
Ws(H)(Ws(H, Xc)+8·Ws
OP T (Xu))(1+H −1)+ u−
u−1
1
W·(Ws(H, Xu)2−
u
X
i=1
Ws(H, Ai)2)
Po la p oposici´on (7), se iene que Pu
i=1 W(Ai)2≥1
uW(Xu)2. Aplicada a es a ´ul ima exp e-
si´on, end ´ıamos que es a se ´ıa igual a
=Ws(H, Xu)
Ws(H)(Ws(H, Xc)+8·Ws
OP T (Xu))(1 + H −1) + u−
u−1
1
Ws(H)(u−1)Ws(H, Xu)2
u
Simpli icando el denominado y sacando ac o com´un a Ws(H,Xu)
Ws(H), lo podemos eesc ibi inal-
men e as´ı
Ws(H, Xu)
Ws(H)Ws(H, Xc)+8·Ws
OP T (Xu))(1 + H −1) + u−
uWs(H, Xu)
65
Hemos conseguido aco a po lo an o, suponiendo que el p ime cen o se escog´ıa en un clus e
cubie o, la exp esi´on
Ws(H, Xc)
Ws(H)·E(Ws+ (H′)|Z= 0) ≤Ws(H, Xc)
W(H)(Ws(H, Xc)+8·Ws
OP T (Xu))(1+H −1)+u− + 1
u·Ws(H, Xu)
Y si po el con a io suponemos que el p ime cen o se escoge en un clus e Aino cubie o, hab´ıamos
is o que
u
X
i=1
Ws+ (H′, Ai)
W·E(Ws+ (H′,|Z=i)≤Ws(H, Xu)
Ws(H)Ws(H, Xc)+8·Ws
OP T (Xu))(1 + H −1) + u−
uWs(H, Xu)
U ilizando que Pu+Pc= 1, ag upando ´e minos y aplicando la p opiedad dis ibu i a, llegamos
a
E(Ws+ (H′)) ≤u−
uWs(H, Xu) + Ws(H, Xc)
Ws(H)Ws(H, Xu)
u
De nue o, si nos cen amos en nues o obje i o p incipal, hab ´ıamos conseguido aco a el alo medio
de Ws+ (H′) po
E(Ws+ (H′)) ≤(Ws(H, Xc)+8·Ws
OP T (Xu))(1+ H −1)+ u−
uWs(H, Xu)+ Ws(H, Xc)
Ws(H)
Ws(H, Xu)
u
Pe o esul a que
Ws(H, Xc)
Ws(H)Ws(H, Xu)≤Ws(H, Xc)≤Ws(H, Xc)+8·Ws
OP T (Xu)
Po lo que, u ilizando que 1
u≤1
, ob enemos el esul ado deseado ag upando 1
yH −1:
E(Ws+ (H′)≤(Ws(H, Xc)+8·Ws
OP T (Xu))(1 + H ) + u−
uWs(H, Xu)
□
G acias a es e lema, podemos inalmen e demos a el eo ema p incipal: El m´e odo de kmedias++
es O−(log k) compe i i o.
Teo ema 8. Si Cse cons uye u ilizando el p ocedimien o de kmedias++, la co espondien e un-
ci´on po encial Wk(H) e i ica que E(Wk(H)) ≤8(ln k+ 2)Wk
OP T
Demos aci´on
Supongamos que solo hemos escogido el p ime cen o de mane a uni o me, de acue do con el
p ime paso de kmedias++. Sea Ael clus e en COP T en el cual hemos escogido el p ime cen o.
En es a si uaci´on, enemos k−1 clus e s de COP T sin cub i . Aplicamos el lema an e io pa a
=u=k−1. De es e modo, como sabemos, la espe anza del nue o po encial se aco a del siguien e
modo
E(Wk(H′)) ≤(Wk(H, Xc)+8·Wk
OP T (Xu))(1 + H )=(Wk(H, A)+8·Wk
OP T (X − A))(1 + Hk−1)
= (E(Wk(H, A)) + 8 ·Wk
OP T (X)−8·Wk
OP T (A))
66
U ilizando el lema (5) , esc ibimos
E(Wk(H′)≤(8 ·Wk
OP T (A)+8·Wk
OP T (X)−8·Wk
OP T (A))(1 + Hk−1) = (8 ·Wk
OP T (X))(1 + Hk−1)
Como Hk−1= 1 + 1
2+1
3+.. +1
k−1≤1 + ln k, llegamos inalmen e a
E(Wk(H′)) ≤(8 ·Wk
OP T (X))(2 + ln k)
Que es lo que que ´ıamos p oba . □
5.2.3. Una co a in e io pa a el p oblema
Acabamos de encon a una co a supe io pa a el alo medio del po encial apo ado po {x1, .., xn}
en elaci´on al po encial ´op imo. Nues a siguien e p egun a se ´a si somos capaces de encon a una
co a in e io . Pa a ello, dise˜na emos un p oblema pa icula en el que el alo medio del po encial se
e ´a aco ado in e io men e.
Nues o p oblema se ´a el siguien e: Vamos a cons ui X={x1, .., xn}un conjun o de npun os,
con ando con kun en e o posi i o y δ, ∆ dos n´ume os posi i os que e i ican n≫ky ∆ ≫δ.
Seguimos los siguien es pasos
1. Elegimos en p ime luga h1, .., hkcen os de clus e ales que ∥hi−hj∥2= ∆2−n−k
nδ2pa a
i=j.
2. Pa a cada cen o hi, a˜nadimos n
kpun os, xi,1, .., xi, n
k, que o men un simplex egula de lado
δ, cen o hiy adio qn−k
2n.
3. Si conside amos una dimensi´on su icien emen e g ande como pa a que los ec o es sean o o-
gonales en e s´ı, enemos que
∥xi,i′−xj,j′∥=δ si i =j
∆si i =j
Ve emos como bajo es as hip´o esis, el algo i mo de kmedias++ no es mejo que 2(ln k)−compe i i o.
Obse aci´on 5. El po encial ´op imo de es e p oblema es exac amen e WOP T =n−k
2δ2, ya que
podemos calcula lo como
Wk
OP T =X
x∈X
m´ın
h∈HOP T
∥x−h∥2=X
x∈X
m´ın
i=1,..,k∥x−hi∥2=X
x∈X
n−k
2nδ2=n·n−k
2nδ2=n−k
2δ2
Ya que los npun os dis an n−k
2nδ2de su espec i o cen o de clus e .
Lema 8. Sea Hun conjun o con k− ≥1cen oides asociados a X. Sea u > 0el n´ume o de clus e s
de COP T sin cub i (No hemos elegido ning´un pun o de Hen ellos). Supongamos que a˜nadimos
cen os {c1, .., c }alea o iamen e a H={h1, .., hk− }, con H′=H∪ {c1, .., c }. Sea Wk− (H′)el
po encial de X as es e p oceso.
Deno amos po
α=n−k2
n, β =∆2−2kδ2
∆2, H′
u=
u
X
i=1
k−i
ki
Bajo es as condiciones, enemos una co a in e io pa a la espe anza del po encial:
E(Wk− (H′)) ≥α +1 nδ2·(1 + H′
u)·β+n
k∆2−2nδ2(u− )(13)
67
Demos aci´on
Al igual que hac´ıamos con el lema de la secci´on an e io , p oba emos el esul ado po inducci´on.
Pa a el caso = 0, enemos escogidos kcen os, odos ellos en e los pun os de X. Adem´as, no
a˜nadimos m´as cen os. De es e modo, podemos esc ibi
E(Wk(H)) = Wk(H) = X
x∈X
m´ın
h∈H∥x−h∥2
Obse emos que hemos seleccionado los cen os hien e los pun os de X. Es o quie e deci que
exis en kpun os x(1), .., x(k) ales que hi=x(i). De es e modo podemos eesc ibi el suma o io como
X
x∈X
m´ın
h∈H∥x−h∥2=X
x∈X
m´ın
i=1,..,k∥x−x(i)∥2=X
x∈Xu
m´ın
i=1,..,k∥x−x(i)∥2+X
x∈Xc
m´ın
i=1,..,k∥x−x(i)∥2
Los pun os de Xuson aquellos pe enecien es a clus e s no cubie os, po lo que no hemos cogido
ning´un cen o ah´ı. Es deci , ∥x−x(i)∥2= ∆2si x∈ Xu∀i= 1, .., k. Como enemos uclus e s sin
cub i con n
kpun os cada uno, esul a que |Xu|=u·n
k, po lo que la con ibuci´on de Xual po encial
es exac amen e X
x∈Xu
m´ın
i=1,..,k∥x−x(i)∥2=u·n
k·∆2
Po o o lado, los pun os en Xcson aquellos pe enecien es a clus e s donde hemos colocado alg´un
cen o. Po ello, ∥x−x(i)∥2=δ2si x∈ Xcy elegimos el iap opiado. El n´ume o o al de pun os en
los clus e s cubie os es |Xc|= (k−u)·n
k, ya que enemos (k−u) clus e s cubie os con n
kpun os
cada uno. Sin emba go, como los cen os x(i)es ´an en Xc ambi´en y dis an 0 de s´ı mismos, pa a
calcula la con ibuci´on de Xcal po encial debemos es a el alo que hemos a˜nadido al conside a
es os kcen os, es deci
X
x∈Xc
m´ın
i=1,..,k∥x−x(i)∥2= (k−u)·n
k·δ2−kδ2
As´ı, si ecopilamos odo es o, podemos a i ma que
Wk(H) = u·n
k·∆2+ (k−u)·n
k·δ2−kδ2=n−u·n
k−kδ2+un
k∆2
Si hemos supues o que u > 0, se cumple que k≥u+ 1, y encadenando desigualdades conseguimos
aco a α:
n−u·n
k−k
n−n
k
≥
n
k−k
n
k
=
n−k2
k
n
k
=n−k2
n=α
De es a mane a, como n−u·n
k−k≥αn−n
ku, se iene
Wk(H) = n−u·n
k−kδ2+un
k∆2≥αn−n
kuδ2+un
k∆2≥αnδ2β−n
kuβδ2+un
k∆2
Siendo es a ´ul ima desigualdad consecuencia de α, β ≤1. Como sabemos que n·u≥u
ku, enemos
que uδ2n≥n
kuβδ2. Aplicando es a desigualdad y iendo que
H′
u=
u
X
i=1
k−i
ki =k−1
k+k−2
2k.. +k−u
2u≤uk−1
k≤u
68

Se iene
αnδ2β+uδ2n−2uδ2n+un
k∆2≥αnδ2β(1 + H′
u) + n
k∆2−2δ2nu
Y con ello, hemos llegado a la desigualdad deseada, comp obando que es cie a cuando = 0:
E(Wk(H)) ≥αnδ2β(1 + H′
u) + n
k∆2−2δ2nu
P ocedemos en onces al paso de inducci´on. Supongamos que enemos uclus e s descubie os y
que a˜nadimos nue os cen os, po lo que enemos k− cen os en H. Sean A1, .., Aulos clus e s
sin cub i , es deci Xu=∪u
i=1Ai. De mane a simila a la demos aci´on del lema an e io , deno amos
con 0 el suceso “Toma el p ime o de los cen os en un clus e cubie o” y con ipa a i= 1, .., u el
suceso “Toma el p ime o de los cen os en el clus e sin cub i Ai”. De inimos en onces la a iable
alea o ia Zcomo aquella que oma el alo 0 con p obabilidad Pcy el alo icon p obabilidad
Wk− (H′,Ai)
Wk− (H′)=PAi.
De es e modo, de mane a an´aloga, esc ibimos
E(Wk− (H′)) = EZ(E(Wk− (H′)|Z)) = P(Z= 0)·E(Wk− (H′)|Z= 0)+
u
X
i=1
P(Z=i)·E(Wk− (H′)|Z=i) =
=Pc·E(Wk− (H′)|Z= 0)+
u
X
i=1
PAi·E(Wk− |Z=i) = Pc·E(Wk− (H′)|Z= 0)+Pu
u
X
i=1
E(Wk− (H′)|Z=i)
Nues a misi´on se ´a aco a E(W′|Z=i) pa a i= 0, .., u.
Supongamos que hemos omado nues o p ime cen o, h′, en un clus e ya cubie o (Es o
quie e deci que, Z= 0). Si H′′ =H− {h′}, esul a que
Wk− (H′) = X
x∈X
m´ın
h∈H′∥x−h∥2=X
x∈X
m´ın
h∈H′−{h′}∥x−h∥2=Wk− +1(H′′)
Ya que hemos a˜nadido un cen o pe enecien e a los clus e s cubie os: los pun os que dis aban
δde los cen oides siguen haci´endolo pues es la m´ınima dis ancia, mien as que los pun os que
dis aban ∆ siguen es ando a es a dis ancia del nue o cen o ya que es e no ha sido escogido en
su clus e . De es e modo, u ilizando que Wk− +1 no depende de h′, enemos
E(Wk− (H′)|Z= 0) = E(Wk− +1(H′′)|Z= 0) = E(Wk− +1(H′′))
Pe o es el po encial co espondien e a a˜nadi −1 cen o y ene uclus e s sin cub i . Po lo
an o, nos encon amos en la si uaci´on ( −1, u) y podemos aplica la hip´o esis de inducci´on:
E(Wk− (H′)|Z= 0) = E(Wk− +1(H′′)) ≥α nδ2·(1 + H′
u)·β+n
k∆2−2nδ2(u− + 1)
Si conside amos la p obabilidad de escoge un cen o en Xc, mul iplicamos y di idimos po
(k− )δ2y emos que g acias a la co a es ablecida an e io men e pa a α, se iene que
n−u·n
k−k
n−n
k
+
n−n
k
≥α
69
Podemos llega a que
Wk− (H′,Xc)
Wk− (H′)=(k−u)·n
k·δ2−(k− )δ2
u·n
k·∆2+ (k−u)·n
k·δ2−(k− )δ2≥α(k− )δ2
u·∆2+ (k−u)·δ2
Supongamos que hemos omado nues o p ime cen o, h′, en un clus e no cubie o, digamos
Ai(Es o es, Z=icon i= 1, .., u). Sea Yla a iable alea o ia que elige un pun o a∈Aicon
p obabilidad pacomo p ime cen o, es deci , P(Y=a|Z=i). Po lo an o, c1=ay podemos
exp esa el alo medio de Wk− (H′) sabiendo que elegimos el p ime cen o en el conjun o
Ai, como
E(Wk− (H′)|Z=i) = EY(E((Wk− (H′)|Y)|Z=i)) = X
a∈Ai
pa·E(Wk− (H′)|Y=a)
En p ime luga , obse amos que pa=P(Y=a|z=i) es la misma pa a odos los pun os de
Ai, ya que odos dis an ∆ de los cen os de clus e ya elegidos. Como en cada Aihay n
kpun os,
la p obabilidad de elegi uno de ellos se ´a 1
n
k=k
n.
Es udiamos en onces c´omo aco a E(Wk− (H′)|Y=a). Conside amos Aicubie o y a˜nadi-
mos aal conjun o de cen os de clus e ijos: H′′ =H′∪ {a}. Tenemos que el po encial se ´ıa
Wk− (H′) = X
x∈X
m´ın
h∈H∪{a,c2,..,c }∥x−h∥2=u·n
k·∆2+ (k−u)·n
k·δ2−(k− )δ2≥
≥(u−1) ·n
k·∆2+ (k−u+ 1) ·n
k·δ2−(k− + 1)δ2
En es a si uaci´on, podemos aplica la hip´o esis de inducci´on (caso (u−1, −1)) y a i ma que
E(Wk− (H′)|Y=a)≥α nδ2·(1 + H′
u−1)·β+n
k∆2−2nδ2(u− )
As´ı, si in oducimos es o en la exp esi´on an e io
X
a∈Ai
pa·E(Wk− (H′)|Y=a) = X
a∈Ai
k
n·E(Wk− (H′)|Y=a)≥α nδ2·(1 + H′
u−1)·β+n
k∆2−2nδ2(u− )
Ya que Ai iene n
kpun os, lo que p o oca que el suma o io Pa∈Ai
k
nsea 1.
Si es udiamos cual es la p obabilidad de escoge el cen o en e los pun os Xu, llegamos a que
Wk− (H′,Xu)
Wk− (H′)=u·n
k·∆2
u·n
k·∆2+ (k−u)·n
k·δ2−(k− )δ2≥αu·∆2
u·∆2+ (k−u)·δ2
T as el es udio de ambos casos, ecopilamos los esul ados ob enidos en la exp esi´on p incipal:
E(Wk− (H′)) = (k− )δ2
u·∆2+ (k−u)·δ2·α +1 nδ2·(1 + H′
u)·β+n
k∆2−2nδ2(u− + 1)+
70
+u∆2
u∆2+ (k−u)δ2·α +1 nδ2·(1 + H′
u−1)·β+n
k∆2−2nδ2(u− )
Sepa ando los ´e minos del p ime sumando pa a pode ag upa y u ilizando que
H′
u−H′
u−1=k−u
uk , as unas cuen as algo pesadas pe o simples, log amos e que
E(Wk− (H′)) ≥α +1 nβδ2(1 + H′
u) + n
k∆2−2nδ2(u− )
Que coincide con el esul ado deseado (13), po lo que hemos concluido.
□
De es a mane a, log amos p oba el esul ado deseado:
Teo ema 9. La ponde aci´on D2no es mejo que 2(ln k)−compe i i a.
Supongamos que cons uimos una pa ici´on en clus e s Ccomo hemos desc i o an e io men e.
Vamos a aplica el lema con u= =k−1 as elegi el p ime cen o. Dado que 1+H′
k−1=Hk>ln k,
se iene que
E(Wk(H′)) ≥αkβδ2ln k
Fijamos odos los ´e minos sal o ∆ y n, que hacemos que iendan a in ini o. Resul a que
l´ım
∆→∞ α= l´ım
∆→∞
n−k2
n= 1,l´ım
∆→∞ β= l´ım
∆→∞
∆2−2kδ2
∆2= 1
Po es a azon, haciendo ende ∆, n → ∞ en ambos lados y eco dando que Wk
OP T =n−k
2δ2, se
iene que
E(Wk(H′)) ≥nδ2ln k=n
n−k2Wk
OP T ≥2(ln k)Wk
OP T
Con lo que conseguimos el esul ado deseado.
5.2.4. Algunas gene alizaciones
Como hemos comen ado, en el es udio pa icula de kmedias++, hemos u ilziado ∥x−h∥2como
medida de disimila iad en e pun os. Los esul ados p obados en las dos subsecciones an e io es
pueden se gene alizados en el caso de minimiza un po encial Wk,[l](H) = Px∈X m´ınh∈H∥x−
h∥l, con l≥1. Lo ´unico que debemos hace en es e cso es u iliza la ponde aci´on Dl, es deci , la
p obabilidad de elegi x0como nue o cen o se ´ıa D(x0)l
Px∈X D(x)l. Se pueden p oba en onces unos lemas
an´alogos a los que hab´ıamos p esen ado p e iamen e, ob eniendo:
El alo espe ado del po encial al escoge el p ime cen o en A∈COP T se aco a como
E(W1,[l](H), A)≤2lW1,[l]
OP T (A)
Si Cse cons uye con la ponde aci´on Dl, el co espondien e po encial sa is ace
E(Wk,[l](H′)) ≤22l(ln k+ 2)Wk,[l]
OP T
71
5.2.5. Ejemplos de la aplicaci´on de kmedias++
Aho a que quedan es udiadas las bases e´o icas que nos pe mi en aco a el alo medio del
po encial que ob enemos inicializando los cen os con kmedias++, abo da emos la ag upaci´on de
los conjun os de da os que esul aban p oblem´a icos pa a kmedias y e emos has a que pun o k
medias++ log a enmenda es os e o es.
Ca encias no esuel as po kmedias++
El algo i mo que hemos desc i o solo busca una o ma m´as cohe en e de elegi los cen os, po
lo que no podemos espe a mejo as muy no ables en conjun os de da os cuya di icul ad pa a
se clasi icados adicaba en la na u aleza no es ´e ica de sus g upos. Po ejemplo, si obse amos
qu´e ocu e con conjun os de da os como “Espi al”:
Figu a 28: No exis e una mejo a pe cep ible en la ag upaci´on de es e conjun o de da os po k
medias++
O como aquellos con g upos en apa iencia “ala gados” que obse ´abamos an es, nos damos
cuen a de que siguen sin se ag upados co ec amen e con kmedias++ ( e [8]: Syn he ic 2-d
Gaussian clus e s o es skewness, N=1000, k=6):
Figu a 29: No exis e una mejo a pe cep ible en la ag upaci´on de es e conjun o de da os po k
medias++
72
Algo i mo con complejidad polin´omica: La asa de c ecimien o de su cos e espec o al ama˜no
de la en ada (n) es del o den de O(nk) pa a alguna cons an e k.
Algo i mo con complejidad exponencial: La asa de c ecimien o de su cos e espec o al ama˜no
de la en ada (n) es del o den de 2O(nk)pa a alguna cons an e k.
De es a o ma, somos capaces de ag upa los p oblemas en clases de complejidad. Denominamos
clase P al conjun o de los p oblemas esolubles en iempo polin´omico. Denominamos clase NP al con-
jun o de odos los p oblemas e i icables en iempo polin´omico (es deci , dada una posible soluci´on,
es a se puede e i ica en un iempo polin´omico po una m´aquina de Tu ing). La clase NP-Ha d es
aquella que con iene a los p oblemas de decisi´o que son como m´ınimo an di iciles como un p oblema
de NP. El algo i mo de kmedias al que hacemos e e encia en el documen o pe enece a es a clase.
Po o o lado, el An´alisis Compe i i o es la disciplina enca gada del es udio de la ac uaci´on de
un algo i mo en una ins ancia de un p oblema en compa aci´on con el compo amiendo del algo i mo
en el ´op imo. Decimos que un algo i mo es “compe i i o” si la az´on en e su compo amien o en un
caso cualquie a y en el caso ´op imo es ´a aco ada. En es e documen o a i ma emos que “El m´e odo
de kmeans++ es O(log k)−compe i i o a la soluci´on ´op ima de ag upamien o en clus e s”. Es a
noci´on no a a la complejidad del algo i mo, sino que a a de e c´omo de e ec i o es y cu´an o
puede aleja se como mucho del alo ´op imo de una ins ancia. Sabemos que el obje i o de kmedias
es minimiza Wk. La a i maci´on an e io po lo an o quie e deci que el k-po encial espe ado de
una soluci´on p opo cionada po kmeans++ es como mucho 8(ln k+2) eces el po encial de la mejo
soluci´on posible.
79

Re e encias
[1] Bholowalia, P., and Kuma , A. (2014). EBK-means: A clus e ing echnique based
on elbow me hod and k-means in WSN. In e na ional Jou nal o Compu e Applica ions,
105(9).
[2] Billingsley, P. (2013). Con e gence o p obabili y measu es. John Wiley and Sons.
[3] Cues a-Albe os, J. A., Go daliza, A., Ma ´
an, C. (1997) T immed c-means
and he Cauchy mean alue p ope y. New T ends in P obabili y and S a is ics, 3, 247-
265.
[4] Cues a-Albe os, J. A., Go daliza, A., Ma ´
an, C. (1997). T immed k-means:
an a emp o obus i y quan ize s. The Annals o S a is ics, 25(2), 553-576.
[5] Cues a, J. A., Ma ´
an, C. (1988). The s ong law o la ge numbe s o k-means and
bes possible ne s o Banach alued andom a iables. P obabili y heo y and ela ed
ields, 78(4), 523-534.
[6] D. A hu , S. Vassil i skii (2006). k-means++: The Ad an ages o Ca e ul Seeding.
S an o d, 2006.
[7] Dudek, A. (2019, Sep embe ). Silhoue e index as clus e ing e alua ion ool. In Con-
e ence o he Sec ion on Classi ica ion and Da a Analysis o he Polish S a is ical As-
socia ion (pp. 19-33). Sp inge , Cham.
[8] F ¨
an i, P., Sie anoja, S. (2019).How much can k-means be imp o ed by using be e
ini ializa ion and epea s?. Pa e n Recogni ion, 93, 95-112.
[9] Ha igan, J. A. and Wong, M. A. (1979).Algo i hm AS 136: A k-means clus e ing
algo i hm.. Jou nal o he oyal s a is ical socie y. se ies c (applied s a is ics), 28(1),
100-108.
[10] Jain, A. K. (2010).Da a clus e ing: 50 yea s beyond K-means. Pa e n ecogni ion
le e s, 31(8), 651-666.
[11] MacQueen, J. (1967, June).Some me hods o classi ica ion and analysis o mul i-
a ia e obse a ions. In P oceedings o he i h Be keley symposium on ma hema ical
s a is ics and p obabili y (Vol. 1, No. 14, pp. 281-297).
[12] Polla d, D. (1981). S ong consis ency o k-means clus e ing.The Annals o S a is ics,
135-140.
[13] Se ling, R. J. (2009). App oxima ion heo ems o ma hema ical s a is ics. John
Wiley and Sons.
[14] Tibshi ani, R., Wal he , G., and Has ie, T . (2001).Es ima ing he numbe o
clus e s in a da a se ia he gap s a is ic. Jou nal o he Royal S a is ical Socie y: Se ies
B (S a is ical Me hodology), 63(2), 411-423.
80
[15] Va ada ajan, V. S. (1958). On he con e gence o sample p obabili y dis ibu ions.
The Indian Jou nal o S a is ics (1933-1960), 19(1/2), 23-26.
[16] Yamamo o, W., Shinozaki, N. (2000). On uniqueness o wo p incipal poin s o
uni a ia e loca ion mix u es. S a is ics and p obabili y le e s, 46(1), 33-42.
81