К-меанс++

У анализи података, к-меанс++^[1]^[2] представља алгоритам који врши одабир почетних вредности (или "семена") за к-меанс цлустеринг алгоритам. Давид Артхур и Сергеи Вассилвитскии су га представили 2007. године, као приближни алгоритам за НП-тежак к-меанс проблем - начин на који се избегава лоше груписање код стандардних к-меанс алгоритама. У самосталном раду, 2006.^[3] Рафаил Островскy, Yувал Рабани, Леонард Сцхулман иЦхаитанyа Сwамy, су представили три метода значења, од којих је првом сличан овај алгоритам. (Дистрибуција првог значења је другачија.)

Развој

К-меанс проблем јесте пронаћи центар груписања који смањује одступање унутар класе, тј. збир квадрата растојања од сваке тачке груписаног податка до његовог центра груписања (њему најближем центру). Иако је проналажење тачног решења за к-меанс проблем за произвољани улаз НП-тежак^[4], стандардни приступ проналажења приближног решења (често назван Лојдов алгоритам или к-меанс алгоритам) је у широкој употреби и често брзо нађе разумљива решења.

Међутим, к-меанс алгоритам има најмање два главна теоријска недостатка:

Прво, показано се да је најгори случај рада алгоритма супер-полиномијално време у почетном стању.^[5]
Друго, пронађена тачност може бити произвољно лоша у односу на објективне функције у поређењу са оптималним груписањем.

К-меанс++ алгоритам превазили другу препреку тако што одређује процедуру за иницијализацију центра груписања пре него што настави са стандардним к-меанс оптимизованим интерацијама.

Са к-меанс++ иницијализацијом, алгоритам гарантује да ће пронаћи решење које је сложености О(лог к) и које је конкурентно оптималном к-меанс решењу.

Пример лошег случаја

Да би илустровали потенцијал к-меанс алгоритма за произвољно слабо извршавање у односу на објективне функције минимизовања, збира квадрата растојања кластера (група) указује на центроид додељених кластера. Пример су 4 тачке из Р² које формирају осно поравнат правоугаоник чија је ширина већа од висине.

Ако је к = 2 и два почетна центра кластера леже на средиштима горње и доње странице правоугаоника формиране од четири тачке података,к-меанс ковергира одмах, без померања ових ценатара кластера. Сходно томе, две доње тачке података су груписане заједно и две тачке података које чине врх правоугаоника су груписане – што је мање од оптималног груписања, јер је ширина правоугаоника већа од његове висине.

Затим, узмимо хоризонтално истезање правоугаоника на произвољну ширину. Стандардни к-меанс ће наставити да групише тачке субоптимално и повећањем хоризонталног растојања између две тачке података у сваком кластеру се може направити да се алгоритам извршава произвољно слабо у односу на објективне функције к-меанс алгоритма.

Алгоритам иницијализације

Интуиција да је ширење к полазног скупа центара добра ствар је иза овог приступа: први центар групе се бира равномерно и насумице из тачака података које су груписане, након чега је сваки следећи кластер центар изабран од преосталих тачака података са вероватноћом пропорционалном са својом квадратом удаљености од најближе тачке за постојеће центре кластера.

Прецизно, алгоритам иде овако:

Равномерно и насумично се бира један центар међу тачакама података.
За сваку тачку података $x$ , израчунава се D( $x$ ), растојање између $x$ и најближег центра који је претходно изабран.
Бира се насумично једна нова тачка која указују на нови центар, помоћу дистрибуције тежинске вероватноће, где је тачка $x$ изабрана са вероватноћом порпорционалном са D( $x$ )².
Кораци 2 и 3 се понављају док се не изабере $к$ центара.
Сада, када су почетни центри изабрани, у настакву се користи к-меанс цлустеринг алгоритам.

Овај метод доноси значајно побољшање код коначне грешке $к$ -меанс-а. Иако почетна селекција у алгоритму захтева додатно време, део $к$ -меанс-а конвергира врло брзо, с тога, алгоритам заиста смањује време израчунавања. . Аутори су тестирали свој метод са реалним и синтетичким скуповима података и добили 2 пута побољшање у брзини, а за одређене скупове података, близу 1000 пута побољшање код грешака. У овим симулацијама нова метода се готово увек извршавала добро барем као ванилла $к$ -меанс и у брзини и што се тиче грешака.

Поред тога, аутори су израчунали приближну сложеност за свој алгоритам. $К$ -меанс++ алгоритам гарантује сложеност О(лог к) где је $k$ број кластера који се користе. То је у супротности са ванилла $к$ -меанс, који може да генерише кластере произвољно лошије од оптимума.^[6]

Примена

К-меанс++ + приступ се користи од кад је први пут представљен. У прегледу,^[7] који укључује многе врсте алгоритама груписања, овај метод је успешно превазишао неке од проблема у вези са другим начинима дефинисања почетних центара кластера за к-меанс цлустеринг. Многи други користе могућност к-меанс++ да створи географски кластер фотографија на основу информације о географској ширини и дужини прикључене фотографији. Финансијску диверсификације су захтевали Хоwард анд Јохансен.^[8] Друга подршка за метод и текуће дискусије су такође доступни онлине.^[9] Пошто к-меанс++ иницијализацији треба к прелаза подацима, није добра размера над великим скуповима података. Бахман Бахмани и др. су предложили прилагодљиву варијанту к-меанс++ названу к-меанс|| која обезбеђује исте теоријске гаранције, а такође је веома скалабилна.^[10]

Софтвер

ЕЛКИ дата-мининг оквир који садржи више к-меанс варијанти, укључујући к-меанс++ за брзину
ГНУ Р укључује к-меанс, а "флеxцлуст" пакети могу да ураде к-меанс++
ОпенЦВ имплементатион
Wека садржи к-меанс (са опционим к-меанс++) и x-меанс цлустеринг.
Апацхе Цоммонс Матх Јава имплементатион

Референце

^ Артхур, D. & Вассилвитскии, С. (2007). „к-меанс++: тхе адвантагес оф царефул сеединг”. Процеедингс оф тхе еигхтеентх аннуал АЦМ-СИАМ сyмпосиум он Дисцрете алгоритхмс. Социетy фор Индустриал анд Апплиед Матхематицс Пхиладелпхиа, ПА, УСА. стр. 1027—1035.
^ Артхур, D.; Вассилвитскии, С. „Слидес фор пресентатион оф метход” (ПДФ).
^ Островскy, Р.; et al. (2006). „Тхе Еффецтивенесс оф Ллоyд-Тyпе Метходс фор тхе к-Меанс Проблем”. Процеедингс оф тхе 47тх Аннуал ИЕЕЕ Сyмпосиум он Фоундатионс оф Цомпутер Сциенце (ФОЦС'06). ИЕЕЕ. стр. 165—174.
^ Дринеас, П.; et al. (2004). „Цлустеринг Ларге Грапхс виа тхе Сингулар Валуе Децомпоситион”. Мацхине Леарнинг. Клуwер Ацадемиц Публисхерс Хингхам, МА, УСА. 56 (1–3): 9—33. дои:10.1023/Б:МАЦХ.0000033113.59016.96.
^ Артхур, D. & Вассилвитскии, С. (2006), Хоw слоw ис тхе к-меанс метход?, АЦМ Неw Yорк, НY, УСА, стр. 144—153
^ Т. Канунго, D. Моунт, Н. Нетанyахуx, C. Пиатко, Р. Силверман, А. Wу "А Лоцал Сеарцх Аппроxиматион Алгоритхм фор к-Меанс Цлустеринг" Архивирано на сајту Wayback Machine (9. фебруар 2006) 2004 Computational Geometry: Theory and Applications.
^ „Approximation Algorithms for the Metric k-Median Problem” (PDF). Архивирано из оригинала 05. 06. 2011. г. Приступљено 31. 05. 2013.
^ http://www.cse.ohio-state.edu/~johansek/clustering.pdf^{[мртва веза]} Цлустеринг Тецхниqуес фор Финанциал Диверсифицатион, Марцх 2009
^ http://lingpipe-blog.com/2009/03/23/arthur-vassilvitskii-2007-kmeans-the-advantages-of-careful-seeding/ Архивирано на сајту Wayback Machine (15. јун 2013) Лингпипе Блог
^ Б. Бахмани, Б. Моселеy, А. Ваттани, Р. Кумар, С. Вассилвитскии "Сцалабле К-меанс++" 2012 Процеедингс оф тхе ВЛДБ Ендоwмент.

[1] Артхур, D. & Вассилвитскии, С. (2007). „к-меанс++: тхе адвантагес оф царефул сеединг”. Процеедингс оф тхе еигхтеентх аннуал АЦМ-СИАМ сyмпосиум он Дисцрете алгоритхмс. Социетy фор Индустриал анд Апплиед Матхематицс Пхиладелпхиа, ПА, УСА. стр. 1027—1035.

[2] Артхур, D.; Вассилвитскии, С. „Слидес фор пресентатион оф метход” (ПДФ).

[3] Островскy, Р.; et al. (2006). „Тхе Еффецтивенесс оф Ллоyд-Тyпе Метходс фор тхе к-Меанс Проблем”. Процеедингс оф тхе 47тх Аннуал ИЕЕЕ Сyмпосиум он Фоундатионс оф Цомпутер Сциенце (ФОЦС'06). ИЕЕЕ. стр. 165—174.

[4] Дринеас, П.; et al. (2004). „Цлустеринг Ларге Грапхс виа тхе Сингулар Валуе Децомпоситион”. Мацхине Леарнинг. Клуwер Ацадемиц Публисхерс Хингхам, МА, УСА. 56 (1–3): 9—33. дои:10.1023/Б:МАЦХ.0000033113.59016.96.

[5] Артхур, D. & Вассилвитскии, С. (2006), Хоw слоw ис тхе к-меанс метход?, АЦМ Неw Yорк, НY, УСА, стр. 144—153

[kanungo-6] Т. Канунго, D. Моунт, Н. Нетанyахуx, C. Пиатко, Р. Силверман, А. Wу "А Лоцал Сеарцх Аппроxиматион Алгоритхм фор к-Меанс Цлустеринг" Архивирано на сајту Wayback Machine (9. фебруар 2006) 2004 Computational Geometry: Theory and Applications.

[7] „Approximation Algorithms for the Metric k-Median Problem” (PDF). Архивирано из оригинала 05. 06. 2011. г. Приступљено 31. 05. 2013.

[8] ttp://www.cse.ohio-state.edu/~johansek/clustering.pdf^{[мртва веза]} Цлустеринг Тецхниqуес фор Финанциал Диверсифицатион, Марцх 2009

[9] ttp://lingpipe-blog.com/2009/03/23/arthur-vassilvitskii-2007-kmeans-the-advantages-of-careful-seeding/ Архивирано на сајту Wayback Machine (15. јун 2013) Лингпипе Блог

[kmeans||-10] Б. Бахмани, Б. Моселеy, А. Ваттани, Р. Кумар, С. Вассилвитскии "Сцалабле К-меанс++" 2012 Процеедингс оф тхе ВЛДБ Ендоwмент.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]