Experiments with Clustering as a Software Remodularization Method

Nicolas Anquetil and Timothy C. LethbridgeUniversity of Ottawa, Canada

WCRE 1999: 235-255

Gustavo Jansen de Souza SantosHudson Silva Borges

Universidade Federal de Minas Gerais

Roteiro

Introdução Clusterização Entidades e suas descrições Outras questões em clusterização Avaliação Experimento Conclusão

2

Introdução

Valorização do Software Manutenção Engenharia reversa Clusterização Complexo Horizonte de possibilidades Comparação entre diferentes métodos Foco em remodularização

3

Clusterização

Atividades da engenharia reversa:

Obter informações Composição do sistema Grupos independentes

---------------------------------------- = Clusterização

4

Clusterização

Requisitos para clusterização:

Descrição das Entidades Acoplamento das Entidades Algoritmo de Clusterização

5

Clusterização

Questões:

Como descrever as fontes?

Ex: Com caracteres.

6

Clusterização

Questões: O que é um cluster coeso?

7

Clusterização

Questões:

Qual algoritmo utilizar?

Depende do objetivo!

8

Clusterização

Entidades e Descrições

O que são entidades: Arquivos Rotinas Classes Processos

Descrição através de features Formal Não formal

9

Clusterização

Descrição Formal

São informações que tem impacto direto no comportamento do sistema;

Escolhas óbvias. Testados: Tipos, Variáveis, Rotinas, Arquivos,

Macros. Limitação da taxonomia e redundância.

10

Clusterização

Descrição Não Formal

São informações que não tem influência direta no comportamento do sistema;

Testados: Identificadores e Comentários; Muitos problemas em sistemas legados; Quando relevantes:

Menor redundância, facilmente extraída, mais

informações, mais próximo do entendimento humano.

11

Metricas de Similaridade

Tão importante quanto o algoritmo;

Quanto mais similar a descrição de duas entidades, maior o acoplamento entre elas.

Meio de agrupá-los: Coeficiente de associação; Coeficiente de distância; Coeficiencia de correlação; Coeficiente probabilístico

12

Algoritmos de Clusterização

Algoritmos aglomerativos hierárquicos; São não supervisionados;

13

Algoritmos de Clusterização

Algoritmos aglomerativos hierárquicos; Ex: Single, Complete, Weighted average e

Unweighted average linkage;

14

Algoritmos de Clusterização

Algoritmos aglomerativos hierárquicos geram uma hierarquia de clusters, onde é necessário cortá-la;

15

Avaliação

Questões Representativo Faz sentido Adaptáveis Geral

Critérios de Qualidade Redundância entre features Expert Design Tamanho

16

Redundância entre Features

Duas features geram resultados similares Quantos pares de entidades no mesmo cluster tem em

comum

Não é um teste perfeito Cada feature pode ter um conjunto de features similares Resultado depende da função de similaridade

Execução para métricas diferentes

17

Critério do Expert

Faz sentido para os projetistas

Critério Ideal Grupo de experts avaliando os clusters Impraticável

Uso da distribuição de pastas do sistema Visão inicial da arquitetura

Métricas Precisão Revocação

18

Critério de Design

Maior interesse dentre os critérios Manutenibilidade

Métricas Coesão

Similaridade média entre entidades de mesmo cluster Acoplamento

Similaridade média entre entidades de clusters diferentes

Métrica de similaridade parecida com a usada no algoritmo

19

Critério de Tamanho

Tamanhos similares Evitar cluster unitários ou muito grandes

Inerente à propriedade do sistema Também depende da métrica de similaridade e do algoritmo

de clusterização

Métricas Número de clusters unitários Número de entidades no maior cluster Número de entidades restantes (clusters intermediários)

20

Critério de Tamanho

Comparação com vários cortes na árvore hierárquica

21

Experimento

22

Experimento

23

Entidades são arquivos, pastas são subsistemas

Coesão e acoplamento são calculadas com features formais

Comparação com abordagem hill climbing de Bunch [7]

Redundância entre Features

24

Features formais têm mais redundância entre si do que features não-formais Exceção: “all” e “ident”

Métrica de similaridade influencia no resultado

Descrições das Entidades

25

Propriedades do vetor de descrição das entidades

Influência no resultado a partir de vetores vazios Tendência a criar um cluster com tais entidades

Descrições das Entidades

26

Métricas de Similaridade

27

Diferentes métricas para vários cortes na árvore

Métricas que não utilizam dimensões nulas tem melhores resultados

Jaccard e Sorensen-Dice dão melhores resultados

Métricas de Similaridade

28

Algoritmos de Clusterização

29

Comporta-se como esperado

Graduação de Complete Linkage a Simple Linkage em relação aos resultados Complete Linkage resulta clusters mais coesos Single Linkage resulta clusters menos acoplados Unweighted Linkage dá melhor combinação

Algoritmos de Clusterização

30

Conclusões

31

Estudo de direfentes fatores que influenciam o resultado de clusterização Como entidades são descritas Como calcular acoplamento entre entidades Qual variante de algoritmo utilizar Critérios de avaliação

Algoritmos hierárquicos se comportam tão bem quanto as outras abordagens

Vantagem de recuperar partição de qualquer nível da árvore Níveis de abstração

Muito Obrigado

32