6.5.1.1 Best Linear Predictors

The estimation methodology used in the previous section is Ordinary Least Square (OLS) . We want to give a statistical definition of three important terms. This is important to make sure that even when we use these words loosely, we are aware what these terms mean.

• Bias of estimator : Bias of an estimator is the difference between estimator's expected value and the true value of the parameter being estimated. The estimator that has zero bias is desired for any model with unbiased estimators.

  This equation tells us that bias is the difference between the estimated value of a parameter and the true value. if the true value of parameter is 5 and the linear model estimated it to be 4.5, our estimator is biased by -0.5. This will cause consistent underprediction (biased prediction). The theorem says if the estimator is unbiased then its bias is equal to 0 for all values of parameter θ.

  The bias-variance tradeoff is discussed in Chapter 8.

• Consistent estimator : An estimator Tn of parameter θ is said to be consistent if it converges in probability to the true value of the parameter:

  Recall our discussion around CLT and LLN; we can rephrase this relationship:

  As n tends to infinity, the probability of the parameter estimate being different from the true value goes to zero. This means as we increase the training dataset, we expect that the parameter estimator value converges to the true value of the parameter.

• Efficient Estimator: An efficient estimator is an estimator that estimates its value in the best manner defined with respect to some loss/cost function. Generally, for the OLS framework, we say a estimator is efficient if it has bounded variance, i.e., variance with an upper limit:

where ℐ _θ is the Fisher information matrix of the model at point θ.

In regression, we want to minimize the variance (standard error) in our estimations of coefficients (parameters), so OLS provides us with an efficient estimator is it satisfies the Gauss-Markov theorem.

These three concepts can be extended to other modeling forms. These are important properties to be followed by our estimators to give a statistically significant model. We will now show the results for some of the important assumptions/properties we test for linear regression models.

6.5.4.1 Influential Point Analysis

In linear regression, extreme values can create issues in the estimation process. Few high leverage values introduce bias in the estimators and create other aberrations in the residuals. So it is important to identify influential points in data. If the influential points seem too extreme, we have to discard them from our analysis as outliers.

A specific statistical measure that we will show, among others, is Cook’s distance. This method is used to find an estimate of the influence data point when doing an OLS estimation.

Cook’s distance is defined as follows:
where is the mean squared error of the regression model and and

In simple terms, Cook's distance measures the effect of deleting a given observation. In this way, if removal of some observation causes significant changes, that means those points are influencing the regression model. These points are assigned a large value to Cook's distance and are considered for further investigation.

The cutoff value for this statistics can be taken as , where n is the number of observations. If you adjust for the number of parameters in the model, then the cutoff can be taken as , where k is the number of variables in the model.

library(car);
 Influential Observations
# Cook's D plot                    
# identify D values > 4/(n-k-1)                    
cutoff <-4/((nrow(Data_lm_Model)-length(fitted_Model_multiple$coefficients)-2))
plot(fitted_Model_multiple, which=4, cook.levels=cutoff)

The plot in Figure 6-17 shows the Cook’s distance for each observation in our dataset.

Figure 6-17. Cook’s distance for each observation

You can see the observation numbers with a high Cook’s distance are highlighted in the plot in Figure 6-17. These observations require further investigation.

# Influence Plot                    
influencePlot(fitted_Model_multiple,    id.method="identify", main="Influence Plot", sub="Circle size is proportional to Cook's Distance",id.location =FALSE)

The plot in Figure 6-18 shows a different view of Cook’s distance. The circle size is proportional to the Cook’s distance.

Figure 6-18. Influence plot

Also, the outlier test results are shown here:

#Outlier Plot                    
outlier.test(fitted_Model_multiple)
        rstudent unadjusted p-value Bonferonni p
 621  -14.285067         1.9651e-42   2.0987e-39
 229    8.259067         4.3857e-16   4.6839e-13
 564   -7.985171         3.6674e-15   3.9168e-12
 1023   7.902970         6.8545e-15   7.3206e-12
 718    5.040489         5.4665e-07   5.8382e-04
 799    4.925227         9.7837e-07   1.0449e-03
 235    4.916172         1.0236e-06   1.0932e-03
 487    4.673321         3.3491e-06   3.5768e-03
 530    4.479709         8.2943e-06   8.8583e-03

The observation numbers—342,621 and 102—as shown in Figure 6-18 (corresponding to HOUSE_ID 412, 759, and 1242) are the three main influence points . Let's pull out these records to see what values they have.

#Pull the records with highest leverage                    

Debug <-Data_lm_Model[c(342,621,1023),]

print(" The observed values for three high leverage points");
 [1] " The observed values for three high leverage points"
Debug
      HOUSE_ID HousePrice StoreArea StreetHouseFront BasementArea LawnArea
 342       412     375000       513              150         1236   215245
 621       759     160000      1418              313         5644    63887
 1023     1242     745000       813              160         2096    15623
      Rating     SaleType
 342       7     NewHouse
 621      10  FirstResale
 1023     10 SecondResale
print("Model fitted values for these high leverage points");
 [1] "Model fitted values for these high leverage points"
fitted_Model_multiple$fitted.values[c(342,621,1023)]
      342      621     1023
 441743.2 645975.9 439634.3
print("Summary of Observed values");                                                                                                              
 [1] "Summary of Observed values"
summary(Debug)
     HOUSE_ID        HousePrice       StoreArea      StreetHouseFront
  Min.   : 412.0   Min.   :160000   Min.   : 513.0   Min.   :150.0   
  1st Qu.: 585.5   1st Qu.:267500   1st Qu.: 663.0   1st Qu.:155.0   
  Median : 759.0   Median :375000   Median : 813.0   Median :160.0   
  Mean   : 804.3   Mean   :426667   Mean   : 914.7   Mean   :207.7   
  3rd Qu.:1000.5   3rd Qu.:560000   3rd Qu.:1115.5   3rd Qu.:236.5   
  Max.   :1242.0   Max.   :745000   Max.   :1418.0   Max.   :313.0   

   BasementArea     LawnArea          Rating          SaleType
  Min.   :1236   Min.   : 15623   10     :2   FifthResale :0  
  1st Qu.:1666   1st Qu.: 39755   7      :1   FirstResale :1  
  Median :2096   Median : 63887   1      :0   FourthResale:0  
  Mean   :2992   Mean   : 98252   2      :0   NewHouse    :1  
  3rd Qu.:3870   3rd Qu.:139566   3      :0   SecondResale:1  
  Max.   :5644   Max.   :215245   4      :0   ThirdResale :0  
                                  (Other):0

Note that the house price for these three leverage points are far away from the mean or high density terms. The house price for two observations corresponds to the highest and lowest in the dataset. Also another interesting thing is the third observation corresponding to median house price is having a very high lawn area, certainly an influence point. Based on this analysis, we can either go back to check if these are data errors or choose to ignore them in our analysis.

6.5.4.2 Normality of Residuals

Residuals are core to the diagnostic of regression models. Normality of residual is an important condition for the model to be a valid linear regression model. In simple words, normality implies that the errors/residuals are random noise and our model has captured all the signals in data.

The linear regression model gives us the conditional expectation of function Y for given values of X. However, the fitted equation has some residual to it. We need the expectation of residual to be normally distributed with a mean of 0 or reducible to 0. A normal residual means that the model inference (confidence interval, model predictors’ significance) is valid.

Distribution of studentized residuals (could be thought of as a normalized value) is a good way to see if the normality assumption is holding or not. But we may still want to formally test the residuals by normality tests like KS tests, Shapiro-Wilk tests, Anderson Darling tests, etc.

Here, we show the plot of studentized residual for a normal distribution, which should follow a bell curve.

library(stats)
library(IDPmisc)
 Loading required package: grid
library(MASS)
sresid <-studres(fitted_Model_multiple)
#Remove irregular values (NAN/Inf/NAs)                    
sresid <-NaRV.omit(sresid)
hist(sresid, freq=FALSE,
main="Distribution of Studentized Residuals",breaks=25)

xfit<-seq(min(sresid),max(sresid),length=40)
yfit<-dnorm(xfit)
lines(xfit, yfit)

The plot in Figure 6-19 is created using the studentized residuals. In the previous code, the residuals are studentized using the studres() function in R.

Figure 6-19. Distribution of studentized residuals

The residual plot is close to a normal plot as the distribution forms a bell curve. However, we still want to do formal testing of the normality. We will show result of all three normality test but formally will introduce the test statistics for the most popular test of normality—one sample Kolmogorov-Smirnov Test or KS test . For rest of the tests, we encourage you to go through the R vignettes for the functions used here. It points to the most appropriate reference on the topic.

Formally, let's introduce the KS test here

The Kolmogorov–Smirnov statistic for a given cumulative distribution function F(x) is
where sup x is the maximum of the set of distances.

The KS statistics give back the largest difference between the empirical distribution of residual and normal distribution. If the largest (supremum) is more than a critical value then we say the distribution is not normal (using the p-value of the test statistic). Here we have three tests for conformity of results:

# test on normality                    
#K-S one sample test                    
ks.test(fitted_Model_multiple$residuals,pnorm,alternative="two.sided")

  One-sample Kolmogorov-Smirnov test

 data:  fitted_Model_multiple$residuals
 D = 0.54443, p-value < 2.2e-16
 alternative hypothesis: two-sided
#Shapiro Wilk Test                    
shapiro.test(fitted_Model_multiple$residuals)

  Shapiro-Wilk normality test

 data:  fitted_Model_multiple$residuals
 W = 0.80444, p-value < 2.2e-16
#Anderson Darling Test                    
library(nortest)
ad.test(fitted_Model_multiple$residuals)

  Anderson-Darling normality test

 data:  fitted_Model_multiple$residuals
 A = 29.325, p-value < 2.2e-16

None of these three test thinks that the residuals are distributed normally. The p-values are less than 0.05, and hence we can reject the null hypothesis that the distribution is normal. This means we have to go back into our model and see what might be driving the non-normal behavior, dropping some variable or adding some variable, influential points, and other issues.

6.5.4.3 Multicollinearity

Multicollinearity is basically a problem of too much information in a pair of independent variables. This is a phenomenon when two or more variables are highly correlated, and hence causes inflated standard errors in the model fit. For testing this phenomenon, we can use the correlation matrix and see if they have a relationship with decent accuracy. If yes, the addition of one variable is enough for supplying the information required to explain the dependent variable.

For this section, we will use the variance inflation factor to determine the degree of multidisciplinary in the independent variables. Another popular method is the Colin index (Condition Index) number to detect multicollinearity.

The variance inflation factor (VIF) for multicollinearity is defined as follows:
where R _j ² is the coefficient of determination of a regression of explanator j on all the other explanators.

Generally, cutoffs for detecting the presence of multicollinearity based on the metrics are:

• Tolerance less than 0.20

• VIF of 5 and greater indicating a multicollinearity problem

The simple solution to this problem is to drop the variable from these thresholds from the model building process.

library(car)
# calculate the vif factor                    
# Evaluate Collinearity                    
print(" Variance inflation factors are ");
 [1] " Variance inflation factors are "
vif(fitted_Model_multiple);
# variance inflation factors                    
                      GVIF Df GVIF^(1/(2*Df))
 StoreArea        1.767064  1        1.329309
 StreetHouseFront 1.359812  1        1.166110
 BasementArea     1.245537  1        1.116036
 LawnArea         1.254520  1        1.120054
 Rating           1.931826  9        1.037259
 SaleType         1.259122  5        1.023309
print("Tolerance factors are ");
 [1] "Tolerance factors are "
1/vif(fitted_Model_multiple)
                       GVIF        Df GVIF^(1/(2*Df))
 StoreArea        0.5659106 1.0000000       0.7522703
 StreetHouseFront 0.7353955 1.0000000       0.8575521
 BasementArea     0.8028664 1.0000000       0.8960281
 LawnArea         0.7971175 1.0000000       0.8928143
 Rating           0.5176450 0.1111111       0.9640796
 SaleType         0.7942043 0.2000000       0.9772220

Now we have the VIF values and tolerance value in the previous tables. We will simply apply the cutoffs for VIF and tolerance as discussed.

# Apply the cut-off to Vif                    
print("Apply the cut-off of 4 for vif")
 [1] "Apply the cut-off of 4 for vif"
vif(fitted_Model_multiple) >4
                   GVIF    Df GVIF^(1/(2*Df))
 StoreArea        FALSE FALSE           FALSE
 StreetHouseFront FALSE FALSE           FALSE
 BasementArea     FALSE FALSE           FALSE
 LawnArea         FALSE FALSE           FALSE
 Rating           FALSE  TRUE           FALSE
 SaleType         FALSE  TRUE           FALSE
# Apply the cut-off to Tolerance
print("Apply the cut-off of 0.2 for vif")
 [1] "Apply the cut-off of 0.2 for vif"
(1/vif(fitted_Model_multiple)) <0.2
                   GVIF    Df GVIF^(1/(2*Df))
 StoreArea        FALSE FALSE           FALSE
 StreetHouseFront FALSE FALSE           FALSE
 BasementArea     FALSE FALSE           FALSE
 LawnArea         FALSE FALSE           FALSE
 Rating           FALSE  TRUE           FALSE
 SaleType         FALSE FALSE           FALSE

You can observe that GVIF column is false for the cutoffs we set for multicollinearity. Hence, we can safely say that our model is not having multicollinearity problem. And hence the standard errors are not inflated, so we can do hypothesis testing.

6.5.4.4 Residual Autocorrelation

Correlation is defined among two different variables, while autocorrelation , also known as serial correlation , is the correlation of a variable with itself at different points in time or in a series. This type of relationship is very important and quite frequently used in time series modeling. Auto-correlation makes more sense when we have an inherent order in the observations, e.g., index by time, key, etc. If the residual shows that it has a definite relationship with prior residuals, i.e. auto-correlated, the noise is not purely by chance, which means we still have some more information that we can extract and put in the model.

To test for auto-correlation we will use the most popular method, the Durbin Watson test .

Given the process has defined the mean and variance, the auto-correlation statistics of Durbin Watson test can be defined as follows:

This can be rewritten for our residual auto-correlation as d-Durbin Watson test statistics:
,where, et is the residual associated with the observation at time t.

To interpret the statistics, you can follow these rules:

Figure 6-20. Durbin Watson statistics bounds

Positive auto-correlations mean a positive error for one observation increases the chances of a positive error for another observation. While negative auto-correlation is the opposite. Both positive and negative auto-correlation are not desired in linear regression models . In Figure 6-21, it is clear that if the d-statistics value is close to 2, we can infer there if no auto-correlation in residual terms.

Figure 6-21. Auto-correlation function (ACF) plot

Another way to detect auto-correlation is by plotting the ACF plots and searching for spikes.

# Test for Autocorrelated Errors                    
durbinWatsonTest(fitted_Model_multiple)
  lag Autocorrelation D-W Statistic p-value
    1     -0.03814535      2.076011   0.192
  Alternative hypothesis: rho != 0
#ACF Plots
plot(acf(fitted_Model_multiple$residuals))

The plot in Figure 6-21 is called an Auto-Correlation Function (ACF) plot against different lags. This plot is popular in time series analysis as the data is time index, so we are using this plot here as a proxy for an auto-correlation explanation.

The Durbin Watson statistics show no auto-correlation among residuals , with d equal to 2.07. Also the ACF plots does not show spikes. Hence, we can say the residuals are free from auto-correlation.

6.5.4.5 Homoscedasticity

Homoscedasticity means all the random variables in the sequence or vector have finite and constant variance. This is also called homogeneity of variance. In the linear regression framework, homoscedastic errors/residuals will mean that the variance of errors is independent of the values of x. This means the probability distribution of y has the same standard deviation regardless of x.

There are multiple statistical tests for checking the homoscedasticity assumption, e.g., the Breush-Pagan test , the arch test, Bartlett's test, and so on. In this section our focus is on Bartlett's test, developed in 1989 by Snedecor and Cochran.

To perform Bartlett’s test, first we create subgroups within our population data. For illustration we have created three groups of population data with 400, 400, and 269 observations in each group.

We can create three groups in data to see if the variance varies across these three groups                    
gp<-numeric()

for( i in 1:1069)
{
  if(i<=400){
    gp[i] <-1;
  }else if(i<=800){
    gp[i] <-2;
  }else{
    gp[i] <-3;
  }
}

Now we define the hypothesis we will be testing in Bartlett’s test:

Ho: All three population variances are the same.

Ha: At least two are different.

Here, we perform Bartlett’s test with the function Bartlett.test():

Data_lm_Model$gp <-factor(gp)
bartlett.test(fitted_Model_multiple$fitted.values,Data_lm_Model$gp)
  Bartlett test of homogeneity of variances                    
data:  fitted_Model_multiple$fitted.values and Data_lm_Model$gp                    
Bartlett's K-squared = 1.3052, df = 2, p-value = 0.5207                    

The Bartlett test has a p-value of greater than 0.05, which means we fail to reject the null hypothesis. The subgroups have the same variance, and hence variance is homoscedastic.

Here, we show some more test for checking variances. This is done for reference purpose so that you can replicate other tests if required.

1. Breush Pagan Test

   # non-constant error variance test - breush pagan test                            
   ncvTest(fitted_Model_multiple)
   Non-constant Variance Score Test                            
   Variance formula: ∼ fitted.values                            
   Chisquare = 2322.866    Df = 1     p = 0                            

   These results are for a popular test for heteroscedasticity called the Breush-Pagan test. The p-value is 0, hence you can reject the null that the variance in heteroscedastic .

2. ARCH Test

   #also show ARCH test - More relevant for a time series model                            
   library(FinTS)
   ArchTest(fitted_Model_multiple$residuals)
     ARCH LM-test; Null hypothesis: no ARCH effects                            
   data:  fitted_Model_multiple$residuals                            
   Chi-squared = 4.2168, df = 12, p-value = 0.9792                            

   The test result for Bartlett test and the Arch test clearly shows that the residuals are homoscedastic. The plot in Figure 6-22 is a residual versus fitted values plot. It is a scatter plot of residuals on the x axis and fitted values (estimated responses) on the y axis. The plot is used to detect non-linearity, unequal error variances, and outliers.

   

   Figure 6-22. Residuals versus fitted plot

# plot residuals vs. fitted values                    
plot(fitted_Model_multiple$residuals,fitted_Model_multiple$fitted.values)

A plot of fitted values and residuals also does not show any behavior of increase or decrease. This means the residuals are homoscedastic as they don’t vary with values of x.

In this section on model diagnostics, we explored the important test and process to identify problems with regression. Influential points can bring bias into the model estimates and reduce the performance of a model. We can explore few options to reduce the problem by capping the values, creating bins and/or may be just remove them for analysis. Normality of residuals is important as we will expect a good model to capture all signals in the data and reduce the residual to just a white noise. Auto-correlation is a feature of indexed data, in this case if the residuals are not independent of each other and have auto-correlation then the model performance will be reduced. Homoscedasticity is another important diagnostic that tells us if the variance of dependent variable is independent of predictor/independent variable. All these diagnostics need to be done after fitting a regression model to make sure the model is reliable and statistically valid to be used in real settings.

Now we have tested major tests for linear regression and can now move onto polynomial regression. So far we have assumed that the relationship between dependent and independent variable was linear, but this may not be the case in real life. Linear relations show the same proportional change behavior at all levels. For example, the HousePrice increase when the store size changes from 10 sq. ft. to 20 sq. ft. is not the same as change of the same 10 sq. ft. from 2000 sq. ft. to 2010 sq. ft. But linear regression ignores this fact and assumes the same change at all levels.

The next section will extend the idea of linear regression to relationships with higher degree polynomials.

6.5.8.1 Binomial Logistic Model

Let’s use our Purchase Prediction data to build a logistic regression model and see its diagnostics. We will be subsetting the data to only have ProductChoice 1 and 3 as 1 and 0 respectively, in our analysis.

#Load the data and prepare a dataset for logistic regression                    
Data_Purchase_Prediction <-read.csv("∼/Dropbox/Book Writing - Drafts/Chapter Drafts/Final Artwork and Code/Chapter 6/Dataset/Purchase Prediction Dataset.csv",header=TRUE);

Data_Purchase_Prediction$choice <-ifelse(Data_Purchase_Prediction$ProductChoice ==1,1,
ifelse(Data_Purchase_Prediction$ProductChoice ==3,0,999));

Data_Logistic <-Data_Purchase_Prediction[Data_Purchase_Prediction$choice %in%c("0","1"),c("CUSTOMER_ID","choice","MembershipPoints","IncomeClass","CustomerPropensity","LastPurchaseDuration")]

table(Data_Logistic$choice,useNA="always")

      0      1   <NA>
 143893 106603      0
Data_Logistic$MembershipPoints <-factor(Data_Logistic$MembershipPoints)
Data_Logistic$IncomeClass <-factor(Data_Logistic$IncomeClass)
Data_Logistic$CustomerPropensity <-factor(Data_Logistic$CustomerPropensity)
Data_Logistic$LastPurchaseDuration <-as.numeric(Data_Logistic$LastPurchaseDuration)

Before we start the model, let's see the distribution of categorical variables over dependent categorical variables .

table(Data_Logistic$MembershipPoints,Data_Logistic$choice)

          0     1
   1  15516 13649
   2  19486 15424
   3  20919 15661
   4  20198 14944
   5  18868 13728
   6  16710 11883
   7  13635  9381
   8   9632  6432
   9   5566  3512
   10  2427  1446
   11   754   441
   12   165    95
   13    17     7

This distribution says, as the MemberShipPoints increase , both choice 0 and 1 decrease.

table(Data_Logistic$IncomeClass,Data_Logistic$choice)

         0     1
   1   145   156
   2   203   209
   3  3996  3535
   4 23894 18952
   5 47025 36781
   6 38905 27804
   7 21784 14715
   8  6922  3958
   9  1019   493

This distribution says, most of the customers are in income classes 4, 5, and 6. The choice distribution is equitable in both 0 and 1 across the income class bands.

table(Data_Logistic$CustomerPropensity,Data_Logistic$choice)

                0     1
   High     26604 10047
   Low      20291 19962
   Medium   27659 17185
   Unknown  36633 52926
   VeryHigh 32706  6483

The distribution is interesting as it tells that customers with very high propensity are very unlikely to buy the product represented by class 1. The distributions are good way to get a first-hand idea of your data. This exploratory task also helps in feature selections for models.

Now, we have all the relevant libraries and function loaded, we will show step by step how to develop the logistic regression and choose one of the model for evaluation in the next chapter. We will be developing model on full data, and the next chapter will discuss performance evaluation metrics in detail.

library(dplyr)
#Get the average purchase rate by Rating and plot that                    

summarise(group_by(Data_Logistic,IncomeClass),Average_Rate=mean(choice))

print("Summary of Average Purchase Rate by IncomeClass")
 [1] "Summary of Average Purchase Rate by IncomeClass"
summary_Rating
 # A tibble: 9 × 2
   IncomeClass Average_Rate
        <fctr><dbl>
 1           1    0.5182724
 2           2    0.5072816
 3           3    0.4693932
 4           4    0.4423283
 5           5    0.4388827
 6           6    0.4167953
 7           7    0.4031617
 8           8    0.3637868
 9           9    0.3260582
plot(summary_Rating$IncomeClass,summary_Rating$Average_Rate,type="b", xlab="Income Class", ylab="Average Purchase Rate observed", main="Purchase Rate and Income Class")

Now we want to see how average purchase rate of product 1 varies over the Income class. We plot the average purchase rate (proportion of 1) by each income class, as shown in Figure 6-27.

The plot in Figure 6-26 shows that, as the income class increases the propensity to buy the product 1, goes down. Similar plots can be created for other variables to see how the expected behavior of model probabilities should be after fitting a model.

Figure 6-26. Purchase rate and income class

Now we will clean up the data from NA’s (missing values 0) and fit a binary logistic regression using the function glm(). GLM stands for generalized linear regression, which can handle exponential family of distributions . The function requires users to mention the family of distribution the dependent variable belong to and the link function you want to use. We have used the binomial family with logit as a link function.

#Remove the Missing values - NAs                    

Data_Logistic <-na.omit(Data_Logistic)
rownames(Data_Logistic) <-NULL

#Divide the data into Train and Test                    
set.seed(917);
index <-sample(1:nrow(Data_Logistic),round(0.7*nrow(Data_Logistic)))
train <-Data_Logistic[index,]
test <-Data_Logistic[-index,]

Fitting a logistic model

Model_logistic <-glm( choice ∼MembershipPoints +IncomeClass +CustomerPropensity +LastPurchaseDuration, data = train, family =binomial(link ='logit'));

summary(Model_logistic)                                                                                      

 Call:
 glm(formula = choice ∼ MembershipPoints + IncomeClass + CustomerPropensity +
     LastPurchaseDuration, family = binomial(link = "logit"),
     data = train)

 Deviance Residuals:
    Min      1Q  Median      3Q     Max  
 -1.631  -1.017  -0.614   1.069   2.223  

 Coefficients:
                             Estimate Std. Error z value Pr(>|z|)    
 (Intercept)                 0.066989   0.145543   0.460 0.645323    
 MembershipPoints2          -0.123408   0.020577  -5.997 2.01e-09 ***
 MembershipPoints3          -0.185540   0.020359  -9.113  < 2e-16 ***
 MembershipPoints4          -0.204938   0.020542  -9.977  < 2e-16 ***
 MembershipPoints5          -0.237311   0.020942 -11.332  < 2e-16 ***
 MembershipPoints6          -0.258884   0.021597 -11.987  < 2e-16 ***
 MembershipPoints7          -0.291123   0.022894 -12.716  < 2e-16 ***
 MembershipPoints8          -0.326029   0.025526 -12.773  < 2e-16 ***
 MembershipPoints9          -0.387113   0.031572 -12.261  < 2e-16 ***
 MembershipPoints10         -0.439228   0.044839  -9.796  < 2e-16 ***
 MembershipPoints11         -0.357339   0.078493  -4.553 5.30e-06 ***
 MembershipPoints12         -0.447326   0.164172  -2.725 0.006435 **
 MembershipPoints13         -1.349163   0.583320  -2.313 0.020728 *  
 IncomeClass2               -0.412020   0.190461  -2.163 0.030520 *  
 IncomeClass3               -0.342854   0.146938  -2.333 0.019631 *  
 IncomeClass4               -0.389236   0.144433  -2.695 0.007040 **
 IncomeClass5               -0.373493   0.144169  -2.591 0.009579 **
 IncomeClass6               -0.442134   0.144244  -3.065 0.002175 **
 IncomeClass7               -0.455158   0.144548  -3.149 0.001639 **
 IncomeClass8               -0.509290   0.146126  -3.485 0.000492 ***
 IncomeClass9               -0.569825   0.160174  -3.558 0.000374 ***
 CustomerPropensityLow       0.877850   0.018709  46.921  < 2e-16 ***
 CustomerPropensityMedium    0.427725   0.018491  23.131  < 2e-16 ***
 CustomerPropensityUnknown   1.208693   0.016616  72.744  < 2e-16 ***
 CustomerPropensityVeryHigh -0.601513   0.021652 -27.781  < 2e-16 ***
 LastPurchaseDuration       -0.063463   0.001211 -52.393  < 2e-16 ***
 ---
 Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1

 (Dispersion parameter for binomial family taken to be 1)

     Null deviance: 235658  on 172985  degrees of freedom
 Residual deviance: 213864  on 172960  degrees of freedom
 AIC: 213916

 Number of Fisher Scoring iterations: 4

The p-value of all the variables and levels is significant. This implies we have fit a model with variables having significant relationship with dependent variable. Now let’s work out to get classification matrix for this model. This is done by method of balancing specificity and sensitivity measure. Details of these metrics are given in Chapter 6, and we will give a brief explanation here and make use of that to create a good cutoff for classification from probabilities into classes.

#install and load package                    
library(pROC)
#apply roc function                    
cut_off <-roc(response=train$choice, predictor=Model_logistic$fitted.values)

#Find threshold that minimizes error                    
e <-cbind(cut_off$thresholds,cut_off$sensitivities+cut_off$specificities)
best_t <-subset(e,e[,2]==max(e[,2]))[,1]

#Plot ROC Curve                    
plot(1-cut_off$specificities,cut_off$sensitivities,type="l",
ylab="Sensitivity",xlab="1-Specificity",col="green",lwd=2,
main ="ROC Curve for Train")
abline(a=0,b=1)

abline(v = best_t) #add optimal t to ROC curve                

The plot in Figure 6-27 is between specificity and sensitivity. The plot is also called ROC plot . The best cutoff is the value on the curve that maximizes sensitivity and minimizes (1-specificity).

Figure 6-27. ROC curve for train data

cat(" The best value of cut-off for classifier is ", best_t)
The best value of cut-off for classifier is 0.4202652                    

Looking at the plot, we can see our choice of cutoff will provide best classification on the train data. We need to test this assumption on the test data and record the classification rate by using this cutoff of 0.42.

# Predict the probabilities for test and apply the cut-off
predict_prob <-predict(Model_logistic, newdata=test, type="response")

#Apply the cutoff to get the class

class_pred <-ifelse(predict_prob >0.41,1,0)

#Classification table
table(test$choice,class_pred)
    class_pred
         0     1
   0 24605 18034
   1  8364 23134
#Classification rate
sum(diag(table(test$choice,class_pred))/nrow(test))
 [1] 0.6439295

The model shows 64% good classification on the test data. This shows the model can capture the signals in the data well to distinguish between 0 and 1.

The logistic model diagnostic is different from linear regression models. In following sections, we explore some common diagnostic metrics for logistic regression.

6.5.9.1 Wald Test

The Wald test is analogous to the t-test test in linear regression. This is used to assess the contribution of individual predictors in a given model.

In logistic regression, the Wald statistic is

Add, β is coefficient and SE is standard error of coefficient β.

The Wald statistic is the ratio of the square of the regression coefficient to the square of the standard error of the coefficient, and it follows a chi-square distribution. The significant Wald statistics implies the predictor/independent variable is significant in the model.

Let's perform a Wald test on MembershipPointsand see if that is significant in model or not.

#Wald test                    
library(survey)
regTermTest(Model_logistic,"MembershipPoints", method ="Wald")
Wald test for MembershipPoints                    
  in glm(formula = choice ∼ MembershipPoints + IncomeClass + CustomerPropensity +                    
     LastPurchaseDuration, family = binomial(link = "logit"),                    
     data = train)                    
F =  31.64653  on  12  and  172960  df: p= < 2.22e-16                    

The p-value is less than 0.05, so at 95% confidence we can reject the null hypothesis that the coefficient’s value is zero. Hence, the MembershipPoints is statistically significant variable of model.

6.5.9.2 Deviance

Deviance is calculated by comparing a null model and a saturated model. A null model is a model without any predictor in it, just the intercept term and a saturated model is the fitted model with some predictors in it. In logistic regression, deviance is used in lieu of sum of squares calculations. The test statistic (often denoted by D) is twice the log of the likelihoods ratio, i.e., it is twice the difference in the log likelihoods :

Deviance

Deviance statistic (D) follows a chi-square distribution. Smaller values indicate better fit as the fitted model deviates less from the saturated model.

Here is the analysis of the deviance table.

#Anova table of significance                    
anova(Model_logistic, test="Chisq")
 Analysis of Deviance Table

 Model: binomial, link: logit

 Response: choice

 Terms added sequentially (first to last)

                      Df Deviance Resid. Df Resid. Dev  Pr(>Chi)    
 NULL                                172985     235658              
 MembershipPoints     12    330.6    172973     235328 < 2.2e-16 ***
 IncomeClass           8    339.1    172965     234989 < 2.2e-16 ***
 CustomerPropensity    4  18297.4    172961     216691 < 2.2e-16 ***
 LastPurchaseDuration  1   2826.9    172960     213864 < 2.2e-16 ***
 ---
 Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1

The chi-square test on all the variables is significant as the p-value is less than 0.05. All the predictors’ contributions to the model are significant.

6.5.9.3 Pseudo R-Square

In linear regression, we have R-Square measure (discussed in detail in Chapter 7), which measures the proportion of variance independently explained by the model. A similar measure in logistics regression is called pseudo R-Square . The most popular of such measure used the likelihood ratio, which is presented as:

The ratio of difference in deviance of null and fitted model by null model. The higher the value of this measure, the better the explaining power of model. There are other similar measures not discussed in this chapter, like Cox and Snell R-Square, Nagelkerke R-Square, McFadden R-Square, and Tjur R-Square. Here we compute the pseudo R-Square for our model.

# R square equivalent for logistic regression                    
library(pscl)
pR2(Model_logistic)
           llh       llhNull            G2      McFadden          r2ML
 -1.069321e+05 -1.178291e+05  2.179399e+04  9.248135e-02  1.183737e-01
          r2CU
  1.591199e-01

The last three outputs from this function are McFadden's pseudo R-Square , Maximum likelihood pseudo R-Square (Cox & Snell) and Cragg and Uhler's or Nagelkerke's pseudo R-Square. The R-Square values are very low, signifying that the model might not be performing better than a null model.

6.5.9.4 Bivariate Plots

The most important diagnostic of logistic regression is to see how the actual probabilities and predicted probabilities behave by each level of single independent variables. These plots are called bivariate as there are two variables actual and predicted plotted against single independent variable levels. The plot have three important inputs:

• Actual Probability: The prior proportion of target level in each category of independent variable.

• Predicted Probability: The probability given by the model.

• Frequency: The frequency of a categorical variable (number of observations).

The plot essentially tells us how the model is behaving for different levels in our categorical variables. You can extend this idea to continuous variables as well by binning the continuous variable.

Another good thing about these plots is that you are able to determine for which cohort in your dataset the model performs better and where it need investigation. This cohort level diagnostic is not possible by looking at aggregated plots.

#The function code is provided separately in the appendix                    
source("actual_pred_plot.R")
MODEL_PREDICTION <-predict(Model_logistic, Data_Logistic, type ='response');
Data_Logistic$MODEL_PREDICTION <-MODEL_PREDICTION
#Print the plots MembershipPoints                    
actual_pred_plot  (var.by=as.character("MembershipPoints"),
var.response='choice',
data=Data_Logistic,
var.predict.current='MODEL_PREDICTION',
var.predict.reference=NULL,
var.split=NULL,
var.by.buckets=NULL,
sort.factor=FALSE,
errorbars=FALSE,
subset.to=FALSE,
barline.ratio=1,
title="Actual vs. Predicted Purchase Rates",
make.plot=TRUE
                )

The plot in Figure 6-28 shows actual versus predicted against the frequency plot of MembershipPoints.

Figure 6-28. Actual versus predicted plot against MembershipPoints

For MembershipPoints, the actual and predicted probabilities follow each other. This means the model predicts the probabilities close to actual. Also, you can see in both cases customer having higher MembershipPoints are less likely to have product choice = 1, that is the same as seen in the actual and predicted.

#Print the plots IncomeClass                    
actual_pred_plot  (var.by=as.character("IncomeClass"),
var.response='choice',
data=Data_Logistic,
var.predict.current='MODEL_PREDICTION',
var.predict.reference=NULL,
var.split=NULL,
var.by.buckets=NULL,
sort.factor=FALSE,
errorbars=FALSE,
subset.to=FALSE,
barline.ratio=1,
title="Actual vs. Predicted Purchase Rates",
make.plot=TRUE
                )

The plot in Figure 6-29 shows actual versus predicted against the frequency plot of IncomeClass.

Figure 6-29. Actual versus predicted plot against IncomeClass

Again the model behavior for IncomeClass is as expected . The model is able to predict the probabilities across different income classes as an actual observed rate.

#Print the plots CustomerPropensity                    
actual_pred_plot  (var.by=as.character("CustomerPropensity"),
var.response='choice',
data=Data_Logistic,
var.predict.current='MODEL_PREDICTION',
var.predict.reference=NULL,
var.split=NULL,
var.by.buckets=NULL,
sort.factor=FALSE,
errorbars=FALSE,
subset.to=FALSE,
barline.ratio=1,
title="Actual vs. Predicted Purchase Rates",
make.plot=TRUE
                )

The plot in Figure 6-30 shows actual versus predicted against the frequency plot of CustomerPropensity.

Figure 6-30. Actual versus predicted plot against CustomerPropensity

The model shows good agreement with observed probabilities for CustomerPropensity as well. Similar plots can be plotted for continuous variable in our model after binning them appropriately. At least on categorical variables, the model performs well.

The model shows a good prediction against actual values across different categorical variable levels. It's a good model at the probability scale!

6.5.9.5 Cumulative Gains and Lift Charts

Cumulative gains and lift charts are visual ways to measure the effectiveness of predictive models. They consist of a baseline and the lift curve due to the predictive model. The more there is separation between baseline and predicted (lift) curve, the better the model.

In a Gains curve:

X-axis: % of customers

Y-axis: Percentage of positive predictions

Baseline: Random line (x% of customers giving x% of positive predictions)

Gains: The percentage of positive responses for the % of customers

In a Lift curve:

X-axis: % of customers

Y-axis: Actual lift (the ratio between the result predicted by our model and the result using no model)

library(gains)
library(ROCR)
library(calibrate)
MODEL_PREDICTION <-predict(Model_logistic, Data_Logistic, type ='response');

Data_Logistic$MODEL_PREDICTION <-MODEL_PREDICTION;

lift =with(Data_Logistic, gains(actual = Data_Logistic$choice, predicted = Data_Logistic$MODEL_PREDICTION , optimal =TRUE));

pred =prediction(MODEL_PREDICTION,as.numeric(Data_Logistic$choice));

#                                              Function                                                                                                                    to create performance objects. All kinds of predictor evaluations are performed using this function.                    
gains =performance(pred, 'tpr', 'rpp');
# tpr: True positive rate                    
# rpp: Rate of positive predictions                    
auc =performance(pred, 'auc');
auc =unlist(slot(auc, 'y.values')); # The same as: [email protected][[1]]                
auct =paste(c('AUC = '), round(auc, 2), sep ='')

#par(mfrow=c(1,2), mar=c(6,5,4,2));                    
plot(gains, col='red', lwd=2, xaxs='i', yaxs='i', main =paste('Gains Chart ', sep =''),ylab='% of Positive Response', xlab='% of customers/population');
axis(side =1, pos =0, at =seq(0, 1, by =0.10));
axis(side =2, pos =0, at =seq(0, 1, by =0.10));

lines(x=c(0,1), y=c(0,1), type='l', col='black', lwd=2,
ylab='% of Positive Response', xlab='% of customers/population');

legend(0.6, 0.4, auct, cex =1.1, box.col ='white')

gains =lift$cume.pct.of.total
deciles =length(gains);

for (j in 1:deciles)
{
  x =0.1;
  y =as.numeric(as.character(gains[[j]]));
lines(x =c(x*j, x*j),
y =c(0, y),
type ='l', col ='blue', lwd =1);
lines(x =c(0, 0.1*j),
y =c(y, y),
type ='l', col ='blue', lwd =1);
# Annotating the chart by adding the True Positive Rate exact numbers at the specified deciles.                    
textxy(0, y, paste(round(y,2)*100, '%',sep=''), cex=0.9);
}

The chart in Figure 6-31 is the Gains chart for our model. This is plotted with % of positive responses on the y axis and % of population on the x axis.

Figure 6-31. Gains charts with AUC

plot(lift,  
xlab ='% of customers/population',
ylab ='Actual Lift',
main =paste('Lift Chart 
', sep =' '),
xaxt ='n');
axis(side =1, at =seq(0, 100, by =10), las =1, hadj =0.4);

The chart in Figure 6-32 is the Lift chart for our model. This is plotted with actual lift on the y axis and % of population on the x axis.

Figure 6-32. Lift chart

The Gains shows a good separation between model line and baseline. This shows that the model has good separation power. Also the AUC value of 0.7 means that the model will be able to roughly separate 70% of cases.

The Lift curve shows a lift of close to 70% for the first 10% of the population. This value need to be the same as what we have observed in Gains chart, only the presentation has changed.

6.5.9.6 Concordance and Discordant Ratios

In any classification model based on raw probabilities, we need a classification methodology to separate these probability cases. In binary logistic, this is most of the time done by choosing a cutoff value and then creating an inequality to classify objects into 0 or 1.

To make sure such a cutoff exists and has good separation power, we have to see if the actual objects with state 1 in data are having higher probability than the actual state 0. For example, a pair of (Yi,Yj) be (0,1), then the predicted values (Pi,Pj) should have Pj>Pi, then we can choose a number between Pj and Pi, which will correctly classify a 1 as 1 and 0 as 0. Based on this understanding , we can divide all the possible pairs in data into three types:

• Concordant pairs: For (0,1) or (1,0) corresponding probabilities with 1 are greater than probabilities with 0

• Discordant pairs: For (0,1) or (1,0) corresponding probabilities with 0 are greater than probabilities with 1

• Tied: (0,0) and (1,0) pairs

The concordance ratio is then defined as the ratio of the number of concordant pairs by the total number of pairs.

If our model produces a high concordance ratio then it will be able to classify the objects in classes more accurately.

#The function code is provided separately in R-code for chapter 6                    
source("concordance.R")

#Call the concordance function to get these ratios                    
concordance(Model_logistic)
 $Concordance
 [1] 0.7002884

 $Discordance
 [1] 0.2991384

 $Tied
 [1] 0.0005731122

 $Pairs
 [1] 7302228665

The concordance is 69.9%, signifying that the model probabilities have good separation on ∼70% cases. This is a good model to create a classifier for 0 and 1.

In this section of model diagnostics for logistic regression we discussed the diagnostics in broadly two bucket, model fit statistics and model classification power. The model fit statistics discussed Wald test , which is significance test for the parameter estimates, Deviance is similar measure to residual in linear regression and pseudo R-Square, which is equivalent to R-Square of liner regression. The other set of diagnostics were to identify if the model can be used to create a powerful classifier. The test included were bivariate plots, this is a plot of actual probability by predicted probabilities, cumulative gains and lift chart to show hoe well our model differentiate between two classes, and the concordance ratio tells us if we can have a good cutoff value for our classifier. These diagnostics provide us vital properties of the model and help the modeler to either improve or re-estimate the models.

In the next section, we will more onto multi-class classification problems. Multi-class problems are one of the hardest problems to solve, as more number of classes bring ambiguity. It is difficult to create a good classifier in many cases. We will discuss multiple ways you can do multi-class classification using machine learning. Multinomial logistic regression is one the popular ways to to multi-class classification.

6.6.1.1 Hard Margins

For the hard margins

Minimize , subject to

6.6.1.2 Soft Margins

For the soft margins
Minimizewhere

Parameter λ determines the tradeoff between increasing the margin and ensuring lies on the correct side of the margin.

6.7.1.1 Regression Trees

In problems where the response variable is continuous, regression trees are useful. They provide the same level of interpretability as Linear Regression and on top of that, they are a very intuitive understanding of final output, which ties back to the domain of the problem. In the previous example in the Figure 6-34, the regression tree is built to recursively split the two feature vector space into different regions based on various thresholds. Our objective in splitting the regions in every iteration is to minimize the Residual Sum of Squares (RSS) defined by the following equation:

Figure 6-34. Decision tree with two attributes and a class

Overall, the following are the two steps involved in regression tree building and prediction on new test data :

• Recursively split the feature vector space (X₁, X₂, …, X_p) into distinct and non-overlapping regions

• For new observations falling into the same region, the prediction is equal to the mean of all the training observations in that region.

In n-dimensional feature vector, Gini-index or Entropy, measures of classification power of node could be used to choose the right feature to split the space into different regions. Variance reduction (not covered in this book) is another popular approach which appropriately discretizes the range of continuous response variable in order to choose the right thresholds for splitting.

Figure 6-35. Recursive binary split and its corresponding tree for two-dimensional feature space

We will take up demonstration using a regression tree algorithm called Classification and Regression Tree (CART) later in this chapter, on the housing dataset described earlier in this chapter.

6.7.1.2 Classification Tree

Classification tree is more suitable for categorical or discrete response variables. The following are the key differences between classification trees and regression trees:

• We use classification error rate for making the splits in classification trees.

• Instead of taking the mean of response variable in a particular region for prediction, here we use the most commonly occurring class of training observation as a prediction methodology.

Again, we could use Gini-Index or Entropy as a measure for selecting the best feature or attribute of splitting the observations into different classes.

In the coming sections, we will discuss some popular classification decision tree algorithms like ID3 and C5.0

6.7.2.1 Gini Index

A Gini-Index is calculated using
where, p _mk is the proportion of training observations in the m^th region that are from the k^th class.

For demonstration purposes, look at Figure 6-36. Suppose you have two classes where P1 proportion of all training observation belongs to class C₁ (triangle) and then P2 = 1-P1 belongs to C₂ (circle), the Gini-Index assumes a curve as shown here:

Figure 6-36. Gini-Index function

curve(x *(1-x) +(1 -x) *x, xlab ="P", ylab ="Gini-Index", lwd =5)

6.7.2.2 Entropy

Entropy is calculated using

The curve for entropy looks something like this:

curve(-x *log2(x) -(1 -x) *log2(1 -x), xlab ="x", ylab ="Entropy", lwd =5)

Figure 6-37. Entropy function

Observe that both measures are very similar, however, there are some differences:

• Gini-index is more suitable to continuous attributes and entropy in case of discrete data.

• Gini-index works well for minimizing misclassifications.

• Entropy is slightly slower than Gini-index, as it involves logarithms (although this doesn't really matter much given today's fast computing machines).

6.7.2.3 Information Gain

Information Gain is a measure that quantifies the change in the entropy before and after the split. It’s an elegantly simple measure to decide the relevance of an attribute. In general, we could write information gain as:

,

where G(Parent) is the Gini-Index (we could use Entropy as well) of parent node represented by an attribute before the split and G(Children) is the Gini-index of children nodes that will be generated after the split. For example, in Figure 6-34, all observations satisfying the parent node condition x<0.43 are its left child nodes and remaining its right.

6.7.3.1 Iterative Dichotomizer 3

J.Ross Quinlan, a computer science researcher in data mining and decision theory, invented the most popular decision tree algorithms, C4.5 and ID3. Here is a brief of how the ID3 algorithm works:

1. Calculates entropy for each attribute using the training observations.

2. Split the observations into subsets using the attribute with minimum entropy or maximum information gain.

3. The selected attribute becomes the decision node.

4. Repeat the process with the remaining attribute on the subset.

For demonstration, we will use a R Package called RWeka , which is a wrapper built on the tool Weka, which is a collection of machine learning algorithms for data mining tasks written in Java, containing tools for data pre-processing, classification, regression, clustering, association rules, and visualization. The package RWeka contains the interface code, and the Weka jar is in a separate package called RWekajars. For more information on Weka, see http://www.cs.waikato.ac.nz/ml/weka/ .

1. Install the package RWeka.

2. Set the environment variable WEKA_HOME to a folder location on your drive (e.g., D:home) where you have sufficient access rights.

3. In the R console, run these two commands :

   WPM("refresh-cache")
   #looks for a package providing id3
   
   WPM("install-package", "simpleEducationalLearningSchemes")
   #load the package

   1. Model Building

      library(RWeka)
      
      WPM("refresh-cache")
      WPM("install-package", "simpleEducationalLearningSchemes")
      
       make classifier
      ID3 <-make_Weka_classifier("weka/classifiers/trees/Id3")
      
      ID3Model <-ID3(ProductChoice ∼CustomerPropensity +IncomeClass , data = train)
      
      summary(ID3Model)                                                                                                      
      
       === Summary ===
      
       Correctly Classified Instances        9423               33.6536 %
       Incorrectly Classified Instances     18577               66.3464 %
       Kappa statistic                          0.1148
       Mean absolute error                      0.3634
       Root mean squared error                  0.4263
       Relative absolute error                 96.9041 %
       Root relative squared error             98.4399 %
       Total Number of Instances            28000     
      
       === Confusion Matrix ===
      
           a    b    c    d   <-- classified as
        4061  987  929 1078 |    a = 1
        3142 1054 1217 1603 |    b = 2
        2127  727 1761 2290 |    c = 3
        2206  859 1412 2547 |    d = 4

   2. Model Evaluation

Training set accuracy are present as part of the ID3 model output (33% correctly classified instances), so we needn't present that here. Let’s look at the testing set accuracy.

Testing set Accuracy = 32%

As you can observe, the accuracy is not exceptionally good. Moreover, given there are four classes of data, the accuracy is prone to be even less. The fact that training and testing accuracy are almost equal tells us that there is as such no overfitting kind of scenario.

library(gmodels)
purchase_pred_test <-predict(ID3Model, test)
CrossTable(test$ProductChoice, purchase_pred_test,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  20002

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   2849 |       758 |       625 |       766 |      4998 |
                |  0.142 |     0.038 |     0.031 |     0.038 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   2291 |       681 |       872 |      1151 |      4995 |
                |  0.115 |     0.034 |     0.044 |     0.058 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1580 |       545 |      1151 |      1759 |      5035 |
                |  0.079 |     0.027 |     0.058 |     0.088 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |   1594 |       590 |      1066 |      1724 |      4974 |
                |  0.080 |     0.029 |     0.053 |     0.086 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |   8314 |      2574 |      3714 |      5400 |     20002 |
 ---------------|--------|-----------|-----------|-----------|-----------|

The accuracy isn’t very impressive with ID3 algorithm. One possible reason could be the multiple classes in our response variables. Generally, the ID3 is not known for performing exceptionally well on multi-class problems.

6.7.3.2 C5.0 algorithm

In his book, C4.5: Programs for Machine Learning, J. Ross Quinlan[3], laid down a set of key requirements for using these algorithms for classification task, which are as follows:

• Attribute-value description: All information about one case should be expressible in terms of fixed collection of attributes (features) and it should not vary from one case to another.

• Predefined classes: As it happens in any supervised learning approach, the categories to which cases are to be assigned must be predefined.

• Discrete classes: The classes must be sharply delineated; a case either does or does not belong to a particular class and there must be far more cases than classes. So, clearly, problems with continuous response variable are not the right fit for this algorithm.

• Sufficient Data: The amount of data required is affected by factors such as number of attributes and classes. As these increases, more data will be needed to construct a reliable model.

• Logical classification models: The description of the class should be logical expressions whose primitives are statements about the values of particular attributes. For example, IF Outlook = "sunny" AND Windy = "false" THEN class = "Play".

Here we will use the C5.0 algorithm, on our purchase prediction dataset which is an extension of C4.5 for building the decision tree. C4.5 was a collective name given to a set of computer programs that constructs a classification models. The following are some new features in C5.0 are illustrated in Ross Quinlan's web page ( http://www.rulequest.com/see5-comparison.html ).

In the classic book, Experiments in Induction, Hunt et. al.[4] has described many implementations of concept learning systems. Here is how Hunt's approach works.

Given a set of T training observations having C₁, C₂, …, C_k classes, at a broad level, following are the three possibilities involved in building the tree:

1. All the observations of T belongs to a single class C_i, the decision tree D for T is a leaf identifying class C_i.

2. T contains no class. C5.0 uses the most frequent class at the parent of this node.

3. T contains observation which mixture of classes. A node condition (test) is chosen based on single attribute (the attribute is chosen based on information gain) which generates a partitioned set of T₁, T₂, …, T_n.

The split in third possibility is recursive in the algorithm, which is repeated until either all the observations are correctly classified or the algorithm runs out of attribute to split. Since this divide and conquer is a greedy approach that looks only at the immediate step to take a decision for split, its possible to end up in situation like overfitting. In order to avoid this, a technique called pruningis used, which reduces the overfit and generalizes better to unseen data. Fortunately, you don't have to worry about pruning since C5.0 algorithm after building the decision tree, iterates back and replace the branches that do not increase the information gain.

Here, we will use our Purchase Preference dataset to build a C5.0 decision tree model on for product choice prediction based on the ProductChoice response variable.

1. Model Building

   model_c50 <-C5.0(train[,c("CustomerPropensity","LastPurchaseDuration", "MembershipPoints")],
                train[,"ProductChoice"],
   control =C5.0Control(CF =0.001, minCases =2))

2. Model Summary

   summary(model_c50)
   
    Call:
    C5.0.default(x = train[, c("CustomerPropensity",
     "LastPurchaseDuration", "MembershipPoints")], y =
     train[, "ProductChoice"], control = C5.0Control(CF = 0.001, minCases = 2))
   
    C5.0 [Release 2.07 GPL Edition]      Sun Oct 02 16:09:05 2016
    -------------------------------
   
    Class specified by attribute `outcome'
   
    Read 28000 cases (4 attributes) from undefined.data
   
    Decision tree:
   
    CustomerPropensity in {High,VeryHigh}:
    :...MembershipPoints <= 1: 4 (1264/681)
    :   MembershipPoints > 1:
    :   :...LastPurchaseDuration <= 6: 3 (3593/2266)
    :       LastPurchaseDuration > 6:
    :       :...CustomerPropensity = High: 3 (1665/1083)
    :           CustomerPropensity = VeryHigh: 4 (2140/1259)
    CustomerPropensity in {Low,Medium,Unknown}:
    :...MembershipPoints <= 1: 4 (3180/1792)
        MembershipPoints > 1:
        :...CustomerPropensity = Unknown: 1 (8004/4891)
            CustomerPropensity in {Low,Medium}:
            :...LastPurchaseDuration <= 2: 1 (2157/1417)
                LastPurchaseDuration > 2:
                :...LastPurchaseDuration > 13: 2 (1083/773)
                    LastPurchaseDuration <= 13:
                    :...CustomerPropensity = Medium: 3 (2489/1707)
                        CustomerPropensity = Low:
                        :...MembershipPoints <= 3: 2 (850/583)
                            MembershipPoints > 3: 1 (1575/1124)
   
    Evaluation on training data (28000 cases):
   
         Decision Tree   
       ----------------  
       Size      Errors  
   
         11 17576(62.8%)   <<
   
        (a)   (b)   (c)   (d)    <-classified as
       ----  ----  ----  ----
       4304   374  1345  1032    (a): class 1
       3374   577  1759  1306    (b): class 2
       2336   484  2691  1394    (c): class 3
       1722   498  1952  2852    (d): class 4
   
     Attribute usage:
   
     100.00% CustomerPropensity
     100.00% MembershipPoints
      55.54% LastPurchaseDuration
   
    Time: 0.1 secs
   plot(model_c50)                            

   You can experiment with the parameters of C5.0 to see how the decision tree changes. As shown in Figure 6-38, if you traverse through any path, it forms one decision rule. For example, Rule: CustomerPropensity in {High,VeryHigh}ANDMembershipPoints <= 1 is one path ending in a decision node as shown in Figure 6-38.

   

   Figure 6-38. C5.0 decision tree on the purchase prediction dataset

3. Evaluation

Training set Accuracy = 37%

library(gmodels)

purchase_pred_train <-predict(model_c50, train,type ="class")
CrossTable(train$ProductChoice, purchase_pred_train,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  28000

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   4304 |       374 |      1345 |      1032 |      7055 |
                |  0.154 |     0.013 |     0.048 |     0.037 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   3374 |       577 |      1759 |      1306 |      7016 |
                |  0.120 |     0.021 |     0.063 |     0.047 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   2336 |       484 |      2691 |      1394 |      6905 |
                |  0.083 |     0.017 |     0.096 |     0.050 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |   1722 |       498 |      1952 |      2852 |      7024 |
                |  0.061 |     0.018 |     0.070 |     0.102 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |  11736 |      1933 |      7747 |      6584 |     28000 |
 ---------------|--------|-----------|-----------|-----------|-----------|

Testing set accuracy = 36%

purchase_pred_test <-predict(model_c50, test)
CrossTable(test$ProductChoice, purchase_pred_test,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))
purchase_pred_test <-predict(model_c50, test)
CrossTable(test$ProductChoice, purchase_pred_test,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  20002

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   3081 |       279 |       895 |       743 |      4998 |
                |  0.154 |     0.014 |     0.045 |     0.037 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   2454 |       321 |      1317 |       903 |      4995 |
                |  0.123 |     0.016 |     0.066 |     0.045 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1730 |       344 |      1843 |      1118 |      5035 |
                |  0.086 |     0.017 |     0.092 |     0.056 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |   1176 |       349 |      1382 |      2067 |      4974 |
                |  0.059 |     0.017 |     0.069 |     0.103 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |   8441 |      1293 |      5437 |      4831 |     20002 |
 ---------------|--------|-----------|-----------|-----------|-----------|

As you can observe, the accuracy is not exceptionally good. Moreover, given there are four classes of data, the accuracy is prone to be even less. The fact that training and testing accuracy are almost equal tells us that there is as such no overfitting kind of scenario.

6.7.3.3 Classification and Regression Tree: CART

CART is a regression tree-based approach and as explained in the section 6.8.1.1and its uses the sum of squared deviation about the mean (residual sum of square) as the node impurity measure. Keep in mind, CART could also be used for classification problems, in which case, Gini-Index is a more appropriate choice for impurity measure. Roughly, here is a short pseudo code for the algorithm:

1. Start the algorithm at the root node.

2. For each attribute X, find the subset S that minimizes the residual sum of square (RSS) of the two children and chooses the split that gives the maximum information gain.

3. Check if relative decrease in impurity is below a prescribed threshold.

4. If Yes, splitting stops, otherwise repeat Step 2.

Let’s see a demonstration of CART using the rpart function , which is available in the most commonly used package with rpart. It also provides methods to build decision tree like Random Forest, which we will cover later in this chapter.

We will also use an additional parameter cp (complexity parameter) in the function call, which signifies that any split that does not decrease the overall lack of fit by a factor of cp would not be attempted by the model.

1. Building the model

   CARTModel <-rpart(ProductChoice ∼IncomeClass +CustomerPropensity +LastPurchaseDuration +MembershipPoints, data=train)
   
   summary(CARTModel)
    Call:
    rpart(formula = ProductChoice ∼ IncomeClass + CustomerPropensity +
        LastPurchaseDuration + MembershipPoints, data = train)
      n= 28000
   
              CP nsplit rel error    xerror        xstd
    1 0.09649081      0 1.0000000 1.0034376 0.003456583
    2 0.02582955      1 0.9035092 0.9035092 0.003739335
    3 0.02143710      2 0.8776796 0.8776796 0.003793749
    4 0.01000000      3 0.8562425 0.8562425 0.003833608
   
    Variable importance
      CustomerPropensity     MembershipPoints LastPurchaseDuration
                      53                   37                    8
             IncomeClass
                       2
   
    Node number 1: 28000 observations,    complexity param=0.09649081
      predicted class=1  expected loss=0.7480357  P(node) =1
        class counts:  7055  7016  6905  7024
       probabilities: 0.252 0.251 0.247 0.251
      left son=2 (14368 obs) right son=3 (13632 obs)
      Primary splits:
     CustomerPropensity   splits as  RLRLR,     improve=408.0354, (0 missing)
     MembershipPoints     < 1.5 to the right,   improve=269.2781, (0 missing)
     LastPurchaseDuration < 5.5 to the left,    improve=194.7965, (0 missing)
     IncomeClass         splits as  LRLLLLRRRL, improve= 24.2665, (0 missing)
     Surrogate splits:
     LastPurchaseDuration < 5.5 to the left,  agree=0.590, adj=0.159, (0 split)
      IncomeClass      splits as  LLLLLLLRRR, agree=0.529, adj=0.032, (0 split)
        MembershipPoints     < 9.5 to the left, agree=0.514, adj=0.002, (0 split)
   
   ....
   
    Node number 7: 2066 observations
      predicted class=4  expected loss=0.5382381  P(node) =0.07378571
        class counts:   291   408   413   954
       probabilities: 0.141 0.197 0.200 0.462
   library(rpart.plot)
   library(rattle)
   
   fancyRpartPlot(CARTModel)                            

   

   Figure 6-39. CART model

2. Model Evaluation

   Training set Accuracy = 27%
   library(gmodels)
   
   purchase_pred_train <-predict(CARTModel, train,type ="class")
   CrossTable(train$ProductChoice, purchase_pred_train,
   prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
   dnn =c('actual default', 'predicted default'))
   
       Cell Contents
    |-------------------------|
    |                       N |
    |         N / Table Total |
    |-------------------------|
   
    Total Observations in Table:  28000
   
                   | predicted default
    actual default |         1 |         3 |         4 | Row Total |
    ---------------|-----------|-----------|-----------|-----------|
                 1 |      4253 |      1943 |       859 |      7055 |
                   |     0.152 |     0.069 |     0.031 |           |
    ---------------|-----------|-----------|-----------|-----------|
                 2 |      3452 |      2629 |       935 |      7016 |
                   |     0.123 |     0.094 |     0.033 |           |
    ---------------|-----------|-----------|-----------|-----------|
                 3 |      2384 |      3842 |       679 |      6905 |
                   |     0.085 |     0.137 |     0.024 |           |
    ---------------|-----------|-----------|-----------|-----------|
                 4 |      1901 |      3152 |      1971 |      7024 |
                   |     0.068 |     0.113 |     0.070 |           |
    ---------------|-----------|-----------|-----------|-----------|
      Column Total |     11990 |     11566 |      4444 |     28000 |
    ---------------|-----------|-----------|-----------|-----------|

It looks like a poor model for this dataset. If you observe, the training model doesn't even predict any instance of class 3. We will skip the testing set evaluation. You are encouraged to try the housing dataset used in linear regression to appreciate CART algorithm much better.

6.7.3.4 Chi-Square Automated Interaction Detection: CHAID

In this method, the R code being used for demonstration accepts only nominal or ordinal categorical predictors. For each predictor variable, the algorithm works by merging non-significant categories, wherein each final category of X will result in one child node, if the algorithm chooses X (based on adjusted p-value) to split the node.

The following algorithm is borrowed from the documentation of the CHAID package in R and the classic paper by G. V. Kass (1980), called “An Exploratory Technique for Investigating Large Quantities of Categorical Data .”

1. If X has one category only, stop and set the adjusted p-value to be 1.

2. If X has two categories, go to Step 8.

3. Else, find the allowable pair of categories of X (an allowable pair of categories for ordinal predictor is two adjacent categories, and for nominal predictor is any two categories) that is least significantly different (i.e., the most similar). The most similar pair is the pair whose test statistic gives the largest p-value with respect to the dependent variable Y. How to calculate p-value under various situations will be described in later sections.

4. For the pair having the largest p-value, check if its p-value is larger than a user-specified alpha-level alpha2. If it does, this pair is merged into a single compound category. Then a new set of categories of X is formed. If it does not, then go to Step 7.

5. (Optional) If the newly formed compound category consists of three or more original categories, then find the best binary split within the compound category which p-value is the smallest. Perform this binary split if its p-value is not larger than an alpha-level alpha3.

6. Go to Step 2.

7. (Optional) Any category having too few observations (as compared with a user-specified minimum segment size) is merged with the most similar other category as measured by the largest of the p-values.

8. The adjusted p-value is computed for the merged categories by applying Bonferroni adjustments that are to be discussed later.

Splitting : The best split for each predictor is found in the merging step. The splitting step selects which predictor to be used to best split the node. Selection is accomplished by comparing the adjusted p-value associated with each predictor. The adjusted p-value is obtained in the merging step.

1. Select the predictor that has the smallest adjusted p-value (i.e., most significant).

2. If this adjusted p-value is less than or equal to a user-specified alpha-level alpha4, split the node using this predictor. Otherwise, do not split and the node is considered as a terminal node.

Stopping : The stopping step checks if the tree growing process should be stopped according to the following stopping rules.

1. If a node becomes pure; that is, all cases in a node have identical values of the dependent variable, the node will not be split.

2. If all cases in a node have identical values for each predictor, the node will not be split.

3. If the current tree depth reaches the user specified maximum tree depth limit value, the tree growing process will stop.

4. If the size of a node is less than the user-specified minimum node size value, the node will not be split.

5. If the split of a node results in a child node whose node size is less than the user-specified minimum child node size value, child nodes that have too few cases (as compared with this minimum) will merge with the most similar child node as measured by the largest of the p-values. However, if the resulting number of child nodes is 1, the node will not be split.

6. If the trees height is a positive value and equals the max height.

Let’s now see a demonstration on our purchase prediction dataset.

1. Building the model

   Since CHAID takes all categorical inputs, we are using the attributes CustomerPropensity and IncomeClass as predictor variables.

   library("CHAID")
    Loading required package: partykit
    Loading required package: grid
   ctrl <-chaid:control(minsplit =200, minprob =0.1)
   CHAIDModel <-chaid(ProductChoice ∼CustomerPropensity +IncomeClass, data = train, control = ctrl)
   print(CHAIDModel)
   
    Model formula:
    ProductChoice ∼ CustomerPropensity + IncomeClass
   
    Fitted party:
    [1] root
    |   [2] CustomerPropensity in High
    |   |   [3] IncomeClass in , 1, 2, 3, 9: 2 (n = 169, err = 68.6%)
    |   |   [4] IncomeClass in 4: 3 (n = 628, err = 65.0%)
    |   |   [5] IncomeClass in 5: 4 (n = 1286, err = 70.2%)
    |   |   [6] IncomeClass in 6: 3 (n = 1192, err = 67.0%)
    |   |   [7] IncomeClass in 7: 3 (n = 662, err = 63.4%)
    |   |   [8] IncomeClass in 8: 4 (n = 222, err = 59.9%)
    |   [9] CustomerPropensity in Low: 2 (n = 4778, err = 72.0%)
    |   [10] CustomerPropensity in Medium
    |   |   [11] IncomeClass in , 1, 2, 3, 4, 5, 7: 3 (n = 3349, err = 73.5%)
    |   |   [12] IncomeClass in 6, 8: 4 (n = 1585, err = 71.0%)
    |   |   [13] IncomeClass in 9: 3 (n = 36, err = 44.4%)
    |   [14] CustomerPropensity in Unknown
    |   |   [15] IncomeClass in : 2 (n = 18, err = 0.0%)
    |   |   [16] IncomeClass in 1: 4 (n = 15, err = 53.3%)
    |   |   [17] IncomeClass in 2, 3, 4, 5, 6, 7, 8: 1 (n = 9524, err = 63.6%)
    |   |   [18] IncomeClass in 9: 1 (n = 33, err = 39.4%)
    |   [19] CustomerPropensity in VeryHigh
    |   |   [20] IncomeClass in , 1, 3, 4, 5, 6, 9: 3 (n = 3484, err = 64.5%)
    |   |   [21] IncomeClass in 2, 8: 4 (n = 268, err = 48.5%)
    |   |   [22] IncomeClass in 7: 4 (n = 751, err = 58.2%)
   
    Number of inner nodes:     5
    Number of terminal nodes: 17
   #plot(CHAIDModel)                            

2. Model Evaluation

   The accuracy has no major improvement compared to C5.0 or ID3. However, it’s interesting to see the accuracy is close to what C5.0 algorithm in spite of using only two attributes.

   Training set accuracy: 32%

   library(gmodels)
   
   purchase_pred_train <-predict(CHAIDModel, train)
   CrossTable(train$ProductChoice, purchase_pred_train,
   prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
   dnn =c('actual default', 'predicted default'))
   
       Cell Contents
    |-------------------------|
    |                       N |
    |         N / Table Total |
    |-------------------------|
   
    Total Observations in Table:  28000
   
                   | predicted default
    actual default |      1 |         2 |         3 |         4 | Row Total |
    ---------------|--------|-----------|-----------|-----------|-----------|
                 1 |   3487 |      1367 |      1610 |       591 |      7055 |
                   |  0.125 |     0.049 |     0.058 |     0.021 |           |
    ---------------|--------|-----------|-----------|-----------|-----------|
                 2 |   2617 |      1410 |      2047 |       942 |      7016 |
                   |  0.093 |     0.050 |     0.073 |     0.034 |           |
    ---------------|--------|-----------|-----------|-----------|-----------|
                 3 |   1669 |      1031 |      3001 |      1204 |      6905 |
                   |  0.060 |     0.037 |     0.107 |     0.043 |           |
    ---------------|--------|-----------|-----------|-----------|-----------|
                 4 |   1784 |      1157 |      2693 |      1390 |      7024 |
                   |  0.064 |     0.041 |     0.096 |     0.050 |           |
    ---------------|--------|-----------|-----------|-----------|-----------|
      Column Total |   9557 |      4965 |      9351 |      4127 |     28000 |
    ---------------|--------|-----------|-----------|-----------|-----------|

Testing set accuracy : 32%

purchase_pred_test <-predict(CHAIDModel, test)
CrossTable(test$ProductChoice, purchase_pred_test,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  20002

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   2493 |      1003 |      1048 |       454 |      4998 |
                |  0.125 |     0.050 |     0.052 |     0.023 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   1929 |       901 |      1502 |       663 |      4995 |
                |  0.096 |     0.045 |     0.075 |     0.033 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1263 |       747 |      2034 |       991 |      5035 |
                |  0.063 |     0.037 |     0.102 |     0.050 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |   1318 |       776 |      2008 |       872 |      4974 |
                |  0.066 |     0.039 |     0.100 |     0.044 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |   7003 |      3427 |      6592 |      2980 |     20002 |
 ---------------|--------|-----------|-----------|-----------|-----------|

Figure 6-40. CHAID decision tree

The accuracy has no major improvement compared to C5.0 or ID3. However, it’s interesting to see the accuracy is close to what C5.0 algorithm in spite of using only two attributes.

With 37% and 36% training and test set accuracy respectively, the C5.0 algorithm seems to have done the best among all the others. Although this accuracy might not be sufficient for using in any practical application, this example gives sufficient understanding of how the decision tree algorithms work. We encourage you to create a subset of the given dataset with only two classes and then see how each of these algorithms performs.

6.7.4.1 Boosting

Boosting is an ensemble meta-algorithm in ML that helps in reducing bias and variance and fits a sequence of weak learners on different weighted training observations (more on this in Chapter 8).

We will demonstrate this technique using C5.0 Ensemble model, which is an extension of what we discussed earlier in this chapter by adding a parameter trials = 10 in the C50 function call which means, perform 10 boosting iterations in the model building process.

library(gmodels)

purchase_pred_train <-predict(ModelC50_boostcv10, train)
CrossTable(train$ProductChoice, purchase_pred_train,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  28000

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   3835 |       903 |      1117 |      1200 |      7055 |
                |  0.137 |     0.032 |     0.040 |     0.043 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   2622 |      1438 |      1409 |      1547 |      7016 |
                |  0.094 |     0.051 |     0.050 |     0.055 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1819 |       812 |      2677 |      1597 |      6905 |
                |  0.065 |     0.029 |     0.096 |     0.057 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |   1387 |       686 |      1577 |      3374 |      7024 |
                |  0.050 |     0.024 |     0.056 |     0.120 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |   9663 |      3839 |      6780 |      7718 |     28000 |
 ---------------|--------|-----------|-----------|-----------|-----------|

Testing set accuracy :

purchase_pred_test <-predict(ModelC50_boostcv10, test)
CrossTable(test$ProductChoice, purchase_pred_test,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  20002

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   2556 |       769 |       770 |       903 |      4998 |
                |  0.128 |     0.038 |     0.038 |     0.045 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   2022 |       748 |      1108 |      1117 |      4995 |
                |  0.101 |     0.037 |     0.055 |     0.056 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1406 |       701 |      1540 |      1388 |      5035 |
                |  0.070 |     0.035 |     0.077 |     0.069 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |    970 |       548 |      1201 |      2255 |      4974 |
                |  0.048 |     0.027 |     0.060 |     0.113 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |   6954 |      2766 |      4619 |      5663 |     20002 |
 ---------------|--------|-----------|-----------|-----------|-----------|

Though the training set accuracy increase to 40%, the testing set accuracy has come down, indicating a slight overfitting in this model.

6.7.4.2 Bagging

This is another class of ML meta-algorithm, also known as bootstrap aggregating. It again helps in reducing the variance and overfitting on training observation. Explained next is the process of bagging:

1. Given a set of N training observations, generate m new training sets D_i each of size n where (n <<N ) by uniform sampling with replacement. This sampling is called bootstrap sampling. (Refer to Chapter 3 for more details.)

2. Using these m training set, m models are fitted and the outputs are combined either by averaging the output (regression) or majority voting (for classification).

Certain version of algorithm could have even a sample set of smaller number of attributes than the original dataset like Random Forest. Let’s use the Bagging CART and Random Forest algorithms here to demonstrate.

control <-trainControl(method="repeatedcv", number=5, repeats=2)

# Bagged CART                      
set.seed(100)
CARTBagModel <-train(ProductChoice ∼CustomerPropensity +LastPurchaseDuration +MembershipPoints, data=train, method="treebag", trControl=control)
 Loading required package: ipred
 Loading required package: plyr
 Warning: package 'plyr' was built under R version 3.2.5
 Loading required package: e1071
 Warning: package 'e1071' was built under R version 3.2.5

library(gmodels)

purchase_pred_train <-predict(CARTBagModel, train)
CrossTable(train$ProductChoice, purchase_pred_train,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  28000

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   3761 |      1208 |       885 |      1201 |      7055 |
                |  0.134 |     0.043 |     0.032 |     0.043 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   2358 |      1970 |      1096 |      1592 |      7016 |
                |  0.084 |     0.070 |     0.039 |     0.057 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1685 |      1054 |      2547 |      1619 |      6905 |
                |  0.060 |     0.038 |     0.091 |     0.058 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |   1342 |       885 |      1291 |      3506 |      7024 |
                |  0.048 |     0.032 |     0.046 |     0.125 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |   9146 |      5117 |      5819 |      7918 |     28000 |
 ---------------|--------|-----------|-----------|-----------|-----------|

purchase_pred_test <-predict(CARTBagModel, test)
CrossTable(test$ProductChoice, purchase_pred_test,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  20002

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   2331 |      1071 |       657 |       939 |      4998 |
                |  0.117 |     0.054 |     0.033 |     0.047 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   1844 |      1012 |       928 |      1211 |      4995 |
                |  0.092 |     0.051 |     0.046 |     0.061 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1348 |       875 |      1320 |      1492 |      5035 |
                |  0.067 |     0.044 |     0.066 |     0.075 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |    979 |       759 |      1066 |      2170 |      4974 |
                |  0.049 |     0.038 |     0.053 |     0.108 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |   6502 |      3717 |      3971 |      5812 |     20002 |
 ---------------|--------|-----------|-----------|-----------|-----------|

Testing set Accuracy = 34%

# Random Forest                      
set.seed(100)

rfModel <-train(ProductChoice ∼CustomerPropensity +LastPurchaseDuration +MembershipPoints, data=train, method="rf", trControl=control)
 Loading required package: randomForest
 randomForest 4.6-10
 Type rfNews() to see new features/changes/bug fixes.

 Attaching package: 'randomForest'
 The following object is masked from 'package:ggplot2':

     margin

library(gmodels)

purchase_pred_train <-predict(rfModel, train)
CrossTable(train$ProductChoice, purchase_pred_train,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))                                                                                                                                                                    

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  28000

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   4174 |       710 |      1162 |      1009 |      7055 |
                |  0.149 |     0.025 |     0.042 |     0.036 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   2900 |      1271 |      1507 |      1338 |      7016 |
                |  0.104 |     0.045 |     0.054 |     0.048 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1970 |       701 |      2987 |      1247 |      6905 |
                |  0.070 |     0.025 |     0.107 |     0.045 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |   1564 |       608 |      1835 |      3017 |      7024 |
                |  0.056 |     0.022 |     0.066 |     0.108 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |  10608 |      3290 |      7491 |      6611 |     28000 |
 ---------------|--------|-----------|-----------|-----------|-----------|

purchase_pred_test <-predict(rfModel, test)
CrossTable(test$ProductChoice, purchase_pred_test,
prop.chisq =FALSE, prop.c =FALSE, prop.r =FALSE,
dnn =c('actual default', 'predicted default'))

    Cell Contents
 |-------------------------|
 |                       N |
 |         N / Table Total |
 |-------------------------|

 Total Observations in Table:  20002

                | predicted default
 actual default |      1 |         2 |         3 |         4 | Row Total |
 ---------------|--------|-----------|-----------|-----------|-----------|
              1 |   2774 |       611 |       845 |       768 |      4998 |
                |  0.139 |     0.031 |     0.042 |     0.038 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              2 |   2210 |       639 |      1194 |       952 |      4995 |
                |  0.110 |     0.032 |     0.060 |     0.048 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              3 |   1531 |       602 |      1774 |      1128 |      5035 |
                |  0.077 |     0.030 |     0.089 |     0.056 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
              4 |   1100 |       462 |      1389 |      2023 |      4974 |
                |  0.055 |     0.023 |     0.069 |     0.101 |           |
 ---------------|--------|-----------|-----------|-----------|-----------|
   Column Total |   7615 |      2314 |      5202 |      4871 |     20002 |
 ---------------|--------|-----------|-----------|-----------|-----------|

6.9.2.1 Hierarchal Clustering

Hierarchical clustering is based on the connectivity model of clusters. The steps involved in the clustering process are:

1. Start with N clusters, N is number of elements (i.e., assign each element to its own cluster). In other words distances (similarities) between the clusters are equal to the distances (similarities) between the items they contain.

2. Now merge pairs of clusters with the closest to other (most similar clusters) (e.g., the first iteration will reduce the number of clusters to N - 1).

3. Again compute the distance (similarities) and merge with closest one.

4. Repeat Steps 2 and 3 to exhaust the items until you get all data points in one cluster.

Now you will get a dendogram of clustering for all levels. Choose a cutoff at how many clusters you want to have by stopping the iteration at the right point.

In R, we use the hclust() function. Hierarchical cluster analysis on a set of dissimilarities and methods for analyzing it. This is part of the stats package.

Another important function used here is dist(); this function computes and returns the distance matrix computed by using the specified distance measure to compute the distances between the rows of a data matrix. By default, it is Euclidean distance.

Mathematically, Euclidean distance is given as

In Cartesian coordinates, Euclidean distance between two vectors p = (p1, p2,…, pn) and q = (q1, q2,…, qn) are two points in Euclidean. n-space is given by

Let’s apply the hclust function and create our clusters.

# apply the hierarchal clustering algorithm                    
clusters <-hclust(dist(Data_House_Worth[,2:3]))

#Plot the dendogram                    
plot(clusters)

Figure 6-42. Cluster dendogram

Now we can see there are number of possible places where we can choose clusters. We will show cross-plot with 2, 3, and 4 clusters.

# Create different number of clusters                    
clusterCut_2 <-cutree(clusters, 2)
#table the clustering distribution with actual networth                    
table(clusterCut_2,Data_House_Worth$HouseNetWorth)

 clusterCut_2 High Low Medium
            1  104 135     51
            2   26   0      0
clusterCut_3 <-cutree(clusters, 3)
#table the clustering distribution with actual networth
table(clusterCut_3,Data_House_Worth$HouseNetWorth)

 clusterCut_3 High Low Medium
            1    0 122      1
            2  104  13     50
            3   26   0      0
clusterCut_4 <-cutree(clusters, 4)
#table the clustering distribution with actual networth
table(clusterCut_4,Data_House_Worth$HouseNetWorth)

 clusterCut_4 High Low Medium
            1    0 122      1
            2   34   9     50
            3   70   4      0
            4   26   0      0

These three separate tables show how much the clusters able to capture the feature of net worth. Let's limit ourselves to three clusters as we know from additional knowledge that there are three groups of house by net worth. In statistical terms, the best number of clusters can be chosen by using elbow method and/or semi-partial R-Square, validity index Pseudo F. More details can be learned from Timm, Neil H., Applied Multivariate Analysis, Springer, 2002.

ggplot(Data_House_Worth, aes(StoreArea, LawnArea, color = HouseNetWorth)) +
geom_point(alpha =0.4, size =3.5) +geom_point(col = clusterCut_3) +
scale_color_manual(values =c('black', 'red', 'green'))

Figure 6-43. Cluster plot with LawnArea and StoreArea

You can see most of our “high”, “medium” and “low” NetHouseworth points are overlapping with the three cluster created by hclust. In hindsight, if we didn't know the actual networth scales, we could have retrieved this information from this cluster analysis.

In next section, we apply another clustering algorithm to the same data and see how the results look.

6.9.2.2 Centroid-Based Clustering

The following text borrowed from the original paper, A K-Means Clustering Algorithmby Hartigan et. al [6] gives the most crisp and precise description of the way k-means algorithm works, it says:

• The aim of the K-means algorithm is to divide M points in N dimensions into K clusters so that the within-cluster sum of squares is minimized. It is not practical to require that the solution has minimal sum of squares against all partitions, except when M, N are small and K = 2. We seek instead "local" optima, solution such that no movement of a point from one cluster to another will reduce the within-cluster sum of squares.

where, within cluster sum of squares (WCSS) is sum of distance of each observation in a cluster to its centroid. More technically, for a set of observations (x₁, x₂, …, x_n) and set of k clusters C = {C₁, C₂, …, C_k}

μ_i is the mean of points in C_i

Algorithm

In the simplest form of the algorithm , it has two steps:

• Assignment: Assign each observation to the cluster that gives the minimum within cluster sum of squares (WCSS).

• Update: Update the centroid by taking the mean of all the observation in the cluster.

These two steps are iteratively executed until the assignments in any two consecutive iteration don’t change, meaning either a point of local or global optima (not always guaranteed) is reached.

Let's use our HouseNetWorth data to show k-means clustering. Unlike the hierarchical cluster, to find the optimal value for k (number of cluster) here, we will use an Elbow curve. The curve shows the percentage of variance explained as a function of the number of clusters.

# Elbow Curve                    

wss <-(nrow(Data_House_Worth)-1)*sum(apply(Data_House_Worth[,2:3],2,var))
for (i in 2:15) {
  wss[i] <-sum(kmeans(Data_House_Worth[,2:3],centers=i)$withinss)
}
plot(1:15, wss, type="b", xlab="Number of Clusters",ylab="Within groups sum of squares")

The elbow curve suggests that with three clusters, we were able to explain most of the variance in data. Beyond four clusters adding more clusters is not helping with explaining the groups (as the plot in Figure 6-44, shows, WCSS is saturating after three). Hence, we will once again choose k=3 clusters.

Figure 6-44. Elbow curve for varying values of k (number of clusters) on the x axis

set.seed(917)
#Run k-means cluster of the dataset                    
Cluster_kmean <-kmeans(Data_House_Worth[,2:3], 3, nstart =20)

#Tabulate the cross distribution                    
table(Cluster_kmean$cluster,Data_House_Worth$HouseNetWorth)

     High Low Medium
   1   84   0      0
   2   46  13     50
   3    0 122      1

The table shows cluster 1 has only of “High” worth, while clusters 2 and 3 have all of it. While cluster 3 only represents the low worth except for one point. Here is the plot of clusters against the actual networth.

Cluster_kmean$cluster <-factor(Cluster_kmean$cluster)
ggplot(Data_House_Worth, aes(StoreArea, LawnArea, color = HouseNetWorth)) +
geom_point(alpha =0.4, size =3.5) +geom_point(col = Cluster_kmean$cluster) +
scale_color_manual(values =c('black', 'red', 'green'))

In the Figure 6-45, we can see in k-means have captured the clusters very well.

Figure 6-45. Cluster plot using k-means

6.9.2.3 Distribution-Based Clustering

Distribution methods are iterative methods to fit a set of dataset into clusters by optimizing distributions of datasets in clusters. Gaussian distribution is nothing but normal distribution. This method works in three steps:

1. First randomly choose Gaussian parameters and fit it to set of data points.

2. Iteratively optimize the distribution parameters to fit as many points it can.

3. Once it converges to a local minima, you can assign data points closer to that distribution of that cluster.

Although this algorithm create complex models, it does capture correlation and dependence among the attributes . The downside is that these methods usually suffer from an overfitting problem. Here, we show example of algorithm on our house worth data.

library(EMCluster, quietly =TRUE)

ret <-init.EM(Data_House_Worth[,2:3], nclass =3)
ret
 Method: em.EMRnd.EM
  n = 316, p = 2, nclass = 3, flag = 0, logL = -1871.0336.
 nc:
 [1]  48 100 168
 pi:
 [1] 0.2001 0.2508 0.5492
ret.new <-assign.class(Data_House_Worth[,2:3], ret, return.all =FALSE)

#This has assigned a class to each case                    
str(ret.new)
 List of 2
  $ nc   : int [1:3] 48 100 168
  $ class: num [1:316] 1 3 3 1 3 3 3 3 3 3 ...
# Plot results                    
plotem(ret,Data_House_Worth[,2:3])

Figure 6-46. Clustering plot-based on the EM algorithm

The low worth and high worth is captured well in the algorithm, while the medium ones are far more scattered, which is not well represented in the cluster. Now let’s see how the scatter plot looks by clustering with this method.

ggplot(Data_House_Worth, aes(StoreArea, LawnArea, color = HouseNetWorth)) +
geom_point(alpha =0.4, size =3.5) +geom_point(col = ret.new$class) +
scale_color_manual(values =c('black', 'red', 'green'))

Figure 6-47. Cluster plot for the EM algorithm

Again, the plot is good for high and low classes, but isn’t doing very well for the medium class. There are some cases scattered in high LawnArea values as well, but comparatively it’s still captured better in the high cluster. If you observe, this method isn’t as good as what we saw in the case of hclust or k-means as there are many more overlaps of points between two clusters.

6.9.2.4 Density-Based Clustering

Density-based spatial clustering of applications with noise (DBSCAN) is a data clustering algorithm proposed by Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu in 1996.

This algorithm works on a parametric approach. The two parameters involved in this algorithm are:

• e: The radius of our neighborhoods around a data point p.

• minPts: The minimum number of data points we want in a neighborhood to define a cluster.

Once these parameters are defined, the algorithm divides the data points into three points:

• Core points: A point p is a core point if at least minPts points are within distance ε (ε is the maximum radius of the neighborhood from p) of it (including p).

• Border points: A point q is border from p if there is a path p1, …, pn with p1 = p and pn = q, where each pi+1 is directly reachable from pi (all the points on the path must be core points, with the possible exception of q).

• Outliers: All points not reachable from any other point are outliers .

The steps in DBSCAN are simple after defining the previous steps:

1. Pick at random a point which is not assigned to a cluster and calculate its neighborhood. If, in the neighborhood, this point has minPts then make a cluster around that; otherwise, mark it as outlier.

2. Once you find all the core points, start expanding that to include border points.

3. Repeat these steps until all the points are either assigned to a cluster or to an outlier.

   library(dbscan)
    Warning: package 'dbscan' was built under R version 3.2.5
   cluster_dbscan <-dbscan(Data_House_Worth[,2:3],eps=0.8,minPts =10)
   cluster_dbscan
    DBSCAN clustering for 316 objects.
    Parameters: eps = 0.8, minPts = 10
    The clustering contains 5 cluster(s) and 226 noise points.
   
      0   1   2   3   4   5
    226  10  25  24  15  16
   
    Available fields: cluster, eps, minPts
   #Display the hull plot                            
   hullplot(Data_House_Worth[,2:3],cluster_dbscan$cluster)

Figure 6-48. Plot for convex cluster hulls for the EM algorithm

The result shows DBSCAN has found five clusters and assigned 226 cases as noise/outliers. The hull plot shows the separation is good , so we can play around with the parameters to get more generalized or specialized clusters.

6.9.3.1 Dunn Index

J Dunn proposed this index in 1974 through his published work titled, “Well Separated Clusters and Optimal Fuzzy Partitions,” Journal of Cybernetics.[7]

The Dunn index aims to identify dense and well-separated clusters. It is defined as the ratio between the minimal intercluster distances to the maximal intracluster distance. For each cluster partition, the Dunn index can be calculated using the following formula. where d(i,j) represents the distance between cluster i and j, and d'(k) measures the intra-cluster distance of cluster k.

library(clValid)
#Showing for hierarchical cluster with clusters = 3                    
dunn(dist(Data_House_Worth[,2:3]), clusterCut_3)
[1] 0.009965404                    

The Dunn Index has a value between zero and infinity and should be maximized . The Dunn score with high value are more desirable; here the value is too low suggesting it’s not a good cluster.

6.9.3.2 Silhouette Coefficient

The silhouette coefficient contrasts the average distance to elements in the same cluster with the average distance to elements in other clusters. Objects with a high silhouette value are considered well clustered; objects with a low value may be outliers.

library(cluster)

#Showing for k-means cluster with clusters = 3                    
sk <-silhouette(clusterCut_3,dist(Data_House_Worth[,2:3]))

plot(sk)

Figure 6-49. Silhouette plot

The silhouette plot shows how the three clusters behave on silhouette width.

6.9.4.1 Rand Measure

The Rand index is similar to classification rate in multi-class classification problems. This measures how many items that are returned by the cluster and expert (labeled) are common and how many differ. If we assume expert labels (or external labels) to be correct than this measure the correct classification rate. It can be computed using the following formula [8]: where TP is the number of true positives, TN is the number of true negatives, FP is the number of false positives, and FN is the number of false negatives.

#Unsign result from EM Algo                    
library(EMCluster)
clust <-ret.new$class
orig <-ifelse(Data_House_Worth$HouseNetWorth == "High",2,
ifelse(Data_House_Worth$HouseNetWorth == "Low",1,2))
RRand(orig, clust)
    Rand adjRand  Eindex
  0.7653  0.5321  0.4099

The Rand index value is high, 0.76, indicating a good clustering fit by our EM method.

6.9.4.2 Jaccard Index

The Jaccard index is similar to Rand index. The Jaccard index measures the overlap of external labels and labels generated by the cluster algorithms. The Jaccard index value varies between 0 and 1, 0 implying no overlap while 1 means identical datasets. The Jaccard index is defined by the following formula:

where TP is the number of true positives, FP is the number of false positives, and FN is the number of false negatives.

#Unsign result from EM Algo                    
#Unsign result from EM Algo                    
library(EMCluster)
clust <-ret.new$class
orig <-ifelse(Data_House_Worth$HouseNetWorth == "High",2,
ifelse(Data_House_Worth$HouseNetWorth == "Low",1,2))
Jaccard.Index(orig, clust)
 [1] 0.1024096

The index value is low, suggesting only 10% values are common. This implies the overlap on the original and cluster is low. Not a good cluster formation .

6.10.1.1 Support

Support is the proportion of transactions in which an item set appears. We will denote it by supp(X), where X is an item set. For example, and .

6.10.1.2 Confidence

While support helps in understanding the strength of an item set, confidence indicates the strength of a rule. For example, in the rule , confidence is the conditional probability of finding the item set {Jams spreads} (RHS) in transactions under the condition that these transactions also contain the {bread and cake, baking needs } (LHS).

More technically, confidence is defined as

,

The rule has a confidence of , which means 50% of the time when the customer buys {bread and cake, baking needs }, they buy {Jams spreads} as well.

6.10.1.3 Lift

If the LHS and RHS of a rule is independent of each other, i.e., the purchase of one doesn’t depend on the other, then lift is a ratio between the observed support to the expected support. So, if lift = 1, LHS and RHS are independent of each other and it doesn’t make any sense to have such a rule, whereas if the lift is > 1, it tells the degree to which the two occurrences are dependent on one another.

More technically

The rule has a lift of , which means people who buy {bread and cake, baking needs } are nearly 1.25 times more likely to buy {Jams spreads} than the typical customer.

There are some other measures like conviction, leverage, and collective strength; however, these three are found to be widely used in all the literature and sufficient for the understanding of the Apriori algorithm.

Things might work well for small examples like these, however, in practicality, a typical database of transactions is very large. Agrawal et. al. proposed a simple yet fast algorithm to work on large databases.

1. In the first step, all possible candidate item sets are generated.

2. Then the rules are formed using these candidate item sets.

3. The rule with the highest lift is generally the preferred choice.

Later, many variations of the Apriori algorithm have been devised but in its original form. Here are the steps involved in the Apriori algorithm for generating candidate item sets:

1. Determine the support of the one element item sets (a.k.a. singletons) and discard the infrequent items/item sets.

2. Form candidate item sets with two items (both items must be frequent), determine their support, and discard the infrequent item sets.

3. Form candidate item sets with three items (all contained pairs must be frequent), determine their support, and discard the infrequent item sets.

4. Continue by forming candidate item sets with four, five, and so on , items until no candidate item set is frequent.

6.10.2.1 Apriori

The support and confidence could be modified to allow for flexibility in this model.

1. Model Building

   We are using the Apriori function from the package arules to demonstrate the market basket analysis with the constant values for support and confidence:

   library(arules)
   
   MarketBasketRules<-apriori(MarketBasket, parameter =list(support =0.2, confidence =0.8, minlen =2))
   MarketBasketRules
   
    Parameter specification:
     confidence minval smax arem  aval originalSupport support minlen maxlen
            0.8    0.1    1 none FALSE            TRUE     0.2      2     10
     target   ext
      rules FALSE
   
    Algorithmic control:
     filter tree heap memopt load sort verbose
        0.1 TRUE TRUE  FALSE TRUE    2    TRUE
   
    writing ... [190 rule(s)] done [0.00s].
    creating S4 object  ... done [0.00s].

2. ModelSummary

   The top five rules and lift:

   {beef,fruit} => {vegetables} - 1.291832
   
   {biscuits,bread and cake,frozen foods,vegetables} => {fruit} - 1.288442
   
   {biscuits,milk cream,vegetables} => {fruit} - 1.275601
   
   {bread and cake,fruit,sauces gravy pkle} =>{vegetables} - 1.273765
   
   {biscuits, bread and cake,vegetables} => {fruit} - 1.270252
   
   summary(MarketBasketRules)
    set of 190 rules
   
    rule length distribution (lhs + rhs):sizes
     2  3  4  5
     4 93 84  9
   
       Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
      2.000   3.000   3.000   3.516   4.000   5.000
   
    summary of quality measures:
        support         confidence          lift      
     Min.   :0.2002   Min.   :0.8003   Min.   :1.106  
     1st Qu.:0.2082   1st Qu.:0.8164   1st Qu.:1.138  
     Median :0.2260   Median :0.8299   Median :1.160  
     Mean   :0.2394   Mean   :0.8327   Mean   :1.169  
     3rd Qu.:0.2642   3rd Qu.:0.8479   3rd Qu.:1.187  
     Max.   :0.3980   Max.   :0.8941   Max.   :1.292  
   
    mining info:
             data ntransactions support confidence
     MarketBasket          4601     0.2        0.8

Sorting grocery rules by lift:

inspect(sort(MarketBasketRules, by ="lift")[1:5])
   lhs                    rhs            support confidence     lift
 1 {beef,                                                           
    fruit}             => {vegetables} 0.2143012  0.8313659 1.291832
 2 {biscuits,                                                       
    bread and cake,                                                 
    frozen foods,                                                   
    vegetables}        => {fruit}      0.2019126  0.8294643 1.288442
 3 {biscuits,                                                       
    milk cream,                                                     
    vegetables}        => {fruit}      0.2206042  0.8211974 1.275601
 4 {bread and cake,                                                 
    fruit,                                                          
    sauces gravy pkle} => {vegetables} 0.2184308  0.8197390 1.273765
 5 {biscuits,                                                       
    bread and cake,                                                 
    vegetables}        => {fruit}      0.2642904  0.8177539 1.270252
# store as  data frame                    
MarketBasketRules_df <-as(MarketBasketRules, "data.frame")
str(MarketBasketRules_df)
 'data.frame':    190 obs. of  4 variables:
  $ rules     : Factor w/ 190 levels "{baking needs,beef} => {bread and cake}",..: 189 106 163 174 60 116 115 118 16 120 ...
  $ support   : num  0.203 0.226 0.223 0.398 0.201 ...
  $ confidence: num  0.835 0.811 0.804 0.8 0.815 ...
  $ lift      : num  1.15 1.12 1.11 1.11 1.13 ...

6.10.2.2 Eclat

Eclat is another algorithm for association rule mining. This algorithm uses simple intersection operations for equivalence class clustering along with bottom-up lattice traversal. The following two references talks about the algorithm in detail:

• Mohammed J. Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, and Wei Li. (1997, “New Algorithms for Fast Discovery of Association Rules,” Technical Report 651, Computer Science Department, University of Rochester, Rochester, NY 14627.

• Christian Borgelt (2003), “Efficient Implementations of Apriori and Eclat,” Workshop of Frequent Item Set Mining Implementations (FIMI), Melbourne, FL, USA.

1. ModelBuilding

   library(arules)
   
   With support = 0.2
   
   MarketBasketRules_Eclat<-eclat(MarketBasket, parameter =list(support =0.2, minlen =2))
   
    parameter specification:
     tidLists support minlen maxlen            target   ext
        FALSE     0.2      2     10 frequent itemsets FALSE
   
    algorithmic control:
     sparse sort verbose
          7   -2    TRUE
   
    writing  ... [531 set(s)] done [0.00s].
    Creating S4 object  ... done [0.00s].
   With support = 0.1
   MarketBasketRules_Eclat<-eclat(MarketBasket, parameter =list(supp =0.1, maxlen =15))
   
    parameter specification:
     tidLists support minlen maxlen            target   ext
        FALSE     0.1      1     15 frequent itemsets FALSE
   
    algorithmic control:
     sparse sort verbose
          7   -2    TRUE
   
    writing  ... [7503 set(s)] done [0.00s].
    Creating S4 object  ... done [0.00s].
   Observe the increase in the number of rules by decreasing the support. Experiment with the support value to see how the rules are changing.

2. Model Summary

The top five rules and support:

{bread and cake,milk cream} 0.5079331

{bread and cake,fruit} 0.5053249

{bread and cake,vegetables} 0.4994566

{fruit,vegetables} 0.4796783

{baking needs,bread and cake} 0.4762008

summary(MarketBasketRules_Eclat) # the model with support = 0.1
 set of 531 itemsets

 most frequent items:
 bread and cake     vegetables          fruit   baking needs   frozen foods
            196            137            136            130            122
        (Other)
            772

 element (itemset/transaction) length distribution:sizes
   2   3   4   5
 187 260  81   3

    Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
   2.000   2.000   3.000   2.812   3.000   5.000

 summary of quality measures:
     support      
  Min.   :0.2002  
  1st Qu.:0.2118  
  Median :0.2378  
  Mean   :0.2539  
  3rd Qu.:0.2768  
  Max.   :0.5079  

 includes transaction ID lists: FALSE

 mining info:
          data ntransactions support
  MarketBasket          4601     0.2

Sorting grocery rules by support :

inspect(sort(MarketBasketRules_Eclat, by ="support")[1:5])
   items              support
 1 {bread and cake,          
    milk cream}     0.5079331
 2 {bread and cake,          
    fruit}          0.5053249
 3 {bread and cake,          
    vegetables}     0.4994566
 4 {fruit,                   
    vegetables}     0.4796783
 5 {baking needs,            
    bread and cake} 0.4762008
# store as  data frame                    
groceryrules_df <-as(groceryrules, "data.frame")
str(groceryrules_df)
 'data.frame':    531 obs. of  2 variables:
  $ items  : Factor w/ 531 levels "{baking needs,beef,bread and cake}",..: 338 250 239 358 357 302 96 334 426 341 ...
  $ support: num  0.203 0.213 0.226 0.203 0.2 ...

The results are shown based on the support of the item sets rather than the lift. This is because Eclat only mines frequent item sets. There are no output of the lift measure, for which Apriori is a more suitable approach. Nevertheless, this output shows the top five item sets with highest support, which could be further used to generate rules.

6.10.3.1 User-Based Collaborative Filtering (UBCF)

The UBCF algorithm works on the assumption that users with similar preferences will rate similarly. For example, if a user A likes spaghetti noodles with a rating of 4 and if user B has similar taste as user A, he will rate the spaghetti close enough to 4. This approach might not work if you consider only two users; however if instead of two, we find three users closest to user A and consider their rating for spaghetti noodles in a collaborative manner (could be as simple as taking an average), we could produce a much accurate rating of user B to spaghetti noodles. For a given user-product (item) rating matrix, as shown in Figure 6-52, the algorithm works as follows:

Figure 6-52. Illustration of UBCF

1. We compute the similarity between two users using either cosine similarity or Pearson correlation, two of the most widely used approaches for comparing two vectors.

2. Based on the similarity measure, choose the k-nearest neighbor to the user to whom recommendation has to be given.

3. Take an average of the ratings of the k-nearest neighbors.

4. Recommend the top N products based on the rating vector.

Some additional notes about the previous algorithm:

• We could normalize the rating matrix to remove any user bias.

• In this approach we treat each user equally in terms of similarity; however, it’s possible that some users in the neighborhood are more similar to U_a than others. In this case, we could assign certain weights to allow for some flexibility.

As shown in Figure 6-54, for a new user, U_a, with a rating vector <2.0,NA,2.0,NA,5.0,NA,NA,3.0,3.0>, we would like to find the missing ratings. Based on the Pearson correlation, for k = 3, the users, U₄, U₈, and U₅ are the nearest neighbors to U_a. Take an average of ratings by these users and you will get <2.7,3.3,3.0,1.0,5.0,1.3,2.0,2.7,2.0>. We might recommend product P5 and P2 to U_a based on these rating vectors.

6.10.3.2 Item-Based Collaborative Filtering (IBCF)

IBCF is similar to UBCF, but here items are compared with items based on the relationship between items inferred from the rating matrix. A similarity matrix is thus obtained using again either cosine or Pearson correlation .

Since IBCF removes any user bias and could be precomputed, it’s generally considered more efficient but is known to produce slightly inferior results to UBCF.

Let’s now use Amazon Fine Food Review and apply the UBCF and IBCF algorithms from the recommender lab package in R.

1. Loading Data

   library(data.table)
   
   fine_food_data <-read.csv("Food_Reviews.csv",stringsAsFactors =FALSE)
   fine_food_data$Score <-as.factor(fine_food_data$Score)
   
   str(fine_food_data[-10])                                                                                                                      
    'data.frame':    35173 obs. of  9 variables:
     $ Id                    : int  1 2 3 4 5 6 7 8 9 10 ...
     $ ProductId             : chr  "B001E4KFG0" "B00813GRG4" "B000LQOCH0" "B000UA0QIQ" ...
     $ UserId                : chr  "A3SGXH7AUHU8GW" "A1D87F6ZCVE5NK" "ABXLMWJIXXAIN" "A395BORC6FGVXV" ...
     $ ProfileName           : chr  "delmartian" "dll pa" "Natalia Corres "Natalia Corres"" "Karl" ...
     $ HelpfulnessNumerator  : int  1 0 1 3 0 0 0 0 1 0 ...
     $ HelpfulnessDenominator: int  1 0 1 3 0 0 0 0 1 0 ...
     $ Score                 : Factor w/ 5 levels "1","2","3","4",..: 5 1 4 2 5 4 5 5 5 5 ...
     $ Time                  : int  1303862400 1346976000 1219017600 1307923200 1350777600 1342051200 1340150400 1336003200 1322006400 1351209600 ...
     $ Summary               : chr  "Good Quality Dog Food" "Not as Advertised" ""Delight" says it all" "Cough Medicine" ...

2. Data Preparation

   library(caTools)
   
   # Randomly split data and use only 10% of the dataset                            
   set.seed(90)
   split =sample.split(fine_food_data$Score, SplitRatio =0.05)
   
   fine_food_data =subset(fine_food_data, split ==TRUE)
   
   select_col <-c("UserId","ProductId","Score")
   
   fine_food_data_selected <-fine_food_data[,select_col]
   rownames(fine_food_data_selected) <-NULL
   fine_food_data_selected$Score =as.numeric(fine_food_data_selected$Score)
   
   #Remove Duplicates                            
   
   fine_food_data_selected <-unique(fine_food_data_selected)

3. Creation Rating Matrix

   We will use a function called dcast to create the rating matrix from the review ratings from the Amazon Fine Food Review dataset:

   library(recommenderlab)
   
   #RatingsMatrix                            
   
   RatingMat <-dcast(fine_food_data_selected,UserId ∼ProductId, value.var ="Score")
   User=RatingMat[,1]
   Product=colnames(RatingMat)[2:ncol(RatingMat)]
   RatingMat[,1] <-NULL
   RatingMat <-as.matrix(RatingMat)
   dimnames(RatingMat) =list(user = User , product = Product)
   
   realM <-as(RatingMat, "realRatingMatrix")                                                                                                                      

4. Exploring the Rating Matrix

   #distribution of ratings
   hist(getRatings(realM), breaks=15, main ="Distribution of Ratings", xlab ="Ratings", col ="grey")

   

   Figure 6-53. Distribution of ratings

   #Sparse Matrix Representation
   head(as(realM, "data.frame"))
                   user       item rating
    467  A10012K7DF3SBQ B000SATIG4      3
    1381 A10080F3BO83XV B004BKP68Q      5
    428  A1031BS8KG7I02 B000PDY3P0      5
    1396 A1074ZS6AOHJCU B004JQTAKW      1
    951   A107MO1RZUQ8V B001RVFDOO      5
    1520 A108GQ9A91JIP4 B005K4Q1VI      1
   #The realRatingMatrix can be coerced back into a matrix which is identical to the original matrix
   identical(as(realM, "matrix"),RatingMat)                                                                                                                      
    [1] TRUE
   #Scarcity in Rating Matrix
   image(realM, main ="Raw Ratings")

   

   Figure 6-54. Raw ratings by users

5. UBCF Recommendation Model

   #UBCF Model                            
   r_UBCF <-Recommender(realM[1:1700], method ="UBCF")
   r_UBCF
    Recommender of type 'UBCF' for 'realRatingMatrix'
    learned using 1700 users.
   #List of objects in the model output                            
   names(getModel(r_UBCF))
    [1] "description" "data"        "method"      "nn"          "sample"     
    [6] "normalize"   "verbose"
   #Recommend product for the rest of 29 left out observations                            
   recom_UBCF <-predict(r_UBCF, realM[1700:1729], n=5)
   recom_UBCF
    Recommendations as 'topNList' with n = 5 for 30 users.                                                                                                                      
   #Display the recommendation                            
   reco <-as(recom_UBCF, "list")
   reco[lapply(reco,length)>0]
    $AY6MB5S44GMH4
    [1] "B000084EK5" "B000084EKL" "B000084ETV" "B00008DF91" "B00008JOL0"
   
    $AYOMAHLWRQHUG
    [1] "B000084EK5" "B000084EKL" "B000084ETV" "B00008DF91" "B00008JOL0"
   
    $AYX86RC7QV2UT
    [1] "B000084EK5" "B000084EKL" "B000084ETV" "B00008DF91" "B00008JOL0"
   
    $AZ4IFJ01WKBTB
    [1] "B000084EK5" "B000084EKL" "B000084ETV" "B00008DF91" "B00008JOL0"

   Similarly, you can extract such recommendations for IBCF as well.

6. Evaluation

   set.seed(2016)
   scheme <-evaluationScheme(realM[1:1700], method="split", train = .9,
   k=1, given=1, goodRating=3)
   
   scheme
    Evaluation scheme with 1 items given
    Method: 'split' with 1 run(s).
    Training set proportion: 0.900
    Good ratings: >=3.000000
    Data set: 1700 x 867 rating matrix of class 'realRatingMatrix' with 1729 ratings.
   algorithms <-list(
   "random items" =list(name="RANDOM", param=NULL),
   "popular items" =list(name="POPULAR", param=NULL),
   "user-based CF" =list(name="UBCF", param=list(nn=50)),
   "item-based CF" =list(name="IBCF", param=list(k=50))
   )
   
   results <-evaluate(scheme, algorithms, type ="topNList",
   n=c(1, 3, 5, 10, 15, 20))
    RANDOM run fold/sample [model time/prediction time]
      1  [0sec/0.91sec]
    POPULAR run fold/sample [model time/prediction time]
      1  [0.03sec/2.14sec]
    UBCF run fold/sample [model time/prediction time]
      1  [0sec/71.13sec]
    IBCF run fold/sample [model time/prediction time]
      1  [292.13sec/0.46sec]
   plot(results, annotate=c(1,3), legend="bottomright")                                                                                                                      

Figure 6-55. True positive ratio versus false positive ratio

You can see that the ROC curve shows the poor accuracy of these recommendations on this data. It could be because of sparsity and high bias in ratings.

6.11.6.1 Evolutionary Methods

Evolutionary methods are derived from the evolutionary process in biology, and evolution can be in terms of reproduction, mutation, selection, and recombination. A fitness function is used to determine the performance of model, and based on this function we select our final model.

The steps involved in this learning method are as follows:

1. Create a population of solutions (i.e., weights on all the inputs).

2. Apply the fitness function to see how this initial population performed with initial population.

3. Select the best solution set from Step 2, and then breed with other solutions (e.g., change weight on one variable with other solution).

4. Evaluate again on the fitness function, and continue with Steps 3 and 4 until you get a solution.

Genetic algorithms are inspired by this evolutionary process.

6.11.6.2 Gene Expression Programming

Gene expression programming is also a type of evolutionary learning algorithm. The learning method is inspired by home gene expression happens in biological body. The gene expression learning program are implemented as complex tree structures adapting to change in sizes, shape, and composition.