数据挖掘 - 具有树路径数据的编码功能 - 吾爱随笔录

用树路径值（例如文件/文件夹路径）编码离散特征而不将树扩展到对应于每个节点的多个特征的常用技术是什么？

更新。

总的来说，我正在寻找可以与不同算法一起使用的编码（例如线性回归，而不仅仅是聚类）。类似于Huffman 编码，但可用于机器学习。

例如，考虑用类似 lisp 的符号描述的这棵树： (a (b b1 b2) (c c1 c2 c3))

它可以通过为每个节点创建特征来编码，但这对于任何足够大的树来说都是非常昂贵的。 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

不是为每个节点创建特征，而是每个深度级别可能都有一个特征。 L1 L2 L3 Path 1 1 0 /a/b 1 2 6 /a/c/c2 其中
L2 可以对应地为 none,b,c 的值为 0,1,2；
L3 的值可以分别为 none,b1,b2,c1,c2,c3 的值 0,1,2,5,6,7（b2 和 c1 之间存在间隙，因此具有不同父节点的节点之间存在数字距离）。

但它也有一些明显的问题，例如 c1 和 c3 比 c1 和 c2 彼此相距更远。

我知道编码真的取决于你想如何解释树和节点之间的关系。我希望可能有一些文章/论文描述不同的方法和权衡。

聚类

我认为在这种情况下，树是一个非常合适的数据结构。您不需要嵌入来进行聚类；也有基于相似性的方法，并且在您的案例中定义相似性函数很简单：我会说它是所考虑的两个项目之间的共同深度的函数。您可能需要定义一个根来“标准化”分数。例如，给定根“a/b/”和路径：

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

foo1 和 foo2 和 0 之间的共享深度，不考虑根。将相似度定义为 this 的转换，其中是一个参数，您可以用于调整集群。

f : x \to 1 - \exp (- a x)

$f:x \to 1-\exp(-ax)$

a

$a$

对于实现，在 python 中，您可以尝试sklearn。

一般的

您可以通过从其父文件夹创建集合来对路径字符串进行特征化，然后可以通过散列集合元素将其表示为稀疏位字符串。例如，如果我们像以前一样让“a/b”作为根，“a/b/c/d/foo1”就变成了(“c”，“c/d”)。（除了确保基线相似度为零之外，根的概念在此不是绝对必要的。）路径相似度就是集合相似度，或者在转换为位串之后，就是距离。

L_{p}

$L_p$