Extracting Features from Surnames

Extracting features from surnames entails encoding the frequency of n-grams and other features such as the string length. Recall that 1-grams are letters or characters, also called unigrams, 2-grams are called bigrams or digraphs, and 3-grams are called trigrams. In some applications entire words, sentences or other tokens are used as grams.

Assumption of Independence of Features

In many (actually most) classification techniques there is an assumption of independence of features. This has two important bearings on classification using n-grams.

First many classifiers 'require' a feature matrix of full column rank, so including a variable like the length of the name along with the n-gram frequencies introduces a linear dependence between the columns; coding EGAN as having length 4 along with the 1-grams E, G, A, and N, clearly introduces no new information. The same is true for bigrams EG, GA, and AN, or trigrams EGA and GAN, and so forth. Likewise coding both bigrams and trigrams introduces no new information.

Second the assumption of independence among features means that with an n-gram encoding the sequence information is lost. That is EGA and GAN are assumed to be uncorrelated, though clearly they are not (as they overlap by GA). Thus there is a potential for improvement by including positional features. One way of denoting the start and end of the string is to add a space to the gram set and delimit surname with spaces. Thus EGAN would be coded in trigrams as " EG", "EGA", "GAN", and "AN ". As space characters can be difficult to spot, a hash (#) or underscore (_) is often used in its place.

Extracting the Features

Feature extraction is performed by a dedicated script (SurnameFeatures.pl).

An example command line is: perl SurnameFeatures.pl -i=sourcefile.txt -ncol=0 -dcol=5 -sp=1 -gram=2 -minfq=1 -diag=0<\tt>

Where sp=1<\tt> forces the inclusion of spaces in the character set (which is otherwise a-z), as well as before and after the string, minfq<\tt> sets to minimum global frequency of occurance of an n-gram for it to be included in the output, and diag=1<\tt> produces an additional frequency of occurance diagnostic file.