ラベル無し順序木のqグラム距離
スポンサーリンク
概要
- 論文の詳細を見る
本稿では, ラベル無し順序木のqグラム距離について考察する.まず, qグラムを線グラフに同型なノード数qの木と定義し, 2つの木のqグラム距離を2つの文字列のqグラム距離と同様に定義する.そして, 後行順の深さ列を用いることで, ノード数nの木Tのすべてのqグラムを, O(n^2)時間O(q)領域で数えあげる単純なアルゴリズムEnumGramを設計する.次に, このEnumGramを, O(qn)時間O(qd)領域のアルゴリズムLinearEnumGramに改良する.ここで, dはTの深さである.したがって, T_1とT_2のqグラム距離D_q(T_1, T_2)は, O(qmax{n_1, n_2})時間O(qmax{d_1, d_2})領域で計算することができる.ただし, n_iおよびd_iはT_iの中のノード数およびT_iの深さである.
- 社団法人電子情報通信学会の論文
- 2005-09-08
著者
-
平田 耕一
九州工業大学情報工学研究院
-
久保山 哲二
東京大学国際・産学共同研究センター
-
久保山 哲二
学習院大学計算機センター
-
Kuboyama Tetsuji
Research Center For Advanced Sciencece And Technology Center For Collaborative Research The Universi
-
久保山 哲二
九州大学大学院システム情報科学研究科知能システム学専攻
-
久保山 哲二
東京大学生産技術研究所
-
久保山 哲二
九州大学大学院総合理工学研究科雨宮研究室
-
大倉 暢仁
九州工業大学情報工学研究科情報科学専攻
-
原尾 政輝
九州工業大学情報工学部知能情報工学科
-
平田 耕一
九州工業大学
-
原尾 政輝
九州工大 情報工
-
平田 耕一
九州工業大学大学院情報工学研究院
関連論文
- 人工知能基本問題研究会(SIG-FPAI)(研究会総覧)
- 自由度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情報処理」及び一般)
- 畳み込みカーネルと多項式カーネルの一般化 (特集 「ウェブマイニング」および一般)
- 効率的な無順序木の融合可能性判定アルゴリズム
- 根付き無順序木のフィルタリング (テーマ:特集「ウェブデータの知的処理」および一般)
- Webコンテンツの不整合問題に対するモデレーションモデルの提案
- 木写像のクラス同定
- ラベル無し順序木のqグラム距離
- 半構造データ統合のための木構造の近似照合と結合手法(セッション3: メタデータとオントロジ応用)
- 順序付き二分法定グラフの学習可能性
- On MAX SNP-hard results for unordered tree edit distance (特集 「ベイジアン・ネットワーク」および一般)
- グラフ生成システムFGSによる帰納学習システムについて
- 類推機能をもった対話型シークェント計算証明システムの開発(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
- グラフデータからの知識発見システムKD-FGSについて
- 金融工学数学のためのグラフィクス教材データベース : Bond Mathematics by Graphics
- 金融工学の数学のための知識データベース構築の提案
- 金融工学の数学のための知識データベース構築の提案
- 金融工学の数学のための知識データベース構築の提案
- 研究解説「セキュリティと利便性の両立をめざしてーパスワード同期とデータベースー」
- 半構造データ統合のための木構造の近似照合と結合手法(セッション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,文書検索)(データ工学,ディペンダビリティ,一般)
- 人間指向型汎用類推証明システムの開発 (計算機科学基礎理論の新展開)
- 類推機能をもった対話型シークェント計算証明システムの開発 (計算機科学基礎理論の新展開)
- Pre-Checkingに基づく効率的スキーママッチングアルゴリズム(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- Pre-checkingを用いた効率的2階述語マッチングアルゴリズム (計算理論とアルゴリズムの新展開)
- スキーママッチングを用いたLK類推証明システムの開発
- スキーママッチングとその計算量
- スキーママッチングにおける計算の複雑さ (計算モデルとアルゴリズム)
- スキーママッチングの計算の複雑さ
- 古典的証明に基づく関数型言語の構築
- A Catalog for Prediction-Preserving Reducibility with Membership Queries on Formal Languages (New Developments of Theory of Computation and Algorithms)
- ALT'96報告
- 多様化する情報・マルチメディア機器を用いた教育・研究に対する効率的な支援体制の検討
- 無矛盾最小OBDD問題の近似困難性について
- 木構造間ノード写像の近似照合クラス同定アルゴリズム (テーマ:特集「ベイジアンネットワーク」および一般)
- 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利用パターンのクラスタリング
- 石灰石球の熱分解における熱移動と CO_2 ガスの流れ
- 32 石灰石球の熱分解における熱及び物質の移動(製銑基礎・コークス, 製銑, 日本鉄鋼協会第 84 回(秋季)講演大会)
- 一階論理式の学習と帰納論理プログラミング (計算学習理論の進展と応用可能性)
- 作業ウィンドウの時系列ログデータからの業務遷移パターン抽出 (「メディアとAI」および一般)
- ソーシャルメディアと履歴書情報の照合を通じた個人の言動の推定
- アクティブウィンドウ遷移ログからの企業内PC利用パターン分析(履歴の操作と活用,ライフログ活用技術,オフィスインフォメーションシステム,ライフインテリジェンス,一般)
- PC操作ログからの従業員PC利用パターンのクラスタリング(ログ活用・情報検索,グループウェアとネットワーク,ライフログ活用技術,一般)
- ソーシャルメディアを対象としたマーケティング解析 : 時事問題をきっかけとした想定外の消費行動抽出
- 大規模グラフから抽出したコミュニティの階層化 (特集 「Webと知識連携・統合,発想支援」および一般)
- A new consistency-based feature selection algorithm (特集 「Webと知識連携・統合,発想支援」および一般)
- バズマーケティングサイトからのコミュニティマッピングの抽出 (特集 「Big data と機械学習・データサイエンス」および一般)
- 集合被覆問題の解法を用いた特徴選択 (特集 「Big data と機械学習・データサイエンス」および一般)
- 絡み目理論の解析ツール : 文法圧縮によるMilnor不変量の抽出 (特集 「Big data と機械学習・データサイエンス」および一般)
- 絡み目理論の解析ツール : 自由曲線からの数式自動生成 (特集 「Big data と機械学習・データサイエンス」および一般)
- キャンパス内の無線LAN利用動向分析
- 学内Web サイトログからの閲覧者の行動分析
- インターネット上の口コミサイトにおける化粧品の評判分析
- Scalable Detection of Frequent Substrings by Grammar-Based Compression
- 木カーネルの選び方 (特集 「情報セキュリティと知的データ処理」および一般)
- ネットワークの機能クラスタリングを用いたPC操作ログ分析 (特集 「情報セキュリティと知的データ処理」および一般)
- 高速な特徴選択アルゴリズムCWCを用いた特徴語抽出 (特集 「情報セキュリティと知的データ処理」および一般)