DBSCAN
ある空間内にある、クラスタリングしたい点集合を考える。ε はある点からの半径を表すパラメータとする。DBSCAN クラスタリングの目的として、点は、コア点 (core points)、(密度)到達可能点、外れ値に分類される。以下のように行う。
点 p を含め、点 p から距離 ε 以内に少なくとも minPts 個の点があれば、点 p はコア点である。
点 q がコア点 p から距離 ε 以内にあれば、q は p から「直接到達可能」であるという。
各 pi+1 が pi から直接到達可能であり、p1 = p かつ pn = q であるパス p1, ..., pn があれば、q は p から「到達可能」である。ここでパス上のすべての点は、 q が例外である可能性があるが、コア点で無ければならない。
他のどの点からも到達可能でないすべての点は外れ値である。
今、p がコア点であれば、点p から到達可能なすべての点(コア点または非コア点)と一緒にクラスタを形成する。各クラスタは少なくともひとつのコア点を含む。