PROBLEMAS
DE
CLASIFICACIÓN
Y
OPTIMIZACIÓN
Po el
D .
EMILIO CARRIZOSA PRIEGO,
P o eso
Ti ula de Es adís ica e In es igación Ope a i a
y P emio del año 1998 de la Real Maes anza
de Caballe ía pa a In es igado es Jó enes.
Con e encia p onunciada el día
12
de
ma zo
de 2003
ABSTRACT
El desa ollo de écncias que pe mi an clasi ica en es (se es i os, elemen os, p o-
blemas, ... ) en dis in as ca ego ías ha sido ecu en e en di e sas amas del sabe .
La
c eación y di usión de g andes bases de da os y la consiguien e necesidad de
ex ae conocimien o de las mismas han e i alizado
el
in e és de la comunidad cien-
í ica po ales écnicas.
En es as páginas se ilus a
cómo
la
P og amación Ma emá ica
puede
con ibui
al diseño de mé odos au oiná icos de clasi icación y p o undiza en el conociinien o
eó ico de los mismos. Nues a in ención no es hace una e isión co nple a del es ado
del a e en el en1a, sino más bien desc ibi some amen e las apo aciones que en esle
campo se es án ealizando
en
el seno del g upo PAi FQM-809 y
en
el p oyec o de
in es igación BFM2002-04525-C02-02 del MCYT.
Palab as cla e: P og amación Ma emá ica. Análisis Disc iminan e.
1.
INTRODUCCIÓN
A endiendo
al
Dicciona io de la Real Academia Española de la Lengua, clasi ica-
ción es la acción de dispone u o dena en es en clases.
No
acla a
el
Dicciona io qué p opiedades sa is acen las clases
en
las que deben
dispone se los en es
en
cues ión. Noso os supond emos que es as clases cons i uyen
una pa ición del conjun o y nos es ingünos po consiguien e a la clasi icación ní ida,
po con aposición a los mé odos basados en conjun os bo osos.
Tampoco acla a el Dicciona io si las clases deben c ea se (a i icialmen e) en
el
p oceso mismo de clasi icación o po
el
con a io exis en p e iamen e.
De
hecho am-
bas posibilidades han sido ampliamen e es udiadas en la li e a u a, y p opo cionan una
clasi icación de los p oblemas de clasi icación.
227
Real Academia Se illana de Ciencias Memo ias 2002-2003
-
--------
En
el
p ime caso habla emos de clasi icación no supe isada, e.g. [13, 16,
17):
debe de e mina se una pa ición de modo que los elemen os que queden en la misma
clase de la pa ición sean homogéneos, mien as que los elemen os de clases dis in as
engan ca ac e ís icas dispa es, donde los concep os de homogeneidad y dispa idad
debe án se de inidos o malmen e.
En
el
caso en el que las clases de la pa ición es én de inidas p e iamen e habla e-
mos de p oblemas de clasi icación supe isada, e.g. [12, 15, 21), y el obje i o pe se-
guido
es
cons ui una egla que asigne cada obje o a la clase a la que pe enece.
P oblemas de los dos ipos apa ecen, jun os o sepa ados, en los más a iados cam-
pos. Como ilus ación, en el ecien e ex o [18)
se
desc iben aplicaciones en á eas
ales como Ma ke ing, Telecomunicaciones, Banca, Medicina, Fa macología, Gené ica,
In o má ica, Educación, e c.
2,
PLANTEAMIENTO GENERAL
Se conside a un conjun o de obje os, (la población) y dos unciones sob e
G = G
X=
X.
G
es
un conjun o ini o, que llama emos de e ique as, e induce una pa ición de la
población es un conjun o ini o de clases. Di emos que G(o) E
G
es la clase de
la
pa ición a la cual el obje o o E pe enece.
Po o o lado, X(o) ep esen a,
en
un
sen ido que p ecisa emos después, una
se ie de ca ac e ís icas, cuan i a i as o cuali a i as, del obje o
o.
Llama emos po eso
X espacio de ca ac e ís icas, y end emos en cuen a asimismo que X suele eni exp e-
sado como
un
subconjun o de un p oduc o ini o de espacios,
II
' ( 1)
donde cada ep esen a el conjun o de alo es que puede oma la i-ésima p opiedad
o ca ac e ís ica obje o de es udio. Como ilus ación podemos menciona los casos clá-
sicos, = R si la i-ésima a iable es cuan i a i a o ... pa a a iable cuali-
a i as, los que podemos añadi o os más
ecien es y
mo i ados
po las aplicaciones,
como
Xi=
R que modela la posibilidad de que
el
alo de la i-ésima p opiedad
sea desconocido, o
X.
es un aespacio de se ies empo ales, o de dis ibuciones de e-
'
cuencias sob e un conjun o
Kj
de en es (pa a modela e.g. la ecuencia ela i a de
apa iciones de cada una de las palab as de
en
una página web).
Una unción
se
dice egla de clasi icación sob e
228
Emilio Ca izosa P iego
Se iene un subconjun o. ini o no acío de obje os e que llama emos mues-
a
de
ap endizaje. Conociendo las unciones
G,
X es ingidas a
se
desea cons ui
una egla de clasi icación : G con
un
doble obje i o (desc ip i o y p edic i o):
l.
Clasi ica co ec amen e odos los obje os de
la
meu a de ap endizaje, i.e.,
esol e la ecuación uncional
= G(o)
(2)
2. Clasi ica co ec amen e odos los obje os de la población, i.e., esol e la ecua-
ción uncional
= G(o) (3)
No
se
asumen p opiedades de inyección sob e la unción X, po lo que la ecuación
(2)
puede no ene solución. Como solo
se
dispone de las imágenes de las unciones G
y X sob e los obje os de
la
mues a de ap endizaje, en ningún caso hab á ga an ías de
pode clasi ica co ec amen e odos los obje os de la población.
En es as ci cuns ancias, hab á que en ende la esolución de (2) y (3) como la bús-
queda de una egla de clasi icación que las iole mínimamen e.
Pa a da sen ido p eciso a lo an e io , in oducimos una unción de cos o C : x
R+,
donde
C(1 ,o)
ep esen a
el
cos o incu ido po clasi ica en la clase
c(X(o))
el obje o
o.
Englobando a ios modelos de unción de cos o exis en es en la li e a u a, exp esa-
mos C a a és de disimila idades a las egiones clasi icadas median e con la misma
e ique a: Pa a cada g G sea
dg
una disimila idad sob e
X,
i.e., d : X x
Res
una
g
unción no nega i a con d (x,x) No imponemos ninguna es icción sob e
la disimila idad d , que puede se e.g. una mé ica bina ia,
dg(x,z)
= {
O,
si
x z
(4)
pa a >
O,
una mé ica inducida po un calib ado ,
como
se e á en
la
sección 3, o, en
g
el
caso de espacio de ca ac e ís icas de inidos a a és de
(1
), cons uido combinando
disimila idades en los e.g. [9, 17].
De inase la unción de cos o C como:
= (X(o), {x E
X:
=
G(o)))
= in : = G(o)}
(5)
Po ejemplo, pa a la mé ica bina ia ( 4
),
la unción de cos o C adquie e la onna:
229
Real
Academia
Se illana de Ciencias -Me,no ias 2002-2003
{
si
"G(o)
O,
si
= G(o) (6)
Cada egla de clasi icación¡¡ lle a asociado el ec o de cos os
cuya o-ésima coo denada
da
el cos o incu ido
al
clasi ica o median e
La
búsqueda
de
eglas de clasi icación con cos os de clasi icación pequeños sob e
puede o maliza se como el p oblema de op imización mul iobje i o.
(7)
donde la minimización hay que en ende la en con espec o
al
o den pa cial na u al,
y e es el conjun o de eglas de clasi icación pe mi idas.
En la p ác ica sus i ui emos el p oblema mul iobje i o (7) po alguna escala ización
del mismo, esol iendo
en
luga de (7) el p oblema escala
min
(8)
pa a
una
cie a E
En
pa icula , con una unción de ag egación lineal se ob iene
min I (9)
pa a unos cie os posi i os con suma
l,
que con ie en
(9)
en el p oblema de mi-
nimiza el cos o en
un
elemen o seleccionado alea o iamen e ( con p obabilidades
de
Ob iamen e, (9) no
es
la única escala ización posible o azonable de (7). Como
ejemplo, ambién podemos segui
el
en oque minimax,
min max (10)
Obsé ese que en la exp esión an e io ,
al
igual que en odas las que siguen, los
e o es se conside an solo sob e la mues a de ap endizaje. El compo amien o sob e
de la egla de clasi icación así ob enida es,
en
p incipio, imp e isible: los da os
disponibles no son, en muchas ocasiones, expe imen ales, sino obse acionales.
Pueden segui se dos es a egias de ap oximación
al
p oblema sob e el en oque
minimax, en el que se explo a el peo caso, y se de i an co as pa a el e o de la "peo "
ex ensión, e.g. [l2J; como al e na i a, podemos segui un en oque mues a!, suponiendo
que es una mues a ale o ia de la población donde el mecanismo de gene ación
alea o ia es conocido, e.g. es
un
mues eo alea o io simple, o
un
1nues eo es a i icado
con p obabilidades de gene ación en cada es a o (g upo) conocidas o es imadas.
230
Emilio
Ca izosa P iego
3.
CLASIFICADORES
LINEALES
Conside a emos en es a sección el caso más sin1ple en el que el espacio X en el
que se ep esen an las ca ac e ís icas de los obje os medidas po X es
RP,
que sólo hay
dos e ique as, G =
{g
1, g2
),
y que el epsacio de eglas de clasi icación pe mi idas
se educe al conjun o de eglas de inidas po
un
hipe plano: Cualquie hipe plano en
di ide a és e en dos egiones (un semiespacio ce ado y su complemen a io) que
podemos iden i ica con las egiones en las que la egla
de
clasi icación oma espec-
i amen e los alo es g1 y g2•
Las hipó esis an e io es son, e iden emen e, es ic i as. No obs an e, la cons uc-
ción de clasi icado es lineales pa a dos g upos puede usa se co no sub u ina pa a la
cons ucción de clasi icado es no lineales pa a un núme o a bi a io de g upos. En
e ec o, la sepa ación de a ios g upos puede ealiza se median e
un
p oceso secuencial
en el que en cada i e ación se sepa an dos g upos, cons i uidos po a ios g upos. El
lec o puede encon a e.g. en [4) más de alles y e e encias sob e la implan ación de
es os mé odos.
Pa a la cons ucción de clasi icado es no lineales, una es a egia muy exi osa en
las aplicaciones p ác icas
se
basa en ealiza una inme sión (no lineal) de en
un
espacio R de mayo dimensión. Se conside an en onces las eglas lineales o,
q
que dan luga a eglas no lineales E canónicamen e:
(11)
co no se desc ibe e.g. en [ 1
O].
De inamos
'!é
1 {O}) x R. Pa a cada pa (µ,B) E conside emos los
se niespacios e hipe planos
= H#(µ,B)
{x
(u;x) #
con#E
Pa a cada se ob iene la egla de clasi icación
si x E (12)
si
x
Siguiendo a [19), en la de inición de la unción de cos os C de (4), imponemos
que las disimila idades ienen inducidas po calib aciones en e.g. [22). En o as
palab as, se iene
un
conjun o coinpac o con eso B C con eniendo al o igen en su
in e io de modo que
d(x,y) = (13)
231

Real Academia Se illana de Ciencias -Memo ias 2002-2003
donde y
es
el calib ado con bola unidad B,
y(x)=min
B)
Se iene en onces, e.g. [24],
es
el
calib ado dual de
y,
y(s)+ max{s,O).
De es a o ma,
el
p oblema mul iobje i o (7) puede e o mula se como
min
((
((X(o);u)-B)'
donde
G(o)=g),i=
1,2.
' '
(B-(X(o);u))'
(14)
(15)
(16)
Es e p oblema gua da una cie a analogía o mal con el p oblema mul iobje i o
abo dado en
[5]
en el que
se
minimizaban simul aneamen e las dis ancias e icales en
un p oblema de eg esión. Sin emba go, mien as que en el caso de la eg esión e ical
el
p oblema mul iobje i o e a poliéd ico (lineal a ozos y con exo), en es e caso,
el
obje i o asociado a cada o E
es
el cocien e de dos unciones con exas homogéneas,
apa en emen e sin p opiedad de con exidad alguna. Una desc ipción de las soluciones
e icien es de (16), como la ob enida en [5], sigue siendo un p oblema abie o.
El
g ado de conocimien o sob e
el
p oblema es mayo en las escala izaciones de
(7). En e ec o, el p oblema (9)
se
con ie e en pa icual en
min
in oducido en [19].
((X(o);u)-B)'
(B-(X(o);u))'
(17)
Es e p oblema gua da g an pa alelismo,
no
solo o mal, con el p oblema de de e -
minación de un hipe plano mediano en :
un
hipe plano que minimiza la suma de las
dis ancias (medidas con el calib ado y) a un conjun o de pun os dados de dimensión
máxima, e.g. [23, 26]. Pa a el p oblema de de e minación de hipe planos medianos,
en [24]
se
descompone el espacio en egiones poliéd icas en las cuales la unción
a minimiza es cuasicónca a o suma de dos cuasicónca as; se iene, [7], que exis e
una
solución
en
una
ca a ce o- o uno-dimensional espec i amen e de alguno
de
los
poli opos an e io es, que
se
co esponden a hipe planos que pasan po p o
p-1
pun os
a ínmen e independien es.
232
Emilio Ca izosa P iego
El
mismo ipo de descomposición del espacio
es
álido pa a
el
p oblema (17), pa a
el
que se p ueba en [25] que, bajo débiles condiciones, exis e una egla de clasi icación
óp ima, gene ada po un hipe plano que con iene a
p-1
pun os a ínmen e independien-
es de cuando y
es
un calib ado a bi a io, inc emen ándose es e núme o a p cuando
es
una no ma.
Una es a egia de esolución es álida p a la escala ización
(l
0), que en es e caso
se con ie e en
min max
(max
max
))
. (18)
Un hipe plano cen o es un hipe plano que minimiza la máxima de las dis ancias a
un
conjun o de pun os, e.g. [26, 27]. En
[8]
se
ealiza una linealización pa cial de los
obje i os, ans o mando
el
p oblema (localmen e) en uno de minimiza una unción
cuasicónca a.
De
es a mane a llegan a p oba que, cuando los conjun os no son
linealmen e sepa ables y
de
dimensión máxima, exis e un hipe plano óp imo al que
el
núme o de pun os sob e él o a dis ancia igual
al
alo óp imo, es
al
menos
p+
1.
En
el caso en que el calib ado sea una
no ma,
además podemos ga an iza que es os
p+
1
pun os son a ínmen e independien es.
4.
MODELOS BASADOS
EN
PROTOTIPOS
Los mé odos desc i os p e iamen e explo an ue emen e
el
hecho de que
el
espacio
X de ca ac e ís icas, con la ep esen ación
(1
),
es
RP.
Cuando no es ese
el
caso, o os
mé odos, que no es én basados en la esc uc u a de espacio ec o ial de
R",
pueden se
más ap opiados.
Uno de es os mé odos
es
el
basado
en
la
gene ación de p o o ipos pa a las dis in as
clases g E
G,
como
se
ha desc ío en [ 6, 20].
Se iene una disimila idad d : X X
X-,
R.
De cada clase g E G
se
iene un conjun o
P,
C C) de candida os a p o o ipos ( ep esen an es) de la clase
g.
Como espacio de eglas de clasi icación n
se
conside a
el
siguien e: cada subcon-
jun o P e u P de k p o o ipos con odas las clases ep esen adas,
se
iden i ica con
la
g g
egla de clasi icación
P
al
ecino más p óximo, [11],
(x)
= G(a g min { d(x,X(o)) : o E y
P,
}
),
(19)
donde los empa es se ompen median e
un
c i e io p ees ablecido.
Pa a la es uc u a de cos es (6) inducida po la mé ica bina ia (4), en [6,20] se de-
mues a que
el
p oblema (9)
es
NP-du o, aunque
es
posible o mula lo como
un
p oble-
ma de p og amación lineal en núme os en e os, esoluble exac amen e pa a p oblemas
de amaño muy educido, o ap oximadamen e median e heu ís icas pa a p oblemas de
mayo amaño.
233
Real Academia Se illana
de
Ciencias -Memo ias 2002-2003
5. CLASIFICACIÓN Y
REGRESIÓN
Es posible ace ca se a los p oblemas de clasi icación desde la eg esión y la es ima-
ción pa amé ica.
Tal
es
el caso de mul i ud de mé odos basados
en
hipó esis dis ibu-
cionales (e.g. no malidad)
de
los da os. como ocu e en el clásico y po en e mé odo de
Fishe , [14]. o en (gene alizaciones de) la eg esión logís ica, que desc ibimos.
Supone nos que, si
un
obje o iene ca ac e ís icas
x,
en onces és e p o iene del g u-
po
g E G con una p obabilidad
P/ÍJ,x)
donde
ÍJ
=
(ÍJ
8
),,,G
es
un
ec o de pa áme os.
Impone nos
una
o ma sepa able, sal o cons an es mul iplica i as, pa a
Pg,
i.e.
dando luga a
. /ÍJ<'x)
P/ÍJ,x)
=
-------
L,, G
. ,.(Í1,,x)
(20)
(21)
En caso pa icula más no o io es el de la eg esión logís ica, en el que se supone
X =
RP
y se hace en (20)
(22)
donde(·;·) deno a el p oduc o escala usual.
El conjun o de obje os O
se
en iende en onces como
una
ealización del expe imen-
o alea o io egido po la ley an e io , de modo que su e osimili ud conjun a L({J;X))
iene dada po
L({J;cJ) = n
Pc ,,,
(ÍJ,X(o)), (23)
oEG
donde los empa es, caso de exis i , se ompen con
un
mecanismo p e ijado.
El espacio
de
eglas de clasi icación conside ado n iene pa ame izado a a és de
ÍJ
: pa a cada
1}
se de ine la egla de asignación
al
g upo más p obable como
= a g max (24)
Como es desconocido,
se
p opone la egla de máxima e osimili ud iden i-
icada con
un
es imado de máxima e osimili ud pa a ob enido maximizando
como se de inió en (23):
max log
(25)
234
E,nilio Ca izosa P iego
-----------------
--
------
De iniendo la unción
de
cos o C como
C(n,o) = log (n,X(o)),
(26)
el p oblema de de e minación de la egla de máxima e osimili ud (25) apa ece como
el p oblema de de e minación de la egla de mínimo cos o, como se de inició en (8).
El p oblema (25), en gene al mul imodal, debe á se esuel o numé icamen e. Mien-
as que
un
óp imo local puede se ob enido con los p ocedimien os usuales de bús-
queda local, pa a la op imización global se án necesa ias écnicas más so is icadas.
En pa icula , bajo débiles hipó esis adicionales en el modelo (20), podemos u iliza
mé odos de op imización d.c., como los desc i os en [1,2,3]. Pa a ello, suponemos que
las unciones E --, log(
,x))
son d.c. pa a cada x E es o es,
log( ,x)) =
,x)),
gg
(27)
donde, pa a cada x E las unciones son con exas
(y
noso os supo-
nemos que conocidas). En onces, sencillas manipulaciones algeb aicas nos lle an a
pode exp esa la unción obje i o de (25) como donde y son
las unciones con exas
=
X(o))
X(o)))
+
X(o)))
X(o)))
X(o))
.
Pa a una es uc u a poliéd ica de el p oblema (25) puede esol e se e.g. po
ap oximación ex e io .
REFERENCES
BLANQUERO,
R.
Localización de se icios en el plano median e écnicas de op imización
d.c.
Tesis Doc o al. Uni e sidad de Se illa, 1999.
[2]
BLANQUERO,
R.
y
E.
CARRIZOSA. "On co e ing me hods o D.C. op imiza ion", Jou nal
o
Global Op imiza ion 18, 265-274, 2000.
[3]
BLANQUERO, R
..
E.
CARRIZOSA y E. CONDE. "Finding GM-es ima o s wi h Global-Op imi-
za ion echniques", Jou nal
o Glohal
Op imiza ion 21, 223-237, 2001.
[4]
BOCK, H.H. "Classi ica ion me hodology", en Handhook
o
da a
mining
and knowledge disco-
e y,
W.
Klósgen and J.M. Zy kow (Eds.), Ox o d, Ox o d Uni e si y P ess, 258-267, 2002.
[5]
CARRIZOSA, E.,
E.
CONDE, F.R. FERNÁNDEZ,
M.
MUÑOZ y
J.
PUERTO. "Pa e o-Op i-
mali y in Linea Reg ession", Jou nal
o
Ma hema ical Analysis
and
Applica ions l 90, 129-141,
1995.
235