Student Member, IEEE Céline Fiot

Anne Laurent

Maguelonne Teisseire

From Crispness to Fuzziness: Three Algorithms for Soft Sequential Pattern Mining

Keywords: Sequential Patterns, Numerical Data, Fuzzy Intervals

Most real world databases consist of historical and numerical data such as sensor, scientific or even demographic data. In this context, classical algorithms extracting sequential patterns, which are well adapted to the temporal aspect of data, do not allow numerical information processing. Therefore the data are pre-processed to be transformed into a binary representation, which leads to a loss of information. Fuzzy algorithms have been proposed to process numerical data using intervals, particularly fuzzy intervals, but none of these methods is satisfactory. Therefore this paper completely defines the concepts linked to fuzzy sequential pattern mining. Using different fuzzification levels, we propose three methods to mine fuzzy sequential patterns and detail the resulting algorithms (SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY). Finally, we assess them through different experiments, thus revealing the robustness and the relevancy of this work.

I. INTRODUCTION

M OST real world databases consist of historically- stamped and numerical data (sensor, scientific, demographic, monitoring, evolution phenomena data, etc.). Within the context of large-scale database mining, few studies have been carried out to process this kind of data and most work is restricted to association rules [START_REF] Srikant | Mining quantitative association rules in large relational tables[END_REF]- [START_REF] Delgado | Acquisition of fuzzy association rules from medical data[END_REF]. A first proposal [START_REF] Srikant | Mining quantitative association rules in large relational tables[END_REF] processes quantitative data for association rule mining using the attribute discretization within crisp intervals. However, some frequent associations could be lost because of too restrictive bounds. Recently, the use of fuzzy set theory has reduced stark cuts between intervals, thus leading to more relevant rules. [START_REF] Fu | Finding fuzzy sets for the mining of fuzzy association rules for numerical attributes[END_REF]- [START_REF] Hong | Fuzzy data mining for interesting generalized association rules[END_REF] presented a new definition of support and confidence based on fuzzy set theory, in the context of association rule extraction from quantitative attributes. Rules will go from "75% of people who buy butter also purchase bread" to the new type "60% of people who eat a lot of candies purchase few potato chips". These association rule based approaches do not allow easy and complete processing of temporal data. Their extension to sequential pattern mining methods takes the temporal or ordered aspect of data into account, so it is well adapted to historically-stamped data. However, the first propositions [START_REF] Agrawal | Mining sequential patterns[END_REF], [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF] do not allow processing of numerical data and require pre-processing of these data into a binary representation,

The authors are with the Laboratory of Computer Science, Robotics, and Microelectronics, University of Montpellier II -CNRS, France. Email: {fiot, laurent, teisseire}@lirmm.fr which necessarily leads to a loss of information.

More recently, [START_REF] Hong | Mining fuzzy sequential patterns from multiple-items transactions[END_REF] and [START_REF] Chen | Discovery of fuzzy sequential patterns for fuzzy partitions in quantitative attributes[END_REF]- [START_REF] Chen | A novel method for discovering fuzzy sequential patterns using the simple fuzzy partition method[END_REF] presented two methods to extract fuzzy sequential patterns to mine sequences within historically-stamped quantitative data. These works were the very first proposals concerning this original mining method. However, these approaches can be generalized and improved. These proposals have indeed introduced several frameworks with drawbacks, the first one being too restrictive, the second one rather ambiguous.

We can indeed extract different kinds of knowledge from quantitative attributes. Sequential patterns are characterized by their support or frequency, which indicates the proportion of sequences in a database that contains this pattern. In the case of quantitative sequences, one can mine for different information: mining for the presence and frequency of certain quantitative attributes or sequences, mining for the frequency of these sequences with minimum relevancy, or mining for a weighted frequency according to the relevancy of the quantitative sequence. In this paper, we present a framework to take these different kinds of knowledge into account through the extraction of fuzzy sequential patterns. This framework extends and generalizes previous proposals concerning fuzzy sequential pattern mining approaches. We detail a complete and efficient fuzzy approach for sequential pattern mining which enables processing of numerical data, with different levels of consideration of numerical information. Our approach is based on the definition of fuzzy intervals. Obtained patterns are of the type "60% of people purchasing a lot of candies and few video games buy later a lot of toothpaste". These patterns are characterized by their frequency (or support), which is by definition the proportion of customers who have bought these products. We define three approaches SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY that differ from each other by their evaluation of the frequency and thus extract different levels of information. The end-user is allowed to choose between the speed of result extraction and the accuracy of the obtained frequent patterns. Implementation of the different solutions is based on an efficient and original data scanning method, which extends the PSP algorithm proposed by F. Masseglia et al. [START_REF] Masseglia | The PSP approach for mining sequential patterns[END_REF]. Experiments were carried out on synthetic datasets. They highlight the feasibility of a fuzzy approach and its robustness. Furthermore our algorithms were assessed on different real-world datasets. This paper is structured as follows: Section II presents an introduction to sequential patterns and describes the shortcomings in former proposals of fuzzy sequential patterns. Section III presents a different way to assess the sequence frequency. Then functions calculating the frequency for each method are detailed in Section IV with their involvement in database scanning. TOTALLYFUZZY, the most complex algorithm is detailed along with its computational complexity. Then Section V describes the overall algorithm to mine fuzzy sequential patterns upon which our three algorithms SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY are based, while providing a short example to describe how it works. Section VI presents the implementation of the algorithms and the experiments carried out on synthetic datasets and also on real-world data. Finally, in Section VII we conclude on the advantages of the different information levels and present different prospects generated by this work.

II. FROM SEQUENTIAL PATTERNS TO FUZZY SEQUENTIAL PATTERNS

In this section, we briefly describe the basic concepts of sequential patterns and then take a look at earlier proposals on fuzzy sequential patterns, highlighting their weaknesses.

A. Sequential Patterns

Let R be a set of objects records where each record R consists of three information elements: an object-id, a record timestamp and a set of attributes/items in the record. Let I = {i 1 , i 2 , ..., i m } be a set of items or attributes. An itemset is a non-empty set of attributes i k , denoted by (i 1 i 2 . . . i k ). It is a non-ordered representation. A sequence s is a non-empty ordered list of itemsets s p , denoted by < s 1 s 2 ...s p >. A n-sequence is a sequence of n items (or of size n).

Example 1: Let us consider an example of market basket analysis. The object is a customer, and records are the transactions made by this customer. Timestamps are the date of transactions. If the customer Smith purchases products 1, 2, 3, 4, and 5 made by the customer Smith according to the sequence s =< (1) (2 3) (4) (5) >, then all items of the sequence were bought separately, except products 2 and 3 which were purchased at the same time. In this example, s is a 5-sequence.

One sequence

< s 1 s 2 ...s p > is a subsequence of another one < s ′ 1 s ′ 2 ...s ′ m > if there are integers l 1 < l 2 < ... < l p such that s 1 ⊆ s ′ l1 , s 2 ⊆ s ′ l2 , ..., s p ⊆ s ′ lp . Example 2: The sequence s ′ = <(2) (5)> is a subsequence of s because (2) ⊆ (2 3
) and ( 5) ⊆ (5). However, <(2) (3)> is not a subsequence of s.

All records from the same object are grouped together and sorted in increasing order of their timestamp. They are called a data sequence. An object supports a sequence s if it is included within the data sequence of this object (s is a subsequence of the data sequence). The frequency of a sequence (f req(s)) is defined as the percentage of objects supporting s. In order to decide whether a sequence is frequent or not, a minimum frequency value (minF req) is specified by the user and the sequence is said to be frequent if the condition f req(s) ≥ minF req holds. Given a database of object records, the problem of sequential pattern mining is to find all maximal sequences whose the frequency is greater than a specified threshold (minF req) [START_REF] Agrawal | Mining sequential patterns[END_REF]. Each of these sequences represents a sequential pattern, also called a maximal frequent sequence. Note that items are processed using a simple binary evaluation -present or not present.

B. Fuzzy Sequential Patterns

In order to mine fuzzy sequential patterns, the universe of each quantitative item is partitioned into several fuzzy sets. T.-P. Hong et al. [START_REF] Hong | Mining fuzzy sequential patterns from multiple-items transactions[END_REF] presented the first proposal of a fuzzy sequential pattern mining approach. Their proposal is based on discretization of data into fuzzy intervals. However, to minimize the number of items being processed, in a first step, the mining algorithm selects the fuzzy items that would be kept for mining sequential patterns. So it only keeps, for each item, the fuzzy set having the highest cardinality over the whole database (by Σ-count).

Example 3: Let us consider the database shown in Table I describing the purchases of 3 customers for the attribute Candy. In this case, the only column that will be taken into account in [START_REF] Hong | Mining fuzzy sequential patterns from multiple-items transactions[END_REF] for the item Candy is little, whereas it is not the quantity that is the most present within the data sequences (it is actually medium or lot).

It is thus obvious that such a decision is reductive and can lead to erroneous rules. The consequences of this strategy on the discovery of sequential patterns are highlighted in our experiments, section VI-D. If we consider that the selection step could be avoided, it is not clearly expressed. Moreover, it would certainly have consequences on the following part of the algorithm.

Y.-C. Hu et al. [START_REF] Chen | Discovery of fuzzy sequential patterns for fuzzy partitions in quantitative attributes[END_REF]- [START_REF] Chen | A novel method for discovering fuzzy sequential patterns using the simple fuzzy partition method[END_REF] adopted a theoretical approach presenting an algorithm without the underlying data structures nor any experimental assessment. Moreover, their proposal has ambiguous formalism and notations for the frequency computation of a fuzzy itemset and thus for a fuzzy sequence. It is especially hard to identify differences between the frequency computation of the sequences <(a)(b)(c)> and <(a)(b c)>. This point is, however, fundamental in the context of sequential pattern mining because the timestamps associated to the items play an important role.

Finally, clearly none of these previous works consider the different levels of information that could be obtained by considering a global framework for fuzzy sequential pattern mining and the different levels of fuzzification that could be used to assess the frequency of a sequence. Therefore we give a generalized definition for the frequency of a sequence and propose three algorithms to mine fuzzy sequential patterns. III. PROPOSAL: FROM CRISPNESS TO FUZZINESS First, we detail the formalism for our fuzzy sequential pattern framework. We give a clear and non-ambiguous definition of the basic concepts (item, itemset, g-k-sequence and fuzzy frequency). The core of this paper is a proposal of three algorithms with three levels of fuzzification, depending on the counting method adopted to determine the frequency of sequences or itemsets. The counting methods considered are based on the four classical ways to compute fuzzy cardinality of a fuzzy subset A:

1) counting all elements for which the membership degree is not null (card(supp(A))); 2) considering only elements for which the membership degree is greater than a defined threshold. This counting method is called thresholded count (card(supp(Aα))); 3) adding the membership degrees of each element. This counting method is called Σ-count (

X x∈supp(A) µA(x));
4) adding membership degrees greater than a defined threshold α, this is called thresholded Σ-count (

X x∈supp(A) µA α (x)).
Each algorithm is defined through a generic one, SMT-Fuzzy, presented Section V. Each of them corresponds to one precise frequency computation, thus allowing three levels of fuzzification during the mining of fuzzy sequential patterns, based on one approach given in [START_REF] Dubois | A note on quality measures for fuzzy association rules[END_REF], thus justifying the use of some fuzzy logical operators for fuzzy association rule frequency measurement.

A. Preamble: item, itemset, g-k-sequence

The item and itemset concepts have been redefined relative to classical sequential patterns. Definition 1: A fuzzy item is the association of one item and one corresponding fuzzy set. It is denoted by [x, a] where x is the item (also called attribute) and a is the associated fuzzy set.

Example 4: [candy, lot] is a fuzzy item where lot is a fuzzy set defined by a membership function on the quantity universe of the possible purchases of the item candy. Definition 2: A fuzzy itemset is a set of fuzzy items. It can be denoted as a pair of sets (set of items, set of fuzzy sets associated to each item) or as a list of fuzzy items. We use the following notation: (X, A), where X is a set of items and A is a set of corresponding fuzzy sets.

Example 5: (X, A) = ([candy, lot][soda, little]) is a fuzzy itemset and can also be denoted by ((candy, soda)(lot, little)).

One fuzzy itemset only contains one fuzzy item related to one single attribute. For example, the fuzzy itemset ([candy, lot][candy, little]) is not a valid fuzzy itemset because it contains twice the attribute candy.

Lastly, we define a g-k-sequence. In the next sections of this article, we use the following notations: let O represent the set of objects and R o the set of records for one object o. Let I be the set of attributes or items and r[i] the value of attribute i in record r. Each attribute i is divided into fuzzy sets.

Definition 3: A g-k-sequence S =< s 1 • • • s g > is a sequence constituted by g fuzzy itemsets s = (X, A) grouping together k fuzzy items [x, a].
Here we apply generic definitions of objects and attributes to the supermarket basket analysis, with one object being a customer and the products standing for the attributes. For example, we use the dataset described in Table II, in which an empty cell indicates that the product has not been purchased.

First, the quantitative database is converted into a membership degree database. Each attribute is partitioned into several fuzzy sets, as shown in Fig. 1, which represents the membership functions for each attribute. These partitions are automatically built by dividing the universe of quantities into intervals. Each interval groups the same proportion of customers. It is then fuzzified in order to enhance generalization. From these membership functions, we get the membership degrees for each transaction and for each fuzzy set. Table III describes these values for customer 1. This example will be used below to illustrate the computation of the different frequencies for the itemset

Ix = ([candy, little][soda, lot]) and the sequence Sx = < ([candy, little])([soda, lot]) >.

B. Three Frequency Computation Methods

The frequency of a fuzzy itemset is computed as the number of objects supporting this fuzzy itemset compared to the total number of objects in the database:

F F req (X,A) = o∈O F (o, (X, A)) |O| (1)
where the frequency degree F (o, (X, A)) marks whether the object o supports the fuzzy itemset (X, A) or not.

As previously presented, the cardinality of a fuzzy set depends on the counting method. We transpose here three of these techniques in the framework of fuzzy sequential patterns and propose three definitions for the fuzzy frequency. • SPEEDYFUZZY is based on the count "supports / does not support" [START_REF] Srikant | Mining quantitative association rules in large relational tables[END_REF]. Computing the frequency of a fuzzy itemset consists of counting all objects that recorded the itemset at least once. Regardless of the membership degree of the record for the fuzzy itemset, if it is greater than zero, the object has the same weight:

F SF (o, (X, A)) = 1 if ∃r ∈ Ro|∀[x, a] ∈ (X, A), µa `r[x] ´> 0 0 else
(2) Example 7: With the SPEEDYFUZZY count, the first customer supports the itemset Ix since one transaction is found containing the regarded itemset with a membership degree greater than zero, this is transaction d1 on Table IV.

• MINIFUZZY is based on a thresholded count. This method only increments the number of objects supporting the fuzzy itemset when each item of the candidate sequence has a membership degree greater than a specified threshold in the data sequence of the object:

F MF (o, (X, A)) = 1 if ∃r ∈ Ro|∀[x, a] ∈ (X, A), µa `r[x] ´> ω 0 else (3)
Example 8: With a MINIFUZZY count, customer 1 supports the itemset Ix since a transaction is found containing the items with a membership degree greater than the threshold (ω=0.49). These correspond to transaction d3 in Table IV.

• TOTALLYFUZZY carries out a thresholded Σ-count. In this approach, the importance of each fuzzy itemset in the data sequence is taken into account in the support computation. To do so, the threshold membership function α is defined as:

α a r[x] = µa `r[x] ´if µa `r[x] ´> ω 0 else (4)
The frequency counting formula becomes:

F T F (o, (X, A)) = ⊥ |Ro| j=1 ⊤ [x,a]∈(X,A) α a r j [x] (5)
where ⊤ and ⊥ are the generalized t-norm and t-conorm operators.

Note that the Σ-count is a thresholded Σ-count, with a threshold ω=0.

Example 9: With a TOTALLYFUZZY count, customer 1 supports the itemset Ix if a transaction is found containing the fuzzy itemset, with a membership degree greater than the threshold ω. The best value for the itemset is kept. In our example, this itemset is supported by d6 in Table IV.

The frequency of a fuzzy g-k-sequence is computed as the ratio of the number of objects supporting this fuzzy sequence compared to the total number of objects in the database:

F F req (X,A) = o∈O F (o, gS) |O| ( 6
)
where the frequency degree F (o, gS) indicates whether the object o supports the fuzzy sequence gS. This frequency degree is computed using the algorithm

IV. COMPUTING A SEQUENCE FREQUENCY

Depending on the algorithm used to mine fuzzy sequential patterns, SPEEDYFUZZY, MINIFUZZY or TOTALLYFUZZY, the difference will depend on the frequency computation.

A. Using SpeedyFuzzy and MiniFuzzy Algorithms

The way the algorithms SPEEDYFUZZY and MINIFUZZY work is quite similar to computing the sequence frequency. For each object, it is a matter of scanning the record set to find the candidate sequence. For each itemset in the sequence, it is necessary to check whether the membership degree is not zero for SPEEDYFUZZY or greater than the threshold ω for MINIFUZZY. As soon as the candidate sequence has been validated (the ordered set of items is supported by the object), scanning of the object records is stopped and the frequency of the sequence is incremented.

The SPEEDYFUZZY count is based on the function F indSpeedySeq, Algorithm 2, which searches for a candidate sequence in the record set of an object. It involves searching for each itemset of the sequence, following their order. When the first one is found within a record with a degree greater than zero, the following itemset is searched for in the following record and so on. In Fig. V, transactions that validate sequence Sx with a SPEEDYFUZZY count are d1 followed by d3. This corresponds to the underlined items.

ALGORITHM 2 -FindSpeedySeq

Input: gS, candidate g-k-sequence; R, record set to run Ouput: f ound, 1 if gS is found, 0 else currIS ← gS.first() ; f ound ← 0 ; r ← R.first() ; While (((!f ound) || (r!=∅))) do If ((⊤ [x,a]∈currIS αa(r[x]) ≥ 0)) Then If ((currIS != gS.last())) Then currIS ← gS.next() ; Else f ound ← 1; End If End If r ← R.next() ; End While return f ound
The MINIFUZZY count is based on the function F indM iniSeq, Algorithm 3, which searches for a candidate sequence in the record set of an object. It consists of searching for each itemset of the sequence, following their order. When the first one is found within a record with a degree greater than the threshold of relevancy ω, the following itemset is searched for in the following record and so on.

ALGORITHM 3 -FindMiniSeq Input: gS, candidate g-k-sequence; R, record set to run Ouput: f ound, 1 if gS is found, 0 else currIS ← gS.first() ; f ound ← 0 ; r ← R.first() ; While (((!f ound) || (r!=∅))) do If ((⊤ [x,a]∈currIS αa(r[x]) ≥ ω)) Then If ((currIS != gS.last())) Then currIS ← gS.next() ; Else f ound ← 1; End If End If r ← R.next() ; End While return f ound
In Table V, transactions that validate the sequence Sx with MINIFUZZY count are d2 followed by d3. This corresponds to the boldfaced items.

B. TotallyFuzzy Frequency Computation

TOTALLYFUZZY implements the fuzzy frequency computation using a thresholded Σ-count to calculate the number of objects supporting a sequence. In this section, we present the frequency calculation carried out by this algorithm.

1) A Trade-Off between Space and Computational Complexity:

When considering classical sequential patterns or even in a certain way SPEEDYFUZZY or MINIFUZZY, an object supports a sequence or not. So the scan can stop as soon as the sequence is found within the record set of an object. On the contrary, as TOTALLYFUZZY computes a thresholded Σ-count, for each object and each sequence, the best membership degree must be considered. This degree is computed as the aggregation of the itemset frequencies. The order of the fuzzy items must also be taken into account. This leads to an exhaustive scanning of the record set, as performed for association rule mining. Let us consider, for instance, Table V. If we look for the same sequence as above, i.e. Sx, the first occurrence of this sequence is the one underlined, supported by transaction d1 then d3. However, the best occurrence of this sequence is given by transaction d4 followed by d6, underlined twice.

A naive approach could be that for each candidate ksequence (likely frequent sequence) we scan all the database to find its frequency, which would involve n k scans of the database at most if n is the number frequent items. The only structure kept in memory would thus be the list of candidate sequences. However, this would be very inefficient, as the computational time would explode. To reduce this number of scans, we have defined a data structure enabling us to find all representations of all ksequences in only k scans of the database. The computational time is also lower but the used memory space is increased. However, some optimizations have been implemented to bound this spatial complexity. So we present here an efficient implementation based on the notion of path. One path corresponds to a possible instantiation of the candidate sequence itemsets within the object record set. Several paths may be initialized for one object. For the global frequency computation, we only keep the complete one having the best degree. Definition 4: One path is a triplet containing the already found sequence seq, the currently searched itemset curIS (coming next in the candidate sequence) and the current membership degree curDeg.

The next subsections illustrate how TOTALLYFUZZY count works and detail the functions for the support calculation.

2) Computing a sequence support. an Illustration:

As an illustration, we run the TOTALLYFUZZY count function, F indT otallySeq, to compute the frequency of the candidate sequence Sx <([candy, little])([soda, lot])> for customer 1 from It is thus modified to pth2 ← (< ([candy, little]) ([soda, lot]) >, ∅, 0.5). This path is closed since it contains all itemsets of g-S. However, we plan to improve this solution. So, before having modified pth2, it is copied into pth3. At this step, we have two paths: pth2, closed with a frequency degree of 0.5 and pth3 = (< ([candy, little]) >, ([soda, lot]), 0.5) (Table VI, row 4). Transaction d4 is then checked. pth3.curIS is found so it is copied, modified and then closed with a degree of 0.5. As d4 also contains the first itemset of g-S, a new path is created. At this point, we have four paths (Table VI, row 5). The Optimize function deletes, for each step in the sequence, the path with the lowest degree, i.e. pth3 and pth4. Scanning then continues. At d5, pth5 is copied into pth6, modified and closed with a frequency degree of 0.63, so pth2 is deleted. Finally, at d6, pth6 is updated and closed with a degree of 0.87. This is the path kept for customer 3.

3) Computing a sequence support. the Algorithms:

The algorithm TOTALLYFUZZY uses the function FindTotally-Seq to carry out an ordered scanning in one object record set and finds the best occurrence of a sequence in the records of one object. When the first itemset of the sequence is found, one path is created with the itemset frequency. The next records are checked to find either the following part of the sequence or once again the beginning of the sequence or an improvement of the paths already created. All possible paths are thus completed step-by-step at each record. The frequency degree of the best path for the whole sequence is then aggregated and returned.

The U pdate function allows an update of each path and closes the complete ones. The Optimize algorithm enables deletion of unnecessary paths, which means, for two paths at the same point, to only keep the one with the greatest degree.

V. MINING FREQUENT SEQUENCES

This section presents the overall algorithm, called SMT-Fuzzy which extracts the fuzzy sequential patterns.

Our approach extends the level-wise approach generate-prune within the sequential pattern context and, more particularly, uses the prefix-tree structure described in [START_REF] Masseglia | The PSP approach for mining sequential patterns[END_REF], in order to improve the frequency computation process. Other data structures may be considered such as the one described in [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]. This structure is used to store both the candidate and frequent sequences. The tree in Fig. 2 The overall algorithm SMT-Fuzzy is presented by Algorithm 7. Whatever function is used to compute the frequency, the way of working is the same. First, the fuzzy frequency of all fuzzy items is computed and only items with a frequency greater than minF req are stored as frequent ones of size 1. Then, while a candidate generation still is possible, the generate function builds the candidate sequences of size k from the frequent sequences of size k-1. Then a scan of the database is run and frequencies are computed using CalcF uzzyF req. Finally, all infrequent sequences of size k are pruned and the process continues. At the end of the process, we obtain a Prefix-tree containing all frequent sequences of the database with their frequency at each leaf of the tree.

represents the sequences <([candy, little][soda, lot])([soda, lot])>, <([candy, little])([toothpaste, medium])> and also the subsequences <([toothpaste, medium])> and <([soda, lot])([soda, lot])>.

ALGORITHM 7 -SMT-Fuzzy

Input: DB, a database, minSupp Ouput: P T , the prefix-tree of frequent sequences find-1-Frequent() ; While (#candidate > 0) do generate(P T .depth+1) ; For each sequence s in P T do CalcF uzzyF req(s); End For prune(P T ); End While return (P T ) ;

As for PSP, the overall computational complexity of SMT-Fuzzy depends only on the length of the candidate sequences, and thus of the frequency calculation. Computation of the generate and prune functions are indeed insignificant in comparison with that of CalcF uzzyF req.

According to the fuzzification level expected by the enduser, the function CalcF uzzF req will call:

• F indSpeedySeq; SMT-Fuzzy will actually be run as SPEEDYFUZZY. It will return the fuzzy sequential patterns corresponding to a global view of the database, giving the frequency of attribute quantities for each one. • F indM iniSeq; SMT-Fuzzy will be run as MINIFUZZY.

It will return more accurate information, giving the fuzzy sequential patterns corresponding to a minimum relevancy of attribute quantities. • F indT otallySeq; SMT-Fuzzy will be run as TOTALLY-FUZZY. It will return accurate fuzzy sequential patterns, taking into account both the relevancy and frequency of fuzzy attributes within the dataset.

In the next paragraph, these different versions of SMT-Fuzzy, respectively called SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY, are used to mine fuzzy sequential patterns within the database given in Table II.

First, the algorithm scans for frequent fuzzy items. Table VII gives the frequencies obtained through the different counts using ω = 0.49 for MINIFUZZY and TOTALLYFUZZY. We obtain the 1-frequent ones boldfaced in this figure, for a minimum frequency of 52%. The different algorithms have found the same frequent items. Then these fuzzy items are combined into candidate 2-sequences whose the frequency is calculated. Frequent 2sequences are then combined into candidate 3-sequences whose the frequency is calculated and so on.

Table VIII shows the sequential patterns (maximal frequent sequences) respectively extracted by SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY, for a minimum frequency minF req=52% and ω=0.49. Note that the frequent items are the same for all counting methods. The difference is in the number and length of the sequences. For a same minF req, the number and length of the mined patterns are indeed greater with MINIFUZZY or SPEEDYFUZZY than with TOTALLYFUZZY. This is due to the thresholded Σ-count.

This reduction in the number of patterns can be used for a database containing very high amounts of frequent patterns to find the most relevant ones. The advantage of this method is to be more selective and therefore to find the most relevant sequential patterns. The user will thus be provided with a selection of patterns, and not only have to assess a selection of patterns or a really large quantity of them.

VI. EXPERIMENTS

In this section, we present a comparison of performances of the three algorithms SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY and the algorithm PSP [START_REF] Masseglia | The PSP approach for mining sequential patterns[END_REF], a generate-prune approach for crisp sequential pattern mining. We also compare TOTALLYFUZZY with an implementation of the [START_REF] Hong | Mining fuzzy sequential patterns from multiple-items transactions[END_REF]'approach. These experiments were carried out on a PC -Linux 2.6.7 OS, CPU 3 GHz with 512 MB of memory. All the algorithms were implemented in Java on the PSP principle. In particular, the Prefix-Tree structure was used to store the candidate and frequent sequences.

A. Synthetic Datasets

We used synthetic datasets which have been created in several steps. In a first step, quantitative databases were generated using an enhancement of DatGen [START_REF] Melli | Synthetic classification data set generator[END_REF]. Then an automatic partitioning was carried out using a tool based on a module of Weka [START_REF] Witten | Data mining: Practical machine learning tools with java implementations[END_REF] using the object-timestamp-item-quantity file. This DiscretizeFilter module enables us to divide a given interval into several smaller intervals of an equivalent number of elements (equi-depth). Lastly, the membership degree database was created. Table IX gives the list of parameters used for the data generation method and Table X shows the databases used and their properties. For these experiments, the number of fuzzy sets by attribute was set at 3, the maximal quantity by item at 10 and the number of different items in the database at 100. These databases are rather dense.

B. Operators

We have chosen to implement our version of TOTALLYFUZZY with min as a t-norm operator and max as a t-conorm operator. Let us consider an item. To be considered frequent, this item must be relevant enough for enough objects (regarding the value of minF req). This means that its degree must be greater than ω. Now let IS be an itemset. If we consider that each item of IS is relevant, this itemset could be considered as relevant. The frequency of this itemset should thus not be lower than the minimum frequency of the items. The operator for computing this frequency must thus be idempotent. For this reason, our t-norm operator is min.

The aggregation operator we have chosen is the average operator. Each itemset in the sequence will thus be considered as equivalent to the others. However, we could have used the min operator to compute the frequency of sequences. A sequence is indeed the intersection, taking into account the temporal order of itemsets. This can be computed using min as explained above. The results described in Fig. 3 show that the aggregation by min is too selective and that it prunes too many sequential patterns.

C. Fuzzy Algorithms vs. PSP Algorithm

The aim of these experiments is to compare the fuzzy algorithms with PSP [START_REF] Masseglia | The PSP approach for mining sequential patterns[END_REF], a sequential pattern algorithm working with the same efficient structure as our fuzzy algorithms. Fig. 4 shows the mining time according to minF req. Note that the extraction time increases as minF req decreases. The number of frequent patterns and generated candidates is indeed higher for a low minF req. So the algorithms scan the dataset more times.

It can also be noted that SPEEDYFUZZY is as fast as PSP despite the fact that it scans three times more items. One should indeed take into account that each PSP item has been split into three (it could have been more) fuzzy items to meet our algorithm needs. TOTALLYFUZZY and MINIFUZZY run slightly slower. If we compare the number of frequent sequences for the same minimum frequency, Fig. 5 shows that MINIFUZZY and TOTALLYFUZZY definitely extract less frequent sequences than SPEEDYFUZZY and PSP. This is due to the frequency evaluation. In fact, these two fuzzy algorithms, MINIFUZZY and TOTALLYFUZZY, only keep items which have a degree greater than ω and so which are considered relevant by the user. The number of frequent sequences is then necessarily reduced compared to SPEEDYFUZZY or PSP. Finally, Fig. 6 shows the extraction time according to the number of records in a database describing records for 5000 objects, for minF req = 0.6. Note that the fuzzy algorithms have the same behavior as PSP. Runtime according to the number of records in the datasets, minF req=0.6 D. TOTALLYFUZZYvs. Hong and al. approach The aim of this paragraph is to show the benefits of our method in comparison to the method of Hong et al. [START_REF] Hong | Mining fuzzy sequential patterns from multiple-items transactions[END_REF] presented in Section II-B. In particular, we study the loss of information resulting from their approach.

In our experiments, we compared our algorithm TOTALLYFUZZY (the closest to their approach) with an implementation of the approach of Hong et al. As shown in Fig. 7, the selection of the item having the highest cardinality carried out by [START_REF] Hong | Mining fuzzy sequential patterns from multiple-items transactions[END_REF] efficiently decreases the runtime of the fuzzy sequential pattern mining. This algorithm runs faster than TOTALLYFUZZY. However, it can be noted from Table XI that some items (e.g. Consequently, the number of maximal frequent sequences found by TOTALLYFUZZY is higher than that obtained by the method of Hong et al. method. The frequent sequences resulting from the five ignored frequent items are indeed never generated and thus cannot be found. Fig. 8 shows this loss of information. In fact, for minF req=70%, the approach of Hong et al. only finds two thirds of the sequential patterns mined by TOTALLYFUZZY. TOTALLY-FUZZY (ω=0.7) and by [START_REF] Hong | Mining fuzzy sequential patterns from multiple-items transactions[END_REF] for ob5rec100I10

E. Response to ω Variation

Parameter ω introduced for the algorithms MINIFUZZY and TOTALLYFUZZY regulates the counting. It is indeed used to filter the relevancy of each record according to the membership degree of the fuzzy attributes. A high value for this parameter enables the user to extract sequential patterns which are both supported by many objects and well-represented in each ones' sequence. On the contrary, a low value for parameter ω allows extraction of sequential patterns supported by more objects. But these patterns do not provide information on the extent to which the objects support them.

The advantage of using this parameter combined with the minimum frequency is that it gives two information elements in one. Choosing a parameter ω greater than minF req will indeed enable the user to more precisely select frequent sequences within the database, keeping only the ones that are both frequent and relevant.

In order to show the response to the variation of the ω parameter, we built a new synthetic dataset (ob5rec100I10Q100) using a larger set for quantities (between 1 and 100) and we built fuzzy sets, the same for each possible quantity, enabling more precise variation for membership degrees, as shown in Fig. 9. Progressive fuzzy sets for quantities between 1 and 100 in ob5rec100I10Q100

We then ran experiments varying the value of parameter ω to show its influence on the runtime and found sequences. As we can see in Fig. 10 we extract more sequences as ω decreased. We indeed enable the mining algorithm to keep less relevant sequences, with lower membership degree as supporting sequences, so we extract more frequent sequences. Consequently the runtimes also increase as ω decreases, as shown in Fig. 11. The programme indeed has to scan the database for more candidate sequences.

F. Experiments on Real-World Datasets

Several experiments have been carried out on real-world datasets. The first ones were aimed at web access log mining. The purpose of the experiments was to increase knowledge obtained through crisp sequential pattern mining for the number of accesses to the same page during a session. Other experiments have been carried out on registered trademarks in order to mine for knowledge about the building of trademarks.

1) Web Access Log Mining:

The aim of these experiments is to show that soft sequential pattern mining brings more relevant information compared to crisp sequential pattern mining. In our case, access logs from a laboratory website were prepared and mined to find frequently visited pages -such as in crisp sequential pattern mining -but also repeatedly visited pages. These experiments are developed in [START_REF] Fiot | Web access log mining with soft sequential patterns[END_REF].

The access logs were pre-processed and the dataset recorded the number of accesses to one page, the same half-day by one user. It contained 27209 web pages visited by 79756 different IPs over 16 days (32 half-days). As explained previously, quantities are converted into fuzzy set membership degrees and mined with fuzzy algorithms. These are partitioned into 3 fuzzy sets per URL using the same tool as that used for synthetical datasets.

We ran the access log database with the different algorithms, starting with SPEEDYFUZZY, to first extract overall information concerning which URLs were often accessed several times in the same session. Then we mined for more accurate knowledge using TOTALLYFUZZY. These experiments revealed that the behavior of our algorithms on synthetical datasets was confirmed on real-world datasets. If we compare the number of frequent sequences for the same minimum support, Fig. 13 shows that MINIFUZZY and TOTALLYFUZZY extract less frequent sequences than SPEEDY-FUZZY and PSP due to the support definition. In fact, these two fuzzy algorithms, MINIFUZZY and TOTALLYFUZZY, only keep items which have a degree greater than ω and thus which are considered as relevant by the user. The number of frequent sequences is then necessarily reduced compared to SPEEDYFUZZY or PSP. These behaviors confirm the good results obtained in experiments on synthetic datasets described in previous Section VI-C. Furthermore, we obtained the same frequent URLs using crisp or soft sequential pattern mining. The advantages of our method concern the additional knowledge supplied by quantities. Indeed, while the crisp algorithm PSP found that one URL (e.g. 139) was frequently accessed, TOTALLYFUZZY found that it was frequently accessed between 2 and 5 times during the same period. Our patterns also revealed that the root page was only a step in the browsing sequences and often accessed only once during the same session.

2) A Trademark Database Summarization:

INPI is the French National Institute for the Industrial Property. It manages and registers industrial title deeds, communicates information on industrial property and devises and adapts French industrial property rights. The INPI trademark database registered around 2 million names between 1961 and 2004. These trademarks have been registered in one or several categories corresponding to industrial fields such as "toys, games" or "clothing, shoes, hat industry". Each record is composed of several attributes, for instance: idnumber, trademark, registration date, registering company, registering class. The global goal of analysing such a database is, for the linguistic expert, to understand how trademarks act on consumers.

These experiments aim at discovering word form in registered tradenames. These experiments were run in several steps. First some statistical results were used to select trademarks that would be interesting to investigate. Then we used TOTALLY-FUZZY to sum up this database.

A statistical analysis revealed that, compared to other registration fields, an appreciable amount of trademarks registered in telecommunication fields contain some figures and symbols. As these results were atypical, we decided to search for an overall description of the composition of trademarks registered in this field. This dataset contains more than 480,000 trademarks consisting of one or several words. The mined patterns would, for example, be "Almost one third of registered names are first composed of one part containing a lot of letters then of a part with a few figures and then a part with a few punctuation marks and a few letters". These proposals would be built from a sequence <([letter, lot]) ([figure, few]) ([punct_symb, few],[letter, few])>. In this case, we can consider trademarks consisting of one or several words. In fact, a name consisting of only one word will appear as an itemset instead of a sequence for a name consisting of several words. In order to mine such patterns, the INPI database is converted into the format [ID_TM,#WORD, FUZZY ITEM,DEGREE], as shown Table XII, whereas the fuzzy items are described in Fig. 15. These fuzzy sets are given by the linguistic expert and are built on common word composition. Extended results are presented in [START_REF] Fiot | Why fuzzy sequential patterns can help data summarization: An application to the inpi trademark database[END_REF], but some revealing patterns show that "Almost one half of these trademarks contain three words with a lot of signs, the first and last ones with a lot of signs and letters, the second one with few letters or a medium amount of signs" (<([#sign By decreasing the value of minF req and ω, we did not find patterns with figures or symbols using TOTALLYFUZZY. As these results did not confirm the statistical analysis results, we ran SPEEDYFUZZY and MINIFUZZY, which then confirmed these statistical results.

Our conclusion on these experiments is that the fuzzy partitioning intuitively given by the expert from common language does not mesh well with the trademark composition. Further experiments will be carried out with automatically built fuzzy sets from the database using a clustering algorithm as presented in [START_REF] Fu | Finding fuzzy sets for the mining of fuzzy association rules for numerical attributes[END_REF] and [START_REF] Gyenesei | Multidimensional fuzzy partitioning of attribute ranges for mining quantitative data: Research articles[END_REF].

VII. DISCUSSION AND PROSPECTS

In this paper, we present a complete and efficient fuzzy approach for sequential pattern mining which enables us to process historical numerical data such as demographic or sensor data. Extracting sequential patterns in such databases is highly interesting for event sequence detection. However, existing algorithms either do not allow numerical data processing or only extract one information element from the several which could be obtained from quantitative databases.

Our proposal clearly and completely defines different concepts and principles associated with fuzzy sequential patterns, which are presented through a global framework for fuzzy sequential pattern mining. This framework enables the user to choose between three fuzzyfication levels and thus between three information levels: presence and frequency of certain quantitative attributes or sequences, the frequency of these sequences with minimum relevancy or weighted frequency according to the relevancy of the quantitative sequence. Note that this framework also generalizes the crisp sequential pattern definition and that it allows mining of binary data. The algorithms we present, i.e. SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY, have been implemented and tested, thus highlighting the benefits of our novel approach and the feasibility with respect to the fuzzy methods described. The user can thus handle three fuzzification levels thanks to our three different algorithms. This choice allows extraction of frequent sequences through a trade-off between relevancy and performance. Experiments have highlighted that this work could be applied to different kinds of data and there are many prospects.

Several extensions could indeed be investigated. More particularly, we plan to apply this framework to the various proposals of incremental fuzzy sequential pattern mining presented in [START_REF] Goswami | A fuzzy data mining algorithm for incremental mining of quantitative sequential patterns[END_REF]. We also plan to study the extension of our framework to take temporal constraints proposed in [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF] into account to mine fuzzy generalized sequential patterns.

Example 6 :

 6 The sequence S =< ([soda, lot][candy, lot]) ([video games, little]) > groups together 3 fuzzy items into 2 itemsets. It is a fuzzy 2-3-sequence.

  Fig. IV highlights the frequency found for Ix in each case:

ALGORITHM

Fig. 2 .

 2 Fig. 2. Storage of sequences as a prefix-tree

Fig. 3 .

 3 Fig. 3. Number of frequent sequences according to minF req depending on the aggregation operator for ob5rec100I10

Fig. 4 .

 4 Fig. 4. Runtime according to minF req for ob5rec100I10

Fig. 5 .

 5 Fig. 5. Number of frequent sequences according to minF req for ob5rec100I10

Fig. 6 .

 6 Fig. 6.Runtime according to the number of records in the datasets, minF req=0.6

Fig. 7 .

 7 Fig. 7. Runtime according to minF req for TOTALLYFUZZY (ω = 0.7) and [10] for ob5rec100I10

  [1000,[START_REF] Kuok | Mining fuzzy association rules in databases[END_REF] and[990,[START_REF] Kuok | Mining fuzzy association rules in databases[END_REF]) with a very relevant frequency (resp. 88.44% and 91.46%) are found by TOTALLYFUZZY and not by the method of Hong et al., they are in fact deleted during the preprocessing step.

Fig. 8 .

 8 Fig. 8. Number of sequential patterns extracted by

Fig. 9 .

 9 Fig. 9.Progressive fuzzy sets for quantities between 1 and 100 in ob5rec100I10Q100

Fig. 10 .

 10 Fig. 10. Number of sequential patterns extracted by TOTALLYFUZZY and MINIFUZZY for ob5rec100I10Q100

Fig. 11 .

 11 Fig. 11. Runtime of TOTALLYFUZZY and MINIFUZZY for ob5rec100I10

Fig. 12

 12 Fig. 12 shows the runtime time according to minF req. Note that the extraction time increases as minF req decreases.

Fig. 12 .

 12 Fig. 12. Runtime according to minF req for 79756 sequences

Fig. 13 .

 13 Fig. 13. Number of frequent sequences according to minF req for 79756 sequences

Fig. 14 .

 14 Fig. 14. Runtime according to the number of sequences in the datasets, for minSupp=0.2%

  , lot][#letter, lot]) ([#letter, few]) ([#sign, lot][#letter, lot])> (42%), <([#sign, lot][#letter, lot]) ([#sign, medium]) ([#sign, lot][#letter, lot])> (42%)).

Fig. 15 .

 15 Fig. 15. Fuzzy sets for fuzzy items for intra-name pattern mining

TABLE I TRANSACTIONS

 I FOR THE FUZZY PARTITION Candy

	Customer	Date	little	medium	lot
	C1	d1	0.6	0.4	0
	C1	d2	0	0.7	0.3
	C1	d3	1	0	0
	Max(C1)		1	0.7	0.3
	C2	d1	0	0	0
	C2	d2	0	0.5	0.5
	C2	d3	0	0.3	0.7
	Max(C2)		0	0.5	0.7
	C3	d1	0	0.6	0.4
	C3	d2	0.9	0	0
	C3	d3	0	0.2	0.8
	Max(C3)		0.9	0.6	0.8
	Count	(Σ(Max))	1.9	1.8	1.8

TABLE III MEMBERSHIP

 III DEGREES FOR CUSTOMER 1

							Items
		candy			toothpaste		soda		ball			videogame
	D.	li.	L.	li.	m	L.	li.	L.	f.	L.	f.	m.	L.

TABLE IV MEMBERSHIP

 IV DEGREES FOR CUSTOMER 1 AND FUZZY FREQUENCIES FOR ITEMSET Ix

							Items
		candy			toothpaste		soda		ball			videogame
	D.	li.	L.	li.	m	L.	li.	L.	f.	L.	f.	m.	L.

  CalcFuzzyFreq, Algorithm 1, which calls the function FindFuzzySeq, which is either F indSpeedySeq, F indM iniSeq or F indT otallySeq depending on the expected information level. These functions are detailed in Sections IV.To illustrate these methods, we again use the membership degrees of customer 1's transactions. The different frequencies of the sequence Sx=< ([candy, little])([soda, lot]) > are highlighted in TableV.

ALGORITHM 1 -CalcFuzzyFreq Input: gS, candidate g-k-sequence ; Ouput: F F req fuzzy frequency for the sequence gS ; F F req, nbF req, m ← 0 ; For each object o ∈ O do m ← FindFuzzySeq(g-S, Ro); nbF req += m ; End For F F req ← nbF req/|O|; return F F req;

Table IV ,

 IV with a threshold ω= 0.2. This is summarized in TableVI.

TABLE VI ILLUSTRATION

 VI OF TOTALLYFUZZY ON C3 pth1 : (∅, ([candy, little]), 0)First, the process is initialized by creating one empty path pth1 = (∅, ([candy, little]), 0) (TableVI, row 1). Then it begins by scanning the first record of customer 1, d1. The currently searched itemset curIS is found with a degree d1[candy, little]=0.25 ≥ ω. The path pth1 is so updated with As this transaction does not contain the next itemset for pth1, the scan of the dataset should continue. Before that, an optimization is carried out to avoid having to use to much memory space: for two paths at the same step, only the one with the best curDeg value is kept. Here we have pth1.curDeg < pth2.curDeg so pth1 is deleted and the scan of the next transaction continues with pth2 (Table VI, row 3).

	After d1	pth1 : (< ([candy, little]) >, ([soda, lot]), 0.25)
	After d2	pth1 : (< ([candy, little]) >, ([soda, lot]), 0.25)
		pth2 : (< ([candy, little]) >, ([soda, lot]), 0.5)
	Opt.	pth1 is deleted
	After d3	pth2 : (< ([candy, little]) ([soda, lot]) >, ∅, 0.5), closed
		pth3 : (< ([candy, little]) >, ([soda, lot]), 0.5)
	After d4	pth2 : (< ([candy, little]) ([soda, lot]) >, ∅, 0.5), closed
		pth3 : (< ([candy, little]) ([soda, lot]) >, ∅, 0.5), closed
		pth4 : (< ([candy, little]) >, ([soda, lot]), 0.5)
		pth5 : (< ([candy, little]) >, ([soda, lot]), 0.75)
	Opt.	pth3 and pth4 are deleted
	After d5	pth2 : (< ([candy, little]) ([soda, lot]) >, ∅, 0.5), closed
		pth5 : (< ([candy, little]) > ([soda, lot]) >, ∅, 0.63), closed
		pth6 : (< ([candy, little]) >, ([soda, lot]), 0.75)
	Opt.	pth2 is deleted
	After d6	pth5 : (< ([candy, little]) > ([soda, lot]) >, ∅, 0.63), closed
		pth6 : (< ([candy, little]) > ([soda, lot]) >, ∅, 0.87), closed
	Opt.	pth5 is deleted
	C3 deg.	0.87
	Transaction	d3	is	then	checked.	It	contains
	pth2.curIS	=

pth1.seq ←< ([candy, little]) >, pth1.curIS ← ([soda, lot]) and pth1.seq ← 0.25 (Table VI, row 2). Then transaction d2 contains the first sequence of the candidate sequence g-S, ([candy, little]). So a new path is created, pth2 ← (< ([candy, little]) >, ([soda, lot]), 0.5). ([soda, lot]).

  5 -UpdateInput: pth, path to update pth.seq ← pth.seq ∪pth.curIS ;

	If (pth.curIS.next = ∅) Then
	pth.curIS ← pth.curIS.next ;
	Else
	close(pth);
	End If
	ALGORITHM 6 -Optimize
	Input: P aths, list of paths to reduce
	For each pth ∈ P aths do
	While ((P aths.hasnext())) do pth ′ ← P aths.next() ;
	If (pth ′ .currIS = pth.currIS) Then If (⊙(pth.curDeg) ≥ ⊙(pth ′ .curDeg)) Then
	delete(pth ′ );
	Else
	delete(pth);
	End If
	End If
	End While
	End For

TABLE IX PARAMETERS

 IX

		FOR SYNTHETICAL DATABASES GENERATION
	R	Number of records in the database
	O	Number of objects in the database
	I	Average number of items by transaction
	X	Number of possible items in the database
	Q	Maximum quantity value
	P	Number of fuzzy sets by item

TABLE X PARAMETER

 X VALUES FOR SYNTHETIC DATASETS IN EXPERIMENTS

	Name	O	R	I
	ob5rec100I10	5,000	100,000	10
	ob5rec200I10	5,000	200,000	10
	ob5rec250I10	5,000	250,000	10
	ob5rec350I10	5,000	350,000	10
	ob5rec450I10	5,000	450,000	10
	ob5rec500I10	5,000	500,000	10
	ob10rec250I10	10,000	250,000	10
	ob10rec500I10	10,000	500,000	10

TABLE XI NUMBER

 XI OF FREQUENT ITEMS EXTRACTED BY TOTALLYFUZZY (ω=0.7) AND HONG AND AL. METHOD, FOR minF req = 60% ON OB5REC100I10 DATABASE.

	Frequent fuzzy items	TOTALLYFUZZY(ω=0.7) Hong and al.
	[960, 1]	65.12%	65.12%
	[970, 1]	74.32%	74.32%
	[980, 1]	85.36%	85.36%
	[980, 3]	73.18%	not found
	[990, 1]	97.24%	97.24%
	[990, 2]	70.28%	not found
	[990, 3]	91.46%	not found
	[1000, 1]	95.94%	95.94%
	[1000, 2]	66.76%	not found
	[1000, 3]	88.44%	not found
	Nb of frequent items	10	5

TABLE XII DATABASE

 XII TRANSLATION FOR INTRA-NAME PATTERN MINING

	Mining formalism		trademark database
	object	↔	a trademark
	timest amp	↔ number of the word in the trademark
	fuzzy item	↔	# of signs, letters, figures,
			punctuations or symbols in this word