여기서는 sublabel을 Lloyd's algorithm을 활용해서 부여할 것이다.
- Seth Lloyd가 아니다. K-means 자체는 이미 몇번을 반복해야 하는지에 대해서 NP-hard임이 증명되어 있지만, 그 반복수를 조금 줄이는 방법이 있다. 그것이 Lloyd's algorithm이다.
각 클러스터에 대해서 mean point가 하나씩 있다고 가정하자. 이때 각 데이터에 대한 트레이닝 벡터를 이 mean point에 하나씩 대응 시킨다.
하지만 로이드 알고리즘에서 나온 결과는 직접 우리 알고리즘에 적용하지는 못한다. Sublabel 중복이나 다음 iteration에서 새로 분포를 만들 수 있을 정도로 sublabel이 충분하지 않을 수도 있기 때문.
이 문제를 해결하기 위해서 여기서는 2개의 추가 알고리즘을 제시한다.
1) 너무 많은 sublabel을 부여하는 것을 막아주는 알고리즘
2) 각 sublabel 간 겹치는 부분이 없도록 해주는 알고리즘
다음과 같은 랜덤한 양자 상태가 있다고 하자.
데이터가 라고 표현될 때, 는 각각 다음과 같이 인코딩 된다.
이때 여기서 는 모든 데이터들에 대해서 첫 번째 애트리뷰트만을 고려했을 때 그 중 최대값을 말한다.
즉, 양자상태 가 갖고 있는 정보들은 번째 데이터 포인트가 갖고 있는 2개의 애트리뷰트가 에 각각 위 식대로 한번 가공해서 들어간 정보들이다.
이제 이렇게 구해진 여러 개에 대해서 거리를 구할 것이다. 당연하지만 inner product가 사용될 것이다.
데이터 인코딩에는 다음과 같은 회로가 사용될 것이다.
유니터리 행렬의 곱셈은 교환법칙이 성립하지 않는다. 따라서 '돌렸다가 다시 되돌리는 것' 같은 위 회로도 사실은 다시 되돌리는 것이 아니다.
이렇게 만든 , 에 대해서 서로 inner product를 구하는 것이 전체 알고리즘의 중요한 서브 루틴 중 하나이다.