Final Exam - Past Questions

Question 1

What are the difference between lazy and eager learners?

Answer 1

Two types: lazy and eager. Eager learners generate the model explicitly (decision tree), lazy do not (kNN).

Question 2

Briefly describe the general objective of Association Rules mining.

Answer 2

The objective of association rules mining is to discover interesting relations between objects in large databases.

Question 3

Explain the benefits of applying the Apriori Principle in the context of the Apriori Algorithm for Association Rules mining.

Answer 3

Apriori is a algorithm used to determine association rules in the database. This is done by identifying frequent individual terms to construct itemsets above a support threshold.

The apriori principle

• If an itemset is frequent, it’s subsets are also frequent.
• If an itemset isn’t frequent, it’s subsets are also not frequent. They can be pruned.

Question 4

Compare the Precision and Recall metrics for classifier evaluation. Illustrate your answer using the Confusion Matrix.

Answer 4

Precision: exactness - what percent of tuples that the classifier labeled as positive are actually positive?

Precision = True Positive / (True Positive + False Positive)

Recall: completeness - what percent of positive tuples did the classifier correctly labelled as positive?

Recall = True Positive / (True Positive + False Negative)

Question 5

What is the main limitation of the Naïve Bayesian Classifier?

Answer 5

Assumes attributes are independent. This is not likely in the real world for some cases. Usually there are dependencies in data.

Question 6

In the context of Decision Tree induction, what does overfitting mean? And how to avoid overfitting?

Answer 6

Overfitting in the context of a decision tree is where your decision tree matches the data too precisely. The decision tree may be capturing noise.

Stop the algorithm before it makes a fully grown tree.

1. Stop if all instances belong to the same class.
2. Stop if all the attribute values are the same.

Other notes Stop if it doesn’t improve the Gini index.

Question 7

Describe the problems involved in selecting the initial points of the K-means clustering method. Describe post-processing techniques to solve such problems.

Answer 7

K-means can return sub-optimal clusters because sometimes the centroids do not readjust in the ‘right’ way.

Post-processing techniques to overcome this problem consist of

1. Eliminating ‘small’ clusters that may represent outliers,
2. Splitting ‘loose’ clusters with relatively high sum of squared error and
3. Merging ‘close’ clusters with relatively low sum of squared error.

Question 8

What is the edit distance of

university —————–> unverstiy?

How do you calculate it?

Answer 8

Edit distance is three start.

university

1. unversity (delete first i)
2. unversty (delete second i)
3. unverstiy (insert final i)

Question 9

What are the confidence rules to test for (a,b,c)?

Answer 9

The following are confidence rules? a -> b a -> c b -> a b -> c a, b -> c c -> a, b a, c -> b b -> a, c b, c -> a a -> b, c

Question 10

How do you calculate support in a dataset?

Answer 10

The count the number of times the word appears and divide by the number of rows

Question 11

How do you calculate the confidence for a rule (a,b) -> c

Answer 11

prob (a, b, c) / prob (a,b)

Question 12

What are the steps for doing a VSM?

Answer 12

1. Extract text 2. Remove stop words 3. Make lower case 4. Stemming 5. Count term frequencies 6. Create index file 7. Create VSM 8. Calculate the IDF log(Number of documents / term frequency 9. Calculate the TF-IDF 10. Normalize the weights 11. Compute the cosine distance with a query

Question 13

What’s the motivation for studying Mining Association Rules?

Answer 13

To look for interesting relationships between objects in large datasets.

Question 14

Provide Formal Notations of the following

item

itemset

k-itemset

transaction

transaction dataset

Answer 14

• An item: an item in a basket
• An itemset is a set of items. n E.g., X = {milk, bread, cereal} is an itemset.
• A k-itemset is an itemset with k items.
• A transaction: items purchased in a basket n it may have TID (transaction ID)
• A transactional dataset: A set of transactions

Question 15

What do we mean when we say X-> Y in Mining Association Rules?

Answer 15

If they buy X, they will buy Y.

Question 16

What is support and confidence in Association Rule Mining?

Answer 16

Support is a measure of how frequent an item appears in the set.

E.g Half of the people at Woolworths have milk in their basket. The support is 0.5 or 50%.

Confidence is a measure of how likely an item is bought if another item is also bought (X->Y). Of the people who buy milk, 80% of people buy bread as well. Confidence is 0.8

Question 17

What do we call association rules that satisfy both the Min_Support and Min_Confidence?

Answer 17

These are Strong Association Rules.

Question 18

What is the minimum support mean?

Answer 18

The minimum frequency we care about.

If minimum support equals 3.

Any item that occurs only 2 times is not important for our analysis.

Question 19

What is the goal of association rule mining? What do we minimally want for a rule?

Answer 19

The goal of association rule mining is to find all rules having

1. support ≥ min_sup threshold
2. confidence ≥ min_conf threshold

Question 20

What algorithms do we you use for Mining Association Rules?

Answer 20

1. Apriori Algorithm
2. Frequent Pattern (FP) Growth Algorithm

Question 21

What are the two steps in Mining Association Rules?

Answer 21

1. Frequent Itemset Generation

– Get all itemsets whose support ≥ minsup

2. • Generate high confidence rules from each frequent itemset

Question 22

What is the principle of the Apriori Algorithm?

Answer 22

If an itemset is frequent, then all of its subsets must also be frequent.

Question 24

What are some factors that affect the complexity of the Apriori Algorithm?

Answer 24

• The choice of minimum support threshold
• Dimensionality (number of items) in the data set
• Size of database
• Average transaction width

Question 25

Explain the challenges when using histograms for detecting outliers?

Answer 25

It’s hard to choose an appropriate bin size for histograms.

Too small: normal objects in empty/rare bins. You get false positives

Too big: outliers in some frequent bins: You get false negatives