最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

基于最优模式发现的大规模半结构化数据智能信息获取系统开发

• 批准号: 16016266
• 负责人: トーマス ツォイクマン
• 金额: $ 5.06万
• 依托单位: Hokkaido University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16016266/
• 关键词: 半構造データ; ウェブマイニング; XMLデータ; グラフマイニング; パターン照合; 系列パターン; 機械学習; 文法圧縮

本研究は,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.その鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ.平成17年度は,初年度から昨年度までの研究成果と統合し,最適半構造マイニングのプロトタイプシステム構築を目指した.研究項目としては,有用な情報源の発見,特徴的なパターンの発見,情報の抽出の3つの情報獲得問題に加えて,昨年度から新たに研究を開始した知識索引問題について取り組んだ.今年度得られた具体的な結果のうち主要なものは以下のとおりである.(1)大規模なトランザクションデータによく見られる疎な組み合わせ集合データを効率よく扱うことのできるデータ構造であるZBDD(Zero-suppress BDD)をベースに,その構造の元で重み付き積和集合を計算可能なZBDDパッケージツールVSOP(Valued Sum-Of-Products)の開発を推し進め,頻出するパターン集合を表現するZBDDを単純直交分解する機能を追加した.これにより,そのデータに内包された意味的構造を自動抽出することが可能になった.(湊)(2)パターン発見アルゴリズムによる分類・予測の長期的ふるまいに関する理論保証を与えることに成功した.(ツォイクマン)(3)系列データからの極大モチーフパターンを効率よく枚挙するアルゴリズムを得た.(有村:H13-H16代表)(4)Arc構造付きテキストに対する高速なパターン照合アルゴリズムを得た.(喜田)

In this study, a large number of XML and other large-scale semi-structured data processing (data processing) base, a large number of data analysis to support the efficiency of the data processing, the information processing system to improve the information processing system implementation mode to clarify the purpose. The latest achievements of computational theory and computational learning theory are applied to the development of semi-structural systems. The research results of Heisei 17 were integrated and the optimal semi-structural structure was established. Research projects: discovery of useful information sources, discovery of characteristics, extraction of information, information acquisition problems, new research projects, knowledge indexing problems, and selection of groups. This year, we got a concrete result. (1)ZBDD(Zero-Suppress BDD) is a new type of structure, which can be used to calculate the product and set of ZBDD (Valued Sum-Of-Products). The structure of the package is automatically extracted from the package. (2) The classification of long-term prediction and theoretical guarantee of success (3) The maximum number of entries in the list is: (There are villages:H13-H16 representatives)(4)Arc structure to pay attention to the high speed of the light and light to get the light. (Kida)

项目成果

Efficient Database Analysis Using VSOP Calculator Based on Zero-suppressed BDDs

使用基于零抑制 BDD 的 VSOP 计算器进行高效数据库分析

• 发表时间: 2006
• 期刊: Frontiers in Artificial Intelligence, Joint JSAI 2005 Workshop Post-Proceedings LNAI 4012
• 作者: 湊 真一;有村博紀;Bjorn Hoffmeister and Thomas Zeugmann;S. Minato;S. Minato
• 通讯作者: S. Minato

Finding Simple Disjoint Decompositions in Frequent Itemset Data Using Zero-suppressed BDD

使用零抑制 BDD 在频繁项集数据中查找简单不相交分解

• 发表时间: 2005
• 期刊: Proc.of IEEE ICDM 2005 workshop on Computational Intelligence in Data Mining TRN2005-09
• 作者: Bjorn Hoffmeister;Thomas Zeugmann;Sin-ichi Minato
• 通讯作者: Sin-ichi Minato

Approximate Point Set Pattern Matching on Sequences and Planes

序列和平面上的近似点集模式匹配

• 发表时间: 2004
• 期刊: Proceeding of the 15th Annual Symposium on Combinatorial Pattern Matching(CPM 2004) LNCS 3109
• 作者: 大崎 純;西脇眞二;Heikki Hyyro et al.;Ayumi Shinohara;Shunsuke Inenaga et al.;Tomoaki Suga et al.
• 通讯作者: Tomoaki Suga et al.

大規模データストリームのためのマイニング技術の動向

大规模数据流挖掘技术趋势

• 发表时间: 2005
• 期刊: 電気情報通信学会論文誌 J88-D-I・2(印刷中)
• 作者: Bjorn Hoffmeister;Thomas Zeugmann;Sin-ichi Minato;有村博紀
• 通讯作者: 有村博紀

An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases

• DOI: 10.1007/978-3-540-30214-8_2
• 发表时间: 2004-10
• 作者: T. Uno;Tatsuya Asai;Y. Uchida;Hiroki Arimura