Classification: Basic Concepts

Classification: Basic Concepts

Overview

Classification is a supervised-learning problem: labeled training examples are used to learn a model that assigns categorical labels to unseen objects. The chapter develops this idea through several complementary model families. Decision trees partition the feature space with interpretable rules; Bayesian classifiers reason from posterior probabilities; lazy learners such as -nearest neighbors postpone most computation until prediction time; and logistic regression turns a linear score into a class probability. The second half of the chapter asks how such models should be evaluated and improved, leading from confusion-matrix metrics and resampling protocols to ensembles and class-imbalance techniques.

The central progression is therefore

The methods differ in their inductive assumptions. Trees build recursive partitions, Naive Bayes assumes conditional feature independence, -NN relies on local similarity, and logistic regression assumes that the log-odds are linear in the features. No single classifier is uniformly best for every data set; model choice must be tied to the structure of the data and to the evaluation criterion.

Classification Setup and Learning Workflow

Exam: ★★★★☆

Supervised classification versus unsupervised learning

In supervised learning, every training object is accompanied by a class label . A classifier is learned from these labeled examples and is then applied to new objects. In contrast, unsupervised learning such as clustering receives observations without known class labels and attempts to discover latent groups or structure in the data.

Classification predicts a categorical target, whereas numeric prediction models a continuous-valued target. Thus predicting whether a customer belongs to a class such as positive or negative is classification; predicting a house price is numeric prediction. Both are predictive tasks, but the target space and the appropriate losses differ.

Training, validation, testing, and deployment

A classification model may be represented as a decision tree, a set of rules, a mathematical function, or another predictive structure. The basic assumption is that each labeled training sample belongs to one predefined class. Model construction uses a training set. Generalization is assessed on data not used to fit the model.

A clean workflow distinguishes three roles:

• training set: fit model parameters or structure;
• validation/development set: select hyperparameters, compare variants, or refine the model;
• test set: estimate the final generalization performance after model selection is complete.

If the resulting performance is acceptable, the selected model is deployed to classify previously unseen data.

Decision Tree Induction

Exam: ★★★★★

Recursive partitioning

A decision tree is constructed top-down by recursively partitioning the training examples. Initially all examples are at the root. At a non-leaf node, the algorithm chooses an attribute or split using a heuristic or statistical criterion such as information gain or the Gini index, partitions the data according to that split, and recurses on the resulting subsets.

Typical stopping conditions are reached when all examples at a node have the same class, no useful attributes remain for further partitioning, or a branch receives no training examples. A leaf predicts a class, commonly the majority class among the training examples that reach that leaf.

The Play Golf example illustrates the structure. The root tests Outlook. Overcast immediately predicts Yes; the Sunny branch is further separated by Windy, and the Rainy branch by Humidity. The point of the example is not the slide order but the mechanism: each internal test reduces class uncertainty until a leaf can make a sufficiently definite prediction.

Continuous-valued attributes

A continuous attribute can first be discretized into categorical intervals, such as age ranges. More commonly, a tree searches directly for a threshold. Sort the observed values and consider candidate thresholds between adjacent values,

For a selected threshold , the node is split into and . The threshold giving the best split criterion, for example the largest information gain, is chosen.

Entropy and information gain

For a discrete class variable taking values with , entropy is

Entropy measures class uncertainty: it is low when one class dominates and high when the distribution is more even. Conditional entropy after observing is

For a training set containing classes, let . The class entropy before splitting is

If attribute partitions into subsets , the expected remaining entropy is

and the information gain is

A larger gain means that the split produces purer child nodes and therefore removes more uncertainty about the class.

Gain ratio

Information gain is biased toward attributes with many distinct values, because a near-unique attribute such as an ID can create many small, pure partitions without providing useful generalization. Gain ratio normalizes the gain by the intrinsic information of the split:

The slides illustrate this with Temp, whose partition sizes are :

ID3 is associated with information gain, while C4.5 refines the selection process using gain ratio.

Strengths and limitations

Decision trees are attractive because their decisions can be inspected as rules, they handle heterogeneous feature types, they do not require feature normalization for axis-aligned splits, and they make no parametric distributional assumption such as Gaussianity or feature independence. Many tree implementations can also handle missing values through explicit strategies.

Their weaknesses motivate later ensemble methods. Small changes in the data may change early splits and therefore the whole tree; greedy induction can miss globally better trees; deep trees can overfit; and a single axis-aligned tree may need many leaves to approximate a complicated boundary.

Bayesian Classification

Exam: ★★★★★

Bayes theorem and maximum a posteriori classification

For mutually exclusive and exhaustive events , the law of total probability gives

Bayes’ theorem reverses a conditional probability:

Here is the prior probability of a hypothesis or class, is the likelihood of the observed evidence, and is the posterior. For classification, the denominator is the same for every candidate class, so maximum a posteriori prediction can compare directly.

Naive Bayes and the conditional-independence assumption

For , the chain rule gives

Naive Bayes replaces these potentially complicated dependencies with the assumption that features are conditionally independent given the class:

This turns learning largely into estimating class priors and one-dimensional class-conditional distributions. The model is therefore extremely efficient and can be updated incrementally as new counts or sufficient statistics arrive. Its main limitation is exactly the simplifying assumption: dependencies among features such as patient profile, symptoms, and diseases are not represented. Bayesian networks, introduced in the advanced chapter, relax this restriction.

Categorical and continuous features

For a categorical feature, is estimated from class-conditional counts. For a continuous feature, the slides use a Gaussian class-conditional model. With class-specific mean and standard deviation ,

Under the Naive Bayes assumption, the full likelihood is the product of these feature-wise terms.

Zero probabilities and Laplace smoothing

Because Naive Bayes multiplies feature likelihoods, one zero estimate makes the entire class score zero. Laplace smoothing prevents this. For a categorical feature with possible values and class-conditional counts ,

Thus counts over three categories become probabilities proportional to with denominator , remaining close to the empirical frequencies while avoiding exact zeros.

Lazy Learning and Nearest Neighbors

Exam: ★★★★☆

Lazy versus eager learning

An eager learner constructs a global model before seeing the test object. Decision trees, Naive Bayes, and logistic regression are examples. A lazy learner stores the training examples with little preprocessing and delays most model construction until a query arrives. This shifts cost from training to prediction.

The conceptual advantage is locality: instead of committing to one global hypothesis, a lazy method can form different local approximations around different queries. Typical instance-based methods include -nearest neighbors, locally weighted regression, and case-based reasoning.

The k-nearest neighbor rule

Represent each object as a point in a feature space. Under Euclidean distance,

For classification, find the training examples closest to the query and return the most common class among them. For real-valued prediction, return the mean target value of the neighbors. With , the feature space is partitioned into Voronoi cells, each associated with its nearest training point.

A distance-weighted variant gives closer neighbors more influence, for example

For regression the weighted prediction is a weighted average; for classification the same idea can be used in a weighted vote.

Choosing k and the curse of dimensionality

The value of controls the bias-variance trade-off. Very small produces flexible, jagged boundaries: low bias but high variance and susceptibility to noise. Large averages over a wider neighborhood: lower variance but higher bias, and potentially includes points from irrelevant regions.

High dimensionality creates an additional problem: distances can become dominated by irrelevant attributes, and nearest and farthest points become less distinguishable. The slides suggest stretching/reweighting informative axes or eliminating irrelevant attributes. Feature scaling is also crucial whenever different coordinates are measured on incomparable numerical scales.

Case-based reasoning

Case-based reasoning extends the lazy-learning idea beyond Euclidean feature vectors. It stores rich symbolic descriptions of previous problems and solutions, retrieves similar cases, and may combine or adapt them using domain knowledge. Applications mentioned in the slides include product diagnosis in customer service and legal reasoning. Its central challenge is defining a useful similarity measure and an indexing/retrieval strategy for complex symbolic cases.

Linear Models: From Regression to Logistic Classification

Exam: ★★★★★

Linear regression as the starting point

The slides motivate linear regression with mappings such as living area house price and college/major/GPA future income. For observations with , linear regression models

Least squares chooses parameters that minimize

The slides then give a closed-form slope for the one-dimensional case. If is scalar and an intercept is included, the correct formulas are

Logistic regression

Linear regression predicts an unrestricted real number, whereas binary classification needs a probability. Logistic regression applies the sigmoid function to a linear score:

The sigmoid maps to the open interval . Its inverse is the logit,

Thus logistic regression is linear in log-odds, not in the binary label itself. A threshold such as converts the probability to a class decision; with that threshold, the decision boundary is . In the slide example using years of employment to predict tenure, the fitted sigmoid changes rapidly near the learned boundary around six years, illustrating how a continuous score becomes a class probability.

Maximum likelihood and log-likelihood

For a binary label ,

Assuming independent training examples, the likelihood is

It is usually optimized through the log-likelihood

If the intercept is absorbed into an augmented feature vector, this can be rewritten as

There is no ordinary closed-form maximizer, so iterative optimization is used.

Gradient descent versus ascent

Gradient descent minimizes an objective by moving opposite the gradient:

where is the step size. To maximize the logistic log-likelihood, however, use gradient ascent. For component ,

so an ascent update is

The term has a simple interpretation. If , an underconfident prediction moves in the direction of ; if , the update moves away from in proportion to the predicted positive probability.

Model Evaluation and Selection

Exam: ★★★★★

Confusion matrix

For binary classification, choose one class as positive. The confusion matrix contains

• TP: actual positive, predicted positive;
• FN: actual positive, predicted negative;
• FP: actual negative, predicted positive;
• TN: actual negative, predicted negative.

For classes, entry counts objects whose true class is but whose predicted class is .

Accuracy, sensitivity, specificity, precision, and recall

Let , , and . Then

Sensitivity, also called recall or true-positive rate, is

Specificity, the true-negative rate, is

Precision asks how many predicted positives are truly positive:

Precision and recall often trade off as the decision threshold changes. The score combines them:

For ,

Underfitting and overfitting

As model complexity increases, training error usually decreases. Test error often first decreases and then rises: the left side corresponds to underfitting, where the model is too simple to capture the signal; the right side corresponds to overfitting, where the model follows idiosyncrasies of the training sample. Model selection should therefore use validation performance rather than training error alone.

Holdout and cross-validation

In the holdout method, the data are randomly partitioned into independent training and test portions, for example and . Repeated random sub-sampling repeats this random split several times and averages the resulting performance estimates.

In -fold cross-validation, the data are partitioned into mutually exclusive folds of approximately equal size. For fold , train on all folds except and evaluate on ; average over all folds. Leave-one-out cross-validation is the limiting case and is mainly practical for small data sets. Stratified cross-validation approximately preserves the class proportions in every fold, which is especially important under imbalance.

ROC curves and AUC

A receiver operating characteristic curve sweeps a decision threshold and plots

against

A random ranking lies near the diagonal, with area under the curve around ; a perfect ranker has AUC . ROC curves therefore compare the trade-off between true-positive and false-positive rates across thresholds.

Ensembles and Class-Imbalanced Classification

Exam: ★★★★★

Why ensembles can help

An ensemble combines learned models into a stronger predictor . Majority-vote examples in the slides show the key condition: merely adding models is not enough. Base models should be individually useful and, crucially, should make different errors. If all models make the same mistake, voting cannot repair it; if weak models fail on unrelated examples, aggregation can cancel some of those errors.

Bagging

Bagging, or bootstrap aggregation, creates diversity by resampling the training set. For :

• draw a bootstrap sample from by sampling with replacement;
• train a base model on .

For classification, predict by majority vote; for numeric prediction, average the base predictions. Because the models are trained independently on different bootstrap samples, they can be learned in parallel. Bagging is especially useful for unstable learners such as decision trees.

Boosting and AdaBoost

Boosting learns base models sequentially. Each new model places more emphasis on examples that earlier models handled poorly, and the final decision is a weighted combination of the base models.

For binary AdaBoost with labels , initialize normalized example weights . At round , train and compute

For a weak learner better than chance,

The standard weight update is