Mais trabalhos sobre clustering.
Anúncios
Clustering
K-Means distribuído sobre dados binários comprimidos
E quem disse que o K-Means estava morto hein?
Introdução sobre Análise de Cluster
Por mais que a análise exploratória de dados ocupe um espaço muito grande em relação em problemas de ciência de dados, os métodos de aprendizado não-supervisionados ainda tem o seu valor, mesmo que nas comunidades científicas e profissionais pouco se fala sobre esse tema com a mesma recorrência dos métodos preditivos.
Uma das técnicas mais subestimadas em machine learning é a técnica de clustering (ou análise de agrupamento).
Esse post do Kunal Jain trás um dos melhores reviews sobre análise de cluster e as suas peculiaridades.
Connectivity models: As the name suggests, these models are based on the notion that the data points closer in data space exhibit more similarity to each other than the data points lying farther away. These models can follow two approaches. In the first approach, they start with classifying all data points into separate clusters & then aggregating them as the distance decreases. In the second approach, all data points are classified as a single cluster and then partitioned as the distance increases. Also, the choice of distance function is subjective. These models are very easy to interpret but lacks scalability for handling big datasets. Examples of these models are hierarchical clustering algorithm and its variants.
Centroid models: These are iterative clustering algorithms in which the notion of similarity is derived by the closeness of a data point to the centroid of the clusters. K-Means clustering algorithm is a popular algorithm that falls into this category. In these models, the no. of clusters required at the end have to be mentioned beforehand, which makes it important to have prior knowledge of the dataset. These models run iteratively to find the local optima.
Distribution models: These clustering models are based on the notion of how probable is it that all data points in the cluster belong to the same distribution (For example: Normal, Gaussian). These models often suffer from overfitting. A popular example of these models is Expectation-maximization algorithm which uses multivariate normal distributions.
Density Models: These models search the data space for areas of varied density of data points in the data space. It isolates various different density regions and assign the data points within these regions in the same cluster. Popular examples of density models are DBSCAN and OPTICS.
Agrupamento usando Mean Shift
Árvore de Decisão para Aplicação de Técnicas de Data Mining
Este é um poster do Scikit, e foi tirado diretamente do Mahbabe.
Não terceirize a Normalização/Padronização dos Dados
Na literatura de mineração de dados muitos autores afirmam que o pré-processamento é uma fase que ocupa 80% do tempo e que os algoritmos são as grandes estrelas com as suas inúmeras formas de descoberta de padrões, regras e associações; e que por isso detêm os 20% mais importantes no que diz respeito à mineração de dados.
Baseado em experiências empíricas acredito que o pré-processamento ocupa 90% do tempo, e que também é responsável por 95% do resultado; dentro da perspectiva da mineração de dados no qual:
Resultado = Custo Computacional + Consistência dos Resultados + Reprodutibilidade
Onde o custo computacional é definido como:
Custo Computacional = Custo Espacial + Custo Temporal
Dito isso, vejo que em fóruns e até mesmo palestras que devido ao grau de dificuldade de trabalhar com os dados, ocorre a famosa terceirização da normalização/padronização dos dados. Isso se dá na forma em que os algoritmos/soluções de análise de dados pegam todos os dados e simplesmente ‘fazem a mágica acontecer’ (acreditem, eu vi um ‘Sales Engineer’ de uma das top 3 ferramentas de Business Intelligence (pela Gartner) falar isso).
No entanto, em alguns pré-experimentos com MARS (Multivariate Adaptive Regression Splines) no Statistica 10 e MLPRegression no Weka observei que muitos valores das variáveis de resposta (i.e. valores para realizar o teste e/ou checagem matemática do algoritmo) estavam com números que não faziam sentido algum, e pior: não davam a reprodutibilidade necessária para exercer um simples hindcast (não confundam com backtesting).
Vejamos dois casos práticos a respeito disso.
Neste primeiro caso vejam o resultado do RBF Regressor no Weka que está abaixo:
=== Run information === Scheme: weka.classifiers.functions.RBFClassifier -N 2 -R 0.01 -L 1.0E-6 -C 1 -G -A -P 1 -E 1 -S 1 Relation: WekaExcel-weka.filters.unsupervised.attribute.Remove-R8-weka.filters.unsupervised.attribute.Remove-R1, 6-weka.filters.unsupervised.attribute.Remove-R5 Instances: 671 Attributes: 5 Var1 Var2 Var3 Var4 Paid Test mode: evaluate on training data === Classifier model (full training set) === Output weights for different classes: -0.658867061591664 0.7268781531574563 Unit center: 1.103191478913074 0.3187908580844808 1.339867551710916 -2.348360195617461 Output weights for different classes: 7.294836535867017 -7.294947917203681 Unit center: 0.001306958680758934 -0.001914844611731498 6.641791379162694E-4 1.0009616503748857 Scale: 0.7556789838127707 Attribute weights: 1.2177544598559824 1.0557440195728327 1.6425390340750194 3.7580013072113965 Bias weights for different classes: -1.1716428958295801 1.171406635309079 Time taken to build model: 0.33 seconds
Até aí nada demais, basta ver qual é o teste dos coeficientes regressores e substituir os coeficientes para posteriormente realizar o cálculo, certo?
Até aí perfeito, mas tem um pequeno problema: todas as variáveis do modelo são nominais e o classificador já fez a normalização os dados. Ou seja, neste exato momento você transformou o modelo em black box, mesmo com todos os coeficientes expostos. Ou seja, a transparência do modelo foi trocada pelo fato da não normalização dos dados.
Neste segundo exemplo vamos ver o resultado de uma RBFNetwork no Weka.
=== Classifier model (full training set) ===
Radial basis function network
(Linear regression applied to K-means clusters as basis functions):
Linear Regression Model
Dummy_Paid =
-0.2146 * pCluster_0_0 +
0.2148 * pCluster_0_1 +
0.612
Neste caso, estou ainda com as mesmas variáveis nominais.
Uma das propriedades da RBFNetwork no Weka, é que a grosso modo o algoritmo permite a escolha do número de clusters e porteriormente implementa uma função de base radial (i.e. realiza a atribuição de valores partindo do distanciamento de um centro) para realizar a classificação.
Abaixo a descrição do algoritmo:
NAME
weka.classifiers.functions.RBFNetwork
SYNOPSIS
Class that implements a normalized Gaussian radial basisbasis function network.
It uses the k-means clustering algorithm to provide the basis functions and learns either a logistic regression (discrete class problems) or linear regression (numeric class problems) on top of that. Symmetric multivariate Gaussians are fit to the data from each cluster. If the class is nominal it uses the given number of clusters per class. It standardizes all numeric attributes to zero mean and unit variance.
OPTIONS
debug -- If set to true, classifier may output additional info to the console.
ridge -- Set the Ridge value for the logistic or linear regression.
maxIts -- Maximum number of iterations for the logistic regression to perform. Only applied to discrete class problems.
clusteringSeed -- The random seed to pass on to K-means.
minStdDev -- Sets the minimum standard deviation for the clusters.
numClusters -- The number of clusters for K-Means to generate.
A frase mais importante é “It standardizes all numeric attributes to zero mean and unit variance.”
Sabendo isto, rodei o meu experimento com os seguintes parâmetros.
Nesta imagem, como tinha controle do pré-processamento dos dados propositalmente coloquei a variável de decisão como a geradora dos centroides dos dois clusters. Após isso fiz uma pergunta ao Eibe Frank que é um dos desenvolvedores do Weka sobre o testes dos coeficientes do Output e obtive a seguinte resposta:
pCluster_0_0 and pCluster_0_1 are cluster membership probabilities. RBFNetwork internally uses clusters build using SimpleKMeans. They are not output, so you can’t manually reproduce the classifications generated by RBFNetwork.
Cheers,
Eibe
Ou seja, se não tivesse inserido (ou mesmo a percepção do que o algoritmo fazia) a minha variável de decisão, jamais saberia como o algoritmo chegou ao resultado.
Neste caso o pré-processamento foi feito de uma maneira reprodutível, ou no mínimo rastreável o que ajudou na compreensão do modelo, e de quebra me permitiu ganhar um midset para trabalhar com problemas de função de base radial e clustering. Mais um item no cinto de utilidades do batman minerador de dados.
O grande aprendizado é que quem tem o controle do pré-processamento tem o controle do modelo, seja na velocidade de execução do algoritmo, como também exerce influência nos resultados do modelo. Então, não terceirize a normalização de dados.
FONTES
http://stn.spotfire.com/spotfire_client_help/norm/norm_scale_between_0_and_1.htm
http://stats.stackexchange.com/questions/70801/how-to-normalize-data-to-0-1-range
Análise de Whiskies usando K-Means
Com isso a geração dos resultados e da análise ficam muito mais ‘walk-thru’ e muito menos black-box.
O resultado final?
“[…]The results indicate that there is a lot of variation in flavor profiles within the different scotch whisky regions. Note that initial cluster centers are chosen at random. In order to replicate the results, you will need to run the following code before your analysis.
set.seed(1) Further data analysis would be required to determine whether proximity to types of water sources or terrain types drive common flavor profiles. This could be done by obtaining shape files and adding them as an additional layer to the ggmap plot.
For me, I have identified my next to-try single malt. Talisker is still within the familiar realm of cluster 4 but a little more malty, fruity and spicy. Sounds like the perfect holiday mix. […]”
Predição de Movimentações Criminais
Tutorial sobre Vector Quantization
Para quem quer saber o que é Vector Quantization nos vídeos abaixo tem um tutorial.
Reverse Clustering
Análise de Cluster com dados de Baseball com WEKA
Um estudo bacana do Peter Hauck de como utilizar o WEKA para análise de dados esportivos.
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
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.
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.
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.
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.
Estudo comparativo entre algoritmos de Análise de Agrupamentos em Data Mining – Fernando Prass
Um dos meus referenciais sobre os estudos em Mineração de Dados foram os trabalhos no blog do Msc. Fernando Prass, no qual ele reuniu dois atributos importantissímos para explicação de uma técnica tão importante 1) simplicidade na abordagem e 2) ausência de ‘lugares comuns’ na abordagem de literatura.
Nessa dissertação de mestrado ele aborda os aspectos comparativos entre os mais diversos algorítmos de agrupamento; e recomendo fortemente a leitura para quem deseja pesquisar mais a fundo essa ramificação da mineração de dados.
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.
