Jak działa clustering (szczególnie String clustering)?
Słyszałem o grupowaniu podobnych danych. Chcę wiedzieć, jak to działa w konkretnym przypadku dla String.
Mam tabelę z ponad 100 000 słów.
Chcę identyfikować to samo słowo z pewnymi różnicami (np.: house, house!!, hooouse, HoUse, @house, "house", etc...).
Co jest potrzebne, aby zidentyfikować podobieństwo i zgrupować każde słowo w klastrze? Jaki algorytm jest do tego bardziej zalecany?
3 answers
Aby zrozumieć, czym jest klastrowanie wyobraź sobie mapę geograficzną. Można zobaczyć wiele różnych obiektów(takich jak domy). Niektóre z nich są blisko siebie, a inne są daleko. Na tej podstawie można podzielić wszystkie obiekty na grupy (np. miasta). Algorytmy klastrowania robią dokładnie to - pozwalają dzielić dane na grupy bez wcześniejszego określania granic grup.
Wszystkie algorytmy klastrowania bazują na odległości (lub prawdopodobieństwie) pomiędzy dwoma obiektami. On Mapa Geograficzna jest to normalna odległość między 2 domami, w przestrzeni wielowymiarowej może to być odległość euklidesowa (w rzeczywistości odległość między 2 domami na mapie również jest odległością euklidesową). Do porównywania łańcuchów musisz użyć czegoś innego. 2 dobre wybory tutaj są Hamming i Levenshtein odległość . W twoim konkretnym przypadku Odległość Levenshteina jeśli jest bardziej pożądana (odległość Hamminga działa tylko z łańcuchami o tej samej wielkości).
Teraz możesz użyć jednego z istniejące algorytmy klastrowania. Jest ich wiele, ale nie wszystkie mogą pasować do Twoich potrzeb. Na przykład, pure k-means, już wspomniane tutaj nie pomoże, ponieważ wymaga początkowej liczby grup do znalezienia, a przy dużym słowniku ciągów może to być 100, 200, 500, 10000 - po prostu nie znasz liczby. Więc inne algorytmy mogą być bardziej odpowiednie.
Jednym z nich jest maksymalizacja oczekiwań algorytm. Jego zaletą jest to, że może znaleźć liczbę klastrów automatycznie. Jednak w praktyce często daje mniej precyzyjne wyniki niż inne algorytmy, więc normalnym jest użycie K-oznacza na górze EM , czyli najpierw znajdź liczbę klastrów i ich centrów za pomocą EM, a następnie użyj K-oznacza, aby dostosować wynik.
Inną możliwą gałęzią algorytmów, która może być odpowiednia dla Twojego zadania, jest hierarchiczne klastrowanie . Wynik analizy klastrów w tym przypadku nie jest zbiorem niezależnych grup, lecz raczej drzewem (hierarchią), gdzie kilka mniejszych gromad jest zgrupowanych w jedną większą, a wszystkie gromady są ostatecznie częścią jednej dużej gromady. W Twoim przypadku oznacza to, że wszystkie słowa są do pewnego stopnia do siebie podobne.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-11-19 21:14:11
Istnieje pakiet o nazwie stringdist , który pozwala na porównywanie łańcuchów za pomocą kilku różnych metod. Copypasting z tej strony:
- odległość Hamminga: Liczba pozycji z tym samym symbolem w obu łańcuchach. Zdefiniowany tylko dla ciągów o jednakowej długości.
- odległość Levenshteina: minimalna liczba wstawek, skreśleń i zamienników potrzebnych do przekształcenia łańcucha a w łańcuch b.
- (Pełna) odległość Damerau-Levenshtein: jak Levenshtein odległość, ale transpozycja sąsiednich symboli jest dozwolona.
- Optimal String Alignment / restricted odległość Damerau-Levenshtein: jak (pełna) odległość Damerau-Levenshtein, ale każdy podłańcuch może być edytowany tylko raz.
- najdłuższa wspólna odległość podłańcucha: minimalna liczba symboli, które muszą zostać usunięte w obu łańcuchach, dopóki wynikowe podłańcuchy nie będą identyczne.
- odległość q-gram: suma bezwzględnych różnic między N-gramowymi wektorami obu ciągów.
- odległość cosinusa: 1 minus cosinus podobieństwa obu N-gramowych wektorów.
- odległość Jaccarda: 1 minuje iloraz dzielonych N-gramów i wszystkich obserwowanych N-gramów.
- odległość Jaro: odległość Jaro jest wzorem 4 wartości i w praktyce szczególnym przypadkiem odległości Jaro-Winklera z p = 0.
- odległość Jaro-Winklera: odległość ta jest wzorem 5 parametrów określonych przez dwa porównywane ciągi (A, B, m, t, l) I P wybrane z [0, 0,25].
To da ci dystans. Ty może nie trzeba wykonywać analizy klastra, być może sortowanie według odległości łańcucha jest wystarczające. Stworzyłem skrypt, aby zapewnić podstawową funkcjonalność tutaj ... możesz go poprawić w razie potrzeby.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-11-30 15:48:50
Możesz użyć algorytmu, takiego jak Levenshtein distance do obliczania odległości i k-means do grupowania.
Odległość Levenshteina jest metryką ciągu do pomiaru ilości różnicy między dwoma sekwencjami
Wykonaj kilka testów i znajdź próg podobieństwa na słowo, który zadecyduje o twoich grupach.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-11-19 19:21:18