Final Exam

Question 1

What are the 3 normalization schemes used in class?

Answer 1

min-max

z-score

decimal scaling

Question 2

What are the 3 preprocessing techniques?

Answer 2

1. Feature selection
2. Dimensionality reduction
3. Normalization

Question 3

What is spatial autocorrelation?

Answer 3

objecsts that are physically close tend to be similar

Question 4

What are the 3 types of data sets?

Answer 4

Record

1. data matrix
2. document data
3. transaction data

Graph

1. web data
2. molecular structures

Ordered

1. spatial
2. temporal
3. sequence
4. sequential

Question 5

What are the two different types of mappings?

Answer 5

1 of n

n of m

Question 6

explain the 1 of n mapping:

Answer 6

create 1 new attribute for every ordinal value

Question 7

explain the n of m mapping

Answer 7

create 1 new attribute with a unique representation for each ordinal value

Question 8

What are the 3 types of missing values?

Answer 8

Missing completely at random

• scratch random items out
• can subsitute mean but effects variance

Missing at Random

• value missing is due to value of another variable

Non Ignorable Data

• Value missing is due to limitations of measuring device

Question 9

What are 4 sampling schemes?

Answer 9

1. Simple Random Sampling: each object is selected with equal probability
2. Sampling with replacement: do not remove the object when sample is selected
3. Sampling without replacement: remove the object when sample is selected
4. Stratified sampling: split the data into several paritions and sample randomly from each one

Question 10

What is the difference between a training and test set?

Answer 10

Training set is used to build a model.

Test set is used to test a model.

Question 11

Why is sampling important with respect to a training and test set?

Answer 11

We want to reduce the amount of bias.

Question 12

What is accuracy?

Answer 12

Used to compare performance of models

of correct predictions / # of predictons

TP + TN / (TP + TN + FP + FN)

Question 13

What is True Positive Rate / sensitivity?

Answer 13

fraction of positive examples predicted correctly by the classifier

TPR = TP / (TP + FN)

Question 14

What is the True Negative Rate / specificity?

Answer 14

fraction of negative examples predicted correctly by the classifier

TNR = TN / (TN + FP)

Question 15

What is False Positive Rate?

Answer 15

fraction of negative examples predicted as positive class

FPR = FP / (FP + TN)

Question 16

What is False Negative Rate?

Answer 16

fraction of positive examples predicted as negative class

FNR = FN / (FN + TP)

Question 17

What is percision?

Answer 17

The fraction of positive examples out of examples declared as positive

p = TP / TP + FP

Question 18

What is recall?

Answer 18

the fraction of positive examples correctly predicted by the classifier

r = TP / (TP + FN)

Question 19

What is F-measure?

Answer 19

summarizes precision and recall

2TP / ( 2TP + FP + FN)

Question 20

What is the apriori principal?

Answer 20

if an itemset is frquent, then all of its subsets are frequent. Conversely, if an itemset if infrequen, then all of its supersets must be infrequent too.

Question 21

Recite the Apriori algorithm?

Answer 21

Let k = 1

generate frequent itemsets of length 1

Repeat:

1. generate (k+1) candidate itemsets from k frequent itemsets
2. prune candidate itemsets containing subsets of length k that are infrequent
3. count support for each canddiate by scanning the DB
4. eliminate candidates that are infrequent

Question 22

What is a frequent itemset?

Answer 22

An itemset that meets the minsup threshold.

Question 23

What is a maximal frequent itemset?

Answer 23

An itemset is maximal frequent if none of its immediate supersets is frequent

Question 24

What is a closed itemset?

Answer 24

An itemset is closed if none of its immediate supersets has the same support as the itemset.

It’s a compressed representation of support

Question 25

How is a ROC curve depicted?

Answer 25

A graphical chart with TP rate on y axis and FP rate on x axis. Each points repersents a point that corresponds to a model induced by a classifier.

Question 26

What 2 things is a ROC curve useful for?

Answer 26

1. Picking the best model after repeatedly adjusting a specific parameter (t) 2. Comparing the relative performance among classifiers

Question 27

In the Apriori frequent itemset generation algorithm, what is a hash tree used for?

Answer 27

Determining if each enuerated k-itemset corresponds to an existing candidate itemset.

Question 28

Describe an FP tree used by the FP growth algoriothm for frequent itemset generation

Answer 28

Reads data set one transaction at a time Maps each transation onto a path in the FP-tree Paths may overlap as transactions are similar The more paths overlap, the more compression Sometimes makes tree small enough to fit into main memory

Question 29

What are the two datastructures used in the Apriori Algorithm and the FP Growth Algorithm?

Answer 29

FP tree Hash tree

Question 30

How does the FP growth algorithm mine frequent itemsets?

Answer 30

It uses a recursive divided-and-conquer approach It uses pointrs to assist frequent itemset generation. It requires preprocessing.

Question 31

What is the mahalnanobis distance?

Answer 31

* takes the average values of pairs of attributes and subtracts them from the mean of values * an alternative to normalizzation (scaling is built in) * take into account the dspread of the data in a direction

Question 32

What is the Minkowski Distance?

Answer 32

* a generalization of the euclidean distance * it's the same as the euclidean distance, but with a parameter r instead of 2

Question 33

What difference measures can be used to deal with attributes that have different ranges?

Answer 33

1. Normalization techniques - scaling - min-max - decimal scaling 2. Can choose an algorithm that is not affected by different ranges (decision trees) 3. Mahalanobis distance 4. PCA - cpatures largest variation and reduces dimensions

Question 34

What are the 3 types of outliers?

Answer 34

1. Point: just a point on a 1D graph 2. Contextual: depends on the context that you are looking at 3. Collective: an outlier that exists as a sequence

Question 35

What are the 3 techniques for outlier detection?

Answer 35

1. Statistical (grubbs test & linear regression) 2. Density based (DBscan) 3. Proximity based (KNN)

Question 36

What are 2 methods to evaluate a model?

Answer 36

Out of bag estimation Cross validation

Question 37

What is bagging with respect to data mining and ensemble methods?

Answer 37

Bagging (bootstrap aggregating) is basically out of bag estimation. Sample repreatedly with replacement from the original data to create new training sets. Reduces variance and helps to avoid overfitting.

Question 38

What is boosting with respect to data mining and ensemble methods?

Answer 38

* Give more emphasis on specific examples that are difficult to classify. Assign a higher weight, greater probability of being selected to them. * Records that are wrongly classified will have their weights increased. * Records that are classified correctly will have their weights decreased.

Question 39

Describe the AdaBoost method used in ensembles.

Answer 39

* AdaBoost creates many classifiers / models and repreatedly draws from samples. * Samples that are easy to classifiy get a lower weight, and ones that are harder to classify get a higher weight. * If any intermediate rounds produce an error rate higher than 50%, the weights are reverted back and the resampling procedure is repreated. * The classifier also gets a weight.

Question 40

What conditions must be satisified for ensemble methods to improve the overall classification accuracy?

Answer 40

1) the different classifiers make different mistakes in the data 2) the different classifiers perform better than random guessing

Question 41

What are the 3 components of the curse of dimensionality?

Answer 41

1. Runtime: if the algorithm does not behave at most linear with the # of attributes, the runtime increase too quickly 2. Amount of Data: The amount of samples needed to cover the space with equal density grows exponentially with the number of dimensions 3. Distances: distances between the data becomes meaningless. The maximum distance between data points does not grow linearly with the # of dimensions.

Question 42

What is the formula for the bias / variance tradeoff?

Answer 42

Mean Squared Error = bias² + variance

Question 43

How is a ROC curve constructed?

Answer 43

Sort the threshold values from lowest to highest for all of the samples. Plot the TPR vs the TNR for each sample.

Question 44

What are the 5 common clustering algorithms?

Answer 44

K-means Hierarchical DBscan Expectation Maximization Self Organizing Maps

Question 45

What is expectation maximization (EM)?

Answer 45

Represents data as distrubutions (usually nomal distribution) Randomly initialize parameters (mean and standard deviation) 1. Expectation: calculate likelyhood of falling into distribution based on parameters & assign data to parameters 2. Maximization: find parameters that best represent the assignments

Question 46

Describe the characteristics of the K-means algorithm

Answer 46

1. deterministic? no (difference results each time) 2. suceptible to falling in a local minimum? yes 3. need to specify # of clusters? yes 4. is noise removed? no 5. partitioned based? yes 6. can handle varying densities? yes

Question 47

Describe the charactersistics of hierarchical clustering

Answer 47

deterministic? yes suceptible to falling in a local minimum? no need to specify # of clusters? no is noise removed? yes partitioned based? no can handle varying densities? yes

Question 48

Describe the characteristics of the DB scan clustering algorithm

Answer 48

deterministic? yes suceptible to falling in a local minimum? no need to specify # of clusters? no is noise removed? yes partitioned based? yes can handle varying densities? no

Question 49

Describe the characteristics of expectation maximization

Answer 49

deterministic? no (random component at start) suceptible to falling in a local minimum? yes need to specify # of clusters? no (run multiple times) is noise removed? no partitioned based? yes can handle varying densities? not sure...

Question 50

Describe the characteristics of self organizing maps

Answer 50

deterministic? no (the map is randomly initialized) suceptible to falling in a local minimum? yes need to specify # of clusters? is noise removed? no partitioned based? not sure... can handle varying densities? not sure...

Question 51

What are self organizing maps?

Answer 51

An effective clustering algorithm An abstraction of the input data

Question 52

Describe how self organaizing maps work

Answer 52

Randomly initialize map repeat: compare a sample and all input datum in map select the prottype that is most imilar update the winner and neighbourhood to more ismilar to winner

Question 53

What is Principal Component Analysis?

Answer 53

It's a preprocessing technique that maps the data to lower dimensional space It captures the largest variation reduces noise and dimensions "knee in curve"