あいまい頻出集合の探索方法及び探索装置
【課題】あいまい頻出集合のパターンを完全かつ短時間に抽出する探索方法を提供する。
【解決手段】各トランザクションＴがアイテム集合Ｅの部分集合になっているデータベースＤ、アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数σ以上に対するあいまい頻出集合Ｐ０の探索方法であって、あいまい頻出集合Ｐの正規出現ＡｍｂｉＯｃｃ（Ｐ）を求める工程と、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める工程と、正規出現ＡｍｂｉＯｃｃ（Ｐ）のトランザクションから代表アイテムｅ＊（Ｐ）を除いて親と定める工程と、あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択工程とを備え、頻出パターンの各候補について、あいまい頻出集合Ｐ０に属するか否かを判断し、親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する。
【解決手段】各トランザクションＴがアイテム集合Ｅの部分集合になっているデータベースＤ、アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数σ以上に対するあいまい頻出集合Ｐ０の探索方法であって、あいまい頻出集合Ｐの正規出現ＡｍｂｉＯｃｃ（Ｐ）を求める工程と、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める工程と、正規出現ＡｍｂｉＯｃｃ（Ｐ）のトランザクションから代表アイテムｅ＊（Ｐ）を除いて親と定める工程と、あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択工程とを備え、頻出パターンの各候補について、あいまい頻出集合Ｐ０に属するか否かを判断し、親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、あいまい頻出集合の探索方法及び探索装置に関する。詳しくは、データベース内に頻繁に現れる頻出パターンを、あいまい性を許して完全かつ短時間に抽出できる探索方法及び探索装置に関する。
【背景技術】
【０００２】
データベース内に頻繁に現れる頻出パターンを抽出する問題は、情報科学の基本問題である。データベースのデータ及びパターンとして、トランザクション、ツリー、グラフ、多次元ベクトル等が、データ及びパターンの要素として、アイテム、部分集合、木、パス・サイクル、グラフ、図形等が挙げられる。特に、データベースＤのデータがアイテム集合Ｅの部分集合であるトランザクションＴである場合に、頻出パターンを全て抽出する問題は頻出パターン列挙問題と云われている。この場合、完全一致検索の問題であれば容易に解決できる。他方、あいまい性を許して多くのデータに含まれるパターンを抽出するあいまい検索は、ゲノムの相同検索等で大いに実用的である。しかし、完全一致検索の問題からこのようなあいまい検索の問題になると、とたんに難しくなる。
【０００３】
アイテム集合Ｅに対して、あいまいな包含関係を考え、頻出集合を列挙するアルゴリズムに関して、従来の解決方法は、包含率の閾値θを定め、全てのデータを照合するか、ヒューリステックな検索をして、多数ではあるが不完全な頻出集合を抽出するかのどちらかであった。（非特許文献１〜３参照）
【０００４】
【非特許文献１】Ｃ．Ｙａｎｇ，Ｕ．Ｆａｙｙａｄ，Ｐ．Ｓ．Ｂｒａｄｌｅｙ，“Ｅｆｆｉｃｉｅｎｔ Ｄｉｓｃｏｖｅｒｙ ｏｆ Ｅｒｒｏｒ−Ｔｏｌｅｒａｎｔ Ｆｒｅｑｕｅｎｔ Ｉｔｅｍｓｅｔｓ ｉｎ Ｈｉｇｈ Ｄｉｍｅｎｓｉｏｎｓ”，ＳＩＧＫＤＤ２００１，２００１．
【非特許文献２】Ｊ．Ｂｅｓｓｏｎ，Ｃ．Ｒｏｂａｒｄｅｔ，ａｎｄ Ｊ．Ｆ．Ｂｏｕｌｉｃａｕｔ，“Ｍｉｎｉｎｇ Ｆｏｒｍａｌ Ｃｏｎｃｅｐｔｓ ｗｉｔｈ ａ Ｂｏｕｎｄｅｄ Ｎｕｍｂｅｒ ｏｆ Ｅｘｃｅｐｔｉｏｎｓ ｆｒｏｍ Ｔｒａｎｓａｃｔｉｏｎａｌ Ｄａｔａ”，ＫＤＩＤ ２００４，ＬＮＣＳ ３３７７，ｐｐ．３３−４５，２００５．
【非特許文献３】Ｗ．Ｓｈｅｎ−Ｓｈｕｎｇ ａｎｄ Ｌ．Ｓｕｈ−Ｙｉｎ，“Ｍｉｎｉｎｇ Ｆａｕｌｔ−Ｔｏｌｅｒａｎｔ Ｆｒｅｑｕｅｎｔ Ｐａｔｔｅｒｎｓ ｉｎＬａｒｇｅ Ｄａｔａｂａｓｅｓ”，ＩＣＳ２００２，２００２．
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、全てのデータを照合する方法は小さいデータベースでは完全抽出できるが、大きいデータベースでは非実用的であった。また、ヒューリステックな検索でも、全てのパターンを完全に抽出できるアルゴリズムは見出されていない。
【０００６】
本発明は、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索方法及び探索装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明の第１の態様によるあいまい頻出集合の探索方法は、例えば、図３に示すように、データベースＤ内に頻繁に現れる頻出パターンＰを、あいまい性を許容して抽出するあいまい頻出集合の探索方法であって、データベースＤのデータが、アイテムｅからなるアイテム集合Ｅの部分集合であるトランザクションＴからなるデータベースＤであり、頻出パターンＰが、構成アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数（最大共起数）が閾値σ以上を条件とするあいまい頻出集合Ｐ０のパターンであり、頻出パターンＰについて、データベースＤのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算工程（Ｓ２０〜Ｓ５０）と、頻出パターンＰの構成アイテムｅのうち、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定工程（Ｓ６０）と、頻出パターンＰから代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定工程（Ｓ７０〜Ｓ９０）と、あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択工程（Ｓ１０，Ｓ１００）とを備え、パターン選択工程（Ｓ１０，Ｓ１００）で選択された各候補について、正規出現演算工程（Ｓ２０〜Ｓ５０）を用いてあいまい頻出集合Ｐ０に属するか否かを判断し、当該候補があいまい頻出集合Ｐ０に属する場合には、代表選定工程（Ｓ６０）及び親選定工程（Ｓ７０〜Ｓ９０）を用いて親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する。
【０００８】
ここにおいて、あいまい性の程度は、平均包含率の閾値θ及び頻出度数（最大共起数）の閾値σにより枠決めされる。また、アイテムｅは明細書中では説明の便宜上、数字としたが、文字、記号でも良く識別符号で対応可能であれば何でも良い。例えば、商品、コンテンツ、サンプルでも良い。また、包含率とは、パターンＰを構成するアイテムｅの総数のうち、データに含まれるアイテム数の割合をいい、平均包含率θｐとは、複数のデータについて包含率を平均化したものをいう。また、最大共起数σｐとは、平均包含率が閾値θ以上となるように選択された最大のデータ数をいう。この態様のように構成すると、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索方法を提供できる。
【０００９】
また、本発明の第２の態様によるあいまい頻出集合の探索方法は、第１の態様において、パターン選択工程において、深さ優先探索を用いる。このように構成すると、親の正規出現から子供の正規出現を導き出せることを利用して、効率的に探索ができる。
【００１０】
また、本発明の第３の態様によるあいまい頻出集合の探索方法は、第１の態様において、アイテムが商品、コンテンツ、サンプル、その他識別符号で対応付けられたもののいずれかである。このように構成すると、商品販売データ、実験データの解析等に役立てられる。
【００１１】
上記課題を解決するために、本発明の第４の態様によるあいまい頻出集合の探索装置１００は、例えば、図５に示すように、データベースＤ内に頻繁に現れる頻出パターンＰを、あいまい性を許容して抽出するあいまい頻出集合の探索装置であって、データベースＤのデータが、アイテムからなるアイテム集合Ｅの部分集合であるトランザクションＴからなるデータベースＤであり、頻出パターンＰが、構成アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数（最大共起数）が閾値σ以上を条件とするあいまい頻出集合Ｐ０のパターンであり、頻出パターンＰについて、データベースＤのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算手段Ｍ１と、頻出パターンＰの構成アイテムｅのうち、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定手段Ｍ２と、頻出パターンＰから代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定手段Ｍ３と、あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択手段Ｍ４とを備え、パターン選択手段Ｍ４で選択された各候補について、正規出現演算手段Ｍ１を用いてあいまい頻出集合Ｐ０に属するか否かを判断し、当該候補があいまい頻出集合Ｐ０に属する場合には、代表選定手段Ｍ２及び親選定手段Ｍ３を用いて親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する。
【００１２】
ここにおいて、解決装置１００はデータベースＤを有しても良いが、有さなくてもアクセス可能であれば良い。また、各手段は１つのコンピュータＣ内に構成されても良く、それぞれ、別のコンピュータで構成されても良い。また、１つのコンピュータＣ内に構成される場合に、各手段毎に別個のハードウエアに構成されても良いが、１つのコンピュータＣが各手段の機能を有するならば、各手段がコンピュータ内に構成されているとみなして良い。この態様のように構成すると、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索装置を提供できる。
【発明の効果】
【００１３】
本発明によれば、あいまい頻出集合のパターンを完全かつ短時間に抽出できる探索方法及び探索装置を提供できる。
【発明を実施するための最良の形態】
【００１４】
［頻出集合について］
まず、頻出集合について説明する。アイテム集合Ｅはアイテムｅ＝１，２・・・ｎの組み合わせからなる集合であり、データベースＤはアイテム集合Ｅの部分集合であるトランザクションＴの集合からなるものとする。データベースＤが有するトランザクション数を｜Ｄ｜、トランザクションＴが有するアイテム数を｜Ｔ｜とする（同様に｜ ｜は数を表すものとする）。データベースサイズを‖Ｄ‖＝｜Ｄ｜＋ΣＴ∈Ｄ｜Ｔ｜と定義する。すなわち、データベースＤが有するトランザクション数と各トランザクションが有するアイテム数の総和である。データベースサイズ‖Ｄ‖はコンピュータ計算時間を求めるために用いられる。ここで、アイテム集合Ｅの部分集合であるパターンＰ（トランザクション）に注目する。データベースＤ内でパターンＰが出現するものの集合を出現集合Ｏｃｃ（Ｐ）、パターンＰの出現頻度をｆｒｑ（Ｐ）（＝｜Ｏｃｃ（Ｐ）｜）とする。また、データベースＤ内でパターンＰのアイテムをｈ個含まないものの集合をＯｃｃ＝ｈ（Ｐ）＝｛Ｔ｜Ｔ∈Ｄ，｜Ｐ＼Ｔ｜＝ｈ｝（Ｐ＼ＴはＰとＴの差異を示す）、ｈ個以下含まないものの集合をＯｃｃ≦ｈ（Ｐ）＝｛Ｔ｜Ｔ∈Ｄ，｜Ｐ＼Ｔ｜≦ｈ｝とする。データベースＤ内に、出現頻度が閾値σ以上出現するパターンの集合を頻出集合という。この閾値σをミニマムサポート（最小頻度）という。データベースＤと閾値σが与えられた時に、頻出集合の全ての解を求める問題を頻出集合列挙問題という。
【００１５】
図１にｋ擬似頻出集合の例を示す。データベースＤのデータがアイテム集合Ｅ（アイテムｅ）の部分集合からなるトランザクションＴであり、図の左側に示すような６データを有しているものとする。ｋ擬似頻出集合とは、データベースＤ内のσ個以上のデータ（トランザクション）にｋ擬似包含の意味で含まれる（ｋ個以下の異なるアイテムがあっても良いことを意味する）アイテム集合であって、図の右側にσ＝３、ｋ＝１での擬似頻出集合の例を示す。例えば、パターン｛１，２，３｝について、データ｛１，２，５，６，７，９｝及び｛１，２，７，８，９｝はアイテム１と２を含み、３を含まない。データ｛２，３，４，５｝はアイテム２と３を含み、１を含まない。このように、３個のアイテム中、ｋ＝１個以下のアイテムが異なるデータが３個、すなわち、閾値σ＝３以上ある。また、パターン｛１，２，７，９｝ついて、データ｛１，２，５，６，７，９｝及び｛１，２，７，８，９｝は全てのアイテムを含む。データ｛１，７，９｝及び｛２，７，９｝は３個のアイテムを含み、１個のアイテムを含まない。このように、４個のアイテム中、ｋ＝１個以下のアイテムが異なるデータが４個、すなわち、閾値σ＝３以上ある。このようなパターン（トランザクション）は図に示すように３個のアイテムを有するものが３３個、４個のアイテムを有するものが１１個ある。
【００１６】
ｋ擬似頻出集合を含め、頻出集合列挙問題の解を全て列挙するのは容易である。その理由は、単調性が保持されているので（解の任意の部分集合も解になっているので）、任意の頻出集合は、頻出集合の域内で、空集合に順次アイテムを付加することによって得ることができるからである。親のパターン（トランザクション）にアイテムｅを１つ付加したものを子供のパターン（トランザクション）という。空集合以外の頻出集合の任意のパターンは親を持つので、この親子関係は頻出集合の全てのパターンを関係付ける列挙木を導き出す。列挙木を探索することにより、頻出集合の全ての解を見つけることができる。ただし、各親について可能な子供を全て探索すると子供のトランザクションに重複が生じるが、唯一の親を選択してアイテムを付加するような秩序を導入することにより重複を避けられる。単調性が保持されていれば、分岐限定法的なアプローチを用いることができる。すなわち、どのアイテムを加えるかで場合分けを繰り返すことにより、簡単に重複を回避しつつ解を列挙できる。
【００１７】
［あいまい頻出集合について］
次に、あいまい頻出集合Ｐ０について説明する。パターンＰのアイテムｅのうちトランザクションＴに含まれるアイテムの割合を包含率といい、（｜Ｔ∩Ｐ｜／｜Ｔ｜）（Ｔ∩ＰはＴとＰが共有するアイテムを示す）で示される。次に、パターンＰのアイテムのうちトランザクションＴの集合Ｔ０に含まれる平均包含率θｐを考える。平均包含率θｐは集合Ｔ０に含まれる各トランザクションＴに対する包含率を平均したもの（ΣＴ∈Ｔ０｜Ｔ∩Ｐ｜）／（｜Ｔ｜｜Ｐ｜）である。平均包含率θｐが閾値（密度閾値）θ以上となる最大数のトランザクションの集合をＰの最大共起集合という。その集合に含まれるトランザクションの数をＰの最大共起数といい、σｐ＝ｃｏｖ（Ｐ）で表す。トランザクションデータベースＤ，最大共起数ｃｏｖ（Ｐ）が閾値（ミニマムサポート）σ以上、平均包含率θｐが閾値（密度閾値）θ以上のあいまい頻出集合Ｐ０の全ての解を求める問題を、あいまい頻出集合列挙問題という。すなわち、あいまい頻出集合列挙問題とは、与えられたトランザクションデータベースＤ、密度閾値θ、ミニマムサポート（最小頻度）σに対し、データベースＤに対するあいまい頻出集合Ｐ０の解（パターンＰ）を全て出力する問題をいう。
【００１８】
図２にあいまい頻出集合Ｐ０の例を示す。データベースＤのデータがアイテム集合Ｅの部分集合からなるトランザクションＴであり、図の左側に示すような３データを有しているものとする。例えば、パターン（トランザクション）｛２，３｝については、データ｛１，３，４｝には２が無く３が有るので、包含率５０％、データ｛２，４，５｝及び｛１，２｝には２が有り３が無いので、包含率５０％であり、これらの平均包含率θｐは５０％である。パターン｛４，５｝については、データ｛１，３，４｝には４が有り５が無いので、包含率５０％、データ｛２，４，５｝には４及び５が有るので、包含率１００％、データ｛１，２｝には４及び５が無いので、包含率０％であり、これらの平均包含率θｐは５０％である。パターン｛１，２｝については、データ｛１，３，４｝には１が有り２が無いので、包含率５０％、データ｛２，４，５｝には１が無く２が有るので、包含率５０％、データ｛１，２｝には１及び２が有るので、包含率１００％であり、これらの平均包含率θｐは６６％である。ここで、平均包含率の閾値θ＝５０％を条件とすれば、３個のデータが該当し、閾値θを６６％を条件とすれば、１個のデータ｛１，２｝が該当する。また、以上の平均包含率θｐについては３個のデータの平均包含率をとっているので、最大共起数は閾値σ＝３を満たす。もし、最大共起数の閾値σ＝２とすれば、パターン｛４，５｝に対しては、データ｛１，３，４｝及びデータ｛２，４，５｝を選択でき、平均包含率θｐ＝７５％となる。もし、平均包含率の閾値（密度閾値）θ＝６６％、最大共起数の閾値（ミニマムサポート）σ＝３を条件とすると、データベースＤに対するあいまい頻出集合として図中の３つのパターンのうちではパターン｛１，２｝のみが該当する。なお、図示しないが、パターン｛１｝や｛２｝などもあいまい頻出集合Ｐ０に該当する。この例ではデータが少ないので、あいまい頻出集合Ｐ０の解を全て列挙するのは容易である。
【００１９】
任意の頻出集合は、単調性が保持されていれば、頻出集合の域内で、空集合に順次アイテムを付加することによって得ることができる。しかしながら、あいまい頻出集合Ｐ０は単調性を保持しないので、分岐限定法的なアプローチを適用できそうにない。また、あいまい頻出集合が存在するか否かの判定はＮＰ完全と呼ばれる難しい問題に属する。そこで、多項式遅延多項式空間の逆探索アルゴリズムを用いる。この場合、各頻出集合のコンピュータ計算時間はデータベースサイズ‖Ｄ‖に比例し、Ｏ（‖Ｄ‖）と表される。
【００２０】
多項式遅延多項式空間のアルゴリズムとは次ぎのようなアルコリズムをいう。もし、アルゴリズムの計算時間が、解の数の線形であるならば、不要な計算をあまりしていないと考えられるため、実用的に優れている。また、アルゴリズムのメモリ使用量が入力サイズの多項式であるなら、解が多量であってもメモリ不足を起こすことがない。本発明では、あいまい頻出集合列挙問題を解決する、このような、解の数に線形の時間で動き、入力の多項式サイズのメモリしか消費しない多項式遅延多項式空間のアルゴリズムを使用する。
【００２１】
［第１の実施の形態］
第１の実施の形態では、あいまい頻出集合Ｐ０の解を全て列挙できるアルゴリズムとして、擬似頻出集合の多項式遅延多項式空間アルゴリズムを用いて、逆探索的アプローチを行うこととする。
【００２２】
あいまい頻出集合Ｐ０に属するパターンＰの最大共起集合のうち、辞書順最小のものをあいまい頻出集合Ｐの正規出現ＡｍｂｉＯｃｃ（Ｐ）と定義する。すなわち、あいまい頻出集合Ｐ０に属するパターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）はデータベースＤに含まれるトランザクションＴを包含率の大きいものから順次選択し、同率のものがあれば、ＩＤ（識別符号）の小さいほうを優先して並べることによって得られる。そして、空集合以外（Ｐ≠０）のパターンＰに含まれるアイテムｅのうち、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数｜ＡｍｂｉＯｃｃ（Ｐ）∩Ｏｃｃ（｛ｅ｝）｜が最小のアイテムを代表ｅ＊（Ｐ）と定義する。すなわち、密度が一番小さいアイテムを除くことにより親子関係を定める。代表ｅ＊（Ｐ）を用いることにより、あいまい頻出集合Ｐ０に明確な探索ルートを決めることができる。
【００２３】
定理１． Ｐ≠０の任意のアイテム集合のパターンＰに対して、ｃｏｖ（Ｐ＼｛ｅ｝）（Ｐからｅを除いたものの最大共起数）≧ｃｏｖ（Ｐ）（Ｐの最大共起数）を満たすアイテムｅ∈Ｐが存在する。
【００２４】
証明： あいまい頻出集合のパターンＰに対する正規出現ＡｍｂｉＯｃｃ（Ｐ）の平均包含率は、Σｅ∈Ｐ｜ＡｍｂｉＯｃｃ（Ｐ）∩Ｏｃｃ（｛ｅ｝）｜／［（Ｐ−１）×｜ＡｍｂｉＯｃｃ（Ｐ）｜］なので、｜ＡｍｂｉＯｃｃ（Ｐ）∩Ｏｃｃ（｛ｅ｝）｜／｜ＡｍｂｉＯｃｃ（Ｐ）｜の平均値で与えられる。親Ｐ＼｛ｅ＊（Ｐ）｝に対するＡｍｂｉＯｃｃ（Ｐ）の平均包含率は、Ｐ＼｛ｅ＊（Ｐ）｝の中の｜ＡｍｂｉＯｃｃ（Ｐ）∩Ｏｃｃ（｛ｅ｝）｜／｜ＡｍｂｉＯｃｃ（Ｐ）｜の平均値であり、Ｐに対するＡｍｂｉＯｃｃ（Ｐ）の平均包含率以上である。このことは、ｃｏｖ（Ｐ＼｛ｅ｝）はｃｏｖ（Ｐ）以上であり、代表ｅ＊（Ｐ）が主題のアイテムｅであるという条件を満たす。
【００２５】
また、Ｐ≠０のアイテム集合のパターンＰに対して、Ｐの親をＰｒｔ（Ｐ）＝Ｐ＼｛ｅ＊（Ｐ）｝（Ｐから代表を除いたもの）と定める。すなわち、親は子から代表ｅ＊（Ｐ）を除いたものをいう。定理１より、Ｐ＼｛ｅ＊（Ｐ）｝もまたあいまい頻出集合に属する。特に、ｃｏｖ（Ｐｒｔ（Ｐ））≦ｃｏｖ（Ｐ）が成り立つ。親Ｐｒｔ（Ｐ）は子供Ｐに比して含むアイテムｅが１つ少なく、このようにして導入された親子関係はあいまい頻出集合の各パターンに対して１つの親が対応し、親子関係が一意的に定まる。空集合以外の任意の頻出集合は親を持つので、この親子関係はあいまい頻出集合の全てのパターンを関係付ける列挙木を導き出す。そして、列挙木を探索することにより、重複なしにあいまい頻出集合の全ての解（パターン）を見つけることができる。列挙木に深さ優先探索を行ない、見つけた子供に対し再帰的に子供を見つけることにより、メモリを付加すること無く、探索を実行できる。
【００２６】
あいまい頻出集合のパターンＰに対する逆探索アルゴリズムは次のようになる。
（１）パターンＰを出力する。
（２）Ｐに含まれない各アイテムｅに対して
（２ａ）もしＰにｅを付加したものＰ∩｛ｅ｝があいまい頻出集合に属するのであれば、
（２ｂ）もしその親Ｐｒｔ｛Ｐ∩｛ｅ｝｝＝Ｐであれば、
（２ｃ）｛Ｐ∩｛ｅ｝｝を逆探索する。
【００２７】
（２ａ）と（２ｂ）における平均包含率とＰにｅを付加したものＰ∩｛ｅ｝の親を求める計算は時間Ｏ（‖Ｄ‖）でなされる。繰り返しは高々ｎ倍（任意のパターンの子供の数は高々ｎ）であり、あいまい頻出集合のコンピュータ計算時間はＯ（‖Ｄ‖×ｎ）でなされる。また、列挙木の深さは高々ｎであり、次の定理が導かれる。
【００２８】
定理２．与えられたトランザクションデータベースＤ、ミニマムサポートの閾値σ、平均包含率の閾値θに対して、任意のあいまい頻出集合は、１つの集合あたり‖Ｄ‖に線形のコンピュータ計算時間で、‖Ｄ‖の大きさのメモリを用いて求められる。
【００２９】
図３にあいまい頻出集合の探索方法の処理フロー例を示す。全体のフローをあいまい頻出集合の探索工程として示す。あいまい頻出集合の探索工程は、頻出パターンＰについて、データベースＤのデータから、あいまい頻出集合の条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算工程と、頻出パターンＰの構成アイテムｅのうち、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定工程と、頻出パターンＰから代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定工程と、あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択工程とを備える。
【００３０】
まず、あいまい頻出集合Ｐ０の候補としてパターンＰ１を選択する（Ｓ１０）。これはパターン選択工程に属する。パターンＰ１の選択は空集合φから、アイテムｅを１つずつ付加していき、あいまい頻出集合Ｐ０に属するか否かを判断していく。子供があいまい頻出集合に属するのであれば、さらにその子供について探索する深さ優先探索を行なうと効率的である。すなわち、パターンＰ１を選択したら、次に、アイテムｅを選択して（Ｓ２０）パターンＰ１に付加して子供のパターンＰ２を作成し（Ｓ３０）、子供Ｐ２＝Ｐ∩｛ｅ｝があいまい頻出集合に属するか否かを判断する（Ｓ４０）。
【００３１】
図４に、パターンがあいまい頻出集合に属するか否かを判断する工程（Ｓ４０）を示す。あいまい頻出集合Ｐ０の候補パターンＰ２に対して（Ｓ４１）、まず、データベースＤのデータを包含率の高い順に並べる（Ｓ４２）。次に、平均包含率θｐが閾値（密度閾値）θ以上の範囲で、包含率の高い順にデータを取得し、データ数が最大になるように取得して集合を形成する（Ｓ４３）。包含率が同じデータについては辞書順最小のものから選択する。次に、取得した集合のデータ数、すなわち最大共起数（頻出度数）σｐが閾値σ（ミニマムサポート）以上か否かを判断する（Ｓ４４）。取得した集合のデータ数が閾値σ以上であれば、子供Ｐ２＝Ｐ１∩｛ｅ｝があいまい頻出集合Ｐ０に属すると判断し（Ｓ４５）、閾値σ以上でなければ、子供Ｐ２＝Ｐ１∩｛ｅ｝があいまい頻出集合Ｐ０に属さないと判断する（Ｓ４６）。
【００３２】
ここで、図３に戻る。子供Ｐ２があいまい頻出集合Ｐ０に属さない場合（Ｓ４０でＮ）は、ステップＳ２０に戻り、あいまい頻出集合Ｐ０の候補Ｐ１に対して次のアイテムｅを選択する。子供Ｐ２があいまい頻出集合Ｐ０に属する場合（Ｓ４０でＹ）は、取得した集合がパターンＰ２の正規出現ＡｍｂｉＯｃｃ（Ｐ２）として求まる（Ｓ５０）。アイテムｅ選択から正規出現ＡｍｂｉＯｃｃ（Ｐ２）を求めるまでの工程（Ｓ１０〜Ｓ５０）は正規出現演算工程に属する。
【００３３】
次に子供Ｐ２＝Ｐ１∩｛ｅ｝について代表ｅ＊（Ｐ２）を求める（Ｓ６０）。これは代表選定工程に属する。子供Ｐ２＝Ｐ１∩｛ｅ｝のアイテムのうち、パターンＰ２の正規出現ＡｍｂｉＯｃｃ（Ｐ２）に含まれる数が最小のものを代表ｅ＊（Ｐ２）として選定する。次に、子供Ｐ２＝Ｐ１∩｛ｅ｝の親Ｐｒｅ（Ｐ２）を求める（Ｓ７０）。パターンＰ２から代表ｅ＊（Ｐ２）を除くことにより親Ｐｒｅ（Ｐ２）＝Ｐ２＼｛ｅ＊（Ｐ２）｝を求める。次に、求めた親Ｐｒｅ（Ｐ２）がＰ１であるか否かを判断する（Ｓ８０）。Ｐ１であれば（Ｓ８０でＹ）、求めた親Ｐｒｅ（Ｐ２）が真の親であり、親子関係が決まる（Ｓ９０）。Ｐ１でなければ（Ｓ８０でＮ）、求めた親Ｐｒｅ（Ｐ２）が真の親ではなく、ステップＳ２０に戻り、次のアイテムｅを選択する。親Ｐｒｅ（Ｐ）の演算から親子関係が決まるまでの工程（Ｓ７０〜Ｓ９０）は親選定工程に属する。
【００３４】
親子関係が定まれば、次のパターンを選択して探索を行う（Ｓ１００でＳ１０に戻る）。これはパターン選択工程に属する。子供があいまい頻出集合Ｐ０に属するのであれば、さらにその子供について再帰的に探索する。子供があいまい頻出集合Ｐ０に属するのでなければ、親に戻って、次のアイテムｅを選択し、探索する。すべてのアイテムｅについて探索が終了したら、さらに上位の親に戻って探索を行う。すなわち、次の候補パターンＰがあれば（Ｓ１００でＹ、Ｓ１０に戻る）、その候補についてあいまい頻出集合Ｐ０に属するか否かを判断し、全てのあいまい頻出集合Ｐ０の候補パターンがなくなる（Ｓ１００でＮ）まで探索を行う。
【００３５】
図５にあいまい頻出集合の探索装置の構成例を示す。あいまい頻出集合の探索装置１００は、コンピュータ（演算手段）Ｃ、データベースＤ、メモリＭを備える。コンピュータＣは頻出パターン探索手段Ｍ０を有する。頻出パターン探索手段Ｍ０は、例えば、あいまい頻出集合の探索方法のプログラムをコンピュータＣにインストールすることにより実現できる。なお、ハードウエアで実現しても良い。頻出パターン探索手段Ｍ０は、正規出現演算手段Ｍ１、代表選定手段Ｍ２、親選定手段Ｍ３、パターン選択手段Ｍ４を有する。正規出現演算手段Ｍ１は正規出現演算工程（Ｓ１０〜Ｓ５０）を実行し、代表選定手段Ｍ２は代表選定工程（Ｓ６０）を実行し、親選定手段Ｍ３は親選定工程（Ｓ７０〜Ｓ９０）を実行し、パターン選択手段Ｍ４はパターン選択工程（Ｓ１０、Ｓ１００）を実行する。この構成により、あいまい頻出集合を完全かつ短時間に抽出できる探索装置を提供できる。
【００３６】
図６に、あいまい頻出集合の正規出現ＡｍｂｉＯｃｃ（Ｐ）の例を示す。データベースＤのデータＡ〜Ｆを左側に示す。平均包含率θｐの閾値（密度閾値）θ＝６６％、最大共起数（頻出度数）σｐの閾値（ミニマムサポート）σ＝４とする。トランザクション（パターン）｛１，４，５｝について、アイテム１，４，５の全てを含むデータ（包含率１００％）はＤ、１個含まないデータ（包含率６６％）はＡ，Ｂ、２個含まないデータ（包含率３３％）はＣ，Ｆ、全て含まれないデータ（包含率０％）はＥであり、４グループに分かれる。これらを包含率の高いものから４とると、ＡｍｂｉＯｃｃ（｛１，４，５｝）＝｛Ｄ，Ａ，Ｂ，Ｃ｝となり、平均包含率θｐは６６％（（１００＋６６＋６６＋３３）／４）となり、トランザクション｛１，４，５｝はあいまい頻出集合Ｐ０の１つの解であることが分かる。ＣとＦについては辞書順からＣが選択される。ここで、トランザクション（パターンＰ）｛１，４，５｝について、代表ｅ＊（Ｐ）を求める。トランザクション｛１，４，５｝のアイテム１及び４は｛Ｄ，Ａ，Ｂ，Ｃ｝のうち３データに含まれ、アイテム５は２データに含まれる。したがって、代表ｅ＊（Ｐ）＝５となる。また、親Ｐｒｔ（｛１，４，５｝）は、トランザクション｛１，４，５｝から代表５を除いた｛１，４｝となる。
【００３７】
また、親となるトランザクション（パターン）｛１，４｝について、アイテム１，４の全てを含むデータ（包含率１００％）はＤ，Ａ、１個含まないデータ（包含率５０％）はＢ，Ｃ，Ｆ、全て含まれないデータ（包含率０％）はＥであり、３グループに分かれる。ＡｍｂｉＯｃｃ（｛１，４｝）＝｛Ｄ，Ａ，Ｂ，Ｃ，Ｆ｝となり、最大共起数σｐ＝５＞σ＝４、平均包含率θｐ＝７０％（（１００×２＋５０×３）／５）＞θ＝６６％となり、トランザクション｛１，４｝もあいまい頻出集合Ｐ０の１つの解であることが分かる。このように、親は子供よりアイテム数が１小さく、親子関係は非巡回的（親を辿っていくことにより自分自身に戻ることはない）である。また親は子供より最大共起数が大きいか等しく、子供があいまい頻出集合Ｐ０に含まれる場合は、親もあいまい頻出集合Ｐ０に含まれる。
【００３８】
図７に、あいまい頻出集合Ｐ０の親子関係を列挙木構造で示す。データベースＤのデータＡ〜Ｆを左側に示す。平均包含率θｐの閾値（密度閾値）θ＝６６％、最大共起数（頻出度数）σｐの閾値（ミニマムサポート）σ＝４とする。親子関係の列挙木構造を右側に示す。親子関係は矢印で示される。トランザクション（パターン）｛１，４，５｝の親は｛１，４｝であり、｛４，５｝ではない。また、トランザクション（パターン）｛１，４｝の親は｛４｝であり、｛１｝ではない。このように親子関係は一意的に定められる。このようにして、全ての解（２０個の解）が列挙木構造で表される。なお、φはアイテムが何も無い空集合を示す。
【００３９】
列挙木を探索すれば、あいまい頻出集合Ｐ０に属する全てのパターンＰを見つけることができる。さらに、深さ優先で探索すれば、列挙木の深さは深くてもアイテム数までであり、解をメモリに保存する必要もない。このような列挙木の深さを探索するには、与えられた頂点にある親の子供を順次見つけ、見つけた子供に対して、再帰的に子供を見つけていけばよい。子供は親にアイテムを１個付け加えることにより得られる。しかし、親にアイテムを付け加えて得られる子供があいまい集合Ｐ０に属する場合でも、付け加えたアイテムが代表アイテムでなければ、真の親ではなく、異なる親が在ることになる。したがって、代表ｅ＊（Ｐ）を求めることにより、親子関係を照合しながら列挙木を探索することとなる。
【００４０】
あいまい頻出集合Ｐ０の最大共起数σｐは、データベースＤのデータから包含率の高い順にトランザクションを選択して得ることができる。しかも、アイテムｅの付加により、この包含率は逆転することはないので、データの配列順序は逆転しない。すなわち、トランザクション（パターンＰ）の最大共起数σｐを計算するに際して、包含率の大きさ順にデータベースＤに含まれるトランザクションをグループ分けすると、パターンＰに対する包含率の順序は、そのまま、親Ｐ∪ｅに対する包含率の順になる。したがって親のＡｍｂｉＯｃｃ（Ｐ∪ｅ）から子供のＡｍｂｉＯｃｃ（Ｐ）を求めることができ、また、親のＡｍｂｉＯｃｃ（Ｐ∪ｅ）について、含まれる数が最小であるアイテムを抽出することにより、代表ｅ＊（Ｐ）を求めることができる。
【００４１】
図８に、トランザクション（パターン）Ｐ＝｛１，４｝に、アイテムｅ＝５を付加したときの正規出現ＡｍｂｉＯｃｃ（Ｐ∪ｅ）の計算例を示す。データベースＤのデータＡ〜Ｆ（図６及び図７と同じ）を左側に示す。平均包含率θｐの閾値（密度閾値）θ＝６６％、最大共起数σｐの閾値（ミニマムサポート）σ＝４とする。親のトランザクション｛１，４｝について、アイテム１，４の全てを含むデータ（包含率１００％）はＤ，Ａ、１個含まないデータ（包含率５０％）はＢ，Ｃ，Ｆ、全て含まれないデータ（包含率０％）はＥであり、３グループに分かれる。ＡｍｂｉＯｃｃ（｛１，４｝）＝｛Ｄ，Ａ，Ｂ，Ｃ，Ｆ｝となり、最大共起数σｐ＝５＞σ＝４、平均包含率θｐ＝７０％となり、トランザクション｛１，４｝もあいまい頻出集合Ｐ０の１つの解である。また、子供のトランザクション（パターン）｛１，４，５｝について、アイテム１，４，５の全てを含むデータ（包含率１００％）はＤ、１個含まないデータ（包含率６６％）はＡ，Ｂ、２個含まないデータ（包含率３３％）はＣ，Ｆ、全て含まれないデータ（包含率０％）はＥであり、４グループに分かれる。ＡｍｂｉＯｃｃ（｛１，４，５｝）＝｛Ｄ，Ａ，Ｂ，Ｃ｝となり、平均包含率θｐは６６％となり、トランザクション｛１，４，５｝もあいまい頻出集合Ｐ０の１つの解であることが分かる。ＣとＦについては辞書順からＣが選択される。ここで、トランザクション｛１，４，５｝について、代表ｅ＊（Ｐ）を求める。トランザクション｛１，４，５｝のアイテム１及び４は｛Ｄ，Ａ，Ｂ，Ｃ｝のうち３データに含まれ、アイテム５は２データに含まれる。したがって、代表ｅ＊（Ｐ）＝５となる。また、親Ｐｒｔ（｛１，４，５｝）は、トランザクション｛１，４，５｝から代表５を除いた｛１，４｝となる。したがって、トランザクション｛１，４｝とトランザクション｛１，４，５｝は親子関係で結ばれる。
【００４２】
しかし、トランザクション｛４，５｝とトランザクション｛１，４，５｝は親子関係で結ばれない。親のトランザクション｛４，５｝について、アイテム４，５の全てを含むデータ（包含率１００％）はＢ，Ｄ、１個含まないデータ（包含率５０％）はＡ，Ｆ、全て含まれないデータ（包含率０％）はＣ，Ｅである。ＡｍｂｉＯｃｃ（｛４，５｝）＝｛Ｂ，Ｄ，Ａ，Ｆ｝となり、最大共起数σｐ＝４、平均包含率θｐ＝７５％となり、トランザクション｛４，５｝もあいまい頻出集合Ｐ０の１つの解である。しかし、ＡｍｂｉＯｃｃ（｛１，４，５｝）＝｛Ｄ，Ａ，Ｂ，Ｃ｝となり、平均包含率θｐは６６％となり、代表ｅ＊（Ｐ）＝５なので、トランザクション｛１，４，５｝から代表を除いた親はＰｒｅ（Ｐ）＝｛１，４｝となり、｛４，５｝と異なるので、トランザクション｛４，５｝とトランザクション｛１，４，５｝は親子関係で結ばれない。また、トランザクション｛１，５｝については、アイテム１，５の全てを含むデータ（包含率１００％）はＤ、１個含まないデータ（包含率５０％）はＡ，Ｂ，Ｃ、全て含まれないデータ（包含率０％）はＥ，Ｆである。ＡｍｂｉＯｃｃ（｛１，５｝）＝｛Ｄ，Ａ，Ｂ｝となり、最大共起数σｐ＝３、平均包含率θｐ＝６６％となり、トランザクション｛４，５｝はあいまい頻出集合Ｐ０の解ではない。したがって、トランザクション｛１，４，５｝についての親子関係はトランザクション｛１，４｝のみについて一意的に成立し、重複することはない。
【００４３】
また、トランザクション｛１，４｝とトランザクション｛１，３，４｝は親子関係で結ばれない。トランザクション｛１，３，４｝について、アイテム１，３，４の全てを含むデータ（包含率１００％）はＡ、１個含まないデータ（包含率６６％）はＤ，Ｆ、２個含まないデータ（包含率３３％）はＢ，Ｃ，Ｅであり、全て含まれないデータ（包含率０％）は無い。ＡｍｂｉＯｃｃ（｛１，３，４｝）＝｛Ａ，Ｄ，Ｆ，Ｂ｝となり、平均包含率θｐは６６％となり、トランザクション｛１，３，４｝もあいまい頻出集合Ｐ０の１つの解であるが、代表ｅ＊（Ｐ）＝１となり、トランザクション｛１，４｝とトランザクション｛１，３，４｝は親子関係で結ばれない。なお、トランザクション｛１，４｝のグループ順序は、｛Ｄ，Ａ， Ｂ，Ｃ，Ｆ｝であり、｛Ａ，Ｄ， Ｆ，Ｂ，Ｃ｝とも並べ替えられるので、トランザクション｛１，３，４｝になってもグループ順序は逆転していない。
【００４４】
次に、列挙木の探索順序について説明する。まず、トランザクション｛１｝について、ＡｍｂｉＯｃｃ（｛１｝）＝｛Ａ，Ｃ，Ｄ，Ｂ｝、最大共起数σ＝４、平均包含率θｐ＝７５％となり、あいまい頻出集合Ｐ０の解であることを求める。次に、トランザクション｛１，２｝〜｛１，７｝について探索を行い、あいまい頻出集合Ｐ０の解でかつ、親子関係が成立するかを求める。あいまい頻出集合Ｐ０の解で親子関係が成立するもの（例えば｛１，ｋ｝）があれば、トランザクション｛１，ｋ｝の子供について同様の探索を行い、あいまい頻出集合Ｐ０の解で親子関係が成立するものがあれば、さらにその子供について探索を行ない、あいまい頻出集合Ｐ０の解で親子関係が成立するものがなくなるまで深さ方向に探索を行なう。次に、トランザクション｛２｝について、ＡｍｂｉＯｃｃ（｛１｝）＝｛Ｂ，Ｃ，Ｅ，Ａ｝、最大共起数σｐ＝４、平均包含率θｐ＝７５％となり、あいまい頻出集合Ｐ０の解であることを求める。同様に、深さ方向に探索を行なう。このようにして、順次深さ方向優先の探索を行い、列挙木を構築する。
【００４５】
よって、各Ｐ∪ｅ（Ｐにｅを付加したもの）の最大共起数σｐを計算するには、ＡｍｂｉＯｃｃ（Ｐ）の各データを包含率でグループ分けしておけば、その中から各Ｐ∪ｅのＡｍｂｉＯｃｃを構成でき、また、各アイテムｅに対して、ｅを含むグループ内のトランザクションを見つけることで、Ｐ∪ｅ の包含率が高いトランザクションを大きい順に見つけることができるので、これを利用すると速く計算できる。最大共起数σｐが大きいアイテム集合は、それほど多くないと思われ、現実的には、一反復の実行時間はＡｍｂｉＯｃｃ（Ｐ）に含まれるアイテムｅの総数に依存し、データベースサイズ‖Ｄ‖に比例する、このため、短時間の計算で解を求めることが可能である。
【００４６】
［第２の実施の形態］
第１の実施の形態ではアイテムが数字の例を説明したが、第２の実施の形態では数字以外の例について説明する。例えば、属性値が実数であるようなデータを扱うことができる。実験結果やセンサーのログなどをデータとし、これを離散化してアイテムｅにすることでトランザクションデータベースＤに変換して利用できる。例えば、属性Ａの数値が０．０〜１．０ならばＡ１、１．０以上ならＡ２、０．０未満ならＡ３というアイテムを含むものとする、というように変換を行なう。このようにして、実験結果をトランザクションの集合として扱い、グループ分けや解析を行なうことが可能である。また、商品に適用すれば、例えばどのような商品が類似グループに属するか、どのような商品の組み合わせ（お弁当とお茶など）が売れ行きが良いのかなどの解析が可能となる。また、コンテンツに対してもどのような類似グループに属するか、どのような組み合わせが良く利用されるかなどの解析ができる。
【００４７】
また、本発明は、以上の実施の形態に記載のあいまい頻出集合の探索方法をコンピュータに実行させるためのプログラムとしても実現可能である。プログラムはコンピュータの内蔵メモリに蓄積して使用してもよく、外付けの記憶装置に蓄積して使用してもよく、インターネットからダウンロードして使用しても良い。また、当該プログラムを記録した記録媒体としても実現可能である。
【００４８】
以上、本発明の実施の形態について説明したが、実施の形態は以上の例に限られるものではなく、本発明の趣旨を逸脱しない範囲で、種々の変更を加え得ることは明白である。
【００４９】
例えば、以上の実施の形態では、アイテムが数字、実験データ、商品の例に言及したが、文字、記号でも良く識別符号で対応可能であれば何でも良い。例えば、音声や映像のコンテンツとしても良く、話者の音声解析、生態系の統計的解析等にも応用できる。また、平均包含率の閾値θ、最大共起数の閾値σは任意に設定できる。
【産業上の利用可能性】
【００５０】
本発明は、データベースのあいまい検索に利用可能である。
【図面の簡単な説明】
【００５１】
【図１】ｋ擬似頻出集合の例を示す図である。
【図２】あいまい頻出集合の例を示す図である。
【図３】あいまい頻出集合の探索方法の処理フロー例を示す図である。
【図４】パターンがあいまい頻出集合に属するか否かを判断する工程を示す図である。
【図５】あいまい頻出集合の探索装置の構成例を示す図である。
【図６】あいまい頻出集合の正規出現の例を示す図である。
【図７】あいまい頻出集合の親子関係を列挙木構造で示す図である。
【図８】正規出現の計算例を示す図である。
【符号の説明】
【００５２】
１００ あいまい頻出集合の探索装置
Ｃ コンピュータ（演算手段）
Ｄ データベース
Ｅ アイテム集合
ｅ アイテム
ｅ＊（Ｐ） 代表
ｋ 擬似頻出集合の係数
Ｍ メモリ
Ｍ０ 頻出パターン探索手段
Ｍ１ 正規出現演算手段
Ｍ２ 代表選定手段
Ｍ３ 親選定手段
Ｍ４ パターン選択手段
Ｐ パターン
Ｐ０ あいまい頻出集合
Ｐ１ 親のパターン
Ｐ２ 子供のパターン
Ｔ トランザクション
Ｔ０ トランザクションの集合
θ 平均包含率の閾値（密度閾値）
θｐ 平均包含率
σ 最大共起数の閾値（ミニマムサポート）
σｐ 最大共起数（頻出度数）
ＡｍｂｉＯｃｃ（Ｐ） 正規出現
Ｐｒｔ（Ｐ） Ｐの親
【技術分野】
【０００１】
本発明は、あいまい頻出集合の探索方法及び探索装置に関する。詳しくは、データベース内に頻繁に現れる頻出パターンを、あいまい性を許して完全かつ短時間に抽出できる探索方法及び探索装置に関する。
【背景技術】
【０００２】
データベース内に頻繁に現れる頻出パターンを抽出する問題は、情報科学の基本問題である。データベースのデータ及びパターンとして、トランザクション、ツリー、グラフ、多次元ベクトル等が、データ及びパターンの要素として、アイテム、部分集合、木、パス・サイクル、グラフ、図形等が挙げられる。特に、データベースＤのデータがアイテム集合Ｅの部分集合であるトランザクションＴである場合に、頻出パターンを全て抽出する問題は頻出パターン列挙問題と云われている。この場合、完全一致検索の問題であれば容易に解決できる。他方、あいまい性を許して多くのデータに含まれるパターンを抽出するあいまい検索は、ゲノムの相同検索等で大いに実用的である。しかし、完全一致検索の問題からこのようなあいまい検索の問題になると、とたんに難しくなる。
【０００３】
アイテム集合Ｅに対して、あいまいな包含関係を考え、頻出集合を列挙するアルゴリズムに関して、従来の解決方法は、包含率の閾値θを定め、全てのデータを照合するか、ヒューリステックな検索をして、多数ではあるが不完全な頻出集合を抽出するかのどちらかであった。（非特許文献１〜３参照）
【０００４】
【非特許文献１】Ｃ．Ｙａｎｇ，Ｕ．Ｆａｙｙａｄ，Ｐ．Ｓ．Ｂｒａｄｌｅｙ，“Ｅｆｆｉｃｉｅｎｔ Ｄｉｓｃｏｖｅｒｙ ｏｆ Ｅｒｒｏｒ−Ｔｏｌｅｒａｎｔ Ｆｒｅｑｕｅｎｔ Ｉｔｅｍｓｅｔｓ ｉｎ Ｈｉｇｈ Ｄｉｍｅｎｓｉｏｎｓ”，ＳＩＧＫＤＤ２００１，２００１．
【非特許文献２】Ｊ．Ｂｅｓｓｏｎ，Ｃ．Ｒｏｂａｒｄｅｔ，ａｎｄ Ｊ．Ｆ．Ｂｏｕｌｉｃａｕｔ，“Ｍｉｎｉｎｇ Ｆｏｒｍａｌ Ｃｏｎｃｅｐｔｓ ｗｉｔｈ ａ Ｂｏｕｎｄｅｄ Ｎｕｍｂｅｒ ｏｆ Ｅｘｃｅｐｔｉｏｎｓ ｆｒｏｍ Ｔｒａｎｓａｃｔｉｏｎａｌ Ｄａｔａ”，ＫＤＩＤ ２００４，ＬＮＣＳ ３３７７，ｐｐ．３３−４５，２００５．
【非特許文献３】Ｗ．Ｓｈｅｎ−Ｓｈｕｎｇ ａｎｄ Ｌ．Ｓｕｈ−Ｙｉｎ，“Ｍｉｎｉｎｇ Ｆａｕｌｔ−Ｔｏｌｅｒａｎｔ Ｆｒｅｑｕｅｎｔ Ｐａｔｔｅｒｎｓ ｉｎＬａｒｇｅ Ｄａｔａｂａｓｅｓ”，ＩＣＳ２００２，２００２．
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、全てのデータを照合する方法は小さいデータベースでは完全抽出できるが、大きいデータベースでは非実用的であった。また、ヒューリステックな検索でも、全てのパターンを完全に抽出できるアルゴリズムは見出されていない。
【０００６】
本発明は、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索方法及び探索装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明の第１の態様によるあいまい頻出集合の探索方法は、例えば、図３に示すように、データベースＤ内に頻繁に現れる頻出パターンＰを、あいまい性を許容して抽出するあいまい頻出集合の探索方法であって、データベースＤのデータが、アイテムｅからなるアイテム集合Ｅの部分集合であるトランザクションＴからなるデータベースＤであり、頻出パターンＰが、構成アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数（最大共起数）が閾値σ以上を条件とするあいまい頻出集合Ｐ０のパターンであり、頻出パターンＰについて、データベースＤのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算工程（Ｓ２０〜Ｓ５０）と、頻出パターンＰの構成アイテムｅのうち、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定工程（Ｓ６０）と、頻出パターンＰから代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定工程（Ｓ７０〜Ｓ９０）と、あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択工程（Ｓ１０，Ｓ１００）とを備え、パターン選択工程（Ｓ１０，Ｓ１００）で選択された各候補について、正規出現演算工程（Ｓ２０〜Ｓ５０）を用いてあいまい頻出集合Ｐ０に属するか否かを判断し、当該候補があいまい頻出集合Ｐ０に属する場合には、代表選定工程（Ｓ６０）及び親選定工程（Ｓ７０〜Ｓ９０）を用いて親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する。
【０００８】
ここにおいて、あいまい性の程度は、平均包含率の閾値θ及び頻出度数（最大共起数）の閾値σにより枠決めされる。また、アイテムｅは明細書中では説明の便宜上、数字としたが、文字、記号でも良く識別符号で対応可能であれば何でも良い。例えば、商品、コンテンツ、サンプルでも良い。また、包含率とは、パターンＰを構成するアイテムｅの総数のうち、データに含まれるアイテム数の割合をいい、平均包含率θｐとは、複数のデータについて包含率を平均化したものをいう。また、最大共起数σｐとは、平均包含率が閾値θ以上となるように選択された最大のデータ数をいう。この態様のように構成すると、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索方法を提供できる。
【０００９】
また、本発明の第２の態様によるあいまい頻出集合の探索方法は、第１の態様において、パターン選択工程において、深さ優先探索を用いる。このように構成すると、親の正規出現から子供の正規出現を導き出せることを利用して、効率的に探索ができる。
【００１０】
また、本発明の第３の態様によるあいまい頻出集合の探索方法は、第１の態様において、アイテムが商品、コンテンツ、サンプル、その他識別符号で対応付けられたもののいずれかである。このように構成すると、商品販売データ、実験データの解析等に役立てられる。
【００１１】
上記課題を解決するために、本発明の第４の態様によるあいまい頻出集合の探索装置１００は、例えば、図５に示すように、データベースＤ内に頻繁に現れる頻出パターンＰを、あいまい性を許容して抽出するあいまい頻出集合の探索装置であって、データベースＤのデータが、アイテムからなるアイテム集合Ｅの部分集合であるトランザクションＴからなるデータベースＤであり、頻出パターンＰが、構成アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数（最大共起数）が閾値σ以上を条件とするあいまい頻出集合Ｐ０のパターンであり、頻出パターンＰについて、データベースＤのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算手段Ｍ１と、頻出パターンＰの構成アイテムｅのうち、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定手段Ｍ２と、頻出パターンＰから代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定手段Ｍ３と、あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択手段Ｍ４とを備え、パターン選択手段Ｍ４で選択された各候補について、正規出現演算手段Ｍ１を用いてあいまい頻出集合Ｐ０に属するか否かを判断し、当該候補があいまい頻出集合Ｐ０に属する場合には、代表選定手段Ｍ２及び親選定手段Ｍ３を用いて親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する。
【００１２】
ここにおいて、解決装置１００はデータベースＤを有しても良いが、有さなくてもアクセス可能であれば良い。また、各手段は１つのコンピュータＣ内に構成されても良く、それぞれ、別のコンピュータで構成されても良い。また、１つのコンピュータＣ内に構成される場合に、各手段毎に別個のハードウエアに構成されても良いが、１つのコンピュータＣが各手段の機能を有するならば、各手段がコンピュータ内に構成されているとみなして良い。この態様のように構成すると、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索装置を提供できる。
【発明の効果】
【００１３】
本発明によれば、あいまい頻出集合のパターンを完全かつ短時間に抽出できる探索方法及び探索装置を提供できる。
【発明を実施するための最良の形態】
【００１４】
［頻出集合について］
まず、頻出集合について説明する。アイテム集合Ｅはアイテムｅ＝１，２・・・ｎの組み合わせからなる集合であり、データベースＤはアイテム集合Ｅの部分集合であるトランザクションＴの集合からなるものとする。データベースＤが有するトランザクション数を｜Ｄ｜、トランザクションＴが有するアイテム数を｜Ｔ｜とする（同様に｜ ｜は数を表すものとする）。データベースサイズを‖Ｄ‖＝｜Ｄ｜＋ΣＴ∈Ｄ｜Ｔ｜と定義する。すなわち、データベースＤが有するトランザクション数と各トランザクションが有するアイテム数の総和である。データベースサイズ‖Ｄ‖はコンピュータ計算時間を求めるために用いられる。ここで、アイテム集合Ｅの部分集合であるパターンＰ（トランザクション）に注目する。データベースＤ内でパターンＰが出現するものの集合を出現集合Ｏｃｃ（Ｐ）、パターンＰの出現頻度をｆｒｑ（Ｐ）（＝｜Ｏｃｃ（Ｐ）｜）とする。また、データベースＤ内でパターンＰのアイテムをｈ個含まないものの集合をＯｃｃ＝ｈ（Ｐ）＝｛Ｔ｜Ｔ∈Ｄ，｜Ｐ＼Ｔ｜＝ｈ｝（Ｐ＼ＴはＰとＴの差異を示す）、ｈ個以下含まないものの集合をＯｃｃ≦ｈ（Ｐ）＝｛Ｔ｜Ｔ∈Ｄ，｜Ｐ＼Ｔ｜≦ｈ｝とする。データベースＤ内に、出現頻度が閾値σ以上出現するパターンの集合を頻出集合という。この閾値σをミニマムサポート（最小頻度）という。データベースＤと閾値σが与えられた時に、頻出集合の全ての解を求める問題を頻出集合列挙問題という。
【００１５】
図１にｋ擬似頻出集合の例を示す。データベースＤのデータがアイテム集合Ｅ（アイテムｅ）の部分集合からなるトランザクションＴであり、図の左側に示すような６データを有しているものとする。ｋ擬似頻出集合とは、データベースＤ内のσ個以上のデータ（トランザクション）にｋ擬似包含の意味で含まれる（ｋ個以下の異なるアイテムがあっても良いことを意味する）アイテム集合であって、図の右側にσ＝３、ｋ＝１での擬似頻出集合の例を示す。例えば、パターン｛１，２，３｝について、データ｛１，２，５，６，７，９｝及び｛１，２，７，８，９｝はアイテム１と２を含み、３を含まない。データ｛２，３，４，５｝はアイテム２と３を含み、１を含まない。このように、３個のアイテム中、ｋ＝１個以下のアイテムが異なるデータが３個、すなわち、閾値σ＝３以上ある。また、パターン｛１，２，７，９｝ついて、データ｛１，２，５，６，７，９｝及び｛１，２，７，８，９｝は全てのアイテムを含む。データ｛１，７，９｝及び｛２，７，９｝は３個のアイテムを含み、１個のアイテムを含まない。このように、４個のアイテム中、ｋ＝１個以下のアイテムが異なるデータが４個、すなわち、閾値σ＝３以上ある。このようなパターン（トランザクション）は図に示すように３個のアイテムを有するものが３３個、４個のアイテムを有するものが１１個ある。
【００１６】
ｋ擬似頻出集合を含め、頻出集合列挙問題の解を全て列挙するのは容易である。その理由は、単調性が保持されているので（解の任意の部分集合も解になっているので）、任意の頻出集合は、頻出集合の域内で、空集合に順次アイテムを付加することによって得ることができるからである。親のパターン（トランザクション）にアイテムｅを１つ付加したものを子供のパターン（トランザクション）という。空集合以外の頻出集合の任意のパターンは親を持つので、この親子関係は頻出集合の全てのパターンを関係付ける列挙木を導き出す。列挙木を探索することにより、頻出集合の全ての解を見つけることができる。ただし、各親について可能な子供を全て探索すると子供のトランザクションに重複が生じるが、唯一の親を選択してアイテムを付加するような秩序を導入することにより重複を避けられる。単調性が保持されていれば、分岐限定法的なアプローチを用いることができる。すなわち、どのアイテムを加えるかで場合分けを繰り返すことにより、簡単に重複を回避しつつ解を列挙できる。
【００１７】
［あいまい頻出集合について］
次に、あいまい頻出集合Ｐ０について説明する。パターンＰのアイテムｅのうちトランザクションＴに含まれるアイテムの割合を包含率といい、（｜Ｔ∩Ｐ｜／｜Ｔ｜）（Ｔ∩ＰはＴとＰが共有するアイテムを示す）で示される。次に、パターンＰのアイテムのうちトランザクションＴの集合Ｔ０に含まれる平均包含率θｐを考える。平均包含率θｐは集合Ｔ０に含まれる各トランザクションＴに対する包含率を平均したもの（ΣＴ∈Ｔ０｜Ｔ∩Ｐ｜）／（｜Ｔ｜｜Ｐ｜）である。平均包含率θｐが閾値（密度閾値）θ以上となる最大数のトランザクションの集合をＰの最大共起集合という。その集合に含まれるトランザクションの数をＰの最大共起数といい、σｐ＝ｃｏｖ（Ｐ）で表す。トランザクションデータベースＤ，最大共起数ｃｏｖ（Ｐ）が閾値（ミニマムサポート）σ以上、平均包含率θｐが閾値（密度閾値）θ以上のあいまい頻出集合Ｐ０の全ての解を求める問題を、あいまい頻出集合列挙問題という。すなわち、あいまい頻出集合列挙問題とは、与えられたトランザクションデータベースＤ、密度閾値θ、ミニマムサポート（最小頻度）σに対し、データベースＤに対するあいまい頻出集合Ｐ０の解（パターンＰ）を全て出力する問題をいう。
【００１８】
図２にあいまい頻出集合Ｐ０の例を示す。データベースＤのデータがアイテム集合Ｅの部分集合からなるトランザクションＴであり、図の左側に示すような３データを有しているものとする。例えば、パターン（トランザクション）｛２，３｝については、データ｛１，３，４｝には２が無く３が有るので、包含率５０％、データ｛２，４，５｝及び｛１，２｝には２が有り３が無いので、包含率５０％であり、これらの平均包含率θｐは５０％である。パターン｛４，５｝については、データ｛１，３，４｝には４が有り５が無いので、包含率５０％、データ｛２，４，５｝には４及び５が有るので、包含率１００％、データ｛１，２｝には４及び５が無いので、包含率０％であり、これらの平均包含率θｐは５０％である。パターン｛１，２｝については、データ｛１，３，４｝には１が有り２が無いので、包含率５０％、データ｛２，４，５｝には１が無く２が有るので、包含率５０％、データ｛１，２｝には１及び２が有るので、包含率１００％であり、これらの平均包含率θｐは６６％である。ここで、平均包含率の閾値θ＝５０％を条件とすれば、３個のデータが該当し、閾値θを６６％を条件とすれば、１個のデータ｛１，２｝が該当する。また、以上の平均包含率θｐについては３個のデータの平均包含率をとっているので、最大共起数は閾値σ＝３を満たす。もし、最大共起数の閾値σ＝２とすれば、パターン｛４，５｝に対しては、データ｛１，３，４｝及びデータ｛２，４，５｝を選択でき、平均包含率θｐ＝７５％となる。もし、平均包含率の閾値（密度閾値）θ＝６６％、最大共起数の閾値（ミニマムサポート）σ＝３を条件とすると、データベースＤに対するあいまい頻出集合として図中の３つのパターンのうちではパターン｛１，２｝のみが該当する。なお、図示しないが、パターン｛１｝や｛２｝などもあいまい頻出集合Ｐ０に該当する。この例ではデータが少ないので、あいまい頻出集合Ｐ０の解を全て列挙するのは容易である。
【００１９】
任意の頻出集合は、単調性が保持されていれば、頻出集合の域内で、空集合に順次アイテムを付加することによって得ることができる。しかしながら、あいまい頻出集合Ｐ０は単調性を保持しないので、分岐限定法的なアプローチを適用できそうにない。また、あいまい頻出集合が存在するか否かの判定はＮＰ完全と呼ばれる難しい問題に属する。そこで、多項式遅延多項式空間の逆探索アルゴリズムを用いる。この場合、各頻出集合のコンピュータ計算時間はデータベースサイズ‖Ｄ‖に比例し、Ｏ（‖Ｄ‖）と表される。
【００２０】
多項式遅延多項式空間のアルゴリズムとは次ぎのようなアルコリズムをいう。もし、アルゴリズムの計算時間が、解の数の線形であるならば、不要な計算をあまりしていないと考えられるため、実用的に優れている。また、アルゴリズムのメモリ使用量が入力サイズの多項式であるなら、解が多量であってもメモリ不足を起こすことがない。本発明では、あいまい頻出集合列挙問題を解決する、このような、解の数に線形の時間で動き、入力の多項式サイズのメモリしか消費しない多項式遅延多項式空間のアルゴリズムを使用する。
【００２１】
［第１の実施の形態］
第１の実施の形態では、あいまい頻出集合Ｐ０の解を全て列挙できるアルゴリズムとして、擬似頻出集合の多項式遅延多項式空間アルゴリズムを用いて、逆探索的アプローチを行うこととする。
【００２２】
あいまい頻出集合Ｐ０に属するパターンＰの最大共起集合のうち、辞書順最小のものをあいまい頻出集合Ｐの正規出現ＡｍｂｉＯｃｃ（Ｐ）と定義する。すなわち、あいまい頻出集合Ｐ０に属するパターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）はデータベースＤに含まれるトランザクションＴを包含率の大きいものから順次選択し、同率のものがあれば、ＩＤ（識別符号）の小さいほうを優先して並べることによって得られる。そして、空集合以外（Ｐ≠０）のパターンＰに含まれるアイテムｅのうち、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数｜ＡｍｂｉＯｃｃ（Ｐ）∩Ｏｃｃ（｛ｅ｝）｜が最小のアイテムを代表ｅ＊（Ｐ）と定義する。すなわち、密度が一番小さいアイテムを除くことにより親子関係を定める。代表ｅ＊（Ｐ）を用いることにより、あいまい頻出集合Ｐ０に明確な探索ルートを決めることができる。
【００２３】
定理１． Ｐ≠０の任意のアイテム集合のパターンＰに対して、ｃｏｖ（Ｐ＼｛ｅ｝）（Ｐからｅを除いたものの最大共起数）≧ｃｏｖ（Ｐ）（Ｐの最大共起数）を満たすアイテムｅ∈Ｐが存在する。
【００２４】
証明： あいまい頻出集合のパターンＰに対する正規出現ＡｍｂｉＯｃｃ（Ｐ）の平均包含率は、Σｅ∈Ｐ｜ＡｍｂｉＯｃｃ（Ｐ）∩Ｏｃｃ（｛ｅ｝）｜／［（Ｐ−１）×｜ＡｍｂｉＯｃｃ（Ｐ）｜］なので、｜ＡｍｂｉＯｃｃ（Ｐ）∩Ｏｃｃ（｛ｅ｝）｜／｜ＡｍｂｉＯｃｃ（Ｐ）｜の平均値で与えられる。親Ｐ＼｛ｅ＊（Ｐ）｝に対するＡｍｂｉＯｃｃ（Ｐ）の平均包含率は、Ｐ＼｛ｅ＊（Ｐ）｝の中の｜ＡｍｂｉＯｃｃ（Ｐ）∩Ｏｃｃ（｛ｅ｝）｜／｜ＡｍｂｉＯｃｃ（Ｐ）｜の平均値であり、Ｐに対するＡｍｂｉＯｃｃ（Ｐ）の平均包含率以上である。このことは、ｃｏｖ（Ｐ＼｛ｅ｝）はｃｏｖ（Ｐ）以上であり、代表ｅ＊（Ｐ）が主題のアイテムｅであるという条件を満たす。
【００２５】
また、Ｐ≠０のアイテム集合のパターンＰに対して、Ｐの親をＰｒｔ（Ｐ）＝Ｐ＼｛ｅ＊（Ｐ）｝（Ｐから代表を除いたもの）と定める。すなわち、親は子から代表ｅ＊（Ｐ）を除いたものをいう。定理１より、Ｐ＼｛ｅ＊（Ｐ）｝もまたあいまい頻出集合に属する。特に、ｃｏｖ（Ｐｒｔ（Ｐ））≦ｃｏｖ（Ｐ）が成り立つ。親Ｐｒｔ（Ｐ）は子供Ｐに比して含むアイテムｅが１つ少なく、このようにして導入された親子関係はあいまい頻出集合の各パターンに対して１つの親が対応し、親子関係が一意的に定まる。空集合以外の任意の頻出集合は親を持つので、この親子関係はあいまい頻出集合の全てのパターンを関係付ける列挙木を導き出す。そして、列挙木を探索することにより、重複なしにあいまい頻出集合の全ての解（パターン）を見つけることができる。列挙木に深さ優先探索を行ない、見つけた子供に対し再帰的に子供を見つけることにより、メモリを付加すること無く、探索を実行できる。
【００２６】
あいまい頻出集合のパターンＰに対する逆探索アルゴリズムは次のようになる。
（１）パターンＰを出力する。
（２）Ｐに含まれない各アイテムｅに対して
（２ａ）もしＰにｅを付加したものＰ∩｛ｅ｝があいまい頻出集合に属するのであれば、
（２ｂ）もしその親Ｐｒｔ｛Ｐ∩｛ｅ｝｝＝Ｐであれば、
（２ｃ）｛Ｐ∩｛ｅ｝｝を逆探索する。
【００２７】
（２ａ）と（２ｂ）における平均包含率とＰにｅを付加したものＰ∩｛ｅ｝の親を求める計算は時間Ｏ（‖Ｄ‖）でなされる。繰り返しは高々ｎ倍（任意のパターンの子供の数は高々ｎ）であり、あいまい頻出集合のコンピュータ計算時間はＯ（‖Ｄ‖×ｎ）でなされる。また、列挙木の深さは高々ｎであり、次の定理が導かれる。
【００２８】
定理２．与えられたトランザクションデータベースＤ、ミニマムサポートの閾値σ、平均包含率の閾値θに対して、任意のあいまい頻出集合は、１つの集合あたり‖Ｄ‖に線形のコンピュータ計算時間で、‖Ｄ‖の大きさのメモリを用いて求められる。
【００２９】
図３にあいまい頻出集合の探索方法の処理フロー例を示す。全体のフローをあいまい頻出集合の探索工程として示す。あいまい頻出集合の探索工程は、頻出パターンＰについて、データベースＤのデータから、あいまい頻出集合の条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算工程と、頻出パターンＰの構成アイテムｅのうち、正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定工程と、頻出パターンＰから代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定工程と、あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択工程とを備える。
【００３０】
まず、あいまい頻出集合Ｐ０の候補としてパターンＰ１を選択する（Ｓ１０）。これはパターン選択工程に属する。パターンＰ１の選択は空集合φから、アイテムｅを１つずつ付加していき、あいまい頻出集合Ｐ０に属するか否かを判断していく。子供があいまい頻出集合に属するのであれば、さらにその子供について探索する深さ優先探索を行なうと効率的である。すなわち、パターンＰ１を選択したら、次に、アイテムｅを選択して（Ｓ２０）パターンＰ１に付加して子供のパターンＰ２を作成し（Ｓ３０）、子供Ｐ２＝Ｐ∩｛ｅ｝があいまい頻出集合に属するか否かを判断する（Ｓ４０）。
【００３１】
図４に、パターンがあいまい頻出集合に属するか否かを判断する工程（Ｓ４０）を示す。あいまい頻出集合Ｐ０の候補パターンＰ２に対して（Ｓ４１）、まず、データベースＤのデータを包含率の高い順に並べる（Ｓ４２）。次に、平均包含率θｐが閾値（密度閾値）θ以上の範囲で、包含率の高い順にデータを取得し、データ数が最大になるように取得して集合を形成する（Ｓ４３）。包含率が同じデータについては辞書順最小のものから選択する。次に、取得した集合のデータ数、すなわち最大共起数（頻出度数）σｐが閾値σ（ミニマムサポート）以上か否かを判断する（Ｓ４４）。取得した集合のデータ数が閾値σ以上であれば、子供Ｐ２＝Ｐ１∩｛ｅ｝があいまい頻出集合Ｐ０に属すると判断し（Ｓ４５）、閾値σ以上でなければ、子供Ｐ２＝Ｐ１∩｛ｅ｝があいまい頻出集合Ｐ０に属さないと判断する（Ｓ４６）。
【００３２】
ここで、図３に戻る。子供Ｐ２があいまい頻出集合Ｐ０に属さない場合（Ｓ４０でＮ）は、ステップＳ２０に戻り、あいまい頻出集合Ｐ０の候補Ｐ１に対して次のアイテムｅを選択する。子供Ｐ２があいまい頻出集合Ｐ０に属する場合（Ｓ４０でＹ）は、取得した集合がパターンＰ２の正規出現ＡｍｂｉＯｃｃ（Ｐ２）として求まる（Ｓ５０）。アイテムｅ選択から正規出現ＡｍｂｉＯｃｃ（Ｐ２）を求めるまでの工程（Ｓ１０〜Ｓ５０）は正規出現演算工程に属する。
【００３３】
次に子供Ｐ２＝Ｐ１∩｛ｅ｝について代表ｅ＊（Ｐ２）を求める（Ｓ６０）。これは代表選定工程に属する。子供Ｐ２＝Ｐ１∩｛ｅ｝のアイテムのうち、パターンＰ２の正規出現ＡｍｂｉＯｃｃ（Ｐ２）に含まれる数が最小のものを代表ｅ＊（Ｐ２）として選定する。次に、子供Ｐ２＝Ｐ１∩｛ｅ｝の親Ｐｒｅ（Ｐ２）を求める（Ｓ７０）。パターンＰ２から代表ｅ＊（Ｐ２）を除くことにより親Ｐｒｅ（Ｐ２）＝Ｐ２＼｛ｅ＊（Ｐ２）｝を求める。次に、求めた親Ｐｒｅ（Ｐ２）がＰ１であるか否かを判断する（Ｓ８０）。Ｐ１であれば（Ｓ８０でＹ）、求めた親Ｐｒｅ（Ｐ２）が真の親であり、親子関係が決まる（Ｓ９０）。Ｐ１でなければ（Ｓ８０でＮ）、求めた親Ｐｒｅ（Ｐ２）が真の親ではなく、ステップＳ２０に戻り、次のアイテムｅを選択する。親Ｐｒｅ（Ｐ）の演算から親子関係が決まるまでの工程（Ｓ７０〜Ｓ９０）は親選定工程に属する。
【００３４】
親子関係が定まれば、次のパターンを選択して探索を行う（Ｓ１００でＳ１０に戻る）。これはパターン選択工程に属する。子供があいまい頻出集合Ｐ０に属するのであれば、さらにその子供について再帰的に探索する。子供があいまい頻出集合Ｐ０に属するのでなければ、親に戻って、次のアイテムｅを選択し、探索する。すべてのアイテムｅについて探索が終了したら、さらに上位の親に戻って探索を行う。すなわち、次の候補パターンＰがあれば（Ｓ１００でＹ、Ｓ１０に戻る）、その候補についてあいまい頻出集合Ｐ０に属するか否かを判断し、全てのあいまい頻出集合Ｐ０の候補パターンがなくなる（Ｓ１００でＮ）まで探索を行う。
【００３５】
図５にあいまい頻出集合の探索装置の構成例を示す。あいまい頻出集合の探索装置１００は、コンピュータ（演算手段）Ｃ、データベースＤ、メモリＭを備える。コンピュータＣは頻出パターン探索手段Ｍ０を有する。頻出パターン探索手段Ｍ０は、例えば、あいまい頻出集合の探索方法のプログラムをコンピュータＣにインストールすることにより実現できる。なお、ハードウエアで実現しても良い。頻出パターン探索手段Ｍ０は、正規出現演算手段Ｍ１、代表選定手段Ｍ２、親選定手段Ｍ３、パターン選択手段Ｍ４を有する。正規出現演算手段Ｍ１は正規出現演算工程（Ｓ１０〜Ｓ５０）を実行し、代表選定手段Ｍ２は代表選定工程（Ｓ６０）を実行し、親選定手段Ｍ３は親選定工程（Ｓ７０〜Ｓ９０）を実行し、パターン選択手段Ｍ４はパターン選択工程（Ｓ１０、Ｓ１００）を実行する。この構成により、あいまい頻出集合を完全かつ短時間に抽出できる探索装置を提供できる。
【００３６】
図６に、あいまい頻出集合の正規出現ＡｍｂｉＯｃｃ（Ｐ）の例を示す。データベースＤのデータＡ〜Ｆを左側に示す。平均包含率θｐの閾値（密度閾値）θ＝６６％、最大共起数（頻出度数）σｐの閾値（ミニマムサポート）σ＝４とする。トランザクション（パターン）｛１，４，５｝について、アイテム１，４，５の全てを含むデータ（包含率１００％）はＤ、１個含まないデータ（包含率６６％）はＡ，Ｂ、２個含まないデータ（包含率３３％）はＣ，Ｆ、全て含まれないデータ（包含率０％）はＥであり、４グループに分かれる。これらを包含率の高いものから４とると、ＡｍｂｉＯｃｃ（｛１，４，５｝）＝｛Ｄ，Ａ，Ｂ，Ｃ｝となり、平均包含率θｐは６６％（（１００＋６６＋６６＋３３）／４）となり、トランザクション｛１，４，５｝はあいまい頻出集合Ｐ０の１つの解であることが分かる。ＣとＦについては辞書順からＣが選択される。ここで、トランザクション（パターンＰ）｛１，４，５｝について、代表ｅ＊（Ｐ）を求める。トランザクション｛１，４，５｝のアイテム１及び４は｛Ｄ，Ａ，Ｂ，Ｃ｝のうち３データに含まれ、アイテム５は２データに含まれる。したがって、代表ｅ＊（Ｐ）＝５となる。また、親Ｐｒｔ（｛１，４，５｝）は、トランザクション｛１，４，５｝から代表５を除いた｛１，４｝となる。
【００３７】
また、親となるトランザクション（パターン）｛１，４｝について、アイテム１，４の全てを含むデータ（包含率１００％）はＤ，Ａ、１個含まないデータ（包含率５０％）はＢ，Ｃ，Ｆ、全て含まれないデータ（包含率０％）はＥであり、３グループに分かれる。ＡｍｂｉＯｃｃ（｛１，４｝）＝｛Ｄ，Ａ，Ｂ，Ｃ，Ｆ｝となり、最大共起数σｐ＝５＞σ＝４、平均包含率θｐ＝７０％（（１００×２＋５０×３）／５）＞θ＝６６％となり、トランザクション｛１，４｝もあいまい頻出集合Ｐ０の１つの解であることが分かる。このように、親は子供よりアイテム数が１小さく、親子関係は非巡回的（親を辿っていくことにより自分自身に戻ることはない）である。また親は子供より最大共起数が大きいか等しく、子供があいまい頻出集合Ｐ０に含まれる場合は、親もあいまい頻出集合Ｐ０に含まれる。
【００３８】
図７に、あいまい頻出集合Ｐ０の親子関係を列挙木構造で示す。データベースＤのデータＡ〜Ｆを左側に示す。平均包含率θｐの閾値（密度閾値）θ＝６６％、最大共起数（頻出度数）σｐの閾値（ミニマムサポート）σ＝４とする。親子関係の列挙木構造を右側に示す。親子関係は矢印で示される。トランザクション（パターン）｛１，４，５｝の親は｛１，４｝であり、｛４，５｝ではない。また、トランザクション（パターン）｛１，４｝の親は｛４｝であり、｛１｝ではない。このように親子関係は一意的に定められる。このようにして、全ての解（２０個の解）が列挙木構造で表される。なお、φはアイテムが何も無い空集合を示す。
【００３９】
列挙木を探索すれば、あいまい頻出集合Ｐ０に属する全てのパターンＰを見つけることができる。さらに、深さ優先で探索すれば、列挙木の深さは深くてもアイテム数までであり、解をメモリに保存する必要もない。このような列挙木の深さを探索するには、与えられた頂点にある親の子供を順次見つけ、見つけた子供に対して、再帰的に子供を見つけていけばよい。子供は親にアイテムを１個付け加えることにより得られる。しかし、親にアイテムを付け加えて得られる子供があいまい集合Ｐ０に属する場合でも、付け加えたアイテムが代表アイテムでなければ、真の親ではなく、異なる親が在ることになる。したがって、代表ｅ＊（Ｐ）を求めることにより、親子関係を照合しながら列挙木を探索することとなる。
【００４０】
あいまい頻出集合Ｐ０の最大共起数σｐは、データベースＤのデータから包含率の高い順にトランザクションを選択して得ることができる。しかも、アイテムｅの付加により、この包含率は逆転することはないので、データの配列順序は逆転しない。すなわち、トランザクション（パターンＰ）の最大共起数σｐを計算するに際して、包含率の大きさ順にデータベースＤに含まれるトランザクションをグループ分けすると、パターンＰに対する包含率の順序は、そのまま、親Ｐ∪ｅに対する包含率の順になる。したがって親のＡｍｂｉＯｃｃ（Ｐ∪ｅ）から子供のＡｍｂｉＯｃｃ（Ｐ）を求めることができ、また、親のＡｍｂｉＯｃｃ（Ｐ∪ｅ）について、含まれる数が最小であるアイテムを抽出することにより、代表ｅ＊（Ｐ）を求めることができる。
【００４１】
図８に、トランザクション（パターン）Ｐ＝｛１，４｝に、アイテムｅ＝５を付加したときの正規出現ＡｍｂｉＯｃｃ（Ｐ∪ｅ）の計算例を示す。データベースＤのデータＡ〜Ｆ（図６及び図７と同じ）を左側に示す。平均包含率θｐの閾値（密度閾値）θ＝６６％、最大共起数σｐの閾値（ミニマムサポート）σ＝４とする。親のトランザクション｛１，４｝について、アイテム１，４の全てを含むデータ（包含率１００％）はＤ，Ａ、１個含まないデータ（包含率５０％）はＢ，Ｃ，Ｆ、全て含まれないデータ（包含率０％）はＥであり、３グループに分かれる。ＡｍｂｉＯｃｃ（｛１，４｝）＝｛Ｄ，Ａ，Ｂ，Ｃ，Ｆ｝となり、最大共起数σｐ＝５＞σ＝４、平均包含率θｐ＝７０％となり、トランザクション｛１，４｝もあいまい頻出集合Ｐ０の１つの解である。また、子供のトランザクション（パターン）｛１，４，５｝について、アイテム１，４，５の全てを含むデータ（包含率１００％）はＤ、１個含まないデータ（包含率６６％）はＡ，Ｂ、２個含まないデータ（包含率３３％）はＣ，Ｆ、全て含まれないデータ（包含率０％）はＥであり、４グループに分かれる。ＡｍｂｉＯｃｃ（｛１，４，５｝）＝｛Ｄ，Ａ，Ｂ，Ｃ｝となり、平均包含率θｐは６６％となり、トランザクション｛１，４，５｝もあいまい頻出集合Ｐ０の１つの解であることが分かる。ＣとＦについては辞書順からＣが選択される。ここで、トランザクション｛１，４，５｝について、代表ｅ＊（Ｐ）を求める。トランザクション｛１，４，５｝のアイテム１及び４は｛Ｄ，Ａ，Ｂ，Ｃ｝のうち３データに含まれ、アイテム５は２データに含まれる。したがって、代表ｅ＊（Ｐ）＝５となる。また、親Ｐｒｔ（｛１，４，５｝）は、トランザクション｛１，４，５｝から代表５を除いた｛１，４｝となる。したがって、トランザクション｛１，４｝とトランザクション｛１，４，５｝は親子関係で結ばれる。
【００４２】
しかし、トランザクション｛４，５｝とトランザクション｛１，４，５｝は親子関係で結ばれない。親のトランザクション｛４，５｝について、アイテム４，５の全てを含むデータ（包含率１００％）はＢ，Ｄ、１個含まないデータ（包含率５０％）はＡ，Ｆ、全て含まれないデータ（包含率０％）はＣ，Ｅである。ＡｍｂｉＯｃｃ（｛４，５｝）＝｛Ｂ，Ｄ，Ａ，Ｆ｝となり、最大共起数σｐ＝４、平均包含率θｐ＝７５％となり、トランザクション｛４，５｝もあいまい頻出集合Ｐ０の１つの解である。しかし、ＡｍｂｉＯｃｃ（｛１，４，５｝）＝｛Ｄ，Ａ，Ｂ，Ｃ｝となり、平均包含率θｐは６６％となり、代表ｅ＊（Ｐ）＝５なので、トランザクション｛１，４，５｝から代表を除いた親はＰｒｅ（Ｐ）＝｛１，４｝となり、｛４，５｝と異なるので、トランザクション｛４，５｝とトランザクション｛１，４，５｝は親子関係で結ばれない。また、トランザクション｛１，５｝については、アイテム１，５の全てを含むデータ（包含率１００％）はＤ、１個含まないデータ（包含率５０％）はＡ，Ｂ，Ｃ、全て含まれないデータ（包含率０％）はＥ，Ｆである。ＡｍｂｉＯｃｃ（｛１，５｝）＝｛Ｄ，Ａ，Ｂ｝となり、最大共起数σｐ＝３、平均包含率θｐ＝６６％となり、トランザクション｛４，５｝はあいまい頻出集合Ｐ０の解ではない。したがって、トランザクション｛１，４，５｝についての親子関係はトランザクション｛１，４｝のみについて一意的に成立し、重複することはない。
【００４３】
また、トランザクション｛１，４｝とトランザクション｛１，３，４｝は親子関係で結ばれない。トランザクション｛１，３，４｝について、アイテム１，３，４の全てを含むデータ（包含率１００％）はＡ、１個含まないデータ（包含率６６％）はＤ，Ｆ、２個含まないデータ（包含率３３％）はＢ，Ｃ，Ｅであり、全て含まれないデータ（包含率０％）は無い。ＡｍｂｉＯｃｃ（｛１，３，４｝）＝｛Ａ，Ｄ，Ｆ，Ｂ｝となり、平均包含率θｐは６６％となり、トランザクション｛１，３，４｝もあいまい頻出集合Ｐ０の１つの解であるが、代表ｅ＊（Ｐ）＝１となり、トランザクション｛１，４｝とトランザクション｛１，３，４｝は親子関係で結ばれない。なお、トランザクション｛１，４｝のグループ順序は、｛Ｄ，Ａ， Ｂ，Ｃ，Ｆ｝であり、｛Ａ，Ｄ， Ｆ，Ｂ，Ｃ｝とも並べ替えられるので、トランザクション｛１，３，４｝になってもグループ順序は逆転していない。
【００４４】
次に、列挙木の探索順序について説明する。まず、トランザクション｛１｝について、ＡｍｂｉＯｃｃ（｛１｝）＝｛Ａ，Ｃ，Ｄ，Ｂ｝、最大共起数σ＝４、平均包含率θｐ＝７５％となり、あいまい頻出集合Ｐ０の解であることを求める。次に、トランザクション｛１，２｝〜｛１，７｝について探索を行い、あいまい頻出集合Ｐ０の解でかつ、親子関係が成立するかを求める。あいまい頻出集合Ｐ０の解で親子関係が成立するもの（例えば｛１，ｋ｝）があれば、トランザクション｛１，ｋ｝の子供について同様の探索を行い、あいまい頻出集合Ｐ０の解で親子関係が成立するものがあれば、さらにその子供について探索を行ない、あいまい頻出集合Ｐ０の解で親子関係が成立するものがなくなるまで深さ方向に探索を行なう。次に、トランザクション｛２｝について、ＡｍｂｉＯｃｃ（｛１｝）＝｛Ｂ，Ｃ，Ｅ，Ａ｝、最大共起数σｐ＝４、平均包含率θｐ＝７５％となり、あいまい頻出集合Ｐ０の解であることを求める。同様に、深さ方向に探索を行なう。このようにして、順次深さ方向優先の探索を行い、列挙木を構築する。
【００４５】
よって、各Ｐ∪ｅ（Ｐにｅを付加したもの）の最大共起数σｐを計算するには、ＡｍｂｉＯｃｃ（Ｐ）の各データを包含率でグループ分けしておけば、その中から各Ｐ∪ｅのＡｍｂｉＯｃｃを構成でき、また、各アイテムｅに対して、ｅを含むグループ内のトランザクションを見つけることで、Ｐ∪ｅ の包含率が高いトランザクションを大きい順に見つけることができるので、これを利用すると速く計算できる。最大共起数σｐが大きいアイテム集合は、それほど多くないと思われ、現実的には、一反復の実行時間はＡｍｂｉＯｃｃ（Ｐ）に含まれるアイテムｅの総数に依存し、データベースサイズ‖Ｄ‖に比例する、このため、短時間の計算で解を求めることが可能である。
【００４６】
［第２の実施の形態］
第１の実施の形態ではアイテムが数字の例を説明したが、第２の実施の形態では数字以外の例について説明する。例えば、属性値が実数であるようなデータを扱うことができる。実験結果やセンサーのログなどをデータとし、これを離散化してアイテムｅにすることでトランザクションデータベースＤに変換して利用できる。例えば、属性Ａの数値が０．０〜１．０ならばＡ１、１．０以上ならＡ２、０．０未満ならＡ３というアイテムを含むものとする、というように変換を行なう。このようにして、実験結果をトランザクションの集合として扱い、グループ分けや解析を行なうことが可能である。また、商品に適用すれば、例えばどのような商品が類似グループに属するか、どのような商品の組み合わせ（お弁当とお茶など）が売れ行きが良いのかなどの解析が可能となる。また、コンテンツに対してもどのような類似グループに属するか、どのような組み合わせが良く利用されるかなどの解析ができる。
【００４７】
また、本発明は、以上の実施の形態に記載のあいまい頻出集合の探索方法をコンピュータに実行させるためのプログラムとしても実現可能である。プログラムはコンピュータの内蔵メモリに蓄積して使用してもよく、外付けの記憶装置に蓄積して使用してもよく、インターネットからダウンロードして使用しても良い。また、当該プログラムを記録した記録媒体としても実現可能である。
【００４８】
以上、本発明の実施の形態について説明したが、実施の形態は以上の例に限られるものではなく、本発明の趣旨を逸脱しない範囲で、種々の変更を加え得ることは明白である。
【００４９】
例えば、以上の実施の形態では、アイテムが数字、実験データ、商品の例に言及したが、文字、記号でも良く識別符号で対応可能であれば何でも良い。例えば、音声や映像のコンテンツとしても良く、話者の音声解析、生態系の統計的解析等にも応用できる。また、平均包含率の閾値θ、最大共起数の閾値σは任意に設定できる。
【産業上の利用可能性】
【００５０】
本発明は、データベースのあいまい検索に利用可能である。
【図面の簡単な説明】
【００５１】
【図１】ｋ擬似頻出集合の例を示す図である。
【図２】あいまい頻出集合の例を示す図である。
【図３】あいまい頻出集合の探索方法の処理フロー例を示す図である。
【図４】パターンがあいまい頻出集合に属するか否かを判断する工程を示す図である。
【図５】あいまい頻出集合の探索装置の構成例を示す図である。
【図６】あいまい頻出集合の正規出現の例を示す図である。
【図７】あいまい頻出集合の親子関係を列挙木構造で示す図である。
【図８】正規出現の計算例を示す図である。
【符号の説明】
【００５２】
１００ あいまい頻出集合の探索装置
Ｃ コンピュータ（演算手段）
Ｄ データベース
Ｅ アイテム集合
ｅ アイテム
ｅ＊（Ｐ） 代表
ｋ 擬似頻出集合の係数
Ｍ メモリ
Ｍ０ 頻出パターン探索手段
Ｍ１ 正規出現演算手段
Ｍ２ 代表選定手段
Ｍ３ 親選定手段
Ｍ４ パターン選択手段
Ｐ パターン
Ｐ０ あいまい頻出集合
Ｐ１ 親のパターン
Ｐ２ 子供のパターン
Ｔ トランザクション
Ｔ０ トランザクションの集合
θ 平均包含率の閾値（密度閾値）
θｐ 平均包含率
σ 最大共起数の閾値（ミニマムサポート）
σｐ 最大共起数（頻出度数）
ＡｍｂｉＯｃｃ（Ｐ） 正規出現
Ｐｒｔ（Ｐ） Ｐの親
【特許請求の範囲】
【請求項１】
データベースＤ内に頻繁に現れる頻出パターンＰを、あいまい性を許容して抽出するあいまい頻出集合の探索方法であって；
前記データベースＤのデータが、アイテムｅからなるアイテム集合Ｅの部分集合であるトランザクションＴからなるデータベースＤであり；
前記頻出パターンＰが、構成アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数（最大共起数）が閾値σ以上を条件とするあいまい頻出集合Ｐ０のパターンであり；
前記頻出パターンＰについて、前記データベースＤのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、前記頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算工程と；
前記頻出パターンＰの構成アイテムｅのうち、前記正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定工程と；
前記頻出パターンＰから前記代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定工程と；
前記あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択工程とを備え；
前記パターン選択工程で選択された各候補について、前記正規出現演算工程を用いて前記あいまい頻出集合Ｐ０に属するか否かを判断し、当該候補が前記あいまい頻出集合Ｐ０に属する場合には、前記代表選定工程及び前記親選定工程を用いて親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する；
あいまい頻出集合の探索方法。
【請求項２】
前記パターン選択工程において、深さ優先探索を用いる；
請求項１に記載のあいまい頻出集合の探索方法。
【請求項３】
前記アイテムが商品、コンテンツ、サンプル、その他識別符号で対応付けられたもののいずれかである；
請求項１に記載のあいまい頻出集合の探索方法。
【請求項４】
データベースＤ内に頻繁に現れる頻出パターンＰを、あいまい性を許容して抽出するあいまい頻出集合の探索装置であって；
前記データベースＤのデータが、アイテムからなるアイテム集合Ｅの部分集合であるトランザクションＴからなるデータベースＤであり；
前記頻出パターンＰが、構成アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数（最大共起数）が閾値σ以上を条件とするあいまい頻出集合Ｐ０のパターンであり；
前記頻出パターンＰについて、前記データベースＤのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、前記頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算手段と；
前記頻出パターンＰの構成アイテムｅのうち、前記正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定手段と；
前記頻出パターンＰから前記代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定手段と；
前記あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択手段とを備え；
前記パターン選択手段で選択された各候補について、前記正規出現演算手段を用いて前記あいまい頻出集合Ｐ０に属するか否かを判断し、当該候補が前記あいまい頻出集合Ｐ０に属する場合には、前記代表選定手段及び前記親選定手段を用いて親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する；
あいまい頻出集合の探索装置。
【請求項１】
データベースＤ内に頻繁に現れる頻出パターンＰを、あいまい性を許容して抽出するあいまい頻出集合の探索方法であって；
前記データベースＤのデータが、アイテムｅからなるアイテム集合Ｅの部分集合であるトランザクションＴからなるデータベースＤであり；
前記頻出パターンＰが、構成アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数（最大共起数）が閾値σ以上を条件とするあいまい頻出集合Ｐ０のパターンであり；
前記頻出パターンＰについて、前記データベースＤのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、前記頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算工程と；
前記頻出パターンＰの構成アイテムｅのうち、前記正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定工程と；
前記頻出パターンＰから前記代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定工程と；
前記あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択工程とを備え；
前記パターン選択工程で選択された各候補について、前記正規出現演算工程を用いて前記あいまい頻出集合Ｐ０に属するか否かを判断し、当該候補が前記あいまい頻出集合Ｐ０に属する場合には、前記代表選定工程及び前記親選定工程を用いて親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する；
あいまい頻出集合の探索方法。
【請求項２】
前記パターン選択工程において、深さ優先探索を用いる；
請求項１に記載のあいまい頻出集合の探索方法。
【請求項３】
前記アイテムが商品、コンテンツ、サンプル、その他識別符号で対応付けられたもののいずれかである；
請求項１に記載のあいまい頻出集合の探索方法。
【請求項４】
データベースＤ内に頻繁に現れる頻出パターンＰを、あいまい性を許容して抽出するあいまい頻出集合の探索装置であって；
前記データベースＤのデータが、アイテムからなるアイテム集合Ｅの部分集合であるトランザクションＴからなるデータベースＤであり；
前記頻出パターンＰが、構成アイテムｅの平均包含率が閾値θ以上、かつ、頻出度数（最大共起数）が閾値σ以上を条件とするあいまい頻出集合Ｐ０のパターンであり；
前記頻出パターンＰについて、前記データベースＤのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、前記頻出パターンＰの正規出現ＡｍｂｉＯｃｃ（Ｐ）として求める正規出現演算手段と；
前記頻出パターンＰの構成アイテムｅのうち、前記正規出現ＡｍｂｉＯｃｃ（Ｐ）に含まれる数が最小であるアイテムを代表アイテムｅ＊（Ｐ）と定める代表選定手段と；
前記頻出パターンＰから前記代表アイテムｅ＊（Ｐ）を除いたパターンを親Ｐｒｔ（Ｐ）と定める親選定手段と；
前記あいまい頻出集合Ｐ０の頻出パターンＰの候補を選択するパターン選択手段とを備え；
前記パターン選択手段で選択された各候補について、前記正規出現演算手段を用いて前記あいまい頻出集合Ｐ０に属するか否かを判断し、当該候補が前記あいまい頻出集合Ｐ０に属する場合には、前記代表選定手段及び前記親選定手段を用いて親子関係を決定し、あいまい頻出集合Ｐ０に属する頻出パターンＰを全て抽出する；
あいまい頻出集合の探索装置。
【図３】
【図４】
【図５】
【図１】
【図２】
【図６】
【図７】
【図８】
【図４】
【図５】
【図１】
【図２】
【図６】
【図７】
【図８】
【公開番号】特開２００９−２３０１８６（Ｐ２００９−２３０１８６Ａ）
【公開日】平成２１年１０月８日（２００９．１０．８）
【国際特許分類】
【出願番号】特願２００８−７１１２８（Ｐ２００８−７１１２８）
【出願日】平成２０年３月１９日（２００８．３．１９）
【出願人】（５０４２０２４７２）大学共同利用機関法人情報・システム研究機構 (119)
【Ｆターム（参考）】
【公開日】平成２１年１０月８日（２００９．１０．８）
【国際特許分類】
【出願日】平成２０年３月１９日（２００８．３．１９）
【出願人】（５０４２０２４７２）大学共同利用機関法人情報・システム研究機構 (119)
【Ｆターム（参考）】
[ Back to top ]