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

我需要开发一个算法，可以找到某些层次结构中的数据项位置。我有层次结构来分类某些数据集的元素。层次结构是分类学的 - 顶级元素是最通用的类，它匹配数据集的任何元素，更深的元素包含更多与数据集的某个子集相匹配的特定类。如何查找层次结构中的数据项目位置？

例如，考虑游艇的层次结构。我们有顶级游艇。在下一级我们有帆船游艇和机动游艇。 帆船游艇有两个小孩 - 巡游游艇和竞速游艇。巡洋舰可以由制造商进一步划分，例如巴伐利亚游艇和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％的元素是很常见的。很多这样的元素并不是很重要，例如游艇变频器只能是电机或航行所以它不会带来很多信息（只有1位）。这些元素可以使用更重要的元素轻松推断，例如，如果我们知道游艇模型，我们可以推断数据项的所有其他元素（或字段）。

第二个难点：即使它们对应于层次结构中相同的地方（相同的游艇模型），某些元素可能在不同的数据项之间有所不同。例如帆船区域可能会有很大差异，因为船主以不同的方式修改了游艇的钻井平台，或者只是围绕面积值进行修改。

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

这将是很酷，如果我可以得到多个路径与概率测量每个。例如，对于不同的生产年份，算法可以返回4个路径，每个路径的概率为25％。

在这一刻我用一些启发式的深度优先搜索来解决这个问题。它给出了很好的结果，但我认为有可能获得更好的结果。也许你可以用更一般的方式来制定这个问题，这样我可以搜索一些有关它的学术论文。

来源

2013-01-22 Lazin

我觉得SQL可以真正帮助您解决困难，

你的第一个困难：使用NVL（字段值是否为空）

例如：打印类型&生产一年（如果存在）的赛艇

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-23 15:51:09

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

回答

相关问题