hw2 110590049

tags data

2023 Educational Data Mining and Applications HW2.pdf

6.3

a

1. Support(L) ≥ minimum support threshold.
   
2. Since S is a subset of L, it means that any transaction containing all items in S also contains all items in L.
3. Support(S) ≥ Support(L) (because S includes all transactions that L includes)
4. Therefore, Support(S) ≥ minimum support threshold.
5. This proves that S is also a frequent itemset.

b

1. S’ ⊆ S
2. {T ∈ D | S ⊆ T} = Support(S) , all possible set T that is the superset of S
3. {T ∈ D | S ⊆ T} ⊆ {T ∈ D | S’ ⊆ T}
4. Support(S) ≤ Support(S’)

c

1. Confidence(X => Y) = Support(X ∪ Y) / Support(X).
2. Confidence(s => {l-s}) = Support(s ∪ {l-s}) / Support({l-s}).
3. Confidence(s’ => {l-s’}) = Support(s’ ∪ {l-s’}) / Support({l-s’}).
4. Support(s’ ∪ (l - s’)) ≤ Support(s ∪ (l - s))
5. Support(s’) ≤ Support(s)
6. Confidence(s’ => (l - s’)) ≤ Confidence(s => (l - s))

d

1. If I is frequent in D, it must have a support count greater than or equal to the minimum support count threshold (minsup) for frequent itemsets in D.
2. If I is not frequent in any partition Pi, it must have a support count less than the minsup in each partition.
3. Any itemset that is frequent in the original database D must be frequent in at least one partition of D.

6.6

min_support=0.6
min_confi=0.8

a

Apriori algorithm

$$\text{frequent itemsets}:\{\{E\},\{K\},\{M\},\{O\},\{Y\},\{EK\},\{EO\},\{KM\},\{KO\},\{KY\},\{EKO\}\}$$

FP-growth algorithm

$$\begin{array}{rl}& \\ \text{frequent itemsets}:& \{\{E:5\},\{K:4\},\{M:3\},\{O:3\},\{Y:3\},\\ & \{E,K:4\},\{E,O:3\},\{K,M:3\},\{K,O:3\},\{K,Y:3\},\\ & \{E,K,O:3\}\}\end{array}$$

conclusion

By query 2 time to build FP-tree reduce the time to query database .So FP-growth is more efficient compared to a priori.

b

6.14

a

$$\text{support(hot dogs , hamburgers)}=P(\text{hot dogs}\cap \text{hamburgers})=0.4$$ $$\text{confidence(hot dogs}\to \text{hamburgers)}=\frac{P(\text{hot dogs}\cap \text{hamburgers})}{P(\text{hamburgers})}=0.8$$ $$0.4>0.25\text{ and }0.8>0.5\text{ so it is a strong rule}$$

b

$$\begin{gathered} lift(\text{hot dogs}\to \text{hamburgers})=\frac{\frac{2000}{5000}}{\frac{3000}{5000}\frac{2500}{5000}}=\frac{4}{3} \\ \frac{4}{3}>1\text{ so positively correlated} \end{gathered}$$

c

$$\begin{array}{rlrl}& & & \\ AllConf(a,b)& =\frac{P(a\&b)}{\max (P(a),P(b))}& =0.666& \\ MaxConf(a,b)& =\max (P(a|b),P(b|a))& =0.8& \\ Kulc(a,b)& =\frac{1}{2}(P(b|a)+P(a|b))& =0.7333& \\ Cosine(a,b)& =\frac{a\cdot b}{|a|\times |b|}=\frac{2000}{\sqrt{2500\times 3000}}& =0.730& \\ Lift(a,b)& =\frac{P(a\&b)}{P(a)P(b)}& =1.333& \end{array}$$