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

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

基本信息

批准号：
13224073
负责人：
有村博紀
金额：
--
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至无数据
项目状态：
已结题

项目摘要

ネットワーク上に分散したウェブページやXML等の半構造データの急速な増大に対して,これらのコンテンツに直接アクセスするための効率良い手法の開発が緊急の課題となっている.本研究では,大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指す.そのために,鍵となる技術として,最適パターン発見を木やグラフ構造に拡張して,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムを開発する.さらに,ウェブマイニングを(a)有用な情報源の発見,および(b)特徴的なパターンの発見,(c)情報抽出の3つの過程からなると考え,これらを有機的に結合して,半構造データを対象とした知識獲得システムの効率良い実現方式を明らかにすることを目標とする,また,計算量理論と計算学習理論の最新の成果を援用して,計算量に徹底的に配慮した高速なアルゴリズムの開発を目指すことも特色である.平成13年度は,次の研究成果を得た.(a)「有用な情報源の発見」に関しては,部分系列パターンとエピソードパターンと呼ぶ組合せパターンに対する効率よい最適化マイニングアルゴリズムを開発し,これを文字列分類のための決定木学習アルゴリズムBONSAIに組み込んだ.(b)「特徴的なパターンの発見」に関しては,半構造データを最も基本的なラベル付き順序木(labeled ordered trees)のクラスとしてモデル化し,データ中の頻出共通部分構造に対する高速な発見アルゴリズムを開発した.木に関するパターン発見問題は,一般に高い計算量をもつことが多い.そこで,最右枝拡張法という効率よい発見手法を与え,これを複数の最適化手法と組み合わせて,半構造データに対する高速なマイニングアルゴリズムを与えた.(c)「情報抽出」に関しては,ウェブからの情報抽出問題を考察し,HTMLデータから木構造の情報を利用して必要な情報を効率よく切り出すTree-Wrapperアルゴリズムを開発した.

随着网络上分布的网页和XML等半结构化数据的快速增加，开发直接访问这些内容的有效方法已成为一个紧迫的问题。正在使用传统信息作为有效工具来交互式支持大量数据的分析。我们的目标是开发一种超越搜索系统的新型信息访问系统。为此，关键技术是将最优模式发现扩展到树和图结构，并针对半结构化数据开发鲁棒且快速的优化模式发现算法。此外，网络挖掘还可用于（a）发现有用的信息源，（b）发现独特的模式，以及（c）提取信息。我们的目标是将这三个过程有机地结合起来，揭示一种针对半结构化数据的知识获取系统的有效实现方法。我们研究的另一个特点是，我们的目标是开发充分考虑计算复杂性的高速算法。利用最新的理论成果。2001财年，我们获得了以下研究成果：（a）关于有用信息源的发现，我们开发了一种有效的组合模式优化挖掘算法，称为子序列模式和情景模式，并将其纳入字符串分类的决策树学习算法 BONSAI 中。(b) 关于“特征模式的发现” ”，半结构化数据可以转化为最基本的带标签有序树（labeledorderedtree）。已订购我们开发了一种高速发现算法，针对数据中经常出现的常见子结构问题，提供了一种良好的发现方法，并将其与多种优化方法相结合。此外，我们还提供了半结构化数据的高速挖掘算法。 (c)关于“信息提取”，我们考虑了从网络中提取信息的问题，并使用树结构信息从HTML数据中提取必要的信息。我们开发了一种可以有效提取数据的 Tree-Wrapper 算法。