There are several variants of the
Apriori algorithm that focus on improving efficiency. For example, the base idea of the
SON algorithm is to partition the database
n partitions. The SON algorithm has several steps:
- In phase I each partition
pigenerates local itemsets of all lengths as the output
Li2, ... ,
- In merge phase the local itemsets of same lengths from all
npartitions are combined to generate the global candidate itemsets.
- In phase II algorithm counts support value of each candidate and generates the global itemsets.
Ussually each partition has its own local mininal support value and is defined by
min_support * number_of_transaction_in_partition, where
min_support is minimal support threshold for transactions in
Now we take an example
D and divide transactions into
n=2 partitions. Global minimal support for Database
min_support=2. Local minimal support for each partition will be
Database D | TID | List of itemsets | |------| ------------------ | | T1 | I1, I2 | | T2 | I3, I4 | | T3 | I1, I5 | | T4 | I2, I6 | | T5 | I1, I2 | | T6 | I3, I4 | | T7 | I1, I7 | | T8 | I2, I8 |
C1 table for partition 1 (local_min_support=2*4) | Itemset | Support count| |------ | -------------- | | I1 | 2 | | I2 | 2 | | I3 | 1 | | I4 | 1 | | I5 | 1 | | I6 | 1 | C1 table for partition 2 (local_min_support=2*4) | Itemset | Support count| |------ | -------------- | | I1 | 2 | | I2 | 2 | | I3 | 1 | | I4 | 1 | | I7 | 1 | | I8 | 1 |
As you can see, the minimum local support in each partition is too high and the frequence 1-itemsets for each partition is empty. However, the frequency 1-itemsets in the database
min_support=2 is not empty.
Can you please tell me what am I doing wrong?
I also find, that local minimum support is
local_min_support=(1/n)*min_support. In this case this local minimal support will work, but in general still not. For example imagine you have Database D where n = 2 and min_support = 10. Then local minimum support for each partition becomes 10/2 = 5. Now we assume that the support_count of an item in partition1 and partition2 is 4 and 4, respectively. Because both support counts in partitions are smaller than locale min support go away, although they are frequent item sets in database D.