Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
Veenita Gupta1, Neeraj Kumar2, Praveen Kumar3
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
Mining frequent item sets is a fundamental task in data mining. Unfortunately the number of frequent item sets describing the data is often too large to comprehend. This problem has been attacked by condensed representations of frequent item sets that are sub collections of frequent item sets containing only the frequent item sets that cannot be deduced from other frequent item sets in the sub collection, using some deduction rules. Most known frequent item set mining approaches enumerate candidate item sets, determine their support, and prune candidates that fail to reach the user-specified minimum support. Apart from this scheme we can use intersection approach for identifying frequent item set. The closed frequent item sets can be represented as the intersection of some subset of the given transactions.As the transactional database increases, the size of prefix tree also grows which make it difficult to handle. Experiments have been done to find out the efficient memory utilization of prefix tree. An improvement has been suggested to reduce the total number of branches in the prefix tree leading to reduction in its size
INTRODUCTION |
| Data mining is essentially the computer-assisted process of information analysis. It is often the case that large collections of data, however well structured, conceal implicit patterns of information that cannot be readily detected by conventional analysis techniques. Such information may often be usefully analyzed using a set of techniques referred to as Knowledge discovery or data mining. Mining frequent itemsets is an important task in data mining. |
| Most of the approaches enumerate candidate item sets, determine their support, and prune candidates that fail to reach the user-specified minimum support. It can be viewed as a depth-first search in the subset lattice of the item sets. However enumeration approaches worked on “top-down", since they start at the one-element item sets and work their way downward by extending identified frequent item sets by new items. Apart from other schemes we can use intersection approach for identifying frequent item set. But the intersection approach of transaction is the least research area and need attention and improvement to be applied. The main reason why the intersection approach is less researched is that it is often not competitive with the item set enumeration approaches, at least on standard benchmark data sets. Naturally, if there are few items, there are (relatively) few candidate item sets to enumerate and thus the search space of the enumeration approaches is of manageable size. |
| In contrast to this, the more transactions there are, the more work an intersection approach has to do, especially, since it is not linear in the number of transactions like the support computation of the item set enumeration approaches. As the transactional database increases, the size of prefix tree also grows which make it difficult to handle. Hence more time is invested in inserting new transactions and searching intersecting items. To overcome this shortcoming an attempt has been made to make the prefix tree more compact, so as to get the desired information in less time and space. |
Basic Definition: |
| Association rule mining:- Association rule mining[1] is a type of mining used to identify certain kind of association (interconnection relation in term of probability) among the items of database. It aims is to extract interesting correlations, frequent patterns, associations or casual structures among sets of items in the transaction or other data repository. |
 |
| Support: - It specifies the fraction of transactions that contains an item sets. |
| Confidence: - It denotes the measure of trueness of the generated association rule true in probabilistic term. |
| Frequent item set:- A frequent item set is the item set whose support is greater than some user specified minimum support. |
| Closed item set:- A frequent item set is closed if there does not exist a super set that has the same support [2]. |
FREQUENT ITEM SET MINING |
| An important observation while mining frequent item sets is that the output is often huge and it may even exceed the size of the transaction database to mine. As a consequence, there are several approaches that try to reduce the output, if possible without any loss of information. The most basic of these approaches is to restrict the output to so-called closed or maximal frequent item sets [3]. Restricting the output of a frequent item set mining algorithm to only the closed or even only the maximal frequent item sets can sometimes reduce it by orders of magnitude. However, little information is lost: From the set of all maximal frequent item sets the set of all frequent item sets can be reconstructed, since any frequent item set has at least one maximal superset. Therefore the union of all subsets of maximal item sets is the set of all frequent item sets. Closed frequent item sets even preserve knowledge of the support values. The reason is that each frequent item set has a uniquely determined closed superset with the same support. Hence the support of a frequent item set that is not closed can be computed as the maximum of the support values of all closed frequent item sets that contain it (the maximum has to be used, because no superset can have a greater support-the so-called apriori property[4]). As a consequence, closed frequent item sets are the most popular form of compressing the result of frequent item set mining. |
 |
Item Set Enumeration Algorithms: |
| standard approach to find all frequent item sets w.r.t. a given database T and support threshold smin, which is adopted by basically all frequent item set mining algorithms (except those of the Apriori family), is a depth-first search in the subset lattice of the item base B. This approach can be interpreted as a simple divide-and-conquer scheme. For some chosen item i, the problem to find all frequent item sets is split into two subproblems: (1) find all frequent item sets containing the item i and (2) find all frequent item sets not containing the item i. Each subproblem is then further divided based on another item j: find all frequent item sets containing (1.1) both items i and j, (1.2) item i, but not j, (2.1) item j, but not i, (2.2) neither item i nor j, and so on. All subproblems that occur in this divide-and-conquer recursion can be de_ned by a conditional transaction database and a prefix. The prefix is a set of items that has to be added to all frequent item sets that are discovered in the conditional database. Formally, all sub problems are tuples S = (C; P), where C is a conditional transaction database and P is a prefix. The initial problem, with which the recursion is started, is S = (T;âñ÷), where T is the transaction database to mine and the prefix[5] is empty. |
Types of Frequent Item Sets: |
| One of the first observations one makes when mining frequent item sets is that the output is often huge-it may even exceed the size of the transaction database to mine. As a consequence, there are several approaches that try to reduce the output, if possible without any loss of information. for example: |
| Closed Item Set: A frequent item set is called closed if there does not exist a superset that has the same support, or formally |
 |
| From the set of all maximal frequent item sets the set of all frequent item sets can be reconstructed, since any frequent item set has at least one maximal superset. Therefore the union of all subsets of maximal item sets is the set of all frequent item sets. Closed frequent item sets even preserve knowledge of the support values. Note that closed item sets are closely related to perfect extensions: an item set is closed if it does not have a perfect extension. However, using perfect extension pruning does not mean that the output is restricted to closed item sets, because in the search not all possible extension items are considered (conditional databases do not contain all items). |
INTERSECTING TRANSACTIONS |
| We discuss two ways of implementing the intersection approach: enumerating transaction sets as it is done in the Carpenter algorithm [6] and a cumulative scheme [7]. |
Enumerating Transaction Sets: |
| The Carpenter algorithm [6] implements the intersection approach by enumerating sets of transactions (or, equivalently, sets of transaction indices) and intersecting them. Technically, the task to enumerate all transaction index sets is split into two sub-tasks: (1) enumerate all transaction index sets that contain the index 1 and (2) enumerate all transaction index sets that do not contain the index 1. These subtasks are then further divided w.r.t. the transaction index 2: enumerate all transaction index sets containing (1.1) both indices 1 and 2, (1.2) index 1, but not index 2, (2.1) index 2, but not index 1, (2.2) neither index 1 nor index 2, and so on. |
Prefix Tree Implementation: |
| The existing system specifies an intersection approach to find out the closed frequent item set. The core problem of implementing the scheme is to find a data structure for stor-ing the closed item sets that allows us to quickly compute the intersections of these sets with a new transaction and to merge the result with them. A prefix tree implementation is used to serve this purpose. Prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node, instead, its position in the tree defines the key with which it is asso-ciated. All the descendants of a node have a com-mon prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. In the ex-ample shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it. A prefix tree can be seen as a deterministic finite automaton, although the symbol on each edge is often implicit in the order of the branches. |
 |
| It is not necessary for keys to be explicitly stored in nodes. (In the figure, words are shown only to illustrate how the prefix tree works.) Prefix tree need not be keyed by charac-ter string. The same algorithms can easily be adapted to serve similar functions of ordered lists of any construct, e.g., permutations on a list of digits or shapes. In particular, a bitwise prefix tree is keyed on the individual bits making up a short, fixed size of bits such as an integer number or pointer to memory. |
INTERSECTING ALGORITHM |
| In the intersection approach after adding the transaction to the prefix tree we need to perform the intersection of cur-rently added transaction with all the existing transaction in the prefix tree. The proposed algorithm for performing the intersection is defined as:- |
 |
 |
| In more detail, the procedure works as follows: whenever the item in the current sibling equals an item in the transac-tion (that is, whenever trans[i] is true) and thus the item is in the intersection, it is checked whether the sibling list starting at *ins contains a node with this item, because this node has to represent the extended intersection. If such a node exists, its support is updated. For this update the step field and vari-able are vital, because they allow us to determine whether the current transaction was already counted for the support in the node or not. If the value of the step field in the node equals the current step, the node has already been updated and therefore the transaction must be discounted again be-fore taking the maximum. The maximum is taken, because we have to determine the support from the largest set of transactions containing the item set represented by the node. If a node with the intersection item does not exist, a new node is allocated and inserted into the tree at the location indicated by ins. In both cases (with the current item in the transaction or not, that is, with trans[i] true or false) the sub-tree is processed recursively, unless the item of the current node is not larger than the minimum item in the current transaction. The only difference between the recursive calls is that in the case where the current item is in the intersec-tion, the insertion position is advanced to the children of the current node. |
EXPERIMENTS |
| As the transactional database increases, the size of prefix tree also grows which make it difficult to handle. Hence more time is invested in inserting new transactions and searching intersecting items. To overcome this shortcoming an attempt has been made to make the prefix tree more compact, so as to get the desired information in less time and space. An improvement has been suggested to reduce the total number of branches in the prefix tree leading to reduction in its size. |
| So we are suggesting the following steps for making a tree out of transaction database. |
 |
| The database is already taken in increasing order of their initial support value |
 |
| Two parameters have been taken for measuring the prefix tree size and its memory utilization. |
| a. Total Number of Nodes in the Prefix Tree. |
| b. Total Number of Paths Existing In the Prefix Tree. |
RESULTS |
 |
 |
 |
CONCLUSIONS |
| The study and experiments conducted of intersection ap-proach shows that this approach outperforms most of the existing technology in different database. The core of inter-section approach is the prefix data structure that is used to represent the transaction database along with the intersecting item that are also represent in the nodes of prefix tree. The main problem that is associated with this data structure is that the size of the prefix tree. The size of prefix tree grows very large when we process larger number of transac-tion.Smaller prefix tree take less time in searching for any particular node and also makes its handling easier. The main fact behind the reduction in size is that items with higher initial support value have more probability of occurring in intersection Arranging of items within the transaction has effect on the size of prefix tree. Arranging the items in de-creasing order of support value allow the higher support item to exits at the first level in prefix tree. These higher support items exist more often in intersection and while we search for intersecting items in the tree they can be found at first level of prefix tree thus it prevents extra branches to be added in the tree and thus the number of branches in the prefix tree reduces. Hence we conclude that arranging the items according to deceasing initial support value reduces the size of prefix tree. It considerably reduces the total num-ber of branches and nodes in the prefix tree and the effect of this reduction reflect in the total memory utilization of the prefix tree. |
References |
|