ニンジンをそのまま丸ごと食べるのは難しい。
でも、ジュースにすればだいぶ楽になる。
というのと同様に、巨大なデータをそのまま処理するのは難しいが、適切な形式の小さなデータに変換すれば楽になる。
スケールダウン戦略で大規模データを適切に小さくするアルゴリズム。
☆BIRCH：大量データの高速クラスタリング
クラスタリングは、データを似たもの同士であるクラスタに分けることにより、データをよりよく理解するための情報を得る学習・発見手法である。(*クラスタ ある特徴から分別する)
☆CFベクトルを用いたクラスタリング
CFベクトルは加法性を満たすため、ハードディスクから例を逐次読み取りながらCFベクトルとして表されたクラスタ情報を効率的に更新できるという特徴を持つ。
*CF(Clustering feature)ベクトル
☆アルゴリズムと性能
BIRCHが対象とするデータは、巨大すぎてメモリに収まらず、ディスクに保存されている。
ディスクアクセスはメモリアクセスに比べて遅くて制限がある。
BIRCHはディスク上のデータを1スキャンしてCFベクトルの集合に変換してメモリに収め、メモリ上のCFベクトル集合をクラスタリングする事によって問題に対処している。
BIRCHではデータスカッシング中、CFベクトルの数が増えすぎて、メモリに収まらなくなる場合が起こり得る上、多数のCFベクトルを効率的に更新する必要がある。
*CFベクトルから元の例を復元する事はできないので。1個のCFベクトルにまとめる例は多すぎない方が良い。
BIRCHのような距離に基づくクラスタリングは、低次元のデータ集合に用いられる。
☆データスカッシング
データ要約とランダムサンプリングの良い所を合わせて元データから小さい疑似データを生成し、疑似データから分類・回帰学習を行う事で、元データを用いた場合に匹敵する正確な結果を高速に得る事である。
この手法は、グループ化、モーメント化、疑似例化の3手順から構成される。
グループ化
名目属性は値ごとに分け、数値属性は四分位数やデータ球などを利用する事によって、集合をいくつかのグループに分割する。
*四分位数とは、データの度数を4等分するときの値のこと
モーメント化
各グループに対して、テイラー級数近似における望ましい字数を決め、モーメント計算をする。
疑似例化
各グループに対して、モーメントがほぼ同じとなるようにスカッシングされたデータを生成する。
☆尤度に基づくデータスカッシング
尤度に基づくデータスカッシング(LDS)
上記のデータスカッシングと概要は似ているが、グループ化と疑似例化の方法が異なる。
LDSには、選択フェーズ、プロファイルフェーズ、グループ化フェーズ、生成フェーズから構成されている。
選択フェーズ
θの推定値であるθ'を求める。
プロファイルフェーズ
データを1スキャンして各例について尤度プロファイルを得る。
グループ化フェーズ
データをさらに１スキャンして元データを尤度に基づく基準を用いてグループに分ける。
生成フェーズ
尤度に基づく基準を用いて各グループについて1個の疑似例を生成する。
☆サポートベクトルマシンのためのデータスカッシング
ノイズはないが属性がきわめて多い小規模データに適する分類学習手法であり、画像やテキストのなどの分類学習問題で予測制度がきわめて良い。
☆ブースティングのための反復データスカッシング
ブースティングは、ノイズがないデータに適する分類学習手法であり、分類モデルの可読性は悪いが正答率は高いという特徴がある。
基本的な考え方として、訓練データの例分布を更新しながら分類学習手法を複数回適用し、得られた複数個の分類モデルを組み合わせて最終的な分類モデルとする。
*AdaBoostは2クラス分類学習を対象とするブースティングの一手法であり、正答率が高い事が証明されている優れたアルゴリズム
*AdaBoost.M2は多クラス分類学習用に拡張した手法である。ブースティングは、分類学習手法を複数回適用するため、訓練データが大規模である場合は計算時間が長いという欠点がある。
これをふまえて、ブースティングで得られる例重みを活かして、フースティングのためのデータスカッシングが提案された。
手順としては、クラスごとにCF木を生成して疑似例を得ることと、疑似例にブースティングを適用してCF木の葉を生成するための閾値θを葉ごと更新することを、指定回数行う。
☆関連議論
☆更に大規模なデータは？
でも、ジュースにすればだいぶ楽になる。
というのと同様に、巨大なデータをそのまま処理するのは難しいが、適切な形式の小さなデータに変換すれば楽になる。
スケールダウン戦略で大規模データを適切に小さくするアルゴリズム。
☆BIRCH：大量データの高速クラスタリング
クラスタリングは、データを似たもの同士であるクラスタに分けることにより、データをよりよく理解するための情報を得る学習・発見手法である。(*クラスタ ある特徴から分別する)
☆CFベクトルを用いたクラスタリング
CFベクトルは加法性を満たすため、ハードディスクから例を逐次読み取りながらCFベクトルとして表されたクラスタ情報を効率的に更新できるという特徴を持つ。
*CF(Clustering feature)ベクトル
☆アルゴリズムと性能
BIRCHが対象とするデータは、巨大すぎてメモリに収まらず、ディスクに保存されている。
ディスクアクセスはメモリアクセスに比べて遅くて制限がある。
BIRCHはディスク上のデータを1スキャンしてCFベクトルの集合に変換してメモリに収め、メモリ上のCFベクトル集合をクラスタリングする事によって問題に対処している。
BIRCHではデータスカッシング中、CFベクトルの数が増えすぎて、メモリに収まらなくなる場合が起こり得る上、多数のCFベクトルを効率的に更新する必要がある。
*CFベクトルから元の例を復元する事はできないので。1個のCFベクトルにまとめる例は多すぎない方が良い。
BIRCHのような距離に基づくクラスタリングは、低次元のデータ集合に用いられる。
☆データスカッシング
データ要約とランダムサンプリングの良い所を合わせて元データから小さい疑似データを生成し、疑似データから分類・回帰学習を行う事で、元データを用いた場合に匹敵する正確な結果を高速に得る事である。
この手法は、グループ化、モーメント化、疑似例化の3手順から構成される。
グループ化
名目属性は値ごとに分け、数値属性は四分位数やデータ球などを利用する事によって、集合をいくつかのグループに分割する。
*四分位数とは、データの度数を4等分するときの値のこと
モーメント化
各グループに対して、テイラー級数近似における望ましい字数を決め、モーメント計算をする。
疑似例化
各グループに対して、モーメントがほぼ同じとなるようにスカッシングされたデータを生成する。
☆尤度に基づくデータスカッシング
尤度に基づくデータスカッシング(LDS)
上記のデータスカッシングと概要は似ているが、グループ化と疑似例化の方法が異なる。
LDSには、選択フェーズ、プロファイルフェーズ、グループ化フェーズ、生成フェーズから構成されている。
選択フェーズ
θの推定値であるθ'を求める。
プロファイルフェーズ
データを1スキャンして各例について尤度プロファイルを得る。
グループ化フェーズ
データをさらに１スキャンして元データを尤度に基づく基準を用いてグループに分ける。
生成フェーズ
尤度に基づく基準を用いて各グループについて1個の疑似例を生成する。
☆サポートベクトルマシンのためのデータスカッシング
ノイズはないが属性がきわめて多い小規模データに適する分類学習手法であり、画像やテキストのなどの分類学習問題で予測制度がきわめて良い。
☆ブースティングのための反復データスカッシング
ブースティングは、ノイズがないデータに適する分類学習手法であり、分類モデルの可読性は悪いが正答率は高いという特徴がある。
基本的な考え方として、訓練データの例分布を更新しながら分類学習手法を複数回適用し、得られた複数個の分類モデルを組み合わせて最終的な分類モデルとする。
*AdaBoostは2クラス分類学習を対象とするブースティングの一手法であり、正答率が高い事が証明されている優れたアルゴリズム
*AdaBoost.M2は多クラス分類学習用に拡張した手法である。ブースティングは、分類学習手法を複数回適用するため、訓練データが大規模である場合は計算時間が長いという欠点がある。
これをふまえて、ブースティングで得られる例重みを活かして、フースティングのためのデータスカッシングが提案された。
手順としては、クラスごとにCF木を生成して疑似例を得ることと、疑似例にブースティングを適用してCF木の葉を生成するための閾値θを葉ごと更新することを、指定回数行う。
☆関連議論
☆更に大規模なデータは？