Data Mining

Question 1

Data Mining

Answer 1

Extraction of implicit, unknown, useful information

Question 2

KDD

Answer 2

Knowledge Discovery from Data

Question 3

Descriptive vs. Predictive

Answer 3

Descriptive extract interpretable models describing data, meanwhile predictive methods predict unknown or future values.

Question 4

Types of attributes

Answer 4

Nominal: Not ordered data (eye color, ID numbers)
Ordinal: Ordered data (grades, rankings, height)
Interval: By ranges (calendar dates)
Ratio: Scaled data (temperature in Kelvins, Length, time)

Question 5

Properties of attributes

Answer 5

Distinctness (D)
Order (O)
Addition (A)
Multiplication (M)

Nominal -> D
Ordinal -> D, O
Interval -> D, O, A
Ratio -> D, O, A, M

Question 6

Discrete vs. Continuous

Answer 6

Discrete has a finite set of values, meanwhile continuous have infinite possible values.

Question 7

Data Quality Problems

Answer 7

• Noise: Modification of original values.
• Outliers: Data objects considerably different than most of the other data.
• Missing Values: Data not collected or attributes not applicable for all objects.
• Duplicate data: Merging problems

Question 8

Data Reduction Types

Answer 8

• Sampling
• Feature Selection / Dimensionality reduction

Question 9

Data Reduction Types

Answer 9

• Sampling
• Feature Selection / Dimensionality reduction

Question 10

Discretization

Answer 10

Supervised or unsupervised conversion of continuous values into a finite set of discrete values.

Question 11

Binarization

Answer 11

One hot encoding

Question 12

Similarity and Dissimilarity

Answer 12

Two measures of how alike and different two data objects are.
[0-1] -> 1 refers to maximum _______ (similarity or dissimilarity)

Question 13

Types of distance measures

Answer 13

• Euclidean Distance
• Minkowski Distance
• Mahalanobis Distance
• Cosine Similarity
• SMC Similarity
• Combined similarities

Question 14

Correlation

Answer 14

Measure between [-1, 1] of the linear relationship between two data objects.

corr(x, y) = covariance(x,y) / std_deviation(x)*std_deviation(y)

Question 15

Association Rules

Answer 15

Extraction of frequent correlations or pattern from a transactional database.

Question 16

AR: Itemset

Answer 16

A set of items.
Example: {Beer, Diapers}

Question 17

AR: Support

Answer 17

Fraction of transactions that contain an itemset.
Example: sup({beer, diapers})=2/5

Question 18

AR: Frequent Itemset

Answer 18

An itemset whose support is greater or equal to a minus threshold.

Question 19

AR: Confidence

Answer 19

Frequency of {A, B} in transactions containing A, where A=>B.
Example: conf=sup(A,B)/sup(A)

Question 20

Association Rule Extraction Steps

Answer 20

1. Extract frequent item sets
2. Extract association rules

Question 21

AR: Brute-force approach

Answer 21

Generate all possible item sets and extract association rules. Computationally unfeasible.

Question 22

AR: Apriori Principle

Answer 22

If an itemset is frequent, then all of its subsets must also be frequent.
Example: {A,B} -> Frequent
{A} and {B} must also be frequent.

Question 23

AR: Apriori Algorithm

Answer 23

1. Extract 1 element itemsets
2. Prune item sets below minusup
3. Generate new possible item sets.
4. Loop
   Draw it or create an example.

Question 24

Association Rule Extraction Algorithms

Answer 24

• Brute-force approach
• Apriori Algortihm
• FP-growth algorithm

Question 25

AR: FP-growth Algorithm

Answer 25

1. Build header table by sorting items (NOT item sets) in decreasing support order. 2. Add header itemsets to frequent if support is greater than minsup. 3. FP-tree construction 4. Select lowest item in header table. 5. Create new transaction with FP-tree. 6. Repeat, exploring all items in the latest header table.

Question 26

AR: Correlation

Answer 26

r: A => B conf(r) / sup(B) Statistical independence -> correlation = 1 Positive correlation -> correlation>1 Else negative.

Question 27

Accuracy

Answer 27

Quality of the prediction

Question 28

Interpretability

Answer 28

Interpretable?

Question 29

Incrementality

Answer 29

Model updating in presence of new labelled records

Question 30

Efficiency

Answer 30

Building and prediction times

Question 31

Scalability

Answer 31

Training set size and attribute number

Question 32

Robustness

Answer 32

How it reacts to noise and missing data

Question 33

Gini Index Formula

Answer 33

NODES: Gini(N1) = 1 - sum[P(C)^2] Example: C1 1 C2 5 P1=1/6 P2=5/6 1-P1^2-P2^2-... SPLITS: Gini(split) = SUM[(#NodeKRecords/#SplitRecords)*Gini(Nk)

Question 34

Decision Tree Elements

Answer 34

Node: Final prediction node Split: Nodes containing another attribute

Question 35

Gini Index

Answer 35

Measures impurity of a node or split. 0: low impurity 1/#records: high impurity

Question 36

Gini Index for continuous values

Answer 36

1. Calculate Gini index for each range 2. Select one range between each continuous value.

Question 37

Entropy Index

Answer 37

Entropy = - SUM[P(Ck) log2 P(Ck)]

Question 38

Decision Tree Evaluation

Answer 38

Accuracy: Average Interpretability: For small trees Incrementality: Not incremental Efficiency: Fast Scalability: Scalable Robustness: Difficult management of missing data

Question 39

Random Forest

Answer 39

Divides original training data in random subsets, then develops a decision tree for each subset and label is decided by majority voting.

Question 40

Random Forest Evaluation

Answer 40

Accuracy: Better than decision trees Interpretability: No Incrementality: No Efficiency: Fast Scalability: Scalable Robustness: Robust

Question 41

Rule Based Classifiers

Answer 41

Classify records by using a collection of “if...then...” rules. (Condition) → y

Question 42

Rule Based Classifier Evaluation

Answer 42

Accuracy: Better than decision trees Interpretable Not incremental Efficient Scalable Robust

Question 43

Instance Based Classifiers

Answer 43

Store training records and use them to predict the class label of unseen cases.

Question 44

K-nearest Neighbors

Answer 44

Selects label based on the k nearest neighbors

Question 45

K-nearest Neighbor Evaluation

Answer 45

Accuracy: Average Not interpretable Incremental Efficient building but slow classification Scalable Distances might affect robustness

Question 46

Bayesian Classification

Answer 46

Computes probability that a given record belongs to C, calculated using Bayes theorem. X: Record C1: class 1 C2: class 2 For C1: P(X1|C1)*P(X1|C1)*...*P(C1) P(X1|C1) = #ofX1s / #ofC1s P(C1) = #ofC1s / #ofRecords

Question 47

Bayes Classifier Evaluation

Answer 47

Accuracy: Average Not interpretable Incremental Efficient Scalable Robust for statistically independent attributes

Question 48

SVM Evaluation

Answer 48

Good accuracy Not interpretable Not incremental Averagely efficient Medium scalability Robust

Question 49

Cross validation

Answer 49

1. Partitioning data into K subsets 2. Train on K-1 partitions and test on remaining one 3. Repeat for all subsets (or folds)

Question 50

Confusion Matrix

Answer 50

Table with true positives...

Question 51

Accuracy

Answer 51

correct/number of classified objects Not appropriate for unbalanced class label distributions or classes with different relevances.

Question 52

Recall

Answer 52

Number of objects correctly assigned to C / Number of objects belonging to C

Question 53

Precision

Answer 53

Number of objects correctly assigned to C / Number of objects assigned to C

Question 54

ROC

Answer 54

Receiver Operating Characteristic True Positive vs. False Positive curve

Question 55

K-means clustering

Answer 55

1. Selects K random points as centroids 2. Assigns points to the closest centroid 3. Define a new centroid, normally the mean 4. Iterate until fixed centroids

Question 56

Bisecting K-means Clustering

Answer 56

1. Split in areas 2. Split area with the highest SSE 3. Repeat until having K clusters

Question 57

Hierarchical Clustering

Answer 57

Construct a hierarchical tree.

Question 58

DBSCAN

Answer 58

Density based clustering