Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2022.tde-02092022-150552
Document
Author
Full name
Rafael Zuolo Coppini Lima
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2022
Supervisor
Committee
Kohayakawa, Yoshiharu (President)
Laber, Eduardo Sany
Pait, Felipe Miguel
Title in English
Dimension reduction in projective clustering
Keywords in English
Approximation
Clustering
Dimension reduction
Johnson-Lindenstrauss lemma
Projective clustering
Singular value decomposition
Abstract in English
The high dimensionality of data may be a barrier to algorithmic efficiency (Nelson, 2020), mainly because of the well known curse of dimensionality which imposes exponential time and/or memory complexity for algorithms, such as the nearest neighbour problem (Har-Peled, Indyk, and Motwani, 2012). It is natural then to search for ways to break the curse by relaxing the problem with approximate versions and by finding good ways to reduce the dimension of data. Our objective is to write a dissertation about a dimension reduction scheme for clustering under 2 2 metric, with a focus on an approximation scheme for a particular case of this problem, called projective clustering. The dimension reduction is achieved by combining randomized techniques, such as the Johnson and Lindenstrauss Lemma, and deterministic techniques, such as the singular value decomposition. The result is an (1 + )-approximation for projective clustering that is polynomial in the number of data points and the dimension of the space. This dissertation will have as main references four papers: Sarlós, 2006, Feldman, Schmidt, and Sohler, 2020, Pratap and Sen, 2018 and Deshpande, Rademacher, Vempala, and Wang, 2006. The results presented in the dissertation will be either the original or modified versions that incorporate current improvements.
Title in Portuguese
Redução de dimensão para agrupamento projetivo
Keywords in Portuguese
Agrupamento projetivo
Aproximação
Clustering
Decomposição em valores singulares
Lema de Johnson e Lindenstrauss
Redução de dimensão
Abstract in Portuguese
A dimensão dos dados pode ser uma barreira para a eficiência de algoritmos (Nelson, 2020) principal- mente em razão da chamada maldição da dimensão, que impõe dependências exponenciais na dimensão para a complexidade de tempo e/ou espaço dos algoritmos para alguns problemas. Este é o caso, por exemplo, do problema do vizinho mais próximo (Har-Peled, Indyk e Motwani, 2012). É natural então estudar aproximações de soluções dos problemas e formas de reduzir a dimensão das instâncias para tentar quebrar essa maldição. Nosso objetivo é escrever uma dissertação sobre um esquema de redução de dimensão para clustering (agrupamento) sob a métrica 2 2, pondo foco em um esquema de aproximação para um caso particular do problema anterior, chamado projective clustering (agrupamento projetivo). A redução de dimensão é feita combinando técnicas aleatorizadas, como o Lema de Johnson e Lindenstrauss, e determinÃsticas, como a decomposição em valores singulares. Obtém-se uma (1 + )-aproximação para o problema do agrupamento projetivo, polinomial no número de pontos e na dimensão. Esta dissertação terá como referências principais quatro artigos: Sarlós, 2006, Feldman, Schmidt e Sohler, 2020, Pratap e Sen, 2018 e Deshpande, Rade- macher, Vempala e Wang, 2006. Os resultados apresentados na dissertação serão ou os originais ou versões modificadas, incorporando aprimoramentos recentes.
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2022-09-02