(57)【特許請求の範囲】
【請求項１】
部品種類の集合をD={d1, ..., dn}とし、部品種類d（∈D）に分類される部品をParts(d)とし、
∀d∈Dについて、Parts(d)の部分集合Parts’ (d)（⊆Parts(d)）を定義したもの（「到達条件」という。）が直積集合すなわち
【数１】
0005175607.tif 000009
に含まれる部品組み合せを表し、
到達条件を要素としてもつリスト（「到達条件リスト」という。）は要素となっている到達条件が表す部品組み合わせの和集合に含まれる部品組み合わせを表し、
コンピュータが、メモリに記憶した到達条件リストの集合Lから識別子の集合Mへの部分写像 g: L→M（∀l1,l2∈Lについてl1∩l2＝φまたはg(l1)=g(l2)を満たすものに限る）と、前記コンピュータに逐次入力される分類部品種類とから、決定木を根頂点から子頂点に向かって段階的に作成し、前記コンピュータが、以下の条件すなわち
条件１：頂点（葉を除く）は部品種類をラベルとしてもつこと、
条件２：葉は単一の識別子をラベルとしてもつこと、
条件３：枝は要素数が１以上の部品名の集合をラベルとしてもつこと、
条件４：逐次入力される分類部品種類の順番は決定木の頂点ラベルと対応している。逐次入力される分類部品種類の順番と頂点ラベルとの対応関係は以下の制約すなわち
制約１：最初に入力された部品分類種類は決定木の根頂点のラベルとする制約
制約２：２番目以降に入力された部品分類種類は、親頂点のラベルが決定されている頂点とであれば自由に対応付けられるという制約
を満たすこと、
条件５：頂点数が最少となっていること、
条件６：根頂点から枝に付けられた部品名を辿って到達する葉頂点ラベル（識別子）は、入力された部分写像gから得られる識別子と一致すること、を満たすように前記決定木を作成する決定木作成装置。
【請求項２】
前記コンピュータが、
前記直積集合から識別子の集合Mへの部分写像すなわち
【数２】
0005175607.tif 000010
から、前記到達条件リストの集合Lから識別子の集合Mへの部分写像 g: L→M（∀l1,l2∈Lについてl1∩l2＝φまたはg(l1)=g(l2)を満たすものに限る）を作成し、作成された部分写像 g: L→Mと逐次入力される分類部品種類から、前記条件１乃至６を満たす決定木を根頂点から子頂点に向かって段階的に作成していくことを特徴とする請求項１記載の決定木作成装置。
【請求項３】
前記コンピュータが、
前記条件１乃至３を満たす決定木から、前記到達条件リストの集合Lから識別子の集合Mへの部分写像 g: L→M（∀l1,l2∈Lについてl1∩l2＝φまたはg(l1)=g(l2)を満たすものに限る）を作成し、作成された部分写像 g: L→Mと逐次入力される分類部品種類から、前記条件１乃至６を満たす決定木を根頂点から子頂点に向かって段階的に作成していくことを特徴とする請求項１記載の決定木作成装置。
【請求項４】
前記コンピュータが、
前記条件１乃至３を満たす決定木と該決定木の部分木から、該部分木の再構成に必要十分な、前記到達条件リストの集合Lから識別子の集合Mへの部分写像 g: L→M（∀l1,l2∈Lについてl1∩l2＝φまたはg(l1)=g(l2)を満たすものに限る）を作成し、作成された部分写像 g: L→Mと、逐次入力される分類部品種類から、前記条件１乃至６を満たす部分木を前記部分木の根頂点から子頂点に向かって段階的に作成していくことを特徴とする請求項１記載の決定木作成装置。
【請求項５】
前記コンピュータが、
前記到達条件リストと識別子との対応関係をルールとし、
優先度を付与した前記ルールを優先度付ルールとし、
前記優先度付ルールの集合を、優先度に応じた順序付けが必ず行えるルールを要素とする部品組み合わせ表とし、
前記部品組み合わせ表において、ある部品組み合わせに対応する識別子を検索する場合、優先度の高い到達条件リストから、その部品組み合わせが到達条件リストに含まれているかを調べ、部品組み合わせが含まれていればそのルールに対応する識別子を対応させ（if then else形式）、
入力される前記部品組み合わせ表から、前記到達条件リストの集合Lから識別子の集合Mへの部分写像 g: L→M（∀l1,l2∈Lについてl1∩l2＝φまたはg(l1)=g(l2)を満たすものに限る）を作成し、
作成された部分写像 g: L→Mと、逐次入力される分類部品種類から、前記条件１乃至６を満たす決定木を根頂点から子頂点に向かって段階的に作成していくことを特徴とする請求項１記載の決定木作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部品組み合せと識別子の多対一の関係を設定し、識別子により製品の仕様を判別できるようにするために用いられ、指定の部品種類分類順に従った頂点数が最少の決定木を作成する決定木作成装置に関する。
【背景技術】
【０００２】
部品組み合せと識別子の多対一の関係を設定し、識別子により製品の仕様を判別できるようにすることは、パソコン製造分野や自動車製造分野でしばしば行われる。指定の部品種類分類順に従った頂点数が最少の決定木として表示することで、部品組み合わせに対して正しい識別子が設定されているかどうかの検証作業を容易にする。
【０００３】
部品組み合わせと識別子の多対一の関係は、一般には表形式で書かれるが部品組み合わせが膨大になると表のサイズも大きくなる。表のサイズを大きくさせないために、ｉｆ  ｔｈｅｎ  ｅｌｓｅ形式で解釈する表で管理する方法も考えられている。
【非特許文献１】Ｂｅａｔｅ  Ｂｏｌｌｉｇ，Ｉｎｇｏ  Ｗｅｇｅｎｅｒ，“Ｉｍｐｒｏｖｉｎｇ  ｔｈｅ  Ｖａｒｉａｂｌｅ  Ｏｒｄｅｒｉｎｇ  ｏｆ  ＯＢＤＤｓ  Ｉｓ  ＮＰ−Ｃｏｍｐｌｅｔｅ”，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，４５（９）：９９３〜１００２，Ｓｅｐｔｅｍｂｅｒ  １９９６．
【非特許文献２】Ｔｏｍ  Ｍ．  Ｍｉｔｃｈｅｌｌ，“Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ”，ＭｃＧｒａｗ−Ｈｉｌｌ  Ｓｅｒｉｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  １９９７．
【非特許文献３】Ｉａｎ  Ｈ．  Ｗｉｔｔｅｎ，  Ｅｉｂｅ  Ｆｒａｎｋ，“Ｄａｔａ  Ｍｉｎｉｎｇ：  Ｐｒａｃｔｉｃａｌ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  Ｔｏｏｌｓ  ａｎｄ  Ｔｅｃｈｎｉｑｕｅｓ”，Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ，Ｊｕｎｅ  ２００５．
【発明の開示】
【発明が解決しようとする課題】
【０００４】
部品組み合わせと識別子の多対一の関係は、一般には表形式で書かれるが部品組み合わせが膨大になると表のサイズも大きくなる。表のサイズを大きくさせないために、ｉｆ  ｔｈｅｎ  ｅｌｓｅ形式で解釈する表で管理する方法も考えられている。しかし、ｉｆ  ｔｈｅｎ  ｅｌｓｅ形式で解釈する表を利用すると、部品組み合わせと識別子との対応を読み解く手間がかかるようになり、誤った対応表となりやすい。そこで、本発明は、部品組み合わせと識別子の多対一の関係をユーザの指定した部品種類分類順に従って頂点数が最少の決定木に変換する決定木作成装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の一観点に係る決定木作成装置は、
部品種類の集合をD={d1, ..., dn}とし、
部品種類d（∈D）に分類される部品をParts(d)とし、
∀d∈Dについて、Parts(d)の部分集合Parts’ (d)（⊆Parts(d)）を定義したもの（「到達条件」という。）が直積集合すなわち
【数３】
0005175607.tif 000002
【０００６】
に含まれる部品組み合せを表し、
到達条件を要素としてもつリスト（「到達条件リスト」という。）は要素となっている到達条件が表す部品組み合わせの和集合に含まれる部品組み合わせを表し、
到達条件リストの集合Lから識別子の集合Mへの部分写像 g: L→M（∀l1,l2∈Lについてl1∩l2＝φまたはg(l1)=g(l2)を満たすものに限る）と、逐次入力される分類部品種類とから、決定木を根頂点から子頂点に向かって段階的に作成する決定木作成装置である。
【０００７】
前記決定木は、以下の条件すなわち
条件１：頂点（葉を除く）は部品種類をラベルとしてもつこと、
条件２：葉は単一の識別子をラベルとしてもつこと、
条件３：枝は要素数が１以上の部品名の集合をラベルとしてもつこと、
条件４：逐次入力される分類部品種類の順番は決定木の頂点ラベルと対応している。逐次入力される分類部品種類の順番と頂点ラベルとの対応関係は以下の制約すなわち
制約１：最初に入力された部品分類種類は決定木の根頂点のラベルとする制約
制約２：２番目以降に入力された部品分類種類は、親頂点のラベルが決定されている頂点とであれば自由に対応付けられるという制約
を満たすこと、
条件５：頂点数が最少となっていること、
条件６：根頂点から枝に付けられた部品名を辿って到達する葉頂点ラベル（識別子）は、入力された部分写像gから得られる識別子と一致すること、を満たす。
【発明の効果】
【０００８】
本発明によれば、分類する部品種類が入力される毎に、その部品種類をラベルとしてもつ頂点と、その頂点から子頂点へ繋げる枝を作成する処理を実行する。その際、枝に付与するラベル（部品名の集合）は、全ての分類部品種類が入力された時点で、決定木の葉頂点ラベルが単一の識別子となり、かつ、頂点数が最少となるように到達条件リストに対する演算を利用し割り振る。到達条件リストに対する演算は、部品組み合わせを展開せずにおこなえるため、状態爆発を抑えられ高速である。
【発明を実施するための最良の形態】
【０００９】
以下、図面を参照しながら本発明の実施形態を説明する。
【００１０】
部品種類の集合をDとし、d∈Dに分類される部品の集合をParts(d)と表す。パソコンの部品を例にすると、CPUやハードディスクなどが部品種類にあたり、例えばPentium（登録商標）4やCeleron（登録商標）がCPUに分類される部品になる。また、300GB HDDや600GB HDDといった部品がハードディスクに分類される部品となる。
【００１１】
図１は本発明の種々の実施形態に係る決定木作成装置を示すブロック図である。
【００１２】
１は、分類する部品種類を入力する分類部品種類入力装置である。分類部品を入力するのは、ユーザであってもよいし、外部の装置（ID3アルゴリズム等）であってもよい。
【００１３】
２は、第１の実施形態に係る到達条件リストの集合Lから識別子の集合Mへの部分写像 g: L→Mを入力する写像入力装置である。部分写像 g: L→Mを入力するのはユーザであってもよいし、同図に示す到達条件リストから識別子への写像作成装置７、９、１２、１４であってもよい。
【００１４】
３は、分類部品種類入力装置１で入力された分類部品種類dをラベルとしてもつ決定木の頂点を作成したとき、dに分類される部品群をどのように分割し、その頂点から出す枝に割り振ればよいかを計算する部品分割計算装置である。
【００１５】
４は、部品分割計算装置３で算出された部品群の分割結果から頂点や枝を作成する頂点・枝作成装置である。
【００１６】
５は、頂点・枝作成装置で作成された決定木もしくは作成途中の決定木を出力する決定木出力装置である。
【００１７】
６は、第２の実施形態に係わり、直積集合すなわち
【数４】
0005175607.tif 000003
【００１８】
から識別子の集合Mへの部分写像すなわち
【数５】
0005175607.tif 000004
【００１９】
を入力する写像入力装置である。
【００２０】
７は、写像入力装置６で入力された部分写像fから写像入力装置２への入力となる部分写像gを作成する写像作成装置である。
【００２１】
８は、第３の実施形態に係わり、決定木を入力する決定木入力装置である。
【００２２】
９は、決定木入力装置８で入力された決定木から写像入力装置２への入力となる部分写像gを作成する写像作成装置である。
【００２３】
１０は、第４の実施形態に係わり、決定木を入力する決定木入力装置である。
【００２４】
１１は、第４の実施形態に係る決定木入力装置１０で入力された決定木の部分木を入力（指定）する部分木入力装置である。
【００２５】
１２は、部分木入力装置１１で入力された部分木を（別の部品種類分類順で）再構成するために必要な、写像入力装置２への入力となる部分写像 gを作成する写像作成装置である。
【００２６】
１３は、第５の実施形態に係わり、部品組み合わせ表を入力する入力装置である。
【００２７】
１４は、入力装置で入力された部品組み合わせ表から、写像作成装置への入力となる部分写像gを作成する写像作成装置である。
【００２８】
定義１．到達条件C
∀d∈Dについて、Parts(d)の部分集合Parts’ (d)（⊆Parts (d )）を定義したものである。D = {d1, ..., dn}とするとき、Cは直積集合Parts’ (d1)×…×Parts’ (dn)に含まれる部品組み合わせを表す。図２に到達条件の例を示す。ただし、部品種類はX, Y, Zの３つを仮定している。この到達条件はParts’ (X)×Parts’ (Y)×Parts’ (Z)で表される計12通りの部品組み合わせを定義している。
【００２９】
定義２．到達条件リストL
到達条件を要素としてもつリストである。リスト内の到達条件が示す部品組み合わせの和を表す。すなわち、要素数が１の到達条件リストは到達条件ともいえる。例えば、部品組み合わせ(x1×y1×z1)と部品組み合わせ(x2×y2×z2)を表す到達条件は記述できないので、和の形（到達条件のリスト）で表現する。部品組み合わせ(x1×y1×z1)に対する到達条件をR1、部品組み合わせ(x2×y2×z2)に対する到達条件をR2とすると、到達条件リストLはR1とR2を要素としてもつ（図３参照）。
【００３０】
本実施形態では、到達条件リストに対する下記の演算を利用している。
【００３１】
１．到達条件リストLの到達可能性判定（L =φ？）
２．到達条件リストL1と到達条件リストL2の共通到達条件リストLの計算（L = L1∩L2）
３．到達条件リストL1と到達条件リストL2の和到達条件リストLの計算（L = L1∪L2）
４．到達条件リストL1から到達条件リストL2を取り除いた到達条件リストLの計算(L=L1−L2)
５．到達条件C1と到達条件リストC2の包含関係の計算（C1⊇C2？）
まず、これらの演算の方法について説明する。L=L1−L2の演算方法に関してはその正しさの説明もおこなう。到達条件Cのもつ集合Parts ’(d)をC:Parts ’(d)と記述する。
【００３２】
１．到達可能性
１．１到達条件Cの到達可能性
到達条件Cの定義（定義1）から、Parts ’(d)＝φとなるd∈Dが存在するならば、Cに含まれる部品組み合わせは存在しないことになる。Cに含まれる部品組み合わせが存在しないとき、Cは到達不能であるといい、C =φと記述する。
【００３３】
１．２到達条件リストLの到達可能性
到達条件リストLに含まれる部品組み合わせが存在しないとき、Lは到達不能であるといい、L =φと記述する。到達条件リストの定義（定義2）からL = C1∪…∪Cpとするとき、∀Ci（1≦i≦p）について、Ci =φならばL =φとなる。
【００３４】
２．共通到達条件（リスト）の計算（積集合計算）
２．１到達条件C1とC2の共通到達条件Cの計算（C = C1∩C2）
∀d∈Dについて、C:Parts ’(d) = C1:Parts ’(d)∩C2:Parts ’ (d)とする。
【００３５】
２．２到達条件リストL1とL2の共通到達条件リストLの計算（L = L1∩L2）
【数６】
0005175607.tif 000005
【００３６】
を計算する。
【００３７】
３．到達条件リストL1とL2との和集合の計算（L = L1∪L2）
到達条件リストの定義（定義2）からL1とL2を連結すればよい。
【００３８】
４．到達条件（リスト）の差集合の計算
４．１到達条件C1からC2を取り除いた到達条件リストLの計算（L = C1−C2）
（場合１）C = C1∩C2 = φの場合
LはC1のみを要素としてもつリストとする。
【００３９】
（場合２）C = C1∩C2 ≠φの場合
∀d∈Dについて、到達条件Cdを以下のように作成し、Cdが到達可能ならばLに追加（連結）する。
【００４０】
（Cdの作成方法）
∀f∈Dについて、
d = fの場合、Cd: Parts ’(f) = C1: Parts ’(f)−C2: Parts ’(f)
（＝C1: Parts ’(f)−(C1: Parts ’(f)∩C2: Parts ’(f)) ）
d≠fの場合、Cd: Parts ’(f) = C1: Parts ’(f)
を計算する。
【００４１】
（例１）C1およびC2が図１１のように与えられている場合、L = C1−C2は図１２のようになる。
【００４２】
（例２）C3およびC4が図１３のように与えられている場合、L=C3−C4は図１４のようになる。
【００４３】
＜証明＞C1−C2 = Lの証明
（前提条件）∀d∈Dについて、C2:Parts ’(d) = C1: Parts ’(d)∩C2: Parts ’(d)とする。一般的にC2にはC1に含まれない部品が含まれているが、C1−C2の計算において、この前提条件をおいても一般性を失うことはない（C1に含まれない部品組み合わせがC2に含まれていても計算結果に影響しない）。
【００４４】
上記Lの作成方法より、L ＝ Cd1∪Cd2∪…∪Cdnとおくことができる（{d1,d2, ..., dn}=D）。
【００４５】
・C2∩L =φの証明（LにはC2に含まれる部品組み合わせが含まれていないことの証明）
∀d∈Dについて、Cd: Parts ’(d) =C1: Parts ’(d)−C2: Parts ’(d)となっているためC2∩Cd =φ。したがって、C2∩L=φである。
【００４６】
・C1 = L + C2の証明
一般的な到達条件C1およびC2として図１１を仮定すると、L（=R1−R2）は図１２のように作成される。Lに含まれる部品組み合わせは定義２から、
{Xa×(Ya∪Yb)×…×(Za∪Zb)} ∪ {(Xa∪Xb)×Ya×…×(Za∪Zb)} ∪ … ∪
{( Xa∪Xb)×(Ya∪Yb)×…×Za}  …（式１）
で表すことができる。式１にはXb×Yb×…×Zbに含まれる部品組み合わせを除く全部品組み合わせが含まれる（添え字がbの部品集合の積集合を除く部品組み合わせが含まれる）。一方、C2に含まれる部品組み合わせは定義１から、
Xb×Yb×…×Zb  …（式２）
で表すことができる。したがって、(式１)∪(式２)には全部品組み合わせが含まれることになり、
(式１)∪(式２) = (X1∪X2)×(Y1∪Y2)×…×(Z1∪Z2) …（式３）
となる。式３の表す部品組み合わせはC1の表す部品組み合わせに一致する。
【００４７】
４．２到達条件リストL1からL2を取り除いた到達条件リストLの計算（L = L1−L2）
L1 = CL11∪…∪CL1p、L2 = CL21∪…∪CL2qとすると、
【数７】
0005175607.tif 000006
【００４８】
である。
【００４９】
５．到達条件の包含関係判定（C2⊇C1？）
∀d∈Dについて、C2: Parts ’(d)⊇C1: Parts ’(d)ならばTrueとし、それ以外の場合Falseとする。
【００５０】
到達条件リストに関する様々な演算を行った結果得られる到達条件リストの要素（到達条件）には不必要なものが含まれてしまう可能性がある。例えば、図１５の到達条件リストL1（= C1∪C2）では、C2⊇C1となっているため、C1はL1に加える必要がない。
【００５１】
そこで、L = C1∪…∪Cnとするとき、∀i, j∈{1,..., n}（i≠j）について、Ci⊇Cjならば、CjをLから削除する手続きを到達条件リストに関する演算を行った後に実行する。この縮約処理は必ずしも要素数が最少の到達条件リストを作成するものではないが、決定木の作成に必要なメモリ領域および計算時間の削減に大きく貢献することが実験的に分かっている。図１６の到達条件リストL2は上記の縮約方法では縮約されない例である（L2=L2’=L2’’）。
【００５２】
第１の実施形態（図１の部品分別計算装置３および頂点・枝作成装置４：決定木作成装置）
図４の部分写像 g: L→Mに対応する決定木を作成するには以下の手順で実現できる。
【００５３】
処理１：同じ識別子に対応する到達条件リスト同士を連結する。すなわち、識別子毎の到達条件リストを作成する。以後、識別子mに対する到達条件リストをLmと記述する。この処理により、図２３のような到達条件リストが作成される。
【００５４】
処理２：入力された分類部品種類をラベルとする頂点を作成し、その頂点に対する到達条件を設定する。以後、頂点nに対する到達条件をCnと記述する。到達条件Cnは頂点nに到達するための部品組み合わせに一致する。すなわち、作成した頂点が根頂点の場合（図９（左））、到達条件 は全ての部品組み合わせが到達可能な条件となり、作成した頂点が根頂点以外の場合（図９（右）頂点2）、到達条件は親頂点の到達条件を枝に付けられた部品集合によりさらに限定したものとなる。例えば、図９（右）頂点１の到達条件C1が、図２４のようであれば、頂点２の到達条件C2は、図２５に示すとおりとなる。
【００５５】
処理３：処理１で設定された識別子毎の到達条件リストLm、および、処理２で作成された頂点nの到達条件Cnを用いて、頂点nのラベルとなっている部品種類に属する部品の集合をどのように枝のラベルに割り振るかを算出する。ただし、説明では、作成した頂点nのラベルとなっている部品種類をXと仮定する。識別子の集合をMとする。
【００５６】
（処理３の詳細）
処理３．１：∀m∈Mについて、共通到達条件リストLm’ = Lm∩Cnを計算する。
【００５７】
（場合１）Lm’≠φとなる識別子mが１つの場合には、部品集合を分割せずとも識別子が一意に決まるので、頂点nを対応する識別子をラベルとする葉頂点に置き換えて処理終了する。
【００５８】
（場合２）Lm’≠φとなる識別子が２つ以上存在する場合には図２６に示すように∀c∈Parts(X)について、ダミーの到達条件Cc’を作成したのち、処理３．２に進む。
【００５９】
処理３．２：∀m∈Mについて、Lm’とCc’の共通到達条件リストLm,c = Lm’∩Cc’を計算する。図４の写像を最初に部品種類Xで分類する場合（決定木の根頂点のラベルがX）、図２７のような共通到達条件リストが得られる。
【００６０】
Lm,cは、頂点nを部品cで分類することによって、識別子がどのように分別されるかを知るための情報として処理３．３で利用する。
【００６１】
処理３．３：∀c1, c2∈Parts(X)（c1≠c2）について、c1とc2を分割する必要があるかどうかを判定する（逆にいうと、一つの枝にラベルとして付けることができるかどうかを判定する）。c1とc2を分割する必要がある場合、仮にc1とc2を決定木の一つの枝のラベルとして付けると、最終的に決定木の葉として識別子が分別しきれなくなる。c1とc2を分割する必要があるかどうかの判定方法を処理３．３．１に示す。
【００６２】
処理３．３．１：∀m1,m2∈M（m1≠m2）について、c1=c2という仮定おいた場合に次式４がTrueとなるm1,m2が存在するかどうかを判定する。
【００６３】
(Lm1,c1∪Lm1,c2)∩(Lm2,c1∪Lm2,c2)≠φ…式４
式４がTrueとなるm1,m2が存在する場合、c1=c2の仮定の下で、（式４の左辺）＝(Lm1,c1∪Lm1,c2)∩(Lm2,c1∪Lm2,c2)に含まれる部品組み合わせについて、識別子m1とm2が分別できないことを意味する。すなわち、c1とc2は分割する必要があることになる。一方、式４がTrueとなるm1,m2が存在しない場合、c1とc2は分割しなくても、全ての識別子が最終的に分別できることになる。
【００６４】
処理３．４：処理３．３において、∀c1, c2∈Parts(X)（c1≠c2）について、c1とc2が分割不要という結果となる場合、そもそも部品種類Xで分類する意味がないことになる。従って、処理2で作成した部品種類Xがラベルとなっている頂点を削除し、次に分類する部品種類をラベルとしてもつ頂点に置き換える（処理２へ戻る）。次に分類する部品種類がない場合、部品種類Xがラベルとなっている頂点を削除しておく（処理４で葉頂点が作成される）。
【００６５】
図４の写像を最初に部品種類Xで分類する（決定木の根頂点のラベルをXとする）場合、「x1とx2」「x2とx3」は分割する必要があり、「x1とx3」は分割する必要がないという結果が得られる。すなわち、図１０のような根頂点とラベルの付けられた枝が作成される。根頂点以外の頂点の作成に関しても、入力される分類する部品種類を利用し、処理２以降を繰り返し適用すれば作成できる。全ての部品種類が入力され処理３が終了した時点で葉頂点を除く決定木が作成されていることになる。
【００６６】
処理４：葉頂点を作成し、その葉頂点に対して到達条件を設定し（処理２をおこなう）、その到達条件に含まれる部品組み合わせに対応する識別子をラベルとして付ける（必ず単一の識別子に対応する）。決定木の全ての葉（ラベルに識別子が付けられた頂点）が作成された時点で決定木が完成する。
【００６７】
第２の実施形態（図１の到達条件リストから識別子への写像作成装置７）
部分写像すなわち
【数８】
0005175607.tif 000007
【００６８】
から図１の写像入力装置２への入力となる到達条件リストから識別子への写像を作成する方法は次mの通りである。
【数９】
0005175607.tif 000008
【００６９】
が対応する識別子をmp（∈M）とおく。∀pについて、pを表す到達条件とmpとが対応する部分写像g: L→Mを作成する。
【００７０】
第３の実施形態（図１の到達条件リストから識別子への写像作成装置９）
決定木から図１の写像作成装置２への入力となる到達条件リストから識別子への写像を作成する方法は以下の通りである。
【００７１】
処理１：入力された決定木の全ての頂点を探索し、分類する部品種類の一覧を作成する（処理２の到達条件設定で利用）。
【００７２】
処理２：入力された決定木の全ての葉頂点に対し到達条件を設定する。到達条件の設定方法は、第１の実施形態における処理２と同様に、根頂点の到達条件を最初に設定し、以後、子頂点の到達条件を親頂点の到達条件と枝のラベルをもとに計算していく。
【００７３】
処理３：入力された決定木の葉頂点の集合をQとし、q∈Qに設定されている到達条件をCqとおく。∀qについて、Cqとqのラベルが対応する部分写像g: L→Mを作成する。
【００７４】
第３の実施形態を利用すると、ある部品種類分類順で分類された決定木を別の部品種類分類順で分類された決定木に変換することが可能になる。
【００７５】
第４の実施形態（図１の到達条件リストから識別子への写像作成装置１２）
決定木およびその決定木の部分木から図１の写像作成装置への入力となる到達条件リストから識別子への写像を作成する方法は以下の通りである。ここでは、入力された部分木の分類順を変更した部分木を作成することが目的であるので、全ての部品組み合わせに対する識別子を定義した部分写像を作成する必要はない。
【００７６】
処理１：入力された決定木の全ての頂点を探索し、分類する部品種類の一覧を作成する（処理２の到達条件設定で利用する。
【００７７】
処理２：部分木の葉の到達条件を設定する。設定方法は第３の実施形態の処理２と同様。
【００７８】
処理３：入力された部分木の葉頂点の集合をQとし、q∈Qに設定されている到達条件をCqとおく。∀qについて、Cqとqのラベルが対応する部分写像g: L→Mを作成する。
【００７９】
ここで作られる部分写像は全ての部品組み合わせに対する識別子が定義されているわけではないが、部分木を再構成するには十分な情報となっている。
【００８０】
第４の実施形態を利用すると、決定木の一部分（部分木）の部品種類分類順を変更した決定木を作成することができる。
【００８１】
第５の実施形態（図１の到達条件リストから識別子への写像作成装置１４）
ここでは、図８の部品組み合わせ表に対する処理を例にしながら、図１の写像作成装置への入力となる到達条件リストから識別子への写像を作成する方法を説明する。ただし、Parts (X) = { x1, x2, x3 }, Parts (Y) = { y1, y2 }, Parts (Z) = { z1, z2 }とする。また、部品組み合わせ表に含まれるルールの集合をR（={r1, r2, r3, r4}）とおく。
【００８２】
処理１：∀r∈Rに対して、rが適用される部品組み合わせを表す到達条件リストLrを設定する。
【００８３】
（処理１の詳細）
処理１．１：∀r∈Rを優先度の高い順にソートする。図８の例の場合、ルール１→ルール２→ルール３→ルール４の順にソートされる。
【００８４】
処理１．２以降は、ソートされた順番通りに∀r∈Rに対して実行する。
【００８５】
処理１．２：rの到達条件Crを設定する。例えば、ルール１に対する到達条件Cr1は、図２８の通りとなる。
【００８６】
ALLは部品種類がもつ全部品と解釈する。例えば、ルール４に対する到達条件Cr4は、図２９のとおりとなる。
【００８７】
尚、一般的に、ここで設定される到達条件Crは、ルールrが適用される部品組み合わせとは一致していない（より優先度の高いルールで一部の部品組み合わせが定義されている可能性がある）。
【００８８】
処理１．３：rより前に到達条件リストを設定したルールの到達条件リストをLr1, Lr2,... とするとき、rの到達条件リストLrは、Lr = Cr−Lr1−Lr2−… となる（到達条件リストは再帰的に計算される）。
【００８９】
処理１により、図８の各ルールに設定される到達条件リストは図３０のようになる。
【００９０】
処理２：部品組み合わせ表のルールrに対応する識別子をmrとする。処理１で作成されて全てのLrとmrが対応する部分写像g: L→Mを作成する。
【００９１】
実際に図１７の部品組み合わせ表を図１の入力装置１３へ入力すると、図１８の部分写像g: L→Mが得られる。図１８の部分写像g: L→MとID3アルゴリズムにより分類部品種類を図１の入力装置１へ入力すると図１９の決定木が得られる。ID3アルゴリズムは、決定木の頂点数が最少になる部品種類分類順を計算するために利用できるヒューリスティックである。
【００９２】
次に図１９の決定木を図１の決定木入力装置８へ入力すると図１８の部分写像g: L→Mが得られる。図１８の部分写像g: L→Mと、部品種類分類順を「CPU→筐体色→ハードディスク」となるように図１の2および図１の入力装置１へ入力すると図２０の決定木が得られる。
【００９３】
図２０の決定木を図１の決定木入力装置８へ入力したときに得られる部分写像g: L→Mは図２１のようになり、図１８の部分写像g: L→Mとは表現が異なるが内容は同じである。例えば図２０の決定木を次の入力とする場合、図１８の部分写像g: L→Mのように過去に作成された写像が存在すれば、それを使い回すことが可能である。
【００９４】
図２０の決定木と図２０の決定木の「筐体色」を根ノードとする左側部分木を図１の決定木入力装置１０および図１の部分木入力装置１１へ入力すると、図２１の上４つの到達条件リストと識別子への対応関係を表す部分写像g: L→Mが作成される。この部分写像g: L→Mと、部品種類分類順を「ハードディスク→筐体色」となるように図１の写像作成装置および図１の入力装置１へ入力すると図２２の部分木の構成が変更された決定木が得られる。
【００９５】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００９６】
【図１】本発明の実施形態に係る決定木作成装置を示すブロック図
【図２】到達条件の表現例を示す図
【図３】到達条件リストの表現例を示す図
【図４】第１の実施形態に係る決定木作成装置へ入力される写像の例を示す図
【図５】作成途中の決定木の例を示す図
【図６】完成した決定木の例を示す図
【図７】分類する部品種類の指定を示す図
【図８】部品組み合わせ表の例を示す図
【図９】実施形態説明用の図（頂点の到達条件計算）
【図１０】実施形態説明用の図（部品種類Ｘで部品を分類した直後の作成途中の決定木）
【図１１】実施形態説明用の図（到達条件例）
【図１２】実施形態説明用の図（図１１の到達条件の差演算結果を表す到達条件リスト）
【図１３】実施形態説明用の図（到達条件例）
【図１４】実施形態説明用の図（図１３の到達条件の差演算結果を表す到達条件リスト）
【図１５】実施形態説明用の図（縮約可能な到達条件リスト）
【図１６】実施形態説明用の図（縮約されない到達条件リスト）
【図１７】実施形態説明用の図（入力する部品組み合わせ表）
【図１８】実施形態説明用の図（図１７の部品組み合わせ表から作成される部分写像）
【図１９】実施形態説明用の図（出力される決定木（ID3アルゴリズムによる分類順入力））
【図２０】実施形態説明用の図（分類順を指定した場合に出力される決定木）
【図２１】実施形態説明用の図（図２０の決定木から作成される部分写像）
【図２２】実施形態説明用の図（部分木の分類順を指定した場合に出力される決定木）
【図２３】実施形態説明用の図
【図２４】実施形態説明用の図
【図２５】実施形態説明用の図
【図２６】実施形態説明用の図
【図２７】実施形態説明用の図
【図２８】実施形態説明用の図
【図２９】実施形態説明用の図
【図３０】実施形態説明用の図
【符号の説明】
【００９７】
１…分類部品種類入力装置；
２…到達条件リストから識別子への写像入力装置；
３…部品分割計算装置；
４…頂点・枝作成装置；
５…決定木出力装置
【図１】
0005175607.tif 000011
【図２】
0005175607.tif 000012
【図３】
0005175607.tif 000013
【図４】
0005175607.tif 000014
【図５】
0005175607.tif 000015
【図６】
0005175607.tif 000016
【図７】
0005175607.tif 000017
【図８】
0005175607.tif 000018
【図９】
0005175607.tif 000019
【図１０】
0005175607.tif 000020
【図１１】
0005175607.tif 000021
【図１２】
0005175607.tif 000022
【図１３】
0005175607.tif 000023
【図１４】
0005175607.tif 000024
【図１５】
0005175607.tif 000025
【図１６】
0005175607.tif 000026
【図１７】
0005175607.tif 000027
【図１８】
0005175607.tif 000028
【図１９】
0005175607.tif 000029
【図２０】
0005175607.tif 000030
【図２１】
0005175607.tif 000031
【図２２】
0005175607.tif 000032
【図２３】
0005175607.tif 000033
【図２４】
0005175607.tif 000034
【図２５】
0005175607.tif 000035
【図２６】
0005175607.tif 000036
【図２７】
0005175607.tif 000037
【図２８】
0005175607.tif 000038
【図２９】
0005175607.tif 000039
【図３０】
0005175607.tif 000040