Кластеризация алгоритмдері Иерархиялық кластеризациясы Single Link, Complete Link, Group Average

Loading...


Дата21.03.2020
өлшемі0.51 Mb.

Кластеризация алгоритмдері

Иерархиялық кластеризациясы

Single Link, Complete Link, Group Average

Деректерді кластерлеу алгоритмдерінің бірі. Бұл әдістердің ерекшелігі, олар құжаттарды кластерлерге оларды иерархиялық топтарға бөлу жолымен бөледі, көптеген кластерлер алатын иерархиялық құрылымы бар. Олар иерархиялық агломерациялық кластерлеу әдістері деп аталады. Иерархиялық агломерациялық процедуралардың жұмыс істеу принципі элементтер топтарын, алдымен ең жақын, содан кейін бір- бірінен алыс элементтерді тізбектеп біріктіруден тұрады. Кластерлік талдаудың иерархиялық әдістері деректер жиынтығының шағын көлемінде қолданылады. Ағаштың классикалық мысалы - жануарлар мен өсімдіктердің жіктелуі.

Иерархиялық кластеризациясы

Осы әдістердің негізгі мәні келесі қадамдарды орындау болып табылады:

  • элементтердің арасындағы жақындық мәндерін есептеу және жақындық матрицасын алу;
  • әр элементті жеке кластерге анықтау;
  • ең жақын жұп элементтерді бір кластерге қосу;
  • кластерлер үшін бағандар мен жолдарды жою арқылы жақындығы матрицасын жаңарту, олар басқалармен қосылған және одан әрі матрицаны қайта есептеу;
  • аялдама критериі жұмыс істемейінше 3- қадамға көшу

Бұл үш әдіс өзара 4-қадамда ерекшеленеді.
  • Және жақындық матрицасын жаңарту тәсілдерінің арқасында әртүрлі Алгоритмдер әртүрлі дәлдікке ие. Алгоритмдердің дәлдігін тексеру арнайы тестілік жиынтықтарда жүргізілді және Single Link алгоритмінің ең аз дәлдігіне ие екенін көрсетті, ал қалған екеуі - Single Link-ге қарағанда неғұрлым жоғары. Аялдамалық критерий ретінде кластердегі құжаттардың ең көп саны таңдалады.
  • Single Link және Group Average - O(n2) алгоритмдерінің жұмыс күрделігі, ал Complete Link - O(n3), мұнда N - элементтер саны. Single Link - O(n) алгоритмімен атқаратын жады саны.

Әдістердің артықшылықтары:

Әдістердің артықшылықтары:

  • Алгоритмдер оқытуды қажет етпейді;
  • Элементтердің арасындағы жақындығы матрицасын пайдалану;
  • Инкременттік алгоритмдер.

Әдістердің кемшіліктері:

Әдістердің кемшіліктері:

  • Шекті қою қажет- кластердегі элементтердің ең көп саны;
  • Кластеризацияның жақсы нәтижелерін алу үшін элементтер жұптарының арасындағы жақындықтың мәні белгілі бір тәртіпте келуі тиіс, яғни алгоритм жұмысы детерминацияланбаған;
  • Кластерлер қиылыспайды.

Метод

Функция стоимости

Single - link

mind(xi,xj),xi,j ≤ Si,j

Average – link

d()

Complete - link

maxd(xi,xj),xi,j ≤ Si,j

Метод

Функция стоимости

Single - link

mind(xi,xj),xi,j ≤ Si,j

Average – link

Complete - link

maxd(xi,xj),xi,j ≤ Si,j

K-MEANS АЛГОРИТМІ

  • K-орташа алгоритмі бір-бірінен мүмкіндігінше үлкен қашықтықта орналасқан k кластерлерін салады. K-орташа алгоритмін шешетін міндеттердің негізгі түрі-кластерлер санына қатысты жорамалдар (гипотезалар) болуы, бұл ретте олар мүмкіндігінше әртүрлі болуы тиіс. K санын таңдау алдыңғы зерттеулердің нәтижелеріне, теориялық пайымдауларға немесе түйсікке негізделуі мүмкін.Алгоритмнің жалпы идеясы: бақылау кластерлерінің берілген белгіленген саны кластерлерге орташа кластерде (барлық айнымалылар үшін) бір-бірінен барынша ерекшеленетіндай етіп салыстырылады.

Алгоритмнің сипаттамасы

1. Кластерлер бойынша объектілерді бастапқы бөлу.

K саны таңдалады және бірінші қадамда бұл нүктелер кластерлердің "орталықтары" болып саналады. Әрбір кластерге бір орталық сәйкес келеді. Бастапқы орталықтарды таңдау мынадай түрде жүзеге асырылуы мүмкін:

  • бастапқы қашықтықты максималдау үшін k-бақылауларды таңдау;
  • k-бақылауларды кездейсоқ таңдау;
  • алғашқы k-бақылауларды таңдау.

  • Нәтижесінде әрбір объект белгілі бір кластерге тағайындалған.

    2. Итеративтік процесс.

    Кластерлер орталықтары есептеледі, олар одан кейін және одан әрі үйлестірілген орта кластерлер болып саналады. Нысандар қайта бөлінеді. Орталықтарды есептеу және объектілерді қайта бөлу процесі шарттардың бірі орындалғанға дейін жалғасады:

    кластерлік орталықтар тұрақтанды, яғни барлық бақылау ағымдағы итерацияға дейін тиесілі кластерге тиесілі.;



    Итерация саны ең көп Итерация санына тең .

Кластерлеу сапасын тексеру
  • K-орташа әдісімен кластерлік талдау нәтижелерін алғаннан кейін кластерлеудің дұрыстығын тексеру керек (яғни кластерлердің бір-бірінен қаншалықты айырмашылығы бар екендігін бағалау). Бұл үшін әрбір кластер үшін орташа мәндер есептеледі. Жақсы кластерлеу кезінде барлық өлшеулер үшін өте ерекшеленетін орташа немесе олардың ең болмағанда көп бөлігі алынуы тиіс.
  • K-MEANS алгоритмінің күрделілігі O(nkl), k – кластерлер саны, l – итерация саны, n- элементтер саны.

K-MEANS АЛГОРИТМІ

K-орташа алгоритмінің артықшылықтары:

  • пайдалану оңай;
  • пайдалану жылдамдығы;
  • алгоритмнің түсініктілігі мен ашықтығы.

K-орташа алгоритмінің кемшіліктері:

  • алгоритм орташаны бұрмалауы мүмкін шығарындыларға өте сезімтал. Бұл проблеманы шешу мүмкін болып k - медиана алгоритмінің модификациясын қолдану табылады;
  • алгоритм үлкен деректер базасында баяу жұмыс істей алады. Бұл мәселені шешу мүмкін деректер таңдауын пайдалану болып табылады.

Қорытынды


Күрделігі

Кластердің формасы

Кіретін ақпарат

Нәтиже

Қолданылады

Иерархия-лық

O(n2), n- элементтер саны.

Еркін

Кластерлер саны немесе иерархияны кесу үшін қашықтық шегі

Кластерлердің екілік ағашы

деректер жиынтығының шағын көлемінде

K-MEANS

O(nkl), k – кластерлер саны, l – итерация саны, n- элементтер саны.

Гиперсфера

Кластерлер саны

Кластерлер ортасы

деректер жиынтығының шағын көлемінде

Пайдаланылған әдебиеттер

  • https://www.intuit.ru/studies/courses/6/6/lecture/184
  • https://yourcmc.ru/wiki/images/0/09/Girshov_clustering.pdf
  • https://www.intuit.ru/studies/courses/6/6/lecture/182?page=2

THANKS!



Достарыңызбен бөлісу:
Loading...


©melimde.com 2019
әкімшілігінің қараңыз

    Басты бет

Loading...