5 ms·

I am blocked on finding a good (defined below) way to determine whether a product description A and product description B refer to the same product. Imagine th

by udev 5y ago

I am blocked on finding a good (defined below) way to determine whether a product description A and product description B refer to the same product. Imagine that a product description is a n-dimensional vector like: ( manufacturerName, modelName, width, height, length, color, ...) Now imagine you have a file with m such vectors (where m is in millions), and that not all fields in the vectors are reliable info (typos, missing info, plain wrong, etc). What is a good way to determine which product descriptions refer to the same product. Is this even a good approach? What is state of the art? Are there simpler ways? Here is what I mean by good: - robust to typos, missing info, wrong info - efficient since both m and n are large - updateable (e.g. if classification was done, and 10k new descriptins are added, how to efficiently update and avoid full recomputation)

alex989898 5y ago
You could generate word embeddings for all natural language text fields and then do cosine similarity?
Fragoel2 5y ago
Definitely some clustering method based on similarity of the vectors (there are many, pick a simple one to start)
ethn 5y ago
Use a Minhash-LSH ensemble with pre-processing on the words to fix typos via Levenshtein. Tune parameters to get the best distance
gurgeous 5y ago
I have worked on this problem many times, at many companies. I am working on it again, actually. Usually some combination of scoring and persisting results in CSVs for human review. (edit: I am at a desktop now and I can say a bit more) Here is the process in a nutshell: 1. Create a fast hashing algorithm to find rows that might be dups. It needs to be fast because you have lots of rows. This is where SimHash, MinHash, etc. come into play. I've had good luck using simhash(name) and persisting it. Unfortunately you need to measure the hamming distance between simhashes to calculate a similarity score. This can be slow depending on your approach. 2. Create a slower scoring algorithm that measures the similarity between two rows. Think about a weighted average of diffs, where you pick the weights based on your intuition about the fields. In your case you have handy discrete fields, so this won't be too hard. The hardest field is name. Start with something simple and improve it over time. Blank fields can be scored as 0.5, meaning "unknown". Hashing photos can help here too. 3. Use (1) to find things that might be dups, then score them with (2). Dump your potential dups to a CSV for human review. As another poster indicated, I've found human review to be essential. It's easy for a human to see that "Super Mario 2" and "Super Mario 3" are very different. 4. Parse your CSV to resolve the dups as you see fit. Have fun!
- dr_zoidberg 5y ago
  With regards to 1, I wonder: why would calculating the Hamming distance be slow? In python you can easily do it like this: hamming_dist = bin(a^b).count("1") It relies on a string operations, but takes ~1 microsecond on an old i5 7200u to compare 32bit numbers. In python 3.10 we'll get int.bit_count() to get the same result without having to do these kind of things (and a ~6x speedup on the operation, but I suspect the XOR and integer handling of python might already be a large part of the running time for this calculation). If you need to go faster, you can basically pull hamming distance with just two assembly instructions: XOR and POPCNT. I haven't gone so low level for a long time, but you should be able to get into the nanosecond speed range using those.
wizzwizz4 5y ago
Usually, I do this sort of thing somewhat manually, building up an algorithm (mostly classical, with a little ML as a treat) that can deal with the problem. I'd start by detecting common typos. Typos are similar to un-typo'd data, so I'd do a frequency analysis on the textual representations of manufacturer name and model name, and a Levenshtein distance calculation, then synonymise the obvious synonyms (looking things up when I wasn't sure). The key idea is that you have access to more information than just this dataset: Tony and Tomy are different manufacturers, but Sony and Somy aren't (even though somy is in the dictionary and tomy isn't). Once the manufacturer and model fields are mostly typo-free (after typo replacement – don't modify the original file, if you can help it!), you can start looking at dimensions and colour. Sort by manufacturer, and start de-duping entries. Once you get a feel for the process you're doing (e.g. under what circumstances do you check whether there's a 102mm Phillips screwthread?), you can start automating bits of it. There will always be special-cases, but your job is to get the data processed correctly, not to get the computer to process the data. Accidentally aliasing two different products is much worse than leaving the same product described twice, so err on the side of “these are different”. (Keep in mind that manufacturers of some things, e.g. SD cards, often pretend two different products are the same – so you can't always win!) Remember, humans exist: bothering them a few million times is a problem, but bothering them a few hundred would be okay. When new data comes in, I'd run all the code I used to come up with my system, and see if the output was notably different. If it was, I'd get the computer to let me know. I'd also add some way for users to flag duplicates. Many humans make light work.
Radim 5y ago
What's your cost matrix? How much does a false positive hurt? False negative? I built a commercial system like that for Thermo Fisher, except their descriptions were encoded as natural language text on input, not vectors (for an extra complication). Some observations: 1. Crude methods based on vector embeddings, cosine similarity, Levenshtein, etc – don't work, if you care at all about false positives. I see sibling comments recommend this, but it's clear this cannot work if you think about it. Values like "black" and "white", or "I" and "II" (part numbers), "with" and "without", are typically close together in such crude representations, but may lead to products that are not interchangeable. 2. A hybrid approach worked. The SW produced suggestions for which products might be duplicates (along with a soft confidence score), then let a human domain expert accept / reject these suggestions. It also learned from these expert decisions as it went, to save human time. What I quickly learned is that even as a human (programmer with a PhD in ML), I could not look at two product descriptions and make the decision myself. Are these the same product or not? One word, even one letter, could be absolutely vital. Or absolutely irrelevant. Sometimes even the same attribute / word, depending on the product category. Hence the final interactive solution with a domain expert in the middle. It worked well and saved time, rather clever, but not in the "hooray NN training" way. A lot of work went into normalizing the surface features intelligently based on context: units, hyphens / tokenization, typos…, because that's a mess in product sheets. The "fancy" downstream ML and clustering part was relatively simple by comparison. But YMMV, the Thermo Fisher products were fairly specialized and sophisticated (in their millions).

by udev 5y ago

alex989898 5y ago

You could generate word embeddings for all natural language text fields and then do cosine similarity?

Fragoel2 5y ago

Definitely some clustering method based on similarity of the vectors (there are many, pick a simple one to start)

ethn 5y ago

Use a Minhash-LSH ensemble with pre-processing on the words to fix typos via Levenshtein. Tune parameters to get the best distance

gurgeous 5y ago

I have worked on this problem many times, at many companies. I am working on it again, actually. Usually some combination of scoring and persisting results in CSVs for human review. (edit: I am at a desktop now and I can say a bit more) Here is the process in a nutshell: 1. Create a fast hashing algorithm to find rows that might be dups. It needs to be fast because you have lots of rows. This is where SimHash, MinHash, etc. come into play. I've had good luck using simhash(name) and persisting it. Unfortunately you need to measure the hamming distance between simhashes to calculate a similarity score. This can be slow depending on your approach. 2. Create a slower scoring algorithm that measures the similarity between two rows. Think about a weighted average of diffs, where you pick the weights based on your intuition about the fields. In your case you have handy discrete fields, so this won't be too hard. The hardest field is name. Start with something simple and improve it over time. Blank fields can be scored as 0.5, meaning "unknown". Hashing photos can help here too. 3. Use (1) to find things that might be dups, then score them with (2). Dump your potential dups to a CSV for human review. As another poster indicated, I've found human review to be essential. It's easy for a human to see that "Super Mario 2" and "Super Mario 3" are very different. 4. Parse your CSV to resolve the dups as you see fit. Have fun!

dr_zoidberg 5y ago
With regards to 1, I wonder: why would calculating the Hamming distance be slow? In python you can easily do it like this: hamming_dist = bin(a^b).count("1") It relies on a string operations, but takes ~1 microsecond on an old i5 7200u to compare 32bit numbers. In python 3.10 we'll get int.bit_count() to get the same result without having to do these kind of things (and a ~6x speedup on the operation, but I suspect the XOR and integer handling of python might already be a large part of the running time for this calculation). If you need to go faster, you can basically pull hamming distance with just two assembly instructions: XOR and POPCNT. I haven't gone so low level for a long time, but you should be able to get into the nanosecond speed range using those.

wizzwizz4 5y ago

Usually, I do this sort of thing somewhat manually, building up an algorithm (mostly classical, with a little ML as a treat) that can deal with the problem. I'd start by detecting common typos. Typos are similar to un-typo'd data, so I'd do a frequency analysis on the textual representations of manufacturer name and model name, and a Levenshtein distance calculation, then synonymise the obvious synonyms (looking things up when I wasn't sure). The key idea is that you have access to more information than just this dataset: Tony and Tomy are different manufacturers, but Sony and Somy aren't (even though somy is in the dictionary and tomy isn't). Once the manufacturer and model fields are mostly typo-free (after typo replacement – don't modify the original file, if you can help it!), you can start looking at dimensions and colour. Sort by manufacturer, and start de-duping entries. Once you get a feel for the process you're doing (e.g. under what circumstances do you check whether there's a 102mm Phillips screwthread?), you can start automating bits of it. There will always be special-cases, but your job is to get the data processed correctly, not to get the computer to process the data. Accidentally aliasing two different products is much worse than leaving the same product described twice, so err on the side of “these are different”. (Keep in mind that manufacturers of some things, e.g. SD cards, often pretend two different products are the same – so you can't always win!) Remember, humans exist: bothering them a few million times is a problem, but bothering them a few hundred would be okay. When new data comes in, I'd run all the code I used to come up with my system, and see if the output was notably different. If it was, I'd get the computer to let me know. I'd also add some way for users to flag duplicates. Many humans make light work.

Radim 5y ago

What's your cost matrix? How much does a false positive hurt? False negative? I built a commercial system like that for Thermo Fisher, except their descriptions were encoded as natural language text on input, not vectors (for an extra complication). Some observations: 1. Crude methods based on vector embeddings, cosine similarity, Levenshtein, etc – don't work, if you care at all about false positives. I see sibling comments recommend this, but it's clear this cannot work if you think about it. Values like "black" and "white", or "I" and "II" (part numbers), "with" and "without", are typically close together in such crude representations, but may lead to products that are not interchangeable. 2. A hybrid approach worked. The SW produced suggestions for which products might be duplicates (along with a soft confidence score), then let a human domain expert accept / reject these suggestions. It also learned from these expert decisions as it went, to save human time. What I quickly learned is that even as a human (programmer with a PhD in ML), I could not look at two product descriptions and make the decision myself. Are these the same product or not? One word, even one letter, could be absolutely vital. Or absolutely irrelevant. Sometimes even the same attribute / word, depending on the product category. Hence the final interactive solution with a domain expert in the middle. It worked well and saved time, rather clever, but not in the "hooray NN training" way. A lot of work went into normalizing the surface features intelligently based on context: units, hyphens / tokenization, typos…, because that's a mess in product sheets. The "fancy" downstream ML and clustering part was relatively simple by comparison. But YMMV, the Thermo Fisher products were fairly specialized and sophisticated (in their millions).