Discovery Knowledge and Data Mining from Structured Data

本研究项目的目的是为从图结构数据或树结构数据中进行数据挖掘系统提供理论基础。最近，诸如HTML文件和XIML文件等Web文档迅速增加。这样的Web文档没有严格的结构，被称为半结构化数据。通常，这种半结构化的Web文档由有根树表示。我们提出了在半结构化Web文档中发现频繁树结构模式的方法，该方法以标签树模式为假设。标签树模式是具有有序或无序的子代和结构化变量的边标记树。在这样的Web文档中，边标签是一个标签或关键字，变量可以用任意的树代替。因此，标签树模式适合于在这样的Web文档中表示树结构模式。从半结构化数据中提取信息变得越来越重要。为了从半结构化数据中提取有意义或有趣的内容，我们需要从半结构化数据中提取常见的结构化模式。我们提出了一种从不规则半结构化数据中提取特征标签树模式的方法，该方法使用了一种算法来寻找解释给定数据的最小广义标签树模式。此外，我们还给出了树结构数据中具有结构化变量的树形结构模式--术语树的各种学习算法，因为这种学习算法为从半结构化数据中进行数据挖掘提供了理论基础。

The purpose of this research project is to give theoretical foundations of data mining systems from graph-structured data or tree-structured data. Recently, Web documents such as HTML files and XIML files have increased rapidly. Such Web documents have no rigid structure and are called semistructured data. In general, such semistructured Web documents are represented by rooted trees. We have proposed methods for discovering frequent tree structured patterns in semistructured Web documents by using a tag tree pattern as a hypothesis. A tag tree pattern is an edge labeled tree which has ordered or unordered children and structured variables. An edge label is a tag or a keyword in such Web documents, and a variable can be substituted by an arbitrary tree. So a tag tree pattern is suited for representing tree structured patterns in such Web documents. Information Extraction from semistructured data becomes more and more important. In order to extract meaningful or interesting contents from semistructured data, we need to extract common structured patterns from semistructured data. We have presented a method for extracting characteristic tag tree patterns from irregular semistructured data by using an algorithm for finding a minimally generalized tag tree pattern explaining given data. Also we have given various learning algorithms of term trees, which are tree structured patterns with structured variables, from tree structured data, since such learning algorithms give theoretical foundations of data mining from semistructured data.