15-721 Database
Management Systems Project
Description
Title:
Data Cleaning on the Plain Text
People: Hubert Chan hubert@cs and Jimeng Sun jimeng@cs
Despite of the
importance of data systems, a large
number of data (e.g.
biological data, scientific data) are still stored in the plain
text where the
records and the fields are separated by
some delimiters (e.g. comma).
Many data mining tasks are performed directly on those data. However,
those data
are usually dirty in a sense that 1) it
contains measurement errors(content
noise); 2) some delimeters are missing
(structure noise). Content noise is
intrisic to the data itself and up to individual data mining
algorithm to deal
with. Structure noise has to be fixed in order to perform any data
mining task.
In this project We focus
on dealing with structure
noise. Or more
specifically, given a text file containing records
that may contain missing
delimiters, we want to reconstruct the records
by putting back the delimiters
into the intended places.
In particular, we restrict the ways in which data can be
dirty to the following:
(1) Delimiters separating fields are missing and so several
fields of a single
record appear as a single field. The task is to identify the
correct places to
segment the data into correct fields.
(2) If a record has a field whose value is missing, it is customary to
represent
the missing field with two consecutive
delimiters. Hence, if one of the
delimiters is missing, the fields of
the record can not be interpreted
correctly. Our goal is to be able to recognize that a
field is missing and
rectify the situation, for example by supplying a null value.
(3) A field can take values in which the special delimiter
character appears.
For example, if comma is used as the delimiter, it is common for
an address to
contain commas as well. The problem is caused by ambiguous use of
the delimiter
character. The task is to distinguish between the
two uses of the delimiter
character, i.e. whether it is used to separate fields or it is just
a character
appearing within a field.
(4) We have implicitly assumed that there is a special character
that separates
records, for example the newline character.
We shall assume at first that
records are always separated and if time permits, extend the
solution to cover
the case when such delimiters can be missing as well.
The goal of the project is to separate out
the data fields. The criteria for
evaluating performance is the percentage of dirty records that
are successfully
cleaned.
SCHEDULE back
Plan of Attack
The Hidden Markov Model (HMM) can be used to model the problem.
For simplicity,
imagine that each field represents a hidden state. The
values of the observed
states are characters in the input file. Hence, the
problem can be rephrased
as: given a sequence of observed states, return the most probable
sequence of
hidden states that is responsible for the observed sequence.
We might also investigate other possible models (e.g. naive
bayes) and compare to see if
it would give interesting results.
Schedule(subject to change)
We plan to start the project on Mar 8, 2004. Here is a tentative
schedule. Note
that the division of work is still subject to
change, and it just reflects
roughly who would be leading which aspects of the project for the
initial stage.
Weeks 1-2 Mar
8 Research on Background
Information
Hubert:
Understand the retails of HMM
Read papers on related problems
Design the structure of HMM specifically for the task
Jimeng: Look into the literature of information extraction
Look for suitable test data
Find suitable software for HMM
Week 3-4 Mar 22
Evaluate the HMM model
Implementing other model for comparison
Week 5 Apr 5 (Milestone)
Continue implementing and the evaluation phase
Week 6 Apr 12
start writing the report
Week 7 Apr 19
finish the report
Week 8 Apr 26
consolidate the result and everything
prepare slides/posters for presentation
Milestone
On the Milestone date, we should have designed the HMM model
specifically
for the problem and implemented it partially.
RESOURCE back
Literature Search (so far)
-
"A Tutorial on Hidden Markov Models and
Selected Applications in Speech Recognition" Lawrence
R. Rabiner
Links:
- Bayes
net toolbox on matlab