마이테이블

데이터 마이닝 테크닉 - 클러스터링 알고리즘 탐구

1. 유사도 정의
군집 분석에서 상사성이 높은 개체(유전자 혹은 환자)들은 같은 군집(발현 양상이 비슷한 유전자들 혹은 같은 종류의 암 환자)에 포함시키고, 상대적 상사성이 낮은 개체(발현 양상이 다르거나 다른 종류의 암 환자)들은 서로 다른 군집에 포함시킬 수 있도록 해주는 상사성이나 비상사성을 측정하는 유사도 정의가 필요 한다. 이러한 유사도 정의에 주로 사용되는 것은 거리인데 대표적으로 사용되는 거리 척도에는 Euclidean 거리이다.



한편 Euclidean 거리는 사용된 척도에 따라서 거리 순위에 상당한 영향을 미치게 된다. 이러한 문제를 극복하기 위하여 일반적으로 각 변수를 표준 편차로 나눈 표준화 변수를 사용하게 된다. 그러나 변수들 사이의 상관관계가 존재 할 때 거리는 척도의 불변성과 상관관계를 고려한 통계적 거리로 측정되어야 한다. 이러한 통계적 거리를 Mahalanobis 거리라고 한다.
한편 Euclidean 거리 이외에 개체들 간의 유사도 평가 기준으로는 pearson correlation coefficient, spearman correlation coefficient나 mutual information이 사용되기도 한다. 유사도에 대한 정의를 어떻게 했느냐가 군집의 질에 영향을 미치게 된다.

2. 계보적 군집 방법
계보적 군집 방법에는 상사성이 밀접한 개체(유전자나 암 환자)들을 단계적으로 발현 양상이 비슷한 유전자들이나 같은 종류의 암 환자들로 이루어진 군집을 형성해 나가는 병합적 방법 (agglomerative method)이 많이 사용 된다. 병합적 방법에서는 각 개체가 별개 군집을 형성하기 때문에 n개 군집에서 출발한다. 연속되는 각 단계 마다 가까운 두 개 군집들을 병합하면, 각 단계 마다 군집의 수가 하나씩 줄어든다. 따라서 마지막 단계에서는 모든 개체들이 하나의 군집을 형성하게 된다. 이러한 계보적 방법에 의한 군집 형성 결과는 이차원상의 도면에 나타낸 dendrogram 형식으로 표시될 수 있다 (그림 1).

병합적 방법으로는 두 군집 사이의 거리에 대한 정의 방법에 따라 군집 연결 방법이 달라지는데 최단 연결법, 최장 연결법, 평균 연결법, 중심 연결법 등이 있다. 최단 연결법은 우선 (NxN) 거리 행렬 D에서 우선 거리가 가장 가까운 개체가 U, V라면 두 개체를 묶어서 군집 (U V)를 형성한다. 다음 단계는 군집 (U V)와 나머지 (N-2)개의 다른 개체 중 임의의 개체 W와의 최소 거리를 다음과 같이 계산한 후
()min{,}UVWuwvwdd d =
거리 행렬에서 거리가 가장 가까운 개체와 다시 군집을 형성한다. 이러한 과정을 반복 하면 모든 개체를 포함하는 하나의 군집을 형성하게 된다.
최장 연결법은 우선 (NxN) 거리 행렬 D에서 우선 거리가 가장 가까운 개체가 U, V라면 두 개체를 묶어서 군집 (U V)를 형성한다. 다음 단계는 군집 (U V)와 나머지 (N-2)개의 다른 개체 중 임의의 개체 W와의 최대 거리를 다음과 같이 계산한 후
()max{,}UVWuwvwdd d =
거리 행렬에서 거리가 가장 가까운 개체와 다시 군집을 형성한다. 이러한 과정을 반복 하면 모든 개체를 포함하는 하나의 군집을 형성하게 된다.
평균 연결법은 우선 (NxN) 거리 행렬 D에서 우선 거리가 가장 가까운 개체가 U, V라면 두 개체를 묶어서 군집 (U V)를 형성한다. 다음 단계는 군집 (U V)와 나머지 (N-2)개의 다른 개체 중 임의의 개체 W와의 평균 거리를 다음과 같이 계산한 후 ()()ijijUVWuvwddnn=ΣΣ
거리 행렬에서 거리가 가장 가까운 개체와 다시 군집을 형성한다. 이러한 과정을 반복 하면 모든 개체를 포함하는 하나의 군집을 형성하게 된다.
중심 연결법은 두 군집 사이의 거리는 두 군집의 중심간의 거리로 계산 된다. 만약 군집 C1에 속하는 개체의 수가 N1 일 때 군집 C1의 중심은 11iiicXXn∈=Σ
이 된다. 군집 C2에 속하는 N2개체의 중심을 2X라고 하면 두 군집 사이의 거리는 122()()1212(,)CCdPXXX==−X
이 된다. 여기서 P는 근접 척도로 Euclidean 거리의 자승이 사용된다. 만약 두 군집이 결합되면 새로운 군집의 중심은 가중 평균을 이용하여 구하고 각 군집 사이의 거리를 구한후 중심 거리가 가장 가까운 개체와 다시 새로운 군집을 형성한다. 이러한 과정을 반복하면 모든 개체를 포함하는 하나의 군집을 형성하게 된다.
평균을 이용하여 구하고 각 군집 사이의 거리를 구한후 중심 거리가 가장 가까운 개체와 다시 새로운 군집을 형성한다. 이러한 과정을 반복하면 모든 개체를 포함하는 하나의 군집을 형성하게 된다.
3. 분리 군집 방법
계보적 군집 방법에서는 일단 어떤 개체가 특정한 군집에 할당되면 다른 군집에 다시 할당 될 수 없는 단점을 가지고 있다. 반면에 분리 군집 방법은 어떤 개체가 초기 할당에서 잘못 되었다 하더라도 다시 할당할 수 있는 방법이다. 이 분리 군집 방법은 미리 설정된 기준의 최적화에 근거해서 자료를 분리하게 된다. 또한 이 방법을 사용할 때에는 최종 군집의 수가 알려져 있고 또한 미리 설정될 수 있다고 가정한다.
분리군집 방법으로 가장 대표적인 k-평균 군집 방법은 다음과 같다. n개 개체(유전자나 암 환자)가 p차원 다변량 개체라고 했을 때 각 개체는 초기에 설정된 k개의 발현 양상이 비슷한 유전자들이나 같은 종류의 암 환자들로 이루어진 군집중 어느 한 군집에 할당된다고 가정하자. 이때 i번째 개체의 j번째 변수를 X(i,j)로 표시하고, c번째 군집에 속한 nc개 개체들의 j번째 변수에 대한 평균을 X(c,j)로 표시했을 때 i번째 개체와 c번째 군집 사이의 Euclidean 거리는 다음과 같이 표시 할 수 있다. 0.521(,)(,)(,)pjDicXijXcj==−Σ
또한 각 개체를 c번째 군집에 재 할당할 때 오차 자승 합 E는
[]21(,())niEDici==Σ
이 된다. 위 식에서 c(i)는 군집 c는 i번째 개체를 포함하고 있다는 것이고, D(i,c(i))는 i번째 개체와 그 개체를 포함하고 있는 군집 사이의 Euclidean 거리를 표시한다. 따라서 분리 군집 방법은 각 개체를 어느 한 군집으로부터 다른 군집으로 움직일 때 오차 자승 합을 계산하여 비교하면서 더 이상 움직일 개체가 없을 때인 오차 자승 합이 최소화 하는 곳까지 반복한다.
4. 최근 제안 되는 군집화 방법
최근 들어 많은 전산학자와 통계 학자, 생물학자들이 개인 별로 또는 팀을 형성하여 군집화 방법을 개발하고 있으며 논문들이 발표되고 있다. 대표적인 논문들에 대해서 아래의 표에 설명 했다.
논문
발표 년도  사용 기법
실험 데이터
소프트 웨어
비고
Eisen et al
1998
계층적 군집화 분석
budding yeast cell cycle
공개
Cluster와 TreeView 프로그램
Tamayo et al
1999
SOM(self organizing map)
Budding yeast cell cycle
공개
Tavazoie et al
1999
K 평균 군집화 분석
budding yeast cell cycle
공개
Ben-Dor et al
1999
CAST
공개
Biocluster 프로그램
Sharan et al
2000
CLICK
Budding yeast cell cycle
라이센스 등록후 제공
계층적 군집화 분석과 비교 결과 제시
표 1 연구 동향
Eisen등은 통계학에서 널리 쓰이는 계층적 군집화를 DNA microarray에 적용하여 좋은 연구 업적을 남겼고, 이 연구의 산출물인 Cluster 와 TreeView라는 소프트웨어는 많은 사람에 의해 사용되고 있다. 이외에도 Hartuv는 그래프 이론을 바탕으로 군집화 방법을 제안하였고. Ben-Dor와 Shamir등도 역시 그래프를 응용하여 CAST라는 방법을 제안하고 프로그램으로 구현하였다. Tamayo등은 SOM(self –organizing maps)라는 방법을 적용하였으며 이외의 다수가 현재 군집화 방법의 개발 또는 평가 논문을 제시하고 있다.
5. 군집 분석시 유의 사항
군집을 형성하는 방법에는 여러 방법이 있지만 최적 방법에 대한 기준은 명확하지 않다. 따라서 군집 분석을 할 때 유의해야 할 사항을 정리하면 다음과 같다.
하나. 만약 집단들 사이에 상당한 차이가 없다면 현실적으로 군집 분석에서 매우 명확한 결과를 기대할 수 없을 것이다. 특히 만약 개체들이 비선형 형태로 분포되어 있다면 명확한 군집들을 찾아내는 것은 어려울 것이다.
둘. 군집 분석은 이상치에 대하여 상당히 민감한 결과를 보인다. 따라서 군집 분석을 시행하기 전에 자료에 대하여 이상치 존재 여부를 살펴야 한다고 판단된다.
셋, 군집 분석에 사용될 변수들의 측정 척도가 서로 다른 경우에는 분석 전에 표준화하여야 한다.
넷, 군집의 타당성을 검토하기 위하여 두 가지 방법이 사용된다. 첫 번째 방법은 자료에 대하여 여러 가지 군집 방법을 적용한 후 그 결과들이 유사한가를 검토하는 방법이다. 두 번째 방법은 자료를 랜덤 하게 이등분하고 각각에 대하여 여러 가지 군집 방법을 실시한 후 두 개의 결과가 유사한지 여부를 검토하여 일치도가 높은 군집 방법을 선택하는 방법이다.
3. 요약 및 연구 전망
DNA microarray 실험의 일반화와 유전자를 이용한 연구의 발전으로 인하여 데이터들은 급속히 증가되고 있다. 이러한 방대한 양의 정보들을 바탕으로 의미 있는 정보를 획득하는
데 있어서는 군집화 분석이 중요한 위치를 차지하고 있다. 그래프 이론에서의 접근, 신경망을 이용한 학습 기법에서의 접근, 확률 통계학적인 접근 방식으로 여러 군집화 분석이 연구되어 왔다. 특히 계층적 군집화와 분리 군집화 분석의 경우는 단순하면서도 어느 정도 의미 있는 결과를 도출하는 알고리즘으로써 많이 활용되고 있으며 CLICK과 CLIFF는 군집화의 정확성을 더욱 높이는 결과를 가져왔다.
이 분야에 있어서 연구는 지속적인 발전이 있으리라고 본다. 생물학이라는 특수 영역에 의존된 데이터라는 특색과 유전 자수에 비해 실험 횟수는 매우 적은 특수한 환경 제약이 있기 때문에 이를 극복하기 위한 여러 가지 heuristic한 방법들이 계속해서 연구되리라고 전망된다.

마할라노비스 거리는 군집분석에서 가장 많이 사용되는 거리개념으로서, 두 지점의 단순한 거리뿐만이 아니라, 변수의 특성을 나타내는 표준편차와 상관계수가 함께 고려된다는 특징을 가지고 있다.

아래 그림과 같은 점 A,B,C 가 있다고 하자.

공분산 행렬(Covariance Matrix)은 아래와 같다라고 하자.



A, B, C 각각의 위치는 다음과 같다.
A(0.5, 0.5)
B(0, 1)
C(1.5, 1.5)


마할라노비스 거리 구하는 공식은 아래와 같다.



은 공분산 행렬의 역행렬이고, 는 변환행렬이다.



먼저, 공분산 행렬의 역행렬을 구하자. 2차 정방행렬의 역행렬 구하는 공식은 다음과 같다.

일 때, A의 역행렬 이다.

위식에 의해 공분산 행렬의 역행렬을 구하면

이다.

마할라노비스 거리 공식에 의해 A,B의 거리와 A,C의 거리를 구해보자.






유클리안 거리와 비교해서 결과가 반대로 나왔음을 알 수 있다. 즉, 상관에 따른 거리가 변할 수 있음을 나타낸다

-] a. 응집하는, 집괴성(集塊性)의.

U ① 분산; 산란(散亂), 이산.
② 〖물리·화학〗 분산; 〖광학〗 분산, 분광; 〖전자공학〗 산란, 산포[분산]도; 〖통계학〗 (평균값 따위와의) 편차; 〖군사〗 (폭탄 등의) 탄착 산포 패턴; 〖항공〗 디스퍼전(미사일 등의 예정로(路)에서의 편차); 〖의학〗 (염증 따위의) 소산(消散).
③ (the C-) 유대인의 이산(Diaspora).

① (수수께끼를 푸는) 실마리, (십자말풀이의) 열쇠, (조사·연구의) 단서.
② 이야기의 줄거리, 사색의 실마리.
③ (미궁에의) 길잡이.
④ (미국속어) 정보, 개인적인 의견. [cf.] clew.
♣get a ∼ (1) 실마리를 얻다; (미국구어) 실정을 잘 보다, 깨닫다, 꾀발라지다. (2) (미국속어) 이해되다, 알다.
♣not have a ∼ (구어) 어림이 안 잡히다, (구어) 무지[무능]하다.
 
†clue [kluː] vt. 
암시로 보여주다, (구어) ┅에게 단서를 주다, (미국속어) 털어놓다; =CLEW.
♣∼ a person in [up] (속어) 아무에게 단서를 주다, 알리다, 설명하다.
㉺∼less [-lis] ―a. 단서 없는; (구어) 어리석은, 무지한.

U,C (의견 따위의) 강요; 방해(한 일), (장소에의) 침입(into; to); 주제넘게 나섬, 〖법률〗 (무권리자의) 침입에 의한 토지 점유, (교회 소유지의) 점유횡령; 〖지질〗 (마그마의) 관입(貫入), 관입암(岩).
㉺∼al ―a. 
㉺∼ist ―n.
[관련어] intrude ―v.

직각적(直覺的)[직관적]인(능력); 직관적으로 얻은(지식·확신); 직관력이 있는(사람).
㉺∼ly ―ad.  
㉺∼ness ―n.

Origianl From : Wikipedia CORDIC

CORDIC은 "for COordinate Rotation DIgital Computer"의 약자로 1959년 Jack E. Volder에 의해 처음 개발 되었고 HP의 John Stephen Walther가 일반화 하였다.
CORDIC은 hyperbolic, trigonometric function, Exponential, Logarithms, Multiplication, Division, Square Root 등 다양한 연산을 Bit-Shift, Addition의 단순한 구조로 구현 가능하도록 하는(멀티플라이어가 필요 없는) 하드웨어에 최적화 된 알고리즘 이다.
(단 반복적인 Iteration이 요구되어 Polynomial 연산법 등에 비해 속도는 저하 될 수 있다.)

원래 CORDIC은 이진수 체계를 가지는 시스템에서 적용하기 위해 개발되었으나 1970년대에는 10진(decimal) CORDIC이 포켓 계산기에서 광범위하게 사용되기 시작하였다.(대부분  BCD코드 사용)

동작방식

CORDIC can be used to calculate a number of different functions. This explanation shows how to use CORDIC in rotation mode to calculate sine and cosine of an angle, and assumes the desired angle is given in radians and represented in a fixed point format. To determine the sine or cosine for an angle β, the y or x coordinate of a point on the unit circle corresponding to the desired angle must be found. Using CORDIC, we would start with the vector v₀:

In the first iteration, this vector would be rotated 45° counterclockwise to get the vector v₁. Successive iterations will rotate the vector in one or the other direction by size decreasing steps, until the desired angle has been achieved. Step i size is Artg(1/(2^(i-1))) where i 1,2,3,….

More formally, every iteration calculates a rotation, which is performed by multiplying the vector v_{i − 1} with the rotation matrix R_i:

The rotation matrix R is given by:

Using the following two trigonometric identities

the rotation matrix becomes:

The expression for the rotated vector v_i = R_iv_{i − 1} then becomes:

where x_{i − 1} and y_{i − 1} are the components of v_{i − 1}. Restricting the angles γ_i so that tanγ_i takes on the values the multiplication with the tangent can be replaced by a division by a power of two, which is efficiently done in digital computer hardware using a bit shift. The expression then becomes:

where

and σ_i can have the values of −1 or 1 and is used to determine the direction of the rotation: if the angle β_i is positive then σ_i is 1, otherwise it is −1.

We can ignore K_i in the iterative process and then apply it afterward by a scaling factor:

which is calculated in advance and stored in a table, or as a single constant if the number of iterations is fixed. This correction could also be made in advance, by scaling v₀ and hence saving a multiplication. Additionally it can be noted that

^[3]

to allow further reduction of the algorithm's complexity. After a sufficient number of iterations, the vector's angle will be close to the wanted angle β. For most ordinary purposes, 40 iterations (n = 40) is sufficient to obtain the correct result to the 10th decimal place.

The only task left is to determine if the rotation should be clockwise or counterclockwise at every iteration (choosing the value of σ). This is done by keeping track of how much we rotated at every iteration and subtracting that from the wanted angle, and then checking if β_{n + 1} is positive and we need to rotate clockwise or if it is negative we must rotate counterclockwise in order to get closer to the wanted angle β.

The values of γ_n must also be precomputed and stored. But for small angles, arctan(γ_n) = γ_n in fixed point representation, reducing table size.

As can be seen in the illustration above, the sine of the angle β is the y coordinate of the final vector v_n, while the x coordinate is the cosine value.

소프트웨어 구현 :
The following is a MATLAB/GNU Octave implementation of CORDIC that does not rely on any transcendental functions except in the precomputation of tables. If the number of iterations n is predetermined, then the second table can be replaced by a single constant. The two-by-two matrix multiplication represents a pair of simple shifts and adds. With MATLAB's standard double-precision arithmetic and "format long" printout, the results increase in accuracy for n up to about 48.

function v = cordic(beta,n)
% This function computes v = [cos(beta), sin(beta)] (beta in radians)
% using n iterations. Increasing n will increase the precision.

if beta < -pi/2 || beta > pi/2
    if beta < 0
        v = cordic(beta + pi, n);
    else
        v = cordic(beta - pi, n);
    end
    v = -v; % flip the sign for second or third quadrant
    return
end

% Initialization of tables of constants used by CORDIC
% need a table of arctangents of negative powers of two, in radians:
% angles = atan(2.^-(0:27));
angles =  [  ...
    0.78539816339745   0.46364760900081   0.24497866312686   0.12435499454676 ...
    0.06241880999596   0.03123983343027   0.01562372862048   0.00781234106010 ...
    0.00390623013197   0.00195312251648   0.00097656218956   0.00048828121119 ...
    0.00024414062015   0.00012207031189   0.00006103515617   0.00003051757812 ...
    0.00001525878906   0.00000762939453   0.00000381469727   0.00000190734863 ...
    0.00000095367432   0.00000047683716   0.00000023841858   0.00000011920929 ...
    0.00000005960464   0.00000002980232   0.00000001490116   0.00000000745058 ];
% and a table of products of reciprocal lengths of vectors [1, 2^-j]:
Kvalues = [ ...
    0.70710678118655   0.63245553203368   0.61357199107790   0.60883391251775 ...
    0.60764825625617   0.60735177014130   0.60727764409353   0.60725911229889 ...
    0.60725447933256   0.60725332108988   0.60725303152913   0.60725295913894 ...
    0.60725294104140   0.60725293651701   0.60725293538591   0.60725293510314 ...
    0.60725293503245   0.60725293501477   0.60725293501035   0.60725293500925 ...
    0.60725293500897   0.60725293500890   0.60725293500889   0.60725293500888 ];
Kn = Kvalues(min(n, length(Kvalues)));

% Initialize loop variables:
v = [1;0]; % start with 2-vector cosine and sine of zero
poweroftwo = 1;
angle = angles(1);

% Iterations
for j = 0:n-1;
    if beta < 0
        sigma = -1;
    else
        sigma = 1;
    end
    factor = sigma * poweroftwo;
    R = [1, -factor; factor, 1];
    v = R * v; % 2-by-2 matrix multiply
    beta = beta - sigma * angle; % update the remaining angle
    poweroftwo = poweroftwo / 2;
    % update the angle from table, or eventually by just dividing by two
    if j+2 > length(angles)
        angle = angle / 2;
    else
        angle = angles(j+2);
    end
end

% Adjust length of output vector to be [cos(beta), sin(beta)]:
v = v * Kn;
return