Data Pre-Processing

Discretization

Binarization

Convert continuous or numerical data into binary values (0, 1) based on some thresholds.

Binning (Quantization)

Group continuous data into bins (Map continuous data to discrete or categorical one).

• Need to decide bins size (width of each bin)

Here are some interesting methods of binning

Fixed-width binning

Each bin has specific numeric range, it can be any scale (custom designed, automatically segment, linear, exponential)

• Simple
• It may be good on uniformly distributed (fairly even spread)

Fixed-frequency binning

Each interval contains approximately the same number of data points

• When data is not uniformly distributed, we can ensure that each bin contains approximately the same number of data points

Quantile Binning

Binning base on quantiles (values that divide the data into equal portions)

4-Quantile = Quartiles (Divide data into quarters) 10-Quantile = Deciles (Divide data into tenths)

Steps In K - Quantile = [$Q_1,Q_2,Q_3,Q_4,...,Q_k-1$] To find position of value of boundary between quantile, find $Q_i$ $Q_i=\frac{i}{K}(n+1{)}^{th}term$

• K = Number of quantile
• n = Number of data in dataset
• i = Number of Quantile

Imbalanced Techniques - Sampling and SMOTE

Imbalanced occur when one class in dataset has more samples than another class. It can be caused by

• Bias while sampling
• Error from measurement
• Natural of that data

Majority Class = Many samples class Minority Class = few samples class

It harder for a model to learn characteristic of Minority Class + some models are assume an equal distribution of class so imbalance can cause problem.

Sampling

Random Under-sampling

Randomly eliminate samples from majority class until classes distribution balance

When training data is not that small, we can afford under-sampling

Advantages

• Reduce model training time: fewer data points

Disadvantages

• Reduced dataset not represent population or true distribution
• May loss useful data

Random Over-sampling

Randomly copy samples in minority class to get more balance distribution

When training data is less, over-sampling would be better than under-sampling

Advantages

• No information loss

Disadvantages

• Overfitting

Synthetic over-sampling: SMOTE

Take subsets of minority class then generate synthetic data points from those subsets and add those new data points to dataset.

It solve overfitting problem of over-sampling

Advantages

• Help with overfitting problem
• No data loss

Disadvantages

• No consideration of majority class
• Addition noise to dataset

Dimensional Reduction - PCA

PCA reduces a large number of variables into a set of Principle Component axes.

Why we need to do dimension reduction

Most of the time, we have dataset which has high dimension (many columns or features), we can't visualize those datasets so dimension reduction lend a hand to help with this problem.

Dimension Reduction algorithm will try to preserve all information in higher dimension data and reduce those data into 2-3D where we can visualize and understand(in other word, extract feature out of those high-dimensional data) them.

It can apply prior to applying some models which get affected a lot by Curse of Dimensionality

How to perform PCA

Ref: https://www.youtube.com/watch?v=MLaJbA82nzk

Features Mean Calculation

$\bar{x}=\frac{4+8+13+7}{4}=8$

$\bar{y}=\frac{11+4+5+14}{4}=8.5$

Covariance Matrix Let Ordered Pairs are (x, x) (x, y) (y, x) (y, y)

• Find covariance of all ordered pairs

$$\boxed{cov(A,B)=\frac{1}{N-1}\sum _{k=1}^N(A_k-\bar{A})(B_k-\bar{B})}$$

$cov(x,x)==\frac{1}{4-1}[(4-8{)}^2+(8-8{)}^2+(13-8{)}^2+(7-8{)}^2]=14$ $cov(x,y)=\frac{1}{4-1}[(4-8)(11-8.5)+(8-8)(4-8.5)+(13-8)(5-8.5)+(7-8)(14-8.5)]=-11$ $cov(y,y)=cov(x,y)=-11$ $cov(y,x)=\frac{1}{4-1}[(11-8.5{)}^2+(4-8.5{)}^2+(5-8.5{)}^2+(14-8.5{)}^2]=33$

Calculate Eigen value and Eigen Vector then Normalized eigen vector

• Eigen value

$$\begin{array}{c}det(S-\lambda I)=0\end{array}$$

where

$$\begin{array}{r}S=\text{Covariane Matrix}=\left[\begin{array}{cc}14& -11\\ -11& 23\end{array}\right]\\ I=\text{Identity Matrix}=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\end{array}$$ $$\begin{array}{r}\det (S-\lambda I)=0\\ (14-\lambda )(23-\lambda )-(-11\times -11)=0\\ {\lambda }^2-37\lambda +201=0\\ \\ \lambda =30.3849,6.6151\to {\lambda }_1>{\lambda }_2\\ \text{First Principle Component}={\lambda }_1=30.3849and{\lambda }_2=6.6151\end{array}$$

• Eigen Vector $U_1$ of ${\lambda }_1$

$$(S-\lambda I)U_1=0$$ $$\left[\begin{array}{cc}14-{\lambda }_1{u}_1& -11u_2\\ -11u_1& (23-{\lambda }_1)u_2\end{array}\right]=0$$ $$U_1=\left[\begin{array}{c}11\\ -16.3849\end{array}\right]$$

• Normalize the eigen vector $U_1$ get unit eigen vector $e_1$

e1=[11112+(−16.3849)2−16.3849112+(−16.3849)2]e_1 = \begin{bmatrix} \dfrac{11}{\sqrt{11^2+(-16.3849)^2}} \\ -\dfrac{16.3849}{{\sqrt{11^2+(-16.3849)^2}}} \end{bmatrix}e1​=​112+(−16.3849)2​11​−112+(−16.3849)2​16.3849​​​ $$e_1=\left[\begin{array}{c}0.5574\\ -0.8303\end{array}\right]\text{and }{e}_2(from{\lambda }_2)=\left[\begin{array}{c}0.8303\\ 0.5574\end{array}\right]$$

Derive new dataset

$$P_{1}1=e_1^T\left[\begin{array}{c}4-8\\ 11-8.5\end{array}\right]=-4.3052$$ $$P_{1}2=e_1^T\left[\begin{array}{c}8-8\\ 4-8.5\end{array}\right]=-4.3052$$

Model Evaluation

Cross-Validation

Technique to evaluate predictive models by partitioning the original sample into a training set to train the model and a test set to evaluate it.

There are many interesting methods those use cross-validation technique.

We can also use the cross validation set to tune model hyperparameters and test with test set later.

Holdout method

Separate dataset into two sets training set and testing set

• Use training set to train only and then predict testing set and validate the model on it

K-fold cross validation

Randomly divide dataset into K equal-size parts, $X_1{X}_2{X}_3...X_k$, use K-1 part as training set and the left one is Validation set

Advantage

• Good to use when don't have a large enough dataset (When a single, random sample of the data is not representative sample of the underlying distribution)

**Disadvantage

• K have effect, larger K $\to$ larger training sets that overlap more, leading to a stronger dependence between the results in the K folds
• Expensive computational time

Leave-one-out cross validation

Extreme case of K-fold cross validation, only one sample is used as a Validation set while the rest are used to train our model

Partitioning Clustering

Data clustering concept

• Grouping similar data points together based on certain criteria
• Unsupervised Learning
• Use Distance/Similarity Metric

The goal of clustering is to discover natural groupings or clusters in the data without any prior knowledge of the groupings.

Pre-processing for clustering

• Normalize the data
• Remove noises or outliers
• Approach few numbers of dimensions (dimensional reduction)

K-means

How to perform K-means

Let $\text{A1=(3,8), A2=(9,4), A3=(4,9), A4=(2,2), A5=(10,5), A6=(2,4), A7=(6,8), A8=(4,3), A9=(4,7)}$

\begin{document}
\begin{tikzpicture}[scale=0.7]

    \coordinate (A1) at (3,8);
    \coordinate (A2) at (9,4);
    \coordinate (A3) at (4,9);
    \coordinate (A4) at (2,2);
    \coordinate (A5) at (10,5);
    \coordinate (A6) at (2,4);
    \coordinate (A7) at (6,8);
    \coordinate (A8) at (4,3);
    \coordinate (A9) at (4,7);
    
    \foreach \point in {A1, A2, A3, A4, A5, A6, A7, A8, A9}
        \fill (\point) circle (3pt);
    
    \foreach \point/\label in {A1/A1, A2/A2, A3/A3, A4/A4, A5/A5, A6/A6, A7/A7, A8/A8, A9/A9}
        \node[above right] at (\point) {\label};
    
    \draw[help lines,gray!30] (0,0) grid (12,10);
    \foreach \x in {1,2,...,12}
        \node[below] at (\x,0) {\x};
    \foreach \y in {1,2,...,10}
        \node[left] at (0,\y) {\y};
    
    \draw[->] (0,0) -- (12,0) node[right] {$x$};
    \draw[->] (0,0) -- (0,10) node[above] {$y$};
\end{tikzpicture}
\end{document}

In this problem we will use $K=3$

Goal: Find member and centroid of each cluster

Step

1. Choose K-centroid randomly (It can be any points)

$$\begin{array}{r}{a}_1=(4,9)\\ a_2=(2,2)\\ a_3=(9,4)\end{array}$$

2. Find the nearest centroid $c_j$ for each point and assign each point to those centroid

$$argmi{n}_j(\text{Distance}(x_i,c_j))$$

In this problem we use Euclidean Distance

$$\text{Distance}(A,B)=\sqrt{(A_X-B_X{)}^2+(A_Y-B_Y{)}^2}$$

Let assume that we have assigned each point to its nearest centroid using Euclidean distance as a matric distance and get this result.

• j1 has [A1, A3, A7, A9]
• j2 has [A4, A6, A8]
• j3 has [A2, A5]

3. Find new centroid $c_j$ and see if cluster member change or not

• If cluster member remain the same : Finish!
• If cluster member change : Find new centroid again!

from j = 1 to K

$$\begin{array}{r}{c}_j(X)=\frac{1}{n}\sum _{i=1}^n{x}_i\\ c_j(Y)=\frac{1}{n}\sum _{i=1}^n{y}_i\\ \\ c_j=(c_j(X),c_j(Y))\end{array}$$

where

$$\begin{array}{r}n=\text{Number of points in cluster with centroid }{c}_j\\ x_i=\text{X coordinate of Point in cluster with centroid }{c}_j\\ y_i=\text{Y coordinate of Point in cluster with centroid }{c}_j\end{array}$$

Example

• j1 has [A1, A3, A7, A9]
• j2 has [A4, A6, A8]
• j3 has [A2, A5]

Member of cluster is not changed so FINISH!

Result

\begin{document}
\begin{tikzpicture}[scale=0.7]
    \coordinate (A1) at (3,8);
    \coordinate (A2) at (9,4);
    \coordinate (A3) at (4,9);
    \coordinate (A4) at (2,2);
    \coordinate (A5) at (10,5);
    \coordinate (A6) at (2,4);
    \coordinate (A7) at (6,8);
    \coordinate (A8) at (4,3);
    \coordinate (A9) at (4,7);
    
    \foreach \point/\label/\color in {A1/A1/blue, A2/A2/yellow, A3/A3/blue, A4/A4/green, A5/A5/yellow, A6/A6/green, A7/A7/blue, A8/A8/green, A9/A9/blue}
        \fill[\color] (\point) circle (3pt) node[above right, \color] {\label};
    
    \coordinate (C1) at (4.25,8);
    \coordinate (C2) at (2.667,3);
    \coordinate (C3) at (9.5,4.5);
    
    \foreach \centroid/\label in {C1/c1, C2/c2, C3/c3}
        \fill[red] (\centroid) circle (5pt) node[below right] {\label};
    
    \foreach \point/\centroid/\color in {A1/C1/blue, A3/C1/blue, A7/C1/blue, A9/C1/blue, A4/C2/green, A6/C2/green, A8/C2/green, A2/C3/yellow, A5/C3/yellow}
        \fill[\color] (\point) circle (3pt);
    
    \draw[help lines,gray!30] (0,0) grid (12,10);
    \foreach \x in {1,2,...,12}
        \node[below] at (\x,0) {\x};
    \foreach \y in {1,2,...,10}
        \node[left] at (0,\y) {\y};
    
    \draw[->] (0,0) -- (12,0) node[right] {$x$};
    \draw[->] (0,0) -- (0,10) node[above] {$y$};
\end{tikzpicture}
\end{document}

Clustering Evaluation

Elbow Method

Help choose the right number of clusters for your clustering algorithm by plot graph between the number of clusters and the sum of squared distances

Within Cluster Sum of Squares - WCSS

$$WCSS=\text{Sum of distance between each point its centroid in each cluster}$$ $$WCSS=\sum _{\text{P in Cluster 1}}distance(P_i,C_1{)}^2+\dots$$

then plot on graph where y is WCSS and x is Number of clusters

Association Rule

Apriori Algorithm

Ref: https://www.youtube.com/watch?v=rgN5eSEYbnY

Goal : get frequent itemset which is a set of data that tend to happen together.

Step

1. Filter item with minimum support

$$\text{Support}(A)=\frac{\text{Frequecy}(A)}{N}$$

Filter out the item which Support < Minimum support

2. Create itemset

To create itemset

2-Itemset

3-Itemset

4-Itemset

3. Get Association Rule and Calculate Confidence and Lift

Association define as

$$A\to B$$

If A exist in transaction then B tend to exist too. For example, If Customer 1 buy A then he tend to buy B too.

We usually call

$$\begin{array}{r}A:Antecedent\\ B:Consequent\end{array}$$

Confidence

$$\boxed{\begin{array}{r}\\ \text{confidence}(A\to B)=\frac{\text{Support}(A,B)}{\text{Support}(A)}\\ \\ \text{Support}(A\to B)=\frac{\text{Frequecy}(A,B)}{N}\\ \end{array}}$$

Measures how often a rule is true

• if A occurs, B is likely to occur

Minimum Confidence set a minimum line for confidence

Let say, minimum confidence = 0.2

Lift

$$\boxed{\text{Lift}(A,B)=\frac{\text{Support}(A,B)}{Support(A)\times Support(B)}}$$

Measure of the strength of the association between two items

• Lift greater than 1 indicates that the presence of item A has a positive effect on the presence of item B

Decision Trees and Random Forest

Terminology

Node Impurity

Node is like a dataset or subset of data in decision tree. Pure Node is a subset where all samples are in the same class

Impure Node is a subset where samples has same portion of classes (#Class + = #Class -)

Entropy

Entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes

When we measure entropy of something, it like we measure how much information we need to describe that thing or measure randomness in the system

In decision tree algorithm, entropy measure impurity in the Node

• Pure Node: entropy = 0 (no impurity + need only few information to describe that node) $\to$ low randomness

$$\boxed{\begin{array}{rl}& \\ \text{Entropy(S)}& =\sum _{i=1}^C\log (\frac{1}{P_i})P_i\\ & \\ & =-\sum _{i=1}^C{P}_i\log (P_i)\\ & \\ & \text{where C = Number of classes in Node/Dataset S}\\ & \end{array}}$$

Example

Find entropy of this Node S where class label are + and -.

$$\begin{array}{rl}\text{Entropy(S)}& =-\sum _{i=1}^C{P}_i\log (P_i)\\ & \\ & =-(0.6\times {\log }_2(0.6))-(0.4\times {\log }_2(0.4))=0.970951\end{array}$$

NOTE: when $P_i=0$, entropy = 0 ()

Information Gain

In decision tree, information gain measure how much entropy will be reduced after each split

• Compute the difference between entropy before split and average of entropy after the split
• Less reduction of entropy $\to$ More Information Gain

Information gain help us select best feature to use to split the data at each internal node of the decision tree

• Feature with the highest information gain is chosen as the split feature

$$\boxed{\begin{array}{r}\\ \text{GAIN}(S,A)=Entropy(S)-\sum _{V\in Values(A)}\frac{|S_V|}{|S|}\times Entropy(S_V)\end{array}}$$ $$\begin{array}{rl}P& =\text{Parent Node or The Subset before the split}\\ A& =\text{Feature that we are going to find the information gain}\\ |S_V|& =\text{Times that value V appear in S}\\ |S|& =\text{Size of entire S}\\ Entropy(S_V)& =\text{Entropy of the particular feature}\\ Value(A)& =\text{Set of all possible values of feature A}\end{array}$$

Example

Let use the previous example where $Entropy(S)=0.970951$

$$\begin{array}{rl}\text{GAIN}(S,A)& =Entropy(S)-\sum _{V\in Values(A)}\frac{|S_V|}{|S|}\times Entropy(S_V)\\ & =0.979951-((\frac{2}{5}\ast 0)+(\frac{3}{5}\ast 0.9182))=0.429031\end{array}$$

GINI Index

GINI index also measure the impurity, it is like information gain but compute differently (GINI faster to compute)

$$\boxed{GINI(E)=1-\sum _{j=1}^C{p}_j^2}$$

Example

Find GINI index of Sex

$F=$ 2 {2+, 0-} $M=$ 3 {1+, 2-} $S$ = 5 {3+, 2-}

$GINI(F)=0$ $GINI(M)=1-((\frac{1}{3}{)}^2+(\frac{2}{3}{)}^2)=\mathrm{1.3333..}$

Decision Trees

Decision Trees construction

Too lazy laew, doo this one https://www.youtube.com/watch?v=_L39rN6gz7Y

Steps

Parameters

• Max Depth: Maximum depth of the tree
  • Higher depth: Lead to overfit
• Min Sample Split: Minimum sample require to split an internal node
  • Prevent splitting with too few sample
• Min Sample Leaf: Minimum sample require to be leaf node
  • Prevent overfitting
• Max Features: Maximum number of features to consider when splitting a node
• Criterion: GINI, Entropy

Random Forest

Pick a random subset S, of training samples

• For each subset => grow a full tree
• Given, a new data point X
• Classify X using each of the trees
• For example, use majority vote: class predicted most often

Evaluation

Decision Tree is mainly use as classifier so we can use Evaluate with Precision/Recall, F-Score and Confusion Matrix

Recommenders Systems

Information filtering system that implicitly or explicitly capture a user's preference and generate a ranked list of items that might be of interest to the user.

Types of recommender systems

Collaborative

Content-Based

Knowledge-Based

Hybrid

Different types of Recommenders Systems

Evaluation of Recommenders Systems

Business Applications of Analytics