Computational methods: data mining, heuristics and performance modelling

Overview

Recall questions on data mining and its limitations, heuristics in route planning, satnavs and antivirus detection, what heuristics trade away, performance modelling with worked examples, and when modelling is the only sensible option.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is data mining, and how does it differ from simply querying a database?

   Model answer

   Data mining is searching very large volumes of data — usually collected for some other purpose and brought together from several sources into a single warehouse — for patterns, correlations, trends and anomalies that nobody knew were there, using statistical and machine-learning techniques. The difference from querying is the direction of travel: a query answers a question you already have ('how many customers bought bread last week?'), whereas data mining looks for the questions worth asking, producing associations such as 'customers who buy X also buy Y', clusters of similar customers, classifications and outliers that no one thought to ask about.

2. 2

   Give a worked example of data mining solving a real problem.

   Model answer

   A supermarket's loyalty scheme records every basket. Mining several years of transactions finds which products are bought together, which purchases predict a change in a household such as a new baby, and how buying varies with the weather and the day of the week. The chain acts on the findings: it places associated goods near each other, times its offers, sets stock levels branch by branch, and sends individual customers vouchers for things they are likely to want. A second example is card fraud: an issuer mines millions of past transactions to learn what normal spending looks like for each customer, so that a transaction far outside that pattern — an unusual amount, country or type of merchant — is flagged within seconds of being attempted.

3. 3

   What are the limitations of data mining?

   Model answer

   It needs enormous quantities of data, and the results are only as good as that data: inconsistent, incomplete, duplicated or out-of-date records produce misleading patterns, so a great deal of cleaning and preparation is required first. Search enough data and coincidental correlations are certain to appear, so a discovered pattern is a hypothesis to be tested rather than a fact, and correlation does not establish cause. It is computationally expensive, needing substantial storage and processing. Many patterns found turn out to be already known or of no practical use. And there are legal and ethical limits: personal data combined from several sources can identify individuals and reveal things they never chose to disclose, so consent, stated purpose and data-protection law constrain what may be done with it.

4. 4

   What is a heuristic, and what exactly does it trade away?

   Model answer

   A heuristic is a rule-of-thumb or educated-guess approach that finds a good enough answer quickly, used when finding the guaranteed best answer would take far too long or when no exact method exists at all. What it trades away is certainty: there is no guarantee that the answer it gives is the optimal one, and in some applications no guarantee that it is even correct. It is chosen precisely when that trade is worth making — a route five per cent longer that is found in a second is worth far more than the perfect route that takes a week to compute.

5. 5

   A delivery firm must visit 30 addresses and return to the depot by the shortest total route. Why is the exact method unusable, and what does a heuristic do instead?

   Model answer

   The exact method compares every possible order of visits, and the number of orders grows factorially with the number of stops, so with 30 addresses there are vastly more routes than could be examined in a human lifetime even at billions per second. A heuristic instead builds a good route fast: nearest neighbour repeatedly drives to the closest address not yet visited, producing a route in a fraction of a second that is typically within about a quarter of the best possible. A second heuristic then improves it — repeatedly swap two legs of the route whenever the swap shortens the total, stopping when no swap helps any more. Neither can promise the shortest route; they promise a good route this morning, which is what the firm actually needs.

6. 6

   How does a satnav use a heuristic to find a route faster?

   Model answer

   A plain shortest-path search spreads out from the start in every direction, examining junctions all around until it happens to reach the destination, including many that lead directly away from it. An informed search adds a heuristic estimate of the distance still to go — typically the straight-line distance from each junction to the destination — to the distance already covered, and always examines next whichever junction has the smallest total. That steers the search towards the destination, so far fewer junctions are examined and the answer arrives much sooner. Here the estimate never overstates the true remaining distance, since a straight line cannot be longer than a road, and that is what allows this particular heuristic to keep finding the genuine shortest route while still cutting the work; heuristics that guess more aggressively are faster still but can return a route that is not the best.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.