Terms

Question 1

Girvan-Newmann

Answer 1

Calculate betweenness in a network (using the leaf / parent scoring system)

Question 2

Betweenness

Answer 2

How often is an edge used as a path between nodes?

Question 3

Support (itemsets)

Answer 3

Number of baskets for which an itemset is a subset

Question 4

Confidence (if I then j)

Answer 4

Support for I divided by the support for I and j together,. (If diapers then beer). If its 1 then its always the case

Question 5

Interest (If I then j)

Answer 5

How interesting is a fact? If diapers then beer is not interesting if beer is in every basket. Confidence in I to j minus fraction of baskets that contain j

Question 6

Support threshold

Answer 6

Find all frequent itemsets that appear in at least s baskets

Question 7

What is a triangular matrix used for?

Answer 7

Efficient way to store count of pairs; (pair 2,1 count is the same as pair 1,2 count).

Question 8

What does the A-priori algorithm do?

Answer 8

Find frequent K-itemsets that appear in at least s baskets. You count all pairs and then filter out the infrequent ones. You then construct new pairs (K + 1) and count again. Filter and repeat until your K is reached.

Question 9

What does the PCY algorithm do?

Answer 9

Like A-priori but we reduce the amount pairs that need to be counted by hashing pairs on K=1 and counting. When constructing a candidate pair, only make it a candidate if the pair hashes to a ‘frequent bucket’.

Question 10

What does the multistage algorithm do?

Answer 10

Like PCY, but a second hash round. First hash table contains a lot of false negatives (multiple pairs hash to same bucket and can have a count > s together). We generate each pair again, and iff it is in a frequent bucket in hash 1 then we hash it to hash 2. Then we count again

Question 11

What does the multihash do?

Answer 11

Like multistage, but doesnt require the extra pass through the baskets. Has multiple hashes, and hashes pairs to all hashes. When counting, increment it in all hash tables. Then only construct candidate pair if it is in a frequent bucket in ALL hashes. (avoid false negatives)

Question 12

Random Sampling (itemsets)

Answer 12

If too much data; we can pick a sample and run A-priori / PCY on it. We then validate the result against the entire dataset.

Question 13

SON algorithm (itemsets)

Answer 13

We can divide the data up into parts. Then for each part, run A-priori / PCY. Then join the results and validate (count).

Question 14

What is the monotonicity property?

Answer 14

An itemset cannot be frequent in the entire set if it is not frequent in at least one subset.

Question 15

How does hierarchical clustering work?

Answer 15

Iteratively join the clusters with closest centroid. Stop when you are at K clusters.

Question 16

How does K-means clustering work?

Answer 16

Pick a K. Then choose K points random, they are the clusters. For all points, place each point in the cluster thats closest. Then update the centroids of all clusters. Now for all points, reassign to closest cluster. Repeat this untill no more points move.

Question 17

How do you pick the right K for clustering?

Answer 17

Power law; for all K we can map the avg distance to a centroid. There is a point where if we increase K, the avg distance doesn’t get much lower. That is the sweet spot.

Question 18

What is the Mahalanobis distance?

Answer 18

We assume a normal distribution of distance to centroid of a cluster. The mahalanobis distance is the amount of standard deviations that a point has from a centroid.

Question 19

What statistics are recorded in the BFR algorithm?

Answer 19

Number of points, sum of all points and sumsquared of all points.

Question 20

What does the Discard Set in BFR hold?

Answer 20

The Discard Set holds all points that are close enough to an existing cluster.

Question 21

What does the Compression Set in BFR hold?

Answer 21

All generated clusters that could not go into DS. If possible these clusters are merged.

Question 22

What does the Retained Set (RS) in BFR hold?

Answer 22

All points that could not be assigned to a mini cluster for the CS in the previous round. They are joined with the retained set from this round to try and form mini-clusters. that go into CS

Question 23

What is the limitation of BFR?

Answer 23

Since it assumes a gaussian distribution, only cigar or round distributions are recognized. Odd shapes in clusters are not recognized.

Question 24

How does the CURE algorithm work?

Answer 24

Pick a large sample from data. Cluster using hierarchical clustering. For each cluster, pick n representative points. Shrink each point 20% towards its centroid. Now compare each point to all representative points. Assign it to the cluster that belongs to the repr point it’s closest to.