k q-bemoles

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

Es una generalización del algoritmo k -means . En el algoritmo k -means, los clústeres se forman de manera que cada clúster esté cerca de un punto, que es un 0 -flat. El algoritmo k q -flats brinda mejores resultados de agrupamiento que el algoritmo k -means para algunos conjuntos 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 -flats tiene como objetivo particionar m puntos de observación generando k q -flats que minimizan la suma de los cuadrados de las distancias de cada observación a un q -flat más cercano. ${\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 -plano es un punto; un 1 -plano es una línea; un 2 -plano es un plano; un -plano es un hiperplano . Un 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)}}$

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

donde es la proyección de sobre . Nótese que es la distancia desde a . ${\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 el sentido de que alterna entre la asignación de clústeres y la actualización de clústeres. En concreto, el algoritmo comienza con un conjunto inicial de q -flats 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

(dados q -flats, asignar cada punto al q -flat 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 clúster, actualice los q -planos): Para , sea con filas correspondientes a todas las asignadas al clúster l . Establezca como la matriz cuyas columnas son los vectores propios ortonormales correspondientes a los valores propios más pequeños 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}}}$

Detenerse cuando las asignaciones ya no cambien.

El paso de asignación de clúster utiliza el siguiente hecho: dado un q -plano y un vector a , donde , la distancia desde 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 clúster, 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 de Lagrangiano y la solución es la que se da 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 se puede reducir ni con una asignación diferente ni definiendo nuevos planos de clúster para estos clústeres (este punto se denomina "óptimo localmente" en las referencias). ${\displaystyle k^{m}}$

Este resultado de convergencia es consecuencia del hecho de que el problema (P2) se puede resolver con exactitud. El mismo resultado de convergencia se aplica al algoritmo k -means porque el problema de actualización de clústeres se puede resolver con exactitud.

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

a-significa algoritmo

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

Aprendizaje de diccionarios dispersos

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 de 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 base, de modo que la señal de alta dimensión pueda representarse con solo unas pocas funciones base. En otras palabras, los coeficientes de la 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 se usa generalmente en el procesamiento de audio. El conjunto de funciones base generalmente se llama diccionario .

Sin embargo, no está claro cuál es el mejor diccionario para usar una vez que se proporciona un conjunto de datos de señales. Un enfoque popular es encontrar un diccionario cuando se proporciona un conjunto de datos utilizando la idea de aprendizaje de diccionario disperso. Su objetivo es encontrar un diccionario, de modo que la señal pueda ser representada de manera dispersa 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 N señales en total.
• B es una matriz d por l . Cada columna de B representa una función base y hay un total de l funciones base en el diccionario.
• R es una matriz 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 de diccionario disperso en su naturaleza. Si restringimos el q -flat a un subespacio q -dimensional, entonces el algoritmo k q -flats simplemente encuentra el subespacio q -dimensional cerrado para una señal dada. El aprendizaje de diccionario disperso también hace lo mismo, excepto por una restricción adicional en la escasez de la representación . Matemáticamente, es posible demostrar que el algoritmo k q -flats es de la forma de aprendizaje de diccionario disperso con una estructura de bloque adicional en R.

Sea una matriz, donde las columnas de son la base del k -ésimo plano. Entonces la proyección de la señal x al k -ésimo plano es , donde es un coeficiente q -dimensional. Sea la concatenación de la base de K planos, 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 bloque. ${\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. Al comparar las dos formulaciones, k q -flat es lo mismo que el modelado de diccionario disperso cuando y con una estructura de bloques 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 generalmente requieren una etapa de aprendizaje supervisado. En la etapa de aprendizaje supervisado, se utilizan los datos de entrenamiento para cada clase 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 se entrenaron.

El algoritmo k q -flat se puede utilizar para la clasificación. Supongamos que hay un total de m clases. Para cada clase, se entrenan a priori k flats mediante un conjunto de datos de entrenamiento. Cuando llegan nuevos datos, se encuentra el flat que está más cerca de los nuevos datos. Luego, los nuevos datos se asocian a la clase del flat más cercano.

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

K-métricas

Fuente: ^[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 q -dimensión, entonces un único q -plano puede representar los datos muy bien. Por el contrario, si los datos se encuentran en un espacio de dimensión muy alta pero cerca de un centro común, entonces el algoritmo k-means es una mejor manera que el algoritmo k q -flat para representar los datos. Esto se debe a que el algoritmo k -means se utiliza 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-metrics, 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 favorecerá ciertas direcciones como la medida de error k q -plana. ${\displaystyle \|x-y\|_{A}^{2}}$

Referencias

1. Bradley, PS; Mangasarian, OL (2000). "Agrupamiento en el plano k". Revista de optimización global . 16 (1): 23–32. doi :10.1023/A:1008324625522. S2CID  913034.
2. Tseng, P. (2000). "Q-Flat 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, Arthur; Sapiro, Guillermo (14 de junio de 2009). "Métricas k discriminantes". En Bottou, Léon; 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. Número de identificación del sujeto  2509292.
4. Szlam, A.; Sapiro, G. (2008). "Aprendizaje supervisado mediante k q-Flats discriminativos" (PDF) .