Biblioteca

Seja um dos 16 apoiadores do Ludopédio e faça parte desse time! APOIAR AGORA
Dissertação

Teoria de HodgeRank aplicada aos dados históricos do Campeonato Brasileiro de Futebol

Ano

2016

Faculdade/Universidade

Instituto Politécnico, Universidade do Estado do Rio de Janeiro

Tema

Dissertação

Área de concentração

Mestrado em Modelagem Computacional

Páginas

176

Arquivos

Resumo

Este trabalho apresenta o desenvolvimento de um conjunto de métodos baseados na teoria de Hodge combinatória, chamado HodgeRank, cujo objetivo principal a criação de um ranking estatístico. Os métodos de HodgeRank são aplicáveis a conjuntos de dados incompletos e desbalanceados, características comuns dos conjuntos de dados modernos, para os quais algoritmos tradicionais de ranqueamento são geralmente ineficazes. Dado um conjunto de eleitores, um conjunto de alternativas elegíveis e um conjunto de avaliações conectando os dois, é possível utilizar técnicas de comparação em pares para tornar o conjunto de dados menos incompleto, através da construção de uma estrutura de grafo que surge naturalmente. O problema a ser resolvido pode ser tratado através da solução de um sistema linear, que lida com um fluxo nas arestas do grafo de comparação em pares. Os métodos de HodgeRank, além de providenciarem um ranking global, geram também um “certificado de confiabilidade”, ou seja, uma forma de validar o ranking através da determinação de suas inconsistências. A partir dos dados referentes a 26 anos do Campeonato Brasileiro de Futebol Série A, foram criados e analisados rankings dos 50 clubes que passaram pela Série A desde 1988. Foram obtidos rankings aceitáveis de acordo com o desempenho dos clubes no período analisado, sendo possível definir os melhores clubes.

Palavras-chave: HodgeRank. Ranking estatístico. Teoria de Hodge combinatória. Campeonato Brasileiro de Futebol.

Abstract

This work presents the development of a set of methods based on combinatorial Hodge theory, HodgeRank, whose main objective is to create a statistical ranking. Hodge- Rank methods can be applied to incomplete and imbalanced data sets that are commom characteristics of modern data sets, where traditional ranking algorithms are usually ineffective. Given a set of voters, a set of eligle alternatives and a set of ratings connecting them, it is possible to use pairwise comparison techniques to make the data set less incomplete, by endowing it with a graph structure that comes up naturally. The problem to be solved can be treated using the solution of a linear system, related to an edge ow on a pairwise comparison graph. Besides providing a global ranking, the HodgeRank methods also generate a “reliability certificate”. In other words, it provides a tool to validate the ranking and to analyse its inconsistencies. Using data from 26 years of the first division of the Brazilian Soccer Championship, rankings, of the 50 clubs that competed in the first division since 1988, were created and analyzed. Acceptable rankings were obtained according to the performance of clubs in the analyzed period, and was possible set the best clubs.

Keywords: HodgeRank. Statistical ranking. Combinatorial Hodge theory. Brazilian Soccer Championship.

Sumário

INTRODUÇÃO, 13

1 RANKING, 16
1.1 História do Ranqueamento, 16
1.1.1 Problema de Borda, 17
1.2 Aprendizado de máquina, 18
1.2.1 Learning to Rank, 19
1.2.1.1 Métodos baseados em pontos, 21
1.2.1.2 Métodos baseados em pares, 22
1.2.1.3 Métodos baseados em listas, 23
1.3 Conjuntos de dados modernos, 24
1.3.1 Pontuações cardinais, 25
1.3.2 Dados incompletos, 25
1.3.3 Dados desbalanceados, 27
1.3.4 Redes complexas, 28
1.4 Inconsistências cíclicas nos rankings, 29
1.4.1 Paradoxo de Condorcet, 30
1.4.2 Probabilidade de intransitividade, 32

2 TEORIA DOS GRAFOS, 35
2.1 Problema das pontes de Königsberg, 35
2.2 O que é um grafo?, 36
2.2.1 Matriz de adjacência, 41
2.2.2 Matriz de grau, 42
2.2.3 Matriz laplaciana, 43
2.3 Grafos ponderados, 44
2.3.1 Matriz de adjacência ponderada, 45
2.3.2 Matriz de grau ponderada, 46
2.3.3 Matriz laplaciana ponderada, 47
2.4 Incompletude e desbalanceamento do conjunto de dados, 48
2.4.1 Incompletude, 49
2.4.2 Desbalanceamento, 49

3 RANQUEAMENTO ESTAT´ıSTICO EM GRAFOS, 51
3.1 Uso da teoria de HodgeRank na literatura, 51
3.2 Definições e notação básica da teoria de HodgeRank, 53
3.2.1 Exemplo de obtenção da matriz de avaliações, 55
3.2.2 Ranking global, 56
3.2.3 Função pontuação, 60
3.2.4 Matriz de comparação em pares, 61
3.2.5 Matriz de pesos, 63
3.3 O problema de minimização, 64
3.3.1 Fluxo nas arestas de um grafo, 65
3.3.2 Gradiente combinatório, 67
3.3.3 Comparação em pares agregada, 71
3.3.4 Funções comparação, 74
3.4 Inconsistência local e global, 77
3.4.1 Fluxo triangular em um grafo, 77
3.4.2 Rotacional combinatório, 78
3.4.3 Divergente combinatório, 84

4 VISAO MATRICIAL DA DECOMPOSIÇÃO DE HODGE, 86
4.1 Construção dos subespaços das matrizes antissimétricas, 86
4.2 Decomposição matricial de Hodge, 90

5 TEORIA DE HODGE COMBINATÓRIA, 93
5.1 Complexos simpliciais, 93
5.1.1 Extensão do grafo de comparação em pares a um complexo simplicial, 97
5.1.2 Relação de ordem parcial nos complexos simpliciais, 99
5.2 Generalização dos operadores combinatórios, 103
5.2.1 Cocadeias, 103
5.2.2 Produtos internos, 104
5.2.3 Operadores de cofronteira, 105
5.2.4 Operadores de cofronteira adjuntos, 106
5.2.5 Operadores laplacianos combinatórios, 114
5.3 Teorema da decomposição de Hodge, 115
5.3.1 Interpretação dos subespaços na decomposição de Helmholtz, 121

6 ANÁLISE DA TEORIA DE HODGERANK, 123
6.1 Pseudoinversa de Moore-Penrose, 123
6.1.1 Lei da ordem reversa para matrizes pseudoinversas de Moore-Penrose, 125
6.2 Obtenção da função potencial de norma mínima, 127
6.2.1 Contagem de Borda, 129
6.3 Obtenção do fluxo rotacional, 131
6.4 Análise das inconsistências na teoria de HodgeRank, 133
6.4.1 Análise dos percentuais de inconsistência local e global, 135
6.4.2 Inconsistência local relativa, 137
6.4.3 Percentual de representatividade do ranking global, 138
6.4.4 Representação gráfica para matrizes, 138
6.5 Algoritmo para a decomposição de Helmholtz, 142

7 APLICAÇÃO DA TEORIA DE HODGERANK AOS DADOS HISTÓRICOS DO CAMPEONATO BRASILEIRO DE FUTEBOL, 145
7.1 Histórico do Campeonato Brasileiro de Futebol, 146
7.2 Descrição do problema, 148
7.2.1 Coleta dos dados e obtenção da comparação em pares agregada, 148
7.2.2 Geração dos resultados, 150 7.3 Análise dos resultados obtidos, 150
7.3.1 Análise do ranking global com todos os clubes da Série A de 1988 a 2014, 151
7.3.2 Análise do ranking com os clubes mais relevantes da Série A de 1988 a 2014, 157
7.3.3 Análise da inconsistência local relativa, 163

CONCLUSÃO, 168

REFERÊNCIAS, 171

Referência

AYRES, José Eduardo de Almeida. Teoria de HodgeRank aplicada aos dados históricos do Campeonato Brasileiro de Futebol. 2016. 176 f. Dissertação (Mestrado em Modelagem Computacional) - Instituto Politécnico, Universidade do Estado do Rio de Janeiro, Nova Friburgo, 2016.