Encoding feature with tree-path data 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.
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.