いくつかの階層でデータ項目の位置を特定できるアルゴリズムを開発する必要があります。私はいくつかのデータセットの要素を分類する階層を持っています。階層はタクソノミである - トップエレメントは最も一般的なクラスであり、データセットの任意の要素にマッチします。より深いエレメントには、データセットのサブセットに一致するより特定のクラスが含まれます。階層内のデータアイテムの位置を見つける方法は？
たとえば、ヨットの階層構造を考えてみましょう。私たちはクラスヨットを頂きました。次のレベルでは、セーリングヨットとモーターヨットがあります。 セーリングヨットには2人の子供がいます。クルージングヨットとレーシングヨット。例えば、バイエルンヨットと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
Iが容易深さ優先順序でそれを検索することにより、階層に各サンプルをマッピングすることができます。
一見すると簡単な検索問題ですが、いくつかの問題があります。
第1の難しさ：データ項目にすべての要素が含まれている必要はありません。データ項目には要素の10〜50％が欠けているのが一般的です。たとえば、ヨットドライブは、モーターまたはセイルにしかなり得ないので、多くの情報（1ビットのみ）をもたらすことはありません。これらの要素は、例えばヨットモデルを知っている場合など、より重要な要素を使用して簡単に推論できます。データ項目の他の要素（またはフィールド）はすべて推論できます。
第2の難点：階層内の同じ場所（同じヨットモデル）に対応していても、いくつかの要素はデータ項目によって異なる場合があります。たとえば、セイルエリアは、ボートの所有者がヨットのリグを異なる方法で変更するか、面積値を変更するだけで、大幅に異なる可能性があります。
すでに述べたように、私は階層内のデータセットから別のデータ項目を探し出す必要があります。各データ項目は、異なる精度で配置することができます。精度は、検索プロセスが停止する階層内の深さです。つまり、各データ項目に対応する階層内のパスを取得する必要があり、このパスは不完全である可能性があります。例えば、アルゴリズムは、データ項目がに対応していることを発見することができます。Juliet 23ヨットですが、生産年はまだ分かりません。
それぞれの確率尺度で複数のパスを取得できたらうれしいです。例えば、アルゴリズムはJuliet 23の4つのパスをそれぞれ異なる生産年に25％の確率で返すことができます。
この時点で、私はいくつかのヒューリスティックで深さの最初の検索を使用してこの問題を解決します。それは良い結果をもたらしますが、よりよい結果を得ることは可能だと思います。たぶんあなたはより一般的な方法でこの問題を定式化することができますので、私はそれに関するいくつかの学術論文を検索することができます。