소결 북마킹(social bookmarking) 시스템은 사용자가 북마크를 저장하고 공유할 수 있는 플랫폼을 제공하는 웹 기반(web-based) 시스템으로 폭소노미(folksonomy)를 이용한 대표적인 웹2.0 서비스이다. 소셜 북마킹 시스템에서의 스패머(spammer)란 자신들의 이익을 위해서 시스템을 고의적으로 악용하는 사람을 말한다. 스패머는 많은 양의 잘못된 정보를 시스템에 포스팅(posting)하기 때문에 전체 소셜 북마킹 시스템의 리소스(resource)를 쓸모없게 만들어 버린다. 따라서, 스패머를 빠른 시간 안에 탐지하고 그들의 접근을 차단하는 것은 시스템의 붕괴를 방지하기 위해 중요하다. 본 논문에서는 사용자가 사용한 태그에 대한 데이터를 추출하여, 사용자가 스패머 인지 아닌지를 예측하는 모델을 기계학습의 다양한 방법을 적용하여 생성한 후 그 성능을 비교해 보았다. 구체적으로, 결정테이블 (decision table, DT), 결정트리(decision tree, ID3), 나이브 베이즈 분류기($na{\ddot{i}}ve$ Bayes classifier), TAN(tree-augmented $na{\ddot{i}}ve$ Bayes) 분류기, 인공신경망(artificial neural network)의 방법을 비교하였다. 그 결과 AUC(area under the ROC curve)와 모델 생성시간을 고려하였을 때 나이브 베이즈 분류기가 가장 만족할 만한 성능을 보였다. 나이브 베이즈 분류기의 분류 결과가 가장 좋았던 이유는 성능을 비교하는 데 사용된 AUC가 결정트리 계열의 방법(ID3 등)보다 나이브 베이즈 분류기에서 일반적으로 높게 나오는 경향이 있다는 것과, 스패머 탐지 문제가 선형으로 분리 가능한 경우(lineally separable)와 유사할 가능성이 높기 때문으로 여겨진다.
소결 북마킹(social bookmarking) 시스템은 사용자가 북마크를 저장하고 공유할 수 있는 플랫폼을 제공하는 웹 기반(web-based) 시스템으로 폭소노미(folksonomy)를 이용한 대표적인 웹2.0 서비스이다. 소셜 북마킹 시스템에서의 스패머(spammer)란 자신들의 이익을 위해서 시스템을 고의적으로 악용하는 사람을 말한다. 스패머는 많은 양의 잘못된 정보를 시스템에 포스팅(posting)하기 때문에 전체 소셜 북마킹 시스템의 리소스(resource)를 쓸모없게 만들어 버린다. 따라서, 스패머를 빠른 시간 안에 탐지하고 그들의 접근을 차단하는 것은 시스템의 붕괴를 방지하기 위해 중요하다. 본 논문에서는 사용자가 사용한 태그에 대한 데이터를 추출하여, 사용자가 스패머 인지 아닌지를 예측하는 모델을 기계학습의 다양한 방법을 적용하여 생성한 후 그 성능을 비교해 보았다. 구체적으로, 결정테이블 (decision table, DT), 결정트리(decision tree, ID3), 나이브 베이즈 분류기($na{\ddot{i}}ve$ Bayes classifier), TAN(tree-augmented $na{\ddot{i}}ve$ Bayes) 분류기, 인공신경망(artificial neural network)의 방법을 비교하였다. 그 결과 AUC(area under the ROC curve)와 모델 생성시간을 고려하였을 때 나이브 베이즈 분류기가 가장 만족할 만한 성능을 보였다. 나이브 베이즈 분류기의 분류 결과가 가장 좋았던 이유는 성능을 비교하는 데 사용된 AUC가 결정트리 계열의 방법(ID3 등)보다 나이브 베이즈 분류기에서 일반적으로 높게 나오는 경향이 있다는 것과, 스패머 탐지 문제가 선형으로 분리 가능한 경우(lineally separable)와 유사할 가능성이 높기 때문으로 여겨진다.
Social bookmarking systems are a typical web 2.0 service based on folksonomy, providing the platform for storing and sharing bookmarking information. Spammers in social bookmarking systems denote the users who abuse the system for their own interests in an improper way. They can make the entire reso...
Social bookmarking systems are a typical web 2.0 service based on folksonomy, providing the platform for storing and sharing bookmarking information. Spammers in social bookmarking systems denote the users who abuse the system for their own interests in an improper way. They can make the entire resources in social bookmarking systems useless by posting lots of wrong information. Hence, it is important to detect spammers as early as possible and protect social bookmarking systems from their attack. In this paper, we applied a diverse set of machine learning approaches, i.e., decision tables, decision trees (ID3), $na{\ddot{i}}ve$ Bayes classifiers, TAN (tree-augment $na{\ddot{i}}ve$ Bayes) classifiers, and artificial neural networks to this task. In our experiments, $na{\ddot{i}}ve$ Bayes classifiers performed significantly better than other methods with respect to the AUC (area under the ROC curve) score as veil as the model building time. Plausible explanations for this result are as follows. First, $na{\ddot{i}}ve$> Bayes classifiers art known to usually perform better than decision trees in terms of the AUC score. Second, the spammer detection problem in our experiments is likely to be linearly separable.
Social bookmarking systems are a typical web 2.0 service based on folksonomy, providing the platform for storing and sharing bookmarking information. Spammers in social bookmarking systems denote the users who abuse the system for their own interests in an improper way. They can make the entire resources in social bookmarking systems useless by posting lots of wrong information. Hence, it is important to detect spammers as early as possible and protect social bookmarking systems from their attack. In this paper, we applied a diverse set of machine learning approaches, i.e., decision tables, decision trees (ID3), $na{\ddot{i}}ve$ Bayes classifiers, TAN (tree-augment $na{\ddot{i}}ve$ Bayes) classifiers, and artificial neural networks to this task. In our experiments, $na{\ddot{i}}ve$ Bayes classifiers performed significantly better than other methods with respect to the AUC (area under the ROC curve) score as veil as the model building time. Plausible explanations for this result are as follows. First, $na{\ddot{i}}ve$> Bayes classifiers art known to usually perform better than decision trees in terms of the AUC score. Second, the spammer detection problem in our experiments is likely to be linearly separable.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
그렇기 때문에 시스템을 악용하는 사용자를 빠른 시간 안에미리 탐지하고 접근을 차단하는 것은 시스템 전체의 붕괴를 막기 위해 중요하다. 본 논문에서는 시스템을 악용하는 사용자-스패머(spammer)-를 탐지하기 위한 모델을 다양한 기계학습 기법들을 이용해 생성한 뒤, 각각의성능을 비교 및 분석하여 이 작업에 가장 적합한 방법을 결정하고 그 이유를 분석하였다.
제안 방법
결정테이블(decision table, DT), 결정트리(decision tree, ID3), 나이브 베이즈 분류기(naive Bayes clas sifier), TAN(tree-augmented naive Bayes) 분류기, 인공신경망(artificial neural network)의 방법으로 태그를 100개, 300개, 500개로 다르게 하여 성능을 비교하였다. 추가로 각 실험에서 모델 생성시간을 비교하였고, 실험은 웨카(Weka) 패키지9)를 이용하였다.
반면에 결정트리 계열(decision table 및 ID3)의 기계학습 방법의 성능이 상당히 좋지 않았다. 결정트리 계열의 기계학습 방법의 성능이 낮게 나온 원인이 실험에 사용한 데이터의 액티브유저와 스패머의 비율이 지나치게 편향되어 있기 때문이라는 가설올 세우고, 이를 검증하기 위해서 추가적인 실험을 진행하였다. 데이터의 편향을 제거하기 위해서 표본추출[under-sam- pling]을 통해 학습데이터와 테스트데이터의 스패머와액티브유저의 비율을 1:1로 조정한 후 추가 실험을 진행하였다.
데이터에 포함된 여러 가지 특성(feature) 중에서 사용자가 사용한 태그를 모델 학습에 사용하였다. 주어진데이터에서 사용된 약 400, 000개의 태그 중에서 유용한태그를 선택하기 위해서 태그의 상호정보량 (mutual information)[5]을 이용하였다.
결정트리 계열의 기계학습 방법의 성능이 낮게 나온 원인이 실험에 사용한 데이터의 액티브유저와 스패머의 비율이 지나치게 편향되어 있기 때문이라는 가설올 세우고, 이를 검증하기 위해서 추가적인 실험을 진행하였다. 데이터의 편향을 제거하기 위해서 표본추출[under-sam- pling]을 통해 학습데이터와 테스트데이터의 스패머와액티브유저의 비율을 1:1로 조정한 후 추가 실험을 진행하였다.
시스템이다. 또한 사용자 간의 북마크 정보 공유를통해서 북마킹의 분류와 검색까지 효과적으로 행하고관리할 수 있는 도구를 제공한다. 이들 시스템의 중요한특징은 사용자가 리소스를 시스템에 더한 후 직접 태그를 붙이고 그것을 공유한다는 것이다.
스패머를 탐지하는 모델을 만들기 위해서 주어진실험 데이터에서 상호정보량이 높은 태그들을 추출하였고 이를 속성으로 이용하여 기계학습의 여러 알고리즘을 적용하여 성능을 비교해 보았다. 여러 방법 중에서나이브 베이즈 분류기 방법이 성능과 모델 생성시간에서 만족할 만한 결과를 주었으며 이는 문제의 특성 및그 평가 기준에 기인하는 것으로 여겨진다.
크게 다음과 같은 두 가지가 있다. 첫째, 시스템에특정 사이트의 링크를 두어서 이목을 끌어 자신들의 사이트를 광고한다. 둘째, 유명한 웹2.
추가로 각 실험에서 모델 생성시간을 비교하였고, 실험은 웨카(Weka) 패키지9)를 이용하였다.
대상 데이터
Challenge, )에서 제공한 것이다. 데이터는 북마크와 빕텍스(bibtex) 정보를 공유하는 빕소노미 (Bib- Sonomy)에서 수집된 데이터로 2, 467명의 액티브 유저 (active user 혹은 non-spammer)오} 29, 248명의 스패머에 대한 것이며, 이는 수작업으로 분류되어 제공되었다데이터는 총 7개의 데이터베이스 테이블로 구성되어 있으며, 그 각각의 내용과 크기는 표 1과 같다.
실험에 사용한 데이터는 ECML & PKDD 2008의 Discovery Challenge, )에서 제공한 것이다. 데이터는 북마크와 빕텍스(bibtex) 정보를 공유하는 빕소노미 (Bib- Sonomy)에서 수집된 데이터로 2, 467명의 액티브 유저 (active user 혹은 non-spammer)오} 29, 248명의 스패머에 대한 것이며, 이는 수작업으로 분류되어 제공되었다데이터는 총 7개의 데이터베이스 테이블로 구성되어 있으며, 그 각각의 내용과 크기는 표 1과 같다.
특징을 가지고 있다. 학습데이터로는 2008년 1월까지의 데이터를 사용하고, 테스트데이터로는 2008년 2월과 3월의 데이터를 사용하였다. 데이터에 대한 통계는 다음과 같다.
이론/모형
주어진데이터에서 사용된 약 400, 000개의 태그 중에서 유용한태그를 선택하기 위해서 태그의 상호정보량 (mutual information)[5]을 이용하였다. 각 태그의 상호정보량을계산한 후에 그 값이 높은 태그들에 대하여 유저가 그태그를 사용했는지 사용하지 않았는지를 속성으로 하여학습데이터를 생성하였다’ 높은 상호정보량을 가진 태그로 학습데이터를 생성하는 과정은 그림 1과 같으며 아래는 각 단계에 대한 자세한 설명이다.
성능/효과
모든 방법에 대해서 사용한 태그가 많을수록 성능이 향상되었다. 각 기법들의 성능을 비교해 보았을 때, 나이브베이즈 분류기, TAN 분류기, 인공신경망이 85%〜90% 로 비교적 높은 결과를 보였고, 결정테이블과 결정트리가 70%〜85%로 비교적 낮은 결과를 보였다. 표 4는 각알고리즘의 모델 생성시간을 비교하고 있다.
이는 나이브 베이즈 분류기의 학습이 다른 방법과 달리탐색 (search)을 필요로 하지 않기 때문이다. 나이브 베이즈 분류기, TAN, 인공신경망이 비록 비슷한 성능을보인다고 하여도, 모델 생성시간에 비추어 볼 때 나이브베이즈 분류기가 태그를 이용한 스패머 탐지 문제에는가장 적절한 방법임을 알 수 있다.
첫째, 시스템에특정 사이트의 링크를 두어서 이목을 끌어 자신들의 사이트를 광고한다. 둘째, 유명한 웹2.0 사이트에 그들의사이트로 향하는 링크를 최대한 많이 두어서 자신들의사이트의 페이지랭크(PageRank)를 높여 구글과 같은검색엔진에서의 노출을 확대한다. 이러한 목적을 가지고시스템을 남용하는 사람을 스패머라고 부른다.
모든 방법에 대해서 사용한 태그가 많을수록 성능이 향상되었다. 각 기법들의 성능을 비교해 보았을 때, 나이브베이즈 분류기, TAN 분류기, 인공신경망이 85%〜90% 로 비교적 높은 결과를 보였고, 결정테이블과 결정트리가 70%〜85%로 비교적 낮은 결과를 보였다.
실험 결과 나이브 베이즈 분류기가 가장 좋은 성능을보였고, TAN 분류기와 인공신경망은 그에 준하는 성능을 보였다. 반면에 결정트리 계열(decision table 및 ID3)의 기계학습 방법의 성능이 상당히 좋지 않았다.
스패머를 탐지하는 모델을 만들기 위해서 주어진실험 데이터에서 상호정보량이 높은 태그들을 추출하였고 이를 속성으로 이용하여 기계학습의 여러 알고리즘을 적용하여 성능을 비교해 보았다. 여러 방법 중에서나이브 베이즈 분류기 방법이 성능과 모델 생성시간에서 만족할 만한 결과를 주었으며 이는 문제의 특성 및그 평가 기준에 기인하는 것으로 여겨진다.
결과를 보여주었다. 이를 통해서 데이터의 불균형이 살험 결과에 의미있는 영향을 주지는 않았음을 확인하였다.
첫째, 본 논문에서 기계학습 방법의 성능을 비교하는 데 사용한 평가 기준인 AUC는 나이브 베이즈 분류기가 결정트리 계열의 방법(ID3, C4.5 등)보다 높게 나오는 경향이 있다⑻. 그 원인은 AUC의 특성과 나이브베이즈 분류기와 결정트리의 사후 확률을 표현하는 능력의 차이와 관련이 있다.
특징이 있다. 첫째, 북마크가 기계에 의해서 자동으로 분류되지 않고 북마크의 내용을 이해하는 사람에 의해서 분류되기 때문에 북마크가 의미를 가지고 있으며유용하다. 둘째, 사용자들은 아직 유명하지 않거나 기존의 웹 검색엔진에 등록되지 않은 웹 페이지를 북마크하는 경향이 있기 때문에 새로운 웹 페이지를 찾을 수있다.
표 5의 실험 결과를 보면, 결정트리 계열인 ID3의 성능이 조금 상승하였으나 여전히 다른 기법들에 비해서낮은 결과를 보여주었다. 이를 통해서 데이터의 불균형이 살험 결과에 의미있는 영향을 주지는 않았음을 확인하였다.
참고문헌 (9)
Heymann, P., Koutrika, G., and Garcia-Molina, H., Can social bookmarking improve web search?, Proceedings of the First ACM International Conference on Web Search and Data mining, 2008
Mathes, A., Folksonomies - cooperative classification and communication through shared metadata, unpublished paper, http://www.adam-mathes.com/academic/computermediatedcommunication/folksonomies.html, 2004
Hotho, A., Jaschke, R., Schmitz, C., and Stumme, G., BibSonomy: a social bookmark and publication sharing system, Proceedings of the Conceptual Structures Tool Interoperability Workshop at the 14th International Conference on Conceptual Structures, pp. 87-102, 2006
Hotho, A., Jaschke, R., Schmitz, C., and Stumme, G., Information retrieval in folksonomies: search and ranking, Proceedings of the Third European Semantic Web Conference, pp. 411-426, 2006
Cover, T.M. and Thomas, J.A., Elements of Information Theory, Wiley-Interscience, 1991
Fawcett, T., An introduction to ROC analysis, Pattern Recognition Letters, Vol.27, pp. 861-874, 2006
Huang, J., Lu, J., and Ling, C.X., Comparing na $\ddot{i}$ ve Bayes, decision trees, and SVM with AUC and accuracy, Proceedings of the Third IEEE International Conference on Data Mining, pp. 553-556, 2003
Ling, C.X. and Zhang, H., The representational power of discrete Bayesian networks, Journal of Machine Learning Research, Vol.3., No.Dec., pp. 709-721, 2002
※ AI-Helper는 부적절한 답변을 할 수 있습니다.