{"id":306,"date":"2016-06-15T04:18:55","date_gmt":"2016-06-15T02:18:55","guid":{"rendered":"http:\/\/www.mlguru.cz\/?p=306"},"modified":"2017-08-12T18:14:21","modified_gmt":"2017-08-12T16:14:21","slug":"konvergence-algoritmu-k-means","status":"publish","type":"post","link":"https:\/\/www.mlguru.com\/cs\/konvergence-algoritmu-k-means\/","title":{"rendered":"Konvergence algoritmu k-means"},"content":{"rendered":"

U pohovor\u016f na pozici v\u00fdzkumn\u00edka v Seznamu<\/a> se pt\u00e1v\u00e1m na principy vybran\u00fdch algoritm\u016f strojov\u00e9ho u\u010den\u00ed, mezi kter\u00e9 pat\u0159\u00ed i k-means pro shlukov\u00e1n\u00ed. Po tom, co algoritmus d\u00e1me dohromady, n\u00e1sleduje ot\u00e1zka, zda je zaru\u010den\u00e9, \u017ee algoritmus v\u017edy skon\u010d\u00ed. Tu\u0161il jsem, \u017ee se daj\u00ed naj\u00edt extr\u00e9mn\u00ed p\u0159\u00edpady, kdy algoritmus m\u016f\u017ee za\u010d\u00edt nekone\u010dn\u011b dlouho kmitat mezi n\u011bkolika stejn\u011b dobr\u00fdmi \u0159e\u0161en\u00edmi, a tak jsem po\u017eadoval drobn\u00e9 dopln\u011bn\u00ed ukon\u010dovac\u00ed podm\u00ednky (nap\u0159\u00edklad detekci cyklu), kter\u00e1 by ukon\u010den\u00ed\u00a0garantovala.<\/p>\n

Ned\u00e1vno jsem v\u0161ak narazil na uchaze\u010de, kter\u00fd byl sk\u00e1lopevn\u011b p\u0159esv\u011bd\u010den\u00fd, \u017ee standardn\u011b definovan\u00fd k-means skon\u010d\u00ed za v\u0161ech okolnost\u00ed a p\u0159\u00edsn\u011bj\u0161\u00ed krit\u00e9rium nen\u00ed pot\u0159eba. Vzhledem k tomu, \u017ee jsem \u017e\u00e1dn\u00fd protip\u0159\u00edklad p\u0159ipraven\u00fd nem\u011bl, zkusil jsem nejprve zahledat na internetu. A ejhle. Internet je pln\u00fd \u201ed\u016fkaz\u016f\u201c toho, \u017ee k-means konverguje. Tvrd\u00ed to dokonce i Wikipedie<\/a>! Nezbylo mi tedy nic jin\u00e9ho, ne\u017e ten protip\u0159\u00edklad vymyslet. Tady je.<\/p>\n

Algoritmus k-means<\/h3>\n

K-means pat\u0159\u00ed do skupiny takzvan\u00fdch algoritm\u016f strojov\u00e9ho u\u010den\u00ed bez u\u010ditele. Jeho c\u00edlem je nalezen\u00ed k<\/em>\u00a0shluk\u016f dan\u00fdch bod\u016f, kde shlukem rozum\u00edme skupinu bod\u016f, kter\u00e9 jsou si navz\u00e1jem bl\u00edzko (ve smyslu n\u011bjak\u00e9 metriky). Typick\u00fdm p\u0159\u00edkladem pou\u017eit\u00ed m\u016f\u017ee b\u00fdt anal\u00fdza z\u00e1kazn\u00edk\u016f internetov\u00e9ho obchodu, kter\u00e9 chceme podle z\u00e1jm\u016f a chov\u00e1n\u00ed rozt\u0159\u00eddit do p\u0159edem nezn\u00e1m\u00fdch kategori\u00ed.<\/p>\n

Vstupem algoritmu je mno\u017eina m<\/em> bod\u016f, kter\u00e9 jsou definovan\u00e9 sou\u0159adnicemi v\u00a0n<\/em>-rozm\u011brn\u00e9m prostoru, a \u010d\u00edslo k, <\/em>ur\u010duj\u00edc\u00ed po\u017eadovan\u00fd po\u010det shluk\u016f. <\/em>V\u0161echny shluky jsou reprezentovan\u00e9 sv\u00fdmi st\u0159edy a ka\u017ed\u00fd bod potom n\u00e1le\u017e\u00ed do shluku, jeho\u017e st\u0159ed je mu nejbl\u00ed\u017ee. Sou\u0159adnice st\u0159ed\u016f se ur\u010duj\u00ed iterativn\u00edm zp\u016fsobem zalo\u017een\u00fdm na EM algoritmu<\/a>. Zde uv\u00e1d\u00edm jeho neform\u00e1ln\u00ed z\u00e1pis (z\u00e1jemci o precizn\u011bj\u0161\u00ed definici si ho m\u016f\u017eou nastudovat na p\u0159\u00edklad na Wikipedii):<\/a><\/p>\n

    \n
  1. Pro ka\u017ed\u00fd shluk zvol n\u00e1hodn\u011b sou\u0159adnice jeho st\u0159edu (typicky se vol\u00ed toto\u017en\u011b se sou\u0159adnicemi n\u00e1hodn\u011b vybran\u00fdch r\u016fzn\u00fdch bod\u016f).<\/li>\n
  2. Ka\u017ed\u00fd bod p\u0159i\u0159a\u010f st\u0159edu, ke kter\u00e9mu le\u017e\u00ed nejbl\u00ed\u017ee.<\/li>\n
  3. Ur\u010di nov\u00e9 sou\u0159adnice st\u0159ed\u016f jako pr\u016fm\u011br sou\u0159adnic v\u0161ech bod\u016f, kter\u00e9 n\u00e1le\u017e\u00ed do dan\u00e9ho shluku.<\/li>\n
  4. Opakuj od bodu 2, dokud se shlukov\u00e1n\u00ed neust\u00e1l\u00ed.<\/li>\n<\/ol>\n

    Princip algoritmu je ilustrovan\u00fd obr\u00e1zkem 1.<\/p>\n

    \"Algoritmus<\/a>

    Obr\u00e1zek 1: Algoritmus k-means.<\/p><\/div>\n

    Nen\u00ed obt\u00ed\u017en\u00e9 dok\u00e1zat, \u017ee tento iterativn\u00ed algoritmus neust\u00e1le zmen\u0161uje chybu, definovanou jako sou\u010det vzd\u00e1lenost\u00ed v\u0161ech bod\u016f od st\u0159ed\u016f sv\u00fdch shluk\u016f, a sp\u011bje tak k\u00a0n\u011bjak\u00e9mu lok\u00e1ln\u011b-optim\u00e1ln\u00edmu \u0159e\u0161en\u00ed. Co v\u0161ak, pokud dojde k\u00a0tomu, \u017ee m\u00e1 jeden bod stejn\u011b daleko ke st\u0159ed\u016fm dvou nebo v\u00edce r\u016fzn\u00fdch shluk\u016f? V\u00a0takov\u00e9m p\u0159\u00edpad\u011b je mo\u017en\u00e9 n\u00e1hodn\u011b vybrat libovoln\u00fd z\u00a0nich a v\u00a0tom je k\u00e1men \u00farazu.<\/p>\n

    Protip\u0159\u00edklady<\/h3>\n

    Za\u010dn\u011bme velmi jednoduch\u00fdm p\u0159\u00edkladem. M\u011bjme pouze dva body, kter\u00e9 le\u017e\u00ed p\u0159esn\u011b na sob\u011b, a hledejme 2 shluky. Pokud budou jejich st\u0159edy\u00a0inicializov\u00e1ny do stejn\u00e9ho m\u00edsta jako shlukovan\u00e9 body, m\u00e1me probl\u00e9m, nebo\u0165 v kroku 2 algoritmu bude m\u00edt ka\u017ed\u00fd\u00a0bod stejn\u011b daleko ke dv\u011bma st\u0159ed\u016fm, a m\u016f\u017ee si tak vybrat odli\u0161n\u00fd od toho z p\u0159edchoz\u00ed iterace. T\u00edm se zm\u011bn\u00ed shlukov\u00e1n\u00ed a algoritmus tak pokra\u010duje d\u00e1l. Takto je mo\u017en\u00e9 kmitat mezi \u010dty\u0159mi \u0159e\u0161en\u00edmi libovoln\u011b dlouho a algoritmus nemus\u00ed nikdy skon\u010dit.<\/p>\n

    Dalo by se nam\u00edtnout, \u017ee se v\u00a0tomto jednoduch\u00e9m p\u0159\u00edkladu oba shluky p\u0159ekr\u00fdvaj\u00ed a nemuseli bychom je tedy pova\u017eovat za r\u016fzn\u00e1 \u0159e\u0161en\u00ed. Lze v\u0161ak vymyslet i netrivi\u00e1ln\u00ed p\u0159\u00edklady.<\/p>\n

    M\u011bjme 10 bod\u016f v trojrozm\u011brn\u00e9m prostoru, kter\u00e9 le\u017e\u00ed na vrcholech a v\u00a0polovin\u00e1ch st\u0159ed\u016f hran pomysln\u00e9ho pravideln\u00e9ho \u010dty\u0159st\u011bnu, a hledejme 6 shluk\u016f, jejich\u017e st\u0159edy A, B, C, D, E, F jsou inicializov\u00e1ny do st\u0159ed\u016f hran, jak je ilustrov\u00e1no na obr\u00e1zku 2.<\/p>\n

    \"Obr\u00e1zek<\/a>

    Obr\u00e1zek 2: Protip\u0159\u00edklad.<\/p><\/div>\n

    V\u00a0takov\u00e9m p\u0159\u00edpad\u011b jsou v\u017edy body na vrcholech stejn\u011b daleko od t\u0159\u00ed r\u016fzn\u00fdch st\u0159ed\u016f a je mo\u017en\u00e9 je tedy p\u0159i\u0159adit t\u0159em r\u016fzn\u00fdm shluk\u016fm. Existuj\u00ed t\u0159i r\u016fzn\u00e1 shlukov\u00e1n\u00ed, mezi kter\u00fdmi m\u016f\u017ee algoritmus kmitat, ani\u017e by zkonvergoval. Tato r\u016fzn\u00e1 \u0159e\u0161en\u00ed jsou zn\u00e1zorn\u011bna na obr\u00e1zku 3.<\/p>\n

    \"Obr\u00e1zek<\/a>

    Obr\u00e1zek 3: T\u0159i r\u016fzn\u00e1 \u0159e\u0161en\u00ed.<\/p><\/div>\n

    Klasick\u00fd algoritmus k-means tedy v\u00a0extr\u00e9mn\u00edch p\u0159\u00edpadech konvergovat nemus\u00ed. Opat\u0159en\u00ed, kter\u00e1 jeho skon\u010den\u00ed zajist\u00ed jsou v\u0161ak snadn\u00e1. Nejjednodu\u0161\u0161\u00edm z\u00a0nich je determinizace v\u00fdb\u011bru shluku v\u00a0p\u0159\u00edpad\u011b, \u017ee m\u00e1me v\u00edce mo\u017enost\u00ed. Shluky si m\u016f\u017eeme o\u010d\u00edslovat a m\u00edsto n\u00e1hodn\u00e9ho v\u00fdb\u011bru vyb\u00edrat nap\u0159\u00edklad v\u017edy ten s\u00a0nejni\u017e\u0161\u00edm identifik\u00e1torem. Jinou mo\u017enost\u00ed je detekovat kmit\u00e1n\u00ed nebo zm\u011bnit ukon\u010dovac\u00ed podm\u00ednku algoritmu a zastavit v p\u0159\u00edpad\u011b, \u017ee u\u017e se chyba shlukov\u00e1n\u00ed nezmen\u0161uje. Nic takov\u00e9ho v\u0161ak standardn\u00ed definice algoritmu neuv\u00e1d\u011bj\u00ed a tvrzen\u00ed, \u017ee k-means v\u017edy konverguje je tedy nespr\u00e1vn\u00e9.<\/p>\n","protected":false},"excerpt":{"rendered":"

    U pohovor\u016f na pozici v\u00fdzkumn\u00edka v Seznamu se pt\u00e1v\u00e1m na principy vybran\u00fdch algoritm\u016f strojov\u00e9ho u\u010den\u00ed, mezi kter\u00e9 pat\u0159\u00ed i k-means pro shlukov\u00e1n\u00ed. Po tom, co algoritmus d\u00e1me dohromady, n\u00e1sleduje ot\u00e1zka, zda je zaru\u010den\u00e9, \u017ee algoritmus v\u017edy skon\u010d\u00ed. Tu\u0161il jsem, \u017ee se daj\u00ed naj\u00edt extr\u00e9mn\u00ed p\u0159\u00edpady, kdy algoritmus m\u016f\u017ee za\u010d\u00edt nekone\u010dn\u011b dlouho kmitat mezi n\u011bkolika stejn\u011b […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"image","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[14],"tags":[],"class_list":["post-306","post","type-post","status-publish","format-image","hentry","category-strojove-uceni","post_format-post-format-image"],"_links":{"self":[{"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/posts\/306","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/comments?post=306"}],"version-history":[{"count":20,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/posts\/306\/revisions"}],"predecessor-version":[{"id":437,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/posts\/306\/revisions\/437"}],"wp:attachment":[{"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/media?parent=306"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/categories?post=306"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/tags?post=306"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}