| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-02-21 14:30 HDDを用いた省メモリK-meansクラスタリング ○大池洋史・岸 和芳・和田俊和（和歌山大）  PRMU2012-140 |
|
| 抄録 | （和） | 本報告では，大規模なデータに適用しても大量のメモリを必要としないK-meansクラスタリング手法を提案する．例えば，一般物体認識等で使用されるcode bookを作成する場合は，大量の局所特徴ベクトルに対するK-meansクラスタリングが必要となる．この際に，全データをメモリに展開する通常のK-means クラスタリングでは，大規模な問題に適用することは出来ない．本報告では，許容されるメモリ使用量の範囲内で，データを補助記憶装置(HDD)からメモリに逐次的にロードしながら計算を行うK-meansクラスタリングの計算方法を提案する．この手法は複数回のデータ走査を行う方法であり，１回目のパスでは，HDDからデータを順番に読み込みながらクラスタリングを行うことで，大数の法則に則った漸近的なクラスタ中心の移動を実現する．この際に，クラスタ中心を決定するための十分統計量と，各データがどのクラスタに所属したかを記録しておき，２回目以降のパスで，所属クラスタが変化した場合に，クラスタ中心の更新を行う．この更新のタイミングを調整することで反復計算の回数を削減し，処理速度を向上させる． |
| （英） | This report presents an “external” k-means clustering on HDD. K-means clustering is widely used for many applications. For example, codebook creation for Bag of Visual Words requires k-means clustering on huge amount of local feature vectors to obtain Visual Words (codebook entries). Standard “internal” k-means clustering loads the whole vector data on the main memory and performs clustering. This working memory can explode for huge amount of data. As a solution of this problem, we propose an “external” clustering algorithm on HDD. This is a multi-path algorithm, which scans the whole data in each path. In the first stage, cluster centroids are updated gradually, providing the data sequentially. Through this path, the number and the sum of the data are recorded for each cluster, and the belonging cluster is recorded for each data. In the following paths, each data is provided and the cluster center is updated for those data that changes belonging cluster. By adjusting this update frequency, the number of distance computation can be reduced and the performance can be improved. | |
| キーワード | （和） | K-meansクラスタリング / 省メモリ / 大規模データ / / / / / |
| （英） | K-means Clustering / memory-efficient / large-scale database / / / / / | |
| 文献情報 | 信学技報, vol. 112, no. 441, PRMU2012-140, pp. 61-66, 2013年2月. | |
| 資料番号 | PRMU2012-140 | |
| 発行日 | 2013-02-14 (PRMU) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | PRMU2012-140 |
|
| 研究会情報 | |
| 研究会 | PRMU |
| 開催期間 | 2013-02-21 - 2013-02-22 |
| 開催地（和） | 大阪府立大 |
| 開催地（英） | |
| テーマ（和） | 大規模データベースとパターン認識 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | PRMU |
| 会議コード | 2013-02-PRMU |
| 本文の言語 | 日本語 |
| タイトル（和） | HDDを用いた省メモリK-meansクラスタリング |
| サブタイトル（和） | |
| タイトル（英） | Memory Efficient K-means Clustering Using HDD |
| サブタイトル（英） | |
| キーワード(1)（和/英） | K-meansクラスタリング / K-means Clustering |
| キーワード(2)（和/英） | 省メモリ / memory-efficient |
| キーワード(3)（和/英） | 大規模データ / large-scale database |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 大池 洋史 / Hiroshi Oike / オオイケ ヒロシ |
| 第1著者 所属（和/英） | 和歌山大学 (略称： 和歌山大) Wakayama University (略称： Wakayama Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 岸 和芳 / Kazuyoshi Kishi / キシ カズヨシ |
| 第2著者 所属（和/英） | 和歌山大学 (略称： 和歌山大) Wakayama University (略称： Wakayama Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 和田 俊和 / Toshikazu Wada / ワダ トシカズ |
| 第3著者 所属（和/英） | 和歌山大学 (略称： 和歌山大) Wakayama University (略称： Wakayama Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-02-21 14:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | PRMU |
| 資料番号 | PRMU2012-140 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.441 |
| ページ範囲 | pp.61-66 |
| ページ数 | 6 |
| 発行日 | 2013-02-14 (PRMU) |
[研究会発表申込システムのトップページに戻る]