(57)【要約】【課題】複数の工程にまたがる複数のキー値の集合について、その組み合わせの種類ごとに、効率よく数え上げを行う数え上げ装置を提供する。【解決手段】データ管理部１０は、生データＤＢ１１のレコード毎に主成分分析により主成分得点を算出してハッシュ値として各レコードに割り当てる。関連性管理部２０は、生データＤＢ１１の各レコード間の関連性を示す関連性情報を作成し、関連性情報と各レコードのハッシュ値とから関係グラフを作成して関係グラフＤＢ２４に格納する。数え上げ管理部３０は、関係グラフＤＢ２４に格納された複数の関係グラフからノード数が最大の極大関係グラフを抽出し、極大関係グラフと構造が共通する関係グラフを関係グラフＤＢ２４から選択し、極大関係グラフと構造類似関係グラフとをハッシュ値を基に比較して類似と認められるノード同士を判定し、互いに類似するノード範囲を部分グラフとして抽出してカウントする。【選択図】図３
2010033348.tif 000002
【特許請求の範囲】
【請求項１】
複数のレコードから構成されるレコード構造データを格納するレコード構造データ格納部内のレコード毎に対して主成分分析により主成分得点をレコード毎に算出し、レコード毎に算出された主成分得点をハッシュ値として各レコードに割り当てるデータ管理部と、
前記レコード構造データ格納部に格納された各レコードに対して所定の規則に従ってレコード間の関連づけを実行して各レコード間の関連性を示す関連性情報を作成し、作成された関連性情報と前記データ管理部により各レコードに割り当てられたハッシュ値とから、一つのレコードを示し、かつ、当該レコードに対応するハッシュ値が対応付けられたシンボルを単位構成要素とするグラフであって、レコード間の関連性がシンボルによってモデル化された複数のハッシュ値付き関連グラフを作成し、作成された複数のハッシュ値付き関連グラフをグラフ格納部に格納する関連性管理部と、
前記グラフ格納部に格納された複数のハッシュ値付き関連グラフからシンボル数が最大であるハッシュ値付き関連グラフを極大グラフとして抽出し、抽出された極大グラフの一部に対して全部または一部がシンボルを同じくする構成であるハッシュ値付き関連グラフを構造類似グラフとして前記グラフ格納部から選択し、極大グラフと構造類似グラフとをハッシュ値を基に比較することにより、所定の基準に従って類似と認められるシンボル同士を判定し、互いに類似するシンボルの範囲を部分グラフとして抽出してカウントすると共に、抽出された部分グラフと同一の部分グラフが抽出される毎に当該部分グラフのカウント数をインクリメントする数え上げ管理部と
を備えたことを特徴とする数え上げ装置。
【請求項２】
前記数え上げ管理部は、
極大グラフを対象とする一連の処理が終了すると、極大グラフを前記グラフ格納部において無効化し、引き続き前記グラフ格納部から無効化されていない新たな極大グラフを選択し、無効化した極大グラフに対して行った一連の処理と同じ一連の処理を新たな極大グラフを対象として実行し、以降、極大グラフを切り替えながら前記グラフ格納部内に有効なグラフがなくなるまで一連の処理を継続することを特徴とする請求項１記載の数え上げ装置。
【請求項３】
前記数え上げ管理部が類似判定に使用する所定の基準は、
互いにハッシュ値の等しいシンボル同士を類似とすることを特徴とする請求項１または２のいずれかに記載の数え上げ装置。
【請求項４】
前記レコード構造データ格納部に格納される各レコードは、
他のレコードに関連付けされる関連付けデータの記載された項目を有し、
前記関連性管理部は、
所定の規則として関連付けデータに従うことにより、前記関連性情報を作成することを特徴とする請求項１〜３のいずれかに記載の数え上げ装置。
【請求項５】
コンピュータを、
複数のレコードから構成されるレコード構造データを格納するレコード構造データ格納部内のレコード毎に対して主成分分析により主成分得点をレコード毎に算出し、レコード毎に算出された主成分得点をハッシュ値として各レコードに割り当てるデータ管理部、
前記レコード構造データ格納部に格納された各レコードに対して所定の規則に従ってレコード間の関連づけを実行して各レコード間の関連性を示す関連性情報を作成し、作成された関連性情報と前記データ管理部により各レコードに割り当てられたハッシュ値とから、一つのレコードを示し、かつ、当該レコードに対応するハッシュ値が対応付けられたシンボルを単位構成要素とするグラフであって、レコード間の関連性がシンボルによってモデル化された複数のハッシュ値付き関連グラフを作成し、作成された複数のハッシュ値付き関連グラフをグラフ格納部に格納する関連性管理部、
前記グラフ格納部に格納された複数のハッシュ値付き関連グラフからシンボル数が最大であるハッシュ値付き関連グラフを極大グラフとして抽出し、抽出された極大グラフの一部に対して全部または一部がシンボルを同じくする構成であるハッシュ値付き関連グラフを構造類似グラフとして前記グラフ格納部から選択し、極大グラフと構造類似グラフとをハッシュ値を基に比較することにより、所定の基準に従って類似と認められるシンボル同士を判定し、互いに類似するシンボルの範囲を部分グラフとして抽出してカウントすると共に、抽出された部分グラフと同一の部分グラフが抽出される毎に当該部分グラフのカウント数をインクリメントする数え上げ管理部、
として機能させることを特徴とする数え上げプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数レコードの組み合わせを数え上げる数え上げ装置に関する。
【背景技術】
【０００２】
従来の数え上げ技術としては、各レコードが持つキーの値に応じて大量のレコードを分類し、ハッシュ処理に基づくグループバイ処理、すなわちキーの値に対して適切なハッシュ関数を適用して得られるハッシュ値に従って大量のレコードをハッシュしてハッシュ済みのレコードリストを作成し、そのハッシュ済みレコードリストをキーの値に従ってソートして、その結果でき上るソート済みレコードリストに対してグループバイ処理を行うことにより、データベースの中の膨大なデータのうちで相関のあるデータの組み合わせの出現回数を数え上げる方法がある（例えば、特許文献１）。また、木構造データで表されたデータ集合を含むデータベースから、集計対象となる候補パターンを用いて、頻出パターンを検出し数え上げる方法がある（例えば、特許文献２）。
【特許文献１】特開２００４−６２８９８号、「相関のあるデータ組み合わせの数え上げ装置」
【特許文献２】特開２００１−１３４５７５号、「頻出パターン検出方法およびシステム」
【発明の開示】
【発明が解決しようとする課題】
【０００３】
例えば、製造業における製造業務では、材料の状態から製品へ至るまで、一連の手順により複数の工程を経て製造、試験処理がなされる。この際、工程ごとに設定値もしくは測定値が発生し、それぞれの工程ごとにデータが蓄積される。このような際、複数のレコードにまたがるキー値の集合を種類ごとに数え上げを行う場合に、組み合わせ数が膨大になり現実的な処理時間にならない。また、複数のキーに対する完全一致で数え上げを行う場合には、組み合わせの種類が多いため、一種類ごとに少数個しか一致しない。そのため、占有率の高い条件を見つけるためには、複数の類似した組み合わせの種類をまとめて考える必要がある。完全一致による数え上げは、そのような処理に不向きである。
【０００４】
本発明は、そのような複数の工程（に属するレコード）にまたがる複数のキー値の集合について、その組み合わせの種類ごとに、効率よく数え上げを行うことを目的とする。
【課題を解決するための手段】
【０００５】
この発明の数え上げ装置は、
複数のレコードから構成されるレコード構造データを格納するレコード構造データ格納部内のレコード毎に対して主成分分析により主成分得点をレコード毎に算出し、レコード毎に算出された主成分得点をハッシュ値として各レコードに割り当てるデータ管理部と、
前記レコード構造データ格納部に格納された各レコードに対して所定の規則に従ってレコード間の関連づけを実行して各レコード間の関連性を示す関連性情報を作成し、作成された関連性情報と前記データ管理部により各レコードに割り当てられたハッシュ値とから、一つのレコードを示し、かつ、当該レコードに対応するハッシュ値が対応付けられたシンボルを単位構成要素とするグラフであって、レコード間の関連性がシンボルによってモデル化された複数のハッシュ値付き関連グラフを作成し、作成された複数のハッシュ値付き関連グラフをグラフ格納部に格納する関連性管理部と、
前記グラフ格納部に格納された複数のハッシュ値付き関連グラフからシンボル数が最大であるハッシュ値付き関連グラフを極大グラフとして抽出し、抽出された極大グラフの一部に対して全部または一部がシンボルを同じくする構成であるハッシュ値付き関連グラフを構造類似グラフとして前記グラフ格納部から選択し、極大グラフと構造類似グラフとをハッシュ値を基に比較することにより、所定の基準に従って類似と認められるシンボル同士を判定し、互いに類似するシンボルの範囲を部分グラフとして抽出してカウントすると共に、抽出された部分グラフと同一の部分グラフが抽出される毎に当該部分グラフのカウント数をインクリメントする数え上げ管理部と
を備えたことを特徴とする。
【発明の効果】
【０００６】
本発明によって、複数の工程にまたがる複数のキー値の集合について、その組み合わせの種類ごとに、効率よく数え上げを行う数え上げ装置を提供できる。
【発明を実施するための最良の形態】
【０００７】
実施の形態１．
図１は、コンピュータで実現される「複数レコード組み合わせ数え上げ装置１００」（数え上げ装置１００ともいう場合がある）の外観の一例を示す図である。図１において、数え上げ装置１００は、システムユニット８３０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶）の表示画面を有する表示装置８１３、キーボード８１４（Ｋｅｙ・Ｂｏａｒｄ：Ｋ／Ｂ）、マウス８１５、ＦＤＤ８１７（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・  Ｄｒｉｖｅ）、コンパクトディスク装置８１８（ＣＤＤ：Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｄｒｉｖｅ）、プリンタ装置８１９などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。
【０００８】
図２は、コンピュータで実現される数え上げ装置１００のハードウェア資源の一例を示す図である。図２において、数え上げ装置１００は、プログラムを実行するＣＰＵ８１０（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ：中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ８１０は、バス８２５を介してＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）８１１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）８１２、表示装置８１３、キーボード８１４、マウス８１５、通信ボード８１６、ＦＤＤ８１７、ＣＤＤ８１８、プリンタ装置８１９、磁気ディスク装置８２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置８２０の代わりに、光ディスク装置、フラッシュメモリなどの記憶装置でもよい。
【０００９】
ＲＡＭ８１２は、揮発性メモリの一例である。ＲＯＭ８１１、ＦＤＤ８１７、ＣＤＤ８１８、磁気ディスク装置８２０等の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部、格納部、バッファの一例である。通信ボード８１６、キーボード８１４、ＦＤＤ８１７などは、入力部、入力装置の一例である。また、通信ボード８１６、表示装置８１３、プリンタ装置８１９などは、出力部、出力装置の一例である。
【００１０】
通信ボード８１６は、ネットワーク（ＬＡＮ等）に接続されている。通信ボード８１６は、ＬＡＮに限らず、インターネット、ＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。
【００１１】
磁気ディスク装置８２０には、オペレーティングシステム８２１（ＯＳ）、ウィンドウシステム８２２、プログラム群８２３、ファイル群８２４が記憶されている。プログラム群８２３のプログラムは、ＣＰＵ８１０、オペレーティングシステム８２１、ウィンドウシステム８２２により実行される。
【００１２】
上記プログラム群８２３には、以下に述べる実施の形態の説明において「〜部」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ８１０により読み出され実行される。
【００１３】
ファイル群８２４には、以下に述べる実施の形態の説明において、「〜の判定結果」、「〜の算出結果」、「〜の抽出結果」、「〜の生成結果」、「〜の処理結果」として説明する情報や、データや信号値や変数値やパラメータなどが、「〜ファイル」や「〜データベース」（ＤＢと表記する場合もある）の各項目として記憶されている。「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ８１０によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵの動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００１４】
また、以下に述べる実施の形態の説明においては、データや信号値は、ＲＡＭ８１２のメモリ、ＦＤＤ８１７のフレキシブルディスク、ＣＤＤ８１８のコンパクトディスク、磁気ディスク装置８２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｋ）等の記録媒体に記録される。また、データや信号は、バス８２５や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００１５】
また、以下に述べる実施の形態の説明において、「〜部」として説明するものは、「手段」、「〜回路」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ＲＯＭ８１１に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。
【００１６】
プログラムはＣＰＵ８１０により読み出され、ＣＰＵ８１０により実行される。すなわち、プログラムは、以下に述べる「〜部」としてコンピュータを機能させるものである。あるいは、以下に述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００１７】
図３は、数え上げ装置１００の構成図である。組み合わせ数え上げ装置１００は、データ管理部１０、関連性管理部２０、数え上げ管理部３０を備える。データ管理部１０は、生データデータベース１１（レコード構造データ格納部）、主成分分析処理部１２、ハッシュ値割当部１３、ハッシュ値ＤＢ１４を備える。関連性管理部２０は、レコード関連性演算管理部２１、関連性ＤＢ２２、関係グラフ作成部２３、関係グラフＤＢ２４（グラフ格納部）を備える。数え上げ管理部３０は、極大関係グラフ抽出部３１、構造類似関係グラフ選択部３２、関係グラフ特性類似判定部３３、特性類似関係グラフ数え上げ部３４、部分グラフ数え上げバッファ３５、数え上げ結果ＤＢ３６を備える。
【００１８】
（データ管理部１０）
（１）生データＤＢ１１は、レコード構造のデータ（レコード構造データ）を格納する。
（２）主成分分析処理部１２は、生データＤＢ１１内のレコードごとの値に対して、主成分分析により主成分得点を算出する。
（３）ハッシュ値割当部１３は、レコード毎に算出された主成分得点をハッシュ値として、各レコードに割り当てる。
（４）ハッシュ値ＤＢ１４は、算出されたハッシュ値と生データＤＢ１１内のレコードとの関連付け情報を格納する。
【００１９】
（関連性管理部２０）
（１）レコード関連性演算管理部２１は、レコード間の関連性を算出し、関連性に関するデータ（関連性情報）を生成する。
（２）関連性ＤＢ２２は、生成されたレコード関連性情報を格納する。
（３）関係グラフ作成部２３は、レコード間の関連性情報とハッシュ値情報から、レコード間の関連性をモデル化したハッシュ値付きグラフを作成する。
（４）関係グラフＤＢ２４は、作成されたハッシュ値付きグラフに関する情報を格納する。
【００２０】
（数え上げ管理部３０）
（１）極大関係グラフ抽出部３１は、複数の関係グラフから、グラフのサイズが最大である関係グラフを、極大関係グラフ（極大グラフ）として抽出する。
（２）構造類似関係グラフ選択部３２は、極大関係グラフ抽出部３１で選択された関係グラフと、構造が類似した関係グラフを抽出する。
（３）関係グラフ特性類似判定部３３は、極大関係グラフと構造類似関係グラフ（構造類似グラフ）とをハッシュ値を基に比較し、類似しているグラフを識別する。
（４）特性類似関係グラフ数え上げ部３４は、抽出された類似グラフから、極大関係グラフもしくはその部分グラフと同一のハッシュ値を持つグラフを数え上げる。
（５）部分グラフ数え上げバッファ３５は、部分グラフの数え上げ時に、後に同じ構造の部分グラフが生成された場合に備えて部分グラフとそれまでの数え上げ結果を格納する。
（６）数え上げ結果ＤＢ３６は、関係グラフ（およびその部分グラフ）との数え上げ結果を格納する。
【００２１】
図４〜図６を参照して数え上げ装置１００が適用される例を説明する。図４は、製造業において、製造工程データ、管理データをもとに数え上げ装置１００によって「（１）同一ＩＤのレコードの関連付」を行い、この関連付けに基づき「（２）複数の工程にわたるパターンの数え上げ」を実行し、その数え上げ装置１００による結果を用いて、「（３）ルールを発見」し、「（４）ルールによる自動制御、管理者の意思決定支援」へと適用する場面を示している。
【００２２】
（同一レコードの関連付け）
図５は、製造業において、材料が工程を経て製品となる場合を示しており、図４に示した「（１）同一レコードの関連付」を概念的に示している。レコード関連性演算管理部２１によって、工程ごと（Ａ工程、Ｂ工程、・・・Ｉ工程）に管理されている製造データのテーブルについて、履歴追跡型ＤＢにより、テーブル間の同一ＩＤのレコードに関係付けがされる。図５は、Ａ工程からＩ工程にわたる「ＩＤ＝１」のレコードの場合を示している。図５に示すように、数え上げ装置１００により複数の工程にわたる関係パターンを数え上げる。シーケンスマイニングなどの分析における基本処理でありながら、従来では処理時間を多く必要とする、複数工程にわたる条件とその結果との関係パターンの数え上げを効率化することができる。製造工程データや管理データをもとに「（１）同一レコードの関連付」を行い、関連性ＤＢ２２に関連性情報を格納する。そして、関連性情報をもとに「（２）複数の工程にわたるパターンの数え上げ」を実行する。この数え上げ装置１００を用いた数え上げによって、例えばＡｐｒｉｏｒｉ法を適用し、支持度、信頼度に基づき「（３）ルールを発見」する。そして、製造工程におけるパラメータの自動制御や、管理者の意思決定支援のための判断材料を提供（「（４）ルールによる自動制御、管理者の意思決定支援」）することができる。
【００２３】
（複数の工程にわたるパターンの数え上げ）
図６は、図４における「（２）複数の工程にわたるパターンの数え上げ」を概念的に示した図である。数え上げ装置１００は、ＩＤごとのレコードの関係から、工程をまたがる条件から得られた結果について、過去の履歴の中から数え上げを行う。そして、数え上げ装置１００による数え上げの結果を用いて、「（３）ルールを発見」し、「（４）ルールによる自動制御、管理者の意思決定支援」が可能となる。
【００２４】
（動作説明）
次に、動作について説明する。図７は、数え上げ装置１００の動作を示すフローチャートである。図７を参照して、数え上げ装置１００の動作を説明する。
【００２５】
（ステップＳ１１：データ蓄積）
最初に、Ｓ１１において、データがレコード形式で取得されており、生データＤＢ１１へ蓄積されているものとする。図８は、生データＤＢ１１のテーブル構造を示す図である。ここでレコード形式とは、図８に示すように、あらかじめ定められた複数の種類のキー項目（項目１、項目１等）に対して、それぞれの値を一つずつ格納するレコードを管理単位として、複数のレコードを管理する形式である。リレーショナルデータベースの一つのテーブルがレコード形式に当たる。図８では、レコードを識別するレコードＩＤと、項目の種類を区別する工程ＩＤとをデータとして持っているが、データベースシステムとして管理させることにより、各レコードがレコードＩＤをデータとして保持しておく必要はなく、工程ＩＤをレコードのデータとして保持しておく必要もない。
【００２６】
（ステップＳ１２：主成分分析処理部１２）
次に、Ｓ１２において、主成分分析処理部１２が、それらの複数の項目からなる複数のレコードに対して主成分分析を行う。主成分分析とは、多くのキー項目からなるデータに含まれている情報を、より少ない軸（項目にあたる）に要約するための分析手法である。全レコードから、最も効率よく要約するための軸の選び方を算出し、元のデータとの誤差が少なくなるように少ない軸を選択する。ここで、効率よく要約がされるように、軸を選択する際には、その軸に各レコードの値を投影したとき、最も分散が大きくなる軸が選ばれる。このとき、レコードごとに軸に投影された値を、そのレコードに対する主成分得点と呼ぶ。主成分得点の値が近いレコードは、その特性が近いという特性がある。一般には、そのような軸は複数個選択することができるが、以後は最初に求めた軸のみに注目して話を進める。
【００２７】
（ステップＳ１３：ハッシュ値割当部１３）
次にＳ１３において、ハッシュ値割当部１３が、そのレコードから得られた主成分得点を、そのレコードのハッシュ値として割り当てる。すなわち、主成分分析により得られる主成分得点は、前述の通り、複数のキー項目からなる多次元空間に各レコードをプロットした場合に、最も値が散らばる軸上の値を意味する。つまり、主成分得点は各レコードを最も拡散させ区別することのできる指標値である。ここでデータベースシステムの検索効率化のためによく使用されるハッシュ値は、同じ値にレコードがなるべく重複しないようにすることが望ましい。そのため、この特性をもとに主成分得点をハッシュ値として利用することができる。
【００２８】
実際には主成分得点は実数であるため、ハッシュ値として使用するには、整数値など離散的な値に丸める必要がある。一般には等間隔で数値範囲を区切り、それぞれの区間毎に丸める方式をとるが、データの分布特性から確率密度関数を推定し、それぞれの区間に属する確率が等確率になるように区間を設定して丸めることも想定される。
【００２９】
上記の特徴により、ハッシュ値割当部１３は、主成分得点をハッシュ値とすることで、複数のキー値を最も効率的に単一値に代表させることができる。生データＤＢ１１内の各レコードに対するハッシュ値の割り当てが完了した後は、ハッシュ値割当部１３は、それぞれのレコードとハッシュ値の関係をハッシュ値ＤＢ１４へ格納する。図９は、ハッシュ値ＤＢ１４のテーブル構造を示す図である。ここでは、図９に示すような例の通り、レコードＩＤと対応するハッシュ値を格納する。図９は、図８のレコードにハッシュ値（丸めた主成分得点）を割り当てた状態を示している。例えば、図８の「レコードＩＤ＝１」のレコードの場合、項目１、項目２・・・を要約し、代表する値としてハッシュ値＝４５が割り当てた状態を示している。
【００３０】
（ステップＳ１４：レコード関連性演算管理部２１）
次に、Ｓ１４において、レコード関連性演算管理部２１が、生データＤＢ１１の各レコードに対して、所定の規則に従ってレコード間の関連性を算出し、関連性ＤＢ２２に格納する。最も単純な実現方法（所定の規則の一例）は、生データＤＢ１１内の各レコードが既に関連付けされるべきレコードの情報（関連付けデータ）を持っており、その情報の突き合わせで関連性情報をデータ化する方法である。図１０は、関連性ＤＢ２２のテーブル構造を示す図であり、関連性情報の例を示している。図１０に示すように、自分自身と関連性を持つレコードを列挙して管理する。関連性の情報には前後関係があり、例えば、製造現場において工程Ａから工程Ｂを経て生産された品物に対して、それぞれレコードＡ、レコードＢの情報がデータとして蓄積された場合、レコードＡとレコードＢには（時系列的な）前後関係を持つ関連性が存在する。生データＤＢ１１内の各レコードに「関連付けデータ」を予め持たせることで、容易にレコード間の関連性情報を作成することができる。
もちろん、レコードごとに関連づけされるべきレコードの情報を保持しておらず、他の情報源やロジックによる演算処理によって関連づけを行う方式もあり得る。
【００３１】
（ステップＳ１５：関係グラフ作成部２３）
次に、Ｓ１５において、関係グラフ作成部２３が、関連性ＤＢ２２とハッシュ値ＤＢ１４とから、「関係グラフ」（ハッシュ値付き関連グラフ）を作成し、関係グラフＤＢ２４に格納する。「関係グラフ」とは、レコードにあたるノードと、２つのレコード間の関連性を示すエッジからなる仮想データ構造である。すなわち関係グラフ」とは、一つのレコードを示し、かつ、当該レコードに対応するハッシュ値が対応付けられたノード（シンボル、後述の円）を単位構成要素とするグラフであって、レコード間の関連性がシンボル（円）によってモデル化されたグラフである。図１１、図１２を参照して関係グラフを説明する。図１１は、関係グラフＤＢ２４のテーブル構造を示す図である。図１２は、関係グラフの可視化を示す図である。図１２に示すように関係グラフは、可視化の際にはノードは円（シンボル）で示され、エッジは２つのノードの円を結ぶ線で表される。関係グラフＤＢ２４では、図１１の例に示すとおり、その関係グラフを構成するノードの情報（レコード）と、そのノードに対応するハッシュ値を格納する。図１２は図１１を可視化した場合を示している。図１２において「Ａ（４２）」とは、工程Ａのハッシュ値が「４２」であることを示している。ただしこれは一例であり、格納するデータ構造として、ノードとエッジに関する情報をそれぞれ別に管理し、ノードの情報として、対応するレコードＩＤを管理し、エッジの情報として、その両端にあるノードの情報（つまりレコードＩＤ）をペアとして管理するようにしてよい。また、ノードの情報としてレコードＩＤと共にハッシュ値も必ずしも格納する必要はない。なお、関係グラフとして登録するグラフは、生データＤＢ１１の他のレコードを用いてもそれ以上グラフとして追加できない（グラフを構成していない残りのレコードとの関連性が存在しない）状態で登録するものとする。また、図１１のようにグラフＩＤをデータとして保持しておくことは必須ではない。
【００３２】
以上までのＳ１１〜Ｓ１５のステップで、複数レコードの組み合わせ数え上げを行うための前準備が行われる。以降では、実際に複数レコードの組み合わせ数え上げを行う。
【００３３】
（ステップＳ１６：極大関係グラフ抽出部３１）
次にＳ１６において、極大関係グラフ抽出部３１は、関係グラフＤＢ２４に格納された複数の関係グラフから、サイズが最大のもの（ノード数が最大のもの）を抽出し、極大関係グラフＧ０とする。例えば、図１２で説明すると、グラフＩＤ１００のグラフはノード数が４つであり、極大関係グラフ抽出部３１により極大関係グラフＧ０として抽出された場合を示している。なおグラフＩＤ２００のグラフもノード数＝４であるが、極大関係グラフ抽出部３１がグラフＩＤ１００のグラフを抽出した場合を示している。なお、後述のように、極大関係グラフであるグラフＩＤ１００のものはいずれ無効化され、新たにグラフＩＤ１００のものが極大関係グラフとして抽出されることになる。
【００３４】
（ステップＳ１７：構造類似関係グラフ選択部３２）
次に、Ｓ１７において、構造類似関係グラフ選択部３２は、極大関係グラフＧ０と構造が共通のものを持つグラフＧ’（構造類似関係グラフという）を、関係グラフＤＢ２４から検索する。ここで「構造が共通」とは、構造類似関係グラフＧ’が極大関係グラフの一部分の構造に該当する場合である。すなわち、「構造が共通」とは、関係グラフにおいて、極大関係グラフの一部に対して全部または一部がノード（シンボル）を同じくする構成であることをいう。このように、構造類似関係グラフ選択部３２は、極大関係グラフと構造が共通なものをもつ関係グラフを関係グラフＤＢ２４から検索する。構造が共通のものを持つグラフとは、共通のノードを持つ関係グラフのことを言う。図１１、図１２の場合で説明する。例えば関係グラフが、図１１のグラフＩＤ＝１００のグラフが極大関係グラフであり、他方の関係グラフがグラフＩＤ＝２００のグラフ（構造類似関係グラフとなるので、あらかじめＧ’の記号を用いる）である場合、図１２に示すように、
Ｇ０の工程ＩＤ２がＧ’の工程ＩＤ１と一致する「Ｂ」であり、
Ｇ０の工程ＩＤ３がＧ’の工程ＩＤ２と一致する「Ｃ」であり、
Ｇ０の工程ＩＤ４がＧ’の工程ＩＤ３に一致する「Ｄ」である。
従って、この関係グラフＧ’は、極大関係グラフと共通の構造をもつ。
従って、関係グラフＧ’は、極大関係グラフに対して構造類似関係グラフである。なお検索の際には、構造が共通している部分の割合によって閾値を設けてもよい。例えば、図１２で説明すると、共通している部分の割合の算出式を、
（Ｇ０とＧ’で工程ＩＤが共通しているノード数）×２÷（Ｇ０のノード数＋Ｇ’のノード数）
の定義式とする。このとき、構造が共通している部分の割合が８０％以上となることを構造類似関係グラフの条件とした場合、上の例のＧ０とＧ’との共通部分は、
（３）×２÷（４＋４）＝６÷８＝０．７５
となり、７５％であるため、Ｇ’はＧ０に構造が類似しているとはみなさない。もちろん、共通している部分の割合の算出式は他の定義を用いてもよい。
【００３５】
（ステップＳ１８：関係グラフ特性類似判定部３３）
関係グラフ特性類似判定部３３は、得られた構造類似関係グラフＧ’（通常はＧ’（１）〜Ｇ’（ｎ）のように複数得られる）を対象として、極大関係グラフＧ０と、それぞれの構造類似関係グラフＧ’との特性の類似性を判定する。類似性の判定には、極大関係グラフＧ０、構造類似関係グラフＧ’を構成するそれぞれのノードに割り当てられたハッシュ値を用いる。関係グラフ特性類似判定部３３は、得られた各構造類似関係グラフＧ’について、極大関係グラフと構造類似関係グラフＧ’との特性の類似性を判定する。関係グラフ特性類似判定部３３による類似性の判定には、それぞれのノードに割り当てられたハッシュ関数（丸められた主成分得点）を用いて、定量的に類似性が判定される。例えば、図１１、図１２の場合を例にとれば、前記のように、関係グラフＧ’は、極大関係グラフに対して共通の構造を持つ構造類似関係グラフである。図１２に示すように、このうちハッシュ値についても一致しているノードは、極大関係グラフの工程ＩＤ２と構造類似関係グラフＧ’の工程ＩＤ１（つまり工程Ｂどうし）、極大関係グラフの工程ＩＤ３と構造類似関係グラフＧ’の工程ＩＤ２（つまり工程Ｃどうし）に当たるノードである。関係グラフ特性類似判定部３３は、図１２において破線で囲んだ範囲のノードＢどうし、ノードＣどうしが類似であると判定する（図１２の場合は、同一であるが、同一も類似に含む）。
【００３６】
（ハッシュ値が同一でない場合）
関係グラフ特性類似判定部３３は、ハッシュ値が同一の場合だけではなく、ハッシュ値が近似している場合には、所定の基準により類似と認識する。
【００３７】
図１３を参照して説明する。図１３は、ハッシュ値の類似の判定方法を説明する図である。主成分分析により得られる主成分得点は、複数のキー項目からなる多次元空間に各レコードをプロットした場合に、最も値が散らばる軸上の値を意味する。つまり、主成分得点は各レコードを最も拡散させ区別することのできる指標値である。この特性は、同じ値にレコードがなるべく重複しないようにすることが望ましいハッシュ値として利用する際のメリットである。また、主成分得点の値が近いレコードは、その特性が近いことが言える。上記特徴により、主成分得点をハッシュ値とすることで、複数のキー値を最も効率的に単一値に代表させることができる。ハッシュ値から類似とみなす範囲は、第２主成分の特異値および主成分係数から算出することができる。第２主成分の特異値をｓ、元データの第ｉ項目に対応する主成分係数をｃｉとすると、ハッシュ値を幅６ｓｃｉの範囲に絞り込むことで、元データの第ｉ項目のある値を持つレコードについて、他の項目で外れ値をとるようなレコードを除く全てのレコードを列挙することができる。運用上は、主成分係数の最大値をＣとしたとき、６ｓＣの幅のハッシュ値を持つレコードに絞り込むことで、外れ値以外の取りもらしを最小限にしたレコードの列挙が可能である。
【００３８】
（ステップＳ１９：特性類似関係グラフ数え上げ部３４）
特性類似関係グラフ数え上げ部３４は、極大関係グラフとそれぞれの構造類似関係グラフＧ’とにおいてハッシュ値が同一である部分（ノード）を抽出し、抽出された部分を「部分グラフ」として部分グラフ数え上げバッファ３５に格納し、数え上げ結果を更新する。図１２の破線で囲んだ部分から得られる工程Ｂ、Ｃの部分が部分グラフである。すなわち「部分グラフ」とは、互いに類似するノード（シンボル）の範囲から構成されるグラフである。このように、特性類似関係グラフ数え上げ部３４は、極大関係グラフと構造類似関係グラフＧ’とにおいてハッシュ値が同一である部分（ノード）を抽出し、部分グラフとして部分グラフ数え上げバッファ３５に格納し、数え上げ結果を更新する。例えば、図１２で説明すれば、ハッシュ値についても一致しているノードは、破線で囲んだ範囲である。この場合、特性類似関係グラフ数え上げ部３４は、工程ＩＤがＢとＣで、ハッシュ値がそれぞれ３５と１５であるノードからなる部分を部分グラフとして抽出し、部分グラフ数え上げバッファ３５内の当該部分グラフのカウント（数え上げ結果）を１増やす。そのような部分グラフが部分グラフ数え上げバッファ３５に登録されていない場合は、この部分グラフを数え上げ結果１としてカウントすると共に部分グラフ数え上げバッファ３５に登録（格納）する。なお、関係グラフ特性類似判定部３３により、同一のハッシュ値ではないが類似すると判定されたノードについては以下の様である。図１２を参照して説明する。すなわち、特性類似関係グラフ数え上げ部３４は、ハッシュ値が類似している部分を抽出する場合、Ｇ０の工程ＩＤ４に当たるノード（工程Ｄ）と、Ｇ’の工程ＩＤ３にあたるノード（工程Ｄ）との類似性を確認する。関係グラフ特性類似判定部３３により、指定された指標で類似と判定されているのであれば、特性類似関係グラフ数え上げ部３４は、そのノードを含め、工程ＩＤがＢ，Ｃ，Ｄで、ハッシュ値がそれぞれ３５，１５，１４であるノードからなる部分グラフ（Ｇ’’とする）を抽出し、部分グラフ数え上げバッファ３５に登録されている部分グラフのうち、同じ構造で最も古く登録された部分グラフＧ’’の数え上げ結果を１増やす。そのような部分グラフＧ’’が部分グラフ数え上げバッファに登録されていない場合は、その部分グラフＧ’’の数え上げ結果１として数え上げたＧ’’を部分グラフ数え上げバッファ３５に登録する。
【００３９】
なお、関係グラフ特性類似判定部３３は、類似範囲とみなす幅は前述の６ｓＣの幅を基準に、適用用途に応じて、より大枠での分類が必要な場合には幅を広げる。限定された部分グラフそれぞれに対して、数え上げを行う。ここではレコードごとに一つの値で評価を行うため、元データで検証する場合のように、レコード毎に存在する複数の値の組み合わせについて条件分けを行う必要がない。そのため、類似判定処理の反復回数について大幅に軽減される。
【００４０】
（ステップＳ２０：特性類似関係グラフ数え上げ部３４）
Ｓ２０において、特性類似関係グラフ数え上げ部３４は、数え上げられていない関係グラフが存在するかどうかを判定する。すなわち、現在の処理対象となっている極大関係グラフに対して部分グラフの数え上げられていない関係グラフが存在するかどうかを判定する。存在しないと判定した場合、すなわち、極大関係グラフを対象とする部分グラフの数え上げを完了すると、処理対象となっていた極大関係グラフを関係グラフＤＢ２４上で無効化する。
【００４１】
（次のループ）
処理は次のループに入り、極大関係グラフ抽出部３１が、再び、関係グラフＤＢ２４において有効な関係グラフの中でサイズが最大の関係グラフを選択し、新たな極大関係グラフとし、Ｓ１６〜Ｓ１９の一連の処理が繰り返される。すなわち、極大関係グラフ抽出部３１よる極大関係グラフの抽出、構造類似関係グラフ選択部３２による構造類似関係グラフの選択、関係グラフ特性類似判定部３３による類似の判定、特性類似関係グラフ数え上げ部３４による部分グラフの数え上げという一連の処理が、関係グラフＤＢ２４上に有効な関係グラフが存在しなくなるまで継続される。
【００４２】
関係グラフＤＢ２４上に有効な関係グラフが存在しなくなったならば、特性類似関係グラフ数え上げ部３４が、数え上げ結果ＤＢ３６へ数え上げ結果を出力する。図１４は、数え上げ結果ＤＢ３６のテーブル構造を示す図である。図１４で示される例のように、数え上げられた関係グラフの情報と、その数え上げ件数を格納する。
【００４３】
これ以降は、バッファに蓄積されている数上げ結果を出力する場合には出力を行い（Ｓ２１）、生ＤＢのデータが更新された場合には（Ｓ２２）、データ取得ステップ（Ｓ１１）に戻って、再び処理を行う。なお、数え上げ結果ＤＢ３６に格納されている関係グラフおよびハッシュ値ごとに、対応する元データ内で詳細な数え上げを行ってもよい。この場合、数え上げの対象件数が少ないため、全体に対する処理に比べて処理時間が短縮される。
【００４４】
以上の実施の形態１の数え上げ装置１００は、各レコードの複数のキー項目に対して、主成分分析を行った結果得られる主成分得点を、レコード毎のハッシュ値として割り当てる。このようにハッシュ値を設定することにより、各レコードの複数のキー項目の特性を代表する単一値を得ることができる。複数レコードにわたる数え上げを行う場合に、レコードの組み合わせに加えて、レコード内のキー項目の組み合わせを考慮する必要がなくなり、組み合わせの数が乗算的に増える事態を抑制することができる。主成分得点値を採用することにより、特性が類似するレコードが似た値になるという特性から、類似検索にも対応することが可能である。
【００４５】
以上の実施の形態１の数え上げ装置１００によって、複数の工程と、工程内の複数の項目という二重の組み合わせ可能な状態の一方を要約することで、組み合わせの種類を大幅に削減し、処理時間を軽減することができる。また数え上げにより、ある事象の過去の発生確率（割合）を評価することができるため、経営判断などの指標とすることができる。従来のデータマイニングの対象を、単一工程同士の組み合わせから複数工程の組み合わせへと拡張でき、より木目の細かい分析が可能である。
【図面の簡単な説明】
【００４６】
【図１】実施の形態１における複数レコード組み合わせ数え上げ装置１００の外観の一例。
【図２】実施の形態１における数え上げ装置１００のハードウェア資源の一例。
【図３】実施の形態１における数え上げ装置１００のブロック図。
【図４】実施の形態１における数え上げ装置１００の利用形態を示す図。
【図５】実施の形態１における数え上げ装置１００の利用形態を示す別の図。
【図６】実施の形態１における数え上げ装置１００の利用形態を示すさらに別の図。
【図７】実施の形態１における数え上げ装置１００の動作のフローチャート。
【図８】実施の形態１における生データＤＢ１１のテーブル構造。
【図９】実施の形態１におけるハッシュ値ＤＢ１４のテーブル構造。
【図１０】実施の形態１における関連性ＤＢ２２のテーブル構造。
【図１１】実施の形態１における関係グラフＤＢ２４のテーブル構造。
【図１２】実施の形態１における関係グラフの可視化を示す図。
【図１３】実施の形態１におけるハッシュ値の類似の判定方法を説明する図。
【図１４】実施の形態１における数え上げ結果ＤＢ３６のテーブル構造。
【符号の説明】
【００４７】
１０  データ管理部、１１  生データＤＢ、１２  主成分分析処理部、１３  ハッシュ値割当部、１４  ハッシュ値ＤＢ、２０  関連性管理部、２１  レコード関連性演算管理部、２２  関連性ＤＢ、２３  関係グラフ作成部、２４  関係グラフＤＢ、３０  数え上げ管理部、３１  極大関係グラフ抽出部、３２  構造類似関係グラフ選択部、３３  関係グラフ特性類似判定部、３４  特性類似関係グラフ数え上げ部、３５  部分グラフ数え上げバッファ、３６  数え上げ結果ＤＢ、１００  数え上げ装置。
【図１】
2010033348.tif 000003
【図２】
2010033348.tif 000004
【図３】
2010033348.tif 000005
【図４】
2010033348.tif 000006
【図５】
2010033348.tif 000007
【図６】
2010033348.tif 000008
【図７】
2010033348.tif 000009
【図８】
2010033348.tif 000010
【図９】
2010033348.tif 000011
【図１０】
2010033348.tif 000012
【図１１】
2010033348.tif 000013
【図１２】
2010033348.tif 000014
【図１３】
2010033348.tif 000015
【図１４】
2010033348.tif 000016