How should I approach to cluster short (one-three words) strings?

Question

I have approx 450.000 strings in a csv file. It's part names, so the strings are normally based on one-three words. I need to somehow group them together in an automated way so I can work with these clusters instead of part by part.

Here are a couple of random examples from the CSV file see above linked:

CENTERING DEVIC, GEAR, PLUG, ADAPTER, ADAPTER, ADAPTER, APPARATUS PANEL A50, BRACKET, BRACKET, BRACKET MOUNT CS1000"P"HD, BRACKET MOUNT CS1000"P"HD, CABLE, SIGNAL CABLE, CABLE, SIGNAL CABLE, CAP, CAPSCREW, CARRIER, CHAIN, CHECK VALVE, CHUCK, CHUCK, CLEVIS, CONDENSER SET, COVER, CRAWLER SET 11-12TON, CYLINDER TUBE, DUST COLLECTOR, ELBOW, ELBOW, FILLER PIPE, FILTER ELEMENT, FLUID LEVEL, GAUGE, FOOT, FORGING, LARGE CAPACITY HUB, GPS-box D-rigg with cabin

Here is what I plan to do to attack the problem:

1. Use Levenshtein to compare the strings. Take the first item of the array of strings and compare it to all others in the array and calculate a score for this first item.
2. Lets say I only allow 10% difference between the first string and the second, third,.,.., and the rest strings in the array. I will remove the first item and the other items in the array that had only 10% difference or less compared with the first string.
3. Continue with second string in the array and do the same calculation over and over again until I have walked through the whole array.
4. Items that remains in the array, that doesn't fit (10% > diff), I will need to handle manual...

Is this a good approach? I have read a bit about hierarchical clustering, is this a better approach or can anyone guide me in another better direction that I suggested?

Answer 1

As I understand, the goal is to match up your part numbers to TARIC's identifiers on the basis of the part name. This is probably most conveniently done with direct comparisons between the two sets rather than with an initial clustering step. You could try something like the following:

1. For each of the two datasets (TARIC and your own data), canonicalize each string by downcasing it and removing all characters other than lowercase ASCII letters. You can concern yourself only with the distinct canonical strings in each dataset. (This step alone reduces your own dataset to 100,020 strings.)
2. Loop through the canonical strings in your data. For each, find the nearest TARIC string by Levenshtein distance. If the match is exact or very close, you're probably good. Otherwise, look more closely. Hopefully you'll find more patterns as you handle cases manually, which you can exploit to further reduce the number of cases you have to handle manually.