[클러스터링] k-medoid Algorism(k-중앙자 알고리즘)

k-medoid Algorism (k-중앙자 알고리즘)

클러스터링은 데이터 객체 집합을 다수의 그룹으로 쪼개는 작업을 말한다. 유사성과 비슷한 정도는 대상을 정의하는 속성 값을 통해 계산하며 주로 거리 측정법을 사용한다.

k-means는 평균값을 구하는 연산을 수행하기 때문에 잡음이나 이상치(아웃라이어)에 민감하다. 이러한 단점을 해결하기 위해 나온것이 k-medoids 알고리즘이다. k-medoids는 클러스터의 대표값으로 오브젝트의 중심점을 구하는 것이 아니라, 오브젝트 중에서 클러스터를 대표할 수 있는 가장 가까운 대표 오브젝트를 뽑는다. 대표로 뽑히지 않은 나머지 오브젝트는 가장 가까운 대표 오브젝트를 따라 해당 클러스터에 배정한다. 이러한 분할 알고리즘은 불일치의 총합을 최소화 하는 원칙에 따라 각 오브젝트 p와 p가 속한 대표 오브젝트사이의 차이를 절대오차(Absolute criterion) 기준으로 결정한다.

k-means의 경우 평균을 대표값으로 가져가기 때문에 분산을 기준으로 알고리즘이 진행되는것에 반해 k-medoid는 중앙값을 대표값으로 가져가므로 위 처럼 절대오차를 기준으로 알고리즘이 진행되게 된다.
k-medoid 알고리즘을 가장 일반적으로 실현화한 것중 대표적인것은 PAM(Partitoning Around Medoid) 알고리즘이 있다.

	# kmedoid elbow graph
	def eblow_kmd(df, n):
	centroids = []
	for k in range(1, n):
	kdata = data
	kmd = pyclust.KMedoids(n_clusters=k)
	kmd.fit(df.values)
	centroids.append(kmd.centers_)
	kdata['cluster'] = kmd.labels_
	printExcel(kdata, k, False)
	k_euclid = [cdist(df.values, cent) for cent in centroids]
	dist = [np.min(ke, axis=1) for ke in k_euclid]
	wcss = [sum(d**2) for d in dist]
	tss = sum(pdist(df.values)**2)/df.values.shape[0]
	bss = tss - wcss
	plt.plot(bss)
	plt.show()
	return bss

view raw eblow_kmd.py hosted with ❤ by GitHub

	# k-medoid clustering
	start_time = time.time()
	kmd = pyclust.KMedoids(n_clusters=4, n_trials=50)
	kmd.fit(ksample.values)
	end_time = time.time()
	# print processing time
	print('처리시간 : ', end_time - start_time)

view raw kmedoid.py hosted with ❤ by GitHub

k-means Algorism과의 비교

중앙값은 평균에 비해 이상치에 영향을 덜 받기 때문에 k-medoid가 k-means보다 안정적이다. 그러나 k-medoid 알고리즘의 경우 kmeans에 비해 계산복잡도가 훨씬 높기 때문에 훨씬 느리며 이는 비용과 직결된다. 즉 작은 데이터에서는 잘 작동하나 대규모 데이터를 다룰때는 적절하지 않다는것이다. 이를 위해 CLARA(clustering LARge Application)라 불리는 표본기반(sample-based)방법이 제시되었다. PAM이 전체 데이터를 고려하는데 반해 CLARA는 전체 중앙자를 계산한다. 데이터에서 일부 데이터만을 대표값으로 뽑아낸 후 PAM 알고리즘 방식으로 샘플안에서 최적의 중앙값을 계산한다.


<출처 : 데이터 마이닝 개념과 기법>