StoryLine-Unsupervised Geo-event Demultiplexing in Social Spaces without Location Information(2017)

본 논문은 위치정보가 없는 소셜 공간의 비감독적인 지리이벤트로 디멀티플렉싱 시스템이다.

 

1. INTRODUCTION

도시에 스마트폰이 보급되면서 스마트폰은 IoT시대에 가장 많이 보급된 기기 중 하나가 되었다.

이러한 스마트폰 사용의 증가는 데이터 수집의 증가로 이루어졌는데 스마트폰의 전화 센서를 이용하여 다양한 도시 전체의 측정 작업에 이용되어왔다. 이러한 작업을 Crowd-Sensing이라고 한다.

(crowd-sensing : 대규모 개인 그룹이 공동으로 데이터를 공유하고 정보를 추출하면서 공통의 관심있는 프로세스를 측정, 매핑, 분석, 추정하는 기술)

 Crowd-Sensing과 함께 본 논문에서는 demultiplexing을 사용한다.

demultiplexing이란 multiplexing의 반대되는 개념이다.

multiplexing이란 우리 말로 다중화로써 그림과 같이 여러 신호를 하나로 묶어 전송하는 것을 말한다.

demultiplexing은 역다중화로써 하나로 묶인 것을 여러 개로 나누는 것을 말합니다. 예를 들면 여러 개의 우편을 한나의 우체국으로 보내지며, 여기서 다시 각각의 목적지로 보내지는 것과 같다고 할 수 있다.

 

본 논문에서는 트위터를 기준으로 분석하기 때문에, 트위터에서 event를 demultiplexing한다고 한다.

 

또한 소셜 환경은 물리적 환경과 다르지 않다고 한다. 그 이유는 다음과 같다.

그림이 말하고자 하는 것은 '물리적 물체가 물리적 환경에서 물리적 매체를 관찰하여 감지할 수 있는 구별 가능한 신호를 유도하는 방법처럼 사회적으로 관련된 사건은 소셜 미디어를 관찰함으로써 감지할 수 있는 구별 가능한 신호를 사회 환경에서 유도할 수 있다.' 이다.

 다음과 같은 이벤트탐지 연구 기법은 총 3가지 카테고리로 나눌 수 있다.

첫 번째로, 몇몇의 알고리즘은 탐지를 수행하지만 demultiplexing은 수행하지 않는다.

이는 교통사고나 홍수 등 큰 타이틀의 구분은 할 수 있지만, 동시발생된 교통사고는 분류할 수 없다.

두 번째로, demultiplexing을 수행하지만 시간과 위치 기반으로 수행한다. 

이는 위치 정보가 없으면 수행하지 못하는데 트위터에서는 2%만이 geotagged를 사용하기 때문에 이 접근법은 작은 이벤트를 쉽게 놓칠 수 있다.

세 번째로, 위치 데이터없이 demultiplexing을 수행한다. 

그러나 자연어 전처리나 머신 러닝을 사용하기 때문에 특정 언어에서만 특화되어있거나 사전 교육이 필요한 상황이 발생한다.

본 논문 주제인 STORYLINE은 위치 정보가 필요하지 않다. 앞에서 설명 한 것처럼 트윗의 98% 이상이 geotagged를 사용하지 않기 때문에 더 많은 이벤트를 식별할 수 있는 것을 알 수 있다.

또한 스토리라인은 비감독적이다. 이는 언어 특징에 구애 받지 않으며 트레이닝이 필요 없음을 의미한다. 그렇기 때문에 비용이 적게 들거나 아예 들지 않을 수 있다.

 

2.PROBLEM STATEMENT

이벤트는 시간이 지남에 따라 새로운 이벤트가 생성될 수 있으며, 오래된 이벤트는 결국 제거된다. 그렇기 때문에 각 이벤트는 lifespan을 가지고 있다고 할 수 있으며 이 기간동안 이벤트가 진행된다고 가정한다. 이 논문의 목적상, event는 사건으로서 광범위하게 정의하며, 제한된 시간과 공간 내에서 여러 명의 사람이 독립적으로 관측할 수 있다.

 본 논문에서는 관련 인스턴스 탐지 및 인스턴스 추적 알고리즘과 함께 동일한 이벤트 범주의 서로 다른 인스턴스의 demultiplex 문제에 대한 주의를 제한한다. 감지 기법으로는 spikes를 사용하며 이는 자주 등장하지 않는 단어를 찾아내는 알고리즘이다. 그렇기 때문에 같은 교통사고 키워드여도 구분할 수 있으며, 이는 co-occur보다 spikes가 성능이 더 좋다고 할 수 있다. 또한 STORYLINE은 시간을 슬롯으로 나누고 현재 상태를 모니터링 환경으로 추상화한다. 각각의 이벤트 인스턴스를 모아 집합으로 관리하며, SUMMARY를 하여 관리한다.

 즉, 본 논문에서는 이벤트 인스턴스를 어떻게 집합할 것인지와 SUMMARY에 어떻게 요약할 것인지가 핵심이다.

 

3. THE DESIGN OF STORYLINE

스토리라인 쿼리에서 교통체증 또는 사고 같은 키워드는 고유한 콘텐츠를 필터링하는 뉴스피드 구독과 같으며, 프로세스가 시작하면 트위터 API를 사용하여 최근 트윗에서 특이한 키워드를 획득한다. 후에 서로 다른 사건에 대하여 분리하기 위해 디멀티플렉싱을 수행하고, 이 과정은 사용자가 종료할 때까지 계속 수행된다. 이 디멀티플렉싱 접근법의 가장 큰 기여는 단순성으로, 이벤트 인스턴스가 충분히 분리되어 있는 가장 간단한 희소 특징 공간을 찾는다.

예를 들어, 10000개의 단어로 1000개의 이벤트를 표현하려고 할 때 왼쪽 그림과 같이 10000개의 단어로는 이벤트를 표현할 때 중복이 될 수 있다. 그래서 오른쪽 그림과 같이 하나의 단어가 아닌 두개의 단어 즉, 단어 쌍으로 표현하면 공간 활용도가 높아져 이벤트를 중복되지 않게 표현할 수 있다. 희소 관측과 관련하여 두 가지 주의사항을 이해해야 한다.

첫 번째로, 희소성 관측 유효성은 사용되는 키워드 간의 강력한 상관관계 결여에 의존한다. 간단한 필터링을 통해 한 쌍의 키워드 사이에 강력한 상관관계가 없음을 보장한다. 

두 번째로, 희소성은 두 이벤트 인스턴스가 다르다면 그들의 차별적인 키워드 쌍 또한 높은 확률로 다르다는 것을 나타내는 것이다. 이 역이 항상 참은 아니며, 만약 이벤트 인스턴스에 이벤트를 고유하게 특성화하는 높은 빈도의 키워드가 세개 이상 있는 경우 통합해줘야 한다. 

여기서 information gain을 계산해주고, 이 값을 통해 차별적인 단어쌍을 추출한다. 

 스토리라인 시스템은 현재 윈도우에서 새로운 차별적 쌍을 감지하면서 이전 윈도우에서 발견된 차별적 쌍에 기반하여 계속 디멀티플렉싱하는 시스템으로, 각 시간 슬롯 k에서 먼저 이전 슬롯에 사용된 모든 파별적 키워드 쌍을 상속한다. 

여기서 각각의 쌍은 거리측정기준을 사용하여 단어들의 통계적 분포를 기반으로 같은 트윗이 아니라는 것을 계산하는데, 총 4가지의 함수를 사용하여 계산한 결과 Jaccard distance가 가장 좋은 결과를 보였다.

 이벤트 추적은 연속적인 시간 간격에 걸쳐서 bin 통합을 적용함으로써 간단한 방법으로 통합 알고리즘을 확장한다. 먼저 현재 슬롯을 통합한 후에 k와 k-1을 통합하는데, 여기서 하나의 문제는 이벤트와 사람들의 묘사방식의 진화로 인한 발달이다. 그래서 overlapping sliding window를 사용하여 이러한 변화를 잡아낸다. 그러므로 시간이 지남에 따라 신호가 달라져도 관련 클러스터를 적절하게 통합할 수 있다.

 

4. SYSTEM IMPLEMENTATION

본 논문에서는 타겟 소셜 매체를 트위터로 지정하였으며 구현은 파이썬으로 하였다. 스토리라인에서는 create, pull, kill, stat 총 네 가지 인터페이스를 제공하며, create는 이벤트 트레킹 작업을 시작하는 것으로 파라미터로 크롤링된 키워드들의 리스트이다. pull은 실시간으로 이벤트 트레킹 결과를 건네주고, kill은 작업을 끝내는 것이며 stat은 시간 경과에 따른 이벤트 인스턴스의 발생 빈도를 검색하는 기능이다.

 먼저 트레킹 작업이 시작되면 크롤링된 파라미터는 트위터 API를 사용하여 파라미터에 포함된 조건을 실시간으로 만족시키는 트윗을 크롤러로 전달하고, 반환된 트윗의 경우 먼저 리트윗과 같은 중복 트윗을 필터링한 다음 필터링된 트윗을 이벤트 감지모듈로 전송한다. 세 번째로 이벤트 신호 감지 및 통합이 수행되고 이벤트 트레킹 모듈로 전달되는데, 사용자가 작업 ID로 pull 함수를 호출하면 JSON형식을 사용하여 인코딩된 가장 최근의 추적 결과가 반환된다. 여기서 지역화 모듈이 포함되어 있지만 본 논문과는 관련이 없다고 한다. 그리고 사용자가 kill을 호출하지 않는 한 트레킹 작업은 계속 작동한다.

 

5. EVALUATION

<논문 참조>

 

7. CONCLUSIONS

본 논문에서는 물리적 이벤트 탐지 및 디멀티플렉싱을 목적으로 물리적 센서 데이터 수집 및 소셜데이터 처리와의 융합을 강화하는 IoT 애플리케이션을 위한 새로운 서비스를 제시하였으며, 이 시스템은 비감독적이고, 위치정보가 필요없는 디멀티플렉싱알고리즘이다. 또한 시간의 경과에 따른 빈도와 같이 사건에 대한 다양한 통계를 계산할 수 있고, 본 논문의 저자들은 물리적 센서와 소셜 미디어의 조합을 공동으로 이용하는 후속 아이디어를 조사하는 과정에 있다고 한다.