Torsten Leander

Force Directed Clustering as a means to extract dependencies in data

Abstract

Force Directed Clustering has been used for some time in VLSI chip design and graph visualization. The idea is to represent objects, such as chip components and graph nodes, as particles and to cluster them with forces representing some kind of inner relations in order to improve the layout.

The object of this Master’s thesis has been to implement and evaluate a method based on Force Directed Clustering to detect dependencies in large masses of data. To demonstrate and test the method the task to de-scramble randomly permuted image sensors, using several images recorded and distorted with the same sensor is used. The clustering forces applied to the particles representing the pixel receptors have been based on the information theory concept of the mutual information of each pair of receptors.

The method is found to work well, but to be computationally heavy for large images. Because of this the method is only tried on images of up to 400 pixels.



Beroenden i data och Force Directed Clustering

Sammanfattning

Force Directed Clustering har länge använts inom design av VLSI-chip och visualisering av grafer. Metoden går ut på att man representerar objekt, t.ex. komponenter på ett chip eller noderna i en graf, med partiklar och förbättrar layouten genom att klustra dem med hjälp av krafter som motsvarar någon form av relationer mellan objekten.

Målet med detta arbete har varit att implementera och utvärdera en metod baserad på Force Directed Clustering för att detektera beroenden i stora datamängder. Som exempelproblem används uppgiften att rekonstruera slumpmässigt permuterade bildsensorer genom att använda flera bilder som upptagits och förvrängts av en och samma sensor. De klustrande krafterna som ansätts på partiklarna representerande pixelreceptorerna är baserade på den mutual information som funnits inom varje par av pixelreceptorer.

Metoden fungerade bra, men var beräkningstung för stora bildsensorer. Därför testades den endast på bilder på upp till 400 pixlar.