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文档中提取有用的信息，我们的目标是发现一个语义和最大树结构模式，它代表了半结构化文档中的一个共同特征。作为树结构模式的一种表示，我们提出了一种有序树模式，称为术语树，它是由有序子树和内部结构变量组成的有根树模式，术语树与其他树结构模式表示的不同之处在于，术语树中的结构变量可以被任意树替换.首先，我们深入研究了术语树语言类的可学习性，给出了多项式时间可学习的术语树语言的基本类。我们证明了某些类型的项树语言是多项式时间归纳推理的，这些类型包括具有多个子端口变量的线性项树语言，具有与叶子相邻的可收缩变量的线性项树语言，以及具有高度约束变量且没有变量链的线性项树语言.此外，我们还证明了某些线性项树语言是可以在多项式时间内通过查询精确学习的。最后，我们给出了一个元数据库系统，该系统使用了我们的有效的项树学习算法。我们实现了这个系统，并表明它提供了一个有效的统一访问多个现有的搜索网站。

项目成果

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 年，人工智能讲义。

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

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