Part 13: Pattern Mining

Printed copy: all task answers and model answers are expanded below their questions.

What this chapter assumes

• The general-to-specific ordering, and the two borders S and G (part12.html). Part 12 orders hypotheses by generality and represents a whole set of surviving hypotheses by two boundaries: S, the most specific survivors, and G, the most general ones. This Part reuses that machinery unchanged. What changes is the test a hypothesis has to pass. In Part 12 it was "consistent with every labelled example". Here it is "occurs often enough in the data", and, when a second threshold is present, "and not too often".
• The covers relation (part12.html). A hypothesis covers an example when the example falls under it. Everything in this Part follows from one concrete instance of that relation: a pattern h covers a transaction e exactly when h ⊆ e (deck p.8). Generality is the same subset relation: h1 is more general than h2 exactly when h1 ⊆ h2.
• A frontier you can write down, worked last in first out (part04.html). The enumeration algorithms here are search algorithms with a queue, and the exam question is a frontier trace of the kind you first wrote in Part 4. The 2023 sample paper's MC 1.2 (depth-first search follows a last in first out strategy, answer True) is the property this Part relies on: children pushed to the front of the queue make the walk depth first.
• Itemsets are the hypothesis language (part12.html). Part 12's hypotheses were tuples over attribute taxonomies. Here a hypothesis is a set of items, which is the special case in which every attribute is boolean (p.8). Smaller language, same search.

1. What pattern mining looks for, and the one thing it drops

Deck p.3 places the topic: data mining is "a subfield by itself that focuses on algorithms and techniques for analysing data, for finding interesting and actionable patterns and models in these data", and the course narrows to one corner of it, "frequent pattern mining, i.e., discovering patterns or regularity in the data". Page 4 gives the commercial instance, recommender systems: a webshop wants to know which books are bought together so it can suggest the third one.

Page 10 is the scope slide, and its middle bullet is the sentence that separates this Part from the previous one:

The rest of p.10 sets the boundaries of the lecture. Patterns come in several data types, "sets / strings / graphs", and the exercise session works on the first two. Patterns are wanted because they "give insight into the data" and because they are "actionable, can be used to suggest further products (association rules)". And the method is stated as search: "we search through the space of possible patterns", with the explicit note that "the basis of pattern mining is closely related to version spaces".

Page 9 gives the non-supermarket example that returns later in this chapter as the motivation for two thresholds at once: molecules are graphs, patterns are subgraphs, and the interesting subgraph is the one that occurs in the mutagenic molecules and not in the clean ones. Keep it in mind for section 12, where "frequent in one dataset, infrequent in another" becomes the algorithm's second test.

2. Data, patterns and frequency

Pages 5 and 6 are the same slide in two frames. Five customers have each bought a subset of six books, and the items are named by the colour of the cover: Blue, Red, Green, Yellow, Brown, AI. The slide writes the first basket twice, once as a boolean vector and once as a set, and the second form is the one the rest of the Part uses.

3. Association rules, shown once

Page 7 is the only slide in the deck about association rules. It states the shape, "IF X THEN Y with a particular probability P", derives one rule from the frequencies of the previous slide, and notes that rules "Can be used for predictive purposes". The conclusions slide p.34 repeats the idea in one line: "Frequent patterns can be turned in association rules to make predictions."

4. Itemsets: the hypothesis language, and the bridge from concept learning

Page 8 (reprinted as p.16 with the phrase "generality ordering lattice" added) gives the whole formal language in five lines. An itemset problem is the "special case where all attributes are boolean", and then:

Read the last two lines together and the geometry of the whole Part follows. More items means a stricter conjunction, which means fewer transactions covered, which means more specific and less frequent. Fewer items means more general and more frequent. The empty itemset {} is the most general pattern of all: it demands nothing, so it covers every transaction and its frequency is always the size of the dataset.

5. The single representation trick

Deck p.13 shows the running dataset for the rest of the chapter, four transactions over four items, plus three worked frequencies. Deck p.14 explains why the same notation means two different things on the two sides of the covers relation.

The four rows, written as itemsets with the initials the deck uses from p.17 onwards (s, b, c, m), are {s,b,c,m}, {s,b,m}, {s,c,m} and {s,m}. Learn this dataset: pages 17 to 33 never change it, and every worked number in the second half of this chapter comes from it.

The slide states it precisely. A transaction itemset {i1, …, ik} denotes i1 ∧ … ∧ ik ∧ ¬i(k+1) ∧ … ∧ ¬in: everything not listed is false. A pattern itemset {i1, …, ik} denotes only i1 ∧ … ∧ ik. From that asymmetry comes the line the whole search is built on: "The pattern covers all its supersets!"

6. Covers and anti-monotonicity

Pages 17 and 18 are one slide in two frames. Two copies of the same 16-node lattice stand side by side, labelled Transactions on the left and Patterns on the right, with the word covers between them. The point of drawing the identical structure twice is the single representation trick: the objects look the same, but a point on the right selects a whole region on the left.

The usable form of the property is its contrapositive, and it is what every algorithm in this Part exploits: if an itemset is infrequent, every extension of it is infrequent too, so the entire region below it can be discarded without a single further count.

7. The lattice: reading the answer off the search space

Pages 19, 20 and 21 run the same experiment three times on the same four transactions, changing only the thresholds. Learn to answer the question "which nodes are solutions" by inspection before learning the algorithm that finds them mechanically; the exam asks for both.

At a minimum frequency of 4, that is 100 percent, the slide gives the answer {s,m}, {s}, {m}, {} and then draws the conclusion this Part keeps coming back to: "Version space with S = {{s,m}} and G = {{}}", "Transactions act as positive examples, and we require 100% frequency !", "If we require 100% coverage, then S is intersection of all itemsets!"

At a minimum frequency of 2 the answer set grows to twelve itemsets, and the slide prints the two definitions that fill-in 2.2 asks for: "S contains the most specific (i.e., the maximal itemsets) that satisfy the frequency threshold. G contains the most general (i.e., the minimal itemsets) that satisfy the frequency threshold." Here S = {{s,m,c}, {s,m,b}} and G = {{}}.

8. The borders: S and G

Pages 22 and 23 are the formal versions of what the previous section did by eye. The deck splits them across two slides, one border each, and the sample exam's fill-in question is built out of both.

9. When this is exactly a version space

Three slides say the same thing at rising levels of precision. Page 19: at 100 percent frequency the answer is a version space, with transactions playing the part of positive examples. Page 23, printed under the G-set definition: "Concept-learning = 100% frequency on the positives AND 0% frequency on the negatives". Page 34, in the conclusions: "Also, 100% frequency on positives and 0% on negatives = concept-learning with version spaces."

The connection also explains why the search space is drawn the same way in both Parts. The lecturer introduced pattern mining as version spaces with the consistency requirement relaxed into a frequency requirement, and the deck's structure follows that: same lattice, same two borders, different acceptance test.

10. Enumeration 1: the naive algorithm and the duplicate problem

Page 25 gives the algorithm in six lines. It is a search from the most general pattern downwards, and it is worth reading with Part 4 in mind: a queue, a pop, a test, a push.

Input: a set of transactions D,
       a set of items ℐ,
       a frequency treshold c.
Queue = { {} }
for all I ∈ Queue do
    if freq(I,D) >= c
    then
        output I
        add all I ∪ {i} to Queue (with i ∈ ℐ - I)
end for

The slide's own justification for starting at the top is printed underneath it: "We start from the top element because the itemsets of interest are typically small. Recall that there can be 100.000s of products in a supermarket." Searching upwards from {s,m,c,b} would begin in the region where every count is zero.

Two details decide whether your trace matches the marking scheme. First, the add step sits inside the then-branch, so an infrequent itemset is never extended. Second, the exercise sheet fixes the queue discipline that the deck leaves open: "New itemsets are added to the front of the queue in alphabetical order." Front insertion makes the structure last in first out, which is why the session 10 solutions rename it and write stack = {{}}, While stack not empty do, Pop I from stack. The resulting walk is depth first, exactly as in Part 4.

11. Enumeration 2: the lexicographic check

The fix for the duplicate problem is one extra condition on the add step. Page 28 states it and page 29 shows the pruned picture.

Why it works: each itemset now has exactly one legal construction, the one that adds its items in descending order, so it has exactly one parent instead of k. The generation graph becomes a tree, and a tree has one path to each node. Nothing is lost, because every itemset still has that one descending construction available.

Input: a set of transactions D,
       a set of items ℐ,
       a frequency treshold c.
Queue = { {} }
for all I ∈ Queue do
    if freq(I,D) >= c
    then
        output I
        add all I ∪ {i} to Queue (with i ∈ ℐ - I
                                    and i lexicographically smaller than elements of I)
end for

12. Enumeration 3: a minimum and a maximum threshold

The last version of the algorithm adds the second threshold. Page 31 puts it in the pseudocode, and the change is smaller than it looks, but its placement is the examinable part.

Input: a set of pos transactions Pos,
       a set of neg transactions Neg,
       a set of items ℐ,
       frequency treshold t1, t2.
Queue = { {} }
for all I ∈ Queue do
    if freq(I,Pos) >= t1 then
        if freq(I,Neg) <= t2 then output I
        add all I ∪ {i} to Queue (with i ∈ ℐ - I
                                    and i lexicographically smaller than elements of I)
end for

Two wordings to watch. The deck writes freq(I,Neg) <= t2, the session 10 solutions write freq(I,D2) < t2, and the session 10 assignment asks for patterns with "a frequency < 3 in the control group". They are not the same boundary. Copy the inequality from the question you are answering, and write it at the top of your trace so the marker can see which one you used.

13. Mining substrings: the same idea, a different generality relation

Deck p.10 lists "sets / strings / graphs" as the data types pattern mining works on, and the third exercise of session 10 takes the algorithm across to strings. The generality relation changes from subset to substring: the sheet gives nut ⊂ donut and dot ⊄ donut, the second because a substring has to be contiguous.

The itemset algorithm cannot be carried over unchanged, because a string is a sequence: ar and ra are different patterns, and there is no single "smallest element" to compare a new letter against. What survives is the principle, and the sheet's hint says which one: "A string can't occur more than any of its substrings". That is anti-monotonicity in the substring order.

queue = { ε }
output = { ε }
While queue not empty do
    Pop I from queue
    for all i ∈ alphabet where substring(I+i, 1) ∈ output do
        if freq(I+i, D) ≥ t do
            output = output ∪ (I+i)
            queue = append (I+i) to back of queue

Why only the tail needs checking: the string I+i has exactly two substrings of its own length minus one, the head I and the tail. The head is already known to be frequent, because it came off the queue, which only ever holds frequent strings. So the tail is the one new thing to verify, and verifying it before counting saves the count.

14. Constraints beyond frequency: what may be pushed into the loop

The conclusions slide p.34 makes the general claim: "Minimum and maximum frequency are just one type of constraints", followed by the arrow "Pattern mining = search". The fourth exercise of session 10 asks what happens when a different kind of constraint arrives, and the answer separates the constraints that can be pushed into the pruning test from the ones that cannot.

Queue = {{}}
While queue not empty do
    Pop I from queue
    If freq(I,D1) >= t1
    Then
        If freq(I,D2) < t2 then output I
        Push I ∪ i in Queue (for all i ∈ ℐ', i ⊄ I and i < I)

Queue = {{}}
A set of anti-monotonic constraints C
While queue not empty do
    Pop I from queue
    If I satisfies all constraints in C and freq(I,D1) >= t1
    Then
        If freq(I,D2) < t2 then output I
        Add all I ∪ {i} to Queue (with i ∈ ℐ - I and i
                                    lexicographically smaller than elements of I)

15. Cross-course: this Part against the ML exam two days later

What this sets up

• Nothing formal in Part 14 (part14.html). Part 14 is the AI debate lecture: hype cycles, the singularity, bias, explainability, the ethics guidelines. It uses no lattice, no border, no frequency threshold, and nothing in this chapter is a prerequisite for it. The only thread that continues is thematic, the applications list on p.34 (molecular feature mining, supermarket data, mining episodes in alarm data over time) as an example of AI already deployed. Treat Part 14 as a separate preparation task, not as a continuation.
• The link that is examinable runs backwards (part12.html). Deck pp.19, 23 and 34 all point at version spaces, and the equivalence condition of section 9 is exactly the sort of cross-chapter statement quote 5 (T9) says the theory exam is built to test. When you revise Part 12, revise this Part's section 9 in the same sitting: they answer each other's questions.
• The search habits from Parts 4 and 5 (part04.html). This Part is the last place in the course where you write a frontier at every step. The discipline is the same one the sample exercise exam's question 1 rewards: write the data structure, not just the answer.
• Drill: viz-patternmining.html for stepping the enumeration on new datasets, and the four session 10 exercises above as the closest thing to a real exam question that exists for this Part.

Term box

Chapter index: index.html  ·  Previous: Part 12, Version Spaces  ·  Next: Part 14, The AI Debate  ·  Drill: viz-patternmining.html  ·  Search by question: question-index.html