Upload
ricardo-raminhos
View
6
Download
0
Embed Size (px)
DESCRIPTION
Resumo do estado da arte na área de algoritmos de inteligência artificial para a classificação e detecção de padrões em dados.
Citation preview
SmartContentProvider | Entidade Promotora: Parceiros:
1/2 Projeto em curso com o apoio de:
08/04/2013
SMART CP Algoritmos de classificação e detecção de padrões
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Índice Introdução .......................................................................................................................................................... 3
Inteligência Artificial ........................................................................................................................................... 4
Definição ......................................................................................................................................................... 4
Áreas de Inteligência Artificial ........................................................................................................................ 4
Machine Learning (Clustering e Classificação) ........................................................................................... 4
Reconhecimento de Padrões...................................................................................................................... 4
Lógica, Inferência e Planeamento .............................................................................................................. 5
Onde a Inteligência Artificial pode ser aplicada ............................................................................................. 5
Jogos ........................................................................................................................................................... 5
Motores de Pesquisa .................................................................................................................................. 6
Visão Computacional .................................................................................................................................. 6
Aprendizagem Supervisionada e Aprendizagem Não Supervisionada ........................................................... 7
Terminologia............................................................................................................................................... 7
Cluster ......................................................................................................................................................... 7
Hard Clustering ........................................................................................................................................... 8
SVM ............................................................................................................................................................ 8
Outlier ......................................................................................................................................................... 8
Linguagem Natural ..................................................................................................................................... 9
Algoritmo MinMax ..................................................................................................................................... 9
Aplicação de Inteligência Artificial ao SMART CP ............................................................................................. 10
Clustering .......................................................................................................................................................... 12
Definição ....................................................................................................................................................... 12
Algoritmos .................................................................................................................................................... 12
K-Modes .................................................................................................................................................... 12
Affinity Propagation ................................................................................................................................. 13
Ferramentas relevantes ............................................................................................................................... 14
Weka 3 ...................................................................................................................................................... 14
Orange ...................................................................................................................................................... 15
PyBrain e scikit-learn ................................................................................................................................ 17
Classificação ..................................................................................................................................................... 19
Definição ....................................................................................................................................................... 19
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Algoritmos .................................................................................................................................................... 19
Redes Neuronais ....................................................................................................................................... 19
Árvores de Decisão ................................................................................................................................... 21
Ferramentas relevantes ............................................................................................................................... 22
Theano ...................................................................................................................................................... 22
LIBSVM ...................................................................................................................................................... 22
PyBrain e SciKit ......................................................................................................................................... 23
Recomendações Finais ..................................................................................................................................... 24
Referências ....................................................................................................................................................... 25
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Introdução O presente documento “Algoritmos de classificação e detecção de padrões” constitui um dos resultados da
fase de “Estudos Preliminares” do projecto SmartCP. Em particular, sumariza o trabalho realizado no
contexto da tarefa “Levantamento do estado da arte e experimentação sobre algoritmos de classificação e
detecção de padrões”.
O documento vai começar por introduzir os conceitos necessários de Inteligência Artificial, como estes se
aplicam ao projecto e algumas alternativas de algoritmos e ferramentas que permitam desenvolvê-lo. Por
fim, as soluções e estratégias mais apropriadas serão recomendadas para que se possa prosseguir com o
desenvolvimento.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Inteligência Artificial
Definição O termo Inteligência Artificial pode-se explicar superficialmente em poucas palavras, mas contemplar todos
os temas por ele abrangidos não é uma tarefa fácil. Existem diferentes domínios, os quais serão mais
detalhados na próxima secção, e cada um destes está dividido em vários subdomínios. De forma geral,
Inteligência Artificial é a disciplina que envolve desenvolver computadores e software inteligente.
Por “inteligente” entende-se que um computador ou aplicação de software consegue recolher informação,
tomar decisões, aprender, planear e comunicar, ou seja, exibir inteligência semelhante à dos seres
humanos. O sonho de criar com sucesso máquinas inteligentes existe há muito tempo [1] [2] mas
concretizá-lo é extremamente complexo e ambicioso. No entanto, a verdadeira inteligência artificial, capaz
de emular a mente de um ser humano, não é o objectivo principal da maioria dos movimentos e projectos
desenvolvidos hoje em dia. Para além de ser difícil um projecto abordar de forma significativa mais do que
um domínio da Inteligência Artificial, devido à enorme complexidade dos temas relacionados,
frequentemente diferentes domínios e tipos de dados requerem abordagens e soluções drasticamente
diferentes.
Áreas de Inteligência Artificial Os temas envolvidos em Inteligência Artificial são numerosos e com fronteiras com algum nível de
indefinição em alguns casos. Certos temas sobrepõem-se parcialmente ou não têm limites bem definidos.
Nesta secção, alguns deles serão abordados. [3]
Machine Learning (Clustering e Classificação)
O Clustering e a Classificação são duas áreas incrivelmente importantes da Inteligência Artificial.
Responsáveis por organizar e analisar informação para que esta seja processável de forma expedita, são
dois temas que afectam muitos outros. Dada a relevância destas áreas neste projecto, estes vão ser mais
detalhados em secções posteriores deste documento.
Reconhecimento de Padrões
Dentro de uma aplicação de software, as mensagens que circulam obedecem sempre à mesma estrutura e
não sofrem grandes alterações, mas num âmbito mais abrangente muitas mensagens não podem de todo
ser descritas assim. O reconhecimento de padrões, no geral, revolve à volta de conseguir aplicar padrões
previamente conhecidos a mensagens recebidas no momento.
Por exemplo, a linguagem natural conta com uma alta expressividade: dependendo da língua,
nacionalidade, disposição e experiência do escritor, e de ainda mais factores, a mesma mensagem pode ser
formulada de inúmeras formas diferentes. Adicionalmente, a ambiguidade de muitos termos, as escolhas
específicas de palavras do escritor e o potencial de frases dependerem de contexto, faz com que criar uma
ferramenta que entenda claramente a escrita humana seja uma tarefa monumental.
Reconhecimento de formas e cores em imagens ou de determinados padrões em ondas sonoras são outras
tarefas muitíssimo complexas. Uma mesma imagem pode ser exposta a diferentes níveis de iluminação ou
um diálogo pode conter ruído que distorce os sons recebidos. Estes são alguns dos muitos obstáculos que
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
são encontrados constantemente durante o desenvolvimento de ferramentas e aplicações que visam
entender e processar o mundo que as rodeia.
Lógica, Inferência e Planeamento
Um sistema pode criar decisões autonomamente, através de uma combinação de cálculos matemáticos
aplicados a dados capturados ou calculados por ferramentas de outras áreas da Inteligência Artificial e
escolhas inteligentes baseadas em padrões e regras que já possui.
A lógica proposicional, um tipo de lógica formal, é usada em vários domínios da ciência há séculos [4] e
continua a ser aplicável actualmente, em parte por ter sido actualizada e reformulada com o tempo.
Computadores modernos usam este sistema de lógica e outros para chegar a conclusões e tomar decisões.
Concretamente, sistemas de “non-monotonic logic” permitem, por exemplo, enfrentar problemas com uma
abordagem de “reasoning by default”, em que começam por escolher a solução mais óbvia mas sempre
mantendo a possibilidade de mudar de opinião quando mais factos são descobertos [5]. Esta forma de
tratar problemas é apropriada para sistemas informáticos de inferência. A conclusão de um raciocínio pode
ser alterada para reflectir a agregação de mais informação, algo útil quando a tentar reconhecer linguagem
natural falada, por exemplo.
Onde a Inteligência Artificial pode ser aplicada Existem muitas características do mundo e das vidas das pessoas que podem beneficiar de Inteligência
Artificial. Desde o funcionamento de grandes empresas até ao dia a dia de famílias, existem tarefas e
problemas que podem ser resolvidos mais facilmente recorrendo a alguns algoritmos.
Jogos
A Inteligência Artificial tem sido utilizada para participar em jogos há décadas. Tentativas de criar
computadores capazes de jogar xadrez têm sido feitas desde os anos 50. Entretanto já foram feitos
computadores capazes de vencer mesmo os melhores jogadores humanos, o que evidenciou, acima de
tudo, que o xadrez não é a melhor forma de medir a inteligência de um computador devido à condição de
vitória clara e complexidade relativamente não muito elevada. Com processadores rápidos o suficiente,
aliados de bons algoritmos, torna-se possível explorar todas as possibilidades e daí eleger a melhor opção
com um algoritmo de MinMax. [6] Com técnicas de brute force e processadores progressivamente mais
capazes, tornou-se possível um computador não especializado vencer certos torneios profissionais de
xadrez.
Daí surgiu um novo objectivo: criar um computador capaz de vencer o melhor jogador humano de Go, o
jogo de estratégia ancestral. [6] Com uma complexidade significativamente superior à do xadrez e com
condições de vitória não tão claras, torna-se muito mais difícil aplicar técnicas de brute force para descobrir
as decisões óptimas.
Mas há mais aplicações de Inteligência Artificial em jogos. Especificamente em videojogos, há décadas que
são feitas tentativas de criar entidades “inteligentes”, capazes de responder de forma dinâmica às decisões
feitas pelos jogadores. Mais do que simplesmente ter entidades a pensar de forma individual, o interesse
está também em permitir que diferentes entidades comuniquem entre elas, trabalhando não só à volta das
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
decisões do jogador mas também de acordo com as decisões de outras entidades artificiais e quaisquer
outros factores importantes. [7]
Motores de Pesquisa
Motores como a Google não se limitam a indexar e pesquisar as inúmeras páginas disponíveis em qualquer
momento. A um nível pessoal, o Google consegue adaptar as suas pesquisas e apresentar dados de acordo
com as preferências do utilizador. Um utilizador que visite muitas páginas fortemente relacionadas
transmite ao Google, inconscientemente, que essas páginas lhe são interessantes. Por exemplo, alguém
que faça muitas compras online recebe em primeiro lugar resultados relacionados com compras quando
realiza pesquisas online. A um nível global, o Google relaciona resultados mais populares e destaca-os
quando temas relacionados são seleccionados.
O sistema utilizado para ordenar as páginas por relevância tem de ter vários factores em conta para além
dos termos escolhidos para iniciar a pesquisa, tais como as antigas pesquisas do utilizador, a popularidade
de cada site e a relevância aparente. Relativamente à relevância, especificamente, esta pode ser afectada
por vários componentes de um site, não só pelas palavras que contém.
Motores de pesquisa como o Google utilizam webcrawlers cuja tarefa é varrer sites à procura de links para
outros sites. À medida que sites são encontrados, os webcrawlers devolvem-nos a um indexer que vai
analisar o conteúdo da página e averiguar os termos chave e respectivas localizações. Nesta fase é
necessária análise de linguagem natural com o intuito de entender os termos a capturar e qual o seu valor
como parâmetro de pesquisa. Aos termos capturados são dados pesos, ou pontuações, que determinam o
seu valor e prioridade de pesquisa quando um pedido é feito por um utilizador. Outros elementos de um
site, tal como a quantidade de links para outros sites e a qualidade / popularidade dos sites referidos,
também influenciam a sua relevância quando é feita uma pesquisa.
A análise de linguagem natural é muito útil também para corrigir erros cometidos durante a inserção de
termos de pesquisa ou para expandir a área de investigação. Ao ser capaz de analisar o texto inserido, um
motor de busca pode pesquisar por erros ortográficos, gramaticais ou até mesmo por incongruências entre
temas no pedido, e decidir apresentar resultados relacionados às correcções obtidas.
Visão Computacional
A visão computacional trata de reconhecer padrões em meios visuais. Software de reconhecimento de
faces é uma das aplicações de Inteligência Artificial mais visíveis hoje em dia. O Facebook é capaz de
reconhecer a posição de caras em fotos de pessoas (mas não necessariamente ao ponto de lhes associar
um nome automaticamente) e câmaras fotográficas conseguem detectar faces e gerir o estado da lente
automaticamente para que não haja fotografias desfocadas.
Mas a visão computacional não se limita a imagens estáticas, sendo também aplicável a vídeo. Um sistema
de câmaras de segurança pode seguir um indivíduo no meio de uma multidão ou para atribuir
automaticamente um nome a uma cara, o que pode até estar associado a um sistema de decisão que
permite ser tomada acção contra crimes sem ser necessária interacção humana.
O reconhecimento de caras é apenas uma das aplicações da visão computacional. Veículos que se movem
autonomamente, como o “self driving car” da Google [8], ou dispositivos de reconhecimento de gestos e
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
comportamentos, como a Kinect V2 da Microsoft [9], são alguns dos exemplos de aplicações de visão
computacional. Na Figura 1 podemos ver as diferentes formas que a Kinect V2 tem de captar informação
visualmente, incluindo a visualização de luz infravermelha e a detecção de profundidade, respectivamente
na primeira e terceira representações.
Figura 1 - Diferentes formas de visualização da Kinect V2
Aprendizagem Supervisionada e Aprendizagem Não Supervisionada Quando a lidar com um problema de Machine Learning é necessário determinar que tipo de aprendizagem
é possível aplicar. A aprendizagem supervisionada consiste em atribuir à priori um label, ou rótulo, a cada
ponto de dados. Durante a fase de treino de um modelo de dados, o algoritmo de aprendizagem percorre
um conjunto de dados de treino e associa certas características a certos labels, conhecimento que depois
pode aplicar ao conjunto de dados de teste. Os dados de teste são analisados durante a fase seguinte onde
o algoritmo aplica o que aprendeu para tentar obter a classificação correcta, que é depois comparada com
a classificação existente para determinar a taxa de sucesso da aprendizagem. Com uma taxa de sucesso
elevada, o algoritmo pode ser considerado fidedigno e pode ser usado em situações reais.
No entanto, nem sempre é possível ter dados pré preenchidos com labels o que força o algoritmo a agrupar
os dados em clusters sem confirmação de que estão bem agrupados. Na fase de treino, o algoritmo tenta
encontrar características comuns entre os pontos de dados. Posteriormente, não existe uma fase de teste
semelhante à que existe com a aprendizagem supervisionada já que não há uma forma certa de aferir se os
clusters criados são adequados. Existem certas medidas que podem ser tomadas para testar a qualidade da
aprendizagem feita deste modo mas dependem imenso do projecto e têm de ser escolhidas para se
adaptar correctamente. [10]
Terminologia
Nesta secção são apresentadas as definições de alguns termos utilizados neste documento para referência.
Cluster
Um cluster é um grupo de dados que partilham semelhanças entre eles mais fortemente do que com dados
de outros grupos, sejam quais forem essas semelhanças.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Hard Clustering
Por oposição a Soft ou Fuzzy clustering, Hard Clustering indica que cada ponto de dados não pode
pertencer a mais do que um único cluster.
SVM
SVM (Support Vector Machine) é um modelo de aprendizagem, usado em problemas de classificação e
regressão, baseado em encontrar padrões em dados numéricos dispostos no espaço. O objectivo principal
de um SVM é separar pontos no espaço em dois grupos de uma forma bem definida e o mais ampla
possível. Não existe um limite máximo de dimensões para espaços de pontos que modelo permite abordar
e, por isso, este tende a ser utilizado para estudar espaços de pontos com um elevado número de
dimensões. A Figura 2 ilustra uma situação em que o espaço estudado tem duas dimensões mas o espaço
resultante tem três.
Figura 2 - Funcionamento de SVM’s
Outlier
Um Outlier é um ponto de dados com características tão divergentes que não pode ser atribuído a nenhum
cluster. Numa representação de pontos no espaço, outliers aparecem habitualmente a uma longa distância
de qualquer outro ponto, tal como apresentado na Figura 3.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Figura 3 - Exemplo de outlier
Linguagem Natural
Não existe consenso sobre uma definição formal mas é possível explicar o termo como qualquer linguagem
usada por humanos. Este termo pode-se referir a qualquer formato (escrito, falado ou de outra forma
transmitido) de qualquer linguagem utilizada por seres humanos, por oposição a linguagens utilizadas por
computadores.
Algoritmo MinMax
Também chamado de Minimax, este algoritmo procura minimizar as perdas no contexto de um problema,
utilizando regras de decisão baseado em ter cada acção associada a um custo.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Aplicação de Inteligência Artificial ao SMART CP O objectivo da plataforma resultante deste projecto é processar e apresentar grandes quantidades de
informação sob a forma de conteúdos / registos. Estes registos (e.g. “Ricardo Raminhos”, “VIATECLA” ou
“Universidade de Évora”) dizem respeito a instâncias de conceitos / objectos (e.g. “Pessoa”, “Empresa” ou
“Universidade”, respectivamente).
Aliada ao gestor de conteúdos Scriptor Server, esta plataforma permitirá aos seus gestores e
administradores ter uma definição aberta de conceitos / objectos, uma mais valia em termos de
generalidade, possibilitando por sua vez que tanto o SMART CP e o Scriptor Server sejam aplicáveis a
domínios tão díspares como o Turismo, Media, Metodologias de Gestão de Projecto ou plataformas de
Ticketing, desde que os conceitos / objectos sejam correctamente modelados a essas realidades.
Pretende-se também que o SMART CP faça a gestão de “Issues” encontrados durante o seu funcionamento.
No entanto, por não ser possível conhecer à priori a estrutura dos conceitos / objectos geridos pelo SMART
CP, entender a gravidade destes Issues pode-se revelar como um problema imponente por si só.
Para conseguir lidar com esta questão, deseja-se adicionar ao SMART CP várias técnicas e ferramentas
utilizadas em Machine Learning, particularmente técnicas de Clustering e Classificação que seriam
utilizadas para entender as relações entre os dados dos Issues.
No entanto, frequentemente os dados utilizados dentro de uma aplicação de software não estão
formatados para serem analisados por um sistema automatizado. Para obter bons resultados a partir deste
tipo de abordagens, frequentemente é necessário pré processar os dados.
A etapa do pré processamento consistiria em retirar campos inúteis e converter o formato de campos
noutros que facilitassem o processo de clustering. Uma análise detalhada dos dados permitiria entender
quais os campos inúteis e quais precisariam de ser transformados. Campos que tivessem o mesmo valor em
todas as entradas da lista não seriam colocados nos dados pré processados.
No caso de existirem campos cuja informação é demasiado complexa por si só, tal como campos com
comentários textuais, esses campos não seriam analisados. Por outro lado, se existissem comentários sem
conteúdo, estes poderiam não ser ignorados mas sim substituídos por valores booleanos para se limitarem
a indicar se havia ou não comentário, independentemente do seu conteúdo, significado ou tamanho. Nos
dados pré processados, campos que anteriormente tinham um comentário passariam a ter um valor
verdadeiro, caso contrário o valor seria falso. Assim seria retida alguma informação sobre o campo sem ser
necessário fazer uma análise muito detalhada sobre o seu conteúdo.
O pré processamento poderia também simplificar alguns campos. Para os algoritmos, ter campos com
múltiplos elementos não apresenta qualquer problema, mas torna-se computacionalmente complexo lidar
com conteúdos como texto ou representações de conceitos mais complexos. Se um certo campo contiver
um elemento de um domínio pequeno e finito, para simplificar o problema, este pode ser substituído por
um número inteiro e guardado num dicionário que associa cada um desses elementos complexos a um
número inteiro para que depois do processamento se entenda o que cada campo significa.
Uma possível estrutura para os dados necessários seria como no exemplo que se segue:
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
1. { 2. "Result": "OK", 3. "Total": "1712", 4. "Content": [ 5. { 6. "Issue": { ... } 7. }, 8. { 9. "Issue": { ... } 10. }, 11. ... 12. { 13. "Issue": { ... } 14. } 15. ] 16. }
Neste exemplo, o campo Content do objecto de raiz contem uma lista de objectos cujo único elemento é
um Issue. Cada Issue teria vários campos com informação e é nestes campos que estaria a informação
usada em experimentação preliminar do projecto.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Clustering
Definição Clustering consiste em encontrar grupos de dados para que dados dentro de um mesmo grupo tenham
mais semelhanças entre eles do que com dados noutros grupos, quaisquer que sejam essas semelhanças.
Ao contrário da classificação e da regressão, com clustering um modelo de dados é treinado de forma não
supervisionada, isto é, não há uma forma certa de aferir se os clusters encontrados são adequados ou não.
Não se trata de um algoritmo em particular mas de um conjunto de técnicas e objectivos que permitem
chegar a conclusões sobre os dados em questão num determinado problema. Concretamente, os
algoritmos a ser usados têm de ser escolhidos de acordo com o contexto, tendo em conta o tipo de dados e
as restrições escolhidas e/ou do próprio problema.
Existem vários algoritmos de clustering, cada um com diferentes propriedades e favorecendo diferentes
tipos de modelos de dados, mas segundo Vladimir Estivill-Castro, não existe um consenso sobre o que um
cluster é já que a definição depende do problema e dos investigadores que trabalham no problema. [11]
Quando a agrupar dados, frequentemente é necessário aplicar-lhes um pré processamento para
uniformizar a sua estrutura e facilitar / acelerar as fases computacionalmente mais exigentes durante o
processamento principal. Um objectivo deste tipo de pré processamento é encontrar outliers e processá-los
de forma a que estes não influenciem os resultados de forma errada ou prolonguem o processamento
principal. Dados que não estão dentro dos parâmetros habituais podem ser transformados ou resumidos
para que não surjam barreiras excessivas.
Algoritmos A escolha de algoritmo, quando a fazer clustering de dados, influencia os resultados e as taxas de sucesso.
Dependendo do algoritmo, ainda podem existir factores adicionais que influenciam os resultados. Devido á
natureza do clustering e dos problemas que ele tenta resolver, não existe uma solução óptima que dê
sempre resultados como desejado. Por isso, resultados obtidos de cada algoritmo, e de cada variação de
cada algoritmo, quando aplicável, devem ser comparados com os dados resultantes de executar o
algoritmo K-Modes várias vezes para melhor entender os resultados.
K-Modes
É difícil analisar o K-Modes sem conhecer o K-Means, já que este é o algoritmo de clustering mais simples e
usado actualmente. [12] É usado sobretudo quando se tem informação nominal e ordenável, isto é, cada
elemento dos dados é distinto e é possível estabelecer uma relação de ordem entre os elementos. No
entanto, neste projecto grande parte dos dados não são ordenáveis, apenas nominais, e como tal o
algoritmo K-Modes, semelhante ao K-Means mas com uma diferente optimização da função de medida de
desempenho, é mais apropriado. A função de medida de desempenho referida mede o quanto boa é essa
separação, dado um conjunto e dados e uma separação em clusters.
Adicionalmente, enquanto que o K-Means utiliza uma definição para dados nominais e ordenáveis, o K-
Modes usa uma função, de certa forma mais simples, que funciona para dados somente nominais. O
primeiro passo do K-Modes consiste em fazer o clustering dos dados. Este algoritmo tem como parâmetro o
número de clusters que irá encontrar nos dados. Nos restantes aspectos, o funcionamento dos algoritmos é
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
idêntico. No entanto, como o resultado deste algoritmo depende do número de clusters escolhidos ao
início, para ter um conjunto de resultados abrangente é necessário executá-lo várias vezes com diferentes
parâmetros. [13] [14] [15] [16]
Affinity Propagation
Um outro algoritmo de clustering relevante é o Affinity Propagation. [17] Este algoritmo não necessita de
conhecer o número de clusters à priori (i.e. como parâmetro) pois o próprio algoritmo encontra o número
óptimo de clusters, mas tem o inconveniente de poder encontrar clusters desproporcionais. Apesar disso,
este algoritmo tem vindo a ser reconhecido como um dos melhores algoritmos de clustering por ter baixas
taxas de erro ao encontrar clusters de forma eficaz e por ser determinístico na sua apresentação de
resultados.
Para auxiliar a explicação deste algoritmo, a Figura 4 contém o fluxo do funcionamento e ilustrações para
os conceitos principais. Os elementos chave deste algoritmo são o sistema de exemplars e o de mensagens.
Um exemplar é um ponto de dados pertencente a um cluster que melhor representa os atributos que
definem esse cluster. Um exemplar, de certa forma, pode ser considerado um label determinado pelos
pontos relacionados e pelo próprio algoritmo, apesar de não ser utilizado do mesmo modo.
O potencial de cada ponto de dados como exemplar começa a 0, por omissão, e à medida que os dados são
analisados e agregados, a validade de cada ponto de dados como exemplar é recalculada com cada
iteração. Cada ponto comunica com os outros, de maneira a determinar o seu valor, e o valor de outros,
como representante de um cluster. Esta comunicação funciona analogamente a uma campanha política, em
que os candidatos anunciam porque são bons candidatos e todos os outros elementos expressam a sua
opinião sobre os candidatos. O que difere nesta situação, todos os pontos são candidatos até que um ponto
vizinho seja eleito. Como apresentado nas secções B e C da Figura 4, as responsibilities funcionam como os
votos de cada nó para cada candidato e as availabilities equivalem à campanha política, o que significa que
cada candidato mostra a todos os outros pontos porque são boas escolhas para exemplar.
Simultaneamente, os clusters são definidos de acordo com os candidatos e estes são agrupados com os
pontos de dados que procuram representar.
O fim da troca de mensagens coincide com a finalização da delineação dos clusters. Nesse momento,
apenas alguns dos pontos de dados têm a pontuação mais alta, sendo assim eleitos como exemplars dos
seus clusters respectivos. [18] [19]
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Figura 4 - Affinity Propagation
A função dos exemplars é exclusivamente delinear clusters à sua volta e não servem qualquer outro
propósito. [20] [21] [22] [23]
Ferramentas relevantes Existem várias ferramentas que podem ser utilizadas para a implementação de um processo de clustering e
para o próprio pré processamento. Algumas dessas ferramentas são utilizadas através de uma linguagem
de programação, outras têm interfaces gráficas e algumas beneficiam de ambas as modalidades.
Weka 3
Um exemplo de uma ferramenta muito usada com ambas as modalidades é o Weka 3. [24] Esta ferramenta
é sobretudo para mineração de dados, permitindo fazer análises estáticas aos mesmos e executar tarefas
de classificação, regressão, e clustering. Desenvolvida na Universidade de Waikato na Nova Zelândia, esta
ferramenta foi desenvolvida com Java e usa a linguagem para fazer algumas das tarefas que disponibiliza
em aplicações externas ao Weka. A facilidade de uso é a sua particularidade mais notável.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
A sua interface gráfica e competente colecção de funcionalidades permite que utilizadores com diferentes
origens, níveis de experiência e tipos de dispositivos possam usar o Weka 3 eficazmente, o que leva a que
seja usada muito frequentemente por motivos educacionais. E quando essa colecção não dá acesso a
alguma funcionalidade ou técnica, o Weka 3 conta também com um gestor de packages, ou extensões, que
permite facilmente expandir as suas capacidades. Existem packages oficiais, desenvolvidas e apresentadas
pela equipa de desenvolvimento do Weka 3, mas também existem packages não oficiais que, apesar de não
terem sido criadas pela mesma equipa, são analisadas e geridas por esta para garantir que a qualidade se
mantém dentro de níveis aceitáveis e que não é distribuído qualquer tipo de software malicioso. Entre as
packages oficiais e não oficiais, o total passa dos 160, elevando o potencial do Weka 3 como ferramenta de
Machine Learning.
Orange
Semelhante ao Weka, existe o Orange. Esta ferramenta permite também fazer algum pré processamento,
tarefas de classificação, regressão, e clustering. Desenvolvida em C++, pode ser usada em aplicações Python
externas ao Orange graças a wrappers mas dois aspectos destacam-na de outras soluções: as formas
alternativas de visualizar dados e a possibilidade de personalizar as funcionalidades base, contidas no
canvas, com widgets dedicados a tarefas específicas.
Os widgets são criados exclusivamente pela equipa responsável pelo software base. A colecção oferece
acima de 100 extensões únicas e mais estão sob desenvolvimento. Alguns desses widgets oferecem opções
de visualização que o Weka 3 não possui, o que aumenta o seu valor consideravelmente. Como se pode ver
nas figuras Figura 5 e Figura 6, para além das tabelas e de um scatterplot básico, a ferramenta permite
também utilizar uma variedade de gráficos, tal como um diagrama de Venn e um gráfico em árvore. Mais
opções de visualização levam a diferentes perspectivas que podem levar a conclusões que não seriam
alcançadas de outro modo.
Em ambas as imagens também é possível ver o esquema de construção de workflows que utiliza widgets
para definir o que é feito pela aplicação, o que funciona como programação visual.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Figura 5 - Orange Diagrama de Venn
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Figura 6 - Orange Dendrogram
PyBrain e scikit-learn
Destacam-se por último duas bibliotecas para Machine Learning e Mineração de Dados: O PyBrain [25] e o
SciKit. [26] Ambas são bibliotecas para Python que implementam vários algoritmos e beneficiam da
linguagem para fazer quaisquer tarefas de pré processamento. Para falar de qualquer uma destas
bibliotecas é necessário referir a NumPy, uma biblioteca de cálculo numérico que permite implementar
quaisquer algoritmos necessários para um projecto deste domínio.
No entanto, apesar de esta secção do documento estar à procura de soluções para clustering, a capacidade
de clustering é apenas uma fracção de todas as capacidades destas bibliotecas. Adicionalmente, permitem
que seja feita redução do número de dimensões de um problema, regressão e classificação dos dados, o
que as torna ainda mais apelativas quando a escolher as ferramentas para um projecto.
A biblioteca scikit-learn é usada para tarefas de clustering. Contando com as capacidades matemáticas
existentes no universo do Python, utilizando o NumPy para o cálculo dos algoritmos, esta oferece todos os
elementos necessários para muitas tarefas de Machine Learning. No entanto, a scikit-learn não apoia redes
neuronais, o que leva a falar de uma outra biblioteca, a PyBrain.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
A PyBrain oferece algoritmos de Machine Learning de forma flexível e simples de utilizar, indicada para
alunos mas também permitindo enfrentar problemas cujo estudo só começou recentemente. Apesar de ter
alguma variedade de tipos de algoritmos, esta biblioteca foi criada para funcionar à volta das redes
neuronais e, por isso, é uma escolha valiosa para qualquer projecto que as envolva.
Já que as competências destas duas bibliotecas se complementam mutuamente, a união das duas é
equivalente ou superior a muitas outras soluções. De forma diferente dos sistemas de packages ou widgets
das outras duas ferramentas mencionadas anteriormente, o potencial destas duas ferramentas pode ser
estendido com outras bibliotecas Python. Isto significa que a extensão pode ser feita com qualquer código,
sem ser necessário passar por qualquer processo de aprovação, o que é altamente desejável para quem
queira criar as suas próprias extensões ou para quem prefira a variedade de funcionalidades
disponibilizadas pelo vasto número de bibliotecas já existentes em Python que trabalham com Machine
Learning. Por exemplo, apesar de não existir uma interface gráfica centralizada para a utilização das
funcionalidades destas duas bibliotecas, a utilização da matplotlib permite a criação de variadíssimos
gráficos, oferecendo um grande número de alternativas de visualizar os dados.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Classificação
Definição A classificação é um domínio da Inteligência Artificial que engloba técnicas e ferramentas cujo propósito é
atribuir diferentes classes ou categorias a diferentes pontos de dados ou a clusters de acordo com uma
série de parâmetros. A classificação é normalmente supervisionada, por oposição ao clustering, pois há um
conjunto de dados já classificados a partir de onde se treina o modelo de dados e há um outro conjunto
também classificado a partir de onde se testa esse modelo.
Treinar o modelo de dados significa alimentar o mecanismo de classificação com um conjunto de dados
previamente classificados. Por exemplo, para classificar um conjunto de pessoas como adultos ou crianças
seria fornecido ao algoritmo de classificação um conjunto de dados sobre pessoas em que cada uma já
tinha sido identificada como “adulta” ou “criança”. Os dados relacionados descreveriam cada pessoa até
certo ponto e, a partir desses dados, o algoritmo formaria regras de decisão que depois poderia aplicar a
mais dados de pessoas sem saber previamente a que categoria pertencem.
Na fase seguinte, o modelo de dados é testado, ou seja, as regras de decisão formadas na fase anterior são
aplicadas aos dados que ainda não têm uma categoria estabelecida e categorias são automaticamente
atribuídas. Continuando no mesmo exemplo, ao receber mais conjuntos de dados, o algoritmo de
classificação seria capaz de determinar, com um certo grau de confiança, se cada pessoa é adulta ou
criança. Uma vez obtidos os resultados dos testes, estes serão comparados com os resultados reais para
conhecer o nível de precisão. Quanto mais informativos forem os dados e quanto melhor forem as regras
formadas, mais resultados serão correctamente classificados e mais elevada será a taxa de sucesso.
Ao automatizar este processo, torna-se possível classificar grandes quantidades de informação sem
intervenção humana, o que significa que os resultados vão ser mais consistentes e obtidos de forma mais
expedita. Adicionalmente, a automatização da execução de algoritmos de classificação permite que os
ajustes sejam feitos entre cada execução, ou, por outras palavras, permite que um algoritmo aprenda e se
torne melhor com o tempo. A aprendizagem é um grande componente da classificação. Ao possibilitar que
as regras de decisão sejam melhoradas automática e iterativamente, a qualidade dos resultados aumenta
com a sua repetida utilização. No entanto, a exactidão deste tipo de reconhecimento nunca vai garantir
resultados correctos e se más regras forem formadas durante o período de treino, os resultados podem ser
inúteis, independentemente de quantas iterações sejam feitas.
Algoritmos
Redes Neuronais
Tal como o nome sugere, uma Rede Neuronal é efectivamente como uma rede de neurónios. Tendo o
cérebro humano como referência, cada neurónio por si só é muito simples e não é capaz de processar
muita informação ou formar conexões complexas. Contudo, quando muitos neurónios colaboram, as
conclusões obtidas são incomparavelmente mais ricas. Esta abordagem é frequentemente aplicada a
problemas de reconhecimento de voz ou imagens.
Estas redes podem ser apresentadas como um grafo direccionado composto por três camadas distintas,
exemplificadas na Figura 7. A primeira camada é a camada de input, um conjunto de subcamadas
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
intermédias de processamento, frequentemente chamadas de hidden layers, e a camada de output. Na
primeira camada existe um neurónio por cada valor de input. Por exemplo, numa imagem com 400 pixels,
ou 20x20 pixels, cada pixel é uma variável de entrada, ou seja, a rede neuronal terá 400 neurónios na
primeira camada. Cada um dos neurónios recebe a informação do pixel correspondente, determina o
significado da informação e envia o seu output para os neurónios da camada seguinte. A camada
intermédia pode conter várias subcamadas de neurónios. É nesta camada intermédia que é feita a maioria
do processamento. De acordo com a informação que recebe, os neurónios nesta camada enviam os seus
resultados para a camada seguinte, seja ela a subcamada seguinte ou a terceira camada. O output final dos
neurónios da camada intermédia é recebido como input na terceira camada, onde se vai determinar o
resultado final. Cada neurónio nesta camada corresponde a um único output do algoritmo. O valor
recebido por cada neurónio é um valor real entre 0 e 1 que indica a probabilidade do seu output
correspondente ser o correcto. Assim, o neurónio com a melhor pontuação é o escolhido para enviar como
resposta ao problema.
Figura 7 - Exemplo de uma rede neuronal
A forma como as subcamadas intermédias separam os dados é ajustável, incluindo o número de
subcamadas, a quantidade de neurónios e os seus parâmetros. É nesta camada que se aplica a
aprendizagem. Isto significa que com ajustes simples e automáticos torna-se possível melhorar a precisão
dos resultados. Em diferentes passagens de uma rede neuronal, o resultado é comparado com soluções já
estabelecidas e é descoberta a eficácia da configuração actual. Após múltiplas tentativas, a configuração
com o maior número de resultados correctos é escolhido para ser usado em situações reais.
Esta estrutura permite lidar com problemas complexos sem que a complexidade da própria rede neuronal
se torne difícil de gerir.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Árvores de Decisão
As árvores de decisão e redes neuronais partilham algumas características. Tal como um neurónio de uma
rede neuronal, cada input passa por um simples teste e envia o output correspondente, e onde cada nó
intermédio de uma árvore de decisão recebe um input e direcciona a execução do algoritmo para o filho
correspondente. Começando pela raiz, à medida que cada elemento dos dados é testado por cada nó
(numa lógica condicional), este aproxima-se de uma folha da árvore onde a sua classificação será
determinada.
A estrutura é equivalente a uma árvore binária, não equilibrada, com vários nós intermédios cujos ramos
levam a folhas que correspondem a uma única classificação. A Figura 8 contém um exemplo de uma árvore
de decisão que determina se um banco deve aceitar a proposta de empréstimo de um cliente. O
rendimento do cliente, a extensão da sua educação, em anos, e o tamanho do agregado familiar
determinam se o banco deve aceitar a proposta.
Figura 8 - Árvore de decisão
Durante a fase de treino, a árvore é construída de forma a minimizar o número de nós / testes e maximizar
a informação obtida de cada um. A construção de uma destas árvores começa com apenas um nó que
representa a raiz. Por cada atributo a ser considerado é feito um teste que maximiza o ganho de
informação. O atributo que resultar numa divisão mais equilibrada dos dados é escolhido para ser testado
nesse nó.
Como apresentado na Figura 9, o valor da entropia está próximo do máximo na raiz porque a divisão de
dados obtida é quase simétrica. Nesse exemplo, a separação na raiz já está definida e é estudada a escolha
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
de atributos para os filhos da raiz. São então testadas as entropias com separações dos dados feitos com
cada atributo (atributos A1 e A2, na figura abaixo) em cada nó. O atributo A1 leva a valores de entropia de
0.706 e 0.742, finalmente levando a um ganho de informação de 0.266. O atributo A2 leva a valores de
entropia de 0.937 e 0.619, resultando num ganho de informação de 0.121. Assim, o atributo A1 resulta em
divisões de dados que mais informação oferecem, por outras palavras este atributo permite classificar
dados com menos passos. Todo este processo, depois de ser aplicado à raiz, é aplicado a cada um dos nós
resultantes da divisão de dados até que se tenha uma conclusão.
Figura 9 - Entropia e Ganho de Informação
A simplicidade de construção e consulta destas árvores tornou-as excepcionalmente populares para
analisar problemas simples. No entanto, conceitos mais complexos podem levar a árvores de grandes
dimensões muito exigentes em termos de recursos.
Ferramentas relevantes
Theano
Esta biblioteca, utilizada com Python e beneficiando de alta integração com o NumPy, permite analisar
expressões matemáticas que envolvam arrays multi-dimensionais e processar enormes quantidades de
informação de forma eficiente. [27] É uma das ferramentas mais populares de Machine Learning segundo
um estudo feito este ano. [28] Destaca-se por executar de forma eficiente tanto em CPU’s como eu GPU’s.
É utilizada por grandes empresas tal como o Facebook, a Google e a Oracle. Projectos como o Theanet
utilizam o Theano para classificar imagens com redes neuronais. [29]
LIBSVM
Dois investigadores da Universidade de Taiwan desenvolveram esta aplicação para tornar a classificação
com SVM’s acessível a utilizadores que de outra forma não teriam conhecimento necessário. [30] Esta
aplicação, criada com C e C++, permite efectuar classificação e regressão de dados e pode ser aliada e
estendida com um número considerável de linguagens.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
PyBrain e SciKit
Apesar de já terem sido mencionados na secção de clustering, a sua versatilidade torna-as candidatas
competitivas para a escolha de ferramenta de classificação.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Recomendações Finais A combinação SciKit e PyBrain é a solução mais indicada, tanto para resolver problemas de clustering como
de classificação. Simultaneamente facilmente acessíveis e poderosas, estas bibliotecas contam com uma
vasta colecção de extensões e documentação que as torna valiosas para qualquer tipo de projecto. A sua
popularidade leva a que haja imensa comunicação envolvente, facilmente acessível e sobre variadíssimos
tópicos relacionados, levando a uma redução do tempo necessário para a resolução de problemas.
Ambos os algoritmos de clustering discutidos, K-Modes e Affinity Propagation, mostram promessa e,
portanto, ambos são recomendados. Os resultados obtidos de cada um podem ser comparados para
conhecer como diferentes algoritmos diferem e detectar falhas no caso de disparidades excessivas serem
encontradas. Mais seriam aconselhadas mas, devido ao elevado custo temporal, apenas duas devem ser
usadas com o intuito de manter a duração do desenvolvimento do projecto dentro de um intervalo de
tempo razoável.
Quando a escolher algoritmos de classificação, tanto as redes neuronais como as árvores de decisão são
úteis, já que se complementam mutuamente e tornam possível lidar com problemas mais complexos e
mais simples, respectivamente.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
Referências
[1] T. Lewis, “A Brief History of Artificial Intelligence,” Live Science, 04 12 2014. [Online]. Available:
http://www.livescience.com/49007-history-of-artificial-intelligence.html. [Acedido em 2015 08 07].
[2] “Brief History,” AI Topics, [Online]. Available: http://aitopics.org/misc/brief-history. [Acedido em 2015
08 07].
[3] J. McCarthy, “WHAT IS ARTIFICIAL INTELLIGENCE?,” 12 11 2007. [Online]. Available: http://www-
formal.stanford.edu/jmc/whatisai/whatisai.html. [Acedido em 10 08 2015].
[4] S. Bobzien, “Ancient Logic,” Stanford Encyclopedia of Philosophy, 13 12 2006. [Online]. Available:
http://plato.stanford.edu/entries/logic-ancient/. [Acedido em 10 08 2015].
[5] C. Strasser e G. A. Antonelli, “Non-monotonic Logic,” Stanford Encyclopedia of Philosophy, 11 12 2001.
[Online]. Available: http://plato.stanford.edu/entries/logic-nonmonotonic/. [Acedido em 10 08 2015].
[6] C. Smith, B. McGuire, T. Huang e G. Yang, “The History of Artificial Intelligence,” December 2006.
[7] M. Lewis e D. Mark, “GDC Vault,” [Online]. Available:
http://www.gdcvault.com/play/1021848/Building-a-Better-Centaur-AI. [Acedido em 11 08 2015].
[8] “Google Self-Driving Car Project,” Google, [Online]. Available: http://www.google.com/selfdrivingcar/.
[9] “Kinect For Windows,” Microsoft, [Online]. Available: https://www.microsoft.com/en-
us/kinectforwindows/.
[10] “Clustering performance evaluation,” Scikit Learn, [Online]. Available: http://scikit-
learn.org/stable/modules/clustering.html#clustering-performance-evaluation. [Acedido em 10 08
2015].
[11] V. Estivill-Castro, “Why so many clustering algorithms: a position paper,” 2002. [Online]. Available:
http://dl.acm.org/citation.cfm?doid=568574.568575.
[12] J. B. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations.,”
Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, p. 281–297,
1967.
[13] K. Wagstaff, C. Cardie, S. Rogers e S. Schroedl, “Constrained K-means Clustering with Background
Knowledge,” Proceedings of the Eighteenth International Conference on Machine Learning, pp. 577-
584, 2001.
[14] B. P. S. e F. U. M., “Refining Initial Points for K-Means Clustering,” 1998.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de:
[15] A. Likasa, N. Vlassisb e J. J. Verbeekb, “The global k-means clustering algorithm,” pp. 451-461, 2003.
[16] D. Pelleg e A. Moore, “X-means: Extending K-means with Efficient Estimation of the Number of
Clusters,” pp. 727-734, 2000.
[17] F. B. J e D. D, “Clustering by Passing Messages between Data Points,” pp. 972-976, 2007.
[18] “AFFINITY PROPAGATION FAQ,” University of Toronto, [Online]. Available:
http://www.psi.toronto.edu/affinitypropagation/faq.html. [Acedido em 11 08 2015].
[19] Y. Fujiwara, G. Irie e T. Kitahara, “Fast Algorithm for Affinity Propagation,” Proceedings of the Twenty-
Second International Joint Conference on Artificial Intelligence.
[20] K. Wang, J. Zhang, D. Li, X. Zhang e T. Guo, “Adaptive Affinity Propagation Clustering,” pp. 1242-1246,
2007.
[21] T. Li, “A General Model for Clustering Binary Data,” Proceedings of the eleventh ACM SIGKDD
international conference on Knowledge discovery in data mining, pp. 188-197, 2005.
[22] Z. Lu e M. Á. Carreira-Perpiñán, “Constrained Spectral Clustering through Affinity Propagation,” pp. 1-
8, 2008.
[23] D. Dueck e B. Frey, “Non-metric affinity propagation for unsupervised image categorization,” pp. 1-8,
2007.
[24] E. F. G. H. B. P. P. R. I. H. Mark Hall, “The WEKA Data Mining Software: An Update,” SIGKDD
Explorations, vol. 11, nº 1, 2009.
[25] T. Schaul, J. Bayer, D. Wierstra, S. Yi, M. Felder, F. Sehnke, T. Rückstieß e J. Schmidhuber, “PyBrain,” To
appear in: Journal of Machine Learning Research, 2010.
[26] G. V. A. G. V. M. B. T. O. G. M. B. P. P. R. W. V. D. J. V. A. P. D. C. M. Fabian Pedregosa, “Scikit-learn:
Machine Learning in Python,” p. 2825−2830, 12 10 2011.
[27] “Deep Learning,” 2015. [Online]. Available: http://deeplearning.net/software/theano/.
[28] J. Steeves, “Machine Learning Tools – An Overview,” 28 5 2015. [Online]. Available:
http://knowm.org/machine-learning-tools-an-overview/.
[29] “Convolutional Neural Network for Image Classification with Theano,” [Online]. Available:
https://github.com/rakeshvar/theanet.
[30] C.-C. Chang e C.-J. Lin, “LIBSVM -- A Library for Support Vector Machines,” ACM Transactions on
Intelligent Systems and Technology, pp. 27:1 - 27:27, 2011.
SmartContentProvider | Entidade Promotora: Parceiros:
2/2 Projeto em curso com o apoio de: