Gal A. Kaminka: Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Mining and Classification of Multivariate Sequential Data

Ariella D. Richardson. Mining and Classification of Multivariate Sequential Data. Ph.D. Thesis, Bar Ilan University, 2011.

Download

[PDF]1.4MB  

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-frequencyhinders 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.

Additional Information

BibTeX

@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. 
 },
}

Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:51