検索エンジンのコンテンツに関してスパムにならないようにはどうしたら良いか、キーワードが５％が最適とか言っている前に最新の論文を読んだほうが良いだろう。ということでWorld Wide Web Conference2006からそれに該当する論文を読んで要約してみた、これを理解すればどのような行為がスパムになるのかが良くわかるはずである。SEO業者も必見かと思います。
論文はこちら このグラフはこの論文中のものを指しています。 また計算式がみにくいですけどこれも論文中のものを見てもらえれば助かります。
Detecting Spam Web Pages through Content Analysis
Introduction
サイトのクオリティを高める努力をせずに検索エンジンのランキングを外部リンクや人気キーワードのサイトへの埋め込みなどによって不正に上昇させるような行為を検索エンジンスパムという。英語のサイトの１３．８％はスパムサイトであるといわれているがこれを看破できないサーチエンジンはリソースの約7分の１を浪費してしまい、更にはサーチエンジンのクオリティの低下でユーザが離れてしまうのでどうにかしなければならない。
これらを防ぐために
Webの大きさを考ると人手を介さず自動でスパムサイトを発見しなければならない
正統な（スパムでない）サイトをスパムとみなしてはいけない。
クエリーをユーザーが投げる前にはスパムを発見したい（そうすることで無駄なロボット巡回、クエリー処理、インデキシングを省くことができリソースを有効活用できる。）
この論文で我々はスパムを発見する様々な方法、また効率、精度よくスパムサイトを発見するアルゴリズムを作るために、如何に個々の方法を統合する機械学習技術を使ったかを示す。
この論文の構成は次のようになる
§２：実験概要、実世界データセットの紹介
§３：データセット中のスパムの蔓延度合いをドメイン、言語別で比較
§４：スパムの発見する方法を説明
§５：我々の手法の評価
§６：関連研究
§７：結論と将来への展望
２．実験概要とデータセット
データセット：MSNサーチエンジンが収集したサイトデータから105,484,446(約１億)のページをランダムで取ってきたもの。
厳密にはMSNサーチが取り込むデータ自体もスパム排除プログラムを潜り抜けたものであるからランダムとは言えないが。しかし実際にユーザが目にするのはそのようなサイトであるし、我々の実験で得られた結果も、真の意味でランダムでとってきたのよりも悪くなるはずなので控えめな見積もりということができるので十分にこの論文の価値はあるといえる。
どれくらいスパムがあるの？
この章では、どれくらいスパムがWeb上に蔓延しているのかと、トップドメイン名、国などで区切った時あるページの集合が他のページの集合に比べてどれくらいスパムが多いのかを調べていく。Figure2はどのトップレベルドメインにスパムが多いかを調べた結果であり、Figure3は言語によるスパムサイトの割合である。この二つの実験からスパムはかなりの割合でWebに蔓延しており、また特定のドメインはスパムだらけである。これらの調査はスパム発見手法に生かしていく。
内容に基づいたスパムの発見
我々のWebDBの論文[8]で、我々はスパムの発見手法を数多く説明したが、その中には完全にページの内容と独立したものもある。（リンク構造やDNSレコードを使ったもの）また一方で内容が解釈されていないもの（ページの進化状況、（構造的に？）似たようなものをクラスタリングする）もある。
この論文では、我々は全てコンテンツに基づいたスパム判定を行う。
我々は1億のデータから最も多数ある（５４％）英語のページをランダムで１７１６８ページ取得してそのそれぞれに対して人手でスパムページかそうでないかを仕分けした。そのうち１３．８％がスパムページで８６．２％がスパムページでなかった。この章の残りで我々が研究したコンテンツに基づくスパム発見手法を詳細に説明していく。
ページ中の単語数
スパムページは人気キーワードをとかく詰め込む傾向があるので、過剰な数の単語がスパムの指標になるのかを調べ、その結果は図４のようになった。確かにページ数が多いほどスパムの割合は高くなるが全ての範囲でスパム率は５０％を切っているのでこれだけでスパムかどうかを判定するわけにはいかない。
ページタイトル中の単語の数
スパムの常套手段のもう一つとしてページタイトル中に単語を詰め込むというものがある。そこで我々はページタイトルに含まれる単語数とスパムの関係を調べ、その結果は図５のようになった。図４と図５を比べると図5のページタイトルに含まれる単語数の方がスパムを判断する上で良い指標となるといえる。
単語の平均の長さ
クエリを複数語を指定して投げる時にスペースを入れない人がいるのでそれを狙って単語をつなげているページがある。例えば”freepicture”,”freemp3”などなど。そこで単語の平均アルファベット数とスパムの関係を調べてみたところ図６のようになった。単語の長さが８文字をすぎるとかなりスパムの割合が高くなることがわかる。
アンカーテキストの量
リンクはアンカーテキストとなっているが、単に他のページにリンクの渡すためだけのカタログページが存在する。そのようなサイトは大量の初リンクがあるのでアンカーテキストの単語が全単語に占める割合とスパムとの関係を調べた。その結果図７のようになった。ややアンカーテキストの割合が高いほどスパムの確率は上昇するがあまり顕著ではなかった。
見えているコンテンツの割合
マークアップでない単語の総バイトをページの総バイト数で割ったところ図８のようになった。これからスパムページはマークアップ（スクリプトやスタイルシートなども含む）が普通のサイトより少なく人にサイトを見せるための装飾等を省いているといえる。
圧縮率
冗長なコンテンツがあるページは圧縮器をかけることによりサイズを縮小できる。例えば同じ単語が何度も使われていたりすると圧縮率は高くなる。そこでGZIP[14]という圧縮器を使って圧縮率とスパムの関係を調査して、その結果が図９のようになった。
ページ中で一般的に良く使われる単語が含まれる割合
スパムページは検索エンジン対策のため文章が不自然になっている可能性があるので、データセットで上位２００位までの頻出単語が全文章中でどれくらいの割合で使われているのかを調べ、それとスパムとの相関を図１０に示した。この結果スパムページは一般的に使われている単語をあまり使っておらず偏りがあることがわかる。
一般的に良く使われる単語の割合
データセットで上位５００位までの頻出単語のうち何種類がページ中に含まれているかを求めスパムとの相関を調べた。４．７の場合例えばページ中に”a”とだけ書かれた文字があったとするとスコアは１となるが４．８の場合は1/500となる。うまく４．７の欠点を補う意味で調査をした。その結果図１１のようになったが全体的に控えめな結果となった。
独立したN-gramの可能性
スパムページは文法的におかしい傾向が強いためn-gramにより文書の傾向を調べた。理想的には文法的かつ意味的に正確さを追求したいのだが、計算量が多くなるため統計的な手法であるn-gramを用いることにした。
という式でまずあるn-gramの発生率を求める。分母はngram全体の数、例えばngramはオーバーラッピングするので3gramで5個単語があるとすれば最初の３つ、真ん中の３つ、最後の３つで合計total number of ngram = 3 となる。分子はこれら３つの重複数で最初、真ん中、最後の全てが異なる場合１となるし、最初と最後が同じで真ん中が異なると最初と最後の値が２となり真ん中が１となる。
この式から文書全体のn-gramの発生率のようなもの（文書中にはk個のn-gramを持った文書の確率は個々のPの確率の積であると書かれているがまったく理解できない）を取り、それを文書の長さによる差がでないように正規化すると
となる、これをコンピュータの誤差が出にくいようにさらに変形して
とする。この式からわかることはngramで共起する回数が少ないほどlogPの値が小さくなる、すなわち負の値が大きくなるためIndepLHの値が大きくなる。また逆にngramで共起回数が多いほどlogPの値が大きくなり、すなわち負の値が小さくなるためIndepLHの値は小さくなるということである。（これ以上は理解不能）
図１２はこのIndepLHの値とスパムとの関係である。極端にngramでの共起が少ないときと多いところにスパムが集まっている。共起が多いときは同じ表現を繰り返し何度も使っているスパムであると判断できる、また（グラフのどこからその根拠を得ているのかは不明だが）起こりそうにないngramで構成されている文書はよりスパムである確率が高い、おそらく文法的にありえない文書を使っているからであろう。
４．１０ 条件付ngramの可能性
と条件付確率を定義するとより計算量が増えるかわりに精度が上がるらしい。（どう、または精度が向上するのかはよくわからないがとにかくより良い手法らしい）そして後は４．９と同じようにして計算してスパムとの関係を調べると図１３のようになった。大体図１２とライングラフが一致している。（結局あまり大差ないやん）。
５．今までのデータを組み合わせて分類器の生成
今までのデータを用いて分類器を生成して、ページがスパムであるかスパムでないのかを求めた。これを行う技術としては決定木、ルールベース技術、ニューラルネット、サポートベクターマシンを使った。そのうちで最も分類精度が良かったのは決定木のC4.5というアルゴリズムである。C4.5は簡単に説明すると最も分類精度が高い順にルートから木を生成していくというアルゴリズムである。分類例は図１４のようになり、再現率と精度はテーブル１のようになった。
5.1 分類の正確さの改善
より分類器の正確さを上げるために我々は最も有名な2つの技術「bagging」と「boosting」を使おうと思う。
Baggingの説明
もとのデータセットからN個のデータセットを作る。その時各データセットはもとのデータセットからそれぞれn個のデータをランダムで選んだものとする。（それゆえデータセット間のデータの重複は許される）
N個のデータセットそれぞれについて分類器を作成する
それぞれの分類器を使ってスパムかスパムでないかを判別する。
最終的な結果は分類器の多数決によって決める。
これがBaggingの概要であるが今回はN=10,n=15453で実験して行ってみたところ結果は表２のようになり正確さは上昇した。
Boostingの説明
最初に全てのデータに1/nの重みを割り当てる（今回の場合n=15453）この重みはトレーニングセットの中で一つデータを取り出した時に該当するデータである確率である。
この重みを使って分類器を生成する
分類した際にスパム・ノンスパムの分類を間違えたデータは重みを増やし、正解したデータは重みを減らす（つまり学習例として適しているデータの重みを増やすってことだとは思う）
２．３を繰り返す（今回の場合10回）
１０個分類器ができるのでスパム・ノンスパムの判定は重み付投票で決める。
これにより分類してみたところ結果は表３のようになりかなり改善が見られた。
６．RELATED WORK
機械学習の関連研究
C4.5を使ったEmailの分類[16,28]
これは人が読むものに対するスパムだが我々は検索エンジンのロボットが読むためのスパムを発見するという意味で異なる。
スパムの役割やシステムについて
Henzingerら[15]はスパムがサーチエンジンにもたらす脅威を認めた
Perkins[25]が数多くのスパムテクニックを定義しGyongyiとGarciaMolina[13]がよりそれを詳細に分割した。
DeStefano[20]はWebスパムと宣伝の関係を指摘(調べてみたらあるサイトのリンクポピュラリティを故意に上げよう（あるサイトを宣伝しよう）とした時に現れるリンク構造を発見したみたいな内容であった)
スパム手法は一般的にリンクスパム、内容スパム、クローキングに大別できる
リンクスパムについて
Davison[7]は早い時期にリンクスパムについて調査しており、縁故主義のリンクについて考察している
Amitayら[2]はリンク構造をルールベースの分類器に入れてリンクスパムを発見する手法を提案
Baeza-Yateら[3]はページランクを上げるために示し合わせたリンク形態の研究を示し、Adaliら[1]はあるページにリンクを張るためのみにページを生成することが最も効率的なスパムの手段である事を示した。（今では古いと思うが）
Zhang[31]らはどうやってページランクを攻撃（スパム）に耐えられるものにするかを示した
Gyongyiら[11]は信頼の置けるサイトからのリンクを辿ることによるTrustRankというものをスパムでないページの発見のために用いた。
Benzur[4]らは不自然にページランクを上昇させているページに対してどうペナルティーを与えるのかについて示した。
Wu と Davison[29]とGyongyi と Garcia-Molina[12]はリンクファームの発見手法について研究した。
[8]で我々はリンクスパムを指数法則からの逸脱をもとに発見する方法を示した。
Mishneら[21]らはブログのコメントにあるリンクスパムを発見するために単語の使用頻度を用いた確率的な手法を提案した。
４． コンテンツスパム
[8]で我々は長いホスト名、多くのダッシュやドット、数字が入っている、単語に多様性がない、頻繁に広範囲にわたってコンテンツを修正する、ということがスパムであるかどうかの良い指標になることが多いということを示した。
[9]で我々は切り取りと貼り付けで作ったようなサイトのスパムを調査して、そのようなページを発見する方法を提案した。
クローキング
クローキングとはWebサーバに細工をして検索エンジンの巡回ロボットに一般の閲覧者とは異なる内容のWebページを見せる事を言う。（フラッシュ等を多用しているサイトでは検索エンジンとの親和性が低いためそれをカバーするため最適化したHTML構造を巡回ロボットに見せるというパターンが多い）GyongyiとMolina[13]は現在のクローキングテクニックを示した。
WuとDavison[30]は３つの別々のページに共通する単語を計算することに基づいたクローキングの発見方法の有効性を示した。（意味不明）注目すべきはクローキングが有益なものを使うということである。例えば帯域幅やストレージコストを減らすためにサーチエンジンに対してクローキングがマークアップなしでページのコピーを返すような感じである。（サーチエンジンに有用な部分だけを見せるということだと思う）
７．結論と先への展望
Webスパムと検索エンジンのいたちごっこは続いていくであろうが我々の技術がより良い検索のために役立てばうれしいと思う。継続的な研究により効果的なスパムを行うよりもコンテンツ作りを充実させたほうがよりリスクが少ないようになるのが我々の願いである。
0 件のコメント:
コメントを投稿