Dimensionality Reduction - spark.mllib
次元削減 は検討中の変数の数を減らす処理です。生およびノイズがある特徴から隠れた特徴を抽出、あるいは構造を保ったままデータを圧縮するために使うことができます。spark.mllib
はRowMatrix クラス上の次元削減のサポートを提供します。
特異値分解 (SVD)
特異値分解 (SVD) はマトリックスを3つのマトリックスに因数分解します: 以下のような $U$, $\Sigma$, および $V$
\[
A = U \Sigma V^T,
\]
ここで
- $U$ は正規直交マトリックスで、カラムは左特異ベクトルと呼ばれます。
- $\Sigma$ は降順の非負数対角を持つ対角マトリックスで、対角は特異値と呼ばれます。
- $V$ は正規直交マトリックで、カラムは右特異ベクトルと呼ばれます。
大きなマトリックスに対して、通常は因数分解を完了する必要はありませんが、一番上の特異値とそれに関連する特異ベクトルには必要があります。これはストレージを節約し、ノイズをなくし、そしてマトリックスの低い階級構造を回復します。
一番上の $k$ 特異値を維持すると、結果の低い階級マトリックスの次元は以下のようになるでしょう:
$U$
:$m \times k$
,$\Sigma$
:$k \times k$
,$V$
:$n \times k$
.
パフォーマンス
$n$ が $m$ より小さいとします。特異値と右特異ベクトルは固有ベクトルとグラム行列 $A^T A$ の固有ベクトルから導かれます。もしcomputeUパラメータを使ってユーザによってリクエストされた場合は、左特異ベクトル $U$ を格納している行列は、$U = A (V S^{-1})$ として行列の掛け算から計算されます。使用する実際のメソッドは計算のコストに基づいて自動的に決定されます。
- もし $n$ が小さい ($n < 100$) あるいは $k$ が $n$ ($k > n / 2$) に比べて大きい場合は、まずグラム行列を先に計算し、一番上の固有値とドライバ上のローカルの固有ベクトルを計算します。これには、各executor上とドライバ上で $O(n^2)$ ストレージの1回の通過と、ドライバ上で $O(n^2 k)$ 回の通過を必要とします。
- そうでなければ、分配の方法で $(A^T A) v$ を計算し、ドライバノード上で $(A^T A)$ の一番上の固有値と固有ベクトルを計算するためにそれをARPACKに送信します。これには、各executor上で $O(k)$ ストレージの通過と、ドライバ上で $O(n k)$ ストレージの通過を必要とします。
SVD の例
spark.mllib
はRowMatrix クラスで提供される、行指向のマトリックスへのSVD機能を提供します。
APIの詳細はSingularValueDecomposition
Scala ドキュメント を参照してください。
import org.apache.spark.mllib.linalg.Matrix
import org.apache.spark.mllib.linalg.distributed.RowMatrix
import org.apache.spark.mllib.linalg.SingularValueDecomposition
val mat: RowMatrix = ...
// Compute the top 20 singular values and corresponding singular vectors.
val svd: SingularValueDecomposition[RowMatrix, Matrix] = mat.computeSVD(20, computeU = true)
val U: RowMatrix = svd.U // The U factor is a RowMatrix.
val s: Vector = svd.s // The singular values are stored in a local dense vector.
val V: Matrix = svd.V // The V factor is a local dense matrix.
もしU
がIndexedRowMatrix
として定義される場合は、同じコードがIndexedRowMatrix
に適用されます。
APIの詳細はSingularValueDecomposition
Java ドキュメント を参照してください。
import java.util.LinkedList;
import org.apache.spark.api.java.*;
import org.apache.spark.mllib.linalg.distributed.RowMatrix;
import org.apache.spark.mllib.linalg.Matrix;
import org.apache.spark.mllib.linalg.SingularValueDecomposition;
import org.apache.spark.mllib.linalg.Vector;
import org.apache.spark.mllib.linalg.Vectors;
import org.apache.spark.rdd.RDD;
import org.apache.spark.SparkConf;
import org.apache.spark.SparkContext;
public class SVD {
public static void main(String[] args) {
SparkConf conf = new SparkConf().setAppName("SVD Example");
SparkContext sc = new SparkContext(conf);
double[][] array = ...
LinkedList<Vector> rowsList = new LinkedList<Vector>();
for (int i = 0; i < array.length; i++) {
Vector currentRow = Vectors.dense(array[i]);
rowsList.add(currentRow);
}
JavaRDD<Vector> rows = JavaSparkContext.fromSparkContext(sc).parallelize(rowsList);
// Create a RowMatrix from JavaRDD<Vector>.
RowMatrix mat = new RowMatrix(rows.rdd());
// Compute the top 4 singular values and corresponding singular vectors.
SingularValueDecomposition<RowMatrix, Matrix> svd = mat.computeSVD(4, true, 1.0E-9d);
RowMatrix U = svd.U();
Vector s = svd.s();
Matrix V = svd.V();
}
}
もしU
がIndexedRowMatrix
として定義される場合は、同じコードがIndexedRowMatrix
に適用されます。
上のアプリケーションを実行するためには、Sparkクイックガイドの自己内包型アプリケーション の章で提供される説明に従ってください。依存性としてビルドファイルにspark-mllibも含めるようにしてください。
主成分分析 (PCA)
主成分分析 (PCA) は、最初の軸がもっとも大きい確率の分散を持つような回転を見つけるための統計的な方法で、続く各軸が順番に大きな確率の分散を持ちます。回転行列のカラムは主成分と呼ばれます。PCA は次元削減で広く使われています。
spark.mllib
は行指向の形式でベクトルの中に格納されているひょろりとしたマトリックスのためのPCAをサポートします。
以下のコードは RowMatrix
上の主成分をどうやって計算するか、それらを使ってベクトルを低次元空間に投影する方法を実演します。
APIの詳細はRowMatrix
Scala ドキュメント を参照してください。
import org.apache.spark.mllib.linalg.Matrix
import org.apache.spark.mllib.linalg.distributed.RowMatrix
val mat: RowMatrix = ...
// Compute the top 10 principal components.
val pc: Matrix = mat.computePrincipalComponents(10) // Principal components are stored in a local dense matrix.
// Project the rows to the linear space spanned by the top 10 principal components.
val projected: RowMatrix = mat.multiply(pc)
以下のコードは ソースのベクトル上の主成分をどうやって計算するか、それらを使って関係するラベルを維持したままベクトルを低次元空間に投影する方法を実演します:
APIの詳細はPCA
Scala ドキュメント を参照してください。
import org.apache.spark.mllib.regression.LabeledPoint
import org.apache.spark.mllib.feature.PCA
val data: RDD[LabeledPoint] = ...
// Compute the top 10 principal components.
val pca = new PCA(10).fit(data.map(_.features))
// Project vectors to the linear space spanned by the top 10 principal components, keeping the label
val projected = data.map(p => p.copy(features = pca.transform(p.features)))
以下のコードは RowMatrix
上の主成分をどうやって計算するか、それらを使ってベクトルを低次元空間に投影する方法を実演します。カラムの数は小さくなければなりません。例えば1000未満。
APIの詳細はRowMatrix
Java ドキュメント を参照してください。
import java.util.LinkedList;
import org.apache.spark.api.java.*;
import org.apache.spark.mllib.linalg.distributed.RowMatrix;
import org.apache.spark.mllib.linalg.Matrix;
import org.apache.spark.mllib.linalg.Vector;
import org.apache.spark.mllib.linalg.Vectors;
import org.apache.spark.rdd.RDD;
import org.apache.spark.SparkConf;
import org.apache.spark.SparkContext;
public class PCA {
public static void main(String[] args) {
SparkConf conf = new SparkConf().setAppName("PCA Example");
SparkContext sc = new SparkContext(conf);
double[][] array = ...
LinkedList<Vector> rowsList = new LinkedList<Vector>();
for (int i = 0; i < array.length; i++) {
Vector currentRow = Vectors.dense(array[i]);
rowsList.add(currentRow);
}
JavaRDD<Vector> rows = JavaSparkContext.fromSparkContext(sc).parallelize(rowsList);
// Create a RowMatrix from JavaRDD<Vector>.
RowMatrix mat = new RowMatrix(rows.rdd());
// Compute the top 3 principal components.
Matrix pc = mat.computePrincipalComponents(3);
RowMatrix projected = mat.multiply(pc);
}
}
上のアプリケーションを実行するためには、Sparkクイックガイドの自己内包型アプリケーション の章で提供される説明に従ってください。依存性としてビルドファイルにspark-mllibも含めるようにしてください。