특정 제약 조건을 처리하려면 다양한 기술이 필요합니다. 다음과 같은 하드 및 소프트 제약 조건을 처리하는 일반 원칙 -
하드 제약 조건 처리 − 어려운 제약 조건을 처리하는 일반적인 방법은 클러스터 할당 절차에서 제약 조건을 엄격하게 고려하는 것입니다. 데이터 세트와 예제에 대한 제약 조건 그룹(즉, 연결해야 함 또는 연결할 수 없음 제약 조건)이 주어지면 이러한 제약 조건을 충족하기 위해 k-평균 접근 방식을 어떻게 개발할 수 있습니까? COP-kmeans 알고리즘은 다음과 같이 작동합니다. -
필수 링크 제약 조건에 대한 슈퍼 인스턴스 생성 − must-link 제약 조건의 전이적 폐쇄를 계산할 수 있습니다. 따라서 모든 must-link 제약 조건은 등가 관계로 간주됩니다. 클로저는 하위 집합의 일부 개체가 하나의 클러스터에 할당되어야 하는 개체의 하나 또는 여러 하위 집합을 제공합니다.
이러한 하위 집합을 정의할 수 있으며 하위 집합의 일부 개체를 평균으로 대체할 수 있습니다. 슈퍼 인스턴스는 또한 정의하는 객체의 수인 가중치를 생성합니다. 이 과정을 거친 후 must-link 제약 조건이 지속적으로 충족됩니다.
수정된 k-평균 클러스터링 수행 − k-means에서는 가장 가까운 중심에 객체가 생성됩니다. 연결 불가 제약 조건을 존중할 수 있으며 k-평균의 중심 할당 프로세스를 가장 가까운 실현 가능한 중심 할당으로 변경합니다.
개체가 순서대로 센터에 할당되면 모든 단계에서 지금까지 할당이 일부 연결할 수 없는 제약 조건을 방해하지 않는지 확인할 수 있습니다. 할당이 일부 연결할 수 없는 제약 조건을 준수하도록 개체가 가장 가까운 중심에 할당됩니다.
COP-k-means는 각 단계에서 제약 조건을 위반하지 않음을 제공하므로 역추적이 필요하지 않습니다. 모든 제약 조건을 만족하는 클러스터링을 생성하기 위한 욕심쟁이 알고리즘으로 제약 조건 간에 충돌이 발생하지 않도록 지원합니다.
소프트 제약 조건 처리 − 소프트 제약 조건이 있는 클러스터링은 최적화 문제입니다. 클러스터링이 소프트 제약 조건을 방해하면 클러스터링에 페널티가 필요합니다. 따라서 클러스터링의 최적화 목표는 클러스터링 측면을 최적화하고 제약 조건 위반 패널티를 최소화하는 것과 같은 두 부분을 포함합니다. 객관적인 서비스는 클러스터링 품질 점수와 패널티 점수의 집합입니다.
예제에 대한 데이터 세트와 일련의 소프트 제약 조건이 주어지면 CVQE(Constrained Vector Quantization Error) 알고리즘 전략은 제약 조건 위반 페널티를 적용하면서 클러스터링을 의미합니다. CVQE에 사용된 목적 함수는 k-평균에 사용된 거리의 총계로, 제약 조건 위반 패널티로 수정되며 다음과 같이 계산됩니다. -
필수 링크 위반에 대한 처벌 − 객체 x 및 y에 필수 링크 제약 조건이 있지만 두 개의 다중 중심에 생성되는 경우 c1 및 c2 , 따라서 제약 조건이 위반됩니다. 결과적으로 dist(c1 ,c2 ), c1 사이의 거리 및 c2 , 벌칙으로 목적 함수에 삽입됩니다.
연결 불가 위반에 대한 처벌 − 객체 x 및 y에 연결할 수 없는 제약이 있지만 공통 중심 c에 생성되므로 제약이 위반됩니다. 거리, 거리(c,c ' ), c와 c ' 사이 벌칙으로 목적 함수에 삽입됩니다.