Jak testujesz implementację k-średnich?

Uwaga: zamieściłem to pytanie na Stackoverflow, ale pomyślałem, że może lepiej pasować do tej platformy.

Jak testujesz własną implementację k-średnich dla wielowymiarowych zestawów danych?

Myślałem o uruchomieniu już istniejącej implementacji (tj. Matlaba) na danych i porównaniu wyników z moim algorytmem. Wymagałoby to jednak, aby oba algorytmy działały w przybliżeniu tak samo, a mapowanie między tymi dwoma wynikami prawdopodobnie nie jest łatwe.

Czy masz lepszy pomysł?

K-średnich zawiera komponent stochastyczny, więc jest bardzo mało prawdopodobne, że otrzymasz ten sam wynik, chyba że masz dokładnie taką samą implementację i użyjesz tej samej konfiguracji początkowej. Można jednak sprawdzić, czy wyniki są zgodne ze znanymi implementacjami (nie wiem o Matlabie, ale implementacja algorytmu k-średnich w R jest dobrze wyjaśniona, patrz Hartigan i Wong, 1979 ).

Jeśli chodzi o porównanie dwóch serii wyników, nadal występuje problem z przełączaniem etykiet, jeśli ma być uruchamiany wiele razy. Ponownie, w pakiecie e1071 R jest bardzo przydatna funkcja (; matchClasses()), której można użyć do znalezienia „najlepszego” odwzorowania między dwiema kategoriami w dwustronnej tabeli klasyfikacji. Zasadniczo chodzi o zmianę kolejności wierszy, aby zmaksymalizować ich zgodność z kolumnami lub zastosować chciwe podejście i permutować wiersze i kolumny, aż suma na przekątnej (zgodność surowa) będzie maksymalna. Podany jest również współczynnik zgodności, taki jak statystyka Kappa .

Wreszcie, jeśli chodzi o test porównawczy swojej implementacji, istnieje wiele swobodnie dostępnych danych lub możesz symulować dedykowany zestaw danych (np. Poprzez model mieszanki skończonej, patrz pakiet MixSim ).

Odwzorowanie między dwoma zestawami wyników jest łatwe do obliczenia, ponieważ informacje uzyskane w teście mogą być reprezentowane jako zbiór trzech krotek: pierwszy składnik to (wielowymiarowy) punkt, drugi to (dowolna) etykieta klastra dostarczany przez algorytm, a trzeci to (dowolna) etykieta klastra dostarczana przez algorytm referencyjny. Skonstruuj na $k$$k$tabela klasyfikacji dla par etykiet: jeśli wyniki się zgadzają, będzie to wielokrotność macierzy permutacji. Oznacza to, że każdy wiersz i każda kolumna musi mieć dokładnie jedną niezerową komórkę. To prosta kontrola do zaprogramowania. Łatwo jest również śledzić niewielkie odchylenia od tego idealnego powrotu do poszczególnych punktów danych, dzięki czemu można dokładnie zobaczyć, jak dwie odpowiedzi różnią się, jeśli w ogóle się różnią. Nie zawracałbym sobie głowy obliczeniem statystycznych miar zgodności: albo istnieje idealna zgodność (aż do permutacji), albo jej nie ma, aw tym drugim przypadku musisz wyśledzić wszystkie punkty niezgody, aby zrozumieć, jak one występują. Wyniki albo się zgadzają, albo nie; każda różnica zdań, nawet w jednym punkcie, wymaga sprawdzenia.

Możesz użyć kilku rodzajów zestawów danych do testowania: (1) opublikowanych zestawów danych z opublikowanymi wynikami k-średnich; (2) syntetyczne zestawy danych z oczywistymi silnymi klastrami; (3) syntetyczne zestawy danych bez oczywistego grupowania. (1) jest dobrym dyscyplina w użyciu, gdy piszesz dowolny program matematyki lub statystyki. (2) jest łatwy do zrobienia na wiele sposobów, na przykład poprzez generowanie niektórych losowych punktów służących jako centra skupień, a następnie generowanie chmur punktów przez losowe przemieszczanie centrów skupień stosunkowo niewielkich ilości. (3) zapewnia losowe kontrole, które potencjalnie mogą wykryć nieoczekiwane zachowania; znowu jest to dobra ogólna dyscyplina testowania.

Ponadto rozważ utworzenie zestawów danych, które podkreślają algorytm, leżąc na granicy między ekstremalnymi rozwiązaniami. Będzie to wymagało kreatywności i głębokiego zrozumienia twojego algorytmu (który prawdopodobnie masz!). Jednym z przykładów, które chciałbym sprawdzić w każdym przypadku, byłyby zbiory wektorów postaci gdzie v jest wektorem bez składników zerowych i i przyjmuje sekwencyjne wartości całkowite 0 , 1 , 2 , … , n - 1 . Chciałbym również sprawdzić algorytm na zestawach wektorów, które tworzą wielokąty równoboczne. W obu przypadkach przypadki, w których n nie jest$i \mathbb{v}$$\mathbb{v}$$i$$0, 1, 2, \ldots, n-1$$n$wielokrotność jest szczególnie interesująca, w tym gdzie n jest mniejsze niż k . Wspólne dla tych sytuacji jest to, że (a) wykorzystują wszystkie wymiary problemu, ale (b) prawidłowe rozwiązania są geometrycznie oczywiste i (c) istnieje wiele poprawnych rozwiązań.$k$$n$$k$

(Twórz losowe wielokąty równoboczne w wymiarach , zaczynając od dwóch niezerowych wektorów u i v wybranych losowo. (Dobrym sposobem jest pozostawienie ich 2 d składowych niezależnym standardowym zmiennym normalnym.) Przeskaluj je, aby miały długość jednostkową; zadzwońmy te x oraz z . Usunąć x składnik z z za pomocą wzoru$d \ge 2$$\mathbb{u}$$\mathbb{v}$$2d$$\mathbb{x}$$\mathbb{z}$$\mathbb{x}$$\mathbb{z}$

Uzyskaj przez przeskalowanie w, aby uzyskać długość jednostki. Jeśli chcesz, równomiernie przeskaluj losowo zarówno x, jak i y . Wektory x i Y tworzą ortogonalną podstawę losowego podprzestrzeni 2d d wymiarach. Równoważny wielokąt n wierzchołków jest uzyskiwany jako zbiór cos ( 2 π k / n ) x + sin ( 2 π k / n ) y, gdy liczba całkowita k wynosi od 0 do$\mathbb{y}$$\mathbb{w}$$\mathbb{x}$$\mathbb{y}$$\mathbb{x}$$\mathbb{y}$$d$$n$$\cos(2 \pi k / n) \mathbb{x} + \sin(2 \pi k / n) \mathbb{y}$$k$$0$ )$n-1$

Jednym bardzo prostym „naiwnym” podejściem byłoby użycie prostych danych syntetycznych, ponieważ każda implementacja powinna dawać te same klastry.

Przykład w Pythonie z import numpy as np:

test_data = np.zeros((40000, 4))
test_data[0:10000, :] = 30.0
test_data[10000:20000, :] = 60.0
test_data[20000:30000, :] = 90.0
test_data[30000:, :] = 120.0

Bo n_clusters = 4powinno dać ci permutację[30, 60, 90, 120]

Ponieważ k-średnie zawiera losowo wybrane decyzje (tylko część inicjalizacyjna), myślę, że najlepszym sposobem na wypróbowanie algorytmu jest wybranie początkowych punktów i pozwolenie na ich ustalenie w algorytmie, a następnie wybranie innego kodu źródłowego algorytmu i napraw punkty w ten sam sposób. Następnie możesz naprawdę porównać wyniki.