ideas on machine-learning algorithms to classify products

Question

I have a list of products, including variables such as the product name (as it appears on the receipt) and the merchant where the product was bought.

I have a good deal of them manually classified into a fixed group of categories (e.g. alcoholic drinks, vegetables, meat, etc.).

The data are, as always, noisy. In this case, particularly noisy because it comes from scanned receipts and OCR on not so good scans is usually very noisy.

I want to play around with algorithms to classify new data, using the two variables above.

There are several major sources of variation here:

• The OCR, which means a product (e.g. chicken) can be found with many different but relatively similar spelling (e.g. chiken, hicken, chicen, ...).
• The same product can have different names, according to the merchant who sold the product. In this case, the names can be either similar or completely different across merchants, but rather similar within every merchant.
• The same product can have very different names within the same merchant (e.g. branded products whose name on the receipt is the brand name, vs. generic names; soft drink vs. coca cola).

I've tried some (kind of naive) classifier, using for example the distance between strings (which tackles mostly the first main source of variation mentioned above), but I am not very happy with the results.

So I wanted to reach out here to ask for ideas on how to tackle this problem. I guess many people have "solved" or at least worked much longer in this kind of problem than I did (a few hours) so I would really appreciate any guidance here.

By the way, I use mostly R, so R-based solutions would be greatly appreciated.

Answer 1

Addressing your issues one by one:

1) OCR: This is probably the easiest of your problems as there are many algorithms that perform well in this task. As a reference, in the best known handwritten digit dataset, MNIST, several algorithms have achieved over 99.5% accuracy (the state-of-the-art being Convolutional Neural Networks). You can also find many out-of-the-box solutions to your problem; it helps a lot if your data is in English, as the tools there are more advanced. If your scans are noisy you may try denoising them first.

2) You need to do some preprocessing for this issue. First I would suggest, if possible, creating a bag of words, i.e. a list of all unique words in your "corpus". Verify that all these words are correct and perform a string distance comparison (e.g. hamming distance) to correct 1-2 letter typos. Another thing I would do would be to calculate the occurrences of each term in your bag and remove the least frequent ones (e.g. terms that occur less than N times in your corpus are probably typos, or remove least frequent M% of your terms). That should significantly reduce the noise in your dataset.

3) In order to solve this issue you need to perform some sort of semantic labelling. If you are familiar with ontologies, their hierarchical structure can help here a lot. You can create rules like "coca-cola" is a "soft drink" which is a type of beverage, etc.

I don't have experience in R, but I'm sure you can find tools to perform all the above quite easily.

Answer 2

It seems that you should define similarity among the entities.

You have plenty of sources for similarity. You mentioned distance on the names (edit distance) and membership in groups. Note that you can extend the similarity by groups to many group and many similarity types. Groups can be belonging to the same recipe, sold by the same merchant, belonging to the same category, etc. Similarity types might be plane belonging to the same group, weight with inverse ratio to the group size, etc. On all of the use can use transitivity. For examples, you can find similar product of a different names by using the fact that they will be used with the same products (e.g., spice X` and spice X`` will both be used with chicken).

Very soon you will have plenty of similarity relations and you will wonder how to combine them. Here come to help the labeling you already done. Take these as positive pairs of associated products. Generate sets of distinct products (not in the positives pairs) as negative pairs. Build a dataset in which the positivity is the concept and the similarities are the pairs. Now you can use supervised learning algorithm to get a model that combines the similarities into a single prediction. You can use this model to predict the association between new pair. As a bonus you will be able to evaluate the performance of the model on the dataset (e.g., accuracy, precision,...) and have more certainty in it.