TOP > 国内特許検索 > あいまい頻出集合の探索方法及び探索装置 > 明細書

明細書 :あいまい頻出集合の探索方法及び探索装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5267847号 (P5267847)
公開番号 特開2009-230186 (P2009-230186A)
登録日 平成25年5月17日(2013.5.17)
発行日 平成25年8月21日(2013.8.21)
公開日 平成21年10月8日(2009.10.8)
発明の名称または考案の名称 あいまい頻出集合の探索方法及び探索装置
国際特許分類 G06F  17/30        (2006.01)
FI G06F 17/30 220Z
G06F 17/30 350C
請求項の数または発明の数 4
全頁数 20
出願番号 特願2008-071128 (P2008-071128)
出願日 平成20年3月19日(2008.3.19)
審査請求日 平成23年2月23日(2011.2.23)
特許権者または実用新案権者 【識別番号】504202472
【氏名又は名称】大学共同利用機関法人情報・システム研究機構
発明者または考案者 【氏名】宇野 毅明
個別代理人の代理人 【識別番号】100097320、【弁理士】、【氏名又は名称】宮川 貞二
【識別番号】100100398、【弁理士】、【氏名又は名称】柴田 茂夫
【識別番号】100131820、【弁理士】、【氏名又は名称】金井 俊幸
【識別番号】100155192、【弁理士】、【氏名又は名称】金子 美代子
審査官 【審査官】吉田 誠
参考文献・文献 特開2007-018349(JP,A)
宇野毅明,あいまい性を考慮した列挙手法,2007年12月15日,第1-86ページ,[平成24年9月20日検索],インターネット<URL:http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/reports/2007/zentai_2/03-uno.ppt>,URL,http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/reports/2007/zentai_2/03-uno.ppt
宇野 毅明,列挙アルゴリズム,経営の科学 オペレーションズ・リサーチ,日本,社団法人日本オペレーションズ・リサーチ学会,2007年 9月 1日,第52巻 第9号,531-534ページ
宇野 毅明,データインテンシブコンピューティング,人工知能学会誌,日本,(社)人工知能学会,2007年 5月 1日,第22巻 第3号,425-436ページ
中藤 哲也,FFTを用いた繰り返しパターン発見手法の提案,電子情報通信学会技術研究報告,日本,社団法人電子情報通信学会,2003年 7月10日,Vol.103 No.191,97-102ページ
調査した分野 G06F 17/30
特許請求の範囲 【請求項1】
データベースD内に頻繁に現れる頻出パターンPを、あいまい性を許容して抽出するあいまい頻出集合の探索方法であって;
前記データベースDのデータが、アイテムeからなるアイテム集合Eの部分集合であるトランザクションTからなり;
前記頻出パターンPが、構成アイテムeの平均包含率が閾値θ以上、かつ、頻出度数(最大共起数)が閾値σ以上を条件とするあいまい頻出集合P0のパターンであり;
前記あいまい頻出集合P0の親子関係は一意的に定められ、列挙木構造で表され;
前記あいまい頻出集合P0のパターンP1について、構成アイテムeを付加した子供のパターンP2を作成し、前記子供のパターンP2を前記あいまい頻出集合P0のパターンの候補として選択するパターン選択工程と;
前記子供のパターンである頻出パターンPについて、前記データベースDのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、前記頻出パターンPの正規出現AmbiOcc(P)として求めると共に、前記正規出現AmbiOcc(P2)に選択されたデータで、前記平均包含率が閾値θ以上、前記頻出度数(最大共起数)が閾値σ以上になるとき、前記頻出パターンP2をあいまい頻出集合P0のパターンに属すると判断する正規出現演算工程と;
前記あいまい頻出集合P0のパターンに属するとされた頻出パターンPの構成アイテムeのうち、前記正規出現AmbiOcc(P)に含まれる数が最小であるアイテムを代表アイテムe(P)と定める代表選定工程と;
前記頻出パターンPから前記代表アイテムe(P)を除いたパターンで、前記構成アイテムeが付加された元の前記あいまい頻出集合P0のパターンP1と一致するものを親Prt(P)と定める親選定工程とを備え
前記パターン選択工程は、前記正規出現演算工程で前記子供のパターンP2があいまい頻出集合P0のパターンと判断され、前記親選定工程で親Prt(P2)が定められた場合には、さらに子供のパターンP2の子供のパターンを選択し、前記頻出パターンP2があいまい頻出集合P0のパターンに属さないと判断された場合には、前記親のパターンP1に次のアイテムeを付加した子供のパターンを選択し、前記親のパターンP1にアイテムeを付加した子供のパターンが全て選択された後には、前記親のパターンP1の上位の親のパターンについてアイテムeを付加した子供のパターンを選択し;
前記パターン選択工程、前記正規出現演算工程、前記代表選定工程及び前記親選定工程を繰り返し行うことにより、あいまい頻出集合P0に属する頻出パターンPを全て抽出する;
あいまい頻出集合の探索方法。
【請求項2】
前記パターン選択工程において、深さ優先探索を用いる;
請求項1に記載のあいまい頻出集合の探索方法。
【請求項3】
前記アイテムが商品、コンテンツ、サンプル、その他識別符号で対応付けられたもののいずれかである;
請求項1に記載のあいまい頻出集合の探索方法。
【請求項4】
データベースD内に頻繁に現れる頻出パターンPを、あいまい性を許容して抽出するあいまい頻出集合の探索装置であって;
前記データベースDのデータが、アイテムからなるアイテム集合Eの部分集合であるトランザクションTからなり;
前記頻出パターンPが、構成アイテムeの平均包含率が閾値θ以上、かつ、頻出度数(最大共起数)が閾値σ以上を条件とするあいまい頻出集合P0のパターンであり;
前記あいまい頻出集合P0の親子関係は一意的に定められ、列挙木構造で表され;
前記あいまい頻出集合P0のパターンP1について、構成アイテムeを付加した子供のパターンP2を作成し、前記子供のパターンP2を前記あいまい頻出集合P0のパターンの候補として選択するパターン選択手段と;
前記子供のパターンである頻出パターンPについて、前記データベースDのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、前記頻出パターンPの正規出現AmbiOcc(P)として求めると共に、前記正規出現AmbiOcc(P2)に選択されたデータで、前記平均包含率が閾値θ以上、前記頻出度数(最大共起数)が閾値σ以上になるとき、前記頻出パターンP2をあいまい頻出集合P0のパターンに属すると判断する正規出現演算手段と;
前記あいまい頻出集合P0のパターンに属するとされた頻出パターンPの構成アイテムeのうち、前記正規出現AmbiOcc(P)に含まれる数が最小であるアイテムを代表アイテムe(P)と定める代表選定手段と;
前記頻出パターンPから前記代表アイテムe(P)を除いたパターンで、前記構成アイテムeが付加された元の前記あいまい頻出集合P0のパターンP1と一致するものを親Prt(P)と定める親選定手段とを備え
前記パターン選択手段は、前記正規出現演算手段で前記子供のパターンP2があいまい頻出集合P0のパターンと判断され、前記親選定手段で親Prt(P2)が定められた場合には、さらに子供のパターンP2の子供のパターンを選択し、前記頻出パターンP2があいまい頻出集合P0のパターンに属さないと判断された場合には、前記親のパターンP1に次のアイテムeを付加した子供のパターンを選択し、前記親のパターンP1にアイテムeを付加した子供のパターンが全て選択された後には、前記親のパターンP1の上位の親のパターンについてアイテムeを付加した子供のパターンを選択し;
前記パターン選択手段、前記正規出現演算手段、前記代表選定手段及び前記親選定手段を繰り返し使用することにより、あいまい頻出集合P0に属する頻出パターンPを全て抽出する;
あいまい頻出集合の探索装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、あいまい頻出集合の探索方法及び探索装置に関する。詳しくは、データベース内に頻繁に現れる頻出パターンを、あいまい性を許して完全かつ短時間に抽出できる探索方法及び探索装置に関する。
【背景技術】
【0002】
データベース内に頻繁に現れる頻出パターンを抽出する問題は、情報科学の基本問題である。データベースのデータ及びパターンとして、トランザクション、ツリー、グラフ、多次元ベクトル等が、データ及びパターンの要素として、アイテム、部分集合、木、パス・サイクル、グラフ、図形等が挙げられる。特に、データベースDのデータがアイテム集合Eの部分集合であるトランザクションTである場合に、頻出パターンを全て抽出する問題は頻出パターン列挙問題と云われている。この場合、完全一致検索の問題であれば容易に解決できる。他方、あいまい性を許して多くのデータに含まれるパターンを抽出するあいまい検索は、ゲノムの相同検索等で大いに実用的である。しかし、完全一致検索の問題からこのようなあいまい検索の問題になると、とたんに難しくなる。
【0003】
アイテム集合Eに対して、あいまいな包含関係を考え、頻出集合を列挙するアルゴリズムに関して、従来の解決方法は、包含率の閾値θを定め、全てのデータを照合するか、ヒューリステックな検索をして、多数ではあるが不完全な頻出集合を抽出するかのどちらかであった。(非特許文献1~3参照)
【0004】

【非特許文献1】C.Yang,U.Fayyad,P.S.Bradley,“Efficient Discovery of Error-Tolerant Frequent Itemsets in High Dimensions”,SIGKDD2001,2001.
【非特許文献2】J.Besson,C.Robardet,and J.F.Boulicaut,“Mining Formal Concepts with a Bounded Number of Exceptions from Transactional Data”,KDID 2004,LNCS 3377,pp.33-45,2005.
【非特許文献3】W.Shen-Shung and L.Suh-Yin,“Mining Fault-Tolerant Frequent Patterns inLarge Databases”,ICS2002,2002.
【発明の開示】
【発明が解決しようとする課題】
【0005】
しかしながら、全てのデータを照合する方法は小さいデータベースでは完全抽出できるが、大きいデータベースでは非実用的であった。また、ヒューリステックな検索でも、全てのパターンを完全に抽出できるアルゴリズムは見出されていない。
【0006】
本発明は、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索方法及び探索装置を提供することを目的とする。
【課題を解決するための手段】
【0007】
上記課題を解決するために、本発明の第1の態様によるあいまい頻出集合の探索方法は、例えば、図3に示すように、データベースD内に頻繁に現れる頻出パターンPを、あいまい性を許容して抽出するあいまい頻出集合の探索方法であって、データベースDのデータが、アイテムeからなるアイテム集合Eの部分集合であるトランザクションTからなり、頻出パターンPが、構成アイテムeの平均包含率が閾値θ以上、かつ、頻出度数(最大共起数)が閾値σ以上を条件とするあいまい頻出集合P0のパターンであり、頻出パターンPについて、データベースDのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンPの正規出現AmbiOcc(P)として求める正規出現演算工程(S20~S50)と、頻出パターンPの構成アイテムeのうち、正規出現AmbiOcc(P)に含まれる数が最小であるアイテムを代表アイテムe(P)と定める代表選定工程(S60)と、頻出パターンPから代表アイテムe(P)を除いたパターンを親Prt(P)と定める親選定工程(S70~S90)と、あいまい頻出集合P0の頻出パターンPの候補を選択するパターン選択工程(S10,S100)とを備え、パターン選択工程(S10,S100)で選択された各候補について、正規出現演算工程(S20~S50)を用いてあいまい頻出集合P0に属するか否かを判断し、当該候補があいまい頻出集合P0に属する場合には、代表選定工程(S60)及び親選定工程(S70~S90)を用いて親子関係を決定し、あいまい頻出集合P0に属する頻出パターンPを全て抽出する。
【0008】
ここにおいて、あいまい性の程度は、平均包含率の閾値θ及び頻出度数(最大共起数)の閾値σにより枠決めされる。また、アイテムeは明細書中では説明の便宜上、数字としたが、文字、記号でも良く識別符号で対応可能であれば何でも良い。例えば、商品、コンテンツ、サンプルでも良い。また、包含率とは、パターンPを構成するアイテムeの総数のうち、データに含まれるアイテム数の割合をいい、平均包含率θpとは、複数のデータについて包含率を平均化したものをいう。また、最大共起数σpとは、平均包含率が閾値θ以上となるように選択された最大のデータ数をいう。この態様のように構成すると、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索方法を提供できる。
【0009】
また、本発明の第2の態様によるあいまい頻出集合の探索方法は、第1の態様において、パターン選択工程において、深さ優先探索を用いる。このように構成すると、親の正規出現から子供の正規出現を導き出せることを利用して、効率的に探索ができる。
【0010】
また、本発明の第3の態様によるあいまい頻出集合の探索方法は、第1の態様において、アイテムが商品、コンテンツ、サンプル、その他識別符号で対応付けられたもののいずれかである。このように構成すると、商品販売データ、実験データの解析等に役立てられる。
【0011】
上記課題を解決するために、本発明の第4の態様によるあいまい頻出集合の探索装置100は、例えば、図5に示すように、データベースD内に頻繁に現れる頻出パターンPを、あいまい性を許容して抽出するあいまい頻出集合の探索装置であって、データベースDのデータが、アイテムからなるアイテム集合Eの部分集合であるトランザクションTからなり、頻出パターンPが、構成アイテムeの平均包含率が閾値θ以上、かつ、頻出度数(最大共起数)が閾値σ以上を条件とするあいまい頻出集合P0のパターンであり、頻出パターンPについて、データベースDのデータから、前記条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンPの正規出現AmbiOcc(P)として求める正規出現演算手段M1と、頻出パターンPの構成アイテムeのうち、正規出現AmbiOcc(P)に含まれる数が最小であるアイテムを代表アイテムe(P)と定める代表選定手段M2と、頻出パターンPから代表アイテムe(P)を除いたパターンを親Prt(P)と定める親選定手段M3と、あいまい頻出集合P0の頻出パターンPの候補を選択するパターン選択手段M4とを備え、パターン選択手段M4で選択された各候補について、正規出現演算手段M1を用いてあいまい頻出集合P0に属するか否かを判断し、当該候補があいまい頻出集合P0に属する場合には、代表選定手段M2及び親選定手段M3を用いて親子関係を決定し、あいまい頻出集合P0に属する頻出パターンPを全て抽出する。
【0012】
ここにおいて、解決装置100はデータベースDを有しても良いが、有さなくてもアクセス可能であれば良い。また、各手段は1つのコンピュータC内に構成されても良く、それぞれ、別のコンピュータで構成されても良い。また、1つのコンピュータC内に構成される場合に、各手段毎に別個のハードウエアに構成されても良いが、1つのコンピュータCが各手段の機能を有するならば、各手段がコンピュータ内に構成されているとみなして良い。この態様のように構成すると、あいまい頻出集合のパターンを完全かつ短時間に抽出する探索装置を提供できる。
【発明の効果】
【0013】
本発明によれば、あいまい頻出集合のパターンを完全かつ短時間に抽出できる探索方法及び探索装置を提供できる。
【発明を実施するための最良の形態】
【0014】
[頻出集合について]
まず、頻出集合について説明する。アイテム集合Eはアイテムe=1,2・・・nの組み合わせからなる集合であり、データベースDはアイテム集合Eの部分集合であるトランザクションTの集合からなるものとする。データベースDが有するトランザクション数を|D|、トランザクションTが有するアイテム数を|T|とする(同様に| |は数を表すものとする)。データベースサイズを∥D∥=|D|+ΣT∈D|T|と定義する。すなわち、データベースDが有するトランザクション数と各トランザクションが有するアイテム数の総和である。データベースサイズ∥D∥はコンピュータ計算時間を求めるために用いられる。ここで、アイテム集合Eの部分集合であるパターンP(トランザクション)に注目する。データベースD内でパターンPが出現するものの集合を出現集合Occ(P)、パターンPの出現頻度をfrq(P)(=|Occ(P)|)とする。また、データベースD内でパターンPのアイテムをh個含まないものの集合をOcc=h(P)={T|T∈D,|P\T|=h}(P\TはPとTの差異を示す)、h個以下含まないものの集合をOcc≦h(P)={T|T∈D,|P\T|≦h}とする。データベースD内に、出現頻度が閾値σ以上出現するパターンの集合を頻出集合という。この閾値σをミニマムサポート(最小頻度)という。データベースDと閾値σが与えられた時に、頻出集合の全ての解を求める問題を頻出集合列挙問題という。
【0015】
図1にk擬似頻出集合の例を示す。データベースDのデータがアイテム集合E(アイテムe)の部分集合からなるトランザクションTであり、データベースDが図の左側に示すような6データを有しているものとする。k擬似頻出集合とは、データベースD内のσ個以上のデータ(トランザクション)にk擬似包含の意味で含まれる(k個以下の異なるアイテムがあっても良いことを意味する)アイテム集合であって、図の右側にσ=3、k=1での擬似頻出集合の例を示す。例えば、パターン{1,2,3}について、データ{1,2,5,6,7,9}及び{1,2,7,8,9}はアイテム1と2を含み、3を含まない。データ{2,3,4,5}はアイテム2と3を含み、1を含まない。このように、3個のアイテム中、k=1個以下のアイテムが異なるデータが3個、すなわち、閾値σ=3以上ある。また、パターン{1,2,7,9}ついて、データ{1,2,5,6,7,9}及び{1,2,7,8,9}は全てのアイテムを含む。データ{1,7,9}及び{2,7,9}は3個のアイテムを含み、1個のアイテムを含まない。このように、4個のアイテム中、k=1個以下のアイテムが異なるデータが4個、すなわち、閾値σ=3以上ある。このようなパターン(トランザクション)は図に示すように3個のアイテムを有するものが33個、4個のアイテムを有するものが11個ある。
【0016】
k擬似頻出集合を含め、頻出集合列挙問題の解を全て列挙するのは容易である。その理由は、単調性が保持されているので(解の任意の部分集合も解になっているので)、任意の頻出集合は、頻出集合の域内で、空集合に順次アイテムを付加することによって得ることができるからである。親のパターン(トランザクション)にアイテムeを1つ付加したものを子供のパターン(トランザクション)という。空集合以外の頻出集合の任意のパターンは親を持つので、この親子関係は頻出集合の全てのパターンを関係付ける列挙木を導き出す。列挙木を探索することにより、頻出集合の全ての解を見つけることができる。ただし、各親について可能な子供を全て探索すると子供のトランザクションに重複が生じるが、唯一の親を選択してアイテムを付加するような秩序を導入することにより重複を避けられる。単調性が保持されていれば、分岐限定法的なアプローチを用いることができる。すなわち、どのアイテムを加えるかで場合分けを繰り返すことにより、簡単に重複を回避しつつ解を列挙できる。
【0017】
[あいまい頻出集合について]
次に、あいまい頻出集合P0について説明する。パターンPのアイテムeのうちトランザクションTに含まれるアイテムの割合を包含率といい、(|T∩P|/|T|)(T∩PはTとPが共有するアイテムを示す)で示される。次に、パターンPのアイテムのうちトランザクションTの集合T0に含まれる平均包含率θpを考える。平均包含率θpは集合T0に含まれる各トランザクションTに対する包含率を平均したもの(ΣT∈T0|T∩P|)/(|T||P|)である。平均包含率θpが閾値(密度閾値)θ以上となる最大数のトランザクションの集合をPの最大共起集合という。その集合に含まれるトランザクションの数をPの最大共起数といい、σp=cov(P)で表す。トランザクションデータベースD,最大共起数cov(P)が閾値(ミニマムサポート)σ以上、平均包含率θpが閾値(密度閾値)θ以上のあいまい頻出集合P0の全ての解を求める問題を、あいまい頻出集合列挙問題という。すなわち、あいまい頻出集合列挙問題とは、与えられたトランザクションデータベースD、密度閾値θ、ミニマムサポート(最小頻度)σに対し、データベースDに対するあいまい頻出集合P0の解(パターンP)を全て出力する問題をいう。
【0018】
図2にあいまい頻出集合P0の例を示す。データベースDのデータがアイテム集合Eの部分集合からなるトランザクションTであり、データベースDが図の左側に示すような3データを有しているものとする。例えば、パターン(トランザクション){2,3}については、データ{1,3,4}には2が無く3が有るので、包含率50%、データ{2,4,5}及び{1,2}には2が有り3が無いので、包含率50%であり、これらの平均包含率θpは50%である。パターン{4,5}については、データ{1,3,4}には4が有り5が無いので、包含率50%、データ{2,4,5}には4及び5が有るので、包含率100%、データ{1,2}には4及び5が無いので、包含率0%であり、これらの平均包含率θpは50%である。パターン{1,2}については、データ{1,3,4}には1が有り2が無いので、包含率50%、データ{2,4,5}には1が無く2が有るので、包含率50%、データ{1,2}には1及び2が有るので、包含率100%であり、これらの平均包含率θpは66%である。ここで、平均包含率の閾値θ=50%を条件とすれば、3個のデータが該当し、閾値θを66%を条件とすれば、1個のデータ{1,2}が該当する。また、以上の平均包含率θpについては3個のデータの平均包含率をとっているので、最大共起数は閾値σ=3を満たす。もし、最大共起数の閾値σ=2とすれば、パターン{4,5}に対しては、データ{1,3,4}及びデータ{2,4,5}を選択でき、平均包含率θp=75%となる。もし、平均包含率の閾値(密度閾値)θ=66%、最大共起数の閾値(ミニマムサポート)σ=3を条件とすると、データベースDに対するあいまい頻出集合として図中の3つのパターンのうちではパターン{1,2}のみが該当する。なお、図示しないが、パターン{1}や{2}などもあいまい頻出集合P0に該当する。この例ではデータが少ないので、あいまい頻出集合P0の解を全て列挙するのは容易である。
【0019】
任意の頻出集合は、単調性が保持されていれば、頻出集合の域内で、空集合に順次アイテムを付加することによって得ることができる。しかしながら、あいまい頻出集合P0は単調性を保持しないので、分岐限定法的なアプローチを適用できそうにない。また、あいまい頻出集合が存在するか否かの判定はNP完全と呼ばれる難しい問題に属する。そこで、多項式遅延多項式空間の逆探索アルゴリズムを用いる。この場合、各頻出集合のコンピュータ計算時間はデータベースサイズ∥D∥に比例し、O(∥D∥)と表される。
【0020】
多項式遅延多項式空間のアルゴリズムとは次ぎのようなアルコリズムをいう。もし、アルゴリズムの計算時間が、解の数の線形であるならば、不要な計算をあまりしていないと考えられるため、実用的に優れている。また、アルゴリズムのメモリ使用量が入力サイズの多項式であるなら、解が多量であってもメモリ不足を起こすことがない。本発明では、あいまい頻出集合列挙問題を解決する、このような、解の数に線形の時間で動き、入力の多項式サイズのメモリしか消費しない多項式遅延多項式空間のアルゴリズムを使用する。
【0021】
[第1の実施の形態]
第1の実施の形態では、あいまい頻出集合P0の解を全て列挙できるアルゴリズムとして、擬似頻出集合の多項式遅延多項式空間アルゴリズムを用いて、逆探索的アプローチを行うこととする。
【0022】
あいまい頻出集合P0に属するパターンPの最大共起集合のうち、辞書順最小のものをあいまい頻出集合Pの正規出現AmbiOcc(P)と定義する。すなわち、あいまい頻出集合P0に属するパターンPの正規出現AmbiOcc(P)はデータベースDに含まれるトランザクションTを包含率の大きいものから順次選択し、同率のものがあれば、ID(識別符号)の小さいほうを優先して並べることによって得られる。そして、空集合以外(P≠0)のパターンPに含まれるアイテムeのうち、正規出現AmbiOcc(P)に含まれる数|AmbiOcc(P)∩Occ({e})|が最小のアイテムを代表e(P)と定義する。すなわち、密度が一番小さいアイテムを除くことにより親子関係を定める。代表e(P)を用いることにより、あいまい頻出集合P0に明確な探索ルートを決めることができる。
【0023】
定理1. P≠0の任意のアイテム集合のパターンPに対して、cov(P\{e})(Pからeを除いたものの最大共起数)≧cov(P)(Pの最大共起数)を満たすアイテムe∈Pが存在する。
【0024】
証明: あいまい頻出集合のパターンPに対する正規出現AmbiOcc(P)の平均包含率は、Σe∈P|AmbiOcc(P)∩Occ({e})|/[(P-1)×|AmbiOcc(P)|]なので、|AmbiOcc(P)∩Occ({e})|/|AmbiOcc(P)|の平均値で与えられる。親P\{e(P)}に対するAmbiOcc(P)の平均包含率は、P\{e(P)}の中の|AmbiOcc(P)∩Occ({e})|/|AmbiOcc(P)|の平均値であり、Pに対するAmbiOcc(P)の平均包含率以上である。このことは、cov(P\{e})はcov(P)以上であり、代表e(P)が主題のアイテムeであるという条件を満たす。
【0025】
また、P≠0のアイテム集合のパターンPに対して、Pの親をPrt(P)=P\{e(P)}(Pから代表を除いたもの)と定める。すなわち、親は子から代表e(P)を除いたものをいう。定理1より、P\{e(P)}もまたあいまい頻出集合に属する。特に、cov(Prt(P))≦cov(P)が成り立つ。親Prt(P)は子供Pに比して含むアイテムeが1つ少なく、このようにして導入された親子関係はあいまい頻出集合の各パターンに対して1つの親が対応し、親子関係が一意的に定まる。空集合以外の任意の頻出集合は親を持つので、この親子関係はあいまい頻出集合の全てのパターンを関係付ける列挙木を導き出す。そして、列挙木を探索することにより、重複なしにあいまい頻出集合の全ての解(パターン)を見つけることができる。列挙木に深さ優先探索を行ない、見つけた子供に対し再帰的に子供を見つけることにより、メモリを付加すること無く、探索を実行できる。
【0026】
あいまい頻出集合のパターンPに対する逆探索アルゴリズムは次のようになる。
(1)パターンPを出力する。
(2)Pに含まれない各アイテムeに対して
(2a)もしPにeを付加したものP∩{e}があいまい頻出集合に属するのであれば、
(2b)もしその親Prt{P∩{e}}=Pであれば、
(2c){P∩{e}}を逆探索する。
【0027】
(2a)と(2b)における平均包含率とPにeを付加したものP∩{e}の親を求める計算は時間O(∥D∥)でなされる。繰り返しは高々n倍(任意のパターンの子供の数は高々n)であり、あいまい頻出集合のコンピュータ計算時間はO(∥D∥×n)でなされる。また、列挙木の深さは高々nであり、次の定理が導かれる。
【0028】
定理2.与えられたトランザクションデータベースD、ミニマムサポートの閾値σ、平均包含率の閾値θに対して、任意のあいまい頻出集合は、1つの集合あたり∥D∥に線形のコンピュータ計算時間で、∥D∥の大きさのメモリを用いて求められる。
【0029】
図3にあいまい頻出集合の探索方法の処理フロー例を示す。全体のフローをあいまい頻出集合の探索工程として示す。あいまい頻出集合の探索工程は、頻出パターンPについて、データベースDのデータから、あいまい頻出集合の条件を満たす範囲で包含率が大きい順に最大数選択したものを、頻出パターンPの正規出現AmbiOcc(P)として求める正規出現演算工程と、頻出パターンPの構成アイテムeのうち、正規出現AmbiOcc(P)に含まれる数が最小であるアイテムを代表アイテムe(P)と定める代表選定工程と、頻出パターンPから代表アイテムe(P)を除いたパターンを親Prt(P)と定める親選定工程と、あいまい頻出集合P0の頻出パターンPの候補を選択するパターン選択工程とを備える。
【0030】
まず、あいまい頻出集合P0の候補としてパターンP1を選択する(S10)。これはパターン選択工程に属する。パターンP1の選択は空集合φから、アイテムeを1つずつ付加していき、あいまい頻出集合P0に属するか否かを判断していく。子供があいまい頻出集合に属するのであれば、さらにその子供について探索する深さ優先探索を行なうと効率的である。すなわち、パターンP1を選択したら、次に、アイテムeを選択して(S20)パターンP1に付加して子供のパターンP2を作成し(S30)、子供P2=P∩{e}があいまい頻出集合に属するか否かを判断する(S40)。
【0031】
図4に、パターンがあいまい頻出集合に属するか否かを判断する工程(S40)を示す。あいまい頻出集合P0の候補パターンP2に対して(S41)、まず、データベースDのデータを包含率の高い順に並べる(S42)。次に、平均包含率θpが閾値(密度閾値)θ以上の範囲で、包含率の高い順にデータを取得し、データ数が最大になるように取得して集合を形成する(S43)。包含率が同じデータについては辞書順最小のものから選択する。次に、取得した集合のデータ数、すなわち最大共起数(頻出度数)σpが閾値σ(ミニマムサポート)以上か否かを判断する(S44)。取得した集合のデータ数が閾値σ以上であれば、子供P2=P1∩{e}があいまい頻出集合P0に属すると判断し(S45)、閾値σ以上でなければ、子供P2=P1∩{e}があいまい頻出集合P0に属さないと判断する(S46)。
【0032】
ここで、図3に戻る。子供P2があいまい頻出集合P0に属さない場合(S40でN)は、ステップS20に戻り、あいまい頻出集合P0の候補P1に対して次のアイテムeを選択する。子供P2があいまい頻出集合P0に属する場合(S40でY)は、取得した集合がパターンP2の正規出現AmbiOcc(P2)として求まる(S50)。アイテムe選択から正規出現AmbiOcc(P2)を求めるまでの工程(S10~S50)は正規出現演算工程に属する。
【0033】
次に子供P2=P1∩{e}について代表e(P2)を求める(S60)。これは代表選定工程に属する。子供P2=P1∩{e}のアイテムのうち、パターンP2の正規出現AmbiOcc(P2)に含まれる数が最小のものを代表e(P2)として選定する。次に、子供P2=P1∩{e}の親Pre(P2)を求める(S70)。パターンP2から代表e(P2)を除くことにより親Pre(P2)=P2\{e(P2)}を求める。次に、求めた親Pre(P2)がP1であるか否かを判断する(S80)。P1であれば(S80でY)、求めた親Pre(P2)が真の親であり、親子関係が決まる(S90)。P1でなければ(S80でN)、求めた親Pre(P2)が真の親ではなく、ステップS20に戻り、次のアイテムeを選択する。親Pre(P)の演算から親子関係が決まるまでの工程(S70~S90)は親選定工程に属する。
【0034】
親子関係が定まれば、次のパターンを選択して探索を行う(S100でS10に戻る)。これはパターン選択工程に属する。子供があいまい頻出集合P0に属するのであれば、さらにその子供について再帰的に探索する。子供があいまい頻出集合P0に属するのでなければ、親に戻って、次のアイテムeを選択し、探索する。すべてのアイテムeについて探索が終了したら、さらに上位の親に戻って探索を行う。すなわち、次の候補パターンPがあれば(S100でY、S10に戻る)、その候補についてあいまい頻出集合P0に属するか否かを判断し、全てのあいまい頻出集合P0の候補パターンがなくなる(S100でN)まで探索を行う。
【0035】
図5にあいまい頻出集合の探索装置の構成例を示す。あいまい頻出集合の探索装置100は、コンピュータ(演算手段)C、データベースD、メモリMを備える。コンピュータCは頻出パターン探索手段M0を有する。頻出パターン探索手段M0は、例えば、あいまい頻出集合の探索方法のプログラムをコンピュータCにインストールすることにより実現できる。なお、ハードウエアで実現しても良い。頻出パターン探索手段M0は、正規出現演算手段M1、代表選定手段M2、親選定手段M3、パターン選択手段M4を有する。正規出現演算手段M1は正規出現演算工程(S10~S50)を実行し、代表選定手段M2は代表選定工程(S60)を実行し、親選定手段M3は親選定工程(S70~S90)を実行し、パターン選択手段M4はパターン選択工程(S10、S100)を実行する。この構成により、あいまい頻出集合を完全かつ短時間に抽出できる探索装置を提供できる。
【0036】
図6に、あいまい頻出集合の正規出現AmbiOcc(P)の例を示す。データベースDのデータA~Fを左側に示す。平均包含率θpの閾値(密度閾値)θ=66%、最大共起数(頻出度数)σpの閾値(ミニマムサポート)σ=4とする。トランザクション(パターン){1,4,5}について、アイテム1,4,5の全てを含むデータ(包含率100%)はD、1個含まないデータ(包含率66%)はA,B、2個含まないデータ(包含率33%)はC,F、全て含まれないデータ(包含率0%)はEであり、4グループに分かれる。これらを包含率の高いものから4とると、AmbiOcc({1,4,5})={D,A,B,C}となり、平均包含率θpは66%((100+66+66+33)/4)となり、トランザクション{1,4,5}はあいまい頻出集合P0の1つの解であることが分かる。CとFについては辞書順からCが選択される。ここで、トランザクション(パターンP){1,4,5}について、代表e*(P)を求める。トランザクション{1,4,5}のアイテム1及び4は{D,A,B,C}のうち3データに含まれ、アイテム5は2データに含まれる。したがって、代表e(P)=5となる。また、親Prt({1,4,5})は、トランザクション{1,4,5}から代表5を除いた{1,4}となる。
【0037】
また、親となるトランザクション(パターン){1,4}について、アイテム1,4の全てを含むデータ(包含率100%)はD,A、1個含まないデータ(包含率50%)はB,C,F、全て含まれないデータ(包含率0%)はEであり、3グループに分かれる。AmbiOcc({1,4})={D,A,B,C,F}となり、最大共起数σp=5>σ=4、平均包含率θp=70%((100×2+50×3)/5)>θ=66%となり、トランザクション{1,4}もあいまい頻出集合P0の1つの解であることが分かる。このように、親は子供よりアイテム数が1小さく、親子関係は非巡回的(親を辿っていくことにより自分自身に戻ることはない)である。また親は子供より最大共起数が大きいか等しく、子供があいまい頻出集合P0に含まれる場合は、親もあいまい頻出集合P0に含まれる。
【0038】
図7に、あいまい頻出集合P0の親子関係を列挙木構造で示す。データベースDのデータA~Fを左側に示す。平均包含率θpの閾値(密度閾値)θ=66%、最大共起数(頻出度数)σpの閾値(ミニマムサポート)σ=4とする。親子関係の列挙木構造を右側に示す。親子関係は矢印で示される。トランザクション(パターン){1,4,5}の親は{1,4}であり、{4,5}ではない。また、トランザクション(パターン){1,4}の親は{4}であり、{1}ではない。このように親子関係は一意的に定められる。このようにして、全ての解(20個の解)が列挙木構造で表される。なお、φはアイテムが何も無い空集合を示す。
【0039】
列挙木を探索すれば、あいまい頻出集合P0に属する全てのパターンPを見つけることができる。さらに、深さ優先で探索すれば、列挙木の深さは深くてもアイテム数までであり、解をメモリに保存する必要もない。このような列挙木の深さを探索するには、与えられた頂点にある親の子供を順次見つけ、見つけた子供に対して、再帰的に子供を見つけていけばよい。子供は親にアイテムを1個付け加えることにより得られる。しかし、親にアイテムを付け加えて得られる子供があいまい集合P0に属する場合でも、付け加えたアイテムが代表アイテムでなければ、真の親ではなく、異なる親が在ることになる。したがって、代表e(P)を求めることにより、親子関係を照合しながら列挙木を探索することとなる。
【0040】
あいまい頻出集合P0の最大共起数σpは、データベースDのデータから包含率の高い順にトランザクションを選択して得ることができる。しかも、アイテムeの付加により、この包含率は逆転することはないので、データの配列順序は逆転しない。すなわち、トランザクション(パターンP)の最大共起数σpを計算するに際して、包含率の大きさ順にデータベースDに含まれるトランザクションをグループ分けすると、パターンPに対する包含率の順序は、そのまま、親P∪eに対する包含率の順になる。したがって親のAmbiOcc(P∪e)から子供のAmbiOcc(P)を求めることができ、また、親のAmbiOcc(P∪e)について、含まれる数が最小であるアイテムを抽出することにより、代表e(P)を求めることができる。
【0041】
図8に、トランザクション(パターン)P={1,4}に、アイテムe=5を付加したときの正規出現AmbiOcc(P∪e)の計算例を示す。データベースDのデータA~F(図6及び図7と同じ)を左側に示す。平均包含率θpの閾値(密度閾値)θ=66%、最大共起数σpの閾値(ミニマムサポート)σ=4とする。親のトランザクション{1,4}について、アイテム1,4の全てを含むデータ(包含率100%)はD,A、1個含まないデータ(包含率50%)はB,C,F、全て含まれないデータ(包含率0%)はEであり、3グループに分かれる。AmbiOcc({1,4})={D,A,B,C,F}となり、最大共起数σp=5>σ=4、平均包含率θp=70%となり、トランザクション{1,4}もあいまい頻出集合P0の1つの解である。また、子供のトランザクション(パターン){1,4,5}について、アイテム1,4,5の全てを含むデータ(包含率100%)はD、1個含まないデータ(包含率66%)はA,B、2個含まないデータ(包含率33%)はC,F、全て含まれないデータ(包含率0%)はEであり、4グループに分かれる。AmbiOcc({1,4,5})={D,A,B,C}となり、平均包含率θpは66%となり、トランザクション{1,4,5}もあいまい頻出集合P0の1つの解であることが分かる。CとFについては辞書順からCが選択される。ここで、トランザクション{1,4,5}について、代表e(P)を求める。トランザクション{1,4,5}のアイテム1及び4は{D,A,B,C}のうち3データに含まれ、アイテム5は2データに含まれる。したがって、代表e(P)=5となる。また、親Prt({1,4,5})は、トランザクション{1,4,5}から代表5を除いた{1,4}となる。したがって、トランザクション{1,4}とトランザクション{1,4,5}は親子関係で結ばれる。
【0042】
しかし、トランザクション{4,5}とトランザクション{1,4,5}は親子関係で結ばれない。親のトランザクション{4,5}について、アイテム4,5の全てを含むデータ(包含率100%)はB,D、1個含まないデータ(包含率50%)はA,F、全て含まれないデータ(包含率0%)はC,Eである。AmbiOcc({4,5})={B,D,A,F}となり、最大共起数σp=4、平均包含率θp=75%となり、トランザクション{4,5}もあいまい頻出集合P0の1つの解である。しかし、AmbiOcc({1,4,5})={D,A,B,C}となり、平均包含率θpは66%となり、代表e(P)=5なので、トランザクション{1,4,5}から代表を除いた親はPre(P)={1,4}となり、{4,5}と異なるので、トランザクション{4,5}とトランザクション{1,4,5}は親子関係で結ばれない。また、トランザクション{1,5}については、アイテム1,5の全てを含むデータ(包含率100%)はD、1個含まないデータ(包含率50%)はA,B,C、全て含まれないデータ(包含率0%)はE,Fである。AmbiOcc({1,5})={D,A,B}となり、最大共起数σp=3、平均包含率θp=66%となり、トランザクション{4,5}はあいまい頻出集合P0の解ではない。したがって、トランザクション{1,4,5}についての親子関係はトランザクション{1,4}のみについて一意的に成立し、重複することはない。
【0043】
また、トランザクション{1,4}とトランザクション{1,3,4}は親子関係で結ばれない。トランザクション{1,3,4}について、アイテム1,3,4の全てを含むデータ(包含率100%)はA、1個含まないデータ(包含率66%)はD,F、2個含まないデータ(包含率33%)はB,C,Eであり、全て含まれないデータ(包含率0%)は無い。AmbiOcc({1,3,4})={A,D,F,B}となり、平均包含率θpは66%となり、トランザクション{1,3,4}もあいまい頻出集合P0の1つの解であるが、代表e(P)=1となり、トランザクション{1,4}とトランザクション{1,3,4}は親子関係で結ばれない。なお、トランザクション{1,4}のグループ順序は、{D,A, B,C,F}であり、{A,D, F,B,C}とも並べ替えられるので、トランザクション{1,3,4}になってもグループ順序は逆転していない。
【0044】
次に、列挙木の探索順序について説明する。まず、トランザクション{1}について、AmbiOcc({1})={A,C,D,B}、最大共起数σ=4、平均包含率θp=75%となり、あいまい頻出集合P0の解であることを求める。次に、トランザクション{1,2}~{1,7}について探索を行い、あいまい頻出集合P0の解でかつ、親子関係が成立するかを求める。あいまい頻出集合P0の解で親子関係が成立するもの(例えば{1,k})があれば、トランザクション{1,k}の子供について同様の探索を行い、あいまい頻出集合P0の解で親子関係が成立するものがあれば、さらにその子供について探索を行ない、あいまい頻出集合P0の解で親子関係が成立するものがなくなるまで深さ方向に探索を行なう。次に、トランザクション{2}について、AmbiOcc({1})={B,C,E,A}、最大共起数σp=4、平均包含率θp=75%となり、あいまい頻出集合P0の解であることを求める。同様に、深さ方向に探索を行なう。このようにして、順次深さ方向優先の探索を行い、列挙木を構築する。
【0045】
よって、各P∪e(Pにeを付加したもの)の最大共起数σpを計算するには、AmbiOcc(P)の各データを包含率でグループ分けしておけば、その中から各P∪eのAmbiOccを構成でき、また、各アイテムeに対して、eを含むグループ内のトランザクションを見つけることで、P∪e の包含率が高いトランザクションを大きい順に見つけることができるので、これを利用すると速く計算できる。最大共起数σpが大きいアイテム集合は、それほど多くないと思われ、現実的には、一反復の実行時間はAmbiOcc(P)に含まれるアイテムeの総数に依存し、データベースサイズ∥D∥に比例する、このため、短時間の計算で解を求めることが可能である。
【0046】
[第2の実施の形態]
第1の実施の形態ではアイテムが数字の例を説明したが、第2の実施の形態では数字以外の例について説明する。例えば、属性値が実数であるようなデータを扱うことができる。実験結果やセンサーのログなどをデータとし、これを離散化してアイテムeにすることでトランザクションデータベースDに変換して利用できる。例えば、属性Aの数値が0.0~1.0ならばA1、1.0以上ならA2、0.0未満ならA3というアイテムを含むものとする、というように変換を行なう。このようにして、実験結果をトランザクションの集合として扱い、グループ分けや解析を行なうことが可能である。また、商品に適用すれば、例えばどのような商品が類似グループに属するか、どのような商品の組み合わせ(お弁当とお茶など)が売れ行きが良いのかなどの解析が可能となる。また、コンテンツに対してもどのような類似グループに属するか、どのような組み合わせが良く利用されるかなどの解析ができる。
【0047】
また、本発明は、以上の実施の形態に記載のあいまい頻出集合の探索方法をコンピュータに実行させるためのプログラムとしても実現可能である。プログラムはコンピュータの内蔵メモリに蓄積して使用してもよく、外付けの記憶装置に蓄積して使用してもよく、インターネットからダウンロードして使用しても良い。また、当該プログラムを記録した記録媒体としても実現可能である。
【0048】
以上、本発明の実施の形態について説明したが、実施の形態は以上の例に限られるものではなく、本発明の趣旨を逸脱しない範囲で、種々の変更を加え得ることは明白である。
【0049】
例えば、以上の実施の形態では、アイテムが数字、実験データ、商品の例に言及したが、文字、記号でも良く識別符号で対応可能であれば何でも良い。例えば、音声や映像のコンテンツとしても良く、話者の音声解析、生態系の統計的解析等にも応用できる。また、平均包含率の閾値θ、最大共起数の閾値σは任意に設定できる。
【産業上の利用可能性】
【0050】
本発明は、データベースのあいまい検索に利用可能である。
【図面の簡単な説明】
【0051】
【図1】k擬似頻出集合の例を示す図である。
【図2】あいまい頻出集合の例を示す図である。
【図3】あいまい頻出集合の探索方法の処理フロー例を示す図である。
【図4】パターンがあいまい頻出集合に属するか否かを判断する工程を示す図である。
【図5】あいまい頻出集合の探索装置の構成例を示す図である。
【図6】あいまい頻出集合の正規出現の例を示す図である。
【図7】あいまい頻出集合の親子関係を列挙木構造で示す図である。
【図8】正規出現の計算例を示す図である。
【符号の説明】
【0052】
100 あいまい頻出集合の探索装置
C コンピュータ(演算手段)
D データベース
E アイテム集合
e アイテム
(P) 代表
k 擬似頻出集合の係数
M メモリ
M0 頻出パターン探索手段
M1 正規出現演算手段
M2 代表選定手段
M3 親選定手段
M4 パターン選択手段
P パターン
P0 あいまい頻出集合
P1 親のパターン
P2 子供のパターン
T トランザクション
T0 トランザクションの集合
θ 平均包含率の閾値(密度閾値)
θp 平均包含率
σ 最大共起数の閾値(ミニマムサポート)
σp 最大共起数(頻出度数)
AmbiOcc(P) 正規出現
Prt(P) Pの親
図面
【図3】
0
【図4】
1
【図5】
2
【図1】
3
【図2】
4
【図6】
5
【図7】
6
【図8】
7