Aprendizado não-supervisionado indica quais senadores votam afim

Neste artigo, detalho como escrever um programa capaz de agrupar os senadores de acordo com seus votos. Desde como encontrar as informações, passando por trechos de código, recorrendo à matemática e chegando enfim às "panelinhas" do Senado.

Introdução

O cenário legislativo brasileiro é complexo e, por vezes, mutante. Ter uma ideia de como nossos representantes se comportam costuma ser um desafio até mesmo aos mais informados no assunto. Ao cidadão comum, a informação nem sempre chega, chega de forma indigerível, ou já mastigada (demais).

Por sorte, a legislação prevê transparência nas esferas públicas e, através de portais para Dados Abertos como o do Senado Federal, podem ser obtidas informações valiosas sobre o exercício parlamentar. O acesso à informação, porém, é mais um direito que vem sendo penosamente estendido no Brasil – não fique muito animado.

Decidi realizar essa atividade paralelamente ao estágio na Infosimples para extrair conclusões imparciais e significativas das votações. Valeu o esforço, pois serviu para colocar sob teste alguns dos conceitos vistos no curso de Introdução à Inteligência Artificial do Udacity (e também serviu para atrair leitores curiosos como você! Deixe seu comentário depois).

Dentro da área de aprendizado de máquina (ramo da IA), uma das abordagens possíveis é o aprendizado não-supervisionado. Ao contrário do supervisionado, o programa aqui não conhece regras ou padrões que o ajudem a tomar decisões com os dados de entrada.

Tampouco recebe uma avaliação sobre suas decisões passadas terem sido boas ou ruins, como é o caso do aprendizado por reforço. É quase como entregar as planilhas do escritório ao novo estagiário, sem dizer o que ele deve fazer com elas, nem responder se ele está fazendo certo. O pior é que funciona.

O clustering é uma forma bem conhecida de aprendizado não-supervisionado, e visa a separar objetos em conjuntos que os caracterizem como os mais similares entre si. Um algoritmo capaz de fazer isso e que estudei no curso de IA é o k-means, que será explicado mais adiante.

Dados das votações

Como mencionado no começo deste artigo, o Senado brasileiro fornece dados sobre as votações através de um portal de Dados Abertos. O tipo de conjunto de dados que levamos em conta para a análise aqui proposta é o de Votações nominais.

Para a atividade realizada, escolhi os dados referentes às votações de 2013 (clique para baixar), mas o programa deve se adequar a qualquer uma das votações. O formato em que vêm os dados é o XML, um dos recomendados pela filosofia de dados abertos (especificação aberta, não-proprietário e estruturado) – ainda bem, pois se fosse PDF eu teria que estender esse artigo a uma saga.

Embora não traga uma descrição detalhada das propostas sob votação (em geral, apenas um pequeno parágrafo), o XML baixado tem todas as votações do ano e quem participou de cada uma. A grande inconveniência é que as votações no Senado Federal podem ser secretas, e nestes casos não há como saber se o voto de um senador foi pela aprovação ou não.

Foram levados em consideração, para a análise descrita a seguir, os dados referentes às votações não-secretas. No caso de 2013, são apenas 76 entre as 180 realizadas. (Ah, se descobríssemos as outras 104...)

Tratamento dos dados

Como pode ser constatado ao abrir qualquer um dos arquivos XML da lista, há muita informação desnecessária para o nosso objetivo (perdoe-me se fiz seu navegador travar... a menos que tenha sido o IE, aí foi inevitável e merecido).

Usando um ambiente pré-configurado para Ruby na máquina, podemos simplificar os dados ao essencial e aproveitar para deixá-los num formato que nos convier. A biblioteca de Ruby que utilizei para o parsing do XML é o Nokogiri. De fácil instalação e uso, é capaz de procurar em documentos através de seletores CSS3 (HTML) e XPath (necessários em nosso caso).

A estrutura do XML em questão, deixando detalhes de lado, é conforme o esquema:

O node <VotoParlamentar> traz o nome, um código (identificador único) e o voto do senador em questão. O node <Votacao> traz valores que utilizei para distinguir as votações entre si, e também o valor <Secreta> que, quando igual a “S”, indica que devo soltar um suspiro (figurativamente) e ignorar essa votação.

votacoes_abertas = []
doc.xpath("//Secreta").each do |node|
  votacoes_abertas << node.parent if node.text.match(/S/).nil?
end

Visando a deixar registrado de forma simples os votos, montei duas Hashes (coleções do tipo chave-valor em Ruby). A primeira traz todos os códigos de senadores como chaves – cada uma apontando para uma nova Hash (representando o senador) cujas chaves são “nome” e os identificadores das votações em que esse senador votou. Exemplo:

A segunda é o inverso: traz os identificadores das votações como chaves, e cada uma aponta para uma nova Hash (representando a votação) cujas chaves são os códigos dos senadores. Acabou não sendo necessário utilizar esta última, mas não deixa de ser interessante mantê-la disponível.

senadores, votacoes = {}, {}
votacoes_abertas.each do |va|
  votacao = {}
  id_va = identificador(va) # método que gera chave única à votação

  va.xpath("Votos").children.each do |vp| # VotoParlamentar
    voto = aprova?(vp.xpath("Voto")) # método que retorna boolean
    cp = vp.xpath("CodigoParlamentar").text
    if senadores[cp].nil?
      senadores[cp] = {nome: vp.xpath("NomeParlamentar").text}
    end
    senadores[cp][id_va] = voto
    
    votacao[cp] = voto
  end
  votacoes[id_va] = votacao
end

Seguiu-se então a escrita em arquivos JSON (aqui entra a questão da preferência, e JSON é previsível para quem usa Ruby) dessas Hashes, para termos os dados prontos sempre que quiséssemos voltar a manuseá-los.

K-means

O algoritmo, embora não seja adequado para muitos casos de clustering, é de fácil implementação e muito popular. Um exemplo de seu funcionamento encontra-se nas figuras a seguir. Seu nome vem do fato de que divide em k grupos os objetos recebidos, e para isso utiliza médias (means) das propriedades desses objetos.


Exemplo de k-means com k = 2. Começamos em (a) com objetos não-classificados (pontos verdes). Em (b) sorteamos dois pontos quaisquer no plano ("x" e "x"). Verificamos (c) qual parte dos pontos verdes estava mais próxima do vermelho ou do azul e lhes atribuímos essa nova cor. Agora (d) calculamos o centroide (média das coordenadas) de cada um dos dois conjuntos e movemos para lá o "x" de cada cor. Verificamos (e) que com esses novos centroides, parte dos pontos azuis e vermelhos trocou de conjunto, devido às novas proximidades. Em (f) recalculamos os centroides, e percebemos que nenhum ponto trocará de conjunto com os novos locais dos "x" (portanto, não há necessidade de calcular novos centroides, e nada mais mudará). O algoritmo convergiu :D

Diferentemente do exemplo acima, em que todo ponto tem duas coordenadas no plano, nossa proposta de agrupar senadores de acordo com seus votos traz na bagagem dois problemas:

  1. O número de dimensões é bem maior (uma para cada votação, chegando a 76). Isso torna as iterações mais lentas (e praticamente impossíveis de serem representadas como nos quadros acima).
  2. Nem todo (ou, me arrisco a dizer, nenhum) senador disse "sim/não" em todas as votações, deixando muitas "coordenadas sem valor". Isso atrapalha o conceito de distância, como será visto a seguir.

Lembra do estagiário sem instruções? Bem, acho que exagerei um pouco, pois o k-means vai precisar de alguma orientação básica pra funcionar bem (nada que envolva regras de negócio). Até consigo imaginar um genérico que não precisaria das especificações listadas abaixo, mas essa é uma outra história, e terá de ser contada em outra ocasião.

Distância

Um requisito básico do k-means é a existência de uma função que estime a distância entre quaisquer dois objetos que desejamos separar em grupos. O recomendado é utilizar uma distância euclidiana (no velho molde  \(d^2 = (p_1 - q_1)^2 + (p_2 - q_2)^2 +{ }...{ }+ (p_n - q_n)^2\), onde p e q são dois pontos com dimensões), mas isso não era possível aqui. Para o caso dos senadores e seus votos, a fórmula que escrevi remete ao Laplace Smoothing visto no curso de IA do Udacity.

\(prob = { sim + 1 \over com + 2 }\)

Onde prob estima a probabilidade de que os dois senadores pertençam ao mesmo conjunto, dada a similaridade (sim) de votos e a quantidade de votações em que ambos participaram (com).

O parâmetro com pode ser facilmente obtido ao listar as chaves (votações) comuns às Hashes dos senadores, enquanto o parâmetro sim cresce (+1) à medida em que os votos comuns são iguais. Portanto, a probabilidade é sempre maior que zero e menor que um. Caso não haja votações em comum entre os dois senadores, a probabilidade resulta em 0.5 (chances iguais de pertencerem ou não ao mesmo conjunto).

Desejando que a distância ficasse entre zero e um, bastou utilizar

\(dist = 1 - prob\)

Vale lembrar que, mesmo com uma fórmula indiscutível, o k-means não pode garantir a melhor solução global (apenas local). No entanto, (spoiler) os resultados finais são satisfatórios.

Centroide

Outro requisito do k-means é que seja possível calcular o centro dos conjuntos (ou centroides), cujas coordenadas são a média entre todos os objetos dentro do cluster. Para tal, em vez de manter os valores true/false nas votações, decidi trocá-los, respectivamente, por 1.0 e 0.0 (com um método curtinho no Ruby responsável por isso).

Sendo assim, cada coordenada do centroide será a porcentagem de votos positivos numa certa votação. Por exemplo, para uma votação em que 5 senadores do conjunto votaram SIM e 3 senadores do conjunto votaram NÃO, o valor dessa coordenada nesse centroide será de \(5 \over 5+3\), ou 0.625.

Algoritmo

A última restrição a mencionar é que o k-means exige que escolhamos um valor k, o número de conjuntos em que os objetos devem ser distribuídos (muita gente envolvida com aprendizado de máquina não gosta disso sad). Iniciamos considerando o caso k = 2, ou seja, tentando dividir o Senado em dois.

O algoritmo (por completo, finalmente) é o seguinte: primeiro, escolhemos dois (devido ao k) pontos aleatórios, um para cada conjunto. Aqui, bastou criar um fator x aleatório, tal que \(0 < x < 1\), para cada uma das votações. Esses pontos ficam sendo os centroides iniciais (se por acaso estiverem nos extremos da direita e da esquerda, é pura coincidência terminológica :P).

Em seguida, realizamos uma iteração: para cada um dos senadores, calculamos sua distância ao centroide de cada conjunto e atribuímos o senador ao conjunto em que a distância se mostrou menor.

Ao fim dessa iteração para todos os senadores, o centroide de cada conjunto será recalculado (devido aos novos senadores que foram atribuídos). Repete-se a iteração do parágrafo anterior, que poderá resultar em novos arranjos de conjuntos. 

Caso nada mude em relação à iteração anterior (os mesmos senadores continuam juntos), significa que o algoritmo convergiu e não adianta mais insistir nele.

Para valores maiores de k, são criados mais conjuntos (a partir de mais centroides arbitrários) no começo do algoritmo, e deve-se acrescentar o cuidado de conferir se nenhum conjunto ficou vazio após o fim de cada iteração. Caso isso ocorra, é sorteado um senador qualquer para preenchê-lo e começam novas iterações.

Como não há garantia da melhor solução global, o procedimento adotado foi de registrar em arquivo o resultado obtido ao fim do algoritmo, e realizá-lo novamente, dezenas ou centenas de vezes. A cada novo início, k outros centroides aleatórios são escolhidos como ponto de partida, e os resultados (provavelmente) variam ao fim da convergência. Como todas as convergências são registradas em arquivo, posso analisar posteriormente qual foi o resultado mais comum.

Resultados

Como indicado na tabela a seguir, o algoritmo foi rodado mil vezes para cada um dos valores de k indicados. As últimas duas colunas se referem ao melhor candidato a solução global (o mais comum nos resultados).

k total de execuções do algoritmo número de ocorrências do resultado mais comum frequência relativa
2 1000 317 31.7%
3 1000 175 17.5%
4 1000 6 0.6%
5 1000 2 0.2%

Conforme cresce, a chance dos resultados se repetirem diminui. Decidi ignorar os senadores que tiveram menos de 10 votos abertos (até pesquisei os nomes dos cinco senadores para entender o motivo de tamanha abstenção), pois muitas convergências deixavam um deles num grupo isolado (em especial para k > 3), enquanto os senadores restantes se distribuíam em k - 1 conjuntos.

Além disso, durante as execuções, pude perceber um aumento na quantidade média de iterações necessárias para cada resultado, conforme crescia. O tempo de execução das mil tentativas então saltava de pouco mais de um minuto (k = 2) para mais de uma hora (k = 5, em que apenas um resultado se repetiu).

Pode-se dizer que o algoritmo, como implementado, não se adequou muito a valores maiores de k. Especulo que isso se deva em grande parte à fórmula de distância adotada, que não é euclidiana como recomendam as referências de k-means consultadas.

No entanto, uma curiosidade: a partir destas identidades (que eu nem poderia imaginar), verifica-se que, num total de 85 senadores, a quantidade de formas em que se pode agrupá-los é absurdamente grande. Para k = 2, chega à ordem de \(10^{25}\). Para k = 3, \(10^{39}\). Para k = 4, \(10^{50}\). E para k = 5, \(10^{57}\). Portanto, mesmo tendo uma porcentagem baixa, a repetição de um resultado é rara demais para ser levada como mera coincidência.

Veja abaixo como provavelmente ficaria uma turma de senadores, caso a professora pedisse para que se separassem em:

k = 2

Acir Gurgacz Aloysio Nunes Ferreira
Alfredo Nascimento Alvaro Dias
Ana Rita Ana Amélia
Angela Portela Ataídes Oliveira
Anibal Diniz Aécio Neves
Antonio Carlos Rodrigues Blairo Maggi
Antonio Carlos Valadares Cristovam Buarque
Armando Monteiro Cyro Miranda
Benedito de Lira Cássio Cunha Lima
Casildo Maldaner Cícero Lucena
Ciro Nogueira Fernando Collor
Clésio Andrade Flexa Ribeiro
Delcídio do Amaral Jarbas Vasconcelos
Eduardo Amorim Jayme Campos
Eduardo Braga José Agripino
Eduardo Lopes Lúcia Vânia
Eduardo Suplicy Mário Couto
Epitácio Cafeteira Osvaldo Sobrinho
Eunício Oliveira Paulo Bauer
Francisco Dornelles Pedro Simon
Gim Pedro Taques
Humberto Costa Randolfe Rodrigues
Inácio Arruda Roberto Requião
Ivo Cassol Ruben Figueiró
Jader Barbalho Waldemir Moka
Jorge Viana Wilder Morais
José Pimentel  
José Sarney  
João Alberto Souza  
João Capiberibe  
João Durval  
João Ribeiro  
João Vicente Claudino  
Kátia Abreu  
Lindbergh Farias  
Lobão Filho  
Luiz Henrique  
Lídice da Mata  
Magno Malta  
Mozarildo Cavalcanti  
Paulo Davim  
Paulo Paim  
Ricardo Ferraço  
Rodrigo Rollemberg  
Romero Jucá  
Sérgio Petecão  
Sérgio Souza  
Valdir Raupp  
Vanessa Grazziotin  
Vicentinho Alves  
Vital do Rêgo  
Walter Pinheiro  
Wellington Dias  
Zeze Perrella  

 

k = 3

Acir Gurgacz Alfredo Nascimento Aloysio Nunes Ferreira
Ana Rita Antonio Carlos Rodrigues Alvaro Dias
Angela Portela Armando Monteiro Ana Amélia
Anibal Diniz Ciro Nogueira Ataídes Oliveira
Antonio Carlos Valadares Clésio Andrade Aécio Neves
Benedito de Lira Eduardo Braga Blairo Maggi
Casildo Maldaner Eduardo Lopes Cristovam Buarque
Delcídio do Amaral Eunício Oliveira Cyro Miranda
Eduardo Amorim Francisco Dornelles Cássio Cunha Lima
Eduardo Suplicy Ivo Cassol Cícero Lucena
Epitácio Cafeteira Jader Barbalho Flexa Ribeiro
Fernando Collor José Sarney Jarbas Vasconcelos
Gim João Alberto Souza Jayme Campos
Humberto Costa João Vicente Claudino José Agripino
Inácio Arruda Lobão Filho Lúcia Vânia
Jorge Viana Luiz Henrique Mário Couto
José Pimentel Mozarildo Cavalcanti Paulo Bauer
João Capiberibe Romero Jucá Pedro Simon
João Durval Sérgio Petecão Pedro Taques
João Ribeiro Valdir Raupp Ruben Figueiró
Kátia Abreu Vanessa Grazziotin Wilder Morais
Lindbergh Farias Zeze Perrella  
Lídice da Mata    
Magno Malta    
Osvaldo Sobrinho    
Paulo Davim    
Paulo Paim    
Randolfe Rodrigues    
Ricardo Ferraço    
Roberto Requião    
Rodrigo Rollemberg    
Sérgio Souza    
Vicentinho Alves    
Vital do Rêgo    
Waldemir Moka    
Walter Pinheiro    
Wellington Dias    

 

k = 4

Acir Gurgacz Aloysio Nunes Ferreira Alvaro Dias Alfredo Nascimento
Ana Rita Ataídes Oliveira Ana Amélia Antonio Carlos Rodrigues
Angela Portela Ivo Cassol Aécio Neves Armando Monteiro
Anibal Diniz Jader Barbalho Blairo Maggi Ciro Nogueira
Antonio Carlos Valadares Jarbas Vasconcelos Cristovam Buarque Clésio Andrade
Benedito de Lira Jayme Campos Cyro Miranda Eduardo Braga
Casildo Maldaner Luiz Henrique Cássio Cunha Lima Eduardo Lopes
Delcídio do Amaral Paulo Bauer Cícero Lucena Eunício Oliveira
Eduardo Amorim Wilder Morais Flexa Ribeiro Francisco Dornelles
Eduardo Suplicy   José Agripino José Sarney
Epitácio Cafeteira   Lúcia Vânia João Alberto Souza
Fernando Collor   Mário Couto João Vicente Claudino
Gim   Osvaldo Sobrinho Lobão Filho
Humberto Costa   Pedro Simon Mozarildo Cavalcanti
Inácio Arruda   Pedro Taques Romero Jucá
Jorge Viana   Randolfe Rodrigues Sérgio Petecão
José Pimentel   Roberto Requião Valdir Raupp
João Capiberibe   Ruben Figueiró Vanessa Grazziotin
João Durval   Waldemir Moka Zeze Perrella
João Ribeiro      
Kátia Abreu      
Lindbergh Farias      
Lídice da Mata      
Magno Malta      
Paulo Davim      
Paulo Paim      
Ricardo Ferraço      
Rodrigo Rollemberg      
Sérgio Souza      
Vicentinho Alves      
Vital do Rêgo      
Walter Pinheiro      
Wellington Dias      

 

k = 5

Acir Gurgacz Aécio Neves Aloysio Nunes Ferreira Alfredo Nascimento Alvaro Dias
Ana Rita Cássio Cunha Lima Ataídes Oliveira Antonio Carlos Rodrigues Ana Amélia
Angela Portela Cícero Lucena Ivo Cassol Armando Monteiro Blairo Maggi
Anibal Diniz Epitácio Cafeteira Jader Barbalho Ciro Nogueira Cristovam Buarque
Antonio Carlos Valadares Flexa Ribeiro Luiz Henrique Clésio Andrade Cyro Miranda
Benedito de Lira Jarbas Vasconcelos Paulo Bauer Eduardo Braga Jayme Campos
Casildo Maldaner José Agripino Wilder Morais Eduardo Lopes Lúcia Vânia
Delcídio do Amaral Vital do Rêgo   Eunício Oliveira Mário Couto
Eduardo Amorim     Francisco Dornelles Osvaldo Sobrinho
Eduardo Suplicy     José Sarney Pedro Simon
Fernando Collor     João Alberto Souza Pedro Taques
Gim     João Vicente Claudino Randolfe Rodrigues
Humberto Costa     Lobão Filho Roberto Requião
Inácio Arruda     Mozarildo Cavalcanti Ruben Figueiró
Jorge Viana     Romero Jucá Waldemir Moka
José Pimentel     Sérgio Petecão  
João Capiberibe     Valdir Raupp  
João Durval     Vanessa Grazziotin  
João Ribeiro     Zeze Perrella  
Kátia Abreu        
Lindbergh Farias        
Lídice da Mata        
Magno Malta        
Paulo Davim        
Paulo Paim        
Ricardo Ferraço        
Rodrigo Rollemberg        
Sérgio Souza        
Vicentinho Alves        
Walter Pinheiro        
Wellington Dias        

 

A análise para valores menores de k se mostrou bem concreta, permitindo enxergar algo como as principais duas ou três formas de se fazer política no Senado. Tudo isso sem recorrer a regras ou conceitos ideológicos/partidários, nem ao tema das votações – apenas pela similaridade de registros.

O que fazer a partir dessas informações fica a seu critério. Dá pra descobrir muito mais só com o XML que escolhi, imagina então com todas as outras fontes? Vale conferir também as ferramentas do Radar Parlamentar, bem mais trabalhadas e que até serviram de inspiração para essa atividade. Se tiver alguma dúvida ou algo a acrescentar, não deixe de comentar aqui ou comigo! Valeu pelo interesse e pela paciência yes





Leia mais sobre: