Top > Info > Data Mining > 2-4. 연관성분석(Link Analysis)

▷▶ 연관성분석(Link Analysis)

 

Business의 세계는 상호관계, 인맥, 장소와 물자들이 함께하는 세계이다. 항공, 트럭등 여러 운송 회사들이 도시간을 연결해준다. 통신 고객들은 전화나 이동전화를 통해 이야기하며 서로서로를 연결하고 있다. 의사들은 그들과 제약 회사들이 연결되는 처방전 유형을 만들어 의약품들을 주문한다. 신용카드 고객들은 특정한 식당이나 소매점을 선호한다. 웹 사용자는 특정 사이트들만을 검색하며, 특정 광고에만 관심을 보인다. 상호연관관계는 어디에나 존재하며 이런 관계들은 대부분 Data mining technique이 직접적으로 이용하기에는 불가능하지만 값진 정보를 담고 있다. LA(연관분석)는 그러한 관계들의 맥을 집는 기술이다.

LA는 graph theory라고 불리는 수학의 지류에 근간을 둔다. 이 장에서는 그래프의 주된 개념을 살펴보고, 어떻게 LA가 실제문제를 푸는데 적용될 수 있는지를 알아보기로 한다. LA가 모든 유형의 data에 적용되고 모든 유형의 문제들을 풀 수 있는 것은 아니다. 그러나, LA가 사용된다면 종종 상당히 핵심적이고 쓰임새 있는 결과가 제시된다. 그런 만족할만한 결과를 얻을 수 있는 분야를 보면 다음과 같다.

- 전화 통화 유형을 분석; 모든 전화통화는 두 점간의 관계이며 가치 있는 정보를 담고 있다. 전화통화는 자연적으로 그래프로 보여질 수 있다.
- 의사 환자이전 유형의 이해; 의사가 환자를 다른 병원으로 보내는 것은 두 의사들간의 상호관계이기 때문에 이 또한 LA로 받아들일 수 있다.
- 사건의 실마리를 연결하는 것을 보면 FBI가 사무소를 도와주는 서로 분리된 출처에서 나온 (사건을 해결하는데) 자료를 연결하는 시스템.

LA를 명백하게 도와주는 tool은 조금 밖에 없고 이 방법들은 법률 시행의 분야로 전문화 되어왔다. 이 방법들은 연결의 시각화에 초점을 맞추고있다. 그래서 그들은 그들의 패턴을 찾기보다는 사람들이 지식을 발견하는데 도와준다. 관계형 데이터베이스에서 SQL 질의어는 LA의 근본이 될 수 있다. LA 질의어는 사용하기 아주 비싸다. 그러한 이유로 연결은 관계형 모형에 join하는 것과 동일하다. 작은 양의 자료에서 그들을 traversing하는 효과적인 방법을 제공한다. 객체지향기술은 데이터베이스 속에서 연결을 요약한다.

Item 간에 언제 연결이 존재하는지의 인식에 대해서 이 장에서 말해준다. 전화통화의 경우 연결은 명백하다. 한 사람이 다른 사람에게 전화를 하는 것이 연결이다. 다른 경우 연결은 자동적으로 생성되는 것을 필요로 한다. FBI에서의 선두적인 분석 시스템은 mbr과 같은 기술을 이용하는 item간의 관계를 결정한다.

 

몇 가지 기본적인 그래프 이론

그래프의 언어는 연결과 관계의 언어이다. 이장의 목적은 약간의 graph theory의 기초를 기술하는 것이다. 근간이 되는 아이디어는 아주 간단하고 이 장에서는 그래프가 어떻게 형성되는지 그리고 그들이 할 수 있는 것에 대한 감각을 준다.

 

그래프란 무엇인가?

그래프는 관계를 특별하게 관계를 말해주는 추상적인 개념으로 발전되었다. 그들은 수학이나 전산학에서 이들 관계를 이용하는 알고리즘을 발전시키는데 유용하다. 그래프는 매우 직관적이고 그들을 어떻게 이용하는지를 알려주는 예제들이 많다. 그래프는 다음 두 구별되는 파트로 구성된다.

 

nodes는 그래프에서 관계를 갖고 있는 것이다. 이것들은 이름을 갖고 추가적인 유용한 속성을 갖는다.
Edges는 관계로 연결된 nodes의 쌍이다. edge는 연결된 두 node로 보여진다.

 

그림 11.2는 두 그래프를 보여준다. 왼쪽의 그래프는 6개의 edges로 연결된 네 개의 node를 갖고 있다. 그리고 각 노드의 쌍 사이에 edge가 있는 속성이 있다. 이러한 그림을 fully connected(완전히 연결된)이라 부른다. 이것은 마이애미와 뉴욕, 네슈빌 그리고 달라스를 연결하는 비행을 나타낼 수 있다. 또 이것은 서로 알고 있는 네 사람을 표현할 수 있다. 또는 연결된 네 개의 범죄수사의 실마리를 나타낼 수 있다. 또한 이것은 아틀란타, 버밍햄, 그림빌, 샬럿 그리고 사바나를 연결하는 비행을 나타낼 수 있고 네 개의 신용카드회사에 의해 자주 방문되는 식당을 나타낼 수 있다. 그래프는 스스로 어떤 것이 어떤 것에 연결되었는지에 대한 정보를 가진다. 이것은 아주 많은 서로 다른 상황을 나타낼 수 있다. 이것이 추상적인 개념의 힘이다.

그래프에 대한 용어에는 적은 관점이 있다. 왜냐하면 그래프는 관계를 시각화하는데 유용하다. 그리고 이것은 node와 edge가 서로 교차하지 않는 edge에서 나온 것이라면 아주 좋다. 11.2에 나오는 그래프는 이 성질을 갖고 있다. 그들은 서로 교차하지 않는 평면 그래프이다. 그림 11.3의 두 그림은 적어도 두 edge가 교차되지않는 것에서 나왔다고 할 수가 없다. 사실 graph theory의 결과는 만약 평면이 아니라면 이것은 두 그래프에 잠재되어 있다.

그래프에서 두 node사이에 길이 존재하면 우리는 그래프가 연결되었다고 말한다. 이 장의 나머지에서 우리는 모든 그래프가 연결되었다고 가정한다. 통로(path)는 이 이름 이 암시하듯 edge로 연결된 노드의 순서화된 순서이다. 각 노드가 도시를 말하고 edge가 그들 사이의 비행을 나타낸다고 가정하자. 이러한 그래프에서 노드는 도시를 edge는 비행 구역이다. 두 도시간에는 논스톱비행구간으로 연결되어있다. 통로는 도시사이를 운행하는 비행구간의 여행 구간이다.

그림 11.4는 edge는 그들 사이에 연관된 가중치를 갖고있는 가중치 그래프이다. 이러한 경우 노드는 고객에 의해 구매되는 물건을 말한다. 그리고 edge에 있는 가중치는 이 두 상품을 포함하는 구매의 수를 말한다. 이러한 그래프는 어떤 구매능력분석에서 문제를 해결하는 방법을 제공한다. 이것은 구매능력자료를 시각화하는 유용한 방법이다.

LA에서 아주 평이한 문제 중 하나는 두 노드간의 가장 짧은 통로를 찾는 것이다. 각 edge에 부여된 가중치에 종속되는 가장 짧은 거리이다. 도시사이의 비행 그래프를 고려해 보자 . 가장 짧다는 것이 거리에 참조된 것일까? 아니면 비행구간의 가장 적은 수를 또는 가장 싼 비용을 참조한 것일까? 이 모든 문제는 그래프를 이용하여 같은 방법으로 대답된다. 이들의 차이는 edge에 부여된 가중치이다.

다음의 두 단락은 그래프 이론의 두 가지의 고전적인 예를 말한다. 이 두 문제와 정확히 같은 data mining문제는 거의 없다. 그러나 문제는 어떻게 그래프의 간단한 구조가 관심있는 해결책을 주도하는 지의 맛을 제공한다. 그들은 그래프이론의 중요한 개념의 예제를 제공하는 그리고 LA를 논의하는 중요한 근간을 제공하는 그래프를 가지고 독자들에게 친밀함을 제공한다.

 

Seven Bridges of Konigsberg

그래프 이론의 가장 초기 문제중 하나는 스위스의 Leonhard Euler이라는 수학자에 의해 18세기에 주장된 간단한 도전으로 생성되었다. 그림 11.5의 간단한 지도에서 보여주듯이 Konigsberg는 서로 연결된 두섬을 가지고 있고 나머지 도시는 7개의 다리로 연결되었다. 강의 다른 부분으로는 어느 다리를 이용해서든지 도달할 수 있다. 그림 11.5는 한번에 5개의 다리로 교차된 도시를 보여준다. Euler는 문제를 제기했다. 어느 도시에서 출발하건 모든 다리를 물에 빠지지 않고 정확히 한번만 지나 갈수 있나? 역사적인 기록에 의하면 도시의 이름보다 더 오래되었다. 18세기 Konigsberg는 지명적인 프로이센 도시이다.

이 문제를 풀기위해 Euler는 그래프 표기를 발명했다. 그는 Konigsberg의 지도를 네 개의 정점을 그리고 일곱 개의 다리를 가진 간단한 그래프로 표현했다.

몇 쌍의 노드는 하나 이상의 edge로 연결되어있다. 도시들간에 하나 이상의 다리가 있는 것을 보면. 지도에서 모든 다리를 한번에 건너는 루트를 찾는 것은 그래프에서 모든 edge를 정확히 한번 지나는 통로를 찾는 것과 동일하다. 이러한 통로(path)를 Eulerian Path라고 부른다.

 

세일즈맨의 여행

그래프 이론의 보다 현대적인 문제는 여행하는 세일즈맨의 문제이다.

 

Biological Computers

가장 짧은 Hamiltonian path를 찾은 것의 어려움이리란 잘 연구된 문제이고 현재 여전히 조사되어지고 있다. 이 분야에서 최근 가장 흥미로운 것 중 하나는 문제해결을 위한 신체공학의 시험 진공관을 밀어내고 들어온 컴퓨터는 더욱더 길어진 연쇄로 성장을 해 왔다. DNA의 연쇄가 특정문제에 나타남으로써 빠른 결정을 초래하게 되었다는 것 뿐이다.가장 짧은 Hamiltonian path의 결과는 생체공학(신체공학)을 성공적으로 적용시켜 왔던 문제 중의 하나였던 것이다.남부 캘리포니아 대학의 조사자(Adleman 박사)는 진공관 실험에 DNA의 연쇄를 사용하여 가장 빠른 Hamilton path를 찾는 것에 대한 문제를 나타내는 방법을 연구하였다. DNA 분석에 의해서 작은 그림으로 Hanmilton path를 찾을 수 있었고 슈퍼컴퓨터보다 몇 배나 더 빠른 computer를 추정해 낼 수 있었다. 그가 1994년에 Science를 논문으로 발간함에 따라 전산 생체학의 분야에 커다란 획을 그을 수 있었다  . 적용이었다. DNA의 연쇄는 표준 컴퓨터의 구성요소보다도 훨씬 작아지고 있다. 

 

Case Study : 누가 집에서 팩스를 사용하나?

자동차, 지역적, 그리고 장거리 전화 서비스 제공자들은 그들의 고객이 받고 거는 모든 전화를 기록한다. 이러한 데이터는 그들의 소비자 행동에 대한 정보(그들이 전화를 걸 때나 누구와 통화할 때, 그들의 계획에 의해 얼마나 이익을 찾는지에 대한)를 다량 포함하고 있다..

이러한 case study가 밝혀짐에 따라 정보분석가 들은 지역적 전화사용량을 분석하곤 하는 것이다. 이는 거주지역의 소비자가 팩스 사용에 대한 높을 확률을 기대할 수 있다.

 

왜 팩스의 사용량이 중요한가?

‘팩스의 소유에 대한 정보가 무엇에 유용할까? 이러한 정보는 시내전화 사용자들의 행동을 어떻게 알 수 있을까? ‘ 이러한 경우 제공자들은 지역에 거주하고 있는 재택근무를 하는 소비자의 서비스 패키지를 개발하게 된다. 판매 목적을 위해 소비자 선택은 회사로서는 핵심적 요소라 하겠다. 그리 오래 전부터 판매되지 않았던 정리된 시내 전화에서 지역서비스 제공자들은 재택근무를 하는 소비자로부터 지속적 수익을 잃고 있었다.

그들은 낮은 지역의 비율대신 높은 지역의 비율을 가진 사업자에게 요금을 높게 책정해 왔다. 지금까지 목표마케팅을 위한 소비자 선정은 지역 전화 제공자들이 지역적 비율이 낮은 사용자들을 의심하게 되었다. (소규모 사업자같은 사람들에겐 충격적인 제안이었다. )

재택근무 근로자를 위한 패키지를 판매, 전략을 세우는 회사는 소비자 서비스에 새로운 진출을 시도하였다. 그러나 어떤 소비자를 타켓으로 할 것인가?

이는 타켓 소비자를 소비자 집단을 정의함으로써 접근하는 방법들이 있다. 회사는 거주지역 거주자 조사, 인구통계학, 우편번호를 사용한 컴퓨터 사용권의 추정, 유사 데이터를 효과적으로 사용할 수 있다. 이 데이터가 시장일부의 정의로 명명지어졌다 할지라도 이는 여전히 개인적 소비자들의 요구를 충족시켜주는 하나의 시장으로 사용되어져 오고 있다.

한 팀이 팩스가 비즈니스를 목적으로 사용되기 때문에 이 팩스의 사용량을 알 수 있는 능력은 이러한 마케팅노력을 증진시킨다고 하였다고 제안하였다.

 

A에서 B로 가는 것은 B에서 A로 가는 경계와는 구분된다. A에서 B로의 경계를 가리키는 A는 A의 outgoing edge이고 B의 incoming edge이다. Directed graph는 자료표현의 강력한 방법이다.

2 종류의 노드는 directed graphs에서 흥미 있는 항목이다. Source 노드에 연결된 모든 경계는 outgoing edge이다. Incoming edge가 없기 때문에, source 노드에서 다른 노드로 가는 길이 그래프에서 존재하지 않는다. 노드의 모든 edge가 incoming edge일 때 그 노드는 ‘sink node’라고 불린다. source노드와 sink노드의 존재는 directed graph와 undirected graph사이의 중요한 차이다. Directed graph의 중요한 속성은 그래프가 같은 꼭지점에서 시작하거나 끝나는 path를 포함하느냐 이다. 이러한path 는 path그 자체가 끝없이 반복된다는 것을 의미하는 cycle이라 불리운다. ABCABCABC등등 directed graph가 적어도 하나의 cycle을 갖고 있다면, cyclic이라 불리운다. 예를 들어 비행구역 graph가 적어도 하나의 비행기의 노선이 될 것이다. 전화 graph에서 cycle의 맴버는 서로를 호출할 것이다. 모든 그룹의 할일이나 전화서비스업체의 판매회의에서 ‘친구와 가족형’ 촉진의 좋은 후보이다. 내과의를 위한 처방전 패턴표현 그래프에서는 cycle은 잠재적으로 부정적인 처방전을 지시한다.

 

Detecting Cycles in a Graph.

간단한 cycle검출 알고리즘은 directed graph가 cycle을 갖는지를 검사한다.

이 알고리즘은 관측치로부터 시작하는데 directed graph가 ‘sink 점’을 갖고 있지 않고 적어도 하나의 edge를 갖는다면 어떠한 path로 제멋대로의 확장이 가능하다. sink점이 없다는 것은 path의 종류노드가 항상 다른 노드와 연결되어 있고 그래서 path 는 그 노드에 연결되어 확장될 수 있다. 유사하게 graph가 source노드를 갖고 있지 않다면 우리는 항상 path의 시작을 위한 노드를 repend해야 한다. path가 graph에서의 노드보다 더 많은 노드를 포함하고 있다면 우리는 path가 적어도 하나의 node를 두번 방문해야 한다는 것을 알 수 있다 이 노드를 ‘X’라고 부른다. path의 첫번째 X와 두번째 X사이의 부분은 cycle이고 따라서 graph는 cyclic하다. 하나나 그 이상의 source node하나 이상의 sink노드를 가진 그래프의 경우를 생각해 보자. Source node와 sink노드는 cycle의 부분이 될 수 없음은 매우 명백하다.

그래프로부터 그들의 모든 edge와 함께 source와 sink code를 제거하는 것은graph가 cyclic한지에 대해 영향을 미치지 않는다. 결과 graph에 sink노드나source노드가 없다면 보여지는 바와 같이 cycle을 포함한다. sink node,source node, edge를 제거하는 과정은 다음중 한가지가 발생할 때까지 반복된다.

cycle이 없다면graph는 ‘acyclic graph’라고 불린다. 한 방향 관계성이나 종속성을 설명하는데 이 graph는 유용하다. 예를 들어 다른 생산 품들이 acyclic graph에 의해 표현될 수 있는 중첩된 계층에 자주 포함된다. 8장에서 우리는 taxonomies로 묘사된 계층을 보았다.

의사결정나무는 12장에서 설명되었듯이 acyclic graph의 또다른 예이다. Acyclic graph에서 어떠한 2개의 node가 서로서로 잘 정의된 상위의 관계성을 갖는다. A와 B 모두를 포함하는 어떤 path에서 node A가 node B보다 앞선다면 A와 B모두를 포함하는 모든 path에서 A는 B에 선행한다.(cycle이dkslfkaus)

이 경우 A는 B의 “predecessor”, B는 A의 “successor”라고 불리운다.

A,B모두를 포함하는 path가 없다면 A와B는 ‘disjoint’하다. 이 강력한 ordering은 node의 중요한 특성이 되며 때로 data mining의목적에 유용하다.

 

 

LINK ANALYSIS의 강점

LA는 이동 전화 데이터를 분석하는데 두 가지 역할을 한다. 하나는 시각적인 장점이다. 전화패턴을 몇 개의 그래프로 볼 수 있다는 것은 확실히 강력한 기능이다. 시각적으로 데이터를 볼 수 있다는 것은 패턴을 찾아내는데 용이하다. 이런 예에서 앞선 분류기술과 비슷하게 간주하여 가치 있는 고객을 골라야 할 것이다. LA는 고객들의 특별한 패턴과 어떤 고객들과 다른지를 제시하여 주었다. 한편으론, 동시에 모든 고객들에 대한 통화 패턴을 찾는 것은 수많은 노드와 수많은 에지의 그래프를 그리는 것을 요구할 것이다. 이것은 불가능하다.

두번째로는 LA는 많은 수의 고객집단을 시각적으로 나타내 줄 수 있다. 예를 들어 산출하는 고객들의 개념을 적용할 수 있다. 예를 들어 해지예방 프로그램은 주저하고 있는 많은 고객들이나 큰 영향을 줄 수 있는 고객들을 피하길 원한다.

 

Link Analysis의 장점

관계를 이용한다. (이에 편승하는 이득이 있다)
가시화하는데 유용하다.
파생되는 특징들이 나타난다.

 

연관된 데이터의 적절성
데이터와 데이터 마이닝의 문제는 대개 연관성을 포함한다. 전화데이터에 대한 두가지 케이스 연구에 의하면, Link Analysis 는 정보통신 측면에서 매우 유용하다. 즉, 전화는 두 사람간의 연관이기 때문이다. 연관은 운송과 같은 다른 영역에서도 나타나는데, 그래프가 종종 실제 지도에 대응되며, 이러한 경우 Link Analysis는 이미 적용되어 있으며, 관련성이 의사의 처방전 패턴과 같은 명확성을 가지지 못하는 다른 영역에서도 역시 적용된다.

 

시각화의 유용성
연관은 데이터의 형태를 시각화하는 가장 자연스러운 방식이다. 연관에 대한 직접적인 시각화는 지식을 발견하는데 큰 도움을 줄 수 있다. 자동화된 패턴이 발견되었을 경우, 연관성의 시각화는 무슨 일이 일어나고 있는지에 대해 명확한 이해를 할 수 있도록 도울 수 있다. Link Analysis는 관계형 데이터베이스와 OLAP툴의 형태와는 다르게 데이터를 보는 대안을 제시할 수 있으며, 데이터의 중요한 패턴을 제시할 수 있으나 패턴의 의미는 해석상에서 인간의 도움을 필요로 하게 된다.

 

파생 속성 생성
아이템을 포함한 연관성은 정보를 담고있다. 이러한 정보는 데이터의 새로운 속성을 생성하는데 사용되며, 영향을 주는 영역은 Link Analysis로부터 생성되는 새로운 속성의 예가 된다. 이러한 속성은 기존에 사용되었던 사용시간(Minutes of Use)보다 더 유용한 예측치로써 사용된다.

 

단점

적용 가능한 데이터의 유형이 적다
이용할만한 tool이 적다
사용되는 도구들이 비효율적이다.

 

데이터의 많은 형태에 적용되지 못한다.
Link Analysis가 적용되었을 경우에는 매우 강력할 수 있으나, 많은 형태의 문제에 있어서는 적절치 못한 단점을 가진다. 데이터를 받아들이고, 대답을 내는 뉴럴 네트워크와 같은 예측 혹은 분류 툴은 아니라는 점이다. 많은 형태의 데이터가 단순히 Link Analysis 에 적합하지는 않다. Link Analysis 가 가장 강력히 사용될 수 있는 것은 외부 전화(Outgoing call)의 형태와 같이 특정 패턴을 찾는 주제이며, 이것이 곧 데이터로 적용된다. 이러한 패턴은 데이터의 새로운 특성으로 전환될 수 있으며, 다른 직접적인 데이터 마이닝 기술을 가지고 연계되어 사용된다.

 

부족한 툴
Link Analysis을 지원하는 툴은 주로 법률 시행 영역에서 관계를 시각화하는데 주로 특화되어 나타나게 되는데 이러한 툴들은 수백 혹은 수천의 데이터 요소의 시각화를 제공한다. 특별한 목적을 지닌 코드는 전화의 상세데이터 혹은 의사들의 패턴을 묘사하는 데이터를 분석하는데 요구되어진다.

 

불충분한 SQL
연관성을 찾는 것은 관계형 테이블에 저장되어 있는 데이터에 대해 굉장한 비용이 소요되는 활동이며, 일반적으로 연관성은 데이터에 있어 매우 상세성을 지니므로 분석을 위한 연관성을 활용하는 것은 거대한 테이블에 대해 조인을 요구하게 된다. 이는 Link Analysis를 거대한 데이터 셋으로 적용하는데 있어 어려움을 야기할 수 있다.

 

Link Analysis를 적용해야할 경우

Link Analysis는 어떤 특정 형태의 문제에 적용가능한 지식 발견 툴이라 할 수 있다. 적용시에 Link Analysis는 다른 기법에서는 찾을 수 없는 데이터간의 패턴을 발견할 수 있으나 이러한 능력은 몇가지 제약사항을 가진다. 즉, 대부분의 데이터 형태에 적용치 않으며, 지식발견의 측면에서는 예측 혹은 분류의 능력을 갖지 못한다. 그러나 일단 패턴이 데이터상에서 발견되면, 뉴럴 네트워크나 의사결정 나무와 같은 다른 데이터 마이닝 기법에 대해 속성으로서의 값을 가진다.

Top > Info > Data Mining > 2-4. 연관성분석(Link Analysis)