EM(Expectation-Maximization) 알고리즘은 매개변수 추정값을 찾는 데 사용할 수 있는 유명한 반복 정제 알고리즘입니다. 클러스터 평균에 따라 가장 유사한 클러스터에 객체를 생성하는 k-means 패러다임의 확장으로 간주될 수 있습니다.
EM은 소속 확률을 정의하는 가중치에 따라 클러스터에 각 객체를 생성합니다. 즉, 클러스터 간에 엄격한 경계가 없습니다. 따라서 새로운 평균은 가중치를 기반으로 평가됩니다.
EM은 조합 모델의 매개변수(집합적으로 매개변수 벡터로 정의됨)의 원래 추정치 또는 "추측"으로 시작합니다. 매개변수 벡터로 만든 혼합물 밀도와 반대로 객체를 반복적으로 다시 채점할 수 있습니다. 재기록된 개체는 매개변수 추정치를 복원하는 데 사용됩니다. 각 개체는 주어진 클러스터의 구성원인 경우 특정 속성 값 집합을 소유할 수 있는 확률을 생성했습니다. 알고리즘은 다음과 같이 표현됩니다 -
-
매개변수 벡터의 원래 추측을 만드는 데 사용할 수 있습니다. 여기에는 클러스터 평균 또는 중심을 정의하기 위해 k 개체를 무작위로 선택하고(k-평균 분할에서와 같이) 새 매개변수에 대한 추측이 포함됩니다.
-
다음 두 단계에 따라 매개변수(또는 클러스터)를 반복적으로 미세 조정할 수 있습니다. -
-
(a) 기대 단계 − 각 객체 xi를 생성하여 확률로 ck를 클러스터링할 수 있습니다.
$$P(x_{i}\epsilon C_{k})=p(C_{k}|x_{i})=\frac{p(C_{k})p(x_{i}|C_{k} )}{p(x_{i})}$$
여기서 p(xi |Ck ) =N(mk , Ek (xi )) 평균 mk 주변의 정규(즉, 가우스) 분포를 따릅니다. , 예상과 함께 Ek . 다른 용어로, 이 단계는 개체 xi의 클러스터 구성원 확률을 계산합니다. , 각 클러스터에 대해. 이러한 확률은 개체 xi에 대한 "예상" 클러스터 구성원입니다. .
-
(b) 최대화 단계 − 모델 매개변수를 재추정(또는 수정)하기 위해 위의 확률 추정이 필요할 수 있습니다. 예를 들어,
$$m_{k}=\frac{1}{n}\sum_{i=1}^{n}\frac{x_{i}P(x_{i}\epsilon C_{k})}{\sum_ {j}P(x_{i}\epsilon C_{j})}$$
이 단계는 주어진 데이터에 할당 가능성의 "최대화"입니다.
EM 알고리즘은 간단하고 실행하기 쉽습니다. 빠르게 수렴하지만 전역 최적에 도달할 수 없습니다. 특정 형태의 최적화 함수에 대해 수렴이 보장됩니다. 계산 복잡도는 d(입력 특성 수), n(항목 수) 및 t(중복 수)에서 선형입니다. 베이지안 클러스터링 기술은 클래스 조건 확률 밀도 계산을 목표로 합니다. 일반적으로 통계 커뮤니티에서 사용됩니다.
업계에서 AutoClass는 EM 알고리즘의 수정을 사용하는 유명한 베이지안 클러스터링 기술입니다. 최적의 클러스터링은 객체의 정확한 클러스터가 주어지면 객체의 속성을 예측하는 능력을 극대화합니다. AutoClass는 클러스터 수를 추정할 수도 있습니다. 다양한 영역에서 사용되어 왔으며 적외선 천문학 데이터에 따라 새로운 종류의 별을 찾을 수 있었습니다.