Data Mining by Mehmed Kantardzic (good book recommendations TXT) 📕

additional MD patterns. The third and last iteration in our example starts with the A3 dimension and the corresponding pattern is (*, *, m).

In summary, the modified BUC algorithm defines a set of MD patterns with the corresponding projections of a database. The processing tree for our example of database DB is shown in Figure 10.8. Similar trees will be generated for a larger number of dimensions.

Figure 10.8. A processing tree using the BUC algorithm for the database in Table 10.4.

When all MD patterns are found, the next step in the analysis of multidimensional-transactional database is the mining of frequent itemsets in the MD-projected database for each MD pattern. An alternative approach is based on finding frequent itemsets first and then the corresponding MD patterns.

10.8 REVIEW QUESTIONS AND PROBLEMS

1. What is the essential difference between association rules and decision rules (described in Chapter 6)?

2. What are the typical industries in which market-basket analysis plays an important role in the strategic decision-making processes?

3. What are the common values for support and confidence parameters in the Apriori algorithm? Explain using the retail industry as an example.

4. Why is the process of discovering association rules relatively simple compared with generating large itemsets in transactional databases?

5. Given a simple transactional database X:X:TIDItems T01A, B, C, D T02A, C, D, F T03C, D, E, G, A T04A, D, F, B T05B, C, G T06D, F, G T07A, B, G T08C, D, F, G

Using the threshold values support = 25% and confidence = 60%,

(a) find all large itemsets in database X;

(b) find strong association rules for database X;

(c) analyze misleading associations for the rule set obtained in (b).

6. Given a transactional database Y:Y:TIDItems T01A1, B1, C2 T02A2, C1, D1 T03B2, C2, E2 T04B1, C1, E1 T05A3, C3, E2 T06C1, D2, E2

Using the threshold values for support s = 30% and confidence c = 60%,

(a) find all large itemsets in database Y;

(b) if itemsets are organized in a hierarchy so that A = {A1, A2, A3},

B = {B1, B2}, C = {C1, C2, C3}, D = {D1, D2}, and E = {E1, E2}, find large itemsets that are defined on the conceptual level including a hierarchy of items;

(c) find strong association rules for large itemsets in (b).

7. Implement the Apriori algorithm and discover large itemsets in transactional database.

8. Search the Web to find the basic characteristics of publicly available or commercial software tools for association-rule discovery. Document the results of your search.

9. Given a simple transactional database, find FP tree for this database if

(a) support threshold is 5;

(b) support threshold is 3.TIDItems1a b c d2a c d f3c d e g a4a d f b5b c g6d f g7a b g8c d f g

10. Given a simple transaction database:TIDItems1X Z V2X Y U3Y Z V4Z V W

Using two iterations of the Apriori algorithm find large 2-itemsets if required support is s ≥ 50%. Show all steps of the algorithm.

11. Given a frequent itemset A,B,C,D, and E, how many possible association rules exist?

12. What are the frequent itemsets with a minimum support of 3 for the given set of transactions?TIDItems101A,B,C,D,E102A,C,D103D,E104B,C,E105A,B,D,E106A,B107B,D,E108A,B,D109A,D110D,E

13. The conviction is a measure for an analysis of a quality of association rules. The formula for conviction CV in terms of probabilities is given as:

or in terms of support and confidence of an association rule:

What are basic characteristics of the conviction measure? Explain the meaning of some characteristic values.

14. Consider the dataset given in the table below.Customer IDTransaction IdItems418234145{X, Z}345543789{U, V, W, X, Y, Z}323965157{U, W, Y}418489651{V, X, Z}567748965{U, Y}567325687{W, X, Y}323147895{X, Y, Z}635617851{U, Z}345824697{V, Y}635102458{V, W, X}

(a) Compute the support for item sets {Y}, {X, Z} and {X, Y, Z} by treating each transaction ID as a market basket.

(b) Use the results from part (a) to compute the confidence for rules XZ → Y and Y → XZ.

(c) Repeat part (a) by treating each customer ID as a market basket. Each item should be treated as a binary variable (1 if an item appears in at least one transaction bought by the customer, and 0 otherwise).

(d) Use the results from part (c) to compute the confidence for rules XZ → Y and Y → XZ.

(e) Find FP-tree for this database if support threshold is 5.

15. A collection of market-basket data has 100,000 frequent items, and 1,000,000 infrequent items. Each pair of frequent items appears 100 times; each pair consisting of one frequent and one infrequent item appears 10 times, and each pair of infrequent items appears once. Answer each of the following questions. Your answers only have to be correct to within 1%, and for convenience, you may optionally use scientific notation, for example, 3.14 × 108 instead of 314,000,000.

(a) What is the total number of pair occurrences? That is, what is the sum of the counts of all pairs?

(b) We did not state the support threshold, but the given information lets us put bounds on the support threshold s. What are the tightest upper and lower bounds on s?

10.9 REFERENCES FOR FURTHER STUDY

Adamo, J., Data Mining for Association Rules and Sequential Patterns, Springer, Berlin, 2001.

This book presents a collection of algorithms for data mining on the lattice structure of the feature space. Given the computational complexity and time requirements of mining association rules and sequential patterns, the design of efficient algorithms is critical. Most algorithms provided in the book are designed for both sequential and parallel execution, and they support sophisticated data mining of large-scale transactional databases.

Cheng J., Y. Ke, W. Ng, A Survey on Algorithms for Mining Frequent Itemsets Over Data Streams, Knowledge and Information Systems, Vol. 16, No. 1, 2008, pp.1–27.

The increasing prominence of data streams arising in a wide range of advanced applications such as fraud detection and trend learning has led to the study of online mining of frequent itemsets. Unlike mining static databases, mining data streams poses many new challenges. In addition to the one-scan nature, the unbounded memory requirement and the high data arrival rate of data streams, the combinatorial explosion of itemsets exacerbates the mining task. The high complexity of the frequent itemset mining problem hinders