41_08.dvi

Transcription

1 Vol. 2 No (Mar. 2009) Splog 1 2 CGM Consumer Generated Media web splog splog splog suffix array splog Splog Filtering Method Based on Copy String Detection Takaharu Takeda 1 and Atsuhiro Takasu 2 CGM (Consumer Generated Media) data such as blog contains valuable information about customers reputation and it becomes important information source for detecting customers needs and analyzing effects of various product promotion. However, CGM data contains spam content such as so called splogs that are generated for promoting products or improving rank of search results. They are harmful for CGM content retrieval and analysis. This paper proposes a splog filtering method based on the feature of Japanese splogs. The Japanese splogs are often generated by combining words and phrases appearing in various documents. This paper proposes an efficient copy string detection algorithm using the dynamic programming technique and suffix array and apply the proposed algorithm to calculate the ratio of copied strings in a blog. We construct an evaluation corpus for splog filters and show that the proposed method achieves high filtering performance using the corpus ) splog splog web splog spam blog splog splog splog web splog splog splog URL web splog splog splog blog splog 1 The Graduate University for Advanced Studies 2 National Institute of Informatics 93 c 2009 Information Processing Society of Japan

2 94 Splog Kolari splog 1) 3) SVM Support Vector Machines splog 6),12) Zipf splog splog 13) splog Lin 4) splog Lin 5) splog splog splog URL splog diet that works 3 Slabetti 7) splog splog youtubemovie affiliateinfo splog skdsjdljdks g3n0x9h2ja9y1 supervised unsupervised 6),12) splog splog Lin 5) TREC Blog Track , blog splog Kolari 1) 3) 1 blog splog blog splog Salvetti 7) web crawler blog splog 10,000 20,000 13) CSP Contents Service Provider RSS 691, ) yahoo 6) 5 CSP splog 3. splog 11) splog 1 splog splog 1 splog 2 1

3 95 Splog 1 splog Table 1 Categories of splog. 2 splog Table 2 Composite splog generation. news update mail magazine dictionary QA product induction RSS search result word salad full template web wikipedia yahoo EC RSS Rich/RDF Site Summary Really Simple Syndication RSS splogger RSS (X) X API X API html FX 6 combine 1 2 template 1 decorator 2 1 full template splog 12) 4. splog 4.1 s i s i s i s :i s i s i: s i:j s i j s s 3 splog copy rate copy rate splog 4.2 splog blog 1 l B splog b s s B df (s) s

4 96 Splog cpl(s) = { s log B df (s) s l, df(s) 2 0 otherwise IDF Inverse DocumentFrequency b = c 1c 2 c l n c 1 c p1 c p1+1 c p2 c pn 1+1 c l (2) } {{ } } {{ } } {{ } b 1 b 2 b n p (b 1, b 2, b n) (3) b p p bl(b, p) n cpl(b i) (4) i=1 bl (b) max bl(b, p) (5) p P (b) P (b) b 4.3 s O(2 s ) (5) s s p s s (5) { bl 0 s <l (s) = (6) max ss {bl (s p)+cpl(s s)} otherwise s (1) input: b l suffix array A output: b begin set 0 to all components of C for i = l +1to b do for j =1toi l s s(b j:i,a), e e(b j:i,a) C[i] max(c[j],cpl(s,f(s, e)) + C[j]) end end return C[ b ] end 1 Fig. 1 Algorithm for copy length calcuation. (6) s df (s) df (s) suffix array suffix array B s B array suffix array s(s) e(s) df (s) 1 s(b j:i,a) e(b j:i,a) suffix array A 2 b j:i A f(s, e) A s e b j:i suffix array s(b j:i,a) e(b j:i,a) ( 1 ) suffix array 2 array 1

5 97 Splog (2) suffix array 2 O(log A ) suffix array e(b j:i,a) s(b j:i,a)+3 g(b j:i,a) b O( b 2 ) 2 O( b 2 log A ) suffix array O( g(bj:i,a)) i,j b O( b 2 log A + g(b j:i,a)) i,j O( b ) 1 suffix array splog : :00 CSP Content Service Provider RSS Labeled entries web splog/blog 21,668 1 splog 3 splog blogger 3 CSP blog splog splog 3 CSP splog Table 3 Ratio of splogs for each CSP. CSP blog splog livedoor Blog 2, goo 1, LOVELOG 68 8 Yahoo! 1, , JUGEM 1, FC ,155 1, Seesaa 148 1, teacup So-net blog AOL 44 1 Iza! 61 5 CURURU 3 0 Cnet ,797 4, Unlabel entries 21,668 splog/blog 50, Search API ( 1 ) (2) Yahoo!

6 98 Splog (3) ranking/ (4) goo (5) 13,733 API API ( 1 ) livedoor (2) goo ( 3 ) ( 4 ) Namaan (5) Yahoo ( 6 ) Technorati ( 7 ) Google (8) ( 9 ) So-net splog splog 1 splog word salad search result 5.5 html CSP 8) CSP splog threshold splog threshold blog threshold precision recall precision-recall F precision recall F 5 Labeled entries Unlabel entries Search API Unlabel entries+search API l l splog F 2 rp r + p r p recall precision r splog splog splog p (9) splog l F 21,668 F 2 l (7) (8)

7 99 Splog 4 precision recall Table 4 Precision and recall w.r.t. copy rate. threshold precision recall F Fig. 2 Filtering performance w.r.t. mimimum copy string length. blog recall precision F l 15 precision recall F precision recall precision recall 2 Labeled entries Unlabel entries Search API Unlabel entries Search API 4 threshold precision recall Unlabel entries+search API l 15 precision splog recall splog 5 2 precision recall precision recall 5 precision splog splog 9)

8 100 Splog 5 F recall precision Table 5 F-value, recall and precision w.r.t. minimum copy string length. Labeled entries l threshold precision recall F 1 1, , Unlabel entries l threshold precision recall F 1 1, , Search API l threshold precision recall F 1 1, , Unlabel entries+search API l threshold precision recall F 1 1, , Fig. 3 Filtering performance w.r.t. database size. 60 MB , suffix array 4 Fig. 4 Processing time w.r.t. minimum copy string length b suffix array O( b 2 ) 5 O( b )

9 101 Splog Table 6 6 Filtering perfomance of spam template detection method. 5 Fig. 5 Processing time w.r.t. blog entrh length. 6.3 l 15 4 l =1 splog 25 Mbyte 21,668 splog suffix array splog splog splog blog splog blog splog 2, ) 12) (1) Suffix Array f s (2) f s s (3) s Template precision recall F (4) (1) N N 1 splog F splog 6 presicion splog

10 102 Splog splog suffix array suffix array 3 6 Fig. 6 Performance comparison between proposed method and template detection method. recall F 6 recall 12) splog splog 1 splog 7. splog IDF splog suffix array splog 3 1 splog news update full template word salad splog 4.2 (1) IDF Narisawa Zipf 6) (1) splog 1) Kolari, P., Finin, T. and Joshi, A.: SVMs for the blogosphere: Blog identification and splog detection, AAAI Spring Symposium on Computational Approaches to Analyzing Weblogs (2006). 2) Kolari, P., Java, A. and Finin, T.: Characterizing the Splogosphere, Annual Workshop on Weblogging Ecosystem: Aggregation, Analysis and Dynamics (2006). 3) Kolari, P., Java, A., Finin, T., Oates, T. and Joshi, A.: Detecting Spam Blogs:

11 103 Splog A Machine Learning Approach, 21st National Conference on Artificial Intelligence (AAAI 2006 ) (2006). 4) Lin, Y.R., et al.: The splog detection task and a solution based on temporal and link properties, Proc. 15th Text REtrieval Conference (TREC 06 ) (2006). 5) Lin, Y.R., Sundaram, H., Chi, Y., Tatemura, J. and Tseng, B.L.: Splog detection using self-similarity analysis on blog temporal dynamics, 3rd Intl. Workshop on Adversarial Information Retrieval on the Web, pp.1 8 (2007). 6) Narisawa, K., Inenaga, S., Bannai, H. and Takeda, T.: Efficient Computation of Substring Equivalence Classes with Suffix Arrays, 18th Annual Symposium on Combinatorial Pattern Matching (CPM 07 ), pp (2007). 7) Salvetti, F. and Nicolov, N.: Weblog classification for fast splog filtering: A url language model segmentation approach, Proc. Human Language Technology Conference of the NAACL, pp (2006). 8) Takeda, T. and Takasu, T.: UpdateNews: A news clustering and summarization system using efficient text processing, Intl. Conf. on Digital Libraries (JCDL 2007 ), pp (2007). 9) Takeda, T. and Takasu, T.: A Spam Blog Filitering Method Based on Text Copy Detection, The 1st IEEE Intl. Conf. on the Applications of Digital Information and Web Technologie, pp (2008). 10) blog Vol.21, No.4, pp (2006). 11) DEWS2008 (2008). 12) Vol.2006, No.59 pp (2006). 13) Web DBWeb2007 (2007). ( ) ( ) ACM IEEE