Jakiego algorytmu należy użyć, aby zgrupować ogromny binarny zestaw danych w kilka kategorii?

11

Mam dużą (650K wierszy * 62 kolumny) macierz danych binarnych (tylko wpisy 0-1). Matryca jest w większości rzadka: około 8% jest wypełnione.

Chciałbym podzielić go na 5 grup - powiedzmy nazwanych od 1 do 5. Próbowałem zgrupować hierarchicznie i nie byłem w stanie obsłużyć rozmiaru. Użyłem również algorytmu grupowania k-średnich opartego na odległości Hamminga, biorąc pod uwagę wektory bitowe 650K o długości 62. Z żadnym z nich nie uzyskałem odpowiednich wyników.

Proszę pomóż.

Bez ograniczeń26
źródło
Nie mogę komentować b / c mojego 1 powtórzenia, więc musiałem wpisać to jako odpowiedź. Możesz spojrzeć na podobieństwo Jaccard. Myślę, że Python Scipy ma jego implementacje. Jaccard ...
gobrewers14
Czy istnieje powód, by zakładać, że dane w naturalny sposób dzielą się na pięć grup, przynajmniej w pewnym stopniu? Czy naprawdę interesuje Cię klastrowanie wierszy, czy też interesują Cię relacje między 62 cechami zakodowanymi w wektorach bitowych? Jeśli to drugie, bardziej odpowiednie są inne techniki.
micans

Odpowiedzi:

4

Zadajesz złe pytanie.

Zamiast pytać „jaki algorytm”, powinieneś zapytać „jaka jest znacząca kategoria / klaster w twojej aplikacji”.

Nie dziwię się, że powyższe algorytmy nie działały - są przeznaczone do bardzo różnych przypadków użycia. K-średnich nie działa z dowolnymi innymi odległościami. Nie używaj go z odległością Hamminga. Jest powód, dla którego nazywa się to k- średnich , ma sens jedynie wtedy, gdy średnia arytmetyczna jest znacząca (co nie jest dla danych binarnych).

Możesz zamiast tego wypróbować tryby k, IIRC jest to wariant, który jest przeznaczony do użycia z danymi kategorialnymi, a dane binarne są nieco kategoryczne (ale rzadkość może cię zabić).

Ale przede wszystkim, czy usunąłeś duplikaty, aby uprościć swoje dane, i na przykład usunąłeś unikalne / puste kolumny?

Być może APRIORI lub podobne metody mają również większe znaczenie dla twojego problemu.

Tak czy inaczej, najpierw ustal, czego potrzebujesz, a następnie który algorytm może rozwiązać to wyzwanie. Pracuj w oparciu o dane , a nie wypróbowując losowe algorytmy.

Ma ZAKOŃCZENIE - Anony-Mus
źródło
Czy możesz wyjaśnić, dlaczego „Nie korzystaj z odległości Hamminga”? Może to mieć sens, w końcu jest dostępne w Matlabie. Nie mam nic przeciwko otwieraniu nowego pytania, jeśli ma to sens.
Dror Atariah
Z powodu średniej. Średnia arytmetyczna jest bez znaczenia dla odległości hamowania lub danych binarnych. Zamiast tego użyj trybu lub medoidu .
Ma ZAKOŃCZENIE - Anony-Mousse
Żeby upewnić się, że dobrze to rozumiem: matlab używa średniej arytmetycznej podczas aktualizacji centroidów, gdy używasz średnich k wraz z metryką Hamminga. Czy to prawda? Jaki jest właściwy sposób wykorzystania tych danych w Matlabie?
Dror Atariah
k-średnich nazywa się k- średnich, ponieważ wykorzystuje średnią. W przeciwnym razie nazywa się to K-medoidami, trybami K itp. Średnia jest dobra dla L2 - suma kwadratowych odchyleń.
Ma ZAKOŃCZENIE - Anony-Mousse
Tak więc Matlab używa k- średnich wraz z metryką Hamminga; to nie ma większego sensu.
Dror Atariah
3

Może trochę spóźniłem się z odpowiedzią, ale prawdopodobnie przydałoby się to w przyszłości dla jakiegoś ciała.

Teoria rezonansu adaptacyjnego jest dobrym algorytmem dla problemów z klasyfikacją binarną. Sprawdź ART 1. Więcej informacji można znaleźć w bezpłatnej książce Projektowanie sieci neuronowych w rozdziale 19.

Sieć ta łączy świetny pomysł biologiczny i dobre wdrożenie matematyki. Również ten algorytm jest łatwy do wdrożenia, aw tej książce można również znaleźć instrukcje krok po kroku, jak zbudować ten klasyfikator.

itdxer
źródło
2

Klasycznym algorytmem dla grupowania danych binarnych jest model Bernoulli Mixture. Model może być dopasowany przy użyciu metod bayesowskich i może być dopasowany również przy użyciu EM (Expectation Maximization). Możesz znaleźć przykładowy kod Pythona w całym GitHubie, podczas gdy ten pierwszy jest potężniejszy, ale także trudniejszy. Mam implementację C # modelu na GitHub (używa Infer.NET, który ma licencję ograniczającą!).

Model jest dość prosty. Najpierw próbkuj klaster, do którego należy punkt danych. Następnie niezależnie próbkuj z tylu Bernoullis, ile masz wymiarów w zbiorze danych. Zauważ, że implikuje to warunkową niezależność wartości binarnych dla klastra!

W ustawieniach Bayesian wcześniejszym przypisaniem do klastra jest rozkład Dirichleta. Jest to miejsce na postawienie priorytetów, jeśli uważasz, że niektóre klastry są większe niż inne. Dla każdego klastra musisz określić wcześniej, rozkład Beta, dla każdego rozkładu Bernoulli. Zazwyczaj ten uprzedni to Beta (1,1) lub jednolity. Na koniec nie zapomnij losowo inicjować przypisań klastra, gdy dane są podawane. Spowoduje to przerwanie symetrii i sampler nie utknie.

Istnieje kilka ciekawych funkcji modelu BMM w ustawieniach Bayesian:

  1. Klastrowanie online (dane mogą być przesyłane jako strumień)

  2. Model może służyć do wnioskowania o brakujących wymiarach

Pierwszy jest bardzo przydatny, gdy zestaw danych jest bardzo duży i nie mieści się w pamięci RAM komputera. Drugi może być wykorzystywany do wszelkiego rodzaju zadań związanych z imputacją danych, np. przypisując brakującą połowę binarnego obrazu MNIST.

Vladislavs Dovgalecs
źródło