Your cart is currently empty!
Overview of the Assignment In Assignment 3, you will complete two tasks. The goal is to let you be familiar with MinHash, Locality Sensitive Hashing (LSH), and different types of collaborative-filtering recommendation systems. The dataset you are going toplaywithis asubset fromthe Yelp dataset(https://www.yelp.com/dataset)used in the previous assignments. Assignment Requirements 2.1 Programming…
In Assignment 3, you will complete two tasks. The goal is to let you be familiar with MinHash, Locality Sensitive Hashing (LSH), and different types of collaborative-filtering recommendation systems. The dataset you are going toplaywithis asubset fromthe Yelp dataset(https://www.yelp.com/dataset)used in the previous assignments.
2.1 Programming Language and Library Requirements
2.2 Programming Environment
We will use Python 3.6, Scala 2.11, and Spark 2.3.3 to test your code. There will be a 20% penalty if we cannot run your code due to the library version inconsistency.
2.3 Write your own code
Do not share your code with other students!!
We will combine all the code we can find from the Web (e.g., GitHub) as well as other students’ code from this and other (previous) sections for plagiarism detection. We will report all the detected plagiarism.
2.4 What you need to turn in
Your submission must be a zip file with the naming convention: firstname_lastname_hw3.zip (all lowercase, e.g., yijun_lin_hw3.zip). You should pack the following required (and optional) files in a folder named firstname_lastname_hw3 (all lowercase, e.g., yijun_lin_hw3) in the zip file (Figure 1, only the files in the red boxes are required to submit):
firstname_lastname_task1.py, firstname_lastname_task2.py
b1. [OPTIONAL] two Scala scripts containing the main function, named:
firstname_lastname_task1.scala, firstname_lastname_task2.scala b2. [OPTIONAL] one Jar package, named:
firstname_lastname_hw3.jar
Figure 1: The folder structure after your submission file is unzipped.
We generated the following two datasets from the original Yelp review dataset with some filters such as the condition: “state” == “CA”. We randomly took 60% of the data as the training dataset, 20% of the data as the validation dataset, and 20% of the data as the testing dataset.
4.1 Task1: Jaccard based LSH (4 points)
In this task, you will implement the Locality Sensitive Hashing algorithm with Jaccard similarity using yelp_train.csv. You can refer to sections 3.3 – 3.5 of the Mining of Massive Datasets book.
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. You can use any combination for the parameters (a, b, p, and m) in your implementation.
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. 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:
user1 | user2 | user3 | user4 | |
business1 | 0 | 1 | 1 | 1 |
business2 | 0 | 1 | 0 | 0 |
Jaccard Similarity (business1, business2) = #intersection / #union = 1/3
Input format: (we will use the following command to execute your code)
Param: input_file_name: the name of the input file (e.g., yelp_train.csv), including the file path. Param:
output_file_name: the name of the output CSV file, including the file path.
Output format:
IMPORTANT: Please strictly follow the output format since your code will be graded automatically. We will not regrade on formatting issues.
Figure 2: a CSV output example for task1
Grading:
We will compare your output file against the ground truth file using the 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 BlackBoard, 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 = 1 and recall >= 0.98. If not, then you will get 80% partial credit with 0.95 <= recall < 0.98:
Your runtime should be less than 120 seconds with 4G driver memory and 4G executor memory. This is the environment of the grading machine. If your runtime is more than or equal to 120 seconds, you will not receive any point for this task.
4.2 Task2: Recommendation System (8.5 points)
In task 2, you are going to build different types of recommendation systems using the yelp_train.csv to predict for 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.
There are two options to evaluate your recommendation systems. You can compare your results to the correspond 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:
>=0 and <1: 12345
>=1 and <2: 123
>=2 and <3: 1234
>=3 and <4: 1234
>=4: 12
This means that there are 12345 predictions with < 1 difference from the ground truth. This way you will be able to know the error distribution of your predictions and to improve the performance of your recommendation systems.
Additionally, you can compute the RMSE (Root Mean Squared Error) by using following formula:
Where Predi is the prediction for business i and Ratei is the true rating for business i. n is the total number of the business you are predicting.
In this task, you are required to implement:
Case 1: Model-based CF recommendation system with Spark MLlib (2.5 point)
Case 2: User-based CF recommendation system (3 points)
Case 3: Item-based CF recommendation system (3 points)
4.2.1. Model-based CF recommendation system
You will use Spark MLlib to implement this task. You can learn more about Spark MLlib by this link:
http://spark.apache.org/docs/latest/mllib-collaborative-filtering.html.
4.2.2. User-basedCF recommendation system
4.2.3. Item-based CF recommendation system
Input format: (we will use the following command to execute your code)
Param: train_file_name: the name of the training file (e.g., yelp_train.csv), including the file path Param:
test_file_name: the name of the testing file (e.g., yelp_val.csv), including the file path Param: case_id: the case
number (i.e., 1, 2, or 3)
Param: output_file_name: the name of the prediction result file, including the file path
Output format:
Figure 2: Output example in CSV for task2
Grading:
We will compare your prediction results against the ground truth. We will grade on all the cases in Task2 based on your accuracy using RMSE. For your reference, the table below shows the RMSE baselines and suggested running time for predicting the validation data.
RMSE baseline and suggested running time for predicting the validation data
Case 1 | Case 2 | Case 3 | |
RMSE | 1.31 | 1.12 | 1.10 |
Running Time | 40s | 150s | 100s |
For grading, we will use the testing data to evaluate your recommendation systems. If you can pass the RMSE baselines in the above table, you should be able to pass the RMSE baselines for the testing data. However, if your recommendation system only passes the RMSE baselines for the validation data, you will receive 50% of the points for each case.
In case 2 and 3, if your RMSE can not pass the baseline, you will receive partial credit:
case2: 100% RMSE <= 1.12, 80% 1.12 < RMSE <= 1.18 else 0%
case3: 100% RMSE <= 1.10, 80% 1.10 < RMSE <= 1.17 else 0%
(% penalty = % penalty of possible points you get)
Example situations
Task | Score for Python | Score for Scala | Total | |
(10% of previous column if correct) | ||||
Task1 | Correct: 4points | Correct: 4 * 10% | 4.4 | |
Task1 | Wrong: 0 point | Correct: 0 * 10% | 0.0 | |
Task1 | Partially correct: 2 points | Correct: 2 * 10% | 2.2 | |
Task1 | Partially correct: 2 points | Wrong: 0 | 2.0 |