1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What are you trying to ultimately accomplish? The best way to cluster something depends on what you want to do with the clusters. $\endgroup$ – Kodiologist Sep 9 '17 at 19:20
  • $\begingroup$ @Kodiologist Ultimately I want to categorize the parts according to TARIC, but I believe it will be easier to do so if I first categorize the parts in clusters and then for each cluster I connect then to TARIC. circabc.europa.eu/faces/jsp/extension/wai/navigation/… $\endgroup$ – Isak La Fleur Sep 9 '17 at 20:48
  • $\begingroup$ The link seems to be broken (it's probably specific to your user session). So does TARIC comprise some sort of list of parts, and you need to match up your part numbers to TARIC's identifiers on the basis of the part name? If so, there might be a method to get you there faster than by using clustering and then sorting the clusters by hand. $\endgroup$ – Kodiologist Sep 9 '17 at 21:06
  • $\begingroup$ @Kodiologist here is an example of a chapter 8431* ec.europa.eu/taxation_customs/dds2/taric/… $\endgroup$ – Isak La Fleur Sep 9 '17 at 21:17
  • 1
    $\begingroup$ Beware that e.g. "dog" and "fog" are highly similar for, e.g., Levenshtein distance. But completely unrelated for humans. $\endgroup$ – Has QUIT--Anony-Mousse Sep 10 '17 at 8:34
1
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your guidance. I know I will need to do quite a lots of manual adjustments. My idea is to run it and "tell" the algo to store rules so for next run it will take into account. ex.. let say string "cap screw" has a wrong best match and it is the second best match that is correct. Then I will will select the second match and also at the same time for all future "cap screw" strings, it should use the second best match in TARIC. It will be a array of objects in javascript like: [{string: "cap screw", taric: "xxxxxxxxxx"}]. Can this be a way forward? $\endgroup$ – Isak La Fleur Sep 10 '17 at 6:31
  • $\begingroup$ another question.. regarding string matching. Normally in this case there will almost non misspelling, but only some variation of how the string is constructed.. different engineers name the same part different, for example: "cap screw" = "screw, cap" or "oring" = "o-ring" = " o ring". Is still Levenshtein a good method for this? $\endgroup$ – Isak La Fleur Sep 10 '17 at 7:00
  • 1
    $\begingroup$ @IsakLaFleur "Can this be a way forward?" — Yes, that's what I mean by considering only the distinct canonical strings. "for example: 'cap screw' = 'screw, cap' or 'oring' = 'o-ring' = ' o ring'" — The canonicalization step I mentioned will already enforce the second of these equations. For the first, you could try inverting the parts of a string whenever a comma occurs in it. $\endgroup$ – Kodiologist Sep 10 '17 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.