Markov-K-means

K-means that stops once the only work left is a handful of boundary points changing cluster, and settles those points from their own label history.

English · 한국어

pip install markov-kmeans

from markov_kmeans import MarkovKMeans

mk = MarkovKMeans(n_clusters=50, random_state=0).fit(X)
mk.labels_                    # hard labels
mk.cluster_centers_           # centers
mk.unstable_indices_          # points still undecided when the run stopped
mk.membership_                # sparse (n, k): one-hot for settled points, a distribution for undecided ones
mk.stop_reason_, mk.regime_   # why it stopped; "drift" or "oscillation"

English

How it works

The base algorithm runs as usual while the recent labels of every point are kept. After each iteration a monitor asks three questions about the whole run, cheapest first. Once all three answers are quiet, the run stops.

At the stop the monitor names the regime, and every undecided point is settled from its own label history:

Where the time of a run goes

Exact Lloyd (left). After the early iterations only a tiny share of points still change cluster, yet the run goes on for many more passes over the data. That tail is what Markov-K-means cuts. Under drift, settling gives the same labels as stopping and keeping them (the two lines overlap), so the whole gain is the time saved.

Constant step (right). After a quick drop, the number of changing points stops falling. The run sits on a plateau, and the share of wrong labels barely moves however long it runs. Once on the plateau, settling the switching points from their history (dashed) leaves fewer wrong labels than keeping the current ones, and the gap widens as the run goes on. The automatic rule stops as soon as the plateau is reached. A later fixed stop (t0) with settlement buys a lower error for more time.

Time versus error, compared with other stopping rules

Each line is one stopping rule with its own setting swept. Every setting is applied unchanged to all datasets of a panel, as a user would choose it without knowing the outcome. A point gives the average error (labels that differ from the reference partition) and the average time relative to running to the end. Lower and further left is better. Circles mark the default settings.

In short, each unit of error costs Markov-K-means the least time when training oscillates. With 1/count mini-batch it costs about the same as the other rules, and on exact Lloyd slightly more than a threshold tuned for the data.

Where it applies

Other iterative hard assignments include online or streaming k-means, VQ codebook training, and k-medoids or k-modes style reassignment. Record the labels at each step and pass them in:

from markov_kmeans import assign_from_history

r = assign_from_history(history)        # history: (n_steps, n_points), oldest first
r.labels, r.dense(n_clusters), r.uncertainty

When to use it

When not to use it

Reading the soft membership

Limits

• The rule only sees what has happened so far. A point that looks settled at the stop but would move later is not caught, and most of the error left after a drift comes from such points. In the left panel above, wrong labels far outnumber changing points. A smaller unstable_tol stops later and leaves fewer of them.
• New points get the nearest center from predict, since they have no history.

Main parameters

The monitor's other thresholds are documented in the docstring; the evaluation used their defaults. assign_rule="markov" settles every undecided point by the long-run law of its label Markov chain. Diagnostics include n_iter_, stop_reason_, regime_, decision_trace_, unstable_fraction_, n_dist_, fit_seconds_ and labels_at_stop_. MarkovKMeans is a scikit-learn estimator: it passes scikit-learn's check_estimator and works with clone, Pipeline, GridSearchCV and set_output.

Further reading

• Evaluation report: methods, every number behind the figures, colour quantization and VQ codebook studies
• Prior work
• Quick start
• Citing: CITATION.cff, or "Cite this repository" on the GitHub page

한국어

작동 방식

기반 알고리즘은 평소처럼 돌고, 모든 점의 최근 라벨이 기록된다. 매 반복 뒤 감시기가 실행 전체에 대해 세 가지를 묻는다. 싼 질문부터 묻고, 셋 다 잠잠해지면 멈춘다.

멈추면 감시기가 체제를 판정하고, 미결정 점은 각자의 라벨 이력으로 정리한다.

실행 시간은 어디에 쓰이는가

exact Lloyd (왼쪽). 초반 반복이 지나면 군집을 바꾸는 점은 아주 적은데, 실행은 그 뒤로도 데이터를 여러 번 더 훑는다. Markov-K-means가 끊는 것이 이 꼬리다. 표류 체제에서는 정리 결과가 멈춘 시점의 라벨을 그대로 두는 것과 같다(두 선이 겹친다). 이득은 전부 줄어든 시간에서 나온다.

고정 학습률 (오른쪽). 초반에 빠르게 줄어든 뒤로는 바뀌는 점의 수가 더 줄지 않는다. 실행은 평탄 구간에 머물고, 틀린 라벨의 비율은 아무리 오래 돌려도 거의 그대로다. 평탄 구간에서는 오가는 점을 이력으로 정리하면(점선) 현재 라벨을 그대로 둘 때보다 틀린 라벨이 적고, 그 차이는 실행이 길어질수록 벌어진다. 자동 규칙은 평탄 구간에 들어서자마자 멈춘다. 더 늦은 고정 시점(t0)에서 멈추고 정리하면 시간을 더 쓰는 대신 오차가 더 낮아진다.

다른 정지 규칙과 비교한 시간–오차 교환

선 하나는 정지 규칙 하나다. 각 규칙의 설정값을 바꿔 가며 돌렸고, 설정 하나는 한 패널의 모든 데이터에 그대로 적용했다. 결과를 모르는 사용자가 설정을 고르는 상황을 그대로 재현한 것이다. 점의 위치는 평균 오차(기준 분할과 라벨이 다른 점의 비율)와 평균 시간(끝까지 돌린 시간 대비)이다. 아래·왼쪽일수록 좋다. 동그라미는 각 규칙의 기본 설정이다.

정리하면, 오차 한 단위를 줄이는 데 드는 시간은 진동하는 학습에서 Markov-K-means가 가장 적다. 1/count mini-batch에서는 다른 규칙과 비슷하고, exact Lloyd에서 데이터에 맞춰 조정한 임계값과 비교하면 조금 더 든다.

적용 가능한 알고리즘

그 밖의 반복형 hard 배정에는 온라인·스트리밍 k-means, VQ 코드북 학습, k-medoids·k-modes식 재배정이 있다. 매 단계의 라벨을 기록해 넘기면 된다.

from markov_kmeans import assign_from_history

r = assign_from_history(history)        # history: (단계 수, 점 수), 오래된 단계부터
r.labels, r.dense(n_clusters), r.uncertainty

이럴 때 쓰면 좋다

이럴 때는 오히려 독이 된다

soft 소속도 읽는 법

한계

• 판단은 지금까지 관찰한 것만으로 내린다. 멈출 때 자리 잡은 듯 보였다가 나중에 옮겨 갈 점은 잡지 못하고, 표류 뒤 남는 오차는 대부분 이런 점에서 나온다. 위 왼쪽 그림에서 틀린 라벨이 바뀌는 점보다 훨씬 많은 이유다. unstable_tol을 낮추면 더 늦게 멈추는 대신 이런 점이 줄어든다.
• 새 점은 이력이 없으므로 predict가 가장 가까운 대표점을 준다.

주요 매개변수

감시기의 나머지 임계값은 docstring에 정리되어 있고, 평가는 모두 기본값으로 했다. assign_rule="markov"는 모든 미결정 점을 라벨 Markov 연쇄의 장기 분포로 정리한다. 진단 속성으로 n_iter_, stop_reason_, regime_, decision_trace_, unstable_fraction_, n_dist_, fit_seconds_, labels_at_stop_이 있다. MarkovKMeans는 scikit-learn 추정기다. scikit-learn의 check_estimator를 통과하고 clone, Pipeline, GridSearchCV, set_output과 함께 쓸 수 있다.

더 보기

• 평가 보고서: 방법, 그림 뒤의 모든 수치, 색 양자화·VQ 코드북 실험
• 선행연구
• 빠른 시작 예제
• 인용: CITATION.cff 또는 GitHub 페이지의 "Cite this repository"

Apache-2.0