ELEN E6880 - Summer 2003

The goal of this project is to provide significant experience employing a number of different learning algorithms over a real-world, complex dataset.  The challenge in this project is to choose the most effective preprocessing of the data into feature vectors for classification, and then to choose an effective algorithm applied in an effective way to this data.

In this html file you will find:

• A description of the data
• A statement of the problem to solve
• A description of the objectives and deliverables of the project
• A list of resources, including SW and the data

Data Description (Updated 03/17/2002)

Our goal is  to recover a sequence of user's actions, or high-level commands, also called  transactions, from a sequence of low-level commands, called Remote Procedure Calls (RPCs), which are recorded in a server log-files.

There are various reasons why we may want to do that.  For example, we may want to model user behavior in order to predict his future actions (e.g., buyer vs. non-buyer on a web-page) and adapt the web-site behavior to the particular user's interest, attract potential buyers, or simply have a more realistic user behavior model in order to better test an application or manage its performance.
Unfortunately, it is hard to obtain the infromation about user' actions directly, since this requires additional instrumentation of the client side (i.e., modifying a web-browser and/or asking a user click a button before and after he is going to do some high-level ''action'', which is clearly not realistic).

Luckily for us, there is practically unlimited amount of historic data on server, where the data contain the sequence of RPCs being executed on server. Every user transaction execution leads to a sequence of RPC calls.  Hence, although we do not have information on transactions, we have a lot of sequences of RPC calls.
However, a sequence of RPC calls corresponding to a specific transaction is not deterministic, since it depends on the current state of both client and server (i.e., whether certain databases are already opened or not), on the parameters of the  transaction (e.g., how many records must be deleted from a database), and on other sources of uncertainty.
Thus, we wish to learn a classifier that would be able to recognize a transaction type from a given sequence of RPCs that were invoked when executing this transaction.

We obtained a set of data labeled by an application expert, which give us instances of RPC sequencs with the corresponding transaction types.
 

Data format (updated 03/17/2002)

1. the value in the first column is the unique transaction number, the value in the second column is RPC identifier; the value in the third column is a transaction label.
2. a sequence of successive rows having the same transaction label correspond to the sequence of RPCs invoked during a specific transaction of the type described by the label.
3. RPCs belonging to the same transaction (see 2. above) are listed in the order in which they were invoked.
4. the sequences of RPCs belonging to an individual transaction is listed in a contiguous range of rows, namely, the data for two different transactions is not intermixed
5. the number of RPCs within an individual transaction varies, even across transactions of the same type.
6. there is no time information in the file; the only time-related information you have is within individual transactions, where the sequence of RPCs is invoked in order starting from the top one.
7. the data contains instances of all the 32 different transaction types
8. the data contains instances of all the 59 RPC types.

4 49 20
4 44 20
4 42 20
4 41 20
4 22 20
4 9 20
5 57 27
5 57 27
5 55 27
5 16 27
5 26 27
5 46 27
5 57 27
6 57 27
6 57 27
6 55 27
6 16 27
6 26 27
6 46 27
6 57 27

the data must be interpreted as follows

1. the top 6 lines correspond to an instance of transaction of type 20 (identified as the 4th transaction in the file by the number 4 in the first column), the next 7 lines correspond to a transaction of type 27 ( the 5th transaction in the file), and the last 7 lines correspond to another transaction of type 27 (the 6th transaction in the file)
2. the first transaction (of type 20) consisted of the following sequence of RPC calls: 49 44 42 41 22 9,  in this order.

the second transaction (of type 27) consist of the following sequence of RPC calls:  57 57 55 16 26 46 57, in this order
the third transaction (also of type 27) consists of the following sequence of RPC calls: 57 57 55 16 26 46 57,  in this order, and is identical to the previous one

Problem Statement

 Problem nr 1: for everyone

15 points for this part (note: with this part alone you can achieve a score of 105% for the entire class).

Problem nr 2: for all who want to do extra work for extra points

10 points for this part (note: since this is extra work, which you might want to do if you feel your grades need a boost, we will grade this part more strictly than problem nr 1: if you decide to address problem nr 2, do it seriously: there is no bonus point for a bad piece of work).
 

Additional Bonus

Project Objectives and Requirements (aka: what you are suppose to do)

1. You hypothesize some method(s) for feature extraction and some choice of induction method(s) and method(s) of evaluation.
2. You write some code for the data preprocessing, and possibly for the execution and evaluation.
3. You run classification learning and testing experiments.

First Deliverable: a journal of your progress, in soft copy (simple text, LaTeX/PS/PDF, or Microsoft Word only)  This deliverable is meant to show that you worked at the problem - it should tell me the story of your struggle to produce the second deliverable.

1. The high-level objectives with the experimental design (e.g. reduce number of features, by removing unrelated features, and by hand creating linear combinations of related features.)
2. A description of the specific approach taken.  (E.g. the method used to determine if a feature is irrelevant.)
3. The code and parameter settings used in the experiment.
4. The results of the experiment.
5. The conclusions you have drawn from the experiment.  (E.g. the performance is slightly worse than the last experiment, but we don’t know if this effect is from the removal of features or the hand-combining of the features.)

Teams of two or three students are encouraged to work together so that each team will be able to perform a number of these iterations, and so that each team will have multiple sources of input for choosing effective strategies.  The journals are intended to be relatively informal; the writing of the journal itself should not significantly impact the time it takes to complete each iteration of the cycle above.  Document parts (3) and (4) above may require that separate source code files, configuration files, and results files be included with the report.  For your convenience we will directly accept these data files, configuration files, and results files from each run in rather unprocessed form.  The goal is to allow you to quickly document that the experiment was carried out, without requiring that you to massage all these pieces into a report.  When possible it would be preferable if you can simply cut and paste relevant data into the report or an appendix to the report.  Otherwise the report must at least mention the external data files by name and describe what they represent.

Second Deliverable:  a report of your conclusions, in soft copy (simple text, LaTeX/PS/PDF, or Microsoft Word only) THIS IS THE IMPORTANT DELIVERABLE: be

1. the approaches your team attempted on the problem
1. description of feature construction - why did you come up with your features
2. description of feature selection - why did you select the features you selected
3. description of  classifier selection - why did you select the classifiers you selected
   
2. your analysis of the approaches taken
1. how did you set up the experiments?
2. what where the results of  the experiments?
3. what are your conclusions regarding the features and the classifiers given the experimental results?
   
3. your analysis of the domain itself as consequence of your overall work

1. You should come up with a variety of features - and you should motivate your choices
2. You should select a good variety of classifiers from the off-the-shelf available ones
3. You should compare different classifiers as well as different variants of the same classifiers, wherever appropriate (for example, if you use Neural Networks, you should see what happens when you vary the number  of hidden nodes) or use model-selection techniques (for example, instead of selecting different number of hidden nodes, use model-selection techniques to select the number of hidden nodes)
4. You should clearly describe the experimental settings
5. If you feel adventurous, you could even build your own classifier
   

Resources

Data

• the dataset will be used only for the project of the ELEN E6880 course, and will be deleted afterwards.
• the dataset cannot be distributed, in its present form or in any modified form, to anybody who is not currently enrolled in the ELEN E6880 course.

Software

• For Matlab Users
• Free Matlab Classification Toolbox at http://tiger.technion.ac.il/~eladyt/Classification_toolbox.html. NEW, Modified toolbox, FOR CLASS USE ONLY.  Read the file "content.m" for the description of what is new.   In a few words, a lot of the methods have been modified to allow arbitrary input dimensions and arbitrary number of classes. Two methods have been added.
• Netlab:  neural networks in Matlab
• Support Vector Machines Toolbox,  at University of East Anglia
• Bayes Network Toolbox, at Berkeley
NOTE: if you decide to use matlab, you cannot just use Netlab, because it only supports neural networks.
• For Java users
• Weka (follow the "software" link at the top of the page)

Papers

• Eric P. Xing, Michael I. Jordan  Richard M. Karp, "Feature Selection for High-Dimensional Genomic Microarray Data", Proceedings of the Eighteenth International Conference on Machine Learning (ICML2001).
• MORE To Come here.

• The NEC Research Index:  this is a huge archive of papers, with links to pdf and ps files, backwards and forward citations etc.
• The DBLP index: another index of publications, some with links to pdf and ps files.
• Collection of papers on Microarray and Data Analysis  (there are a lot of papers on feature selections hidden around here, but careful: they are for a specific topic...)