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

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

国内特許コード P10A015391
整理番号 A0200156
掲載日 2010年4月9日
出願番号 特願2008-071128
公開番号 特開2009-230186
登録番号 特許第5267847号
出願日 平成20年3月19日(2008.3.19)
公開日 平成21年10月8日(2009.10.8)
登録日 平成25年5月17日(2013.5.17)
発明者
  • 宇野 毅明
出願人
  • 大学共同利用機関法人情報・システム研究機構
発明の名称 あいまい頻出集合の探索方法及び探索装置
発明の概要

【課題】あいまい頻出集合のパターンを完全かつ短時間に抽出する探索方法を提供する。
【解決手段】各トランザクションTがアイテム集合Eの部分集合になっているデータベースD、アイテムeの平均包含率が閾値θ以上、かつ、頻出度数σ以上に対するあいまい頻出集合P0の探索方法であって、あいまい頻出集合Pの正規出現AmbiOcc(P)を求める工程と、正規出現AmbiOcc(P)に含まれる数が最小であるアイテムを代表アイテムe(P)と定める工程と、正規出現AmbiOcc(P)のトランザクションから代表アイテムe(P)を除いて親と定める工程と、あいまい頻出集合P0の頻出パターンPの候補を選択するパターン選択工程とを備え、頻出パターンの各候補について、あいまい頻出集合P0に属するか否かを判断し、親子関係を決定し、あいまい頻出集合P0に属する頻出パターンPを全て抽出する。
【選択図】図7

従来技術、競合技術の概要


データベース内に頻繁に現れる頻出パターンを抽出する問題は、情報科学の基本問題である。データベースのデータ及びパターンとして、トランザクション、ツリー、グラフ、多次元ベクトル等が、データ及びパターンの要素として、アイテム、部分集合、木、パス・サイクル、グラフ、図形等が挙げられる。特に、データベースDのデータがアイテム集合Eの部分集合であるトランザクションTである場合に、頻出パターンを全て抽出する問題は頻出パターン列挙問題と云われている。この場合、完全一致検索の問題であれば容易に解決できる。他方、あいまい性を許して多くのデータに含まれるパターンを抽出するあいまい検索は、ゲノムの相同検索等で大いに実用的である。しかし、完全一致検索の問題からこのようなあいまい検索の問題になると、とたんに難しくなる。



アイテム集合Eに対して、あいまいな包含関係を考え、頻出集合を列挙するアルゴリズムに関して、従来の解決方法は、包含率の閾値θを定め、全てのデータを照合するか、ヒューリステックな検索をして、多数ではあるが不完全な頻出集合を抽出するかのどちらかであった。(非特許文献1~3参照)




【非特許文献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.

産業上の利用分野


本発明は、あいまい頻出集合の探索方法及び探索装置に関する。詳しくは、データベース内に頻繁に現れる頻出パターンを、あいまい性を許して完全かつ短時間に抽出できる探索方法及び探索装置に関する。

特許請求の範囲 【請求項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を全て抽出する;
あいまい頻出集合の探索装置。
産業区分
  • 計算機応用
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2008071128thum.jpg
出願権利状態 権利存続中
※ 情報・システム研究機構 国立情報学研究所(NII)は、我が国唯一の情報系に特化した研究所です。NIIでは、外部資金による研究成果の社会還元を中心に、技術移転活動に積極的に取り組んでいます。上記の発明にライセンス対象や共同開発対象として関心をお持ちいただいた方は、国立情報学研究所 社会連携推進室までお気軽にお問合せください。


PAGE TOP

close
close
close
close
close
close
close