k-keskmiste klasterdamine: alguspunkt määrab tulemuse

K-keskmiste algoritm on esimene klasterdamismeetod, mille igaüks selgeks õpib. Sel on aga üks omadus, mida keegi ei maini: leitud vastus sõltub otseselt sellest, kust algoritm juhtub alustama. Keerake allolevat ketast. Jälgige, kuidas samad punktid leiavad samaks arvuks rühmadeks jaotatuna hoopis teistsuguse paigutuse.

Näidisarvutus — k-keskmiste klasterdamine: alguspunkt määrab tulemuse

Klastrisisene ruutude summa	1,0989
Iteratsioone koondumiseni	2
Nende erinevus	430,8%
Erinevaid leitud vastuseid	3 24-st
Seega on see alguspunkt	parim leitud tulemus

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — k-keskmiste klasterdamine: alguspunkt määrab tulemuse

k-keskmiste meetod otsib k rühma, korrates kaht sammu, kuni miski enam ei muutu: iga punkt seotakse lähima keskusega, misjärel nihutatakse iga keskus talle kogunenud punktide keskväärtusele. Meetod püüab minimeerida klastrisisest ruutude summat. See on iga punkti ja tema keskuse vaheliste kauguste ruutude kogusumma. Kumbki kahest sammust saab seda väärtust üksnes vähendada. See asjaolu ongi kogu tõestus, et algoritm lõpuks peatub.

Mida iga sümbol tähendab

k: küsitud klastrite arv, mida andmed ise kuidagi ette ei ütle
WCSS: iga punkti ja tema keskuse vaheliste kauguste ruutude kogusumma

Eeldab: Et klaster on ümar ja teistega laias laastus sama suur kogum, sest keskväärtusest arvutatud eukleidilise kauguse ruut ei suuda midagi muud väljendada. Piklikke, pesastatud või väga erineva suurusega rühmi ei leia k-keskmiste meetod lihtsalt halvasti. Need pole üldse seda laadi rühmad, mida ta otsib.

Kõik need käivitused koondusid 🖖

Jätke kolm kobarat ning k = 3 muutmata ja liigutage alguspunkti valikunuppu asendist 1 asendisse 24. Kakskümmend kaks katset koonduvad skoorile 1,0989. Numbrid 17 ja 21 koonduvad tulemustele 5,8172 ja 5,8331, mis on 5,3 korda halvem. Nad ühendavad kaks kobarat ja lõikavad kolmanda pooleks. Neis kahes käivituses ei juhtunud tegelikult midagi valesti. Lloydi algoritm koondub garanteeritult. Klastrisisene ruutude summa langeb iga sammuga ja see ei saa väheneda igavesti. Seetõttu peab algoritm peatuma. Läbi viidud 1536 katsest, mis katsid kõik andmestikud, kõik k väärtused ja mõlemad initsialiseerimise meetodid, ei ebaõnnestunud see kordagi. Algoritm aga ei taga, et peatumispunkt on sisuliselt hea. Fraas „algoritm koondus“ räägib aritmeetikast, mitte andmete tegelikust struktuurist. K-keskmiste meetodit ainult korra käivitades pole teil mingit võimalust teada, kumba lahendust te parasjagu käes hoiate.

k-means++ poolitab kahju, kuid ei luba midagi 🖖

Muutke Algus valikuks k-means++ ja selle andmestiku hajuvus kaob. Kõik kakskümmend neli katset leiavad väärtuse 1,0989. Seda abinõu kasutavad kõik. See töötab tänu algsete keskpunktide laialijaotamisele, mitte ei vali neid enam juhuslikult. Paranemine on siiski statistiline, mitte kindel garantii, ja on kasulik teada selle täpset suurust. Mõõdetuna 112 andmestiku, valimi suuruse ja k väärtuse kombinatsioonil: k-means++ leidis parema optimumi 38 korral, juhuslik algus 17 korral ning 57 juhul jäid tulemused viiki. Keskmine erinevus kahekümne nelja alguspunkti vahel langes 55,5% juurest 31,7% juurde. See umbkaudu poolitab halva juhuse tekitatud veamäära. Samas ühel juhul kuuest oleksite ka noolt visates täpsema vastuse saanud. Üheks selliseks näiteks seadke rõnga punktide arvuks 90 ja k = 5. Juhuslik algus jõuab väärtuseni 0,9884, aga k-means++ peatub skooril 1,0213.

Stabiilne, tasakaalustatud ja kindel vastus küsimusele, millel pole lahendust 🖖

Laadige viimane eelseadistus. Punktid moodustavad korrapärase võre, kus pole ainsatki klastrit, kuid k-keskmiste meetod jagab need neljaks täpselt 25 elemendiga rühmaks. Vaadake nüüd, mida kõik teie diagnostikavahendid selle tulemuse kohta ütlevad. Algoritm koondus üheteistkümne iteratsiooniga. Tulemus on stabiilne. Kõik kakskümmend neli alguspunkti jõuavad sama vastuseni, seega ei paljasta korduv käivitamine ühtegi viga. Klastrid on ideaalselt tasakaalus, mis tavaliselt iseloomustabki head klasterdamist. Kolm eraldiseisvat signaali viitavad samale järeldusele, kuigi tegelikult pole andmetes midagi peidus. See on klasterdamise osa, millele pole tehnilist lahendust. K-keskmised vastab küsimusele „kuhu k tsentrit paigutuksid“ ja leiab alati vastuse. Seda sõltumata sellest, kas küsimusele „mitu rühma neis andmetes on“ üldse leidub loogiline lahendus.

Ülesanne täielikult lahendatud

Sa ei tea, mitu klastrit sinu andmetes on, seega plaanid selle välja lugeda skoorikõvera küünarnukilt. Katseta seda lugemist kõigil neljal punktikogumil ja loe kokku, mitmel korral see paika peab. Alumine paneel annab sulle parima skoori iga k korral 1 kuni 8, mille taustale on joonistatud langus võrreldes eelmise k-ga.

Ava see ülesanne tööriistas
1. Kõigepealt sellest, miks küünarnukk ja mitte miinimum. Vali punktikogumiks Kolm kobarat ja uuri kõverat: 10,3978 kui k = 1, seejärel 5,6145, 1,0989, 0,9241, 0,8052, 0,6875, 0,6077, 0,5366. Kõver ei tõuse kordagi. See on võimatu: igasuguse k rühmaks jaotamise saab muuta k + 1 rühmaks lihtsalt ühte rühma jagades ning jagamine saab punkte viia vaid nende oma keskpunktile lähemale. Suurenda k väärtust kuni punktide arvuni ja iga punkt moodustab omaette klastri, mille skoor on täpselt 0.
  
  $WCSS (k) = \sum_{j = 1}^{k} \sum_{x \in C_{j}} ∥ x - μ_{j} ∥^{2}, WCSS (k + 1) \leq WCSS (k) three blobs : 10.3978, 5.6145, 1.0989, 0.9241, 0.8052, 0.6875, 0.6077, 0.5366$
2. Seega pole kõveral ühtegi miinimumi, mida leida, ja tõlgendamine peab põhinema hoopis langustel. Kobarate puhul jooksevad need 46,0%, seejärel 80,4%, siis 15,9%, 12,9%, 14,6%, 11,6%, 11,7%. Langus pärast k = 3 on viiendik eelnevast langusest – kukkumine teguriga 5,06 – ja andmed loodigi täpselt k = 3 baasil. Siin meetod toimib ja see ongi näide, mida kõigile esitletakse.
  
  $drop (k) = 1 - \frac{WCSS ( k + 1 )}{WCSS ( k )}, elbow = ar g max_{k} \frac{drop ( k - 1 )}{drop ( k )} three blobs : 46 . 0%, 80 . 4%, 15 . 9%, 12 . 9%, 14 . 6%, 11 . 6%, 11 . 7% \Rightarrow k = 3, \times 5.06$
3. Nüüd aga Võre, milles klastrid üldse puuduvad. Selle langused on 41,6%, 34,1%, 36,8%, 16,4%, 16,9%, 12,8%, 15,7%. Pärast k = 4 toimub kukkumine teguriga 2,25, mis on täpselt see kuju, mida sul paluti otsida. Küünarnukimeetod annab tulemuseks "neli klastrit" andmestiku puhul, kus pole ainsatki.
  
  $lattice : 41 . 6%, 34 . 1%, 36 . 8%, 16 . 4%, 16 . 9%, 12 . 8%, 15 . 7% \Rightarrow k = 4, \times 2.25$
4. Järgmisena Rõngas, kus on tõepoolest kaks rühma. Langused jooksevad seal 37,2%, 32,8%, 38,5%, 33,4%, 43,1%, 25,3%, 15,3%; see tähendab täielikku suundumuse puudumist ja päris lõpus kahte kukkumist. Kõige järsum kukkumine leiab aset pärast k = 6. Tulemus annab kuus, ent õige vastus on kaks.
  
  $ring : 37 . 2%, 32 . 8%, 38 . 5%, 33 . 4%, 43 . 1%, 25 . 3%, 15 . 3% \Rightarrow k = 6, \times 1.70$
5. Lõpetuseks Ebaühtlane, milles on kolm eri suurusega klastrit: 43,8%, 48,4%, 35,4%, 24,7%, 16,1%, 14,4%, 21,8%. Sujuv kahanemine ilma ühegi kukkumiseta – kõige järsum neist on teguriga 1,53, mis ei moodusta murdepunkti. Lugemine ei anna sulle midagi andmete põhjal, milles tegelikult on kolm klastrit.
  
  $uneven : 43 . 8%, 48 . 4%, 35 . 4%, 24 . 7%, 16 . 1%, 14 . 4%, 21 . 8% \Rightarrow k = 5, \times 1.53$
Vastus

Neljast üks õige: kobarate puhul läks täppi, võre peal mõeldi välja neli klastrit, rõnga kahe asemele pakuti kuut ja ebaühtlase kogumi puhul valitses vaikus. See muster ei ole juhuslik. Küünarnukk on terav täpselt siis, kui klastrid on ümarad, sarnase suurusega ning hästi eraldatud. Teisisõnu olukorras, kus sa oleksid võinud nad ka niisama peale vaadates kokku lugeda. See hajub igal andmestikul, kus sul tegelikult seda abi vaja oleks läinud. Seda on kasulik teada, enne kui kasutad antud kõverat kellelegi mingi arvu kaitsmiseks, ja just seetõttu seisab küünarnukk siluetiskoori, lüngastatistiku ning informatsioonikriteeriumite kõrval, mitte nendest kõrgemal. Ühtegi neist pole sellel lehel ja igaüks neist esindab erinevat viisi sama küsimuse esitamiseks, millele skoorikõver vastata ei suuda. See küsimus pole mitte "kuhu läheksid k keskpunkti", millele leidub alati vastus, vaid "kas siin üldse on mingeid rühmi".

$set three blobs lattice ring uneven elbow says 3465 truth 3023 sharpness \times 5.06 \times 2.25 \times 1.70 \times 1.53$

Õpitee

Andmetele sirge sobitamine

Allikad (3)

The algorithm itself. Written in 1957 for quantising a signal into levels, circulated as a Bell Labs memorandum, and not published for twenty-five years: S. P. Lloyd, “Least squares quantization in PCM.” IEEE Transactions on Information Theory 28(2), 129–137, 1982.
The initialisation the second insight block measures — and the source of the bound that makes it worth using, which is a guarantee about the EXPECTED score rather than about any single run: D. Arthur and S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding.” In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’07), 1027–1035. SIAM, 2007.
Where the elbow reading comes from, and it was proposed with more caution than it is usually repeated with: R. L. Thorndike, “Who belongs in the family?” Psychometrika 18(4), 267–276, 1953.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.