3
\$\begingroup\$

I have a dataset composed of ~700k samples. Each sample is composed of n_features features. Each feature is a word. Each feature has his own vocabulary. The size of the vocabularies range from 18 to 32000.

np.shape(x) -> (n_samples, n_features)

Instead of having lists of features I would like to have lists of indexes corresponding to the indexes in vocabularies. This is my code:

vocs = [np.array(list(set(x[:,i]))) for i in range(np.shape(x)[1])]
x_new = [[np.argwhere(vocs[j]==x[i,j]) for j,feature in enumerate(features)] for i,features in enumerate(x)]

This code works but I wonder if there is a way to improve the performances. These 2 lines take 10min to run on my i7-7700HQ @ 2.8GHz.

Edit:

For more context, what I'm working on is natural language processing. I want to train a classifier to predict relations between words in a sentence. For this I have a conllu file which give sentences and for each word of each sentence a list of features and with which word it's related and how. These features may be the word itself, its lemma, its position in the sentence etc... I'm trying a different set of features and type of embedding and I want to test the embedding described above.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi! I'm not sure this question is super clear to some readers. Could you maybe give a small example of the expected behavior of your code? \$\endgroup\$ – IEatBagels Dec 4 '18 at 18:23
5
\$\begingroup\$
  1. When using NumPy, stick to NumPy functions where possible instead of going via pure Python and back again (which is usually slower). So instead of getting the unique elements of an array by writing np.array(list(set(...))), call numpy.unique.

  2. The expression np.argwhere(vocs[j]==x[i,j]) has to search the whole vocabulary for the word x[i,j], and this has to be done for every feature in every sample. This means that if there are \$s\$ samples and \$f\$ features, and each feature has \$w = O(s)\$ words, the overall runtime is proportional to \$sfw = O(s^2f)\$. That is, it's quadratic in the number of samples. This is why it takes so long.

    To avoid this, we need to construct, for each feature, an inverse mapping from words in the samples to their indexes in the vocabulary. How do we construct such inverse mappings? Well, looking at the numpy.unique documentation, we find that it takes a keyword argument:

    return_inverse : bool, optional

    If True, also return the indices of the unique array (for the specified axis, if provided) that can be used to reconstruct ar.

    These inverse arrays are exactly what you need, and so your code becomes:

    vocs, inverses = zip(*(np.unique(feature, return_inverse=True) for feature in x.T))
    x_new = np.vstack(inverses).T
    
\$\endgroup\$
  • \$\begingroup\$ Thank you! I was looking for a numpy function to convert a list of values to a list of indexes giving a vocabulary but I didn't find it and I was sure I was missing something. With your code it takes less than 10s. \$\endgroup\$ – amarion Dec 2 '18 at 18:36

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