Кіріспе
Кластерлердің иерархиясын құруға бағытталған статистикалық талдау әдісі. Деректерді өндіру және статистика салаларында иерархиялық кластерлеу (иерархиялық кластерлік талдау немесе HCA деп те аталады) – кластерлердің иерархиясын құруға бағытталған кластерлік талдау әдісі. Иерархиялық кластерлеу стратегиялары көбінесе екі санатқа бөлінеді:
Агломеративтік: Бұл "төменнен жоғарыға" қарайғы әдіс: әрбір дерек нүктесі өз кластерінен басталады, ал кластерлердің жұптары иерархия бойымен жоғары қарай жылжығанда біріктіріледі. Бөлу: Бұл "жоғарыдан төменге" қарайғы әдіс: барлық дерек нүктелері бір кластерден басталады, ал иерархия бойынша төмен қарай жылжығанда бөлінулер рекурсивті түрде орындалады. Жалпы, бірігулер мен бөлінулер ашкөздік қағидасы бойынша анықталады. Иерархиялық кластерлеу нәтижелері әдетте дендрограмма түрінде көрсетіледі. Иерархиялық кластерлеудің ерекше артықшылығы – қашықтықтың кез келген жарамды өлшемін қолдану мүмкіндігі. Шындығында, дерек нүктелерінің өзі қажет емес, тек қашықтықтар матрицасы ғана қолданылады. Дегенмен, жалғыз байланыс қашықтығының ерекше жағдайын есептемегенде, алгоритмдердің ешқайсысы (атап айтқанда, толық іздеуді есептемегенде) оңтайлы шешімді табуға кепілдік бермейді.
In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two categories:
Agglomerative: This is a "bottom up" approach: Each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. Divisive: This is a "top down" approach: All observations start in one cluster, and splits are performed recursively as one moves down the hierarchy. In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram. Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a matrix of distances. On the other hand, except for the special case of single linkage distance, none of the algorithms (except exhaustive search in ) can be guaranteed to find the optimum solution.
Күрделілігі
Иерархиялық агломеративтік кластерлеудің (HAC) стандартты алгоритмі уақыт күрделілігіне ие және жадты қажет етеді, бұл оны тіпті орташа көлемдегі деректер жиынтықтары үшін де тым баяу етеді. Дегенмен, кейбір ерекше жағдайларда тиімді агломеративтік әдістер белгілі (күрделілігі ): SLINK бір байланыс үшін және CLINK толық байланыс кластерлеуі үшін. Heap пайдалану арқылы, жалпы жағдайдың орындалу уақытын , жоғарыда аталған шектеуден жақсартуға болады, бірақ бұл жад талаптарын одан әрі арттырудың есебінен мүмкін. Көптеген жағдайларда, осы тәсілдің жадқа қажетті қосымша шығындары оны практикалық қолдануға қолайсыз етеді. Жалпы орындалу уақытын және кеңістікті көрсететін квадристерді қолданатын әдістер де бар. Кез келген іздеумен дивизивтік кластерлеу , бірақ k-ортасы сияқты бөліністерді таңдау үшін жылдам эвристика қолдану жиі кездеседі.
Коммерциялық іске асыру
MATLAB иерархиялық кластерлік талдауды қамтиды. SAS PROC CLUSTER-де иерархиялық кластерлік талдау бар. Mathematica-да иерархиялық кластерлеуге арналған пакет бар. NCSS иерархиялық кластерлік талдауды қамтиды. SPSS иерархиялық кластерлік талдауды қамтиды. Qlucore Omics Explorer иерархиялық кластерлік талдауды қамтиды. Stata иерархиялық кластерлік талдауды қамтиды. CrimeStat географиялық ақпараттық жүйе үшін графикалық көрінісі бар ең жақын көрші иерархиялық кластерлік алгоритмін қамтиды.