DEIM Forum 2019 H1-5

セルベースの DBSCAN の Anytime アルゴリズム
酒井達弘†,††

田村

慶一†

北上

始†††

竹澤

寿幸†

† 広島市立大学大学院情報科学研究科 〒 731–3194 広島県広島市安佐南区大塚東 3–4–1†† 日本学術振興会特別研究員 PD 〒 102–0083 東京都千代田区麹町 5–3–1††† 広島工業大学情報学部 〒 731–5193 広島県広島市佐伯区三宅 2–1–1
E-mail: sakai@hiroshima-cu.ac.jp, {ktamura,takezawa}@hiroshima-cu.ac.jp, h.kitakami.su@it-hiroshima.ac.jp
あらまし

DBSCAN はデータの密度をクラスタリングの基準とした，任意形状のクラスタを抽出可能なデータクラスタリング手法である．DBSCAN には，各データの近傍を求めるための範囲検索とクラスタを形成するための到達可能データ探索という計算コストの大きい二つの処理がある．そこで，DBSCAN の高速化手法としてセルベースのDBSCAN が提案されている．セルベースの DBSCAN はデータセット全体を小さいセルに分割し，密度をセル単位で考え，セルを結合していくことでクラスタリングを行う．本論文では，一定の精度を持つクラスタリングの途中結果
を高速に出力でき，最終的には厳密解を出力可能なセルベースの DBSCAN の Anytime アルゴリズムを提案する．提案手法は乱択アルゴリズムに基づくセルの結合とクラスタリングの途中結果の算出を繰り返し行う．提案手法が算出するクラスタリング結果は，処理が進むに連れて高精度となり，最終的には厳密解となる．評価実験の結果，提案手法は一定の精度のクラスタリング結果を高速に算出でき，また既存手法と比較して高速に厳密解を算出できることを示した．
キーワード DBSCAN，密度に基づくクラスタリング，Anytime アルゴリズム，セルベースの DBSCAN

1 はじめに近年，ビッグデータへの注目の高まりとともにデータベースの大規模化が進んでおり，データマイニング分野においてデー
タクラスタリング手法の高速化に関する研究が注目を集めている．Ester ら [1]，[2] によって提案された密度に基づくクラスタ
リングは，最も有名なデータクラスタリング手法の一つである．
密度に基づくクラスタリングは予めクラスタ数を指定することなく任意形状のクラスタを自動的に抽出可能な手法として様々な分野で利用されている．密度に基づくクラスタリングの代表的な手法として DBSCAN（Density-based spatial clusteringof applications with noise）がある．DBSCAN は密度の基準として，データから距離 ϵ 以内の近傍に含まれるデータ数を用いる．そして，近傍内に閾値 M inP ts 以上のデータが存在する
とき当該データをコアデータと呼び，コアデータを接続していくことでクラスタリングを行う．

DBSCAN には，各データの近傍を求めるための範囲検索とクラスタを形成するための到達可能データ探索という計算コストの大きい二つの処理がある．そこで，DBSCAN の高速化について数多くの研究が行われてきた．高速化の研究では，
厳密解を返す手法と近似解を許す手法に分かれている．現在，
厳密解を返す DBSCAN の高速化手法として，セルベースのDBSCAN [3]，[4]，[5] が提案されている．
セルベースの DBSCAN は範囲検索の回数を大幅に削減し，小さく分割されたセルを基準にクラスタを形成することで到達可能データ探索の処理を必要としないため，処理の高速化が実現できている．セルベースの DBSCAN は 2 次元の場合におい√て，データセット全体を一辺が長さ ϵ/ 2 の小さいセルに分割する．ここで，セル内のデータ数が M inP ts 以上である場合，セル内の全てのデータは自動的にコアデータであると判定できる．そして，コアデータを含むセルを結合していくことでク
ラスタリングを行う．二つのセル間に距離 ϵ 以内の任意のコア
データのペアがある場合にのみ，その二つのセルを結合する．
我々は先行研究 [6]，[7] において，このセルの結合判定に最小外接矩形とセルの再帰分割を用いることで処理の高速化を行った．

DBSCAN の Anytime アルゴリズムとして，乱択アルゴリズ
ムに基づく AnyDBC が提案されている [8]．Anytime アルゴ
リズムとは，任意の時刻でその時点での一定の精度の解を出力することができ，処理を再開することができるようなアルゴリ
ズムである [9]．データクラスタリング手法における Anytime
アルゴリズムは，任意の時刻で一定の精度を持つクラスタリン
グ結果を出力でき，最終的には厳密解のクラスタリング結果を出力可能なアルゴリズムとなる．AnyDBC はランダムに選択したいくつかのデータに対して範囲検索を行いクラスタを形成し，クラスタリングの途中結果を算出する．そして，再びい
くつかのデータに対して範囲検索を行いクラスタを再形成し，処理が進むに連れて精度の高いクラスタリング結果を算出していく．しかしながら，AnyDBC はデータ分布や選択される
データによって処理時間が大きくなる場合があり，セルベースの DBSCAN に比べて処理時間が安定しない．
そこで本論文では，セルベースの DBSCAN に乱択アルゴリ
ズムの考えを導入した Anytime アルゴリズムを提案する．本
論文の貢献は以下の通りである．

•

一定の精度を持つクラスタリングの途中結果を高速に出力でき，最終的には厳密解を出力可能なセルベースの DBSCANの Anytime アルゴリズムを提案する．提案手法は乱択アルゴ
リズムに基づくセルの結合とクラスタリングの途中結果の算出を繰り返し行う．提案手法が算出するクラスタリング結果は，処理が進むに連れて高精度となり，最終的には厳密解となる．

•

݀‫ݐ‬ଵ

評価実験により，提案手法は一定の精度のクラスタリン

グ結果を高速に算出でき，また既存手法と比較して高速に厳密݀‫ݐ‬ସ

解を算出できることを示す．
本論文の構成は以下の通りである．第 2 章では，関連研究を説明する．第 4 章では，提案手法について説明する．第 5 章で2 関連研究

݀‫ݐ‬ଶ
=5

図1

は，評価実験の結果を示し，第 6 章で本論文をまとめる．

݀‫ݐ‬ହ

݀‫ݐ‬ଷ

ܰఢ ݀‫ݐ‬ଵ

述べる．第 3 章では，DBSCAN とセルベースの DBSCAN を߳ܰఢ ݀‫ݐ‬ଶ=3

定義 1 と定義 2 の例

め，kd-tree といった索引構造の構築が必要となり，セルベー
スの DBSCAN に比べて多くのメモリを要する．本論文では，

近年，ビッグデータへの注目の高まりとともにデータベー

安定して処理を高速化でき，索引構造を必要としないセルベースの大規模化が進んでおり，データクラスタリング手法の高スの DBSCAN に着目し，セルベースの DBSCAN の Anytime

速化に関する研究が注目を集めている．密度に基づくクラス

アルゴリズムを提案する．DBSCAN の高速化の研究において，タリング [1]，[2] はデータの密度をクラスタリングの基準としセルベースの DBSCAN の Anytime アルゴリズムは提案された汎用的に使用されているクラスタリング手法であり，多くていない．

の研究者によってその代表的な手法である DBSCAN の高速化が行われてきた．DBSCAN の高速化の研究では，クラス

3 事前準備

タリング結果が厳密解となる手法 [10]，[11] と近似解を許す手
法 [12]，[13]，[14]，[15]，[16]，[17] がある．近似解を許す手法はパ

本章では，DBSCAN とセルベースの DBSCAN について説

ラメータやデータ分布によっては得られるクラスタリング結果

明する．

が厳密解とは異なる場合があるが，厳密解を返す手法よりも高3. 1 DBSCAN

速化することができる．

DBSCAN の高速化手法としてセルベースの DBSCAN [3]，[4]，[5] が提案されている．セルベースの DBSCAN は範囲検索の回数を大幅に削減し，小さく分割されたセルを基準にクラスタを形成するため到達可能データ探索の処理を必要としない．
また，セルベースの DBSCAN は範囲検索に依存しておらず，索引構造の構築を必要としないため，メモリの使用を抑えることができる．我々は先行研究 [6]，[7] において，セルベースのDBSCAN の最も処理時間を要するセルの結合判定に最小外接

本節では，DBSCAN の諸定義を説明する．d 次元のデータ
集合を DT とし，ϵ と M inP ts をユーザが与えるパラメータとする．データ dtp ∈ DT について，dtp から距離 ϵ 以内に存在するデータ集合を dtp の ϵ-近傍と呼び，Nϵ (dtp ) と表記する．
本研究では，データ間の距離はユークリッド距離と定める．
定義 1 (コアデータ)

デ ー タ dtp の ϵ-近 傍 に つ い て ，>|Nϵ (dtp )| = M inP ts を満たすとき，dtp をコアデータと呼ぶ．

矩形とセルの再帰分割を用いることで処理の高速化を行った．

DBSCAN の Anytime アルゴリズムとして，乱択アルゴリズ
ムに基づく AnyDBC が提案されている [8]．AnyDBC はランダムに選択したいくつかのデータに対して範囲検索を行いクラスタを形成し，クラスタリングの途中結果を算出する．そして，
再びいくつかのデータに対して範囲検索を行いクラスタを再形

定義 2 (ϵ-密度的に到達可能)

データ列 (dt1 , dt2 , · · · , dtn ) について，以下の条件を満たすとき，dt1 から dtn へ ϵ-密度的に到達可能であると表現する．
（1） dt1 , dt2 , · · · , dtn−1 がコアデータである．
（2） dti+1 が dti の ϵ-近傍に存在（dti+1 ∈ Nϵ (dti )）する．

成し，処理が進むに連れて精度の高いクラスタリング結果を算図 1 に定義 1 と定義 2 の例を示す．M inP ts = 4 とする．

出していく．また，クラスタリング結果に変化を与えないデー

データ dt1 の ϵ-近傍は dt1 を含めると |Nϵ (dt1 )| = 5 となるの

タに対しては範囲検索を行わないことで，範囲検索の回数を削で，dt1 はコアデータとなる．反対に，データ dt2 の ϵ-近傍は減でき，効率よく厳密解に近づくことを示している．

|Nϵ (dt2 )| = 3 であるため，dt2 はコアデータではない．また，

しかしながら，AnyDBC はランダムに行う範囲検索で多くのデータをカバーできない場合，範囲検索の回数が多くなるた

dt1 から dt3 と dt4 へは ϵ-密度的に到達可能であるが，dt2 からdt5 へは ϵ-密度的に到達可能ではない．

め処理時間が大きくなり，セルベースの DBSCAN に比べて処DBSCAN において，密度に基づくクラスタはコアデータか理時間が安定しない．また，範囲検索に依存する手法であるたら ϵ-密度的に到達可能なデータを再帰的に接続していくことで݀‫ݐ‬ଵ
݀‫ݐ‬ଶ

߳

߳/ 2

Step0

Step1

Step2

図 3 乱択アルゴリズムに基づくセルの結合

߳/ 2

図 2 セルベースの DBSCAN の例

3. 2. 3 コアデータ判定
次に，各データがコアデータであるかそうでないか判定する．セル内のデータ間の距離は最大でも高々ϵ であり，セル内にデータが M inP ts 以上存在する場合，そのセル内のデータ形成されていく．コアデータではないがコアデータから ϵ-密度的に到達可能なデータをボーダデータと呼ぶ．また，どのコアデータからも ϵ-密度的に到達可能ではないデータをノイズと呼ぶ．密度に基づくクラスタの定義を以下に示す．

は全てコアデータと判定できる．反対に，セル内のデータ数がM inP ts 未満の場合，そのセル内のデータについては近傍セルに存在するデータとの距離計算を行い，コアデータであるか判定する．図 2 の例を見ると，M inP ts = 5 とすると，グレーで示しているセルにはデータが 5 以上あり，これらのセルに属す

定義 3 (密度に基づくクラスタ)

データ集合 DT において，密度に基づくクラスタ DBC は以下の条件を満たす部分データ集
合である．

るデータは全てコアデータとなる．

3. 2. 4 セ ル 結 合次に，コアデータを含むセルを結合しクラスタを形成してい（1） 任意のコアデータ dtp ∈ DBC について，DBC に属す

く．二つのセル間に距離 ϵ 以内の任意のコアデータのペアがある全てのデータは dtp から ϵ-密度的に到達可能である．

る場合，二つのセルに含まれる全データは ϵ-密度的に到達可能（2） 任意のデータ dtp ，dtq ∈ DBC について，dtp と dtq へとなり，二つのセルを結合しセル内のデータ集合でクラスタを

ϵ-密度的に到達可能な dto ∈ DBC が存在する．

形成する．セルの結合判定には，先行研究 [7] にて提案された
最小外接矩形とセルの再帰分割を用いる．図 2 の例では，左上

3. 2 セルベースの DBSCAN
本節では，セルベースの DBSCAN について説明する．セル
ベースの DBSCAN はセル分割，近傍セルリストの作成，コアに密集しているセルに属するデータ集合と，右下に密集しているセルに属するデータ集合とで二つのクラスタが形成される．

3. 2. 5 ボーダデータとノイズの判定

データの判定，セル結合とボーダデータとノイズの判定の五つ

最後に，コアデータではないデータに対してクラスタに属すの処理から構成される．五つの処理が完了すると，各データはるボーダデータ，もしくはノイズとなるか判定する．判定する

定義 3 を満たすクラスタを形成するか，またクラスタに属さな

データについて，もし ϵ 以内にコアデータが存在する場合，そいノイズとなるかが決定する．

のデータはボーダデータとなり，最も近いコアデータが属する

3. 2. 1 セ ル 分 割

クラスタに属する．反対に，ϵ 以内にコアデータが存在しない

最初に，データセット全体を小さいセルに分割し，各データ場合，そのデータはクラスタに属さないノイズとなる．図 2 のを一つのセルに割り当てる．セルは一辺の長さが同じ超立方体√とする．d をデータの次元数とすると，セル一辺の長さは ϵ/ d√となる．セル一辺の長さを ϵ/ d とすることでセルの対角線の例を見ると，データ dt1 から距離 ϵ 以内にコアデータが存在し長さは ϵ となる．図 2 にセルベースの DBSCAN の例を示す．
√√
図 2 は d = 2 であり，ϵ/ 2 × ϵ/ 2 のセルに分割されている．

3. 2. 2 近傍セルリストの作成ており，dt1 はボーダデータとなる．反対に，データ dt2 から
距離 ϵ 以内にはコアデータが存在していないので，dt2 はノイズとなる．

4 提案手法次に，各セルの近傍セルリストを作成する．あるセルから最短距離が ϵ 以下のセルを，そのセルの近傍セルと呼び，各セルの近傍セルリストを作成する．近傍セルリストを作成すること
で，あるデータの ϵ-近傍を求める際に，そのデータが属するセ
ルの近傍セルリストの内のデータとの距離を計算するのみで，求めることができる．

本章では，提案手法について説明する．

4. 1 概要

提案するセルベースの DBSCAN の Anytime アルゴリズム
は，セル結合の処理において，乱択アルゴリズムに基づいてい
くつかのセルの結合を行いクラスタを形成する．そして，結合されたセル以外のセルに属する残されたデータについてボーダ

Algorithm 1 セルベースの DBSCAN の Anytime アルゴリ

データとノイズの判定を行い，クラスタリングの途中結果を算ズム

出する．提案手法は乱択アルゴリズムに基づくセル結合とクラInput: DT , d, ϵ, M inP ts, p

スタリングの途中結果の算出を繰り返し行う．提案手法が算出

Output: ClusterList，N oiseListするクラスタリング結果は，処理が進むに連れて高精度となり，

1: /*セル分割*/

最終的には厳密解となる．

4. 2 乱択アルゴリズムに基づくセル結合
本節では，乱択アルゴリズムに基づくセル結合について説明する．クラスタリング結果の算出回数を p とする．最初に，セ3: データ数が 0 個のセルを CellList から削除
4: /*近傍セルリストの作成*/
5: for i = 0 to |CellList| do
6:

Ci の近傍セルリストを作成

7: end forを作成する．そして，CellP airList からランダムにセルのペ8: /*コアデータ判定*/

アを選択してセルの結合判定を行い，二つのセルが結合できる

9: for i = 0 to |CellList| doと判定された場合，セルの結合行う．提案手法はセルの結合判

10:

定と結合の処理を (|CellP airList|/p) 回行う度に，ボーダデー

11:

p 回目に算出するクラスタリング結果は，全てのセルの結合判

12:
13:
14:

定と結合を終えており，厳密解となる．

if |Ci | >= M inP ts thenCi 内のデータをコアデータとする
else
for j = 0 to |Ci | do
Ci 内の j 番目のデータに対して，近傍セル内のデータとの距離計算を行いコアデータ判定を行う

図 3 に乱択アルゴリズムに基づくセルの結合の例を示す．図15:3 の例は p = 2 としており，Step1 では，ランダムに選ばれた

16:

いくつかのセルが結合し，二つのクラスタを形成している．提17: end forend forend if

案手法は Step1 の段階で，残されたデータに対してボーダデー

18: for i = 0 to p do

タとノイズの判定を行い，クラスタリングの途中結果を算出す

19:

ClusterList = ϕ，N oiseList = ϕ

20:/*セル結合*/る．Step2 では，全てのセルの結合判定と結合を終えており，

21:

最終的な厳密解となる．

4. 3 アルゴリズム

セルの結合判定を行う必要があるセルのペアリスト

CellP airList を計算
22:23:

本節では，提案手法のアルゴリズムについて説明する．提案

for i = 0 to (|CellP airList|/p) do
CellP airList から結合判定を行っていないセルのペア Ci とCj をランダムに選択手法の流れを Algorithm1 に示す．Algorithm1 は入力として，

24:

データセット DT ，次元数 d，ϵ-近傍の距離 ϵ，閾値 M inP ts，

25:

クラスタリング結果の算出回数 p を入力として受け取り，ク26:

end if

ラスタリスト ClusterList とノイズリスト N oiseList を出力

27:

end forする．

√
まず，データセット全体を一辺の長さが ϵ/ d の超立方体に

28:

if CheckConnectCells(Ci , Cj , ϵ) == true thenCi と Cj を結合結合されたセル内のデータ集合をクラスタとし，ClusterList
を作成

29:

/*ボーダデータとノイズの判定*/

分割してセルリスト CellList を作成し，各データをセルに割り

30:

for i = 0 to |DT | do

当て，データ数が 0 個のセルは削除する（2〜3 行）．次に，各31:

Ci はセルとする．そして，各データがコアデータであるかそう

32:

でないか判定する（9〜17 行）．乱択アルゴリズムに基づくセ33:

データとノイズの判定を行い，N oiseList を作成する（30〜36
行）．現時点でのクラスタリング結果として，ClusterList とN oiseList を保存しておく（37 行）．乱択アルゴリズムに基づ

if dti がコアデータではなく，dti の ϵ 以内にコアデータが存
在 thenセルの近傍セルリストを作成する（5〜7 行）．Algorithm1 中でル結合を行い，ClusterList を作成する（21〜28 行）．ボーダ

d の超立方体に分割し，CellList を作成

ルの結合判定を行う必要があるセルのペアリスト CellP airList

タとノイズの判定を行いクラスタリングの途中結果を算出する．

√

2: データセット全体を一辺の長さが ϵ/34:dti から最も近いコアデータが属するクラスタに dti を追加
else
dti を N oiseList に追加

35:

end if36:

end for37:

現 時 点 で の ク ラ ス タ リ ン グ 結 果 と し て ，ClusterList とN oiseList を保存

くセル結合，ボーダデータとノイズの判定とクラスタリング結

38: end for

果の保存を p 回繰り返す（18〜38 行）．ユーザが Algorithm1

39: return ClusterList，N oiseList

を停止した場合，保存された ClusterList と N oiseList が出力される．途中で停止されなかった場合，Algorithm1 は最終的な厳密解を出力する（39 行）．

5 評価実験
提案手法を評価するために，既存手法との比較実験を行った．

CDBC

AnyCDBC

40
80
120
Processing time [sec]AnyCDBC

0

50

100
150
200
Processing time [sec]250

NMI score

1
0.999
0.998

1
0.999
0.998

50

100
150
Processing time [sec]

120

200

160
200
Processing time [sec]

SSD5
SSD7
図 4 人工データを使用した実験結果
AnyCDBC

CDBC

AnyCDBC

1.02
1

AnyCDBC

CDBC
1

NMI score

1

0.98

0.94

0.97

0.92
0.9
30
50
Processing time [sec]70

PAMAP2

0.997
0.994
0.991
0.988

0.96
10

CDBC

1.003

0.99

0.96

240

SSD9

1.01

0.98

CDBC

1.001

0.997

160

SSD3

NMI score

CDBC

1.001

NMI score0

AnyCDBC

CDBC

1.001
1
0.999
0.998
0.997
0.996
0.995
0.994

NMI score

NMI score

NMI score

AnyCDBC
1.02
1
0.98
0.96
0.94
0.92
0.9
0.88

0.985
300

600
900
Processing time [sec]

1200

FARM
図 5 実データを使用した実験結果

表 1 データセットの詳細

300

500
700
Processing time [sec]900

HOUSEHOLD

献 [8] の著者より提供を受けたバイナリを使用した．

データセット

次元数

データ数

データセットは文献 [4] にて開発された Seed Spreader を使用

SSD3

3

10,000,000

して作成した人工データ（SSD3，SSD5，SSD7，SSD9）と文

SSD5

5

10,000,000

献 [4]，[7] にて使用された実データ（P AM AP 2 [19]，F ARM

SSD7

7

10,000,000

SSD9

9

10,000,000

PAMAP243,850,505

細を表 1 に示す．Seed Spreader は空間内に密集したデータ

FARM

5

3,627,086

集合をいくつかランダムに配置し，少量のノイズをランダム

HOUSEHOLD

72,049,280に配置することで，クラスタリングのベンチマークに適した[20]，HOU SEHOLD [21]）を使用した．各データセットの詳分布のデータセットを作成できる．パラメータは ϵ = 5, 000，
表 2 NMI が 1.00 となったときの処理時間（秒）
データセットM inP ts = 100，p = 10 を用いた．

AnyCDBC CDBC

5. 2 実 験 結 果

SSD3

123.41146.26

SSD5

80.83

214.69図 4 に人工データを使用した実験結果を示す．図 4 では，

SSD7

101.05180.28SSD9142.65214.11AnyCDBC は 10 回算出されるクラスタリング結果の NMI のPAMAP2

50.27

36.03

推移を示している．CDBC のクラスタリング結果の算出は 1 回

FARM

647.46651.55であり，厳密解を返す手法のため NMI は 1.00 となる．全てのHOUSEHOLD

724.41512.70

人工データにおいて，AnyCDBC は 9 回目までのクラスタリ
ング結果を CDBC よりも高速に算出できている．また，表 2

本章では，評価実験の結果を示す．

に AnyCDBC のクラスタリング結果の NMI が 1.00 となったときの処理時間を示す．表 2 より，全ての人工データにおいて

5. 1 実験内容とデータセット
評価実験では，提案手法（AnyCDBC と表記する），厳密解をAnyCDBC は CDBC よりも高速に厳密解を算出することができた．人工データを使用した実験では，AnyCDBC は一定の精返すセルベースの DBSCAN の中で最も高速であるセルの結合度のクラスタリング結果を高速に算出でき，CDBC よりも厳密判定に最小外接矩形とセルの再帰分割を用いる手法（CDBC と解を高速に算出できることを示した．

表記する）[7] と乱択アルゴリズムに基づく DBSCAN の Any-

図 5 に実データを使用した実験結果を示す．実データを使用

time アルゴリズム（AnyDBC と表記する）を比較する．評価

した場合でも，AnyCDBC は CDBC よりも一定の精度のクラ指標としては，処理時間とクラスタリングの精度として正規

スタリング結果を高速に算出できている．しかしながら，表 2 よ化相互情報量（NMI）[18] を比較する．実験に用いる計算機とり，PAMAP2 と HOUSEHOLD を使用した場合，AnyCDBC

しては，CPU が Intel Xeon E5-1270 V2 @3.5 GHz，メモリ

は CDBC よりも NMI が 1.00 となるのが遅い．実データは人が 32GB の計算機を使用した．AnyCDBC と CDBC はプログ

工データよりもノイズとなるデータ数が多く，毎回行われる

ラミング言語として C++を用いて実装し，コンパイラとして

ボーダデータとノイズの判定に多くの処理時間を要したためで

g++ 4.9.4，オプションとして-O3 を使用した．AnyDBC は文ある．セル結合だけでなくボーダデータとノイズの判定につい表 3 AnyDBC の処理時間（秒）
データセット

1

2

3

4

5

7

8

9

10

平均

SSD3

70965.1 70755.8

81557.6

SSD5

130.94133.2743.89

72982.5 81847.4 128168.0 63540.2 98549.1 62073.0 66427.2 79686.59
39.64

901.69106.7049.54

129.0555.36

175.22SSD7

918.30919.43443.48323.07509.27440.62500.65688.65510.08147.85540.14SSD91134.75 1141.91

1165.171155.84 1621.67

1116.96981.341205.87 1312.49 1679.12

1251.51

PAMAP2104.38104.11103.99101.22105.47110.02112.07111.63102.37109.17106.44

FARM

347.85347.5324433.50

398.96210.24193.73190.74242.75

181.56218.272676.51

HOUSEHOLD

69.16

69.00

67.13

67.21

69.65

66.74

67.24

73.75

69.01

67.13

68.60

ても，一部のデータのみに対して高速に処理を行い，随時クラスタリング結果を算出するような手法を考える必要がある．
各データセットを使用した AnyDBC の実験結果を表 3 に示す．表 3 には，AnyDBC の最終的なクラスタリング結果の算出を終えるまでの処理時間を示している．また，AnyDBC は実行毎に処理時間に大幅な差があったため，10 回実行した結果を示している．10 回の処理時間の平均を見ると，SSD5 とHOUSEHOLD を使用した場合，AnyDBC は AnyCDBC よりも高速である．しかしながら，AnyDBC は AnyCDBC よりも高速な場合はあるが，ランダムに選ばれるデータによって処理時間が安定していないのが分かる．特に，SSD3 を使用した場合，

AnyDBC は AnyCDBC よりも大幅に処理時間が遅くなった．
AnyCDBC も乱択アルゴリズムの考えを導入しているが，最終的なクラスタリング結果を算出するまでの処理数は実行毎に等しく，処理時間に大きな差は出ない．AnyCDBC は AnyDBC
よりも処理時間を安定させつつ，DBSCAN の Anytime アルゴ
リズムを実現できたといえる．

6 ま と め
本論文では，一定の精度を持つクラスタリングの途中結果を高速に出力でき，最終的には厳密解を出力可能なセルベースのDBSCAN の Anytime アルゴリズムを提案した．提案手法は乱択アルゴリズムに基づくセルの結合とクラスタリングの途中結果の算出を繰り返し行う．提案手法が算出するクラスタリン
グ結果は，処理が進むに連れて高精度となり，最終的には厳密解となる．人工データと実データを用いて行った評価実験の結果，提案手法は一定の精度のクラスタリング結果を高速に算出できることを示した．人工データを使用した場合，既存手法よりも厳密解を高速に算出できることを示した．実データを使用
した場合，ボーダデータとノイズの判定に多くの処理時間を要したために，提案手法は既存手法よりも厳密解を算出するまでの処理時間は遅くなった．今後の研究としては，ボーダデータとノイズの判定についても，一部のデータのみに対して処理を行い，随時クラスタリング結果を算出するような手法を考える必要がある．また，パラメータの ϵ と M inP ts を変化させて評価実験を行う必要がある．

謝

6

辞

本研究の一部は，JSPS 科研費 JP16J05403 と JP18K11320

176.53と，広島市立大学・特定研究費の支援により行われた．
文

献[1] Martin Ester, Hans-Peter Kriegel, Jorg Sander, and Xiaowei
Xu. A density-based algorithm for discovering clusters inlarge spatial databases with noise. In Proc. KDD 1996, pp.
226–231, 1996.
[2] Jörgand Sander, Martinand Ester, Hans-Peterand Kriegel,and Xiaowei Xu.
Density-based clustering in spatial
databases: The algorithm GDBSCAN and its applications.
Data Mining and Knowledge Discovery, Vol. 2, No. 2, pp.
169–194, 1998.
[3] Ade Gunawan. A faster algorithm for DBSCAN. Master’s
thesis, Technische University Eindhoven, 40 pages, 2013.
[4] Junhao Gan and Yufei Tao. DBSCAN revisited: Mis-claim,
un-fixability, and approximation. In Proc. SIGMOD 2015,
pp. 519–530, 2015.
[5] Junhao Gan and Yufei Tao. On the hardness and approximation of euclidean dbscan. ACM Trans. Database Syst.,
Vol. 42, No. 3, pp. 14:1–14:45, 2017.
[6] Tatsuhiro Sakai, Keiichi Tamura, and Hajime Kitakami.
Cell-based DBSCAN algorithm using minimum bounding
rectangle criteria. In Proc. BDMS 2017, pp. 133–144, 2017.
[7] 酒井達弘, 田村慶一, 北上始, 竹澤寿幸. 最小外接矩形とセルの再帰分割を用いたセルベースの DBSCAN の高速化. 電子情報通信学会論文誌, Vol. J101-D, No. 4, 2018.
[8] Son T. Mai, Ira Assent, and Martin Storgaard. AnyDBC:
An eﬃcient anytime density-based clustering algorithm forvery large complex datasets. In Proc. KDD 2016, pp. 1025–
1034, 2016.
[9] Shlomo Zilberstein. Using anytime algorithms in intelligent
systems. Vol. 17, pp. 73–83, 1996.
[10] Y. El-Sonbaty, M. A. Ismail, and M. Farouk. An eﬃcientdensity based clustering algorithm for large databases. In
Proc. ICTAI 2004, pp. 673–677, 2004.
[11] S. Mahran and K. Mahar. Using grid for accelerating
density-based clustering. In Proc. CIT 2008, pp. 35–40,
2008.
[12] Shuigeng Zhou, Aoying Zhou, Jing Cao, Jin Wen, Ye Fan,and Yunfa Hu. Combining sampling technique with DBSCAN algorithm for clustering large spatial databases. In
Proc. PAKDD 2000, pp. 169–172, 2000.
[13] M. Dash, H. Liu, and Xiaowei Xu. ’1+1>2’: merging distance and density based clustering. In Proc. DASFAA 2001,
pp. 32–39, 2001.
[14] Xin Wang and Howard J. Hamilton. DBRS: A density-based
spatial clustering method with random sampling. In Proc.
PAKDD 2003, pp. 563–575, 2003.
[15] B. Borah and D. K. Bhattacharyya. An improved samplingbased DBSCAN for large spatial databases. In Proc. ICISIP
2004, pp. 92–96, 2004.
[16] B. Liu. A fast density-based clustering algorithm for large
databases. In Proc. ICMLC 2006, pp. 996–1000, 2006.
[17] Cheng-Fa Tsai and Chien-Tsung Wu. GF-DBSCAN: A neweﬃcient and eﬀective data clustering technique for large

databases. In Proc. MUSP 2009, pp. 231–236, 2009.
[18] Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Is acorrection for chance necessary? In Proc. ICML 2009, pp.
1073–1080, 2009.
[19] A. Reiss and D. Stricker. Introducing a new benchmarked
dataset for activity monitoring. In Proc. ISWC 2012, pp.
108–109, 2012.
[20] M. Varma and A. Zisserman. Texture classification: arefilter banks necessary? In Proc. CVPR 2003, Vol. 2, pp.
II–691–8 vol.2, 2003.
[21] Bache K and Lichman M. UCI machine learning repository,
2013.