階層内のデータ項目の位置を特定できるアルゴリズムを開発する必要があります。一部のデータセットの要素を分類する階層があります。階層は分類学的です。最上位の要素は、データセットの任意の要素に一致する最も一般的なクラスです。より深い要素には、データセットの一部のサブセットに一致するより具体的なクラスが含まれます。
たとえば、ヨットの階層を考えてみましょう。トップにクラスヨットがあります。次のレベルでは、セーリング ヨットとモーター ヨットがあります。Sailing yachtには、 Cruising yachtとRacing yachtという 2 つの子があります。巡洋艦は、バイエルン ヨットやデュフール ヨットなど、メーカーごとにさらに分けることができます。次に、この各クラスは、船体のタイプ、長さ、帆の面積などによってさらに分類できます。
これはデータセットの例です:
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% の要素を欠いていることはよくあることです。この要素の多くはあまり重要ではありません。たとえば、yacht DriveはMotorまたはSailしかできないため、多くの情報は得られません (1 ビットのみ)。これらの要素は、より重要な要素を使用して簡単に推測できます。たとえば、yacht Modelがわかっている場合、データ項目の他のすべての要素 (またはフィールド) を推測できます。
2 つ目の問題: 要素によっては、階層内の同じ場所 (同じヨット モデル) に対応していても、データ項目ごとに異なる場合があります。たとえば、帆の面積は、ボートの所有者がヨットのリグを別の方法で変更したり、単に面積の値を丸めたりするため、大きく異なる場合があります。
既に述べたように、階層内のデータセットからさまざまなデータ項目を見つける必要があります。各データ項目は、異なる精度で配置できます。精度は、検索プロセスが停止する階層の深さです。つまり、各データ項目に対応する階層内のパスを取得する必要がありますが、このパスは不完全な場合があります。たとえば、アルゴリズムはデータ項目がジュリエット 23ヨットに対応することを検出できますが、製造年はまだ不明な場合があります。
それぞれの確率測定値を使用して複数のパスを取得できれば素晴らしいと思います。たとえば、アルゴリズムは、異なる製造年のジュリエット 23の 4 つのパスをそれぞれ 25% の確率で返すことができます。
現時点では、いくつかのヒューリスティックを使用した深さ優先検索を使用して、この問題を解決しています。良い結果が得られますが、より良い結果が得られる可能性があると思います。おそらく、この問題をより一般的な方法で定式化できるので、それに関する学術論文を検索できます。