Exploring Linguistic Features for Web Spam Detection: A Preliminary Study
J. Piskorski, M. Sydow, D. Weiss
Exploring Linguistic Features for Web Spam Detection: A Preliminary Study
In Proceedings of Fourth International Workshop on Adversarial Information Retrieval on the Web
2008. Apr.
論文の在処
概要
Webのspamに関連した論文。
ページの文書を言語学的に解析して、spamを見つけようとしている。
すごいのは、とにかくたくさんの方法で試してみていることと、そのすべてを定量的に評価していること。
そしてその結果を誰でも利用できるようにしている。
彼らによると、これまでにWebのspam発見の分野ではこのような言語学的なアプローチは無かったらしい。
1. INTRODUCTION
この論文ではSydowらにより[12]で報告された仕事を、より多くのlinguistic-based featuresとWeb spam分類への利用の可能性を研究することで、extendした。
この論文での努力はSection 1.1にある他のcontent-based featuresに関連した仕事の補完。
主なcontributionsは以下
（１）200以上のlinguistic-based attributesを計算したこと。より良い、偏りのない洞察を得るため、様々なNLP toolsと、三つのdocument length-restrictionモードの二つのWeb spam corporaをテストした。
（２）Web spam discriminatorsとしてすべてのattributesの1200以上の分布を準備し、研究したこと。
（３）最も有望なattributesを二つの客観的な基準で実験的に特定したこと。
（４）計算済みのattributesをhistogramsの形でresearch communityで利用できるようにしたこと。*1
この論文で議論されているすべてのfeaturesは計算的には扱いやすく、documentレベルで計算できる。
1.1 Related Work
様々な有用なcontent-based featuresが報告されている。
Fetterlyらは[7]で単純なfrequency-based measuresが有用であることを証明している。
Drostらは[4]でchecksumsとword weighting techniquesに基づいたfeatureを加えることにより、リストを広げている。この方向でのさらなる探求がNtoulasらに[11]で行われている。
Mshneらは[10]でWeb documentのコンテンツを解析し、blog spam発見のためにその言語モデルをその引用しているブログの言語モデルと比較している。
Fetterlyらは[8]でそのコンテンツがnon-spamページからのフレーズの張り合わせで自動的に生成されたようなspamページを特定する技術を報告している。
Urvoyらは[13]で自動生成されパターンに基づいたspamページを発見するためのHTML文書構造に基づいたfeaturesを紹介している。
Benczurらは[2]でMicrosoft OCI、Yahoo! Mindsetや、Google AdWords及びGoogle AdSenseから抽出したキーワードを利用して、ページのcommercial attractivenessを研究している。
既存の様々な結果に基づき、何人かの著者はcontent-based featuresとlink-based featuresを利用した自動spam分類を報告し、bagging、exploration of the link structure for label-smoothing、2-level stacked graphical learning、graph regularizationを含むより洗練された技術を加えてうまく利用している[3,1]。
2. LINGUISTIC FEATURES
Zhouらは[15]であるlanguage featuresがテキストベースのコミュニュケーションにおけるhuman deception detectionに対して特有なポテンシャルを持つことを証明した。
この仕事に触発され、これらのfeaturesのsubsetをWeb spam分類へ適用した。
オープンで制限されていないWebのテキストではよりエラーの多い高いレベルの言語ツールはノイズを生み出すと考え、多くの言語的な洗練された計算をしていないfeaturesだけ考えた。
linguistic featuresの計算のために２種類のNLPツールを使った。
一つはCoreleoneで[9]、extended MULTEXT resource [5]に基づいた形態論的解析器をcomes with。
もう一つはGeneral Inquirerで、辞書に与えられたカテゴリーの数と共にインプットしたテキストをマップする道具。現在のバージョンはHarvard IV-4とLaswellの辞書でカテゴリーは全部で182。
計算はHTMLのボディをテキストに変換したものだけに限定し、すべてのテキストは英語であると仮定して行った。
2.1 Corleone-based features
Corleoneにより計算されるfeaturesは主に品詞情報に基づいているが、品詞の曖昧さはWebのopen-domainという早くから言及されている特徴により解消されていない。
ここでは曖昧な単語に対して品詞タグという時にはタグは全てのを表すとする。たとえばfightという単語にはNVタグがつき、noun(N)とverb(V)を意味する。
Type:
Webページは自由なテキスト、大量のデータ、あるいはそのどちらもを含んでいる。ページの'type'（character）を見積もるための二つのattributesを紹介する。
Lexical validity = # of valid word forms / # of all token
Text-like fraction = # of potential word forms / # of all tokens
potential word formsは掲載粗解析を受けたトークンで、数字、URL、句読点を表すもの、文字じゃないものは含まれない。
Quantity:
テキストの量と言うcontextで全てのトークンの数に対する名詞の割合（Noun Fraction）、動詞の割合（Verb Fraction）、大文字で始まるトークン（Capitalized Tokens）を計算する。
Diversity:
テキストの多様性として以下の三つのタイプを調べる。
Lexical diversity = # of different tokens / # of all tokens
Content diversity = # of different nouns & verbs / # of all nouns & verbs
Syntactical diversity = # of different POS n-grams / # of all POS n-grams
morphological componentに'unknown'とタグ付けされた、頭文字の大文字の単語はContent diversityの文脈では名詞と計算される。Syntactical diversityは２、３、４-gramsで計算される。
さらに品詞n-gramsの分布のエントロピーであるSyntactical entropyを計算する。G = g_1, ... g_kをページの品詞n-gramsの全ての集合として、{p_g}をGの品詞n-gramsの分布とすると、syntactical entropyは以下で計算される。
Syntactical Entropy = -Σ_g∈G p_g・log p_g
Expressivity:
言語の表現性として、content wordの中のmodifiersの割合であるEmotivenessを選ぶ。
Emotiveness = # of adjectives & adverbs / # of all nouns & verbs
Non-immediacy:
言語的なnon-immediacyはcommunicatorが彼ら自身に言及する際のverbal inderectnessのdegreeとして見ることができる。
non-immedicacyのdegreeの測定方法として以下の二つのスコアを定義する。
Passive Voice = # of passive constructions / # of all verbs
Self Referencing = # of 1st person pronouns / # of all pronouns
Ucertainty:
uncertaintyの測定方法として、全ての動詞に対する法動詞の割合を計算する。（Modal Verbs）
Affect:
ページのaffectを計算するため、SENTIWORDNET[6] （Coreleoneに組み込まれている）を利用。SENTIWORDNETではWORDNET*2のそれぞれのsynset sはPos(s)とNeg(s)という二つのスコアを持っていて、それぞれsynset s含まれるtermsがどれくらい'positive'か'negative'かを表す。特に、t_iはテキストの中のi番目のトークンを表すとして、テキストT = t_1 ... t_2として、以下のPosSentとNegSentを計算する。
PosSent = Σ_t∈T max(Pos(t)) / Σ_t∈T max(Pos(t)) + max(Neg(t))
NegSent = Σ_t∈T max (Neg(t)) / Σ_t∈T max(Pos(t)) + max(Neg(t))
トークン（term）tは潜在的に違った意味を持っているので、それぞれのトークンtに対して、tが所属するsynsetsのスコアで最大のPosスコアと最大のNegスコアを計算する。
このようにして、positiveな意味とnegativeな意味両方で使われているtermsはなんとか中和される。
次に、重さの就いていないaffectスコアを計算する。それは約1200のopinion expressionsに基づいた全てのopinion expressionsに対する'positive' tonality expressionsの割合（Tonality）。
2.2 Features obtained with General Inquirer
General Inquirer（GI）の182のカテゴリーは社会科学者によるcontent analysisの適用により開発された。GIによって割当てられるこれらのカテゴリーの値はoccurrence statisticsに基づいている。
これらのいくつかはsection 2.1で定義されたfeaturesとかぶっているが、それぞれのGIカテゴリーを別のものとして扱う。GIによってカバーされているカテゴリーのスナップショットがTable 1に示されており、詳細はWebページ*3で見られる。
3. EXPERIMENTS
3.1 Data Sets
Web spamのデータセットとしてWebSpam-Uk2006とWebSpam-Uk2007[14]を用いた。
これらのデータは.uki Web domainの２回の一般的なクロールで得られたもので、それぞれのページのコンテンツ、リンク、人の手によって割り当てられたカテゴリー（spam、non-spam、borderline、undecided）を持っている。
実験ではホストごとに幅優先探索による400のサンプルページを用いた。
元のGZIP-compressed WARCファイルをまずbinaryのblock-compressed wequenceファイルに変換し、map-reduce programming paradigmを用いて分散実行できるようにした。
10 quad-coreマシンのクラスタで動いているHadoop project*4を計算に用いた。
データセットの統計データはTable 1にある。
3.2 Histograms
二つのデータセットに対してCorleoneとGeneral Inquirerを使ってlinguistic attributesを計算した。
計算するにあたり以下の三つのモードを考えた。
(0)50k以下のトークンを含むからでない文書
(1)150から20kのトークンを含む文書
(2)400から5kのトークンを含む文書
(1)と(2)はとても短い文書（多くのノイズを生み出す可能性がある）と、とても長い文書（文書の長さがベキ則のようになっているので、計算速度の低下を招く）の影響を調べるためのもの。
以上の６つのコンビネーションに対して、208のlinguistic attributesを計算した。（23がCoreleone、185がGeneral Inquierer）
そして、それぞれのattributeの値にたいして、文書レベルでの度数分布図を、spam、non-spam、borderlineのカテゴリーに対して作った。（文書レベルでのラベル付けはWebSpam-Uk2006でもWebSpam-Uk2007でもなされていないため、文書にはそのホストのラベルを付けた。）これにより1200以上の度数分布図が生成された。
すべての度数分布図は横軸にattributesの値の幅（bins）、縦軸にはその範囲に入るページのパーセンテージを取った。
これらの度数分布図の予備的な調査結果は以下。
- 長さの制限をした文書に対して得られた度数分布図は顕著に（mode-0に比べて）ノイズが少なかった。
- mode-2の度数分布図はmode-1のそれと比べてわずかにnoisyだと思われたため、次のsectionではmode-2のみを使う。
- borderlineの度数分布図は一般的にspamのそれと近かったが、この点はより厳密に調べる必要がある。
3.3 Objective selection of the best attributes
主観的な観察を広げるため、客観的な方法で有望なattributesを特定するために、以下に定義されるの二つのdifference measures（absDist、sqDist）を紹介する。
それぞれのattributeに対して、spamクラスとnon-spamクラスの差異をこのmeasuresを用いて測定する。
attributeの度数分布図hに対して、{s^h}_iと{n^h}_iをbins i∈Iのバーの高さのsequencesとする。
absDist(h) = Σ_i∈I |s^h_i - n^h_i| / 200
これはspamとnon-spamの度数分布のカーブに囲まれた部分の面積の割合と解釈できる。
sqDist(h) = Σ_i∈I (s^h_i/max_h - n^h_i / max_h)^2 / |I|
max_hは正規化のファクターの類いで、{s^h}_iと{n-h}_iの中で最大の値。
absDistはより自然な幾何学的な解釈なので、より直感的に思える。しかし二つの違った測定基準が結果の偏りを減らしてくれる。
いずれの測定基準でも高い値がより識別の力があることを意味する。
次に、最も良いattributesを特定するために、1200からなる度数分布図に対して両方のmeasuresを計算し、6つのセッティングごとに値の降順でソートした。
面白いことにトップ10のattributesではどちらのmeasuresでも6つのセッティングによらず長さの制限はほとんど意味をなさなかった。例えば二つの測定基準がまるで違うにもかかわらず、Corleoneのトップ9のattributesは二つのデータセット、測定基準で同じリストになった。結果はTable 2にある。
absDistの場合いくつかの度数分布図ではAUC（area under the ROC curve）が25パーセント違った。これはそれらの潜在的な識別の力を示している。
4-grams、mode-2、WebSpam-Uk2007のSyntactical Diversityの度数分布図がFigure 2にある。
同じような実験をGIにより得られたattributesに対しても行った。
absDistではトップ7のattributesが二つのデータセットで一致した。Table 3に結果あり。
いくつかのattributesではspamの度数分布図のAUCとnon-spamの度数分布図のAUCでは30パーセント違い、Coreleoneにより得られたattributesよりも有望だと言える。
sqDistではトップ9のattributesが二つのデータセットで一致した。Table 3に結果あり。
全く違った測定基準から顕著なオーバーラップをもったリストが得られた。
GIから得られたattributesでいくつかのものが一つだったり別のmeasureやセッティングでもトップ10に入った。それらは以下
EnlOth、EnlTot（enlightenment words、啓蒙語）
WltTot、WltOth（Words in wealth domain、例えばpursuit of wealth）
ECON、Wcon@dat（words reffering to objects、例えばfood、vehicles、building）
Leftover（他の'大きい'GIのカテゴリーに関連付けられなかった'lasswell dictionary'のattributesを網羅し、達成、取引、望まれるあるいは望まれない終わりやゴールの単語、意味や実用性に言及した単語、俳優、国家、感情を意味する単語を含む）
CorleoneのattributesよりGIのattributsの方が7倍も多いので、GIにより得られたattributesのトップリストはより不安定であると言える。
3.4 Discussion
一般的に、明らかな分布の違いが見られたことから、計算したattributesの中で最も良いものはspamかnon-spamの見極めにかなり有望であることを観察した。
また、attriutesのトップリストはWebコーパスの選択に関してかなり安定しており、attributesにとっては重要な良い側面である。
Corleoneにより得られたattributesよりGIにより得られたattributesの方がより潜在的な識別の力が大きいように思われる。
驚くべきことではないが、GIから得られたattributesでトップスコアだったものは商品の購入、取引、ビジネス、産業、人間でないもの、啓蒙運動の周りのvocabulary centeringに関連したものだった。
別の面白い発見として、syntactical diversityがlexical diversityよりも良い識別の力を示したことがある。
これはキーワードを大雑把に組み合わせてできたspamページは浅薄なsyntactical analysisにより決定できることを意味する。
一方で明らかにspamとnon-spamのクラスを分けられるようなattributesはなかった。これはおそらくspammersが現存するWebコンテンツを再利用し、繰り返し使ったり、自分のコンテンツと交互に重ねて使ったりしているからである。
最後に[15]の仕事とは対照的に、表現力、あいまいさ、感情はspamを見つけるの力がないように思われた。
たぶん、より良い洞察を得るために、前述のlanguage featuresを計算するためのより洗練されたattributesが研究されるべきである。
4. CONCLUSION
200以上のlinguistic-based attributesを二つのWeb spamコーパスに対して計算し、1200以上の解析結果の度数分布図の一般的な特徴に関して議論した。
知る限りではこのようなattributesはWeb spam発見の文脈ではこれまでに研究されていない。
特に、二種類の、分布の違いの測定方法はもっとも有望なattributesを特定するのに使える。あとの方のリストはいろいろなセッティングに対して安定しているように思われるが、これらの本当の有用性は今後研究される。
すべての計算されたattributesと度数分布図は研究目的で利用可能。
5. REFERENCE
[1] J. Abernethy, O. Chapelle, and C. Castillo. Witch: A new approach to web spam detection, 2007. submitted.
[2] A. Bencz´ur, I. B´ır´o, K. Csalog´any, and T. Sarl´os. Web spam detection via commercial intent analysis. In Proceedings of AIRWeb 2007, pages 89–92, New York, NY, USA, 2007. ACM.
[3] C. Castillo, D. Donato, A. Gionis, V. Murdock, and F. Silvestri. Know your neighbors: web spam detection using the web topology. In SIGIR ’07: Proceedings of the 30th ACM SIGIR conference, Amsterdam, The Netherlands, pages 423–430. ACM, 2007.
[4] I. Drost and T. Scheffer. Thwarting the nigritude ultramarine: learning to identify link spam. In Proceedings of ECML 2005, volume 3720 of LNAI, pages 233–243, Porto, Portugal, 2005.
[5] T. Erjavec. MULTEXT – East Morphosyntactic Specifications, 2004. URL: http://nl.ijs.si/ME/V3/msd/html.
[6] A. Esuli and F. Sebastiani. SentiWordNet: A publicly available lexical resource for opinion mining. In Proceedings of LREC 2006, pages 417–422, Genova, IT, 2006.
[7] D. Fetterly, M. Manasse, and M. Najork. Spam, damn spam, and statistics: using statistical analysis to locate spam web pages. In Proceedings of WebDB ’04, New York, USA, 2004.
[8] D. Fetterly, M. Manasse, and M. Najork. Detecting phrase-level duplication on the world wide web. In Proceedings of SIGIR ’05, pages 170–177, New York, NY, USA, 2005. ACM.
[9] Jakub Piskorski. Corleone - Core Linguistic Entity Extraction. Technical Report. JRC of the European Commission, 2008.
[10] G. Mishne, D. Carmel, and R. Lempel. Blocking blog spam with language model disagreement. In Proceedings of AIRWeb 2005, May 2005.
[11] A. Ntoulas, M. Najork, M. Manasse, and D. Fetterly. Detecting spam web pages through content analysis. In Proceedings of WWW 2006, Edinburgh, Scotland, pages 83–92, 2006.
[12] M. Sydow, J. Piskorski, D. Weiss, and C. Castillo. Application of machine learning in combating web spam, 2007. submitted for publication in IOS Press.
[13] T. Urvoy, T. Lavergne, and P. Filoche. Tracking web spam with hidden style similarity. In AIRWeb 2006, pages 25–31, 2006.
[14] Webspam corpora. URL: http://yr-bcn.es/webspam/datasets, accessed February 21, 2008.
[15] A. Zhou, J. Burgoon, J. Nunamaker, and D. Twitchell. Automating Linguistics-Based Cues for Detecting Deception of Text-based Asynchronous Computer-Mediated Communication. Group Decision and Negotiations, 12:81–106, 2004.
