Data mining technique from huge graph structured data which are lossless compressed

无损压缩的海量图结构数据的数据挖掘技术

• 批准号: 17500096
• 负责人: UCHIDA Tomoyuki
• 金额: $ 2.35万
• 依托单位: Hiroshima City University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17500096/
• 关键词: Algorithm; Data Mining; Machine Learning; Algorithmic Graph Theory; 情報基礎

Due to the rapid growth of Internet, many graph structured data such as Web documents, electric power wiring diagram and chemical compounds have become accessible on Internet. The purpose of this research is to present efficient graph mining algorithms for finding characteristic graph patterns from lossless compressed graph structured data. Then, we give results of this research as follows.1. For tree structured data such as Web documents, we gave polynomial time learning algorithms on inductive inference and polynomial time learning algorithms in query learning model. Moreover, we presented tree mining algorithms for tree structured data.2. In order to give graph mining techniques for graph structured data, by giving a polynomial time matching algorithm and a polynomial time algorithm for solving the minimal language problem for TTSP graph patterns, which is one of knowledge representations of an Electric power wiring diagram, we showed that the class of TTSP graphs is inductively inf … More erable from positive data. In the query learning model, we showed that finite unions of TTSP graph patterns are polynomial time learnable from queries. Moreover, we presented a graph mining algorithm of finding characteristic graph patterns from a set of outerplanar graphs which is a data model of chemical compounds.3. Based on Lempel-Zip compression for strings, we proposed a lossless compression algorithm for huge trees. Through several experiments, we showed that the proposed algorithms have good performance. Moreover, based on XBW transformations for trees given by Ferragina, et. al. in 2005, we presented an XBW transformation of lossless compressed trees. Then, we presented an efficient search algorithm of finding all occurrences of a given path on XBW structures of lossless compressed trees.4. Based on an XBW transformation for huge lossless compressed trees, we proposed an XBW transformation for TTSP graphs. Moreover, we also presented an efficient search algorithm of finding all occurrences of a given path on XBW structures of TTSP graphs. Less

由于Internet的快速发展，Web文档、电力接线图、化学化合物等许多图形结构化数据都可以在Internet上访问。本研究的目的是提出一种有效的图挖掘算法，用于从无损压缩的图结构化数据中发现特征图模式。然后，我们给出了本研究的结果如下：1。对于Web文档等树状结构数据，给出了归纳推理的多项式时间学习算法和查询学习模型的多项式时间学习算法。此外，我们还提出了树状结构数据的树挖掘算法。为了给出图结构数据的图挖掘技术，我们给出了一个多项式时间匹配算法和求解TTSP图模式最小语言问题的多项式时间算法，TTSP图模式是电力接线图的知识表示之一，我们证明了TTSP图类是可以从正数据中归纳推断的。在查询学习模型中，我们证明了TTSP图模式的有限联合在查询中是多项式时间可学习的。此外，我们提出了一种从一组外平面图中寻找特征图模式的图挖掘算法，这是一种化合物的数据模型。基于字符串的Lempel-Zip压缩，提出了一种大型树的无损压缩算法。实验结果表明，本文提出的算法具有良好的性能。此外，在Ferragina等人2005年给出的树的XBW变换的基础上，我们提出了无损压缩树的XBW变换。然后，我们提出了一种高效的搜索算法，可以在无损压缩树的XBW结构上找到给定路径的所有出现点。在对大型无损压缩树进行XBW变换的基础上，提出了对TTSP图进行XBW变换的方法。此外，我们还提出了一种有效的搜索算法，可以在TTSP图的XBW结构上找到给定路径的所有出现点。少

项目成果

Mining of Frequent Block Preserving Outerplanar Graph Structured Patterns

频繁块保留外平面图结构化模式的挖掘

• 发表时间: 2008
• 期刊: Proc. ILP-2007, Springer, Lecture Notes in Artificial Intelligence 4894
• 作者: Y.;Sasaki;H.;Yamasaki;T.;Shoudai;T.;Uchida
• 通讯作者: Uchida

Polynomial Time Inductive Inference of Interval Graph Pattern Languages from Positive Data

正数据区间图模式语言的多项式时间归纳推理

• 发表时间: 2006
• 期刊: Proc.the 4th Workshop on Learning with Logics and Logics for Learning (LLLL 2006)
• 作者: K.;Inata;T.;Miyahara;H.;Ueda;K.;Takahashi;Hitoshi Yamasaki
• 通讯作者: Hitoshi Yamasaki

Discovery of Maximally Frequent Tag Tree Patterns with Height-Constrained Variables from Semistructured Web Documents

从半结构化 Web 文档中发现具有高度约束变量的最大频繁标签树模式

• 发表时间: 2005
• 期刊: Proc.International Workshop on Challenges in Web Information Retrieval and Integration (WIRI 2005)
• 作者: R.;Takami;Y.;Suzuki;T.;Uchida;T.;Shoudai;Y.;Nakamura;Yusuke Suzuki
• 通讯作者: Yusuke Suzuki

Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data

TTSP图语言从正数据的多项式时间归纳推理

• 发表时间: 2005
• 期刊: Proc.ILP-2005, Springer, Lecture Notes in Artificial Intelligence 3625
• 作者: R.Takami;Y.Suzuki;T.Uchida;T.Shoudai;and Y.Nakamura
• 通讯作者: and Y.Nakamura

Sequential Algorithm Based on a Lempel-Ziv Compression Scheme for Tree Structured Data

基于Lempel-Ziv压缩方案的树结构数据顺序算法

• 发表时间: 2006
• 作者: 加藤 廣一郎;糸川 裕子;内田 智之;正代 隆義;中村 泰明
• 通讯作者: 中村 泰明