K-średnich jest standardowym nie nadzorowanym algorytmem grupowania, który, biorąc pod uwagę zestaw „punktów” i pewną liczbę klastrów K, przypisze każdy „punkt” do jednego z K klastrów.
Pseudokod K-średnich
Zauważ, że istnieje wiele wariantów K-średnich. Musisz zaimplementować algorytm, który opisuję poniżej. Możesz mieć pewne różnice w algorytmie lub użyć wbudowanych, o ile uzyskasz taki sam wynik jak ten algorytm, mając te same punkty początkowe.
W tym wyzwaniu wszystkie dane wejściowe będą punktami na płaszczyźnie 2D (każdy punkt jest reprezentowany przez jego współrzędne w xiy).
Inputs: K, the number of clusters
P, the set of points
Choose K points of P uniformly at random
Each chosen point is the initial centroid of its cluster
Loop:
For each point in P:
Assign to the cluster whose centroid is the nearest (Euclidean distance)
In case of a tie, any of the tied cluster can be chosen
Recompute the centroid of each cluster:
Its x coordinate is the average of all x's of the points in the cluster
Its y coordinate is the average of all y's of the points in the cluster
Until the clusters don't change from one iteration to the next
Output: the set of clusters
Wejścia i wyjścia
- Możesz wziąć K i P przez
STDIN, lub jako argument funkcji itp. - P i punkty w P można przedstawić za pomocą dowolnej struktury, która jest naturalna dla zestawu / list w wybranym języku.
- K jest ściśle dodatnią liczbą całkowitą.
- Możesz założyć, że dane wejściowe są prawidłowe.
- Zawsze będzie co najmniej K punktów w P.
- Możesz wyprowadzać klastry do
STDOUT, zwracać je z funkcji itp. - Kolejność klastrów i kolejność wewnątrz klastrów jest nieistotna. -Można albo zwrócić grupy punktów, które reprezentują klastry, albo każdy punkt oznaczony identyfikatorem klastra (np. Liczba całkowita).
Przypadki testowe
Ponieważ powstałe klastry zależą od tego, które punkty zostały początkowo wybrane, nie wszyscy mogą uzyskać takie same wyniki (lub ten sam wynik przy każdym uruchomieniu kodu).
Dlatego dane wyjściowe należy traktować tylko jako dane wyjściowe.
Input:
K = 1
P = [[1,2.5]]
Output:
[[[1,2.5]]]
Input:
K = 3
P = [[4,8], [15,16], [23,42], [-13.37,-12.1], [666,-666]]
Output:
[[[666,-666]],[[-13.37,-12.1],[4,8]],[[15,16],[23,42]]]
Input:
K = 2
P = [[1,1], [1,1], [1,1]]
Output:
[[[1,1]],[[1,1],[1,1]]]
Punktacja
To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
1, wszystkie punkty drugiego klastra mają etykietę 2itp.)
K=2, P = [[1,1], [1,1], [1,1]].