Modified Bagging in Linear Discriminant Analysis: Machine Learning

Abstract

The main idea of this work is the use of machine learning of BAGGING or Bootstrap AGGregatiING, which is extended to average the classifiers based on a distance function. The idea of this function is to find the shortest distance from each data point to the classification boundary by using ‘Manhattan’ distance in decision trees and alternative distance measure is the ‘Mahalanobis’ distance used for Linear Discriminant Analysis or LDA, called modified bagging in this work. Thus providing a weighted voting system instead of equal weight voting, the classification error is reduced. Modified bagging is a viable option to reduce the variance which is a component of the classification error. Referring to the analysis, we conclude that modified bagging gives statistically significant improvement in Ripley’s data set with different bootstrap sample sizes.

1. Introduction

Advances in data collection and processing technology have led to a revolution in database management. Classification plays a key role in understanding, summarising and finding useful patterns in data, for example in medicine, agriculture, archaeology, taxonomy and industry. Statistical classification has been traditionally developed by not only statisticians but also engineers and computer scientists such as machine learning and neural network.

There are two main aspects to classification: cluster analysis and discriminant analysis. The goal of cluster analysis or unsupervised learning is to identify classes from data, that is, to determine the number of clusters and assign each observation to a specific class. Each cluster can be defined as a region of observations that are similar enough to each other to be grouped together. Cluster analysis is applied in medicine to cluster the incidences of specific types of tumours and in history to group archaeological findings. Recent applications of clustering techniques have come from biology, for instance discovery of tumour classes using gene expression data (bioinformatics). A popular clustering algorithm is the k-means algorithm [1], which aims to partition a given data set into k clusters based on squared distance.

By contrast, in discriminant analysis or supervised learning, we have a training sample (or learning sample) of data, in which we observe the outcome and feature measurements of a set of objects. Using this data, the aim then is to construct (or build) a classification rule to predict the outcome for unseen objects (test set). Contexts in which discriminant analysis is fundamental include, as examples: (i) Mechanical procedure for sorting a collection of coins into several classes (e.g. 10, 20, 50 pence or 1 pound), in which the obtained measurements could be diameter, shape or weight. A measurement on which the coins differ can be used for sorting the coins into pre-specified classes. (ii) Patients who experience a heart attack admitted to a hospital; data are often obtained, such as heart rate, blood pressure, patient’s age and medical history, and a wide variety of other information. It would be useful to develop criteria to differentiate low-risk from high-risk patients. (iii) In social sciences, people use information collected from polls to predict the outcome of elections. Note that in the statistical literature, supervised learning problems (classification problems) are usually, but not always, referred to as discrimination.

All of these problems have in common the requirement of using knowledge of previously classified data to build a classifier in order to assign a class to a new observation. We refer to the construction or building of classification rules from data as discrimination, classification or learning. The quality of a classifier is characterised by the misclassification error rate on the test set. The main assumption is that observations in the test set are assumed to be generated from the same underlying distribution as the observations in the training set. Almost all methods of discriminant analysis can be seen as ways for the construction of a classifier.

Two contrasting points of view have been taken. We could take a parametric family, which can only be applied when the general parametric form of the probability density functions (pdfs) is known or assumed from either a theoretical knowledge or from studying a training set. This method’s most well-known use is linear discriminant analysis (LDA), which assumes that the class-conditional densities are multivariate normal distributions with distinct means but a similar covariance matrix. This is in contrast to a non-parametric or distribution-free approach in which no assumption is made about the type of distribution from which the samples are drawn. An example is to use kernel density or k-nearest neighbour. Classification decision trees provide another example of a successful non-parametric method.

Comparing discriminant analysis to cluster analysis, more data is available on the observations. Applying discriminating in a cluster analysis makes sense because the clusters (classes) produced by the analysis can ultimately be used for prediction. Despite the fact that discriminant analysis and cluster analysis provide a useful dichotomy of classification problems, numerous real-world issues include the characteristics of both circumstances. Note that the focus of this thesis is on supervised learning problems only.

In this work, bagging is applied to linear discriminant analysis (LDA). Aggregating several decision classifiers in a committee is generally more accurate than the use of a single classifier, possibly ignoring the opinion of some classifiers. Thus, it might be promising to use bagging technique to get a better classifier with a more stable solution. Here, we use the LDA classifier with the usual bagging, averaging combining rule and modified version. The modified bagging is based on averaging the probability of LDA classifiers by aggregating posterior distance. We consider these techniques from the perspective of a two-class linear discriminant function. Historically, [2] was the first to propose a procedure for a two-group problem based on maximising the separation between the groups, and it is widely applied in assigning future examples to these groups. Note that usually, LDA is stable when it is constructed on large training samples and unstable when small training samples are used, that is, n small relative to d. Here, we believe that LDA demonstrates that it is not always as stable as one would hope; consequently, applying modified bagging can be useful in some situations (see [3]).

Typical discrimination and classification play a key role in understanding, summarising and finding useful patterns in data, for example in medicine, archaeology, taxonomy and industry. The term discrimination or separation refers to the process of deriving classification rules from data of classified observations, whereas classification or allocation refers to the application of the rules to new observations of unknown class. In practice, discrimination and classification frequently overlap and the distinction between them becomes blurred.

1.1 Linear discriminant analysis: overview

Contrasting discriminant analysis to cluster analysis, more data is available on the observations. Applying discriminating in a cluster analysis makes sense because the clusters (classes) produced by the analysis can ultimately be used for prediction. Although the fact that discriminant analysis and cluster analysis provide a useful dichotomy of classification problems, numerous real-world issues include the characteristics of both circumstances. Note that the focus of this thesis is on supervised learning problems only.

Consider modeling each class density as a multivariate normal distribution with the following forms:

$$f_i\left(x\right)=\frac{1}{{\left(2\pi \right)}^{\raisebox{1ex}{$d$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{\left|{\mathrm{\Sigma }}_i\right|}^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}}\exp \left[-\frac{1}{2}{\left(x-{\mu }_i\right)}^{/}{\mathrm{\Sigma }}_{\mathrm{i}}^{-1}\left(x-{\mu }_i\right)\right],\text{for}i=\mathit{1},\mathit{2}$$E1

with mean vector μ_i, covariance matrix ∑_i and d as the dimension of the feature space. Further, if we suppose that we have the special case where each of the classes has a common covariance matrix ∑, this leads to a particularly simple linear discriminant analysis (or LDA).

A general approach for a classification rule is to consider the posterior probabilities. The Bayes discriminant rule with respect to the posterior is to allocate a new observation z to the population for which π_if_i(z) is maximised, where π_i are the prior probabilities. Then, the allocation rule that allocates z to ₲₁ is

$${\left({\mu }_1-{\mu }_2\right)}^{/}{\Sigma }^{-1}z\left({\mu }_1-{\mu }_2\right)-\frac{1}{2}{\left({\mu }_1-{\mu }_2\right)}^{/}{\Sigma }^{-1}\left({\mu }_1+{\mu }_2\right)\ge log\left(\frac{{\pi }_2}{{\pi }_1}\right)$$E2

In most practical situations, the population quantities μ_i, ∑_i and π_i are unknown and replaced by their sample counterparts. Hence, the samples of n_i observations from each ₲_i are used to define a sample-based rule by replacing:

μ_i with ${\overline{x}}_i,$ the estimated mean vector in ₲_i, ∑ with S_p, the pooled sample covariance matrix and πi with, $\widehat{\pi }=n_i/n$ the estimated prior probability. These estimates are given by

$$\overline{x}=\frac{1}{n}\sum _{i:y_i=j}{x}_i,,S_j=\frac{1}{n_j-1}\sum _{i:y_i=j}\left({\overline{x}}_i-{\overline{x}}_j\right){\left({\overline{x}}_i-{\overline{x}}_j\right)}^{/},\text{for}i=\mathit{1},\mathit{2}$$E3

$$S_p^2=\frac{\left(n_1-1\right)S_1+\left(n_2-1\right)S_2}{n_1+n_2-2}$$E4

With these estimates inserted to give parametric estimates of f1 and f2, the rule (2) now becomes a sample linear discriminant rule: allocate z to ₲₁ if

$${\left({\overline{x}}_1-{\overline{x}}_2\right)}^{/}{S_p}^{-1}z\left({\overline{x}}_1-{\overline{x}}_2\right)-\frac{1}{2}{\left({\overline{x}}_1-{\overline{x}}_2\right)}^{/}{S_p}^{-1}\left({\overline{x}}_1+{\overline{x}}_2\right)\ge log\left(\frac{{\pi }_2}{{\pi }_1}\right)$$E5

2. Bootstrap aggregating or bagging: overview

The quest for a ‘good’ learner is an important issue in discriminant analysis. Usually, a single classifier constructed on a training set is biased and has large variance. Consequently, such a classifier may be misleading and will typically generalise poorly. One can improve the classifier by combing multiple classifiers instead of a single classifier. The cooperation of several classifiers as a decision ‘committee’ has been proposed as a way of reducing misclassification error.

In Breiman’s paper [4], bagging, which has been shown to increase classifier accuracy, is used to enhance the performance of a learning algorithm. A general technique known as bagging involves combining several classifier outputs produced from a single classifier on a bootstrap resample version of the training set using a majority vote to improve the performance of a given learning algorithm.

Bagging produces random and independent training sets with replacement from the original data set. This procedure is repeated B times (say B = 50) and the resulting B classifiers [5]. A final classifier or prediction can be obtained by averaging the individual classifiers in regression or by taking the majority vote over individual classifiers in classification.

The following is how bootstrapping and aggregating approaches are used in bagging: enter a training set, which consists of n observations ℓ = {(x_i, y_i), i = 1 … n} with x_i being the feature vector and y_i being the response, taking values in y ϵ {1, 2…J}. Draw bootstrap samples each of size m with replacement from the original training set. Construct a classifier from each bootstrap sample, and the final classifiers built from whose output is the class predicted most often by its sub-classifiers (for more details see [6]). Figure 1 contains full details:

Figure 1.

Illustration of a majority vote proposed by the researcher depicts: BAGGING = Bootstrap + AGGregatING.

2.1 Mechanics of bagging algorithm on LDA

Bagging is usually investigated for decision trees. Breiman [4] has shown that bagging could reduce the classification error of decision trees, and he noticed that bagging is useful for unstable procedures only. For stable rules like LDA, [7] found that bagging is useless, because most cases [4] used large training sets, when LDA is very stable. In this work, we perform our study for linear discriminant analysis to investigate if applying bagging can be useful in some situations. Aggregating techniques are implemented on LDA in the following way:

Algorithm 1. Bagging algorithm on LDA

 1.  for b = 1 to B do

ℓ^*b = bootstrap sample of size m from ℓ (iid sample with replacement)

      estimate the parameters used by LDA in Eq. (4).

      construct the LDA classifier c _ℓ*b (x)

endfor

store the classifiers {c _ℓ*b (x), b = 1,2…, B}

 2.  Each observation in ℓ or in a test set is then classified using a majority vote of c_*1, c_*2,…, c_*B classifiers.

    A final decision rule: c_bag (x) = argmax $y_i\in \left\{0,1\right\}$$\sum _{b=1}^{B}I\left[{\mathrm{c}}_{{\mathrm{\ell }}_{\ast \mathrm{b}}}\left(\mathrm{x}\right)=\mathrm{y}\right],$

    Where I[.] is the indicator function, I[.] = 1 if c _ℓ*b (x) = y and 0 if c _ℓ*b (x) ≠ y

2.2 Illustration of bagging algorithm on LDA

Linear discriminant analysis is optimal for providing a classification rule that minimises the misclassification error rate if each class is a sample from a multivariate normal population and the population covariance matrices are all equal. Decision tree classification can achieve lower error rates when these assumptions are violated, for example in the case of bimodality.

To illustrate this, let us consider the situation where the LDA is applied to a two-class problem of one-dimensional data. Sixteen values from the first population N(−2,1.2) and sixteen values from the second population N(2,1.2). The separation of these two sets of ‘univariate xs’ is assessed by a linear discriminant rule in Eq. (4). In Figure 2, one can see that the LDA classifier built on the complete data is unable to accurately segregate the data. Making classifiers with bootstrapped samples based on 10 replicates sometimes gives a better classifier, sometimes a worse one. Aggregating bootstrap versions using a simple majority vote of classifiers could allow us to get a better classifier than the original classifier. An interesting observation from this example is that the bagged classifier is closer to Bayes’ rule (where densities intersect) than the LDA classifier.

Figure 2.

LDA classifier vertical (solid) line, bootstrap classifiers (dotted lines) and majority vote vertical (dashed) line. The two classes are shown by ᴼ and *. Note that there are 16 observations in each class.

In one dimension, the majority rule is in a special case equivalent to a ‘median’ procedure.

Let us consider the above classification example with a two-class problem. In this example, we have 32 training examples. Also, we have classifier c_b (x), b = 1, 2,…, B, as shown in Figure 1, so that if x < c_b (x), then class 1 otherwise class 2. For a given new observation z, classify z to class 1 if [# b = 1,2 …,10 c_b (x) > z] > [# b = 1,2 …,10 c_b (x) < z], as majority vote.

The majority vote is usually constituted by 50% + 1 of the class that has the power to make decisions binding upon the whole. Here, the majority criterion is equivalent to the median, since [# b = 1,2 …,10 c_b(x) > Ć_b] = 10/2, so that if z < Ć_b, then z is classified to class 1 otherwise to class 2, where Ć_b is the median of c_b (x), b = 1,2 …, 10. Notice that it is very difficult to define the median in more than one-dimensional data. However, while comparing the averaging classifier with the median classifier, it is necessary to evaluate moments like the variance to make sure that a suitable classification rule has a low variance to ensure a low error rate. Let us denote $\tilde{\mu }$ is the median of the population. Standard asymptotic theory reveals that $\left(\mathit{4}n\right[f\left(\tilde{\mu }]{}^{\mathit{2}}\right)‐1$ is an estimator of var.$\left(\tilde{\mu }\right),$ if we knew the density function. For example, in the case of the normal distribution, we have $\tilde{\mu }=\mu ,$ so that $\mathrm{f}\left(\tilde{\mu }\right)=\mathrm{f}\left(\mu \right)=1/\left(\sigma \sqrt{2}\pi \right).$ So, the variance of the mean here is smaller than that of the median.

3. Averaging combining rule on LDA

Based on the above observations on the variance of the mean and median, we introduce here the averaging combining rule when applying bagging to LDA classifiers, which is based on averaging their coefficients built on bootstrap replicates to create a final decision rule. As we have seen in the above example, the averaging has an advantage over the median procedure, which is in some sense equivalent to a majority vote that makes possible to use the averaging combining rule. Notice, however, that the averaging combining rule makes sense only when rules are ‘consistent’ at the boundaries. Thus, bagging in this case is organised as the follows:

Algorithm 2. Averaging combining algorithm on LDA

  1.  for b = 1 to B do

ℓ^*b = bootstrap sample of size m from ℓ (iid sample with replacement)

      estimate the parameters used by LDA in Eq. (4)

     construct the LDA classifier c _ℓ*b (x)

endfor

    store the classifiers {c _ℓ*b (x), b = 1,2 …, B}

  2.  combine the LDA classifier by averaging their coefficients into a final decision rule:

$${\mathrm{c}}_{\mathrm{bag}}\left(x\right)=\left(\frac{1}{B}\sum _{b=1}^B{c}_{l^{\ast b}}\right)\left(x\right)$$E6

3.1 Modified bagging algorithm on LDA

As mentioned previously, the averaging combining rule performs well only if the constructed rules on the bootstrap samples are consistent at the boundaries. In practice, this situation may not hold, because bootstrap samples have different features, which lead to inconsistent classifiers at the boundaries, especially if the bootstrap sample size is small. For this reason, we introduce an alternative procedure, which is based on posterior distance or Mahalanobis distance. The posterior distance treats with respective mean vectors and covariance matrix as the specification of a probability distribution for that class. For each new observation, we calculate the probability that the observation came from each class; the observation is then classified to the class which gave the highest probability. To illustrate, consider the one-dimensional example shown in Figure 3.

Figure 3.

Two probability densities from N(4,1.52) and N(9,1.52). Classifiers c _ℓ*b (z₁) and c _ℓ*b (z₂) (dashed) lines have higher probability, which are z₁ and z₂ to class 1 and class 2, respectively, according to posterior distance.

Suppose, first of all, we have two probability distributions with common covariance matrix: that observations drawn from class 1 have known distribution with mean 4, whereas those from class 2 have known distribution with mean 9. The classifier c _ℓ*b (z₁) has a higher probability in class 1 than in class 2, and consequently, it would be classified z₁ to the class 1. In contrast, the classifier c _ℓ*b (z₂) has a larger probability in class 2 than in class 1. Consequently, the observation z₂ would be classified to class 2. The posterior distance differs from the Euclidean distance in that it takes into account the variance of the probability distribution for each class.

4. Mechanics of modified (weighted) bagging algorithm on LDA

A commonly used distance measure is the Mahalanobis distance, which is defined as where S_p is the pooled sample covariance matrix, and x_i and x_j are respective vectors of measurements on observations i and j. Compared to the Euclidean distance or Manhattan distance, this distance measure has the advantage of explicitly accounting for any correlations that might exist between variables. This is similar to the posterior distance in the case of the data for each class being similarly distributed. Thus, a second modified version of bagging is implemented by us in the following way:

Algorithm 3. Modified bagging algorithm on LDA.

  for b = 1 to B do

ℓ^*b = bootstrap sample of size m from ℓ (iid sample with replacement)

      estimate the parameters used by LDA in Eq. (4)

     construct the LDA classifier c _ℓ*b (x)

     for each new observation z^*, let

$$D\left(z^{\ast }\right)=min\left[{min}_{\infty }\left(d(z^{\ast },x\backslash c_{l\ast b}\left(x\right)\ne c_{\mathrm{l}\ast \mathrm{b}}\left(z^{\ast }\right)\right),{min}_{\infty }\left(d(z^{\ast },x\backslash x\mathrm{on}\text{edge}\text{of}X\right)\right]$$E7

endfor

$$c_{\mathit{bag}}\left(z^{\ast }\right)=sign\left[\sum _{b=1}^{B}D\left(z^{\ast }\right)\times c_{l\ast b}\left(z^{\ast }\right)\right],$$E8

  Where sign (.) = ±1 dependent on sign of its argument.

The procedure for modified (or weighed) bagging is performed by the following steps (Algorithm 3). Given a training set ℓ = {(x_i, y_i), i = 1… n}, which consists of n observations ℓ_i = {(x_i, y_i)} with x_i the two-dimensional feature vector and $y_i\in \left[‐\mathit{1},\mathit{1}\right],$ draw bootstrap samples l^* = 1, …, L each of size m with replacement from the original training set L. Let Z be a 2D array covering the sample values x, and define the distance between z₁ and z₂ as

$$d\left(z_{\mathit{1}},z_{\mathit{2}}\right)=\mid z_{\mathit{11}}-z_{\mathit{21}}\mid +\mid z_{\mathit{12}}-z_{\mathit{22}}\mid .$$E9

4.1 Ripley’s simulated data

The data set is a two-class classification problem in two features. A training set of 250 observations is used, and the error rates are estimated by using a further sample of size 1000 observations. We use the same data as in [8], as illustrated in Figure 4. The class distributions are chosen to allow a best-possible error rate of about 8% and are in fact equal mixtures of two normal distributions. The LDA classifier is constructed on the full training set and tested on the test set with test error rate of about 10.8% and has been superimposed (solid line) on the graph.

Figure 4.

Two-class problem data from [8]. Two classes are displayed by 0 and 1: Note that there are 100 observations in each class. LDA classifier is constructed on the full data and has been superimposed with error rate of 10.8% (solid line), usual bagging (dashed-line) and weighted bagging (dotted line).

In this example, we perform weighted bagging, averaging rule and usual bagging for LDA. One of the reasons to choose the LDA classifier is ease of comparison. Another reason which nicely illustrates is that the training sample for the LDA is small, and therefore, the LDA becomes less stable. Here, we consider Ripley’s data set with different bootstrap sample sizes (m = 75 and 100). Bootstrap replicates of small training samples differ more from each other than the large training samples (by statistical properties). Therefore, it appears that bagging may be advantageous for an LDA classifier built on relatively small training samples, especially when the classifier is most influenced by perturbations in the composition of the training sample. However, a very small training sample may be very misleading. As shown in Figure 5 at the LHS that compares weighted bagging, averaging rule and usual bagging, constructed on a training sample of size (m = 75) and performed on the test set. One can clearly see the superiority of weight bagging over the other two procedures as the iterations increase. However, the optimal error rates can be found after 7 iterations by usual bagging, which gave better improvement than the later iterations. The test error rate was about 10.3% for modified bagging and 10.6% for both averaging rule and usual bagging. When the training sample size increased to m = 100, as shown at RHS of the same figure, all procedures are less accurate compared to the LHS plot produced by training sample size 75. With the further increase of the training sample size, up to m = 200, the modified bagging and usual bagging become more stable, nearly identical to the averaging rule. This result is consistent with the simulation study performed by Breiman [7] on LDA.

Figure 5.

Weighted bagging (solid line) and usual bagging (dashed line) of the different training sizes from Ripley’s data set. The left panel is based on m = 75, while the right panel is based on m = 100. Note that test error rates for both procedures are estimated over 50 repetitions.

As a result, the classifier developed using a high training sample size may be comparable to the classifier developed using the entire training set. Therefore, some features of the classifiers built on a whole training set may be present in the bagged classifiers. The LDA classifier is where this phenomena is most pronounced. In general, the training sample size and the data distribution are strongly affected by the performance of the modified bagging and usual bagging, as well as the averaging combining rule.

5. Conclusion

Combining several decision classifiers in a committee can provide an improvement over the use of a single classifier. Bagging is a general technique which combines benefits of bootstrapping and aggregating. However, bagging is mainly investigated for decision trees and much less in linear discriminant analysis (LDA). Breiman [4] claims that bagging works well for unstable procedures, which often have high variance. This variance is a major component of classification error, which can be reduced by aggregating, often producing good results.

The idea of bagging is extended to averaging the classifiers based on the Manhattan distance in the decision tree (see [9]) or the Mahalanobis distance in the linear discriminant analysis (LDA) instead of a majority vote. In the first direction, we focused on creating decision trees, and experimental findings and analysis demonstrate that for all sample sizes, weighted bagged classifier outperforms conventional bagging on various tree levels. It is interesting to note that weighted bagging with stump trees outperforms standard bagging somewhat. In the second direction, we concentrated on building linear discriminant analysis (LDA). We have shown by using Ripley’s simulated data that weighted bagging can provide a good classifier, which is better than the averaging rule and usual bagged classifier constructed on small training sample size. Increasing the training sample sizes, classifier becomes stable; both modified bagging and usual bagging are identical to the averaging rule. These techniques depend on the training sample size, as well as the distribution of data used to construct the classifier. Therefore, it is crucial to consider them while using this strategy to enhance classifier performance.

5.1 Potential research directions

We have concluded that LDA could sometimes be preferable to usual bagging. In general, simple majority vote strategy is not a good choice for the aggregating rule, whereas the weighted vote technique is often a good choice for a bagged classifier in decision trees [9].

Furthermore, the weighted bagging may also perform well in LDA classifier. However, the choice of aggregating technique may be important, which strongly depends on the training sample size and the distribution of data.

We only use weighted bagging in this study for the situation of a two-dimensional predictor space, but what about the more important scenario in terms of practical application of many variables? We leave this as an unsolved research issue.

Acknowledgments

I like to thank Professor Charles Taylor from Leeds University for his scientific input on this effort.