Кластеризация алгоритмдері Иерархиялық кластеризациясы 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 2020
әкімшілігінің қараңыз

    Басты бет
рсетілетін ызмет
Жалпы ережелер
ызмет стандарты
дістемелік кешені
бекіту туралы
туралы хабарландыру
біліктілік талаптары
кіміні аппараты
Конкурс туралы
жалпы біліктілік
ойылатын жалпы
мемлекеттік кімшілік
жалпы конкурс
Барлы конкурс
білім беретін
ызмет регламенті
республикасы білім
ткізу туралы
конкурс атысушыларына
біліктілік талаптар
атысушыларына арнал
бойынша жиынты
Республикасы кіметіні
идаларын бекіту
облысы кімдігіні
рсетілетін ызметтер
мемлекеттік ызмет
стандарттарын бекіту
Конкурс ткізу
мемлекеттік мекемесі
дебиеті маманды
дістемелік материалдар
дістемелік сыныстар
Мектепке дейінгі
ауданы кіміні
конкурс туралы
жалпы білім
рметті студент
облысы бойынша
мыссыз азаматтар
Мемлекеттік кірістер
мектепке дейінгі
білім беруді
дарламасыны титулды
Конкурс жариялайды
мелетке толма
разрядты спортшы
ызметтер стандарттарын
дістемелік кешен
директоры бдиев
аласы кіміні

Loading...