Clustering algorithm to sort filenames

Question

A client would like to sort out his filesystem (~ 1,000,000,000 files), which has been fed by numerous workers over the years, each with their own unknown naming convention, e.g.:

• [DATE]-[CLIENT]-[FILENAME]
• [TYPE]-[CLIENT].[DATE][FILENAME]
• ...

Here are four examples (out of ~1,000,000,000 files) to make things clearer:

JPM_TPD0001662_2009124012302000451.pdf

JPMF_STA_1712010832_18001_LUX_approval.pdf

CHACN05CTRP_00111.001.pdf

CHACN63CJO1_00018.001.pdf

The purpose is to find out patterns in the naming conventions, but I can't use regular expressions, since the conventions are unknown a priori.

I was wondering whether there was a kind of clustering algorithm to be able to group files according to their naming conventions.

Any K-Mean philosophy applied to strings?

Answer 1

This is not at all a typical clustering problem, so I doubt any of these algorithms will help. If you want to try clustering, you will need to do appropriate feature extraction. Don't expect things to work on the raw data. But I guess once you have good features, the problem will already be solved.

Instead of trying to frame this as a clustering problem, look at it either from a sequential pattern view point, or even better: look at the few questions on how to learn regexps from a set of strings.

Answer 2

For those interested in a solution for similar problems, I found a solution with these steps:

1. Splitting the filenames on "_", generating n strings

2. Taking the length of each string

3. Running KMeans (optimal K using Gap Statistics)

4. Taking one sample per cluster and reverse-engineering it to a generic regex, via a customized function

In practice, here is an example of 10 files:

File 0 splits on "" into groups of lengths 3, 10 and 23 respectively. File 3 splits on "" into groups of lengths 11 and 13 respectively. File 5 splits on "_" into groups of lengths 4, 3, 10, 5, 3 and 12 respectively.

Files 0, 1 and 2 belong to the same cluster and have identical naming convention. Files 3, 4, 6, 7, 8 and 9 belong to the same cluster and have identical naming convention. File 5 belongs to another cluster and has yet another naming convention.

Answer 3

Parse using regular expressions

I work a project where we get thousands of data files per day from on the order of 10 different systems. The filenames are all a jumble, and have a tendency to change over time. This is a job for regular expressions.

The primary thing I use to organize is functional groupings. I simply use a small set of indicators common to each file set. In my case, the server that aggregates and sends the data files to me appends its name to the filename (zs2101, or something like that). So then I search file names for this limited set of regular expressions (I am currently using 20). In your situation, it seems like the client name in the file headers is something you could search for an use for the base of your organization

Then, I divide files by date of generation of the data. Each file comes with a timestamp. When I read files into my archive, I find the date field in every file and convert it to a standard format, and then change the filename to reflect that standard format. Now I build a directory tree for each server name, organized by date (a folder for each year, and a sub-folder for each month, in my case).

My recommendation is that you use regular expressions to organize your data. These are deterministic in the sense that if you receive a strange file header or malformed filename, you know where it will end up (in my case, there is an 'Undetermined' folder that accepts everything that doesn't match a server or date regex). The problem with k-means is that if you get something you didn't plan for, it can be pretty hard to tell where the clustering algorithm will put it, leading to lost data.

Good luck, hope this helps.

Answer 4

If you don't know the patterns in advance, then it is going to be quite difficult to do the automated grouping.

You can, however, take the following approach

Step - 1 -
Define basic rules (data-driven) based on which grouping can be done (like starts-with JPM_, ends-with a number in a specific range, file-size, source, etc)

Step - 2 -
Unless a direct match towards a group, rules should direct towards a group but with a staging state where a manual verification can be done. If there is a direct match, directly apply step 4.

Step - 3 -
After manual verification, change their state to verified.

Step - 4 -
Remember the inputs and the verified output so that next-time when the same input comes, directly put them in the same verified group.

Basically, your manual verification will be your machine-learning and there are two advantages

• In due time machine will be able to take decisions by itself.

• Process is easy to debug, verify and port to another system.

Answer 5

Your problem here isn't in choosing an appropriate clustering algorithm, its defining an appropriate similarity metric. Edit distance and jaro winkler distance will cover a lot of ground for you, but you should still anticipate needing to do a fair amount of pre-processing and customization here. Also, as great as text-based metrics are, you have much more information here that can be leveraged. Your data is obviously going to have implicit clusters in it already based on documents that are contained in the same folders, and going further those folders exist in a hierarchy which also implies certain groupings. You should make sure that your clustering and/or similarity scoring incorporates these topological features in addition to any text similarity you do.

Your first step is going to be understanding your data more. I'd recommend constructing a tree visualization of the folder hierarchies you're going to be dealing with, taking a sample of 5-10 filenames from within each folder so you can better understand what your dealing with. From here, start trying to understand what kinds of naming conventions are in place that you can take advantage of. There are probably lots of files with dates at the beginning or end, maybe commonly occurring client names, words that are suggestive of document classifications like "report", "newsletter", "resume" etc. The more of these you can capture and deal with directly, the better. Next, you may start seeing some patterns that suggest ways you can further tokenize filenames. spaces, hyphens, and underscores are probably good places to start (after dealing with dates/timestamps, obviously), and CamelCasing would be worth looking out for as well. Also, different filetypes might have different naming conventions. For example, *.png files are probably more likely to have all numeric names starting with dates (i.e. someone dumped their camera to a folder).

If you want to just get really quick and dirty with it, something you could try would be to parse each filename into n-grams (e.g. all sequential 3-letter sequences that occur in a filename) and then score pairwise filename similarity based on the jaccard distance of the n-grams that appear in each filename.

Once you've figured out a couple of different approaches you want to try, you should start thinking about how to evaluate your results. Obviously you're going to start out evaluating things qualitatively, but that doesn't really help you compare the strengths/weaknesses of different approaches. One thing you could try would be to use the naming conventions learned by a particular method to try to predict whether or not randomly sampled filenames appear in the same folder or not, and score your methods based on how well the resulting classifiers perform.

Ultimately, your going to have to custom tailor the solution to what you see in your clients filenames. Hopefully, I gave you a few ideas to work with here.