Explain APRIORI ALGORITHM.

-

 APRIORI ALGORITHM

  • Apriori algorithm was the first algorithm that was proposed for frequent itemset mining. It was later improved by R Agarwal and R Srikant and came to be known as Apriori. This algorithm uses two steps "join" and "prune" to reduce the search space. It is an iterative approach to discover the most frequent itemsets.
  • Apriori algorithm is a candidate generation & test approach for frequent itemset generation. It is based on the Apriori principle. Apriori principle states that "If there is any item set which is infrequent, its superset should not be generated or tested". 
  • Therefore, the Apriori algorithm initially, scan the transaction dataset once to get candidate 1-itemset and then frequent 1-itemsets, generate length (k+1) candidate itemset from length k frequent itemset, test the candidates against transaction dataset to filter frequent itemset from infrequent itemsets present in candidate itemset, this process terminates when no frequent or candidate set can be generated.

The steps followed in the Apriori Algorithm of data mining are

Input:

- Transaction database D

- Minimum support count threshold

Output:

F frequent itemset of size k in D.

Join Step: This step generates (K+1) itemset from K-itemsets by joining each item with itself.

 Prune Step: This step scans the count of each item in the database. If the candidate item does not meet minimum support, then it is regarded as infrequent and thus it is removed. This step is performed to reduce the size of the candidate itemsets.

Method



Apriori Algorithm: Finding Frequent Itemsets by Confined Candidate Generation

Apriori is a seminal algorithm proposed by R. Agrawal and R. Srikant in 1994 for mining frequent itemsets for Boolean association rules [AS94b]. The name of the algorithm is based on the fact that the algorithm uses prior knowledge of frequent itemset properties, as we shall see later. Apriori employs apr iterative approach known as a level-wise search, where k-itemsets are used to explore (k+1)-itemsets. First, the set of frequent 1-itemsets is found by scanning the database to accumulate the count for each item and collecting those items that satisfy minimum support. The resulting set is denoted by L₁. Next, Li is used to find L2, the set of frequent 2-itemsets, which is used to find L3, and so on, until no more frequent k-itemsets can be found. The finding of each Lk requires one full scan of the database.

To improve the efficiency of the level-wise generation of frequent itemsets, an important property called the Apriori property is used to reduce the search space.



Comments

Post a Comment

Popular posts from this blog

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 four dimensions; date, spectator, location, and game, and the two measures, count and charge, where charge is the fee that a spectator pays when watching a game on a given date. Spectators may be students, adults, or seniors, with each category having its own charge rate. a) Draw a star schema diagram for the data b) Starting with the base cuboid [date; spectator; location; game], what specific OLAP operations should perform in order to list the total charge paid by student spectators at GM Place in 2004?

-
Image
  b) The specific OLAP operations to be performed are: 1. Roll-up on date from date id to year. 2. Roll-up on spectator from spectator id to status. 3. Roll-up on location from location id to location name. 4. Roll-up on the game from game id to all. 5. Dice with status= “students”, location name= “GM Place”, and year=2004
Read more

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