最小外接矩形とセルの再帰分割を用いたセルベースのDBSCANの高速化

酒井 達弘  田村 慶一  北上 始  竹澤 寿幸  

誌名
電子情報通信学会論文誌 D   Vol.J101-D   No.4   pp.690-701
発行日: 2018/04/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2017DEP0009
論文種別: 特集論文 (データ工学と情報マネジメント論文特集)
専門分野: クラスタリング
キーワード: 
密度に基づくクラスタリング,  DBSCAN,  最小外接矩形,  高速化,  データマイニング,  

本文: PDF(1.1MB)
>>論文を購入


あらまし: 
密度に基づくクラスタリングはデータの密度をクラスタリングの基準とした,任意形状のクラスタを抽出できるクラスタリング手法である.近年,ビッグデータへの注目の高まりとともに,データベースの大規模化と多次元化が進んでいる.そこで,多くの研究者によって密度に基づくクラスタリングの代表的な手法であるDBSCANの高速化が行われてきた.DBSCANの高速化手法の一つとして,セルベースのDBSCANが提案されている.セルベースのDBSCANはデータセット全体を小さいセルに分割し,データの密度をセル単位で考え,セルを結合することでクラスタリングを行う.セルベースのDBSCANは既存のDBSCANよりも高速にクラスタリングを行えるが,セルの結合判定に多くの時間を要することが明らかとなっている.そこで本論文では,最小外接矩形(MBR)とセルの再帰分割を用いた新しいセルベースのDBSCANを提案する.提案手法はセルの結合判定について,MBRを用いた結合判定とセルの分割を再帰的に行うことによって,高速に処理することができる.評価実験の結果,提案手法は既存手法と比較して高速化できることを示した.