::고려대학교 DMQA 연구실::

Lab. Activity

 

 

 

Lab. Activity>Seminar  

Exemplars Detection and Identifying Fundamental Structure of Data Points (발표자: 김영훈)

작성자 관리자 작성일 2016-07-29 오후 5:08:13
내용

발표자 Summary


김영훈

오늘 세미나에서는 Exemplar Group을 찾고, 이 정보를 활용해서 Clustering 까지 하는 방법에 대해서 소개를 했다. 기존에도 Exemplar 를 찾으면서 Clustering 하는 방법들이 있었지만 이 방법들은 One Exemplar for One Cluster 라는 가정을 가지고 있어 데이터를 분석하고 군집화하는 데 태생적인 한계점을 가지고 있다. 이러한 한계점을 극복하기 위해서 Exemplar group for One Cluster 라는 가정을 하게 되었고, 이 가정을 기반으로 Swarm Ascending 이라는 방법을 만들었다. 이 방법은 Density Peak을 찾는 일반적인 방법과 달리 Density Range 를 찾는 방법이다. 고전적인 Optimization 기법으로는 이것을 찾을 수 없기 때문에 우리는 Swarm Intelligence 에 기반해서 알고리즘을 만들었다. 각 데이터 포인트들을 Swarm 을 구성하는 하나의 개체로 보고서 이 개체들을 밀도가 높아지는 방향으로 움직인 후 이것을 합쳐서 Exemplar Group 을 만든다. 그 다음 Outlier 개체들을 제거하고 Scan해서 Clustering을 한다. 이 방법을 사용했을 때, 기존 방법들의 한계점들을 잘 극복하고 강건한 군집화 및 Exemplar Detection 방법을 만들 수 있었다. 향후에는 실제 연속적인 패턴이 군집이 되는 실제 데이터를 사용해서 군집화를 잘 하고, Exemplar Group 도 잘 찾을 수 있는지 실험해보고 싶다.

 

청취자 Summary


유재홍

금일 세미나는 Exemplars Detection and Identifying Fundamental Structure of Data Points를 주제로 진행되었다. 가장 유명한 군집화 방법론 중 하나인 k-means 알고리즘이나 k-medoid와 같은 방법론은 군집을 대표할 수 있는 관측치를 추정하거나 탐색하여 이를 중심으로 군집을 구성하게 된다. 이러한 방법론에서는 대표적인 관측치를 거리를 기반으로 탐색하는 반면, Mean shift clustering의 경우는 kernel density estimation (KDE)을 통해 밀도를 추정하면서 밀도를 최대화할 수 있는 관측치들을 탐색하게 된다. 이와 같이 밀도를 기반으로 추정하는 방법론들은 잡음이나 이상치에 대해서 강건하게 작동함으로써 보다 군집을 효과적으로 탐색할 수 있다는 장점을 가지고 있다. 하지만, 기존 방법론들은 대표 관측치 (Examplar)를 단일하게 추정하여 군집을 구성하게 되는데, 이러한 경우 Globular하지 않은 군집이 내재된 경우에 적절한 군집을 탐색할 수 없다. 이를 해결하기 위해서 발표자는 단일 Examplar가 아닌 Examplar group를 추정하여 이를 바탕으로 군집을 구성하는 방법론을 제안하였다. Examplar group은 군집의 중심이 되는 뼈대 (Structure)을 의미하며, Swarm ascending이라는 방법론을 활용하여 KDE를 최대화하는 방향으로 추정되는데, 매우 흥미로운 방법론이라고 생각된다. 특히, 발표자와 유사한 분야를 연구하고 있는 입장에서 상당히 흥미롭게 청취하였고, 많은 도움이 되었다. 

 

정영재

영훈이의 "Exampler Detection and Identifying Fundamental Structure of Data Points"라는 제목의 세미나를 들었다. 세미나가 매우 인상깊었고, 이런 연구가 진행되는 점에서 신선한 자극을 받았다. 기존 example points를 찾는 방법으로는 k-means, mean shifts, affinity propagation, density peak search가 있었다. 하지만 이런 방법들은 nonlinear한 pattern을 잘 못찾는 단점이 있다. 왜냐하면 local optima를 찾는 방법이기 때문이고, local optima에 해당하는 one data point들을 찾기 때문이다. 하지만, 제안 방법에서는 example points들을 찾음으로써, nonlinear pattern을 잘 찾을 수 있다. 또한 outlier를 고려하는 방법을 찾음으로써, outlier에도 강건하다(robust to outlier). 이번 세미나를 들음으로 많은 자극이 되었다. 


손지은

하나의 exemplar를 통해 하나의 군집을 형성하는 기존의 방법론과 달리, exemplar 그룹을 찾는 방법론을 설명하였다. density 기반으로 데이터 분포의 패턴을 찾는다는 것이, 사람의 눈으로 직접보고 직관적으로 군집을 구별하는 방법과 가장 유사하지 않을까 생각된다. 제안하는 방법론을 통해 도출된 range 정보로부터 어떻게 exemplar 그룹을 정의할 것인가에 대한 연구가 더 이루어져야 하겠다.

 

이한규

우리가 흔히 배우는 군집화는 군집 하나당 군집을 대표하는 하나의 관측치 혹은 대표값이 있을 것이다 라는 가정을 한다. 그러나 오늘 진행한 세미나의 (제안한) 방법은 하나의 군집을 대표하는 대표값은 여러개 일수도 있다 라는 생각을 가지고 진행한 것 같다. 이러한 생각은 어떻게 보면 당연한 것이라 생각한다. 실제 다루는 데이터에서는 하나의 군집을 설명하기에 하나의 대표값은 상당히 부족하다. 아니 설명이 안될 때가 더 많다고 생각된다. 그렇기 때문에 각 군집을 설명하기 위한 여러개는 대표값이 필요하다. 본 세미나에서는 군집을 설명(대표)하기 위한 여러개의 대표값을 찾기위한 방법론을 제안하였다. 그리고 그 시뮬레이션을 통해 결과를 같이 공유하였다. 본 방법론은 데이터 구조의 뼈대를 찾는 점에서 상당히 좋은 연구라고 생각된다. 세미나 처음에 말했던것 처럼  semi-supervised learning에서도 초기 값을 선택 문제등 과 같이 적용될 수 있는 분야도 다양하다고 생각한다. 기존에 알고 있는 것을 뒤집어 생각하는 연습이 필요할 것 같다.

 

곽민구

금일 세미나는 데이터의 핵심적인 특성을 대표하는 Exemplar를 찾고 군집화하는 알고리즘 제안에 대한 내용으로 진행되었다. 기존의 Exemplar Detection 방법들은 하나의 군집에 하나의 Exemplar가 존재한다는 가정을 하고 있는데, 다수의 Exemplar가 이루고 있는 '산맥'을 찾는 방법론을 제안하였다. 실제 현실세계에서 사용되는 데이터(특히 이미지 데이터)는 Manifold Structure를 가지고 있으며 이는 선형적 관계를 가지고 있는 데이터와는 다르게 널리 알려진 군집화 알고리즘인 K-means, Mean-shift 방법 등으로 찾아내기가 매우 까다롭다. 이를 해결하기 위해 김영훈 연구원이 제안한 방법은 Swarm Intelligence를 활용한 Swarm Ascending for Detecting Exemplar Group and Clustering이다. 우선 데이터에서 밀도가 높은 곳으로 초기의 Gradient를 계산한 다음 데이터 포인트를 그곳으로 옮긴다. Outlier Detection을 위해 Nearest Distance와 Kernel Density의 Plot을 그려 elbow point를 찾아 이상치를 제거한 후, 데이터를 다시 원래의 위치로 옮기는 알고리즘이다. 기존의 방법들과의 차별화로 하나의 Center를 찾지 않고 group을 찾는 점, 계산속도와 활용성이 높다는 점 등이 있다. 개인적으로 Clustering 결과물을 Plot으로만 보여주는 것이 아니라 다른 measurement를 사용해서 정량적으로 보여주면 좋을 것 같다는 생각이 든다.


이슬기

오늘 세미나에서는 Exemplar와 군집화를 주제로 다루었다. 데이터의 군집이 존재할 때, 그 군집을 대표하는 점인 Exemplar를 찾는 기존 연구들의 가정은 한 군집당 하나의 Exemplar가 존재한다는 것이다. 발표자는 manifold 형태의 데이터에서는 하나의 군집을 하나의 Exemplar가 표현하기는 어렵다는 현상을 발견하고, 여러 개의 Exemplar의 그룹으로 manifold 형태의 군집을 표현하고자 했다. 문제를 풀기 위해 기존 알고리즘들을 적절하게 수정 보안해서 사용한 것도 탁월하지만, 발표자가 현상을 바라보는 관점 자체가 실제 데이터에서 매우 의미가 있다고 생각된다. 문제를 정의하고 이를 해결하는 일련의 과정을 다 거치는 좋은 연구방법을 보여준 것 같다. 현재 여러 가지 시뮬레이션을 통해 군집의 결과가 좋다는 점을 보여주었지만, Exemplar point를 정하는 것도 중요한 이슈가 될 것 같다. 세미나 중에 나온 방법으로는 nearest neighbor를 이용하여 몇 개의 데이터를 찾는다고 하였으나 산맥과 같은 부분을 얼마나 연속적으로 잘 찾아질 수 있을지나 데이터 포인트의 개수는 몇 개가 될 지 등 고민할 부분이 있을 것 같다. 최종적으로 데이터가 모인 그 지역 자체의 boundary를 잘 만들어 Exemplar 구조 또는 지역 등으로 정의해도 의미가 있지 않을까 생각된다.

 

박찬희

Exemplar detection은 대표성을 지닌 관측치를 찾는 방법론으로 레이블이 없는 데이터를 분석대상으로 하는 unsupervised learning에  속한다. Exemplar를 찾기 위해 clustering 기법이 주로 이용된다. k-means 모델에서는 각 군집의 centroid를 exemplar로 볼 수 있다. Mean shift clustering 모델에서는 density gradient estimation을 이용해 각 군집에서 밀도가 제일 높은 점을 exemplar로 제안한다. 기존 기법들은 군집 당 하나의 exemplar를 도출하였지만 발표자는 군집을 잘 설명할 수 있는 다수의 exemplar 찾을 수 있는 알고리즘을 제안하였다. 실험결과, 비선형 특성을 가지는 데이터에서 제안모델이 기존모델들에 비해 우수한 성능을 보여주었다. 무인자동차 산업의 성장과 더불어 visual recognition분야가 크게 각광 받고 있다. 제안된 알고리즘은 2차원으로 표현된 다양한 이미지 데이터 분석에 유용할 것으로 생각된다.


강현구

오늘 세미나에서는 특정 데이터 군집을 대표할 수 있는 exemplars를 찾는 다양한 기법들과 함께, 발표자인 영훈이 형이 제안하는 새로운 방법론이 함께 소개되었다. 기존 방법론들에선 특정 군집을 대표하는 exemplar을 1개만 찾도록 하였는데, 이런 방식은 데이터가 비선형적인 특성을 가질 경우에 적절한 exemplar을 찾는데 어려움을 겪는다. 발표자는 이를 보완하기 위해 특정 군집을 대표하는 exemplar가 1개여야 한다는 가정에서 벗어나, 다수의 exemplar을 찾는 알고리즘을 제안하였다. 해를 찾아가는 과정에서 최적화 기법인 swarm intelligence의 개념을 도입했다는 점에서 굉장히 창의적이였다는 생각이 든다. 기존 군집화 알고리즘들과 사뭇 다른 접근 방식을 갖고 있다는 점에서 향후 파생 연구도 다양하게 나아갈 수 있을 것 같다. 실험결과로 보여준 2차원 데이터에 대한 군집화 성능이 탁월했는데, 높은 차원의 데이터에 대해서도 실험을 진행하여 계산 속도 등의 문제도 추가적으로 체크해보면 좋을 것 같다.

 

강성현

Science, IEEE TPAMI 등 유수 저널에 실리는 논문 중에서는 이론적으로 난이도가 높은 논문들도 물론 다수 개제되어 있다. 그러나 개인적으로 관심이 가는 내용은 아무래도 쉽고 기발한 아이디어로 우수한 성과를 나타내는 논문들이 아닐까 한다. 오늘 세미나에서 소개된 방법론은 바로 후자에 속하는 내용이라고 생각된다. 일반적으로 Exemplar Detection은 데이터의 성격을 규정하는 대표적인 포인트를 찾는다. 이는 k-mean, mean shift, affinity propagation, density peak search 등 대중적인 방법론에서 공통적인 접근 방식이다. 그러나 오늘 제안된 방법론은 대표적인 하나의 포인트를 찾는 대신 대표 데이터 그룹을 찾음으로써 이를 대신한다. 이를 위해 mean shift clustering의 방법론을 응용한다. 기존 방법은 반복될 때 마다 밀도가 높은 방향으로 점의 이동 방향을 갱신하지만, 제안된 방법은 초기 설정된 방향으로 변경없이 반복적으로 이동시키는 방법을 사용한다. 이러한 과정을 거치면 데이터들이 군집화됨과 동시에 요약된 데이터 구조들을 파악할 수 있는 특징이 있다. 클러스팅 성능은 매우 고무적이다. 실험 결과를 보면 일반적으로 클러스터링이 까다롭다고 여겨지는 바나나, 도너츠, 스파이럴 등의 형태도 완벽하게 클러스터링 되는 모습을 보였다. 이는 향후 사진과 같은 고차원에서도 높은 성능을 기대해 볼 수 있는 부분이라고 생각된다. 또한 파라미터 종류도 많지 않고 bandwidth와 같은 일부 파라미터는 모델에 강건한 성격도 있어 활용성도 매우 돋보였다. 물론 한 포인트가 아닌 데이터 그룹을 찾았기 때문에 여전히 그룹 중에서 어떤 데이터를 대표 데이터로 볼 것인가 선택하는 문제는 남아있지만 데이터 특징이 이미 규정되어 있기 때문에 크게 어렵지 않을 것으로 보인다. 향후 연구로 고려하면 좋을 것으로 생각된다. 

 

박성호

방대한 데이터에서 의미 있는 유의미한 패턴을 찾아내는 것이 데이터마이닝이다. 하지만 유의미한 패턴이라는 것은 매우 추상적이다. 가장 직관적인 방법은 수 많은 데이터 중에서 핵심적인 데이터 포인트를 뽑아내는 것으로 생각 할 수 있다. 본 세미나에서는 군집과 함께, 군집을 대표 할 수 있는 데이터 포인트 또는 집합을 추출하는 Exemplars Detection 연구가 소개되었다. 데이터로부터 유의미한 정보를 추출하고, 이를 바탕으로 무언가를 하려면 결국 인간이 이런 일련의 과정을 이해하고 있어야 한다. Exemplars 연구는 시각화를 비롯해 인간이 데이터의 정보를 직관적으로 파악하고 활용하는데 널리 사용될 연구로 예상된다. 한편, 발표자는 기존 Exemplars Detection연구가 가정하는 One Exemplar for One Cluster 가정을 깨면서 좀 더 일반화된 연구를 선보였다. 방법이 매우 참신하여 앞으로의 연구가 기대가 된다. 추가적으로 Exemplars selection 연구가 진행된다면 연구의 완성도가 높아 질 것으로 예상한다.




이전글
다음글

(136-713) 서울시 성북구 안암로145 고려대학교 자연계캠퍼스 신공학관 211호 | TEL.02-3290-3769
고려대학교 산업경영공학과 데이터마이닝 및 품질애널리틱스 연구실. All Right Reserved. 개인정보처리방침