[5] Co-Occurrence Networks Analyzing

[5] Co-Occurrence Networks Analyzing

 

Network Science

요즘 데이터 분석은 사회 전반적인 부분에서 쓰이지 않는 곳이 없다. 각각의 사용되는 domain 분야에서 세부적인 분석은 다를 수 있지만 , 두 가지 큰 공통점들이 있다. 어떠한 오브젝트들 사이의 관계를 파악하는 것이 중요하다는 것과 이러한 관계에 대한 데이터의 양이 점점 방대해지고 있다는 점이다. 즉 neuron에서 entity가 사람이 될 수도 , 나라가 될 수도 , 물건이 될 수도 있다는 것이고 이러한 entity들 사이의 관계를 파악할 수 있는 데이터의 수의 양이 점점 늘어나고 있다는 것이다. 

 

 

그래서 Network Science 라는 분야가 대두되기 시작했다. 기본적으로 Network Science는 아래 그림과 같은 형태로 데이터를 표현하고 이해한다. node와 entity , 그리고 사이에 연결된 edge가 entity들 사이의 관계를 이야기한다.

 

 

Network Science

 

이러한 Network Science는 실제 비즈니스에도 많은 영향을 미쳤다. 이러한 Network Science를 통한 다양한 알고리즘들이 등장하였고 , 넷플릭스나 아마존 같은 기업들은 Network Science를 통해 다양한 서비스를 제공하였다. 예를 들어 페이스북 같은 경우는 다양한 웹페이지들이 entity가 되고 , 웹페이지 들 사이의 관계를 파악해 Network 기반 , Graph 기반의 데이터 분석을 하고 사용자들에게 서비스를 제공한다는 것이다.

 

 

빅데이터 시대에 다가감에 따라 다루어야 할 데이터의 양은 점점 더 늘어나고 있다. 빅데이터를 다룬다는 것은 entity와 node , edge가 늘어난다는 것이고 graph의 크기가 커진다는 것을 의미한다. 그래서 방대한 양을 담고 있는 graph나 network를 다루기 위해서 제공되는 Framework가 몇 가지 존재한다. 예시로는 Google의 Pregel, Yahoo의 Giraph,  CMU의 GraphLab , Spark의 GraphX 등이 존재한다. 본문에서는 GraphX를 통한 Networks Analyzing의 예시를 소개한다.

 

 

 

Networks Analyzing

 

의료 데이터를 예시로 살펴보자. 어떠한 논문의 질을 평가할 때 Impact Factor라는 것을 사용한다. Impact Factor란 피인용지수로, 다른 논문에 인용이 많이 되었다면 그 논문이 중요하다는 것을 의미한다. 의료 분야의 논문은 전 분야에 걸쳐 논문 인용이 굉장히 많이 일어나는 논문 분야이다. 예를 들어 컴퓨터 분야의 Impact Factor가 5라고 하면 높은 수치일 수 있지만 , 의료 분야의 5는 낮은 수치라는 것이다. 이는 의료 논문의 양 자체가 많고 자주 나오기 때문이기도 하다. 즉 볼륨이 크기 때문이다. 의료 분야의 논문에는 의학 주제 표목(Medical Subject Headings)이라는 줄여서 MeSH라고 부르는 tag가 있다. MeSH라는 semantic tag를 이용해 논문 사이의 관계를 파악할 수 있고 , GraphX에서는 이와 관련된 Framework를 제공한다.

 

 

먼저 처음 살펴볼 것들은 major topic과 Co-Occurrence의 관계이다. 단순한 분석 이므로 굳이 GraphX를 사용하지 않아도 된다. major topic이 그냥 MeSH term에서 얼마나 많이 등장했는지 보기만 하면 된다는 것이다. 이런 간단한 분석 이외에도 connected components도 살펴본다. MeSH term에 있는 요소들을 Graph 형식으로 만들면 connection 즉 edge가 보일 것이다. 하나의 major topic에서 출발해 edge를 따라가다 보면 다른 연관된 topic으로 넘어가게 되고 , 이러한 방식을 통해 데이터가 small graph set 인지 아닌지 파악할 수 있다. 또 degree distribution을 확인해 해당 topic이 얼마나 중요한지도 알 수 있다. degree는 뒤에서 좀 더 살펴보자.

 

 

 

 

 

MeSH 데이터를 단순하게 나열한 예시이다. 이런 식으로 각각의 Topic name이 존재하고 각 topic이 얼마나 존재하는지 count 할 수 있다. 

 

 

이러한 MeSH 데이터 안의 topic 데이터 들 사이의 Co-Occurrence를 보려면 2개씩 짝 지어보면 topic 사이의 pair를 확인할 수 있다. pair에 대하여 살펴보자. 하나의 논문안에 두 가지 topic이 동시에 등장했다면 , 두 topic 사이에는 관계가 강하다고 볼 수 있다. 그래서 해당 pair가 전체 데이터 set 안에서 얼마나 등장하였는지 확인하면 어떠한 topic끼리 관계가 강하고 약한지 알 수 있는 것이다. 하지만 많이 등장한 major topic이 Co-Occurrence에도 많이 있다면 이 pair는 흥미로운 , 의미 있는 pair가 아니라는 결론이 나온다. 데이터 사이언스의 목적은 당연한 정보를 알려주는 것이 아닌 그 안의 무언가 모르는 사실을 알려주는 것이기 때문이다. 

 

 

또한 데이터를 단순히 세는 방법으로는 Insight를 얻을 수 없다. 그래서 Co-Occurrence Network를 만들어 분석한다. Co-Occurrence Network를 통해 분석하면 보다 의미있는 결과와 Insight를 얻을 수 있다.

 

 

 

 

위와 같이 Co-Occurrence Network를 만들고 , 또 분석하면서 의미있는 결과를 얻을 수 있다. 위의 Co-Occurrence Network 예시를 통해 살펴본 결과 Docetaxel이라는 항암제와 Paclitaxel이라는 항암제 사이에 증식당뇨망막병증이 연관되어있는 사실을 확인할 수 있다. 이를 통해 위의 두 항암제는 증식당뇨망막병증이라는 부작용과 관련이 높다고 볼 수 있는 것이다.

 

 

 

Spark GraphX

 

GraphX 라이브러리는 2개의 특징 RDD를 가지고 있다. VertexRDD와 EdgeRDD이다. 각각 줄여 VD , ED라고 부른다. VD에는 VertexID와 속성이 들어있다. ID의 경우 정수 타입의 단순한 Vertex를 구분하는 ID이고 , 속성 값으로는 위의 예시에서 본 것처럼 항암제 이름 같은 데이터가 들어간다. ED에는 2개의 VertexID가 들어가고 Edge에 대한 속성이 들어있다. ED의 속성에는 연결된 2개의 VertexID 요소 사이의 Edge가 얼마나 강한지 보여주는 속성 값이 들어있다. 위의 VD와 ED를 통해 Graph class의 instance를 만들 수 있다.

 

 

분석하기에 앞서 , 먼저 전체 graph가 하나로 연결되어있는지 그렇지 않은지 확인해야 한다. Full connected는 어느 Vertex에서 출발하던지 어디든 갈 수 있다. 그래서 단순히 Edge의 sequence로 표현할 수 있다. 하지만 전체 graph가 2개 혹은 그 이상의 graph들로 나뉘어 있다면 이러한 각각의 graph를 분석해야 한다.

 

 

또한 Full connected 역시 다양한 형태로 나뉠 수 있다.

 

 

 

위의 두 graph 모두 Full connected graph이지만 모양은 서로 다른 것을 확인할 수 있다. 좌측의 graph의 경우 중앙의 Vertex를 제거하면 graph 구조 자체가 깨져버리게 된다. 우측의 경우는 순환하는 형태의 graph이고 loop를 이루는 구조이다. 우리는 Full connected graph를 시각화해서 확인하기 전까지는 graph가 좌측의 형태인지 , 우측의 형태인지 , 혹은 다른 형태인지 알지 못한다. 

 

 

여기서 살펴보는 개념이 degree이다. degree란 한 Vertex에 연결된 Edge의 개수를 의미한다. 만약 좌측의 graph의 경우 중앙의 Vertex는 5의 degree를 갖게 될 것이고 우측의 경우 어떠한 Vertex든 2의 degree를 갖게 될 것이다. 따라서 graph안의 각각의 Vertex의 degree를 확인하는 것으로 graph 구조에 대한 추가적인 정보를 얻을 수 있다.

 

 

 

Pearson’s chi-squared test

 

위의 MeSH를 통한 예시에서 간단한 Co-Occurrence counting으로는 concept pair가 의미 있는 관계라서 Co-Occurrence가 높은지 , 혹은 단순히 자주 같이 표현되어서 node가 큰 weight의 edge로 연결되었는지 분간할 수 없다. 따라서 2개의 node pair가 얼마나 흥미롭고 놀라운지 알려주는 방식이 필요하다. 이때 사용하는 방식이 Pearson’s chi-squared test이다.

 

 

이를 통해 나오는 값을 가지고 2개의 node가 얼마나 서로 의존성이 높은지 , 독립적인지 알 수 있다는 것이다. 2개의 node 사이에 관계가 강하게 존재한다면 의미 있는 관계라고 여길 수 있고 서로 독립적이지 않다고 볼 수 있다. 그래서 chi-squared test (카이제곱 검정)을 통해 통계적인 유의미성을 살펴보고 연관이 있는지 없는지 확인하는 과정으로 두 node 사이의 관계를 알아볼 수 있다.

 

 

아래의 예시는 가장 기본적인 2 * 2 테이블의 chi-squared test 다.

 

 

 

위의 chi-squared test 예시는 2 변수에 대한 수행 방식을 보여준다. chi-squared test는 빈도수를 관찰하면서 관계가 있는지 없는지를 본다. 위의 예시는 2변수에 관한 chi-squared test 이므로 2개의 node로 이루어진 pair를 살펴보는 chi-squared test다. chi-squared 값은 위의 x^2 식처럼 나오게 된다. A가 나오고 B는 안 나오는 빈도수 , A가 안 나오고 B는 나오는 빈도수 등등 위의 테이블 안의 값들을 빈도수로 모두 채워 넣는다. 이후 식에 따라 계산하고 값을 구한다. 만약 YY나 NN처럼 같이 나오거나 , 나오지 않거나 하는 빈도수가 크다면 두 변수 사이의 관계가 크다고 판단할 수 있다. 또한 YN이나 NY 같이 하나가 나왔는데 다른 하나가 나오지 않은 빈도수가 크다면 이는 두 변수 사이의 관계가 작다고 판단할 수 있다. 따라서 chi-squared 값이 크면 두 변수 사이에 관계가 존재한다고 볼 수 있고 이를 Edge의 weight로 사용할 수 있다는 것이다. 

 

 

만약 Co-Occurrence 한 경우만 생각해서 Edge의 weight를 만들어 주었다면 이는 chi-squared test에서 YY만을 사용한 것과 다름이 없을 것이다. 그 이상의 결과를 알아보기 위해 사용한 것이 chi-squared test 다.

 

 

Edge의 weight 값을 chi-squared 값으로 두었기에 클수록 의미 있다는 사실을 알았다. 통계적 분포를 사용하는 경우에는 언제나 기준값이 존재한다. 이를 알아보기 위해 chi-squared 분포를 확인해야 한다.

 

chi-squared 분포는 DOF (degree of freedom) , 자유도에 따라 모양새가 달라진다. chi-squared test를 통한 chi-squared 분포의 DOF는 비교하기 위한 변수의 개수를 의미한다. 위의 예시의 경우 2개의 변수 사이의 관계를 확인하는 chi-squared test 이므로 DOF는 1이 될 것이다. 따라서 위의 예시의 기준값을 정하는 경우 DOF = 1인 chi-squared 분포를 확인하면 된다.

 

 

 

 

 

DOF가 1인 chi-squared 분포에서 chi-squared값을 통해 p-value를 확인하고 이후 null hypothesis을 수용할지 , 거부할지 선택한다. 만약 p-value가 0.001이라면 그때 chi-squared값은 19.5이다. 따라서 chi-squared값이 19.5 라면 두 변수 사이에 관계가 없을 확률이 0.001% 아래라는 것이다. 그렇다면 두 변수 사이에는 강한 관계가 존재한다고 판단할 수 있다. 이처럼 Edge에 대한 chi-squared값들을 통해 일정 신뢰도 이상의 Edge만 남길 수 있고 이를 통해 의미 있는 graph를 그릴 수 있다.