Clustering tree (slides)

The clustering tree algorithm is both a clustering approach and a multi-objective supervised learning method.

In the cluster analysis framework, the aim is to group objects in clusters, where the objects in the same cluster are similar in a certain sense. The clustering tree algorithm enables to perform this kind of task. We obtain a decision tree as a clustering structure. Thus, the deployment of the classification rule in the information system is really easy.

But we can also consider the clustering tree as an extension of the classification/regression tree because we can distinguish two set of variables: the explained (active) variables which are used to determine the similarities between the objects; the predictive (illustrative) variables which allows to describe the groups.

In this slides, we show the main features of this approach.

Keywords: cluster analysis, clustering, clustering tree, groups characterization
Slides: Clustering tree
References :
M. Chavent (1998), « A monothetic clustering method », Pattern Recognition Letters, 19, 989—996.
H. Blockeel, L. De Raedt, J. Ramon (1998), « Top-Down Induction of Clustering Trees », ICML, 55—63. 

Sipina - Version 3.12

The transfer between the Excel spreadsheet and Sipina was improved on the databases of moderate size (on large databases, several hundreds of thousands of rows, it is better to perform a direct importation of data file in text format TXT). The management of the decimal point has been improved. Now, the automatic processing is much faster than before.

The precision of the numerical cut points displayed in a decision tree becomes customizable. The users dispose of a new item into the menu "Tree Management".

Sipina website: Sipina
Download: Setup file

Binary classification via regression (slides)

In these slides, we study the analogy between the linear discriminant analysis and the regression on an indicator variable when we deal with a binary classification problem.

The tests for the global significance of the model and the individual significance of the coefficients are equivalent. The coefficients are proportional, including the intercepts when we treat the balanced case. In the other case (unbalanced classes), an additional correction of the regression intercept is needed to obtain the linear discriminant analysis intercept.

For the multiclass classification, the equivalence between the regression and the linear discriminant analysis is no longer valid.

Keywords: supervised learning, linear discriminant analysis, multiple linear regression, R2, wilks lambda
Slides: Classification via regression
References :
R.O. Duda, P.E. Hart, D. Stork, « Pattern Classification », 2nd Edition, Wiley, 2000.
C.J. Huberty, S. Olejnik, « Applied MANOVA and Discriminant Analysis »,Wiley, 2006.

Naive Bayes classifier (slides)

Here are the slides I use for my course about “Naive Bayes Classifier”. The main originality of this presentation is that I show it is possible to extract an explicit model based on the calculations of the conditional distributions. This makes highly easier the deployment of the model in real case studies. This aspect is commonly unknown. The feature selection problem in the context of Naive Bayes Classifier learning is also highlighted.

Keywords: machine learning, supervised methods, naive bayes, independence assumption, independent feature model, feature selection, cfs
Slides: Naive Bayes classifier
References:
T. Mitchell, "Generative and discriminative classifiers: naive bayes and logistic regression", in "Machine Learning", McGraw Hill, 2010; Draft of January 2010.
Wikipedia, "Naive Bayes classifier".

Linear discriminant analysis (slides)

Here are the slides I use for my course about “Linear Discriminant Analysis” (LDA). The two main assumptions which enable to obtain a linear classifier are highlighted. The LDA is very interesting because we can interpret the classifier in different ways: it is a parametric method based on the MAP (maximum a posteriori) decision rule; it is a classifier based on a distance to the conditional centroids; it is a linear separator which defines various regions in the representation space.

Statistical tools for the overall model evaluation and the checking of the relevance of the predictive variables are presented.

Keywords: machine learning, supervised methods, discriminant analysis, predictive discriminant analysis, linear discriminant analysis, linear classification functions, wilks lambda, stepdisc, feature selection
Slides: linear discriminant analysis
References:
J. Gareth, D. Witten, T. Hastie, R. Tibshirani, "An introduction to statistical learning with applications in R", Springer, 2013.
R. Duda, P. Hart, G. Stork, "Pattern Classification", Wiley, 2000.

Regression Trees

Here are the slides I use for my course about “Regression Trees”. Because this course comes after the one about “Decision Trees”, only the special features for the handling of a continuous target attribute are highlighted. The described algorithms correspond roughly to the AID and the CART approaches.

Keywords: machine learning, supervised methods, regression tree, aid, cart, continuous class attribute
Slides: regression trees
References:
L. Breiman, J. Friedman, R. Olshen and C. Stone, “Classification and Regression Trees”, Wadsworth Int. Group, 1984.
J. Morgan, J.A. Sonquist, "Problems in the Analysis of Survey Data and a Proposal", JASA, 58:415-435, 1963.

Decision tree learning algorithms

Here are the slides I use for my course about the existing decision tree learning algorithms. Only the most popular ones are described: C4.5, CART and CHAID (a variant). The differences between these approaches are highlighted according: the splitting measure; the merging strategy during the splitting process; the approach for determining the right sized tree.

Keywords: machine learning, supervised methods, decision tree learning, classification tree, chaid, cart, c4.5
Slides: C4.5, CART and CHAID
References:
L. Breiman, J. Friedman, R. Olshen and C. Stone, “Classification and Regression Trees”, Wadsworth Int. Group, 1984.
G. Kass, “An exploratory technique for Investigating Large Quantities of Categorical Data”, Applied Statistics, 29(2), 1980, pp. 119-127.
R. Quinlan, “C4.5: Programs for machine learning”, Morgan Kaufman, 1993.

Introduction to Decision Trees

Here are the lecture notes I use for my course “Introduction to Decision Trees”. The basic concepts of the decision tree algorithm are described. The underlying method is rather similar to the CHAID approach.

Keywords: machine learning, supervised methods, decision tree learning, classification tree
Slides: Introduction to Decision Trees
References:
T. Mitchell, "Decision Tree Learning", in "Machine Learning", McGraw Hill, 1997; Chapter 3, pp. 52-80.
L. Rokach, O. Maimon, "Decision Trees", in  "The Data Mining and Knowledge Discovery Handbook", Springer, 2005; Chapter 9, pp. 165-192.

Introduction to Supervised Learning

Here are the lecture notes I use for my course “Introduction to Supervised Learning”. The presentation is very simplified. But, all the important elements are described: the goal of the supervised learning process, the Bayes rule, the evaluation of the models using the confusion matrix.

Keywords: machine learning, supervised methods, model, classifier, target attribute, class attribute, input attributes, descriptors, bayes rule, confusion matrix, error rate, sensitivity, precision, specificity
Slides: Introduction to Supervised Learning
References:
O. Maimon, L. Rokach, "Introduction to Supervised Methods", in  "The Data Mining and Knowledge Discovery Handbook", Springer, 2005; Chapter 8, pp. 149-164.
T. Hastie, R. Tibshirani, J. Friedman, "The elements of Statistical Learning", Springer, 2009.

Cluster analysis for mixed data

The aim of clustering is to gather together the instances of a dataset in a set of groups. The instances in the same cluster are similar according a similarity (or dissimilarity) measure. The instances in distinct groups are different. The influence of the used measure, which is often a distance measure, is essential in this process. They are well known when we work on attributes with the same type. The Euclidian distance is often used when we deal with numeric variables; the chi-square distance is more appropriate when we deal with categorical variables. The problem is a lot of more complicated when we deal with a set of mixed data i.e. with both numeric and categorical values. It is admittedly possible to define a measure which handles simultaneously the two kinds of variables, but we have trouble with the weighting problem. We must define a weighting system which balances the influence of the attributes, indeed the results must not depend of the kind of the variables. This is not easy .

Previously we have studied the behavior of the factor analysis for mixed data (AFDM in French). This is a generalization of the principal component analysis which can handle both numeric and categorical variables . We can calculate, from a set of mixed variables, components which summarize the information available in the dataset. These components are a new set of numeric attributes. We can use them to perform the clustering analysis based on standard approaches for numeric values.

In this paper, we present a tandem analysis approach for the clustering of mixed data. First, we perform a factor analysis from the original set of variables, both numeric and categorical. Second, we launch the clustering algorithm on the most relevant factor scores. The main advantage is that we can use any type of clustering algorithm for numeric variables in the second phase. We expect also that by selecting a few number of components, we use the relevant information from the dataset, the results are more reliable .

We use Tanagra 1.4.49 and R (ade4 package) in this case study.

Keywords: AFDM, FAMD, factor analysis for mixed data, clustering, cluster analysis, hac, hierarchical agglomerative clustering, R software, hclust, ade4 package, dudi.mix, cutree, groups description
Components: AFDM, HAC, GROUP CHARACTERIZATION, SCATTERPLOT 
Tutorial: en_Tanagra_Clustering_Mixed_Data.pdf
Dataset: bank_clustering.zip
References:
Tanagra, "Factor Analysis for Mixed Data".
Jerome Pages, « Analyse Factorielle de Données Mixtes », Revue de Statistique Appliquee, tome 52, n°4, 2004 ; pages 93-111.

Scilab and R - Performance comparison

We have studied the Scilab tool in a data mining scheme in a previous tutorial . We noted that Scilab is well adapted for data mining. It is a credible alternative to R. But, we observed also that the available toolboxes for statistical processing and data mining are not very numerous compared to those of R. In this second tutorial, we evaluate the behavior of Scilab when we deal with a dataset with 500,000 instances and 22 attributes. We compare its performances with those of R. Two criteria are used: the memory occupation measured in the Windows task manager; the execution time at each step of the process.

It is not possible to obtain an exhaustive point of view. To delimit the scope of our study, we have specified a standard supervised learning scenario: loading a data file, building the predictive model with linear discriminant analysis approach, calculating the confusion matrix and resubstitution error rate. Of course, this study is incomplete. But it seems that Scilab is less efficient in the data management step. It is however quite efficient in the modeling step. This last assessment depends on the toolbox used.

Keywords: scilab, toolbox, nan, linear discriminant analysis, R software, sipina, tanagra
Tutorial: en_Tanagra_Scilab_R_Comparison.pdf
Dataset: waveform_scilab_r.zip
References:
Scilab - https://www.scilab.org/en
Michaël Baudin, "Introduction to Scilab (in French)", Developpez.com.

Data Mining with Scilab

I know the name "Scilab" for a long time (http://www.scilab.org/en). For me, it is a tool for numerical analysis. It seemed not interesting in the context of the statistical data processing and data mining. Recently a mathematician colleague spoke to me about this tool. He was surprised about the low visibility of Scilab within the data mining community, knowing that it proposes functionalities which are quite similar to those of R software. I confess that I did not know Scilab from this perspective. I decided to study Scilab by setting a basic goal: is it possible to perform simply a predictive analysis process with Scilab? Namely: loading a data file (learning sample), building a predictive model, obtaining a description of its characteristics, loading a test sample, applying the model on this second set of data, building the confusion matrix and calculating the test error rate.

We will see in this tutorial that the whole task has been completed successfully easily. Scilab is perfectly prepared to fulfill statistical treatments. But two small drawbacks appear during the catch in hand of Scilab: the library of statistical functions exists but it is not as comprehensive as that of R; their documentation is not very extensive at this time. However, I am very satisfied of this first experience. I discovered an excellent free tool, flexible and efficient, very easy to take in hand, which turns out a credible alternative to R in the field of data mining.

Keywords: scilab, toolbox, nan, libsvm, linear discriminant analysis, R software, predictive analytics
Tutorial : en_Tanagra_Scilab_Data_Mining.pdf
Dataset : data_mining_scilab.zip
References :
Scilab - https://www.scilab.org/fr
ATOMS : Homepage - http://atoms.scilab.org/

Tanagra, tenth anniversary

First of all, let me introduce you to all my wishes of happiness, health and success for the year 2014 which begins.

For Tanagra, 2014 is of quite particular importance. 10 Years ago almost to the day, the first version of the software has been put on line. Designed originally as a tool for the students and researchers in the data mining domain, the project has changed a bit of nature in recent years. Today, Tanagra is an academic project which provides a point of access to the statistical and the data mining techniques. It is addressed to students, but also to the researchers of other areas (psychology, sociology, archeology, etc.). It allows, I hope, make it more attractive, more clear, the implementation of these techniques on real case studies.

This mutation was accompanied by a refocusing of my activity. The Tanagra software is still evolving (we are at version 1.4.50), new methods are added, existing components are regularly improved, but at the same time I put emphasis on the documentation in the form of books, training materials and tutorials. The underlying idea is very simple: understanding the ins and outs of the methods is the best way to learn how to use software which proposes them.

Over the past 5 years (2009/01/01 to 2013/12/31), my site gets 677 visits per day. The 10 countries that come most often are: France, Morocco, Algeria, Tunisia, United States, India, Canada, Belgium, United Kingdom and Brazil. The page of the materials for my data mining courses is the most visited (http://eric.univ-lyon2.fr/~ricco/cours/supports_data_mining.html; 99 visits per day, 6 minutes 35 seconds average time spent on the page). At the same time, I note with great satisfaction that the English pages are overall as much visited as those in French. I think that the effort to write documentation in English is fruitful.

I hope that this work will be useful for a long time, and that 2014 will be the opportunity of exchanges always so rewarding for everybody.

Ricco.

Tanagra - Version 1.4.50

Improvements have been introduced, a new component is added.

HAC. Hierarchical agglomerative clustering. Computing time has been dramatically improved. We will detail the new procedure used in a new tutorial soon.

CATVARHAC. Classification of the levels of the nominal variables. The calculations are based on the work of Abdallah and Saporta (1998). The component performs an agglomerative hierarchical clustering of the levels of qualitative variables. The Dice's index is used as the distance measures. Several kind of linkage criteria are proposed: single linkage, complete linkage, average linkage, Ward's method. A tutorial will come to describe the method soon.

Download page : setup

Parallel programming in R

Personal computers become more and more efficient. They are mostly equipped with multi-core processors. At the same time, most of the data mining tools, free or not, are often based on single-threaded calculations. Only one core is used during calculations, while others remain inactive.

Previously, we have introduced two multithreaded variants of linear discriminant analysis in Sipina 3.10 and 3.11. During the analysis that allowed me to develop the solutions introduced in Sipina, I had much studied parallelization mechanisms available in other Data Mining Tools. They are rather scarce. I noted that highly sophisticated strategies are proposed for the R software. These are often environments that enable to develop programs for multi-core processors machines, multiprocessor machines, and even for computer cluster. I studied in particular the "parallel" package which is itself derived from 'snow' and 'multicore' packages. Let us be quite clear. The library cannot miraculously accelerate an existing procedure. It gives us the opportunity to effectively use the machines resources by rearranging properly the calculations. Basically, the idea is to break down the process into tasks that can be run in parallel. When these tasks are completed, we perform the consolidation.

In this tutorial, we detail the parallelization of the calculation of the within-class covariance matrix under R 3.0.0. In a first step, we describe single-threaded approach, but easily convertible i.e. the basic tasks are easily identifiable. As a second step, we use the tools of “parallel” and “doParallel” packages to run elementary tasks on the available cores. We will then compare the processing time. We note that, unlike the toy examples available on the web, the results are mixed. The bottleneck is the managing of the data when we handle a large dataset.

Keywords:  linear discriminant analysis, within-class covariance matrix, R software, parallel package, doparallel package, parLapply, mclapply, foreach
Didacticiel : en_Tanagra_Parallel_Programming_R.pdf
Fichiers :  parallel.R, multithreaded_lda.zip
Références :
R-core, Package 'parallel', April 18, 2013.