Improving hyperplane based density clustering solutions with applications in image processing

Kenyon, Jacob Bradley (2019-04)

Thesis (MCom)--Stellenbosch University, 2019.

Thesis

ENGLISH SUMMARY : Minimum Density Hyperplane (MDH) clustering is a recently proposed method that seeks the location of an optimal low-density separator by directly minimising the integral of the empirical density function on the separating surface. This approach learns underlying clusters within the data in an efficient and scalable way using projection pursuit. The main limitation of MDH is that it defines clusters using a linear hyperplane. In recent research, MDH was applied to data which was non-linearly embedded in a high-dimensional feature space using Kernel Principal Component Analysis. While this method has shown to be an effective approach that extends the linear plane to a non-linear form, it does not scale well. A procedure is needed that can improve the hyperplane solution in an efficient way. We pose a novel approach to improve upon MDH by reassigning observations in a neighbourhood around a hyperplane solution using a gradient ascent procedure, Mean Shift. While Mean Shift is shown to provide promising results, the computation required to reassign objects becomes prohibitive as the size of the dataset increases. To reduce computation, a single step gradient heuristic is proposed whereby observations are reassigned based on the initial gradient evaluated at each point in relation to the hyperplane. This study critically reviews the validity of these approaches through applications with simulated and real-world datasets, with a focus on applications in image segmentation. We show that these approaches have the potential to improve hyperplane solutions.

AFRIKAANSE OPSOMMING : Minimum Digtheid Hipervlak (MDH) tros-vorming is 'n onlangs voorgestelde metode waartydens die optimale ligging van ?n lae digtheids-hipervlak gevind word deur die integraal van die empiriese dightheidsfunksie oor die hipervlak oppervlak te minimimeer. Hierdie benadering maak gebruik van projeksienajaging om op 'n doeltreffende wyse onderliggende trosse te identifiseer. Die primêre beperking van MDH is dat trosse deur 'n liniêre hipervlak geskei word. In onlangse navorsing is nie-liniêre of kernfunksie gebaseerde hoofkomponentanalise gebruik tydens die toepassing van MDH. Terwyl dit bevind is dat hierdie metode op doeltreffende wyse die liniêre hipervlak uitbrei na 'n nie-liniêre funksie, kan dit nie effektief toegepas word op baie groot datastelle nie. Daar bestaan dus ruimte vir die ontwikkeling van ?n metode om die hipervlakoplossing op 'n doeltreende wyse te verbeter. Ons stel derhalwe 'n nuwe benadering voor wat die hertoewysing van datapunte rondom die hipervlak behels, en wat gebruik maak van die 'mean shift gradient ascent' prosedure. Terwyl ons aantoon dat die implementering van die 'mean shift' algoritme belowende resultate lewer, raak die hertoewysing van datapunte te berekenings-intensief namate die grootte van die datastel toeneem. Ten einde die nodige berekeninge te verminder, word 'n meer heuristiese metode voorgestel waarin slegs 'n enkele stap benodig word. Hiervolgens word waarnemings hertoegewys op grond van die aanvanklike gradiënt van elke punt in verhouding met die hipervlak. In hierdie studie word die geldigheid van bogaande benaderings op datastelle in beeldsegmentering, en op gesimuleerde data, krities beoordeel. Ons toon aan dat die benaderings wel potensiaal het om hipervlak oplossing te verbeter.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/106178
This item appears in the following collections: