Springen naar inhoud

K-means algoritme


  • Log in om te kunnen reageren

#1

Imengine

    Imengine


  • >25 berichten
  • 85 berichten
  • Ervaren gebruiker

Geplaatst op 03 februari 2011 - 16:20

Bij K-means clustering wordt via een iteratieve procedure punten aan clusters toegewezen op basis van de afstand van het punt tot de clusters. Vervolgens wordt op basis van het gemiddelde van de punten die aan de cluster waren toegewezen, de positie van de cluster verplaatst, waarna opnieuw punten toegewezen worden aan de cluster op basis van afstand enzovoorts enzovoorts.

1 van de opmerkingen op dit algoritme was dat omwille van het gebruik van de Euclidische afstand, binnen elke cluster de variantie van variabele 1 gelijk moet zijn aan variabele 2 (voor het geval van 2 variabelen).

Ik begrijp echter niet hoe dit komt. Mijn redenering is dat de variantie niet kan verschillen, want als de variantie langs de ene variabele groter zou worden, dan zouden net die punten aan een andere cluster toegewezen worden, waardoor dergelijke verschillen in variantie dus net zouden moeten verdwijnen.

De cluster eindigt eigenlijk altijd in het midden van een aantal punten, het zoekt als het ware de punten op en plaats zich daar dan mooi tussen, wat maakt dat varianties net klein zouden blijven en de variantie van variabele 1 kort zou liggen bij variabele 2.

Is dit een juiste redenering? Zou iemand misschien het principe kunnen uitleggen waarom net het gebruik van die afstandsmaat zorgt dat varianties gelijk blijven.

Bedankt!

Veranderd door Imengine, 03 februari 2011 - 16:22


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 03 februari 2011 - 17:37

Toevallig ook les gehad van Schrauwen?

Dat komt volgens mij omdat doordat de afstandmaat kwadratisch is, beide (echte) clusters waarmee je begint ook min of meer even groot moeten zijn. Stel je voor dat je een heel kleine cluster hebt, en een cluster die veel groter is. Door die kwadratische afstandsmaat kom je dan toch in de problemen? Die kleine cluster zal ook punten van de grote cluster meenemen.

Dus zal K-means clustering inderdaad voor zorgen dat de variantie van de clusters steeds ongeveer even groot is, ook al is dat niet altijd terecht.
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#3

Imengine

    Imengine


  • >25 berichten
  • 85 berichten
  • Ervaren gebruiker

Geplaatst op 03 februari 2011 - 22:32

Bedankt voor je antwoord. Ik denk dat ik het nu wel snap waarom dergelijk afstandsmaat voor die problemen zorgt (na het ook wel nog een aantal keer getekend te hebben ;)). De maat hanteert een soort van "zelfde" criterium voor alle datapunten in relatie tot de cluster, wat maakt dat je inderdaad uiteindelijk een concentratie van je punten krijgt rond je cluster die gelijke varianties in de hand werken. Dit zorgt dan inderdaad voor problemen als je "ware" verdeling uit twee clusters van punten zouden bestaan die een verschillende grootte hebben, met name ook omdat de clusters min of meer even groot moeten zijn (dit wist ik niet maar speelt dus wel belangrijke rol).

Geen les gehad van Schrauwen nee :P





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures