What is FP-growth? Discuss FP-growth approach for frequent pattern mining.

-

FP GROWTH

The main Bottlenecks of the Apriori approach are it uses Breadth-first (i.e., level-wise) search and it often generates and tests a huge number of candidates. One possible better alternative approach for the Apriori approach is the FP-Growth approach uses depth-first search and avoids explicit candidate generation. Its Major philosophy is "grow long patterns from short ones using local frequent items only". For example, if "abc" is a frequent pattern then get all transactions having "abc", and find that "d" is a local frequent item in transactions having "abe" then abcd is also a frequent pattern. 

In FP-Growth there are mainly two steps involved first, build a compact data structure called FP-Tree and then, extract frequent itemsets directly from the FP-tree and then, extract frequent itemsets directly from the FP-tree.

1. FP-tree 

Construction from a Transactional DB: FP-Tree is constructed using two passes over the data set:

Pass1:

  • Scan DB to find frequent 1-itemsets as:
  • Scan DB and find support count for each item.
  • Discard infrequent items
  • Sort items in descending order of their frequency (support count). 
  • Sort the items in each transaction in descending order of their frequency. Use this order when building the FP-tree, so common prefixes can be shared.


Pass2:

  •  Scan DB again, construct FP-tree
  • FP-growth reads one transaction at a time and maps it to a path. 
  • Fixed order is used, so path can overlap when transaction share items.
  • Pointers are maintained between nodes containing the same item(dotted line)


2. Mining Frequent Patterns Using FP-tree:

  • Start from each frequent length-1 pattern (called suffix pattern) 
  • Construct its conditional pattern base (set of prefix paths in the FP-tree co-occurring with the suffix pattern)
  • Then construct its conditional FP-tree.
  • The pattern growth is achieved by the concatenation of the suffix pattern with the frequent patterns generated from a conditional FP-tree.

The steps used by the FP-growth approach for FP-tree construction can be expressed in the Flow chart as shown below:




Comments

Post a Comment

Popular posts from this blog

Discuss classification or taxonomy of virtualization at different levels.

-
Image
Taxonomy of virtualization Virtualization is mainly used to emulate the execution environment, storage, and networks. The execution environment is classified into two: – Process-level – implemented on top of an existing operating system.  – System-level – implemented directly on hardware and does not or minimum requirement of the existing operating system. OR,  Virtualization covers a wide range of emulation techniques that are applied to different areas of computing. A classification of these techniques helps us better understand their characteristics and use  V irtualization is mainly used to emulate  ● Execution Environments: To provide support for the execution of the programs eg. OS, and Application.  ○ Process Level: Implemented on top of an existing OS that has full control of the hardware  ○ System Level: Implemented directly on Hardware and do not require support from existing OS.  ● Storage: Storage vi...
Read more

Suppose that a data warehouse for Big-University consists of the following four dimensions: student, course, semester, and instructor, and two measures count and avg_grade. When at the lowest conceptual level (e.g., for a given student, course, semester, and instructor combination), the avg_grade measure stores the actual course grade of the student. At higher conceptual levels, avg_grade stores the average grade for the given combination. a) Draw a snowflake schema diagram for the data warehouse. b) Starting with the base cuboid [student, course, semester, instructor], what specific OLAP operations (e.g., roll-up from semester to year) should one perform in order to list the average grade of CS courses for each BigUniversity student. c) If each dimension has five levels (including all), such as “student < major < status < university < all”, how many cuboids will this cube contain (including the base and apex cuboids)?

-
Image
a) A Snowflake Shema is shown in figure below: b) The specific OLAP operations to be performed: 1. Roll-up on course from course_id to department. 2. Roll-up on a student from student_id to university. 3. Dice on course, student with department ="CS" and university = "biguniversity" 4. Drill-down on a student from the university to student_name. c) N = 4 dimensions The cube will contain 54 = 625 cuboids.
Read more

Suppose that a data warehouse consists of the three dimensions time, doctor, and patient, and the two measures count and charge, where a charge is the fee that a doctor charges a patient for a visit. a) Draw a schema diagram for the above data warehouse using one of the schemas. [star, snowflake, fact constellation] b) Starting with the base cuboid [day, doctor, patient], what specific OLAP operations should be performed in order to list the total fee collected by each doctor in 2004? c) To obtain the same list, write an SQL query assuming the data are stored in a relational database with the schema fee (day, month, year, doctor, hospital, patient, count, charge)

-
Image
Solution: a) Star Schema is shown in the figure below: b) First, we should use the roll-up operation to get the year 2004(rolling-up from the day then month to a year). After getting that, we need to use the slice operation to select (2004). Second, we should use roll-up operation again to get all patients. Then, we need to use the slice operation to select (all). Finally, we get a list of the total fee collected by each doctor in 2004. So, 1. roll up from day to month to year 2. slice for year = “2004” 3. roll up on patient from the individual patient to all 4. slice for patient = “all” 5. get the list of the total fees collected by each doctor in 2004 c) Select doctor, Sum(charge) From fee Where year = 2004 Group by doctor
Read more