For the Partition algorithm, prove that any frequent itemset in the database must appear as a local frequent itemset in at least one partition.
What will be an ideal response?
We can do a proof by contradiction.
Assume M transactions,
N partitions, wlog each contains M/N transactions
frequent itemset I with support S,
where S * M = number of transactions containing I,
We know that since I is a frequent itemset, then S >= min_support
or equivalently, S * M >= min_support * M.
Now assume that I is not frequent within any of the N partitions, Pi,
i.e., the support within a partition Pi is Si which is < min_support, or
equivalently Si * M/N < min_support * M/N.
Hence,
```
(S1 * M/N) + (S2 *M/N) + ... + (SN * M/N) < N * (min_support * M/N)
(S1 * M/N) + (S2 *M/N) + ... + (SN * M/N) < min_support * M
```
This contradicts the fact that the support of itemset I should be
>= min_support or equivalently that the number of transactions containing
I be >= min_support * M.
You might also like to view...
C++11]: Given a built-in array of ints named values, which of the following statements would sort the array?
a. sort(values.begin(), values.end()); b. sort(values.array_begin(), values.array_end()); c. sort(begin(values), end(values)); d. sort(array_begin(values), array_end(values));
The basic form of communication between processes or threads in a microkernel operating system is _________ .
Fill in the blank(s) with the appropriate word(s).
If the useful life of the Data Encryption Standard (DES) was about 20 years (1977–1999), how long do you predict the useful life of the Advanced Encryption System (AES) will be? Justify your answer
What will be an ideal response?
Which of the following statements about the else-if construct is false?
A. The else-if is a multiway selection. B. The else-if is a C construct. C. The else-if is used when the expression is not an integral type. D. The last test in an else-if series concludes with only an else, which is then the default action. E. The else-if should be used only then the same basic expression is being evaluated in the multiway selection.