関連するパターン認識技術
本章では，本研究で利用する圧縮性によるパターン表現と，学習機能付き事例データ ベースの2種類のパターン認識技術について説明する．尚，本章の説明は本研究の理解に 必要な部分に留め，詳細は参考文献に譲る．
ここで，文字列xの圧縮により文字列x∗を得たとき，復元プログラムの長さをc，x∗の 長さを|x∗|とすると，K(x)の定義からK(x)≤ |x∗|+cが成立する．このcはxに依ら ない定数項O(1)であるため，|x∗| ≈K(x)が成立する．よって，K(x)の近似値として 圧縮後の文字列長が一般に利用される．xはバイナリ文字列{0,1}∗，|x|はxのビット長 であるが，本論文では必要な場合を除き，xを文字列，|x|を文字列長と記す．
3.1.2 コルモゴロフ複雑性に基づく文字列間の類似度
ここでは，コルモゴロフ複雑性に基づく文字列間の類似度として正規化圧縮距離 NCD(Normalized Compression Distance)[42, 43, 41]を説明する．このNCDは，計算 不可能なK(x)に基づく正規化情報距離NID(Normalized Information Distance)[42, 43, 41]において，K(x)を圧縮後の文字列長C(x)で近似した値である．そのため，NIDの 後でNCDを説明する．尚，ここで述べる関係式からは誤差項が除外されている．
(1) 正規化情報距離NID(Normalized Information Distance)
文字列x, y間の距離E(x, y)はx, yを相互に変換する最短プログラム長であると考え られる．よって，K(y|x)を入力xから出力yを得る最短プログラム長として，E(x, y) は下式で表現される．
E(x, y) =max{K(y|x), K(x|y)} (3.1)
E(x, y)は絶対量であり，相対的比較には不適である．例えば，1000文字のプログラムが
100文字異なる場合と，100文字のプログラムが100文字異なる場合を区別する必要が ある．よって，入力が必要ない最短プログラム長でE(x, y)を正規化し，正規化情報距離
NIDを得る．
N ID(x, y) = max{K(y|x), K(x|y)}
max{K(x), K(y)} , 0≤N ID(x, y)≤1 (3.2) NIDはx, yが同一のときに0，完全に異なるときに1となる文字列間の非類似度を表す．
(2) 正規化圧縮距離NCD(Normalized Compression Distance)
x, yと区切り文字を出力する最短プログラム長K(x, y)には，下式が成立する．
K(x, y) =K(x) +K(y|x), K(x, y) =K(xy) =K(yx) (3.3) 式(3.2)に対して式(3.3)を適用し，更にK(x)をC(x)で置き換えて，次のNCDを得る．
N CD(x, y) = C(xy)−min{C(x), C(y)}
max{C(x), C(y)} , 0≤N CD(x, y)≤1 (3.4) C(x), C(y)は文字列x，yの圧縮後の長さ，C(xy)は連結文字列xy の圧縮後の長さであ る．NCDの分子は，x, yが同一であるときに最小値0，完全に異なるときに分母と同一
となる．つまり，NCDは連結文字列と単独文字列の圧縮後の長さの比較に基づく類似度 である．本研究では，圧縮器C(x)として，Lampel-Ziv-Welch(LZW)アルゴリズム[45]
に基づくUNIX compressを使用する．
(3) 圧縮性を使用しない文字列間類似度とNCDの比較
圧縮性に基づく類似度は対象の事前知識やモデル化が不要であり，パラメータフリー で利用できるため，圧縮性を使用しない従来の類似度よりも取扱いが容易である．更に，
NCDは多様な圧縮器を変更せずにそのまま利用可能であるため，取扱いが非常に容易で ある．NCDは多様なデータの分類や識別に利用されている．例えば，西田らのツイート
（最長140文字の短文テキスト）分類[46]では，文章を単語に区切る必要がなく，多言語 やスラングが使用された文章の取扱いが容易であるため，類似度としてNCDが使用され ている．そして，NCDを応用した手法により多数の多言語ツイートが指定キーワードを 含む興味のあるものとそうでないものに自動で分類されている．また，Cerraらの地表面 の衛星画像の分析[47]でも，NCDにより衛星画像から人工物が自動認識されている．他 にも，NCDはミトコンドリアゲノムや自然言語等の分類に適用されている[42, 43, 41]． ここでは，トラヒックの比較を主眼として，圧縮性を利用しない文字列間類似度とNCD を比較する．圧縮性を利用しない文字列間類似度として，ダイバージェンスと編集距離 を取り上げる．一般に，トラヒックでは同一の部分パターンが繰り返される傾向が強い ため，繰り返し出現する特徴的な部分文字列の分布はトラヒックの重要な特徴である．
NCDはデータ圧縮よりこの特徴的な部分文字列を対象文字列から適応的に抽出し，その 分布に基づいて類似度を決定する．そのため，NCDはトラヒックの比較に適した類似度 である．一方で，ダイバージェンスは文字の出現確率分布の差異により，編集距離は文字 列Aを文字列Bに変換する文字操作（追加，削除，置換）の回数によりそれらの類似度を 測る．ダイバージェンスは文字を単位として類似度を測るため，トラヒックの重要な特徴 である繰り返し出現する部分文字列を殆ど反映しない．編集距離も文字列全体の順序の維 持を重視するため，特徴的な部分文字列の分布の類似性を判定する事には適していない．
3.1.3 圧縮性特徴空間
基準文字列との圧縮性に基づく類似度で構成される圧縮性特徴空間について説明する．
正規化圧縮距離は2つの文字列間の距離を定めるが，文字列をクラス分類する場合，文字 列がベクトル表現されていないため，ベクトルデータに対する分類手法を適用できない．
例えば，K-Meansやサポートベクトルマシンは適用できない．そのため，使用可能な分
類手法が類似度行列を対象とした手法に限定され，従来のベクトルに対する分類手法を使 用するためには，圧縮性に基づく特徴空間を構成する事が必要になる．そこで，基準とな る文字列を定めた上で，基準文字列との圧縮性に基づく類似度を用いて，圧縮性特徴空間 を構成する．圧縮性特徴空間では，任意のパターンxは，基準パターンbiとの圧縮性に
基づく類似度ρ(bi, x) により，圧縮性特徴ベクトルpx として表現される．本研究では，
この類似度ρとしてNCDを用いる（図3.1）．
px = (ρ(b0, x),· · · , ρ(bn−1, x))
図3.1 NCDによる3次元圧縮性特徴空間の例
圧縮性特徴空間にはNCD以外の類似度も使用できる．例えば，[39]では，辞書による LZWアルゴリズムの圧縮率の差異に着目し，基準文字列biの圧縮辞書を用いた文字列x の圧縮率を類似度ρとして利用している．圧縮性特徴空間は次の特徴を持つ．
1) 文字列として表現された大量データをパラメータフリーで人の介在なしに比較可能 2) 多種のデータを同一フレームワークの下で扱うことが可能
3) 計算コストが低く，実装も容易
これらの特徴により，従来はデータに合わせた個別の特徴空間を構成する事で実現されて きた画像認識，音声やゲノムの分類等が圧縮性特徴空間により同一フレームワークの下で 実現されている[39]．また，パラメータフィッティングが不要なため，圧縮性特徴空間は 多様に変化するデータへの適応性が必要な複雑なシステムに適している．