(57)【特許請求の範囲】
【請求項１】
コンピュータを、
対象と、対象に属するものとして関連付けられた第１の種類のデータと、前記第１の種類のデータに属するものとして関連付けられた第２の種類のデータとを構造の要素として含む複数の比較対象のデータから、予め定めた頻度で出現するデータ構造を見本のデータ構造として取得する取得手段と、
前記取得手段が取得した複数の前記見本のデータ構造の前記第２の種類のデータを比較する際に、前記見本のデータ構造間で前記第１の種類のデータが共通する第２の種類のデータ間の第１の類似度をそれぞれ算出する第１の類似度算出手段と、
前記第１の類似度算出手段が前記第２の種類のデータ毎に算出した前記第１の類似度に基づいて前記見本のデータ構造間の第２の類似度を算出する第２の類似度算出手段と、
前記第２の類似度が予め定められた値以上の類似性を示す前記見本のデータ構造を１つの分類として抽出する抽出手段として機能させるデータ構造比較プログラム。
【請求項２】
前記取得手段が前記見本のデータ構造を取得する際に、前記見本のデータ構造を取得した前記複数の比較対象のデータから時間を単位とする日時データを取得する日時データ取得手段と、
前記第１の類似度算出手段は、複数の見本のデータ構造の前記第２の種類のデータを比較する際に、前記見本のデータ構造間で前記第１の種類のデータが共通する第２の種類のデータに前記日時データ取得手段が取得した前記日時のデータを予め定めた方法で加えて、当該日時のデータが加えられた見本のデータ構造の間の第１の類似度を算出する請求項１に記載のデータ構造比較プログラム。
【請求項３】
前記第１の類似度算出手段は、第２の種類のデータの内容に応じて重み付けをして類似度を算出する請求項１又は２に記載のデータ構造比較プログラム。
【請求項４】
対象と、対象に属するものとして関連付けられた第１の種類のデータと、前記第１の種類のデータに属するものとして関連付けられた第２の種類のデータとを構造の要素として含む複数の比較対象のデータから、予め定めた頻度で出現するデータ構造を有する見本のデータ構造を取得する取得手段と、
前記取得手段が取得した複数の前記見本のデータ構造の前記第２の種類のデータを比較する際に、前記見本のデータ構造間で前記第１の種類のデータが共通する第２の種類のデータ間の第１の類似度をそれぞれ算出する第１の類似度算出手段と、
前記第１の類似度算出手段が前記第２の種類のデータ毎に算出した前記第１の類似度に基づいて前記見本のデータ構造間の第２の類似度を算出する第２の類似度算出手段と、
前記第２の類似度が予め定められた値以上の類似性を示す前記見本のデータ構造を１つの分類として抽出する抽出手段とを有するデータ構造比較装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ構造比較プログラム及びデータ構造比較装置に関する。
【背景技術】
【０００２】
従来のデータ構造を比較する方法として、例えば、ツリー構造を有する複数のデータからパターン抽出技法を用いて頻出するツリー構造を見本のデータ構造として抽出し、抽出された見本のデータ構造の類似度を算出するものがある（例えば、非特許文献１、２参照）。
【０００３】
非特許文献１には、根ノードを頂点として分岐する内部ノード及び最底辺の葉ノードから構成されるツリー構造間の比較をする際に、それぞれのツリー構造の葉ノードの並びを比較し、一方の葉ノードの並びから他方の葉ノードの並びへ変形するのに要するデータの挿入、削除、置換等の手順の最小回数（以下、「編集距離」という。）を算出する方法が開示されている。この編集距離を用いて、編集距離が予め定められた値より小さいツリー構造同士を類似性があるツリー構造とする。
【０００４】
また、非特許文献２には、ツリー構造の葉ノードだけでなく、ツリー構造間の根ノード及び内部ノードを含めて一方のツリー構造から他方のツリー構造へ変形するのに要するデータの挿入、削除、置換等の手順の最小回数（以下、「Ｔｒｅｅ  Ｅｄｉｔ距離」という。）を算出する方法が開示されている。このＴｒｅｅ  Ｅｄｉｔ距離の算出方法は、上記した非特許文献１の方法に比べて計算量が増加するものの、葉ノード以外も考慮するため、ツリー構造間の類似度としてより確かな値を算出する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Gusfield, Dan （1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN0-521-58519-8.
【非特許文献２】Philip, Bille.  A survey on tree edit distance and related problems. Journal Theoretical Computer Science, Volume 337 Issue 1-3, 9 June  2005. Elsevier Science Publishers Ltd. Essex, UK
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、本構成を採用しない場合と比べて計算量を減少するデータ構造比較プログラム及びデータ構造比較装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明の一態様は、上記目的を達成するため、以下のデータ構造比較プログラム及びデータ構造比較装置を提供する。
【０００８】
［１］コンピュータを、
対象と、対象に属するものとして関連付けられた第１の種類のデータと、前記第１の種類のデータに属するものとして関連付けられた第２の種類のデータとを構造の要素として含む複数の比較対象のデータから、予め定めた頻度で出現するデータ構造を見本のデータ構造として取得する取得手段と、
前記取得手段が取得した複数の前記見本のデータ構造の前記第２の種類のデータを比較する際に、前記見本のデータ構造間で前記第１の種類のデータが共通する第２の種類のデータ間の第１の類似度をそれぞれ算出する第１の類似度算出手段と、
前記第１の類似度算出手段が前記第２の種類のデータ毎に算出した前記第１の類似度に基づいて前記見本のデータ構造間の第２の類似度を算出する第２の類似度算出手段と、
前記第２の類似度が予め定められた値以上の類似性を示す前記見本のデータ構造を１つの分類として抽出する抽出手段として機能させるデータ構造比較プログラム。
【０００９】
［２］前記取得手段が前記見本のデータ構造を取得する際に、前記見本のデータ構造を取得した前記複数の比較対象のデータから時間を単位とする日時データを取得する日時データ取得手段と、
前記第１の類似度算出手段は、複数の見本のデータ構造の前記第２の種類のデータを比較する際に、前記見本のデータ構造間で前記第１の種類のデータが共通する第２の種類のデータに前記日時データ取得手段が取得した前記日時のデータを予め定めた方法で加えて、当該日時のデータが加えられた見本のデータ構造の間の第１の類似度を算出する前記［１］に記載のデータ構造比較プログラム。
【００１０】
［３］前記第１の類似度算出手段は、第２の種類のデータの内容に応じて重み付けをして類似度を算出する前記［１］又は［２］に記載のデータ構造比較プログラム。
【００１１】
［４］対象と、対象に属するものとして関連付けられた第１の種類のデータと、前記第１の種類のデータに属するものとして関連付けられた第２の種類のデータとを構造の要素として含む複数の比較対象のデータから、予め定めた頻度で出現するデータ構造を有する見本のデータ構造を取得する取得手段と、
前記取得手段が取得した複数の前記見本のデータ構造の前記第２の種類のデータを比較する際に、前記見本のデータ構造間で前記第１の種類のデータが共通する第２の種類のデータ間の第１の類似度をそれぞれ算出する第１の類似度算出手段と、
前記第１の類似度算出手段が前記第２の種類のデータ毎に算出した前記第１の類似度に基づいて前記見本のデータ構造間の第２の類似度を算出する第２の類似度算出手段と、
前記第２の類似度が予め定められた値以上の類似性を示す前記見本のデータ構造を１つの分類として抽出する抽出手段とを有するデータ構造比較装置。
【発明の効果】
【００１２】
請求項１又は４に係る発明によれば、本構成を採用しない場合と比べて計算量を減少することができる。
【００１３】
請求項２に係る発明によれば、日時データを含めた第１の類似度を算出することができる。
【００１４】
請求項３に係る発明によれば、第２の種類のデータの内容に応じて重み付けをすることができる。
【図面の簡単な説明】
【００１５】
【図１】図１は、本発明の実施の形態に係るデータ構造比較装置の構成の一例を示す図である。
【図２】図２は、ＤＰＣデータのパターンの構成の一例を示す概略図である。
【図３】図３は、計算用係数情報の構成の一例を示す概略図である。
【図４】図４は、重み付け係数情報の構成の一例を示す概略図である。
【図５】図５（ａ）及び（ｂ）は、パターン取得手段１００のパターンの取得元となるＤＰＣデータのサポートの構成例を示す。
【図６】図６（ａ）及び（ｂ）は、追加日時データが追加されたＤＰＣデータのパターンの構成の一例を示す概略図である。
【図７】図７は、第１の類似度の算出に用いる部分パターンを説明するための図である。
【図８】図８は、第１の類似度の算出に用いるリストの生成を説明するための図である。
【図９】図９は、第１の類似度の算出方法を説明するための図である。
【図１０】図１０は、第２の類似度の算出方法を説明するための図である。
【図１１】図１１（ａ）〜（ｃ）は、データ構造抽出動作の一例を説明するための概略図である。
【発明を実施するための形態】
【００１６】
（データ構造比較装置の構成）
図１は、本発明の実施の形態に係るデータ構造比較装置の構成の一例を示す図である。
【００１７】
データ構造比較装置１は、ＣＰＵ等から構成され各部を制御するとともに各種のプログラムを実行する制御部１０と、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）やフラッシュメモリ等の記憶媒体から構成され情報を記憶する記憶部１１とを備え、例えば、患者臨床情報及び診療行為の電子データの解析に用いられる。
【００１８】
制御部１０は、後述するデータ構造比較プログラム１１０を実行することで、パターン取得手段１００、日時データ追加手段１０１、第１の類似度算出手段１０２、第２の類似度算出手段１０３及びデータ構造抽出手段１０４等として機能する。
【００１９】
パターン取得手段１００は、解析対象である電子データとして記憶部１１から後述するＤＰＣデータ１１１に含まれる複数の比較対象のデータ（以下、「サポート」という。）から対象として患者名を根ノードとした見本のツリー構造を複数取得する。ここで、見本のツリー構造（以下、「パターン」という。）とは、パターン抽出技法を用いて、ツリー構造を有する複数のデータに予め定めた頻度で出現する共通のツリー構造として抽出されるもののことをいう。
【００２０】
なお、パターン取得手段１００は、周知のパターン抽出技法を用いることで、複数のサポート間で後述するＥファイル及びＦファイルが共通したものをパターンとして取得する。周知のパターン抽出技法として、例えば、シーケンシャル・パターン・マイニングのＰｒｅｆｉｘ  Ｓｐａｎ、ＢＩＤＥ、ＣｌｏＳｐａｎ等又はサブツリーマイニング等を用いることができる。
【００２１】
日時データ追加手段１０１は、パターン取得手段１００が取得したパターンの元となった複数のサポートから時間を単位とする日時データを抽出してパターンに追加する。なお、時間は、年月日、時間、分、秒等いずれを用いてもよい。
【００２２】
第１の類似度算出手段１０２は、比較対象となるパターン間において、葉ノードであるＦファイルのうち、後述するＥファイルが共通するＦファイルをリスト化して、パターン中の日時データをさらにリストに追加して、Ｅファイル毎に当該リストの類似度（以下、「第１の類似度」という。）として編集距離を算出する。
【００２３】
第２の類似度算出手段１０３は、第１の類似度算出手段１０２が算出したＥファイル毎の第１の類似度に基づいて比較対象のパターン間の類似度（以下、「第２の類似度」という。）として編集距離を算出する。
【００２４】
データ構造抽出手段１０４は、第２の類似度算出手段１０３が算出した第２の類似度が予め定められた値以下である複数のパターンの集合を１つの分類として抽出する。
【００２５】
記憶部１１は、制御部１０を上述した各手段として動作させるデータ構造比較プログラム１１０、ＤＰＣデータ１１１、計算用係数情報１１２及び重み付け係数情報１１３等を記憶する。
【００２６】
ＤＰＣデータ１１１は、分析可能な全国統一形式の患者臨床情報及び診療行為の電子データセットである。患者臨床情報は、例えば、患者基本情報、病名、術式、各種のスコア・ステージ分類等であり、診療行為情報は、診療行為、医薬品、医療材料、実施日、回数・数量、診療科、病棟、保険種別等である。
【００２７】
また、ＤＰＣデータ１１１は、基本となるデータとして様式１、Ｅファイル及びＦファイルと呼ばれるデータを有する。様式１とは、患者の臨床情報、傷病名、術式、補助治療等である。Ｅファイルとは、実施日、回数、診療科、病棟、オーダ医師等の情報である。Ｆファイルとは、Ｅファイルの詳細な内容であり、例えば、行為、薬剤、材料、数量等の情報である。
【００２８】
本実施の形態では、患者を根ノードとし、その患者に属する日時データ及びＥファイルを内部ノード、Ｅファイルに属するＦファイルを葉ノードとして構成されるツリー構造をサポートとし、複数のサポートに予め定めた頻度以上で現れるサポートのデータ構造をパターンとして取得して、取得されたパターン間で類似度を算出し、算出された類似度に基づいて複数のパターンの集合を抽出する。
【００２９】
図２は、ＤＰＣデータのパターンの構成の一例を示す概略図である。
【００３０】
ＤＰＣデータ１１１から取得されたパターン２ａ及びパターン２ｂは、患者に属する日時データ２２と、日時データ２２に属するＥファイル２１と、Ｅファイル２１に属するＦファイルとを有し、ツリー構造を構成する。
【００３１】
図３は、計算用係数情報の構成の一例を示す概略図である。
【００３２】
計算用係数情報１１２は、Ｆファイル、期間、日単位を行列の項目とし、第１の類似度算出手段１０２が編集距離を算出する際にＦファイル又は日時データに乗じる係数を定義する。なお、Ｆファイルと期間、Ｆファイルと日単位はそれぞれ比較すべき対象ではないので係数を「∞」としている。
【００３３】
図４は、重み付け係数情報の構成の一例を示す概略図である。
【００３４】
重み付け係数情報１１３は、Ｆファイル内容欄と、重み付け係数欄とを有し、第１の類似度算出手段１０２が編集距離を算出する際にＦファイルの内容に応じてＦファイル又は日時データに乗じる係数を定義する。
【００３５】
（データ構造比較装置の動作）
以下に、データ構造比較装置の動作例を各図を参照しつつ、（１）基本動作、（２）類似度算出動作、（３）データ構造抽出動作に分けて説明する。
【００３６】
（１）基本動作
まず、パターン取得手段１００は、記憶部１１のＤＰＣデータ１１１からデータ構造を抽出する対象となる複数のパターンを取得する。以下、説明を簡単にするため、図２に示す２つのパターン２ａ及び２ｂを取得した場合について説明する。
【００３７】
まず、パターンの取得方法を示すためにパターン２ｂを例にとって説明する。
【００３８】
図５（ａ）及び（ｂ）は、パターン取得手段１００のパターンの取得元となるＤＰＣデータ１１１のサポートの構成例を示す。
【００３９】
パターン取得手段１００は、パターン抽出技法を用いて、図５（ａ）に示す複数のサポート２００ｂ１、２００ｂ２…からパターン２ｂを取得する。
【００４０】
Ｆファイルの編集距離を利用した従来の技術では、Ｆファイル以外の情報を用いないため、日時データ２２がサポート２００ｂ１、２００ｂ２…それぞれにおいて異なっていても構わないため、図２に示すように、日時データ２２の内容が異なる箇所は「日単位」としてパターンＢを取得していた。
【００４１】
しかし、本実施の形態においては日時データ２２も考慮し、日時データ追加手段１０１は、パターン取得手段１００が取得したパターン２ｂの元となった複数のサポート２００ｂ１、２００ｂ２…（図５（ａ））から時間を単位とする日時データ２２を抽出して、異なる日時データを包括する内容の日時データとして、図５（ｂ）に示すように、追加日時データ２１０ｂ１、２１０ｂ２…を追加する。
【００４２】
図６（ａ）及び（ｂ）は、追加日時データが追加されたパターンの構成の一例を示す概略図である。
【００４３】
次に、日時データ追加手段１０１は、複数のサポート２００ｂ１、２００ｂ２…に追加された追加日時データ２１０ｂ１、２１０ｂ２…に基づき、図６（ａ）に示すように、パターン２ｂに追加日時データ２２ａを追加する。
【００４４】
次に、日時データ追加手段１０１は、追加日時データ２２ｂの日時の範囲内で複数のサポート２００ｂ１、２００ｂ２…の日時データを検索し、図６（ａ）に示す日時データ２２ａを、図６（ｂ）に示すように、例えば、対象とする日時データを包括する最小の値である追加日時データ２２ｂで置き換える。このように、本実施の形態では、従来の類似度の算出において用いられなかった日時データを要素として加えて類似度を算出する。なお、追加日時データ２２ａは、最小の値に限らず、予め定めた単位のうち全ての日時データを包括する値に設定してもよい。
【００４５】
（２）類似度算出動作
図７は、第１の類似度の算出に用いる部分パターンを説明するための図である。
【００４６】
次に、図７に示すように、第１の類似度算出手段１０２は、パターン２ａ及び２ｂをＥファイル２１に予め定められたデータ区分に基づき部分パターン２ａ１〜２ａ４、２ｂ１〜２ｂ４に分ける。
【００４７】
次に、第１の類似度算出手段１０２は、区分が「６０」で一致する部分パターン同士２ａ１と２ｂ１、区分が「５０」で一致する２ａ２と２ｂ２、区分が「５４」で一致する２ａ３と２ｂ３、区分が「７０」で一致する２ａ４と２ｂ４の間の第１の類似度を算出する。以下、算出方法を説明する。
【００４８】
図８は、第１の類似度の算出に用いるリストの生成を説明するための図である。
【００４９】
第１の類似度算出手段１０２は、例えば、区分が「６０」で一致する部分パターン２ａ１及び２ｂ１からそれぞれ日時データ２２とＦファイル２０を文字列として含むリスト３ａ１及び３ｂ１を生成する。この際、第１の類似度算出手段１０２は、Ｆファイル２０が属する日時データ２２をそのＦファイル２０の前を並び順としてリストに追加する。なお、日時データ２２の追加する並び順はこれに限るものではなく、Ｆファイル２０の後に追加してもよい。
【００５０】
図９は、第１の類似度の算出方法を説明するための図である。
【００５１】
次に、第１の類似度算出手段１０２は、リスト３ａ１及び３ｂ１の編集距離を算出する。具体的には、図９に示すように、リスト３ａ１及び３ｂ１に含まれる項目毎の類似度を数値化して行列とし、左上の要素から右下の要素へ最小値を取るように移動する。
【００５２】
ここで、行列中の同一の要素に対する右下への移動はリストに対して編集しない場合であり、異なる要素に対する下への移動はリストの要素を削除する場合、異なる要素に対する右への移動はリストの要素を挿入する場合にそれぞれ対応する。
【００５３】
上記の操作の結果、得られた最小値が編集距離となる。なお、図９に折れ線で示す例において、要素「翌日」と要素「２日後」を交換、要素「ＴＰ」を挿入、要素「ＧＰＴ」を削除、要素「ＡＬＰ」を挿入、要素「ＡＬｂ」を挿入する操作を行っている。
【００５４】
また、上記操作に対し、計算用係数情報１１２を係数として用いることで、日時データ同士の編集操作、Ｆファイル同士の編集操作以外を排除するとともに、Ｆファイルの交換に対する制限を大きくしている。なお、Ｆファイルの交換の係数を１としてもよい。
【００５５】
また、上記操作に対し、重み付け係数情報１１３を用いても良い。つまり、要素「翌日」と要素「２日後」を交換する操作は、図４においてＦファイル内容欄が「一日差」に対応するため、０．７を係数として乗じる。以下、同様に、要素「ＴＰ」を挿入する操作に対し１を係数として乗じ、要素「ＧＰＴ」を削除する操作に対し１を係数として乗じ、要素「ＡＬＰ」を挿入する操作に対し０．５を係数として乗じ、要素「ＡＬｂ」を挿入する操作する操作に対し２を係数として乗じて編集距離を算出してもよい。
【００５６】
上記の編集距離の算出をすべての部分パターン同士２ａ１と２ｂ１、２ａ２と２ｂ２、２ａ３と２ｂ３、２ａ４と２ｂ４について行いそれぞれパターン２ａと２ｂ間の第１の類似度を得る。
【００５７】
図１０は、第２の類似度の算出方法を説明するための図である。
【００５８】
パターン２ａ及び２ｂの対象とする全てのＦファイルを項目とし、Ｅファイル毎に分類した行列において、得られた各部分パターンの第１の類似度は、図１０に示すように、同行列中において対角上に配置される。
【００５９】
次に、第２の類似度算出手段１０３は、図１０に示す行列において、第２の類似度を算出する。具体的には、図９において説明したのと同様に、左上から右下へ単純に第１の類似度を加算していけばよい。このように、Ｅファイルが異なるＦファイル間の編集距離、例えば、Ｅファイル２１「５０」と「５４」、「６０」と「７０」等の間の第１の類似度を算出しないため、すべてのＦファイル間の編集距離を算出していた従来の方法に比べて計算量が減少する。
【００６０】
（３）データ構造抽出動作
図１１（ａ）〜（ｃ）は、データ構造抽出動作の一例を説明するための概略図である。
【００６１】
第２の類似度算出手段１０３によって各パターン間の第２の類似度が算出されると、図１１（ａ）に示すように、各パターン間の第２の類似度の関係を示す行列が生成される。
【００６２】
データ構造抽出手段１０４は、図１１（ａ）に示す行列において、第２の類似度の値が小さいものから順番に各パターンのデータ構造の類似性が高いと判断し、図１１（ｂ）に示すように、データ構造の類似性の高い複数のパターンを１つの分類として抽出する。
【００６３】
ここで、分類の閾値を、例えば、第２の類似度の値が３未満とすると、図１１（ｂ）に示すように、パターン２ａ〜２ｈの分類と、パターン２ｉ及び２ｊの分類とに分断され、図１１（ｃ）に示すように、データ構造抽出手段１０４は、パターン２ａ〜２ｈの分類をクラスター１、パターン２ｉ及び２ｊの分類をクラスター２として抽出する。
【００６４】
［他の実施の形態］
なお、本発明は、上記実施の形態に限定されず、本発明の趣旨を逸脱しない範囲で種々な変形が可能である。
【００６５】
また、上記実施の形態で使用されるデータ構造比較プログラム１１０は、ＣＤ−ＲＯＭ等の記憶媒体から装置内の記憶部に読み込んでも良く、インターネット等のネットワークに接続されているサーバ装置等から装置内の記憶部にダウンロードしてもよい。また、上記実施の形態で使用されるＤＰＣパターン取得手段１００、日時データ追加手段１０１、第１の類似度算出手段１０２、第２の類似度算出手段１０３及びデータ構造抽出手段１０４の一部または全部をＡＳＩＣ等のハードウェアによって実現してもよい。
【符号の説明】
【００６６】
１     データ構造比較装置
２ａ−２ｈ    パターン
２ａ１−２ａ４       部分パターン
３ａ１、３ｂ１       リスト
１０   制御部
１１   記憶部
２０   Ｆファイル
２１   Ｅファイル
２２   日時データ
２２ａ、２２ｂ       追加日時データ
１００ パターン取得手段
１０１ 日時データ追加手段
１０２ 第１の類似度算出手段
１０３ 第２の類似度算出手段
１０４ データ構造抽出手段
１１０ データ構造比較プログラム
１１１ ＤＰＣデータ
１１２ 計算用係数情報
１１３ 重み付け係数情報
２００ｂ１、２００ｂ２      サポート
２１０ｂ１、２１０ｂ２      追加日時データ
【図１】
0005652332.tif 000002
【図２】
0005652332.tif 000003
【図３】
0005652332.tif 000004
【図４】
0005652332.tif 000005
【図５】
0005652332.tif 000006
【図６】
0005652332.tif 000007
【図７】
0005652332.tif 000008
【図８】
0005652332.tif 000009
【図９】
0005652332.tif 000010
【図１０】
0005652332.tif 000011
【図１１】
0005652332.tif 000012