如何在层次结构中查找数据项位置？

Question

我需要开发一种算法,可以在某个层次结构中定位数据项位置.我有一个层次结构,对某些数据集的元素进行分类.层次结构是分类的 - 顶级元素是最通用的类​​,它匹配数据集的任何元素,更深层的元素包含与数据集的某个子集匹配的更具体的类.

例如,考虑游艇的层次结构.我们有顶级游艇.在下一个级别,我们有帆船游艇和机动游艇.帆船游艇有两个孩子 - 巡航游艇和赛艇游艇.巡洋舰可以由制造商进一步划分,例如Bavaria Yachts和Dufour Yachts.然后,每个类可以进一步除以船体类型,长度,风帆面积等.

这是数据集中的一个示例:

Drive   Class   Manufacturer   Hull type Len  Sails Area ... Model
Sailing Cruiser Bavaria Yachts Mono-hull 25ft 560sqft    ... Bavaria 32
Sailing Cruiser Dufour Yachts  Mono-hull 27ft 580sqft    ... Dufour 32 Classic

通过深度优先顺序搜索,我可以轻松地将每个样本映射到层次结构.

乍一看这是一个简单的搜索问题,但存在一些困难.

第一个难点:数据项不必包含所有元素.数据项通常缺少10%到50%的元素.许多这些元素并不是很重要,例如游艇Drive只能是Motor或Sail,所以它不会带来很多信息(只有1位).可以使用更重要的元素轻松推断这些元素,例如,如果我们知道游艇模型,我们可以推断出数据项的所有其他元素(或字段).

第二个难点:某些元素可能因不同数据项而异,即使它们对应于层次结构中的相同位置(相同的游艇模型).例如,帆船区域可能会有很大差异,因为船主以不同的方式修改游艇的装备或仅仅是圆形区域值.

正如我已经提到的,我需要从层次结构中的数据集中找到不同的数据项.每个数据项可以以不同的精度定位.精度是层次结构中搜索过程停止的深度.换句话说,我需要在层次结构中获取与每个数据项对应的路径,并且此路径可能不完整.例如,算法可以发现数据项对应于Juliet 23游艇,但生产年份仍然是未知的.

如果我可以为每个路径获得具有概率测量的多个路径,那将会很酷.例如,算法可以为不同的生产年份返回Juliet 23的 4条路径,每条路径的概率为25%.

此时我使用深度优先搜索和一些启发式方法解决了这个问题.它给出了很好的结果,但我认为可以获得更好的结果.也许你可以用更通用的方式来表达这个问题,这样我就可以搜索一些关于它的学术论文.

Answer 1

我觉得SQL确实可以帮助你解决你的困难，

对于您的第一个困难：使用 NVL(field, value-if-null)

示例：赛艇的打印类型和生产年份（如果存在）

SELECT Y.TYPE, NVL(Y.PRDYEAR, 'UNKNOWN')
FROM T_YACHT Y WHERE Y.CLASS = 'RACING'

示例：获取生产年份在 2000 年以上的所有游艇

SELECT * FROM T_YACHT Y WHERE
NVL(Y.PRDYEAR,TO_TIMESTAMP('01-01-0001','DD-MM-YYYY'))
    > TO_TIMESTAMP('01-01-2000','DD-MM-YYYY')

对于第二个困难：使用 GROUP BY\CASCADING-SQL\DISTINCT\NVL

示例：查看赛艇有多少种类型

SELECT Y.TYPE, COUNT(Y.ID) AS YACHT_TYPE
FROM T_YACHT Y
WHERE Y.CLASS = 'RACING'
GROUP BY Y.TYPE