I teoretisk datalogi er spektral partitionering eller spektral klyngedannelse på engelsk en type datadeling, der tager højde for inputets spektrale egenskaber. Spektral opdeling bruger oftest egenvektorerne i en lighedsmatrix . Sammenlignet med klassiske algoritmer som k-middel , giver denne teknik fordelen ved at klassificere datasæt af "ikke-globulær" struktur i et passende repræsentationsrum.
Denne partitionering anvendes især i kunstig intelligens , hvor udtrykket spektral klassifikation henviser til det faktum, at man udfører ukontrolleret klassificering ved hjælp af denne type partitionering.
Spektral opdeling er en metode til opdeling i K- grupper baseret på minimering af et " skåret " type kriterium (enkelt snit ved K = 2 eller multiple snit ved K≥2). Disse to mål udtrykker gruppernes indre samhørighed i forhold til deres dissociation fra hinanden. De er direkte funktioner af en lighedsmatrix mellem objekter, betegnet S .
Givet et sæt N- objekter er det muligt at opnå en detaljeret gengivelse af dette sæt i form af en vægtet graf (jf . Grafteori ), bemærket G (V, E, S) . V betegner sættet med N- noder i grafen, der svarer til objekterne; E er sættet med inter-node buer og S er vægtmatricen for buerne (lighedmatrix), symmetrisk og ikke negativ ( S ij angiver ligheden mellem objekterne x i og x j ).
For at løse problemet med optimering af det tidligere definerede skærekriterium er den spektrale opdeling baseret på anvendelsen af spektret af datalignende matrix med henblik på opdeling af alle objekter i et rum med mindre dimension. Vi har derefter et grafdelingsproblem, hvor knudepunkterne i den samme gruppe er ens, og knudepunkterne, der tilhører forskellige grupper, er forskellige.
Målet med at opbygge en vægtet graf er at redegøre for (eller modellere) nabolagsforholdet mellem objekter. Der er derefter flere måder at gå videre på:
I litteraturen gør flere teknikker det muligt at opnå et mål for lighed mellem to objekter. Valget af lighedsfunktion afhænger primært af dataens oprindelsesområde (f.eks. Søgedokumenter , webdatamining osv.), Men også typen af data (som kan beskrives ved hjælp af numeriske variabler, kategoriske, binære filer osv. .). De to mest populære og mest anvendte formler er dog:
hvor d er et afstandsmål (af euklidisk, Manhattan, Minkowski-type osv.) og σ, en skalaparameter, hvis værdi indstilles af brugeren.
med B, der angiver datamatrixen (sammensat af N- objekter hver beskrevet af M- attributter) standardiseret online.
De spektrale partitioneringsalgoritmer bruger informationen indeholdt i egenvektorerne i en laplacisk matrix (bygget fra lighedmatricen S ) for at detektere en datastruktur. Lad D være den diagonale matrix af grader ( D = diag (D 11 , ..., D NN ) ) sådan at:
repræsenterer graden af i th knudepunkt i grafen G . Det er derefter muligt at bygge den laplaciske matrix L ved hjælp af en af de mange standardiseringer, der findes i litteraturen:
(hvor d max angiver den maksimale grad af D og I er identitetsmatrixen). Det næste trin består i at udtrække egenvektorerne fra den laplaciske matrix . Det demonstreres, at brugen af K (antal ønskede grupper) første ortogonale egenvektorer af L (svarende til de K- mindste egenværdier ) gør det muligt at opnå et projektionsrum med mindre dimension (i K- dimensioner) end l oprindelige rum (i M dimensioner). Matrixen X konstrueres derefter ved at lagre disse egenvektorer (kolonner) . Blandt algoritmerne til beregning af egenværdier kan vi citere metoden til itereret effekt .
Data partitionering udføres dernæst på matricen X . Faktisk består det første trin i at betragte hver række i denne matrix som repræsenterende et objekt i spektralrum (i K- dimensioner). Det andet trin er derefter at anvende en ikke-overvåget klassificeringsalgoritme på denne matrix. Den opdeling af data i K -grupper så kommer ned til tildelingen af det oprindelige objekt x jeg til gruppen k hvis og kun hvis den jeg th rækken af X er blevet tildelt til gruppen k .
Selvom den partitioneringsalgoritme, der oftest bruges i litteraturen, er K-middelalgoritmen, er det meget muligt at bruge enhver anden metode uden opsyn for at klassificere de forskellige objekter.