Classi cation of sequential data (data obtained from series of actions in chronological order) has many applications in security, marketing or ergonomy. In this paper, we present a tool for classi cation of sequential data. We introduce a new clean dataset of web-browsing logs, and study the case of implicit authenti cation from web-browsing. We then detail more of the functioning of the tool and some of its parameters.
Event-related data can have the form of a succession of actions or events in
chronological order. Data mining of such data has many applications in elds
such as security (intrusion detection [
The enumeration of these patterns alone is not su cient in many cases and is only one step of a decision-making process. For example, in a context of security, one might want to nd meaningful patterns as the rst step of classi cation or prediction. In marketing, one might use patterns to construct groups of consumers or to nd interesting association rules.
In [
In this paper, we present a tool for classi cation of sequential data, based
on closed-patterns. This tool implements the classi er presented in [
This paper is organised as follow: in section 2 we explain the functioning of the classi er and give more details about the tool and its parameters, in section 3 we show a case study and propose a clean dataset for experimentation, nally we conclude and give some perspectives of our work. 2 2.1
General parameters In this section, we describe the classi er implemented by our tool. The tool includes a whole experimental process, from the building of transactions from raw data to detailed results of classi cation. We mention some of the parameters accepted by each steps.
Building transactions Our tool allows us to group the data into transactions. The transactions can be of xed size, or created with respect to a time stamp present in the original data. In our case study, the size is xed and is equal to 10. The data le from where the transactions are built can be of arbitrary size. Extraction of own patterns We call own patterns the patterns we believe to be respresentative of each class. For each class, we compute the patterns that verify some property or threshold for a given metric (e.g. support or tf idf ). With some metrics, the space of those patterns is prunable. The number of patterns we want to keep as well as their maximum size is a parameter. The nature of the pattern is also a parameter: as of today, one can choose between closed itemset or sequence. For a given class c, we denote the set of own patterns by Pc. Pro le of a class There exist di erent ways to compute the pro le of a class. In our tool, we chose to de ne a common vector pro le V = Sc2C Pc that is the union of all own patterns for all classes. We then compute its numerical components for each classes from either the support, the lift or the tf idf . This vector allows us to embed all classes in a common space. This numerical value can be seen as the distance from the origin of the space, in each dimensions of the vector. For exemple, let and two classes. P = fA; B; Cg and P = fC; D; Eg then the vector V = P [ P will have 5 component (A; B; C; D; E). For each class c, we compute a numerical value kic for each component, giving V = (kA; kB; kC ; 0; 0) and V
= (0; 0; kC ; kD; kE ).
Pro le of an anonymous transaction This step accepts the same parameters as the construction of the pro le of a class. We can also choose the number of anonymous transaction that will be submitted to the classi er in the next step. For example, in Fig. 3, the number of anonymous transactions recieved by the classi er goes from 1 to 30.
Identi cation step The goal is to guess the class corresponding to an anonymous set of transactions. After the computation of a pro le for this anonymous set, we compute the nearest neighbor in the common space de ned previously. The tool implements di erent similarity functions: euclidean distance, cosine similarity, Kulczynski measure, and Dice similarity. The heuristics gain in e ciency when they are provided with a higher number of anonymous transactions that allows them to construct a ner pro le for the anonymous user.
Global parameters Other parameters for experimentations include the number of runs, the verbosity level, the format of the data, the possibility to only compute stats on the data, the use of a fuzzy approach and some parameters for binary classi cation.
Bayesian Classi er Our tool implements two smoothed Bayesian classi ers: a traditional Bayes classi er and a pattern-based Bayes classi er. Those classi ers allow to compare the results during the experimentations. 2.2
Fuzzy approach The inclusion of a pattern in a transaction is a binary measure. When working with own patterns of signi cant size, this strict inclusion will often be false. We consider a fuzzy approach for the support during the computation step of an anonymous pro le. We will use a inclusion level instead of a binary measure. The fuzzy support may then be computed as the average of the inclusion levels on the set of transitions.
The fuzzy inclusion level inc(P; T ) can be computed as the proportion of the own pattern P included in the transaction T : inc(P; T ) = jjP \ T jj jjP jj (1) To adjust to di erent cases and be able to represent a wide range of inclusion, from intersection to strict inclusion, we use a transfer function to transform the simple level of inclusion of eq. 1. In the tool, those functions are de ned by specifying points on a 2-dimensional space. Two points are xed, (0; 0) and (1; 1). Some transfer functions are illustrated in Fig. 1.
Intersection 0:5 1 0 1 0:5 0 0 0 0:5 Ratio 0:5 1 1
The coordinates of the two points that de ne the transfer function are con guration parameters. In Fig. 1, the parameters for the inclusion are [(1; 0); (1; 0)]. This is equivalent to the binary measure of inclusion. For the intersection, the parameters are [(0; 1); (0; 1)]. Those parameters mean the measure is equal to one as soon as the intersection is not empty. For the simple ratio or a more sigmoidal function, the parameters are resp. [(0; 0); (1; 1)] and [(0:25; 0); (0:75; 1)]. The parameters are given to the tool by a con guration le in .yml format. For the results of our case study, presented in Table 2, the le is presented in Fig. 2.
With this le as argument, the tool will recieve from 1 to 30 anonymous transactions, and run 10 executions. The random seed can be xed to reproduce experimentations. The data comes from the directory Data/150users, and is in csv format. The transactions are built of xed size 10. The identi cation method is H1 (closed itemsets and tf idf metric), with at most 40 own closed-patterns of maximum size 5. The similarity measure used is Kulczynski. The pro ler is the metric used to compute the numerical coordinate of the common vector. When not speci ed, the method used for inclusion of the pattern is the strict inclusion. 3
Our case study is about implicit identi cation in web-browsing. Implicit identi
cation is studied in [
Data description Our data comes from Blaise Pascal university proxy servers. It consists of 17 106 lines of connection logs from more than 3, 000 users and contains the user ID, the time stamp and a domain name for each line. We applied two types of lters on the domain names: blacklist lters and HTTP-request based lters. We used some lists3 of domain names to remove all domains regarded as advertising. We also ltered the data by the status code obtained after a simple HTTP request on the domain name. After those steps, we still have 4 106 lines. We divide the le between the 3K users to obtain the class les. This dataset is available at http://fc.isima.fr/ kahngi/cez13.zip. The studies were conducted on the 150 users with the higher number of requests. 3 http://winhelp2002.mvps.org/hosts.htm and https://pgl.yoyo.org/as.
Some information about the data is available in Table 1. The table shows
some statistics from before preprocessing and after the lters were applied.
#U sers represent the number of users, #Sites represents the cardinal of the
whole set of websites for all users and Avg#lines/user is the average number of
line per user. We can see that the number of users decreases because some users
did not have a single line after the lters. Roughly 40% of the websites were
deleted by the lters, and the average number of lines by user was divided by 5.
Our tool implements several heuristics. H0 considers frequent 1-patterns with
the best support, H0Lif t considers frequent 1-patterns with the best lift, H1
considers closed k-patterns with the best tf idf , and B is a smoothed Bayes
classi er. The tf idf is a metric that comes from information retrieval and text
mining. It is the product of term frequency and inverse document frequency. It
re ects how discriminating a pattern is for a given class. The experiments in [
Figure 3 shows the kind of results that can be obtained with our tool. The abscissa is the number of anonymous transactions given to the classi er and the ordinate the accuracy of the di erent heuristics. The dataset is divided as follows: 32 of learning base for the learning step and 13 for the identi cation step. The division is random. Each test session consists of multiple runs of both those steps. That allows us to smooth the results by using the average accuracy.
The table generated by our tool contains 15 columns. Those include the number of classes NC , the number of anonymous transactions recieved A, the method used, the average accuracy, the average number of transactions successfully and 0.8 y c rau 0.6 c c a e g reav 0.4 A 0.2 not successfully classi ed, the ratio of classi ed and not classi ed tests, and the run time in second. TC represents the ratio of classi ed tests. All this information allows the analysis of various aspects of the result. Some are presented in Table 2. 4
We presented a tool for classi cation of sequential data. It includes a lot of features in the construction of the transactions, and di erent parameters and heuristics for classi cation. The tool is exible and adaptable to many contexts of classi cation and types of data.
The perspectives of our work are to add others means of classi cation based
on other types of patterns (such as closed-sequences, pattern structures, or class
association rules), and other types of metrics (for example structural metrics
such as stability). We are also considering the use of aggregation functions other
than the average for fuzzy support, such as ordered weighted averaging (OWA)
operators [
This research was partially supported by the European Union's \Fonds Europeen de Developpement Regional (FEDER)" program.