05-04-2010, 08:20 PM
[attachment=3025]
An Efficient Algorithm for Mining Frequent Patterns
Abstract:
Mining frequent patterns are one of the most important research topics in data mining. The function is to mine the transactional data which describes the behavior of the transaction. In an online business or in an online shopping the customers can purchase items together. Frequent patterns are patterns such as item sets, subsequences or substructures that appear in a data set frequently. Many efficient algorithms were developed based on the data structure and the processing scheme. The mining of most efficient algorithms such as Apriori and FP Growth were implemented here.
In this paper we propose the efficient algorithms (Apriori and FP Growth) used to mine the frequent patterns. The Apriori algorithm generates candidate set during each pass. It reduces the dataset by discarding the infrequent itemsets that do not meet the minimum threshold from the candidate sets. To avoid the generation of candidate set which is expensive the FP Growth algorithm is used to mine the database.
1.1. About the project:
Frequent patterns are patterns such as item sets, subsequences or substructures that appear in a data set frequently. From the transactional database, we can examine the behavior of the products purchased by the customers. For example a set of items Mobile and Sim card that appear frequently as well as together in a transaction set is a frequent item set. Subsequences means if a customer buys a Mobile he must also buy a Sim card and then head phone etc. From the history of the database these transactions are happening sequentially is called sequential patterns. The Substructure refers to different structural forms such as sub graphs, sub trees which may be used along with item sets or sequences. Many of the algorithms were developed for mining the frequent items.
In this paper we propose the efficient algorithms (Apriori and FP Growth) used to mine the frequent patterns. The Apriori algorithm generates candidate set during each pass. It reduces the dataset by discarding the infrequent itemsets that do not meet the minimum threshold from the candidate sets. To avoid the generation of candidate set which is expensive the FP Growth algorithm is used to mine the database. The FP Growth does not generate the candidate set instead it generates an optimized data set that is FP tree from the dataset. The FP tree is mined to construct a conditional database. FP mining processes uses the divide and conquer strategy, so the dataset shrinks and gives us quite small conditional frequent pattern base. From this database the frequent patterns are generated.
Existing system:
Traditional system based on the manual calculation and dynamic counting method. Very difficult to find frequent patterns from the large transaction using manual calculation. Dynamic Item set counting method contains very complex procedure. So it is difficult to implement. DIC (Dynamic Item set Counting) algorithm which uses more database scan, presents a new approach for finding large item sets. Aim of the DIC algorithm is improving the performance and eliminating repeated database scan. DIC algorithm divides the database into partitions ( intervals M ) and use a dynamic counting strategy. DIC algorithm determines some stop points for item set counting. Any appropriate points, during the database scan, stopping counting, then starts to count with another item sets.
Disadvantages:
¢ Time requirement is high.
¢ User interaction is not efficient.
¢ Very difficult to process the large transaction.
¢ It require manual calculation.
¢ Very complex to implement.
Proposed System:
we propose the efficient algorithms used to mine the frequent patterns.
1. Apriori Algorithm.
2. FP Growth .
The Apriori algorithm is the most popular association rule algorithm. Apriori
uses bottom up search. FP-Growth is an algorithm for generating frequent item sets for association rules. This algorithm compresses a large database into a
compact, frequent pattern“ tree (FP tree) structure. we analysis the time requirement between two algorithms. And make suggestion which one is efficient.
Advantages:
DIC (Dynamic Itemset Counting) is much slower than every other
algorithm for the real -dataset. The propose system very fast.
FP growth even has the advantage that the transaction database need not
be loaded in ever time.
Very fast compare than existing system.
Candidate key generation is minimum when using FP growth.
Problem Definition and Description:
Mining frequent patterns in transactional databases, relational databases, data warehouses, flat files, data streams, advanced database systems include object relational databases and specific application oriented databases such as spatial databases, time series database, text database and multimedia databases have been studied popularly in data mining research
A fundamental problem in data mining is the process of finding frequent patterns in large datasets. Frequent item sets play an essential role in many data mining tasks that try to find interesting patterns from databases, such as association rules, correlations, sequences, episodes, classifiers, clusters and many more of which the mining of association rules is one of the most popular problems.
data mining system can generate thousands or even millions of patterns or rules. All patterns generated by the system are not meaningful. An interesting pattern represents knowledge. There are several objective measures exist based on the structure of discovered patterns and statistics. Mining Frequent Patterns leads to the discovery of interesting association and correlations within data. If a marketing manager would like to determine which items are purchased together in the same transactions.
Modules:
This project contains following modules,
Authentication.
Making Transaction.
Apriori Implementation.
FP Growth Tree Generation.
Comparison.
a. Authentication:
This module is used to verify the access permission. If user name and password is correct then we can access the main project.
2 Making Transaction:
Through this module we can make the transaction. Each transaction correctly observed and stored into database. These values are used to find out the frequent items.
Steps in transaction:
1. First set the number of total items in the list.
2. Make the transaction and select the items from list.
3. Save the transaction.
4. Complete the transaction.
3 Apriori Implementation:
This modules generates the frequent patterns based on apriori
algorithm. Execution time of the algorithm this algorithm is noted for the future comparison purpose.
Developed by Agrawal and Srikant 1994 Innovative way to find association rules on large scale, allowing implication outcomes that consist of more than one item Based on minimum support threshold
Apriori algorithm works as follows:
¢ The first step, Apriori algorithm generates Candidate 1 “ item sets.
Then, item sets count and minimum support value are compared to find
the set L1 (frequent item sets).
¢ The second step, algorithm use L1 to construct the set C2 of
Candidate 2 “ item sets. The process is finished when there are no more
candidates.
4. FP Growth Tree Generation:
This modules generates the frequent patterns based on FP growth
Algorithm. And also it generates the FP Tree to find out the frequent patterns. The FP-growth algorithm is currently one of the fastest approaches to frequent item set mining. It is based on a prefix tree representation of the given database of transactions (called an FP-tree), which can save considerable amounts of memory for storing the transactions.
FP-Growth is an algorithm for generating frequent item sets for association rules. This algorithm compresses a large database into a compact, frequent pattern“ tree (FP tree) structure. FP “ tree structure stores all necessary information about frequent itemsets
in a database.
. A frequent pattern tree (or FP-tree in short) is defined as
1. The root labeled with null and set of items as the children of the root.
2. Each node contains of three fields: item-name (holds the frequent item), count (number of transactions that share that node), and node- page link (next node in the FP-tree).
3. Frequent-item header table contains two fields, item-name and head of node page link (points to the first node in the FP-tree holding the item).
5. Comparison:
This modules generates the bar chart to differentiate the execution time of
the two algorithms. Through this module we can easily differentiate the two algorithms.
System Analysis:
Packages Selected:
Front End: Net Beans-IDE 6.7, JDK 1.6
Back End: MS SQl.
HARDWARE CONFIGURATION:
System : HCL
Processor : Pentium IV
Processor Speed : 2.80GHz
Main Storage : 512MB RAM
Hard Disk Capacity : 80GB
Floppy Disk Drive : 1.44MB
CD-ROM Drive : LG 52X Reader
Keyboard : 104 Keys
Mouse : Logitech
Monitor : Samsung 17 Color
SOFTWARE CONFIGURATION
Operating System : Windows XP
Front end : Java
Back end : SQL server
Feasibility Study:
We develop the final graphical interactive user interface implementation using Java technology with applets. The similarity between the algorithms and the final applications is the implementation of algorithm logic. The source code of project was highly reusable for the final graphical application. The major difference between the two algorithms is the interactive nature of the final application. In the prototype, besides getting input parameters and transaction data, there is hardly any user interaction. While in the final graphical application, it provides ample user interactions as users can step forward and backward with the algorithm processing steps. Users can also play around with various graphical components during certain algorithm data processing step, for instance, change the placement of an object in the illustration screen. Our major design considerations include: simple and consistent presentation background, multiple algorithms comparison, reusability of design/source code, and setting limitations on user input.
Software Features
Java:
Java is a new computer programming language developed by Sun Microsystems. Java has a good chance to be the first really successful new computer language in several decades. Advanced programmers like it because it has a clean, well-designed definition. Business likes it because it dominates an important new application, Web programming.
Java has several important features:
¢ A Java program runs exactly the same way on all computers. Most other languages allow small differences in interpretation of the standards.
¢ It is not just the source that is portable. A Java program is a stream of bytes that can be run on any machine. An interpreter program is built into Web browsers, though it can run separately. Java programs can be distributed through the Web to any client computer.
¢ Java applets are safe. The interpreter program does not allow Java code loaded from the network to access local disk files, other machines on the local network, or local databases. The code can display information on the screen and communicate back to the server from which it was loaded.
A group at Sun reluctantly invented Java when they decided that existing computer languages could not solve the problem of distributing applications over the network. C++ inherited many unsafe practices from the old C language. Basic was too static and constrained to support the development of large applications and libraries.
Today, every major vendor supports Java. Netscape incorporates Java support in every version of its Browser and Server products. Oracle will support Java on the Client, the Web Server, and the Database Server. IBM looks to Java to solve the problems caused by its heterogeneous product line.
The Java programming language and environment is designed to solve a number of problems in modern programming practice. It has many interesting features that make it an ideal language for software development. It is a high-level language that can be characterized by all of the following buzzwords:
Features
Sun describes Java as
Simple
Object-oriented
Distributed
Robust
Secure
Architecture Neutral
Portable
Interpreted
High performance
Multithreaded
Dynamic.
¢ Java is simple.
What it means by simple is being small and familiar.Sun designed Java as closely to C++ as possible in order to make the system more comprehensible, but removed many rarely used, poorly understood, confusing features of C++. These primarily include operator overloading, multiple inheritance, and extensive automatic coercions. The most important simplification is that Java does not use pointers and implements automatic garbage collection so that we don't need to worry about dangling pointers, invalid pointer references, and memory leaks and memory management.
¢ Java is object-oriented.
This means that the programmer can focus on the data in his application and the interface to it. In Java, everything must be done via method invocation for a Java object. We must view our whole application as an object; an object of a particular class. .
¢ Java is distributed.
Java is designed to support applications on networks. Java supports various levels of network connectivity through classes in java. net. For instance, the URL class provides a very simple interface to networking. If we want more control over the downloading data than is through simpler URL methods, we would use a URLConnection object which is returned by a URL URL.openConnection() method. Also, you can do your own networking with the Socket and ServerSocket classes.
¢ Java is robust.
Java is designed for writing highly reliable or robust software. Java puts a lot of emphasis on early checking for possible problems, later dynamic (runtime) checking, and eliminating situations that are error prone. The removal of pointers eliminates the possibility of overwriting memory and corrupting data.
¢ Java is secure.
Java is intended to be used in networked environments. Toward that end, Java implements several security mechanisms to protect us against malicious code that might try to invade your file system. Java provides a firewall between a networked application and our computer.
¢ Java is architecture-neutral.
Java program are compiled to an architecture neutral byte-code format. The primary advantage of this approach is that it allows a Java application to run on any system that implements the Java Virtual Machine. This is useful not only for the networks but also for single system software distribution. With the multiple flavors of Windows 95 and Windows NT on the PC, and the new PowerPC Macintosh, it is becoming increasing difficult to produce software that runs on all platforms.
¢ Java is portable.
The portability actually comes from architecture-neutrality. But Java goes even further by explicitly specifying the size of each of the primitive data types to eliminate implementation-dependence. The Java system itself is quite portable. The Java compiler is written in Java, while the Java run-time system is written in ANSI C with a clean portability boundary.
¢ Java is interpreted.
The Java compiler generates byte-codes. The Java interpreter executes the translated bytecodes directly on system that implements the Java Virtual Machine. Java's linking phase is only a process of loading classes into the environment.
¢ Java is high-performance.
Compared to those high-level, fully interpreted scripting languages, Java is high-performance. If the just-in-time compilers are used, Sun claims that the performance of byte-codes converted to machine code are nearly as good as native C or C++. Java, however, was designed to perform well on very low-power CPUs.
¢ Java is multithreaded.
Java provides support for multiple threads of execution that can handle different tasks with a Thread class in the java.lang Package. The thread class supports methods to start a thread, run a thread, stop a thread, and check on the status of a thread. This makes programming in Java with threads much easier than programming in the conventional single-threaded C and C++ style.
¢ Java is dynamic.
Java language was designed to adapt to an evolving environment. It is a more dynamic language than C or C++. Java loads in classes, as they are needed, even from across a network. This makes an upgrade to software much easier and effectively. With the compiler, first we translate a program into an intermediate language called Java bytecodes ---the platform-independent codes interpreted by the interpreted on the Java platform. The interpreter parses and runs each Java bytecode instruction on the computer. Compilation happen s just once; interpretation occurs each time the program is executed.
Java bytecodes can be thought as the machine code instructions for the Java Virtual Machine (JVM). Every Java interpreter, whether itâ„¢s a development tool or a web browser that can run applets, is an implementation of the Java Virtual Machine.
The Java Platform
A platform is the hardware or software environment in which a program runs. Most Platforms can be described as a combination of the operating system and hardware. The Java platform differs from most other platforms in that it™s software “only platform that runs on top of other hardware-based platforms.
The Java platform has two components:
1. The Java Virtual Machine (JVM).
2. The Java Application Programming Interfaces (Java API).
The JVM has been explained above. Itâ„¢s the base for the Java platform and is ported onto various hardware-based platforms.
The Java API is a large collection of ready-made software components that provide many useful capabilities, such as graphical user interface (GUI). The Java API is grouped into libraries of related classes and interfaces; these libraries are known as packages.
Native code is code that after you compile it, the compiled code runs on a specific hardware platform. As a platform-independent environment, the Java platform can be bit slower than native code. However, smart compilers, well-tuned interpreters, and just-in-time bytecode compilers can bring performance close to that of native code without threatening portability.
SYSTEM ANALYSIS
In this chapter, concepts associated with term structured system and how
they are implemented in the project has been dealt with the tools used for structure
system analysis are,
¢ Data Flow Diagram
3.1 ENVIRONMENTAL MODEL
The Environmental model defines the interfaces between the system and the environment. Building an environmental model is the first and the most important part of building complete model of user requirements. The critical aspect of environmental model is to identify the events occurring in the environment to which the system must respond. It also defines the boundary between the system and the environment.
3.2 BEHAVIOURAL MODEL:
A system flow diagram is a pictorial representation of the working of the system. It is a tool that depicts the flow of data through a system and the work processing performed by that system. This takes an important role in the system analysis part to know the present level of existing system and what modification is to be done to overcome the problem occurring in the system. It is the starting point of the design phase that functionally decomposed the requirement. A system flow diagram consists of a series of rectangles joined by lines. The rectangles represents data transformation and lines represent data flow in those systems. A data flow diagram describes data flow rather than how they are proposed.
TESTING AND IMPLEMENTATION SYSTEM DESIGN:
System design is the process of planning a new system to complement or altogether replace the old system. The purpose of the design phase is the first step in moving from the problem domain to the solution domain. The design of the system is the critical aspect that affects the quality of the software. System design is also called top-level design. The design phase translates the logical aspects of the system into physical aspects of the system.
3.2 INPUT DESIGN
Input design is one of the most important phase of the system design. Input design is the process where the input received in the system are planned and designed, so as to get necessary information from the user, eliminating the information that is not required. The aim of the input design is to ensure the maximum possible levels of accuracy and also ensures that the input is accessible that understood by the user.
The input design is the part of overall system design, which requires very careful attention. if the data going into the system is incorrect then the processing and output will magnify the errors.
The objectives considered during input design are:
¢ Nature of input processing.
¢ Flexibility and thoroughness of validation rules.
¢ Handling of properties within the input documents.
¢ Screen design to ensure accuracy and efficiency of the input relationship with files.
¢ Careful design of the input also involves attention to error handling, controls, batching and validation procedures.
Input design features can ensure the reliability of the system and produce result from accurate data or they can result in the production of erroneous information. The input design of the system includes the following
Form Design:
Existing Database:
New Database
Comparison results of two algorithms:
Coding:
Code:
package mining;
/**
*
* @author admin
*/
public class main extends javax.swing.JFrame {
/** Creates new form main */
public main() {
initComponents();
}
/** This method is called from within the constructor to
* initialize the form.
* WARNING: Do NOT modify this code. The content of this method is
* always regenerated by the Form Editor.
*/
@SuppressWarnings("unchecked")
// <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents
private void initComponents() {
jPanel1 = new javax.swing.JPanel();
jLabel1 = new javax.swing.JLabel();
jLabel2 = new javax.swing.JLabel();
jLabel3 = new javax.swing.JLabel();
setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
setBounds(new java.awt.Rectangle(200, 150, 0, 0));
jPanel1.setBackground(new java.awt.Color(204, 255, 204));
jLabel1.setFont(new java.awt.Font("Script MT Bold", 1, 24)); // NOI18N
jLabel1.setForeground(new java.awt.Color(255, 153, 153));
jLabel1.setText(" Mining Frequent Patterns");
jLabel2.setFont(new java.awt.Font("Tahoma", 3, 15)); // NOI18N
jLabel2.setForeground(new java.awt.Color(255, 51, 51));
jLabel2.setText("Existing Database");
jLabel2.addMouseListener(new java.awt.event.MouseAdapter() {
public void mouseClicked(java.awt.event.MouseEvent evt) {
jLabel2MouseClicked(evt);
}
});
jLabel3.setFont(new java.awt.Font("Tahoma", 3, 15)); // NOI18N
jLabel3.setForeground(new java.awt.Color(255, 51, 51));
jLabel3.setText("New Database");
jLabel3.addMouseListener(new java.awt.event.MouseAdapter() {
public void mouseClicked(java.awt.event.MouseEvent evt) {
jLabel3MouseClicked(evt);
}
});
javax.swing.GroupLayout jPanel1Layout = new javax.swing.GroupLayout(jPanel1);
jPanel1.setLayout(jPanel1Layout);
jPanel1Layout.setHorizontalGroup(
jPanel1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
.addGroup(jPanel1Layout.createSequentialGroup()
.addGroup(jPanel1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
.addGroup(jPanel1Layout.createSequentialGroup()
.addGap(195, 195, 195)
.addComponent(jLabel3, javax.swing.GroupLayout.PREFERRED_SIZE, 117, javax.swing.GroupLayout.PREFERRED_SIZE))
.addGroup(jPanel1Layout.createSequentialGroup()
.addGap(185, 185, 185)
.addComponent(jLabel2, javax.swing.GroupLayout.PREFERRED_SIZE, 138, javax.swing.GroupLayout.PREFERRED_SIZE))
.addGroup(jPanel1Layout.createSequentialGroup()
.addGap(84, 84, 84)
.addComponent(jLabel1, javax.swing.GroupLayout.PREFERRED_SIZE, 327, javax.swing.GroupLayout.PREFERRED_SIZE)))
.addContainerGap(114, Short.MAX_VALUE))
);
jPanel1Layout.setVerticalGroup(
jPanel1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
.addGroup(jPanel1Layout.createSequentialGroup()
.addGap(24, 24, 24)
.addComponent(jLabel1, javax.swing.GroupLayout.PREFERRED_SIZE, 27, javax.swing.GroupLayout.PREFERRED_SIZE)
.addGap(63, 63, 63)
.addComponent(jLabel2, javax.swing.GroupLayout.PREFERRED_SIZE, 22, javax.swing.GroupLayout.PREFERRED_SIZE)
.addGap(36, 36, 36)
.addComponent(jLabel3)
.addContainerGap(172, Short.MAX_VALUE))
);
javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());
getContentPane().setLayout(layout);
layout.setHorizontalGroup(
layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
.addComponent(jPanel1, javax.swing.GroupLayout.Alignment.TRAILING, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
);
layout.setVerticalGroup(
layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
.addComponent(jPanel1, javax.swing.GroupLayout.Alignment.TRAILING, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
);
pack();
}// </editor-fold>//GEN-END:initComponents
private void jLabel2MouseClicked(java.awt.event.MouseEvent evt) {//GEN-FIRST:event_jLabel2MouseClicked
// TODO add your handling code here:
new Exist().setVisible(true);
this.setVisible(false);
}//GEN-LAST:event_jLabel2MouseClicked
private void jLabel3MouseClicked(java.awt.event.MouseEvent evt) {//GEN-FIRST:event_jLabel3MouseClicked
// TODO add your handling code here:
new main1().setVisible(true);
this.setVisible(false);
}//GEN-LAST:event_jLabel3MouseClicked
/**
* @param args the command line arguments
*/
public static void main(String args[]) {
java.awt.EventQueue.invokeLater(new Runnable() {
public void run() {
new main().setVisible(true);
}
});
}
// Variables declaration - do not modify//GEN-BEGIN:variables
private javax.swing.JLabel jLabel1;
private javax.swing.JLabel jLabel2;
private javax.swing.JLabel jLabel3;
private javax.swing.JPanel jPanel1;
// End of variables declaration//GEN-END:variables
}Testing is a series of different tests that whose primary purpose is to fully exercise the computer based system. Although each test has a different purpose, all work should verify that all system element have been properly integrated and performed allocated function. Testing is the process of checking whether the developed system works according to the actual requirement and objectives of the system.
The philosophy behind testing is to find the errors. A good test is one that has a high probability of finding an undiscovered error. A successful test is one that uncovers the undiscovered error. Test cases are devised with this purpose in mind. A test case is a set of data that the system will process as an input. However the data are created with the intent of determining whether the system will process them correctly without any errors to produce the required output.
Types of Testing:
¢ Unit testing
¢ Integration testing
¢ Validation testing
¢ Output testing
¢ User acceptance testing
unit Testing
All modules were tested and individually as soon as they were completed and were checked for their correct functionality.
Integration Testing
The entire project was split into small program; each of this single programs gives a frame as an output. These programs were tested individually; at last all these programs where combined together by creating another program where all these constructors were used. It give a lot of problem by not functioning is an integrated manner.
The user interface testing is important since the user has to declare that the arrangements made in frames are convenient and it is satisfied. when the frames where given for the test, the end user gave suggestion. Based on their suggestions the frames where modified and put into practice.
Validation Testing:
At the culmination of the black box testing software is completely assembled as a package. Interfacing errors have been uncovered and corrected and a final series of test i.e., Validation succeeds when the software function in a manner that can be reasonably
accepted by the customer.
Output Testing
After performing the validation testing the next step is output testing of the proposed system. Since the system cannot be useful if it does not produce the required output. Asking the user about the format in which the system is required tests the output displayed or generated by the system under consideration. Here the output format is considered in two ways. one is on screen and another one is printed format. The output format on the screen is found to be corrected as the format was designed in the system phase according to the user needs. And for the hardcopy the output comes according to the specifications requested by the user.
IMPLEMENTATION
System implementation is stage in the project where the theoretical design is turned into the working system. The most crucial stage is giving the users confidence that the new system will work effectively and efficiently.
The performance of reliability of the system is tested and it gained acceptance. The system was implemented successfully. Implementation is a process that means converting a new system in to operation.
Proper implementation is essential to provide a reliable system to meet organization requirements. During the implementation stage a live demon was undertaken and made in front of end-users. The various features provided in the system were discussed during implementation
1. Apriori Algorithm:
The Apriori Algorithms an influential algorithm for mining frequent item sets for boolean association rules. In computer science and data mining, Apriori is a classic algorithm for learning association rules. Apriori is designed to operate on databases containing transactions (for example, collections of items bought by customers, or details of a website frequentation). The algorithm attempts to find subsets which are common to at least a minimum number C (the cutoff, or confidence threshold) of the item sets.
Input: A transaction database D and a minimum threshold value.
Output: Its frequent itemsets.
Method: Candidate set that contains frequent patterns are generated in the following steps:
1. Scan D for count of each candidate that generates candidate set C1.
2. From C1 check the support count whose support count is less than
minimum support. If it is discard it from C1 and form L1.
3. Generate C2 from L1 joins with itself
4. Repeat step 2 and 3 for further candidate sets until the join results in null.
Disadvantages of Apriori Algorithm:
1. It requires more times.
2. Large set of candidate key generation.
3. Require many database scans.
4. Large memory requirement.
2. FP growth:
The FP-growth algorithm is currently one of the fastest approaches to frequent item set mining. It is based on a prefix tree representation of the given database of transactions (called an FP-tree), which can save considerable amounts of memory for storing the transactions. The basic idea of the FP-growth algorithm can be described as a recursive elimination scheme: in a preprocessing step delete all items from the transactions that are not frequent individually, i.e., do not appear in a user-specified minimum number of transactions. Then select all transactions that contain the least frequent item (least frequent among those that are frequent) and delete this item from them.
Advantages of FP-Growth:
Only 2 passes over data-set
Compresses data-set
No candidate generation
Much faster than Apriori
Conclusion:
We have proposed the implementation of efficient algorithms to find frequent patterns. The Apriori algorithm scans the dataset repeatedly whereas the FP growth avoids the costly candidate set procedure and generates the highly condensed database called as FP tree. Our implementation shows that the FP Growth method is efficient for mining frequent patterns and it is an order of magnitude faster than Apriori algorithm.
