In this thesis we present a new fuzzy approach to cluster inherently ambiguous data whose boundaries vague and uncertain to classify. To deal with such uncertainties, a spatial homogeneity-based fuzzy c-means (SHFCM) algorithm has been proposed. The SHFCM algorithm is based on two concepts: the initialization using dominant data and the membership updating method using spatial homogeneity. Moreover, a new cluster validity index is incorporated into the SHFCM algorithm to automatically determine the number of clusters for a given data set.
The choice of initialization scheme is of importance because the optimal partitions identified by clustering algorithms may vary depending on the initial cluster centroids selected. The proposed initialization method is based on the idea that the dominant data in a given data set are likely to belong to separate clusters. The dominant data are identified using a membership model of data in conjunction with a set of reference data. Data points closest to the dominant data are selected as the initial centroids. Having selecting the initial centroids, the SHFCM algorithm iteratively improves a sequence of sets of fuzzy clusters. The SHFCM algorithm takes the relations between data and clusters into consideration on the spatial space as well as the feature space. The membership degree between a data point and a cluster is influenced by its relations between the spatial neighborhood and the cluster. The influence of neighborhood is discriminated by its homogeneity value.
The cluster validity has been used to search for the optimal number of clusters when the number of clusters is not known a priori. A new cluster validity index for the fuzzy c-means-type algorithm has been proposed. The proposed index $υ_os$ introduced two measures in terms of inter-cluster overlap and separation. The inter-cluster overlap measure indicates the degree of overlapping between fuzzy clusters. The separation measure indicates the isolation between fuzzy clusters. The proposed index $υ_os$ was defined as the ratio of the overlapping degree to the separation. A good fuzzy partition is expected to have a low degree of overlap and a larger separation distance. $υ_os$ is applied to the clustering results obtained through the SHFCM algorithm to validate the quality of the partitions. This procedure is repeated with respect to the number of clusters. Of the partitions considered, the partition with the minimum validity value $υ_os$ is produced as the optimal clustering result.
클러스터 분석은 특정한 훈련이나 학습 데이터의 활용없이 주어진 데이터에 내재된 특성을 찾아내는 기법이다. 이러한 분석 기법은 데이터에 대한 사전 정보를 필요치 않는다는 장점으로 인해, 패턴인식, 영상처리 및 데이터마이닝 분야를 비롯해 최근에는 바이오정보학 분야까지 널리 활용되고 있다. 실세계에 발생하는 대부분의 클러스터링 문제는 매우 복잡한 양상을 가진다. 이는 분석의 대상이 되는 데이터가 복수개의 클러스터로 동시에 분류될 수 있기 때문이다. 특히, 인접하는 클러스터간의 경계에 위치한 데이터일 경우 분류시에 발생하는 불확실성과 애매성은 더욱 증가한다. 본 논문에서는 이와 같이 분류의 불확실성과 애매성을 가지는 데이터를 효과적으로 다룰 수 있는 퍼지 클러스터 분석 및 검증 기법을 연구한다.
퍼지 클러스터 분석 기법은 모호한 데이터를 분류할 때 클러스터에 대한 분류 정도를 신뢰도로 표현한다. 이 신뢰도 값은 퍼지 집합 이론에 기초한 소속 정도 값으로 부여된다. 일반적으로 알려진 퍼지 클러스터 분석의 과제로는 다음의 세 가지 이슈가 있다. 먼저, 클러스터의 초기 중심 값 선택의 문제로서, 선택된 초기 중심에 따라서 상이한 분석 결과가 도출될 수 있으며, 경우에 따라서는 지역해 빠질 수도 있다. 두번째 이슈로서 분석의 대상이 되는 데이터에 대한 최적 클러스터 수를 산정하는 문제를 생각해 볼 수 있다. 기존의 방법에서는 사용자에 의해 수동으로 결정되고 있다. 마지막으로 데이터의 형태나 밀집도에 큰 차이를 가지는 경우 이를 효과적으로 해결할 수 있는 방안이 필요하다. 본 연구에서는 위에서 언급한 세 가지의 이슈 중 앞선 두 가지의 문제를 해결하고자 한다.
초기 클러스터의 중심을 선택하는 것은 클러스터 분석에 있어서 매우 중요한 문제이다. 선택된 군집 중심에 따라서 상이한 분석 결과가 도출될 수 있다. 본 연구에서 제안한 방법은 주어진 데이터 중에서 다른 데이터에 비해 우세하고 유력하게 판별되는 데이터를 산정하고, 산정된 우세한 데이터를 이용해서 초기 중심 값을 선택한다. 우세한 데이터를 판별하기 위해서 참조 데이터의 개념을 도입하였으며, 각 데이터와 참조 데이터간의 소속 정도를 계산하는 모델을 제안하였다. 그리고 모호한 데이터의 효과적인 분류를 위해서 기존의 특성 공간 뿐만 아니라 기하학적 공간에서의 클러스터 소속 정도를 모델링하였다. 즉, 주어진 데이터와 클러스터간의 소속 정도 값을 계산할 때, 기하학적 공간에서 인접하는 이웃 데이터가 해당 클러스터에 대해 가지는 소속 정도 값을 반영하는 것이다. 이는 분류의 모호성을 해소하기 위해서 신뢰성있는 다량의 정보를 활용하는 접근 방식이다.
퍼지 클러스터 분석의 두번째 이슈로 제기된 최적 클러스터 수의 산정 문제는 클러스터 검증 기법을 이용하여 해결하고자 하였다. 클러스터 검증 기법은 클러스터 분석의 결과에 대해 정량적인 평가 수치를 제시한다. 따라서 클러스터 수를 다양하게 변화시키면서 클러스터 분석을 수행, 검증 및 평가하고, 이들 중 최적의 평가값을 제시하는 분할을 최적의 클러스터 분석 결과로 인식한다. 본 연구에서는 기존의 대부분의 검증 기법들이 클러스터 중심 정보에 매우 의존적인 사실에 착안하여, 퍼지 집합 이론에 기반한 새로운 방법론을 제안하였다. 제안된 방법론은 각 퍼지 클러스터를 개개의 퍼지 집합으로 간주하고, 퍼지 집합간의 중첩성 척도와 분리성 척도를 이용해 검증하였다.
본 연구에서 제안한 우세한 데이터를 이용한 초기 클러스터 중심 선택, 기하학적 공간에서의 동질성 활용 및 퍼지 이론에 기반한 클러스터 검증 기법의 우월성을 입증하기 위해서 컬러 영상 분할 문제에 적용해 기존의 방법들과 비교 실험하였다. 컬러 영상 분할 문제는 컬러간 경계의 불확실성으로 인해 현재까지 다양한 퍼지 클러스터 분석 기법이 연구되고 있는 분야이다. 클러스터 검증 기법을 이용하여 최적의 컬러 클러스터 수를 자동적으로 산정하고, 이를 기반으로 비교 대상이 되는 다양한 클러스터 기법을 비교 실험해 보았다. 실험 결과를 살펴보면, 본 연구에서 제안된 퍼지 클러스터 분석 및 검증 기법이 다른 방법론에 비해 효과적이며 안정적인 결과를 제시함을 알 수 있었다.
