공학석사학위청구논문 블로그구조분석기반으로사용자행동을이용한 스팸블로그여과방법 Spam Blog Filtering using User Actions based on Analysis of Blog Structures 2008 년 02 월 인하대학교대학원 컴퓨터정보공학과 한아성
공학석사학위청구논문 블로그구조분석기반으로사용자행동을이용한 스팸블로그여과방법 Spam Blog Filtering using User Actions based on Analysis of Blog Structures 2008 년 02 월 지도교수조근식 이논문을공학석사논문으로제출함 인하대학교대학원 컴퓨터정보공학과 한아성
이논문을한아성의석사학위논문으로인정함. 2008 년 02 월 주심 ( 인 ) 부심 ( 인 ) 위원 ( 인 )
요 약 1인 1 미디어의시대로접어들면서블로그의사용이급격히증가하였다. 이에따라, 필요한블로그를쉽게검색할수있는블로그전용검색엔진이등장하였다. 블로그에많은사용자들이다양한글을포스팅하며블로그공간을풍성하게하는반면, 이를역으로이용해문제를일으키는스플로그도늘어나고있다. 최근의스플로그는내용구분이쉬운단어를포함하고있던과거와달리정상적인, 혹은최근화두가되고있는내용을포스팅한다. 이를이용해, 보다많은사용자를블로그로유입시킨후블로그자체내에광고를설치하여스팸을노출시키는특징이있다. 그러나지금까지논의되어온많은방법들은스플로그의내용을기반으로하여스플로그를여과하기때문에최근급속히퍼져가는새로운형태의스플로그에대한여과성능이매우떨어진다. 따라서이러한형태의스플로그를효과적으로여과하여블로그검색엔진의성능을향상시키는새로운방법이필요하게되었다. 본논문에서는블로그의구조적특성을기반으로스플로그를여과하고자한다. 블로그사이의상호작용및블로그와포스트, 포스트와포스트, 덧글및트랙백과같은블로그만의고유한구조를분석하고, 이를기반으로각블로그와포스트에대한신뢰도를구축하여랭킹알고리즘에적용한다. 각블로그와포스트에부여된신뢰도는이들과상호작용하는블로그및포스트의신뢰도에영향을주며, 하나의블로그와그내부포스트간의관계까지고려하고자한다. 랭킹알고리즘으로는가중치가부여된 HITS 알고리즘을사용하여본 i
논문이제안하는시스템의스플로그여과정확도를측정한다. 또한, 블로그에대한사용자의행동을기반으로가중치를결정하여여과정확도를높이고자한다. 각포스트와, 포스트가속한블로그에사용자가머문시간을측정하여사용자의관심도를가중치에반영한다. 실험을위해페이지간의링크구조만을고려하여점수를부여하던기존연구와의여과정확도를비교, 측정하였다. 실험결과, 링크구조를포함한블로그내부의모든관계를고려함으로써기존의시스템보다스플로그에대한여과성능이좋아진것을볼수있었다. 또한사용자의행동을기반으로가중치부여방식을달리함으로써정상블로그에대한점수차이를크게하여정상블로그에대한랭킹정확도를높였다. 마지막으로, 기존의시스템들과달리블로그자체에대해점수를부여하여이를내부포스트의랭킹점수에반영하여낮은점수를가진정상블로그의점수를높이고, 높은점수를가진스플로그의점수를낮추어여과정확도를더욱향상시켰다. ii
ABSTRACT With the rapidly growth of bloggers, search engines for blog, which user can find blogs relevant to their needs, appeared. Although many users use blogs with posting various topics, splog(spam+blog) is also increased. In the past, splog has many words of spam. Recently, however, splog has normal word or popular issue and attract bloggers that induce them to click advertisements attached at blog. Because most of existing research to detect splogs based on contents of splogs, their accuracy shows very low performance about new forms of splogs. Therefore, new methods for filtering splog are needed. In this research, we propose a splog filtering algorithm using analysis of blog structures. We analyze nteractions of blogs and structures of blogs, such as blogroll, hyperlink, comment, and trackback, to apply trustworthy of blogs and posts to ranking algorithm. It affects to blogs and posts that interact with the blog or post. And a blog affect to its posts. We adapt weighted HITS algorithm as ranking algorithm and measure filtering performance of a proposed system. We give weights of the algorithm based on user actions of blogs for improving accuracy. To this end, we measure user s visiting time at blog or post, and subsequently apply it to weights. In experiments, we compared filtering performances of a proposed method with previous iii
research. Experiment result showed that a proposed method obtains improved performance compared with existing method. iv
목 차 요 약...i ABSTRACT...iii 목 차...v 제 1 장서론...1 제 2 장관련연구...3 2.1. HITS... 3 2.2. Weighted HITS... 5 2.3. 내부링크를이용한 hub value 기반스플로그여과... 6 제 3 장구조분석을이용한스플로그여과...8 3.1. 시스템구조도... 9 3.2. 블로그의구조적특성기반의 WHITS... 10 3.3. 사용자행동기반가중치부여... 13 3.4. 블로그점수를반영한포스트랭킹... 16 제 4 장실험및결과...18 4.1. 실험평가방법및데이터집합... 18 v
4.2. 실험결과및평가... 19 4.2.1. 랭킹점수분포도... 19 4.2.2. 여과성능비교... 21 4.2.3. 랭킹결과에블로그점수반영... 23 제 5 장결론및향후연구...26 참고문헌...28 vi
제 1 장서론 스플로그 (Splog) 란스팸과블로그의합성어로, 광고나음란성과같은불필요한정보를담고있는블로그를뜻한다 [1]. 최근이러한스플로그들은스팸덱싱 (Spamdexing) 문제로불거지고있는데, 스팸덱싱 ( 스팸 + 인덱싱 ) 이란검색엔진의색인프로그램을속여스플로그가상위권에들어가도록하는문제이다 [1]. 스플로그는검색엔진을통해블로그방문을유도한후음란 도박 광고사이트로자동연결시킨다. 그리고블로그, 위키, 게시판등에자동으로스팸덧글및트랙백을남기며, 방문자가많은검색웹페이지를크롤링 (crawling) 해방문자를유도하여광고수익을창출한다. 국내에스플로그가최근화두로떠오르게된것은, 대형포털블로그중한업체의서버접속장애현상때문이다. 이서버접속장애는스패머에의해스크랩된글이검색결과에노출되어급격한트래픽을유발시켜일어났다 [19]. 또한여러유명블로그검색엔진에서광고글이검색상위에랭크되는등, 검색결과의정확도가저하되어신뢰도가하락되는현상이발생하고있다 [20]. 이러한스플로그가확산된원인은블로그산업이발달함에따라검색엔진이블로그검색을강화해포털검색사용자들이점차블로그로유입되고있기때문이다. 따라서기존의메일과웹페이지를공격하던스패머들이블로그공간으로점차영역을확장해가고있다. 또한구글애드센스가대중화됨에따라그수가급격히증가하여블로그가수익창출의수단으로전락하게된것도하나의원인이라할수있다 [21]. 이러한여러목적을위해스패머들은블로그공간에서자신의블로그를최대한노출시키려노력한다. 그방법으로남의글을무단도용해 1
스크랩하거나, 실시간인기글이나검색어에관한뉴스를복사하거나, 또는키워드만으로포스트내용을채우는것등이있다. 수동으로직접포스트를작성하거나스크랩하던기존의방식과는달리, 최근에는최신인기키워드를검색하여상위에랭크되는포스트를자동으로복사하는프로그램을통해자신의블로그에포스팅한다. 따라서스팸포스트가급격히증가하여더욱심각한문제가발생하고있는데, 이는블로그내용의저작권문제, 블로그가수익창출수단으로의전락함에따른블로그공간오염, 네트워크트래픽증가, 검색결과의질저하등의문제점이되겠다. 이러한문제점을해결하기위해많은연구들이제안되었으나, 내용기반접근을통해여과하는기존의방법들은스플로그의특성에맞지않아새로운여과방법이필요하게되었다. 따라서본논문에서는내용기반의접근보다는블로그간의관계에대한구조적접근을통해스플로그를여과하여, 스플로그가검색엔진에노출되는것을방지하는시스템을제안하고자한다. 본논문의구성은다음과같다. 먼저 2장에서는기존에연구되어온스플로그여과방법들과, 제안된방법의기반이된랭킹알고리즘및비교대상이되는여과방법에대하여소개할것이다. 3장에서는제안하는시스템의기본아이디어와구조및방식에관해논의할것이고, 이에대한실험을 4장에서다룰것이다. 마지막으로, 실험을통해얻어진결론을 5장에나타낼것이다. 2
제 2 장 관련연구 스플로그를여과하는기존의연구로포스트의내용, 시간, 링크에따른포스트간유사성에따른여과방법 [2, 3], 내용과 URL을토큰화하여모델을구축하는방법 [4, 5], Support Vector Machine을적용한방법 [6] 이존재한다. 또, 네트워크상에서의협업적여과방법 [7, 8], 단어들의길이를측정하여여과하는방법 [9] 등이연구되어왔다. 2.3절에서설명할기존의연구는블로그와웹페이지간의내부링크에 HITS 알고리즘을적용하여스플로그를여과함으로써, 내용을기반으로한다른연구들에비해여과성능이높아이를본논문의실험에서비교하고자한다. 이장에서는본논문이제안하는시스템을적용하여랭킹하는알고리즘인 HITS 알고리즘과, 여기에가중치를부여하여정확도를높인 WHITS 알고리즘에대해소개한다. 2.1. HITS 링크분석알고리즘중의하나인 HITS(Hypertext-Induced Topic Selection) 알고리즘은웹페이지간의링크구조를통해정보를추출하여검색엔진에서페이지를랭킹한다 [10]. Kleinberg가제안한 HITS 알고리즘은웹페이지간의관계를기반으로하므로페이지간의신뢰도를정확히줄수있다는장점이있다. 각페이지는 authority value와 hub value라는두개의값을이용해점수를부여한다. Authority value는페이지내용자체에대한점수이며, 해당페이지로링크하는페이지의 hub value의합을통해계산한다. 이 3
값은최종랭킹점수가되며얼마나신뢰할수있는페이지인가를 나타내는수치이다. Hub value 는다른페이지로의링크에대한수치 로, 얼마나좋은페이지로많이링크하는지를나타낸다. 이는해당 페이지가링크하는페이지의 authority value 의합을통해계산한다. 즉, 수식은다음과같다. Authority value 크를갖는모든페이지 j 의 hub value value value a 는현재페이지로의링 i h j 의합으로나타내고, hub hi 는현재페이지가링크하는모든페이지 k의 authority ak 의합으로나타낸다. a i = å h j, h = i åa k (1) j k 초기디폴트값을 1로할당한후, 이연관된두개의점수를지속적으로갱신함으로써 hub value를포함한 authority value에따라랭킹된페이지의결과를보일수있다. HITS 알고리즘은그래프구조를기반으로하며, 그래프 G = (V, E) 의식을통해나타낼수있다. 그래프 (G) 에서 V는정점 (Vertex) 으로각페이지를나타내며 E 는간선 (Edge) 으로각페이지간의링크를나타낸다. 따라서 hub value가높은페이지는높은 authority value를가진페이지로많이링크하며, authority value가높은페이지는높은 hub value를가진페이지가많이링크한다. 초기의두 value들은모두 1로초기화되며두 value의계산식을교대로적용함으로써수렴된 authority value 와 hub value를구할수있다. 이렇게구해진값들은정규화과정을거친다. PageRank[11], TrustRank[12], SpamRank[13] 등다른링크분석알고리즘에비해 HITS 알고리즘의랭킹정확도가높은원인 4
은다음과같다. HITS 알고리즘은인덱싱시간에미리점수를계산하는다른랭킹알고리즘과달리쿼리요청즉시실행하여랭킹점수를계산한다. 또한, 다른알고리즘이한개의점수만을갖는것에비해, 각페이지마다 authority value와 hub value의두점수를가짐으로써페이지간의신뢰도를보다정확하게측정할수있다. 마지막으로, 모든페이지를계산하는다른랭킹알고리즘과달리 HITS 알고리즘은쿼리와관련된페이지에대해서만랭킹순위를계산하므로수행속도를개선시킬수있다. 하지만 Kleinberg의 HITS 알고리즘은링크의 in-degree와 outdegree에만의존하여페이지를랭크하므로최초의 seed set에따라결과가달라진다는문제점이있다. 즉, 링크된페이지가스팸페이지이든아니든, 모든페이지에같은가중치를부여하므로정확도가떨어진다. 따라서호스트간에 mutually reinforcing relationship이나타날수있고 topic drift를반영하는것이어렵다. Bharat은이두가지경우의문제점을인식, 각페이지에가중치를추가함으로써해결하고자했다 [14]. 2.2. Weighted HITS WHITS(Weighted Hypertext-Induced Topic Selection) 알고리즘은기존의 HITS 알고리즘에가중치를추가한것으로, HITS 알고리즘기반방법중의하나이다 [15]. BHITS(Bharat's HITS) 가각페이지의 value 계산에가중치를주었지만이방식이매우단순하여, WHITS에서는보다정확한점수를구하기위해가중치주는방법을달리하였다. 기존의전형적인 Kleinberg의 HITS 알고리즘을기본으로하되, authority value와 hub value의계산에각페이지의가중 5
치를추가했다. 가중치를추가한수식은다음과같다. a i = å j w a h j j, hi = å k w a hk k (2) 처음에 w 는모두 1로초기화하며, w a 는다음과같이부여한 j hk 다. 루트페이지 (root page) 의 w a 는 4로, 나머지페이지의 w j a j 1 로초기화시킨다. 루트페이지란, 페이지로의 in-degree 가매우 적고페이지에서나가는 out-degree 가매우큰페이지를뜻한다. 초기화된가중치는 authority 와 hub value 가변경되면새로운루트 페이지가생기는지의여부에따라변화된다. 는 2.3. 내부링크를이용한 hub value 기반스플로그여과 Y. R. Lin은스플로그를찾아내기위해블로그와웹페이지의관계에가장전형적인 Kleinberg의 HITS 알고리즘을사용했다 [16]. 즉, 블로그에서웹페이지로의하이퍼링크에 HITS 알고리즘의공식을적용하였다. 각웹페이지는 authority value를, 각블로그는 hub value를가지며이 hub value는블로그가얼마나신뢰할수있는웹페이지로링크하는가의정도를나타낸다. 즉, 스플로그는스팸웹사이트로의링크를포함한다는가정하에, 검색엔진에서의랭킹은각블로그의 hub value의크기로결정된다. 즉, 블로그가스팸웹페이지로링크하는경우그블로그는스플로그로분류되어검색결과하위에랭크된다. 이방법은블로그의링크구조를사용했지만기존웹페이지와블로그사이의단순한링크만으로스플로그와블로그를구분하는방법에한정된다. 최근스플로그는링크를통해다른스팸웹사이트로연결하기보다는블로그자체에광고를포함하 6
고있는경우가대부분이므로 hub value에기반한방법은현재스플로그의특성에맞지않아정확도를떨어뜨리는원인이된다. 또한, 최근스플로그는내부링크가스팸웹사이트로연결될가능성이매우적다. 따라서최신특성, 즉블로그내부구조를기반으로스플로그를걸러내는새로운방법이필요하게되었다. [ 그림 1] 내부링크를이용한 hub value 기반시스템의구조도 [ 그림 1] 은내부링크를이용한 hub value 기반시스템의동작을나타낸다. 정상적인블로그는신뢰할수있는블로그로많은링크를가지며, 스플로그는스팸웹사이트로많이링크하므로웹사이트의 authority value를이용해계산한블로그의 hub value를최종랭킹점수로결정한다. 7
제 3 장 구조분석을이용한스플로그여과 기존스플로그의전형적인유형인펌블로그는다른사람의글을그대로스크랩한것으로, Dedup 알고리즘을적용하여스플로그의랭킹을낮추어해결이가능하다. Dedup 알고리즘은다른블로그에서스크랩한글이라면, 먼저게시한글을원본이라하여펌블로그를노출하지않는방식으로국내의주요블로그서비스업체들이사용하고있다. 그러나이러한방식은글을복사하여포스트를새로작성한경우에는적용되지않으므로새로운접근방법이필요하다. 대부분의스플로그여과방법들은내용기반접근을사용하지만, 최근스플로그는링크를밖으로보내지않고, 내용은정상적이거나혹은인기있는글을게시하는동시에블로그자체에광고를포함한다. 따라서더이상내용기반접근을통해서는정확한여과효과를기대할수없다. 이러한문제를보완하기위해본논문에서는내용기반이아닌관계구조기반접근을통해스플로그를여과한다. 또한, 각포스트에대한사용자의행동을고려해, 각사용자의관심도를포스트의점수계산에반영해랭킹정확도를높이고자한다. 본장에서는블로그자체의구조적특성에기반하여스플로그를식별해내는방법을제안하고블로그검색엔진에서스플로그가검색결과의상위에랭크되는것을방지하는방법에대해기술한다. 각블로그와그내부의포스트들은각각 authority value와 hub value 를가지며, 각블로그의점수와내부포스트의점수는서로영향을주어최종랭킹점수에두점수를모두반영한다. 검색결과를나타내기위한랭킹점수는포스트의 authority value에블로그의 8
authority value를일정비율포함하여계산함으로써보다정확한랭킹결과를나타내고자한다. Authority value와 hub value를구하기위해 WHITS 알고리즘을적용하였으며, 가중치는사용자의행동에기반하여보다정교한가중치의차이를부여하고자한다. 3.1. 시스템구조도 H H H A A A BlogRoll Authority value Hub value Post A H Trackback Comment Category Post A H Hyperlink Post Comment H H A Blog Trackback H A Authority Value H Hub Value [ 그림 2] 시스템구조도 [ 그림 2] 는블로그와포스트, 웹페이지간의링크관계에의한구조 적특성에따라각블로그와포스트의 authority value, hub value 의 9
계산에사용되는요소들을그림으로나타낸것이다. 블로그의 authority value는이블로그를블로그롤 (blogroll) 에추가한블로그의 hub value를통해계산하고, 블로그의 hub value는이블로그가블로그롤에추가한블로그의 authority value들과, 이블로그가덧글 (comment) 이나트랙백 (trackback) 을추가한포스트의 authority value들의합으로계산한다. 또한, 포스트의 authority value는이포스트로의링크를포함하는포스트 / 웹페이지의 hub value들과, 이포스트에덧글이나트랙백을추가한블로그의 hub value들의합으로구한다. 포스트의 hub value는이포스트가링크하는블로그 / 포스트 / 웹페이지의 authority value들의합으로계산할수있다. 3.2. 블로그의구조적특성기반의 WHITS 정보간의관계만을표현하는일반웹페이지와달리, 블로그는정보간의관계와사람사이의관계를모두고려한형식을갖는다. 즉, 블로그와블로그, 블로그와포스트, 포스트와포스트, 그밖의웹페이지와의상호작용까지모두포함한다. 구체적종류는 [ 표 1] 과같다. [ 표 1] 블로그내부상호작용 블로그롤 (BlogRoll) 하이퍼링크 (HyperLink) 덧글 (Comment) 블로그 -> 블로그포스트 -> 웹페이지웹페이지 -> 포스트웹페이지 -> 블로그포스트 -> 블로그블로그 -> 포스트 10
트랙백 (TrackBack) 블로그 -> 포스트 블로그롤은신뢰할수있는블로그를자신의블로그내에추가시킨것으로, 블로그와블로그간의관계를나타낸다. 하이퍼링크는포스트나웹페이지의글내부에작성되는링크로, 포스트 / 웹페이지에서포스트 / 웹페이지 / 블로그로의관계를나타낸다. 덧글과트랙백은블로그에서다른블로그의포스트에남기는것으로, 블로그에서포스트로의관계를나타낸다. 이러한관계를바탕으로각블로그와포스트들에점수를부여해, 이를기반으로랭킹알고리즘을적용하여검색결과의정확도를높이고자한다. 블로그와포스트에영향을미치는요소는 [ 그림 3] 과같이나타낼수있다. 여기서 AV는 authority value를, HV는 hub value를나타낸다. (a) 에서각블로그는다른블로그로부터의블로그롤을가질수있고다른블로그로의블로그롤을추가할수있으며또한, 다른포스트에덧글이나트랙백을남길수있다. 이관계들을바탕으로각블로그에대한 authority value와 hub value들을계산한다. 포스트의 authority value와 hub value 역시 (b) 와같이다른블로그 / 포스트 / 웹페이지와의관계에기반하여계산할수있다. 각포스트는다른포스트나웹페이지로링크할수있고, 다른블로그로부터의덧글이나트랙백을받을수있다. 또한, 다른포스트나웹페이지로부터의링크를포함할수있고, 이모든관계들을바탕으로 authority value와 hub value를 [ 그림 3] 과같이계산할수있다. 11
(a) 블로그의 authority, hub value (b) 포스트의 authority, hub value [ 그림 3] 블로그와포스트의 authority, hub value 이렇게블로그공간구조를검색결과랭킹점수에반영함으로써 블로그및포스트의순위를나타내도록한다. 여기에서 hub value 는 12
페이지간의관계를나타낼뿐, 실제랭킹결과로의적용에는 authority value만이관여한다. 즉, 제안된시스템은블로그및포스트의 authority value를기반으로한다. 이는페이지간의관계에바탕을두기때문에신뢰도를정확히줄수있다. 제안하는방법의핵심은다음과같다. 블로그와그내부포스트들에대한다른블로그들의피드백에따라점수를조정하며, 이때받을수있는피드백은 positive 피드백과 negative 피드백으로구성된다. Positive 피드백은높은점수를가진블로그 / 포스트 / 웹페이지로부터의피드백으로, 피드백을받은블로그나포스트의점수를증가시킨다. 반대로, 스패머로의심되는낮은점수를가진블로그 / 포스트 / 웹페이지로부터의피드백을받으면낮은점수를갖도록한다. 3.3. 사용자행동기반가중치부여블로그간의관계에기반해랭킹점수를부여하기위해랭킹알고리즘인 WHITS 알고리즘을사용한다 [15]. 하지만 HITS 알고리즘에가중치를부여한 WHITS 알고리즘은가중치부여방식이매우단순하여랭킹정확도가떨어지는단점이있다. 따라서본논문에서는가중치부여방식을보다정교화하여랭킹성능을높이고자한다. 하나의블로그와포스트에대한각사용자의관심정도는모두다르므로, 관심정도에따라사용자의행동역시각각다르게나타날수있다. 따라서웹로그파일을이용하여사용자들의개인정보를활용해그들의각기다른행동을포스트점수부여에적용한다. 관심도를가장크게나타내는요소로글을읽는시간 (viewing time) 을들수있다. 사용자가포스트를얼마나빨리읽고, 얼마나오랜 13
시간머무는지, 혹은다른포스트를클릭하여블로그내에얼마나 오래머무는지를파악할수있다. 블로그나포스트에사용자가머 무는시간은각블로그나포스트에대한사용자의관심정도를반 영한다고볼수있으므로이를가중치부여식에적용하고자한다. 웹페이지에사용자가머무는시간을통해사용자의관심도를결 정했던기존연구의실험에서사용자는믿을수있는페이지에최 소 1 초이상머무는것으로나타났다 [17]. 따라서가중치계산은 다음과같이적용할수있다. 기존의가중치에사용자의관심에따 른가중치를더하는방식으로, 로그 (logarithm) 함수를사용하여시 간이 1 초를넘기면사용자가그글에관심이있다가정하고양수 값인가중치를갖도록한다. 또한, 1 초미만일경우사용자는그글 을스팸으로인식했다고할수있으므로음수값을가중치로갖게 된다. 이러한개인별가중치를최종가중치에합산하여정규화하는 과정을거치도록했다. 시간은초단위로측정하되소수점으로마이 크로초단위까지포함하도록한다. 사용자개인별가중치 하는공식은다음과같이기존의가중치 대한가중치를더해계산한다. ' wi 를구 wi 에현재사용자행동에 ' i w = w + log( time) * w (3) i i 또한, 글을읽는시간은사용자의관심이나행동양식에따라다르기때문에시간을개인화할필요성이있다. 즉, 같은글을읽을때어떤사용자는대충훑어보는반면다른사용자는정독하는경우가있을수있다. 따라서이러한개인차를반영하고자본논문에서는각사용자가글을읽는시간을개인별로달리하여이를위의식에적용하고자한다. 각사용자가글을읽는시간이얼마나큰가 14
중치를갖는지즉, 의미의정도를따져개인화된시간을측정한다 [18]. 사용자가글을읽는평균시간을측정하여이를가중치를부여한시간이라한다. 이를적용하여, 개인화된시간은실제측정된시간을가중치를부여한시간으로나누어계산한다. 가중치를부여한시간 WT(weighted time) 은한사용자가방문한모든페이지의가중치 (weight) 와그방문시간 (time) 의곱을페이지의개수 (N) 로나누어구한다. 즉, 시간에가중치를부여한계산식은식 (4) 와같이나타낼수있다. WT = N å i = 1 ( weight N i * time ) i (4) 개인화된시간을구하기위해실제측정된시간 t 를식 (4) 의 WT 로나누어, 이를 (3) 에적용한최종개인별가중치부여공식은 식 (5) 와같다. ' t w i = wi + log( ) * wi (5) WT 이렇게구해진가중치를반영하여블로그 / 포스트 i 에대한 authority value a i 와 hub value h i 를구하는공식은식 (6) 과같다. 15
a h i i = = + + å j å å k å k j w w a w h w h a k j HV ( blogroll ) + HV ( trackback) AV ( blogroll) + k j AV ( hyperlink ) å å k j w k a j HV ( hyperlink ) + w AV ( comment) + å k å j w h w k a j HV ( comment) AV ( trackback) (6) 여기에서 w a 와 w h 는 WHITS 알고리즘에사용되는가중치를나타낸다. Authority value는 i가블로그일경우, i를블로그롤에등록한블로그 j의 hub value들의합으로나타낼수있으며, i가포스트일경우 i로의내부링크를추가한포스트 / 블로그 / 웹페이지 j의 hub value들과 i에덧글과트랙백을추가한블로그 j의 hub value들의합으로나타낼수있다. 블로그 i에대한 hub value의경우, i의블로그롤에추가한블로그 j의 authority value들과 i가덧글, 트랙백을추가한포스트 j의 authority value들의합으로구할수있다. 또한포스트 i에대한 hub value는포스트 i가내부링크를추가한포스트 / 웹페이지 j의 hub value들의합으로계산한다. 3.4. 블로그점수를반영한포스트랭킹 지금까지하나의블로그및포스트와다른블로그및포스트와의관계를통해점수를부여했다면, 앞으로는하나의블로그와그내부의포스트간의관계를분석하고자한다. 이역시구조적접근을통해이루어진다. 어떤블로그에새로운포스트가등록되면디폴트점수가부여된다. 이후포스트에대한어떤상호작용이발생하면그점수는변하게되나, 만일어떤상호작용도일어나지않고링크조차 16
존재하지않는다면이포스트는계속낮은점수를유지해, 포스트의스팸 / 논스팸여부에관계없이검색결과의하위에랭크된다. 이러한문제를해결하기위해포스트와, 그포스트가속한블로그의관계를반영했다. 즉, 하나의블로그와그내부포스트의점수들은서로유기적으로연결되어블로그점수가변동되면그에따라포스트의점수도바뀔수있고, 반대로포스트의점수가변동되면블로그의점수역시바뀔수있다. 이를 authority value에직접반영하는것이아닌, 랭킹알고리즘적용시랭킹점수로반영하고자한다. 즉, 최종랭킹점수에포스트점수와해당블로그점수의일정비율을각각반영해스팸이아닌포스트가스팸으로분류되는것을방지하는동시에블로그의신뢰도를내부포스트에반영해여과성능을향상시키고자했다. 따라서새로등록된포스트의랭킹점수는디폴트점수가아닌, 해당블로그의점수를일정비율반영한값이된다. 블로그의점수반영비율을 p라할때최종랭킹을위한점수는다음식 (7) 과같이표현할수있다. Ranking _ Score = AV ( blog) * p + AV ( post) * (1 - p) (7) 랭킹점수 Ranking_Score는블로그의 authority value AV(blog) 에그반영비율 p를곱한값과, 포스트의 authority value AV(post) 에포스트점수의반영비율 1-p를곱한값의합으로계산한다. 실험에서, 0부터 1까지의범위를가지는블로그의반영비율 p는 0.1, 0.3, 0.5, 0.7, 0.9로변경하며적용하였고, 따라서포스트점수의반영비율은 0.9, 0.7, 0.5, 0.3, 0.1의순서로적용해계산하였다. 17
제 4 장 실험및결과 제안된방법이기존연구에비해여과성능이얼마나향상되었는지를평가하기위해 2.3절에소개한 Y. R. Lin의내부링크를이용한 hub value 기반스플로그여과방법 [16] 과비교하여실험을진행하였다. 4.1. 실험평가방법및데이터집합성능평가를위한데이터집합으로는네이버, 야후, 티스토리의블로그를사용하였으며정상블로그와스플로그각각 50개를수집하였다. 각블로그에포함되는포스트는스팸포스트가 2000여개, 정상포스트가 850여개사용되었다. 데이터구성은 [ 표 2] 와같다. [ 표 2] 데이터집합의구성 블로그 포스트 정상 50 850 스팸 50 2000 제안된방법이얼마나정확하게스플로그를여과하였는지성능을평가하기위하여정확도 (Precision), 재현율 (Recall), 그리고 F1- measure 측정식을이용하였다. 식 (9) 와 (10) 의 F1-measure는재현율과정확도가반비례관계를고려하여재현율과정확도에동일한가중치를부여하는방법으로문서분류의성능평가에가장많 18
이이용되는방법이다. precision recall ( s) ( s) = = F1- measure 스플로그로분류된스플로그스플로그로분류된전체 스플로그로분류된스플로그전체스플로그 2 * precision( s) * recall ( s) = precision + recall ( s) ( s) ( s) (9) precision recall ( b) ( b) = = F1- measure 정상블로그로분류된정상블로그정상블로그로분류된전체 정상블로그로분류된정상블로그전체정상블로그 2* precision( b) * recall( b) ( b) = precision + recall ( b) ( b) (10) 4.2. 실험결과및평가 4.2.1. 랭킹점수분포도랭킹점수가증가함에따른각점수에해당하는포스트의개수를측정하였다. 스플로그와정상블로그, 두가지에대한그래프를그려비교하였다. 즉, 낮은랭킹점수일수록스플로그에해당하는개수가많고, 높은점수일수록정상블로그에해당하는개수가많은것이보다나은성능을제공한다고볼수있다. 또한, 두개의그래프가만나는점보다더낮은점수는스플로그로, 더높은점수는정상블로그로판단하는기준을마련할수있다. [ 그림 4] 와 [ 그림 5] 는내부링크이용한 hub value 기반여과방식과블로그구조이용한 authority value 기반여과방식의랭킹점수분포도를나타낸 19
다. 120 100 80-40 -60-80 스팸포스트개수에따른랭킹점수분포도 60 랭 40 킹 20 점 0 수 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0-20 내부링크이용 hub 기반 스팸포스트개수 블로그구조이용 authority 기반 [ 그림 4] 스팸포스트개수에따른랭킹점수분포도비교 12000 정상포스트개수에따른랭킹점수분포도 10000 랭킹 점수 8000 6000 4000 2000 0 1 10 100 1000-2000 내부링크이용 hub 기반 정상포스트개수 블로그구조이용 authority 기반 [ 그림 5] 정상포스트개수에따른랭킹점수분포도비교 20
[ 그림 4] 에서 Y. R. Lin의시스템인내부링크를이용한 hub value 기반여과방식은대부분의스팸포스트가 0에가까운값을갖는다. 또한 [ 그림 5] 에서정상포스트의 authority value 역시 0 에가까운값을갖는다. 즉, 내부링크를이용한 hub value 기반의여과방식은정상포스트와스팸포스트를잘구분하지못하는결과를보인다. 이는블로그와웹페이지간의관계에만기반한시스템의내용에보다정확한비교를위해덧글및트랙백을추가하여실험한것으로, 본래의 Y. R. Lin의시스템은 hub value 값이더낮아져그성능이본실험에서보다좋지못할것으로보인다. 반면, 본논문에서제안한블로그구조를이용한 authority 기반여과방식은 [ 그림 4] 와 [ 그림 5] 에서보듯이각포스트가매우다양한점수를가진다. 스팸포스트의경우음수값이많고, 높은점수를가진포스트가비교적적은것을볼수있다. 정상포스트역시음수값을갖는포스트가거의없는것에비해, 높은점수를가진포스트가기존의시스템에비해많아진것을볼수있었다. 4.2.2. 여과성능비교 [ 그림 6] 과 [ 그림 7] 는내부링크이용한 hub value 기반여과방식과본논문에서제안한블로그구조이용한 authority value 기반여과방식을이용했을때, 각각의정확도 (Precision), 재현율 (Recall), 그리고 F1-measure 값을비교한것이다. [ 그림 6] 의정확도측정에서스플로그의정확도, 재현율및 F1- measure는매우높게측정되었으나, [ 그림 7] 과같이대부분의정상포스트가스팸포스트로분류되었다. 따라서스플로그의정확도, 재현율및 F1-measure로는그정확도를비교할수없어, 블로그에대해측정한결과를비교해야한다. 21
120% 100% 80% 60% 40% 20% 0% Precis ion(s ) Recall(s ) F1-meas ure(s ) 내부링크이용 hub 기반 블로그구조이용 authority 기반 [ 그림 6] 스플로그여과성능비교 120% 100% 80% 60% 40% 20% 0% Precis ion(b) Recall(b) F1-meas ure(b) 내부링크이용 hub 기반 블로그구조이용 authority 기반 [ 그림 7] 정상블로그여과성능비교 22
[ 그림 6] 에비해 Y. R. Lin 시스템은 [ 그림 7] 과같이재현율과 F1-measure가매우낮게측정되었다. 본논문에서제안한시스템의재현율및 F1-measure는그에비해매우향상된것을볼수있다. 이는사용자의행동에기반한가중치를부여해여과성능을보다향상시켰기때문인것으로보인다. 4.2.3. 랭킹결과에블로그점수반영 120% 100% 80% 60% 40% 20% 0% Precis ion(s ) Recall(s ) F1-measure(s ) 블로그점수 0% 블로그점수 10% [ 그림 8] 블로그점수를 0%, 10% 반영한스플로그여과성능비교 3.4절에서언급하였듯이, 스팸이아닌포스트가스팸포스트로분류되는것을막기위해최종랭킹점수결정에포스트가속하는블로그의점수를반영한다. 블로그와포스트점수의일정비율을각각부여하도록했는데, 그비율을결정하기위해블로그점수를 10%, 30%, 50%, 70%, 90% 씩반영하며여과정확도를측정했다. 그중 10% 를반영한결과와반영하지않은여과정확도의비교결과를 23
[ 그림 8] 과 [ 그림 9] 에나타냈다. 120% 100% 80% 60% 40% 20% 0% Precis ion(b) Recall(b) F1-meas ure(b) 블로그점수 0% 블로그점수 10% [ 그림 9] 블로그점수를 0%, 10% 반영한정상블로그여과성능비교 [ 그림 8] 과 [ 그림 9] 의그래프에서블로그점수의반영비율에따른변화를볼수있다. 블로그점수의일정비율을최종랭킹점수에반영한것은포스트의점수만으로랭킹한것에비해스플로그여과정확도는저하되나, 블로그여과정확도는향상된것을볼수있다. 이는어떤상호작용없이디폴트점수만을가지던정상포스트에디폴트점수가아닌블로그의점수를반영하여, 랭킹점수를보다높임으로써스팸포스트로분류되지않도록하기때문이다. 그러나블로그점수의반영비율을높일수록스플로그여과성능은같지만, 포스트의개수에따른점수가평이해지는현상이나타난다. 이는정상포스트간의차별성없이점수가균일해져, 정상블로그간의점수차이가작아져부정확한랭킹결과로나타날수있다. 즉, 24
정상포스트간의차별성이저하되어정상블로그의랭킹결과의 성능이낮아질수있다. 따라서이를얼마나적용해야할지를판단 하여적절히반영해야할필요가있다. 25
제 5 장 결론및향후연구 본논문은블로그의구조적특성과사용자행동을기반으로스플로그를여과하는방법을제안함으로써여과정확도를높여검색엔진의신뢰도를향상시키는것을목적으로하였다. 스플로그는블로그롤 (blogroll), 덧글 (comment) 및트랙백 (trackback) 을갖지않기때문에 authority value가대부분음수이다. 또한, 스플로그의 hub value 값은클수있지만랭킹점수인 authority value엔영향을미치지않으므로, Y. R. Lin의시스템과달리아무리많은링크를가지고있더라도상위에랭크되는것을막을수있다. 본논문에서제안한블로그구조를이용한 authority 기반여과방식은모든포스트들이다양한점수를가짐으로써정상블로그간의랭킹점수차를크게하는한편, 사용자의글을읽는개인화된시간을반영해스팸포스트에대해음수값을부여했다. 따라서스플로그에대한여과성능이기존의시스템에비해향상된것을볼수있었다. 정상포스트와스팸포스트사이의점수차이를크게하여정상포스트에대한랭킹정확도역시높일수있었다. 또한포스트뿐아니라블로그에대해서도점수를부여하여이를포스트의최종랭킹점수에반영함으로써정상포스트의점수를높이고스팸포스트의점수를낮추어여과성능을더욱향상시켰다. 실험결과에서스플로그의 authority value와 hub value는낮은값을가진다. 또한, 아무활동도하지않는블로그의점수역시대부분낮은값을가진다. 아무포스트도없는정상블로그는검색결과에나타나지않으므로그점수가스플로그와같은음수값을가 26
져도관계없다. 그러나낮은점수를가진정상블로그에새로운포스트가작성되었을경우, 그포스트에어떠한상호작용도존재하지않는다면, 그포스트가좋은포스트임에도불구하고랭킹점수가계속낮은점수로유지되는문제가발생한다. 이러한현상을해결하기위한새로운관계의형성및점수계산방식의도입은향후과제를통해해결하고자한다. 또한, 가중치를부여하는방법에있어더욱다양한사용자의행동을반영할필요가있다. 검색결과에서사용자의블로그클릭여부, 재방문빈도, 방문이후다른블로그를클릭하는가의여부와같은다양한행동이있을수있다. 이를분석하여가중치부여방식을보다정교화해스플로그여과정확도를높이고, 정상블로그간의신뢰도에따른점수를차별화하여랭킹성능을향상시키는것역시향후과제로해결해야한다. 27
참고문헌 [1] Wikipedia, http://en.wikipedia.org/wiki/splog [2] P. Kolari, T. Finin, A. Java, A. Joshi, J. Martineau, J. Mayfield, Blog track open task : spam blog classification, American Association for Artificial Intelligence, 2006 [3] G. Mishne, D. Carmel, R. Lempel, Blocking blog spam with language model disagreement, WWW2005, 2005 [4] P. Kolari, A. Java, T. Finin, T. Oates, A. Joshi, Detecting spam blogs: A machine learning approach, AAAI, 2006 [5] F. Salvetti, N. Nicolov, Weblog classification for fast splog filtering: A URL language model segmentation approach, Human Language Technology Conference of the North American Cahpter of the ACL, 2006 [6] P. Kolari, A. Java, T. Finin, T. Oates, A. Joshi, Detecting spam blogs: A machine learning approach, AAAI, 2006 [7] S. Han, Y. Ahn, Collaborative blog spam filtering using adaptive percolation search, WWW2006, 2006 [8] P. Kolari, T. Finin, A. Java, A. Joshi, Towards spam detection at ping servers, ICWSM, 2007 [9] K. Narisawa, Y. Yamada, D. Ikeda, M. Takeda, Detecting blog spams using the vocabulary size of all substrings in their copies, WWE2006, 2006 28
[10] Jon M. Kleinberg, Authoritative Sources in a Hyperlinked Environment, Journal of ACM, 1999 [11] Google s PageRank, http://pr.efactory.de/e-pr0.shtml, 2002 [12] Z. Gyongyi, H. G. Molina, J. Pefersen, Combating web spam with TrustRank, VLDB Conference, 2004 [13] A. A. Benczur, K. Csalogany, T. Sarlos, M. Uher, SpamRank Fully automatic link spam detection work in progress, AIRWeb, 2005 [14] K. Bharat, M. R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, International ACM SIGIR Conference on Research and Development in Information Retrieval, 1998 [15] L. Li, Y. Shang, W. Zhang, Improvement of HITS-based Algorithms on Web Documents, International World Wide Web Conference, 2002 [16] Y. R. Lin, H. Sundaram, Y. Chi, J. Tatemura, B. Tseng, SPLOG Detection Using Content, Time and Link Structures, IEEE International Conference, 2007 [17] S. Burklen, P. J. Marron, S. Fritsch, K. Rothermel, User Centric Walk: An Integrated Approach for Modeling the Browsing Behavior of Users on the Web, ANSS, 2005 [18] K. Menon, C. H. Dagli, Web Personalization using Neuro- 29
Fuzzy Clustering Algorithms, NAFIPS, 2003 [19] 아이뉴스, http://www.inews24.com/php/news_view.php?g_ serial=271107&g_menu=020900, 2007/07/11 [20] 스타베이스 Trand Watch, http://www.strabase.com, 2007/09/04 [21] 매일신문, http://www.imaeil.com/sub_news/sub_news_ view.php?news_id=33407&yy=2007, 2007/07/30 30