Top > Info > Data Mining > 2-3. 군집분석(Automatic Cluster Detection)
▷▶ 군집분석(Automatic Cluster Detection)
거대한 데이터베이스는 많은 변수와 많은 차원, 많은 복잡한 구조로 되어 있어 제일 좋은 직접적인 데이터마이닝 기법일지라도 데이터베이스로부터 의미 있는 패턴을 이끌어 낼 수 없다. 대부분의 경우, 문제는 찾을 수 있는 패턴이 없다는 것이 아니라 너무 많은 패턴이 있다는 것이다 . 이러한 데이터 베이스에서 어떤 특별한 답을 원하는 데이터마이닝을 할 때 많은 경우 단지 잡음만을 찾는다.
마케팅에서 이미 좋은 식별자로 알려진 변수로 집단을 세분하는 것을 ‘분할’이라 부른다. 많은 경우, 매우 잡음이 많은 데이터 셋이 다수의 좋은 행동을 하는 집단으로 구성되어 있다고 짐작하지만, 어떻게 그 집단을 정의 할 지에 대한 의견은 없다. 세부집단에 대해 지식이 없어서 전체를 이해할 수 없을 때 자동집단발견이 좋은 기법이 될 수 있다.
클러스터링은 비통제 학습이나 간접적인 지식발견과 같이 묘사될 수 있는 극소수의 데이터마이닝 행동중의 하나이다. 대다수의 데이터마이닝 작업에서 이미 분류된 TRAINING SET에서 시작하여 새로운 레코드를 어떻게 분류할 것인가를 예측할 수 있는 모델 개발을 시도한다. 크러스트링에서는 독립변수와 종속변수사이의 구별이나 이미 분류된 데이터 셋이 필요없는 대신에 유사한 고객들, 제품들을 대표하는 유사한 레코드들이 유사하게 행동하리라는 기대하에서 ‘크러스터’라고 하는 서로 유사한 레코드의 그룹을 찾고자 한다.
클러스터를 찾은 것이 목적이 아니기 때문에 자동집단 발견만을 사용하는 경우는 매우 드물다. 그래서 크러스터가 발견되면 크러스터의 의미를 찾기 위하여 다른 방법들이 적용된다. 클러스트링이 성공적이면, 결과는 극적으로 나타날 수 있다.
Fitting the Troops
예를 들면, 미국 군대에서 최근에 여군의 유니폼을 어떻게 다시 디자인할 것인가를 고민하고 있다고 하자. 즉, 군대의 목적은 여군들에게 잘 맞는 옷을 제공하면서도 사이즈별 차이를 어떻게 든 줄여보고 싶다고 하자. 그래서, 그들은 기존에 나와있는 무수히 많은 여성 옷을 사이즈 체계대신 특정한 신체부위를 잰 사이즈를 도입했다. 즉, 긴 body, 보통 팔 사이즈, 넓은 어깨를 가진 사람은 짧은 다리, 잘록한 허리, 큰 가슴을 가진 사람의 사이즈가 적합하다.
데이터베이스는 3000명 여성의 100가지의 측정을 담고 있다. 이러한 경우에 쓰이는 방법은 k-means 알고리즘이다. 단계를 살펴보면, 먼저 형성하고 싶은 크러스터링의 수를 결정한다 이때의 수가 바로 K-means의 K가 되는 것이다. 그리고 k개의 시드가 크러스터링의 중심이 되도록 선택되어진다. 그리고, 데이터베이스의 각각의 레코드가 그것의 가장 가까운 시드를 기반으로 하는 크러스터링 할당에 주어진다.그리고 나서 새로운 크러스터의 중심이
‘means’가 계산된다. 새로운 중심점은 원래 시드처럼 같은 자리가 아니기 때문에 어떤 레코드는 첫번째 크러스터에서 이동한다.(실제로는 크러스터의 경계가 움직이는 것이다.) 몇 번의 반복을 통해, 각각 크러스터의 중심은 새로운 유니폼의 사이즈중하나를 정의할 수 있는 측도가 된다.
THE K-MEANS METHOD
Cluster Detection 의 K-means method는 실제로 가장 보편적으로 이용되는 방법이다. 사전에 결정된 군집수 k에 기초하여 전체 데이터를 상대적으로 유사한 k개의 군집으로 구분하는 병법이다. 설명을 간단히 하기 위해 2차원의 다이어그램을 이용하여 설명한다.(실제로는 많은 차원의 환경에서 이루어진다.)
첫번째 단계에서 군집의 수 k를 정한다..
두번째 단계에서 초기 K개 군집의 중심을 선택한다.
세번째 단계에서 각 관찰치를 그 중심과 가장 가까운 거리에 있는 군집에 할당한다.
네번째 각 군집별로 그에 속하는 관찰치를 이용해 새로운 중심을 계산한다.
위의 과정을 기존의 중심과 새로운 중심의 차이가 없을 때까지 반복한다.
K-means method는 상업용 software tool과 함께 계산방식에 많은 변동을 가졌다. 즉, 초기의 시드들을 선택하는 데 있어서 또 다음 중심 값을 계산하는데 있어서 다른 방법이 적용되거나 군집과 관련한 레코드들의 거리를 계산하기 보다는 확률밀도를 이용하기도 한다.
Similarity , Association ,And Distance
k-means 알고리즘의 단계를 살펴보면, 데이터베이스의 레코드들은 일단 공간에서 점으로 메핑이 되어야 한다. 하지만 우리가 마케팅, 영업 등에서 접하는 데이터 베이스들은 그러하지 하다. 그래서 우리는 레코드를 공간의 점으로 취급하기 위해서 모든 필드를 수치형 변수로 바꾼다. 만약 두 점들이 가까이 근접해 있다면, 우리는 그 점들을 데이터베이스에서 같은 레코드라고 표현할 수 있다. 그러나 이러한 접근은 여러 형태의 변수 타입들이 벡터의 요소로 표현되기 어렵다라는 문제점을 가지고 있다.
변수의 다양성 : 범주형, 순서형, 구간형
소개할 세 가지 방법 중 처음 두개는 구간변수와 true measure에 적합하고 세 번째는 범주형 변수에 적합하다.
1. 두점들사이의 거리 측정
두 점들 사이의 거리가 연관성 측도로써 쓰인다. 두 점이 가깝다면 두 점들 사이의 상호관계가 비슷하다. 이 방법은 주로 수 변수에 주로 쓰인다.
2. 두 벡터의 각도
공간에서 X와 Y를 점으로 생각하고 그 거리를 고려하는 것 대신, 우리는 두 사이의 벡터와 각을 고려한다. 예를 들어 사자와 고양이의 이빨, 몸통, 꼬리, 수염의 길이를 재어서 그것을 점으로 표현하여 그린다면 그 점들은 서로 멀리 떨어져 있을 것이다. 하지만, 두 동물들의 위에서의 길이의 비율을 조사해 보면 둘은 비슷할 것이다. 벡터사이의 각은 두 사물이 얼마나 많이 떨어져 있냐는 것에는 영향을 받지 않는다.
K-means가 무엇인가?
모든 변수들이 독립적이라면 군집은 형성되지 않을 것이다. 또한, 그 반대라면 하나의 크러스터를 생성할 것이다. 따라서, 우리는 얼마나 많은 크러스터가 존재하는지 모른다. 이러한 경우 사전에 K의 수를 지정해 주고 군집을 하는데, 만일 군집수 K가 원 데이터구조에 적합하지 않으면 좋은 결과를 얻을 수 없다. 따라서 적절한 군집수를 택해야만 의미 있는 분석결과도 얻을 수 있을 것이다. 보통 K-means군집분석에서 군집수를 결정하는 방법은 먼저 적절한 다변량 통계분석법을 이용해 관찰치의 위치를 시각화해 이를 관찰해서 결정하는 방법이 있다. 이는 보통 주성분 분석을 통해서 변수의 수를 줄이고 이를 2차원 혹은 3차원 의 그래프를 통해서 살펴본다.
Agglomeration Methods
이 방법은 각각 소속된 군집내의 형성된 각 data점으로부터 시작해서 점차적으로 하나의 큰 군집에 모든 점이 모일 때까지 흡수하는 것이다. 이 알고리즘의 첫번째 단계는 유사성 matrix를 만들어 내는 것이다. 유사성 matrix는 점들 사이의 거리나 관련정도를 나타내는 table이다.
거리를 계산하는 데 는 세가지 방법이 있다.
Single linkage: 이 방법은 두 군집 사이에 가장 가까이 있는 점들 사이의 거리를 측정
Complete linkage: 이 방법은 두 군집 사이에 가장 멀리 있는 점들 사이의 거리를 측정
Comparison of centroids: 두 군집 사이에 중심점의 거리측정
EVALUATION CLUSTERS
K-MEANS방법을 사용할 때 우리는 가장 잘 군집을 형성하기 위해 K의 값을 결정해야 한다.이와 비슷하게 계보적 군집 방법을 이용할 때, 계층적 구조내의 어떤 단계가 가장 잘 군집을 형성하는지 검토할 필요도 있다. 그러면, 우리는 무엇을 좋은 군집이라고 할 수 있는가? 일반적으로, 우리는 그 군집내의 요소들이 높은 연관성을 갖기를 바란다. 이러한 서로의 유사성을 측정하는 가장 기본적인 방법은 분산을 이용하는 것이다. 따라서, 우리는 가장 낮은 분산을 나타내주는 군집을 형성하는 것을 목적으로 두고 있다. 그러나, 계보적 군집은 이것을 이용할 수 없기 때문에 다른 방법을 제시한다. 즉, 다음 단계에 통합되었을 때의 거리값과 그전의 값을 비교하는 방법을 적용한다.
INSIDE THE CLUSTER
만약 아주 잘된 군집을 보았을 때, 아마 그 군집안의 레코드가 어떠한지 궁금하고, 또 그것들을 하나로 묶는 원인이 무엇인지 궁금할 것이다. 더 나아가, 그 안의 패턴과 규칙이 궁금할 것이고, 데이터베이스에서 노이즈의 제거에도 궁금해 할 것이다.
첫번째 질문의 해결하기위한 간단한 방법은 군집 내에 있는 변수의 평균을 취하여 군집을 하기 전의 평균과 비교해본다. 또한 차이를 가지고 순위를 매겨보기도 한다. 차이가 많은 변수일수록 군집을 잘 설명해준다.
AUTOMATIC CLUSTER DETECTION의 장점
- Automatic Cluster Detection은 undirected knowledge discovery기법이다. 따라서 데이터에 대한 어떠한 사전적 지식을 요구하지 않는다. 또한, directed 기법의 적용을 지원하기위해 사용될 숨겨진 구조를 밝혀낸다.
- Automatic Cluster Detection는 분석을 위해서는 기본적으로 관찰치 간의 거리를 데이터형태에 맞게만 정의하면, 범주형, 수치형, textual 데이터 등 어떤 데이터에도 적용된다.
- 분석방법의 적용 용이성 : 대부분의 군집방법이 분석대상 데이터에 대해 사전정보를 거의 요구하지 않으므로 적용하는 데에 큰 어려움이 없다. 즉, 모형화를 위한 분석과 같이 사전에 특정 변수들에 대한 역할 정의가 필요하지 않고, 다만 관찰치들 사이의 거리만이 분석에 필요한 입력자료가 된다.
.
AUTOMATIC CLUSTER DETECTION의 단점
* 가중치와 거리정의 : 군집분석의 결과는 관찰치 사이의 거리 또는 유사성을 어떻게 정의하는가에 크게 좌우된다. 따라서 특히 여러 가지 자료유형(연속형, 범주형)을 포함하는 데이터의 경우, 관찰치들 사이의 거리를 정의하고 각 변수에 대한 가중치를 결정하는 것은 매우 어려운 문제다.
* 초기값에 민감 : k-means 방법에서 k에 대한 값 선택은 군집 수를 결정해 버린다. 이 k가 data구조에 적절하지 못하다면 좋지 못한 결과를 낳는다.
* 결과 해석의 어려움 : 탐색적인 분석방법으로의 장점을 가지고 있는 반면에, 사전에 주어진 목적이 없으므로 결과를 해석하는 데 있어서 어려움이 있다. 따라서 주어진 변수에 따라 잘 구분된 군집이라 하여도 그 결과를 충분히 이해하고 실제적으로 활용하기는 쉽지 않다
WHEN TO USE CLUSTERING
군집분석은 많은 변수를 가지고 있는 복잡하고 대용량의 데이터에는 잘 적용될 수 있다. 따라서 데이터마이닝을 수행하기 위한 초기 작업을 유용하지만, 이는 복잡한 데이터를 요약하는 도구일 뿐이고, 유사성을 갖는 군집내의 관찰치 들을 통한 변수들 사이의 규칙이나 패턴을 찾는 또 다른 데이터마이닝 기법을 사용하여 더욱 유용한 결과를 얻도록 노력해야 할 것이다
Top > Info > Data Mining > 2-3. 군집분석(Automatic Cluster Detection)