Improving hyperplane based density clustering solutions with applications in image processing
Date
2019-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
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.
Description
Thesis (MCom)--Stellenbosch University, 2019.
Keywords
Cluster analysis, Image segmentation, Cluster analysis, Low density separation, Mean shift, Spatial analysis (Statistics), Image processing -- Statistical methods, UCTD