(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
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、出現する複数のデータ構造のうち、共通するデータと当該共通するデータ以外のデータとの頻度を用い、当該データ構造から類似するものを判断して出力するデータ構造抽出プログラム及びデータ構造抽出装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明の一態様は、上記目的を達成するため、以下のデータ構造抽出プログラム及びデータ構造抽出装置を提供する。
【０００８】
［１］コンピュータを、
複数のサポートから予め定めた閾値以上の頻度で出現するパターンを複数種類抽出する抽出手段と、
前記抽出手段が第１の閾値を用いて抽出したパターンを有するサポートの集合のそれぞれにおいて、互いに有するパターンが類似するサポートの集合のすべてに共通するサポートが存在し、当該互いに有するパターンが類似するサポートの集合において当該共通するサポート以外のサポートを有さないサポートの集合が存在しない場合、前記共通するサポートの数を第２の閾値として設定する設定手段と、
前記抽出手段が第１の閾値を用いて抽出したパターンを有するサポートの集合のそれぞれにおいて、当該互いに有するパターンが類似するサポートの集合のすべてに共通するサポートが存在し、当該互いに有するパターンが類似するサポートの集合において当該共通するサポート以外のサポートを有さないサポートの集合が存在する場合、当該共通するサポート以外のサポートを有さないサポートの集合のパターンを出力すべきパターンであると判断する出力判断手段と、
前記出力判断手段が出力すべきパターンであると判断したパターンと、前記設定手段が対象としたサポートから前記第２の閾値以上の頻度で前記抽出手段により抽出されるパターンを出力する出力手段として機能させるデータ構造抽出プログラム。
【０００９】
［２］複数のサポートから予め定めた閾値以上の頻度で出現するパターンを複数種類抽出する抽出手段と、
前記抽出手段が第１の閾値を用いて抽出したパターンを有するサポートの集合のそれぞれにおいて、互いに有するパターンが類似するサポートの集合のすべてに共通するサポートが存在し、当該互いに有するパターンが類似するサポートの集合において当該共通するサポート以外のサポートを有さないサポートの集合が存在しない場合、前記共通するサポートの数を第２の閾値として設定する設定手段と、
前記抽出手段が第１の閾値を用いて抽出したパターンを有するサポートの集合のそれぞれにおいて、当該互いに有するパターンが類似するサポートの集合のすべてに共通するサポートが存在し、当該互いに有するパターンが類似するサポートの集合において当該共通するサポート以外のサポートを有さないサポートの集合が存在する場合、当該共通するサポート以外のサポートを有さないサポートの集合のパターンを出力すべきパターンであると判断する出力判断手段と、
前記出力判断手段が出力すべきパターンであると判断したパターンと、前記設定手段が対象としたサポートから前記第２の閾値以上の頻度で前記抽出手段により抽出されるパターンを出力する出力手段とを有するデータ構造抽出装置。
【発明の効果】
【００１０】
請求項１又は２に係る発明によれば、本構成を採用しない場合に比べて、出現する複数のデータ構造から、類似する特徴を有するデータ構造を精度よく抽出することができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、本発明の実施の形態に係るデータ構造抽出装置の構成の一例を示す図である。
【図２】図２は、ＤＰＣデータのパターンの構成の一例を示す概略図である。
【図３】図３は、ＤＰＣデータから抽出されるパターンの構成の一例を示す概略図である。
【図４】図４は、データ構造抽出装置のパターン抽出動作を示すフローチャートである。
【図５】図５は、サポートベクトルの構成の一例を示す概略図である。
【図６】図６は、サポートベクトルの分類動作を説明するための図である。
【図７】図７（ａ）〜（ｃ）は、サポートベクトル分類手段がマッピングした表及び出力手段１０７が出力する出力内容の一例を示す概略図である。
【図８】図８（ａ）〜（ｃ）は、サポートベクトル分類手段がマッピングした表及び出力手段１０７が出力する出力内容の一例を示す概略図である。
【図９】図９は、データ構造抽出装置の動作例を示すフローチャートである。
【図１０】図１０は、データ構造抽出装置のパターン出力動作の一例を示すフローチャートである。
【図１１】図１１（ａ）及び（ｂ）は、データ構造抽出装置によって抽出されるパターンの一例を示す概略図である。
【発明を実施するための形態】
【００１２】
（データ構造抽出装置の構成）
図１は、本発明の実施の形態に係るデータ構造抽出装置の構成の一例を示す図である。
【００１３】
データ構造抽出装置１は、ＣＰＵ等から構成され各部を制御するとともに各種のプログラムを実行する制御部１０と、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）やフラッシュメモリ等の記憶媒体から構成され情報を記憶する記憶部１１とを備え、例えば、患者臨床情報及び診療行為の電子データの解析に用いられる。
【００１４】
制御部１０は、後述するデータ構造抽出プログラム１１０を実行することで、パターン抽出手段１００、サポートベクトル生成手段１０１、サポートベクトル分類手段１０２、共通サポート計算手段１０３、閾値設定手段１０４、パターン再抽出手段１０５、出力判断手段１０６及び出力手段１０７等として機能する。
【００１５】
パターン抽出手段１００は、抽出手段の一例であり、解析対象である電子データとして記憶部１１から後述するＤＰＣデータ１１１に含まれる複数の比較対象のデータ（以下、「サポート」という。）からデータ構造の一例として、対象として患者名を根ノードとした見本のツリー構造（以下、「パターン」という。）を複数取得する。ここで、パターンとは、パターン抽出技法を用いて、ツリー構造を有する複数のデータに予め定めた頻度（第１の閾値）で出現する共通のツリー構造として抽出されるもののことをいう。
【００１６】
なお、パターン抽出手段１００は、周知のパターン抽出技法を用いることで、複数のサポート間で後述するＥファイル及びＦファイルが共通したものをパターンとして抽出する。周知のパターン抽出技法として、例えば、シーケンシャル・パターン・マイニングのＰｒｅｆｉｘ  Ｓｐａｎ、ＢＩＤＥ、ＣｌｏＳｐａｎ等又はサブツリーマイニング等を用いることができる。
【００１７】
サポートベクトル生成手段１０１は、パターン抽出手段１００が抽出したパターン毎にサポートの集合をベクトル化し、後述するサポートベクトルを生成する。
【００１８】
サポートベクトル分類手段１０２は、サポートベクトル生成手段１０１が生成したサポートベクトル間の相関係数を計算し、この相関関数に基づいてサポートベクトルを複数のグループに分類する。
【００１９】
共通サポート計算手段１０３は、サポートベクトル分類手段１０２が分類したグループに属するパターン間に共通するサポートの数を計算する。
【００２０】
閾値設定手段１０４は、同じサポートベクトルのグループに属するパターン間に共通するサポートの集合が存在し、パターンのそれぞれに共通するサポート以外の他のサポートが存在する場合、共通するサポートの集合に含まれるサポートの数を第２の閾値として設定する。
【００２１】
パターン再抽出手段１０５は、抽出手段の他の一例であり、閾値設定手段１０４が設定した第２の閾値に基づいてパターン抽出手段１００が抽出しなかったパターンを抽出する。なお、パターン再抽出手段１０５を用いる代わりにパターン抽出手段１００により第２の閾値に基づいてパターンを抽出するものであってもよい。
【００２２】
出力判断手段１０６は、同じサポートベクトルのグループに属するパターン間に共通するサポートの集合が存在し、一方のパターンに共通するサポート以外の他のサポートが存在する場合、当該一方のパターンを出力しないと判断する。
【００２３】
出力手段１０７は、パターン抽出手段１００が抽出したパターンから出力判断手段１０６が出力しないと判断したパターンを削除し、パターン再抽出手段が抽出したパターンを加えて、パターン抽出結果として出力する。
【００２４】
記憶部１１は、制御部１０を上述した各手段として動作させるデータ構造抽出プログラム１１０、ＤＰＣデータ１１１及び閾値情報１１２等を記憶する。
【００２５】
ＤＰＣデータ１１１は、分析可能な全国統一形式の患者臨床情報及び診療行為の電子データセットである。患者臨床情報は、例えば、患者基本情報、病名、術式、各種のスコア・ステージ分類等であり、診療行為情報は、診療行為、医薬品、医療材料、実施日、回数・数量、診療科、病棟、保険種別等である。
【００２６】
また、ＤＰＣデータ１１１は、基本となるデータとして様式１、Ｅファイル及びＦファイルと呼ばれるデータを有する。様式１とは、患者の臨床情報、傷病名、術式、補助治療等である。Ｅファイルとは、実施日、回数、診療科、病棟、オーダ医師等の情報である。Ｆファイルとは、Ｅファイルの詳細な内容であり、例えば、行為、薬剤、材料、数量等の情報である。
【００２７】
本実施の形態では、患者を根ノードとし、その患者に属する日時データ及びＥファイルを内部ノード、Ｅファイルに属するＦファイルを葉ノードとして構成されるツリー構造をサポートとし、複数のサポートに予め定めた頻度以上で現れるサポートのデータ構造をパターンとして取得して、取得されたパターン間で類似度を算出し、算出された類似度に基づいて複数のパターンの集合を抽出する。
【００２８】
閾値情報１１２は、パターン抽出手段１００が用いる予め定められた第１の閾値と、閾値設定手段１０４が設定した第２の閾値とを格納する。
【００２９】
図２は、パターン抽出手段１００のパターンの取得元となるＤＰＣデータ１１１のサポートの構成の一例を示す概略図である。
【００３０】
ＤＰＣデータ１１１から取得される複数のサポート２００ａ、２００ｂ…は、患者に属する日時データ２２と、日時データ２２に属するＥファイル２１と、Ｅファイル２１に属するＦファイルとを有し、ツリー構造を構成する。
【００３１】
図３は、ＤＰＣデータ１１１から抽出されるパターンの構成の一例を示す概略図である。
【００３２】
ＤＰＣデータ１１１から抽出されるパターン２ａ及びパターン２ｂは、患者に属する日時データ２２と、日時データ２２に属するＥファイル２１と、Ｅファイル２１に属するＦファイルとを有し、ツリー構造を構成する。
【００３３】
（データ構造抽出装置の動作）
以下に、データ構造抽出装置の動作例を各図を参照しつつ、（１）パターン抽出動作、（２）サポート分類動作、（３）パターン出力動作に分けて説明する。
【００３４】
図９は、データ構造抽出装置の動作例を示すフローチャートである。
【００３５】
（１）パターン抽出動作
まず、パターン抽出手段１００は、記憶部１１のＤＰＣデータ１１１からパターンを抽出する対象となる複数のサポートを取得する（Ｓ１）。
【００３６】
図４は、データ構造抽出装置のパターン抽出動作を示すフローチャートである。
【００３７】
以下、説明を簡単にするため、図４に示すように簡略表示した６つのサポート２００Ａ〜２００Ｆを取得した場合について説明する。
【００３８】
パターン抽出手段１００は、サポート２００Ａ〜２００ＤからＥファイル２１ａ及び２１ｂを含むパターン２１を抽出し、サポート２００Ｂ、２００Ｅ及び２００ＦからＥファイル２１ｃ及びＦファイル２０ｃを含むパターン２２を抽出する。
【００３９】
（２）サポート分類動作
次に、サポートベクトル生成手段１０１は、パターン抽出手段１００が抽出したパターン２１及び２２のそれぞれについてサポートの集合をベクトル化してサポートベクトルを生成する（Ｓ４）。
【００４０】
図５は、サポートベクトルの構成の一例を示す概略図である。
【００４１】
サポートベクトルＳＶ１は、パターン２１についてのサポートベクトルであり、サポート２００Ａ、２００Ｂ…の順でベクトルの成分が記載されている。例えば、サポート２００Ａはパターン２１を含むためベクトル成分は「１」であり、サポート２００Ｆはパターン２１を含まないためベクトル成分は「０」である。サポートベクトルＳＶ２も同様に記載される。
【００４２】
次に、サポートベクトル分類手段１０２は、サポートベクトル間の相関係数として内積を算出する（Ｓ４）。サポートベクトルＳＶ１とＳＶ２との内積は、１／√６となる。
【００４３】
次に、サポートベクトル分類手段１０２は、サポートベクトルを以下に説明するようにクラスタリング（分類）する（Ｓ５）。以下に説明する例では、ステップＳ１においてサポートが７つ抽出され、７つのサポートそれぞれについてサポートベクトルＳＶ１〜ＳＶ７が生成され、サポートベクトルＳＶ１〜ＳＶ７間の内積が計算されたものとする。
【００４４】
図６は、サポートベクトルの分類動作を説明するための図である。
【００４５】
図６に示すように、サポートベクトル分類手段１０２は、それぞれの内積で行列を生成する。内積の値の大きなものがサポートベクトルに対応したパターンが類似していることを示す。そこで、サポートベクトル分類手段１０２は、内積の値に応じてサポートベクトルをクラスタリングし、サポートベクトルＳＶ１〜ＳＶ５のクラスター１と、サポートベクトルＳＶ６及びＳＶ７のクラスター２とに分類する。
【００４６】
次に、サポートベクトル分類手段１０２は、分類したサポートグループをパターンで表上にマッピングする。マッピングの結果を以下に示す。
【００４７】
（３）パターン出力動作
図１０は、データ構造抽出装置のパターン出力動作の一例を示すフローチャートである。また、図７（ａ）〜（ｃ）は、サポートベクトル分類手段がマッピングした表及び出力手段１０７が出力する出力内容の一例を示す概略図である。
【００４８】
まず、共通サポート計算手段１０３は、クラスタリングされたサポートグループ間の共通サポート数を計算する（Ｓ１１）。図７（ａ）に示すようにマッピングされた例において、「サポートグループ１」のサポートを概略化して図示すると図７（ｂ）に示すようになるが、各パターン１〜５において共通するサポートの数、ここでは「８」を共通サポート数として計算する。
【００４９】
次に、「サポートグループ１」のように各パターンに共通サポート以外のサポートを含む場合（Ｓ１２；Ｙｅｓ）、閾値設定手段１０４は、共通サポート数を第２の閾値として閾値情報１１２を設定する（Ｓ１３）。
【００５０】
次に、パターン再抽出手段１０５は、第１の閾値より小さく第２の閾値より以上の条件で「サポートグループ１」の共通サポートに該当する「パターン８」を再抽出する（Ｓ１４）。
【００５１】
次に、「サポートグループ２」に対して上記動作を繰り返す（Ｓ１６）。「サポートグループ２」は、各パターンに共通サポート以外のサポートを含まない場合（Ｓ１２；Ｎｏ）である。
【００５２】
図８（ａ）〜（ｃ）は、サポートベクトル分類手段がマッピングした表及び出力手段１０７が出力する出力内容の一例を示す概略図である。
【００５３】
図８（ａ）に示すようにマッピングされた例において、「サポートグループ２」のサポートを概略化して図示すると図８（ｂ）に示すようになるが、出力判断手段１０６は、共通サポート以外のサポートを含む「パターン６」は、共通サポートが支配的である「パターン７」に比べて意味が薄い（重要度が低い）と判断できるため、「パターン６」を出力しないと判断する（Ｓ１５）。
【００５４】
次に、出力手段１０７は、ステップＳ１２で各パターンに共通サポート以外のサポートを含むと判断された「サポートグループ１」については、パターン抽出手段１００が抽出した「パターン１」〜「パターン５」に加え、パターン再抽出手段１０５が再抽出した「パターン８」を、図７（ｃ）に示すように「サポートグループ１」の出力内容１０７ａとして出力する（Ｓ１７）。
【００５５】
また、出力手段１０７は、ステップＳ１２で各パターンに共通サポート以外のサポートを含まないと判断された「サポートグループ２」については、出力判断手段１０６が出力しないと判断した「パターン６」を除き、「パターン７」を、図８（ｃ）に示すように「サポートグループ２」の出力内容１０７ｂとして出力する（Ｓ１７）。
【００５６】
［実施例］
図１１（ａ）及び（ｂ）は、データ構造抽出装置１によって抽出されるパターンの一例を示す概略図である。
【００５７】
図１１（ａ）に示すように、Ｅファイル２１ｇ、２１ｈ及びＦファイル２０ｇを含むパターン２３のみ有する患者のサポートが「４名」、Ｅファイル２１ｇ、２１ｈ及びＦファイル２０ｇ、２０ｈを含むパターン２３有する患者のサポートが「８名」、Ｅファイル２１ｇ及びＦファイル２０ｇ、２０ｈを含むパターン２３のみ有する患者のサポートが「４名」存在する場合を考える。
【００５８】
このとき、第１の閾値を「１２」とすると、パターン抽出手段１００は、パターン２４はパターン２３及び２５を含み、パターン２３のサポート数がパターン２３と２４のサポート数の和である「１２」であり、パターン２３のサポート数がパターン２５と２４のサポート数の和である「１２」であるため、パターン２３び２５を抽出し、サポート数が「８」であるパターン２４は抽出しない。
【００５９】
しかし、パターン２４は、パターン２３及び２５より患者の多い重要度の高いパターンであるため、抽出すべきパターンである。ここで、閾値設定手段１０４は、パターン抽出手段１００によって抽出されたパターン２３及び２５に共通サポートが存在すると判断し、第２の閾値を共通サポート数である「８」に設定する。
【００６０】
その結果、パターン再抽出手段１０５は、パターン抽出手段１００が抽出しなかった重要度の高いパターン２４を抽出する。
【００６１】
次に、図１１（ｂ）に示すように、Ｅファイル２１ｇ、２１ｈ及びＦファイル２０ｇを含むパターン２３のみ有する患者のサポートが「２名」、Ｅファイル２１ｇ、２１ｈ及びＦファイル２０ｇ、２０ｈを含むパターン２３有する患者のサポートが「１０名」存在する場合を考える。
【００６２】
このとき、第１の閾値を「９」とすると、パターン抽出手段１００は、パターン２４はパターン２３を含み、パターン２３のサポート数がパターン２３と２４のサポート数の和である「１２」であり、パターン２３のサポート数が「１０」であるため、パターン２３び２４を抽出する。
【００６３】
しかし、パターン２３は、パターン２４に比べて患者の少ない重要度の低いパターンであるため、抽出すべきでないパターンである。そこで、出力判断手段１０７は、パターン２３を出力すべきでないパターンであると判断する。
【００６４】
［他の実施の形態］
なお、本発明は、上記実施の形態に限定されず、本発明の趣旨を逸脱しない範囲で種々な変形が可能である。例えば、本発明はＤＰＣデータ１１１にのみ適用されるものではなく、木構造を代表とする任意のデータ構造を有するデータの集合であれば同様に適用することができる。
【００６５】
また、上記実施の形態で使用されるデータ構造抽出プログラム１１０は、ＣＤ−ＲＯＭ等の記憶媒体から装置内の記憶部に読み込んでも良く、インターネット等のネットワークに接続されているサーバ装置等から装置内の記憶部にダウンロードしてもよい。また、上記実施の形態で使用される手段１００〜１０７の一部または全部をＡＳＩＣ等のハードウェアによって実現してもよい。
【符号の説明】
【００６６】
１     データ構造抽出装置
１０   制御部
１１   記憶部
２０   Ｆファイル
２１   Ｅファイル
２２   日時データ
１００ パターン抽出手段
１０１ サポートベクトル生成手段
１０２ サポートベクトル分類手段
１０３ 共通サポート計算手段
１０４ 閾値設定手段
１０５ パターン再抽出手段
１０６ 出力判断手段
１０７ 出力手段
１１０ データ構造抽出プログラム
１１１ ＤＰＣデータ
１１２ 閾値情報
【図１】
0005772437.tif 000002
【図２】
0005772437.tif 000003
【図３】
0005772437.tif 000004
【図４】
0005772437.tif 000005
【図５】
0005772437.tif 000006
【図６】
0005772437.tif 000007
【図７】
0005772437.tif 000008
【図８】
0005772437.tif 000009
【図９】
0005772437.tif 000010
【図１０】
0005772437.tif 000011
【図１１】
0005772437.tif 000012