2
$\begingroup$

What are the common techniques for encoding discrete features with tree-path value (e.g. file/folder path) without expanding tree into multiple features corresponding to each node?

Update.

Overall, I am looking for encoding which can be used with different algorithms (e.g. linear regression, not only clustering). Something like Huffman coding but usable with machine learning.

For example, consider this tree described with lisp-like notation: (a (b b1 b2) (c c1 c2 c3))

It could be encoded by creating feature for each node but this will be very expensive for any sufficiently large tree. a b b1 b2 c c1 c2 c3 Path 1 1 0 0 0 0 0 0 /a/b 1 0 0 0 1 0 1 0 /a/c/c2

Instead of creating feature for each node, there could probably be a feature for each depth level. L1 L2 L3 Path 1 1 0 /a/b 1 2 6 /a/c/c2 where
L2 can have value of 0,1,2 for none,b,c correspondingly;
L3 can have value of 0,1,2,5,6,7 for none,b1,b2,c1,c2,c3 correspondingly (with gap between b2, and c1 so that there is numerical distance between nodes with different parents).

There are some obvious problems with it though, e.g. c1 and c3 are further away from each other than c1 and c2.

I understand that encoding really depends on how you want to interpret the tree and relation between nodes. I was hoping there might be some article/paper which describes different approaches and trade-offs.

$\endgroup$
  • 1
    $\begingroup$ Welcome to DataScience.SE! Please can you tell us a little bit about your goal? $\endgroup$ – Emre Mar 9 '16 at 0:26
  • $\begingroup$ Hello @Emre. For example, given data about file changes, I'd like to use changed file path as one of the inputs for clustering to find changes which were roughly in the same area. $\endgroup$ – Dmitry Kandalov Mar 9 '16 at 0:36
2
$\begingroup$

Clustering

I think a tree is a perfectly appropriate data structure in this case. You don't need an embedding to do clustering; there are similarity-based approaches too, and defining a similarity function in your case is straightforward: I'd say it's a function of the common depth between the two items in consideration. You will probably want to define a root to "normalize" the scores. For example, given the root "a/b/" and the paths:

a/b/c/d/foo1
a/b/c1/foo2
a/b/c1/foo3
a/b/c/d/foo4

The shared depth between foo1 and foo2 and 0, discounting the root. For foo1 and foo4 it is 2. For foo2 and foo3 it is 1. You can define the similarity as a transformation of this through the function $f:x \to 1-\exp(-ax)$, where $a$ is a parameter you can use to tweak the clusters.

For implementation, in python, you can try sklearn.

General

You can featurize a path string by creating a set from its parent folders, which can then be represented as a sparse bit string by hashing the set elements. For example, "a/b/c/d/foo1" becomes ("c", "c/d"), if we let "a/b" be the root, as before. (The notion of a root is not strictly necessary here except to ensure that the baseline similarity is zero.) The path similarity is simply then the set similarity or, after conversion to bit strings, the $L_p$ distance.

$\endgroup$
  • $\begingroup$ Thank you @Emre. I do use sklearn and didn't realise it can take similarity function for clustering. $\endgroup$ – Dmitry Kandalov Mar 9 '16 at 12:33
  • $\begingroup$ More generally, I was looking for encoding which can be used with different algorithms not only clustering. Something like Huffman coding but usable with machine learning. $\endgroup$ – Dmitry Kandalov Mar 9 '16 at 12:47
  • $\begingroup$ Currently I can think of two options: - expand tree to features corresponding to each possible path with 0 or 1 value. This should work but can be expensive if the tree is large. - expand tree to features corresponding to each depth level with unique values for nodes at particular depth level. This might work but given many child nodes for one parent, some children will be encoded as if they are closer. I can write an example if it can be useful. I was hoping this has been already researched and there is article/paper with trade-offs. $\endgroup$ – Dmitry Kandalov Mar 9 '16 at 12:47
  • $\begingroup$ Detailed examples are always welcome; you can edit your question. $\endgroup$ – Emre Mar 9 '16 at 16:09

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.