DSCI553 Foundations and Applications of Data Mining
4.1 Task1: Jaccard based LSH (2 points)
In this task, you will implement the Locality Sensitive Hashing algorithm with Jaccard similarity using
In this task, we focus on the “0 or 1” ratings rather than the actual ratings/stars from the users.
Specifically, if a user has rated a business, the user’s contribution in the characteristic matrix is 1. If the
user hasn’t rated the business, the contribution is 0. You need to identify similar businesses whose
similarity >= 0.5.
You can define any collection of hash functions that you think would result in a consistent permutation
of the row entries of the characteristic matrix. Some potential hash functions are:
f(x)= (ax + b) % m or f(x) = ((ax + b) % p) % m
where p is any prime number and m is the number of bins. Please carefully design your hash functions.
After you have defined all the hashing functions, you will build the signature matrix. Then you will divide
the matrix into b bands with r rows each, where b x r = n (n is the number of hash functions). You should
carefully select a good combination of b and r in your implementation (b>1 and r>1). Remember that
two items are a candidate pair if their signatures are identical in at least one band.
Your final results will be the candidate pairs whose original Jaccard similarity is >= 0.5. You need to write
the final results into a CSV file according to the output format below.
Example of Jaccard Similarity:
Input format: (we will use the following command to execute your code)
./spark-submit task1.py <input_file_name> <output_file_name>
Param: input_file_name: the name of the input file (yelp_train.csv), including the file path.
Param: output_file_name: the name of the output CSV file, including the file path.
IMPORTANT: Please strictly follow the output format since your code will be graded automatically. We
will not regrade because of formatting issues.
a. The output file is a CSV file, containing all business pairs you have found. The header is
“business_id_1, business_id_2, similarity”. Each pair itself must be in the alphabetical order. The entire
file also needs to be in the alphabetical order. There is no requirement for the number of decimals for
the similarity value. Please refer to the format in Figure 2.
Figure 2: a CSV output example for task1
We will compare your output file against the ground truth file using precision and recall metrics.
Precision = true positives / (true positives + false positives)
Recall = true positives / (true positives + false negatives)
The ground truth file has been provided in the Google drive, named as “pure_jaccard_similarity.csv”.
You can use this file to compare your results to the ground truth as well.
The ground truth dataset only contains the business pairs (from the yelp_train.csv) whose Jaccard
similarity >=0.5. The business pair itself is sorted in the alphabetical order, so each pair only appears
once in the file (i.e., if pair (a, b) is in the dataset, (b, a) will not be there).
In order to get full credit for this task you should have precision >= 0.99 and recall >= 0.97. If not, then
you will get only partial credit based on the formula:
(Precision / 0.99) * 0.4 + (Recall / 0.97) * 0.4
Your runtime should be less than 100 seconds. If your runtime is more than or equal to 100 seconds,
you will not receive any point for this task.
4.2 Task2: Recommendation System (5 points)
In task 2, you are going to build different types of recommendation systems using the yelp_train.csv to
predict the ratings/stars for given user ids and business ids. You can make any improvement to your
recommendation system in terms of the speed and accuracy. You can use the validation dataset
(yelp_val.csv) to evaluate the accuracy of your recommendation systems, but please don’t include it as
your training data.
There are two options to evaluate your recommendation systems. You can compare your results to the
corresponding ground truth and compute the absolute differences. You can divide the absolute
differences into 5 levels and count the number for each level as following:
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: firstname.lastname@example.org 微信号:vipnxx