(57)【特許請求の範囲】
【請求項１】
スパム文書を判別するためのスパム分類モデル生成装置であって、
スパム判定対象のスパムページ（spam）または非スパムページ(ham)のいずれかのスパムラベルと特徴ベクトルを有する事例が入力されると、クラス毎に設定されているマージンの大きさに応じて該事例の損失を計算し、該損失の値と事例情報の組を、スパムラベルに応じてspamラベルの配列、またはhamラベルの配列に格納し、損失が最大の事例を当該ラベルの配列から除去し、該損失が最大の事例の特徴ベクトルを抽出し、該特徴ベクトルを用いて該重みベクトルの更新を行い、更新された該重みベクトルをスパム分類モデル記憶手段に格納するスパム分類モデル生成手段と、
スパム判別対象の事例毎の特徴ベクトルが格納された分類データ記憶手段と、
前記スパム分類モデル記憶手段の前記重みベクトルと、前記分類データ記憶手段の前記特徴ベクトルとを用いてスパムスコアを算出し、該スパムスコアが所定の閾値以上の場合はspamと判定し、閾値より小さい場合はhamと判定し、判定結果を出力するスパム分類手段と、
を有することを特徴とするスパム分類モデル生成装置。
【請求項２】
前記スパム分類モデル生成手段は、
前記事例の損失を計算する際に、
前記事例に対して誤りを０にし、前記重みベクトルのL2ノルムの変化量が最小になるように更新する手段を含む
請求項１記載のスパム分類モデル生成装置。
【請求項３】
前記スパム分類モデル生成手段は、
前記spamラベルの配列、前記hamラベルの配列から同じ数だけ損失が最大の事例を選択する事例選択手段を含む
請求項１記載のスパム分類モデル生成装置。
【請求項４】
前記事例選択手段は、
前記重みベクトルの更新を行う毎に更新回数カウンタをインクリメントし、該更新回数カウンタの値が偶数の場合、前記spamラベルの配列から、奇数の場合は、前記hamラベル配列から事例を抽出する手段を含む
請求項３記載のスパム分類モデル生成装置。
【請求項５】
スパム文書を判別するためのスパム分類モデル生成方法であって、
スパム分類モデル生成手段が、スパム判定対象のスパムページ（spam）または非スパムページ(ham)のいずれかのスパムラベルと特徴ベクトルを有する事例が入力されると、クラス毎に設定されているマージンの大きさに応じて該事例の損失を計算し、該損失の値と事例情報の組を、スパムラベルに応じてspamラベルの配列、またはhamラベルの配列に格納し、損失が最大の事例を当該ラベルの配列から除去し、該損失が最大の事例の特徴ベクトルを抽出し、該特徴ベクトルを用いて該重みベクトルの更新を行い、更新された該重みベクトルをスパム分類モデル記憶手段に格納するスパム分類モデル生成ステップと、
スパム分類手段が、前記スパム分類モデル記憶手段の前記重みベクトルと、スパム判別対象の事例毎の特徴ベクトルを保持する分類データ記憶手段の前記特徴ベクトルとを用いてスパムスコアを算出し、該スパムスコアが所定の閾値以上の場合はspamと判定し、閾値より小さい場合はhamと判定し、判定結果を出力するスパム分類ステップと、
を行うことを特徴とするスパム分類モデル生成方法。
【請求項６】
前記スパム分類モデル生成ステップにおいて、
前記事例の損失を計算する際に、前記事例に対して誤りを０にし、前記重みベクトルのL2ノルムの変化量が最小になるように更新する
請求項５記載のスパム分類モデル生成方法。
【請求項７】
前記スパム分類モデル生成ステップにおいて、
前記spamラベルの配列、前記hamラベルの配列から同じ数だけ損失が最大の事例を選択する
請求項５記載のスパム分類モデル生成方法。
【請求項８】
コンピュータを、
請求項１乃至４のいずれか１項に記載のスパム分類モデル生成装置の各手段として機能させるためのスパム分類モデル生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スパム分類モデル生成装置及び方法及びプログラムに係り、特に、スパム文書を判別するためのスパム分類モデル生成装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
ウェブ検索システムのような検索システムにおいては、検索対象の文書を取得し、検索可能にする際に、ユーザの満足度を下げる要因となるスパムページを予め判別し、除去を行うことがある。この際、日々大量に作成されるスパムページに対応するため、スパム、非スパムのラベルが付与された評価データセット（以下、『訓練データ』と記す）を元に機械学習手法を用いて判別器を自動生成する方法がある（例えば、非特許文献1参照）。なお、本明細書では、以下、スパムページのことをspam、非スパムページのことをhamと呼ぶ。
【０００３】
スパム分類においては２つの誤分類が存在し、spamを    hamに誤分類するFalse Negativ(FN)誤りと、hamをspamに誤分類するFalse Positive(FP)誤りが存在する。通常のサービス運用方法では、スパム判別されたデータは検索対象から除去されるため、hamである文書をspamと誤分類するFP誤りは損失が非常に大きい。
【０００４】
また、評価データセットを作成する対象のデータを取得する際、事前にspam、hamのラベルがわからないため、一般的に訓練データ内のspam、hamの事例数には偏りが生じる傾向がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】G. V. Cormack, "Content-based web spam detection", In Proceedings of the 3rd International workshop on Adversarial Information Retrieval on the Web (AIRWeb '07), 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記のように、従来のスパム分類器生成手法では、与えられた訓練データ内にham、spam事例数を考慮していないため、事例数の偏りが生じた際に、スパム分類器を適切に生成できなかった。また、事例の誤りに対して等しく損失を設定していたため、ＦＮ誤りに対してＦＰ誤りを低く抑えることができなかった。そのため、ＦＰ誤りが低い、高精度なスパム分類モデルの生成が困難である、という課題があった。
【０００７】
本発明は、上記の点に鑑みなされたもので、事例の偏りがある訓練データであっても適切にスパム判別モデルを生成することが可能なスパム分類モデル生成装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明（請求項１）は、スパム文書を判別するためのスパム分類モデル生成装置であって、
スパム判定対象のスパムページ（spam）または非スパムページ(ham)のいずれかのスパムラベルと特徴ベクトルを有する事例が入力されると、予めクラス毎に設定されているマージンの大きさに応じて該事例の損失を計算し、該損失の値と事例情報の組を、スパムラベルに応じてspamラベルの配列、またはhamラベルの配列に格納し、各ラベルの配列から損失が最大の事例を当該ラベルの配列から除去し、該損失が最大の事例の特徴ベクトルを抽出し、該特徴ベクトルを用いて該重みベクトルの更新を行い、更新された該重みベクトルをスパム分類モデル記憶手段に格納するスパム分類モデル生成手段と、
スパム判別対象の事例毎の特徴ベクトルを保持する分類データ記憶手段と、
前記スパム分類モデル記憶手段の前記重みベクトルと、前記分類データ記憶手段の前記特徴ベクトルとを用いてスパムスコアを算出し、該スパムスコアが所定の閾値以上の場合はspamと判定し、閾値より小さい場合はhamと判定し、判定結果を出力するスパム分類手段と、を有する。
【０００９】
また、本発明（請求項２）は、前記スパム分類モデル生成手段において、
前記事例の損失を計算する際に、
前記事例に対して誤りを０にし、前記重みベクトルのL2ノルムの変化量が最小になるように更新する手段を含む。
【００１０】
また、本発明（請求項３）は、前記スパム分類モデル生成手段において、
前記spamラベルの配列、前記hamラベルの配列から同じ数だけ損失が最大の事例を選択する事例選択手段を含む。
【００１１】
また、本発明（請求項４）は、前記事例選択手段において、
前記重みベクトルの更新を行う毎に更新回数カウンタをインクリメントし、該更新回数カウンタの値が偶数の場合、前記spamラベルの配列から、奇数の場合は、前記hamラベル配列から事例を抽出する手段を含む。
【発明の効果】
【００１２】
上記のように、本発明によれば、事例の偏りがある訓練データを用いてもスパム判別モデルを生成することが可能となる。また、非スパム事例とスパム事例に対して異なる重要度を付与することが可能となり、訓練データに偏りがある場合においても、非スパム事例をスパムに誤分類するＦＰ誤りを低く抑えて高精度なスパム判別器の生成が可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施の形態におけるスパム分類生成装置の構成図である。
【図２】本発明の一実施の形態における重みの更新のイメージである。
【図３】本発明の一実施の形態におけるスパム分類モデル生成部の処理のフローチャートである。
【図４】本発明の一実施の形態におけるスパム分類部の処理のフローチャートである。
【発明を実施するための形態】
【００１４】
以下、図面と共に本発明の実施の形態を説明する。
【００１５】
図１は、本発明の一実施の形態におけるスパム分類モデル生成装置の構成を示す。
【００１６】
同図に示すスパム分類モデル生成装置は、スパム訓練データＤＢ１０、スパム分類モデル生成部２０、スパム分類モデルＤＢ３０，スパム分類部４０、分類データＤＢ５０、予測ラベルＤＢ６０を有する。
【００１７】
スパム訓練データＤＢ１０、スパム分類モデルＤＢ３０、分類データＤＢ５０、予測ラベルＤＢ６０はハードディスク等の記憶媒体である。
【００１８】
スパム分類モデル生成部２０は、スパム訓練データＤＢ１０のスパム訓練データを読み込み、スパム分類モデルＤＢ３０にスパム分類モデルを出力する。
【００１９】
スパム訓練データＤＢ１０のデータの構造の例を表1に示す。
【００２０】
【表１】
0005815468.tif 000002
スパム訓練データＤＢ１０は、1レコードに1事例の訓練データを格納しており、事例ＩＤ，スパムラベルと特徴ベクトルのカラムで構成されている。ここで「事例」とは、スパム判定の単位である文書のことを表し、判定されたスパムラベルｙと、Ｍ次元の特徴ベクトルｘT=(x1，x2，…，ｘM)の情報を持つ。スパムラベルｙ∈｛＋１，−１｝は、spamの場合＋１、hamの場合−１とする。表１では、"spam"、"ham"で表している。特徴ベクトルには例えば、当該ページに含まれている単語情報やリンク情報などを用いる。特徴ベクトルの各カラムは、当該事例の特徴ベクトルの値を格納している。
【００２１】
スパム分類モデルＤＢ３０のデータ構造の例を表２に示す。
【００２２】
【表２】
0005815468.tif 000003
スパム分類モデルＤＢ３０は、事例の特徴ベクトルの次元数と同じ次元数である重みベクトルｗT=(w1，w2，…，ｗM)の情報を格納しており、ｗiが特徴ｘiに対する重みである。
【００２３】
スパム分類モデル生成部２０は、スパム訓練データＤＢ１０から読み出した事例に対して誤りを０にし、重みベクトルのL2ノルムの変化量が最小になるように重みパラメータを更新することでマージンを変更する。重みパラメータの更新のイメージを図２に示す。同図では、入力事例（訓練データ）に対して損失が０になるように重みパラメータを更新する例を示している。
【００２４】
スパム分類モデル生成部２０では、システムに対して予め正例マージンサイズＥ（＋１），負例マージンサイズＥ（−１），コストパラメータＣ，イテレーション回数ｎ、選択サンプル数ｕ、出力に対する閾値ｔが設定されているとする。
【００２５】
図３は、本発明の一実施の形態におけるスパム分類モデル生成部の処理のフローチャートである。
【００２６】
ステップ１０１）  スパム分類モデル生成部２０は、重みベクトルｗを初期化する。事前の設定がなければ、ｗT＝（０，０，…，０）とする。また、更新回数カウンタを初期化し、ｉ←０とする。
【００２７】
ステップ１０２）  スパム訓練データＤＢ１０に含まれる全ての事例について、現在の重みベクトルに基づいて損失を計算する。ある事例（ｘ，ｙ）に対する損失は、当該ラベルを考慮したマージンＥ（ｙ）を用いて
【００２８】
【数１】
0005815468.tif 000004
と求めることができる。上記では、予めクラス毎に設定されたマージンの大きさ（E(y)）に応じて損失の計算を行っている。
【００２９】
そして、式(1)で計算された損失の値と事例情報の組（ｌ(i)，ｘ(i)，ｙ(i)）をラベルに応じた配列に格納する。ｙ＝＋１の場合、すなわち、spam事例の場合には、spam用の配列に格納し、ｙ＝−１の場合、すなわちham事例の場合にはham用の配列に格納する。この配列を用いてステップ１０４において損失が最大の事例を選択するため、ピープ木のようなデータ構造を用いてデータを格納すると計算効率がよい。なお、各配列はメモリ（図示せず）に格納されるものとする。
【００３０】
ステップ１０３）  選択事例用カウンタｊを初期化し、ｊ←０とする。
【００３１】
ステップ１０４）  i mod 2=0の場合、すなわち、重みベクトル更新のための更新回数カウンタｉが偶数の場合、spam用配列から損失が最大の事例を取得し、spam用配列から当該事例を除去する。それ以外の場合、すなわち更新回数カウンタが奇数の場合、ham用配列から損失が最大の事例を取得し、ham用配列から当該事例を除去する。ここで選択した事例の損失をｌt、ラベルをｙt、特徴ベクトルをｘとする。当該処理を行うことにより、事例数の偏りの影響を排除することができる。
【００３２】
ステップ１０５）  選択した事例に基づいて、重みベクトルの更新を行う。重みベクトルの更新は例えば、文献「K. Crammer, O. Dekel, J. Keshet, S. S.-Shwartz and Y. Singer, "Online Passive-Aggressive Algorithm", Journal of Machine Learning, vol. 7, pp. 551-585, 2006.」の方法を用いて
【００３３】
【数２】
0005815468.tif 000005
で計算することができる。ここで、
【００３４】
【数３】
0005815468.tif 000006
である。ここで‖ｘ‖は特徴ベクトルのL2ノルムを表し、
【００３５】
【数４】
0005815468.tif 000007
で計算できる。
【００３６】
ステップ１０６）  カウンタを更新し、ｉ←ｉ＋１，ｊ←ｊ＋１とする。
【００３７】
ステップ１０７）  ｊ＜ｕかつｉ＜ｎの場合、ステップ１０４に戻り、それ以外の場合はステップ１０８に移行する。ここで、ｕ，ｎは事前に定めたパラメータ（定数）であり、ｕとｎの関係は経験的にｕ≪ｎである。
【００３８】
ステップ１０８）ｉ＜ｎの場合ステップ１０２に戻る。それ以外の場合はステップ１０９に移行する。
【００３９】
ステップ１０９）  重みベクトルｗをスパム分類モデルＤＢ３０に出力し、処理を終了する。
【００４０】
スパム分類部４０は、分類データＤＢ５０のデータを入力として受け取り、スパム分類結果を予測ラベルＤＢ６０に出力する。その際、分類データＤＢ５０の1レコードに対応するデータを逐次的に受け取り、予測ラベルＤＢ６０の1レコードに対応する結果を逐次的に出力することも可能である。
【００４１】
分類データＤＢ５０のデータ構造を表３に示す。
【００４２】
【表３】
0005815468.tif 000008
分類データＤＢ５０は、スパム判別を行う対象のデータを格納しており、事例ＩＤと特長ベクトルｘの特徴を格納している。分類データＤＢ５０のデータベーススキーマは、スパム訓練データ１０からラベルカラムを除いたものとなる。
【００４３】
予測ラベルＤＢ６０のデータ構造の例を表４に示す
【００４４】
【表４】
0005815468.tif 000009
予測ラベルＤＢ６０は、入力された各事例に対して予測ラベルと予測スコアの情報を格納している。
【００４５】
図３は、本発明の一実施の形態におけるスパム分類部の処理のフローチャートである。
【００４６】
ステップ２０１）  スパム分類部４０は、スパム分類モデルＤＢ３０から重みベクトル情報を取得し、Ｍ次元の重みベクトルｗT=(ｗ1，ｗ2，…，ｗM)とする。
【００４７】
ステップ２０２）  分類データＤＢ５０から未処理のデータを取得し、Ｍ次元の特徴ベクトルｘ＝(ｘ1，ｘ2，…，ｘM)とする。
【００４８】
ステップ２０３）  ステップ２０１で取得した重みベクトルとステプ２０２から取得した特徴ベクトルを用いて、スパムスコアｓを
【００４９】
【数５】
0005815468.tif 000010
に従って計算する。
【００５０】
ステップ２０４）  スパムスコアｓが予めシステムに設定された閾値以上の場合にはspamと判定し、そうでない場合はhamと判定する。判定された予測ラベルを
【００５１】
【数６】
0005815468.tif 000011
とする。
【００５２】
ステップ２０５）  当該事例ＩＤ、当該事例に対するスパムスコアｓと予測ラベル
【００５３】
【数７】
0005815468.tif 000012
を、予測ラベルＤＢ６０に出力する。
【００５４】
ステップ２０６）  分類データＤＢ５０に未処理のデータがある場合にはステップ２０２に戻り、そうでない場合は処理を終了する。
【００５５】
上記のような処理を行うことで、訓練データに事例の偏りがある状態においてもhamをspamに誤分類する悪影響を抑えることが可能となり、FP誤りを押さえた高精度なスパム分類を実現することが可能である。
【００５６】
なお、上記の実施の形態におけるスパム分類モデル生成装置の各構成要素の動作をプログラムとして構築し、スパム分類モデル生成装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５７】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５８】
１０  スパム訓練データＤＢ
２０  スパム分類モデル生成部
３０  スパム分類モデルＤＢ
４０  スパム分類部
５０  分類データＤＢ
６０  予測ラベルＤＢ
【図１】
0005815468.tif 000013
【図２】
0005815468.tif 000014
【図３】
0005815468.tif 000015
【図４】
0005815468.tif 000016