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

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

• 批准号: 13224073
• 负责人: 有村 博紀
• 金额: --
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13224073/
• 关键词: ウェブマイニング; 最適パターン発見; エピソードパターン; ウェブからの情報抽出; 半構造データ; 知識獲得; データマイニング

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

The rapid growth of semi-structural data such as XML, etc., is an urgent problem for the development of high-quality data. This study aims to provide guidance for the development of large-scale semi-structured data structures based on the analysis of a large number of data structures to support the efficiency of data analysis and the development of new information systems. In addition, the key technology is to optimize the development of structural, semi-structural, and high-speed optimization. (a) Discovery of useful information sources;(b) Discovery of characteristics;(c) Investigation of the process of information extraction;(d) Organic combination;(e) Semi-structural analysis;(e) Knowledge acquisition;(e) Efficient realization;(e) Application of the latest results of computational learning theory;(e) Application of the theory of computational learning;(f) Application of the theory of computational learning;(e) Application of the theory of computational learning;(e) Application of the theory of computational learning;(e) Application of the theory of computational learning;(f) Application of the theory of computational learning;(e) Application of the theory of computational learning;(e) Application of the theory of computational learning;(e) Application of the theory of computational learning; and (f) Application of the theory of computational learning. The calculation of the amount of thorough allocation of high-speed, high-speed and high-speed development of the target indicators. Heisei 13 years, the second research results obtained. (a)"Useful information source discovery" is related to, part of the series from the right to the left to the right to the right to optimize the efficiency of, part of the text series classification and decision tree learning from the right to the left to the right to the right. (b)In terms of "discovery of characteristic trees", semi-structural trees are the most basic types of trees, and common structures are frequently used in the development of high-speed discovery. In general, the calculation amount is high and the problem is not solved. For example, the right-most branch expansion method and the middle detection method, the optimization method and the semi-structural optimization method are combined, and the high-speed detection method and the semi-structural optimization method are combined. (c)"Information extraction" is related to the problem of information extraction, and the development of Tree-Wrapper is carried out by using information of HTML structure and necessary information.

项目成果

村上 他(第3著者): "HTMLからのテキストの自動切りだしアルゴリズムと実装"情報処理学会論文誌:数理モデル化と応用. 42:SIG14 (TOM5). 39-49 (2001)

Murakami 等人（第三作者）：“从 HTML 自动提取文本的算法和实现”，日本信息处理学会汇刊：数学建模和应用 42：SIG14 (TOM5)。

T.Asai, et al.(第4著者): "Efficient Substructure Discovery from Large Semi-structured Data"Proc.Second SIAM International Conference on Data Mining 2002 (SDM'02). (発表予定). (2002)

T.Asai 等人（第四作者）：“来自大型半结构化数据的高效子结构发现”Proc.2002 年第二届 SIAM 国际数据挖掘会议（SDM02）（待提交）。

M.Hirao et al.: "A Practical Algorithm to Find the Best Episode Patterns"Proc.the 4th International Conference on Discovery Science. LNCS 2226. 435-440 (2001)

M.Hirao 等人：“寻找最佳情节模式的实用算法”Proc.第四届国际发现科学会议。

H.Arimura, et al.: "Efficient Learning of Semi-structured Data from Queries"Proc.the 12th International Conference on Algorithmic Learning Theory (ALT'O1). LNAI 2225. 315-331 (2001)

H.Arimura 等人：“从查询中有效学习半结构化数据”Proc.第 12 届国际算法学习理论会议 (ALTO1)。

K.Taniguchi, et al.(第3著者): "Mining Semi-Structured Data by Path Expressions"Proc.the 4th International Conference on Discovery Science. LNAI 2226. 378-388 (2001)

K.Taniguchi 等人（第三作者）：“通过路径表达式挖掘半结构化数据”Proc.第四届国际发现科学会议 2226. 378-388 (2001)