パターン認識問題における終端条件の付加によるk近隣法の高速化
スポンサーリンク
概要
- 論文の詳細を見る
k近隣法の計算量を減らすため方法の一つである大町らの手法に終端条件を付加することを提案する.k近隣法を効率的に実行する枠組みの一つに分枝限定法がある.これは, 階層的なクラスタリングにより探索木を作り, 逐次更新される基準に基づいて, 枝刈りにより冗長な探索を避ける方法である.大町らは, 探査木をクラスごとに構築する方式で更に分枝限定法を効率化できることを示している.しかし, 彼らの方法では探索途中に真のk近隣点が見つかった場合でも探索を最後まで続ける.本研究では, 真のk近隣点が発見された際に, その事実を判定できる終端条件を付加することにより, 探索時の計算量が削減できることを示す.また, 手法の有効性について実験的検証を行う.
- 社団法人電子情報通信学会の論文
- 2001-03-01
著者
-
工藤 峰一
北海道大学大学院情報科学研究科
-
外山 淳
北海道大学大学院情報科学研究科
-
新保 勝
北海道大学大学院工学研究科システム情報工学専攻数理情報工学講座
-
外山 淳
北海道大学
-
工藤 峰一
北海道大学大学院工学研究科システム情報工学専攻
-
新保 勝
北海道情報大
-
益山 直人
北海道大学大学院工学研究科システム情報工学専攻
-
工藤 峰一
北海道大学情報科学研究科
-
新保 勝
北海道大学大学院工学研究科
-
新保 勝
北海道大学
-
工藤 峰一
北海道大学 大学院情報科学研究科
関連論文
- Data compression by volume prototypes for streaming data
- Probably correct k-nearest neighbor search in high dimensions
- 複数アクションを選択するAdversarial Bandit問題について
- ウエーブレットパケット解析を用いた音声符号化
- 編集距離による最類似文字列の探索高速化に関する研究(テーマ,膨大なデータから学ぶもの)
- 多面体識別子族における識別子選択(一般セッション1,移動カメラ画像処理におけるパターン認識とメディア理解)
- 非確率的なmulti-armed bandit問題における分散投資の効果について(一般セッション4,移動カメラ画像処理におけるパターン認識とメディア理解)
- パッキングアライメントとその音楽マイニングへの応用
- Notes on Enumeration of Concepts in a Sperner Family Concept Class Using Subconcept Queries (Foundations of Theoretical Computer Science : For New Computational View)
- 部分クラスの複雑さと列挙法について
- 木構造データに対する頻出類似部分木の発見(テーマセッション,データ工学とメディア理解との融合)
- LA_001 繰返し表現木最小化アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- 繰返し構造をもつラベル付順序木の簡潔な表現法(計算理論とアルゴリズムの新展開)
- 両方向 N-gram 確率を用いた誤り文字検出法(自然言語処理)
- 節点包含制約を満たす頻出木マイニング
- ルールの予測精度と興味深さに関する検討(テーマセッション(1))(データマイニングとパターン認識・メディア理解)
- 両方向N-gram確率を用いた確率変化パターンによる誤り検出(テーマセッション(1))(データマイニングとパターン認識・メディア理解)
- Webデータベース汎用システムの開発と音声データ管理システムとしての利用(テーマセッション: Web, データ工学とメディア理解との融合)
- 哺乳類における5'-スプライスサイトの配列パターンの位置木による解析
- グラフによるインタラクティブなデータ分析と決定木の構成(パターン認識)
- 識別情報を利用したクラス情報のグラフ表示
- グラフによる多次元データの構造解析
- 編集距離による最類似文字列の探索高速化に関する研究(テーマ,膨大なデータから学ぶもの)
- パターン認識における都市伝説 (パターン認識・メディア理解)
- 体積プロトタイプの解析と混合分布モデルとの比較(一般セッション,データ工学とメディア理解との融合)
- 体積プロトタイプの解析と混合分布モデルとの比較(一般セッション,データ工学とメディア理解との融合)
- Webデータベース汎用システムの開発と音声データ管理システムとしての利用(テーマセッション: Web, データ工学とメディア理解との融合)
- 音声分析のための Web-データベース連携システムの検討
- 位相を考慮したスペクトルサブトラクションを用いた単語認識
- パターン認識問題における終端条件の付加によるk近隣法の高速化
- スプライン曲面を用いた画像の2チャネル符号化
- 聴覚フィルタ出力に補正を施した音声認識
- 通過領域に着目した多次元空間における曲線分類
- 連母音の挙動に含まれる個人性情報の抽出
- 分枝限定法利用の最近隣法における終端条件の効果
- 複数領域の隣接関係に基づく自然シーンの高速ラベリング
- 非線形変換を用いた連母音わたり部の挙動推定
- 非線形識別関数のための特徴選択
- 顔の幾何学的特徴による個人識別
- 領域の隣接関係を用いたラベル画像の生成
- 特殊な合成母音における音素境界の曖昧さ
- 極小値が単峰列な傾向をもつ多峰関数の大域的最適化法
- 極小値が単峰列で単峰領域幅が等しい一変数多峰関数の大域的最適化法
- 無声母音のピッチと音韻性に対するホルマント周波数とスペクトルの傾斜の影響
- 無声母音のホルマント周波数と音韻性に関する検討
- 音響を利用した掃流砂観測手法の開発
- パターン認識における都市伝説(テーマセッション,パターン認識とメディア理解のフロンティアとグランドチャレンジ)
- 凸包によるクラス領域の近似
- 混合分布を用いた識別規則における最適な混合数の選択
- 手書き漢字同定のための動的モデルによるストローク抽出
- 識別問題におけるMDL基準を用いたクラスタリング法
- 圧力センサを用いた着席者の姿勢識別に関する研究(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- 圧力センサを用いた着席者の姿勢識別に関する研究(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- Design of Decision Trees Using Class-Dependent Feature Subsets
- 音響管モデルに束縛を与えた音声合成(合成,生成,韻律,一般)
- SNRの変化に適応するSS法による雑音混入音声の認識(福祉と知能・情動・認知障害,福祉と音声処理,一般)
- SNRの変化に適応するSS法による雑音混入音声の認識(福祉と知能・情動・認知障害,福祉と音声処理,一般)
- SNRの変化に適応するSS法による雑音混入音声の認識(福祉と知能・情動・認知障害,福祉と音声処理,一般)
- S/N比に自動適合するHMM合成法を用いた単語認識
- S/N比に自動適合するHMM合成法を用いた単語認識
- 劣決定信号復元における最小l_1ノルム系列の効率的構成(一般セッション(8))(データマイニングとパターン認識・メディア理解)
- モデル選択基準を用いた非線形識別関数の構成
- 孤立発声母音を用いた聴覚モデルによる話者認識
- スプライン曲面を使った画像情報の圧縮
- 階層的重複クラスタリングによるウェブ検索結果の集約(一般セッション4,移動カメラ画像処理におけるパターン認識とメディア理解)
- データ部分集合と特徴部分集合の同時選択による識別子統合(一般セッション,データ工学とメディア理解との融合)
- データ部分集合と特徴部分集合の同時選択による識別子統合(一般セッション,データ工学とメディア理解との融合)
- Knowledge-Based Enhancement of Low Spatial Resolution Images
- Interactive Data Analysis Based on Graph and Construction of Decision Trees
- 超矩形による貪欲被覆学習の効率的実装と実データによる性能評価(IBIS2010(情報論的学習理論ワークショップ))
- 木構造データに対する頻出類似部分木の発見(テーマセッション,データ工学とメディア理解との融合)
- 体積プロトタイプによるデータ集約(テーマセッション(4),パターン認識・メディア理解のための学習理論とその応用)
- 情報の粒度を用いた属性値の抽象化(テーマセッション(4),パターン認識・メディア理解のための学習理論とその応用)
- 特徴選択 : これまでと今後の展開(テーマセッション(2),パターン認識・メディア理解のための学習理論とその応用)
- 特徴選択 : これまでと今後の展開
- 最小包含球の族による被覆を用いたノンパラメトリック識別(一般セッション(2))(ユビキタスコンピューティングのためのパターン認識・メディア理解,一般)
- 節点包含制約を満たす頻出木マイニング
- 包含と排除によるκ最近隣法の高速化(テーマセッション(3))(データマイニングとパターン認識・メディア理解)
- クラスに依存した特徴集合を用いた決定木の設計(パターン認識)
- クラスに依存した特徴集合の有効性の検討
- クラスに依存した特徴集合の有効性の検討
- 同時マスキングモデルによる母音の特徴抽出
- 連母音わたり部の挙動を利用した後続母音の認識
- 後舌母音の知覚に及ぼす基本周波数と遮断周波数の影響
- 聴覚モデルによる母音の特徴周波数の抽出
- 母音の音韻性におよぼす継続時間の影響
- 幾何学モデルを用いた連母音わたり部の挙動推定
- マスキングモデルによる子音の認識
- 二次遅れを考慮したニューラルネットワークによる時系列の学習
- 所属性質問を利用した区分的線形識別規則の追加学習
- 統計的弛緩法による図形分節モデル
- 時変パラメータを用いた母音および半母音の認識 (情報工学専攻創立20周年記念号)
- 極小値が単峰列となる多峰関数の大域的最適化手法(1) : 単峰領域幅が等しい目的関数の大域的最適化(数値計算,数理計画法)
- 音源の個人性を考慮した声質変換(一般(ポスターセッション),第12回音声言語シンポジウム:情報アクセス,音声・言語処理一般)
- 音源の個人性を考慮した声質変換(一般(ポスターセッション),第12回音声言語シンポジウム:情報アクセス,音声・言語処理一般)
- 大規模データに対する識別子独立型の特徴選択(一般セッション,PRMUのフロンティア・グランドチャレンジ)
- Closeness Centralityの高いノードを発見する高速アルゴリズム
- 1-Median問題の高速な近似アルゴリズム (特集 「Webと知識連携・統合,発想支援」および一般)
- マッチング選択多腕bandit問題の効率的解法アルゴリズム (特集 「Webと知識連携・統合,発想支援」および一般)
- 順列バンディット問題における新しいUCB型アルゴリズム(一般)