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

Lab. Activity

 

 

 

Lab. Activity>Seminar  

spectral clustering with autoencoder (발표자: 정영재)

작성자 관리자 작성일 2016-07-09 오전 1:13:17
내용

발표자 Summary

 

정영재
오늘은 나의 발표로, "spectral clustering with autoencoder"란 제목의 세미나를 진행하였다. spectral clustering이란 기존의 linear clustering 방법(예: k-Means)와 달리 nonlinear한 clustering을 하기 위하여 제안된 방법이다. spectral clustering은 지역적인 유사도를 계산한 후, 각 군집간의 유사도가 최소화 되는 방향으로 군집을 구분한다. 이러한 방향을 위해 사용한 지표가 Normalized Cut으로, 두 군집간의 유사도를 Normalizing한 방법으로 이상치에 영향을 적게 받는 특징이 있다. Normalized Cut을 최소화하는 방식의 계산은 계산이 어렵다(NP-Hard). 따라서 이와 근접한 성능을 내기 위하여, Similarity Matrix에 대해 Spectral Decomposition을 하고, Eigen Vector들을 특징추출(Feature)한 변수로 사용한다. 그다음 K-Means Clustering을 적용한다. 이렇게 하면 기존의 Normalized Cut을 하는 것과 유사한 성능을 내는 것이 입증되었다. Eigen Vector들의 특징으로는 Similarity Matrix를 잘 복원한다는 것이다. 하지만 Eigen Vector는 Linear Embedding이기 때문에, Nonlinear Embedding인 AutoEncoder를 사용하여 특징추출을 하면 Similarity Matrix가 더 잘 복원되고, 그 결과 Spectral Clustering의 Normalized Cut을 최소화하는 목적을 더 잘 달성할 수 있다는게, 본 세미나에서 소개한 논문의 주장이였다. 이번 세미나를 준비하면서, Spectral Clustering이란 방법에 대해 공부할 수 있었고, 전달할 수 있는 기회였다. 하지만 대략적인 개념 외에, 방법에 대한 이해를 탄탄하게 해주는 설명의 측면에서 전달력이 부족했던 것 같다. 따라서 앞으로도 계속 전달을 어떻게 할 것인지 고민해봐야겠다.​

 

 

청취자 Summary

 

유재홍
금일 세미나는 spectral clustering with autoencoder을 주제로 진행되었다. Spectral clustering은 가장 대표적인 그래프 기반의 군집화 방법론으로, 군집 간 연결성을 나타내는 Normalized cut이 최소화되는 조합을 탐색하는 방법론이다. Normalized cut을 최소화하는 조합을 찾는 문제는 NP-Hard에 해당하는 문제로 이를 효율적으로 해결하기 위해서 조합의 포함여부를 0과1이 아닌 실수해를 가질 수 있도록 Relaxation하여 해결하게된다. 이를 위해서 Spectral decomposition을 수행하여 이를 통해 도출된 eigenvector들을 바탕으로 군집을 구성하게된다. 발표자가 발표한 논문에서는 Spectral decomposition을 통해 eigenvector을 구하는 것은 유사도 행렬을 Linear embedding하는 것이므로 비선형 군집을 탐색하는데 많은 어려움이 있다고 하였고, 이를 해결하기 위하여 유사도 행렬에 대해 autoencoder를 통해 구성된 새로운 축들을 바탕으로 군집화를 수행하는 방법론을 개발하였다. 하지만, 논문의 저자가 가정한 부분이 다소 문제가 있다고 생각된다. 많은 버전의 Spectral clustering 방법론에서 그래프를 구성할 때, 비선형적인 군집에 대해서도 잘 적용될 수 있도록 하기 위하여 지역적인 패턴을 반영할 수 있는 가우시안 기반의 유사도를 계산하여 이를 바탕으로 Neighborhood 그래프를 구성하게되므로, 유사도행렬을 구하는 과정에 이미 비선형 패턴을 반영하는 과정이 포함되어있다고 생각된다. 따라서, 비선형 패턴이 이미 반영되어 있는 이러한 유사도 행렬에 대해 spectral decomposition을 적용한다고 해도 비선형 군집은 충분히 찾아진다고 생각한다. 내가 생각하기에 오히려 다른 장점으로 인해서 일반적인 spectral clustering에 비해 우수한 결과가 도출되었다고 판단되는데 autoencoder부분을 좀 더 심도있게 공부하여 어떠한 장점으로 인해 높은 성능을 보이는지를 더 공부해보고 싶다. 또한, 딥러닝 알고리즘을 활용하여 군집화 알고리즘을 개발하는 연구가 조금씩 각광을 받고 있는데, 이 분야를 연구하고 있는 연구자로써 보다 열심히 공부해야겠다는 생각이 들었다.

 

이상민
금일 세미나는 데이터의 선형적 분류가 어려운 상황에서 분류 성능(정확도)을 높이기 위한 기법연구를 소개하였다. spectral clustering은 비선형적 분류를 잘할 수 있는 대표적인 클러스터링 알고리즘이다. 이 알고리즘은 spectral decomposition을 통해 구한 similarity matrix을 기반으로 분류하게 되는데, 이 matrix에서조차 비선형적 분류 특성이 남아 있어 분류 성능을 떨어뜨릴 수 있다. 금일 소개한 논문의 실험결과에서도 이를 잘 보여주고 있는데, autoencoder로 추출한 변수에 대해 spectral clustering을 수행했을 때 분류 정확도가 13% 이상 좋아졌다는 점이 이를 말해준다. autoencoder를 차원축소(dimensionality reduction)기법으로 클러스터링 문제에 활용한 좋은 사례라 본다. 세미나 후 추가로 궁금한 점은, autoencoder로 좋은 특질에 대한 분류를 잘 했다면, 선형적 클러스터링에 잘 쓰이는 kmeans나 HC와 같은 알고리즘으로 분류해도 그 성능이 좋지 않을까 싶다.

 

손지은
nonlinear한 데이터를 클러스터링 하기위해서 autoencoder 를 사용하여 spectral 클러스터링을 한 논문을 소개하였다. 기존의 normalized cut 최소화의 어려움을 해결할 수 있는 방법으로 similarity matrix를 계산하고 spectral decomposition을 통해 feature extraction을 한 후, 이를 K-means로 군집화하는 방법이 있다. 그러나 이러한 방법은 eigen vector가 linear embedding이라는 한계점을 가진다. Tian(2014)는 sparse auto encoder를 제안하였으며 기존의 spectral clustering이나 k-means보다 매우 우수한 성능을 보였다. 단순한 아이디어라고 생각할 수 있지만 다각도로 알고리즘 특징을 생각해봄으로써 좋은 성능을 이끌어 낼 수 있던점이 인상깊었다. 즉, 보통 널리 사용되는 알고리즘에 대해서는 그냥 수동적으로 받아들이기만 할 뿐 비판적사고를 갖거나 다양한 시각으로 알고리즘의 특징을 파악하려는 노력이 부족할 수 있는데 그런 부분에서 많은 생각을 하게되는 계기가 되었다. 발표 또한 매우 간결하고 이해하기 쉽도록 진행한 점도 좋았다.

 

곽민구
금일 세미나는 군집화 알고리즘 중 하나인 Spectral clustering에 AutoEncoder를 적용한 알고리즘에 관해 진행되었다. K-means와 같은 군집화 알고리즘은 선형 분리만 가능하다는 한계점이 있으며, Spectral Clustering은 이런 한계점을 극복하고 군집을 비선형적으로 분리하기 위해 제안된 알고리즘들 중 하나이다. Spectral Clustering은 각 데이터간의 유사성을 계산해, 군집을 분리할 때 잘라지는 아크 (즉 각 data간의 similarity) 값이 최소가 되도록 분리되는 아크를 찾아내는 방법론이다. 하지만 저자는, spectral clustering에서 사용하는 eigenvector를 이용한 접근방법은 linear embedding으로 비선형적인 패턴을 가지는 데이터에서는 non-linear embedding을 사용하는 autoencoder보다 성능이 낮다고 주장하며, autoencoder를 사용하여 기존 데이터의 similarity matrix를 효과적으로 복원시켜 군집을 나누었다. 유사도 행렬의 각 열을 autoencoder의 input variable로 사용하여 높은 성능을 보여주었지만, 많은 알고리즘들 중에서 autoencoder를 사용한 이유와 높은 성능이 나온 이유에 대하여 설명이 부족한 점이 아쉬웠다.

 

이한규
k-means clustering은 대표적인 clustering 방법이나 군집을 linear하게 분리하는 특성을 갖는다 예를 들어 이미지를 군집화 하는 상황에서는 이러한 특징은 오히려 부적절한 clustering방법이라 할 수 있다. nonlinear한 데이터 군집화를 위해 spectral clustering 기법 그중에서도 auto encoder를 활용한 군집화 기법에 대해 논의하였다. 해당 분야에 대해서는 잘 모르지만 기존 spectral clustering은 네트워크 분석에서 사용되는 방법이 주된 부분을 차지하는것 같다. 정희된 유사도를 통해 네트워크 구성 이후 MinCut 방식과 유사한 방법으로 데이터를 군집화 한다 그러나 적절한 MinCut 지점을 찾는것은 매우 어려운 방법으로 이와 유사한 효과를 내면서 쉬운 접근 방법을 제안하였다. 유사도 행렬에서 각 열을 feature로 하여 auto encoder를 사용하여 변수 추출이후 이를 통해 k-means 군집화 방법을 적용하였다. 군집화에 대해 전문적으로 파고들지 않아서 이렇게 접근하는 것이 얼마큼 좋은지는 정확히 잘 모르겠다. 그러나 유사도 행렬에서 각 열을 변수로 사용하여 군집화를 진행한 방법은 나중에 기회가 된다면 적용해볼 수 있을 것이란 생각이 들었다.

 

강성현
금일 소개된 연구는 기존의 spectral clustering에 autoencoder 방법을 접목하여 clustering 성능을 향상시킨 연구이다. spectral clustering은 그래픽 이론 기반의 알고리즘으로 관측치간 유사도의 크기로 연결된 네트워크에서 cut(cluster를 나누기 위해 제거하는 연결값의 누적합)을 최소화하는 연결을 찾아 제거함으로써 군집을 나누는 방법론이다. 그러나 최소 cut를 찾는 문제는 NP Hard에 속하므로 대체 방법을 활용하게 된다. 대체 방법은 Eigen Vector Decomposition(EDA) 후 K-mean를 적용하는 방법이며 최소 cut를 찾는 문제와 매우 유사한 결과가 나오는 것으로 증명되어 있다. 금일 소개된 방식은 기존 EDA 대신 Autoencode를 활용하여 비선형 패턴을 반영함으로써 기존 방법론보다 더욱 향상된 성능이 측정된 것을 알 수 있다. 최근 딥러닝에 대한 세미나가 수 주간 지속되고 있으며 활용 범위도 매우 광범위해짐을 실감한다. 상이한 개발환경으로 인해 딥러닝을 공부하는 것에 주저함이 있었는데 더이상 미룰 수 없음을 강하게 느낀다.

 

박찬희
Clustering은 대표적인 unsupervised learning 중 하나로 데이터를 군집화 시키는데 이용된다. 데이터가 hypersphere 형태로 분포되어 있을 때, 각 hypersphere의 중심점을 찾을 수 있는 k-means 기법이 널리 이용된다. Spectral clustering 데이터가 sphere가 아닌 비선형적 분포를 가지고 있을때 적용할 수 있는 기법이다. Spectral clustering은 spectral decomposition을 기반으로 유사도가 가장 낮은 노드간의 연결을 분리하여 군집을 만든다. Spectral decomposition은 linear embedding 기법인 feature extraction으로 이해될 수 있다. k-means가 가진 한계를 극복하기 위해 다양한 kernel k-means 기법들이 제안되었는데, spectral decomposition도 그중 하나이다.  딥러닝의 pretraining에 이용되는 autoencoder는 비선형적 분포를 가지는 데이터의 특징추출에 효과적인 것으로 알려져 있다.  본 세미나에서 소개한 논문은 autoencoder로 특징추출 후 k-means를 적용하여 기존 방법에 비해 우수한 성능을 보여주는 clustering 모델을 구축하였다.

 

박성호
Spectral Clustering 알고리즘은 데이터 속에 숨어있는 비선형 패턴을 발견하는데 널리 사용되는 방법이다. Spectral Clustering은 mincut을 최소화하는 최적화 문제로 해석될 수 있는데, analytic하게 풀 수 없기 때문에 approximate한 방법으로 푼다. 이 과정에서 linear embedding 방식인 Spectral Decomposition이 진행된다. 논문의 저자는 비선형 군집을 실행하는데 있어 linear embedding 방식 보다는 비선형 방식이 더 효율적일 것이라는 가정을 세우고 이를 비선형 차원축소방법 중 하나인 autoencoder 알고리즘을 이용하여 실험적으로 증명을 하였다. 사실, 비선형에 대한 문제는 Spectral Decomposition을 진행하는 절차 보다는 앞선 laplacian matrix를 계산하는 단계에서 해결된다고 볼 수 있기 때문에 저자가 세운 가설은 논리적인 측면에서 탄탄하지 않다고 볼 수 있다. 다만, deep learning이 대두되고 있고 실제로 deep learning 모델이 이상치 등에 좀 더 강건한 결과를 보여 줄 수 있는 부분이 연구적으로 좀 더 가치가 있지 않을까 생각한다.

 

이슬기
비선형 패턴으로 데이터를 군집화 하기 위해 spectral clustering이 개발되었는데, 데이터간 유사도를 기반으로 normalized cut값이 가장 작은 것을 기준으로 군집화를 한다. 이때 normalized cut을 최소화 하는 최적화 문제가 풀리기 어렵기 때문에 spectral decomposition을 이용하여 유사한 결과를 낼 수 있는 방법이 제안되었다. 오늘 주제로 설명한 논문의 저자는 비선형 군집을 위해 autoencoder를 통한 차원축소를 진행한 후 spectral clustering을 진행하였다. autoencoder 사용에 대한 전개의 논리는 조금 부족하다고 느꼈지만, 새로운 접근을 통해 좋은 실험결과를 보여주는 것은 의미가 있다고 생각한다.

 

강현구
오늘 세미나는 autoencoder를 이용하여 spectral clustering의 군집화 성능을 높인 논문을 주제로 진행되었다. Spectral clustering은 데이터가 비선형적인 특성을 가질 때 자주 사용되며, normalized cut 방식을 통해 최적에 가까운 군집을 찾는다. 본 논문에서는 normalized cut 대신 autoencoder를 이용하였으며, 데이터의 원래 변수들이 아닌 유사도 행렬을 이용하여 개체 간의 거리를 이용했다는 점에서 눈여겨볼 만한 것 같다. 군집화 결과는 탁월하게 좋음을 알 수 있었는데, 아마도 noise에 취약한 spectral clustering의 단점을 autoencoder가 보완해주었기 때문인 것 같다. 차후에 자세한 수식을 모두 이해하기 위해서 개인적으로 공부를 더 해봐야겠다.

 

박영준
금일 세미나에서는 영재가 autoencoder를 이용한 spectral clustering 방법론에 대한 연구를 소개하였다. spectral cluster 방법론은 관측치 사이의 유사도 행렬을 기반으로 spectral decomposition을 이용하여 clustering을 수행한다. 이때 기존의 방법론에서는 spectral decomposition을 SVD를 통해 수행한다. 소개한 연구에서는 SVD 대신 autoencoder을 이용하는데 유사도 행렬을 reconstruction 할 수 있는 latent feature를 제공한다는 부분에서 공통점이 있다. 다만 autoencoder는 SVD 와는 다르게 비선형 패턴에 대해서도 좋은 부분이 있어 보다 낮은 reconstruction error를 기대할 수 있다. 본 세미나에서는 autoencoder를 사용할 때의 이점이 무엇인지 이론적/실험적 검증이 없어 다소 아쉬운 부분으로 남는다.

 

김영훈
오늘은 Autoencoder를 이용해서 Spectral Clustering 방법의 성능을 개선하는 방법에 대해서 설명을 들을 수 있었다. Spectral Clustering은 데이터의 Manifold 구조를 반영하여 Clustering을 하기 위해 고안된 방법으로 KNN Graph를 이용해서 지역적으로 가까이 있는 관측치들끼리 유사한 변수 구조를 만들 수 있는 데이터를 생성하고, 이를 SVD를 이용해서 차원 축소한 후 일반적인 군집화 알고리즘을 적용하는 방법이다. 일반적인 K-means와 같은 경우 비선형 패턴 군집화에 취약한 면모를 보인다. K-means는 군집이 원형으로 분포하고 있다는 가정을 하기 때문인데, KNN Graph 를 만들고 Spectral Decomposition 을 하게 되면 비선형적인 데이터들이 K-means를 하기 좋게 둥글게 뭉치게 되어 결과적으로 비선형 군집화가 가능해 진다. 이 Spectral Decomposition은 PCA 와도 맥을 같이 한다고 볼 수 있는데, 저자는 Autoencoder가 PCA가 드러내지 못하는 Manifold 구조를 찾을 수 있기 때문에 Spectral Decomposition을 대신했을 경우 성능이 더 좋을 것이라는 가정을 가지고 연구를 진행했고, 좋은 결과를 얻었다. 많은 데이터들 쏟아져 나오고 분석되는 상황에서 실제 데이터들이 비선형 패턴, Manifold 구조를 갖는 다는 가정이 많이 필요해지고 있는데, 관련해서 연구를 더 해보고 싶다.​




이전글
다음글

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