2
85kviews
Explain multidimensional and multilevel association rules with an example.
1 Answer
18
3.9kviews

MULTILEVEL ASSOCIATION RULES:

  • Association rules generated from mining data at multiple levels of abstraction are called multiple-level or multilevel association rules.
  • Multilevel association rules can be mined efficiently using concept hierarchies under a support-confidence framework.
  • Rules at high concept level may add to common sense while rules at low concept level may not be useful always.
    • Using uniform minimum support for all levels:
  • When a uniform minimum support threshold is used, the search procedure is simplified.
  • The method is also simple, in that users are required to specify only one minimum support threshold.
  • The same minimum support threshold is used when mining at each level of abstraction.
  • For example, in Figure, a minimum support threshold of 5% is used throughout.
  • (e.g. for mining from “computer” down to “laptop computer”).
  • Both “computer” and “laptop computer” are found to be frequent, while “desktop computer” is not.

  • Using reduced minimum support at lower levels:

    • Each level of abstraction has its own minimum support threshold.
    • The deeper the level of abstraction, the smaller the corresponding threshold is.
    • For example in Figure, the minimum support thresholds for levels 1 and 2 are 5% and 3%, respectively.
    • In this way, “computer,” “laptop computer,” and “desktop computer” are all considered frequent.

Multilevel Association rule consists of alternate search strategies and Controlled level cross filtering:

1.Alternate Search Strategies:

  • Level by level independent:

    • Full breadth search.
    • No background knowledge in pruning.
    • Leads to examine lot of infrequent items.
  • Level-cross filtering by single item:

    • Examine nodes at level i only if node at level (i-1) is frequent.
    • Misses frequent items at lower level abstractions (due to reduced support).
  • Level-cross filtering by k-item set:
    • Examine k-itemsets at level i only if k-itemsets at level (i-1) is frequent.
    • Misses frequent k-itemsets at lower level abstractions (due to reduced support).
  • Controlled Level-cross filtering by single item:
    • A modified level-cross filtering by single item.
    • Sets a level passage threshold for every level.
  • Allows the inspection of lower abstractions even if its ancestor fails to satisfy min_sup threshold.

MULTIDIMENSIONAL ASSOCIATION RULES:

1.In Multi dimensional association:

  • Attributes can be categorical or quantitative.
  • Quantitative attributes are numeric and incorporates hierarchy.
  • Numeric attributes must be discretized.
  • Multi dimensional association rule consists of more than one dimension:

Eg: buys(X,”IBM Laptop computer”)buys(X,”HP Inkjet Printer”)

2.Three approaches in mining multi dimensional association rules:

1.Using static discritization of quantitative attributes.

  • Discritization is static and occurs prior to mining.
  • Discritized attributes are treated as categorical.
  • Use apriori algorithm to find all k-frequent predicate sets(this requires k or k+1 table scans ).
  • Every subset of frequent predicate set must be frequent.
  • Eg: If in a data cube the 3D cuboid (age, income, buys) is frequent implies (age, income), (age, buys), (income, buys) are also frequent.
  • Data cubes are well suited for mining since they make mining faster.
  • The cells of an n-dimensional data cuboid correspond to the predicate cells.

2.Using dynamic discritization of quantitative attributes:

  • Known as mining Quantitative Association Rules.
  • Numeric attributes are dynamically discretized.
  • Eg: age(X,”20..25”) Λ income(X,”30K..41K”)buys (X,”Laptop Computer”)

GRID FOR TUPLES

GRID FOR TUPLES

3.Using distance based discritization with clustering.

This id dynamic discretization process that considers the distance between data points.

  • It involves a two step mining process:
    • Perform clustering to find the interval of attributes involved.
    • Obtain association rules by searching for groups of clusters that occur together.
  • The resultant rules may satisfy:
    • Clusters in the rule antecedent are strongly associated with clusters of rules in the consequent.
    • Clusters in the antecedent occur together.
    • Clusters in the consequent occur together.
Please log in to add an answer.