5

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

例如,考虑游艇的层次结构。我们有一流的游艇在顶部。在下一个级别,我们有帆船机动游艇帆船有两个孩子——巡航游艇赛艇。巡洋舰可以按制造商进一步划分,例如Bavaria YachtsDufour 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只能是MotorSail,因此它不会带来很多信息(只有 1 位)。这些元素可以使用更重要的元素轻松推断,例如,如果我们知道游艇模型,我们可以推断数据项的所有其他元素(或字段)。

第二个困难:一些元素在不同的数据项之间可能会有所不同,即使它们对应于层次结构中的相同位置(相同的游艇模型)。例如,帆面积可能会有很大差异,因为船主以不同的方式修改他们的游艇装备或只是四舍五入面积值。

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

如果我能得到多条路径,每个路径都有概率度量,那就太酷了。例如,算法可以为Juliet 23返回不同生产年份的 4 条路径,每条路径的概率为 25%。

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

4

1 回答 1

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
于 2013-03-23T15:51:09.867 回答