Final Exam

Question 1

What is False Negative Rate?

Answer 1

fraction of positive examples predicted as negative class

FNR = FN / (FN + TP)

Question 2

What 2 things is a ROC curve useful for?

Answer 2

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

Question 3

What are 2 methods to evaluate a model?

Answer 3

Out of bag estimation

Cross validation

Question 4

What is F-measure?

Answer 4

summarizes precision and recall

2TP / ( 2TP + FP + FN)

Question 5

What are the 3 components of the curse of dimensionality?

Answer 5

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 6

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

Answer 6

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

Question 7

Describe the characteristics of the K-means algorithm

Answer 7

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 8

What are the 3 types of data sets?

Answer 8

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 9

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

Answer 9

• 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 10

What is Principal Component Analysis?

Answer 10

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”

Question 11

Describe how self organaizing maps work

Answer 11

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 12

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

Answer 12

We want to reduce the amount of bias.

Question 13

What are the 5 common clustering algorithms?

Answer 13

K-means

Hierarchical

DBscan

Expectation Maximization

Self Organizing Maps

Question 14

What is spatial autocorrelation?

Answer 14

objecsts that are physically close tend to be similar

Question 15

Describe the characteristics of expectation maximization

Answer 15

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 16

What are the 3 normalization schemes used in class?

Answer 16

min-max

z-score

decimal scaling

Question 17

What is the mahalnanobis distance?

Answer 17

• 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 18

What are the two different types of mappings?

Answer 18

1 of n

n of m

Question 19

What is recall?

Answer 19

the fraction of positive examples correctly predicted by the classifier

r = TP / (TP + FN)

Question 20

What are the 3 types of missing values?

Answer 20

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 21

explain the 1 of n mapping:

Answer 21

create 1 new attribute for every ordinal value

Question 22

What is the formula for the bias / variance tradeoff?

Answer 22

Mean Squared Error = bias² + variance

Question 23

What is expectation maximization (EM)?

Answer 23

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 24

What is the difference between a training and test set?

Answer 24

Training set is used to build a model.

Test set is used to test a model.

Question 25

How does the FP growth algorithm mine frequent itemsets?

Answer 25

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

Question 26

How is a ROC curve depicted?

Answer 26

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 27

What are self organizing maps?

Answer 27

An effective clustering algorithm An abstraction of the input data

Question 28

What is accuracy?

Answer 28

Used to compare performance of models of correct predictions / # of predictons TP + TN / (TP + TN + FP + FN)

Question 29

What are the 3 techniques for outlier detection?

Answer 29

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

Question 30

What is False Positive Rate?

Answer 30

fraction of negative examples predicted as positive class FPR = FP / (FP + TN)

Question 31

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

Answer 31

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 32

What is a maximal frequent itemset?

Answer 32

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

Question 33

What are the 3 types of outliers?

Answer 33

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 34

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

Answer 34

FP tree Hash tree

Question 35

What is percision?

Answer 35

The fraction of positive examples out of examples declared as positive p = TP / TP + FP

Question 36

What are the 3 preprocessing techniques?

Answer 36

1. Feature selection 2. Dimensionality reduction 3. Normalization

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 the apriori principal?

Answer 38

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 39

What is the Minkowski Distance?

Answer 39

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

Question 40

Describe the charactersistics of hierarchical clustering

Answer 40

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 41

Recite the Apriori algorithm?

Answer 41

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 42

What is the True Negative Rate / specificity?

Answer 42

fraction of negative examples predicted correctly by the classifier TNR = TN / (TN + FP)

Question 43

What is a frequent itemset?

Answer 43

An itemset that meets the minsup threshold.

Question 44

Describe the characteristics of self organizing maps

Answer 44

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 45

explain the n of m mapping

Answer 45

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

Question 46

What is True Positive Rate / sensitivity?

Answer 46

fraction of positive examples predicted correctly by the classifier TPR = TP / (TP + FN)

Question 47

How is a ROC curve constructed?

Answer 47

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

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 AdaBoost method used in ensembles.

Answer 49

* 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 50

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

Answer 50

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

Question 51

What are 4 sampling schemes?

Answer 51

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 52

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

Answer 52

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 53

What is a closed itemset?

Answer 53

An itemset is closed if none of its immediate supersets has the same support as the itemset. It's a compressed representation of support