CUR行列分解

15.1 CUR行列分解について

CUR行列分解は、データ行列の数少ない実際の列または行(あるいはその両方)を明示的に表す低ランクの行列分解アルゴリズムです。

CUR行列分解は、特異値分解(SVD)と主成分分析(PCA)に取って替わるものとして作成されました。CUR行列分解は、高い統計的レバレッジまたは大きな影響を示す列および行をデータ行列から選択します。CUR行列分解アルゴリズムを実装することで、元のデータ行列から数少ない最も重要な属性または行(あるいはその両方)を識別できます。そのため、CUR行列分解は探索的データ解析の重要な機能です。CUR行列分解は様々な分野に適用可能であり、回帰、分類、クラスタリングを容易にします。

関連項目

SVD用のデータ準備

15.2 特異ベクトル

特異値分解(SVD)は、CUR行列分解の最初のステップです。

SVDは、列と行のレバレッジ・スコアを計算するための左右の特異ベクトルを返します。次の行列にSVDを実行します。

A ε R^mxn

行列が次のように因数分解されます。

A=UΣV^T

ここで、U = [u¹ u²...u^m]およびV = [v¹ v²...vⁿ]は直交行列です。

Σは、対角線上に非負実数σ1,...,σ_ρ を持つ対角行列m×nであり、ρ = min {m,n}、およびσ_ξはAのξ番目の特異値となります。

u^ξおよびv^ξをAのξ番目の左右の特異ベクトルとし、Aのj番目の列が上位k個の特異ベクトルと対応する特異値で近似されるようにします。

singular_vectors.epsの図の説明

ここで、v^ξ_jはξ番目の右特異ベクトルのj番目の座標です。

15.3 統計的レバレッジ・スコア

レバレッジ・スコアとは、行列のランク部分空間について最も代表的な列(または行)を判断する統計のことです。統計的レバレッジ・スコアは、列(または属性)と行の評価を示します。

すべての列の正規化された統計的レバレッジ・スコアは、次のように上位k個の右特異ベクトルから計算されます。

statistical_leverage_score.epsの図の説明

ここで、kはランク・パラメータと呼ばれ、j = 1,...,nとなります。π_j>=0とし、

statistical_leverage_score_1.epsの図の説明

とすると、これらのスコアはn列の確率分布を形成します。

同様に、すべての行の正規化された統計的レバレッジ・スコアは、上位k個の左特異ベクトルから次のように計算されます。

statistical_leverage_score_2.epsの説明が続きます

statistical_leverage_score_2.epsの図の説明

ここで、i = 1,...,mです。

15.4 列(属性)選択と行選択

OML4SQLのCUR行列分解は、属性評価や行重要度に向けて設計されています。レバレッジ(重要度)スコアによってランク付けされた高重要度の属性と行が返されます。列(属性)選択と行選択は、CUR行列分解の最終ステージです。

属性選択: レバレッジ・スコアの高い属性を選択し、それらの名前、スコア(評価)、ランク(評価順)をレポートします。

行選択: レバレッジ・スコアの高い行を選択し、それらの名前、スコア(評価)、ランク(評価順)をレポートします。

CUR行列分解では、最初にすべてのj ε {1,...,n}に対して、p_j= min {1,cπ_j}の確率でAのj番目の列(または属性)を選択します。
ユーザーが行選択を有効にした場合は、すべてのi ε {1,...,m}に対してpˊ_i = min {1,rπˊ_i}の確率でAのi番目の行を選択します。
選択したすべての属性(行評価が無効の場合)、または選択したすべての属性と行(行評価が有効の場合)の名前(またはID)とレバレッジ・スコア(評価)をレポートします。

cは近似(予測)列数、rは近似(予測)行数であり、どちらもユーザーが選択できます。

列選択と行選択を実行するには、個々の列および行を選択する確率を計算する必要があります。

次に示すように、各列の確率を計算します。

p_j = min {1,cπ_j}

次のように、各行の確率を計算します。

pˊ_i = min{1, cπˊ_i}

確率がしきい値よりも大きい場合は、列または行が1つ選択されます。

15.5 CUR行列分解アルゴリズムの構成

CUR行列分解アルゴリズム設定を構成してモデルを構築します。

アルゴリズム固有の設定でモデルを作成します。アルゴリズム名をALGO_CUR_DECOMPOSITIONとして、マイニング機能をATTRIBUTE_IMPORTANCEとして定義します。