Czy istnieją przypadki, w których nie ma optymalnej wartości k w średnich?

To było w mojej głowie przez co najmniej kilka godzin. Próbowałem znaleźć optymalne k dla danych wyjściowych z algorytmu k-średnich (z metryką podobieństwa kosinusowego ), więc skończyłem na wykreślaniu zniekształcenia w funkcji liczby klastrów. Mój zestaw danych to zbiór 800 dokumentów w 600-wymiarowej przestrzeni.

Z tego, co rozumiem, znalezienie punktu kolana lub łokcia na tej krzywej powinno mi powiedzieć co najmniej w przybliżeniu liczbę skupień, w których muszę umieścić moje dane. Umieszczam poniższy wykres. Punkt, w którym narysowano czerwoną pionową linię, uzyskano za pomocą testu maksymalnej drugiej pochodnej . Po wykonaniu tego wszystkiego utknąłem w czymś znacznie prostszym: co ten wykres mówi mi o zbiorze danych?

Czy mówi mi, że nie warto grupować i że w moich dokumentach brakuje struktury, lub że muszę ustawić bardzo wysoką wartość k? Jedną dziwną rzeczą jest to, że nawet przy niskim k widzę podobne dokumenty w klastrze, więc nie jestem pewien, dlaczego otrzymuję tę krzywą. jakieś pomysły?

W większości sytuacji pomyślałbym, że dsuch wykres zasadniczo oznacza, że ​​w danych nie ma struktury klastrowej. Jednak grupowanie w bardzo duże wymiary, takie jak to, jest trudne, ponieważ w przypadku metryki odległości euklidesowej wszystkie odległości wydają się być takie same, jak rośnie liczba wymiarów. Zobacz tę stronę Wikipedii, aby znaleźć odniesienia do niektórych artykułów na ten temat. Krótko mówiąc, może to być po prostu wielowymiarowość zbioru danych, który jest problemem.

Jest to w istocie „klątwa wymiarowości”, patrz także ta strona Wikipedii.

Artykuł, który może być interesujący, to Sanguinetti, G., „Redukcja wymiarów klastrowanych zestawów danych”, Transakcje IEEE dotyczące analizy wzorców i inteligencji maszyn, vol. 30 nie 3, s. 535–540, marzec 2008 r. ( Www ). Jest to trochę jak nienadzorowana wersja LDA, która poszukuje niskiego wymiaru, który podkreśla strukturę klastra. Być może mógłbyś użyć tego jako metody wyodrębniania funkcji przed wykonaniem k-średnich?

Jak dokładnie używasz podobieństwa cosinus? Czy to jest określane mianem sferycznych K-środków? Twój zestaw danych jest dość mały, więc spróbuję go wyobrazić jako sieć. W tym celu naturalne jest zastosowanie podobieństwa (w rzeczy samej, na przykład podobieństwa cosinusowego lub korelacji Pearsona), zastosowanie granicy (rozważ tylko relacje powyżej pewnego podobieństwa) i zobacz wynik jako sieć np. W Cytoscape lub BioLayout . Może to być bardzo pomocne, aby poznać dane. Po drugie, obliczyłbym wartości osobliwe dla macierzy danych lub wartości własne odpowiednio transformowanej i znormalizowanej macierzy (macierz dokument-dokument uzyskana w jakiejś formie). Struktura skupień powinna (ponownie) pojawić się jako skok na uporządkowanej liście wartości własnych lub wartości pojedynczych.

Zasadniczo tak, k-średnie mogą zbiegać się w bardzo różne rozwiązania, które można by uznać za nieodpowiednie. Dzieje się tak w szczególności w przypadku klastrów o nieregularnych kształtach.

Aby uzyskać więcej intuicji, możesz także wypróbować inne podejście do wizualizacji: w przypadku k-średnich możesz wizualizować kilka przebiegów za pomocą k-średnich za pomocą Graphgrams (patrz pakiet graficzny WEKA - najlepiej uzyskany przez menedżera pakietów lub tutaj . Wprowadzenie i przykłady mogą być również znaleziono tutaj .

Jeśli dobrze rozumiem wykres, jest to wykres liczby klastrów, K na osi x i odległości wewnątrz klastrów na osi y?

Ponieważ twoją funkcją celu K-średnich jest zminimalizowanie WCSS, fabuła ta powinna zawsze monotonicznie zmniejszać się. W miarę dodawania kolejnych klastrów odległość między punktami w klastrze zawsze będzie się zmniejszać. Jest to podstawowy problem wyboru modelu, więc musisz zastosować nieco bardziej wyrafinowane.

Być może spróbuj statystyki Gap: www-stat.stanford.edu/~tibs/ftp/gap.ps lub innych podobnych.

Co więcej, może się okazać, że K-oznacza nie jest odpowiednim narzędziem do pracy. Ile klastrów spodziewasz się znaleźć? Stosowanie reguły wariancji do zmniejszania wymiarów do grupowania nie jest właściwe. Zapoznaj się z tym dokumentem, ponieważ podczas wyświetlania na pierwszych komputerach K-1 odpowiednia metoda przetwarzania wstępnego: http://people.csail.mit.edu/gjw/papers/jcss.ps

Możesz szybko sprawdzić, czy jest to właściwe, wykreślając rzut na dwa pierwsze główne elementy. Jeśli istnieje wyraźna separacja, wówczas środki K powinny być w porządku, jeśli nie, musisz spojrzeć na coś innego. Być może podprzestrzenie K lub inne metody klastrowania podprzestrzeni. Należy pamiętać, że metody te dotyczą odległości euklidesowej. Nie jestem pewien, jak to się zmienia dla cosinusa.