Downward closure property(Apriori) of frequent patternsApriori : Every subset of a frequent itemset must be frequent.

Efficient mining methodology :
If any of the subset of an itemset S is infrequent then there is no way the S is a frequent itemset.

Aprioti Pruning principle:
If an itemset is not frequent then it's superset should not even be generated.

We have three mining methods :
1.Level wise, join based approach : Apriori
2.Vertical data format : ECLAT
3.Frequent pattern projection and growth : FPgrowth

Apriori Algorithm:
The name is because the algorithm uses the knowledge of the prior frequent itemsets.
It is a level wise,candidate generation and test approach.

OUTLINE OF THE ALGORITHM:
Initially generate all the frequent 1item frequent itemset.
Then run a loop on the database for generation of k+1 length frequent itemset using the knowledge about the frequent k length item set.
Then again increase the length by one and repeat the above procedure until no more frequent itemset can be generated.

Then there was the pseudo code.
The concrete implementation is given as :
1.self joining Fk(the frequent itemsets), joining 1 item which is part of the frequent k-1 length item set is joined to items of L(k-1)
2.pruning, it is used to lessen the candidate items by checking the frequency support with the help of hash table.

Improvements in apriori:
-Reduce number of passes through the database.
1. Partitioning method
2.Dynamic item set counting

-Shrink the number of candidates
1.Hashing. Interesting for mining max patterns.
2.Pruning by supporting lower bounding.
3.Sampling

-Explore special data structures
1.Tree projection
2.H-tree
3.Hypercube decomposition
A new tree structure called fptree will be seen.

Partitioning method: Scan database only twice.
This method guarantees that you only need to scan data twice before all the case.
Theorem:Any itemset that is frequent in the transactional database must be frequent in atleast one of the partitioned databases.

1.The first scan is used to partition the database into k databases.
How to partition?
Partition such that each part fits into the main memory. Because no matter how you scan them you will not involve any database i/o.
And then you can use it to derive k frequent items.We can derive all the local frequent item sets.
2.Using the theorem above the second scan can be done such that any candidate set that is frequenting in any one of the partitioned database will also be a global candidate set for frequent item set. Then you add these and find the global frequent data sets.

Direct hashing and pruning:
DHP is a method used to reduce the number of candidates.
The observation is: if the k- item set is frequent then in the hashing bucket,it must be containing several potential item sets that must be frequent.
So if hash count is not frequent then, any one of them will not be frequent. So while we are counting the 1 item set things, the two item set hash table is set up, and we can also cut entries from the two item set hash table by looking at the frequency supports and removing entries hence making the hash table shorter.

ECLAT:
This method is called equivalence class transformation.
a depth first search algo using set intersection. The original data format is horizontal.
Then in here we transform this horizontal data format into vertical data format.item and tid getting interchanged.
In the vertical list, to find the tid list of a k item list an intersection of their respective tid's is performed.and if the item contains sufficient numbers of transactions then they are frequent or else they are infrequent.

Properties of tid lists -
1. If tid's of two item lists are equivalent then they are happening at the same time.
2. If transaction id of one item is the subset of the transaction id of another item then the bigger one always happens when the smaller set happens.
3. To derive frequent patterns based on vertical intersections it is used.
4. We use diffset to accelarate the mining

Diffset -

Each item will have a huge number of transaction id's associated. So diffset is a better method because the intersection can be large, so we write the difference as that will be smaller and eat up lesser storage.

FPGrowth -
It is mining pattern by pattern growth.
Method -
Find frequent single items and partition the database based on each such items.
Then recursively grow frequent patterns by doing the above for each partitioned database(also called conditional database).
To facilitate efficient processing we use the a new data structure called FP-tree.
So mining becomes -
Recursively construct and mine the conditional FP-trees, until the resulting FP-tree is empty or until it contains only one path- single path will generate all the combinations of its sub paths, each of which is a frequent pattern.

How to construct FP-tree from a transactional database?
1.Scan DB to find the single item frequent pattern.
2.Sort frequent items in frequency descending list.
3.Scan DB again, create FP-tree.

The tree's leaves or parts of leaves are also assigned the support.

How to mine this tree?
To mine this tree we can use divide and conquer and do it recursively.
Then we can also find out conditional support of patterns.Like support of patterns containing p or support of pattern containing m but not p.
Based on this tree we can find out transformed prefix paths and their respective supports too. This is the conditional pattern base that we are talking about.

For each conditional pattern base, we,
- mine single item patterns.
- Construct its FP-tree and mine it.

When there is a shared single prefix path P, two things can happen
- Reduction of single prefix path into one node.Concatenation of mining results of the two parts.

Scaling FP-growth by database projection.
This is used when the database can not fit into the main memory.
- Project the DB based on the patterns ,based on single itemset.
- Then we can construct and mine FP-tree for each projected database.

Parallel projection vs. Partition projection.

Parallel Projection -
Project the database on each frequent items.
This means, take an item f4 and project the items which are same or more frequent than it.
It is space costly but all partitions can be processed in parallel.
Partition Projection -
Partition the database in order.Here we pass the unprocessed parts to subsequent partitions so that the items related to a single transaction
are not repeated and so it ain't space costly.

Closet+
For mining closed patterns.

ITEMSET MERGING -
If Y appears in every occurrence of X, then Y is merged with X.
There are many other tricks like -
-Hybrid tree projection
-Bottom up physical tree projection
-Top Down pseudo tree projection
-Sub-itemset pruning
-item skipping
-Efficient subset checking

	Created by NIVEDITA RAO almost 9 years ago

Computer Science (Data mining ) Note on pattern discovery, created by NIVEDITA RAO on 12/06/2017.