ESTGV - DMAT - Teses de doutoramento (após aprovadas pelo júri)
Permanent URI for this collection
Browse
Recent Submissions
- Contribution to the knowledge of hierarchical clustering algorithms and consensus clustering. Studies applied to personal recognition by hands biometricsPublication . Sousa, Lúcia; Gama, João; Faceli, KattiIn exploratory data analysis, hierarchical clustering algorithms with its features can provide different clusterings when applied to the same data set. In the presence of several clusterings, each one identifying a specific data structure, consensus clustering provide a contribution to deal with this issue. The work reported here is composed by two parts: In the first part, we intend to explore the profile of base hierarchical clusterings, according to their variabilities, to obtain the consensus clustering. As a first result of our researches, we identified the consensus clustering technique as having better performance than the others, depending on the characteristics of hierarchical clusterings used as base. This result allows us to identify a sufficient condition for the existence of consensus clustering, as well as define a new strategy to evaluate the consensus clustering. It also leads to study a new property of hierarchical clustering algorithms. In the second part, we explore a real-world application. In a first analysis, we use data sets derived by biometrics extracted from hands for personal recognition. We show that the hierarchical clusterings obtained by SEP/COP algorithms, can provide results with great accuracy when applied to these data sets. Furthermore, we found an increased 100% of recognition rate, comparing to the ones found in literature. In a second analysis, we consider the application of consensus clustering techniques to the problem of the identification of people's parenting by the hands biometrics. The results obtained indicate that hand’s photography has information that allows the identification of people’s family members but, according to our data, we didn't have very positive results (we observed a probability of 95% of the parents, and 94% of a sibling to be in the half of the more similar hands) that we believe it’s due to the poor quality of the photographs we used. However, the results indicate that the technique has potential, and if the collection of photographs is made using a scanner with fixed pins, the hand may be an interesting alternative for the identification of parenting of missing children when it is applied the consensus clustering.
- Invólucros Reflectivos e OrtogonaisPublication . da Costa e Sousa, Maria de Lurdes; Adámek, Jirí; Sobral, ManuelaUm dos mais importantes e frutuosos conceitos em Teoria das Categorias é o de subcategoria reflectiva. Por um lado, toda a subcategoria plena de uma categoria X que seja reflectiva partilha muitas das propriedades mais significativas de X (tais como existência e construção de limites e colimites), por outro lado, é conhecido um considerável número de boas condições suficientes para que haja reflectividade. Para categorias plenas A de uma categoria X que não são reflectivas interessa determinar uma subcategoria plena de X que seja a menor de entre as que são reflectivas e contêm A, chamada invólucro reflectivo de A. Este é o tema central da presente dissertação. Duas questões se levantam: (1) Quando é que A tem um invólucro reflectivo? (2) Como pode ser construído o invólucro reflectivo de A, se ele existir? Para (2), um caminho possível é formar o invólucro para limites de A, i.e., a menor subcategoria plena de X fechada para limites e que contém A. Se este invólucro é reflectivo, ele é um invólucro reflectivo de A, mas a questão de determinar quando isto acontece tem-se revelado muito difícil. Portanto, nesta tese, optei por uma abordagem diferente baseada no conceito de ortogonalidade. Recordemos que um objecto A se diz ortogonal a um morfismo f:X-->Y se a aplicação hom(A,f):hom(Y,A--> hom(X,A) é uma bijecção. Para cada subcategoria plena A de uma categoria X, denotemos por Ort(A) a classe de todos os morfismos f da categoria X ortogonais a todos os objectos de A. É fácil concluir que se A é uma subcategoria reflectiva de X, então A pode ser reconstruída a partir de Ort(A) do seguinte modo: A é constituída por precisamente todos os objectos ortogonais a todos os morfismos em Ort(A). Geralmente, para uma subcategoria plena A, denotamos por O(A) o invólucro ortogonal de A, i.e., a subcategoria plena de todos os objectos ortogonais a todos os Ort A )-morfismos. Analogamente ao que acontece para o fecho para limites, quando a subcategoria O(A) é reflectiva, então ela é o invólucro reflectivo de A. Por conseguinte, o invólucro ortogonal é também um bom candidato a ser o invólucro reflectivo. Na verdade, muitos dos invólucros reflectivos de subcategorias não reflectivas ``do dia-a-dia" coincidem com o fecho para limites e, consequentemente, coincidem também com os respectivos invólucros ortogonais (visto que toda a subcategoria plena reflectiva é ortogonal). Contudo, o invólucro ortogonal pode ser simultaneamente reflectivo e diferente do fecho para limites. Por outro lado, é de salientar que para toda a categoria topológica com fibras pequenas sobre Set, o invólucro reflectivo de uma subcategoria, caso exista, coincide com o invólucro ortogonal, mas não necessariamente com o fecho para limites. Portanto, o invólucro ortogonal pode constituir uma melhor abordagem do invólucro reflectivo do que o fecho para limites. Assim, o conceito de ortogonalidade tem um lugar central nesta tese. A noção de ortogonalidade no sentido usado ao longo do presente estudo aparece já na literatura dos anos sessenta. Em 1972, D. Pumplun observou que esta noção determina uma correspondência de Galois que induz um ``operador de invólucro" que faz corresponder a cada subcategoria A de uma categoria X uma subcategoria - o invólucro ortogonal de A- que é uma boa aproximação do invólucro (mono)reflectivo de A em X e que tem grande parte das propriedades do invólucro (mono)reflectivo, mesmo se este não existir. Este conceito de ortogonalidade foi clarificado por P. J. Freyd e G. M. Kelly (1972) que apresentaram uma definição de ortogonalidade entre um morfismo e um objecto de uma dada categoria. Desde então até ao presente, o estudo desta noção, bem como o da sua relação com o conceito de reflectividade, tem-se desenvolvido. Nomeadamente, o chamado ``Problema da Subcategoria Ortogonal", ou seja o problema de quando é que uma subcategoria ortogonal é reflectiva, tem merecido a atenção de vários matemáticos. A nossa abordagem, em contraste com a de outros autores, parte de uma dada subcategoria plena ao invés de partir de uma dada classe de morfismos. Para além do `` Problema do Invólucro Reflectivo", investigamos também a relação deste com outros problemas tais como, por exemplo, a existência e caracterização do invólucro sólido de uma categoria concreta (Capítulo IV). Finalmente, a investigação feita sobre reflectividade e ortogonalidade conduzir-nos-á ao estudo de uma correspondente generalização sobre multi-reflectividade e multiortogonalidade (Capítulos V e VI).
- Escolha e ordenação com informação ordinal: extensão à decisão em grupo e à negociaçãoPublication . Paula, Sarabando; Dias, LuísOs modelos matemáticos utilizados no apoio à decisão são, regra geral, caracterizados por múltiplos parâmetros. De entre as muitas aproximações concebidas com o objectivo de ordenar um conjunto de alternativas ou com o objectivo de escolher a(s) melhor(es), tendo em conta múltiplos critérios, focamo-nos na Teoria de Valor Multicritério. Uma situação de informação completa ocorre quando os decisores conseguem indicar um valor preciso para cada um dos parâmetros do modelo utilizado. Contudo, por diversas razões, surgem frequentemente dificuldades em obter valores precisos para todos os parâmetros. Em alternativa os decisores podem fornecer aquilo a que chamamos de informação incompleta, que se caracteriza por não conduzir a uma combinação de valores precisos para todos os parâmetros do modelo. No contexto da agregação multicritério aditiva, estudamos problemas com informação ordinal, nomeadamente considerando uma ordenação dos pesos dos critérios, uma ordenação do valor de cada alternativa em cada critério e uma ordenação da diferença de valor entre alternativas consecutivas em cada critério. O principal objectivo deste trabalho é apresentar e comparar métodos para ajudar os decisores, mesmo que estes optem por fornecer informação ordinal sobre as suas preferências. Propomos duas novas regras para lidar com informação incompleta relativamente ao valor de cada alternativa em cada critério e estudamos até que ponto estas regras conduzem a bons resultados. Estas regras são testadas tanto no caso da decisão individual como no caso da negociação e da decisão em grupo. Sugerimos ainda três novas aproximações, para o caso da negociação, e uma nova aproximação, para o caso da decisão em grupo, para que um mediador, ou um facilitador, possa sugerir uma ou mais alternativas. Este trabalho pode ser dividido em duas partes. Em ambas as partes utilizamos simulação Monte Carlo. Numa primeira parte, estudamos quão boas são as regras propostas quando existe informação ordinal, em comparação com uma situação ideal na qual todos os parâmetros do modelo são conhecidos. Esta parte do trabalho visa conhecer melhor a forma como as diferentes regras e fórmulas se comparam, bem como fornecer algumas pistas sobre a melhor forma de as utilizar. O propósito deste tipo de estratégias é simplificar o problema em termos do número de alternativas, com o objectivo de as estudar em mais detalhe, ou com o objectivo de eliciar mais informação. As simulações realizadas mostram que as regras propostas conduzem a bons resultados, pelo que será de recomendar o uso de informação ordinal para identificar as alternativas mais promissoras, sempre que se anteveja ser difícil ou moroso usar os processos tradicionais para eliciar valores precisos para todos os parâmetros. Numa segunda parte o objectivo não é comparar regras, mas sim ver como diferentes aproximações podem ser utilizadas para sugerir alternativas. No caso da negociação sugerimos três aproximações. Defendemos que não existe nenhuma aproximação que seja claramente melhor do que as restantes e todas as aproximações têm forças particulares que as tornam adequadas para algumas situações. Sugerimos uma integração das aproximações, que deve ser preferencialmente implementada através de um processo interactivo. Na aproximação apresentada para o caso da decisão em grupo, o objectivo é aproximar o volume do subconjunto do espaço dos parâmetros no qual cada alternativa é a melhor, ou não perde por uma diferença significativa, bem como determinar aproximadamente as alternativas que cada alternativa domina. A aproximação apresentada pode ser facilmente utilizada, e apesar de não fornecer resultados precisos, pode ser bastante útil para recomendar um subconjunto de alternativas aos decisores.
- Avaliação de projectos de investigação e desenvolvimento na área das telecomunicaçõesPublication . Fialho, JoanaUma correta avaliação de projetos de investigação e desenvolvimento (I&D) permite que as empresas possam selecionar e/ou priorizar os projetos que melhor satisfaçam os seus objetivos. Para além disso, muitas empresas deparam-se com limitações de recursos, especialmente os humanos. Uma ferramenta que ajude os gestores a encontrarem a melhor estratégia para alocar os recursos é muito importante para a conclusão dos projetos de forma eficiente e sem desperdícios. Este trabalho apresenta duas ferramentas que ajudam a avaliar projetos de I&D, tendo como base a estrutura e política de uma empresa específica: a PT Inovação. A avaliação deste tipo de projetos (e outros) depende, também, dessa estrutura e política, pois os pressupostos admitidos por umas empresas podem não o ser noutras. De acordo, então, com a empresa, construiu-se uma primeira abordagem de avaliação baseada em múltiplos critérios, dispostos numa estrutura hierárquica: abordagem hierárquica. Seguidamente, outra abordagem foi construída, tendo em conta apenas o critério financeiro e baseada na teoria das opções reais: abordagem estocástica. Note-se que a informação necessária para a utilização da abordagem hierárquica é mais fácil de obter do que a requerida pela abordagem estocástica. Os projetos de I&D da PT Inovação podem ser muito diferentes entre si e, em geral, são desagregados em ações, cuja estrutura e objetivos podem ser muito específicos. Devido a esta variedade, os projetos e ações são diferenciados por tipos. Esta diferenciação leva a que, na abordagem hierárquica, os critérios tenham diferentes pesos, mediante o tipo de projeto ou o tipo de ação que se está a considerar. O processo de avaliação desta abordagem baseia-se no AHP (analytic hierarchy process), sendo que algumas das suas limitações tiveram que ser ultrapassadas, nomeadamente a dificuldade em estabelecer algumas comparações, o grande número de comparações que podem ser requeridas pelo método, e o tratamento de critérios que utilizem valores financeiros. O resultado da abordagem hierárquica permite priorizar e/ou selecionar projetos ou ações. São ainda sugeridas formas de, perante o resultado dessa avaliação, afetar os recursos disponíveis pelas diferentes ações consideradas no processo de avaliação. A abordagem estocástica parte do pressuposto inicial que as ações são compostas por um conjunto de tarefas (parcelas) homogéneas. Essas tarefas são avaliadas, ao mesmo tempo que é definida a melhor estratégia para a sua execução: mediante os níveis de recursos disponíveis, são definidas regras que ajudam a decidir sobre o nível de recursos a utilizar em cada instante, de acordo com a maximização de um valor financeiro que caracteriza a tarefa. Considera-se que o tempo de execução de uma tarefa e os cash flows esperados têm comportamento estocástico. Os custos são fixos, por unidade de tempo e, tal como o tempo de execução, dependem do nível de recursos utilizado. O processo de avaliação baseia-se na teoria das opções reais e no processo de simulação least squares Monte Carlo (LSM), com algumas adaptações, já que se considera o tempo de execução estocástico, e não determinista.
- Meta-heurísticas de optimização por colónias de formigas em problemas periódicos de estabelecimento de rotasPublication . Matos, Ana Cristina Bico Rodrigues; Oliveira, Rui Manuel Moura de CarvalhoNesta tese são apresentados procedimentos inovadores na classe das meta-heurísticas de optimização por colónias de formigas e técnicas de pós-optimização que se revelaram promissores na resolução de problemas periódicos de estabelecimento de rotas de grandes dimensões. Um sistema de recolha de resíduos sólidos urbanos de um concelho do centro de Portugal é usado como caso de estudo, sendo objectivo dos modelos desenvolvidos a optimização dos circuitos dos veículos de recolha. Os problemas periódicos de estabelecimento de rotas (PVRP) constituem uma extensão do problema clássico de estabelecimento de rotas no qual os clientes têm que ser visitados um número diferenciado de vezes num dado horizonte temporal. Deste modo, é necessário elaborar um planeamento, definindo a calendarização das visitas aos clientes, e desenhar o conjunto de rotas para o horizonte temporal. São comparadas duas abordagens para a resolução deste tipo de problemas: uma formulação em que a calendarização e o estabelecimento de rotas são abordados em duas fases distintas e sequenciais, e outra formulação em que estas duas vertentes do problema são abordadas em simultâneo. Deste modo, são desenvolvidos dois modelos distintos que incorporam elementos inovadores e cujo desempenho se compara favoravelmente com outros modelos da mesma classe anteriormente desenvolvidos e publicados.
- Cálculo fraccional em escalas temporaisPublication . Bastos, Nuno; Torres, Delfim Fernando MaradoIntroduzimos um cálculo das variações fraccional nas escalas temporais ℤ e (hℤ)!. Estabelecemos a primeira e a segunda condição necessária de optimalidade. São dados alguns exemplos numéricos que ilustram o uso quer da nova condição de Euler–Lagrange quer da nova condição do tipo de Legendre. Introduzimos também novas definições de derivada fraccional e de integral fraccional numa escala temporal com recurso à transformada inversa generalizada de Laplace.
- Sobre problemas inversos na teoria dos polinómios ortogonaisPublication . Jesus, Márcio; Petronilho, JoséA presente dissertação insere-se no âmbito da Teoria dos Polinómios Ortogonais e das Funções Especiais, nos domínios da Análise e da Teoria da Aproximação, bem como das suas aplicações, incluindo o estudo de certos operadores de Jacobi, na descrição dos correspondentes espectros e espectros essenciais.