(57)【要約】  本発明は、検索ログの悪用を防止する方法を開示する。本発明の一実施例による検索ログ悪用防止方法は、検索ログから異常行為を検査する対象を選別する段階と、選別された対象に対して正常から外れた度合を点数化し、異常行為を検出する段階と、を含む。また、検索ログ悪用防止方法は、所定の減点ロジックを用いて、検出された異常行為を検索ログから除去し、検索ログを訂正する段階をさらに含むことができる。したがって、検索ログから検出された異常行為を效率的に除去することによって検索ログに対する悪用を防止し、検索ログをきれいに維持することができる。
2010511246.tif 000002
【特許請求の範囲】
【請求項１】
検索ログの悪用を防止する方法において、
前記検索ログから異常行為を検査する対象を選別する段階と、
前記選別された対象に対して正常から外れた度合を点数化し、異常行為を検出する段階と、
を含むことを特徴とする、検索ログ悪用防止方法。
【請求項２】
所定の減点ロジックを用いて前記検索ログから前記検出された異常行為を除去することによって、前記検索ログを訂正する段階をさらに含むことを特徴とする、請求項１に記載の検索ログ悪用防止方法。
【請求項３】
前記検査対象選別段階は、
前記検索ログから所定の時間ウィンドウ内に含まれた特定検索語の各ＩＰ別入力回数を統計的に解析した検索語要約情報及び特定ＩＰにおける各検索語の入力回数を統計的に解析したＩＰ要約情報のうち少なくとも一つを生成する段階を含み、
前記異常行為検出段階で、前記検索語要約情報及びＩＰ要約情報のうち少なくとも一つから前記異常行為を検出することを特徴とする、請求項２に記載の検索ログ悪用防止方法。
【請求項４】
前記要約情報生成段階は、
前記検索ログから所定の時間ウィンドウ内に含まれた特定検索語の各ＩＰ別入力回数ベクトル及び特定ＩＰにおける各検索語の入力回数ベクトルのうち少なくとも一つを生成する段階と、
前記検索語要約情報を生成するために前記特定検索語の各ＩＰ別入力回数ベクトルの次元を縮小したり、前記ＩＰ要約情報を生成するために前記特定ＩＰにおける各検索語の入力回数ベクトルの次元を縮小する段階を含むことを特徴とする、請求項３に記載の検索ログ悪用防止方法。
【請求項５】
前記入力回数ベクトルの次元縮小段階は、
ハッシュバケツ（hashed-bucket）を用いて前記特定検索語の各ＩＰ別入力回数ベクトル及び特定ＩＰにおける各検索語の入力回数ベクトルを、制限された数のバケツに対する回数ベクトルに変換することを特徴とする、請求項４に記載の検索ログ悪用防止方法。
【請求項６】
前記検索語要約情報及びＩＰ要約情報は、統計的方法を用いて多次元分布（Distribution）にモデリングされることを特徴とする、請求項３に記載の検索ログ悪用防止方法。
【請求項７】
前記異常行為検出段階は、
前記多次元分布にモデリングされた検索語要約情報及びＩＰ要約情報のうち少なくとも一つに対して中心から離れた度合によって異常の度合を点数として計算する段階と、
前記計算された点数が所定の基準値以上である検索語要約情報及びＩＰ要約情報のうち少なくとも一つに異常行為が含まれたと判断する段階と、
を含むことを特徴とする、請求項６に記載の検索ログ悪用防止方法。
【請求項８】
前記異常行為検出段階は、
前記計算段階以前に、前記モデリングされた検索語要約情報及びＩＰ要約情報のうち少なくとも一つの次元を縮小し、データを圧縮する段階をさらに含むことを特徴とする、請求項７に記載の検索ログ悪用防止方法。
【請求項９】
前記データ圧縮段階は、
入力データを互いに直交する座標系に写像（mapping）させる主成分分析（Principal Component Analysis）方法を用いて行なわれることを特徴とする、請求項８に記載の検索ログ悪用防止方法。
【請求項１０】
前記計算段階は、
前記縮小された次元の互いに独立した標準正規分布のサンプルの和を通じてモデリングされる統計値を用いて所定基準値に対する割合として異常の度合に対する点数を計算することを特徴とする、請求項８に記載の検索ログ悪用防止方法。
【請求項１１】
前記異常の度合に対する点数（Score）は、式
【数１】
2010511246.tif 000047
を用いて計算され、ここで、統計値
【数２】
2010511246.tif 000048
は互いに独立している標準正規分布のサンプルの和を通じてモデリングされる自由度ｄであるカイ二乗分布に従い、
【数３】
2010511246.tif 000049
は臨界値αを越えない正常範囲の最大境界を表すことを特徴とする、請求項１０に記載の検索ログ悪用防止方法。
【請求項１２】
前記
【数４】
2010511246.tif 000050
を越える全ての
【数５】
2010511246.tif 000051
は異常範囲に含まれると判断することを特徴とする、請求項１１に記載の検索ログ悪用防止方法。
【請求項１３】
前記減点ロジックは、母集団の確率模型と前記異常行為が検出された検索語要約情報及びＩＰ要約情報のうち少なくとも一つの確率模型間の分布の差を表すＫＬ距離（Kullback-Leibler Distance）を用いて前記異常行為を除去することを特徴とする、請求項６に記載の検索ログ悪用防止方法。
【請求項１４】
前記検索ログ訂正段階は、
分布の差を測定する情報理論を適用した減点ロジックを用いて、異常行為が検出された前記検索語要約情報及びＩＰ要約情報のうち少なくとも一つから異常行為を除去することを特徴とする、請求項３に記載の検索ログ悪用防止方法。
【請求項１５】
前記検査対象選別段階は、前記異常行為を検査する対象として検索語及び／またはＩＰを選別し、
前記異常行為検出段階で、前記選別された検索語及び／またはＩＰから異常行為を検出することを特徴とする、請求項１に記載の検索ログ悪用防止方法。
【請求項１６】
請求項１乃至１５のいずれか１項に記載の検索ログ悪用防止方法をコンピュータで実行させるためのプログラムを記録した、コンピュータ読み取り可能な記録媒体。
【請求項１７】
検索ログから異常行為を検査する対象を選別する前処理部と、
前記選別された対象に対して正常から外れた度合を点数化して異常行為を検出する異常行為検出部と、
所定の減点ロジックを用いて前記検索ログから前記検出された異常行為を除去し、前記検索ログを訂正する異常行為訂正部と、
を含むことを特徴とする、検索ログ悪用防止装置。
【請求項１８】
前記前処理部は、前記異常行為を検査する対象選別のために、前記検索ログから所定時間ウィンドウ内に含まれた特定検索語の各ＩＰ別入力回数を統計的に解析した検索語要約情報及び／または特定ＩＰにおける各検索語の入力回数を統計的に解析したＩＰ要約情報を生成し、
前記異常行為検出部は、前記検索語要約情報及び／またはＩＰ要約情報のうち少なくとも一つから前記異常行為を検出することを特徴とする、請求項１７に記載の検索ログ悪用防止装置。
【請求項１９】
前記検索語要約情報及び／またはＩＰ要約情報は、統計的方法を用いて多次元分布（distribution）にモデリングされることを特徴とする、請求項１８に記載の検索ログ悪用防止装置。
【請求項２０】
前記前処理部は、
前記特定検索語の各ＩＰ別入力回数ベクトルの次元を縮小して前記検索語要約情報を生成し、特定ＩＰにおける各検索語の入力回数ベクトルの次元を縮小して前記ＩＰ要約情報を生成することを特徴とする、請求項１９に記載の検索ログ悪用防止装置。
【請求項２１】
前記異常行為検出部は、
前記モデリングされた検索語要約情報及び／またはＩＰ要約情報に対して中心から離れた度合によって異常の度合を点数として計算し、前記計算された点数が所定の基準値以上である検索語要約情報及び／またはＩＰ要約情報に異常行為が含まれたと判断することを特徴とする、請求項１９に記載の検索ログ悪用防止装置。
【請求項２２】
前記異常行為検出部は、
前記点数を計算する以前に、前記モデリングされた検索語要約情報及び／またはＩＰ要約情報の次元を縮小し、データを圧縮することを特徴とする、請求項２１に記載の検索ログ悪用防止装置。
【請求項２３】
前記異常行為訂正部は、
分布の差を測定する情報理論を適用した減点ロジックを用いて、異常行為が検出された検索語要約情報及び／またはＩＰ要約情報から異常行為を除去することを特徴とする、請求項１９に記載の検索ログ悪用防止装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット検索に関するもので、特に、検索ログ（Search Logs）の悪用（Abusing）を效率的に防止する方法及びその装置に関する。
【背景技術】
【０００２】
近年、インターネットの発達によってインターネットを用いた多様なサービスがユーザーに提供されており、その最も代表的なものは検索サービスといえる。検索サービスとは、検索サービスプロバイダにより提供される検索サイトの検索窓にユーザーが検索語を入力すると、検索サービスプロバイダが、入力された検索語に相応する情報を検索結果として提供することを意味する。
【０００３】
このように検索サービスを利用するために各ユーザーが入力する検索語及び各ユーザーの検索行為に関する情報は検索ログの形態で保存され、検索サービスプロバイダは、このような検索ログを分析することによってユーザーに多様な検索サービスを提供することができる。
【０００４】
例えば、キーワード広告では、キーワードの人気度に基づいて課金が決定される。ここで、人気度とは、検索ログ分析を通じて獲得した検索語の様相に基づいて決定されるもので、このような人気度に基づいて検索サービスプロバイダは広告要請者に中立的で正当な課金根拠を提示することができる
また、検索サービスプロバイダは、検索ログを用いて様々な１次、２次サービスを提供している。例えば、人気検索語、関連検索語サービスなどは、検索ログを用いて現在ユーザーの関心を受けている検索語、連関性のある検索語を提示している。このようなサービスに成功できたのは、ぼう大な検索ログがインターネットユーザーの純粋な意図の産物という前提を満たしたためである。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、最近では、特定個人、特定集団の不正な意図が反映されるように検索ログに歪曲を加えようとする試みが増加してきている。これらの比重は今後も益々大きくなると推測される。このような検索ログの悪用（abusing）行為は検索ログを汚染させ、検索ログに依存している収益モデルの信頼墜落、サービスの品質低下を招くという問題点がある。
【０００６】
本発明は上記の問題点を解決するためのもので、その目的は、検索ログを追跡及び分析することによって、異常行為を検出し、汚染された部分を除去するための検索ログ悪用防止方法及びその装置を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するための本発明の一側面による検索ログ悪用防止方法は、検索ログから異常行為を検査する対象を選別する段階と、選別された対象に対して正常から外れた度合を点数化し、異常行為を検出する段階を含む。一実施例において、前記検索ログ悪用防止方法は、所定の減点ロジックを用いて、前記検索ログから前記検出された異常行為を除去することによって前記検索ログを訂正する段階をさらに含むことができる。
【０００８】
前記検査対象選別段階は、前記検索ログから所定の時間ウィンドウ内に含まれた特定検索語の各ＩＰ別入力回数を統計的に解析した検索語要約情報及び特定ＩＰにおける各検索語の入力回数を統計的に解析したＩＰ要約情報のうち少なくとも一つを生成する段階を含み、前記異常行為検出段階で、前記検索語要約情報及びＩＰ要約情報のうち少なくとも一つから前記異常行為を検出する。ここで、ＩＰとは、インターネットプロトコル(Internet Protocol)を意味する。
【０００９】
ここで、前記要約情報生成段階は、前記検索ログから所定の時間ウィンドウ内に含まれた特定検索語の各ＩＰ別入力回数ベクトル及び特定ＩＰにおける各検索語の入力回数ベクトルのうち少なくとも一つを生成する段階と、前記検索語要約情報を生成するために前記特定検索語の各ＩＰ別入力回数ベクトルの次元を縮小したり、前記ＩＰ要約情報を生成するために前記特定ＩＰにおける各検索語の入力回数ベクトルの次元を縮小する段階を含む。
【００１０】
一方、前記入力回数ベクトルの次元縮小段階は、ハッシュバケツ（hashed-bucket）を用いて前記特定検索語の各ＩＰ別入力回数ベクトル及び特定ＩＰにおける各検索語の入力回数ベクトルを、制限された数のバケツに対する回数ベクトルに変換する。
【００１１】
この時、前記検索語要約情報及びＩＰ要約情報は統計的方法を用いて多次元分布（Distribution）にモデリングされることを特徴とする。
【００１２】
一方、前記異常行為検出段階は、前記多次元分布にモデリングされた検索語要約情報及びＩＰ要約情報のうち少なくとも一つに対して中心から離れた度合によって異常の度合を点数として計算する段階と、前記計算された点数が所定の基準値以上である検索語要約情報及びＩＰ要約情報のうち少なくとも一つに異常行為が含まれたと判断する段階と、を含み、この時、前記異常行為検出段階は、前記計算段階以前に、前記モデリングされた検索語要約情報及びＩＰ要約情報のうち少なくとも一つの次元を縮小し、データを圧縮する段階をさらに含むことができる。
【００１３】
また、前記計算段階は、縮小された次元の互いに独立している標準正規分布のサンプルの和を通じてモデリングされる統計値を用いて所定基準値に対する割合として異常の度合に対する点数を計算する。
【００１４】
また、前記訂正段階は、分布の差を測定する情報理論を適用した減点ロジックを用いて、異常行為が検出された前記検索語要約情報及びＩＰ要約情報のうち少なくとも一つから異常行為を除去する段階を含む。
【００１５】
上述した目的を達成するための本発明の他の側面による検索ログ悪用防止装置は、検索ログから異常行為を検査する対象を選別する前処理部と、前記選別された対象に対して正常から外れた度合を点数化し、異常行為を検出する異常行為検出部と、所定の減点ロジックを用いて前記検索ログから前記検出された異常行為を除去し、前記検索ログを訂正する異常行為訂正部と、を含む。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施例による検索ログ悪用防止装置の概略ブロック図である。
【図２】本発明の一実施例による検索ログ悪用防止方法を示すフローチャートである。
【図３】本発明の一実施例による検査対象選別過程の詳細を示すフローチャートである。
【図４】本発明の一実施例による異常行為検出過程の詳細を示すフローチャートである。
【図５】異常行為検出過程で用いられる統計方法を説明するための参考図である。
【図６】本発明の一実施例による検索ログ訂正過程の詳細を示すフローチャートである。
【図７】検索ログ訂正過程で用いられる本発明の一実施例による減点ロジックを示す図である。
【図８】本発明の一実施例によるユーザーインターフェース画面を示す図である。
【図９】本発明の一実施例による検索ログ悪用防止装置の性能実験結果を示す図である。
【図１０】本発明の一実施例による検索ログ悪用防止装置の性能実験結果を示す図である。
【図１１】本発明の一実施例による検索ログ悪用防止装置の性能実験結果を示す図である。
【図１２】本発明の一実施例による検索ログ悪用防止装置の性能実験結果を示す図である。
【図１３】本発明の一実施例による検索ログ悪用防止装置の性能実験結果を示す図である。
【発明を実施するための形態】
【００１７】
以下、添付の図面を参照しつつ、本発明の好適な実施例について詳細に説明する。本発明を説明する上で、関連している公知機能または構成についての具体的な説明が本発明の要旨を曖昧にすると判断される場合には適宜省略するものとする。また、後述される用語は本発明における機能を考慮して定義されたもので、これらはユーザー、運用者の意図または慣例などによって異なってくることができる。したがって、各用語は、本明細書全般にわたる内容に基づいて定義されるべきである。
【００１８】
図１は、本発明の一実施例による検索ログ悪用防止装置の概略ブロック図である。同図で、検索ログ悪用防止装置は、前処理部１０、異常行為検出部２０、及び異常行為訂正部３０を含む。
【００１９】
前処理部１０は、検索ログから異常行為を検査する対象を選別する。ここで、検索ログ全体に対して異常行為を検査するのではなく、前処理部１０を通じて異常行為を検査する対象を選別する理由は、検索語の入力されたＩＰの数や検索語の数、またはそれらの組合せを考慮すると検索ログの数が多すぎになるためである。
【００２０】
このために、前処理部１０はまず、検査時点に注目されるＩＰ及び検索語候補を生成し、検査段階で使用する入力値を生成する。
【００２１】
前処理部１０は、検索ログから所定の時間ウィンドウ内に含まれた特定検索語のＩＰ別入力回数ベクトル及び／または特定ＩＰにおける各検索語の入力回数ベクトルを生成し、生成された各入力回数ベクトルの次元を縮小し、検索語要約情報及び／またはＩＰ要約情報を生成する。
【００２２】
このように、前処理部１０は、特定検索語のＩＰ別入力回数を統計的に解析した検索語要約情報、特定ＩＰにおける各検索語の入力回数を統計的に解析したＩＰ要約情報、またはこれらの組合せを生成し、生成された検索語要約情報及び／またはＩＰ要約情報は統計的方法を用いて多次元分布（distribution）にモデリングされることができる。
【００２３】
一方、本発明の他の実施例として、異常行為を検査する対象を減らすために、本出願人により先出願された韓国登録特許第５２２０２９号に記載された“実時間急上昇検索語検出方法及び実時間急上昇検索語検出システム”の概念を適用し、ある程度注目されている検索語及び／またはＩＰのみを検査対象として選定することができる。
【００２４】
異常行為検出部２０は、前処理部１０により選別された対象に対して正常から外れた度合を点数化し、選別された対象から異常行為を検出する。すなわち、統計方法論に基盤した点数技法を導入し、ＩＰ別及び／または検索語別異常行為に対する点数算定手順を行なう。
【００２５】
異常行為検出部２０は、統計的方法を用いて多次元分布（distribution）にモデリングされた検索語要約情報及び／またはＩＰ要約情報に対して中心から離れた度合によって異常の度合を点数として計算し、計算された点数が所定の基準値以上である検索語要約情報及び／またはＩＰ要約情報に異常行為が含まれたと判断する。この時、データ処理の効率を上げるために、点数を計算する前に、モデリングされた検索語要約情報及び／またはＩＰ要約情報の次元を縮小することでデータを圧縮して処理することができる。
【００２６】
異常行為訂正部３０は、所定の減点ロジックを用いて、異常行為検出部２０により検出された異常行為を検索ログから除去することによって検索ログを訂正する。一実施例において、異常行為訂正部３０は、分布の差を測定する情報理論を適用した減点ロジックを利用することによって、異常行為が検出された検索語要約情報及び／またはＩＰ要約情報から汚染部分を除去することができる。すなわち、減点ロジックを用いて異常行為の検索回数を減点し、検索ログから正常行為のみを残す手順を行なう。これにより、不正意図による検索語悪用（Abusing）行為を検出及び治療し、検索ログをきれいに維持することができる。
【００２７】
以下、上述した本発明の一実施例による検索ログ悪用防止装置の構成に基づいて本発明の一実施例による検索ログ悪用防止方法を詳細に説明する。
【００２８】
図２は、本発明の一実施例による検索ログ悪用防止方法を示すフローチャートである。
【００２９】
図２を参照すると、検索ログの悪用を防止するために、まず、検索ログから異常行為を検査する対象を選別する（Ｓ１００）。すなわち、一実施例において、検索ログから異常行為を検査する対象として、特定検索語のＩＰ別入力回数を統計的に解析した検索語要約情報及び／または特定ＩＰにおける各検索語の入力回数を統計的に解析したＩＰ要約情報を選別する。この時、このような検索語要約情報とＩＰ要約情報は統計的方法を用いて多次元分布（Distribution）にモデリングされることができる。
【００３０】
次に、選別された検索語要約情報及び／またはＩＰ要約情報に対して正常から外れた度合を点数化し、異常行為を検出する（Ｓ２００）。一実施例において、所定の減点ロジックを用いて検出された異常行為を除去することによって検索ログを訂正する段階（Ｓ３００）をさらに含むことができる。
【００３１】
次に、検査対象を選別する過程について図３を参照してより具体的に説明する。
【００３２】
図３を参照すると、異常行為を検査する対象を選別するために、まず、検索ログから所定の時間ウィンドウ内で、特定検索語のＩＰ別入力回数ベクトル及び／または特定ＩＰにおける各検索語の入力回数ベクトルを生成する（Ｓ１１０）。その後、生成された各入力回数ベクトル、すなわち、特定検索語のＩＰ別入力回数ベクトル及び／または特定ＩＰにおける各検索語の入力回数ベクトルの次元を縮小し、検索語要約情報及び／またはＩＰ要約情報を生成する（Ｓ１２０）。
【００３３】
以下、上述した検査対象選別過程を具体的な実施例に挙げてより詳細に説明する。ただし、下記の実施例は検査対象選別方法の一例に過ぎず、様々な変形が可能であることはもちろんである。
【００３４】
１．第１段階−前処理段階
検索語悪用調査のために検索ログＤＢからＩＰ要約情報及び検索語要約情報を生成する必要がある。一つのＩＰは、特定時間に多数の検索語を入力する。このＩＰが行なう検索の様相が、他の普通のＩＰが行なう検索の様相と異なる度合を測定するためにＩＰ要約情報を生成する必要がある。また、一つの検索語は様々なＩＰから入力される。したがって、該当の検索語を入力したＩＰに関する要約情報を生成する必要がある。
【００３５】
しかし、ＩＰの数、検索語の数、及びこれらの組合せは非常にぼう大なので、検査の対象となるＩＰ及び検索語を選別する必要がある。これらを全て処理するにはメモリー問題が生じるわけである。
【００３６】
１）入力ベクトルの表現
ＩＰ及び検索語要約情報を生成するために、まず、下記のようなベクトル表現を導入することができる。
【００３７】
全体ＩＰ数をＮＩ、全体検索語数ＮＱとすれば、特定検索時点にあらかじめ定義された時間ウィンドウＷ内の特定ＩＰに対する情報は、次のように特定ＩＰで各検索語が入力された回数のベクトルで表すことができる。
【００３８】
【数１】
2010511246.tif 000003
【００３９】
ここで、
【００４０】
【数２】
2010511246.tif 000004
【００４１】
は、特定ＩＰでｋ番目の検索語が入力された回数を意味する。
【００４２】
同様に、特定検索語に関する情報は、各ＩＰで特定検索語が入力された回数のベクトルで表すことができる。
【００４３】
【数３】
2010511246.tif 000005
【００４４】
ここで、
【００４５】
【数４】
2010511246.tif 000006
【００４６】
は、ｋ番目のＩＰで特定検索語を入力した回数を意味する。
【００４７】
しかし、全体ＩＰ数ＮＩ及び全体検索語数ＮＱが非常にぼう大なため、上記ベクトル表現を全て維持するにはメモリー問題にぶつからざるを得ない。
【００４８】
２）ハッシュバケツを用いた検査対象ＩＰ及び検索語の選別
一方、特定時間ウィンドウＷ内で特定ＩＰで入力された検索語のうち、互いに異なる検索語の数は、全体検索語の数ＮＱに比較するとごく少数に過ぎない。また、特定時間ウィンドウＷ内で特定検索語を入力したＩＰのうち、互いに異なるＩＰの数も全体ＩＰ数ＮＩに比べるとごく少数に過ぎない。このような特性を用いて特定ＩＰに関する要約情報及び特定検索語に関する要約情報を生成することによって、前述したメモリー問題を解決することができる。すなわち、全体検索語の数または全体ＩＰ数よりはごく少ないバケツの個数を持つハッシュバケツ（hashed bucket）を利用する。
【００４９】
バケツの個数 D <<  ＮＩ, ＮＱ とすれば、特定ＩＰの要約情報は、下記のようにハッシュバケツの回数ベクトルで表現することができる。
【００５０】
【数５】
2010511246.tif 000007
【００５１】
ここで、
【００５２】
【数６】
2010511246.tif 000008
【００５３】
は、特定ＩＰでｋ番目のバケツがヒットされた数を意味し、特定ＩＰが入力した検索語ｑがある時、検索語ｑと関連したバケツのインデックスｋをハッシュ関数を用いて次のように計算する。
【００５４】
【数７】
2010511246.tif 000009
【００５５】
次に、計算されたインデックスｋに該当するバケツのカウントを増加させる。
【００５６】
このような過程により、特定ＩＰに対する情報を、上記式５に表現されたように、バケツの個数Ｄだけの長さを持つベクトルで要約して表現することによってＩＰ要約情報を生成することができる。また、同様に、検索語に関する情報をバケツの個数Ｄだけの長さを持つベクトルで要約して表現することによって検索語の要約情報も生成することができる。
【００５７】
これにより、ＩＰ情報及び検索語情報を、全体ＩＰ数ＮＩ及び全体検索語数ＮＱよりごく少ないバケツの数Ｄだけの長さを持つベクトルで要約して表現することによって、メモリー問題を解決することができる。
【００５８】
一方、上述した過程を通じて生成された検索語要約情報とＩＰ要約情報は、統計的方法を用いて多次元分布にモデリングされることができる。
【００５９】
以下、上記の式５に表現されたハッシュバケツを用いたベクトル表現に基盤して異常行為の度合を点数化する方法を、異常行為検出過程の流れを詳細に示す図１４を参照して具体的に説明する。
【００６０】
図４を参照すると、異常行為を検出するために、まず、統計的方法を用いて多次元分布にモデリングされた検索語要約情報及び／またはＩＰ要約情報の次元を縮小することでデータを圧縮する（Ｓ２１０）。一実施例において、データを圧縮するための方法として、入力データを互いに直交する座標系に写像（Mapping）させる主成分分析（Principal Component Analysis：以下、‘ＰＣＡ’と略す。）を利用することができる。
【００６１】
続いて、縮小された次元の検索語要約情報及び／またはＩＰ要約情報に対して、中心から離れた度合によって異常の度合を点数として計算する（Ｓ２２０）。一実施例において、異常の度合を計算するために、縮小された次元の互いに独立した標準正規分布のサンプルの和を通じてモデリングされる統計値を用いて所定基準値に対する割合として異常の度合に対する点数を計算することができる。
【００６２】
最後に、計算された点数が所定の基準値以上である検索語要約情報及び／またはＩＰ要約情報に異常行為が含まれたと判断する（Ｓ２３０）。すなわち、計算された点数が基準値以上である検索語要約情報及び／またはＩＰ要約情報を異常行為として検出する。
【００６３】
以下、前述した異常行為検出過程を、具体的な実施例に上げてより詳細に説明する。下記の実施例は異常行為検出方法の一例に過ぎず、様々な変形が可能であることはもちろんである。
【００６４】
２．第２段階−異常行為検出段階
上記の式５で表現されたように、ＩＰ要約情報及び検索語要約情報はそれぞれ、特定ＩＰにおける各検索語の入力回数情報及び特定検索語のＩＰ別入力回数情報を元素とするベクトルで表現できる。
このベクトルを
【００６５】
【数８】
2010511246.tif 000010
【００６６】
とすれば、これは離散確率分布（Discrete distribution）を見せ、
【００６７】
【数９】
2010511246.tif 000011
【００６８】
で表現できる。
【００６９】
ここで、ｐは確率ベクトルで、下記のように計算される。
【００７０】
【数１０】
2010511246.tif 000012
【００７１】
最終的に、本発明では確率ベクトルｐを用いてＩＰ要約情報及び／または検索語要約情報を、下記のような確率ベクトルの集合で表現する。
【００７２】
【数１１】
2010511246.tif 000013
【００７３】
以下では、上記の式１１のように確率ベクトルｐを用いて表現される検索語要約情報及び／またはＩＰ要約情報に対して正常行為から外れた度合を点数化する方法を提案する。
【００７４】
１）主成分分析を用いたデータ圧縮
本発明の一実施例によれば、より円滑なデータ処理のためにデータ圧縮過程を行なう。具体的には、ＰＣＡを用いてバケツの個数であるＤ次元を縮小することによってデータを圧縮する。すなわち、この方法は、ＩＰ要約情報または検索語要約情報を表す離散確率分布
【００７５】
【数１２】
2010511246.tif 000014
【００７６】
から、写像された値の分散を大きくする主成分ベクトルを探すもので、これは該当の離散確率分布の特徴を最もよく説明する数個の固有ベクトルを探すということを意味する。
【００７７】
このようなＰＣＡ方法において、主成分ベクトルとしては、全体分散のうち該当の離散確率分布の分散をよく説明するｄ個の主成分ベクトル（ここで、ｄ＜Ｄである）のみを利用することが一般的である。この時、ｄ個の主成分ベクトルに写像された入力データにおいて、各成分ごとに互いに異なる分散で写像された値間の相関関係（correlation）は存在しないし、各主成分ベクトルは直交することとなる。ＰＣＡ方法は既に広く知られた公知の方法を使用するので、ＰＣＡについての具体的な説明は省略する。
【００７８】
このようなＰＣＡ方法を用いてバケツの個数がＤ次元だったＩＰ要約情報または検索語要約情報を表す離散確率分布を、それよりはるかに少ない数のｄ次元にその次元を縮小することでデータを圧縮し、データ処理効率を上げることができる。
【００７９】
以下、主成分分析されたｄ次元の入力データを用いて正常行為から外れた度合を点数化する方法について具体的に説明する。
【００８０】
２）異常の度合を測定する点数化方法
前述したＰＣＡ方法を通じてｄ次元の主成分ベクトルに写像された入力データは、各成分ごとに互いに異なる分散を有することがわかる。これは、各次元ごとにスケーリングが異なるということを意味する。この場合、視覚化及び後処理に役立つように各次元ごとに分散が１となるように主成分ベクトルをスケーリングするプリホワイトニング技法（Prewhitening Method）を利用することができる。
プリホワイトニングされた写像行列
【００８１】
【数１３】
2010511246.tif 000015
【００８２】
がある時、これに対する入力ベクトルｘの写像値をｄ次元のベクトル
【００８３】
【数１４】
2010511246.tif 000016
【００８４】
で表現するとする。この時、
【００８５】
【数１５】
2010511246.tif 000017
【００８６】
と
【００８７】
【数１６】
2010511246.tif 000018
【００８８】
は互いに相関関係がないし、分散
【００８９】
【数１７】
2010511246.tif 000019
【００９０】
である。
【００９１】
さて、本発明によって異常行為を点数化するために下記のように仮定する。
１）各
【００９２】
【数１８】
2010511246.tif 000020
【００９３】
は、標準正規分布Ｎ（０,１）に従う。
２）i≠ｊの時、
【００９４】
【数１９】
2010511246.tif 000021
【００９５】
と
【００９６】
【数２０】
2010511246.tif 000022
【００９７】
は互いに独立している。
【００９８】
ここで、一般に、相関関係がないということが互いに独立しているということを意味するわけではないが、本発明では、データ処理の効率を上げるために強い仮定を使用する。
【００９９】
このような仮定の下に、下記のような統計値を定義することができる。
【０１００】
【数２１】
2010511246.tif 000023
【０１０１】
一般に、統計学では自由度ｄのカイ二乗分布
【０１０２】
【数２２】
2010511246.tif 000024
【０１０３】
は、ｄ個の互い独立している標準正規分布のサンプルの和を通じてモデリングされる。したがって、上記の式２１のような仮定の下に、統計値
【０１０４】
【数２３】
2010511246.tif 000025
【０１０５】
は自由度ｄのカイ二乗分布に従うと見なすことができる。
以下では、臨界値αに対して、
【０１０６】
【数２４】
2010511246.tif 000026
【０１０７】
を満足する最も小さいｓ値を
【０１０８】
【数２５】
2010511246.tif 000027
【０１０９】
と定義する。ここで
【０１１０】
【数２６】
2010511246.tif 000028
【０１１１】
はｓ境界までの累積確率分布値を表し、αは誤差水準または有意水準で、通常、０．０５または０．０１とすることが好ましい。結局、
【０１１２】
【数２７】
2010511246.tif 000029
【０１１３】
は臨界値αを越えない正常範囲の最大境界を意味することから、境界
【０１１４】
【数２８】
2010511246.tif 000030
【０１１５】
を越える全ての
【０１１６】
【数２９】
2010511246.tif 000031
【０１１７】
は異常の範囲に含まれると考えることができる。
【０１１８】
したがって、本発明では正常行為から外れた度合を点数化するために、悪用点数を下記の式で定義する。
【０１１９】
【数３０】
2010511246.tif 000032
【０１２０】
すなわち、
【０１２１】
【数３１】
2010511246.tif 000033
【０１２２】
が１より大きい値を持つほど、確率ベクトル
【０１２３】
【数３２】
2010511246.tif 000034
【０１２４】
は小さい値を有し、確率ベクトルｐが臨界値αよりも小さくなる。結局、これは、与えられた仮定の下に極めて稀であると判定する根拠を提供する。すなわち、上記の式３０によって定義された悪用点数（score）値が１より大きい場合は、正常範囲から外れた稀な場合で、これは異常行為と判定されることができる。
上述した統計方法を、図５の例を参照して具体的に説明する。図５には、自由度１のカイ二乗分布の一例が示されている。
【０１２５】
【数３３】
2010511246.tif 000035
【０１２６】
は、誤差水準または有意水準を表す臨界値がαの時のカイ二乗分布での正常範囲の最大境界９０２を意味するから、境界
【０１２７】
【数３４】
2010511246.tif 000036
【０１２８】
を越える全ての
【０１２９】
【数３５】
2010511246.tif 000037
【０１３０】
は異常範囲に含まれると考えることができる。
すなわち、確率ベクトル１から正常境界範囲までの累積確率分布
【０１３１】
【数３６】
2010511246.tif 000038
【０１３２】
を減算した領域９０４が異常領域を意味し、この領域９０４に含まれる全ての
【０１３３】
【数３７】
2010511246.tif 000039
【０１３４】
は異常範囲に含まれると考えることができる。
【０１３５】
次に、図６を参照して本発明の一実施例による検索ログ訂正過程について詳細に説明する。
【０１３６】
図６を参照すると、検索ログを訂正するために、分布の差を測定する情報理論を適用した減点ロジックを用いて異常行為として検出された検索語要約情報及び／またはＩＰ要約情報から汚染部分を除去する（Ｓ３１０）。
【０１３７】
この時、検索ログを訂正するための減点ロジック（Discounting Logic）は、母集団の確率模型と前述の異常行為が検出された検索語要約情報及び／またはＩＰ要約情報の確率模型間の分布の差を表すＫＬ距離（Kullback-Leibler Distance）を用いて異常行為を除去することができる。
【０１３８】
以下、前述の検索ログ訂正過程を具体的な実施例に上げて詳細に説明する。下記の実施例は、検索ログ訂正方法の一例に過ぎず、様々な変形が可能であることはもちろんである。
【０１３９】
３．第３段階−検索ログ訂正段階
１）分布の差を測定する手段−ＫＬ距離
上述したように、本発明の一実施例によって検索ログ訂正のために利用される減点ロジックは、異常行為が検出された検索語要約情報及び／またはＩＰ要約情報の確率模型と母集団の確率模型間の分布の差を測定する手段としてＫＬ距離を利用する。
【０１４０】
このようなＫＬ距離は情報理論（Information Theory）に根拠しているもので（Cover and Thomas(1991)）、例えば、２つの分布ｐ，ｑがあるとすれば、これら両分布間のＫＬ距離は下記のように求めることができる。
【０１４１】
【数３８】
2010511246.tif 000040
【０１４２】
したがって、ＫＬ距離は、両分布が同じ時に０の値を持つ。
【０１４３】
２）減点ロジック
便宜上、モデルを構成するために使われたＮ個のデータを母集団とし、これをＮＸＤの行列Ｍで表現する。この時、ＭのＩ番目の行miは、ハッシュバケツの回数を保存したベクトルである。行列Ｍを行を基準にして正規化（normalization）し、離散確率模型ｍを得る。
【０１４４】
【数３９】
2010511246.tif 000041
【０１４５】
異常パターンのハッシュバケツベクトルをｈ、その離散確率模型をｐとすれば、母集団の離散確率分布ｍと検査対象となる離散確率分布ｐ間のＫＬ距離は、下記のように計算される。
【０１４６】
【数４０】
2010511246.tif 000042
【０１４７】
上記式４０を用いてハッシュバケツベクトルｈで特定元素の値を減らすと、変形された離散確率模型と母集団の離散確率模型間の差を減らすことができる。
具体的には、あるハッシュバケツｉの
【０１４８】
【数４１】
2010511246.tif 000043
【０１４９】
値が大きい正の値を持つほど、両分布間のＫＬ距離が大きくなり、これは分布ｐを異常なものとさせる。したがって、異常行為を除去することで検索ログをきれいに維持するために、臨界値をβとする時、
【０１５０】
【数４２】
2010511246.tif 000044
【０１５１】
のハッシュバケツが減点ロジックを適用する校正候補となる。
【０１５２】
一方、図７は、本発明の一実施例によって検索ログ訂正過程に用いられる減点ロジックを説明するための図である。
図７には全体的な減点ロジックが示されている。ここで、“find()”関数は、()中の条件を満たす元素のインデックスを取り戻す関数である。“ceil()”関数は、()中の因子よりも大きい最も小さい整数を取り戻す関数である。演算子“.*”は、ベクトルの元素間の乗算を行なう。“score”は、上記の式３０で定義した悪用点数を意味する。
【０１５３】
【数４３】
2010511246.tif 000045
【０１５４】
は検索語入力回数を、ｐは
【０１５５】
【数４４】
2010511246.tif 000046
【０１５６】
を正規化した確率関数を、βは校正候補を選定する臨界値を、ｆは母集団の離散確率分布ｍと検査対象となる離散確率分布ｐ間のＫＬ距離をそれぞれ意味する。
【０１５７】
全体的な減点ロジックについて説明すると、まず、特定検索語のＩＰ別入力回数または特定ＩＰにおける各検索語の入力回数を正規化し確率関数を求め、母集団の離散確率模型との差に基づくＫＬ距離を計算する（９０４）。求められたＫＬ距離が臨界値βよりも大きいインデックスｉを求める。求められたインデックスが異常行為の含まれた検索語またはＩＰを意味する。求められたインデックスに該当する検索回数を減少させ（９０６）、臨界値βを調整する。
【０１５８】
以上の減点ロジックは、score＜１と正常範囲に属したり臨界値β以上の候補がないまで反復する。特に反復の度にβを増加させる理由は、既に反復の初期に核心的な異常行為の減点がなされるから、次の反復では減点基準をより厳格にするためである。
【０１５９】
一方、図８は、本発明の一実施例による検索ログ悪用防止装置により提供されるユーザーインターフェース画面である。
【０１６０】
図８を参照すると、左側窓に検索対象として選別された検索語目録とＩＰ目録が表示され、中間窓には異常の度合を計算した悪用点数によって減点処理すべきカウント数が表示される。
【０１６１】
一方、図９〜図１３は、本発明の一実施例による検索ログ悪用防止方法による実験結果を示す図である。
【０１６２】
本発明の一実施例による検索ログ悪用防止方法の性能を確認するために、２００６年７月７日１２時３０分頃の結果を調べる。本実験で時間ウィンドウＷは１時間、ハッシュバケツの個数Ｄは３２と設定した。また、臨界値α＝０．０１、β＝ｌｏｇ(１．８)、ｓｃａｌｅ＝ｌｏｇ(１．３)と設定した。
【０１６３】
検索語要約情報からモデルを構築し、検査候補集合に対して前述の悪用検査を行なった後、算定された悪用点数の高い上位２０個の検索語が図９のように示される。これは、各サンプルの離散確率模型をヒストグラム形態で表現したもので、縦軸は確率値であって［０，１］に軸のスケールを固定した。横軸はハッシュバケツのインデックスを表す。絵の上端には検索語の名前と悪用点数（score）を記録した。上位２０個の検索語はいずれも悪用点数が３〜９程度と、いずれも１以上であるから、異常行為が含まれたと予測される。
【０１６４】
一方、図１０には、本発明によって検出された上位２０個の悪用検索語に対する減点処理結果の一例を示す。各行を見ると、減点以前の元来のハッシュバケツと、減点ロジックの反映されたハッシュバケツを対として表した。点数については、減点後には悪用点数が１未満となり、異常行為が除去されたことが確認できる。
【０１６５】
一方、図１１は、本発明によって上記減点処理結果と離散確率分布値を比較した結果を示す。悪用点数が３〜９程度と異常だった検索語の悪用点数が１以下となり、正常範囲に訂正されたことが確認できる。例えば、検索語“タイプ”の場合、９．６７３８３３だった悪用点数が、異常行為が除去される減点処理手順の後には０．２１１１６６程度となり、正常範囲内に訂正されたことがわかる。便宜上、減点後では縦軸を［０，０．１］にスケーリングした。
【０１６６】
減点ロジックでＫＬ距離を計算するための基準とされた母集団の確率模型は、図１２に示す。
【０１６７】
減点前と減点後の点数を比較した時、減点ロジックを通じて異常行為が除去されることによって、異常だった検索語の悪用点数が正常水準に回復したといえる。
【０１６８】
図１３には、上位４０個の検索語に対する減点処理結果の一例を示す。左側に悪用点数が記載され、減点前の総検索回数と減点ロジックによって計算された減点回数が表示されている。すなわち、総検索回数から減点ロジックによって計算された減点回数を減算することによって、異常行為として検出された検索語から汚染された部分を除去し、検索ログを訂正できることがわかる。
【０１６９】
以上では検索語要約情報を用いて異常と判断された検索語の検索回数を減点し、検索ログ上に正常行為の情報のみが維持されるようにする方法について説明した。大部分の検索語悪用問題は、前述したように検索語要約情報を用いた悪用検出及び治療方法だけで十分に解決することができる。しかし、検索語要約情報では悪用点数が１未満と正常行為として判断されるが、実際には検索語悪用による異常行為である場合が稀にある。このような場合にはＩＰ要約情報を用いて悪用行為をさらに訂正することができる。このような方法は、検索語要約情報に対する悪用検出及び治療方法と略同様なので、その詳細な説明は省略する。
【０１７０】
本発明では、検索ログにおける検索悪用の診断及び後処理を通じてきれいな検索ログを維持するための検索ログ悪用防止方法及び装置を提案した。すなわち、ＩＰ要約情報及び／または検索語要約情報を表現するためにハッシュバケツ基盤の資料構造を構築したし、これを離散確率模型に変換して入力データを表現した
また、正常サンプルに比べて異常サンプルを検出できる技法を提案した。入力データはＰＣＡ方法によって互いに直交する主成分ベクトルの空間に移され、ここで中心から離れた度合を測定する統計学基盤の点数化技法を提示した。
【０１７１】
最後に、情報理論に基づいて異常なサンプルを正常なサンプルに変換する減点技法を提案した。
【０１７２】
一方、前述した検索ログの悪用を防止する方法は、コンピュータプログラムとして作成可能である。当該プログラムを構成するコード及びコードセグメントは当該分野におけるコンピュータプログラマーによって容易に推論可能である。また、当該プログラムは、コンピュータ読取可能な情報記憶媒体（computer readable media）に記憶され、コンピュータによって読み取られて実行されることによって検索ログの悪用防止方法を具現する。当該情報記憶媒体は、磁気記録媒体、光記録媒体、及びキャリアウェーブ媒体を含む。
【０１７３】
以上では本発明についてその好適な実施例に上げて説明してきた。本発明の属する技術分野における通常の知識を持つ者には、本発明が、本発明の本質的な特性を逸脱しない範囲で変形された形態に具現されることができるということが理解できる。したがって、開示された実施例は、限定的な観点ではなく説明的な観点で考慮されなければならない。本発明の範囲は、前述した説明ではなく特許請求の範囲に現れており、それと同等な範囲内にある差異点はいずれも本発明に含まれたものと解釈されるべきである。
【産業上の利用可能性】
【０１７４】
前述した如く、本発明によれば、検索ログから異常行為を含む悪用検索語を效率的に検出し、悪用と判断された検索語の検索回数のうち有効な検索回数のみを残し、異常行為を除去することによって、検索ログに対する悪用を防止し、検索ログをきれいに維持することができる。
【図１】
2010511246.tif 000052
【図２】
2010511246.tif 000053
【図３】
2010511246.tif 000054
【図４】
2010511246.tif 000055
【図５】
2010511246.tif 000056
【図６】
2010511246.tif 000057
【図７】
2010511246.tif 000058
【図８】
2010511246.tif 000059
【図９】
2010511246.tif 000060
【図１０】
2010511246.tif 000061
【図１１】
2010511246.tif 000062
【図１２】
2010511246.tif 000063
【図１３】
2010511246.tif 000064
【国際調査報告】
2010511246.tif 000065
2010511246.tif 000066