Locality-Sensitive Hashingを用いた階層的クラスタ分析手法(データマイニング)
スポンサーリンク
概要
- 論文の詳細を見る
階層的クラスタ分析は, 各データを一つのクラスタとみなし, 最も近いクラスタ同士を結合していき, 最終的に全データが一つのクラスタに含まれるまで結合を繰り返すという手法である.結合過程を樹形図で表現することで各クラスタ間の距離や包含関係が理解しやすく, 外的基準を必要としない教師なし自動分類であるため, 未知のデータ集合に対して有効である.しかし, データサイズnに対してO(n^2)の時間計算量がかかるため, 大規模なデータ集合に対して適用することは難しい.本論文では, 階層的クラスタ分析手法の一つであるSingle Link法の高速な近似手法を提案する.本手法は, 近似最近接点探索手法Locality-Sensitive Hashingを利用して, 結合すべきクラスタ, つまり近接するクラスタの探索にかかる手間を減らすもので, O(nB)の時間計算量を達成する.ここで, Bはハッシュテーブルの1エントリに格納されるデータ数の上限であり, テーブルサイズを十分大きくとることでnより十分小さくなる.更に実験により, 提案手法がSingle Link法と近似した結果を得られることや, 大規模データに対してより高速に実行できることを示す.
- 2005-04-01
著者
-
古賀 久志
電気通信大学大学院情報システム学研究所情報システム設計学専攻
-
渡辺 俊典
電気通信大学
-
石橋 徹夫
電気通信大学大学院情報システム学研究科
-
古賀 久志
電気通信大学 大学院 情報システム学研究科
関連論文
- 頻出グラフマイニングを利用した動画像解析(データマイニング)
- テキスト化を介した画像分類手法の提案(企業・学生交流セッション「企業のAI・大学のAI」)
- スライディングウィンドウを考慮したDynamic TCP Acknowledgment問題
- スライディングウィンドウを考慮した Dynamic TCP Acknowledgment 問題
- 指向性アンテナを用いた無線アドホックネットワークにおける空間の有効利用を目指したパワーコントロール手法(省電力)
- MPEG動きベクトルを用いたグローバルモーション推定に基づく移動物体のリアルタイム抽出(一般セッション,システム・制御のためのパターン認識・メディア理解)
- MPEG動きベクトルを用いたグローバルモーション推定に基づく移動物体のリアルタイム抽出
- モバイルアドホックネットワークにおけるマルチパスロードアウェアルーティングを利用した優先制御ベースのQoSフレームワーク(モバイル・アドホックネットワーク(1))
- 将来の輻輳状態の予測に基づくアクティブキュー管理手法の提案(アクティブネットワーク, IP-VPN, ネットワークセキュリティ, 超高速ネットワーク, P2P通信, ネットワークソフトウェア, 一般)
- MPEGビデオデータの動きベクトルを用いた圧縮領域における移動物体の検出と追跡(画像認識,コンピュータビジョン)
- MPEGビデオデータの動きベクトルを用いた移動物体追跡手法(一般セッション4)
- MPEGビデオデータの動きベクトルを用いた移動物体追跡手法(一般セッション,事例ベースメディア解析)
- オプティカルフローを用いた複雑背景下における人物領域の抽出(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 情報システム担当組織のための総合運営モデルの提案(情報システムの開発と運用,社会的課題に挑む情報システム)
- 超解像処理を用いたブレ画像修復手法(画像・映像処理)
- オプティカルフローを用いた複雑背景下における人物領域の抽出(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- TAMPOPO 学習機械を用いた自律化ネットワーク・オペレータ ANATA の適応能力の検証
- パッシブRTT推定法を使用したAQMアルゴリズム
- グラフカットを用いた動画像からの自動移動物体抽出(一般セッション,クロスモーダル)
- グラフカットを用いた動画像からの自動移動物体抽出(一般セッション,クロスモーダル)
- グラフカットを用いた動画像からの自動移動物体抽出(一般セッション,クロスモーダル)
- グラフカットを用いた動画像からの自動移動物体抽出(一般セッション,クロスモーダル)
- 画像の最小全域木の局所構造に着目したアピアランスベース3D物体認識手法(画像認識,コンピュータビジョン)
- MSTを用いたアピアランスベース3D物体認識手法の画像スケール変換下での性能分析
- 多次元特徴量直方体を用いたアピアランスベースオブジェクト認識手法
- ユークリッド空間内の点分布の外郭を求めるアルゴリズム(一般セッション,クロスモーダル)
- ユークリッド空間内の点分布の外郭を求めるアルゴリズム(一般セッション,クロスモーダル)
- ユークリッド空間内の点分布の外郭を求めるアルゴリズム(一般セッション,クロスモーダル)
- ユークリッド空間内の点分布の外郭を求めるアルゴリズム(一般セッション,クロスモーダル)
- 多頻度グラフマイニングを利用した動画の解析(一般セッション1,移動カメラ画像処理におけるパターン認識とメディア理解)
- 近傍集合表現を利用した画像からのオブジェクト自動抽出(画像認識,コンピュータビジョン)
- 映像からの動作オブジェクト自動学習システムAMOR(一般セッション1,文字・文書の認識・理解)
- 異種の高速トランスポートプロトコルへの帯域公平性を考慮したUDTの改良(ネットワークモデルと通信プロトコル,インターネットトラヒック,TCP/IP,性能解析・評価,ネットワークモデル及び一般)
- 最小全域木の適応しきい値切断による画像分割方式(画像処理,画像パターン認識)
- 直交する2つの最小全域木(MST)を用いた画像特徴抽出可能性の検討
- 圧縮性とオブジェクトらしさ尺度に着目した画像からのオブジェクト自動抽出法(一般,日本・韓国におけるPRMU技術の産業応用)
- マルチフェーズハッシュを利用した部品ベースオブジェクト発見手法(一般セッション7)
- マルチフェーズハッシュを利用した部品ベースオブジェクト発見手法(一般セッション7,顔・ジェスチャの認識・理解)
- マルチフェーズハッシュを利用した部品ベースオブジェクト発見手法(一般セッション7,顔・ジェスチャの認識・理解)
- H-001 両方向ゼロ比較に基づくノイズベクトルの除去(H分野:画像認識・メディア理解,一般論文)
- 投票機構による動作オブジェクトのオンラインリアルタイム学習と認識(画像認識,コンピュータビジョン)
- 輸送問題の解法に基づく動き領域抽出手法
- 木編集距離を利用した木データの構造と内容の類似性を反映する分類手法(一般セッション(1),データ工学とメディア理解との融合)
- 木編集距離を利用した木データの構造と内容の類似性を反映する分類手法(一般セッション(1),データ工学とメディア理解との融合)
- 属性付きグラフマッチングアルゴリズムの効率的な実装(セッション4)
- 投票機構を用いた動作モデルのオンライン自動獲得(一般セッション)
- 投票機構を用いた動作モデルのオンライン自動獲得(一般セッション)
- 競合度によるオンラインアルゴリズムの解析(学生のページ)
- 場との相互作用による群ロボットの協調搬送行動
- フラクタル符号の写像対応に基づく特徴量と類似検索について(画像の表現ならびに一般(グラフィックス/アニメ, コンテンツ配信, 認識/理解, 色空間, 信号処理など))
- 最小全域木(MST)の深さ優先探索による画像分割方式
- 多次元特徴量直方体の相関関係を用いたオブジェクト認識方式FRCMの機能検証
- 最小全域木(MST)の深さ優先探索による画像分割方式
- 多次元特徴量直方体の相関関係を用いたオブジェクト認識方式FRCMの機能検証
- 最小全域木(MST)の深さ優先探索による画像分割方式
- 航空写真内オブジェクトに関する半自動観念抽出方式
- Locality-Sensitive Hashingを用いた階層的クラスタ分析手法(データマイニング)
- Locality-Sensitive Hashingを用いた階層的クラスタ解析手法の近似解法(文字とドキュメントの認識・理解)
- Locality-Sensitive Hashing を用いた階層的クラスタ解析手法の近似解法(文字とドキュメントの認識・理解))
- Locality-Sensitive Hashingを用いた階層的クラスタ解析手法の高速化
- 画像からのオブジェクト記述の自動抽出
- 画像からのオブジェクト定義自動抽出手法の研究
- 画像オブジェクトに関する概念抽出と認識手法
- 画像オブジェクトに関する概念抽出と認識手法
- 骨格線を利用したオブジェクト検索手法(一般セッション(3))
- 高次元圧縮空間の対話的手法による次元縮小(機械学習)
- LZ78の圧縮性を利用した文書検索手法の提案(情報検索・情報抽出・QA)
- LZ78の圧縮性を利用した文書検索手法の提案(情報検索・情報抽出・QA)
- 圧縮性に注目した文書の関係分析手法(文書分類・評判分析)
- 圧縮性に注目した文書の関係分析手法(文書分類・評判分析)
- 背景の分割に対応したグラフマイニングベースの動画像からの背景除去
- フラクタル符号のベクトル集合間類似度に基づく検索の高速化手法
- フラクタル符号に基づく圧縮領域における類似画像検索手法
- 木のDPマッチングによるオブジェクト類似度の解析(文字とドキュメントの認識・理解)
- 木のDPマッチングによるオブジェクト類似度の解析(文字とドキュメントの認識・理解))
- フラクタル符号の写像情報に基づいた圧縮領域における類似度(エンタテインメントのためのパターン認識・メディア理解)
- テンポラルテンプレートを用いた動画解析手法
- ユークリッド空間内の点分布の外郭を求めるアルゴリズム
- 画像認識用データ圧縮空間の自動構成方式
- 多次元特徴量直方体の相関関係を用いたオブジェクト認識手法FRCM
- エンドホストでのAQMエミュレーションによるTCPコネクション間のスループット公平性改善(TCP)
- テンポラルテンプレートを用いた動画解析手法
- フラクタル符号に基づく構造的な類似性抽出手法の提案
- ピット近似関数を用いた局所解集合探索(セッション4)
- ピット近似関数を用いた局所解集合探索(セッション4)
- 圧縮率を利用した画像からのオブジェクト自動抽出(一般セッション(3))
- オンライン実時間 PCA を用いた動画からの変動背景の推定(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- オンライン実時間 PCA を用いた動画からの変動背景の推定(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 相互写像に基づくベクトル集合間類似度とその上限値(一般セッション(4))
- 投票機構を用いた人物動作の認識手法(一般セッション(1))
- クラスタリングアルゴリズム LSH-Link を利用した動画像からのオブジェクト軌跡の自動抽出(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- クラスタリングアルゴリズム LSH-Link を利用した動画像からのオブジェクト軌跡の自動抽出(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 木の DP マッチングを利用した DTD 類似度の考察(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 木の DP マッチングを利用した DTD 類似度の考察(学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 相互写像に基づくベクトル集合間類似度とその上限値(一般セッション(4))(CVのためのパターン認識・学習理論の新展開)
- LI-010 フラクタル符号のベクトル集合間類似度に基づく画像検索手法(I. 画像認識・メディア理解)
- 分散環境におけるL_1距離ベースLocality-Sensitive Hashingの通信回数削減手法とその実装評価(データ処理アルゴリズム,e-science and Big Data,一般)
- SURF特徴点を用いたグラフカットによる動画像からの移動物体自動抽出結果の精度向上(一般セッション,実世界文字認識と理解)
- 時系列の圧縮性を用いたネットワークトラフィックの適応的パターン解析(オーバーレイネットワーク,P2Pネットワーク,自律分散制御及び一般)
- SURF特徴点を用いたグラフカットによる動画像からの移動物体自動抽出結果の精度向上