テキストの自動分類の簡単なまとめ

テキストの自動分類について研究で調べる必要があったので整理してみた.何かの役に立つかもしれないです.

テキストの自動分類に関する研究は1960年にMaronが行った事例が発端とされている.その後1990年代に入り,Webで大量のデータが手に入るようになり,活発に研究されるようになった.
テキスト分類は大きく分けて２つあり,一つは予めカテゴリを定めずに,類似する主題を持つテキスト集合をグループ化する手法であるクラスタリング,もう一つは予めカテゴリを定めておいて,そのいずれかに新たに入ってきた文章を振り分けるテキストカテゴライゼーションである.
テキストカテゴライゼーションにおいて,どの語を分類ルールの生成に使うか,という問題があるが,これについてはN-gramという文章をN個ずつ,単語を一つずつずらしながら区切っていき,それらを語とする方法と,形態素解析という,予め辞書に単語を登録しておき,文章中の文字を辞書と照合することにより,文章を単語に分解していく手法がある.さらに分類精度を高めるために,より文書分類に重要な語を抽出しようという試みもある.これには言語特徴を用いた手法と,統計的特徴を用いた手法の２通りがあり,通常は両方を合わせて使う事が多い.言語特徴として,言語には語と語の関係を表し,それ自体は意味を持たない機能語と,語自体がある概念を表現している内容語に分けられる.機能語は助詞や助動詞を指し,内用語は主に名詞や動詞である.形態素解析を用いている場合は品詞情報を得ることが可能であるので簡単に機能語と内用語を分類する事ができる.一方でN-gramを用いている場合は全てカタカナや,全て漢字が使われている語は内容的に意味を持つ可能性が高い,特に漢字は主題的特徴を現している事が多いという事で,これらを重要語として抽出することが多い.次に統計的特徴として,該当カテゴリにおける語の出現頻度TFや,ある語が出現するテキストがカテゴリに属しているテキスト数DF,あるいは相互情報量,カイ２乗統計を使ったもの,またそれらを組み合わせて使ったものなどが存在する.また統計的特徴を用いたものとしてLSI(Latent Semantic Indexing:滞在意味インデキシング)という方法もあり,これはカテゴリ内で同時に出現する傾向のある複数の語を一つにまとめてしまうもので,例えば「情報センター」という言葉を「情報」と「センター」という２語ではなく１語として捉えることを言う.
分類ルールの作成に関しては,1980年代までは知識ベースのアプローチが主であり,人手で書かれた規則を用いる方法が一般的であったが,1990年代に入ると機械学習を用いた手法が多くなりサポートベクターマシン等が使われるようになった.

クロスレコメンドの効果は？

２００６年の春から始まったディレクトリサービスにクロスレコメンドというものがある。これはWebサイトを複数の大手ポータルサイトのディレクトリに登録するサービスである。４万２０００円を払い審査に通るとgooやexcite,biglobeなど相当たるサイトのディレクトリに登録される。さてこのサービスにはどれ程のSEO効果があるのだろうか？ちなみに巷ではアクセスアップおよびSEOに対して効果があると様々なメディアで取り上げられていたり、あるサイトではほとんど検索順位が上がらずSEO効果はなかったと書かれていたりと賛否両論である。まあしかし実際にクロスレコメンドに登録して順位が上がったとしても今の検索エンジンは複雑なのでそれがクロスレコメンドへの登録によるものなのか他の要因によるものなのかなどは分かる術はない。そこで検索エンジンのアルゴリズムを考慮してクロスレコメンドの効果について考えたいと思う。
　まず効果があると思われる点が、信用の置ける大手ポータルサイトからのリンクされるという点、それも複数のドメインからのリンクであるという点である。
　質の低いスパムサイトに多数リンクしているようなページからのリンクであればほとんどSEO的には効果がないが、大手ポータルサイトのような質の非常に高いサイトからのリンクは非常に有用なものとなる。さらに複数の大手ポータルサイトからのリンクを受けることになるのでその効果はかなりのものであると言える。また相互リンクではSEO的な効果は半減してしまうが（検索エンジン側でアルゴリズムを公開しているわけではないのでおそらくとしか言えないが常識的に考えればそうだろう）受けるのは一方的な被リンクなわけであるからこれもかなりSEO的にプラスに働いてくるといえる。さらにヤフーディレクトリと比べて登録サイトが少ないのでこの点でもSEO的にプラスである。
　逆に効果が減少してしまうんじゃないかという懸念要素として、検索エンジンの高度化によるクラスタリング機能がまず第一に考えられる。クラスタリング機能とは検索エンジンが内容の似通ったページを類似ページ、ミラーページとしてみなすことである。類似サイトとみなされたページからのリンクはSEO効果が下がるかあるいは全くリンクとしての価値がなくなってしまう恐れがある。ところでこのサービスのリンク集はクロスレコメンドが作っているので、リンク集はgooであってもexciteであってもniftyであってもほとんど同じとなる（リンク先ページとその説明は完全に同じ、サイトのデザイン部分が違うだけ）。すなわちこれらのリンク集は互いに類似ページとみなされてそのSEO価値を失う可能性は大いにある。現在グーグルではクロスレコメンドのディレクトリに対してこのクラスタリングがなされていると思われる節がある。グーグルのバックリンク情報を調べたときにクロスレコメンドと契約しているポータルサイトからのリンクが１つしか出てこない場合が多いからである。(gooからのリンクだけバックリンクとして表示されている場合が多い、ただし実際にクラスタリングされているかどうかはイマイチよくわからない）、YSTに関しては今のところそのような節は見当たらないが、ヤフーディレクトリ側としてはクロスレコメンドは競合サービスといえるのでヤフーディレクトリに登録するよりクロスレコメンドに登録した方がYSTに効果があるなんて事になっては絶対にいけない。だからYSTのアルゴリズムを近々変更してクラスタリング機能を強化してくる可能性は大いにあり得る話だと思う。
　その他のSEO効果が減少する要素としてはリンク集サイトのSEO価値の低下、ディレクトリサービスが始まってから経た年月が少ない（２００６年サービス開始、検索エンジンは昔からあるサイトを重視する傾向がある）ということなどが挙げられる。まあこれは最初のクラスタリングに比べたらあまり重要な要素ではないが。
　で、結局総合して考えてクロスレコメンドの効果はどうなんだって事なんですけどグーグルの検索エンジンに対しては割と大きな効果が期待できそうです。クラスタリングに引っかかるとしてもページランクの値の配分に関してはクラスタリングとは何の関係もないです。クラスタリングで他の要因がマイナスになるんでしょうけどそれでもYahooディレクトリに登録するよりはクロスレコメンドに登録したほうが効果が高いと思います。またYSTに関してですけど、こちらはヤフーディレクトリへの登録よりは効果が薄い気はしますがYSTはポータルサイトからのリンクを重視する傾向があるのでそれなりには効果が望めそうです。下手すればヤフーディレクトリを上回る効果が得られるかもしれません（まあ後々上回らないように手を打たれるような気もしますがｗ）
　まあ複数の大手ポータルサイトがそれぞれ独自にディレクトリを作っていたと仮定してそれに全部登録するよりはSEO効果が薄いけれどもそれなりのSEO効果は十分に望めるのではないかというのが私の見解です。審査もヤフーと比べれば優しく値段も安いので試しにクロスレコメンドに登録してみたらどうかと思います。

　

検索連動広告の掲載順位の決定法など・・ Predicting Clicks

今回の話は検索エンジンの検索連動広告についてである。どの広告をどの順番で表示すれば検索エンジン側の収益の最大化、ユーザの満足度の向上が図れるかという問題についてが書かれてある。クリック率が分かっているならば話は早いのであるが新しい広告に対してはクリック率は過去のデータがないのでわからない。そこで新しい広告に対するクリック率を様々な手法を用いて推定してやるというのが本論文の核となるところである。ちなみにこれはマイクロソフトからの研究発表であるがビジネス要素が強いこのような研究を表に出してもいいのか？と疑問が残る・・・まあ取り合えず貴重な論文ということで・・・邦訳・要約しておいたのでブログに載せときます。論文の詳細はhttp://delivery.acm.org/10.1145/1250000/1242643/p521-richardson.pdf?key1=1242643&key2=0763889911&coll=GUIDE&dl=GUIDE&CFID=49087471&CFTOKEN=54138199です。具体的な表や計算式はこちらを参照願います。またまた図や式が汚くて申し訳ないです。ワードからグーグルdocに移してそこからブログに投稿しているので汚くなるわけです。もう少し互換性をどうにかして欲しいものです。ちなみに検索連動広告を考えている人に一言いっておくと、この論文のような内容が既に検索エンジン側で実装しているとしたら、たとえ個人運営のサイトが大手の会社より多くのクリック単価を払ったとしても大手より検索順位が低くなってしまう事がかなりありそうです。クオリティの低いサイトはお金を払っても認めてもらえないということですね、頑張ってコンテンツの充実などを図りましょう！

１．イントロダクション

ほとんどの主要な検索エンジン会社は今日検索結果の隣に配置されるテキスト広告によって利益を得ている。これはクリックがユーザによってされる度に料金が広告主から検索エンジン会社へ支払われるという仕組みをとっている。このモデルをクリック単価型成果主義と呼ぶ。検索エンジン側の収入とユーザの満足度を最大にするためには、システムがそれぞれの広告に対するユーザの挙動を予測して、可能な限りユーザにクリックを促さなければならない。サーチエンジンは過去に広告がクリックされたかでユーザの挙動を予測することができる。例えば100回広告が表示されてクリックが5回されたならば、その広告のCTR(click-through rate)は０．０５と推測することができる。しかしこの予測は新しい広告が入ってきた場合、すなわち過去のデータが利用できない場合は使うことができないという問題がある。

この論文では、私たちは新しく作られた広告がクリックされる可能性を予測する。我々は広告それ自体（広告の長さ、使用されている単語）、広告が指し示すページ、関連する広告の統計情報などを用いて新しい広告の将来的なCTRを合理的に予想する。

２．モチベーション

検索エンジン広告システムの主要な仕事は、サーチエンジンが受け取ったそれぞれのクエリに対してどんな広告を表示するかと、その順番をどうするかを決定することである。大抵広告主は広告が現れる状況をクエリ指定などにより既に指定してしまっているのでサーチエンジン側はマッチした広告を減らすことさえ考えれば良い。

　ユーザが広告をクリックする確率は広告の表示位置によって大きく変わってしまうので、サーチエンジンにとって最も効果的な広告を最も目立つ位置に持ってくることが収入増を考える上で非常に重要な要素になる。しかも広告数が増加傾向にあり、与えられたクエリに対して適合する広告の数は効果的な広告表示枠の数を大きく上回ってしまうことが多くさらに広告の表示位置決定は重要さを増してきている。

　広告の質（ユーザのクリックによって計測される）と総収益を最大にするためにほとんどの検索エンジンは期待収益（クリック率とクリック単価の積）の順に広告を並べ替えている。例外としてYahooはクリック単価の順番のみで並び替えているが今後期待収益の順に並び替びかえる事を検討している。それゆえ理想的な広告の並び替えを実現するには広告のクリック率を推定することが必要となる。

　表示回数が多い広告ではクリック率は単純にクリック数を表示回数で割ったものと推測できる。ところが広告のクリック率は基本的にかなり低い（２．６％程度）ため推定の誤差が非常に大きくなってしまう。例えば真のクリック率が５％であるとして８５％の信頼区間でクリック率が４％～６％だと判断するには１０００回広告が表示されなければならない。

不正確な広告掲載順位のランキングはユーザと広告主の満足度を低下させ、収益もダウンする。それゆえ新しくて広告表示回数が少ない広告に対して我々は過去履歴を見る以外の手段でクリック率を予測する方法を発見しなければならない。新しい広告や広告主のために広告がクリックされる確率推定することがこの論文で述べられるシステムの目的である。

　先行研究としてRegelsonとFain[19]が同じ入札語や同じトピックのクラスタによって新しい広告のクリック率を推定するというものがある。しかし我々の経験上同じ語であっても広告のパフォーマンスは大きく異なると言う事を知っている。このことを説明するために入札語以外の特徴を取り入れて考える必要がある。後述するが我々のモデルではそのような特徴を自然な形で取り入れている。

３．検索広告の骨組み

広告がクリックされるには

1. ユーザが広告を見る

2. ユーザが広告をクリックする

の２つの段階を経る必要がある。ここでユーザが広告を見るかどうかは広告の掲載位置のみに依存し、見られた上で広告がクリックされるかは広告の掲載位置に依存しないと仮定すると、あるポジションである広告がクリックされる確率は次のように表される。

ここでCTRをと定義する。

CTRとの減衰曲線からすべての場所での広告のクリック率を推定することができる。

　何度も表示された広告に対しては簡単にCTRを予測することができる。

広告が見られた回数＝広告がクリックされた回数＋クリックはされていないが見られたと思われる回数であり、広告掲載位置ごとの広告が見られる確率は実験で調べることができ、クリックされていないが見られたと思われる回数は推定することができる。最後にクリック数を広告が見られた回数で割るとCTRを求める事が出来る。

　我々の目的は新しい広告に対してこのCTRを予測することである。次のセクションではモデルの学習・テスト用のデータについて述べて、その後モデルの詳細について述べていく。

4. データセット

我々はマイクロソフトのサーチエンジンで実際に使われている広告についての情報を集めた。それぞれの広告には以下の情報が含まれている。

• Landing page：クリック先のURLの情報

• Bid term(“keywords”):広告が表示されるのに必要なクエリ（広告主が事前に入力しておく）

• Title:広告のタイトル

• Body:広告についてのテキストの説明

• Display URL:広告下に表示されるURL

• Clicks:広告が何度クリックされたか

• Views:広告が何度閲覧されたか（第３章で述べた仮定を用いる、広告の表示回数ではなく、閲覧回数は表示回数に広告掲載位置による減衰係数を掛けたものになる。）

広告主は１万、５０万を超えるキーワードに対して広告の数は１００万以上、１０万を超える広告のテキスト

トレーニングセットとして広告主の７０％、検証用として広告主の１０％、テスト用として広告主の２０％を選んだ。

広告のViewがあまりに少ないと実験で求めたCTRと真のCTRがかなりずれてしまうのでViewが１００以下の広告は除くことにした。（トレーニングセットで学習するにあたりView数が大きい方がCTRの予測精度はノイズが少なくなるため良いが、一定のView数を獲得できなかった広告を排除してしまうため偏ったデータとなってしまう。そこでバランスを考えて100という数字を設定した。）

4. モデル

我々はCTRを予測するためにロジスティック回帰を使うことを考える。ロジスティック回帰は値を０～１の間で予測するため本質的に確率の問題に適している。

　

（モデルのここからははっきり言って良くわからない取り合えず様々なツールを使い、情報を精度が出やすいように正規化している）

ここでは広告のi番目の特徴の値であり、は特徴の学習した重みである。

特徴はある単語が含まれているかどうかやタイトル中の単語の数などであるが詳しくは後述する。

ロジスティック回帰はL-BFGS手法[16]を用いて訓練された。我々はゼロ平均ガウス重みを用いてクロスエントロピー損失関数を使い最適な標準偏差σの値を求めた。（よくわからない）最適なσの値は検証セットからσ＝０．１であった。よく行われることだが我々はいつも１にセットされるようなバイアス特徴を加えた。

それぞれの特徴に対して我々はの生成された特徴と、を加えた。１を加えた理由は最低の値を０にするためである、我々は特徴をゼロ平均になり、単位標準偏差を持つように正規化した。異常値を持つ特徴もあったので、偏差値５５以上のものは５５、偏差値４５以下のものは４５となるように調整した。これらの調整により制度の向上が見られた。

　我々の計測方法は、モデルにより予測されたCTRと真のCTRのKL-divergenceをとるというものである（KL-divergenceは低いほうが良い）。この場合KL-divergenceは一回の広告のビューの結果をエンコードするために必要となるビット数を示している。我々のベースラインモデルは単純にトレーニングセットの平均のCTRを予測することである。（トレーニングセットのCTRの平均　＝　テストセットの広告のCTR　とする？）

4. 入札語のCTRの予測

全体の平均のCTRとある入札語のCTRの間にはかなりの差異がある。よって広告のCTRを予測するに当たって、他の同じ入札語、あるいは関連した語のCTRを用いるのが有効である。

6.1 語のCTR

最初の特徴は、同じ入札語の他の広告のCTRである。これをトレーニングセットの広告の平均とうまく組み合わせると次のような式になる。

ここではある入札語を与えている広告主の数ではそれらの広告の平均のCTRである。またはすべてのトレーニングセットの平均のCTRを表している。

我々はロジスティック回帰に（の事だと思う）も特徴として加えた。この２つの特徴をTerm CTR feature setと呼ぶことにする。結果はテーブル１のようになり、誤差を１３％減らすことが出来た。

2. 関連語のCTR

RegelsonとFain[19]の場合と同様に、ある広告の入札語と関連した入札語を持つ広告のを利用したい。そこで入札語の部分集合と上位集合を考える。広告集合を考える、広告の入札語をtとすると、tにm語付け加えたものをと表し、tからn語を取り除いたものをと表し、t からm語付け加えてn語取り除いたものをと表す、これらの集合の総数はで与えられる。ここでこれらの集合のCTRの平均値を次の式により取る

これが関連広告の平均クリック率となり、6.1のをで置き換えて同様の計算をしたところさらに６％の精度の向上が見られた。

4. 広告の質を予測する

前章ではCTRを入札した語だけに基づいて推測したが、それだけでは十分ではなく、入札語が同じでも図３のようにCTRにはかなりの差が生じていることが分かる。そこでこの章

では広告そのものの特徴がよりよいCTRの予測に使えるのかを試したい。そこで広告をクリックするかどうかの判定基準となるような要因を考えてみた。その結果次のようなものが挙がった。

Appearance	広告が審美的に喜ばしいか	title,body内のの単語数、効果的に大文字を取り入れているか？、エクスクラメーションが多すぎないかなど
Attention Capture	広告がユーザを引き込むかどうか	title,body内にbuy,join, subscribeなど行動を示す言葉が入っているか、値段が書かれているかなど
Reputation	広告主が知られているか？または有名なブランドであるか？	ファーストドメイン(.comなど)、ドメイン長、セグメント数(books.comだと２セグント,books.something.comだと３セグメント)、短くて良い.comドメインは広告主が大きくて一流である場合が多い
Landing page quality	クリック先のページの質	フラッシュを含んでいるか、イメージの割合、W３Cの規定を遵守しているか、スタイルシートを使っているか、広告で覆われていないかなど
Relevance	どれだけ検索クエリが広告と関連しているか	入札語がtitleに現れるか？bodyに現れるか、bodyに現れるならその割合は？

全部で８１の特徴を５つのカテゴリから挙げた。

我々はユニグラムの特徴も加えた。広告のトレーニングセットのtitleとbody中で最も使用頻度が高い１００００の語に対して、語が存在したら１の値を、存在しなければ０の値をつけた。これらの特徴は我々が手動でとった特徴の機械版を意図している。これにより我々が発見できなかったような特徴もカバーできるかもしれない。

この結果さらに４％精度が向上した。しかしユニグラムの特徴を使わない場合わずか１％しか精度が向上しなかったのが驚きであった。

4. 命令の詳細さを計測

例えば

Title: Buy shoes now,

Text: Shop at our discount shoe warehouse!

Url: shoes.com

Terms:{buy shoes,shoe,cheap shoes}

というように広告主が命令を与えておくと、広告主は靴を買いに来る人のみを限定的に狙っているということになる。ところが

Title:Buy [term] now,

Text: Shop at our discount warehouse!

Url:store.com

Terms:{shoe,TVs,grass,paint}

と命令を与えるとより広い層の顧客をターゲットしていることになる。ターゲットの絞込みが弱いともいえる。そしてターゲットの絞込みが弱いとCTRも下がってしまうのではないかと我々は考えているのでこれを実証してみる。

ターゲットの広さを測るために、我々は語のカテゴリーエントロピーを計測することにする。方法はまずTermsの語をWebサーチにかけ、その結果得られるスニペットをテキスト分類アルゴリズムにかけることでそれぞれの語を７４のカテゴリーに分類する。そのあと入札語のカテゴリの分布のエントロピーを測り、それを特徴として用いる。我々は入札語の個数も特徴として加えた。エントロピーの特徴と入札語の数の特徴は命令の特異性を扱ったものである。この結果はテーブル３のようになりさらに５．５％程度精度が向上した。

９. データの外部ソースの利用

さらに広告が持つデータ以外のデータを使って２つの特徴を加える。検索ヒット件数と検索回数である。我々は検索回数とCTRの関係を発見した。この関係は図５のようになる。図５より検索回数の多い語はクリック率が高いことが分かる。これらの特徴を考慮して実験したところテーブル４のようになった。ベースラインからだと３％精度が向上したにも関わらず、前章までの組み合わせで実験すると０．５％しか制度が上昇しなかった。これは前章までの特徴の何かと今回の特徴とがオーバーラップしているからである。

１０　結果の討論

10.1 特徴の有用性

それぞれの特徴セットを独立してCTRの予測に用いると、どの特徴がより予測に有効なのか興味が出るところである。そこでそれぞれの特徴セットを独立に計測してKL-divergenceをとったところ広告の質が１２％（人手でつけた特長とユニグラムの特徴、ユニグラムだけだと１０．２％）でエントロピーの特徴が８．９％でサーチデータのセット（検索回数とヒット件数）が３．１％であった。

ロジスティック回帰モデルなので、我々はそれぞれの特徴の重みを知ることができる。その結果はテーブル５のようになった。

ユニグラムの特徴はテーブル６のようになった。これによるとofficialなどがトップに上がってきていることから、ユーザはより権威ある、一流のサイトを好んでクリックする傾向があるといえる。またquotes（見積もり）,trial（試用）,compareなどより限定的なユーザをつかむような単語が使われている場合のクリック率は低くなった。

それぞれの特徴の有用性をつかむのも面白いが、最も実用的なことはできる限り最終的なモデルに多くの特徴を含ませる事である。これによりどんな広告に対しても的確に予測できるようになるのである。

１０．２　初期化後の進化？

我々のモデルはCTRをいくらか正確に予測することができるが、いったいどれくらいのViewがあればCTRが十分に推測できるのであろうか？ベースラインモデルと特徴を用いたモデルの、Viewの数とCTRの誤差の関係を表したグラフは図６のようになる。これによると１００回のView、表示回数に換算すると約２００～３００回の表示でベースラインモデルの誤差と特徴を用いたモデルの誤差が同じになることが分かる。特徴を用いたモデルは１００回Viewがあるまでの期間でうまく作用し、収益増をもたらしてくれる事が分かる。

１０．３　より多くのViewを持った広告

よりView数を多く持った広告をトレーニングセット、テストセットに選びCTRの予想に用いるとより正確なCTRを予測できる。よって１０００Viewを超えた広告のみをトレーニングセット、テストセットに選び同様の実験を行ったところテーブル７のような結果が得られ精度が向上した。しかし１０００Viewを超えるような広告は優良な広告が多くデータにかなりバイアスがかかってしまっている。

１１　将来への考察・展望

• この分野の研究があまりなされていないので、誰でも研究、比較できるように標準となるデータセットが必要である。

• 将来的にはユーザのクエリ情報を用いて、ユーザのクエリと入札語が完全に等しい場合、緩く当てはまる場合などを考慮する必要がある。（緩い例：広告主がパソコンという語が入ったクエリに対して広告を表示するという条件を与えておくと、“パソコン”というクエリ以外にも“中古パソコン”、“パソコン修理”といったクエリに対しても広告が表示される。）例えばクエリと入札語の類似度などを特徴として用いれば、今回のモデルをそのまま適用することができる。

• RegelsonとFain[19]の手法を追加の特徴として取り入れて我々の手法と比較してみたい。

• 実際に実用化させるにあたっては、CTRの予測を広告の表示順位を決めるために使う以外に、広告主にCTRを向上させるアドバイスを与えるために使いたい。

• その他、人による直感的な判断、広告サイトへの再訪問率、滞在時間、またデータを蓄積することで得られる広告主の質などを特徴として加え、さらなる精度の向上を図りたい。
  

最新のSEO関連研究 コンテンツスパムの発見法

検索エンジンのコンテンツに関してスパムにならないようにはどうしたら良いか、キーワードが５％が最適とか言っている前に最新の論文を読んだほうが良いだろう。ということでWorld Wide Web Conference2006からそれに該当する論文を読んで要約してみた、これを理解すればどのような行為がスパムになるのかが良くわかるはずである。SEO業者も必見かと思います。

論文はこちら　このグラフはこの論文中のものを指しています。 また計算式がみにくいですけどこれも論文中のものを見てもらえれば助かります。

Detecting Spam Web Pages through Content Analysis

1. Introduction

サイトのクオリティを高める努力をせずに検索エンジンのランキングを外部リンクや人気キーワードのサイトへの埋め込みなどによって不正に上昇させるような行為を検索エンジンスパムという。英語のサイトの１３．８％はスパムサイトであるといわれているがこれを看破できないサーチエンジンはリソースの約7分の１を浪費してしまい、更にはサーチエンジンのクオリティの低下でユーザが離れてしまうのでどうにかしなければならない。

これらを防ぐために

1. Webの大きさを考ると人手を介さず自動でスパムサイトを発見しなければならない

2. 正統な（スパムでない）サイトをスパムとみなしてはいけない。

3. クエリーをユーザーが投げる前にはスパムを発見したい（そうすることで無駄なロボット巡回、クエリー処理、インデキシングを省くことができリソースを有効活用できる。）

この論文で我々はスパムを発見する様々な方法、また効率、精度よくスパムサイトを発見するアルゴリズムを作るために、如何に個々の方法を統合する機械学習技術を使ったかを示す。

この論文の構成は次のようになる

§２：実験概要、実世界データセットの紹介

§３：データセット中のスパムの蔓延度合いをドメイン、言語別で比較

§４：スパムの発見する方法を説明

§５：我々の手法の評価

§６：関連研究

§７：結論と将来への展望

２．実験概要とデータセット

データセット：MSNサーチエンジンが収集したサイトデータから105,484,446(約１億)のページをランダムで取ってきたもの。

厳密にはMSNサーチが取り込むデータ自体もスパム排除プログラムを潜り抜けたものであるからランダムとは言えないが。しかし実際にユーザが目にするのはそのようなサイトであるし、我々の実験で得られた結果も、真の意味でランダムでとってきたのよりも悪くなるはずなので控えめな見積もりということができるので十分にこの論文の価値はあるといえる。

3. どれくらいスパムがあるの？

この章では、どれくらいスパムがWeb上に蔓延しているのかと、トップドメイン名、国などで区切った時あるページの集合が他のページの集合に比べてどれくらいスパムが多いのかを調べていく。Figure2はどのトップレベルドメインにスパムが多いかを調べた結果であり、Figure3は言語によるスパムサイトの割合である。この二つの実験からスパムはかなりの割合でWebに蔓延しており、また特定のドメインはスパムだらけである。これらの調査はスパム発見手法に生かしていく。

3. 内容に基づいたスパムの発見

我々のWebDBの論文[8]で、我々はスパムの発見手法を数多く説明したが、その中には完全にページの内容と独立したものもある。（リンク構造やDNSレコードを使ったもの）また一方で内容が解釈されていないもの（ページの進化状況、（構造的に？）似たようなものをクラスタリングする）もある。

　この論文では、我々は全てコンテンツに基づいたスパム判定を行う。

　我々は1億のデータから最も多数ある（５４％）英語のページをランダムで１７１６８ページ取得してそのそれぞれに対して人手でスパムページかそうでないかを仕分けした。そのうち１３．８％がスパムページで８６．２％がスパムページでなかった。この章の残りで我々が研究したコンテンツに基づくスパム発見手法を詳細に説明していく。

1. ページ中の単語数

スパムページは人気キーワードをとかく詰め込む傾向があるので、過剰な数の単語がスパムの指標になるのかを調べ、その結果は図４のようになった。確かにページ数が多いほどスパムの割合は高くなるが全ての範囲でスパム率は５０％を切っているのでこれだけでスパムかどうかを判定するわけにはいかない。

2. ページタイトル中の単語の数

スパムの常套手段のもう一つとしてページタイトル中に単語を詰め込むというものがある。そこで我々はページタイトルに含まれる単語数とスパムの関係を調べ、その結果は図５のようになった。図４と図５を比べると図5のページタイトルに含まれる単語数の方がスパムを判断する上で良い指標となるといえる。

3. 単語の平均の長さ

クエリを複数語を指定して投げる時にスペースを入れない人がいるのでそれを狙って単語をつなげているページがある。例えば”freepicture”,”freemp3”などなど。そこで単語の平均アルファベット数とスパムの関係を調べてみたところ図６のようになった。単語の長さが８文字をすぎるとかなりスパムの割合が高くなることがわかる。

4. アンカーテキストの量

リンクはアンカーテキストとなっているが、単に他のページにリンクの渡すためだけのカタログページが存在する。そのようなサイトは大量の初リンクがあるのでアンカーテキストの単語が全単語に占める割合とスパムとの関係を調べた。その結果図７のようになった。ややアンカーテキストの割合が高いほどスパムの確率は上昇するがあまり顕著ではなかった。

5. 見えているコンテンツの割合

マークアップでない単語の総バイトをページの総バイト数で割ったところ図８のようになった。これからスパムページはマークアップ（スクリプトやスタイルシートなども含む）が普通のサイトより少なく人にサイトを見せるための装飾等を省いているといえる。

6. 圧縮率

冗長なコンテンツがあるページは圧縮器をかけることによりサイズを縮小できる。例えば同じ単語が何度も使われていたりすると圧縮率は高くなる。そこでGZIP[14]という圧縮器を使って圧縮率とスパムの関係を調査して、その結果が図９のようになった。　

7. ページ中で一般的に良く使われる単語が含まれる割合

スパムページは検索エンジン対策のため文章が不自然になっている可能性があるので、データセットで上位２００位までの頻出単語が全文章中でどれくらいの割合で使われているのかを調べ、それとスパムとの相関を図１０に示した。この結果スパムページは一般的に使われている単語をあまり使っておらず偏りがあることがわかる。

8. 一般的に良く使われる単語の割合

データセットで上位５００位までの頻出単語のうち何種類がページ中に含まれているかを求めスパムとの相関を調べた。４．７の場合例えばページ中に”a”とだけ書かれた文字があったとするとスコアは１となるが４．８の場合は1/500となる。うまく４．７の欠点を補う意味で調査をした。その結果図１１のようになったが全体的に控えめな結果となった。

9. 独立した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の説明

1. もとのデータセットからN個のデータセットを作る。その時各データセットはもとのデータセットからそれぞれn個のデータをランダムで選んだものとする。（それゆえデータセット間のデータの重複は許される）

2. N個のデータセットそれぞれについて分類器を作成する

3. それぞれの分類器を使ってスパムかスパムでないかを判別する。

4. 最終的な結果は分類器の多数決によって決める。

これがBaggingの概要であるが今回はN=10,n=15453で実験して行ってみたところ結果は表２のようになり正確さは上昇した。

Boostingの説明

1. 最初に全てのデータに1/nの重みを割り当てる（今回の場合n=15453）この重みはトレーニングセットの中で一つデータを取り出した時に該当するデータである確率である。

2. この重みを使って分類器を生成する

3. 分類した際にスパム・ノンスパムの分類を間違えたデータは重みを増やし、正解したデータは重みを減らす（つまり学習例として適しているデータの重みを増やすってことだとは思う）

4. ２．３を繰り返す（今回の場合10回）

5. １０個分類器ができるのでスパム・ノンスパムの判定は重み付投票で決める。

これにより分類してみたところ結果は表３のようになりかなり改善が見られた。

６．RELATED WORK

1. 機械学習の関連研究

C4.5を使ったEmailの分類[16,28]
これは人が読むものに対するスパムだが我々は検索エンジンのロボットが読むためのスパムを発見するという意味で異なる。

2. スパムの役割やシステムについて

   • Henzingerら[15]はスパムがサーチエンジンにもたらす脅威を認めた

   • Perkins[25]が数多くのスパムテクニックを定義しGyongyiとGarciaMolina[13]がよりそれを詳細に分割した。

   • DeStefano[20]はWebスパムと宣伝の関係を指摘(調べてみたらあるサイトのリンクポピュラリティを故意に上げよう（あるサイトを宣伝しよう）とした時に現れるリンク構造を発見したみたいな内容であった)

スパム手法は一般的にリンクスパム、内容スパム、クローキングに大別できる

3. リンクスパムについて

• 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]で我々は切り取りと貼り付けで作ったようなサイトのスパムを調査して、そのようなページを発見する方法を提案した。

3. クローキング
   クローキングとはWebサーバに細工をして検索エンジンの巡回ロボットに一般の閲覧者とは異なる内容のWebページを見せる事を言う。（フラッシュ等を多用しているサイトでは検索エンジンとの親和性が低いためそれをカバーするため最適化したHTML構造を巡回ロボットに見せるというパターンが多い）

   • GyongyiとMolina[13]は現在のクローキングテクニックを示した。

   • WuとDavison[30]は３つの別々のページに共通する単語を計算することに基づいたクローキングの発見方法の有効性を示した。（意味不明）注目すべきはクローキングが有益なものを使うということである。例えば帯域幅やストレージコストを減らすためにサーチエンジンに対してクローキングがマークアップなしでページのコピーを返すような感じである。（サーチエンジンに有用な部分だけを見せるということだと思う）

７．結論と先への展望
Webスパムと検索エンジンのいたちごっこは続いていくであろうが我々の技術がより良い検索のために役立てばうれしいと思う。継続的な研究により効果的なスパムを行うよりもコンテンツ作りを充実させたほうがよりリスクが少ないようになるのが我々の願いである。

ここが変だよGoogle翻訳

GoogleにはGoogle翻訳というサービスがある。http://www.google.co.jp/translate_t?langpair=jaenこれは文法をきちきちと解釈して訳をつくっているのではなく、日本語文書とそれに対応する英語文書があれば、対応関係などを大量に学習して自動的に適切な訳を出してくれる機械学習を用いている。
その性能は非常に高く、別に暇な人が対応表みたいなものをつくったわけでもないのに「千と千尋の神隠し」と入れるとSpirited Awayと返すし、「バイオハザード」と入れるとRezident Evilと、固有名詞までしっかりと学習している。
ところが・・・・「JOJOの奇妙な冒険」と入力すると
WRYYY
とか返してきた。これはJOJOの最大の敵であるDIOの有名な奇声のことなのだが一体何をどう学習すればWRYYYになるのか見当もつきません。Googleなりのギャグととらえるべきでしょうか？
他にも「ニューガンダムは伊達じゃない」とかガンダムの名言でも入れてみるとKiwi is not NYUGANDAMU（ニュージーランド人はガンダムではない）とか返してきた。
今後もGoogleからは目が離せません！

Ajax vs Flash

リッチクライアントを実現するためのコア技術であるAjaxとFlash、どちらがどのような方面で一体優れているのか比較検討してみたい。

ニューヨークで行われたフラッシュ先進会議みたいなものでAjaxの動きがフラッシュ製作者にどのようなインパクトを与えるかという話題があったそうである。

クライアントに対して行えることに関してはFlashはDHTMLよりかなり優位に立っているということがいえる。Ajaxをフラッシュの替わりに用いているサイトの特徴としてはユーザーインターフェースや機能が比較的簡単なものであるということが言える。確かにGooglemapsのような巨大予算を費やした例外もあるが、これはGoogleがビジネス上の思惑でmacromediaやadobeに頼ったシステムを作りたくなかったゆえではないか？という事が伺える。まあしかしフラッシュにもAjaxにも長所、短所がありそれらについて簡単にまとめてみる。

Flash

・プラグインをしなければならず、また決められた範囲の場所にしか表示できない。

・互換性についてはあまり考えなくてもよく作るのが簡単。

・CSSをある程度しかサポートしていない

・javaに似た堅牢なプログラミングモデル

・テキスト表示が弱い、（汚い？）

Ajax

・html、ブラウザとの親和性が高い

・CSSをフルサポート

・動的なコンテンツ生成が容易

個人的にはどちらが良いのかはあまりわかりませんが、javascriptとflashを連携させることなども可能なので両方学習しておいていいとこどりするのが一番いいと思います。

情報可視化インタフェース

数値データから描かれる統計グラフ⇒値の推移を把握するのに適しているが節目と考えられる部位や、背景・影響などを読み取るのは難しい

新聞記事などのテキスト⇒具体的な値の推移把握には不十分だが、背景や影響、節目として解釈すべき箇所を理解する際には有効

ということなのでこれらの情報を相補的に扱うことができればユーザーインターフェースは確実に向上する。

時系列数値情報とテキスト情報を組み合わせて情報を提示する場合、その最も単純な実現方法は、白書等より得られる数値情報を統計グラフとして描画し、新聞記事等のテキスト情報をその発行日を用いてグラフの時間軸に関連付ける方法であろう。

しかし、この方法は欠点があり、それは記事の発効日を利用したとしてもその記事がいつの出来事について書いているのかがわからないということである。今までの変遷をつづったものなのかもしれないし、昨日の出来事を書いたものかもしれない。これをまずテキストの自動解釈技術に基づいていつからいつまでの出来事について書いたものなのかを判別して時間軸と連動させる必要がある。またテキストがグラフのどの変遷箇所に注目して書かれたものなのかを解釈必要がある。

ユーザの探索行為を考えた場合（１）グラフの特徴的な箇所に着目し、それに関する知見を得るためにテキストを参照する。（２）テキスト情報から気になる箇所を見つけそれがグラフのどこに対応しているのかを参照する。っという双方向の情報アクセスが想定できる。そのため、情報提示インタフェースはユーザにテキスト情報の一覧からグラフの対応箇所を見つけるインタラクションを提供する必要がある。

Webで情報可視化インタフェースを考えるとフラッシュかAjaxあたりで実装できそう