Text Clustering - NMF & Mini Batch k-means
Clustering
data instances를 비슷한 것끼리 묶어서 그룹을 만드는 방법으로 같은 cluster에 속해있는 문서들이라면 해당 문서들은 서로 비슷해야 하며, 다른 cluster에 해당되는 문서들끼리는 서로 달라야 한다.
unsupervised learning의 한 방법이다.
Non-negative Matrix Factorization(NMF)
비음수 행렬 분해: 행렬을 분해하는 방법으로 모든 요소가 음수가 아닌 행렬 V를, 모든 요소가 음수가 아닌 행렬 W, H의 곱으로 분해한다.
NMF는 document clustering 에 사용할 수 있다.
Goal: V가 주어졌을 때, V ≈ WH 를 만족하는 W, H 를 구해내는 것
V의 column vector는 W의 column vector들과 H의 해당 column vector의 요소값(계수)들을 곱한 linear combination이다.
- documents clustering 입장에서는 V 가 document matrix 이다.
- 아이템(data sample)이 column에 존재하기 때문에 → term-document matrix 이다.
- 문서 Vi 의 차원이 축소되어서(dimensionality reduction) hi 로 표현된다. (hi 를 clustering에 사용하면, 각 행이 각 cluster에 해당한다고 해석!) → 즉, hi 각 요소의 값 중에서 가장 큰 값에 해당하는 cluster가 이 문서 vi 의 cluster 이다.
NMF Cost Function
V와 WH의 차이를 최소화 하게끔 만들어야 한다.
Minimize Error Function → min ||V-WH||, subject to W >= 0, H >= 0
- V : (m x n) data matrix (n개의 문서, m차원의 feature space)
- V = (v1, ..., vi, ... , vn)
- vi : (v1i, ..., vmi)T 열 벡터 (column vector / m: 요소, i: 벡터의 인덱스, T: transpose)
- W : (m x k) feature matrix
- H : (k x n) coefficient matrix
Recommender system with NMF applications
NMF 수행 후, 점수를 매기지 않은 영화에 대해 WH를 역으로 계산해서 예측할 수 있다.
Mini Batch K-means clustering
Input: 문서들의 집합, cluster의 개수 k (미리 정해둔다) / Output: 각 cluster에 할당된 document
k-means의 특성상 데이터가 많다질 수록 계산량이 크게 증가한다는 문제가 있다. 따라서 데이터가 크고 방대하다면 메모리에 데이터를 다 올리지 못하는 문제가 발생하기 때문에, 이를 해결하기 위해서 Mini batch k-means를 이용해서 업데이트를 잘라서 할 수 있다. 이 방법을 이용하면 기존의 방법보다 빠르게 최적의 해로 수렴한다.
⇒ mini batch k-means clustering은 데이터가 증가할수록(number of data), runtime이 감소한다.
