exam

Question 1

supervised learning

Answer 1

• how does the output depend on the input?
• can we predict the output, given the input?
• classification, regression

Question 2

unsupervised learning

Answer 2

• no target

- clustering and frequent pattern mining (find dependencies between variables)

Question 3

univariate distribution

Answer 3

what values occur for an attribute and how often, data is a sample of a population

Question 4

entropy H(A)

Answer 4

how informative is an attribute? (about the value of another attribute)
measurement about the amount of information/chaos

Question 5

distribution of a binary attribute

Answer 5

H(A) = – plg(p) – (1–p)lg(1–p)

H(A) maximal (1) when p = 1/2 = 1/m (m nr of possible values)

Question 6

distribution of a nominal attribute

Answer 6

H(A) = Σ–p_{i}*lg(p_{i})
H maximal when p = 1/m
H_max = lg(m)

Question 7

histograms

Answer 7

define cut points and count occurrences within bins

• equal width: cut domain in k equal sized intervals

- equal height: select k cut points such that all bins contain n/k data points

Question 8

information gain

Answer 8

gain(A) = H(p) – ΣH(p_{i})*n_{i}/n

p probability of positive in current set (before split)
n number of examples in current set (before split)
p_{i} probability of positive in branch i (after split)
n_{i} number of examples in branch i (after split)

Question 9

problem highly-branching attributes

Answer 9

attributes with a large number of values are more likely to create pure subsets => information gain is biased towards choosing attributes with many values (may result in overfitting: not optimal for prediction)
=> solution: gain ratio

Question 10

Gain ratio

Answer 10

modification of the information gain that reduces its bias on high-branching attributes => large when data is divided in few, even groups, small when each example belongs to a separate branch

GainRatio(S,A) = Gain(S,A)/IntrinsicInfo(S,A)

Question 11

intrinsic information

Answer 11

the entropy of distribution of instances into branches: the more branches, the higher this entropy

Question 12

entropy over numeric attributes

Answer 12

many possible split points:
evaluate information gain for every possible split point, choose best one and its info gain is the information gain for the attribute (breakpoints between values of the same class cannot be optimal)

Question 13

pruning

Answer 13

prevent overfitting to noise in the data

prepruning, postpruning

Question 14

prepruning

Answer 14

stop growing the tree when there is no statistically significant dependence between an attribute and the class at a particular node
- chi-squared test

problem: prepruning might stop the process to soon (early stopping), eg. XOR problem (no individual attribute exhibits any sign. association to the class, only visible in expanded tree)

Question 15

postpruning

Answer 15

first, build full tree

then, prune: subtree replacement (bottom up, consider replacing a tree only after considering all its subtrees)

Question 16

estimating error rates

Answer 16

avoid overfitting: don’t model details that will produce errors on future data => estimate such errors

• prune only if it reduces the estimated error
• compute confidence interval around observed error rate (take high end as worst case)
• C4.5: error estimate for subtree is weighted sum of error estimates for all its leaves

Question 17

covering algorithms

Answer 17

for each class in turn, identify a rule set that covers all examples in it

• a single rule describes a convex concept: describes only examples of the same class
• generate a rule by adding tests that maximize the rule’s accuracy
• each additional test reduces the rule’s coverage

Question 18

selecting a test (covering algorithms)

Answer 18

goal: maximize accuracy
- t total number of examples covered by the rule
- p positive examples of the class covered by the rule
- select test that maximizes p/t (finished when p/t = 1)

Question 19

PRISM algorithm

Answer 19

(separate-and-conquer: all examples covered by a rule are separated out, remaining examples are conquered)

for each class, make rules by adding tests (maximizing p/t) until the rule is perfect and until each example of the class has been covered by a rule

Question 20

instance-based / rote / lazy learning

Answer 20

training set is searched for example that most closely resembles the new example, examples themselves represent the knowledge
- (k-)NN

Question 21

distance function

Answer 21

• simplest case: 1 numeric attribute (difference between the two values)
• several numeric attributes: Euclydian distance + normalization (square root of the sum of squares of the distance between the two values, for every attribute)

Question 22

1-NN discussion

Answer 22

• can be accurate, but is slow
• assumes all attributes are equally important (solution: attribute selection or add weights)
• take majority vote over k nearest neighbours (solution for noisy examples)

Question 23

proper test and training procedure uses 3 sets

Answer 23

training set: train models
validation set: optimize algorithm parameters
test set: evaluate final model

Question 24

trade-off: performance vs evaluation accuracy

Answer 24

more training data => better model

more test data => more accurate error estimate

Question 25

ROC analysis

Answer 25

Receiver Operating Characteristic | compute TPR = TP/(TP+FN) and FPR = FP/(FP+TN)

Question 26

data science

Answer 26

extract insights from large data less emphasis on algorithms, more on outreach (application)

Question 27

big data

Answer 27

- very large data (Google, Facebook, Twitter) - it's possible: cheap storage - analytics - internet-gathered data - social data - heterogeneous, unstructured data

Question 28

exploratory data analysis

Answer 28

- scan data without much prior focus - find unusual parts in the data - analyse attribute dependencies: if X=x and Y=y (subgroup) then Z is unusual - understanding the effects of all attributes on the target

Question 29

classification

Answer 29

model the dependency of the target attribute on the remaining attributes

Question 30

subgroup discovery

Answer 30

find all subgroups within the inductive constraints (minimum/maximum coverage, minimum quality, maximum complexity) that show a significant deviation in the distribution of the target attribute - a quality measure for subgroups summarizes the interestingness of its confusion matrix into a single number, eg. WRAcc, weighted relative accuracy: WRAcc(S,T) = P(ST) - P(S) * P(T) (compare to independence: 0 means uninteresting) (typically produces many patterns with high levels of reduncancy)

Question 31

numeric subgroup discovery

Answer 31

numeric target: find subgroups with significantly higher or lower average value - trade-off between size of subgroup and average target value

Question 32

we cannot just apply a learner

Answer 32

- algorithms are biased - considering all possible data distributions, no algorithm works better than another - algorithms make assumptions about data (eg. all features are equally relevant (kNN, k-means), all features are discrete (ID3), numeric (k-means)) so adapt data to the algorithm (data engineering) or adapt the algorithm to data (selection/parameter tuning)

Question 33

data engineering

Answer 33

- attribute selection: remove features with little predictve information - attribute discretization: convert numeric attributes to nominal ones - data transformations: transform data to another representation

Question 34

attribute selection

Answer 34

- filter approach: learner independent, based on data properties or simple models built by other learners - wrapper approach: learner dependent, rerun learner with different attributes, select attributes based on performance (will also consider attributes that are only interesting combined with other attributes, unlike the filter approach, but greedy: O(k^2) for k attributes)

Question 35

attribute discretization

Answer 35

- descretize values in small intervals - always loses information: try to preserve as much as possible 1. transform into 1 k-valued nominal attribute 2. replace with k-1 new binary attributes (preserve order of classes)

Question 36

unsupervised discretization

Answer 36

determine intervals without knowing class labels 1. equal-interval binning (equal-width) 2. equal-frequency binning: bins of equal size 2b. proportional k-interval discretization: equal-frequency binning with # bins = sqrt(dataset size)

Question 37

supervised discretization

Answer 37

class labels are known - best if all examples in a bin have the same class eg. entropy discretization: split data in same way C4.5 would (each leaf = bin), use entropy as splitting criterion

Question 38

data transformations

Answer 38

can lead to new insights in the data and better performance (eg. subtract two "date" attributes to get new "age" attribute)

Question 39

how good is a regression model?

Answer 39

(for linear data) coefficient of determination: ``` R^2 = 1 - SSres/SStot (between 0 and 1) SSres = Σ(yi−fi)^2 (difference between actual and predicted value) SStot = Σ(yi−y_bar)^2 (scaling term: difference between actual value and horizontal line at average level of all y values) ``` compare a model where x is used to a model where x does not play a role explained variance: what percentage of the variance is explained by the model

Question 40

regression trees

Answer 40

- regression variant of decision tree 1. regression tree: constant value in leaf 2. model tree: local linear model in leaf

Question 41

M5 model (regression trees)

Answer 41

we cannot use entropy (no classification): use standard deviation - splitting criterion: standard deviation reduction (sdr: compare sd before and after splitting) SDR = sd(T) – Σ(sd(Ti) * |Ti| / |T|) - stopping criterion: sd below some threshold or too few examples in node - pruning (bottom up): estimate amount of error by splitting all splits are binary - numeric: as usual - nominal: order all values according to average and introduce k-1 indicator variables in this order

Question 42

dissimilar patterns

Answer 42

make sure every additional pattern adds extra value - consider extent of patterns (what do they represent) - add binary column for every subgroup - joint entropy of itemset captures informativeness of a set of items (= set of subgroups)

Question 43

maximally informative k-itemset (miki)

Answer 43

itemset of size k (k subgroups in it) that maximizes the joint entropy (maximal when all parts are of equal size) properties: - p(Xi) = 0.5 has highest entropy - items in miki are independent - every individual item adds at most 1 bit of information - monotonicity: adding an item will always increase the joint entropy - every item adds at most H(Xi), so a candidate itemset can be discarded if the bound is not above the current maximum)

Question 44

partitions of itemsets

Answer 44

- group items that share information into blocks - obtain a tighter bound - precompute the joint entropy of small (2 or 3) itemsets

Question 45

joint entropy

Answer 45

- Sigma(p_i*lg(p_i))

Question 46

itemset

Answer 46

a collection of one or more items, eg. {break, milk, eggs}

Question 47

Support count (σ)

Answer 47

frequency of occurrence of an itemset, eg. σ({Bread, Milk, Diapers}) = 2

Question 48

association rule mining

Answer 48

given a set of transactions, find rules that predict the occurrence of an item based on occurrences of other items in the transaction, X --> Y with X and Y itemsets support (s) = fraction of transactions that contain both X and Y confidence (c) = how often items in Y appear in transactions that contain X (how many times does the right hand side occur together with the left hand side) c(ABC → D) ≥ c(AB → CD) ≥ c(A → BCD)

Question 49

frequent itemset

Answer 49

itemset whose support >= minsup

Question 50

maximal frequent itemset

Answer 50

if none of its immediate supersets are frequent

Question 51

closed itemset

Answer 51

if none of its (immediate) supersets have the same support

Question 52

ensemble

Answer 52

a collection of models that works by aggregating the individual predictions - classification and regression (supervised learning) - typically more accurate than base model - diversity between models improves performance (different models, randomness) - more randomized models work better

Question 53

bootstrap aggregating (bagging)

Answer 53

build different models by bootstrapping: - given a training set D of size n, bagging generates m new training sets, each of size n - sampling with replacement: for large n, each set has 36,8% duplicates --> creates randomness, each time a slightly different model - performance improves with more learners (large m) - de-correlate learners by learning from diffferent datasets

Question 54

random subspace method

Answer 54

each tree is built from a random subset of the attributes --> individual trees do not over-focus on attributes that appear highly informative in the training set works better in high-dimensional problems

Question 55

random forest

Answer 55

combine bagging and random attribute samples: at each node, take a sample of the attributes and pick the best one

Question 56

Out-Of-Bag error (OOB)

Answer 56

mean prediction error on each training sample Xi, using only those trees that did not have Xi in their bootstrap sample

Question 57

measure an attribute's importance

Answer 57

- make a random forest - record average OOB error over all the trees => e_0 - for each independent attribute j: swap randomize j, refit the random forest, record average OOB e_j => importance of j = e_j - e_0

Question 58

benefits of random forests

Answer 58

- good theoretical basis (ensembles) - easy to run: works well without tuning - easy to run in parallel: inherent parallelism

Question 59

clustering: overlapping vs non-overlapping

Answer 59

a point can be a member of more than one cluster vs every point is in one cluster only

Question 60

clustering: top down vs bottom up

Answer 60

take entire dataset and cut somewhere vs first assume every individual point is a different cluster

Question 61

clustering: deterministic vs probablistic

Answer 61

100% sure about in which cluster you are vs probability of being in a cluster is between 0 and 1

Question 62

k-means algorithm

Answer 62

1. pick k random points: initial cluster centres 2. assign each point to nearest cluster centre 3. move cluster centres to mean of each cluster 4. reassign points to nearest cluster centre repeat steps 3-4 until cluster centres converge

Question 63

k-means: discussion

Answer 63

+ simple, understandable + fast + instances automatically assigned to clusters - results can vary depending on initial choice of centres - can get trapped in local minimum (restart with different random seed) - must pick number of clusters beforehand - all instances forced into a single cluster - sensitive to outliers - random algorithm, random results

Question 64

centroid: distance between clusters

Answer 64

single link: smallest distance between points complete link: largest distance between points average link: average distance between points

Question 65

hierarchical clustering advantages

Answer 65

- you don't have to choose the amount of clusters beforehand (k-menas), you can choose it afterwards and see what amount of detail you want (draw a line in the dendrogram) - can be applied to nominal data more easily than k-means

Question 66

complexity of association rules

Answer 66

given d unique items - total nr possible itemsets: 2^d - total nr possible association rules: 3^d - 2^(d+1) + 1 in case of a frequent k-itemset, the total nr of possible association rules = 2^k - 2