DSCI 553: Assignment 2 solved

Description

1. Assignment Overview
The goal in this assignment is to let you be familiar with A-Prior, MinHash, Locality
Sensitive Hashing (LSH), and different types of recommendation systems. You will
keep using MovieLens dataset that has been used in Lab sessions.
2. Requirements
2.1 Programming Environment
Python 3.6. You could use spark, numpy, scipy, pandas, sklearn, pytorch, tensorflow
library.
If you need to use additional libraries, you must have approval from TA and declare it
in requirements.txt
There will be a 20% penalty if we cannot run your code due to Python version
inconsistency or undeclared 3rd party library.
2.2 Write your own code
Do not share code with other students!
For this assignment to be an effective learning experience, you must write your own
code! We emphasize this point because you will be able to find Python implementations
of some of the required functions on the web. Please do not look for or at any such code!
TAs 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 detected plagiarism.
2.3 What you need to turn in
The submission format will be the the same as homework 1. Your submission must be
a zip file with name: firstname_lastname_hw2.zip (all lowercase). You need to pack the
following files in the zip:
a. four Python scripts, named: (all lowercase)
firstname_lastname_task1.py, firstname_lastname_task2.py, firstname_lastname_task3.py,
firstname_lastname_task4.py
You could have additional files, but these four Python scripts are required.
b. You don’t need to include your results. We will grade on your code with our testing
data (data will be in the same format).
3. MovieLens Dataset
Dataset homepage: https://grouplens.org/datasets/movielens/
You could use the small dataset for development. A copy of the dataset is included,
along with split training and testing data.
4. Tasks
4.1 Task 1: Find interesting association rules
Users’ ratings to movies are stored in ratings.csv. Recall market-based model. The
set of movies that a user gives 5.0 rating could be viewed as a basket.
Task: Find association rules {𝑖1
, 𝑖2
, ⋯ , 𝑖𝑘} → 𝑗 in these baskets, such that interest ≥ 𝐼,
and support ≥ S. 𝑖 and 𝑗 are movieId.
Note:
1. Only consider 5.0 rating in this task.
2. You should use an efficient algorithm like A-Prior method.
3. Although interest could be positive or negative, only consider positive interest here
4. To simplify the computation, the threshold of support is applied to 𝐼 ∪ 𝑗. In the
textbook, the support is applied to 𝐼 only.
Grading:
1. 20 points in total
2. This is a deterministic algorithm. Your answer should be exactly the same as the
solution.
3. We will test your implementation on multiple datasets (same format). If you get
them all correct, you get full points.
4. If your answer doesn’t match the solution, 5 points deducted. The remaining
points will be given based on an analysis of your implementation.
5. The reference implementation takes less than 10 seconds on the ratings.csv,
with I=0.5, S =10. If your implementation takes more than 5 minutes, likely it’s not
implemented correctly and will deduct points.
Input format: (We will use the following command to execute your code)
python firstname_lastname_task1.py
Params:
input_filename: Path to input file, e.g.: ml-latest-small/ratings.csv
output_filename: Path to output file
I: Threshold of the of interest, e.g: 0.5. Use the definition in week 2, slide 19. Only
consider positive interest here.
S: Threshold of support, e.g.: 10. Use the definition in week 2, slide 14. Support is an
integer, not a percentage. The threshold is applied to 𝐼 ∪ 𝑗.
Output format:
A JSON file serialized from a nested list of association rules. Indent doesn’t matter.
You need to output every association rule {𝑖1
, 𝑖2
, ⋯ , 𝑖𝑘} → 𝑗, along with interest and
support for that rule. Below is an illustration of the format.
[
[[𝑖1, 𝑖2, 𝑖3], 𝑗1, interest1, 𝑠𝑢𝑝𝑝𝑜𝑟𝑡1],
[[𝑖1, 𝑖2, 𝑖4], 𝑗2, interest2, support2],
⋯
]
The reference output on ratings_test_truth.csv with I=0.2, S=2 is attached as
task1_sample.json
Sorting Order:
1. In each association rule, the list of 𝑖 are sorted in ascending order
2. Between association rules, rules are first sorted by interest, descending order
3. Then sorted by support, descending order
4. Then sorted by the list of 𝑖, ascending order. Python has sorting order defined
on two lists.
5. Then sorted by 𝑗, ascending order
Please do the sorting correctly. Otherwise your answer will not match the solution and
lose points. Step 2-5 could be done by sorted function with argument:
key=lambda x: (-x[2], -x[3], x[0], x[1])
You don’t need to worry about rounding errors. There is a tolerance in grading script.
Optional: Convert movieId to title. Are there any findings from the association
rules?
4.2 Task 2: Content-based recommendation system with LSH
In the Lab session, we have built a family of memory based recommendation system:
content-based, user-based, and item-based. But they are not scalable to massive
datasets. For every recommendation made, the entire dataset has to be visited once. This
could be optimized by using LSH algorithm to find similar items, instead of linear
search.
Task: Build an efficient content-based recommendation system, that using LSH to
find similar items.
Note:
1. Items (movies) are represented by a set of genres. Their similarity could be
measured by Jaccard similarity.
2. You should implement LSH and content-based recommendation yourself. Using
spark.mllib or similar library is not allowed.
3. There are many hyper-parameters like hash size, bucket size, similarity threshold,
prime number. You need to decide these hyper-parameters, as long as your MSE is
below a threshold, you get full points.
4. Don’t forget to clip the rating to [0.5, 5.0]
5. The submitted program shouldn’t read ground truth values. To calculate MSE, do
it in another program.
Grading:
1. 20 points in total
2. 0 point if your LSH or recommendation system is provided by a library
3. This algorithm has randomness in nature. We will run your program multiple times
and take the average. As long as your 𝑀𝑆𝐸 ≤ 0.85 , you get full points.
4. If your MSE is higher than the threshold, 5 points deducted. The remaining points
will be given based on an analysis of your implementation.
5. We will test your implementation on multiple datasets(same format). These datasets
come from the same distribution and should yield similar MSE. If your model gets
consistent MSE among different datasets, we will use the MSE on provided dataset
for grading. Otherwise, we will analyze your implementation to see if it’s
memorizing test data and deduct points if found.
6. The reference implementation takes about 10 seconds. If your implementation takes
more than 5 minutes, likely it’s not implemented correctly and will deduct points.
7. The running time of LSH based method is similar to linear search method on the
provided dataset. That’s because in this dataset, on average, each user only rated a
small number of movies. The rating matrix is very sparse. The LSH based method
could show its advantage when the rating matrix is denser.
Input format:
python firstname_lastname_task2.py

movies_filename: Path to movies file, e.g.: ml-latest-small/movies.csv
rating_train_filename: Path to train rating file, e.g.: ml-latestsmall/ratings_train.csv
rating_test_filename: Path to test rating file, e.g.: ml-latest-small/
ratings_test.csv
output_filename: Path to output file
In ratings_test.csv, column rating is filled with 0. If you want to evaluate your
model’s performance, you need to compare your prediction with
rating_test_truth.csv
Output format:
Similar to rating_test.csv, it’s column rating is replaced with your model’s
prediction.
4.3 Task 3: Model based recommendation system
In contrast to memory based method, model based method doesn’t need to store or
look up the massive training dataset during inference, which makes it scalable and
widely used in the industry.
Task: Build a model-based recommendation system based on matrix factorization.
Note:
1. You are free to use any matrix factorization algorithm, and any library
implementing them (e.g.: numpy, sklearn), or you could implement it yourself
a. Singular value decomposition
b. Neural network based matrix factorization
2. You should only use these libraries to do matrix factorization. Using a
recommendation system API from 3rd party library is not allowed
3. There are many hyper-parameters like number of components, regularization
coefficient. You need to decide on your own, maybe with grid search. As long
as your MSE is below a threshold, you get full points.
4. In order to reach required MSE, it’s recommended to include overall/user/movie
bias term.
Grading:
1. 20 points in total
2. 0 point if your recommendation system is provided by a library
3. This algorithm has randomness in nature. We will run your program multiple times
and take the average. As long as your 𝑀𝑆𝐸 ≤ 0.785 , you get full points.
4. The reference implementation takes less than 10 seconds. If your implementation
takes more than 5 minutes, likely it’s not implemented correctly and will deduct
points.
5. Same as Task 2, Grading 4
Input and output format: Same as task 2.
4.4 Bonus Task: Further improve the recommendation system
Task: Build a recommendation system that gets the lowest MSE as you can.
Note:
1. You are free to use any method in slides/textbook/online. But that must be your
own implementation, not a functionality of an existing library.
2. Make sure your model performs well on the test set, not training set. We will
evaluate your model in multiple datasets.
3. Possible ideas:
a. The BellKor Solution to the Netflix Grand Prize
b. Hybrid model of Item based and User based RS, may combined with
LSH.
Grading:
1. For every 0.01 MSE reduced over baseline 𝑀𝑆𝐸 = 0.75 , get 1 bonus point. 20
bonus point max.
2. 0 point if your method is provided by a library, or copy-paste from GitHub.
3. Same as Task 2, Grading 3,4,5
Input and output format: Same as task 2.
5. Grading Criteria
The perfect score for this assignment is 60 points + 20 bonus point.
Assignment Submission Policy
Homework assignments are due at 11:59 pm on the due date and should be submitted in
Blackboard. Every student has FIVE free late days for the homework assignments. You can use these
five days for any reason separately or together to avoid the late penalty. There will be no other
extensions for any reason. You cannot use the free late days after the last day of the class. You can
submit homework up to one week late, but you will lose 20% of the possible points for the
assignment. After one week, the assignment cannot be submitted.
(% penalty = % penalty of possible points you get)
1. You can use your free 5-day extension separately or together.
2. If we cannot run your programs with the command we specified, there will be 80% penalty.
3. If your program cannot run with the required Python/Spark versions, there will be 20% penalty.
4. If our grading program cannot find a specified tag, there will be no point for this question.
5. If the outputs of your program are unsorted or partially sorted, there will be 50% penalty.
6. If the header of the output file is missing, there will be 10% penalty.
7. We can regrade on your assignments within seven days once the scores are released. No argue after
one week. There will be 20% penalty if our grading is correct.
8. There will be 20% penalty for late submission within a week and no point after a week.
9. There will be no point if the total execution time exceeds 15 minutes.