1.
Here I write about some definitions about Sequential Pattern Mining.
We define the basic elements items, and S the set of all items. The subset of S, defined as event, inside a event, the items are unordered. The ordered set of event is defined as Sequence.
We define size of a Sequence the number of events, and length of a Sequence the total count of the instances of items. The sequence of length l is called l-sequence.
2.
Sequences is the basic logical elements of Sequential Pattern Mining. While implementing some mining algorithm, we need a high efficiency impletation of Sequence. So to design the class is a very important and fundamental work.
We need to design the Sequence class to meet the following requirments:
1) We could visit the a sequence by items and by event, and for a single item, we could locate it in the form "event X item Y" or in the form "item T from beginning of the sequence";
2) We need to get a sub-sequence of sequence easily and need to save memory of storing the sub-sequences;
3) We need a efficient way to find the instances of prefix in sequence, and then build the projectd-database with high efficiency.
3.The mapping between suquences is a very fundamental algorithm for mining sequential patterns. While judging the support relationships, finding the prefix, a huge amounts of such operations need to be proformed. We will consider a algorithm for the mapping here.
We build the algorithm in a layerd way. First, check all the events. Second, inside each events, check the items. We use two pointer for both layer, one sub-objects pointer, the other the parents-objects pointer. The basic algorithm is as below:
while parents-objects pointer not reach the end of the parents-sequence if map(parents-objects, sub-objects)==true sub-ojbects ++; parents-objects++; if sub-objects reach the end of the sub-sequence return true; end while;return false.
The function map, in the first layer should call the second layer for cheking the events.
4.
Here, we shall design the class for sequence.
First, we design a iterator fo sequence, it can get or set a item by "event X item Y" form, or just "the i-th item from the beginning of the sequence" form; and could move forward or backward by a item.
Second, the Event class, just using a vector in STL to store items by lexicographic order, and provide a function to judge the relationship of containment between events.
Third, the Sequence class, store a pointer to the vector composing of a series of events(this is the "real" sequence in the SDB), and two iterators, one pointing at the beginning of this Sequence, the other pointing at the end of this Sequence. When new Sequence generated, just "new" a vector, and modify the pointer to it and two iterators.
5.
The application of Sequential Pattern Mining is to mining the patterns in the opensource code examples(or something like), and sometimes the pattern could show you then common usages of the method in API.
The application is denoted in paper MAPO: Mining API Usages from Open Source Repositories(2005).
MAPO is to search the methods of API by some search engine. With the large amount of the search results, mining the code containing the wanted items.
Here I write about some definitions about Sequential Pattern Mining.
We define the basic elements items, and S the set of all items. The subset of S, defined as event, inside a event, the items are unordered. The ordered set of event is defined as Sequence.
We define size of a Sequence the number of events, and length of a Sequence the total count of the instances of items. The sequence of length l is called l-sequence.
2.
Sequences is the basic logical elements of Sequential Pattern Mining. While implementing some mining algorithm, we need a high efficiency impletation of Sequence. So to design the class is a very important and fundamental work.
We need to design the Sequence class to meet the following requirments:
1) We could visit the a sequence by items and by event, and for a single item, we could locate it in the form "event X item Y" or in the form "item T from beginning of the sequence";
2) We need to get a sub-sequence of sequence easily and need to save memory of storing the sub-sequences;
3) We need a efficient way to find the instances of prefix in sequence, and then build the projectd-database with high efficiency.
3.The mapping between suquences is a very fundamental algorithm for mining sequential patterns. While judging the support relationships, finding the prefix, a huge amounts of such operations need to be proformed. We will consider a algorithm for the mapping here.
We build the algorithm in a layerd way. First, check all the events. Second, inside each events, check the items. We use two pointer for both layer, one sub-objects pointer, the other the parents-objects pointer. The basic algorithm is as below:
while parents-objects pointer not reach the end of the parents-sequence if map(parents-objects, sub-objects)==true sub-ojbects ++; parents-objects++; if sub-objects reach the end of the sub-sequence return true; end while;return false.
The function map, in the first layer should call the second layer for cheking the events.
4.
Here, we shall design the class for sequence.
First, we design a iterator fo sequence, it can get or set a item by "event X item Y" form, or just "the i-th item from the beginning of the sequence" form; and could move forward or backward by a item.
Second, the Event class, just using a vector in STL to store items by lexicographic order, and provide a function to judge the relationship of containment between events.
Third, the Sequence class, store a pointer to the vector composing of a series of events(this is the "real" sequence in the SDB), and two iterators, one pointing at the beginning of this Sequence, the other pointing at the end of this Sequence. When new Sequence generated, just "new" a vector, and modify the pointer to it and two iterators.
5.
The application of Sequential Pattern Mining is to mining the patterns in the opensource code examples(or something like), and sometimes the pattern could show you then common usages of the method in API.
The application is denoted in paper MAPO: Mining API Usages from Open Source Repositories(2005).
MAPO is to search the methods of API by some search engine. With the large amount of the search results, mining the code containing the wanted items.
Comments