Cpsc 340

Front 1

Steps in Data mining:

Back 1

1. Collect data

2. Data mining

3. Good Stuff

Front 2

What is data?

Back 2

a collection of objects and their features.

Front 3

Types of Data

Back 3

1. Discrete features

2. Numerical Features( Continuous Features)

Front 4

Give ways that data might not be clean

Back 4

1. Noise (phone)

2. Outliers (instrument error; technical problem)

3. Missing values

4. Duplicated data

Front 5

what is the Best way to clean data?

Back 5

ML is the best way to detect/fix these.

Front 6

What is object in ML+DM?

Back 6

object = IID = independent and identically distributed.

- the order of the objects doesn't matter

- new objects will behave like the existing objects.

The IID assumption implies that our conclusionswill probably also apply to new data.

eg: assignment question would be similar to an exam question.

Front 7

How much data do we need?

Back 7

need more data than categories.

Front 8

What is feature aggregation?

Back 8

combining features to form new features.

Front 9

What is feature selection?

Back 9

Removing features that are not relevant to the task.

Front 10

what is feature transformation?

Back 10

Mathematical transformations:– Square, exponentiation, or take logarithm.

Front 11

What is Discretization?

Back 11

Feature transformation

– Discretization: turn continuous into discrete.

- – Scaling: convert variables to comparable scales

Front 12

how do you ‘look’ at features and highdimensionalobjects?

Back 12

- Summary statistics.

– Visualization.

– ML + DM (later in course).

Front 13

Type of Summary Stat?

Back 13

1. Discrete SS:

for a discrete variable:

- Simple matching coefficient:

- Jaccard coefficient for binary var

2. Continuous SS:

- Measures of location:

- Measures of spread:

- Measures between continuous variables:

Front 14

Type of Visualization

Back 14

1. Basic Plot: f(x) = 2x+1 (2d graph)

2. Historgram

3. Box plot

4. Scatterplot (look at distribution of 2 featuers)

5. scatter plot array(Can plot multiple variables in an array.)

6. Map Coloring

7. Contour Plot

Front 15

What is the IID assumption?

Back 15

The IID assumption implies that our conclusionswill probably also apply to new data.

Front 16

What is quantiles?

Back 16

categories that occur more than t times

Front 17

what is decision stump?

Back 17

decision tree with one rule.

Front 18

Key idea of decision stump

Back 18

we have so many options to make this tree.

There may be more than one optimal solution.

require classification accuracy.

Front 19

classification accuracy

Back 19

“If we use this rule, how many objects do we label correctly?"

Front 20

Running time on this finding the best rule algorithm of the decision tree.

Back 20

O(dtn),

d = # of the objects

n = # of the features that might be the main cause

t = all the possible good threshold to check

Front 21

How to speed up this process?

Back 21

Limiting the threshold to check:

- Restrict the thresholds to the range of each feature.

- Restrict thresholds to values of the features in data.

We will then have just one threshold per one feature.

O(dtn) -> O(n^2d)

With sorting,

O(n^2d) -> O(dnlogn)

Front 22

What does supervised learning do?

Back 22

using data to build programthat outputs labels from input features

Front 23

what does a decision tree do?

Back 23

making a decision via a sequenceof simple rules

Front 24

What is overfitting?

Back 24

lower accuracy on new data.

Front 25

the idea of supervised learning

Back 25

Typical supervised learning steps:1. Build model based on training data X and y.

2. Model makes predictions ‘yhat’ on new data Xtest.

• You win if yhat is similar to true unseen ytest

Front 26

Golden rule of machine learning

Back 26

Minimizing test error is not the goal, but is ameasure of how well we do on new data:

Front 27

What is the decision Tree's idea?

Back 27

1.Start at root note.

2. Branch using splitting rule.

3. Leaf nodes are labeled.

a) If leaf, return label.b) Otherwise, go to 2.

Front 28

What is the idea of Decision Stump?

Back 28

decision tree with one rule.

Go through all objects, and find out which class is more likelygiven rule. (Classification Accuracy)

To learn ‘best’ stump, find the ‘best’ rule.

Front 29

What is the fundamental TradeOff?

Back 29

1. How small you can make the training error.vs.2. How well training error approximates the test error

Front 30

Tell me about validation Error

Back 30

if used once:– unbiased approximation of test error

Can overfit if you use validation error too many times

With Decision Tree, You only evaluate a few depths, so validation error likelyapproximates test error.

Front 31

What can we do with Cross-Validation?

Back 31

You can use CV to select decision tree depth.

• You can also use to decide whether to split:– Don’t split if CV error doesn’t improve.

• Or fit deep decision tree and use CV to prune:– Remove leaf nodes that don’t improve CV error.

Front 32

What does Cross-Validation do?

Back 32

Cross-validation allows using more of the datasetto estimate validation error

Front 33

What is the Golden Rule?

Back 33

Even though what we care about is test error:– YOU CANNOT USE THE TEST DATA TO BUILD MODEL.

• Minimizing test error is not the goal, but is ameasure of how well we do on new data.

Front 34

What do we mean by 'maximizing' over data?

Back 34

“I built 10 models based on half of the data you gave me.”– “One of them classified the other half of the data with 98% accuracy.”

Maximizing over these errors is a biased approximation of test error.– But they only maximized it over 10 models, so bias is probably small.– They probably know about the golden rule.

Front 35

Explain naïve Bayes and its uses.

Back 35

Naïve Bayes is probabilistic classifier based on Bayes rule.

– It’s ‘naïve’ because it makes a strong independence assumption.

– But it tends to work well with bag of words.

Front 36

What is Generative classifiers?

Back 36

build a probability of seeing the features.

– It needs to know the probability of the features, given the class.

– You need one model that knows what spam messages look like.

– You need a second model that knows what non-spam messages look like.

Assume that variables in xiare independent of each other given yi.

Front 37

Again, what is the assumption of Naïve Bayes?***

Back 37

given yi, all xiare conditionally independent of each other.

Front 38

what's the problem with Maximum Likelihood estimate?

Back 38

there is a chance of that one probability can mess up the whole thing.

eg. p(seeing lac | spam) = 0

Front 39

What is parametric method?

Back 39

There are a fixed number of “parameters” in the model (e.g., number of rules).

As you get more data, you can estimate them more accurately.

• But at some point, more data doesn’t help because model is too simple.

Front 40

what is non-parametric method?

Back 40

Number of parameters grows with the number of training examples.

– Model gets more complicated as you get more data.

– E.g., decision tree whose depth grows with the number of examples.

Front 41

What is the problem with KNN?

Back 41

KNN does not know that labels should be translation invariant( rotation, size enlarge)

Solution:

1. The hard/slow way is to modify your distance function:

2. The easy/fast way is to just add transformed data during training

Front 42

Do we have any classifiers that are accurate and run in real time?

Back 42

– Decision trees and naïve Bayes are fast, but often not very accurate.

– KNN is often accurate, but not very fast.

Solution=> Deployed system uses an ensemble method called random forests.

Front 43

What is ensemble methods?

Back 43

classifiers that have classifiers as input.

Eg:

1. Boosting: take simple classifier that underfits, improve its training error.

b) Averaging: take complex classifier that overfits, improve its test error.

Front 44

2 types of averaging (ensemble method)?

Back 44

Model averaging:– Take the mode of the predictions (or average if probabilistic).•

Stacking:– Fit another classifier that uses the predictions as features

Front 45

Two key ingredients in random forests?

Back 45

- Bootstrap sampling: randomize the incoming inputs (same # of inputs but some inputs might be repeated)

– Random splits: randomly pick one feature and split right away (*** do not consider all features when searching for optimal rule)

Front 46

Explain the difference between supervised learning and unsupervised learning.***

Back 46

Supervised learning:

– We have features xiand class labels yi.

– Write a program that produces yifrom xi.

• Unsupervised learning:

– We only have xivalues, but no explicit target labels.

– You want to do ‘something’ with them.

Front 47

What is clustering?

Back 47

– Input: set of objects described by features xi.– Output: an assignment of objects to ‘groups’.

Unlike classification, we are not given the ‘groups’.– Algorithm must discover groups. (ie a group that we find by ourselves)

Front 48

Explain K-means algorithm:

Back 48

– Assign each xito its closest mean.

– Update the means based on the assignment.

– Repeat until convergence.

Front 49

Problem with K-means?

Back 49

It may converge to sub-optimal local solution.

(ie we may not get the true k clusters).

- attributes have to be numerical.

Solution: Do k-means++

Front 50

Explain k-means++ steps

Back 50

-Choose a random data point as the first mean.

– Compute the distance of every point to the closets mean.

– Sample the next proportional to these distances squared.

Front 51

What is density-based clustering? param or non-param?

Back 51

non-parametric clustering method!

- Clusters are defined by connected dense regions.

• Become more complicated the more data we have.

– Data points in non-dense regions are not assigned a cluster

Front 52

Given parameters of Density-based clustering (DBSCAN)

Back 52

– Radius: minimum distance between points to be considered ‘close’.

– MinPoints: number of ‘close’ points needed to define a cluster.

Front 53

Pros and Cons on DBSCAN

Back 53

Cons

-Assigning new points to clusters is expensive.

• In high-dimensions, need a lot of points to ‘fill’ the space

Runtime: O(n^2)

pros:

useful for finding non-convex connectedclusters.

Front 54

Param vs non-param

Back 54

– Fixed-depth decision tree: ‘size’ of the model is O(1) in terms of ‘n’.

– K-nearest neighbours: ‘size’ of the model is O(n) in terms of ‘n’

Front 55

Explain concept of Region-based pruning:

Back 55

for finding closest objects among hugenumber of objects

***Don’t have to compute distances between points in distant regions.