Dimension reduction in projective clustering (2022)
- Authors:
- Autor USP: LIMA, RAFAEL ZUOLO COPPINI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2022.tde-02092022-150552
- Subjects: APROXIMAÇÃO; MÉTODOS DE DECOMPOSIÇÃO
- Keywords: Agrupamento projetivo; Approximation; Clustering; Decomposição em valores singulares; Dimension reduction; Johnson-Lindenstrauss lemma; Lema de Johnson e Lindenstrauss; Projective clustering; Redução de dimensão; Singular value decomposition
- Agências de fomento:
- Language: Inglês
- Abstract: 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
- Imprenta:
- Data da defesa: 22.06.2022
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
LIMA, Rafael Zuolo Coppini. Dimension reduction in projective clustering. 2022. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2022. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-02092022-150552/. Acesso em: 03 jan. 2026. -
APA
Lima, R. Z. C. (2022). Dimension reduction in projective clustering (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-02092022-150552/ -
NLM
Lima RZC. Dimension reduction in projective clustering [Internet]. 2022 ;[citado 2026 jan. 03 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-02092022-150552/ -
Vancouver
Lima RZC. Dimension reduction in projective clustering [Internet]. 2022 ;[citado 2026 jan. 03 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-02092022-150552/
Informações sobre o DOI: 10.11606/D.45.2022.tde-02092022-150552 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
