 Open Access
 Total Downloads : 241
 Authors : Dr.P.Raguraman, Mr.S.Hariharan, Mr.V.Raji
 Paper ID : IJERTV2IS90330
 Volume & Issue : Volume 02, Issue 09 (September 2013)
 Published (First Online): 14092013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Novel Approach for Scalability – Two Way Sequential Pattern Mining using UDDAG
Vol. 2 Issue 9, September – 2013
Dr.P.Raguraman Assistant Professor
Department of Computer Science
Mr.S.Hariharan Assistant Professor
Department of Computer Science
Mr.V.Raji
Assistant Professor
Department of Computer Science
Sri Sankara Arts and Science College Sri Sankara Arts and Science CollegeeSri Sankara Arts and Science Collegee
Enathur, Kanchipuram, TN, India
Enathur, Kanchipuram, TN, India
Enathur, Kanchipuram, TN, India
AbstractTraditional pattern growthbased approaches for sequential pattern mining derive length (k + 1) patterns based on the projected databases of lengthk patterns recursively. At each level of recursion, they unidirectionally grow the length of detected patterns by one along the suffix of detected patterns, which needs k levels of recursion to find a lengthk pattern. In this paper, a novel data structure, UpDown Directed Acyclic Graph (UDDAG), is invented for efficient sequential pattern mining.
UDDAG allows
bidirectional pattern growth along both ends of detected patterns. Thus, a lengthk pattern can be detected in  log2 k + 1 levels of recursion at best, which results in fewer levels of recursion and faster pattern growth. When minSup is large such that the average pattern length is close to 1, UDDAG and PrefixSpan have similar performance because the problem degrades into frequent item counting problem. However, UDDAG scales up much better. It often outperforms PrefixSpan by almost one order of magnitude in scalability tests. UDDAG is also considerably faster than Spade and LapinSpam. Except for extreme cases, UDDAG uses comparable memory to that of PrefixSpan and less memory than Spade and LapinSpam. Additionally, the special feature of UDDAG enables its extension toward applications involving searching in large spaces.
Index TermsData mining algorithm, directed acyclic graph, performance analysis, sequential pattern, transaction database.
1 INTRODUCTION
SEQUENTIAL pattern mining is an important data mining problem, which detects frequent
subsequences in a sequence database. A major technique for sequential pattern mining is pattern growth. Traditional pattern growth based approaches(e.g., PrefixSpan) derive length(k + 1) patterns based on the projected databases of a lengthk pattern recursively. At each level of recursion, the length of detected patterns is grown by 1, and patterns are grown unidirectionally along the suffix direction. Consequently, we need k levels of recursion to mine a lengthk pattern, which is expensive due to the large number of recursive database projections. In this paper, a new approach based on UpDown Directed Acyclic Graph (UDDAG) is proposed for fast pattern growth. UDDAG is a novel data structure, which supports bidirectional pattern growth from both ends of detected patterns. With UDDAG, at level i recursion, wemay grow the length of patterns by 2i_1 at most. Thus, a lengthk pattern can be detected in  log2 k + 1 levels of recursion at minimum, which results in better scaleup property for UDDAG compared to PrefixSpan. Our extensive experiments clearly demonstrated the strength of UDDAG with its bidirectional pattern growth strategy. When minSup is very large such that the average length of patterns is very small (close to 1), UDDAG and PrefixSpan have similar performance because in this case,
the problem degrades into a basic frequent item counting problem. However, UDDAG
scales up much better compared to
similar to GSP except
Vothl. a2 tIssueth9,eSeptember – 2013
PrefixSpan. It often outperforms PrefixSpan by one order of magnitude in our scalability tests. UDDAG is also considerably faster than two other representative algorithms, Spade and LapinSpam. Except for some extreme cases, the memory usage of UDDAG is comparable to that of PrefixSpan. UDDAG generally uses less memory than
Spade and LapinSpam. UDDAG may be extended to other areas where efficient
searching in large searching spaces is necessary.
Related Work
The problem of sequential pattern mining was introduced by Agrawal and Srikant [1]. Among the many algorithms proposed to solve the problem, GSP [17] and PrefixSpan[13], [14] represent two major types of approaches: a prioribased and pattern growth based.A priori principle states that any supersequence of a nonfrequent sequence must not be frequent. A prioribased approaches can be considered as breadthfirst traversal algorithms because they construct all lengthk patterns before constructing length(k+1) patterns. The AprioriAll algorithm [1] is one of the earliest a prioribased approaches. It first finds all frequent item sets, transforms the database so that each transaction is replaced by all frequent item sets it contains, and then finds patterns. The GSP algorithm [16] is an improvement over AprioriAll.To reduce candidates, GSP only creates a new lengthk candidate when there are two frequent length(k _ 1) sequences with the prefix of one equal to the suffix of the other. To test whether a candidate is a frequent lengthk
pattern, the support of each lengthk candidate is counted by examining all the sequences. The PSP algorithm [12] is
placement of candidates is improved through a prefix tree arrangement to speed up pattern discovery. The SPIRIT algorithm [9] uses regular expressions as constraints and developed a family of algorithms for pattern mining under constraints based on a priori rule. The SPaRSe algorithm
[3] improves GSP by using both candidate generation and projected databases to achieve higher efficiency for high pattern density conditions.Problem Definition
UPDOWN DIRECTED ACYCLIC GRAPHBASED SEQUENTIAL PATTERN MINING
UDDAGbased pattern mining approach, which first transforms a database based on
frequent item sets, then partitions the problem, and finally, detects each subset using UDDAG. The absolute support for an item set in a sequence database is the number of tuples whose sequences contain the item set. An item set with a support
larger than minSup is called a frequent item (FI) set. Based on frequent item sets, we transform each sequence in a database D into an alternative representation.
Transformed database
Definition: Let D be a database and P be the complete set of sequential patterns in D, D be its transformed database, substituting the ids of each item pattern contained in D with the corresponding item sets, and denoting the resulted pattern set by P, we have P = P.
Based on frequent item sets, we transform each sequence in a database D into an alternative representation. Steps involved in Database Transformation:

Find the set of frequent items in D

Assign a unique id to each FI in D and then replace each item set in each
sequence with the ids of all the FIs contained in the item set.
Table 1: sequence database
Table 2: Transformed Database
For the database in Table 1, the FIs are:
(1),(2), (3), (4), (5), (6), (1,2), (2,3).
By assigning a unique id to each FI, e.g., (1)1, (1,2)2, (2)3, (2,3)4, (3)5,
(4)6, (5)7, (6)8, we can transform the database as shown in Table 2 (infrequent items are eliminated).
Problem Partitioning
Definition: Let {x1, x2, . . . , xt} be the frequent item sets in a database D, x1 < x2 <. . . . < xt, the complete set of patterns (P) in D can be divided into t disjoint subsets. The ith subset (denotd by Pxi, 1 < = i <= t) is the set of patterns that contains xi and FIs smaller than xi.
Definition (Projected database):
The collection of all the tuples whose sequences contain an item set x in a database D is called xprojected database, denoted by xD.
The total number of different Frequent Items FIs in the Sequential Database are found by Database Transformation module. For a database with n different frequent items, its patterns can be divided into n disjoint subsets. The ith subset (1 < i < n) is the set of patterns that contain i (the root item of the
subset) and items smaller thVaonl. 2 iI.sEsuae c9,hSeptember – 2013
subset i of the problem is mapped into a projected database denoted by (i D)
P is partitioned into eight subsets as there are 8 FIs in table2, the one contains 1 (P1), the one contains 2 and smaller ids (P2), . . . ,and the one contains 8 and smaller ids (P8).
Given the following database (P8) alone is found as given by 8D:
1. <9 4 5 8 3 6>
2. <3 9 4 5 8 3 1 5>
3. <3 8 2 4 6 3 9>
4. <2 8 4 3 6>
5. <9 6 3>
8D is,
1. <4 5 8 3 6>
2. <3 4 5 8 3 1 5>
3. <3 8 2 4 6 3>
4. <2 8 4 3 6>
UpDown Directed Acyclic Graph
Definition: Directed acyclic graph (UDDAG) is a graphical approach that represents patterns as vertices and contain relationships as directed edges in between vertices.
Given an FI x and xD, an UpDown Directed Acyclic Graph based on Px, denoted by xUDDAG, is constructed as follows:

Each pattern in Px corresponds to a vertex in xUDDAG. <x> corresponds to the root vertex, denoted by Vx

Let PU be the set of length2 patterns ending with x in Px . Add a directed edge from Vx to Uv called up root child of Vx. This represents the common prefix set to root X.

Let PD be the set of length2 patterns starting with x in Px, add a directed edge from Vx to VD called a down root child of Vx. This represents the common suffix set to root X.
Such a DAG can be recursively constructed in an efficient way to
derive the contain relationship of patterns
Example of UDDAG Construction:
By concatenating the patterns
{<3>,<4>,<5>,<4 5>} of Pre(8D) with
8, we derive patterns {<3 8>, <4 8>,
<5 8>, <4 5 8>} in figurea.
By concatenating patterns {<3>, <4>,
<6>, <3 6>, <4 3>, <4 6>} of Suf(8D)
with 8,we derive patterns {<8 3>, <8
4>, <8 6>, <8 3 6>, <8 4 3>, <8 4 6>}
in figureb.
UDDAG based Pattern Mining:
In the ith subset, each pattern in the projected database (xD) can be divided into two parts, prefix and suffix of i.
The collection of all the prefix/suffix tuples of a frequent item set X in xD is called the prefix/suffixprojected database of x, denoted by Pre(xD) / Suf(xD).
To detect the sequential pattern in projected database (xD) Px,

Detect patterns in Pre(xD) called pattern prefix (PP)

Detect pattern in Suf(xD) called pattern suffix (PS)

The above steps are repeated recursively until no frequent items are found in the pre(x D) / suf(x D)
.

Combine the patterns of all the iterations to derive Px.
The complete set of patterns is the union of patterns of the all subsets or projected database (xD) detected above.
The Apriori property is used to reduce the number of candidate sets to be considered
Example for Pattern MininVgo:l. 2 Issue 9, September – 2013
Assuming 8D is,
1. <4 5 8 3 6>
2. <3 4 5 8 3 1 5>
3. <3 8 2 4 6 3>
4. <2 8 4 3 6>.
The prefix subsequences of 8 in 8D, or Pre(8D) is :{<3 8>, <4 8>, <5 8>, <4 5
8>} the patterns with 8 at the end.
The suffix subsequences of 8 in 8D, or Suf(8D) is : {<8 3>, <8 4>,<8 6>, <8 3
6>, <8 4 3>, <8 4 6>} the patterns with 8 at the beginning.
The patterns with 8 in between the beginning and end of each pattern is:
{<3 8 3>,<4 8 3>, <5 8 3>, <4 5 8 3>}
Example: UDDAG based Pattern Mining:
Fig a: UP DAG
Fig b: DOWN DAG Fig c: UPDOWN DAG
Algorithm 1. UDDAG based pattern Mining.
Input: A database D and the minimum support
Output: P, the complete set of patterns in D
Method: findP (D, minSup){ P =
FISet=D:getAllFI(minSup); D.transform( );
for each FI x in FISet{ UDVertexrootVT = newUDVertex(x) findP(D.getPreD(x), rootVT, up, minSup) findP(D.getSurD(x),rootVT,down,min Sup)
findPUDDAG(rootVT)
P = P U rootVT.getAllPatterns( )
}
}
Subroutine:findP(PD,rootVT,type, minSup){ FISet=PD.getAllFI(minSup);
for each FI x in FISet{ UDVertexcurVT=new DVertex(x, rootVT)
if(type==up) rooVT.addUpChild(curVT)
else rootVT.addDownChild(curVT) findP(PD. getPreD(x), curVT, up, minSup) findP(PD.getSufD(x),curVT,down,min Sup)
findPUDDAG(curVT)
}
}
Subroutine: findPUDDAG(rootVT){ upQueue.enQueue (rootVT.upChildren) while(!upQueue.isEmpty()){ UDVertex upVT=upQueue.deQueue() if(upVT.upParent==rootVT) downQueue.enQueue(rootVT.downChildr en)
else if (upVT.downParent==null) downQueue.enQueue(upVT.upParent.VD VS)
else downQueue.enQueue(upVT.upParent. VDVS n upVT.downParent.VDVS) while(!downQueue.isEmpty()){ UDVertexdownVT=downQueue.deQueue ()
if(isValid(upVT, downVT){ UDVertexcurVT=new UDVertex (upVT, downVT) upVT.addVDVS(downVT) if(upVT.upParent==rootVT) downQueue.enQueue(downVT.childre n)
}
}
if(upVT.VDVS.size>0)upQueue.enQu eue(upVT.children)
}
}
Performance EvaluationVol. 2 Issue 9, September – 2013
We conducted an extensive set of
experiments to compare our approach with other representative algorithms. All the experiments were performed on a windows Server 2003 with 3.0 GHz Quad Core Intel Xeon Server and 16 GB memory. The algorithms we compared are PrefixSpan,
Spade, and LapinSpam, which were all implemented in C++ by their authors (Minor changes have been made to adapt Spade to Windows). Two versions of UDDAG were tested. UDDAGbv uses bit vector to verify candidates and UDDAGco uses co occurrences to verify candidates whenever possible. We perform two studies using the same data generator as in [14]: 1) Comparative study, which uses similar data sets as that in [14]; 2) Scalability study. The data sets were generated by maintaining all except one of the parameters as shown in Table 4 fixed, and exploring different values for the remaining ones.
CONCLUSION
In this paper, a novel data structure UDDAG is invented for efficient pattern mining. The new approach grows patterns from both ends (prefixes and suffixes) of detected patterns, which results in faster pattern growth because of less levels of database projection compared to traditional approaches. Extensive experiments on both comparative and scalability studies have been performed to evaluate the proposed algorithm.
One major feature of UDDAG is that it supports efficient pruning of invalid candidates. This represents a promising approach for applications involving searching in large spaces. Thus, it has great potential to related areas of data mining and artificial intelligence. In the future, we expect to further improve UDDAGbased pattern mining algorithm as follows: 1) Currently, FI detection is independent from
pattern mining. Practically, the knowledge gained from FI detection may be useful for pattern mining. In the future, we will integrate the solutions of the two so that they can benefit from each other. 2) Different candidate verification strategies may have different impacts to the efficiency of the algorithm. I the future, we will study more efficient verification strategy. 3) UDDAG has big impact to the memory usage when the number of patterns in a subset is extremely large. In the future, we will find an efficient way to store UDDAG.
REFERENCES

R. Agrawal and R. Srikant, Mining Sequential Patterns, Proc. Intl Conf. Data Eng. (ICDE 95), pp. 314, 1995. CHEN: AN UPDOWN DIRECTED ACYCLIC GRAPH APPROACH FOR EQUENTIAL PATTERN MINING 927

R. Agrawal and R. Srikant, Fast Algorithms for Mining Association Rules, Proc. 20th Intl Conf. Very Large Data Bases (VLDB), pp. 487 499, 1994.

C. Antunes and A.L. Oliveira, Generalization of PatternGrowth Methods for Sequential Pattern Mining with Gap Constraints, Proc. Intl Conf. Machine Learning and Data Mining 2003, pp. 239
251, 2003.

J. Ayres, J. Gehrke, T. Yu, and J. Flannick, Sequential Pattern Mining Using a Bitmap Representation, Proc. Intl Conf. Knowledge Discovery and Data Mining 2002, pp. 429435, 2002.

S. Berkovich, G. Lapir, and M. Mack, A BitCounting Algorithm Using the Frequency Division Principle, Software: Practice and Experience, vol. 30, no. 14, pp. 1531 1540, 2000.

J. Chen and T. CookV, ol. M2 Isisnuein9,gSeptember – 2013
Contiguous Sequential Patterns from
Web Logs, Proc. World Wide Web Conf. (WWW 07) Poster Session, May 2007.

J. Chen and K. Xiao, BISC: A Binary Itemset Support Counting Approach Towards Efficient Frequent Itemset Mining, to be published in ACM Trans. Knowledge Discovery in Data.

G. Grahne and J. Zhu, Efficiently Using PrefixTrees in Mining Frequent Itemsets, Proc. Workshop Frequent Itemset Mining Implementations (FIMI 03), 2003.

M. Garofalakis, R. Rastogi, and K. Shim, SPIRIT: Sequential Pattern Mining with Regular Expression Constraints, Proc. Intl Conf. Very Large Data Bases (VLDB 99), pp. 223234, 1999.

J. Han, J. Pei, B. MortazaviAsl,
Q. Chen, U. Dayal, and M.C. Hsu, FreeSpan: Frequent PatternProjected Sequential Pattern