Weeks 8-9: Association Rules & Temporal Data Mining

Question 1

Association Rule

Answer 1

An expression in if-then format.

The if is the precondition or antecedent. It has a series of tests.

The then part is the conclusion or consequent. It assigns values to one or more attributes.

Association rules may incorporate any attribute or combination of attributes as the target.

Question 2

Bottom-up Generate-and-test

Answer 2

A procedure for generating association rules that frequently occur in the rule’s right-hand side.

Question 3

Coverage/Support Count

Answer 3

The number of instances covered by the rule.

Question 4

Support

Answer 4

Proportion of instances covered by the rule.

Question 5

Confidence/accuracy

Answer 5

Proportion of instances that the rule predicts correctly over all instances satisfying the precondition.

Question 6

Apriori Algorithm

Answer 6

This is an algorithm for generating association rules.

1. Find all 1-item sets, calculate their coverage and discard any 1-item sets below the predefined min coverage value.
2. Find all 2-item sets by making pairs of 1-item sets and retain only 2-item sets with coverage above the minimum coverage value.
3. Similarly, find all 3-item sets, 4-item sets, and so on.
4. Repeat until no larger item sets are possible.
5. For each item set, produce as many association rules as the number of ways to split the relevant items between the precondition and the conclusion.
6. For each rule, evaluate the confidence and retain if the rule meets the minimum requirement.

Note that the algorithm implements the property that, if an item-set isn’t frequent, then all its supersets are also not frequent. The algorithm produces k+1 items only from k-item sets. The worst-case running of the algorithm is exponential with respect to the number of attributes.

Question 7

FP-Growth Algorithm

Answer 7

1. Count each item frequency and sort in descending order.
2. Perform a second pass of the data to create the FP-tree.
3. Recursively process the tree to identify frequent item sets.

The tree structure allows for more efficient extracting of association rules from a dataset. Usually, it has better run time than the apriori algorithm.

Question 8

Header Table

Answer 8

It appears on the left hand side of the FP-tree. It shows the frequencies of individual items satisfying the minimum coverage threshold, sorted in descending order.

Question 9

Lift

Answer 9

This metric measures the usefulness of a rule by comparing with respect to random guessing. It compares the confidence of the rule to the confidence of the null rule, which has the same right-hand side, but empty left-hand side.

Question 10

Contingency Table

Answer 10

There are two dimensions to this table.

Does the antecedent of the association rule appear in the transaction?
No: Absent
Yes: Present

Doe the consequent of the association rule appear in the transaction?
No: Absent
Yes: Present

The number of transactions is equal to the sum of the four resulting cells. If the cell for antecedent and consequent both being present is higher than the other cells, then this is a good indication that the association rule is good.

Question 11

Sequential Analysis/Sequential Pattern Analysis

Answer 11

This method adds the element of time to association analysis. It considers the sequences, not just the associations, of items, where the order in time is important.

As such, the support of an item set also depends on the order of the items. Generalised sequential pattern (GSP) is a suitable algorithm for sequence mining based on the apriori algorithm.

Question 12

Link Analysis

Answer 12

Approach for analysing and exploiting relationships and connections between items. It utilises graphs, with items as nodes and relationships as edges. Can be both supervised and unsupervised in training.

Graphs can be directed, undirected, multigraph (when multiple edges between the same pair of nodes are allowed), and connected (if there’s a path between every pair of nodes).

Question 13

Degree Centrality

Answer 13

This metric evaluates the relative importance of a node to the graph.

Question 14

Closeness Centrality

Answer 14

This metric measures how close a node is to all the other nodes in the graph.

Question 15

Time Series

Answer 15

A set of values obtained from measurements over time. A dataset may have a single or multiple time series.

T = (x_1,…,x_n)
x_t = time series value at time t

Question 16

Decomposition

Answer 16

Traditional approaches decompose a time series into additive components:

x_t = T_t + C_t + S_t + \epsilon_t

T_t: Trend, variations of low frequency
S: Seasonality, regular predictable changes
C: Cycle, periodic variations
\epsilon_t: Error, captures uncertainty of the model

Question 17

Moving Average (MA)

Answer 17

\hat{x}{t+1} = \frac{x{t-k+1}+…+x_{t-1} + x_t}{k}

Question 18

AutoRegressive (AR)

Answer 18

\hat{x}_{t+1} = \beta_0 + \beta_1 x_1 + \epsilon_t

Question 19

Exponential Smoothing

Answer 19

\hat{x}_{t+1} = \alpha x_t + (1 - \alpha)\hat{x}_t, for t \ge 1

\alpha = smoothing factor

Question 20

Representation

Answer 20

This is a challenge with time series data, as time series data reduces the dimensionality o the data.

Question 21

Similarity

Answer 21

This is a challenge with time series data, as one of the goals to to evaluate how similar a pair of time series are.

Question 22

Indexing

Answer 22

This is a challenge with time series data, as there needs to be an organising of time series to achieve low memory requirements and allow for faster querying.

Question 23

Non-Adaptive Representation

Answer 23

Common representation for all parts of a time series.

Question 24

Adaptive

Answer 24

Local properties are used to construct a non-uniform representation of a time series.

Question 25

Piecewise Linear Approximation

Answer 25

Approximates a time series using piecewise linear segments.

Question 26

Discrete Fourier Transformation (DFT)

Answer 26

Any signal can be represented with a finite number of sine/cosine waves.

Question 27

Singular Value Decomposition (SVD)

Answer 27

Represents the shape in terms of a linear combination of basic shapes, based on the variance of the dataset. In contrast to DFT which is local, SVD is a global transformation.

Question 28

Segmentation

Answer 28

Given a time series T with a large number n of time points, compute a model with k < n piecewise segments approximating T.

Question 29

Measuring Similarity

Answer 29

Whole series matching: compare two time series T and T’ using their entire length.

Subsequence matching: given a large sequence T and a query subsequence Q, find the T’s subsequences matching Q.

Question 30

Euclidean Distance for Time Series

Answer 30

It’s the euclidean distance between the points x_t(T) and x_t(T’).

This method is used in standardisation, but doesn’t account for acceleration and deceleration along the time axis.

Question 31

Dynamic Time Warping

Answer 31

Warp the time axis of one or both sequences for better alignment.

Question 32

Longest Common Subsequences

Answer 32

Match two sequences with potentially unmatched elements.

Question 33

Indexing

Answer 33

Given a time series T and similarity measure D(T,T’), find the most similar time series to T among a set of different time series.

Question 34

Anomaly Detection

Answer 34

Given a time series and a model of its behaviour, identify subsequences with anomalies.

Question 35

Motif Discovery

Answer 35

Find every subsequence, called motif, that appears repeatedly in a longer time series.

Question 36

Survival Analysis or Time-to-Even Analysis

Answer 36

Focuses on finding when something important will happen.

Examples:
- Churn, the number of customers who stop using a service or a company to move to another company that offers better services and prices for them.
- Tenure, the length of time that an individual remains a customer of a company.

Question 37

Survival Curve

Answer 37

This plot starts at a 100% and keeps decreasing. It’s similar in concept to the half life of an atom. Is used to predict the tenure of a customer. Survival curves may or may not reach 0%.

Question 38

Survival Function

Answer 38

S(t) = P(T > t)

Question 39

Discrete Survival Time Data

Answer 39

Time is partitioned into continuous non-overlapping time intervals specifried by the time points t_0 = 0 < t_1 < … < t_{\ell}.

The time intervals are (t_0, t_1], (t_1,t_2],…,(t_{\ell - 1}, t_{\ell}]

Question 40

Hazard for Discrete Survival Time Data

Answer 40

The probability h_i that the subject of interest will fail during (t_{i-1}, t_i], assuming survival at least until t_{i-1}:

h_i = P(t_{i-1} < T \le t_i \mid T > t_{i-1})

Hazard functions may increase and decrease over time.

Question 41

Kaplan_Meier Estimator of Survival Function

Answer 41

\hat{S}(t) = \prod_{i: t_i \le t} \left( 1 - \frac{d_i}{n_i} \right)

Kaplan-Meier survival curves decrease over time, with each curve modelling a different leaf in the survival tree.

Question 42

Survival Trees

Answer 42

A singe tree groups subjects according to their survival behaviour based on covariates.