効率的な無順序木の融合可能性判定アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
木の編集距離は、2つの木の(非)類似度を計るための最も一般的な枠組みである。編集距離計算の結果は、木写像とよばれる構造に帰着できることが知られている。木写像は、2つの木が「どのように似ているのか」という構造的な情報を提供する。2つの木が共有する部分構造への制約の違いにより、木写像はクラス分けできる。同型な部分木のみを考慮するクラス、位相同型な部分木のみを考慮するクラス、頂点の先祖祖先関係のみを考慮するクラスなどが知られている。本稿では、まず重要な木写像のクラス階層を与え、木写像の類似性の構造に基づき、2つの木を1つの木に統合できるかどうかを判定する効率のよいアルゴリズムを与える。このアルゴリズムは、判定の過程で、木写像のクラスを同定することができる。
- 社団法人電子情報通信学会の論文
- 2006-04-19
著者
-
久保山 哲二
学習院大学計算機センター
-
Kuboyama Tetsuji
Research Center For Advanced Sciencece And Technology Center For Collaborative Research The Universi
-
久保山 哲二
九州大学大学院システム情報科学研究科知能システム学専攻
-
久保山 哲二
東京大学 国際・産学共同研究センター
-
申 吉浩
東京大学 先端科学技術研究センター
-
久保山 哲二
東京大学生産技術研究所
-
久保山 哲二
九州大学大学院総合理工学研究科雨宮研究室
関連論文
- 自由度1及び2の分割自由カーネル (特集 「諸分野の連携による知識発見」および一般)
- 特許の有効性に影響を与える要因の検討(セッション2)
- 特許の質の機械学習からのアプローチ : 特許の法的有効性判定のための特徴抽出の試み
- 木構造データからの知識発見について
- ハミング距離空間の次元削減によるインフルエンザウイルス遺伝子変異の解析 (特集 「知識発見の生命科学への応用」および一般)
- 金融工学数学における確率論の教授法 : 高校数学との関連づけ
- The Gram Distribution Kernel: A Tree Kernel for Glycan Classification (テーマ:特集「ウェブデータの知的処理」および一般)
- A spectrum tree kernel (論文特集:データマイニングと統計数理)
- A Theoretical Analysis of Tree Edit Distance Measures
- Measuring Distance and Finding Approximate Common Patterns in Trees--Focus on Edit Distance (特集「人工知能における論理の新たな展開」)
- Evolution of multiple tree structured patterns using soft clustering (特集 「知識発見の生命科学への応用」および一般)
- Evolution of multiple tree structured patterns using clustering (特集 「大規模データからの機械学習と自然言語処理への応用」および一般)
- A Hierarchy of Tree Edit Distance Measures (Theoretical Computer Science and its Applications)
- 木の編集距離尺度の理論的解析(数理モデル一般)
- 木の編集距離尺度の理論的解析
- Alignable Mapping による Shock Tree の合成(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 半構造データアラインメントによるWebページからのメタデータとコンテンツの抽出 (特集:「アクティブマイニング」および一般) -- (セッション3 Webマイニング)
- 木の編集距離を用いたWebページからの情報抽出(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- 木構造アラインメントのマッピング条件
- アミノ酸の高次元符号化によるインフルエンザウイルスの抗原変異予測 (特集 「脳科学と知識処理」および一般)
- 学会報告 「人工知能学会 第73回人工知能学会基本問題研究会」
- 海外出張報告
- 動的補題生成を用いたモデル生成木の枝刈り手法とその実装
- MGTPにおけるケース分割の重複削除手法とその評価
- 木カーネルの構成のためのフレームワークとサーベイ (特集 「大規模データからの機械学習と自然言語処理への応用」および一般)
- 二分木符号の文字列編集距離による木の編集距離の近似 (特集「知識発見の諸科学への応用」および一般)
- SVMを用いたモブログテキストからの感情抽出(情報抽出,特集「Web情報処理」及び一般)
- SVMを用いたモブログテキストからの感情抽出
- 畳み込みカーネルと多項式カーネルの一般化 (特集 「ウェブマイニング」および一般)
- 効率的な無順序木の融合可能性判定アルゴリズム
- 根付き無順序木のフィルタリング (テーマ:特集「ウェブデータの知的処理」および一般)
- Webコンテンツの不整合問題に対するモデレーションモデルの提案
- 半構造データ統合のための木構造の近似照合と結合手法
- 木写像のクラス同定
- ラベル無し順序木のqグラム距離
- 半構造データ統合のための木構造の近似照合と結合手法(セッション3: メタデータとオントロジ応用)
- On MAX SNP-hard results for unordered tree edit distance (特集 「ベイジアン・ネットワーク」および一般)
- グラフ生成システムFGSによる帰納学習システムについて
- グラフデータからの知識発見システムKD-FGSについて
- 金融工学数学のためのグラフィクス教材データベース : Bond Mathematics by Graphics
- 金融工学の数学のための知識データベース構築の提案
- 金融工学の数学のための知識データベース構築の提案
- 金融工学の数学のための知識データベース構築の提案
- 研究解説「セキュリティと利便性の両立をめざしてーパスワード同期とデータベースー」
- Consensual Disclosureを実現する実用的な追跡不能アクセス制御方式(セキュリティ)
- 半構造データ統合のための木構造の近似照合と結合手法(セッション3: メタデータとオントロジ応用)
- Alignable Mapping による Shock Tree の合成(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 海外派遣報告書(3件)
- 長時間過分極時のニューロン電位の揺らぎの時系列解析と脳の情報処理における機能的意義
- 文字列の高速類似度計算・検索のための要素技術について─ 系列分割手法─
- 学習管理システムによる自己学習型マルチメディア教育支援体制
- MODELING THE USER IN 3D CHARACTER ANIMATION AUTHORING(International Workshop on Advanced Image Technology 2007)
- MODELING THE USER IN 3D CHARACTER ANIMATION AUTHORING
- A MODEL FOR MISMATCH RESOLUTION OF WEB PAGES(International Workshop on Advanced Image Technology 2006)
- A Spectrum Tree Kernel
- 根付き順序木のグラム分散 (テーマ:特集「シンボルグラウンディング問題」および一般)
- 木の編集距離尺度の理論的解析
- 木の編集距離を用いたWebページからの情報抽出(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- 多様化する情報・マルチメディア機器を用いた教育・研究に対する効率的な支援体制の検討
- 部分パスに基づいた木カーネル
- 木構造間ノード写像の近似照合クラス同定アルゴリズム (テーマ:特集「ベイジアンネットワーク」および一般)
- Alignment of Tree Structures for Generation of Web Wrappers (特集 オントロジー)
- Discovering Knowledge from Graph Structured Data by Using Refutably Inductive Inference of Formal Graph Systems (Special lssue on Selected Papers from LA Synposium)
- 研究の方法と評価
- D-9-21 利用アプリケーションの時系列ログを用いたPCの利用形態分析(D-9.ライフインテリジェンスとオフィス情報システム,一般セッション)
- D-9-22 Webアクセスログからの閲覧者の行動分析(D-9.ライフインテリジェンスとオフィス情報システム,一般セッション)
- PC操作ログからの従業員PC利用パターンのクラスタリング
- 作業ウィンドウの時系列ログデータからの業務遷移パターン抽出 (「メディアとAI」および一般)
- ソーシャルメディアと履歴書情報の照合を通じた個人の言動の推定
- アクティブウィンドウ遷移ログからの企業内PC利用パターン分析(履歴の操作と活用,ライフログ活用技術,オフィスインフォメーションシステム,ライフインテリジェンス,一般)
- PC操作ログからの従業員PC利用パターンのクラスタリング(ログ活用・情報検索,グループウェアとネットワーク,ライフログ活用技術,一般)
- ソーシャルメディアを対象としたマーケティング解析 : 時事問題をきっかけとした想定外の消費行動抽出
- IT活用教育支援業務組織における効果的なデータベースの開発と運用方法の検討
- 海外派遣報告書(4件)
- 電子メールの送受信ログによる学内コミュニケーション構造の定性的分析
- 大規模グラフから抽出したコミュニティの階層化 (特集 「Webと知識連携・統合,発想支援」および一般)
- A new consistency-based feature selection algorithm (特集 「Webと知識連携・統合,発想支援」および一般)
- 低レベルPC操作ログからの業務パターン抽出手法の提案(「コンテキストを意識した知識の利用」及び一般)
- バズマーケティングサイトからのコミュニティマッピングの抽出 (特集 「Big data と機械学習・データサイエンス」および一般)
- 集合被覆問題の解法を用いた特徴選択 (特集 「Big data と機械学習・データサイエンス」および一般)
- 絡み目理論の解析ツール : 文法圧縮によるMilnor不変量の抽出 (特集 「Big data と機械学習・データサイエンス」および一般)
- 絡み目理論の解析ツール : 自由曲線からの数式自動生成 (特集 「Big data と機械学習・データサイエンス」および一般)
- 低レベルPC操作ログからの業務パターン抽出手法の提案
- キャンパス内の無線LAN利用動向分析
- 学内Web サイトログからの閲覧者の行動分析
- インターネット上の口コミサイトにおける化粧品の評判分析
- Scalable Detection of Frequent Substrings by Grammar-Based Compression
- 木カーネルの選び方 (特集 「情報セキュリティと知的データ処理」および一般)
- ネットワークの機能クラスタリングを用いたPC操作ログ分析 (特集 「情報セキュリティと知的データ処理」および一般)
- 高速な特徴選択アルゴリズムCWCを用いた特徴語抽出 (特集 「情報セキュリティと知的データ処理」および一般)
- 金融工学の数学のための知識データベース構築の提案 (データベースシステム(DBS)) -- (データベース構築)
- ソーシャルメディアにおけるバーストパターンの共起に基づく新概念抽出 (特集 「機械学習と自然言語処理への応用」および一般)
- Temporal Awareness of Needs after East Japan Great Earthquake based on Latent Semantic Analysis and Pattern Similarity (特集 「諸分野における知的情報処理技術の動向」および一般)
- A path searching method for the backward elimination feature selection (特集 「機械学習と自然言語処理への応用」および一般)
- D-9-48 ネットワークの機能クラスタリングによるPC操作ログ分析(D-9.ライフインテリジェンスとオフィス情報システム)
- Feature Selection based on Distribution Distances (特集 「機械学習とその周辺情報分野における離散問題と高速アルゴリズム」および一般)
- 特徴選択指標の理論 (特集 「人工知能とデータサイエンス」および一般)
- 金融工学の数学のための知識データベース構築の提案 (情報基礎とアクセス技術(IFAT)) -- (データベース構築)
- Learning of Glycan Motifs Using Genetic Programming and Various Fitness Functions (Selected Papers from The 6th International Conference on Soft Computing and Intelligent Systems and The 13th International Symposium on Advanced Intelligent Systems (SCIS&I