(57)【要約】特徴パターン出力装置（２１）内部の類似データ抽出部（３２）は、入力データ処理部（３１）から受信した入力データに類似する類似データをデータベース（２２）から抽出し、二値化処理部（３３）よって二値化し、類似パターン集合算出部（３４）および入力データ分類処理部（３６）に送信する。類似パターン集合算出部（３４）は、二値化された類似データをもとに、クラスＰクラスＮのそれぞれについて最大パターン集合と最小パターン集合とを算出する。特徴パターン集合算出部（３５）は、最大パターン集合と最小パターン集合からクラスＰとクラスＮにそれぞれ特徴的に出現するアイテムの組合せを特徴パターンとして出力する。また、二値化された類似データと特徴パターンとを比較し、入力データをクラスＰに分類するかクラスＮに分類するかを決定する。
2004040477.tif 000002
【特許請求の範囲】
【請求項１】
複数のアイテムからなるデータを複数のクラスにそれぞれ区分して記憶したデータベースを有し、各クラスの特徴をなすアイテムの組合せを当該クラスの特徴パターンとして出力する特徴パターン出力装置であって、
入力データを受け付けた際に、該入力データに類似する類似データを前記データベースから各クラスごとに抽出する類似データ抽出手段と、
前記類似データ抽出手段により抽出された類似データから各クラスごとの類似パターン集合を算出する類似パターン集合算出手段と、
前記類似パターン集合算出手段により算出された類似パターン集合から各クラスごとの特徴パターンを算出する特徴パターン算出手段と、
を備えたことを特徴とする特徴パターン出力装置。
【請求項２】
前記類似パターン集合算出手段は、前記類似データ抽出手段により抽出された類似データを形成する各アイテムの値と、前記入力データを形成する各アイテムの値とが一致したアイテムの組合せをパターン集合として抽出し、前記パターン集合に自身以外の部分集合が存在しないアイテムの組合せである最小パターンを最小パターン集合として抽出し、前記パターン集合に自身以外の上位集合が存在しないアイテムの組合せである最大パターンを最大パターン集合として抽出し、前記最小パターン集合と前記最大パターン集合とを前記類似パターン集合として出力することを特徴とする請求の範囲第１項に記載の特徴パターン出力装置。
【請求項３】
前記特徴パターン算出手段は、複数のクラスにまたがって出現する共通パターン集合を前記最小パターン集合から抽出し、前記特徴パターン算出手段は、前記共通パターン集合が有するアイテムを全て有する特徴パターンを算出することを特徴とする請求の範囲第２項に記載の特徴パターン出力装置。
【請求項４】
前記類似データ抽出手段は、前記データベースから類似データを抽出する際に、クラスごとに異なる条件に基づいて類似データの抽出をおこなうことを特徴とする請求の範囲第２項に記載の特徴パターン出力装置。
【請求項５】
前記類似パターン集合算出手段は、複数のクラスにまたがって出現する最大パターンが存在する場合に当該最大パターンから所定のアイテムを除外することを特徴とする請求の範囲第４項に記載の特徴パターン出力装置。
【請求項６】
前記特徴パターン算出手段が算出した特徴パターンをもとに、前記入力データを前記複数のクラスのいずれかに分類する分類手段をさらに備えたことを特徴とする請求の範囲第１項〜第５項のいずれか一つに記載の特徴パターン出力装置。
【請求項７】
前記分類手段は、各クラスの類似データにおける前記特徴パターンの数を計数し、該計数結果がもっとも大きい値となるクラスに前記入力データを分類することを特徴とする請求の範囲第６項に記載の特徴パターン出力装置。
【請求項８】
前記類似パターン集合算出手段は、前記入力データを形成する所定のアイテムの値と前記類似データを形成するアイテムの値とが所定の数値範囲内にある場合には、両者のアイテムの値が一致したものと判定することを特徴とする請求の範囲第２項〜第７項のいずれか一つに記載の特徴パターン出力装置。
【請求項９】
複数のアイテムからなるデータを複数のクラスにそれぞれ区分して記憶したデータベースから各クラスの特徴をなすアイテムの組合せを当該クラスの特徴パターンとして出力する特徴パターン出力方法であって、
入力データを受け付けた際に、該入力データに類似する類似データを前記データベースから各クラスごとに抽出する類似データ抽出工程と、
前記類似データ抽出工程により抽出された類似データから各クラスごとの類似パターン集合を算出する類似パターン集合算出工程と、
前記類似パターン集合算出工程により算出された類似パターン集合から各クラスごとの特徴パターンを算出する特徴パターン算出工程と、
を含むことを特徴とする特徴パターン出力方法。
【請求項１０】
前記類似パターン集合算出工程は、前記類似データ抽出工程により抽出された類似データを形成する各アイテムの値と、前記入力データを形成する各アイテムの値とが一致したアイテムの組合せをパターン集合として抽出し、前記パターン集合に自身以外の部分集合が存在しないアイテムの組合せである最小パターンを最小パターン集合として抽出し、前記パターン集合に自身以外の上位集合が存在しないアイテムの組合せである最大パターンを最大パターン集合として抽出し、前記最小パターン集合と前記最大パターン集合とを前記類似パターン集合として出力することを特徴とする請求の範囲第９項に記載の特徴パターン出力方法。
【請求項１１】
前記特徴パターン算出工程は、複数のクラスにまたがって出現する共通パターン集合を前記最小パターン集合から抽出し、前記特徴パターン算出工程は、前記共通パターン集合が有するアイテムを全て有する特徴パターンを算出することを特徴とする請求の範囲第１０項に記載の特徴パターン出力方法。
【請求項１２】
前記類似データ抽出工程は、前記データベースから類似データを抽出する際に、クラスごとに異なる条件に基づいて類似データの抽出をおこなうことを特徴とする請求の範囲第１０項に記載の特徴パターン出力方法。
【請求項１３】
前記類似パターン集合算出工程は、複数のクラスにまたがって出現する最大パターンが存在する場合に当該最大パターンから所定のアイテムを除外することを特徴とする請求の範囲第１２項に記載の特徴パターン出力方法。
【請求項１４】
前記特徴パターン算出工程が算出した特徴パターンをもとに、前記入力データを前記複数のクラスのいずれかに分類する分類工程をさらに含むことを特徴とする請求の範囲第９項〜第１３項のいずれか一つに記載の特徴パターン出力方法。
【請求項１５】
前記分類工程は、各クラスの類似データにおける前記特徴パターンの数を計数し、該計数結果がもっとも大きい値となるクラスに前記入力データを分類することを特徴とする請求の範囲第１４項に記載の特徴パターン出力方法。
【請求項１６】
前記類似パターン集合算出工程は、前記入力データを形成する所定のアイテムの値と前記類似データを形成するアイテムの値とが所定の数値範囲内にある場合には、両者のアイテムの値が一致したものと判定することを特徴とする請求の範囲第９項〜第１５項のいずれか一つに記載の特徴パターン出力方法。
【請求項１７】
複数のアイテムからなるデータを複数のクラスにそれぞれ区分して記憶したデータベースから各クラスの特徴をなすアイテムの組合せを当該クラスの特徴パターンとして出力する特徴パターン出力プログラムであって、
入力データを受け付けた際に、該入力データに類似する類似データを前記データベースから各クラスごとに抽出する類似データ抽出工程と、
前記類似データ抽出工程により抽出された類似データから各クラスごとの類似パターン集合を算出する類似パターン集合算出工程と、
前記類似パターン集合算出工程により算出された類似パターン集合から各クラスごとの特徴パターンを算出する特徴パターン算出工程と、
をコンピュータに実行させることを特徴とする特徴パターン出力プログラム。
【請求項１８】
前記類似パターン集合算出工程は、前記類似データ抽出工程により抽出された類似データを形成する各アイテムの値と、前記入力データを形成する各アイテムの値とが一致したアイテムの組合せをパターン集合として抽出し、前記パターン集合に自身以外の部分集合が存在しないアイテムの組合せである最小パターンを最小パターン集合として抽出し、前記パターン集合に自身以外の上位集合が存在しないアイテムの組合せである最大パターンを最大パターン集合として抽出し、前記最小パターン集合と前記最大パターン集合とを前記類似パターン集合として出力することを特徴とする請求の範囲第１７項に記載の特徴パターン出力プログラム。
【請求項１９】
前記特徴パターン算出工程は、複数のクラスにまたがって出現する共通パターン集合を前記最小パターン集合から抽出し、前記特徴パターン算出工程は、前記共通パターン集合が有するアイテムを全て有する特徴パターンを算出することを特徴とする請求の範囲第１８項に記載の特徴パターン出力プログラム。
【請求項２０】
前記類似データ抽出工程は、前記データベースから類似データを抽出する際に、クラスごとに異なる条件に基づいて類似データの抽出をおこなうことを特徴とする請求の範囲第１８項に記載の特徴パターン出力プログラム。
【請求項２１】
前記類似パターン集合算出工程は、複数のクラスにまたがって出現する最大パターンが存在する場合に当該最大パターンから所定のアイテムを除外することを特徴とする請求の範囲第２０項に記載の特徴パターン出力プログラム。
【請求項２２】
前記特徴パターン算出工程が算出した特徴パターンをもとに、前記入力データを前記複数のクラスのいずれかに分類する分類工程をさらにコンピュータに実行させることを特徴とする請求の範囲第９項〜第２１項のいずれか一つに記載の特徴パターン出力プログラム。
【請求項２３】
前記分類工程は、各クラスの類似データにおける前記特徴パターンの数を計数し、該計数結果がもっとも大きい値となるクラスに前記入力データを分類することを特徴とする請求の範囲第２２項に記載の特徴パターン出力プログラム。
【請求項２４】
前記類似パターン集合算出工程は、前記入力データを形成する所定のアイテムの値と前記類似データを形成するアイテムの値とが所定の数値範囲内にある場合には、両者のアイテムの値が一致したものと判定することを特徴とする請求の範囲第１７項〜第２３項のいずれか一つに記載の特徴パターン出力プログラム。
【発明の詳細な説明】
【技術分野】  この発明は、複数のアイテムを有するデータを複数のクラスのいずれかに区分して記憶するデータベースから、前記クラスに特徴的に含まれるアイテムの組合せを当該クラスの特徴パターンとして出力する特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムに関し、特にデータベースが大規模であっても高速に特徴パターンを出力可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムに関する。
【背景技術】  近年、データベースに記憶したデータについて、データ間の相関関係や、データが有するルールを抽出する手法が考案されている。データ間の相関関係やデータが有するルールは、データベースに記憶されたデータを分類する場合や、新規のデータを分類する場合などに用いることができる。
従来、データベースからルールを取り出してデータベースにフィードバックする相関ルール学習の手法として、Ａｇｒａｗｅｌ，Ｒ．，“Ｆａｓｔ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｍｉｎｉｎｇ  Ａｓｓｏｃｉａｔｉｏｎ  Ｒｕｌｅｓ”およびこれに対応する特許文献として「大規模データベース内の順次パターンをマイニングするためのシステムおよび方法」（特開平８−２６３３４６号公報）が公開されている。
ここに公開された手法によれば、アイテムと呼ばれるデータの構成要素を組み合わせてパターンを形成し、データの相関ルールを頻出するパターンによって示している。
しかしながらこの手法では、相関ルールの抽出に要するコストが高く、データベースの内容に変更があった場合に、その変更に対応して相関ルールの内容を行使するまでに時間が必要であった。そのため、相関ルールの抽出はデータベースをオフラインにして実行される場合が多く、データベースの更新に対して追従性が劣化するという問題点があった。
さらに、相関ルールの抽出や、抽出した相関ルールをもとにデータを分類するために必要な処理時間は、パラメータの設定によって大きく異なり、また、得られる相関ルール自体もパラメータに大きく依存するという問題があった。すなわち、パラメータの設定を適切におこなうためには、専門知識や経験が必要であり、パラメータの設定によっては得られたルールの有用性の低下を引き起こしたり、相関ルールの運用が不可能になるほどの処理時間が必要となる可能性があった。
一方、ルールの抽出手法としては、他にもＪ．Ｌｉ，Ｇ．Ｄｏｎｇ，Ｋ．Ｒａｍａｍｏｈａｎａｒａｏ，ａｎｄ  Ｌ．Ｗｏｎｇ．ＤｅＥＰｓ：Ａ  ｎｅｗ  ｉｎｓｔａｎｃｅ−ｂａｓｅｄ  ｄｉｓｃｏｖｅｒｙ  ａｎｄ  ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ｓｙｓｔｅｍ．Ｔｅｃｈｎｉｃａｌ  ｒｅｐｏｒｔ，Ｄｅｐｔ  ｏｆ  ＣＳＳＥ，Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｍｅｌｂｏｕｒｎｅ，２０００が公開されている。ここで公開されているＤｅＥＰｓは、入力データが与えられてから、適用可能なパターンを学習するリアルタイムなパターンの発見が可能である。したがって、データベースをオフラインにすることなく、任意のタイミングで更新することができる。また、ＤｅＥＰｓでは、パターン発見にパラメータを設定する必要がないため、運用時に要求される専門知識や経験が少ない。
しかしながら、ＤｅＥＰｓは、パターン発見時にデータベースの全てのデータを処理の対象とするため、データベースが有するデータ数に応じて必要な処理能力が大きくなる。したがって、データベースのデータ数が大きい場合、パターン抽出処理にリアルタイム処理におけるレスポンス時間としては許容できない時間が必要になるという問題点があった。
さらに、ＤｅＥＰｓでは、データの構成要素であるアイテムの数に比例して処理時間が要求される。したがって、それぞれのデータに含まれるアイテムの数が多い場合、パターン抽出処理に膨大な時間が必要になるという問題点があった。
この発明は、上述した従来技術による問題点を解消するためになされたものであり、データベースに含まれるデータ数が多く、またデータが多数のアイテムを有する大規模なデータベースにおいてもパターン抽出を高速に実行可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することを目的とする。
【発明の開示】
上述した課題を解決し、目的を達成するため、本発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、複数のアイテムからなるデータを複数のクラスにそれぞれ区分して記憶したデータベースから各クラスの特徴をなすアイテムの組合せを当該クラスの特徴パターンとして出力する特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムであって、入力データを受け付けた際に、該入力データに類似する類似データを前記データベースから各クラスごとに抽出する類似データ抽出手段と、前記類似データ抽出手段により抽出された類似データから各クラスごとの類似パターン集合を算出する類似パターン集合算出手段と、前記類似パターン集合算出手段により算出された類似パターン集合から各クラスごとの特徴パターンを算出する特徴パターン算出手段と、を備えたことを特徴とする。
この発明によれば、入力データに類似する類似データをデータベースから抽出し、抽出した類似データから各クラスの特徴をなす特徴パターンを算出する。
また、本発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、前記類似パターン集合算出手段は、前記類似データ抽出手段により抽出された類似データを形成する各アイテムと、前記入力データを形成する各アイテムとが一致したアイテムの組合せをパターン集合として抽出し、前記パターン集合に自身以外の部分集合が存在しないアイテムの組合せである最小パターンを最小パターン集合として抽出し、前記パターン集合に自身以外の上位集合（スーパーセット）が存在しないアイテムの組合せである最大パターンを最大パターン集合として抽出し、前記最小パターン集合と前記最大パターン集合とを前記類似パターン集合として出力することを特徴とする。
この発明によれば、データベースから抽出した抽出データの各アイテムと入力データの各アイテムとを比較し、一致するアイテムの組合せから最大パターン集合と最小パターン集合とを抽出し、この最大パターン集合と最小パターン集合とをもとに特徴パターンを算出するようにしている。
また、本発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、前記特徴パターン算出手段は、複数のクラスにまたがって出現する共通パターン集合を前記最小パターン集合から抽出し、前記特徴パターン算出手段は、前記共通パターン集合が有するアイテムを全て有する特徴パターンを算出することを特徴とする。
この発明によれば、最小パターン集合をもとに複数のクラスにまたがって出現する共通パターンを求め、特徴パターンを共通パターンの上位集合として算出している。
また、本発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、前記類似データ抽出手段は、前記データベースから類似データを抽出する際に、クラスごとに異なる条件に基づいて類似データの抽出をおこなうことを特徴とする。
この発明によれば、類似データを抽出する場合に、クラスごとに条件を変更し、各クラスについて十分な数の類似データを取得するようにしている。
また、本発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、前記類似パターン集合算出手段は、複数のクラスにまたがって出現する最大パターンが存在する場合に当該最大パターンから所定のアイテムを除外することを特徴とする。
この発明によれば、複数のクラスにまたがって出現する最大パターンについて、そのアイテムを除去することで特徴パターンが存在しなくなるという状況が発生することを防止している。
また、本発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、前記特徴パターン算出手段が算出した特徴パターンをもとに、前記入力データを前記複数のクラスのいずれかに分類する分類手段をさらに備えたことを特徴とする。
この発明によれば、類似データから算出した特徴パターンをもとに入力データを分類している。
また、本発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、前記分類手段は、各クラスの類似データにおける前記特徴パターンの数を計数し、該計数結果がもっとも大きい値となるクラスに前記入力データを分類することを特徴とする。
この発明によれば、各クラスの類似データにおける特徴パターンの出現数を計数し、この計数結果がもっとも大きい値となったクラスに入力データを分類している。
また、本発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、前記類似パターン集合算出手段は、前記入力データを形成する所定のアイテムの値と前記類似データを形成するアイテムの値とが所定の数値範囲内にある場合には、両者のアイテムの値が一致したものと判定することを特徴とする。
この発明によれば、アイテムが数値データである場合に所定の数値範囲を設定し、入力データのアイテムの値と類似データのアイテムの値とが所定の範囲内にある場合に両者のアイテムの値が一致したと判定する。
【図面の簡単な説明】  第１図は、本発明の実施の形態１である特徴パターン出力装置の概要構成を説明する概要構成図でり、第２図は、入力データと類似データの具体例を示す図であり、第３図は、データ群を類似度に従って配したデータ空間を示す図であり、第４図は最大パターン集合と最小パターン集合とを示す図であり、第５図は、特徴パターン集合算出部の処理動作を示す図であり、第６図は、入力データ分類処理部３６の処理動作を説明するフローチャートであり、第７図は、属性ノイズを除去する統計的検定処理を説明する図であり、第８図は、実施の形態２におけるデータと類似度の関係を示す図であり、第９図は、実施の形態２における最大パターン集合と最小パターン集合とを示す図であり、第１０図は、本実施の形態３におけるコンピュータシステムを説明するための説明図であり、第１１図は、第１０図に示した本体部の構成を説明する説明図である。
【発明を実施するための最良の形態】  以下に添付図面を参照して、この発明に係る特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムの好適な実施の形態を詳細に説明する。
（実施の形態１）
第１図は、本発明の実施の形態１である特徴パターン出力装置の概要構成を説明する概要構成図である。第１図において、特徴パターン出力装置２１は、データベース２２に接続されている。データベース２２は、顧客に関する情報を記憶しており、一つのデータが顧客一人に対応する。また、データには、「年齢」、「住居」、「性別」、「結婚」などの項目がある。各データは、それぞれ項目について値を有する。以下、データが有する項目と項目の値との組合せをアイテムと称する。データベース２２は、各顧客、すなわち各データを与信の可否によってクラス分けしている。データベース２２は、「与信可能」の顧客を「クラスＰ」、「与信不可」の顧客を「クラスＮ」として分類している。
特徴パターン出力装置２１は、その内部に入力処理部３１、類似データ抽出部３２、二値化処理部３３、類似パターン集合算出部３４、特徴パターン集合算出部３５および入力データ分類処理部３６を有している。入力処理部３１は、顧客の情報を入力データとして受信した場合に、この入力データを類似データ抽出部３２と、二値化処理部３３に出力する。
類似データ抽出部３２は、入力データに類似したデータをデータベース２２から抽出し、類似データとして二値化処理部３３に出力する。二値化処理部は、入力データをもとにして類似データを二値化した後、類似パターン集合算出部３４および入力データ分類処理部３６に送信する。
類似パターン集合算出部３４は、二値化された類似データをもとに、クラスＰクラスＮのそれぞれについて類似パターン集合を算出する。特徴パターン集合算出部３５は、類似パターン集合からクラスＰとクラスＮにそれぞれ特徴的に出現するアイテムの組合せを特徴パターンとして出力する。
さらに、入力データ分類処理部３６は二値化された類似データと特徴パターンとを比較し、入力データをクラスＰに分類するかクラスＮに分類するかを決定する。
特徴パターン出力装置２１は、この特徴パターンと、入力データの分類結果とを出力する。すなわち、この特徴パターン出力装置２１は、入力データに類似するデータをデータベース２２から抽出し、この類似データから特徴パターンを算出するので、データベース２２のデータ数や各データのアイテム数に依存することなく、高速に特徴パターンの算出をおこなうことができる。
つぎに、各処理について具体例を用いて詳細に説明する。
第２図に、入力データと類似データの具体例を示す。第２図（ａ）は、入力データの一例であり、第２図（ｂ）は、データベース２２が記憶するデータの一例である。第２図に示すように、入力データは、「年齢」の値として「３５」、「住居」の値として「借家」、「性別」の値として「男性」、「結婚」の値として「既婚」を有している。
類似データ抽出部３２は、類似度関数としてＣｉｔｙ−ｂｌｏｃｋ距離を用いた類似度を採用し、データベース２２から類似データの抽出をおこなう。
具体的には、
ｎをアイテムの数、Ｘをデータベース２２に記憶されたデータ、Ｙを入力データとして、
2004040477.tif 000003
ここで、アイテム＜ｆｉ：ｘｉ＞は、項目「ｆｉ」の値が「ｘｉ」であることを示す。また、項目が数値属性であるアイテムについては、全て［０，１］区間に正規化し、αを０〜１の半径として定める。すなわち、入力データの値を中心に、半径αの中にある場合にδの値は１となり、半径αの外にある場合にδの値は０となる。
すなわち、この類似度関数は、データベースに記憶したデータについて、入力データが有するアイテムと一致するアイテムの数を計数することとなる。第２図（ｂ）では、各データにおいて入力データと一致するアイテムを円で囲んで示し、類似度関数の出力を類似度として示す。なお、「年齢」は数値データであるが、ここでのα＝０．１８に相当するマージン５を許容し、年齢の値が３０〜４０である場合にアイテムが一致したと判断している。
さらに、第２図（ｂ）に示したデータ群を類似度に従って配したデータ空間を第３図に示す。第３図では、入力データを「★」によって示し、クラスＰに属するデータを「○」、クラスＮに属するデータを「×」として示す。なお、各記号の近傍に示した数字が第２図（ｂ）のデータナンバーである。
第３図に示したように、類似度が３であるデータ７，１０，１２，１３が入力データに最も近く、同心円４１の上に存在する。また、類似度２であるデータ２，９が次の同心円４２の上に存在する。さらに、類似度１であるデータ１，４，５，６，１１が次の同心円４３の上に存在し、類似度が０のデータ３，８は、同心円４３の外に存在することとなる。
類似データ抽出部３２は、類似度が所定の閾値以上であるデータを類似データとして抽出する。または、類似度が高い順に、所定の数、例えば５個のデータを類似データとして抽出する。なお、類似度が等しいデータは全て類似データに含める。したがって、第３図では、類似度が３であるデータ７，１０，１２，１３および類似度が２であるデータ２，９の６個のデータを類似データとして抽出することとなる。
二値化処理部３３は、類似データ抽出部３２が抽出した類似データに対して二値化処理をおこなう。具体的には、類似データからδ＝０であったアイテムを除外し、さらに、δ＝１であった項目の値を入力データの同一項目の値に置き換える。ここで、離散値属性の項目の値は入力データと同一である。したがって、数値属性の項目の値を入力データの項目の値に書き換えることで、類似データの二値化をおこなうことができる。
したがって、二値化の結果、以下の類似データが得られる。
データ２    ｛＜住居：借家＞＜性別：男性＞｝
データ７    ｛＜住居：借家＞＜性別：男性＞＜結婚：既婚＞｝
データ９    ｛＜年齢：３５＞＜性別：男性＞｝
データ１０  ｛＜年齢：３５＞＜性別：男性＞＜結婚：既婚＞｝
データ１２  ｛＜年齢：３５＞＜住居：借家＞＜性別：男性＞｝
データ１３  ｛＜住居：借家＞＜性別：男性＞＜結婚：既婚＞｝
このように、類似データを二値化することで、類似データに含まれるアイテムは、入力データに含まれるアイテムのみとなる。したがって、以降、アイテム集合の演算のみで特徴パターン算出の処理をおこなうことができる。
つぎに、類似パターン集合算出部３４の処理について説明する。類似パターン集合算出部３４は、クラスＰとクラスＮのそれぞれについて最大パターン集合と最小パターン集合とを算出する。最大パターン集合は、そのクラスの類似データに自身の上位集合が存在しないアイテムの集合である。また、最小パターン集合は、そのクラスの類似データに、自身の部分集合（サブセット）となる集合が存在しないアイテムの集合である。
第４図に最大パターン集合と最小パターン集合とを示す。第４図（ａ）は、クラスＰにおける集合の包含関係を示す図であり、第４図（ｂ）は、クラスＮにおける集合の包含関係を示す図である。
ここで、クラスＰに関しては、
データ２  ｛＜住居：借家＞＜性別：男性＞｝
データ７  ｛＜住居：借家＞＜性別：男性＞＜結婚：既婚＞｝
であり、データ２のアイテムは、全てデータ７に含まれる。すわなち、データ２はデータ７の部分集合であり、データ７は、データ２の上位集合である。この関係を第４図（ａ）において実線の矢印によって示している。
ここで、クラスＰの類似データに、データ７の上位集合となる集合は存在しない。したがって、データ７は、クラスＰの最大パターン集合である。一方、データ１，６は、データ２の部分集合である。しかしながら、データ１，６は類似度が１であり、類似データとして選択されていない。すなわち、クラスＰの類似データの中にデータ２の部分集合となる集合は存在しないので、データ２は、クラスＰの類似データの最小パターン集合となる。
同様に、クラスＮに関しては、
データ９    ｛＜年齢：３５＞＜性別：男性＞｝
データ１０  ｛＜年齢：３５＞＜性別：男性＞＜結婚：既婚＞｝
データ１２  ｛＜年齢：３５＞＜住居：借家＞＜性別：男性＞｝
データ１３  ｛＜住居：借家＞＜性別：男性＞＜結婚：既婚＞｝
であり、データ９のアイテムは、全てデータ１０，１２に含まれる。すなわち、データ９は、データ１０と１２の両方の部分集合であり、データ１０，１２はともにデータ９の上位集合である。この関係を第４図（ｂ）において実線の矢印によって示している。
ここで、クラスＮの類似データにデータ１０，１２の上位集合となる集合は存在しない。したがって、データ１０，１２はそれぞれクラスＮの最大パターン集合である。また、クラスＮの類似データの中にデータ９の部分集合となる集合は存在しないので、データ９は、クラスＮの最小パターン集合となる。
なお、データ１３は、クラスＮの類似データの中に上位集合も部分集合も存在しない。したがって、データ１３は、クラスＮの最大パターン集合であり、かつ最小パターン集合である。
ここで、クラスＰにおいて、二値化済み類似データをＤｐ、最小パターン集合をＬｐ、最大パターン集合をＲｐとすると、パターン集合［Ｌｐ，Ｒｐ］は、少なくとも一つの最小パターンの上位集合であり、少なくとも一つの最大パターンの部分集合であるようなパターン全体である。したがって、
Ｄｐ⊆［Ｌｐ，Ｒｐ］
が成立する。
第４図（ａ）に示したデータでは、Ｌｐ＝｛｛借家，男性｝｝、Ｒｐ＝｛｛借家，男性，既婚｝｝および、Ｄｐ＝｛｛借家，男性｝｝、｛借家，男性，既婚｝｝となる。
同様に、クラスＮにおいて、二値化済み類似データをＤｎ、最小パターン集合をＬｎ、最大パターン集合をＲｎとすると、パターン集合［Ｌｎ，Ｒｎ］は、少なくとも一つの最小パターンの上位集合であり、少なくとも一つの最大パターンの部分集合であるようなパターン全体である。したがって、
Ｄｐ⊆［Ｌｐ，Ｒｐ］
が成立する。
第４図（ｂ）に示したデータでは、Ｌｎ＝｛｛３５，男性｝，｛借家，男性，既婚｝｝、Ｒｎ＝｛｛３５，借家，男性｝，｛３５，男性，既婚｝，｛借家，男性，既婚｝｝および、Ｄｎ＝｛｛借家，男性｝｝、｛３５，借家，男性｝，｛３５，男性，既婚｝，｛借家，男性，既婚｝｝となる。
なお、図４に示した例では、Ｄｐ＝［Ｌｐ，Ｒｐ］であったが、最小パターンの上位集合であり最大パターンの部分集合であるようなパターンは、類似データに存在しない場合、すなわちＤｐに存在しないパターンであっても、［Ｌｐ，Ｒｐ］に含まれる。
ここで、＜Ｌ，Ｒ＞を最小パターンＬおよび最大パターンＲのボーダーとして定義する。ボーダー＜Ｌ，Ｒ＞は、パターン集合である［Ｌ，Ｒ］を最小パターンと最大パターンのペアとして表記したものである。したがって、ボーダーを用いることで、集合の演算をおこなう場合に直接集合の要素を扱うことなく、最大パターンと最小パターンだけを対象とする演算に置き換えることができ、計算を大幅に効率化することができる。
類似パターン算出部３４は、このボーダー＜Ｌｐ，Ｒｐ＞およびボーダー＜Ｌｎ，Ｒｎ＞を類似パターン集合として特徴パターン集合３５に出力し、処理を終了する。
つぎに、特徴パターン算出部３５の動作について説明する。まず、ＲｐおよびＲｎが全データを対象としたクラスＰおよびクラスＮの最大パターンであるとき、［｛φ｝，Ｒｐ］−［｛φ｝，Ｒｎ］は、クラスＰのみに出現する全てのパターンを含むパターン集合であることが証明されている。（Ｊ．Ｌｉ  ａｎｄ  Ｋ．Ｒａｍａｍｏｈａｎａｒａｏ．Ｔｈｅ  ｓｐａｃｅ  ｏｆ  ｊｕｍｐｉｎｇ  ｅｍｅｒｇｉｎｇ  ｐａｔｔｅｒｎｓ  ａｎｄ  ｉｔｓ  ｉｎｃｒｅｍｅｎｔａｌ  ｍａｉｎｔｅｎａｎｃｅ  ａｌｇｏｒｉｔｈｍ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  １７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  ｌｅａｒｎｉｎｇ，ｐａｇｅｓ  ５５１−５５８．Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ，２０００．）
本発明では、ＲｐおよびＲｎは入力データに類似するデータを処理対象としており、データ全体における最大パターンである保証は無いが、類似データは高い類似度を持つことから入力データのアイテムに対する一致数は多く、また、最大パターンは通常、アイテム数が多いため、最大パターンが類似パターンに含まれる可能性は高い。
しかし、最大パターンが多数含まれていたとしても、最大パターンの検出漏れが発生する可能性があり、一つでも検出漏れがあった場合には正しくない特徴パターンを発見する可能性がある。このような正しくない特徴パターンは分類精度の低下の原因となる。そこで、類似データから特徴パターンを算出する場合に類似データに対してクラスＰとクラスＮに共通して現れるパターンよりもアイテム数が多いことを条件として付加することで、最大パターンの検出漏れを防止し、分類精度の低下を防止することができる。
特徴パターン集合算出部３５の処理動作を第５図に示す。第５図において、特徴パターン集合算出部３５は、まず、類似パターン集合＜Ｌｐ，Ｒｐ＞および＜Ｌｎ，Ｒｎ＞からパターン集合［｛φ｝，Ｌｐ］および［｛φ｝，Ｌｎ］に共通して出現するパターン集合をもとめる。具体的には、まず、出力データとなるｅｐＬｐとｅｐＲｐをｅｐＬｐ＝｛｝，ｅｐＲｐ＝｛｝として初期化する。つぎに、ｉｎｔｅｒｓｅｃＯｐｅｒａｔｉｏｎ（＜｛φ｝，Ｌｐ＞，＜｛φ｝，Ｌｎ＞）によって＜｛φ｝，｛ｃｌ，．．．．ｃｋ｝＞を算出する（ステップＳ１０２）。このｉｎｔｅｒｓｅｃＯｐｅｒａｔｉｏｎは、上述の文献に示されたものと同一であり、２つのボーダー＜｛φ｝，Ｌｐ＞，＜｛φ｝，Ｌｎ＞によって示される集合に共通に出現する全てのパターンをボーダー＜｛φ｝，｛ｃｌ，．．．．ｃｋ｝＞の形式で出力する。
すなわち、この処理によって、パターン集合［｛φ｝，Ｌｐ］および［｛φ｝，Ｌｎ］に共通して出現する最大パターンの集合である｛ｃｌ，．．．．ｃｋ｝が得られることとなる。この｛ｃｌ，．．．．ｃｋ｝に含まれる任意のｃｉは、共通の最大パターンであるから、ｃｉの上位集合は、
・クラスＰのデータにのみ出現する
・クラスＮのデータにのみ出現する
・クラスＰ、クラスＮのいずれにも出現しない
のいずれかである。
したがって、｛ｃｌ，．．．．ｃｋ｝の各要素ｃｉについて、ｃｉを含み、クラスＰにのみ出現してクラスＮに出現しないパターンを探すことで、クラスＰに特徴的に出現するパターンの集合を得ることができる。
したがって、特徴パターン集合算出処理部３５は、｛ｃｌ，．．．．ｃｋ｝を求めた後、最初のパターンｃｌを処理対象に設定し（ステップＳ１０３）、さらに、クラスＰの最大パターン集合Ｒｐの中から、処理対象である共通パターンの上位集合になるパターン集合ｒｐを求める（ステップＳ１０４）。その後、クラスＮの最大パターン集合Ｒｎから処理対象の共通パターンの上位集合になるパターン集合ｒｎを求める（ステップＳ１０５）。
つぎに、特徴パターン集合算出処理部３５は、パターン集合［｛φ｝，ｒｐ］に出現し、パターン集合［｛φ｝，ｒｎ］に出現しないパターン集合を求める。具体的には、ｊｅｐＰｒｏｄｕｃｅｒ（＜｛φ｝，ｒｐ＞，＜｛φ｝，ｒｎ＞）によって＜ｅｌ，ｅｒ＞を算出する（ステップＳ１０６）。このｊｅｐＰｒｏｄｕｃｅｒは、上述の文献に示されたものと同一であり、ボーダー＜｛φ｝，ｒｐ＞によって示されるパターン集合［｛φ｝，ｒｐ］に出現し、ボーダー＜｛φ｝，ｒｎ＞によって示されるパターン集合［｛φ｝，ｒｎ］に出現しないパターン集合をボーダー＜ｅｌ，ｅｒ＞の形式で出力する。
ここで、ｅｌが｛φ｝でなければ（ステップＳ１０７，Ｎｏ）特徴パターン集合算出処理部３５は、＜ｅｌ，ｅｒ＞に処理対象の共通パターンを加え、ボーダー＜ｅＬ，ｅＲ＞を作成する（ステップＳ１０８）。このボーダー＜ｅＬ，ｅＲ＞によって示されるパターン集合は、処理対象の共通パターンの上位集合であるので、クラスＰに出現し、クラスＮに出現しないパターン集合となる。
特徴パターン集合３５は、このボーダー＜ｅＬ，ｅＲ＞をボーダー＜ｅｐＬｐ，ｅｐＲＰ＞に追加する（ステップＳ１０９）。ボーダー＜ｅｐＬｐ，ｅｐＲｐ＞は、最終的に特徴パターンとして出力するデータである。ここで、ｅｐＬｐは、常に最小パターンのみを要素とするように監視し、最小ではないパターンを除外する（ステップＳ１１０）。
ステップＳ１１０終了後またはｅｌが｛φ｝の場合（ステップＳ１０７，Ｙｅｓ）、特徴パターン集合算出部３５は、パターン集合｛ｃ１，．．．．ｃｋ｝の全ての要素について処理が終了したか否かを判定する（ステップＳ１１１）。特徴パターン集合算出部３５は、まだ処理が終了していない要素がある場合に（ステップＳ１１１，Ｎｏ）、つぎの要素を検査対象に設定し（ステップＳ１１３）、ステップＳ１０４に移行する。
一方、全ての要素について処理が終了していた場合（ステップＳ１１１，Ｙｅｓ）、特徴パターン集合算出部３５は、ボーダー＜ｅｐＬｐ，ｅｐＲｐ＞を出力する（ステップＳ１１２）。
また、特徴パターン算出処理部３５は、クラスＮについても同様にボーダー＜ｅｐＬｎ，ｅｐＲｎ＞を算出することができる。特徴パターン算出処理部３５は、この＜ｅｐＬｐ，ｅｐＲｐ＞と＜ｅｐＬｎ，ｅｐＲｎ＞とをもちいて、
ＳＥＰ＝ｅｐＬｐ∪ｅｐＬｎ
である特徴パターン集合ＳＥＰを出力する。この特徴パターンＳＥＰは、クラスＰまたはクラスＮに特徴的にあらわれる最小パターンの和集合である。特徴パターン算出部３５は、特徴パターン集合ＳＥＰを特徴パターン出力装置２１の外部に出力するともに、入力データ分類処理部３６に出力する。
この特徴パターン算出部３５の処理を、図４に示したデータについて適用すると、まず、クラスＰの最小パターン集合がＬｐ＝｛｛借家，男性｝｝であり、クラスＮの最小パターン集合がＬｎ＝｛｛３５，男性｝，｛借家，男性，既婚｝｝であるので、共通して出現するパターン集合は｛｛借家，男性｝｝である（ステップＳ１０２）。
そこで、ｃｉ＝｛借家，男性｝として、続く処理を継続する（ステップＳ１０２）。
クラスＰでは、クラスＰの最大パターン集合Ｒｐ＝｛｛借家，男性，既婚｝｝のうち、ｃｉ＝｛借家，男性｝の上位集合となっているものは、ｒｐ＝｛｛借家，男性，既婚｝｝である（ステップＳ１０３）。同様にクラスＮでは、クラスＮの最大パターン集合Ｒｎ＝｛｛３５，借家，男性｝，｛３５，男性，既婚｝，｛借家，男性，既婚｝｝のうち、ｃｉ＝｛借家，男性｝の上位集合となっているものは、ｒｎ＝｛｛３５，借家，男性｝，｛借家，男性，既婚｝｝である（ステップＳ１０４）。
求めた［｛φ｝，ｒｐ］に出現し、［｛φ｝，ｒｎ］に出現しないパターン集合を、ｊｅｐＰｒｏｄｕｃｅｒ（＜｛φ｝，ｒｐ＞，＜｛φ｝，ｒｎ＞）によって求めた結果は、＜ｅｌ，ｅｒ＞＝＜｛φ｝，｛φ｝＞である（ステップＳ１０５）。
最大の共通パターン集合｛ｃｉ｝の要素はひとつだけであり、結局この例ではクラスＰの特徴パターンは＜ｅｐＬｐ，ｅｐＲｐ＞＝＜｛φ｝，｛φ｝＞となる。
一方、クラスＮでは、ステップＳ１０４までの処理結果は、クラスＰの場合と同様であり、ｃｉ＝｛借家，男性｝，ｒｎ＝｛｛３５，借家，男性｝，｛借家，男性，既婚｝｝，ｒｐ＝｛｛借家，男性，既婚｝｝である。（ステップＳ１０１〜Ｓ１０４）。
求めた［｛φ｝，ｒｎ］に出現し、［｛φ｝，ｒｐ］に出現しないパターン集合を、ｊｅｐＰｒｏｄｕｃｅｒ（＜｛φ｝，ｒｎ＞，＜｛φ｝，ｒｐ＞）によって求めた結果は、＜ｅｌ，ｅｒ＞＝＜｛３５｝，｛３５，借家，男性｝＞である（ステップＳ１０５）。このｅｌ，ｅｒそれぞれにｃ１を追加したボーダーは＜ｅＬ，ｅＲ＞＝＜｛３５，借家，男性｝，｛３５，借家，男性｝＞である（ステップＳ１０６）。最大の共通パターン集合｛ｃ１｝の要素はひとつだけであり、結局この例ではクラスＮの特徴パターン集合は＜ｅｐＬｎ，ｅｐＲｎ＞＝＜｛３５，借家，男性｝，｛３５，借家，男性｝＞となる（ステップＳ１０７〜Ｓ１１０）。
つぎに、入力データ分類処理部３６の動作について説明する。第６図は、入力データ分類処理部３６の処理動作を説明するフローチャートである。第６図において、入力データ分類処理部は、まず、クラスＰの二値化済み類似データＤｐ＝｛ｄ１，ｄ２・・・ｄｓ｝および特徴パターンＳＥＰ＝｛ｐ１，ｐ２・・・ｐｔ｝を入力データとして取得する（ステップＳ２０１）。
つづいて、入力データ分類処理部３６は、類似データＤｐのうち、最初の要素であるｄ１を処理対象に設定する（ステップＳ２０２）。さらに、入力データ分類処理部３６は、特徴パターンＳＥＰのうち、最初の要素であるｐ１を検査対象に設定する（ステップＳ２０３）。
入力データ分類処理部３６は、検査対象である特徴パターンが処理対象である類似データの部分集合になっているかどうかを検査する（ステップＳ２０４）。検査対象である特徴パターンが処理対象の類似データの部分集合になっている場合（ステップＳ２０４，Ｙｅｓ）、入力データ分類処理部３６は、クラスＰカウンタの値を一つ増加させる（ステップＳ２０９）。
一方、検査対象である特徴パターンが処理対象である類似データの部分集合になっていない場合（ステップＳ２０４，Ｎｏ）、入力データ分類処理部３６は、全ての特徴パターンについて検査を終了したか否かを判定する（ステップＳ２０５）。まだ検査が終了していない特徴パターンが存在する場合（ステップＳ２０５，Ｎｏ）、入力データ分類処理部３６は、次の特徴パターンを検査対象に設定（ステップＳ２０８）し、ステップＳ２０４に移行する。
全ての特徴パターンについて検査が終了した場合（ステップＳ２０５，Ｙｅｓ）、もしくはクラスＰカウンタの値を増加させた後、入力データ分類処理部３５は、全ての類似データについて処理を終了したか否かを判定する（ステップＳ２０６）。まだ検査が終了していない類似データが存在する場合（ステップＳ２０６，Ｎｏ）、入力データ分類処理部３５は、次の類似データを処理対象に設定し（ステップＳ２１０）、ステップＳ２０３に移行する。
一方、全ての類似データについて処理が終了した場合（ステップＳ２０６，Ｙｅｓ）、入力データ分類処理部３６は、クラスＰカウンタの値を出力して処理を終了する。この処理によって、入力データ分類処理部３６は、クラスＰに属する類似データのうち、特徴パターンＳＥＰのいずれかを含む類似データの数を計数することができる。すなわち、クラスＰカウンタの値は、クラスＰの類似データのうち、一つ以上の特徴パターンにマッチするデータ数となる。
また、入力データ分類処理部３６は、同様の処理によってクラスＮカウンタの値を出力する。このクラスＮカウンタの値は、クラスＮの類似データのうち、一つ以上の特徴パターンマッチするデータ数となる。入力データ分類処理部３６は、このクラスＰカウンタの値とクラスＮカウンタの値とを比較し、値の大きい方のクラスに入力データを分類する。
上述してきたように、この実施の形態１に示した特徴パターン出力装置２１では、入力データに類似するデータをデータベースか２２から抽出し、この類似データからクラスごとの最大パターン集合と最小パターン集合とを算出し、クラスごとの最大パターン集合と最小パターン集合から特徴パターンを算出するので、データベース２２のデータ数や各データのアイテム数に依存することなく、高速に特徴パターンの算出をおこなうことができる。
その結果、算出した特徴パターンをもちいて入力データを分類することで、入力データを簡易に分類することができる。
さらに、入力データに類似するデータから特徴パターンを算出することで、局所的な特徴パターンであっても高精度で検出することが可能となる。
ところで、入力データをもとに類似データを抽出する場合、類似データにノイズが発生することがある。そこで、類似データ抽出部３２にノイズ除去の機構を付加することで、特徴パターンの検出精度および入力データの分類精度を向上することができる。
類似データに発生するノイズとしては、所定のクラスの類似データに他のクラスのデータが混入するクラスノイズと、所定の類似データのアイテムが他のアイテムに置き換わる属性ノイズとが存在する。
クラスノイズが存在する場合、二値化処理後の類似データにおいて、クラスＰとクラスＮに同一の最大パターンが出現する可能性がある。クラスＰとクラスＮとに同一の最大パターンが出現すると、特徴パターンが一つも発見できなくなり、また、分類精度も著しく低下する。そこで、クラスＰとクラスＮに同一のパターンが共通して出現した場合には、共通して出現したパターンをそれぞれのクラスから除外し、除外したパターンの部分集合であるパターンをあらたに含めることで、クラスノイズの発生を抑制することができる。
また、属性ノイズについては、第７図に示した統計的検定処理によって除去することができる。第７図に示すように、この属性ノイズ除去では、まず、最小パターンの一つであるＬを入力する（ステップＳ３０１）。ここで、Ｌに含まれるアイテムをＩ１，Ｉ２・・・Ｉｋとすると、Ｌ＝｛Ｉ１，Ｉ２・・・Ｉｋ｝である。
つぎに、Ｌのうち、最初のアイテムであるＩ１を処理対象Ｉｉに設定する（ステップＳ３０２）．つぎに、Ｌｐから処理対象のアイテムを除外したパターンＢを生成する（ステップＳ３０３）。その後、Ｂ＝＞ＰとＢ∧Ｉｉ＝＞Ｐについて統計的検定をおこなう（ステップＳ３０４）。この検定によってパターンＢに処理対象であるアイテムＩｉを追加することが、統計的に偶然程度とみなせるか否かを判定する。統計的に偶然とみなせない場合、アイテムＩｉは、属性ノイズによって出現したと考えられる。
統計的検定処理は、具体的には、Ｂ＝＞ＰとＢ∧Ｉｉ＝＞Ｐの確率分布の間に違いがないという統計的仮説をたて、この仮説を棄却できるかを次の式によって検定する。
Ｔ＝（ＳＬＰＳＬ−ＳＬＳＢＰ）／（ＳＬＳＢＰ（ＳＢ−ＳＢＰ）／Ｎ）１／２
ここで、ＳＢはパターンＢにマッチするデータ数であり、ＳＬはパターンＢ∧Ｉｉにマッチするデータ数であり、ＳＢＰは、パターンＢにマッチするクラスＰのデータ数であり、ＳＬＰは、パターンＢ∧ＩｉにマッチするクラスＰに属するデータ数である。
このＴは正規分布に従うことが知られており、有意水準をａとすると、ｚ（ａ／２）は正規分布の密度関数ｐ（ｚ）＝ａ／２なる値であり、Ｔ≧ｚ（ａ／２）であれば、仮説はＢ＝＞ＰとＢ∧Ｉｉ＝＞Ｐの間に統計的な違いは無く、Ｉｉは偶然現れたものとして扱い、パターン集合Ｌｐから除外する。
したがって、第７図では、統計的検定の結果、仮説が棄却できるかいなかを判定し（ステップＳ３０５）、仮説が棄却できなかった場合（ステップＳ３０５，Ｎｏ）、処理対象のアイテムＩｉを属性ノイズとしてＬから除外し（ステップＳ３０８）、ステップＳ３０６に移行する。
一方、仮説が棄却できた場合（ステップＳ３０５，Ｙｅｓ）、全てのアイテムについて検定が終了したか否かを判定する（ステップＳ３０６）。まだ検定が終了していないアイテムがある場合（ステップＳ３０６，Ｎｏ）、次のアイテムを検定対象に設定し（ステップＳ３０９）、ステップＳ３０３に移行する。
また、全てのアイテムについて処理が終了した場合（ステップＳ３０６，Ｙｅｓ）、属性ノイズを除去した最小パターンＬを出力し（ステップＳ３０７）、処理を終了する。
このように、類似データ抽出部３２にクラスノイズおよび属性ノイズを除去する機能をもたせることで、特徴パターンの検出精度および入力データの分類精度を向上することができる。
（実施の形態２）
つぎに本発明の実施の形態２について説明する。上記実施の形態１では、データベース２２から類似データを抽出する場合に、所定の閾値を一つ設定し、この閾値以上の類似度を有するデータを抽出していたが、この実施の形態２では、クラスＰのデータとクラスＮのデータのそれぞれについて閾値を設定し、クラス別に類似データを抽出する。なお、類似データの抽出を所定の数を充たすように抽出する場合、クラスＰとクラスＮのそれぞれに所定の数を設定し、クラスＰとクラスＮについてそれぞれ抽出すればよい。
第８図に、実施の形態２におけるデータと類似度の関係を示す。第８図において、データ１〜１３の配置は、第４図と同様であり、同心円５１が類似度３を示し、同心円５２が類似度２を示し、同心円５３が類似度１を示す点についても第４図と同様である。しかしながら、この第８図では、クラスＰのデータについては同心円５３が閾値となり、クラスＮのデータについては同心円５２が閾値となる点が第４図の場合と異なる。
クラスＰについて類似度の閾値が１に下がったことで、第９図（ａ）に示すように、データ１，４，５，６が類似データとして新たに抽出されることとなる。ここで、データ１，６はデータ２の部分集合であり、データ４は、データ７の部分集合である。しかしながら、データ５は自身の上位集合をもたないため、クラスＰの最大パターンとなる。したがって、実施の形態２におけるＲｐはデータ５に対応する｛３５｝を加え、｛｛３５｝，｛借家，男性，既婚｝｝となる。なお、第９図（ｂ）にしめすように、クラスＮに関しては閾値が２であるので、クラスＮの類似パターンは変化しない。
実施の形態１において説明したように、全データから全ての最大パターンを取得すれば、全ての特徴パターンを算出できることが証明されており、本発明のように入力データの近傍のデータのみを扱う場合には、類似データから特徴パターンを算出する場合に類似データに対してクラスＰとクラスＮに共通して現れるパターンよりもアイテム数が多いことを条件として付加することで、最大パターンの検出漏れを防止し、分類精度の低下を防止することが必要である。
したがって、クラス別に閾値を設定し、全てのクラスから十分な数のサンプルを取得することで、最大パターンの検出漏れによる分類精度の低下を防止することができる。
この類似データの二値化と類似パターン集合の算出処理については、実施の形態１と同様であるので説明を省略するが、この実施の形態２における類似パターン集合は、入力データに対するクラス別の近傍を用い、データベース２２にふくまれるデータ全体の近似となっている。そこで、特徴パターンの算出処理では、上述のｊｅｐＰｒｏｄｕｃｅｒを使用し、
＜ｅｐＬｐ，ｅｐＲｐ＞＝ｊｅｐＰｒｏｄｕｃｅｒ（＜｛φ｝，Ｒｐ＞，＜｛φ｝，Ｒｎ＞）によって＜ｅｐＬｐ，ｅｐＲｐ＞を算出する。したがって、本実施の形態では、最小パターン集合Ｒｐ，Ｒｎを使用せず、最大パターン集合Ｌｐ，Ｌｎから特徴パターンを算出することができる。
さらに、この実施例では、ＳＥＰ＝ｅｐＬｐ∪ｅｐＬｎは、データベース２２全体に対する特徴パターンの近似であるので、入力データの分類をする場合に、データベース２２に含まれるデータ全体を対象にクラスＰカウントおよびクラスＮカウントを算出することができる。
なお、データベース２２全体に対してクラスＰカウントを算出する場合には、その値をデータベース２２に含まれるクラスＰデータのサイズで除することで、データベース２２全体におけるクラスＰの分布の偏りを補正することが好ましい。また、クラスＮカウントについても同様である。このように、各クラスに属するデータ集合のサイズをもとに補正をおこなうことで、データベース２２おける各クラスの分布比率に大きな偏りがある場合、たとえば、クラスＮのデータがクラスＰのデータに比して著しく多い場合であっても、入力データを精度良く分類することができる。
上述してきたように、本実施の形態２では、クラス別に異なる閾値を用いて類似データを抽出することで最大パターンの検出漏れを防止し、入力データの分類精度を向上している。
また、この実施の形態２では、データベース２２全体の特徴パターンの近似を得ることができ、さらにクラスの分布状態に関わらず、入力データの分類を高精度におこなうことができる。
なお、上述した実施の形態１および実施の形態２においては、入力データを分類する場合に、クラスＰの類似データおよびクラスＮの類似データについて、特徴パターンの出現数を比較しているが、入力データの分類はこの方法に限られるものではなく、他の評価基準や、その組合せを用いて入力データを分類することができる。
入力データの分類に使用可能な評価基準としては、たとえば特徴パターン数、特徴パターンのアイテム数などを用いることができる。なお、特徴パターン数では、特徴パターン現数が多い場合に評価を高くし、特徴パターンのアイテム数では、アイテム数が多い場合に評価を高くする。
具体的には、特徴パターン数を使用する場合には、ｅｐＬｐに属する特徴パターンのサイズの総和と、ｅｐＬｎに属する特徴パターンのサイズの総和とを比較し、その値が大きい方に入力パターンを分類する。
（実施の形態３）
本実施の形態３では、上記実施の形態１，２に示した特徴パターン出力装置と同様の機能を有する特徴パターン出力プログラムを実行するコンピュータシステムについて説明する。
第１０図に示すコンピュータシステム１００は、本体部１０１、本体部１０１からの指示により表示画面１０２ａに画像等の情報を表示するディスプレイ１０２、このコンピュータシステム１００に種々の情報を入力するためのキーボード１０３、ディプレイ１０２の表示画面１０２ａ上の任意の位置を指定するマウス１０４、ローカルエリアネットワーク（ＬＡＮ）１０６または広域エリアネットワーク（ＷＡＮ）に接続するＬＡＮインターフェース、インターネットなどの公衆回線１０７に接続するモデム１０５が備えられている。ここで、ＬＡＮ１０６は、ほかのコンピュータシステム（ＰＣ）１１１、サーバ１１２、プリンタ１１３等とコンピュータシステム１００とを接続している。また、第１１図に示すように、本体部１０１は、ＣＰＵ１２１、ＲＡＭ１２２、ＲＯＭ１２３、ハードディスクドライブ（ＨＤＤ）１２４、ＣＤ−ＲＯＭドライブ１２５、ＦＤドライブ１２６、Ｉ／Ｏインターフェース１２７およびＬＡＮインターフェース１２８を備えている。
このコンピュータシステム１００においてデータ管理方法を実行する場合、記憶媒体に記憶された、特徴パターン出力プログラムをコンピュータシステム１００にインストールする。インストールされた特徴パターン出力プログラムは、ＨＤＤ１２４に記憶され、ＲＡＭ１２２、ＲＯＭ１２３などを利用してＣＰＵ１２１により実行される。ここで、記憶媒体とは、ＣＤ−ＲＯＭ１０９、フロッピーディスク１０８、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体やコンピュータシステム１００の内外に備えられたハードディスク１２４等の記憶装置のほか、ＬＡＮ１０６を介して接続されたインストール元のデータ管理プログラムを保持するサーバ１１２のデータベース、あるいは、ほかのコンピュータシステム１１１並びにそのデータベースや、さらに公衆回線１０７上の伝送媒体をも含むものである。
上述してきたように、本実施の形態３では、実施の形態１，２に示した特徴パターン出力装置が有する構成をソフトウェアによって実現した特徴パターン出力プログラムをコンピュータシステム１００上で実行することで、実施の形態１，２に示した特徴パターン出力装置と同様の効果を、一般的なコンピュータシステムを用いて実現することができる。
以上説明したように、本発明によれば、入力データに類似する類似データをデータベースから抽出し、抽出した類似データから各クラスの特徴をなす特徴パターンを算出するので、データベースの規模によらず高速に特徴パターンを出力可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することができるという効果を奏する。
また、本発明によれば、データベースから抽出した抽出データの各アイテムの値と入力データの各アイテムの値とを比較し、一致するアイテムの組合せから最大パターン集合と最小パターン集合とを抽出し、この最大パターン集合と最小パターン集合とをもとに特徴パターンを算出するようにしているので、簡易な構成で高速に特徴パターンを出力可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することができるという効果を奏する。
また、本発明によれば、最小パターン集合をもとに複数のクラスにまたがって出現する共通パターンを求め、特徴パターンを共通パターンの上位集合として算出しているので、高速に特徴パターンを出力可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することができるという効果を奏する。
また、本発明によれば、類似データを抽出する場合に、クラスごとに条件を変更し、各クラスについて十分な数の類似データを取得するようにしているので、類似データを用いてデータベース全体を近似し、高速に特徴パターンを出力可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することができるという効果を奏する。
また、本発明によれば、複数のクラスにまたがって出現する最大パターンについて、そのアイテムを除去することで最大パターンが複数のクラスにまたがることを防止しているので、特徴パターンを高速かつ高精度に出力可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することができるという効果を奏する。
また、本発明によれば、類似データから算出した特徴パターンをもとに入力データを分類しているので、データベースの規模に関わらず入力データを高速に分類可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することができるという効果を奏する。
また、本発明によれば、各クラスの類似データにおける特徴パターンの出現数を計数し、この計数結果がもっとも大きい値となったクラスに入力データを分類しているので、入力データを高速かつ高精度に分類可能な特徴パターンを出力可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することができるという効果を奏する。
また、本発明によれば、アイテムが数値データである場合に所定の数値範囲を設定し、入力データのアイテムの値と類似データのアイテムの値とが所定の範囲内にある場合に両者のアイテムの値が一致したと判定するので、アイテムに数値データが含まれる場合であっても簡易な構成で高速に特徴パターンを出力可能な特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムを提供することができるという効果を奏する。
【産業上の利用可能性】  以上のように、本発明にかかる特徴パターン出力装置、特徴パターン出力方法および特徴パターン出力プログラムは、特に大規模データベースにおける特徴パターンの抽出の高速化に対して有用である。
【図１】
2004040477.tif 000004
【図２】
2004040477.tif 000005
【図３】
2004040477.tif 000006
【図４】
2004040477.tif 000007
【図５】
2004040477.tif 000008
【図６】
2004040477.tif 000009
【図７】
2004040477.tif 000010
【図８】
2004040477.tif 000011
【図９】
2004040477.tif 000012
【図１０】
2004040477.tif 000013
【図１１】
2004040477.tif 000014
【国際調査報告】
2004040477.tif 000015
2004040477.tif 000016