CUREアルゴリズム

CURE（Clustering Using REpresentatives）は、大規模データベース向けの効率的なデータクラスタリングアルゴリズムです。K平均法クラスタリングと比較して、外れ値に対する耐性が高く、非球形形状やサイズにばらつきのあるクラスタを識別することができます。

広く用いられているK平均クラスタリングアルゴリズムは、二乗誤差の合計を最小化する基準を採用している。

${\displaystyle E=\sum _{i=1}^{k}\sum _{p\in C_{i}}(p-m_{i})^{2},}$

異なるクラスターのサイズや形状に大きな違いがある場合、二乗誤差法は大きなクラスターを分割して二乗誤差を最小化する可能性がありますが、これは常に正しいとは限りません。また、階層的クラスタリングアルゴリズムでは、クラスター間の距離尺度がどれも（${\displaystyle d_{min},d_{mean}}$異なるクラスタ形状で動作する傾向があります。また、nが大きい場合、実行時間が長くなります。

BIRCHアルゴリズムの問​​題点は、ステップ3以降にクラスターが生成されると、クラスターの重心を使用して各データポイントを最も近い重心を持つクラスターに割り当てる点です。クラスターのサイズや形状が均一でない場合、重心のみを使用してデータを再分配すると問題が発生します。

クラスターのサイズや形状が不均一になる問題を回避するため、CUREは重心ベースと全点ベースの中間的な階層型クラスタリングアルゴリズムを採用しています。CUREでは、クラスター内の十分に分散した点を定数c個選択し、クラスターの重心に向かってαの割合で縮小します。縮小後の分散点は、クラスターの代表点として使用されます。CUREの階層型クラスタリングアルゴリズムの各ステップでは、代表点のペアが最も近いクラスターがマージされます。これにより、CUREはクラスターを正しく識別し、外れ値の影響を受けにくくなります。

実行時間は${\displaystyle O(n^{2}\log n)}$そのため、かなり高価になり、空間の複雑さは${\displaystyle O(n)}$。

実行時間の複雑さが高いため、このアルゴリズムを大規模データベースに直接適用することはできません。今回の改良により、この要件に対応できるようになりました。

• ランダムサンプリング： ランダムサンプリングは大規模なデータセットに対応できます。一般的に、ランダムサンプルはメインメモリに収まります。ランダムサンプリングでは、精度と効率のトレードオフが生じます。
• パーティショニング：基本的な考え方は、サンプル空間をp個のパーティションに分割することです。各パーティションにはn/p個の要素が含まれます。最初のパスでは、各パーティションを部分的にクラスタリングし、最終的なクラスタ数が定数 q ≥ 1 に対してn/pqに減少するまで処理します。n /q個のパーティションに対する 2 番目のクラスタリング パスでは、パーティションを部分的にクラスタリングします。マージ手順では、マージされたクラスタの代表点を計算する前に、以前のクラスタの代表点のみが必要となるため、2 番目のパスでは代表点のみが格納されます。入力をパーティショニングすることで、実行時間を短縮できます。
• ディスク上のデータへのラベル付け： k個のクラスターに対して代表点のみが与えられた場合、残りのデータ点もクラスターに割り当てられます。このために、k個のクラスターそれぞれについてランダムに選択された代表点の一部が選択され、データ点は、それに最も近い代表点を含むクラスターに割り当てられます。

治癒（ポイント数、k）

入力: 点の集合 S

出力：k個のクラスター

• 各クラスタ u (各入力点) について、u.mean と u.rep には、クラスタ内の点の平均値と、クラスタを代表するc個の点のセット(各クラスタにはデータ点が 1 つしかないため、初期値はc = 1) が格納されます。また、u.closest には、u に最も近いクラスタが格納されます。
• すべての入力ポイントはkd木Tに挿入されます
• 各入力点を個別のクラスタとして扱い、各 u に対して u.closest を計算し、各クラスタをヒープ Q に挿入します。（クラスタは u と u.closest 間の距離の昇順に並べられます。）
• サイズ（Q）＞k
• Q の最上位要素 (u とします) を削除し、最も近いクラスター u.closest (v とします) とマージし、マージされたクラスター w の新しい代表点を計算します。
• TとQからuとvを取り除く。
• Q内のすべてのクラスターxについて、x.closestを更新し、xを再配置する。
• Qにwを挿入する
• 繰り返す

• pyclusteringオープンソースライブラリには、CUREアルゴリズムのPythonおよびC++による実装が含まれています。

• k平均クラスタリング
• BFRアルゴリズム

• Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). "CURE: 大規模データベースのための効率的なクラスタリングアルゴリズム" (PDF) .情報システム. 26 (1): 35– 58. doi : 10.1016/S0306-4379(01)00008-4 .
• Kogan, Jacob; Nicholas, Charles K.; Teboulle, M. (2006).多次元データのグループ化：クラスタリングの最近の進歩. Springer. ISBN 978-3-540-28348-5。
• テオドリディス、セルギオス；クトゥルンバス、コンスタンティノス（2006）。パターン認識。アカデミックプレス。pp. 572–574。ISBN  978-0-12-369531-4。