統計数理（2008）
第 56 巻 第 2 号 185–198
c 2008 統計数理研究所


特集「データマイニングと統計数理」［研究ノート］

幾何データからの Geometric Algebra を用いた特徴抽出11

2

3Pham Minh Tuan ・橘 完太 ・Eckhard Hitzer ・Sven Buchholz ・1

吉川 大弘 ・古橋 武

1（受付 2008 年 1 月 7 日；改訂 2008 年 4 月 22 日）

要旨

従来のデータマイニングにおけるパターン認識では，空間的な特徴を含むデータに対しても幾何的な性質を考慮せずに特徴を抽出する．本研究では，複素数や四元数の一般形である
Geometric Algebra が持つ，空間的な物体や物体間の関係を簡潔に記述できるという長所を活かして，データの空間的な特徴を抽出する．本稿では，空間ベクトルの系列で与えられるデータからの特徴抽出について，Geometric Algebra を用いる系統的な手法を提案する．そして，データが幾何的な特徴を持つ手書き文字の分類問題について，提案手法により従来は偶然または経験的にしか発見・注目できなかった特徴を抽出でき，分類精度および頑健性が向上することを示す．
キーワード： Geometric Algebra，特徴抽出，混合正規分布モデル，混合エキスパー
ト，パターン認識，手書き数字分類．
1.

はじめに

様々な分野で膨大なデータが蓄積されている現在では，データを解析し有力な情報を発掘す
るデータマイニングがますます必要となっている．しかし，従来のデータマイニングにおけるほとんどのパターン認識手法では，空間的な特徴を含むデータ（以下，幾何データ）に対しても幾何的な性質を考慮せずに特徴抽出する．例えば，ある 3 次元物体に関して m 本の 3 次元空間ベクトルが計測された場合，多くの従来手法では，各ベクトルの 3 座標を順番に m 組ならべ，3m 個の実数，あるいは 3m 次元実ベクトル x ∈ R3m として扱う．ところが，これらの座
標値は座標系の定義に依存するため，たとえば，学習データの計測環境と異なる環境で計測されたデータに関して著しく推論が悪くなるといった問題が生じる．さらに，各変数に正規化などを行った場合には 3 次元空間での形状に関する情報は失われてしまう．これに対して従来手法でも座標系に依存しない特徴抽出が考えられるだろうが，そのような特徴抽出が発案され採用されるか否かは偶然やモデル構築者の経験に依存する．
本研究では，空間ベクトルや空間ベクトル間の関係を簡潔に記述できる Geometric Algebra
1
2
3名古屋大学大学院 工学研究科：〒 464–8601 名古屋市千種区不老町
福井大学 物理工学科：〒 910–8507 福井市文京 3–9–1

Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Olshausenstrasse 40, D-24098 Kiel,
Germany

統計数理

186

第 56 巻

第 2 号 2008

（GA）
（Hestenes, 1999; Doran and Lasenby, 2003; Dorst et al., 2007）を用いて，幾何データからの系統的な特徴抽出を行い，分類問題における精度および頑健性の向上を狙う． GA の一部ともみなすことができる複素数や四元数については，これらをそれぞれ用いた画像処理・時系列信
号処理や色付画像処理・多次元時系列信号処理などの，空間的な処理を要する応用での成功例が多く挙げられる．
（Sekita et al., 1992; Hirose, 2003; Matsui et al., 2004; Buchholz and Bihan,
2006; Nitta, 1997; Hildenbrand and Hitzer, 2008; Hitzer, 2007）また，GA 値入出力関数の学習
手法（Sommer, 2001）も提案され，その有効性が示されている．
提案手法で GA によって抽出した特徴は，入出力関数の学習にもデータ分布の学習にも，用いることができる．本研究では，幾何データから GA を用いて系統的に複数抽出する特徴デー
タの分布に対して，正規分布や混合正規分布モデルを学習させ，多クラス分類問題へ適用する．
提案手法で導出する複数の特徴抽出には，座標系に依存するものとしないものがあるため，複数 GMM の混合エキスパートの分類問題への適用も提案する．幾何データの多クラス分類問題の例として，UCI レポジトリ（Asuncion and Newman, 2007）の手書き文字（数字）データを用いる．学習済みのモデルを用いて実際の手書き文字（数字）
を分類する際，分類したいデータの座標系が学習データの座標系とぴたりと一致することは考えにくい．そのため本稿では，テスト
データにランダムな回転を加えた場合の分類性能により頑健性を評価する．
2.

手法

2.1 Geometric Algebraは代数構造の一種であり，クリフォード代数とも呼ばれる．実ベク
Geometric Algebra（GA）nトル空間 R には，正規直交基底 O = {e1 , . . . , en } を定めることができる．次数 n の GA は，本稿では Gn で表し，O 相互の結合的で双線形な積演算：幾何積（geometric product）

1(i = j)ei ej =
(2.1)
−ej ei (i = j)により構成される．なお，n 個のうち一部または全部の基底が e2i = −1 となる場合も，たかだ
か各項の符号が変わるだけであり，以下の議論を同様に展開できる．本稿では
（2.1）
の場合のみ
を考える．

いま，Rn において 2 本のベクトル {al = i ali ei , l = 1, 2} を考える．これらの幾何積は(2.2)

a1 a2 =n
i=1

a1i a2i +

n−1


n


(a1i a2j − a1j a2i ) eij

i=1 j=i+1となる．ここで eij = ei ej であり，以下同様に略記する．第 1 項はベクトル代数と同様の内積 a1 · a2 であり，内積は対称 a1 · a2 = a2 · a1 である．第 2 項は外積 a1 ∧ a2 と呼ばれる．外積は Grassmann の反対称積とも呼ばれ a1 ∧ a2 = −a2 ∧ a1 となる．第 2 項は，2 ブレードと呼ばれる．2 ブレードの線形和は，バイベクトルと呼ばれ，{1, . . . , n} から 2 つを選ぶ集合を
I2 = {i1 i2 | 1 ≤ i1 < i2 ≤ n} とすると， I∈I2 wI eI , wI ∈ R と表される．なお，a1 = κa2 , κ ∈ R であるとき第 2 項は 0 となる．
次に，a1 a2 = a1 · a2 + a1 ∧ a2 と第 3 のベクトル a3 との幾何積を考える．まず，a1 · a2 ∈ Rであるので，(a1 · a2 ) a3 はベクトルである．一方，(a1 ∧ a2 ) a3 = ( I∈I2 wI eI ) i a3i ei であって，ある I = i1 i2 に対して

幾何データからの Geometric Algebra を用いた特徴抽出

(2.3)

187

⎧
⎪
⎨ ei1 (i = i2 )eI ei = ei1 ei2 ei = −ei2 (i = i1 )⎪⎩ei1 i2 i (i1 = i = i2 )である．よって (a1 ∧ a2 ) a3 はベクトル（式（2.3）の上 2 行に該当する部分の総和）と 3 ブレードa1 ∧ a2 ∧ a3（式（2.3）の下 1 行に該当する部分の総和）とに分けられる．3 ブレードの線形和はトライベクトルと呼ばれ，{1, . . . , n} から 3 つを選ぶ集合 I3 = {i1 i2 i3 | 1 ≤ i1 < i2 < i3 ≤ n} を用いて， I∈I3 wI eI と表される．
以下同様に，互いに独立な a1 , . . . , ak , (k ≤ n) の幾何積 a1 · · · ak を考える際に，k ブレード
a1 ∧ . . . ∧ ak が出現する．任意の k ブレードの線形和である k ベクトルは，{1, . . . , n} から k

個を選ぶ集合 Ik = {i1 · · · ik | 1 ≤ i1 < · · · < ik ≤ n} を用いて， I∈Ik wI eI と表される．また，
I1 = {i1 | 1 ≤ i1 ≤ n} を用いて 1 ブレードであるベクトルを， I0 = {∅} を用いて 0 ブレードであるスカラーを，それぞれ表すことができる．スカラーについては e∅ = 1 と表す．Gn の k ブ

レード全体を k Rn ，k ベクトル全体を Gnk と表す．
ここで，n ≤ 3 では 0 ≤ k ≤ n についてすべての k ベクトルは同時に k ブレードでもある．つまり k 本のベクトルの外積で表すことができる．しかし，n ≥ 4 では，k ブレードでない k ベクト
ルが存在する．例えば e12 + e34 はバイベクトルであるが 2 本のベクトルの外積として表せないので，2 ブレードではない．k ブレードと k ベクトルの関係を改めて強調すると k Rn = {A ∈ Gnk |∃{b1 , . . . , bk }, A = b1 ∧ · · · ∧ bk } である．Gn の最も一般な元 A は，I = n
k=0 Ik = P ({1, . . . , n})を用いて，A = I∈I wI eI と表される．ここで P (·) はベキ集合を表す．より具体的に，G2 の一般の元は {1, e1 , e2 , e12 } の線形和であり，G3 の一般の元は {1, e1 , e2 , e3 , e12 , e13 , e23 , e123 } の線形和である．また A k = I∈Ik wI eI を用いて，A = nk=0 A k とも表される．· k は k ベクト
ル部分のみを取り出す演算とみなせる．スカラー部分を取り出す演算は · = · 0 と略記する．
k (1 ≤ k ≤ n) 個のベクトルの幾何積をまとめると，
a1 ∈ Gn1 = Rn =a1 a2 ∈ Gn0 ⊕a1 a2 a3 ∈ Gn1 ⊕
..
.
(2.4)

a1 a2 · · · ak ∈



1

Rn

2

Rn
3

Rn

Gn1 ⊕ Gn3 ⊕ · · · ⊕ Gnk−2 ⊕Gn0 ⊕ Gn2 ⊕ · · · ⊕ Gnk−2 ⊕kkRn (odd k)
Rn (even k)となる．ここで集合 A, B について A ⊕ B ≡ {a + b | a ∈ A, b ∈ B} である．
2.2 特徴抽出
n 次元での m 本のベクトルの集合 ξ = {p1 , p2 , . . . , pm }, pi = [xi,1 , . . . , xi,n ] から作ることができる特徴の多くは，(2.5)

F1m = {x1,1 , . . . , x1,n , . . . , xm,1 , . . . , xm,n }F2m = {x21,1 , x1,1 x1,2 , . . . , x1,1 xm,n−1 , x1,1 xm,n ,x21,2 , . . . , x1,2 xm,n , . . . , x2m,n−1 , xm,n−1 xm,n , x2m,n }

統計数理

188

第 56 巻

第 2 号 2008

F3m = {x31,1 , x21,1 x1,2 , . . . , x1,1 xm,n−1 xm,n , x1,1 x2m,n ,x31,2 , . . . , x1,2 x2m,n , . . . , x3m,n−1 , x2m,n−1 xm,n , xm,n−1 x2m,n , x3m,n }..
.

の線形和 Fk = { φ∈F m wφ φ | wφ ∈ R} によって表すことができる．しかし特徴の数は
k

(2.6)

|F1m | = nm = O(nm)mm(m + 1)= O(nm2 )|F1i | = n|F2m | =2
i=1|F3m | =m
|F2i | = O(nm3 )

i=1

..
.
|Fkm | =

m


i
|Fk−1
| = O(nmk )

i=1

..
.

と膨大になり，識別問題においてそれらのすべてが識別に有効な特徴になるとは限らないし，
これらのすべてを学習モデルに入力することは計算量の面から現実的でない．そのため，この膨大な特徴空間のうち適切な部分空間を設定する必要がある．従来この設定はアドホックに行われてきた．
従来，識別問題に関する特徴抽出について様々な手法が提案された．例えば，オンライン手
書き文字認識での特徴抽出は最も簡単な座標値特徴（Bahlmann and Burkhardt, 2004; Guyon etが多く使われる．これは上記の部分特徴空間 F1 に他ならない．F1 はal., 1991; Hu et al., 1999）
計測座標系の回転の影響を受ける．その他 Connell and Jain（2002）
はオンライン手書き文字の識別問題に関して，6 種類の特徴抽出を提案した． 6 種類のうち 4 種類は F1 に含まれるが，残りの回転に不変な 2 種類の特徴のそれぞれは 2 本のベクトル pi+1 − pi と pi − pi−1 間の角度 θに対する cos θ および sin θ と本質的に変わらず， cos θ も sin θ も F2 に含まれる（ペン先の軌道上で pi と pi+1 の間隔を変えた 2 種類を特徴として抽出する）．また，画像認識で用いられるモーメント特徴（Hu，1962）
および複素モーメント特徴（Abo-Zaid et al, 1988）
は，全てのベクト
ルに対する一般化慣性モーメントであり，次数 (p, q) のモーメントは k = p + q として Fk のうち {xpi,1 xqi,2 | i = 1, . . . , m} の線形和で表される．しかし，これらのモーメントが画像に対して提案された経緯から，モーメントではベクトル間（画像の場合はピクセル間）の関係は考慮されな
pqい．つまり Fk において i = j となる xi,1 xj,2 の係数は常に 0 となる．そこで，本研究では，回転に不変であり，ベクトル間の関係を考慮するような特徴も含めた部分空間を GA の幾何積により系統的に抽出する手法を提案する．
空間ベクトルの集合，または，系列（順序つき集合）ξ = {pl ∈ Rn , l = 1, . . . , m} からの系統的な特徴抽出を以下のように提案する．まず，ξ が空間ベクトルの（順序なし）集合である場合を考える．各 k ブレードと式（2.4）で k = 2 のときに出現するスカラーをそれぞれ特徴として抽出するという方針で，空間ベクトルの集合 ξ から，n = min{n, m} として，以下の n + 1 通りの特徴抽出を導出する．k = 1, . . . , n について，(2.7)

f0 (ξ) = {pl1 pl2 } ∈ R((m C2 )+m)
, I ∈ Ik } ∈ R(m Ck )|Ik |fk (ξ) = {pl1 · · · plk e−1I幾何データからの Geometric Algebra を用いた特徴抽出

189

ここで，e−1
I = i1 i2 · · · ik の場合 e−1
I は eI の逆数であり，I = eik · · · ei2 ei1 である．pl pl+1 · · · pl+k−1−1の eI の係数は eI との幾何積を施した後のスカラー部分として，取り出すことが出来る．
次に，ξ が空間ベクトルの系列である場合を考える．集合である場合と同様に n + 1 通りの特徴抽出を導出するが，各 f で抽出される特徴の次元数が異なる．
(2.8)

f0 (ξ) = {pl pl+1 } ∈ Rm−1
, I ∈ Ik } ∈ R(m−k+1)|Ik |fk (ξ) = {pl · · · pl+k−1 e−1I

以上で，順序なし集合と順序つき集合に関する特徴抽出を系統的に導入した． f0 は内積であり，ある注目ベクトル pl1 の次の注目ベクトル pl2 に平行な成分の長さに |pl2 | を掛けたものを示す．f1 は注目点の座標値を示す．f2 は 2 本のベクトルが各基底バイベクトル方向に作る面積を示す．f3 は 3 本のベクトルが各基底トライベクトル方向に作る体積を示す．f0 および fnの特徴は計測座標系の回転に依存しない．
また，前述の Connell and Jain（2002）
が提案した回転に不変な 2 種類の特徴は |pi+1 − pi ||pi −pi−1 | = γ として，cos(θ) = γ(pi+1 − pi ) · (pi − pi−1 ) = γ(pi+1 · pi − pi+1 · pi−1 − pi · pi + pi ·pi−1 ) ∈ f0 となり，sin(θ) = γ(pi+1 − pi ) ∧ (pi − pi−1 )e−1
12 = γ(pi+1 ∧ pi − pi+1 ∧ pi−1 + pi ∧−1
pi−1 )e12 ∈ f2 となる．本研究で提案した空間ベクトルの集合の特徴に含まれることが分かる．
UCI レポジトリの手書き文字と手書き数字データから筆跡曲線上で等間隔に 8 つのポイント
ξ = {p1 , . . . , p8 } を取り出す．そのポイントの系列から，G2 を使用した提案手法により系統的に
幾何的な特徴を抽出できる．ここで，pl = xl e1 + yl e2 であり， 8l=1 xl = 8l=1 yl = 0 と数字の中心に原点を合わせてあるものとする．図 1 に手書き数字 ‘7’ の例を示し，図 2 に手書き文字‘H’ と ‘h’ の例を示す．
特徴抽出 f0 は，連続する 2 点の内積を抽出する．
(2.9)

f0 (ξ) = [p1 p2 , . . . , p7 p8 ]= [x1 x2 + y1 y2 , . . . , x7 x8 + y7 y8 ] ∈ R7

図 1.

Examples of hand-written digit ‘7’.

図 2. Examples of hand-written character ‘H’.

190

統計数理

第 56 巻

第 2 号 2008

特徴抽出 f1 は，最も簡単で従来手法でもよく使われる特徴として，座標値を抽出する．
(2.10)

f1 (ξ) = p1 e−1, p1 e−1
, . . . , p8 e−1, p8 e−11212
= [p1 · e1 , p1 · e2 , . . . , p8 · e1 , p8 · e2 ]= [x1 , y1 , . . . , x8 , y8 ] ∈ R16

特徴抽出 f2 は，連続する 2 点の外積を抽出する．
(2.11)−1f2 (ξ) = p1 p2 e−1
12 , . . . , p7 p8 e12= [p1 ∧ p2 , . . . , p7 ∧ p8 ]= [x1 y2 − x2 y1 , . . . , x7 y8 − x8 y7 ] ∈ R7
2.3 多クラス分類問題に対する分布の学習
本研究では，前節で述べた提案手法によって抽出した特徴データについて，データ分布を学習し，多クラスの分類を行う． Gaussian mixture model（GMM）は，データ空間におけるデー
タ分布を M 個の正規分布で近似する．ここで，M = 1 の場合は，2 次判別に相当する．GMM
はパラメータ Θ = {βj , µj , Σj } によって特徴づけられる．ここで，βj ，µj および Σj はそれぞれ
j 番目のガウス分布の混合比，平均および共分散行列である．GMM の出力は，(2.12)p (ξ | Θ) =Mβj Nd (f (ξ) − µj ; Σj )j=1で表される．ここで，Nd (·; ·) は平均が原点である d 次元ガウス分布関数を表す．
不完全データ X = {xi = f (ξi ) | 1 ≤ i ≤ N } から，EM アルゴリズム（Dempster et al., 1977）により GMM のパラメータ Θ と潜在変数 Z = {zij ∈ {0, 1} | 1 ≤ j ≤ M } を求める．ここで，zij = 1
は各データ xi が GMM の j 番目のガウス分布に属することを意味し， M
j=1 P (zij ) = 1 を常に満たす．初期値として，zij を適当に選択する．そして，P (Z) と Θ が収束するまで，E ステップ（Expectation）と M ステップ
（Maximization）を繰り返し，潜在変数 Z とパラメータ Θ をそれぞれ更新する．E ステップは，ベイズの定理 P (Z | X, Θ) ∝ p (X | Z, Θ) により，潜在変数 Zの確率を更新する． M ステップは，尤度 l (Θ, X, Z) = p (X | Z, Θ) を最大化するように，ガウス
分布の変数 Θ を更新する．

しかし，GMM の大きな欠点は，自由パラメータ数が次元数の 2 乗 d2 と混合数 M に比例して増えるため，過学習が起こることである．自由パラメータを増やせば増やすほど，学習データの分布を正確に近似できるが，学習しないデータに対する分布から遠ざかってしまう．この欠点を緩和するために，Meinicke and Ritter（2001）が提案したように，各ガウス分布の共分散行列を固有値分解し，大きな固有値に対応する分散成分のみを用いることにする．不完全データ
X に対する共分散行列の最大固有値 λmax と超パラメータ α ∈ (0, 1) を使用して， λ− = αλmax
より大きな固有値に対応する成分のみを用いることにする．つまり，式（2.12）を展開し(2.13)p (x | Θ) =

M


βj

j=1

≈

M

j=1

d


N1 ((x − µj ) · vk ; λk )

k=1

βj

 qj

k=1


N1 ((x − µj ) · vk ; λk )d−qj× N1 (x − µj )− ; λ−

幾何データからの Geometric Algebra を用いた特徴抽出

図 3.

191

Flow of multi-class classiﬁcation. The top diagram shows the training of the
GMM for class C ∈ {‘0’, . . ., ‘9’}. The D1C denotes a subset of training samples
whose label is C. The f : ξ → x shows feature extraction. Either of {f1 , f2 , f0 } ischosen as f . The bottom diagram shows estimation by the learned GMMs. The
same f chosen for training is used here. The GMMC outputs p (ξ | C). The ﬁnal
estimation is C ∗ = arg maxC p (ξ | C) P (C), where P (C) is the prior distribution.
The set D3 consists of independent test data.

とする．ここで，λk は j 番目のガウス分布の k 番目に大きな固有値，vk はそれに対応する固有ベクトルである．また，k ≤ qj ⇔ λk > λ− であり，(x − µj )− は qj 番目までの固有ベクトルと直交する成分の長さである．
多クラス分類問題の例として，手書き数字分類の流れを図 3 に示す．図 3 の上部の図に，数字 C ∈ {‘0’, . . . , ‘9’} 用 GMM の学習の流れを示す．D1C は数字 C の学習データであり，特徴抽
出方法 f : ξ → x は {f0 , f1 , f2 } から選ばれる．図 3 の下部の図に，学習済み GMM による分類の流れを示す．分類時の f には学習時と同じ f を用いる．GMMC は確率密度 p (ξ | C) を出力する．最後に C ∗ = arg maxC p (ξ | C) P (C) により分類結果を出力する．ここで，P (C) は C の事
1
前確率であり，∀C, P (C) = 10とした．D2 はバリデーション用データセットである．各 GMMCの混合数 M は D2 に対する尤度により決定し，その後，決定した M を用いて，D2 に対する分類成功率により，α を決定する．D3 はテストデータセットである．
2.4 エキスパートの混合
入出力関数の学習ではなく，データ分布の学習を行うことの大きなメリットに，弱学習機の推論を混合することによってより信頼できる推論を得られる点が挙げられる．GA を用いて導出する各特徴抽出は，それぞれ長所と短所を持つ．それらの長所を活かし短所を補うために，
本研究では，次式の，推論の混合を用いて，分類を行う．
(2.14)p (ξ | C) =2p (fk (ξ) | C)

k=0

各 GMM のパラメータには前節で述べた学習で獲得されたものを用いる．図 4 に，GA による特徴抽出 f0 , f1 , f2 を通した推論の混合により数字を分類する流れを示す．
式（2.14）の事後確率の積のほかに，多数決も考えられるが，クラス数に比べエキスパートの数が少ないため，エキスパートによる識別結果が全て異なる場合が生じ，その場合は多数決できないという欠点がある．また，各特徴抽出が幾何的な情報を含んでおり，極端に識別率が低
いエキスパートはないと期待できるため，本研究では式 2.14 によりエキスパートの識別結果を
混合する．

統計数理

192

図 4.

3.

第 56 巻

第 2 号 2008

Mixture of GMMs. Three GMMs via diﬀerent feature extractions are mixed toyield output p (ξ | C).

数値実験と考察

3.1 手書き文字（数字）分類問題
UCI レポジトリの Pen-Based Recognition of Handwritten Digits データセット（以下，Pendigits
データセット）および UJI Pen Characters データセット（以下，Penchars データセット）を用いて多クラス分類の数値実験を行った．
Pendigits データセットは，44 人が書いた 10992 サンプルから構成される．44 人のうち 30
人が書いた 7494 サンプルが学習データ D1 とバリデーションデータ D2 に分けられ，残りの14 人が書いた 3498 サンプルがテストデータ D3 として用いられる．各サンプルを収集する際，500 × 500 ピクセルの解像度を持つタブレット上で 100[msec] 間隔のペン先座標が獲得される．
ペン先の軌道長を 7 等分する 8 ポイント {rl } が選ばれ，縦方向の最大値が 100，最小値が 0 となるようにスケーリングされる．本研究では，GA を用いる特徴抽出に先立ち，pl = rl − r̄ と，
数字の中心を原点とした．
Penchars データセットは，11 人が書いた 26 種類の文字（大文字と小文字を別々のクラスとしない）と 9 種類の数字の 1364 サンプルから構成される．クラスの合計が 35 クラスである．評
価するには， 11 leaving-one-writer-out tests という方法を用いるテストを行った．つまり，11
人が書いたデータのうち，10 人が書いたデータを学習データとし，残りの一人が書いたデータをテストデータとする 11 組の「学習・テスト」データセットが構成される．バリデーション
データは使用しないこととする．Pendigits データセットと同じように，ペン先の軌道長を 7 等分する 8 ポイント {rl } を選び，縦方向の最大値が 100，最小値が 0 となるようにスケーリング
する．GA を用いる特徴抽出に先立ち，pl = rl − r̄ と，数字の中心を原点とした．
3.2 各特徴抽出と混合エキスパートでの分類結果
Pendigits データセットでは，特徴抽出 f ∈ {f0 , f1 , f2 } の各場合について，α ∈ {0.1, 0.01, 0.001,
0.0001} の 4 通りで D1 を学習しそれぞれ D2 に対する分類成功率を評価した．その結果を表 1に示す．表中，分類成功率の最大値に下線を引く．特徴抽出 f0 , f1 について α = 0.01 が選択さ
れ，特徴抽出 f2 について α = 0.0001 が選択された．
表 1.

Correct classiﬁcation rate for D2 of Pendigits.

幾何データからの Geometric Algebra を用いた特徴抽出
表 2.

表 3.

193

Identiﬁed models and number of misclassiﬁcation via coordinates f1 of Pendigits.

Identiﬁed models and number of misclassiﬁcation via outer products f2 of Pendigits.

表2 に，特徴抽出 f1 を用いた場合の各数字に対する GMM の混合数 M と平均有効次元数j qjq̄ = Mおよび D3 に対する誤分類数を示す．表 2 の誤分類数の見かたの例として，‘0’ の行と‘8’ の列のセルは，‘0’ であるデータのうち 8 サンプルが ‘8’ として誤分類されたことを示す．誤分類の総数は 90（分類成功率 97.42％）であった．同様に，表 3 に，外積特徴を抽出する f2 を使用した場合の結果を示す．誤分類の総数は 176（分類成功率 94.97％）であった．表 4 に，内積特徴を抽出する f0 を使用した場合のモデル同定結果および分類結果を示す．誤分類の総数
は 316（分類成功率 90.97％）であった．
表 2，3，4 に示すように，特徴抽出によって，テストデータに対する分類結果が異なる．特徴抽出 f1 では，各ポイントの座標情報が保たれるため，全般に誤分類が少ない．しかし脆弱な面もある．例えば ‘0’ の学習データはほとんど全て数字の中心から見てタブレットの左上から書き始められていたため，テストデータで右上から書き始められる ‘0’ に対し，分類に失敗した．f2 と f0 では，各ポイントの座標情報が失われるが，数字の部分がどこに書かれたかに

統計数理

194
表 4.

第 56 巻

第 2 号 2008

Identiﬁed models and number of misclassiﬁcation via inner products f0 of Pendigits.

表 5.

Number of misclassiﬁcations by mixture of experts of Pendigits.

表 6. Correct classiﬁcation rate of Penchars.

関わらず部分的な形状を特徴として抽出する．そのため，f1 では分類に失敗した右上から書き始められた ‘0’ も左上から書き始められた ‘0’ と部分的な形状は同じであるので， ‘0’ データに対する誤分類はほとんどなかった．
そこで，特徴抽出 f1 , f2 , f0 のお互いの長所を活かすべく，混合エキスパートを利用した数字分類を行った．表 5 に混合エキスパートの分類結果を示す．誤分類の総数は 65（分類成功率
98.14％）
であり，f1 ，f2 あるいは f0 単独の分類結果より良くなった．
Penchars データセットでは，データ数が少ないためバリデーションを行わず， M = 1 とし，
α = 0.01 とする．

幾何データからの Geometric Algebra を用いた特徴抽出

195

表 6 に示すように特徴抽出によって，混合エキスパートの分類結果は f1 単独の分類結果より良くなり，分類成功率 75.51％を示す．
3.3 計測環境の揺らぎに対する頑健性
測定環境が揺らいだ場合を想定し，テストデータ D3 の各数字をランダムに回転させたデー
タセット D3 = {R (ξ, ϕ) , ξ ∈ D3 , ϕ ∼ U (ε)} を生成した．U (ε) は [−ε, ε] の一様分布を示し ϕ は確π π π率変数である．R (ξ, θ) は ξ に属する全ポイントを一律に角度 θ だけ回転させる．ε ∈ { 20
, 10 , 5 }
でそれぞれ 20 回 D3 を生成し分類テストを行った．
特徴抽出 f1 を用いた場合と混合エキスパートを用いた場合の，Pendigits データセットとPenchars データセットの分類成功率の平均と標準偏差を図 5 と図 6 にそれぞれ示す．特徴抽出
f1 のみを用いた場合の分類精度は ε が大きくなるにつれ著しく低下したが，混合エキスパートを利用した分類精度はそれほど低下しなかった．なお，f0 , f2 については，それらで抽出する

図 5.

Correct classiﬁcation rate with f1 and mixture of experts of Pendigits.

図 6.

Correct classiﬁcation rate with f1 and mixture of experts of Penchars.

統計数理

196

第 56 巻

第 2 号 2008

特徴は座標を回転しても変わらないため，どんな ε で作成した D3 に対しても分類結果は同じ
である．
4.

まとめ

本研究では，GA を用いる系統的な特徴抽出手法を提案した．抽出した特徴を使って，混合正規分布を用いた手書き数字分類問題に適用した．手書き数字のような 2 次元の対象に提案手法を適用した場合，座標値と外積および内積の 3 通りの特徴抽出が導出される．座標値特徴と外積特徴および内積特徴それぞれ単独で分類したとき，テストデータに対して，座標値特徴を用いた場合の分類成功率が一番高かった．しかし，異なる測定環境を想定して座標を回転変換したテストデータに対しては，座標値特徴による分類成功率は低下した．それに対し，GA で系統的に導出した特徴抽出の混合エキスパートを用いると，測定環境が学習時とテスト時で同じであっても分類成功率は高く，また，テスト時の測定環境の揺らぎを大きくしても分類精度はそれほど低下しなかった．したがって，従来よく用いられる座標値特徴と比べ，GA を用い導出する複数の特徴抽出を混合する戦略は，分類精度および頑健性において優越であることが確認できた．

参 考 文 献Abo-Zaid, A., Hinton, O. and Horne, E.（1988）. About moment normalization and complex momentdescriptors, Proceeding of the 4th International Conference on Pattern Recognition, 399–407.
Asuncion, A. and Newman, D. J.（2007）. UCI Machine Learning Repository, University of California,
School of Information and Computer Science, Irvine, California.
. The writer independent on-line handwriting recognition
Bahlmann, C. and Burkhardt, H.（2004）
system frog on hand and cluster generative statistical dynamic time warping, IEEE Transac-（3）, 299–310.
tions on Pattern Analysis and Machine Intelligence, 26
Buchholz, S. and Bihan, N. L.（2006）. Optimal separation of polarized signals by quaternionic neuralnetworks, 14th European Signal Processing Conference, EUSIPCO, Florence, Italy.
. Writer adaptation for online handwriting recognition, IEEE
Connell, S. D. and Jain, A. K.（2002）
Transactions on Pattern Analysis and Machine Intelligence, 24（3）, 329–346.
. Maximum likelihood from incomplete data via theDempster, A., Laird, N. and Rubin, D.（1977）
EM algorithm, Journal of the Royal Statistical Society Series B, 39（1）, 1–38.
. Geometric Algebra for Physicists, Cambridge University Press,
Doran, C. and Lasenby, A.（2003）
Cambridge.
Dorst, L., Fontijne, D. and Mann, S.（2007）. Geometric Algebra for Computer Science: An Objectoriented Approach to Geometry, Series in Computer Graphics, Morgan Kaufmann, San Francisco, California.
Guyon, I., Albrecht, P., LeCun, Y., Denker, J. and Hubbard, W.（1991）. Design of a neural network
character recognizer for a touch terminal, Pattern Recognition, 24, 105–119.
. New Foundations for Classical Mechanics, 2nd ed., Kluwer Academic, DorHestenes, D.（1999）
drecht.
. Analysis of point clouds using conformal geometric algeHildenbrand, D. and Hitser, E.（2008）
bra, 3rd International Conference on Computer Graphics Theory and Applications, Funchal,
Machira, Portugal.
Hirose, A.（2003）. Complex-valued Neural Networks: Theories and Applications, Series on Innovative
Intelligence, World Scientiﬁc, Singapore.

幾何データからの Geometric Algebra を用いた特徴抽出

197. Quaternion Fourier transform on quaternion ﬁelds and generalizations, Advances
Hitzer, E.（2007）
in Applied Cliﬀord Algebras, 17（3）, 497–517.
. Writer independent on-line handwriting recognition
Hu, J. Y., Lim, S. G. and Brown, M. K.（1999）
using an HMM approach, Pattern Recognition, 33, 133–147.
Hu, M. K.（1962）. Visual pattern recognition by moment invariants, IRE Transactions on Informa（2）, 179–187.
tion Theory, 8
Matsui, N., Isokawa, T., Kusamichi, H., Peper, F. and Nishimura, H.（2004）. Quaternion neuralnetwork with geometrical operators, Journal of Intelligent and Fuzzy Systems, 15（3–4）, 149–
164.
. Resolution-based complexity control for Gaussian mixture models,
Meinicke, P. and Ritter, H.（2001）（2）, 453–475.
Neural Computation, 13
Nitta, T.（1997）. An extension of the back-propagation algorithm to complex numbers, Neural Networks, 10（8）, 1391–1415.
. Complex autoregressive model for shape recognition, IEEE
Sekita, I., Kurita, T. and Otsu, N.（1992）
Transaction on Pattern Analysis and Machine Intelligence, 14（4）, 489–496.
Sommer, G.（2001）. Geometric Computing with Cliﬀord Algebras, Springer-Verlag, Heidelberg.

198

Proceedings of the Institute of Statistical Mathematics Vol. 56, No. 2, 185–198(2008)

Feature Extraction by Geometric Algebra from Geometric Data
Minh Tuan Pham1 , Kanta Tachibana1, Eckhard Hitzer2 , Sven Buchholz3 ,Tomohiro Yoshikawa1 and Takeshi Furuhashi1
1 School of Engineering, Nagoya University
2 School of Engineering, University of Fukui
3 Institute for Informatics, University of Kiel

Most conventional methods of feature extraction for pattern recognition do not pay
suﬃcient attention to inherent geometric properties of data, even where the data havecharacteristic spatial features. In this study, we introduce geometric algebra to systematically extract invariant geometric features from spatial data given in a vector space.
Geometric algebra is a multidimensional generalization of complex numbers and of quaternions, and can accurately describe oriented spatial objects and relations between them.
We further propose a combination of several geometric features using Gaussian mixture
models. We demonstrate our new method by classiﬁcation of hand-written digits andalphabetic characters.

Key words: Geometric algebra, feature extraction, Gaussian mixture model, pattern recognition,
mixture of experts.