@COMMENT This file was generated by bib2html.pl version 0.94
@COMMENT written by Patrick Riley
@COMMENT This file came from Gal A. Kaminka's publication pages at
@COMMENT http://www.cs.biu.ac.il/~galk/publications/
@PhdThesis{ariella-phd,
author = {Ariella D. Richardson},
title = {Mining and Classification of Multivariate Sequential Data},
school = {{B}ar {I}lan {U}niversity},
year = {2011},
wwwnote = {},
OPTannote = {} ,
abstract = { Multivariate sequence mining and classification are important and challenging tasks.
They can be applied to numerous domains including medical diagnosis, handwriting
deficiency diagnosis, identification of users for security or personalized TV services,
and even transportation and traffic planning. The problem we address in this dissertation is
classification of multivariate sequences. Multivariate sequences are sequences
that have multiple attributes for each item in the sequence. Several attempts to address
this problem exist, but none provide a full solution. One type of solution to this
problem is to reduce the solution to a single attribute or non sequential problem while
loosing valuable information. Other solutions address both the multivariate and the
sequential aspect of the input but provide an unscalable solution.
In this dissertation we first present COACH (Cumulative Online Algorithm for
Classification of Handwriting deficiencies). COACH is a classification algorithm
for multivariate sequences that uses heuristics to combine several single attribute
classifications. COACH is evaluated on real data obtained from children with poor
handwriting using a digitizer tablet. Results show that COACH manages to successfully
differentiate between poor to proficient handwriting. Integrating several
single attribute classifications encouraged us to search for a solution that uses all the
attributes together in the classification process.
The second part of the dissertation introduces frequent sequence mining. Frequent
sequence mining, as well as being a challenging and interesting task, can be used for
classification as we will show in the third part of the dissertation. Many algorithms
have been proposed to efficiently address frequent sequence mining. Most of them
use support based mining to achieve this task. However, support based mining has
been shown to suffer from a bias towards mining short sequences. We will show how
resolving this bias produces better sequences than traditional support based mining.
We present REEF, a frequent sequence mining algorithm that resolves this length
bias. We define norm-frequency, based on the statistical z-score of support, and
use it to replace support based frequency. Unfortunately the use of norm-frequency
hinders pruning. We address this issue and introduce a bound to perform pruning.
Calculating the norm-frequency requires a preprocessing stage performed on a sample
of the database. Values acquired from the sample suffer from a distortion. We analyze
this distortion and correct it.
Experimental results on synthetic and real world data presented in this dissertation
establish that REEF overcomes the short sequence bias successfully. Mining
performed with REEF on textual data is used to demonstrate that the sequences
mined with REEF are more meaningful than those mined with support based algorithms,
indicating that REEF is better than traditional algorithms for producing
interesting sequences.
Finally in the third part of the dissertation we use the new mining algorithm
REEF to develop CUBS (Classification Using Bounded Z-Score with Sampling) a
classification algorithm for multivariate sequences. CUBS uses the REEF mining to
produce frequent subsequences, and then selects among them the statistically significant
subsequences to compose a classification model. We evaluate the accuracy of
CUBS on a synthetic dataset and on two real world dataset. CUBS provides a scalable
classification algorithm for multivariate sequence classification that makes use of
both the multiple attributes and the sequential nature of the data.
},
}