拡張出現マッチングを用いた制約付きノイズ許容極小順序木パターンの発見

IPSJ Web Site

Bibliographic Information

Other Title
  • カクチョウ シュツゲン マッチング オ モチイタ セイヤク ツキ ノイズ キョヨウ キョクショウ ジュンジョ モク パターン ノ ハッケン
  • Mining Noise-tolerant Minimal Constrained Ordered Subtrees by Using Extended Occurrence Matching

Search this article

Description

近年，大量のパターンが抽出されるという構造データを対象とした頻出パターン発見の問題に対し，(1) 頻出パターンの代表元のみを発見する手法や，(2) 利用者により与えられる制約を満たすパターンのみを発見する手法などが提案されている．本論文では，順序木データベースを対象とした両者の統合アプローチとして，制約下でのノイズを許容した極小元である，(1) 制約付きδ-フリー順序木パターンと，(2) 制約付き Δ-トレランス順序木パターンの発見問題について議論する．この問題を解決するために，本論文では，拡張出現マッチングと，それに基づく枝刈り手法をともなう3種のアルゴリズムを提案する．合成データと実データを用いた比較実験により，抽出されるパターン数や実行時間の観点から，提案手法の有効性が確認された．

Frequent pattern miners for structured data often discover huge number of patterns. To alleviate this problem, two major approaches, (1) condensed representation mining and (2) constraint-based mining, have been proposed. In this paper, as a technique for integrating these two approaches in ordered subtree mining, we focus on mining ‘noise-tolerant minimal patterns under constraints’ and discuss the problems of mining (1) δ-free constrained ordered subtrees and (2) Δ-tolerance constrained ordered subtrees. To achieve this objective, we propose three kinds of algorithms having pruning capability based on extended occurrence-matching. The results of experiments with synthetic and real world datasets show that, compared with a naive algorithm, the proposed algorithms succeed in reducing the number of extracted patterns and execution time.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top