Chapter 3

• The systematic assignment of new observations to known categories according to criteria learned from a training set

• A classifier K for a model M(θ) is a function K_M(θ): D -> Y, where

  • D: data space

    • often d-dim space with attributes a1,…,ad

    • some other metric space

  • Y = {y1,…,yk} : set of k distinct class labels

  • O ⊆ D: set of training objects o with known class labels y∈Y

Classification

• Application of classifier K on objects from D

M(θ)

• The ‘type’ of classifier, and θ are the model parameters

Supervised Learning

• Finding/learning optimal parameters θ for M(θ) given O (set of training objects)

• Determining the numerical value of an object

• Method example: regression analysis

• Example: Prediction of flight delays i.e. given the wind speed, what is the predicted delay of flight

Different

• Classification refers to predict categorical class labels

• Numerical prediction models continuous-valued function

Similar

• Model constructed

• Model used to predict unknown value

• Regression is a major method of both

• Accuracy/error (complementary)

• Compactness of model (tree size, #rules)

• Interpretability of the model

• Efficiency

• Scalability for large databases

• Robustness

• Let C(o) denote the correct class label of an object o

• Predict the class label for each object o from a data set T⊆O

• Determine the fraction of correctly predicted class labels

Note: for a data set with classes of different sizes, accuracy is misleading

• It is true that the object is in the predicted class A

It is false that the object is in predicted class A

It is true that the object is in the predicted class !A

It is false that the object is in the predicted class !A

• [0.1]

• The larger the better

• = TP / (TP + FN)

  
  

• [0,1]

• The larger the better

• = TP / (TP + FP)

• [0,1]

• The larger the better

• = 2 rec prec / (rec + prec)

• = 2TP / (2TP + FN + FP)

• The fraction of test objects of class i, which have been correctly identified.

• Fraction of test objects assigned to class i, which have been identified correctly

• Decomposition of labeled data set O into 2 partitions

  • training data is used to train the classifier

  • test data is use to evaluate the classifier

• If the set of objects for which the class label is known is very small

• Decompose data set evenly into m subsets of (nearly) equal size

• Iteratively use (m-1) partitions for training data and the remaining single partition as test data

• Combine the m classification accuracy values to an overall classification accuracy

• For each of the objects o in the data set O:

  • use set O / {o} as training set

  • use the singleton set {o} as the test set

• Compute classification accuracy by dividing the number of correct predictions through the database size |O|

• Especially good for nearest-neighbour classifiers

• The error that a classifier would make if it were used to predict the class of the training data it was trained on

• This error can be calculated by training the classifier on a subset of the training data and then evaluating its performance on the rest of the training data

• error that a classifier makes when it is used to predict the class of new data that it has never seen before.

• This error is typically estimated using a separate test set that the classifier has not been trained on.

• The classifier adapts too closely to the training dataset and may therefore fail to accurately predict class labels for test objects unseen during training

• Bad quality of training data (noise, missing values, wrong values)

• Different statistical characteristics of training data and test data

• Removal of noisy/erroneous/contradicting training data

• Choice of an appropriate size of the training set

  • not too small, not too large

• Choice of appropriate sample

  • sample should describe all aspects of the domain and not only parts of it

• Occurs when the classifier’s model is too simple, e.g. trying to separate classes linearly that can only be separated by a quadratic surface

• Probability based classification: given a query object q, assign to q the class with the highest probability:

• The conditional probabilities P(cj | q) are hard to estimate, so turn the rule by applying Bayes’ theorem to a formular based on P(q | cj).

• Estimate the required probability density functions by using distribution models learned from the training data

  
  

P(A|B) = P(A ^ B) / P(B)

Apriori Probabilities P(c_j):

• Use the observed relative frequency of the individual class labels c_j in the training set, i.e.,

• P(cj) = N_c_j / N

Conditional Probabilities P(x | c_j):

• Non-parametric methods: Kernel methods - Parzen’s window, Gaussian kernels, etc.

• Parametric methods:

  • Single Gaussian Distribution: Computed using maximum likelihood estimators

  • Mixture models: e.g. Gaussian Mixture Model computed by EM algorithm

Problems

• Correlations of attributes are hardly available if training sets are small

• Curse of dimensionality may cause problems in high-dimensional data

Solutions

• Dimensionality reduction

• Assume statistical independence of single attributes -> naive Bayes

• For any given class cj the attribute values xi are distributed independently, i.e.

• The Maximum A Posteriori (MAP) decision rule. This rule states that for a given data point x, the classifier should assign it to the class c that maximizes the posterior probability P(c | x).

  • In other words, the classifier should predict the class that is most likely given the observed data.

• P(xi | cj) can be estimated as the relative frequency of samples having value vi as the ith attribute in class cj in the training set

• Easy to compute

• P(xi, cj) can be estimated through a Gaussian distribution determined by μij,σij

• Computationally easy

Pros

• High classification accuracy for many applications if density function defined properly

• Incremental computation: many models can be updated to new training objects by updating densities

• Incorporation of expert knowledge about the application in the prior P(C_i)

Cons

• Limited applicability: often required conditional probabilities are not available

• Lack of efficient computation: in case of a high number of attributes

• It is seldom satisfied in practice, as attributes are often correlated

Overcome

• Bayesian networks: combine Bayesian reasoning with causal relationships between attributes

• Decision trees: that reason one 1 attribute at the time, considering most important attributes first

• Separate points of two classes by a hyperplane

  • i.e. classification model is a hyperplane

  • points of one class in one half space, points of second class in the other half space

• The inner product of two vectors x,y ∈ V

  • e.g. the scalar product ⟨x,y⟩= x^Ty = sigma^d{i=1}x_iy_i

    
    

• A hyperplane with normal vector w and constant term w_0

  • x ∈ H <-> ⟨x , w ⟩ + w_0 = 0

• The normal vector w may be normalized to w’

• A hyperplane with normal vector w and constant term can be used to classify data points into two classes

• if w^T x + w_0 > 0 then x is in class 1 else x is in class 2

1. Define an objective/loss function L(.) that assigns a value (i.e error of the training set) to each parameter configuration

2. Optimal parameters minimize/maximize the objective function

• Different choices possible

• Most intuitive: each misclassified object contributes a constant (loss) value

  • i.e. 0-1 loss

• One-vs-the-rest (one vs all) = k classifiers

• One-vs-one (majority vote of classifiers) = k(k-1) / 2 classifiers

• Multiclass linear classifiers = k classifiers

• Advantage: no ambiguous regions except for points on decision hyperplanes

• Simple approach

• Closed form solution for parameters

• Easily extendable to non-linear spaces

• Sensitive to outliers - depending on loss function - not a stable classifier

• Only good results for linearly separatable data

• Expensive computation of selected hyperplanes

• Linear separation with the Maximum Margin Hyperplane (MMH)

• Distance to points from any of the two sets is maximal i.e. at least ξ

• Minimal probability that the separating hyperplane has to be moved due to an insertion

• Maximum Margin Hyperplane only depends on points p_i whose distance to the hyperplane is exactly ξ.

• These pi are called support vectors

• Let xi ∈ R^d denote the data points, and yi = +1 if first class, else y_i = -1

• A hyperplane in Hesse normal form is represented by a normal vector w ∈ R^d of unit length (i.e. ||w||_2 = 1), and a (signed) distance from the origin b ∈ R

• generate classifiers with a high classification accuracy

• relatively weak tendency to overfitting (generalization theory)

• efficient classification of new objects due to often small number of support vectors

• compact models

• training times may be long (feature space may be very high-dimensional)

• expensive implementation

• Map to linearly discriminant functions (phi) by using non-linear transformation into an (extended) space

• Separate the data in the new space by linear methods

i.e.

• Explicit feature transformation yields a richer hypotheses space

• Simple extension of existing techniques

• Efficient evaluation, if transformed feature space not too high-dimensional

• Explicit mapping may run into problems (efficiency, high dimensions)

• Meaningful transformation is usually not known a-priori

• Complex data distributions may require very high-dimensional features spaces -> high memory consumption, high computational costs

• We often need the scalar product of mapped objects only, K_{phi}(x,y) = <phi(x), phi(y)>

• If K_{phi}(x,y) is represented in the original domain, the mapping phi remains implicit only, and the problems of mapping explicitly are avoided

• Kernel allows for mappings with infinite dimensions

• Kernels correspond to scalar products in the corresponding feature space

• Scalar products and, thus, kernels are used in various definitions:

A kernel function K: chi x chi -> R on an input space chi is a symmetric function which maps pairs of objects x,y ∈ chi to real numbers.

A kernel function K is called Mercer kernel, valid kernel, admissible kernel, or positive semi-definitive kernel, if for all finite subsets X = {x1, … , xn} ⊆ chi, the n x n matrix M_K(X) with M_K(X)_{i,j} is positive semi-definite, i.e. for all c ∈ R^n, it holds

• c^T · M_K(X) · c >= 0

A vector spacew H endowed with a scalar product <·,·>: H x H -> R for which the induced norm gives a complete metric space, is called a Hilbert space.

• every kernel K can be seen as a scalar product in some feature space H

• Feature space H can be infinite-dimensional

• Not really necessary to know which feature space H we have

• Computation of kernel is done in original domain chi

• Linear

• Polynomial

• Radial basis function (RBF) / Gaussian Kernel

• The kernel trick may be applied to non-numerical, structured objects as well.

• Kernels K(x,y) are defined in terms of object properties

• K(x,y) = <phi(x), phi(y)> remains a scalar product in R^d but phi : chi -> R^d is not needed explicitly

• Examples:

  • Graph Kernels

  • Fisher Kernels: digest complex objects by pooling features

• Kernel methods provide a great method for dealing with non-linearity

• Implicit mapping allows for spaces of arbitrary dimensions (even infinite)

• Computational effort of training Kernel machines depends on the number of training examples, but not on the feature space dimension

• Resulting methods may be hard to intuitively explain

• Choice of kernel may be difficult

• Approximating discrete-valued target function

• Learned function represented as a tree:

  • flow-chart-like tree structure

  • Internal node denotes a test on an attribute

  • Branch represents outcome of the test

  • Leaf nodes represent class labels or class distribution

• Tree can be transformed into decision rules

• Relatively fast learning speed

• Fast classification speed

• Convertible to simple and easy to understand classification rules

• Often comparable classification accuracy with other classification models

• Decision trees represent explicit knowledge

• Decision trees are intuitive to most users

• Not very stable, small changes of the data can lead to large changes of the tree

• Each tree node defines an axis-parallel (d-1) dimensional hyperplane, that splits the data space

• Find such splits which lead to as homogenous groups as possible

1. Tree construction

   • At start, all the training examples are at the root

   • Partition examples recursively based on selected attributes

2. Tree pruning

   • Identify and remove branches that reflect noise or outliers

• Traverse the tree and test the attribute values of the sample against the decision tree

• Assign the class label of the respective leaf to the query object

ID3 (Iterative Dichotomiser 3)

• Tree is created in a top-down recursive divide-and-conquer manner

• Attributes may be categorical or continuous-valued

• At the start, all the training examples assigned to root node

• Recursively partition examples at each node and push them down to the new nodes

• Select test attributes and determine split points or split sets for the respective values based on a heuristic or statistical measure (split stategy e.g. information gain)

• Conditions for stopping partitioning

  • All samples for a given node belong to the same class

  • There are no remaining attributes for further partitioning

  • No samples left

• Minimum amount of bits to encode a message that contains the class label of a random training object

• The entropy of a set T of training objects is defined as

for k classes with frequencies p_i.

• entropy(T) = 0 is pi = 1 for any class ci

• entropy(T) = 1 if pi = 1/k for all classes ci

• Split criteria based on equality “attribute = a”

• Based on subset relationships “attributes ∈ set“

  • many possible choices (subset)

    • choose best split according to e.g. gini index

• Split criteria of the form “attribute < a“

  • many possible choices for split point

  • approach idea: order test samples w.r.t their attribute value, consider every mean value between two adjacent samples as possible split point

  • partition the attribute value into discrete set of intervals (binning)

• Too many branches, some may reflect anomalies due to noise or outliers

• Results has poor accuracy for unseen data

• Post-pruning = pruning of overspecialized branches

• Pre-pruning = halt tree construction early

• Remove branches from a ‘fully grown’ tree and get a sequence of progressively pruned trees

• Use a set of data different from the training data to decide which is the ‘best pruned tree’

Halt tree construction early, do not split a threshold if this would result in the goodness measure falling below a threshold.

• Choice of an appropriate value for minimum support

  • = minimum number of data objects a leaf node contains, in general >> 1

• Choice of an appropriate value for minimum confidence

  • = minimum fraction of the majority class in a leaf node, in general << 100%

  • Leaf nodes can absorb errors or noise in data records

• Difficult to choose appropriate thresholds

• Pre-pruning has less information for the pruning decisions than post-pruning -> can be expected to produce trees with lower classification quality

• Tradeoff: tree construction time vs classification quality

• To prevent overfitting of a model

  • to make the model generalize better

• Recursively evaluates and pruens the weakest links in the decision tree by looking at the sub trees.

  • This is done until the cost complexity of the tree is minimized

• Reduces overfitting

• Improves generalization

• Enchances interpretability

• Assume data is in a non-vector representation: graphs, forms, XML-files, etc.

• No simple way to use linear classifiers or decision trees

• Use appropriate kernel function for kernel machines (e.g. kernel SVM)

• Embedding of objects into some vector space (representation learning)

• Direct usage of (dis-)similiarity functions for objects

• Assign query object q to the class c_j of the closes training object x ∈ D

class(q) = class(NN(q))

NN(q) = {x ∈ D | ∀x′ ∈ D: d(q,x) <= d(q, x’)}

• Where the prediction for a new instance is computed immediately when presented to the model

• Decision tree

• Bayes classifier

• SVM

• Training phase: learn parameters for chosen model from training data

• Test phase:evaluate parametrized model for arriving query objects

• k-nearest neighbor classifiers

• Derive labels from individual training objects: instance based learning

• No training required

• Put data into efficient index structures (e.g. R-Tree)

  
  

• Distance function: Defines the (dis-)similarity for pairs of objects

• Decision set: The set of k nearest neighbouring objects used in the decision rule

Given the class labels of the objects from the decision set, how can one derive the class labels for the query object

• Nearest neighbour rule (k=1)

• Majority vote (k>=1)

• Distance-weighted majority vote

• Class-weighted majority vote

• Too small: high sensitivity against outliers

• Too large: decision set contains many objects from other classes

• Based on theoretical considerations: choose k, such that it grows slowly with n, e.g. k = sqrt(n), or k = log n

• 1 << k < 10 yields a high classification accuracy in many cases

• k-NN classifier: consider the k nearest neighbours for the class assignment decision

• Weighted k-NN classifier: use weights for the classes of the k nearest neighbours

• Mean-based NN classifier: determine mean vector mi for each class cj (in training phase); assign query object to the class cj of the nearest mean vector mi

• Generalization: Representative-based NN mean classifier; use more than one representative per class - no longer just instance-based

• Applicability: training data and distance function required only

• High classification accuracy in many applications

• Easy incremental adaptation to new training objects useful also for prediction

• Robust to noisy data by averaging k-nearest neighbours

• Naive implementation is inefficient: requires k-nearest neighbour query processing but with database support techniques to goes from O(n) to O(log n)

• Does not produce explicit knowledge about classes, but provides explanations

• Curst of dimensionality: distance between neighbours could be dominated by irrelevant attributes, apply dimensionality reduction first.

• No single classifier performs good on every problem

• For some techniques, small changes in the training set lead to very different classifiers

• Improve performance by combining different classifiers = ensemble classification

• Different possibilities exist

  • bagging (bootstrap aggregation)

  • boosting

• Randomly select m different subsets from the training set

• On each subset, independently train a classifier K_i (i = 1,…,m)

• Overall decision:

• Linear combination of several weak lerners (different classifiers)

• Given m weak learners Ki and weights alphai for i=1,…,m

• Overall decision:

• Important difference: classifiers trained in sequence

• Repeatedly misclassifies points are weighted stronger

• Extensively studied problem

• Widely used data mining techniques with a lot of extensions

• Scalability important issue

• Many research directions

• Results can be improved by ensemble classification