CLARANSとは
CLARANSは、クラスタリングアルゴリズムの一つであり、サンプリングと探索の組み合わせ（Randomized Search）を用いて、K-medoids法における局所最適解の問題を緩和し、より高品質なクラスタリング結果を得ることを目指す手法のことです。
CLARANSの概要とK-medoids法における役割
CLARANS（Clustering Large Applications based upon RANdomized Search、ランダム化探索に基づく大規模応用クラスタリング）は、1994年に提案されたパーティショニング型クラスタリングアルゴリズムです。
このアルゴリズムは、K-means法と類似していますが、クラスタの中心をメドイド（Medoid）、すなわちクラスタ内の実際のデータ点で表現するK-medoids法（PAM: Partitioning Around Medoids）に基づいています。
K-medoids法は、K-means法が平均値（重心）をクラスタ中心とするために外れ値（ノイズ）に弱いという欠点を克服しますが、計算コストが高いという問題があります。特に、最適なメドイドの組み合わせを見つける探索プロセスは、総当たりで行うと計算時間が膨大になります。
CLARANSは、この探索プロセスを効率化するためにランダム化された局所探索（Randomized Local Search）を採用します。これにより、PAMよりも計算時間を大幅に短縮しつつ、PAMの欠点である探索が初期メドイドに依存し、局所最適解に陥りやすいという問題を軽減します。
主な目的は、大規模なデータセットに対して、外れ値に頑健なK-medoids法を適用し、大域的最適解に近いクラスタリング結果を効率的に導出することです。
CLARANSの動作原理とアルゴリズムの流れ
CLARANSは、グラフ探索の概念を用いて最適なメドイドの組み合わせを探します。各ノード（頂点）はK個のメドイドの特定のセットを表し、隣接ノードはメドイドのセットのうち一つだけを変更したセットを表します。
アルゴリズムは、以下の2つの主要なパラメータによって制御されます。
- NumLocal: 実行する局所探索（Local Search）の回数。この回数だけランダムな初期メドイドセットから探索を開始します。
- MaxNeigh: 各局所探索において、メドイド交換の評価を行う**隣接ノード（Neighbor）**の最大数。
CLARANSの実行ステップは以下の通りです。
1. 初期化
- データセットからK個のデータ点をランダムに選び、初期メドイドセット Mcurrent とします。
2. ランダム化された局所探索（Randomized Local Search）
- NumLocalの回数だけ、以下の手順を繰り返します。
- 評価: 現在のメドイドセット Mcurrent のコスト（通常は、非メドイド点と最も近いメドイドとの距離の合計）を計算します。
- 隣接ノードの調査: 現在のメドイドセット Mcurrent から、メドイドではない点とメドイドである点の一つの交換によって生成される隣接ノードをランダムに MaxNeigh 個だけ調査します。
- 交換の決定:
- 調査した隣接ノード Mneighbor の中で、Mcurrent よりもコストが低いものが一つでも見つかった場合、最も低いコストを持つ Mneighbor を新しい Mcurrent として置き換え、探索を継続します。
- コストの低い隣接ノードが見つからなかった場合（局所最適解に到達）、その探索は終了します。
- 大域的最適解の更新: 探索中に見つかったすべてのメドイドセットの中で、最もコストの低いものを暫定的な最良解として保持します。
3. 最終結果
- NumLocal 回の局所探索がすべて完了した後、保持されている最良解が最終的なクラスタリング結果として採用されます。
CLARANSの利点と課題
利点
- 外れ値への頑健性: メドイド（実際のデータ点）をクラスタの中心とするため、K-means法よりも外れ値の影響を受けにくい性質を引き継いでいます。
- 局所最適解の回避: 複数回（NumLocal回）のランダムな初期化と探索を行うため、単一の初期値に依存する従来のK-medoids法よりも、大域的最適解に近い結果を見つける可能性が高くなります。
- 効率性: 調査する隣接ノードの数を MaxNeigh に制限することで、PAMのようにすべての隣接ノードを調査する場合に比べて、計算時間を大幅に短縮できます。
課題
- パラメータ依存性: NumLocal と MaxNeigh の設定が結果と計算効率に大きな影響を与えます。特に MaxNeigh が小さすぎると、探索が早すぎて局所最適解に陥りやすくなります。
- 計算時間: 効率化されているとはいえ、K-means法と比較すると、距離計算の総量は依然として多く、特にKが大きい場合や次元が高いデータでは計算コストが高くなる傾向があります。
関連用語
お問い合わせ
システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。
APPSWINGBYの
ソリューション
APPSWINGBYのセキュリティサービスについて、詳しくは以下のメニューからお進みください。
システム開発
既存事業のDXによる新規開発、既存業務システムの引継ぎ・機能追加、表計算ソフトによる管理からの卒業等々、様々なWebシステムの開発を行っています。
iOS/Androidアプリ開発
既存事業のDXによるアプリの新規開発から既存アプリの改修・機能追加まで様々なアプリ開発における様々な課題・問題を解決しています。
リファクタリング
他のベンダーが開発したウェブサービスやアプリの不具合改修やソースコードの最適化、また、クラウド移行によってランニングコストが大幅にあがってしまったシステムのリアーキテクチャなどの行っています。
ご相談・お問い合わせはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、
お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、
より良い社会創りに貢献していきます。
T関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答致します。
ご相談・お問合せはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、より良い社会創りに貢献していきます。
IT関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答させて頂きます。
