Data Mining: Association Rules

Question 1

Knowledge Discovery Process

Answer 1

Question 2

Analysis techniques, methods

Answer 2

Descriptive methods:

Extract interpretable models describing data, for example client segmentation.

Predictive methods:

Exploidt some known variables to predict unknown or future values of variables, for example spam emails.

Question 3

Attributes types

Answer 3

Nominal: ID, eye color, zip codes

Ordinal: Rankings, grades, size in {tall, medium, short}

Interval: calendar dates, temperatures in celsius

Ratio: temperature in Kelvin, length, time, counts

Question 4

Nominal attributes possesses

Answer 4

Distinctness

Question 5

Ordinal attribute possesses

Answer 5

distinctness, order

Question 6

Interval attribute

Answer 6

Distinctness, order, addition

Question 7

Ratio attribute

Answer 7

Distinctness, order, addition, multiplication

Question 8

Data quality problems

Answer 8

Noise, outliers, missing values, duplicate data

Question 9

Important characteristics of structured data

Answer 9

Dimensionality: curse of dimensionality

Sparsity: Only presence counts

Resolution: Patterns depend on the scale

Question 10

Aggregation

Answer 10

Combining attributes into single one.

Purpose:

Data reduction: reducing attribute number ( sampling, feature selection, discretization)

Change of scale: from regions into states

Stability: aggregated data tends to be more stable (less deviation)

Question 11

Sampling

Answer 11

Samping is necessary because employing the entire data set is too expensive.

Sampling works if the sample set is representative of the entire dataset.

A sample is representative if it has approximately the same property as the original set of data.

Types:

Simple Random: Randomly selected

Without replacement: An object can be taken only once

With replacement: Same object can be takes more than once.

Stratified: Split data into several partitions, take random samples from each partition

Question 12

Dimensionality reduction

Answer 12

When dimensionality increases, data becomes more sparse in the space it occupies; Definition of distance and density between points become less meaningful. To prevent this we have dim. reduction:

Principal comp. analysis: find projection that captures largest amount of variation in data.

Singular value decomp.

Feature subset selection: remove redundant features and irrelevant features

Question 13

Feature subset selection techniques

Answer 13

Bruteforce: try all possible subsets as input of data mining algo

Emebedded: features are selected naturally by the data mining algo

Filter: features selected before algorithm is run

Wrapper: use algorithms as black box to get best subset

Question 14

Feature Creation

Answer 14

Create new attribute that represent better the inormation in the data set.

Feature Extraction: domain specific

Mapping Data to new space: for example Fourier Transform

Feature Construction: combine features

Question 15

Discretization

Answer 15

Split attribute domain from continuos into discrete.

Reduces cardinality of attribute domain.

Techniques:

• N intervals with same width (Incremental, easy to do, can be badly affected by outliers and sparse data)
• N intervals approx same cardinality (non incremental approach, good for sparse data and outliers)
• Clustering (fits wel sparse data)

Question 16

Attribute transformation

Answer 16

Function that maps attribute values to a new set of values;

Example: Normalization ( min-max, z-score, decimal scaling)

Question 17

Similarity/Dissimilarity for simple attributes

Answer 17

Question 18

Minkowski distance

Answer 18

r=1: city block (hamming distance)

r = 2: euclidean distance

r -> ∞: maximum distance between any component of the vectors.

Question 19

Properties of metrics

Answer 19

Question 20

Common properties of similarities

Answer 20

s(p,q) = 1 only if p = q

s(p, q) = s(q, p) for all p and q.

Question 21

Similarity between binary vectors

Answer 21

Simple matching:

SMC = matches/(number of attributes)

Jaccoard Coefficients:

J = (11 matches) / (number not both zero attribute values) = (M11) / (M01 + M10 + M11)

Question 22

Cosine similarity

Answer 22

Question 23

Combining similarities and combining weighted similarities

Answer 23

Question 24

Goal of association rules

Answer 24

Expoloratory technique.

Extraction of frequent correlations or pattern form a transactional database

Example:

diapers => beer

• 2% of transactions contains both items
• 30% of the ones containing diapers contais also beer

Question 25

transactional formats

Answer 25

A transaction can be a set of: - Market basket data - Textual data - Structured data

Question 26

Association rule: Itemset

Answer 26

Set including one or more items

Question 27

Association rule: k-itemset

Answer 27

Itemset with cardinality of k

Question 28

Association rule: Support count(#)

Answer 28

Frequency of occurrence of itemset example #{Diapers, Beer} = 2

Question 29

Association rule: support

Answer 29

is the fraction of transactions that contain an itemset example sup({beer, diapers}) = 2/5

Question 30

Association rule, Frequent itemset

Answer 30

Is an itemset whose support is greater than or equal to a minsup threshold

Question 31

Association rule, rule quality metrics

Answer 31

Given A=\>B Support := #{A,B}/ |T| where |T| is the cardinality of the transactional database. Confidence := sup(A,B)/sup(A), conditional probability of finding B having found A.

Question 32

Association rule extraction

Answer 32

Given a set of transaction, association rule mining is the extraction of rules satisfying the constraints: - support \>= minsup threshold - confidence \>= minconf threshold Result is - complete (all rules satisfying both contraints) - correct (only the rules satisfying both contraints)

Question 33

Association rule, frequent itemset generation and extraction of association rules

Answer 33

Frequent itemsets - many different techniques - level-wise approaches (apriori) - without candidate generation (fp-growth) - other - this is the most computationally expensive step Extraction of association rules - generation of all possible binary partitioning of each frequent itemset - possibly enforcing a confidence threshold

Question 34

Association rule, Apriori principle

Answer 34

If an itemset is frequent, then all of its subsets must also be frequent. - The support of an itemset can never exceed the support of any of its subsets - it reduces then number of candidates.

Question 35

Association rule, apriori algo

Answer 35

1. Candidate generation - Join step: generate candidates of len k+1 by joining frequent itemsets of len k - Prune step: apply apriori principle := prune len k+ 1 that contain at least on k-itemset that is not frequent. 2. Frequent itemset generation - ScanDB to count support for k+1 candidates - prune candidates below minsup Counting support of candidates: - candidate itemsets are stored in a hash-tree - subset function finds all candidates contain Performance issues: Candidate sets may be huge - 2-itemset generation is the most critical - extracting long frequent itemsets requires generating all frequent subsets Multiple database scans: n+1 scans when longest frequent pattern len is n Factors affecting performance: - min support threshold - dimensionality

Question 36

Association rule, FP-growth algo

Answer 36

Exploits compressed representation of the database = FP-TREE -\> high compression fo dense data distributions, complete representation for frequent pattern mining Frequent pattern mining: 1. recursive visit of fp-tree 2. applies divide and conquer approach Only 2 DB scans: cout item support + fp-tree build Fp-tree is just a Trie that counts how many childs a node has. Also each node with key k points to another node with key k and to the corresponding element on the header table. The header table counts the frequency of each single item. Alog: Scan header table from lowest support item up. For each item in header table extract freqeunt itemsets including item i and items preceding it in header table.

Question 37

Association rule, vertical data layout

Answer 37

Question 38

Association rule, Frequent Itemset

Answer 38

Question 39

Association rule, closed itemset

Answer 39

An itemset is closed if none of its immediatesupersets has the same support as the itemset

Question 40

Association rule, maximal, closed itemsets set

Answer 40

Question 41

Association rule, effect of support threshold

Answer 41

minsup too high: itemsets including rare but interesting items may be lost minsup is too low: too much data -\> computationally expensive.

Question 42

Confidence

Answer 42

Objective measure. Not always reliable, results are influenced by the cardinality of a set of data points.

Question 43

Correlation

Answer 43

Subjective measure: r: A =\> B correlation = P(A|B) / (P(A)P(B)) = conf(r) / sup(B) correlation = 1 =\> statistical independence correlation \> 1 =\> positive correlation correlation \< 1 =\> negative correlation.

Question 44

Weighted association rules

Answer 44

Consider item/transaction weights during association rule estraction Extend rule quality measures -\> weighted support, weigheted confidence. Apply ad-hoc weight aggregation -\> min, max, avg.

Question 45

Hierarchical association rules

Answer 45

Enable aggregation over attributes in a dataset... Typically user provided Example: time hierarchy, product category, location hierarchy.

Question 46

Generalized itemsets association rules

Answer 46

Sets of item at different generalization levels. Generalized itemset covers a transaction when: - all its generalized items are ancestors of items included in the transaction - its data items are included in the transaction Generalized itemset support: - ratio between number of covered transactions and dataset cardinality.

Question 47

High level, cross level, low level rules

Answer 47

High level -\> Only generalized itemsets (high level info) Cross level -\> generalized items and data items combined Low-level reles -\> only data itemsets.