Slides

Association Analysis (Data Engineering)

Type of attributes in assoc. analysis • Association rule mining assumes the input data consists of binary attributes called items. – The presence of an item in a transaction is also assumed to be more important than its absence. – As a result, an item is treated as an asymmetric binary attribute.

• Now we extend the formulation to data sets with symmetric binary, categorical, and continuous attributes.

Type of attributes • Symmetric binary attributes – – – – –

Gender Computer at Home Chat Online Shop Online Privacy Concerns

• Nominal attributes – Level of Education – State

• Example of rules: {Shop Online= Yes}  {Privacy Concerns = Yes}. This rule suggests that most Internet users who shop online are concerned about their personal privacy.

Transforming attributes into Asymmetric Binary Attributes • Create a new item for each distinct attribute-value pair. • E.g., the nominal attribute Level of Education can be replaced by three binary items: – Education = College – Education = Graduate – Education = High School

• Binary attributes such as Gender are converted into a pair of binary items – Male – Female

Data after binarizing attributes into “items”

Handling Continuous Attributes • Solution: Discretize

• Example of rules: – Age[21,35)  Salary[70k,120k)  Buy – Salary[70k,120k)  Buy  Age: =28, =4 • Of course discretization isn’t always easy. – If intervals too large may not have enough confidence Age  [12,36)  Chat Online = Yes (s = 30%, c = 57.7%) (minconf=60%) – If intervals too small may not have enough support Age  [16,20)  Chat Online = Yes (s = 4.4%, c = 84.6%) (minsup=15%)

Statistics-based quantitative association rules Salary[70k,120k)  Buy  Age: =28, =4 Generated as follows: • Specify the target attribute (e.g. Age). • Withhold target attribute, and “itemize” the remaining attributes. • Apply algorithms such as Apriori or FP-growth to extract frequent itemsets from the itemized data. – Each frequent itemset identifies an interesting segment of the population.

• Derive a rule for each frequent itemset. – E.g., the preceding rule is obtained by averaging the age of Internet users who support the frequent itemset {Annual Income> $100K, Shop Online = Yes}

• Remark: Notion of confidence is not applicable to such rules.

Concept Hierarchies Food

Electronics

Bread Computers

Milk

Wheat

White

Skim

Foremost

Home

2% Desktop

Laptop Accessory

TV

Kemps Printer

Scanner

DVD

Multi-level Association Rules • Why should we incorporate a concept hierarchy? – Rules at lower levels may not have enough support to appear in any frequent itemsets – Rules at lower levels of the hierarchy are overly specific e.g., skim milk  white bread, 2% milk  wheat bread, skim milk  wheat bread, etc.

are all indicative of association between milk and bread

Multi-level Association Rules • How do support and confidence vary as we traverse the concept hierarchy? – If X is the parent item for both X1 and X2, and they are the only children, then (X) ≤ (X1) + (X2) (Why?) – Because X1, and X2 might appear in the same transactions.

– If and then

(X1  Y1) ≥ minsup, X is parent of X1, Y is parent of Y1 (X  Y1) ≥ minsup (X1  Y) ≥ minsup (X  Y) ≥ minsup

– If then

conf(X1  Y1) ≥ minconf, conf(X1  Y) ≥ minconf

Multi-level Association Rules Approach 1 • Extend current association rule formulation by augmenting each transaction with higher level items Original Transaction: {skim milk, wheat bread} Augmented Transaction: {skim milk, wheat bread, milk, bread, food}

• Issue: – Items that reside at higher levels have much higher support counts if support threshold is low, we get too many frequent patterns involving items from the higher levels

Multi-level Association Rules Approach 2 • Generate frequent patterns at highest level first.

• Then, generate frequent patterns at the next highest level, and so on. • Issues: – May miss some potentially interesting cross-level association patterns. E.g. skim milk  white bread, 2% milk  white bread, skim milk  white bread might not survive because of low support, but milk  white bread could. However, we don’t generate a cross-level itemset such as {milk, white bread}

Mining word associations (in Web) Document-term matrix: Frequency of words in a document “Itemset” here is a collection of words “Transactions” are the documents. Example: W1 and W2 tend to appear together in the same documents. Potential solution for mining frequent itemsets: Convert into 0/1 matrix and then apply existing algorithms –Ok, but looses word frequency information

TID W1 W2 W3 W4 W5 D1 2 2 0 0 1 D2 0 0 1 2 2 D3 2 3 0 0 0 D4 0 0 1 0 1 D5 1 1 1 0 2

Normalize First • How to determine the support of a word? • First, normalize the word vectors – Each word has a support, which equals to 1.0 • Reason for normalization – Ensure that the data is on the same scale so that sets of words that vary in the same way have similar support values.

TID W1 D1 2 D2 0 D3 2 D4 0 D5 1

W2 W3 W4 W5 20 0 0 1 0 1 2 2 30 0 0 0 0 1 0 1 10 1 0 2

Normalize

TID D1 D2 D3 D4 D5

W1 0.40 0.00 0.40 0.00 0.20

W2 0.33 0.00 0.50 0.00 0.17

W3 0.00 0.33 0.00 0.33 0.33

W4 0.00 1.00 0.00 0.00 0.00

W5 0.17 0.33 0.00 0.17 0.33

Association between words • E.g. How to compute a “meaningful” normalized support for {W1, W2}? • One might think to sum-up the average normalized supports for W1 and W2. s({W1,W2}) = (0.4+0.33)/2 + (0.4+0.5)/2 + (0.2+0.17)/2 =1

• This result is by no means an accident. Why? • Averaging is useless here.

TID D1 D2 D3 D4 D5

W1 0.40 0.00 0.40 0.00 0.20

W2 0.33 0.00 0.50 0.00 0.17

W3 0.00 0.33 0.00 0.33 0.33

W4 0.00 1.00 0.00 0.00 0.00

W5 0.17 0.33 0.00 0.17 0.33

Min-APRIORI • Use instead the min value of normalized support (frequencies).

TID D1 D2 D3 D4 D5

W1 0.40 0.00 0.40 0.00 0.20

W2 0.33 0.00 0.50 0.00 0.17

W3 0.00 0.33 0.00 0.33 0.33

W4 0.00 1.00 0.00 0.00 0.00

W5 0.17 0.33 0.00 0.17 0.33

Example: s({W1,W2}) = min{0.4, 0.33} + min{0.4, 0.5} + min{0.2, 0.17} = 0.9

s({W1,W2,W3}) = 0 + 0 + 0 + 0 + 0.17 = 0.17

Anti-monotone property of Support TID D1 D2 D3 D4 D5

W1 0.40 0.00 0.40 0.00 0.20

W2 0.33 0.00 0.50 0.00 0.17

W3 0.00 0.33 0.00 0.33 0.33

W4 0.00 1.00 0.00 0.00 0.00

W5 0.17 0.33 0.00 0.17 0.33

Example: s({W1}) = 0.4 + 0 + 0.4 + 0 + 0.2 = 1

s({W1, W2}) = 0.33 + 0 + 0.4 + 0 + 0.17 = 0.9 s({W1, W2, W3}) = 0 + 0 + 0 + 0 + 0.17 = 0.17 So, standard APRIORI algorithm can be applied.