1、Data Mining and Model Choice in Supervised Learning,Gilbert Saporta Chaire de Statistique Applique & CEDRIC, CNAM, 292 rue Saint Martin, F-75003 Parisgilbert.saportacnam.fr http:/am.fr/saporta,Beijing, 2008,2,Outline,What is data mining? Association rule discovery Statistical models Predictive model
2、ling A scoring case study Discussion,Beijing, 2008,3,1. What is data mining?,Data mining is a new field at the frontiers of statistics and information technologies (database management, artificial intelligence, machine learning, etc.) which aims at discovering structures and patterns in large data s
3、ets.,Beijing, 2008,4,1.1 Definitions:,U.M.Fayyad, G.Piatetski-Shapiro : “ Data Mining is the nontrivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data ” D.J.Hand : “ I shall define Data Mining as the discovery of interesting, unexpected, or va
4、luable structures in large data sets”,Beijing, 2008,5,The metaphor of Data Mining means that there are treasures (or nuggets) hidden under mountains of data, which may be discovered by specific tools. Data Mining is concerned with data which were collected for another purpose: it is a secondary anal
5、ysis of data bases that are collected Not Primarily For Analysis, but for the management of individual cases (Kardaun, T.Alanko,1998) . Data Mining is not concerned with efficient methods for collecting data such as surveys and experimental designs (Hand, 2000),Beijing, 2008,6,The idea of discoverin
6、g facts from data is as old as Statistics which “ is the science of learning from data ” (J.Kettenring, former ASA president). In the 60s: Exploratory Data Analysis (Tukey, Benzecri) Data analysis is a tool for extracting the diamond of truth from the mud of data. (J.P.Benzcri 1973),What is new? Is
7、it a revolution ?,Beijing, 2008,7,1.2 Data Mining started from:,an evolution of DBMS towards Decision Support Systems using a Data Warehouse. Storage of huge data sets: credit card transactions, phone calls, supermarket bills: giga and terabytes of data are collected automatically. Marketing operati
8、ons: CRM (customer relationship management) Research in Artificial Intelligence, machine learning, KDD for Knowledge Discovery in Data Bases,Beijing, 2008,8,1.3 Goals and tools,Data Mining is a secondary analysis of data collected in an other purpose (management eg) Data Mining aims at finding struc
9、tures of two kinds : models and patternsPatterns a characteristic structure exhibited by a few number of points : a small subgroup of customers with a high commercial value, or conversely highly risked. Tools: cluster analysis, visualisation by dimension reduction: PCA, CA etc. association rules.,Be
10、ijing, 2008,9,ModelsBuilding models is a major activity for statisticians econometricians, and other scientists. A model is a global summary of relationships between variables, which both helps to understand phenomenons and allows predictions. DM is not concerned with estimation and tests, of prespe
11、cified models, but with discovering models through an algorithmic search process exploring linear and non-linear models, explicit or not: neural networks, decision trees, Support Vector Machines, logistic regression, graphical models etc. In DM Models do not come from a theory, but from data explora
12、tion.,Beijing, 2008,10,process or tools?,DM often appears as a collection of tools presented usually in one package, in such a way that several techniques may be compared on the same data-set. But DM is a process, not only tools:Data Information Knowledge,preprocessing,analysis,Beijing, 2008,11,2. A
13、ssociation rule discovery, or market basket analysis,Illustration with a real industrial example at Peugeot-Citroen car manufacturing company. (Ph.D of Marie Plasse).,ASSOCIATION RULES MINING,“90% of transactions that purchase bread and butter,also purchase milk“ (Agrawal et al., 1993), bread, butte
14、r ,milk ,antecedent,consequent,where A C = ,Itemset A,Itemset C,Supp = 30 % 30% of transactions contain + +,Conf = 90 % 90% of transactions that contain + , contain also,Beijing, 2008,14,Support: P(AC) Confidence: P(C/A) thresholds s0 et c0 Interesting result only if P(C/A) is much larger than P(C)
15、or P(C/not A) is low. Lift:,MOTIVATION,Motivation : decision-making aid Always searching for a greater quality level, the car manufacturer can take advantage of knowledge of associations between attributes.,Industrial data : A set of vehicles described by a large set of binary flags,Our work : We ar
16、e looking for patterns in data : Associations discovery,Vehicles,DATA FEATURE,Data size : More than 80 000 vehicles (transactions) 4 months of manufacturing More than 3000 attributes (items),DATA FEATURE,Count of attributes owned by vehicle,Vehicle Percent,OUPUT : ASSOCIATION RULES,Aims : Reduce cou
17、nt of rules Reduce size of rules,A first reduction is obtained by manual grouping :,COMBINING CLUSTER ANALYSIS AND ASSOCIATION RULES,10-clusters partition with hierarchical clustering and Russel Rao coefficient,Cluster 2 is atypical and produces many complex rules,Mining association rules inside eac
18、h cluster except atypical cluster :,The number of rules to analyse has significantly decreased The output rules are more simple to analyse Clustering has detected an atypical cluster of attributes to treat separately,Beijing, 2008,21,3.Statistical models,About statistical modelsUnsupervised case: a
19、representation of a probabilisable real world: X r.v. parametric family f(x;)Supervised case: response Y=(X)+ Different goals Unsupervised: good fit with parsimony Supervised: accurate predictions,Beijing, 2008,22,3.1. Model choice and penalized likelihood,The likelihood principle (Fisher, 1920)samp
20、le of n iid observations:The best model is the one which maximizes the likelihood, ie the probability of having observed the data. ML estimation etc.,Beijing, 2008,23,Overfitting risk,Likelihood increases with the number of parameters Variable selection: a particular case of model selection Need for
21、 parsimony Occams razor,Beijing, 2008,24,An English Franciscan friar and scholastic philosopher. He was summoned to Avignon in 1324 by Pope John XXII on accusation of heresy, and spent four years there in effect under house arrest. William of Ockham has inspired in U.Ecos The Name of the Rose, the m
22、onastic detective William of Baskerville, who uses logic in a similar manner. Occams razor states that the explanation of any phenomenon should make as few assumptions as possible, eliminating, or “shaving off“, those that make no difference in the observable predictions of the explanatory hypothesi
23、s or theory. lex parsimoniae : entia non sunt multiplicanda praeter necessitatem, or: entities should not be multiplied beyond necessity.,William of Occham(12851348),from wikipedia,Beijing, 2008,25,penalized likelihood,Nested (?) family of parametric models, with k parameters: trade-off between the
24、fit and the complexity Akake : AIC = -2 ln(L) + 2k Schwartz : BIC = -2 ln(L) + k ln(n)Choose the model which minimizes AIC or BIC,Beijing, 2008,26,3.2 AIC and BIC: different theories,AIC : approximation of Kullback-Leibler divergence between the true model and the best choice inside the family,Beiji
25、ng, 2008,27,AIC and BIC: different theories,BIC : bayesian choice between m models Mi . For each model P(i / Mi). The posterior probability of Mi knowing the data x is proportional to P(Mi) P(x/Mi). With equal priors P(Mi): The most probable model Mi a posteriori is the one with minimal BIC.,Beijing
26、, 2008,28,AIC and BIC: different uses,BIC favourises more parsimonious models than AIC due to its penalization AIC (not BIC) is biased : if the true model belongs to the family Mi , the probability that AIC chooses the true model does not tend to one when the number of observations goes to infinity.
27、 It is inconsistent to use AIC and BIC simultaneously Other penalisations such astheory?,Beijing, 2008,29,3.3 Limitations,Refers to a “true” which generally does not exist, especially if n tends to infinity. “Essentially, all models are wrong, but some are useful ” G.Box (1987) Penalized likelihood
28、cannot be computed for many models: Decision trees, neural networks, ridge and PLS regression etc. No likelihood, which number of parameters?,Beijing, 2008,30,4. Predictive modelling,In Data Mining applications (CRM, credit scoring etc.) models are used to make predictions. Model efficiency: capacit
29、y to make good predictions and not only to fit to the data (forecasting instead of backforecasting: in other words it is the future and not the past which has to be predicted).,Beijing, 2008,31,Classical framework Underlying theory Narrow set of models Focus on parameter estimation and goodness of f
30、it Error: white noise,Data mining context Models come from data Algorithmic models Focus on control of generalization error Error: minimal,Beijing, 2008,32,The black-box problem and supervised learning (N.Wiener, V.Vapnik),Given an input x, a non-deterministic system gives a variable y = f(x)+e. Fro
31、m n pairs (xi,yi) one looks for a function which approximates the unknown function f. Two conceptions: A good approximation is a function close to f A good approximation is a function which has an error rate close to the black box, ie which performs as well,Beijing, 2008,33,4.1 Model choice and Stat
32、istical Learning Theory,How to choose a model in a family of models (eg: degree of a polynomial regression)?,A too complex model: too good fit,A too simple (but robust) model: bad fit,Beijing, 2008,34,4.2 Model complexity and prediction error,Beijing, 2008,35,Model complexity,The more complex a mode
33、l, the better the fit but with a high prediction variance. Optimal choice: trade-off But how can we measure the complexity of a model?,Beijing, 2008,36,4.3 Vapnik-Cervonenkis dimension for binary supervised classification,A measure of complexity related to the separating capacity of a family of clas
34、sifiers. Maximum number of points which can be separated by the family of functions whatever are their labels 1,Beijing, 2008,37,Example,In 2-D, the VC dimension of “free” linear classifiers is 3 (in p-D VCdim=p+1),Beijing, 2008,38,But VC dimension is NOT equal to the number of free parameters: can
35、be more or less The VC dimension of f(x,w) = sign (sin (w.x) ) c 0, with only one parameter w is infinite. Hastie et al. 2001,Beijing, 2008,39,Consistent learning,Non consistent learning,n,Generalization error,h must be finite,Vapniks inequality,Beijing, 2008,40,4.4 Model choice by Structural Risk M
36、inimization (SRM),Vapniks inequality:Comments: the complexity of a family of models may increase when n increases, provided h is finite Small values of h gives a small difference between R and Remp . It explains why regularized (ridge) regression, as well as dimension reduction techniques, provide b
37、etter results in generalisation than ordinary least squares.,Beijing, 2008,41,With SRM, instead of minimizing R, one minimizes the upper bound: Remp + confidence interval. For any distribution , SRM provides the best solution with probability 1 (universally strong consistency) Devroye (1996) Vapnik
38、(2006).,Beijing, 2008,42,4.5 High dimensional problems and regularization,Many ill-posed problems in applications (eg genomics) where pn In statistics (LS estimation) Tikhonov regularization = ridge regression; a constrained solution of Af= F under (f)c (convex and compact set)Other techniques: proj
39、ection onto a low dimensional subspace: principal components (PCR), partial least squares regression (PLS), support vector machines (SVM),Beijing, 2008,43,Ridge regression,the VC dimension of subject to: may be far lower than p+1:,Beijing, 2008,44,Since Vapniks inequality is an universal one, the up
40、per bound may be too large. Exact VC-dimension are very difficult to obtain, and in the best case, one only knows bounds But even if the previous inequality is not directly applicable, SRM theory proved that the complexity differs from the number of parameters, and gives a way to handle methods wher
41、e penalized likelihood is not applicable.,Beijing, 2008,45,Empirical model choice,The 3 samples procedure (Hastie & al., 2001) Learning set: estimates model parameters Test : selection of the best model Validation : estimates the performance for future data Resample (eg: bootstrap, 10-fold CV, ) Fin
42、al model : with all available data Estimating model performance is different from estimating the model,Beijing, 2008,46,5. A scoring case study,Beijing, 2008,47,An insurance example,1106 belgian automobile insurance contracts :2 groups: 1 good , 2 bad 9 predictors: 20 categories Use type(2), gender(
43、3), language (2), agegroup (3), region (2), bonus-malus (2), horsepower (2), duration (2), age of vehicle (2),Beijing, 2008,48,Principal plane MCA,Beijing, 2008,49,Fishers LDAFACTORS CORRELATIONS LOADINGS 1 F 1 0.719 6.90642 F 2 0.055 0.7149 3 F 3 -0.078 -0.82114 F 4 -0.030 -0.46155 F 5 0.083 1.2581
44、6 F 6 0.064 1.02747 F 7 -0.001 0.21698 F 8 0.090 1.31339 F 9 -0.074 -1.1383 10 F 10 -0.150 -3.3193 11 F 11 -0.056 -1.4830 INTERCEPT 0.093575 R2 = 0.57923 F = 91.35686 D2 = 5.49176 T2 = 1018.69159 ,Score= 6.90 F1 - 0.82 F3 + 1.25 F5 + 1.31 F8 - 1.13 F9 - 3.31 F10,Beijing, 2008,50,Transforming scores
45、Standardisation between 0 and 1000 is often convenient Linear transformation of score implies the same transformation for the cut-off point,Beijing, 2008,51,Scorecard,Beijing, 2008,52,LDA and logistic regression,Changing priors changes the constant term in the score function Previous formula: LDA wi
46、th normality and equal covariance matrices, the model in logistic regression.Estimation techniques differ: least squares in LDA , conditional maximum likelihood in logistic regression.,Beijing, 2008,53,LDA and logistic,The probabilistic assumptions of logistic regression seem less restrictive than t
47、hose of discriminant analysis, but discriminant analysis also has a strong non-probabilistic background being defined as the least-squares separating hyperplane between classes.,Beijing, 2008,54,Performance measures for supervised binary classification,Misclassification rate or score performance? Er
48、ror rate implies a strict decision rule. Scores A score is a rating: the threshold is chosen by the end-user Probability P(G1/x): also a score ranging from 0 to 1. Almost any technique gives a score.,Beijing, 2008,55,ROC curve and AUC,A synthesis of score performance for any threshold s . x is class
49、ified in group 1 if S(x) s Using s as a parameter, the ROC curve links the true positive rate 1- to the false positive rate .,Beijing, 2008,56,ROC curve and AUC,AUC : area under curve Probability of concordance P(X1X2) Estimated by the proportion of concordant pairs among n1n2 Related to Mann-Whitneys U statistic : AUC = U/n1n2,
