clustering
DESCRIPTION
Exposición de Inteligencia ArtificialAlex GonzagaCarlos RomanLuis FeijooTRANSCRIPT
UNIVERSIDAD TECNICA PARTICULAR DE LOJA“La Universidad Católica de Loja”
INTELIGENCIA ARTIFICIAL AVANZADA
CLUSTERING
CLASIFICACIÓN: ANÁLISIS DE CLUSTERS (CLUSTERING)
INTRODUCCION
El Análisis de Clusters (o Análisis de conglomerados) es una técnica de Análisis Exploratorio de Datos para resolver problemas de clasificación. Su objeto consiste en ordenar objetos (personas, cosas, animales, plantas, variables, etc, …) en grupos (conglomerados o clusters) deacuerdo a carcteristicas que asemejan a los diferentes objetos
ETAPAS DE UN ANÁLISIS CLUSTER
1) Elección de las variables2) Elección de la medida de asociación3) Elección de la técnica Cluster4) Validación de los resultados
Elección de variables
Variables:♦ Variables cualitativas
Ordinales (ej: nivel de estudios)Nominales (ej: nacionalidad)
♦ Variables cuantitativasVariables discretas (ej: número de hermanos)Variables continuas (ej: peso)
ANÁLISIS CLUSTER POR VARIABLES O POR INDIVIDUOS
Un paso importante en cualquier agrupación consiste en seleccionar una medida de distancia , lo que determinará la forma en la similitud de los dos elementos que se calcula. Esto influirá en la forma de los clusters, ya que algunos elementos pueden estar cerca o lejos el uno del uno otro en función de una distancia.
1.Distancia Euclidea
Elección de una medida de asociación
21
),(
yxyxyxd
21
1
2
n
iii yx
2. Distancia de Minkowsky (q >=1)
q=2distancia euclideaq=1distancia ciudad
3. Distancia Valor Absoluto
iiM yxyxd
1
),(
n
iiiABS yxyxd
1
),(
q=1 Minkowsky
4. Distancia Mahalanobis:
Datos provienen de una o varias poblaciones con matrices de varianzas-covarianzas
21
1 )(),(
yxyxyxdMH
EJEMPLO
Supongamos que se han medido n=4 variables continuas y que dos casos x,y vienen representados por los vectores x=(2.1,3.1,3.4,1.9)` e y=(1.2,2.0,1.7,3.6)`
Distancia euclidea:x-y=(0.9,1.1,1.7,-1.7)`
7.1
7.1
1.1
9.0
)7.1,7.1,1.1,9.0(),(2 yxdE
79.2),(
8.7
89.289.221.181.0
yxdE
21
1
2
n
iii yx
Distancia Minkowsky para q=1 y q=3Con q=1:
Con q=3:
Distancia del Valor absoluto:
4,57,17,11,19,0),( yxdM
32,24,5),( yxd ABS
28,289,11
89,117,17,11,19,0),(
3
33333
yxd M
MÉTODOS DE ANÁLISIS CLUSTER
Se dividen en dos grandes grupos1.Métodos jerárquicos: son aquellos que para formar un
clúster nuevo une o separa alguno ya existente para dar origen a otros dos de forma que se maximice una similaridad o se minimice una distancia. Dentro de estos a su vez se clasifican en:
1. Asociativos o aglomerativos: se parte de tantos grupos como individuos y se van agrupando hasta llegar a tener todos los individuos en un solo grupo.
2. Disociativos: se parte de un solo grupo que contenga a todos los individuos y se va separando hasta llegar a formar grupos individuales.
2.Métodos no jerárquicos: se clasifican los individuos en k grupos, estudiando todas las particiones de individuos en esos k grupos y eligiendo la mejor partición.
MÉTODOS JERÁRQUICOS
Sucesión de particiones donde cada partición se obtiene uniendo o dividiendo clusters
Ejemplo:
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
4
3
2
1
0
P
P
P
P
P
Metodos aglomerativos: los nuevos clusters se crean uniendo clusters Ventaja
Rapidez Son los mas habituales
Metodos divisivos: los nuevos clusters se crean dividiendo clusters(lentos) Ventaja
Parten de la información global que hay en los datos El proceso de división no tienen porque seguir hasta
que cada elemento forme un cluster
MÉTODOS JERÁRQUICOS
Dendrograma: son diagramas bidimensional es utilizados para representar clasificaciones jerárquicas
Muestra como ha sido el proceso de unión o división de los clusters
divisivo
Aglomerativo
MÉTODOS JERÁRQUICOS
Algoritmo básico de clasificación (ABC)
1. Cada caso formara un clusterP0=1….m
2. Supongamos que los casos mas cercanos son i,j:Entonces la union de estos formara un nuevo cluster (iUj=i,j) y se actualizara la matriz
u`(k,i,j)=u(k,i) =u(k,j)3. Una vez obtenida la particion P1=1,..
i,j,..n, se repiten los pasos 2 y 3 del algoritmo hasta que todos los casos formen un unico cluster
EJEMPLO: supongamos que tenemos la siguiente matriz definida sobre Ω=1,2,3,4,5 calculemos cual es la jerarquia indexada que nos da el algoritmo ABC
0......................................
1,0.......0...........................
35,0...35,0......0.................
35,0...35,0...15,0.....0........
35,0....35,0....2,0....2,0....0
U
4,15,4,1 uu
35,0
)5,1(
u
5,43
2
1
0...........................
35,0......0.................
35,0...15,0.....0........
35,0....2,0....2,0....0
U
Algoritmo básico de clasificación (ABC)
5,4,25,4,3,2 uu
35,0
)5,4,3(
u
5,43,2
1
0.................
35,0.....0........
35,0....2,0....0
U
5,4
3,2,1
0.........
35,0.....0
U
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
4
3
2
1
0
P
P
P
P
P
Algoritmo básico de clasificación (ABC)
Dendrograma
Algoritmo básico de clasificación (ABC)
Algoritmo de clasificación (AC)
1. Cada caso formara un clusterP0=1….m
2. Supongamos que los casos mas cercanos son i,j:Entonces la union de estos formara un unico cluster (iUj=i,j) y se definira la disyancia desde un caso cualquiera l al nuevo cluster(i,j)
d`(l,i,j)= f(d(l,i),d(l,j), l <>i,j
3. Una vez obtenida la particion P1=1,..i,j,..n, se repiten los pasos 2 y 3 del algoritmo hasta que todos los casos formen un unico cluster
Método del mínimo
La distancia entre dos clústeres mínima de las distancias entre los casos de cada clúster
Ejemplo: Supongamos que tenemos la siguiente matriz de distancias D definida sobre Ω=1,..5 calcular cual es la jerarquía indexada de método del mínimo.
0........................
7...0...................
8...2...0.............
8...4...4...0........
7...4....3....1....0
D
PASOS1. caso forma un clúster2. Los casos i, j más cercanos
Formamos el clúster 1,2Definimos la distancias de un caso al nuevo clúster
5,4,3,2,10 P
1)2,1(),(min , dlkdlk
)2,3(),1,3(min2,1,3 ddd
3
4,3min
5
4
3
2,1
0...................
7....0.............
8...2....0.......
7....4....3....0
Matriz de distancias
Método del mínimo
3. Volver a los pasos 2 y 3 buscar casos con distancias mínimas d(3,4)=2 nuevo cluster3,4 rehacer distancia
4. Volver a los pasos 2 y 3 buscar casos con distancias mínimas 3=d(1,2,3,4) nuevo cluster1,2,3,4 rehacer matriz
)4,2,1(),3,2,1(min4,3,2,1 ddd
3
4,3min
5
4,3
2,1
0.............
7.....0......
7....3....0
5
4,3,2,1
0......
7....0
Método del mínimo
Jerarquía aglomerada indexada
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
5,4,3,2,1
4
3
2
1
0
P
P
P
P
P
Método del mínimo
Método del Máximo
Este método es conocido como Complete Linkage o “vecino más lejano”, .
La distancia entre dos clúster se define como el máximo de las distancias entre los casos de los clúster.
),(),,(),,( jkdikdmáxjikd
,),(),( jiji CjCijidmáxCCd
EJEMPLOInicialmente la partición es: 1, 2,3,
4,5 y los casos más próximos son 1 y 2
La nueva matriz de distancia es:Los casos 3 y 4 forman la siguiente matriz
Método del Máximo
Cálculo para sacar el máximo
Por lo tanto se unen 1,2 con 3,4 DENDROGRAMA
Método del Máximo
Método de Ward
Se calculan las distancias como medida de similitud entre los objetos.
El objetivo del método se basa en que al unir dos clúster el aumento de la heterogeneidad total sea lo menor posible.
El proceso termina cuando todos los casos forman un único clúster.
Mide heterogeneidad
Suma distancias
Vector de medias
EJEMPLOHay 6 casos con dos variables
Cada caso forma un clústerP0=1,2,3,4,5,6
Perdida mínima de heterogeneidad
P1=1,2,3,4,5,6
Método de Ward
Luego la pérdida mínima se obtiene uniendo 1 y 3
Por lo tanto:
Se calcula el centro de 1,3
P2=1,3,2,4,5,6
La siguiente perdida mínima de heterogeneidad al unir 1,3 y 2 es:
P3=1,2,3,4,5,6
Método de Ward
Siguiendo el proceso de aglomeración para la partición P4 hay 3 posibilidades:
Calculando cada uno de los centros y la pérdida mínima queda:
Método de Ward
Quedando como perdida mínima de heterogeneidad uniendo los clúster 4 y 5,6 con un valor de 2,21.
P4=1,2,3,4,5,6
Método de Ward
Single-linkeage
JerárquicoAglomerativoSi hay un error en algún paso no se puede
volver atrás …
Single-linkeage
Dado un conjunto de N (5) elementos a ser agrupado y una matriz de distancia (o similitud) de N x N:
d 1 2 3 4 5
1 0 5 6 10 13
2 5 0 1 5 8
3 6 1 0 4 7
4 10 5 4 0 3
5 13 8 7 3 0
Single-linkeageComenzar por asignar cada item a un cluster.Tenemos 5 clustersSean las distancias entre los clusters las mismas
que entre los elementos de cada cluster
d 1 2 3 4 5
1 0 5 6 10 13
2 5 0 1 5 8
3 6 1 0 4 7
4 10 5 4 0 3
5 13 8 7 3 0
Single-linkeage
Encontrar el par más cercano de clusters y unirlo en un único cluster.
Tenemos 4 clusters
d 1 2 3 4 5
1 0 5 6 10 13
2 5 0 1 5 8
3 6 1 0 4 7
4 10 5 4 0 3
5 13 8 7 3 0
Single-linkeage
Calcular las distancias entre el nuevo cluster y los viejos clusters old clusters
d 1 2-3 4 5
1 0 5,5 10 13
2-3 5,5 0 4,5 8,5
4 10 4,5 0 3
5 13 8,5 3 0
d 1 2 3 4 5
1 0 5 6 10 13
2 5 0 1 5 8
3 6 1 0 4 7
4 10 5 4 0 3
5 13 8 7 3 0
Single-linkeage
Repetir los pasos 2y 3 hasta que todos los elementos se encuentren en el mismo cluster de tamaño N
Single-linkeage
http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/AppletH.html
Simple K-Medias
Particional Distancia euclídea Necesita el valor de k (#clusters) Búsqueda de prototipos
Simple K-Medias
• Ubicar k (2) puntos en el espacio representado por los objetos a ser agrupados. Estos k puntos son los centroides iniciales de cada grupo
Simple K-Medias
• Asignar cada objeto al grupo que esté más cercano a su centroide
Simple K-Medias
• Recalcular la posición de los k centroides
• Repetir pasos 2 y 3 hasta que los prototipos ya no varíen
K-means
De esta manera se minimiza la distancia intracluster según la metrica dada
GRACIAS!!