High Dimensional Data Clustering

Grande parte dos avanços em Machine Learning que ocorreram nos últimos 10 anos foram bastante relacionados com alguns aspectos que são:

  1. Algoritmos mais robustos em termos de acurácia (XGBoost);
  2. Métodos Ensemble para a combinação de algoritmos; e
  3. Incorporação de metaheurísticas para melhoria em termos de tempo processamento e otimização de parâmetros

Contudo, um dos aspectos em que ainda há um caminho longo para evolução é em relação ao tratamento de dados com alta dimensionalidade (e.g. com muitos atributos, ou colunas se estivéssemos falando de banco de dados) dado que dependendo desse volume o tempo de processamento torna-se proibitivo.

Isso de maneira geral é um problema essencialmente algorítmico do que computacional.

Muitas técnicas vem se destacando para tratar dessa limitação como Rough Sets, PCA, LDA entre outras, em que o produto final da aplicação de cada uma dessas técnicas é um conjunto de dados menor, o que consequentemente causa uma perda de informação.

Esse artigo abaixo trata de uma forma de lidar com esse problema, sem ter que limitar o conjunto de dados.

É de extrema importância para todos que tenham que lidar com esse tipo de problema em Machine Learning.

High Dimensional Data Clustering

Summary. Clustering in high-dimensional spaces is a recurrent problem in many domains, for example in object recognition. High-dimensional data usually live in different lowdimensional subspaces hidden in the original space. This paper presents a clustering approach which estimates the specific subspace and the intrinsic dimension of each class. Our approach adapts the Gaussian mixture model framework to high-dimensional data and estimates the parameters which best fit the data. We obtain a robust clustering method called HighDimensional Data Clustering (HDDC). We apply HDDC to locate objects in natural images in a probabilistic framework. Experiments on a recently proposed database demonstrate the effectiveness of our clustering method for category localization.

High Dimensional Data Clustering

High Dimensional Data Clustering

7 técnicas para redução da dimensionalidade

Na atual era do Big Data em que o custo de armazenamento praticamente foi levado ao nível de commodity, muitas corporações que se gabam que são ‘adeptas’ do Big Data acabam pagando/armazenando ruído ao invés de sinal.

Pelo motivo exposto acima, diante do prisma de Engenharia de Dados o problema de absorção/retenção dessas informações está resolvido.

No entanto, quando é necessário escalar negócios através de inteligência usando os dados (lembrando o que foi dito no passado: Dado > Informação > Conhecimento > Sabedoria) o que era uma característica inerente ao avanço tecnológico de engenharia de dados, torna-se um problema gigante dentro da ciência de dados.

Com esse aumento horizontal das bases de dados (dimensões / atributos) um problema grave é o aumento da dimensionalidade (Course of Dimensionality) em que temos não somente multicolinearidade, heteroscedasticidade e autocorreação para ficar em exemplos estatísticos simples.  Em termos computacionais nem é preciso dizer que o aumento de atributos faz com que os algoritmos de Data Mining ou Inteligência Computacional tenham que processar um volume de dados muito maior (aumento da complexidade do processamento = maior custo temporal).

Dada essa pequena introdução, essa é a razão na qual a redução da dimensionalidade é muito importante para qualquer data miner.

Esse post da Knime apresenta 7 técnicas para redução da dimensionalidade, que são:

Missing Values Ratio. Data columns with too many missing values are unlikely to carry much useful information. Thus data columns with number of missing values greater than a given threshold can be removed. The higher the threshold, the more aggressive the reduction.

Low Variance Filter. Similarly to the previous technique, data columns with little changes in the data carry little information. Thus all data columns with variance lower than a given threshold are removed. A word of caution: variance is range dependent; therefore normalization is required before applying this technique.

High Correlation Filter. Data columns with very similar trends are also likely to carry very similar information. In this case, only one of them will suffice to feed the machine learning model. Here we calculate the correlation coefficient between numerical columns and between nominal columns as the Pearson’s Product Moment Coefficient and the Pearson’s chi square value respectively. Pairs of columns with correlation coefficient higher than a threshold are reduced to only one. A word of caution: correlation is scale sensitive; therefore column normalization is required for a meaningful correlation comparison.

– Random Forests / Ensemble Trees. Decision Tree Ensembles, also referred to as random forests, are useful for feature selection in addition to being effective classifiers. One approach to dimensionality reduction is to generate a large and carefully constructed set of trees against a target attribute and then use each attribute’s usage statistics to find the most informative subset of features. Specifically, we can generate a large set (2000) of very shallow trees (2 levels), with each tree being trained on a small fraction (3) of the total number of attributes. If an attribute is often selected as best split, it is most likely an informative feature to retain. A score calculated on the attribute usage statistics in the random forest tells us ‒ relative to the other attributes ‒ which are the most predictive attributes.

Principal Component Analysis (PCA). Principal Component Analysis (PCA) is a statistical procedure that orthogonally transforms the original n coordinates of a data set into a new set of n coordinates called principal components. As a result of the transformation, the first principal component has the largest possible variance; each succeeding component has the highest possible variance under the constraint that it is orthogonal to (i.e., uncorrelated with) the preceding components. Keeping only the first m < n components reduces the data dimensionality while retaining most of the data information, i.e. the variation in the data. Notice that the PCA transformation is sensitive to the relative scaling of the original variables. Data column ranges need to be normalized before applying PCA. Also notice that the new coordinates (PCs) are not real system-produced variables anymore. Applying PCA to your data set loses its interpretability. If interpretability of the results is important for your analysis, PCA is not the transformation for your project.

Backward Feature Elimination. In this technique, at a given iteration, the selected classification algorithm is trained on n input features. Then we remove one input feature at a time and train the same model on n-1 input features n times. The input feature whose removal has produced the smallest increase in the error rate is removed, leaving us with n-1 input features. The classification is then repeated using n-2 features, and so on. Each iteration k produces a model trained on n-k features and an error rate e(k). Selecting the maximum tolerable error rate, we define the smallest number of features necessary to reach that classification performance with the selected machine learning algorithm.

– Forward Feature Construction. This is the inverse process to the Backward Feature Elimination. We start with 1 feature only, progressively adding 1 feature at a time, i.e. the feature that produces the highest increase in performance. Both algorithms, Backward Feature Elimination and Forward Feature Construction, are quite time and computationally expensive. They are practically only applicable to a data set with an already relatively low number of input columns.

Os resultados obtidos em termos de acurácia foram:

dimensionality_reduction

Alguns insights em relação aos resultados:

  • Apesar da robustez matemática, o PCA apresenta um resultado não tão satisfatório em relação a métodos mais simples de seleção de atributos. Isso pode indicar que esse método não lida tão bem com bases de dados com inconsistências.
  • Filtro de baixa variância e de valores faltantes são técnicas absolutamente simples e tiveram o mesmo resultado de técnicas algoritmicamente mais complexas como Florestas Aleatórias.
  • Construção de modelos com inclusão incremental de atributos e eliminação de atributos retroativa são métodos que apresentam uma menor performance e são proibitivos em termos de processamento.
  • A estatística básica ainda é uma grande ferramenta para qualquer data miner, e não somente ajuda em termos de redução do custo temporal (processamento) quanto em custo espacial (custo de armazenamento).

A metodologia do estudo pode ser encontrada abaixo.

knime_seventechniquesdatadimreduction

7 técnicas para redução da dimensionalidade

Estudo Comparativo entre SVM em Bases de Dados com Alta Dimensionalidade

Estudo Comparativo entre SVM em Bases de Dados com Alta Dimensionalidade

Comparação das técnicas de aprendizado de máquina para previsão de sobrevivência em Câncer de Mama

Um ótimo estudo do BioDataMining que poderia ser reproduzido aqui em terra brasilis. Uma crítica que eu vejo nesse trabalho foi que a seleção de atributos como diria o Daniel Larose foi um pouco black-box e particularmente a abordagem em Algoritmos Genéticos não deve ser tão performática em relação a SVM (o ponto dos autores é que os dados tinha uma dimensionalidade razoável).

A comparison of machine learning techniques for survival prediction in breast cancer

Comparação das técnicas de aprendizado de máquina para previsão de sobrevivência em Câncer de Mama

Data analysis recipes: Fitting a model to data

Para quem deseja um overview sobre fitting de modelos e entender um pouco sobre questões como variância, esse artigo de David Hogg, Jo Bovy, Dustin Lang é uma leitura bem interessante.

Abstract

We go through the many considerations involved in fitting a model to data, using as an example the fit of a straight line to a set of points in a two-dimensional plane. Standard weighted least-squares fitting is only appropriate when there is a dimension along which the data points have negligible uncertainties, and another along which all the uncertainties can be described by Gaussians of known variance; these conditions are rarely met in practice. We consider cases of general, heterogeneous, and arbitrarily covariant two-dimensional uncertainties, and situations in  which there are bad data (large outliers), unknown uncertainties, and unknown but expected intrinsic scatter in the linear relationship being fit.

Above all we emphasize the importance of having a “generative model” for the data, even an approximate one. Once there is a generative model, the subsequent fitting is non-arbitrary because the model permits direct computation of the likelihood of the parameters or the posterior probability distribution. Construction of a posterior probability distribution is indispensible if there are “nuisance parameters” to marginalize away.

 Data analysis recipes – Fitting a Model to Data

 

Data analysis recipes: Fitting a model to data

Técnicas de Detecção de Outliers

Essa apresentação de Hans-Peter Kriegel apresenta um pequeno tutorial sobre as técnicas de detecção de anomalias em mineração de dados (Outliers); no qual esses slides apresentam algumas das tecnicas mais populares, indo desde testes estatísticos, até abordagens de detecção de anomalias utilizando modelos com alta dimensionalidade.

Link – http://www.dbs.ifi.lmu.de/~zimek/publications/KDD2010/kdd10-outlier-tutorial.pdf

Outlier Detection Techniques

Técnicas de Detecção de Outliers