Aprendizado não-supervisionado indica quais senadores votam afim

Este artigo foi originalmente publicado em https://infosimples.com/ por Leonardo Berbare de Araujjo em Janeiro de 2015. Ele foi importado para o Medium da Infosimples, a nova casa dos artigos da Infosimples.

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 © 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² = (p_1 — q_1)² + (p_2 — q_2)² +{ }…{ }+ (p_n — q_n)²\), onde p e q são dois pontos com n 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

). 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 k 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 k 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


Originally published at infosimples.com.