Różnica między standardowymi a sferycznymi algorytmami k-średnich

Chciałbym zrozumieć, jaka jest główna różnica w implementacji między standardowymi a sferycznymi algorytmami klastrowania k-średnich.

Na każdym etapie k-średnich oblicza odległości między wektorami elementów i centroidami gromady i ponownie przypisuje dokument do tej gromady, której centroid jest najbliższy. Następnie wszystkie centroidy są przeliczane.

W sferycznych średnich k wszystkie wektory są znormalizowane, a miarą odległości jest podobieństwo cosinus.

Czy to wszystko, czy jest coś jeszcze?

Pytanie brzmi:

Jaka jest różnica między klasycznymi k-średnimi a sferycznymi k-średnimi?

Klasyczny K-oznacza:

W klasycznych środkach k staramy się zminimalizować odległość euklidesową między centrum gromady a członkami gromady. Intuicja tego polega na tym, że promieniowa odległość od centrum skupiska do położenia elementu powinna „mieć identyczność” lub „być podobna” dla wszystkich elementów tego skupiska.

Algorytm to:

• Ustaw liczbę klastrów (inaczej liczbę klastrów)
• Zainicjuj, losowo przypisując punkty w przestrzeni do wskaźników skupień
• Powtarzaj, aż się zbiegną
  • Dla każdego punktu znajdź najbliższy klaster i przypisz punkt do klastra
  • Dla każdego klastra znajdź średnią punktów członkowskich i średnią centrum aktualizacji
  • Błąd jest normą odległości klastrów

Kuliste K-oznacza:

W sferycznych k-średnich chodzi o ustawienie środka każdego skupienia w taki sposób, aby zarówno jednolity, jak i minimalny był kąt między składnikami. Intuicja przypomina patrzenie na gwiazdy - punkty powinny mieć spójne odstępy między sobą. To odstępy są łatwiejsze do oszacowania jako „podobieństwo kosinusowe”, ale oznacza to, że nie ma galaktyk „mleczno-drogowych” tworzących duże jasne obszary na niebie danych. (Tak, staram się rozmawiać z babcią w tej części opisu.)

Więcej wersji technicznej:

Pomyśl o wektorach, rzeczach, które przedstawiasz jako strzałki z orientacją i stałą długością. Może być przetłumaczony w dowolnym miejscu i być tym samym wektorem. ref

Orientację punktu w przestrzeni (jego kąt względem linii odniesienia) można obliczyć za pomocą algebry liniowej, w szczególności iloczynu punktowego.

Jeśli przeniesiemy wszystkie dane, aby ich ogon znalazł się w tym samym punkcie, możemy porównać „wektory” pod kątem i zgrupować podobne w jedną grupę.

Dla jasności długości wektorów są skalowane, dzięki czemu łatwiej je porównać z gałką oczną.

Możesz myśleć o tym jak o konstelacji. Gwiazdy w jednej gromadzie są w pewnym sensie blisko siebie. To są moje gałki oczne uważane za konstelacje.

Wartość ogólnego podejścia polega na tym, że pozwala nam tworzyć wektory, które inaczej nie miałyby wymiaru geometrycznego, na przykład w metodzie tf-idf, w której wektorami są częstotliwości słów w dokumentach. Dwa dodane słowa „i” nie oznaczają „the”. Słowa są nieciągłe i nienumeryczne. Są niefizyczne w sensie geometrycznym, ale możemy nadać im kształt geometryczny, a następnie użyć metod geometrycznych do ich obsługi. Kuliste k-średnie mogą być używane do grupowania na podstawie słów.

$$\begin{bmatrix} x1&y1&x2&y2&group\\ 0&-0.8&-0.2013&-0.7316&B\\ -0.8&0.1&-0.9524&0.3639&A\\ 0.2&0.3&0.2061&-0.1434&C\\ 0.8&0.1&0.4787&0.153&B\\ -0.7&0.2&-0.7276&0.3825&A\\ 0.9&0.9&0.748&0.6793&C\\ \end{bmatrix}$$

Kilka punktów:

• Występują w sferze jednostkowej, aby uwzględnić różnice w długości dokumentu.

Przeanalizujmy faktyczny proces i zobaczmy, jak (złe) było moje „gałki oczne”.

Procedura jest następująca:

1. (ukryty w problemie) łączenie ogonów wektorów u źródła
2. rzut na sferę jednostkową (w celu uwzględnienia różnic w długości dokumentu)
3. użyj klastrowania, aby zminimalizować „ podobieństwo cosinusa ”

$$J = \sum_{i} d \left( x_{i},p_{c\left( i \right)} \right)$$
$$d \left( x,p \right) = 1- cos \left(x,p\right) = \frac{\langle x,p \rangle}{\left \|x \right \|\left \|p \right \|}$$

(więcej edycji wkrótce)

Spinki do mankietów:

1. http://epub.wu.ac.at/4000/1/paper.pdf
2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11111125125&rep=rep1&type=pdf
3. http://www.cs.gsu.edu/~wkim/index_files/papers/refinehd.pdf
4. https://www.jstatsoft.org/article/view/v050i10
5. http://www.mathworks.com/matlabcentral/fileexchange/32987-the-spherical-k-means-alameterm
6. https://ocw.mit.edu/courses/sloan-school-of-management/15-097-prediction-machine-learning-and-statistics-spring-2012/projects/MIT15_097S12_proj1.pdf