k-중간 군집화

k-medians clustering

통계에서 k-medians 군집화는[1][2] 군집 분석 알고리즘이다.이것은 k-평균 군집화의 변화로, 각 군집의 중심을 결정하기 위한 평균을 계산하는 대신 중앙값을 계산한다.이는 거리 측정 기준의 제곱 2-규격(k-평균이 하는 것)과 반대로 1-규격 거리 측정 기준과 관련하여 모든 클러스터에 대한 오류를 최소화하는 효과가 있다.

이것은 1-규범에 관한 k-메디아 문제와 직접적으로 관련이 있는데, 이것은 그들이 형성한 클러스터가 가장 작도록 k-중심을 찾는 문제다.공식적으로, 일련의 데이터 점 x가 주어진 경우, 각 x에서 가장 가까운 c까지의i 거리의 합을 최소화하기 위해 k 중심i c를 선택해야 한다.

이러한 방식으로 공식화된 기준 함수는 때때로 거리 제곱의 합계가 사용되는 k-평균 군집화 알고리즘에서 사용된 기준보다 더 나은 기준이다.거리 합계는 시설 위치 등의 용도에 널리 사용된다.

제안된 알고리즘은 기대(E) 단계와 최대화(M) 단계를 번갈아 사용하는 로이드식 반복을 사용하므로 기대-최대화 알고리즘이 된다.E 단계에서 모든 객체는 가장 가까운 중위수에 할당된다.M 단계에서 중위수는 각 단일 차원에 있는 중위수를 사용하여 다시 계산된다.

중간자와 중간자

중위수는 k-median 문제의 맨해튼 거리 공식에서 각 단일 차원으로 계산되므로 개별 속성은 데이터 집합(또는 데이터 집합에서 두 값의 평균)에서 나온다.이는 이산형 또는 2진수 데이터 세트에 대해 알고리즘을 더 신뢰할 수 있게 한다.대조적으로, 수단 또는 유클리드 거리 중위수의 사용은 반드시 데이터 집합에서 개별 속성을 산출하지는 않을 것이다.맨해튼 거리 공식에서도 개별 속성은 데이터 집합의 서로 다른 인스턴스로부터 나올 수 있으므로, 결과 중위수는 입력 데이터 집합의 구성원이 아닐 수 있다.

이 알고리즘은 k-medoids 알고리즘과 혼동되는 경우가 많다.단, 다변량 맨해튼 거리 중위수의 경우 단일 속성 값만 보유하는 반면, 데이터 집합의 실제 인스턴스여야 한다.따라서 실제 중위수는 여러 인스턴스의 조합이 될 수 있다.예를 들어 벡터(0,1),(1,0),(2,2)를 감안할 때 맨해튼 거리 중위수는 (1,1)로, 이는 원래 데이터에 존재하지 않기 때문에 메디오드가 될 수 없다.

소프트웨어

참고 항목

참조

  1. ^ A. K. Jain과 R. C. Dubes, 클러스터링 데이터 알고리즘.프렌티스 홀, 1988년
  2. ^ P. S. Bradley, O. L. Mangasarian, W. N. Street, "오목 최소화를 통한 클러스팅", 신경 정보 처리 시스템의 진보 9, M. C. Mozer, M. I. Jordan, T.에서.펫시, 에드.메사추세츠주 캠브리지: MIT 프레스, 1997, 페이지 368–374.