Databases Reference
In-Depth Information
mined efficiently using concept hierarchies under a support-confidence framework. In
general, a top-down strategy is employed, where counts are accumulated for the calcu-
lation of frequent itemsets at each concept level, starting at concept level 1 and working
downward in the hierarchy toward the more specific concept levels, until no more fre-
quent itemsets can be found. For each level, any algorithm for discovering frequent
itemsets may be used, such as Apriori or its variations.
A number of variations to this approach are described next, where each variation
involves “playing” with the support threshold in a slightly different way. The variations
are illustrated in Figures 7.3 and 7.4, where nodes indicate an item or itemset that has
been examined, and nodes with thick borders indicate that an examined item or itemset
is frequent.
Using uniform minimum support for all levels
(referred to as
uniform support
):
The same minimum support threshold is used when mining at each abstraction level.
For example, in Figure 7.3, a minimum support threshold of 5% is used throughout
(e.g., for mining from “
computer
” downward to “
laptop computer
”). Both “
computer
”
and “
laptop computer
” are found to be frequent, whereas “
desktop computer
” is not.
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
Level 1
min_sup
= 5%
computer
[support = 10%]
Level 2
min_sup
= 5%
laptop computer
[support = 6%]
desktop computer
[support = 4%]
Figure 7.3
Multilevel mining with uniform support.
Level 1
min_sup
= 5%
computer
[support = 10%]
Level 2
min_sup
= 3%
laptop computer
[support = 6%]
desktop computer
[support = 4%]
Figure 7.4
Multilevel mining with reduced support.
