从具有不同特征的节点中预测树结构

数据挖掘 机器学习 神经网络 聚类 深度学习 图表
2022-02-26 18:36:38

问题

假设我们有一个文档文本布局的表示,如下图所示:

文档布局

在这里,每个矩形代表一段文本(一个单词、一个表达式甚至是句子的一部分)。

每个矩形都有一组特征和与相邻矩形的连接(图像没有显示所有连接,但它们存在):

  • 顶部/bot/lft/rgh 同级
  • top/bot/lft/rgh 到兄弟姐妹的距离(如果兄弟姐妹存在)
  • 边距对齐(对于在列中对齐的矩形)
  • 字体大小(连续可变类型)
  • 字体类型(分类)
  • all_caps(二进制)
  • 和其他一些

我想要实现的是训练一种算法(ML?DNN?图?其他东西?),它将构建这些矩形,从这些单独的节点中创建一个树结构。例如,上述示例的结构如下:

          ROOT
 __________|___
|          |   |
2          10  12
|_         |   |_________
| |        |   |         |
3 9        11  14        20...
|________      |__       |__
| | | | |      |  |      |  |
4 5 6 7 8      13 15...  19 21...
                            |  \
                            22 23...

到目前为止我的结果

我花了一些时间(大约 8 小时)寻找解决方案,但找不到适用于这种情况的任何东西。我对 ML 比较陌生,没有太多经验,但是我认为可以使用监督学习算法来解决这个问题,方法是提供一个训练集,该训练集包含所有这些节点及其特征和注释树的文档,这些节点应该生成为这些节点的结果。

我在搜索时发现的一些想法可能会有所帮助(可能其中之一就是解决方案,但我需要一些关于如何正确调整的指导):

  1. 使用某种 DNN。它将从训练集中找出节点的距离和其他特征之间的关系,以便能够预测仅给定节点及其特征的结构。我没有使用 DNN,我不知道如何让它生成结构,而不是对图像中显示的数字进行分类(我做了一些基本教程)
  2. 创建/训练 PCFG(概率上下文无关语法)。这种方法似乎是有效的,因为它用于在 NLP 中生成解析树(那些以树的形式构建句子的树​​),我在上面找到了一些资源,但是我不明白如何使用所有的功能在我的节点上可以学习这样的语法吗?此外,我看不出这种方法如何利用 2D 空间中的定位数据和兄弟之间的距离,因为它是构建节点的关键特征之一。
  3. 可能一些与 Graph 或 Tree 相关的算法可以解决我的问题,但我不知道如何制定可以帮助我找到解决方案的查询。

在Computer Science SE 网站上提出了一个非常相似的问题,但没有答案,OP 也没有回应。

如果你能提供一个解决方案,或者甚至是为了解决这个问题而向哪个方向移动的提示,我将不胜感激。

1个回答

不要为此使用机器学习——您可能没有数百万个训练示例。

相反,您正在寻找的是一个简单的深度优先搜索

从根开始,然后定义优先级列表,例如左下方、下方、右下方,按顺序进行。不要两次访问节点,但在第一次访问它们时将它们标记为已查看,然后将它们添加到您的树中。

或者,定义如何定义父节点的优先级模式。根据这个单一的“最佳父”关系构建一棵树,但要确保不要创建循环。