(57)【特許請求の範囲】
【請求項１】
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得部と、
前記取得部により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成部と、
前記学習結果に基づいてノード毎に算出されるスコアに基づいて順位付けされた前記複数のノードのうち、前記順位が所定の条件を満たすノードに対応する前記主体が前記行動における不正行為を行ったと判定する判定部と、
を備えたことを特徴とする生成装置。
【請求項２】
前記生成部は、
前記不正行為に関するラベルとして不正行為を示すラベルが割り当てられたノードとの連結に関する情報を用いて得られた前記学習結果に基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する
ことを特徴とする請求項１に記載の生成装置。
【請求項３】
前記生成部は、
前記不正行為に関するラベルであって各ノードと連結する他のノードに割り当てられた前記ラベルに応じて前記各ノードにおける前記ラベル毎の割当値を算出し、前記割当値に基づいて学習される前記各ノードにおける前記ラベル毎の予測値を前記学習結果として、前記各ノードに対応する前記主体の前記行動における不正行為の有無に関する情報を生成する
ことを特徴とする請求項１または請求項２に記載の生成装置。
【請求項４】
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得部と、
前記取得部により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報として不正行為を示す不正ラベル、又は、正当行為を示す正当ラベルが割り当てられたノードとの連結に関する情報として、各ノードにおける前記不正ラベル毎、及び、前記正当ラベル毎の割当値を算出し、前記割当値に基づいて学習された各ノードにおける前記不正ラベル毎、及び、前記正当ラベル毎の予測値を用いて得られた学習結果に基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成部と、
を備えたことを特徴とする生成装置。
【請求項５】
前記生成部は、
前記各ノードにおける前記ラベル毎の前記予測値を用いて算出されるスコアに基づいて、前記各ノードに対応する前記主体の前記行動における不正行為の有無に関する情報を生成する
ことを特徴とする請求項４に記載の生成装置。
【請求項６】
前記生成部により算出された前記スコアに基づいて、所定の条件を満たすノードに対応する前記主体が前記行動における不正行為を行ったと判定する判定部、
をさらに備えたことを特徴とする請求項５に記載の生成装置。
【請求項７】
前記判定部は、
前記スコアに基づいて順位付けされた前記複数のノードのうち、前記順位が所定の条件を満たすノードに対応する前記主体が前記行動における不正行為を行ったと判定する、
ことを特徴とする請求項６に記載の生成装置。
【請求項８】
前記生成部は、
前記各ノードにおける前記ラベル毎の前記予測値を用いて算出される第１スコアと、前記各ノードと連結する他のノードにおける前記第１スコアと、前記各ノードと前記他のノードとの前記行動の回数に応じて前記各ノードと前記他のノードとを連結する前記エッジに付された重みと、により算出される第２スコアに基づいて、前記各ノードに対応する前記主体の前記行動における不正行為の有無に関する情報を生成する
ことを特徴とする請求項４に記載の生成装置。
【請求項９】
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得部と、
前記取得部により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、各ノードにおいて算出される第１スコアと、前記各ノードと連結する他のノードにおいて算出される前記第１スコアと、前記各ノードと前記他のノードとの前記行動の回数に応じて前記各ノードと前記他のノードとを連結する前記エッジに付された重みと、により算出される第２スコアに基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成部と、
を備えたことを特徴とする生成装置。
【請求項１０】
前記生成部により算出された前記第２スコアに基づいて、所定の条件を満たすノードに対応する前記主体が前記行動における不正行為を行ったと判定する判定部、
をさらに備えたことを特徴とする請求項８または請求項９に記載の生成装置。
【請求項１１】
前記判定部は、
前記第２スコアに基づいて順位付けされた前記複数のノードのうち、前記順位が所定の条件を満たすノードに対応する前記主体が前記行動における不正行為を行ったと判定する、
ことを特徴とする請求項１０に記載の生成装置。
【請求項１２】
コンピュータが実行する生成方法であって、
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得工程と、
前記取得工程により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成工程と、
前記学習結果に基づいてノード毎に算出されるスコアに基づいて順位付けされた前記複数のノードのうち、前記順位が所定の条件を満たすノードに対応する前記主体が前記行動における不正行為を行ったと判定する判定工程と、
を含むことを特徴とする生成方法。
【請求項１３】
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得手順と、
前記取得手順により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成手順と、
前記学習結果に基づいてノード毎に算出されるスコアに基づいて順位付けされた前記複数のノードのうち、前記順位が所定の条件を満たすノードに対応する前記主体が前記行動における不正行為を行ったと判定する判定手順と、
をコンピュータに実行させることを特徴とする生成プログラム。
【請求項１４】
コンピュータが実行する生成方法であって、
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得工程と、
前記取得工程により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報として不正行為を示す不正ラベル、又は、正当行為を示す正当ラベルが割り当てられたノードとの連結に関する情報として、各ノードにおける前記不正ラベル毎、及び、前記正当ラベル毎の割当値を算出し、前記割当値に基づいて学習された各ノードにおける前記不正ラベル毎、及び、前記正当ラベル毎の予測値を用いて得られた学習結果に基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成工程と、
を含むことを特徴とする生成方法。
【請求項１５】
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得手順と、
前記取得手順により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報として不正行為を示す不正ラベル、又は、正当行為を示す正当ラベルが割り当てられたノードとの連結に関する情報として、各ノードにおける前記不正ラベル毎、及び、前記正当ラベル毎の割当値を算出し、前記割当値に基づいて学習された各ノードにおける前記不正ラベル毎、及び、前記正当ラベル毎の予測値を用いて得られた学習結果に基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成手順と、
をコンピュータに実行させることを特徴とする生成プログラム。
【請求項１６】
コンピュータが実行する生成方法であって、
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得工程と、
前記取得工程により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、各ノードにおいて算出される第１スコアと、前記各ノードと連結する他のノードにおいて算出される前記第１スコアと、前記各ノードと前記他のノードとの前記行動の回数に応じて前記各ノードと前記他のノードとを連結する前記エッジに付された重みと、により算出される第２スコアに基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成工程と、
を含むことを特徴とする生成方法。
【請求項１７】
ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得手順と、
前記取得手順により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、各ノードにおいて算出される第１スコアと、前記各ノードと連結する他のノードにおいて算出される前記第１スコアと、前記各ノードと前記他のノードとの前記行動の回数に応じて前記各ノードと前記他のノードとを連結する前記エッジに付された重みと、により算出される第２スコアに基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成手順と、
をコンピュータに実行させることを特徴とする生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、生成装置、生成方法、及び生成プログラムに関する。
【背景技術】
【０００２】
従来、インターネットオークション等のネットワーク上の行動における不正行為を検出する技術が提供されている。例えば、数理モデルを適用することにより、不正行為を抽出する技術が提供されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−２１１４４号公報
【非特許文献】
【０００４】
【非特許文献１】P.  P.  Talukdar  and  K.  Crammer.  “New  Regularized  Algorithms  for  Transductive  Learning.  In  Proceedings  of  the  European  Conference  on  Machine  Learning  and  Knowledge  Discovery  in  Databases”:  Part  II,  ECML  PKDD  '09,  pages  442-457,  Berlin,  Heidelberg,  2009.  Springer-Verlag.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の従来技術では、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成できるとは限らない。例えば、数理モデルを適用することにより不正行為を抽出する場合、不正行為のパターン毎に数理モデルを要する場合がある。また、数理モデルが不正行為に適切に対応していない場合、不正行為の有無に関する情報を適切に生成することは難しい。
【０００６】
本願は、上記に鑑みてなされたものであって、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成する生成装置、生成方法、及び生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本願に係る生成装置は、ネットワーク上における行動の主体の各々に対応する複数のノードと、前記行動における関係を有するノード間を連結するエッジとを含むグラフを取得する取得部と、前記取得部により取得された前記グラフにおける前記複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、前記複数のノードの各々に対応する前記主体の前記行動における不正行為の有無に関する情報を生成する生成部と、を備えたことを特徴とする。
【発明の効果】
【０００８】
実施形態の一態様によれば、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】図１は、実施形態に係る生成処理の一例を示す図である。
【図２】図２は、実施形態に係る判定装置の構成例を示す図である。
【図３】図３は、実施形態に係る行動情報記憶部の一例を示す図である。
【図４】図４は、実施形態に係るグラフ情報記憶部の一例を示す図である。
【図５】図５は、実施形態に係る割当値情報記憶部の一例を示す図である。
【図６】図６は、実施形態に係る予測値情報記憶部の一例を示す図である。
【図７】図７は、実施形態に係るスコア情報記憶部の一例を示す図である。
【図８】図８は、実施形態に係る生成処理手順示すフローチャートである。
【図９】図９は、変形例に係る生成処理の一例を示す図である。
【図１０】図１０は、変形例に係る判定装置の構成例を示す図である。
【図１１】図１１は、変形例に係る第１スコア情報記憶部の一例を示す図である。
【図１２】図１２は、変形例に係る第２スコア情報記憶部の一例を示す図である。
【図１３】図１３は、変形例に係る生成処理手順を示すフローチャートである。
【図１４】図１４は、判定装置の機能を実現するコンピュータの一例を示すハードウェア構成図である。
【発明を実施するための形態】
【００１０】
以下に、本願に係る生成装置、生成方法、及び生成プログラムを実施するための形態（以下、「実施形態」と呼ぶ）について図面を参照しつつ詳細に説明する。なお、この実施形態により本願に係る生成装置、生成方法、及び生成プログラムが限定されるものではない。また、以下の各実施形態において同一の部位には同一の符号を付し、重複する説明は省略される。
【００１１】
（実施形態）
〔１．生成処理〕
まず、図１を用いて、実施形態に係る生成処理の一例について説明する。図１は、実施形態に係る生成処理の一例を示す図である。以下では、生成処理において不正行為に関する情報の生成を行った後、不正行為の判定までを行う場合を示すが、生成処理には不正行為の判定は含まれなくてもよい。以下に示す例においては、インターネットオークションにおける行動、をネットワーク上における行動の一例として説明する。図１に示す例においては、１８個のノードＮ１〜Ｎ１８を図示する。ここで、各ノードは、インターネットオークションの主体（例えば、ユーザやショップ等）に対応する。例えば、ノードＮ１は、インターネットオークションを行う一ユーザに対応し、ノードＮ２は、インターネットオークションを行う一ショップに対応する。なお、図１に示す例において、説明のために少数のノードＮ１〜Ｎ１８が含まれるグラフＧ１１を一例として示すが、例えば、グラフには、１００万のノードが含まれてもよい。また、図１に示す例において、インターネットオークションにおける関係を有するノード間をエッジにより連結する。例えば、インターネットオークションにおいて一方が出品し、他方が出品された商品に入札した一対のノード間はエッジにより連結される。また、各エッジに付された数値（重み）は、連結するノード間において入札された商品の数を示す。なお、図１に示すグラフＧ１２は、生成処理後（判定後）のグラフを示し、ノード数やエッジの連結については生成処理前（判定前）のグラフＧ１１と同様である。なお、エッジの重みは、ノード間において入札された商品の数に限らず、ノード間において商品が落札された回数（取引回数）やノード間において入札が行われた回数など、目的に応じて種々の要素を適宜選択してもよい。
【００１２】
以下では、判定装置１００が、図１に示すノードＮ１〜Ｎ１８を含むノードについて不正行為を行った主体に対応するノード（以下、「不正ノード」と称する場合がある）を判定する例を示す。
【００１３】
まず、判定装置１００は、図１左側の生成処理前（判定前）のグラフＧ１１に示すように、予め不正行為を行う主体であると特定された主体に対応するノードに不正行為に関する情報として、不正行為を行う主体であることを示すラベルを割り当てる。以下では、不正行為を行う主体であることを示すラベルを不正ラベルと称し、不正ラベルが割り当てられたノードを不正シードと称する場合がある。図１に示す例においては、判定装置１００は、ノードＮ２、ノードＮ３、ノードＮ９、及びノードＮ１０の４個のノードを不正シードとして不正ラベルを割り当てる。例えば、不正ラベルの他に正当行為を行う主体であることを示すラベル（以下、「正当ラベル」と称する場合がある）等が割り当てられるが、図１に示す例においては不正ラベルのみが割り当てられた場合を説明する。なお、正当ラベルが割り当てられたノードを正当シードと称する場合がある。例えば、ノードに割り当てるラベルについては、後述する行動情報記憶部１２１に記憶された行動情報等から判定装置１００の管理者等が推定して割り当てる。
【００１４】
その後、判定装置１００は、各ノードと連結する他のノードに割り当てられたラベルに応じて各ノードにおけるラベル毎の割当値を算出する。例えば、判定装置１００は、エッジにより連結するノードのラベルに応じて、各ノードにおけるラベル毎の割当値を算出する。そして、判定装置１００は、各ノードにおけるラベル毎の割当値に基づいて学習されるラベル毎の予測値を学習結果として、各ノードに対応する主体のインターネットオークションにおける不正行為の有無に関する情報を生成する。例えば、判定装置１００は、ノードに割り当てたラベルと生成処理の結果が一致するように、周囲に不正シードが多いノードは不正ノードとなるように学習を行うが詳細は後述する。判定装置１００は、各ノードにおけるラベル毎の予測値を用いて算出されるスコアに基づいて、所定の条件を満たすノードに対応する主体がインターネットオークションにおける不正行為を行ったと判定する。具体的には、判定装置１００は、各ノードにおけるラベル毎の予測値を用いて算出されるスコアに基づいて順位付けされたノードのうち、順位が所定の条件を満たすノードに対応する主体がインターネットオークションにおける不正行為を行ったと判定する。図１に示す例においては、順位が９位以内であることを順位が所定の条件を満たす場合の一例として、順位１位〜９位までのノードを不正ノードとして判定する。なお、上記の判定装置１００による、割当値の算出、予測値の学習、及び不正行為の判定等の生成処理の詳細については後述する。
【００１５】
上記の生成処理により、図１右側に示す生成処理後（判定後）のグラフＧ１２に示すように、不正シードであるノードＮ２、ノードＮ３、ノードＮ９、及びノードＮ１０を含む９個のノードが不正ノードとして判定される。例えば、ノードＮ４は、不正シードであるノードＮ２及びノードＮ３と連結する。そのため、ノードＮ２及びノードＮ３と連結するノードＮ４が不正ノードとして判定される。また、例えば、ノードＮ１１及びノードＮ１２は、不正シードであるノードＮ９と連結する。そのため、ノードＮ９と連結するノードＮ１１及びノードＮ１２が不正ノードとして判定される。また、例えば、ノードＮ１３は、不正シードであるノードＮ１０と連結する。そのため、ノードＮ１０と連結するノードＮ１３が不正ノードとして判定される。すなわち、不正シードであるノードＮ９やノードＮ１０と２部グラフを形成するノードＮ１１〜Ｎ１３も不正ノードとして判定される。また、ノードＮ１２に連結するノードＮ１４も不正ノードとして判定される。
【００１６】
このように、実施形態に係る判定装置１００は、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。図１に示すように、判定装置１００は、複数のノードとノード間を連結するエッジを含むグラフを不正検知に応用することにより、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成し、不正ノードを精度よく判定することができる。また、判定装置１００は、不正ラベルを割り当てられた不正シードを応じて各ノードに割り当てられる割当値に基づいて、学習を行うことにより、適切に予測値を導出することができる。そして、判定装置１００は、導出した予測値に基づいて算出されたスコアに基づいて、各ノードを順位付けすることにより、不正ノードを精度よく判定することができる。
【００１７】
なお、判定装置１００は、予め不正行為を行わない（正当行為を行う）主体であると特定された主体に対応するノードに不正行為に関する情報として、正当行為を行う主体であることを示す正当ラベルを割り当ててもよい。例えば、図１に示す例においては、判定装置１００は、ノードＮ１６及びノードＮ１７等に正当ラベルを割り当ててもよい。例えば、ノードＮ１６及びノードＮ１７が正当シードである場合、上記の生成処理において、不正ノードと判定されたノードＮ１４は、正当シードであるノードＮ１６と連結するため、不正ノードと判定されない場合がある。このように、判定装置１００は、正当シードも含めて生成処理を行うことにより、精度よく不正ノードを判定することができる。
【００１８】
〔２．判定装置の構成〕
次に、図２を用いて、実施形態に係る判定装置１００の構成について説明する。図２は、実施形態に係る判定装置の構成例を示す図である。判定装置１００は、グラフにおける複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、複数のノードの各々に対応する主体のネットワーク上での行動における不正行為の有無に関する情報を生成する生成装置である。また、判定装置１００は、各ノードにおけるラベル毎の予測値を用いて算出されるスコアに基づいて、所定の条件を満たすノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定する。図２に示すように、判定装置１００は、通信部１１０と、記憶部１２０と、制御部１３０とを有する。なお、判定装置１００は、各種の情報を表示する表示部や、各種の情報を入力する入力部を有してもよい。
【００１９】
（通信部１１０）
通信部１１０は、例えば、ＮＩＣ等によって実現される。そして、通信部１１０は、所定のネットワークと有線または無線で接続され、外部の情報処理装置との間で情報の送受信を行う。
【００２０】
（記憶部１２０）
記憶部１２０は、例えば、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置によって実現される。実施形態に係る記憶部１２０は、図２に示すように、行動情報記憶部１２１と、グラフ情報記憶部１２２と、割当値情報記憶部１２３と、予測値情報記憶部１２４と、スコア情報記憶部１２５とを有する。
【００２１】
（行動情報記憶部１２１）
実施形態に係る行動情報記憶部１２１は、グラフの生成に用いる行動情報を記憶する。図３は、実施形態に係る行動情報記憶部の一例を示す図である。図３に示す例においては、行動情報として、インターネットオークションにおける行動である出品された商品への入札のログ情報が記憶される。図３に示すように、行動情報記憶部１２１は、行動情報として、「オークションＩＤ（商品ＩＤ）」、「出品者ＩＤ（ノードＩＤ）」、「入札者ＩＤ（ノードＩＤ）」、「日時」等の項目を有する。なお、項目は上記に限らず、行動情報記憶部１２１は、出品した商品に関する情報や、入札金額等に関する項目など、目的に応じて種々の項目を有してもよい。
【００２２】
「オークションＩＤ」は、インターネットオークションにおける各オークション（商品）を識別するための識別情報を示す。「出品者ＩＤ（ノードＩＤ）」は、対応するオークションＩＤにより識別されるオークションにおける出品者である主体を識別するための識別情報を示す。また、「入札者ＩＤ（ノードＩＤ）」は、対応するオークションＩＤにより識別されるオークションにおける入札者である主体を識別するための識別情報を示す。なお、図３に示す例においては、出品者ＩＤ及び入札者ＩＤとして、ノードＩＤを用いた場合を示すが、ノードＩＤと対応付けられたユーザＩＤやショップＩＤを用いてもよい。また、ノードＩＤは、図１に示す各ノードの符号に対応する。例えば、ノードＩＤ「Ｎ１」により識別されるノードは、図１に示すノードＮ１に対応する。すなわち、ノードＩＤ「Ｎ１」により識別されるノードと、図１中のノードＮ１とは同じノードを示し、図１に示す他のノードＮ２〜Ｎ１８についても同様である。また、「日時」は、対応するオークションＩＤにより識別されるオークション（商品）に入札者ＩＤにより識別される主体が入札した日時を示す。
【００２３】
例えば、図３に示す例において、オークションＩＤ「Ａ１１」により識別されるオークション（商品）は、出品者ＩＤ（ノードＩＤ）「Ｎ１」により識別されるノードに対応する主体が出品し、入札者ＩＤ（ノードＩＤ）「Ｎ２」により識別されるノードに対応する主体が、日時「２０１５/４/１  １３:０５」に入札したことを示す。なお、判定装置１００は、後述するグラフ情報を外部から取得する場合、行動情報記憶部１２１を有さなくてもよい。例えば、判定装置１００は、外部のオークション装置からグラフ情報を取得する場合、行動情報記憶部１２１を有さなくてもよい。
【００２４】
（グラフ情報記憶部１２２）
実施形態に係るグラフ情報記憶部１２２は、グラフ情報を記憶する。図４は、実施形態に係るグラフ情報記憶部の一例を示す図である。図４に示すように、グラフ情報記憶部１２２は、グラフ情報として、ノードＩＤにより識別される主体間において入札された商品の数を記憶する。
【００２５】
例えば、図４に示す例において、ノードＩＤ「Ｎ１」の行とノードＩＤ「Ｎ２」の列とが交差する項目には、ノードＩＤ「Ｎ１」により識別される主体とノードＩＤ「Ｎ２」により識別される主体との間において入札された商品の数が記憶される。図３に示す例においては、ノードＩＤ「Ｎ１」の行とノードＩＤ「Ｎ２」の列とが交差する項目には、「１０」が記憶される。つまり、ノードＩＤ「Ｎ１」により識別される主体とノードＩＤ「Ｎ２」により識別される主体との間において入札された商品の数が１０個であることを示す。このように、グラフ情報記憶部１２２において「１」以上の値が記憶された項目に対応するノード間には一方が出品した商品に他方が入札行った履歴があることを示す。
【００２６】
また、図４に示す例において、ノードＩＤ「Ｎ２」の行とノードＩＤ「Ｎ１」の列とが交差する項目には、ノードＩＤ「Ｎ１」の行とノードＩＤ「Ｎ２」の列とが交差する項目と同様の情報が記憶される。なお、判定装置１００は、ノードＩＤ「Ｎ１」の行とノードＩＤ「Ｎ２」の列とが交差する項目かノードＩＤ「Ｎ２」の行とノードＩＤ「Ｎ１」の列とが交差する項目かのいずれか一方のみを記憶してもよい。
【００２７】
また、図３に示す例においては、ノードＩＤ「Ｎ１」の行とノードＩＤ「Ｎ３」の列とが交差する項目には、「０」が記憶される。つまり、ノードＩＤ「Ｎ１」により識別される主体とノードＩＤ「Ｎ３」により識別される主体との間には一方が出品した商品に他方が入札を行った履歴がないことを示す。なお、ノードＩＤ「Ｎ１」の行とノードＩＤ「Ｎ１」の列とが交差する項目には、「０」を記憶してもよい。他のノードＩＤ「Ｎ２」等についても同様である。
【００２８】
（割当値情報記憶部１２３）
実施形態に係る割当値情報記憶部１２３は、予測値の学習に用いる割当値情報を記憶する。図５は、実施形態に係る割当値情報記憶部の一例を示す図である。図５に示す例においては、割当値情報として３つのラベル毎に対応する割当値が記憶される。図５に示すように、割当値情報記憶部１２３は、割当値情報として、「不正割当値」、「正当割当値」、「ダミー割当値」の項目を有する。なお、項目は上記に限らず、割当値情報記憶部１２３は、ラベルに応じて種々の項目を有してもよい。
【００２９】
「不正割当値」は、隣接するノードに含まれる不正ノードの数に基づいて各ノードに割り当てられる割当値を示す。「正当割当値」は、隣接するノードに含まれる正当ノードの数に基づいて各ノードに割り当てられる割当値を示す。「ダミー割当値」は、本実施形態において用いられるラベルであるダミーラベルに対応する割当値を示す。
【００３０】
例えば、図５に示す例においては、ノードＩＤ「Ｎ１」により識別されるノードには、不正割当値、正当割当値、及びダミー割当値として「０」が割り当てられる。図１に示す例において不正シードとなるノードＩＤ「Ｎ２」により識別されるノードには、不正割当値として「１」が割り当てられ、正当割当値、及びダミー割当値として「０」が割り当てられる。なお、不正割当値、正当割当値、及びダミー割当値の算出等についての詳細は後述する。
【００３１】
（予測値情報記憶部１２４）
実施形態に係る予測値情報記憶部１２４は、割当値に基づく学習により導出された予測値情報を記憶する。図６は、実施形態に係る予測値情報記憶部の一例を示す図である。図６に示す例においては、予測値情報として３つのラベル毎に対応する予測値が記憶される。図６に示すように、予測値情報記憶部１２４は、予測値情報として、「不正予測値」、「正当予測値」、「ダミー予測値」の項目を有する。なお、項目は上記に限らず、予測値情報記憶部１２４は、ラベルに応じて種々の項目を有してもよい。
【００３２】
「不正予測値」は、割当値に基づく学習により導出された不正ノードに対応する予測値を示す。「正当予測値」は、割当値に基づく学習により導出された正当ノードに対応する予測値を示す。「ダミー予測値」は、本実施形態において用いられるラベルであるダミーラベルに対応する予測値を示す。
【００３３】
例えば、図６に示す例においては、ノードＩＤ「Ｎ１」により識別されるノードに関して、不正予測値として「０．３」が導出され、正当予測値として「０．３」が導出され、ダミー予測値として「０．４」が導出されたことを示す。また、ノードＩＤ「Ｎ２」により識別されるノードに関して、不正予測値として「０．６」が導出され、正当予測値として「０．１」が導出され、ダミー予測値として「０．３」が導出されたことを示す。なお、学習による不正予測値、正当予測値、及びダミー予測値の導出等についての詳細は後述する。
【００３４】
（スコア情報記憶部１２５）
実施形態に係るスコア情報記憶部１２５は、各ノードにおけるラベル毎の予測値を用いて算出されるスコア情報を記憶する。図７は、実施形態に係るスコア情報記憶部の一例を示す図である。図７に示す例においては、スコアが高い方から順に順位付されたノードに関する情報が記憶される。図７に示すように、スコア情報記憶部１２５は、スコア情報として、「順位」、「ノードＩＤ」、「スコア」の項目を有する。なお、項目は上記に限らず、スコア情報記憶部１２５は、目的に応じて種々の項目を有してもよい。
【００３５】
「順位」は、各ノードのスコアに基づく順位を示す。「ノードＩＤ」は、各ノードを識別する識別情報を示す。「スコア」は、各ノードにおけるラベル毎の予測値を用いて算出されるスコアを示す。
【００３６】
例えば、図７に示す例においては、順位「１」のノードはノードＩＤ「Ｎ９」により識別されるノードであり、スコアは「０．９」であることを示す。順位「２」のノードはノードＩＤ「Ｎ３」により識別されるノードであり、スコアは「０．８」であることを示す。スコア算出等の詳細は後述するが、スコアが高い程、不正行為を行った主体に対応するノードである可能性が高いことを示す。
【００３７】
（制御部１３０）
図２の説明に戻って、制御部１３０は、例えば、ＣＰＵやＭＰＵ等によって、判定装置１００内部の記憶装置に記憶されている各種プログラム（判定プログラムの一例に相当）がＲＡＭを作業領域として実行されることにより実現される。また、制御部１３０は、例えば、ＡＳＩＣやＦＰＧＡ等の集積回路により実現される。
【００３８】
図２に示すように、制御部１３０は、取得部１３１と、生成部１３２と、判定部１３３とを有し、以下に説明する情報処理の機能や作用を実現または実行する。なお、制御部１３０の内部構成は、図２に示した構成に限られず、後述する情報処理を行う構成であれば他の構成であってもよい。また、制御部１３０が有する各処理部の接続関係は、図２に示した接続関係に限られず、他の接続関係であってもよい。また、制御部１３０は、例えば、外部の情報処理装置に不正行為の有無に関する情報や生成処理に関する情報を送信する場合、送信部を有してもよい。
【００３９】
（取得部１３１）
本実施形態における取得部１３１は、行動情報やグラフ情報等を取得する。また、取得部１３１は、外部のオークション装置から行動情報やグラフ情報を取得してもよい。また、取得部１３１は、外部のオークション装置から行動情報やグラフ情報を取得した場合、取得した行動情報やグラフ情報を行動情報記憶部１２１やグラフ情報記憶部１２２に格納する。
【００４０】
（生成部１３２）
生成部１３２は、グラフにおける複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、複数のノードの各々に対応する主体のネットワーク上での行動における不正行為の有無に関する情報を生成する。例えば、生成部１３２は、不正行為に関するラベルとして不正行為を示すラベルが割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、複数のノードの各々に対応する主体のネットワーク上での行動における不正行為の有無に関する情報を生成する。また、生成部１３２は、行動情報に基づいてグラフ情報を生成してもよい。
【００４１】
以下、生成部１３２による不正行為の有無に関する情報の生成について説明する。本実施形態において、生成部１３２は、各ノードと連結する他のノードに割り当てられたラベルに応じて各ノードにおけるラベル毎の割当値を算出し、割当値に基づいて学習される各ノードにおけるラベル毎の予測値を学習結果として、各ノードに対応する主体のネットワーク上での行動における不正行為の有無に関する情報を生成する。
【００４２】
以下に示す例では、図１に示すグラフ情報及び、図３〜図７に示す各種情報に基づいて説明する。ここで、本実施形態における生成部１３２は、不正行為の有無に関する情報の生成において、非特許文献１に示されるＭＡＤ（Modified  Adsorption）を用いる。非特許文献１に示されるＭＡＤは、グラフ構造に基づく半教師あり機械学習アルゴリズムである。すなわち、生成部１３２は、グラフ構造に基づく半教師あり機械学習アルゴリズムであるＭＡＤに関する技術を応用することにより、複数のノードの各々に対応する主体のネットワーク上での行動における不正行為の有無に関する情報を生成する。まず、生成部１３２は、各ラベルに対応する予測値を以下の式（１）により算出する。すなわち、以下の式（１）に基づいて学習を行うことにより、適切な予測値を導出する。具体的には、以下の式（１）が最小となるように予測値を導出する。
【００４３】
【数１】
0006333213.tif 000002
【００４４】
上記式（１）中の割当値行列「Ｙ」（以下、単に「Ｙ」と表記する）は、ｎ行（ｍ＋１）列の行列により表され、初期のラベル情報を示す。ここで、「Ｙ」の行数を示すｎは、グラフに含まれるノード数に対応する。図１に示す例においては、「Ｙ」の行数を示すｎは、１８になる。例えば、「Ｙ」の１行目は、ノードＩＤ「Ｎ１」により識別されるノードに関する情報が割り当てられ、「Ｙ」の２行目は、ノードＩＤ「Ｎ２」により識別されるノードに関する情報が割り当てられる。また、「Ｙ」の列数を示す（ｍ＋１）は、ラベル数に対応する。図１に示す例においては、「Ｙ」の列数を示す（ｍ＋１）は、不正ラベルと正当ラベルとの２つのラベル数を示すｍである２に、ダミーラベルのラベル数を示す１を加えた３（＝２＋１）になる。例えば、「Ｙ」の１列目は、不正ラベルに対応する割当値が割り当てられ、「Ｙ」の２列目は、正当ラベルに対応する割当値が割り当てられ、「Ｙ」の３列目は、ダミーラベルに対応する割当値が割り当てられる。つまり、図１に示す例においては、「Ｙ」は、１８行３列の行列となる。また、上記式（１）中のラベル数を示す「ＬＡＢＥＬ」は、不正ラベルと正当ラベルとの２つのラベル数を示すｍである２に、ダミーラベルのラベル数を示す１を加えた３となる。なお、上記式（１）に示す「Ｙｌ」は、「Ｙ」におけるｌ列の行列を示す。例えば、ｌが２である場合、「Ｙ」の２列目の成分に対応するｖ行１列の行列を示す。
【００４５】
上述のように、本実施形態においては、「Ｙ」の各成分は、割当値情報記憶部１２３に記憶される各ラベルに対応する割当値が割り当てられる。ここで、各ラベルに対応する割当値の算出について説明する。生成部１３２は、以下の式（２）により各ラベルに対応する割当値を算出する。
【００４６】
【数２】
0006333213.tif 000003
【００４７】
上記式（２）の左辺中の「Ｙｖｌ」は、「Ｙ」におけるｖ行ｌ列の成分に対応する。例えば、ｖが１でありｌが１である「Ｙ」における１行１列、「Ｙ１１」は、ノードＩＤ「Ｎ１」により識別されるノードの不正ラベルに対応する割当値を示す。また、ｖが１でありｌが２である「Ｙ」における１行２列、「Ｙ１２」は、ノードＩＤ「Ｎ１」により識別されるノードの正当ラベルに対応する割当値を示し、ｖが１でありｌが３である「Ｙ」における１行３列、「Ｙ１３」は、ノードＩＤ「Ｎ１」により識別されるノードのダミーラベルに対応する割当値を示す。このように、「Ｙｖｌ」は、ノードＩＤ「Ｎｖ」により識別されるノードのラベルｌの重みを示す。
【００４８】
上記式（２）により、不当ラベルに対応する列である「Ｙ」におけるｖ行１列の成分には、ノード毎に算出されるパラメータ「α」または「０」が割り当てられる。上記式（２）中の「Ｆ」は、不正行為を行う主体に対応するノードの集合を示す。図１に示す例においては、「Ｆ」には、ノードＮ２，Ｎ３，Ｎ９，Ｎ１０が含まれる。つまり、「Ｆ」には、不正シードとなるノードが含まれる。ここに、ノードＮ２，Ｎ３，Ｎ９，Ｎ１０に対応する「Ｙｖ１」には、パラメータ「α」が割当値として割り当てられ、他のノードに対応する「Ｙｖ１」には、「０」が割当値として割り当てられる。ここで、パラメータ「α」は、ノードに連結された不正シードの数となる。例えば、ノードＮ２は、不正シードであるノードＮ３と連結されるため、ノードＮ２のパラメータ「α」は、１となる。そのため、「Ｙ２１」には、１が割当値として割り当てられる。「Ｆ」に含まれる他のノードＮ３，Ｎ９，Ｎ１０に対応する「Ｙ３１」、「Ｙ９１」、「Ｙ１０１」にも、１が割当値として割り当てられる。
【００４９】
また、上記式（２）により、正当ラベルに対応する列である「Ｙ」におけるｖ行２列の成分には、ノード毎に算出されるパラメータ「β」または「０」が割り当てられる。上記式（２）中の「Ｓ」は、正当行為を行う主体に対応するノードの集合を示す。例えばノードＮ８及びノードＮ１６に正当ラベルが割り当てられた場合、「Ｓ」には、ノードＮ８及びノードＮ１６が含まれる。なお、パラメータ「β」については、ノードに連結された正当シードの数となる。なお、ダミーラベルに対応する列である「Ｙ」におけるｖ行３列の成分には、全て「０」が割り当てられる。ここに、上記式（２）により、「Ｙ」中の各成分は、０以上の実数である。また、生成部１３２は、算出した割当値情報を割当値情報記憶部１２３へ格納する。
【００５０】
また、上記式（１）中の予測値行列「Ｙ＾」（上記式（１）においては、“Ｙ”の上に“＾”を冠した表記がされる。明細書中においては単に「Ｙ＾」と表記する）は、ｎ行（ｍ＋１）列の行列により表され、学習により導出されるラベル情報を示す。ここで、「Ｙ＾」の行数及び列数は、「Ｙ」と同等である。例えば、「Ｙ＾」の１行目は、ノードＩＤ「Ｎ１」により識別されるノードに関する情報が割り当てられ、「Ｙ＾」の２行目は、ノードＩＤ「Ｎ２」により識別されるノードに関する情報が割り当てられる。例えば、「Ｙ＾」の１列目は、不正ラベルに対応する予測値が割り当てられ、「Ｙ＾」の２列目は、正当ラベルに対応する予測値が割り当てられ、「Ｙ＾」の３列目は、ダミーラベルに対応する予測値が割り当てられる。つまり、図１に示す例においては、「Ｙ＾」は、「Ｙ」と同様に１８行３列の行列となる。なお、上記式（１）に示す「Ｙ＾ｌ」は、「Ｙ＾」におけるｌ列の行列を示す。例えば、ｌが２である場合、「Ｙ＾」の２列目の成分に対応するｖ行１列の行列を示す。
【００５１】
また、上記式（１）中の「Ｓ」は、シードとなるノードの位置を、各成分を実数とするｎ行ｎ列の行列により表す。例えば、「Ｓ」は、シードとなるノードに対応する成分以外が０となる対角行列である。例えば、ノードＮ２がシードである場合、「Ｓ」の２行２列の成分は、０以外の値となる。また、上記式（１）中の「Ｌ」は、非特許文献１に示されれるラプラシアン行列Ｌに対応する。例えば、「Ｌ」は、重み付きエッジの定義に対応する。また、上記式（１）中の「Ｒ」は、ｎ行（ｍ＋１）列の行列により表され、ノード毎のラベルの事前行列を示す。例えば、「Ｒ」は、ランダムウォークと関連する。「Ｓ」、「Ｌ」、「Ｒ」の各成分の値については、例えば、非特許文献１に従う。
【００５２】
なお、上記式（１）中の「μ１」〜「μ３」は、ハイパーパラメータである。例えば、生成部１３２は、グラフ情報等に基づいて統計的手法等の種々の技術により推定されたハイパーパラメータ「μ１」〜「μ３」を用いてもよいし、判定装置１００の管理者等により設定されたハイパーパラメータ「μ１」〜「μ３」を用いてもよい。なお、上記式（１）の大括弧（“［”、“］”）内の「ＸＴ」については、対応するＸの転置行列を示す。例えば、大括弧内の１項目中の、（Ｙｌ−Ｙ＾ｌ）Ｔは、（Ｙｌ−Ｙ＾ｌ）の差の転置行列を表す。また、大括弧内の３項目は、ハイパーパラメータ「μ３」に（Ｙ＾ｌ−Ｒｌ）の差の２乗ノルムを乗算する。
【００５３】
生成部１３２は、上記式（１）に基づいて学習を行うことにより、適切な「Ｙ＾」を導出する。具体的には、以下の式（３）が最小となるように「Ｙ＾」を導出する。上述したように、生成部１３２は、各ノードに対応する主体のネットワーク上での行動における不正行為の有無に関する情報として、ラベル毎の予測値を導出する。例えば、生成部１３２は、図６に示すような予測値情報を各ノードに対応する主体のネットワーク上での行動における不正行為の有無に関する情報として生成する。生成部１３２は、生成した予測値情報を予測値情報記憶部１２４へ格納する。
【００５４】
次に、生成部１３２は、各ノードにおけるラベル毎の予測値を用いてスコアを算出する。具体的には、生成部１３２は、各ノードのスコアを以下の式（３）により算出する。
【００５５】
【数３】
0006333213.tif 000004
【００５６】
上記式（３）の左辺中のスコア「φ（ｖ，Ｙ＾）」（「φ」は、上記式（３）中と表記が異なるが、同一のもの（ファイ）とし、明細書中においては単に「φ」と表記する）は、ノードＩＤ「Ｎｖ」により識別されるノードの予測値「Ｙ＾」に基づくスコアを示す。
【００５７】
例えば、ノードＮ１のスコア「φ（１，Ｙ＾）」は、図６に示す予測値情報に基づいて算出される。具体的には、ノードＮ１のスコア「φ（１，Ｙ＾）」は、０．３（＝０．３／（０．３＋０．３＋０．４））となる。また、ノードＮ３のスコア「φ（３，Ｙ＾）」は、０．８（＝１．２／（１．２＋０＋０．３））となる。
【００５８】
生成部１３２は、上記式（３）により算出したスコアに基づいて、順位付けを行ったスコア情報を、各ノードに対応する主体のネットワーク上での行動における不正行為の有無に関する情報として生成する。具体的には、生成部１３２は、図７に示すスコア情報を生成する。また、生成部１３２は、生成したスコア情報をスコア情報記憶部１２５へ格納する。
【００５９】
なお、生成部１３２は、上記式（３）に代えて、ダミーラベルに関する予測値を除外した以下の式（４）により、各ノードのスコアを算出してもよい。
【００６０】
【数４】
0006333213.tif 000005
【００６１】
（判定部１３３）
判定部１３３は、生成部１３２により生成された不正行為の有無に関する情報により、スコアに基づいて、所定の条件を満たすノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定する。以下では、図１に示す例において、生成部１３２が図７に示すスコア情報を生成した場合を例に説明する。
【００６２】
本実施形態における判定部１３３は、生成部１３２が各ノードにおけるラベル毎の予測値を用いて算出したスコアに基づいて順位付けされたノードのうち、順位が所定の条件を満たすノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定する。判定部１３３は、順位が９位以内であることを順位が所定の条件を満たす場合の一例として、順位１位〜９位までのノードを不正ノードとして判定する。図７に示すスコア情報において、順位１位〜９位までにはノードＮ２〜Ｎ４，Ｎ９〜Ｎ１４の９個のノードが含まれる。そこで、判定部１３３は、ノードＮ２〜Ｎ４，Ｎ９〜Ｎ１４の９個のノードの各々に対応する主体がネットワーク上での行動における不正行為を行ったと判定する。
【００６３】
なお、上記の例においては、順位が９位以内であることを順位が所定の条件を満たす場合の一例として示したが、判定部１３３は、所定の条件を例えばノード数に応じて適宜設定してもよい。また、判定部１３３は、所定の閾値を設定し、設定した閾値以上のスコアが算出されたノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定してもよい。
【００６４】
〔３．生成処理のフロー〕
次に、図８を用いて、実施形態に係る判定装置１００による生成処理の手順について説明する。図８は、実施形態に係る判定装置１００による生成処理手順を示すフローチャートである。
【００６５】
図８に示すように、判定装置１００の取得部１３１は、グラフ情報を取得する（ステップＳ１０１）。そして、生成部１３２は、取得部１３１により取得されたグラフ情報にシードを設定する（ステップＳ１０２）。例えば、生成部１３２は、グラフ情報中において予め不正行為を行う主体であると特定された主体に対応するノードを不正シードとして設定する。
【００６６】
その後、生成部１３２は、各ノードにおけるラベル毎の割当値を算出し、設定する（ステップＳ１０３）。そして、生成部１３２は、割当値に基づいて学習を行う（ステップＳ１０４）。生成部１３２は、ステップＳ１０４における学習により、各ノードのラベル毎の予測値を導出する（ステップＳ１０５）。
【００６７】
続けて、生成部１３２は、ステップＳ１０５で導出した予測値に基づいて、各ノードのスコアを算出する（ステップＳ１０６）。そして、生成部１３２は、ステップＳ１０６で算出したスコアに基づいて、ノードの順位付を行う（ステップＳ１０７）。
【００６８】
その後、判定装置１００の判定部１３３は、スコアに基づいて順位付されたノードのうち、上位から所定数のノードを不正ノードと判定する（ステップＳ１０８）。
【００６９】
〔４．効果〕
上述してきたように、実施形態に係る判定装置１００は、取得部１３１と、生成部１３２とを有する。取得部１３１は、ネットワーク上における行動の主体の各々に対応する複数のノードと、行動における関係を有するノード間を連結するエッジとを含むグラフを取得する。生成部１３２は、取得部１３１により取得されたグラフにおける複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、複数のノードの各々に対応する主体の行動における不正行為の有無に関する情報を生成する。
【００７０】
これにより、実施形態に係る判定装置１００は、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。判定装置１００は、複数のノードとノード間を連結するエッジを含むグラフを不正検知に応用することにより、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成し、不正ノードを精度よく判定することができる。
【００７１】
また、実施形態に係る判定装置１００において、生成部１３２は、不正行為に関するラベルとして不正行為を示すラベルが割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、複数のノードの各々に対応する主体の行動における不正行為の有無に関する情報を生成する。
【００７２】
これにより、実施形態に係る判定装置１００は、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。また、判定装置１００は、不正ラベルが割り当てられた不正シードに応じて各ノードに割り当てられる割当値に基づいて、学習を行うことにより、適切に予測値を導出することができる。
【００７３】
また、実施形態に係る判定装置１００において、生成部１３２は、各ノードと連結する他のノードに割り当てられたラベルに応じて各ノードにおけるラベル毎の割当値を算出し、割当値に基づいて学習される各ノードにおけるラベル毎の予測値を学習結果として、各ノードに対応する主体の行動における不正行為の有無に関する情報を生成する。
【００７４】
これにより、実施形態に係る判定装置１００は、割当値に基づいて学習される各ノードにおけるラベル毎の予測値に基づいて、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。
【００７５】
また、実施形態に係る判定装置１００において、生成部１３２は、各ノードにおけるラベル毎の予測値を用いて算出されるスコアに基づいて、各ノードに対応する主体の行動における不正行為の有無に関する情報を生成する。
【００７６】
これにより、実施形態に係る判定装置１００は、各ノードにおけるラベル毎の予測値を用いて算出されるスコアに基づいて、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。
【００７７】
また、実施形態に係る判定装置１００は、判定部１３３を有する。判定部１３３は、生成部１３２により算出されたスコアに基づいて、所定の条件を満たすノードに対応する主体が行動における不正行為を行ったと判定する。
【００７８】
これにより、実施形態に係る判定装置１００は、行動における不正行為を行った主体を適切に判定することができる。
【００７９】
また、実施形態に係る判定装置１００において、判定部１３３は、スコアに基づいて順位付けされた複数のノードのうち、順位が所定の条件を満たすノードに対応する主体が行動における不正行為を行ったと判定する。
【００８０】
これにより、実施形態に係る判定装置１００は、行動における不正行為を行った主体を適切に判定することができる。また、判定装置１００は、導出した予測値に基づいて算出されたスコアに基づいて、各ノードを順位付けすることにより、不正ノードを精度よく判定することができる。
【００８１】
〔５．変形例〕
上述した実施形態に係る判定装置１００は、上記実施形態以外にも種々の異なる形態にて実施されてもよい。そこで、以下では、判定装置１００の他の実施形態について説明する。
【００８２】
〔５−１．生成処理〕
上述した実施形態において、判定装置１００は、各ノードについて予測値に基づいて算出されたスコアに基づいて、ノードの各々に対応する主体がネットワーク上での行動における不正行為を行ったと判定する。しかしながら、変形例に係る判定装置１００Ａは、各ノードにおけるスコア（変形例においては、「第１スコア」と称する）に加えて、各ノードに連結されたノードにおける第１スコア及び連結されたノードとの間において入札された商品の数（すなわち、エッジの重み）により算出された第２スコアに基づいて、ノードの各々に対応する主体がネットワーク上での行動における不正行為を行ったと判定する点において、実施形態に係る判定装置１００と相違する。この点について、図９〜図１３を用いて説明する。図９は、変形例に係る生成処理の一例を示す図である。なお、実施形態と同様の内容については、説明を省略する。
【００８３】
図９に示す例においては、グラフＧ２１には１８個のノードＮ１〜Ｎ１８が含まれる。なお、図９に示すグラフＧ２２は、生成処理後（判定後）のグラフを示し、ノード数やエッジの連結については生成処理前（判定前）のグラフＧ２１と同様である。まず、判定装置１００Ａは、図１左側の生成処理前（判定前）のグラフＧ２１に示すように、予め不正行為を行う主体であると特定された主体に対応するノードに不正ラベルを割り当てる。図９に示す例においては、判定装置１００Ａは、ノードＮ２、ノードＮ３、ノードＮ９、及びノードＮ１０の４個のノードを不正シードとして不正ラベルを割り当てる。
【００８４】
その後、判定装置１００Ａは、各ノードと連結する他のノードに割り当てられたラベルに応じて各ノードにおけるラベル毎の割当値を算出する。そして、判定装置１００Ａは、各ノードにおけるラベル毎の割当値に基づいて学習されるラベル毎の予測値を学習結果として、各ノードに対応する主体のネットワーク上での行動における不正行為の有無に関する情報を生成する。判定装置１００Ａは、各ノードにおけるラベル毎の予測値を用いて算出されるスコアに基づいて、所定の条件を満たすノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定する。具体的には、判定装置１００Ａは、各ノードにおけるラベル毎の予測値を用いて算出されるスコアに基づいて順位付けされたノードのうち、順位が所定の条件を満たすノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定する。図９に示す例においては、順位が９位以内であることを順位が所定の条件を満たす場合の一例として、順位１位〜９位までのノードを不正ノードとして判定する。
【００８５】
上記の生成処理により、図９右側に示す生成処理後（判定後）のグラフＧ２２に示すように、不正シードであるノードＮ２、ノードＮ３、ノードＮ９、及びノードＮ１０を含む９個のノードが不正ノードとして判定される。例えば、不正シードであるノードＮ２やノードＮ３と連結するノードＮ１やノードＮ４が不正ノードとして判定される。また、不正シードであるノードＮ９やノードＮ１０と２部グラフを形成するノードＮ１１〜Ｎ１３も不正ノードとして判定される。このように、図９に示す例においては、図１に示す例で不正ノードと判定されたノードＮ１４に代えて、ノードＮ１が不正ノードと判定される。
【００８６】
〔５−２．判定装置の構成〕
次に、図１０を用いて、実施形態に係る判定装置１００Ａの構成について説明する。図１０は、変形例に係る判定装置の構成例を示す図である。なお、判定装置１００Ａにおいて、実施形態に係る判定装置１００と同様の構成は、同一の符号を付して説明を省略する。
【００８７】
図１０に示すように、判定装置１００Ａは、記憶部１２０Ａに第１スコア情報記憶部１２５Ａ及び第２スコア情報記憶部１２６を有する点において判定装置１００と相違する。図１１は、変形例に係る第１スコア情報記憶部の一例を示す図である。なお、上述したように、変形例における第１スコアは、実施形態におけるスコアと同様であり、第１スコア情報記憶部１２５Ａの項目「第１スコア」ついては、図７に示す実施形態におけるスコア情報記憶部１２５の項目「スコア」と同様の情報が記憶される。すなわち、第１スコアは、実施形態に係る式（３）または（４）に基づいて、実施形態におけるスコアと同様に算出される。
【００８８】
（第２スコア情報記憶部１２６）
実施形態に係る第２スコア情報記憶部１２６は、第２スコア情報を記憶する。図１２は、変形例に係る第２スコア情報記憶部の一例を示す図である。図１２に示す例においては、スコアが高い方から順に順位付されたノードに関する情報が記憶される。図１２に示すように、第２スコア情報記憶部１２６は、スコア情報として、「順位」、「ノードＩＤ」、「第２スコア」の項目を有する。なお、項目は上記に限らず、第２スコア情報記憶部１２６は、目的に応じて種々の項目を有してもよい。
【００８９】
「順位」は、各ノードのスコアに基づく順位を示す。「ノードＩＤ」は、各ノードを識別する識別情報を示す。「第２スコア」は、各ノードにおける第１スコアに加えて、各ノードに連結されたノードにおける第１スコア及び連結されたノード間のエッジの重みにより算出された第２スコアを示す。
【００９０】
例えば、図１２に示す例においては、順位「１」のノードはノードＩＤ「Ｎ２」により識別されるノードであり、第２スコアは「３．５」であることを示す。順位「２」のノードはノードＩＤ「Ｎ９」により識別されるノードであり、スコアは「２．９」であることを示す。第２スコア算出等の詳細は後述するが、第２スコアが高い程、不正行為を行った主体に対応するノードである可能性が高いことを示す。
【００９１】
ここで、制御部１３０Ａの生成部１３２Ａは、各ノードにおけるラベル毎の予測値を用いて算出される第１スコアと、他のノードにおける第１スコアと、各ノードと他のノードと間における一方は出品した商品へ他方が入札した商品の数に応じて各ノードと他のノードとを連結するエッジに付された重みと、により算出される第２スコアに基づいて、各ノードに対応する主体のネットワーク上での行動における不正行為の有無に関する情報を生成する。
【００９２】
具体的には、生成部１３２Ａは、各ノードの第２スコアを以下の式（５）により算出する。
【００９３】
【数５】
0006333213.tif 000006
【００９４】
上記式（５）の左辺中の第２スコア「ρ（ｖ，Ｙ＾）」は、ノードＩＤ「Ｎｖ」により識別されるノードの予測値「Ｙ＾」に基づく第２スコアを示す。
【００９５】
ここで、上記式（５）の右辺中の各項について説明する。１項目の「φ（ｖ，Ｙ＾）」は、ノードＩＤ「Ｎｖ」により識別されるノードの第１スコアに対応する。例えば、「φ（ｖ，Ｙ＾）」は、式（３）により算出される。
【００９６】
次に、上記式（５）の右辺中の２項目について説明する。「Ｎ（ｖ）」は、ノードＩＤ「Ｎｖ」により識別されるノードに連結するノードを示す。「｜Ｎ（ｖ）｜」は、ノードＩＤ「Ｎｖ」により識別されるノードに連結するノード数を示す。また、「γ」は、所定のパラメータである。例えば、生成部１３２Ａは、グラフ情報等に基づいて統計的手法等の種々の技術により推定されたパラメータ「γ」を用いてもよいし、判定装置１００Ａの管理者等により設定されたパラメータ「γ」を用いてもよい。「Ｗuv」は、ノードＩＤ「Ｎｖ」により識別されるノードと、ノードＩＤ「Ｎｕ」により識別されるノードとの間を連結するエッジの重みを示す。例えば、図９に示す例において、「Ｗ１２」は１０となり、「Ｗ３４」は４となる。「φ（ｕ，Ｙ＾）」は、ノードＩＤ「Ｎｕ」により識別されるノードの第１スコアに対応する。例えば、「φ（ｕ，Ｙ＾）」は、式（３）により算出される。
【００９７】
このように、生成部１３２Ａは、各ノードにおける第１スコアに加えて、各ノードに連結されたノードにおける第１スコア及び連結されたノードとの間のエッジの重みに基づいて第２スコアを算出する。これにより、生成部１３２Ａは、周囲のノードの影響を反映し、より適切に不正ノードを判定することができる第２スコアを算出する。
【００９８】
生成部１３２Ａは、上記式（５）により算出した第２スコアに基づいて、順位付けを行ったスコア情報を、各ノードに対応する主体のネットワーク上での行動における不正行為の有無に関する情報として生成する。具体的には、生成部１３２Ａは、図１２に示す第２スコア情報を生成する。また、生成部１３２Ａは、生成した第２スコア情報を第２スコア情報記憶部１２６へ格納する。
【００９９】
制御部１３０Ａの判定部１３３Ａは、生成部１３２Ａにより生成された不正行為の有無に関する情報により、第２スコアに基づいて、所定の条件を満たすノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定する。具体的には、判定部１３３Ａは、生成部１３２Ａにより生成された不正行為の有無に関する情報により、第２スコアに基づいて順位付けされた複数のノードのうち、順位が所定の条件を満たすノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定する。以下では、図９に示す例において、生成部１３２Ａが図１２に示す第２スコア情報を生成した場合を例に説明する。
【０１００】
判定部１３３Ａは、生成部１３２Ａが各ノードにおけるラベル毎の予測値を用いて算出される第１スコアと、他のノードにおける第１スコアと、各ノードと他のノードとの間における一方は出品した商品へ他方が入札した商品の数に応じて各ノードと他のノードとを連結するエッジに付された重みと、により算出した第２スコアに基づいて順位付けされたノードのうち、順位が所定の条件を満たすノードに対応する主体がネットワーク上での行動における不正行為を行ったと判定する。判定部１３３Ａは、順位が９位以内であることを順位が所定の条件を満たす場合の一例として、順位１位〜９位までのノードを不正ノードとして判定する。図１２に示す第２スコア情報において、順位１位〜９位までにはノードＮ１〜Ｎ４，Ｎ９〜Ｎ１３の９個のノードが含まれる。そこで、判定部１３３Ａは、ノードＮ１〜Ｎ４，Ｎ９〜Ｎ１３の９個のノードの各々に対応する主体がネットワーク上での行動における不正行為を行ったと判定する。
【０１０１】
〔５−３．生成処理のフロー〕
次に、図１３を用いて、変形例に係る判定装置１００Ａによる生成処理の手順について説明する。図１３は、変形例に係る判定装置による生成処理手順を示すフローチャートである。
【０１０２】
図１３に示すように、判定装置１００Ａの取得部１３１は、グラフ情報を取得する（ステップＳ２０１）。そして、生成部１３２Ａは、取得部１３１により取得されたグラフ情報にシードを設定する（ステップＳ２０２）。例えば、生成部１３２Ａは、グラフ情報中において予め不正行為を行う主体であると特定された主体に対応するノードを不正シードとして設定する。
【０１０３】
その後、生成部１３２Ａは、各ノードにおけるラベル毎の割当値を算出し、設定する（ステップＳ２０３）。そして、生成部１３２Ａは、割当値に基づいて学習を行う（ステップＳ２０４）。生成部１３２Ａは、ステップＳ２０４における学習により、各ノードのラベル毎の予測値を導出する（ステップＳ２０５）。
【０１０４】
続けて、生成部１３２Ａは、ステップＳ２０５で導出した予測値に基づいて、各ノードの第１スコアを算出する（ステップＳ２０６）。そして、生成部１３２Ａは、ステップＳ２０６で算出した第１スコア及びエッジの重みに基づいて、第２スコアを算出する（ステップＳ２０７）。そして、生成部１３２Ａは、ステップＳ２０７で算出した第２スコアに基づいて、ノードの順位付を行う（ステップＳ２０８）。
【０１０５】
その後、判定装置１００Ａの判定部１３３Ａは、第２スコアに基づいて順位付されたノードのうち、上位から所定数のノードを不正ノードと判定する（ステップＳ２０９）。
【０１０６】
〔５−４．効果〕
上述してきたように、変形例に係る判定装置１００Ａは、取得部１３１と、生成部１３２Ａとを有する。取得部１３１は、ネットワーク上における行動の主体の各々に対応する複数のノードと、行動における関係を有するノード間を連結するエッジとを含むグラフを取得する。生成部１３２Ａは、取得部１３１により取得されたグラフにおける複数のノードのうち、不正行為に関する情報が割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、複数のノードの各々に対応する主体の行動における不正行為の有無に関する情報を生成する。
【０１０７】
これにより、変形例に係る判定装置１００Ａは、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。判定装置１００Ａは、複数のノードとノード間を連結するエッジを含むグラフを不正検知に応用することにより、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成し、不正ノードを精度よく判定することができる。
【０１０８】
また、変形例に係る判定装置１００Ａにおいて、生成部１３２Ａは、不正行為に関するラベルとして不正行為を示すラベルが割り当てられたノードとの連結に関する情報を用いて得られた学習結果に基づいて、複数のノードの各々に対応する主体の行動における不正行為の有無に関する情報を生成する。
【０１０９】
これにより、変形例に係る判定装置１００Ａは、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。また、判定装置１００Ａは、不正ラベルが割り当てられた不正シードに応じて各ノードに割り当てられる割当値に基づいて、学習を行うことにより、適切に予測値を導出することができる。
【０１１０】
また、変形例に係る判定装置１００Ａにおいて、生成部１３２Ａは、各ノードと連結する他のノードに割り当てられたラベルに応じて各ノードにおけるラベル毎の割当値を算出し、割当値に基づいて学習される各ノードにおけるラベル毎の予測値を学習結果として、各ノードに対応する主体の行動における不正行為の有無に関する情報を生成する。
【０１１１】
これにより、変形例に係る判定装置１００Ａは、割当値に基づいて学習される各ノードにおけるラベル毎の予測値に基づいて、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。
【０１１２】
また、変形例に係る判定装置１００Ａにおいて、生成部１３２Ａは、各ノードにおけるラベル毎の予測値を用いて算出される第１スコアと、他のノードにおける第１スコアと、各ノードと他のノードとの行動の回数に応じて各ノードと他のノードとを連結するエッジに付された重みと、により算出される第２スコアに基づいて、各ノードに対応する主体の行動における不正行為の有無に関する情報を生成する。
【０１１３】
これにより、変形例に係る判定装置１００Ａは、ネットワーク上の行動における不正行為の有無に関する情報を適切に生成することができる。また、判定装置１００Ａは、各ノードにおける第１スコアに加えて、各ノードに連結されたノードにおける第１スコア及び連結されたノードとの間のエッジの重みに基づいて第２スコアを算出することにより、周囲のノードの影響を反映し、より適切に不正ノードを判定することができる第２スコアを算出することができる。
【０１１４】
また、変形例に係る判定装置１００Ａは、判定部１３３Ａを有する。判定部１３３Ａは、生成部１３２Ａにより算出された第２スコアに基づいて、所定の条件を満たすノードに対応する主体が行動における不正行為を行ったと判定する。
【０１１５】
これにより、変形例に係る判定装置１００Ａは、各ノードに連結されたノードにおける第１スコア及び連結されたノードとの間のエッジの重みに基づいて算出された第２スコアに基づいて、行動における不正行為を行った主体を適切に判定することができる。
【０１１６】
また、変形例に係る判定装置１００Ａにおいて、判定部１３３Ａは、第２スコアに基づいて順位付けされた複数のノードのうち、順位が所定の条件を満たすノードに対応する主体が行動における不正行為を行ったと判定する。
【０１１７】
これにより、変形例に係る判定装置１００Ａは、行動における不正行為を行った主体を適切に判定することができる。また、判定装置１００Ａは、導出した予測値に基づいて算出された第２スコアに基づいて、各ノードを順位付けすることにより、不正ノードを精度よく判定することができる。
【０１１８】
〔６．ネットワーク上における行動〕
なお、上記実施形態及び変形例においては、ネットワーク上における行動の一例として、インターネットオークションにおける行動について説明したが、判定装置１００，１００Ａは、インターネットオークションに限らず、複数ユーザが絡む不正が発生し得る種々のサービス（例えば、レビュー、掲示板、ＳＮＳ（Social  Networking  Service）、クラウドソーシングなど）でのユーザ（主体）の行動における不正行為の有無に関する情報を生成するに適用してもよい。例えば、判定装置１００，１００Ａは、ＳＮＳにおいて、所定の評価を行ったり、コメントしたり、アクセスしたりするユーザ（主体）の行動における不正行為の有無に関する情報を生成するに適用してもよい。すなわち、判定装置１００，１００Ａは、複数ユーザが絡むネットワーク上における行動に関する不正行為、例えば全てのサクラ行為に対して、適用することが可能である。
【０１１９】
〔７．ハードウェア構成〕
上述してきた実施形態に係る判定装置１００及び変形例に係る判定装置１００Ａは、例えば図１４に示すような構成のコンピュータ１０００によって実現される。図１４は、判定装置の機能を実現するコンピュータの一例を示すハードウェア構成図である。コンピュータ１０００は、ＣＰＵ１１００、ＲＡＭ１２００、ＲＯＭ１３００、ＨＤＤ１４００、通信インターフェイス（Ｉ／Ｆ）１５００、入出力インターフェイス（Ｉ／Ｆ）１６００、及びメディアインターフェイス（Ｉ／Ｆ）１７００を有する。
【０１２０】
ＣＰＵ１１００は、ＲＯＭ１３００またはＨＤＤ１４００に格納されたプログラムに基づいて動作し、各部の制御を行う。ＲＯＭ１３００は、コンピュータ１０００の起動時にＣＰＵ１１００によって実行されるブートプログラムや、コンピュータ１０００のハードウェアに依存するプログラム等を格納する。
【０１２１】
ＨＤＤ１４００は、ＣＰＵ１１００によって実行されるプログラム、及び、かかるプログラムによって使用されるデータ等を格納する。通信インターフェイス１５００は、所定のネットワークＮを介して他の機器からデータを受信してＣＰＵ１１００へ送り、ＣＰＵ１１００が生成したデータを所定のネットワークＮを介して他の機器へ送信する。
【０１２２】
ＣＰＵ１１００は、入出力インターフェイス１６００を介して、ディスプレイやプリンタ等の出力装置、及び、キーボードやマウス等の入力装置を制御する。ＣＰＵ１１００は、入出力インターフェイス１６００を介して、入力装置からデータを取得する。また、ＣＰＵ１１００は、生成したデータを入出力インターフェイス１６００を介して出力装置へ出力する。
【０１２３】
メディアインターフェイス１７００は、記録媒体１８００に格納されたプログラムまたはデータを読み取り、ＲＡＭ１２００を介してＣＰＵ１１００に提供する。ＣＰＵ１１００は、かかるプログラムを、メディアインターフェイス１７００を介して記録媒体１８００からＲＡＭ１２００上にロードし、ロードしたプログラムを実行する。記録媒体１８００は、例えばＤＶＤ（Digital  Versatile  Disc）、ＰＤ（Phase  change  rewritable  Disk）等の光学記録媒体、ＭＯ（Magneto-Optical  disk）等の光磁気記録媒体、テープ媒体、磁気記録媒体、または半導体メモリ等である。
【０１２４】
例えば、コンピュータ１０００が実施形態に係る判定装置１００として機能する場合、コンピュータ１０００のＣＰＵ１１００は、ＲＡＭ１２００上にロードされたプログラムを実行することにより、制御部１３０の機能を実現する。コンピュータ１０００のＣＰＵ１１００は、これらのプログラムを記録媒体１８００から読み取って実行するが、他の例として、他の装置から所定のネットワークを介してこれらのプログラムを取得してもよい。
【０１２５】
以上、本願の実施形態のいくつかを図面に基づいて詳細に説明したが、これらは例示であり、発明の開示の行に記載の態様を始めとして、当業者の知識に基づいて種々の変形、改良を施した他の形態で本発明を実施することが可能である。
【０１２６】
〔８．その他〕
また、上記実施形態及び変形例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。例えば、各図に示した各種情報は、図示した情報に限られない。
【０１２７】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、不正行為の有無に関する情報を生成する装置と、主体がネットワーク上での行動における不正行為を行ったと判定する装置は別体であってもよい。例えば、不正行為の有無に関する情報を生成する生成装置は、通信部と、取得部及び生成部を有する制御部とを備えてもよい。また、上記の生成装置は、割当値情報記憶部、予測値情報記憶部、及びスコア情報記憶部等を有する記憶部を備えてもよい。また、上記の生成装置は、割当値情報記憶部、予測値情報記憶部、及びスコア情報記憶部等を有さず、外部の記憶装置から各種情報を取得してもよい。また、上記の生成装置は、スコア情報記憶部に代えて、第１スコア情報記憶部及び第２スコア情報記憶部を有してもよい。また、主体がネットワーク上での行動における不正行為を行ったと判定する装置は、判定部を備えてもよい。また、主体がネットワーク上での行動における不正行為を行ったと判定する装置は、生成装置から取得した予測値情報に基づいて、スコアを算出したり、第１スコア及び第２スコアを算出したりしてもよい。
【０１２８】
また、上述してきた各実施形態は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【０１２９】
また、上述してきた「部（section、module、unit）」は、「手段」や「回路」などに読み替えることができる。例えば、取得部は、取得手段や取得回路に読み替えることができる。
【符号の説明】
【０１３０】
１００  判定装置
１２１  行動情報記憶部
１２２  グラフ情報記憶部
１２３  割当値情報記憶部
１２４  予測値情報記憶部
１２５  スコア情報記憶部
１３０  制御部
１３１  取得部
１３２  生成部
１３３  判定部
【図１】
0006333213.tif 000007
【図２】
0006333213.tif 000008
【図３】
0006333213.tif 000009
【図４】
0006333213.tif 000010
【図５】
0006333213.tif 000011
【図６】
0006333213.tif 000012
【図７】
0006333213.tif 000013
【図８】
0006333213.tif 000014
【図９】
0006333213.tif 000015
【図１０】
0006333213.tif 000016
【図１１】
0006333213.tif 000017
【図１２】
0006333213.tif 000018
【図１３】
0006333213.tif 000019
【図１４】
0006333213.tif 000020