JP5269999B2 - 決定木作成装置 - Google Patents

Description

部品組合せと製品番号との対応表である部品構成表について決定木を作成する決定木作成装置に関する。

ＰＣのような製品は複数の部品種類（ＣＰＵ，メモリ，ＨＤＤ，…）が組み合されて構成される。各部品種類には、一般に複数の部品がある（メモリなら５１２ＭＢ，１０２４ＭＢ等）。このような製品の設計では、部品の組合せに応じて異なった製品番号を設定する。ただし、同じ製品番号を持つ部品組合せが存在してもよい。部品組合せと製品番号との対応は一般に表形式（部品構成表と呼ぶ）で記述されるが、部品種類および部品数が多いと組合せが多くなり可読性が悪くなる。そこで、部品組合せと製品番号との対応を、葉頂点のラベルが製品番号に対応し、他の頂点のラベルが分類する部品種類となっている決定木で表現する手法がある。決定木で表現する場合、どのような部品種類で分類していくかによって決定木のサイズ（頂点数）が変わる。サイズの小さい決定木を作成する手法の１つにＩＤ３アルゴリズムを利用した分類部品種類の決定手法がある（例えば、非特許文献１参照）。

J. R. Quinlan, Machine Learning 1 "Induction of Decision Tree," p81-p106 1986.

部品組合せ数が多くなると部品構成表も大きくなり、特定の部品組合せに対する製品番号を調べる際、その部品組合せが表のどこに記載されているのかを検索するのに手間がかかる。決定木で表現すると根頂点から部品に対応する枝をたどっていけば製品番号を知ることができるが、決定木で表現する場合でも、頂点数が多いと一般的に木の深さが深くなり、製品番号を知るまでに手間がかかる。すなわち、同じ内容を表わすのであれば、頂点数は少ない決定木の方が容易に製品番号を知ることができる。

この発明は、上述した事情を考慮してなされたものであり、部品構成表に対応する、頂点数の少ない決定木を生成する決定木作成装置を提供することを目的とする。

上述の課題を解決するため、本発明の決定木作成装置は、複数の部品種類による部品組合せと製品番号との対応表を入力する入力部と、前記対応表に対応する第１対応情報であって、複数の部品組合せを表現する要素である到達条件の和集合である到達条件リストと製品番号とを含む第１対応情報を作成する対応情報作成部と、前記対応表および前記第１対応情報のいずれか１つから、決定木の第１頂点の第１到達条件を作成する第１条件作成部と、前記第１頂点よりも祖先にあたるいずれの第２頂点でも未分類である全ての部品種類を順に該第１頂点の分類部品種類として仮決定する仮決定部と、前記分類部品種類を前記第１頂点とし、前記第１到達条件に応じて該第１頂点から子頂点への枝に部品名を割り振る計算をする分割計算部と、前記第１到達条件および前記分割に応じて前記子頂点ごとに該子頂点の第２到達条件を作成する第２条件作成部と、前記第１対応情報から前記第２到達条件に関連する第２対応情報を抽出する抽出部と、前記第２対応情報に含まれる到達条件リストの要素数を部品種類ごとに計算する要素数計算部と、前記要素数が最も少なくなる部品種類を前記第１頂点の分類部品種類として判定する判定部と、前記判定部が判定した部品種類の第１頂点を作成し、第１頂点から子頂点への枝に割り振る部品名を前記分割計算部の計算結果から作成する頂点枝作成部と、を具備することを特徴とする。

本発明の決定木作成装置によれば、部品構成表に対応する、頂点数の少ない決定木を生成することができる。

実施形態の決定木作成装置のブロック図。 部品構成表の一例を示す図。 部品構成表の一例を示す図。 図２または図３の部品構成表を示す決定木を示す図。 図１の製品番号−到達条件リスト対応情報作成部が利用する到達条件リストの一例を示す図。 図１の製品番号−到達条件リスト対応情報作成部が作成する製品番号−到達条件リスト対応情報の一例を示す図。 図１の決定木作成装置が決定木を作成する動作の一例を示すフローチャート。 図７のステップＳ７１２ １回目までで作成される決定木の一例を示す図。 図１の製品番号−到達条件リスト対応情報作成部、部品分割計算部、および仮子頂点関連製品番号−到達条件リスト対応情報抽出部が含んでもよい縮約処理装置のブロック図。

以下、図面を参照しながら本発明の実施形態に係る決定木作成装置について詳細に説明する。なお、以下の実施形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。
簡単に概要を説明する。決定木の頂点数は部品種類の分類順番によって変わる。うまく分類順番を決定すると小さな決定木が構成される。既知の手法として、ＩＤ３アルゴリズムが知られている。ＩＤ３アルゴリズムは部品種類に対し平均情報量の期待値を計算し、期待値が最大になる部品種類によって分類をおこなう。本実施形態の決定木作成装置は、平均情報量の期待値は利用せず、任意の部品組合せを表現できる到達条件リストの要素数に注目して分類する部品種類を決定する。

本実施形態の決定木作成装置について図１を参照して説明する。
本実施形態の決定木作成装置は、部品構成表入力部１０１、製品番号−到達条件リスト対応情報作成部１０２、作成頂点到達条件作成部１０３、分類部品種類仮決定部１０４、部品分割計算部１０５、仮子頂点到達条件作成部１０６、仮子頂点関連製品番号−到達条件リスト対応情報抽出部１０７、到達条件リスト長計算部１０８、分類部品種類判定部１０９、頂点・枝作成部１１０、決定木出力部１１１を含む。

入力部１０１は、部品組合せと製品番号との対応表（部品構成表）を入力する。部品構成表は、例えば図２および図３に示すものがある。
図２の部品構成表は、機器の全ての部品組合せに対して製品番号を個々に定義した部品構成表の例であり、部品種類Ｘ，Ｙ，Ｚから構成される機器があり、部品ｘ１，ｘ２，ｘ３は部品種類Ｘに分類され、部品ｙ１，ｙ２は部品種類Ｙに分類され、部品ｚ１，ｚ２は部品種類Ｚに分類されると仮定した場合の一例である。図３の部品構成表は、図２と同一の内容を表わす部品構成表の別の記述例（ｉｆ−ｔｈｅｎ−ｅｌｓｅ形式）である。この構成表では、優先度を１→２→…の順に行を読んでいき、部品組み合わせが含まれている行に記載されている製品番号が、その部品組合せに対応する製品番号となる。図２のように全ての部品組合せを記述するより行数が少なくなる利点がある。

ここで、決定木について図４を参照して説明する。なお、決定木の各ノードのことを頂点と呼び、頂点間を結ぶ線を枝と呼ぶ。また、決定木の最上層にある頂点を根頂点と呼び、決定木の最下層にある頂点を葉頂点と呼ぶ。図４の左図では、Ｘが根頂点であり、Ｓ００１、Ｓ００３、およびＳ００２が葉頂点である。図４の右図では、Ｙが根頂点であり、Ｓ００１、Ｓ００３、およびＳ００２が葉頂点である。
図４に示す決定木は、図２または図３の内容と同じ内容を表わしている。部品種類Ｘ→部品種類Ｙの順で分類すると図４の左図に示す決定木が作成され、部品種類Ｙ→部品種類Ｘの順で分類すると図４の右図に示す決定木が作成される。部品種類Ｚの頂点が存在しないのは、部品種類Ｚで分類する必要がなかったためである。例えば、部品組合せ（ｘ３，ｙ２，ｚ１）に対応する製品番号を検索する場合で図４の左図に示される決定木の場合、枝を１回たどれば製品番号がわかるのに対し、図４の右図に示される決定木の場合、枝を２回たどる必要がある。すなわち、頂点数が少ない決定木の方（ここでは図４の左図に示される決定木）が早く製品番号を調べることができる例となっている。

図１に戻って、対応情報作成部１０２は、入力された部品構成表に対応する、製品番号−到達条件リスト対応情報（製品番号毎の到達条件リスト）を作成する。到達条件リストは、複数の部品組合せを表現する要素の和集合であるが、詳細については後に図５を参照して説明する。また、製品番号−到達条件リスト対応情報については後に図６を参照して説明する。なお、入力部１０１と対応情報作成部１０２との代わりに、製品番号−到達条件リスト対応情報を直接入力する対応情報入力部（図示せず）を備えてもよい。

条件作成部１０３は、これから作成しようとする頂点の到達条件を作成する。作成しようとする頂点が決定木の根頂点の場合、条件作成部１０３は、任意の部品組合せを表わす到達条件を、入力部１０１が入力した部品構成表、または、対応情報作成部１０２が作成した、部品構成表に対応する製品番号−到達条件リスト対応情報から作成する。作成しようとする頂点が決定木の根頂点でない場合、既に作成されている親頂点の到達条件および枝に付けられた部品名から到達条件を計算し作成する（条件作成部１０６の結果を利用することもできる）。

仮決定部１０４は、これから作成しようとする頂点において、どの部品種類について分類するかを仮決定する。仮決定部１０４は作成しようとする頂点の祖先にあたる頂点で未分類の全ての部品種類について順に仮決定する。

分割計算部１０５は、仮決定部１０４で決定された分類部品種類で分類すると仮定したとき、枝にどのように部品名を割り振るかを決定する。分割計算部１０５は、枝の本数が最少になるように可能な限り１つの枝に部品名を複数割り振ろうとするが、必ず、最終的に全ての葉頂点が単一の製品番号となるように部品名を枝に分割する。分割計算部１０５が行う部品分割の手法については図７の説明の後で説明する。

条件作成部１０６は、仮決定部１０４で決定された分類部品種類で分類すると仮定したとき、子頂点の到達条件を計算し作成する。

対応情報抽出部１０７は、条件作成部１０６が作成した子頂点の到達条件が関連する製品番号−到達条件リスト対応情報を、対応情報作成部１０２が作成した製品番号−到達条件リスト対応情報から抽出する。

リスト長計算部１０８は、対応情報抽出部１０７が抽出した、子頂点の到達条件が関連する製品番号−到達条件リスト対応情報に現れる到達条件リストの要素数を、全ての子頂点について足し合わせる。

判定部１０９は、仮決定部１０４が仮決定した部品種類の中で、リスト長計算部１０８が計算した要素数の和が最小となるものを、作成しようとする頂点で分類する部品種類として判定する。

作成部１１０は、判定部１０９で判定された部品種類の頂点を作成し、作成された頂点から子頂点へつなぐ枝を作成する。枝に付ける部品名については、分割計算部１０５で行った計算を再びおこなってもよいし、分割計算部１０５で計算された結果を利用することもできる。子頂点が唯一の製品番号に対応する場合は、その製品番号を頂点とする子頂点（葉頂点となる）も作成する。葉頂点が作成されていない枝が残っている場合には、その枝先に作成すべき頂点を次に作成する頂点とし、条件作成部１０３へ渡される。

出力部１１１は、完成した決定木を出力（表示）する。出力部１１１は、作成部１１０が頂点や枝を作成するたびに取得し、作成途中経過を表示してもよい。出力部１１１は、全ての枝先に葉頂点が作成された時点で決定木を出力する。

次に、対応情報作成部１０２で利用する到達条件リストについて図５を参照して説明する。
到達条件リストは任意の部品組合せを表現できるデータ構造である。図５に示す到達条件リストＬは、２つの要素をもっており、最初の要素はＬ_１（Ｘ）×Ｌ_１（Ｙ）×Ｌ_１（Ｚ）で表される部品組合せを、２つ目の要素はＬ_２（Ｘ）×Ｌ_２（Ｙ）×Ｌ_２（Ｚ）で表される部品組合せを表わしている。到達条件リストＬの全体としては、Ｌ_１（Ｘ）×Ｌ_１（Ｙ）×Ｌ_１（Ｚ）で表される部品組合せとＬ_２（Ｘ）×Ｌ_２（Ｙ）×Ｌ_２（Ｚ）で表される部品組合せの和集合で定義される部品組合せを表現していることになる。具体的には、（ｘ１，ｙ１，ｚ１）（ｘ２，ｙ１，ｚ１）（ｘ２，ｙ１，ｚ２）（ｘ２，ｙ２，ｚ１）（ｘ２，ｙ２，ｚ２）（ｘ３，ｙ１，ｚ１）（ｘ３，ｙ１，ｚ２）（ｘ３，ｙ２，ｚ１）（ｘ３，ｙ２，ｚ２）の９種類の部品組合せを表わしている。（ｘ２，ｙ１，ｚ１）は到達条件リストのどちらの要素でも定義されているが問題ない（１つの部品組合せとして考える）。

また、要素数が１の到達条件リストのことを特に到達条件と呼ぶ。到達条件は決定木の各頂点にも設定することができ、その頂点へ到達する部品組合せに対応する。また、図５の到達条件リストＬの最初の要素となっている到達条件を［｛ｘ１，ｘ２｝×｛ｙ１｝×｛ｚ１｝］、２番目の要素となっている到達条件を［｛ｘ２，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］のように記述し、到達条件リストＬを［｛ｘ１，ｘ２｝×｛ｙ１｝×｛ｚ１｝］∪［｛ｘ２，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］のように記述する。

次に、対応情報作成部１０２が作成する製品番号−到達条件リスト対応情報について図６を参照して説明する。
製品番号−到達条件リスト対応情報は、各製品番号に対応する部品組合せを到達条件リストで表現した情報（製品番号毎の到達条件リスト）である。図６の例は、図２または図３の内容と同じ内容を表わす製品番号−到達条件リスト対応情報となっている。図６の製品番号−到達条件リスト対応情報は、［｛ｘ１｝×｛ｙ１｝×｛ｚ１｝］∪［｛ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ１，ｙ２｝×｛ｚ２｝］⇔Ｓ００１，［｛ｘ２｝×｛ｙ２｝×｛ｚ１，ｚ２｝］⇔Ｓ００２， ［｛ｘ２｝×｛ｙ２｝×｛ｚ１，ｚ２｝］⇔Ｓ００３と記述する。

次に、図３に示す部品構成表から決定木を作成する方法について図７を参照して説明する。
（ステップＳ７０１） 入力部１０１が部品構成表を入力する。例えばユーザが用意した部品構成表を入力部１０１が入力する。入力部１０１は、部品種類としてＸ，Ｙ，Ｚの３つがあり、部品種類Ｘには部品ｘ１，ｘ２，ｘ３、部品種類Ｙには部品ｙ１，ｙ２、部品種類Ｚには部品ｚ１，ｚ２があるという情報を得る。

（ステップＳ７０２） 対応情報作成部１０２が入力された部品構成表に対応する製品番号−到達条件リスト対応情報（製品番号毎の到達条件リスト）を作成する。図３の優先度１の行から、到達条件Ｌ１＝［｛ｘ１｝×｛ｙ１｝×｛ｚ１｝］で表される部品組合せは製品番号Ｙ００１に対応することがわかり、同様に、図３の優先度２の行から、到達条件Ｌ２＝［｛ｘ２｝×｛ｙ２｝×｛ｚ１，ｚ２｝］で表される部品組合せは製品番号Ｙ００２に対応することがわかる。次に図３の優先度３の行を見ると到達条件Ｌ３’＝［｛ｘ２｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］が製品番号Ｙ００３対応するとなっているが、Ｌ３’にはＬ２で定義済みの部品組合せが含まれている。すなわち、実際に優先度３の行が表す到達条件リストＬ３は、Ｌ３’で表される部品組合せからＬ２で表される部品組合せを引いた部品組合せとする必要がある。すなわち、Ｌ３＝Ｌ３’−Ｌ２＝［｛ｘ２｝×｛ｙ１｝×｛ｚ１，ｚ２｝］。同様に、図３の優先度４の行についても、到達条件リストＬ４＝Ｌ４’−Ｌ３−Ｌ２−Ｌ１も計算する（Ｌ４’＝［｛ｘ１，ｘ２，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］）。この結果、Ｌ４＝［｛ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ１，ｙ２｝×｛ｚ２｝］となる。到達条件リストに対する差演算の手法については後述する。

最後に同じ製品番号が割り当てられている行の到達条件リスト同士を連結することにより、製品番号毎の到達条件リスト（製品番号−到達条件リスト対応情報）を得る。図３の部品構成表から製品番号−到達条件リスト対応情報を作成する例の場合、到達条件リストＬ１∪Ｌ４が製品番号Ｙ００１に対応し、Ｌ２がＹ００２に対応し、Ｌ３がＹ００３に対応することになる（図６が得られる製品番号−到達条件リスト対応情報である）。

（ステップＳ７０３） 条件作成部１０３がこれから作成しようとする頂点Ｐの到達条件を計算する。決定木は根頂点から葉頂点に向かって順に作成されていく。すなわち、最初に作成しようとする頂点Ｐは根頂点である。根頂点の到達条件となる任意の部品組合せを表わす到達条件が、ステップＳ７０１で入力された部品構成表、または、ステップＳ７０２で作成された製品番号−到達条件リスト対応情報から作成される。頂点Ｐは根頂点なので、全ての部品組合せが到達する到達条件［｛ｘ１，ｘ２，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］が作成される。この到達条件はステップＳ７０１において、どのような部品種類および部品が存在するかわかっているため作成できる。

（ステップＳ７０４） 仮決定部１０４が頂点Ｐにおいて、頂点Ｐの祖先にあたる頂点で未分類の全ての部品種類Ｔ（＝｛ｔ_ａ，ｔ_ｂ，…｝）について、順に部品種類ｔ（∈Ｔ）を選択してゆく。現時点では頂点Ｐは根頂点なので、分類済みの部品種類は存在しない。すなわち、ｔ∈｛Ｘ，Ｙ，Ｚ｝となる。ここで、頂点Pの祖先にあたる頂点とは、決定木の中で頂点Pの位置よりもより根頂点に近いところに位置する頂点のことを示す。

（ステップＳ７０５） 分割計算部１０５が頂点ＰにおいてステップＳ７０４で選択された部品種類ｔで分類する場合、頂点Ｐから子頂点への枝に付ける部品分割を計算する。換言すれば、分割計算部１０５はどのような部品名が付けられた枝を作成すればよいかを計算する。ここで部品分割が不要という結果が得られる場合、今調べている部品種類ｔで分割する意味がないことになる。この場合、ステップＳ７０４に戻り、次の部品種類を選択する。
ｔ＝Ｘの時は図４の左図にあるように、根頂点Ｐからはｘ１とｘ３を付けた枝とｘ２を付けた枝の２本を作成すればよいという結果を算出する。ｘ２を別の枝に割り付けるのは、葉頂点を単一の製造番号に対応させるためで、ｘ１とｘ３を同じ枝に割り付けるのは、枝の本数を最少にするためである（異なる枝に割り付けても葉頂点は単一の製造番号となる）。ｔ＝Ｙの時は図４の右図にあるように、根頂点Ｐからはｙ１を付けた枝とｙ２を付けた枝の２本を作成すればよいという結果を算出する。ｔ＝Ｚの場合は、ｚ１とｚ２を付けた枝１本でよいという結果が得られる。これは、Ｚによる分類は不要であることに対応する。この時点で、部品種類Ｚによる分類は不要であることわかり、以後の処理ではｔ＝Ｚの場合を考える必要がない。分割計算部１０５は、枝の本数が最少になるように、可能な限り１つの枝に部品名を複数割り振ろうとする。加えて、全ての葉頂点が単一の製品番号に対応するように部品名を枝に分割する。枝への部品分割の手法については後述する。

（ステップＳ７０６） 条件作成部１０６が頂点Ｐを部品種類ｔで分類したときの子頂点（Ｃ_ｔ１，Ｃ_ｔ２，…）の到達条件（Ｒ_Ｃｔ１，Ｒ_Ｃｔ２，…）を計算する。部品組合せが対応する製品番号が複数ある場合、子頂点は複数存在することになる。子頂点はこの時点では実際に作られる頂点ではないので仮子頂点と呼ぶことにする。この処理では実際に子頂点を作成する必要はなく、部品種類ｔで頂点Ｐを分類したと仮定したとき、頂点Ｐの仮子頂点（実際には頂点は作成されていないので仮子頂点と記述する）の到達条件だけを計算すればよい。ｔ＝Ｘの場合、ステップＳ７０５の結果から頂点Ｐからｘ１およびｘ３を付けられた枝によってつながる仮子頂点Ｃ_Ｘ１と、ｘ２を付けられた枝によってつながる仮子頂点Ｃ_Ｘ２が作成されることになる。頂点Ｐは根頂点でステップＳ７０３の結果から到達条件は［｛ｘ１，ｘ２，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］である。仮子頂点Ｃ_Ｘ１は頂点Ｐから部品種類Ｘがｘ１およびｘ３に限定された部品組合せが到達するので、到達条件は［｛ｘ１，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］となる。同様にＣ_Ｘ２の到達条件は［｛ｘ２｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］となる。ｔ＝Ｙの場合、ステップＳ７０５の結果から、頂点Ｐからｙ１を付けられた枝によってつながる仮子頂点Ｃ_Ｙ１と、ｙ２を付けられた枝によってつながる仮子頂点Ｃ_Ｙ２が作成されることになり、到達条件はそれぞれ、［｛ｘ１，ｘ２，ｘ３｝×｛ｙ１｝×｛ｚ１，ｚ２｝］および［｛ｘ１，ｘ２，ｘ３｝×｛ｙ２｝×｛ｚ１，ｚ２｝］となる。

（ステップＳ７０７） 対応情報抽出部１０７がステップＳ７０６で作成された仮子頂点の到達条件が関連する製品番号−到達条件リスト対応情報（Ｒ_Ｃｔ１，Ｒ_Ｃｔ２，…）をステップＳ７０２で作成されている製品番号−到達条件リストから抽出する。まず、ｔ＝Ｘの場合を考える。仮子頂点Ｃ_Ｘ１の到達条件［｛ｘ１，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］は、全ての部品組合せが到達する到達条件をもつ根頂点からｘ２に関する部品組合せを含まなくしたものなので、関連する製品番号−到達条件リスト対応情報は、ステップＳ７０２で計算されている製品番号−到達条件リストから部品ｘ２に関する情報を削除したものになる（逆に言うとｘ１，ｘ３が関連するもの）。すなわち、Ｒ_ＣＸ１：［｛ｘ１｝×｛ｙ１｝×｛ｚ１｝］∪［｛ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ１，ｙ２｝×｛ｚ２｝］⇔Ｓ００１，φ⇔Ｓ００２，φ⇔Ｓ００３という製品番号−到達条件リストが得られる。ただし、φは要素数０の到達条件リストを表わす。同様に仮子頂点Ｃ_Ｘ２の到達条件に関してはＲ_ＣＸ２：φ⇔Ｓ００１，［｛ｘ２｝×｛ｙ２｝×｛ｚ１，ｚ２｝］⇔Ｓ００２，［｛ｘ２｝×｛ｙ１｝×｛ｚ１，ｚ２｝］⇔Ｓ００３が得られる。ｔ＝Ｙの場合も同様に、Ｒ_ＣＹ１：［｛ｘ１｝×｛ｙ１｝×｛ｚ１｝］∪［｛ｘ３｝×｛ｙ１｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ１｝×｛ｚ２｝］⇔Ｓ００１，φ⇔Ｓ００２，［｛ｘ２｝×｛ｙ１｝×｛ｚ１，ｚ２｝］⇔Ｓ００３、Ｒ_ＣＹ２：［｛ｘ３｝×｛ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ２｝×｛ｚ２｝］⇔Ｓ００１，［｛ｘ２｝×｛ｙ２｝×｛ｚ１，ｚ２｝］⇔Ｓ００２，φ⇔Ｓ００３が得られる。

（ステップＳ７０８） リスト長計算部１０８が、ステップＳ７０７で計算した製品番号−到達条件リスト対応情報に現れる到達条件リストの要素数を部品種類ｔごとに足し合わせる（｜Ｒ_ｔ｜）。ｔ＝Ｘの場合、Ｒ_ＣＸ１に現れる到達条件リストの要素数（｜Ｒ_ＣＸ１｜）およびＲ_ＣＸ２に現れる到達条件リストの要素数（｜Ｒ_ＣＸ２｜）を足し合わせる。この結果｜Ｒ_Ｘ｜＝｜Ｒ_ＣＸ１｜＋｜Ｒ_ＣＸ２｜＝６となる。ｔ＝Ｙの場合、｜Ｒ_ＣＹ１｜および｜Ｒ_ＣＹ２｜に現れる到達条件リストの要素数を足し合わせ、｜Ｒ_Ｙ｜＝｜Ｒ_ＣＹ１｜＋｜Ｒ_ＣＹ２｜＝８を得る。

（ステップＳ７０９） 判定部１０９が、ステップＳ７０８で計算された部品種類ｔ（∈Ｔ）ごとの到達条件リストの要素数（｜Ｒ_ｔ｜）が最も小さいものを頂点Ｐで分類する部品種類として判定する。ここでの例の場合、｜Ｒ_Ｘ｜＜｜Ｒ_Ｙ｜となっているので、頂点Ｐは部品種類Ｘで分類する頂点とする。

（ステップＳ７１０） 作成部１１０がステップＳ７０９で判定された部品種類Ｘで分類する頂点Ｐを作成する。

（ステップＳ７１１） 作成部１１０が頂点Ｐから子頂点への枝を作成する。子頂点への枝に付ける部品名（部品分割）はステップＳ７０５の結果を再利用する。

（ステップＳ７１２） 作成部１１０が単一の製造番号に対応する葉頂点を作成する。頂点Ｐから部品ｘ１とｘ３が付けられた枝でつながる子頂点Ｃ_Ｘ１の到達条件が関連する製品番号−到達条件リスト対応情報Ｒ_ＣＸ１（ステップＳ７０７の結果を再利用）から子頂点Ｃ_Ｘ１は単一の製品番号Ｓ００１に対応することがわかるため（製品番号がＳ００２およびＳ００３に対応する到達条件リストの要素数が０のため製品番号Ｓ００１以外にはならない）、Ｃ_Ｘ１として製品番号Ｓ００１の葉頂点を作成する。頂点Ｐから部品ｘ２が付けられた枝でつながる子頂点Ｃ_Ｘ２に関しては、Ｒ_ＣＸ２から単一の製品番号には分類できないことがわかるため、まだ葉頂点は作成しない。ここまでの処理で作成される決定木を図８に示す。決定木構成の途中経過も表示するならば出力部１１１へ図８の決定木を渡し、表示する。

（ステップＳ７１３） 作成部１１０が、全ての頂点の枝先が葉頂点（製品番号を表わす頂点）になったかを調べ、全ての頂点の枝先に葉頂点作成されていれば、決定木を出力部１１１へ渡し出力する。一方、葉頂点が作られていない枝先が残っている場合（ここでの例の場合、ステップＳ７１２のＣ_Ｘ２にあたる頂点）、その枝先に付ける頂点を次に作成する頂点Ｐとし、ステップＳ７０３に戻る。

（ステップＳ７０３ ２回目） 条件作成部１０３は作成しようとする頂点Ｐの到達条件を計算する。今、頂点Ｐは到達条件［｛ｘ１，ｘ２，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］をもつ親頂点から部品ｘ２が付けられた枝でつながる子頂点なので、頂点Ｐの到達条件は［｛ｘ２｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］となる（実際はステップＳ７０６で一度計算されているのでこの結果を再利用する）。

（ステップＳ７０４ ２回目） 頂点Ｐにおいて未分類の部品種類ＹとＺなので、仮決定部１０４が、分類部品種類ｔとして、ＹおよびＺを選択する。

（ステップＳ７０５ ２回目〜ステップＳ７０９ ２回目） 分割計算部１０５が部品種類ｔで分類した時の枝への部品分割を計算する。ここでは、１回目と同様に、ｔ＝Ｙの時は、ｙ１を付けた枝とｙ２を付けた枝の２本を作成すればよいという結果が得られ、ｔ＝Ｚの場合は、ｚ１とｚ２を付けた枝１本でよい（部品種類Ｚでは分類不要）という結果が得られる。この時点で、頂点Ｐにおいて分類する部品種類はＹに決定される。頂点Ｐにおいて分類する部品種類を決定することだけを考えるとステップＳ７０６〜ステップＳ７０９は不要だが、頂点Ｐの子頂点が単一の製品番号に対応するかを調べるため、子頂点の到達条件や、子頂点の関連する製品番号−到達条件リスト対応情報を計算しておく（ステップＳ７０６およびステップＳ７０７）。

（ステップＳ７１０ ２回目） 作成部１１０が、根頂点（頂点Ｐの親頂点）から部品ｘ２が付けられた枝の子頂点として、部品種類Ｙで分類する頂点Ｐを作成する。

（ステップＳ７１１ ２回目） 作成部１１０が頂点Ｐから子頂点への枝を作成する。枝に付ける部品はステップＳ７０５（２回目）の結果を再利用する。

（ステップＳ７１２ ２回目） 作成部１１０が単一の製造番号に対応する葉頂点を作成する。今回、子頂点は全て単一の製造番号に対応し、結果として図４の左図に示す決定木が作成される。ここまでで、全ての枝先に葉頂点が作成されたことになる。

（ステップＳ７１３ ２回目） 作成部１１０が全ての枝先に葉頂点が作成されたことを確認する。すなわち、作成部１１０は決定木が完成されたことを確認する。作成部１１０は出力部１１１へ決定木を渡し表示する。

ここで、ステップＳ７０５での分割計算部１０５が行う枝への部品分割の手法について説明する。この手法は、枝の本数は最少になるように可能な限り１つの枝に部品名を複数割り振ろうとするが、必ず、最終的に全ての葉頂点が単一の製品番号となるように部品名を枝に分割する。ここでは、上記、図７のステップＳ７０５の１回目において、分類部品種類をＸとしたとき、根頂点Ｐからはｘ１とｘ３を付けた枝とｘ２を付けた枝の２本を作成すればよいという結果を出力するまでの手順を説明する。根頂点Ｐの到達条件は既に［｛ｘ１，ｘ２，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］と計算されている。まず、１つの部品ｘ∈｛ｘ１，ｘ２，ｘ３｝を枝に付けた時、その子頂点の到達条件が関連する、製品番号−到達条件リスト対応情報Ｒｘを計算する（図７のステップＳ７０７と同様の手法で計算できる）。実際には、
Ｒ_ｘ１：［｛ｘ１｝×｛ｙ１｝×｛ｚ１｝］∪［｛ｘ１｝×｛ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ１，ｙ２｝×｛ｚ２｝］⇔Ｓ００１，φ⇔Ｓ００２，φ⇔Ｓ００３、
Ｒ_ｘ２：φ⇔Ｓ００１，［｛ｘ２｝×｛ｙ２｝×｛ｚ１，ｚ２｝］⇔Ｓ００２，［｛ｘ２｝×｛ｙ１｝×｛ｚ１，ｚ２｝］⇔Ｓ００３、
Ｒ_ｘ３：［｛ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］⇔Ｓ００１，φ⇔Ｓ００２，φ⇔Ｓ００３
という製品番号−到達条件リスト対応情報が得られる。以後の説明のため、Ｌ（ｘ，ｓ）でＲｘにおける製品番号ｓに対応する到達条件リストを表わすとものとする。例えば、Ｌ（ｘ２，Ｓ００２）は［｛ｘ２｝×｛ｙ２｝×｛ｚ１，ｚ２｝］となる。

次に分割計算部１０５は、２つの部品ｃ１，ｃ２を別々の枝に付けなければならないかどうかの判定を以下の判定手法を利用しておこなう。

（判定手法）
ｃ１＝ｃ２という仮定の下で、任意の２つの製品番号ｓ１，ｓ２（ｓ１≠ｓ２）について、
（Ｌ（ｃ１，ｓ１）∪Ｌ（ｃ２，ｓ１））∩（Ｌ（ｃ１，ｓ２）∪Ｌ（ｃ２，ｓ２））≠φ …（判定式）
が真となるｓ１，ｓ２が存在するか？
上記の判定式が真になるｓ１，ｓ２が存在することは、ｃ１とｃ２を同じ枝に割り当てると葉頂点において製品番号ｓ１とｓ２が分離できないことに対応する。根頂点を部品種類Ｘで分類する場合に作成する枝を計算する場合には、部品種類Ｘに属する部品｛ｘ１，ｘ２，ｘ３｝の任意の２つの部品の組合せ（ｘ１，ｘ２）（ｘ１，ｘ３）（ｘ２，ｘ３）について上記の判定手法を適用すればよい。この例の場合、ｘ１とｘ２、および、ｘ２とｘ３は別々の枝に分ける必要があり、ｘ１とｘ３は分ける必要がないという結果が得られる。すなわち、根頂点を部品種類Ｘで分類する場合、根頂点からは、ｘ１とｘ３が付けられた枝とｘ２が付けられた枝の２本の枝を作成する必要があることになる。

次に、対応情報作成部１０２、分割計算部１０５、および対応情報抽出部１０７が行うことが望ましい縮約処理について図９を参照して説明する。

到達条件リストは任意の部品組合せを表わすことのできるデータ構造であるが、部品組合せと到達条件リストは一対一対応していない（同じ部品組合せを表わす到達条件リストは複数存在する）。本実施形態においては、同じ内容を表わす到達条件リストであれば、要素数（到達条件）が少ない方が、頂点数の小さな決定木が構成されやすく、かつ、計算時間・計算に必要なメモリ領域の面でも有利となる。したがって、到達条件リストに関する演算をおこなう対応情報作成部１０２、分割計算部１０５、および対応情報抽出部１０７においては、到達条件リストの要素数（長さとも称す）をなるべく短くする処理（縮約処理）が含まれていることが望ましい。

図９は縮約処理を行う装置のブロック図である。この装置は、到達条件リスト入力部９０１、部品追加部９０２、重複到達条件削除部９０３、到達条件リスト出力部９０４を含んでいる。ここでは、到達条件リストＬ＝［｛ｘ１｝×｛ｙ１｝×｛ｚ１｝］∪［｛ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１｝×｛ｙ１，ｙ２｝×｛ｚ２｝］（図６のＳ００１に対応する到達条件リストと同一）を縮約する手法を説明する。説明のため、到達条件リストＬの４つの要素をそれぞれＬ^１，Ｌ^２，Ｌ^３，Ｌ^４と記述する（Ｌ^１＝［｛ｘ１｝×｛ｙ１｝×｛ｚ１｝］，Ｌ^２＝［｛ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］，Ｌ^３＝［｛ｘ１｝×｛ｙ２｝×｛ｚ１，ｚ２｝］，Ｌ^４＝［｛ｘ１｝×｛ｙ１，ｙ２｝×｛ｚ２｝］、Ｌ＝Ｌ^１∪Ｌ^２∪Ｌ^３∪Ｌ^４）。

まず、到達条件リスト入力部９０１が縮約したい到達条件リストＬを入力する。次に、部品追加部９０２は到達条件リストＬで定義されている部品種類（Ｘ，Ｙ，Ｚ）のそれぞれに関してＬ内で現れる部品を調べる。今回の例の場合、Ｘに属する部品でＬ内に現れているのは｛ｘ１，ｘ３｝（＝Ｘ’とおく）、Ｙに属する部品でＬ内に現れているのは｛ｙ１，ｙ２｝（＝Ｙ’とおく）、Ｚに属する部品でＬ内に現れているのは｛ｚ１，ｚ２｝（＝Ｚ’とおく）である。次に、Ｌの各要素（Ｌ^１，Ｌ^２，Ｌ^３，Ｌ^４）へ、Ｌが表している部品組合せが変わらない範囲で、Ｘ’，Ｙ’，Ｚ’の要素となっている部品を追加していく。例えば、Ｌ^１にｚ２を追加するとＬ^１’＝［｛ｘ１｝×｛ｙ１｝×｛ｚ１，ｚ２｝］となり、元のＬ^１と比べて部品組合せ｛ｘ１｝×｛ｙ１｝×｛ｚ２｝が新たに含まれることになるが、｛ｘ１｝×｛ｙ１｝×｛ｚ２｝は元々Ｌ^４の表す部品組合せに含まれているので、Ｌ全体としては意味が変わっていない。このようにＬの意味が変わらないように、Ｌ^１，Ｌ^２，Ｌ^３，Ｌ^４へ部品を追加していくと、Ｌ^１には部品ｘ３，ｙ２，ｚ２を、Ｌ^２には部品ｘ１を、Ｌ^３には部品ｘ３，ｙ１をＬ^４には部品ｘ３，ｚ１をそれぞれ追加し、結果として、部品追加部９０２の処理結果はＬ＝［｛ｘ１，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］∪［｛ｘ１，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］となる。部品追加部９０２の処理結果は、重複到達条件削除部９０３へ渡る。重複到達条件削除部９０３は、削除しても意味の変わらない到達条件リストの要素（到達条件）を削除する。具体的には、Ｌの任意の２つの要素（到達条件）Ｌ^ｉ，Ｌ^ｊ（ｉ＜ｊ）について、（Ｌ^ｉの表す部品組合せ）⊇（Ｌ^ｊの表す部品組合せ）となっている場合、Ｌ^ｊをＬから削除する。この処理を適用しても到達条件リストが表す部品組合せが変わらないのは明らかである。今回の例の場合、最終的に到達条件リストＬは、Ｌ＝［｛ｘ１，ｘ３｝×｛ｙ１，ｙ２｝×｛ｚ１，ｚ２｝］となり、このＬが到達条件リスト出力部９０４から出力される。

これまで示したように、本実施形態の決定木作成装置を実現するためには、到達条件（リスト）に関する様々な集合演算を利用する必要がある。次にその演算手法を示す。

（１）到達条件リストＬ_１の表す部品組合せと到達条件リストＬ_２の表す部品組合せの和集合を表わす到達条件リストＬ（＝Ｌ_１∪Ｌ_２）の構成手法：
Ｌを、Ｌ_１の要素（到達条件）とＬ_２の要素（到達条件）の両方を要素とするリストとする。

（２）到達条件Ｌ^１の表す部品組合せと到達条件Ｌ^２の表す部品組合せの共通部品組合せを表わす到達条件Ｌ（＝Ｌ^１∩Ｌ^２）の構成手法：
Ｌ^１＝［Ｓ^ａ×Ｓ^ｂ×…×Ｓ^ｚ］、Ｌ^２＝［Ｔ^ａ×Ｔ^ｂ×…×Ｔ^ｚ］とおく。ただし、Ｓ^ｉおよびＴ^ｉは部品種類ｉに属する部品の部分集合を表わす。このとき、Ｌ＝［（Ｓ^ａ∩Ｔ^ａ）×（Ｓ^ｂ∩Ｔ^ｂ）×…×（Ｓ^ｚ∩Ｔ^ｚ）］とする。ただし、Ｓ^ｉ∩Ｔ^ｉ＝φとなる部品種類ｉが存在する場合、Ｌ＝φとする。

（３）到達条件リストＬ_１の表す部品組合せと到達条件Ｌ^２の表す部品組合せの共通部品組合せを表わす到達条件リストＬ（＝Ｌ_１∩Ｌ^２）の構成手法：
Ｌ_１＝Ｌ_１ ^１∪…∪Ｌ_１ ^ｎとおく。ただし、Ｌ_１ ^ｉはＬ_１の要素となっている到達条件を表わす。このとき、Ｌ＝（Ｌ_１ ^１∩Ｌ^２）∪…∪（Ｌ_１ ^ｎ∩Ｌ^２）とする。

（４）到達条件リストＬ_１の表す部品組合せと到達条件リストＬ_２の表す部品組合せの共通部品組合せを表わす到達条件リストＬ（＝Ｌ_１∩Ｌ_２）の構成手法：
Ｌ_２＝Ｌ_２ ^１∪…∪Ｌ_２ ^ｍとおく。ただし、Ｌ_２ ^ｉはＬ_２の要素となっている到達条件を表わす。このとき、Ｌ＝（（Ｌ_１∩Ｌ_２ ^１）∩…）∩Ｌ_２ ^ｍとする。

（５）到達条件Ｌ^１の表す部品組合せから到達条件Ｌ^２の表す部品組合せを取り除いた部品組合せを表わす到達条件リストＬ（＝ Ｌ^１−Ｌ^２）の構成手法：
Ｌ^１＝［Ｓ^ａ×Ｓ^ｂ×…×Ｓ^ｚ］、Ｌ^２＝［Ｔ^ａ×Ｔ^ｂ×…×Ｔ^ｚ］とおく。ただし、Ｓ^ｉおよびＴ^ｉは部品種類ｉに属する部品の部分集合を表わす。Ｓ^ｉ∩Ｔ^ｉ＝φとなる部品種類ｉが存在する場合、Ｌ^１とＬ^２に共通する部品組合せが存在しないのでＬ＝Ｌ^１とする。Ｓ^ｉ∩Ｔ^ｉ＝φとなる部品種類ｉが存在しない場合、Ｌ＝［（Ｓ^ａ￥Ｔ^ａ）×Ｓ^ｂ×…×Ｓ^ｚ］∪［Ｓ^ａ×（Ｓ^ｂ￥Ｔ^ｂ）×…×Ｓ^ｚ］∪…∪［Ｓ^ａ×Ｓ^ｂ×…×（Ｓ^ｚ￥Ｔ^ｚ）］とする。ここで、Ｓ^ｉ￥Ｔ^ｉは集合Ｓ^ｉからＴ^ｉに含まれる要素を削除した集合を表わす。ただし、Ｓ^ｉ￥Ｔ^ｉ＝φとなる到達条件はＬの要素から削除する。

（６）到達条件リストＬ_１の表す部品組合せから到達条件Ｌ^２の表す部品組合せを取り除いた部品組合せを表わす到達条件リストＬ（＝Ｌ_１−Ｌ^２）の構成手法：
Ｌ_１＝Ｌ_１ ^１∪…∪Ｌ_１ ^ｎとおく。ただし、Ｌ_１ ^ｉはＬ_１の要素となっている到達条件を表わす。このとき、Ｌ＝（Ｌ_１ ^１−Ｌ^２）∪…∪（Ｌ_１ ^ｎ−Ｌ^２）とする。

（７）到達条件リストＬ_１の表す部品組合せから到達条件リストＬ_２の表す部品組合せを取り除いた部品組合せを表わす到達条件リストＬ（＝Ｌ_１−Ｌ_２）の構成手法：
Ｌ_２＝Ｌ_２ ^１∪…∪Ｌ_２ ^ｍとおく。ただし、Ｌ_２ ^ｉはＬ_２の要素となっている到達条件を表わす。このとき、Ｌ＝（（Ｌ_１−Ｌ_２ ^１）−…）−Ｌ_２ ^ｍとする。

（８）到達条件Ｌ^１の表す部品組合せに到達条件Ｌ^２の表す部品組合せが包含されているかの判定手法（Ｌ^１⊇Ｌ^２ ？）：
Ｌ^１＝［Ｓ^ａ×Ｓ^ｂ×…×Ｓ^ｚ］、Ｌ^２＝［Ｔ^ａ×Ｔ^ｂ×…×Ｔ^ｚ］とおく。ただし、Ｓ^ｉおよびＴ^ｉは部品種類ｉに属する部品の部分集合を表わす。このとき、全ての部品種類ｉについて、Ｓ^ｉ⊇Ｔ^ｉとなっていれば、Ｌ^１⊇Ｌ^２が成り立つ。

以上の実施形態によれば、頂点数の少ない決定木を作成することができ、特定の部品組合せに対応する製品番号の検索等を効率よく実行できる。しかし、場合によってはユーザが指定する部品種類で分類した方がユーザにとって見やすい決定木となることもある。例えば、図３（図２でも同じ）の部品構成表を利用し出荷した機器において、後で部品ｙ２に欠陥が見つかり、関連する製品番号を見つけ出したいという状況を想定する。このとき、ユーザが根頂点は部品種類Ｙで分類すると指定し図４の右図に示す決定木が作成できれば、すぐに部品ｙ２の関連する製品番号はＳ００１とＳ００２であることが分かる。このようにユーザによる分類部品種類の指定に関しても、ユーザ指定情報をあらかじめ仮決定部１０４や判定部１０９に入力しておくことにより実現することができる（分類部品種類の判定処理を無視しユーザ指定の部品種類を利用するだけ）。このときユーザが指定していない頂点の分類部品種類に関しては、本実施形態の決定木作成装置によれば、ユーザの指示を満たした上で頂点数の少ない決定木を作成することができ、ユーザにとって全体が俯瞰しやすく、かつ、見やすい決定木を作成することができる。

本実施形態の決定木作成装置の特徴の１つは、製品番号−到達条件リスト対応情報に現れる到達条件リストの要素数を基準として、分類する部品種類を決定する仕組みにある。決定木の（葉）頂点に付けられる到達条件リストは必ず要素数が１となることが分かっていることから、対応情報抽出部１０７が計算する製品番号−到達条件リスト対応情報に現れる到達条件リストの要素数が１にならない限り葉頂点を作れないことになる（到達条件リストの縮約が完全におこなわれていると仮定）。このことから、なるべく早い段階（根頂点に近い頂点）で、製品番号−到達条件リスト対応情報に現れる到達条件リストの要素数の和を減らしておく方が、葉頂点に早く到達する、すなわち、頂点数の少ない決定木が作成できるという効果につながる。到達条件リスト縮約機能を利用し、同じ内容を表わす到達条件リストであれば要素数（到達条件）が少ない方が、頂点数の小さな決定木が構成されやすい理由は、縮約すれば製品番号−到達条件リスト対応情報に現れる到達条件リストの要素数が１となり、葉頂点をすぐに作成できるにも関わらず、縮約しない状態ではすぐに葉頂点が作成できると判断できずに、その分類部品種類を選択しないという誤った選択をする可能性があるためである。

一方、既存のＩＤ３アルゴリズムは情報量の期待値を利用している。本実施形態の手法とＩＤ３アルゴリズムのどちらの手法も決定木の頂点数を少なくするために利用できるが、どちらの手法も選ばれた部品種類で部品を分類すれば必ず決定木の頂点数が最少になることは保証しない。また、本実施形態ではＩＤ３アルゴリズムより常に頂点数が少ない決定木を構成することも保証しないが、実験では、ＩＤ３アルゴリズムを利用すると決定木の頂点数が４８１となる部品構成表を、本発明の手法では頂点数が３４１の決定木にできるという結果が得られている。少なくとも本実施形態の決定木作成装置による手法はＩＤ３アルゴリズムと同等以上の効果を奏する。

本実施形態の手法とＩＤ３アルゴリズムでは、部品種類を選ぶアプローチが異なっているため、場合によって使い分けることが有効である。例えば、本実施形態の決定木作成装置において、部品種類Ｘまたは部品種類Ｙのどちらで分類すればよいかを判定するとき、比較対象となる到達条件リストの要素数の和が等しいとき、基本的に適当に分類する部品種類を選ぶ。しかし、このような状況の時に、判定部１０９がＩＤ３アルゴリズムを利用して部品種類を選択すればよりよいと考えられる部品種類を選択することができ、適当に部品種類を選ぶよりは、最終的に頂点数の少ない決定木が作成される可能性が上がる。

以上に示した実施形態によれば、部品構成表を頂点数の少ない決定木で表示することにより可読性が上がる。例えば、特定の部品組合せに対する製品番号を調べる際には、根頂点から部品に対応する枝をたどっていけば製品番号を知ることができ、表形式の場合、表のどこにその部品組合せが記載されているのかを検索する必要があることに比べ容易かつ高速である。また、ＩＤ３アルゴリズムを利用すると決定木の頂点数が４８１となる部品構成表を本発明の手法では頂点数が３４１の決定木に変換する結果が得られており、一般的に、製品番号を知るために枝をたどる回数がＩＤ３アルゴリズムを利用する場合より少なくて済む。

本実施形態によれば、部品構成表が正しく作成されているかの検証を行う際にも、頂点数の少ない決定木で表現でき、全体を俯瞰しやすく、効率が上がる。特定の部品不良により影響のある製品番号を検索したい場合には、その部品が属する部品種類を決定木の根頂点となるように指定すれば、根頂点から不良部品をたどって到達する子頂点を根頂点とする部分木の葉に全ての関連製品番号が表示されることになり、高速に関連する製品番号を検索できる。

なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。

部品組合せと製品番号との対応表である部品構成表を表示する際に部品構成表を決定木で提示する際に利用できる。

１０１…部品構成表入力部、１０２…製品番号−到達条件リスト対応情報作成部、１０３…作成頂点到達条件作成部、１０４…分類部品種類仮決定部、１０５…部品分割計算部、１０６…仮子頂点到達条件作成部、１０７…仮子頂点関連製品番号−到達条件リスト対応情報抽出部、１０８…到達条件リスト長計算部、１０９…分類部品種類判定部、１１０…頂点・枝作成部、１１１…決定木出力部。

Claims (5)

1. 複数の部品種類による部品組合せと製品番号との対応表を入力する入力部と、
   前記対応表に対応する第１対応情報であって、複数の部品組合せを表現する要素である到達条件の和集合である到達条件リストと製品番号とを含む第１対応情報を作成する対応情報作成部と、
   前記対応表および前記第１対応情報のいずれか１つから、決定木の第１頂点の第１到達条件を作成する第１条件作成部と、
   前記第１頂点よりも祖先にあたるいずれの第２頂点でも未分類である全ての部品種類を順に該第１頂点の分類部品種類として仮決定する仮決定部と、
   前記分類部品種類を前記第１頂点とし、前記第１到達条件に応じて該第１頂点から子頂点への枝に部品名を割り振る計算をする分割計算部と、
   前記第１到達条件および前記分割に応じて前記子頂点ごとに該子頂点の第２到達条件を作成する第２条件作成部と、
   前記第１対応情報から前記第２到達条件に関連する第２対応情報を抽出する抽出部と、
   前記第２対応情報に含まれる到達条件リストの要素数を部品種類ごとに計算する要素数計算部と、
   前記要素数が最も少なくなる部品種類を前記第１頂点の分類部品種類として判定する判定部と、
   前記判定部が判定した部品種類の第１頂点を作成し、第１頂点から子頂点への枝に割り振る部品名を前記分割計算部の計算結果から作成する頂点枝作成部と、を具備することを特徴とする決定木作成装置。
2. 前記対応情報作成部、前記分割計算部、および前記抽出部の少なくとも１つは、
   前記到達条件リストが表す部品組合せが変わらない範囲で、該到達条件リストで定義されている部品種類ごとに、該到達条件リストの要素に部品名を追加する追加部と、
   前記到達条件リストの第１要素が表す部品組合せの集合が該到達条件リストの第２要素が表す部品組合せの集合に含まれる場合には、該第１要素を削除する削除部と、を含むことを特徴とする請求項１に記載の決定木作成装置。
3. 前記入力部と前記対応情報作成部との代わりに、前記第１対応情報を直接入力する対応情報入力部を具備することを特徴とする請求項１に記載の決定木作成装置。
4. 分類部品種類を取得する取得部をさらに具備し、
   前記取得部が分類部品種類を取得する場合には、前記仮決定部は該分類部品種類を前記第１頂点の分類部品種類として仮決定し、前記判定部は前記取得部が取得した分類部品種類を前記第１頂点の分類部品として判定し、前記取得部が分類部品種類を取得しない場合には、前記仮決定部は前記第１頂点よりも祖先にあたるいずれの第２頂点でも未分類である全ての部品種類を順に該第１頂点の分類部品種類として仮決定し、前記判定部は前記要素数が最も少なくなる部品種類を前記第１頂点の分類部品種類として判定することを特徴とする請求項１に記載の決定木作成装置。
5. 前記要素数が最も少なくなる部品種類が複数ある場合は、前記判定部はＩＤ３アルゴリズムを利用して前記第１頂点の分類部品種類を判定する請求項１に記載の決定木作成装置。

Images