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

Groups > comp.programming > #3207 > unrolled thread

document classification problem?

Back to article view | Back to comp.programming

Contents

  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

#3207 — document classification problem?

Hi,

I have an interesting problem. It goes like this:

I have a list of "ideal" product names; each product is linked to some code (say class A, B, C etc. You can imagine anything for a product name like for e.g. a csv file of such a file would look like the follows:

---
ItemName,Class
Philips Plasma LED TV - Model 45321Q,A
Angle Bracket 1.0" x 2.25" x 4.0",B
Spray Paint - Black 150 ml,C
...
.
.
---

Please visualize the above as a table. The above file is what I call the master file. It can contain millions of records.

Next I am given a dump of invoices which contain item names. The goal is to apply "class" to each invoice line item description. 

However the data you see an invoice line item isn't exactly what you'd get in the master file. It can contain so many other attributes describing the item. To explain the scenario, take the case of a simple pencil:

The entry in the master file may go like:

---

ItemName,Class
...
...
HB Lead Pencil,C
...
...

---

But it the transaction file the corresponding item can appear as:

20Nos Stadler 1.5 HB Lead Pencil


It can appear to be jumbled up in any order. Hence there will never be a direct match. But still a human can gets hints and probably classify that item with class 'C'.

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

-arun

[toc] | [next] | [standalone]

#3208

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 

[toc] | [prev] | [next] | [standalone]

#3236

Hi,

Splitting the item names in the master and in the transaction seems to be the right approach. Additionally we remove instances of stop words which can appear in the item names as such (like 'the', 'with', etc).

But now we have found an issue with spelling variations in the split string output (we call it tokens). Now even before we munge the item names we want to do a spell correction. The normal business of spell correction is to put the words in a trie from which distance calculations can be easily done.

But this requires a list (or an English dictionary of sorts). I am not saying that an actual Merriam Websters or Oxford English dictionary will be appropriate; we'd need to build one that "represents the population"?

Ideally what I imagined is we'd prepare a list of words studying the item names and test this list against the population (list of tokens we get out of splitting item names). I'd take a statistic - i.e. a ratio of words (derived from master.itemname) which actually has matches (either direct or distance based) to the total number of tokens in the population. I might get a percentage out of it. If the percentage is low it means that this list isn't representative - it needs more tokens (ideal forms) added to the list, some tokens have to be excluded (stopped). I have to do this process repeatedly until I have a satisfiable percentage on the list.

So this is kind of an iterative process. My question at the moment is can be somehow automate this process? Or is this a process that would definitely need human intervention?

-Arun

On Friday, March 29, 2013 6:14:51 PM UTC+5:30, Chris Uppal wrote:
> 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

[toc] | [prev] | [next] | [standalone]

#3209

Arun Jayapal <deostroll@gmail.com> writes:
<snip>
> I have a list of "ideal" product names; each product is linked to some
> code (say class A, B, C etc. You can imagine anything for a product
> name like for e.g. a csv file of such a file would look like the
> follows:
>
> ---
> ItemName,Class
> Philips Plasma LED TV - Model 45321Q,A
> Angle Bracket 1.0" x 2.25" x 4.0",B
> Spray Paint - Black 150 ml,C
> ...
<snip>
> Next I am given a dump of invoices which contain item names. The goal
> is to apply "class" to each invoice line item description.
<snip>
> The entry in the master file may go like:
>
> ItemName,Class
> ...
> HB Lead Pencil,C
> ---
>
> But it the transaction file the corresponding item can appear as:
>
> 20Nos Stadler 1.5 HB Lead Pencil
<snip>
> Given all these problems how should you write a computer program to
> solve it?

I can give you some hints about a method I've used with some success:

You split and normalise both descriptions into "tokens" and discard any
that are unlikely to be useful in matching.  In natural language, these
might be short words like "a" but in your case there may be none that
you discard.  The normalisation can be done ad-hoc as you test the
system but its purpose is simply remove irrelevant detail.  For example,
you might map everything to lower case, or you might combine and convert
units (150 ml becoming 0.15l maybe).

Your master file is indexed by these tokens (I used a hash table) and
you score each entry for every matching token in the invoice.  So when
you see "lead" you might see that two entries now have a positive score:

  HB Lead Pencil,C
  lead pipe,B

Each new token will add some more possible entries whilst modifying the
scores of others.  Seeing "pencil" increases the score of the first
entry but it also might add a new (currently low-scoring) entry for
"Pencil sharpener".

The scoring can also be endlessly fine tuned.  If you add 1 for every
match and -oo for every non-match you get one very simple metric, but in
my case I found that scoring that was weighted by the length of the
token helped: a match for "evaporated" was more important than one for
"milk".  You, for example, might weight model numbers over colours.  A
45321Q is likely to be a specific TV, but a "black tv" could be any
number of TVs.

I've used lots of different metrics.  For example, a proportional one
can sometimes be useful.  A match the covers a greater proportion of the
(weighted) value of the tokens might be better than one that includes
more but in a longer description.  You might also weight the tokens by
the their position.  I found that to help when there is a "headline"
token:  "Pencil, lead, HB 2" makes "pencil" the most important token to
match.

You can keep this scheme very clean with easily separable tokenising and
scoring modules.  This makes it easy to experiment and to fine-tune.
What works best will depend on your application's reaction to false
positives and false negatives.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#3212

Author: Steven Bird, Ewan Klein & Edward Loper
Title: Natural Language Processing with Python
Sub: Analyzing Text with The Natural Language Toolkit
Publisher: O'Reilly
Year: 2009
Website: http://www.nltk.org

It should be obvious that you're asking for working solutions on a domain 
that is by far not understood and subject of heavy research.  Nevertheless, 
if a 85%-95% solution satisfies you, you'll be able to program that with 
NLTK.

Any good introductory book on Computer Linguistics will help you getting 
started to learn the basics of the underlying problems.  Important IMHO to 
be able to estimate what such a toolkit can do and what not, and why.
-- 
=|o)

[toc] | [prev] | [next] | [standalone]

#3214

Torsten Eichstädt wrote:

> It should be obvious that you're asking for working solutions on a domain
> that is by far not understood and subject of heavy research.
> Nevertheless, if a 85%-95% solution satisfies you, you'll be able to
> program that with NLTK.

I doubt if computer linguistics would help as much as one might hope.  To me 
this seems like a fuzzy, patern-matching, problem (as in "data cleansing") 
which people are good at (they have to be since they /define/ what "good" means 
;-) rather than a linguistic (or even AI) problem, even though people are 
/also/ good at those.

But even so, I agree that the OP(Arun)'s "asking for working solutions on a 
domain that is by far not understood and subject of heavy research" -- although 
I differ about what that domain /is/ ;-)

    -- chris 

[toc] | [prev] | [next] | [standalone]

#3215

Chris Uppal wrote:
> I doubt if computer linguistics would help as much as one might hope.  To
> me this seems like a fuzzy, patern-matching, problem (as in "data
> cleansing") which people are good at (they have to be since they /define/
> what "good" means ;-) rather than a linguistic (or even AI) problem, even
> though people are /also/ good at those.

Nes.  Jo.  It's clear that _some_ (simple?) linguistic problems of (written) 
natural language can be solved with fuzzy pattern matching.

But consider examples like these:
booked:     "Universal Cleaning Fluid _special_ for CD/DVD, $19,99"
delivered:  "Spiritus/Alcohol (med.), 1/2 Gal., $1,27 (please re-label)"

A few bits of AI & CL could be able to see that's the same.

  "Ink Cartridge (refilled), black, #2743, 100 ml, Pencil Inc."
  "Refund pencil leads, black ink, 100 pcs"

"Dumb" fuzzy pattern matching could falsely tell you that's likely similar 
by 85%, but applied AI & CL would tell you it's very likely s/th different.

  paper - paper white (sheets - colour, different)
  product - brand name only (the same, e.g. in german "tissue" = "Tempo")
  compound words (can be very different from their parts)
  ...
  the list is quite long where lack of AL & CL will give you wrong results.

You have to ask yourself how much you want, estimate the effort, and 
estimate if the domain (of words and terms) is tight or large.  For a tight 
domain, you might be successful w/o full-featured CL, you can program the 
missing bits yourself, step-by-step.
-- 
=|o)

[toc] | [prev] | [next] | [standalone]

#3226

Torsten Eichstädt wrote:

> > I doubt if computer linguistics would help as much as one might hope.
> > To me this seems like a fuzzy, patern-matching, problem (as in "data
> > cleansing") which people are good at (they have to be since they
> > /define/ what "good" means ;-) rather than a linguistic (or even AI)
> > problem, even though people are /also/ good at those.
>
> Nes.  Jo.  It's clear that _some_ (simple?) linguistic problems of
> (written) natural language can be solved with fuzzy pattern matching.
>
> But consider examples like these:
> booked:     "Universal Cleaning Fluid _special_ for CD/DVD, $19,99"
> delivered:  "Spiritus/Alcohol (med.), 1/2 Gal., $1,27 (please re-label)"

I see what you mean.  Also the fact that Ben Bacarisse said elsethread:
> The scoring can also be endlessly fine tuned
suggests that beyond a certain point you'd be better off with something with 
[some approximation to] "insight" rather than fiddling with ad-hoc weightings.

My own small brushes with data-matching/cleaning have all been in the area of 
addresses (places where people live, not RAM ;-) where there is both a lot more 
structure (hierarchical) and a fair bit more redundancy (e..g postcodes or zip 
codes) to reduce the need for "insight".

    -- chris 

[toc] | [prev] | [next] | [standalone]

#3235

On Friday, March 29, 2013 3:40:02 PM UTC+5:30, Arun Jayapal wrote:
> Hi,
> 
> 
> 
> I have an interesting problem. It goes like this:
> 
> 
> 
> I have a list of "ideal" product names; each product is linked to some code (say class A, B, C etc. You can imagine anything for a product name like for e.g. a csv file of such a file would look like the follows:
> 
> 
> 
> ---
> 
> ItemName,Class
> 
> Philips Plasma LED TV - Model 45321Q,A
> 
> Angle Bracket 1.0" x 2.25" x 4.0",B
> 
> Spray Paint - Black 150 ml,C
> 
> ...
> 
> .
> 
> .
> 
> ---
> 
> 
> 
> Please visualize the above as a table. The above file is what I call the master file. It can contain millions of records.
> 
> 
> 
> Next I am given a dump of invoices which contain item names. The goal is to apply "class" to each invoice line item description. 
> 
> 
> 
> However the data you see an invoice line item isn't exactly what you'd get in the master file. It can contain so many other attributes describing the item. To explain the scenario, take the case of a simple pencil:
> 
> 
> 
> The entry in the master file may go like:
> 
> 
> 
> ---
> 
> 
> 
> ItemName,Class
> 
> ...
> 
> ...
> 
> HB Lead Pencil,C
> 
> ...
> 
> ...
> 
> 
> 
> ---
> 
> 
> 
> But it the transaction file the corresponding item can appear as:
> 
> 
> 
> 20Nos Stadler 1.5 HB Lead Pencil
> 
> 
> 
> 
> 
> It can appear to be jumbled up in any order. Hence there will never be a direct match. But still a human can gets hints and probably classify that item with class 'C'.
> 
> 
> 
> Given all these problems how should you write a computer program to solve it?
> 
> 
> 
> -arun

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web