2009/11/07 15:37

Sammon's Stress

Sammon mapping
Suppose that we consider a set of n objects. Each object is represented by one point in an m-dimensional (high-dimensional) space. The aim of Sammon mapping is to find n points in a d-dimensional space (with d < m), in such a way that the corresponding distances approximate the original ones as well as possible. We denote:

d_ij, $\forall \,i,j=1,\ldots,n$ - the distance between two points in a d-dimensional space.

$\delta_{ij}$ , $\forall \,i,j=1,\ldots,n$ - the distance between two points in an m-dimensional space.

Without loss of generality, only projections onto a 2-dimensional space are studied (d=2), since our interest is in data visualization.
There is a need for a criterion to decide whether one configuration is better than another. For that purpose, the error (stress) function E is considered, which measures the difference between the present configuration of n points in the d-dimensional space and the configuration of n points in the original m-dimensional space. The stress is given by the following formula:

$\begin{displaymath}E = \frac{1}{\sum_{i=1}^{n-1} \sum_{j=i+1}^n \delta_{ij}} \, ... ...1} \sum_{j=i+1}^n \frac{(\delta_{ij} - d_{ij})^2}{\delta_{ij}} \end{displaymath}$

and yields in fact a badness-of-fit measure for the entire representation. The stress range is [0,1] with 0 indicating a lossless mapping.

고차원의 데이터를 낮은 차원으로 매핑하여 보여주는 방법으로는 PCA, MDS등의 기법등이 있는데, 이번에 MDS에 관련한 연구를 진행하면서 알게된 에러 measure이다. 기존에는 저차원으로 매핑된 결과들에 대해서 결과내 점들에 가능한 모든 조합에 대해 유클리드 거리를 계산하고 이를 이용하여 CPU를 통해서 얻은 결과와 새로이 제안하는 방법으로 얻은 결과간에 피어슨 상관계수를 계산하여 그 유사도를 측정하였는데, 이번에 KCC에 논문을 내면서 심사위원이 Sammon's Stress를 사용하면 더욱 그 결과가 명확해질 것 같다는 코멘트를 남겨주었다.

Sammon Stress는 MDS기법 중에 하나인 Sammon mapping에서 사용하는 에러 measure로서, 고차원에서의 객체들간의 거리를 저차원에 매핑한 결과가 얼마나 잘 유지하고 있는지를 측정하는 방법이 되겠다. 측정방법은 아래와 같다.

d_ij : 낮은 차원에 매핑되어진 객체들간의 유클리드 거리

$\delta_{ij}$ : 고차원에서의 객체들간의 유클리드 거리

위의 두가지의 거리를 가지고 아래의 수식에 따라 Stress 값을 측정하게 된다.

$\begin{displaymath}E = \frac{1}{\sum_{i=1}^{n-1} \sum_{j=i+1}^n \delta_{ij}} \, ... ...1} \sum_{j=i+1}^n \frac{(\delta_{ij} - d_{ij})^2}{\delta_{ij}} \end{displaymath}$

고차원에서의 객체들간의 거리와 해당 객체들의 낮은 차원에서의 거리를 뺀 결과를 제곱한 결과

를 낮은 차원에서의 객체 거리로 나눠준다. 이렇게 모든 객체들간의 조합에 대하여 값을 계산한

다음 모두 더해준다. 모두 더해준 결과를 다시 낮은 차원에서의 객체들간의 거리를 모두 합산한

결과로 나누어주게 된다.

이때 E가 가질 수 있는 값의 범위는 [0,1]로 0에 가까울 수록 손실이 적은 결과가 되겠다.

출처 : http://www.qi.tnw.tudelft.nl/Research/neural/feature_extraction/papers/asci99b/node2.html

'Machine Learning' 카테고리의 다른 글

PCA(Principal Components Analysis) (0)	2009/11/13
Hamming Distance (0)	2009/11/11
Sammon's Stress (0)	2009/11/07
MNIST parser (0)	2009/10/20
참고하면 좋을 블로그 (0)	2009/10/01
Dendrogram (0)	2009/09/07