Spelling suggestions: "subject:"clusterização hierárquica"" "subject:"clusterização hierárquicas""
1 |
Characterization of implied scenarios as families of Common BehaviorMelo, Caio Batista de 31 August 2018 (has links)
Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2018. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES). / Sistemas concorrentes enfrentam uma ameaça à sua confiabilidade em comportamentos
emergentes, os quais não são incluídos na especificação, mas podem acontecer durante o
tempo de execução. Quando sistemas concorrentes são modelados a base de cenários, é
possível detectar estes comportamentos emergentes como cenários implícitos que, analogamente,
são cenários inesperados que podem acontecer devido à natureza concorrente
do sistema. Até agora, o processo de lidar com cenários implícitos pode exigir tempo
e esforço significativos do usuário, pois eles são detectados e tratados um a um. Nesta
dissertação, uma nova metodologia é proposta para lidar com vários cenários implícitos
de cada vez, encontrando comportamentos comuns entre eles. Além disso, propomos uma
nova maneira de agrupar estes comportamentos em famílias utilizando uma técnica de
agrupamento usando o algoritmo de Smith-Waterman como uma medida de similaridade.
Desta forma, permitimos a remoção de vários cenários implícitos com uma única correção,
diminuindo o tempo e o esforço necessários para alcançar maior confiabilidade do sistema.
Um total de 1798 cenários implícitos foram coletados em sete estudos de caso, dos quais
14 famílias de comportamentos comuns foram definidas. Consequentemente, apenas 14
restrições foram necessárias para resolver todos os cenários implícitos coletados coletados,
aplicando nossa abordagem. Estes resultados suportam a validade e eficácia da nossa
metodologia. / Concurrent systems face a threat to their reliability in emergent behaviors, which are not
included in the specification but can happen during runtime. When concurrent systems
are modeled in a scenario-based manner, it is possible to detect emergent behaviors as
implied scenarios (ISs) which, analogously, are unexpected scenarios that can happen due
to the concurrent nature of the system. Until now, the process of dealing with ISs can
demand significant time and effort from the user, as they are detected and dealt with in a
one by one basis. In this paper, a new methodology is proposed to deal with various ISs
at a time, by finding Common Behaviors (CBs) among them. Additionally, we propose
a novel way to group CBs into families utilizing a clustering technique using the Smith-
Waterman algorithm as a similarity measure. Thus allowing the removal of multiple
ISs with a single fix, decreasing the time and effort required to achieve higher system
reliability. A total of 1798 ISs were collected across seven case studies, from which 14
families of CBs were defined. Consequently, only 14 constraints were needed to resolve all
collected ISs, applying our approach. These results support the validity and effectiveness
of our methodology.
|
2 |
Melhorando o desempenho da técnica de clusterização hierárquica single linkage utilizando a metaheurística GRASPRibeiro Filho, Napoleão Póvoa 30 March 2016 (has links)
O problema de clusterização (agrupamento) consiste em, a partir de uma base de dados,
agrupar os elementos de modo que os mais similares fiquem no mesmo cluster (grupo),
e os elementos menos similares fiquem em clusters distintos. Há várias maneiras de se
realizar esses agrupamentos. Uma das mais populares é a hierárquica, onde é criada uma
hierarquia de relacionamentos entre os elementos. Há vários métodos de se analisar a
similaridade entre elementos no problema de clusterização. O mais utilizado entre eles é o
método single linkage, que agrupa os elementos que apresentarem menor distância entre si.
Para se aplicar a técnica em questão, uma matriz de distâncias é a entrada utilizada. Esse
processo de agrupamento gera ao final uma árvore invertida conhecida como dendrograma.
O coeficiente de correlação cofenética (ccc), obtido após a construção do dendrograma,
é utilizado para avaliar a consistência dos agrupamentos gerados e indica o quão fiel o
dendrograma está em relação aos dados originais. Dessa forma, um dendrograma apresenta
agrupamentos mais consistentes quando o ccc for o mais próximo de um (1) . O problema
de clusterização em todas as suas vertentes, inclusive a clusterização hierárquica (objeto
de estudo nesse trabalho), pertence a classe de problemas NP-Completo. Assim sendo, é
comum o uso de heurísticas para obter soluções de modo eficiente para esse problema. Com
o objetivo de gerar dendrogramas que resultem em melhores ccc, é proposto no presente
trabalho um novo algoritmo que utiliza os conceitos da metaheurística GRASP. Também
é objetivo deste trabalho implementar tal solução em computação paralela em um cluster
computacional, permitindo assim trabalhar com matrizes de dimensões maiores. Testes
foram realizados para comprovar o desempenho do algoritmo proposto, comparando os
resultados obtidos com os gerados pelo software R. / The problem of clustering (grouping) consists of, from a database, group the elements so
that more queries are in the same cluster (group) and less similar elements are different
clusters. There are several ways to accomplish these groupings. One of the most popular is
the hierarchical, where a hierarchical relationships between the elements is created. There
are several methods of analyzing the similarity between elements in the clustering problem.
The most common among them is the single linkage method, which brings together the
elements that are experiencing less apart. To apply the technique in question, distance
matrix is the input used. This grouping process generates the end an inverted tree known
as dendrogram. The cophenetic correlation coefficient (ccc), obtained after the construction
of the dendrogram is a measure used to evaluate the consistency of the clusters generated
and indicates how faithful he is in relation to the original data. Thus, a dendrogram gives
more consistent clusters when the ccc is closer to one (1). The clustering problem in all
its aspects, including hierarchical clustering (object of study in this work), belongs to
the class of NP-complete problems. Therefore, it is common to use heuristics for efficient
solutions to this problem. In order to generate dendrograms that result in better ccc, it is
proposed in this paper a new algorithm that uses the concepts of GRASP metaheuristic.
It is also objective of this work to implement such a solution in parallel computing in a
computer cluster, thus working with arrays larger. Tests were conducted to confirm the
performance of the proposed algorithm, comparing the results with those generated by
the software R.
|
Page generated in 0.0728 seconds