Agrupamiento espectral

En estadístiques multivariantes i agrupamiento de les senyes, les tècniques agrupamiento espectral fan us del espectre (valors propis) de la matriu de similitut de les senyes per a realisar reducció de dimensionalidad abans de l'agrupació en un menor número de dimensions. La matriu de similitut es proporciona com una entrada i consta d'una evaluació quantitativa de la similitut relativa de cada parell de punts en el conjunt de senyes.

En aplicació a la segmentación de l'image, l'agrupació espectral es coneix com categorisació basada en la segmentación.

Algoritmes

Donat un conjunt enumerat de punts de senyes, la matriu de similitut es pot definir com una matriu simètrica $A$, a on $A_{ij}\ge 0$ representa una mida de la similitut entre els punts de senyes en índexs $i$ i $j$.

Una de les tècniques de agrupamiento espectral és l'algoritme de corts normalisats o algoritme Shi-Malik, introduït per Jianbo Shi i Jitendra Malik, comunament utilisat para segmentación d'imàgens. Es dividix en dos conjunts de punts $(B_1,B_2)$ basat en l' autovector $v$ corresponent a la segona més chicotet autovalor de la Matriu laplaciana definix com

$L^{norma}:=I-D^{-1/2}A{D}^{-1/2}$,

a on $D$ és la matriu diagonal

$D_{ii}=\sum _j{A}_{ij}.$

Un algoritme matemàticament equivalent pren el vector propi corresponent a la major valor propi de la matriu laplaciana normalisada $P=D^{-1}A$.

Una atra possibilitat és utilisar la matriu laplaciana definida com

$L:=D-A$

en lloc de la matriu laplaciana normalisada .

El particionamiento es pot fer de vàries maneres, tals com per mig del càlcul de la mijana $m$ dels components del vector propi segon més chicotet $v$, i la colocació de tots els punts el component dels quals en $v$ és major que $m$ en $B_1$, i el restant en $B_2$. L'algoritme pot ser utilisat per a l'agrupació jeràrquica per mig de la partició repetidament els subconjunts d'esta manera.

Com a alternativa a l'informàtica només un vector propi, k vector propi s per a alguns k , es calculen, i després un atre algoritme (per eixemple, k-miges) s'utilisa per a punts d'arracada per la seua respectiva k components d'estos vectores propis.

L'eficiència de agrupamiento espectral es pot millorar si la solució al problema de valor propi corresponent es realisa en un moda de matriu lliure, és dir, sense manipular de forma explícita o inclús el càlcul de la matriu de similitut, com, per eixemple, en l'Algoritme de Lanczos.

Per a gràfics de gran tamany, el segon valor propi de la gràfica (normalisat) és a sovint mal condicionada la matriu laplaciana, lo que du a reduir la velocitat de convergència de valors propis solucionadores iterativos. preacondicionamiento és una tecnologia clau accelerar la convergència, per eixemple, en el LOBPCG método de matriu lliure. Agrupamiento espectral s'ha aplicat en èxit en grans gràfics identificant primer el seu estructura de la comunitat, i després agrupar comunitats

Agrupamiento espectral està estretament relacionat en reducció de dimensionalidad no llineal, i les tècniques de reducció de dimensions tals com la incrustación localment llineal es poden utilisar per a reduir els errors de soroll o valors atípics. Un còdic de font oberta està disponible en

Relació en k - means

El kernel k - means problema és una extensió de la k - significa problema en el que els punts de senyes d'entrada s'assignen de forma no llineal en un espai de característiques de dimensions superiors a través d'una funció kernel $k(x_i,x_j)={\varphi }^T(x_i)\varphi (x_j)$. El núcleu ponderada k - significa problema adicional s'estén este problema per mig de la definició d'un pes $w_r$ per a cada grup com el recíproc del número d'elements en el cluster,

$\underset{\{C_s\}}{\max }\sum _{r=1}^k{w}_r\sum _{x_i,x_j\in C_r}k(x_i,x_j).$

Supongam $F$ és una matriu dels coeficients de la normalisació per a cada punt per a cada grup $F_{ij}=w_r$ si $i,jin{c}_r$ i zero en cas contrari. Supongam $K$ és la matriu del kernel per a tots els punts. El núcleu ponderada k - significa un problema en n punts i clusters k es dona com,

$\underset{F}{\max }\mathrm{trace}\left(KF\right)$ de tal manera que,

$F=G_{n\times k}{G}_{n\times k}^T$

$G^{T}G=I$

tal que $textrank(G)=k$. Ademés, hi ha identitat llimita en $F$ donada per,

$F\cdot 𝕀=𝕀$

a on $𝕀$ representa un vector d'uns.

$F^T𝕀=𝕀$

Este problema pot ser refosa com,

$\underset{G}{\max }\text{ trace }\left(G^{T}G\right).$

Este problema és equivalent al problema de agrupamiento espectral quan les llimitacions d'identitat en $F$ estan relaixats. En particular, el núcleu ponderada k - significa problema pot ser reformulada com un problema de agrupamiento espectral (particionamiento gràfic) i viceversa. L'eixida dels algoritmes són vectores propis que no complixquen els requisits d'identitat per a les variables indicadores definits per $F$. Per lo tant, es requerix de post-processament dels vectores propis de l'equivalència entre els problemes. Transformar el problema de agrupamiento espectral en un kernel ponderada k - significa problema es reduïx en gran medida la càrrega computacional