블로그의 스팸 덧글 검출하는 방법 - 자카드 유사도(Jaccard similarity). 자바 구현.

지금까지 티스토리 초대장을 70분 정도 나눠드렸는데요.

종종 초대장 받으신 분들이 블로깅 많이 하시나 궁금해서 찾아가봅니다.

근데 그 중 한 두 분 정도 열심히 블로깅을 하시고 나머지 분들은 다 잠수하시더군요.

그리고 그 중 절반 약간 못미치게 30% 정도 사용자가 스팸성 사용자더군요.

얼마 전 블로그 초대장을 배포했는데, 서로 다른 두 초대 포스팅에서 이메일 주소만 다르고 나머지는 비슷한 한 글이 있어서 자카드 유사도를 검사해봤습니다.

자카드 유사도는 두 집합을 비교할 때, 교집합의 원소 갯수 나누기 합집합의 원소 갯수를 자카드 유사도라고 합니다.

공식으로 나타내면 아래와 같습니다.

$$Jaccard \ Similarity = {|A\cap B| \over |A\cup B|}$$

유사도의 최소 0에서 1입니다.

텍스트 마이닝은 물론 그래프 이론에 접목해서 소셜 네트워크에서 스팸 링크 탐지에도 사용합니다.

문제를 정의해보면, 블로그 초대 요청 덧글의 쌍이 주어졌을 때, 덧글의 유사도를 측정해서 스팸인지 아닌지 판단하는 것입니다. 이 때 두 덧글의 유사도가 높다면 스팸으로 판단하는 겁니다.

아래는 검사에 소스 코드입니다.

소스 코드를 올리는 게 엄청 쪽팔리지만 그냥 올립니다. 재미로 보시길... ㅎ

덧글의 토큰을 쪼갤때는 공백과 .?만 구분자(delimiter)로 썼습니다. 

n-gram으로 하려다 생각이 안나서 그냥 단순한 한 워드를 단위로 쪼갰습니다. 

import java.io.*;
import java.util.*;

public class JaccardSimilarity {
	public static void main(String[] args) {
		
		HashMap<String, Integer> S1 = new HashMap<String,Integer>();
		HashMap<String, Integer> S2 = new HashMap<String,Integer>();
		HashMap<String, Integer> S3 = new HashMap<String,Integer>();
		
		try {
			BufferedReader br1 = new BufferedReader(new FileReader("s1.txt"));
			String buffer1="";
			while( (buffer1 = br1.readLine())!=null) {
				StringTokenizer st = new StringTokenizer(buffer1, " ?.");
				while(st.hasMoreTokens()) {
					String tempToken = st.nextToken();
					//System.out.println(tempToken);
					if(!S1.containsValue(tempToken)) {
						S1.put(tempToken, 1);
					} else {
						Integer tempInt = S1.get(tempToken) + 1;
						S1.put(tempToken, tempInt);
					}
				}
			}
			
			BufferedReader br2 = new BufferedReader(new FileReader("s2.txt"));
			String buffer2="";
			while( (buffer2 = br2.readLine())!=null) {
				StringTokenizer st = new StringTokenizer(buffer2, " ?.");
				while(st.hasMoreTokens()) {
					String tempToken = st.nextToken();
					//System.out.println(tempToken);
					if(!S2.containsValue(tempToken)) {
						S2.put(tempToken, 1);
					} else {
						Integer tempInt = S2.get(tempToken) + 1;
						S2.put(tempToken, tempInt);
					}
				}
			}
			
			BufferedReader br3 = new BufferedReader(new FileReader("s3.txt"));
			String buffer3="";
			while( (buffer3 = br3.readLine())!=null) {
				StringTokenizer st = new StringTokenizer(buffer3, " ?.");
				while(st.hasMoreTokens()) {
					String tempToken = st.nextToken();
					//System.out.println(tempToken);
					if(!S3.containsValue(tempToken)) {
						S3.put(tempToken, 1);
					} else {
						Integer tempInt = S3.get(tempToken) + 1;
						S3.put(tempToken, tempInt);
					}
				}
			}
			
			
			br1.close();
			br2.close();
			br3.close();
		} catch (IOException e) {}
		
		// S1과 S2의 JC 계산
		int numOfCommon1 = 0;
		Iterator<String> iS1 = S1.keySet().iterator();
		while(iS1.hasNext()) {
			String tempKey1 = iS1.next();
			if(S3.containsKey(tempKey1)) {
				numOfCommon1++;
			}
		}

		System.out.println(numOfCommon1);
		System.out.println("JC S1 and S2 = " + (double)numOfCommon1/(double)(S1.keySet().size()+S2.keySet().size()-numOfCommon1));
		
		// S2과 S3의 JC 계산
		int numOfCommon2 = 0;
		Iterator<String> iS2 = S2.keySet().iterator();
		while(iS2.hasNext()) {
			String tempKey2 = iS2.next();
			if(S3.containsKey(tempKey2)) {
				numOfCommon2++;
			}
		}

		System.out.println(numOfCommon2);
		System.out.println("JC S2 and S3 = " + (double)numOfCommon2/(double)(S2.keySet().size()+S3.keySet().size()-numOfCommon2));
		
		// S2과 S3의 JC 계산
		int numOfCommon3 = 0;
		Iterator<String> iS3 = S3.keySet().iterator();
		while(iS3.hasNext()) {
			String tempKey3 = iS3.next();
			if(S1.containsKey(tempKey3)) {
				numOfCommon3++;
			}
		}

		System.out.println(numOfCommon3);
		System.out.println("JC S1 and S3 = " + (double)numOfCommon3/(double)(S1.keySet().size()+S3.keySet().size()-numOfCommon3));
		
		
	}
}

36
JC S1 and S2 = 0.13382899628252787
151
JC S2 and S3 = 0.9869281045751634
36
JC S1 and S3 = 0.13382899628252787

덧글 S2와 S3는 거의 다 똑같아서 유사도가 매우 높게 나왔습니다. 그래서 두번째 작성하신 메일로는 초대장을 안보냈습니다.

덧글 S1과 S2의 경우 자카드 유사도는 낮게 나온 것 같은데요. 제가 읽기에 글의 문체와 분위기가 매우 비슷하게 느꼈습니다.

아마 저정도 유사도도 매우 높은건지 몰라요. 더 실험을 안해봐서...

더 정확하게 유사한 덧글을 검출하려면 유사도의 임계치를 실험으로 정하거나, 다른 방법을 써야할 것 같아요.

나머지는 차차 연구해보려구요.