Clustering evaluation for deinterleaving

Abstract

Deinterleaving is a fundamental step in a lot of processing in ESM and radar systems, enabling users and/or client programs to focus on data from a single emitter at a time, rather than a mixture of data from several emitters. When developing deinterleaving algorithms, it is sometimes useful to compare deinterleaving results with a model solution. Such a solution may be available because one has some alternative way of deinterleaving existing interleaved data, because one generates the data oneself, for example with a PDW simulator, or because one combines (interleaves) several existing non-interleaved data sets. This report discusses some methods of assessing clustering results in the context of deinterleaving, and focuses on evaluation criteria that consider the problem of clustering as a binary classification problem, where the objects to be classified are all the possible pairs of distinct input points. A pair is classified as positive or negative, respectively, if the two points in the pair are in the same or different clusters. An efficient evaluation algorithm is developed, which avoids visiting every pair of points, but instead calculates the necessary information based on the sizes of clusters. Finally, the evaluation criteria are used along with some already deinterleaved data in order to optimize a key parameter to the LINE deinterleaving algorithm. This leads to a new choice of evaluation criterion that is more suitable to the current data set. The GEOIDE deinterleaving algorithm is tested on the same data and the results are discussed. The same data set is used for generating new data sets, by combining deinterleaved emissions in new ways. The new data sets are used for testing LINEs deinterleaver further.

Deinterleaving er et grunnleggende steg i ESM- og radarsystemer, og gjør det mulig for brukere og/eller programmer å fokusere på data fra en enkelt emitter, istedenfor en blanding av data fra flere emittere. Ved utvikling av deinterleavingsalgoritmer, er det noen ganger nyttig å sammenligne deinterleavingsresultater med en fasit. En fasit kan være tilgjengelig fordi man har en alternativ måte å deinterleave eksisterende interleavede data, fordi en genererer data selv, for eksempel ved hjelp av en PDW simulator, eller fordi man kombinerer (interleaver) flere eksisterende sett av ikke-interleavede pulsdata. Denne rapporten tar for seg noen metoder for å evaluere klyngingsresultater i forbindelse med deinterleaving, og fokuserer på evalueringskriterier som betrakter klynging som et binært klassifiseringsproblem, hvor objektene som skal klassifiseres er alle mulige par av distinkte inputpunkter (pulser). Et par er klassifisert som henholdsvis positivt eller negativt, dersom de to punktene i paret er i samme eller forskjellige grupper. En effektiv evalueringsalgoritme er utviklet, som unngår å besøke hvert mulig par av punkter, men i stedet beregner den nødvendige informasjon basert på størrelsene av punktklynger. Evalueringskriteriene brukes sammen med noen ferdig deinterleavede data for å optimalisere en viktig parameter i LINEs deinterleavingsalgoritme. Evalueringen av disse dataene leder til valg av et nytt evalueringskriterium, som er mer egnet til det gjeldende datasettet. GEOIDEs deinterleavingsalgoritme er testet på samme datasett, og resultatene diskuteres. Det samme datasettet brukes til å generere nye datasett, ved å sette emisjonene sammen på nye måter, og LINEs deinterleaver prøves på nye måter.