# Algorithm to determine whether the first row in CSV is likely to be a header row or a data row

I have a fairly simple problem. I am trying to determine whether the first row in CSV is likely to be a header row or a data row. Looking at single column, the problem can be simplified to: I have a set of n strings and need to determine if another string is similiar to these first strings in some way. For example:

set1 = ['12345', '14.32', '18000', '1200', '0', '123']
candidate1_1 = 'Nums' # Not similiar, uses different chars, not a number.
candidate1_2 = '400' # Similiar (is a number).

set2 = ['123-456-7890', '4412389112342', '+1-123-451-0983', '1009097812']
candidate2_1 = 'Phone Numbers' # Not similar, definitely a label.
candidate2_2 = '(123)123-1234' # Similiar.
candidate2_3 = '911' # Might be similar or not, depending on the algorithm.

# The function I need to write is:
...


So I can write out all of these different ideas for checks (data types, chars used, lengths, etc.) but I'm wondering if there is a better more abstract approach that would work robustly.

Could I use something like a word embedding? How might I looks at all columns to arrive at a more accurate estimate?

This question may be better asked on another forum (ex. https://math.stackexchange.com/), but I'm unsure which one. If that is the case, please advise.

• I have a simple algorithm. I use the linux/mac command line tool 'less'. It allows one to view any text file a line or page at a time, then my eyes decide. ;) Commented Dec 21, 2022 at 16:12

You can create a dataset containing features, such as: data types, characters used, lengths and others that you believe to be important for determining the class. Create another column in the dataset for the classes (header/ data). After you have created the dataset, you can use label encoding for the non-numerical features. Split the data in a training set and a test set and run a binary classification model of your choice. The task, as you said is relatively simple, and a lot of models can solve it - KNN, decision tree and many others.

• This is a nice idea. However, it does seem to have some limitations. 1) This method is going to require a large dataset of CSV files, labelled with which ones have a header row and which ones don't. That might be time-consuming to collect. 2) Also, this method assumes that the types that occur in header rows vs in the rest of the file are the same for all CSV files. I am skeptical of that. "Date" might be a header in one CSV file and a data value in another CSV file -- or, more to the point, "4-letter string using only a-zA-Z" might be a header in one file and data in another file.
– D.W.
Commented Dec 16, 2022 at 21:21

First thing I'd do is examine the source of the CSVs to determine if there's a way to detect the difference upstream without having to perform string-based calculations (which are relatively computationally expensive compared to others, giving the process a scaling limit). Hopefully the CSVs with headers are coming from a different place than the CSVs without headers, otherwise that's somewhat concerning from a data quality/integrity perspective.

If I determined that I needed to inspect the files to get the answer, next thing I'd do is perform a few simple checks meant to work for the majority of cases. If the first row has any blanks, it's either data or a bad file. If the first and second row have even a single field that differs in data type, it's a header. If the file is expected to contain a longer text column, I may also use a heuristic on field length to determine if the first row is likely to contain a value for that field, or compare the coefficient of variation between the field lengths of the first few rows to see if the first row has significantly lower variance.

If all else fails, time to get a little weird.

Word embeddings will not work if the column names are out of vocab, which is fairly frequently the case in my experience. Edit distance metrics like Levenshtein or Jaro-Winkler aren't going to work because values for the data rows don't need to be similar to each other to be valid, e.g. 123 and 456 are 100% different but could be values for the same column.

This is where I'd reach for one of the more obscure tools in my toolkit, string profiles. My preferred profile scheme is forcing all letters to A/a, and all numbers to 0, so Abc-123 becomes Aaa-000. This transforms the string from carrying semantic meaning to just information about "shape". You can also, if anticipating longer words in the data, truncate the shapes with run-length encoding or something similar. Once you have the shapes, edit-distance metrics become far more viable of a solution.

Edit to add: While they'd be seriously overkill for the task, I can't leave out that this is something a large language model would be almost as good at as a person if given a good prompt.

Overall, though, it's important to recognize that you could quite easily design a file that is impossible to accurately make a determination on, so there is no magic bullet. You may never encounter an impossible case but you do need to account for them existing either in your process or your documentation.

One possible approach might be to use a permutation test. This will let you use a statistical hypothesis test to check that the first row looks "different" from all the other rows and more like a header row.

# General approach

First, create some heuristic score $$H$$ that is designed to measure how likely it is that the first row is a header row, given all the rows of the CSV file.

Next, use a permutation test. Calculate $$H(f)$$, where $$f$$ is the original CSV file. Also, create 5,000 random permutations of $$f$$ (where the rows have been randomly shuffled), call them $$f_1,\dots,f_{5000}$$, calculate $$H(f_1),\dots,H(f_{5000})$$, and compute the p-value as

$$p = \sum_{i=1}^{5000} \mathbf{1}_{H(f_i) \ge H(f)},$$

i.e., the number of permuted files that have a higher heuristic score than the original.

Finally, if the p-value is below some threshold (say 0.001), conclude that the first row is a header row.

# An appropriate heuristic

How should you compute a heuristic $$H$$? In principle, anything is safe (in the sense that it'll rarely err on the side of treating ordinary data as a header row), but the better the heuristic, the more reliable this will be at detecting actual headers.

One possible approach is to choose a bunch of little tests, and add 1 point for each little test that suggests the first row is a header and 0 otherwise. Then, the heuristic $$H$$ is the sum of these tests.

To build these little tests, you might accumulate many boolean features that can be applied to a string: e.g., "is it a number?", "is it a date/time?", "does it contain any whitespace?". Then, for each column and each data type, we obtain a little test as follows: map all the values in that column to true/false using that boolean feature; compute the distribution of true/false in all rows other than the first row; look at the feature value in the first row; if the frequency of that value in the inferred distribution for the other rows is below 0.01, then this little test suggests the first row is a header row (add 1 point to $$H$$), otherwise it doesn't (add 0 to $$H$$). Repeat for all combinations of rows/features.

# Optimization

You can speed this up a lot in a way that removes the need to explicitly compute 5,000 random permutations of the file. In particular, precompute the featurization of all cells under all candidate features, and also precompute the distribution (counts) of true/false in each column under each feature. Then, instead of picking a random permutation $$f_i$$, it suffices to randomly pick a row to be treated as the first row of $$f_i$$, and then you can very quickly compute the value of $$H(f_i)$$ from the values that were previously precomputed.

# Corner cases

Technically, a CSV file can have multiple header rows. This procedure assumes there are 0 or 1 header rows. If you need to deal with this, you could extend the above procedure to first test whether the first 4 rows are headers, then whether the first 3 rows are headers, etc.

If the file has fewer than 8 rows, this procedure will fail and always infer that the first row is not a header row, because the statistical hypothesis test doesn't have enough power (it will never yield a p-value below 0.001).

This is usually done as part of a multi-step process for data analysis and quality control, and the first step is to identify the type of each column, e.g. number, currency, date, string, ...

Simplifying that to just number vs. other, you would calculate the mean, min, max and s.d. of each column, and count number of rows that are not numbers (and also count blanks separately). (If dealing with huge files, just do the first 1000 rows, or first 500 and last 500.)

Columns that are mostly numeric, and which you managed to calculate a mean and s.d. for, are the interesting ones. Was row 1 a number/blank or was it a string?

If most numeric columns have a string in row 1 it is almost certainly a header row. If most numeric columns are numeric/blank in row 1, it is almost certainly a data row.

When you are in the grey area, either give the user a warning, or treat it as a header row.

You adapt it to deal with the type of data you typically get. E.g. if order data, look for a leading "\$" and remove that, before trying it as numeric. Also look for dates (this also where you try and discover if is YYYY-MM-DD, YY/MM/DD, YY/DD/MM, or a mix of all three).

H2O has always been very good at identifying a header row automatically, and I think it uses this algorithm. I think the R libraries for reading csv also use something like this.