Write a Python application program (main file called Recommend.py) that implements e-commerce recommendation based on item-to-item collaborative filtering.

Input and Output. The input to your program involves two text files history.txt which contains the purchase history of all the customers and queries.txt which includes all the queries (shopping cart items based on which you need to provide recommendation).

The file history.txt is a text file describing the complete purchase history of all the customers. The first line includes three numbers: Number of Customers Number of Items Number of Transactions This is followed by Number of Transactions lines of text, each line containing two numbers: Customer ID Item ID This means the customer Customer ID bought the item Item ID. Both Customer ID and Item ID are integers starting from 1. Note that the same customer may have bought the same item multiple times.

The file queries.txt is a text file with each line containing a query, describing a list of items in the current shopping cart. Each query is composed of one or more numbers, separated by whitespace, corresponding to the item IDs in the current shopping cart. All the input files described above are assumed to be in the current folder. Your program should read from these files in the current folder without any user interaction. Do not ask users to enter paths or filenames.

For output, print the required messages (see details below and sample outputs overleaf) following exactly the same format (except for the actual number of whitespace) as specified and as in the examples. When printing real numbers, you should print them with at least two fractional digits.

Reading the transaction history. Your program should read in all the transactions from history.txt, and build the customer-item purchase history table (as explained in the lecture) where an entry of 1 means the customer has bought the item and 0 otherwise. Print the total number of non-zero entries (i.e. with a value of 1) in the customer-item purchase history table (Positive entries: number).

Precomputing item-to-item angles. Your program should work out the angles (in degrees) between every pair of items (excluding an item with itself). Print the average of all the pairwise angles (Average angle: average angle).

Recommendation. For each query (each line in queries.txt), your program should perform the following: Print the query in a line Shopping cart: query. For each item Item ID in the query (in the order as it appears), find an item Match ID not in the current shopping cart which has the minimum angle Min Angle with the item Item ID. If Min Angle is less than 90 , print Item: Item ID; match: Match ID; angle: Min Angle. Otherwise, no match is accepted, and you should simply print Item: Item ID no match. Note that when multiple items have the same minimum angle, your algorithm can print any one of these. Each printed item Match ID is considered as a candidate for recommendation. Produce the recommendation list by combining all the candidates and order them in increasing order of angles. For items which are considered relevant via different shopping cart items, the minimum angle it makes with any item in the shopping cart should be used in ranking, and it should only appear in the recommendation list once. If multiple candidates have the same angle, they may appear in arbitrary order. Print Recommend: list of recommended items.

Given the following history.txt:

5 5 12

1 1

1 2

2 1

2 3

3 1

3 2

3 4

4 2

4 4

1 2

2 3

5 5

and the following queries.txt:

2

1 2

5

5 1

5 1 4

1 3 5

the exact output of your program should be:

Positive entries: 10

Average angle: 74.41

Shopping cart: 2

Item: 2; match: 4; angle: 35.26

Recommend: 4

Shopping cart: 1 2

Item: 1; match: 3; angle: 54.74

Item: 2; match: 4; angle: 35.26

Recommend: 4 3

Shopping cart: 5

Item: 5 no match

Recommend:

Shopping cart: 5 1

Item: 5 no match

Item: 1; match: 2; angle: 48.19

Recommend: 2 Shopping cart: 5 1 4

Item: 5 no match

Item: 1; match: 2; angle: 48.19

Item: 4; match: 2; angle: 35.26

Recommend: 2

Shopping cart: 1 3 5

Item: 1; match: 2; angle: 48.19

Item: 3 no match

Item: 5 no match

Recommend: 2