Tag Archives: Agrupamento

Tutorial sobre Vector Quantization

Para quem quer saber o que é Vector Quantization nos vídeos abaixo tem um tutorial.

Etiquetado , ,

Agrupamento de Ativos do Mercado Indiano para Administração de Portfólios

Este paper publicado na revista acadêmica Expert Systems with Applications traz um trabalho interessante no qual pesquisadores indianos utilizaram as técnicas de clustering para construção e administração de portfólios de ativos da bolsa de valores da Índia e compararam os resultados com o índice Sensex.

A pesquisa utiliza como parâmetro de seleção de ativos idéias relativas ao artigo Portfolio Selection de Markowitz, no qual a carteira seria composta não somente pelos ativos que tivessem um melhor retorno financeiro, mas que também tivessem um baixo risco.

Partindo desse princípio, as empresas seriam agrupadas em clusters de acordo com alguns indicadores de análise técnica, e em um momento segunte de acordo com o valor do índice de validação dos clusters seriam formados os portfólios com os pesos de cada companhia.

O artigo trás idéias interessantes e o ponto negativo (e que provavelmente não foram apresentados pelos autores por desconhecimento ou abstração) é que fatores técnicos são inadequados para esse tipo de classificação devido ao seu alto volume de transações, bem como a pesquisa é inviável em termos de atualização de dados para alocação de ativos. O artigo se tivesse focado em indicadores fundamentalistas, macroeconômicos e setoriais  para enquadrar a construção e gestão de portfólios apresentaria melhores resultados.

Clustering Indian stock market data for portfolio management

Etiquetado , , , , , , , , , ,

Modelos de Segmentação e Classificação

Em mais um post de  Antonios Chorianopoulos, ele apresenta as principais características relativas a essas duas tarefas de mineração de dados.

Etiquetado , , , ,

Básico sobre Segmentação de Clientes em Marketing

Para quem deseja aplica a mineração de dados especificamente em Marketing, este artigo do Inside Data Mining explica características bem interessantes sobre o tema, e como devem ser construídas as métricas de negócios.

Etiquetado , , , ,

Aplicação de Mineração de Dados no Mercado Financeiro – Application of data mining techniques in stock markets

Ehsan Hajizadeh, Hamed Davari Ardakani e Jamal Shahrabi, todos da Amirkabir University of Technology no Irã trazem nesse paper uma boa abordagem de idéias de aplicações de mineração de dados no mercado financeiro.

Aos moldes do que faz o ótimo livro do Roberto Pontes que já foi resenhado aqui, os autores colocam um leque de possibilidades bem interessantes com as técnicas de mineração de dados, no qual não somente a mineração de dados será uma ferramenta de análise exploratória e reconhecimento de padrões, como colocam as técnicas como forma de se analisar tendências futuras para melhorar a análise de ativos.

Como os autores bem colocam, o paper vem a preencher uma lacuna na literatura sobre a aplicação de mineração de dados, principalmente no que vai além da dupla árvore de decisão e rede neural.

As técnicas elencadas pelos autores foram: Árvore de Decisão (alternativas de decisão), Redes Neurais (avaliação paramétrica), Agrupamento – Clustering – (observação de dinâmicas de características dos ativos financeiros, análise de fator (avaliação de variáveis e a influência de cada um sobre um modelo de predição), regras de associação (relacionamento entre os ativos de acordo com as características da base de dados), Séries Temporais (análise de tendência e predição).

Para quem deseja engajar-se em um projeto sério de análise de dados financeiros, sem dúvidas esse  artigo traz uma luz bem oportuna ao assunto, e pode auxiliar em pesquisas neste aspecto.

Application of data mining techniques in stock markets

Etiquetado , , , , , , , , , ,

Agrupamento é difícil quando não importa

Esse paper engloba bem os aspectos de como são desenvolvidas métricas para avaliar se um cluster é bom em termos de agrupamento ou não; mas a proposta matemática apresentada está longe de ser trivial.

Clustering is difficult only when it does not matter

Etiquetado , , ,

Mean-Shift

Esse post do Normal Deviate apresenta de uma maneira bem técnica o algoritmo que faz a distribuição da Mean-Shift (algo como mudança de média em tradução literal).

A Mean-Shift é uma técnica de Clustering (agrupamento) na qual tem como objetivo inferir a média dos clusters de acordo com uma função de densidade, na qual em uma janela de interesse (range de dados que compreende o círculo) de faz o cálculo da área em que há mais densidade, e nesse ponto será determinado o ponto central da Mean-Shift e o círculo de interesse se move até esse novo ponto central. Esse processo é realizado de forma sucessiva e só termina quando a Mean-Shift é igual a inferência anterior.

Como bem ressaltado no post, são basicamente 3 passos: (1) estimar a densidade, (2) encontrar a moda da densidade, e (3) associar cada ponto a uma moda.

Esse tipo de função de densidade é mais utilizada em processamento de imagens; mas também pode ser muito útil na análise visual de clusters em qualquer número de dimensões, na qual podem ser feitas análises para 1) detecção de anomalias (outliers), 2) identificação de padrões de outliers, e 3) através de um determinado range (janela de interesse) segmentar e concentrar as análises no ponto de maior densidade  e dentro desse espectro (Mean-Shift e Janela de Interesse) realizar segmentações e ações específicas de acordo com esses dados.

Esse tipo de estudo com Mean-Shift na análise de clusters em mineração de dados, auxilia a determinar espectros de analises em grupos com melhores segmentações e similaridades e com o ‘corte‘ determinado pela janela de interesse.

Um ponto negativo nessa abordagem, é que nem precisa olhar muito para ver que o custo computacional é alto (3 divisões aninhadas e um sigma ali no meio cheira algo de O(g(n))) e se pensarmos em uma análise de cluster trivial (que contenha 100K de registros, essa abordagem pode se tornar inviável.

Uma ótima referência é esse post da pesquisadora Gabriela Bauermann.

Esse vídeo do canal da Gabriela explica de forma visual como é feito o processo do algoritmo Mean-Shift.

PS: Seguem dois códigos para o Main-Shift, um é para Python e outro para Matlab.

Etiquetado , , , , , , , , ,

Livro – Encyclopedia of Distances – Michel Marie Deza, Elena Deza

As técnicas de agrupamento (clustering) são provavelmente uma das disciplinas mais difíceis em relação ao aprendizado/aplicação prática tratando-se de mineração de dados. As técnicas de clustering tem diversas intersecções em relação ao conjunto de disciplinas em sua concepção: estatística, matemática, geometria, etc; e uma importante parte da construção dos clusters (indução gráfica) é bastante relacionado com as medidas de distâncias sejam elas de similaridade (relações entre os pontos da base de dados) e dissimilaridade (relações baseadas nas diferenças entre os pontos).

As medidas de distância são fundamentais em termos de clusters seja no seu custo computacional, complexidade e representação gráfica para análise; a qual dependendo da medida de distância utilizada pode apresentar mudanças significativas em termos de identificação de outliers,  formato dos clusters na camada de apresentação, e até mesmo na formação de vizinhanças entre os grupos de pontos de dados .

Esse livro tem tudo isso bem explicado, com pormenores que vão até o nível mais baixo em relação a aprendizado de máquina; na qual é explicado as importancias, detalhes matemáticos e características de cada uma das medidas de distâncias apresentadas.  

O livro é bem escrito e com as mais diversas medidas apresentadas oferece um leque bem vasto de possibilidades para análise de dados, tudo em linguagem bem acessível e com uma notação matemática bem simples.  É uma boa pedida para quem deseja sair do arroz e feijão das técnicas de cluster (Distância Euclideana, e Manhattan).

O livro não é recomendado para quem não tem familiaridade com análise de clusters, ou não tem endentimento básico de matemática; porém, não é impeditivo.

Encyclopedia of Distances – Michel Marie Deza, Elena Deza

Etiquetado , , , , , , ,

Análise RFM

Um dos tópicos mais comuns para quem trabalha com Mineração de Dados em escala gerencial em especial em setores de CRM é RFM que é a sigla de Recency, Frequency, and Monetary Value (Fator de Recência, Frequência e Valor Monetário) e é um fator de metrificação que tem como finalidade identificar a distribuição de clientes, e o seu comportamento de acordo com a última situação de consumo mais a frequência que o mesmo realiza suas compras bem como o seu valor monetário, isto é o quanto ele efetivamente gasta.

Com esse tipo de métrica é possível realizar análises de segmentação de clientes, como desenvolvimento de campanhas de marketing, ou até mesmo auxiliar setores de cobrança na questão do modelo de liquidação de portfólio de cobrança.

Dois cenários rápidos de aplicação do RFM:

a)      Dentro de uma base de clientes você deseja realizar uma campanha de marketing para fidelização de clientes, no qual de acordo com o RFM você pode escolher os clientes que tenham menor fator F (Frequência) ordenados pelo seu valor monetário e posteriormente pela última atividade de compra (Recência); e

b)      Através de uma campanha de cobrança, você pode incluir o RFM para indicar o quão valioso é o cliente na questão de enviar ou não uma carta; ou mesmo dentro de um limite de acionamento você colocar os clientes mais valiosos em valor monetário (M) em prioridade de acordo com o quão recente é o seu débito (R) já que dívidas recentes tem uma propensão maior para serem pagas.

O artigo em si é bem sintético, porém  dá ótimas dicas de como utilizar o conceito de RFM.

Etiquetado , , , , , , ,

Livro Discovering Knowledge in Data: An Introduction to Data Mining

É sempre difícil comentar sobre um livro o qual se vê claramente que é um dos textbooks que podem receber a denominação de clássico. O livro do Dr. Daniel Larose Discovering Knowledge in Data: An introduction to Data Mining ( ISBN-10: 0471666572 | ISBN-13: 978-0471666578) é um ótimo livro para quem busca conhecer de forma introdutória a Mineração de Dados; bem como quer fugir do lugar comum no qual dezenas de livros sobre o assunto levam.

O autor inicia o livro realizando uma série de overviews bastante pertinentes em relação a elucidação das tarefas de mineração de dados, até mesmo apresentando o CRISP-DM através de casos de estudos.

Após isso, o livro entra na questão do Pre-processamento de dados, e explica de forma bem concisa o conceito de Análise Exploratória de Dados (Exploratory Data Analysis – EDA) .

Nos capítulos subsequentes o autor desvenda através de abordagens conceituais e práticas as Abordagens Estatísticas para Estimação e Predição, Algoritmo k-Nearest Neighbor , Árvores de Decisão, Redes Neurais, Técnicas de Agrupamento e Regras de Associação.

O mais valioso no livro sem sombra de dúvidas é o capitulo 11-Model Evaluation Techniques (Modelo de Técnicas de Avaliação) no qual mostra alguns dos atributos de um projeto de Mineração de Dados mais negligenciados que são Índice de Erros, Falsos Positivos e Falsos Negativos; que através de exemplos práticos em capitulos anteriores mostram uma forma prática de se avaliar os modelos de mineração.

Este livro é para: Cursos Introdutórios de Mineração de Dados, Interessados em Análise Hands-On em Mineração de Dados, Estudantes de Banco de Dados, Entusiastas de Mineração de Dados, Cursos de Graduação sobre a Disciplina de Banco de Dados/Mineração de Dados.

Este livro NÃO é para: Desenvolvimento de projetos complexos de Mineração de Dados, Aprendizado de Técnicas Avançadas em Mineração de Dados, quem não gosta/entende representações matemáticas.

Pontos Positivos: Facilidade de Leitura, Roteiro de assuntos abordados pelo autor, explicações teóricas sem prolixidade, abordagem prática.

Pontos Negativos: Abordagem matemática do autor em determinadas sessões que pode confundir o leitor menos habituado ao tipo de leitura, Tamanho (pouco mais de 220 páginas).

Etiquetado , , , , , , , , ,

Spacial Data Mining in Precision Agriculture

Esse site do pesquisador Georg Ruß é um amplo repositório de dados e pesquisas interessantes sobre utilização de técnicas de agrupamento sobre a atividade de agricultura, e como essas aplicações podem ser úteis na resolução do aproveitamento do espaço no campo, seja na melhoria da produtividade so setor agricola; bem como a manutenção do equilíbrio dentro do aspecto ambiental/ecológico.

Segue abaixo o resumo da tese de doutorado chamada Spatial Data Mining in Precision Agriculture:

Technological advances are nowadays often based on improvements in information and data processing capabilities. Even modern agriculture is to a large extent based on adequate data processing, since the usage of novel information devices, GPS-based georeferenced data collection and high-resolution spatial data sets have become standard modes of operation,
turning the once uniform site management into site-specific management as one of the most important sub-fields in precision agriculture. On the one hand, the resulting data sets clearly provide the foundations for economic and ecologic improvements. On the other hand, these data sets pose novel challenges for spatial data mining. Two specific tasks are explored in this study: spatial variable importance and management zone delineation.

The foundations of this thesis are data originating in site-specific management operations. They typically include electrical conductivity readings, fertilizer applications, soil sampling results, vegetation indicators and yield measurements. These variables are georeferenced, i.e. for a particular point of the site under study the variables and their values are known at a certain spatial resolution. These spatial data sets are furthermore augmented with digital elevation models from which terrain attributes such as slope, wetness index and curvatures are derived.

The first of the tasks is concerned with yield prediction and based on an existing dissertation in this area. Yield prediction is handled as a multivariate regression task using spatial data sets. However, taking the spatial relationships of the data sets into account requires some changes in the standard cross-validation to make it aware of spatial relationships in the data sets. Based on this addition, the question can be answered which of a variety of regression models are best suited for yield prediction. Eventually the regression models help to estimate which of the variables are important for yield prediction using permutation-based variable importance measures.

The second task is concerned with management zone delineation. Based on a literature review of existing approaches, a lack of exploratory algorithms for this task is concluded, in both the precision agriculture and the computer science domains. Hence, a novel algorithm (HACC-spatial) is developed, fulfilling the requirements posed in the literature. It is based on hierarchical agglomerative clustering incorporating a spatial constraint. The spatial contiguity of the management zones is the key parameter in this approach. Furthermore, hierarchical clustering offers a simple and appealing way to explore the data sets under study, which is one of the main goals of data mining.

O autor ainda mantém um grupo de pesquisas com diversos trabalhos sobre regressão, agrupamento, e demais técnicas.

Etiquetado , , , ,

Medidas de Distância

Um dos tópicos mais importantes no momento de se realizar uma análise de agrupamento sobre a base de dados é em relação à medida de distância adotada.

Diversos fatores são levados em consideração quando se faz uma análise como inferência estatística, métricas adotadas para composição do modelo, quantidade de dados a serem minerados; o que exige conhecimento por parte do analista de qual medida de distância escolher de acordo com o domínio do problema e o conjunto de dados, ou se não houver escolha ao menos ter consciência do tipo de resultado que  pode ser obtido de acordo com a medida de distância implantada.

As medidas de distância de uma maneira geral podem ser definidas como medidas de similaridade, e dissimilaridade; na qual a primeira é para definir o grau de semelhança entre as instâncias e realizam o agrupamento de acordo com a sua coesão, e a segunda de acordo com as diferenças dos atributos das instâncias. Como forma de reduzir o escopo de assuntos tratados, esse post irá adotar abordar somente as distâncias de similaridade mais comuns que são a Distância Euclidiana e a Distância Manhattan.

WITTEN e FRANK (2005) realizam uma consideração sobre a utilização das medidas de similaridade:

In instance-based learning, each new instance is compared with existing ones using a distance metric, and the closest existing instance is used to assign the class to the new one. This is called the nearest-neighbor classication method. (WITTEN e FRANK, 2005 p.78)

A Distância Euclidiana é definida como a soma da raiz quadrada da diferença entre x e y em suas respectivas dimensões.

Já a Distância Manhattan tem uma definição mais simples na qual é apenas a soma das diferenças entre x e y em cada dimensão.

Abaixo segue a representação matemática dessas duas medidas:

Distância Euclideana: √((x1 - x2)² + (y1 - y2)²).

Distância Manhattan: |x1 - x2| + |y1 - y2|.

Realizando uma analogia entre a diferença entre essas duas distâncias, vamos imaginar uma a rota de GPS para dois veículos, uma para um carro e outra para um helicóptero. A Distância Euclidiana seria o segmento de uma reta na qual indicaria uma possível rota de helicóptero (na qual não haveria preocupação com as ruas já que é um veículo aéreo, e geometricamente seria a hipotenusa de um triângulo) e a Distância Manhattan seria um segmento de retas na vertical quanto na horizontal semelhante a uma rota de carro (já que esse obedece o sentido das ruas, e devido à esse comportamento essa medida de distância é também conhecida como City Block, e  geometricamente seriam a soma dos catetos).

Um dos problemas para a utilização de técnicas de agrupamento é a utilização de dados nominais em seus atributos, os quais por não ter uma métrica implícita dificultam o trabalho dos algoritmos em termos de atribuição de pesos e valores para formação dos clusters. WITTEN e FRANK (2005) realizam uma observação sobre essa ocorrência de dados nominais em bases de dados para agrupamento.

When nominal attributes are present, it is necessary to come up with a “distance” between different values of that attribute. What are the distances between, say, the values red, green, and blue? Usually a distance of zero is assigned if the values are identical; otherwise, the distance is one. Thus the distance between red and red is zero but that between red and green is one. However, it may be desirable to use a more sophisticated representation of the attributes. For example, with more colors one could use a numeric measure of hue in color space, making yellow closer to orange than it is to green and ocher closer still. Some attributes will be more important than others, and this is usually reflected in the distance metric by some kind of attribute weighting. Deriving suitable attribute weights from the training set is a key problem in instance based learning. (WITTEN e FRANK, 2005 p.78)

Um dos trabalhos futuros para melhorias das medidas de distância são pesquisas na área atribuição dinâmica de pesos para distribuição dos clusters, no qual ao invés dos atributos deterem pesos fixos, de acordo com a sua distribuição e incidência seriam atualizados de forma incremental, WITTEN e FRANK afirmam abaixo:

The next improvement in instance-based learning is to learn the relevance of each attribute incrementally by dynamically updating feature weights. (WITTEN e FRANK, 2005 p.238)

Em termos relativos a utilização da distância euclideana se aplica melhor a dados não padronizados (ou seja dados que não tem nenhum tipo de tratamento de adaptação de escala); e devido a isso o resultado final é insensível a outliers (exceções, ou dados com uma diferença muito grande em relação à média do dataset). Uma desvantagem sobre essa medida de distância pode acontecer se houver diferença de escala entre as dimensões; por exemplo, se no eixo X houver a distância em kilometros, e no eixo Y a distância estiver em centímetros pensando em termos cartográficos. No momento em que houver a transformação de escala (ou seja a conversão de Cm para Km) os resultados euclideanos (que se baseiam nos quadrados e na raiz) sofrem uma influência muito grande das dimensões que possuem os maiores valores.
(Adaptado de STATISTICA)

Já para a Distância Manhattan, além do fato que os outliers são igualmente desconsiderados; entretanto, não há influência de escala (dentro do conjunto de dados) sobre o resultado já que não há elevação ao quadrado dos valores de X e Y.

Concluíndo, na análise de agrupamento é importante saber qual o tipo de medida de distância utilizar de acordo não só com os resultados esperados, mas também analisando todo o tipo de dado que será minerado; pois, como vimos este também exerce influência no resultado final e se não levado em consideração pode tornar a análise de dados enviesada e consequentemente levando a decisões erradas.

REFERÊNCIAS

WITTEN, Ian H., FRANK, Eibe. Data Mining : practical machine learning tools and techniques. 2ª Edição – (2005). Morgan Kaufmann series in data management systems. ISBN: 0-12-088407-0

JAIN, A.K.; MURTY, M.N.; FLYNN, P.J. Data Clustering: A Review. ACM Computing Surveys, Vol. 31, No. 3, September 1999

STANFORD University. Curso CS345 — Lecture Notes – 11 – Clustering, Part I. 2004

OLIVEIRA, Luiz Eduardo S. Inteligência Computacional: Tipos de Aprendizagem. Disponível em << http://www.ppgia.pucpr.br/~soares >> Acessado em 10 Jun 10

Paul E. Black, “Manhattan distance”, in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 31 May 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/manhattanDistance.html

Paul E. Black, “Euclidean distance”, in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/euclidndstnc.html

Stanford University. Heuristics Program. Disponível em <<http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html >> Acessado em 10 Mar 12.

STATISTICA. Cluster Analysis. Disponível em <<http://www.statsoft.com/textbook/cluster-analysis/#d >> Acessado em 10 Mar 12.

Etiquetado , , , , , ,
%d blogueiros gostam disto: