www.wikidata.uk-ua.nina.az

Ієрархічна кластеризація англ hierarchical cluster analysis HCA в добуванні даних та статистиці метод кластерного аналіз

Ієрархічна кластеризація

Ієрархічна кластеризація (англ. hierarchical cluster analysis, HCA) в добуванні даних та статистиці — метод кластерного аналізу, який намагається побудувати ієрархію кластерів. Стратегії побудови ієрархічної кластеризації діляться на два типи:

  • агломератові (об'єднувальні). Це підхід «знизу-вгору[en]». Спочатку кожна точка має власний кластер, а далі пари кластерів об'єднуються при підйомі по ієрархії.
  • розділювальні. Це підхід «згори-вниз[en]». Спочатку всі точки знаходяться у єдиному кластері, потім відбувається рекурсивне розбиття при русі вниз по ієрархії.

Зазвичай розбиття та об'єднання визначаються у жадібний спосіб. Отриману ієрархію типово зображають як дендрограму[en].

Стандартний алгоритм ієрархічної кластеризації має часову складність та потребує пам'яті, що занадто повільно навіть для наборів даних середнього розміру. Однак, для деяких випадків, є агломератові методи, які виконуються за час . Це методи SLINK при однозв'язній та CLINK при повнозв'язній кластеризації[en]. Використання купи дозволяє у загальному випадку скоротити час виконання до ціною збільшення вимог до об'єму пам'яті. Такі накладні витрати на пам'ять, для багатьох мов програмування, роблять цей підхід неможливим для реалізації.

Окрім спеціального однозв'язного випадку немає алгоритмів (окрім повного перебору за час ), який би гарантував оптимальний розв'язок.

Розділювальна кластеризація з повним перебором виконується за час , проте звичайною практикою є використання більш швидких евристик для розбиття, такі як k-середні.

Дендрограма ред.

Дендрограма

Під дендрограмою зазвичай розуміється дерево, тобто граф без циклів побудований за матриці заходів близькості. Дендрограма дозволяє зобразити взаємні зв'язки між об'єктами з заданого переліку. Для створення дендрограми потрібно матриця подібності (чи відмінності), яка визначає рівень спорідненості між парами об'єктів. Частіше використовуються агломеративні методи.

Далі необхідно вибрати метод побудови дендрограми, який визначає метод візуалізації матриці подібності (чи відмінності) після об'єднання (або поділу) чергових двох об'єктів в кластер.

У роботах по кластерному аналізу описаний досить значний ряд способів побудови (англ. sorting strategies) дендрограмм:

  1. Метод одиночного зв'язку (англ. single linkage). Також відомий як «метод найближчого сусіда».
  2. Метод повного зв'язку (англ. complete linkage). Також відомий як «метод далекого сусіда».
  3. Метод середнього зв'язку (англ. pair-group method using arithmetic averages).
  1. Центроїдний метод (англ. pair-group method using the centroid average).
  • Незважений.
  • Зважений (медіанний).
  1. Метод Уорда (англ. Ward's method).

Для перших трьох методів існує загальна формула, запропонована А. Н. Колмогоровим для заходів подібності:

де  — група з двох об'єктів (кластерів) і ;  — об'єкт (кластер), з яким шукається схожість зазначеної групи;  — кількість елементів у кластері ;  — кількість елементів у кластері . Для відстаней є аналогічна формула Ланса — Вільямса.

Центроїдний метод використовує для перерахунку матриці відстаней. Як відстані між двома кластерами у цьому методі береться відстань між центрами тяжіння.

У методі Уорда як відстані між кластерами береться приріст суми квадратів відстаней об'єктів до центрів кластерів, що отримується в результаті їх об'єднання. На відміну від інших методів кластерного аналізу для оцінки відстаней між кластерами, тут використовуються методи дисперсійного аналізу. На кожному кроці алгоритму об'єднуються такі два кластери, які призводять до мінімального збільшення цільової функції, тобто внутрішньогрупової суми квадратів. Цей метод спрямований на об'єднання близько розташованих кластерів.

Кореляційні плеяди ред.

Дендрит

Широко застосовуються в геоботаніці та флористиці. Їх часто називають «кореляційними плеядами».

Окремим випадком є метод, відомий як метод побудови «оптимальних дерев (дендритів)», який був запропонований математиком львівської школи Гуго Штейнгаузом, згодом метод був розвинений математиками вроцлавської таксономічної школи. Дендрити також не повинні утворювати циклів. Можна частково використовувати спрямовані дуги графів при використанні додатково заходів включення (несиметричних заходів подібності).

Діаграма Чекановського ред.

Метод «діагоналізації» матриці відмінності і графічне зображення кластерів уздовж головної діагоналі матриці відмінності (діаграма Чекановського) вперше запропонований Яном Чекановським у 1909 році. Наведемо опис методики:

Суть цього методу полягає в тому, що всю амплітуду отриманих величин подібності розбивають на ряд класів, а потім в матриці величин подібності замінюють ці величини штрихуванням, різної для кожного класу, причому зазвичай для більш високих класів подібності застосовують темніше штрихування. Потім, змінюючи порядок описів в таблиці, домагаються того, щоб подібні описи були розташовані поруч

Наведемо гіпотетичний приклад отримання такої діаграми. Основою методу є побудова матриці транзитивного замикання.

Приклад розрахунку діаграми Чекановского

Для побудови матриці транзитивного замикання візьмемо просту матрицю подібності і помножимо її на саму себе:

,

де  — елемент, що стоїть на перетині -го рядка -го стовпця в новій (другій) матриці, отриманій після першої ітерації;  — загальна кількість рядків (стовпчиків) матриці подібності. Дану процедуру необхідно продовжувати поки матриця не стане ідемпотентною (тобто самоподібною): , де  — кількість ітерацій.

Далі перетворюємо матрицю таким чином, щоб близькі числові значення знаходилися поряд. Якщо кожному числовому значенню поставити у відповідність будь-який колір або відтінок кольору (як у нашому випадку), то отримаємо класичну діаграму Чекановського. Традиційно темніший колір відповідає більшій подібності, а світліший — меншій. В цьому вона схожа з теплокартою матриці відстаней.

Див. також ред.

Примітки ред.

  1. Rokach, Lior, and Oded Maimon. «Clustering methods.» Data mining and knowledge discovery handbook. Springer US, 2005. 321—352.
  2. ↑ Schütze, Hinrich Christopher D. Manning Raghavan, Prabhakar (2008). . Cambridge, UK: Cambridge University Press. ISBN 0-521-86571-9. Архів оригіналу за 12 листопада 2018.
  3. «Жамбю М.» Ієрархічний кластер-аналіз та відповідності. — М.: Финансы и статистика, 1988. — 345 с.
  4. Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
  5. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.
  6. «Lance G.N., Willams W.T.» A general theory classification of sorting strategies. 1. Hierarchical systems // Comp. J. 1967. № 9. P. 373—380.
  7. «Sneath P.H.A., Sokal R.R.» Numerical taxonomy: The principles and practices of numerical classification. — San-Francisco: Freeman, 1973. — 573 p.
  8. «Ward J.H.» Hierarchical grouping to optimize an objective function // J. of the American Statistical Association, 1963. — 236 р.
  9. «von Terentjev P.V.» Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) [ 5 березня 2016 у Wayback Machine.] // Biometrika. 1931. № 23(1-2). P. 23-51.
  10. «Терентьєв П. У.» Метод кореляційних плеяд // Вісн. ЛДУ. № 9. 1959. С. 35-43.
  11. «Терентьєв П. У.» Подальший розвиток методу кореляційних плеяд // Застосування математичних методів в біології. Т. 1. Л.: 1960. С. 42-58.
  12. «Выханду Л. К.» Про дослідженні многопризнаковых біологічних систем // Застосування математичних методів в біології. Л.: вып. 3. 1964. С. 19-22.
  13. «Штейнгауз Р.» Математичний калейдоскоп. — М.: Наука, 1981. — 160 с.
  14. «Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S.» Taksonomia Wroclawska // Przegl. antropol. 1951. T. 17. S. 193—211.
  15. «Czekanowski J.» Zur differential Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
  16. Василевич В. И. Статистические методы в геоботанике. — Л.: Наука, 1969. — 232 с.
  17. «Tamura S., Hiquchi S., Tanaka K.» Pattern classification based on fuzzy relation [ 17 травня 2017 у Wayback Machine.] // IEEE transaction on systems, man, and cybernetics, 1971, SMC 1, № 1, P. 61-67.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Iyerarhichna klasterizaciya angl hierarchical cluster analysis HCA v dobuvanni danih ta statistici metod klasternogo analizu yakij namagayetsya pobuduvati iyerarhiyu klasteriv Strategiyi pobudovi iyerarhichnoyi klasterizaciyi dilyatsya na dva tipi 1 aglomeratovi ob yednuvalni Ce pidhid znizu vgoru en Spochatku kozhna tochka maye vlasnij klaster a dali pari klasteriv ob yednuyutsya pri pidjomi po iyerarhiyi rozdilyuvalni Ce pidhid zgori vniz en Spochatku vsi tochki znahodyatsya u yedinomu klasteri potim vidbuvayetsya rekursivne rozbittya pri rusi vniz po iyerarhiyi Zazvichaj rozbittya ta ob yednannya viznachayutsya u zhadibnij sposib Otrimanu iyerarhiyu tipovo zobrazhayut yak dendrogramu en Standartnij algoritm iyerarhichnoyi klasterizaciyi maye chasovu skladnist O n3 displaystyle mathcal O n 3 ta potrebuye O n2 displaystyle mathcal O n 2 pam yati sho zanadto povilno navit dlya naboriv danih serednogo rozmiru Odnak dlya deyakih vipadkiv ye aglomeratovi metodi yaki vikonuyutsya za chas O n2 displaystyle mathcal O n 2 Ce metodi SLINK 2 3 pri odnozv yaznij ta CLINK 4 3 pri povnozv yaznij klasterizaciyi en Vikoristannya kupi dozvolyaye u zagalnomu vipadku skorotiti chas vikonannya do O n2log n displaystyle mathcal O n 2 log n cinoyu zbilshennya vimog do ob yemu pam yati Taki nakladni vitrati na pam yat dlya bagatoh mov programuvannya roblyat cej pidhid nemozhlivim dlya realizaciyi Okrim specialnogo odnozv yaznogo vipadku nemaye algoritmiv okrim povnogo pereboru za chas O 2n displaystyle mathcal O 2 n yakij bi garantuvav optimalnij rozv yazok Rozdilyuvalna klasterizaciya z povnim pereborom vikonuyetsya za chas O 2n displaystyle mathcal O 2 n prote zvichajnoyu praktikoyu ye vikoristannya bilsh shvidkih evristik dlya rozbittya taki yak k seredni Zmist 1 Dendrograma 2 Korelyacijni pleyadi 3 Diagrama Chekanovskogo 4 Div takozh 5 PrimitkiDendrograma red nbsp DendrogramaPid dendrogramoyu zazvichaj rozumiyetsya derevo tobto graf bez cikliv pobudovanij za matrici zahodiv blizkosti Dendrograma dozvolyaye zobraziti vzayemni zv yazki mizh ob yektami z zadanogo pereliku 5 Dlya stvorennya dendrogrami potribno matricya podibnosti chi vidminnosti yaka viznachaye riven sporidnenosti mizh parami ob yektiv Chastishe vikoristovuyutsya aglomerativni metodi Dali neobhidno vibrati metod pobudovi dendrogrami yakij viznachaye metod vizualizaciyi matrici podibnosti chi vidminnosti pislya ob yednannya abo podilu chergovih dvoh ob yektiv v klaster U robotah po klasternomu analizu opisanij dosit znachnij ryad sposobiv pobudovi angl sorting strategies dendrogramm 6 Metod odinochnogo zv yazku angl single linkage Takozh vidomij yak metod najblizhchogo susida Metod povnogo zv yazku angl complete linkage Takozh vidomij yak metod dalekogo susida Metod serednogo zv yazku angl pair group method using arithmetic averages Nezvazhenij angl unweighted Zvazhenij angl weighted Centroyidnij metod angl pair group method using the centroid average Nezvazhenij Zvazhenij mediannij Metod Uorda angl Ward s method Dlya pershih troh metodiv isnuye zagalna formula zaproponovana A N Kolmogorovim dlya zahodiv podibnosti 7 Kh i j k niK i k h njK j k h ni nj 1h 1 h 1 displaystyle K eta i j k left frac n i K i k eta n j K j k eta n i n j right frac 1 eta mathcal 1 leqslant eta leqslant mathcal 1 nbsp de i j displaystyle i j nbsp grupa z dvoh ob yektiv klasteriv i j displaystyle j nbsp k displaystyle k nbsp ob yekt klaster z yakim shukayetsya shozhist zaznachenoyi grupi ni displaystyle n i nbsp kilkist elementiv u klasteri displaystyle nj displaystyle n j nbsp kilkist elementiv u klasteri j displaystyle j nbsp Dlya vidstanej ye analogichna formula Lansa Vilyamsa 8 Centroyidnij metod vikoristovuye dlya pererahunku matrici vidstanej 9 Yak vidstani mizh dvoma klasterami u comu metodi beretsya vidstan mizh centrami tyazhinnya U metodi Uorda yak vidstani mizh klasterami beretsya pririst sumi kvadrativ vidstanej ob yektiv do centriv klasteriv sho otrimuyetsya v rezultati yih ob yednannya 10 Na vidminu vid inshih metodiv klasternogo analizu dlya ocinki vidstanej mizh klasterami tut vikoristovuyutsya metodi dispersijnogo analizu Na kozhnomu kroci algoritmu ob yednuyutsya taki dva klasteri yaki prizvodyat do minimalnogo zbilshennya cilovoyi funkciyi tobto vnutrishnogrupovoyi sumi kvadrativ Cej metod spryamovanij na ob yednannya blizko roztashovanih klasteriv Korelyacijni pleyadi red nbsp DendritShiroko zastosovuyutsya v geobotanici ta floristici Yih chasto nazivayut korelyacijnimi pleyadami 11 12 13 14 Okremim vipadkom ye metod vidomij yak metod pobudovi optimalnih derev dendritiv yakij buv zaproponovanij matematikom lvivskoyi shkoli Gugo Shtejngauzom 15 zgodom metod buv rozvinenij matematikami vroclavskoyi taksonomichnoyi shkoli 16 Dendriti takozh ne povinni utvoryuvati cikliv Mozhna chastkovo vikoristovuvati spryamovani dugi grafiv pri vikoristanni dodatkovo zahodiv vklyuchennya nesimetrichnih zahodiv podibnosti Diagrama Chekanovskogo red Metod diagonalizaciyi matrici vidminnosti i grafichne zobrazhennya klasteriv uzdovzh golovnoyi diagonali matrici vidminnosti diagrama Chekanovskogo vpershe zaproponovanij Yanom Chekanovskim u 1909 roci 17 Navedemo opis metodiki Sut cogo metodu polyagaye v tomu sho vsyu amplitudu otrimanih velichin podibnosti rozbivayut na ryad klasiv a potim v matrici velichin podibnosti zaminyuyut ci velichini shtrihuvannyam riznoyi dlya kozhnogo klasu prichomu zazvichaj dlya bilsh visokih klasiv podibnosti zastosovuyut temnishe shtrihuvannya Potim zminyuyuchi poryadok opisiv v tablici domagayutsya togo shob podibni opisi buli roztashovani poruch 18 Navedemo gipotetichnij priklad otrimannya takoyi diagrami Osnovoyu metodu ye pobudova matrici tranzitivnogo zamikannya 19 nbsp Priklad rozrahunku diagrami ChekanovskogoDlya pobudovi matrici tranzitivnogo zamikannya vizmemo prostu matricyu podibnosti i pomnozhimo yiyi na samu sebe K 2 i j max min K i 1 K 1 j min K i q K q j displaystyle K 2 i j max min K i 1 K 1 j min K i q K q j nbsp de K i j displaystyle K i j nbsp element sho stoyit na peretini i displaystyle i nbsp go ryadka j displaystyle j nbsp go stovpcya v novij drugij matrici otrimanij pislya pershoyi iteraciyi q displaystyle q nbsp zagalna kilkist ryadkiv stovpchikiv matrici podibnosti Danu proceduru neobhidno prodovzhuvati poki matricya ne stane idempotentnoyu tobto samopodibnoyu K n i j K n 1 i j displaystyle K n i j K n 1 i j nbsp de n displaystyle n nbsp kilkist iteracij Dali peretvoryuyemo matricyu takim chinom shob blizki chislovi znachennya znahodilisya poryad Yaksho kozhnomu chislovomu znachennyu postaviti u vidpovidnist bud yakij kolir abo vidtinok koloru yak u nashomu vipadku to otrimayemo klasichnu diagramu Chekanovskogo Tradicijno temnishij kolir vidpovidaye bilshij podibnosti a svitlishij menshij V comu vona shozha z teplokartoyu matrici vidstanej Div takozh red Graf matematika Klasternij analiz Metrichnij prostir Zavdannya klasifikaciyi Gilkova dekompoziciyaPrimitki red Rokach Lior and Oded Maimon Clustering methods Data mining and knowledge discovery handbook Springer US 2005 321 352 R Sibson 1973 SLINK an optimally efficient algorithm for the single link cluster method PDF The Computer Journal British Computer Society 16 1 doi 10 1093 comjnl 16 1 30 Arhiv originalu PDF za 24 veresnya 2014 Procitovano 31 zhovtnya 2018 a b Schutze Hinrich Christopher D Manning Raghavan Prabhakar 2008 Introduction to information retrieval Cambridge UK Cambridge University Press ISBN 0 521 86571 9 Arhiv originalu za 12 listopada 2018 D Defays 1977 An efficient algorithm for a complete link method The Computer Journal British Computer Society 20 4 doi 10 1093 comjnl 20 4 364 Arhiv originalu za 12 zhovtnya 2016 Procitovano 31 zhovtnya 2018 Zhambyu M Iyerarhichnij klaster analiz ta vidpovidnosti M Finansy i statistika 1988 345 s Klassifikaciya i klaster Pod red Dzh Ven Rajzina M Mir 1980 390 s Ajvazyan S A Buhshtaber V M Enyukov I S Meshalkin L D Prikladnaya statistika Klassifikaciya i snizhenie razmernosti M Finansy i statistika 1989 607 s Lance G N Willams W T A general theory classification of sorting strategies 1 Hierarchical systems Comp J 1967 9 P 373 380 Sneath P H A Sokal R R Numerical taxonomy The principles and practices of numerical classification San Francisco Freeman 1973 573 p Ward J H Hierarchical grouping to optimize an objective function J of the American Statistical Association 1963 236 r von Terentjev P V Biometrische Untersuchungen uber die morphologischen Merkmale von Rana ridibunda Pall Amphibia Salientia Arhivovano 5 bereznya 2016 u Wayback Machine Biometrika 1931 23 1 2 P 23 51 Terentyev P U Metod korelyacijnih pleyad Visn LDU 9 1959 S 35 43 Terentyev P U Podalshij rozvitok metodu korelyacijnih pleyad Zastosuvannya matematichnih metodiv v biologiyi T 1 L 1960 S 42 58 Vyhandu L K Pro doslidzhenni mnogopriznakovyh biologichnih sistem Zastosuvannya matematichnih metodiv v biologiyi L vyp 3 1964 S 19 22 Shtejngauz R Matematichnij kalejdoskop M Nauka 1981 160 s Florek K Lukaszewicz S Percal S Steinhaus H Zubrzycki S Taksonomia Wroclawska Przegl antropol 1951 T 17 S 193 211 Czekanowski J Zur differential Diagnose der Neandertalgruppe Korrespbl Dtsch Ges Anthropol 1909 Bd 40 S 44 47 Vasilevich V I Statisticheskie metody v geobotanike L Nauka 1969 232 s Tamura S Hiquchi S Tanaka K Pattern classification based on fuzzy relation Arhivovano 17 travnya 2017 u Wayback Machine IEEE transaction on systems man and cybernetics 1971 SMC 1 1 P 61 67 Otrimano z https uk wikipedia org w index php title Iyerarhichna klasterizaciya amp oldid 37405509