Pagerank, Frequent Itemsets, And Clustering Assignment

Assignment Task

Purpose

The purpose of this assessment is to evaluate your learning and knowledge of using and developing algorithms for websearch, finding frequent itemsets, and clustering.

Task

You will complete 3 exercises as detailed below. The maximum total number of points is 120, split into the three exercises. Your task is to complete the following.

PageRank

1. Implement the PageRank Algorithm as discussed in Section 5.1 and 5.2 (Leskovec, Rajaraman & Ullman, 2014) in Python (see Overview module for download instructions). Your implementation should make use of the improvements regarding efficiency and the methods of dealing with dead-ends and spider traps. There are several PageRank implementations available on the web. You have to do your own implementation without using any code from other sources.

2. Run your algorithm on the Google Web Graph 2002 available at and provide a file listing the PageRank for each node. Report separately, the ordered list of the ten nodes having the largest PageRank.

Frequent Itemsets

For this exercise, you have to read Section 6.4 up to 6.4.3 in Mining of Massive Datasets (3rd edition).

1. Implement the simple, randomized algorithm given in Section 6.4.1

2. Implement the algorithm of Savasere, Omiecinski, and Navathe (SON algorithm) in 6.4.3

3. Compare the two algorithms on the datasets T10I4D100K, T40I10D100K, chess, connect, mushroom, pumsb, pumsb_star provided at and report the outcomes.

4. Experiment with different sample sizes in the simple randomized algorithm such as 1, 2, 5, 10% and compare your results (including the result produced by the SON algorithm).

Your approach should be as efficient as possible in terms of runtime and memory requirements. Report on any challenges that you might have observed in the implementation and by running the experiments.

Clustering 

1. Perform a hierarchical clustering on the one-dimensional set of points $1, 4, 11, 16, 25, 36, 49, 64, 81$, assuming the clusters are represented by their centroid (average), and at each step the clusters with the closest centroids are merged.

2. How would the clustering of change if we use for the distance between the two clusters the minimum of the distances between any two points (one from each cluster).

This Engineering has been solved by our PhD Experts at My Uni Paper.