論文

査読有り
2015年

Tree PCA for Extracting Dominant Substructures from Labeled Rooted Trees

DISCOVERY SCIENCE, DS 2015
  • Tomoya Yamazaki
  • ,
  • Akihiro Yamamoto
  • ,
  • Tetsuji Kuboyama

9356
開始ページ
316
終了ページ
323
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-319-24282-8_27
出版者・発行元
SPRINGER-VERLAG BERLIN

We propose novel principal component analysis (PCA) for rooted labeled trees to discover dominant substructures from a collection of trees. The principal components of trees are defined in analogy to the ordinal principal component analysis on numerical vectors. Our methods substantially extend earlier work, in which the input data are restricted to binary trees or rooted unlabeled trees with unique vertex indexing, and the principal components are also restricted to the form of paths. In contrast, our extension allows the input data to accept general rooted labeled trees, and the principal components to have more expressive forms of subtrees instead of paths. For this extension, we can employ the technique of flexible tree matching; various mappings used in tree edit distance algorithms. We design an efficient algorithm using top-down mappings based on our framework, and show the applicability of our algorithm by applying it to extract dominant patterns from a set of glycan structures.

リンク情報
DOI
https://doi.org/10.1007/978-3-319-24282-8_27
DBLP
https://dblp.uni-trier.de/rec/conf/dis/YamazakiYK15
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000367678000027&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/conf/dis/dis2015.html#conf/dis/YamazakiYK15
ID情報
  • DOI : 10.1007/978-3-319-24282-8_27
  • ISSN : 0302-9743
  • DBLP ID : conf/dis/YamazakiYK15
  • Web of Science ID : WOS:000367678000027

エクスポート
BibTeX RIS