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

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

基本信息

批准号：
16016266
负责人：
トーマスツォイクマン
金额：
$ 5.06万
依托单位：
Hokkaido University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

项目摘要

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

这项研究旨在阐明基于大规模半结构数据挖掘的数据挖掘（Web挖掘）的新信息访问系统的实现方法，该方法超越了传统信息检索系统，例如大量的网页和XML，作为一种有效的工具，可以交互支持大量数据分析。作为关键技术，该公司将最佳模式发现扩展到树木和图形结构，并致力于为半结构化数据开发出强大而快速的优化模式发现算法，同时还推进了计算复杂性理论和计算学习理论的最新结果。 2005年，该公司致力于为半结构化数据开发强大而快速的优化模式发现算法。该公司旨在通过与去年第一年的研究结果集成，以建立一个原型系统，以进行最佳的半结构采矿。除了三个信息获取问题外：发现有用的信息源，发现独特的模式并提取信息外，该公司还致力于知识指数问题，该问题已于去年刚开始研究。今年获得的主要结果如下：（1）ZBDD（Zero-Suppress），该数据结构可以有效地处理大型交易数据中经常发现的稀疏组合集数据。基于BDD），我们促进了ZBDD软件包工具与POP（有价值的产品总和）的开发，该工具可以计算其结构下的加权产品工会，并为ZBDD的简单正交分解添加了一个函数，该ZBDD经常表达的模式经常出现，可以自动提取。这使数据中包含的语义结构能够自动提取。（Minato）（2）我们成功地提供了使用模式发现算法的分类和预测长期行为的理论保证。（Tsoikman）（3）我们获得了一种有效地列出串联数据中最大基序模式的算法。（Arimura：H13-H16代表）（4）我们获得了具有ARC结构的文本的快速图案匹配算法。（Kida）

项目成果

期刊论文数量（16）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

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

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

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

DOI：
发表时间：
2005
期刊：
Proc.of IEEE ICDM 2005 workshop on Computational Intelligence in Data Mining TRN2005-09
影响因子：
0
作者：
Bjorn Hoffmeister;Thomas Zeugmann;Sin-ichi Minato
通讯作者：
Sin-ichi Minato

Approximate Point Set Pattern Matching on Sequences and Planes

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

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

An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases