Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3208

Re: document classification problem?

Show all headers | View raw

Arun Jayapal wrote:
>     HB Lead Pencil,C
> But it the transaction file the corresponding item can appear as:
>     20Nos Stadler 1.5 HB Lead Pencil

> Given all these problems how should you write a computer program to solve
> it?

One approach, assuming that the text in the master.ItemName column tends to be 
a subset of the more verbose text in the transaction file, and assuming that 
the word order is likely to change (e.g "20Nos Stadler 1.5 HB Lead Pencil" or 
"Lead Pencil, 20Nos Stadler 1.5 HB") is as follows:

Split each master.ItemName string into words separated by spaces and 
punctuation (discarding the spaces and punctuation).  Sort, reassemble into a 
space-separated string.  Only needs to be done once.

Do the same for the data in the transaction file.

For each item in the (munged) transaction file calculate the edit distance to 
each of the entries in the (munged) master file.  Note: this is O(n^4).  Be 
careful how you calculate the edit distance.  Don't just Google for "Edit 
distance" (or "Levenshtein distance") and use the first implementation you 
find.  It won't be suitable.  You need a version which does /not/ use 
replacement (i.e. considers only insertions and deletions), or equivalently 
gives a weight of 2 to replacement operations.  Secondly it should give a low 
weight (I think 0 would work but I've never tried it) to deletions from the 
(more verbose) string in the transactions file.  Thirdly it should be an 
algorithm that is able to take a "maximum" value for the distance and stop 
prematurely if it can prove that the distance is greater than the given 
maximum; that should reduce the problem to something more like O(n^3). One 
suitable algorithm is described in:

    An O(NP) Sequence Comparison Algorithm
    Sun Wu, Udi Manber, Gene Myers & Webb Miller
    Information Processing Letters, vol. 35, pp. 317-323, 1990.

which used to be online at:

    http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps

maybe you can find a copy in waybackmachine, or via citeseer.

The pairs with the lowest edit distance (or the lowest value of edit-distance / 
length of master string) and the most promising candidates for a match.

If the transactions file nearly always has (most) of the same words in (mostly) 
the same order then you can skip the sorting stages.

It might be more efficient to calculate the edit distance between arrays of 
words (the space-separated sub-strings) using simple string equality to compare 
two strings, instead of running the algorithm on the characters in the strings.

Another possibility is to try a sort of "convolution" algorithm.  To compare 
one string with another, just slide the shorter across the longer noting for 
each step how many characters match their counterparts in the other string. 
Take a total of that.  The pairs that have the highest totals are the best 
candidates for a match.

There are many, many, possible other approaches (there's a /vast/ literature on 
indexing, approximate search, and data warehousing).  It may be possible to 
build an index on your master file in such a way that you could try to match an 
entry from the transactions file in some accelerated time -- say O(log(n)), 
which would make the whole thing O(n log(n)).  I don't know of a good data that 
will do that directly (mostly the needle-in-a-haystack problem is the other way 
around: search a lot of long texts for relevance to a single short text). 
However, it might well be worth a quick experiment with something like Lucene: 
put all you master table entries as texts into a Lucene database, and try 
matching the transaction file entries against that.

I suspect, though, that if you want to go the indexing route then you'll have 
to do something less conventional.  Maybe build a map/dictionary/table of words 
in the master file ("pencil", "HB", etc) to the set of rows in which it 
appears.  Then for each word in a record from the transaction file, looks to 
see which rows in the master file contain that word.  The record(s) with the 
largest number of matched words (over some fixed minimum) are the best 
candidates.  Don't index or lookup words like "the".

This has come out in the wrong order :-(  The later suggestions are simpler to 
try and will work faster (if they work [well enough] at all).  So try Lucene 
first, then the index, and only if they don't work, try one or another of the 
other two.  And, of course, any other suggestions that you may receive.

    -- chris 

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

document classification problem? Arun Jayapal <deostroll@gmail.com> - 2013-03-29 03:10 -0700
  Re: document classification problem? "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-03-29 12:44 +0000
    Re: document classification problem? Arun Jayapal <deostroll@gmail.com> - 2013-04-09 12:06 -0700
  Re: document classification problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-03-29 14:48 +0000
  Re: document classification problem? Torsten Eichstädt <torsten.eichstaedt@FernUni-Hagen.de> - 2013-03-30 12:51 +0100
    Re: document classification problem? "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-03-30 16:15 +0000
      Re: document classification problem? Torsten Eichstädt <torsten.eichstaedt@FernUni-Hagen.de> - 2013-03-31 17:27 +0200
        Re: document classification problem? "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-04-06 14:06 +0100
  Re: document classification problem? Arun Jayapal <deostroll@gmail.com> - 2013-04-09 12:05 -0700

csiph-web