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.

Árvore de Decisão para Aplicação de Técnicas de Data Mining

Este é um poster do Scikit, e foi tirado diretamente do Mahbabe.

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:

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

Uma ótima análise usando K-Means com o R. Mais do que a análise, esse post é uma aula de como proceder com uma análise de cluster usando a determinação arbitrária de clusters como o K-means exige.

Com isso a geração dos resultados e da análise ficam muito mais ‘walk-thru’ e muito menos black-box.

“[…]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. […]”

Tutorial sobre Vector Quantization

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

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.

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.

Application of data mining techniques in stock markets

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

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.

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.