> For the complete documentation index, see [llms.txt](https://sejkai.gitbook.io/academic/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sejkai.gitbook.io/academic/ncku-data-mining/classification.md).

# Classification

## Classification

* Given a collection of training sets **`[attributes : class]`**
* Find a **model** for class attribute as a function of the values of other attributes. 
* Goal: **previously unseen** records should be assigned a class as accurately as possible. 

### Data Preparation

* Data cleaning
* Relevance analysis
* Data transformation

### Classification Evaluation

* accuracy
* speed & scalability
* robustness
  * handling noise and missing values
* interpretability
* goodness of rules
  * decision tree size 
  * compactness of classification rules 

### Techniques for classification

* Decision Tree
* Memory based reasoning (K-NN)
* Regression
* Neural Networks
* Naïve Bayes
* Support Vector Machines
* Random Forest

### Issues of Classification

* Missing Values
* Costs of Classification
* Underfitting and Overfitting
  * Address Overfitting
    * Pre-Pruning (Early Stopping Rule)
      * Stop the algorithm before it becomes a fully-grown tree
    * Post-pruning
      * Grow decision tree to its entirety
      * Trim the nodes of the decision tree in a bottom-up fashion
      * If generalization error improves after trimming, replace sub-tree by a leaf node
      * Class label of leaf node is determined from majority class of instances in the sub-tree

## Decision tree

* Algorithms
  * Hunt's Algorithm
  * CART
  * ID3, C4.5, C5.0, See5
  * SLIQ,SPRINT
* Tree Induction
  * Greedy strategy
    * Split the records based on an attribute test that 

      optimizes certain criterion
  * Issues
    * How to split the records
    * When to stop splitting
* Test Condition
  * Depend on attribute types
    * Nominal: `{hot, cool, cold}`
    * Ordinal: `{A, B, C}, {small, medium, large}`
    * Continuous: `{1.25, 2, -3}`
      * Binary split
        * `x > 80 -> Yes, No`
      * Multi-way split
        * `[10, 25], [25, 50], [50, 80]`
  * Depends on number of ways to split
    * binary split
      * Divides values into two subsets.
      * Need to find optimal partitioning.
        * `CarType -> {Sports, Luxury}, {Family}`
    * Multi-way split
      * Use as many partitions as distinct values.
        * `CarType -> Family, Sports, Luxury`
* How to Determine the Best Split
  * Need a measure of node impurity
  * Non-homogeneous, High degree of impurity 
    * `a:5, b:5`
  * Homogeneous, Low degree of impurity 
    * `a:9, b:1`
* Measures of Node Impurity
  * Gini Index
  * Entropy
  * Misclassification error
* Advantages
  * Inexpensive to construct
  * Extremely fast at classifying unknown records
  * Easy to interpret for small-sized trees
  * Accuracy is comparable to other classification techniques for many simple data sets
  * Good at dealing with symbolic feature
  * Easy to comprehend

### GINI

$$
GINI(t) = 1 - \sum\_j \[p(j\mid t)]^2
$$

* Maximum : when records are equally distributed among all classes, implying least interesting information
* Minimum : when all records belong to one class, implying most interesting information
* GINI 越小代表分的越好
  * 最差 0.5，最好 0

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoDvd7ywTpIk1l-%2Fgini_computation.jpg?generation=1573290681189035\&alt=media)

#### GINI with Multiple Attributes

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoGUO3cIbg_QybL%2Fgini_multiple_attrs.jpg?generation=1573290680941255\&alt=media)

* 以左邊為例

$$
\begin{aligned}
1-(\frac{3}{5})^2 - (\frac{2}{5})^2 &= 0.48\\
1-(\frac{1}{5})^2 - (\frac{4}{5})^2 &= 0.32\\
0.48 \times \frac{5}{10} + 0.32 \times \frac{5}{10} &= 0.4
\end{aligned}
$$

#### GINI with Continuous Attributes

* Need to Computing Gini Index 
  * Several Choices for the splitting value
* For efficient computation:
  * Sort the attribute on values
  * Linearly scan these values
    * Updating the count matrix and computing gini index
  * Choose the split position that has the least gini index

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoKvMIxCmtIYjgK%2Fgini_continuous_attrs.jpg?generation=1573290681338794\&alt=media)

### Entropy

$$
Entropy(t) = -\sum\_j p(j\mid t)\log\_2p(j\mid t)
$$

* NOTE: $$p(j\mid t)$$ is relative frequency of class j at node t
* Maximum : when records are equally distributed among all classes implying least information
* Minimum :  when all records belong to one class, implying most information 
* Entropy 越小代表分的越好
  * Entropy based computations are similar to the GINI index computations
  * 最差 1，最好 0
* log\_2 代表有 2 類別，若有 10 類別可以用 log\_10

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoNfZL4HDFG0fdH%2Fentropy_computation.jpg?generation=1573290682152495\&alt=media)

#### Information Gain

$$
GAIN\_{\text{split}} = Entropy(p) - (\sum\_{i=1}^k \frac{n\_i}{n}Entropy(i))
$$

* Measures Reduction in Entropy achieved because of the split. 
* Choose the split that achieves most reduction (maximizes GAIN) 
* Used in ID3 and C4.5
* Disadvantage
  * Tends to prefer splits that result in large number of partitions, each being small but pure.

#### Gain Ratio

$$
GainRATIO\_\text{split} = \frac{GAIN\_\text{split}}{SplitINFO}
$$

$$
SplitINFO = -\sum\_{i=1}^k \frac{n\_i}{n}\log\frac{n\_i}{n}
$$

* Adjusts Information Gain by the entropy of the partitioning (SplitINFO).
* Higher entropy partitioning (large number of small partitions) is penalized!
* Used in C4.5
* Designed to overcome the disadvantage of Information Gain

### Classification error

$$
Error(t) = 1 - \max\_i P(i\mid t)
$$

* Maximum : when records are equally distributed among all classes, implying least interesting information
* Minimum : when all records belong to one class, implying most interesting information
* Error 越小越好
* 最差 1，最好 0

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoPJcdMRPgFdvDR%2Fclassification_error_computation.jpg?generation=1573290682888036\&alt=media)

### Splitting Criteria Comparison

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoRHE95ahvBfXni%2Fdecision_tree_methods_comparison.jpg?generation=1573290682744436\&alt=media)

## Nearest Neighbor Classifiers

* Requires three things
  * The set of stored records
  * **Distance Metric** to compute distance between records
  * **The value of k**, the number of nearest neighbors to retrieve
* To classify an unknown record
  * Compute distance to other training records
  * Identify k nearest neighbors
  * Use class labels of nearest neighbors to determine the class label of unknown record

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoTs50K9gdOUV_G%2Fknn_intuition.jpg?generation=1573290681909498\&alt=media)

* k-NN classifiers are lazy learners
* Compute distance between two points

  $$
  d(p, q) = \sqrt{\sum\_i (p\_i - q\_i)^2}
  $$
* Determine the class from nearest neighbor list
* Choosing the value of k
  * k is too small, sensitive to noise points
  * k is too large, neighborhood may include points from other classes
* Scaling issues
  * Attributes may have to be scaled to prevent distance measures error
    * height, weight, income with different unit
* distance measure issues
  * High dimensional data may cause **curse of dimensionality**
  * Can produce counter-intuitive results
  * Solution
    * Normalize the vectors to unit length

## Bayesian Classifiers

* A probabilistic framework for solving classification problems
* Bayes theorem

  $$
  P(C\mid A) = \frac{P(A\mid C)P(C)}{P(A)}
  $$
* Consider each attribute and class label as random variables 
  * Given a record with attributes $$(A\_1, A\_2, \cdots, A\_n)$$
  * Goal is to predict class $$C$$
* Estimate $$P(C\mid A\_1 , A\_2 ,\cdots,A\_n)$$ directly from data
  * compute the posterior probability for all values of C

$$
P(C\mid A\_1A\_2\cdots A\_n) = \frac{P(A\_1A\_2\cdots A\_n\mid C)P(C)}{P(A\_1A\_2\cdots A\_n)}
$$

## Naïve Bayes Classifier

* Assume independence among attributes

  $$
  P(A\_1 , A\_2 ,\cdots,A\_n\mid C) = P(A\_1\mid C) P(A\_2\mid C)\cdots P(A\_n\mid C)
  $$
* Estimate all $$P(A\_i \mid C\_j)$$
* Maximize $$P(C\_j) \prod P(A\_i\mid C\_j)$$

### Example

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoWjZYuV4grYs95%2Fnaive_bayes_example.jpg?generation=1573290683531096\&alt=media)

* Summary
  * Robust to **isolated noise points**
  * Handle missing values by ignoring the instance during probability estimate calculations
  * Robust to irrelevant attributes
  * **Independence** assumption may not hold for some attributes

## Support Vector Machines

* Find a linear hyperplane (decision boundary) that will separate the data
* Find hyperplane maximizes the margin

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcoY8Tf3YyuBAeYI%2Fsvm_intuition.jpg?generation=1573290681906974\&alt=media)

$$
\text{Margin} = \frac{2}{\lVert \vec{w}\rVert^2}
$$

* This is a constrained optimization problem
  * Numerical approaches to solve it

## Ensemble Methods

* Construct a set of classifiers from the training data
* Predict class label of previously unseen records by aggregating predictions made by multiple classifiers

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQco_VDYUUmpi3m7U%2Fensemble_method_intuition.jpg?generation=1573290681625436\&alt=media)

* Why it works?
  * Suppose there are 25 base classifiers
    * Each classifier has error rate $$\epsilon = 0.3$$
    * Assume classifiers are independent
    * Probability that the ensemble classifier makes a wrong prediction

      $$
      \sum\_{i=13}^{25}\binom{25}{i}\epsilon^i(1-\epsilon)^{25-i}=0.06
      $$
* Methods
  * Bagging
  * Boosting

### Boosting

* Training
  * Produce a sequence of classifiers
  * Each classifier is dependent on the previous one
    * and focuses on the previous one’s errors
  * Examples that are **incorrectly** predicted in previous classifiers are given **higher weights**
* Testing
  * the results of the series of classifiers are combined to determine the final class of the test case
* Records that are wrongly classified will have their weights increased 
* Records that are classified correctly will have their weights decreased

#### AdaBoost

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcobfQbN3iZXpsUy%2Fadaboost_intuition.jpg?generation=1573290683216490\&alt=media)

* The actual performance of boosting depends on the data and the base learner. 
* Boosting seems to be **susceptible to noise**.
  * When the number of outliners is very large, the emphasis placed on the hard examples can hurt the performance. 

## Semi-supervised learning

* Assigning labels to training set
  * expensive, time consuming
* Abundance of unlabeled data
  * LU learning
    * Learning with a small set of labeled examples and a large set of unlabeled examples
  * PU learning
    * Learning with positive and unlabeled examples

| Usage          | Supervised | Semi-Supervised | Unsupervised |
| -------------- | ---------- | --------------- | ------------ |
| labeled data   | yes        | yes             | no           |
| unlabeled data | no         | yes             | yes          |

* Label propagation
  * Each node in the graph is an example
    * Two examples are labeled 
    * Most examples are unlabeled
  * Compute the similarity between examples
  * Connect examples to their most similar examples

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcodq6ZLm70InlYm%2Flabel_propogation_intuition.jpg?generation=1573290682526073\&alt=media)

* Application of PU Learning
  * given a ICML proceedings, find all machine learning papers from AAAI, IJCAI, KDD
  * given one's bookmarks (positive documents), identify those documents that are of interest to him/her from Web sources.
  * Company has database with details of its customer – positive examples, but no information on those who are not their customers
    * No labeling of negative examples from each of these collections. 

### PU Learning 2-step strategy

1. Identifying a set of **reliable negative** documents from the unlabeled set. 
   * Reliable Negative : Human labeling 100% Negative data
2. Building a sequence of classifiers by iteratively applying a classification algorithm and then selecting a good classifier. 

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcogrf7S7QwzRmU2%2Ftwo_step_strategy.jpg?generation=1573290683428191\&alt=media)

## Co-training Algorithm

* Given
  * labeled data L
  * unlabeled data U
* Compute
  * Train **h1** using L
  * Train **h2** using L
  * Allow h1 to label p positive, n negative examples from U
  * Allow h2 to label p positive, n negative examples from U
  * Add these most confident self-labeled examples to L
  * Loop

### Example

Consider the task of classifying web pages into two categories: category for students and category for professors

Two aspects of web pages should be considered

* Content of web pages
  * "I am currently the second year Ph.D. student …"
* Hyperlinks
  * "My advisor is …"

#### Scheme

1. Train a content-based classifier using labeled web pages
2. Apply the content-based classifier to classify unlabeled web pages
3. Label the web pages that have been confidently classified
4. Train a hyperlink based classifier using the web pages that **are initially labeled and labeled by the classifier**
5. Apply the hyperlink-based classifier to classify the unlabeled web pages
6. Label the web pages that have been confidently classified