Пређи на садржај

Кластеризација методом K-средњих вредности

С Википедије, слободне енциклопедије

U analizi podataka, klasterizacija metodom k-srednjih vrednosti (engl. k-means clustering) метод је за анализу груписања чији је циљ партиционисање н опсервација у к кластера у којем свака опсервација припада кластеру са најсличнијим значењем. Ово резултује партиционисањем простора за податке у Воронои ћелије.

Овај проблем је рачунарски тежак (НП-тежак), ипак постоје ефиаксни хеуристички алгоритми који се често примењују и брзо конвергирају ка локалном оптимуму. Они су често слични алгоритму очекиване минимизације за мешавине Гаусових расподела путем итеративног приступа пречишћавања заступљеног код оба алгоритма. Поред тога, оба користе цетре кластера (група) да би обликовали податак. Ипак, кластеризација медотом к-средњих вредности тежи да нађе кластере упоредивог просторног обима, док механизам алгоритма очекиване минимизације дозвољава да кластер има различите облике.

Опис[уреди | уреди извор]

Дат је скуп опсервација (x1, x2, …, xн), где је свака опсервација д-димензионалан реалан вектор. Циљ овог метода је да пратиционише н опсервација у к скупова (к ≤ н) С = {С1, С2, …, Ск}, тако да минимизује суму квадрата унутар кластера (енгл. within-cluster sum of squares - WCSS).

Где је μи главна тачка у Си.

Историја[уреди | уреди извор]

Израз „к-меанс” је први употребио Џејмс Макквид 1967. године,[1] иако је први дошао на идеју Гуго Штејнгауз 1957.[2] Стандардни алгоритам је први представио Стјуарт Лојд 1957. као технику за импулсивну кодну модулацију, мада није објављена ван Белових лабораторија до 1982.[3] Е. V. Форги је 1956. објавио есенциално исти метод, због чега га некад називају и Лојд-Форгијев метод.[4] Хартиган и Вонг су представили ефикаснију верзију и објавили је у Фортрану 1975/1979.[5][6]

Алгоритми[уреди | уреди извор]

Стандардни алгоритам[уреди | уреди извор]

Најчешћи алгоритам користи итеративне технике пречишћавања. Упркос великој присутности често се назива к-менас алгоритам, а такође и Лојдов алгоритам, нарочито у рачунарском друштву.

Након што се алгоритму да иницијални сет к меанс м1(1),…,мк(1) (погледати испод), алгоритам ради тако што алтернира између 2 корака:[7]

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

Алгоритам се зауставља када у кораку додељивања више нема промена.

Методе иницијализације[уреди | уреди извор]

Најчешће кориштене медоте иницијализације су Форгy и Рандом Партитион.[8] Форгy метода насумично бира к опсервација из сета података и користи их као иницијална значења. Рандом Партитион прво насумично додељује кластере опсервацијама, а онда прелази на корак ажурирања, затим рачуна иницијална значења која ће бити центри тачака насумично додељени кластерима. Форгy метод тежи да раздваја иницијална значања, док их Рандом Партитион приближава центру сету података. Према Хамерлy, и др.,[8] Рандом Партитион метод се генерално више преферира за алгоритме као што су к-хармониц меанс и фуззy к-меанс. За алгоритам очекиване минимизације и стандардни к-меанс алгоритам, преферира се Форгy метод.

  • Демонстрација стандардног алгоритма
  • 1) к инитиал "меанс" (ин тхис цасе к=3) аре рандомлy генератед wитхин тхе дата домаин (схоwн ин цолор).
    1) к инитиал "меанс" (ин тхис цасе к=3) аре рандомлy генератед wитхин тхе дата домаин (схоwн ин цолор).
  • 2) к цлустерс аре цреатед бy ассоциатинг еверy обсерватион wитх тхе неарест меан. Тхе партитионс хере репресент тхе Воронои диаграм генератед бy тхе меанс.
    2) к цлустерс аре цреатед бy ассоциатинг еверy обсерватион wитх тхе неарест меан. Тхе партитионс хере репресент тхе Воронои диаграм генератед бy тхе меанс.
  • 3) Тхе центроид оф еацх оф тхе к цлустерс бецомес тхе неw меан.
    3) Тхе центроид оф еацх оф тхе к цлустерс бецомес тхе неw меан.
  • 4) Степс 2 анд 3 аре репеатед унтил цонвергенце хас беен реацхед.
    4) Степс 2 анд 3 аре репеатед унтил цонвергенце хас беен реацхед.

Пошто је ово хереутички алгоритам, не гарантује се да ће конвергирати га глобалном оптимуму, такође, резултат може да зависи од иницијалних кластера. Пошто је алгоритам углавном врло брз, често се покреће више пута са различитим почетним условима. Ипак, у најгорем случају к-меанс може да се извршава врло споро: кокретно, показано је да постоји одређени сет тачака, чак и у 2 димензије, у којима к-меанс има експоненцијално време извршавања 2Ω(н).[9] Овај сет тачака се углавном не појављује у пракси, што је поткрепљено чињеницом да је глатко време извршава к-менас алгоритма полиномијално.[10]

Корак додељивања се назива и корак очекивања, а корак ажурирања корак максимизације, чиме алготирам постаје варијанта алгортитма очекиване минимизације.

Сложеност[уреди | уреди извор]

У односу на рачунарску сложеност, к-менас цлустеринг проблем обсервација у д димензијама је:

  • НП-тежак у Еуклидовом простору д, чак и за 2 кластера[11][12]
  • НП-тежак за уопштен број кластера к[13]
  • Ако су к и д (димензија) поправљене, проблем може бити прецизно решен у времену О(ндк+1 лог н), где је н број целина које треба груписати[14]

Такође, више хеуристичких алгоритма се генерано користе.

  • -меанс је разматран изнад глатког полиномијалног времена. Показано је да[10] је за произвољан сет од тачака , ако је свака тачка независно померена од стране нормалне расподеле са значењем и неслагањем , онда је очекивано време извршавања -меанс алгоритма ограничено на , што је полиномијално у , , и .
  • Боље огрнаичење је доказано за једноставне случајеве. На пример,[15] показано је да време извршавања -меанс алгоритам ограничено на за тачка у мрежи интеџера .

Варијације[уреди | уреди извор]

  • Кластеризација методом фази C-средњих вредности је блажа верзија К-меанс, где свака тачка података има фруззy степен припадности за сваки кластер.
  • Гаусов модел мешавине у комбинацији са алгоритмом очекиване минимизације (ЕМ алгоритам) одржава вероватноћу доделе калстеру.
  • Неколико метода је предложено за избор бољих почетних класетра. Један од новијих предлога је к-менас++.
  • Алгортам пречишћавања користи К-D стабло да би убрзао сваки к-менас корак.[16]
  • Неке методе намеравају да убрзају сваки к-менас корак коришћењем корсета[17] или неједнакости троугла.[18]
  • збегавање локалног оптимума замењујући тачке између кластера.[6]
  • Спхерицал к-меанс цлустеринг алгоритам је примерен за усмерене подарке.[19]
  • Минкоwски метриц wеигхтед к-меанс се суочава са проблемом буке[20]

Дискусија[уреди | уреди извор]

Типичан пример коневргенције к-меанс алгоритма ка локалном минимуму.[21]

Две главне карактеристике к-менас алгоритма које га чини ефикасним су често и његови највећи недостаци::

  • Еуклидско растојање се користи као метрика, а диспрезија као мера расутости кластера.
  • Број кластера к је улазни параметар, лош избор к може проузроковати лоше резултате. Због тога, кад се извршава к-менас алгоритам важно је покренути дијагностичку проверу за одређивање броја кластера у сету података
  • Конвергенција ка локалном минимуму може проузроковати погрешне ‘резултате’

Кључно ограничење к-менас алгоритма је модел кластера. Концепт је базиран на сферним кластерима који се раздвајају на такав начин да вредност значења конвергира ка центру кластера. Кластери би требало да буду сличне величине, да би додељивање најближем центру кластера било испавно. На пример, када се примењује к-меанс за вредности к=3 на добро познати сет података цвета Ирис, резултат често не уради раздвајање 3 врсте Ириса које су у сету података. Са к=2, два видљива кластера (сваки садржи 2 врсте) ће бити откривени, а кад је к=3, један од 2 кластера ће бити подељен на два једнака дела. Дакле, к=2 је прикладнији за сет података, иако садржи 3 класе. Као и код осталих алгоритама за груписање, резултати к-менас алгоритма се заснивају на томе да сет података задовољи претпоставке које је направио алгоритам за груписање. За неке случајеве ради добро, за неке не.

Резултат к-менас алгоритма се може приказати и као Воронои ћелије значења кластера. Кад се податак подели између значења кластера, то може довести до субоптималног дељења, као у примеру ‘моусе’. Гаусови модели, које користи ЕМ алгоритам (који се може гледати као генерализација к-менас алгоритма), су флексибилнији овде, јер имају и разлике и коваријансе. Резултат ЕМ-аа може да смести кластере варљиве величинине много боље него к-менас, као и повезане калстере (не у овом примеру).

Примена[уреди | уреди извор]

К-меанс цлустеринг је, конкретно када користи хеуристике као што је Ллоyдов алгоритам, лак за имплементацију и примењивање на велики сет података. Због тога, успешно се користи у разним областима, почев од сегментације тржишта, рачунарског вида, геостатике[22] и астрономије до агрокултуре. Често се користи као корак претпроцесирања за друге алгоритме, нпр. за проналажење почетне конфигураије.

Учење за (семи-)надгледане класификације[уреди | уреди извор]

К-меанс цлустеринг к-менас цлутеринг је кориштен за као корак за семи-надгледано учење.[23] У овој употреби, клатеровање се изводи у великом сету података, који треба да се означи. Онда се извршава учење нагдледањем и за сваки означени узорак раздаљина за сваки од к научених централних кластера је компијутеризована да би подстакла к еxтра одлика за узорак. Одлике могу бити буловске са вредношћу 1 за затворене центре[24] или нека глатка трансформација за далеке трансфомришући узорак кластера кроз Гаусов РБФ, он садржи сакривене слојеве радијалне основне мреже функције.[25]

Ова употреба к-менас аа је успешно комбинована са једниставним, линеарним класификатором за семи-недгледаноучење у обради природних језика и у компијутерском виду.

Однос са другим алгоритмима за статичко машинско учење[уреди | уреди извор]

К-меанс цлустеринг, и његов придружени алгоритам ЕМ, у специјалном случају Гаусовог модела мешавине, конкретно, лимит узимања коваријански као дијагоналне, једнаке и мале. Некад је једноставно уопштити к-менас проблем у Гаусов метод мешавине..[26]

Меан схифт цлустеринг[уреди | уреди извор]

Основни mean shift садржи скуп тачака података исте величине као улазни сет података. Иницијално, овај сет је копирам од улазног сета. Онда је овај сет итеративно премештен на основу значења оних тачака у сету који су на одређеној удаљености од те тачке. К-менас ограничава овај промењен сет на к тачака углавном много мањим него број тачака у улазном сету података и замењује их сетом по значењу свих тачака у улазном сету које су ближе тој тачки од осталих. Меан схифт алгоритам, који је сличан к-меанс алгоритму се зове и ликелихоод менас схифт, замењује сет тачака тренутне размене по значењу свих тачака у улазном сету које су у оквиру задате раздаљине сета који се мења.[27] Једна од преднсоти меан схифт алгоритма у односу на к-менас је што нема потребе да се бира број кластера, јер меан схирт углавном нађе врло мало кластера, ако мали број постоји. Ипак, меан схифт може бити спорији од к-менас алгоритма и још увек захтева селекцију пропусног опсега параметра. Мена схифт има варијанте као и к-менас.

Анализа основних компоненти (ПЦА)[уреди | уреди извор]

Трвди се[28][29] да је 'опуштено' решење к-меанс цлустеринг, спрецификовано од стране индокатора кластера, дато од стране ПЦА (Метод главних компоненти) основне компонете и да је ПЦА међупростор проширен основним упутствима идентичан централном међупростору кластера. Ипак, није ново да је ПЦА корисна опуштање к-меанса (погледати, нпр.[30]), и да иде ка неотрктивеним контрапримерима тврдње да је међупростор центра калстера проширен.

Билатерално пречишћавање[уреди | уреди извор]

к-меанс имплицитно претпоставља да редослед улазног сета података небитан. Билатерални филтер је сличан к-менасу по томе што одржава сет тачака података које су итеративно премештене на основу значења. Ипак, он ограничава израчунавање значења да би укључио само тачке коју су близу на основу редоследа уноса. Ово га чини применљивим за проблеме као што је имаге деноисинг, где је просторна расподела пиксела од велике важности.[27] Тхис макес ит апплицабле то проблемс суцх ас имаге деноисинг, wхере тхе спатиал аррангемент оф пиxелс ин ан имаге ис оф цритицал импортанце.

Слични проблеми[уреди | уреди извор]

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

Софтвер[уреди | уреди извор]

Бесплатан[уреди | уреди извор]

Комерцијални[уреди | уреди извор]

Изворни код[уреди | уреди извор]

  • ЕЛКИ и Wека су написани у Јави и укључују к-средње вредности и варијације
  • примена К-средњих вредности у ПХП-у,[31] коришћење ВБ,[32] коришћење Перл,[33] коришћење C++,[34] коришћење Матлаб,[35] коришћење Рубy,[36][37] коришћење Пyтхон wитх сципy,[38] усинг X10[39]
  • паралелна out-of-core имплементација у C-у[40]
  • колекција отвореног кода кластеринг алгоритама, укључујући к-средње вредности, имплентирано у Јаваскрипту[41] Онлине демо.[42]

Визуализација, анимација и примери[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ а б MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1. University of California Press. str. 281—297. MR 0214227. Zbl 0214.46201. Pristupljeno 7. 4. 2009. 
  2. ^ Steinhaus, H. (1957). „Sur la division des corps matériels en parties”. Bull. Acad. Polon. Sci. 4 (12): 801—804. MR 0090073. Zbl 0079.16403. 
  3. ^ а б Lloyd, S. P. (1957). „Least square quantization in PCM”. Bell Telephone Laboratories Paper.  Публисхед ин јоурнал муцх латер: Lloyd., S. P. (1982). „Least squares quantization in PCM” (PDF). IEEE Transactions on Information Theory. 28 (2): 129—137. doi:10.1109/TIT.1982.1056489. Pristupljeno 15. 4. 2009. 
  4. ^ E.W. Forgy (1965). „Cluster analysis of multivariate data: efficiency versus interpretability of classifications”. Biometrics. 21: 768—769. 
  5. ^ J.A. Hartigan (1975). Clustering algorithms. John Wiley & Sons, Inc. 
  6. ^ а б в Hartigan, J. A.; Wong, M. A. (1979). „Algorithm AS 136: A K-Means Clustering Algorithm”. Journal of the Royal Statistical Society, Series C. 28 (1): 100—108. JSTOR 2346830. 
  7. ^ MacKay, David (2003). „Chapter 20. An Example Inference Task: Clustering” (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. str. 284—292. ISBN 978-0-521-64298-9. MR 2012999. 
  8. ^ а б Hamerly, G. & Elkan, C. (2002). „Alternatives to the k-means algorithm that find better clusterings” (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). Arhivirano iz originala (PDF) 7. 11. 2006. g. 
  9. ^ Vattani., A. (2011). „k-means requires exponentially many iterations even in the plane” (PDF). Discrete and Computational Geometry. 45 (4): 596—616. doi:10.1007/s00454-011-9340-1. 
  10. ^ а б Arthur, D.; Manthey, B.; Roeglin, H. (2009). „k-means has polynomial smoothed complexity”. Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). 
  11. ^ Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). „NP-hardness of Euclidean sum-of-squares clustering”. Machine Learning. 75: 245—249. doi:10.1007/s10994-009-5103-0. 
  12. ^ Dasgupta, S. & Freund, Y. (2009). „Random Projection Trees for Vector Quantization”. Information Theory, IEEE Transactions on. 55: 3229—3242. arXiv:0805.1390 Slobodan pristup. doi:10.1109/TIT.2009.2021326. 
  13. ^ Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). „The Planar k-Means Problem is NP-Hard”. Lecture Notes in Computer Science. 5431: 274—285. doi:10.1007/978-3-642-00202-1_24. 
  14. ^ Inaba, M.; Katoh, N.; Imai, H. (1994). Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering. Proceedings of 10th ACM Symposium on Computational Geometry. str. 332—339. doi:10.1145/177424.178042. 
  15. ^ Артхур Абхисхек Бхоwмицк (2009). А тхеоретицал аналyсис оф Ллоyд'с алгоритхм фор к-меанс цлустеринг (Теза). 
  16. ^ Kanungo, T.; et al. (2002). „An efficient k-means clustering algorithm: Analysis and implementation” (PDF). IEEE Trans. Pattern Analysis and Machine Intelligence. 24: 881—892. doi:10.1109/TPAMI.2002.1017616. Pristupljeno 24. 4. 2009. 
  17. ^ Frahling, G.; Sohler, C. (2006). „A fast k-means implementation using coresets” (PDF). Proceedings of the twenty-second annual symposium on Computational geometry (SoCG). Arhivirano iz originala (PDF) 5. 7. 2010. g. 
  18. ^ Elkan, C. (2003). „Using the triangle inequality to accelerate k-means” (PDF). Proceedings of the Twentieth International Conference on Machine Learning (ICML). 
  19. ^ Dhillon, I. S.; Modha, D. M. (2001). „Concept decompositions for large sparse text data using clustering”. Machine Learning. 42 (1): 143—175. 
  20. ^ Amorim, R. C.; Mirkin, B (2012). „Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering”. Pattern Recognition. 45 (3): 1061—1075. doi:10.1016/j.patcog.2011.08.012. 
  21. ^ а б Е.M. Миркес, К-меанс анд К-медоидс апплет Архивирано на сајту Wayback Machine (29. мај 2013). Университy оф Леицестер, 2011.
  22. ^ Хонаркхах, Мехрдад; Цаерс, Јеф (2010). „Стоцхастиц Симулатион оф Паттернс Усинг Дистанце-Басед Паттерн Моделинг”. Матхематицал Геосциенцес. 42 (5): 487—517. Бибцоде:2010МаГео..42..487Х. С2ЦИД 73657847. дои:10.1007/с11004-010-9276-7. 
  23. ^ Цоатес, Адам; Нг, Андреw Y. (2012). „Леарнинг феатуре репресентатионс wитх к-меанс” (ПДФ). Ур.: Г. Монтавон, Г. Б.; et al. Неурал Нетwоркс: Трицкс оф тхе Траде. Спрингер. Архивирано из оригинала (ПДФ) 6. 6. 2013. г. 
  24. ^ Csurka, Gabriella; Dance, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). Visual categorization with bags of keypoints (PDF). ECCV Workshop on Statistical Learning in Computer Vision. 
  25. ^ Schwenker, Friedhelm; Kestler, Hans A.; Palm, Günther (2001). „Three learning phases for radial-basis-function networks”. Neural Networks. 14: 439—458. 
  26. ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Section 16.1. Gaussian Mixture Models and k-Means Clustering”. Numerical Recipes: The Art of Scientific Computing (3rd izd.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. 
  27. ^ а б Little, M.A.; Jones, N.S. (2011). „Generalized Methods and Solvers for Piecewise Constant Signals: Part I” (PDF). Proc. Roy. Soc. A. 
  28. ^ H. Zha; et al. (2001). „Spectral Relaxation for K-means Clustering” (PDF). Neural Information Processing Systems vol.14 (NIPS 2001). Vancouver, Canada: 1057—1064. 
  29. ^ Ding, Chris; Xiaofeng He (2004). „K-means Clustering via Principal Component Analysis” (PDF). Proc. of Int'l Conf. Machine Learning (ICML 2004): 225—232. 
  30. ^ Drineas, P.; A. Frieze; et al. (2004). „Clustering large graphs via the singular value decomposition” (PDF). Machine learning. 56: 9—33. Pristupljeno 2. 8. 2012. 
  31. ^ „Архивирана копија”. Архивирано из оригинала 23. 10. 2007. г. Приступљено 23. 10. 2007. 
  32. ^ K-Means Clustering Tutorial: Download
  33. ^ „Perl script for Kmeans clustering[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 18. 06. 2012. г. Приступљено 01. 06. 2013.  Сукоб URL—викивеза (помоћ)
  34. ^ Antonio Gulli's coding playground: K-means in C
  35. ^ K-Means Clustering Tutorial: Matlab Code
  36. ^ AI4R :: Artificial Intelligence for Ruby
  37. ^ „reddavis/K-Means · GitHub[[Категорија:Ботовски наслови]]”. GitHub. Архивирано из оригинала 08. 07. 2012. г. Приступљено 08. 07. 2012.  Сукоб URL—викивеза (помоћ)
  38. ^ K-means clustering and vector quantization (scipy.cluster.vq) — SciPy v0.11 Reference Guide (DRAFT)
  39. ^ „Архивирана копија”. Архивирано из оригинала 09. 07. 2012. г. Приступљено 09. 07. 2012. 
  40. ^ https://web.archive.org/web/20110607074701/http://www.cs.princeton.edu/~wdong/kmeans/
  41. ^ http://code.google.com/p/figue/ FIGUE
  42. ^ „Interactive Demo of figue[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 06. 07. 2011. г. Приступљено 06. 07. 2011.  Сукоб URL—викивеза (помоћ)
  43. ^ Clustering - K-means demo
  44. ^ siebn.de - YAK-Means
  45. ^ k-Means and Voronoi Tesselation: Built with Processing | Information & Visualization
  46. ^ [„Hyper-threaded Java - JavaWorld[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 02. 06. 2013. г. Приступљено 01. 06. 2013.  Сукоб URL—викивеза (помоћ) Hyper-threaded Java - JavaWorld]
  47. ^ Color clustering
  48. ^ Clustergram: visualization and diagnostics for cluster analysis (R code) | R-statistics blog
Преузето из „https://sr.wikipedia.org/w/index.php?title=Klasterizacija_metodom_K-srednjih_vrednosti&oldid=27751440”