スプレッドシートに象を収める方法

リンク一覧

要約と1 はじめに

2 準備と関連作業

2.1 サンプリング戦略について

2.2 その他のコアセット戦略

2.3 データベースアプリケーション用コアセット

2.4 四分木埋め込み

3 高速コアセット

4 感染拡大の影響を軽減する

4.1 大まかな上限値の計算

4.2 近似解から拡散の縮小へ

5 高速圧縮の実践

5.1 実証分析の目的と範囲

5.2 実験のセットアップ

5.3 サンプリング戦略の評価

5.4 ストリーミング設定と 5.5 まとめ

6 結論

7 謝辞

8 証明、疑似コード、拡張と 8.1 系 3.2 の証明

8.2 k平均法からk中央値法への簡約

8.3 ツリーにおける最適コストの推定

8.4 アルゴリズム1の拡張

参考文献

抽象的な

大規模なデータセットにおける k-means および k-median クラスタリングの理論的および実用的な実行時間限界について調査します。実質的にすべてのクラスタリング手法はデータセットの読み取りにかかる時間よりも遅いため、最も速いアプローチは、データをすばやく圧縮し、圧縮された表現に対してクラスタリングを実行することです。残念ながら、ポイントの数を圧縮するための普遍的な最善の選択肢はありません。ランダム サンプリングは線形以下の時間で実行され、コアセットは理論的な保証を提供しますが、前者は精度を強制せず、後者はポイントとクラスターの数が増えると遅くなりすぎます。実際、感度ベースのコアセット構築には、データセットのサイズに対して超線形の時間が必要であると推測されています。

この関係を調べるために、まず、感度サンプリングによってコアセットを実質的に線形時間（データの読み取りにかかる時間の log 係数以内）で取得するアルゴリズムが存在することを示します。これを大幅に改善するアプローチは、実用的なヒューリスティックに頼らざるを得ず、静的設定とストリーミング設定の両方で実際のデータセットと人工データセットの両方にわたるサンプリング戦略の範囲を考慮することになります。これにより、クラスターの妥当性を維持するためにコアセットが必要な条件と、より高速で粗いサンプリング戦略で十分な設定を示します。その結果、データ サイズに関係なく、効果的なクラスタリングのための包括的な理論的かつ実用的な青写真を提供します。コードはソースで公開されており、実験を再現するためのスクリプトが含まれています。

1 はじめに

現代のデータ アナリストには、クラスタリング アルゴリズムの選択肢が不足することはありませんが、関連するデータセットのサイズがますます大きくなっていることを考えると、多くのアルゴリズムは実用的であるには遅すぎることがよくあります。これは、クラスタリング アルゴリズムが圧縮によく使用されるビッグ データ パイプラインに特に当てはまります。目標は、非常に大きなデータセットを、下流のタスク用に、元の入力を適切に表すために、より小さく管理しやすいデータセットに置き換えることです。ロイドのアルゴリズム [49] はまさにこの理由で導入され、量子化誤差 (各入力ポイントから圧縮されたデータセット内のその代表までの二乗距離の合計) を最小限に抑えます。おそらく最も人気のあるクラスタリング アルゴリズムであるロイドのアルゴリズムは、収束するまで複数の反復を実行し、各反復には O(ndk) 時間が必要です。ここで、n はポイントの数、d は特徴の数、k はクラスターの数、つまり対象となる圧縮のサイズです。このようなアプリケーションでは、ポイントの数は簡単に数億になり、圧縮の品質はkとともに向上するため、標準的な目標ではkが数千になる可能性があります[41, 4]。このような設定では、O(ndk)アルゴリズムは非常に遅くなります。

このような例から、理論上および実用上の両方の実行時間の改善を実現するビッグ データ アルゴリズムが台頭してきました。ただし、理論上の健全性と実用上の有効性という観点は、しばしば相反します。一方では、理論上の保証により、アルゴリズムは不運な入力が何であれ正常に機能することが保証されます。他方では、より素早い実行が可能で、実用上も優れたパフォーマンスを発揮するより粗雑な方法がある場合、理論的に最適なアルゴリズムを実装するのは難しいかもしれません。

データセットはポイント数 n や特徴数 d が大きくなる可能性があるため、ビッグデータ手法では両方の影響を軽減する必要があります。特徴空間に関しては、ランダム投影が高速 (実質的に線形時間で実行) で、実装が実用的 [50] であり、埋め込みのサイズと品質が厳密に保証されるため、この疑問は事実上解決されています。ポイント数 n を減らすと見通しは明確ではなくなり、それぞれが異なる利点を提供する 2 つの別々のパラダイムがあります。一方では、均一サンプリングがあり、これは線形時間未満で実行されますが、データの重要なサブセットを見逃す可能性があるため、データに関する特定の強力な仮定の下でのみ精度を保証できます [45]。他方では、最も正確なサンプリング戦略は強力なコアセット保証を提供し、圧縮データに対する任意のソリューションのコストは、元のデータセットに対するそのソリューションのコストの ε 係数以内になります [25]。

私たちの貢献 私たちは、古典的な問題である k-means と k-median の目的関数の圧縮に関して、両方のパラダイム (均一サンプリングと強力なコアセット) を研究しています。均一サンプリングは最適な速度を提供しますが、最悪の場合の精度は保証されませんが、利用可能なすべてのコアセット構成では、正確な圧縮に必要な最小サンプル数の厳しい境界を生成する場合、実行時間は少なくとも Ω˜(nd + nk) です。

圧縮保証を実現するアルゴリズムはデータセット全体を読み込まなければならないことは簡単に示せます[1]。したがって、線形またはほぼ線形の時間でどのような保証が達成できるかは、明確な未解決の問題です。実際、現在利用可能なクラスタリング用の高速サンプリングアルゴリズム[6, 5]は、強力なコアセット保証を実現できません。最近、[31]は、O˜(nd + nk)の時間で実行される強力なコアセットの方法を提案し、これがk-medianおよびk-meansに最適であると推測しました。

この境界はkの値が小さい場合には事実上最適であるが、コンピュータビジョン[34]やアルゴリズムの公平性[18]などの多くのアプリケーションでは、クラスターの数が特徴の数よりも数桁大きくなる可能性がある。このような設定では、時間最適なコアセットの問題は未解決のままである。最適サイズのコアセットを決定する問題は最近解決されたため[25, 28, 44]、これはセンターベースクラスタリングのコアセット研究における主要な未解決問題であると言える。我々は、O˜(nd)時間でコアセットを構築する実装が容易なアルゴリズムが存在することを示すことで、この問題を解決した。これは、データセットの読み取りにかかる時間から対数係数だけ離れている。

しかし、これでは実際のクラスタリングにおけるサンプリング アルゴリズムの状況が完全に明らかになるわけではありません。私たちのアルゴリズムは最適な実行時間と最適な圧縮の両方を実現しますが、他のより粗雑な方法もすべての実用目的において同様に実行可能である可能性は確かにあります。私たちはこれを次の質問で正式に述べています。最適な k-means および k-median コアセットはいつ必要であり、コアセットの速度と精度の間の実際的なトレードオフは何ですか?

この質問に答えるために、私たちは提案した方法よりも高速なサンプリング アルゴリズム全体にわたって徹底的な比較を行いました。これにより、これらの高速な方法は多くの実際のデータセットで十分な精度を発揮しますが、それぞれに壊滅的な障害を引き起こすデータ分布が存在することが確認されました。実際、これらのケースは強力なコアセット メソッドでのみ回避できます。したがって、多くの実用的な設定では完全なコアセット保証は必要ありませんが、圧縮に自信を持ちたいのであれば、手抜きをすることはできません。これがストリーミング パラダイムにまで拡張され、下流のクラスタリング アプローチにも適用されることを確認しました。

要約すると、私たちの貢献は次のとおりです。

• k-meansとk-medianの強いコアセットをO˜(nd)時間で取得できることを示します。これにより、k-meansコアセットに必要な実行時間に関する推測[31]が解決され、理論的には対数因子まで最適です。

• データセット、タスク、ストリーミング/非ストリーミング パラダイムにわたる包括的な分析を通じて、線形時間サンプリング方法とサブ線形時間サンプリング方法の間で速度と精度の間に必要なトレードオフがあることを確認しました。これにより、クラスタリングの実践者は、各圧縮アルゴリズムをいつ使用すれば、最短時間で効果的なクラスタリング結果が得られるかについての青写真を得ることができます。