Clustering, association rules, reinforcement learning and genetic algorithms (HL)

A gym records three values for each of its 2400 members: number of visits per month, average length of a visit, and number of fitness classes attended. The gym does not know in advance what types of member it has. It uses a clustering algorithm to group the members.

(a) Explain why this is an example of unsupervised learning. [1]

(b) Describe what the algorithm is trying to achieve when it forms the clusters. [1]

(c) Outline one way the gym could use the clusters it finds. [1]

A games company uses k-means clustering (k = 2) to group six players of a mobile app. The graph shows each player’s sessions per week and hours of use per week, together with the two initial centroids K1 (1, 1) and K2 (5, 5).

The data points are A (1, 2), B (2, 1), C (2, 3), D (4, 4), E (6, 5) and F (7, 7).

(a) Using Euclidean distance, determine which centroid each player is assigned to in the first iteration. Show your working for player C. [2]

(b) Calculate the new position of each centroid after the first iteration. [2]

(c) State when the k-means algorithm stops. [1]

A café records the items bought in ten transactions.

(a) Outline what is meant by an association rule. [1]

(b) Calculate the support of the itemset {croissant, latte}. [1]

(c) Calculate the confidence of the rule {croissant} → {latte}. Show your working. [2]

(d) The confidence of the rule {latte} → {croissant} is lower. Suggest how the café could use the rule {croissant} → {latte}. [1]

An online shop sells four products: phone case (P), screen protector (S), charger (C) and headphones (H). Eight orders are shown.

The shop uses the Apriori algorithm with a minimum support count of 3. All four single items are frequent.

(a) Identify the frequent itemsets that contain exactly two items. Show the counts you used. [2]

(b) Explain why the algorithm does not need to count the itemset {P, S, C}. [2]

(c) The lift of a rule X → Y is given by

Calculate the lift of the rule {S} → {P}. [2]

(d) Interpret your answer to (c). [1]

A robot lawnmower uses reinforcement learning to learn how to cut a garden efficiently.

(a) For this system, identify:

    (i) the agent [1]

    (ii) the environment [1]

    (iii) one action the agent could take [1]

    (iv) one event that could give a negative reward. [1]

(b) State what is meant by the agent’s policy. [1]

A music-streaming app uses reinforcement learning to choose which of four playlists, A–D, to show on a user’s home screen. The reward is 1 if the user plays the playlist and 0 otherwise. The table shows the average reward the agent has recorded so far.

The agent uses an ε-greedy strategy with ε = 0.1: with probability ε it chooses one of the four playlists at random (each equally likely); otherwise it chooses the playlist with the highest average reward.

(a) State which playlist the agent chooses when it exploits. [1]

(b) Calculate the probability that playlist B is shown on a given turn. [2]

(c) Explain why setting ε = 0 could lead to a poor long-term outcome. [2]

(d) Suggest why the developers reduce ε gradually as more data is collected. [1]

An agent learns to move through the 3 × 3 grid shown. Each square is a state, labelled (column, row). It starts in square (1, 1) and can move Up, Down, Left or Right by one square.

Rewards: every move into an ordinary square gives −1; moving into the GOAL (3, 3) gives +10 and moving into the PIT (2, 2) gives −10. Reaching the GOAL or the PIT ends the episode.

(a) State the number of states in this environment. [1]

(b) The agent follows the policy: “move Right if possible, otherwise move Up”. State the squares the agent visits and calculate its total reward. [2]

(c) Calculate the total reward for the sequence of moves Right, Up. [1]

(d) Explain why every ordinary move is given a reward of −1. [1]

(e) During training, the agent sometimes moves Up from the start square even though its current policy says Right. Explain why. [2]

A genetic algorithm is used to find a short delivery route that visits five towns, A, B, C, D and E, exactly once each and returns to the start (a travelling salesperson problem).

(a) Describe how a possible solution (an individual in the population) could be represented. [1]

(b) Outline how the fitness of an individual could be calculated. [1]

(c) Two parent routes are A B C D E and C E A D B. Single-point crossover is applied after the second town. Explain why this produces an invalid child route. [2]

(d) Describe a mutation operator that always produces a valid route. [1]

(e) State one condition that could be used to terminate the algorithm. [1]

A genetic algorithm is used to choose items to pack into a bag with a maximum capacity of 10 kg. Each individual is a 5-bit string; bit i is 1 if item i is packed.

Fitness = total value of the packed items, or 0 if the total mass is more than 10 kg.

(a) Calculate the fitness of P3. [2]

(b) Roulette-wheel selection is used, so the probability of selection is proportional to fitness. Calculate the probability that P4 is selected as a parent. [1]

(c) P3 and P4 are crossed over using single-point crossover after bit 2. State the two children. [2]

(d) Bit 4 of the first child (from (c)) is then mutated. Calculate the fitness of the mutated child and explain what this shows about the purpose of mutation. [2]

An online clothing store uses k-means clustering to segment its customers. The graph shows the within-cluster sum of squares (WCSS) for different values of k.

(a) Using the elbow method, state the most suitable value of k. [1]

(b) Explain why the store should not simply choose the value of k that gives the lowest WCSS. [2]

The store clusters customers using two features: annual spend (from £200 to £5000) and number of returns per year (from 0 to 10). Three customers are:

(c) (i) Calculate the Euclidean distance from X to Y and from X to Z, using the raw values. [2]

    (ii) Explain why these distances could produce misleading clusters. [1]

    (iii) Outline how the store should prepare the data before clustering. [1]