k q-pisos

En minería de datos y aprendizaje automático , el algoritmo k q -planos ^{[1] [2]} es un método iterativo que tiene como objetivo dividir m observaciones en k grupos donde cada grupo está cerca de un q -plano , donde q es un número entero dado.

Es una generalización del algoritmo k -means . En el algoritmo k -means, los grupos se forman de manera que cada grupo está cerca de un punto, que es un 0 -plano. El algoritmo k q -flats proporciona mejores resultados de agrupación que el algoritmo k -means para algún conjunto de datos.

Descripción

Formulación del problema

Dado un conjunto A de m observaciones donde cada observación es un vector real n-dimensional, el algoritmo k q -planos tiene como objetivo dividir m puntos de observación generando k q -planos que minimizan la suma de los cuadrados de las distancias de cada observación al punto más cercano. q -plano. ${\displaystyle (a_{1},a_{2},\dots ,a_{m})}$ ${\displaystyle a_{i}}$

Un q -plano es un subconjunto de que es congruente con . Por ejemplo, un 0 -bemol es un punto; un 1 -bemol es una línea; un 2 -plano es un plano; un plano es un hiperplano . q -plano se puede caracterizar por el conjunto solución de un sistema lineal de ecuaciones: , donde , . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {R} ^{q}}$ ${\displaystyle n-1}$ ${\displaystyle F=\left\{x\mid x\in \mathbb {R} ^{n},W'x=\gamma \right\}}$ ${\displaystyle W\in \mathbb {R} ^{n\times (n-q)}}$ ${\displaystyle \gamma \in \mathbb {R} ^{1\times (n-q)}}$

Denota una partición de como . El problema se puede formular como ${\displaystyle \{1,2,\dots ,n\}}$ ${\displaystyle S=(S_{1},S_{2},\dots ,S_{k})}$

¿Dónde está la proyección de sobre ? Tenga en cuenta que es la distancia desde hasta . ${\displaystyle P_{F_{i}}(a_{j})}$ ${\displaystyle a_{j}}$ ${\displaystyle F_{i}}$ ${\displaystyle \|a_{j}-P_{F_{i}}(a_{j})\|=\operatorname {dist} (a_{j},F_{l})}$ ${\displaystyle a_{j}}$ ${\displaystyle F_{l}}$

Algoritmo

El algoritmo es similar al algoritmo k-means (es decir, el algoritmo de Lloyd) en que alterna entre asignación de conglomerados y actualización de conglomerados. En concreto, el algoritmo comienza con un conjunto inicial de q -planos y continúa alternando entre los dos pasos siguientes: ${\displaystyle F_{l}^{(0)}=\left\{x\in R^{n}\mid \left(W_{l}^{(0)}\right)'x=\gamma _{l}^{(0)}\right\},l=1,\dots ,k}$

Asignación de clúster

(dado q -planos, asigne cada punto al q -plano más cercano): el i -ésimo grupo se actualiza como

$${\displaystyle S_{i}^{(t)}=\left\{a_{j}\mid \left\|(W_{i}^{(t)})'a_{j}-\gamma _{i}^{(t)}\right\|_{F}=\min _{l=1,\dots ,k}\left\|(W_{l}^{(t)})'a_{j}-\gamma _{l}^{(t)}\right\|_{F}\right\}.}$$

Actualización del clúster

(dada la asignación de grupo, actualice q -flats ): para , deje las filas correspondientes a todas las asignadas al grupo l . Se establece como la matriz cuyas columnas son los vectores propios ortonormales correspondientes a los valores propios mínimos de y . ${\displaystyle l=1,\dots ,k}$ ${\displaystyle A(l)\in R^{m(l)\times n}}$ ${\displaystyle a_{i}}$ ${\displaystyle W_{l}^{(t+1)}}$ ${\displaystyle (n-q)}$ ${\displaystyle A(l)'\left(I-{\tfrac {ee'}{m}}\right)A(l)}$ ${\displaystyle \gamma _{l}^{(t+1)}={\frac {e'A(l)W_{l}^{(t+1)}}{m}}}$

Deténgase cuando las asignaciones ya no cambien.

El paso de asignación de conglomerados utiliza el siguiente hecho: dado un q -plano y un vector a , donde , la distancia de a al q -plano es ${\displaystyle F_{l}=\{x\mid W'x=\gamma \}}$ ${\displaystyle W'W=I}$ ${\displaystyle F_{l}}$ ${\textstyle \operatorname {dist} (a,F_{l})=\min _{x:W'x=\gamma }\left\|x-a\right\|_{F}^{2}=\left\|W(W'W)^{-1}(W'x-\gamma )\right\|_{F}^{2}=\left\|W'x-\gamma \right\|_{F}^{2}.}$

La parte clave de este algoritmo es cómo actualizar el grupo, es decir, dados m puntos, cómo encontrar un q -plano que minimice la suma de los cuadrados de las distancias de cada punto al q -plano. Matemáticamente, este problema es: dado resolver el problema de optimización cuadrática ${\displaystyle A\in R^{m\times n},}$

donde se da, y . ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ ${\displaystyle e=(1,\dots ,1)'\in \mathbb {R} ^{m\times 1}}$

El problema se puede resolver utilizando el método del multiplicador lagrangiano y la solución es la que se proporciona en el paso de actualización del clúster.

Se puede demostrar que el algoritmo terminará en un número finito de iteraciones (no más que el número total de asignaciones posibles, que está limitado por ). Además, el algoritmo terminará en un punto en el que el objetivo general no pueda reducirse ni mediante una asignación diferente ni definiendo nuevos planos de conglomerados para estos conglomerados (dicho punto se denomina "localmente óptimo" en las referencias). ${\displaystyle k^{m}}$

Este resultado de convergencia es consecuencia del hecho de que el problema (P2) se puede resolver exactamente. El mismo resultado de convergencia es válido para el algoritmo k -means porque el problema de actualización del clúster se puede resolver exactamente.

Relación con otros métodos de aprendizaje automático

k -algoritmo de medias

El algoritmo k q -flats es una generalización del algoritmo k -means. De hecho, el algoritmo k -medias es un algoritmo k 0 -planos ya que un punto es un 0 -plano. A pesar de su conexión, deberían usarse en escenarios diferentes. k q Algoritmo de planos para el caso de que los datos se encuentren en unos pocos espacios de baja dimensión. El algoritmo k -means es deseable para el caso de que los grupos sean de dimensión ambiental. Por ejemplo, si todas las observaciones se encuentran en dos líneas, se puede utilizar el algoritmo k q -planos con ; si las observaciones son dos nubes gaussianas, se puede utilizar el algoritmo k -means. ${\displaystyle q=1}$

Aprendizaje disperso del diccionario

Las señales naturales se encuentran en un espacio de alta dimensión. Por ejemplo, la dimensión de una imagen de 1024 por 1024 es aproximadamente 10 ⁶ , que es demasiado alta para la mayoría de los algoritmos de procesamiento de señales. Una forma de deshacerse de la alta dimensionalidad es encontrar un conjunto de funciones básicas, de modo que la señal de alta dimensión pueda representarse mediante solo unas pocas funciones básicas. En otras palabras, los coeficientes de representación de la señal se encuentran en un espacio de baja dimensión, en el que es más fácil aplicar algoritmos de procesamiento de señales. En la literatura, la transformada wavelet se usa generalmente en el procesamiento de imágenes y la transformada de Fourier generalmente se usa en el procesamiento de audio. El conjunto de funciones básicas suele denominarse diccionario .

Sin embargo, no está claro cuál es el mejor diccionario a utilizar una vez que se le proporciona un conjunto de datos de señal. Un enfoque popular es encontrar un diccionario cuando se le proporciona un conjunto de datos utilizando la idea de Sparse Dictionary Learning. Su objetivo es encontrar un diccionario, de modo que la señal pueda ser representada escasamente por el diccionario. El problema de optimización se puede escribir de la siguiente manera.

${\displaystyle \min _{B,R}\|X-BR\|_{F}^{2}}$sujeto a ${\displaystyle \|R_{i}\|_{0}\leq q}$

dónde

• X es una matriz d -por- N. Cada columna de X representa una señal y hay un total de N señales.
• B es una matriz d -por- l . Cada columna de B representa una función básica, y hay un total de l funciones básicas en el diccionario.
• R es una matriz de l por N. ( i -ésimas columnas de R ) representan los coeficientes cuando usamos el diccionario B para representar las i -ésimas columnas de X. ${\displaystyle R_{i}}$
• ${\displaystyle \|v\|_{0}}$denota la norma cero del vector v .
• ${\displaystyle \|V\|_{F}}$denota la norma de Frobenius de la matriz V.

La idea del algoritmo k q -flats es similar al aprendizaje disperso de diccionarios en la naturaleza. Si restringimos el subespacio q -plano a q -dimensional, entonces el algoritmo k q -planos simplemente encuentra el subespacio q -dimensional cerrado para una señal dada. El aprendizaje disperso de diccionarios también hace lo mismo, excepto por restricciones adicionales en la escasez de la representación. Matemáticamente, es posible demostrar que el algoritmo k q -flats tiene la forma de aprendizaje de diccionario disperso con una estructura de bloques adicional en R.

Sea una matriz, donde las columnas de son la base del k -ésimo piso. Entonces la proyección de la señal x al k -ésimo plano es , donde es un coeficiente q -dimensional. Denotemos la concatenación de la base de K pisos, es fácil demostrar que el algoritmo k q -plano es el mismo que el siguiente. ${\displaystyle B_{k}}$ ${\displaystyle d\times q}$ ${\displaystyle B_{k}}$ ${\displaystyle B_{k}r_{k}}$ ${\displaystyle r_{k}}$ ${\displaystyle B=[B_{1},\cdots ,B_{K}]}$

${\displaystyle \min _{B,R}\|X-BR\|_{F}^{2}}$sujeto a y R tiene una estructura de bloques. ${\displaystyle \|R_{i}\|_{0}\leq q}$

La estructura de bloques de R se refiere al hecho de que cada señal está etiquetada en un solo plano. Comparando las dos formulaciones, k q -plano es lo mismo que el modelado de diccionario disperso cuando y con una estructura de bloque adicional en R. Los usuarios pueden consultar el artículo de Szlam ^[3] para obtener más información sobre la relación entre los dos conceptos. ${\displaystyle l=K\times q}$

Aplicaciones y variaciones

Clasificación

La clasificación es un procedimiento que clasifica una señal de entrada en diferentes clases. Un ejemplo es clasificar un correo electrónico en clases de spam o no spam . Los algoritmos de clasificación suelen requerir una etapa de aprendizaje supervisado. En la etapa de aprendizaje supervisado, los datos de entrenamiento de cada clase se utilizan para que el algoritmo aprenda las características de la clase. En la etapa de clasificación, una nueva observación se clasifica en una clase utilizando las características que ya fueron entrenadas.

El algoritmo k q -plano se puede utilizar para la clasificación. Supongamos que hay un total de m clases. Para cada clase, k pisos se entrenan a priori mediante un conjunto de datos de entrenamiento. Cuando llegue un nuevo dato, busque el piso más cercano al nuevo dato. Luego los nuevos datos se asocian a la clase del piso más cercano.

Sin embargo, el rendimiento de la clasificación se puede mejorar aún más si imponemos alguna estructura a los pisos. Una posible opción es exigir que los diferentes pisos de diferentes clases estén suficientemente separados. Algunos investigadores ^[4] utilizan esta idea y desarrollan un algoritmo discriminativo k q-plano.

K-métricas [3]

En el algoritmo k q -flats, se utiliza para medir el error de representación. denota la proyección de x al plano F . Si los datos se encuentran en un plano de dimensión q , entonces un solo plano q puede representar los datos muy bien. Por el contrario, si los datos se encuentran en un espacio de dimensiones muy altas pero cerca de un centro común, entonces el algoritmo k-medias es una mejor manera que el algoritmo k q -plano para representar los datos. Esto se debe a que k -means utiliza el algoritmo para medir el error, donde denota el centro. K-metrics es una generalización que utiliza tanto la idea de plano como de media. En k-métricas, el error se mide mediante la siguiente métrica de Mahalanobis. ${\displaystyle \|x-P_{F}(x)\|^{2}}$ ${\displaystyle P_{F}(x)}$ ${\displaystyle \|x-x_{c}\|^{2}}$ ${\displaystyle x_{c}}$

$${\displaystyle \left\|x-y\right\|_{A}^{2}=(x-y)^{\mathsf {T}}A(x-y)}$$

donde A es una matriz semidefinida positiva.

Si A es la matriz identidad, entonces la métrica de Mahalanobis es exactamente la misma que la medida de error utilizada en k -medias. Si A no es la matriz identidad, entonces se favorecerán ciertas direcciones como medida de error k q -plana. ${\displaystyle \|x-y\|_{A}^{2}}$

Referencias

1. Bradley, PD; Mangasarian, OL (2000). "Agrupación de planos k". Revista de optimización global . 16 (1): 23–32. doi :10.1023/A:1008324625522. S2CID  913034.
2. Tseng, P. (2000). "Q-Plano más cercano a m puntos". Revista de teoría y aplicaciones de optimización . 105 (1): 249–252. doi :10.1023/A:1004678431677. ISSN  0022-3239. S2CID  118142932.
3. Szlam, Arturo; Sapiro, Guillermo (14 de junio de 2009). "K -métricas discriminativas". En Bottou, León; Littman, Michael (eds.). Actas de la 26ª Conferencia Internacional Anual sobre Aprendizaje Automático . ACM. págs. 1009-1016. doi :10.1145/1553374.1553503. hdl :11299/180116. ISBN 978-1-60558-516-1. S2CID  2509292.
4. Szlam, A.; Sapiro, G. (2008). "Aprendizaje supervisado mediante k q-Flats discriminativos" (PDF) .