av

Si f: R x R -> cumple que f(x,y) <= f(x,z) para todo x,y,z c R. F es una métrica. F no puede ser una métrica. F puede ser una métrica. Esta propiedad de f no tiene que ver con la caracterización de las métricas.

Existen 2 algoritmos de agrupamiento que como salida no proporcionan un agrupamiento directamente. Fuzzy C-means y OPTICS. K-means y DBSCAN. El algoritmo aglomerativo del modelo jerárquico y el agrupamiento espectral. DBSCAN y OPTICS.

Imagina un dataset S formado por puntos de un espacio R2 que están situados en dos segmentos paralelos entre si que están separados a una distancia mucho mas grande que la longitud de cada uno. Queremos agrupar los puntos usando el algoritmo jerárquico aglomerativo con ‘Single Linkage’. Entonces: Los cluster iniciales serán parejas de puntos cada uno de ellos perteneciente a un segmento. Cuando se hayan formado todas las parejas entre segmentos se irán fusionando entre ellas hasta llegar a un solo cluster. Se iran seleccionando de ambos segmentos de tal manera que la media (centroide) del cluster que se va formando caiga exactamente en el punto medio entre los dos segmentos. Los clusters se formarán primero a lo largo de cada segmento cuando un único cluster….. Los clusters no se formarán de ninguna manera anteriormente descrita.

Un dendograma completo muestra: El ultimo agrupamiento generado por el agrupamiento jerárquico. Los N-1 agrupamientos que se han producido. El mejor de los N-1 agrupamientos. El dendograma muestra un histograma de la frecuencia de fusión de cada elemento.

El problema del agrupamiento espectral se resume en 3 pasos ordenados: 1. Calcular la matriz laplaciana del dataset. 2. Obtener el grafo a partir de esta matriz. 3. Obtener los autovectores la matriz laplaciana que indican las direcciones de máxima varianza de los datos y proyectar a S en ellas. 1. Calcular un grafo a partir de S. 2. Calculas los autovectores y autovalores de la matriz de disimilaridad de S. 3. Romper las aristas del grafo que tengas pesos mucho mas grandes que el autovalor mas grande. 1. Calcular un grafo a partir del dataset S. 2. Calcular la matriz Laplaciana del grafo y su descomposición espectral. 3. Obtener los cluster de S mediante los q autovectores de los autovalores mas pequeños. 1. Calcula un grafo a partir de S. 2. Hacer una PCA (análisis componentes principales) de la matriz de pesos de las aristas del grafo. 3. Proyectar a S sobre las dos direcciones principales.

Respecto a los hiperpárametros e y MinPts. Ambos algoritmos DBSCAN y OPTICS son muy sensibles. Pequeñas variaciones de cualquiera de ellos generan resultados distintos. DBSCAN es robusto a los hiperparámetros (es decir, que variaciones pequeñas de los mismos dan lugar a resultados parecidos), mientras que OPTICS es sensible a ambos. OPTICS es sensible sobre todo al valor de € y DBSCAN lo es al valor de MinPts únicamente. DBSCAN es muy sensible a ambos y OPTICS no es sensible a ninguno de ellos de manera extrema.

Un cliente ha comprado los mismos productos que otro pero el doble de cantidad. La distancia del coseno entre estos dos clientes es: (falta medio enunciado). 0. 1. 2. -1.

Considera K-Means y el dataset de los tres anillos como céntricos de prácticas. ¿En cúal de las propiedades del teorema de Kleinberg falla?. Inviarianza al escalado. Riqueza. Consistencia. K-Menas las cumple todas y es, por tanto. La técnica de agrupamiento universal y es la que primero se prueba.

Llamamos a filtrado colaborativo: A la normalización de los datos por características que nos permite referir cada característica al valor conjunto que tiene en el grupo (colaborativo). A un preprocesado de los datos consistente en eliminar los datos que tienen características a 0. Al uso de la épsilon-vecindad de cada dato para identificar si dicho dato es ruido. A una técnica que rellena con información útil características que tenia a cero el dataset original, a partir de todo el conjunto de datos.

Considera el agrupamiento aglomerativo con Complete Linkage. Definimos el concepto de ‘k-vecinos-en-cluster-i’ de un elemento x a los k-vecinos mas próximos que pertenecen al mismo cluster que x en la iteración i-ésima del algoritmo. Entonces: Los k-vecinos-en-cluster-i pueden cambiar en la siguiente iteración del algoritmo si el cluster que contiene a x se funde en la siguiente iteración con otro cluster. Dos puntos de diferentes clusters en la iteración i del algoritmo pueden tener comunes algún o algunos puntos de sus k-vecinos-en-cluster-i. Es posible que un punto x mantenga sus k-vecionos-en-cluster-i constantes desde la iteración 2 hasta la n-1 (donde n es el numero de elementos del dataset). Los k-vecinos-en-cluster-i son los ……… en iteraciones a partir de i hasta el final.

La distancia de Ward en el agrupamiento jerárquico se define como: La diferencia de inercia entre los centroides que se unen. La diferencia entre la inercia del centroide resultante de la fusión y la suma de las inercias de los clusters antes de la fusión. La distancia entre los centroides de los clústeres. Max(|x1-x2|) x1€Cx xj € C1.

En el dendograma ha aparecido un crossover. Esto significa que: El agrupamiento jerárquico ha salido mal y debe ser desechado. La distancia de fusión donde se produce el crossover es la mas adecuada para ‘cortar’ el dendograma y sacar un agrupamiento de los datos. El linkage utilizado no tiene la propiedad de monotonicidad. Los agrupamientos a distancias de fusión superiores a la del crossover están mal formadas y no pueden ser considerados verdaderos clusters.

En el algoritmo Fuzzy-CMeans: El numero de clusters lo determina el propio algoritmo. Es posible que con algún dataset, algún cluster se quede vacío (habiendo varios clusters). Los centroides son calculados usando todo el dataset para cada uno de ellos. Es posible que en algún dataset, todos los puntos sean asignados a un único cluster (habiendo varios clusters).

Estamos realizando un clustering espectral paso a paso con K=1. Vemos que la multiplicidad del autovalor λ == 0 es uno, y que el segundo autovector no discrimina claramente los datos en 4 grupos. Entonces: Debo construir una matriz con unos autovectores por columnas (empíricamente hasta que haya un salto ajustable en los valores de los autovalores) y realizar K-Means sobre ella. Esta técnica no es valida para este dataset. Debería probar con otra familia de algoritmos de agrupamiento. El dataset esta mal formado porque siempre la multiplicidad del autovalor λ == 0 es mayor que 1. El autovector asociado al autovalor λ == 0, es decir, el vector 1, nos indica que solo hay un cluster.

En el agrupamiento espectral, la expresión a minimizar originalmente es min NCut(A1,,,,, Ak) == . Donde el denominador vol(Ai): Es un termino de normalización. Hace que el proceso de minimización genere clusters de un tamaño parecido. Es una constante para compensar el hecho de que en el proceso de minimización los cortes se cuentas dos veces. Ninguna de las opciones anteriores es correcta.

Realizamos un agrupamiento espectral con numero de clusters k sobre un dataset de cardinal n, eligiendo para hacer K-Means p autovectores entonces: El numero de componentes de cada uno de los autovectores implicados es k. El numero de componentes de cada uno de los autovectores implicados es n x p. El numero de componentes de cada uno de los autovectores implicados es k x n x p. El numero de componentes de cada uno de los autovectores implicados es n.

En el contexto del agrupamiento basado en densidad DBSCAN si un punto x1 es directamente alcanzable por un punto x2 pero no viceversa: Estos puntos no pueden pertenecer al mismo cluster. El punto x1 es clasificado como ruido. Ambos puntos pertenecerán al mismo cluster. Ambos puntos pertenecerán al mismo cluster siempre que x1 sea un punto core.

La curva del cuarto vecino mas próximo, se utiliza en DBSCAN para: Determinar un posible valor del parámetro e. Ver a través de esa grafica la calidad del agrupamiento realizado. Determinar el numero de clusters. Determinar el valor de MinPts.

En el contexto de OPTICS hacemos lo siguiente: calentamos la curva del cuarto vecino más próximo y cortamos la curva por la derecha en el tramo ascendente (como hemos visto en clase). Elegimos si € correspondiente a ese punto de corte y fijamos MinPoints ==5 (es decir los 4 vecinos mas próximos y el propio punto. Entonces el diagrama de alcances resultado de OPTICS: Tiene el aspecto de los que hemos visto en las diapos de teoría. Tiene un conjunto de puntos formado por todos los puntos de la derecha de la curva que pasan a ser ruido y por tanto a distancia de alcance infinita (o fijada a un valor alto constante). Puede tener uno o mas clusters separados por algún punto a distancia infinita (o muy alta), pero todos los clusters tienen sus puntos a la misma profundidad, que es €. Con estos parámetros cada punto es un cluster diferente y por tanto el diagrama de alcance estará formado por barras de altura infinitas o muy grande.

El problema del agrupamiento espectral se resume en tres pasos ordenados: 1. Calcular la matriz laplaciana del dataset S. 2. Obtener el grafo a partir de esa matriz. 3. Obtener los autovectores la matriz laplaciana que indican las direcciones máxima varianza de los datos y proyectar a S en ellas. 1. Calcular un grafo a partir de S. 2. Calcular los autovectores y autovalores de la matriz de disimilaridad de S. 3. Romper las aristas del grafo que tengan pesos mucho más grandes que el autovalor más grande. 1. Calcular un grafo a partir de S. 2. Hacer una PCA (análisis de componentes principales) de la matriz de pesos de las aristas del grafo. 3. Proyectar a S sobre las dos direcciones principales. 1. Calcular un grafo a partir del dataset S. 2. Calcular la matriz Laplaciana del grafo y su descomposición espectral. 3. Obtener los cluster de S mediante los q autovectores de los autovalores más pequeños.

En el algoritmo de Fuzzy-CMeans el cálculo de los centroides en cada iteración se realiza: De la misma manera que se hace con K-Means. Usando la misma fórmula que con K-Means pero, para el cluster k solo contribuyen al cálculo los puntos que tienen la máxima probabilidad para dicho cluster k. Se utilizan todos los puntos del dataset para el cálculo de cada centroide, pesando cada punto por su probabilidad de pertenencia. En este algoritmo no se calculan centroides, solo probabilidades de pertenencia a clusters.

Si p es un punto directamente alcanzable por densidad (directy density-reachable) por q, entonces: q es un punto directamente alcanzable por densidad por p. Necesariamente p es un punto frontera. Necesariamente q es un punto core. Hay una cadena de puntos core de longitud mayor o igual a dos que une p y q.

En el contexto del agrupamiento espectral, una manera de construir un grafo es mediante el ‘grafo de vecindad Ꜫ’. Que consiste: Se conectan todos los puntos que se encuentran a una distancia menor que Ꜫ. Se conectan los Ꜫ-vecinos más próximos a cada punto. Se conectan aleatoriamente Ꜫ puntos entre sí, a los que denominamos ‘vecinos’. Ninguno de los procesos anteriores genera un grafo de vecindad Ꜫ.

Al realizar un dendrograma sobre un dataset usando la distancia de grupos ‘single linkage’ nos hemos encontrado que casi todos los clusters se forman en un rango muy pequeño de la distancia ‘single linkage’ (entre 0 y 2) y luego hay un salgo muy grande (gap) hasta el valor de linkage 12 donde se unen los dos últimos grupos. Por lo tanto, para el ‘single linkage’: Todos los puntos del dataset están homogéneamente partidos en el espacio de características. Todos los puntos del dataset están muy próximos entre ellos. Existen dos zonas en el espacio de características alejadas entre sí donde se concentran los puntos del dataset. El dataset no está normalizado.

Realizamos un agrupamiento espectral con el número de clusters k sobre un dataset de cardinal n, eligiendo para hacer K-Means p autovectores entonces: El número de componentes de cada uno de los autovectores implicados es k. El número de componentes de cada uno de los autovectores implicados en n x p. El número de componentes de cada uno de los autovectores implicados es k x n x p. El número de componentes de cada uno de los autovectores implicados es n.

La existencia de crossover en un dendrograma depende de: El linkage elegido. El tipo de métrica de Minkowski elegida. La posición del centroide de cada cluster en cada iteración. El número de iteraciones que se le de como parámetro de entrada al algoritmo.

Dado un grafo G, se define la matriz de grado del grafo como: La matriz de los pesos de los arcos que conectan un nodo con otro. La matriz que contiene los autovalores de la descomposición espectral de la laplaciana del grafo. Es otra manera de referirse a la matriz laplaciana de un grafo. Es la matriz diagonal donde cada término de la misma es la suma de los pesos de los arcos de un nodo del grafo.

Existen dos algoritmos de agrupamiento que, como salida, no proporcionan un agrupamiento directamente. Estos son: Fuzzy C-Means y OPTICS. K-Means y DBSCAN. Los algoritmos del agrupamiento jerárquico y el agrupamiento espectral. DBSCAN y OPTICS.

Hemos realizado un agrupamiento usando OPTICS y el diagrama de la distancia de alcances nos aparece con casi todos los puntos a distancia infinito (la más grande). Entonces: Hemos elegido un valor del parámetro MinPts muy pequeño. Hemos elegido una distancia Core demasiado grande. Hemos elegido un parámetro Ꜫ demasiado grande. Hemos elegido un parámetro Ꜫ demasiado pequeño.

Tenemos un dataset con el que hemos hecho un clustering espectral y observamos que el grado de multiplicidad del autovalor de valor 0 es 3. Igualmente, observando las componentes del segundo autovector, vemos que podríamos agrupar los datos en 4 grupos. Sin embargo, para nuestro problema deseamos obtener 5 clusters. Entonces: Si el grado de multiplicidad del valor 0 es tres, las tres componentes conexas ofrecen la mejor clusterización posible y hay que aceptar ese resultado. Hacemos una clusterización con K-Medias de la matriz de autovectores con k=5. La mejor solución posible la ofrecen las componentes del segundo autovector. Cogemos 5 autovectores para hacer la clusterización usando K-Medias con k=3.

Considera el agrupamiento aglomerativo con Complete Linkage. Definimos el concepto de ‘kvecinos-en-cluster-i’ de un elemento x a los k-vecinos más próximos que pertenecen al mismo cluster que x en la iteración i-ésima del algoritmo. Entonces: Los k-vecinos-en-cluster-i pueden cambiar en la siguiente iteración del algoritmo si el cluster que contiene a x se funde en la siguiente iteración con otro cluster. Dos puntos de diferentes clusters en la iteración x del algoritmo pueden tener comunes algún o algunos puntos de sus k-vecinos-en-cluster-i. Es posible que un punto x mantenga sus 5-vecinos-en-cluster-i constantes desde la iteración 2 hasta la n-1 (donde n es el número de elementos del dataset). Los k-vecinos-en-cluster-i son los mismo en las siguientes iteraciones a partir de la i hasta el final.

El algoritmo KMeans ++: Es el algoritmo iterativo de inicialización de KMeans. En cada iteración se calcula un nuevo centroide de manera estocástica. Es un algoritmo de agrupamiento basado en K-Means pero que pertenece a la familia de los agrupamientos soft clustering. Es un algoritmo de inicialización de K-Means que consiste en etiquetar a cada punto del dataset como perteneciente a un cluster usando un procedimiento estocástico. Es un algoritmo de agrupamiento basado en K-Means pero cuyo resultado es la asignación a cada punto del dataset de una probabilidad de pertenencia a cada cluster.

En el agrupamiento jerárquico, una variación ligera de los valores de los puntos en el dataset: No hace falta variar el resultado del agrupamiento. Puede hacer no converger el algoritmo y por tanto no se generará un dendrograma. Puede generar un agrupamiento muy distinto. Generará crossover si no existían ya.

Dados dos puntos en un espacio R^4, x1 = (4,1,5,-3), x2 = (3,8,-2,-1), entonces ||x2 – x1||_∞ =. 7. √102. 18. 6.

El problema original que se plantea en el agrupamiento espectral consiste en: Dado un grafo construido a partir del dataset, encontrar una partición del conjunto de vértices del mismo tal que la suma de los pesos de los arcos que unen vértices de diferentes clusters sea mínima. Encontrar un grafo a partir del dataset cuya matriz laplaciana tenga tantos autovalores cero como número de clusters que buscamos. Dado un dataset generar un grafo con k componentes conexas cuya inercia sea mínima. Dada una matriz de pesos de los arcos de un grafo, elegir el número de autovectores propios de dicha matriz, suficientes para hacer un KMeans con buenos resultados.

En DBSCAN la determinación heurística del parámetro Ꜫ se realiza mediante: Una curva Elbow. El indicador Silhouette. El coeficiente cofenético. La curva de distanciad al 4º vecino más próximo.

Hemos realizado un agrupamiento con Fuzzy-CMeans para k clusters y el coeficiente de Dunn nos da un valor de 1/k. Entonces: El agrupamiento es igual a un agrupamiento realizado con K-Means y para cada punto del dataset solo hay un cluster al que pertenece con probabilidad 1. El agrupamiento es el peor posible ya que todos los puntos del dataset tienen la misma probabilidad de pertenecer a cada cluster. La distancia media de los puntos de un cluster a su centroide es 1/k. Cada cluster tiene una probabilidad 1/k de contener a todo el dataset.

Tenemos un dataset con el que hemos hecho un clustering espectral y observamos que el grado de multiplicidad del autovalor de valor 0 es 3. Igualmente, observando las componentes del segundo autovector, vemos que podríamos agrupar los datos en 4 grupos. Sin embargo, para nuestro problema deseamos obtener 5 clusters. Entonces: Si el grado de multiplicidad del valor 0 es tres, las tres componentes conexas ofrecen la mejor clusterización posible y hay que aceptar ese resultado. Hacemos una clusterización con K-Medias de la matriz de autovectores con k=5. La mejor solución posible la ofrecen las componentes del segundo autovector. Cogemos 5 autovectores para hacer la clusterización usando K-Medias con k=3.

En el contexto del agrupamiento espectral, una manera de construir un grafo es mediante el ‘grafo de vecindad Ꜫ’. Que consiste: Se conectan todos los puntos que se encuentran a una distancia menor que Ꜫ. Se conectan los Ꜫ-vecinos más próximos a cada punto. Se conectan aleatoriamente Ꜫ puntos entre sí, a los que denominamos ‘vecinos’. Ninguno de los procesos anteriores genera un grafo de vecindad Ꜫ.

Al realizar un dendrograma sobre un dataset usando la distancia de grupos ‘single linkage’ nos hemos encontrado que casi todos los clusters se forman en un rango muy pequeño de la distancia ‘single linkage’ (entre 0 y 2) y luego hay un salgo muy grande (gap) hasta el valor de linkage 12 donde se unen los dos últimos grupos. Por lo tanto, para el ‘single linkage’: Todos los puntos del dataset están homogéneamente partidos en el espacio de características. Todos los puntos del dataset están muy próximos entre ellos. Existen dos zonas en el espacio de características alejadas entre sí donde se concentran los puntos del dataset. El dataset no está normalizado.

En el agrupamiento jerárquico, una variación ligera de los valores de los puntos en el dataset: No hace falta variar el resultado del agrupamiento. Puede hacer no converger el algoritmo y por tanto no se generará un dendrograma. Puede generar un agrupamiento muy distinto. Generará crossover si no existían ya.

El algoritmo KMeans ++: Es el algoritmo iterativo de inicialización de KMeans. En cada iteración se calcula un nuevo centroide de manera estocástica. Es un algoritmo de agrupamiento basado en K-Means pero que pertenece a la familia de los agrupamientos soft clustering. Es un algoritmo de inicialización de K-Means que consiste en etiquetar a cada punto del dataset como perteneciente a un cluster usando un procedimiento estocástico. Es un algoritmo de agrupamiento basado en K-Means pero cuyo resultado es la asignación a cada punto del dataset de una probabilidad de pertenencia a cada cluster.

En el algoritmo de Fuzzy-CMeans el cálculo de los centroides en cada iteración se realiza: De la misma manera que se hace con K-Means. Usando la misma fórmula que con K-Means pero, para el cluster k solo contribuyen al cálculo los puntos que tienen la máxima probabilidad para dicho cluster k. Se utilizan todos los puntos del dataset para el cálculo de cada centroide, pesando cada punto por su probabilidad de pertenencia. En este algoritmo no se calculan centroides, solo probabilidades de pertenencia a clusters.

Hemos realizado un agrupamiento con Fuzzy-CMeans para k clusters y el coeficiente de Dunn nos da un valor de 1/k. Entonces: El agrupamiento es igual a un agrupamiento realizado con K-Means y para cada punto del dataset solo hay un cluster al que pertenece con probabilidad 1. El agrupamiento es el peor posible ya que todos los puntos del dataset tienen la misma probabilidad de pertenecer a cada cluster. La distancia media de los puntos de un cluster a su centroide es 1/k. Cada cluster tiene una probabilidad 1/k de contener a todo el dataset.

Dado un grafo G, se define la matriz de grado del grafo como: La matriz de los pesos de los arcos que conectan un nodo con otro. La matriz que contiene los autovalores de la descomposición espectral de la laplaciana del grafo. Es otra manera de referirse a la matriz laplaciana de un grafo. Es la matriz diagonal donde cada término de la misma es la suma de los pesos de los arcos de un nodo del grafo.

El problema original que se plantea en el agrupamiento espectral consiste en: Dado un grafo construido a partir del dataset, encontrar una partición del conjunto de vértices del mismo tal que la suma de los pesos de los arcos que unen vértices de diferentes clusters sea mínima. Encontrar un grafo a partir del dataset cuya matriz laplaciana tenga tantos autovalores cero como número de clusters que buscamos. Dado un dataset generar un grafo con k componentes conexas cuya inercia sea mínima. Dada una matriz de pesos de los arcos de un grafo, elegir el número de autovectores propios de dicha matriz, suficientes para hacer un KMeans con buenos resultados.

En DBSCAN la determinación heurística del parámetro Ꜫ se realiza mediante: Una curva Elbow. El indicador Silhouette. El coeficiente cofenético. La curva de distanciad al 4º vecino más próximo.

Considera el agrupamiento aglomerativo con Complete Linkage. Definimos el concepto de ‘kvecinos-en-cluster-i’ de un elemento x a los k-vecinos más próximos que pertenecen al mismo cluster que x en la iteración i-ésima del algoritmo. Entonces: Los k-vecinos-en-cluster-i pueden cambiar en la siguiente iteración del algoritmo si el cluster que contiene a x se funde en la siguiente iteración con otro cluster. Dos puntos de diferentes clusters en la iteración x del algoritmo pueden tener comunes algún o algunos puntos de sus k-vecinos-en-cluster-i. Es posible que un punto x mantenga sus 5-vecinos-en-cluster-i constantes desde la iteración 2 hasta la n-1 (donde n es el número de elementos del dataset). Los k-vecinos-en-cluster-i son los mismo en las siguientes iteraciones a partir de la i hasta el final.

Imagina un dataset S formado por puntos de un espacio R2 que están situados en dos segmentos paralelos entre si que están separados a una distancia mucho mas grande que la longitud de cada uno. Queremos agrupar los puntos usando el algoritmo jerárquico aglomerativo con ‘Single Linkage’. Entonces: Los cluster iniciales serán parejas de puntos cada uno de ellos perteneciente a un segmento. Cuando se hayan formado todas las parejas entre segmentos se irán fusionando entre ellas hasta llegar a un solo cluster. Se iran seleccionando de ambos segmentos de tal manera que la media (centroide) del cluster que se va formando caiga exactamente en el punto medio entre los dos segmentos. Los clusters se formarán primero a lo largo de cada segmento cuando un único cluster……. Los clusters no se formarán de ninguna manera anteriormente descrita.

Respecto a los hiperpárametros e y MinPts. - Ambos algoritmos DBSCAN y OPTICS son muy sensibles. Pequeñas variaciones de cualquiera de ellos generan resultados distintos. - DBSCAN es robusto a los hiperparámetros (es decir, que variaciones pequeñas de los mismos dan lugar a resultados parecidos), mientras que OPTICS es sensible a ambos. OPTICS es sensible sobre todo al valor de € y DBSCAN lo es al valor de MinPts únicamente. DBSCAN es muy sensible a ambos y OPTICS no es sensible a ninguno de ellos de manera extrema.

Falta medio enunciado Un cliente ha comprado los mismos productos que otro pero el doble de cantidad. La distancia del coseno entre estos dos clientes es: 0. 1. 2. -1.

Considera K-Means y el dataset de los tres anillos como céntricos de prácticas. ¿En cúal de las propiedades del teorema de Kleinberg falla?. Inviarianza al escalado. - Riqueza. Consistencia. - K-Menas las cumple todas y es, por tanto. La técnica de agrupamiento universal y es la que primero se prueba.

Llamamos a filtrado colaborativo: A la normalización de los datos por características que nos permite referir cada característica al valor conjunto que tiene en el grupo (colaborativo). A un preprocesado de los datos consistente en eliminar los datos que tienen características a 0. Al uso de la épsilon-vecindad de cada dato para identificar si dicho dato es ruido. A una técnica que rellena con información útil características que tenia a cero el dataset original, a partir de todo el conjunto de datos.

La distancia de Ward en el agrupamiento jerárquico se define como: La diferencia de inercia entre los centroides que se unen. La diferencia entre la inercia del centroide resultante de la fusión y la suma de las inercias de los clusters antes de la fusión. La distancia entre los centroides de los clústeres. Max(|x1-x2|) x1€Cx xj € C1.

En el dendograma ha aparecido un crossover. Esto significa que: El agrupamiento jerárquico ha salido mal y debe ser desechado. - La distancia de fusión donde se produce el crossover es la mas adecuada para ‘cortar’ el dendograma y sacar un agrupamiento de los datos. El linkage utilizado no tiene la propiedad de monotonicidad. Los agrupamientos a distancias de fusión superiores a la del crossover están mal formadas y no pueden ser considerados verdaderos clusters.

En el algoritmo Fuzzy-CMeans: El numero de clusters lo determina el propio algoritmo. Es posible que con algún dataset, algún cluster se quede vacío (habiendo varios clusters). Los centroides son calculados usando todo el dataset para cada uno de ellos. Es posible que en algún dataset, todos los puntos sean asignados a un único cluster (habiendo varios clusters).

Estamos realizando un clustering espectral paso a paso con K=1. Vemos que la multiplicidad del autovalor λ == 0 es uno, y que el segundo autovector no discrimina claramente los datos en 4 grupos. Entonces: Debo construir una matriz con unos autovectores por columnas (empíricamente hasta que haya un salto ajustable en los valores de los autovalores) y realizar K-Means sobre ella. - Esta técnica no es valida para este dataset. Debería probar con otra familia de algoritmos de agrupamiento. - El dataset esta mal formado porque siempre la multiplicidad del autovalor λ == 0 es mayor que 1. El autovector asociado al autovalor λ == 0, es decir, el vector 1, nos indica que solo hay un cluster.

En el agrupamiento espectral, la expresión a minimizar originalmente es min NCut(A1,,,,, Ak) == . Donde el denominador vol(Ai): - Es un termino de normalización. Hace que el proceso de minimización genere clusters de un tamaño parecido. Es una constante para compensar el hecho de que en el proceso de minimización los cortes se cuentas dos veces. Ninguna de las opciones anteriores es correcta.

En el contexto del agrupamiento basado en densidad DBSCAN si un punto x1 es directamente alcanzable por un punto x2 pero no viceversa: Estos puntos no pueden pertenecer al mismo cluster. El punto x1 es clasificado como ruido. Ambos puntos pertenecerán al mismo cluster. Ambos puntos pertenecerán al mismo cluster siempre que x1 sea un punto core.

La curva del cuarto vecino mas próximo, se utiliza en DBSCAN para: Determinar un posible valor del parámetro e. Ver a través de esa grafica la calidad del agrupamiento realizado. Determinar el numero de clusters. Determinar el valor de MinPts.

En el contexto de OPTICS hacemos lo siguiente: calentamos la curva del cuarto vecino más próximo y cortamos la curva por la derecha en el tramo ascendente (como hemos visto en clase). Elegimos si € correspondiente a ese punto de corte y fijamos MinPoints ==5 (es decir los 4 vecinos mas próximos y el propio punto. Entonces el diagrama de alcances resultado de OPTICS: Tiene el aspecto de los que hemos visto en las diapos de teoría. Tiene un conjunto de puntos formado por todos los puntos de la derecha de la curva que pasan a ser ruido y por tanto a distancia de alcance infinita (o fijada a un valor alto constante). Puede tener uno o mas clusters separados por algún punto a distancia infinita (o muy alta), pero todos los clusters tienen sus puntos a la misma profundidad, que es €. Con estos parámetros cada punto es un cluster diferente y por tanto el diagrama de alcance estará formado por barras de altura infinitas o muy grande.

- Al realizar un dendrograma sobre un dataset usando la distancia de grupos 'single linkage' nos hemos encontrado que casi todos los clusters se forman en un rango muy pequeño de la distancia 'single linkage' (entre 0 y 2) y luego hay un salto muy grande (gap) hasta el valor de linkage 12 donde se unen los dos últimos grupos. Por lo tanto, para el 'single linkage": Todos los puntos de dataset están homogeneamente repartidos en el espacio de características. -Todos los puntos de dataset están muy próximos entre ellos. Existen dos zonas en el espacio de características aloja das entre sí donde se concentran los puntos del dataset. -El dataset no está normalizado.

-Dado un grafo Gi, se define la matriz de grado del grafo, como: -La matriz de los pesos de los arcos que conectan un nodo con otro. La matriz que contiene los autovalores del la descomposición espectral de la laplaciana del grafo. -Es otra manera de referirse a la matriz laplaciana de un grafo. -Es la matriz diagonal donde cada termino de la misma es la suma de los pesos de los arcos de un nodo del grafo.

El problema original que se plantea en el agrupamiento espectral consiste en: -Dado un grafo construido a partir del dataset, encontrar una partición del conjunto de vértices del mismo tal que la suma de los pesos de los arcos que unen vértices de diferentes clusters sea mínima. Encontrar un grafo a partir del dataset cuya matriz laplaciana tenga tantos autovalores cero como número de clusters que buscamos. Dado un dataset generar un grafo con k componentes conexas cuya inercia sea mínima. Dada una matriz de pesos de los arcos….

En la práctica, el coeficiente correlación cofenético se calcula: -Resolviendo el siguiente problema de optimización minSumSum||c-c||^2. Calculando a partir de la matriz de disimilaridad los autovalores y autovectores propios y sumando luego los autovalores que son positivos. -Obteniendo primero la matriz de las distancias de fusión Xab a las que un cluster que tenia un elemento Xa se funde con un con un cluster que tenia un elemento Xb. Luego se calcula la correlación de esta distancia con la distancia entre Xa y Xb de la matriz de disimilaridad. -Calculando la inercia de cada punto que pertenece a un cluster para cada uno de los N niveles (donde N es el número de elementos del dataset) y luego promediando estos valores para todos los puntos.

En t-SNE usamos el parámetro perplexity para: Calcular la desviación estándar de la gausiana de cada dato. Calcular la cantidad que hay que restarle a la divergen- cia K-L de manera constante por elegir una distribución t-Student (Cauchy) para los puntos embebidos. Calcular la calidad del embebimiento realizado por el algoritmo. Calcular el valor de la entropía del dataset.

Sea un dataset S de puntos de R ^ n . Sea una manifold M definida como un homomorfismo sobre R ^ d donde d < n Sea que los puntos de S se encuentran alojados en M. Entonces: La dimensión intrínseca de Ses n - d. La dimensión intrínseca de S es n. La dimensión intrínseca de S es d. La dimensión intrínseca de S es n + d.

La curva del cuarto vecino más próximo, se utiliza en DBSCAN para: Determinar un posible valor del parámetro ε. Ver a través de esa gráfica la calidad del agrupamiento realizado. Determinar el numero de clusters. Determinar el valor del parámetro MinPts.

El algoritmo EM tiene una estructura muy similar al algoritmo: LLE. K-Medias. t-SNE. MDS.

En el contexto de matrices simétricas definidas semipositivas, el teorema de Courant-Fisher afirma que: Siempre existe un proceso algorítmico para resolver un problema de optimización. Los autovectores de una matriz M son los vectores que maximizan y minimizan el coeficiente de Rayleight para dicha matriz en dicho espacio vectorial. Los autovalores de una matriz M establecen el orden de selección de los autovalores en el problema espectral. La diagonalización (descomposición espectral) de la matriz laplaciana de un grafo es la solución al problema del corte.

La forma de un dendrograma para un dataset S de 5 elementos en R2 S = {A, B, C, D, E, } en la que se ha utilizado Single Linkage es la siguiente, en orden ascendente de valores de fusión: Primera fusión: A con B. Segunda fusión: el anterior conjunto con C. Tercera fusion: el anterior conjunto con D. Cuarta fusión: El anterior conjunto con E. Entonces la forma en que se distribuyen dichos elementos en el plano R ^ 2 podría ser: Dos hileras de puntos muy separadas entre sí. En una hilera están A, B. En la otra C,D,E, todos separados de sus vecinos dentro de cada hilera a la misma distancia, que es mucho menor que la distancia que separa las hileras. En una Rosa de los vientos, el Punto A estaría en el Norte, el B en el Sur, el C en el Este, el D en el Oeste y el E en el Noroeste. Una línea recta donde se sitúan por este orden en sentido positivo: A luego B, luego C, luego D, luego E. Donde las distancias entre vecinos cada vez son mayores según este orden. Ninguna de las anteriores configuraciones explica la for- mación de este dendrograma.

En la práctica del agrupamiento jerárquico usamos la instrucción 'fcluster()' de la librería Scikit para. Obtener todos los clusters de todos los niveles del dendrograma, que son devueltos en una estructura de tipo Pandas. Obtener el conjunto de clusters correspondientes a una distancia de fusión pasada como argumento. Obtener el dendrograma del agrupamiento. Devolver los distintos clusters en los que se encuentra un elemento del dataset en todos los niveles del agrupamiento jerárquico.

De los siguientes algoritmos indica cuál de ellos no es Un proceso iterativo. LLE. K-Medias. t-SNE. EM.

Estamos realizando un clustering espectral paso a paso con K=4. Vemos que la multiplicidad del autovalor lambda = 0 es uno, y que el segundo autovector no discrimina claramente los datos en 4 grupos. Entonces: Debo construir una matriz con mas autovectores por columnas (empíricamente hasta que haya un salto apreciable en los valores de los autovalores) y realizar K- Means sobre ella. Esta técnica no es válida para este dataset. Debería probar con otra familia de algoritmos de agrupamiento. El dataset está mal formado porque siempre la multiplicidad del autovalor lambda = 0 es mayor que 1. El autovector asociado al autovalor lambda = 0 es decir, el vector 1, nos indica que solo hay un cluster.

Si f: R x R cumple que f(x,y) <= f(x,z) + f(z,y) para todo x,y,z de R y además f(x,y) = f(y,x) y f(x,y) >= 0. f es una métrica. f no puede ser una métrica. f puede ser una métrica. Estas propiedades de f no tienen que ver con la caracterización de las métricas.

Un supermecado describe las preferencias de compra de los clientes mediante un vector donde cada componente es el numero de unidades que ha comprado de un producto específico (Ej. el vector podria estar formado por (aceite, vino, agua,..)). Un cliente ha comprado los mismos productos que otro pero el doble de cantidad. La distancia del coseno entre estos dos clientes es: sqrt(2). 2. 0. 1.

En el algoritmo EM,. Lo que hallamos es la probabilidad de que cada una de las gausianas que se nos dan como datos de entrada en el algoritmo haya generado el Dataset que tambien se da como entrada. Lo que hallamos es la media y la matriz de covarianza (mu, sum) que definen a cada una de las gausianas más probables de haber generado independientemente a un subconjunto los datos del Dataset. Lo que hallamos es la terna (w_{i}, mu_{i}, sum_{i}) para cada gausiana componente de la mezcla donde wi es la probabilidad que que dicha gausiana sea la elegida para extraer un dato y(mu_{i}, sum_{i}) son la media y la matriz de covarian- za de la gausiana i-esima. Lo que hallamos es, para cada dato xi una gausiana centrada en él mismo (xi, sum_i), que establece la probabilidad de que los datos vecinos (más próximos a xi) del dataset pertenezcan al mismo cluster que xi.

En el algoritmo MDS, dada como entrada la matriz de disimilaridad D, obtenemos la matriz B = - 1/2 * HDH para. Encontrar mediante su diagonalización los puntos del espacio embebido que buscamos. Despejar en la igualdad de matrices B = X * X ^ T la matriz X que es la que contiene los puntos embebidos. En MDS no se calcula ninguna matriz B. Se trabaja siempre con D. Transformar las distancias euclídeas de la matriz D en las distancias geodésicas.

De todas las partes que constituyen el algoritmo Isomap, lo que lo hace apto para datasets no lineales es: El uso de MDS. El cálculo de geodésicas como verdaderas distancias entre los puntos. La organización del dataset en un grafo. El enunciado de la pregunta es falso, Isomap es un reductor de dimensionalidad lineal.

En el algoritmo t-SNE, para los puntos embebidos, se utiliza una distribución de t-Student (Cauchy) en lugar de una Gausiana (como en el dataset original) porque. Si usáramos dos gausianas (aunque fueran distintas) la divergencia K-L sería siempre 0. La probabilidad de que un punto embebido sea vecino de otro se expresa mejor con una distribución de cauchy en espacio de pocas dimensiones (dos o tres dimensiones). Elegir la distribución de probabilidad que queramos y la de t-student es computacionalmente más sencilla y menos costosa en recursos. La distribución t-student tiene colas más largas (es decir, a elementos lejanos de la media les asigna probabilidad no 0) y esto aminora el problema conocido como ``crowding´´.

En el contexto del agrupamiento espectral y dentro del proceso de optimización que se lleva a cabo, el concepto del 'volumen' de un subgrafo es importante para garantizar: La convergencia del proceso de optimización. Que las componentes conexas en las que se parte un grafo tienen un tamaño parecido (en número de vértices y conexiones). Que el número de aristas que se cortan para hacer de dicho subgrafo una componente conexa es al menos igual a dicho volumen. Que la inercia de cada una de las conponentes conexas resultantes es parecida.

El algoritmo LLE sobre un dataset S=x_{1}, x_{2} ,…xn define el error de reconstrucción de un elemento xi sobre k-vecinos como: sum_j(w_ij) |x_{i} - x_{j}| ^ 2. sum_j |w_ij x_i - x_j |^ 2. |x_i - w_ij - sum_j(w_ij * x_j)|^ 2. sum_i |x_i - sum_j(w_ij * x_j)|^ 2.

Considera la estructura de railes de una montaña rusa. Es una variedad de dimensión intrínseca 2 en un espacio R ^ 3. Es una variedad de dimensión intrínseca 3 en un espacio R ^ 3. Es una variedad de dimensión intrínseca 2 en un espacio R ^ 4. Es una variedad de dimensión intrínseca 1 en un espacio R ^ 3.

En t-SNE, fijados sus parámetros, dos ejecuciones sobre el mismo dataset pueden dar diferentes embebimientos porque. Las gausianas del dataset pueden ser distintas cada ejecución. La inicialización del conjunto de puntos Y para el descenso por gradiente en el espacio embebido puede ser distinta en cada ejecución. La entropía es distinta en cada ejecución. El dataset no ha sido normalizado.

En el contexto del agrupamiento por densidad considera la siguiente situación de 4 puntos: El punto A es un punto frontera que está en la e-vecindad del punto B que es core. A su vez el punto C es un punto core que está en la e- vecindad del punto B. El punto D está en la evecindad del punto C. Entonces: Los puntos A y D no tienen ninguna relación basada en densidad. El punto Des directamente alcanzable por densidad (directly density-reachable) desde A. Los puntos A y D son conectados por densidad (density- connected). Los puntos A y D son alcanzables por densidad (density-reachable).

En alguna de las PCAs que hemos usado en laboratorio calculábamos la varianza explicada por cada autovector porque. si la suma de estos datos no daba 1.0, entonces la PCA no había salido bien. nos daba una medida directa del ruido existente en cada dirección principal. esto nos permite determinar cuánta información (de algún modo) perdemos cuando nos quedamos con al- gunos autovectores solamente. nos permitia clasificar a los autovectores como menos fiables (los de mayor varianza explicada) y más fiables (los de menor varianza).

En la práctica 3 sobre K-Means utilizamos en la primera parte el método SMOTE para: Obtener más datos para el dataset mediante interpola- ción de los ya existentes. Encontrar y eliminar datos que se salían del rango de valores aceptable (detección de outsiders). Normalizar de una forma más adecuada los datos. Evaluar la calidad de los clusters generados, como al- ternativa al indicador Silhouette.