Distributed Data Mining Systems for Structured Web Data

结构化 Web 数据的分布式数据挖掘系统

• 批准号: 14580423
• 负责人: SHOUDAI Takayoshi
• 金额: $ 1.92万
• 依托单位: KYUSHU UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14580423/
• 关键词: data mining; machine learning; inductive inference; tree structured data; web mining; metasearch; network algorithm; 並列アルゴリズム; 半構造データ; グラフ構造; 質問学習; 知識発見; 多項式時間学習可能; 正データからの帰納推論; 厳密学習; データマイニングプロセス; 仮説クラスアトラス

In this research, we studied knowledge discovery from semistructured Web documents such as HTML/XML files. Graph or tree-based data mining and discovery of frequent structures in graph or tree structured data have been extensively studied. Our target of discovery is neither a simply frequent pattern nor a maximally frequent pattern with respect to syntactic sizes of patterns such as the number of vertices. In order to extract useful information from heterogeneous semistructured Web documents, our target of discovery is a semantically and maximally tree structured pattern which represents a common characteristic in semistructured documents. As a representation of a tree structured pattern, we proposed an ordered tree pattern, called a term tree, which is a rooted tree pattern consisting of ordered children and internal structured variables.A term tree is different from other representations of tree structured patterns in that a term tree has structured variables which can be substituted by arbitrary trees. First of all, we deeply studied the learnabilities of classes of term tree languages and gave fundamental classes of term tree languages which are polynomial time learnable. We proved that some classes of term tree languages are polynomial time inductively inferable from positive data, which include the class of linear term tree languages with multiple child-port variables, the class of linear term tree languages with contractible variables which are adjacent to leaves, and the class of linear term tree languages with height-constrained variables and no variable chain. Moreover, we showed that some classes of linear term tree languages are exactly learnable in polynomial time using queries.Finally, we presented a metasearch system which uses our efficient learning algorithms for term trees. We implemented this system and showed that it provides an effective unified access to multiple existing search sites.

在这项研究中，我们研究了半结构化 Web 文档（例如 HTML/XML 文件）中的知识发现。基于图或树的数据挖掘以及图或树结构数据中频繁结构的发现已经被广泛研究。我们的发现目标既不是简单的频繁模式，也不是就模式的句法大小（例如顶点数量）而言的最大频繁模式。为了从异构半结构化 Web 文档中提取有用信息，我们的发现目标是语义上最大的树结构模式，它代表了半结构化文档的共同特征。作为树结构模式的表示，我们提出了一种有序树模式，称为术语树，它是由有序子项和内部结构化变量组成的有根树模式。术语树与树结构模式的其他表示不同，因为术语树具有可以用任意树替换的结构化变量。首先，我们深入研究了术语树语言类别的可学习性，并给出了多项式时间可学习的术语树语言的基本类别。我们证明了某些类别的项树语言是多项式时间可从正数据归纳推断的，其中包括具有多个子端口变量的线性项树语言类、具有与叶子相邻的可收缩变量的线性项树语言类以及具有高度受限变量且无变量链的线性项树语言类。此外，我们还表明，某些类别的线性术语树语言可以使用查询在多项式时间内完全学习。最后，我们提出了一个元搜索系统，该系统使用我们针对术语树的高效学习算法。我们实施了这个系统，并表明它提供了对多个现有搜索站点的有效统一访问。

项目成果

Learning of Ordered Tree Languages with Height-Bounded Variables Using Queries

使用查询学习具有高度限制变量的有序树语言

• 发表时间: 2004
• 期刊: Proc.15th Workshop on Algorithmic Learning Theory, Springer-Verlag, LNAI 3244
• 作者: Daisuke Ibuki;Souya Michitsuji;Norihiko Ono;Isao Ono;Satoshi Matsumoto
• 通讯作者: Satoshi Matsumoto

Y.Suzuki, T.Shoudai, T.Miyahara, T.Uchida: "Ordered Term Tree Languages Which Are Polynomial Time Inductively Inferable from Positive Data"Proc.Algorithmic Learning Theory 2002, Lecture Notes in Artificial Intelligence. 2533. 188-202 (2002)

Y.Suzuki、T.Shoudai、T.Miyahara、T.Uchida：“从正数据中可归纳推断出多项式时间的有序术语树语言”Proc.算法学习理论 2002 年，人工智能讲义。

Ordered term tree languages which are polynomial time inductively inferable from positive data

• DOI: 10.1016/j.tcs.2005.10.022
• 发表时间: 2002-11
• 期刊: Archive of Applied Mechanics
• 影响因子: 2.8
• 作者: Yusuke Suzuki;Takayoshi Shoudai;Tomoyuki Uchida;T. Miyahara

Discovery of Maximally Frequent Tag Tree Patterns with Contractible Variables from Semistruc-tured Documents.

从半结构化文档中发现具有可收缩变量的最大频繁标签树模式。

• 发表时间: 2004
• 期刊: Proc.8th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Lecture Notes in Artificial Intelligence(Springer-Verlag) Vol.3056
• 作者: T.Miyahara;Y.Suzuki;T.Shoudai;T.Uchida;K.Takahashi;H.Ueda
• 通讯作者: H.Ueda

Efficient learning of ordered and unordered tree patterns with contractible variables

具有可收缩变量的有序和无序树模式的高效学习

• 发表时间: 2003
• 期刊: Proc.14th Workshop on Algorithmic Learning Theory, Springer-Verlag, LNAI 2842
• 作者: Yusuke Suzuki