Attachment '07_scaping.html'

Download

title: “SNA Data Crawling”
author: “Jeongsoo, Park”
date: “Friday, Aug 18, 2014”

Data Crawling

Data Crawling

오늘은 인터넷 상에 존재하는 웹 문서로부터 정보를 추출하는 방법을 알아보도록 하겠습니다.

웹 문서로부터 정보를 추출하기 위해서는 몇 가지 단계가 필요합니다.

수집 (retrieval): 웹으로부터 raw 데이터를 수집합니다. seed 페이지로부터 시작해서 링크를 따라 계속 페이지들을 수집합니다.
구조화 (parse): 수집된 페이지를 구조화하고, 필요한 데이터를 식별해서 골라냅니다.

수집 전략 - Snowballing

웹 문서로부터 정보를 추출하는 경우, 대부분은 전체 데이터를 한번에 가져올 수 없습니다. 그래서 snowballing (눈덩이 굴리기) 방식으로 데이터를 수집합니다.

Snowballing 방식에서는, 맨 처음 수집할 웹 페이지를 지정합니다. 그래서 그 웹 페이지에서 하이퍼링크를 수집하여, 인접하는 웹 페이지를 알아냅니다.

## Loading required package: methods

plot of chunk unnamed-chunk-3

seed에서 첫 번째 탐색을 한 직후에는, seed와 이웃 페이지 사이의 관계만 알 수 있을 뿐, 이웃들 사이의 관계(alter 간의 관계)는 알 수 없습니다.

인접하는 웹 페이지를 알아낸 후에는, 각 웹 페이지들을 방문하며 다시 그 웹 페이지에 인접한 페이지들을 알아냅니다.

plot of chunk unnamed-chunk-4

이 시점에는, seed를 기준으로 볼 때, 이웃들 사이의 관계를 비로소 알 수 있게 됩니다. 그리고 2차 이웃의 존재를 알 수 있게 됩니다. 하지만 이 시점 역시 2차 이웃들 서로간의 관계는 알 수 없습니다.

이렇게 이웃을 확장해가면서 네트워크를 만들어가는 방법이 snowballing 방식입니다.

plot of chunk unnamed-chunk-5

httr 사용하기

이제 실제로 R을 사용해서 웹 페이지를 수집하는 방법을 알아보겠습니다.

httr과 같은 패키지는 내부적으로 RCurl과 XML 패키지를 사용하여, 웹 페이지의 수집과 추출을 할 수 있도록 해줍니다.

우선 아래 명령으로 httr 패키지를 설치해줍니다.

> install.packages('httr')

그리고 현재 R 환경에 로드합니다.

> library('httr')

## Warning: package 'httr' was built under R version 3.1.1

> library('XML')

위키피디아에 있는 내용을 가져오는 것을 해보겠습니다. 아래 명령을 통해 웹 페이지의 내용을 가져올 수 있습니다.

> request <- GET('http://en.wikipedia.org', path="wiki/Social_network_analysis")
> c <- content(request)

XPath

여기서 c에는 웹 페이지의 내용이 구조화되어 들어가 있습니다. 이 구조화된 정보에서 특정한 웹 페이지 요소를 추출해내려면 httr에서는 XPath라는 것을 사용합니다.

XPath는 HTML 문서를 일종의 디렉토리 구조처럼 지칭할 수 있게 해줍니다.

<html>
    <head>
    </head>

    <body>
        <div id="main-container" style="color: black;">This is a container</div>
        <div class="article header">Webpage scrapying <a href="http://jsoup.org">Visit JSoup!</a></div>
    </body>
</html>

위와 같은 문서에서, /div라고 하면, 아래와 같은 두 내용이 반환됩니다.

        <div id="main-container" style="color: black;">This is a container</div>
        <div class="article header">Webpage scrapying <a href="http://jsoup.org">Visit JSoup!</a></div>

/div/a라고 하면, div 태그 아래에 있는 a 태그를 반환해줍니다. 결과는

<a href="http://jsoup.org">Visit JSoup!</a>

가 될 것입니다.

XPath에 대한 자세한 내용은 XPath 예제를 참고하세요.

해당 페이지의 모든 하이퍼링크 주소를 추출해내는 XPath는 //a입니다. 이것을 적용해서 모든 주소를 추출해보겠습니다.

> links <- xpathSApply(c, "//a", xmlGetAttr, "href")
> nrow(links)

## NULL

> links[1:8]

## [[1]]
## NULL
## 
## [[2]]
## [1] "#mw-navigation"
## 
## [[3]]
## [1] "#p-search"
## 
## [[4]]
## [1] "/wiki/Social_networking_service"
## 
## [[5]]
## [1] "/wiki/Social_network_(disambiguation)"
## 
## [[6]]
## [1] "/wiki/File:Kencf0618FacebookNetwork.jpg"
## 
## [[7]]
## [1] "/wiki/File:Kencf0618FacebookNetwork.jpg"
## 
## [[8]]
## [1] "/wiki/Network_diagram"

해당 페이지에는 총 `` 개의 링크가 있는 것을 알 수 있습니다.

이런 방법으로 seed 웹 페이지에 이웃한 페이지들의 하이퍼 링크 주소를 가져올 수 있습니다. SNA적으로 표현하자면, seed 웹 페이지의 egonet을 수집한 셈이 됩니다.

> library(igraph)
> egonet_raw <- cbind('/wiki/Social_network_analysis', links)
> egonet_df <- as.data.frame(egonet_raw)
> egonet <- graph.data.frame(egonet_df)
> 
> V(egonet)$size <- 2
> V(egonet)$label <- NA
> E(egonet)$arrow.size <- 0.2
> E(egonet)$color <- "#33333333"
> 
> plot(egonet)

plot of chunk unnamed-chunk-10

그리고 이렇게 얻어진 이웃들을 각각 다시 seed로 삼아서 방문하는 것을 반복하면, snowballing 방식으로 웹 페이지들의 관계들을 확대해나가며 데이터를 수집해 올 수 있습니다.

더 나가기 전에, 위의 추출 규칙을 조금 더 정교화해보겠습니다.

우선, 위키피디아에 존재하는 하이퍼링크 중에는, 위키피디아 사이트 외부로 향하는 링크도 있고, 카테고리로 향하는 링크들도 있습니다. 이런 링크들은 제거해주는 것이 페이지간의 관계를 더 잘 나타내줄 것 같습니다.

우선, 하이퍼링크들 중에서, 본문 내용에 있는 링크들만 가져오고 싶습니다. 웹 페이지 구조를 보니 본문 내용은 id 값이 mw-content-text인 div 태그 안에 담겨 있습니다.

mw-content-text

그 태그 하위에 있는 문단 중에서 모든 하이퍼 링크를 가져오려면 아래와 같이 합니다.

> links <- xpathSApply(c, '//div[@id="mw-content-text"]//p//a', xmlGetAttr, "href")
> links[1:8]

## [1] "/wiki/File:Internet_map_1024.jpg" "/wiki/Network_theory"            
## [3] "/wiki/Social_network"             "/wiki/Social_relationship"       
## [5] "/wiki/Friendship"                 "/wiki/Kinship"                   
## [7] "/wiki/Sexual_network"             "#cite_note-1"

추가로 처리해줄만한 것으로는, : 문자가 포함된 특수 링크는 제외하고, /wiki/로 시작하는, in-site 링크만을 대상으로 하는 것입니다.

> links <- xpathSApply(c, '//div[@id="mw-content-text"]//p//a[not(contains(@href,":")) and starts-with(@href, "/wiki/")]', xmlGetAttr, "href")
> 
> links[1:8]

## [1] "/wiki/Network_theory"      "/wiki/Social_network"     
## [3] "/wiki/Social_relationship" "/wiki/Friendship"         
## [5] "/wiki/Kinship"             "/wiki/Sexual_network"     
## [7] "/wiki/Network_diagram"     "/wiki/Sociology"

이제 위의 내용들을 합쳐서 하나의 함수로 만들어줍니다. 위키피디아의 도메인 경로를 입력으로 받아서 해당 페이지 본문에 존재하는 모든 하이퍼 링크를 추출하는 함수입니다.

> visit_page <- function(path) {
+   request <- GET(paste('http://en.wikipedia.org', path, sep=''))
+   c <- content(request)
+   out_links <- xpathSApply(c, '//div[@id="mw-content-text"]//p//a[not(contains(@href,":")) and starts-with(@href, "/wiki/")]', xmlGetAttr, "href")
+ 
+   title <- substring(path, 7)
+   out_link_titles <- substring(out_links, 7)
+   network <- cbind(title, out_link_titles)
+ 
+   if (length(out_link_titles) == 0) {
+       network <- list()
+   }
+ 
+   return(list("out_links"=out_links, "network"=network))
+ }

Snowballing으로 추출 대상 확대해나가기

다시 Social network analysis 페이지에 대해 실행해보면 아래와 같은 결과가 나옵니다.

> result <- visit_page('/wiki/Social_network_analysis')
> net <- result$network
> net

##       title                     out_link_titles                          
##  [1,] "Social_network_analysis" "Network_theory"                         
##  [2,] "Social_network_analysis" "Social_network"                         
##  [3,] "Social_network_analysis" "Social_relationship"                    
##  [4,] "Social_network_analysis" "Friendship"                             
##  [5,] "Social_network_analysis" "Kinship"                                
##  [6,] "Social_network_analysis" "Sexual_network"                         
##  [7,] "Social_network_analysis" "Network_diagram"                        
##  [8,] "Social_network_analysis" "Sociology"                              
##  [9,] "Social_network_analysis" "Anthropology"                           
## [10,] "Social_network_analysis" "Biology"                                
## [11,] "Social_network_analysis" "Communication_studies"                  
## [12,] "Social_network_analysis" "Economics"                              
## [13,] "Social_network_analysis" "Geography"                              
## [14,] "Social_network_analysis" "History"                                
## [15,] "Social_network_analysis" "Information_science"                    
## [16,] "Social_network_analysis" "Organizational_studies"                 
## [17,] "Social_network_analysis" "Political_science"                      
## [18,] "Social_network_analysis" "Social_psychology"                      
## [19,] "Social_network_analysis" "Development_studies"                    
## [20,] "Social_network_analysis" "Sociolinguistics"                       
## [21,] "Social_network_analysis" "Georg_Simmel"                           
## [22,] "Social_network_analysis" "%C3%89mile_Durkheim"                    
## [23,] "Social_network_analysis" "Jacob_Moreno"                           
## [24,] "Social_network_analysis" "Group_(sociology)"                      
## [25,] "Social_network_analysis" "Categorization"                         
## [26,] "Social_network_analysis" "Ronald_Burt"                            
## [27,] "Social_network_analysis" "Kathleen_Carley"                        
## [28,] "Social_network_analysis" "Mark_Granovetter"                       
## [29,] "Social_network_analysis" "David_Krackhardt"                       
## [30,] "Social_network_analysis" "Edward_Laumann"                         
## [31,] "Social_network_analysis" "Anatol_Rapoport#Social_network_analysis"
## [32,] "Social_network_analysis" "Barry_Wellman"                          
## [33,] "Social_network_analysis" "Douglas_R._White"                       
## [34,] "Social_network_analysis" "Harrison_White"                         
## [35,] "Social_network_analysis" "Money_laundering"                       
## [36,] "Social_network_analysis" "Terrorism"                              
## [37,] "Social_network_analysis" "Homophily"                              
## [38,] "Social_network_analysis" "Assortativity"                          
## [39,] "Social_network_analysis" "Closure_(psychology)"                   
## [40,] "Social_network_analysis" "Propinquity"                            
## [41,] "Social_network_analysis" "Bridge_(graph_theory)"                  
## [42,] "Social_network_analysis" "Centrality"                             
## [43,] "Social_network_analysis" "Betweenness_centrality"                 
## [44,] "Social_network_analysis" "Closeness_centrality"                   
## [45,] "Social_network_analysis" "Eigenvector_centrality"                 
## [46,] "Social_network_analysis" "Alpha_centrality"                       
## [47,] "Social_network_analysis" "Degree_centrality"                      
## [48,] "Social_network_analysis" "Dense_graph"                            
## [49,] "Social_network_analysis" "Stanley_Milgram"                        
## [50,] "Social_network_analysis" "Small_world_experiment"                 
## [51,] "Social_network_analysis" "Entrepreneur"                           
## [52,] "Social_network_analysis" "Ronald_Stuart_Burt"                     
## [53,] "Social_network_analysis" "Clique"                                 
## [54,] "Social_network_analysis" "Social_circle"                          
## [55,] "Social_network_analysis" "Structural_cohesion"                    
## [56,] "Social_network_analysis" "Clustering_coefficient"                 
## [57,] "Social_network_analysis" "Social_cohesion"                        
## [58,] "Social_network_analysis" "Structural_cohesion"                    
## [59,] "Social_network_analysis" "Social_network_analysis_software"       
## [60,] "Social_network_analysis" "Collaboration_graph"                    
## [61,] "Social_network_analysis" "Cycle_(graph_theory)"                   
## [62,] "Social_network_analysis" "Sign"                                   
## [63,] "Social_network_analysis" "Social_network_graph"                   
## [64,] "Social_network_analysis" "Net-map_toolbox"                        
## [65,] "Social_network_analysis" "Business_intelligence"                  
## [66,] "Social_network_analysis" "Counter-intelligence"                   
## [67,] "Social_network_analysis" "Law_enforcement"                        
## [68,] "Social_network_analysis" "Espionage"                              
## [69,] "Social_network_analysis" "National_Security_Agency"               
## [70,] "Social_network_analysis" "Clandestine_operation"                  
## [71,] "Social_network_analysis" "Mass_surveillance"                      
## [72,] "Social_network_analysis" "Computer_surveillance"                  
## [73,] "Social_network_analysis" "Decapitation_attack"                    
## [74,] "Social_network_analysis" "High-value_targets"                     
## [75,] "Social_network_analysis" "Call_Detail_Record"                     
## [76,] "Social_network_analysis" "Metadata"                               
## [77,] "Social_network_analysis" "September_11_Attacks"

> nrow(net)

## [1] 77

이것을, 각 이웃 링크에 대해서 다시 수행해줍니다.

> for (user_2nd_neighbor in result$out_links) {
+   result_2nd_neighbor <- visit_page(user_2nd_neighbor)
+   net <- rbind(net, result_2nd_neighbor$network)
+ }

이제 net 변수는 총 7151 개의 링크 데이터를 가지게 되었습니다. 이것을 igraph로 옮겨와보겠습니다.

우선 아래와 같이 dataframe으로 옮깁니다.

> df <- as.data.frame(net)

그리고 igraph 형식으로 변환합니다.

> library(igraph)
> network <- graph.data.frame(df)
> summary.igraph(network)

## IGRAPH DN-- 4678 7151 -- 
## attr: name (v/c)

> V(network)$size <- 2
> V(network)$label <- NA
> E(network)$arrow.size <- 0.2
> E(network)$color <- "#33333333"
> plot(network, layout=layout.fruchterman.reingold)

2단계 이웃 - 3단계 alter 포함

데이터가 너무 많으니 3단계 alter는 제거해서 보겠습니다. 3단계 alter는 아직 자신의 out-neighbor를 가지지 못했을테니, out-degree가 0인 노드를 제거하면 3단계 alter를 제거하는 것과 같을 것입니다.

아래는 2단계 이웃까지의 네트워크이면서 alter간의 관계를 포함하는 네트워크입니다.

> V(network)$out_degree <- degree(network, mode="out")
> out_degree_0_nodes <- V(network)[V(network)$out_degree == 0]
> new_network <- delete.vertices(network, out_degree_0_nodes)
> summary.igraph(new_network)

## IGRAPH DN-- 76 335 -- 
## attr: name (v/c), out_degree (v/n)

네트워크 맵을 한 번 보겠습니다.

> V(new_network)$size <- 5
> V(new_network)$label <- NA
> E(new_network)$arrow.size <- 0.2
> E(new_network)$color <- "#33333333"
> plot(new_network, layout=layout.fruchterman.reingold)

plot of chunk wiki_two_depth_neighbor_without_alter

이와 같은 방식으로 3단계, 4단계, … n단계 이웃까지 계속 확장해나가면서 네트워크를 구성해나갈 수 있습니다.

종료 조건

구글이나 야후같은 거대한 검색엔진 회사가 아닌 이상, 웹이라는 망망대해를 1년 365일 계속 헤매며 다닐 수는 없을 것입니다. 언젠가는 웹 데이터 수집을 종료해야겠죠. 생각해볼 수 있는 종료조건으로는 아래와 같은 것들이 있습니다.

더 이상 확장할 이웃이 없을 때까지 계속 수집한다.
데이터를 수집할 때, 웹 페이지의 총 갯수가 n개가 될 때까지만 수집하도록 제한한다.
데이터를 수집할 때, n차 이웃까지만 수집하도록 제한한다.

수집할 웹 서비스나 페이지의 특성에 따라 어떤 전략이 적절할지 선택해서 사용합니다.

다루지 않은 것들

재방문(revisit)에 대한 고려
웹 수집 예의 (politeness)
병렬화
인덱싱 (indexing: 메타데이터 추출)

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.

attachment:07_scaping.html of 강의들/SNA 분석을 위한 R 프로그래밍