著者

成澤和志 山田 泰寛 池田 大輔

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告情報学基礎(FI) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.59, pp.45-52, 2006-05-30

---

プログの増加が著しい近年、プログスパムが大きな問題であり、スパム検出の技術の発達が求められている。スパム検出に関する研究は内容解析やリンク解析によるものが多く、複雑な処理やアルゴリズムを使用する。我々はプログスパムの内容ではなく、コピーされ大凰に生成される性質に着目した手法を提案する。テキストの部分文字列を数え上げた時、出現頻度と異なり数にはジップの法則が成り立つことを利用して、自然言語の知識を必要としない、高速なスパム検出の技術を得ることができる。また、我々は人エ的なデータによる本手法の正当性を調ぺ、実際のプログデータから本手法によりプログスパムを検出することに成功した。Blog spam detection is a key for the blog spam problems as the number of blog sites is extermery in creasing.Existing methods for blog spam detection are based on contexts o rlinkstructures analysis,and does not work well completely.We suggest a method utilizing thefact that spamsaremassproducedatalowcostinsteadoftheircontext・Ourmethoddoesnot need backgroundknowledge of blog entries,such as naturallanguages,because of usingZipf's law for the frequency and the vocabulary size of substrings.We present the validity of our method by artificial data set,and succeed to detect blog spamsftomactualblogentries.

著者

池田 大輔 山田 泰寛 廣川 佐千男

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.46, no.SIG2(TOM11), pp.56-66, 2005-01-15

---

本論文では,複数の文字列に共通な部分を見つける問題を考察する.まず,この問題をパターンから生成された文字列の集合が与えられたときに,そのパターンの定数部分を見つける問題(テンプレート発見問題)として定式化する.パターンとは定数と変数からなる文字列で,パターンが生成する語は変数を定数文字列で置きかえて得られる.置きかえに用いられる文字列中の部分文字列の頻度分布はベキ分布に従うことを仮定し,高確率でテンプレート発見を解くアルゴリズムを構築する.共通部分の発見問題の1 つである最長の共通部分列を探す問題はNP 完全であることが知られているが,問題の再定式化,部分文字列の集合による定数部分の表現方法,部分文字列の頻度と総出現数から共通部分を発見する手法により,テンプレート発見問題は高確率でO(n) 時間で解けることを示す.ここで,n は入力文字列の長さの和である.さらに,このアルゴリズムがノイズに対し頑健であることと,複数のテンプレートが混在する場合でも有効であることを,Web 上の実データに適用することで実証する.

著者

山田 泰寛 池田 大輔 坂本 比呂志 有村 博紀

出版者

社団法人人工知能学会

雑誌

人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence (ISSN:09128085)

巻号頁・発行日

vol.19, no.3, pp.302-310, 2004-05-01

参考文献数

36

被引用文献数

6