- Je voert de twee afwisselende stappen van k-means zelf uit.
- Je controleert inertia en handelt een leeg cluster expliciet af.
Je hebt metingen van planten, maar geen labels voor hun soorten. Kun je voorbeelden die op elkaar lijken bij elkaar leggen? Clustering zoekt zulke groepen; k-means wisselt tussen punten aan centra toewijzen en die centra naar hun groepsgemiddelden verplaatsen.
Een gevonden cluster is geen automatisch ontdekte waarheid. Features, schaling, het gekozen aantal k en de startcentra bepalen mede het resultaat. Hier krijg je de begincentra expliciet, zodat iedere stap te volgen is.
1. Kies het dichtstbijzijnde centrum
Neem punten [0,0], [2,0], [8,0] en [10,0], met startcentra [0,0] en [8,0]. Voor punt [2,0] zijn de gekwadrateerde afstanden 4 en 36, dus het hoort bij centrum 0. De vier toewijzingen zijn [0,0,1,1].
Je kent deze afstand uit k-NN. Het verschil is dat je nu centra vergelijkt en hun indices als clusterlabels gebruikt; er worden geen antwoordklassen meegegeven.
def afstand2(a, b):
som = 0
for j in range(len(a)):
som = som + (a[j] - b[j]) ** 2
return som
def wijs_toe(points, centers):
labels = []
for punt in points:
kandidaten = []
for i in range(len(centers)):
d = afstand2(punt, centers[i])
kandidaten.append((d, i))
labels.append(min(kandidaten)[1])
return labels
points = [[0, 0], [2, 0], [8, 0], [10, 0]]
initial = [[0, 0], [8, 0]]
print(wijs_toe(points, initial))
# [0,0,1,1]
Tuplevergelijking kiest eerst de afstand en daarna de laagste index. Maak wijs_toe(points,centers). We werken met niet-lege rechthoekige lijsten van eindige getallen, steeds met dezelfde positieve featurebreedte voor punten en centra.
2. Verplaats ieder centrum naar zijn groepsgemiddelde
De eerste groep bevat [0,0] en [2,0], met gemiddelde [1,0]. De tweede bevat [8,0] en [10,0], met gemiddelde [9,0]. Je berekent dat gemiddelde afzonderlijk voor iedere feature.
Waarom het gemiddelde? Voor vaste toewijzingen minimaliseert het de som van gekwadrateerde afstanden. Dat sluit aan op precies de afstand die we gebruiken; voor een andere afstand kan een ander middelpunt passend zijn.
def nieuwe_centra(
points, labels, old_centers):
result = []
for c in range(len(old_centers)):
groep = []
for i in range(len(points)):
if labels[i] == c:
groep.append(points[i])
centrum = []
if groep:
breedte = len(old_centers[c])
for j in range(breedte):
som = 0
for punt in groep:
som = som + punt[j]
waarde = som / len(groep)
centrum.append(waarde)
else:
centrum = list(old_centers[c])
result.append(centrum)
return result
labels = wijs_toe(points, initial)
centers = nieuwe_centra(
points, labels, initial)
print(centers) # [[1.0, 0.0], [9.0, 0.0]]
Maak nieuwe_centra(points,labels,old_centers) zonder de invoerlijsten te veranderen. Iedere punt krijgt één geldige clusterindex. Een leeg cluster heeft geen gemiddelde; onze afspraak is dat het zijn oude centrum behoudt als een nieuwe lijst.
Met een derde startcentrum [30,0] krijgt dat centrum geen punten. Je houdt dan [30,0], in plaats van te delen door nul. Andere algoritmen kunnen een leeg cluster herstarten; dit is een bewust gekozen beleid.
De centra starten dicht bij elkaar. Rondjes zijn punten, kruisen centra. Voer de twee stappen om en om uit.
C0 (0.00, 0.00) · C1 (1.00, 0.00)
Na een centrumupdate horen de lijnen nog bij de vorige toewijzing. Wijs opnieuw toe om te zien of punten van groep wisselen.
Voorspel in het diagram eerst welke punten bij elk kruis horen en klik daarna op toewijzen. Na de centrumupdate tonen de lijnen nog de vorige toewijzing; klik opnieuw op toewijzen om te zien of er punten wisselen.
023. Meet de resterende kwadratische afstand
Inertia is de som van de gekwadrateerde afstanden tot de gekozen centra. Het is een som, geen gemiddelde. Voor onze startcentra zijn de bijdragen 0,4,0,4: som 8; na de update zijn ze alle vier 1: som 4.
i wijst een punt x aan; l_i kiest zijn cluster en c dat centrum. Bereken de toewijzingen telkens opnieuw wanneer je de inertia bij nieuwe centra meet.
def inertia(points, centers):
labels = wijs_toe(points, centers)
som = 0
for i in range(len(points)):
c = centers[labels[i]]
som = som + afstand2(points[i], c)
return som
print(inertia(points, initial)) # 8
print(inertia(points, centers)) # 4.0
4. Wissel beide stappen af
Na nog een ronde blijven onze centra [1,0] en [9,0]. Er is dan een stabiele oplossing. Bewaar ook de begin-inertia en de waarde na iedere volledige ronde; bij deze start wordt dat [8,4,4].
centers = [list(c) for c in initial]
history = [inertia(points, centers)]
for stap in range(20):
labels = wijs_toe(points, centers)
nieuw = nieuwe_centra(
points, labels, centers)
history.append(inertia(points, nieuw))
stabiel = nieuw == centers
centers = nieuw
if stabiel:
break
print(centers, history)
# [[1.0, 0.0], [9.0, 0.0]] [8, 4.0, 4.0]
break verlaat de lus bij stabiliteit. Maak kmeans(points,initial,max_iter=20) als (centers,labels,history) met de uiteindelijke toewijzingen. Kopieer de startcentra; max_iter is een niet-negatief geheel getal, anders ValueError, en nul rondes geeft de beginsituatie terug.
Veelgemaakte fout: altijd twintig rondes uitvoeren en een verzonnen dalende geschiedenis teruggeven. De waarden moeten uit de echte centra komen; met deze afwisselende stappen hoort inertia niet toe te nemen, op afronding na.
De uitkomst kan een lokaal minimum zijn. Vergelijk meerdere starts en onthoud dat cluster 0 in een andere run gerust cluster 1 kan heten. Een kleinere inertia bij meer clusters bewijst bovendien niet dat die groepen nuttiger zijn.
03Wat neem je mee?
- Toewijzen en gemiddelden bijwerken lossen om de beurt een deel van hetzelfde afstandsprobleem op.
- Lege clusters en invoerkopieën vragen een expliciete afspraak.
- Echte inertia helpt het verloop controleren; ze bewijst geen betekenisvolle groepen.
Hierna maak je een kleinere representatie die zoveel mogelijk variatie bewaart.