0
$\begingroup$

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 D into n partitions. The SON algorithm has several steps:

  • In phase I each partition pi generates local itemsets of all lengths as the output Li1,Li2, ... ,Lil.
  • In merge phase the local itemsets of same lengths from all n partitions 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 D.

Now we take an example D and divide transactions into n=2 partitions. Global minimal support for Database D is min_support=2. Local minimal support for each partition will be local_min_support=2*4.

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 D with 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.