光学アルゴリズム

クラスタリング構造を識別するための点の順序付け( OPTICS ) は、空間データ内の密度ベースの^{[ 1 ]}クラスタを見つけるためのアルゴリズムです。これは、1999 年に Mihael Ankerst、Markus M. Breunig、 Hans-Peter Kriegel、およびJörg Sanderによって発表されました。^{[ 2 ]} その基本的な考え方はDBSCAN ^{[ 3 ]}と似ていますが、DBSCAN の主要な弱点の 1 つ、つまり密度が変化するデータ内の意味のあるクラスタを検出するという問題に対処しています。そのためには、データベースの点が (線形に) 順序付けられ、空間的に最も近い点が順序付けで隣接します。さらに、各点に対して、両方の点が同じクラスタに属するためにクラスタに対して受け入れられなければならない密度を表す特別な距離が格納されます。これはデンドログラムとして表されます。

DBSCANと同様に、OPTICSも2つのパラメータを必要とします。1つは考慮する最大距離（半径）を表すε 、もう1つはクラスタを形成するために必要な点の数を表すMinPtsです。点pは、そのε近傍内に少なくともMinPts個の点が見つかった場合にコア点となります。${\displaystyle N_{\varepsilon }(p)}$（点p自体も含む）。DBSCAN とは対照的に、 OPTICSはより密集したクラスターの一部である点も考慮するため、各点にはMinPts番目の最も近い点までの距離を表すコア距離が割り当てられます。

${\displaystyle {\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th smallest distance in }}N_{\varepsilon }(p)&{\text{otherwise}}\end{cases}}}$

点pから別の点oへの到達距離は、 oとpの間の距離、またはpのコア距離のうち、大きい方の値となる。

${\displaystyle {\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p,o))&{\text{otherwise}}\end{cases}}}$

pとoが最近傍である場合、これは${\displaystyle \varepsilon '<\varepsilon }$pとoが同じクラスターに属すると仮定する必要がある。

十分に密なクラスタ ( εに関して) が存在しない場合、コア距離と到達可能性距離の両方が未定義になります。十分に大きなεが与えられた場合、これは決して発生しませんが、その場合、すべてのε近傍クエリはデータベース全体を返し、結果として次のようになります。${\displaystyle O(n^{2})}$実行時間。したがって、εパラメータは、もはや興味のないクラスターの密度を切り捨て、アルゴリズムを高速化するために必要です。

厳密に言えば、パラメータεは必須ではありません。単純に最大値に設定すればよいのです。しかし、空間インデックスが利用可能な場合、複雑さに関して実用的な役割を果たします。OPTICSは、少なくとも最大値を指定するだけで済むという点において、このパラメータを削除することでDBSCANを抽象化しています。

OPTICSの基本的なアプローチはDBSCANに似ていますが、既知ではあるものの未処理のクラスタメンバーをセットに保持する代わりに、優先度キュー（インデックス付きヒープなどを使用）に保持します。

関数OPTICS(DB, ε, MinPts)は、 DB の各点 p に対して、 p.到達距離 = 未定義 DBの未処理の各ポイントpに対して、 N = getNeighbors(p, ε) pを処理済みとしてマークする pを順序付きリストに出力する core-distance(p, ε, MinPts) != UNDEFINED の場合、 シード = 空の優先度キュー update(N, p, Seeds, ε, MinPts) Seeds の各次の q に対して、 N' = getNeighbors(q, ε) qを処理済みとしてマークする qを順序付きリストに出力する core-distance(q, ε, MinPts) が UNDEFINED でない場合、 update(N', q, Seeds, ε, MinPts)を実行します。

update() では、優先度キュー Seeds が更新されます。${\displaystyle \varepsilon }$-近隣${\displaystyle p}$そして${\displaystyle q}$、 それぞれ：

関数update(N, p, Seeds, ε, MinPts)は coredist = コア距離(p, ε, MinPts) N の 各 o について、 o が処理されない場合は、 new-reach-dist = max(coredist, dist(p,o)) if o.reachability-distance == UNDEFINED then // o は Seeds に含まれていない o.reachability-distance = new-reach-dist Seeds.insert(o, new-reach-dist) else // o が Seeds 内にある場合、改善をチェックします。 もしnew-reach-dist < o.reachability-distanceならば o.reachability-distance = new-reach-dist 種子.移動(o、新しい到達距離)

したがって、OPTICSは特定の順序で点を出力し、それぞれの最小到達距離を注釈として付けます（元のアルゴリズムでは、中心距離も出力されますが、これは後続の処理には必要ありません）。

到達可能性プロット（特殊なデンドログラムの一種）を用いることで、クラスターの階層構造を容易に把握できます。これは2次元プロットであり、x軸はOPTICSによって処理された点の順序、y軸は到達可能性距離を表します。クラスターに属する点は、最も近い隣接点までの到達可能性距離が短いため、到達可能性プロットではクラスターは谷として現れます。谷が深いほど、クラスターの密度が高くなります。

上の図はこの概念を示しています。左上には合成データセットの例が表示されています。右上にはOPTICSによって生成されたスパニングツリーが、下にはOPTICSによって計算された到達可能性プロットが表示されています。このプロットの色はラベルであり、アルゴリズムによって計算されたものではありません。しかし、プロットの谷が上記のデータセットのクラスターに対応していることは一目瞭然です。この図の黄色の点はノイズとみなされ、到達可能性プロットには谷は見られません。階層的な結果において常に存在する「すべてのデータ」クラスターを除き、通常はクラスターに割り当てられません。

このプロットからクラスターを抽出するには、目視検査後に x 軸の範囲を選択し、y 軸の閾値を選択することで手動で行うことができます (結果は、同じ DBSCAN クラスタリングの結果と似ています)${\displaystyle \varepsilon }$およびminPtsパラメータ (ここでは 0.1 の値で良好な結果が得られる場合があります)、または傾斜、ニー検出、または局所最大値によって谷を検出しようとするさまざまなアルゴリズムによって。急な下降で始まり急な上昇で終わるプロットの範囲は谷と見なされ、高密度の連続した領域に対応します。谷の最後の点を内側または外側のクラスターに割り当てるには、さらに注意を払う必要があります。これは、先行点を考慮することによって実現できます。^{[ 4 ]}このようにして得られるクラスタリングは通常階層的であり、単一の DBSCAN 実行では実現できません。

DBSCANと同様に、OPTICSは各ポイントを一度処理し、${\displaystyle \varepsilon }$-この処理中の近隣クエリ。近隣クエリを許可する空間インデックスが与えられた場合${\displaystyle O(\log n)}$ランタイム、全体のランタイム${\displaystyle O(n\cdot \log n)}$得られる。しかし最悪の場合は${\displaystyle O(n^{2})}$DBSCANと同様です。オリジナルのOPTICS論文の著者らは、DBSCANと比較して実際の一定の減速係数が1.6であることを報告しています。${\displaystyle \varepsilon }$値が大きすぎると近傍クエリのコストが線形複雑度まで上昇する可能性があるため、アルゴリズムのコストに大きな影響を与える可能性がある。

特に、選択する${\displaystyle \varepsilon >\max _{x,y}d(x,y)}$（データセット内の最大距離よりも大きい）は可能ですが、すべての近傍クエリがデータセット全体を返すため、2次複雑度になります。空間インデックスが利用できない場合でも、ヒープの管理に余分なコストがかかります。したがって、${\displaystyle \varepsilon }$データセットに応じて適切に選択する必要がある。

OPTICS-OF ^{[ 5 ]}は、OPTICS に基づく外れ値検出アルゴリズムです。主な用途は、他の外れ値検出方法を使用する場合と比較して低コストで、既存の OPTICS の実行から外れ値を抽出することです。よりよく知られているバージョンであるLOF は、同じ概念に基づいています。

DeLi-Clu、^{[ 6 ]} Density-Link-Clusteringは、単連結クラスタリングとOPTICSのアイデアを組み合わせ、${\displaystyle \varepsilon }$パラメータを調整し、光学方式に比べて性能向上を実現しています。

HiSC ^{[ 7 ]}は、OPTICS に基づく階層的サブスペースクラスタリング(軸平行) 手法です。

HiCO ^{[ 8 ]}は、OPTICS に基づく階層的相関クラスタリングアルゴリズムです。

DiSH ^{[ 9 ]}は HiSC を改良したもので、より複雑な階層構造を見つけることができる。

FOPTICS ^{[ 10 ]}はランダム投影を使用したより高速な実装です。

HDBSCAN* ^{[ 11 ]}は DBSCAN の改良版に基づいており、クラスターから境界点を除外することで、Hartigan による密度レベルの基本的な定義に厳密に従っています。^{[ 12 ]}

OPTICS Cordillera ^{[ 13 ]}は、データセットがどの程度クラスタリングされているかを示す記述的なScagnostics尺度です。OPTICS を使用してデンドログラムを作成し、デンドログラムの情報を集約して、0 (クラスタリングなし) から 1 (最大のクラスタリング) の間のクラスタリング尺度を作成します。

OPTICS、OPTICS-OF、DeLi-Clu、HiSC、HiCO、DiSHのJava実装は、ELKIデータマイニングフレームワークで利用可能です（複数の距離関数に対するインデックス高速化機能と、ξ抽出法を用いた自動クラスタ抽出機能を備えています）。その他のJava実装としては、 Weka拡張機能があります（ただし、ξクラスタ抽出機能はサポートされていません）。

Rパッケージ「dbscan」には、ユークリッド距離のみのインデックス高速化のためにkd ツリーを使用するOPTICS の C++ 実装 (従来の dbscan のような方式とξクラスタ抽出の両方を含む)が含まれています。

OPTICSのPython実装は、PyClusteringライブラリとscikit-learnで利用可能です。HDBSCAN*はhdbscanライブラリで利用できます。