学習装置、クラス識別装置、学習方法、およびプログラム
【課題】時間とともに複雑な変化をともなうデータストリームの特徴を入力ベクトルの属性で表現することは困難である。
【解決手段】
履歴数入力部２６は過去履歴の参照範囲を履歴数として入力する。教師ストリーム構造データ作成部２８は属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる。教師ストリームカーネル作成部３０は教師ストリーム構造データに基づいて教師ストリームカーネルを作成する。機械学習部３２は教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する。
【解決手段】
履歴数入力部２６は過去履歴の参照範囲を履歴数として入力する。教師ストリーム構造データ作成部２８は属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる。教師ストリームカーネル作成部３０は教師ストリーム構造データに基づいて教師ストリームカーネルを作成する。機械学習部３２は教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は学習装置、クラス識別装置、学習方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、金融や流通分野の取引記録、ネットワーク監視システムの通信記録等のデータストリームが新しいタイプの大規模データとして注目を集めている。このようなデータストリームの識別は、一般的に教師付き学習が用いられる。従来の教師付き学習は、オンラインで到着するデータを特徴ベクトルで表し、それを事前に作成した識別器に入力することで、あらかじめ定義されたカテゴリへ識別することが行われている。
【０００３】
大規模に蓄積されたデータストリームを解析し、その結果を有効に活用する研究は、データマインイング１）、情報検索、統計的学習分野２）等において長年活発に行われてきた。カーネル法３），４）は、データの非線形構造をとらえる強力な手法として注目されており、分類５）や識別６）等に適用され、高い精度を得ている。特に識別において、線形識別器であるＳＶＭにカーネルトリックを適用し、非線形識別関数を構成することで非線形識別を可能にした非線形ＳＶＭは、最も識別性能に優れたモデルのひとつである（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−１５３５８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、データストリームを対象にした場合の識別精度は、静的データを対象にした場合と比べると識別精度が劣るという欠点がある。時間とともに複雑な変化をともなうデータストリームの特徴を入力ベクトルの属性で表現することは困難であり、無理に特徴を出そうと入力ベクトルの属性数を増やせば、次元の呪いによって識別器の汎化性能が失われるという欠点もある。
【０００６】
本発明はこうした状況に鑑みてなされたものであり、その目的は、汎化性を持って精度良くデータを識別することができる情報処理装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明のある態様は学習装置に関する。この装置は、過去履歴の参照範囲を履歴数として入力する履歴数入力部と、属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる教師ストリーム構造データ作成部と、教師ストリーム構造データに基づいて教師ストリームカーネルを作成する教師ストリームカーネル作成部と、教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する機械学習部とを含む。
【０００８】
本発明の別の態様はクラス識別装置に関する。この装置は、オンラインで受け取ったデータと当該データの過去履歴とから識別用ストリーム構造データを構築するストリーム構造データ構築部と、前記識別用ストリーム構造データと、教師ストリームカーネルの値を機械学習することにより得られた識別器とを用いて識別用ストリームカーネルを作成する識別用ストリームカーネル作成部と、識別用ストリームカーネルの出力値に基づいて当該データの属するクラスを識別する識別部とを含む。
【０００９】
本発明のさらに別の態様は学習方法に関する。この方法は、過去履歴の参照範囲を履歴数として入力するステップと、属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめるステップと、教師ストリーム構造データに基づいて教師ストリームカーネルを作成するステップと、教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成するステップとをプロセッサに実行させる。
【００１０】
本発明のさらに別の態様は、ストリーム構造データを識別する識別器を生成するためのプログラムに関する。このプログラムは、過去履歴の参照範囲を履歴数として入力する機能と、属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる機能と、教師ストリーム構造データに基づいて教師ストリームカーネルを作成する機能と、教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する機能とをコンピュータに実現させる。
【００１１】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１２】
本発明によれば、汎化性を持って精度良くデータを識別する技術を提供することができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態に係る識別プロセスを表す図である。
【図２】カーネル法による線形分離の様子を例示する図である。
【図３】ストリーム構造データの構成図である。
【図４】振舞い属性を考慮した識別を表す図である。
【図５】ストリーム構造データの作成を表す図である。
【図６】ＣＡＰ曲線による性能比較を表す図である。
【図７】ＣＡＰ曲線の見方を説明する図である。
【図８】実施の形態に係る情報処理装置の全体構成を表す図である。
【図９】ストリームカーネル学習部の構成図である。
【図１０】教師ストリームカーネル作成部の構成図である。
【図１１】ストリームカーネルを作成する処理の流れを表す図である。
【図１２】ストリーム構造データ識別部の構成図である。
【発明を実施するための形態】
【００１４】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【００１５】
［前提技術］
［１］ はじめに
実施の形態は、大規模データストリームのための履歴情報を用いたカーネル法の拡張に関するものである。実施の形態の基礎技術は、カーネル法を拡張してデータストリームを構造データと見なして識別することである。
【００１６】
近年、金融や流通分野の取引記録や、ネットワーク監視システムの通信記録等のデータストリームが新しいタイプの大規模データとして注目を集めている。データストリームには、日々刻々と生成され、時間とともに複雑な変化をともなう性質があり、この蓄積されたデータをいかに分析し活用するかが重要な課題となっている。そこで、データマイニングや機械学習がその有力な手法となる。
【００１７】
データマイニングや機械学習は、大量のデータから知識やルールを発見するための分析手法であり、本実施の形態ではこのデータストリームを識別することに焦点を当てる。これはクレジットカードの不正利用識別、ＰＯＳトランザクションからの優良顧客識別、ネットワークログからの不正侵入識別等、その応用は多岐にわたる。しかし、時間とともに複雑な変化をともなうデータストリームの識別は困難であり、識別性能を向上させることは重要な課題である。
【００１８】
このようなデータストリームの識別は、一般的に教師付き学習が用いられる。従来の教師付き学習は、オンラインで到着するデータを特徴ベクトルｘで表し、それを事前に作成した識別器ｙ＝ｆ（ｘ）に入力することで、あらかじめ定義されたカテゴリへ識別する。ここで識別精度を上げるために重要なことは、対象データ世界の特徴を抽出することである。従来の識別手法を用いれば、複雑なストリームの特徴をベクトル形式で表現しなければならない。識別で十分な精度が得られないのは、ベクトルの属性値に識別のための特徴が出ていないからである。特徴を出そうと属性の数を増やせば、次元の呪いによって識別器の汎化性能が失われ、また、その特徴抽出には深い領域知識が必要である。
【００１９】
一方、線形識別器であるサポートベクタマシン（ＳＶＭ）は、カーネル法によって非線形識別を行うことができる非線形ＳＶＭへと拡張された。詳細は後述するが、カーネル法は元のデータ空間を高次元空間へ埋め込み、この空間で線形識別を実行する。その計算はカーネル関数と呼ばれる高次元空間上の内積を表す関数で行われ、実際には高次元へ写像することなく、高次元空間上での動作を可能にする。この仕組みはカーネルトリックと呼ばれ、カーネルトリックを用いて非線形識別関数を構成することで非線形識別を可能にするＳＶＭを非線形ＳＶＭという。そしてこの非線形ＳＶＭは、最も識別性能に優れたモデルのひとつである。
【００２０】
また、このカーネル法は近年、構造を持つデータを入力にすることができるように拡張され、これまでに木、配列、グラフ等の構造データに対するカーネル関数が提案されている。このような構造データを用いると、ベクトル形式では失われていたデータの特徴を識別に用いることができ、ベクトル形式で識別するよりも高い精度が得られている。
【００２１】
そこで、本実施の形態では、カーネル法を拡張して、データストリームを構造データと見なして識別する手法を提案する。図１は実施の形態に係る識別プロセスを表す図である。例えば、クレジットカードデータの場合、この構造データは、オンラインで到着するデータ（特徴ベクトルｘ）だけでなく、あるユーザの過去ｎ回までの履歴情報をまとめた、ひとつのストリーム構造を持つデータＸ＝｛ｘ（１），ｘ（２），・・・，ｘ（ｎ）｝である。また、このストリーム構造データに適用できるカーネル関数は、新しいデータであるほど識別の影響が大きく、古いデータほど識別の影響が小さくなるようにデータを扱い、履歴情報から得られるデータストリームの時間的な変化を特徴にする。
【００２２】
まとめると、本実施の形態は既存の手法・研究と比較して、以下の技術的特徴を有する。
・オンラインで到着するデータのみを入力として分析に用いるのではなく、過去ｎ回までの履歴をまとめたものを、ひとつのストリーム構造を持つデータとして扱い、これを入力するカーネル関数（以下、「ストリームカーネル」という。）を構築する。
・従来のベクトルを入力とした場合、すなわちオンラインで到着したデータのみを用いて、過去の履歴を用いない場合のカーネルの計算量に対して、このストリームカーネルの計算量はＯ（ｎ）である。
・大規模な実際のクレジットカードデータを用いた識別実験を行い、既存の手法よりも優れた精度であることを示す。
【００２３】
本実施の形態では二値の識別に関して述べるが、この制約は重要ではない。なぜなら、どのような二値識別器でも、多重クラスの問題へ拡張できるからである。たとえば代表的なｏｎｅ−ｖｅｒｓｕｓ−ｒｅｓｔは、Ｃ１，・・・，Ｃｋのｋ個のクラスへの識別問題においてあるクラスＣｉと、それ以外のクラス∪ｊ≠ｉＣｊとを識別する二値識別器をｋ個構築する。クラスラベルが未知のデータに対する予測は、ｋ個の識別器が一貫した出力をした場合、そのクラスへ割り当て、そうでない場合は候補の中からランダムにあるいは識別器の出力の中から最もあてはまりが良いクラスへ割り当てられる。
【００２４】
[２] 関連研究
大規模に蓄積されたデータストリームを解析し、その結果を有効に活用する研究は、データマイニング１）、情報検索、統計的学習分野２）等において長年活発に行われてきた。カーネル法３），４）は、データの非線形構造をとらえる強力な手法として注目されており、分類（ｃｌｕｓｔｅｒｉｎｇ）５）や識別（ｃｌａｓｓｉｆｉｃａｔｉｏｎ）６）等に適用され、高い精度を得ている。
【００２５】
特に識別において、線形識別器であるＳＶＭにカーネルトリックを適用し、非線形識別関数を構成することで非線形識別を可能にした非線形ＳＶＭ３）は、最も識別性能に優れたモデルのひとつである。このことは、本実施の形態について行った実際の大規模なクレジットカードデータを不正利用と正常利用に識別する実験でも示されており、本実施の形態における識別器に非線形ＳＶＭを選択した動機である。
【００２６】
しかし、データストリームを対象にした場合（ネットワーク侵入識別、優良顧客識別８）等）の識別精度は、静的なデータを対象にした場合（画像認識、テキスト識別等９））と比べると劣り、先行研究では複雑な個人情報ストリームの識別が困難であることを示している。ここで使われている多くの識別アルゴリズム（Ｋ−最近傍法、決定木、ベイジアン識別器、ニューラルネットワーク、ＳＶＭ、ロジステック回帰）の入力はベクトル形式であり、過去には識別精度を向上させるために識別に有効なベクトルの属性が考えられてきた８）。しかし、時間とともに複雑な変化をともなうデータストリームの特徴をすべてベクトルの属性で表現することは困難であり、無理に特徴を出そうとベクトルの属性数を増やせば、次元の呪いによって識別器の汎化性能は失われる。
【００２７】
本実施の形態では、従来識別器に用いてきたデータだけではなく、過去の履歴データに注目する。そして、遡って得られるデータ群をひとつのストリーム構造データとして定義し、このストリーム構造データを入力して識別を行う新しい手法を提案する。
【００２８】
まず初めに直面する課題は、どのようにして構造データを入力として扱うかということであるが、上述したカーネル法は近年、配列やグラフ等の構造データを入力にして扱えるように拡張され１２），１３）、テキスト識別等で高い識別精度を得ている１１），１４）。しかし、これらは単に構造データの共通部分構造を数え上げるものであり、次の理由でデータストリームに適用することができない：共通部分の数え上げは、部分構造が一致している数をカウントしたものである。たとえば、文字列を配列として扱う文字カーネルにおいて、ふたつの文字列“ｃａｔ”と“ｃａｒｔ”には、“ｃ，ａ，ｔ，ｃａ，ａｔ，ｃｔ，ｃａｔ”という７つの共通部分文字列がある。このようにデータ要素がすべてカテゴリデータであれば、部分構造が一致している数をカウントできる。しかし、データストリームの属性は基本的にカテゴリ属性だけで構成されているわけではなく、連続値の属性も含む。したがって、共通部分の構造の数え上げという概念を持ち込むことができない。また、従来手法はデータストリームの時間的に変化する性質を考慮していない。
【００２９】
これらの課題から、本実施の形態では構造データを扱う基礎理論である畳み込みカーネルを用いて、データストリームに適用できるカーネル法を提案する。提案手法は、新しいデータほど識別の影響を大きく、古いデータほど識別の影響を小さくするようにデータを扱い、識別を行う。これによりストリームの時間的な変化を特徴にすることができる。また、上述した配列・グラフ等の構造データに対するカーネル法が高い精度を得ていることは、本実施の形態におけるデータストリームに適用できるカーネル法を提案することで精度を向上させる根拠となる。
【００３０】
[３] カーネル法と非線形サポートベクタマシン
[３．１] カーネル法
カーネル法は、データの非線形構造をとらえる強力な手法であり、ふたつの本質的な要素からなる。
（１） データを高次元特徴空間に埋め込む。
（２） 高次元特徴空間で、線形識別アルゴリズムを適用する。
【００３１】
線形識別アルゴリズムは多く研究されているが、真の識別境界が非線形である場合、十分な性能が実現できない。そこで、カーネル法は元のデータ空間をいったん線形識別アルゴリズムを適用できる高次元空間へ写像し、この空間で線形識別アルゴリズムを適用する。しかし、カーネル法はデータを高次元特徴空間では明確に示さず、カーネル関数と呼ばれる半正定値関数Ｋ：χ×χ→Ｒを用いて、高次元特徴空間での動作を可能にする。
Ｋ（ｘ，ｚ）＝〈φ（ｘ），φ（ｚ）〉 （１）
図２はこのようなカーネル法による線形分離の様子を例示する図である。
【００３２】
Ｍｅｒｃｅｒの定理を満たす半正定値関数Ｋをカーネル関数と呼び、これはφによって写像された高次元特徴空間上での内積を意味する。このように実際に高次元特徴空間へ写像する計算を避け、入力空間でのカーネル関数を用いて高次元特徴空間上での内積を計算する仕掛けをカーネルトリックと呼ぶ。また、カーネル関数には次のようなものが知られている。
・多項式カーネル
Ｋ（ｘｉ，ｘｊ）＝（ｘｉＴｘｊ＋ｃ）ｄ （２）
・ガウスカーネル
Ｋ（ｘｉ，ｘｊ）＝ｅｘｐ（−‖ｘｉ−ｘｊ‖２／σ２） （３）
・シグモイドカーネル
Ｋ（ｘｉ，ｘｊ）＝ｔａｎｈ（ａｘｉＴｘｊ−ｂ） （４）
【００３３】
線形識別器であるＳＶＭは、上述したカーネルトリックを用いて非線形識別を行うことができる識別器へと拡張された。ＳＶＭによる識別は、異なるクラスのデータ間の距離（マージン）を最大にする超平面を考える。このときの目的関数と識別関数は、特徴ベクトルの内積のみに依存した形で記述される。たとえば識別関数は、クラスレベル変数ｔ、サポートベクタの集合Ｓ、Ｌａｎｇｒａｎｇｅ乗数αｉ＊＞０、最適な閾値ｈ＊を用いて次式で書ける。
【数１】
【００３４】
この線形識別関数は、カーネルトリックを適用することにより以下の形に書き変えることができる。
【数２】
【００３５】
ここで、元の空間よりも高次元に写像するカーネル関数Ｋを選択すれば、高次元空間上で線形ＳＶＭを実行したことになり、これは元の空間で非線形識別を実行したことと等価である。このように、カーネルトリックによって非線形識別関数を構成することで、非線形識別を可能にしたＳＶＭを、非線形ＳＶＭという。
【００３６】
また、これらカーネル関数はふたつの入力の類似度を定めていると考えることができる。すなわち、適当に類似度Ｒを定義した関数Ｋを、カーネル関数として使うことができる。したがって、上述したカーネル関数のふたつの入力ｘｉ，ｘｊがベクトルでなく、ＤＮＡ配列やテキスト等の配列、ＸＭＬやＨＴＭＬで記述された構文解析木のような木構造、あるいは化合物の分子構造のようなグラフで表現される場合にも、カーネル法を適用することができる。本実施例はストリーム構造を持ったデータ間のカーネル関数であり、これら構造を持ったデータ間のカーネルを定義するための基礎理論である畳み込みカーネルについて、以下述べる。
【００３７】
[３．２] 畳み込みカーネル
本節では、カーネル関数の入力がベクトルでなく、配列やグラフ等の構造を持ったデータに対するカーネル関数を構築するための基礎理論である畳み込みカーネルについて述べる。畳み込みカーネル１５）は、構造を持つデータ間のカーネル関数はその構造の部分構造どうしのカーネル関数によって再帰的に計算されるという考えに基づいている。
【００３８】
ｘはある構造を持つデータ、Ｓ（ｘ）はｘに含まれる部分構造の集合、ｓｘをその部分構造とする。これはｚについても同様である。Ｋｓを部分構造間のカーネル関数とすると、畳み込みカーネルは以下で表現される。
【数３】
【００３９】
また、畳み込みカーネルは部分構造ｓに対する重みｆ（ｓ｜ｘ）を用いて次のように記述することができる。
【数４】
【００４０】
この部分構造のカーネル関数Ｋｓは、更に分けられた部分構造による畳み込みカーネルにより、再帰的に表現される。つまり、構造を持ったデータｘとｚは、ここから取り出される部分構造ｓｘ∈Ｓ（ｘ）とｓｚ∈Ｓ（ｚ）のカーネル関数の値をすべて足し合わせることで全体のカーネル関数が定義される。本実施例では、ストリーム構造を持つデータＸ＝｛ｘ（１），ｘ（２），・・・，ｘ（ｎ）｝間のカーネル関数を提案する。このカーネル関数がストリームカーネルであるが、このストリームカーネルも畳み込みカーネルを基礎理論としている。
【００４１】
[４] ストリームカーネル
[４．１] ストリーム構造データの定義
データストリームに対する従来の識別手法は、オンラインで到着したデータをベクトルｘ＝（ｘ１，ｘ２，・・・，ｘｄ）で表現し、これを入力に用いる。これに対し、本実施例における識別手法は、次の特徴を持った構造データを入力に用いる。
（１） オンラインで到着したｘ（１）だけでなく、過去の履歴ｎ個のデータを持つ。
（２） ｎ個の前後のデータ間に、ｎ−１個の時間間隔を持つ。
本実施例ではこれをストリーム構造データと定義し、次のように表現する。
Ｘ＝｛ｘ（１），ｘ（２），・・・，ｘ（ｎ）｝ （１０）
【００４２】
なお、ｘ（１）が新しいデータ、ｘ（ｎ）が古いデータとし、括弧内の上付き添え字を履歴番号と呼ぶ。時間間隔とは、データが到着した時間の間隔であり、例えばｘ（１）とｘ（２）との時間間隔はｔ[１，２]と表す。図３はストリーム構造データの構成図である。
【００４３】
ここで、時間間隔を計算に用いる上で注意すべきことがある。時間間隔は、後述するように、古い情報ほど識別の影響を小さくする重みを計算するときに用いられるが、このとき、遡った期間全体を１に正規化する。つまり、たとえばｎ＝４とし、過去の履歴４件を遡る場合、得られる時間間隔は、ｔ[１，２]、ｔ[２，３]、ｔ[３，４]であり、その合計をｔ[１，２]＋ｔ[２，３]＋ｔ[３，４]＝１となるように値を変換する。これは単に、各時間間隔についての、遡った期間全体に対する比を考えるだけである。たとえばクレジットカードデータを考えると、クレジットカードを１週間に１度の間隔で使う人もいれば、１カ月に１度の間隔で使う人もいる。時間間隔を正規化することで、各人それぞれの利用の間隔を同じ尺度でとらえることができる。
【００４４】
[４．２] 部分構造間のカーネル
本実施例におけるストリームカーネルは前述した畳み込みカーネルが基本理論となっている。したがって、まず前述したストリーム構造データＸ＝｛ｘ（１），ｘ（２），・・・，ｘ（ｎ）｝の部分構造ｓを定義する。例として、遡る履歴の数をｎ＝３としたＸ＝｛ｘ（１），ｘ（２），ｘ（３）｝の場合について考える。Ｘの部分構造全体の集合をＳ（Ｘ）とすると、順序関係を考慮して、Ｓ（Ｘ）は以下の６つの部分構造へ分割される。このとき、遡る履歴の数ｎに対して、得られる部分構造の数はｎ（ｎ＋１）／２である。
Ｓ（Ｘ）＝｛ｓ１，ｓ２，ｓ３，ｓ４，ｓ５，ｓ６｝
＝｛｛ｘ（１）｝，｛ｘ（２）｝，｛ｘ（３）｝，｛ｘ（１），ｘ（２）｝，｛ｘ（２），ｘ（３）｝，｛ｘ（１），ｘ（２），ｘ（３）｝｝
【００４５】
次に、分割された部分構造のカーネルの組合せを考える。ここで、異なる履歴番号で観測されたデータが独立であるとする。すなわち、Ｋ（ｘ（ｉ），ｚ（ｊ））＝０，ｉ≠ｊとし、部分構造間のカーネルを、部分構造に含まれるデータのカーネルの積で表現する。すると、部分構造のデータ数が同じで，かつ履歴番号が同じであるときのみ、その部分構造どうしのカーネルＫｓは計算され、次式で表される。
【数５】
【数６】
【００４６】
なお、Ｋ（ｘ（ｉ），ｚ（ｉ））は前述した半正定値カーネルである。これにより、考えるべきカーネルの組合せはｎ（ｎ＋１）／２通りとなる。
【００４７】
[４．３] 部分構造の重み
次に、畳み込みカーネルにおける部分構造の重みｆ（ｓ｜Ｘ）を定義する。このｆ（ｓ｜Ｘ）は前述した部分構造のカーネルが、全体の類似度にどれほどの影響力を持つかを表す。これを考えるうえで、理解が単純になるよう再度クレジットカードデータの例を用いる。
【００４８】
オンラインで到着した顧客ＡのデータをｘＡ（１）とすると、この利用ｘＡ（１）が正常利用か、不正利用かを識別するために、顧客Ａの利用履歴を過去ｎ回遡ったストリーム構造データＸＡ＝｛ｘＡ（１），ｘＡ（２），・・・，ｘＡ（ｎ）｝を得る。ｘＡ（１）が新しいデータ、ｘＡ（ｎ）が古いデータとすると、ｘＡ（１）とｘＡ（ｎ）とを同じ重みで扱うと正確な識別を行うことができない。なぜなら、知りたいのは到着したデータｘＡ（１）が不正利用か、正常利用かということである。古いデータがいくら正常利用らしくても、到着したデータが明らかに不正利用らしければ、到着したデータの方を優先すべきである。したがって、新しいデータを含む部分構造であるほど重み（影響度）を大きく、古いデータを含む部分構造であるほど重みを小さくする。この重みｆ（ｓ｜Ｘ）は、前述した時間間隔ｔと、新たに導入するパラメータλ∈（０，１）とを用いた単調減少関数λｔによって定義される。
【００４９】
ここで、部分構造に含まれるそれぞれのデータに対して具体的に重みを与える。すなわちｎ番目の履歴データに対して、重みを
【数７】
と定義する。例として、ｓｘ＝｛ｘ（２），ｘ（３），ｘ（４）｝とｓｚ＝｛ｚ（２），ｚ（３），ｚ（４）｝の重みｆ（ｓｘ｜Ｘ）とｆ（ｓｚ｜Ｚ）とを求める。部分構造ｓｘに含まれるデータそれぞれの重みを表１に示す。
【表１】
なお、ｔｘは、ストリーム構造データＸが持つ時間間隔であるとし、記述の簡略化のため、
【数８】
とする。このｘをすべてｚで置き換えれば、同様に部分構造ｓｚに含まれるデータそれぞれの重みを表す。簡略化せずに重みを詳細に記述すれば、ｆ（ｓｘ｜Ｘ）とｆ（ｓｚ｜Ｚ）はそれぞれ次式で表される。
【数９】
【数１０】
【００５０】
したがって、このときの部分構造の重みを含めたカーネルは式（１１）を用いて、
【数１１】
となる。
【００５１】
[４．４] ストリームカーネル計算アルゴリズム
Ｋｎ（Ｘ，Ｚ）と、ＸとＺとがともに過去ｎ件のストリーム構造データからなるときのストリームカーネルとする。また、過去ｎ件からなるＸに、さらにもう１件遡って得られるｘ（ｎ＋１）が、Ｘに付与されることをＸｘ（ｎ＋１）と表現する。もちろんこれはＺについても同様であるが、以降はＺにも同じ作業を与えたとして、その記述は省略する。
【００５２】
ここで具体的に、例としてｎ＝１の場合から考える。このとき、ＸはＸ＝｛ｘ（１）｝であり、Ｓ（Ｘ）＝｛ｓ１｝＝｛ｘ（１）｝である。したがって、単純にＫ１（Ｘ，Ｚ）は次で表される。
Ｋ１（Ｘ，Ｚ）＝Ｋ（ｘ（１），ｚ（１）） （１５）
【００５３】
次に、Ｘ＝｛ｘ（１）｝にｘ（２）が付与され、Ｘｘ（２）＝｛ｘ（１），ｘ（２）｝となったときのＫ２（Ｘｘ（２），Ｚｚ（２））を考える。Ｘｘ（２）＝｛ｘ（１），ｘ（２）｝により、前述と同様の手法で、Ｘｘ（２）は３つの部分構造に分割できる。
Ｓ（Ｘｘ（２））＝｛ｓ１，ｓ２，ｓ３｝
＝｛｛ｘ（１）｝，｛ｘ（２）｝，｛ｘ（１），ｘ（２）｝｝
【００５４】
式（９）、（１１）、（１４）により、Ｋ２（Ｘｘ（２），Ｚｚ（２））は次式で記述できる。なお、数式の簡略化のため、ｔｘ[ｉ，ｉ＋１]＋ｔｚ[ｉ，ｉ＋１]＝Ｔ[ｉ，ｉ＋１]とする。
Ｋ２（Ｘｘ（２），Ｚｚ（２））＝Ｋ（ｘ（１），ｚ（１））＋λＴ[１，２]Ｋ（ｘ（２），ｚ（２））＋λＴ[１，２]Ｋ（ｘ（１），ｚ（１））Ｋ（ｘ（２），ｚ（２）） （１６）
【００５５】
ここで、式（１５）と式（１６）とを比較し、ｘ（２）が付与されることで増加するカーネルの量を計算する。この量をＪ２とすると、Ｊ２は次のようにＪ１を用いた形で書くことができる。
Ｊ２＝Ｋ２（Ｘｘ（２），Ｚｚ（２））−Ｋ１（Ｘ，Ｚ）
＝λＴ[１，２]Ｋ（ｘ（２），ｚ（２））＋λＴ[１，２]Ｋ（ｘ（１），ｚ（１））Ｋ（ｘ（２），ｚ（２））
＝λＴ[１，２]Ｋ（ｘ（２），ｚ（２））｛１＋Ｋ（ｘ（１），ｚ（１））｝
＝λＴ[１，２]Ｋ（ｘ（２），ｚ（２））｛１＋Ｊ１｝ （１７）
【００５６】
同様に、Ｘ＝｛ｘ（１），ｘ（２）｝にｘ（３）を付与した場合を展開しても、ｘ（２）が付与されることで増加するカーネルの量Ｊ３もまた、Ｊ２を用いた形で書くことができる。したがって、遡るデータがひとつ増えることで、全体のカーネルに加えられる部分構造のデータのカーネルの量をＪｎとすると、ストリームカーネルは以下のように一般化した形で、再帰的に表現することができる。
Ｋｎ（Ｘｘ（ｎ），Ｚｚ（ｍ））＝Ｋｎー１（Ｘ，Ｚ）＋Ｊｎ （１８）
【数１２】
ただし、Ｋ０（Ｘ，Ｚ）＝１、Ｊ１＝Ｋ（ｘ（１），ｚ（１））である。
【００５７】
動的計画法を用いることにより、この計算量は遡るデータ数ｎに対してＯ（ｎ）で済む。また、ＸとＺのデータ数が異なる場合、このままでは、データ数が少ない部分集合のカーネルのみを考えてしまう。たとえば、Ｘ＝｛ｘ（１），ｘ（２），ｘ（３）｝，Ｚ＝｛ｚ（１），ｚ（２）｝とすると、ｘ（３）はカーネルの計算にまったく用いられない。そこで、以下の式で正規化を行い、これをストリームカーネルの最終出力値とする。
【数１３】
【００５８】
さらに、このストリームカーネルが半正定値性を満たすことを述べる。いくつかの半正定値性を満たすカーネル関数は、これを足し合わせたり、掛け合わせたり、また定数倍したりしたものもまた、半正定値性を満たすカーネル関数となることが知られている。ストリームカーネルは、半正定値性を満たすカーネル関数を基本として用い、部分構造どうしのカーネルの計算ではこのカーネルを掛け合わせ、部分構造の重みはカーネルを定数倍し、畳み込みで表現された構造全体のカーネルはこれらを足し合わせたものである。したがって，ストリームカーネルは半正定値性を満たす。
【００５９】
[５] 実験評価
本実施例では、実際のデータストリームであるクレジットカードデータ（実験データの詳細は後述する。）に対して、ガウスカーネルを用いた通常のＳＶＭと、本実施例のストリームカーネルＳＶＭ（以下、「ＳＫＳＶＭ」という。）を適用し，正常利用と不正利用に識別した。また、その性能を以下の点から比較した：
（ａ） 学習・検証にかかる時間
（ｂ） 識別の精度（正答率）
（ｃ） モデルの性能（ＣＡＰ曲線）
【００６０】
[５．１] 実験準備
実験は２ＧＨｚのＣＰＵと、３ＧＢのメモリを持つハードウェア環境を使用した。本実施例に係るＳＫＳＶＭは、ＯＳＳであるｓｖｍ−ｌｉｇｈｔ１６）（Ｃ言語）上で実装を行った。
【００６１】
実験で使用したカーネル関数は、ガウスカーネルＫ（ｘｉ，ｘｊ）＝ｅｘｐ（−‖ｘｉ−ｘｊ‖２／σ２）である。ガウスカーネルは、パラメータσの設定によってはシグモイドカーネルようにも動作し、また、先行研究で行った実験結果により、ガウスカーネルが識別に最も有効に動作すると判断した。ガウスカーネルのパラメータσは、事前に‖ｘｉ−ｘｊ‖２の統計を取り、これらが適切にＫ（ｘｉ，ｘｊ）∈（０，１）を得るような範囲を確定し、ＳＶＭの正則化パラメータＣとともに試行錯誤的に決定した。
【００６２】
ストリームカーネルのパラメータλは、一番最近のデータのカーネル関数の値が、ストリームカーネル全体の影響の７割程度を占めるように設定した。これは、過去の情報の重みを大きくしすぎてしまうと、一番重要な最近のデータの特徴が埋もれてしまうためである。また、顧客の遡る履歴数ｎは、ｎ＝５に設定した。これら実験で用いたパラメータを表２に示す。
【表２】
【００６３】
本実施例ではモデルの性能をＣＡＰ曲線によって評価するため、新たにスコア値という考えを導入している。スコア値とは、値が高いものほど不正利用であるらしく、逆に値が低いものほど正常利用であるらしいという指標である。具体的には、ＳＶＭの出力ｙに対して、スコア値ｓｃｏｒｅは以下の式で１〜１０００の値で出力される。
【数１４】
【００６４】
[５．２] 実験データ
本実験で用いたデータセットは、実際のクレジットカードデータである。クレジットカードデータは、約２年分のデータが用意されており、そのデータ量は約１ＴＢに及ぶ。クレジットカードデータの属性は、大きく次の２つのグループに分類される。
（ａ） オーソリデータ属性： 利用時の状況を記述した属性
（ｂ） 振舞いデータ属性： 顧客の行動パターンを記述した属性
【００６５】
属性（ａ）は、単にクレジットカードの取引データ（以下、「オーソリデータ」という。）の属性である。たとえばこの属性には、顧客ＩＤ、生年月日、利用時間、利用金額、購入商品コード等があり、計８４属性からなる。しかし、これらの属性には識別に有効な（不正利用と正常利用で、はっきり値が異なるような）属性は少ない。したがって、この属性だけを用いて識別アルゴリズムを適用しても高い精度は得られない。そこで、識別の特徴として貢献するような以下の属性（ｂ）を、人工的に作成する。
【００６６】
属性（ｂ）は過去の履歴情報から作成した顧客モデル（過去の利用金額の平均や分散、過去の利用時間帯の頻度等）との乖離値であり、顧客の行動パターンを記述した属性である。たとえばある人が高額な買い物をしたとする。その人が前回も同程度の額の買い物をしていたならば、その利用は本人、すなわち正常利用らしいが、逆に前回低額な買い物をしていたならば、第三者利用、すなわち不正利用である可能性があると判断することができる。図４は振舞い属性を考慮した識別を表す図である。
【００６７】
このように顧客モデルに基づいてその顧客の行動パターンの時間的変化に注目することは、クレジットカードの領域だけでなく、ネットワーク侵入や個人認証等、他の多くの領域・データにあてはまり、有用である。この属性（ｂ）には「前回利用時間との差」、「前回利用金額との差」、「過去６カ月の曜日ごとの利用回数との比較」等があり、計４０属性からなる。本実験で用いたクレジットカードデータセットは属性（ａ）と属性（ｂ）とから５５属性を分析に用いた。データセットの詳細を表３に示す。
【表３】
【００６８】
ＳＫＳＶＭとＳＶＭの学習・検証データの違いは、利用時点から過去ｎ回の履歴があるか、ないかである。ＳＫＳＶＭの学習・検証データは、図５で示すように、上述した顧客モデルを更新しながら属性（ｂ）を作成して、ストリームデータ構造を作成する。本実験では、ｎ＝５とし過去５回の履歴を遡ってストリーム構造データを作成し、識別を行う。
【００６９】
クレジットカードデータを、ストリーム構造データとして扱ううえでの注意すべき点として、顧客のマスタ情報を繰り返し用いることがあげられる。たとえば、顧客の「性別」等属性を分析に用いるとする。すると、過去２件目、３件目にも同じ性別の属性が、繰り返し入ることになる。一見これはデータの冗長性から無駄のように見えるが、これらは全て必要である。なぜなら、冗長性のある「性別」という属性を１件目だけに用いて、それ以降の過去２件目、３件目には用いない場合を考える。そしてもし、その「性別」という属性が、不正利用につながる重要な属性であるとすれば、部分集合間のカーネルを考える際、不十分な情報で過去の履歴を処理してしまい、全体として、特徴が薄れてしまうためである。
【００７０】
[５．３] 実験結果と考察
[５．３．１] 学習と検証の時間
通常のＳＶＭと、ＳＫＳＶＭの学習時間・検証時間の比較を表４で示す。表４における数字の単位は秒である。実験の結果、学習時間・検証時間ともに、本実施例の手法は通常のＳＶＭと比べて約１０倍の時間がかかった。ＳＫＳＶＭのカーネルの計算量は、通常のＳＶＭのカーネルの計算量に比べ、理論上では遡る履歴の数ｎに対してＯ（ｎ）で増加するものの、実際のデータでは欠損値の場合の処理、時間間隔データの変換等の事前計算処理が必要であるため、表４に示した結果はこれらオーバーヘッドを含んだものである。
【表４】
【００７１】
次に、通常のＳＶＭと、ＳＫＳＶＭのモデルの大きさであるサポートベクタ（ＳＶ）の数の比較を表５で示す。これは式（７）において検証の際に計算を繰り返す数を表している。したがって、ＳＶの数が少なければ、より少ない計算量で検証を行うことができることを示し、また、スパースな解が得られていることになる。表５で示すように、ＳＫＳＶＭの方がよりスパースな解を得ていることが分かる。
【表５】
【００７２】
[５．３．２] 識別の精度（正答率）
識別の精度を評価する指標には、一般に適合率（ｐｒｅｃｉｓｉｏｎ）と再現率（ｒｅｃａｌｌ）が用いられる。しかし、本実験で用いた実際のクレジットカードデータは、不正利用の数が正常利用の数に比べて約０．０２％と極端に少なく、また、識別能力の弱い識別器を用いるとすべてを正常利用であると判断してしまうほど、正常利用と不正利用との識別は困難である。したがって、適合率と再現率はともに数％という値しか取ることができず、実際のクレジットカードデータを不正利用と正常利用に識別するというこの領域においては、これらの指標は適当ではない。
【００７３】
本実施例にかかるＳＫＳＶＭによる識別精度の向上を明確にするため、本実験の識別精度は正答率で評価する。正答率は、識別を行った全件（７２０，９２０件）に対し、その識別結果が正しかった件数の割合である。表６と表７で示すように、ＳＶＭの正答率が９９．８２％であったのに対し、ＳＫＳＶＭの正答率は９９．８９％であり、０．０７％向上している。
【００７４】
割合からはそれほどの向上は見られないが、これは大きな変化である。表６において、ＳＶＭが不正利用であると判断した件数は、１１１０件である。しかし、そのうち１０８０件は実際には正常利用であり、これは間違った識別である。一方、表７において、ＳＫＳＶＭが不正利用であると判断した件数は５８６件である。これはＳＶＭと比べると約半分のヒット件数であるにもかかわらず、実際に不正利用であった件数は変わらない（３０件と２８件）。検証データとして用いたデータセットは不正利用の数が少ないため、この変化は割合として大きく現れないが、実際にはＳＫＳＶＭは不正利用データを発見するときのノイズを半分に減らしていることが分かる。
【表６】
【表７】
【００７５】
[５．３．３] ＣＡＰ曲線による比較
ＣＡＰ（Ｃｕｍｕｌａｔｉｖｅ Ａｃｃｕｒａｃｙ Ｐｒｏｆｉｌｅｓ）曲線は、予測モデルの性能を評価するのに用いられ、実際のクレジットカード業界でも使用されている。横軸は、不正利用である確率（スコア値）が高いと識別器が判断したクレジットカードデータを順に並べた数であり、縦軸は、その中で実際に不正利用であった顧客の人数である。図６は、通常のＳＶＭと、ＳＫＳＶＭのＣＡＰ曲線による比較を示している。また、図７はＣＡＰ曲線の見方を説明する図である。もし得られた曲線が、図７で示すＣに近いならば、スコア値はランダムにつけられたものと等価であり、モデルにまったく説明力がないことを示す。対称的に、得られた曲線がＡに近いならば、実際に不正利用であるクレジットカードデータに対して高いスコア値をつけられていることになり、モデルの性能が高いことを示す。実際にはＡとＣとの間の、Ｂのような曲線を取る。
【００７６】
図６から、ＳＫＳＶＭは不正らしい上位５００件を監視すれば、１５人の不正利用者を検知できていることを示している。これに対し、ＳＶＭは同様に不正らしい上位５００件を監視しても、約半数の８人の不正利用者しか検知できていない。さらに、ＳＫＳＶＭが不正らしい上位５００件を監視するだけで検知できる１５人の不正利用者を、ＳＶＭが検知しようとすれば、不正らしい上位１，０００件（ＳＫＳＶＭの場合の倍）もの監視をしなければならないと言うことも示している。
【００７７】
[６] 参考文献
1) McCarthy, J.: PHENOMENAL DATA MINING: FROM DATA TO PHENOMENA, ACM SIGKDD Explorations, Vol.1, No.2, pp.24-29, (2000).
2) Martin, H.C.L., Zhang, N. and Anil, K.J.: Nonlinear Manifold Learning For Data Stream, Proc. SIAM International Conference for Data Mining, pp.33-44 (2004).
3) Scholkopf, B. and Smola, A.J.: Learning with Kernels, MIT Press (2002)
4) Shawe-Taylor, J. and Cristianini, N.: Kernel Methods for Pattern Analysis, Cambridge University Press (2004).
5) Jain, A., Zhang, Z. and Chang, E.Y.: Adaptive non-linear clustering in data streams, CIKM '06: Proc. 15th ACM International Conference on Information and Knowledge Management, New York, NY, USA, pp.122-131, ACM (2006).
6) Milenova, B.L., Yarmus, J.S. and Campos, M.M.: SVM in Oracle Database 10g: Removing the Barriers to Widespread Adoption of Support Vector Machines, VLDB '05: Proc. 31st International Conference on Very Large Data Bases, VLDB Endowment, pp.1152-1163 (2005).
7) 都築 学、小西 修、新美礼彦：カーネル法による現象データマイニング、電子情報通信学会第１８回データ工学ワークショップ（２００６）.
8) 鈴木秀男、水野 誠、住田 潮、佐治 明：ＣＲＭのための優良顧客識別手法の特性評価と財務効果、Department of Social Systems and Management Discussion Paper Series, No.1123 (2005).
9) Hoi, S.C.H., Jin, R. and Lyu, M.R.: Large-scale text categorization by batch mode active learning, WWW '06: Proc. 15th International Conference on World Wide Web, pp.633-642, ACM (2006).
10) Komarek, P. and Moore, A.: Making Logistic Regression A Core Data Mining Tool: A Practical Investigation of Accuracy, Speed, and Simplicity, Technical report, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA (2005).
11) Joachims, T.: Text categorization with support vector machines: Learning with many relevant features, Proc. European Conference on Machine Learning (ECML'98), pp.137-142 (1998).
12) 鹿島久嗣:カーネル法による構造データマイニング、情報処理、Vol.46, No.1, pp.27-33 (2005).
13) 津田宏治：カーネル設計の技術、情報論的学習理論ワークショップ（IBIS2002）, pp.1-10 (2002).
14) Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N. and Watkins, C.: Text classification using string kernels, Journal of Machine Learning Research, Vol.2, pp.419-444 (2002).
15) Haussler, D.: Convolution Kernels on Discrete Structures, Technical report, UC Santa Cruz (1999).
16) Joachims, T.: SVM-Light Support Vector Machine. http://svmlight.joachims.org/
【００７８】
［具体例］
実施の形態
図８は、実施の形態に係る情報処理装置１００の全体構成を表す図である。これらの構成は、ハードウェア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。
【００７９】
情報処理装置１００は、学習部１０と識別部１２とを含む。学習部１０はさらに、教師データ格納部１４、ストリームカーネル学習部１６、識別器格納部１８を含む。また、識別部１２はさらに、ストリーム構造データ識別部２０、ストリームデータ格納部２２、出力部２４を含む。
【００８０】
本実施の形態に係る情報処理装置は、あらかじめ機械学習手法であるストリームカーネルＳＶＭによって識別器を作成しておき、その識別器に基づいてオンラインで到着するデータの属するクラスを判別するという構造を持つ。そこで、まずストリームカーネルＳＶＭによる学習過程について説明する。
【００８１】
教師データ格納部１４は機械学習に用いるためのデータを格納する部分である。教師データとは、そのデータの属するクラスが既知であるデータの集合のことである。たとえば、クレジットカードの取引データについて、その取引が正常利用であるのか不正利用であるのかの二値に分類する問題を考える。このとき、教師データとは、その取引が正常利用か不正利用であるかが既知であるデータの集合である。
【００８２】
ストリームカーネル学習部１６は、教師データ格納部１４から受け取った教師データに基づいてストリーム構造データを構築し、ストリームカーネルＳＶＭを用いて機械学習により識別器を作成する部分である。これは主に前提技術[４]に記載の技術に基づいて作成したストリームカーネルを使って前提技術[３]に記載の非線形ＳＶＭにより学習する。
【００８３】
識別器格納部１８はストリームカーネル学習部１６が出力した学習結果である識別器を格納する部分である。
【００８４】
ストリーム構造データ識別部２０は、過去の履歴データと、ストリームデータ格納部２２から受け取るオンラインで到着したデータとからストリーム構造データを構築し、識別器格納部１８から受け取った識別器に基づいて、当該オンラインで到着したデータのクラスを識別する部分である。これは主に前提技術[４]に記載の技術に基づくものである。出力部２４はストリーム構造データ識別部２０が識別した結果を図示しないモニタ等の出力ディバイスやストレージ等に出力する。
【００８５】
図９はストリームカーネル学習部１６の構成図である。ストリームカーネル学習部１６は履歴数入力部２６、教師ストリーム構造データ作成部２８、教師ストリームカーネル作成部３０、機械学習部３２を含む。
【００８６】
履歴数入力部２６はストリーム構造データを作成するに際し、過去何回までの履歴をまとめるかについての情報を入力する部分である。ユーザが任意の回数を自由に入力できるようにしても良いし、例えば５回のように固定されていても良い。教師ストリーム構造データ作成部２８は、履歴数入力部２６から参照すべき過去の履歴回数を受け取り、ストリーム構造データを作成する部分である。ストリーム構造データは前提技術[４．１]に記載の構造のデータであるが、ここではさらに、おのおののデータが正常利用であるか不正利用であるかの情報をも付与された教師データとして作成される。
【００８７】
教師ストリームカーネル作成部３０は、教師ストリーム構造データ作成部２８から教師ストリーム構造データを受け取り、ＳＶＭの学習に供すべき教師ストリームカーネルを作成する部分である。詳細は後述するが、これは前提技術[４．２]、[４．３]、[４．４]に記載のアルゴリズムに基づく。
【００８８】
機械学習部３２は、教師ストリームカーネル作成部３０が作成した教師ストリームカーネルを用いてＳＶＭの学習を行う部分である。ＳＶＭは前提技術[３．１]に記載の非線形識別アルゴリズムに基づく。
【００８９】
図１０は教師ストリームカーネル作成部３０の構成図である。教師ストリームカーネル作成部３０は時間間隔正規化部３４、ストリームカーネル作成部３６、カーネル正規化部３８を含む。
【００９０】
時間間隔正規化部３４は、教師ストリーム構造データ作成部２８から受け取ったストリーム構造データに含まれる履歴の発生日時を参照して、各履歴間の時間間隔を正規化する部分である。これは前提技術[４．１]に記載のアルゴリズムに基づくものであり、その目的はデータによって異なる履歴の発生間隔を正規化して、それぞれの履歴の発生間隔を同じ尺度でとらえることである。
【００９１】
ストリームカーネル作成部３６は、教師ストリーム構造データ作成部２８から受け取った教師ストリーム構造データと時間間隔正規化部３４から受け取った正規化された時間間隔とを受け取って、ストリームカーネルを計算する部分である。これは前提技術[４．４]に記載のアルゴリズムに基づくものである。式（１８）、式（１９）で表されるように、ストリームカーネルは漸化式を用いて表現できるため、動的計画法を適用することでストリームカーネル生成の計算量を抑制することができる。
【００９２】
カーネル正規化部３８は、ストリームカーネル作成部３６が作成したカーネルを正規化する部分である。これは、ストリームカーネルの計算に用いるストリーム構造データＸとＺとの履歴数が異なる場合には、履歴数の少ない部分集合のカーネルのみとなるため、前提技術[４．４]の式（２０）を用いて是正するものである。
【００９３】
図１１はストリームカーネルを作成する処理の流れを表す。ステップＳ１０およびステップＳ１２は前提技術[４．４]に記載の漸化式（１８）、（１９）を計算するための初期値を設定する。具体的には、まずＫ０（Ｘ，Ｚ）の値を１に設定し（Ｓ１０）、Ｊ１の値をＫ（ｘ（１），ｚ（１））に設定する（Ｓ１２）。ここで、Ｋ（ｘ（１），ｚ（１））としては、たとえば前提技術[３．１]における式（３）に示すガウスカーネルを用いる。次に、ループ変数ｉを１に初期化する（Ｓ１４）。
【００９４】
ステップＳ１６はループの終了を判断するステップである。具体的には、ループ変数ｉの値が遡る履歴回数ｎ以下の場合にはステップＳ１８に進む（Ｓ１６Ｙ）。そうでない場合にはループを終了し、ステップＳ２４に進む（Ｓ１６Ｎ）。
【００９５】
ステップＳ１８からステップＳ２２は、前提技術[４．４]に記載の漸化式（１８）、（１９）を用いて、順次更新することによりストリームカーネルを生成するステップである。まず式（１８）に基づき、Ｋｉ（Ｘｘ（ｉ），Ｚｚ（ｉ））をＪｉとＫｉ−１（Ｘ，Ｚ）との和により求める（Ｓ１８）。例えばｉ＝１の場合にはＫ１（Ｘｘ（１），Ｚｚ（１））＝Ｋ０（Ｘ，Ｚ）＋Ｊ１となるが、右辺はそれぞれ前述のステップＳ１０およびＳ１２において定められている。結局、Ｋ１（Ｘｘ（１），Ｚｚ（１））＝Ｋ（ｘ（１），ｚ（１））となる。
【００９６】
次に、式（１９）に基づき、Ｊｉ＋１をＪｉ、Ｋ（ｘ（ｉ＋１），ｚ（ｉ＋１））および前提技術[４．３]のアルゴリズムに基づいて求めた重みを用いて求める（Ｓ２０）。例えばｉ＝１の場合にはＪ２＝（１＋Ｊ１）Ｋ（ｘ（２），ｚ（２））λＴ［１，２］となる。ここで、Ｊ１はステップＳ１２において定められており、Ｋ（ｘ（２），ｚ（２））は例えば前提技術[３．１]における式（３）のガウスカーネルを用いれば計算できる。またλＴ［１，２］は前提技術[４．３]のアルゴリズムに基づき、時間間隔正規化部３４であらかじめ計算しておいたデータを用いればよい。
【００９７】
ステップＳ１８およびステップＳ２０によりＫｉ（Ｘｘ（ｉ），Ｚｚ（ｉ））およびＪｉ＋１が更新できたので、ループ変数ｉをｉ＋１に更新し、ステップＳ１６に戻る（Ｓ２２）。ループ変数ｉがｎ以下の間、以上のループを回すことにより、ストリームカーネルＫｎ（Ｘ，Ｚ）を漸化式を用いて順に更新することができる。こうして得られたストリームカーネルＫｎ（Ｘ，Ｚ）を出力し（Ｓ２４）、終了する。
【００９８】
以上ストリーム構造データをＳＶＭで扱うためのストリームカーネルの作成方法について説明した。ストリームカーネルを用いることにより、あるひとつのストリーム構造データから対応するひとつのストリームカーネルの出力値を得ることができる。この出力値を用いれば従来のＳＶＭによる機械学習を行うことができる。このように、ストリームカーネルの出力値を用いて従来のＳＶＭによる機械学習を行うことがストリームカーネルＳＶＭである。
【００９９】
次に、ストリームカーネルＳＶＭの学習結果である識別器を用いて、オンラインで到着するデータがどのクラスに属するかを識別する方法について説明する。
【０１００】
図１２はストリーム構造データ識別部２０の構成図である。ストリーム構造データ識別部２０はストリーム構造データ構築部４０、識別用ストリームカーネル作成部４２、識別部４４を含む。
【０１０１】
ストリーム構造データ構築部４０は、ストリームデータ格納部２２からオンラインで到着したデータを受け取り、当該データを含め過去ｎ回までの履歴データを基にストリーム構造データを構築する部分である。これにより、オンラインで到着するデータのみならず、過去ｎ回までの履歴を入力として識別することが可能となる。これは主に前提技術[４．１]〜[４．３]に記載のアルゴリズムに基づく。
【０１０２】
識別用ストリームカーネル作成部４２は、識別器格納部１８から識別器と、ストリーム構造データ構築部４０で構築されたオンラインで到着したデータを含むストリーム構造データとを受け取り、識別用のストリームカーネルを作成する部分である。識別器には複数のストリーム構造データがサポートベクタとして含まれている。これらのサポートベクタを例えば前提技術[４．１]〜[４．４]に記載のアルゴリズムのＺとし、ストリーム構造データ構築部４０で構築されたストリーム構造データをＸとすれば、識別用のストリームカーネルを構築することができる。
【０１０３】
識別部４４は、識別用ストリームカーネル作成部４２で作成された識別用のストリームカーネルに基づき、オンラインで到着したデータの属するクラスを識別する部分である。具体的には、前提技術[３．１]に記載の式（７）におけるＫ（ｘｉ，ｘ）を前記ストリームカーネルに置換し、その出力値の正負によってふたつのクラスに識別すればよい。
【０１０４】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【符号の説明】
【０１０５】
１０ 学習部、 １２ 識別部、 １４ 教師データ格納部、 １６ ストリームカーネル学習部、 １８ 識別器格納部、 ２０ ストリーム構造データ識別部、 ２２ ストリームデータ格納部、 ２４ 出力部、 ２６ 履歴数入力部、 ２８ 教師ストリーム構造データ作成部、 ３０ 教師ストリームカーネル作成部、 ３２ 機械学習部、 ３４ 時間間隔正規化部、 ３６ ストリームカーネル作成部、 ３８ カーネル正規化部、 ４０ ストリーム構造データ構築部、 ４２ 識別用ストリームカーネル作成部、 ４４ 識別部、 １００ 情報処理装置。
【技術分野】
【０００１】
この発明は学習装置、クラス識別装置、学習方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、金融や流通分野の取引記録、ネットワーク監視システムの通信記録等のデータストリームが新しいタイプの大規模データとして注目を集めている。このようなデータストリームの識別は、一般的に教師付き学習が用いられる。従来の教師付き学習は、オンラインで到着するデータを特徴ベクトルで表し、それを事前に作成した識別器に入力することで、あらかじめ定義されたカテゴリへ識別することが行われている。
【０００３】
大規模に蓄積されたデータストリームを解析し、その結果を有効に活用する研究は、データマインイング１）、情報検索、統計的学習分野２）等において長年活発に行われてきた。カーネル法３），４）は、データの非線形構造をとらえる強力な手法として注目されており、分類５）や識別６）等に適用され、高い精度を得ている。特に識別において、線形識別器であるＳＶＭにカーネルトリックを適用し、非線形識別関数を構成することで非線形識別を可能にした非線形ＳＶＭは、最も識別性能に優れたモデルのひとつである（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−１５３５８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、データストリームを対象にした場合の識別精度は、静的データを対象にした場合と比べると識別精度が劣るという欠点がある。時間とともに複雑な変化をともなうデータストリームの特徴を入力ベクトルの属性で表現することは困難であり、無理に特徴を出そうと入力ベクトルの属性数を増やせば、次元の呪いによって識別器の汎化性能が失われるという欠点もある。
【０００６】
本発明はこうした状況に鑑みてなされたものであり、その目的は、汎化性を持って精度良くデータを識別することができる情報処理装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明のある態様は学習装置に関する。この装置は、過去履歴の参照範囲を履歴数として入力する履歴数入力部と、属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる教師ストリーム構造データ作成部と、教師ストリーム構造データに基づいて教師ストリームカーネルを作成する教師ストリームカーネル作成部と、教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する機械学習部とを含む。
【０００８】
本発明の別の態様はクラス識別装置に関する。この装置は、オンラインで受け取ったデータと当該データの過去履歴とから識別用ストリーム構造データを構築するストリーム構造データ構築部と、前記識別用ストリーム構造データと、教師ストリームカーネルの値を機械学習することにより得られた識別器とを用いて識別用ストリームカーネルを作成する識別用ストリームカーネル作成部と、識別用ストリームカーネルの出力値に基づいて当該データの属するクラスを識別する識別部とを含む。
【０００９】
本発明のさらに別の態様は学習方法に関する。この方法は、過去履歴の参照範囲を履歴数として入力するステップと、属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめるステップと、教師ストリーム構造データに基づいて教師ストリームカーネルを作成するステップと、教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成するステップとをプロセッサに実行させる。
【００１０】
本発明のさらに別の態様は、ストリーム構造データを識別する識別器を生成するためのプログラムに関する。このプログラムは、過去履歴の参照範囲を履歴数として入力する機能と、属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる機能と、教師ストリーム構造データに基づいて教師ストリームカーネルを作成する機能と、教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する機能とをコンピュータに実現させる。
【００１１】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１２】
本発明によれば、汎化性を持って精度良くデータを識別する技術を提供することができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態に係る識別プロセスを表す図である。
【図２】カーネル法による線形分離の様子を例示する図である。
【図３】ストリーム構造データの構成図である。
【図４】振舞い属性を考慮した識別を表す図である。
【図５】ストリーム構造データの作成を表す図である。
【図６】ＣＡＰ曲線による性能比較を表す図である。
【図７】ＣＡＰ曲線の見方を説明する図である。
【図８】実施の形態に係る情報処理装置の全体構成を表す図である。
【図９】ストリームカーネル学習部の構成図である。
【図１０】教師ストリームカーネル作成部の構成図である。
【図１１】ストリームカーネルを作成する処理の流れを表す図である。
【図１２】ストリーム構造データ識別部の構成図である。
【発明を実施するための形態】
【００１４】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【００１５】
［前提技術］
［１］ はじめに
実施の形態は、大規模データストリームのための履歴情報を用いたカーネル法の拡張に関するものである。実施の形態の基礎技術は、カーネル法を拡張してデータストリームを構造データと見なして識別することである。
【００１６】
近年、金融や流通分野の取引記録や、ネットワーク監視システムの通信記録等のデータストリームが新しいタイプの大規模データとして注目を集めている。データストリームには、日々刻々と生成され、時間とともに複雑な変化をともなう性質があり、この蓄積されたデータをいかに分析し活用するかが重要な課題となっている。そこで、データマイニングや機械学習がその有力な手法となる。
【００１７】
データマイニングや機械学習は、大量のデータから知識やルールを発見するための分析手法であり、本実施の形態ではこのデータストリームを識別することに焦点を当てる。これはクレジットカードの不正利用識別、ＰＯＳトランザクションからの優良顧客識別、ネットワークログからの不正侵入識別等、その応用は多岐にわたる。しかし、時間とともに複雑な変化をともなうデータストリームの識別は困難であり、識別性能を向上させることは重要な課題である。
【００１８】
このようなデータストリームの識別は、一般的に教師付き学習が用いられる。従来の教師付き学習は、オンラインで到着するデータを特徴ベクトルｘで表し、それを事前に作成した識別器ｙ＝ｆ（ｘ）に入力することで、あらかじめ定義されたカテゴリへ識別する。ここで識別精度を上げるために重要なことは、対象データ世界の特徴を抽出することである。従来の識別手法を用いれば、複雑なストリームの特徴をベクトル形式で表現しなければならない。識別で十分な精度が得られないのは、ベクトルの属性値に識別のための特徴が出ていないからである。特徴を出そうと属性の数を増やせば、次元の呪いによって識別器の汎化性能が失われ、また、その特徴抽出には深い領域知識が必要である。
【００１９】
一方、線形識別器であるサポートベクタマシン（ＳＶＭ）は、カーネル法によって非線形識別を行うことができる非線形ＳＶＭへと拡張された。詳細は後述するが、カーネル法は元のデータ空間を高次元空間へ埋め込み、この空間で線形識別を実行する。その計算はカーネル関数と呼ばれる高次元空間上の内積を表す関数で行われ、実際には高次元へ写像することなく、高次元空間上での動作を可能にする。この仕組みはカーネルトリックと呼ばれ、カーネルトリックを用いて非線形識別関数を構成することで非線形識別を可能にするＳＶＭを非線形ＳＶＭという。そしてこの非線形ＳＶＭは、最も識別性能に優れたモデルのひとつである。
【００２０】
また、このカーネル法は近年、構造を持つデータを入力にすることができるように拡張され、これまでに木、配列、グラフ等の構造データに対するカーネル関数が提案されている。このような構造データを用いると、ベクトル形式では失われていたデータの特徴を識別に用いることができ、ベクトル形式で識別するよりも高い精度が得られている。
【００２１】
そこで、本実施の形態では、カーネル法を拡張して、データストリームを構造データと見なして識別する手法を提案する。図１は実施の形態に係る識別プロセスを表す図である。例えば、クレジットカードデータの場合、この構造データは、オンラインで到着するデータ（特徴ベクトルｘ）だけでなく、あるユーザの過去ｎ回までの履歴情報をまとめた、ひとつのストリーム構造を持つデータＸ＝｛ｘ（１），ｘ（２），・・・，ｘ（ｎ）｝である。また、このストリーム構造データに適用できるカーネル関数は、新しいデータであるほど識別の影響が大きく、古いデータほど識別の影響が小さくなるようにデータを扱い、履歴情報から得られるデータストリームの時間的な変化を特徴にする。
【００２２】
まとめると、本実施の形態は既存の手法・研究と比較して、以下の技術的特徴を有する。
・オンラインで到着するデータのみを入力として分析に用いるのではなく、過去ｎ回までの履歴をまとめたものを、ひとつのストリーム構造を持つデータとして扱い、これを入力するカーネル関数（以下、「ストリームカーネル」という。）を構築する。
・従来のベクトルを入力とした場合、すなわちオンラインで到着したデータのみを用いて、過去の履歴を用いない場合のカーネルの計算量に対して、このストリームカーネルの計算量はＯ（ｎ）である。
・大規模な実際のクレジットカードデータを用いた識別実験を行い、既存の手法よりも優れた精度であることを示す。
【００２３】
本実施の形態では二値の識別に関して述べるが、この制約は重要ではない。なぜなら、どのような二値識別器でも、多重クラスの問題へ拡張できるからである。たとえば代表的なｏｎｅ−ｖｅｒｓｕｓ−ｒｅｓｔは、Ｃ１，・・・，Ｃｋのｋ個のクラスへの識別問題においてあるクラスＣｉと、それ以外のクラス∪ｊ≠ｉＣｊとを識別する二値識別器をｋ個構築する。クラスラベルが未知のデータに対する予測は、ｋ個の識別器が一貫した出力をした場合、そのクラスへ割り当て、そうでない場合は候補の中からランダムにあるいは識別器の出力の中から最もあてはまりが良いクラスへ割り当てられる。
【００２４】
[２] 関連研究
大規模に蓄積されたデータストリームを解析し、その結果を有効に活用する研究は、データマイニング１）、情報検索、統計的学習分野２）等において長年活発に行われてきた。カーネル法３），４）は、データの非線形構造をとらえる強力な手法として注目されており、分類（ｃｌｕｓｔｅｒｉｎｇ）５）や識別（ｃｌａｓｓｉｆｉｃａｔｉｏｎ）６）等に適用され、高い精度を得ている。
【００２５】
特に識別において、線形識別器であるＳＶＭにカーネルトリックを適用し、非線形識別関数を構成することで非線形識別を可能にした非線形ＳＶＭ３）は、最も識別性能に優れたモデルのひとつである。このことは、本実施の形態について行った実際の大規模なクレジットカードデータを不正利用と正常利用に識別する実験でも示されており、本実施の形態における識別器に非線形ＳＶＭを選択した動機である。
【００２６】
しかし、データストリームを対象にした場合（ネットワーク侵入識別、優良顧客識別８）等）の識別精度は、静的なデータを対象にした場合（画像認識、テキスト識別等９））と比べると劣り、先行研究では複雑な個人情報ストリームの識別が困難であることを示している。ここで使われている多くの識別アルゴリズム（Ｋ−最近傍法、決定木、ベイジアン識別器、ニューラルネットワーク、ＳＶＭ、ロジステック回帰）の入力はベクトル形式であり、過去には識別精度を向上させるために識別に有効なベクトルの属性が考えられてきた８）。しかし、時間とともに複雑な変化をともなうデータストリームの特徴をすべてベクトルの属性で表現することは困難であり、無理に特徴を出そうとベクトルの属性数を増やせば、次元の呪いによって識別器の汎化性能は失われる。
【００２７】
本実施の形態では、従来識別器に用いてきたデータだけではなく、過去の履歴データに注目する。そして、遡って得られるデータ群をひとつのストリーム構造データとして定義し、このストリーム構造データを入力して識別を行う新しい手法を提案する。
【００２８】
まず初めに直面する課題は、どのようにして構造データを入力として扱うかということであるが、上述したカーネル法は近年、配列やグラフ等の構造データを入力にして扱えるように拡張され１２），１３）、テキスト識別等で高い識別精度を得ている１１），１４）。しかし、これらは単に構造データの共通部分構造を数え上げるものであり、次の理由でデータストリームに適用することができない：共通部分の数え上げは、部分構造が一致している数をカウントしたものである。たとえば、文字列を配列として扱う文字カーネルにおいて、ふたつの文字列“ｃａｔ”と“ｃａｒｔ”には、“ｃ，ａ，ｔ，ｃａ，ａｔ，ｃｔ，ｃａｔ”という７つの共通部分文字列がある。このようにデータ要素がすべてカテゴリデータであれば、部分構造が一致している数をカウントできる。しかし、データストリームの属性は基本的にカテゴリ属性だけで構成されているわけではなく、連続値の属性も含む。したがって、共通部分の構造の数え上げという概念を持ち込むことができない。また、従来手法はデータストリームの時間的に変化する性質を考慮していない。
【００２９】
これらの課題から、本実施の形態では構造データを扱う基礎理論である畳み込みカーネルを用いて、データストリームに適用できるカーネル法を提案する。提案手法は、新しいデータほど識別の影響を大きく、古いデータほど識別の影響を小さくするようにデータを扱い、識別を行う。これによりストリームの時間的な変化を特徴にすることができる。また、上述した配列・グラフ等の構造データに対するカーネル法が高い精度を得ていることは、本実施の形態におけるデータストリームに適用できるカーネル法を提案することで精度を向上させる根拠となる。
【００３０】
[３] カーネル法と非線形サポートベクタマシン
[３．１] カーネル法
カーネル法は、データの非線形構造をとらえる強力な手法であり、ふたつの本質的な要素からなる。
（１） データを高次元特徴空間に埋め込む。
（２） 高次元特徴空間で、線形識別アルゴリズムを適用する。
【００３１】
線形識別アルゴリズムは多く研究されているが、真の識別境界が非線形である場合、十分な性能が実現できない。そこで、カーネル法は元のデータ空間をいったん線形識別アルゴリズムを適用できる高次元空間へ写像し、この空間で線形識別アルゴリズムを適用する。しかし、カーネル法はデータを高次元特徴空間では明確に示さず、カーネル関数と呼ばれる半正定値関数Ｋ：χ×χ→Ｒを用いて、高次元特徴空間での動作を可能にする。
Ｋ（ｘ，ｚ）＝〈φ（ｘ），φ（ｚ）〉 （１）
図２はこのようなカーネル法による線形分離の様子を例示する図である。
【００３２】
Ｍｅｒｃｅｒの定理を満たす半正定値関数Ｋをカーネル関数と呼び、これはφによって写像された高次元特徴空間上での内積を意味する。このように実際に高次元特徴空間へ写像する計算を避け、入力空間でのカーネル関数を用いて高次元特徴空間上での内積を計算する仕掛けをカーネルトリックと呼ぶ。また、カーネル関数には次のようなものが知られている。
・多項式カーネル
Ｋ（ｘｉ，ｘｊ）＝（ｘｉＴｘｊ＋ｃ）ｄ （２）
・ガウスカーネル
Ｋ（ｘｉ，ｘｊ）＝ｅｘｐ（−‖ｘｉ−ｘｊ‖２／σ２） （３）
・シグモイドカーネル
Ｋ（ｘｉ，ｘｊ）＝ｔａｎｈ（ａｘｉＴｘｊ−ｂ） （４）
【００３３】
線形識別器であるＳＶＭは、上述したカーネルトリックを用いて非線形識別を行うことができる識別器へと拡張された。ＳＶＭによる識別は、異なるクラスのデータ間の距離（マージン）を最大にする超平面を考える。このときの目的関数と識別関数は、特徴ベクトルの内積のみに依存した形で記述される。たとえば識別関数は、クラスレベル変数ｔ、サポートベクタの集合Ｓ、Ｌａｎｇｒａｎｇｅ乗数αｉ＊＞０、最適な閾値ｈ＊を用いて次式で書ける。
【数１】
【００３４】
この線形識別関数は、カーネルトリックを適用することにより以下の形に書き変えることができる。
【数２】
【００３５】
ここで、元の空間よりも高次元に写像するカーネル関数Ｋを選択すれば、高次元空間上で線形ＳＶＭを実行したことになり、これは元の空間で非線形識別を実行したことと等価である。このように、カーネルトリックによって非線形識別関数を構成することで、非線形識別を可能にしたＳＶＭを、非線形ＳＶＭという。
【００３６】
また、これらカーネル関数はふたつの入力の類似度を定めていると考えることができる。すなわち、適当に類似度Ｒを定義した関数Ｋを、カーネル関数として使うことができる。したがって、上述したカーネル関数のふたつの入力ｘｉ，ｘｊがベクトルでなく、ＤＮＡ配列やテキスト等の配列、ＸＭＬやＨＴＭＬで記述された構文解析木のような木構造、あるいは化合物の分子構造のようなグラフで表現される場合にも、カーネル法を適用することができる。本実施例はストリーム構造を持ったデータ間のカーネル関数であり、これら構造を持ったデータ間のカーネルを定義するための基礎理論である畳み込みカーネルについて、以下述べる。
【００３７】
[３．２] 畳み込みカーネル
本節では、カーネル関数の入力がベクトルでなく、配列やグラフ等の構造を持ったデータに対するカーネル関数を構築するための基礎理論である畳み込みカーネルについて述べる。畳み込みカーネル１５）は、構造を持つデータ間のカーネル関数はその構造の部分構造どうしのカーネル関数によって再帰的に計算されるという考えに基づいている。
【００３８】
ｘはある構造を持つデータ、Ｓ（ｘ）はｘに含まれる部分構造の集合、ｓｘをその部分構造とする。これはｚについても同様である。Ｋｓを部分構造間のカーネル関数とすると、畳み込みカーネルは以下で表現される。
【数３】
【００３９】
また、畳み込みカーネルは部分構造ｓに対する重みｆ（ｓ｜ｘ）を用いて次のように記述することができる。
【数４】
【００４０】
この部分構造のカーネル関数Ｋｓは、更に分けられた部分構造による畳み込みカーネルにより、再帰的に表現される。つまり、構造を持ったデータｘとｚは、ここから取り出される部分構造ｓｘ∈Ｓ（ｘ）とｓｚ∈Ｓ（ｚ）のカーネル関数の値をすべて足し合わせることで全体のカーネル関数が定義される。本実施例では、ストリーム構造を持つデータＸ＝｛ｘ（１），ｘ（２），・・・，ｘ（ｎ）｝間のカーネル関数を提案する。このカーネル関数がストリームカーネルであるが、このストリームカーネルも畳み込みカーネルを基礎理論としている。
【００４１】
[４] ストリームカーネル
[４．１] ストリーム構造データの定義
データストリームに対する従来の識別手法は、オンラインで到着したデータをベクトルｘ＝（ｘ１，ｘ２，・・・，ｘｄ）で表現し、これを入力に用いる。これに対し、本実施例における識別手法は、次の特徴を持った構造データを入力に用いる。
（１） オンラインで到着したｘ（１）だけでなく、過去の履歴ｎ個のデータを持つ。
（２） ｎ個の前後のデータ間に、ｎ−１個の時間間隔を持つ。
本実施例ではこれをストリーム構造データと定義し、次のように表現する。
Ｘ＝｛ｘ（１），ｘ（２），・・・，ｘ（ｎ）｝ （１０）
【００４２】
なお、ｘ（１）が新しいデータ、ｘ（ｎ）が古いデータとし、括弧内の上付き添え字を履歴番号と呼ぶ。時間間隔とは、データが到着した時間の間隔であり、例えばｘ（１）とｘ（２）との時間間隔はｔ[１，２]と表す。図３はストリーム構造データの構成図である。
【００４３】
ここで、時間間隔を計算に用いる上で注意すべきことがある。時間間隔は、後述するように、古い情報ほど識別の影響を小さくする重みを計算するときに用いられるが、このとき、遡った期間全体を１に正規化する。つまり、たとえばｎ＝４とし、過去の履歴４件を遡る場合、得られる時間間隔は、ｔ[１，２]、ｔ[２，３]、ｔ[３，４]であり、その合計をｔ[１，２]＋ｔ[２，３]＋ｔ[３，４]＝１となるように値を変換する。これは単に、各時間間隔についての、遡った期間全体に対する比を考えるだけである。たとえばクレジットカードデータを考えると、クレジットカードを１週間に１度の間隔で使う人もいれば、１カ月に１度の間隔で使う人もいる。時間間隔を正規化することで、各人それぞれの利用の間隔を同じ尺度でとらえることができる。
【００４４】
[４．２] 部分構造間のカーネル
本実施例におけるストリームカーネルは前述した畳み込みカーネルが基本理論となっている。したがって、まず前述したストリーム構造データＸ＝｛ｘ（１），ｘ（２），・・・，ｘ（ｎ）｝の部分構造ｓを定義する。例として、遡る履歴の数をｎ＝３としたＸ＝｛ｘ（１），ｘ（２），ｘ（３）｝の場合について考える。Ｘの部分構造全体の集合をＳ（Ｘ）とすると、順序関係を考慮して、Ｓ（Ｘ）は以下の６つの部分構造へ分割される。このとき、遡る履歴の数ｎに対して、得られる部分構造の数はｎ（ｎ＋１）／２である。
Ｓ（Ｘ）＝｛ｓ１，ｓ２，ｓ３，ｓ４，ｓ５，ｓ６｝
＝｛｛ｘ（１）｝，｛ｘ（２）｝，｛ｘ（３）｝，｛ｘ（１），ｘ（２）｝，｛ｘ（２），ｘ（３）｝，｛ｘ（１），ｘ（２），ｘ（３）｝｝
【００４５】
次に、分割された部分構造のカーネルの組合せを考える。ここで、異なる履歴番号で観測されたデータが独立であるとする。すなわち、Ｋ（ｘ（ｉ），ｚ（ｊ））＝０，ｉ≠ｊとし、部分構造間のカーネルを、部分構造に含まれるデータのカーネルの積で表現する。すると、部分構造のデータ数が同じで，かつ履歴番号が同じであるときのみ、その部分構造どうしのカーネルＫｓは計算され、次式で表される。
【数５】
【数６】
【００４６】
なお、Ｋ（ｘ（ｉ），ｚ（ｉ））は前述した半正定値カーネルである。これにより、考えるべきカーネルの組合せはｎ（ｎ＋１）／２通りとなる。
【００４７】
[４．３] 部分構造の重み
次に、畳み込みカーネルにおける部分構造の重みｆ（ｓ｜Ｘ）を定義する。このｆ（ｓ｜Ｘ）は前述した部分構造のカーネルが、全体の類似度にどれほどの影響力を持つかを表す。これを考えるうえで、理解が単純になるよう再度クレジットカードデータの例を用いる。
【００４８】
オンラインで到着した顧客ＡのデータをｘＡ（１）とすると、この利用ｘＡ（１）が正常利用か、不正利用かを識別するために、顧客Ａの利用履歴を過去ｎ回遡ったストリーム構造データＸＡ＝｛ｘＡ（１），ｘＡ（２），・・・，ｘＡ（ｎ）｝を得る。ｘＡ（１）が新しいデータ、ｘＡ（ｎ）が古いデータとすると、ｘＡ（１）とｘＡ（ｎ）とを同じ重みで扱うと正確な識別を行うことができない。なぜなら、知りたいのは到着したデータｘＡ（１）が不正利用か、正常利用かということである。古いデータがいくら正常利用らしくても、到着したデータが明らかに不正利用らしければ、到着したデータの方を優先すべきである。したがって、新しいデータを含む部分構造であるほど重み（影響度）を大きく、古いデータを含む部分構造であるほど重みを小さくする。この重みｆ（ｓ｜Ｘ）は、前述した時間間隔ｔと、新たに導入するパラメータλ∈（０，１）とを用いた単調減少関数λｔによって定義される。
【００４９】
ここで、部分構造に含まれるそれぞれのデータに対して具体的に重みを与える。すなわちｎ番目の履歴データに対して、重みを
【数７】
と定義する。例として、ｓｘ＝｛ｘ（２），ｘ（３），ｘ（４）｝とｓｚ＝｛ｚ（２），ｚ（３），ｚ（４）｝の重みｆ（ｓｘ｜Ｘ）とｆ（ｓｚ｜Ｚ）とを求める。部分構造ｓｘに含まれるデータそれぞれの重みを表１に示す。
【表１】
なお、ｔｘは、ストリーム構造データＸが持つ時間間隔であるとし、記述の簡略化のため、
【数８】
とする。このｘをすべてｚで置き換えれば、同様に部分構造ｓｚに含まれるデータそれぞれの重みを表す。簡略化せずに重みを詳細に記述すれば、ｆ（ｓｘ｜Ｘ）とｆ（ｓｚ｜Ｚ）はそれぞれ次式で表される。
【数９】
【数１０】
【００５０】
したがって、このときの部分構造の重みを含めたカーネルは式（１１）を用いて、
【数１１】
となる。
【００５１】
[４．４] ストリームカーネル計算アルゴリズム
Ｋｎ（Ｘ，Ｚ）と、ＸとＺとがともに過去ｎ件のストリーム構造データからなるときのストリームカーネルとする。また、過去ｎ件からなるＸに、さらにもう１件遡って得られるｘ（ｎ＋１）が、Ｘに付与されることをＸｘ（ｎ＋１）と表現する。もちろんこれはＺについても同様であるが、以降はＺにも同じ作業を与えたとして、その記述は省略する。
【００５２】
ここで具体的に、例としてｎ＝１の場合から考える。このとき、ＸはＸ＝｛ｘ（１）｝であり、Ｓ（Ｘ）＝｛ｓ１｝＝｛ｘ（１）｝である。したがって、単純にＫ１（Ｘ，Ｚ）は次で表される。
Ｋ１（Ｘ，Ｚ）＝Ｋ（ｘ（１），ｚ（１）） （１５）
【００５３】
次に、Ｘ＝｛ｘ（１）｝にｘ（２）が付与され、Ｘｘ（２）＝｛ｘ（１），ｘ（２）｝となったときのＫ２（Ｘｘ（２），Ｚｚ（２））を考える。Ｘｘ（２）＝｛ｘ（１），ｘ（２）｝により、前述と同様の手法で、Ｘｘ（２）は３つの部分構造に分割できる。
Ｓ（Ｘｘ（２））＝｛ｓ１，ｓ２，ｓ３｝
＝｛｛ｘ（１）｝，｛ｘ（２）｝，｛ｘ（１），ｘ（２）｝｝
【００５４】
式（９）、（１１）、（１４）により、Ｋ２（Ｘｘ（２），Ｚｚ（２））は次式で記述できる。なお、数式の簡略化のため、ｔｘ[ｉ，ｉ＋１]＋ｔｚ[ｉ，ｉ＋１]＝Ｔ[ｉ，ｉ＋１]とする。
Ｋ２（Ｘｘ（２），Ｚｚ（２））＝Ｋ（ｘ（１），ｚ（１））＋λＴ[１，２]Ｋ（ｘ（２），ｚ（２））＋λＴ[１，２]Ｋ（ｘ（１），ｚ（１））Ｋ（ｘ（２），ｚ（２）） （１６）
【００５５】
ここで、式（１５）と式（１６）とを比較し、ｘ（２）が付与されることで増加するカーネルの量を計算する。この量をＪ２とすると、Ｊ２は次のようにＪ１を用いた形で書くことができる。
Ｊ２＝Ｋ２（Ｘｘ（２），Ｚｚ（２））−Ｋ１（Ｘ，Ｚ）
＝λＴ[１，２]Ｋ（ｘ（２），ｚ（２））＋λＴ[１，２]Ｋ（ｘ（１），ｚ（１））Ｋ（ｘ（２），ｚ（２））
＝λＴ[１，２]Ｋ（ｘ（２），ｚ（２））｛１＋Ｋ（ｘ（１），ｚ（１））｝
＝λＴ[１，２]Ｋ（ｘ（２），ｚ（２））｛１＋Ｊ１｝ （１７）
【００５６】
同様に、Ｘ＝｛ｘ（１），ｘ（２）｝にｘ（３）を付与した場合を展開しても、ｘ（２）が付与されることで増加するカーネルの量Ｊ３もまた、Ｊ２を用いた形で書くことができる。したがって、遡るデータがひとつ増えることで、全体のカーネルに加えられる部分構造のデータのカーネルの量をＪｎとすると、ストリームカーネルは以下のように一般化した形で、再帰的に表現することができる。
Ｋｎ（Ｘｘ（ｎ），Ｚｚ（ｍ））＝Ｋｎー１（Ｘ，Ｚ）＋Ｊｎ （１８）
【数１２】
ただし、Ｋ０（Ｘ，Ｚ）＝１、Ｊ１＝Ｋ（ｘ（１），ｚ（１））である。
【００５７】
動的計画法を用いることにより、この計算量は遡るデータ数ｎに対してＯ（ｎ）で済む。また、ＸとＺのデータ数が異なる場合、このままでは、データ数が少ない部分集合のカーネルのみを考えてしまう。たとえば、Ｘ＝｛ｘ（１），ｘ（２），ｘ（３）｝，Ｚ＝｛ｚ（１），ｚ（２）｝とすると、ｘ（３）はカーネルの計算にまったく用いられない。そこで、以下の式で正規化を行い、これをストリームカーネルの最終出力値とする。
【数１３】
【００５８】
さらに、このストリームカーネルが半正定値性を満たすことを述べる。いくつかの半正定値性を満たすカーネル関数は、これを足し合わせたり、掛け合わせたり、また定数倍したりしたものもまた、半正定値性を満たすカーネル関数となることが知られている。ストリームカーネルは、半正定値性を満たすカーネル関数を基本として用い、部分構造どうしのカーネルの計算ではこのカーネルを掛け合わせ、部分構造の重みはカーネルを定数倍し、畳み込みで表現された構造全体のカーネルはこれらを足し合わせたものである。したがって，ストリームカーネルは半正定値性を満たす。
【００５９】
[５] 実験評価
本実施例では、実際のデータストリームであるクレジットカードデータ（実験データの詳細は後述する。）に対して、ガウスカーネルを用いた通常のＳＶＭと、本実施例のストリームカーネルＳＶＭ（以下、「ＳＫＳＶＭ」という。）を適用し，正常利用と不正利用に識別した。また、その性能を以下の点から比較した：
（ａ） 学習・検証にかかる時間
（ｂ） 識別の精度（正答率）
（ｃ） モデルの性能（ＣＡＰ曲線）
【００６０】
[５．１] 実験準備
実験は２ＧＨｚのＣＰＵと、３ＧＢのメモリを持つハードウェア環境を使用した。本実施例に係るＳＫＳＶＭは、ＯＳＳであるｓｖｍ−ｌｉｇｈｔ１６）（Ｃ言語）上で実装を行った。
【００６１】
実験で使用したカーネル関数は、ガウスカーネルＫ（ｘｉ，ｘｊ）＝ｅｘｐ（−‖ｘｉ−ｘｊ‖２／σ２）である。ガウスカーネルは、パラメータσの設定によってはシグモイドカーネルようにも動作し、また、先行研究で行った実験結果により、ガウスカーネルが識別に最も有効に動作すると判断した。ガウスカーネルのパラメータσは、事前に‖ｘｉ−ｘｊ‖２の統計を取り、これらが適切にＫ（ｘｉ，ｘｊ）∈（０，１）を得るような範囲を確定し、ＳＶＭの正則化パラメータＣとともに試行錯誤的に決定した。
【００６２】
ストリームカーネルのパラメータλは、一番最近のデータのカーネル関数の値が、ストリームカーネル全体の影響の７割程度を占めるように設定した。これは、過去の情報の重みを大きくしすぎてしまうと、一番重要な最近のデータの特徴が埋もれてしまうためである。また、顧客の遡る履歴数ｎは、ｎ＝５に設定した。これら実験で用いたパラメータを表２に示す。
【表２】
【００６３】
本実施例ではモデルの性能をＣＡＰ曲線によって評価するため、新たにスコア値という考えを導入している。スコア値とは、値が高いものほど不正利用であるらしく、逆に値が低いものほど正常利用であるらしいという指標である。具体的には、ＳＶＭの出力ｙに対して、スコア値ｓｃｏｒｅは以下の式で１〜１０００の値で出力される。
【数１４】
【００６４】
[５．２] 実験データ
本実験で用いたデータセットは、実際のクレジットカードデータである。クレジットカードデータは、約２年分のデータが用意されており、そのデータ量は約１ＴＢに及ぶ。クレジットカードデータの属性は、大きく次の２つのグループに分類される。
（ａ） オーソリデータ属性： 利用時の状況を記述した属性
（ｂ） 振舞いデータ属性： 顧客の行動パターンを記述した属性
【００６５】
属性（ａ）は、単にクレジットカードの取引データ（以下、「オーソリデータ」という。）の属性である。たとえばこの属性には、顧客ＩＤ、生年月日、利用時間、利用金額、購入商品コード等があり、計８４属性からなる。しかし、これらの属性には識別に有効な（不正利用と正常利用で、はっきり値が異なるような）属性は少ない。したがって、この属性だけを用いて識別アルゴリズムを適用しても高い精度は得られない。そこで、識別の特徴として貢献するような以下の属性（ｂ）を、人工的に作成する。
【００６６】
属性（ｂ）は過去の履歴情報から作成した顧客モデル（過去の利用金額の平均や分散、過去の利用時間帯の頻度等）との乖離値であり、顧客の行動パターンを記述した属性である。たとえばある人が高額な買い物をしたとする。その人が前回も同程度の額の買い物をしていたならば、その利用は本人、すなわち正常利用らしいが、逆に前回低額な買い物をしていたならば、第三者利用、すなわち不正利用である可能性があると判断することができる。図４は振舞い属性を考慮した識別を表す図である。
【００６７】
このように顧客モデルに基づいてその顧客の行動パターンの時間的変化に注目することは、クレジットカードの領域だけでなく、ネットワーク侵入や個人認証等、他の多くの領域・データにあてはまり、有用である。この属性（ｂ）には「前回利用時間との差」、「前回利用金額との差」、「過去６カ月の曜日ごとの利用回数との比較」等があり、計４０属性からなる。本実験で用いたクレジットカードデータセットは属性（ａ）と属性（ｂ）とから５５属性を分析に用いた。データセットの詳細を表３に示す。
【表３】
【００６８】
ＳＫＳＶＭとＳＶＭの学習・検証データの違いは、利用時点から過去ｎ回の履歴があるか、ないかである。ＳＫＳＶＭの学習・検証データは、図５で示すように、上述した顧客モデルを更新しながら属性（ｂ）を作成して、ストリームデータ構造を作成する。本実験では、ｎ＝５とし過去５回の履歴を遡ってストリーム構造データを作成し、識別を行う。
【００６９】
クレジットカードデータを、ストリーム構造データとして扱ううえでの注意すべき点として、顧客のマスタ情報を繰り返し用いることがあげられる。たとえば、顧客の「性別」等属性を分析に用いるとする。すると、過去２件目、３件目にも同じ性別の属性が、繰り返し入ることになる。一見これはデータの冗長性から無駄のように見えるが、これらは全て必要である。なぜなら、冗長性のある「性別」という属性を１件目だけに用いて、それ以降の過去２件目、３件目には用いない場合を考える。そしてもし、その「性別」という属性が、不正利用につながる重要な属性であるとすれば、部分集合間のカーネルを考える際、不十分な情報で過去の履歴を処理してしまい、全体として、特徴が薄れてしまうためである。
【００７０】
[５．３] 実験結果と考察
[５．３．１] 学習と検証の時間
通常のＳＶＭと、ＳＫＳＶＭの学習時間・検証時間の比較を表４で示す。表４における数字の単位は秒である。実験の結果、学習時間・検証時間ともに、本実施例の手法は通常のＳＶＭと比べて約１０倍の時間がかかった。ＳＫＳＶＭのカーネルの計算量は、通常のＳＶＭのカーネルの計算量に比べ、理論上では遡る履歴の数ｎに対してＯ（ｎ）で増加するものの、実際のデータでは欠損値の場合の処理、時間間隔データの変換等の事前計算処理が必要であるため、表４に示した結果はこれらオーバーヘッドを含んだものである。
【表４】
【００７１】
次に、通常のＳＶＭと、ＳＫＳＶＭのモデルの大きさであるサポートベクタ（ＳＶ）の数の比較を表５で示す。これは式（７）において検証の際に計算を繰り返す数を表している。したがって、ＳＶの数が少なければ、より少ない計算量で検証を行うことができることを示し、また、スパースな解が得られていることになる。表５で示すように、ＳＫＳＶＭの方がよりスパースな解を得ていることが分かる。
【表５】
【００７２】
[５．３．２] 識別の精度（正答率）
識別の精度を評価する指標には、一般に適合率（ｐｒｅｃｉｓｉｏｎ）と再現率（ｒｅｃａｌｌ）が用いられる。しかし、本実験で用いた実際のクレジットカードデータは、不正利用の数が正常利用の数に比べて約０．０２％と極端に少なく、また、識別能力の弱い識別器を用いるとすべてを正常利用であると判断してしまうほど、正常利用と不正利用との識別は困難である。したがって、適合率と再現率はともに数％という値しか取ることができず、実際のクレジットカードデータを不正利用と正常利用に識別するというこの領域においては、これらの指標は適当ではない。
【００７３】
本実施例にかかるＳＫＳＶＭによる識別精度の向上を明確にするため、本実験の識別精度は正答率で評価する。正答率は、識別を行った全件（７２０，９２０件）に対し、その識別結果が正しかった件数の割合である。表６と表７で示すように、ＳＶＭの正答率が９９．８２％であったのに対し、ＳＫＳＶＭの正答率は９９．８９％であり、０．０７％向上している。
【００７４】
割合からはそれほどの向上は見られないが、これは大きな変化である。表６において、ＳＶＭが不正利用であると判断した件数は、１１１０件である。しかし、そのうち１０８０件は実際には正常利用であり、これは間違った識別である。一方、表７において、ＳＫＳＶＭが不正利用であると判断した件数は５８６件である。これはＳＶＭと比べると約半分のヒット件数であるにもかかわらず、実際に不正利用であった件数は変わらない（３０件と２８件）。検証データとして用いたデータセットは不正利用の数が少ないため、この変化は割合として大きく現れないが、実際にはＳＫＳＶＭは不正利用データを発見するときのノイズを半分に減らしていることが分かる。
【表６】
【表７】
【００７５】
[５．３．３] ＣＡＰ曲線による比較
ＣＡＰ（Ｃｕｍｕｌａｔｉｖｅ Ａｃｃｕｒａｃｙ Ｐｒｏｆｉｌｅｓ）曲線は、予測モデルの性能を評価するのに用いられ、実際のクレジットカード業界でも使用されている。横軸は、不正利用である確率（スコア値）が高いと識別器が判断したクレジットカードデータを順に並べた数であり、縦軸は、その中で実際に不正利用であった顧客の人数である。図６は、通常のＳＶＭと、ＳＫＳＶＭのＣＡＰ曲線による比較を示している。また、図７はＣＡＰ曲線の見方を説明する図である。もし得られた曲線が、図７で示すＣに近いならば、スコア値はランダムにつけられたものと等価であり、モデルにまったく説明力がないことを示す。対称的に、得られた曲線がＡに近いならば、実際に不正利用であるクレジットカードデータに対して高いスコア値をつけられていることになり、モデルの性能が高いことを示す。実際にはＡとＣとの間の、Ｂのような曲線を取る。
【００７６】
図６から、ＳＫＳＶＭは不正らしい上位５００件を監視すれば、１５人の不正利用者を検知できていることを示している。これに対し、ＳＶＭは同様に不正らしい上位５００件を監視しても、約半数の８人の不正利用者しか検知できていない。さらに、ＳＫＳＶＭが不正らしい上位５００件を監視するだけで検知できる１５人の不正利用者を、ＳＶＭが検知しようとすれば、不正らしい上位１，０００件（ＳＫＳＶＭの場合の倍）もの監視をしなければならないと言うことも示している。
【００７７】
[６] 参考文献
1) McCarthy, J.: PHENOMENAL DATA MINING: FROM DATA TO PHENOMENA, ACM SIGKDD Explorations, Vol.1, No.2, pp.24-29, (2000).
2) Martin, H.C.L., Zhang, N. and Anil, K.J.: Nonlinear Manifold Learning For Data Stream, Proc. SIAM International Conference for Data Mining, pp.33-44 (2004).
3) Scholkopf, B. and Smola, A.J.: Learning with Kernels, MIT Press (2002)
4) Shawe-Taylor, J. and Cristianini, N.: Kernel Methods for Pattern Analysis, Cambridge University Press (2004).
5) Jain, A., Zhang, Z. and Chang, E.Y.: Adaptive non-linear clustering in data streams, CIKM '06: Proc. 15th ACM International Conference on Information and Knowledge Management, New York, NY, USA, pp.122-131, ACM (2006).
6) Milenova, B.L., Yarmus, J.S. and Campos, M.M.: SVM in Oracle Database 10g: Removing the Barriers to Widespread Adoption of Support Vector Machines, VLDB '05: Proc. 31st International Conference on Very Large Data Bases, VLDB Endowment, pp.1152-1163 (2005).
7) 都築 学、小西 修、新美礼彦：カーネル法による現象データマイニング、電子情報通信学会第１８回データ工学ワークショップ（２００６）.
8) 鈴木秀男、水野 誠、住田 潮、佐治 明：ＣＲＭのための優良顧客識別手法の特性評価と財務効果、Department of Social Systems and Management Discussion Paper Series, No.1123 (2005).
9) Hoi, S.C.H., Jin, R. and Lyu, M.R.: Large-scale text categorization by batch mode active learning, WWW '06: Proc. 15th International Conference on World Wide Web, pp.633-642, ACM (2006).
10) Komarek, P. and Moore, A.: Making Logistic Regression A Core Data Mining Tool: A Practical Investigation of Accuracy, Speed, and Simplicity, Technical report, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA (2005).
11) Joachims, T.: Text categorization with support vector machines: Learning with many relevant features, Proc. European Conference on Machine Learning (ECML'98), pp.137-142 (1998).
12) 鹿島久嗣:カーネル法による構造データマイニング、情報処理、Vol.46, No.1, pp.27-33 (2005).
13) 津田宏治：カーネル設計の技術、情報論的学習理論ワークショップ（IBIS2002）, pp.1-10 (2002).
14) Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N. and Watkins, C.: Text classification using string kernels, Journal of Machine Learning Research, Vol.2, pp.419-444 (2002).
15) Haussler, D.: Convolution Kernels on Discrete Structures, Technical report, UC Santa Cruz (1999).
16) Joachims, T.: SVM-Light Support Vector Machine. http://svmlight.joachims.org/
【００７８】
［具体例］
実施の形態
図８は、実施の形態に係る情報処理装置１００の全体構成を表す図である。これらの構成は、ハードウェア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。
【００７９】
情報処理装置１００は、学習部１０と識別部１２とを含む。学習部１０はさらに、教師データ格納部１４、ストリームカーネル学習部１６、識別器格納部１８を含む。また、識別部１２はさらに、ストリーム構造データ識別部２０、ストリームデータ格納部２２、出力部２４を含む。
【００８０】
本実施の形態に係る情報処理装置は、あらかじめ機械学習手法であるストリームカーネルＳＶＭによって識別器を作成しておき、その識別器に基づいてオンラインで到着するデータの属するクラスを判別するという構造を持つ。そこで、まずストリームカーネルＳＶＭによる学習過程について説明する。
【００８１】
教師データ格納部１４は機械学習に用いるためのデータを格納する部分である。教師データとは、そのデータの属するクラスが既知であるデータの集合のことである。たとえば、クレジットカードの取引データについて、その取引が正常利用であるのか不正利用であるのかの二値に分類する問題を考える。このとき、教師データとは、その取引が正常利用か不正利用であるかが既知であるデータの集合である。
【００８２】
ストリームカーネル学習部１６は、教師データ格納部１４から受け取った教師データに基づいてストリーム構造データを構築し、ストリームカーネルＳＶＭを用いて機械学習により識別器を作成する部分である。これは主に前提技術[４]に記載の技術に基づいて作成したストリームカーネルを使って前提技術[３]に記載の非線形ＳＶＭにより学習する。
【００８３】
識別器格納部１８はストリームカーネル学習部１６が出力した学習結果である識別器を格納する部分である。
【００８４】
ストリーム構造データ識別部２０は、過去の履歴データと、ストリームデータ格納部２２から受け取るオンラインで到着したデータとからストリーム構造データを構築し、識別器格納部１８から受け取った識別器に基づいて、当該オンラインで到着したデータのクラスを識別する部分である。これは主に前提技術[４]に記載の技術に基づくものである。出力部２４はストリーム構造データ識別部２０が識別した結果を図示しないモニタ等の出力ディバイスやストレージ等に出力する。
【００８５】
図９はストリームカーネル学習部１６の構成図である。ストリームカーネル学習部１６は履歴数入力部２６、教師ストリーム構造データ作成部２８、教師ストリームカーネル作成部３０、機械学習部３２を含む。
【００８６】
履歴数入力部２６はストリーム構造データを作成するに際し、過去何回までの履歴をまとめるかについての情報を入力する部分である。ユーザが任意の回数を自由に入力できるようにしても良いし、例えば５回のように固定されていても良い。教師ストリーム構造データ作成部２８は、履歴数入力部２６から参照すべき過去の履歴回数を受け取り、ストリーム構造データを作成する部分である。ストリーム構造データは前提技術[４．１]に記載の構造のデータであるが、ここではさらに、おのおののデータが正常利用であるか不正利用であるかの情報をも付与された教師データとして作成される。
【００８７】
教師ストリームカーネル作成部３０は、教師ストリーム構造データ作成部２８から教師ストリーム構造データを受け取り、ＳＶＭの学習に供すべき教師ストリームカーネルを作成する部分である。詳細は後述するが、これは前提技術[４．２]、[４．３]、[４．４]に記載のアルゴリズムに基づく。
【００８８】
機械学習部３２は、教師ストリームカーネル作成部３０が作成した教師ストリームカーネルを用いてＳＶＭの学習を行う部分である。ＳＶＭは前提技術[３．１]に記載の非線形識別アルゴリズムに基づく。
【００８９】
図１０は教師ストリームカーネル作成部３０の構成図である。教師ストリームカーネル作成部３０は時間間隔正規化部３４、ストリームカーネル作成部３６、カーネル正規化部３８を含む。
【００９０】
時間間隔正規化部３４は、教師ストリーム構造データ作成部２８から受け取ったストリーム構造データに含まれる履歴の発生日時を参照して、各履歴間の時間間隔を正規化する部分である。これは前提技術[４．１]に記載のアルゴリズムに基づくものであり、その目的はデータによって異なる履歴の発生間隔を正規化して、それぞれの履歴の発生間隔を同じ尺度でとらえることである。
【００９１】
ストリームカーネル作成部３６は、教師ストリーム構造データ作成部２８から受け取った教師ストリーム構造データと時間間隔正規化部３４から受け取った正規化された時間間隔とを受け取って、ストリームカーネルを計算する部分である。これは前提技術[４．４]に記載のアルゴリズムに基づくものである。式（１８）、式（１９）で表されるように、ストリームカーネルは漸化式を用いて表現できるため、動的計画法を適用することでストリームカーネル生成の計算量を抑制することができる。
【００９２】
カーネル正規化部３８は、ストリームカーネル作成部３６が作成したカーネルを正規化する部分である。これは、ストリームカーネルの計算に用いるストリーム構造データＸとＺとの履歴数が異なる場合には、履歴数の少ない部分集合のカーネルのみとなるため、前提技術[４．４]の式（２０）を用いて是正するものである。
【００９３】
図１１はストリームカーネルを作成する処理の流れを表す。ステップＳ１０およびステップＳ１２は前提技術[４．４]に記載の漸化式（１８）、（１９）を計算するための初期値を設定する。具体的には、まずＫ０（Ｘ，Ｚ）の値を１に設定し（Ｓ１０）、Ｊ１の値をＫ（ｘ（１），ｚ（１））に設定する（Ｓ１２）。ここで、Ｋ（ｘ（１），ｚ（１））としては、たとえば前提技術[３．１]における式（３）に示すガウスカーネルを用いる。次に、ループ変数ｉを１に初期化する（Ｓ１４）。
【００９４】
ステップＳ１６はループの終了を判断するステップである。具体的には、ループ変数ｉの値が遡る履歴回数ｎ以下の場合にはステップＳ１８に進む（Ｓ１６Ｙ）。そうでない場合にはループを終了し、ステップＳ２４に進む（Ｓ１６Ｎ）。
【００９５】
ステップＳ１８からステップＳ２２は、前提技術[４．４]に記載の漸化式（１８）、（１９）を用いて、順次更新することによりストリームカーネルを生成するステップである。まず式（１８）に基づき、Ｋｉ（Ｘｘ（ｉ），Ｚｚ（ｉ））をＪｉとＫｉ−１（Ｘ，Ｚ）との和により求める（Ｓ１８）。例えばｉ＝１の場合にはＫ１（Ｘｘ（１），Ｚｚ（１））＝Ｋ０（Ｘ，Ｚ）＋Ｊ１となるが、右辺はそれぞれ前述のステップＳ１０およびＳ１２において定められている。結局、Ｋ１（Ｘｘ（１），Ｚｚ（１））＝Ｋ（ｘ（１），ｚ（１））となる。
【００９６】
次に、式（１９）に基づき、Ｊｉ＋１をＪｉ、Ｋ（ｘ（ｉ＋１），ｚ（ｉ＋１））および前提技術[４．３]のアルゴリズムに基づいて求めた重みを用いて求める（Ｓ２０）。例えばｉ＝１の場合にはＪ２＝（１＋Ｊ１）Ｋ（ｘ（２），ｚ（２））λＴ［１，２］となる。ここで、Ｊ１はステップＳ１２において定められており、Ｋ（ｘ（２），ｚ（２））は例えば前提技術[３．１]における式（３）のガウスカーネルを用いれば計算できる。またλＴ［１，２］は前提技術[４．３]のアルゴリズムに基づき、時間間隔正規化部３４であらかじめ計算しておいたデータを用いればよい。
【００９７】
ステップＳ１８およびステップＳ２０によりＫｉ（Ｘｘ（ｉ），Ｚｚ（ｉ））およびＪｉ＋１が更新できたので、ループ変数ｉをｉ＋１に更新し、ステップＳ１６に戻る（Ｓ２２）。ループ変数ｉがｎ以下の間、以上のループを回すことにより、ストリームカーネルＫｎ（Ｘ，Ｚ）を漸化式を用いて順に更新することができる。こうして得られたストリームカーネルＫｎ（Ｘ，Ｚ）を出力し（Ｓ２４）、終了する。
【００９８】
以上ストリーム構造データをＳＶＭで扱うためのストリームカーネルの作成方法について説明した。ストリームカーネルを用いることにより、あるひとつのストリーム構造データから対応するひとつのストリームカーネルの出力値を得ることができる。この出力値を用いれば従来のＳＶＭによる機械学習を行うことができる。このように、ストリームカーネルの出力値を用いて従来のＳＶＭによる機械学習を行うことがストリームカーネルＳＶＭである。
【００９９】
次に、ストリームカーネルＳＶＭの学習結果である識別器を用いて、オンラインで到着するデータがどのクラスに属するかを識別する方法について説明する。
【０１００】
図１２はストリーム構造データ識別部２０の構成図である。ストリーム構造データ識別部２０はストリーム構造データ構築部４０、識別用ストリームカーネル作成部４２、識別部４４を含む。
【０１０１】
ストリーム構造データ構築部４０は、ストリームデータ格納部２２からオンラインで到着したデータを受け取り、当該データを含め過去ｎ回までの履歴データを基にストリーム構造データを構築する部分である。これにより、オンラインで到着するデータのみならず、過去ｎ回までの履歴を入力として識別することが可能となる。これは主に前提技術[４．１]〜[４．３]に記載のアルゴリズムに基づく。
【０１０２】
識別用ストリームカーネル作成部４２は、識別器格納部１８から識別器と、ストリーム構造データ構築部４０で構築されたオンラインで到着したデータを含むストリーム構造データとを受け取り、識別用のストリームカーネルを作成する部分である。識別器には複数のストリーム構造データがサポートベクタとして含まれている。これらのサポートベクタを例えば前提技術[４．１]〜[４．４]に記載のアルゴリズムのＺとし、ストリーム構造データ構築部４０で構築されたストリーム構造データをＸとすれば、識別用のストリームカーネルを構築することができる。
【０１０３】
識別部４４は、識別用ストリームカーネル作成部４２で作成された識別用のストリームカーネルに基づき、オンラインで到着したデータの属するクラスを識別する部分である。具体的には、前提技術[３．１]に記載の式（７）におけるＫ（ｘｉ，ｘ）を前記ストリームカーネルに置換し、その出力値の正負によってふたつのクラスに識別すればよい。
【０１０４】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【符号の説明】
【０１０５】
１０ 学習部、 １２ 識別部、 １４ 教師データ格納部、 １６ ストリームカーネル学習部、 １８ 識別器格納部、 ２０ ストリーム構造データ識別部、 ２２ ストリームデータ格納部、 ２４ 出力部、 ２６ 履歴数入力部、 ２８ 教師ストリーム構造データ作成部、 ３０ 教師ストリームカーネル作成部、 ３２ 機械学習部、 ３４ 時間間隔正規化部、 ３６ ストリームカーネル作成部、 ３８ カーネル正規化部、 ４０ ストリーム構造データ構築部、 ４２ 識別用ストリームカーネル作成部、 ４４ 識別部、 １００ 情報処理装置。
【特許請求の範囲】
【請求項１】
過去履歴の参照範囲を履歴数として入力する履歴数入力部と、
属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる教師ストリーム構造データ作成部と、
教師ストリーム構造データに基づいて教師ストリームカーネルを作成する教師ストリームカーネル作成部と、
教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する機械学習部とを含むことを特徴とする学習装置。
【請求項２】
前記教師ストリームカーネル作成部は、前記履歴数個のデータのうち最新のデータと最古のデータとの時間間隔に基づいて前記履歴数個のデータ間の時間間隔を正規化する時間間隔正規化部を含むことを特徴とする請求項１に記載の学習装置。
【請求項３】
前記教師ストリームカーネル作成部は、前記正規化された時間間隔に基づいて、前記教師ストリーム構造データの各部分構造が持つストリームカーネルに対する寄与率を定めることを特徴とする請求項２に記載の学習装置。
【請求項４】
前記教師ストリームカーネル作成部は、前記教師ストリーム構造データの各部分構造のカーネル関数と前記寄与率との積の総和をストリームカーネルとして出力することを特徴とする請求項３記載の学習装置。
【請求項５】
前記教師ストリームカーネル作成部は、前記履歴数個のうち古いデータほど前記寄与率を小さく設定することを特徴とする請求項３または４に記載の学習装置。
【請求項６】
前記機械学習部は、前記履歴数個のデータ間で時間の経過とともに変化しうる情報を識別のための特徴ベクトルとして学習することを特徴とする請求項１から５のいずれかに記載の学習装置。
【請求項７】
オンラインで受け取ったデータと当該データの過去履歴とから識別用ストリーム構造データを構築するストリーム構造データ構築部と、
前記識別用ストリーム構造データと、教師ストリームカーネルの値を機械学習することにより得られた識別器とを用いて識別用ストリームカーネルを作成する識別用ストリームカーネル作成部と、
識別用ストリームカーネルの出力値に基づいて当該データの属するクラスを識別する識別部とを含むことを特徴とするクラス識別装置。
【請求項８】
過去履歴の参照範囲を履歴数として入力するステップと、
属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめるステップと、
教師ストリーム構造データに基づいて教師ストリームカーネルを作成するステップと、
教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成するステップとをプロセッサに実行させることを特徴とする学習方法。
【請求項９】
過去履歴の参照範囲を履歴数として入力する機能と、
属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる機能と、
教師ストリーム構造データに基づいて教師ストリームカーネルを作成する機能と、
教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する機能とをコンピュータに実現させることを特徴とするプログラム。
【請求項１】
過去履歴の参照範囲を履歴数として入力する履歴数入力部と、
属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる教師ストリーム構造データ作成部と、
教師ストリーム構造データに基づいて教師ストリームカーネルを作成する教師ストリームカーネル作成部と、
教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する機械学習部とを含むことを特徴とする学習装置。
【請求項２】
前記教師ストリームカーネル作成部は、前記履歴数個のデータのうち最新のデータと最古のデータとの時間間隔に基づいて前記履歴数個のデータ間の時間間隔を正規化する時間間隔正規化部を含むことを特徴とする請求項１に記載の学習装置。
【請求項３】
前記教師ストリームカーネル作成部は、前記正規化された時間間隔に基づいて、前記教師ストリーム構造データの各部分構造が持つストリームカーネルに対する寄与率を定めることを特徴とする請求項２に記載の学習装置。
【請求項４】
前記教師ストリームカーネル作成部は、前記教師ストリーム構造データの各部分構造のカーネル関数と前記寄与率との積の総和をストリームカーネルとして出力することを特徴とする請求項３記載の学習装置。
【請求項５】
前記教師ストリームカーネル作成部は、前記履歴数個のうち古いデータほど前記寄与率を小さく設定することを特徴とする請求項３または４に記載の学習装置。
【請求項６】
前記機械学習部は、前記履歴数個のデータ間で時間の経過とともに変化しうる情報を識別のための特徴ベクトルとして学習することを特徴とする請求項１から５のいずれかに記載の学習装置。
【請求項７】
オンラインで受け取ったデータと当該データの過去履歴とから識別用ストリーム構造データを構築するストリーム構造データ構築部と、
前記識別用ストリーム構造データと、教師ストリームカーネルの値を機械学習することにより得られた識別器とを用いて識別用ストリームカーネルを作成する識別用ストリームカーネル作成部と、
識別用ストリームカーネルの出力値に基づいて当該データの属するクラスを識別する識別部とを含むことを特徴とするクラス識別装置。
【請求項８】
過去履歴の参照範囲を履歴数として入力するステップと、
属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめるステップと、
教師ストリーム構造データに基づいて教師ストリームカーネルを作成するステップと、
教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成するステップとをプロセッサに実行させることを特徴とする学習方法。
【請求項９】
過去履歴の参照範囲を履歴数として入力する機能と、
属するクラスが既知である履歴数個のデータをひとつの教師ストリーム構造データとしてまとめる機能と、
教師ストリーム構造データに基づいて教師ストリームカーネルを作成する機能と、
教師ストリームカーネルの出力値を機械学習することにより、任意のストリーム構造データの属するクラスを識別するための識別器を生成する機能とをコンピュータに実現させることを特徴とするプログラム。
【図３】
【図５】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１】
【図２】
【図４】
【図６】
【図５】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１】
【図２】
【図４】
【図６】
【公開番号】特開２０１０−２８２４４０（Ｐ２０１０−２８２４４０Ａ）
【公開日】平成２２年１２月１６日（２０１０．１２．１６）
【国際特許分類】
【出願番号】特願２００９−１３５５０１（Ｐ２００９−１３５５０１）
【出願日】平成２１年６月４日（２００９．６．４）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２０年１２月２６日 ｈｔｔｐ：／／ｆｗ８．ｂｏｏｋｐａｒｋ．ｎｅ．ｊｐ／ｃｍ／ｉｐｓｊ／ｐａｒｔｉｃｕｌａｒｓ．ａｓｐ？ｃｏｎｔｅｎｔ＿ｉｄ＝ＩＰＳＪ−ＴＯＤ０１０３００６−ＰＤＦに発表
【出願人】（５０８２３６２４０）公立大学法人公立はこだて未来大学 (16)
【出願人】（３９７０６７８５３）株式会社インテリジェントウェイブ (20)
【公開日】平成２２年１２月１６日（２０１０．１２．１６）
【国際特許分類】
【出願日】平成２１年６月４日（２００９．６．４）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２０年１２月２６日 ｈｔｔｐ：／／ｆｗ８．ｂｏｏｋｐａｒｋ．ｎｅ．ｊｐ／ｃｍ／ｉｐｓｊ／ｐａｒｔｉｃｕｌａｒｓ．ａｓｐ？ｃｏｎｔｅｎｔ＿ｉｄ＝ＩＰＳＪ−ＴＯＤ０１０３００６−ＰＤＦに発表
【出願人】（５０８２３６２４０）公立大学法人公立はこだて未来大学 (16)
【出願人】（３９７０６７８５３）株式会社インテリジェントウェイブ (20)
[ Back to top ]