Markov-K-means

K-means that stops once the only work left is a handful of boundary points changing cluster, then finishes the run with Markov chains: the path of each center tells where it is heading, and each undecided point's label history tells how it splits between clusters.

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.pseudo_centers_            # where each center was heading (long-run mean of its path)
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 and the recent positions of the centers 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, two kinds of Markov chains finish the run.

1. The centers' chains give pseudo representatives. Each center's recent path is read as a chain that keeps stepping the same way. Its long-run position is where a converging center is heading, or the middle of a center that only jitters. Every point is then assigned to its nearest pseudo representative. This moves, right away, the points that are about to cross a boundary but have not moved yet, which no label history can see. The new labels are kept only if they fit the data at least as well as the old ones.

2. The labels' chains settle the undecided points. The undecided points are those that changed cluster in the window, plus those the pseudo representatives just moved. Each gets a membership from its own label history:

When the monitor diagnoses an oscillation, every point that changed in the window gets its share of time. Hard labels come from the pseudo representatives; if their labels were not kept, from the larger share.

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. Most labels that are still wrong at a stop belong to points that have not started to move, so their label histories say nothing: settling from the histories alone (green) gives the same labels as stopping and keeping them. The pseudo representatives (blue) see where the centers are heading and move part of those points in advance, so the blue line runs below the others at every stop.

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 leaves fewer wrong labels than keeping the current ones, and the gap widens as the run goes on. Averaging the jittering centers adds a little more. 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, and with 1/count mini-batch when a precise answer is needed. On exact Lloyd it costs slightly more than a threshold tuned for the data. The pseudo representatives lower the error at each stop on exact Lloyd too, but there the error jumps between stops are larger than the gain, so the curve barely moves.

On real satellite images

Twelve Sentinel-2 scenes from very different landscapes, each with about thirty million pixels, were clustered with exact K-means until no pixel changed. Every stopping rule was judged on the same run.

The tail is real on satellite images, and the right number of iterations varies so much between scenes that no fixed setting reaches the converged map everywhere. Markov-K-means is the only rule that gets there in every scene without tuning. Almost every pixel still wrong at its stop had not started to move, which is exactly what the pseudo representatives are for: nearly all the pixels they move end where the converged run puts them. The time saved is moderate, because late iterations on low-dimensional imagery are already cheap. The undecided list and soft memberships carry little information here: the scenes settle by drift, and a simple distance ratio flags mixed pixels better.

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

• Most of the error left after a drift comes from points that look settled at the stop but would move later. The pseudo representatives catch those on the path of a moving center; points the centers would reach only much later remain. A smaller unstable_tol stops later and leaves fewer of them.
• The extrapolation of a center is capped (rho_max). A cap set higher overshoots on exact Lloyd, so a center still far from its final position is extrapolated only part of the way.
• 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_, labels_at_stop_, and for the pseudo representatives pseudo_centers_, center_rho_, pseudo_accepted_ and predicted_moves_. 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

한국어

작동 방식

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

멈추면 두 종류의 Markov 연쇄가 실행을 마무리한다.

1. 대표점의 연쇄가 의사 대표점(pseudo representative)을 준다. 대표점마다 최근 경로를 같은 방식으로 계속 걸어가는 연쇄로 읽는다. 그 장기 위치는 수렴 중인 대표점이 향하는 곳이고, 흔들리기만 하는 대표점이면 흔들림의 한가운데다. 모든 점을 가장 가까운 의사 대표점에 다시 배정한다. 경계를 곧 넘을 참이지만 아직 움직이지 않은 점, 즉 어떤 라벨 이력도 볼 수 없는 점을 지금 옮겨 준다. 새 라벨은 데이터에 대한 적합도가 이전보다 나쁘지 않을 때만 채택한다.

2. 라벨의 연쇄가 미결정 점을 정리한다. 미결정 점은 관찰 창 안에서 군집을 바꾼 점에, 의사 대표점이 방금 옮긴 점을 더한 것이다. 각 점은 자기 라벨 이력에서 소속도를 받는다.

감시기가 진동으로 판정하면, 관찰 창 안에서 바뀐 모든 점이 머문 시간의 비율을 받는다. hard 라벨은 의사 대표점에서 오고, 의사 대표점의 라벨을 채택하지 않았으면 더 큰 비율 쪽이다.

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

exact Lloyd (왼쪽). 초반 반복이 지나면 군집을 바꾸는 점은 아주 적은데, 실행은 그 뒤로도 데이터를 여러 번 더 훑는다. Markov-K-means가 끊는 것이 이 꼬리다. 멈춘 시점에 아직 틀린 라벨은 대부분 움직이기 시작하지도 않은 점의 것이라, 라벨 이력은 아무것도 말해 주지 않는다. 이력만으로 정리하면(초록) 멈춘 시점의 라벨을 그대로 두는 것과 같다. 의사 대표점(파랑)은 대표점이 향하는 곳을 보고 그런 점의 일부를 미리 옮기므로, 어느 정지 시점에서든 파란 선이 다른 선보다 아래에 있다.

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

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

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

정리하면, 오차 한 단위를 줄이는 데 드는 시간은 진동하는 학습에서, 그리고 1/count mini-batch에서 정밀한 답이 필요할 때 Markov-K-means가 가장 적다. exact Lloyd에서는 데이터에 맞춰 조정한 임계값보다 조금 더 든다. 의사 대표점은 exact Lloyd에서도 정지 시점마다 오차를 줄이지만, 정지 시점 사이의 오차 차이가 그보다 커서 곡선은 거의 그대로다.

실제 위성영상에서

지형이 전혀 다른 Sentinel-2 장면 12개(장면마다 화소 약 3천만 개)를 라벨이 하나도 바뀌지 않을 때까지 exact K-means로 군집하고, 같은 실행 위에서 정지 규칙들을 판정했다.

위성영상에도 꼬리가 분명히 있고, 알맞은 반복 수가 장면마다 크게 달라서 고정된 설정 하나로는 모든 장면에서 수렴 결과에 닿지 못한다. 조정 없이 모든 장면에서 그곳에 닿는 규칙은 Markov-K-means뿐이다. 멈춘 시점에 아직 틀린 화소는 거의 모두 움직이기 시작하지도 않은 화소였고, 의사 대표점이 바로 그런 화소를 위한 것이다. 의사 대표점이 옮긴 화소는 거의 모두 수렴한 실행이 두는 곳으로 갔다. 저차원 영상에서는 늦은 반복이 원래 싸서 절약되는 시간은 크지 않다. 미결정 목록과 soft 소속도는 여기서 정보가 거의 없다. 장면들이 표류 후 정착하는 체제여서, 혼합 화소는 단순한 거리 비가 더 잘 가려낸다.

적용 가능한 알고리즘

그 밖의 반복형 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을 낮추면 더 늦게 멈추는 대신 이런 점이 줄어든다.
• 대표점의 외삽에는 상한(rho_max)이 있다. 상한을 높이면 exact Lloyd에서 지나치게 외삽하므로, 최종 위치에서 아직 먼 대표점은 일부만 외삽된다.
• 새 점은 이력이 없으므로 predict가 가장 가까운 대표점을 준다.

주요 매개변수

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

더 보기

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

Apache-2.0