[連載] フリーソフトによるデータ解析・マイニング 第31回

Rとカーネル法・サポートベクターマシン

1.カーネル法とは

  図1に示すように、非線形データ構造を線形構造に変換することができれば、線形データ解析手法で非線形データを容易に扱うことができる。

変換による線形化のイメージ

図1 変換による線形化のイメージ

  データを変換することで、非線形構造を線形構造に変換することが可能である。例えば、図2(a) に示す2次元平面座標系 (x , y ) 上の4つの点 A1 (1,1)、A2 (1,-1)、A3 (-1,-1)、A4 (-1,1) を考えよう。仮に A1 と A3 がひとつのクラス、A2 とA4 がひとつのクラスだとすると、平面上でクラスの境界線を一本の直線で引くことができない。しかし、新しい変数 を導入し、2次元平面 (x , y ) 上の4つの点を3次元空間 (x , y , z ) に射影するとA1 (1,1,1)、A2 (1,-1,-1)、A3 (-1,-1,1)、A4 (-1,1,-1) になり、両クラスは平面で切り分けることが可能である。例えば,z = 0 の平面を境界面とすることができる。

図2 データ写像の例

(a)                        (b)

図2 データ写像の例

  図1では、関数 φ(x ) を用いて個体の特徴・属性ベクトルについて変換を施している。関数 φ(x ) は、通常高次元への写像関数で、x を入力空間、変換されたF を特徴空間と呼ぶ。
  従来のデータ解析方法では、高い次元のデータを低次元に縮約して分析を行う。その典型的な方法としては、主成分分析、因子分析、対応分析、多次元尺度法などがある。
  データを高い次元の特徴空間に射影すると非線形問題を線形問題に置き換えることが可能であるが、計算量が増える。カーネル (kernel) 法は、データを高次元に射影し、線形問題に置き換えると同時に計算量の問題を解決する技法である。
  カーネル法では射影された高次元のデータを直接計算するのではなく、任意の個体xz を変換した φ(x ) , φ(z ) の内〈φ(x ) , φ(z) 〉のような処理を借りて間接的に高次元のデータについて計算処理を行う。このようなデータの変換と内積のような演算を組み合わせた関数をカーネル関数と呼び、K (x , z ) =〈φ(x ), φ(z ) 〉のように表記する。カーネルに関する厳密な定義やカーネル関数の性質などについては[1]、 [3]、[4]が詳しい。
  カーネル法を取り入れた幾つかのデータ解析方法が提案されている。例えば、カーネル主成分分析、カーネル正準相関分析、カーネルクラスター分析、カーネルk 平均ほう、カーネル回帰分析、カーネル判別分析などがある。本稿では、カーネル主成分分析とカーネル法による分類器サポートベクターマシンについて紹介する。

2.カーネル主成分分析

  カーネル主成分分析 (KPCA; kernel principal component analysis) は、非線形主成分分析とも呼ばれている。カーネル主成分分析には幾つかのアルゴリズムが提案されているが、その大まかな流れは次のステップを取る。

  (1) カーネル関数 K (x , z ) =〈φ(x ) , φ(z) 〉を決める
  (2) データから写像行列 K m×nを求める
  (3) K m×n の固有値と固有ベクトル
  (4) 固有値と固有ベクトルを正規化する

2.1 パッケージと関数

  パッケージ kernlab には、カーネル主成分分析の関数 kpca がある。パッケージ kernlab は CRAN ミラーサイトからダウンロードできる。次に関数 kpca の書き式を示す。

kpca(x, kernel = "rbfdot", features=0, kpar= list(sigma = 0.1),...)

  引数 x はマトリックスとデータフレーム形式のデータである。引数 kernel では、用いるカーネル関数を指定する。デフォルトには "rbfdot" (ガウシアン)が指定されているが、これ以外に、カーネル関数 "polydot" (多項式)、"vanilladot" (線形)、"tanhdot" (タンジェント)、"laplacedot" (ラプラシアン)、"besseldot" (ベッセル)、"anovadot" (ANOVA RBF)、"splinedot" (スプライン) が用意されている。これらの関数は [2]に定義されている。
  引数 features では、求める主成分の数を指定する。デフォルトはゼロになっている。引数 kpar はカーネル関数に用いるパラメータを指定する。
  結果としては、固有値 eig()、主成分ベクトル kpc()、用いたデータの主成分得点 pcv()、回転・射影後の主成分得点 rotated() が返される。

2.2 カーネル主成分分析の例

  次にデータ iris を用いた主成分得点の散布図を作成するコマンドとその結果を図3 (a) に示す。

> library(kernlab)
> x<-as.matrix(iris[,1:4])
> iris.kpc1<-kpca(x,kernel="rbfdot", features=2,kpar=list(sigma=0.1))
> plot(pcv(iris.kpc1), col=as.integer(iris[,5]))

  カーネル主成分析法は、古典的主成分分析方法と異なり、用いるカーネル関数および kpar のパラメータによって返される結果が異なる。カーネル関数を kernel = "polydot"、kpar のパラメータを list(degree =1) にしたコマンドラインとその結果を図3 (b) に示す。

図3 irisのカーネル主成分得点散布図(a)     図3 irisのカーネル主成分得点散布図(b)

図3 iris のカーネル主成分得点散布図 (a)          図3 iris のカーネル主成分得点散布図 (b)

  このようにカーネル関数、kpar のパラメータは主成分の結果に大きく影響する。どのようなカーネル関数を用い、kpar のパラメータをどのような値にするべきであるかに関しては、用いるデータに依存するので、経験に頼るのが現状である。
  次に iris.kpc の結果を用いて新しいデータ new.data を当てはめる書き式を示す。

predict(kpc(iris.kpc),new.data)

3.サポートベクターマシンの基礎

  サポートベクターマシン (SVM: Support Vector Machine) は、分類と回帰問題を主としたデータ解析方法である。広く知られるようになったのは1990年代の後半からであり、Vapnik,V の貢献が高く評価されている。SVM は高次元の分類問題に得意であると言われている。SVM は、線形分離が可能な高次元の仮説空間において、線形的なアプローチで学習を行うシステムである。
  学習データ集合 (x 1 , y 1) 、( x2 , y2)、・・・、(xn , yn) があるとする。このxk = (xk1 , xk2 , ・・・ , xkp )t は個体の特徴ベクトルで、yk は目的変数であり、回帰問題では数値、分類問題ではクラスのラベルである。線形回帰と線形判別の問題では次に示す線形関数を用いる。式の中の w t = (w1 , w2 , … , wp ) は各変数の重みである。

  説明のために、2群 ( + , - ) 線形分類の SVM のイメージを図4に示す。SVM は図4に示すマージンを最大になる分類境界を求め、次のように判別を行う。y = 1 は "+" のグループ、y = -1 は "-" のグループ判別される。

SVMの識別境界のイメージ

図4 SVMの識別境界のイメージ

  図4における点線上の個体をサポートベクターと呼ぶ。マージン最大に影響を与えるのはサポートベクターのみである。平面 w txi +b = 1 と w txj +b = -1 の間の間隔をマージンと呼ぶ。マージンを最大にすることは ||w || を最小にすることである。その解を求める第1ステップは、次に示すラグランジュ乗数の関数を導入し、w , b を推測する。

関数

  上記 L (w , a , b ) を w , b で偏微分し、ゼロとすると

次の解が得られる。

  この結果を L (w , a , b ) に代入すると、 L (w , a , b ) は次となる。

  第2ステップは、上記の L (a ) を最大とする推測値 を求めることである。

  制約条件 , の条件の下で、max {L (α)} を最適化することにより の推測値および , , を求めることができる。この最適化問題は Karush-Kuhn-Tucker の条件の下での双対問題といわれている。

  初期の SVM は2群線形分類器として提案されたが、多群分類にも用いるようになっている。カーネル法によるSVM はカーネル関数 K (a i , x ) を用いて次に示す線形関数で表される。

4 その他

  パッケージ kernlab には、データの特徴を分析するアルゴリズム関数 kfa(Kernel Feature Analysis)、カーネルヘッビアン (Kernel Hebbian) アルゴリズムによる主成分分析関数 khc、カーネル準相関分析関数 kcca、適合ベクターマシン関数 rvm(Relevance Vector Machine) などがある。現段階の関数 rvm は回帰分析のみが機能している。
  カーネル法は機械学習、パターン分析の方法として、研究・応用が広がりつつある。カーネル法によるパターン分析に関しては[1]が詳しい。
  SVM は、狭義の分類と回帰問題だけではなく、自然言語処理などへも応用されている。カーネル法とSVMの基礎理論に関しては [3]、[4]が詳しい。また SVM に関しては [5]がある。
  群平均法(group average method)は、最近隣法と最遠隣法を折衷した方法で、2つのクラスターのそれぞれの中から1個ずつ個体を選んで個体間の距離を求め、それらの距離の平均値を2つのクラスター間の距離とする。
  SVM は、パッケージ klaR、e1071 にも実装されている。
  カーネル法は回帰、平滑化や密度の推定などにも多く用いる。パッケージ stats には平滑化に関する関数 kernel 、kernapply 、ksmooth 密度を推定する関数 density がある。
  カーネル法による関数 ksmooth を用いたカーネル回帰平滑化の例のコマンドとその結果を次に示す。

> attach(cars)
> plot(speed, dist)
> lines(ksmooth(speed, dist, "normal", bandwidth=1.3), col=2)
> lines(ksmooth(speed, dist, "normal", bandwidth=4), col=3,lty=2)
> detach("cars")

図7 関数ksmoothによるカーネル回帰平滑化

図7 関数 ksmooth によるカーネル回帰平滑化

  カーネル法による平滑化関数パッケージとしては KernSmooth、ks があり、パッケージ ade4 、assist 、fields 、lattice、splancs、sandwich などにもカーネル法に関連する関数がある。

参考文献:
[1] J.Shawe-Taylor and N. Cristianini (2004): Kernel Methods for Pattern Analysis, Cambridge.
[2] Karatzoglou, A., Smola, A., hornik, K., Zeileis,A.(2004): kernlab-An S4 Package for Kernel Methods in R, Journal of statistical Software, Vol.11, Is.9, p.1-20.
   http://www.jstatsoft.org/v11/i09/paper
[3] 麻生英樹, 津田宏治, 村田昇(2003):パターン認識と学習の統計学―新しい概念と手法,岩波書店
[4] 大北剛訳(2005):サポートベクターマシン入門,共立出版
[5] 前田英作(2001):痛快!サポートベクトルマシン - 古くて新しいパターン認識手法 - ,情報処理学会誌, Vol.42, No.7, p.676-683