# Computational Data Analytics - Final Exam Summer Term 2020

###### tags: `Exam`

## Question 1 Clustering


---


---


---


---

Chi-merge uses a Bottom-Up Strategy to join two neighboring intervals. You can consider this to be clustering on a one-dimensional dataset.

## Question 2 Association Rules

You play Rock/Paper/Scissors against your neighbor, and want to improve your performance in this game by trying to guess your opponent’s moves. In the last 15 games, your neighbor has played the following moves (Scissors = S, Rock = R, Paper = P).

From that you want to generate rules which can predict your neighbor’s next move from her last moves. Therefore you decide to modify an association rule learner in such a way that it does not operate on sets but on sequences.


#### 2–a Compute support and confidence for the rule
S → P
(Immediately after Scissors your opponent plays Paper.)

$\operatorname{supp}(S \rightarrow P)=\operatorname{supp}(P \rightarrow S)=\frac{n(S \cup P)}{n}$


#### 2–b Compute the lift for the rule in a). How do you interpret the obtained value?


$$\operatorname{lift}(S \rightarrow P)=\frac{\frac{n(S \cup P)}{n(S)}}{\frac{n(P)}{n}}=\frac{\text { confidence }(S \rightarrow P)}{\text { confidence }(\rightarrow P)}=\frac{\operatorname{support}(S \rightarrow P)}{\operatorname{support}(S) \operatorname{support}(P)}$$



#### 2–c How can you efficiently (i.e., by generating as few unnecessary candidates as possible) obtain a set of candidate sequences of length l + 1 from a set of frequent sequences of length l?

Association Rule Mining p.16 (Apriori Phase 3(b))

#### 2–d Use an algorithm inspired by Apriori to find all move sequences of arbitrary length > 0, which your opponent has played at least 3 times. Show the candidate sequences and the frequent sequences for each length.


#### 2–e Construct all frequent rules that apply to at least 3 cases, for which the move sequence in the head follows immediately after the move sequence in the body with a confidence of at least 3/4. Note: You can here, of course, build upon the results from d).


## Question 3 KD-Trees
![](https://i.imgur.com/Qni7rmP.png)

#### 3–a In which order must the examples have been observed so that the shown partitioning is the result?

1. $E_5$
2. $E_2$
3. $E_1$
4. $E_3$
5. $E_4$

#### 3–b Sketch the resulting KD-Tree. Is this tree good or bad for increasing the efficiency of a k-NN algorithm. Why (not)?

![](https://i.imgur.com/qN3XhUt.png)



#### 3–c Sketch the computation of the nearest neighbor for the example Q = (3, 4) using the KD-tree shown below.
![](https://i.imgur.com/7FCi0L3.png)

![](https://i.imgur.com/S8nSJqM.png)

#### 3–d KD-trees can also be used for k-nearest neighbor algorithms with k > 1. How would you proceed?
![](https://i.imgur.com/5FKDNoG.png)

For more p46-51 in Distance-based Methods. 

#### 3–e Can you apply Locality Sensitive Hashing using Min-Hashing to the above data? If so, how? If not, why not?

Not 100% sure but. 

From chat some thoughts:

* "I suppose with discretization it might work but if its the optimal choice is a different question."
* "I mean we learned that Min Hashing can be applied to Boolean Matrices. I wouldnt know how to apply it to this data table and also how it would make sense. One could one hot encode the instances, if there are just certain values like integers in a finite range or we could discretize, you are right. Then it could work."

* "I had the same thought as.... for Locality Sensitive Hashing you need Min Hashing. Tbh I have no idea how to apply it on the given data. However, I think with Supervised Discretization it might work easily. Since it is an open question, you can write a lot anyway."

* "i think even if one could make locality sensitive hashing work (not sure how to efficiently) it would be a overkill, as it is made for large sparse matrices"



## Question 4 Miscellaneous 

#### 4–a You have a multi-class problem with 10 classes. You want to solve it by learning a set of binary theories with a) one-against-all and b) pairwise classification. Give for both a) and b)

1. How many binary classifiers have to be trained?
2. How many training examples does each of them receive, if the original training set contains 100 examples for each class?
3. How many examples are therefore used in total for training? (examples that are used multiple times are counted multiple times)

![](https://i.imgur.com/49llrfI.png)

1) #Classifiers
`c = 10`
OAA: `c` - one for every class (against all others) = **10**
PC: `c(c-1)/2` - all possible combinations = 10*9/2 = **45**

2) #Examples per classifer
`c = 10`
`e = 100`
OAA: `1*e + (c-1)*e` - current class all 100, opposite classifier 900 = **1.000**
PC: `1*e + 1*e` - current class all 100, comparing class 100 = **200**


3) #Examples in total
`c = 10`
`e = 100`
OAA: `c*(1e + (c-1)*e)` - 1.000 for each of the 10 classifiers = 10*1.000 = **10.000**
PC: `c(c-1)/2 * (2*e)` - 200 for every of the 45 classifiers = 200\*45 = **9.000**

#### 4–b You have a dataset with class information and several algorithms. How can you design a setup in order to determine the algorithm with the highest degree of overfitting?

Hint: The algorithm with the highest degree of overfitting is not necessarily the least accurate algorithm because the quality of the learning of different algorithms may be different.


"Determine Generalization performance on a test set or with cross validation and compare accuracy to train set performance. The larger the difference the more overfitting."

#### 4–c The Laplace-corrected Precision $h_{Lap}$ is a commonly used heuristic in inductive rule learning. Somebody proposes to use the heuristic $h^2_{Lap}$ instead, which squares the Laplace evaluation value of each rule. What can you say about its isometrics in coverage space? Can you expect this heuristic to perform better or worse when used in a separate-and-conquer rule learner?

"The shape of the isometric lines stays the same, however their values change. Especially for increasing n it will go to 0 faster. I am not 100% sure about the performance, I would say it performs better since we want to punish large n and small p which it does more than the not squared version of Laplace heuristic"

#### 4–d You have a set of documents D = {di}, where each document is assigned to an arbitrary number of keywords from a fixed set of keywords. There is no order between the keywords in a set. You now have the task to train a learner that suggest the five most likely keywords (ordered by relevance) to a new unseen document. How would you proceed?

Note: You can assume that the documents are represented as binary feature vectors $d_i$, which can be directly used by a learner.


#### 4–e Your dataset S contains a million features and you want to speed up your learner. You therefore decide to use a very quick filter approach to feature subset selection, which computes a weight for each feature, and use only the 100 features which discriminate best between the classes, resulting in a dataset S' which has the same examples, but each example represented with only 100 features. You then remember that there is a danger that some features are only useful in combination with others and might have been discarded with this simple approach. So you evaluate your rule learning algorithm with cross-validation on S and compare it to an evaluation with cross-validation on S' (using the same folds). The results show that its estimated performance on S' is even significantly better than the estimated performance on S. Can you conclude that the reduced feature subset is indeed better for the used rule learning algorithm? Justify your answer.

(my theory)
I would say that in the original feature set, there were probably many *noise* or *duplicate*/*correlated* attributes which "seemed" important by **chance** during training. Removing them has simplified our model and improved generalization. Thus the reduced set is better.

![](https://i.imgur.com/CqWlGYh.png)


#### 4–f A video streaming platform publishes user-generated content. Users can associate their uploads with arbitrarily chosen keywords. Users can not bulk-download all content or all keywords associated with the content, but they can register for some keywords, so that they get a notification whenever somebody uploads new content associated with that keyword. As a user, you are interested in monitoring over a longer period of time how evenly distributed all keywords are. How can you use one of the algorithms in the lecture for this task?

Approximate Query Answering(?) Computational Data Analytics – Data Stream Mining p29