Sansan Tech Blog

Sansanのものづくりを支えるメンバーの技術やデザイン、プロダクトマネジメントの情報を発信

【ML Tech RPT.】第25回 k-center クラスタリングを学ぶ

機械学習 R&D 連載

f:id:sansan_yoshimura:20210222095528p:plain DSOC 研究員の吉村です。あまり外出できない日々が続いているので、読書に勤しんでおります。直接業務に関係の無いようなものでも、蓄積しておくことでどこかで役に立つだろうという気持ちで幅広いジャンルの本に手を出しては、本の山が部屋を埋め尽くしています。

さて、今回は k-center クラスタリングについて見ていきます。普段は教師なし学習のことを調べることがあまりなかったので、個人的には新鮮でした。それでは本題に入っていきましょう！

本記事のキーワード

  • k-center
  • p-center
  • k-センター

k-center 問題とは

k-center クラスタリングの話をする前に k-center 問題 について説明します。予め与えられた空間またはグラフ上の点集合 V を考えます。点集合 Vに含まれるようなサイズ k の中心点集合 S \subseteq V を選択することが k-center 問題の目的です。このとき、「点集合 V の全ての要素に対して、最も近傍にある中心点との距離の最大値」が最小になるように k 個の中心点を選ぶことが条件となります。

f:id:sansan_yoshimura:20210630134004p:plain
図１：k-center 問題の例。黒点が与えられたデータ点。赤点は k=2 の時の中心点を表す。

理解のために具体例で説明します。図１は、サイズが 10 の点集合 V に対して、k=2 の時の k-center 問題の解答の例です。 (あくまでも図１は例示なので、必ずしも最適解になっていないことはご了承ください。) 図を見て分かるように、k-center 問題は言い換えると、 V の全ての点を S 内の中心点を中心とするできるだけ半径の小さい円で覆えるように中心点を選ぶ問題と言えます。

特に、距離空間の上の点や、各頂点が三角不等式を満たす完全グラフ上の頂点を扱う場合には、metric k-center 問題と言います。この性質は、最適化の際に用いられます。

metric k-center クラスタリング とは

metric k-center クラスタリングは、 metric k-center 問題に基づいてクラスタリングを実現する手法です。metric k-center 問題の厳密解を得るアルゴリズムは NP-hard である [*1] ことから、近似解を得ることを考えます。

それほど点の数が多くない metric k-center 問題に帰着できる場合には、greedy algorithm (貪欲法) を用いることが一般的です。そのアルゴリズムを下記に示します。

  1. 集合 V から任意の点を一つ取ってきて、 S に追加します。
  2. S から最も遠い V の点を取ってきて、 S に追加します。
  3. 2.を |S|=k になるまで繰り返します。

これは、 O(k|V|) の計算量で2-近似解が得られる2-近似アルゴリズムです [*1]。 \alpha-近似解は、簡単に言うと、得られる解により与えられる目的関数値が最適値の \alpha 倍よりも小さくなることを表します。k-center 問題の場合の目的関数値は、 V の点と最近傍の中心点との距離のうち、最大の距離です。そのため、2-近似解は、最適な場合の半径の二倍の半径よりは、小さい目的関数値を返すことができると言うことになります。

次に、対象となる集合 V の要素が非常に大きい場合を考えていきましょう。

extreme metric k-center クラスタリング

対象となる集合 V の要素の数が非常に大きい metric k-center クラスタリングの場合を extreme metric k-center クラスタリングということにします。この場合、計算量 O(kn) が実用上かなり大きくなってしまうことになります。そこで、大規模なデータ集合に対しても適用できるように、分散処理を用いる近似アルゴリズムの研究がいくつかあります。

分散処理による近似アルゴリズムを考える場合には、近似解の性能は多少劣化してしまう可能性を許容した上で、うまくスケールさせる方法を考えることになります。そうした、手法の一つに DISTRIBUTED-CENTER アルゴリズムがあります[*2]。

DISTRIBUTED-k-CENTER アルゴリズム

このアルゴリズムは O(\log \log \log n)-近似解を得ることができます [*2]。ただし、 n は集合 V 中の点の総数を表します。この近似解を得るためには、各マシンリソースあたり \tilde{O}(n^{\varepsilon}) の空間計算量を利用し、全体で \tilde{O}(n^{1+\varepsilon}) の時間計算量が必要となります。[*2] では、380万点くらいの大規模な集合に対してこのアルゴリズムを用いることで、高々 10 分前後の処理時間で近似解を得られることを実験的に示しました。ただし、このアルゴリズムは k-center 問題を解いていますが、最後に解として与えられる中心点集合 S のサイズが k とは限らない点は注意が必要です。このアルゴリズムでは、中心点集合 S のサイズが (1+o(1))k となることが分かっています。

さて、次にアルゴリズムを示します。DISTRIBUTED-k-CENTER アルゴリズムは、二つのフェーズから構成されます。

準備

各 Phase の内部で用いるアルゴリズム、SAMPLE-AND-SOLVE( V, p, r) を次に示します。ただし、 V は点集合、 p はサンプリング確率、 r は中心点からの半径 です。

SAMPLE-AND-SOLVE( V, p, r) in [*2]

  1. H を確率 p で V から i.i.d でサンプリングした点で構成。
  2. V の全ての点を、最近傍の h \in H に対応する bag 集合 \{ B_h: h \in H \} のいずれかに割り当てる。
  3. 各 h \in H ごとに分散処理で、下記の処理 4.~6.を行う。
  4. h に対応する中心点集合 S_h = \{ h \} を考える。
  5. B_h に含まれる点の内、 S_h 内の点との距離が 2r 以上離れている点があれば、 S_h 内の点から最も距離が離れている点を S_h に追加。
  6. B_h に含まれる点全てが、 S_h 内の点との距離が 2r 未満になるまで 5.を繰り返す。
  7. 最後に \bigcup_h S_h を返す。

Phase1

Phase1 では、UNIFORM-k-CENTER( V, r) というアルゴリズムで、仮の中心点集合を得ることが目的です。UNIFORM-k-CENTER( V, r) を下記に示します。ただし、 V は点集合、 r は中心点からの半径 です。

UNIFORM-k-CENTER( V, r) in [*2]

  1. S_1 に SAMPLE-AND-SOLVE( V, \frac{1}{n^{\varepsilon}}, r) の結果を代入。
  2. s_0 = n^{1-\varepsilon} とする。
  3. t=1 とする。
  4. s_t = \sqrt{s_{t-1}} とする。
  5. S_{t+1} に SAMPLE-AND-SOLVE( S_t, \frac{1}{s_t}, r) の結果を代入。
  6. t が \lfloor 3 \log \log n \rfloor (=\tau) になるまで 4.と5.を繰り返す。
  7. S_{\tau} を返す。

Phase2

Phase2 では、Phase1 の結果 S_1 = UNIFORM-k-CENTER( V, \frac{r}{\log \log n}) が得られているとして、次のアルゴリズムを実行します。

Phase2 of DISTRIBUTED-k-CENTER in [*2]

  1. s_1 = \log n \log \log n とする。
  2. t = 1 とする。
  3. S_{t+1} に SAMPLE-AND-SOLVE( S_t, \frac{1}{s_t}, r) の結果を代入。
  4. s_{t+1} = s_t^{2/3} とする。
  5. t が \lfloor c_t \log \log \log n \rfloor (=\tau) になるまで 3.と4.を繰り返す。
  6. S_{\tau} を返す。

この S_{\tau} が最終的な k-center 問題の中心点集合になります。ただし、 c_t は十分大きい定数です。

まとめ

今回は k-center 問題について取り上げました。まず、問題設定について紹介しました。次にある程度小さめの場合には貪欲法で2-近似解が得られること等を説明し、最後に点集合 V のサイズが非常に大きい場合に分散処理で現実的な時間で解を得る方法を紹介しました。今回取り上げませんでしたが、k-center 問題については streaming setting についての研究もありますので、ご興味がある方は [*3] 等を見てみると良いかと思います。

次回は、また別のトピックを紹介します。もし今回の記事に興味を持ってくださった方は読者になるボタンを押してくださると嬉しいです。


buildersbox.corp-sansan.com

*1:T. F. Gonzalez, "Clustering to Minimize the Maximum Intercluster Distance," in TCS, 1985.

*2:M. H. Bateni, H. Esfandiari, M. Fischer, and V. Mirrokni, "Extreme k-Center Clustering," in AAAI, 2021.

*3:M. Charikar, C. Chekuri, T. Feder, and R. Motwani, "Incremental Clustering and Dynamic Information Retrieval," in SIAM, 2004.

© Sansan, Inc.