El método de k-medias

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